随机梯度下降及其变种的综述
随机梯度算法作为重要的一阶优化算法，每次采用小部分样本进行梯度的更新，迭代速度比较快。在随机梯度算法的基础上，为了选择合适的学习率，出现动量法与自适应学习率算法。为了更好的学习稀疏特征，随机梯度下降算法融合RDA以及FOBOS形成FTRL算法。由于随机梯度下降算法每次采用部分样本进行梯度计算，引入较大的方差，因此提出减少方差的随机梯度算法svrg以及sag算法。本文将从随机梯度下降算法开始，并对其变种算法分别进行讲解以及实验。
本文的试验集采用https://www.csie.ntu.edu.tw/~f01922139/libffm_data/libffm_toy.zip，batch_size为100。代码位于https://github.com/summersunshine1/optimize。
1、随机梯度下降算法
传统的随机梯度下降算法每次采用部分样本计算梯度，来更新参数，代码详见仓库下的sparsesgd.py。
实验auc与loss变化如下：
2、FTRL算法
稀疏性不仅为了特征选择，同时可以降低计算量。产生稀疏性可以采用多种方法，最常采用的是l1正则。由于批量算法采用l1正则时，沿着全局梯度下降方向进行参数的更新，因此可以产生有效的稀疏性。而随机梯度下降算法由于采用部分样本进行梯度更新，不一定按全局梯度下降方向下降，因此一般不能产生稀疏性。代码见svrg.py。
随机梯度下降算法产生稀疏性的算法主要包括TG即梯度截断法，FOBOS前向后向截断法，RDA正则对偶平均法以及FTRL算法，这些算法的方法是渐进发展的。
TG算法通过apha与v参数共同决定梯度的截断。，算法如下所示：
FOBOS算法将权重的更新分为两步，第一步限制参数的更新不能太大，第二步增加正则项。
增加L1正则的FOBOS算法将第二步改为l1正则。
RDA算法将权重的更新分为三部分，第一部分计算之前所有的梯度和，第二部分加入正则，第三部分加入正则使其成为强凸函数。
加入l1正则的RDA为
通过对累积梯度的分情况讨论，得到l1-RDA为下式，即梯度累积小于一定的阈值则置为0。
将l1-FOBOS与l1-RDA公式进行整理，得到如下公式，因此两者主要有两点差异：1、前者采用当前梯度，而后者采用累加梯度且l1正则采用累加2、前者限制不能离之前的解太远，后者限制不能离0太远。
FTRL综合考虑了l1-FOBOS与l1-RDA算法，更新公式如下，l2正则的引入只是为了增强函数的强凸性。
其中FTRL的学习率采用各坐标分别计算学习率的方法。当某个方向的梯度变化较大，则减少学习率。
最终FTRL的算法如下
实验auc与loss变化如下：
3、自适应学习率算法
本文将着重实验adam算法，对于其他的自适应学习率算法及动量法详见http://blog.csdn.net/u013453936/article/details/79004264。Adam主要将动量法与自适应学习率算法相结合，既存储历史梯度累积，也计算历史梯度平方累积，作为最终的学习率。代码详见sparsesgd.py以及adadelta.py
实验auc与loss变化如下：
4、方差减少的梯度算法
由于随机梯度下降算法计算的梯度方差较大，仅具有次线性收敛速度。通过加入梯度累积，可以使方差减少。典型的方差减少算法包含SVRG以及SAG算法。
Sag主要通过维护一个旧的梯度，将更新的项使用新的梯度替换旧的梯度。
Svrg通过每隔一定的迭代次数，计算全部样本的梯度。每个阶段内部每次迭代计算两个部分样本的梯度，包含外层参数计算的梯度，以及当前参数计算的梯度，通过外层参数计算的梯度与全部样本的梯度的差来纠正当前参数的梯度。具体如下所示。其中svrg在训练过程中不需要降低学习率，可以以一个很大的学习率来更新参数。代码详见svrg.py
实验auc与loss变化如下：
以上四种算法的对比图如下。
[1] Ad Click Prediction: a View from the Trenches
[2] ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION
[3] Minimizing finite sums with the stochastic average gradient.
[4] Accelerating Stochastic Gradient Descent using
[5] Accelerating Stochastic Gradient Descent using Predictive Variance Reduction