Optimal Lower Bounds for Online Multicalibration

Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth

arXivarxiv/2601.05245Jan 8, 2026cs.LGscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2601.05245
curl -X POST /api/v1/records/arxiv/2601.05245/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.05245/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'