Gradient Descent Optimization Algorithms【Advance-Level】

For Ryan_Fan's leanote blog

写在前言

• 本篇笔记是一个学习性总结，其中大部分内容来自网上大牛们的学习资料。
• 如果有涉及到版权问题，请私信~
• 总结一下：
  
  • 自适应学习速率方法的 Gradient Descent Algos: Adagrad、Adadelta、RMSprop、Adam、Nadam、AMSGrad
  • 完全不依赖learning_rate的 Gradient Descent Algos: Adadelta、Nadam

0、需要复习的数学知识

• 进阶的Gradient Descent Algos会相继出现的动力：
  
  1. Entry版Gradient Descent难以选择合适的Learning_Rate；
  2. Entry版Gradient Descent对所有的特征采用相同的Learning_Rate，简直非常的傻；
  3. Entry版Gradient Descent容易收敛到局部最优，并且在某些情况下可能被困在鞍点；
• 进阶的Gradient Descent Algos本质上都是做以下三件事：
  
  1. 避免局部最优；
  2. 避免参数(Learning_Rate)依赖；
  3. 更快收敛；

1、SGD with Momentum

1.1 数学知识

• 大多数情况下，目标函数往往在不同的维度上梯度相差很大（例如稀疏特征和非稀疏特征），比如在下面的函数等高线图中可以看出函数在纵向上要比横向陡峭得多。
• 
• SGD with Momentum 在更新参数的时候，会在一定程度上保留之前更新的方向，同时利用当前batch的梯度微调最终的更新方向。
• 可以在一定程度上增加稳定性，从而学习地更快，并且还有一定摆脱局部最优的能力。 $\Leftrightarrow$ momentum项能够在相关方向加速SGD，抑制振荡，从而加快收敛。
  $v_t = \gamma v_{t-1} + \nabla_\theta J( \theta)$
  $\theta = \theta - \alpha v_t$，$\alpha$为learning_rate。$\gamma$为momentum，表示要在多大程度上保留原来的更新方向。
• 在一次迭代中总的参数更新量包含两个部分：
  
  1. 由上次的更新量得到的$\alpha\gamma v_{t-1}$；
  2. 由本次梯度得到的$\alpha \nabla_\theta J( \theta)$；
• 曾看到一个知乎问题，有知友纠结于以下两种SGD with Momentum的公式形式：
  
  1. $v_t = \gamma v_{t-1} + \nabla_\theta J( \theta),\quad\theta = \theta - \alpha v_t$
  2. $v_t = \gamma v_{t-1} +\alpha \nabla_\theta J( \theta),\quad\theta = \theta - v_t$
  3. 仔细推导一下，就能发现，$\alpha$位置的不同并没有产生任何本质影响：
     
     • learning_rate * Momentum，结果依旧可以认为是Momentum；
     • SGD with Momentum本身不存在learning_rate的decay，所以每一次的迭代的learning_rate是定值，由于Momentum也是定值，故learning_rate * Momentum仍然是定值。

1.2 谈谈理解

• 梯度下降类似滑板少年的那张图：
  
  1. 
  2. 以前的gradient descent都是左右摇摆着前行: 因为在梯度下降算法眼中，这样走是最快的；
  3. 如果盲目把步长调大，只会震荡得更为严重and甚至导致滑板少年飞出去；
• 先验知识:
  
  1. 梯度下降只会朝以下三个方向走：
     
     • 沿-x方向滑行
     • 沿+y方向滑行
     • 沿-y方向滑行
• 后验知识：
  
  1. 当使用了动量后，带来的效果:
     
     • 上沿-y和+y方向的两个力可以相互抵消，
     • 而-x方向的力则会一直加强，
     • 虽然滑板少年会在y方向打转，但是y方向的力量会越来越小，但是他在-x方向的速度会比之前快不少；
