{"id":"arxiv/2601.05245","url":"https://arxiv.org/abs/2601.05245","tags":["cs.LG","math.ST","stat.ML"],"score":0,"title":"Optimal Lower Bounds for Online Multicalibration","domain":"cs.LG","source":"arxiv","authors":["Natalie Collina","Jiuyao Lu","Georgy Noarov","Aaron Roth"],"reviews":0,"subject":"cs.LG","summary":"We prove tight lower bounds for online multicalibration, establishing an information-theoretic separation from marginal calibration. In the general setting where group functions can depend on both context and the learner's predictions, we prove an $Ω(T^{2/3})$ lower bound on expected multicalibration error using just three disjoint binary groups. This matches the upper bounds of Noarov et al. (2025) up to logarithmic factors and exceeds the $O(T^{2/3-\\varepsilon})$ upper bound for marginal calibration (Dagan et al., 2025), thereby separating the two problems. We then turn to lower bounds for…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-08","reactions":{}}