目录
SGD（with Nesterov Acceleration）= NAG
记在前面：本文是Adam那么棒，为什么还对SGD念念不忘 (1)的阅读笔记。
---------------------------------------------------------------------------------------------------------------------------------
优化算法发展回顾：SGD -> SGDM -> NAG ->AdaGrad -> AdaDelta -> Adam -> Nadam
---------------------------------------------------------------------------------------------------------------------------------
--定义：
---------------目标函数：f(w)
---------------优化参数：w
---------------初始学习率：
--迭代优化过程【对每个epoch t】：
---------------1. 计算目标函数关于当前参数wt的梯度：
---------------2. 根据历史梯度计算一阶动量和二阶动量：
---------------3. 计算当前时刻的下降梯度：
---------------4. 根据下降梯度进行更新：
步骤3、4对于各个算法都是一致的，主要的差别就体现在1和2上。
此时，2步骤变为：
，带入3步骤得到：
SGD缺点：下降速度慢，可能会在沟壑的两边持续震荡，停留在一个局部最优点。
梯度下降过程引入惯性，来抑制SGD震荡。
SGD基础上，引入一阶动量：
--------可以认为：这是一个加权求平均的过程，当前时刻的一阶动量等于，经β1加权的前一时刻的一阶动量 与 经（1-β1）加权的当前时刻的梯度。
一阶动量是各个时刻梯度方向的指数移动平均值，约等于最近 1/(1-β1) 个时刻的梯度向量和的平均值。也就是说，t 时刻的下降方向，不仅由当前点的梯度方向决定，而且由此前累积的下降方向决定。
--------原文解释的理解：如下图公式，可以看到，当前t时刻的一阶动量，通过对g1,..,gt所有梯度分布进行指数移动加权得到，也就是“各个时刻梯度方向的指数移动平均值”。
--------即：t时刻的下降方向，由g1, g2, g3, …, gt的梯度方向共同决定。
--------经验值为0.9，这就意味着下降方向即η，主要是此前累积的下降方向，并略微偏向当前时刻的下降方向。想象高速公路上汽车转弯，在高速向前的同时略微偏向，急转弯可是要出事的。
--------例子解释：如下，t=10时，g1…gt的加权值依次增大，即当前t时刻的下降方向主要是此前累积的下降方向，并略微偏向当前时刻的下降方向。
上面截图中,=0.9，改变
=0.8，计算t=10的权重如下，可以看到，此时，
更加偏向当前时刻的下降方向。
SGD的另一个问题：困在局部最优的沟壑里震荡。
需要改进：不能停留在当前位置，要去观察未来的方向，而要向前一步、多看一步、看远一些。
改进方法：在SGD、SGD-M 的基础上的进一步改进，改进点在于步骤 1，改动如下：
再用改动的步骤 1 计算步骤 2 中当前时刻的累积动量。
思想：SGD-M中已知，时刻 t 的主要下降方向由累积动量决定。自己的梯度方向说了也不算，那与其看当前梯度方向，不如先看看如果跟着累积动量走了一步，那个时候再怎么走。
(source: http://cs231n.github.io/neural-networks-3)
SGD及其变种：无二阶动量，以同样的学习率更新每个参数。
二阶动量：可以实现“自适应学习率”。
思想：经常更新的参数，需要学习速度慢一些，稳定些；偶尔更新的参数，需要学习速率大一些，多学点。
二阶动量：可以度量历史更新频率，表示如下，可以解释为以往所有梯度值的平方和，即越大表示经常更新，需要放慢点，越小表示不经常更新，需要放快些：
因为步骤3的下降梯度为：
，因此，此时的实质学习率由α变成了α/Vt
。为避免分母为0，会在分母上加一个小的平滑项。
因此，分母恒大于0，而且参数更新越频繁，二阶动量越大，学习率就越小。
AdaGrad 方法在稀疏数据场景下表现非常好。
缺陷：过于激进。因为
单调递增，学习率会单调递减至0，可能会使训练过程提前结束，即便后续还有数据也无法学到必要的知识。
针对 AdaGrad 过于激进的改进策略：不累积全部历史梯度，而只关注过去一段时间窗口的下降梯度。这也就是 AdaDelta 名称中Delta的来历。
思路：和上述SGD-M思路一样，指数移动平均值大约就是过去一段时间的平均值。从下面公式看到，与SGD-M不一样的是，此处 加权的是
的平方。
这就避免了二阶动量持续累积、导致训练过程提前结束的问题了。
Adam和Nadam：前述方法的集大成者。
-------SGD + 一阶动量 = SGD-M ;
-------SGD + 二阶动量 = AdaGrad / AdaDelta
-------SGD + 一阶动量 + 二阶动量 = Adam = Adaptive + Momentum
其中，SGD-M的一阶动量是：
==【公式1】
-------AdaGrad的二阶动量是：
==【公式2】
【公式1】和【公式2】就是优化算法里面最常见的两个超参数β1和β2。前者控制一阶动量，越大表示对以前积累梯度考虑的越多，越小表示越偏重于当前的梯度下降方向；后者控制二阶动量，同样地，越大表示对以前梯度方向考虑的越多。
β1=0 时 Adam 特例化为 AdaGrad / AdaDelta。
-------SGD + 一阶动量 + 二阶动量 = Adam = Adaptive + Momentum
-------SGD + 一阶动量 + Nesterov +二阶动量 = NAG +二阶动量 = Adam + Nesterov = Nadam
其中，在Adam公式基础上，对步骤1重新计算梯度：
《On the Convergence of Adam and Beyond》，通过反例证明了Adam在某些情况下可能会不收敛。
SGD【没有二阶动量，学习率恒定，但有学习率衰减策略】和AdaGrad【二阶动量不断积累，学习率递减】，因此，这两种方法学习率都会衰减，会最终收敛到0，模型也得已收敛。
但，AdaDelta 和 Adam 因为是固定时间窗口内的累积，随着时间窗口的变化，遇到的数据可能发生巨变，从而Vt会巨变（非单调变化）。从而导致学习率震荡，模型无法收敛。
改进策略：对二阶动量的变化进行控制，避免上下波动。
这样保证了：
，从而学习率单调递减。
相关文章：
《The Marginal Value of Adaptive Gradient Methods in Machine Learning》UC Berkeley。自适应学习率算法可能会对前期出现的特征过拟合，后期才出现的特征很难纠正前期的拟合效果。这个文章给的例子很极端，在实际情况中未必会出现。
《Improving Generalization Performance by Switching from Adam to SGD》CIFAR-10。 试着对Adam的学习率的下界进行控制，发现效果好了很多。
于是，提出了一个用来改进Adam的方法：前期用Adam，享受Adam快速收敛的优势；后期切换到SGD，慢慢寻找最优解。
- 主流的观点认为：Adam等自适应学习率算法对于稀疏数据具有优势，且收敛速度很快；但精调参数的SGD（+Momentum）往往能够取得更好的最终结果。
------于是，有了思考：Adam先粗调，SGD后精调。但，先后中间的时间怎么决定？？
-----回答：Improving Generalization Performance by Switching from Adam to SGD
Adam 下降方向：
SGD下降方向：
解释：因为SGD下降慢，而Adam走得快，因此，SGD下降方向必定可以分解为 Adam下降方向及其正交方向上的两个方向之和。
因此，Adam+ SGD方法走的路==gk黑色线方向+pk蓝色线方向。
------如何确定SGD的学习率？
------SGD（pk蓝色线）在Adam方向上的投影（gk红色线），应该正好等于Adam的下降方向：
，得到
。
-------为了减少噪声影响，使用移动平均值修正对学习率的估计：
这里直接复用了Adam的 beta 参数。
-------何时进行算法的切换？
---------当 SGD的相应学习率的移动平均值基本不变的时候，即
不过，这一时机是不是最优的切换时机，作者并没有给出数学证明，只是通过实验验证了效果，切换时机还是一个很值得深入研究的话题。
- 刚入门，优先考虑：SGD+Nesterov Momentum或者Adam。
- 选择熟悉的算法。
- 充分了解数据。---模型非常稀疏，则优先考虑自适应学习率算法Adam等。
- 根据需求选择。--快速验证，Adam，模型上线或者结果发布前，精调的SGD进行模型的极致优化。
- 先用小数据集实验。有论文研究指出，随机梯度下降算法的收敛速度和数据集的大小的关系不大。（The mathematics of stochastic gradient descent are amazingly independent of the training set size. In particular, the asymptotic SGD convergence rates are independent from the sample size. [2]）因此可以先用一个具有代表性的小数据集进行实验，测试一下最好的优化算法，并通过参数搜索来寻找最优的训练参数。
- 考虑不同算法的组合。先用Adam进行快速下降，而后再换到SGD进行充分的调优。切换策略可以参考本文介绍的方法。
- 数据集一定要充分的打散（shuffle）。这样在使用自适应学习率算法的时候，可以避免某些特征集中出现，而导致的有时学习过度、有时学习不足，使得下降方向出现偏差的问题。
- 训练过程中持续监控训练数据和验证数据上的目标函数值以及精度或者AUC等指标的变化情况。对训练数据的监控是要保证模型进行了充分的训练——下降方向正确，且学习率足够高；对验证数据的监控是为了避免出现过拟合。
- 制定一个合适的学习率衰减策略。可以使用定期衰减策略，比如每过多少个epoch就衰减一次；或者利用精度或者AUC等性能指标来监控，当测试集上的指标不变或者下跌时，就降低学习率。
