Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
HTML articles powered by AMS MathViewer
- by Zexin Pan and Art B. Owen;
- Math. Comp. 93 (2024), 2265-2289
- DOI: https://doi.org/10.1090/mcom/3880
- Published electronically: April 18, 2024
- HTML | PDF | Request permission
Abstract:
We study approximate integration of a function $f$ over $[0,1]^s$ based on taking the median of $2r-1$ integral estimates derived from independently randomized $(t,m,s)$-nets in base $2$. The nets are randomized by Matousek’s random linear scramble with a random digital shift. If $f$ is analytic over $[0,1]^s$, then the probability that any one randomized net’s estimate has an error larger than $2^{-cm^2/s}$ times a quantity depending on $f$ is $O(1/\sqrt {m})$ for any $c<3\log (2)/\pi ^2\approx 0.21$. As a result, the median of the distribution of these scrambled nets has an error that is $O(n^{-c\log (n)/s})$ for $n=2^m$ function evaluations. The sample median of $2r-1$ independent draws attains this rate too, so long as $r/m^2$ is bounded away from zero as $m\to \infty$. We include results for finite precision estimates and some nonasymptotic comparisons to taking the mean of $2r-1$ independent draws.References
- George E. Andrews, The theory of partitions, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1998. Reprint of the 1976 original. MR 1634067
- Mohammadreza Bidar, Partition of an integer into distinct bounded parts, identities and bounds, Integers 12 (2012), no. 3, 445–457. MR 2955525, DOI 10.1515/integers-2011-0115
- R. E. Caflisch, W. Morokoff, and A. B. Owen, Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. of Comput. Finance 1 (1997), 27–46.
- Sou-Cheng T. Choi, Fred J. Hickernell, Rathinavel Jagadeeswaran, Michael J. McCourt, and Aleksei G. Sorokin, Quasi-Monte Carlo software, Monte Carlo and quasi-Monte Carlo methods, Springer Proc. Math. Stat., vol. 387, Springer, Cham, [2022] ©2022, pp. 23–47. MR 4461047, DOI 10.1007/978-3-030-98319-2_{2}
- Philip J. Davis and Philip Rabinowitz, Methods of numerical integration, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1984. MR 760629
- Luc Devroye, Matthieu Lerasle, Gabor Lugosi, and Roberto I. Oliveira, Sub-Gaussian mean estimators, Ann. Statist. 44 (2016), no. 6, 2695–2725. MR 3576558, DOI 10.1214/16-AOS1440
- 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 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
- Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235, DOI 10.1017/CBO9780511801655
- E. Gobet, M. Lerasle, and D. Métivier, Mean estimation for randomized quasi Monte Carlo method, Technical Report, hal-03631879, 2022.
- Takashi Goda and Pierre L’Ecuyer, Construction-free median quasi–Monte Carlo rules for function spaces with unspecified smoothness and general weights, SIAM J. Sci. Comput. 44 (2022), no. 4, A2765–A2788. MR 4474386, DOI 10.1137/22M1473625
- Boris L. Granovsky, Dudley Stark, and Michael Erlihson, Meinardus’ theorem on weighted partitions: extensions and a probabilistic proof, Adv. in Appl. Math. 41 (2008), no. 3, 307–328. MR 2449593, DOI 10.1016/j.aam.2007.11.001
- Zhijian He and Art B. Owen, Extensible grids: uniform sampling on a space filling curve, J. R. Stat. Soc. Ser. B. Stat. Methodol. 78 (2016), no. 4, 917–931. MR 3534356, DOI 10.1111/rssb.12132
- F. J. Hickernell, Koksma-Hlawka inequality, Wiley StatsRef: Statistics Reference Online, 2014.
- Fred J. Hickernell and Rong-Xian Yue, The mean square discrepancy of scrambled $(t,s)$-sequences, SIAM J. Numer. Anal. 38 (2000), no. 4, 1089–1112. MR 1786132, DOI 10.1137/S0036142999358019
- Julian Hofstadler and Daniel Rudolf, Consistency of randomized integration methods, J. Complexity 76 (2023), Paper No. 101740, 10. MR 4557311, DOI 10.1016/j.jco.2023.101740
- Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theoret. Comput. Sci. 43 (1986), no. 2-3, 169–188. MR 855970, DOI 10.1016/0304-3975(86)90174-X
- 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
- Robert J. Kunsch, Erich Novak, and Daniel Rudolf, Solvable integration problems and optimal sample size selection, J. Complexity 53 (2019), 40–67. MR 3953086, DOI 10.1016/j.jco.2018.10.007
- Guillaume Lecué and Matthieu Lerasle, Robust machine learning by median-of-means: theory and practice, Ann. Statist. 48 (2020), no. 2, 906–931. MR 4102681, DOI 10.1214/19-AOS1828
- Wei-Liem Loh, On the asymptotic distribution of scrambled net quadrature, Ann. Statist. 31 (2003), no. 4, 1282–1324. MR 2001651, DOI 10.1214/aos/1059655914
- 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
- Günter Meinardus, Asymptotische Aussagen über Partitionen, Math. Z. 59 (1954), 388–398 (German). MR 62781, DOI 10.1007/BF01180268
- William J. Morokoff and Russel E. Caflisch, Quasi-Monte Carlo integration, J. Comput. Phys. 122 (1995), no. 2, 218–230. MR 1365433, DOI 10.1006/jcph.1995.1209
- M. K. Nakayama and B. Tuffin, Sufficient conditions for a central limit theorem to assess the error of randomized quasi-Monte Carlo methods, 2021 Winter Simulation Conference (WSC), IEEE, 2021, pp. 1–12.
- Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
- 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
- Art B. Owen, The dimension distribution and quadrature test functions, Statist. Sinica 13 (2003), no. 1, 1–17. MR 1963917
- Art Owen, Effective dimension of some weighted pre-Sobolev spaces with dominating mixed partial derivatives, SIAM J. Numer. Anal. 57 (2019), no. 2, 547–562. MR 3922913, DOI 10.1137/17M1158975
- Zexin Pan and Art B. Owen, The nonzero gain coefficients of Sobol’s sequences are always powers of two, J. Complexity 75 (2023), Paper No. 101700, 16. MR 4536728, DOI 10.1016/j.jco.2022.101700
- 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
- I. H. Sloan and H. Wozniakowski. When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?, Journal of Complexity, 14 (1998), no. 1, 1–33.
- 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
- S. Surjanovic and D. Bingham, Virtual library of simulation experiments: test functions and datasets, 2013, https://www.sfu.ca/~ssurjano/.
- Takehito Yoshiki, Bounds on Walsh coefficients by dyadic difference and a new Koksma-Hlawka type inequality for quasi-Monte Carlo integration, Hiroshima Math. J. 47 (2017), no. 2, 155–179. MR 3679888, DOI 10.32917/hmj/1499392824
- Rong-Xian Yue and Fred J. Hickernell, The discrepancy and gain coefficients of scrambled digital nets, J. Complexity 18 (2002), no. 1, 135–151. MR 1895080, DOI 10.1006/jcom.2001.0630
Bibliographic Information
- Zexin Pan
- Affiliation: Department of Statistics, Stanford University, Sequoia Hall, 390 Jane Stanford Way, Stanford, CA 94305, USA
- MR Author ID: 1340663
- ORCID: 0009-0003-1902-4061
- Art B. Owen
- Affiliation: Department of Statistics, Stanford University, Sequoia Hall, 390 Jane Stanford Way, Stanford, CA 94305, USA
- MR Author ID: 134875
- Received by editor(s): September 8, 2022
- Received by editor(s) in revised form: April 21, 2023, and June 8, 2023
- Published electronically: April 18, 2024
- Additional Notes: This work was supported by the US National Science Foundation under grants IIS-1837931 and DMS-2152780 and a Stanford Graduate Fellowship in Science & Engineering
- © Copyright 2024 American Mathematical Society
- Journal: Math. Comp. 93 (2024), 2265-2289
- MSC (2020): Primary 65D30; Secondary 05A15
- DOI: https://doi.org/10.1090/mcom/3880
- MathSciNet review: 4759375