【博士论文】基于冲量的加速优化算法

2021 年 11 月 29 日 专知

来自北京大学李欢的博士论文，入选2021年度“CCF优秀博士学位论文奖”初评名单！

https://www.ccf.org.cn/Focus/2021-11-22/750448.shtml

基于冲量的加速优化算法

优化在机器学习中扮演着重要的角色。作为理论上收敛速度最快的一阶优化算法，加速梯度法在机器学习领域取得了广泛的应用。本文将研究经典加速算法在带约束凸优化问题、随机凸优化问题、分布式凸优化问题和非凸优化问题上的应用。本文首先介绍加速技巧在交替方向乘子法(ADMM)中的应用，并提出了具有最优非遍历意义收敛速度的加速ADMM算法。经典ADMM算法在求解非强凸非光滑问题时具有遍历意义下O ( 1 K ) 收敛速度和非遍历意义下O ( 1 √ K ) 收敛速度。在稀疏和低秩学习中，遍历意义中的取平均操作会破坏解的稀疏性和低秩性，因此在实际应用中我们往往使用非遍历意义解。我们提出的加速ADMM具有非遍历意义下更快的O ( 1 K ) 收敛速度。并且我们还证明了经典ADMM的非遍历意义下O ( 1 √ K ) 收敛速度是紧的，即经典ADMM具有较慢的非遍历意义收敛速度是算法本身的特性，并非由于证明技巧不足所致。另外，我们证明了当求解非强凸非光滑问题时，ADMM类型算法的复杂度下界是O ( 1 K ) ，即任何ADMM类型算法都不可能比O ( 1 K ) 更快。

在大数据背景下，加速技巧不仅应用于传统优化，而且在随机优化和分布式优化中也有广泛应用。本文研究了在随机优化领域经典的加速随机对偶坐标上升算法，并对其原问题解的复杂度进行分析。该算法使用加速随机坐标下降法求解对偶问题，当目标函数是强凸非光滑函数时，对偶问题解具有O ( 1 √ ϵ ) 的复杂度。在实际应用中，我们需要使用的是原问题解，而非对偶问题解，因此我们需要度量原问题解的复杂度。已有结论显示，对于一般的带约束凸优化问题，当对偶问题解具有O ( 1 √ ϵ ) 的复杂度时，原问题解只有O ( 1 ϵ ) 的复杂度。我们证明了如果对原问题解合适地进行加权平均，原问题解具有和对偶问题解一样的O ( 1 √ ϵ ) 的复杂度。当将加速随机对偶坐标上升算法应用到机器学习中经典的经验损失最小问题时，我们的收敛速度比当前已有结论提高了O ( log 1 ϵ ) 因子。

除了随机优化领域，本文还研究了分布式优化领域的加速算法。我们首先对分布式优化中经典的EXTRA算法重新分析，并给出了更快的O ( ( L µ + 1 1−σ2 (W) ) log 1 ϵ ) 的计算复杂度和通信复杂度。然后我们使用Catalyst框架对EXTRA加速，得到了强凸情况下复杂度为O (√ L µ(1−σ2 (W)) log L µ(1−σ2 (W)) log 1 ϵ ) 和非强凸情况下复杂度为O (√ L ϵ(1−σ2 (W)) log 1 ϵ ) 的加速EXTRA算法。除了对EXTRA进行扩展，我们还使用加速罚函数法对经典的分布式加速梯度法进行解释，并给出了具有最优计算复杂度（强凸情况下 O (√ L µ log 1 ϵ ) 和非强凸情况下O (√ L ϵ ) ）和接近最优通信复杂度（强凸情况下O (√ L µ(1−σ2 (W)) log2 1 ϵ ) 和非强凸情况下O (√ L ϵ(1−σ2 (W)) log 1 ϵ ) ）的分布式加速算法。与已有分布式算法相比，我们提出的加速EXTRA算法和加速罚函数法具有更低的计算复杂度，同时我们的通信复杂度或者与当前最好算法一样，或者只比当前最好算法高 O ( log L µ(1−σ2 (W))) 或O ( log 1 ϵ ) 因子。最后，我们研究了加速算法在非凸低秩优化中的应用。我们首先分析了该问题中目标函数的曲面性质，证明了当受限于某个特定凸集时，目标函数是受限制的局部强凸函数。基于该性质，我们提出了交替约束加速梯度法并证明了该算法能够局部线性收敛到最优解。相比于梯度下降法，我们的收敛速度对条件数具有最优的 √ L/µ的依赖关系。另外，当初始值为任意值时，我们的算法能够全局收敛到梯度为0的点。

专知便捷查看