mlsanityData to 14 Oct 2026

Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization

arXiv 2608.16216 ↗First posted 17 Aug 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

What is the right delay complexity when a learner can track only C pending feedback items and discarded feedback is permanently lost? Existing one-point bandit convex optimization guarantees in this model pay √Tσmax, where σmax is the peak backlog, although unlimited tracking admits the sharper √dtot dependence on total delay. We introduce a scheduler-side conditional-energy interface that separates rate adaptation from the one-point perturbation filtration and handles the dependent importance weights created by randomized admission. Under the same semi-clairvoyant oracle and pathwise hard-capacity contract, this yields an untuned learner whose delay term scales as O(√EC dtot), with only an explicit restart factor EC; a public constant-factor peak bound removes this factor while dtot remains unknown. Under strong convexity, the same interface yields the temporal cost HA(d)=sumt σt/(A+t). Two delay vectors with identical delay multisets, dtot, σmax, and capacity can nevertheless have polynomially different minimax regret, showing that timing matters under curvature even when aggregate delay summaries agree. Finally, a continuous hard family converts tracking capacity into a zeroth-order query budget and gives a complementary capacity-starvation lower endpoint. The upper bounds require C≥ ln T+1 and do not constitute a complete capacity minimax characterization.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 21 of its 43 references that are in the map. First posted on arXiv 17 Aug 2026.

Builds on

21 of 43 references.

References · 21

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  3. 2013Online Learning under Delayed Feedbackcited by 141
  4. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
  5. 2016Scale-Free Online Learningcited by 85
  6. 2015Online Learning with Feedback Graphs: Beyond Banditscited by 80
  7. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
  8. 2016Kernel-based methods for bandit convex optimizationcited by 63
  9. 2019Nonstochastic Multiarmed Bandits with Unrestricted Delayscited by 46
  10. 2019An Optimal Algorithm for Adversarial Bandits with Arbitrary Delayscited by 44
  11. 2020Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisationcited by 33
  12. 2020Adapting to Delays and Data in Adversarial Multi-Armed Banditscited by 29
9 more
  1. 2016An optimal algorithm for bandit convex optimizationcited by 20
  2. 2021No Weighted-Regret Learning in Adversarial Bandits with Delayscited by 12
  3. 2024Online Newton Method for Bandit Convex Optimisationcited by 12
  4. 2024Improved Regret for Bandit Convex Optimization with Delayed Feedbackcited by 8
  5. 2025Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offscited by 6
  6. 2025Exploiting Curvature in Online Convex Optimization with Delayed Feedbackcited by 6
  7. 2024Adversarial Online Learning with Temporal Feedback Graphscited by 3
  8. 2026A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guaranteescited by 3
  9. 2026Capacity-Constrained Online Convex Optimization with Delayed Feedbackcited by 1

Built on by

Not cited yet.