动量为什么真的有效
中文翻译版

动量为什么真的有效

步长 α = 0.02
动量 β = 0.99
我们通常认为动量是抑制振荡、加速迭代从而使收敛更快的手段。但它还有其他有趣的行为：它允许使用更大范围的步长，并产生自身的振荡。这到底是怎么回事？
Gabriel Goh UC Davis
April. 4
2017
Citation:
Goh, 2017

动量算法，也叫重球法，常常让人觉得与启发它的那套物理直觉密不可分。人们习惯把梯度下降想象成一个人下山，而把动量想象成同一座山坡上滚下的重球。动量为迭代过程赋予了惯性，能抑制陡峭谷地间的来回摆动，强化那些变化较为平滑的方向，让算法得以穿过狭窄山谷、小丘、山脊乃至局部极小值。从这个角度看，动量确实有一种非常自然的物理解释。不过，这套如今几乎成了标准说法的故事，终究只是一个高度简化的比喻。它并非错误，却不足以解释动量的许多关键性质。比如，动量究竟该取多大？它通过越过目标、再借助梯度把轨迹拉回正轨来工作，那么这些“过冲”的迭代真的值得吗？如果值得，能换来多大的加速？再比如，动量还会扩大可用步长的范围，这种扩展的边界在哪里，又为什么会出现？

关于动量，一个广为流传的说法是 [1, 2, 3]：梯度下降像一个人沿最陡方向下山，步子不快，却相当稳；动量则像一个重球沿着同一座山坡滚下。额外的惯性既起到平滑作用，也起到加速作用，能抑制振荡，让我们冲过狭窄的山谷、小丘和局部极小值。

这个经典比喻本身没有错，但它无法解释动量的许多重要特性。事实上，如果我们用正确的模型来研究动量，就能更加精确地理解它。

一个很好的分析对象是凸二次型。它既足够丰富，能够复现动量在真实问题中的局部动力学；又足够简单，可以写出闭式解加以分析。正是这种简洁与表现力之间的平衡，让我们能够真正看清这个算法。

我们从梯度下降开始。该算法有许多优点，但速度不是其中之一。它很简单——当优化一个光滑函数 ff 时，我们在梯度方向上迈出一小步 wk+1=wk−α∇f(wk).w^{k+1} = w^k-\alpha\nabla f(w^k). 对于足够小的步长，梯度下降在每次迭代中都会单调改进。它总是能收敛，尽管是到一个局部最小值。在一些较弱的曲率条件下，它甚至可以以指数速率到达那里。

然而，理论上诱人的指数收敛，在实践里常常慢得令人沮丧。刚开始时，一切看上去都很好，损失几乎立刻就显著下降；但随着迭代继续推进，速度很快慢了下来。你会隐约觉得，进展似乎没有想象中那么理想。问题到底出在哪里？

问题可能出在优化器的老对手——病态曲率上。简单来说，病态曲率就是 ff 的某些区域没有被适当缩放。这些地形常被描述为峡谷、沟渠、水渠和沟壑。迭代点要么在山谷之间跳跃，要么以小而胆怯的步伐逼近最优点。沿着某些方向的进展会陷入停滞。在这些不幸的区域里，梯度下降步履维艰。

动量对梯度下降做了一个很小的修改：给它加上一点“短期记忆”。更新公式如下： zk+1=βzk+∇f(wk)wk+1=wk−αzk+1 \begin{aligned} z^{k+1}&=\beta z^{k}+\nabla f(w^{k})\\[0.4em] w^{k+1}&=w^{k}-\alpha z^{k+1} \end{aligned} 这个改动很简单，几乎没有额外代价。当 β=0\beta = 0 时，我们恢复为梯度下降。但对于 β=0.99\beta = 0.99（有时是 0.9990.999，如果情况真的很糟糕），这似乎正是我们需要的推动力。我们的迭代恢复了曾经失去的速度和魄力，以焕然一新的能量向最优点冲刺。

优化器称这个小奇迹为"加速"。

乍看之下，动量似乎像是一种廉价的“技巧”：不过是在梯度下降行为失常时打个补丁，顺手抹平陡峭峡谷中的振荡而已。但事实如果说有什么不同，那恰恰是反过来的。某种意义上，真正像权宜之计的反而是梯度下降。首先，动量在很多函数上都能带来高达二次量级的加速。1 这绝不是一个小改进，它和快速傅里叶变换、快速排序、Grover 算法这类著名结果中的加速量级处在同一档次。面对二次加速，很难不认真对待。

还不止如此。Nesterov [5] 给出的下界表明，在一种非常狭义但也非常严格的技术意义上，动量是“最优”的。当然，这并不是说它在任何函数、任何场景下都是最好的算法；但它确实满足了一些近乎优雅到过分的数学性质。关于这一点我们稍后再谈。现在先记住一句话：动量是一类值得认真研究的算法。

第一步：梯度下降

我们从最简单的非平凡模型——凸二次型开始研究梯度下降， f(w)=12wTAw−bTw,w∈Rn. f(w) = \tfrac{1}{2}w^TAw - b^Tw, \qquad w \in \mathbf{R}^n. 假设 AA 是对称且可逆的，那么最优解 w⋆w^{\star} 出现在 w⋆=A−1b. w^{\star} = A^{-1}b. 虽然这个模型很简单，但它足够丰富，可以近似许多函数（将 AA 想象为你最喜欢的曲率模型——Hessian 矩阵、Fisher 信息矩阵 [6] 等），并且捕捉到了病态曲率的所有关键特征。更重要的是，我们可以写出梯度下降在这个函数上的精确闭合公式。

推导如下。由于 ∇f(w)=Aw−b\nabla f(w)=Aw - b，迭代公式为 wk+1=wk−α(Awk−b). w^{k+1}=w^{k}- \alpha (Aw^{k} - b). 这里有个技巧。有一个非常自然的空间来观察梯度下降，在这个空间中所有维度独立作用——即 AA 的特征向量。

每个对称矩阵 AA 都有一个特征值分解 A=Q diag(λ1,…,λn) QT,Q=[q1,…,qn], A=Q\ \text{diag}(\lambda_{1},\ldots,\lambda_{n})\ Q^{T},\qquad Q = [q_1,\ldots,q_n], ，按照惯例，我们假设 λi\lambda_i 从小到大排序，从最小的 λ1\lambda_1 到最大的 λn\lambda_n。如果我们进行基变换 xk=QT(wk−w⋆)x^{k} = Q^T(w^{k} - w^\star)，迭代会分离为： xik+1=xik−αλixik=(1−αλi)xik=(1−αλi)k+1xi0 \begin{aligned} x_{i}^{k+1} & =x_{i}^{k}-\alpha \lambda_ix_{i}^{k} \\[0.4em] &= (1-\alpha\lambda_i)x^k_i=(1-\alpha \lambda_i)^{k+1}x^0_i \end{aligned} 回到原始空间 ww，我们可以看到 wk−w⋆=Qxk=∑inxi0(1−αλi)kqi w^k - w^\star = Qx^k=\sum_i^n x^0_i(1-\alpha\lambda_i)^k q_i 这就是了——闭合形式的梯度下降。

