标题： 在线多校准的最优下界 显示英文标题

标题： Optimal Lower Bounds for Online Multicalibration

摘要： 我们证明了在线多校准的紧下界，确立了与边缘校准的信息理论分离。 在组函数可以同时依赖于上下文和学习者的预测的一般情况下，我们仅使用三个不相交的二元组，证明了期望多校准误差的$Ω(T^{2/3})$下界。 这与 Noarov 等人 (2025) 的上界在对数因子范围内匹配，并超过了 Dagan 等人 (2025) 的边缘校准的$O(T^{2/3-\varepsilon})$上界，从而区分了这两个问题。 然后我们转向组函数可能依赖于上下文但不依赖于学习者预测的更困难情况的下界。 在这种情况下，我们通过使用正交函数系统构造的$Θ(T)$大小的组族，建立了在线多校准的$\widetildeΩ(T^{2/3})$下界，再次在对数因子范围内匹配上界。 显示英文摘要

摘要： 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.