arXiv:2608.16216cs.LG2026-08

提出新调度机制,让有限反馈容量下的延迟优化更高效。

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

  • 引入条件能量接口,分离速率调整与扰动过滤
  • 延迟项仅依赖显式重启因子,性能逼近最优
  • 揭示时间分布对优化效果的关键影响,适合算法设计者

当学习者只能追踪 $C$ 个未完成的反馈项且丢弃反馈永久丢失时,如何定义合适的延迟复杂度?现有单点贝叶斯凸优化保证中延迟项为 $\ oot2\of{Tσ_{ ext{max}}} $,其中 $σ_{ ext{max}}$ 为峰值积压;而无限追踪下可达到 $\ oot2\of{d_{\mathrm{tot}}} $ 的更优依赖。本文引入调度端的条件能量接口,将速率自适应与单点扰动滤波解耦,并处理随机准入带来的依赖重要权重。在相同半先知预言机和路径硬容量约束下,该方法实现无需调参的学习器,延迟项为 $O(\ oot2\of{E_C d_{\mathrm{tot}}} )$,仅显式依赖重启因子 $E_C$;公开常数倍峰值界可消除该因子,而 $d_{\mathrm{tot}}$ 仍未知。强凸情形下,时间成本为 $H_A(d)=\\\ rac{σ_t}{A+t} $。两个延迟向量即使拥有相同的延迟多重集、$d_{\mathrm{tot}}$、$σ_{\max}$ 及容量,其极小最大遗憾仍可能呈多项式差异,表明在曲率存在时时机至关重要。最后,连续硬族将追踪容量转化为零阶查询预算,给出互补的容量枯竭下界。上界要求 $C \ge \ln T + 1$,但不构成完整的容量极小最大刻画。

原文摘要 · Abstract (English)

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 $\sqrt{Tσ_{\max}}$, where $σ_{\max}$ is the peak backlog, although unlimited tracking admits the sharper $\sqrt{d_{\mathrm{tot}}}$ 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(\sqrt{E_C d_{\mathrm{tot}}})$, with only an explicit restart factor $E_C$; a public constant-factor peak bound removes this factor while $d_{\mathrm{tot}}$ remains unknown. Under strong convexity, the same interface yields the temporal cost $H_A(d)=\sum_t σ_t/(A+t)$. Two delay vectors with identical delay multisets, $d_{\mathrm{tot}}$, $σ_{\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\ge \ln T+1$ and do not constitute a complete capacity minimax characterization.

在线学习延迟优化凸优化调度机制

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。