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

A multivariate ridge function is a function of the form $f(x) = g(a^{\scriptscriptstyle T} x)$, where $g$ is univariate and $a \in \mathbb{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_\infty$-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.

• Publication year

  2019

• Venue

  Journal of Complexity

• Publication date

  2019-03-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.jco.2020.101521arXiv 1903.10223
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Notes on (s, t)-weak tractability: A refined classification of problems with (sub)exponential information complexity

  2015cited by this paper
• A Mathematical Introduction to Compressive Sensing

  2015cited by this paper
• On the approximate calculation of multiple integrals

  2015cited by this paper
• Ridge Functions: Approximation Algorithms

  2015cited by this paper
• Tractability of the Approximation of High-Dimensional Rank One Tensors

  2014cited by this paper
• On some aspects of approximation of ridge functions

  2014cited by this paper
• Uniform weak tractability

  2013cited by this paper
• Approximation of High-Dimensional Rank One Tensors

  2013cited by this paper
• Entropy and Sampling Numbers of Classes of Ridge Functions

  2013cited by this paper
• Learning Non-Parametric Basis Independent Models from Point Queries via Low-Rank Methods

  2013cited by this paper
• An Invitation to Compressive Sensing

  2013influential reference
• Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach

  2012cited by this paper
• Tractability of Multivariate Problems, Volume III: Standard Information for Operators.

  2012cited by this paper
• Consistent estimation of scaled coefficients

  2011cited by this paper
• Quasi-polynomial tractability

  2011cited by this paper
• Capturing Ridge Functions in High Dimensions from Point Queries

  2011influential reference
• The EFM approach for single-index models

  2011cited by this paper
• Minimax-Optimal Rates For Sparse Additive Models Over Kernel Classes Via Convex Programming

  2010cited by this paper
• Tractability of Multivariate Problems Volume II: Standard Information for Functionals

  2010cited by this paper
• Learning Functions of Few Arbitrary Linear Parameters in High Dimensions

  2010cited by this paper
• Approximation of infinitely differentiable multivariate functions is intractable

  2009cited by this paper
• Probabilistic Methods in Combinatorics

  2009cited by this paper
• Tractability of Multivariate Problems

  2008influential reference
• Projection Pursuit for Exploratory Supervised Classification

  2005cited by this paper
• Nonparametric and Semiparametric Models

  2005cited by this paper
• Nonparametric and Semiparametric Models

  2004cited by this paper
• Ridgelets: estimating with ridge functions

  2003cited by this paper
• The Elements of Statistical Learning: Data Mining, Inference, and Prediction

  2001cited by this paper
• Direct estimation of the index coefficient in a single-index model

  2001cited by this paper
• Orthonormal Ridgelets and Linear Singularities

  2000cited by this paper
• Approximation theory of the MLP model in neural networks

  1999cited by this paper
• Neural Network Learning: Theoretical Foundations

  1999cited by this paper
• Harmonic Analysis of Neural Networks

  1999cited by this paper
• Identifying Linear Combinations of Ridge Functions

  1999cited by this paper
• Approximating by Ridge Functions

  1997cited by this paper
• Constructive Approximation

  1993cited by this paper
• Optimal Smoothing in Single-index Models

  1993cited by this paper
• Lower bounds for the complexity of Monte Carlo function approximation

  1992cited by this paper
• On Projection Pursuit Regression

  1989cited by this paper
• Semiparametric Estimation of Index Coefficients

  1989cited by this paper
• Estimation of single index models

  1987cited by this paper
• Projection Pursuit Regression

  1981cited by this paper
• Probabilistic Methods in Combinatorics

  1974cited by this paper
• Approximate calculation of multiple integrals

  1973cited by this paper

• On the representability of a continuous multivariate function by sums of ridge functions

  2024cites this paper
• Recovery of regular ridge functions on the ball

  2021cites this paper
• Spatial prediction of highway slope disasters based on convolution neural networks

  2021cites this paper
• Ridge Functions and Applications in Neural Networks

  2021cites this paper
• A Fully Bayesian Gradient-Free Supervised Dimension Reduction Method using Gaussian Processes

  2020cites this paper