# Partially Lazy Gradient Descent for Smoothed Online Learning

arXiv: https://arxiv.org/abs/2601.15984 · HTML: https://mlsanity.com/paper/2601.15984/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 32 references that are in the map.
- First posted on arXiv 22 Jan 2026.

## Builds on (most cited first, 18 of 18)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (2019)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition](https://mlsanity.com/paper/1910.10873/) (2019)
- [Lazy OCO: Online Convex Optimization on a Switching Budget](https://mlsanity.com/paper/2102.03803/) (2021)
- [Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithms](https://mlsanity.com/paper/2011.12539/) (2020)
- [Smoothed Online Optimization with Unreliable Predictions](https://mlsanity.com/paper/2202.03519/) (2022)
- [Understand Dynamic Regret with Switching Cost for Online Decision Making](https://mlsanity.com/paper/1911.12595/) (2019)
- [Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor](https://mlsanity.com/paper/2205.00741/) (2022)
- [On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning](https://mlsanity.com/paper/2505.22899/) (2025)
- [Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization](https://mlsanity.com/paper/2505.21394/) (2025)

## Built on by (most cited first, 2 of 2)

- [SEArch: Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search](https://mlsanity.com/paper/2606.01325/) (2026)
- [Dynamic Regret in Online Convex Optimization with Indicator Switching Costs](https://mlsanity.com/paper/2609.30556/) (2026)

## Abstract (arXiv)

We introduce textsck-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 textsck-lazyGD achieves the optimal dynamic regret O(√(PT+1)T) for any laziness slack k up to Theta(√T/PT), where PT is the comparator path length. This result formally connects the allowable laziness to the comparator's shifts, showing that textsck-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 PT, 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.