Partially Lazy Gradient Descent for Smoothed Online Learning
This work provides a solution to the problem of balancing stability and agility in online learning for machine learning practitioners and researchers dealing with dynamic and changing environments.
The authors tackled the problem of online learning with smoothed online convex optimization, achieving an optimal dynamic regret of O(√((P_T+1)T)) with their k-lazyGD algorithm, which bridges the gap between greedy and lazy gradient descent methods. This result shows that laziness is possible without sacrificing hitting performance for any laziness slack k up to Θ(√(T/P_T)).
We introduce $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 $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 $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.