确定性多重校准的最优解：从随机性到确定性的理论突破

TL;DR（200字）

在机器学习中，我们希望模型的预测不仅是准确的，而且是"诚实的"——当模型说"有80%的概率下雨"时，实际上应该有80%的时间真的下雨。这种性质被称为"校准"。多重校准进一步要求这种诚实性不仅在整体数据上成立，而且在各种子群体上都成立。此前，达到最优样本复杂度的多重校准算法都依赖随机化机制，而确定性算法只能达到远非最优的性能。本文作者Georgy Noarov和Aaron Roth首次给出了一个确定性的、达到最小最大最优样本复杂度的多重校准算法，证明了随机化并非实现最优校准的必要条件。该方法还被推广到全预测器和泛预测器，解决了该领域多个重要的开放问题。

论文信息

论文标题：Optimal Deterministic Multicalibration and Omniprediction
作者：Georgy Noarov, Aaron Roth
发表时间：2026年6月18日
arXiv ID：2606.20557v1
学科分类：cs.LG（机器学习）、math.ST（统计理论）、stat.ML（统计机器学习）
论文链接：https://arxiv.org/abs/2606.20557v1

研究背景与动机

校准：机器学习中最基本的"诚实"要求

在深入讨论本文的贡献之前，我们需要理解一个核心概念：校准（Calibration）。

想象你是一位天气预报员。你说"今天有70%的概率会下雨"。如果你的预测是校准的，那么在你说"70%概率下雨"的所有日子里，实际上应该有大约70%的日子真的下雨了。这听起来很简单，但它蕴含着一个深刻的含义：你的预测不仅要反映你对世界的信念，还要诚实地反映这些信念的强度。

在机器学习中，校准是一个同样重要但经常被忽视的性质。当我们训练一个模型来预测某个事件是否会发生（比如一个用户是否会点击某个广告，或者一个病人是否患有某种疾病），我们通常关注的是准确率、召回率等指标。但校准关注的是一个更根本的问题：模型的概率输出是否真正反映了现实世界的概率？

为什么校准如此重要？原因有很多：

第一，决策的基础。 当我们用模型的输出来做决策时（比如是否批准贷款、是否进行手术），我们需要知道这些概率估计是可靠的。一个说"风险为30%"的模型，如果实际风险是60%，那么基于这个预测做出的决策将是灾难性的。

第二，可信度和可解释性。 一个校准良好的模型是"诚实的"——它不会夸大或低估自己的确定性。这对于建立用户对AI系统的信任至关重要。

第三，多模型集成。 当多个模型的输出需要组合时（例如在医学诊断中多个测试结果的综合判断），校准的概率是正确组合的前提。

从校准到多重校准

然而，仅仅整体校准是不够的。这就是**多重校准（Multicalibration）**概念出现的原因。

考虑一个贷款审批模型。假设这个模型在整体数据上是校准的——它预测的违约概率与实际违约率一致。但如果仔细检查，你可能会发现，在某个特定的少数族裔群体中，这个模型系统性地低估了违约风险。虽然整体上模型是"诚实"的，但对这个特定群体来说，它是不诚实的。

这正是多重校准要解决的问题。一个多重校准的模型不仅在整体数据上是校准的，而且在数据的各种子群体上都是校准的。这些子群体可以按照种族、性别、年龄、收入水平等各种属性来定义。

形式化地说，给定一个群体权重函数的集合 $G$，如果一个预测器在用每个 $g \in G$ 对上下文进行重新加权后仍然是校准的，那么它就是多重校准的。这里的"群体权重函数"是一个很灵活的概念——它可以指示某个样本是否属于某个群体，也可以为不同样本赋予不同的权重。

多重校准的概念最初由Hébert-Johnson等人在2018年提出，作为公平性的一种形式。但很快人们就发现，它的意义远不止于公平性——它实际上是一个关于预测器"诚实性"的更一般性的要求。

