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

Effective Dimension of Some Weighted Pre-Sobolev Spaces with Dominating Mixed Partial Derivatives

Art B. Owen

Published Jan 1, 2019• 12 citations
arXivHTMLPDF

Abstract

This paper considers two notions of effective dimension for quadrature in weighted pre-Sobolev spaces with dominating mixed partial derivatives. We begin by finding a ball in those spaces just barely large enough to contain a function with unit variance. If no function in that ball has more than $\varepsilon$ of its variance from analysis of variance (ANOVA) components involving interactions of order $s$ or more, then the space has effective dimension at most $s$ in the superposition sense. A similar truncation sense notion replaces the cardinality of an ANOVA component by the largest index it contains. These effective dimension definitions for the integration problem coincide with some of the definitions in information-based complexity for the function approximation problem. Some Poincaré-type inequalities are used to bound variance components by multiples of these space's squared norm and those in turn provide bounds on effective dimension. Very low effective dimension in the superposition sense holds for some spaces defined by product weights in which quadrature is strongly tractable. The superposition dimension is $O( \log(1/\varepsilon)/\log(\log(1/\varepsilon)))$ just like the superposition dimension used in the multivariate decomposition method. Surprisingly, even spaces where all subset weights are equal, regardless of their cardinality or included indices, have low superposition dimension in this sense. This paper does not require periodicity of the integrands.

DOI
10.1137/17m1158975

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

Tractability of multivariate approximation over a weighted unanchored Sobolev space: Smoothness sometimes hurts

Arthur G. Werschulz, Henryk Woźniakowski

We study d-variate approximation for a weighted unanchored Sobolev space having smoothness m ≥ 1. Folk wisdom would lead us to believe that this problem should become easier as its smoothness increases. This is true if we are only concerned with asymptotic analysis: the nth minimal error is of order n^-(m-δ) for any δ > 0. However, it is unclear how long we need to wait before this asymptotic behavior kicks in. How does this waiting period depend on d and m? We prove that no matter how the weights are chosen, the waiting period is at least m^d, even if the error demand ε is arbitrarily close to 1. Hence, for m ≥ 2, this waiting period is exponential in d, so that the problem suffers from the curse of dimensionality and is intractable. In other words, the fact that the asymptotic behavior improves with m is irrelevant when d is large. So, we will be unable to vanquish the curse of dimensionality unless m = 1 , i.e., unless the smoothness is minimal. We then show that our problem can be tractable if m = 1. That is, we can find an ε-approximation using polynomially-many (in d and ε^-1) information operations, even if only function values are permitted. When m = 1, it is even possible for the problem to be strongly tractable, i.e., we can find an ε-approximation using polynomially-many (in ε^-1) information operations, independent of d. These positive results hold when the weights of the Sobolev space decay sufficiently quickly or are bounded finite-order weights, i.e., the d-variate functions we wish to approximate can be decomposed as sums of functions depending on at most ω variables, where ω is independent of d.

•Jan 1, 2008•1 citation

Numerical integration in $\log$-Korobov and $\log$-cosine spaces

Josef Dick, Peter Kritzer, Gunther Leobacher +1 more

QMC rules are equal weight quadrature rules for approximating integrals over $[0,1]^s$. One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on $[0,1]^s$ with square integrable partial mixed derivatives of order $α$. Using Parseval's identity, this smoothness can be defined for all real numbers $α> 1/2$. This condition is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with $α$ arbitrarily close to $1/2$. To obtain such estimates we introduce a $\log$-scale for functions with smoothness close to $1/2$, which we call $\log$-Korobov spaces. We show that lattice rules can be used to obtain an integration error of order $\mathcal{O}(N^{-1/2} (\log N)^{-μ(1-λ)/2})$ for any $1/μ<λ\le 1$, where $μ>1$ is a power in the $\log$-scale. We also consider tractability of numerical integration for weighted Korobov spaces with product weights $(γ_j)_{j \in \mathbb{N}}$. It is known that if $\sum_{j=1}^\infty γ_j^τ< \infty$ for some $1/(2α) < τ\le 1$ one can obtain error bounds which are independent of the dimension. In this paper we give a more refined estimate for the case where $τ$ is close to $1/(2 α)$, namely we show dimension independent error bounds under the condition that $\sum_{j=1}^\infty γ_j \max\{1, \log γ_j^{-1}\}^{μ(1-λ)} < \infty$ for some $1/μ< λ\le 1$. The essential tool in our analysis is a $\log$-scale Jensen's inequality. The results described above also apply to integration in $\log$-cosine spaces using tent-transformed lattice rules.

arXiv:1411.2715•Nov 11, 2014•0 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

A gentle introduction to approximating high-dimensional integrals with lattice rules and a maybe-not-so-gentle introduction to the relevant function spaces for QMC integration

Dirk Nuyens

These lecture notes give both a practical and theoretical introduction to high-dimensional integration with lattice rules. We introduce lattice points and rules in combination with accompanying Julia code. Next we introduce the typical function spaces used in the literature. We compare classical Sobolev spaces with Sobolev spaces of dominating mixed smoothness. We derive lower bounds and show that the curse of dimensionality is unavoidable for these unweighted function spaces. Next we switch to weighted periodic spaces and derive a constructive upper bound using the component-by-component construction for the generating vector of a lattice rule. We pick periodic spaces because they are a perfect match with lattice rules. The upper bound shows that under suitable conditions on the weights we obtain dimension-independent worst-case error bounds. We then use embedding constants to transfer these bounds to some common norms for these periodic spaces.

