Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands

DOI10.1214/11-AOS880zbMATH Open1298.65011arXiv1007.0842MaRDI QIDQ638795FDOQ638795

Authors: Josef Dick 

Publication date: 14 September 2011

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: We study a random sampling technique to approximate integrals $in{t}_{[0,1{]}^s}f(mathbfx),mathrmdmathbfx$ by averaging the function at some sampling points. We focus on cases where the integrand is smooth, which is a problem which occurs in statistics. The convergence rate of the approximation error depends on the smoothness of the function $f$ and the sampling technique. For instance, Monte Carlo (MC) sampling yields a convergence of the root mean square error (RMSE) of order $N^{-1/2}$ (where $N$ is the number of samples) for functions $f$ with finite variance. Randomized QMC (RQMC), a combination of MC and quasi-Monte Carlo (QMC), achieves a RMSE of order $N^{-3/2+varepsilon}$ under the stronger assumption that the integrand has bounded variation. A combination of RQMC with local antithetic sampling achieves a convergence of the RMSE of order $N^{-3/2-1/s+varepsilon}$ (where $sge1$ is the dimension) for functions with mixed partial derivatives up to order two. Additional smoothness of the integrand does not improve the rate of convergence of these algorithms in general. On the other hand, it is known that without additional smoothness of the integrand it is not possible to improve the convergence rate. This paper introduces a new RQMC algorithm, for which we prove that it achieves a convergence of the root mean square error (RMSE) of order $N^{-alpha-1/2+varepsilon}$ provided the integrand satisfies the strong assumption that it has square integrable partial mixed derivatives up to order $alpha>1$ in each variable. Known lower bounds on the RMSE show that this rate of convergence cannot be improved in general for integrands with this smoothness. We provide numerical examples for which the RMSE converges approximately with order $N^{-5/2}$ and $N^{-7/2}$, in accordance with the theoretical upper bound.

Full work available at URL: https://arxiv.org/abs/1007.0842

Recommendations

• Scrambled net variance for integrals of smooth functions
• On the variance of quadrature over scrambled nets and sequences
• On integration methods based on scrambled nets of arbitrary size
• The mean square quasi-Monte Carlo error for digitally shifted digital nets
• Scrambling Sobol' and Niederreiter-Xing points

zbMATH Keywords

randomized quasi-Monte Carlo methodsexact convergence ratedigital \((t,m,s)\)-netsOwen's scrambling on order \(d\)root mean square worst-case error

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical integration (65D30) Well-distributed sequences and other variations (11K36) Pseudo-random numbers; Monte Carlo methods (11K45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Monte Carlo Variance of Scrambled Net Quadrature
• A class of generalized Walsh functions
• Title not available (Why is that?)
• Explicit Constructions of Quasi-Monte Carlo Rules for the Numerical Integration of High-Dimensional Periodic Functions
• Walsh Spaces Containing Smooth Functions and Quasi–Monte Carlo Rules of Arbitrary High Order
• Geometric discrepancy. An illustrated guide
• Deterministic and stochastic error bounds in numerical analysis
• Local antithetic sampling with scrambled nets
• Scrambled net variance for integrals of smooth functions
• On the \(L_2\)-discrepancy for anchored boxes
• On quasi-Monte Carlo rules achieving higher order convergence
• Variance with alternative scramblings of digital nets
• \(I\)-binomial scrambling of digital nets and sequences
• The mean square discrepancy of randomized nets
• Title not available (Why is that?)
• The discrepancy and gain coefficients of scrambled digital nets.

Cited In (26)

• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• The mean square quasi-Monte Carlo error for digitally shifted digital nets
• Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
• Convergence analysis of deterministic kernel-based quadrature rules in misspecified settings
• Quasi-Monte Carlo integration using digital nets with antithetics
• On the convergence rate of randomized quasi-Monte Carlo for discontinuous functions
• Higher-Order Monte Carlo through Cubic Stratification
• Fast construction of higher order digital nets for numerical integration in weighted Sobolev spaces
• Super-polynomial accuracy of one dimensional randomized nets using the median of means
• Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration
• \(I\)-binomial scrambling of digital nets and sequences
• A constraint on extensible quadrature rules
• Scrambling non-uniform nets
• Decision-theoretic sensitivity analysis for reservoir development under uncertainty using multilevel quasi-Monte Carlo methods
• Modification of the Maximin and ϕ_p (Phi) Criteria to Achieve Statistically Uniform Distribution of Sampling Points
• Discrepancy theory and quasi-Monte Carlo integration
• Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules
• Integration and approximation based on scramble sampling in arbitrary dimensions
• Comment: unreasonable effectiveness of Monte Carlo
• Improved bounds on the gain coefficients for digital nets in prime power base
• Scrambled geometric net integration over general product spaces
• The discrepancy and gain coefficients of scrambled digital nets.
• Construction of interlaced scrambled polynomial lattice rules of arbitrary high order
• Transformations and Hardy-Krause variation
• Optimal order quadrature error bounds for infinite-dimensional higher-order digital sequences
• On Dropping the First Sobol’ Point

This page was built for publication: Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q638795)