Optimal Convergence Rates for the Orthogonal Greedy Algorithm

Jonathan W. Siegel, Jinchao XuIEEE Trans. Information Theory 2022 · OpenReview

TL;DR

This paper shows that the Orthogonal Greedy Algorithm (OGA) can achieve faster convergence rates than previously known, specifically when approximating functions using dictionaries with "small entropy" (like those from shallow neural networks). They prove these improved rates are optimal and robust to noise, but also demonstrate that the OGA's intermediate steps can grow unboundedly in a specific norm.

What Problem Does This Paper Address?

The paper tackles the problem of approximating a target function $f$ using a sparse linear combination of elements from a given dictionary $D$. This is a fundamental problem in areas like machine learning, signal processing, and compressed sensing. While it's known that any function within the "convex hull" of a dictionary can be approximated with a certain rate (specifically, $O(n^{-1/2})$ for $n$ dictionary elements), a key question is whether greedy algorithms can achieve this rate. The Orthogonal Greedy Algorithm (OGA) is a popular choice, but its theoretical convergence rate was known to be $O(n^{-1/2})$. This paper investigates if the OGA can do better, especially for dictionaries that are "compact" in a specific sense (measured by their metric entropy). They are particularly interested in dictionaries arising from shallow neural networks, which are known to have this "compactness" property.

Methods

The core of the paper lies in a theoretical analysis of the OGA's convergence. The authors introduce the concept of metric entropy of the dictionary's convex hull, which quantifies its "compactness." They prove that if this entropy decays at a rate faster than $O(n^{-1/2})$, specifically $O(n^{-1/2 - \alpha})$ for some $\alpha > 0$, then the OGA can achieve a corresponding improved convergence rate of $O(n^{-1/2 - \alpha})$. This is a significant improvement over the standard $O(n^{-1/2})$ bound.

Key techniques include:

  • Metric Entropy: Quantifying the "size" or "complexity" of the dictionary's convex hull.
  • K-functionals and Interpolation Spaces: Used to extend the convergence results to more general function spaces.
  • Lower Bounds and Negative Results: Demonstrating that the derived rates are sharp and that certain desirable properties (like bounded coefficients) cannot always be guaranteed.
  • Numerical Experiments: Validating the theoretical findings using dictionaries derived from shallow neural networks.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic dictionaries and functions for illustration and validation.

Key Insights and Ideas

  • Beyond $O(n^{-1/2})$: The most significant insight is that the OGA's convergence rate is not inherently capped at $O(n^{-1/2})$. It can be faster if the dictionary has a certain geometric property (low metric entropy). This opens the door to faster approximations for specific classes of functions and dictionaries.
  • Shallow Neural Networks as a Prime Example: The paper highlights shallow neural networks (with Heaviside or ReLU activation) as a key application where these improved rates are realized. This connects theoretical approximation theory directly to a practically important machine learning model.
  • Robustness to Noise: The improved convergence rates are shown to hold even when the target function is not perfectly in the dictionary's convex hull but is close to it (i.e., with noise). This is crucial for real-world applications where data is often noisy.
  • Optimality of Rates: The authors provide theoretical lower bounds that match their derived upper bounds, confirming that the improved rates are indeed the best possible under the given assumptions.
  • Unbounded Intermediate Steps: A surprising negative result is that while the final approximation error improves, the intermediate iterates of the OGA can grow arbitrarily large in the "variation norm" ($K_1(D)$). This means that while the algorithm eventually converges faster, its internal steps might not be well-behaved in a specific sense.

Key Results

  • Improved Convergence Rate: For dictionaries $D$ where the metric entropy of their convex hull decays as $O(n^{-1/2 - \alpha})$ for $\alpha > 0$, the OGA achieves a convergence rate of $O(n^{-1/2 - \alpha})$. This improves upon the standard $O(n^{-1/2})$ rate.
  • Application to Neural Networks: This improved rate is shown to apply to dictionaries corresponding to shallow neural networks with Heaviside and ReLU activation functions.
  • Sharpness of Rates: Theoretical lower bounds are established, demonstrating that the derived convergence rates are optimal.
  • Robustness to Noise: The convergence analysis is extended to handle noisy target functions, showing that the improved rates are maintained.
  • Unbounded Variation Norm: A counterexample is provided showing that the iterates of the OGA can have arbitrarily large $K_1(D)$ norms, meaning their coefficients in the variation norm are not uniformly bounded.

Limitations and Future Work

  • Unbounded Coefficients: The paper explicitly notes that the improved convergence rates are achieved without guaranteeing that the coefficients of the dictionary elements in the OGA's expansion are uniformly bounded in the $l_1$ norm. This is a significant limitation for some applications.
  • Greedy Algorithms with Further Restrictions: A key open question is whether greedy algorithms that do satisfy coefficient bounds can also achieve these improved rates.
  • Extension to Other Problems: The authors suggest extending this analysis to other areas like reduced basis methods and sparse PCA.
  • Practical Implications of Unbounded Norms: While the theoretical rates are improved, the practical implications of unbounded intermediate variation norms are not fully explored. Future work could investigate how this affects practical performance or if alternative algorithms can achieve similar rates with bounded norms.

Summary updated

Abstract

We analyze the orthogonal greedy algorithm when applied to dictionaries <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {D}$ </tex-math></inline-formula> whose convex hull has small entropy. We show that if the metric entropy of the convex hull of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {D}$ </tex-math></inline-formula> decays at a rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O\left({n^{-\frac {1}{2}-\alpha }}\right)$ </tex-math></inline-formula> for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha &gt; 0$ </tex-math></inline-formula> , then the orthogonal greedy algorithm converges at the same rate on the variation space of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {D}$ </tex-math></inline-formula> . This improves upon the well-known <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O\left({n^{-\frac {1}{2}}}\right)$ </tex-math></inline-formula> convergence rate of the orthogonal greedy algorithm in many cases, most notably for dictionaries corresponding to shallow neural networks. These results hold under no additional assumptions on the dictionary beyond the decay rate of the entropy of its convex hull. In addition, they are robust to noise in the target function and can be extended to convergence rates on the interpolation spaces of the variation norm. We show empirically that the predicted rates are obtained for the dictionary corresponding to shallow neural networks with Heaviside activation function in two dimensions. Finally, we show that these improved rates are sharp and prove a negative result showing that the iterates generated by the orthogonal greedy algorithm cannot in general be bounded in the variation norm of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {D}$ </tex-math></inline-formula> .
BibTeX
@article{siegel2022optimal,
  author = {Jonathan W. Siegel and Jinchao Xu},
  title = {{Optimal Convergence Rates for the Orthogonal Greedy Algorithm}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  url = {https://openreview.net/forum?id=ykc0ZBXiS8u},
}
Figure