Momentum

• 目标函数有关自变量的梯度代表了目标函数在自变量当前位置下降最快的方向。
  • 因此，梯度下降也叫作最陡下降（steepest descent）。
• 在每次迭代中，梯度下降根据自变量当前位置，沿着当前位置的梯度更新自变量。

• 然而，如果自变量的迭代方向仅仅取决于自变量当前位置，这可能会带来一些问题。

  An ill-conditioned Problem

  Condition Number of Hessian Matrix:
  
  where λmax,λmin is the maximum amd minimum eignvalue of Hessian matrix.
  让我们考虑一个输入和输出分别为二维向量x=[x1,x2]⊤和标量的目标函数:
  f(x)=0.1x12+2x22
  condH=40.2=20→ill-conditioned

• Condition number如果过大的话，表明函数在不同维度的梯度差别比较大

• 

  • 可以看到，同一位置上，目标函数在竖直方向（x2轴方向）比在水平方向（x1轴方向）的斜率的绝对值更大。因此，给定学习率，梯度下降迭代自变量时会使自变量在竖直方向比在水平方向移动幅度更大。那么，我们需要一个较小的学习率从而避免自变量在竖直方向上越过目标函数最优解。然而，这会造成自变量在水平方向上朝最优解移动变慢。

    Supp: Preconditioning

    在二阶优化中，我们使用Hessian matrix的逆矩阵(或者pseudo inverse)来左乘梯度向量，这样的做法称为precondition，相当于将 H 映射为一个单位矩阵，拥有分布均匀的Spectrum，也即我们去优化的等价标函数的Hessian matrix为良好的identity matrix。

    Solution to ill-condition

• Preconditioning gradient vector: applied in Adam, RMSProp, AdaGrad, Adelta, KFC, Natural gradient and other secord-order optimization algorithms.

• Averaging history gradient: like momentum, which allows larger learning rates to accelerate convergence; applied in Adam, RMSProp, SGD momentum.

  Momentum Algorithm

• 动量法的提出是为了解决梯度下降的上述问题。

• 设时间步 t 的自变量为 xt，学习率为 ηt。 在时间步 t=0，动量法创建速度变量 m0，并将其元素初始化成 0。在时间步 t>0，动量法对每次迭代的步骤做如下修改：

• Another version:

• 其中，动量超参数 β满足 0≤β<1。当 β=0 时，动量法等价于小批量随机梯度下降。

  Exponential Moving Average（exponential moving average）

• 给定超参数 0≤β<1，当前时间步 t 的变量 yt 是上一时间步 t−1 的变量 yt−1 和当前时间步另一变量 xt 的线性组合：

yt=βyt−1+(1−β)xt.

• 我们可以对 yt 展开：

由指数加权移动平均理解动量法

• 现在，我们对动量法的速度变量做变形：

• Another version:

• 由指数加权移动平均的形式可得，速度变量 vt 实际上对序列 {ηt−igt−i/(1−β):i=0,…,1/(1−β)−1} 做了指数加权移动平均。
• 换句话说，相比于小批量随机梯度下降，动量法在每个时间步的自变量更新量近似于将前者对应的最近 1/(1−β) 个时间步的更新量做了指数加权移动平均后再除以 1−β。
  • 需要根据近似步数相应调整学习率

• 所以，在动量法中，自变量在各个方向上的移动幅度不仅取决当前梯度，还取决于过去的各个梯度在各个方向上是否一致。

  AdaGrad

• 在之前介绍过的优化算法中，目标函数自变量的每一个元素在相同时间步都使用同一个学习率来自我迭代。

• 在前一节里我们看到当x1和x2的梯度值有较大差别时，需要选择足够小的学习率使得自变量在梯度值较大的维度上不发散。
• 但这样会导致自变量在梯度值较小的维度上迭代过慢。
• 动量法依赖指数加权移动平均使得自变量的更新方向更加一致，从而降低发散的可能。

• 本节我们介绍AdaGrad算法，它根据自变量在每个维度的梯度值的大小来调整各个维度上的学习率，从而避免统一的学习率难以适应所有维度的问题。

  Algorithm

• AdaGrad算法会使用一个小批量随机梯度gt按元素平方的累加变量st。

• 在时间步0，AdaGrad将s0中每个元素初始化为0。在时间步t，首先将小批量随机梯度gt按元素平方后累加到变量st：

st←st−1+gt⊙gt,

