A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
复制标题
DOI：
--
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Guodong Zhang;Xuchao Bao;Laurent Lessard;R. Grosse
中科院分区：
文献类型：
--
作者：
Guodong Zhang;Xuchao Bao;Laurent Lessard;R. Grosse
积分二次约束 (IQC) 理论允许验证包含非线性或不确定元素的互连系统的指数收敛性。在这项工作中，我们采用 IQC 理论来研究平滑和强单调博弈的一阶方法，并展示如何设计定制的二次约束以获得严格的收敛速度上限。使用这个框架，我们恢复了梯度法~(GD)的现有界限，导出了近点法~(PPM)和乐观梯度法~(OG)的更清晰的界限，并为负动量法~(NM)提供了\emph{第一次}全局收敛速度，其迭代复杂度为$\bigo(\kappa^{1.5})$，与其已知的下界相匹配。此外，对于时变系统，我们证明具有最佳步长的梯度方法可以通过二次李亚普诺夫函数实现最快的可证明最坏情况收敛率。最后，我们进一步将分析扩展到随机博弈，并研究乘性噪声对不同算法的影响。我们证明，如果每批只查询一次梯度，具有一步内存的算法就不可能实现加速（与随机强凸优化设置相反，其中已经证明了这种加速）。然而，我们展示了一种算法，该算法可以通过每批两次梯度查询来实现加速。
The theory of integral quadratic constraints (IQCs) allows the certification of exponential convergence of interconnected systems containing nonlinear or uncertain elements. In this work, we adapt the IQC theory to study first-order methods for smooth and strongly-monotone games and show how to design tailored quadratic constraints to get tight upper bounds of convergence rates. Using this framework, we recover the existing bound for the gradient method~(GD), derive sharper bounds for the proximal point method~(PPM) and optimistic gradient method~(OG), and provide \emph{for the first time} a global convergence rate for the negative momentum method~(NM) with an iteration complexity $\bigo(\kappa^{1.5})$, which matches its known lower bound. In addition, for time-varying systems, we prove that the gradient method with optimal step size achieves the fastest provable worst-case convergence rate with quadratic Lyapunov functions. Finally, we further extend our analysis to stochastic games and study the impact of multiplicative noise on different algorithms. We show that it is impossible for an algorithm with one step of memory to achieve acceleration if it only queries the gradient once per batch (in contrast with the stochastic strongly-convex optimization setting, where such acceleration has been demonstrated). However, we exhibit an algorithm which achieves acceleration with two gradient queries per batch.