# Trading-Off Static and Dynamic Regret in Online Least-Squares and Beyond

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Sep 2019.

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

- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Online Linear Regression in Dynamic Environments via Discounting](https://mlsanity.com/paper/2405.19175/) (2024)
- [An Optimal Reduction of TV-Denoising to Adaptive Online Learning](https://mlsanity.com/paper/2101.09438/) (2021)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [Predictive Linear Online Tracking for Unknown Targets](https://mlsanity.com/paper/2402.10036/) (2024)
- [Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR](https://mlsanity.com/paper/2111.11550/) (2021)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [Online Residual Learning from Offline Experts for Pedestrian Tracking](https://mlsanity.com/paper/2409.04069/) (2024)
- [Bayesian Ensembling: Insights from Online Optimization and Empirical Bayes](https://mlsanity.com/paper/2505.15638/) (2025)
- [Dynamic Regret for Online Regression in RKHS via Discounted VAW and Subspace Approximation](https://mlsanity.com/paper/2604.25021/) (2026)

## Abstract (arXiv)

Recursive least-squares algorithms often use forgetting factors as a heuristic to adapt to non-stationary data streams. The first contribution of this paper rigorously characterizes the effect of forgetting factors for a class of online Newton algorithms. For exp-concave and strongly convex objectives, the algorithms achieve the dynamic regret of maxO(log T),O(√TV), where V is a bound on the path length of the comparison sequence. In particular, we show how classic recursive least-squares with a forgetting factor achieves this dynamic regret bound. By varying V, we obtain a trade-off between static and dynamic regret. In order to obtain more computationally efficient algorithms, our second contribution is a novel gradient descent step size rule for strongly convex functions. Our gradient descent rule recovers the order optimal dynamic regret bounds described above. For smooth problems, we can also obtain static regret of O(T1-β) and dynamic regret of O(Tβ V^*), where β ∈ (0,1) and V^* is the path length of the sequence of minimizers. By varying β, we obtain a trade-off between static and dynamic regret.