技术摘要：容量受限的延迟反馈在线凸优化

1. 问题陈述

本文研究了在同时存在延迟反馈和有限追踪容量两种约束下的在线凸优化 (OCO) 与 带置信区间凸优化 (BCO) 问题。

在标准的延迟在线学习中，学习者在第 $t$ 轮选择一个动作 $x_t$，产生损失 $f_t(x_t)$，但仅在第 $t + d_t$ 轮收到反馈（梯度或标量损失）。传统文献假设学习者拥有无限的容量来追踪所有待处理的轮次，直到其反馈到达。然而，在实际场景中（例如临床试验中有限的监测资源），学习者只能追踪有限数量的待处理轮次，记为容量 $C$。如果某一轮未被追踪，其反馈将永久丢失。

本文将此形式化为一个博弈过程：

• 对手确定凸损失 $f_t$ 和延迟 $d_t$。
• 玩家维护一个大小至多为 $C$ 的追踪集合 $S$。
• 在每一轮，玩家可以抢占（丢弃）已追踪的轮次，或者将当前轮次加入 $S$。
• 当且仅当 $s \in S$ 时，轮次 $s$ 的反馈在 $s + d_s$ 时被观测到。
• 目标是最小化相对于事后最优固定动作 $x^*$ 的遗憾值 $R_T = \sum_{t=1}^T (f_t(x_t) - f_t(x^*))$。

本文考虑了关于延迟的两种信息模型：

1. 全知型 (Clairvoyant)： 延迟 $d_t$ 在预测时已知。
2. 半全知型 (Semi-Clairvoyant)： 延迟仅在到期时（即 $t+d_t$ 时）才揭示，这与标准的延迟学习设置一致。

2. 方法论

作者提出了一种基于归约 (reduction-based) 的方法，将容量受限问题分解为两个部分：一个调度器 (scheduler) 和一个基础学习器 (base learner)。

2.1 归约框架

核心思想是将容量受限问题归约为一种新型的**“延迟且加权”的 OCO** 问题。

• 调度器： 一个包装算法负责管理追踪集合 $S$。它使用一种代理延迟调度 (proxy-delay scheduling) 机制。对于每一轮 $t$，调度器从分布 $D_t$ 中采样一个“代理延迟” $d'_t$。如果 $d'_t \ge 0$ 且容量允许，则将第 $t$ 轮加入 $S$。如果反馈尚未到达，则在 $t + d'_-t + 1$ 时将其从 $S$ 中移除。
• 重要性加权： 如果第 $s$ 轮的反馈被观测到（即 $s \in S$ 且 $d'_s \ge d_s$），包装器将反馈以重要性权重 $w_s = 1 / P(d'_s \ge d_s)$ 转发给基础学习器。如果反馈丢失（由于容量饱和或过早的代理超时），则权重设为 0。
• 基础学习器： 学习器接收流式的延迟、加权反馈。本文引入了专门用于处理这种加权、延迟流的算法。

2.2 基础算法：延迟加权 FTRL

本文引入并分析了两种用于加权延迟设置的基础算法：

1. DW-FTRL (延迟加权跟随正则化领先者)： 用于一阶（梯度）反馈。它通过最小化一个聚合了所有观测轮次加权梯度的正则化目标函数来更新迭代值。
2. DW-FTBL (延迟加权跟随带置信区间领先者)： 用于带置信区间（标量损失）反馈。它使用标准的单点梯度估计器（扰动中心点），但将其应用于加权的延迟反馈流。

对这些基础算法的理论分析确立了其遗憾界，该界明确考虑了时间变化权重与待处理观察序列之间的相互作用。一个关键发现是，遗憾值取决于具有重叠延迟的轮次的权重之间的成对相互作用。

2.3 代理延迟调度器

为了确保归约奏效，调度器必须平衡两个竞争目标：覆盖真实延迟（以观测反馈）和避免容量饱和。本文提出了两种特定的调度器：

1. 帕累托调度器 (Pareto Scheduler)： 适应个体延迟 $d_t$。它从偏移帕累托分布中采样代理延迟，使得追踪概率与延迟成反比。这适用于一般的凸损失。
2. 伯努利调度器 (Bernoulli Scheduler)： 根据最大积压 (maximum backlog) $\sigma_{max}$（任何时刻待处理观测的最大数量）进行校准。它以概率 $p \approx C / \sigma_{max}$ 采样代理延迟为 $\infty$，否则为 $-1$。这产生了均匀重要性权重，这一特性对于在强凸和带置信区间设置中实现紧凑界至关重要。

