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

Abstract: We study approximate integration of a function

f

over

[0, 1]^{s}

based on taking the median of

2 r - 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^{- c m^{2} / s}

times a quantity depending on

f

is

O (1 / s q r t m)

for any

c < 3 l o g (2) / p i^{2} a p p r o x 0.21

. As a result the median of the distribution of these scrambled nets has an error that is

O (n^{- c l o g (n) / s})

for

n = 2^{m}

function evaluations. The sample median of

2 r - 1

independent draws attains this rate too, so long as

r / m^{2}

is bounded away from zero as

m o i n f t y

. We include results for finite precision estimates and some non-asymptotic comparisons to taking the mean of

2 r - 1

independent draws.

This page was built for publication: Super-polynomial accuracy of multidimensional randomized nets using the median-of-means