Research map / Bandits and online learning / Online convex optimization and games
A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces a continuous-time model for delayed feedback and a black-box reduction from delayed OCO/BCO to drift-penalized online linear optimization, improving bandit convex optimization regret bounds and recovering first-order state-of-the-art bounds.
Problem
Online convex optimization and bandit convex optimization with round-dependent delayed feedback, where existing reductions require advance knowledge of delays/horizon, have memory overhead, or are limited to full information.
Approach
Model predictions and observations as events on a continuous timeline; regret decomposes into non-delayed regret on observation-ordered losses plus a prediction-drift penalty; a wrapper feeds observation-ordered gradients (or single-point bandit estimates) with dual-delays and dual-backlogs to any drift-penalized OLO algorithm such as P-FTRL or OMD.
Key results
- Bandit convex OCO with delays: regret O(sqrt(d_tot) + T^{3/4} sqrt(k)), improving delay term from sqrt(T d_max) of prior work.
- Strongly convex bandit case: delay term improved from d_max ln T to min{sigma_max ln T, sqrt(d_tot)}.
- First-order OCO with delays: recovers O(sqrt(d_tot)+sqrt(T)) and strongly convex O(min{sigma_max ln T, sqrt(d_tot)} + ln T) bounds with a unified, delay-adaptive analysis.
Limitations
- Analysis assumes an oblivious adversary fixing losses and delays in advance.
- Bounds for bandit feedback hold in expectation and rely on smoothing with a bias term.
- Strongly convex bandit bound retains a non-matching additive term and a log factor relative to the sigma_max bound.
Experimental setup
Metrics: regret bound
Baselines: delayed bandit gradient descent blocking-based delayed BCO algorithm delayed gradient descent for OCO
Builds on: P-FTRL online mirror descent single-point gradient estimation (Flaxman et al.) skipping scheme for delayed OCO
Closest papers by meaning
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.94)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.93)
- Exploiting Curvature in Online Convex Optimization with Delayed Feedback (ICML 2025 · similarity 0.93)
- Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting (AAAI 2025 · similarity 0.92)
- Non-stationary Online Convex Optimization with Arbitrary Delays (ICML 2024 · similarity 0.91)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.