Local antithetic sampling with scrambled nets

DOI10.1214/07-AOS548MaRDI QIDQ955143zbMATH OpenFDO

Authors Art B. Owen

Publication date 18 November 2008

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

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

zbMATH Keywords

ANOVA decompositionb-ary reflections and foldscubatureDigital netsDigital scramblesMonomial rulesmultidimensional quadraturesRandomized quasi-Monte Carlo methodroot mean square errorVariance for scrambled digital netsvariance reduction methods

Mathematics Subject Classification ID

Pseudo-random numbers; Monte Carlo methods (11K45) Approximate quadratures (41A55) Multidimensional problems (41A63) Monte Carlo methods (65C05)

Abstract: We consider the problem of computing an approximation to the integral $I=in{t}_{[0,1{]}^d}f(x)dx$. Monte Carlo (MC) sampling typically attains a root mean squared error (RMSE) of $O(n^{-1/2})$ from $n$ independent random function evaluations. By contrast, quasi-Monte Carlo (QMC) sampling using carefully equispaced evaluation points can attain the rate $O(n^{-1+varepsilon})$ for any $varepsilon>0$ and randomized QMC (RQMC) can attain the RMSE $O(n^{-3/2+varepsilon})$, both under mild conditions on $f$. Classical variance reduction methods for MC can be adapted to QMC. Published results combining QMC with importance sampling and with control variates have found worthwhile improvements, but no change in the error rate. This paper extends the classical variance reduction method of antithetic sampling and combines it with RQMC. One such method is shown to bring a modest improvement in the RMSE rate, attaining $O(n^{-3/2-1/d+varepsilon})$ for any $varepsilon>0$, for smooth enough $f$.

Review text

Many problems in science and engineering require multidimensional quadratures. The Monte Carlo integration can be improved by the use of variance reduction methods. The author extends the classical variance reduction method of antithetic sampling and combine it with randomized quasi-Monte Carlo methods. Several ways of combining and randomized digital nets are considered. The main result is that for any \(\epsilon > 0\) such method reduces the rate of the root mean square error (RMSE) of the integration of smooth integrands to \({\mathcal O}\left( n^{-{3 \over 2} - {1 \over d} + \epsilon}\right),\) where \(d\) is the dimension. In section 2 the information on scrambled nets is reminded. The concepts of \((q,m,d)\)-nets, \((\lambda,q,m,d)\)-nets and \((q,d)\)-sequences in base \(b \geq 2\) are discussed. Techniques of random scrambles as a random linear scrambling, an affine matrix scramble with a different structure of the matrices are presented. The ANOVA decomposition of functions is reminded. In Section 3 \(d\)-dimensional folding operations are used to introduce local antithetic properties into digital nets. Three specific methods -- reflection nets, box folded nets and monomial nets -- are introduced for inducing local antithetic properties in some \((q,m,2)\)-nets. In Section 4 these three methods are illustrated to concrete two-dimensional integrand. In Section 5 the variance for scrambled digital nets quadrature of smooth functions is considered. Theorem 2 shows some upper bounds of the gain coefficients for a \((0,m,d)\)-net, a \((\lambda,0,m,d)\)-net and a \((\lambda,q,m,d)\)-net in base \(b.\) Theorem 3 gives an order \({\mathcal O}\left( n^{-{3 \over 2}} (\log n)^{d-1 \over 2}\right)\) of the RMSE of the integration of smooth functions using a randomized relaxed \((\lambda,q,m,d)\)-net in base \(b.\) In Section 6 the effect of the reflection scheme on a scrambled net is investigated. The concept of the box fold scheme is introduced. Theorem 4 states that for doubly smooth functions under the box folding on a randomized relaxed \((\lambda,0,m,d)\)-net in base \(b\) the RMSE of the integration has an order \({\mathcal O}\left( n^{-{3 \over 2} - {1 \over d}} (\log n)^{d-1 \over 2}\right).\) In Section 7 the box folding scheme is presented as a hybrid of a monomial cubature rule with scrambled net sampling.

Recommendations

