【强基固本】深度学习算法收敛性证明之拓展SGD

“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。

作者：知乎—大厂推荐算法

地址：https://www.zhihu.com/people/zhao-li-cheng-90

这是我“科研喂饭”系列的第四篇文章，希望它能为正在从事算法研发以及对算法研发感兴趣的小伙伴带来帮助。我写这个专栏的目的是希望能尽力降低科研的门槛，让大家更好地享受科研的乐趣。

文章中会涉及到论文的细节，以数学推导过程为主。限于篇幅以及讲解的便利性，我将会对原文作出调整和删减。如果大家在阅读本文时感到困惑，可以进一步参阅文献，看一看原作者的讲解。

由于本文篇幅较长，大家可以根据实际情况挑选自己感兴趣的部分来读：

• 我是小白：可以先看看SGD简介：深度学习算法收敛性证明，再从第1章开始；

• 我只想看拓展SGD算法：直接从第2章开始，遇到不明含义的数学符号参考前文；

• 我只想看拓展SGD算法理论分析及收敛性证明：直接从第3章开始，遇到不明含义的数学符号参考前文。

01

引言

1.1 回顾SGD

在科研喂饭系列的第一篇文章里，我们学习了最朴素的SGD算法（大厂推荐算法：【强基固本】深度学习算法收敛性证明）以及它在目标函数为convex函数时的收敛性证明。朴素SGD的变量迭代表达式：

其中  是学习率，  是  时刻目标函数  在  处的梯度。它的收敛性证明基于以下前提假设（来自参考文献[1, 第2.1节] ）：

• 对于任意  ，  都是关于  的convex函数
• 变量有界：

或者对于变量的任意一维 

• 梯度有界：

或者对于变量的任意一维 

判定收敛的指标为统计量  （Regret）：

若当  ，  的均摊值  ，我们认为这样的算法是收敛的，并且一般认为  随着  增长得越慢，算法收敛越快。

02

拓展SGD算法

我们将从以下两个角度来拓展SGD算法：1）变量迭代表达式，2）目标函数与判定收敛的指标。

2.1 变量迭代表达式

我们知道Adam算法引入了动量这一概念，即让历史值与当前的更新增量值做加权和。其实Adam并不是最早使用动量这一概念的，在SGD算法的拓展中早就有这样的先例，文献[2]提到了多种SGD的变形，其中一种叫动量SGD变量迭代（简称为动量SGD），形如：

另一种叫NAG变量迭代（简称为NAG），形如：

它们可以统一表达为

其中  （动量SGD）或 （NAG）。

动量SGD与NAG的表达方式并不惟一。我们补充定义  ，那么

• 动量SGD：  ，  （文献[3]与Tensorflow2.0文档一致）

• NAG：

 ，  （文献[3]）

 ，  （Tensorflow2.0文档）

我们首先证明上述两种NAG的表达式是等价的。代换变量  （谨记： 

才是变量），于是

因此两种NAG写法等价。接着我们证明文献[3]和Tensorflow2.0文档的写法与我们提出的写法等价：

• 动量SGD：当  时，  ；当 时，

• NAG：当  时，  ；当 时，

