Optimal Recalibration of an Online Predictor¶

会议: NeurIPS 2026
arXiv: 2607.19689
OpenReview: https://openreview.net/forum?id=IZBCEtLXFZ
代码: https://github.com/chutongyang98/Optimal-Recalibration-of-an-Online-Predictor
领域: 优化/理论
关键词: 在线学习, 校准误差, Blackwell 可逼近性, 在线重校准, Calibeating

一句话总结¶

针对序列预测中模型损失最小化与概率校准往往不可兼得的问题，本文提出了非对称不平衡的 Blackwell 可逼近性框架与二次审计算法，针对任意 Lipschitz 恰当损失实现了最优的 $(\varepsilon, \varepsilon^2)$ 在线重校准与 $\widetilde{\mathcal{O}}(\varepsilon^{-3})$ 轮次下同时达到 $\varepsilon$-校准与 $\varepsilon^2$-calibeating。

研究背景与动机¶

现代机器学习与深度神经网络广泛采用最小化损失（如交叉熵或平方损失）的目标函数进行训练，在分类和回归任务上取得了优异的泛化能力。然而，以损失最小化为导向训练的模型，其输出概率往往缺乏良好的可信度与统计可解释性，出现严重的过自信或未校准现象。在序列决策与在线预测场景中，预测者在每轮根据特征给出概率预测后才能观测到真实标签，这要求预测序列不仅要保持较低的累积损失，还必须满足校准性（例如预测概率为 0.8 时，实际对应标签均值也接近 0.8）。这种对于可解释概率与低损失的双重需求，使得研究者引入了带提示序列的在线预测模型。

然而，在线校准与损失优化之间存在固有的理论张力：纯粹的在线校准算法（如基于 Blackwell 可逼近性或 Minimax 预测的方法）虽然能在 $\mathcal{O}(\varepsilon^{-3})$ 甚至略快的轮次内消除校准误差，但可能彻底破坏原始预测器已有的良好损失；反之，若完全保留提示预测器，模型虽然保留了特征判别力，校准误差却无法消除。先前的在线重校准（Online Recalibration）工作试图在不显著增加损失的前提下对任意黑盒预测进行实时修正，但其收敛轮次依赖极差，先验文献需要高达 $\mathcal{O}(\varepsilon^{-8})$ 或 $\mathcal{O}(\varepsilon^{-4})$ 轮才能达到 $(\varepsilon, \varepsilon^2)$ 重校准；而在能够超越提示序列损失的事后精炼基准（calibeating）方向上，现有算法亦无法在最优收敛率下同时保证校准性。

解决该张力的切入点在于认识到：校准误差与超额损失在尺度上具有天然的不平衡几何结构——当校准误差要求为 $\varepsilon$ 时，恰当损失（如平方损失）下的超额误差必须紧致地控制在 $\varepsilon^2$ 量级。核心 idea：将在线重校准重新建模为不平衡的同时 Blackwell 可逼近性问题，结合非对称公差的混合线性优化预言机（MLOO）与不对称镜像下降，并在 $\mathcal{K}_2$ 范数下引入基于 Savage 表象的二次审计机制，以匹配理论下界的 $\Theta(\varepsilon^{-3})$ 紧致轮次实现了最优重校准以及校准与 calibeating 的完全兼容。

方法详解¶

整体框架¶

本文的方法 pipeline 针对带提示的在线序列预测博弈（Model 1）：环境在第 $t$ 轮选择提示 $q_t \in [0,1]$ 并先将 $q_t$ 透露给学习者；学习者在未观测到真实标签 $y_t \in \{0,1\}$ 前，基于离散网格 $\mathcal{N} = \{i/N\}_{i=0}^N$ 上的概率分布 $\mathbf{a}_t \in \Delta^\mathcal{N}$ 采样并输出标量预测 $p_t \in \mathcal{N}$；随后环境揭示真实标签 $y_t$。学习算法的目标是使预测序列 $p_{[T]}$ 逼近原点对应的校准误差集合与超额损失集合。

