Step-Size Decay and Structural Stagnation in Greedy Sparse Learning
This work addresses a theoretical problem for researchers and practitioners designing greedy sparse learning algorithms, offering insights into step-size selection to avoid stagnation.
This paper investigates the convergence of Power-Relaxed Greedy Algorithms in sparse learning, specifically when step sizes decay as $m^{-α}$. It demonstrates that step-size schedules with $α>1$ can lead to structural stagnation, resulting in explicit lower bounds on the residual norm even in low-dimensional sparse settings. Numerical experiments validate these theoretical predictions and highlight the impact of feature coherence.
Greedy algorithms are central to sparse approximation and stage-wise learning methods such as matching pursuit and boosting. It is known that the Power-Relaxed Greedy Algorithm with step sizes $m^{-α}$ may fail to converge when $α>1$ in general Hilbert spaces. In this work, we revisit this phenomenon from a sparse learning perspective. We study realizable regression problems with controlled feature coherence and derive explicit lower bounds on the residual norm, showing that over-decaying step-size schedules induce structural stagnation even in low-dimensional sparse settings. Numerical experiments confirm the theoretical predictions and illustrate the role of feature coherence. Our results provide insight into step-size design in greedy sparse learning.