Step-Size Decay and Structural Stagnation in Greedy Sparse Learning

Pablo M. Berná

cs.LGMar 8, 2026

Step-Size Decay and Structural Stagnation in Greedy Sparse Learning

Authors: Pablo M. Berná

Organizations: Departamento de Matemáticas, CUNEF Universidad Madrid, Spain

Abstract

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.

Figures & tables

Figure 1: Minimum residual norm $\min_{1\leq m\leq M}\|r_{m}\|_{2}$ as a function of the coherence $\mu$ for $\alpha=1.1$ and $\alpha=1.5$ . Solid lines correspond to the empirical PRGA performance, while dashed lines indicate the theoretical lower bound $b(1-\mu)\sqrt{\frac{1+\mu}{2}}\,P_{\alpha}$ .

Explore similar work

Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup-Stable-Decay
Feb 6, 2026Binghui Li, Zilin Wang, Fengling Chen +3Learning Rate Scheduling Kernel Regression
Center for Machine Learning Research, Peking University · School of Mathematical Sciences, Peking University · AI for Science Institute, Beijing
On Regularization via Early Stopping for Least Squares Regression
Jun 6, 2024Rishi Sonthalia, Jackie Lok, Elizaveta RebrovaEarly Stopping Linear Regression
Department of Mathematics, Boston College · ORFE Department, Princeton University
Asymptotic Risk of Learning-Rate Schedules for Least-Squares Regression with Discretely Distributed Features
Oct 12, 2026Noé Colomban, Francis Bach, Fabian SchaippLearning Rate Scheduling Stochastic Gradient Descent
Inria - École Normale Supérieure PSL Research University

Feb 6, 2026J/K move · Enter open · S save

Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup-Stable-Decay

Binghui Li, Zilin Wang, Fengling Chen, Shiyang Zhao+2

Center for Machine Learning Research, Peking University · School of Mathematical Sciences, Peking University · AI for Science Institute, Beijing

Learning Rate Scheduling Kernel Regression Stochastic Gradient Descent

Open paper AskPDF arXiv

We study optimal learning rate (LR) schedules under the functional scaling law (FSL) framework (Li et al., 2025), which decomposes training dynamics into signal learning and noise forgetting. In power-law kernel regression, these two components are governed by a source exponent

s>0

and a capacity exponent

q>1

, respectively, with smaller

s

corresponding to harder tasks. For a fixed training horizon

N

, we characterize the schedules that minimize the final-step loss under a stability constraint and reveal a sharp phase transition. In the easy-task regime

s>1-1/q

, the optimal schedule follows power decay from the beginning of training; in the hard-task regime

s<1-1/q

, it becomes warmup-stable-decay (WSD)-like (Hu et al., 2024), staying at the largest admissible LR for most of training before a final decay. In both regimes, the decay exponent is

2q-1

: task difficulty determines when to decay, while model capacity determines how to decay. Beyond the exact optimum, we study fractional schedules, whose shape is defined over relative training progress. We show that precise tuning of the decay shape is often unnecessary: a broad class of profiles attains the optimal convergence rate, while overly slow terminal decay leads to schedule-induced capacity saturation. Finally, for one-pass SGD in kernel regression, FSL-motivated power-decay schedules achieve optimal last-iterate rates. Experiments support the theoretical predictions and the task-dependent transition between early and delayed decay.

Abstract

Explore similar work

Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup-Stable-Decay

On Regularization via Early Stopping for Least Squares Regression

Asymptotic Risk of Learning-Rate Schedules for Least-Squares Regression with Discretely Distributed Features