An analysis of binary isotonic regression: degrees of freedom and implications for calibration

Raphael Rossellini; Rina Foygel Barber; Zhimei Ren; Jake A. Soloff

stat.MLJul 29, 2026

An analysis of binary isotonic regression: degrees of freedom and implications for calibration

Authors: Raphael Rossellini, Rina Foygel Barber, Zhimei Ren, Jake A. Soloff

Organizations: Department of Statistics, University of Chicago · Department of Statistics and Data Science, University of Pennsylvania · Department of Statistics, University of Michigan

Abstract

Isotonic regression is a canonical tool for estimating monotone functions and calibrating probabilistic predictors. We provide a fully sharp finite-sample characterization of its worst-case degrees of freedom on binary samples. Specifically, we identify the binary sequences that maximize the number of distinct fitted values produced by isotonic regression. We develop a sharp bound on the degrees of freedom with a leading term of $\frac{3}{(4π^2)^{1/3}} n^{2/3}$ using analytic number theory, improving on previous bounds. We then apply this result to calibration. Calibration is a central requirement for probabilistic prediction, and isotonic regression is a widely used post-processing method for improving calibration. Building on deterministic degrees-of-freedom bounds, we derive, to our knowledge, the first nontrivial distribution-free guarantee on the Expected Calibration Error (ECE) of isotonic regression. This ECE bound is fully model-free and distribution-free, only assuming $Y \in \{0,1\}$ .

Explore similar work

Isotonic Conformal Prediction
Jul 18, 2026Daniel Bensimon, Sean Xiang Yu, Eric D. Kolaczyk +1Conformal Prediction Reliable Uncertainty Quantification
Efficient Sequential Calibration with $O(T^{2/3-ε})$ Error Bound
Jul 14, 2026Zihan ZhangMulticalibration and Calibration High-Fidelity Surrogates
A Ranking Approach for Measuring Calibration
Sep 14, 2026Anirban Chatterjee, Rina Foygel BarberMulticalibration and Calibration Probability

Jul 18, 2026 · stat.MLJ/K move · Enter open · S save

Isotonic Conformal Prediction

Daniel Bensimon, Sean Xiang Yu, Eric D. Kolaczyk, Archer Y. Yang

Department of Mathematics and Statistics, McGill University; Mila · Eli Lilly and Company

A point prediction that is well calibrated on average can still be systematically biased conditional on its own value, undermining its use in downstream decision-making. We consider two objectives for reliable uncertainty quantification: self-calibration, requiring a point prediction to be unbiased conditional on its own value, and prediction-conditional validity, requiring a prediction interval to attain nominal coverage conditional on the prediction. Self-Calibrating Conformal Prediction (SC-CP) attains both objectives exactly in finite samples, but requires refitting its calibrator for every candidate outcome, which is computationally prohibitive for continuous outcomes. We propose Isotonic Conformal Prediction (ICP), a framework that decouples calibration from prediction-set construction by fitting a single isotonic recalibration map and constructing prediction intervals within strata of similar recalibrated predictions. Within this framework we develop two procedures. Split Isotonic Conformal Prediction (SICP) attains prediction-conditional validity in finite samples and self-calibration asymptotically, at the computational cost of split conformal prediction. Transductive Isotonic Conformal Prediction (TICP) attains both objectives exactly in finite samples through a per-test-point inner loop that avoids refitting the isotonic calibrator. On synthetic heteroscedastic regression problems and a real-world healthcare-utilization dataset, both procedures match the coverage of SC-CP at substantially lower computational cost.

Conformal Prediction Reliable Uncertainty Quantification Heteroskedasticity Multicalibration and Calibration

Open paper Ask about it PDF

Abstract

Explore similar work

Isotonic Conformal Prediction

Efficient Sequential Calibration with O(T2/3−ε)O(T^{2/3-ε})O(T2/3−ε) Error Bound

A Ranking Approach for Measuring Calibration

Efficient Sequential Calibration with $O(T^{2/3-ε})$ Error Bound