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:1209.0882 · SIAM Journal on Numerical Analysis

Optimal Randomized Multilevel Algorithms for Infinite-Dimensional Integration on Function Spaces with ANOVA-Type Decomposition

Jan Baldeaux, Michael Gnewuch

Published Jan 1, 2014• 25 citations
arXivHTMLPDF

Abstract

In this paper, we consider the infinite-dimensional integration problem on weighted reproducing kernel Hilbert spaces with norms induced by an underlying function space decomposition of analysis of variance type. The weights model the relative importance of different groups of variables. We present new randomized multilevel algorithms to tackle this integration problem and prove upper bounds for their randomized error. Furthermore, we provide in this setting the first nontrivial lower error bounds for general randomized algorithms, which, in particular, may be adaptive or nonlinear. These lower bounds show that our multilevel algorithms are optimal. Our analysis refines and extends the analysis provided in [F. J. Hickernell, T. Müller-Gronbach, B. Niu, and K. Ritter, J. Complexity, 26 (2010), pp. 229--254], and our error bounds improve substantially on the error bounds presented there. As an illustrative example, we discuss the unanchored Sobolev space and employ randomized quasi--Monte Carlo multilevel algorithms based on scrambled polynomial lattice rules.

DOI
10.1137/120896001

Related papers

Optimal randomized multilevel algorithms for infinitedimensional integration on function spaces with ANOVA-type decomposition

Jan F. Baldeaux, Michael Gnewuch

In this paper, we consider the infinite-dimensional integration problem on weighted reproducing kernel Hilbert spaces with norms induced by an underlying function space decomposition of analysis of variance type. The weights model the relative importance of different groups of variables. We present new randomized multilevel algorithms to tackle this integration problem and prove upper bounds for their randomized error. Furthermore, we provide in this setting the first nontrivial lower error bounds for general randomized algorithms, which, in particular, may be adaptive or nonlinear. These lower bounds show that our multilevel algorithms are optimal. Our analysis refines and extends the analysis provided in [F. J. Hickernell, T. Müller-Gronbach, B. Niu, and K. Ritter, J. Complexity, 26 (2010), pp. 229--254], and our error bounds improve substantially on the error bounds presented there. As an illustrative example, we discuss the unanchored Sobolev space and employ randomized quasi--Monte Carlo multilevel algorithms based on scrambled polynomial lattice rules.

•Aug 17, 2016•27 citations

Infinite-dimensional integration on weighted Hilbert spaces

Michael Gnewuch

We study the numerical integration problem for functions with infinitely many variables which stem from a weighted reproducing kernel Hilbert space. We study the worst case ε \varepsilon -complexity which is defined as the minimal cost among all algorithms whose worst case error over the Hilbert space unit ball is at most ε \varepsilon . Here we assume that the cost of evaluating a function depends polynomially on the number of active variables. The infinite-dimensional integration problem is tractable if the ε \varepsilon -complexity is bounded by a constant times a power of 1 / ε 1/\varepsilon . The smallest such power is called the exponent of tractability. We provide improved lower bounds for the exponent of tractability for general finite-order weights and, with the help of multilevel algorithms, improved upper bounds for three newly defined classes of finite-order weights. The newly defined finite-intersection weights model the situation where each group of variables interacts with at most ρ \rho other groups of variables, ρ \rho some fixed number. For these weights we obtain sharp upper bounds for any decay of the weights and any polynomial degree of the cost function. For the other two classes of finite-order weights our upper bounds are sharp if, e.g., the decay of the weights is fast or slow enough. Furthermore, we deduce a lower bound for the exponent of tractability for arbitrary weights and a constructive upper bound for product weights.

Mathematics of Computation•Apr 5, 2012•38 citations

On quasi-Monte Carlo methods in weighted ANOVA spaces

Peter Kritzer, Friedrich Pillichshammer, G.W. Wasilkowski

In the present paper we study quasi-Monte Carlo rules for approximating integrals over the $d$-dimensional unit cube for functions from weighted Sobolev spaces of regularity one. While the properties of these rules are well understood for anchored Sobolev spaces, this is not the case for the ANOVA spaces, which are another very important type of reference spaces for quasi-Monte Carlo rules. Using a direct approach we provide a formula for the worst case error of quasi-Monte Carlo rules for functions from weighted ANOVA spaces. As a consequence we bound the worst case error from above in terms of weighted discrepancy of the employed integration nodes. On the other hand we also obtain a general lower bound in terms of the number $n$ of used integration nodes. For the one-dimensional case our results lead to the optimal integration rule and also in the two-dimensional case we provide rules yielding optimal convergence rates.

arXiv:2001.05765•Mathematics of Computation•Nov 18, 2020•1 citation

The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension

Fred J. Hickernell, Xiaoqun Wang

