证明在线多校准的最优下界，揭示其与边际校准的本质差异。
Optimal Lower Bounds for Online Multicalibration
- 基于三组互斥二分类群体，构造信息论下界
- 在一般情形下达到Ω(T^{2/3})，与上界对齐
- 适用于关注公平性与预测校准的研究者
本文证明了在线多校准问题的紧致下界，建立了其与边际校准之间的信息论分离。在群体函数可依赖于上下文和学习者预测的一般情形下，仅使用三个互斥的二分类群体，即证明了期望多校准误差的Ω(T^{2/3})下界。该结果与Noarov等（2025）的上界在对数因子内匹配，并显著超过边际校准O(T^{2/3−ε})的上界（Dagan等，2025），从而实现两者的严格分离。随后针对更困难的情形——群体函数可依赖上下文但不可依赖预测，我们通过一个大小为O(log³T)的群族（基于正交基构造），建立了𝑚(T^{2/3})的下界，再次与上界在对数因子内一致。
原文摘要 · Abstract (English)
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 an $O(\log^3 T)$-sized group family constructed from an orthonormal basis, again matching upper bounds up to logarithmic factors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。