Improved Error Bounds for Weak Chebyshev Greedy Algorithms

We introduce a posteriori analysis framework for theWeak Chebyshev Greedy Algorithm (WCGA) and establish new error bounds in terms of the K-functional, which use posteriori information {uk} and improve those prior results. The novelty of this framework lies in its ability to not only unify and generalize the classical results of Temlyakov and Jiang, as well as the entropy-based bounds of Li and Siegel, but also establish a quantitative connection between dictionary entropy and the posteriori information for the first time. Furthermore, we prove the stability of the WCGA by extending our analysis to the Approximate WCGA, under certain mild perturbations on the norming functional and approximant. We also establish improved error estimates for the Approximate WCGA. Then, we apply these results to analyze the approximation quality of shallow neural networks with activation functions ReLU s , revealing that higher order activations may yield improved convergence rates. Moreover, the WCGA is nearly optimal for training ReLU s shallow neural networks in L 2 space. These improved error bounds also provide a finer analysis for the performance of the WCGA in the least squares regression problem.