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

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

Arthur G. Werschulz, Henryk Woźniakowski

Published Jan 1, 2008• 1 citation
Publisher

Abstract

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.

DOI
10.7916/d8k362jm

Related papers

Strong tractability of multivariate integration using quasi–Monte Carlo algorithms

Xiaoqun Wang

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 })

Mathematics of Computation•Jun 25, 2002•58 citations

Complexity and tractability of the heat equation

Arthur G. Werschulz

In a previous paper, we developed a general framework for establishing tractability and strong tractability for quasilinear multivariate problems in the worst case setting. One important example of such a problem is the solution of the heat equation ut = ∆u − qu in Id × (0,T), where I is the unit inter- val and T is a maximum time value. This problem is to be solved subject to homogeneous Dirichlet boundary conditions, along with the initial conditions u(·,0) = f over Id. The solution u depends linearly on f, but nonlinearly on q. Here, both f and q are d-variate functions from a reproducing kernel Hilbert space with finite-order weights of order ω. This means that, although d can be arbitrary large, f and q can be decomposed as sums of functions of at most ω variables, with ω independent of d. In this paper, we apply our previous general results to the heat equation. We study both the absolute and normalized error criteria. For either error criterion, we show that the problem is . That is, the number of evaluations of f and q needed to obtain an ε-approximation is polynomial in ε and d, with the degree of the polynomial depending linearly on ω. In addition, we want to know when the problem is strongly tractable, meaning that the dependence is polynomial only in ε, independently of d. We show that if the sum of the weights defining the weighted reproducing kernel Hilbert space is uniformly bounded in d and the integral of the univariate kernel is positive, then the heat equation is strongly tractable

•Jan 1, 2006•1 citation

High-Dimensional Function Approximation: Breaking the Curse with Monte Carlo Methods

Robert J. Kunsch

In this dissertation we study the tractability of the information-based complexity $n(\varepsilon,d)$ for $d$-variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $d$. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the $L_{\infty}$-approximation of certain classes of $C^{\infty}$-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the $L_{\infty}$-approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the $L_1$-approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $\sqrt{d}$ only.

arXiv:1704.08213•Apr 26, 2017•17 citations

Tractability of Multivariate Approximation over a Weighted Unanchored Sobolev Space

Arthur G. Werschulz, H. Woźniakowski

Constructive Approximation•Jul 30, 2009•15 citations

Tractability of multivariate analytic problems

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which $s$-variate problems can be approximated to within $\varepsilon$ by using, say, polynomially many in $s$ and $\varepsilon^{-1}$ function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with $\varepsilon^{-1}$ replaced by $1+\log \varepsilon^{-1}$. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of $s$ and $1+\log \varepsilon^{-1}$. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.

arXiv:1407.1615•De Gruyter eBooks•Jul 25, 2014•22 citations

A note on approximation in weighted Korobov spaces via multiple rank-1 lattices

Mou Cai, Takashi Goda

This paper studies the multivariate approximation of functions in weighted Korobov spaces using multiple rank-1 lattice rules. It has been shown by Kämmerer and Volkmer (2019) that algorithms based on multiple rank-1 lattices achieve the optimal convergence rate for the L ∞ error in Wiener-type spaces, up to logarithmic factors. While this result was translated to weighted Korobov spaces in the recent monograph by Dick, Kritzer, and Pillichshammer (2022), the analysis requires the smoothness parameter α to be greater than 1 and is restricted to product weights. In this paper, we extend this result for multiple rank-1 lattice-based algorithms to the case where 1 / 2 < α ≤ 1 and for general weights, covering a broader range of periodic functions with low smoothness and general relative importance of variables. We also provide a summability condition on the weights to ensure strong polynomial tractability for any α > 1 / 2 . Furthermore, by incorporating random shifts into multiple rank-1 lattice-based algorithms, we prove that the resulting randomized algorithm achieves a nearly optimal convergence rate in terms of the worst-case root mean squared L 2 error, while retaining the same tractability property.

arXiv:2601.20290•Journal of Complexity•May 12, 2026•4 citations
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.
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 })
In a previous paper, we developed a general framework for establishing tractability and strong tractability for quasilinear multivariate problems in the worst case setting. One important example of such a problem is the solution of the heat equation ut = ∆u − qu in Id × (0,T), where I is the unit inter- val and T is a maximum time value. This problem is to be solved subject to homogeneous Dirichlet boundary conditions, along with the initial conditions u(·,0) = f over Id. The solution u depends linearly on f, but nonlinearly on q. Here, both f and q are d-variate functions from a reproducing kernel Hilbert space with finite-order weights of order ω. This means that, although d can be arbitrary large, f and q can be decomposed as sums of functions of at most ω variables, with ω independent of d. In this paper, we apply our previous general results to the heat equation. We study both the absolute and normalized error criteria. For either error criterion, we show that the problem is . That is, the number of evaluations of f and q needed to obtain an ε-approximation is polynomial in ε and d, with the degree of the polynomial depending linearly on ω. In addition, we want to know when the problem is strongly tractable, meaning that the dependence is polynomial only in ε, independently of d. We show that if the sum of the weights defining the weighted reproducing kernel Hilbert space is uniformly bounded in d and the integral of the univariate kernel is positive, then the heat equation is strongly tractable
In this dissertation we study the tractability of the information-based complexity n(ε,d)n(\varepsilon,d)n(ε,d) for ddd-variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance ε>0\varepsilon>0ε>0 the complexity n(ε,d)n(\varepsilon,d)n(ε,d) grows exponentially in ddd. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the L∞L_{\infty}L∞​-approximation of certain classes of C∞C^{\infty}C∞-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the L∞L_{\infty}L∞​-approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the L1L_1L1​-approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance ε>0\varepsilon>0ε>0 the complexity n(ε,d)n(\varepsilon,d)n(ε,d) grows exponentially in d\sqrt{d}d​ only.
In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which sss-variate problems can be approximated to within ε\varepsilonε by using, say, polynomially many in sss and ε−1\varepsilon^{-1}ε−1 function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with ε−1\varepsilon^{-1}ε−1 replaced by 1+log⁡ε−11+\log \varepsilon^{-1}1+logε−1. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of sss and 1+log⁡ε−11+\log \varepsilon^{-1}1+logε−1. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.
This paper studies the multivariate approximation of functions in weighted Korobov spaces using multiple rank-1 lattice rules. It has been shown by Kämmerer and Volkmer (2019) that algorithms based on multiple rank-1 lattices achieve the optimal convergence rate for the L ∞ error in Wiener-type spaces, up to logarithmic factors. While this result was translated to weighted Korobov spaces in the recent monograph by Dick, Kritzer, and Pillichshammer (2022), the analysis requires the smoothness parameter α to be greater than 1 and is restricted to product weights. In this paper, we extend this result for multiple rank-1 lattice-based algorithms to the case where 1 / 2 < α ≤ 1 and for general weights, covering a broader range of periodic functions with low smoothness and general relative importance of variables. We also provide a summability condition on the weights to ensure strong polynomial tractability for any α > 1 / 2 . Furthermore, by incorporating random shifts into multiple rank-1 lattice-based algorithms, we prove that the resulting randomized algorithm achieves a nearly optimal convergence rate in terms of the worst-case root mean squared L 2 error, while retaining the same tractability property.