FTRL算法的数学原理

我们来深入讲解 FTRL（Follow The Regularized Leader）的数学原理。

我将从直观理解、公式拆解、与经典方法的对比、几何解释四个方面，完整地解析其数学原理。

---

直观理解：FTRL这个名字的含义

FTRL的名字“Follow The Regularized Leader”已经揭示了它的核心思想：

• Leader（领导者）：指的是“到目前为止，在所有已见数据上累积损失最小的那个模型权重”。
• Follow The Leader：一个朴素的想法是，每一步都直接采用当前的Leader。但这会导致模型剧烈震荡，因为每个新数据都可能让Leader完全改变。
• Regularized（正则化的）：为了避免震荡，我们不直接跟随Leader，而是跟随一个带有正则化约束的、更稳定的版本。

FTRL的本质：在每一步，寻找一个权重 w，它既要能很好地解释历史数据（Follow the Leader），又要保持稳定和简洁（Regularized）。

---

公式深度拆解

让我们仔细分析图中的公式：

$$w_{t+1} = \arg\min_{w} \bigg( \underbrace{\sum_{s=1}^{t} g_{s} \cdot w}_{\text{累积梯度项}} + \underbrace{\lambda_{1} \| w \|_{1}}_{\text{L1 正则化}} + \underbrace{\frac{\lambda_{2}}{2} \| w \|_{2}^{2}}_{\text{L2 正则化}} + \underbrace{\vphantom{\frac{1}{2}}\text{稳定性项}}_{\text{稳定性约束}} \bigg)$$

第一项：累积梯度项 $ \sum_{s=1}^{t} g_s \cdot w$

• $g_s = \nabla \text{loss}(w_s)$是第 s步的梯度

• 这一项的含义：我们希望新的权重 w的方向与历史所有梯度的加权平均方向一致

• 为什么是点积？在线性近似下，损失函数可写为：

  $$\sum_{s=1}^t \text{loss}_s(w) \approx \text{常数} + \sum_{s=1}^t g_s \cdot (w - w_s)$$

  忽略常数和与 w无关的项，就得到了 $\sum g_s \cdot w$

这一项实现了“Follow the Leader”：让 w朝着能降低历史累积损失的方向调整。

第二项：L1正则化 $ \lambda_1 |w|_1 $

• $\|w\| _1 = \sum_i w_i$是L1范数
• 作用1：产生稀疏性。L1正则化会将不重要的特征的权重压缩到0
• 作用2：特征选择。在CTR预估中，可能有上亿特征，L1正则化能自动选择重要特征
• 几何上，L1约束区域是“菱形”，最优解容易落在坐标轴上（产生0值）

第三项：L2正则化 $ \frac{\lambda_2}{2} |w|_2^2 $

• $\|w\|_2^2 = \sum_i w_i^2$是L2范数的平方
• 作用1：防止过拟合。让所有权重都变小，使模型更平滑
• 作用2：数值稳定性。防止权重过大
• 几何上，L2约束区域是“球形”

第四项：稳定性项（图中未展开）

这是FTRL算法的关键创新点。在实际的FTRL-Proximal算法中，这个“稳定性项”的具体形式是：

$$\text{稳定性项} = \frac{1}{2} \sum_{s=1}^{t} \sigma_s \|w - w_s \|_2^2$$

其中 σs是学习率相关的参数，通常定义为：

$$\sigma_s = \frac{1}{\eta_s} - \frac{1}{\eta_{s-1}}, \quad \eta_s = \frac{\alpha}{\beta + \sqrt{\sum_{i=1}^{s} \|g_i\| _2^2}}$$

稳定性项的几何意义：它惩罚 w与历史各点权重 ws 的偏离。这使得：

1. 更新是平稳的，不会剧烈震荡
2. 结合了“Proximal”方法的思想：每一步不要离历史点太远
3. 保证了理论上的收敛性

---

完整的FTRL-Proximal公式

将稳定性项展开，得到完整的FTRL优化问题：

