研究多层级属性的多校准样本复杂度，给出精确的理论边界。
Sample Complexity of Multicalibration for Multilevel Properties
- 针对多层级属性设计多校准框架，逐层依赖前序属性。
- 证明样本复杂度为ε^{-(k+2)}量级，与分组数量相关。
- 适用于需要多属性精准校准的公平性建模场景。
校准要求预测器在给定自身预测值的条件下无偏。多校准则要求在一组群体中同时满足该条件。许多预测任务需对同一条件分布的多个相关特征进行建模：方差相对于均值定义，偏度相对于均值和方差，条件风险价值相对于分位数。本文研究一种包含k个属性的序列多校准问题，其中每个属性在前序属性确定后可识别。该框架涵盖贝叶斯对，但不要求属性来自单一损失函数。对于任意固定k≥2，我们在正则条件下建立了匹配的上下界（忽略对数因子）。即使仅有多项式对数大小的二元分组，实现多校准误差ε也需至少˜Ω(ε^{-(k+2)})样本。反之，对任意有限分组族𝒢，我们给出一个随机学习算法，仅需O(ε^{-(k+2)} + ε^{-2} log|𝒢|)样本。因此，对于多项式大小的分组族，样本复杂度为˜Θ(ε^{-(k+2)})。本文通过三个典型实例验证了该理论。
原文摘要 · Abstract (English)
Calibration requires a predictor to be unbiased after conditioning on its own predictions. Multicalibration asks for this guarantee simultaneously across a collection of groups. Many prediction tasks ask for several related features of the same conditional outcome distribution: variance is defined relative to the mean, skewness relative to both mean and variance, and conditional value at risk relative to a quantile. We study multicalibration for a sequence of $k$ properties in which each property is identifiable once the preceding properties are fixed. This framework includes Bayes pairs but does not require the properties to arise from a single loss. For every fixed $k\ge2$, we establish matching upper and lower sample-complexity bounds up to logarithmic factors under regularity conditions. Even with only polylogarithmically many binary groups, achieving multicalibration error $\varepsilon$ requires $\widetildeΩ(\varepsilon^{-(k+2)})$ samples. Conversely, for any finite group family $\mathcal G$, we give a randomized learner using $O(\varepsilon^{-(k+2)}+\varepsilon^{-2}\log|\mathcal G|)$ samples. Thus the sample complexity is $\widetildeΘ(\varepsilon^{-(k+2)})$ for polynomial-size group families. We instantiate the theory for three canonical examples.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。