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

arXiv:2607.27301v1 Announce Type: cross 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}{(4pi^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}.

Related

• Hierarchies of Calibration: Classification meets Regression
• Optimal and Provable Calibration in High-Dimensional Binary Classification: Angular Calibration and Platt Scaling

Source: arXiv cs.LG | 2026-07-31