Optimal Lower Bounds for Online Multicalibration
This provides foundational theoretical insights for fairness and calibration in machine learning, addressing a key problem for researchers and practitioners in algorithmic decision-making.
The paper tackles the problem of establishing lower bounds for online multicalibration, proving tight information-theoretic separations from marginal calibration. It shows an Ω(T^{2/3}) lower bound on expected multicalibration error in general settings, matching upper bounds up to logarithmic factors and exceeding bounds for marginal calibration.
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.