最优化求解问题可能是我们在工作中遇到的最多的一类问题了：从已有的数据中炼出最适合的模型参数，从而对未知的数据进行预测。当我们面对高维高数据量的场景时，常见的批量处理的方式已经显得力不从心，需要有在线处理的方法来解决此类问题。

动机与目的

在实际工作中，无论是工程师、项目经理、产品同学都会经常讨论一类话题：“从线上对比的效果来看，某某特征或因素对某某产品的最终效果有很大的影响”。这类话题本质上说的是通过已有的数据反映出某些特定的因素对结果有很强的正（或负）相关性。而如何定量计算这种相关性？如何得到一套模型参数能够使得效果达到最优？这就是最优化计算要做的事情。

举一类典型点的例子：在推荐和广告计算中，我们经常会需要对某些值进行预测，例如在一条推荐或广告在曝光之前先预测用户是否会产生点击（CTR预估），或者是否会由此产生某些转化（RPM预估）。这类问题可以表示为：针对一个输入，通过某个函数计算（预测）输出。根据值为连续的还是离散的，预测问题被划分成回归问题和分类问题。而利用已有的样本数据训练的过程往往转换成一个最优化求解的过程。

无论是线性回归（Linear Regression）、逻辑回归（Logistic Regression）、支持向量机（SVM）、深度学习（Deep Learning）中，最优化求解都是基本的步骤。常见的梯度下降、牛顿法、拟牛顿法等属于批量处理的方法（Batch），每次更新都需要对已经训练过的样本重新训练一遍。而当我们面对高维高数据量的时候，批量处理的方式就显得笨重和不够高效，因此需要有在线处理的方法（Online）来解决相同的问题。

从Batch到Online

我们面对的最优化问题都是无约束的最优化问题（有约束最优化问题可以利用拉格朗日乘数法或KKT条件转化成无约束最优化问题），因此我们通常可以将它们描述成：

这里为观测样本集合（训练集）；为第条样本的特征向量；为预测值；为特征向量到预测值的映射函数；为最优化求解的目标函数，也称作损失函数，损失函数通常可以分解为各样本损失函数的累加，即；为特征权重，也就是我们需要求解的参数。

在我们实际的数值计算中，通常的做法是随机给定一个初始的，通过迭代，在每次迭代中计算损失函数在当前的下降方向，并更新，直到损失函数稳定在最小的点。例如梯度下降法（GD，Gradient Descent）就是通过计算损失函数在当前处的梯度，以梯度的反方向作为下降方向更新，如果损失函数是一个非平滑的凸函数（Non-smooth convex），在不可导处用次梯度（Subgradient）方向的反方向作为下降方向。算法如下：

GD是一种批处理的方式（Batch），每次更新的时候都要扫描所有的样本以计算一个全局的梯度
考虑另一种策略

每次迭代仅仅根据单个样本更新权重，这种算法称作随机梯度下降（SGD，Stochastic Gradient Descent）。与GD相比较，GD每次扫描所有的样本以计算一个全局梯度，SGD则每次只针对一个观测到的样本进行更新。通常情况下，SGD能够比GD“更快”地令逼近最优值。当样本数特别大的时候，SGD的优势更加明显，并且由于SGD针对观测到的“一条”样本更新，很适合进行增量计算，实现梯度下降的Online模式（OGD，Online Gradient Descent）

在线最优化求解算法

稀疏性对于高维特征向量以及大数据集特别重要，假设有一亿维特征，但其有良好稀疏性，发现只有其中1000维特征与结果高度相关，那我们训练时模型仅高度关注这1000维特征即可，也就是模型帮我们做了需要业务精通的专业人士下大力才能做的特征工程。但是在Online模式下，不同于Batch，Online中每次的更新并不是沿着全局梯度进行下降，而是沿着某个样本的产生的梯度方向进行下降，整个寻优过程变得像是一个“随机”查找的过程（这也就是SGD中Stochastic的来历），这样Online最优化求解即使采用L1正则化的方式，也很难产生稀疏解。所以在我们接下来讨论的各个在线最优化求解算法中，稀疏性是一个重要的追求目标。

TG

为了得到稀疏的特征权重，最简单粗暴的方式就是设定一个阈值，当的某维度上系数小雨这个阈值时将其设置为（称作简单截断）。这种方法实现起来很简单，也很容易理解，即模型判断这个特征与最终结果相关性非常低，那我们可以直接抛弃这个特征。但实际中（尤其在OGD里面）的某个系数比较小可能是因为该维度训练不足引起的，简单进行截断会造成这部分特征的丢失。梯度截断法（TG，Truncated Gradient）是由John Langford，Lihong li和Tong Zhang在2009年提出，实际上是对简单截断的一种改进

