Approximation and learning by greedy algorithms

We consider the problem of approximating a given element f from a Hilbert space H by means of greedy algorithms and the application of such procedures to the regression problem in statistical learning theory. We improve on the existing theory of convergence rates for both the orthogonal greedy algorithm and the relaxed greedy algorithm, as well as for the forward stepwise projection algorithm. For all these algorithms, we prove convergence results for a variety of function classes and not simply those that are related to the convex hull of the dictionary. We then show how these bounds for convergence rates lead to a new theory for the performance of greedy algorithms in learning. In particular, we build upon the results in [IEEE Trans. Inform. Theory 42 (1996) 2118-2132] to construct learning algorithms based on greedy approximations which are universally consistent and provide provable convergence rates for large classes of functions. The use of greedy algorithms in the context of learning is very appealing since it greatly reduces the computational burden when compared with standard model selection using general dictionaries.

• Publication year

  2008

• Venue

  Annals of Statistics

• Publication date

  2008-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/009053607000000631arXiv 0803.1718
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Sparse regularization in MRI iterative reconstruction using GPUs

  2010influential reference
• On ψ- interpolation spaces

  2009cited by this paper
• Rate of Convergence of Pure Greedy Algorithms

  2004cited by this paper
• [Least Angle Regression]: Discussion

  2004cited by this paper
• Nonlinear Methods of Approximation

  2003cited by this paper
• The Elements of Statistical Learning

  2003cited by this paper
• Comparison of worst case errors in linear and neural network approximation

  2002cited by this paper
• A Distribution-Free Theory of Nonparametric Regression

  2002influential reference
• Greedy algorithms in Banach spaces

  2001influential reference
• Bounds on rates of variable-basis and neural-network approximation

  2001cited by this paper
• Penalized least squares, model selection, convex hull classes and neural nets

  2001cited by this paper
• Two Lower Estimates in Greedy Approximation

  2001influential reference
• Weak greedy algorithms[*]This research was supported by National Science Foundation Grant DMS 9970326 and by ONR Grant N00014‐96‐1‐1003.

  2000cited by this paper
• Approximation by ridge functions and neural networks

  1999cited by this paper
• Minimax estimation via wavelet shrinkage

  1998cited by this paper
• Nonlinear approximation

  1998cited by this paper
• Adaptive greedy approximations

  1997influential reference
• Some remarks on greedy algorithms

  1996influential reference
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• Wavelet Shrinkage: Asymptopia?

  1995cited by this paper
• Universal approximation bounds for superpositions of a sigmoidal function

  1993cited by this paper
• A Simple Lemma on Greedy Approximation in Hilbert Space and Convergence Rates for Projection Pursuit Regression and Neural Network Training

  1992cited by this paper
• Complexity Regularization with Application to Artificial Neural Networks

  1991cited by this paper
• Interpolation of operators

  1987cited by this paper

• Greedy reconstruction algorithms for function approximation

  2026cites this paper
• Barron-Wiener-Laguerre models

  2026cites this paper
• Don't stop me now: Rethinking Validation Criteria for Model Parameter Selection

  2026cites this paper
• Sparse RBF Networks for PDEs and nonlocal equations: function space theory, operator calculus, and training algorithms

  2026cites this paper
• Stochastic convergence of a class of greedy-type algorithms for Configuration Optimization Problems

  2026cites this paper
• Expansive Natural Neural Gradient Flows for Energy Minimization

  2025cites this paper
• Navigating beyond backpropagation: on alternative training methods for deep neural networks

  2025cites this paper
• A New Rational Approximation Algorithm via the Empirical Interpolation Method

  2025cites this paper
• Brief introduction in greedy approximation

  2025cites this paper
• Provable wavelet-based neural approximation

  2025influential citation
• Learning where to learn: Training data distribution optimization for scientific machine learning

  2025cites this paper
• Variationally correct neural residual regression for parametric PDEs: on the viability of controlled accuracy

  2025cites this paper
• Orthogonal greedy algorithm for linear operator learning with shallow neural network

  2025cites this paper
• DPG loss functions for learning parameter-to-solution maps by neural networks

  2025influential citation
• Improving Greedy Algorithms for Rational Approximation

  2025cites this paper
