Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
Mathematics of Computation · 18.04.2024 · 93 (349) · 2265-2289
DOI: 10.1090/mcom/3880 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Computation, online erschienen am 18.04.2024. Verfasst von Zexin Pan und 1 weiteren Autor:innen. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 38 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
We study approximate integration of a function f f over [ 0 , 1 ] s [0,1]^s based on taking the median of 2 r − 1 2r-1 integral estimates derived from independently randomized ( t , m , s ) (t,m,s) -nets in base 2 2 . The nets are randomized by Matousek’s random linear scramble with a random digital shift. If f f is analytic over [ 0 , 1 ] s [0,1]^s , then the probability that any one randomized net’s estimate has an error larger than 2 − c m 2 / s 2^{-cm^2/s} times a quantity depending on f f is O ( 1 / m ) O(1/\sqrt {m}) for any c > 3 log ( 2 ) / π 2 ≈ 0.21 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 ) O(n^{-c\log (n)/s}) for n = 2 m n=2^m function evaluations. The sample median of 2 r − 1 2r-1 independent draws attains this rate too, so long as r / m 2 r/m^2 is bounded away from zero as m → ∞ m\to \infty . We include results for finite precision estimates and some nonasymptotic comparisons to taking the mean of 2 r − 1 2r-1 independent draws.
Förderung
- National Science Foundation
Zitieren
APA
Pan, Z., & Owen, A. (2024). Super-polynomial accuracy of multidimensional randomized nets using the median-of-means. Mathematics of Computation, 93(349), 2265-2289. https://doi.org/10.1090/mcom/3880
Vancouver
Pan Z, Owen A. Super-polynomial accuracy of multidimensional randomized nets using the median-of-means. Mathematics of Computation. 2024;93(349):2265-2289. doi:10.1090/mcom/3880
BibTeX
@article{Pan2024,
author = {Pan, Zexin and Owen, Art},
title = {Super-polynomial accuracy of multidimensional randomized nets using the median-of-means},
journal = {Mathematics of Computation},
year = {2024},
volume = {93},
number = {349},
pages = {2265--2289},
doi = {10.1090/mcom/3880}
}
EUVIMED