Paper Overview
Field: ML 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 to produce optimal deterministic predictors satisfying outcome indistinguishability (OI) for finite or finitely covered test collections. As an application, this also yields deterministic omnipredictors and pan-predictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].
Original Abstract (excerpt)
> 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...
*Auto-collected on 2026-06-20*