• Integral Representations of Sobolev Spaces via ReLUk Activation Function and Optimal Error Estimates for Linearized Networks

  2025influential citation
• Spectrum Sharing and Interference Management for 6G LEO Satellite-Terrestrial Network Integration

  2025cites this paper
• Constructive Universal Approximation and Sure Convergence for Multi-Layer Neural Networks

  2025influential citation
• Stochastic extended finite element analysis based on sparse polynomial chaos expansion

  2025cites this paper
• On greedy approximation in complex Banach spaces

  2024cites this paper
• Towards optimal hierarchical training of neural networks

  2024cites this paper
• Sensitivity analysis, surrogate modeling, and optimization of pebble-bed reactors considering normal and accident conditions

  2024cites this paper
• The Benefits of Cyclic Refinement Steps of Two-Dimensional Multi-Snapshot Newtonized Orthogonal Matching Pursuit Algorithm

  2024cites this paper
• Rethinking Adversarial Robustness in the Context of the Right to be Forgotten

  2024cites this paper
• A Review of Smart Camera Sensor Placement in Construction

  2024cites this paper
• Sparse Subsurface Sensor Signal Estimation for Formation Damage Assessment via a Smart Orthogonal Matching Pursuit

  2024cites this paper
• A new analysis of empirical interpolation methods and Chebyshev greedy algorithms

  2024cites this paper
• Time Series Forecasting with Many Predictors

  2024cites this paper
• Exploiting Fine-grained Dimming with Improved LiFi Throughput

  2024cites this paper
• Variationally Correct Neural Residual Regression for Parametric PDEs: On the Viability of Controlled Accuracy

  2024cites this paper
• Log-Concave Coupling for Sampling Neural Net Posteriors

  2024cites this paper
• Matrix Pre-orthogonal Matching Pursuit and Pseudo-Inverse

  2024cites this paper
• Dynamic location model for designated COVID-19 hospitals in China.

  2024cites this paper
• Sparse Signal Recovery via Rescaled Matching Pursuit

  2024influential citation
• FC-KAN: Function Combinations in Kolmogorov-Arnold Networks

  2024cites this paper
• Research on the Optimization Strategy of Crop Planting Combining Dynamic Programming and Monte Carlo Simulation

  2024cites this paper
• Randomized Greedy Algorithms for Neural Network Optimization in Solving Partial Differential Equations

  2024cites this paper
• Dynamic DMA Design Methodology Based on Multilevel DMA and Multiobjective Optimization

  2024cites this paper
• Sharp Convergence Rates for Matching Pursuit

  2023cites this paper
• Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networks

  2023cites this paper
• Adaptive piecewise Poly-Sinc methods for function approximation

  2023cites this paper
• Learning capability of the rescaled pure greedy algorithm with non-iid sampling

  2023cites this paper
• Variation Spaces for Multi-Output Neural Networks: Insights on Multi-Task Learning and Network Compression

  2023cites this paper
• Weighted variation spaces and approximation by shallow ReLU networks

  2023influential citation
• On the selection of predictors by using greedy algorithms and information theoretic criteria

  2023cites this paper
• ReLU Neural Network Galerkin BEM

  2023cites this paper
• Approximation Properties of the Vector Weak Rescaled Pure Greedy Algorithm

  2023cites this paper
• The Convergence Analysis of Newtonized Orthogonal Matching Pursuit for Line Spectrum Estimation after Random Compression with Multiple Measurement Vectors

  2023cites this paper
• Entropy-based convergence rates of greedy algorithms

  2023cites this paper
• A reduced conjugate gradient basis method for fractional diffusion

  2023influential citation
• Quadratic Neural Networks for Solving Inverse Problems

  2023influential citation
• A New Greedy Algorithm for the Curriculum-based Course Timetabling Problem

  2023cites this paper
• An energy-efficient hierarchical algorithm of dynamic obstacle avoidance for unmanned surface vehicle

  2023cites this paper
• Clustering the Sketch: A Novel Approach to Embedding Table Compression

  2023cites this paper
• Inverse Problems with Learned Forward Operators

  2023cites this paper
• Dynamic and heterogeneity-sensitive urban network partitioning: a data-driven technique

  2023cites this paper
• On the Application of the Stability Methods to Time Series Data

  2023cites this paper
