# Sample Complexity of Multicalibration for Multilevel Properties

arXiv: https://arxiv.org/abs/2608.04288 · HTML: https://mlsanity.com/paper/2608.04288/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 46 references that are in the map.
- First posted on arXiv 4 Aug 2026.

## Builds on (most cited first, 3 of 3)

- [An Exploration of Multicalibration Uniform Convergence Bounds](https://mlsanity.com/paper/2202.04530/) (2022)
- [Supersimulators](https://mlsanity.com/paper/2509.17994/) (2025)
- [The Sample Complexity of Multicalibration](https://mlsanity.com/paper/2604.21923/) (2026)

## Abstract (arXiv)

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.