# On Computationally Efficient Multi-Class Calibration

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 44 references that are in the map.
- First posted on arXiv 12 Feb 2024.

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

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Beyond temperature scaling: Obtaining well-calibrated multiclass probabilities with Dirichlet calibration](https://mlsanity.com/paper/1910.12656/) (2019)
- [Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration](https://mlsanity.com/paper/2107.05719/) (2021)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [On the Computational Efficiency of Training Neural Networks](https://mlsanity.com/paper/1410.1141/) (2014)
- [Batch Multivalid Conformal Prediction](https://mlsanity.com/paper/2209.15145/) (2022)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [A Unifying Theory of Distance from Calibration](https://mlsanity.com/paper/2211.16886/) (2022)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Top-label calibration and multiclass-to-binary reductions](https://mlsanity.com/paper/2107.08353/) (2021)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [Smooth Calibration, Leaky Forecasts, Finite Recall, and Nash Dynamics](https://mlsanity.com/paper/2210.07152/) (2022)
- [From average case complexity to improper learning complexity](https://mlsanity.com/paper/1311.2272/) (2013)
- [From Pseudorandomness to Multi-Group Fairness and Back](https://mlsanity.com/paper/2301.08837/) (2023)
- [From Boltzmann Machines to Neural Networks and Back Again](https://mlsanity.com/paper/2007.12815/) (2020)

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

- [High dimensional online calibration in polynomial time](https://mlsanity.com/paper/2504.09096/) (2025)
- [Evaluating Posterior Probabilities: Decision Theory, Proper Scoring Rules, and Calibration](https://mlsanity.com/paper/2408.02841/) (2024)
- [Confidence Calibration of Classifiers with Many Classes](https://mlsanity.com/paper/2411.02988/) (2024)
- [Provable Uncertainty Decomposition via Higher-Order Calibration](https://mlsanity.com/paper/2412.18808/) (2024)
- [Generalized and Unified Equivalences between Hardness and Pseudoentropy](https://mlsanity.com/paper/2507.05972/) (2025)
- [Calibration through the Lens of Indistinguishability](https://mlsanity.com/paper/2509.02279/) (2025)
- [Efficient Calibration for Decision Making](https://mlsanity.com/paper/2511.13699/) (2025)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [Multi-Group Proportional Representation in Retrieval](https://mlsanity.com/paper/2407.08571/) (2024)
- [Dimension-Free Decision Calibration for Nonlinear Loss Functions](https://mlsanity.com/paper/2504.15615/) (2025)
- [Testable and Actionable Calibration for Full Swap Regret](https://mlsanity.com/paper/2605.17749/) (2026)
- [Sample-efficient Multiclass Calibration under ℓp Error](https://mlsanity.com/paper/2509.23000/) (2025)
- [Truthful Calibration Errors for Multi-Class Prediction](https://mlsanity.com/paper/2510.06388/) (2025)
- [Scalable Utility-Aware Multiclass Calibration](https://mlsanity.com/paper/2510.25458/) (2025)
- [L2-Regularized Empirical Risk Minimization Guarantees Small Smooth Calibration Error](https://mlsanity.com/paper/2510.13450/) (2025)
- [Smoothed Elicitation Complexity for Approximate Gamma-calibration of Discrete Classification Tasks](https://mlsanity.com/paper/2605.23017/) (2026)

## Abstract (arXiv)

Consider a multi-class labelling problem, where the labels can take values in [k], and a predictor predicts a distribution over the labels. In this work, we study the following foundational question: Are there notions of multi-class calibration that give strong guarantees of meaningful predictions and can be achieved in time and sample complexities polynomial in k? Prior notions of calibration exhibit a tradeoff between computational efficiency and expressivity: they either suffer from having sample complexity exponential in k, or needing to solve computationally intractable problems, or give rather weak guarantees. Our main contribution is a notion of calibration that achieves all these desiderata: we formulate a robust notion of projected smooth calibration for multi-class predictions, and give new recalibration algorithms for efficiently calibrating predictors under this definition with complexity polynomial in k. Projected smooth calibration gives strong guarantees for all downstream decision makers who want to use the predictor for binary classification problems of the form: does the label belong to a subset T subseteq [k]: e.g. is this an image of an animal? It ensures that the probabilities predicted by summing the probabilities assigned to labels in T are close to some perfectly calibrated binary predictor for that task. We also show that natural strengthenings of our definition are computationally hard to achieve: they run into information theoretic barriers or computational intractability. Underlying both our upper and lower bounds is a tight connection that we prove between multi-class calibration and the well-studied problem of agnostic learning in the (standard) binary prediction setting.