样本复杂度的核心问题

在理论上，多重校准面临的一个核心问题是：要达到 $\varepsilon$-多重校准，需要多少样本？

这里的"样本复杂度"是一个关键概念。直观地说，它衡量的是：如果我们只有有限的训练数据，我们能在多大程度上保证校准性？样本复杂度越低，意味着我们可以在更少的数据上实现更好的校准，这在实际应用中是极其重要的。

在多重校准的理论研究中，已知的**最小最大最优（minimax optimal）**样本复杂度是 $\widetilde{O}(\varepsilon^{-3})$。这里的 $\widetilde{O}$ 表示忽略对数因子，$\varepsilon$ 是我们希望达到的校准误差。也就是说，如果我们要将校准误差降低一半，样本量需要增加大约8倍。

随机化与确定性之争

在达到这个最优样本复杂度的道路上，一个关键的技术选择是：算法是否需要使用随机化？

此前，所有已知能够达到 $\widetilde{O}(\varepsilon^{-3})$ 最优样本复杂度的多重校准算法都依赖于随机化。这意味着这些算法在做出预测时会引入随机性——即使对于相同的输入，算法也可能给出略微不同的预测。

随机化在算法设计中是一个强大的工具。它可以帮助打破对称性、避免过拟合、增加探索等。但随机化也带来了问题：

可重复性问题。 同样的输入在不同的运行中可能产生不同的输出，这使得结果难以重现。

确定性偏好。 在许多实际应用中，人们更希望模型给出确定性的、可重复的预测。一个贷款审批系统应该对同样的申请给出同样的回答。

理论理解。 从理论角度看，理解随机化是否是必要的，有助于我们更深入地理解问题的本质结构。

而在确定性算法方面，此前只有样本复杂度远高于最优的算法。换句话说，确定性算法为了实现多重校准，需要付出远高于随机化算法的数据代价。

这自然引出了一个核心问题：随机化对于达到最优样本复杂度是否是必要的？ 这个问题被CLNR26明确提出，也被多项先前工作隐含地提出。

核心发现

确定性最优多重校准算法

本文最核心的贡献是给出了一个确定性的、达到最小最大最优样本复杂度的多重校准算法。

具体而言，作者证明了存在一个确定性算法，对于任意给定的群体权重函数集合 $G$，能够输出一个预测器，该预测器是 $\varepsilon$-多重校准的，且所需的样本量为 $\widetilde{O}(\varepsilon^{-3})$——与此前已知的随机化算法的样本复杂度完全相同。

这意味着什么？这意味着随机化并不是实现最优多重校准所必需的。确定性算法和随机化算法在样本复杂度上没有本质的区别。

这个结果直接回答了CLNR26提出的问题，也从正面解决了先前工作中隐含的疑问。

结果的可推广性：超越多重校准

更令人印象深刻的是，作者并不局限于多重校准这一特定目标。他们将算法进行了广泛的推广，使之能够满足更一般的**结果不可区分性（Outcome Indistinguishability, OI）**条件。

结果不可区分性是一个比多重校准更广泛的概念。直观地说，一个预测器满足结果不可区分性，意味着从某个特定的"测试"集合的角度来看，预测器的输出与真实的标签是不可区分的。也就是说，任何在这个测试集合中指定的测试，都无法区分预测器的输出是来自模型还是来自真实世界。

作者证明了他们的确定性算法可以达到最小最大最优的样本复杂度，适用于有限集合的测试，以及更一般的"有限覆盖"测试集合。

全预测器和泛预测器的确定性最优结果

作为结果不可区分性框架的直接推论，作者还解决了两个重要的开放问题：

全预测器（Omnipredictors）。 全预测器的概念由Le Goh等人提出。一个全预测器是一个预测器，其输出可以被任何下游损失函数的最优决策规则直接使用。换句话说，全预测器给出的不是针对某个特定任务的预测，而是一个通用的预测，可以被任何决策者根据自己的偏好来使用。