Dimensionally unbounded problems are frequently encountered in practice, such as in simulations of stochastic processes, in particle and light transport problems and in the problems of mathematical finance. This paper considers quasi-Monte Carlo integration algorithms for weighted classes of functions of infinitely many variables, in which the dependence of functions on successive variables is increasingly limited. The dependence is modeled by a sequence of weights. The integrands belong to rather general reproducing kernel Hilbert spaces that can be decomposed as the direct sum of a series of their subspaces, each subspace containing functions of only a finite number of variables. The theory of reproducing kernels is used to derive a quadrature error bound, which is the product of two terms: the generalized discrepancy and the generalized variation. Tractability means that the minimal number of function evaluations needed to reduce the initial integration error by a factor ε \varepsilon is bounded by C ε − p C \varepsilon ^{-p} for some exponent p p and some positive constant C C . The ε \varepsilon -exponent of tractability is defined as the smallest power of ε − 1 \varepsilon ^{-1} in these bounds. It is shown by using Monte Carlo quadrature that the ε \varepsilon -exponent is no greater than 2 for these weighted classes of integrands. Under a somewhat stronger assumption on the weights and for a popular choice of the reproducing kernel it is shown constructively using the Halton sequence that the ε \varepsilon -exponent of tractability is 1, which implies that infinite dimensional integration is no harder than one-dimensional integration.

Mathematics of Computation•Aug 2, 2001•61 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

Constructive approaches to quasi-Monte Carlo methods for multiple integration

Frances Y. Kuo

Recently, quasi-Monte Carlo methods have been successfully used for approximating multiple integrals in hundreds of dimensions in mathematical finance, and were significantly more efficient than Monte Carlo methods. To understand the apparent success of quasi-Monte Carlo methods for multiple integration, one popular approach is to study worst-case error bounds in weighted function spaces in which the importance of the variables is moderated by some sequences of weights. Ideally, a family of quasi-Monte Carlo methods in some weighted function space should be strongly tractable. Strong tractability means that the minimal number of quadrature points n needed to reduce the initial error by a factor of ε is bounded by a polynomial in ε⁻¹ independently of the dimension d. Several recent publications show the existence of lattice rules that satisfy the strong tractability error bounds in weighted Korobov spaces of periodic integrands and weighted Sobolev spaces of non-periodic integrands. However, those results were non-constructive and thus give no clues as to how to actually construct these lattice rules. In this thesis, we focus on the construction of quasi-Monte Carlo methods that are strongly tractable. We develop and justify algorithms for the construction of lattice rules that achieve strong tractability error bounds in weighted Korobov and Sobolev spaces. The parameters characterizing these lattice rules are found ‘component-by-component’: the (d + 1)-th components are obtained by successive 1-dimensional searches, with the previous d components kept unchanged. The cost of these algorithms vary from O(nd²) to O(n³d²) operations. With currently available technology, they allow construction of rules easily with values of n up to several million and dimensions d up to several hundred.

