在线学习 FTRL：大规模稀疏特征的跟随正则化

在点击率预估、推荐系统等场景中，数据以流式形式不断产生，特征维度可高达数十亿且极度稀疏。FTRL（Follow The Regularized Leader）算法正是为此而生，它兼具在线学习的实时性与稀疏模型的内存效率，是工业界最成熟的大规模逻辑回归训练方案之一。

本教程将从零带你理解 FTRL 的核心思想、公式推导与工程实践，让你能够快速上手实现一个高效的 FTRL 模型。

1. 从在线学习讲起

传统机器学习使用全量离线数据进行批量训练，但在真实业务中，数据通常是按时间顺序到达的数据流。在线学习（Online Learning）的目标是：每来一条新样本，模型立刻更新一次参数，并用更新后的模型对下一条样本进行预测。

1.1 通用在线学习框架

设模型参数为向量 w，在时刻 $t$ 我们先看到特征 x_t，然后给出预测值 $\hat{y}_t = \sigma(\mathbf{w}_t \cdot \mathbf{x}_t)$，其中 $\sigma$ 为 sigmoid 函数。真实标签 $y_t$ 随后揭晓，我们根据损失 $L_t(\mathbf{w}) = \ell(y_t, \hat{y}_t)$ 更新参数。

这种将“预测-反馈-更新”循环在线完成的范式就是在线学习。

1.2 在线梯度下降（OGD）

最直接的想法是对每一条样本执行一次梯度下降：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t - \eta_t \nabla L_t(\mathbf{w}_t) $$

这就是 Online Gradient Descent，简单有效。但它有两个严重缺陷：

• 稀疏性差：即使特征向量极稀疏，更新后几乎所有坐标都会变为非零值，导致模型体积爆炸。
• 正则化耦合不强：在线场景下，如果只是简单地在损失中加上 L1/L2 正则项，并不能得到真正稀疏的解，因为一次梯度更新很难将已非零的权重精确推向零。

FTRL 正是为解决上述问题而诞生的。

2. 从 OGD 到 FTRL 的直觉

2.1 累计损失的优化视角

在线学习的性能通常用遗憾值（regret）衡量：算法在 $T$ 轮后累积损失 $\sum_{t=1}^T L_t(\mathbf{w}_t)$ 与事后最优固定参数 $\mathbf{w}^*$ 的损失之差。我们希望 regret 次线性于 $T$。

OGD 选择了每步局部更新的策略，而 FTRL 则换了一种思路：在每一时刻，考虑所有历史损失，求解一个优化问题得到当前最优参数。具体地，在第 $t$ 轮，我们令

$$ \mathbf{w}{t} = \arg\min{\mathbf{w}} \left( \sum_{s=1}^{t-1} L_s(\mathbf{w}) + \frac{1}{2\eta} |\mathbf{w}|_2^2 \right) $$

这就是 Follow The Leader (FTL) 的原型：选择历史上累计损失最小的参数作为当前参数。但 FTL 在实践中非常不稳定（会震荡），因此需要加上一个正则化项来稳定解——这就是 Follow The Regularized Leader (FTRL)。

实际上，为了适用于大规模数据，通常使用线性近似来简化求解：

$$ \mathbf{w}{t} = \arg\min{\mathbf{w}} \left( \sum_{s=1}^{t-1} \mathbf{g}_s^\top \mathbf{w} + r(\mathbf{w}) \right) $$

其中 $\mathbf{g}_s = \nabla L_s(\mathbf{w}_s)$ 是损失在 $\mathbf{w}_s$ 处的梯度，$r(\mathbf{w})$ 是正则化项。这样做虽然损失了非线性精度，但让每步更新成为闭式解，速度极快。

2.2 为什么 FTRL 能得到稀疏解？

关键在于 $r(\mathbf{w})$ 的设计。我们希望 $r(\mathbf{w})$ 同时包含 L1 和 L2 正则，并且能够自适应地控制每个维度的学习率。FTRL 的一个重要变体 FTRL-Proximal 把正则项写为：

$$ r(\mathbf{w}) = \lambda_1 |\mathbf{w}|_1 + \frac{1}{2} \lambda_2 |\mathbf{w}|2^2 + \frac{1}{2} \sum{i=1}^d \frac{\sigma_i^{(t)}}{\eta} w_i^2 $$

其中 $\sigma_i^{(t)}$ 源自历史梯度的平方和，$\eta$ 是全局学习率。这种 per-coordinate 的学习率调整使得算法能对不同特征采取不同的更新步伐，配合 L1 正则项，大量不活跃特征的权重会自然地被推向零并被截断，从而实现极高的模型稀疏性。

3. FTRL-Proximal 算法详解

目前工业界最广泛使用的是 FTRL-Proximal，其更新公式具备优雅的闭式解。下面我们逐步推导。

3.1 优化目标

我们在第 $t$ 轮需要求解：

$$ \mathbf{w}{t} = \arg\min{\mathbf{w}} \left( \mathbf{g}{1:t-1}^\top \mathbf{w} + \sum{i=1}^d \frac{1}{2\eta_{t,i}} (w_i - w_{t-1,i})^2 + \lambda_1 |\mathbf{w}|_1 + \frac{\lambda_2}{2} |\mathbf{w}|_2^2 \right) $$

其中：

• $\mathbf{g}_{1:t-1}$ 是前 $t-1$ 轮所有梯度之和（或平均梯度与 $t-1$ 的乘积，实际实现中往往维护累计梯度）。
• 第二项是邻近项，用每个坐标独立的学习率 $\eta_{t,i}$ 惩罚参数与上一时刻的偏移，能有效稳定更新。
• 最后两项是经典的 Elastic Net 正则化。

