Capacity-Constrained Online Convex Optimization with Delayed Feedback¶

会议: NeurIPS 2026
arXiv: 2606.11711
领域: 优化/理论
关键词: 在线凸优化, 延迟反馈, 容量约束, 强凸优化, 无导数凸优化 (BCO)

一句话总结¶

本文首次研究了具有有限追踪容量 $C$ 的延迟在线凸优化（OCO 与 BCO）问题，提出将原问题约化为带有重要性权重的延迟优化子问题，结合新型代理延迟调度机制，证明了在 $C=\Omega(\ln T)$ 的极小容量下即可达到近乎无约束时的最优后悔界。

研究背景与动机¶

在线凸优化（OCO）及其无导数变体（Bandit Convex Optimization, BCO）是序贯不确定决策的核心数学框架。在现实工业系统（如临床试验中的受试者监护、异步分布式训练中的参数延迟聚合以及排队服务系统）中，决策所产生的损失或梯度反馈往往无法实时返回，而是带有任意未知的延迟时间 $d_t$。长久以来，绝大多数延迟在线学习的文献均默认玩家拥有无限的存储与追踪容量，即假设玩家能够同时悬挂追踪任意数量的未决轮次，直至其反馈最终送达。

然而在真实硬件与管理约束下，能够被并发追踪的未决轮次数量上限必然受到物理容量 $C$ 的硬性约束。一旦未决任务超出容量 $C$，未被追踪轮次的反馈将被永久丢弃。这种容量瓶颈在离散的多臂老虎机（MAB）设定中虽有初步探讨，但在连续凸域的 OCO 与 BCO 场景中却存在本质理论障碍：无导数单点梯度估计具有极大的方差，若重要性权重随时间剧烈波动，会导致估计方差以高阶累积发散；同时，先前工作依赖在预测时已知延迟时长的全知假定（Clairvoyant Delay），与经典延迟学习仅在反馈到达时获知延迟的实际设定严重脱节。

本文的核心 idea 是构建一套通用的“代理延迟调度器-带权延迟基础学习器”解耦约化框架：利用随机化代理延迟调度机制将硬性容量限制转化为样本到达过程的重要性加权，引入针对积压峰值 $\sigma_{\max}$ 校准的均匀伯努利调度消除权重波动，并在带权延迟 FTRL/FTBL 算法中精确控制延迟重叠交叉项与梯度估计方差，从而在 $C=\Omega(\ln T)$ 乃至强凸与 Bandit 条件下获得紧致的容量依赖型后悔界。

方法详解¶

整体框架¶

本文的方法 pipeline 采用模块化解耦约化设计，将面临硬容量约束 $C$ 的半先知延迟 OCO/BCO 游戏分解为两层架构：上层的“代理延迟调度器（Scheduler Wrapper $\mathcal{W}(\mathcal{A}, \mathfrak{D})$）”与底层的“带权延迟基础学习器（Base Learner $\mathcal{A}$）”。调度器在每轮做出动作后，通过采样代理生存期 $d'_t \sim \mathfrak{D}_t$ 来管理容量至多为 $C$ 的追踪集合 $\mathcal{S}$，对未追踪或提前超时的轮次输出补齐零反馈，对成功捕获反馈的轮次赋予逆概率重要性权重 $w_t = 1/\mathbb{P}(d'_t \ge d_t)$；底层基础学习器则运行专门设计的 DW-FTRL 或 DW-FTBL 算法，吸收带权梯度并动态更新决策。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["环境输入与决策预测<br/>玩家选择动作 x_t，产生未知损失与延迟"] --> B["代理延迟采样与追踪维护<br/>根据代理分布采样 d'_t 决定准入与抢占淘汰"]
    B --> C["带权重要性反馈流构造<br/>成功捕获赋予逆概率权重，未捕获转发零占位"]
    C --> D["带权延迟正则化决策更新<br/>DW-FTRL / DW-FTBL 聚合带权历史梯度并正则化更新"]

关键设计¶

