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 multicalibration: whether randomization is necessary to achieve the minimax-optimal sample complexity rate of O-tilde(epsilon^-3) for epsilon-multicalibration. Multicalibration requires a model to be calibrated not just overall, but also after reweighting contexts by each group in a collection of group weights, making it a foundational property for trustworthy machine learning with many downstream applications. Previously, all predictors achieving the optimal rate were randomized, while deterministic predictors had substantially worse sample complexity. The authors give a minimax-optimal multicalibration algorithm that outputs a deterministic predictor, then generalize it to produce optimal deterministic predictors satisfying outcome indistinguishability (OI) with respect to finite or finitely covered collections of tests. As an application, they obtain deterministic omnipredictors and panpredictors with optimal sample complexity, resolving open problems posed by OKK25 and BHHLZ25.

Paper Overview

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

Abstract (translated from the post)

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.

The authors resolve this open problem by giving a minimax-optimal multicalibration algorithm that outputs a deterministic predictor. They then 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].

Key Contributions

First deterministic predictor achieving the minimax-optimal $\widetilde O(\varepsilon^{-3})$ rate for multicalibration.
Generalization to optimal deterministic outcome indistinguishability (OI) for finite or finitely covered test collections.
Deterministic omnipredictors and panpredictors with optimal sample complexity, settling prior open questions.

---

*Auto-collected on 2026-06-21. Source: arXiv:2506.17585*