← Back to Papers
Key Insights
- The paper proves an Ω(T^{2/3}) information‑theoretic lower bound on expected multicalibration error even when only three disjoint binary groups are used, matching known upper bounds up to log factors.
- This lower bound exceeds the best possible O(T^{2/3‑ε}) rate for marginal calibration, establishing a provable gap between the two notions of calibration in the online setting.
- For the more restrictive setting where group functions may depend on context but not on the learner’s predictions, the authors construct a Θ(T)-sized family of groups via orthogonal function systems and obtain a ~Ω(T^{2/3}) lower bound, again matching the corresponding upper bound up to logarithmic terms.
- The techniques hinge on adversarial constructions that force the learner to incur error on at least one group while remaining compatible with the online feedback model, illustrating why multicalibration inherently requires more samples than marginal calibration.
Abstract
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 the more difficult case of group functions that may depend on context but not on the learner's predictions. In this case, we establish an $\widetildeΩ(T^{2/3})$ lower bound for online multicalibration via a $Θ(T)$-sized group family constructed using orthogonal function systems, again matching upper bounds up to logarithmic factors.
Full Analysis
# Tight Lower Bounds Separate Online Multicalibration from Marginal Calibration
**Authors:** Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth
**Source:** [HuggingFace](None) | [arXiv](https://arxiv.org/abs/2601.05245)
**Published:** 2026-01-08
## Summary
- The paper proves an Ω(T^{2/3}) information‑theoretic lower bound on expected multicalibration error even when only three disjoint binary groups are used, matching known upper bounds up to log factors.
- This lower bound exceeds the best possible O(T^{2/3‑ε}) rate for marginal calibration, establishing a provable gap between the two notions of calibration in the online setting.
- For the more restrictive setting where group functions may depend on context but not on the learner’s predictions, the authors construct a Θ(T)-sized family of groups via orthogonal function systems and obtain a ~Ω(T^{2/3}) lower bound, again matching the corresponding upper bound up to logarithmic terms.
- The techniques hinge on adversarial constructions that force the learner to incur error on at least one group while remaining compatible with the online feedback model, illustrating why multicalibration inherently requires more samples than marginal calibration.
## Abstract
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 the more difficult case of group functions that may depend on context but not on the learner's predictions. In this case, we establish an $\widetildeΩ(T^{2/3})$ lower bound for online multicalibration via a $Θ(T)$-sized group family constructed using orthogonal function systems, again matching upper bounds up to logarithmic factors.
---
*Topics: ai-ml*
*Difficulty: advanced*
*Upvotes: 0*