• 其中⊙是按元素相乘。
  • 接着，我们将目标函数自变量中每个元素的学习率通过按元素运算重新调整一下：

xt←xt−1−ηst+ϵ⊙gt,

• 其中η是学习率，ϵ是为了维持数值稳定性而添加的常数，如10−6。
  • 这里开方、除法和乘法的运算都是按元素运算的，使得目标函数自变量中每个元素都分别拥有自己的学习率。

    Feature

• 小批量随机梯度按元素平方的累加变量st出现在学习率的分母项中。
• 因此，如果目标函数有关自变量中某个元素的偏导数一直都较大，那么该元素的学习率将下降较快；反之，如果目标函数有关自变量中某个元素的偏导数一直都较小，那么该元素的学习率将下降较慢。

• 然而，由于st一直在累加按元素平方的梯度，自变量中每个元素的学习率在迭代过程中一直在降低（或不变）。所以，当学习率在迭代早期降得较快且当前解依然不佳时，AdaGrad算法在迭代后期由于学习率过小，可能较难找到一个有用的解。

  RMSProp

  为了解决AdaGrad后期学习率过小的问题

  Algorithm

• 不同于AdaGrad算法里状态变量st是截至时间步t所有小批量随机梯度gt按元素平方和，RMSProp算法将这些梯度按元素平方做指数加权移动平均。

• 具体来说，给定超参数0≤γ0计算

• 和AdaGrad算法一样，RMSProp算法将目标函数自变量中每个元素的学习率通过按元素运算重新调整，然后更新自变量

• 其中η是学习率，ϵ是为了维持数值稳定性而添加的常数，如10−6。
  • 因为RMSProp算法的状态变量st是对平方项gt⊙gt的指数加权移动平均，所以可以看作是最近1/(1−β)个时间步的小批量随机梯度平方项的加权平均。
  • 如此一来，自变量每个元素的学习率在迭代过程中就不再一直降低（或不变）。

    AdaDelta

    同样是解决AdaGrad的问题，有趣的是取消了学习率这一参数

    Algorithm

• AdaDelta算法也像RMSProp算法一样，使用了小批量随机梯度gt按元素平方的指数加权移动平均变量st。
• 在时间步0，它的所有元素被初始化为0。给定超参数0≤ρ0，同RMSProp算法一样计算

st←ρst−1+(1−ρ)gt⊙gt.

• 与RMSProp算法不同的是，AdaDelta算法还维护一个额外的状态变量Δxt，其元素同样在时间步0时被初始化为0。我们使用Δxt−1来计算自变量的变化量：

• 其中ϵ是为了维持数值稳定性而添加的常数，如10−5。
• 对反向传播得到的梯度按照历史记录进行scale
  • 接着更新自变量：

xt←xt−1 − gt′.

• 最后，我们使用Δxt来记录自变量变化量gt′按元素平方的指数加权移动平均：

Δxt←ρΔxt−1+(1−ρ)gt′⊙gt′.

• 可以看到，如不考虑ϵ的影响，AdaDelta算法与RMSProp算法的不同之处在于使用Δxt−1来替代超参数η。

  Adam

  结合了RMSProp和动量

  Algorithm

• 给定超参数0≤β1<1（算法作者建议设为0.9），时间步t的动量变量mt即小批量随机梯度gt的指数加权移动平均：

• 和RMSProp算法中一样，给定超参数0≤β2<1（算法作者建议设为0.999）， 将小批量随机梯度按元素平方后的项gt⊙gt做指数加权移动平均得到vt：

• 由于我们将m0和s0中的元素都初始化为0， 在时间步t我们得到。将过去各时间步小批量随机梯度的权值相加，得到 。需要注意的是，当t较小时，过去各时间步小批量随机梯度权值之和会较小。例如，当β1=0.9时，m1=0.1g1。为了消除这样的影响，对于任意时间步t，我们可以将mt再除以，从而使过去各时间步小批量随机梯度权值之和为1。这也叫作偏差修正。在Adam算法中，我们对变量mt和vt均作偏差修正：

• 接下来，Adam算法使用以上偏差修正后的变量m^t和m^t，将模型参数中每个元素的学习率通过按元素运算重新调整：

• 其中η是学习率，ϵ是为了维持数值稳定性而添加的常数，如10−8。
  • 和AdaGrad算法、RMSProp算法以及AdaDelta算法一样，目标函数自变量中每个元素都分别拥有自己的学习率。最后，使用gt′迭代自变量：