# Sample-efficient Multiclass Calibration under ℓp Error

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 18 references that are in the map.
- First posted on arXiv 26 Sep 2025.

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

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Beyond temperature scaling: Obtaining well-calibrated multiclass probabilities with Dirichlet calibration](https://mlsanity.com/paper/1910.12656/) (2019)
- [Verified Uncertainty Calibration](https://mlsanity.com/paper/1909.10155/) (2019)
- [Evaluating model calibration in classification](https://mlsanity.com/paper/1902.06977/) (2019)
- [Calibration tests in multi-class classification: A unifying framework](https://mlsanity.com/paper/1910.11385/) (2019)
- [Better Uncertainty Calibration via Proper Scores for Classification and Beyond](https://mlsanity.com/paper/2203.07835/) (2022)
- [A Consistent and Differentiable Lp Canonical Calibration Error Estimator](https://mlsanity.com/paper/2210.07810/) (2022)
- [Top-label calibration and multiclass-to-binary reductions](https://mlsanity.com/paper/2107.08353/) (2021)
- [A New Analysis of Differential Privacy's Generalization Guarantees](https://mlsanity.com/paper/1909.03577/) (2019)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [From Pseudorandomness to Multi-Group Fairness and Back](https://mlsanity.com/paper/2301.08837/) (2023)
- [Can a calibration metric be both testable and actionable?](https://mlsanity.com/paper/2502.19851/) (2025)

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

- [Smoothed Elicitation Complexity for Approximate Gamma-calibration of Discrete Classification Tasks](https://mlsanity.com/paper/2605.23017/) (2026)

## Abstract (arXiv)

Calibrating a multiclass predictor, that outputs a distribution over labels, is particularly challenging due to the exponential number of possible prediction values. In this work, we propose a new definition of calibration error that interpolates between two established calibration error notions, one with known exponential sample complexity and one with polynomial sample complexity for calibrating a given predictor. Our algorithm can calibrate any given predictor for the entire range of interpolation, except for one endpoint, using only a polynomial number of samples. At the other endpoint, we achieve nearly optimal dependence on the error parameter, improving upon previous work. A key technical contribution is a novel application of adaptive data analysis with high adaptivity but only logarithmic overhead in the sample complexity.