Approximation and learning by greedy algorithms

By Andrew R. Barron, Albert Cohen, Wolfgang Dahmen, Ronald A. DeVore. 2008

342 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/6b240ac2d947bb83a0a24a1988c2da166ad00405

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise (2011, methodology): “This method has been used for signal recovery and approximation, for example, in Davis, Mallat, and Avellaneda (1997), Tropp (2004, 2006), and Barron et al. (2008).”
Greedy approximation (2008, background): “Assuming that the systems D(n, q) are normalized in L2(ρX), Barron et al. (2005) proved the following error estimate.”
Results and Questions on a Nonlinear Approximation Approach for Solving High-dimensional Partial Differential Equations (2008, background): “For both algorithms, it is known that there exist dictionaries and right-hand sides f (even simple ones, like a sum of only two elements of the dictionary) such that the rate of convergence n−1/2 is attained (see [2, 4, 7]).”
Proper Generalized Decompositions and Separated Representations for the Numerical Solution of High Dimensional Stochastic Problems (2010, background): “In [7], the progressive construction (without update) has been interpreted as a Greedy algorithm in nonlinear approximation [12,4], where the dictionary is composed by separated functions of type ∏r j=0 φ j , φ ∈ S .”
Early stopping for non-parametric regression: An optimal data-dependent stopping rule (2011, methodology): “r these claims. A more recent line of work has provided theoretical justiﬁcation for various types of early stopping, including boosting algorithms (e.g., [5, 10, 17, 22, 25, 42, 43]), greedy methods [3], gradient descent over reproducing kernel Hilbert spaces (e.g. [7, 13, 11, 37, 42]), the conjuga”
Restricted Strong Convexity Implies Weak Submodularity (2016, background): “Greedy algorithms are prevalent in compressed sensing literature [8], statistical learning theory [13], and sparsity constrained regression [9–11, 14–16] but without connections to submodularity.”
Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent (2018, methodology): “, 2017), Hilbert space vector approximation methods (Barron et al., 2008), kernel herding (Chen et al.”
From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images (2009, methodology): “Approximation theorists refer to these algorithms as GAs and consider several variants of them—the pure (PGA), the orthogonal (OGA), the relaxed (RGA), and the weak GA (WGA) [154, 155, 36, 4, 87].”
Kernel Sparse Representation-Based Classifier (2012, methodology): “The -norm regularization is widely used to recover a compressible signal in compressed sensing domain [1]–[4], [6],”
Forward Regression for Ultra-High Dimensional Variable Screening (2009, methodology): “As one type of important greedy algorithms, FR’s theoretical properties have been considered in the past literature; see for example Donoho and Stodden (2006) and Barron and Co- hen (2008).”
Sparse Variational Inference: Bayesian Coresets from Scratch (2019, methodology): “which can be solved with sparse optimization techniques [31, 32, 34–36, 45, 46, 48, 58–60].”