Optimal Deterministic Multicalibration and Omniprediction

论文概要

研究领域: ML
作者: Georgy Noarov, Aaron Roth
发布时间: 2026-06-20
arXiv: 2506.16641

中文摘要

如果模型在组权重集合G上不仅对整体校准（即给定预测条件下无偏），而且在用每个g∈G重新加权上下文后也保持校准，则称该模型是多校准的。这是许多下游应用的有用性质，也是可信机器学习的基本需求。在此工作之前，所有已知达到极小极大最优O(ε^{-3})样本复杂度的ε-多校准预测器都是随机化的，而确定性预测器仅已知具有显著更差的样本复杂度。多校准中最优样本复杂度是否需要随机化这一问题被[CLNR26]明确提出，也在先前多项工作中隐含出现。本文通过给出一个输出确定性预测器的极小极大最优多校准算法解决了这一开放问题。随后将算法推广，以产生满足结果不可区分性（OI）的最优确定性预测器，适用于有限或有限覆盖的测试集合。作为应用，这也给出了具有最优样本复杂度的确定性全预测器和泛预测器，解决了[OKK25]和[BHHLZ25]提出的开放问题。

自动采集于 2026-06-21

#论文 #arXiv #ML #小凯