An Elementary Predictor Obtaining 2\sqrt{T} Distance to Calibration
Abstract
Blasiok et al (2023) proposed distance to calibration as a natural measure of calibration error that, unlike expected calibration error (ECE), is continuous. Recently, Qiao and Zheng (COLT 2024) gave a non-constructive argument establishing the existence of a randomized online predictor that can obtain $O(\sqrt{T})$ distance to calibration in expectation in the adversarial setting, which is known to be impossible for ECE. They leave as an open problem finding an explicit, efficient, deterministic algorithm. We resolve this problem and give an extremely simple, efficient, deterministic algorithm that obtains distance to calibration error at most $2\sqrt{T}$.
Cite
Text
Arunachaleswaran et al. "An Elementary Predictor Obtaining 2\sqrt{T} Distance to Calibration." NeurIPS 2024 Workshops: OPT, 2024.Markdown
[Arunachaleswaran et al. "An Elementary Predictor Obtaining 2\sqrt{T} Distance to Calibration." NeurIPS 2024 Workshops: OPT, 2024.](https://mlanthology.org/neuripsw/2024/arunachaleswaran2024neuripsw-elementary/)BibTeX
@inproceedings{arunachaleswaran2024neuripsw-elementary,
title = {{An Elementary Predictor Obtaining 2\sqrt{T} Distance to Calibration}},
author = {Arunachaleswaran, Eshwar Ram and Collina, Natalie and Roth, Aaron and Shi, Mirah},
booktitle = {NeurIPS 2024 Workshops: OPT},
year = {2024},
url = {https://mlanthology.org/neuripsw/2024/arunachaleswaran2024neuripsw-elementary/}
}