1. 代理延迟采样与追踪维护：以随机代理生存期规避容量溢出饱和 面对容量上限 $C$，传统贪心追踪策略在面对长尾延迟脉冲时会立刻将容量耗尽，导致后续大量新轮次被机械丢弃。本文引入代理延迟分布 $\mathfrak{D} = (\mathfrak{D}_t)_{t=1}^T$，每轮入队时独立采样代理生存期 $d'_t$。若当前追踪集未满且 $d'_t \ge 0$，则将轮次加入 $\mathcal{S}$；若在 $t + d'_t + 1$ 时真实反馈尚未返回，则主动抢占（Preempt）将其移出，释放容量给新轮次。当代理分布满足以下均值约束条件时： $$\sum_{s \in \mathcal{B}_t \cup \{t\}} \mathbb{P}(d'_s \ge t - s) \le \frac{C}{8}, \quad \forall t \in [T]$$ 根据 Chernoff 界，追踪集发生容量溢出的饱和概率被指数级压制为 $\mathbb{P}(|\mathcal{S}_t| = C) \le \exp(-C)$。只要容量 $C \ge \ln T + 1$，全时段累计的容量溢出风险对后悔界的影响仅为一个常数项 $GD$。针对凸 OCO，设计了截断 Pareto 分布调度器（Corollary 4.4），适应单轮延迟 $d_t$；而针对强凸及 Bandit 设定，设计了新型均匀伯努利调度器（Corollary 4.5），设定 $p = \min\{1, \frac{C}{8(\sigma_{\max}+1)}\}$，以固定概率赋予 $d'_t = \infty$，从而在全时段维持恒定观测权重 $w_t \equiv 1/p$。

2. 带权延迟正则化决策更新：DW-FTRL 与 DW-FTBL 算法架构 在接收到底层调度器传递的非均匀带权延迟反馈流后，基础学习器必须稳健更新且不被权重方差冲垮。针对一阶反馈，DW-FTRL 维护累积加权历史观测集合 $\mathcal{O}_{t+1} = \{s \in [t]: s + d_s \le t\}$ 并施加动态步长正则化： $$x_{t+1} = \arg\min_{x \in \mathcal{K}} \left\{ \langle x, \sum_{s \in \mathcal{O}_{t+1}} w_s \nabla f_s(x_s) \rangle + \sum_{s=1}^t \frac{\alpha_s}{2} \|x_s - x\|^2 \right\}$$ 其中正则化增量 $\alpha_s = 1/\eta_s - 1/\eta_{s-1}$。其带权后悔严格分解为对角权重平方项与积压重叠交叉项 $w_t \sum_{s \in \mathcal{B}_t} w_s$。对于 Bandit 反馈（DW-FTBL），算法在收缩域上对中心点 $y_t$ 施加球面上均匀扰动 $x_t = (1 - \delta_t/r)y_t + \delta_t u_t$，利用单点损失构建无偏梯度估计量 $\widehat{g}_t = \frac{k}{\delta_t} f_t(x_t) u_t$，并通过中心点投影更新消除扰动漂移。

3. 最大积压量自适应倍增机制：无需预知先验信息的大步长延拓 伯努利调度器及 Bandit 步长依赖于最大未决积压量 $\sigma_{\max} = \max_t |\mathcal{B}_t|$（满足 $\sigma_{\max} \le \min\{d_{\max}, \sqrt{2 d_{\mathrm{tot}}}\}$）。为了避免预先获知 $\sigma_{\max}$，本文提出了针对积压峰值的倍增机制（Doubling Trick）。算法划分为若干 Epoch $j = 0, 1, \dots, J$，令第 $j$ 轮的积压上限猜测为 $S_j = 2^j - 1$。一旦观测到的未决积压超过 $S_j$，立即重置当前追踪集合并进入下一 Epoch，将参数重新校准到 $S_{j+1}$。由于后悔界中关于 $\sigma_{\max}$ 的主要依赖项阶数 $b_m > 0$（如 $\sigma_{\max} \ln T$ 或 $(1 + \sigma_{\max}/C)^{1/4}$），几何级数求和 $\sum_{j=0}^J 2^{b_m j} = O((\sigma_{\max}+1)^{b_m})$ 能够自动吸收分段重启代价，从而使算法在完全无需先验信息的前提下依然达到理论最优率。

实验关键数据¶

本文为纯理论突破论文，其核心贡献体现在对 OCO 和 BCO 在容量限制下的后悔理论上界的严谨推导与建立。下面两张表格汇总了论文 Theorem 5.1 和 Theorem 5.2 给出的容量约束下紧致后悔界，并与无容量限制（$C=\infty$）下的前沿基线进行严格对比。

主实验：容量约束下 OCO 与 BCO 的理论后悔界对比（与无约束基线对比）¶

