最优确定性多校准与全预测

论文信息

标题: Optimal Deterministic Multicalibration and Omniprediction

作者: Georgy Noarov, Aaron Roth

发布日期: 2026-06-18

arXiv ID: 2606.20557v1

PDF 链接: 下载 PDF

3 分钟速览

研究问题：这篇论文要解决多校准和全预测中 “是否需要随机性才能达到最优样本复杂度” 这一开放问题，即能否用确定性预测器（训练后可复现、不丢硬币）匹配此前只有随机预测器才能达到的极小极大最优样本速率 $\widetilde{O}(\varepsilon^{-3})$ 。
核心方法：提出一种三阶段算法：先用置信样本为每个上下文建立置信区间 “提示”，再利用带区间提示的在线多校准算法产出受约束的随机预测器，最后用一个独立采样种子对应一个舍入单元格，把随机预测器变成确定性的。
关键结果：首次给出极小极大最优的确定性多校准算法，样本复杂度为 $\widetilde{O}(\varepsilon^{-3})$ （见 Theorem 7.1），并推广到结果不可区分和全预测，得到确定性的 $\widetilde{O}(d/\varepsilon^2)$ 全预测器（见 Corollary 8.11）。
主要局限：训练阶段仍使用随机性（尽管输出是确定的，附录 F 指出可移除，只增加对数因子）；算法要求有限测试族或可被有限覆盖的无限族，最一般无限类仍需覆盖假设。
适合读者：做可信机器学习（校准、公平性）、算法博弈论、在线学习和批次学习理论的研究者，以及对随机性在统计学习中角色感兴趣的读者。

论文背景和研究动机

校准要求预测器给出的每一个预测值，在统计上等于该预测值上的条件标签均值，即 “报多少，就应是多少”。多校准则将这一要求推广到由多个群组权重函数构成的集合 $\mathcal{G}$ ，要求在校准的每一个预测值上，经任何群组 $g \in \mathcal{G}$ 重新加权后的偏差之和都小。多校准和与其密切相关的全预测（单预测器可经后处理同时优化一大类损失函数）是可信机器学习的基础属性，在学习和公平性等领域有大量应用。

一个长期困扰理论的难题是：达到极小极大最优样本复杂度的已知算法，全都输出随机预测器，而确定性预测器的已知速率差得多。例如，Collina 等人（2026c）证明批次多校准的极小极大样本复杂度为 $\widetilde{\Theta}(\varepsilon^{-3})$ ，但他们给出的上界来自在线到批次的归约，输出是随机化的。Haghtalab 等人（2023）给出确定性多校准保证，但其 ECE 多校准的样本复杂度约为 $\widetilde{O}(\varepsilon^{-6})$ （按论文第 1 节的翻译）。全预测也有类似缺口：Okoroafor 等人（2025）得到样本最优的 $\widetilde{O}(d/\varepsilon^2)$ 全预测器，但输出是随机化的；他们明确提问这些全预测器是否可以被去随机化而不损失样本最优性。在多分布学习中，随机预测器在统计上可比确定性预测器更容易学习，而最近的工作也表明去随机化在一般设定中可能计算困难。

这篇论文的关键追问是：多校准是否又是一个 “随机性带来统计优势” 的场景？作者最终给出了否定的答案：预测时的随机性不是必需的，确定性预测器可以达到极小极大最优样本复杂度。

核心方法和技术细节

整体算法将 i.i.d. 样本分成三份：置信样本 $S_0$ 、在线学习样本 $S_1$ 和分区样本 $S_2$ 。输出的是一个确定性的网格预测器 $h: \mathcal{X} \to \Lambda$ 。

第一阶段：置信区间提示

用 $S_0$ 对每个出现过的上下文 $x$ 计算其经验标签均值 $\hat{\mu}_x$ 和半径 $r_x = \min(1, \sqrt{J/N_x})$ ，其中 $N_x$ 是在 $S_0$ 中看到 $x$ 的次数， $J$ 是受控的对数因子。得到的置信区间 $I_x = [\hat{\mu}_x - r_x, \hat{\mu}_x + r_x] \cap [0,1]$ 以高概率包含真实的 $\mu(x)$ 。同时还构造允许的网格值集合 $\Lambda_x = \{v \in \Lambda : \text{dist}(v, I_x) \le \gamma\}$ 。罕见上下文得到全区间 $[0,1]$ ，频繁上下文得到窄区间。这套区间提示系统的关键在于，它能平滑地在 “信息足够多” 和 “信息不足” 之间插值，避免了此前硬划分造成的样本浪费（见论文第 4 节，图 1）。

第二阶段：在线多校准与随机归约

