A Monte Carlo method for integration of multivariate smooth functions

Abstract

We study a Monte Carlo algorithm that is based on a specific (randomly shifted and dilated) lattice point set. The main result of this paper is that the mean squared error for a given compactly supported, square-integrable function is bounded by $n^{-1/2}$ times the $L_2$-norm of the Fourier transform outside a region around the origin, where $n$ is the expected number of function evaluations. As corollaries we obtain the optimal order of convergence for functions from the Sobolev spaces $H_p^s$ with isotropic, anisotropic, or mixed smoothness with given compact support for all values of the parameters. If the region of integration is the unit cube, we obtain the same optimal orders for functions without boundary conditions. This proves, in particular, that the optimal order of convergence in the latter case is $n^{-s-1/2}$ for $p\ge 2$, which is, in contrast to the case of deterministic algorithms, independent of the dimension. This shows that Monte Carlo algorithms can improve the order by more than $n^{-1/2}$ for a whole class of natural function spaces.

The numbering of the theorems differs from the published version

References in corpus (5)

• The role of Frolov's cubature formula for functions with bounded mixed derivative
• A direct proof of Sobolev embeddings for quasi-homogeneous Lizorkin--Triebel spaces with mixed norms
• Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube
• Hyperbolic Cross Approximation
• Product rules are optimal for numerical integration in classical smoothness spaces

Cited by in corpus (9)

• Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube
• Lattice rules with random $n$ achieve nearly the optimal $\mathcal{O}(n^{-\alpha -1/2})$ error independently of the dimension
• A note on the dispersion of admissible lattices
• A universal median quasi-Monte Carlo integration
• Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate
• Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration
• Consistency of randomized integration methods
• Enumeration of the Chebyshev-Frolov lattice points in axis-parallel boxes
• Digital net properties of a polynomial analogue of Frolov's construction