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:1507.06853

A Universal Algorithm for Multivariate Integration

David Krieg, Erich Novak

Published Jan 1, 2015• 2 citations
arXivHTMLPDF

Abstract

We present an algorithm for multivariate integration over cubes that is unbiased and has optimal order of convergence (in the randomized sense as well as in the worst case setting) for all Sobolev spaces $H^{r, mix}([0,1]^d)$ and $H^s([0,1]^d)$ for $s>d/2$.

DOI
10.13140/rg.2.1.2411.8885

Related papers

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

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

Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces

Frances Y. Kuo

Journal of Complexity•Mar 25, 2003•156 citations

Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces

Josef Dick, Friedrich Pillichshammer

Journal of Complexity•Nov 12, 2004•92 citations

Randomized sparse grid algorithms for multivariate integration on Haar wavelet spaces

M Wnuk, Michael Gnewuch

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.

arXiv:2001.08558•IMA Journal of Numerical Analysis•Dec 1, 2021•2 citations

An Algorithm-Driven Approach to Error Analysis for Multidimensional Integration

Fred J. Hickernell, Josef Dick

Most error analyses for numerical integration algorithms specify the space of integrands and then determine the convergence rate for a particular algorithm or the optimal algorithm. This article takes a different perspective of specifying the convergence rate and then finding the largest space of integrands for which the algorithm gives that desired rate. Both worst-case and randomized error analyses are provided.

International Journal of Numerical Analysis and Modeling•May 1, 2008•2 citations
We present an algorithm for multivariate integration over cubes that is unbiased and has optimal order of convergence (in the randomized sense as well as in the worst case setting) for all Sobolev spaces Hr,mix([0,1]d)H^{r, mix}([0,1]^d)Hr,mix([0,1]d) and Hs([0,1]d)H^s([0,1]^d)Hs([0,1]d) for s>d/2s>d/2s>d/2.
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 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.
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.