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

Abstract:

Let $f$ be analytic on $[0,1]$ with $|f^{(k)}(1/2)|\leqslant A\alpha ^kk!$ for some constants $A$ and $\alpha <2$ and all $k\geqslant 1$. We show that the median estimate of $\mu =\int _0^1f(x)\,\mathrm {d} x$ under random linear scrambling with $n=2^m$ points converges at the rate $O(n^{-c\log (n)})$ for any $c< 3\log (2)/\pi ^2\approx 0.21$. We also get a super-polynomial convergence rate for the sample median of $2k-1$ random linearly scrambled estimates, when $k/m$ is bounded away from zero. When $f$ has a $p$’th derivative that satisfies a $\lambda$-Hölder condition then the median of means has error $O( n^{-(p+\lambda )+\epsilon })$ for any $\epsilon >0$, if $k\to \infty$ as $m\to \infty$. The proof techniques use methods from analytic combinatorics that have not previously been applied to quasi-Monte Carlo methods, most notably an asymptotic expression from Hardy and Ramanujan on the number of partitions of a natural number.