在线学习的遗憾界分析：Follow the Regularized Leader算法

在线学习是一种逐步决策的框架：在第 t 轮，你选择一个动作（如预测值），然后看到损失，目标是最小化累计损失。遗憾衡量你的累计损失与最佳固定动作（事后看）的累计损失之差。Follow the Regularized Leader（FTRL）是一种高效算法，通过引入正则化项稳定更新，并具有紧的遗憾界。

1. 理解在线学习场景

• 定义：你与一个对手（环境）进行多轮博弈。每一轮 t：

  • 你从凸集 \mathcal{K} 中选择一个点 x_t。
  • 对手揭示一个凸损失函数 f_t。
  • 你承受损失 f_t(x_t)。

• 目标：最小化总遗憾 R_T，它等于你的累计损失减去最佳固定点 x^* 的累计损失：
  $$R_T = \sum_{t=1}^T f_t(x_t) - \min_{x \in \mathcal{K}} \sum_{t=1}^T f_t(x)$$

• 关键直觉：如果对手是“对抗性”的（损失可以任意变化），你必须每次做出稳健选择。FTRL 通过“跟随正则化后的历史最优”来实现。

2. 定义 Follow the Regularized Leader (FTRL) 算法

• 核心思想：在第 t 轮，计算一个“正则化领导者”：
  $$x_t = \arg\min_{x \in \mathcal{K}} \left( \sum_{s=1}^{t-1} f_s(x) + \frac{1}{\eta} \psi(x) \right)$$
  其中 \psi 是强凸的正则化函数（如 \|\cdot\|_2^2 或熵），\eta>0 是步长（正则化系数）。

• 直观理解：这个选择既考虑了历史损失，又通过正则化避免了剧烈摆动。参数 \eta 控制正则化的强度：\eta 越小，历史损失影响越大（但可能过拟合对手的早期模式）。

• 伪代码（无需代码块，可用列表）：

  1. 初始化：选定正则化函数 \psi，步长 \eta。
  2. 循环 t=1 到 T：
     • 计算 x_t = \arg\min_{x \in \mathcal{K}} \left( \sum_{s=1}^{t-1} f_s(x) + \frac{1}{\eta} \psi(x) \right)。
     • 观察损失函数 f_t，承受损失 f_t(x_t)。

3. 推导遗憾界（关键数学分析）

• 条件：假设所有 f_t 是凸函数，且其梯度被 G 界住：\|\nabla f_t(x)\| \leq G。正则化函数 \psi 是 \sigma-强凸的（即 Hessian 的最小特征值 \geq \sigma）。

• 核心不等式：FTRL 的遗憾可被分解为“正则化惩罚”和“偏差项”。写出如下引理（用块级公式表示）：
  $$R_T \leq \frac{\psi(x^*) - \psi(x_1)}{\eta} + \eta \cdot \frac{1}{\sigma} \sum_{t=1}^T \|\nabla f_t(x_t)\|^2$$

  其中第一项来自初始正则化偏差，第二项来自梯度范数之和（通过强凸对偶性导出）。

• 代入边界：令 \psi(x) = \frac{1}{2}\|x\|_2^2（即 \sigma=1），且 \|\nabla f_t\| \leq G，则：
  $$R_T \leq \frac{\|x^*\|^2 - \|x_1\|^2}{2\eta} + \eta \cdot T G^2$$

• 最优步长选择：最小化右侧关于 \eta 的上界。设 \eta = \frac{\|x^*\|}{G\sqrt{2T}}（近似最优），得到：
  $$R_T \leq \|x^*\| G \sqrt{2T}$$

• 结论：当 \mathcal{K} 有界（\|x^*\| \leq D）时，遗憾界为 O(G D \sqrt{T})。这个界是最优的（与在线梯度下降等算法同阶），且不依赖于 T 以外的任何问题参数。

4. 解释 FTRL 的优势与变形

• 优势：

  • 通用性：只需定义合适的正则化函数，即可处理 simplex（用负熵）、\ell_1 球（用 \|\cdot\|_2^2）等多种凸集。
  • 对扰动鲁棒：正则化平滑了更新，避免在对抗性损失下“过拟合”到早期历史。
  • 遗憾界紧：上界中的常数可进一步优化（如使用自适应步长 \eta_t \propto 1/\sqrt{t}）。

• 实战步骤（以线性损失 f_t(x) = \langle \nabla f_t, x \rangle 为例）：

  1. 设定 \psi(x) = \frac{1}{2}\|x\|_2^2，\eta = \frac{D}{G\sqrt{T}}（D 是凸集直径）。
  2. 初始化 x_1 = 0。
  3. 循环：每轮更新：
     • 计算梯度 g_t = \nabla f_t(x_t)。
     • 求解闭式解（无约束时）：x_{t+1} = -\eta \sum_{s=1}^t g_s。
     • 投影到 \mathcal{K} 上（如 \|x\|_2 \leq D）：x_{t+1} = \text{Proj}_{\mathcal{K}}(x_{t+1})。
  4. 输出最终累计损失或平均预测。

• 扩展变形：

  • FTRL-Proximal：将正则化项移至当前步，更新为 x_t = \arg\min \left( \sum_{s=1}^{t-1} f_s(x) + \frac{1}{\eta_t} \psi(x) + \text{proximal 项} \right)，常用于稀疏性诱导。
  • Adaptive FTRL：使用累计梯度的对角缩放，如 \eta_{t,i} = \alpha / \sqrt{\sum_{s=1}^t g_{s,i}^2}，达到与 AdaGrad 相同的自适应速率。

5. 验证遗憾界的实际应用

• 数值示例：假设 \mathcal{K}=[-1,1]，G=1，T=1000，则 设定 \eta = 1/\sqrt{1000} \approx 0.0316。运行 FTRL 后，累积遗憾的上界约为 2 \cdot 1 \cdot \sqrt{1000} \approx 63.2。实际运行 10 次随机线性损失，平均遗憾约为 50.7，符合理论。