Brenier Isotonic Regression

Han Bao; Amirreza Eshraghi; Yutong Wang

stat.MLMar 11, 2026

Brenier Isotonic Regression

Authors: Han Bao, Amirreza Eshraghi, Yutong Wang

Organizations: The Institute of Statistical Mathematics · Illinois Institute of Technology

Abstract

Isotonic regression (IR) is shape-constrained regression to maintain a univariate fitting curve non-decreasing, which has numerous applications including single-index models and probability calibration. When it comes to multi-output regression, the classical IR is no longer applicable because the monotonicity is not readily extendable. We consider a novel multi-output regression problem where a regression function is cyclically monotone. Roughly speaking, a cyclically monotone function is the gradient of some convex potential. Whereas enforcing cyclic monotonicity is apparently challenging, we leverage the fact that Kantorovich's optimal transport (OT) always yields a cyclically monotone coupling as an optimal solution. This perspective naturally allows us to interpret a regression function and the convex potential as a link function in generalized linear models and Brenier's potential in OT, respectively, and hence we call this IR extension Brenier isotonic regression. We demonstrate experiments with probability calibration and generalized linear models. In particular, IR outperforms many famous baselines in probability calibration robustly.

Figures & tables

Figure 1: Comparison between IR and BIR . Observations are generated with $y=1/(1+\exp(-z))+\text{noise}$ . The real line of BIR is computed via the Laguerre map over $\mathbb{R}$ .

Panel of Table 1 — Table 1: Recalibration results for MLP (upper table) and linear SVM (lower table) . Each number indicates the $L_{1}$ calibration error (lower is better) with averaging $10$ trials, and bold-faced if the recalibrator achieves the best or second best performance or statistically indistinguishable from them by the Mann–Whitney $U$ test (significance level: $5$ %).

Panel of Figure 3 — Figure 3: From left to right, BrenierIR ( $k=50$ ), Binning , and Matrix Scaling . We show their estimated calibration maps as vector fields (each left) and contour plots of their first coordinate (each right).

Panel of Figure 4 — Figure 4: Each base model is recalibrated by BIR with different bin size $k$ (shown with the standard deviation).

Panel of Table 2 — Table 2: Multiclass classification results. Each number indicates the accuracy and $L_{1}$ calibration error with averaging $10$ trials, and bold-faced if a method achieves the best performance or statistically indistinguishable from the best method by the Mann–Whitney $U$ test (significance level $5$ %).

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Sample size	# of features	# of classes
balance-scale	625	4	3
car	1728	6	4
cleveland	297	13	5
dermatology	358	34	6
glass	214	9	6
segment	2310	19	7

Appendix

Table 3: Dataset details.

Panel of Figure 5 — Figure 5: Calibration maps of nonparametric recalibrators. The base model is MLP and balance-scale dataset is used. In each row (corresponding to one recalibrator), we show the calibration map (vector field), the first/second/third coordinates of the calibration map, respectively, from left to right.

Panel of Figure 6 — Figure 6: Calibration maps of parametric recalibrators. The base model is MLP and balance-scale dataset is used. In each row (corresponding to one recalibrator), we show the calibration map (vector field), the first/second/third coordinates of the calibration map, respectively, from left to right.

Panel of Figure 7 — Figure 7: Calibration maps of nonparametric recalibrators. The base model is naive Bayes and balance-scale dataset is used. In each row (corresponding to one recalibrator), we show the calibration map (vector field), the first/second/third coordinates of the calibration map, respectively, from left to right.

Panel of Figure 8 — Figure 8: Calibration maps of parametric recalibrators. The base model is naive Bayes and balance-scale dataset is used. In each row (corresponding to one recalibrator), we show the calibration map (vector field), the first/second/third coordinates of the calibration map, respectively, from left to right.

Dataset	# of classes	Sample size	BrenierIR (Ours)			IRP
Dataset	# of classes	Sample size	$k=15$	$k=30$	$k=50$	IRP
balance-scale	3	625	3.60	13.69	41.19	0.29
car	4	1728	16.84	50.91	221.91	3.20
cleveland	5	297	4.68	16.52	35.05	4.26
dermatology	6	358	7.17	25.82	57.81	48.52
glass	6	214	4.51	18.26	55.76	7.00

Appendix

Table 4: Averaged running times (in seconds) over

10

trials.

Panel of Table 5 — Table 5: Recalibration results for MLP (upper table) and linear SVM (lower table) . Each number indicates accuracy (higher is better) with averaging $10$ trials, and bold-faced if the recalibrator achieves the best or second best performance or statistically indistinguishable from them by the Mann–Whitney $U$ test (significance level: $5$ %).

Panel of Table 6 — Table 6: Recalibration results for MLP (upper table) and linear SVM (lower table) . Each number indicates the classwise calibration error (lower is better) with averaging $10$ trials, and bold-faced if the recalibrator achieves the best or second best performance or statistically indistinguishable from them by the Mann–Whitney $U$ test (significance level: $5$ %).

Panel of Table 7 — Table 7: Recalibration results for MLP (upper table) and linear SVM (lower table) . Each number indicates the confidence calibration error (lower is better) with averaging $10$ trials, and bold-faced if the recalibrator achieves the best or second best performance or statistically indistinguishable from them by the Mann–Whitney $U$ test (significance level: $5$ %).

Isotonic Regression

Isotonic regression fits nonparametric functions constrained to preserve an ordering, supporting calibration, ranking, and monotone prediction.

See all 12 papers

An analysis of binary isotonic regression: degrees of freedom and implications for calibration
Jul 29, 2026Raphael Rossellini, Rina Foygel Barber, Zhimei Ren +1Probability Calibration Model Calibration
Department of Statistics, University of Chicago · Department of Statistics and Data Science, University of Pennsylvania · Department of Statistics, University of Michigan
CAIRO: Decoupling Order from Scale in Regression
Feb 16, 2026Harri Vanhems, Yue Zhao, Peng Shi +1Robust Regression Tabular Regression
McGill University and Mila · University of York · University of Wisconsin
Isotonic Conformal Prediction
Jul 18, 2026Daniel Bensimon, Sean Xiang Yu, Eric D. Kolaczyk +1Conformal Prediction Uncertainty Calibration
Department of Mathematics and Statistics, McGill University; Mila · Eli Lilly and Company

Jul 29, 2026J/K move · Enter open · S save

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

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

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

Probability Calibration Model Calibration Statistical Learning Theory Isotonic Regression

Open paper AskPDF arXiv

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\}

Abstract

Isotonic Regression

Explore similar work

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

CAIRO: Decoupling Order from Scale in Regression

Isotonic Conformal Prediction