在线学习：从梯度截断到FTRL

什么是在线学习，为什么要用在线学习

在一些大型互联网公司的广告系统中，Logistic Regression的权重更新非常看重速度，否则无法应对超大规模的数据集和在线数据流，因此就不能再用传统的批量梯度更新方法。在线学习是根据新来的样本，一边学习，一边对样本进行预测，从而保证了模型的及时更新。在线更新算法主要为了减少在线更新的误差同时又保证参数的稀疏性。

Truncated Gradient

问题定义：

无优化约束描述：

soft regularization formulation，L1正则约束

Logistic Regression损失函数：

LR损失函数

相对于TG来说，两种传统的优化算法是Gradient Decsent和Stochastic Gradient Decsent。SGD每次只选择一个样本更新参数，但是没有考虑稀疏性。

简单截断

解决参数稠密问题，最简单粗暴的方法就是当参数矩阵W中某维参数w小于设定阈值时直接置为0，但是w数值比较小可能是因为迭代轮数小学习不充分，简单截断可能会丢失重要特征。

K是截断窗口的大小，窗口中的迭代正常进行。

简单截断更新公式

T0是分段函数

梯度截断

上面的简单截断法看上去十分 aggressive，TG则是对简单截断的一种改进，同样是以 k 作为窗口，每进行 k 步就进行一次截断操作：

梯度截断更新公式

T1是分段函数，cta是截断阈值，alpha是截断斜率

从上面的公式可以看出， $\lambda ,\theta$ 决定了 W 的稀疏程度，如果 $\lambda$ 和 $\theta$ 都很大，那么稀疏性就会越强。

简单截断和梯度截断的对比

由上图可以看出选择 $\alpha =0$ ，截断梯度法就可以变成简单截断法。从公式上也可以通过计算直接得出。

FOBOS（FORWARD-BACKWARD SPLITTING）

$W^{(t+1)}=argmin_W{\{\frac {1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)} ||_2^2 +\eta^{(t+0.5)}\Psi (W)\}}$

第一项2范数那项表示不能离loss损失迭代结果太远，第二项通常是正则化项（例如L1范数），用来限定模型复杂度、抑制过拟合和做稀疏化等。设：

$F(W)=\frac {1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)} ||_2^2 +\eta^{(t+0.5)}\Psi (W)$

那么Wt+1的最优解一定在F(W)的偏导集合中：

$0 \in \partial F(W)= W-W^{(t)} + \eta^{(t)}G^{(t)}+\eta^{(t+0.5)}\partial \Psi(W)$

进而得到另一种权重更新方式：

$W^{(t+1)}=W^{(t)} - \eta^{(t)}G^{(t)}-\eta^{(t+0.5)}\partial \Psi(W)$

RDA（Regularized Dual Averaging Algorithm）

RDA的特点是：相对FOBOS，在精度与稀疏性之间做平衡，其中实验表明，在L1正则下，RDA比FOBOS可以更加有效地得到稀疏解。

$W^{(t+1)}=argmin_W{\{\frac {1}{t}\sum\nolimits_{r=1}^t G^{(r)}\cdot W + \Psi(W) + \frac{\beta^{(t)}}{t}h(W)\}}$

公式中第一项表明前t轮所有梯度的均值作为了当前轮参数的稀疏， $\psi (W)$ 通常指L1范数 $||W||_1$ ， $h(W)$ 通常指L2范数 $\frac{1}{2}||W||_{2}^2$ 。 $\beta^t=\gamma \sqrt{t} (\gamma >0)$ 是一个非负递增序列。自然地RDA的L1形式如下：

$W^{(t+1)}=argmin_W{\{\frac {1}{t}\sum\nolimits_{r=1}^t G^{(r)}\cdot W + \lambda||W||_1 + \frac{\gamma}{2\sqrt{t}}||W||_2^2\}}$

因此第t+1轮的参数矩阵中 $\omega _{i+1} (i\in [0,n-1])$ 的更新方式如下：

$\omega _{i+1}^{(t+1)}=argmin_{w_1}{\{\bar{g}_i^{(t)}+\lambda|\omega_i|+\frac{\gamma}{2\sqrt{t}}\omega_i^2 \}}$

其中 $g_i^{(t)}=\frac{1}{t}\sum\nolimits_{r=1}^t g_i^{(r)}$

经过推导证明， $\omega _{i+1}$ 可以表示成如下形式：

$\omega_i^{(t+1)}=0, if |\bar{g}_i^{(t)}|<\lambda \\ \omega_i^{(t+1)}=-\frac {\sqrt t}{\gamma}(\bar{g}_i^{(t)}-\lambda\cdot sgn(\bar{g}_i^{(t)})),otherwise$

意思就是：当某个维度的累加平均值小于 $\lambda$ 时，时，该维度的权重被设置成零，此时就可以产生特征权重的稀疏性。

RDA与FOBOS形式上的统一：

假设 $\eta ^{(t+0.5)}=\eta ^{(t)}=\Theta (t^{-0.5})$ ，并带入到FOBOS-L1的权重更新公式中，可以得到：

$W^{(t+1)}=argmin_W{\{||\frac {1}{2}W-W^{(t)}+\eta^{(t)}G^{(t)} ||_2^2 +\eta^{(t)}\lambda ||W||_1\}}$

等式右边除以 $\eta ^{(t)}$ 可以整理成如下形式:

$W^{(t+1)}=argmin_W{\{G^{(t)}\cdot W+\lambda||W||_1 +\frac {1}{2\eta^{(t)}}||W-W^{(t)}||_2^2\}}$

同时LDA-L1可以整理成：

$W^{(t+1)}=argmin_W{\{G^{(1:t)}\cdot W +t\lambda||W||_1 +\frac {1}{2\eta^{(t)}}||W-0||_2^2\}}$

其中 $G^{(1:t)}=\sum_{s=1}^tG^{(s)}$ ，如果令： $\sigma^{(s)}=\frac {1}{\eta^{(s)}}-\frac {1}{\eta^{(s-1)}},\sigma^{(1:t)}=\frac {1}{\eta^{(s)}},\sigma^{(1:t)}=\sum_{s=1}^t\sigma ^{(s)}$