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.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.18677Information and Inference A Journal of the IMAFeb 6, 20260 citations

A Practical Approach to the Error Estimation of Quasi-Monte Carlo Integrations

Hozumi Morohosi, Masanori Fushimi

Springer eBooksJan 1, 200021 citations

A Universal Median Quasi-Monte Carlo Integration

Takashi Goda, Kosuke Suzuki, Makoto Matsumoto

Abstract. We study quasi-Monte Carlo (QMC) integration over the multidimensional unit cube in several weighted function spaces with different smoothness classes. We consider approximating the integral of a function by the median of several integral estimates under independent and random choices of the underlying QMC point sets (either linearly scrambled digital nets or infinite-precision polynomial lattice point sets). Even though our approach does not require any information on the smoothness and weights of a target function space as an input, we can prove a probabilistic upper bound on the worst-case error for the respective weighted function space, where the failure probability converges to 0 exponentially fast as the number of estimates increases. Our obtained rates of convergence are nearly optimal for function spaces with finite smoothness, and we can attain a dimension-independent super-polynomial convergence for a class of infinitely differentiable functions. This implies that our median-based QMC rule is universal in the sense that it does not need to be adjusted to the smoothness and the weights of the function spaces and yet exhibits the nearly optimal rate of convergence. Numerical experiments support our theoretical results.Abstract. We study quasi-Monte Carlo (QMC) integration over the multidimensional unit cube in several weighted function spaces with different smoothness classes. We consider approximating the integral of a function by the median of several integral estimates under independent and random choices of the underlying QMC point sets (either linearly scrambled digital nets or infinite-precision polynomial lattice point sets). Even though our approach does not require any information on the smoothness and weights of a target function space as an input, we can prove a probabilistic upper bound on the worst-case error for the respective weighted function space, where the failure probability converges to 0 exponentially fast as the number of estimates increases. Our obtained rates of convergence are nearly optimal for function spaces with finite smoothness, and we can attain a dimension-independent super-polynomial convergence for a class of infinitely differentiable functions. This implies that our median-based QMC rule is universal in the sense that it does not need to be adjusted to the smoothness and the weights of the function spaces and yet exhibits the nearly optimal rate of convergence. Numerical experiments support our theoretical results.

arXiv:2209.13186SIAM Journal on Numerical AnalysisFeb 16, 202412 citations

A Monte Carlo method for integration of multivariate smooth functions I: Sobolev spaces

Mario Ullrich

We study a Monte Carlo algorithm that is based on a specific (randomly shifted and dilated) lattice point set. The main result of this paper is that the mean squared error for a given compactly supported, square-integrable function is bounded by $n^{-1/2}$ times the $L_2$ -norm of the Fourier transform outside a region around the origin, where $n$ is the expected number of function evaluations. As corollaries we obtain the order of convergence for the Sobolev spaces $H^s_p$ with isotropic, anisotropic or mixed smoothness for all values of the parameters. This proves, in particular, that the optimal order of convergence in the latter case is $n^{-s-1/2}$ for $p\ge2$ , which is, in contrast to the case of deterministic algorithms, independent of the dimension. This shows that Monte Carlo algorithms can improve the order by more than $n^{-1/2}$ for a whole class of practically important function classes. All results carry over to functions defined on the unit cube without boundary conditions.We study a Monte Carlo algorithm that is based on a specific (randomly shifted and dilated) lattice point set. The main result of this paper is that the mean squared error for a given compactly supported, square-integrable function is bounded by $n^{-1/2}$ times the $L_2$-norm of the Fourier transform outside a region around the origin, where $n$ is the expected number of function evaluations. As corollaries we obtain the order of convergence for the Sobolev spaces $H^s_p$ with isotropic, anisotropic or mixed smoothness for all values of the parameters. This proves, in particular, that the optimal order of convergence in the latter case is $n^{-s-1/2}$ for $p\ge2$, which is, in contrast to the case of deterministic algorithms, independent of the dimension. This shows that Monte Carlo algorithms can improve the order by more than $n^{-1/2}$ for a whole class of practically important function classes. All results carry over to functions defined on the unit cube without boundary conditions.

Apr 20, 20161 citation

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.

n^{-1/2}

times the

L_2

-norm of the Fourier transform outside a region around the origin, where

n

is the expected number of function evaluations. As corollaries we obtain the order of convergence for the Sobolev spaces

H^s_p

with isotropic, anisotropic or mixed smoothness for all values of the parameters. This proves, in particular, that the optimal order of convergence in the latter case is

n^{-s-1/2}

for

p\ge2

, which is, in contrast to the case of deterministic algorithms, independent of the dimension. This shows that Monte Carlo algorithms can improve the order by more than

n^{-1/2}

for a whole class of practically important function classes. All results carry over to functions defined on the unit cube without boundary conditions.