• SGD with Momentum的本质理解:
  
  1. 从Momentum的数学表达可以看出，算法希望通过多更新一部分上一次迭代的更新量，来加速这一次的迭代 or 平滑这一次迭代的梯度:
     
     • 当第t轮的梯度$\nabla_\theta J( \theta)$的方向与第t-1次的更新量$v_{t-1}$的方向相同时，上次的更新量能够对本次的迭代搜索起到一个正向加速的作用，即达到“比原先更新迭代的步子更大”的效果。
     • 反之，第t-1次的更新量$v_{t-1}$能够对本次的搜索起到一个减速的作用，即达到“会比原先更新迭代的步子更小”的效果
     • “原先更新”是指原始版SGD or MBGD；
• SGD with Momentum 的效果展示:
  
  1. 
     
     • 从第一行可看出：在learning_rate较小的时候，适当的momentum能够起到一个加速收敛速度的作用。
     • 从第四行可看出：在learning_rate较大的时候，适当的momentum能够起到一个减小收敛时震荡幅度的作用。

1.3 新的问题

当momentum较大时，原本能够正确收敛的时候却因为刹不住车跑过头了。

2、Nesterov Accelerated Gradient(NAG)

2.1 数学知识

• NAG就对Momentum说：“既然我都知道我这一次一定会走$\alpha\gamma v_{t-1}$的量，那么何必还用现在这个位置的梯度呢？直接先走到$\alpha\gamma v_{t-1}$之后的地方，然后根据那里的梯度再前进一下，岂不美哉？”
• 所以就有了如下公式：
  $v_t = \gamma v_{t-1} + \nabla_\theta J( \theta - \alpha \gamma v_{t-1} )$
  $\theta = \theta - \alpha v_t$
• 跟上面Momentum公式的唯一区别在于，梯度不是根据当前参数位置$\theta_{i-1}$，而是根据先走了本来计划（Momentum）要走的一步后，达到的参数位置$\theta_{i-1} - \alpha\gamma v_{t-1}$计算出来的。

2.2 谈谈理解

• 对于NAG相较于Momentum的变化带来的收敛速度的加快的原因：
  
  1. 一些paper给出的解释是：
     
     • 如果前面的梯度比当前位置的梯度大，那么可以把步子迈得比原来大一些；
     • 如果前面的梯度比现在的梯度小，那么可以把步子迈得小一些。
     • 前面的梯度比当前的梯度大，意味着离“最优解”或“局部最优解”还有一段的距离，由于learning_rate是定值，一般设的较小，故为了让步子更大，就要让梯度值变大。
     • 这个大一些、小一些，都是相对于原来不看前方梯度、只看当前位置梯度的情况来说的。
     • 【其实这个解释蛮牵强，因为最多Momentum只是多用了一次迭代，不太可能会有明显的收敛速度差异。】
  2. 知友给出的解释是：
     
     • 在原始形式中，Nesterov Accelerated Gradient（NAG）算法相对于Momentum的改进在于，以“向前看”看到的梯度而不是当前位置梯度去更新。
     • 经过变换之后的等效形式中，NAG算法相对于Momentum多了一个本次梯度相对上次梯度的变化量，这个变化量本质上是对目标函数二阶导的近似。
     • 由于利用了二阶导的信息，NAG算法才会比Momentum具有更快的收敛速度。
     • 参考文献：https://zhuanlan.zhihu.com/p/22810533
• NAG和Momentum的区别：
  
  1. 
  2. Momentum首先计算一个梯度(短的蓝色向量)，然后在加速更新梯度的方向进行一个大的跳跃(长的蓝色向量)，nesterov项首先在之前加速的梯度方向进行一个大的跳跃(棕色向量)，计算梯度然后进行校正(绿色梯向量)

2.3 新的问题

希望每个单独的参数能够自适应各自的变化频率，比如稀疏特征采用高的更新速率，其他特征采用相对较低的更新速率。

3、Adagrad

3.1 数学知识

• 与梯度下降不同的是，更新规则中，对于learning_rate不在设置固定的值，每次迭代过程中，每个参数优化时使用不同的learning_rate。 具体而言，是对learning_rate进行了一个约束，即：
  $n_t = n_{t-1}+g_t^2$
  $\theta = \theta - \frac{\alpha}{\sqrt{n_t + \epsilon}} \ast g_t$
  对$g_t$从1到t进行一个递推形成一个约束项regularizer，$-\frac{1}{\sqrt{\sum\limits_{r=1}^t(g_r)^2 + \epsilon}}$，其中$\epsilon$用来保证分母非0。
