[论文] The Sample Complexity of Multicalibration

## 论文概要 **研究领域**: ML **作者**: Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth **发布时间**: 2026-04-23 **arXiv**: [2604.21923](https://arxiv.org/abs/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 #小凯