Sample Complexity of Multicalibration for Multilevel Properties

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≥2, 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 widetildeOmega(varepsilon-(k+2)) samples. Conversely, for any finite group family mathcal G, we give a randomized learner using O(varepsilon-(k+2)+varepsilon-2log|mathcal G|) samples. Thus the sample complexity is widetildeTheta(varepsilon-(k+2)) for polynomial-size group families. We instantiate the theory for three canonical examples.