The recovery of ridge functions on the hypercube suffers from the curse of dimensionality

DOI10.1016/J.JCO.2020.101521MaRDI QIDQ1996887zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Sebastian Mayer

Publication date 26 February 2021

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.10223

zbMATH Keywords

randomized algorithmslower boundshigh-dimensional function approximationinformation-based complexityridge functions

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Multidimensional problems (41A63) Approximation by other special function classes (41A30) Algorithms for approximation of functions (65D15)

Abstract: A multivariate ridge function is a function of the form $f(x)=g(a^{scriptscriptstyleT}x)$, where $g$ is univariate and $ainmathbb{R}^d$. We show that the recovery of an unknown ridge function defined on the hypercube $[-1,1{]}^d$ with Lipschitz-regular profile $g$ suffers from the curse of dimensionality when the recovery error is measured in the $L_{i}nfty$-norm, even if we allow randomized algorithms. If a limited number of components of $a$ is substantially larger than the others, then the curse of dimensionality is not present and the problem is weakly tractable provided the profile $g$ is sufficiently regular.

Recommendations

• On some aspects of approximation of ridge functions
• Entropy and sampling numbers of classes of ridge functions
• Capturing ridge functions in high dimensions from point queries
• Approximation of generalized ridge functions in high dimensions
• Recovery algorithms for high-dimensional rank one tensors

Cites work

• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 477682 (Why is no real title available?)
• scientific article; zbMATH DE number 1404611 (Why is no real title available?)
• scientific article; zbMATH DE number 1405266 (Why is no real title available?)
• A mathematical introduction to compressive sensing
• Approximation of high-dimensional rank one tensors
• Approximation of infinitely differentiable multivariate functions is intractable
• Asymptotic minimax estimation of regression in the additive model
• Capturing ridge functions in high dimensions from point queries
• Consistent Estimation of Scaled Coefficients
• Direct estimation of the index coefficient in a single-index model
• Entropy and sampling numbers of classes of ridge functions
• Harmonic analysis of neural networks
• Identifying linear combinations of ridge functions
• Learning functions of few arbitrary linear parameters in high dimensions
• Learning non-parametric basis independent models from point queries via low-rank methods
• Lower bounds for the complexity of Monte Carlo function approximation
• Minimax-optimal rates for sparse additive models over kernel classes via convex programming
• Neural Network Learning
• Nonparametric and semiparametric models.
• Notes on \((s,t)\)-weak tractability: a refined classification of problems with (sub)exponential information complexity
• On projection pursuit regression
• On some aspects of approximation of ridge functions
• On the approximate calculation of multiple integrals
• Optimal smoothing in single-index models
• Orthonormal Ridgelets and Linear Singularities
• Projection pursuit
• Quasi-polynomial tractability
• Ridge functions
• Ridgelets: estimating with ridge functions
• Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach
• Semiparametric Estimation of Index Coefficients
• The EFM approach for single-index models
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Tractability of multivariate problems. Volume III: Standard information for operators
• Tractability of the approximation of high-dimensional rank one tensors
• Uniform weak tractability

Cited in

(6)

• On recovery of regular ridge functions
• Capturing ridge functions in high dimensions from point queries
• Recovery of regular ridge functions on the ball
• On some aspects of approximation of ridge functions
• Entropy and sampling numbers of classes of ridge functions
• On the representability of a continuous multivariate function by sums of ridge functions

Describes a project that uses

Uses Software

• ElemStatLearn

This page was built for publication: The recovery of ridge functions on the hypercube suffers from the curse of dimensionality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1996887)