Approximation of infinitely differentiable multivariate functions is intractable
Let \(F_d\) be a normed linear space of functions \(f:[0,1]^d\to\mathbb R\) that are infinitely differentiable endowed with the norm \(\|f\|_{F_d}=\sup_\alpha \|D^\alpha f\|_\infty<\infty\). Let \(A_{n,d}(f)=\varphi_n(L_1(f),\dots,L_n(f))\), where \(\varphi_n:\mathbb R^n\to L_\infty ([0,1]^d)\) is a linear or non-linear mapping, and \(L_j\) is an arbitrary continuous functional whose choice may depend on the previous values \(L_1(f),\dots,L_{j-1}(f)\). The worst case error of \(A_{n,d}\) is \(e^{\text{wor}}(A_{n,d})=\sup_{\|f\|_{F_d}\leq 1}\|f-A_{n,d}(f)\|_\infty\), and the \(n\)th minimal error is \(e(n,d)=\inf_{A_{n,d}}e^{\text{wor}}(A_{n,d})\). The minimal number of information operations needed to solve the problem to within \(\varepsilon\) is \(n(\varepsilon,d)=\min\{n:e(n,d)\leq \varepsilon\}\). A problem is weakly tractable if \(\lim_{\varepsilon^{-1}+d\to \infty}\ln\,n(\varepsilon,d)/(\varepsilon^{-1}+d)=0\), and intractable when the above relation does not hold. If \(n(\varepsilon,d)\) depends exponentially on \(d\), then it is said that the problem suffers from the curse of dimensionality. Moreover, a problem is polynomially tractable if there exist \(C,p,q>0\) such that \(n(\varepsilon,d) \leq C\varepsilon ^{-p}d^q\), for all \(\varepsilon \in (0,1)\), and \(d\in\mathbb N\). \textit{F. L. Huang} and \textit{S. Zhang} [J. Complexity 23, No.~1, 73--81 (2007; Zbl 1108.41024)] conjectured that this \(L_\infty\)-approximation problem is not polynomially tractable, and this paper is devoted to prove this conjecture and somewhat even stronger: the problem is not weakly tractable. The result is the following: For this problem \(e(n,d)=1\) for all \(n=0,1,\dots,2^{[d/2]}-1\). Therefore \(n(\varepsilon,d)\geq 2^{[d/2]}\) for all \(\varepsilon \in (0,1)\) and \(d\in\mathbb N\), and \(L_\infty\)-approximation is intractable and suffers from the curse of dimensionality.
- Approximation of infinitely differentiable multivariate functions is not strongly tractable
- On best approximation of infinitely differentiable functions
- On best approximation of infinitely differentiable functions
- Exponential convergence of an approximation problem for infinitely differentiable multivariate functions
- Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions
- Best approximations of infinitely differentiable functions in the space \(L_ s\)
- Approximation by Fourier sums of infinitely differentiable functions of several variables
- Approximations of differentiable functions of several variables
- Approximation and Extension in Normed Spaces of Infinitely Differentiable Functions
- scientific article; zbMATH DE number 665379
- An intractability result for multiple integration
- Approximation of infinitely differentiable multivariate functions is not strongly tractable
- Multivariate integration in \(C^{\infty}([0,1]^{d})\) is not strongly tractable.
- Open problems for tractability of multivariate integration.
- Optimal order of convergence and (in)tractability of multivariate approximation of smooth functions
- Tractability of multivariate approximation over a weighted unanchored Sobolev space
- Tractability of multivariate problems. Volume I: Linear information
- Multivariate integration in \(C^{\infty}([0,1]^{d})\) is not strongly tractable.
- Uniform recovery of high-dimensional C^r-functions
- Exponential convergence of an approximation problem for infinitely differentiable multivariate functions
- Tractability of the Fredholm problem of the second kind
- Algorithms and complexity for functions on general domains
- The recovery of ridge functions on the hypercube suffers from the curse of dimensionality
- How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings
- Learning general sparse additive models from point queries in high dimensions
- Efficient approximation of solutions of parametric linear transport equations by ReLU DNNs
- Numerical solution of the parametric diffusion equation by deep neural networks
- Recovery guarantees for polynomial coefficients from weakly dependent data with outliers
- On weak tractability of the Smolyak algorithm for approximation problems
- Sampling numbers of a class of infinitely differentiable functions
- Approximation of generalized ridge functions in high dimensions
- On some aspects of approximation of ridge functions
- \(N\)-widths and \(\varepsilon \)-dimensions for high-dimensional approximations
- Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions
- Approximation numbers of Sobolev embeddings-sharp constants and tractability
- On weak tractability of the Clenshaw-Curtis Smolyak algorithm
- Exponential tractability of \(L_2\)-approximation with function values
- Bernstein numbers and lower bounds for the Monte Carlo error
- The curse of dimensionality for numerical integration of smooth functions
- Tensor-sparsity of solutions to high-dimensional elliptic partial differential equations
- Liberating the dimension for \(L_2\)-approximation
- Learning functions of few arbitrary linear parameters in high dimensions
- Orthogonal polynomial expansions on sparse grids
- Approximation of high-dimensional rank one tensors
- Breaking the curse of dimensionality
- Optimal Lagrange interpolation of a class of infinitely differentiable functions
- Cubature, approximation, and isotropy in the hypercube
- Tractability of the approximation of high-dimensional rank one tensors
- Optimal Reaction Coordinates: Variational Characterization and Sparse Computation
- Neural network approximation and estimation of classifiers with classification boundary in a Barron class
- Approximation of curve-based sleeve functions in high dimensions
- Low dimensional approximation and generalization of multivariate functions on smooth manifolds using deep ReLU neural networks
- Tractability results for weighted Banach spaces of smooth functions
- Compositional sparsity, approximation classes, and parametric transport equations
- Approximation of functions: optimal sampling and complexity
- Dimension-independent learning rates for high-dimensional classification problems
- Learning non-parametric basis independent models from point queries via low-rank methods
- Entropy and sampling numbers of classes of ridge functions
- Optimal order of convergence and (in)tractability of multivariate approximation of smooth functions
- Approximation of infinitely differentiable multivariate functions is not strongly tractable
- Adaptive near-optimal rank tensor approximation for high-dimensional operator equations
This page was built for publication: Approximation of infinitely differentiable multivariate functions is intractable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272156)
