Research map / Bandits and online learning / Online convex optimization and games
Non-stationary Online Convex Optimization with Arbitrary Delays
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DOGD and Mild-OGD for online convex optimization with arbitrary delays under non-stationary environments, achieving dynamic regret bounds O(sqrt(d̄T(PT+1))) and O(sqrt(dT(PT+1))) with a matching lower bound.
Problem
Online convex optimization with arbitrary (possibly unbounded per-round) gradient delays, where the goal is to minimize dynamic regret against any comparator sequence in non-stationary environments.
Approach
DOGD performs one gradient step per delayed gradient in arrival order, enabling analysis that depends on average delay; Mild-OGD runs multiple DOGD with different learning rates and combines them with a delayed Hedge meta-algorithm that uses surrogate linear losses, recovering the optimal dynamic regret rate under delays.
Key results
- DOGD attains dynamic regret O(sqrt(d̄T(PT+1))) under the In-Order assumption and O(sqrt(dT(PT+1))) in the worst case.
- Mild-OGD improves these to O(sqrt(d̄T(PT+1))) and O(sqrt(dT(PT+1))) respectively, matching the non-delayed optimal rate of Zhang et al. (2018a) when there is no delay.
- A lower bound of Omega(sqrt(dT(PT+1))) is proved for dynamic regret of delayed OCO, showing Mild-OGD is worst-case optimal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Mild-OGD instead of DOGD, combining multiple learning-rate DOGD experts with delayed Hedge | Delayed OCO · Delayed OCO, arbitrary delays (worst case) | dynamic regret: O(√dT(PT + 1)) | Helped |
| Assume delays preserve gradient arrival order | DOGD · Delayed OCO | dynamic regret: O(√dT(PT + 1)) -> O(√¯dT(PT + 1)) | Helped |
| Assume delays preserve gradient arrival order | Mild-OGD · Delayed OCO | dynamic regret: O(√dT(PT + 1)) -> O(√¯dT(PT + 1)) | Helped |
| Use Mild-OGD with multiple learning rates and delayed Hedge rather than a single DOGD learning rate | Delayed OCO · Delayed OCO, arbitrary delays (worst case) | dynamic regret dependence on comparator path-length: linear dependence on PT -> sublinear | Helped |
| Allow arbitrary delays instead of no delay | Mild-OGD · Delayed OCO, arbitrary delays (worst case) | dynamic regret: O(√(T(PT + 1))) -> O(√(dT(PT + 1))) | Hurt |
| Use Mild-OGD in the worst case with d ≤ L | Delayed OCO · Delayed OCO, arbitrary delays (worst case) | dynamic regret: O(√(dT(PT + 1))); Ω(√(dT(PT + 1))) | No clear effect |
Limitations
- Tight bounds without the In-Order assumption only hold in the worst case; the average-delay bound needs In-Order or a small comparator drift condition C.
- Learning rate tuning requires knowledge of sum of m_t, handled only via doubling trick in the appendix.
- Theoretical paper with no empirical experiments.
Experimental setup
Metrics: dynamic regret
Baselines: OGD DOGD (Quanrud & Khashabi, 2015 style static-regret delayed OGD) Joulani et al. 2013 black-box delayed reduction
Builds on: online gradient descent Zhang et al. 2018a multiple-learning-rate dynamic regret algorithm delayed Hedge (Korotin et al., 2020) Quanrud & Khashabi 2015 delayed OGD
Closest papers by meaning
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.91)
- Exploiting Curvature in Online Convex Optimization with Delayed Feedback (ICML 2025 · similarity 0.90)
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.90)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.89)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.89)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.