# Low-Degree Multicalibration

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 60 references that are in the map.
- First posted on arXiv 2 Mar 2022.

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

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [On Fairness and Calibration](https://mlsanity.com/paper/1709.02012/) (2017)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Beyond temperature scaling: Obtaining well-calibrated multiclass probabilities with Dirichlet calibration](https://mlsanity.com/paper/1910.12656/) (2019)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Distribution Calibration for Regression](https://mlsanity.com/paper/1905.06023/) (2019)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration](https://mlsanity.com/paper/2107.05719/) (2021)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Moment Multicalibration for Uncertainty Estimation](https://mlsanity.com/paper/2008.08037/) (2020)
- [Fairness Through Computationally-Bounded Awareness](https://mlsanity.com/paper/1803.03239/) (2018)
- [Individual Calibration with Randomized Forecasting](https://mlsanity.com/paper/2006.10288/) (2020)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [A New Analysis of Differential Privacy's Generalization Guarantees](https://mlsanity.com/paper/1909.03577/) (2019)
- [Advancing subgroup fairness via sleeping experts](https://mlsanity.com/paper/1909.08375/) (2019)
- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (2021)
- [Sample Complexity of Uniform Convergence for Multicalibration](https://mlsanity.com/paper/2005.01757/) (2020)
- [Calibration for the (Computationally-Identifiable) Masses](https://mlsanity.com/paper/1711.08513/) (2017)
- [Sum-of-squares proofs and the quest toward optimal algorithms](https://mlsanity.com/paper/1404.5236/) (2014)
- [Multicalibrated Partitions for Importance Weights](https://mlsanity.com/paper/2103.05853/) (2021)
- [Tracking and Improving Information in the Service of Fairness](https://mlsanity.com/paper/1904.09942/) (2019)
- [Right Decisions from Wrong Predictions: A Mechanism Design Alternative to Individual Calibration](https://mlsanity.com/paper/2011.07476/) (2020)

## Built on by (most cited first, 30 of 45)

- [Large language model validity via enhanced conformal prediction methods](https://mlsanity.com/paper/2406.09714/) (2024)
- [Smooth ECE: Principled Reliability Diagrams via Kernel Smoothing](https://mlsanity.com/paper/2309.12236/) (2023)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [A Unifying Theory of Distance from Calibration](https://mlsanity.com/paper/2211.16886/) (2022)
- [Multicalibration for Confidence Scoring in LLMs](https://mlsanity.com/paper/2404.04689/) (2024)
- [A Survey on Intersectional Fairness in Machine Learning: Notions, Mitigation, and Challenges](https://mlsanity.com/paper/2305.06969/) (2023)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [When Does Optimizing a Proper Loss Yield Calibration?](https://mlsanity.com/paper/2305.18764/) (2023)
- [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Loss Minimization Yields Multicalibration for Large Neural Networks](https://mlsanity.com/paper/2304.09424/) (2023)
- [HappyMap: A Generalized Multi-calibration Method](https://mlsanity.com/paper/2303.04379/) (2023)
- [When is Multicalibration Post-Processing Necessary?](https://mlsanity.com/paper/2406.06487/) (2024)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [From Pseudorandomness to Multi-Group Fairness and Back](https://mlsanity.com/paper/2301.08837/) (2023)
- [Fair Risk Control: A Generalized Framework for Calibrating Multi-group Fairness Risks](https://mlsanity.com/paper/2405.02225/) (2024)
- [Multi-group Uncertainty Quantification for Long-form Text Generation](https://mlsanity.com/paper/2407.21057/) (2024)
- [On the Richness of Calibration](https://mlsanity.com/paper/2302.04118/) (2023)
- [Fair admission risk prediction with proportional multicalibration](https://mlsanity.com/paper/2209.14613/) (2022)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)
- [How Global Calibration Strengthens Multiaccuracy](https://mlsanity.com/paper/2504.15206/) (2025)
- [Networked Information Aggregation via Machine Learning](https://mlsanity.com/paper/2507.09683/) (2025)
- [When does a predictor know its own loss?](https://mlsanity.com/paper/2502.20375/) (2025)
- [Discretization-free Multicalibration through Loss Minimization over Tree Ensembles](https://mlsanity.com/paper/2505.17435/) (2025)
- [The Scope of Multicalibration: Characterizing Multicalibration via Property Elicitation](https://mlsanity.com/paper/2302.08507/) (2023)
- [Is your model predicting the past?](https://mlsanity.com/paper/2206.11673/) (2022)
- [Generalized and Unified Equivalences between Hardness and Pseudoentropy](https://mlsanity.com/paper/2507.05972/) (2025)
- [Stability and Multigroup Fairness in Ranking with Uncertain Predictions](https://mlsanity.com/paper/2402.09326/) (2024)
- [Comparing Uncertainty Measurement and Mitigation Methods for Large Language Models: A Systematic Review](https://mlsanity.com/paper/2504.18346/) (2025)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)

## Abstract (arXiv)

Introduced as a notion of algorithmic fairness, multicalibration has proved to be a powerful and versatile concept with implications far beyond its original intent. This stringent notion -- that predictions be well-calibrated across a rich class of intersecting subpopulations -- provides its strong guarantees at a cost: the computational and sample complexity of learning multicalibrated predictors are high, and grow exponentially with the number of class labels. In contrast, the relaxed notion of multiaccuracy can be achieved more efficiently, yet many of the most desirable properties of multicalibration cannot be guaranteed assuming multiaccuracy alone. This tension raises a key question: Can we learn predictors with multicalibration-style guarantees at a cost commensurate with multiaccuracy? In this work, we define and initiate the study of Low-Degree Multicalibration. Low-Degree Multicalibration defines a hierarchy of increasingly-powerful multi-group fairness notions that spans multiaccuracy and the original formulation of multicalibration at the extremes. Our main technical contribution demonstrates that key properties of multicalibration, related to fairness and accuracy, actually manifest as low-degree properties. Importantly, we show that low-degree multicalibration can be significantly more efficient than full multicalibration. In the multi-class setting, the sample complexity to achieve low-degree multicalibration improves exponentially (in the number of classes) over full multicalibration. Our work presents compelling evidence that low-degree multicalibration represents a sweet spot, pairing computational and sample efficiency with strong fairness and accuracy guarantees.