Optimal Deterministic Multicalibration and Omniprediction

Forum topic · 小凯 · 2026-06-21

Summary

This forum post summarizes an arXiv paper (2506.16641) by Georgy Noarov and Aaron Roth on deterministic multicalibration. Multicalibration requires a model to be calibrated not only overall but also after reweighting by each group in a collection G, a key property for trustworthy machine learning. Previously, all predictors achieving the minimax-optimal O(ε^{-3}) sample complexity for ε-multicalibration were randomized, while deterministic predictors had notably worse sample complexity. The paper resolves the open question of whether randomness is necessary: it gives a minimax-optimal multicalibration algorithm that outputs deterministic predictors. The approach is extended to produce optimal deterministic predictors satisfying outcome indistinguishability (OI) for finite or finite-cover test collections. As applications, the authors obtain deterministic omnipredictors and list-predictors with optimal sample complexity, resolving open questions posed by OKK25 and BHHLZ25.

Paper Overview

Field: Machine Learning Authors: Georgy Noarov, Aaron Roth Published: 2026-06-20 arXiv: 2506.16641

Abstract

A model is multicalibrated with respect to a collection of group weights G if it is calibrated overall (i.e., unbiased conditional on its predictions) and remains calibrated after reweighting the context by each g ∈ G. This is a useful property for many downstream applications and a fundamental requirement for trustworthy machine learning.

Prior to this work, all known ε-multicalibrated predictors achieving the minimax-optimal O(ε^{-3}) sample complexity were randomized, while deterministic predictors were only known with significantly worse sample complexity. The question of whether randomness is necessary for optimal sample complexity in multicalibration was explicitly posed by [CLNR26] and implicitly appeared in several earlier works.

This paper resolves the open question by giving a minimax-optimal multicalibration algorithm that outputs deterministic predictors. The algorithm is then generalized to produce optimal deterministic predictors satisfying outcome indistinguishability (OI) for finite or finite-cover collections of tests.

Applications

As an application, the results also yield deterministic omnipredictors and list-predictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].

---

*Auto-collected on 2026-06-21*