整个系统由两大核心算法范式构成： 1. $\mathcal{K}_1$ 重校准（不平衡同时 Blackwell 可逼近性）：将校准向量 $\mathbf{v}^{(1)}$（维度为 $|\mathcal{N}|$）与标量超额损失 $v^{(2)}$ 耦合为双目标向量逼近任务。通过建立具有不对称松弛参数 $(\varepsilon, \varepsilon^2)$ 的几何混合线性优化预言机（MLOO），并在元控制器中运行步长为 $\eta \approx \varepsilon^2$ 的非对称双专家镜像下降，协调两个判别子模块的无悔在线学习更新。 2. $\mathcal{K}_2$ 重校准（上下文二次审计与极小极大预测）：借助 Fenchel 对偶将均方根校准误差 $\mathcal{K}_2^2$ 与由 Savage 表象及梯度共强单调性导出的恰当损失超额转化为统一的二次测试函数族 $\Phi(u, e) = 2ue - u^2$。在每个预测 bin 内维护一组针对指数凹损失的指数加权预测器，再通过求解一个二维零和博弈在线给出极大极小最优预测分布。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["环境输入提示序列<br/>第 t 轮观测提示 qt"] --> B["阶段1：非对称 MLOO 与元镜像下降<br/>耦合校准向量 v1 与超额损失 v2 构造非对称半空间"]
    B --> C["阶段2：采样预测输出 pt<br/>在两相邻网格点间两点支撑随机化输出"]
    C --> D["环境揭示真实标签 yt<br/>产生校准残差 pt - yt 与损失增量"]
    D --> E["阶段3：多目标在线无悔更新<br/>校准判别器 PGD 更新与元权重 wt 调整"]
    E --> F["输出渐近校准且无超额损失预测<br/>同时达成 ε-校准与 ε²-超额控制"]

关键设计¶

1. 非对称混合线性优化预言机（Asymmetric MLOO）：统一几何分割与双目标容忍度

传统 Blackwell 可逼近性要求向量回报落入目标凸集，而同时逼近多个集合需要满足所有半空间约束。在重校准中，校准目标是让 $\mathbf{v}^{(1)}(\mathbf{a}, q, y) = \{\mathbf{a}_s(s - y)\}_{s \in \mathcal{N}}$ 的 $\ell_1$ 范数受控于 $\varepsilon$，而损失目标则要求标量 $v^{(2)}(\mathbf{a}, q, y) = \sum_{s \in \mathcal{N}} \mathbf{a}_s (\ell(s, y) - \ell(q, y))$ 受控于 $\varepsilon^2$。二者容忍度天然不同阶。本文构造了一个参数为 $(\varepsilon^{(1)}, \varepsilon^{(2)}) = (1/N, 4L/N^2)$ 的非对称 MLOO，输入包含判别向量 $\mathbf{u} \in [-1, 1]^\mathcal{N}$、标量凸组合权重 $\mathbf{w} = (\alpha, \beta) \in \Delta^2$ 及提示 $q$。预言机通过利用恰当损失在标签取 0 和 1 时的单调性质，巧妙地在凸多面体空间中寻找一个至多两点支撑于相邻网格点 $\{j/N, (j+1)/N\}$ 的分布 $\mathbf{a} \in \Delta^\mathcal{N}$，使得对任意 $y \in \{0, 1\}$ 同时满足： $$\alpha \sum_{s \in \mathcal{N}} \mathbf{a}_s u_s (s - y) + \beta \sum_{s \in \mathcal{N}} \mathbf{a}_s (\ell(s, y) - \ell(q, y)) \le \frac{\alpha}{N} + \frac{4\beta L}{N^2}$$ 该设计完全消除了先前方法中对两套目标采用相同保守容忍度导致的轮次劣化。

2. 不平衡双专家镜像下降（Imbalanced Mirror Descent）：消除超额损失的累积开销

在元优化层，传统多目标 Blackwell 算法对混合权重 $\mathbf{w}_t$ 运行标准的梯度下降或指数权重，这会导致所有目标均承受等同于 $1/(\eta T) + \eta$ 的后悔值。然而对于超额损失而言，容忍上限仅为 $\varepsilon^2$，若承受 $1/(\eta T) \approx \varepsilon$ 的项将直接导致整个界失效。本文的核心洞见在于：初始化权重固定设定为纯超额损失专家 $\mathbf{w}_1 = \mathbf{e}_2$。由于 Bregman 散度满足 $D_r(\mathbf{e}_2 \parallel \mathbf{e}_2) = 0$ 且 $D_r(\mathbf{e}_1 \parallel \mathbf{e}_2) = 1$，采用步长 $\eta = \Theta(\varepsilon^2 / L^2)$ 时，校准目标支付 $\eta L^2 + 1/(\eta T) = \mathcal{O}(\varepsilon^2 + \varepsilon) = \mathcal{O}(\varepsilon)$ 的后悔率，而超额损失目标由于起点散度为 0，仅承受 $\eta L^2 = \mathcal{O}(\varepsilon^2)$ 的纯方差界，完全避开了 $1/(\eta T)$ 的惩罚，从而在 $T = \Omega(L^2 \varepsilon^{-3})$ 轮次内同时闭合两项上界。

