凸在线学习：理论与实践
为什么写在线学习的博客？
有三个原因，一是在线学习在工业界广受欢迎，应用场景较多，尤其是涉及时序数据流的场景，有研究的价值；二是在线学习理论完备且较繁杂，需要仔细梳理归纳总结，硬看 Google 论文里的伪代码很难理解其真正含义；三是在线学习网上学习资源较少，我希望能通过自己的学习和理解，写出一篇综述型博客为后来者提供些许帮助。本人水平有限，时间有限，所以对在线学习无法深挖，只能点到为止，我在写这篇博客时所参考的资料在最后会全部给出，想要看更多细节可以去仔细阅读那些书籍和论文。本人才疏学浅，文章里有错误的地方，还望指出。如需转载，须经得本人同意。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
这篇博客主体内容已经写完，还有些细枝末节之后再做补充。
在线学习通俗的讲指的是在线上实时接受数据并对模型进行训练更新，这里所说的模型可以是线性回归，逻辑回归，神经网络等等，所解决的问题可以是分类也可以是回归。在现实中在线学习主要应用在搜索排名，广告点击等领域，其优势体现在以下几点：
训练数据无需满足独立同分布条件，数据分布可以随时间变化；
无需大量数据预训练，可以线上实时获取数据进行训练；
实时更新，针对数据变化及时响应，调整模型参数以达到更精准预测；
理论起源
本文将会聚焦在线学习中极为重要的一类，凸在线学习（Online Convex Learning），从理论上解读并理解在线学习模型，探究当前工业界应用最广的 FTRL-Proximal 方法的演变过程，为之后的代码实现和方法应用铺平道路。
首先我们要知道在线学习究竟要解决一个什么样的问题，在在线学习框架下，我们在时间 \(t\) 接收到实时数据 \(x_t\)，做出预测 \(p_t\)，之后收到正确值 \(y_t\)，受到损失 \(f(p_t, y_t)\)。我们想要得到一个策略使得我们能够在未来有尽可能小的损失，一个很自然的想法是通过在每一步最小化累积损失来做决策。然而，在这种想法的情形下，我们只关注了最小化过去，而未来是不确定的，我们无法保证未来也能有最小损失。另一个想法是如果有一个专家能够指引我们前进，那么我们只需要跟紧他就能保证未来也能得到尽可能小的损失。由此，我们定义经历 \(T\) 时刻的后悔 \(Regret_T\) 为我们的决策所导致的累积损失和最优决策（专家）所导致的累积损失之差，形式如下：
\[Regret_T = \sum\limits_{t=1}^Tf_t(w_t) - \min_w \sum\limits_{t=1}^Tf(w)\]
因此我们想要找到某个算法，它能够最小化 Regret。需要阐明的是，Regret 是从理论角度对算法的评估，其具体表现为 Regret Bound，而不是一个数值。所谓最小化 Regret，就是我们希望找到一个算法，它的 Regret Bound 能足够小。不过事实上低 Regret 算法，即 Regret 随时间 \(T\) 次线性增长，已经能满足我们的需求了。次线性增长是指 \(\displaystyle\lim_{T\to \infty} \frac{Regret_T}{T} = 0\)。次线性增长意味着算法的平均表现和最优决策的平均表现是相当的。
接下来，我们仔细谈谈凸在线学习里面的各种低 Regret 算法，在这里我们主要谈一阶方法，比如镜面下降（Mirror Descent）以及 FTRL（Follow the Regularized Leader），这两大类的本质是相同的，只是看待问题角度不同，这一点在之后会谈到。
在正式开始讨论之前，我们首先要定义几个符号。\(w_t\) 是 \(t\) 时刻的参数，\(f_t(w_t)\) 是 \(t\) 时刻的损失函数，\(S\) 是参数所在的凸集，\(\alpha\) 是学习率，\(\nabla f_t\) 是梯度，\(\partial f_t\) 是次梯度。
Follow the Regularized Leader
如何进行在线学习？最容易想到的方法就是最小化累积损失，也就是 FTL（Follow the Leader），其形式如下：
\[w_t = \arg \min_{w \in S} \sum\limits_{i=1}^{t-1}f_i(w)\]
在 2.1 节我们谈到了能最小化累计损失不能说明此算法在在线学习场景是有效，我们需要探究算法的 Regret bound。
对任意的 \(u \in S\)，都有
\[Regret_T(u) = \sum\limits_{i=1}^T (f_t(w) - f_t(u)) \leq \sum\limits_{i=1}^T (f_t(w) - f_{t+1}(w))\]
通过归纳法可以很容易证明以上定理，但是这个上界在 \(w_t\) 不停上下震荡（比如在1和-1循环取值）的时候是会达到 \(O(T)\)，不满足次线性。事实上 FTL 在损失函数强凸的情形下是满足 Regret 次线性的，但在一般凸函数情形下不满足。我们可以在 FTL 基础上加上正则项 \(R(w)\) 使得算法变得“平稳”一些。这就是 FTRL（Follow the Regularized Leader）。注意，FTRL 里的正则项和所谓的稀疏性并没有联系，只是为了让算法更稳定从而满足次线性。其形式如下：
\[w_t = \arg \min_{w \in S} \sum\limits_{i=1}^{t-1}f_i(w) + R(w)\]
正则项可以有多种不同的选择。首先我们讨论线性损失函数加上 \(L_2\) 正则项的情形。为方便起见，定义 \(z_t = \partial f_t(w_t)\)。
损失函数为 \(f_t(w) = \left<w, z_t\right>\)，正则项为 \(R(w) = \frac{1}{2\eta}||w||_2^2\)，其中 \(\eta\) 是某个常数，代入 FTRL 更新式很容易验证：
\[w_{t+1} = -\eta\sum\limits_{i=1}^tz_i = w_t - \eta z_t = w_t - \eta \partial f_t(w_t)\]
这就是在线梯度下降（Online Gradient Descent (OGD)），OGD 是 FTRL 当损失函数为线性以及正则项为 \(L_2\) 的特殊形式，它的 Regret bound 可以被证明是 \(O(\sqrt T)\)，这里就不展开了，这能够说明 OGD 在在线学习场景中是有理论来保障其性能的。我们还能延扩到其它凸损失函数领域而不只是局限于线性函数，利用凸函数定义可得，
\[\sum\limits_{i=1}^t f_i(w_i) - f_i(w^*) \leq \sum\limits_{i=1}^t z_i(w-w^*)\]
可以看到线性函数的 Regret 构成了凸函数的上界，所以我们只需要针对线性函数即可，能够证明凸损失函数函数加上 \(L_2\) 正则项的 Regret bound 在满足一定条件下是 \(O(\sqrt T)\) 的，同时延拓到其它强凸的正则项 \(R(w)\) 也是可行的。此时我们可以得到 FTRL 的通式：
\[w_{t+1} = \arg \min_{w\in S} \; \eta\sum\limits_{i=1}^tz_iw + R(w)\]
Online Mirror Descent
在每回合，FTRL 都需要求解一个优化问题，在线镜面下降（Online Mirror Descent (OMD)）可以简化 FTRL，同时其 Regret bound 和 FTRL 是一致的。OMD 和线性损失函数加正则项的 FTRL 是等价的，下面我们来推导一下。为了方便起见，定义 \(z_{1:t} = \sum\limits_{i=1}^t z_i\)。
\[ \begin{align*} w_{t+1} &= \arg \min_w R(w) + \sum\limits_{i=1}^t \left<w, z_i\right> \\ &= \arg \min_w R(w) + \left<w, z_{1:t}\right> \\ &= \arg \max_w \left<w, -z_{1:t}\right> - R(w) \end{align*} \]
定义连接函数 \(g(\theta) = \arg \max_w \left<w, \theta\right> - R(w)\)（注意连接函数可以是已定义的函数，此时OMD就不需要每回合求解一个优化问题）此时 FTRL 的更新式就变成了以下形式：
\[ \begin{align*} w_{t} &= g(\theta_{t}) \\ \theta_{t+1} &= \theta_t - z_t = \theta_t - \partial f_t(w_t) \end{align*} \]
OMD 的更新形式很像是 OGD，事实上，OGD 正是 OMD 最简单的形式。当 \(g(\theta) = \eta \theta\)，\(\eta > 0\) 以及 \(S \in R^d\)，很容易能看出 OMD 就是 OGD。当\(g\)函数是一般的非线性函数时，\(w_{t+1}\) 是通过连接函数 \(g\) 将 \(\theta_{t+1}\) “映射”（mirror）到 \(S\) 集合中得到的。这就是 OMD 名字的由来。
OMD 是一个大家族，包含了各种梯度下降式算法，我们首先从 OGD 看起，OGD 形式如下：
\[w_{t+1} = w_{t}-\alpha \nabla f_t(w_t)\]
我们在此讨论离线形式的随机梯度下降（SGD），即每次输入一个样本对参数进行更新，其本质和 OGD 是一致的。顺便说一句，SGD 有一个别称叫增量梯度下降 IGD（Incremental Graident Descent），其对应了增量学习（Incremental Learning），具体不展开了，想了解可以自行查阅资料。SGD 有一个很大的缺陷，即要求目标函数必须是光滑的，这一点在现实中较难满足，因为通常为了达到稀疏性我们要考虑正则项，\(L_1\) 正则在 \(0\) 点是不可微的。因此需要对 SGD 作出一点改进，将梯度改成次梯度，次梯度的定义为 \(\partial f = \{u \mid f(y) \geq f(x)+u^T(y-x)\}\)，此时 \(L_1\) 正则在 \(0\) 点的次梯度为 \(\left[-1, 1\right]\) 中元素。
梯度下降转化为了次梯度下降（Subgradient Descent (SubGD)），形式如下：
\[w_{t+1} = w_{t} - \alpha_t \partial f_t(w_t)\]
次梯度下降从理论上解决了非光滑损失函数这一类问题，但是其收敛速度较慢，只有 \(O(1/\sqrt t)\)，梯度下降的收敛速度为 \(O(1/t)\)。究其原因，由于损失函数非光滑，导致次梯度值会出现急剧变化，比如从-1跳到了1，尽管 \(w_t\) 和 \(w_{t+1}\) 是很接近的，这就导致了收敛速度减慢。为了解决这种问题，我们可以采取“作弊”的方式，用 \(t+1\) 时刻的次梯度去更新得到 \(w_{t+1}\)，这就是后向次梯度下降。这个问题第一眼看是没法解的，我们得不到 \(w_{t+1}\) 的更新式，不过我们可以利用 Fermat 引理来求解。
\[0 \in w_{t+1} - w_t + \alpha_t \partial f_t(w_{t+1}) \] 等价于
\[w_{t+1} = \arg\min_w \frac{1}{2} ||w - w_t||_2^2 + \alpha_t f_t(w)\]
为方便起见，引入邻近算子（proximal operator）概念：
\[prox_{\alpha f}(y) = \arg\min_w \frac{1}{2} ||w-y||_2^2 + \alpha f(w)\]
这时后向次梯度下降的形式为：
\[w_{t+1} = prox_{\alpha_t f_t}(w_t)\]
在实际的大量凸优化问题中，损失函数本身可能是凸光滑的，所带的正则项是非光滑的，问题转化为最小化 \(f(w) + \lambda \Psi(w)\)，\(\Psi(w)\) 是非光滑的正则项。这时为了适应特定问题场景，后向次梯度下降转化为了前向后向分割（FOBOS），FOBOS 的全称是 Forward-Backward Splitting，之所以不叫 FOBAS 是为了和之前的 FOLOS Forward-Looking Subgradients 保持一致，避免引起读者的误解。
FOBOS 分为两步进行，对于光滑项梯度下降，对于非光滑项后向次梯度下降。具体形式如下：
\[ \begin{align*} w_{t+\frac{1}{2}} &= w_t - \alpha_t\nabla f(w_t) \\ w_{t+1} &= prox_{\lambda \alpha \Psi}(w_{t+\frac{1}{2}}) \end{align*} \]
统一起来，其形式为
\[w_{t+1} = prox_{\lambda \alpha \Psi}(w_t - \alpha_t\nabla f(w_t))\]
因此 FOBOS 又可以被叫做邻近梯度下降（Proximal Gradient Descent (PGD)）
以上导出 FOBOS 的过程看上去很直观，但实际上缺乏一些理论依据。接下来我们从理论角度重新推导 FOBOS。
首先，对于损失函数，我们采用二阶近似来逼近，用 \(\frac{1}{\eta} I\) 代替 \(\nabla^2 f\)。
\[f(y) \approx f(x) + \nabla f(x)^T (y-x) + \frac{1}{2\eta}||y-x||_2^2\]
实质上，这是一阶逼近加上\(x\)的邻近项。这样一来，在下一个时间点，我们就是要最小化二阶逼近值。通过配完全平方法，我们很容易能得到：
\[w_{t+1} = \arg\min_w \frac{1}{2\eta}||w - (w_t - \alpha_t\nabla f(w_t))||_2^2 + \Psi(w)\]
这就是 FOBOS 的最终形式。
看上去 FOBOS 是比梯度下降复杂多了，实际上不然，在很多场景下邻近算子是非常容易求得的，比如 LASSO。当正则项为 \(L_1\) 的时候，我们把它的邻近算子称为软阙值算子 \(T_\alpha\)（soft-thresholding operator），其形式为：
\[\left[prox_{\alpha ||.||_1}(y)\right]_i = \left\{ \begin{array}{rcl} y_i + \alpha, & & {y_i \leq -\alpha} \\ 0, & & {\vert y_i\vert \leq \alpha} \\ y_i - \alpha, & & {y_i \geq \alpha} \end{array} \right. \]
以上，我们都是在讨论线下场景的凸优化，凸在线学习本质上和线下凸优化是一致的，不过也有一些不同。以梯度下降为例，在线学习中梯度下降的形式为在线梯度下降（OGD），OGD 和 SGD 本质上是相同的，即每次使用一个样本的梯度下降。但是两者应用的场景不同，OGD 适用于线上情景，损失依次到来，其 Regret bound \(\alpha-\) 能达到 \(O(\sqrt(T))\)，Regret 次线性增长能够证明 OGD 是适用于在线学习场景的。另外虽然 SGD 形式和 OGD 一致，但两者思路还是有区别，SGD 的梯度是靠样本去估计的，而 OGD 则是直接进行处理。FOBOS 的在线版本也是同理，Regret bound 在损失函数\(\alpha-\)强凸情况下能达到 \(O(log(T))\)。
Regularized Dual Averaging
SubGD 还有一个问题，在于新的次梯度的权重比老次梯度要低。具体的推导如下：
考虑二阶近似，令 \(Z_t = \sum\limits_{i=1}^t \eta_i\)，\(g_t = \partial f(w_t)\)
\[\begin{align*} w_{t+1} &= \arg \min_w f(w_t) + g_t(w-w_t) + \frac{1}{2\eta_t}||w-w_t||_2^2 \\ &= \arg \min_w \eta_t \left[f(w_t) + g_t(w-w_t)\right] - w^Tw_k + \frac{w^Tw}{2} \\ &= \arg \min_w \eta_t \left[f(w_t) + g_t(w-w_t)\right] - w^T(w_{t-1} - \eta_{t-1}g_{t-1}) + \frac{w^Tw}{2} \\ &= \arg \min_w \frac{\sum_{i=1}^t \eta_i}{\sum_{i=1}^t \eta_i} \left[f(w_i) + g_i(w-w_i)\right] + \frac{||w||_2^2}{2\sum_{i=1}^t \eta_i} \\ &= \arg \min_w \sum\limits_{i=1}^t \frac{\eta_i}{Z_t} \left[f(w_i) + g_i(w-w_i)\right] + \frac{||w||_2^2}{2Z_t} \end{align*}\]
可以看出，老的次梯度相比新的次梯度有更高的权重，这显然不合理。对偶平均（Dual Averaging）通过赋予所有次梯度同等权重，解决了 SubGD 这种缺陷。
定义 \(\hat g_t = \frac{1}{t}\sum\limits_{i=1}^t g_i\)，
\[\begin{align*} w_{t+1} &= \arg \min_w \frac{1}{t} \sum\limits_{i=1}^t \left[f(w_i) + g_i(w-w_i)\right] + \frac{\mu_t ||w||_2^2}{2t} \\ &= \arg \min_w \hat g_t w + \frac{\mu_t ||w||_2^2}{2t} \end{align*}\]
其中 \(\mu_t\) 是步长。
SubGD 的在线版本还有一个额外的缺陷，即无法得到稀疏解，于是微软提出了正则对偶平均（Regularized Dual Averaging (RDA)），能得到比 FOBOS 更稀疏的解。相比于 DA，RDA 增加了一个正则项 \(\Psi\) ，用一个强凸函数 \(h\) 替代了原先的二阶范数，其形式如下：
\[w_{t+1} = \arg \min_w \hat g_t w + \frac{\mu_t}{t}h(w) + \Psi(w)\]
由于是在线算法，因此出于运行效率的考量，通常选取简单形式的 \(h\) 和 \(\Psi\)，比如二阶范数和 \(L_1\) 正则项，令 \(\mu_t = \gamma\sqrt t\)。接下来，我们就来求解这种简单形式的 RDA：
\[w_{t+1} = \arg \min_w \hat g_t w + \frac{\gamma}{2\sqrt t}||w||_2^2 + \lambda ||w||_1\]
将其右式分成 \(n\) 个独立式分别求解，令 \(\gamma_t = \frac{\gamma}{\sqrt t}\)，这就转化为了：
\[minimize \ \, \hat g_tw + \lambda \vert w \vert + \frac{\gamma_t}{2} w^2\]
求导之后可得，
\[g_t + \lambda \delta + \gamma_t w^* = 0\]
其中 \(w^*\) 是最优解，\(\delta \in \partial \vert w \vert\)，之后根据 \(\delta\) 的取值分情况讨论，最终可以得到 RDA 的闭式解，
\[w_{t+1}^{(i)} = \left\{ \begin{array}{lcr} 0, & & {\vert \hat g_t^{(i)} \vert \leq \lambda} \\ -\frac{\sqrt t}{\gamma}(\hat g_t^{(i)} - \lambda sgn(\hat g_t^{(i)})), & & {otherwise} \end{array} \right. \]
FOBOS + RDA = FTRL-Proximal
现在我们有了两个 SubGD 加强版算法，FOBOS 以及 RDA。FOBOS 相比 RDA 能够达到更高的精度，而 RDA 能够得到更稀疏解，Google 融合两者各取所长提出了如今在工业界中应用甚广的 FTRL Proximal。
为了看得更清楚一些，我们把 FOBOS 和 RDA 写成相似的形式（推导过程不严格）：
\[\begin{align*} FOBOS \qquad w_{t+1} &= \arg\min_w \frac{1}{2\eta}||w - (w_t - \alpha_tg_t)||_2^2 + \lambda ||w||_1 \\ &= \arg\min_w g_tw + \lambda ||w||_1 + \frac{1}{2}||Q_{1:t}^{1/2}(w-w_t)||_2^2 \end{align*}\]
\[\begin{align*} \qquad RDA \qquad \; w_{t+1} &= \arg \min_w \hat g_t w + \lambda ||w||_1 + \frac{\mu_t}{2t}||w||_2^2\\ &= \arg \min_w g_{1:t}w + t\lambda||w||_1 + \frac{1}{2}\sum\limits_{i=1}^t||Q_i^{1/2}(w-0)||_2^2 \end{align*}\]
在这里 \(Q\) 是学习率，\(g_t\) 是损失函数的梯度，\(g_{1:t} = \sum_{i=1}^t g_i\)。从以上可以看出，更新式分为三项，第一项是损失函数的一阶近似，第二项是非光滑正则项，此处为 \(L_1\) 正则，第三项为强凸正则项，此处为 \(L_2\) 正则。
从通式上我们能看出 FOBOS 和 RDA 总共有三点不同：
FOBOS 的优化只针对了最近的梯度，而 RDA 针对了过去所有的梯度；
RDA 的优化针对了累积的 \(L_1\) 正则，而 FOBOS 只针对了当前的；
FOBOS 强凸项中心化点为 \(w_t\)，而 RDA 的中心化点为 \(0\)；
事实上，Google 在论文中证明了一个等价定理，即 OMD 和 FTLR 等价。如此一来 FOBOS 的更新式能够等价地写成：
\[FOBOS \qquad w_{t+1} = \arg \min_w g_{1:t}w + \phi_{1:t-1}w + \lambda ||w||_1 + \frac{1}{2}\sum_{i=1}^t||Q_i^{\frac{1}{2}}(w-w_i)||_2^2\]
此处 \(\phi\) 是 \(L_1\) 正则的次梯度。这个更新式和 RDA 就更像了。FOBOS 的优化是针对基于次梯度估计的累积 \(L_1\) 正则，经实验验证正是因为次梯度估计的存在才导致了 FOBOS 的稀疏性不如 RDA 来得好。FOBOS 的强凸项中心化点为当前的点而非原点，这个好处是更新后我们不会在预测我们已经见过的样本时有太多偏差，这就是所谓的 Proximal 名字的来历。
FTRL Proximal 在处理稀疏性上和 RDA 一致，处理中心化点上和 FOBOS 一致，如此一来既达到了更好的稀疏性又提升了精确度，其形式如下：
\[w_{t+1} = \arg \min_w g_{1:t}w + t\lambda||w||_1 + \frac{1}{2}\sum\limits_{i=1}^t||Q_i^{1/2}(w-w_i)||_2^2 \]
注意 \(L_1\) 正则前并没有 \(t\) 。 【3】和【4】中 FTRL-Proximal 公式在这一点上是不同的，不过都是 \(\alpha_t\) 的特殊形式，一个是 \(\alpha_t=1\)，一个是 \(\alpha_t =t\)。我特地发邮件问了作者 Brendan McMahan，他的回复是在实践中固定的 \(\lambda_1\) 经常 makes the most sense。
看上去这个优化问题有点复杂，但实质上这和 \(RDA\) 的求解是非常相似的。定义 \(z_t = g_{1:t} - \sum\limits_{i=1}^t \sigma_i w_i\)，其中 \(\sigma_{1:t} = \frac{1}{\eta_t}\)。如此一来，优化式就转化为：
\[w_{t+1} = \arg \min_w z_tw + \frac{1}{\eta_t}||w||_2^2 + \lambda ||w||_1\]
这个形式和上面的 RDA 是一模一样的，求解完全相同。最终结果是：
\[w_{t+1}^{(i)} = \left\{ \begin{array}{lcr} 0, & & {\vert z_t^{(i)} \vert \leq \lambda} \\ -\eta_t(z_t^{(i)} - \lambda sgn(z_t^{(i)}), & & {otherwise} \end{array} \right. \]
FTRL-Proximal 的伪代码如下：
总结归纳
最后，我们对上面讲过的内容做一下总结归纳。
在线学习是一种强大的线上模型训练方法，一个低 Regret 算法能够保证其平均表现和最优决策的平均表现是相当的，我们着重介绍了在线学习中的一大类，一阶凸在线学习，其代表算法是 FTRL。FTRL 通过最小化累计损失来更新参数，加上了正则项来使算法平稳。通过选取不同的损失函数和正则项，FTRL 可以转化为多种形式，比如 OGD。
OMD 也是一种代表算法，它与 FTRL 本质相同，由于其梯度特性被认为是梯度下降类算法的通式。OGD 是 OMD 最简单的形式，它一种高效简洁的在线学习方法，在不少问题上能以很小的计算消耗达到不错的精度，但其有两大缺陷，一是稀疏性不够，即使加上了正则项也会因为浮点数相加而很难得到精确零值。这时可以采用截断法，比较流行的有 Truncated Gradient 以及 FOBOS。二是不能处理非光滑函数，这时就需要用次梯度代替梯度，即 SubGD。SubGD 虽然能处理非光滑，但收敛速度慢，FOBOS 通过向前看一步，有效提升了收敛速度。而且在加上正则项后通过软阙值截断，能达到较好的稀疏性。RDA 也是 SubGD 的加强版，相比 FOBOS 能达到更好的稀疏性，不过由于其中心化点是原点，可能会在预测我们已经见过的样本时有一定偏差。
虽然我们在上面没有提，不过从 FTRL 通式和 RDA 通式能看出两者的相似性，RDA 实质上是 FTRL 家庭中的一员。当我们融合 RDA 和 FOBOS，将 FTRL 和 OMD 相联结，我们就得到了 FTRL-Proximal，既能达到较高的预测精度，又能达到较好的稀疏性。
几点备注
还有几点零碎的我想说的，一并写在这里。
有关工程实现，这方面我不详谈了，毕竟 Google 的论文里写的很详细，网上其他资源翻译的也比较到位。我就来谈谈实践中还有什么注意点。特征尺度是个需要考虑的问题，由于模型大多是线性模型，尺度的不同会对算法有很大的影响。对于这一点，有几个解决方案。一是始终存储着最近的N个样本点，用来计算均值方差，对新来的数据标准化；二是将数值变量分箱离散化，之后转化为二元变量；三是多使用百分率而不是数值，把数据压到0和1之间；四是使用不受特征尺度影响的算法，比如 Normalized Gradient Descent。实践中所有方法都值得一试。还有一点是线性模型的局限性，通常在线学习都会用线性模型，因为它简单效率高，但是要注意线性模型是不能处理非线性的，需要人为的干预。如果特征都是类别变量，比较好的做法是将其两两组合，如果对数值变量进行了分箱，那就能够组合数值变量了。如果没对数值变量分箱，可能需要手动组合特征。特征组合能大大提升线性模型的性能，代价是解释性降低。
Google 在论文中提到，实践中需要对每个特征用不同的学习率，出现次数多的特征学习率要低，出现次数少的特征学习率要高。论文中的学习率设置是和 Adagrad 一致的。其缺点也和 Adagrad 一样，由于线上数据源源不断，学习率可能会出现持续衰减到极小的数值，Adagrad 在深度学习里也是遇到了一样的困境。解决方法可以是设置一个底线，学习率不能低于这个底线。
强化学习和在线学习的联系非常密切，是个值得详谈的点，可惜我当前时间不够多，以后再行补充。
在线学习涵盖广阔，我只是侧重于谈了谈一阶的凸在线学习方法，其中一些高级概念如对偶出于简化论述的缘故都没有涉及。除了一阶凸方法，还有二阶凸方法比如牛顿法，还有多臂赌博机，还有贝叶斯方法等等。总而言之，我所谈到的只是在线学习这个有几十年历史的领域的冰山一角而已，希望这篇博客能将读者领入门，更多地内容希望读者自己去探索学习。
参考文献
【1】 Introduction to Online Convex Optimization. Elad Hazan. Princeton University. 2016.
【2】 Online Learning and Online Convex Optimization. Shai Shalev-Shwartz. 2011.
【3】 Ad Click Prediction: a View from the Trenches. H. Brendan McMahan et.al. Google. 2013.
【4】 Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and L1 Regularization. H. Brendan McMahan. Google. 2011
【5】 Efficient Online and Batch Learning Using Forward Backward Splitting. John Duchi et.al. 2009.
【6】 Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. John Duchi et.al. 2011.
【7】 Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization. Lin Xiao. Microsoft. 2010.
【8】 A Unified View of Regularized Dual Averaging and Mirror Descent with Implicit Updates.H. Brendan McMahan. Google. 2011
【9】 Optimization and Matrix Computation course by Jianfeng Cai. Hong Kong University of Science and Technology. 2017.
【10】 Optimization course by Geoff Gordon. Carnegie Mellon University. 2012.
【11】 Introduction to Online Learning course by Haipeng Luo. University of Southern California. 2017.
【12】 Normalized online learning. Stephane Ross et.al. 2013
【13】A Survey of Algorithms and Analysis for Adaptive Online Learning. H. Brendan McMahan. 2017
【14】Introduction to Online Learning Theory. Wojciech Kot lowski. Institute of Computing Science, Pozna´n University of Technology. 2013
【15】Wikipedia, Quora, StackOverflow, CrossValidated, Zhihu
