技术摘要：实例自适应在线多校准

1. 问题陈述

本文解决了序列预测设置中的在线多校准问题。在该设置中，学习器观察上下文 $x_t$，发布混合预测 $\pi_t$（$[0,1]$ 内预测值的分布），采样得到实现预测 $p_t$，并观察结果 $y_t$。目标是确保预测不仅在整个序列上边缘校准，而且同时在由一组群 $\mathcal{G}$ 定义的许多子序列上校准。

虽然先前的工作已证明多校准在最坏情况的对抗设置中是可达的，其速率为 $\tilde{O}(T^{2/3})$，且已知该速率对于一般对抗者是紧的。然而，算法是否能在不牺牲最坏情况保证的前提下，在“更简单”的实例（例如随机或分段平稳环境）上实现更好的速率，仍是一个未解之谜。本文提出的核心问题是：是否存在单一算法能够实现实例相关的界限，从而在最优随机速率 $\tilde{O}(\sqrt{T})$ 和最坏情况速率 $\tilde{O}(T^{2/3})$ 之间进行插值？

2. 方法论

作者提出了一种基于动态分箱细化和休眠专家的高效单一算法。

2.1 动态二分网格

与维持预测空间固定离散化的标准在线校准算法不同，该算法维护区间 $[0, 1]$ 的自适应二分划分（树）。

• 初始化：过程从单个分箱 $[0, 1]$ 开始。
• 细化阈值：仅当分配给该区间 $I$ 的总“播放量”（分配的概率质量），记为 $N(I)$，超过与 $L/w_I^2$ 成正比的阈值时，区间 $I$ 才会分裂为两个子区间。其中 $w_I$ 是区间的宽度，$L = \log(eT|\bar{\mathcal{G}}|)$。
• 原理：该阈值平衡了两个误差源：确定性离散化误差（随 $N(I)w_I$ 缩放）和控制偏差的遗憾成本（随 $\sqrt{N(I)L}$ 缩放）。仅当离散化误差成为偏差的主要来源时，才进行分裂。

2.2 休眠专家封装

该算法采用休眠专家框架（通过置信度评分的 AdaNormalHedge 实例化）来管理偏差控制。

• 专家：对于每个群 $g$、区间 $I$ 和符号 $\sigma \in \{+, -\}$，都有专家跟踪加权符号偏差 $\phi^\pm_{g,I}$。
• 可行性：在每一轮中，学习器求解一个线性规划，以在当前活跃分箱上找到混合预测 $\pi_t$，使得对于任何可能的结果 $y \in [0, 1]$，聚合的一步偏差均为非正。这确保了没有任何活跃偏差项的凸组合能被对抗者利用。

2.3 复杂度度量：阈值复杂度

算法的性能由一种新的实例复杂度度量多尺度阈值复杂度（$\Gamma^{thr}_T$）决定。

• 定义：该度量量化了可预测均值过程 $\mu_t$ 能被一个“分数”函数 $f$ 逼近的程度，其中 $f$ 的水平集（阈值）可以表示为群函数 $\bar{\mathcal{G}}$ 的低权重线性组合。
• 直觉：如果均值过程频繁变化，但这些变化可以通过群结构预测（即均值的阈值符号可由群表示），则复杂度保持较低，从而实现更快的收敛。

3. 主要贡献与结果

3.1 主定理

本文证明了动态分箱算法的多校准误差由多尺度阈值复杂度的函数界定。具体而言，以高概率：
$$\text{MCerr}_{\mathcal{G}}(T) \leq C \min \left\{ T^{2/3}L^{1/3}, \sqrt{TL(1 + \Gamma^{thr}_T)} + L(1 + \Gamma^{thr}_T) \right\}$$
该界限在最坏情况与实例相关机制之间平滑插值。

3.2 特定机制

本文推导了几个推论，展示了算法的适应性：

1. 最坏情况对抗：对于多项式大小的群族，该算法恢复了已知的最优速率 $\tilde{O}(T^{2/3})$。
2. 随机（边缘）设置：在没有群（或群平凡）且均值平稳的情况下，算法实现 $\tilde{O}(\sqrt{T})$ 的速率。
3. 分段平稳均值：如果均值最多变化 $J-1$ 次，速率提升至 $\tilde{O}(\sqrt{JT})$。
4. 一般阈值可表示均值：对于均值由具有 $K$ 个层级且表示成本为 $B$ 的分数逼近的序列，速率为 $\tilde{O}(\sqrt{BKT})$。

3.3 紧性

作者证明了 $\Gamma^{thr}_T$ 的依赖关系在对数因子范围内是紧的。他们构建了一个基于有序网格上 Walsh 族的参数化下界实例，其中阈值复杂度随网格大小 $m$ 缩放，且多校准误差的下界为 $\tilde{\Omega}(\sqrt{mT})$。这证实了该算法的上界对于一般实例无法显著改进。

4. 意义与主张

本文声称提供了首个实现在线多校准“两全其美”保证的单一高效算法。

• 超越最坏情况：对于底层均值过程具有群族可见结构的实例，它突破了最坏情况 $\tilde{O}(T^{2/3})$ 的障碍。
• 自适应细化：核心创新在于预测网格的自适应细化，这使得算法能够“生长”出针对特定数据轨迹量身定制的预测值树，而不是依赖固定的离散化。
• 统一框架：该结果将边缘校准、多校准以及各种非平稳设置统一在一个复杂度度量（阈值复杂度）下，表明多校准的难度根本上取决于群函数预测均值过程阈值符号的能力。

作者强调，他们的分析在标准设置中恢复了已知的最优速率，同时自动适应更简单的实例，这是此前在线多校准文献中尚未实现的特质。