A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees
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
- Delayed Bandits: When Do Intermediate Observations Help?
- Online convex optimization in the bandit setting: gradient descent without a gradient
- An optimal algorithm for bandit convex optimization
- Slow Learners are Fast
- Bandit Convex Optimisation
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback
- Online Learning: A Modern Introduction Using Convex Optimization
- Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Related papers
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis
- (Mis)generalization of Helpful-Only Fine-tuning