从非凸到强凸：面向在线优化的曲率自适应FTPL算法

# 曲率自适应FTPL在线优化  
来源：https://arxiv.org/html/2606.02948  
## 从非凸到强凸：曲率自适应FTPL在线优化  
Chirag PabbarajuStanford University。邮箱：[email protected]。  
Ambuj TewariUniversity of Michigan, Ann Arbor。邮箱：[email protected]。  

###### 摘要  
曲率适应是在线优化中的一个经典主题：对于凸Lipschitz损失，自适应方法在一般凸损失的最优O\(T\)O\(\\sqrt\{T\}\)遗憾和强凸下的O\(log⁡T\)O\(\\log T\)遗憾之间插值。最近的研究表明，假设能够访问一个近似的离线优化预言机，即使对于在线非凸Lipschitz损失，跟随扰动领导者（FTPL）也能达到最优的O\(T\)O\(\\sqrt\{T\}\)遗憾，但这些保证没有利用曲率。我们证明FTPL可以在非凸设置中实现曲率自适应，而无需预先知道曲率如何随时间累积。我们的算法用仅利用过去信息选择的时间变化尺度替代了标准FTPL的固定扰动尺度。我们给出了一个简单的跟随领导者调参规则用于该尺度，并证明它与事后最佳选择在常数因子内竞争。所得到的方法对于任意非凸Lipschitz损失实现O\(T\)O\(\\sqrt\{T\}\)遗憾，并随着累积曲率增长而改进；当累积曲率线性增长时（包括经典的强凸情况），通过足够精确的预言机调用，它实现O\(log⁡T\)O\(\\log T\)遗憾。我们通过针对预设累积曲率序列（即使是一维凸损失）的匹配下界来补充这些上界，表明最坏情况非凸遗憾与曲率驱动的快速率之间的权衡是内在的。  

## 1 引言  
在线优化的一个核心问题是遗憾如何随回合数TT增长。两个经典结果描述了这种依赖关系：对于凸且Lipschitz的损失，最优遗憾为O\(T\)O\(\\sqrt\{T\}\)（Zinkevich,2003 (https://arxiv.org/html/2606.02948#bib.bib11)），而对于强凸且Lipschitz的损失，它改进为O\(log⁡T\)O\(\\log T\)（Hazan等人,2006 (https://arxiv.org/html/2606.02948#bib.bib12)）。已知这两个速率都是紧的（Abernethy等人,2008 (https://arxiv.org/html/2606.02948#bib.bib7)）。因此，一个自然的目标是设计其保证适应损失序列曲率的算法。在一项开创性工作中，Bartlett等人（2007 (https://arxiv.org/html/2606.02948#bib.bib20)）为在线*凸*优化引入了自适应梯度方法，其遗憾根据序列中的累积强凸性在O\(T\)O\(\\sqrt\{T\}\)和O\(log⁡T\)O\(\\log T\)之间无缝插值。这些想法此后影响了广泛使用的方法，如Adagrad（Duchi等人,2011 (https://arxiv.org/html/2606.02948#bib.bib9)）和Adam（Kingma和Ba,2015 (https://arxiv.org/html/2606.02948#bib.bib8)）。最近，Suggala和Netrapalli（2020 (https://arxiv.org/html/2606.02948#bib.bib17)）表明，假设能够访问求解扰动离线问题的预言机，跟随扰动领导者（FTPL）框架即使对于*非凸*Lipschitz损失也能实现O\(T\)O\(\\sqrt\{T\}\)遗憾。这些结果自然引出了以下问题：  
> *能否使FTPL适应曲率，对于一般非凸Lipschitz损失实现O\(T\)O\(\\sqrt\{T\}\)遗憾，同时在存在足够强凸性时改进为O\(log⁡T\)O\(\\log T\)？*  
在本文中，我们肯定地回答了这个问题。我们的方法基于在FTPL扰动中引入一个时间变化的噪声尺度，该尺度仅使用过去信息自适应选择。我们首先推导出一个由该噪声尺度序列参数化的通用遗憾界。然后我们表明，选择这些参数本身可以视为一个元在线学习问题，对此一个简单的FTL方法可以实现常数竞争比。所得到的算法在O\(T\)O\(\\sqrt\{T\}\)和O\(log⁡T\)O\(\\log T\)之间插值的遗憾，而无需预先知道损失的曲率。我们进一步用匹配的下界补充我们的上界，表明我们元优化的界是问题内在的，而不是我们方法的人为产物。  

除了理论意义，我们的设置还受到一类广泛问题的启发，其中学习器遇到形式为 ft=gt\+rt,f\_\{t\}=g\_\{t\}\+r\_\{t\} 的复合损失，其中gtg\_\{t\}是可能非凸的数据依赖项，而rtr\_\{t\}是强凸正则化项。这种复合结构在现代机器学习和优化中普遍存在。一个突出的例子出现在持续学习（Kirkpatrick等人,2017 (https://arxiv.org/html/2606.02948#bib.bib2)）中，其中gtg\_\{t\}表示任务特定损失，由于神经网络参数化通常是非凸的，而rtr\_\{t\}是一个正则化器，*将当前迭代绑定到先前学习的模型*，从而减轻灾难性遗忘。相比之下