本文给出了确定性的、具有最优样本复杂度的全预测器，解决了OKK25提出的开放问题。

泛预测器（Panpredictors）。 泛预测器是Barocas等人提出的另一个相关概念，它在某种程度上是多重校准和全预测的推广。

本文同样给出了确定性的、具有最优样本复杂度的泛预测器，解决了BHHLZ25提出的开放问题。

总结核心发现

结果	此前最优	本文贡献
多重校准（随机化）	$\widetilde{O}(\varepsilon^{-3})$	—
多重校准（确定性）	远高于 $\widetilde{O}(\varepsilon^{-3})$	$\widetilde{O}(\varepsilon^{-3})$ ✓
全预测器（确定性）	开放问题	$\widetilde{O}(\varepsilon^{-3})$ ✓
泛预测器（确定性）	开放问题	$\widetilde{O}(\varepsilon^{-3})$ ✓

技术方法详解

基本框架：从校准到多重校准的构造

理解本文的技术贡献需要我们先回顾一下校准和多重校准的基本技术方法。

校准的"分箱"方法。 最直观的校准方法是"分箱"（binning）。假设我们有一组预测，每个预测都在0到1之间。我们可以将预测值分成若干个区间（箱子），比如[0, 0.1), [0.1, 0.2), 等等。对于每个箱子，我们计算该箱子中预测的平均值和实际的正例比例。如果两者接近，说明在这个区间内预测是校准的。

多重校准的迭代方法。 多重校准比整体校准更难，因为它需要同时对所有子群体进行校准。已知的有效方法是使用**迭代校准（iterative calibration）**的思想。

想象你有一个预测器，它在某些子群体上不够校准。迭代方法的思路是：

找到一个"最不校准"的子群体
对这个子群体的预测进行调整
重复这个过程，直到所有子群体都足够校准

这个过程可以类比为修理一个管道系统。如果你发现某个水管漏水（某个子群体不够校准），你修补它。但修补一个地方可能会导致其他地方出现问题，所以你需要反复检查和修补，直到整个系统都不再漏水。

随机化为何有效

此前的随机化算法之所以能够达到最优样本复杂度，有一个直观的原因。

在迭代校准过程中，每次调整一个子群体的预测时，我们可能会无意中破坏其他子群体的校准。随机化的作用类似于在高维空间中"扩散"影响——通过引入随机性，每次调整的影响被"稀释"到更大的空间中，从而减小对其他子群体的负面影响。

这就像在一个嘈杂的房间中，如果你小声说话，没人会注意到你的声音（随机化使得对任何单个子群体的影响都很小）。但如果你大声说话（确定性调整），每个人都可能会注意到。

确定性方法的挑战

确定性方法面临的核心挑战是：如何在不引入随机性的情况下，控制每次迭代对其他子群体的影响？

在随机化方法中，随机性充当了一个"缓冲器"——它将调整的影响分散到各个方向，使得对任何特定方向的影响都很小。而在确定性方法中，我们需要找到其他机制来实现类似的效果。

这就像用精密的机械手来修补管道系统（确定性），而此前的方法则像用胶水随意喷涂（随机化）。两者都能修好管道，但机械手需要更精巧的设计。

本文的关键技术洞察

作者的解决方案基于以下几个关键洞察：

洞察一：精心构造的确定性扰动。 作者发现，通过精心设计校准调整的方向和幅度，可以在不引入随机性的情况下控制对其他子群体的影响。这需要对迭代过程中的误差传播进行精确的分析。

想象你在玩一个平衡游戏——你需要在多个支点上放置砝码，使得每个支点都保持平衡。随机化就像是随机放置砝码然后通过多次尝试找到平衡点，而确定性方法则是精确计算每个砝码应该放在哪里。

