Automatic optimal-rate convergence of randomized nets using median-of-means

2024/11/03 by Zexin Pan, Pan, Zexin · 4 citations
Computer Science · Decision Sciences · Engineering · #Advanced Control Systems Optimization #FOS: Mathematics #Neural Networks and Applications #Numerical Analysis (math.NA) #Simulation Techniques and Applications

paper · pdf · doi:10.48550/arxiv.2411.01397

openalex publication_date 2024/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the sample median of independently generated quasi-Monte Carlo estimators based on randomized digital nets and prove it approximates the target integral value at almost the optimal convergence rate for various function spaces. In contrast to previous methods, the algorithm does not require a priori knowledge of underlying function spaces or even an input of pre-designed (t,m,s)-digital nets, and is therefore easier to implement. This study provides further evidence that quasi-Monte Carlo estimators are heavy-tailed when applied to smooth integrands and taking the median can significantly improve the error by filtering out the outliers.

Cited by

• Coarse scrambling for Sobol' and Niederreiter sequences
• Separation properties of scrambled digital nets and related random point sets
• The median trick does not help for fully nested scrambling
• Dimension-independent convergence rates of randomized nets using median-of-means

Related

• Dimension-independent convergence rates of randomized nets using median-of-means
• Quasi-Monte Carlo confidence intervals using quantiles of randomized nets
• The median trick does not help for fully nested scrambling
• Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
• Super-polynomial accuracy of one dimensional randomized nets using the median-of-means