EUVIMEDEUVIMED entdecken
Crossref

Super-polynomial accuracy of multidimensional randomized nets using the median-of-means

Zexin Pan, Art Owen

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →