多重校准的样本复杂度

The Sample Complexity of Multicalibration

arXiv: 2604.21923v1

论文信息

标题: The Sample Complexity of Multicalibration

作者: Natalie Collina, Jiuyao Lu, Georgy Noarov, et al.

发布日期: 2026-04-23

arXiv ID: 2604.21923v1

PDF 链接: 下载 PDF

3 分钟速览

  • 研究问题： 本文研究批量设置下多重校准（multicalibration）的最小最大样本复杂度，即需要多少独立同分布样本才能将多重校准误差控制在 ε 以内。
  • 核心方法： 通过构造一个由编码理论驱动的困难实例（包含压缩群族和阶梯函数分布族），将多重校准问题归约为精确解码问题，再利用 Fano 不等式导出下界；上界则通过在线算法到批量学习的转化得到。
  • 关键结果： 对于均值 ECE 多重校准，最优样本复杂度为 Θ~(ε−3)\widetilde{\Theta}(\varepsilon^{-3})，且该下界对随机化预测器也成立（见定理 14）。
  • 主要局限： 对于 LpL_p 多重校准指标，当 p>2p>2 时的下界尚未建立；群族大小与 ε 的联合依赖关系在 κ=0\kappa=0 的极小群族区间外仍需进一步精细刻画。
  • 适合读者： 从事统计学习理论、算法公平性、预测校准或信息论下界研究的学者和研究生。

论文背景和研究动机

校准（calibration）是预测模型可靠性的基石：一个校准好的预测器，其输出的预测值应当等于条件于该预测值的真实期望结果。然而，经典的边缘校准（marginal calibration）仅要求全局意义上的无偏性，一个常数值预测器（如始终输出总体均值）即可满足要求，这显然无法刻画预测质量。

Hebert-Johnson 等人于 2018 年提出的多重校准概念从根本上强化了这一要求：预测器必须在每个由群函数 GG 定义的子总体上都同时满足校准条件。这一概念及其变体已在全预测（omniprediction）、分布式信息聚合、复杂度理论构造等方向展现出广泛应用。

尽管多重校准的算法研究已有近十年历史，其最优样本复杂度——作为目标误差 ε 的函数——一直悬而未决。早期算法给出的样本复杂度从 O~(ε−7)\widetilde{O}(\varepsilon^{-7}) 逐步改进到 O~(ε−4)\widetilde{O}(\varepsilon^{-4})，最近 Noarov 等人（2025）的在线算法结合适当的在线到批量转化可达到 O~(ε−3)\widetilde{O}(\varepsilon^{-3})。上界在不断改进，而下界却长期停留在由均值估计导出的平凡下界 Ω(ε−2)\Omega(\varepsilon^{-2})。Gibbs 和 Tibshirani（2025）虽将这一下界推进到 Ω(ε−5/2)\Omega(\varepsilon^{-5/2})，但仅适用于确定性预测器。随机化预测器是否能将样本复杂度降至 ε−2\varepsilon^{-2} 级别，一直悬而未决。

这一差距的存在不仅关乎理论完整性，更直接影响实践：若样本复杂度确实为 O~(ε−3)\widetilde{O}(\varepsilon^{-3})，则意味着在某些群族结构下，多重校准所需的样本量比普通边缘校准高出约 1/ε1/\varepsilon 倍——当 ε 较小时，这是数量级的差异。

核心方法和技术细节

下界构造的整体架构

本文的下界证明遵循一条清晰的逻辑链：首先构造一个特定的困难实例，然后证明在该实例上，多重校准误差小意味着预测误差小，预测误差小进一步意味着能精确解码隐藏参数，最后通过信息论下界证明精确解码所需样本量必然很大。

困难实例由两个组件构成：

