关于神经网络一阶优化算法，网上已经有很多资料了，本文为笔者很久之前做的一份梳理，整理了一下一些popular的一阶优化算法及他们的逻辑线，优缺点等。读者自行甄别，自取所需，大神直接过即可。

Notations

$\theta$ : parameters

$J$ : objective function

$\nabla J(\theta) = J’$ w.r.t parameter

$\eta$ : learning rate

从SGD说起

SGD(Stochastic Gradient Descent)是目前最流行的机器学习，深度学习优化算法之一，现在通常所说的SGD指的是Mini-batch gradient descent，更新规则如下，

$$\theta_{t+1} = \theta_{t} - \eta \nabla J(\theta_{t}; x_{i:i+m}; y_{i:i+m})$$

每次采用一小批数据计算梯度来更新paramter，既能够缓解每次单个样本的SGD带来的剧烈波动问题，又能够加快训练速度，所以受到了machine learning和neural network训练的喜爱。

但是SGD有如下几个不足[1]：
1）learning rate很难选取
2）schedule策略需要预先选定，无法自适应
3）参数的每一维使用相同的学习率
4）SGD在鞍点或者pleatu区域容易陷入困境，难以逃离

根据这些不足，人们设计了许多SGD的改进算法。

Momentum

为了加速SGD的训练，以及改善面对“峡谷”型目标函数的鲁棒性，人们将物理学中的Momentum概念加入优化中。实验证明，Momentum SGD[2]能够有效地抑制函数值震荡的现象。
Momentum的更新公式如下：

$v_t = \rho v_{t-1} + \eta \nabla J(\theta)$

$\theta = \theta - v_t$

where $\rho$ 控制着前面诸参数更新的衰减率。
有了Momentum，SGD能够收敛的更快，并且震荡会减弱。

Nesterov Accelerated Gradient(NAG)

接着，Nesterov提出了一种无约束凸优化方法，称为Nesterov accelerated gradient(NAG)[3]，这种方法预先估计下一个位置，然后看看该位置的梯度，根据对该“未来”梯度的判断，来调整自己的预期步长，使得更加智能的往局部最优点走去。NAG的更新式与Momentum只有一丝细微的差别：

$v_t = \rho v_{t-1} + \eta \nabla J(\theta-\rho v_{t-1})$

$\theta = \theta - v_t$

Adagrad

虽然我们对SGD进行了加速，并且非常智能地调整好了方向，我们的参数向量各个维度更新幅度仍然是一样的，（在有些时候，尤其是稀疏场景中，对于出现极少次数的特征维，我们不会想只更新一个很小的幅度，这样会使得这个维度学习很差。）

另一种思路是使得参数向量$\theta$的各个维以不同步调来差异化地调整。
Adagrad就是其中一种，由Duchi et. al[4]在2011年提出。Ada means Adaptive，代表着它能够自适应地为参数调整学习率，非常适合稀疏数据，这种方法将梯度平方的累积值加入梯度更新中，更新方式如下：

$g_{t,i} = \nabla J(\theta_i)$

$\theta_{t+1, i} = \theta_{t, i} - \frac {\eta} {\sqrt{G_{t,ii} + \epsilon}} \cdot g_{t,i}$

$G_t \in {\mathbb R}^{d \times d}$ is a diagonal matrix that each diagonal element is sum of the squares of the gradient w.r.t $w_i$ up to time step t [4].
$\epsilon$ is just a smoothing term avoiding division by zero, usually 1e-8.
我们也可以写成向量形式：
$$\theta_{t+1} = \theta_{t} - \frac {\eta} {\sqrt{G_{t} + \epsilon}} \odot g_{t}$$
$\odot$ means element-wise matrix-vector multiplication.

RMSprop

随着梯度平方的累积，Adagrad会自适应地降低频繁更新的参数的学习率，使得你无需去手动指定learning rate schedule策略来调试学习率，但是Adagrad的一大缺点就是它的学习率会随着训练中不断增长的累计梯度平方和而单调下降到任意小，甚至导致学习的停滞。

