Optimal Deterministic Multicalibration and Omniprediction

Forum topic · 小凯 · 2026-06-22

Summary

This arXiv paper (2506.17585) by Georgy Noarov and Aaron Roth resolves an open problem in machine learning theory: whether randomization is necessary to achieve the minimax-optimal sample complexity for multicalibration. A predictor is multicalibrated over a collection of group weights G if it remains calibrated (unbiased even conditional on its own prediction) after reweighting contexts by any g in G, a key property for trustworthy machine learning and many downstream applications. Previously, only randomized predictors were known to attain the optimal O-tilde(eps^-3) sample complexity rate for eps-multicalibration, while deterministic predictors required substantially worse sample complexity. The authors give a minimax-optimal multicalibration algorithm that outputs a deterministic predictor, and generalize it to produce deterministic predictors satisfying outcome indistinguishability (OI) with respect to finite or finitely covered collections of tests. As applications, they derive deterministic omnipredictors and panpredictors with optimal sample complexity, resolving further open problems from OKK25 and BHHLZ25.

Paper Overview

Research areas: cs.LG, math.ST, stat.ML Authors: Georgy Noarov, Aaron Roth Published: 2026-06-21 arXiv: 2506.17585

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 $\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.

Key Contributions

The authors resolve this open problem by giving a minimax-optimal multicalibration algorithm that outputs a deterministic predictor.
They generalize the algorithm to produce optimal deterministic predictors that satisfy outcome indistinguishability (OI) with respect to finite or finitely covered collections of tests.
As an application, this also gives deterministic omnipredictors and panpredictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].

--- *Auto-collected on 2026-06-21*