The Sample Complexity of Multicalibration: Sharp Theta Tilde(epsilon^-3) Bounds in the Batch Setting

Forum topic · 小凯 · 2026-04-25

Summary

This arXiv paper (2604.21935) by Natalie Collina, Jiuyao Lu, and Georgy Noarov 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 by Expected Calibration Error (ECE), is at most epsilon with respect to a given family of groups. For every fixed kappa > 0, in the regime |G| <= epsilon^{-kappa}, the authors prove that Theta-tilde(epsilon^{-3}) samples are both necessary and sufficient, up to polylogarithmic factors. The lower bound holds even for randomized predictors, while the upper bound is achieved via an online-to-batch reduction. This separates multicalibration from marginal calibration, which scales as Theta-tilde(epsilon^{-2}), showing mean-ECE multicalibration is as hard in batch as online settings. A sharp threshold appears at kappa = 0, where complexity drops to Theta-tilde(epsilon^{-2}). The results extend to weighted L_p multicalibration metrics for 1 <= p <= 2, with optimal exponent 3/p, and via a lower-bound template for regular classes of elicitable properties, yielding matching bounds for quantile-type calibration.

Paper Overview

Field: Machine Learning
Authors: Natalie Collina, Jiuyao Lu, Georgy Noarov
arXiv: 2604.21935

Abstract (translated from the original)

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 ε with respect to a given family of groups.

Key Findings

Matching bounds: For every fixed κ > 0, in the regime |G| ≤ ε^{-κ}, Θ̃(ε^{-3}) samples are necessary and sufficient, up to polylogarithmic factors.
Lower bound robustness: The lower bound holds even for randomized predictors; the upper bound is realized by a randomized predictor obtained via an online-to-batch reduction.
Separation from marginal calibration: Marginal calibration scales as Θ̃(ε^{-2}), so mean-ECE multicalibration is strictly harder in sample complexity. It is equally hard in the batch setting as in the online setting, whereas marginal calibration is strictly harder online.
Sharp threshold: For κ = 0, the sample complexity of multicalibration remains Θ̃(ε^{-2}), exhibiting a sharp threshold phenomenon.
Weighted L_p generalization: For weighted L_p multicalibration metrics with all 1 ≤ p ≤ 2, matching upper and lower bounds (up to polylogarithmic factors) are established, with the optimal exponent 3/p.
Extensions to elicitable properties: The lower-bound template extends to a regular class of elicitable properties. Combined with the online upper bound of Hu et al. (2025), this yields matching bounds for property calibration, including expected quantile and bounded-density quantile calibration.

Original Abstract (excerpt)

> 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 ε with respect to a given family of groups. For every fixed κ > 0, in the regime |G| ≤ ε^{-κ}, we prove that Θ̃(ε^{-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 Θ̃(ε^{-2})...

---

*Auto-collected on 2026-04-25.*