为何我们需要动量

我们经常把梯度下降中的动量方法看作是一种去除振荡和加速迭代的好方法，但是它有时也会表演一些其他有趣的行为。它在允许更大的学习速率的同时也带来了自己的振荡行为。这是什么原因呢。

这张图看起来是可互动的，实际上它确实是可以互动的，只不过不是在这篇笔记里。因为这篇笔记中的大部分内容是对https://distill.pub/2017/momentum/的翻译，如果你很爱读英文的话，希望你直接去阅读原作者的文章，原文默认大家都有一个更高的数学水平，但是也挖掘地更加透彻，也有一些中文难以表达的幽默，同时还有极其炫酷的可交互图表，阅读原文也是对原作者的支持哦。

这篇笔记的特点是为各位线性代数不是很好的同志们铺平了道路，而且最重要的是这是中文文章。 话不多说，让我们开始吧。

有一个关于动量的形象比喻是这样的：梯度下降就是一个人走下山坡。他总是沿着最陡的路径下山，虽然他走的很慢，但是很稳。动量方法就是一个大滚石滚下同样的山坡。这给了它一些惯性的特点，包括轨迹更连贯更快，有抵抗振荡的能力，还可以使我们冲过比较窄的峡谷，小坑和局部最优点。

这个标准的故事不能说他错，但它实际上并不能解释很多动量方法的独特行为。实际上，只要我们用正确的模型研究动量，我们就可以更加准确地了解动量概念。

一个很好的模型就是凸二次型。这个模型足够复杂，可以重现动量在实际问题中的各种局部动态行为；但是也足够简单，可以让我们深入彻底地分析它。这样的平衡给了我们足够的动力去把它作为标准模型来了解算法。

什么是凸二次型？$z=a_1{y}^2+a_{2}xy+a_3{x}^2$ 就是一个，写成矩阵形式就是$$\begin{gathered} z=\left[\begin{array}{c}xy\end{array}\right]\left[\begin{array}{cc}{a}_1& a_2/2\\ & \\ a_2/2& a_3\end{array}\right]\left[\begin{array}{c}x \\ y\end{array}\right] \end{gathered}$$，这是二元的，扩展到n元就是$z=X^{T}AX$

我们先从梯度下降开始吧。这个算法有着诸多优点，可惜速度并不是其中之一。它的公式是这样的：当优化一个平滑的函数f，我们就在梯度上迈出一小步：

$$w^{k+1}=w^k-\alpha \nabla f(w^k)$$

如果这一步足够小，那么梯度下降每次的移动都是单调下降的。它一定可以收敛，尽管一般都是在局部最小值。不过只要有几个很弱的条件，它甚至可以以指数级的速度抵达最低点（后面会解释）。但是这种指数级下降的情况，尽管在理论上非常可能发生，但是事实上它即使发生了，一般也是非常的微弱。在梯度下降一开始时，你会觉得一切都很好——几乎可以立即在损失函数上看到显著的下降。但是随着梯度下降的进行，那条Loss曲线的速度就开始变慢了。你这时会开始觉得你的迭代算法的进度似乎不如一开始那样理想，你会好奇，到底是哪出了问题？

答案可能是你遇上优化算法的死对头——病态曲率了。病态曲率指的就是$f$上尺寸大小非常不合理的地方。这样的地形常常被描述为峡谷，山沟沟之类的。这时你的迭代算法就会在峡谷两侧之间反复横跳，或者以一种非常害羞的速度缓慢地前往最小点，导致在某个方向上的移动基本就停滞了。这可为难了梯度下降。下图就是一个病态曲率山谷。

动量方法就是在原有梯度下降的基础上做了一点修改，使之具有了短期的记忆能力：

$$\begin{gathered} z^{k+1}=\beta z^k+\nabla f(w^k) \\ {w}^{k+1}=w^k-\alpha z^{k+1} \end{gathered}$$

这个修改的好处就在于它基本没修改什么。如果$\beta =0$那么这还是我们的梯度下降。但是如果我们把$\beta =0.99$（在一些极端情况下可以$\beta =0.999$），那这样的动量方法就可以产生我们想要的加速效果。我们的算法就可以克服病态曲率的问题继续愉快的梯度下降了。

这个新的算法第一眼看过去就是一个简单的小伎俩，通过抵消梯度下降的异常行为来平滑轨迹还有减少振荡现象。但是事实恰恰相反。梯度下降才是动量方法中的小伎俩。首先，动量方法抛弃了在很多函数中的二次型加速的优势。这可不是什么小事，这就像你抛弃了快速傅立叶变换，快速排序中的速度优势一样。

