Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.23000 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912609756774400 |
|---|---|
| author | Bairaktari, Konstantina Nguyen, Huy L. |
| author_facet | Bairaktari, Konstantina Nguyen, Huy L. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_23000 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sample-efficient Multiclass Calibration under $\ell_{p}$ Error Bairaktari, Konstantina Nguyen, Huy L. Machine Learning Data Structures and Algorithms 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. |
| title | Sample-efficient Multiclass Calibration under $\ell_{p}$ Error |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.23000 |