Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2504.18677 · Information and Inference A Journal of the IMA

Empirical Bernstein and betting confidence intervals for randomized quasi-Monte Carlo

Aadit Jain, Fred J. Hickernell, Art B. Owen, Aleksei G. Sorokin

Published Feb 6, 2026• 0 citations
arXivHTMLPDF

Abstract

Abstract Randomized quasi-Monte Carlo (RQMC) methods estimate the mean of a random variable by sampling an integrand at $n$ equidistributed points. For scrambled digital nets, the resulting variance is typically $\tilde O(n^{-\theta })$, where $\theta \in [1,3]$ depends on the smoothness of the integrand and $\tilde O$ neglects logarithmic factors. While RQMC can be far more accurate than plain Monte Carlo (MC), it remains difficult to get confidence intervals on RQMC estimates. We investigate some empirical Bernstein confidence intervals (EBCIs) and hedged betting confidence intervals (HBCIs), both from Waudby-Smith and Ramdas (2024, J. Roy. Statist. Soc. B, 86, 1–27), when the random variable of interest is subject to known bounds. When there are $N$ integrand evaluations partitioned into $R$ independent replicates of $n=N/R$ RQMC points, and the RQMC variance is $\varTheta (n^{-\theta })$, then an oracle minimizing the width of a Bennett confidence interval would choose $n =\varTheta (N^{1/(\theta +1)})$. The resulting intervals have a width $\varTheta (N^{-\theta /(\theta +1)})$. Our empirical investigations had optimal values of $n$ grow slowly with $N$, HBCI intervals that were usually narrower than the EBCI ones and optimal values of $n$ for HBCI that were equal to or smaller than the ones for the oracle.

DOI
10.1093/imaiai/iaag003

Related papers

Randomized Quasi-Monte Carlo: An Introduction for Practitioners

Pierre L’Ecuyer

We survey basic ideas and results on randomized quasi-Monte Carlo (RQMC) methods, discuss their practical aspects, and give numerical illustrations. RQMC can improve accuracy compared with standard Monte Carlo (MC) when estimating an integral interpreted as a mathematical expectation. RQMC estimators are unbiased and their variance converges at a faster rate (under certain conditions) than MC estimators, as a function of the sample size. Variants of RQMC also work for the simulation of Markov chains, for function approximation and optimization, for solving partial differential equations, etc. In this introductory survey, we look at how RQMC point sets and sequences are constructed, how we measure their uniformity, why they can work for high-dimensional integrals, and how can they work when simulating Markov chains over a large number of steps.

•Aug 14, 2016•2 citations

On the error distribution for randomly-shifted lattice rules

Pierre L’Ecuyer, Bruno Tuffin

Randomized quasi-Monte Carlo (RQMC) methods estimate the expectation of a random variable by the average of n dependent realizations of it. In general, due to the strong dependence, the estimation error may not obey a central limit theorem. Analysis of RQMC methods have so far focused mostly on the convergence rates of asymptotic worst-case error bounds and variance bounds, when n ¿ ¿, but little is known about the limiting distribution of the error. Here we examine this limiting distribution for the special case of a randomly-shifted lattice rule, when the integrand is smooth. We start with simple one-dimensional functions, where we show that the limiting distribution is uniform over a bounded interval if the integrand is non-periodic, and has a square root form over a bounded interval if the integrand is periodic. In higher dimensions, for linear functions, the distribution function of the properly standardized error converges to a spline of degree equal to the dimension.

Winter Simulation Conference•Dec 1, 2009•2 citations

On the error distribution for randomly-shifted lattice rules

Pierre L’Ecuyer, Bruno Tuffin

Randomized quasi-Monte Carlo (RQMC) methods estimate the expectation of a random variable by the average of n dependent realizations of it. In general, due to the strong dependence, the estimation error may not obey a central limit theorem. Analysis of RQMC methods have so far focused mostly on the convergence rates of asymptotic worst-case error bounds and variance bounds, when n → ∞, but little is known about the limiting distribution of the error. Here we examine this limiting distribution for the special case of a randomly-shifted lattice rule, when the integrand is smooth. We start with simple one-dimensional functions, where we show that the limiting distribution is uniform over a bounded interval if the integrand is non-periodic, and has a square root form over a bounded interval if the integrand is periodic. In higher dimensions, for linear functions, the distribution function of the properly standardized error converges to a spline of degree equal to the dimension.

