“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。
地址：https://www.zhihu.com/people/zhao-li-cheng-90
01
这是我“科研喂饭”系列的第一篇文章，希望它能为正在从事算法研发以及对算法研发感兴趣的小伙伴带来帮助。科研的道路寂寞且艰辛。我希望能尽力降低科研的门槛，让大家更好地享受科研的乐趣。
深度学习算法的科普文章网上已有千千万万（推荐Ruder写的[1]），然而它们大多是介绍算法本身或者是总结各种算法、比较各个算法的异同，并不涉及算法的收敛性证明。收敛性证明既是衡量算法有效性的重要指标，又是提出新算法的思想源泉；也就是说，掌握现有算法的收敛性证明可以帮助我们构造出新的算法（最终实现批量生产顶会文章的目的）。
文章中会涉及到论文的细节，以数学推导过程为主。限于篇幅以及讲解的便利性，我将会对原文作出调整和删减。如果大家在阅读本文时感到困惑，可以进一步参阅文献，看一看原作者的讲解。
由于本文篇幅较长，大家可以根据实际情况挑选自己感兴趣的部分来读：
1. 引言
1.1 深度学习
深度学习领域的研究主要包含两个大分支：
深度学习的模型训练过程本质上就是求解一个最优化问题：
其中 为待优化的损失函数，因而要将其最小化， 为网络参数（此时网络结构已经确定下来了）， 是网络参数的定义域（或者叫限制域）。在深度学习这个具体场景中，我们可以将优化问题具体化：
定义域 一般无需指定，直接略去即可，或者指定为 ，意为 维空间内的全体实数，其中 为参数总数；
是基于某个（数量巨大的）样本集的损失函数，我们把样本集记为 ， 为网络结构的输入（可以理解为特征）， 为该样本的标签（可以是一个实数，抑或是二分类值0-1、多分类值0-1-2-3等），那么 ，即损失函数 为各个样本损失函数的和，样本损失函数计算的是预测值 与真实值 之间的损失值，预测值 依赖于输入特征 、网络结构（函数解析式）、以及网络参数 。
于是，深度学习模型训练的优化问题具体化为：
当我们执行某一类机器学习任务，采用某一个网络结构时，只需指定 和 的表达式即可。举个例子，当我们做二分类的逻辑回归任务时，
表示内积运算。在逻辑回归中，参数个数与特征个数相同，而在深度神经网络中，参数个数远大于特征个数，模型的表达能力因而大大增强。目前深度学习大部分的研究都集中在模型设计，也就是设计 和 ，其中大部分的工作都致力于研究 ，改进 的工作相对较少。本文暂时不讨论模型设计，我们把精力放在优化算法这个分支上。
1.2 在线学习
在深度学习场景中，样本集往往非常巨大，样本量少则百万级，多则上亿。这样巨大的样本量是无法一次性加载进内存的。更有甚者，样本量是无穷多，例如电商推荐系统，每时每刻都有用户在产生行为，或点击，或加购物车，或下单。只要行为上报不取消，训练样本就会源源不断地涌入到后台存储。对于这些场景，加载全部样本数据做离线学习是明显不合适的。我们只能分批次地加载数据，根据局部样本数据更新模型参数，这就是在线学习。在 Goodfellow et al.的著作[2]中还提到，分批加载数据还涉及到硬件计算的原因（例如GPU运算）和最优化效果的原因（比如正则化效果）。总之，在线学习不仅是深度学习这个应用场景的必然选择，也是任何一个需要处理海量样本数据场景的必然选择。在线学习可分为以下两种情况：
对于样本量巨大却有限的情况，我们将全部样本随机打散后按照固定的大小（我们称为batch size）分成许多批次，最后不足一个batch size的样本也算一批，这样每次输入网络的样本数就降到了batch size这么大，大大缓解了内存压力。我们把所有批次全部输入网络一次记为一个epoch，在样本量有限的情况下，可以多运行几个epoch，确保模型参数数值趋于稳定（收敛），每次开启新一个epoch之前，都可以做一次全部样本随机打散；
对于样本量无穷多的情况，我们只需准备一个大小为batch size的样本收集缓存，缓存满了之后就将收集到的样本输入网络，随即清空缓存，收集下一个批次。样本在输入网络后可直接丢弃，无需重复训练，也就是epoch=1。电商推荐系统中，新数据比旧数据更能反应用户当前的行为状态，将旧数据丢弃有一定的合理性。
落实到数学层面，在线学习情况下的优化问题为：对于第 个批次，
唯一的区别就是把全部样本数 换成批次内样本数 ，可以简单理解为batch size）。在下面的讲解中，我们将目标函数简记为 ，因为现有文献对算法的分析不涉及 的具体形式。（这就意味着我们可以在算法分析中利用 的具体形式，改进现有的分析方法。）此时，全局目标函数
。
2. 随机梯度下降——SGD SGD的参考文献是[3, 第2.1节]。SGD的变量迭代方式： 其中 满足 ， 常被称为学习率，而 在深度学习框架TensorFlow中，我们通过调用优化器API的形式来实现上述SGD算法：
我们发现从 到 是一个加性的更新（additive update），于是我们可以整理出通项公式：
当 时， 的收敛性乍看之下并不明朗。我们将借助文献[3]中的做法来证明收敛性。
2.1 基本假设与判定指标
为了分析收敛性，我们首先给出基本假设和判定指标：
目标函数： 对于任意 ， 都是关于 的convex函数（convex函数也译作凸函数，然而“凸”这个概念易引发歧义，因而此处保留英文术语。），即给定定义域内任意 和 ，对于 都有（convex函数第一定义）
以及（convex函数第二定义）
第一定义和第二定义的说法并不严谨，仅仅是为了方便讲解。实际上第二定义是convex函数的性质，可从第一定义推出。
判定指标：
当 为convex函数时，判定指标选择为统计量 （Regret）：
当 ， 的均摊值 ，我们认为这样的算法是收敛的，即 ，不仅是趋于某个值，而且这个值使目标函数最小。在算法收敛的前提下，我们一般认为：
1. 随着 增长得越慢，算法收敛越快；
2. 增长速率相同时，学习率衰减越慢，算法收敛越快。
变量有界假设：
或者对于变量的任意一维
梯度有界假设：
或者对于变量的任意一维
2.2 收敛性证明
在一般情况下，我们很难精确计算出 ；大家普遍的做法是求取 的一个上界，然后利用上界值除以 在极限情况下是否趋于 来判定收敛性。
2.2.1 从统计量
已知 ，那么
由于 是convex函数，有
亦即
代入 ：
这个结论通用性很强，适用范围不仅限于SGD。
2.2.2 建立联系：从 迭代式到
从 的迭代式开始做数学变形：
这一系列的数学变形是为了分离出 ，与 的上界相呼应。接着我们进行整理：
从这里可以看出， 的上界由两个部分组成。
2.2.3 对 的上界做放缩
我们将利用（i）2.1节中基本假设和（ii）数学不等式来做放缩。首先我们看（2）式，根据梯度有界假设
我们保留 以便后续设计最优学习率。接着我们看（1）式，我们将用到一个错位重组求和的技巧：
这个技巧只涉及将求和号内的各项展开及合并，合并的依据是将标红的部分每相邻两项套个括号。整理成上面的形式后，我们开始放缩：
• 根据变量有界假设： ；
• 由于 单调不增， ；变量有界假设： ，
• 数学不等式：
所以（1）式最终的放缩结果为
最后我们整理出 的上界
2.2.4 设计最优学习率
令 是关于 的函数： ，且采用多项式衰减： ，
于是 。当 时， 取得最优上界 ， 相应的学习率为 ， 均摊值 在 时趋于 。
2.2.5 几点补充说明
• 当 时， 取得最优上界 。
• 当 时， ， ， ，故而无法证明算法收敛性，但是这并不意味着算法发散。
• 样本总量有限时如何实现 ？从全局目标函数的拆分方式来看：样本总数 ，由于 ，那么 ；当样本总量有限时，我们通过增加epoch数的方式，可以达到复制样本的效果（运行多少个epoch，样本复制至原来的多少倍），当 ，batch size为有限值时， 成立。
整个证明过程可以总结为以下几个步骤：
• 当任意 都是convex函数时， ；
• 从 的迭代式中分离出 ；
[1] S. Ruder, “An overview of gradient descent optimization algorithms,” arXiv preprint arXiv:1609.04747, 2016.
[2] I. Goodfellow, Y. Bengio, A. Courville, and Y. Bengio, Deep learning. MIT press Cambridge, 2016, vol. 1, no. 2.
[3] 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.
02
这是我“科研喂饭”系列的第二篇文章，希望它能为正在从事算法研发以及对算法研发感兴趣的小伙伴带来帮助。我写这个专栏的目的是希望能尽力降低科研的门槛，让大家更好地享受科研的乐趣。 文章中会涉及到论文的细节，以数学推导过程为主。限于篇幅以及讲解的便利性，我将会对原文作出调整和删减。如果大家在阅读本文时感到困惑，可以进一步参阅文献，看一看原作者的讲解。 由于本文篇幅较长，大家可以根据实际情况挑选自己感兴趣的部分来读： 我只想看算法和收敛性证明部分：直接从第2章开始，遇到不明含义的数学符号参考前文 我只想看科研创新的部分(我想从事深度学习算法开发)：直接从第4章开始，遇到不明含义的数学符号参考前文 1. 引言 在上一篇文章里我们详细介绍了最朴素的SGD算法及其收敛性证明（深度学习算法收敛性证明之SGD），在这里我们做一个简单的回顾：SGD的变量迭代式非常简单 其中 是学习率， 是 时刻目标函数 在 处的梯度。SGD收敛性证明须基于一系列的前提假设，根据参考文献 [1, 第2.1节] ，前提假设如下： 若当 ， 的均摊值 ，我们认为这样的算法是收敛的，并且一般认为 随着 增长得越慢，算法收敛越快。上面提到的前提假设与判定收敛指标将在Adagrad算法的收敛性证明中继续沿用。 2. 自适应梯度算法——Adagrad Adagrad的参考文献有不少，有[2]和[3，第3节]等。本文中的证明步骤主要参照 [3，第3节]。Adagrad的变量迭代式： 其中 ，与SGD相同； 为两个向量在对应位置做乘积（哈达玛积）； 从标量变成了向量： 这里的分子 是标量，分母 是向量。向量的数值运算（加减乘除、乘方开方、指数对数）是指对向量的各个元素做数值运算。标量除以向量的运算是指让标量除以向量的各个元素，最终输出向量的运算。在深度学习框架TensorFlow中，我们通过调用优化器API的形式来实现Adagrad算法： Agadrad与SGD的主要区别在于学习率：SGD的学习率是个标量，一般采用多项式衰减，对梯度的每一维衰减程度都一样，缺乏个性化设计；而Adagrad的学习率是个向量，衰减程度与历史梯度的累积平方和有关，对梯度的每一维的衰减程度都不同，实现了自适应。 基本假设与判定指标与SGD完全一致，不做赘述，我们直接进入证明环节。由于基本假设与判定指标没变，我们可以复用SGD证明中的一些结论（【科研喂饭】深度学习算法收敛性证明之SGD） 我们将 的变量迭代式按照维度做拆分：对任意第 维，都有 这样一来，迭代形式就与SGD一致了（仅仅是向量与标量的区别，或者说是字体加粗与否的区别）。分离出 的做法可以依样画葫芦： 没看懂这些技巧的同学可以参考我那篇证明SGD收敛性的文章。接着我们做个小小的整理， 对不等号右边的式子，我们将对中括号内的部分分别放缩。 关于（2），（2）式的处理相对复杂一些，主要运用数学变形，此处为证明的难点： 最后一个不等号用了放缩（1）式的结论。（2）式最终的放缩结果为 在工程实践中，学习率 是个常数，但是在这里，为了更好地压低 的上界，我们令 与维度 有关，即 ， 根据基本不等式，当 ， 时，上界取到最小值 ，即 ，与SGD的上界同阶。 3. 总结 Adagrad与SGD的迭代步骤很相似，区别仅体现在 或者 上 SGD： ，学习率仅与迭代次数有关，对变量的每一维一视同仁。 Adagrad： ，学习率仅与历次迭代的梯度有关，对变量的每一维可自适应调整。 Adagrad与SGD证明算法收敛的步骤重合度很高，几乎都可以复用。 Adagrad与SGD的 上限值同阶，那么理论上Adagrad与SGD收敛速率相同，但在工程实践中并不是这样。 局限性：计算历史梯度的累积平方和（ ），迭代步数越多，其数值会越大，导致数值计算不稳定（出现正无穷）； 的数值也会越来越小，新样本对模型参数的影响越来越弱，对推荐系统来说实时性越来越差。 4. 科研小创新：Adagrad新样本提权 因为要对新样本提权， 需满足单调不减，即 我们接下来证明使用调整后 的Adagrad的收敛性。 当 ， ，比 更高阶，但是均摊值 在极限情况下依然趋近于0 我们简单评价下这种做法，虽然提权操作的确能够带来新样本权重增加，学习率衰减变慢等好处，然而 上限值的数量级也被提高了，并且 的数值计算依然不稳定，在局部仍可能出现正无穷。 5. 参考文献 [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] J. Duchi, E. Hazan, and Y. Singer, “Adaptive subgradient methods for online learning and stochastic optimization.” Journal of machine learning research, vol. 12, no. 7, 2011. [3] M. Streeter and H. B. McMahan, “Less regret via online conditioning,” arXiv preprint arXiv:1002.4862, 2010.
03
这是我“科研喂饭”系列的第三篇文章，希望它能为正在从事算法研发以及对算法研发感兴趣的小伙伴带来帮助。我写这个专栏的目的是希望能尽力降低科研的门槛，让大家更好地享受科研的乐趣。 文章中会涉及到论文的细节，以数学推导过程为主。限于篇幅以及讲解的便利性，我将会对原文作出调整和删减。如果大家在阅读本文时感到困惑，可以进一步参阅文献，看一看原作者的讲解。 由于本文篇幅较长，大家可以根据实际情况挑选自己感兴趣的部分来读： 我只想看算法和收敛性证明部分：直接从第2章开始，遇到不明含义的数学符号参考前文 我只想看拓展的部分（Amsgrad）：直接从第4章开始，遇到不明含义的数学符号参考前文 1. 引言 在上两节文章里我们详细介绍了最朴素的SGD算法和Adagrad算法的收敛性证明，我们做一个简单的回顾： 其中 是学习率， 是 时刻目标函数 在 处的梯度。 其中 ，与SGD相同； 为两个向量在对应位置做乘积（哈达玛积）； 从标量变成了向量： 向量的数值运算（加减乘除、乘方开方、指数对数）是指对向量的各个元素做数值运算。标量除以向量的运算是指让标量除以向量的各个元素，最终输出向量的运算。 它们的收敛性证明基于以下前提假设（来自参考文献[1, 第2.1节]）： 若当 ， 的均摊值 ，我们认为这样的算法是收敛的，并且一般认为 随着 增长得越慢，算法收敛越快。这些的前提假设与判定收敛指标将在Adam算法的收敛性证明中继续沿用。 2 Adam算法 Adam算法的参考文献是[2]。本文中的证明步骤将参考[2]，然而由于其Lemma 10.3和Lemma 10.4存在错误，因此本文将作出调整和删改。Adam的变量迭代式比SGD和Adagrad更复杂些：（ 、 初始化为 ， 随机初始化） 其中 。在深度学习框架TensorFlow中，我们通过调用优化器API的形式来实现Adam算法： 我们可以根据 和 的迭代式算出它们的闭式解，我们以 为例： Adam 改进了Adagrad的分母，具体表现为： • Adagrad：所有的梯度分配相同的权重，新梯度的影响力越来越弱；分母的数值越来越大，数值计算不稳定，引发数值溢出； • Adam：旧梯度分配的权重越来越小，例如 的权重 随 的增大呈指数衰减；分母的数值始终可控，如果对任意 ， ，那么 基本假设与判定指标与SGD、Adagrad完全一致，不做赘述，我们直接进入证明环节。由于基本假设与判定指标没变，我们可以复用SGD、Adagrad证明中的一些结论。 在Adagrad证明中（大厂推荐算法：【科研喂饭】深度学习算法收敛性证明之Adagrad），我们将 的上界具体拆分到每一维变量上，以双重求和的形式呈现 仿照Adagrad证明，我们需要分离出 。首先从Adam的迭代表达式出发：对于变量的任意一维 根据文献[2]，当 取值为常数时算法收敛性难以证明，于是我们令 ，即让 随迭代次数的增加而变化，且 单调不增，即 ，也就是说动量将逐渐消失，最终 将趋近于 。此时 变成了 从 到 依然是加性的更新。由于形式较为复杂，我们考虑换元，令 接下来我们将对（1）、（2）、（3）三项分别放缩。 在Adam算法中，对 上界的放缩即对上述（1）、（2）、（3）三项的放缩。 我们重点看第三项 ，这一项的放缩时常为人诟病，因为它是有条件的，当 对任意 恒成立时： 其中用到了变量有界假设。需要注意的是，Adam算法不能使 对任意 恒成立，于是有人提出Amsgrad[3]，补上了这一漏洞。最后还剩下些扫尾的工作，因为 ， ，于是（1）放缩到 接下来我们关注 以便进一步放缩，前面我们有提到 ，我们借此机会来探索 和 的有界性：运用梯度有界假设 其中（a）处因为 。此时我们运用梯度有界假设， 对任意 都有 在整理出 的上界之前，我们做个小小的总结：对于（1），当 对任意 恒成立时， 至此， 上界的数量级仅与 、 、 有关。根据SGD中的结论，如果 ， ， ；当 时，取到最优上界 ，这意味着 的最优上界不会低于 。如果我们希望 衰减尽可能慢（动量项衰减尽可能慢），可使 3. 总结 • 当目标函数 对任意 均为convex函数时，SGD、Adagrad、Adam的 上界最优数量级均为 ，算法均收敛。 • 从理论上来看，三者的收敛速率相同；在工程实际中，Adam的收敛速率一般最快。 • 在工程实践中， 为convex函数的情形十分少见，以推荐系统的场景为例，仅有逻辑回归符合要求。 • 在现有证明框架下，Adam算法的动量项必须衰减，并且至少以平方根的速率衰减；然而在工程实践中，动量项的超参数 一般设置为常数，不影响算法的实际收敛性。若要证明 时Adam算法依旧收敛，可考虑修改算法的前提假设、评价指标、证明框架等。 对分离后的结果分部分放缩，常用手段有：（i）变量、梯度有界假设，（ii）错位重组求和，（iii）数学不等式：级数求和、柯西不等式； 4 Adam拓展：Amsgrad 为克服Adam算法收敛性证明中的缺陷，Reddi et al. [3]提出Amsgrad，旨在对Adam做的改进：从 改进为 TensorFlow 2.0版本的Adam优化器可以很方便地实现Amsgrad： 参数amsgrad的默认值为False，amsgrad=False对应Adam算法。文献[3]中Amsgrad未做均值校正，为了最大限度复用Adam的证明，我们补充均值校正的操作。均值校正操作不影响算法收敛性。 Amsgrad收敛性证明以复用Adam证明为主，仍然成立的核心结论有： 我们依然是对（1）、（2）、（3）三项分别放缩，由于（2）不涉及 ，结论可以全部复用，我们只需关注（1）和（3）。关于（1），我们可以复用 展开前的所有结论：当 对任意 恒成立时， 我们接下来验证 对任意 恒成立。 ， 在单调不增的情况下： ，即 ，因此 对任意 恒成立。我们还需要重新审视 和 的有界性： 于是 和 的有界性与Adam中一致，因此第一项的结论可以直接复用。 即 依然成立，因此第三项的结论也可以直接复用，Amsgrad收敛性证毕。 最后我们简单评价一下Amsgrad：Amsgrad改进了 ，给Adam算法从收敛性证明的角度打了补丁；但在工程实践中，Amsgrad的性能未必会比Adam更胜一筹，时至今日，Adam依然是使用最广泛的优化器。 5. 参考文献 [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] D. P. Kingma and J. Ba, "Adam: A method for stochastic optimization," arXiv preprint arXiv:1412.6980, 2014. [3] S. J. Reddi, S. Kale, and S. Kumar, "On the convergence of adam and beyond," arXiv preprint arXiv:1904.09237, 2019. 本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。
“强基固本”历史文章
分享、点赞、在看，给个三连击呗！