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

On the Randomization of Frolov's Algorithm for Multivariate Integration

David Krieg

Published Mar 15, 2016• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1603.04637

Related papers

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

L2-approximation using randomized lattice algorithms

Mou Cai, Takashi Goda, Yoshihito Kazashi

We propose a randomized lattice algorithm for approximating multivariate periodic functions over the d -dimensional unit cube from the weighted Korobov space with mixed smoothness α > 1 / 2 and product weights γ 1 , γ 2 , … ∈ [ 0 , 1 ] . Building upon the deterministic lattice algorithm by Kuo et al. (2006), we incorporate a randomized quadrature rule by Dick et al. (2022) to accelerate the convergence rate. This randomization involves drawing the number of points for function evaluations randomly, and selecting a good generating vector for rank-1 lattice points using the randomized component-by-component algorithm. We prove that our randomized algorithm achieves a worst-case root mean squared L 2 -approximation error of order ɛ M − α ( 2 α + 1 ) / ( 4 α + 1 ) + ɛ for an arbitrarily small ɛ ɛ > 0 , where M denotes the maximum number of function evaluations, and that the error bound is independent of the dimension d if the weights satisfy ∑ j = 1 ∞ γ j 1 / α < ∞ . Our upper bound converges faster than a lower bound on the worst-case L 2 -approximation error for deterministic rank-1 lattice-based approximation proved by Byrenheid et al. (2017). We also show a lower error bound of order M − α / 2 − 1 / 2 for our randomized algorithm, leaving a slight gap between the upper and lower bounds open for future research.

arXiv:2409.18757•Journal of Approximation Theory•Apr 1, 2026•7 citations

Richardson Extrapolation of Polynomial Lattice Rules

Josef Dick, Takashi Goda, Takehito Yoshiki

We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness $\alpha\geq 2$ defined over the $s$-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named the extrapolated polynomial lattice rule, which achieves the almost optimal rate of convergence. Extrapolated polynomial lattice rules are constructed in two steps: (i) construction of classical polynomial lattice rules over $\Bbb{F}_b$ with $\alpha$ consecutive sizes of nodes, $b^{m-\alpha+1},\ldots,b^{m}$, and (ii) recursive application of Richardson extrapolation to a chain of $\alpha$ approximate values of the integral obtained by consecutive polynomial lattice rules. We prove the existence of good extrapolated polynomial lattice rules achieving the almost optimal order of convergence of the worst-case error in Sobolev spaces with general weights. Then, by restricting to product weights, we show that such good extrapolated polynomial lattice rules can be constructed by the fast component-by-component algorithm under a computable quality criterion. The required total construction cost is of order $(s+\alpha)N\log N$, which improves the currently known result for the interlaced polynomial lattice rule, which is of order $s\alpha N\log N$. We also study the dependence of the worst-case error bound on the dimension. A big advantage of our method compared to interlaced polynomial lattice rules is that the fast QMC matrix vector method can be used in this setting, while still achieving the same rate of convergence. Such a method was previously not known. Numerical experiments for test integrands support our theoretical result.

arXiv:1707.03989•SIAM Journal on Numerical Analysis•Jan 1, 2019•10 citations

A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with $0 < α\le 1/2$

Dirk Nuyens, Laurence Wilkes

