Paper Overview
Field: Machine Learning Authors: Georgy Noarov, Aaron Roth Published: 2026-06-20 arXiv: 2506.16641
Summary
A model is said to be multicalibrated with respect to a collection of group weight functions G if it is calibrated not only on the overall distribution (i.e., unbiased conditioned on its predictions), but remains calibrated after reweighting contexts by each g in G. This is a useful property for many downstream applications and a fundamental requirement for trustworthy machine learning.
Prior to this work, all known predictors achieving the minimax optimal O(eps^{-3}) sample complexity for eps-multicalibration were randomized, while deterministic predictors were only known with substantially worse sample complexity. The question of whether optimal sample complexity in multicalibration requires randomization was explicitly raised by [CLNR26] and implicitly appears in several earlier works.
This paper resolves the open problem by giving a minimax optimal multicalibration algorithm that outputs deterministic predictors. The authors then generalize the algorithm to produce optimal deterministic predictors satisfying outcome indistinguishability (OI) for finite or finite-cover test collections.
As an application, this also yields deterministic omnipredictors and list predictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].
--- *Automatically collected on 2026-06-21*