• Spectral Barron Space for Deep Neural Network Approximation

  2023cites this paper
• Continuous and atlas-free analysis of brain structural connectivity

  2023influential citation
• Adaptively Topological Tensor Network for Multi-View Subspace Clustering

  2023cites this paper
• Space-Time Approximation with Shallow Neural Networks in Fourier Lebesgue spaces

  2023cites this paper
• Carousel Greedy Algorithms for Feature Selection in Linear Regression

  2023cites this paper
• Turnpike in optimal control of PDEs, ResNets, and beyond

  2022cites this paper
• Clustering the Sketch: Dynamic Compression for Embedding Tables

  2022cites this paper
• Inverse Problems: A Deterministic Approach using Physics-Based Reduced Models

  2022cites this paper
• Early stopping for L2-boosting in high-dimensional linear models

  2022cites this paper
• Toward Efficient Ensemble Learning with Structure Constraints: Convergent Algorithms and Applications

  2022cites this paper
• Uniform approximation rates and metric entropy of shallow neural networks

  2022cites this paper
• Convergence rates of oblique regression trees for flexible function libraries

  2022cites this paper
• An Orthogonal Matching Pursuit Variable Screening Algorithm for High-Dimensional Linear Regression Models

  2022cites this paper
• Compositional Sparsity, Approximation Classes, and Parametric Transport Equations

  2022cites this paper
• Clustering Embedding Tables, Without First Learning Them

  2022cites this paper
• Almost Optimality of the Orthogonal Super Greedy Algorithm for μ-Coherent Dictionaries

  2022cites this paper
• Approximating Choice Data by Discrete Choice Models

  2022influential citation
• On some similarities and differences between deep neural networks and kernel learning machines

  2022cites this paper
• Consistency of The Oblique Decision Tree and Its Random Forest

  2022cites this paper
• Ensemble projection pursuit for general nonparametric regression

  2022cites this paper
• Optimal Approximation Rates and Metric Entropy of ReLU$^k$ and Cosine Networks

  2021cites this paper
• Sparse Water Fracture Channel Detection from Subsurface Sensors Via a Smart Orthogonal Matching Pursuit

  2021cites this paper
• Universal Consistency of Decision Trees for High Dimensional Additive Models

  2021cites this paper
• Optimal Convergence Rates for the Orthogonal Greedy Algorithm

  2021cites this paper
• Near-Minimax Optimal Estimation With Shallow ReLU Neural Networks

  2021cites this paper
• Universal approximation properties of shallow quadratic neural networks

  2021influential citation
• Universal Consistency of Decision Trees in High Dimensions

  2021cites this paper
• Efficient Multidimensional Functional Data Analysis Using Marginal Product Basis Systems

  2021cites this paper
• Doing More with Less: Characterizing Dataset Downsampling for AutoML

  2021cites this paper
• Sharp Bounds on the Approximation Rates, Metric Entropy, and n-Widths of Shallow Neural Networks

  2021cites this paper
• Two-dimensional multi-snapshot Newtonized orthogonal matching pursuit for DOA estimation

  2021cites this paper
• N A ] 29 O ct 2 01 5 Schwarz Iterative Methods : Infinite Space Splittings

  2021cites this paper
• Characterization of the Variation Spaces Corresponding to Shallow Neural Networks

  2021cites this paper
• Duality Gap Estimates for a Class of Greedy Optimization Algorithms in Banach Spaces

  2021cites this paper
• Improved Convergence Rates for the Orthogonal Greedy Algorithm

  2021cites this paper
• Generalization Performance of Empirical Risk Minimization on Over-Parameterized Deep ReLU Nets

  2021cites this paper
• Two-layer neural networks with values in a Banach space

  2021cites this paper
• A Priori Analysis of Stable Neural Network Solutions to Numerical PDEs

  2021cites this paper
• An efficient greedy training algorithm for neural networks and applications in PDEs

  2021cites this paper
• Greedy training algorithms for neural networks and applications to PDEs

  2021cites this paper
• Non-asymptotic oracle inequalities for the Lasso in high-dimensional mixture of experts

  2020cites this paper
• High-Order Approximation Rates for Shallow Neural Networks with Cosine and ReLU Activation Functions

  2020cites this paper
• Large-time asymptotics in deep learning

  2020cites this paper