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\} 是一个非负递增序列。

从公式中可以看出:

  1. \frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W 包括了之前所有梯度的平均值。
  2. 具有正则项 \Psi(W)
  3. 额外项 \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)输入 \gamma, \lambda,初始化 W\in \mathbb{R}^{N}, G=0\in\mathbb{R}^{N}
(2)for t=1,2,3... 
         G=\frac{t-1}{t}G+\frac{1}{t}\nabla_{W}\ell(W,X^{(t)},Y^{(t)})
         更新 Ww_{i+1}^{(t+1)}=argmin_{w_{i}}\{\overline{g}_{i}^{(t)}+\lambda|w_{i}|+\frac{\gamma}{2\sqrt{t}}w_{i}^{2}\}
     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)}, 上面的公式可以写成:

L1-FOBOS:

W^{(t+1)}=argmin_{W}\{G^{(t)}\cdot W+\lambda||W||_{1}+\frac{1}{2}\sigma^{(1: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}\sigma^{(1:t)}||W-0||_{2}^{2} \}

可以看出:

  1. L1-FOBOS 考虑了梯度和当前模的 L1 正则项,L1-RDA 考虑的是累积梯度。
  2. L1-FOBOS 的第三项限制 W 不能够距离已经迭代过的 W^{(t)} 值太远,L1-RDA 的第三项限制的是 W 不能够距离 0 太远。
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s