洞察二：利用几何结构。 作者发现，校准问题的数学结构允许我们使用确定性的方法来"分散"调整的影响。具体来说，他们利用了群体权重函数集合的几何性质，找到了一种确定性的方法来将调整的影响均匀地分散到各个方向。

这就像在物理学中，虽然空气分子的运动是随机的（温度、压力等宏观性质是可以确定性地描述的。作者在校准问题中发现了类似的"宏观确定性"结构。

洞察三：统一的处理框架。 作者不仅仅是针对多重校准设计了一个新算法，而是发现了一个统一的框架，可以同时处理多重校准、结果不可区分性、全预测、泛预测等多个问题。这个统一框架的发现是本文最重要的概念贡献之一。

算法的高层描述

在高层面上，本文的算法可以描述为以下步骤：

初始化： 从一个任意的初始预测器开始。
迭代优化： 在每一步中：
- 检查当前预测器是否满足所有需要的校准条件
- 如果存在违反的条件，找到一个"最有影响力"的违反条件
- 精心计算一个确定性的调整量，使得调整后违反条件的数量或程度减少
- 应用调整
终止： 当所有条件都满足时停止，输出最终的预测器。

关键的创新在于第2步中的"精心计算"——作者展示了如何在不使用随机化的情况下，设计调整量使得每一步都有效地改善校准质量，同时不破坏已有的校准性质。

与先前方法的技术对比

为了更清楚地说明本文的技术创新，让我们与先前的随机化方法进行对比：

技术方面	随机化方法	本文确定性方法
调整方向	随机选取	精心计算
影响控制	通过随机性稀释	通过几何结构分散
收敛分析	期望意义下	确定性保证
实现复杂度	需要随机数生成器	纯确定性计算

这种对比揭示了本文的核心贡献：作者发现了一种确定性的替代机制，可以达到与随机化相同的效果，但具有更好的可重复性和确定性保证。

关于结果不可区分性的技术细节

结果不可区分性（Outcome Indistinguishability, OI）是本文推广框架的核心概念。

给定一个测试集合 $\mathcal{T}$，一个预测器 $\hat{\mu}$ 满足关于 $\mathcal{T}$ 的结果不可区分性，意味着对于 $\mathcal{T}$ 中的每一个测试 $t$，预测器的输出分布与真实标签的分布在该测试下是不可区分的。

这里的"测试"可以理解为一种"检查"——它指定了一个函数 $t(x, y, \hat{\mu}(x))$，这个函数计算一个基于输入、真实标签和预测的统计量。如果预测器满足OI，那么无论你使用哪个测试，你都无法区分预测器的输出是来自模型还是来自真实世界。

作者证明了对于有限集合的测试以及"有限覆盖"（finitely covered）的测试集合，存在确定性的算法可以达到最优的样本复杂度。

这里的"有限覆盖"条件是一个技术性的要求，它保证测试集合可以被有限个"基本测试"所覆盖，从而使得分析变得可行。

实验结果分析

本文是一篇理论论文，主要贡献在于算法设计和理论证明，而非实验验证。因此，作者没有进行大规模的实证实验。

然而，我们可以从以下几个角度来评估本文结果的理论意义：

最优性分析

作者证明了他们的确定性算法达到了 $\widetilde{O}(\varepsilon^{-3})$ 的样本复杂度，这与已知的下界匹配。这意味着在最坏情况下，没有算法（无论是确定性的还是随机化的）能够在更少的样本上实现多重校准。

具体来说：

上界：本文证明了存在确定性算法可以在 $\widetilde{O}(\varepsilon^{-3})$ 样本上实现 $\varepsilon$-多重校准
下界：先前工作已经证明了 $\Omega(\varepsilon^{-3})$ 的下界（即使是随机化算法也无法突破）

因此，本文的算法在样本复杂度意义上是最优的，不可能被进一步改进。

与先前确定性算法的对比

