# Optimistic Online Convex Optimization in Dynamic Environments

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 22 references that are in the map.
- First posted on arXiv 28 Mar 2022.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [MetaGrad: Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1604.08740/) (2016)
- [Dynamical Models and Tracking Regret in Online Convex Programming](https://mlsanity.com/paper/1301.1254/) (2013)
- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [A closer look at temporal variability in dynamic online learning](https://mlsanity.com/paper/2102.07666/) (2021)
- [A Unified Analysis Method for Online Optimization in Normed Vector Space](https://mlsanity.com/paper/2112.12134/) (2021)

## Abstract (arXiv)

In this paper, we study the optimistic online convex optimization problem in dynamic environments. Existing works have shown that Ader enjoys an Oleft(√left(1+PTright)Tright) dynamic regret upper bound, where T is the number of rounds, and PT is the path length of the reference strategy sequence. However, Ader is not environment-adaptive. Based on the fact that optimism provides a framework for implementing environment-adaptive, we replace Greedy Projection (GP) and Normalized Exponentiated Subgradient (NES) in Ader with Optimistic-GP and Optimistic-NES respectively, and name the corresponding algorithm ONES-OGP. We also extend the doubling trick to the adaptive trick, and introduce three characteristic terms naturally arise from optimism, namely MT, widetildeMT and VT+1L2ρleft(ρ+2 PTright)leqslantvarrho2 VTDT, to replace the dependence of the dynamic regret upper bound on T. We elaborate ONES-OGP with adaptive trick and its subgradient variation version, all of which are environment-adaptive.