# Optimal Deterministic Multicalibration and Omniprediction

arXiv: https://arxiv.org/abs/2606.20557 · HTML: https://mlsanity.com/paper/2606.20557/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 37 references that are in the map.
- First posted on arXiv 18 Jun 2026.

## Builds on (most cited first, 27 of 27)

- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Stronger Calibration Lower Bounds via Sidestepping](https://mlsanity.com/paper/2012.03454/) (2020)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Near-Optimal Algorithms for Omniprediction](https://mlsanity.com/paper/2501.17205/) (2025)
- [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications](https://mlsanity.com/paper/2108.03837/) (2021)
- [Forecasting for Swap Regret for All Downstream Agents](https://mlsanity.com/paper/2402.08753/) (2024)
- [Sample Complexity of Uniform Convergence for Multicalibration](https://mlsanity.com/paper/2005.01757/) (2020)
- [Breaking the T2/3 Barrier for Sequential Calibration](https://mlsanity.com/paper/2406.13668/) (2024)
- [Complexity-Theoretic Implications of Multicalibration](https://mlsanity.com/paper/2312.17223/) (2023)
- [Collaborative Prediction: Tractable Information Aggregation via Agreement](https://mlsanity.com/paper/2504.06075/) (2025)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [Tractable Agreement Protocols](https://mlsanity.com/paper/2411.19791/) (2024)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)
- [Networked Information Aggregation via Machine Learning](https://mlsanity.com/paper/2507.09683/) (2025)
- [Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability](https://mlsanity.com/paper/2203.04536/) (2022)
- [Optimal Lower Bounds for Online Multicalibration](https://mlsanity.com/paper/2601.05245/) (2026)
- [Derandomizing Multi-Distribution Learning](https://mlsanity.com/paper/2409.17567/) (2024)
- [Sample-Efficient Omniprediction for Proper Losses](https://mlsanity.com/paper/2510.12769/) (2025)
- [An Exploration of Multicalibration Uniform Convergence Bounds](https://mlsanity.com/paper/2202.04530/) (2022)
- [Supersimulators](https://mlsanity.com/paper/2509.17994/) (2025)
- [Panprediction: Optimal Predictions for Any Downstream Task and Loss](https://mlsanity.com/paper/2510.27638/) (2025)

## Built on by (most cited first, 2 of 2)

- [Optimal Rates for Agentic Networked Information Aggregation](https://mlsanity.com/paper/2609.05318/) (2026)
- [Sample-Optimal Multi-Group Learning with an ERM Oracle](https://mlsanity.com/paper/2610.15916/) (2026)

## Abstract (arXiv)

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