Adaptive Calibration in Non-Stationary Environments¶

会议: NeurIPS 2026
arXiv: 2605.11490
OpenReview: https://openreview.net/forum?id=WTLTiMlgq3
论文: https://arxiv.org/abs/2605.11490
领域: 优化/理论
关键词: 在线校准, 非平稳环境, ℓ1/ℓ2校准误差, 伪KL校准, 分段平稳

一句话总结¶

针对序列预测中对抗性校准算法过于保守而平稳算法无法应对漂移的脱节问题，本文提出了能够自适应环境非平稳程度 $C$ 与分段数 $K$ 的在线校准算法体系，在 $\ell_1$、$\ell_2$ 与伪 KL 误差下平滑内插最优独立同分布界与对抗界。

研究背景与动机¶

概率预测的校准性（Calibration）是现代 AI 系统做出可靠决策的基石。在医疗诊断、天气预报及金融风险控制等高风险应用场景中，预测值仅具备平均意义上的准确率远远不够，还必须保证置信度与经验发生频率一致——例如在所有被赋予 0.7 发生概率的事件序列中，实际发生正例的比例应当严格逼近 70%。在实际动态交互中，底层数据生成机制往往随时间持续漂移，这推动了在线校准问题的深入研究。

自 Foster & Vohra (1998) 提出在线校准理论以来，主流理论文献几乎完全聚焦于全对抗设定（Fully Adversarial Regime），即环境产生的结果序列可以是任意恶意的。为了应对极端对抗，现有最优显式算法展现出极高的保守性，在 $\ell_1$ 校准误差上仅能达到 $\widetilde{\mathcal{O}}(T^{2/3})$，在 $\ell_2$ 和伪 KL 校准误差上仅能达到 $\widetilde{\mathcal{O}}(T^{1/3})$。然而，真实世界环境往往具备更良性的演化规律，例如在相当长的时间窗口内呈现统计平稳或缓慢漂移。当真实数据退化为独立同分布（i.i.d.）分布时，简单的倍增分块经验均值预测算法即可获得 $\mathcal{O}(\log^2 T)$ 的 $\ell_2$ 校准误差以及 $\widetilde{\mathcal{O}}(\sqrt{T})$ 的 $\ell_1$ 校准误差；对抗算法在良性环境下反而被严重锁死，完全无法从数据平稳性中获益。

这一现状的核心矛盾在于：如何在完全不预先获知环境漂移量与突变点的前提下，设计出能够自适应环境非平稳程度的在线校准算法，实现从 i.i.d. 平稳基准到全对抗极限的连续平滑内插？核心 idea：以均值序列的中位数最小 $\ell_1$ 偏差 $C$ 和分段数 $K$ 作为非平稳度量，构建基于倍增时间周期与非均匀空间剖分的通用元框架，并在真值邻域配置精细几何分辨率，从而自适应消除平稳与对抗状态之间的理论鸿沟。

方法详解¶

整体框架¶

算法围绕序列二值预测博弈展开：在每个轮次 $t \in [T]$ 中，对手选定伯努利参数 $q_t \in [0,1]$ 并生成真实标签 $y_t \sim \text{Ber}(q_t)$；预测者输出分布 $\mathcal{P}_t$，依分布采样给出预测概率 $p_t \in [0,1]$，随后观测到实际结果 $y_t$。算法的核心逻辑是将整个预测时域划分为长度呈几何级数递增的周期（Epoch $m=1,2,\dots$），在每个周期 $m$（长度为 $s_m=2^m$）内，利用前一个周期的经验结果中心构造一个包含潜在真值的高置信度内部区间，并向两侧构造宽度倍增的外部对数条带；随后在离散化的预测网格上调用专门的底座在线学习算法（如基于 MsMwC 的专家系统、在线梯度下降 OGD 或指数加权在线优化 EWOO）。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}, 'subGraphTitleMargin': {'top': 8, 'bottom': 16}}}%%
flowchart TD
    A["输入历史序列与置信参数 δ"] --> B["自适应重启调度器<br/>双重搜索 C 与平稳性测试"]
    B --> C["周期化时间划分<br/>长度指数翻倍 s_m = 2^m"]
    C --> D["真值邻域非均匀空间剖分<br/>内部高分辨率网格 + 外部指数倍增条带"]
    D --> E["底座校准预测子程序<br/>MsMwC 专家系统 / OGD / EWOO"]
    E --> F["输出校准概率 p_t 并观测 y_t"]
    F -->|触发漂移阈值或周期结束| B