分解误差

上述方程有一个简单解释。 x0x^0 的每个元素是初始猜测误差在 QQ 基中的分量。共有 nn 个这样的误差，每个误差都沿着自己独立的路径走向最小值，以复合速率 1−αλi1-\alpha\lambda_i 指数递减。这个数越接近 11，收敛就越慢。

对于大多数步长，具有最大特征值的特征向量收敛最快。这在最初的几次迭代中引发了进展的爆发，随着较小特征向量的困境显露出来，速度会放缓。通过将每个特征空间误差对损失的贡献写为 f(wk)−f(w⋆)=∑(1−αλi)2kλi[xi0]2 f(w^{k})-f(w^{\star})=\sum(1-\alpha\lambda_{i})^{2k}\lambda_{i}[x_{i}^{0}]^2 ，我们可以可视化每个误差分量对损失的贡献。

优化可以看作若干子问题的组合，这里用 1 2 3 表示，分别对应特征值 λ1=0.01\lambda_1=0.01、 λ2=0.1\lambda_2=0.1 和 λ3=1\lambda_3=1。
步长
最优步长

选择步长

以上分析为我们如何设置步长 α\alpha 提供了直接指导。为了收敛，每个 ∣1−αλi∣|1-\alpha \lambda_i| 必须严格小于 1。因此所有可行的步长落在区间 0<αλi<2.0<\alpha\lambda_i<2. 中。总体收敛率由最慢的误差分量决定，它必然是 λ1\lambda_1 或 λn\lambda_n： rate(α) = maxi∣1−αλi∣ = max{∣1−αλ1∣, ∣1−αλn∣} \begin{aligned}\text{rate}(\alpha) & ~=~ \max_{i}\left|1-\alpha\lambda_{i}\right|\\[0.9em] & ~=~ \max\left\{|1-\alpha\lambda_{1}|,~ |1-\alpha\lambda_{n}|\right\} \end{aligned}

当 λ1\lambda_1 和 λn\lambda_n 的速率相同时，总体速率被最小化——这印证了我们在前一节中的非正式观察，即最优步长使第一个和最后一个特征向量以相同速率收敛。如果我们推导出来，得到： optimal α = argminα rate(α) = 2λ1+λnoptimal rate = minα rate(α) = λn/λ1−1λn/λ1+1 \begin{aligned} \text{optimal }\alpha ~=~{\mathop{\text{argmin}}\limits_\alpha} ~\text{rate}(\alpha) & ~=~\frac{2}{\lambda_{1}+\lambda_{n}}\\[1.4em] \text{optimal rate} ~=~{\min_\alpha} ~\text{rate}(\alpha) & ~=~\frac{\lambda_{n}/\lambda_{1}-1}{\lambda_{n}/\lambda_{1}+1} \end{aligned}

注意到比值 λn/λ1\lambda_n/\lambda_1 决定了问题的收敛率。事实上，这个比值出现得如此频繁，以至于我们给它起了名字和符号——条件数。 condition number:=κ:=λnλ1 \text{condition number} := \kappa :=\frac{\lambda_n}{\lambda_1} 条件数有多重含义。它是矩阵接近奇异的度量。它是 A−1bA^{-1}b 对 bb 中扰动鲁棒性的度量。而在本文的语境中，条件数给了我们梯度下降表现多差的一个度量。比值为 κ=1\kappa = 1 是理想的，能在一步内收敛（当然，函数是平凡的）。不幸的是，比值越大，梯度下降就越慢。因此条件数是病态曲率的直接度量。

示例：多项式回归

以上分析揭示了一个重要事实：误差并不都是一样的。更准确地说，误差可以分成不同的类型，而这里恰好有 nn 种，对应 AA 的每个特征向量。而梯度下降在纠正某些类型的误差方面比其他类型更擅长。但 AA 的特征向量意味着什么？令人惊讶的是，在许多应用中它们有着非常具体的解释。

让我们看看这在多项式回归中是如何体现的。给定一维数据 ξi\xi_i，我们的问题是拟合模型 model(ξ)=w1p1(ξ)+⋯+wnpn(ξ)pi=ξ↦ξi−1 \text{model}(\xi)=w_{1}p_{1}(\xi)+\cdots+w_{n}p_{n}(\xi)\qquad p_{i}=\xi\mapsto\xi^{i-1} 到观测值 did_i。这个模型虽然对输入 ξ\xi 是非线性的，但对权重是线性的，因此我们可以将模型写为单项式的线性组合，如：

由于线性特性，我们可以使用线性回归在模型不匹配上拟合此模型到数据 ξi\xi_i minimizew12∑i(model(ξi)−di)2  =  12∥Zw−d∥2 \text{minimize}_w \qquad\tfrac{1}{2}\sum_i (\text{model}(\xi_{i})-d_{i})^{2} ~~=~~ \tfrac{1}{2}\|Zw - d\|^2 其中 Z=(1ξ1ξ12…ξ1n−11ξ2ξ22…ξ2n−1⋮⋮⋮⋱⋮1ξmξm2…ξmn−1). Z=\left(\begin{array}{ccccc} 1 & \xi_{1} & \xi_{1}^{2} & \ldots & \xi_{1}^{n-1}\\ 1 & \xi_{2} & \xi_{2}^{2} & \ldots & \xi_{2}^{n-1}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & \xi_{m} & \xi_{m}^{2} & \ldots & \xi_{m}^{n-1} \end{array}\right).

我们知道，收敛的路径在 QQ（ ZTZZ^T Z 的特征向量）的空间中观察时变得清晰。因此让我们在 QQ 的基中重新表述我们的回归问题。首先，我们进行基变换，将 ww 旋转到 QwQw，并将特征映射 pp 逆向旋转到特征空间 p¯\bar{p}。现在我们可以将同样的回归概念化为在不同多项式基上的回归，模型为 model(ξ) = x1p¯1(ξ) + ⋯ + xnp¯n(ξ)p¯i=∑qijpj. \text{model}(\xi)~=~x_{1}\bar{p}_{1}(\xi)~+~\cdots~+~x_{n}\bar{p}_{n}(\xi)\qquad \bar{p}_{i}=\sum q_{ij}p_j. 这个模型与旧模型完全相同。但这些新特征 p¯\bar{p}（我称之为"特征特征"）和权重具有一个令人愉悦的特性：每个坐标独立于其他坐标。现在我们的优化问题真正分解为 nn 个小型一维优化问题。每个坐标可以贪心地、独立地、以任意顺序逐个优化，最终得到全局最优解。特征特征也更加信息丰富：