3. 基于 Savage 表象的二次审计机制（Quadratic Audits for $\mathcal{K}_2$ Recalibration）：统一均方根校准与恰当损失

对于均方根校准误差 $\mathcal{K}_2$，利用其平方项的 Fenchel 对偶恒等式：$T \mathcal{K}_2^2 = \sup_{\boldsymbol{\lambda} \in [-1, 1]^\mathcal{N}} \sum_{t=1}^T (2 \boldsymbol{\lambda}_{p_t}(p_t - y_t) - \boldsymbol{\lambda}_{p_t}^2)$。同时，对任意具有 $G$-Lipschitz 连结函数 $\psi(p) = \ell(p, 0) - \ell(p, 1)$ 的恰当损失，利用凸分析中的共强单调性（co-coercivity），超额损失同样被二次测试上界控制： $$\ell(z, y) - \ell(q, y) \le \frac{G}{2} \left( 2 f_z(q)(z - y) - f_z(q)^2 \right), \quad f_z(q) = \frac{\psi(z) - \psi(q)}{G} \in [-1, 1]$$ 本文因此构建了一个通用的二次测试基元 $\Phi(u, e) = 2ue - u^2$。在每个离散预测 bin 内，运行针对 $1/8$-指数凹损失的指数加权专家聚合算法，并在每轮通过求解一个 $2 \times |\mathcal{N}|$ 规模的二维零和博弈极小极大预测分布（可在 $\mathcal{O}(|\mathcal{N}|)$ 时间内完成），将博弈支付稳定在 $1/(4N^2)$，最终以极为优美的纯解析结构实现了近乎无额外常数开销的 $\widetilde{\mathcal{O}}(L^{3/2} \varepsilon^{-3})$ 阶 $\mathcal{K}_2$ 紧致重校准。

损失函数 / 训练策略¶

算法属于在线无模型预测后处理框架，无需反向传播梯度训练网络权重。算法在每轮维护内部状态： 1. 在线判别器更新：针对校准向量空间的判别子 $\mathbf{u}_t \in [-1, 1]^\mathcal{N}$，采用欧氏球上的投影梯度下降（PGD），步长设为 $\eta_u = \varepsilon / 16$； 2. 元权重更新：对双目标混合向量 $\mathbf{w}_t \in \Delta^2$，根据第 $t-1$ 轮的经验无偏梯度反馈 $\tilde{\mathbf{g}}_{t-1}$ 进行投影梯度下降：$\mathbf{w}_t \leftarrow \arg\min_{\mathbf{w} \in \Delta^2} \{ -\langle \eta \tilde{\mathbf{g}}_{t-1} + \mathbf{w}_{t-1}, \mathbf{w} \rangle + \frac{1}{2} \|\mathbf{w}\|_2^2 \}$，步长设定为 $\eta = \varepsilon^2 / (16 L^2)$； 3. 离散网格超参：网格大小严格配置为偶数 $N = 2 \lceil 2\sqrt{L} / \varepsilon \rceil$，保证在理论下界允许的时间视界 $T = \Theta(L^2 \varepsilon^{-3})$ 内完全满足 $(\varepsilon, \varepsilon^2)$ 上界。

实验关键数据¶

主实验¶

论文在 CIFAR-10 猫狗二分类子集（CIFAR-2）上进行了在线概率预测评估，采用 40 层 DenseNet-BC 作为基础模型（输出为未校准提示 $q_t$）。在总轮次 $T = 200,000$ 的数据流中，前 100,000 轮为平稳分布，后 100,000 轮引入概念漂移（标签以概率 $\beta = 0.2$ 发生随机翻转），测试算法在分布漂移下的自适应重校准能力。

