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

SIAM Journal on Numerical Analysis

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

Zhijian He, Xiaoqun Wang

Published Jan 1, 2015• 28 citations
Publisher

Abstract

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.

DOI
10.1137/15m1007963

Related papers

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

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

Quasi-Monte Carlo Beyond Hardy-Krause

Nikhil Bansal, Haotian Jiang

We examine the problem of numerically estimating the integral of a function f. The classical approaches to this problem are Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods. MC methods use random samples to evaluate f and have error , where σ(f ) is the standard deviation of f. QMC methods are based on evaluating f at explicit point sets with low discrepancy, and as given by the classical Koksma- Hlawka inequality, they have error Õ (σHK(f )/n ), where σΗΚ(f ) is the variation of f in the sense of Hardy and Krause. These two methods have distinctive advantages and shortcomings, and a fundamental question is to find a method that combines the advantages of both.

arXiv:2408.06475•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2025•2 citations

Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands

Josef Dick

We study a random sampling technique to approximate integrals ∫[0, 1]s f(x) dx by averaging the function at some sampling points. We focus on cases where the integrand is smooth, which is a problem which occurs in statistics. The convergence rate of the approximation error depends on the smoothness of the function f and the sampling technique. For instance, Monte Carlo (MC) sampling yields a convergence of the root mean square error (RMSE) of order N−1/2 (where N is the number of samples) for functions f with finite variance. Randomized QMC (RQMC), a combination of MC and quasi-Monte Carlo (QMC), achieves a RMSE of order N−3/2+ε under the stronger assumption that the integrand has bounded variation. A combination of RQMC with local antithetic sampling achieves a convergence of the RMSE of order N−3/2−1/s+ε (where s ≥ 1 is the dimension) for functions with mixed partial derivatives up to order two. Additional smoothness of the integrand does not improve the rate of convergence of these algorithms in general. On the other hand, it is known that without additional smoothness of the integrand it is not possible to improve the convergence rate. This paper introduces a new RQMC algorithm, for which we prove that it achieves a convergence of the root mean square error (RMSE) of order N−α−1/2+ε provided the integrand satisfies the strong assumption that it has square integrable partial mixed derivatives up to order α > 1 in each variable. Known lower bounds on the RMSE show that this rate of convergence cannot be improved in general for integrands with this smoothness. We provide numerical examples for which the RMSE converges approximately with order N−5/2 and N−7/2, in accordance with the theoretical upper bound.

arXiv:1007.0842•The Annals of Statistics•May 4, 2011•48 citations

Fixed-Horizon Error Rates for Array-RQMC Metropolis-Hastings

Jiarui Du, Josef Dick, Zexin Pan +1 more

This paper studies randomised quasi-Monte Carlo (RQMC) methods for Metropolis--Hastings (MH) algorithms, whose accept--reject discontinuity complicates RQMC analysis. To circumvent some of these complications, we study Array-RQMC for MH, with $N$ replicated chains evolved over a fixed time horizon $T$, where we make use of Hilbert sorting for joint multidimensional updates at each step. For one-dimensional MH and bounded-variation test functions, we prove a sampling mean squared error bound of $\mathcal O_T(N^{-4/3})$ relative to the finite-horizon expectation. For product targets, coordinatewise Array-RQMC Metropolis-within-Gibbs retains this exponent for additive marginal bounded-variation tests, with constants that may depend on dimension. With Gaussian random-walk proposals, the bounds extend to scalar and additive marginal polynomials with an additional factor $(\log N)^\ell$, where $\ell$ is the maximum polynomial degree. For joint updates in state dimension $p$ using $p$ proposal uniforms, we provide a conditional $\mathcal O_T(N^{-1-1/(p+2)})$ framework under regularity assumptions that are not verified for the joint multidimensional examples. Numerical experiments support the verified one-dimensional theory and demonstrate variance reduction for joint Hilbert-sorted updates, including Bayesian logistic regression, while illustrating the limitations of these gains as dimension increases.

arXiv:2610.36431•Oct 27, 2026•0 citations

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

Aadit Jain, Fred J. Hickernell, Art B. Owen +1 more

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.

arXiv:2504.18677•Information and Inference A Journal of the IMA•Feb 6, 2026•3 citations
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.
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.
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 examine the problem of numerically estimating the integral of a function f. The classical approaches to this problem are Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods. MC methods use random samples to evaluate f and have error , where σ(f ) is the standard deviation of f. QMC methods are based on evaluating f at explicit point sets with low discrepancy, and as given by the classical Koksma- Hlawka inequality, they have error Õ (σHK(f )/n ), where σΗΚ(f ) is the variation of f in the sense of Hardy and Krause. These two methods have distinctive advantages and shortcomings, and a fundamental question is to find a method that combines the advantages of both.
We study a random sampling technique to approximate integrals ∫[0, 1]s f(x) dx by averaging the function at some sampling points. We focus on cases where the integrand is smooth, which is a problem which occurs in statistics. The convergence rate of the approximation error depends on the smoothness of the function f and the sampling technique. For instance, Monte Carlo (MC) sampling yields a convergence of the root mean square error (RMSE) of order N−1/2 (where N is the number of samples) for functions f with finite variance. Randomized QMC (RQMC), a combination of MC and quasi-Monte Carlo (QMC), achieves a RMSE of order N−3/2+ε under the stronger assumption that the integrand has bounded variation. A combination of RQMC with local antithetic sampling achieves a convergence of the RMSE of order N−3/2−1/s+ε (where s ≥ 1 is the dimension) for functions with mixed partial derivatives up to order two. Additional smoothness of the integrand does not improve the rate of convergence of these algorithms in general. On the other hand, it is known that without additional smoothness of the integrand it is not possible to improve the convergence rate. This paper introduces a new RQMC algorithm, for which we prove that it achieves a convergence of the root mean square error (RMSE) of order N−α−1/2+ε provided the integrand satisfies the strong assumption that it has square integrable partial mixed derivatives up to order α > 1 in each variable. Known lower bounds on the RMSE show that this rate of convergence cannot be improved in general for integrands with this smoothness. We provide numerical examples for which the RMSE converges approximately with order N−5/2 and N−7/2, in accordance with the theoretical upper bound.
This paper studies randomised quasi-Monte Carlo (RQMC) methods for Metropolis--Hastings (MH) algorithms, whose accept--reject discontinuity complicates RQMC analysis. To circumvent some of these complications, we study Array-RQMC for MH, with NNN replicated chains evolved over a fixed time horizon TTT, where we make use of Hilbert sorting for joint multidimensional updates at each step. For one-dimensional MH and bounded-variation test functions, we prove a sampling mean squared error bound of OT(N−4/3)\mathcal O_T(N^{-4/3})OT​(N−4/3) relative to the finite-horizon expectation. For product targets, coordinatewise Array-RQMC Metropolis-within-Gibbs retains this exponent for additive marginal bounded-variation tests, with constants that may depend on dimension. With Gaussian random-walk proposals, the bounds extend to scalar and additive marginal polynomials with an additional factor (log⁡N)ℓ(\log N)^\ell(logN)ℓ, where ℓ\ellℓ is the maximum polynomial degree. For joint updates in state dimension ppp using ppp proposal uniforms, we provide a conditional OT(N−1−1/(p+2))\mathcal O_T(N^{-1-1/(p+2)})OT​(N−1−1/(p+2)) framework under regularity assumptions that are not verified for the joint multidimensional examples. Numerical experiments support the verified one-dimensional theory and demonstrate variance reduction for joint Hilbert-sorted updates, including Bayesian logistic regression, while illustrating the limitations of these gains as dimension increases.
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.