Winter Simulation Conference•Dec 13, 2009•2 citations

Some convergence results in randomized quasi Monte Carlo

Yang Liu

We study the convergence rate of randomized quasi-Monte Carlo (RQMC) methods for integrands with different smoothness. The Koksma--Hlawka inequality fails to be informative for certain $L^2$ singular integrands. We provide convergence results based on spectral analysis.

•Jan 1, 2025•0 citations

Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + \varepsilon)n$ Samples Suffice

Ekene Ezeunala, Agastya Vibhuti Jha, Haotian Jiang

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}.

arXiv:2609.10921•Sep 10, 2026•0 citations

On the Convergence Rate of Randomized Quasi--Monte Carlo for Discontinuous Functions

Zhijian He, Xiaoqun Wang

This paper studies the convergence rate of randomized quasi--Monte Carlo (RQMC) for discontinuous functions, which are often of infinite variation in the sense of Hardy and Krause. It was previously known that the root mean square error (RMSE) of RQMC is only $o(n^{-1/2})$ for discontinuous functions. For certain discontinuous functions in $d$ dimensions, we prove that the RMSE of RQMC is $O(n^{-1/2-1/(4d-2)+\epsilon})$ for any $\epsilon>0$ and arbitrary $n$. If some discontinuity boundaries are parallel to some coordinate axes, the rate can be improved to $O(n^{-1/2-1/(4d_u-2)+\epsilon})$, where $d_u$ denotes the so-called irregular dimension, that is, the number of axes which are not parallel to the discontinuity boundaries. Moreover, this paper shows that the RMSE is $O(n^{-1/2-1/(2d)})$ for certain indicator functions.