• Adagrad有如下特点：
  
  1. 前期$g_t$较小的时候，regularizer较大，能够放大前进步子；
  2. 后期$g_t$较大的时候，regularizer较小，能够约束前进步子；
  3. 适合处理稀疏梯度；
  4. 【Gradient Descent最理想化的下降方式是：每一次迭代前进的步长是差不多的，是一种稳定的前进姿态。故当梯度小时应增大learning_rate，在梯度大时应减小learning_rate。】

3.2 谈谈理解

• Adagrad的更新规则中，learning_rate会随着每次迭代而根据历史梯度的变化而变化，这是它的优势，优势的具体表现是更加适合处理稀疏梯度，如何处理:
  
  1. 对稀疏特征，给予一个较大的learning_rate，使其得到大的学习更新，避免halting(早停)；
  2. 对非稀疏特征，给予一个较小的learning_rate，使其得到较小的学习更新，避免overshooting(步子迈过头);
  3. 可以得到一个推论: 特征越稀疏，梯度值越小，Adagrad会给予它们一个更大的learning_rate；
  4. 提醒一个知识点：Gradient Descent的停止迭代条件:
     
     • 超过迭代次数;
     • 当两次迭代之间的差值小于该阈值时，迭代结束；（解释了为什么系数特征容易出现早停。）
• Adagrad 算法最大的特点是将历史梯度 L2 范数的倒数作为缩放learning_rate的因子。
• 只要regular item里有平方和的1/2次方，都可以视为是L2范数？
• 为什么分母要进行平方根的原因是去掉平方根操作算法的表现会大打折扣？
  
  1. 如果去掉了平方根，那么learning_rate下降的速度会非常快，导致更新能力会越来越弱，能学到的更多知识的能力也越来越弱。
• 劣势：
  
  1. 分母项的对梯度平方不断累积，随之时间步地增加，分母项越来越大，最终导致learning_rate收缩到太小无法进行有效更新。

3.3 新的问题

• 虽然Adagrad 在稀疏梯度的情况下工作良好，但仍有如下问题：
  
  1. 但由于在更新中使用了所有的历史梯度信息，导致算法在loss function非凸和梯度比较密集的情况下会引起learning_rate的快速衰减。
  2. learning_rate骤减 <=> 学习到后来的阶段，网络的更新能力会越来越弱，能学到的更多知识的能力也越来越弱，因为learning_rate会变得很小

4、Adadelta

4.1 数学知识

• 梯度和是递归的定义成历史梯度平方的衰减平均值，即$E[g^2]_t$；
• $E[g^2_t]$仅仅取决于当前的梯度值与上一时刻的平均值：
  
  1. $E[g^2]_t = \gamma E[g^2]_{t-1} +(1-\gamma)g^2_t$；
  2. $\gamma$类似于Momentum；
• 回顾Adagrad，参数更新的形式：$\triangle\theta_t = - \frac{\alpha}{\sqrt{\sum\limits_{r=1}^t(g_r)^2+\epsilon}}\ast g_{t}$
• 而Adadelta用$E[g^2]_t$代替$\sum\limits_{r=1}^t(g_r)^2$：$\triangle\theta_t = - \frac{\eta}{\sqrt{E[g^2]_{t} +\epsilon}}\ast g_{t}$
• 将分母简记为RMS，表示梯度的均方根误差：$\triangle\theta_t = - \frac{\eta}{RMS[g]_t}g_t$
• 用$RMS[\triangle\theta]_{t-1}$代替learning_rate，$E[\triangle\theta_t^2]_t = \gamma E[\triangle\theta_t^2]_{t-1} +(1-\gamma)\triangle\theta_t^2$
• 得到Adadelta更新规则：
  $\theta = \theta - \frac{RMS[\triangle\theta]_{t-1}}{RMS[g]_t}g_t$
