A Unifying Theory of Distance to Calibration
8A Google TechTalk, presented by Jarosław Błasiok, 2023-04-04
ABSTRACT: We study the fundamental question of how to define and measure the distance from calibration for probabilistic predictors. While the notion of “perfect calibration” is well-understood, there is no consensus on how to quantify the distance from perfect calibration. Numerous calibration measures have been proposed in the literature, but it is unclear how they compare to each other, and many popular measures such as Expected Calibration Error (ECE) fail to satisfy basic properties like continuity.
We present a rigorous framework for analyzing calibration measures, inspired by the literature on property testing. We propose a ground-truth notion of distance from calibration: the $\ell_1$ distance to the nearest perfectly calibrated predictor. We define a “consistent calibration measure” as one that is a polynomial factor approximation to the this distance. Applying our framework, we identify three calibration measures that are “consistent” and can be estimated efficiently: smooth calibration, interval calibration, and Laplace kernel calibration. The former two give quadratic approximations to the ground truth distance, which we show is information-theoretically optimal. Our work thus establishes fundamental lower and upper bounds on measuring distance to calibration, and also provides theoretical justification for preferring certain metrics (like Laplace kernel calibration) in practice.
Based on joint work with Parikshit Gopalan, Lunjia Hu and Preetum Nakkiran.
Full text available at https://arxiv.org/abs/2211.16886
Bio: Jarosław Błasiok is a Junior Fellow at Simons Society of Fellows, conducting postdoctoral research at the Theory of Computation group at Columbia University, under mentorship of Professor Alex Andoni. He finished his Ph.D. at the John A. Paulson School of Engineering and Applied Sciences at Harvard University, advised by Professor Jelani Nelson. He received his B.S. and M.Sc. in Computer Science from the University of Warsaw.
He has a broad research interest in Theoretical Computer Science and has worked in design and analysis of streaming algorithms, the theory of error-correcting codes, algorithms related to machine learning, differential privacy and compressed sensing. In his dissertation, he described his research in streaming algorithms and error correction, featuring applications of high dimensional probability in these two areas.
A Google Talk Series on Algorithms, Theory, and Optimization