Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
share
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 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/√(m)) for any c<3log(2)/π^2≈ 0.21. As a result the median of the distribution of these scrambled nets has an error that is O(n^-clog(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→∞. We include results for finite precision estimates and some non-asymptotic comparisons to taking the mean of 2r-1 independent draws.
READ FULL TEXT