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

Mathematics of Computation

Strong tractability of multivariate integration using quasi–Monte Carlo algorithms

Xiaoqun Wang

Published Jun 25, 2002• 56 citations
Publisher

Abstract

We study quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the ε \varepsilon -exponent of strong tractability is between 1 and 2. However, their proof is not constructive . In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with ε \varepsilon -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta })

DOI
10.1090/s0025-5718-02-01440-0

Related papers

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

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

When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?

Ian H. Sloan, Henryk Woźniakowski

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.

Journal of Complexity•Mar 1, 1998•605 citations

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

On the step-by-step construction of quasi–Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces

Ian H. Sloan, Frances Y. Kuo, Stephen Joe

We develop and justify an algorithm for the construction of quasi–Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. The parameters characterising the shifted lattice rule are found “component-by-component”: the ( d + 1 d+1 )-th component of the generator vector and the shift are obtained by successive 1 1 -dimensional searches, with the previous d d components kept unchanged. The rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for n n -point rules with n n prime and all dimensions 1 to d d requires a total cost of O ( n 3 d 2 ) O(n^3d^2) operations. This may be reduced to O ( n 3 d ) O(n^3d) operations at the expense of O ( n 2 ) O(n^2) storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and n n up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.

Mathematics of Computation•Mar 20, 2002•91 citations

Quasi-Monte Carlo tractability of integration problem in function spaces defined over products of balls

Jie Zhang, Yongping Liu

Recently, quasi-Monte Carlo (QMC) rules for multivariate integration in some weighted Sobolev spaces of functions defined over unit cubes [Formula: see text], products of [Formula: see text] copies of the simplex [Formula: see text] and products of [Formula: see text] copies of the unit sphere [Formula: see text] have been well-studied in the literature. In this paper, we consider QMC tractability of integrals of functions defined over product of [Formula: see text] copies of the ball [Formula: see text]. The space is a tensor product of [Formula: see text] reproducing kernel Hilbert spaces defined by positive and uniformly bounded weights [Formula: see text] for [Formula: see text]. We obtain matching necessary and sufficient conditions in terms of this weights for various notions of QMC tractability, including strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniformly weak tractability and [Formula: see text]-weak tractability.

International Journal of Wavelets Multiresolution and Information Processing•May 12, 2019•3 citations
We study quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the ε \varepsilon -exponent of strong tractability is between 1 and 2. However, their proof is not constructive . In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with ε \varepsilon -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta })
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.
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.
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.
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.
We develop and justify an algorithm for the construction of quasi–Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. The parameters characterising the shifted lattice rule are found “component-by-component”: the ( d + 1 d+1 )-th component of the generator vector and the shift are obtained by successive 1 1 -dimensional searches, with the previous d d components kept unchanged. The rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for n n -point rules with n n prime and all dimensions 1 to d d requires a total cost of O ( n 3 d 2 ) O(n^3d^2) operations. This may be reduced to O ( n 3 d ) O(n^3d) operations at the expense of O ( n 2 ) O(n^2) storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and n n up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.
Recently, quasi-Monte Carlo (QMC) rules for multivariate integration in some weighted Sobolev spaces of functions defined over unit cubes [Formula: see text], products of [Formula: see text] copies of the simplex [Formula: see text] and products of [Formula: see text] copies of the unit sphere [Formula: see text] have been well-studied in the literature. In this paper, we consider QMC tractability of integrals of functions defined over product of [Formula: see text] copies of the ball [Formula: see text]. The space is a tensor product of [Formula: see text] reproducing kernel Hilbert spaces defined by positive and uniformly bounded weights [Formula: see text] for [Formula: see text]. We obtain matching necessary and sufficient conditions in terms of this weights for various notions of QMC tractability, including strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniformly weak tractability and [Formula: see text]-weak tractability.