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

优化在机器学习中扮演着重要的角色。作为理论上收敛速度最快的一阶优化算 法，加速梯度法在机器学习领域取得了广泛的应用。本文将研究经典加速算法在带 约束凸优化问题、随机凸优化问题、分布式凸优化问题和非凸优化问题上的应用。本文首先介绍加速技巧在交替方向乘子法(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的点。