上图中的现象可以严格地用数学刻画。从统计学角度看，我们希望模型在某种意义上对噪声是鲁棒的；如果观测值发生一点点扰动就会显著改变整个模型，那这样的模型显然靠不住。而特征方向，也就是数据的主成分，恰好提供了我们需要的分解方式，使我们能够按照它们对 did_i 扰动的敏感度对特征进行排序。最鲁棒的分量出现在前面（具有最大的特征值），而最敏感的分量出现在后面（具有最小的特征值）。

这个鲁棒性度量，通过一个相当方便的巧合，也是衡量特征空间收敛难易程度的指标。因此，"病态方向"——收敛最慢的特征空间——也正是对噪声最敏感的方向！所以从像 00 这样简单的初始点开始（用语言上的滥用，我们把它视为先验），我们跟踪迭代直到达到所需的复杂程度。让我们看看这在梯度下降中是如何体现的。

这正是早停这一启发式方法能够发挥作用的原因：提前停止优化，往往反而能得到更好的泛化结果。事实上，早停和更传统的正则化方法（如 Tikhonov 回归）效果颇为相似。两者都在抑制那些对应最小特征值的分量，只不过采用的是不同的谱衰减方式。2 不过，早停有一个很直接的优势：一旦步长选定，就不再需要额外调节正则化参数。换句话说，在一次优化过程中，你已经沿途获得了一整族模型，从欠拟合到过拟合，一应俱全。这几乎像是一顿免费的午餐 [7]。

动量的动力学

