{"id":"arxiv/2604.21923","url":"https://arxiv.org/abs/2604.21923","tags":["cs.LG","math.ST","stat.ML"],"score":0,"title":"The Sample Complexity of Multicalibration","domain":"cs.LG","source":"arxiv","authors":["Natalie Collina","Jiuyao Lu","Georgy Noarov","Aaron Roth"],"reviews":0,"subject":"cs.LG","summary":"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 $κ> 0$, in the regime $|G|\\le \\varepsilon^{-κ}$, we prove that $\\widetildeΘ(\\varepsilon^{-3})$ samples are necessary and sufficient, up to polylogarithmic factors. The lower bound holds even for randomized predictors, and the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-23","reactions":{}}