A randomized lattice rule without component-by-component construction

Goda, Takashi

doi:10.1090/mcom/4051

A randomized lattice rule without component-by-component construction
HTML articles powered by AMS MathViewer

by Takashi Goda;

Math. Comp.

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

Published electronically: January 21, 2025

HTML | PDF | Request permission

Abstract:

We study the multivariate integration problem for periodic functions from the weighted Korobov space in the randomized setting. We introduce a new randomized rank-1 lattice rule with a randomly chosen number of points, which avoids the need for component-by-component construction in the search for good generating vectors while still achieving nearly the optimal rate of the randomized error. Our idea is to exploit the fact that at least half of the possible generating vectors yield nearly the optimal rate of the worst-case error in the deterministic setting. By randomly choosing generating vectors $r$ times and comparing their corresponding worst-case errors, one can find one generating vector with a desired worst-case error bound with a very high probability, and the (small) failure probability can be controlled by increasing $r$ logarithmically as a function of the number of points. Numerical experiments are conducted to support our theoretical findings.

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, On the convergence rate of the component-by-component construction of good lattice rules, J. Complexity 20 (2004), no. 4, 493–522. MR 2068155, DOI 10.1016/j.jco.2003.11.008
Josef Dick and Takashi Goda, Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm, J. Comput. Appl. Math. 382 (2021), Paper No. 113062, 16. MR 4114951, DOI 10.1016/j.cam.2020.113062
Josef Dick, Takashi Goda, and Kosuke Suzuki, Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate, Math. Comp. 91 (2022), no. 338, 2771–2801. MR 4473103, DOI 10.1090/mcom/3769
Josef Dick, Peter Kritzer, and Friedrich Pillichshammer, Lattice rules—numerical integration, approximation, and discrepancy, Springer Series in Computational Mathematics, vol. 58, Springer, Cham, [2022] ©2022. With an appendix by Adrian Ebert. MR 4472208, DOI 10.1007/978-3-031-09951-9
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, Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Good lattice rules in weighted Korobov spaces with general weights, Numer. Math. 103 (2006), no. 1, 63–97. MR 2207615, DOI 10.1007/s00211-005-0674-6
Takashi Goda, A note on concatenation of quasi-Monte Carlo and plain Monte Carlo rules in high dimensions, J. Complexity 72 (2022), Paper No. 101647, 12. MR 4438170, DOI 10.1016/j.jco.2022.101647
Takashi Goda, Yoshihito Kazashi, and Yuya Suzuki, Randomizing the trapezoidal rule gives the optimal RMSE rate in Gaussian Sobolev spaces, Math. Comp. 93 (2024), no. 348, 1655–1676. MR 4730245, DOI 10.1090/mcom/3910
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
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
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
Frances Y. Kuo, Dirk Nuyens, and Laurence Wilkes, Random-prime-fixed-vector randomised lattice-based algorithm for high-dimensional integration, J. Complexity 79 (2023), Paper No. 101785, 28. MR 4627735, DOI 10.1016/j.jco.2023.101785
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
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
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266, DOI 10.4171/026
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume II: Standard information for functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR 2676032, DOI 10.4171/084
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 Laurence Wilkes, A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with $0 < \alpha \leq 1/2$, Monte Carlo and quasi-Monte Carlo methods, Springer Proc. Math. Stat., vol. 460, Springer, Cham, [2024] ©2024, pp. 507–523. MR 4774937, DOI 10.1007/978-3-031-59762-6_{2}5
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, DOI 10.1093/oso/9780198534723.001.0001
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