Abstract The deterministic sparse grid method, also known as Smolyak’s method, is a well-established and widely used tool to tackle multivariate approximation problems, and there is a vast literature on it. Much less is known about randomized versions of the sparse grid method. In this paper we analyze randomized sparse grid algorithms, namely randomized sparse grid quadratures for multivariate integration on the
D-dimensional unit cube
[0,1)D. Let
d,s∈N be such that
D=d⋅s. The
s-dimensional building blocks of the sparse grid quadratures are based on stratified sampling for
s=1 and on scrambled
(0,m,s)-nets for
s≥2. The spaces of integrands and the error criterion we consider are Haar wavelet spaces with parameter $\alpha $ and the randomized error (i.e., the worst case root mean square error), respectively. We prove sharp (i.e., matching) upper and lower bounds for the convergence rates of the
Nth minimal errors for all possible combinations of the parameters
d and
s. Our upper error bounds still hold if we consider as spaces of integrands Sobolev spaces of mixed dominated smoothness with smoothness parameters
1/2<α<1 instead of Haar wavelet spaces.
In this paper, we consider Smolyak algorithms based on quasi-Monte Carlo rules for high-dimensional numerical integration. The quasi-Monte Carlo rules employed here use digital (t, α, β, σ, d)-sequences as quadrature points. We consider the worst-case error for multivariate integration in certain Sobolev spaces and show that our quadrature rules achieve the optimal rate of convergence. By randomizing the underlying digital sequences, we can also obtain a randomized Smolyak algorithm. The bound on the worst-case error holds also for the randomized algorithm in a statistical sense. Further, we also show that the randomized algorithm is unbiased and that the integration error can be approximated as well.
We study the randomized worst-case error and the randomized error of scrambled quasi–Monte Carlo (QMC) quadrature as proposed by Owen. The function spaces considered in this article are the weighted Hilbert spaces generated by Haar-like wavelets and the weighted Sobolev-Hilbert spaces. Conditions are found under which multivariate integration is strongly tractable in the randomized worst-case setting and the randomized setting , respectively. The ε \varepsilon -exponents of strong tractability are found for the scrambled Niederreiter nets and sequences. The sufficient conditions for strong tractability for Sobolev spaces are more lenient for scrambled QMC quadratures than those for deterministic QMC net quadratures.
We study the numerical approximation of high-dimensional integrals using randomized quasi-Monte Carlo (RQMC) methods, with a focus on scrambled Sobol' sequences. While asymptotically faster than Monte Carlo, classical RQMC suffers from error bounds that grow exponentially in the dimension
s, and its root mean squared error (RMSE) convergence rate is generally no better than
O(N−3/2). To overcome these limitations, we combine two recent developments: Suzuki's coarse scrambling and the median trick. Coarse scrambling randomizes Sobol' sequences according to their generating base polynomials and significantly reduces the maximal gain coefficient. By appropriately choosing the base polynomials, we show that the coefficient can be made uniformly bounded in
s, yielding an
O(N−1/2) RMSE for
L2 integrands with a dimension-independent constant. The median trick then enables near-optimal convergence for function classes beyond
L2: for
Lp integrands with
p∈(1,2), the median of independent coarsely scrambled estimates achieves an error of
O(N−1+1/p) with high probability; for integrands in the Haar wavelet space
Hwav,α,s,p,q with
αp:=α−(1/p−1/2)+>0, we prove a high-probability error bound of
O(N−αp−1/2+ε) for any
ε>0; the bound improves to
O(N−r−αp−1/2+ε) when the integrand has dominating mixed derivatives of order
r≥1 that belong to
Hwav,α,s,p,q. The latter two bounds are uniform in
s under suitable conditions on the ANOVA components of the integrands. Numerical experiments confirm the predicted convergence rates and demonstrate the robustness of the proposed approach.
Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.