Lattice rules with random $n$ achieve nearly the optimal $\mathcal{O}(n^{-\alpha -1/2})$ error independently of the dimension

Abstract

We analyze a new random algorithm for numerical integration of $d$-variate functions over $[0,1{]}^d$ from a weighted Sobolev space with dominating mixed smoothness $\alpha \ge 0$ and product weights $1\ge {\gamma }_1\ge {\gamma }_2\ge \cdots >0$, where the functions are continuous and periodic when $\alpha >1/2$. The algorithm is based on rank-$1$ lattice rules with a random number of points~$n$. For the case $\alpha >1/2$, we prove that the algorithm achieves almost the optimal order of convergence of $\mathcal{O}(n^{-\alpha -1/2})$, where the implied constant is independent of the dimension~$d$ if the weights satisfy ${\sum }_{j=1}^{\infty }{\gamma }_j^{1/\alpha }<\infty$. The same rate of convergence holds for the more general case $\alpha >0$ by adding a random shift to the lattice rule with random $n$. This shows, in particular, that the exponent of strong tractability in the randomized setting equals $1/(\alpha +1/2)$, if the weights decay fast enough. We obtain a lower bound to indicate that our results are essentially optimal. This paper is a significant advancement over previous related works with respect to the potential for implementation and the independence of error bounds on the problem dimension. Other known algorithms which achieve the optimal error bounds, such as those based on Frolov's method, are very difficult to implement especially in high dimensions. Here we adapt a lesser-known randomization technique introduced by Bakhvalov in 1961. This algorithm is based on rank-$1$ lattice rules which are very easy to implement given the integer generating vectors. A simple probabilistic approach can be used to obtain suitable generating vectors.

17 pages

References in corpus (4)

• The role of Frolov's cubature formula for functions with bounded mixed derivative
• Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube
• A Monte Carlo method for integration of multivariate smooth functions
• An explicit construction of optimal order quasi-Monte Carlo rules for smooth integrands

Cited by in corpus (5)

• Construction-free median quasi-Monte Carlo rules for function spaces with unspecified smoothness and general weights
• Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm
• Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate
• Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
• Möbius-Transformed Trapezoidal Rule