Source-linked AI summary
Approximation and learning by greedy algorithms
Andrew R. Barron, Albert Cohen, Wolfgang Dahmen, Ronald A. DeVore
TL;DR
The paper asks how greedy algorithms can approximate Hilbert-space elements and support regression when general dictionaries make best N-term selection difficult. It develops convergence theory for several greedy methods over broader function classes, then constructs universally consistent learning estimators with provable rates. The approach also reduces computational cost by searching sequentially generated subsets rather than all dictionary subsets.
Problem
Best N-term approximation is computationally difficult for large general dictionaries, while existing greedy convergence theory does not adequately cover general target functions outside L1-type classes.
Method
The paper derives approximation bounds for OGA, RGA, and SPA using broader function classes including interpolation spaces, and transfers these bounds to empirical greedy regression estimators.
Results
The learning estimators are universally consistent and have provable convergence rates for broader regression-function classes; for fρ ∈ L1, the result has p = 1 and s = 1/2.
Takeaways & Limitations
Greedy algorithms provide a computationally cheaper alternative to exhaustive subset selection while retaining provable approximation and learning guarantees.
Takeaways & Limitations
Practical schemes still require dictionary truncation; controlling discretization of direction vectors then requires the smoother classes L1,r and Bp,r.
Abstract
from arXiv · showhide
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.
1. Introduction.
The paper studies greedy approximation in Hilbert spaces and statistical learning, extending convergence theory beyond convex-hull classes and developing computationally efficient, universally consistent learning procedures.
- Two contexts: The paper analyzes deterministic approximation and statistical learning, where the target is respectively known or an unknown regression function estimated from independent data.In learning, error is measured using the distribution-dependent norm E(|u(x)|^2).
- Motivation: Greedy algorithms construct manageable N-term approximations when finding the best approximation over large dictionaries is computationally infeasible.They select dictionary elements sequentially rather than minimizing over all N-dimensional subspaces.
- Computational benefit: Greedy estimation reduces computational cost by considering only the sequentially generated sets Λk instead of all dictionary subsets.The empirical algorithm generates Λk = {g1,...,gk} for k = 1,...,n.
- Learning theory: The resulting learning estimators remove fρ ∈ L1 requirements, apply to broader interpolation-space regression functions, and are universally consistent with provable convergence rates.When fρ ∈ L1, the paper obtains p = 1 and s = 1/2.
2. Approximation properties.
The section develops approximation guarantees for OGA and RGA beyond L1, using interpolation spaces to obtain rates for general Hilbert-space targets while retaining convergence under dictionary truncation.
- Greedy algorithms: OGA constructs nested approximation spaces by selecting dictionary elements and projecting f orthogonally onto the resulting spaces.The residual is updated after each projection, and the next dictionary element is chosen greedily.
- Greedy algorithms: RGA uses parameterized updates with optimized coefficients, and the considered version is computationally similar to PGA.When αk=1, RGA coincides with PGA.
- Approximation of general functions: For general f∈H, interpolation spaces Bp between L1 and H yield rates CN^-s for OGA and RGA, with s=1/p−1/2, and convergence without a rate holds for every f∈H.These rates are optimal for orthonormal bases, while general dictionaries cannot guarantee rates better than N^-1/2 even for simple functions.
- Approximation of general functions: The nonlinear greedy approximants satisfy K-functional bounds, despite not being generated by continuous linear operators.For f∈Bp, the resulting residual decays as N^-θ/2, and the OGA bound is obtained despite the algorithm’s highly nonlinear construction.
- Greedy algorithms with a truncated dictionary: With a truncated dictionary, targets in Bp,r or L1,r recover the full-dictionary rate up to an additive perturbation that vanishes as the truncation grows.The classes Bp,r depend on the exhaustion order of the dictionary.
3. Application to statistical learning.
The paper formulates bounded regression estimation through greedy approximations in empirical Hilbert spaces, selecting and truncating iterates with complexity regularization. Its analysis yields rates under several function classes, universal consistency for arbitrary regression functions, and applicability to OGA, RGA, and SPA.
- Estimator: The estimator applies OGA, SPA, or RGA to bounded noisy data over a truncated dictionary using the empirical inner product.The dictionary size is limited according to the sample size, and the RGA uses the second parameter choice described in the paper.
- Problem formulation: The regression function fρ minimizes quadratic risk, and performance is measured by the expected squared L2 error between the estimator and fρ.
- Estimator: The selected iterate is truncated at level B and chosen by minimizing a penalized empirical risk over the greedy sequence.The penalty parameter is κ, and the algorithm need not run beyond the range implied by the bound Bn/κ.
- Caveat: The complexity constant κ0 = 2568B4(a + 5) is described as pessimistic, and hold-out selection is offered as an alternative to the complexity penalty.
4. Neural networks.
The paper specializes its greedy-learning theory to neural-network dictionaries, relating approximation and learning guarantees to dictionary completeness and function smoothness. It improves the earlier convex-hull result but identifies practical costs from dictionary truncation and dimensionality.
- Neural-network dictionaries: Neural networks are represented by dictionaries formed from a positive increasing activation function σ applied to affine functions of the input.Typical activations include the Heaviside function and regularized sigmoidal functions.
- Prior results: Earlier results for d-bounded fan-in Heaviside networks converge to the projection fa onto the dictionary's convex hull, so they are not universally consistent.
- Convergence results: Without truncation, the neural-network dictionary supports the stated rates under f ∈ L1 and f ∈ Bp; universal consistency requires completeness, which holds only when d = D.
- Convergence results: Theorem 3.1 replaces fa with an arbitrary optimizable h and also allows k to be optimized, improving the earlier bound.
- Practical limitation: For finite practical dictionaries, additional smoothness in L1,r and Bp,r is needed to control discretization error from restricting the direction vectors.