二阶专家建议界 | Codeboy's Blog

形式陈述

一个规范结论

采用全信息专家协议， $N\ge1$ 、 $T\ge1$ ，每轮损失向量属于 $[0,1]^N$ 。先固定对每个专家都为正的先验 $\pi\in\Delta_N$ 。记混合损失 $\widehat\ell_t=\sum_i p_{t,i}\ell_{t,i}$ ，相对差 $r_{t,i}=\widehat\ell_t-\ell_{t,i}\in[-1,1]$ ，以及

R_{T,i}=\sum_{t=1}^T r_{t,i},\qquad V_{T,i}=\sum_{t=1}^T r_{t,i}^2.

存在参数自适应算法，例如采用合适学习率先验的 Squint，使对所有专家 $i$ 同时有

R_{T,i} \le C_1\sqrt{V_{T,i}\bigl(\ln(1/\pi_i)+\ln\ln(e+T)\bigr)} +C_2\bigl(\ln(1/\pi_i)+\ln\ln(e+T)\bigr),

其中 $C_1,C_2$ 是普适常数。均匀先验时 $\ln(1/\pi_i)=\ln N$ 。这是 Koolen–van Erven 定理中对单个专家取值并放松常数后的形式；无需预知每位专家的 $V_{T,i}$ 。学习率混合的完整参数估计见其 Theorems 3–4，下面先证明固定学习率的核心不等式。

固定学习率的二次修正

固定 $0<\eta\le1/2$ 。在第 $t$ 轮开始时令

w_{t,i}=\pi_i\exp\!\left(\eta R_{t-1,i}-\eta^2V_{t-1,i}\right), \qquad p_{t,i}=\frac{w_{t,i}}{\sum_jw_{t,j}}.

这是累计权重本身；每轮的乘法因子是 $\exp(\eta r_{t,i}-\eta^2r_{t,i}^2)$ ，不能每次再乘一遍累计指数。

在 $x\in[-1/2,1/2]$ 上有 $e^{x-x^2}\le1+x$ 。令 $W_t=\sum_iw_{t,i}$ ，并注意 $\sum_i p_{t,i}r_{t,i}=0$ ，便得到

W_{t+1}\le\sum_iw_{t,i}(1+\eta r_{t,i})=W_t.

初始 $W_1=1$ ，而每个末权重都不超过 $W_{T+1}$ ，故

\pi_i e^{\eta R_{T,i}-\eta^2V_{T,i}}\le1, \qquad R_{T,i}\le\frac{\ln(1/\pi_i)}{\eta}+\eta V_{T,i}.

知道二阶量后，可在允许区间内优化 $\eta$ ；小二阶量时仍须保留边界步长带来的加性项。与普通 Hedge相比，这里明确增加了专家各自的二次修正，不能把同一个 $V_{T,i}$ 界直接赋给未经修正的算法。

Squint 再对学习率作混合。其预测权重包含额外的 $\eta$ 因子：

p_{t,i}\propto\pi_i\int_{(0,1/2]} \eta e^{\eta R_{t-1,i}-\eta^2V_{t-1,i}}\,\gamma(d\eta).

它让势函数的一阶增量抵消；仅对累计专家权重作普通平均，并不能自动保持这个不变量。适当选择 $\gamma$ 后，学习率适应所付的代价成为上面的对数对数项。

这里的 $V_{T,i}$ 是实际序列上的相对损失平方和，不是损失随机变量的总体方差。环境可以完全确定或对抗，公式仍然有意义。

直觉

为什么看二阶量

Hedge 的经典界把每轮损失范围都按最坏情况计费，最终得到 $O(\sqrt{T\log N})$ 。若所有专家在多数轮给出几乎相同的损失，学习器其实没有付出多少选择代价； $T$ 却仍把这些无争议轮完整计入。二阶界改用观察到的损失差平方，让有信息的分歧轮而非日历长度主导复杂度。

当学习器与某个专家的每轮表现接近时，该专家的 $V_{T,i}$ 就保持较小；不同专家拥有各自的二阶预算，不必共用一个最坏波动值。

例子与边界

一个容易序列

假设所有专家每轮损失都落在某个共同值的 $10^{-3}$ 邻域。无论轮数多大， $|r_{t,i}|\le2\times10^{-3}$ ，所以 $V_{T,i}\le4\times10^{-6}T$ 。在平方根主项占优时，相对于用 $T$ 代替 $V_{T,i}$ ，这一项约缩小到 $1/500$ ；加性的复杂度项不会同时缩小。它反映的是专家之间的损失分歧很小。

相反，若每轮有专家损失 $0$ 、另一些损失 $1$ ，且领先者不断变化， $V_{T,i}$ 可与 $T$ 同阶，结论便回到平方根于 $T$ 的最坏尺度，同时保留所选自适应版本的对数对数项。二阶界没有承诺在真正困难的序列上突破 minimax 下界。

边界

二阶保证仍相对固定专家。环境发生制度切换时，某个固定专家的 $V_{T,i}$ 小不代表动态比较器表现好，应转向漂移比较器。部分反馈下无法观察所有 $r_{t,i}$ ，还需要重要性加权估计，方差可能因小抽样概率放大。

推论与应用

与 small-loss 界的关系

因为 $r_{t,i}^2$ 可由学习器损失和专家损失控制，二阶界常推出依赖最佳专家累计损失 $L_i$ 的 small-loss bound，例如得到以 $\sqrt{L_i}$ 为主的界，并保留相应先验代价及学习率适应项。但从哪个二阶量推到哪个 small-loss 形式需要损失范围和代数不等式；二者不应直接当同义术语。

AdaHedge 通过 mixability gap 自调学习率，Squint 通过对学习率积分得到专家逐一二阶界。它们共享目标但机制不同。本页保留一个规范定理，不并列堆砌算法名；若实现具体算法，应以所引用论文的更新式和常数为准。比较器允许随时间变化时，则应转向自适应遗憾与漂移比较器，而不是继续套固定专家的二阶量。

参考资料

Nicolò Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz, “Improved Second-Order Bounds for Prediction with Expert Advice,” Machine Learning, 2007.
Wouter Koolen and Tim van Erven, “Second-Order Quantile Methods for Experts and Combinatorial Games,” COLT, 2015，§2 Equation(5)、Lemma1 与 Theorems3–4。
Steven de Rooij et al., “Follow the Leader If You Can, Hedge If You Must,” JMLR, 2014.

形式陈述 ​

一个规范结论 ​

固定学习率的二次修正 ​

为什么看二阶量 ​

一个容易序列 ​

边界 ​

与 small-loss 界的关系 ​

反向链接