SGD算法

• GD算法
  
• SGD算法
  
  与SGD比较，GD需要每次扫描所有的样本以计算一个全局梯度，SGD则每次只针对一个观测到的样本进行更新。通常情况下SGD可以更快的逼近最优值，而且SGD每次更新只需要一个样本，使得它很适合进行增量或者在线计算（也就是所谓的Online learning）。

稀疏解

代和选取模型的时候我们经常希望得到更加稀疏的模型，这不仅仅起到了特征选择的作用，也降低了预测计算的复杂度。在实际使用LR的时候我们会使用L1或者L2正则，避免模型过拟合和增加模型的鲁棒性。在GD算法下，L1正则化通常能得到更加稀疏的解；可是在SGD算法下模型迭代并不是沿着全局梯度下降，而是沿着某个样本的梯度进行下降，这样即使是L1正则也不一定能得到稀疏解。

TG算法

1.L1正则化法

由于L1正则项在0处不可导，往往会造成平滑的凸优化问题变成非平滑的凸优化问题，因此可以采用次梯度(Subgradient)来计算L1正则项的梯度。权重更新方式为：

其中$\lambda\ge0$λ≥0是一个标量，为L1正则化的参数；$sgn(x)$sgn(x)为符号函数；$\eta^{(t)}$η(t)称为学习率；$G^{(t)}=\nabla_Wl(W^{(t)},Z^{(t)})$G(t)=∇W​l(W(t),Z(t))代表第$t$t次迭代中损失函数的梯度。
次梯度概念参考：https://blog.****.net/qq_32742009/article/details/81704139

2.简单截断法

既然L1正则化在Online模式下也不能产生更好的稀疏性，而稀疏性对于高维特征向量以及大数据集又特别的重要，我们应该如何处理呢？
简单粗暴的方法是设置一个阀值，当W的某纬度的系数小于这个阀值的时候，将其直接设置为0。这样我们就得到了简单截断法。权重更新方式如下：


$\theta$θ是一个正数

3.梯度截断法

简单截断法法简单且易于理解，但是在实际训练过程中的某一步，W的某个特征系数可能是因为该特征训练不足引起的，简单的截断过于简单粗暴(too aggresive)，会造成该特征的缺失。那么我们有没有其他的方法，使得权重的归零和截断处理稍微温柔一些呢？对，这就是梯度截断法，简单截断法和梯度截断法对特征权重的处理映射图对比如下：

梯度截断法的迭代公式如下：


如果$\alpha=\infty$α=∞，此时退化为简单截断法
如果$\alpha=0$α=0，此时退化为L1正则化法

FOBOS算法

FOBOS(Forward-Backward Splitting)算法把正则化的梯度下降问题分成一个经验损失梯度下降迭代和一个最优化问题。其中第二个最优化问题有两项：第一项2范数那项表示不能离loss损失迭代结果太远，第二项是正则化项，用来限定模型复杂度、抑制过拟合和做稀疏化等。

L1-FOBOS是TG在特定条件下的特殊形式

RDA算法