FTRL在线最优化

（一）RDA（Regularized Dual Averaging）

是微软的研究成果，它更有效地提升了特征权重的稀疏性。

算法原理--特征权重的更新策略为： $W^ {(t+1)} ={\arg\min}_{W} \{ \frac{1}{2}\sum_{r=1}^t <G^{(t)},W >+\psi (W)+\frac{\beta ^t }{t} h(W) \}$ ---公式(1)

其中 $\frac{1}{2} <G^{(t)},W >$ 表示梯度 $G^{(t)}$ 对W的积分中值； $\psi (W)$ 表示正则项；h(W)表示一个辅助的严格凸函数； $\{\beta ^t |t \geq 1 \}$ 是一个非负且非自减序列。

L1-RDA

令: $\psi (W)=\lambda \mathop \| W \|_{1}$ ， $h(W)=\frac{1}{2} \| W \|_{2}^2$ ， $\beta ^t =\gamma \sqrt{t}$ ，将公式(1)L1正则化

$W^ {(t+1)} ={\arg\min}_{W} \{ \frac{1}{2}\sum_{r=1}^t <G^{(t)},W >+\lambda \mathop \| W \|_{1}+\frac{\gamma }{2\sqrt{t}} \| W \|_{2}^2 \}$

根据特征权重的各个维度将其拆解成N个独立的标量最小化问题：

$\min_{w_{i}\in \mathbb {R} } \{ \frac{1}{2}\sum_{r=1}^t <{g_{i} }^{(t)},w_{i} >+\lambda \mathop \| w_{i} \|_{1}+\frac{\gamma }{2\sqrt{t}} \| w_{i} \|_{2}^2 \}$

即 $\min_{w_{i}\in \mathbb {R} } \{ \frac{1}{2}\sum_{r=1}^t {g_{i} }^{(t)} w_{i} +\lambda \mathop | w_{i} |+\frac{\gamma }{2\sqrt{t}} w_{i} ^2 \}$

这里 $\lambda \geq 0$ ， $\gamma > 0$ ，假设 $w_i^*$ 是最优解

次导数 $\partial | w_{i} |=\left\{ \begin{aligned}\{-1<\xi <1\} \quad if \ w_{i}^* = 0 \\\{1\} \quad if \ w_{i}^* > 0 \\\{-1\} \quad if \ w_{i}^* </p><p>求导并等于0：<img class=$ ---公式(2)

令 $\bar{g}_{i} ^t =\frac{1}{2}\sum_{r=1}^t {g_{i} }^{(t)}$

求导并令等于0： $\bar{g}_{i} ^t +\lambda \partial | w_{i}^* | +\frac{\gamma }{\sqrt{t}} w_{i}^*=0$

(1)当 $w_{i}^* = 0$ 时， $\bar{g}_{i} ^t +\lambda \partial | w_{i}^* | =0$ ，得 $| \bar{g}_{i} ^t | < \lambda$

(2)当 $w_{i}^* < 0$ 时， $w_{i}^* =\frac{\sqrt{t} }{\gamma } (\lambda -\bar{g}_{i} ^t)$ ，则 $\frac{\sqrt{t} }{\gamma } (\lambda -\bar{g}_{i} ^t)<0$ ，即 $0 \leq \lambda <\bar{g}_{i} ^t$

(3)当 $w_{i}^* > 0$ 时， $w_{i}^* =\frac{\sqrt{t} }{\gamma } (-\lambda -\bar{g}_{i} ^t)$ ，则 $\frac{\sqrt{t} }{\gamma } (-\lambda -\bar{g}_{i} ^t)>0$ ，即 $\bar{g}_{i} ^t < -\lambda \leq 0$

综合可知，L1-RDA特征权重的各个维度更新的方式为： $w_{i}^{(t+1)} =\left\{ \begin{aligned}0 \ \ \ \ \ \ \ \ \ \ \ \ \quad if \ | \bar{g}_{i} ^t | < \lambda \\\frac{\sqrt{t} }{\gamma } (\lambda \cdot sgn(\bar{g}_{i} ^t) -\bar{g}_{i} ^t ) \quad if \ otherwise )\end{aligned} \right\}$

L1-RDA的“截断阈值”为λ，是一个常数，并不随着t而变化，因此这种性质使得L1-RDA更容易产生稀疏性。某一维特征的梯度累加中值未达到“截断阈值”时，其特征权重仍置为0。

