The Sample Complexity of Multicalibration

Forum topic · 小凯 · 2026-04-27

Summary

This paper by Natalie Collina, Jiuyao Lu, Georgy Noarov, and Aaron Roth studies 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 via expected calibration error (ECE) with respect to a group family, is at most ε. For every fixed κ>0 with group families of size |G| ≤ ε^{-κ}, the authors prove that exactly (ε^{-3}) samples are necessary and sufficient, up to polylogarithmic factors. The lower bound holds even for randomized predictors, while the upper bound is achieved via randomized predictors from an online-to-batch reduction. This separates multicalibration sample complexity from marginal calibration, which scales as (ε^{-2}), and shows mean-ECE multicalibration is as hard in the batch setting as in the online setting. For κ=0, the complexity remains (ε^{-2}), exhibiting a sharp threshold phenomenon. The paper also establishes matching bounds of exponent 3/p for weighted Lp multicalibration metrics for all 1 ≤ p ≤ 2, and extends lower bounds to regular classes of inducible properties, yielding matching bounds for quantile and bounded-density quantile calibration combined with online upper bounds by Hu et al. (2025).

Paper Overview

Field: Machine Learning Authors: Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth arXiv: 2604.21923

Abstract

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 with respect to a given family of groups, measured via expected calibration error (ECE), is at most ε.

Key Results

For every fixed $\kappa > 0$ , when $|G| \le \varepsilon^{-\kappa}$ , we prove that $\widetilde{\Theta}(\varepsilon^{-3})$ samples are both necessary and sufficient, up to polylogarithmic factors.
The lower bound holds even for randomized predictors; the upper bound is achieved by randomized predictors obtained via an online-to-batch reduction.
This separates the sample complexity of multicalibration from that of marginal calibration, which scales as $\widetilde{\Theta}(\varepsilon^{-2})$ , and shows that mean-ECE multicalibration is as hard in the batch setting as it is in the online setting, while marginal calibration is strictly harder in the online setting.
In contrast, for $\kappa = 0$ , the sample complexity of multicalibration remains $\widetilde{\Theta}(\varepsilon^{-2})$ , exhibiting a sharp threshold phenomenon.
More generally, we establish matching upper and lower bounds for weighted $$L_p$$ multicalibration measures (for all $1 \le p \le 2$ ), up to polylogarithmic factors, with optimal exponent $$3/p$$ .
We also extend our lower-bound template to regular classes of inducible properties, which—combined with the online upper bounds of Hu et al. (2025)—yields matching bounds for property calibration, including quantile and bounded-density quantile calibration.