Nesterov曾礼貌地指出，动量方法，从狭隘的技术化的角度来看，简直完美。“Nesterov, states that momentum is, in a certain very narrow and technical sense, optimal”。实际上，它满足了很多有趣又美丽的数学性质，让那些有数学强迫症的人身心舒畅。这点我们以后再说。我现在想说的是——动量是一个教科书级的算法。

第一步 梯度下降

我们先让我们的优化函数是一个凸二次型：

$$f(w)=\frac{1}{2}{w}^{T}Aw-b^{T}w,w\in {\mathbb{R}}^n$$

假设 A 是对称且可逆的，那么我们可以直接解出最优的$w^{\ast }$：

$$w^{\ast }=A^{-1}b（解的过程略，实际上就是令梯度为零）$$

尽管这个模型如此简单，它的复杂程度足够你拟合很多的函数了（想象A就是你最爱的模型——Heissian矩阵，费歇尔信息矩阵等的，如果你不知道这些是啥没有任何关系）。它也能包含所有病态曲率的关键特征。当然最重要的是你可以以此写出梯度下降的封闭形式：

因为$\nabla f(w)=Aw-b$，迭代式子可以写成：

$$w^{k+1}=w^k-\alpha (A{w}^k-b)$$

这里有一个重要的技巧：我们可以在一种非常自然的坐标体系下观察梯度下降，使得梯度下降里的每个参数的迭代都只和自己的值有关，和其他参数无关（由于矩阵乘法$A{w}^k$的存在，在此之前任何一个参数$w$的更新都和其他所有参数值有关，只有$A$是对角阵时才能使每个参数独立完成梯度下降）。只要利用$A$的特征值就可以了。

每一个对称阵$A$都可以相似对角化：

