这篇论文解决了机器学习里一个悬而未决的问题：确定性多校准算法终于能像随机算法一样高效了。如果你关心公平性、可信预测的样本效率，可以看看他们怎么做到的。
这篇论文提出了一种确定性多校准算法，达到最小最大最优的样本复杂度率 O~(ε⁻³)，解决了此前只有随机算法能达到该复杂度而确定性算法样本复杂度更差的开放问题。算法进一步推广到结果不可区分性（OI）和全预测器，给出了针对有限或有限覆盖测试集合的最优确定性预测器。这解决了CLNR26和OKK25等先前工作中明确提出的开放问题。
Optimal Deterministic Multicalibration and Omniprediction
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].