在线学习算法RDA（二）ILCTW

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

在RDA中，特征权重的更新策略为：

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

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

如果对公式(3)求导（求次导数）并等于0，则有：

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

还可以分为三种情况：

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

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

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

[1]LinXiao.DualAveragingMethodsforRegularizedStochasticLearningandOnlineOptimization.JournalofMachineLearningResearch,2010