优化｜无悔动力学解释凸优化算法

原文信息：No-regret dynamics in the Fenchel game- A unified framework for algorithmic convex optimization

原文作者：Jun-Kun Wang， Jacob Abernethy， Kfir Y. Levy

论文解读者：赵田田

编者按：

对于一个凸优化问题，我们可以把它看作是一个min-max问题中的一部分. 而对于求解min-max问题，我们可以考虑让对应极小化和极大化的两个变量依次进行更新，并持续重复这个过程. 本文将这两个变量可以采取的更新方法限定在无悔学习策略（no-regret learning algorithms）. 可以证明，许多的一阶凸优化算法，都可以看作是双方采取不同的无悔学习策略来求解min-max问题. 利用这个特别的框架（FGNRD, the Fenchel game no-regret dynamics），我们可以给出一套算法的收敛性证明，并提出一些包含在框架中的新算法，它们同时也具有好的收敛结果.

一、从凸优化到min-max问题

二、无悔动力学：求解min-max问题

2.1 整体算法框架

2.2 用 Regret 刻画解的接近程度

2.3 OAlg 算法

我们接下来介绍 OAlg 算法的具体选择 (这里继续使用 Protocol 1中的符号). OAlg 算法基本上可以被分为两大类: Batch-style 和 Update-style. 此外还有一种不属于二者的更新方法: BESTRESP+.

Update-style的目标函数集中在最新的损失函数上, 同时增加了一项 Bregman 距离, 其中 �是生成距离的函数. Update-style 类的算法如下所示.

2.4 刻画 Regret 的上界

对于 Batch-style 类中的其他算法, 我们都可以从 Lemma 3 出发, 得到 Regret 上界的表达式. 对于 Update-style 类的算法, 我们有如下形式的结论 (以 OPTIMISTICMD 为例, 其余算法省去):

三. 从无悔动力学到凸优化算法

定理的证明过程如下.

根据 2.2 节的 Theorem 2 和 2.4 节的 Lemma 2，可以得到

3.3 Boundary Frank-Wolfe 算法（新）

参考文献

[1] Wang, J., Abernethy, J.D., & Levy, K.Y. (2021). No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization. ArXiv, abs/2111.11309..