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

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^{\frac{3}{4}}\sqrt{k}) regret, improving the delay-dependent term from O(\min{\sqrt{T d_{max}},(Td_{tot})^{\frac{1}{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(\min{σ_{max} \ln T, \sqrt{d_{tot}}} + (T^2\ln T)^{\frac{1}{3}} {k}^{\frac{2}{3}}), improving the delay-dependent term from O(d_{max} \ln T) to O(\min{σ_{max} \ln T, \sqrt{d_{tot}}}), where σ_{max} denotes the maximum number of outstanding observations and may be considerably smaller than d_{max}.