为何我们需要动量
2021年8月3日 · #research · Read in English
我们经常把梯度下降中的动量方法看作是一种去除振荡和加速迭代的好方法，但是它有时也会表演一些其他有趣的行为。它在允许更大的学习速率的同时也带来了自己的振荡行为。这是什么原因呢。
这张图看起来是可互动的，实际上它确实是可以互动的，只不过不是在这篇笔记里。因为这篇笔记中的大部分内容是对 https://distill.pub/2017/momentum/ 的翻译，如果你很爱读英文的话，希望你直接去阅读原作者的文章，原文默认大家都有一个更高的数学水平，但是也挖掘地更加透彻，也有一些中文难以表达的幽默，同时还有极其炫酷的可交互图表，阅读原文也是对原作者的支持哦。
这篇笔记的特点是为各位线性代数不是很好的同志们铺平了道路，而且最重要的是这是中文文章。话不多说，让我们开始吧。
有一个关于动量的形象比喻是这样的：梯度下降就是一个人走下山坡。他总是沿着最陡的路径下山，虽然他走的很慢，但是很稳。动量方法就是一个大滚石滚下同样的山坡。这给了它一些惯性的特点，包括轨迹更连贯更快，有抵抗振荡的能力，还可以使我们冲过比较窄的峡谷，小坑和局部最优点。
这个标准的故事不能说他错，但它实际上并不能解释很多动量方法的独特行为。实际上，只要我们用正确的模型研究动量，我们就可以更加准确地了解动量概念。
一个很好的模型就是凸二次型 。这个模型足够复杂，可以重现动量在实际问题中的各种局部动态行为；但是也足够简单，可以让我们深入彻底地分析它。这样的平衡给了我们足够的动力去把它作为标准模型来了解算法。
什么是凸二次型？z = a 1 y 2 + a 2 x y + a 3 x 2 z=a_1 y^2+a_2 xy + a_3 x^2 z = a 1 y 2 + a 2 x y + a 3 x 2 z = [ x y ] [ a 1 a 2 / 2 a 2 / 2 a 3 ] [ x y ] z=\begin{bmatrix} {x\ \ y}\end{bmatrix}\begin{bmatrix} a_1& a_2/2\\\\a_2/2 &a_3\end{bmatrix}\begin{bmatrix} {x\\\\ y}\end{bmatrix} z = [ x y ] a 1 a 2 /2 a 2 /2 a 3 [ x y ] z = X T A X z=X^TAX z = X T A X
我们先从梯度下降 开始吧。这个算法有着诸多优点，可惜速度并不是其中之一。它的公式是这样的：当优化一个平滑的函数 f，我们就在梯度上迈出一小步：
w k + 1 = w k − α ∇ f ( w k )
w^{k+1}=w^k-\alpha\nabla f(w^k)
w k + 1 = w k − α ∇ f ( w k ) 如果这一步足够小，那么梯度下降每次的移动都是单调下降的。它一定可以收敛，尽管一般都是在局部最小值。不过只要有几个很弱的条件，它甚至可以以指数级的速度抵达最低点（后面会解释）。但是这种指数级下降的情况，尽管在理论上非常可能发生，但是事实上它即使发生了，一般也是非常的微弱。在梯度下降一开始时，你会觉得一切都很好——几乎可以立即在损失函数上看到显著的下降。但是随着梯度下降的进行，那条 Loss 曲线的速度就开始变慢了。你这时会开始觉得你的迭代算法的进度似乎不如一开始那样理想，你会好奇，到底是哪出了问题？
答案可能是你遇上优化算法的死对头——病态曲率 了。病态曲率指的就是 f f f
动量方法就是在原有梯度下降的基础上做了一点修改，使之具有了短期的记忆能力：
z k + 1 = β z k + ∇ f ( w k ) w k + 1 = w k − α z k + 1
z^{k+1} = \beta z^{k}+\nabla f(w^k) \\\\
w^{k+1} = w^k - \alpha z^{k+1}
z k + 1 = β z k + ∇ f ( w k ) w k + 1 = w k − α z k + 1 这个修改的好处就在于它基本没修改什么。如果 β = 0 \beta=0 β = 0 β = 0.99 \beta=0.99 β = 0.99 β = 0.999 \beta=0.999 β = 0.999
这个新的算法第一眼看过去就是一个简单的小伎俩，通过抵消梯度下降的异常行为来平滑轨迹还有减少振荡现象。但是事实恰恰相反。梯度下降才是动量方法中的小伎俩 。首先，动量方法抛弃了在很多函数中的二次型加速的优势。这可不是什么小事，这就像你抛弃了快速傅立叶变换，快速排序中的速度优势一样。
Nesterov 曾礼貌地指出，动量方法，从狭隘的技术化的角度来看，简直完美。“Nesterov, states that momentum is, in a certain very narrow and technical sense, optimal”。实际上，它满足了很多有趣又美丽的数学性质，让那些有数学强迫症的人身心舒畅。这点我们以后再说。我现在想说的是——动量是一个教科书级的算法。
第一步 梯度下降
我们先让我们的优化函数是一个凸二次型：
f ( w ) = 1 2 w T A w − b T w , w ∈ R n
f(w)=\frac12 w^TAw-b^Tw,\ \ \ \ w \in \mathbb{R}^n
f ( w ) = 2 1 w T A w − b T w , w ∈ R n 假设 A 是对称且可逆的，那么我们可以直接解出最优的 w ∗ w^* w ∗
w ∗ = A − 1 b （解的过程略，实际上就是令梯度为零）
w^*=A^{-1}b（解的过程略，实际上就是令梯度为零）
w ∗ = A − 1 b （解的过程略，实际上就是令梯度为零） 尽管这个模型如此简单，它的复杂程度足够你拟合很多的函数了（想象 A 就是你最爱的模型——Heissian 矩阵，费歇尔信息矩阵等的，如果你不知道这些是啥没有任何关系）。它也能包含所有病态曲率的关键特征。当然最重要的是你可以以此写出梯度下降的封闭形式 ：
因为 ∇ f ( w ) = A w − b \nabla f(w)=Aw-b ∇ f ( w ) = A w − b
w k + 1 = w k − α ( A w k − b )
w^{k+1} = w^k - \alpha(Aw^k-b)
w k + 1 = w k − α ( A w k − b ) 这里有一个重要的技巧：我们可以在一种非常自然的坐标体系下观察梯度下降，使得梯度下降里的每个参数的迭代都只和自己的值有关，和其他参数无关（由于矩阵乘法 A w k Aw^k A w k w w w A A A A A A
每一个对称阵 A A A 相似对角化 ：
A = Q d i a g ( λ 1 , λ 2 , ⋯ , λ n ) Q − 1 , Q = [ q 1 , q 2 , ⋯ , q n ] a n d Q − 1 = Q T
A=Q diag(\lambda_1,\lambda_2,\cdots,\lambda_n)Q^{-1},\ \ \ \ Q=[q_1, q_2, \cdots,q_n]\\\\
and Q^{-1}=Q^T \\\\
A = Q d ia g ( λ 1 , λ 2 , ⋯ , λ n ) Q − 1 , Q = [ q 1 , q 2 , ⋯ , q n ] an d Q − 1 = Q T （由于矩阵乘法代表了一个向量在另一组基底下的表示，那么形如 A=QBQ^{-1}的含义就是，存在一组基底 q 1 , q 2 , ⋯ , q n q_1, q_2, \cdots,q_n q 1 , q 2 , ⋯ , q n
如图所示，可以通过矩阵变换将本来互相牵连的 w w w
并且为了方便起见，我们假设 λ 1 … n \lambda_{1…n} λ 1 … n 。我们对现有的 w k w^k w k w ∗ w^* w ∗ x k = Q T ( w k − w ∗ ) x^k=Q^T(w^k-w^*) x k = Q T ( w k − w ∗ ) x k → 0 x^k\rightarrow0 x k → 0
由于 A = Q E Q T w k + 1 = w k − α ( A w k − b ) w k + 1 = w k − α ( ( Q E Q T ) w k − ( Q E Q T ) A − 1 b ) 两边左乘 Q T Q T w k + 1 = Q T w k − α E Q T ( w k − w ∗ )
\begin{align}
由于A&=QEQ^T\\\\
w^{k+1} &= w^k - \alpha(Aw^k-b) \\\\
w^{k+1} &= w^k - \alpha((QEQ^T)w^k-(QEQ^T)A^{-1}b)两边左乘Q^T\\\\
Q^Tw^{k+1}&=Q^T w^k - \alpha EQ^T(w^k-w^*)\\\\
\end{align}
由于 A w k + 1 w k + 1 Q T w k + 1 = QE Q T = w k − α ( A w k − b ) = w k − α (( QE Q T ) w k − ( QE Q T ) A − 1 b ) 两边左乘 Q T = Q T w k − α E Q T ( w k − w ∗ ) 对于其中每一个参数：
x i k + 1 = x i k − α λ i x i k = ( 1 − α λ i ) x i k = ( 1 − α λ i ) k + 1 x i 0
x^{k+1}_i =x_i^{k}-\alpha\lambda_i x^k_i=(1-\alpha\lambda_i)x_i^k=(1-\alpha\lambda i)^{k+1}x^0_i
x i k + 1 = x i k − α λ i x i k = ( 1 − α λ i ) x i k = ( 1 − α λi ) k + 1 x i 0 转移回到原来的空间下，我们有：
w k − w ∗ = Q x k = ∑ i n x i 0 ( 1 − α λ i ) k q i
w^k-w^*=Qx^k=\sum_i^nx_i^0(1-\alpha\lambda_i)^kq_i
w k − w ∗ = Q x k = i ∑ n x i 0 ( 1 − α λ i ) k q i 这就是封闭形式下的梯度下降 。
拆分误差
上述公式给出了一个简单而深刻的道理：在凸二次型的优化中，每个初始参数差值 x i 0 x^0_i x i 0 Q Q Q n n n ( 1 − α λ i ) (1-\alpha\lambda_i) ( 1 − α λ i )
（P.S. 我翻译这篇文章的原因正是我非常喜欢它的思考方式——用足够简单又典型的例子结合封闭形式的公式，得到精准又直观的结论。我认为对于培养直觉非常有好处。）
对于大多数的步长来说，有着最大特征特征值的特征向量对应着最快的收敛速度。正是这个原因导致了梯度下降在前几步会产生很明显的损失减小，等待大的特征值对应的损失被消灭了以后，小特征值的缓慢下降开始浮出水面成为主流，这时我们就开始抱怨梯度下降进展缓慢了。
如果写出每个参数对应的特征子空间对于损失的贡献：
f ( w k ) − f ( w ∗ ) = ∑ ( 1 − α λ i ) 2 k λ i [ x i 0 ] 2
f(w^k)-f(w^*)=\sum(1-\alpha \lambda_i)^{2k}\lambda_i[x_i^0]^2
f ( w k ) − f ( w ∗ ) = ∑ ( 1 − α λ i ) 2 k λ i [ x i 0 ] 2 我们就可以可视化每个误差项在 Loss 中的占比。（想要体验交互图表前往原网页）
选一个步长吧
上面的分析给了我们关于如何选择步长 α \alpha α ∣ 1 − α λ i ∣ |1-\alpha\lambda_i| ∣1 − α λ i ∣
0 < α λ i < 2
0<\alpha\lambda_i<2
0 < α λ i < 2 这个整体的收敛速率是由最慢收敛的那一项误差项决定的，也就是必须是 λ 1 \lambda_1 λ 1 λ n \lambda_n λ n λ \lambda λ
r a t e ( α ) = max i ∣ 1 − α λ i ∣ = max { ∣ 1 − α λ 1 ∣ , ∣ 1 − α λ n ∣ }
rate(\alpha)=\max_i |1-\alpha\lambda_i|=\max\{|1-\alpha\lambda_1|,|1-\alpha\lambda_n|\}
r a t e ( α ) = i max ∣1 − α λ i ∣ = max { ∣1 − α λ 1 ∣ , ∣1 − α λ n ∣ } 整体的收敛速率当 λ 1 \lambda_1 λ 1 λ n \lambda_n λ n
o p t i m a l α = arg min α r a t e ( α ) = 2 λ 1 + λ n o p t i m a l r a t e ( α ) = min α r a t e ( α ) = λ n / λ 1 − 1 λ n / λ 1 + 1
optimal\ \alpha= \arg\min_\alpha rate(\alpha)=\frac{2}{\lambda_1+\lambda_n} \\\\
optimal\ rate(\alpha)= \min_\alpha rate(\alpha)=\frac{\lambda_n/\lambda_1-1}{\lambda_n/\lambda1+1}
o pt ima l α = arg α min r a t e ( α ) = λ 1 + λ n 2 o pt ima l r a t e ( α ) = α min r a t e ( α ) = λ n / λ 1 + 1 λ n / λ 1 − 1 注意，这个比例 λ n / λ 1 \lambda_n/\lambda_1 λ n / λ 1
c o n d i t i o n n u m b e r ( 条件数 ) : = κ : = λ n λ 1
condition\ number(条件数):=\kappa:=\frac{\lambda_n}{\lambda_1}
co n d i t i o n n u mb er ( 条件数 ) := κ := λ 1 λ n 条件数有很多含义。它可以衡量一个矩阵和奇异矩阵的接近程度。它可以衡量 A − 1 b A^{-1}b A − 1 b b b b
例子：多项式回归
上面的分析解释了一个道理：误差项和误差项之间是不平等的。实际上，一个问题中存在多种误差，嗯，严格来说是 n n n A A A A A A
让我们看看我们刚学到的知识在多项式回归里是怎么作用的吧。给定 1 维数据 ξ i \xi_i ξ i d i d_i d i
m o d e l ( ξ ) = w 1 p 1 ( ξ ) + w 2 p 2 ( ξ ) + ⋯ + w n p n ( ξ ) , p n ( x ) = x n − 1
model(\xi)=w_1p_1(\xi)+w_2p_2(\xi)+\cdots+w_np_n(\xi), \ \ \ p_n(x) = x^{n-1}
m o d e l ( ξ ) = w 1 p 1 ( ξ ) + w 2 p 2 ( ξ ) + ⋯ + w n p n ( ξ ) , p n ( x ) = x n − 1 虽然这个模型相对于输入 ξ \xi ξ
因为这种线性性质，我们可以用线形回归描述我们的模型在数据 ξ i \xi_i ξ i
m i n i m i z e w 1 2 ∑ i ( m o d e l ( ξ i ) − d i ) 2 = 1 2 ∣ ∣ Z w − d ∣ ∣ 2
minimize_w\ \ \ \frac12\sum_i(model(\xi_i)-d_i)^2=\frac12||Zw-d||^2
minimi z e w 2 1 i ∑ ( m o d e l ( ξ i ) − d i ) 2 = 2 1 ∣∣ Z w − d ∣ ∣ 2 其中
Z = [ 1 ξ 1 ξ 1 2 ⋯ ξ 1 n − 1 1 ξ 2 ξ 2 2 ⋯ ξ 2 n − 1 ⋮ ⋮ ⋮ ⋮ ⋮ 1 ξ m ξ m 2 ⋯ ξ m n − 1 ]
Z=\begin{bmatrix}
1&\xi_1&\xi_1^2&\cdots&\xi_1^{n-1}\\\\
1&\xi_2&\xi_2^2&\cdots&\xi_2^{n-1}\\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\\
1&\xi_m&\xi_m^2&\cdots&\xi_m^{n-1}\\\\
\end{bmatrix}
Z = 1 1 ⋮ 1 ξ 1 ξ 2 ⋮ ξ m ξ 1 2 ξ 2 2 ⋮ ξ m 2 ⋯ ⋯ ⋮ ⋯ ξ 1 n − 1 ξ 2 n − 1 ⋮ ξ m n − 1 注意，这个问题中的 A A A Z Z Z Z T Z Z^TZ Z T Z Q Q Q Q Q Q w w w x = Q w x=Qw x = Qw p p p p ˉ \bar{p} p ˉ
m o d e l ( ξ ) = x 1 p ˉ 1 ( ξ ) + ⋯ + x n p ˉ n ( ξ ) , p ˉ i = ∑ q i j p j
model(\xi)=x_1\bar p_1(\xi)+\cdots+x_n\bar p_n(\xi),\ \ \ \bar p_i=\sum q_{ij}p_j
m o d e l ( ξ ) = x 1 p ˉ 1 ( ξ ) + ⋯ + x n p ˉ n ( ξ ) , p ˉ i = ∑ q ij p j 虽然形式不一样，但是这个模型和原有的模型是同一个模型。在这个模型下任意一个项 x i p ˉ i ( ξ ) x_i\bar p_i(\xi) x i p ˉ i ( ξ ) x i p ˉ i ( ξ ) x_i\bar p_i(\xi) x i p ˉ i ( ξ ) x i x_i x i p ˉ i ( ξ ) \bar p_i(\xi) p ˉ i ( ξ ) x i x_i x i
这些新的特征 p ˉ \bar{p} p ˉ x x x x i x_i x i
这里一共有六个特征值，这批数据里的点聚在两簇。前两幅图反映了前两个特征值，它们涵盖了这两个点簇的位置差距。
接下来的特征值描述了点簇内部的变化和朝向
最后两个特征值对应锯齿状的函数，在相邻的顶点上有着巨大的变化（损失值在该方向上变化率大说明该方向可能有着更大的特征值）
上面那个图表里的观察证据都可以通过数学的方法证明。从统计的角度来看，我们喜欢的模型应该是对噪音鲁棒的。如果很小的扰动就剧烈地改变整个模型，那这个模型大概率没什么意义。这些代表着特征值的特征，是整个数据的黄金部分，正好赋予了我们把特征按照对扰动敏感程度排序的能力。这种分解特征的能力正是 A A A
这种描述鲁棒性的方法，同时也是一个描述一个特征空间收敛快慢的方法。因此，病态曲率中病态的方向对应的误差项，也正是特征空间中收敛的最慢（这需要 α \alpha α ∣ 1 − α λ i ∣ |1-\alpha\lambda_i| ∣1 − α λ i ∣
那么让我们把这个多项式回归的参数初值都设为 0，然后跟踪迭代过程直到达到非常过拟合的程度，让我们看看这些性质如何体现在梯度下降里吧。
十分推荐你自己到网站当中操作一下可交互图表感受变化。一开始，中等大小的特征值对应的误差项最先收敛。
最为鲁棒的特征完成收敛以后，就是更加细节的，λ \lambda λ
最后是最为敏感的误差项收敛也完成了，算法达到了过拟合。各种各样的防止过拟合的算法都是围绕消灭最底下的最大特征值展开的（早停：不给大特征值收敛的机会/减小算法复杂度：直接在 A 里砍掉多余的特征空间维度/正则化：构建一个要求所有特征子空间尽可能收缩的附加任务来抵抗误差项参数靠近最佳参数值的趋势）
Early stopping 这种方法就很好的利用了这个特点：通过早点停止优化，你一般会得到泛化能力更强的结果。实际上，早停的效果和我们更加常见的正则化方法是相似的（比如 L2 正则），都是通过直接抑制最小特征值（我觉得这里应该是最大，可能是我理解有误）的误差项来阻止过拟合。但是早停有一个非常直接的好处。一旦选定了迭代的步长，就没有放进正则参数的地方了。但是在单独的一次优化的过程中，我们有从欠拟合到过拟合的整整一族的模型可供选择。这简直是天上掉馅饼，早停似乎只有好处而没有坏处。
动量方法
让我们把注意力转回动量。回忆我们的动量更新公式：
v k + 1 = β v k + ∇ f ( w k ) w k + 1 = w k − α z k + 1
v^{k+1} = \beta v^{k}+\nabla f(w^k) \\\\
w^{k+1} = w^k - \alpha z^{k+1}
v k + 1 = β v k + ∇ f ( w k ) w k + 1 = w k − α z k + 1 因为 ∇ f ( w k ) = A w k − b \nabla f(w^k)=Aw^k-b ∇ f ( w k ) = A w k − b
v k + 1 = β v k + A w k − b w k + 1 = w k − α z k + 1
v^{k+1} = \beta v^{k}+Aw^k-b \\\\
w^{k+1} = w^k - \alpha z^{k+1}
v k + 1 = β v k + A w k − b w k + 1 = w k − α z k + 1 和我们处理梯度下降的方法如出一辙，我们改变基底 x k = Q ( w k − w ∗ ) x^k=Q(w^k-w^*) x k = Q ( w k − w ∗ ) y k = Q z k y^k=Qz^k y k = Q z k
y i k + 1 = β y i k + λ i x i k x i k + 1 = x i k − α y i k + 1
y^{k+1}_i=\beta y^k_i+\lambda_ix_i^k \\\\
x^{k+1}_i=x_i^k-\alpha y_i^{k+1}
y i k + 1 = β y i k + λ i x i k x i k + 1 = x i k − α y i k + 1 同样的，在这样的基底下，每个误差项的优化都是独立于其他误差项的（不过 x i k x_i^k x i k y i k y_i^k y i k
( y i k x i k ) = R k ( y i 0 x i 0 ) , 其中 R = ( β λ i − α β 1 − α λ i )
\begin{pmatrix}
y_i^k\\\\x_i^k
\end{pmatrix}
= R^k
\begin{pmatrix}
y_i^0\\\\x_i^0
\end{pmatrix}
,其中R=\begin{pmatrix}
\beta&\lambda_i\\\\
-\alpha\beta&1-\alpha\lambda_i
\end{pmatrix}
y i k x i k = R k y i 0 x i 0 , 其中 R = β − α β λ i 1 − α λ i 想办法将 R R R k k k σ 1 , σ 2 \sigma_1,\sigma_2 σ 1 , σ 2 R R R
R k = { σ 1 k R 1 − σ 2 k R 2 , σ 1 ≠ σ 2 σ 1 k ( k R / σ 1 − ( k − 1 ) I ) , σ 1 = σ 2 , R j = R − σ j I σ 1 − σ 2
R^k=\left\{
\begin{aligned}
\sigma_1^kR_1-\sigma_2^kR_2&,& \sigma_1 \neq \sigma_2 \\\\
\sigma_1^k(kR/\sigma_1-(k-1)I) &,& \sigma_1=\sigma_2
\end{aligned}
\right.
,\ \ \ \ R_j=\frac{R-\sigma_jI}{\sigma_1-\sigma_2}
R k = ⎩ ⎨ ⎧ σ 1 k R 1 − σ 2 k R 2 σ 1 k ( k R / σ 1 − ( k − 1 ) I ) , , σ 1 = σ 2 σ 1 = σ 2 , R j = σ 1 − σ 2 R − σ j I 这个公式虽然很复杂，但是最重要的是现在 R R R 1 − α λ 1-\alpha\lambda 1 − α λ max { ∣ σ 1 ∣ , ∣ σ 2 ∣ } \max\{|\sigma_1|,|\sigma_2|\} max { ∣ σ 1 ∣ , ∣ σ 2 ∣ } R k = σ 1 k R 1 − σ 2 k R 2 R^k=\sigma_1^kR_1-\sigma_2^kR_2 R k = σ 1 k R 1 − σ 2 k R 2 R k → 0 R^k\rightarrow0 R k → 0 σ 1 k , σ 2 k → 0 \sigma_1^k,\sigma_2^k\rightarrow0 σ 1 k , σ 2 k → 0
涟漪：R 的特征值在此时是复数，同时迭代时，f ( k ) = R k f(k)=R^k f ( k ) = R k 2 β 2\sqrt\beta 2 β α \alpha α λ i \lambda_i λ i
单调下降：R 的特征值都是实数，同时模长也都小于 1。这时的行为很像梯度下降。
一步收敛。当 α = 1 / λ i \alpha=1/\lambda_i α = 1/ λ i β = 0 \beta=0 β = 0
单调振荡：当 α > 1 / λ i \alpha>1/\lambda_i α > 1/ λ i f ( k ) = R k f(k)=R^k f ( k ) = R k α > 1 / λ i \alpha>1/\lambda_i α > 1/ λ i R k R^k R k x i k x_i^k x i k x i k x_i^k x i k
发散：当 max { ∣ σ 1 ∣ , ∣ σ 2 ∣ } > 1 \max\{|\sigma_1|,|\sigma_2|\}>1 max { ∣ σ 1 ∣ , ∣ σ 2 ∣ } > 1
那么怎样的 α \alpha α β \beta β σ 1 , σ 2 \sigma_1,\sigma_2 σ 1 , σ 2 max { ∣ σ 1 ∣ , ∣ σ 2 ∣ } < 1 \max\{|\sigma_1|,|\sigma_2|\}<1 max { ∣ σ 1 ∣ , ∣ σ 2 ∣ } < 1 α \alpha α
0 < α λ i < 2 + 2 β f o r 0 ≤ β < 1
0<\alpha\lambda_i<2+2\beta\ \ \ for \ \ \ \ 0 \leq \beta < 1
0 < α λ i < 2 + 2 β f or 0 ≤ β < 1 令 β = 0 \beta=0 β = 0
临界阻尼系数
真正的魔法发生于当我们确定下最优的 α \alpha α β \beta β β \beta β
当 α \alpha α
− y i k -y_i^k − y i k x i k x_i^k x i k
β \beta β 水平轴 ：当 λ i = 0 , β = 0 \lambda_i=0,\beta=0 λ i = 0 , β = 0 β \beta β
λ \lambda λ 竖直轴 ：外力使得粒子有回到原点的趋势。结合阻尼和外力场，粒子的运动就类似一个阻尼谐波振荡器。
（虽然你应该明白，但是事实上左下角的圆并不是在说明粒子在做圆周运动，只是说明粒子在做恒定的简谐运动（因为没有阻力））。
这个系统可以被想象为一个重物挂在弹簧上。我们下拉一下重物，松手并观察它的运动。在这个比喻中，平衡态就是位置 x i k x_i^k x i k
和 y i k y_i^k y i k β \beta β
阻尼不足：β \beta β
完美阻尼：在两个极端之间是最完美的 β \beta β β = ( 1 − α λ i ) 2 \beta=(1-\sqrt{\alpha\lambda_i})^2 β = ( 1 − α λ i ) 2
阻尼过大：当 β \beta β β = 0 \beta=0 β = 0
临界值 β = ( 1 − α λ i ) 2 \beta=(1-\sqrt{\alpha\lambda_i})^2 β = ( 1 − α λ i ) 2 1 − α λ i 1-\sqrt{\alpha\lambda_i} 1 − α λ i i i i 1 − α λ i 1-\alpha\lambda_i 1 − α λ i α \alpha α i i i
最佳参数
为了得到一个全局的收敛速率，我们必须同时优化 α \alpha α β \beta β
α = ( 2 λ 1 + λ n ) 2 , β = ( λ n − λ 1 λ n + λ 1 ) 2
\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
α = ( λ 1 + λ n 2 ) 2 , β = ( λ n + λ 1 λ n − λ 1 ) 2 把这个代入收敛率公式中，你会得到：
只需要一点点努力，我们就把条件数缩小了一个平方根！当然要完全利用这里的加成，我们得对 λ 1 , λ 2 \lambda_1,\lambda_2 λ 1 , λ 2 α \alpha α β \beta β α \alpha α
在你和这张图互动的时候（要互动去原网站），你会发现：梯度下降的 Loss 曲线有着优雅连续下降的曲线，而动量的优化过程就伴随着清晰的振荡。这个振荡的涟漪不局限于二次型，实践中几乎出现于所有的函数里。它们不是一种警告，只是提醒你这里还有这调参的空间呢。(接下来有一个动量法的应用例子，因为需要配合可交互图像才能很好的理解，因此就不翻译了。)
下降方法的局限性
让我们退一步看。我们现在使用了一个聪明的技巧，将梯度下降的速度提升了平方倍，而这一切的代价只是一个简单的辅助序列。那么我们很自然地会想——这就是我们的极限了吗？我们有没有可能再多引入几个序列进一步提高收敛速度？有没有人可以发明适应性和智能的方法选择最优的 α \alpha α β \beta β
不幸的是，尽管各种对于动量算法的改进算法确实存在，但是，它们的收敛时间都磕在了一个明确，坚硬的，几乎无法逃脱的下确界上。
算法空间里的冒险
想要理解我们所能做的一切的极限，我们需要首先严谨定义我们正在搜索的算法空间。这里有一个可能的定义。就我们的观察，梯度下降和动量方法都是可以 " 展开 " 的。事实上，由于：
w 1 = w 0 − α ∇ f ( w 0 ) w 2 = w 1 − α ∇ f ( w 1 ) = w 0 − α ∇ f ( w 1 ) − α ∇ f ( w 0 ) ⋮ w k + 1 = w 0 − α ∇ f ( w 0 ) − ⋯ − α ∇ f ( w k )
\begin{aligned}
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)\\\\
&\vdots\\\\
w^{k+1}&=w^0-\alpha\nabla f(w^0)-\cdots-\alpha\nabla f(w^k)
\end{aligned}
w 1 w 2 w k + 1 = w 0 − α ∇ f ( w 0 ) = w 1 − α ∇ f ( w 1 ) = w 0 − α ∇ f ( w 1 ) − α ∇ f ( w 0 ) ⋮ = w 0 − α ∇ f ( w 0 ) − ⋯ − α ∇ f ( w k ) 我们可以把梯度下降写作
w k + 1 = w 0 − α ∑ i k ∇ f ( w i )
w^{k+1}=w^0-\alpha\sum_i^k\nabla f(w^i)
w k + 1 = w 0 − α i ∑ k ∇ f ( w i ) 我们可以对动量方法做同样的操作：
w k + 1 = w 0 + α ∑ i k ( 1 − β k + 1 − i ) 1 − β ∇ f ( w i )
w^{k+1}=w^0+\alpha\sum_i^k\frac{(1-\beta^{k+1-i})}{1-\beta}\nabla f(w^i)
w k + 1 = w 0 + α i ∑ k 1 − β ( 1 − β k + 1 − i ) ∇ f ( w i ) 事实上，所有形式的基于一阶导数的算法，包括共轭梯度法、AdaMax、平均梯度法等等，都可以被写成（当然不一定简洁）这个展开形式。因此对于这样一族的算法
w k + 1 = w 0 + α ∑ i k γ i k f ( w i )
w^{k+1}=w^0+\alpha\sum_i^k\gamma^k_i f(w^i)
w k + 1 = w 0 + α i ∑ k γ i k f ( w i ) 包含了梯度下降，动量以及一切你能想到的优化算法。这也是 Nesterov 的假设中的一个假设。但是让我们把这个定义更向前推一步，扩展这个族使得允许在不同的方向上有着不同的学习率：
w k + 1 = w 0 + ∑ i k Γ i k ∇ f ( w k ) , 其中 Γ i k 是一个对角阵
w^{k+1}=w^0+\sum^k_i\Gamma^k_i \nabla f(w^k),其中\Gamma^k_i是一个对角阵
w k + 1 = w 0 + i ∑ k Γ i k ∇ f ( w k ) , 其中 Γ i k 是一个对角阵 这一类的算法涵盖了几乎所有用来训练神经网络的算法，包括 Adam 和 AdaGrad。我们把这类方法叫做 " 线形一阶方法（Linear First Order Methods）"，接下来我将展示一个使这些所有算法都跌跟头的函数。
抵抗的神谕（原文就是这么写的）
我们让每个 w i w_i w i
这个函数的最优解是：
w i ∗ = ( κ − 1 κ + 1 ) i
w_i^*=\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^i
w i ∗ = ( κ + 1 κ − 1 ) i 这个问题 f n f^n f n n n n κ \kappa κ
这里我们展示了动量方法在 Convex Rosenbrock 上的前 50 次迭代情况（图中 n = 25 n=25 n = 25
右上：这个三角形是我们迭代时的死亡三角洲。在这里的部分参数不会被迭代影响，无论这个参数的用途。（Convex Rosenbrock 中由于第二项的原因，下一个参数的更新依赖于上一个参数的值，直到上一个参数稳定之前这个参数都不能被很好地优化）
右下：剩下的逐渐扩张的区域就是我们的迭代能够影响到的 " 光锥 "。在这些区域，设置了最完美参数的动量方法表现的非常好。（一样的，光锥的产生是由于参数之间的相互影响。）
上面的观察对于任意一个基于一阶偏导的优化算法都是成立的。让我们来证明这一点。首先，我们可以观察到每一个参数的梯度都只依赖于它的直接相邻的上一个和下一个参数。
∇ f ( x ) i = 2 w i − w i − 1 − w i + 1 + 4 κ − 1 w i , i ≠ 1
\nabla f(x)_i=2w_i-w_{i-1}-w_{i+1}+\frac{4}{\kappa-1}w_i,\ \ \ i \neq 1
∇ f ( x ) i = 2 w i − w i − 1 − w i + 1 + κ − 1 4 w i , i = 1 因此既然我们的算法从 0 开始，这保证了每个参数在它的相邻上一个和下一个参数改变之前都是一直为零的。
试着把这种限制看作信息传递中的光速。误差信号至少需要 k k k w 0 w_0 w 0 w k w_k w k
∣ ∣ w k − w ∗ ∣ ∣ ∞ ≥ max i ≥ k + 1 { ∣ w i ∗ ∣ } = ( κ − 1 κ + 1 ) k + 1 = ( κ − 1 κ + 1 ) k ∣ ∣ w 0 − w ∗ ∣ ∣ ∞
\begin{aligned}
||w^k-w^*||_\infin&\geq\max_{i\geq k+1}\{|w^*_i|\} \\\\
&=\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{k+1} \\\\
&=\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{k}||w^0-w^*||_\infin
\end{aligned}
∣∣ w k − w ∗ ∣ ∣ ∞ ≥ i ≥ k + 1 max { ∣ w i ∗ ∣ } = ( κ + 1 κ − 1 ) k + 1 = ( κ + 1 κ − 1 ) k ∣∣ w 0 − w ∗ ∣ ∣ ∞
无穷范数 ∣ ∣ x ∣ ∣ ∞ = max { ∣ x 1 ∣ , ∣ x 2 ∣ , ⋯ , ∣ x n ∣ } ||x||_\infin=\max\{|x_1|,|x_2|,\cdots,|x_n|\} ∣∣ x ∣ ∣ ∞ = max { ∣ x 1 ∣ , ∣ x 2 ∣ , ⋯ , ∣ x n ∣ }
当 n n n f n f^n f n κ \kappa κ
对于像这样的理论下界，我们不应该单纯从字面意思上理解它，而应该从它所代表的精神上去理解。它可能确实在某种程度上给我们在这类算法上的研究投入带来了一种终结感。但这不是意味着基于一阶导数的优化算法已经走到头了。比如，这个理论下界并没有否定我们通过调整问题本身来减小问题条件数的可能性。如果你知道往哪个方向努力的话，这里还有非常多的提升速度的空间。
随机梯度下降里的动量方法
这里还有最后一个值得强调的点。之前的所有讨论都假设我们使用的是真正的梯度——这在现代机器学习项目中是很难得到的。计算精确的梯度需要遍历所有的数据，这个成本可能大的无法接受。相对应的，像 minibatch 采样那样，随机地估计一下梯度，经常被用来代替 ∇ f ( w ) \nabla f(w) ∇ f ( w ) E [ e r r o r ( w ) ] = 0 \mathbb E[error(w)]=0 E [ er r or ( w )] = 0
∇ f ( w ) + e r r o r ( w )
\nabla f(w)+error(w)
∇ f ( w ) + er r or ( w ) 这有助于我们把这个估计的梯度想象成是往我们的迭代过程中注入了某种特别的误差。利用我们之间使用的分析方法，我们可以直接处理掉这个额外的项。在一个二次型优化问题上，这个误差项很容易被分进一个单独的项，有：
这个误差项，ϵ k \epsilon^k ϵ k w k w^k w k
就我们的观察，优化有两个阶段。在一开始的快速变化阶段，噪音的尺度是小于梯度的尺度的，动量方法取得了很大的进展。在第二个更为随机的阶段，噪音盖过了梯度，这时动量就不那么有效了。
注意这里存在一个我们不喜欢的 tradeoff，想要降低某一个部分的误差水平就会使另一个提升。比如，减小步长会减小随机误差，但是也减慢了收敛速率。而和我们的直觉相悖的是，增大动量会导致误差被放大。当然就算有这些不想要的性质，带有动量的随机梯度下降还是在神经网络中展现了一个较理想的表现。就我们的观察，这个快速下降阶段在机器学习中似乎比微调阶段重要的多。并且事实上，最近研究发现噪音其实是一件好事——它扮演了一个隐式的正则项，就像 early stopping 一样，防止了在微调阶段的过拟合。
Onwards and Downwards
关于优化加速的研究正在优化理论的社区看到一丝复兴的迹象。（以下引用请去原文查看）如果这篇文章里的想法让你感到很兴奋的话，你可能会希望去读一读 [13]，这篇文章充分的探索了动量的思想，它把动量看作一个微分方程的离散形式。当然也有其他不那么物理的解释存在。有一些研究给出了把动量看作近似多项式的代数解释。同时一些几何的解释也在出现，把动量和一些更为古老的方法如 Ellipsoid 方法相结合。最后，还有一些解释是关于动量和对偶性的联系的，这些解释可能会给我们关于如何加速二阶导方法和 Quasi Newton 一些启发。但是就像那个盲人摸象的寓言一样，动量似乎是一种比它的部分之和还要大的事物。希望我们可以尽快迎来所有的观点都融合成一个满意的模型的那一天吧。
参考资料：
[1] Why Momentum Really Works https://distill.pub/2017/momentum/
