Quasi-Monte Carlo confidence intervals using quantiles of randomized nets
Zexin Pan · 2025
Read Quasi-Monte Carlo confidence intervals using quantiles of randomized nets by Zexin Pan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19138.txt.
Introduction
Zexin Pan shows in 2025 how to build confidence intervals for quasi-Monte Carlo estimates using quantiles of randomized nets. These methods estimate high dimensional integrals with structured point sets rather than pure chance. Recent work found that taking the median of many runs can speed convergence sharply.
Pan extends that idea from the median to the full set of quantiles. For a class of very smooth integrands, the error splits into a symmetric main part and a shrinking rest. That symmetry means an interval built from run quantiles will cover the true integral with a chance that nears its target level. The target itself follows from a binomial count of runs. The result gives users of these fast estimators a principled way to state their uncertainty.
Catalog record
| CREATOR | Zexin Pan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 119 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19138
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quasi-Monte Carlo confidence intervals using quantiles of randomized nets Zexin Pan Abstract Recent advances in quasi-Monte Carlo integration have shown that for linearly scrambled digital net estimators, the convergence rate can be dramatically improved by taking the median rather than the mean of multiple independent replicates. In this work, we demonstrate that the quantiles of such estimators can be used to construct confidence intervals with asymptotically valid coverage for high-dimensional integrals. By analyzing the error distribution for a class of infinitely differentiable integrands, we prove that as the sample size increases, the integration error decomposes into an asymptotically symmetric component and a vanishing remainder. Consequently, the asymptotic error distribution is symmetric about zero, ensuring that a quantile-based interval constructed from independent replicates captures the true integral with probability converging to a nominal level determined by the binomial distribution. 0 0 footnotetext: Email addresses: [email protected] 1 Introduction Quasi-Monte Carlo (QMC) methods have emerged as a powerful alternative to conventional Monte Carlo (MC) integration [ 3 ] . Like MC, QMC approximates a high-dimensional integral \mu=\int_{[0,1]^{s}}f(\boldsymbol{x})\,\mathrm{d}\boldsymbol{x} by averaging n function evaluations \hat{\mu}=(1/n)\sum_{i=0}^{n-1}f(\boldsymbol{x}_{i}) . Unlike MC, however, QMC replaces independent sampling with carefully constructed point sets \{\boldsymbol{x}_{0},\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{n-1}\} designed to efficiently explore the integration domain [0,1]^{s} , which corresponds to s uniform random seeds. This paper focuses on digital nets [ 4 ] , a class of point set constructions that enable QMC to mitigate the curse of dimensionality more effectively than classical quadrature rules while achieving convergence rates faster than MC under smoothness assumptions. Despite their success, QMC estimators based on digital nets face challenges in error quantification because the function evaluations f(\boldsymbol{x}_{i}) within a QMC mean \hat{\mu} are dependent [ 22 ] . Conventional solutions employ randomization techniques to generate independent replicates of QMC means, from which t -confidence intervals are constructed. Common choices of randomization are Owen’s nested uniform scrambling [ 21 ] and Matoušek’s random linear scrambling [ 18 ] . Loh [ 16 ] establishes the asymptotic normality of Owen-scrambled QMC means under certain restrictions, thereby justifying the use of t -intervals. However, even for infinitely differentiable integrands, the variance of these estimators cannot decay faster than O(n^{-3}) , compromising their computational efficiency. Random linear scrambling, on the other hand, produces estimators with the same variance as Owen’s scrambling [ 32 ] , but exhibits markedly different error behavior. These estimators lack asymptotic normality and instead concentrate within a narrow interval whose length adapts to the smoothness of integrands. Notably, for one-dimensional analytic integrands, the median of linearly scrambled QMC means converges to the target integral at super-polynomial rates O(n^{-c\log n}) for a constant c>0 [ 24 ] . This result was later generalized to multidimensional analytic integrands [ 25 ] . For \alpha -times differentiable integrands, Pan [ 28 ] demonstrates that the median attains nearly optimal convergence rates O(n^{-\alpha-1/2+\varepsilon}) for every \varepsilon>0 even without prior knowledge of \alpha . The apparent paradox between fast median convergence and slow variance decay is explained by the presence of outliers [ 24 , Section 3] . Owing to their outlier sensitivity, t -intervals constructed under linear scrambling often overestimate uncertainty and achieve coverage exceeding the nominal level, as observed empirically in [ 17 ] . Quantile-based intervals, while more robust and empirically accurate, currently lack theoretical guarantees on coverage—a critical gap that this work addresses. Before presenting our results, we situate our contributions within the context of existing methods for error quantification with QMC. In [ 19 ] , asymptotically valid t -intervals are established by letting the number of independent QMC replicates r grow polynomially with the per-replicate sample size n . While theoretically sound, this approach requires a total sample size N=nr=O(n^{1+c}) for r=O(n^{c}) , resulting in suboptimal convergence rates. An alternative approach by [ 10 ] introduces robust estimation techniques to handle non-normal errors, but still requires reliable variance estimation and is ultimately constrained by the slow decay of the variance. Higher-order scrambled digital nets [ 5 ] attain optimal rates under explicit smoothness priors and enable empirically valid t -intervals, though rigorous coverage guarantees remain unproven. A recent method by [ 12 ] establishes valid finite-sample coverage based on empirical Bernstein bounds, but it requires explicit upper and lower bounds on the integrand and its variance decays no faster than O(N^{-2}) given a total sample size N . For completely monotone integrands, point sets with non-negative (or non-positive) local discrepancy yield computable upper (or lower) error bounds [ 9 ] , but their convergence rates degrade with the dimension s and become unattractive for s>4 . We refer to [ 22 ] for a comprehensive survey. Together, these gaps motivate our focus on quantile-based intervals, which achieve both convergence rates that adapt to the smoothness of integrands and, as we will establish, asymptotically valid coverage for a class of infinitely differentiable integrands including f(\boldsymbol{x})=\exp(\sum_{j=1}^{s}x_{j}) and f(\boldsymbol{x})=\prod_{j=1}^{s}(1-x_{j}/2)^{-1} . Furthermore, the number of replicates r need not scale with the per-replicate sample size n . Our main result, informally stated, is the following theorem. We refer to Theorem 7 and Theorem 10 for precise statements. Theorem 1 . If the integrand f satisfies the assumptions of Theorem 6 , then the QMC estimator \hat{\mu}_{m,\infty} with sample size n=2^{m} defined in Subsection 2.1 satisfies \lim_{m\to\infty}\left(\Pr(\hat{\mu}_{m,\infty}<\mu)+\frac{1}{2}\Pr(\hat{\mu}_{m,\infty}=\mu)\right)=\frac{1}{2}. As a consequence, given r independent replicates \hat{\mu}^{(1)}_{m,\infty},\dots,\hat{\mu}^{(r)}_{m,\infty} ordered from smallest to largest, we may choose indices 1\leqslant\ell<u\leqslant r and construct the confidence interval [\hat{\mu}^{(\ell)}_{m,\infty},\hat{\mu}^{(u)}_{m,\infty}] for \mu . Its asymptotic coverage is guaranteed by Theorem 1 and follows directly from the binomial distribution. Precise expressions are given in Corollary 3 . The remainder of this paper is structured as follows. Section 2 introduces foundational concepts and notation, including the Walsh decomposition framework and properties of Walsh coefficients that are critical to our analysis. Section 3 proves Theorem 1 for complete random designs, a simplified yet illustrative randomization scheme. After outlining the proof strategy, we systematically address each key component of the argument in Subsections 3.1 – 3.3 , and derive crucial corollaries in Subsection 3.4 . Section 4 extends these results to more general randomization schemes, with random linear scrambling as a central special case. Section 5 empirically validates our theory on two highly skewed integrands. Finally, Section 6 identifies challenges in extending these results to finitely differentiable integrands and concludes the paper with a discussion of open research questions. 2 Background and notation Let \mathbb{N}=\{1,2,3,\dots\} denote the natural numbers, \mathbb{N}_{0}=\mathbb{N}\cup\{0\} , and \mathbb{N}_{*}^{s}=\mathbb{N}_{0}^{s}\setminus\{\boldsymbol{0}\} (excluding the zero vector). For \ell\in\mathbb{N} , we define \mathbb{Z}_{\ell}=\{0,1,\dots,\ell-1\} . When we wish to emphasize its field structure, we write \mathbb{Z}_{2} as \mathbb{F}_{2} . The dimension of the integration domain is s\in\mathbb{N} , with 1{:}s=\{1,2,\dots,s\} . For a matrix C , C(\ell,:) denotes its \ell -th row. The indicator function \boldsymbol{1}\{\mathcal{A}\} equals 1 if event \mathcal{A} occurs and 0 otherwise. For a finite set K , |K| is its cardinality, and \mathbb{U}(K) represents the uniform distribution over K . Equality in distribution is written as X\overset{d}{=}Y . For asymptotics, a_{m}\sim b_{m} denotes \lim_{m\to\infty}a_{m}/b_{m}=1 and a_{m}\sim\sum_{\ell=1}^{L}b_{m,\ell} recursively means a_{m}-\sum_{\ell=1}^{L^{\prime}-1}b_{m,\ell}\sim b_{m,L^{\prime}} for 2\leqslant L^{\prime}\leqslant L . The integrand f:[0,1]^{s}\to\mathbb{R} has L^{1} -norm \|f\|_{1}=\int_{[0,1]^{s}}|f(\boldsymbol{x})|\,\mathrm{d}\boldsymbol{x} and L^{\infty} -norm \|f\|_{\infty}=\sup_{\boldsymbol{x}\in[0,1]^{s}}|f(\boldsymbol{x})| . Let C([0,1]^{s}) and C^{\infty}([0,1]^{s}) denote the spaces of continuous and infinitely differentiable functions,