预测方法	Brier Score ($\downarrow$)	$\mathcal{K}_1$ 校准误差 ($\downarrow$)	$\mathcal{K}_2^2$ 均方校准误差 ($\downarrow$)	0-1 分类准确率 (%) ($\uparrow$)
原始提示 (Hint)	$0.16124 \pm 7.8\text{e-}4$	$0.15413 \pm 8.4\text{e-}4$	$0.02976 \pm 3.0\text{e-}4$	$82.075 \pm 0.082$
在线精炼 (Calibeating)	$0.13865 \pm 5.4\text{e-}4$	$0.05771 \pm 5.1\text{e-}4$	$0.00663 \pm 1.0\text{e-}4$	$82.428 \pm 0.084$
在线重校准 (Recalibration, 本文)	$0.14708 \pm 8.3\text{e-}4$	$\mathbf{0.01188 \pm 2.5\text{e-}4}$	$\mathbf{0.00052 \pm 0.5\text{e-}4}$	$78.597 \pm 0.308$
组合策略 (Calibeating + Recalibration, 本文)	$\mathbf{0.13314 \pm 4.5\text{e-}4}$	$0.01319 \pm 4.5\text{e-}4$	$0.00090 \pm 0.3\text{e-}4$	$\mathbf{82.408 \pm 0.088}$

消融实验¶

为了验证多分类设置下的投影拓展性，论文在 CIFAR-100（100 类，数据流长度 $T = 1,000,000$）上进行了自适应消融分析，对比了不同处理组件对置信度校准指标和最终 top-1 判别精度的影响：

配置 / 模块方案	投影 Brier Score ($\downarrow$)	$\mathcal{K}_1$ 校准误差 ($\downarrow$)	$\mathcal{K}_2^2$ 均方校准误差 ($\downarrow$)	Top-1 准确率 (%) ($\uparrow$)
Baseline (Hint)	$0.55862$	$0.23330$	$0.07473$	$65.510$
仅 Calibeating (在线频率精炼)	$0.51501 \pm 1.3\text{e-}4$	$0.08476 \pm 2.6\text{e-}4$	$0.02286 \pm 1.6\text{e-}4$	$62.114 \pm 0.023$
仅 Recalibration (本文 Blackwell 重校准)	$0.55281 \pm 1.8\text{e-}4$	$\mathbf{0.03107 \pm 1.05\text{e-}3}$	$\mathbf{0.00336 \pm 1.5\text{e-}4}$	$\mathbf{64.379 \pm 0.051}$
完整模型 (Calibeating + Recalibration)	$\mathbf{0.51240 \pm 1.4\text{e-}4}$	$0.06622 \pm 7.1\text{e-}4$	$0.01152 \pm 1.8\text{e-}4$	$63.549 \pm 0.039$

关键发现¶

单独使用 Recalibration 能将校准误差降低一个数量级以上（CIFAR-2 上 $\mathcal{K}_1$ 从 0.154 暴降至 0.01188，$\mathcal{K}_2^2$ 下降约 98%），充分验证了不平衡 Blackwell 框架的极端校准控制力。
Calibeating 单独使用虽然能降低 Brier score（从 0.16124 降到 0.13865），但由于缺乏显式校准闭环，其剩余校准误差仍是 Recalibration 的近 5 倍。
将 Calibeating 作为预处理送入 Recalibration 的串联结构（C + R），成功在获得最优 Brier score（0.13314）的同时保持极低的校准误差（0.01319），经验上完全印证了理论中同时达成 Calibeating 与 Calibration 的最优性。

亮点与洞察¶

证明了重校准的极小极大下界为 $\Theta(\varepsilon^{-3})$：构造了基于伯努利轮询分布的困难实例，运用偏置-误校准分解（bias-miscalibration decomposition）与随机扰动下界，首次证明了 $(\varepsilon, \varepsilon^2)$ 重校准的下界严格为 $\Omega(\varepsilon^{-3})$，确立了其与普通在线校准的严格分离。
解决了多目标可逼近性的步长失配瓶颈：通过固定极端原点初始化（$\mathbf{w}_1 = \mathbf{e}_2$）消除次要目标的 $1/(\eta T)$ 项，这一技巧极具通用性，可推广至任意具有非对称精度约束的同时博弈与多目标在线凸优化问题。
打通了多序列提示压缩与多目标校准的理论联结：证明了利用 $\eta$-可混合损失（mixable loss）的指数聚合可将 $m$ 个模型的提示序列在仅耗费 $\mathcal{O}(L \log m / \varepsilon^2)$ 的附加代价下压缩，实现了无需重新设计复杂多智能体博弈即可扩展至多提示预测。