设定与损失函数类型	维度/延迟指标	无约束基线 ($C = \infty$)	本文容量约束上界 ($C = \Omega(\ln T)$)	容量衰减因子 / 匹配结论
一阶 OCO (凸损失)	$T, d_{\mathrm{tot}}$	$O(\sqrt{d_{\mathrm{tot}}} + \sqrt{T})$ [Quanrud & Khashabi, 2015]	$\mathcal{O}(GD\sqrt{d_{\mathrm{tot}} + T})$	仅需 $C \ge \ln T + 1$ 即可完全无损匹配无约束率
一阶 OCO ($\lambda$-强凸损失)	$T, \sigma_{\max}$	$O(\sigma_{\max}\ln T + \ln T)$ [Qiu et al., ICML 2025]	$\mathcal{O}(\frac{G^2}{\lambda}(\sigma_{\max} + 1)\ln T)$	匹配无约束极小极大率 $\Theta((\sigma_{\max}+1)\ln T)$
Bandit BCO (凸损失)	$T, k, \sigma_{\max}$	$O(\sqrt{T d_{\max}} + T^{3/4}\sqrt{k})$ [Wan et al., NeurIPS 2024]	$\mathcal{O}(GD(\sqrt{T\sigma_{\max}} + T^{3/4}(1 + \frac{\sigma_{\max}}{C})^{1/4}\sqrt{\nu k}))$	依赖更优的 $\sigma_{\max} \le d_{\max}$，容量降至 $C$ 时平滑退化
Bandit BCO ($\lambda$-强凸损失)	$T, k, \sigma_{\max}$	$O(\sigma_{\max} + T^{2/3}k^{2/3})$ [Ryabchenko et al., 2026]	$\mathcal{O}(\frac{G^2}{\lambda}(\sigma_{\max}\ln T + (T^2\ln T)^{1/3}(1 + \frac{\sigma_{\max}}{C})^{1/3}(\nu k)^{2/3}))$	达到次线性 $T^{2/3}$ 依赖，容量乘子仅为 $(1 + \frac{\sigma_{\max}}{C})^{1/3}$

消融与参数分析：调度机制与抢占模式对后悔界的影响¶

调度器配置 / 假设场景	适用损失设定	观测概率 $p_t$ 形式	容量饱和风险概率 $\mathbb{P}(\\|\mathcal{S}_t\\|=C)$	后悔界关于关键参数的依赖阶数
Pareto 调度器 (抢占式)	凸 OCO	$\min\{1, \frac{C}{16 H_t (d_t + 1)}\}$	$\le \exp(-C)$ (由 Chernoff 保证)	$\mathcal{O}(\sqrt{d_{\mathrm{tot}} + T})$，自适应单轮时变延迟 $d_t$
Bernoulli 调度器 (非抢占式)	强凸 OCO	$p = \min\{1, \frac{C}{8(\sigma_{\max} + 1)}\}$	$\le \exp(-C)$	$\mathcal{O}((\sigma_{\max} + 1)\ln T)$，权重恒定为 $1/p$ 避免强凸项发散
Bernoulli 调度器 (Bandit)	凸 BCO	$p = \min\{1, \frac{C}{8(\sigma_{\max} + 1)}\}$	$\le \exp(-C)$	$\mathcal{O}(\sqrt{T\sigma_{\max}} + T^{3/4}(1 + \frac{\sigma_{\max}}{C})^{1/4}\sqrt{k})$
Bernoulli 调度器 (强凸 Bandit)	强凸 BCO	$p = \min\{1, \frac{C}{8(\sigma_{\max} + 1)}\}$	$\le \exp(-C)$	$\mathcal{O}(\sigma_{\max}\ln T + T^{2/3}(\ln T)^{1/3}(1 + \frac{\sigma_{\max}}{C})^{1/3}k^{2/3})$
先知/非先知延拓 (Non-preemptive)	全部设定	二值支撑 $\{-1, \infty\}$	$\le \exp(-C)$	与抢占式完全一致，无需撤回已追踪样本

关键发现¶

对数容量足以弥合延迟代价：在一阶 OCO 设定下，无论损失是凸还是强凸，仅需极小容量 $C = \Omega(\ln T)$，算法即可达成与无容量约束（$C = \infty$）完全一致的最优渐近后悔界，证明了追踪容量的边际收益在超过对数阶后迅速递减。
均匀权重对曲率与无导数优化的决定性作用：若使用 Pareto 调度器，时变逆概率权重 $w_t \propto d_t$ 会产生剧烈的二次项波动 $w_t^2$，导致强凸项负漂移无法抵消方差，并在 Bandit 估计中使 $\ell_2$ 范数截面膨胀；改用以 $\sigma_{\max}$ 标定的恒定伯努利调度是使 BCO 和强凸 OCO 成立的核心数学支撑。
$\sigma_{\max}$ 相较于 $d_{\max}$ 的显著优势：在排队系统或重尾服务延迟场景中，最大延迟 $d_{\max}$ 往往因极少数长尾任务而极大，但并发未决任务峰值 $\sigma_{\max}$ 保持较低。本文的界成功将对 $d_{\max}$ 的依赖收敛为 $\sigma_{\max}$，拓宽了实用场景。

