1.3　加速算法中的代表性工作综述

根据上一节给出的“加速”定义，第一个加速算法可能是Polyak提出的重球法［Polyak，1964］．考虑最小化一个L-光滑（见定义18）、μ-强凸（见定义15）且二阶连续可微的目标函数，并且令ε表示所需精度．重球法将经典梯度下降法的复杂度降低到．Nesterov于1983年提出了加速梯度下降法（AGD）．当最小化一个L-光滑的一般凸函数（见定义15）时，AGD将经典梯度下降法的复杂度降低到．之后，Nesterov相继发表了若干重要的工作，包括1988年提出的另一个最小化L-光滑函数的加速梯度法［Nesterov，1988］、2005年提出的针对非光滑函数的平滑与加速技术［Nesterov，2005］以及2007年提出的用于求解复合问题的加速算法［Nesterov，2007］（正式发表是2013年［Nesterov，2013］）．然而，Nesterov的原创性工作一开始并没有在机器学习领域得到重视，这可能是因为机器学习中的问题大部分是非光滑的，例如稀疏、低秩学习经常使用促进稀疏和低秩的正则化项，从而使得目标函数不可微．Beck和Teboulle于2009年提出了用于求解复合优化问题的加速邻近梯度法（APG）［Beck and Teboulle，2009］．该方法是［Nesterov，1988］的扩展，比［Nesterov，2007］更简单[1]，并且APG天然适用于求解当时很流行的稀疏、低秩学习模型．因此，APG在机器学习领域被广泛关注．之后，Tseng对已有的加速算法给出了一个统一的分析［Tseng，2008］，Bubeck针对高阶光滑的凸优化问题提出了接近最优的加速算法［Bubeck et al.，2019］．

Nesterov加速梯度法的加速原理并不是很直观．很多研究者试图对他的加速梯度法为什么能够加速进行解释．Su等人从微分方程的角度解释AGD［Su et al.，2014］，Wibisono等人进一步将该思路扩展到高阶加速梯度法［Wibisono et al.，2016］．Lessard等人及Fazlyab等人使用鲁棒控制理论中的积分二次约束（Integral Quadratic Constraint）技术提出了线性矩阵不等式（Linear Matrix Inequality），并用于解释加速梯度法［Fazlyab et al.，2018；Lessard et al.，2016］．Allen-Zhu和Orecchia将加速梯度法视为梯度下降法和镜像下降法（Mirror Descent）的线性耦合（Linear Coupling）［Allen-Zhu and Orecchia，2017］．另一方面，一些研究者试图提出新的可解释的加速梯度法．Kim和Fessler使用性能估计问题（Performance Estimation Problem）技术提出了一种新的最优一阶算法［Kim and Fessler，2016］，其复杂度只有Nesterov加速梯度法的一半．Bubeck受椭球法启发提出了一种几何加速法［Bubeck et al.，2015］，Drusvyatskiy等人则指出Bubeck方法产生的迭代序列可以通过计算目标函数的二次下界函数（Quadratic Lower-Model）的最优平均得到［Drusvyatskiy et al.，2018］．

对于带线性约束的凸优化问题，其与无约束问题的不同点在于我们需要同时考虑目标函数离最小值的差和约束的误差．理想情况下，目标函数误差和约束误差应该以同样的速度减小．将Nesterov的加速技巧扩展到带约束问题的一个直接做法是使用加速梯度下降法求解对偶问题（见定义30）．典型例子包括加速对偶上升法［Beck and Teboulle，2014］和加速增广拉格朗日乘子法［He and Yuan，2010］．二者在对偶空间都具有最优的收敛速度．Lu等人［Lu and Johansson，2016］和Li等人［Li and Lin，2020］进一步考虑了加速对偶上升法及其在随机优化中的变种在原始空间的复杂度．基于对偶的算法的一个主要不足之处是需要在每次迭代中求解一个子问题．线性化是解决这个问题的有效策略．具体地，Li等人提出了惩罚因子逐渐递增的加速线性化罚函数法［Li et al.，2017］，Xu提出了加速线性化增广拉格朗日乘子法［Xu，2017］．对于一般的光滑凸优化问题，我们也可以加速交替方向乘子法（ADMM）和原始-对偶算法［Li and Lin，2019；Ouyang et al.，2015］，它们是带约束优化中最常用的两个方法．当目标函数是强凸函数时，即使不使用Nesterov加速技巧，ADMM和原始-对偶算法也可以有更快的收敛速度［Chambolle and Pock，2011；Xu，2017］．

