2.2.3 FTRL

FTRL（Follow the Regularized Leader）是一种优化算法，在处理诸如逻辑回归 之类的带非光滑正则化项的凸优化问题上性能出色，自 2013 年谷歌发表 FTRL 算 法的工程性实现论文后[17]，业界纷纷上线该算法，Amazon 通过上线该算法在搜索 广告业务中取得了不错的效果。FTRL 是一种在线学习算法，在线学习算法的特点 是，单独对每个数据进行训练，在 FTRL 之前常用的在线算法有 OGD（Online Gradient Descent）在线梯度下降和 SGD（Stochastic Gradient Descent）随机梯度下 降等。以上在线梯度下降算法的优点是精度很高，缺点是难以产生稀疏性[18]，导致 在预测时运算复杂度高。在 2010 年微软提出了 RDA（Regularized Dual Averaging） 的算法[19]，该算法相对于 OGD 算法在精度和稀疏性之间做平衡。算法的性能对比 如表 2-1[20]所示，其中 FOBOS（Forward Backward Splitting）为 OGD 改进。

FTRL 算法结合了 FOBOS（Forward-Backward Splitting）算法和 RDA （Regularized Dual Averaging）算法的优点，既能像基于梯度下降的方法一样具有比较 高的精度，又能在精度和稀疏性之间做更好的平衡，产生稀疏性良好的模型，并且能 够针对不同的特征权重维度进行单独训练，以方便实现并行化。 在线学习算法的主要特点体现在模型权重（特征权重）W 的更新上，其通常使用 随机梯度下降（SGD, Stochastic Gradient Descent）方法根据单个训练样本对模型进行 迭代更新，以实现梯度下降的 Online 模式（OGD, Online Gradient Descent）。FTRL 算 法的特征权重更新公式如下：（4.5）

其中，是前 t 次迭代的梯度和； 是第 s 次迭代 的学习率。经过化简分析以及特征权重各个维度的更新求解转化，第 i 个维度的特征 权重更新方式如下所示：

是ܼ的第 i 个分量。另外，在 FTRL 算法 中，不采用全局的学习率，而是单独考虑每一特征维度的学习率，因为不同特征的变 化率不一样。第 i 个特征维度的学习率使用如下公式计算：

（4.7）

 其中，݃是第 s 次迭代梯度的第 i 个分量。 根据 FTRL 算法的特征权重更新公式以及不同维度的学习率的计算方法，下面是 FTRL 算法工程化实现的主体过程：