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

DOI10.1214/11-AOS880MaRDI QIDQ638795zbMATH OpenFDO

Authors Josef Dick

Publication date 14 September 2011

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

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

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)

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.

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

Cites work

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

Cited in

(26)

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

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)