Research map / Bandits and online learning / Online convex optimization and games
Capacity-Constrained Online Convex Optimization with Delayed Feedback
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.
Studies delayed OCO and BCO under a hard tracking-capacity constraint, introducing a semi-clairvoyant model, delayed-weighted FTRL/FTBL base learners, and proxy-delay schedulers that yield regret bounds for capacity-constrained OCO and BCO.
Problem
Delayed online convex optimization where the learner can track at most C pending rounds; untracked feedback is permanently lost, and delays are revealed only upon expiration (semi-clairvoyant).
Approach
Reduce capacity-constrained delayed OCO/BCO to a delayed-and-weighted OCO/BCO problem via a randomized proxy-delay scheduler that importance-weights observations; a new Bernoulli scheduler calibrated to max backlog yields uniform weights, and DW-FTRL / DW-FTBL handle the resulting weighted delayed feedback.
Key results
- First-order convex regret O(GD sqrt(d_tot + T)) with capacity C >= ln T + 1 via Pareto scheduler, matching unconstrained delayed rates.
- Strongly convex first-order regret O((G^2/lambda)(sigma_max+1) ln T) under capacity C >= ln T + 1.
- Bandit convex regret O(GD(sqrt(T sigma_max) + T^{3/4}(1+sigma_max/C)^{1/4} sqrt(nu k))) with capacity-dependent degradation factor.
Limitations
- Bandit convex-case delay term scales as sqrt(T sigma_max) rather than the optimal sqrt(d_tot) of the unconstrained setting.
- Bernoulli scheduler requires knowledge of sigma_max (removed via doubling trick in appendix).
- Analysis restricted to oblivious adversaries.
Experimental setup
Metrics: regret
Baselines: unconstrained delayed OCO (C = infinity) delayed BCO (Joulani et al.-style reduction)
Builds on: Pareto proxy-delay scheduler (capacity-constrained experts/bandits) delayed FTRL reduction single-point bandit gradient estimator scale-free online learning
Closest papers by meaning
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.94)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.92)
- Exploiting Curvature in Online Convex Optimization with Delayed Feedback (ICML 2025 · similarity 0.92)
- Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting (AAAI 2025 · similarity 0.91)
- Non-stationary Online Convex Optimization with Arbitrary Delays (ICML 2024 · similarity 0.90)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 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.