Robust high-dimensional integration using medians of coarsely scrambled Sobol' sequences

Abstract

We study the numerical approximation of high-dimensional integrals using randomized quasi-Monte Carlo (RQMC) methods, with a focus on scrambled Sobol' sequences. While asymptotically faster than Monte Carlo, classical RQMC suffers from error bounds that grow exponentially in the dimension s, and its root mean squared error (RMSE) convergence rate is generally no better than O(N^−3/2). To overcome these limitations, we combine two recent developments: Suzuki's coarse scrambling and the median trick. Coarse scrambling randomizes Sobol' sequences according to their generating base polynomials and significantly reduces the maximal gain coefficient. By appropriately choosing the base polynomials, we show that the coefficient can be made uniformly bounded in s, yielding an O(N^−1/2) RMSE for L² integrands with a dimension-independent constant. The median trick then enables near-optimal convergence for function classes beyond L²: for L^p integrands with p∈(1,2), the median of independent coarsely scrambled estimates achieves an error of O(N^−1+1/p) with high probability; for integrands in the Haar wavelet space ℋ_wav,α,s,p,q with α_p:=α−(1/p−1/2)₊>0, we prove a high-probability error bound of O(N^{−α_p−1/2+ε}) for any ε>0; the bound improves to O(N^{−r−α_p−1/2+ε}) when the integrand has dominating mixed derivatives of order r≥1 that belong to ℋ_wav,α,s,p,q. The latter two bounds are uniform in s under suitable conditions on the ANOVA components of the integrands. Numerical experiments confirm the predicted convergence rates and demonstrate the robustness of the proposed approach.

The Coarse Novikov Conjecture for Finite Products of Fibred Coarsely Embeddable Spaces
Liang Guo, Zheng Luo, Qin Wang
arXiv22 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
n-Scrambled Cantor sets
B. Miller
arXiv24 Sep 2026PreprintCC BY 4.0Full textDynamical systems Logic & foundationsarXiv
Recurrent two-dimensional sequences over three and four letters simulating von Neumann constructions of finite ordinals
Xiaofang Jiang, Mihai Prunescu, Bogdan Dumitru
arXiv1 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
On the Tightness and Computational Tractability of Higher-Dimensional Confidence Sequences
Fabian Denoodt, Sibylle Hess, Joaquin Vanschoren +1
arXiv8 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
A continuum of coarse medians for all mapping class groups and right-angled groups
Giorgio Mangioni
arXiv6 Oct 2026PreprintCC BY-SA 4.0Full textAlgebra & number theory Geometry & topologyarXiv

Cite

BibTeX RIS

BibTeX

@misc{ye2026robust,
  title = {{Robust high-dimensional integration using medians of coarsely scrambled Sobol' sequences}},
  author = {Ziyang Ye and Chaokun Zhu and Zexin Pan},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.05979},
  eprint = {2609.05979},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.05979},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Robust high-dimensional integration using medians of coarsely scrambled Sobol' sequences
AU  - Ziyang Ye
AU  - Chaokun Zhu
AU  - Zexin Pan
PY  - 2026
DA  - 2026/09/05
PB  - arXiv
DO  - 10.48550/arxiv.2609.05979
UR  - https://arxiv.org/abs/2609.05979
AB  - We study the numerical approximation of high-dimensional integrals using randomized quasi-Monte Carlo (RQMC) methods, with a focus on scrambled Sobol' sequences. While asymptotically faster than Monte Carlo, classical RQMC suffers from error bounds that grow exponentially in the dimension s, and its root mean squared error (RMSE) convergence rate is generally no better than O(N^−3/2). To overcome these limitations, we combine two recent developments: Suzuki's coarse scrambling and the median trick. Coarse scrambling randomizes Sobol' sequences according to their generating base polynomials and significantly reduces the maximal gain coefficient. By appropriately choosing the base polynomials, we show that the coefficient can be made uniformly bounded in s, yielding an O(N^−1/2) RMSE for L^2 integrands with a dimension-independent constant. The median trick then enables near-optimal convergence for function classes beyond L^2: for L^p integrands with p∈(1,2), the median of independent coarsely scrambled estimates achieves an error of O(N^−1+1/p) with high probability; for integrands in the Haar wavelet space ℋ_wav,α,s,p,q with α_p:=α−(1/p−1/2)_+>0, we prove a high-probability error bound of O(N^−α_p−1/2+ε) for any ε>0; the bound improves to O(N^−r−α_p−1/2+ε) when the integrand has dominating mixed derivatives of order r≥1 that belong to ℋ_wav,α,s,p,q. The latter two bounds are uniform in s under suitable conditions on the ANOVA components of the integrands. Numerical experiments confirm the predicted convergence rates and demonstrate the robustness of the proposed approach.
ER  -

Abstract

Related

Cite