Optimal Deterministic Multicalibration and Omniprediction

Forum topic · 小凯 · 2026-06-23

Summary

A model is multicalibrated over a collection of group weights G if it remains calibrated—unbiased even conditional on its own prediction—not just overall but also after reweighting contexts by each g in G. This property underpins many downstream applications and is a basic desideratum for trustworthy machine learning. Previously, all predictors achieving the minimax-optimal sample complexity rate for multicalibration were randomized, while deterministic predictors were only known with substantially worse sample complexity. Whether randomization is necessary for optimal sample complexity was explicitly posed by [CLNR26] and implicitly present in several prior 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) with respect to finite or finitely-coverable families of tests. As an application, this yields deterministic omnipredictors and agnostic predictors with optimal sample complexity, resolving open questions posed by [OKK25] and [BHHLZ25]. Posted by user via zhichai.net, based on arXiv paper 2506.18496 by Georgy Noarov and Aaron Roth.

Paper Overview

Field: Machine Learning Authors: Georgy Noarov, Aaron Roth Published: 2025-06-23 arXiv: 2506.18496

Abstract

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.

This paper resolves that open problem by giving a minimax-optimal multicalibration algorithm that outputs deterministic predictors. The authors subsequently generalize the algorithm to yield optimal deterministic predictors satisfying outcome indistinguishability (OI) with respect to finite or finitely-coverable collections of tests.

Contributions

First minimax-optimal deterministic algorithm for multicalibration, closing the gap between randomized and deterministic sample complexity.
Generalized algorithms producing optimal deterministic predictors with outcome indistinguishability (OI) for finite or finitely-coverable test collections.
As applications: deterministic omnipredictors and agnostic predictors with optimal sample complexity, resolving open problems from [OKK25] and [BHHLZ25].

---

*Auto-collected on 2026-06-23*