# Sample Complexity of Uniform Convergence for Multicalibration

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2020.

## Built on by (most cited first, 24 of 24)

- [On Calibration and Out-of-domain Generalization](https://mlsanity.com/paper/2102.10395/) (2021)
- [Assessing Generalization of SGD via Disagreement](https://mlsanity.com/paper/2106.13799/) (2021)
- [Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration](https://mlsanity.com/paper/2107.05719/) (2021)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Don't Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification](https://mlsanity.com/paper/2102.07856/) (2021)
- [Multicalibration as Boosting for Regression](https://mlsanity.com/paper/2301.13767/) (2023)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [When is Multicalibration Post-Processing Necessary?](https://mlsanity.com/paper/2406.06487/) (2024)
- [Understanding the Under-Coverage Bias in Uncertainty Estimation](https://mlsanity.com/paper/2106.05515/) (2021)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)
- [Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability](https://mlsanity.com/paper/2203.04536/) (2022)
- [Reconciling Model Multiplicity for Downstream Decision Making](https://mlsanity.com/paper/2405.19667/) (2024)
- [MCGrad: Multicalibration at Web Scale](https://mlsanity.com/paper/2509.19884/) (2025)
- [An Exploration of Multicalibration Uniform Convergence Bounds](https://mlsanity.com/paper/2202.04530/) (2022)
- [Stability and Multigroup Fairness in Ranking with Uncertain Predictions](https://mlsanity.com/paper/2402.09326/) (2024)
- [Measuring multi-calibration](https://mlsanity.com/paper/2506.11251/) (2025)
- [Heterogeneous Calibration: A post-hoc model-agnostic framework for improved generalization](https://mlsanity.com/paper/2202.04837/) (2022)
- [Multi-Group Proportional Representation in Retrieval](https://mlsanity.com/paper/2407.08571/) (2024)
- [Optimal and Provable Calibration in High-Dimensional Binary Classification: Angular Calibration and Platt Scaling](https://mlsanity.com/paper/2502.15131/) (2025)
- [Optimal Deterministic Multicalibration and Omniprediction](https://mlsanity.com/paper/2606.20557/) (2026)
- [Instance-Adaptive Online Multicalibration](https://mlsanity.com/paper/2605.09273/) (2026)
- [Auditability and the Landscape of Distance to Multicalibration](https://mlsanity.com/paper/2509.16930/) (2025)

## Abstract (arXiv)

There is a growing interest in societal concerns in machine learning systems, especially in fairness. Multicalibration gives a comprehensive methodology to address group fairness. In this work, we address the multicalibration error and decouple it from the prediction error. The importance of decoupling the fairness metric (multicalibration) and the accuracy (prediction error) is due to the inherent trade-off between the two, and the societal decision regarding the "right tradeoff" (as imposed many times by regulators). Our work gives sample complexity bounds for uniform convergence guarantees of multicalibration error, which implies that regardless of the accuracy, we can guarantee that the empirical and (true) multicalibration errors are close. We emphasize that our results: (1) are more general than previous bounds, as they apply to both agnostic and realizable settings, and do not rely on a specific type of algorithm (such as deferentially private), (2) improve over previous multicalibration sample complexity bounds and (3) implies uniform convergence guarantees for the classical calibration error.