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

• URL: http://arxiv.org/abs/2607.27301v1
• Date: Wed, 29 Jul 2026 16:53:12 GMT
• Title: An analysis of binary isotonic regression: degrees of freedom and implications for calibration
• Abstract summary: We identify the binary sequences that maximize the number of distinct fitted values produced by isotonic regression.<n>We develop a sharp bound on the degrees of freedom with a leading term of $frac3(42) 1/3 n2/3$ using analytic number theory.<n>We derive the first non-trivial distribution-free guarantee on the Expected Error (ECE) of isotonic regression.
• Score: 11.823728812515839
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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\}$.

Related papers

• The Minimax Rate of Second-Order Calibration [8.791341107339637]
  We characterize the minimax rate of estimating the second-order calibration error for binary classification.<n>As a corollary, we give the first finite-sample guarantee for second-order Platt scaling.
  arXiv  Detail & Related papers  (2026-05-08T14:41:56Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Information Hidden in Gradients of Regression with Target Noise [2.8911861322232686]
  We show that the gradients alone can reveal the Hessian.<n>We provide non-asymptotic operator-norm guarantees under sub-Gaussian inputs.
  arXiv  Detail & Related papers  (2026-01-26T14:50:16Z)
• $L_2$-Regularized Empirical Risk Minimization Guarantees Small Smooth Calibration Error [10.968987566851263]
  This work provides the first theoretical proof that canonical $L_2$-regularized empirical risk minimization directly controls the smooth calibration error (smCE)<n>We then instantiate this theory for models in reproducing kernel Hilbert spaces, deriving concrete guarantees for kernel ridge and logistic regression.<n>Our experiments confirm these specific guarantees, demonstrating that $L_2$-regularized ERM can provide a well-calibrated model without boosting or post-hoc recalibration.
  arXiv  Detail & Related papers  (2025-10-15T11:49:58Z)
• Test Set Sizing for the Ridge Regression [51.56484100374058]
  We derive the ideal train/test split for the ridge regression to high accuracy in the limit that the number of training rows m becomes large.<n>This is the first time that such a split is calculated mathematically for a machine learning model in the large data limit.
  arXiv  Detail & Related papers  (2025-04-27T13:17:18Z)
• Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise [51.87307904567702]
  Quantile regression is a leading approach for obtaining such intervals via the empirical estimation of quantiles in the distribution of outputs.<n>We propose Relaxed Quantile Regression (RQR), a direct alternative to quantile regression based interval construction that removes this arbitrary constraint.<n>We demonstrate that this added flexibility results in intervals with an improvement in desirable qualities.
  arXiv  Detail & Related papers  (2024-06-05T13:36:38Z)
• Dimension free ridge regression [10.434481202633458]
  We revisit ridge regression on i.i.d. data in terms of the bias and variance of ridge regression in terms of the bias and variance of an equivalent' sequence model.<n>As a new application, we obtain a completely explicit and sharp characterization of ridge regression for Hilbert covariates with regularly varying spectrum.
  arXiv  Detail & Related papers  (2022-10-16T16:01:05Z)
• A Consistent and Differentiable Lp Canonical Calibration Error Estimator [21.67616079217758]
  Deep neural networks are poorly calibrated and tend to output overconfident predictions. We propose a low-bias, trainable calibration error estimator based on Dirichlet kernel density estimates. Our method has a natural choice of kernel, and can be used to generate consistent estimates of other quantities.
  arXiv  Detail & Related papers  (2022-10-13T15:11:11Z)
• T-Cal: An optimal test for the calibration of predictive models [49.11538724574202]
  We consider detecting mis-calibration of predictive models using a finite validation dataset as a hypothesis testing problem. detecting mis-calibration is only possible when the conditional probabilities of the classes are sufficiently smooth functions of the predictions. We propose T-Cal, a minimax test for calibration based on a de-biased plug-in estimator of the $ell$-Expected Error (ECE)
  arXiv  Detail & Related papers  (2022-03-03T16:58:54Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  We derive the regret upper bounds on the classes of Sobolev spaces $W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$. The upper bounds are supported by the minimax regret analysis, which reveals that in the cases $beta> fracd2$ or $p=infty$ these rates are (essentially) optimal.
  arXiv  Detail & Related papers  (2021-02-06T15:05:14Z)
• Individual Calibration with Randomized Forecasting [116.2086707626651]
  We show that calibration for individual samples is possible in the regression setup if the predictions are randomized. We design a training objective to enforce individual calibration and use it to train randomized regression functions.
  arXiv  Detail & Related papers  (2020-06-18T05:53:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.