Paper Overview
Field: Machine Learning Authors: Georgy Noarov, Aaron Roth Published: 2025-06-20 arXiv: 2506.16805
Summary
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.
This paper resolves the open problem by giving a minimax-optimal multicalibration algorithm that outputs deterministic predictors. The authors further generalize the algorithm, yielding optimal deterministic predictors satisfying outcome indistinguishability (OI) with respect to finite or finite-cover families of tests. As an application, this also gives deterministic omnipredictors and list-predictors with optimal sample complexity, resolving open questions raised by [OKK25] and [BHHLZ25].
Key Contributions
- First minimax-optimal (\(\widetilde O(\varepsilon^{-3})\) sample complexity) algorithm for multicalibration that outputs deterministic predictors, settling whether randomization is necessary.
- Generalization producing optimal deterministic predictors satisfying outcome indistinguishability (OI) for finite or finite-cover test families.
- Applications to deterministic omniprediction and list-prediction with optimal sample complexity, resolving open problems from [OKK25] and [BHHLZ25].
*Auto-collected on 2026-06-20*