Abstract:We introduce \textsc{$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 \textsc{$k$-lazyGD} achieves the optimal dynamic regret $\mathcal{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 \textsc{$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.
| Comments: | to appear in the proceedings of AISTATS 2026 |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2601.15984 [cs.LG] |
| (or arXiv:2601.15984v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2601.15984 arXiv-issued DOI via DataCite |
From: Naram Mhaisen [view email]
[v1]
Thu, 22 Jan 2026 14:05:08 UTC (1,324 KB)
[v2]
Wed, 22 Apr 2026 23:02:06 UTC (2,928 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。