揭示多校准的样本复杂度，发现其比单校准更难且存在明显阈值现象。
The Sample Complexity of Multicalibration
- 通过在线转批量方法构造随机预测器，实现最优样本效率
- 当分组数不超过ε⁻ᵏ时，需约ε⁻³量级样本，比单校准更耗样本
- 首次证明多校准在批量设置下与在线设置难度相当，适合关注公平性建模的研究者
研究批量设置下多校准的极小最大样本复杂度。学习者从未知分布中观察n个独立同分布样本，需输出一个（可能随机的）预测器，使其总体多校准误差（以期望校准误差ECE衡量）相对于给定分组族不超过ε。对于每个固定的κ>0，当|G|≤ε⁻ᵏ时，我们证明了˜Θ(ε⁻³)样本在必要性和充分性上均成立，仅含对数因子差异。该下界即使对随机预测器也成立，上界由在线转批量方法得到的随机预测器实现。这将多校准的样本复杂度与边际校准（˜Θ(ε⁻²)）区分开来，并表明均值-ECE多校准在批量设置下的难度与在线设置相当，而边际校准在在线设置中更困难。相反，当κ=0时，多校准的样本复杂度仍为˜Θ(ε⁻²)，呈现出明显的阈值现象。更一般地，我们对所有1≤p≤2的加权L_p多校准度量建立了匹配的上下界，最优指数为3/p。我们还将下界模板扩展至一类可诱导属性，并结合Hu等（2025）的在线上界，获得对期望值和有界密度分位数等属性校准的匹配边界。
原文摘要 · Abstract (English)
We study the minimax sample complexity of multicalibration in the batch setting. A learner observes $n$ i.i.d. samples from an unknown distribution and must output a (possibly randomized) predictor whose population multicalibration error, measured by Expected Calibration Error (ECE), is at most $\varepsilon$ with respect to a given family of groups. For every fixed $κ> 0$, in the regime $|G|\le \varepsilon^{-κ}$, we prove that $\widetildeΘ(\varepsilon^{-3})$ samples are necessary and sufficient, up to polylogarithmic factors. The lower bound holds even for randomized predictors, and the upper bound is realized by a randomized predictor obtained via an online-to-batch reduction. This separates the sample complexity of multicalibration from that of marginal calibration, which scales as $\widetildeΘ(\varepsilon^{-2})$, and shows that mean-ECE multicalibration is as difficult in the batch setting as it is in the online setting, in contrast to marginal calibration which is strictly more difficult in the online setting. In contrast we observe that for $κ= 0$, the sample complexity of multicalibration remains $\widetildeΘ(\varepsilon^{-2})$ exhibiting a sharp threshold phenomenon. More generally, we establish matching upper and lower bounds, up to polylogarithmic factors, for a weighted $L_p$ multicalibration metric for all $1 \le p \le 2$, with optimal exponent $3/p$. We also extend the lower-bound template to a regular class of elicitable properties, and combine it with the online upper bounds of Hu et al. (2025) to obtain matching bounds for calibrating properties including expectiles and bounded-density quantiles.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。