L1正则法

由于L1正则项在处不可导，往往会造成平滑的凸函数变成非平滑凸优化问题，因此在每次迭代中采用次梯度计算L1正则项的梯度。权重更新方式为：

这里的是一个标量，且，为L1正则化参数；为符号函数，如果是一个向量，是向量的一个维度，那么有；为学习率，通常将其设置成的函数；代表了第次迭代中损失函数的梯度，由于OGD每次仅根据观测到的一个样本进行权重更新，因此也不再使用区分样本的下标

简单截断法

以为窗口，当不为整数时，采用标准的SGD进行迭代，当为整数时，采用如下权重更新方式

这里是一个标量，且；如果是一个向量，是向量的一个维度，那么有

梯度截断法

上述的简单截断法被TG的作者形容为too aggressive，因此TG在此基础上进行了改进，同样是采用截断的方式，但是比较不那么粗暴。采用相同的方式表示为：

其中且。TG同样是以为窗口，每步进行一次截断。当不为整数时，当为整数时。从上述公式可以看出，和决定了的稀疏程度，这两个值越大，则稀疏性越强。尤其令时，只需要通过调节一个参数就能控制稀疏性。通过公式，我们很容易写出TG的算法逻辑：

TG与简单截断以及L1正则化的关系

简单截断和截断梯度的区别在于采用了不同的截断公式和，如下图所示

为了清晰地进行比较，我们将TG的公式进行改写，描述特征权重每个维度的更新方式：

如果令，截断公式变成

此时TG退化成简单截断法。
如果令截断公式变成：

如果再令，那么特征权重维度更新公式变成：

此时，TG退化为L1正则化法。

Forward-Backward Splitting

算法原理

前向后向切分（Forward-Backward splitting）将权重的更新分为两个步骤：

前一个步骤实际上是一个标准的梯度下降步骤，后一个步骤可以理解为对梯度下降的结果进行微调。
观察第二个步骤，发现对的微调也分为两部分：

1. 前一部分保证微调发生在梯度下降的结果附近
2. 后一部分则用于处理正则化，产生稀疏性

如果将两个步骤合二为一，即将的计算代入中，有：

令，如果存在一个最优解，那么可以推断向量一定属于的次梯度集合：

由于，那么有：

上式实际上给出了权重更新的另一种形式：

我们这里可以看到，不仅仅与迭代前的状态有关，而且与迭代后的有关，这就是前后向名称的由来。

L1-Forward-Backward Splitting

在L1正则化下，有。为了简化描述，用向量来表示，用标量来表示，并将公式等号右边按维度展开：

我们可以看到，在求和公式中的每一项都是大于等于的，所以上式可以拆解成对特征权重每一维度单独求解：

首先，假设是的最优解，则有，这是因为：
反证法：假设，那么有：

这与是的最优解矛盾，故假设不成立，

综合上面的分析，可以得到Forward-Backward Splitting在L1正则化的条件下，特征权重的各个维度更新：

其中为梯度在维度上的取值。根据上式我们很容易就可以设计出其算法逻辑

L1-Forward-Backward Splitting与TG的关系

从上面的分析可以看出，L1-Forward-Backward Splitting在每次更新的时候，对的每个维度都会进行判定，当时对该维度进行“截断”，令。那么我们怎么去理解这个判定条件呢？如果我们把判定条件写成，那么这个含义就很清晰了：当一条样本产生的梯度不足以令对应维度上的权重值发生足够大的变化，认为在本次更新过程中该维度不够重要，应当令其权重为。L1-Forward-Backward Splitting特征权重的各个维度更新公式也可以写作如下形式：

比较上式与TG的特征权重维度更新公式，我们发现如果令，，，L1-Forward-Backward Splitting与TG完全一致。我们可以认为L1-Forward-Backward Splitting是TG在特殊条件下的特殊形式。

RDA

算法原理

不论怎样，简单截断、TG、FOBOS 都还是建立在 SGD 的基础之上的，属于梯度下降类型的方法，这类型方法的优点就是精度比较高，并且 TG、FOBOS 也都能在稀疏性上得到升。但是有些其它类型的算法，例如 RDA，是从另一个方面来求解 Online Optimization 并且更有效地升了特征权重的稀疏性。

正则对偶平均（RDA，Regularized Dual Averaging）是微软十年的研究成果，RDA是Simple Dual Averaging Scheme一个扩展，其特征权重的更新策略为：

