Automatic optimal-rate convergence of randomized nets using median-of-means

Pan, Zexin

doi:10.1090/mcom/4093

Automatic optimal-rate convergence of randomized nets using median-of-means
HTML articles powered by AMS MathViewer

by Zexin Pan;

Math. Comp.

DOI: https://doi.org/10.1090/mcom/4093

Published electronically: April 16, 2025

PDF | Request permission

Abstract:

We study the sample median of independently generated quasi-Monte Carlo estimators based on randomized digital nets and prove it approximates the target integral value at almost the optimal convergence rate for various function spaces. In contrast to previous methods, the algorithm does not require a priori knowledge of underlying function spaces or even an input of pre-designed $(t,m,s)$-digital nets, and is therefore easier to implement. This study provides further evidence that some types of randomized quasi-Monte Carlo estimators are heavy-tailed when applied to smooth integrands and taking the median can significantly improve the error by filtering out the outliers.

References

H. Bahouri, Fourier Analysis and Nonlinear Partial Differential Equations, Springer, 2011.
R. E. Caflisch, W. Morokoff, and A. B. Owen, Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. Computat. Finance 1 (1997), 27–46.
L. Chen, M. Xu, and H. Zhang, A random integration algorithm for high-dimensional function spaces, Preprint (2025).
Josef Dick, Koksma-Hlawka type inequalities of fractional order, Ann. Mat. Pura Appl. (4) 187 (2008), no. 3, 385–403. MR 2393141, DOI 10.1007/s10231-007-0048-z
Josef Dick, Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order, SIAM J. Numer. Anal. 46 (2008), no. 3, 1519–1553. MR 2391005, DOI 10.1137/060666639
Josef Dick, Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands, Ann. Statist. 39 (2011), no. 3, 1372–1398. MR 2850206, DOI 10.1214/11-AOS880
Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394, DOI 10.1017/CBO9780511761188
Rick Durrett, Probability: theory and examples, 4th ed., Cambridge Series in Statistical and Probabilistic Mathematics, vol. 31, Cambridge University Press, Cambridge, 2010. MR 2722836, DOI 10.1017/CBO9780511779398
M. Gnewuch, J. Dick, L. Markhasin, and W. Sickel, QMC integration based on arbitrary (t,m,s)-nets yields optimal convergence rates on several scales of function spaces, Preprint (2024).
E. Gobet, M. Lerasle, and D. Métivier, Mean estimation for randomized quasi monte carlo method, Hal preprint hal-03631879v2 (2022).
T. Goda and D. Krieg, A simple universal algorithm for high-dimensional integration, Preprint (2024).
Takashi Goda, Kosuke Suzuki, and Makoto Matsumoto, A universal median quasi–Monte Carlo integration, SIAM J. Numer. Anal. 62 (2024), no. 1, 533–566. MR 4706045, DOI 10.1137/22M1525077
Stefan Heinrich and Erich Novak, Optimal summation and integration by deterministic, randomized, and quantum algorithms, Monte Carlo and quasi-Monte Carlo methods, 2000 (Hong Kong), Springer, Berlin, 2002, pp. 50–62. MR 1958846
F. J. Hickernell, Koksma-Hlawka Inequality, Wiley StatsRef: Statistics Reference Online (2014).
Stephen Joe and Frances Y. Kuo, Constructing Sobol′sequences with better two-dimensional projections, SIAM J. Sci. Comput. 30 (2008), no. 5, 2635–2654. MR 2429482, DOI 10.1137/070709359
P. L’Ecuyer, M. K. Nakayama, A. B. Owen, and B. Tuffin, Confidence intervals for randomized quasi-Monte Carlo estimators, Tech. report, hal-04088085, 2023.
Ruixue Liu and Art B. Owen, Estimating mean dimensionality of analysis of variance decompositions, J. Amer. Statist. Assoc. 101 (2006), no. 474, 712–721. MR 2281247, DOI 10.1198/016214505000001410
Y. Liu, Randomized quasi-monte carlo and owen’s boundary growth condition: A spectral analysis, Preprint (2025).
Jiří Matoušek, On the $L_2$-discrepancy for anchored boxes, J. Complexity 14 (1998), no. 4, 527–556. MR 1659004, DOI 10.1006/jcom.1998.0489
Harald Niederreiter and Chaoping Xing, Low-discrepancy sequences and global function fields with many rational places, Finite Fields Appl. 2 (1996), no. 3, 241–273. MR 1398076, DOI 10.1006/ffta.1996.0016
Art B. Owen, Randomly permuted $(t,m,s)$-nets and $(t,s)$-sequences, Monte Carlo and quasi-Monte Carlo methods in scientific computing (Las Vegas, NV, 1994) Lect. Notes Stat., vol. 106, Springer, New York, 1995, pp. 299–317. MR 1445791, DOI 10.1007/978-1-4612-2552-2_{1}9
Art B. Owen, Scrambled net variance for integrals of smooth functions, Ann. Statist. 25 (1997), no. 4, 1541–1562. MR 1463564, DOI 10.1214/aos/1031594731
A. B. Owen, Halton sequences avoid the origin, SIAM Rev. 48 (2006), 487–583.
A. B. Owen, Error estimation for quasi-Monte Carlo, Preprint (2025).
Zexin Pan and Art B. Owen, Super-polynomial accuracy of one dimensional randomized nets using the median of means, Math. Comp. 92 (2023), no. 340, 805–837. MR 4524109, DOI 10.1090/mcom/3791
Pierre L’Ecuyer, Randomized quasi–Monte Carlo: an introduction for practitioners, Monte Carlo and quasi–Monte Carlo methods, Springer Proc. Math. Stat., vol. 241, Springer, Cham, 2018, pp. 29–52. MR 3828133, DOI 10.1007/978-3-319-91436-7_{2}
Zexin Pan and Art B. Owen, Super-polynomial accuracy of multidimensional randomized nets using the median-of-means, Math. Comp. 93 (2024), no. 349, 2265–2289. MR 4759375, DOI 10.1090/mcom/3880
I. M. Sobol′, Distribution of points in a cube and approximate evaluation of integrals, Ž. Vyčisl. Mat i Mat. Fiz. 7 (1967), 784–802 (Russian). MR 219238
Kosuke Suzuki and Takehito Yoshiki, Formulas for the Walsh coefficients of smooth functions and their application to bounds on the Walsh coefficients, J. Approx. Theory 205 (2016), 1–24. MR 3471153, DOI 10.1016/j.jat.2015.12.002
Z. Ye, J. Dick, and X. Wang, Median QMC method for unbounded integrands over $\mathbb {R}^s$ in unanchored weighted sobolev spaces, Preprint (2025).

AMS Website Down

Mathematics of Computation

Automatic optimal-rate convergence of randomized nets using median-of-means
HTML articles powered by AMS MathViewer

Abstract: