Paper Overview
Field: Machine Learning Authors: Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth arXiv: 2604.21923
Abstract (English Translation)
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 in expected calibration error (ECE) with respect to a given collection of groups — is at most ε. For every fixed κ > 0, in the range |G| ≤ ε^{-κ}, we prove that Õ(ε^{-3}) samples are both necessary and sufficient, up to polylogarithmic factors. The lower bound holds even for randomized predictors, and the upper bound is achieved via randomized predictors obtained from an online-to-batch reduction. This separates the sample complexity of multicalibration from that of marginal calibration, which scales as Õ(ε^{-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, we observe that for κ = 0, the sample complexity of multicalibration remains Õ(ε^{-2}), exhibiting a sharp threshold phenomenon.
More generally, we establish matching upper and lower bounds — up to polylogarithmic factors — for weighted Lp multicalibration measures for all 1 ≤ p ≤ 2, with an optimal exponent of 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 quantiles and bounded-density quantiles.
Links
- arXiv: https://arxiv.org/abs/2604.21923