On Computationally Efficient Multi-Class Calibration
<|reference_start|>On Computationally Efficient Multi-Class Calibration: 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 \subseteq [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.<|reference_end|>
@article{gopalan2024on,
    title={On Computationally Efficient Multi-Class Calibration},
    author={Parikshit Gopalan, Lunjia Hu, Guy N. Rothblum},
    journal={arXiv preprint arXiv:2402.07821},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.07821},
    primaryClass={cs.LG cs.CC cs.DS math.ST stat.ML stat.TH}
}