[论文] The Sample Complexity of Multicalibration

论文概要

研究领域: ML
作者: Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth
发布时间: 2026-04-23
arXiv: 2604.21923

中文摘要

我们研究批量设置中多校准的极小极大样本复杂度。学习者从未知分布中观察n个i.i.d.样本，必须输出一个（可能是随机化的）预测器，其相对于给定群体族的人口多校准误差（以期望校准误差ECE衡量）至多为ε。对于每个固定的κ>0，在|G|≤ε^{-κ}的范围内，我们证明需要且仅需\(\widetilde{\Theta}(\varepsilon^{-3})\)样本，最多相差多对数因子。下界即使对随机化预测器也成立，上界通过在线到批量的约简获得的随机化预测器实现。这将多校准的样本复杂度与边际校准分开，后者缩放为\(\widetilde{\Theta}(\varepsilon^{-2})\)，并表明均值-ECE多校准在批量设置中与在线设置中一样困难，而边际校准在在线设置中则严格更困难。相反，我们观察到对于κ=0，多校准的样本复杂度保持为\(\widetilde{\Theta}(\varepsilon^{-2})\)，表现出急剧的阈值现象。更一般地，我们为加权\(L_p\)多校准度量（对所有\(1 \le p \le 2\)）建立了匹配的上界和下界，最多相差多对数因子，最优指数为3/p。我们还将下界模板扩展到可诱导属性的正则类，并结合Hu等人（2025）的在线上界，获得包括分位数和有界密度分位数在内的属性校准的匹配界。

原文摘要

自动采集于 2026-04-27

#论文 #arXiv #ML #小凯