# Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 59 references that are in the map.
- First posted on arXiv 9 Feb 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [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)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (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)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [Prediction with Corrupted Expert Advice](https://mlsanity.com/paper/2002.10286/) (2020)
- [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate](https://mlsanity.com/paper/1901.09344/) (2019)
- [Optimal Rates for Random Order Online Optimization](https://mlsanity.com/paper/2106.15207/) (2021)
- [A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints](https://mlsanity.com/paper/1706.08141/) (2017)
- [SDCA without Duality, Regularization, and Individual Convexity](https://mlsanity.com/paper/1602.01582/) (2016)
- [Universal Online Convex Optimization Meets Second-order Bounds](https://mlsanity.com/paper/2105.03681/) (2021)

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

- [Online conformal prediction with decaying step sizes](https://mlsanity.com/paper/2402.01139/) (2024)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach](https://mlsanity.com/paper/2307.08360/) (2023)
- [Byzantine-Robust Distributed Online Learning: Taming Adversarial Participants in An Adversarial Environment](https://mlsanity.com/paper/2307.07980/) (2023)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Universal Online Convex Optimization with 1 Projection per Round](https://mlsanity.com/paper/2405.19705/) (2024)
- [On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning](https://mlsanity.com/paper/2505.22899/) (2025)
- [Gradient-Variation Online Adaptivity for Accelerated Optimization with H"older Smoothness](https://mlsanity.com/paper/2511.02276/) (2025)
- [Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations](https://mlsanity.com/paper/2602.04761/) (2026)
- [Optimistic Interior Point Methods for Sequential Hypothesis Testing by Betting](https://mlsanity.com/paper/2502.07774/) (2025)
- [Parameter-free Algorithms for the Stochastically Extended Adversarial Model](https://mlsanity.com/paper/2510.04685/) (2025)
- [Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization](https://mlsanity.com/paper/2311.00181/) (2023)
- [Distribution-informed Online Conformal Prediction](https://mlsanity.com/paper/2512.07770/) (2025)
- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)
- [Gradient-Variation Regret Bounds for Unconstrained Online Learning](https://mlsanity.com/paper/2604.11151/) (2026)
- [Online Optimization for Learning to Communicate over Time-Correlated Channels](https://mlsanity.com/paper/2409.00575/) (2024)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)
- [Improved Impossible Tuning and Lipschitz-Adaptive Universal Online Learning with Gradient Variations](https://mlsanity.com/paper/2505.21095/) (2025)
- [Source Component Shift Adaptation via Offline Decomposition and Online Mixing Approach](https://mlsanity.com/paper/2508.10257/) (2025)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)
- [FedSEA: Achieving Benefit of Parallelization in Federated Online Learning](https://mlsanity.com/paper/2604.19336/) (2026)

## Abstract (arXiv)

Stochastically Extended Adversarial (SEA) model is introduced by Sachs et al. [2022] as an interpolation between stochastic and adversarial online convex optimization. Under the smoothness condition, they demonstrate that the expected regret of optimistic follow-the-regularized-leader (FTRL) depends on the cumulative stochastic variance σ1:T2 and the cumulative adversarial variation Sigma1:T2 for convex functions. They also provide a slightly weaker bound based on the maximal stochastic variance σmax2 and the maximal adversarial variation Sigmamax2 for strongly convex functions. Inspired by their work, we investigate the theoretical guarantees of optimistic online mirror descent (OMD) for the SEA model. For convex and smooth functions, we obtain the same O(√σ1:T2+√Sigma1:T2) regret bound, without the convexity requirement of individual functions. For strongly convex and smooth functions, we establish an O((σmax2 + Sigmamax2) log (σ1:T2+Sigma1:T2)) bound, better than their O((σmax2 + Sigmamax2) log T) result. For exp-concave and smooth functions, we achieve a new O(dlog(σ1:T2+Sigma1:T2)) bound. Owing to the OMD framework, we broaden our work to study dynamic regret minimization and scenarios where the online functions are non-smooth. We establish the first dynamic regret guarantee for the SEA model with convex and smooth functions, which is more favorable than static regret bounds in non-stationary scenarios. Furthermore, to deal with non-smooth and convex functions in the SEA model, we propose novel algorithms building on optimistic OMD with an implicit update, which provably attain static regret and dynamic regret guarantees without smoothness conditions.