FOLLOW THE REGULARIZED LEADER 算法总结

之前在个人的 blog 中介绍过 FTRL 算法，也写过文章如下：

本文在知乎上也有发表，标题是《 FOLLOW THE REGULARIZED LEADER (FTRL) 算法总结 》，链接是 https://zhuanlan.zhihu.com/p/32903540 .在之前的网站（zr9558.com）上面也整理过这些文章，供读者参考。

1. TRUNCATED GRADIENT (TG) 算法简介

2. FORWARD-BACKWARD SPLITTING (FOBOS) 算法简介

3. REGULARIZED DUAL AVERAGING ALGORITHM (RDA)

4. FOLLOW THE REGULARIZED LEADER (FTRL) 算法

现在做在线学习和 CTR 常常会用到逻辑回归（ Logistic Regression ），而传统的批量（batch）算法无法有效地处理超大规模的数据集和在线数据流，美国的 Google 公司先后三年时间（2010年-2013年）从理论研究到实际工程化实现的 FTRL（Follow-the-regularized-Leader） 算法，在处理诸如逻辑回归之类的带非光滑正则化项（例如 L1 范数，做模型复杂度控制和稀疏化）的凸优化问题上性能非常出色。

通常，优化算法中的 gradient descent 等解法，是对一批样本进行一次求解，得到一个全局最优解。但是，实际的互联网广告应用需要的是快速地进行模型的更新。为了保证快速的更新，训练样本是一条一条地过来的，每来一个样本，模型的参数对这个样本进行一次迭代，从而保证了模型的及时更新，这种方法叫做在线梯度下降法（ Online Gradient Descent ）。

在应用的时候，线上来的每一个广告请求，都提取出相应的特征，再根据模型的参数，计算一个点击某广告的概率。在线学习的任务就是学习模型的参数。所谓的模型的参数，其实可以认为是一个目标函数的解。跟之前说的根据批量的样本计算一个全局最优解的方法的不同是，解这个问题只能扫描一次样本，而且样本是一条一条地过来的。

当然这会有误差，所以为了避免这种误差，又为了增加稀疏性，有人又想到了多个版本的算法，Google 公司有人总结了其中几种比较优秀的，例如 FOBOS，AOGD 和微软的 RDA，同时提出了 Google 自己的算法 FTRL-Proximal。其中，FTRL-Proximal 在稀疏性和精确度等方面表现都比较好。