Auditability and the Landscape of Distance to Multicalibration

Nathan Derhake, Siddartha Devic, Dutch Hansen, Kuan Liu, Vatsal Sharan

TL;DR

This paper explores how to measure the "distance" between a machine learning model and a state of perfect multicalibration—a rigorous fairness standard. The authors reveal a fundamental tension: natural metrics either have "traps" (local minima) that hinder optimization or are "inauditable" (impossible to estimate from finite data). They solve this by proposing a new "continuized" metric that is both mathematically well-behaved and statistically estimable.

What Problem Does This Paper Address?

In high-stakes AI (like lending or medicine), we don't just want a model to be accurate; we want it to be calibrated. If a model says there is a 70% risk, that event should happen exactly 70% of the time. Multicalibration takes this further, requiring the model to be calibrated across many potentially overlapping subgroups (e.g., age, race, and geography simultaneously).

As practitioners start using multicalibration, a critical question arises: How do we measure how far a model is from being multicalibrated?

The authors identify two "must-have" properties for any such metric:

  1. Nice Landscape: The metric should have a "local minima are global minima" property. If it doesn't, an algorithm trying to improve fairness might get stuck in a "fairness trap" where it looks like no improvement is possible, even though a much fairer model exists nearby.
  2. Auditability: We must be able to estimate the metric using a reasonable number of data samples. If a tiny change in the underlying truth causes a massive jump in the metric, we can never trust our measurements.

Methods

The authors build on the distance to Calibration Error (dCE) framework. They analyze several candidate metrics:

  • wdMC (Worst-group distance to Multicalibration): Measures the worst-performing subgroup.
  • dMC (Distance to Multicalibration): Measures the distance to the nearest set of perfectly multicalibrated predictors.
  • dIMC (Distance to Intersection Multicalibration): A new metric requiring calibration on all possible intersections of defined subgroups.

The paper uses geometric analysis to map the "loss landscape" of these metrics and information theory (specifically Le Cam’s method) to prove whether these metrics can be "audited" with finite samples. They also employ a clever "continuization" technique—essentially smoothing out the mathematical "jumps" in the dMC metric to make it auditable.

Datasets

This is a theoretical paper and does not use standard empirical datasets like ImageNet or Census data. Instead, the authors construct synthetic mathematical instances and "hard examples" to prove their theorems. For instance, they use a specific construction based on the Fibonacci recurrence to demonstrate how certain bias metrics can be misleadingly small even when a model is far from being fair.

Key Insights and Ideas

  • The Discontinuity Trap: The authors show that the most "natural" metric (dMC) is actually impossible to audit. A microscopic change in the ground truth can cause the set of "perfectly multicalibrated models" to shift or shrink violently, causing the distance metric to jump. This means you can't reliably measure it from data.
  • Smoothing leads to Intersectionality: To fix the auditability problem, the authors "continuize" (smooth) the metric. Surprisingly, they prove that this smoothed metric is mathematically equivalent to requiring intersectional fairness—meaning the model must be calibrated on every possible combination of the defined subgroups.
  • Local is Global: They prove that for dMC and its variants, the loss landscape is "nice." Even though the set of fair models is non-convex, the distance to that set has no "bad" local minima. This suggests that, in theory, we could use gradient-based methods to "push" models toward multicalibration.
  • The Fibonacci Barrier: For the simpler property of multiaccuracy (being unbiased on groups), they show that "worst-group bias" is a poor proxy for distance. Using a Fibonacci-based construction, they show a model can have tiny bias on every group but still be exponentially far away from any truly unbiased model.

Key Results

  • Failure of wdMC: The authors prove that the "worst-group" approach (common in practice) has bad local minima, meaning optimization can fail.
  • Inauditability of dMC: They prove that dMC cannot be estimated with any finite number of samples due to its lack of "Lipschitz continuity" relative to the ground truth.
  • The "Goldilocks" Metric: They identify dIMC (Distance to Intersection Multicalibration) as the winner. It satisfies both desiderata: it has a clean loss landscape and is statistically auditable.
  • Hierarchy of Metrics: The paper establishes a formal hierarchy (Proposition 22), showing how these different fairness notions relate to one another mathematically.

Limitations and Future Work

  • The Curse of Dimensionality: While the proposed dIMC metric is auditable, its sample complexity can be exponential in the number of subgroups ($2^k$). In practice, if you have 20 overlapping groups, auditing the "intersections" becomes statistically expensive.
  • Finite Domain: The current proofs assume a finite (though large) set of possible individuals ($\mathcal{X}$). Extending this to continuous or infinite domains remains an open challenge.
  • Simpler Truths: The authors suggest that if we assume the "ground truth" is simple (e.g., has low VC dimension), we might find more efficient ways to audit these metrics.

Summary updated

Abstract

Calibration is a critical property for establishing the trustworthiness of predictors that provide uncertainty estimates. Multicalibration is a strengthening of calibration which requires that predictors be calibrated on a potentially overlapping collection of subsets of the domain. As multicalibration grows in popularity with practitioners, an essential question is: how do we measure how multicalibrated a predictor is? Błasiok et al. (2023) considered this question for standard calibration by introducing the distance to calibration framework (dCE) to understand how calibration metrics relate to each other and the ground truth. Building on the dCE framework, we consider the auditability of the distance to multicalibration of a predictor $f$. We begin by considering two natural generalizations of dCE to multiple subgroups: worst group dCE (wdMC), and distance to multicalibration (dMC). We argue that there are two essential properties of any multicalibration error metric: 1) the metric should capture how much $f$ would need to be modified in order to be perfectly multicalibrated; and 2) the metric should be auditable in an information theoretic sense. We show that wdMC and dMC each fail to satisfy one of these two properties, and that similar barriers arise when considering the auditability of general distance to multigroup fairness notions. We then propose two (equivalent) multicalibration metrics which do satisfy these requirements: 1) a continuized variant of dMC; and 2) a distance to intersection multicalibration, which leans on intersectional fairness desiderata. Along the way, we shed light on the loss-landscape of distance to multicalibration and the geometry of the set of perfectly multicalibrated predictors. Our findings may have implications for the development of stronger multicalibration algorithms as well as multigroup auditing more generally.
BibTeX
@inproceedings{derhake2026auditability,
  author = {Nathan Derhake and Siddartha Devic and Dutch Hansen and Kuan Liu and Vatsal Sharan},
  title = {{Auditability and the Landscape of Distance to Multicalibration}},
  booktitle = {ITCS},
  year = {2026},
  doi = {10.4230/lipics.itcs.2026.48},
}

Loading related content...

Figure