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

DOI10.1016/j.jco.2020.101521zbMath1460.65014arXiv1903.10223OpenAlexW3093331194MaRDI QIDQ1996887

Sebastian Mayer, Benjamin Doerr

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

lower boundsrandomized algorithmsridge functionsinformation-based complexityhigh-dimensional function approximation

Mathematics Subject Classification ID

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

Related Items (2)

On recovery of regular ridge functions ⋮ Recovery of regular ridge functions on the ball

Uses Software

• ElemStatLearn

Cites Work

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

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