Capacity-Constrained Online Convex Optimization with Delayed Feedback
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Capacity-Constrained Online Convex Optimization with Delayed Feedback".
Jane: Here's the gist of the paper. Online learning with delayed feedback typically assumes that the learner can track all pending rounds until their feedback arrives <ref:2606.11711#pg3>.
Tom: In this paper, we study delayed online convex optimization (OCO) under a hard capacity constraint, where at most C pending rounds can be tracked at any time <ref:2606.11711#pg6>.
Jane: Problem Setting and Notation The problem setting involves a T-round game between a player and an adversary with delayed, capacity-constrained feedback <ref:2606.11711#pg5>.
Tom: The player selects an action from a convex domain, incurs an unobserved loss, and receives feedback only at round t dt after round t <ref:2606.11711#pg5>.
Paper summary: Tom: So, wrapping up this look at Capacity-Constrained Online Convex Optimization with Delayed Feedback by Ryabchenko, Attias, and Roy. The paper shows how we can handle online learning when we have a strict limit on the number of pending rounds you can track at any time <ref:two thousand six hundred six point one one seven one one#pg5.
Jane: It tackles the issue where tracking resources are finite, and it introduces a semi-clairvoyant model to handle delays by observing expirations online instead of knowing them upfront <ref:two thousand six hundred six point one one seven one one#pg5. The main claim is that they can establish regret bounds for this setting under both convex and strongly convex losses, which is important because prior work often assumed an infinite tracking capacity <ref:two thousand six hundred six point one one seven one one#pg2.
Lu: What matters most is how they handle the interaction between the time-varying weights and the stochastic weight process induced by their scheduler <ref:two thousand six hundred six point one one seven one one#pg3. They prove that with logarithmic capacity for first-order feedback, you can match unconstrained delayed rates up to some logarithmic factors <ref:two thousand six hundred six point one one seven one one#pg6.
Meng: For us engineers, the implication is that we don't need infinite memory to perform well in these constrained settings; we just need enough capacity related to the problem complexity, and they give us a concrete way to calculate that required capacity <ref:two thousand six hundred six point one one seven one one#pg3.
Lalam: The title, Capacity-Constrained Online Convex Optimization with Delayed Feedback, points toward a specific challenge in applied machine learning where real-world constraints on memory and feedback timing are unavoidable <ref:two thousand six hundred six point one one seven one one#pg5.
Tom: It means if you're building an online system where data points arrive sporadically and you can only afford to store a fixed number of recent items, this framework gives you the mathematical tools to ensure the learning process doesn't completely derail <ref:two thousand six hundred six point one one seven one one#pg5.
Jane: So, in simple terms, they’ve shown that if you have enough capacity proportional to the complexity and use a smart scheduler to manage what you track, you can achieve good performance even when your feedback is delayed and unreliable <ref:two thousand six hundred six point one one seven one one#pg5.
Conclusion: Jane: So, to wrap up this look at "Capacity-Constrained Online Convex Optimization with Delayed Feedback," we're talking about how you handle online learning when you have a strict limit on how many rounds you can track at any one time.
Tom: Right. The authors are Ryabchenko, Attias, and Roy. Basically, they're tackling that capacity problem in online optimization where feedback is delayed and you can only keep a certain number of past actions in mind.
Lu: What they did is introduce a framework called the Delayed-Weighted Learning Framework which lets you predict an action now, take a weighted loss from it, and then get feedback later along with some weight information.
Meng: So, the core idea is that even if you can't track everything perfectly because of time or capacity constraints, this method gives you a way to make progress on convex problems.
Jane: It shows that for first-order feedback, as long as your capacity is logarithmic relative to the problem complexity, you can get rates close to what you'd get if you could track everything.
Tom: That’s a big deal because it means we don't need infinite memory just to do well in these constrained delayed settings; we just need enough memory that scales with the problem size.
Lu: And for bandit feedback, the regret rates still work, but they get modulated by some terms involving p one and sigma max. So you have to be careful if your capacity is less than sigma max because then the regret grows in a specific way.
Jane: It’s interesting how they handle that capacity constraint through this proxy delay scheduling mechanism, where you use distributions to decide whether or not to keep a round in your tracking set at any given moment.
Tom: And they even show how that scheduling works for different scenarios, like recovering the non-preemptive version of the algorithm by restricting those delay distributions.
Lu: The main implication is that this framework gives us concrete regret bounds for capacity-constrained problems under both convex and strongly convex losses, which is a solid starting point.
Meng: For me, what matters is that we have these bounds because I need to know how much memory and tracking overhead this actually requires when we try to deploy something in production.
Jane: And that leads us into the next part of the paper where they look at exactly how big those capacity-dependent terms are for strongly convex losses.
Alexander Ryabchenko, Idan Attias, Daniel M. Roy
Department of Statistical Sciences, University of Toronto · Vector Institute
cs.LG, stat.ML
Submitted: 2026-06-10
Updated: 2026-11-09
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 91/100
The gist: Online learning with delayed feedback typically assumes that the learner can track all pending rounds until their feedback arrives <ref:2606.11711#pg3>.
Key concepts
- Delayed Online Convex Optimization (OCO)
- This is an online learning problem where the player receives feedback on their actions after a time delay. The goal is to make good decisions sequentially without knowing the full future sequence of losses beforehand, making it challenging when feedback arrives late.
- Capacity Constraint (C)
- This limits the number of past rounds that can be tracked simultaneously. Instead of tracking every round, the system only keeps at most C pending rounds in memory. This constraint is crucial for managing complexity and ensuring tractability in the learning process.
- Proxy Delay Scheduling
- Since true delays are often unknown when making a prediction, this mechanism uses proxy delay distributions to decide which rounds to track. It balances the need to cover actual delays with the risk of overloading the system's capacity.
Terminology
Summary
Online learning with delayed feedback typically assumes that the learner can track all pending rounds until their feedback arrives <ref:2606. p. 0 Capacity-Constrained Online Convex Optimization
with Delayed Feedback
Alexander Ryabchenko* Idan Attias † Daniel M. Roy‡
Abstract
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 untracked rounds is permanently lost. In this paper, we study delayed online convex optimization (OCO) under a hard capacity constraint, where at most
C pending rounds can be tracked at any time.Where the paper says it
Where the paper says it
Problem Setting and Notation
The problem setting involves a T-round game between a player and an adversary with delayed, capacity-constrained feedback <ref:2606.11711#pg5>. The player selects an action from a convex domain, incurs an unobserved loss, and receives feedback only at round t dt after round t <ref:2606. p. 0 This allows the regret bound to degrade gracefully when C ă σmax, while remaining sublinear. 1 Introduction
Online convex optimization is a canonical framework for sequential decision-making under uncertainty [Haz16,
Ora19]: a player repeatedly selects an action from a convex domain, incurs a convex loss, and receives either full
gradient information (first-order feedback) or only the incurred scalar loss (bandit feedback). A natural example
arises in clinical trials: a study can actively monitor only a bounded number of patients at any given time, and
outcomes are observed only for the patients selected for monitoring — side effects may still manifest in unmonitored
patients, but the trial never observes them. [RAR25] formalized this limitation as a hard capacity constraint, capping
the number of tracked rounds by a capacity parameter C, and studied it in the multi-armed bandit setting. The bandit setting is substantially
more challenging even without delays or capacity constraints, as the player must optimize over a continuous domain
from scalar loss observations alone. Moreover, we relax the clairvoyant delay model of prior work, which assumes
delays are known at prediction time; our framework instead reveals delays only upon their expiration, matching the
information available in standard delayed online learning.Where the paper says it
Where the paper says it
Where the paper says it
Delayed-Weighted Learning Framework
The paper introduces a weighted variant of OCO with delayed feedback that serves as the foundation for reductions in subsequent sections <ref:2606.11711#pg4>. This framework involves predicting an action, incurring a weighted loss, and receiving feedback at round t dt along with the weight wt <ref:2606. p. 4 At each round t, the player predicts xt P K and incurs the weighted loss wtftpxtq. The feedback for round t is
revealed at the end of round t ` dt, together with the weight wt. Starting from x1 P K, delayed-weighted FTRL (DW-FTRL) updates are given by
DW-FTRL: xt`1 “ arg min
xPK
xx, ř
sPOt`1
ws∇fspxsqy ` řt
s“1
αs
2
}xs´x}
2
. (1)
Each update aggregates the weighted gradients revealed so far and regularizes against the running sequence of
iterates.Where the paper says it
Where the paper says it
Proxy Delay Scheduling Mechanism
To handle delays that are unknown at prediction time, the paper introduces a unified framework for proxy delay scheduling <ref:2606.11711#pg5>. This scheduler uses proxy delay distributions D to determine a round's lifetime in the tracking set S, adding the current round only if its proxy delay is non-negative and capacity allows <ref:2606.11711#pg5>. The choice of D navigates a tradeoff between covering true delays and risking saturation <ref:2606. p. 6 , |St| ă C). The choice of D navigates a fundamental tradeoff:
heavier-tailed distributions are more likely to cover true delays but keep rounds in S longer, risking saturation.Where the paper says it
Regret Guarantees for Capacity Constraints
The main results establish regret guarantees for capacity-constrained OCO and BCO under convex and strongly convex losses <ref:2606.11711#pg10>. For first-order feedback, logarithmic capacity suffices to match unconstrained delayed rates up to logarithmic factors <ref:2606. p. 1 Combining the delayed-weighted regret bounds with the
proxy-delay schedulers yields regret guarantees for capacity-constrained OCO and BCO; see Table 1. For first-order feedback, capacity C “ Ωplog Tq suffices to match the optimal unconstrained rates in terms of
the total delay dtot and the maximum number of pending observations σmax, up to logarithmic factors, since
σmax ď
? For first-order feedback, capacity C “ Ωplog Tq suffices
to recover standard delayed OCO rates up to logarithmic factors. For bandit feedback, the regret rates are
modulated by powers of p1 ` σmax{Cq, where σmax is the maximum number of pending observations at any time.Where the paper says it
Where the paper says it
Capacity-Dependent Regret Bounds
The capacity constraint enters the dimension-dependent terms through factors of p1 σmax in the convex case and p1 σmax(C/4) in the strongly convex case <ref:2606.11711#pg3>. The delay-dependent terms match the optimal σmax scaling of [RAR26] in the strongly convex case, while for convex losses they scale as? p. 1 For bandit feedback in dimension k, the capacity constraint enters the dimension-dependent
terms through factors of p1 ` σmax{Cq
1{4
in the convex case and p1 ` σmax{Cq
1{3
in the strongly convex case,
so the bounds degrade gracefully as capacity decreases. The delay-dependent terms match the optimal σmax
scaling of [RAR26] in the strongly convex case; for convex losses they scale as ? The delay-dependent terms match the optimal σmax
scaling of [RAR26] in the strongly convex case; for convex losses they scale as ? T σmax rather than ? T σmax rather than ? dtot, but
still improve over the ? dtot, but
still improve over the ? T dmax dependence of [WYSZ24a], since σmax ď dmax.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Doubling Trick and Epoch Structure
The strong convexity and bandit results require tuning with knowledge of σmax, which may not be available in advance, necessitating a doubling over σmax <ref:2606.11711#pg9>. The epoch structure involves restarting the base algorithm when the observed backlog exceeds a guess Sj, leading to a regret bound that depends on log pσmax(C/4) <ref:2606.11711#pg9>.
Non-Preemptive Framework Equivalence
The framework recovers the non-preemptive variant by restricting the support of proxy delay distributions Dt to t−1 Y t8u, ensuring that each round is either rejected outright or committed until feedback delivery <ref:2606.11711#pg3>. Since both schedulers satisfy the same saturation and weight moment bounds as their preemptive counterparts, combining them yields identical regret guarantees in the non-preemptive setting <ref:2606. p. 1 There is also a non-preemptive variant of the problem, in which once a round
is tracked, it cannot be dropped until its feedback is delivered. Several of our schedulers are non-preemptive by
construction and achieve analogous guarantees in this setting; see Appendix G.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Capacity-Constrained Online Convex Optimization with Delayed Feedback (OCO) can be solved in continuous domains with convex and strongly convex losses by utilizing a proxy-delay scheduling wrapper that randomizes tracking decisions and importance-weights observations. This allows for regret guarantees explicitly dependent on capacity C, such as
For first-order feedback, capacity C Omegaplog Tq suffices to recover standard delayed OCO rates up to logarithmic factors.
-
The system can handle bandit feedback by employing a delayed-weighted Follow-The-Bandit-Leader (DW-FTBL) update that utilizes single-point estimators derived from smoothed surrogates. This provides regret bounds that account for the interaction between time-varying weights and delayed feedback, such as the term involving
cross term kMwt Gdelta t p r sPBt w 2 s q 1/2
. -
The capacity constraint is managed by a unified proxy-delay scheduler, which uses distributions like the Bernoulli or Pareto scheduler to control the saturation probability of tracking set size. This allows for the bounding of
PpSt is Cq
with high probability, leading to regret bounds thatdegrade gracefully when C ă sigma max
. -
The system can be adapted for varying knowledge about maximum backlog by using a doubling trick over maximum backlog, which avoids needing prior knowledge of sigma max. This enables the use of learning rates and smoothing parameters that depend on problem quantities such as
dtot and T
instead of requiringsigma max
.
Abstract
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 C 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 = Ω(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) factors, where σ max is the maximum number of outstanding observations. This allows the regret bound to degrade gracefully when C < σ max. We complement our analysis with numerical experiments.
Sources
- An optimal algorithm for bandit convex optimization
- Bandit Convex Optimisation
- Online Learning: A Modern Introduction Using Convex Optimization
- Decentralized Online Convex Optimization with Unknown Feedback Delays
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- 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