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

Technical Summary: Dimension-independent convergence rates of randomized nets using median-of-means

Problem Statement
High-dimensional integration is a fundamental challenge in computational finance, physics, and other fields. While Quasi-Monte Carlo (QMC) methods offer faster convergence than standard Monte Carlo (MC) by utilizing low-discrepancy point sets, they face limitations in high dimensions. Specifically, traditional randomized QMC (RQMC) methods based on averaging independent replicates of linearly scrambled digital nets are susceptible to outliers. Even when the integrand satisfies strong smoothness assumptions, these outliers can prevent the estimator from attaining faster convergence rates. Furthermore, existing tractability analyses often rely on worst-case error criteria over unit balls in function spaces, which may not reflect the performance on specific, fixed integrands. There is a need for a method that achieves dimension-independent convergence (strong tractability) under weaker assumptions and provides probabilistic error guarantees tailored to specific integrands.

Methodology
The paper proposes and analyzes a median-of-means approach applied to linearly scrambled base-2 digital nets. The methodology proceeds as follows:

1. Estimator Construction: Instead of averaging $2r-1$ independent RQMC replicates, the estimator $\hat{\mu}^{(r)}_\infty$ takes the sample median. This "median trick" is designed to mitigate the impact of outliers inherent in the randomization process.
2. Randomization Schemes: The analysis covers two primary randomization schemes:
   • Completely Random Design (CRD): All entries of the generating matrices are drawn independently from Bernoulli(0.5). This simplifies theoretical analysis.
   • Random Linear Scrambling (RLS): A computationally efficient method where generating matrices are multiplied by random lower-triangular matrices. This preserves the structure of digital nets while introducing controlled randomness.
3. Theoretical Framework:
   • ANOVA Decomposition: The integrand $f$ is decomposed into ANOVA components $f_u$. The variation of these components is quantified using fractional Vitali variation, a generalization of Sobolev norms that accommodates discontinuities.
   • Relative Variation ($\gamma_u$): A key metric, $\gamma_u$, is defined as the ratio of the variation of a specific ANOVA component to the global variation norm. This captures the concept of effective dimensionality, where high-dimensional integrands concentrate variation in low-order interactions.
   • Probabilistic Error Bounds: The authors utilize the properties of the median to derive probabilistic error bounds. By selecting a set of Walsh coefficients $K$ based on the decay of the integrand's smoothness, they bound the probability that the median estimator deviates significantly from the true integral.

Key Contributions

1. Dimension-Independent Convergence (Strong Tractability): The paper proves that the median estimator achieves convergence rates that are independent of the dimension $s$, provided the relative variation $\gamma_u$ decays sufficiently fast. This holds under tractability conditions that are strictly weaker than those required for worst-case error bounds in previous literature (e.g., [12]).
2. Integrand-Specific Probabilistic Guarantees: Unlike worst-case analyses over function spaces, this work establishes that for a fixed integrand, the median estimator achieves near-optimal convergence rates with high probability. The error bound depends on the specific decay of the integrand's Walsh coefficients and its effective dimensionality.
3. Robustness to Smoothness Misspecification: The method does not require a priori knowledge of the integrand's smoothness parameters ($\alpha$ and $\lambda$). The median estimator automatically adapts to the effective smoothness of the function, matching theoretical lower bounds up to an arbitrarily small $\eta > 0$.
4. Generalization of Randomization: The theoretical results are extended from the simplified completely random design to the more practical random linear scrambling, demonstrating that dimension-independent convergence is achievable with standard RQMC constructions.

Results

• Convergence Rates: For an integrand with continuous mixed partial derivatives of order $k$ (or more generally, satisfying $\|f\|_{\alpha, \lambda} < \infty$), the median estimator achieves a convergence rate of nearly $O(n^{-k-1/2})$ (or $O(N^{-(\alpha+\lambda+1/2)})$ where $N$ is the total number of function evaluations). This is nearly optimal and significantly faster than the $O(n^{-1/2})$ rate of standard MC.
• Tractability Conditions: The paper derives specific conditions on the decay of $\gamma_u$ (e.g., $\gamma_u \leq \prod_{j \in u} \gamma_j$ with $\sum \gamma_j^{1/(\alpha+\lambda+1/2)} < \infty$) under which the error bounds remain independent of the dimension $s$.
• Numerical Validation: Simulations on high-dimensional integrands ($s=10, 100, 1000$) confirm the theoretical predictions. The median estimator consistently outperforms the standard RQMC average (STD), particularly in the presence of outliers. The empirical convergence rates align with the theoretical bounds, showing dimension-independent behavior as $s$ increases.

Significance and Claims
The paper claims that the median-of-means RQMC method offers a practical and robust alternative for high-dimensional integration. Its primary significance lies in:

• Eliminating the need for parameter tuning: The method does not require specifying smoothness parameters or pre-optimizing digital nets, yet it automatically achieves near-optimal rates.
• Overcoming the "outlier" barrier: By using the median, the method avoids the convergence degradation caused by outliers that plagues averaging-based RQMC.
• Strong Tractability: It establishes that dimension-independent convergence is achievable under realistic assumptions about the effective dimensionality of integrands, bridging the gap between theoretical complexity and practical performance.

The authors note that while other algorithms (such as higher-order digital nets or Frolov lattice rules) match lower complexity bounds in specific spaces, the median estimator is distinct in its immunity to parameter misspecification and its straightforward implementation. The work also suggests potential extensions to $L^2$-approximation and non-smooth integrands, though these are identified as directions for future research rather than current results.