Integration method reduces sample size with similar accuracy benefits
Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + \varepsilon)n$ Samples Suffice
Data Structures and Algorithms
Summary
Calculating the average value of complicated functions can be done by sampling points and averaging their outputs. Traditional methods either use random points (Monte Carlo) or carefully chosen points (quasi-Monte Carlo), each with pros and cons. The authors built upon a recent method that combined these two approaches but needed a large number of samples. Their improvement drastically cuts the extra samples required, making the method more efficient while keeping good accuracy. This new approach helps in generating sample points that balance randomness and structure for better estimation.
What this means in practice
- •For simulation engineers: Generate more accurate numerical estimates using fewer samples in high-dimensional simulations to speed up engineering analyses.
- •For financial modelers: Improve the efficiency of calculating risk and pricing models by using fewer simulation points with controlled integration error.
Authors
Ekene Ezeunala, Agastya Vibhuti Jha, Haotian Jiang
Abstract
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(σ_{\mathsf{SO}}(f)/n)$, where the smoothed-out variation $σ_{\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}.