$$\begin{gathered} A=Qdiag({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n)Q^{-1},Q=[q_1,q_2,\cdots ,q_n] \\ and{Q}^{-1}=Q^T \end{gathered}$$

（由于矩阵乘法代表了一个向量在另一组基底下的表示，那么形如A=QBQ^{-1}的含义就是，存在一组基底 $q_1,q_2,\cdots ,q_n$，使得A在这组基底下也可以用B来表示。故相似对角化的含义存在某个坐标系，按照这个坐标系看待A，A就是对角阵）

如图所示，可以通过矩阵变换将本来互相牵连的$w$的变化（斜着移动），变成上下左右无关的变化，图中等高线密集的方向代表了特征值较大。

并且为了方便起见，我们假设${\lambda }_{\mathrm{1...}n}$是从小到大排序的。我们对现有的$w^k$和最佳的$w^{\ast }$之间的差做一个基底的变换，$x^k=Q^T(w^k-w^{\ast })$，优化目标现在就变成使$x^k\to 0$了。那我们就可以把迭代过程拆成n个独立的进程：

$$\begin{array}{rl}由于A& =QE{Q}^T\\ & \\ w^{k+1}& =w^k-\alpha (A{w}^k-b)\\ & \\ w^{k+1}& =w^k-\alpha ((QE{Q}^T)w^k-(QE{Q}^T)A^{-1}b)两边左乘Q^T\\ & \\ Q^T{w}^{k+1}& =Q^T{w}^k-\alpha E{Q}^T(w^k-w^{\ast })\\ & \end{array}$$

对于其中每一个参数：

$$x_i^{k+1}=x_i^k-\alpha {\lambda }_i{x}_i^k=(1-\alpha {\lambda }_i)x_i^k=(1-\alpha \lambda i{)}^{k+1}{x}_i^0$$

转移回到原来的空间下，我们有：

$$w^k-w^{\ast }=Q{x}^k=\sum _i^n{x}_i^0(1-\alpha {\lambda }_i{)}^k{q}_i$$

这就是封闭形式下的梯度下降。

拆分误差

上述公式给出了一个简单而深刻的道理：在凸二次型的优化中，每个初始参数差值$x_i^0$都对应了在$Q$基底下的一个误差项。这样的误差项有$n$个，并且每个误差都沿着自己的单独的优化路径前往最小值，按照等比数列的指数级下降速度收敛。每一次迭代每一个误差项都会缩小到原来的$(1-\alpha {\lambda }_i)$倍。这个项越接近1，收敛的越慢。

（P.S. 我翻译这篇文章的原因正是我非常喜欢它的思考方式——用足够简单又典型的例子结合封闭形式的公式，得到精准又直观的结论。我认为对于培养直觉非常有好处。）

对于大多数的步长来说，有着最大特征特征值的特征向量对应着最快的收敛速度。正是这个原因导致了梯度下降在前几步会产生很明显的损失减小，等待大的特征值对应的损失被消灭了以后，小特征值的缓慢下降开始浮出水面成为主流，这时我们就开始抱怨梯度下降进展缓慢了。

如果写出每个参数对应的特征子空间对于损失的贡献：

$$f(w^k)-f(w^{\ast })=\sum (1-\alpha {\lambda }_i{)}^{2k}{\lambda }_i[x_i^0{]}^2$$

我们就可以可视化每个误差项在Loss中的占比。（想要体验交互图表前往原网页）

选一个步长吧

上面的分析给了我们关于如何选择步长$\alpha$最为直接的指导。为了收敛，每个$|1-\alpha {\lambda }_i|$必须严格小于1。因此所有的可以收敛的步长，都落在这个区域内：

$$0<\alpha {\lambda }_i<2$$

这个整体的收敛速率是由最慢收敛的那一项误差项决定的，也就是必须是${\lambda }_1$或者${\lambda }_n$（还记得$\lambda$是排序好了的吗）。

$$rate(\alpha )=\underset{i}{\max }|1-\alpha {\lambda }_i|=\max \{|1-\alpha {\lambda }_1|,|1-\alpha {\lambda }_n|\}$$

整体的收敛速率当${\lambda }_1$和${\lambda }_n$贡献的收敛速率一样的时候达到最小——这和我们的认为最快最慢特征向量收敛速度都相等时，整体速度最快的直觉相符合。如果你愿意计算，你会得到：

$$\begin{gathered} optimal\alpha =\arg \underset{\alpha }{\min }rate(\alpha )=\frac{2}{{\lambda }_1+{\lambda }_n} \\ optimalrate(\alpha )=\underset{\alpha }{\min }rate(\alpha )=\frac{{\lambda }_n/{\lambda }_1-1}{{\lambda }_n/\lambda 1+1} \end{gathered}$$

注意，这个比例${\lambda }_n/{\lambda }_1$决定了问题的收敛速度。事实上，这个比例出镜的次数实在是太高了，以至于我们需要给他一个名字和一个符号。

$$conditionnumber(条件数):=\kappa :=\frac{{\lambda }_n}{{\lambda }_1}$$

条件数有很多含义。它可以衡量一个矩阵和奇异矩阵的接近程度。它可以衡量$A^{-1}b$对于$b$的扰动的鲁棒性有多强。同时条件数是在优化问题的数值运算中非常重要的概念，通常来说，条件数越高，这个问题的数值稳定性越差，越难以优化。比如如果损失函数的条件数很高，那么大概率你会看见病态曲率（由于特征值相差太多构成的大峡谷）。

例子：多项式回归

上面的分析解释了一个道理：误差项和误差项之间是不平等的。实际上，一个问题中存在多种误差，嗯，严格来说是$n$种，$A$的每个特征向量对应一种。我们还知道梯度下降会更擅长修正某些误差，而另一些就没那么擅长。但是$A$的每个特征向量又有什么含义呢？令人惊讶的是，在很多的应用中它们的含义非常的具体。

让我们看看我们刚学到的知识在多项式回归里是怎么作用的吧。给定1维数据${\xi }_i$，我们的目标是构建模型来拟合训练集数据$d_i$：

$$model(\xi )=w_1{p}_1(\xi )+w_2{p}_2(\xi )+\cdots +w_n{p}_n(\xi ),p_n(x)=x^{n-1}$$

虽然这个模型相对于输入$\xi$是非线性的，但是相对于权重来说是线性的。因此我们可以把模型写成单项式的线性组合：

因为这种线性性质，我们可以用线形回归描述我们的模型在数据${\xi }_i$上的误差：

$$minimiz{e}_w\frac{1}{2}\sum _i(model({\xi }_i)-d_i{)}^2=\frac{1}{2}||Zw-d|{|}^2$$

其中

$$Z=\left[\begin{array}{ccccc}1& {\xi }_1& {\xi }_1^2& \cdots & {\xi }_1^{n-1}\\ & & & & \\ 1& {\xi }_2& {\xi }_2^2& \cdots & {\xi }_2^{n-1}\\ & & & & \\ ⋮& ⋮& ⋮& ⋮& ⋮\\ & & & & \\ 1& {\xi }_m& {\xi }_m^2& \cdots & {\xi }_m^{n-1}\\ & & & & \end{array}\right]$$

注意，这个问题中的$A$不是$Z$，而是$Z^{T}Z$了。我们现在知道了，我们需要通过在$Q$的基底下观察迭代过程就能看到每个参数独自的收敛路径。因此现在让我们把我们的回归问题放到$Q$基底下吧。首先，我们要修改基底，把$w$旋转为$x=Qw$，同样的也要把特征映射函数$p$旋转到特征空间中$\bar{p}$.我们现在就可以把原有的回归问题转化到另一个不一样的多项式基底下了，如果你愿意算算你会发现，模型变成这样：

$$model(\xi )=x_1{\bar{p}}_1(\xi )+\cdots +x_n{\bar{p}}_n(\xi ),{\bar{p}}_i=\sum q_{ij}{p}_j$$

虽然形式不一样，但是这个模型和原有的模型是同一个模型。在这个模型下任意一个项$x_i{\bar{p}}_i(\xi )$的对于整体损失函数的贡献都只由$x_i{\bar{p}}_i(\xi )$这一项本身决定，也就是只需要考虑$x_i$和${\bar{p}}_i(\xi )$这两项的值就可以求出最优的$x_i$。

这些新的特征$\bar{p}$和它们的权重就有了一个可以独立变换而不影响其他特征的优良性质了。现在我们在改变某一个权重$x$时再也不必担心要顺带改变其他值，我们的优化问题被拆解为了n个小的一维优化问题。我们可以放肆的按照任何顺序修改$x_i$的权重，最终得到一个全局的最优值。

这里一共有六个特征值，这批数据里的点聚在两簇。前两幅图反映了前两个特征值，它们涵盖了这两个点簇的位置差距。

接下来的特征值描述了点簇内部的变化和朝向

最后两个特征值对应锯齿状的函数，在相邻的顶点上有着巨大的变化（损失值在该方向上变化率大说明该方向可能有着更大的特征值）

上面那个图表里的观察证据都可以通过数学的方法证明。从统计的角度来看，我们喜欢的模型应该是对噪音鲁棒的。如果很小的扰动就剧烈地改变整个模型，那这个模型大概率没什么意义。这些代表着特征值的特征，是整个数据的黄金部分，正好赋予了我们把特征按照对扰动敏感程度排序的能力。这种分解特征的能力正是$A$的特征值赋予我们的——当我们按照特征值拆分出互不相干的误差项，最为鲁棒的部分排在最前面（有着最大的特征值），最敏感的特征值就排在最后面（有着最小的特征值）。

这种描述鲁棒性的方法，同时也是一个描述一个特征空间收敛快慢的方法。因此，病态曲率中病态的方向对应的误差项，也正是特征空间中收敛的最慢（这需要$\alpha$大小合适，毕竟收敛速率是$|1-\alpha {\lambda }_i|$）的那一项——也正是对噪音最敏感的项！

那么让我们把这个多项式回归的参数初值都设为0，然后跟踪迭代过程直到达到非常过拟合的程度，让我们看看这些性质如何体现在梯度下降里吧。

十分推荐你自己到网站当中操作一下可交互图表感受变化。一开始，中等大小的特征值对应的误差项最先收敛。

最为鲁棒的特征完成收敛以后，就是更加细节的，$\lambda$更大的误差项的收敛过程成为主流。

最后是最为敏感的误差项收敛也完成了，算法达到了过拟合。各种各样的防止过拟合的算法都是围绕消灭最底下的最大特征值展开的（早停：不给大特征值收敛的机会/减小算法复杂度：直接在A里砍掉多余的特征空间维度/正则化：构建一个要求所有特征子空间尽可能收缩的附加任务来抵抗误差项参数靠近最佳参数值的趋势）

Early stopping这种方法就很好的利用了这个特点：通过早点停止优化，你一般会得到泛化能力更强的结果。实际上，早停的效果和我们更加常见的正则化方法是相似的（比如L2正则），都是通过直接抑制最小特征值（我觉得这里应该是最大，可能是我理解有误）的误差项来阻止过拟合。但是早停有一个非常直接的好处。一旦选定了迭代的步长，就没有放进正则参数的地方了。但是在单独的一次优化的过程中，我们有从欠拟合到过拟合的整整一族的模型可供选择。这简直是天上掉馅饼，早停似乎只有好处而没有坏处。

动量方法

让我们把注意力转回动量。回忆我们的动量更新公式：

$$\begin{gathered} v^{k+1}=\beta v^k+\nabla f(w^k) \\ {w}^{k+1}=w^k-\alpha z^{k+1} \end{gathered}$$

因为$\nabla f(w^k)=A{w}^k-b$，更新公式也可以写成：

$$\begin{gathered} v^{k+1}=\beta v^k+A{w}^k-b \\ {w}^{k+1}=w^k-\alpha z^{k+1} \end{gathered}$$

和我们处理梯度下降的方法如出一辙，我们改变基底$x^k=Q(w^k-w^{\ast })$，并且$y^k=Q{z}^k$，我们得到更新公式：

$$\begin{gathered} y_i^{k+1}=\beta y_i^k+{\lambda }_i{x}_i^k \\ {x}_i^{k+1}=x_i^k-\alpha y_i^{k+1} \end{gathered}$$

同样的，在这样的基底下，每个误差项的优化都是独立于其他误差项的（不过$x_i^k$和$y_i^k$是成对互相影响的）。这就允许我们把更新公式重写为：

$$\left(\begin{array}{c}{y}_i^k\\ \\ x_i^k\end{array}\right)=R^k\left(\begin{array}{c}{y}_i^0\\ \\ x_i^0\end{array}\right),其中R=\left(\begin{array}{cc}\beta & {\lambda }_i\\ & \\ -\alpha \beta & 1-\alpha {\lambda }_i\end{array}\right)$$

想办法将$R$取$k$次方以后（计算这个可能有一些难度，原文给出了比较好的方法可以参考，这里就不描述了），如果${\sigma }_1,{\sigma }_2$是$R$的特征值：

$$R^k=\{\begin{array}{rlr}{\sigma }_1^k{R}_1-{\sigma }_2^k{R}_2& ,& {\sigma }_1\ne {\sigma }_2\\ & & \\ {\sigma }_1^k(kR/{\sigma }_1-(k-1)I)& ,& {\sigma }_1={\sigma }_2\end{array},R_j=\frac{R-{\sigma }_{j}I}{{\sigma }_1-{\sigma }_2}$$

这个公式虽然很复杂，但是最重要的是现在$R$扮演了和梯度下降中$1-\alpha \lambda$一样的收敛速度的角色。但是相比于一个几何的序列，现在我们的下降序列中一个下标对应两个元素，这对应了实部和虚部。而这时我们的收敛率也相应的就是两个速率中最慢的那个$\max \{|{\sigma }_1|,|{\sigma }_2|\}$（因为$R^k={\sigma }_1^k{R}_1-{\sigma }_2^k{R}_2$，$R^k\to 0$依赖于${\sigma }_1^k,{\sigma }_2^k\to 0$）。通过把这个收敛率画出来，我们可以在参数空间中划分出很多不同的收敛行为区域出来。

涟漪：R的特征值在此时是复数，同时迭代时，$f(k)=R^k$呈现一个低频的涟漪状波动。令人惊讶的是，收敛率$2\sqrt{\beta }$这时和$\alpha$与${\lambda }_i$都无关。

单调下降：R的特征值都是实数，同时模长也都小于1。这时的行为很像梯度下降。

一步收敛。当$\alpha =1/{\lambda }_i$并且$\beta =0$，我们可以只需要一步就收敛。这是一个非常特殊的点，可以彻底消除特征空间内的所有误差。

单调振荡：当$\alpha >1/{\lambda }_i$，这时迭代的$f(k)=R^k$在正负之来回切换。这一般就是梯度下降中说的“振荡”。（注意，原本当$\alpha >1/{\lambda }_i$时梯度下降应该发散，这时$R^k$符号不断变化表明在相邻的迭代步之间$x_i^k$近似关于原点对称，并且不断靠近原点。这应该是动量法可以支持更大的学习速率最直观的解释——动量将原先会关于最优点振荡发散的$x_i^k$通过添加惯性变为了振荡收敛。）

发散：当$\max \{|{\sigma }_1|,|{\sigma }_2|\}>1$时，迭代发散。

那么怎样的$\alpha$和$\beta$才能收敛呢？既然我们需要${\sigma }_1,{\sigma }_2$都收敛，我们的的收敛条件就是$\max \{|{\sigma }_1|,|{\sigma }_2|\}<1$，可行的$\alpha$算出来应该是：

$$0<\alpha {\lambda }_i<2+2\beta for0\le \beta <1$$

令$\beta =0$我们就得到了梯度下降时的结论。但是注意我们从这个公式得到的大好处——动量允许我们在最大学习速率放大快两倍以后依然可以收敛。

临界阻尼系数

真正的魔法发生于当我们确定下最优的$\alpha$和$\beta$以后。让我们先对$\beta$进行优化。

当$\alpha$很小的时候，动量给出了一个有趣的物理解释：它是一个离散的阻尼谐波振荡器（a discretization of a damped harmonic oscillator）（似乎并不有趣）。考虑一个在离散时间运行中的物理模拟系统（就像游戏里的物理引擎）

$-y_i^k$就是粒子的速度，$x_i^k$就是粒子的偏离平衡点的位置。我们可以把这个公式拆开看看每个项是怎么影响系统的运动的。这里我们绘制了一个粒子的150帧的速度-位置图像。

$\beta$水平轴：当${\lambda }_i=0,\beta =0$时，物体将以恒定的速度运动。当$\beta$变小一些，粒子就会减速，每一帧它都会失去一些原有的动能。

$\lambda$竖直轴：外力使得粒子有回到原点的趋势。结合阻尼和外力场，粒子的运动就类似一个阻尼谐波振荡器。

（虽然你应该明白，但是事实上左下角的圆并不是在说明粒子在做圆周运动，只是说明粒子在做恒定的简谐运动（因为没有阻力））。

这个系统可以被想象为一个重物挂在弹簧上。我们下拉一下重物，松手并观察它的运动。在这个比喻中，平衡态就是位置$x_i^k$

和$y_i^k$都为零的时刻。$\beta$的选择对于回到稳态的速率至关重要。

阻尼不足：$\beta$过大的时候我们就遇到阻尼过小的情况，阻力太小了导致弹簧不断上下震动，一遍又一遍地错过最小值。

完美阻尼：在两个极端之间是最完美的$\beta$，这个最优点发生在R的特征值重复了，并且$\beta =(1-\sqrt{\alpha {\lambda }_i}{)}^2$的时候。

阻尼过大：当$\beta$太小了（比如在梯度下降中$\beta =0$），我们就阻尼过大了。这个粒子此时浸润在粘性极大的液体中，每一瞬间它的动能都只由液体的外力环境决定。

临界值$\beta =(1-\sqrt{\alpha {\lambda }_i}{)}^2$ 给了我们一个大小为$1-\sqrt{\alpha {\lambda }_i}$的收敛速率（当然是在第$i$个特征空间方向上）。这给了我们一个平方根量级的加速！（相对于梯度下降的$1-\alpha {\lambda }_i$）。可惜的是，因为$\alpha$固定了，这个加速只适用于第$i$个特征空间方向上。

最佳参数

为了得到一个全局的收敛速率，我们必须同时优化$\alpha$和$\beta$。这可复杂多了，但是算出来后是这样：

$$\alpha ={\left(\frac{2}{\sqrt{{\lambda }_1}+\sqrt{{\lambda }_n}}\right)}^2,\beta ={\left(\frac{\sqrt{{\lambda }_n}-\sqrt{{\lambda }_1}}{\sqrt{{\lambda }_n}+\sqrt{{\lambda }_1}}\right)}^2$$

把这个代入收敛率公式中，你会得到：

只需要一点点努力，我们就把条件数缩小了一个平方根！当然要完全利用这里的加成，我们得对${\lambda }_1,{\lambda }_2$有提前的了解。但是这个公式还是提供了一个非常简单的指导。如果这个问题的条件数非常差，动量法下的最优$\alpha$就大约是梯度下降的两倍大小，并且动量项系数应该趋近1。因此你就把$\beta$仅可能设置地靠近1，然后选一个最大的可以收敛的$\alpha$吧！正好压着发散的边界线，这一般是个好地方。

在你和这张图互动的时候（要互动去原网站），你会发现：梯度下降的Loss曲线有着优雅连续下降的曲线，而动量的优化过程就伴随着清晰的振荡。这个振荡的涟漪不局限于二次型，实践中几乎出现于所有的函数里。它们不是一种警告，只是提醒你这里还有这调参的空间呢。(接下来有一个动量法的应用例子，因为需要配合可交互图像才能很好的理解，因此就不翻译了。)

下降方法的局限性

让我们退一步看。我们现在使用了一个聪明的技巧，将梯度下降的速度提升了平方倍，而这一切的代价只是一个简单的辅助序列。那么我们很自然地会想——这就是我们的极限了吗？我们有没有可能再多引入几个序列进一步提高收敛速度？有没有人可以发明适应性和智能的方法选择最优的$\alpha$和$\beta$？试想一下把速率提升到三次根号甚至更多是多么诱人的一件事！

不幸的是，尽管各种对于动量算法的改进算法确实存在，但是，它们的收敛时间都磕在了一个明确，坚硬的，几乎无法逃脱的下确界上。

算法空间里的冒险

想要理解我们所能做的一切的极限，我们需要首先严谨定义我们正在搜索的算法空间。这里有一个可能的定义。就我们的观察，梯度下降和动量方法都是可以”展开“的。事实上，由于：

$$\begin{array}{rl}{w}^1& =w^0-\alpha \nabla f(w^0)\\ & \\ w^2& =w^1-\alpha \nabla f(w^1)\\ & \\ & =w^0-\alpha \nabla f(w^1)-\alpha \nabla f(w^0)\\ & \\ & ⋮\\ & \\ w^{k+1}& =w^0-\alpha \nabla f(w^0)-\cdots -\alpha \nabla f(w^k)\end{array}$$

我们可以把梯度下降写作

$$w^{k+1}=w^0-\alpha \sum _i^k\nabla f(w^i)$$

我们可以对动量方法做同样的操作：

$$w^{k+1}=w^0+\alpha \sum _i^k\frac{(1-{\beta }^{k+1-i})}{1-\beta }\nabla f(w^i)$$

事实上，所有形式的基于一阶导数的算法，包括共轭梯度法、AdaMax、平均梯度法等等，都可以被写成（当然不一定简洁）这个展开形式。因此对于这样一族的算法

$$w^{k+1}=w^0+\alpha \sum _i^k{\gamma }_i^{k}f(w^i)$$

包含了梯度下降，动量以及一切你能想到的优化算法。这也是Nesterov的假设中的一个假设。但是让我们把这个定义更向前推一步，扩展这个族使得允许在不同的方向上有着不同的学习率：

$$w^{k+1}=w^0+\sum _i^k{\Gamma }_i^k\nabla f(w^k),其中{\Gamma }_i^k是一个对角阵$$

这一类的算法涵盖了几乎所有用来训练神经网络的算法，包括Adam和AdaGrad。我们把这类方法叫做”线形一阶方法（Linear First Order Methods）“，接下来我将展示一个使这些所有算法都跌跟头的函数。

抵抗的神谕（原文就是这么写的）

我们让每个$w_i$在优化的时候都互相依赖，这就是一个极度恶心的函数，以至于Nesterov称它的一个变种“世界上最糟糕的函数”。这个函数我们叫做Convex Rosenbrock。

这个函数的最优解是：

$$w_i^{\ast }={\left(\frac{\sqrt{\kappa }-1}{\sqrt{\kappa }+1}\right)}^i$$

这个问题$f^n$的条件数随着$n$趋向于无穷趋向于$\kappa$。接下来让我们看看动量方法在这个函数上的表现吧。

这里我们展示了动量方法在Convex Rosenbrock上的前50次迭代情况（图中$n=25$），所有基于一阶导数的算法在此的表现都是相似的。

右上：这个三角形是我们迭代时的死亡三角洲。在这里的部分参数不会被迭代影响，无论这个参数的用途。（Convex Rosenbrock中由于第二项的原因，下一个参数的更新依赖于上一个参数的值，直到上一个参数稳定之前这个参数都不能被很好地优化） 右下：剩下的逐渐扩张的区域就是我们的迭代能够影响到的“光锥”。在这些区域，设置了最完美参数的动量方法表现的非常好。（一样的，光锥的产生是由于参数之间的相互影响。）

上面的观察对于任意一个基于一阶偏导的优化算法都是成立的。让我们来证明这一点。首先，我们可以观察到每一个参数的梯度都只依赖于它的直接相邻的上一个和下一个参数。

$$\nabla f(x{)}_i=2w_i-w_{i-1}-w_{i+1}+\frac{4}{\kappa -1}{w}_i,i\ne 1$$

因此既然我们的算法从0开始，这保证了每个参数在它的相邻上一个和下一个参数改变之前都是一直为零的。

试着把这种限制看作信息传递中的光速。误差信号至少需要$k$步才能从$w_0$传播到$w_k$。我们可以因此总结出那些还没办法被改变的误差：

$$\begin{array}{rl}||w^k-w^{\ast }|{|}_{\infty }& \ge \underset{i\ge k+1}{\max }\{|w_i^{\ast }|\}\\ & \\ & ={\left(\frac{\sqrt{\kappa }-1}{\sqrt{\kappa }+1}\right)}^{k+1}\\ & \\ & ={\left(\frac{\sqrt{\kappa }-1}{\sqrt{\kappa }+1}\right)}^k||w^0-w^{\ast }|{|}_{\infty }\end{array}$$

无穷范数$||x|{|}_{\infty }=\max \{|x_1|,|x_2|,\cdots ,|x_n|\}$

当$n$变的足够大，$f^n$的条件数趋向于$\kappa$。这时所有优化算法的效率都变的一样了；动量方法能够给出的收敛速率就是一切基于一阶导数的优化算法所能给出的最优速率。我们就得到了这个令人不悦的结论：在这个问题上，我们没法做的更好了。

对于像这样的理论下界，我们不应该单纯从字面意思上理解它，而应该从它所代表的精神上去理解。它可能确实在某种程度上给我们在这类算法上的研究投入带来了一种终结感。但这不是意味着基于一阶导数的优化算法已经走到头了。比如，这个理论下界并没有否定我们通过调整问题本身来减小问题条件数的可能性。如果你知道往哪个方向努力的话，这里还有非常多的提升速度的空间。

随机梯度下降里的动量方法

这里还有最后一个值得强调的点。之前的所有讨论都假设我们使用的是真正的梯度——这在现代机器学习项目中是很难得到的。计算精确的梯度需要遍历所有的数据，这个成本可能大的无法接受。相对应的，像minibatch采样那样，随机地估计一下梯度，经常被用来代替$\nabla f(w)$。我们可以把这个估计写成两个部分：真正的梯度和一个估计的误差，这个误差是无偏的$\mathbb{E}[error(w)]=0$。

$$\nabla f(w)+error(w)$$

这有助于我们把这个估计的梯度想象成是往我们的迭代过程中注入了某种特别的误差。利用我们之间使用的分析方法，我们可以直接处理掉这个额外的项。在一个二次型优化问题上，这个误差项很容易被分进一个单独的项，有：

这个误差项，${ϵ}^k$由于和$w^k$相依赖，是个很难搞定的数字。我们在这把这个误差建模为均值为零的高斯分布噪音。在这个简化过的模型中，优化过程也被我们分为两个单独的组成部分，可确定的误差之和与一个随机的误差，下面是他的可视化。

就我们的观察，优化有两个阶段。在一开始的快速变化阶段，噪音的尺度是小于梯度的尺度的，动量方法取得了很大的进展。在第二个更为随机的阶段，噪音盖过了梯度，这时动量就不那么有效了。

注意这里存在一个我们不喜欢的tradeoff，想要降低某一个部分的误差水平就会使另一个提升。比如，减小步长会减小随机误差，但是也减慢了收敛速率。而和我们的直觉相悖的是，增大动量会导致误差被放大。当然就算有这些不想要的性质，带有动量的随机梯度下降还是在神经网络中展现了一个较理想的表现。就我们的观察，这个快速下降阶段在机器学习中似乎比微调阶段重要的多。并且事实上，最近研究发现噪音其实是一件好事——它扮演了一个隐式的正则项，就像early stopping一样，防止了在微调阶段的过拟合。

Onwards and Downwards

关于优化加速的研究正在优化理论的社区看到一丝复兴的迹象。（以下引用请去原文查看）如果这篇文章里的想法让你感到很兴奋的话，你可能会希望去读一读[13]，这篇文章充分的探索了动量的思想，它把动量看作一个微分方程的离散形式。当然也有其他不那么物理的解释存在。有一些研究给出了把动量看作近似多项式的代数解释。同时一些几何的解释也在出现，把动量和一些更为古老的方法如Ellipsoid 方法相结合。最后，还有一些解释是关于动量和对偶性的联系的，这些解释可能会给我们关于如何加速二阶导方法和Quasi Newton一些启发。但是就像那个盲人摸象的寓言一样，动量似乎是一种比它的部分之和还要大的事物。 希望我们可以尽快迎来所有的观点都融合成一个满意的模型的那一天吧。

参考资料：

[1] Why Momentum Really Works https://distill.pub/2017/momentum/