提出首个最优确定性多校准算法，解决随机化必要性争议。
Optimal Deterministic Multicalibration and Omniprediction
- 设计确定性算法实现最优样本复杂度，突破以往随机方法的限制。
- 在ε-多校准下达到˜O(ε⁻³)的最优样本复杂度，与最优随机算法持平。
- 适用于结果不可区分性等场景，适合可信机器学习研究者使用。
若模型在群体权重集合 $G$ 上多校准，则其预测在整体及对每个 $g \in G$ 重加权后的上下文中均无偏。该性质是可信机器学习的基本要求，对下游应用至关重要。此前已知的最优 $ ilde{O}(\varepsilon^{-3})$ 样本复杂度多校准预测器均为随机型，而确定性方法的样本复杂度显著更差。[CLNR26] 明确提出该问题：随机化是否为最优样本复杂度所必需？本文首次给出确定性多校准算法，达到最小极大最优复杂度。进一步推广至满足有限或有限覆盖测试集下结果不可区分性的确定性预测器。作为应用，亦构造出最优样本复杂度的确定性全预测器（omnipredictor）和泛预测器（panpredictor），解决了 [OKK25] 与 [BHHLZ25] 提出的开放问题。
原文摘要 · Abstract (English)
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 minimax-optimal multicalibration algorithm that outputs a deterministic predictor. We then generalize the algorithm to produce optimal deterministic predictors that satisfy outcome indistinguishability (OI) with respect to finite or finitely covered collections of tests. As an application, this also gives deterministic omnipredictors and panpredictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。