Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization

技术摘要：在线凸优化中的噪声自适应高概率遗憾界

问题陈述
本研究解决了在线凸优化（OCO）在三种不同且相互关联的挑战下的问题：(1) 在全信息设置下，实现强凸损失函数的噪声自适应高概率遗憾界；(2) 确定从全信息到带反馈（bandit feedback）设置时，基本置信成本（对失败概率 $\delta$ 的依赖关系）的变化；(3) 在具有随机约束的约束性 OCO 中，建立累积遗憾与长期约束违反的同步高概率保证。

虽然经典结果已经确立了在线梯度下降（OGD）在 $\alpha$-强凸损失下可以实现 $O(\frac{G^2}{\alpha} \log T)$ 的期望遗憾（其中 $G$ 限制了梯度范数），但高概率保证对于安全至上的应用场景而言往往不够紧凑。标准方法依赖于 Azuma-Hoeffding 不等式，其产生的鞅偏差项随最坏情况梯度界 $G$ 和定义域直径 $D$ 缩放（具体为 $GD\sqrt{2T \log(1/\delta)}$）。当实际随机噪声水平 $\sigma$ 显著小于 $G$ 时（这在正则化经验风险最小化中是一个常见情形），该界限会显得过于宽松。此外，现有文献缺乏对噪声自适应性、反馈结构差异以及高概率约束满足的统一处理。

方法论与核心贡献

本文通过创新的集中不等式论证和下界构造解决了三个开放性问题：

1. 噪声自适应高概率界（全信息）：
   作者证明了采用步长 $\eta_t = 1/(\alpha t)$ 的投影 OGD 可以实现一个高概率遗憾界，其中鞅偏差项随噪声水平 $\sigma$ 而非梯度界 $G$ 缩放。

   • 方法论： 分析引入了一种专门针对条件亚高斯序列定制的指数超鞅论证（exponential supermartingale argument）。该技术绕过了 Freedman 不等式中固有的有界差分要求，后者通常需要对无界亚高斯噪声进行截断。通过避免截断，作者保留了鞅性质，并推导出一个偏差项为 $O(\sigma D \sqrt{T \log(1/\delta)})$ 的界。
   • 结果： 遗憾界为 $O(\frac{G^2}{\alpha} \log T + \sigma D \sqrt{T \log(1/\delta)})$。当 $\sigma \ll G$ 时，相比于经典的 Azuma-Hoeffding 基准，这实现了 $G/\sigma$ 倍的多倍改进。证明过程利用独立的概率预算来分离梯度范数的截断与鞅尾部集中。

2. 置信成本分离（带反馈 vs. 全信息）：
   本文建立了一个极小极大下界，证明了强凸 OCO 在全信息反馈与带反馈设置之间存在基本的置信成本分离。

   • 方法论： 使用基于分段（epoch-based）的测试构造及加性高斯噪声，作者应用 Bretagnolle-Huber 引理和条件耦合论证来构建一个困难实例。
   • 结果： 在全信息设置下，高概率遗憾随 $\sqrt{\log(1/\delta)}$ 缩放。相比之下，在带反馈设置下（仅观测到标量损失值），遗憾随 $\log(1/\delta)$ 线性缩放。这首次正式证明了对于强凸问题，带反馈设置的信息论置信成本严格高于全信息设置。

3. 同步高概率保证（约束性 OCO）：
   作者提供了首个能在满足 Slater 条件的随机约束下，同时实现累积遗憾与长期约束违反的高概率控制算法。

   • 方法论： 分析采用了原-对偶 OGD 框架。遗憾界的分析利用了 Freedman 不等式（由于约束噪声几乎处处有界而适用）。约束违反分析将累积违反分解为期望部分和随机鞅部分。期望部分通过鞍点论证和马尔可夫不等式进行界定，而随机部分则通过 Freedman 不等式进行控制。
   • 结果： 该算法实现了 $O(\sqrt{T \log(m/\delta)})$ 的遗憾和 $O(\frac{\sqrt{T}}{\zeta \delta_1} + m\sqrt{T \log(m/\delta_2)})$ 的长期约束违反。值得注意的是，由于使用了马尔可夫不等式，违反界在期望部分保留了 $1/\delta$ 因子，而随机偏差则随 $\sqrt{\log(1/\delta)}$ 缩放。

实验验证
合成实验证实了理论预测：

• 噪声自适应性： 经验尾部统计数据确认，遗憾分位数追踪了噪声自适应界（依赖于 $\sigma$），并且在 $\sigma \ll G$ 时明显低于 Azuma-Hoeffding 基准（依赖于 $G$）。
• 置信成本： 在一维强凸问题上的实验表明，全信息遗憾随 $\sqrt{\log(1/\delta)}$ 增长，而带反馈遗憾随 $\log(1/\delta)$ 线性增长，验证了信息论层面的分离。
• 约束性 OCO： 遗憾与违反的联合分布确认了独立的概率预算分配以及违反量与 Slater 间隙 $\zeta$ 的反线性缩放关系。

意义与主张

本文声称解决了强凸 OCO 在噪声自适应性、反馈结构和约束满足交汇处的三个特定开放问题。

• 它提供了一种噪声自适应的精细化方法，展示了“置信的价格”可以从最坏情况下的梯度幅值中解耦，转而与实际噪声水平挂钩。
• 它建立了形式化的分离，证明了带反馈设置相对于全信息设置，会产生线性 $\log(1/\delta)$ 的惩罚，而非平方根级的 $\sqrt{\log(1/\delta)}$ 惩罚。
• 它提供了针对随机约束环境下，同时实现遗憾与约束违反的首个高概率保证，阐明了控制这两部分的统计机制（马尔可夫 vs. Freedman）。

作者指出，虽然约束违反界中的 $1/\delta$ 依赖关系对于当前的证明技术（依赖于马尔可夫不等式处理期望部分）是紧致的，但将其改进为 $\log(1/\delta)$ 仍是一个需要通过路径控制原-对偶鞍点不等式的开放问题。同样，将噪声自适应性扩展到具有非平凡偏差-超鞅相互作用的带反馈设置，也被确定为未来的研究方向。