这篇博客主体内容已经写完，还有些细枝末节之后再做补充。
本文将会聚焦在线学习中极为重要的一类，凸在线学习（OnlineConvexLearning），从理论上解读并理解在线学习模型，探究当前工业界应用最广的FTRL-Proximal方法的演变过程，为之后的代码实现和方法应用铺平道路。
接下来，我们仔细谈谈凸在线学习里面的各种低Regret算法，在这里我们主要谈一阶方法，比如镜面下降（MirrorDescent）以及FTRL（FollowtheRegularizedLeader），这两大类的本质是相同的，只是看待问题角度不同，这一点在之后会谈到。
在正式开始讨论之前，我们首先要定义几个符号。\(w_t\)是\(t\)时刻的参数，\(f_t(w_t)\)是\(t\)时刻的损失函数，\(S\)是参数所在的凸集，\(\alpha\)是学习率，\(\nablaf_t\)是梯度，\(\partialf_t\)是次梯度。
如何进行在线学习？最容易想到的方法就是最小化累积损失，也就是FTL（FollowtheLeader），其形式如下：
在2.1节我们谈到了能最小化累计损失不能说明此算法在在线学习场景是有效，我们需要探究算法的Regretbound。
对任意的\(u\inS\)，都有
通过归纳法可以很容易证明以上定理，但是这个上界在\(w_t\)不停上下震荡（比如在1和-1循环取值）的时候是会达到\(O(T)\)，不满足次线性。事实上FTL在损失函数强凸的情形下是满足Regret次线性的，但在一般凸函数情形下不满足。我们可以在FTL基础上加上正则项\(R(w)\)使得算法变得“平稳”一些。这就是FTRL（FollowtheRegularizedLeader）。注意，FTRL里的正则项和所谓的稀疏性并没有联系，只是为了让算法更稳定从而满足次线性。其形式如下：
正则项可以有多种不同的选择。首先我们讨论线性损失函数加上\(L_2\)正则项的情形。为方便起见，定义\(z_t=\partialf_t(w_t)\)。
损失函数为\(f_t(w)=\left
这就是在线梯度下降（OnlineGradientDescent(OGD)），OGD是FTRL当损失函数为线性以及正则项为\(L_2\)的特殊形式，它的Regretbound可以被证明是\(O(\sqrtT)\)，这里就不展开了，这能够说明OGD在在线学习场景中是有理论来保障其性能的。我们还能延扩到其它凸损失函数领域而不只是局限于线性函数，利用凸函数定义可得，
可以看到线性函数的Regret构成了凸函数的上界，所以我们只需要针对线性函数即可，能够证明凸损失函数函数加上\(L_2\)正则项的Regretbound在满足一定条件下是\(O(\sqrtT)\)的，同时延拓到其它强凸的正则项\(R(w)\)也是可行的。此时我们可以得到FTRL的通式：
在每回合，FTRL都需要求解一个优化问题，在线镜面下降（OnlineMirrorDescent(OMD)）可以简化FTRL，同时其Regretbound和FTRL是一致的。OMD和线性损失函数加正则项的FTRL是等价的，下面我们来推导一下。为了方便起见，定义\(z_{1:t}=\sum\limits_{i=1}^tz_i\)。
定义连接函数\(g(\theta)=\arg\max_w\left
OMD的更新形式很像是OGD，事实上，OGD正是OMD最简单的形式。当\(g(\theta)=\eta\theta\)，\(\eta>0\)以及\(S\inR^d\)，很容易能看出OMD就是OGD。当\(g\)函数是一般的非线性函数时，\(w_{t+1}\)是通过连接函数\(g\)将\(\theta_{t+1}\)“映射”（mirror）到\(S\)集合中得到的。这就是OMD名字的由来。
OMD是一个大家族，包含了各种梯度下降式算法，我们首先从OGD看起，OGD形式如下：
我们在此讨论离线形式的随机梯度下降（SGD），即每次输入一个样本对参数进行更新，其本质和OGD是一致的。顺便说一句，SGD有一个别称叫增量梯度下降IGD（IncrementalGraidentDescent），其对应了增量学习（IncrementalLearning），具体不展开了，想了解可以自行查阅资料。SGD有一个很大的缺陷，即要求目标函数必须是光滑的，这一点在现实中较难满足，因为通常为了达到稀疏性我们要考虑正则项，\(L_1\)正则在\(0\)点是不可微的。因此需要对SGD作出一点改进，将梯度改成次梯度，次梯度的定义为\(\partialf=\{u\midf(y)\geqf(x)+u^T(y-x)\}\)，此时\(L_1\)正则在\(0\)点的次梯度为\(\left[-1,1\right]\)中元素。
梯度下降转化为了次梯度下降（SubgradientDescent(SubGD)），形式如下：
次梯度下降从理论上解决了非光滑损失函数这一类问题，但是其收敛速度较慢，只有\(O(1/\sqrtt)\)，梯度下降的收敛速度为\(O(1/t)\)。究其原因，由于损失函数非光滑，导致次梯度值会出现急剧变化，比如从-1跳到了1，尽管\(w_t\)和\(w_{t+1}\)是很接近的，这就导致了收敛速度减慢。为了解决这种问题，我们可以采取“作弊”的方式，用\(t+1\)时刻的次梯度去更新得到\(w_{t+1}\)，这就是后向次梯度下降。这个问题第一眼看是没法解的，我们得不到\(w_{t+1}\)的更新式，不过我们可以利用Fermat引理来求解。
为方便起见，引入邻近算子（proximaloperator）概念：
这时后向次梯度下降的形式为：
在实际的大量凸优化问题中，损失函数本身可能是凸光滑的，所带的正则项是非光滑的，问题转化为最小化\(f(w)+\lambda\Psi(w)\)，\(\Psi(w)\)是非光滑的正则项。这时为了适应特定问题场景，后向次梯度下降转化为了前向后向分割（FOBOS），FOBOS的全称是Forward-BackwardSplitting，之所以不叫FOBAS是为了和之前的FOLOSForward-LookingSubgradients保持一致，避免引起读者的误解。
FOBOS分为两步进行，对于光滑项梯度下降，对于非光滑项后向次梯度下降。具体形式如下：
统一起来，其形式为
因此FOBOS又可以被叫做邻近梯度下降（ProximalGradientDescent(PGD)）
以上导出FOBOS的过程看上去很直观，但实际上缺乏一些理论依据。接下来我们从理论角度重新推导FOBOS。
首先，对于损失函数，我们采用二阶近似来逼近，用\(\frac{1}{\eta}I\)代替\(\nabla^2f\)。
这就是FOBOS的最终形式。
看上去FOBOS是比梯度下降复杂多了，实际上不然，在很多场景下邻近算子是非常容易求得的，比如LASSO。当正则项为\(L_1\)的时候，我们把它的邻近算子称为软阙值算子\(T_\alpha\)（soft-thresholdingoperator），其形式为：
以上，我们都是在讨论线下场景的凸优化，凸在线学习本质上和线下凸优化是一致的，不过也有一些不同。以梯度下降为例，在线学习中梯度下降的形式为在线梯度下降（OGD），OGD和SGD本质上是相同的，即每次使用一个样本的梯度下降。但是两者应用的场景不同，OGD适用于线上情景，损失依次到来，其Regretbound\(\alpha-\)能达到\(O(\sqrt(T))\)，Regret次线性增长能够证明OGD是适用于在线学习场景的。另外虽然SGD形式和OGD一致，但两者思路还是有区别，SGD的梯度是靠样本去估计的，而OGD则是直接进行处理。FOBOS的在线版本也是同理，Regretbound在损失函数\(\alpha-\)强凸情况下能达到\(O(log(T))\)。
SubGD还有一个问题，在于新的次梯度的权重比老次梯度要低。具体的推导如下：
考虑二阶近似，令\(Z_t=\sum\limits_{i=1}^t\eta_i\)，\(g_t=\partialf(w_t)\)
可以看出，老的次梯度相比新的次梯度有更高的权重，这显然不合理。对偶平均（DualAveraging）通过赋予所有次梯度同等权重，解决了SubGD这种缺陷。
定义\(\hatg_t=\frac{1}{t}\sum\limits_{i=1}^tg_i\)，
其中\(\mu_t\)是步长。
SubGD的在线版本还有一个额外的缺陷，即无法得到稀疏解，于是微软提出了正则对偶平均（RegularizedDualAveraging(RDA)），能得到比FOBOS更稀疏的解。相比于DA，RDA增加了一个正则项\(\Psi\)，用一个强凸函数\(h\)替代了原先的二阶范数，其形式如下：
由于是在线算法，因此出于运行效率的考量，通常选取简单形式的\(h\)和\(\Psi\)，比如二阶范数和\(L_1\)正则项，令\(\mu_t=\gamma\sqrtt\)。接下来，我们就来求解这种简单形式的RDA：
将其右式分成\(n\)个独立式分别求解，令\(\gamma_t=\frac{\gamma}{\sqrtt}\)，这就转化为了：
求导之后可得，
其中\(w^*\)是最优解，\(\delta\in\partial\vertw\vert\)，之后根据\(\delta\)的取值分情况讨论，最终可以得到RDA的闭式解，
现在我们有了两个SubGD加强版算法，FOBOS以及RDA。FOBOS相比RDA能够达到更高的精度，而RDA能够得到更稀疏解，Google融合两者各取所长提出了如今在工业界中应用甚广的FTRLProximal。
为了看得更清楚一些，我们把FOBOS和RDA写成相似的形式（推导过程不严格）：
在这里\(Q\)是学习率，\(g_t\)是损失函数的梯度，\(g_{1:t}=\sum_{i=1}^tg_i\)。从以上可以看出，更新式分为三项，第一项是损失函数的一阶近似，第二项是非光滑正则项，此处为\(L_1\)正则，第三项为强凸正则项，此处为\(L_2\)正则。
从通式上我们能看出FOBOS和RDA总共有三点不同：
事实上，Google在论文中证明了一个等价定理，即OMD和FTLR等价。如此一来FOBOS的更新式能够等价地写成：
此处\(\phi\)是\(L_1\)正则的次梯度。这个更新式和RDA就更像了。FOBOS的优化是针对基于次梯度估计的累积\(L_1\)正则，经实验验证正是因为次梯度估计的存在才导致了FOBOS的稀疏性不如RDA来得好。FOBOS的强凸项中心化点为当前的点而非原点，这个好处是更新后我们不会在预测我们已经见过的样本时有太多偏差，这就是所谓的Proximal名字的来历。
FTRLProximal在处理稀疏性上和RDA一致，处理中心化点上和FOBOS一致，如此一来既达到了更好的稀疏性又提升了精确度，其形式如下：
注意\(L_1\)正则前并没有\(t\)。【3】和【4】中FTRL-Proximal公式在这一点上是不同的，不过都是\(\alpha_t\)的特殊形式，一个是\(\alpha_t=1\)，一个是\(\alpha_t=t\)。我特地发邮件问了作者BrendanMcMahan，他的回复是在实践中固定的\(\lambda_1\)经常makesthemostsense。
看上去这个优化问题有点复杂，但实质上这和\(RDA\)的求解是非常相似的。定义\(z_t=g_{1:t}-\sum\limits_{i=1}^t\sigma_iw_i\)，其中\(\sigma_{1:t}=\frac{1}{\eta_t}\)。如此一来，优化式就转化为：
这个形式和上面的RDA是一模一样的，求解完全相同。最终结果是：
FTRL-Proximal的伪代码如下：
最后，我们对上面讲过的内容做一下总结归纳。
在线学习是一种强大的线上模型训练方法，一个低Regret算法能够保证其平均表现和最优决策的平均表现是相当的，我们着重介绍了在线学习中的一大类，一阶凸在线学习，其代表算法是FTRL。FTRL通过最小化累计损失来更新参数，加上了正则项来使算法平稳。通过选取不同的损失函数和正则项，FTRL可以转化为多种形式，比如OGD。
OMD也是一种代表算法，它与FTRL本质相同，由于其梯度特性被认为是梯度下降类算法的通式。OGD是OMD最简单的形式，它一种高效简洁的在线学习方法，在不少问题上能以很小的计算消耗达到不错的精度，但其有两大缺陷，一是稀疏性不够，即使加上了正则项也会因为浮点数相加而很难得到精确零值。这时可以采用截断法，比较流行的有TruncatedGradient以及FOBOS。二是不能处理非光滑函数，这时就需要用次梯度代替梯度，即SubGD。SubGD虽然能处理非光滑，但收敛速度慢，FOBOS通过向前看一步，有效提升了收敛速度。而且在加上正则项后通过软阙值截断，能达到较好的稀疏性。RDA也是SubGD的加强版，相比FOBOS能达到更好的稀疏性，不过由于其中心化点是原点，可能会在预测我们已经见过的样本时有一定偏差。
虽然我们在上面没有提，不过从FTRL通式和RDA通式能看出两者的相似性，RDA实质上是FTRL家庭中的一员。当我们融合RDA和FOBOS，将FTRL和OMD相联结，我们就得到了FTRL-Proximal，既能达到较高的预测精度，又能达到较好的稀疏性。
还有几点零碎的我想说的，一并写在这里。
【1】IntroductiontoOnlineConvexOptimization.EladHazan.PrincetonUniversity.2016.
【2】OnlineLearningandOnlineConvexOptimization.ShaiShalev-Shwartz.2011.
【3】AdClickPrediction:aViewfromtheTrenches.H.BrendanMcMahanet.al.Google.2013.
【4】Follow-the-Regularized-LeaderandMirrorDescent:EquivalenceTheoremsandL1Regularization.H.BrendanMcMahan.Google.2011
【5】EfficientOnlineandBatchLearningUsingForwardBackwardSplitting.JohnDuchiet.al.2009.
【6】AdaptiveSubgradientMethodsforOnlineLearningandStochasticOptimization.JohnDuchiet.al.2011.
【7】DualAveragingMethodsforRegularizedStochasticLearningandOnlineOptimization.LinXiao.Microsoft.2010.
【8】AUnifiedViewofRegularizedDualAveragingandMirrorDescentwithImplicitUpdates.H.BrendanMcMahan.Google.2011
【9】OptimizationandMatrixComputationcoursebyJianfengCai.HongKongUniversityofScienceandTechnology.2017.
【10】OptimizationcoursebyGeoffGordon.CarnegieMellonUniversity.2012.
【11】IntroductiontoOnlineLearningcoursebyHaipengLuo.UniversityofSouthernCalifornia.2017.
【12】Normalizedonlinelearning.StephaneRosset.al.2013
【13】ASurveyofAlgorithmsandAnalysisforAdaptiveOnlineLearning.H.BrendanMcMahan.2017
【14】IntroductiontoOnlineLearningTheory.WojciechKotlowski.InstituteofComputingScience,Pozna′nUniversityofTechnology.2013
【15】Wikipedia,Quora,StackOverflow,CrossValidated,Zhihu