TensorFlow API中的SGD优化器可完整表示为：tf.optimizers.SGD(learning_rate=  ，momentum=  ，nesterov=  ）

•  对应学习率，  对应momentum；
•  时对应动量SGD，对应nesterov=False；  时对应NAG，对应nesterov=True。

我们对本小节做个简单的总结：

• 变量迭代式中  在时序上与  、  均有关，而之前朴素SGD算法中  仅与  有关；

• 拓展SGD算法相比朴素的SGD多出了动量的部分。动量的计算可以是  （不包含梯度），也可以是  （包含梯度）

2.2 目标函数与判定收敛的指标

因为任意  都是关于  的convex函数这一假设太过严苛（只有线性回归、逻辑回归满足要求），严重脱离工程实际，所以我们考虑放宽这一假设。对于非convex的目标函数，在  时，  不一定趋于  ，  也就不一定趋于  ，因此我们有必要调整判定收敛的指标。

对于无限制条件的非convex优化问题，我们一般认为当目标函数的梯度消失时，算法收敛。由于目标函数非convex，我们不得不牺牲全局最优解，转而接受局部最优解。然而问题还没有全部解决。对于传统的非convex优化问题，它的目标函数是明确给定的，与时刻  无关，但是在深度学习领域这是不现实的，尤其是在推荐系统中，训练样本是源源不断地涌过来的。在这样的应用场景中，我们考虑定义一个抽象的目标函数：

我们把  看作随机函数  的样本，根据大数定理，

我们对上述这些符号表达式做一些解释：  是一个随机函数，  是参数，  是随机源，源自训练样本的特征  和标签  ；  是随机函数  在  时刻的实现（也叫样本），具有随机性；  是关于  的确定性函数，产生自无限多个  的均值，趋近于总体均值，无随机性。我们要优化的目标函数是  ，这是一个全局却不可知的函数；我们只能通过获取尽量多的  来试图接近  。有了这些知识储备，我们来初步认识一下判定收敛的指标：

从表达式可以看出，  是一系列梯度模值平方的期望的最小值，也就是说，只要有某一个t时刻梯度消失了，算法就收敛了。采用这个指标的文献有[2,4]。在正式接受这个指标之前，我们要意识到，这个判定收敛的指标是比较弱的：它只要求存在时刻  使梯度消失，并没有要求当  大于某时刻  时，梯度（必然、几乎必然、以概率1）消失；也就是说，如果我们任由算法无休止地运行下去，算法可能会发散。

我们详细地剖析一下  ，重点关注  。为什么要对  求期望呢？我们知道函数  是个确定性函数，同样的输入会产生同样的输出，不存在随机性，那么必然是  存在随机性。联想  的迭代表达式：

 是初始值，无随机性；  与  、  有关，  ，由于  具有随机性，我们令  ，那么  与随机变量  有关；  与  、  、  、  有关，  又与  、  有关，由于  也具有随机性，我们同样令  ，那么  与随机变量  、  有关。通过上面的推导，我们可以大胆地得出：  与随机变量  有关（与  无关），因为  与  都有关（与  无关）。为了在求期望时表现出这一规律，我们将符号表达式完善一下：

 表示对随机变量  求期望。于是判定收敛的指标最终写作：

当  时，若  的均摊值  ，我们认为这样的算法是收敛的，并且一般认为  随着  增长得越慢，算法收敛越快。

最后我们再对符号  做一点说明，  表示基于  时刻及之前的随机变量求期望，  时刻及之前的随机变量有  。如果我们只想对  求期望，我们使用  这个符号。它表示给定  时刻之前的随机变量值，仅基于  时刻的随机变量  求期望，  时刻之前的随机变量有  。我们举一个朴素SGD算法的例子来运用这些符号：如果  ，  ，  ，  ，那么

•  ：

在收敛性证明中，我们将会用到  和  这两个符号。

2.3 前提假设

前面我们提到了放宽 的假设，允许  是非convex函数。由于非convex函数不满足  ，于是  不成立。在正式开始证明算法收敛性之前，我们要重新给出前提假设：

• 变量有界假设：表述与SGD一致；

• 梯度有界假设（对象为  而非  ）：

或者对于变量的任意一维 

•  虽不再是convex函数，但仍须是L-smooth函数，即满足（1）  可导，  在定义域内处处存在；（2）存在  ，使得定义域内任意  和  都有 （第一定义）

亦即（第二定义）

这个条件也被称作利普希茨连续（Lipschitz continuous）；

• 对于  ，随机变量  定义为  ，  须满足  ，  ，且在  时，  与  统计独立。

 其实可以从已知条件中推导得出：

03

收敛性证明

我们首先证明两个引理。

3.1 引理一

令  。当  按照拓展SGD算法来迭代时，  满足

下面我们给出证明。拓展SGD算法的迭代式如下：

当  时，

命题得证；当  时，

命题得证。

3.2 引理二

当  按照拓展SGD算法来迭代时，

下面我们给出证明。当  时，  ，

当  时，

命题得证。

证明引理一与引理二的关键在于拆分动量项：

 可看作变量现值与前值的差（动量SGD）、变量现值与前值的预更新值的差（NAG）。

3.3 完整证明

我们要证明统计量  在  时趋于 0。

我们从从引理二入手，令  ，因为  是L-smooth函数

根据引理二

接着我们做数学变形：

不等号两边对随机变量  取期望：

接着我们将分别处理（1）和（2）：

• （1）：

这里用到了  的统计特性：  ，  ，且在  时，  与  统计独立；

• （2），我们关注期望算子内的表达式：

稍作整理：

下面我们要关注（3）：

• 根据L-smooth函数的第二定义：

• 根据  的定义：  ，于是

于是（3）的关键在于  ，这里我们要用到引理一：  。首先做个换元，化简表达式：令  ，这样  。  存在闭式解：  ，当  时，

我们考察  ：当  时，

令  ，有  ，  ；运用琴生（Jensen）不等式：

于是

因为

（最后的放缩利用了梯度有界和统计特性），故

最后的等号将  还原为  。有了  的上界，我们可据此计算  的上界：当  时，

随即计算  的上界：

我们做一下数学变形：

我们还需要补充讨论  的情形：当  时，  ， 

于是

结合  和  的情形，我们让不等号两边同时对  求和：

之后是放缩，我们将不等号左边缩小，右侧放大，以使不等式仍成立：

• 左侧缩小：

• 右侧放大：我们暂时只放大其中一项：

其中  ， 

最终

这样  的上界就只与学习率  有关了，在下一节我们设计最优的学习率。

04

设计最优学习率

4.1 小试牛刀

首先我们不妨沿用之前的做法，即假设  ，让学习率呈现多项式衰减。我们首先关注  ：

于是不等号右边：

再看不等号左边，当  时，

最终，令 

• 当  时， 

• 当  时， 
• 当  时， 

这意味着在当前的证明框架下，无论  取何值，  在  时，都不趋近于  ！最好的上界在  ，即  时取到。有没有挽救的余地呢？

4.2 从失败走向成功

根据文献[2]中的定理3，我们可以这样做：令

这里我们做一些解释：改进前的方案是  ，即学习率是关于迭代次数  的函数；改进后的方案是：学习率是一个与迭代次数  无关的常数，但是这个常数是关于总迭代次数  的函数。这时，  的上界修正为

（把表达式  的参数  置为  ，再把  、  、  中与  有关的项单独列出）

我们假设  ，那么

当  时，  取到最优上界  ，此时  ，  可取  ，以使学习率尽量大。

当  时，学习率的选取与迭代总次数  有关，算法不再支持无限迭代了。我们举例说明：

• 变量迭代  次（不是epoch数），学习率为  ；

• 变量迭代  次，学习率为  。

虽然我们成功地让算法收敛了，但是我们牺牲了算法的无限可迭代性。

05

总结

在放宽了目标函数对convexity的限制后，我们将判定收敛的指标调整为  ，这使得拓展SGD算法的收敛性证明困难了不少。看到这里的小伙伴都是勇士，给你们点赞！

06

参考文献

[1] M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in Proceedings of the 20th international conference on machine learning (ICML-03), 2003, pp. 928– 936.

[2] T. Yang, Q. Lin, and Z. Li, “Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization,” arXiv preprint arXiv:1604.03257, 2016.

[3] I. Sutskever, J. Martens, G. Dahl, and G. Hinton, “On the importance of initialization and momentum in deep learning,” in International conference on machine learning, 2013, pp. 1139– 1147.

[4] X. Chen, S. Liu, R. Sun, and M. Hong, “On the convergence of a class of adam-type algorithms for non-convex optimization,” arXiv preprint arXiv:1808.02941, 2018.

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“强基固本”历史文章

更多强基固本专栏文章，

请点击文章底部“阅读原文”查看

分享、点赞、在看，给个三连击呗！