局限与展望¶

依赖损失函数的 Lipschitz 光滑性假设：理论分析基于 Assumption 1（$L$-Lipschitz），这使得对于在预测概率接近 0 或 1 时无界的对数损失（交叉熵），理论无法直接闭合，目前需依赖经验截断。
多分类向二分类投影时的理论断层：实验中多分类任务依靠将 top-1 置信度转化为二分类进行事后缩放，虽然实证表现良好，但尚缺乏严格的多分类向量级全校准理论保障。
未来方向：探索无界损失函数（如标准对数损失）下的重校准速率，以及研究非二值、连续动作输出强化学习中的自适应策略重校准。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立非对称 MLOO 与不平衡 Blackwell 理论，并给出匹配的 $\Omega(\varepsilon^{-3})$ 下界。
实验充分度: ⭐⭐⭐⭐☆ 包含分布漂移下的二分类与多分类验证，完整覆盖了 Brier score、$\mathcal{K}_1$ 与 $\mathcal{K}_2^2$ 指标。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严密精炼，对偶与几何直觉交代得极其透彻。
价值: ⭐⭐⭐⭐⭐ 解决了在线学习与概率校准领域悬而未决的速率问题，为黑盒大模型输出概率校准提供了坚实理论地基。

预测方法	Brier Score (\(\downarrow\))	\(\mathcal{K}_1\) 校准误差 (\(\downarrow\))	\(\mathcal{K}_2^2\) 均方校准误差 (\(\downarrow\))	0-1 分类准确率 (%) (\(\uparrow\))
原始提示 (Hint)	\(0.16124 \pm 7.8\text{e-}4\)	\(0.15413 \pm 8.4\text{e-}4\)	\(0.02976 \pm 3.0\text{e-}4\)	\(82.075 \pm 0.082\)
在线精炼 (Calibeating)	\(0.13865 \pm 5.4\text{e-}4\)	\(0.05771 \pm 5.1\text{e-}4\)	\(0.00663 \pm 1.0\text{e-}4\)	\(82.428 \pm 0.084\)
在线重校准 (Recalibration, 本文)	\(0.14708 \pm 8.3\text{e-}4\)	\(\mathbf{0.01188 \pm 2.5\text{e-}4}\)	\(\mathbf{0.00052 \pm 0.5\text{e-}4}\)	\(78.597 \pm 0.308\)
组合策略 (Calibeating + Recalibration, 本文)	\(\mathbf{0.13314 \pm 4.5\text{e-}4}\)	\(0.01319 \pm 4.5\text{e-}4\)	\(0.00090 \pm 0.3\text{e-}4\)	\(\mathbf{82.408 \pm 0.088}\)

配置 / 模块方案	投影 Brier Score (\(\downarrow\))	\(\mathcal{K}_1\) 校准误差 (\(\downarrow\))	\(\mathcal{K}_2^2\) 均方校准误差 (\(\downarrow\))	Top-1 准确率 (%) (\(\uparrow\))
Baseline (Hint)	\(0.55862\)	\(0.23330\)	\(0.07473\)	\(65.510\)
仅 Calibeating (在线频率精炼)	\(0.51501 \pm 1.3\text{e-}4\)	\(0.08476 \pm 2.6\text{e-}4\)	\(0.02286 \pm 1.6\text{e-}4\)	\(62.114 \pm 0.023\)
仅 Recalibration (本文 Blackwell 重校准)	\(0.55281 \pm 1.8\text{e-}4\)	\(\mathbf{0.03107 \pm 1.05\text{e-}3}\)	\(\mathbf{0.00336 \pm 1.5\text{e-}4}\)	\(\mathbf{64.379 \pm 0.051}\)
完整模型 (Calibeating + Recalibration)	\(\mathbf{0.51240 \pm 1.4\text{e-}4}\)	\(0.06622 \pm 7.1\text{e-}4\)	\(0.01152 \pm 1.8\text{e-}4\)	\(63.549 \pm 0.039\)