• 至此可以发现，Adadelta不需要设定缺省learning_rate，更新规则已经不受learning_rate影响。

4.2 谈谈理解

• 本质上，Adadelta是利用“梯度的二阶矩估计”和“参数的二阶矩估计”来优化Gradient Descent：
  
  1. 使用“梯度的二阶矩估计”来限制learning_rate的快速decay；
  2. 使用“参数的二阶矩估计”来摆脱learning_rate的参数依赖；
  3. 梯度的二阶矩估计（Second Moment Estimation，即梯度的未中心化的方差）：$E[g^2]_t = \gamma E[g^2]_{t-1} +(1-\gamma)g^2_t$，如果不好看懂，把$E[g^2]_t$换成$v_t$就一目了然了。
  4. 参数的二阶矩估计：$E[\triangle\theta^2]_t = \gamma E[\triangle\theta^2]_{t-1} +(1-\gamma)\triangle\theta^2_t$
• 优点：
  
  1. 训练初中期，加速效果不错，很快。（为什么快？因为用了二阶导的信息）
• 缺点：
  
  1. 训练后期，反复在局部最小值附近抖动。

5、RMSProp

5.1 一笔带过的Summary:

• 和Adagrad相比，多了一个：用“梯度平方的期望（梯度的二阶矩估计）”代替“梯度平方的累加和的开方”作为learning_rate的约束项；
• 和Adadelata相比，少了一个：继续使用learning_rate这个参数；

6、Adam(Adaptive Moment Estimation，自适应矩估计)

6.1 数学知识

• Adam根据loss function对梯度的一阶矩估计（First Moment Estimation，即梯度的均值）和二阶矩估计（Second Moment Estimation，即梯度的未中心化的方差）进行综合考虑，来动态调整针对于每个参数的学习步长(learning_rate * 更新步长)。并且每次迭代参数的学习步长都有一个确定的范围，不会因为很大的梯度导致很大的学习步长，参数的值比较稳定；
• 值得一提的是：在Adam中，单个权重的更新规则是将其梯度与当前和过去梯度的 L^2 范数（二阶矩）成反比例缩放。
• Adam的计算策略：
  
  1. $m_t = \beta_1 m_{t-1} + (1 - \beta_1) g_t$
  2. $v_t = \beta_2 v_{t-1} + (1 - \beta_2) g_t^2$
  3. $\hat{m}_t = \dfrac{m_t}{1 - \beta^t_1}$
  4. $\hat{v}_t = \dfrac{v_t}{1 - \beta^t_2}$
  5. $\theta = \theta - \dfrac{\alpha}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t$
• 参数解释：
  
  1. $m_t$和$n_t$分别是对梯度的一阶矩估计和二阶矩估计；
  2. 由于$m_0$和$n_0$初始化为0，会导致$m_t$和$n_t$偏向于0，尤其在训练初期阶段。所以需要对梯度均值$m_t$和$n_t$进行偏差纠正，降低偏差对训练初期的影响，即$\hat{m_t}$和$\hat{n_t}$。
  3. 由表达式可以看出，对更新的步长计算，能够从梯度均值（一阶矩）及梯度平方（二阶矩）两个角度进行自适应地调节，而不是直接由当前梯度决定。

6.2 谈谈理解

• 关于“矩估计”的数学知识：
  
  1. 如果一个随机变量 X 服从某个分布，X 的一阶矩是 E(X)，也就是样本均值，即期望。X 的二阶矩就是 E(X^2)，也就是样本平方的均值，即方差；
  2. 详情参见【荆哲】知友的回答，非常棒：https://www.zhihu.com/question/23236070/answer/143316942
• 为什么Adam可以看作是对梯度的一阶矩估计和二阶矩估计进行综合考虑，并计算出更新步长的？
  
  1. Adam是利用指数递减规律对一阶矩和二阶矩进行加权运算，是为了有效解决历史数据时间越久对现在影响越小的问题。
  2. 因此，Adam中关于一阶矩和二阶矩的计算公式和一般的一阶矩（期望）和二阶矩（方差）的计算公式不一样！！！
  3. 基于此，才有：Adam对更新的步长计算，能够从梯度均值及梯度平方两个角度进行自适应地调节