RMSprop[5]和Adadelta[6]是提出来解决上述Adagrad学习率降到任意小问题的，RMSprop的基本思想是，instead of 除以所有梯度平方的累积，RMSprop将学习率除以梯度平方的指数衰减平均$E[g^2]$，梯度平方的指数衰减平均$E[g^2]$可以表示前w个平方梯度的累积，又避免了直接存储前w个平方梯度的存储开销，这样能够有效防止无限小的，单调下降的，diminishing的learning rate问题，RMSprop更新规则如下：
$g_t$代表time step t时刻的梯度向量。

$E[g^2]_t = \rho E[g^2]_{t-1} + (1-\rho)g_t^2 $

$\theta_{t+1} = \theta_t - \frac {\eta} {\sqrt{E[g^2]_t + \epsilon}} \cdot g_{t,i} = \theta_t - \frac {\eta} {RMS[g]_t} \cdot g_{t,i}$

Adadelta

Adadelta[6]为与RMSprop几乎同一时间提出来的，可以看做在RMSprop的基础上做了进一步的改进的版本。其与RMSprop的关键区别就在于Adadelta统一了$\Delta \theta$与$\theta$的单位(unit)。
作者指出，在原来的$$\Delta \theta = - \frac {\eta} {\sqrt{E[g^2]_t + \epsilon}} \cdot g_{t,i}$$中，$\Delta \theta$的单位与$\theta$是不匹配的，在SGD，Momentum或者Adagrad中也是如此，所以Adadelta通过引入$\Delta \theta^2$的指数衰减平均，来使得单位统一。故Adadelta的更新式为：
$E[g^2]_t = \rho E[g^2]_{t-1} + (1-\rho)g_t^2$

$\theta_{t+1} = \theta_t - \frac {\sqrt {E[\Delta \theta^2]_{t-1} + \epsilon}} {\sqrt{E[g^2]_t + \epsilon}} \cdot g_t$

$E[\Delta \theta^2]_t = \rho E[\Delta \theta^2]_{t-1} + (1-\rho)\Delta \theta_t^2$

where $\rho$ 是类似于Momentum中的衰减率常数。
Adadelta有两个重要的优点，1) 解决了学习率随着训练持续减小的问题 2) 无需预先设置学习率超参
[6]指出，在MNIST数据集上，Adadelta的参数敏感性好于SGD,Momentum和Adagrad等算法。

Adam

另一个现在用的较多的自适应学习率方法是Adam(Adaptive Moment Estimation)[7]，Adam结合了RMSprop和Momentum的思想，不过Adam不仅维护过去一阶梯度的指数衰减平均$m_t$(exponentially decaying average of past gradients)，而且还维护二阶梯度的指数衰减平均$v_t$，并且加入了bias-correction步骤，以纠正$m_t, v_t$初始化为0带来的偏差(bias)，由是可得到Adam的更新规则如下：

$m_t = \beta_1 m_{t-1} + (1-\beta_1)g_t $

$v_t = \beta_2 v_{t-1} + (1-\beta_2)g_t^2 $

$\hat{m}_t = \frac {m_t} {1-\beta_1^t} $

$\hat{v}_t = \frac {v_t} {1-\beta_2^t}$

$\theta_{t+1} = \theta_t - \frac {\eta} {\sqrt{\hat{v}_t} + \epsilon} \cdot \hat{m}_t $

where $\beta_1, \beta_2$ is exponential decay rates of moment estimates.
[7]中推荐参数设置为$\eta = 0.001, \beta_1 = 0.9, \beta_2 = 0.999 \
and \ \epsilon = 1e-8$

Actually, Adam algorithm works well in practice, not only in acedemia but industry. Empirical results show that Adam consistantly outperforms other methods for a variety of models and datasets, and it’s a versatile algorithm that scales to large-scale high-dimensional machine learning problems.

Optimization Algorithms Relationship

References

[1] Sebastian Ruder. An overview of gradient descent optimization algorithms
[2] Ning Qian. On the Momentum Term in Gradient Descent Learning Algorithms
[3] Y. Nestrov. A method of solving a convex programming problem with convergence rate O (1/k2)
[4] John Duchi et.al. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization
[5] Geoffrey Hinton et.al Lecture 6. RMSprop
[6] Matthew D. Zeiler. ADADELTA: AN ADAPTIVE LEARNING RATE METHOD
[7] Diederik P. Kingma et.al. ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION