Testing Calibration in Subquadratic Time
Lunjia Hu Kevin Tian Chutong Yang
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 $\mathcal{D}$ on
(predictions, binary outcomes), our goal is to distinguish between the case
where $\mathcal{D}$ is perfectly calibrated, and the case where $\mathcal{D}$
is $\varepsilon$-far from calibration.
  We design an algorithm based on approximate linear programming, which solves
calibration testing information-theoretically optimally (up to constant
factors) in time $O(n^{1.5} \log(n))$. This improves upon state-of-the-art
black-box linear program solvers requiring $\Omega(n^\omega)$ time, where
$\omega > 2$ is the exponent of matrix multiplication. We also develop
algorithms for tolerant variants of our testing problem, and give sample
complexity lower bounds for alternative calibration distances to the one
considered in this work. Finally, we present preliminary experiments showing
that the testing problem we define faithfully captures standard notions of
calibration, and that our algorithms scale to accommodate moderate sample
sizes.