其中，表示梯度对的积分平均值（积分中值）；为正则项；为一个辅助的严格凸函数；是一个非负非自减序列。本质上，上式包含了3个部分：

1. 线性函数，包含了之前所有梯度（或次梯度）的平均值（dual average）
2. 正则项
3. 额外正则项，它是一个严格凸函数

L1-RDA

我们下面来看看在L1正则化下，RDA中的特征权重更新具有什么样的形式以及如何产生稀疏性。令，并且由于是一个关于的严格凸函数，不妨令，此外，将非负非自减序列定义为，将L1正则化代入公式有：

针对特征权重的各个维度将其拆解成个独立的标量最小化问题，我们可以得到L1-RDA各维度更新方式：

这里我们发现，当某个维度上积累梯度平均值的绝对值小于阈值的时候，该维度权重将被置为，特征权重的稀疏性由此产生。根据上式，可以设计出L1-RDA的算法逻辑

L1-RDA与L1-Forward-Backward Splitting的比较

我们之前分析出L1-Forward-Backward Splitting实际上是TG的一种特殊形式，在L1-Forward-Backward Splitting中，进行“截断”的判定条件是。通常会定义为与正相关的函数（），因此L1-Forward-Backward Splitting的“截断阈值”为，随着的增加，这个阈值会逐渐降低。

相较而言，L1-RDA的“截断阈值”为，是一个常数，并不随着而变化，因此可以认为L1-RDA比L1-Forward-Backward Splitting在截断判定上更加aggressive，这种性质使得L1-RDA更容易产生稀疏性；此外，RDA中判定对象是梯度的累加平均值，不同于TG或L1-Forward-Backward Splitting中针对单次梯度计算的结果进行判定，避免了由于某些维度由于训练不足导致截断的问题。并且通过调节一个参数，很容易在精度和稀疏性上进行权衡。

FTRL

有实验证明，L1-Forward-Backward Splitting这一类基于梯度下降的方法有比较高的精度，但是L1-RDA却能在损失一定精度的情况下产生更好的稀疏性。那么这两者的优点能不能在一个算法上体现出来？这就是FTRL 要解决的问题。

FTRL（Follow the Regularized Leader）是由 Google 的 H. Brendan McMahan 在 2010 年出的，后来在 2011 年发表了一篇关于 FTRL 和 AOGD、Forward-Backward Splitting、RDA 比较的论文，2013年又和 Gary Holt, D. Sculley, Michael Young 等人发表了一篇关于 FTRL 工程化实现的论文。

FTRL算法原理

FTRL综合考虑Forward-Backward Splitting和RDA对于正则项和限制的区别，其特征权重的更新公式为：

注意，上式出现了L2正则项，在论文公式中并没有这一项，但在2013年发表的FTRL工程化实现的论文中却用了L2正则项。事实上该项的引入并不影响FTRL的稀疏性，L2正则项的引入仅仅相当于对最优化过程多了一个约束，使得结果求解结果更加“平滑”。

公式看上去很复杂，更新特征权重貌似非常困难的样子。不妨将其进行改写，将最后一项展开，等价于求下面这样一个最优化问题：

由于相对于来说是一个常数，并且令，上式等价于：

针对特征权重的各个维度将其拆解成个独立的标量最小化问题：

到这里，我们可得：

由上式可以看出，引入L2正则化并没有对FTRL结果的稀疏性产生任何影响。

Per-Coordinate Learning Rates

前面介绍了FTRL的基本推导，但是这里还有一个问题是一直没有被讨论到的：关于学习率的选择和计算。事实上在FTRL中，每个维度上的学习率都是单独考虑的（Per-Coordinate Learning Rates）。

在一个标准的OGD里面使用的是一个全局的学习率策略，这个策略保证了学习率是一个正的非增长序列，对于每一个特征维度都是一样的。

考虑特征维度的变化率：如果特征1比特征2的变化更快，那么在维度1上的学习率应该下降的更快。我们很容易就可以想到可以用某个维度上梯度分量来反应这种变化率。在FTRL中，维度上的学习率是这样计算的：

由于，所以中。这里的和是需要输入的参数，学习率写成累加的形式，是为了方便理解后面FTRL的迭代计算逻辑。

FTRL算法逻辑

到现在为止。我们已经得到了FTRL的特征权重维度的更新方法，每个特征维度的学习率计算方法，那么很容易写出FTRL的算法逻辑：

Source

在线最优化求解(Online Optimization)-冯扬
https://zhuanlan.zhihu.com/p/61724627