通过算法等价实现隐凸损失的在线学习：最优遗憾、几何障碍与赌博机反馈

# 基于算法等价性的隐凸损失在线学习：最优遗憾、几何障碍与赌博反馈 来源：https://arxiv.org/html/2605.26373 Anas Barakat¹ Andreas Kontogiannis²,⁵ Vasilis Pollatos³,⁵ Ioannis Panageas⁴ Antonios Varvitsiotis¹,⁵,⁶ ###### 摘要 我们研究具有隐凸损失的对抗性在线学习，即那些经过非线性重参数化后变为凸损失的非凸损失。Ghai等人(2022 (https://arxiv.org/html/2605.26373#bib.bib46))证明，在几何和光滑性假设下，对此类非凸损失应用在线梯度下降(OGD)会近似模拟在底层凸损失上使用合适正则化器的在线镜像下降(OMD)，从而得到O(T^{2/3})的遗憾界。他们留下了这样一个开放问题：在此隐凸设置中，能否恢复在线凸优化的最优Θ(√T)遗憾率？我们对这个问题给出了肯定回答。更具体地说，通过一个更尖锐的离散时间算法等价性论证，我们证明在相同假设下OGD能达到O(√T)的遗憾，与对抗性在线凸优化的最差情况最优率相匹配。我们还解决了(Ghai等人，2022 (https://arxiv.org/html/2605.26373#bib.bib46))的另一个开放问题，即阐明该算法等价性所需的几何条件。我们用必要且充分的Hessian相容性条件替换了对角Jacobian充分条件，从而扩展了可容许重参数化的类别。我们用下界补充了紧的遗憾界，该下界表明Hessian相容性假设对OGD至关重要；当该条件不满足时，我们构造了一个光滑的重参数化和一个对抗性的隐凸损失序列，使得OGD遭受Ω(T)的遗憾。最后，我们将分析扩展到单点赌博反馈，并证明了使用球面平滑的赌博OGD的O(T^{3/4})期望遗憾界，这与其在凸损失上的经典率相匹配。 00footnotetext:作者单位：¹新加坡科技设计大学，²雅典国家技术大学，³雅典国立卡波迪斯特里安大学，⁴加州大学尔湾分校，⁵希腊雅典娜研究中心阿基米德实验室，⁶新加坡国立大学量子技术中心 00footnotetext:联系方式：[email protected], [email protected], [email protected], [email protected], [email protected]. ## 1 引言 在线凸优化(OCO)为对抗性序列决策提供了理论框架：对于凸Lipschitz损失，简单的在线梯度下降(OGD)等一阶方法能达到最优的Θ(√T)遗憾率 (Zinkevich, 2003 (https://arxiv.org/html/2605.26373#bib.bib27); Hazan, 2016 (https://arxiv.org/html/2605.26373#bib.bib39); Shalev-Shwartz, 2012 (https://arxiv.org/html/2605.26373#bib.bib38))。超出凸性范围后，情况变得更加复杂。对于任意的非凸损失，如果没有额外的结构或预言机访问，简单的一阶方法通常无法实现对事后最佳固定决策的亚线性遗憾 (Krichene等人, 2015 (https://arxiv.org/html/2605.26373#bib.bib35); Agarwal等人, 2019 (https://arxiv.org/html/2605.26373#bib.bib34); Suggala和Netrapalli, 2020 (https://arxiv.org/html/2605.26373#bib.bib36); Héliou等人, 2020 (https://arxiv.org/html/2605.26373#bib.bib33))。例如，已知一般非凸在线学习中，没有确定性算法能实现亚线性遗憾 (Suggala和Netrapalli, 2020 (https://arxiv.org/html/2605.26373#bib.bib36)，命题3)。这激发了人们对结构化非凸在线问题的探索，这类问题保留足够的几何结构，使得简单一阶算法能够获得类似凸优化的保证。

