在线最优化求解(Online Optimization)之四:RDA

时间:2022-02-27 14:55:36

在线最优化求解(Online Optimization)之四:RDA

不论怎样,简单截断、TG、FOBOS都还是建立在SGD的基础之上的,属于梯度下降类型的方法,这类型方法的优点就是精度比较高,并且TG、FOBOS也都能在稀疏性上得到提升。但是有些其它类型的算法,例如RDA从另一个方面来求解Online Optimization并且更有效地提升了特征权重的稀疏性。RDA(Regularized Dual Averaging)是微软十年的研究成果。RDA是Simple Dual Averaging Scheme一个扩展,由Lin Xiao发表于2010年[1]。

1. 算法原理

在RDA中,特征权重的更新策略为:

在线最优化求解(Online Optimization)之四:RDA  公式(1)

其中在线最优化求解(Online Optimization)之四:RDA表示梯度在线最优化求解(Online Optimization)之四:RDA在线最优化求解(Online Optimization)之四:RDA的积分平均值(积分中值);在线最优化求解(Online Optimization)之四:RDA为正则项;在线最优化求解(Online Optimization)之四:RDA为一个辅助的严格凸函数;在线最优化求解(Online Optimization)之四:RDA是一个非负且非自减序列。

本质上,公式(1)中包含了3个部分:(1) 线性函数在线最优化求解(Online Optimization)之四:RDA,包含了之前所有梯度(或次梯度)的平均值(dual average);(2) 正则项在线最优化求解(Online Optimization)之四:RDA;(3) 额外正则项在线最优化求解(Online Optimization)之四:RDA,它是一个严格凸函数。

2. L1-RDA

我们下面来看看在L1正则化下,RDA中的特征权重更新具有什么样的形式以及如何产生稀疏性。

在线最优化求解(Online Optimization)之四:RDA,由于在线最优化求解(Online Optimization)之四:RDA是一个关于在线最优化求解(Online Optimization)之四:RDA的严格凸函数,不妨令在线最优化求解(Online Optimization)之四:RDA,此外将非负非自减序列在线最优化求解(Online Optimization)之四:RDA定义为在线最优化求解(Online Optimization)之四:RDA,将L1正则化代入公式(1)有:

在线最优化求解(Online Optimization)之四:RDA   公式(2)

直接求解上式看上去非常困难,但是我们可以仿照上一篇FOBOS中采用的方法,针对特征权重的各个维度将其拆解成N个独立的标量最小化问题:

在线最优化求解(Online Optimization)之四:RDA    公式(3)

这里在线最优化求解(Online Optimization)之四:RDA在线最优化求解(Online Optimization)之四:RDA在线最优化求解(Online Optimization)之四:RDA;公式(3)就是一个无约束的非平滑最优化问题。其中第2项在线最优化求解(Online Optimization)之四:RDA在线最优化求解(Online Optimization)之四:RDA处不可导。假设在线最优化求解(Online Optimization)之四:RDA是其最优解,并且定义在线最优化求解(Online Optimization)之四:RDA在线最优化求解(Online Optimization)之四:RDA在线最优化求解(Online Optimization)之四:RDA的次导数,那么有:

在线最优化求解(Online Optimization)之四:RDA   公式(4)

如果对公式(3)求导(求次导数)并等于0,则有:

在线最优化求解(Online Optimization)之四:RDA   公式(5)

由于在线最优化求解(Online Optimization)之四:RDA,我们针对公式(5)分三种情况进行讨论:

-------------------------------------

(1) 当在线最优化求解(Online Optimization)之四:RDA时:

还可以分为三种情况:

(a) 如果在线最优化求解(Online Optimization)之四:RDA,由公式(5)可得在线最优化求解(Online Optimization)之四:RDA,满足公式(4)

(b) 如果在线最优化求解(Online Optimization)之四:RDA,由公式(4)可得在线最优化求解(Online Optimization)之四:RDA,那么有在线最优化求解(Online Optimization)之四:RDA,不满足公式(5)

(c) 如果在线最优化求解(Online Optimization)之四:RDA,由公式(4)可得在线最优化求解(Online Optimization)之四:RDA,那么有在线最优化求解(Online Optimization)之四:RDA,不满足公式(5)

所以,当在线最优化求解(Online Optimization)之四:RDA时,在线最优化求解(Online Optimization)之四:RDA

(2) 当在线最优化求解(Online Optimization)之四:RDA时:

采用相同的分析方法可以得到在线最优化求解(Online Optimization)之四:RDA,此时在线最优化求解(Online Optimization)之四:RDA,即:在线最优化求解(Online Optimization)之四:RDA

(3) 当在线最优化求解(Online Optimization)之四:RDA时:

采用相同的分析方法可以得到在线最优化求解(Online Optimization)之四:RDA,此时在线最优化求解(Online Optimization)之四:RDA,即:在线最优化求解(Online Optimization)之四:RDA

--------------------------------------

综合上面的分析,可以得到L1-RDA特征权重的各个维度更新的方式为:

在线最优化求解(Online Optimization)之四:RDA      公式(6)

这里我们发现,当某个维度上累积梯度平均值的绝对值在线最优化求解(Online Optimization)之四:RDA小于阈值在线最优化求解(Online Optimization)之四:RDA的时候,该维度权重将被置在线最优化求解(Online Optimization)之四:RDA,特征权重的稀疏性由此产生。

根据公式(6),可以设计出L1-RDA的算法逻辑为:

在线最优化求解(Online Optimization)之四:RDA

3. L1-RDA与FOBOS的比较

在上一篇博文中中我们看到了L1-FOBOS实际上是TG的一种特殊形式,在L1-FOBOS中,进行“截断”的判定条件是在线最优化求解(Online Optimization)之四:RDA。通常会定义在线最优化求解(Online Optimization)之四:RDA在线最优化求解(Online Optimization)之四:RDA的正相关函数(在线最优化求解(Online Optimization)之四:RDA),因此L1-FOBOS的“截断阈值”为在线最优化求解(Online Optimization)之四:RDA,随着在线最优化求解(Online Optimization)之四:RDA的增加,这个阈值会逐渐降低。

相比较而言,从公式(6)可以看出,L1-RDA的“截断阈值”为在线最优化求解(Online Optimization)之四:RDA,是一个常数,并不随着在线最优化求解(Online Optimization)之四:RDA而变化,因此可以认为L1-RDA比L1-FOBOS在截断判定上更加aggressive,这种性质使得L1-RDA更容易产生稀疏性;此外,RDA中判定对象是梯度的累加平均值在线最优化求解(Online Optimization)之四:RDA,不同于TG或L1-FOBOS中针对单次梯度计算的结果进行判定,避免了由于某些维度由于训练不足导致截断的问题。并且通过调节在线最优化求解(Online Optimization)之四:RDA一个参数,很容易在精度和稀疏性上进行权衡。

参考文献

[1]  Lin Xiao. Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization. Journal of Machine Learning Research, 2010