An Elementary Predictor Obtaining $2\sqrt{T}+1$ Distance to Calibration

Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, Mirah Shi
2/18/2024
cs.LGcs.DSstat.ML

No confident code implementation found for this paper.

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 [2024] gave a non-constructive argument establishing the existence of an online predictor that can obtain $O(\sqrt{T})$ distance to calibration in the adversarial setting, which is known to be impossible for ECE. They leave as an open problem finding an explicit, efficient algorithm. We resolve this problem and give an extremely simple, efficient, deterministic algorithm that obtains distance to calibration error at most $2\sqrt{T}+1$.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Computational and Statistical Hardness of Calibration Distance

87% match2026

Testing Calibration in Nearly-Linear Time

81% match1 repo22024

Calibration Error for Decision Making

80% match2024

A Perfectly Truthful Calibration Measure

78% match2025

A Confidence Interval for the $\ell_2$ Expected Calibration Error

76% match1 repo12024

Calibration through the Lens of Indistinguishability

76% match2025

Cite this paper

@article{arunachaleswaran2024elementary,
  title  = {An Elementary Predictor Obtaining $2\sqrt{T}+1$ Distance to Calibration},
  author = {Eshwar Ram Arunachaleswaran and Natalie Collina and Aaron Roth and Mirah Shi},
  year   = {2024},
  eprint = {2402.11410},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2402.11410v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2402.11410.svg)](https://codeofpaper.com/paper/2402.11410)

Discussion