3.2 Per-Coordinate 学习率

为了保证收敛性并自适应特征频率，$\eta_{t,i}$ 常取为：

$$ \eta_{t,i} = \frac{\alpha}{\beta + \sqrt{\sum_{s=1}^{t-1} g_{s,i}^2}} $$

其中 $\alpha, \beta$ 是超参数，$g_{s,i}$ 是第 $s$ 轮第 $i$ 维的梯度。这正是 AdaGrad 风格的动态学习率：频繁出现的非零特征梯度平方和大，学习率会自动变小；稀疏特征梯度和为零，学习率保持较大，有利于罕见特征的快速学习。

3.3 闭式解推导

将优化目标对 $w_i$ 求导（忽略不可导的绝对值部分，用次梯度处理），并令导数为零，可得每个坐标的独立更新规则。

设累计梯度 $z_{t,i} = \sum_{s=1}^{t-1} g_{s,i}$，其更新为 $z_{t,i} = z_{t-1,i} + g_{t,i} - \frac{1}{\eta_{t,i}} (w_{t,i} - w_{t-1,i})$ 实际上更常见的实现是维护累加量：对于逻辑回归，$g_{t,i} = (\sigma(\mathbf{w}_t^\top \mathbf{x}t) - y_t) x{t,i}$。

推导闭式解时，令：

$$ \theta_i = z_{t,i} - \sum_{s=1}^{t-1} \frac{1}{\eta_{s,i}} (w_{s,i} - w_{s-1,i}) \quad \text{（实际中用中间变量简化）} $$

最终得到著名的 per-coordinate 更新公式：

$$ w_{i} = \begin{cases} 0, & \text{if } |z_i| \le \lambda_1 \ -\frac{1}{\lambda_2 + \frac{1}{\eta_i}} (z_i - \operatorname{sgn}(z_i) \lambda_1), & \text{otherwise} \end{cases} $$

其中 $z_i$ 是某种累积梯度统计量。在典型的 FTRL 工程实现中，会维护两个累积量：n_i（梯度累积和）和 z_i（类似动量的累积）。具体更新流程如下。

4. 工程实现与伪代码

下面给出逻辑回归 + FTRL-Proximal 的简洁实现框架。我们假设样本标签为 ${0,1}$，使用 sigmoid 函数预测。

4.1 初始化与超参数

• 全局参数：$\alpha, \beta, \lambda_1, \lambda_2$
• 对第 $i$ 个特征维，维护：
  • $z_i = 0$：梯度带 L1 修正的累积量
  • $n_i = 0$：梯度平方累积量
  • $w_i = 0$：当前权重

4.2 单样本更新步骤

对于每个到来的样本 $(\mathbf{x}, y)$：

1. 计算预测值
   $p = \sigma(\mathbf{w} \cdot \mathbf{x})$

2. 对每个非零特征 $i$，计算梯度
   $g_i = (p - y) \cdot x_i$

3. 更新每个特征维的中间变量
   对于每个 $i$ where $x_i \neq 0$：

   • $\sigma_i = \frac{1}{\alpha}\left(\sqrt{n_i + g_i^2} - \sqrt{n_i}\right)$
     注：这里 $\sigma_i$ 用于计算动态学习率。
   • $z_i \leftarrow z_i + g_i - \sigma_i w_i$
   • $n_i \leftarrow n_i + g_i^2$

4. 更新权重
   对于上述 $i$：

   • 若 $|z_i| \le \lambda_1$ 则 $w_i = 0$
   • 否则 $w_i = -\frac{1}{\lambda_2 + \frac{\beta + \sqrt{n_i}}{\alpha}} (z_i - \operatorname{sgn}(z_i) \lambda_1)$

只有在样本中出现的特征才会被更新，这极大节省了计算，同时没有出现的特征保留原值（大部分为0）。

4.3 重要工程技巧

• 哈希特征处理：若特征用哈希映射，可能只学习出现的特征，未知特征直接设0。
• 惰性更新：由于大量特征 $z_i$ 累积量可能因长期未更新而过时，可以记录最后更新时间戳，在需要使用前修正，但一般忽略以保持速度和稀疏性。
• 冷启动与学习率：$\alpha, \beta$ 通常选 0.1 与 1，$\lambda_1$ 是控制稀疏度的关键，可尝试从 1e-5 到 1e-1 搜索，$\lambda_2$ 较小如 0.1 ~ 1。

5. FTRL 与其它在线算法的对比

FTRL 将 FTL 的全局优化视角与 AdaGrad 的 per-coordinate 学习率以及 L1/L2 正则解耦合，形成了一套理论优雅且实现高效的框架。

6. 理论与实践总结

FTRL 的成功可以归纳为三点：

1. 跟随正则化领导者的原则：每一轮都基于所有历史数据和正则项求全局解，避免了 OGD 的短视。
2. 动态 per-coordinate 学习率：嵌入梯度平方和，让低频特征保持大学习率，高频特征自动衰减，非常适合稀疏 ID 特征。
3. L1 正则+阈值截断的闭式更新：使更新算法同时产出稀疏模型，无需额外剪枝。

如果你正要搭建一个高维稀疏场景的在线学习系统，从 FTRL 起步是非常可靠的选择。理解其核心思想后，你可以轻松扩展到各类损失函数（如多分类 softmax），并通过调整正则参数平衡精度与模型体积。