# Testing Calibration in Nearly-Linear Time

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 49 references that are in the map.
- First posted on arXiv 20 Feb 2024.

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

- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Measuring Calibration in Deep Learning](https://mlsanity.com/paper/1904.01685/) (2019)
- [Revisiting the Calibration of Modern Neural Networks](https://mlsanity.com/paper/2106.07998/) (2021)
- [Verified Uncertainty Calibration](https://mlsanity.com/paper/1909.10155/) (2019)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Uncertainty Quantification and Deep Ensembles](https://mlsanity.com/paper/2007.08792/) (2020)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Smooth ECE: Principled Reliability Diagrams via Kernel Smoothing](https://mlsanity.com/paper/2309.12236/) (2023)
- [A Unifying Theory of Distance from Calibration](https://mlsanity.com/paper/2211.16886/) (2022)
- [When Does Optimizing a Proper Loss Yield Calibration?](https://mlsanity.com/paper/2305.18764/) (2023)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [T-Cal: An optimal test for the calibration of predictive models](https://mlsanity.com/paper/2203.01850/) (2022)
- [Solving Tall Dense Linear Programs in Nearly Linear Time](https://mlsanity.com/paper/2002.02304/) (2020)
- [Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration](https://mlsanity.com/paper/2011.06572/) (2020)
- [Solving Sparse Linear Systems Faster than Matrix Multiplication](https://mlsanity.com/paper/2007.10254/) (2020)
- [Matrix anti-concentration inequalities with applications](https://mlsanity.com/paper/2111.05553/) (2021)
- [Nearly Maximum Flows in Nearly Linear Time](https://mlsanity.com/paper/1304.2077/) (2013)
- [Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time](https://mlsanity.com/paper/2205.01562/) (2022)
- [Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations](https://mlsanity.com/paper/2303.15627/) (2023)

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

- [Omnipredicting Single-Index Models with Multi-Index Models](https://mlsanity.com/paper/2411.13083/) (2024)
- [A Perfectly Truthful Calibration Measure](https://mlsanity.com/paper/2508.13100/) (2025)
- [Calibration through the Lens of Indistinguishability](https://mlsanity.com/paper/2509.02279/) (2025)
- [Efficient Calibration for Decision Making](https://mlsanity.com/paper/2511.13699/) (2025)
- [Computational and Statistical Hardness of Calibration Distance](https://mlsanity.com/paper/2603.18391/) (2026)
- [The Verification Tax: Fundamental Limits of AI Auditing in the Rare-Error Regime](https://mlsanity.com/paper/2604.12951/) (2026)
- [Uniform convergence of the smooth calibration error and its relationship with functional gradient](https://mlsanity.com/paper/2505.19396/) (2025)
- [Auditability and the Landscape of Distance to Multicalibration](https://mlsanity.com/paper/2509.16930/) (2025)
- [L2-Regularized Empirical Risk Minimization Guarantees Small Smooth Calibration Error](https://mlsanity.com/paper/2510.13450/) (2025)
- [Sharp Integrality Gaps in Calibration Distance](https://mlsanity.com/paper/2610.05679/) (2026)

## Abstract (arXiv)

In the recent literature on machine learning and decision making, calibration has emerged as a desirable and widely-studied statistical property of the outputs of binary prediction models. However, the algorithmic aspects of measuring model calibration have remained relatively less well-explored. Motivated by [BGHN23], which proposed a rigorous framework for measuring distances to calibration, we initiate the algorithmic study of calibration through the lens of property testing. We define the problem of calibration testing from samples where given n draws from a distribution D on (predictions, binary outcomes), our goal is to distinguish between the case where D is perfectly calibrated, and the case where D is varepsilon-far from calibration. We make the simple observation that the empirical smooth calibration linear program can be reformulated as an instance of minimum-cost flow on a highly-structured graph, and design an exact dynamic programming-based solver for it which runs in time O(nlog2(n)), and solves the calibration testing problem information-theoretically optimally in the same time. This improves upon state-of-the-art black-box linear program solvers requiring Omega(nω) time, where ω > 2 is the exponent of matrix multiplication. We also develop algorithms for tolerant variants of our testing problem improving upon black-box linear program solvers, and give sample complexity lower bounds for alternative calibration measures to the one considered in this work. Finally, we present experiments showing the testing problem we define faithfully captures standard notions of calibration, and that our algorithms scale efficiently to accommodate large sample sizes.