群族 GmG_m（定义 19）：采用基于编码理论的压缩二分构造。在大小为 mm 的有序域上，通过二分区间分解和低相关编码，使用仅 polylog(m)\text{polylog}(m) 个群函数就能近似表示所有 mm 个阈值符号函数。具体而言，每个二分尺度 hh 上的区间由长度 khk_h 的符号向量标识，这些向量来自引理 17 保证存在的低相关编码，其内积绝对值不超过 ρmkh\rho_m k_h（其中 ρm=1/(8(1+log⁡2m))\rho_m = 1/(8(1+\log_2 m))）。

分布族 HmΓ\mathcal{H}_m^{\Gamma}（定义 23）：对于每个由 packing 码 Θm\Theta_m（来自引理 18）索引的参数 θ\theta，定义阶梯映射 tθt_\theta。该映射在奇数位置按等差级数上升（步长 4γm4\gamma_m），在偶数位置根据码字 θj\theta_j 决定是否额外上升 γm\gamma_m。当 Γ\Gamma 为均值属性时，tθt_\theta 恰为回归函数，这一构造使得不同 θ\theta 对应的回归函数在 L1L_1 距离上至少相隔 γm/16\gamma_m/16（引理 24）。

从多重校准到精确解码的归约

命题 26 证明了核心引理：对于任何非递减的 t:[m]→I0t:[m]\to I_0 和任何随机化预测器 QQ，其预测误差 Δt(Q)\Delta_t(Q) 不超过 O(log⁡m)⋅MCtΓ(Q;Gm)O(\log m) \cdot \text{MC}_t^\Gamma(Q; G_m)。

证明的关键在于利用阶梯映射的单增性：对于任意预测值 vv，符号模式 v−t(i)v - t(i) 必然等价于某个阈值函数。由于群族 GmG_m 可通过系数和有界地近似所有阈值（引理 22），预测误差可被分解为群函数上的偏差之和，每个偏差又不超过多重校准误差。系数的有界性（sup⁡r∣α0(r)∣≤1\sup_r |\alpha_0(r)| \leq 1，∑h,qsup⁡r∣αh,q(r)∣≤2log⁡2m\sum_{h,q} \sup_r |\alpha_{h,q}(r)| \leq 2\log_2 m）确保了 log⁡m\log m 因子。

命题 27 进一步利用分布族的分离性质：当多重校准误差降至 cΓγm/(384(1+log⁡2m))c_\Gamma \gamma_m / (384(1+\log_2 m)) 以下时，最近邻解码器能以概率 1 恢复真实的 θ\theta。

Fano 不等式的应用

引理 28 完成信息论下界：参数空间大小 log⁡∣Θm∣=Ω(m)\log |\Theta_m| = \Omega(m)，而任意两个分布的 KL 散度不超过 CΓ,KLγm2/2C_{\Gamma,\text{KL}} \gamma_m^2 / 2（引理 25）。Fano 不等式给出：

n≥Ω(log⁡∣Θm∣γm2)=Ω(m3).n \geq \Omega\left(\frac{\log |\Theta_m|}{\gamma_m^2}\right) = \Omega(m^3).

代入 m=Θ(1/(ε1/plog⁡(1/ε)))m = \Theta(1/(\varepsilon^{1/p} \log(1/\varepsilon)))，得到 Ω~(ε−3/p)\widetilde{\Omega}(\varepsilon^{-3/p})。

对于 p∈[1,2]p \in [1,2] 的 LpL_p 指标，通过 Hölder 不等式 MC≤(MC(p))1/p\text{MC} \leq (\text{MC}^{(p)})^{1/p}，将 ECE 下界转化为 LpL_p 下界而不损失指数。

上界构造

上界采用在线到批量转化框架。对于均值 ECE（定理 32），将 Noarov 等人（2025）的在线算法在 TT 轮上的经验 ECE 误差 O~(T−1/3)\widetilde{O}(T^{-1/3}) 结合 Azuma-Hoeffding 鞅差集中，得到批量预测器的人口误差同为 O~(T−1/3)\widetilde{O}(T^{-1/3})，因此需 T=O~(ε−3)T = \widetilde{O}(\varepsilon^{-3}) 样本。

