다단계 속성에 대한 다중 교정의 표본 복잡도

Sample Complexity of Multicalibration for Multilevel Properties

교정은 예측자가 자신의 예측값에 조건화된 후에도 편향되지 않도록 요구합니다. 다중 교정은 이러한 보장이 여러 그룹 전체에 걸쳐 동시에 만족되도록 합니다. 많은 예측 작업에서는 동일한 조건부 결과 분포의 여러 관련 특성을 필요로 합니다. 분산은 평균을 기준으로 정의되고, 왜도는 평균과 분산을 기준으로 정의되며, 조건부 가치 위험(value at risk)은 특정 분위수를 기준으로 정의됩니다. 본 연구는 $k$개의 속성 시퀀스에 대한 다중 교정을 다룹니다. 여기서 각 속성은 이전 속성이 고정되면 식별 가능합니다. 이 프레임워크는 베이즈 쌍을 포함하지만, 속성들이 단일 손실 함수에서 비롯될 필요는 없습니다. 고정된 $k ext{ } ( ext{} k ext{ } ext{>=} 2)$에 대해, 우리는 정규 조건 하에서 상/하한 표본 복잡도 경계를 제시합니다. 다수의 이진 그룹이라 할지라도, 다중 교정 오류 $ ext{ } ext{ε}$을 달성하는 데에는 $ ext{ } ext{Ω}( ext{ } ext{ε}^{- ext{(}k+2 ext{)}}$)만큼의 표본이 필요합니다. 반대로, 임의의 유한 그룹 패밀리 $ ext{ } ext{G}$에 대해, 우리는 $O( ext{ } ext{ε}^{- ext{(}k+2 ext{)}}+ ext{ } ext{ε}^{-2} ext{log}| ext{ } ext{G}|)$개의 표본을 사용하는 랜덤 학습기를 제시합니다. 따라서 다항식 크기의 그룹 패밀리에 대해서는 표본 복잡도는 $ ext{ } ext{Θ}( ext{ } ext{ε}^{- ext{(}k+2 ext{)}}$)입니다. 본 이론을 세 가지 대표적인 예시에 대해 구체적으로 설명합니다.

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.