Sample-efficient Multiclass Calibration under $\ell_{p}$ Error
This work addresses the problem of efficient calibration for multiclass predictors in machine learning, offering improvements in sample complexity over previous methods.
The paper tackles the challenge of multiclass calibration with exponential sample complexity by proposing a new calibration error definition that interpolates between two established notions, enabling polynomial sample complexity for calibrating any given predictor across most of the interpolation range and achieving nearly optimal error dependence at one endpoint.
Calibrating a multiclass predictor, that outputs a distribution over labels, is particularly challenging due to the exponential number of possible prediction values. In this work, we propose a new definition of calibration error that interpolates between two established calibration error notions, one with known exponential sample complexity and one with polynomial sample complexity for calibrating a given predictor. Our algorithm can calibrate any given predictor for the entire range of interpolation, except for one endpoint, using only a polynomial number of samples. At the other endpoint, we achieve nearly optimal dependence on the error parameter, improving upon previous work. A key technical contribution is a novel application of adaptive data analysis with high adaptivity but only logarithmic overhead in the sample complexity.