2024/02/12 by Parikshit Gopalan, Lunjia Hu, Gopalan, Parikshit +3 · 7 citations
Computer Science · Engineering · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Fault Detection and Control Systems #Image Processing Techniques and Applications #Image and Signal Denoising Methods #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2402.07821
openalex publication_date 2024/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a multi-class labelling problem, where the labels can take values in [k], and a predictor predicts a distribution over the labels. In this work, we study the following foundational question: Are there notions of multi-class calibration that give strong guarantees of meaningful predictions and can be achieved in time and sample complexities polynomial in k? Prior notions of calibration exhibit a tradeoff between computational efficiency and expressivity: they either suffer from having sample complexity exponential in k, or needing to solve computationally intractable problems, or give rather weak guarantees. Our main contribution is a notion of calibration that achieves all these desiderata: we formulate a robust notion of projected smooth calibration for multi-class predictions, and give new recalibration algorithms for efficiently calibrating predictors under this definition with complexity polynomial in k. Projected smooth calibration gives strong guarantees for all downstream decision makers who want to use the predictor for binary classification problems of the form: does the label belong to a subset T ⊆ [k]: e.g. is this an image of an animal? It ensures that the probabilities predicted by summing the probabilities assigned to labels in T are close to some perfectly calibrated binary predictor for that task. We also show that natural strengthenings of our definition are computationally hard to achieve: they run into information theoretic barriers or computational intractability. Underlying both our upper and lower bounds is a tight connection that we prove between multi-class calibration and the well-studied problem of agnostic learning in the (standard) binary prediction setting.