Approximation and learning by greedy algorithms

Abstract

We consider the problem of approximating a given element $f$ from a Hilbert space $\mathcal{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.

Published in at http://dx.doi.org/10.1214/009053607000000631 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (10)

• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al

Cited by in corpus (58)

• High-dimensional variable selection
• Newtonized Orthogonal Matching Pursuit: Frequency Estimation over the Continuum
• Provable approximation properties for deep neural networks
• Early stopping and non-parametric regression: An optimal data-dependent stopping rule
• Sharp Bounds on the Approximation Rates, Metric Entropy, and $n$-widths of Shallow Neural Networks
• Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and Decoding
• Approximation and Estimation for High-Dimensional Deep Learning Networks
• Near-Minimax Optimal Estimation With Shallow ReLU Neural Networks
• Risk Bounds for High-dimensional Ridge Function Combinations Including Neural Networks
• Convex relaxations of structured matrix factorizations
• A unified way of analyzing some greedy algorithms
• Approximating Probability Densities by Iterated Laplace Approximations
• Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variation
• Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent
• Iterative Feature Selection In Least Square Regression Estimation
• Sure Independence Screening for Ultra-High Dimensional Feature Space
• Greedy algorithms for prediction
• Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits
• Asymptotics for high-dimensional covariance matrices and quadratic forms with applications to the trace functional and shrinkage
• Entropy-based convergence rates of greedy algorithms
• A Priori Analysis of Stable Neural Network Solutions to Numerical PDEs
• Sampling based approximation of linear functionals in Reproducing Kernel Hilbert Spaces
• An l1-Oracle Inequality for the Lasso
• A reduced conjugate gradient basis method for fractional diffusion
• Adaptive Minimax Estimation over Sparse ${\ell }_q$-Hulls
• Characterization of the Variation Spaces Corresponding to Shallow Neural Networks
• Toward Fast Reliable Communication at Rates Near Capacity with Gaussian Noise
• Lossy Compression via Sparse Linear Regression: Performance under Minimum-distance Encoding
• FC-KAN: Function Combinations in Kolmogorov-Arnold Networks
• Modeling and Analysis of Energy Harvesting and Smart Grid-Powered Wireless Communication Networks: A Contemporary Survey
• Nearly optimal minimax estimator for high-dimensional sparse linear regression
• Re-scale boosting for regression and classification
• On Approximation Guarantees for Greedy Low Rank Optimization
• Re-scale AdaBoost for Attack Detection in Collaborative Filtering Recommender Systems
• Structured, sparse regression with application to HIV drug resistance
• Higher order Matching Pursuit for Low Rank Tensor Learning
• Spectral Barron space for deep neural network approximation
• Sparse Variational Inference: Bayesian Coresets from Scratch
• A Sequential Significance Test for Treatment by Covariate Interactions
• Greedy metrics in orthogonal greedy learning
• Constructive neural network learning
• Weighted variation spaces and approximation by shallow ReLU networks
• A new analysis of empirical interpolation methods and Chebyshev greedy algorithms
• Variable Selection in High Dimensions with Random Designs and Orthogonal Matching Pursuit
• Efficient Multidimensional Functional Data Analysis Using Marginal Product Basis Systems
• Wavelets centered on a knot sequence: theory, construction, and applications
• Minimax Lower Bounds for Ridge Combinations Including Neural Nets
• Submodularity in Statistics: Comparing the Success of Model Selection Methods
• Ultra-high Dimensional Multiple Output Learning With Simultaneous Orthogonal Matching Pursuit: A Sure Screening Approach
• Prediction of Preliminary Maximum Wing Bending Moments under Discrete Gust
• Modified Jaccard Index Analysis and Adaptive Feature Selection for Location Fingerprinting with Limited Computational Complexity
• Greedy Criterion in Orthogonal Greedy Learning
• Projection Sparse Principal Component Analysis: an efficient least squares method
• Learning through deterministic assignment of hidden parameters
• Model selection of polynomial kernel regression
• Learning rates of $l^q$ coefficient regularization learning with Gaussian kernel
• Learning and approximation capability of orthogonal super greedy algorithm
• Semi Parametric Estimations of rotating and scaling parameters for aeronautic loads