New analysis of isotonic regression delivers first distribution-free calibration guarantee

A team of statisticians—Raphael Rossellini, Rina Foygel Barber, Zhimei Ren, and Jake Soloff—has published a new theoretical analysis of binary isotonic regression, the go-to method for fitting monotone functions and calibrating probabilistic classifiers. Their paper, posted on arXiv (2607.27301), focuses on a fundamental question: how many degrees of freedom does isotonic regression use on binary data? They identify the worst-case binary sequences that maximize the number of distinct fitted values, then use analytic number theory to prove a sharp bound on degrees of freedom, with a leading term of 3/(4π²)^{1/3} n^{2/3}. This improves on previously known bounds and provides a complete finite-sample characterization.

Building on that result, the authors tackle calibration—a key requirement for trustworthy probabilistic predictions. Isotonic regression is widely used as a post-processing step to make model outputs well-calibrated, but its theoretical guarantees have been limited. The team derives the first nontrivial distribution-free bound on Expected Calibration Error (ECE) for isotonic regression. The guarantee is fully model-free and distribution-free, requiring only that labels be binary (Y ∈ {0,1}). That means practitioners can now bound calibration error without assuming a specific data-generating distribution—a major step for robust ML pipelines. The work bridges analytic number theory and machine learning, offering both deeper theory and practical reassurance for anyone using isotonic regression to calibrate probabilities.