Capacity-Constrained Online Convex Optimization with Delayed Feedback

arXiv:2606.11711 · cs.LG, stat.ML · Submitted 2026-06-10 · Read on arXiv

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

Where the paper says it

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.

11711#pg3>. 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. p. 0
Where the paper says it

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.

11711#pg6>.

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

Where the paper says it

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).

11711#pg5>. The capacity constraint caps the number of tracked rounds by C <ref:2606. p. 0
Where the paper says it

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.

11711#pg5>. The framework distinguishes between a clairvoyant model, where delays are known at the start of each round, and a semi-clairvoyant model, where delays are only revealed upon expiration <ref:2606. p. 0
Where the paper says it

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.

11711#pg5>.

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

Where the paper says it

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.

11711#pg4>. For first-order feedback, Delayed-Weighted Follow-The-Regularized-Leader (DW-FTRL) updates are defined by aggregating weighted gradients and regularizing against a running sequence of iterates <ref:2606. p. 5
Where the paper says it

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.

11711#pg7>.

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

Where the paper says it

, |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.

11711#pg9>.

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

Where the paper says it

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 ď ?

11711#pg6>. For bandit feedback, the regret rates are modulated by powers of p1 σmax, allowing for graceful degradation when C is less than σmax <ref:2606. p. 0
Where the paper says it

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.

11711#pg6>.

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

Where the paper says it

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 ?

T σmax rather than? p. 1
Where the paper says it

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 ?

dtot, but still improve over the? p. 1
Where the paper says it

T σmax rather than ? dtot, but still improve over the ?

T dmax dependence of [WYSZ24a] <ref:2606. p. 1
Where the paper says it

dtot, but still improve over the ? T dmax dependence of [WYSZ24a], since σmax ď dmax.

11711#pg6>.

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

Where the paper says it

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.

11711#pg9>.

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

  1. 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.

  2. 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.

  3. 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 that degrade gracefully when C ă sigma max.

  4. 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 requiring sigma 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

Related papers