A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees

arXiv:2602.02634 · cs.LG · Submitted 2026-02-02 · Read on arXiv

cs.LG

Submitted: 2026-02-02

Updated: 2026-11-09

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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.

Terminology

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 O(sqrt d tot + T 3 over 4 sqrt k) regret, improving the delay-dependent term from O(sqrt T d max,(Td tot) 1 over 3) in prior work to O(sqrt d tot). Here, k, T, d max, and d tot denote the dimension, time horizon, maximum and total delay, respectively. Under strong convexity, we achieve O(σ max T, sqrt d tot + (T squared T) 1 over 3 k 2 over 3), improving the delay-dependent term from O(d max T) to O(σ max T, sqrt d tot), where σ max denotes the maximum number of outstanding observations and may be considerably smaller than d max.

Sources

Related papers