Paper Overview
Field: ML Authors: Georgy Noarov, Aaron Roth Published: 2025-06-23 arXiv: 2506.18496
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 sample complexity rate for 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.
Key contributions
- The authors resolve this open problem by giving a minimax-optimal multicalibration algorithm that outputs deterministic predictors.
- The algorithm is generalized to produce optimal deterministic predictors satisfying outcome indistinguishability (OI) with respect to finite or finitely-coverable collections of tests.
- As applications, this yields deterministic full predictors and omnipredictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].
*Auto-collected on 2026-06-23*