cs.LGFeb 2, 2026

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

Authors: Alexander Ryabchenko, Idan Attias, Daniel M. Roy

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 O(dtot+T34k)O(\sqrt{d_{\text{tot}}} + T^{\frac{3}{4}}\sqrt{k}) regret, improving the delay-dependent term from O(min⁡{Tdmax,(Tdtot)13})O(\min\{\sqrt{T d_{\text{max}}},(Td_{\text{tot}})^{\frac{1}{3}}\}) in prior work to O(dtot)O(\sqrt{d_{\text{tot}}}). Here, kk, TT, dmaxd_{\text{max}}, and dtotd_{\text{tot}} denote the dimension, time horizon, maximum and total delay, respectively. Under strong convexity, we achieve O(min⁡{σmaxln⁡T,dtot}+(T2ln⁡T)13k23)O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\} + (T^2\ln T)^{\frac{1}{3}} {k}^{\frac{2}{3}}), improving the delay-dependent term from O(dmaxln⁡T)O(d_{\text{max}} \ln T) to O(min⁡{σmaxln⁡T,dtot})O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\}), where σmaxσ_{\text{max}} denotes the maximum number of outstanding observations and may be considerably smaller than dmaxd_{\text{max}}.

Figures & tables

Explore similar work

CardsList
  1. Capacity-Constrained Online Convex Optimization with Delayed Feedback

    Jun 10, 2026Alexander Ryabchenko, Idan Attias, Daniel M. RoyOnline Convex OptimizationBandit Convex Optimization

  2. Universal Online Convex Optimization With Delayed Feedback

    Oct 20, 2026Hao Qiu, Andrew Jacobsen, Emmanuel Esposito +1Online Convex Optimization

  3. Near-Optimal Stochastic Linear Bandits with Delay

    Jun 15, 2026Ofir Schlisselberg, Mengxiao Zhang, Yishay MansourBandits with Delayed FeedbackContextual Bandits