提出可调懒惰度的在线优化算法，兼顾稳定与响应速度。
Partially Lazy Gradient Descent for Smoothed Online Learning
- 通过调节更新频率，在贪心与延迟更新间实现平滑过渡。
- 在路径长度受限时，动态误差达最优阶 $\mathcal{O}(\sqrt{(P_T+1)T})$。
- 适合需要自适应稳定性与灵活性的在线学习场景。
我们提出 extsc{$k$-lazyGD}，一种在线学习算法，介于贪婪在线梯度下降（OGD，$k=1$）与延迟梯度下降/对偶平均（$k=T$）之间，形成从反应式到稳定更新的连续谱。在平滑在线凸优化（SOCO）中，学习者需权衡损失代价与移动代价。主要贡献在于证明：在不牺牲损失表现的前提下，允许一定程度的懒惰—— extsc{$k$-lazyGD} 在任意懒惰松弛 $k \leq \Theta(\sqrt{T/P_T})$ 下均能实现最优动态误差 $\mathcal{O}(\sqrt{(P_T+1)T})$，其中 $P_T$ 为比较路径长度。该结果明确关联了允许的懒惰程度与比较路径的变动幅度，表明 extsc{$k$-lazyGD} 可保持延迟方法的小移动特性而不影响跟踪能力。分析基于正则化领导者追随（FTRL）框架，并给出匹配下界。由于松弛参数依赖 $P_T$，采用多个不同松弛参数的学习器集成，使得算法在可稳定时保持稳定，在必须响应时保持敏捷。
原文摘要 · Abstract (English)
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 $Θ(\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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。