（二）FOBOS(Forward-Backward Splitting)

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

$W^{(t+\frac{1}{2} )} =W^{(t)} -\eta^{(t)} G^{(t)}$

$W^{(t+1)}=\arg\min_{W} \{ \frac{1}{2}\|W-W^{(t+\frac{1}{2})} \|_2^2+\eta^{(t+\frac{1}{2})}\Psi (W) \}$

其中 $\eta>0$ 是学习率，通常定义为 $\frac{1}{\sqrt{t} }$ 的正相关函数； $\Psi (W)>0$ 是正则项；

更新后的 $W^{(t+1)}$ 不仅和 $W^{(t)}$ 有关，还和自己 $\Psi (W)$ 有关。这也许就是”前向后向切分”这个名称的由来；

L1-FOBOS

令 $V=W^{(t+\frac{1}{2})}$ 是已知的， $\Psi (W) =\lambda ||W||_1$ , $\tilde{\lambda } =\eta^{(t+\frac{1}{2} )} \lambda$ ，并拆解成对特征权重每一维度单独求解：

$w_i^{(t+1)}=\arg \min_{w_i} \{ \frac{1}{2}(w_i-v_i)^2+\tilde{\lambda }|w_i| \}$

假设 $w_i^*$ 是最优解，有 $w_i^* v_i\geq 0$

反证法：

假设 $w_i^* v_i<0$ 成立，则 $\frac{1}{2}(w_i-v_i)^2+\tilde{\lambda }|w_i| > \frac{1}{2}v_i^2$ ，则此时最优解是 $w_i^*=0$ ，与假设矛盾。得证： $w_i^* v_i\geq 0$ 。

wi的次导数见上面的公式(2)

求导： $w_i^*-v_i+\tilde{\lambda }\partial |w_i^*| =0$

(1)当 $w_i^*=0$ 时， $|v_i|<\tilde{\lambda }$

(2)当 $w_i^*>0$ 时， $w_i^*=v_i-\tilde{\lambda } =v_i-\tilde{\lambda } \cdot sgn(v_i)$ ， $v_i>-\tilde{\lambda }$

(3)当 $w_i^*<0$ 时， $w_i^*=v_i+\tilde{\lambda } =v_i-\tilde{\lambda } \cdot sgn(v_i)$ ， $v_i<-\tilde{\lambda }$

综合可知，L1-FOBOS特征权重的各个维度更新的方式为：

$w_{i}^{(t+1)} =\left\{ \begin{aligned}0 \ \ \ \ \ \quad if \ | w_i^{( t )}-\eta^{(t)} g_i^{(t)} | < \eta^{(t+\frac{1}{2} )}\lambda \\\ w_i^{(t)}-\eta^{(t)} g_i^{(t)}-\eta^{(t+\frac{1}{2} )} \lambda \cdot sgn(w_i^{(t)}-\eta^{(t)} g_i^{(t)}) \quad if \ otherwise )\end{aligned} \right\}$

L1-RDA VS L1-FOBOS

在L1-FOBOS中，“截断阈值”随着时间t会逐渐减低，而L1-RDA是固定的，这种性质使得L1-RDA更容易产生稀疏性；RDA中判定对象是梯度的累加平均值，而L1-FOBOS针对单次梯度计算的结果进行判定，使得L1-RDA避免了由于某些维度由于训练不足导致截断的问题。

实验证明，L1-FOBOS这一类基于梯度下降的方法有比较高的精度，但是L1-RDA却能在损失一定精度的情况下产生更好的稀疏性。

（三）FTRL（Follow the Regularized Leader）

$W^{(t+1)}=\arg \min_{W} \{ G^{(1:t)}W+\lambda_1 ||W||_1+\lambda _2||W||_2^2+\frac{1}{2}\sum_{s=1}^t (\delta ^{(s)}||W-W^{(s)}||_2^2) \}$ -----公式(3)

$G^{(1:t)}=\sum_{s=1}^t G^ {(s)}$

$\delta ^{(s)}=\frac{1}{\eta ^{(s)} } -\frac{1}{\eta ^{(s-1)}}$

$\delta ^{(1:t)}=\sum_{s=1}^t \delta ^{(s)}=\frac{1}{\eta ^{(t)} }$

