Stability of Weak Rescaled Pure Greedy Algorithms

We study the stability of Weak Rescaled Pure Greedy Algorithms for convex optimization, WRPGA(co), in general Banach spaces. We obtain the convergence rates of WRPGA(co) with noise and errors under a weaker assumption for the modulus of smoothness of the objective function. The results show that the rate is almost the same as that of WRPGA(co) without noise and errors, which is optimal and independent of the spatial dimension. This makes WRPGA(co) more practically applicable and scalable for high-dimensional data. Furthermore, we apply WRPGA(co) with errors to the problem of m-term approximation and derive the optimal convergence rate. This indicates the flexibility of WRPGA(co) and its wide utility across machine learning and signal processing. Our numerical experiments verify the stability of WRPGA(co). Thus, WRPGA(co) is a desirable choice for practical implementation.