A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees
Organizations: University of Toronto · Vector Institute · Institute for Data, Econometrics, Algorithms, and Learning (IDEAL), hosted by UIC and TTIC
Abstract
This paper develops a reduction-based framework for online learning with delayed feedback that recovers and improves upon existing results for first-order and bandit convex optimization. We introduce a continuous-time model that enables an observation-centric rather than prediction-centric analysis. Under this model, regret decomposes into a delay-independent learning term and a delay-induced drift term, yielding a delay-adaptive reduction that converts any online linear optimization algorithm into one that handles round-dependent delays. For bandit convex optimization, we significantly improve existing regret bounds, with delay-dependent terms matching optimal first-order rates. For first-order feedback, we recover optimal regret bounds via a simpler, unified analysis. Quantitatively, for bandit convex optimization we obtain regret, improving the delay-dependent term from in prior work to . Here, , , , and denote the dimension, time horizon, maximum and total delay, respectively. Under strong convexity, we achieve , improving the delay-dependent term from to , where denotes the maximum number of outstanding observations and may be considerably smaller than .
Figures & tables
| Loss type | Regret bounds for bandit convex optimization with delays | ||
|---|---|---|---|
| Bistritz et al. (2022) | Wan et al. (2024a) | Our work | |
| Convex | |||
| Strongly convex | N/A | ||
| Loss type | Regret bounds | ||
| Delayed OCO | Two-point BCO | Delayed two-point BCO | |
| Quanrud and Khashabi (2015) ; Qiu et al. (2025) | Shamir (2017) | Our work | |
| Convex | |||
| Strongly convex | |||
Online Convex Optimization
Online Convex Optimization studies sequential decisions under changing convex losses, seeking low regret with limited feedback and constraints.
See all 73 papers