[论文] Optimal Deterministic Multicalibration and Omniprediction

论文概要

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

中文摘要

一模型若对一群权重集合G实现多校准，则其不仅整体校准（即条件于其预测亦无偏），且于以G中每g重加权语境后亦然。此性质对诸多下游应用有用，且为可信机器学习之基本要求。

此前，所有已知达极小极大最优$O(ε^{-3})$样本复杂度率之ε-多校准预测器均为随机化，而确定性预测器之样本复杂度则显著更差。随机化是否为多校准最优样本复杂度所必需，此问题由[CLNR26]明确提出，亦隐含于若干先前工作。

本文解决此开放问题，给出一输出确定性预测器之极小极大最优多校准算法。作者复将算法推广，产生满足有限或有限覆盖测试集合之结果不可区分性（OI）的最优确定性预测器。作为应用，此亦给出具最优样本复杂度之确定性全能预测器与泛预测器，解决[OKK25]与[BHHLZ25]所提开放问题。

原文摘要

A model is multicalibrated on a collection of group weights $G$ if it is calibrated -- i.e. unbiased even conditional on its prediction -- not just overall, but also after reweighting contexts by each $g \in G$. It is a useful property for many downstream applications and is a basic desideratum of trustworthy machine learning. Before this work, all predictors known to attain the minimax-optimal $\widetilde O(\varepsilon^{-3})$ sample complexity rate for $\varepsilon$-multicalibration were randomized, while deterministic predictors were known only with substantially worse sample complexity. Whether randomization is necessary for optimal sample complexity in multicalibration was explicitly asked by [CLNR26] and implicitly in several prior works. We resolve this open problem by giving a minim...

--- *自动采集于 2026-06-20*

#论文 #arXiv #ML #小凯