论文标题
使用中位数的多维随机网的超级顺序准确性
Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
论文作者
论文摘要
我们研究了$ f $超过$ [0,1]^s $的近似集成，因为它的中位数为$ 2R-1 $ $的积分估计，这些估计来自于独立的随机$（t，m，s）$ - 基本$ 2 $的网络。网络由Matousek的随机线性争夺随机分配，并具有数字偏移。如果$ f $超过$ [0,1]^s $，那么任何一个随机净估计的估计值大于$ 2^{ - cm^2/s} $ times的可能性，其数量取决于$ f $是$ o（1/\ sqrt {m}）$，对于任何$ c <3 \ 3 \ 3 \ log（2）/f log log（2）/fog（2）/f of。结果，对于$ n = 2^m $ function评估，这些炒网的分布的中位数为$ o（n^{ - c \ log（n）/s}）$。 $ 2R-1 $独立抽奖的样本中位数也达到了这一速率，只要$ r/m^2 $从零以$ m \至\ infty $限制。我们包括有限精度估计值的结果，以及对$ 2R-1 $独立抽奖的平均值进行一些非反应比较。
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/\sqrt{m})$ for any $c<3\log(2)/π^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 non-asymptotic comparisons to taking the mean of $2r-1$ independent draws.