对于一般的 LpL_p 指标（定理 30），证明更为精细。关键困难在于指标中的比值形式 ∣Bk∣p/πkp−1|B_k|^p / \pi_k^{p-1}：在质量轻的桶中分母可能导致误差膨胀。处理方式为设定阈值 τ=Θ~(1/T)\tau = \widetilde{\Theta}(1/T)，轻桶贡献不超过 KτK\tau，重桶则通过方差自适应 Freedman 不等式和二分剥离技术控制，最终得到 O~(ε−3/p)\widetilde{O}(\varepsilon^{-3/p})（1≤p≤21 \leq p \leq 2 时）的样本复杂度。

创新点和贡献

  1. 首次确定多重校准的紧最小最大样本复杂度：证明 Θ~(ε−3)\widetilde{\Theta}(\varepsilon^{-3}) 是均值 ECE 多重校准的紧界（上界见定理 32，下界见定理 14），解决了多年来的开放问题。

  2. 下界对随机化预测器成立：此前的下界 Ω(ε−5/2)\Omega(\varepsilon^{-5/2}) 仅适用于确定性预测器（Gibbs 和 Tibshirani，2025），本文将其推进到 Ω~(ε−3)\widetilde{\Omega}(\varepsilon^{-3}) 且不受随机化影响，说明随机化不能根本性地降低多重校准的样本复杂度。

  3. 揭示批量与在线设置的差异：边际校准在批量和在线设置中的难度不同（批量 Θ(ε−2)\Theta(\varepsilon^{-2})，在线 Θ~(T−1/3)\widetilde{\Theta}(T^{-1/3}) 不可达），而多重校准在两种设置中均为 Θ~(ε−3)\widetilde{\Theta}(\varepsilon^{-3})，显示出多重校准本质上不受对抗性影响。

  4. 扩展到一般学习属性：引入正则学习属性（regular elicitable properties）框架（定义 11），将下界模板推广到包含期望分位点（expectiles）和有界密度分位点（bounded-density quantiles）在内的属性族（定理 13），同时与 Hu 等人（2025）的在线算法结合给出紧上界。

  5. 统一的编码理论构造：通过简单的概率方法引理（引理 16）同时提供 packing 码和低相关码，以一致的方式构建整个困难实例，展现了编码理论在统计学习下界中的力量。

局限与待解决问题

LpL_p 指标当 p>2p>2 时的下界缺失：本文的 LpL_p 下界通过 Hölder 不等式从 L1L_1 导出，当 p>2p>2 时这一归约会损失指数。作者指出，直接设计针对大 pp 的困难实例并非显然，因为此时指标对轻桶的惩罚更重，需要分布构造具有不同的信息论性质。定理 30 虽然给出了匹配的上界 O~(ε−(p+1)/p)\widetilde{O}(\varepsilon^{-(p+1)/p})，但下界仍停留在 Ω~(ε−3)\widetilde{\Omega}(\varepsilon^{-3})，留下明显的间隙。

群族大小的精细依赖：本文的主要结果在 κ>0\kappa>0（群族大小允许随 ε\varepsilon 多项式增长）的区间内成立。当 κ=0\kappa=0（群族大小固定为常数）时，样本复杂度退化为 O~(ε−2)\widetilde{O}(\varepsilon^{-2})（通过经验区域均值预测实现），与多重校准的 Θ~(ε−3)\widetilde{\Theta}(\varepsilon^{-3}) 形成尖锐阈值。然而，在群族大小仅以对数多项式增长（如 polylog(1/ε)\text{polylog}(1/\varepsilon)）的中间区间与 κ>0\kappa>0 区间之间，样本复杂度的过渡行为尚未完全刻画。

其他属性类的完备性：正则属性的定义包含了均值、期望分位点和有界密度分位点，但并非所有学习属性都满足其条件（尤其是 KL 散度的二次上界）。论文未讨论如何将下界推广到不满足这些条件的属性类，也未说明正则性是获得 ε−3/p\varepsilon^{-3/p} 速率的最小充分条件。