3. 主要贡献

1. 首次提供容量受限 OCO/BCO 的遗憾保证： 本文提供了容量受限的延迟反馈在线学习在凸和强凸领域下，针对一阶和带置信区间反馈的第一个亚线性遗憾界。
2. 延迟加权 OCO 框架： 引入了一个新的问题设置（延迟且加权反馈），并分析了其中的 FTRL 变体。该框架对于延迟下的无标度在线学习具有独立的价值。
3. 统一的代理延迟调度： 作者统一了之前的调度思想，并引入了一种新的调度器（伯努利），它能产生均匀权重，从而为强凸和带置信区间设置提供更强的保证。
4. 处理未知参数： 该框架兼容半全知模型（延迟在预测时未知），并使用倍增技巧 (doubling trick) 来处理未知 $\sigma_{max}$ 的情况。

4. 主要结果

遗憾界取决于时间跨度 $T$、维度 $k$、总延迟 $d_{tot}$、最大积压 $\sigma_{max}$ 以及容量 $C$。

4.1 一阶反馈 (OCO)

• 凸损失： 当 $C = \Omega(\log T)$ 时，其遗憾值在对数因子范围内匹配了最优无约束延迟速率：
  $$\tilde{O}\left( G D \sqrt{d_{tot} + T} \right)$$
• 强凸损失： 其遗憾值为：
  $$\tilde{O}\left( \frac{G^2}{\lambda} (\sigma_{max} + 1) \log T \right)$$
  这与无约束设置中发现的最优 $\sigma_{max}$ 相关性相匹配。

4.2 带置信区间反馈 (BCO)

对于带置信区间反馈，容量约束通过因子 $(1 + \sigma_{max}/C)$ 进入维度相关项。

• 凸损失：
  $$\tilde{O}\left( GD \left( \sqrt{T \sigma_{max}} + T^{3/4} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/4} \sqrt{\nu k} \right) \right)$$
  其中 $\nu$ 是函数值与梯度的尺度比例。当 $C$ 减小时，界限会平滑下降。
• 强凸损失：
  $$\tilde{O}\left( \frac{G^2}{\lambda} \left( \sigma_{max} \log T + (T^2 \log T)^{1/3} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/3} (\nu k)^{2/3} \right) \right)$$

关键观察： 当 $C \ge \sigma_{max}$ 时，界限恢复为无约束速率。当 $C < \sigma_{max}$ 时，遗憾值会增加但仍保持亚线性。研究表明，在类队列系统中，对 $\sigma_{max}$（峰值并发量）的依赖比对 $d_{max}$（最大延迟）的依赖更为自然。

5. 重要性与主张

本文声称是第一个推导出容量受限 OCO 和 BCO 遗憾保证的研究。其意义在于：

• 弥合理论与实践： 它解决了追踪资源有限的现实约束，而以往大多数延迟学习文献都忽略了这一点，默认假设具有无限容量。
• 完善延迟模型： 通过采用半全知模型（延迟仅在到期时揭示），这项工作比以往的“全知型”假设更贴近标准的延迟学习和在线作业调度现实。
• 优雅降级： 结果表明，对于一阶反馈，对数容量（$C = \Omega(\log T)$）足以恢复标准的延迟速率；而对于带置信区间反馈，当容量低于峰值积压时，性能会优雅地下降。
• 理论新颖性： 引入“延迟且加权”的 OCO 问题以及对 FTRL 中权重与延迟相互作用的特定分析，为分析资源受限下的在线学习提供了新工具。

作者指出，虽然他们对于凸带置信区间反馈的界限随 $\sqrt{T \sigma_{max}}$ 缩放，而非无约束设置中的最优 $\sqrt{d_{tot}}$，但仍优于以往依赖于 $\sqrt{T d_{max}}$ 的界限。他们认为缩小这一差距是一个开放性问题。此外，他们建议该模型与有限缓冲区队列系统之间的结构相似性值得进一步探索。