Dimension-independent convergence rates of randomized nets using median-of-means

2025/05/20 by Zexin Pan, Pan, Zexin
Computer Science · Decision Sciences · Mathematics · #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Neural Networks and Applications #Numerical Analysis (math.NA) #Simulation Techniques and Applications #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2505.13815

openalex publication_date 2025/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Recent advances in quasi-Monte Carlo integration demonstrate that the median of linearly scrambled digital net estimators achieves near-optimal convergence rates for high-dimensional integrals without requiring a priori knowledge of the integrand's smoothness. Building on this framework, we prove that the median estimator attains dimension-independent convergence, a property known as strong tractability in complexity theory, under tractability conditions characterized by low effective dimensionality. Using a probabilistic, integrand-specific error criterion, our analysis establishes both faster and dimension-independent convergence under weaker assumptions than previously possible in the worst-case setting.

Citations

• Universal L₂-approximation using median lattice algorithms
• A median QMC method for unbounded integrands over \mathbb R^s in weighted unanchored Sobolev spaces
• Integrability of weak mixed first-order derivatives and convergence rates of scrambled digital nets
• L₂-approximation using median lattice algorithms
• A simple universal algorithm for high-dimensional integration
• Automatic optimal-rate convergence of randomized nets using median-of-means
• A Random Integration Algorithm for High-dimensional Function Spaces
• 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
• Optimal confidence for Monte Carlo integration of smooth functions
• Solvable Integration Problems and Optimal Sample Size Selection
• Application of quasi-Monte Carlo methods to elliptic PDEs with random\n diffusion coefficients - a survey of analysis and implementation
• A Universal Algorithm for Multivariate Integration
• Formulas for the Walsh coefficients of smooth functions and their application to bounds on the Walsh coefficients

Related

• Automatic optimal-rate convergence of randomized nets using median-of-means
• Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
• Quasi-Monte Carlo confidence intervals using quantiles of randomized nets
• Affine matrix scrambling achieves smoothness-dependent convergence rates
• Super-polynomial accuracy of one dimensional randomized nets using the median-of-means