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

Jun 10, 2026

Capacity-Constrained Online Convex Optimization with Delayed Feedback

Online learning with delayed feedback typically assumes that the learner can track all pending rounds until their feedback arrives. In practice, tracking resources are finite, and feedback from rounds that cannot be tracked is permanently lost. In this paper, we study delayed online convex optimization (OCO) under a hard capacity constraint, where at most CC pending rounds can be tracked at any time. To model delay information, we introduce a semi-clairvoyant model that refines the clairvoyant assumption from prior work: rather than requiring delays to be known at prediction time, the learner observes delay expirations online, consistent with the classical unconstrained delayed setting. Our approach proceeds via a reduction to a novel ``delayed and weighted'' OCO problem, using a scheduler that randomizes which rounds are tracked and importance-weights the resulting observations. For the base problem, we propose and analyze Delayed-Weighted FTRL and its bandit analogue, obtaining regret bounds that characterize how weights interact with delayed feedback in both settings. Combining these bounds with our schedulers yields regret guarantees for capacity-constrained OCO under convex and strongly convex losses, for both first-order and bandit feedback. For first-order feedback, capacity C=Ω(log⁡T)C = Ω(\log T) suffices to recover the standard delayed OCO rates up to logarithmic factors. For bandit feedback, the standard delayed BCO rates are instead modulated by (1+σmax/C)(1 + σ_{\text{max}}/C) factors, where σmaxσ_{\text{max}} is the maximum number of outstanding observations. This allows the regret bound to degrade gracefully when C<σmaxC < σ_{\text{max}}. We complement our analysis with numerical experiments.
Oct 20, 2026

Universal Online Convex Optimization With Delayed Feedback

We study universal online convex optimization with delayed feedback. We develop a single algorithm that simultaneously adapts to general convex, strongly convex, and exp-concave losses without prior knowledge of the curvature class or parameters. Our regret bounds match the best known dependence on the time horizon TT and delays up to doubly logarithmic factors: roughly T+dtot\sqrt{T + d_{\mathrm{tot}}} for convex losses and σmax⁡log⁡Tσ_{\max}\log T rates with curved losses, where dtotd_{\mathrm{tot}} is the total cumulative delay and σmax⁡σ_{\max} is the maximum number of simultaneously missing observations. Our main technical contribution is a delayed meta-learner with a second-order excess-loss guarantee, which enables curvature-adaptive aggregation of delayed base learners. In addition, our new exp-concave base learner yields a sharper regret bound which improves the state-of-the-art delay dependence by replacing the maximum delay with the potentially much smaller σmax⁡σ_{\max}, while retaining the complementary dtot\sqrt{d_{\mathrm{tot}}} dependence.
Jun 15, 2026

Near-Optimal Stochastic Linear Bandits with Delay

We study stochastic linear bandits with delayed feedback under several delay models and establish near-optimal regret guarantees. Our results identify when delayed linear bandits exhibit the same qualitative behavior as multi-armed bandits (MAB), and when the linear structure creates fundamentally new challenges. Specifically, (1) for loss-independent delays, where the delay does not depend on the realized loss (but potentially depends on the arm), we show that delays incur only an additive regret penalty. Under stochastic delays, this penalty scales with the expected delay, while under adversarial delays, it scales with the maximum number of outstanding observations. Notably, both delay penalties are dimension-free, improving upon the state-of-the-art results; (2) for loss-dependent delays, we show that linear bandits are substantially harder than MAB: unlike in MAB, we prove matching (up to log factors) upper and lower bounds in linear bandits, whose delay penalty depends on the square root of the dimension. (3) for the delay-as-payoff model, a special case of loss-dependent delay, we show that the optimal MAB guarantee, which depends only on the delay of the optimal arm, is also unattainable in linear bandits. Together, these results provide a sharp characterization of how delayed feedback interacts with linear generalization.