Super-polynomial accuracy of one dimensional randomized nets using the median-of-means

2021/11/24 by Zexin Pan, Art B. Owen, Pan, Zexin +1 · 5 citations
Computer Science · Mathematics · #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Approximation and Integration #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2111.12676

openalex publication_date 2021/11/24 · openalex created_date 2021/12/06 · openalex updated_date 2026/07/28

Abstract

Let f be analytic on [0,1] with |f^(k)(1/2)|≤ Aα^kk! for some constant A and α<2. We show that the median estimate of μ=∫₀¹f(x) dx under random linear scrambling with n=2^m points converges at the rate O(n^-clog(n)) for any c< 3log(2)/π²≈ 0.21. We also get a super-polynomial convergence rate for the sample median of 2k-1 random linearly scrambled estimates, when k=Ω(m). When f has a p'th derivative that satisfies a λ-Hölder condition then the median-of-means has error O( n^-(p+λ)+ε) for any ε>0, if k→∞ as m→∞.

Cited by

• Coarse scrambling for Sobol' and Niederreiter sequences
• Better bootstrap t confidence intervals for the mean
• The median trick does not help for fully nested scrambling
• Dimension-independent convergence rates of randomized nets using median-of-means
• Affine matrix scrambling achieves smoothness-dependent convergence rates

Related

• Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
• Dimension-independent convergence rates of randomized nets using median-of-means
• Automatic optimal-rate convergence of randomized nets using median-of-means
• Affine matrix scrambling achieves smoothness-dependent convergence rates
• Gain coefficients for scrambled Halton points