Optimal Convergence Rates for the Orthogonal Greedy Algorithm

2021/06/28 by Siegel, Jonathan W., Xu, Jinchao · 2 citations
#41A25 #41A46 #46N30 #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2106.15000

Abstract

We analyze the orthogonal greedy algorithm when applied to dictionaries \mathbbD whose convex hull has small entropy. We show that if the metric entropy of the convex hull of \mathbbD decays at a rate of O(n^-(1)/(2)-α) for α> 0, then the orthogonal greedy algorithm converges at the same rate on the variation space of \mathbbD. This improves upon the well-known O(n^-(1)/(2)) 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 \mathbbD.

Cited by

• Sharp Lower Bounds for Linearized ReLU^k Approximation on the Sphere
• Constructive Universal Approximation and Sure Convergence for Multi-Layer Neural Networks

Related

• Randomized Greedy Algorithms for Neural Network Optimization
• On Greedy Algorithms with bounded cumulative coherence
• Sharp Lower Bounds on the Approximation Rate of Shallow Neural Networks
• On the optimality of Orthogonal Greedy Algorithm for M-coherent dictionaries
• Greedy metrics in orthogonal greedy learning