# The Sample Complexity of Multicalibration

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 37 references that are in the map.
- First posted on arXiv 23 Apr 2026.

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

- [Optimal Lower Bounds for Online Multicalibration](https://mlsanity.com/paper/2601.05245/) (2026)
- [Sample-Efficient Omniprediction for Proper Losses](https://mlsanity.com/paper/2510.12769/) (2025)
- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (2025)
- [An Exploration of Multicalibration Uniform Convergence Bounds](https://mlsanity.com/paper/2202.04530/) (2022)
- [Supersimulators](https://mlsanity.com/paper/2509.17994/) (2025)

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

- [Instance-Adaptive Online Multicalibration](https://mlsanity.com/paper/2605.09273/) (2026)
- [Smoothed Elicitation Complexity for Approximate Gamma-calibration of Discrete Classification Tasks](https://mlsanity.com/paper/2605.23017/) (2026)
- [Sample Complexity of Multicalibration for Multilevel Properties](https://mlsanity.com/paper/2608.04288/) (2026)

## Abstract (arXiv)

We study the minimax sample complexity of multicalibration in the batch setting. A learner observes n i.i.d. samples from an unknown distribution and must output a (possibly randomized) predictor whose population multicalibration error, measured by Expected Calibration Error (ECE), is at most varepsilon with respect to a given family of groups. For every fixed kappa > 0, in the regime |G|≤ varepsilon-kappa, we prove that widetildeTheta(varepsilon-3) samples are necessary and sufficient, up to polylogarithmic factors. The lower bound holds even for randomized predictors, and the upper bound is realized by a randomized predictor obtained via an online-to-batch reduction. This separates the sample complexity of multicalibration from that of marginal calibration, which scales as widetildeTheta(varepsilon-2), and shows that mean-ECE multicalibration is as difficult in the batch setting as it is in the online setting, in contrast to marginal calibration which is strictly more difficult in the online setting. In contrast we observe that for kappa = 0, the sample complexity of multicalibration remains widetildeTheta(varepsilon-2) exhibiting a sharp threshold phenomenon. More generally, we establish matching upper and lower bounds, up to polylogarithmic factors, for a weighted Lp multicalibration metric for all 1 ≤ p ≤ 2, with optimal exponent 3/p. We also extend the lower-bound template to a regular class of elicitable properties, and combine it with the online upper bounds of Hu et al. (2025) to obtain matching bounds for calibrating properties including expectiles and bounded-density quantiles.