$$w_{t+1} = \arg\min_{w} \left( g_{1:t} \cdot w + \frac{1}{2} \sum_{s=1}^{t} \sigma_s \|w - w_s\| _2^2 + \lambda_1 \ w\ _1 + \frac{\lambda_2}{2} \ w\ _2^2 \right)$$

其中 $g_{1:t} = \sum_{s=1}^{t} g_s$ 。

---

与经典方法的对比

FTRL vs SGD（随机梯度下降）

SGD更新：

$$w_{t+1} = w_t - \eta_t g_t$$

• 只考虑当前梯度
• 没有显式正则化
• 容易震荡

FTRL更新：

• 考虑所有历史梯度的累积
• 有显式的L1/L2正则化
• 有稳定性约束
• 产生稀疏解

FTRL vs AdaGrad

AdaGrad更新：

$$w_{t+1,i} = w_{t,i} - \frac{\eta}{\sqrt{\sum_{s=1}^t g_{s,i}^2}} g_{t,i}$$

• 有自适应学习率
• 但没有L1正则化（不产生稀疏性）
• 没有稳定性项

FTRL的优势：

1. 有L1正则化 → 稀疏性
2. 有稳定性项 → 更平稳的更新
3. 理论性质更好

---

FTRL的求解：闭式解

虽然优化问题看起来很复杂，但FTRL有逐坐标的闭式解，这是它能实用的关键。

标量情况推导

考虑单个权重分量 wi的更新。省略下标 i简化表示：

FTRL的优化问题对每个坐标是独立的：

$$\min_w \left( z \cdot w + \frac{1}{2} (\beta + \sqrt{n}) w^2 + \lambda_1 w \right)$$

其中：

• $z = \sum_{s=1}^t (g_s - \sigma_s w_s)$（修正后的累积梯度）
• $n = \sum_{s=1}^t g_s^2$（梯度平方和）
• 这里做了近似和简化，详细推导见论文

这个问题的解是软阈值函数：

$$w_{t+1} = \begin{cases} 0 & \text{if } z \le \lambda_1 \\ -\frac{1}{\frac{\beta + \sqrt{n}}{\alpha} + \lambda_2} \left( z - \text{sgn}(z) \lambda_1 \right) & \text{otherwise} \end{cases}$$

多变量情况的更新规则

对于每个特征 i：

$$w_{t+1,i} = \begin{cases} 0 & \text{if } z_{t,i} \le \lambda_1 \\ -\dfrac{1}{\lambda_2 + \dfrac{\beta + \sqrt{n_{t,i}}}{\alpha}} (z_{t,i} - \text{sgn}(z_{t,i}) \lambda_1) & \text{otherwise} \end{cases}$$

其中：

• $$z_{t,i} = g_{1:t,i} - \sum_{s=1}^{t} \sigma_{s,i} w_{s,i}$$
• $$n_{t,i} = \sum_{s=1}^{t} g_{s,i}^2$$
• $$\sigma_{s,i} = \frac{1}{\alpha} \left( \sqrt{n_{s,i}} - \sqrt{n_{s-1,i}} \right)$$

---

数学原理的直观图解

如果以下代码执行后，图中有乱码出现，可以添加以下两行解决：

# 解决方案1：设置字体，避免中文显示为方框
# 方法A：使用系统支持的中文字体（Windows）
plt.rcParams['font.sans-serif'] = ['SimHei', 'Microsoft YaHei']  # 使用黑体或雅黑
plt.rcParams['axes.unicode_minus'] = False  # 正确显示负号

一维情况下的更新

import numpy as np
import matplotlib.pyplot as plt

def ftrl_update(z, n, alpha=0.1, beta=1.0, lambda1=1.0, lambda2=1.0):
    """FTRL更新规则（一维）"""
    if abs(z) <= lambda1:
        return 0.0
    else:
        eta = 1.0 / (lambda2 + (beta + np.sqrt(n)) / alpha)
        return -eta * (z - np.sign(z) * lambda1)

# 对比不同优化器
z_values = np.linspace(-3, 3, 100)
n = 1.0  # 假设梯度平方和为1

