# Online Strongly Convex Optimization with Unknown Delays

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 37 references that are in the map.
- First posted on arXiv 21 Mar 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [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)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Field-aware Factorization Machines in a Real-world Online Advertising System](https://mlsanity.com/paper/1701.04099/) (2017)
- [Efficient Online Portfolio with Logarithmic Regret](https://mlsanity.com/paper/1805.07430/) (2018)
- [Bandit Online Learning with Unknown Delays](https://mlsanity.com/paper/1807.03205/) (2018)
- [Gradient-free Online Learning in Games with Delayed Rewards](https://mlsanity.com/paper/2006.10911/) (2020)
- [Online Learning with Local Permutations and Delayed Feedback](https://mlsanity.com/paper/1703.04274/) (2017)
- [Adversarial Delays in Online Strongly-Convex Optimization](https://mlsanity.com/paper/1605.06201/) (2016)

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

- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Exploiting Curvature in Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2506.07595/) (2025)
- [Asynchronous Gradient Play in Zero-Sum Multi-agent Games](https://mlsanity.com/paper/2211.08980/) (2022)
- [Online Sequential Decision-Making with Unknown Delays](https://mlsanity.com/paper/2402.07703/) (2024)
- [Projection-free Online Learning with Arbitrary Delays](https://mlsanity.com/paper/2204.04964/) (2022)
- [Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting](https://mlsanity.com/paper/2305.12131/) (2023)
- [A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees](https://mlsanity.com/paper/2602.02634/) (2026)
- [Interactive and Hybrid Imitation Learning: Provably Beating Behavior Cloning](https://mlsanity.com/paper/2412.07057/) (2024)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)
- [Capacity-Constrained Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2606.11711/) (2026)
- [Revisiting Multi-Agent Asynchronous Online Optimization with Delays: the Strongly Convex Case](https://mlsanity.com/paper/2503.10013/) (2025)

## Abstract (arXiv)

We investigate the problem of online convex optimization with unknown delays, in which the feedback of a decision arrives with an arbitrary delay. Previous studies have presented a delayed variant of online gradient descent (OGD), and achieved the regret bound of O(√T+D) by only utilizing the convexity condition, where D is the sum of delays over T rounds. In this paper, we further exploit the strong convexity to improve the regret bound. Specifically, we first extend the delayed variant of OGD for strongly convex functions, and establish a better regret bound of O(dlog T), where d is the maximum delay. The essential idea is to let the learning rate decay with the total number of received feedback linearly. Furthermore, we consider the more challenging bandit setting, and obtain similar theoretical guarantees by incorporating the classical multi-point gradient estimator into our extended method. To the best of our knowledge, this is the first work that solves online strongly convex optimization under the general delayed setting.