Computational and Statistical Hardness of Calibration Distance
This paper investigates computing and estimating the 'distance from calibration,' a measure of how poorly a probabilistic predictor is calibrated. It finds efficient algorithms for specific data types but proves the problem is NP-hard in general, meaning finding exact answers or tight bounds requires exponential time unless simplifying assumptions are made.