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:2001.08558 · IMA Journal of Numerical Analysis

Randomized sparse grid algorithms for multivariate integration on Haar wavelet spaces

M Wnuk, Michael Gnewuch

Published Dec 1, 2021• 2 citations
arXivHTMLPDF

Abstract

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 \in {\mathbb {N}}$ be such that $D=d\cdot 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\ge 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 $N$th 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< \alpha < 1$ instead of Haar wavelet spaces.

DOI
10.1093/imanum/drab085

Related papers

Randomized Algorithms for High-Dimensional Integration and Approximation

Marcin Wnuk

We prove upper and lower error bounds for error of the randomized Smolyak algorithm and provide a thorough case study of applying the randomized Smolyak algorithm with the building blocks being quadratures based on scrambled nets for integration of functions coming from Haar-wavelets spaces. Moreover, we discuss different notions of negative dependence of randomized point sets which find applications in discrepancy theory and randomized quasi-Monte Carlo integration.

•Dec 20, 2019•0 citations

On the Randomization of Frolov's Algorithm for Multivariate Integration

David Krieg

We are concerned with the numerical integration of functions from the Sobolev space $H^{r,\text{mix}}([0,1]^d)$ of dominating mixed smoothness $r\in\mathbb{N}$ over the $d$-dimensional unit cube. In 1976, K. K. Frolov introduced a deterministic quadrature rule whose worst case error has the order $n^{-r} \, (\log n)^{(d-1)/2}$ with respect to the number $n$ of function evaluations. This is known to be optimal. 39 years later, Erich Novak and me introduced a randomized version of this algorithm using $d$ random dilations. We showed that its error is bounded above by a constant multiple of $n^{-r-1/2} \, (\log n)^{(d-1)/2}$ in expectation and by $n^{-r} \, (\log n)^{(d-1)/2}$ almost surely. The main term $n^{-r-1/2}$ is again optimal and it turns out that the very same algorithm is also optimal for the isotropic Sobolev space $H^s([0,1]^d)$ of smoothness $s>d/2$. We also added a random shift to this algorithm to make it unbiased. Just recently, Mario Ullrich proved that the expected error of the resulting algorithm on $H^{r,\text{mix}}([0,1]^d)$ is even bounded above by $n^{-r-1/2}$. This thesis is a review of the mentioned upper bounds and their proofs.

arXiv:1603.04637•Mar 15, 2016•0 citations

QMC integration based on arbitrary (t,m,s)-nets yields optimal convergence rates on several scales of function spaces

Michael Gnewuch, Josef Dick, Lev Markhasin +1 more

We study the integration problem over the $s$-dimensional unit cube on four types of Banach spaces of integrands. First we consider Haar wavelet spaces, consisting of functions whose Haar wavelet coefficients exhibit a certain decay behavior measured by a parameter $α>0$. We study the worst case error of integration over the norm unit ball and provide upper error bounds for quasi-Monte Carlo (QMC) cubature rules based on arbitrary $(t,m,s)$-nets as well as matching lower error bounds for arbitrary cubature rules. These results show that using arbitrary $(t,m,s)$-nets as sample points yields the best possible rate of convergence. Afterwards we study spaces of integrands of fractional smoothness $α\in (0,1)$ and state a sharp Koksma-Hlawka-type inequality. More precisely, we show that on those spaces the worst case error of integration is equal to the corresponding fractional discrepancy. Those spaces can be continuously embedded into tensor product Bessel potential spaces, also known as Sobolev spaces of dominated mixed smoothness, with the same set of parameters. The latter spaces can be embedded into suitable Besov spaces of dominating mixed smoothness $α$, which in turn can be embedded into the Haar wavelet spaces with the same set of parameters. Therefore our upper error bounds on Haar wavelet spaces for QMC cubatures based on $(t,m,s)$-nets transfer (with possibly different constants) to the corresponding spaces of integrands of fractional smoothness and to Sobolev and Besov spaces of dominating mixed smoothness. Moreover, known lower error bounds for periodic Sobolev and Besov spaces of dominating mixed smoothness show that QMC integration based on arbitrary $(t,m,s)$-nets yields the best possible convergence rate on periodic as well as on non-periodic Sobolev and Besov spaces of dominating smoothness.

arXiv:2409.12879•Sep 19, 2024•0 citations

Randomized Smolyak algorithms based on digital sequences for multivariate integration

Josef Dick, Gunther Leobacher, Friedrich Pillichshammer

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.

IMA Journal of Numerical Analysis•Feb 17, 2007•5 citations

Strong tractability of integration using scrambled Niederreiter points

Rong‐Xian Yue, Fred J. Hickernell

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.

Mathematics of Computation•Mar 3, 2005•15 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.

