# Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 66 references that are in the map.
- First posted on arXiv 20 May 2023.

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

- [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)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [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)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [MetaGrad: Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1604.08740/) (2016)
- [Improved Dynamic Regret for Non-degenerate Functions](https://mlsanity.com/paper/1608.03933/) (2016)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions](https://mlsanity.com/paper/2006.05876/) (2020)
- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Online Forecasting of Total-Variation-bounded Sequences](https://mlsanity.com/paper/1906.03364/) (2019)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds](https://mlsanity.com/paper/1709.02726/) (2017)
- [A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization](https://mlsanity.com/paper/1301.4666/) (2013)
- [Improved Regret Bounds for Projection-free Bandit Convex Optimization](https://mlsanity.com/paper/1910.03374/) (2019)
- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [No Weighted-Regret Learning in Adversarial Bandits with Delays](https://mlsanity.com/paper/2103.04550/) (2021)
- [Gradient-free Online Learning in Games with Delayed Rewards](https://mlsanity.com/paper/2006.10911/) (2020)
- [Online Strongly Convex Optimization with Unknown Delays](https://mlsanity.com/paper/2103.11354/) (2021)
- [Improved Dynamic Regret for Online Frank-Wolfe](https://mlsanity.com/paper/2302.05620/) (2023)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [Distributed stochastic optimization with large delays](https://mlsanity.com/paper/2107.02919/) (2021)
- [Projection-free Online Learning with Arbitrary Delays](https://mlsanity.com/paper/2204.04964/) (2022)
- [Adaptive Hedging under Delayed Feedback](https://mlsanity.com/paper/1902.10433/) (2019)
- [Delay-Tolerant Constrained OCO with Application to Network Resource Allocation](https://mlsanity.com/paper/2105.04005/) (2021)

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

- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting](https://mlsanity.com/paper/2508.00523/) (2025)
- [Risk-averse learning with delayed feedback](https://mlsanity.com/paper/2409.16866/) (2024)

## Abstract (arXiv)

Although online convex optimization (OCO) under arbitrary delays has received increasing attention recently, previous studies focus on stationary environments with the goal of minimizing static regret. In this paper, we investigate the delayed OCO in non-stationary environments, and choose dynamic regret with respect to any sequence of comparators as the performance metric. To this end, we first propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available. The basic idea is to maintain multiple experts in parallel, each performing a gradient descent step with different learning rates for every delayed gradient according to their arrival order, and utilize a meta-algorithm to track the best one based on their delayed performance. Despite the simplicity of this idea, our novel analysis shows that the dynamic regret of Mild-OGD can be automatically bounded by O(√bardT(PT+1)) under the in-order assumption and O(√dT(PT+1)) in the worst case, where bard and d denote the average and maximum delay respectively, T is the time horizon, and PT is the path-length of comparators. Moreover, we demonstrate that the result in the worst case is optimal by deriving a matching lower bound. Finally, we develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values. Interestingly, we prove that under a relatively large amount of delay, our bandit algorithm even enjoys the best dynamic regret bound of existing non-delayed bandit algorithms.