Reproduce “Distribution-free binary classification: prediction sets, confidence intervals and calibration” on OpenResearch

About this paper

Chirag Gupta, Aleksandr Podkopaev, Aaditya Ramdas

A theoretical framework for distribution-free uncertainty quantification in binary classification clarifies fundamental limits and possibilities. Researchers from Carnegie Mellon University show that parametric post-hoc calibration methods cannot achieve distribution-free asymptotic guarantees, while non-parametric histogram binning offers provably robust approximate and asymptotic calibration, even in streaming data and covariate shift settings, with uniform-mass binning achieving (ε, α)-calibration where ε = O(√(B log(1/α)/n)).

Key insights

• There is a fundamental impossibility for "informative" distribution-free confidence intervals, which extends to preventing common parametric post-hoc calibration methods from achieving distribution-free asymptotic calibration.
• Non-parametric histogram binning, specifically uniform-mass binning, provides a provably robust approach to achieve distribution-free approximate and asymptotic calibration for binary classification.
• A unified theoretical framework, termed the "tripod" of theorems, rigorously connects calibration, confidence intervals, and prediction sets, clarifying their interdependencies and limits.

Summary by alphaXiv.