技术摘要：基于算法等价性的隐藏凸损失在线学习

问题陈述

本文解决了具有隐藏凸损失的对抗性在线学习问题。在该设定下，学习者面临一系列损失函数 $(\ell_t)$，这些函数在算法的原生参数空间 $X$ 中是非凸的，但在经过特定的、未知的非线性重参数化 $q: X \to Y$ 后变为凸函数。目标是相对于事后最佳固定决策最小化外部遗憾：
$$R_T = \sum_{t=1}^T \ell_t(x_t) - \min_{x \in X} \sum_{t=1}^T \ell_t(x)$$
其中 $\ell_t(x) = h_t(q(x))$，且 $h_t$ 是凸函数。

虽然在线梯度下降（OGD）在标准在线凸优化（OCO）中实现了最优的 $\Theta(\sqrt{T})$ 遗憾，但 OGD 在非凸损失上的表现通常较差。Ghai 等人 [2022] 的先前工作表明，在特定的几何和平滑性假设下，隐藏凸损失上的 OGD 近似模拟了重参数化凸损失上的在线镜像下降（OMD），从而产生了次优的 $O(T^{2/3})$ 遗憾界。本文解决的核心开放性问题如下：

1. 在精确梯度反馈下，隐藏凸损失能否恢复最优的 $\Theta(\sqrt{T})$ 遗憾率？
2. 实现这一恢复所需的精确几何条件是什么，它们是否是必要的？
3. 该框架是否扩展到带反馈设定（即每轮仅观察到一个损失值）？

方法论

核心方法论依赖于原始非凸空间中的 OGD 与隐藏凸空间中的 OMD 之间经过改进的算法等价性论证。

1. 算法等价性与离散化误差

作者分析了 $X$ 中的 OGD 迭代序列 $(x_t)$ 与 $Y$ 中的 OMD 迭代序列 $(y_t)$（其中 $y_t = q(x_t)$）之间的关系。

• 连续与离散： 在连续时间中，如果正则化项 $R$ 的 Hessian 矩阵与 $q$ 的 Jacobian 诱导的度量相匹配，则在重参数化下梯度流与镜像流完全重合。在离散时间中，这种等价性被离散化误差打破。
• 关键技术改进： Ghai 等人 [2022] 将一步 OGD 与 OMD 迭代之间的距离界定为 $O(\eta^{3/2})$。本文引入了更锐利的分析，证明该距离实际上为 $O(\eta^2)$。
• 机制： 证明将两个更新都定位在 $O(\eta)$ 邻域内。它将两个更新表达为同一个强凸二次模型 $\Phi_t(y)$ 的最小化器，该模型受到不同的高阶泰勒余项（$\varepsilon^{OGD}_t$ 和 $\varepsilon^{OMD}_t$）的扰动。通过直接比较一阶最优性条件（而不是界定目标函数值的差异），作者表明最小化器之间的差异受限于 $\eta$ 乘以误差项梯度的差异，从而得出 $O(\eta^2)$ 的界。

2. 几何条件

分析依赖于假设 1（Hessian 兼容的重参数化），该假设要求存在一个严格凸的正则化项 $R$，使得：
$$[\nabla^2 R(z)]^{-1} = J_q(x) J_q(x)^\top$$
其中 $z = q(x)$。该条件确保原始空间中的欧几里得度量对应于隐藏空间中由 $R$ 诱导的 Bregman 度量。

3. 下界构造

为了证明 Hessian 兼容条件的必要性，作者构造了一个该条件失效的反例。他们定义了一个平滑的重参数化，其中诱导的度量不是 Hessian 场（即相关的向量场不是保守场）。通过设计对抗性的线性损失序列，他们迫使 OGD 迭代在隐藏空间中围绕一个具有非零环流的环路循环，从而累积线性遗憾 $\Omega(T)$。

4. 带反馈扩展

对于带反馈设定，本文采用了带有球面平滑的**带 OGD（BOGD）**算法（Flaxman 等人 [2005]）。分析将期望遗憾分解为四个部分：

1. 扰动 OMD 遗憾（使用“幽灵”OMD 迭代）。
2. 域收缩误差（由于限制域以允许扰动）。
3. 梯度估计偏差（源于一阶估计器）。
4. 平滑误差（在扰动点评估的损失）。
   $O(\eta^2)$ 耦合结果被扩展到带反馈设定，以控制扰动 OMD 项。

主要贡献与结果

1. 精确梯度反馈下的最优遗憾

结果： 在与 Ghai 等人 [2022] 相同的几何和平滑性假设下，OGD 对隐藏凸损失实现了 $O(\sqrt{T})$ 遗憾。
意义： 这改进了先前 $O(T^{2/3})$ 的界，并匹配了对抗性 OCO 的最优最坏情况率。这一改进直接源于算法等价性中更紧致的 $O(\eta^2)$ 离散化误差界。

2. 改进的几何条件

结果： 本文放宽了先前工作中使用的“对角 Jacobian"充分条件。它基于逆度量场的交叉偏导数，提供了 Hessian 兼容性的充要条件（命题 1）。
意义： 这扩大了可接受重参数化的类别（例如，可分离参数化的仿射混合和秩一非线性混合），这些参数化能保证次线性遗憾。

3. 几何障碍（必要性）

结果： 本文证明了 Hessian 兼容性对 OGD 是至关重要的。如果该条件失效，则存在一个平滑的重参数化和一个对抗序列，使得 OGD 遭受 $\Omega(T)$ 线性遗憾（定理 2）。
意义： 这表明几何结构不仅仅是证明的技术产物，而是该设定下一阶方法成功的基本前提。

4. 带反馈保证

结果： 在针对无记忆对抗者的单点带反馈设定中，所提出的带 OGD 实现了 $O(T^{3/4})$ 的期望遗憾（定理 3）。
意义： 这匹配了标准凸损失上带 OGD 的已知最佳率，表明与凸情况相比，隐藏凸结构在带反馈设定中并未产生额外的惩罚。

意义与主张

本文声称解决了关于隐藏凸在线学习中 OGD 最优性的开放性问题。通过锐化算法等价性分析，它证明了先前工作中观察到的较慢的 $O(T^{2/3})$ 率是分析的产物，而非问题类别固有的局限性。

该工作确立了：

• 最优性可恢复： 如果隐藏几何满足 Hessian 兼容性，简单的基于一阶的方法（OGD）可以实现结构化非凸问题的最优遗憾率。
• 几何至关重要： Hessian 兼容条件是一个尖锐的边界；如果没有它，OGD 会完全失效（线性遗憾）。
• 鲁棒性： 该框架扩展到带反馈，尽管存在梯度估计和域收缩的额外挑战，但仍保持了经典速率。

作者指出，虽然他们的下界排除了在没有 Hessian 兼容性的情况下 OGD 实现次线性遗憾的可能性，但其他在线算法是否能在缺乏该几何条件的情况下实现次线性遗憾仍然是一个开放问题。同样，虽然带反馈率匹配了凸情况，但实现更锐利的速率或高概率界限仍是未来工作的方向。