Metraipolis › archive › dc_082fce380494
A Simpler Analysis of the Bansal-Jiang Quasi Monte-Carlo Algorithm via Haar Wavelets — arXiv:2608.27986
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.27986
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T11:52:23.904Z
- SHA-256 of the archived text
3f3aff336ea6860600d1586f4935dfc1737e7a4c184d398083712d4d841c3144- Stable URL of this page
https://metraipolis.com/documento/dc_082fce380494
How to cite
A Simpler Analysis of the Bansal-Jiang Quasi Monte-Carlo Algorithm via Haar Wavelets — arXiv:2608.27986 — arXiv (en), https://arxiv.org/abs/2608.27986 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_082fce380494 (Metraipolis archive dc_082fce380494, sha256 3f3aff336ea6860600d1586f4935dfc1737e7a4c184d398083712d4d841c3144)
BibTeX
@misc{dc082fce380494,
title = {A Simpler Analysis of the Bansal-Jiang Quasi Monte-Carlo Algorithm via Haar Wavelets — arXiv:2608.27986},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.27986},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_082fce380494; sha256 3f3aff336ea6860600d1586f4935dfc1737e7a4c184d398083712d4d841c3144},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.27986. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Numerical integration---approximating the integral of a function $f$ using $n$ point evaluations---is a central task in science and engineering. The two main paradigms for this problem, the Monte Carlo and quasi-Monte Carlo methods, have distinct strengths and limitations, and a fundamental question is to design a method that combines the benefits of both. \smallskip Building on recent algorithmic advances in discrepancy theory, Bansal and Jiang \cite{BJ25a} gave a randomized QMC method that naturally bridges the MC and QMC error guarantees. Their method also achieves a surprising improvement over the classical Koksma--Hlawka inequality for QMC methods: it attains an error bound of $\widetilde{O}(\sigma_{\mathsf{SO}}(f)/n)$, where $\sigma_{\mathsf{SO}}(f)$ is a new notion of \emph{smoothed-out variation} that they introduced and showed to be substantially smaller than the Hardy--Krause variation governing the classical bound. \smallskip However, the analysis in \cite{BJ25a} is quite involved: it must carefully exploit the structure of the dyadic decomposition and the randomness of the algorithm inside a sufficiently fine discretization of the Hlawka--Zaremba formula to obtain cancellations among the high-frequency components in the Fourier decomposition of $f$. The contribution of this article is twofold: (1) We give an equivalent characterization of $\sigma_{\mathsf{SO}}(f)$ in terms of the Haar--Besov seminorm of $f$, relating this new notion of smoothed-out variation to classical quantities. (2) Through this characterization, we provide a conceptually simpler and more direct analysis of the Bansal--Jiang QMC method via Haar decomposition, bypassing the use of the Hlawka--Zaremba formula, Fourier decomposition, and the delicate cancellation arguments of \cite{BJ25a} that heavily exploit the structure of dyadic decomposition.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-31 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.27986 — 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-17T11:23:11.254Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).