Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2024 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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

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
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2020): 65D30, 05A15
  • Retrieve articles in all journals with MSC (2020): 65D30, 05A15
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