先前的确定性多重校准算法的样本复杂度远高于 $\widetilde{O}(\varepsilon^{-3})$。具体来说，先前最好的确定性算法的样本复杂度大约是 $\widetilde{O}(\varepsilon^{-4})$ 或更高。

这意味着本文的结果在确定性算法中实现了从 $\varepsilon^{-4}$ 到 $\varepsilon^{-3}$ 的改进——这是一个多项式级别的改进，在 $\varepsilon$ 较小时（比如 $\varepsilon = 0.01$），这意味着样本量可以减少100倍。

算法的构造性

值得注意的是，作者的算法是构造性的——他们不仅证明了最优确定性算法的存在性，还给出了具体的构造方法。这意味着算法可以被实际实现和应用，尽管其主要价值目前在于理论层面。

与现有工作对比

多重校准的理论研究

多重校准的理论研究始于Hébert-Johnson等人2018年的工作。他们首次定义了多重校准的概念，并给出了基于迭代方法的算法。

随后的工作在多个方向上推进了这一理论：

Globus-Harris等人 研究了多重校准的近似版本，以及它与公平性的关系
Jung等人 给出了多重校准与校准之间关系的理论分析
CLNR26 系统性地研究了多重校准的样本复杂度，并明确提出了随机化是否必要性的问题

本文直接回答了CLNR26的问题，是这一研究线路上的一个里程碑。

结果不可区分性框架

结果不可区分性的概念由Garg等人提出，作为理解和统一系列校准相关概念的框架。

Garg等人 首次定义了OI的概念，并研究了其基本性质
Ben-David等人 将OI与多重校准联系起来
OKK25和BHHLZ25 分别研究了全预测器和泛预测器的理论性质

本文在OI框架下给出了确定性的最优结果，统一了这些先前工作的结论。

确定性 vs 随机化

在更广泛的机器学习理论中，确定性与随机化算法的对比是一个经典主题：

在线学习中，随机化对于minimax最优性是必要的（如对抗性赌博机问题）
PAC学习中，随机化通常不是必要的
在多重校准中，本文证明了随机化不是必要的

这一结果为理解随机化在机器学习理论中的作用提供了新的见解。

全预测器与泛预测器

全预测器的概念由Dwork等人在2021年提出，泛预测器的概念由Barocas等人在2023年提出。

OKK25 研究了全预测器的样本复杂度，并提出了确定性最优全预测器的开放问题
BHHLZ25 研究了泛预测器的理论性质，并提出了类似的开放问题

本文一举解决了这两个开放问题，展示了统一框架的力量。

潜在应用与影响

对可信AI的影响

本文的结果对可信AI的发展具有重要意义。多重校准是可信AI的一个基本要求——它保证模型不仅在整体上是可靠的，而且对各种子群体都是可靠的。

本文证明了确定性算法可以最优地实现多重校准，消除了人们对"是否必须牺牲确定性来获得最优校准"的担忧。这意味着在实际的可信AI系统中，我们可以同时拥有：

确定性的、可重复的预测
最优的校准质量
对各种子群体的公平对待

对公平性研究的影响

多重校准最初就是作为公平性的一种形式被提出的。本文的结果表明，在理论层面上，公平性和确定性并不是互相矛盾的目标——我们可以同时实现两者。

这对公平性算法的设计具有指导意义。在实际应用中，确定性的公平算法通常比随机化的公平算法更受欢迎，因为它们的结果更容易理解、审计和解释。

对模型部署的影响

在工业界，模型的确定性通常是一个重要的要求。一个确定性的模型更容易：

测试和验证：相同的输入总是产生相同的输出
调试：问题更容易重现和定位
监管合规：在金融、医疗等受监管领域，确定性通常是法规要求

本文的结果表明，选择确定性算法并不意味着要在校准质量上做出妥协。

对理论研究的影响

从理论研究的角度，本文有几个重要的影响：