让我们将注意力转回动量。回顾动量更新公式为 zk+1=βzk+∇f(wk)wk+1=wk−αzk+1. \begin{aligned} z^{k+1}&=\beta z^{k}+\nabla f(w^{k})\\[0.4em] w^{k+1}&=w^{k}-\alpha z^{k+1}. \end{aligned} 由于 ∇f(wk)=Awk−b\nabla f(w^k) = Aw^k - b，在二次型上的更新为 zk+1=βzk+(Awk−b)wk+1=wk−αzk+1. \begin{aligned} z^{k+1}&=\beta z^{k}+ (Aw^{k}-b)\\[0.4em] w^{k+1}&=w^{k}-\alpha z^{k+1}. \end{aligned} 按照 [8]，我们经历相同的步骤，通过基变换 xk=Q(wk−w⋆) x^{k} = Q(w^{k} - w^\star) 和 yk=Qzk y^{k} = Qz^{k}，得到更新规则 yik+1=βyik+λixikxik+1=xik−αyik+1. \begin{aligned} y_{i}^{k+1}&=\beta y_{i}^{k}+\lambda_{i}x_{i}^{k}\\[0.4em] x_{i}^{k+1}&=x_{i}^{k}-\alpha y_{i}^{k+1}. \end{aligned} 其中每个分量独立于其他分量（虽然 xikx^k_i 和 yiky^k_i 是耦合的）。这使我们可以将迭代重写为 3 (yikxik)=Rk(yi0xi0)R=(βλi−αβ1−αλi). \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) \qquad R = \left(\!\!\begin{array}{cc} \beta & \lambda_{i}\\ -\alpha\beta & 1-\alpha\lambda_{i} \end{array}\!\!\right). 将矩阵求 kthk^{th} 次方有很多方法。但对于 2×22 \times 2 的情况，存在一个优雅而鲜为人知的公式 [9]，用 RR 的特征值 σ1\sigma_1 和 σ2\sigma_2 表示。 Rk={σ1kR1−σ2kR2σ1≠σ2σ1k(kR/σ1−(k−1)I)σ1=σ2,Rj=R−σjIσ1−σ2 \color{#AAA}{\color{black}{R^{k}}=\begin{cases} \color{black}{\sigma_{1}^{k}}R_{1}-\color{black}{\sigma_{2}^{k}}R_{2} & \sigma_{1}\neq\sigma_{2}\\ \sigma_{1}^{k}(kR/\sigma_1-(k-1)I) & \sigma_{1}=\sigma_{2} \end{cases},\qquad R_{j}=\frac{R-\sigma_{j}I}{\sigma_{1}-\sigma_{2}}} 这个公式相当复杂，但要点在于，它扮演着与梯度下降中各个收敛率 1−αλi1-\alpha\lambda_i 完全相同的角色。但不是只有一个几何级数，我们有两个耦合的级数，可能具有实值或复值。因此收敛率是两个速率中较慢的那个， max{∣σ1∣,∣σ2∣}\max\{|\sigma_{1}|,|\sigma_{2}|\} 4。通过将其绘制出来，我们可以看到参数空间的不同区域，揭示出丰富的收敛行为分类 [10]：

Convergence Rate
max{∣σ1∣,∣σ2∣}\max\{|\sigma_1|, |\sigma_2|\} 的图表揭示了不同的区域，每个区域都有其独特的收敛风格。

对于 α\alpha 和 β\beta 取什么值，动量会收敛？由于我们需要 σ1\sigma_1 和 σ2\sigma_2 都收敛，我们的收敛准则现在是 max{∣σ1∣,∣σ2∣}<1\max\{|\sigma_{1}|,|\sigma_{2}|\} < 1。可用步长的范围推导出来 5 为 0<αλi<2+2βfor0≤β<10<\alpha\lambda_{i}<2+2\beta \qquad \text{for} \qquad 0 \leq \beta < 1 当 β=0\beta = 0 时，我们恢复为梯度下降的先前结果。但请注意我们立即获得了一个好处。动量允许我们将步长提高到原来的 2 倍才会发散。

临界阻尼系数

然而，真正的魔法发生在我们找到 α\alpha 和 β\beta 的最佳平衡点时。让我们先尝试优化 β\beta。

当 α\alpha 是 [11] 很小时，动量有一个有趣的物理解释：它是阻尼谐振子的离散化。想象一个在离散时间中运行的物理模拟（像一个视频游戏）。

yik+1y_{i}^{k+1} == ++ λixik\lambda_{i}x_{i}^{k}
并受到外部力场的扰动
我们可以将 −yik-y_i^k 视为 velocity
βyik\beta y_{i}^{k}
它在每一步都被阻尼衰减
xik+1x_i^{k+1} == xik−αyik+1x_i^k - \alpha y_i^{k+1}
而 xx 是我们粒子的 position
它在每一步沿速度 yik+1y^{k+1}_i 的方向移动一小段距离。

我们可以将这个方程分解开来，观察每个分量如何影响系统的动力学。这里我们绘制了 150150 次迭代中粒子的速度（横轴）与位置（纵轴）的相图。

这个系统最好想象为一个悬挂在弹簧上的重物。我们将重物向下拉一个单位，然后研究它返回平衡的路径。在这个类比中，弹簧是我们外力 λixik\lambda_ix^k_i 的来源，平衡是当位置 xikx^k_i 和速度 yiky^k_i 都为 0 时的状态。 β\beta 的选择至关重要地影响着返回平衡的速率。

β=(1−αλi)2\beta = (1 - \sqrt{\alpha \lambda_i})^2 的临界值给我们在特征空间 ii 中的收敛率为 1−αλi.1 - \sqrt{\alpha\lambda_i}. 比梯度下降 1−αλi1-\alpha\lambda_i 有平方根级别的改进！可惜，这仅适用于第 ithi^{th} 个特征空间中的误差，且 α\alpha 固定。

最优参数

为了获得全局收敛率，我们必须同时优化 α\alpha 和 β\beta。这是一件更复杂的事，6 但结果推导出为 α=(2λ1+λn)2β=(λn−λ1λn+λ1)2 \alpha = \left(\frac{2}{\sqrt{\lambda_{1}}+\sqrt{\lambda_{n}}}\right)^{2} \quad \beta = \left(\frac{\sqrt{\lambda_{n}}-\sqrt{\lambda_{1}}}{\sqrt{\lambda_{n}}+\sqrt{\lambda_{1}}}\right)^{2} 将其代入收敛率，你得到

κ−1κ+1\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}
收敛率，Momentum
κ−1κ+1 \frac{\kappa-1}{\kappa+1}
收敛率，Gradient Descent

几乎不需要付出额外代价，我们就等于把条件数开了平方根。原则上，这样的收益需要我们显式知道 λ1\lambda_1 和 λn\lambda_n。但公式揭示了一个简单的指导原则。当问题的条件数很差时，最优 α\alpha 约为梯度下降的两倍，动量项接近 11。因此将 β\beta 设置得尽可能接近 11，然后找到仍然收敛的最高 α\alpha。像梯度下降一样，处于发散的危险边缘是一个好位置。

我们可以用动量做同样的分解，特征值为 λ1=0.01\lambda_1=0.01、 λ2=0.1\lambda_2=0.1 和 λ3=1\lambda_3=1。虽然下降不再是单调的，但显著更快。
f(wk)−f(w⋆)f(w^k) - f(w^\star)
请注意，最优参数并不一定意味着最快的收敛速度，只是最快的渐近收敛率。
步长 α =
动量 β =

梯度下降的损失曲线通常平滑而单调，而加入动量后，优化过程往往会出现明显振荡。这种波动并不只出现在二次型上，在实际问题中同样十分常见。它们并不意味着算法出了问题，更多时候只是提醒你：超参数还需要继续调节。

示例：上色问题

让我们通过一个具体示例来看看动量如何加速收敛。在像素网格上，设 GG 是以像素为顶点的图， EE 是连接每个像素与其四个相邻像素的边的集合， DD 是少量特定顶点的小集合。考虑以下最小化问题：

minimize\text{minimize} 12∑i∈D(wi−1)2\qquad \frac{1}{2} \sum_{i\in D} (w_i - 1)^2
colorizer 将特定像素拉向 1
++ 12∑i,j∈E(wi−wj)2.\frac{1}{2} \sum_{i,j\in E} (w_i - w_j)^2.
smoother 将颜色扩散开

这个问题的最优解是全为 11 的向量 7。检查梯度迭代可以揭示我们为什么需要很长时间才能到达那里。对于每个分量，梯度步是当前值与其邻居的某种加权平均： wik+1=wik−α∑j∈N(wik−wjk)−{α(wik−1)i∈D0i∉D w_{i}^{k+1}=w_{i}^{k}-\alpha\sum_{j\in N}(w_{i}^{k}-w_{j}^{k})-\begin{cases} \alpha(w_{i}^{k}-1) & i\in D\\ 0 & i\notin D \end{cases} 这种局部平均在平滑像素的局部变化方面很有效，但在利用全局结构方面很差。更新类似于一滴墨水滴入水中扩散。朝向平衡的运动只能通过局部修正来实现，因此不受干扰的情况下，其向解的推进是缓慢而费力的。幸运的是，动量显著加快了速度。

上色问题的特征向量构成了 RnR^n 的广义傅里叶基。最小特征值具有低频率，因此梯度下降能很好地纠正高频误差，但不能很好地纠正低频误差。

以向量化形式，上色问题是：

minimize\text{minimize}
smoother 的二次型是 Graph Laplacian
12∑i∈D(xTeieiTx−eiTx)\frac{1}{2}\sum_{i\in D}\left(x^{T}e_{i}e_{i}^{T}x-e_{i}^{T}x\right) ++ 12xTLGx\frac{1}{2}x^{T}L_{G}x
上色器是一个带有线性项的小型低秩修正。 eie_i 是第 ithi^{th} 个单位向量。

拉普拉斯矩阵 LGL_G 8，主导着优化问题的行为，是线性代数与图论之间的宝贵桥梁。这是一个丰富的研究领域，但有件事与我们的讨论密切相关。 LGL_G 的条件数（这里定义为第二个特征向量与最后一个特征向量的比值——第一个特征值始终为 0，对应的特征向量为全 1 矩阵）与图的连通性直接相关。

小世界图，如扩展图和稠密图，具有良好的条件数
网格的条件数随其维度增加而改善。
而狭长、线状的图，如路径图，条件数很差。

这些观察结果延续到上色问题中，其背后的直觉应该是清晰的。连通性良好的图允许信息沿边快速扩散，而连通性差的图则不行。这个原理被推到极致时，提供了一类难以优化的函数，它们揭示了一阶优化的极限。

下降的极限

让我们退一步看。通过一个巧妙的技巧，我们引入了一个辅助序列，就将梯度下降的收敛速度提高了平方因子。但这就是我们能做的最好结果吗？用两个序列能否进一步改善收敛？能否智能且自适应地选择 α\alpha 和 β\beta？乐观的浪潮令人心驰神往——向着立方根乃至更远前进！

不幸的是，虽然动量算法确实存在改进方案，但它们最终都会遇到一个关键的、几乎无法逃避的下界。

算法空间中的探索

为了理解我们能做什么的极限，我们首先必须正式定义我们正在搜索的算法空间。以下是一种可能的定义。我们将观察到，梯度下降和动量都可以被"展开"。实际上，由于 w1=w0 − α∇f(w0)w2=w1 − α∇f(w1)=w0 − α∇f(w0) − α∇f(w1) ⋮wk+1=w0 − α∇f(w0) −    ⋯⋯    − α∇f(wk) \begin{array}{lll} w^{1} & \!= & \!w^{0} ~-~ \alpha\nabla f(w^{0})\\[0.35em] w^{2} & \!= & \!w^{1} ~-~ \alpha\nabla f(w^{1})\\[0.35em] & \!= & \!w^{0} ~-~ \alpha\nabla f(w^{0}) ~-~ \alpha\nabla f(w^{1})\\[0.35em] & ~ \!\vdots \\ w^{k+1} & \!= & \!w^{0} ~-~ \alpha\nabla f(w^{0}) ~-~~~~ \cdots\cdots ~~~~-~ \alpha\nabla f(w^{k}) \end{array} 我们可以将梯度下降写为 wk+1  =  w0 − α∑ik∇f(wi). w^{k+1} ~~=~~ w^{0} ~-~ \alpha\sum_i^k\nabla f(w^{i}). 类似的技巧可以用于动量： wk+1  =  w0 + α∑ik(1−βk+1−i)1−β∇f(wi). w^{k+1} ~~=~~ w^{0} ~+~ \alpha\sum_i^k\frac{(1-\beta^{k+1-i})}{1-\beta}\nabla f(w^i). 实际上，各种一阶算法，包括共轭梯度算法、AdaMax、平均梯度等，都可以写成（虽然不那么整洁）这种展开形式。因此满足 wk+1  =  w0 + ∑ikγik∇f(wi) for some γik w^{k+1} ~~=~~ w^{0} ~+~ \sum_{i}^{k}\gamma_{i}^{k}\nabla f(w^{i}) \qquad \text{ for some } \gamma_{i}^{k} 的算法类包含动量、梯度下降以及你可能想到的一大堆其他算法。这就是 Nesterov 的假设 2.1.4 [5] 中假设的内容。但让我们更进一步，扩展这个类以允许对不同方向使用不同步长。 wk+1  =  w0 + ∑ikΓik∇f(wi) for some diagonal matrix Γik. w^{k+1} ~~=~~ w^{0} ~+~ \sum_{i}^{k}\Gamma_{i}^{k}\nabla f(w^{i}) \quad \text{ for some diagonal matrix } \Gamma_{i}^{k} . 这类方法涵盖了训练神经网络的大多数流行算法，包括 ADAM 和 AdaGrad。我们将这类方法称为"线性一阶方法"，并且我们将展示所有这些方法最终都会在一个函数上失败。

抵抗的预言机

之前，当我们讨论上色问题时，我们观察到线状图会导致优化问题中糟糕的条件数。将其推到极致，我们可以看一个由单一路径组成的图——一个如此病态的函数，以至于 Nesterov 称其变体为"世界上最差的函数"。该函数遵循与上色问题相同的结构，我们将称之为凸 Rosenbrock 函数，

fn(w)f^n(w) ==
带有一个节点的上色器
12(w1−1)2\frac{1}{2}\left(w_{1}-1\right)^{2} ++ 12∑i=1n(wi−wi+1)2\frac{1}{2}\sum_{i=1}^{n}(w_{i}-w_{i+1})^{2}
路径中相邻节点的强耦合，
++ 2κ−1∥w∥2.\frac{2}{\kappa-1}\|w\|^{2}.
以及一个小的正则化项。

此问题的最优解为 wi⋆=(κ−1κ+1)i w_{i}^{\star}=\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{i} ，而问题 fnf^n 的条件数随 nn 趋于无穷而趋近 κ\kappa。现在观察动量算法在此函数上的行为，从 w0=0w^0 = 0 开始。

步长 α =
动量 β =
这里我们展示了在 n=25n=25 下的凸 Rosenbrock 函数上动量算法的前 50 次迭代。此处的行为与任何线性一阶方法类似。
这个三角形是我们迭代点的"死区"。无论参数如何，迭代点始终为 0。
剩余的扩展空间是迭代影响的"光锥"。动量在最优参数下在这里表现得非常好。
Error
Weights

上述图中的观察结果对任何线性一阶方法都是成立的。让我们证明这一点。首先观察到梯度的每个分量仅依赖于其前后直接相邻的值： ∇f(x)i=2wi−wi−1−wi+1+4κ−1wi,i≠1. \nabla f(x)_{i}=2w_{i}-w_{i-1}-w_{i+1} +\frac{4}{\kappa-1} w_{i}, \qquad i \neq 1. 因此，我们从 0 开始这一事实保证了该分量必须坚忍地保持在那里，直到它前面或后面的某个元素变为非零。因此，通过归纳，对于任何线性一阶算法，

w0=[  0,0,0,…0,0,…0 ]w1=[ w11,0,0,…0,0,…0 ]w2=[ w12,w22,0,…0,0,…0 ] ⋮wk=[ w1k,w2k,w3k,…wkk,0,…0 ]. \begin{array}{lllllllll} w^{0} & = & [~~0, & 0, & 0, & \ldots & 0, & 0, & \ldots & 0~]\\[0.35em] w^{1} & = & [~w_{1}^{1}, & 0, & 0, & \ldots & 0, & 0, & \ldots & 0~]\\[0.35em] w^{2} & = & [~w_{1}^{2}, & w_{2}^{2}, & 0, & \ldots & 0, & 0, & \ldots & 0~]\\[0.35em] & ~ \vdots \\ w^{k} & = & [~w_{1}^{k}, & w_{2}^{k}, & w_{3}^{k}, & \ldots & w_{k}^{k}, & 0, & \ldots & 0~].\\ \end{array}

将这种限制视为信息传输的"光速"。误差信号至少需要 kk 步才能从 w0w_0 移动到 wkw_k。因此我们可以将尚未改变的误差相加 9： ∥wk−w⋆∥∞≥maxi≥k+1{∣wi⋆∣}=(κ−1κ+1)k+1=(κ−1κ+1)k∥w0−w⋆∥∞. \begin{aligned} \|w^{k}-w^{\star}\|_{\infty}&\geq\max_{i\geq k+1}\{|w_{i}^{\star}|\}\\[0.9em]&=\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{k+1}\\[0.9em]&=\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{k}\|w^{0}-w^{\star}\|_{\infty}. \end{aligned} 当 nn 很大时， fnf^n 的条件数趋近 κ\kappa。而这个差距因此闭合；动量承诺的收敛率与任何线性一阶方法所能达到的最好结果相匹配。我们得出了令人失望的结论：在这个问题上，我们无法做得更好。

像许多这样的下界一样，这个结果不能从字面上理解，而应领会其精神。它或许给我们的研究带来了一些收尾和终结感。但这并不是一阶优化的最终结论。这个下界并不排除例如重新表述问题以改变条件数本身的可能性！只要你知道正确的地方去寻找，仍然有很大的加速空间。

动量与随机梯度

还有最后一点值得讨论。上述所有讨论都假设我们可以获得真实梯度——这在现代机器学习中是一种很少有的奢侈。计算精确梯度需要对所有数据做一次完整遍历，其代价可能高得令人望而却步。相反，梯度的随机近似，如小批量采样，通常被用作 ∇f(w)\nabla f(w) 的即插即用替代。我们可以将近似写为两个部分：

∇f(w)\nabla f(w)
真实梯度
++ error(w).\text{error}(w).
以及一个近似误差。
如果估计量是无偏的，例如 E[error(w)]=0\mathbf{E}[\text{error}(w)] = 0

将我们的近似梯度视为一种特殊噪声的注入是有帮助的。利用前几节开发的工具，我们可以直接处理这个额外的项。在二次型上，误差项清晰地分裂为一个单独的项，其中 10

(yikxik) \left(\begin{array}{c} y_{i}^{k}\\ x_{i}^{k} \end{array}\right)
带噪声的迭代是以下两者之和：
== Rk(yi0xi0)R^{k}\left(\begin{array}{c} y_{i}^{0}\\ x_{i}^{0} \end{array}\right)
无噪声的确定性迭代
++ ϵik∑j=1kRk−j(1−α)\epsilon^k_i \sum_{j=1}^{k}R^{k-j}\left(\begin{array}{c} 1\\ -\alpha \end{array}\right)
以及误差的衰减和，其中 ϵk=Q⋅error(wk)\epsilon^k = Q \cdot \text{error}(w^k)。

误差项 ϵk\epsilon^k 依赖于 wkw^k，是一个相当棘手的对象。按照 [10] 的做法，我们将其建模为独立的零均值高斯噪声。在这个简化模型中，目标函数也分为两个可分离的分量，即确定性误差和随机误差 11 之和，如下图所示。

我们将目标值的期望 Ef(w)−f(w⋆)\mathbf{E} f(w) - f(w^\star) 分解为确定性部分 和随机部分 。
Ef(w)−f(w⋆)\mathbf{E} f(w) - f(w^\star)
小黑点是随机梯度的单次运行轨迹
步长 α =
动量 β =
正如 [1] 所指出的，优化通常会经历两个阶段。在最初的瞬态阶段，噪声幅度还小于梯度幅度，因此动量依然能够稳定推进；到了后面的随机阶段，噪声开始压过梯度，动量的效果也就随之减弱。

请注意，这里存在一组颇为棘手的权衡，使两类误差此消彼长。比如，减小步长能够降低随机误差，却也会拖慢收敛；而增大动量则与常见直觉相反，可能会让误差不断累积。即便如此，带动量的随机梯度下降在神经网络训练中依然表现出很强的竞争力。正如 [1] 所观察到的，在机器学习里，瞬态阶段往往比最后的微调阶段更重要。甚至还有研究提出 [12]，这种噪声本身也许并非坏事，它像早停一样，充当了一种隐式正则化机制，在优化后期帮助抑制过拟合。

继续前进，持续下降

关于“加速”的研究，近年在优化领域迎来了一次小规模复兴。如果本文的思路让你觉得有意思，不妨继续读一读 [13]，它系统探讨了把动量看成某个微分方程离散化的观点。当然，除了物理直觉之外，还有别的解释路径。代数视角把动量和逼近多项式联系起来 [3, 14]；新近发展的几何视角 [15, 16]，则把它与更早的方法，如椭球法，联系了起来；还有一些解释从对偶性的角度理解动量 [17]，并可能为加速二阶方法和拟牛顿法提供线索（可先参考 [18]）。但就像“盲人摸象”的寓言一样，动量似乎始终比任何单一视角所捕捉到的部分都更完整。希望在不久的将来，这些不同的理解方式能汇聚成一个令人真正满意的整体。

致谢

我深深感谢 Shan Carter 和 Chris Olah 的编辑贡献，没有他们，本文将会大为逊色。Shan Carter 对我许多原创交互组件进行了彻底重新设计，为所有图形带来了视觉一致性，并对页面性能进行了宝贵的优化。Chris Olah 在所有细节和抽象层面都提供了无可挑剔的编辑反馈——从内容结构到公式对齐。

我也感谢 Michael Nielsen 提供了本文的标题，它真正使文章融为一体。Marcos Ginestra 为本文最早期的草稿提供了编辑意见，以及在我最需要时的精神鼓励。我还要感谢我的审稿人 Matt Hoffman 和匿名审稿人 B，感谢他们敏锐的观察和批评。我特别要感谢审稿人 B，他指出原稿中的两个非平凡错误（讨论 here）。首图的等高线绘制库是 Ben Frederickson、Jeff Heer 和 Mike Bostock 的共同作品。

非常感谢在 github 上提交的诸多 pull request 和 issue。特别感谢 Osemwaro Pedro 发现了其中一个公式中的 off-by-one 错误。也感谢 Dan Schmidt 对整个项目进行了编辑，纠正了大量排版和语法错误。

讨论与审阅

Reviewer A - Matt Hoffman
Reviewer B - Anonymous
Discussion with User derifatives

Footnotes

  1. It is possible, however, to construct very specific counterexamples where momentum does not converge, even on convex functions. See [4] for a counterexample.
  2. In Tikhonov Regression we add a quadratic penalty to the regression, minimizing minimize12∥Zw−d∥2+η2∥w∥2=12wT(ZTZ+ηI)w−(Zd)Tw \text{minimize}\qquad\tfrac{1}{2}\|Zw-d\|^{2}+\frac{\eta}{2}\|w\|^{2}=\tfrac{1}{2}w^{T}(Z^{T}Z+\eta I)w-(Zd)^{T}w Recall that ZTZ=Q diag(Λ1,…,Λn) QTZ^{T}Z=Q\ \text{diag}(\Lambda_{1},\ldots,\Lambda_{n})\ Q^T. The solution to Tikhonov Regression is therefore (ZTZ+ηI)−1(Zd)=Q diag(1λ1+η,⋯,1λn+η)QT(Zd) (Z^{T}Z+\eta I)^{-1}(Zd)=Q\ \text{diag}\left(\frac{1}{\lambda_{1}+\eta},\cdots,\frac{1}{\lambda_{n}+\eta}\right)Q^T(Zd) We can think of regularization as a function which decays the largest eigenvalues, as follows: Tikhonov Regularized λi=1λi+η=1λi(1−(1+λi/η)−1). \text{Tikhonov Regularized } \lambda_i = \frac{1}{\lambda_{i}+\eta}=\frac{1}{\lambda_{i}}\left(1-\left(1+\lambda_{i}/\eta\right)^{-1}\right). Gradient descent can be seen as employing a similar decay, but with the decay rate  Gradient Descent Regularized λi=1λi(1−(1−αλi)k) \text{ Gradient Descent Regularized } \lambda_i = \frac{1}{\lambda_i} \left( 1-\left(1-\alpha\lambda_{i}\right)^{k} \right) instead. Note that this decay is dependent on the step-size.
  3. This is true as we can write updates in matrix form as (10α1)(yik+1xik+1)=(βλi01)(yikxik) \left(\!\!\begin{array}{cc} 1 & 0\\ \alpha & 1 \end{array}\!\!\right)\Bigg(\!\!\begin{array}{c} y_{i}^{k+1}\\ x_{i}^{k+1} \end{array}\!\!\Bigg)=\left(\!\!\begin{array}{cc} \beta & \lambda_{i}\\ 0 & 1 \end{array}\!\!\right)\left(\!\!\begin{array}{c} y_{i}^{k}\\ x_{i}^{k} \end{array}\!\!\right) which implies, by inverting the matrix on the left, (yik+1xik+1)=(βλi−αβ1−αλi)(yikxik)=Rk+1(xi0yi0) \Bigg(\!\!\begin{array}{c} y_{i}^{k+1}\\ x_{i}^{k+1} \end{array}\!\!\Bigg)=\left(\!\!\begin{array}{cc} \beta & \lambda_{i}\\ -\alpha\beta & 1-\alpha\lambda_{i} \end{array}\!\!\right)\left(\!\!\begin{array}{c} y_{i}^{k}\\ x_{i}^{k} \end{array}\!\!\right)=R^{k+1}\left(\!\!\begin{array}{c} x_{i}^{0}\\ y_{i}^{0} \end{array}\!\!\right)
  4. We can write out the convergence rates explicitly. The eigenvalues are σ1=12(1−αλ+β+(−αλ+β+1)2−4β)σ2=12(1−αλ+β−(−αλ+β+1)2−4β) \begin{aligned} \sigma_{1} & =\frac{1}{2}\left(1-\alpha\lambda+\beta+\sqrt{(-\alpha\lambda+\beta+1)^{2}-4\beta}\right)\\[0.6em] \sigma_{2} & =\frac{1}{2}\left(1-\alpha\lambda+\beta-\sqrt{(-\alpha\lambda+\beta+1)^{2}-4\beta}\right) \end{aligned} When the (−αλ+β+1)2−4β<0(-\alpha\lambda+\beta+1)^{2}-4\beta<0 is less than zero, then the roots are complex and the convergence rate is ∣σ1∣=∣σ2∣=(1−αλ+β)2+∣(−αλ+β+1)2−4β∣=2β \begin{aligned} |\sigma_{1}|=|\sigma_{2}| & =\sqrt{(1-\alpha\lambda+\beta)^{2}+|(-\alpha\lambda+\beta+1)^{2}-4\beta|}=2\sqrt{\beta} \end{aligned} Which is, surprisingly, independent of the step-size or the eigenvalue αλ\alpha\lambda. When the roots are real, the convergence rate is max{∣σ1∣,∣σ2∣}=12max{∣1−αλi+β±(1−αλi+β)2−4β∣} \max\{|\sigma_{1}|,|\sigma_{2}|\}=\tfrac{1}{2}\max\left\{ |1-\alpha\lambda_{i}+\beta\pm\sqrt{(1-\alpha\lambda_{i}+\beta)^{2}-4\beta}|\right\}
  5. This can be derived by reducing the inequalities for all 4 + 1 cases in the explicit form of the convergence rate above.
  6. We must optimize over minα,βmax{∥(βλi−αβ1−αλi)∥,…,∥(βλn−αβ1−αλn)∥}. \min_{\alpha,\beta}\max\left\{ \bigg\| \! \left(\begin{array}{cc} \beta & \lambda_{i}\\ -\alpha\beta & 1-\alpha\lambda_{i} \end{array}\right) \! \bigg\|,\ldots,\bigg\| \! \left(\begin{array}{cc} \beta & \lambda_{n}\\ -\alpha\beta & 1-\alpha\lambda_{n} \end{array}\right)\! \bigg\|\right\}. ( ∥⋅∥\|\cdot \| here denotes the magnitude of the maximum eigenvalue), and occurs when the roots of the characteristic polynomial are repeated for the matrices corresponding to the extremal eigenvalues.
  7. The above optimization problem is bounded from below by 00, and vector of all 11’s achieve this.
  8. This can be written explicitly as [LG]ij={degree of vertex ii=j−1i≠j,(i,j) or (j,i)∈E0otherwise [L_{G}]_{ij}=\begin{cases} \text{degree of vertex }i & i=j\\ -1 & i\neq j,(i,j)\text{ or }(j,i)\in E\\ 0 & \text{otherwise} \end{cases}
  9. We use the infinity norm to measure our error, similar results can be derived for the 1 and 2 norms.
  10. The momentum iterations are zk+1=βzk+Awk+error(wk)wk+1=wk−αzk+1. \begin{aligned} z^{k+1}&=\beta z^{k}+ A w^{k} + \text{error}(w^k) \\[0.4em] w^{k+1}&=w^{k}-\alpha z^{k+1}. \end{aligned} which, after a change of variables, become (10α1)(yik+1xik+1)=(βλi01)(yikxik)+(ϵik0) \left(\!\!\begin{array}{cc} 1 & 0\\ \alpha & 1 \end{array}\!\!\right)\Bigg(\!\!\begin{array}{c} y_{i}^{k+1}\\ x_{i}^{k+1} \end{array}\!\!\Bigg)=\left(\!\!\begin{array}{cc} \beta & \lambda_{i}\\ 0 & 1 \end{array}\!\!\right)\left(\!\!\begin{array}{c} y_{i}^{k}\\ x_{i}^{k} \end{array}\!\!\right)+\left(\!\!\begin{array}{c} \epsilon_{i}^{k}\\ 0 \end{array}\!\!\right) Inverting the 2×22 \times 2 matrix on the left, and applying the formula recursively yields the final solution.
  11. On the 1D function f(x)=λ2x2f(x)=\frac{\lambda}{2}x^{2}, the objective value is Ef(xk)=λ2E[(xk)2]=λ2E(e2TRk(y0x0)+ϵke2T∑i=1kRk−i(1−α))2=λ2e2TRk(y0x0)+λ2E(ϵke2T∑i=1kRk−i(1−α))2=λ2e2TRk(y0x0)+λ2E[ϵk]⋅∑i=1k(e2TRk−i(1−α))2=λ2e2TRk(y0x0)+λE[ϵk2⋅∑i=1kγi2,γi=e2TRk−i(1−α) \begin{aligned} \mathbf{E}f(x^{k})&=\frac{\lambda}{2}\mathbf{E}[(x^{k})^{2}]\\&=\frac{\lambda}{2}\mathbf{E}\left(e_{2}^{T}R^{k}\left(\begin{array}{c} y^{0}\\ x^{0} \end{array}\right)+\epsilon^{k}e_{2}^{T}\sum_{i=1}^{k}R^{k-i}\left(\begin{array}{c} 1\\ -\alpha \end{array}\right)\right)^{2}\\&=\frac{\lambda}{2}e_{2}^{T}R^{k}\left(\begin{array}{c} y^{0}\\ x^{0} \end{array}\right)+\frac{\lambda}{2}\mathbf{E}\left(\epsilon^{k}e_{2}^{T}\sum_{i=1}^{k}R^{k-i}\left(\begin{array}{c} 1\\ -\alpha \end{array}\right)\right)^{2}\\&=\frac{\lambda}{2}e_{2}^{T}R^{k}\left(\begin{array}{c} y^{0}\\ x^{0} \end{array}\right)+\frac{\lambda}{2}\mathbf{E}[\epsilon^{k}]\,\cdot\,\sum_{i=1}^{k}\left(e_{2}^{T}R^{k-i}\left(\begin{array}{c} 1\\ -\alpha \end{array}\right)\right)^{2}\\&=\frac{\lambda}{2}e_{2}^{T}R^{k}\left(\begin{array}{c} y^{0}\\ x^{0} \end{array}\right)+\frac{\lambda\mathbf{E}[\epsilon^{k}}{2}\cdot\sum_{i=1}^{k}\gamma_{i}^{2}, \qquad \gamma_i = e_{2}^{T}R^{k-i}\left(\begin{array}{c} 1\\ -\alpha \end{array}\right) \end{aligned} The third inequality uses the fact that Eϵk=0\mathbf{E} \epsilon^k = 0 and the fourth uses the fact they are uncorrelated.

参考文献

  1. On the importance of initialization and momentum in deep learning.  [PDF]
    Sutskever, I., Martens, J., Dahl, G.E. and Hinton, G.E., 2013. ICML (3), Vol 28, pp. 1139—1147.
  2. Some methods of speeding up the convergence of iteration methods  [PDF]
    Polyak, B.T., 1964. USSR Computational Mathematics and Mathematical Physics, Vol 4(5), pp. 1—17. Elsevier. DOI: 10.1016/0041-5553(64)90137-5
  3. Theory of gradient methods
    Rutishauser, H., 1959. Refined iterative methods for computation of the solution and the eigenvalues of self-adjoint boundary value problems, pp. 24—49. Springer. DOI: 10.1007/978-3-0348-7224-9_2
  4. Analysis and design of optimization algorithms via integral quadratic constraints  [PDF]
    Lessard, L., Recht, B. and Packard, A., 2016. SIAM Journal on Optimization, Vol 26(1), pp. 57—95. SIAM.
  5. Introductory lectures on convex optimization: A basic course
    Nesterov, Y., 2013. , Vol 87. Springer Science \& Business Media. DOI: 10.1007/978-1-4419-8853-9
  6. Natural gradient works efficiently in learning  [link]
    Amari, S., 1998. Neural computation, Vol 10(2), pp. 251—276. MIT Press. DOI: 10.1162/089976698300017746
  7. Deep Learning, NIPS′2015 Tutorial  [PDF]
    Hinton, G., Bengio, Y. and LeCun, Y., 2015.
  8. Adaptive restart for accelerated gradient schemes  [PDF]
    O’Donoghue, B. and Candes, E., 2015. Foundations of computational mathematics, Vol 15(3), pp. 715—732. Springer. DOI: 10.1007/s10208-013-9150-3
  9. The Nth Power of a 2x2 Matrix.  [PDF]
    Williams, K., 1992. Mathematics Magazine, Vol 65(5), pp. 336. MAA. DOI: 10.2307/2691246
  10. From Averaging to Acceleration, There is Only a Step-size.  [PDF]
    Flammarion, N. and Bach, F.R., 2015. COLT, pp. 658—695.
  11. On the momentum term in gradient descent learning algorithms  [PDF]
    Qian, N., 1999. Neural networks, Vol 12(1), pp. 145—151. Elsevier. DOI: 10.1016/s0893-6080(98)00116-6
  12. Understanding deep learning requires rethinking generalization  [PDF]
    Zhang, C., Bengio, S., Hardt, M., Recht, B. and Vinyals, O., 2016. arXiv preprint arXiv:1611.03530.
  13. A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights  [PDF]
    Su, W., Boyd, S. and Candes, E., 2014. Advances in Neural Information Processing Systems, pp. 2510—2518.
  14. The Zen of Gradient Descent  [HTML]
    Hardt, M., 2013.
  15. A geometric alternative to Nesterov’s accelerated gradient descent  [PDF]
    Bubeck, S., Lee, Y.T. and Singh, M., 2015. arXiv preprint arXiv:1506.08187.
  16. An optimal first order method based on optimal quadratic averaging  [PDF]
    Drusvyatskiy, D., Fazel, M. and Roy, S., 2016. arXiv preprint arXiv:1604.06543.
  17. Linear coupling: An ultimate unification of gradient and mirror descent  [PDF]
    Allen-Zhu, Z. and Orecchia, L., 2014. arXiv preprint arXiv:1407.1537.
  18. Accelerating the cubic regularization of Newton’s method on convex problems  [PDF]
    Nesterov, Y., 2008. Mathematical Programming, Vol 112(1), pp. 159—181. Springer. DOI: 10.1007/s10107-006-0089-x

更新与更正

View all changes 查看本文自首次发布以来的所有更改。如果你发现错误或想建议修改，请 create an issue on GitHub。

引用与复用

除非另有说明，图表和文本均以 Creative Commons Attribution CC-BY 2.0 许可，source available on GitHub。从其他来源重用的图形不受此许可约束，可在其标题中看到注释："Figure from …"。

在学术语境中引用时，请引用本文为

Goh, "Why Momentum Really Works", Distill, 2017. http://doi.org/10.23915/distill.00006

BibTeX 引用

@article{goh2017why,
  author = {Goh, Gabriel},
  title = {Why Momentum Really Works},
  journal = {Distill},
  year = {2017},
  url = {http://distill.pub/2017/momentum},
  doi = {10.23915/distill.00006}
}
原文：Why Momentum Really Works  ·  作者：Gabriel Goh  ·  中文翻译版