本文主要会分三个部分介绍，如果对理论产生背景不感兴趣的话，可以直接看第3部分的工程实现（这一部分google13年那篇工程化的paper介绍得很详细）：
【问题描述】
对于loss函数+正则化的结构风险最小化的优化问题（逻辑回归也是这种形式）有两种等价的描述形式，以1范数为例，分别是：
a、无约束优化形式的softregularizationformulation：
b、带约束项的凸优化问题convexconstraintformulation：
【批量（batch）算法】
批量算法中每次迭代对全体训练数据集进行计算（例如计算全局梯度），优点是精度和收敛还可以，缺点是无法有效处理大数据集（此时全局梯度计算代价太大），且没法应用于数据流做在线学习。这里分无约束优化形式和约束优化（与上面问题描述可以对应起来）两方面简单介绍一下一些传统批量算法。
b、不等式约束凸优化形式：1、传统的不等式约束优化算法内点法等；2、投影梯度下降（约束优化表示下），gt是subgradient，直观含义是每步迭代后，迭代结果可能位于约束集合之外，然后取该迭代结果在约束凸集合上的投影作为新的迭代结果（第二个公式中那个符号标识向X的投影）：
【在线算法】
如上所述，批量算法有自身的局限性，而在线学习算法的特点是：每来一个训练样本，就用该样本产生的loss和梯度对模型迭代一次，一个一个数据地进行训练，因此可以处理大数据量训练和在线训练。常用的有在线梯度下降（OGD）和随机梯度下降（SGD）等，本质思想是对上面【问题描述】中的未加和的单个数据的loss函数L（w，zi)做梯度下降，因为每一步的方向并不是全局最优的，所以整体呈现出来的会是一个看似随机的下降路线。典型迭代公式如下：
这里使用混合正则化项：，例如可能是1范数与2范数强凸项的混合（后面会看到其实很多都是这种混合正则化的格式，而且是有一定直观含义的）。迭代公式中：gt是loss函数（单点的loss，未加和）的subgradient，与gt相加的那一项是混合正则化项中的第二项的梯度，投影集合C是约束空间（例如可能是1范数的约束空间），跟上面介绍的投影梯度下降类似的做法。
1、简单的在线梯度下降很难产生真正稀疏的解，稀疏性在机器学习中是很看重的事情，尤其我们做工程应用，稀疏的特征会大大减少predict时的内存和复杂度。这一点其实很容易理解，说白了，即便加入L1范数（L1范数能引入稀疏解的简单示例可以产看PRML那本书的第二章，我前面一篇blog的ppt里也大概提了），因为是浮点运算，训练出的w向量也很难出现绝对的零。到这里，大家可能会想说，那还不容易，当计算出的w对应维度的值很小时，我们就强制置为零不就稀疏了么。对的，其实不少人就是这么做的，后面的TruncatedGradient和FOBOS都是类似思想的应用；
2、对于不可微点的迭代会存在一些问题，具体有什么问题，有一篇paper是这么说的：theiteratesofthesubgradientmethodareveryrarelyatthepointsofnon-differentiability。我前后看了半天也没看明白，有熟悉的同学可以指导一下。
二、TruncatedGradient、FOBOS以及RDA（RegularizedDualAveraging）
上面提到了，稀疏性在机器学习中是很重要的一件事情，下面给出常见的三种做稀疏解的途径：
1）、简单加入L1范数
下面会提一下FOBOS（Forward-BackwardSplittingmethod，其实应该叫FOBAS的，历史原因）以及RDA，因为后面的FTRL其实相当于综合了这两种算法的优点：
a、FOBOS，google和伯克利09年的工作：
b、RDA（Regularizeddualaveraging），微软10年的工作，更加理论性一些，这里就直接略过去了，仅对其特点做一个简单介绍：
ok，背景和一些铺垫终于完成了，下面重点进入FTRL的部分。。。
三、FTRL(Follow-the-regularized-Leader)
【发展历程】
FTRL的理论推进和工程应用首先要感谢这个人：H.BrendanMcMahan,google这哥们儿护了三年的坑，直到13年工程性paper出来。发展历程和基本说明如下：
–10年理论性paper，但未显式地支持正则化项迭代；11年证明regretbound以及引入通用的正则化项；11年另一篇的paper揭示OGD、FOBOS、RDA等算法与FTRL关系；13年的paper给出了工程性实现，并且附带了详细的伪代码，开始被大规模应用。
1）PoissonInclusion：对某一维度特征所来的训练样本，以p的概率接受并更新模型；
2.浮点数重新编码
[1]J.Langford,L.Li,andT.Zhang.Sparseonlinelearningviatruncatedgradient.JMLR,10,2009.（截断梯度的paper）
[2]H.B.McMahan.Follow-the-regularized-leaderandmirrordescent:EquivalencetheoremsandL1regularization.InAISTATS,2011（FOBOS、RDA、FTRL等各种方法对比的paper）
[3]L.Xiao.Dualaveragingmethodforregularizedstochasticlearningandonlineoptimization.InNIPS,2009（RDA方法）
[4]J.DuchiandY.Singer.Efficientlearningusingforward-backwardsplitting.InAdvancesinNeuralInformationProcessingSystems22,pages495{503.2009.（FOBOS方法）
[5]H.BrendanMcMahan,GaryHolt,D.Sculley,MichaelYoung,DietmarEbner,JulianGrady,LanNie,ToddPhillips,EugeneDavydov,DanielGolovin,SharatChikkerur,DanLiu,MartinWattenberg,ArnarMarHrafnkelsson,TomBoulos,JeremyKubica,AdClickPrediction:aViewfromtheTrenches,Proceedingsofthe19thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining(KDD)(2013)（这篇是那篇工程性的paper）
[6]H.BrendanMcMahan.Auniedanalysisofregular-izeddualaveragingandcompositemirrordescentwithimplicitupdates.Submitted,2011（FTRL理论发展，regretbound和加入通用正则化项）
[7]H.BrendanMcMahanandMatthewStreeter.Adap-tiveboundoptimizationforonlineconvexoptimiza-tion.InCOLT,2010（开始的那篇理论性paper）