Optimal Convergence Rates for the Orthogonal Greedy Algorithm

DOI10.1109/TIT.2022.3147984MaRDI QIDQ5088475zbMATH OpenOpenAlexFDO

Authors Jonathan W. Siegel, Jinchao Xu

Publication date 13 July 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.15000

Mathematics Subject Classification ID

Approximation algorithms (68W25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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^{-frac12-alpha})$ for $alpha>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^{-frac12})$ 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 in

(13)

• Uniform approximation rates and metric entropy of shallow neural networks
• Greedy training algorithms for neural networks and applications to PDEs
• Large-precision homomorphic sign evaluation using FHEW/TFHE bootstrapping
• Entropy-based convergence rates of greedy algorithms
• A reduced conjugate gradient basis method for fractional diffusion
• Approximation results for gradient flow trained shallow neural networks in \(1d\)
• Approximation and gradient descent training with neural networks
• Subspace method based on neural networks for solving the partial differential equation in weak form
• Randomized greedy algorithms for neural network optimization in solving partial differential equations
• Approximation results for gradient flow trained neural networks
• A new analysis of empirical interpolation methods and Chebyshev greedy algorithms
• Ensemble projection pursuit for general nonparametric regression
• A positivity-preserving subspace method based on neural networks for solving diffusion equations in the weak form

This page was built for publication: Optimal Convergence Rates for the Orthogonal Greedy Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088475)