In previous work (Kuo, Nuyens, Wilkes, 2023), we showed that a lattice rule with a pre-determined generating vector but random number of points can achieve the near optimal convergence of $O(n^{-α-1/2+ε})$, $ε> 0$, for the worst case expected error, commonly referred to as the randomised error, for numerical integration of high-dimensional functions in the Korobov space with smoothness $α> 1/2$. Compared to the optimal deterministic rate of $O(n^{-α+ε})$, $ε> 0$, such a randomised algorithm is capable of an extra half in the rate of convergence. In this paper, we show that a pre-determined generating vector also exists in the case of $0 < α\le 1/2$. Also here we obtain the near optimal convergence of $O(n^{-α-1/2+ε})$, $ε> 0$; or in more detail, we obtain $O(\sqrt{r} \, n^{-α-1/2+1/(2r)+ε'})$ which holds for any choices of $ε' > 0$ and $r \in \mathbb{N}$ with $r > 1/(2α)$.

arXiv:2308.03138•Aug 6, 2023•2 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

Lattice rules and beyond..

Dirk Nuyens

In this talk I will show the beautiful simplicity of approximating high-dimensional integrals using lattice rules. In current engineering applications it is relatively easy to come up with very high and ultra high dimensional integrals, which might be expectations, that depend on hundreds, thousands, or even an infinite number of variables. As the minimal non-trivial tensor product rule, constructed from a 2-point rule, in 100 dimensions already uses 2^{100} = 1267650600228229401496703205376 ≈ 10^{30} function evaluations—which would take 10^{24} seconds at 1 function evaluation per microsecond and we remember the age of the universe to be only approximately 10^{17} seconds—we all know why to use Monte Carlo or quasi-Monte Carlo methods where we can freely choose the number of function evaluations independent of the number of dimensions. While plain vanilla Monte Carlo methods are very robust and easy to apply, in the case of quasi-Monte Carlo methods a lot more details can pop up. I will first introduce the most elegant—in my biased opinion, which I will defend—of all quasi-Monte Carlo methods: the rank-1 lattice rule. This method is defined by one single integer generating vector together with the total number of points in the rule. Approximating a multivariate integral by this method can be done in one line of Matlab code! As one is often interested in successive approximations I will next introduce a rank-1 lattice sequence. Maybe surprisingly, also here, one simple line of Matlab code is sufficient to calculate a segment of a lattice sequence (with a special property). While for Monte Carlo integration the usual assumption is L2 integrability, leading to an error bound of O(N^{−1/2}). For quasi-Monte Carlo methods we generally work with more involved function space settings, leading to error bounds of the form O(N^{−α}) with α ≥ 1/2. I will show the standard function space settings and dive into the weighted function spaces which are being used in current theory to be able to make the error bounds independent of the number of dimensions. We will gloss over the Korobov space of periodic smooth functions, the unanchored Sobolev space with first mixed derivatives, and the cosine space which is a special space of smooth non-periodic functions. All of which are spaces of so-called mixed dominating smoothness, which in terms of mixed derivatives would mean ∂^{k_1+···+k_s} /(∂x_1^{k_1} · · · ∂x_s^{k_s}) exists for all (k_1, . . . , k_s) ≤ (α, . . . , α). For non-periodic function spaces lattice rules and sequences can only reach O(N^{−1}) convergence. To arrive at higher-order convergence of O(N^{−α}) for non-periodic functions we dive into higher-order Sobolev spaces (of mixed dominating smoothness) in combination with digital nets, but here disguised as a lattice rule, namely polynomial lattice rules. Here, all arithmetic is over a finite field (we will choose the one of order 2) and our lattice rules now take the form of a lattice of polynomials which we map back to points in the unit cube. Higher order can now be obtained by means of the interlacing method from Josef Dick. Although more complicated, again, given the generating matrices of the digital net (as a bunch of integers), and two lines for a magical de Bruijn sequence, we can approximate an integral by such a digital sequence with a single line of (complicated) Matlab code. While Matlab/Octave one-liners might be fun, and somehow instructive, I will also point you to my online resources where code is available to (a) construct good lattice rules, lattice sequences and polynomial lattice rules (for product, order-dependent, product-and-order-dependent aka POD, and smoothness-driven product-and-order dependent aka SPOD) weighted spaces, and (b) generate points given the generating vector or matrices. Armed with this software you will be able to attack your own problems in no time. This talk is based upon the results of collaborations with many colleagues.

•Aug 1, 2016•0 citations
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.
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 propose a randomized lattice algorithm for approximating multivariate periodic functions over the d -dimensional unit cube from the weighted Korobov space with mixed smoothness α > 1 / 2 and product weights γ 1 , γ 2 , … ∈ [ 0 , 1 ] . Building upon the deterministic lattice algorithm by Kuo et al. (2006), we incorporate a randomized quadrature rule by Dick et al. (2022) to accelerate the convergence rate. This randomization involves drawing the number of points for function evaluations randomly, and selecting a good generating vector for rank-1 lattice points using the randomized component-by-component algorithm. We prove that our randomized algorithm achieves a worst-case root mean squared L 2 -approximation error of order ɛ M − α ( 2 α + 1 ) / ( 4 α + 1 ) + ɛ for an arbitrarily small ɛ ɛ > 0 , where M denotes the maximum number of function evaluations, and that the error bound is independent of the dimension d if the weights satisfy ∑ j = 1 ∞ γ j 1 / α < ∞ . Our upper bound converges faster than a lower bound on the worst-case L 2 -approximation error for deterministic rank-1 lattice-based approximation proved by Byrenheid et al. (2017). We also show a lower error bound of order M − α / 2 − 1 / 2 for our randomized algorithm, leaving a slight gap between the upper and lower bounds open for future research.
We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness α≥2\alpha\geq 2α≥2 defined over the sss-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named the extrapolated polynomial lattice rule, which achieves the almost optimal rate of convergence. Extrapolated polynomial lattice rules are constructed in two steps: (i) construction of classical polynomial lattice rules over Fb\Bbb{F}_bFb​ with α\alphaα consecutive sizes of nodes, bm−α+1,…,bmb^{m-\alpha+1},\ldots,b^{m}bm−α+1,…,bm, and (ii) recursive application of Richardson extrapolation to a chain of α\alphaα approximate values of the integral obtained by consecutive polynomial lattice rules. We prove the existence of good extrapolated polynomial lattice rules achieving the almost optimal order of convergence of the worst-case error in Sobolev spaces with general weights. Then, by restricting to product weights, we show that such good extrapolated polynomial lattice rules can be constructed by the fast component-by-component algorithm under a computable quality criterion. The required total construction cost is of order (s+α)Nlog⁡N(s+\alpha)N\log N(s+α)NlogN, which improves the currently known result for the interlaced polynomial lattice rule, which is of order sαNlog⁡Ns\alpha N\log NsαNlogN. We also study the dependence of the worst-case error bound on the dimension. A big advantage of our method compared to interlaced polynomial lattice rules is that the fast QMC matrix vector method can be used in this setting, while still achieving the same rate of convergence. Such a method was previously not known. Numerical experiments for test integrands support our theoretical result.
A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with 0<α≤1/20 < α\le 1/20<α≤1/2
In previous work (Kuo, Nuyens, Wilkes, 2023), we showed that a lattice rule with a pre-determined generating vector but random number of points can achieve the near optimal convergence of O(n−α−1/2+ε)O(n^{-α-1/2+ε})O(n−α−1/2+ε), ε>0ε> 0ε>0, for the worst case expected error, commonly referred to as the randomised error, for numerical integration of high-dimensional functions in the Korobov space with smoothness α>1/2α> 1/2α>1/2. Compared to the optimal deterministic rate of O(n−α+ε)O(n^{-α+ε})O(n−α+ε), ε>0ε> 0ε>0, such a randomised algorithm is capable of an extra half in the rate of convergence. In this paper, we show that a pre-determined generating vector also exists in the case of 0<α≤1/20 < α\le 1/20<α≤1/2. Also here we obtain the near optimal convergence of O(n−α−1/2+ε)O(n^{-α-1/2+ε})O(n−α−1/2+ε), ε>0ε> 0ε>0; or in more detail, we obtain O(r n−α−1/2+1/(2r)+ε′)O(\sqrt{r} \, n^{-α-1/2+1/(2r)+ε'})O(r​n−α−1/2+1/(2r)+ε′) which holds for any choices of ε′>0ε' > 0ε′>0 and r∈Nr \in \mathbb{N}r∈N with r>1/(2α)r > 1/(2α)r>1/(2α).
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.
In this talk I will show the beautiful simplicity of approximating high-dimensional integrals using lattice rules. In current engineering applications it is relatively easy to come up with very high and ultra high dimensional integrals, which might be expectations, that depend on hundreds, thousands, or even an infinite number of variables. As the minimal non-trivial tensor product rule, constructed from a 2-point rule, in 100 dimensions already uses 2^{100} = 1267650600228229401496703205376 ≈ 10^{30} function evaluations—which would take 10^{24} seconds at 1 function evaluation per microsecond and we remember the age of the universe to be only approximately 10^{17} seconds—we all know why to use Monte Carlo or quasi-Monte Carlo methods where we can freely choose the number of function evaluations independent of the number of dimensions. While plain vanilla Monte Carlo methods are very robust and easy to apply, in the case of quasi-Monte Carlo methods a lot more details can pop up. I will first introduce the most elegant—in my biased opinion, which I will defend—of all quasi-Monte Carlo methods: the rank-1 lattice rule. This method is defined by one single integer generating vector together with the total number of points in the rule. Approximating a multivariate integral by this method can be done in one line of Matlab code! As one is often interested in successive approximations I will next introduce a rank-1 lattice sequence. Maybe surprisingly, also here, one simple line of Matlab code is sufficient to calculate a segment of a lattice sequence (with a special property). While for Monte Carlo integration the usual assumption is L2 integrability, leading to an error bound of O(N^{−1/2}). For quasi-Monte Carlo methods we generally work with more involved function space settings, leading to error bounds of the form O(N^{−α}) with α ≥ 1/2. I will show the standard function space settings and dive into the weighted function spaces which are being used in current theory to be able to make the error bounds independent of the number of dimensions. We will gloss over the Korobov space of periodic smooth functions, the unanchored Sobolev space with first mixed derivatives, and the cosine space which is a special space of smooth non-periodic functions. All of which are spaces of so-called mixed dominating smoothness, which in terms of mixed derivatives would mean ∂^{k_1+···+k_s} /(∂x_1^{k_1} · · · ∂x_s^{k_s}) exists for all (k_1, . . . , k_s) ≤ (α, . . . , α). For non-periodic function spaces lattice rules and sequences can only reach O(N^{−1}) convergence. To arrive at higher-order convergence of O(N^{−α}) for non-periodic functions we dive into higher-order Sobolev spaces (of mixed dominating smoothness) in combination with digital nets, but here disguised as a lattice rule, namely polynomial lattice rules. Here, all arithmetic is over a finite field (we will choose the one of order 2) and our lattice rules now take the form of a lattice of polynomials which we map back to points in the unit cube. Higher order can now be obtained by means of the interlacing method from Josef Dick. Although more complicated, again, given the generating matrices of the digital net (as a bunch of integers), and two lines for a magical de Bruijn sequence, we can approximate an integral by such a digital sequence with a single line of (complicated) Matlab code. While Matlab/Octave one-liners might be fun, and somehow instructive, I will also point you to my online resources where code is available to (a) construct good lattice rules, lattice sequences and polynomial lattice rules (for product, order-dependent, product-and-order-dependent aka POD, and smoothness-driven product-and-order dependent aka SPOD) weighted spaces, and (b) generate points given the generating vector or matrices. Armed with this software you will be able to attack your own problems in no time. This talk is based upon the results of collaborations with many colleagues.