亮点与洞察¶

解耦式约化机制：将系统底层的资源丢弃与调度决策与上层的凸优化算法严格剥离，把硬容量约束巧妙转化为虚拟的“带权延迟流”，为分布式系统中有损传输优化提供了标准范式。
半先知（Semi-Clairvoyant）模型的提出：打破了过去必须在预测时刻提前预知延迟的苛刻假设，只要求在延迟结束时获知到期信号，契合了实际异步计算中事件驱动轮询的真实环境。
基于 $\sigma_{\max}$ 的一维倍增技巧：巧妙利用参数仅依赖时间步 $t$ 而非全时长 $T$ 的 Anytime 特性，将传统二维倍增简化为针对积压量的一维倍增，理论证明了几何级数对分段常数项的完美吸收。

局限与展望¶

凸 BCO 中的延迟项差距：在凸损失 Bandit 设定下，延迟主导项为 $\sqrt{T\sigma_{\max}}$，而无容量约束下的最佳界为 $\sqrt{d_{\mathrm{tot}}}$；在长延迟场景下两者是否存在本质分离仍是开放问题。
对抗性自适应环境的拓展：当前理论建立在 Oblivious Adversary（遗忘型对手，损失函数与延迟序列在游戏开始前预设）假定上，无法直接抵御根据玩家历史动作动态生成延迟的自适应对手。
排队论与缓存策略的深度融合：目前代理延迟调度采用独立的随机入队丢弃机制，尚未深入利用 FIFO、LRU 等经典队列调度策略来优化确定性容量利用率。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统研究连续凸域与 Bandit 下具有硬容量限制的延迟优化，理论构建完备严谨。
实验充分度: ⭐⭐⭐⭐☆ 纯理论工作，数学推导极其扎实完备，定理与附录覆盖所有凸性与反馈形式，但缺少合成/真实数据的数值仿真。
写作质量: ⭐⭐⭐⭐⭐ 概念界定清晰，问题形式化优美，符号体系统一且动机直观生动。
价值: ⭐⭐⭐⭐⭐ 填补了在线凸优化在有限缓存/有限硬件资源下的基础理论空白，对异步分布式计算具有高度指导意义。

理论推导与技术细节补注¶

虚拟带权延迟序列的构造: 在硬容量 $C$ 下，由于丢弃事件发生，真实反馈集合被截断。算法构造虚拟带权序列 $\tilde{g}_t = w_t g_t \mathbf{1}_{\{E_t\}}$，其中 $E_t$ 表示反馈被调度接收的指示事件，$w_t = 1/P(E_t)$ 为逆倾向得分。通过这一构造，$\mathbb{E}[\tilde{g}_t | \mathcal{F}_{t-1}] = g_t$，保证了梯度估计在条件期望下的严格无偏性。
并发积压与方差控制: 在 Bandit 反馈下，单点无导数梯度估计自身具有 $d$ 倍维度的方差膨胀。若权重 $w_t$ 随延迟动态剧烈波动，二阶矩 $\mathbb{E}[\|\tilde{g}_t\|^2]$ 将出现 $w_t^2$ 级别的发散。通过以峰值积压 $\sigma_{\max}$ 标定均匀丢弃门限，算法将逆概率上界严格控制在 $\mathcal{O}(\sigma_{\max}/C)$ 内，从而在技术上阻断了高阶方差爆炸，使得 BCO 下的 $\sqrt{T\sigma_{\max}}$ 阶极小化极大遗憾界成立。
强凸损失下的负曲率对冲: 对于 $\alpha$-强凸损失，标准的 Follow-the-Regularized-Leader 依赖连续两步决策点之间的强凸项增量 $\frac{\alpha}{2}\|x_t - x_{t+1}\|^2$ 来抵消未决梯度的滞后内积偏差。当引入权重时，该抵消关系要求累积权重保持均匀下界，避免局部大权重撕裂正则化步长。论文所设计的恒定伯努利调度完美保留了强凸势函数的超加性，最终导出了对数级 $\mathcal{O}(\frac{\sigma_{\max}}{\alpha C}\ln T)$ 遗憾界。
与经典排队系统的边界衔接: 在 M/M/1 或更一般的 G/G/1 排队模型中，到达率与服务率的动态失配会导致瞬时队列长度呈现重尾特征。若直接采用传统延迟界（依赖 $d_{\max}$），系统上界将由极少量的病态长尾延迟主导而趋于平凡。本文建立的 $\sigma_{\max}$ 依赖性保证了只要并发服务窗口受到物理容量限制，算法的性能就受到严格的确定性约束，这为网络流量控制和流式在线广告投放中的有限缓存设计提供了理论支撑。
开放性理论问题: 未来工作的一个核心方向是将当前的遗忘型对手（Oblivious Adversary）扩展为自适应对手（Adaptive Adversary）。在自适应环境下，对手可以根据玩家的历史决策动态调整当前轮次的延迟长度，从而诱导反馈拥塞并强制触发丢弃，如何在此类恶意对抗调度下维持次线性遗憾界仍是一个深刻的开放难题。

