# Proximal Online Gradient is Optimum for Dynamic Regret

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2018.

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

- [Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints](https://mlsanity.com/paper/2111.07707/) (2021)
- [Learning Large DAGs by Combining Continuous Optimization and Feedback Arc Set Heuristics](https://mlsanity.com/paper/2107.00571/) (2021)

## Abstract (arXiv)

In online learning, the dynamic regret metric chooses the reference (optimal) solution that may change over time, while the typical (static) regret metric assumes the reference solution to be constant over the whole time horizon. The dynamic regret metric is particularly interesting for applications such as online recommendation (since the customers' preference always evolves over time). While the online gradient method has been shown to be optimal for the static regret metric, the optimal algorithm for the dynamic regret remains unknown. In this paper, we show that proximal online gradient (a general version of online gradient) is optimum to the dynamic regret by showing that the proved lower bound matches the upper bound that slightly improves existing upper bound.