plt.figure(figsize=(10, 6))

# SGD
plt.plot(z_values, -0.1 * z_values, 'b-', label='SGD (lr=0.1)', alpha=0.7)

# AdaGrad (学习率衰减)
ada_lr = 0.1 / np.sqrt(n)
plt.plot(z_values, -ada_lr * z_values, 'g-', label='AdaGrad', alpha=0.7)

# FTRL
ftrl_values = [ftrl_update(z, n) for z in z_values]
plt.plot(z_values, ftrl_values, 'r-', linewidth=2, label='FTRL')

# 标记稀疏区域
plt.axvspan(-1, 1, alpha=0.2, color='gray', label='稀疏区域 (|z|≤λ₁)')

plt.xlabel('累积梯度 z', fontsize=12)
plt.ylabel('权重更新 w', fontsize=12)
plt.title('FTRL vs 其他优化器的更新规则', fontsize=14)
plt.legend()
plt.grid(True, alpha=0.3)
plt.axhline(y=0, color='k', linestyle='-', alpha=0.3)
plt.axvline(x=0, color='k', linestyle='-', alpha=0.3)
plt.show()

图形解释：

• 在 $z\le \lambda_1$区域，FTRL直接将权重设为0（稀疏性！）
• 在 $z>\lambda_1$ 区域，FTRL进行软阈值收缩
• 相比SGD/AdaGrad，FTRL有明确的截断机制

二维情况下的优化路径

# 二维优化路径对比
def loss_function(w1, w2):
    """简单的二次损失 + L1正则化"""
    return 0.5 * (w1**2 + w2**2) + 0.1 * (abs(w1) + abs(w2))

# 模拟不同优化器的优化路径
def sgd_path(start, lr=0.1, steps=20):
    path = [start]
    w = np.array(start, dtype=float)
    for _ in range(steps):
        # 梯度 = w + 次梯度符号
        grad = w + 0.1 * np.sign(w)
        w = w - lr * grad
        path.append(w.copy())
    return np.array(path)

def ftrl_path(start, alpha=0.1, lambda1=0.1, steps=20):
    path = [start]
    w = np.array(start, dtype=float)
    z = np.zeros(2)
    n = np.ones(2)  # 初始梯度平方和
    
    for _ in range(steps):
        # 模拟梯度
        grad = w + 0.1 * np.sign(w)
        
        # 更新n和z
        n += grad**2
        sigma = (np.sqrt(n) - np.sqrt(n - grad**2)) / alpha
        z += grad - sigma * w
        
        # FTRL更新
        for i in range(2):
            if abs(z[i]) <= lambda1:
                w[i] = 0.0
            else:
                eta = 1.0 / (0.1 + (1.0 + np.sqrt(n[i])) / alpha)
                w[i] = -eta * (z[i] - np.sign(z[i]) * lambda1)
        
        path.append(w.copy())
    return np.array(path)

# 绘制
w1 = np.linspace(-1.5, 1.5, 100)
w2 = np.linspace(-1.5, 1.5, 100)
W1, W2 = np.meshgrid(w1, w2)
L = loss_function(W1, W2)

plt.figure(figsize=(12, 5))

# 损失函数等高线
plt.subplot(1, 2, 1)
plt.contourf(W1, W2, L, levels=20, alpha=0.7)
plt.colorbar(label='Loss')

# 优化路径
start_point = [1.2, 1.2]
sgd_traj = sgd_path(start_point)
ftrl_traj = ftrl_path(start_point)

plt.plot(sgd_traj[:, 0], sgd_traj[:, 1], 'bo-', label='SGD路径', alpha=0.7)
plt.plot(ftrl_traj[:, 0], ftrl_traj[:, 1], 'ro-', label='FTRL路径', linewidth=2)

plt.xlabel('w1', fontsize=12)
plt.ylabel('w2', fontsize=12)
plt.title('优化路径对比', fontsize=14)
plt.legend()
plt.grid(True, alpha=0.3)

