# Bounds for the tracking error of first-order online optimization methods

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2020.

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

- [Stochastic Optimization under Distributional Drift](https://mlsanity.com/paper/2108.07356/) (2021)
- [An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2409.19212/) (2024)
- [A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2412.20017/) (2024)
- [Stochastic Saddle Point Problems with Decision-Dependent Distributions](https://mlsanity.com/paper/2201.02313/) (2022)
- [Locally Differentially Private Distributed Online Learning with Guaranteed Optimality](https://mlsanity.com/paper/2306.14094/) (2023)

## Abstract (arXiv)

This paper investigates online algorithms for smooth time-varying optimization problems, focusing first on methods with constant step-size, momentum, and extrapolation-length. Assuming strong convexity, precise results for the tracking iterate error (the limit supremum of the norm of the difference between the optimal solution and the iterates) for online gradient descent are derived. The paper then considers a general first-order framework, where a universal lower bound on the tracking iterate error is established. Furthermore, a method using "long-steps" is proposed and shown to achieve the lower bound up to a fixed constant. This method is then compared with online gradient descent for specific examples. Finally, the paper analyzes the effect of regularization when the cost is not strongly convex. With regularization, it is possible to achieve a non-regret bound. The paper ends by testing the accelerated and regularized methods on synthetic time-varying least-squares and logistic regression problems, respectively.