Entropy-based convergence rates of greedy algorithms

Abstract

We present convergence estimates of two types of greedy algorithms in terms of the metric entropy of underlying compact sets. In the first part, we measure the error of a standard greedy reduced basis method for parametric PDEs by the metric entropy of the solution manifold in Banach spaces. This contrasts with the classical analysis based on the Kolmogorov n-widths and enables us to obtain direct comparisons between the greedy algorithm error and the entropy numbers, where the multiplicative constants are explicit and simple. The entropy-based convergence estimate is sharp and improves upon the classical width-based analysis of reduced basis methods for elliptic model problems. In the second part, we derive a novel and simple convergence analysis of the classical orthogonal greedy algorithm for nonlinear dictionary approximation using the metric entropy of the symmetric convex hull of the dictionary. This also improves upon existing results by giving a direct comparison between the algorithm error and the metric entropy.

fixed two typos in the older version

References in corpus (2)

• Approximation and learning by greedy algorithms
• Sharp Bounds on the Approximation Rates, Metric Entropy, and $n$-widths of Shallow Neural Networks

Cited by in corpus (5)

• A reduced conjugate gradient basis method for fractional diffusion
• On the optimality of target-data-dependent kernel greedy interpolation in Sobolev Reproducing Kernel Hilbert Spaces
• Reduced Krylov Basis Methods for Parametric Partial Differential Equations
• A new analysis of empirical interpolation methods and Chebyshev greedy algorithms
• Refined rates of convergence for target-data dependent greedy generalized interpolation with Sobolev kernels