• Barren plateaus from learning scramblers with local cost functions
• Approximation by neural networks with scattered data
• Scrambling non-uniform nets
• An Acceleration Strategy for Randomize-Then-Optimize Sampling Via Deep Neural Networks
• Neural networks-based variationally enhanced sampling
• Scattered data interpolation based upon generalized minimum norm networks
• Neural Networks for Localized Approximation
• scientific article; zbMATH DE number 7306864
• Localized sampling in the presence of noise

Cites work

• \(I\)-binomial scrambling of digital nets and sequences
• A Class of Statistics with Asymptotically Normal Distribution
• Control variates for quasi-Monte Carlo (with comments and rejoinder)
• Discrépance de suites associées à un système de numération (en dimension s)
• Funktionen von beschränkter Variation in der Theorie der Gleichverteilung
• Geometric discrepancy. An illustrated guide
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 3591295 (Why is no real title available?)
• scientific article; zbMATH DE number 1103058 (Why is no real title available?)
• scientific article; zbMATH DE number 1999206 (Why is no real title available?)
• scientific article; zbMATH DE number 822320 (Why is no real title available?)
• scientific article; zbMATH DE number 914714 (Why is no real title available?)
• scientific article; zbMATH DE number 3302899 (Why is no real title available?)
• MinT: A Database for Optimal Net Parameters
• Monomial cubature rules since ``Stroud: A compilation
• Monomial cubature rules since ``Stroud: A compilation. II
• Monte Carlo Variance of Scrambled Net Quadrature
• Numerical Evaluation of Multiple Integrals
• Quasi-Random Methods for Estimating Integrals Using Relatively Small Samples
• Scrambled net variance for integrals of smooth functions
• Scrambling Sobol' and Niederreiter-Xing points
• Tensor Analysis of ANOVA Decomposition
• The discrepancy and gain coefficients of scrambled digital nets.
• The jackknife estimate of variance
• The microstructure of \((t,m,s)\)-nets
• Variance with alternative scramblings of digital nets

Cited in

(28)

• Decision-theoretic sensitivity analysis for reservoir development under uncertainty using multilevel quasi-Monte Carlo methods
• Monte Carlo integration of non-differentiable functions on \([0,1]^\iota\), \(\iota =1,\ldots, d\), using a single determinantal point pattern defined on \([0,1]^d\)
• Sensitivity estimation of conditional value at risk using randomized quasi-Monte Carlo
• Monte Carlo with determinantal point processes
• Are quasi-Monte Carlo algorithms efficient for two-stage stochastic programs?
• Scrambled geometric net integration over general product spaces
• Quasi-Monte Carlo integration using digital nets with antithetics
• Van der Corput and Golden ratio sequences along the Hilbert space-filling curve
• Improving Approximate Bayesian Computation via Quasi-Monte Carlo
• Scrambling non-uniform nets
• A Strong Law of Large Numbers for Scrambled Net Integration
• scientific article; zbMATH DE number 7626758 (Why is no real title available?)
• Quasi-Random Sampling for Multivariate Distributions via Generative Neural Networks
• Quasi-Monte Carlo methods for lattice systems: a first look
• Preintegration via Active Subspace
• On the Error Rate of Importance Sampling with Randomized Quasi-Monte Carlo
• On Dropping the First Sobol’ Point
• Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands
• Conditional quasi-Monte Carlo with constrained active subspaces
• Achieving high convergence rates by quasi-Monte Carlo and importance sampling for unbounded integrands
• Generalization error analysis of deep backward dynamic programming for solving nonlinear PDEs
• Accelerated convergence of error quantiles using robust randomized quasi Monte Carlo methods
• Skewness of a randomized quasi-Monte Carlo estimate
• Integrability of weak mixed first-order derivatives and convergence rates of scrambled digital nets
• Randomized quasi-Monte Carlo and Owen's boundary growth condition: a spectral analysis
• Empirical Bernstein and betting confidence intervals for randomized quasi-Monte Carlo
• Repelled point processes with application to numerical integration
• On integration methods based on scrambled nets of arbitrary size

Describes a project that uses

Uses Software

• MinT

This page was built for publication: Local antithetic sampling with scrambled nets

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