在置信样本提供的区间提示下，运行一个在线多校准算法（Algorithm 3 及其分解实现）。该算法在每轮根据历史维护一个指数权重分布，混合所有带符号校准测试，产生一个系数向量 $c_t(x,v)$ ，再通过求解一个小型线性规划（LP）得到该轮的预测分布 $q_t(x)$ ，其支撑集受限在 $\Lambda_x$ 中。关键是：只要区间提示是 $\gamma$ -有效的，该在线算法就能保证各测试的累积误差为 $\tilde{O}(\gamma + \sqrt{(\log M)/T})$ ，同时支撑集永远不超出提示区间。最后用标准的鞅在线到批次归约将在线迭代平均，得到一个批次随机预测器 $Q$ ，其多校准误差有界，且对每个 $x$ 支撑集 $\text{supp}(Q_x) \subseteq \Lambda_x$ （见 Theorem 3.1）。

第三阶段：舍入与去随机化

分区样本 $S_2$ 用于构造有限个舍入单元格 $\Pi$ 。对未在 $S_0$ 中出现的上下文空间，采用字典序排序 $S_2$ 中的点，用相邻点之间的间隙作为单元格。作者通过可交换性论证，证明这样做能保证所有单元格的质量平方和 $\sum_{C} P_X(C)^2$ 被控制在 $O(\alpha^2 / L)$ （见 Lemma 5.2）。

最后，为每个舍入单元格 $C$ 独立抽取一个均匀种子 $U_C$ ，并通过逆 CDF 采样器 $F_x$ 将 $Q_x$ 舍入为确定性的 $h(x)$ ，所有落在同一单元格的上下文共享同一个种子。Proposition 6.1 的核心在于，因为 $Q_x$ 被限制在 $\Lambda_x$ 中，置信区间窄的上下文本身就具有较小的偏差变化范围，而置信区间宽的上下文几乎必然是罕见上下文，其平方质量小——两个效应叠加，使得单种子舍入带来的额外误差被联合控制。Lemma 6.2 最终证明，从 $Q$ 舍入得到的确定性 $h$ 的多校准误差只比 $Q$ 增加一个可控制的常数倍 $\alpha$ ，不破坏样本最优性。

对全预测的推广遵循同一框架：将测试族 $\mathcal{A}$ 从带符号校准测试替换为阈值校准测试加上损失导出的多精度审计测试，再套用 Loss OI 归约即可（见 Section 8）。

创新点和贡献

解决了多校准确定性极小极大样本复杂度这一开放问题，首次给出 $\widetilde{O}(\varepsilon^{-3})$ 的确定性多校准算法（见 Theorem 7.1），直接回应了 Collina 等人（2026c）和 Haghtalab 等人（2023）的提问。
引入 “置信区间提示 + 在线学习 + 单种子舍入” 的三阶段架构，绕过了以往硬划分原子带来的样本瓶颈，用平滑的置信度插值使罕见原子和频繁原子都能被合理地统计控制（见图 1 和相关讨论）。
将方法推广到结果不可区分和全预测，给出确定性全预测器，样本复杂度为 $\widetilde{O}(d/\varepsilon^2)$ （当审计类有伪维度 $p$ 或可被覆盖时），解决了 Okoroafor 等人（2025）和 Balakrishnan 等人（2026）提出的全预测与泛预测的去随机化问题（见 Theorem 8.7 及其推论，以及附录 E）。
证明算法可在多项式时间内隐式实现（见 Theorem 7.1 的复杂性陈述），指数权重可以在按预测值分解的因式化形式中计算和存储，查询时无需重建全部在线迭代。

局限与待解决问题

本文解决的是批次情形下的统计最优性，理论贡献的核心在于去随机化，但留有若干延伸空间。

首先，论文虽然给出确定性的输出预测器，但训练过程本身是随机的（依赖对 $S_1$ 的在线随机化以及对 $S_0$ 、 $S_2$ 的抽样随机性）。作者在附录 F 中指出训练随机性可以移除，代价仅是样本大小的对数因子，正文中并未给出具体的确定性训练算法和完整的端到端论证。完全确定性的训练流程是否能在相同的 $\widetilde{O}(\varepsilon^{-3})$ 样本界限内实现，仍需读者查阅附录自行验证。

其次，本文算法依赖有限测试族或可被有限覆盖的无限测试族（见 Corollary 7.2 和 Corollary 8.10），尽管覆盖估计来自标准理论，但当审计类结构复杂、覆盖数量大时，算法效率与样本数量均受影响。对于最一般的无限群组族，如果没有紧的覆盖性质，本文的方法并不直接适用。

第三，本文的在线学习组件对每个时间步需要求解一个小型 LP，算法虽然是多项式时间的，但在大规模上下文空间中的实际效率文章并未评估，也没有实验部分可供参考。对于高维上下文和高精度（小 $\varepsilon$ ）场景，存储和计算量可能依然显著。

最后，论文中全预测部分假设二元标签、损失有界且满足 Bayes 作用选取约定，结果的泛化需要用户自行核查所用损失类是否满足这些条件。泛预测的扩展虽在附录 E 中给出，但正文仅略述结论，完整的技术条件需要读者追溯原文定义。