设定与损失函数类型	维度/延迟指标	无约束基线 (\(C = \infty\))	本文容量约束上界 (\(C = \Omega(\ln T)\))	容量衰减因子 / 匹配结论
一阶 OCO (凸损失)	\(T, d_{\mathrm{tot}}\)	\(O(\sqrt{d_{\mathrm{tot}}} + \sqrt{T})\) [Quanrud & Khashabi, 2015]	\(\mathcal{O}(GD\sqrt{d_{\mathrm{tot}} + T})\)	仅需 \(C \ge \ln T + 1\) 即可完全无损匹配无约束率
一阶 OCO (\(\lambda\)-强凸损失)	\(T, \sigma_{\max}\)	\(O(\sigma_{\max}\ln T + \ln T)\) [Qiu et al., ICML 2025]	\(\mathcal{O}(\frac{G^2}{\lambda}(\sigma_{\max} + 1)\ln T)\)	匹配无约束极小极大率 \(\Theta((\sigma_{\max}+1)\ln T)\)
Bandit BCO (凸损失)	\(T, k, \sigma_{\max}\)	\(O(\sqrt{T d_{\max}} + T^{3/4}\sqrt{k})\) [Wan et al., NeurIPS 2024]	\(\mathcal{O}(GD(\sqrt{T\sigma_{\max}} + T^{3/4}(1 + \frac{\sigma_{\max}}{C})^{1/4}\sqrt{\nu k}))\)	依赖更优的 \(\sigma_{\max} \le d_{\max}\)，容量降至 \(C\) 时平滑退化
Bandit BCO (\(\lambda\)-强凸损失)	\(T, k, \sigma_{\max}\)	\(O(\sigma_{\max} + T^{2/3}k^{2/3})\) [Ryabchenko et al., 2026]	\(\mathcal{O}(\frac{G^2}{\lambda}(\sigma_{\max}\ln T + (T^2\ln T)^{1/3}(1 + \frac{\sigma_{\max}}{C})^{1/3}(\nu k)^{2/3}))\)	达到次线性 \(T^{2/3}\) 依赖，容量乘子仅为 \((1 + \frac{\sigma_{\max}}{C})^{1/3}\)

调度器配置 / 假设场景	适用损失设定	观测概率 \(p_t\) 形式	容量饱和风险概率 \(\mathbb{P}(\\|\mathcal{S}_t\\|=C)\)	后悔界关于关键参数的依赖阶数
Pareto 调度器 (抢占式)	凸 OCO	\(\min\{1, \frac{C}{16 H_t (d_t + 1)}\}\)	\(\le \exp(-C)\) (由 Chernoff 保证)	\(\mathcal{O}(\sqrt{d_{\mathrm{tot}} + T})\)，自适应单轮时变延迟 \(d_t\)
Bernoulli 调度器 (非抢占式)	强凸 OCO	\(p = \min\{1, \frac{C}{8(\sigma_{\max} + 1)}\}\)	\(\le \exp(-C)\)	\(\mathcal{O}((\sigma_{\max} + 1)\ln T)\)，权重恒定为 \(1/p\) 避免强凸项发散
Bernoulli 调度器 (Bandit)	凸 BCO	\(p = \min\{1, \frac{C}{8(\sigma_{\max} + 1)}\}\)	\(\le \exp(-C)\)	\(\mathcal{O}(\sqrt{T\sigma_{\max}} + T^{3/4}(1 + \frac{\sigma_{\max}}{C})^{1/4}\sqrt{k})\)
Bernoulli 调度器 (强凸 Bandit)	强凸 BCO	\(p = \min\{1, \frac{C}{8(\sigma_{\max} + 1)}\}\)	\(\le \exp(-C)\)	\(\mathcal{O}(\sigma_{\max}\ln T + T^{2/3}(\ln T)^{1/3}(1 + \frac{\sigma_{\max}}{C})^{1/3}k^{2/3})\)
先知/非先知延拓 (Non-preemptive)	全部设定	二值支撑 \(\{-1, \infty\}\)	\(\le \exp(-C)\)	与抢占式完全一致，无需撤回已追踪样本