• 关于$\beta_1$ 和 $\beta_2$的作用：
  
  1. 首先要清楚，Adam中矩的计算等价于EWMA(Exponentially Weighted Moving Average，指数加权移动平均) 详见：https://blog.csdn.net/x_i_y_u_e/article/details/44194761
     
     • $\lambda$代表EWMA对于历史量测值之权重系数﹐其值越接近1，表对过去量测值的权重较低。$\Leftrightarrow$ $\lambda$决定EWMA估计器跟踪实际数据突然发生变化的能力，即时效性,随着λ增大，估计器的时效性就越强，反之，越弱;
     • 由于 $\lambda$的存在，EWMA还表现出一定的吸收瞬时突发的能力，这种能力称为平稳性。随着 $\lambda$减小，估计器的平稳性增强，反之降低。
     • 从概率角度看，EWMA是一种理想的最大似然估计技术，它采用一个权重因子 $\lambda$对数据进行估计，当前估计值由前一次估计值和当前的抽样值共同决定;
  2. Adam 中关于beta_1 和 beta_2的物理意义和$\lambda$刚好相反，因为它们和$\lambda$所处的位置刚好。
• 优点：
  
  1. 实现简单，计算高效，对内存需求少；
  2. 参数的更新不受梯度的伸缩变换影响；
  3. 超参数具有很好的解释性，且通常无需调整或仅需很少的微调；
  4. 更新的步长能够被限制在大致的范围内（初始learning_rate）；
  5. 能自然地实现步长退火过程（自动调整learning_rate）；
  6. 很适合应用于大规模的数据及参数的场景；
  7. 适用于不稳定目标函数；
  8. 适用于梯度稀疏或梯度存在很大噪声的问题；

7、Adamax

7.1 一笔带过的Summary:

• Adamax是Adam的一种变体，此方法对learning_rate的上限提供了一个更简单的范围。公式上的变化如下：
  $u_t = \beta_2^\infty v_{t-1} + (1 - \beta_2^\infty) |g_t|^\infty = \max(\beta_2 \cdot v_{t-1}, |g_t|)$
  $\theta = \theta - \dfrac{\eta}{u_t} \hat{m}_t$
• 可以看出，Adamax对learning_rate的边界范围的限定更为简单。
• Adamax的地位远不及Adam和Nadam, So此处做一个了解就好！！！~~

8、Nadam

8.1 一笔带过的Summary:

• Nadam对learning_rate有了更强的约束, 同时对梯度的更新也有更直接的影响。
• 一般而言, 在想使用带动量的RMSprop, 或者Adam的地方, 大多可以使用Nadam取得更好的效果。
• 算法流程：
• 

9、AMSGrad

9.1 数学原理

• 在 Adam 算法收敛到次优解的过程中，它已经观察到一些小批量数据提供了大量且具有信息的梯度，但是由于这些小批量数据发生地非常少，指数平均将降低它们的影响，这也就造成了 Adam 只能收敛到次优的极小值点。如下图所示：
• 
• 为了解决这个问题，AMSGrad使用过去梯度平方的最大值以替代指数平均值来更新参数
• AMSGrad的计算策略：（此处带上了偏差修正估计）
  
  1. $m_t=\beta_1 m_{t-1}+(1-\beta_1)g_t$
  2. $v_t=\beta_2 v_{t-1}+(1-\beta_2)g_t^2$
  3. $\hat{v}_t = \max(\hat{v}_{t-1}, v_t)$
  4. $\tilde{m}_t = \frac{m_t}{1-\beta_1^t}$
  5. $\tilde{v}_t = \frac{\hat{v}_t}{1-\beta_2^t}$
  6. $\theta=\theta-\frac{\alpha}{\sqrt{\tilde{v}_t}+\epsilon} \ast \tilde{m}_t$

9.2 谈谈理解

