Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate
HTML articles powered by AMS MathViewer
- by Josef Dick, Takashi Goda and Kosuke Suzuki HTML | PDF
- Math. Comp. 91 (2022), 2771-2801 Request permission
Abstract:
We study a randomized quadrature algorithm to approximate the integral of periodic functions defined over the high-dimensional unit cube. Recent work by Kritzer, Kuo, Nuyens and Ullrich [J. Approx. Theory 240 (2019), pp. 96–113] shows that rank-1 lattice rules with a randomly chosen number of points and good generating vector achieve almost the optimal order of the randomized error in weighted Korobov spaces, and moreover, that the error is bounded independently of the dimension if the weight parameters, $\gamma _j$, satisfy the summability condition $\sum _{j=1}^{\infty }\gamma _j^{1/\alpha }<\infty$, where $\alpha$ is a smoothness parameter. The argument is based on the existence result that at least half of the possible generating vectors yield almost the optimal order of the worst-case error in the same function spaces.
In this paper we provide a component-by-component construction algorithm of such randomized rank-1 lattice rules, without any need to check whether the constructed generating vectors satisfy a desired worst-case error bound. Similarly to the above-mentioned work, we prove that our algorithm achieves almost the optimal order of the randomized error and that the error bound is independent of the dimension if the same condition $\sum _{j=1}^{\infty }\gamma _j^{1/\alpha }<\infty$ holds. We also provide analogous results for tent-transformed lattice rules for weighted half-period cosine spaces and for polynomial lattice rules in weighted Walsh spaces, respectively.
References
- N. S. Bahvalov, Estimates in the mean of the remainder term of quadratic formulas, Ž. Vyčisl. Mat i Mat. Fiz. 1 (1961), 64–77 (Russian). MR 136068
- Ronald Cools, Frances Y. Kuo, Dirk Nuyens, and Gowri Suryanarayana, Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions, J. Complexity 36 (2016), 166–181. MR 3530643, DOI 10.1016/j.jco.2016.05.004
- Josef Dick, Aicke Hinrichs, and Friedrich Pillichshammer, Proof techniques in quasi–Monte Carlo theory, J. Complexity 31 (2015), no. 3, 327–371. MR 3325678, DOI 10.1016/j.jco.2014.09.003
- J. Dick, F. Y. Kuo, F. Pillichshammer, and I. H. Sloan, Construction algorithms for polynomial lattice rules for multivariate integration, Math. Comp. 74 (2005), no. 252, 1895–1921. MR 2164102, DOI 10.1090/S0025-5718-05-01742-4
- Josef Dick, Frances Y. Kuo, and Ian H. Sloan, High-dimensional integration: the quasi-Monte Carlo way, Acta Numer. 22 (2013), 133–288. MR 3038697, DOI 10.1017/S0962492913000044
- Josef Dick, Dirk Nuyens, and Friedrich Pillichshammer, Lattice rules for nonperiodic smooth integrands, Numer. Math. 126 (2014), no. 2, 259–291. MR 3150223, DOI 10.1007/s00211-013-0566-0
- Josef Dick and Friedrich Pillichshammer, Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces, J. Complexity 21 (2005), no. 2, 149–195. MR 2123222, DOI 10.1016/j.jco.2004.07.003
- 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
- Adrian Ebert, Peter Kritzer, Dirk Nuyens, and Onyekachi Osisiogu, Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness, J. Complexity 66 (2021), Paper No. 101555, 37. MR 4292361, DOI 10.1016/j.jco.2021.101555
- Takashi Goda and Josef Dick, Construction of interlaced scrambled polynomial lattice rules of arbitrary high order, Found. Comput. Math. 15 (2015), no. 5, 1245–1278. MR 3394710, DOI 10.1007/s10208-014-9226-8
- Takashi Goda, Kosuke Suzuki, and Takehito Yoshiki, Lattice rules in non-periodic subspaces of Sobolev spaces, Numer. Math. 141 (2019), no. 2, 399–427. MR 3905431, DOI 10.1007/s00211-018-1003-1
- I. S. Gradshteyn and I. M. Ryzhik, Table of Integrals, Series, and Products, Academic Press, 2007.
- Fred J. Hickernell, Lattice rules: how well do they measure up?, Random and quasi-random point sets, Lect. Notes Stat., vol. 138, Springer, New York, 1998, pp. 109–166. MR 1662841, DOI 10.1007/978-1-4612-1702-2_{3}
- Fred J. Hickernell, Obtaining $O(N^{-2+\epsilon })$ convergence for lattice quadrature rules, Monte Carlo and quasi-Monte Carlo methods, 2000 (Hong Kong), Springer, Berlin, 2002, pp. 274–289. MR 1958860
- Peter Kritzer, Frances Y. Kuo, Dirk Nuyens, and Mario Ullrich, Lattice rules with random $n$ achieve nearly the optimal $\mathcal O(n^{-\alpha -1/2})$ error independently of the dimension, J. Approx. Theory 240 (2019), 96–113. MR 3926053, DOI 10.1016/j.jat.2018.09.011
- F. Y. Kuo, Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, J. Complexity 19 (2003), no. 3, 301–320. Numerical integration and its complexity (Oberwolfach, 2001). MR 1984116, DOI 10.1016/S0885-064X(03)00006-2
- Christiane Lemieux and Pierre L’Ecuyer, Randomized polynomial lattice rules for multivariate integration and simulation, SIAM J. Sci. Comput. 24 (2003), no. 5, 1768–1789. MR 1978160, DOI 10.1137/S1064827501393782
- Gunther Leobacher and Friedrich Pillichshammer, Introduction to quasi-Monte Carlo integration and applications, Compact Textbooks in Mathematics, Birkhäuser/Springer, Cham, 2014. MR 3289176, DOI 10.1007/978-3-319-03425-6
- 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, Low-discrepancy point sets obtained by digital constructions over finite fields, Czechoslovak Math. J. 42(117) (1992), no. 1, 143–166. MR 1152177, DOI 10.21136/CMJ.1992.128322
- Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255, DOI 10.1007/BFb0079792
- Dirk Nuyens and Ronald Cools, Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces, Math. Comp. 75 (2006), no. 254, 903–920. MR 2196999, DOI 10.1090/S0025-5718-06-01785-6
- Dirk Nuyens and Ronald Cools, Fast component-by-component construction, a reprise for different kernels, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 373–387. MR 2208719, DOI 10.1007/3-540-31186-6_{2}2
- 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
- Vern I. Paulsen and Mrinal Raghupathi, An introduction to the theory of reproducing kernel Hilbert spaces, Cambridge Studies in Advanced Mathematics, vol. 152, Cambridge University Press, Cambridge, 2016. MR 3526117, DOI 10.1017/CBO9781316219232
- Friedrich Pillichshammer, Polynomial lattice point sets, Monte Carlo and quasi-Monte Carlo methods 2010, Springer Proc. Math. Stat., vol. 23, Springer, Heidelberg, 2012, pp. 189–210. MR 3173834, DOI 10.1007/978-3-642-27440-4_{8}
- Paul Pollack, Irreducible polynomials with several prescribed coefficients, Finite Fields Appl. 22 (2013), 70–78. MR 3044094, DOI 10.1016/j.ffa.2013.03.001
- J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
- I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994. MR 1442955
- I. H. Sloan, F. Y. Kuo, and S. Joe, Constructing randomly shifted lattice rules in weighted Sobolev spaces, SIAM J. Numer. Anal. 40 (2002), no. 5, 1650–1665. MR 1950616, DOI 10.1137/S0036142901393942
- I. H. Sloan, F. Y. Kuo, and S. Joe, On the step-by-step construction of quasi-Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces, Math. Comp. 71 (2002), no. 240, 1609–1640. MR 1933047, DOI 10.1090/S0025-5718-02-01420-5
- I. H. Sloan and A. V. Reztsov, Component-by-component construction of good lattice rules, Math. Comp. 71 (2002), no. 237, 263–273. MR 1862999, DOI 10.1090/S0025-5718-01-01342-4
- Ian H. Sloan and Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1–33. MR 1617765, DOI 10.1006/jcom.1997.0463
- Mario Ullrich, A Monte Carlo method for integration of multivariate smooth functions, SIAM J. Numer. Anal. 55 (2017), no. 3, 1188–1200. MR 3648970, DOI 10.1137/16M1075557
- Rong-Xian Yue and Fred J. Hickernell, Strong tractability of integration using scrambled Niederreiter points, Math. Comp. 74 (2005), no. 252, 1871–1893. MR 2164101, DOI 10.1090/S0025-5718-05-01755-2
Additional Information
- Josef Dick
- Affiliation: School of Mathematics and Statistics, UNSW Sydney, Sydney, NSW, Australia
- MR Author ID: 735535
- ORCID: 0000-0003-0142-6022
- Email: josef.dick@unsw.edu.au
- Takashi Goda
- Affiliation: School of Engineering, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
- MR Author ID: 936012
- ORCID: 0000-0001-6055-8055
- Email: goda@frcer.t.u-tokyo.ac.jp
- Kosuke Suzuki
- Affiliation: Graduate School of Advanced Science and Engineering, Hiroshima University, 1-3-1 Kagamiyama, Higashi-Hiroshima City, Hiroshima 739-8526, Japan
- MR Author ID: 1057946
- Email: kosuke-suzuki@hiroshima-u.ac.jp
- Received by editor(s): September 23, 2021
- Received by editor(s) in revised form: March 21, 2022, and May 12, 2022
- Published electronically: August 5, 2022
- Additional Notes: The first author was partly supported by the Australian Research Council Discovery Project DP190101197. The second author was supported by JSPS KAKENHI Grant Number 20K03744. The third author was supported by JSPS KAKENHI Grant Number 20K14326.
- © Copyright 2022 American Mathematical Society
- Journal: Math. Comp. 91 (2022), 2771-2801
- MSC (2020): Primary 11K45, 65C05, 65D30, 65D32
- DOI: https://doi.org/10.1090/mcom/3769
- MathSciNet review: 4473103