Metraipolis › archive › dc_8190ada6aaa6
Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + \varepsilon)n$ Samples Suffice — arXiv:2609.10921
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.10921
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T06:39:29.149Z
- SHA-256 of the archived text
c0b024bd258b137d25d7bb9a13b365b425c568b984441d5c7007a3e2091b2dab- Stable URL of this page
https://metraipolis.com/documento/dc_8190ada6aaa6
How to cite
Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + \varepsilon)n$ Samples Suffice — arXiv:2609.10921 — arXiv (en), https://arxiv.org/abs/2609.10921 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8190ada6aaa6 (Metraipolis archive dc_8190ada6aaa6, sha256 c0b024bd258b137d25d7bb9a13b365b425c568b984441d5c7007a3e2091b2dab)
BibTeX
@misc{dc8190ada6aaa6,
title = {Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + varepsilon)n$ Samples Suffice — arXiv:2609.10921},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.10921},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8190ada6aaa6; sha256 c0b024bd258b137d25d7bb9a13b365b425c568b984441d5c7007a3e2091b2dab},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.10921. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Numerical integration studies how well one can estimate the integral of a function $f$ over $[0,1)^d$ using $n$ sample points. The two classical methods, Monte Carlo (MC) and quasi-Monte Carlo (QMC), have complementary strengths and weaknesses, and a fundamental question is to design an approach that combines the benefits of both. Recently, building on the transference principle in discrepancy theory, Bansal and Jiang~\cite{BJ25a} gave a randomized QMC method that bridges MC and QMC guarantees using only i.i.d.\ samples. Their method also goes beyond the classical Koksma--Hlawka inequality: it achieves integration error $\widetilde{O}_d(\sigma_{\mathsf{SO}}(f)/n)$, where the smoothed-out variation $\sigma_{\mathsf{SO}}(f)$ can be substantially smaller than the Hardy--Krause variation that governs the classical bound. However, their algorithm requires $n^2$ i.i.d.\ samples as input, and this quadratic blowup is inherent to any method based on the transference principle. In this work, we bypass the quadratic blowup: for any constant $\varepsilon > 0$, we show that $(1+\varepsilon)n$ i.i.d.\ samples suffice to both obtain the beyond-Hardy--Krause guarantee of~\cite{BJ25a}, resolving an open problem posed there, and to produce low-discrepancy point sequences. Our algorithms are variants of the online Haar-thinning method of Dwivedi, Feldheim, Gurel-Gurevich, and Ramdas~\cite{DFG+19}.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-11 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.10921 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T06:16:40.971Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).