建立了确定性多重校准的最优理论，为此后的工作设定了基准
提供了统一的OI框架，为研究其他校准相关概念提供了工具
展示了确定性方法的潜力，鼓励了在其他问题中探索确定性替代方案

对算法设计的影响

本文的技术方法——通过精心设计的确定性扰动来替代随机化——可能对更广泛的算法设计问题有启发意义。

在许多机器学习问题中，随机化被用作一种"简便"的技术手段。本文的结果表明，在某些情况下，通过更精巧的设计，可以用确定性方法达到相同甚至更好的效果。

局限性与未来方向

当前局限性

尽管本文的结果在理论上是完美的，但仍存在一些局限性：

计算复杂度。 本文主要关注样本复杂度，而没有详细讨论算法的计算复杂度。虽然算法在理论上是可行的，但其实际运行时间可能很高，特别是当群体权重函数集合 $G$ 很大时。

有限覆盖条件。 本文对结果不可区分性的推广要求测试集合满足"有限覆盖"条件。对于不满足这一条件的测试集合，最优的确定性算法是否仍然存在，目前还不清楚。

理论性质。 本文是纯理论的，没有进行实证实验。虽然理论结果是最优的，但在实际应用中，算法的性能如何还需要进一步的实验验证。

渐近分析。 本文的样本复杂度结果是渐近的——它描述的是当样本量趋于无穷时的行为。在有限样本的情况下，算法的实际性能可能与理论保证有所偏差。

未来研究方向

本文的结果为多个未来研究方向打开了大门：

方向一：计算效率。 如何设计计算上更高效的确定性多重校准算法？这可能需要结合本文的理论洞察与实际的优化技术。

方向二：无限测试集合。 对于无限或连续的测试集合，确定性的最优算法是否存在？这需要发展新的技术工具。

方向三：自适应群体。 本文假设群体权重函数集合 $G$ 是固定的。在实际应用中，我们可能希望算法能够适应数据的结构，自动发现需要校准的群体。

方向四：实证研究。 将本文的理论算法转化为实际可用的工具，并在真实数据集上进行验证，是一个重要的实际研究方向。

方向五：与其他公平性概念的结合。 多重校准只是众多公平性概念之一。如何将本文的方法推广到其他公平性框架，是一个有趣的问题。

方向六：在线学习设置。 本文的结果是在离线（batch）设置下证明的。在线性学习的设置中，确定性多重校准的最优性如何，目前还不清楚。

方向七：差分隐私。 在差分隐私的约束下，确定性多重校准的最优样本复杂度是多少？这是一个自然的延伸问题。

总结

本文是多重校准理论研究中的一个里程碑式的工作。Georgy Noarov和Aaron Roth首次给出了确定性的、达到最小最大最优样本复杂度的多重校准算法，证明了随机化并非实现最优校准所必需的。

这一结果解决了该领域多个重要的开放问题，包括确定性多重校准的最优性、确定性全预测器和泛预测器的最优性等。作者的统一框架——基于结果不可区分性的方法——为未来的研究提供了强大的理论工具。

从更广阔的视角来看，本文展示了确定性方法在机器学习理论中的潜力。在许多情况下，我们可能不需要牺牲确定性来获得最优的性能——通过更精巧的设计，确定性算法可以达到与随机化算法相同甚至更好的效果。

对于可信AI和公平AI的研究社区，本文的结果是令人鼓舞的：它表明在理论层面上，我们可以同时实现确定性、校准性和公平性。虽然将这些理论结果转化为实际应用还有很长的路要走，但本文为这条道路奠定了坚实的理论基础。

这项研究也提醒我们，在机器学习理论中，有些看似理所当然的技术选择（比如使用随机化来达到最优性能）可能并不是真正必要的。通过更深入的理论分析，我们可能会发现更简洁、更优雅的解决方案。这正是理论研究的价值所在——它不仅告诉我们什么是可能的，还帮助我们理解什么是本质的，什么是可以被替代的。