Approximation and learning by greedy algorithms
The Annals of StatisticsPublished 1 February 2008Open access
Andrew R. Barron, Albert Cohen, Wolfgang Dahmen, Ronald DeVore
Citations314
SJR quartileQ1
SJR score4.77
SNIP3.13
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work improves 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, and proves convergence results for a variety of function classes and not simply those that are related to the convex hull of the dictionary.
Abstract
We consider the problem of approximating a given element f from a Hilbert spaceHby 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. 1. Introduction. We
Keywords
Computer ScienceEngineering
Journal of the Royal Statistical Society Series B (Statistical Methodology)Regression Shrinkage and Selection Via the Lasso
51,790 Citations1996Robert Tibshirani
A new method for estimation in linear models called the lasso, which minimizes the residual sum of squares subject to the sum of the absolute value of the coefficients being less than a constant, is proposed.
Springer series in statisticsThe Elements of Statistical Learning
24,344 Citations2001Trevor Hastie, J. Friedman +1 more
The Annals of StatisticsLeast angle regression
9,493 Citations2004Bradley Efron, Trevor Hastie +2 more
IEEE Transactions on Information TheoryUniversal approximation bounds for superpositions of a sigmoidal function
2,849 Citations1993Andrew R. Barron
The approximation rate and the parsimony of the parameterization of the networks are shown to be advantageous in high-dimensional settings and the integrated squared approximation error cannot be made smaller than order 1/n/sup 2/d/ uniformly for functions satisfying the same smoothness assumption.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Wavelet Shrinkage: Asymptopia?
1,758 Citations1995David L. Donoho, Iain M. Johnstone +2 more
A method for curve estimation based on n noisy data: translate the empirical wavelet coefficients towards the origin by an amount √(2 log n) /√n and draw loose parallels with near optimality in robustness and also with the broad near eigenfunction properties of wavelets themselves.
Springer series in statisticsA Distribution-Free Theory of Nonparametric Regression
1,738 Citations2002László Györfi, Michael Köhler +2 more
How to Construct Nonparametric Regression Estimates * Lower Bounds * Partitioning Estimates * Kernel Estimates * k-NN Estimates * Splitting the Sample * Cross Validation * Uniform Laws of Large Numbers
Constructive ApproximationAdaptive greedy approximations
1,141 Citations1997Geoffrey M. Davis, Stéphane Mallat +1 more
A notion of the coherence of a signal with respect to a dictionary is derived from the characterization of the approximation errors of a pursuit from their statistical properties, which can be obtained from the invariant measure of the pursuit.
The Annals of StatisticsMinimax estimation via wavelet shrinkage
1,028 Citations1998David L. Donoho, Iain M. Johnstone
A nonlinear method which works in the wavelet domain by simple nonlinear shrinkage of the empirical wavelet coefficients is developed, andVariants of this method based on simple threshold nonlinear estimators are nearly minimax.
Acta NumericaNonlinear approximation
859 Citations1998Ronald DeVore
This is a survey of nonlinear approximation, especially that part of the subject which is important in numerical computation, and emphasis will be placed on approximation by piecewise polynomials and wavelets as well as their numerical implementation.
Advances in Computational MathematicsSome remarks on greedy algorithms
574 Citations1996Ronald DeVore, Vladimir Temlyakov
Three greedy algorithms are discussed: the Pure GreedyAlgorithm, an Orthogonal Greedy Algorithm, and a Relaxed Gre greedy Algorithm.
The Annals of StatisticsA Simple Lemma on Greedy Approximation in Hilbert Space and Convergence Rates for Projection Pursuit Regression and Neural Network Training
474 Citations1992Lee Jones
A general convergence criterion for certain iterative sequences in Hilbert space is presented and results establish an 0(1/ F4n) nonsampling convergence rate for projection pursuit regression and neural network training.
Foundations of Computational MathematicsNonlinear Methods of Approximation
293 Citations2003Vladimir Temlyakov
Nonlinear approximation is focused on both in the classical form of m -term approximation (where several important problems remain unsolved) and in the form of highly nonlinear approximation where a theory is only now emerging.
Advances in Computational MathematicsWeak greedy algorithms[*]This research was supported by National Science Foundation Grant DMS 9970326 and by ONR Grant N00014‐96‐1‐1003.
231 Citations2000Vladimir Temlyakov
The convergence theorems are proved and estimates for the rate of approximation are given by means of these algorithms, which apply to approximation from an arbitrary dictionary in a Hilbert space.
Complexity Regularization with Application to Artificial Neural Networks
160 Citations1991Andrew R. Barron
This paper defines general complexity regularization criteria and establishes bounds on the statistical risk of the estimated functions and establishes consistency, yield rates of convergence, and the near asymptotic optimality of the model selection criterion in both parametric and nonparametric cases.
IEEE Transactions on Information TheoryEfficient agnostic learning of neural networks with bounded fan-in
156 Citations1996Wee Sun Lee, Peter L. Bartlett +1 more
IEEE Transactions on Information TheoryComparison of worst case errors in linear and neural network approximation
141 Citations2002Věra Kůrková, Marcello Sanguineti
A theoretical framework for describing sets of multivariable functions for which worst case errors in linear approximation are larger than those in approximation by neural networks is developed in the context of nonlinear approximation by fixed versus variable basis functions.
SIAM Journal on Mathematical AnalysisApproximation by Ridge Functions and Neural Networks
118 Citations1998Pencho Petrushev
The theorems obtained show that this form of ridge approximation has the same efficiency of approximation as other more traditional methods of multivariate approximation such as polynomials, splines, or wavelets.
IEEE Transactions on Information TheoryBounds on rates of variable-basis and neural-network approximation
105 Citations2001Věra Kůrková, Marcello Sanguineti
The tightness of bounds on rates of approximation by feedforward neural networks is investigated in a more general context of nonlinear approximation by variable-basis functions.
Advances in Computational MathematicsGreedy algorithms in Banach spaces
77 Citations2001Vladimir Temlyakov
It is proved that for any f from the closure of the convex hull of D the error of m-term approximation by WCGA is of order and similar results are obtained for Weak Relaxed Greedy Algorithm and its modification.
IEEE Transactions on Information TheoryAsymptotic distribution of the errors in scalar and vector quantizers
63 Citations1996D.H. Lee, David L. Neuhoff
High-rate (or asymptotic) quantization theory has found formulas for the average squared length and the probability density of the length of the error and, in certain special cases, for the probabilitydensity of the multidimensional error vector, itself, which can be used to analyze the distortion of two-stage vector quantization.
Constructive ApproximationTwo Lower Estimates in Greedy Approximation
45 Citations2003Eugene Livshitz, Vladimir Temlyakov
One lower estimate combined with the known upper estimate gives the right dependence of the exponent in the rate of convergence of the Pure Greedy Algorithm on the parameter t when t ↠ 0.
Mathematical NotesRate of Convergence of Pure Greedy Algorithms
29 Citations2004Евгений Давидович Лившиц
Upper bounds for the rate of convergence of pure greedy algorithms for functions from the class Aα, β(D) are obtained for function-based greedy algorithms in Hilbert space.
The European Symposium on Artificial Neural NetworksPenalized least squares, model selection, convex hull classes and neural nets.
4 Citations2001Gerald H. L. Cheang, Andrew R. Barron