Regularized Dual Averaging Algorithm (RDA)

Regularized Dual Averaging Algorithm 算法介绍

（一）RDA（Regularized Dual Averaging Algorithm）算法原理

RDA（Regularized Dual Averaging Algorithm）叫做正则对偶平均算法，特征权重的更新策略是：

$W^{(t+1)}=argmin_{W}\{\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W + \Psi(W) +\frac{\beta^{(t)}}{t}h(W)\}$

其中 $G^{(t)}\cdot W$ 指的是向量 $G^{(t)}$ 和 $W$ 的内积， $\Psi(W)$ 是正则项， $h(W)$ 是一个严格凸函数， $\{\beta^{(t)}|t\geq 1\}$ 是一个非负递增序列。

从公式中可以看出：

$\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W$ 包括了之前所有梯度的平均值。
具有正则项 $\Psi(W)$ 。
额外项 $\frac{\beta^{(t)}}{t}h(W)$ 。

（二）RDA 的 L1 正则化

假设 $\Psi(W)=||W||_{1}$ ； $h(W)=\frac{1}{2}||W||_{2}^{2}$ ，i.e. $h(W)$ 是一个严格凸函数； $\beta^{(t)}=\gamma\sqrt{t} \text{ with } \gamma>0$ 是一个非负递增序列。那么 RDA 算法就可以写成：

$W^{(t+1)}=argmin_{W}\{\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W + \lambda||W||_{1}+\frac{\gamma}{2\sqrt{t}}||W||_{2}^{2}\}$

此时可以采取同样的策略，把各个维度拆分成 N 个独立的问题来处理。也就是：

$w_{i+1}^{(t+1)}=argmin_{w_{i}}\{\overline{g}_{i}^{(t)}+\lambda|w_{i}|+\frac{\gamma}{2\sqrt{t}}w_{i}^{2}\}$

其中， $\lambda>0, \gamma>0,$ $\overline{g}_{i}^{(t)}=\frac{1}{t}\sum_{r=1}^{t}g_{i}^{(r)}.$

通过数学推导可以证明：

$w_{i}^{(t+1)}=0,$ if $|\overline{g}_{i}^{(t)}|<\lambda$

$w_{i}^{(t+1)}=-\frac{\sqrt{t}}{\gamma}(\overline{g}_{i}^{(t)}-\lambda\cdot sgn(\overline{g}_{i}^{(t)})),$ otherwise

意思就是：当某个维度的累加平均值 $|\overline{g}_{i}^{(t)}|$ 小于 $\lambda$ 时，该维度的权重被设置成零，此时就可以产生特征权重的稀疏性。

RDA 的算法

（1）输入 ，初始化 
（2）for  
         
         更新 ：
         
     end
     return W

（三）L1-RDA 与 L1-FOBOS 的对比

从截断方式来看，在 RDA 的算法中，只要梯度的累加平均值小于参数 $\lambda$ ，就直接进行截断，说明 RDA 更容易产生稀疏性；同时，RDA 中截断的条件是考虑梯度的累加平均值，可以避免因为某些维度训练不足而导致截断的问题，这一点与 TG，FOBOS 不一样。通过调节参数 $\lambda$ 可以在精度和稀疏性上进行权衡。

（四）L1-RDA 与 L1-FOBOS 形式上的统一

在 L1-FOBOS 中，假设 $\eta^{(t+0.5)}=\eta^{(t)}=\Theta(t^{-0.5})$ ，可以得到：

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

通过计算可以把 L1-FOBOS 写成：

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

同时 L1-RDA 可以写成：

$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}^{t}G^{(s)}$ 。如果令 $\sigma^{(s)}=\frac{1}{\eta^{(s)}}-\frac{1}{\eta^{(s-1)}},$ $\sigma^{(1:t)}=\frac{1}{\eta^{(t)}},$ $\sigma^{(1:t)}=\sum_{s=1}^{t}\sigma^{(s)},$ 上面的公式可以写成：