公式(3)中出现了L2正则项，在论文[2]的公式中并没有这一项，但是在其2013年发表的FTRL工程化实现的论文[3]却使用到了L2正则项。事实上该项的引入并不影响FRTL的稀疏性，后面的推导过程会显示这一点。L2正则项的引入仅仅相当于对最优化过程多了一个约束，使得结果求解结果更加“平滑”。

根据特征权重的各个维度将其分解成若干个独立的标量最小化问题：

$w_i^{(t+1)}=\arg \min_{w_i} \{ g^{(1:t)}w_i+\lambda_1 |w_i|+\lambda_2 w_i^2+\frac{1}{2}\sum_{s=1}^t (\delta ^{(s)}(w_i-w_i^{(s)})^2) \}$

公式(3)最后一项展开，等价于：

$w_i^{(t+1)}=\arg \min_{w_i} \{ (g^{(1:t)}-\sum\nolimits_{s=1}^t \delta ^{(s)}w_i^{(s)} )w_i+(\lambda _2 +\frac{1}{2} \sum_{s=1}^t \delta ^{(s)} )w_i^2+\lambda _1|w_i|+\frac{1}{2} \sum_{s=1}^t \delta^{(s)}(w_i^{(s)})^2 \}$

最后一项是常数项，可忽略，并令 $z^{(t)}=g^{(1:t)}-\sum\nolimits_{s=1}^t \delta ^{(s)}w_i^{(s)}$

$w_i^{(t+1)}=\arg \min_{w_i} \{ z^{(t)}w_i+(\lambda _2 +\frac{1}{2} \sum_{s=1}^t \delta ^{(s)} )w_i^2+\lambda _1|w_i| \}$

花括号里面求导并令等于0： $z^{(t)}+(2\lambda _2 + \sum_{s=1}^t \delta ^{(s)} )w_i+\lambda _1 \partial|w_i| =0$

令 $w_i^*$ 是最优解

(1)当 $w_i^*=0$ 时， $| z^{(t)}|\leq \lambda _1$

(2)当 $w_i^*> 0$ 时， $z^{(t)}<- \lambda _1<0$ ， $w_i^*=-(2\lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}+\lambda _1)=-(2\lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}-\lambda _1\cdot sgn(z_i^{(t)}))$

(3)当 $w_i^*< 0$ 时， $z^{(t)}> \lambda _1>0$ ， $w_i^*=-(2\lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}-\lambda _1)=-(2\lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}-\lambda _1\cdot sgn(z_i^{(t)}))$

综合可知，FTRL特征权重的各个维度更新的方式为：

$w_{i}^{(t+1)} =\left\{ \begin{aligned}0 \ \ \ \ \ \ \ \ \ \ \ \ \quad if \ | z^{(t)} | < \lambda_1 \\\ -(2 \lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}-\lambda _1\cdot sgn(z_i^{(t)})) \quad if \ otherwise )\end{aligned} \right\}$

或者简化等价为 $w_{i}^{(t+1)} =\left\{ \begin{aligned}0 \ \ \ \ \ \ \ \ \ \ \ \ \quad if \ | z^{(t)} | < \lambda_1 \\\ -(\lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}-\lambda _1\cdot sgn(z_i^{(t)})) \quad if \ otherwise )\end{aligned} \right\}$ ---公式(4)

可知，引入L2正则化并没有对FTRL结果的稀疏性产生任何影响。

Per-Coordinate Learning Rates

标准的学习率 $\eta ^{(t)} =\frac{1}{\sqrt{t} }$ ，这个策略保证了学习率是一个正的非增长序列，对于每一个特征维度都是一样的。

事实上在FTRL中，每个维度上的学习率都是单独考虑的（Per-Coordinate Learning Rates）。

公式(4)变为： $w_{i}^{(t+1)} =\left\{ \begin{aligned}0 \ \ \ \ \ \ \ \ \ \ \ \ \quad if \ | z^{(t)} | < \lambda_1 \\\ -(\lambda _2+\frac{1}{\eta_i ^{(t)}} )^{-1} \cdot (z_i^{(t)}-\lambda _1\cdot sgn(z_i^{(t)})) \quad if \ otherwise )\end{aligned} \right\}$

$\eta_i ^{(t)} =\frac{\alpha }{\beta +\sqrt{\sum_{s=1}^t (g_i^{(s)})^2} }$

（四）FTRL工程实现

完毕。

FTRL在线最优化

推荐阅读更多精彩内容