arXiv:2610.25331•Oct 18, 2026•0 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
This paper considers two notions of effective dimension for quadrature in weighted pre-Sobolev spaces with dominating mixed partial derivatives. We begin by finding a ball in those spaces just barely large enough to contain a function with unit variance. If no function in that ball has more than ε\varepsilonε of its variance from analysis of variance (ANOVA) components involving interactions of order sss or more, then the space has effective dimension at most sss in the superposition sense. A similar truncation sense notion replaces the cardinality of an ANOVA component by the largest index it contains. These effective dimension definitions for the integration problem coincide with some of the definitions in information-based complexity for the function approximation problem. Some Poincaré-type inequalities are used to bound variance components by multiples of these space's squared norm and those in turn provide bounds on effective dimension. Very low effective dimension in the superposition sense holds for some spaces defined by product weights in which quadrature is strongly tractable. The superposition dimension is O(log⁡(1/ε)/log⁡(log⁡(1/ε)))O( \log(1/\varepsilon)/\log(\log(1/\varepsilon)))O(log(1/ε)/log(log(1/ε))) just like the superposition dimension used in the multivariate decomposition method. Surprisingly, even spaces where all subset weights are equal, regardless of their cardinality or included indices, have low superposition dimension in this sense. This paper does not require periodicity of the integrands.
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 d-variate approximation for a weighted unanchored Sobolev space having smoothness m ≥ 1. Folk wisdom would lead us to believe that this problem should become easier as its smoothness increases. This is true if we are only concerned with asymptotic analysis: the nth minimal error is of order n^-(m-δ) for any δ > 0. However, it is unclear how long we need to wait before this asymptotic behavior kicks in. How does this waiting period depend on d and m? We prove that no matter how the weights are chosen, the waiting period is at least m^d, even if the error demand ε is arbitrarily close to 1. Hence, for m ≥ 2, this waiting period is exponential in d, so that the problem suffers from the curse of dimensionality and is intractable. In other words, the fact that the asymptotic behavior improves with m is irrelevant when d is large. So, we will be unable to vanquish the curse of dimensionality unless m = 1 , i.e., unless the smoothness is minimal. We then show that our problem can be tractable if m = 1. That is, we can find an ε-approximation using polynomially-many (in d and ε^-1) information operations, even if only function values are permitted. When m = 1, it is even possible for the problem to be strongly tractable, i.e., we can find an ε-approximation using polynomially-many (in ε^-1) information operations, independent of d. These positive results hold when the weights of the Sobolev space decay sufficiently quickly or are bounded finite-order weights, i.e., the d-variate functions we wish to approximate can be decomposed as sums of functions depending on at most ω variables, where ω is independent of d.
Numerical integration in log⁡\loglog-Korobov and log⁡\loglog-cosine spaces
QMC rules are equal weight quadrature rules for approximating integrals over [0,1]s[0,1]^s[0,1]s. One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on [0,1]s[0,1]^s[0,1]s with square integrable partial mixed derivatives of order ααα. Using Parseval's identity, this smoothness can be defined for all real numbers α>1/2α> 1/2α>1/2. This condition is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with ααα arbitrarily close to 1/21/21/2. To obtain such estimates we introduce a log⁡\loglog-scale for functions with smoothness close to 1/21/21/2, which we call log⁡\loglog-Korobov spaces. We show that lattice rules can be used to obtain an integration error of order O(N−1/2(log⁡N)−μ(1−λ)/2)\mathcal{O}(N^{-1/2} (\log N)^{-μ(1-λ)/2})O(N−1/2(logN)−μ(1−λ)/2) for any 1/μ<λ≤11/μ<λ\le 11/μ<λ≤1, where μ>1μ>1μ>1 is a power in the log⁡\loglog-scale. We also consider tractability of numerical integration for weighted Korobov spaces with product weights (γj)j∈N(γ_j)_{j \in \mathbb{N}}(γj​)j∈N​. It is known that if ∑j=1∞γjτ<∞\sum_{j=1}^\infty γ_j^τ< \infty∑j=1∞​γjτ​<∞ for some 1/(2α)<τ≤11/(2α) < τ\le 11/(2α)<τ≤1 one can obtain error bounds which are independent of the dimension. In this paper we give a more refined estimate for the case where τττ is close to 1/(2α)1/(2 α)1/(2α), namely we show dimension independent error bounds under the condition that ∑j=1∞γjmax⁡{1,log⁡γj−1}μ(1−λ)<∞\sum_{j=1}^\infty γ_j \max\{1, \log γ_j^{-1}\}^{μ(1-λ)} < \infty∑j=1∞​γj​max{1,logγj−1​}μ(1−λ)<∞ for some 1/μ<λ≤11/μ< λ\le 11/μ<λ≤1. The essential tool in our analysis is a log⁡\loglog-scale Jensen's inequality. The results described above also apply to integration in log⁡\loglog-cosine spaces using tent-transformed lattice rules.
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.
These lecture notes give both a practical and theoretical introduction to high-dimensional integration with lattice rules. We introduce lattice points and rules in combination with accompanying Julia code. Next we introduce the typical function spaces used in the literature. We compare classical Sobolev spaces with Sobolev spaces of dominating mixed smoothness. We derive lower bounds and show that the curse of dimensionality is unavoidable for these unweighted function spaces. Next we switch to weighted periodic spaces and derive a constructive upper bound using the component-by-component construction for the generating vector of a lattice rule. We pick periodic spaces because they are a perfect match with lattice rules. The upper bound shows that under suitable conditions on the weights we obtain dimension-independent worst-case error bounds. We then use embedding constants to transfer these bounds to some common norms for these periodic spaces.
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.