A universal median quasi-Monte Carlo integration

Abstract

We study quasi-Monte Carlo (QMC) integration over the multi-dimensional unit cube in several weighted function spaces with different smoothness classes. We consider approximating the integral of a function by the median of several integral estimates under independent and random choices of the underlying QMC point sets (either linearly scrambled digital nets or infinite-precision polynomial lattice point sets). Even though our approach does not require any information on the smoothness and weights of a target function space as an input, we can prove a probabilistic upper bound on the worst-case error for the respective weighted function space, where the failure probability converges to 0 exponentially fast as the number of estimates increases. Our obtained rates of convergence are nearly optimal for function spaces with finite smoothness, and we can attain a dimension-independent super-polynomial convergence for a class of infinitely differentiable functions. This implies that our median-based QMC rule is universal in the sense that it does not need to be adjusted to the smoothness and the weights of the function spaces and yet exhibits the nearly optimal rate of convergence. Numerical experiments support our theoretical results.

arXiv commentMinor revision, 33 pages, 4 figures

References in corpus (19)

• Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order
• Higher order QMC Galerkin discretization for parametric operator equations
• Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules
• The role of Frolov's cubature formula for functions with bounded mixed derivative
• Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces
• A Monte Carlo method for integration of multivariate smooth functions
• The decay of the Walsh coefficients of smooth functions
• Construction-free median quasi-Monte Carlo rules for function spaces with unspecified smoothness and general weights
• Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions
• Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm
• Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration
• Richardson extrapolation of polynomial lattice rules
• WAFOM on abelian groups for quasi-Monte Carlo point sets
• Formulas for the Walsh coefficients of smooth functions and their application to bounds on the Walsh coefficients
• Quasi-Monte Carlo point sets with small $t$-values and WAFOM
• Quasi-Monte Carlo integration using digital nets with antithetics
• Construction of interlaced polynomial lattice rules for infinitely differentiable functions
• Consistency of randomized integration methods
• Improved bounds on the gain coefficients for digital nets in prime power base

Cited by in corpus (2)

• The median trick does not help for fully nested scrambling
• A median QMC method for unbounded integrands over ${\mathbb{R}}^s$ in weighted unanchored Sobolev spaces