Research
Partially Lazy Gradient Descent for Smoothed Online Learning
arXiv:2601.15984v2 Announce Type: replace Abstract: We introduce extsc{k-lazyGD}, an online learning algorithm that bridges the gap between greedy Online Gradient Descent (OGD, for k{=}1) and lazy GD/
arXiv:2601.15984v2 Announce Type: replace Abstract: We introduce extsc{k-lazyGD}, an online learning algorithm that bridges the gap between greedy Online Gradient Descent (OGD, for k{=}1) and lazy GD/dual-averaging (for k{=}T), creating a spectrum between reactive and stable updates. We analyze this spectrum in Smoothed Online Convex Optimization (SOCO), where the learner incurs both hitting and movement costs. Our main contribution is establishing that laziness is possible without sacrificing hitting performance: we prove that extsc{k-lazyGD} achieves the optimal dynamic regret O(sqrt{(P_T{+}1)T}) for any laziness slack k up to Theta(sqrt{T/P_T}), where P_T is the comparator path length. This result formally connects the allowable laziness to the comparator's shifts, showing that extsc{k-lazyGD} can retain the inherently small movements of lazy methods without compromising tracking ability. We base our analysis on the Follow the Regularized Leader (FTRL) framework, and derive a matching lower bound. Since the slack depends on P_T, an ensemble of learners with various slacks is used, yielding a method that is provably stable when it can be, and agile when it must be.
Related
- On the Theory of Continual Learning with Gradient Descent for Neural Networks
- Online Quantile Regression for Nonparametric Additive Models
- Nonmonotone subgradient methods based on a local descent lemma
- DADA: Dual Averaging with Distance Adaptation
- Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance
Source: arXiv cs.LG | 2026-04-24