• AMSGrad算法其实很直接：既然Adam的劣势是指数平均会降低小批量数据重要性，那么就用max()来判断当前是进行指数平均还是保留之前的梯度。

10、Which optimizer to choose?

参考文献：http://ruder.io/optimizing-gradient-descent/index.html#whichoptimizertochoose
- If your input data is sparse, then you likely achieve the best results using one of the adaptive learning-rate methods. An additional benefit is that you won't need to tune the learning rate but likely achieve the best results with the default value.
💡：稀疏特征空间，建议使用自适应的learning_rate相关的Optimizer。
- In summary, RMSprop is an extension of Adagrad that deals with its radically diminishing learning rates. It is identical to Adadelta, except that Adadelta uses the RMS of parameter updates in the numinator update rule. Adam, finally, adds bias-correction and momentum to RMSprop. Insofar, RMSprop, Adadelta, and Adam are very similar algorithms that do well in similar circumstances. Kingma et al. [15] show that its bias-correction helps Adam slightly outperform RMSprop towards the end of optimization as gradients become sparser. Insofar, Adam might be the best overall choice.
💡：RMSprop, Adadelta, and Adam属于同一类的Optimizer，在相似的环境下，它们的表现比较相近。但是Kingma证明了Adam Optimizer算法对一阶矩估计和二阶矩估计的修正，对寻找最优解有slightly的提升。Insofar（基于此），Adam might be the best overall choice。
- Interestingly, many recent papers use vanilla SGD(普通的SGD) without momentum and a simple learning rate annealing schedule(退火算法). As has been shown, SGD usually achieves to find a minimum, but it might take significantly longer than with some of the optimizers, is much more reliant on a robust initialization and annealing schedule, and may get stuck in saddle points rather than local minima. Consequently, if you care about fast convergence and train a deep or complex neural network, you should choose one of the adaptive learning rate methods.
💡：很多Paper只是用最基本的SGD + 退火算法来进行梯度下降，但是SGD有着明显的缺陷：在寻找最优解的过程中用时长（因为在解空间的搜索过程很盲目），所以它非常依赖于参数初始化和退火算法的效果。并且SGD很容易被困在鞍点出不来进而将鞍点作为最优解输出。如果对收敛效率要求比较高，比如复杂的深度学习网络，选择一个自适应的learning_rate会是一个大概率不错的选择。

11、Make Gradient Descent's work better

• 在【Entry-Level】中提到了“well-conditioned”的含义：函数中的梯度最大变化速度 / 函数中的梯度最小变化速度。
• 对于Gradient Descent 算法，如果是well-conditioned，即“函数中的梯度最大变化速度 / 函数中的梯度最小变化速度”比较小，那么整个优化过程是相对平稳，收敛速度也会相对较快，也更有可能收敛到最优解。
• But现实总是残酷的，大多数情况下，特征空间都是ill-conditioned，这个时候会导致什么问题呢？
• 
• 如果feature的scale相差很大，则会出现scale越大的feature，对模型的影响越大。比如对于multivariate regression, 极端情况下, 有一个特征的值特别特别大，其他特征的值都特别特别小，那么cost function就被这个特别大的特征主导，甚至退化为univariate。即使使用自适应的learning_rate，也不能保证优化过程的是平稳的。（鬼知道scale的相差程度是否会大于自适应learning_rate算法带来的benefit呢）
• 这个时候就需要做“归一化”。归一化的目的是把最大和最小的特征值差距拉进，这也是sebastian ruder在blog中提到的“初始化对梯度下降的影响”。具体而言：gradient[j] += (y[i] - predict_y) * samples[i][j]。如果不归一化，scale越大的s[i][j]，对模型的影响越大，这本身是不公平的，也会对求解过程带来障碍。归一化后的Gradient Descent效果会是这样：
• 

12、☻ 引出后面要学习的Point

• Gradient Descent对初始化敏感，即需要进行适当的归一化处理。
• 而Newton's method优于gradient descent的一个方面：Newton's method是affine invariant的，就是收敛速度不受坐标系变换影响。