技术摘要：从非凸到强凸：面向在线优化的曲率自适应 FTPL

问题陈述

本文解决了在线优化理论中关于算法对损失函数曲率适应性的一个基本空白。经典结果表明，对于凸 Lipschitz 损失，最优遗憾（regret）阶数为 $O(\sqrt{T})$；而对于强凸损失，该阶数可提升至 $O(\log T)$。自适应方法（例如 Bartlett 等人，2007）已成功在凸设置中实现了这两者之间的插值。然而，最近的研究（Suggala 和 Netrapalli，2020）表明，使用近似离线优化算子（oracle）的跟随扰动领导者算法（Follow-the-Perturbed-Leader, FTPL）对于非凸 Lipschitz 损失可以实现 $O(\sqrt{T})$ 的遗憾，但这些保证并未利用曲率特性，因此在存在强凸性时无法实现更快的速率。

核心问题在于：是否可以让 FTPL 在非凸领域实现曲率自适应，即在保持对一般非凸损失实现 $O(\sqrt{T})$ 遗憾的同时，能够在存在足够的累积强凸性时自动提升至 $O(\log T)$（或更好），且无需预先知晓曲率序列。

方法论

算法：自适应 FTPL (AdaFTPL)

作者提出了 AdaFTPL，它是标准 FTPL 框架的一种扩展。其核心创新在于将固定的扰动尺度 $\rho$ 替换为随时间变化的噪声尺度 $\rho_t$。

• 算子访问： 算法假设可以访问一个 $(\alpha, \beta)$-近似优化算子。给定累积损失函数 $F_{t-1}$ 和扰动向量 $\sigma_t$，该算子返回一个点 $\hat{x}$，该点近似最小化 $F_{t-1}(x) - \langle \sigma_t, x \rangle$。
• 扰动机制： 在每一轮 $t$，学习者生成一个具有独立同分布指数项的随机向量 $\sigma_t$，并将其缩放 $\rho_t$ 倍。预测值 $x_t$ 通过查询带有扰动累积损失 $F_{t-1} - \rho_t \sigma_t$ 的算子获得。

用于调度选择的元在线学习 (Meta-Online Learning)

序列 $\rho_1, \dots, \rho_T$ 不是固定的，而是根据过去的信息进行自适应选择。作者将 $\rho_t$ 的选择建模为一个元在线学习问题：

1. 遗憾界参数化： 他们推导出了一个通用的遗憾界（定理 1），该界依赖于序列 $\rho_t$ 和累积损失函数 $F_t = \sum_{i=1}^t f_i$ 的累积强凸常数 $S_t$。该界包含两个项的最小值：一个反映非凸稳定性（与 $1/\rho_t$ 相关），另一个反映强凸性（与 $1/S_t$ 相关）。
2. 跟随领导者 (FTL) 微调： 为了在不知道未来损失的情况下选择 $\rho_t$，算法通过最小化过去的遗憾上界来进行“跟随领导者”式的微调（即在噪声调度空间中的一次 FTL 移动）。具体而言，$\rho_t$ 的选择旨在最小化由第 $1$到$t-1$ 轮产生的累积界。
3. 竞争分析： 定理 2 证明，这种简单的 FTL 微调策略相对于事后最优的固定调度（离线最优）具有常数竞争性（constant-competitive）。

理论分析

分析依赖于一种“幽灵”移动分解（"ghost" move decomposition）。作者引入了一个假设的移动 $\bar{x}_{t+1}$，它使用当前的噪声尺度 $\rho_t$ 但使用更新后的累积损失 $F_t$。这使得他们可以将遗憾分解为：

• 稳定性： 实际移动 $x_t$ 与幽灵移动 $\bar{x}_{t+1}$ 之间的距离。这可以通过两种方式进行界定：
  • 非凸界： 基于 Lipschitz 连续性和指数扰动的性质导出（遵循 Suggala 和 Netrapalli, 2020）。
  • 强凸界： 基于 $F_t$ 的强凸性导出，产生一个正比于 $L/S_t$ 的界。
• 扰动： 噪声和算子近似误差带来的代价。

通过在每一步取非凸稳定性界与强凸稳定性界的最小值，该算法有效地在两种机制之间进行插值。

关键结果

上界

• 通用遗憾： 对于任意非凸 Lipschitz 损失，该算法实现了 $O(\sqrt{T})$ 的遗憾界。
• 曲率自适应遗憾： 如果累积曲率 $S_t$ 随 $t^\gamma$ 增长，则遗憾规模如下（推论 3.1）：
  • $\gamma \leq 1/2$：$O(\sqrt{T})$
  • $1/2 < \gamma < 1$：$O(T^{1-\gamma})$
  • $\gamma = 1$（线性增长，即强凸性）：$O(\log T)$
  • $\gamma > 1$：$O(1)$
• 算子要求： 为了达到这些速率，算子误差参数必须满足 $\alpha, \beta = O(1/T)$。

下界

作者提供了匹配的下界（定理 3），即使在受限的一维凸损失设定下也是如此。他们证明了对于任何给定的累积曲率序列，极小极大遗憾（minimax regret）的下界为 $\Omega(\text{OPT}_T^0(0))$，这与 AdaFTPL 实现的上界在常数因子内是一致的。这证明了最坏情况下的非凸遗憾与曲率驱动的快速速率之间的权衡是该问题固有的，而非算法分析的人为产物。

实证验证

在具有不同曲率（通过概率参数 $p_+$ 控制）的二次函数上的合成实验表明：

• 在低曲率机制下（$p_+$ 较小时），AdaFTPL 的表现与标准 FTPL 和 FTL 相当。
• 随着曲率增加，AdaFTPL 显著优于非自适应的 FTPL，接近 FTL 的性能（FTL 对强凸问题是最优的，但在非凸设置中会失效）。
• 算法能在曲率中途引入或移除时进行动态自适应。
• 在 FTL 会产生线性遗憾的对抗性交替符号场景中，AdaFTPL 由于其扰动机制仍能保持亚线性遗憾。

意义与主张

本文声称提供了首个在非凸领域实现曲率自适应的 FTPL 方法。其重要性在于：

1. 弥合差距： 它统一了用于在线凸优化（如 Bartlett 等人，2007）的自适应方法与用于非凸环境的 FTPL（Suggala 和 Netrapalli, 2020）的保证。
2. 算子效率： 它保持了 FTPL 的计算效率，仅依赖于离线优化算子，这对于直接梯度方法难以处理的结构化决策集至关重要。
3. 最优性： 通过提供匹配的下界，作者确立了所推导的遗憾速率在给定曲率序列下是极小极大最优的。
4. 实际动机： 该工作受到现代机器学习中复合损失结构的启发（例如持续学习、鲁棒回归），其中非凸数据项与强凸正则项相互作用，创造了一个未知的动态曲率景观。

作者谦虚地指出，其结果显著扩展了自适应遗憾速率在在线凸优化之外的应用范围，为那些“最佳”算法行为取决于未知的非凸性与正则化之间相互作用的场景提供了一个稳健的框架。