关键设计¶

1. 非平稳度量与自适应双重搜索调度：消除对漂移参数的先验依赖

算法首先建立了以漂移中位数偏差为核心的非平稳度量体系：定义 $p^\star \in \arg\min_{q \in [0,1]} \sum_{t=1}^T |q_t - q|$ 为序列真实均值的中位数，总非平稳偏差定义为 $C = \sum_{t=1}^T c_t = \sum_{t=1}^T |q_t - p^\star|$；同时引入分段平稳段数 $K = 1 + \sum_{t=1}^{T-1} \mathbb{I}\{q_t \neq q_{t+1}\}$。针对 $C$ 和 $K$ 事先未知的根本困难，算法设计了分块（Block）与子块（Sub-block）层次重启框架：每个大块 $b$ 包含 $G_b+1$ 个子块。前 $G_b$ 个子块均作为平稳性检验器，以猜测值 $\widetilde{C}=0$ 启动底座算法，一旦累计校准误差突破平稳置信上界 $U_{\delta'}(\mathcal{T}_\ell^{(b)}, 0)$ 即判定环境发生突变，以此充抵环境跳变数 $K$；而在每个大块的最后一个子块中，算法执行指数倍增猜测 $\widehat{C}^{(b)} = 2^{3b}$。这种嵌套调度机制不仅将未知参数的适应性损失严格压制在 $\log T$ 乘子以内，还赋予算法在连续漂移与突变跳变双维度同时取极小的自适应能力。

2. 周期化非均匀空间剖分：在真值邻域自适应分配超精细几何分辨率

在经典校准算法中，空间均匀剖分会将有限的分辨率资源浪费在远离真实发生率的空白区域，导致在 $\ell_2$ 和 KL 散度等对局部扰动更敏感的强校准指标下无法达成 $C$ 相关的收缩上界。本文提出了周期化非均匀剖分机制：在周期 $m$ 开启时，算法计算上一周期的经验平均发生率 $\widehat{y}_m$，并在其周围界定高置信度核心内部区域 $I_m = [a_m, b_m] = [\widehat{y}_m - 2r_m, \widehat{y}_m + 2r_m] \cap [0,1]$，其中置信半径 $r_m = \sqrt{\iota / s_{m-1}} + C / s_{m-1}$，并对 $I_m$ 进行 $N_m$ 等份的密集均匀划分；而对于外部区域 $[0, a_m)$ 与 $(b_m, 1]$，算法构造 $Q = \lceil\log_2 T\rceil$ 层宽度呈 $2^q r_m$ 指数倍增的外部条带 $L_{m,q}$ 与 $R_{m,q}$，并在各条带内划分 $K$ 个子网格。这种非均匀划分确保了预测点距离真值越近，区间跨度 $\Delta_J$ 越窄，满足 $\Delta_J \le \mathcal{O}(|p_t - p^\star| / K)$，精妙抵消了集中发生点处 $n_J$ 较大所累积的高阶离散化误差。

3. 底座算法的距真值频次约束与拟交换遗憾自界定：闭合收敛证明闭环

针对不同阶数的校准测度，本方法在统一非均匀空间骨架下分别实现了对底层预测子程序的动力学控制。在 $\ell_1$ 校准中，算法依托改进的 MsMwC 专家更新机制，突破性地证明了任意预测区间 $J_i$ 被采样的频次 $n_{J_i}$ 与该区间到真值中位数的几何距离 $d_{J_i}$ 呈严格反比： $$ \sqrt{n_{J_i}} \le \mathcal{O}\left(\frac{\sqrt{\iota}}{d_{J_i}} + \sqrt{\frac{C_{J_i}}{d_{J_i}}}\right) $$ 在此不等式支撑下，对所有远离真值的区间求和通过柯西-施瓦茨不等式得以收敛至 $\widetilde{\mathcal{O}}(\sqrt{NC})$。而在 $\ell_2$ 和伪 KL 校准中，算法将校准误差等价转换为关于平方损失与对数损失的伪交换遗憾（Pseudo Swap Regret），并结合 OGD 和 EWOO 的无遗憾性质导出关键的自界定引理：$\sum_{t \in \mathcal{T}_m} \sum_{s \in \mathcal{Z}_m} \mathcal{P}_t(s)(a_{s,t} - p^\star)^2 \le \mathcal{O}(|\Pi_m|\log T + C_m + \iota)$。在伪 KL 场景下，算法更进一步引入反余弦坐标变换 $\theta(y) = 2\arcsin(\sqrt{y})$，将预测边界与贝努利海灵格几何对齐，一举攻克了对数损失在边界处的无界发散问题。

实验关键数据¶

论文为纯理论机器学习工作，所有结论均以严格的数学定理呈现，并通过严格构造的对抗与平稳实例给出了匹配的上下界证明。

主实验（理论收敛界与运行复杂度对比）¶

下表完整对比了在各校准指标下本文提出的算法与代表性历史文献在不同环境非平稳状态下的理论上界及单轮时间复杂度（其中 $T$ 为博弈轮数，$C \in [0,T]$ 为最小 $\ell_1$ 偏差，$K$ 为分段平稳段数）：

校准指标	方法来源	环境假定	最终校准误差上界	单轮时间复杂度
$\mathrm{Cal}_1$	民间下界 / Qiao & Valiant (2021)	i.i.d.	$\Omega(\sqrt{T})$	–
$\mathrm{Cal}_1$	Dagan et al. (2025)	全对抗	$\widetilde{\mathcal{O}}(T^{2/3-\epsilon})$（非构造性）	–（无显式算法）
$\mathrm{Cal}_1$	本文（均匀剖分，定理 3.1）	任意非平稳	$\widetilde{\mathcal{O}}\big(\min\{\sqrt{T} + (TC)^{1/3}, \sqrt{KT}\}\big)$	$\widetilde{\mathcal{O}}\big(\min\{(T^2/C)^{1/3}, \sqrt{T}\}\big)$
$\mathrm{Cal}_1$	本文（非均匀剖分，定理 F.2）	任意非平稳	$\widetilde{\mathcal{O}}\big(\min\{\sqrt{T} + (TC)^{1/3}, \sqrt{KT}\}\big)$	$\widetilde{\mathcal{O}}\big(1 + \min\{C^{1/3}, \sqrt{K}T^{1/6}\}\big)$
$\mathrm{Cal}_2$	本文下界（定理 A.3）	i.i.d.	$\Omega(\log T)$	–
$\mathrm{Cal}_2$	Foster & Hart / Fishelson / Hu	全对抗	$\widetilde{\mathcal{O}}(T^{1/3})$	$\widetilde{\mathcal{O}}(T^{1/3}) \sim \widetilde{\mathcal{O}}(T^{2/3})$
$\mathrm{Cal}_2$	本文（定理 4.1）	任意非平稳	$\widetilde{\mathcal{O}}\big(\min\{(1+C)^{1/3}, K\}\big)$	$\widetilde{\mathcal{O}}\big(\min\{(1+C)^{1/3}, K\}\big)$
$\mathrm{PKLCal}$	本文下界（推论 A.5）	i.i.d.	$\Omega(\log T)$	–
$\mathrm{PKLCal}$	Luo et al. (2025)	全对抗	$\widetilde{\mathcal{O}}(T^{1/3})$	$\widetilde{\mathcal{O}}(T^{2/3})$
$\mathrm{PKLCal}$	本文（定理 E.10）	任意非平稳	$\widetilde{\mathcal{O}}\big(\min\{(1+C)^{1/3}, K\}\big)$	$\widetilde{\mathcal{O}}\big(\min\{(1+C)^{2/3}, K^2\}\big)$

消融与极端退化分析¶

环境设定	非平稳参数取值	算法在本文框架下的理论界	理论基准最优速率	结论与理论意义
纯平稳环境（i.i.d.）	$C=0, K=1$	$\mathrm{Cal}_1 = \widetilde{\mathcal{O}}(\sqrt{T})$	$\Omega(\sqrt{T})$	达到常数级对数因子以内的极小极大最优平稳速率
纯平稳环境（i.i.d.）	$C=0, K=1$	$\mathrm{Cal}_2 = \mathcal{O}(\log^2 T)$	$\Omega(\log T)$	达成多项式对数界，彻底打破传统对抗算法 $\widetilde{\mathcal{O}}(T^{1/3})$ 瓶颈
纯平稳环境（i.i.d.）	$C=0, K=1$	$\mathrm{PKLCal} = \mathcal{O}(\log^2 T)$	$\Omega(\log T)$	首次在强散度意义下证明平稳极小极大收敛阶
慢漂移平稳环境	$C = \mathcal{O}(T^\alpha), \alpha \in (0, 1)$	$\mathrm{Cal}_2 = \widetilde{\mathcal{O}}(T^{\alpha/3})$	–	误差随漂移率平滑过渡，在小漂移下严格优于对抗算法
全对抗极限环境	$C = \Omega(T), K = \Omega(T)$	$\mathrm{Cal}_1 = \widetilde{\mathcal{O}}(T^{2/3}), \mathrm{Cal}_2 = \widetilde{\mathcal{O}}(T^{1/3})$	现有最佳显式算法上界	无缝回退恢复至经典的对抗最优显式算法保证

关键发现¶

打破均匀网格局限：单纯调节传统算法的均匀剖分粒度无法在 $\ell_2$ 指标下达成 $C$ 自适应，其求和误差项固定包含 $\mathcal{O}(N + T/N^2)$，必须借助围绕真值构造的非均匀几何剖分，才能使得累积离散化残差与预测距离形成平方抵消。
时间复杂度显著下降：非均匀剖分框架不仅强化了统计收敛阶，还使得单轮时间复杂度自适应降解。在平稳环境下，$\mathrm{Cal}_1$ 的每轮预测计算开销从 $\widetilde{\mathcal{O}}(\sqrt{T})$ 陡降至 $\widetilde{\mathcal{O}}(1)$。
度量独立性与不可替代性：尽管满足 $\mathrm{Cal}_1 \le \sqrt{T \cdot \mathrm{Cal}_2}$，但若直接通过 $\mathrm{Cal}_2 = \widetilde{\mathcal{O}}((1+C)^{1/3})$ 转换求解 $\ell_1$ 误差，仅能得到 $\widetilde{\mathcal{O}}(\sqrt{T}(1+C)^{1/6})$，这在中间非平稳区间严格弱于本文定理 3.1 和 F.2 所获得的 $\widetilde{\mathcal{O}}(\sqrt{T} + (TC)^{1/3})$。

亮点与洞察¶

平稳与对抗的统一桥梁：首次将在线校准领域两套长期割裂的方法论（i.i.d. 下简单的经验累积法与全对抗下极度保守的扰动离散化/不动点法）纳入统一的理论自适应体系，实现了无缝平滑内插。
真值几何导向的空间分层：巧妙利用上一周期的均值估计将预测区间划分为一个致密的“内核”与按 $2^q$ 宽度几何发散的“外环”，将大部分预测采样质量锁定在内核，使外环极少被采样的频次惩罚精准中和几何条带的大跨度。
双重未知参数的元自适应转化：借鉴非平稳马尔可夫博弈的前沿技术，通过平稳性检验子块截断与倍增搜索相结合，在无需知道总漂移量 $C$ 和分段数 $K$ 的黑盒场景下，以极轻微的对数开销达成多指标联合自适应。

局限与展望¶

下界匹配度尚待完善：目前所得自适应上界在 $C=0$ 及 $C=\Omega(T)$ 两极与已知下界匹配，但在 $C \in (0, T)$ 的中间非平稳过渡态下，是否存在关于 $C$ 更紧致的信息论极小极大下界仍属未解之谜。
非上下文设定的扩展限制：当前理论与算法均基于非上下文（Non-Contextual）设定推导，直接向高维多校准（Multicalibration）以及多分类决策问题迁移仍面临维度灾难与几何构建复杂性。
其他校准指标的泛化：平滑校准（Smooth Calibration）、距离校准（Distance from Calibration）以及 U-校准在非平稳环境下的自适应推广仍有待探索。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [首次系统性解决在线校准对非平稳环境的平滑自适应，构建了全新的非均匀几何剖分框架]
实验充分度: ⭐⭐⭐⭐⭐ [纯理论工作，给出了极其详尽完备的上下界证明、自适应元调度及计算复杂度分析]
写作质量: ⭐⭐⭐⭐⭐ [概念阐述清晰，数学符号定义严谨，主文直觉与附录严密推导高度统一]
价值: ⭐⭐⭐⭐⭐ [填补了在线学习校准领域长期存在的基础理论空白，为动态序列预测提供坚实理论保障]

校准指标	方法来源	环境假定	最终校准误差上界	单轮时间复杂度
\(\mathrm{Cal}_1\)	民间下界 / Qiao & Valiant (2021)	i.i.d.	\(\Omega(\sqrt{T})\)	–
\(\mathrm{Cal}_1\)	Dagan et al. (2025)	全对抗	\(\widetilde{\mathcal{O}}(T^{2/3-\epsilon})\)（非构造性）	–（无显式算法）
\(\mathrm{Cal}_1\)	本文（均匀剖分，定理 3.1）	任意非平稳	\(\widetilde{\mathcal{O}}\big(\min\{\sqrt{T} + (TC)^{1/3}, \sqrt{KT}\}\big)\)	\(\widetilde{\mathcal{O}}\big(\min\{(T^2/C)^{1/3}, \sqrt{T}\}\big)\)
\(\mathrm{Cal}_1\)	本文（非均匀剖分，定理 F.2）	任意非平稳	\(\widetilde{\mathcal{O}}\big(\min\{\sqrt{T} + (TC)^{1/3}, \sqrt{KT}\}\big)\)	\(\widetilde{\mathcal{O}}\big(1 + \min\{C^{1/3}, \sqrt{K}T^{1/6}\}\big)\)
\(\mathrm{Cal}_2\)	本文下界（定理 A.3）	i.i.d.	\(\Omega(\log T)\)	–
\(\mathrm{Cal}_2\)	Foster & Hart / Fishelson / Hu	全对抗	\(\widetilde{\mathcal{O}}(T^{1/3})\)	\(\widetilde{\mathcal{O}}(T^{1/3}) \sim \widetilde{\mathcal{O}}(T^{2/3})\)
\(\mathrm{Cal}_2\)	本文（定理 4.1）	任意非平稳	\(\widetilde{\mathcal{O}}\big(\min\{(1+C)^{1/3}, K\}\big)\)	\(\widetilde{\mathcal{O}}\big(\min\{(1+C)^{1/3}, K\}\big)\)
\(\mathrm{PKLCal}\)	本文下界（推论 A.5）	i.i.d.	\(\Omega(\log T)\)	–
\(\mathrm{PKLCal}\)	Luo et al. (2025)	全对抗	\(\widetilde{\mathcal{O}}(T^{1/3})\)	\(\widetilde{\mathcal{O}}(T^{2/3})\)
\(\mathrm{PKLCal}\)	本文（定理 E.10）	任意非平稳	\(\widetilde{\mathcal{O}}\big(\min\{(1+C)^{1/3}, K\}\big)\)	\(\widetilde{\mathcal{O}}\big(\min\{(1+C)^{2/3}, K^2\}\big)\)

环境设定	非平稳参数取值	算法在本文框架下的理论界	理论基准最优速率	结论与理论意义
纯平稳环境（i.i.d.）	\(C=0, K=1\)	\(\mathrm{Cal}_1 = \widetilde{\mathcal{O}}(\sqrt{T})\)	\(\Omega(\sqrt{T})\)	达到常数级对数因子以内的极小极大最优平稳速率
纯平稳环境（i.i.d.）	\(C=0, K=1\)	\(\mathrm{Cal}_2 = \mathcal{O}(\log^2 T)\)	\(\Omega(\log T)\)	达成多项式对数界，彻底打破传统对抗算法 \(\widetilde{\mathcal{O}}(T^{1/3})\) 瓶颈
纯平稳环境（i.i.d.）	\(C=0, K=1\)	\(\mathrm{PKLCal} = \mathcal{O}(\log^2 T)\)	\(\Omega(\log T)\)	首次在强散度意义下证明平稳极小极大收敛阶
慢漂移平稳环境	\(C = \mathcal{O}(T^\alpha), \alpha \in (0, 1)\)	\(\mathrm{Cal}_2 = \widetilde{\mathcal{O}}(T^{\alpha/3})\)	–	误差随漂移率平滑过渡，在小漂移下严格优于对抗算法
全对抗极限环境	\(C = \Omega(T), K = \Omega(T)\)	\(\mathrm{Cal}_1 = \widetilde{\mathcal{O}}(T^{2/3}), \mathrm{Cal}_2 = \widetilde{\mathcal{O}}(T^{1/3})\)	现有最佳显式算法上界	无缝回退恢复至经典的对抗最优显式算法保证