•Jan 1, 2002•2 citations
In this paper, we consider the infinite-dimensional integration problem on weighted reproducing kernel Hilbert spaces with norms induced by an underlying function space decomposition of analysis of variance type. The weights model the relative importance of different groups of variables. We present new randomized multilevel algorithms to tackle this integration problem and prove upper bounds for their randomized error. Furthermore, we provide in this setting the first nontrivial lower error bounds for general randomized algorithms, which, in particular, may be adaptive or nonlinear. These lower bounds show that our multilevel algorithms are optimal. Our analysis refines and extends the analysis provided in [F. J. Hickernell, T. Müller-Gronbach, B. Niu, and K. Ritter, J. Complexity, 26 (2010), pp. 229--254], and our error bounds improve substantially on the error bounds presented there. As an illustrative example, we discuss the unanchored Sobolev space and employ randomized quasi--Monte Carlo multilevel algorithms based on scrambled polynomial lattice rules.
In this paper, we consider the infinite-dimensional integration problem on weighted reproducing kernel Hilbert spaces with norms induced by an underlying function space decomposition of analysis of variance type. The weights model the relative importance of different groups of variables. We present new randomized multilevel algorithms to tackle this integration problem and prove upper bounds for their randomized error. Furthermore, we provide in this setting the first nontrivial lower error bounds for general randomized algorithms, which, in particular, may be adaptive or nonlinear. These lower bounds show that our multilevel algorithms are optimal. Our analysis refines and extends the analysis provided in [F. J. Hickernell, T. Müller-Gronbach, B. Niu, and K. Ritter, J. Complexity, 26 (2010), pp. 229--254], and our error bounds improve substantially on the error bounds presented there. As an illustrative example, we discuss the unanchored Sobolev space and employ randomized quasi--Monte Carlo multilevel algorithms based on scrambled polynomial lattice rules.
We study the numerical integration problem for functions with infinitely many variables which stem from a weighted reproducing kernel Hilbert space. We study the worst case ε \varepsilon -complexity which is defined as the minimal cost among all algorithms whose worst case error over the Hilbert space unit ball is at most ε \varepsilon . Here we assume that the cost of evaluating a function depends polynomially on the number of active variables. The infinite-dimensional integration problem is tractable if the ε \varepsilon -complexity is bounded by a constant times a power of 1 / ε 1/\varepsilon . The smallest such power is called the exponent of tractability. We provide improved lower bounds for the exponent of tractability for general finite-order weights and, with the help of multilevel algorithms, improved upper bounds for three newly defined classes of finite-order weights. The newly defined finite-intersection weights model the situation where each group of variables interacts with at most ρ \rho other groups of variables, ρ \rho some fixed number. For these weights we obtain sharp upper bounds for any decay of the weights and any polynomial degree of the cost function. For the other two classes of finite-order weights our upper bounds are sharp if, e.g., the decay of the weights is fast or slow enough. Furthermore, we deduce a lower bound for the exponent of tractability for arbitrary weights and a constructive upper bound for product weights.
In the present paper we study quasi-Monte Carlo rules for approximating integrals over the ddd-dimensional unit cube for functions from weighted Sobolev spaces of regularity one. While the properties of these rules are well understood for anchored Sobolev spaces, this is not the case for the ANOVA spaces, which are another very important type of reference spaces for quasi-Monte Carlo rules. Using a direct approach we provide a formula for the worst case error of quasi-Monte Carlo rules for functions from weighted ANOVA spaces. As a consequence we bound the worst case error from above in terms of weighted discrepancy of the employed integration nodes. On the other hand we also obtain a general lower bound in terms of the number nnn of used integration nodes. For the one-dimensional case our results lead to the optimal integration rule and also in the two-dimensional case we provide rules yielding optimal convergence rates.
Dimensionally unbounded problems are frequently encountered in practice, such as in simulations of stochastic processes, in particle and light transport problems and in the problems of mathematical finance. This paper considers quasi-Monte Carlo integration algorithms for weighted classes of functions of infinitely many variables, in which the dependence of functions on successive variables is increasingly limited. The dependence is modeled by a sequence of weights. The integrands belong to rather general reproducing kernel Hilbert spaces that can be decomposed as the direct sum of a series of their subspaces, each subspace containing functions of only a finite number of variables. The theory of reproducing kernels is used to derive a quadrature error bound, which is the product of two terms: the generalized discrepancy and the generalized variation. Tractability means that the minimal number of function evaluations needed to reduce the initial integration error by a factor ε \varepsilon is bounded by C ε − p C \varepsilon ^{-p} for some exponent p p and some positive constant C C . The ε \varepsilon -exponent of tractability is defined as the smallest power of ε − 1 \varepsilon ^{-1} in these bounds. It is shown by using Monte Carlo quadrature that the ε \varepsilon -exponent is no greater than 2 for these weighted classes of integrands. Under a somewhat stronger assumption on the weights and for a popular choice of the reproducing kernel it is shown constructively using the Halton sequence that the ε \varepsilon -exponent of tractability is 1, which implies that infinite dimensional integration is no harder than one-dimensional integration.
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.
Recently, quasi-Monte Carlo methods have been successfully used for approximating multiple integrals in hundreds of dimensions in mathematical finance, and were significantly more efficient than Monte Carlo methods. To understand the apparent success of quasi-Monte Carlo methods for multiple integration, one popular approach is to study worst-case error bounds in weighted function spaces in which the importance of the variables is moderated by some sequences of weights. Ideally, a family of quasi-Monte Carlo methods in some weighted function space should be strongly tractable. Strong tractability means that the minimal number of quadrature points n needed to reduce the initial error by a factor of ε is bounded by a polynomial in ε⁻¹ independently of the dimension d. Several recent publications show the existence of lattice rules that satisfy the strong tractability error bounds in weighted Korobov spaces of periodic integrands and weighted Sobolev spaces of non-periodic integrands. However, those results were non-constructive and thus give no clues as to how to actually construct these lattice rules. In this thesis, we focus on the construction of quasi-Monte Carlo methods that are strongly tractable. We develop and justify algorithms for the construction of lattice rules that achieve strong tractability error bounds in weighted Korobov and Sobolev spaces. The parameters characterizing these lattice rules are found ‘component-by-component’: the (d + 1)-th components are obtained by successive 1-dimensional searches, with the previous d components kept unchanged. The cost of these algorithms vary from O(nd²) to O(n³d²) operations. With currently available technology, they allow construction of rules easily with values of n up to several million and dimensions d up to several hundred.