# 稀疏性示意图
plt.subplot(1, 2, 2)
plt.plot(sgd_traj[:, 0], label='SGD: w1')
plt.plot(sgd_traj[:, 1], label='SGD: w1', alpha=0.7)
plt.plot(ftrl_traj[:, 0], label='FTRL: w2', linewidth=2)
plt.plot(ftrl_traj[:, 1], label='FTRL: w2', linewidth=2, alpha=0.7)
plt.axhline(y=0, color='k', linestyle='--', alpha=0.5)
plt.xlabel('迭代步数', fontsize=12)
plt.ylabel('权重值', fontsize=12)
plt.title('权重收敛过程', fontsize=14)
plt.legend()
plt.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

关键观察：

• FTRL路径更直接地趋向原点
• FTRL的权重能精确收敛到0（稀疏性）
• SGD在0附近震荡，无法产生精确的0

---

FTRL的数学创新性总结

理论贡献

1. 统一框架：将在线学习、正则化、稳定性约束统一在一个框架内
2. 闭式解：虽然优化问题复杂，但能导出逐坐标的闭式解
3. 理论保证：有regret bound理论保证，在在线学习场景下是最优的

实际优势的数学原理

优势	对应的数学原理
稀疏性	L1正则化 + 软阈值函数
稳定性	稳定性项 $\sum \sigma_s \ w-w_s\ ^2$
自适应学习率	通过 $n_i = \sum g_i^2$实现
处理大规模数据	逐坐标更新，只更新非零特征

与其他方法的数学联系

FTRL可以看作是以下方法的推广：

1. SGD with L1：当去掉稳定性项和历史累积，退化为SGD with L1
2. AdaGrad：当去掉L1正则化和稳定性项，近似AdaGrad
3. 在线镜像下降：FTRL是OMD的一种特殊形式
4. 近端梯度法：FTRL-Proximal是近端梯度法的在线版本

---

从数学到工程：为什么FTRL有效？

统计学习角度

• 偏差-方差权衡：L1/L2正则化控制模型复杂度
• 在线学习理论：regret bound保证累积损失接近最优
• 稀疏统计理论：L1正则化在适当条件下可恢复真实稀疏模式

优化理论角度

• 收敛性：在凸问题下保证收敛
• 计算效率：逐坐标更新，复杂度O(非零特征数)
• 数值稳定性：自适应学习率避免梯度爆炸

工程实现角度

# FTRL的实际更新公式（工程版本）
for each feature i in non-zero features:
    # 1. 计算梯度
    g_i = (prediction - label) * feature_value[i]
    
    # 2. 更新统计量
    n_i += g_i * g_i
    sigma = (sqrt(n_i) - sqrt(n_i - g_i*g_i)) / alpha
    z_i += g_i - sigma * w_i
    
    # 3. 应用FTRL更新规则
    if abs(z_i) <= lambda1:
        w_i = 0
    else:
        learning_rate = 1.0 / (lambda2 + (beta + sqrt(n_i)) / alpha)
        w_i = -learning_rate * (z_i - sign(z_i) * lambda1)

---

总结：FTRL的数学精髓

图片中的公式：

$$w_{t+1}=\arg \min _{w}\left(\sum_{s=1}^{t} g_{s} \cdot w+\lambda_{1}\|w\| _{1}+\frac{\lambda_{2}}{2}\| w\| _{2}^{2}+\text{稳定性项}\right)$$

包含了FTRL的全部数学思想：

1. 累积经验：$\sum g_s \cdot w$让模型从历史中学习
2. 稀疏简约：$\lambda_1 \|w\|_1$迫使模型简洁，自动特征选择
3. 稳定泛化：$\frac{\lambda_2}{2} \|w\|_2^2$防止过拟合
4. 平稳进化：稳定性项保证更新不过于激进

FTRL的数学之美在于：它将在线学习的动态性、正则化的结构性、优化算法的有效性，完美地融合在一个简洁的公式中。这个公式不仅是理论分析的工具，也直接导出了高效的工程实现，是连接机器学习理论与工业实践的典范。