Capacity-Constrained Online Convex Optimization with Delayed Feedback

• URL: http://arxiv.org/abs/2606.11711v1
• Date: Wed, 10 Jun 2026 06:37:06 GMT
• Title: Capacity-Constrained Online Convex Optimization with Delayed Feedback
• Abstract summary: We study delayed online convex optimization (OCO) under a hard capacity constraint.<n>We find that for first-order feedback, capacity $C = (log T)$ suffices to recover standard delayed OCO rates up to logarithmic factors.<n>For bandit feedback, the regret rates are modulated by powers of $(1 + _textmax/C)$, where $_textmax$ is the maximum number of pending observations at any time.
• Score: 58.59385794080679
• License: http://creativecommons.org/licenses/by/4.0/
• 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. 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 tracking decisions and importance-weights the resulting observations. For this base problem, we propose and analyze Delayed-Weighted FTRL and its bandit analogue, establishing regret bounds that explicitly characterize the interaction between time-varying weights and delayed feedback. Combining these base learners with our schedulers yields the first 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 = Ω(\log T)$ suffices to recover standard delayed OCO rates up to logarithmic factors. For bandit feedback, the regret rates are modulated by powers of $(1 + σ_{\text{max}}/C)$, where $σ_{\text{max}}$ is the maximum number of pending observations at any time. This allows the regret bound to degrade gracefully when $C < σ_{\text{max}}$, while remaining sublinear.

Related papers

• Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization [11.872017840435428]
  We introduce a scheduler-side conditional-energy interface that separates rate adaptation from the one-point perturbation filtration.<n>Two delay vectors with identical delay multisets, $d_mathrmtot$, $_max$, and capacity can nevertheless have banditly different minimax regret showing that aggregate timing matters under curvature.
  arXiv  Detail & Related papers  (2026-08-17T07:49:51Z)
• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions [13.10320454140084]
  We study linear dueling bandits in volatile environments characterized by the simultaneous presence of post-serving contexts, delayed feedback, and adversarial corruption.<n>We propose term, which integrates a learned approximator that predicts post-serving contexts from pre-serving information.<n>Our analysis reveals an additive cost structure between corruption and delay, avoiding the multiplicative degradation typical of prior works.
  arXiv  Detail & Related papers  (2026-05-03T07:19:05Z)
• Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs [60.7808741738461]
  We study online learning with oblivious delays under a novel clairvoyance'' that limits how many past rounds can be tracked simultaneously for delayed feedback.<n>Our algorithms achieve minimax regrets across all capacity levels, with performance degrading gracefully under suboptimal capacity.
  arXiv  Detail & Related papers  (2025-03-25T17:20:39Z)
• Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
  We quantify the excess risk incurred using approximate posterior probabilities in batch binary decision-making.<n>We identify regimes where recalibration alone addresses most of the regret, and regimes where the regret is dominated by the grouping loss.<n>On NLP experiments, we show that these quantities identify when the expected gain of more advanced post-training is worth the operational cost.
  arXiv  Detail & Related papers  (2025-03-23T10:52:36Z)
• Revisiting Multi-Agent Asynchronous Online Optimization with Delays: the Strongly Convex Case [14.550539239345582]
  We revisit multi-agent asynchronous online optimization with delays, where only one of the agents becomes active for making the decision at each round.<n>We propose a delayed variant of the classical follow-the-leader algorithm, namely FTDL, which is very simple but requires the full information of functions as feedback.
  arXiv  Detail & Related papers  (2025-03-13T03:49:25Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  We propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available.<n>We show that the dynamic regret of Mild-OGD can be automatically bounded by $O(sqrtbardT(P_T+1))$ under the in-order assumption.<n>We also develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Delayed Feedback in Generalised Linear Bandits Revisited [5.349852254138085]
  We study the phenomenon of delayed rewards in generalised linear bandits in a theoretical manner. We show that a natural adaptation of an optimistic algorithm to the delayed feedback achieves a regret bound where the penalty for the delays is independent of the horizon.
  arXiv  Detail & Related papers  (2022-07-21T23:35:01Z)
• Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
  We investigate the problem of online convex optimization with unknown delays. We first extend the delayed variant of OGD for strongly convex functions. We establish a better regret bound of $O(dlog T)$, where $d$ is the maximum delay.
  arXiv  Detail & Related papers  (2021-03-21T10:16:15Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  We analyze variants of the Exp3 algorithm that tune their step-size using only information available at the time of the decisions. We obtain regret guarantees that adapt to the observed (rather than the worst-case) sequences of delays and/or losses.
  arXiv  Detail & Related papers  (2020-10-12T20:53:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.