Most error analyses for numerical integration algorithms specify the space of integrands and then determine the convergence rate for a particular algorithm or the optimal algorithm. This article takes a different perspective of specifying the convergence rate and then finding the largest space of integrands for which the algorithm gives that desired rate. Both worst-case and randomized error analyses are provided.
Most error analyses for numerical integration algorithms specify the space of integrands and then determine the convergence rate for a particular algorithm or the optimal algorithm. This article takes a different perspective of specifying the convergence rate and then finding the largest space of integrands for which the algorithm gives that desired rate. Both worst-case and randomized error analyses are provided.
We present an algorithm for multivariate integration over cubes that is unbiased and has optimal order of convergence (in the randomized sense as well as in the worst case setting) for all Sobolev spaces Hr,mix([0,1]d) and Hs([0,1]d) for s>d/2.
A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with 0<α≤1/2
In previous work (Kuo, Nuyens, Wilkes, 2023), we showed that a lattice rule with a pre-determined generating vector but random number of points can achieve the near optimal convergence of O(n−α−1/2+ε), ε>0, for the worst case expected error, commonly referred to as the randomised error, for numerical integration of high-dimensional functions in the Korobov space with smoothness α>1/2. Compared to the optimal deterministic rate of O(n−α+ε), ε>0, such a randomised algorithm is capable of an extra half in the rate of convergence. In this paper, we show that a pre-determined generating vector also exists in the case of 0<α≤1/2. Also here we obtain the near optimal convergence of O(n−α−1/2+ε), ε>0; or in more detail, we obtain O(rn−α−1/2+1/(2r)+ε′) which holds for any choices of ε′>0 and r∈N with r>1/(2α).
Recent advances in quasi-Monte Carlo integration demonstrate that the median of linearly scrambled digital net estimators achieves near-optimal convergence rates for high-dimensional integrals without requiring a priori knowledge of the integrand’s smoothness. Building on this framework, we prove that the median estimator attains dimension-independent convergence, a property known as strong tractability in complexity theory, under tractability conditions characterized by low effective dimensionality. Using a probabilistic, integrand-specific error criterion, our analysis establishes both faster and dimension-independent convergence under weaker assumptions than previously possible in the worst-case setting.