•Apr 20, 2016•1 citation
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 DDD-dimensional unit cube [0,1)D[0,1)^D[0,1)D. Let d,s∈Nd,s \in {\mathbb {N}}d,s∈N be such that D=d⋅sD=d\cdot sD=d⋅s. The sss-dimensional building blocks of the sparse grid quadratures are based on stratified sampling for s=1s=1s=1 and on scrambled (0,m,s)(0,m,s)(0,m,s)-nets for s≥2s\ge 2s≥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 NNNth minimal errors for all possible combinations of the parameters ddd and sss. Our upper error bounds still hold if we consider as spaces of integrands Sobolev spaces of mixed dominated smoothness with smoothness parameters 1/2<α<11/2< \alpha < 11/2<α<1 instead of Haar wavelet spaces.
We are concerned with the numerical integration of functions from the Sobolev space Hr,mix([0,1]d)H^{r,\text{mix}}([0,1]^d)Hr,mix([0,1]d) of dominating mixed smoothness r∈Nr\in\mathbb{N}r∈N over the ddd-dimensional unit cube. In 1976, K. K. Frolov introduced a deterministic quadrature rule whose worst case error has the order n−r (log⁡n)(d−1)/2n^{-r} \, (\log n)^{(d-1)/2}n−r(logn)(d−1)/2 with respect to the number nnn of function evaluations. This is known to be optimal. 39 years later, Erich Novak and me introduced a randomized version of this algorithm using ddd random dilations. We showed that its error is bounded above by a constant multiple of n−r−1/2 (log⁡n)(d−1)/2n^{-r-1/2} \, (\log n)^{(d-1)/2}n−r−1/2(logn)(d−1)/2 in expectation and by n−r (log⁡n)(d−1)/2n^{-r} \, (\log n)^{(d-1)/2}n−r(logn)(d−1)/2 almost surely. The main term n−r−1/2n^{-r-1/2}n−r−1/2 is again optimal and it turns out that the very same algorithm is also optimal for the isotropic Sobolev space Hs([0,1]d)H^s([0,1]^d)Hs([0,1]d) of smoothness s>d/2s>d/2s>d/2. We also added a random shift to this algorithm to make it unbiased. Just recently, Mario Ullrich proved that the expected error of the resulting algorithm on Hr,mix([0,1]d)H^{r,\text{mix}}([0,1]^d)Hr,mix([0,1]d) is even bounded above by n−r−1/2n^{-r-1/2}n−r−1/2. This thesis is a review of the mentioned upper bounds and their proofs.
We study the integration problem over the sss-dimensional unit cube on four types of Banach spaces of integrands. First we consider Haar wavelet spaces, consisting of functions whose Haar wavelet coefficients exhibit a certain decay behavior measured by a parameter α>0α>0α>0. We study the worst case error of integration over the norm unit ball and provide upper error bounds for quasi-Monte Carlo (QMC) cubature rules based on arbitrary (t,m,s)(t,m,s)(t,m,s)-nets as well as matching lower error bounds for arbitrary cubature rules. These results show that using arbitrary (t,m,s)(t,m,s)(t,m,s)-nets as sample points yields the best possible rate of convergence. Afterwards we study spaces of integrands of fractional smoothness α∈(0,1)α\in (0,1)α∈(0,1) and state a sharp Koksma-Hlawka-type inequality. More precisely, we show that on those spaces the worst case error of integration is equal to the corresponding fractional discrepancy. Those spaces can be continuously embedded into tensor product Bessel potential spaces, also known as Sobolev spaces of dominated mixed smoothness, with the same set of parameters. The latter spaces can be embedded into suitable Besov spaces of dominating mixed smoothness ααα, which in turn can be embedded into the Haar wavelet spaces with the same set of parameters. Therefore our upper error bounds on Haar wavelet spaces for QMC cubatures based on (t,m,s)(t,m,s)(t,m,s)-nets transfer (with possibly different constants) to the corresponding spaces of integrands of fractional smoothness and to Sobolev and Besov spaces of dominating mixed smoothness. Moreover, known lower error bounds for periodic Sobolev and Besov spaces of dominating mixed smoothness show that QMC integration based on arbitrary (t,m,s)(t,m,s)(t,m,s)-nets yields the best possible convergence rate on periodic as well as on non-periodic Sobolev and Besov spaces of dominating smoothness.
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 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/2n^{-1/2}n−1/2 times the L2L_2L2​-norm of the Fourier transform outside a region around the origin, where nnn is the expected number of function evaluations. As corollaries we obtain the order of convergence for the Sobolev spaces HpsH^s_pHps​ 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/2n^{-s-1/2}n−s−1/2 for p≥2p\ge2p≥2, 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/2n^{-1/2}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.