SIAM Journal on Numerical Analysis•Jan 1, 2015•27 citations
Abstract Randomized quasi-Monte Carlo (RQMC) methods estimate the mean of a random variable by sampling an integrand at nnn equidistributed points. For scrambled digital nets, the resulting variance is typically O~(n−θ)\tilde O(n^{-\theta })O~(n−θ), where θ∈[1,3]\theta \in [1,3]θ∈[1,3] depends on the smoothness of the integrand and O~\tilde OO~ neglects logarithmic factors. While RQMC can be far more accurate than plain Monte Carlo (MC), it remains difficult to get confidence intervals on RQMC estimates. We investigate some empirical Bernstein confidence intervals (EBCIs) and hedged betting confidence intervals (HBCIs), both from Waudby-Smith and Ramdas (2024, J. Roy. Statist. Soc. B, 86, 1–27), when the random variable of interest is subject to known bounds. When there are NNN integrand evaluations partitioned into RRR independent replicates of n=N/Rn=N/Rn=N/R RQMC points, and the RQMC variance is Θ(n−θ)\varTheta (n^{-\theta })Θ(n−θ), then an oracle minimizing the width of a Bennett confidence interval would choose n=Θ(N1/(θ+1))n =\varTheta (N^{1/(\theta +1)})n=Θ(N1/(θ+1)). The resulting intervals have a width Θ(N−θ/(θ+1))\varTheta (N^{-\theta /(\theta +1)})Θ(N−θ/(θ+1)). Our empirical investigations had optimal values of nnn grow slowly with NNN, HBCI intervals that were usually narrower than the EBCI ones and optimal values of nnn for HBCI that were equal to or smaller than the ones for the oracle.
We survey basic ideas and results on randomized quasi-Monte Carlo (RQMC) methods, discuss their practical aspects, and give numerical illustrations. RQMC can improve accuracy compared with standard Monte Carlo (MC) when estimating an integral interpreted as a mathematical expectation. RQMC estimators are unbiased and their variance converges at a faster rate (under certain conditions) than MC estimators, as a function of the sample size. Variants of RQMC also work for the simulation of Markov chains, for function approximation and optimization, for solving partial differential equations, etc. In this introductory survey, we look at how RQMC point sets and sequences are constructed, how we measure their uniformity, why they can work for high-dimensional integrals, and how can they work when simulating Markov chains over a large number of steps.
Randomized quasi-Monte Carlo (RQMC) methods estimate the expectation of a random variable by the average of n dependent realizations of it. In general, due to the strong dependence, the estimation error may not obey a central limit theorem. Analysis of RQMC methods have so far focused mostly on the convergence rates of asymptotic worst-case error bounds and variance bounds, when n ¿ ¿, but little is known about the limiting distribution of the error. Here we examine this limiting distribution for the special case of a randomly-shifted lattice rule, when the integrand is smooth. We start with simple one-dimensional functions, where we show that the limiting distribution is uniform over a bounded interval if the integrand is non-periodic, and has a square root form over a bounded interval if the integrand is periodic. In higher dimensions, for linear functions, the distribution function of the properly standardized error converges to a spline of degree equal to the dimension.
Randomized quasi-Monte Carlo (RQMC) methods estimate the expectation of a random variable by the average of n dependent realizations of it. In general, due to the strong dependence, the estimation error may not obey a central limit theorem. Analysis of RQMC methods have so far focused mostly on the convergence rates of asymptotic worst-case error bounds and variance bounds, when n → ∞, but little is known about the limiting distribution of the error. Here we examine this limiting distribution for the special case of a randomly-shifted lattice rule, when the integrand is smooth. We start with simple one-dimensional functions, where we show that the limiting distribution is uniform over a bounded interval if the integrand is non-periodic, and has a square root form over a bounded interval if the integrand is periodic. In higher dimensions, for linear functions, the distribution function of the properly standardized error converges to a spline of degree equal to the dimension.
We study the convergence rate of randomized quasi-Monte Carlo (RQMC) methods for integrands with different smoothness. The Koksma--Hlawka inequality fails to be informative for certain L2L^2L2 singular integrands. We provide convergence results based on spectral analysis.
Quasi-Monte Carlo Beyond Hardy-Krause II: (1+ε)n(1 + \varepsilon)n(1+ε)n Samples Suffice
Numerical integration studies how well one can estimate the integral of a function fff over [0,1)d[0,1)^d[0,1)d using nnn 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 O~d(σSO(f)/n)\widetilde{O}_d(σ_{\mathsf{SO}}(f)/n)Od​(σSO​(f)/n), where the smoothed-out variation σSO(f)σ_{\mathsf{SO}}(f)σSO​(f) can be substantially smaller than the Hardy--Krause variation that governs the classical bound. However, their algorithm requires n2n^2n2 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 ε>0\varepsilon > 0ε>0, we show that (1+ε)n(1+\varepsilon)n(1+ε)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}.
This paper studies the convergence rate of randomized quasi--Monte Carlo (RQMC) for discontinuous functions, which are often of infinite variation in the sense of Hardy and Krause. It was previously known that the root mean square error (RMSE) of RQMC is only o(n−1/2)o(n^{-1/2})o(n−1/2) for discontinuous functions. For certain discontinuous functions in ddd dimensions, we prove that the RMSE of RQMC is O(n−1/2−1/(4d−2)+ϵ)O(n^{-1/2-1/(4d-2)+\epsilon})O(n−1/2−1/(4d−2)+ϵ) for any ϵ>0\epsilon>0ϵ>0 and arbitrary nnn. If some discontinuity boundaries are parallel to some coordinate axes, the rate can be improved to O(n−1/2−1/(4du−2)+ϵ)O(n^{-1/2-1/(4d_u-2)+\epsilon})O(n−1/2−1/(4du​−2)+ϵ), where dud_udu​ denotes the so-called irregular dimension, that is, the number of axes which are not parallel to the discontinuity boundaries. Moreover, this paper shows that the RMSE is O(n−1/2−1/(2d))O(n^{-1/2-1/(2d)})O(n−1/2−1/(2d)) for certain indicator functions.