一种突出的良性非凸形式是隐凸性 (Ben-Tal和Teboulle, 1996 (https://arxiv.org/html/2605.26373#bib.bib16); Li等人, 2005 (https://arxiv.org/html/2605.26373#bib.bib15); Fatkhullin等人, 2025a (https://arxiv.org/html/2605.26373#bib.bib42); Levin等人, 2025 (https://arxiv.org/html/2605.26373#bib.bib29); Gorissen等人, 2026 (https://arxiv.org/html/2605.26373#bib.bib14))。这一结构特性出现在多个现代优化问题中，包括神经网络训练 (Wang等人, 2022 (https://arxiv.org/html/2605.26373#bib.bib18); Patel和Vlatakis-Gkaragkounis, 2025 (https://arxiv.org/html/2605.26373#bib.bib22); Ergen和Pilanci, 2025 (https://arxiv.org/html/2605.26373#bib.bib1); Zeger和Pilanci, 2026 (https://arxiv.org/html/2605.26373#bib.bib17))、强化学习 (Hazan等人, 2019 (https://arxiv.org/html/2605.26373#bib.bib3); Zhang等人, 2020 (https://arxiv.org/html/2605.26373#bib.bib2); Zahavy等人, 2021 (https://arxiv.org/html/2605.26373#bib.bib5); Barakat等人, 2023 (https://arxiv.org/html/2605.26373#bib.bib7), 2025 (https://arxiv.org/html/2605.26373#bib.bib8); D'Orazio等人, 2025 (https://arxiv.org/html/2605.26373#bib.bib20))，以及非凸博弈 (Vlatakis-Gkaragkounis等人, 2019 (https://arxiv.org/html/2605.26373#bib.bib23); Mladenovic等人, 2022 (https://arxiv.org/html/2605.26373#bib.bib9); Sakos等人, 2023 (https://arxiv.org/html/2605.26373#bib.bib24); Kalogiannis等人, 2024 (https://arxiv.org/html/2605.26373#bib.bib21); Gemp等人, 2025 (https://arxiv.org/html/2605.26373#bib.bib12); Kalogiannis等人, 2025 (https://arxiv.org/html/2605.26373#bib.bib11); Barakat等人, 2026 (https://arxiv.org/html/2605.26373#bib.bib10))。在这些设置中，目标函数在算法的原生参数下是非凸的，但在适当的非线性变量变换后变成凸的。这一结构已在确定性和随机优化中被利用，为非凸问题提供全局收敛保证 (Chen等人, 2025 (https://arxiv.org/html/2605.26373#bib.bib40); Fatkhullin等人, 2025a (https://arxiv.org/html/2605.26373#bib.bib42), b (https://arxiv.org/html/2605.26373#bib.bib41); Bhaskara等人, 2025 (https://arxiv.org/html/2605.26373#bib.bib13))。然而，在线设置中，学习器面临一个独特的挑战：随时间顺序揭示的损失函数甚至可能是对抗性选择的，目标是在事后最佳固定比较器上实现低遗憾，而不是收敛到固定函数的最小化器。

Ghai等人(2022 (https://arxiv.org/html/2605.26373#bib.bib46))通过算法等价性开创性地研究了这种结构化的非凸在线学习设置。他们证明，在重参数化的适当几何和光滑性假设下，应用于非凸损失的OGD近似模拟了在重参数化空间中应用于相应凸损失的OMD。这一关联导致了O(T^{2/3})的遗憾界。他们的结果留下了这样一个开放问题：比凸优化更慢的率是否是非凸在线学习设置固有的？由于恒等重参数化可恢复普通的OCO，在该类中通过精确梯度反馈可能达到的最佳遗憾是Θ(√T)。这引出了核心问题：
> 对于非凸隐凸损失，在精确梯度反馈下，OGD何时能恢复最优遗憾？并且同样的算法等价性原理能否扩展到赌博反馈设置？

在本文中，我们对精确梯度反馈问题给出肯定回答，并证明该框架可扩展到单点赌博反馈。具体来说，我们证明了OGD的O(√T)遗憾，讨论了算法等价性所需的相容性条件，展示了在没有该条件时的线性遗憾下界，并给出了赌博设置中的亚线性期望遗憾保证。我们在下一节中更详细地阐述我们的贡献。

### 1.1 主要贡献

我们研究损失函数在非线性重参数化下为凸的在线非凸学习，该重参数化对学习器是未知的。我们的结果解决了Ghai等人(2022 (https://arxiv.org/html/2605.26373#bib.bib46))提出的几个开放问题，精炼并扩展了OGD与OMD之间的算法等价性分析。我们的主要贡献如下：

- **精确梯度反馈下的最优遗憾。** 在精确梯度设置中，我们证明在Ghai等人(2022 (https://arxiv.org/html/2605.26373#bib.bib46))所考虑的几何相容性和光滑性假设下，OGD对隐凸损失实现了O(√T)的遗憾（定理1 (https://arxiv.org/html/2605.26373#Thmtheorem1)）。这改进了他们的O(T^{2/3})界，并与对抗性在线凸优化的最优遗憾相匹配。由于经典OCO可通过恒等重参数化恢复，该率对此问题类而言通常是最优的。我们的分析基于OGD与在线镜像下降(OMD)之间更尖锐的算法等价性，改进了支撑先前O(T^{2/3})保证的扰动分析。具体来说，我们的证明表明，非凸损失上的OGD以足够小的离散化误差追踪凸参数化中的OMD，从而保留了经典的√T遗憾。

- **重参数化的几何条件。** 先前的工作(Ghai等人，2022 (https://arxiv.org/html/2605.26373#bib.bib46))施加了对角Jacobian条件以保证OGD–OMD等价性所需的Hessian相容性。我们放松了这一结构假设，并给出了相容性的必要充分条件（命题1 (https://arxiv.org/html/2605.26373#Thmproposition1)），从而扩展了分析所涵盖的重参数化类别。

- **OGD的几何障碍。** 我们证明Hessian相容性条件并非仅仅是证明中的产物。我们证明存在一个违反相容性的光滑重参数化以及一个对抗性隐凸损失序列，使得OGD遭受Ω(T)的遗憾（定理2 (https://arxiv.org/html/2605.26373#Thmtheorem2)）。

- **赌博反馈。** 我们将分析扩展到单点赌博设置，其中学习器每轮仅观察一个损失值。针对非对抗性对手，我们在标准的额外Lipschitz性和有界性假设下，证明了期望遗憾界为O(T^{3/4})（定理3 (https://arxiv.org/html/2605.26373#Thmtheorem3)）。值得注意的是，我们的结果与赌博设置中凸损失OGD的已知最佳遗憾率相匹配(Flaxman等人，2005 (https://arxiv.org/html/2605.26373#bib.bib43))。

综上所述，我们的结果为结构化类别的在线非凸优化问题建立了OGD的新遗憾保证，将在线凸优化的经典结果扩展到了新的领域。

### 1.2 相关工作

**在线非凸优化。** 在线凸优化是对抗性序列决策的标准框架；例如，参见Hazan (2016 (https://arxiv.org/html/2605.26373#bib.bib39))；Shalev-Shwartz (2012 (https://arxiv.org/html/2605.26373#bib.bib38))；Orabona (2019 (https://arxiv.org/html/2605.26373#bib.bib37))。另一条工作线研究非凸损失的在线学习 (Krichene等人, 2015 (https://arxiv.org/html/2605.26373#bib.bib35); Agarwal等人, 2019 (https://arxiv.org/html/2605.26373#bib.bib34); Suggala和Netrapalli, 2020 (https://arxiv.org/html/2605.26373#bib.bib36); Héliou等人, 2020 (https://arxiv.org/html/2605.26373#bib.bib33))。在此类设置中，亚线性全局遗憾通常需要访问强预言机，例如允许连续域指数权重的采样预言机 (Maillard和Munos, 2010 (https://arxiv.org/html/2605.26373#bib.bib32); Krichene等人, 2015 (https://arxiv.org/html/2605.26373#bib.bib35))，或针对非凸损失的离线优化预言机 (Agarwal等人, 2019 (https://arxiv.org/html/2605.26373#bib.bib34); Suggala和Netrapalli, 2020 (https://arxiv.org/html/2605.26373#bib.bib36))。我们的工作走了一条不同的路线：我们不是假设一般非凸损失的预言机访问，而是利用损失序列的隐凸性，并通过非凸参数化中OGD与凸参数化中OMD之间的算法等价性来分析一阶算法 (Amid和Warmuth, 2020 (https://arxiv.org/html/2605.26373#bib.bib58); Ghai等人, 2022 (https://arxiv.org/html/2605.26373#bib.bib46); Li等人, 2022 (https://arxiv.org/html/2605.26373#bib.bib28))。文献中也有一些工作考虑具有特殊结构的非凸损失，例如非增函数与线性函数的复合 (Zhang等人, 2015 (https://arxiv.org/html/2605.26373#bib.bib44))，或较弱的凸性概念，如严格局部拟凸性 (Hazan等人, 2015 (https://arxiv.org/html/2605.26373#bib.bib25))和弱伪凸性 (Gao等人, 2018 (https://arxiv.org/html/2605.26373#bib.bib26))。

**隐凸优化。** 隐凸性近年来在若干离线确定性和随机优化设置中得到了研究 (Chen等人, 2025 (https://arxiv.org/html/2605.26373#bib.bib40); Fatkhullin等人, 2025a (https://arxiv.org/html/2605.26373#bib.bib42), b (https://arxiv.org/html/2605.26373#bib.bib41); Levin等人, 2025 (https://arxiv.org/html/2605.26373#bib.bib29))。这些工作考虑在非线性变换下允许凸重构的非凸问题，通常使用比在线算法等价性框架更弱的假设。然而，它们的焦点是离线优化：目标函数是固定的，或是作为固定数据生成分布上的期望。相比之下，我们研究的是对抗性在线设置，其中损失函数可能随时间任意变化，性能准则是遗憾而非收敛到全局最优。这种区别需要不同的分析，因为学习器必须在仅顺次观察到反馈的同时与事后最佳固定决策竞争。

**赌博反馈下的在线学习。** 在线赌博学习的文献非常广泛；我们建议参考Lattimore和Szepesvári (2020 (https://arxiv.org/html/2605.26373#bib.bib31))；Lattimore (2024 (https://arxiv.org/html/2605.26373#bib.bib30))以获取现代处理方法。对于赌博在线凸优化，Flaxman等人(2005 (https://arxiv.org/html/2605.26373#bib.bib43))引入了一种基于球面平滑的单点梯度估计器，表明当仅观察到函数值时可以实施基于梯度的在线方法。赌博设置也已被研究用于一般Lipschitz非凸损失和特殊非凸类别 (Zhang等人, 2015 (https://arxiv.org/html/2605.26373#bib.bib44); Gao等人, 2018 (https://arxiv.org/html/2605.26373#bib.bib26))。我们的赌博结果在焦点上有所不同：我们考虑隐凸损失，并使用平滑化以及OGD–OMD等价性将遗憾保证从凸参数化转移到原始非凸参数化。因此，虽然我们算法模板的灵感来自赌博OCO，但主要挑战在于控制赌博梯度估计、非线性重参数化以及算法等价性中近似误差之间的相互作用。

## 2 隐凸损失的在线学习

在本节中，我们介绍在线隐凸优化(OHCO)问题，该问题扩展了著名的在线凸优化(OCO)设置 (Shalev-Shwartz, 2012 (https://arxiv.org/html/2605.26373#bib.bib38); Hazan等人, 2015 (https://arxiv.org/html/2605.26373#bib.bib25); Orabona, 2019 (https://arxiv.org/h