二阶专家建议界

为什么看二阶量 ​

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

每轮记混合损失

$${\hat{\ell }}_t=\sum _i{p}_{t,i}{\ell }_{t,i}$$

以及相对差

$$r_{t,i}={\hat{\ell }}_t-{\ell }_{t,i}.$$

相对专家 $i$ 的遗憾是 $R_{T,i}=\sum _t{r}_{t,i}$，二阶量为

$$V_{T,i}=\sum _{t=1}^T{r}_{t,i}^2.$$

$V_{T,i}$ 会在学习器与该专家表现接近时保持很小，即使 $T$ 很大。

一个规范结论 ​

存在参数自适应的指数权重算法，例如 Squint，使对任意先验 $\pi$ 和任意专家 $i$，同时有

$$R_{T,i}\le C_1\sqrt{V_{T,i}(\ln \left(1/{\pi }_i\right)+\ln \ln (e+T))}+C_2(\ln \left(1/{\pi }_i\right)+\ln \ln (e+T)),$$

其中 $C_1,C_2$ 是普适常数。均匀先验时 $\ln \left(1/{\pi }_i\right)=\ln N$。文献中的精确算法和低阶项各异，本页选择这一代表结构：对所有比较专家同时成立，主项由该专家自己的 $V_{T,i}$ 控制，并且无需预知它。

若只用一个固定学习率 $\eta$，基础二阶分析通常先给

$$R_{T,i}\le \frac{\ln \left(1/{\pi }_i\right)}{\eta }+c\eta V_{T,i},$$

前提是 $\eta r_{t,i}$ 落在指数不等式允许的范围。知道 $V_{T,i}$ 后优化 $\eta$ 就得到平方根形式；Squint 对学习率再做混合，避免事先知道每位专家的二阶量。

势函数中的二次修正 ​

经典指数权重使用 $e^{\eta r}$，并用一阶加二阶项控制指数：在合适范围内

$$e^{x-x^2}\le 1+x.$$

若给专家权重乘上

$$\exp (\eta R_{t,i}-{\eta }^2{V}_{t,i}),$$

二次项正好抑制过大的乐观累计。对专家求和的势函数不会爆炸，再与单个专家的权重下界比较，就得到“描述代价除以学习率，加学习率乘二阶量”的权衡。

这里的 $V_{T,i}$ 不是随机变量损失本身的总体方差公理库方差Variance随机变量与其期望之差平方的期望。，而是沿着实际在线序列观察到的相对损失平方和。环境可以完全确定、甚至对抗，公式仍有意义。

一个容易序列 ​

假设所有专家每轮损失都落在某个共同值的 ${10}^{-3}$ 邻域。无论轮数多大，$|r_{t,i}|\le 2\times {10}^{-3}$，所以 $V_{T,i}\le 4\times {10}^{-6}T$。二阶主项比最坏界缩小约三个数量级；这准确反映“专家虽多，但意见几乎一样”。

相反，若每轮有专家损失 $0$、另一些损失 $1$，且领先者不断变化，$V_{T,i}$ 可与 $T$ 同阶，结论便自然退回 $O(\sqrt{T\log N})$。二阶界没有承诺在真正困难的序列上突破 minimax 下界。

与 small-loss 界的关系 ​

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

AdaHedge 通过 mixability gap 自调学习率，Squint 通过对学习率积分得到专家逐一二阶界。它们共享目标但机制不同。本页保留一个规范定理，不并列堆砌算法名；若实现具体算法，应以所引用论文的更新式和常数为准。

边界 ​

二阶保证仍相对固定专家。环境发生制度切换时，某个固定专家的 $V_{T,i}$ 小不代表动态比较器表现好，应转向漂移比较器公理库自适应遗憾与漂移比较器Adaptive regret · Shifting regret · Dynamic regret · 漂移遗憾把固定比较器遗憾扩展到切换序列、任意时间区间和逐轮最优动作，并用切换数或路径长度限制基准强度。。部分反馈下无法观察所有 $r_{t,i}$，还需要重要性加权估计，方差可能因小抽样概率放大。

参考资料

• 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.
• Steven de Rooij et al., “Follow the Leader If You Can, Hedge If You Must,” JMLR, 2014.