CRPS-Optimal Binning for Conformal Regression
Paolo Toccaceli · 2026
Read CRPS-Optimal Binning for Conformal Regression by Paolo Toccaceli (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22000.txt.
Introduction
Toccaceli builds a distribution estimator for regression by sorting data on covariates and cutting it into bins. Each bin's empirical distribution is the forecast for its members. Bin edges minimize a leave-one-out CRPS score with a closed-form cost. Dynamic programming finds the best split for any bin count. Cross-validation picks it, since the in-sample score cheats. From the bins, Toccaceli forms a Venn band and a conformal set with a finite-sample coverage guarantee. Benchmarks give narrower intervals at near-nominal coverage.
Catalog record
| CREATOR | Paolo Toccaceli |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67957 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.22000
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
CRPS-Optimal Binning for Conformal Regression Paolo Toccaceli Abstract We propose a method for non-parametric conditional distribution estimation based on partitioning covariate-sorted observations into contiguous bins and using the within-bin empirical CDF as the predictive distribution. Bin boundaries are chosen to minimise the total leave-one-out Continuous Ranked Probability Score (LOO-CRPS), which admits a closed-form cost function with O ( n 2 log n ) O(n^{2}\log n) precomputation and O ( n 2 ) O(n^{2}) storage; the globally optimal K K -partition is recovered by a dynamic programme in O ( n 2 K ) O(n^{2}K) time. Minimisation of Within-sample LOO-CRPS turns out to be inappropriate for selecting K K as it results in in-sample optimism. So we instead select K K by evaluating test CRPS on an alternating held-out split, which yields a U-shaped criterion with a well-defined minimum. Having selected K ∗ K^{*} and fitted the full-data partition, we form two complementary predictive objects: the Venn prediction band and a conformal prediction set based on CRPS as the nonconformity score, which carries a finite-sample marginal coverage guarantee at any prescribed level ε \varepsilon . On real benchmarks against split-conformal competitors (Gaussian split conformal, CQR, and CQR-QRF), the method produces substantially narrower prediction intervals while maintaining near-nominal coverage. Keywords: conformal prediction, conformal regression, distribution-free, non-parametric regression, optimal binning 1 Introduction A fundamental problem in supervised learning is to estimate not just the conditional mean \mathbb{E}[Y\mid X=x] but the full conditional distribution P(Y\mid X=x) . A distributional forecast communicates uncertainty in a way that a point prediction cannot: it is necessary for decision-making under risk, hypothesis testing at a test point, and the construction of valid prediction sets. The simplest non-parametric approach is to collect nearby training observations and use their empirical CDF as a stand-in for P(Y\mid X=x) . Nearest-neighbour and kernel density methods implement this idea but require tuning a bandwidth that trades off local fidelity against statistical efficiency. When the covariate is one-dimensional and the data are sorted by x , a natural alternative is to partition the sorted sequence into contiguous bins and predict with the within-bin ECDF. Binning is interpretable, fast, and directly connected to the Venn predictor framework of Vovk, Gammerman, and Shafer [ 12 ] : the within-bin ECDF is the reference class predictor for a test point that falls in a given bin. The central question is how to place bin boundaries optimally. Informal choices, such as equal-width or equal-count bins, are oblivious to the heteroscedasticity of the response and to the local density of the covariate. We argue that bin boundaries should minimise a proper scoring rule evaluated on the training data, so that the binning criterion and the predictive goal are aligned. Among proper scoring rules, the CRPS is particularly well suited to this purpose: it targets the full distribution (not a single functional), it admits a closed-form leave-one-out formula that depends only on pairwise absolute differences, and it is the same score used in the conformal prediction step, ensuring coherence between bin selection and prediction-set construction. Section 11.2 discusses these properties in detail. Contributions. 1. Closed-form LOO-CRPS cost. We derive the total leave-one-out CRPS of a bin of size m as \mathrm{cost}(S)=mW/(m-1)^{2} , where W=\sum_{\ell<r}|y_{\ell}-y_{r}| is the pairwise dispersion (Proposition 1 ). This scalar is updated in O(\log n) per extension step, giving O(n^{2}\log n) precomputation and O(n^{2}) storage for all subintervals. 2. Exact optimal partitioning via dynamic programming. The additive cost structure satisfies the optimal substructure property, so a DP recovers the globally optimal K -partition in O(n^{2}K) time (Section 5 ). Unlike greedy binary segmentation [ 19 ] , which fixes cut points sequentially and can miss the global optimum, the DP evaluates all continuations simultaneously and is exact — and vastly more efficient than exhaustive search, which would enumerate all \binom{n-1}{K-1} candidate K -partitions. 3. Cross-validated K selection. We identify in-sample optimism as the reason within-sample LOO-CRPS fails as a model selection criterion and propose an alternating-split test-CRPS criterion that yields a U-shaped curve and a sensible K^{*} (Section 7 ). 4. Conformal prediction sets and Venn connection. We construct CRPS-based conformal prediction sets with finite-sample marginal coverage guarantees and show they are always connected intervals by convexity of the score. We also formalise the regression analog of the Venn Predictor, namely a constant-width family of augmented ECDFs, as the theoretical underpinning that motivates the LOO scoring construction (Section 8 ). Organisation. Section 2 surveys related work. Section 3 fixes notation and defines the binning problem. Section 4 derives the closed-form LOO-CRPS cost. Section 5 presents the DP recurrence. Section 6 describes precomputation and complexity. Section 7 analyses K selection, diagnosing the failure of within-sample LOO-CRPS, and proposes the cross-validated criterion. Section 8 covers the Venn band, conformal prediction, and the approximate-exchangeability trade-off that governs the choice of K . Section 9 gives the synthetic numerical illustration. Section 10 presents real-data experiments on Old Faithful and the motorcycle benchmark. Section 11 discusses DP optimality and the role of CRPS. Section 12 concludes and identifies open problems. 2 Related Work Conformal prediction for regression. Conformal prediction [ 12 ] wraps any nonconformity score in a distribution-free prediction set with finite-sample marginal coverage; Lei et al. [ 24 ] provide a comprehensive treatment for the regression setting, covering a range of nonconformity scores and establishing finite-sample guarantees. The inductive (split-conformal) variant [ 13 ] divides training data into a fitting half and a calibration half; the quantile of calibration nonconformity scores determines the prediction set for a new point. Conformalized Quantile Regression (CQR) [ 14 ] improves efficiency in heteroscedastic settings by using conditional quantile estimates as the base predictor and measuring residuals relative to the estimated interval. Mondrian conformal prediction [ 12 ] stratifies the calibration set into categories (taxonomies) so that coverage holds conditionally within each stratum; our method is a Mondrian predictor with data-adaptive bins as strata and CRPS as the nonconformity score. Sesia and Romano [ 25 ] propose conformal prediction based on conditional histograms, stratifying calibration scores by the value of a one-dimensional predictor (such as an estimated quantile); our method instead partitions on the covariate x directly and selects bin boundaries to minimise LOO-CRPS rather than conditioning on a downstream predictor score. Venn predictors. Venn predictors [ 12 ] output a set of probability distributions, one for each candidate label of the test point. Vovk and Petej [ 15 ] develop Venn-ABERS predictors for binary classification: isotonic regression on an underlying scoring function implicitly identifies an optimal partition of the score range into reference classes, each with finite-sample calibration guarantees. Our method mirrors this structure on the covariate axis: the DP selects CRPS-optimal bins, defining reference classes whose within-bin ECDF best describes the local conditional distribution. Our Venn prediction band (Section 8 ) then follows: for each hypothesised response value y^{*} , the within-bin ECDF is augmented with y^{*} , yielding a family of distributions parametrised by the test label. Conditional distribution estimation. Quantile Regression Forests [ 16 ] estimate the full conditional CDF by aggregating leaf-node empirical CDFs from an ensemble. NGBoost [ 17 ] fits parametric conditional distributions via natural-gradient boosting with proper scoring rule objectives.