Nesterov的加速梯度法也可以扩展到非凸问题上．［Ghadimi and Lan，2016］使用AGD最小化一个光滑非凸函数（见定义17）和一个非光滑凸函数（见定义12）的和．受［Ghadimi and Lan，2016］启发，Li和Lin提出了极小化目标函数为光滑非凸函数和非光滑非凸函数的和的AGD变种［Li and Lin，2015］．［Ghadimi and Lan，2016；Li and Lin，2015］都证明了加速梯度法可以收敛到一般非凸问题的一阶临界点（Critical Point，见定义40）．Carmon等人进一步给出了复杂度为的分析［Carmon et al.，2017］．对于许多机器学习问题，例如矩阵感知（Matrix Sensing）和矩阵填充，所有的局部最优解处的目标函数值都近似于全局最优解处的目标函数值［Bhojanapalli et al.，2016；Ge et al.，2016］．因此，我们只需要考虑如何避开鞍点（见定义35）．［Carmon et al.，2018］第一个给出了可以收敛到二阶临界点的加速算法．具体地，该算法交替运行负曲率下降法（Negative Curvature Descent，NCD）和几乎凸加速梯度下降法（Almost Convex AGD，AC-AGD）这两个子程序，因此可以被视为加速梯度法和Lanczos方法的组合．Jin等人进一步提出了单循环加速梯度法［Jin et al.，2018］．Agarwal等人则提出了Nesterov-Polyak方法的巧妙实现［Agarwal et al.，2017］，其中快速近似求解逆矩阵时用到了加速方法．［Agarwal et al.，2017；Carmon et al.，2018；Jinet al.，2018］中算法的复杂度都是．

加速技巧也可以应用于随机优化．与确定性优化相比，随机优化的主要难点是梯度中的噪声不会随着迭代的进行而趋于0．因此，当目标函数是强凸光滑函数时，随机梯度法只有次线性的收敛速度．方差缩减（Variance Reduction，VR）是减小噪声影响的有效技术［Defazio et al.，2014；Johnson and Zhang，2013；Mairal，2013；Schmidt et al.，2017］．Allen-Zhu使用方差缩减和冲量技术提出了第一个真正的加速随机算法：Katyusha［Allen-Zhu，2017］．Katyusha是一个在原始空间运行的算法．加速随机算法的另一种方式是在对偶空间求解问题，这样就可以方便地使用加速随机坐标下降算法［Fercoq and Richtárik，2015；Lin et al.，2014；Nesterov，2012］和加速随机原始-对偶算法［Lan and Zhou，2018；Zhang and Xiao，2017］．另一方面，2015年Lin等人使用加速邻近点算法提出了一个加速一阶算法的统一框架：Catalyst［Lin et al.，2015］．该加速框架的思想可以在更早的文献［Shalev-Shwartz and Zhang，2014］里找到．随机非凸优化也是机器学习中的一个重要课题，感兴趣的读者可参考［Allen-Zhu，2018；Allen-Zhu and Hazan，2016；Allen-Zhu and Li，2018；Ge et al.，2015；Reddi et al.，2016；Tripuraneni et al.，2018；Xu et al.，2018］．需要特别指出的是，Fang等人于2018年提出了一般的随机路径积分差分估计子算法SPIDER［Fang et al.，2018b］，可以以低得多的计算量跟踪感兴趣的量，并应用于归一化的梯度下降法，得到了接近最优的收敛速度．

加速技巧也可以用于并行优化．并行算法有两种实现方式：异步更新和同步更新．对于异步算法，每一个机器不需要等待其他机器完成计算．代表性工作包括异步加速梯度下降法［Fang et al.，2018a］和异步加速坐标下降法［Hannah et al.，2019］．根据不同的连接网络拓扑，同步算法包括中心化算法和去中心化算法．中心化算法的典型代表包括分布式ADMM［Boyd et al.，2011］、分布式对偶上升法［Zheng et al.，2017］和它们的变种．中心化算法的一个主要性能瓶颈是中心节点的通信压力很大［Lian et al.，2017］．去中心化算法在控制领域早已被深入研究，但直到2017年人们才知道去中心化算法的复杂度下界［Seaman et al.，2017］．另外，［Seaman et al.，2017］还提出了一个达到该下界的最优分布式对偶上升算法．受该复杂度下界启发，Li等人进一步分析了分布式加速梯度法，并给出了接近最优的通信复杂度和计算复杂度（差一个log因子）［Li et al.，2020］．

---

[1]在每次迭代中，APG［Beck and Teboulle，2009］只用到了最近两次迭代的信息，并求解一次邻近映射问题，而［Nesterov，2007］则需要之前所有迭代的信息并需要求解两次邻近映射问题．