Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction
Authors: Lars van der Laan
Ahmed Alaa
Venue: ICML 2025 poster (2025)
Keywords: Calibration
multicalibration
Venn-Abers
conformal prediction
isotonic calibration
distribution-free
epistemic uncertainty
Primary area: general_machine_learning->everything_else
TL;DR: We introduce a unified framework for Venn and Venn-Abers calibration for generic prediction tasks and loss functions, including conformal prediction as a special case.

Abstract: Ensuring model calibration is critical for reliable prediction, yet popular distribution-free methods such as histogram binning and isotonic regression offer only asymptotic guarantees. We introduce a unified framework for Venn and Venn-Abers calibration that extends Vovk's approach beyond binary classification to a broad class of prediction tasks defined by generic loss functions. Our method transforms any perfectly in-sample calibrated predictor into a set-valued predictor that, in finite samples, outputs at least one marginally calibrated point prediction. These set predictions shrink asymptotically and converge to a conditionally calibrated prediction, capturing epistemic uncertainty. We further propose Venn multicalibration, a new approach for achieving finite-sample calibration across subpopulations. For quantile loss, our framework recovers group-conditional and multicalibrated conformal prediction as special cases and yields novel prediction intervals with quantile-conditional coverage.

Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction
Lars van der Laan
Ahmed Alaa 2
Abstract
Prodictions with Venn Abers Set Callrration
Ensuring model calibration is critical for reliable prediction, yet popular distribution-free methods such as histogram binning and isotonic regression offer only asymptotic guarantees. We introduce a unified framework for Venn and Venn-Abers cali- bration that extends Vovk's s approach beyond bi- nary classification to broad class of prediction problems defined by generic loss functions. Our method transforms any perfectly in-sample cali- brated predictor into a set-valued predictor that, in finite samples, outputs at least one marginally calibrated point prediction. These set predictions shrink asymptotically and converge to condition- ally calibrated prediction, capturing epistemic un- certainty. We further propose Venn multicalibra- tion, a new approach for achieving finite-sample calibration across subpopulations. For quantile loss, our framework recovers group-conditional and multicalibrated conformal prediction spe- cial cases and yields novel prediction intervals with quantile-ondditoonal coverage.
na situlliina wedkteer
Outcomn
Feature (X)
Feature (X)
Figure I. Prediction bands capturing epistemic uncertainty in the calibration of point predictions generated by our proposed methods with squared error loss.
such as healthcare, it is crucial to ensure that model-driven decisions are reliable under minimal assumptions (Mandi- nach et al., 2006; Veale et al., 2018; Vazquez and Facelli, 2022; Gohar and Cheng, 2023). Point calibrators, which map single model prediction to single calibrated pre- diction (e.g.. histogram binning and isotonic regression), can provide distribution-Fie calibration conditional on the calibration data. However, their guarantees are asymptotic, achieving zero calibration error only in the limit, and their performance may degrade in finite samples.
To address these limitations, calibrators transform sin- gle model prediction into set of calibrated point predic- tions, explicitly capturing epistemic uncertainty in the cali- bration process. This class of methods includes Venn and Venn-Abers calibration (Vovk et al., 2003; Vovk and Petej, 2012; van der Laan and Alaa, 2024) for classification and regression, and Conformal Prediction (CP) for quantile re- gression and predictive inference (Vovk et al., 2005). Set cal- ibrators provide prediction sets with finite-sample marginal calibration guarantees, while these sets generally converge asymptotically to conditionally calibrated point predictions. For example, Venn calibration produces a set of calibrated probabilities, and conformal prediction generates a set of calibrated quantiles (from which an interval can derived), ensuring that at least one prediction in the set is perfectly calibrated marginally over draws of calibration data.
1. Introduction
Calibration is essential for ensuring that machine learn- ing models produce reliable predictions and enable robust decision-making across diverse applications. Model cali- bration aligns predicted probabilities with observed event frequencies and predicted quantiles with the specified pro- portion of outcomes. Recent work formalizes calibration as the alignment of predictions with elicitable properties defined through minimization of an expected loss, thereby generalizing traditional notions of mean and quantile cali- bration (Noarov and Roth, 2023). In safety-critical sectors
'Equal contribution 'Department of Statistics, University of Washington 'Computational Precision Health, UC Berke- ley and UCSF, Correspondence to: Lars van der Laan <lvd- l uw.edu>..
Our Contributions. Venn and Venn-Abers calibration, generalizing Vovk and Petej (2012) to a broad class prediction tasks and loss functions. This framework extends point calibrators, e.g., histogram binning and isotonic regression, to produce pre-
We introduce unified framework for
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Generalized Venn and Venn-Abers Calibration
diction sets with sinite-sample marginal and large-sample conditional calibration guarantees capture epistemic un- certainty. We further propose Venn multicalibration, en- suring sinite-sample calibration across subpopulations. For quantile regression, we show that Venn calibration corre- sponds to a novel CP procedure with quantile-codditionl coverage, and that multicalibrated conformal prediction (Gibbs et al., 2023) is special case of Venn multicalibra- tion, unifying and extending existing calibration methods. Our approach enables the construction of set calibrators and set multicalibrators from point calibration algorithms for generic loss functions (Noarov and Roth, 2023).
conditions (Whitehouse al., 2024):
(r( (()) [(]] for all x E X, (2)
where df(f(z), y) := dy (17, y) (y= denotes the partial derivative of with respect to its first argument f(x).
In regression, with taken as the squared error loss f is perfectly calibruted if Ep (s() = ʃ(=)] - f(x) for all x E X (Lichtenstein et al., 1977: Gupta et al., 2020), a property also known self-consistency (Flury and Tarpey, 1996). This property addresses systematic over- under- estimation and ensures that f(X) is conditionally unbiased proxy for Y in decision making. In binary classification, calibration ensures that the score f(X) can be interpreted as a probability, making decision rules such as assigning label 1 when f(X) > 0.5 valid on average, since P(Y (X) 0.5) > 0.5 (Silva Filho al., 2023).
2. Preliminaries for loss calibration
2.1. Notation
We consider the problem of predicting an outcome Y e y from context X X, where Z (X, is drawn from an unknown distribution P = PxPrIx, on which we impose no distributional assumptions. Let f X + y denote a predictive model trained to minimize a loss func- tion (f(z). 2) + {(fx)) 2) using a machine learning al- gorithm on training data. For example, {((()), =) could be the squared error loss {y - fx))²² or the (1 a)- quantile loss 1 fy 2 f()))a(y f())))((()))))-aa))(())))))))))) fx=))
For a model f. which depends randomly on the calibration set C,,, we define two types of calibration: marginal and con- ditional (Vovk, 2012). A random model f is conditionally (perfectly) l-calibrated if it is calibrated conditional on the data C,: (f)]@(((x), Z) f(X)) C,] = O almost surely. The model f is marginally E-calibrated if it is calibrated marginally over C,: E[0e(](X), Z) [(X)] = O, where EE is taken over the randomness in both (X, Y) and Cn.
[1=) ()(x(r) y). We assume access to calibration dataset C. = (X,,Y)) of n i.i.d. samples drawn from the same distribution P. independent from the training data. Throughout this work, we treat the model f as fixed, implic- itly conditioning on its training process.
2.3. Post-hoc calibration via point calibrators
Models trained for predictive accuracy often require post- hoc calibration, typically using an independent calibration dataset or, in some cases, the training data (Gupta and Ram- das, 2021). Post-hoc methods treat prediction and calibra- tion as distinct tasks, each optimized for a different yet com- plementary objective. Since perfect calibration is unattain- able in finite samples, the goal of calibration is to obtain a model f with minimal calibration error relative to a chosen metric, such as the conditional l² calibration error Calgz (f), defined as (Whitehouse et 2024):
2.2. Defining calibration for general losses
Machine learning models, such as neural networks and wradient-boosted trees, are powerful predictors but often produce biased point predictions due to model misspecifi- cation, distribution shifts, or limited data (Zadrozny and Elkan, 2001; Niculescu-Mizil and Caruana, 2005; Bella et al., 2010; Guo et al., 2017; Davis et al., 2017). To ensure reliable meciiinn-making, we seek calibrated models (Roth, 2022: Silva Filho et al., 2023). Informally, calibration means that the predictions are optimal conditional on the prediction itself, so they cannot be improved by applying a transfor- mation reduce the loss. Formally, model / is perfectly é-calibrated if (Noarov and Roth, 2023; Whitchouse al., 2024)
I (E F(o)) (px
A point calibrator, following van der Laan et al. (2023) and Gupta et al. (2020), is a post-hoc procedure that learns a transformation 6,. R - IR of a black-bon model f from C, such that: (i) 0, (J())) is well-calibrated with low calibration error, and (ii) 0, (fx)) remains comparably predictive to f(X) in terms of the loss f. Common point calibrators include Platt scaling (Platt et al., 1999; Cox, 1958), histogram binning (Zadrozny and Elkan, 2001), and isotonic calibration (Zadrozny and Elkan, 2002).
Ex((((X)), 2) = inf EP((((((X))) 2),,
where the infimum is taken over all one-dimensional trans- formations 0 IR- + IR of f. Perfect calibration implies that f(x) = argmin.eR Epl[(c, Z) f(X) = f(x)] for all x E X. We assume that the loss E is smooth, such that é-calibration is equivalent to satisfying the first-order
A calibrated predictor can be constructed from C₂ by leamn ing the calibrator 0, via minimizing the empirical risk
2

---

Generalized Venn and Venn-Abers Calibration
EL_ ((O(S(X;)) Ze). For regression, this involves regress- ing outcomes (Yi) predictions {f(X;))²= (Mincer and Zarnowitz, 1969). If On accurately estimates the con- ditional calibration function ming Ep [e(((f(X)), Z) Cn,,, the predictor is well-calibrated by the tower property. This approach is not distribution- free and typically requires cor- rect model specification. Methods like kernel smoothing and Platt scaling impose smoothness or parametric assumptions on the calibration function (Jiang et al., 1).
3. Generalized Venn calibration framework
3.1. Venn calibration for general losses
Suppose we are interested in obtaining an é-calibrated pre- diction f(xx+1) for an unseen outcome Yn+1 from a new context Xn+1, where (Xx+1, Yu+1) is drawn from P and independent of the calibration data C.. Let Ae be any point calibration algorithm that takes model f and calibration data Cn and outputs refined model fü := Af(f, Cn) that is in-sample f-calibrated in the sense of (3). For example, Ae(f. C.)) could be defined as 6, o f. where 6,, is learned using an outcome-agnostic histogram binning method, such as uniform mass binning, or an autcome-adaptin method, such as regression tree or isotonic regression. We assume that the algorithm Ae processes input data exchangeably, ensuring the calibrated predictor is invariant to permutations of the calibration data.
2.4. Distribution-fres calibration via histogram binning
A simple class of distribution free calibration methods is histogram binning, such as uniform mass (quantile) binning (Gupta et al., 2020; Gupta and Ramdas, 2021). Here, the prediction space f(X)) is partitioned into K bins {=x in an outcome-agnostic manner, often by taking quantiles of the predictions {f(x;));= in C,, The binning calibrator On is a step function obtained via histogram regression:
Distribution- free binning- -ased point calibrators, like his- togram binning and isotonic regression, achieve perfect in-sample calibration on calibration data but may exhibit poor conditional calibration in finite samples, attaining population-level calibration only asymptotically. To ad- dress this, Vovk et al. (2003) proposed Venn calibration for binary classification, which transforms point calibrators into set calibrators that ensure finite-sample marginal calibration while retaining conditional calibration asymptotically.
(t)() == min .ER.
((f(X)) E BR(s) M(c, 2.),
where k(() indexes the bin containing L E f(X). For the squared error loss, 0, (t) is the empirical mean of the out- comes (Y: : i E [m], f(x)) E Bu(T}} within the bin BR(z)- The histogram regression property ensures that the resulting calibrated model fú == 8n o f is in-sample l faaliiraated (van der Laan et al., 2024b), meaning that, for each æ E X,
In this section, we extend Venn calibration to general pre- diction tasks defined by loss functions. We demonstrate that Venn calibration can be applied to any point calibra- tor that achieves perfect E-in-sample calibration to ensure finite-sample marginal calibration. Unlike traditional point calibrators, which produce a single calibrated prediction for each context, Venn calibration generates prediction set that is guaranteed to contain a marginally perfectly &- calibrated prediction. This set reflects epistemic uncertainty by covering range of possible calibrated predictions, each of which remains asymptotically conditionally é-calibrated. A prominent example is Venn-Abers calibration, which uses isotonic regression as the underlying point calibrator (Vovk and Petej. 2012: Toceaceli, 2021; van der Laan and Alaa, 2024).
n (x.(() = [1)))((())))) = 0,
(3)
implying that its empirical risk cannot be improved by any transformation of its predictions.
in-sample calibration does not guarantee good out-of- sample calibration or predictive performance. With max- imal partition K- n. perfect iamsae calibration leads to overfitting, resulting in poor out-of-sample performance. Conversely, with a minimal partition K = 1, the model is well-calibrated but poorly predictive, yielding constant predictor min Ei= f(c, Z4). This illustrates a trade- off: too few bins reduce predictive power, while too many increase variance and degrade calibration. Histogram bin- ning asymptotically provides conditionally calibrated pre- dictions, with the conditional e calibration error satisfying Calpa (f+) = Op log(n/K) (Whitehouse et al., 2024). Thus, tuning of K, for example via cross- validatii,,,,,,, is cru- cial to balance calibration and predictiveness.
Our generalized Venn calibration procedure is detailed in Alg. 1. A distinctive aspect of Venn calibration is that it adapts the model f specifically for the given context X unlike point calibrators, which produce a single calibrated model intended to be (asymptotically) valid across all con- texts. For a given context X the algorithm iteratively considers imputed outcomes y E y for Yn+1 and applies the calibrator At to the augmented dataset C. U ((X.+1, W)). This process yields a set of point predictions:
Ju,x. (xx1)) = (f(Xx+t))) : E)E
3

---

Generalized Venn and Venn-Abers Calibration
When the outcome space y/ is continuous, Alg. may be computationally infeasible to execute exactly and can in- stead be approximated by discretizing Y. Nonetheless, the range of the prediction set (2) can often be computed by iterating over the extreme points { (Umin: Umax of y.
calibration, such as uniform mass binning, a regression tree, or isotonic regression. Importantly, this condition does not impose restrictions on how the bins are selected, allowing pre-specified and data-adaptive binning schemes. While the choice of binning calibrator does not affect the marginal perfect calibration guarantee in Theorem 3.1, it influences both the width of the Venn prediction set and the conditional calibration of the point predictions. In general, using a point calibrator that ensures conditionally well-calibrated predictions, such as histogram binning with appropriately tuned bins or isotonic calibration, is recommended.
Algorithm| Venn loss calibration
Require: Calibration data C.. = {(X,, Yi)-=,, model f, context X. loss calibrator As-
1: for each y E Y' do
2: augment dataset: Cha.a) = C. U ((r,y));
3: calibrate model: f! == (I
For example, in the regression setting with squared error loss, Theorem 3.1 ensures that the set fn.X, (Xn+1) con- tains [i+1 using histogram binning with one observation per bin re- sults in fn, (Xn+1)
4: end for
5: set (x.)(x)) ( (x) y E e}}
= [[[,+11 [x+1(Xn+1)) However,
Ensure:
prodiction set (x).
V uninformative set that poorly reflects conditional calibration despite including f (X.+1) = Yn+1. In contrast, using a single bin pro- duces a set containing the marginally perfectly calibrated prediction f (Xn+1) = 1 Σi=1 Y,, where each pre- n+1
To establish the validity of Venn calibration, we impose the following conditions, which ensure that the data are exchangeable- - a common assumption in conformal pre- diction (Vovk et al., 2005), particularly satisfied when the data are i.i.d and that the derivative of the loss has a finite second moment.
diction is close to the sample mean 2 Y,, ensuring conditional calibration but resulting in poor predictiveness.
Suppose that Ac(ff, Cn U (x, outputs a transformed model ((..v) o f. where 0f.-9) is learned using an outcome- agnostic gulcome-adaptive binning calibrator, such as quantile binning or regression tree. The following theo- rem shows that each calibrated model f( o!..v) ) f. used to construct the Venn prediction set, is asymptotically conditionally calibrated, provided the calibration data are i.i.d. and the number of bins in the calibrator 6.5-.) does not grow too quickly.
CI) Exchangeability: {(,, / are exchangeable.
C2) Finite variance: B[(de(f)+ (X Zn+ +11))++++-++ 1) co.
C3) Perfect in- in-sapple calibration: Σ m++1g1 (X,) Jū+1(1) (1))) Z.) = 0 almost surely for each x E X.
The finite-sample validity of the Venn calibration proce- dure can be established through an oracle procedure that assumes knowledge of the unseen outcome Yn-1- In this oracle procedure, a perfectly in-sample f-calibrated pre- diction (X.+1) ;= Aelf, (rf,c++1)(xx++1 is obtained by calibrating / using Ar on the oracle-augmented calibra- By leveraging exchangeability, the in in-sample calibration of the oracle pre- diction li+1 (X=+1) ensures marginal perfect É-calibration, such that E[dE[fi+1 (Xn+1), Zn+1) 1 almost surely. Since the oracle prediction is, by construc- tion, contained in the Venn prediction set fn.x.. (X.+1),
C4) Independence: ((x,, ? are i.i.d.
C5) Boundedness: ess susp (ee(o! (f(x'),
and esssup,, (0!2.0) (x') are bounded by constant M < co.
tion set Ci+11 := C, U {(Xn+1,
)n Y(+1).
C6) Lipschitz derivative: There exists L < oo such that jāl(m, =) - 06(122 =)] S Lmm- - 7/2 for all z, M1, 7/2
0
C7) Finite number of bins: o(5-9) is piecewise constant taking at most k((n) < 0o values.
we conclude the following theorem.
Theorem 3.1 (Marginal calibration of Venn prediction). Under CI-C3, the Venn prediction set fa.Xam (Xn-1) contains the marginally perfectly t-calibrated prediction, (2t2(Xa41) fn ((xxt1nNx11) which satisfies
Theorem 3.2 (Conditional calibration of Venn cal- ibration). Under C4-C7, we have Calga (fl Op( k(n) (og(n/k())))))
For stable point calibrators, as the calibration set size increases, the Venn prediction set narrows and converges to a single perfectly é-calibrated prediction (Vovk and Petej, 2012). In large-sample settings, where standard point cali- brators perform reliably, the Venn prediction set becomes
E [(00(S2+1(Xxtt 7n+1) (i
In order to satisfy C3, Algorithm should be applied with a binning-basee calibrator As that achieves perfect ia-sample
4

---

Generalized Venn and Venn-Abers Calibration
narrow, closely resembling point prediction. In contrast, in small-sample settings, where overfitting can undermine the reliability of point calibrators such as histogram binning and isotonic calibration, the Venn prediction set widens, reflecting increased uncertainty about the true calibrated prediction (Johansson et al., 2023). Consequently, Venn calibration improves the robustness of the point calibration procedure Ae by explicidly representing uncertainty through set of possible calibrated predictions.
quet and Elisseeff, 2000). Consequently, the Venn-Abers prediction set inherits the marginal calibration guarantee of Venn calibration, while each point prediction in the set is conditionally calibrated in large samples.
Let fn,X,.11 (Xx+1) denote the Venn-Abers prediction set obtained by applying Alg. 2 with x = Xn+1- The following theorem follows directly from Theorem 3.1.
Theorem 3.3 (Marginal calibration of Venn-Abers). Un- der CI and C2, the Venn prediction set fn,x,+> (..xx,+xXnn (Xn+1) contains the marginally perfectly l-calibrated prediction. fi (X-+1) := (x11)))))),, which satisfies
3.2. Isotonic and Venn-A calibration
Venn calibration can be applied with any loss calibrator A that provides in-sample calibrated predictions. While his- togram binning requires pre-specifying the number of bins, isotonic calibration (Zadrozny and Elkan, 2002; Niculescu- Mizil and Caruana, 2005) addresses this limitation by adap- tively determining bins through isotonic regression, a non- parametric method for estimating monotone functions (Bar- low and Brunk, 1972). Instead of fixing K in advance, isotonic calibration selects bins by minimizing an empir- ical MSE criterion, ensuring the calibrated predictor is non-decreasing monotone transformation of the original pre- dictor. Isotonic calibration allows the number of bins to grow with sample size, ensuring good calibration while pre-
E ([00((hit) Zn+z) (
The following theorem establishes that each isotonic cali- brated model f(2.0) used to construct the Venn-Abers pre- diction set is asymptotically conditionally calibrated.
C8) Best predictor of gradient has fmite variation: There exists an B < do such that t + Ep (aE(( (X), Y) f(X) t, Cr.] has total variation norm that is almost surely bounded by B.
Theorem 3.4 (Conditional calibration of Venn-Abers). Un- der C4-C6, and C8, we have Calys (fr. (((()))))))))) = Op(n 22/3).
serving predictive performance. van der Laan et al. (2023) show that, in the context of treatment effect estimation, the
conditional 2² calibration error of isotonic calibration for
This theorem generalizes the distribution-free conditional calibration guarantees for isotonic calibration of van der Laan et al. (2023) and van der Laan et al. (2024a) for regres- sion and inverse probabilities to general losses.
i..d. data asymptotically satisfies Calga (fii) = Op(n 2/3).
Algorithm 2 Venn-Abers loss calibration
Require: Calibration data C., = {(x,, Y= model f. loss l, context x E X.
Computational considerations. As discussed in van der Laan and Alaa (2024), the main computational cost of Alg. 2 lies in the isotonic calibration step for each y E y. Iso- tonic regression (Barlow and Brunk, 1972) can be efficiently computed using xgboost (Chen and Guestrin, 2016) with monotonicity constraints. Similar to Full CP (Vovk et al., 2005), Alg. 2 may be infeasible for non-discrete outcomes, but it can be approximated by iterating over a finite subset of Y with linear interpolation for f(æ,.) (æ)). Like Full and multicalibrated CP (Gibbs et al., 2023), this algorithm must be applied separately for each context x E X. Since the algorithms depend on E X only through its prediction f(x), we can approximate the outputs for all x E X by running each algorithm on a finite set of x E X correspond- ing to a finite grid over the one-dimensional output space f(X) = {f(z) : x E X' C R. Moreover, both algorithms are fully parallelizable across both the input context x X' and the imputed outcome y E y. In our implementation, we use nearest neighbor interpolation in the prediction space to impute outputs for each x E X. In our experiments with sample sizes ranging from n = 5000 to 40000, quantile binning of both f(X) and y into 200 equal frelufeey bins
1: for each y E y do
2: augment dataset: c( : C, U ((Xn+1, Yo+1) = v));
3: calibrate model using generalized isotonic regression:
0(.-0) argminsce... EiEckr.o (X.() 7,).
p(.))) .! f.
4: end for
(x): J';: 5: set (x) = ( (
Ensure:
prediction set (1).
In this section, we propose Venn-Abers calibration for gen- eral loss functions, a special instance of Venn calibration that employs isotonic regression as the underlying point calibrator, thereby generalizing the original procedure for classification and regression (Vovk and Petej. 2012; van der Laan and Alaa, 2024). Our generalized Venn-Abers calibra- tion procedure is outlined in Alg. 2. Isotonic regression is a stable algorithm, meaning small changes in the training set do not significantly affect the solution, ensuring that the Venn-A Aaen- prediction set converges to a point prediction as the sample size grows (Caponnetto and Rakhlin, 2006; Bous-
5

---

Generalized Venn and Venn-Abers Calibration
enables execution of Algorithm 2 with squared error and quantile loss across all contexts in minutes, with negligible approximation error.
Algorithm 3 Venn loss multicalibration
Require: Calibration data C, = {(X,, V. model f, loss E, context x E X, function class F.
1: for each y E y do
3.3. Venn multicalibration for finit-ddimensional classes
2: augment dataset: ck. := C. U [(Xn+1, Yn+1) == (z,, w)}:
3: multicalibrate model using offset loss minimization:
Standard calibration ensures that predicted outcomes can- not be improved by any transformation of the predictions, making them optimal on average for contexts with the same predicted value. However, this aggregate guarantee can mask systematic errors within subgroups. Multicalibration extends standard calibration by enforcing calibration within specified subpopulations, ensuring fairnsss and reliability across groups (Jung et al., 2008; Roth, 2022; Noarov and Roth, 2023; Deng et al., 2023; Haghtalab et al., 2023). In this section, we introduce Venn multicalibration, general- ization of Venn calibration that provides calibration guar- antees across multiple subpopulations. This approach pro- duces prediction sets that contain a perfectly multicalibrated prediction in finite samples. Our work enables the exten- sion of existing methods for pointwise multicalibration with generic loss functions to set-valued calibration (Noarov and Roth, 2023; Deng et al., 2023; Haghtalab et al., 2023).
gh = arginiu Eieetr {(f(x.) + g(x.), Z,).
ska := f + gi kh
4: end for
5: set fx, == (s (I) :E); Ensure: prediction set (x).
function class G, we propose Venn multicalibration for generic loss function ? in Algo- rithm 3. For mean multicalibration with squared error loss, this algorithm can be computed efficiently using the Sher- man Morr-ioon formula to update linear regression solutions with new data points (Shermen and Morrison, 1949; Yang et al., 2023). This formula has previously been used for efficient computation of leave-oneoout (e.g., Jackknife) pre- dictions by applying rank-one updates to the inverse Gram matrix, thereby enabling fast updates to the least-squares solution without retraining on each leave-one-out subset. Under monotonicity of y +> p!(,.)) tte range of the Venn prediction set fn.= can be computed by iterating over the extreme points {ymin ymax of )/
For a
We say model f is marginally perfectly (-multicalibrated with respect to a function class G if the following holds:
0t {V + +g)( 1)+ [ = 0 for all E 9,
(4)
The following theorem establishes that the prediction set fn.Xa-1 (Xa+1) in Alg. contains the f-multicalibrated prediction (X++())+)), where fü+1 == f/ ((xa1 Yn+1)
where the expectation is taken over (Xn+1, Yn+1) as well as randomness of f. Assuming the order of integration and
differentiation can be exchanged, this condition implies that
C9) In-sample multicalibration: tx)( l==0== 0 almost surely for each E G.
a11 2 ((( + i=
E (m+ = min E [e(CF + 9) ()) Yn+1)
DEG
In other words, the loss E( ((((X++)) Zn+1) incurred for the new data point cannot be improved in expectation by adjust- ing the calibrated model f using functions from G.
Theorem 3.5 (Perfect calibration of Venn multicalibration). Under CI and C9, the Venn prediction set fn.X,+s ( (Xn+1) contains the marginally perfectly calibrated prediction
( flx (X (( (Xn+z). which satisfies
Multicalibration for classification and regression requires that (Hébert-Johnson et al., 2018; Kim et al., 2019):
E
((Si+t + +g))(x++1) 71+1) 1c- = 0, Eg 0t
E (Y F(Xx+1)3} = 0 for all E G. (5)
The function g E &G is sometimes viewed to as a represen- tation of covariate shift. When g nonnegative, it follows
In the special case where E is the squared error loss, the next corollary shows that Venn prediction sets contain a perfectly multicalibrated regression prediction, as defined in (5).
that B2 [,[((X,++)] = E,(Yn++), where the weighted expec- tation is defined as Ex = E 9(x=+1) ((x.+1) E[g(X.+1))
Corollary 3.6 (Regression Venn Multicalibration) Sup- pose that {(f(x), =)) is fy - {(x))} Under Cl and C2, the Venn prediction set (x.x,_I(Xn=) con- tains the perfectly multicalibrated prediction, denoted as fū+1(Xn+1) = f( ((Xati. (x-))) which satisfies F. [g(Xx+i)(Yr4z fit1 (Xn=1))]] = for all g E G.
For example, when g = (ar + 1(x B) B B} consists of all set indicators for (possibly intersecting) subgroups in B, multicalibration implies that the model f(X.+1) is calibrated for Ya+1 within each subgroup, meaning that B/ | Xot1 E B] = E(f(())))) Xn-1 E B3.
6

---

Generalized Venn and Venn-Abers Calibration
4. Applications to conformal prediction
- a. This result follows directly from the perfect quantile calibration of fū+1 (Xn+1) because, by definition,
4.1. Conformal prediction via Venn quantile calibration
P(Yn+1 E (xn(X Ju+t (X++()))))
Conformal prediction (CP) (Vovk et al., 2005) is a flexi- ble approach for predictive inference that can be applied post-hoe to any black-box model. It constructs prediction intervals (x,++ that are guaranteed cover the true outcome Yn+1 with probability 1 The standard CP method ensures prediction intervals satisfy the marginal cov- erage guarantee: P(Y,+1 E Cx (X++1)) 2 1 - a, where the probability P accounts for the randomness in Cn and (Xa+1, 1.) In this section, we show how our general- ized Venn calibration framework, when combined with the quantile loss, enables the construction of perfectly calibrated quantile predictions and CP intervals in finite samples.
P(((((X++1, Ynt1)) S fn f fitt (Xn+1))
P(Sn+1 S Sn+i
f (Xn+1)
=1 =1-a.
As a consequence, the CP interval satisfies form of thresh- old calibration (Jung et al., 2022), meaning its coverage is valid conditional on the quantile fū+1 (X.+1) used to define the interval. The law of total expectation implies that C, (X,++) also satisfies the marginal calibration con- dition P(S.+1 I fü+ (Xn+1)) = 1 1-6 a. We note that, without assuming St o fu+1 (X,) almost surely for each [n + 1), we can still establish the lower bound P(Yn+1 E C. (X Si+z (X=+)))))) 2 1 - a using argu- ments from Gibbs et al. (2023), though we do not pursue this here for simplicity.
Let {S be conformity scores, where S: = S(,, Yi) for some scoring function S. For example, we could set S as the absolute residual scoring function 2 + ly-r((z),, where u predicts y from x. Conformity scores quantify how well a predicted outcome aligns with the true outcome. Let/ f: X + R be model trained to predict the (1-a) a.) quantile of the conformity scores. Given ʃ. we can define conformal interval for Ya+1 as (y y ((((x+1, S f(Xn+1))- However, this interval does not provide distribution-free coverage guarantees due to potential miscalibration of f. To ensure finite-sample coverage, we propose calibrating the predictor using quantile Venn and Venn-Abers calibration.
4.2. Conformal prediction as Venn multicalibration
In this section, we show that conformal prediction is a spe- cial case of Venn multicalibration with the quantile loss.
Suppose Alg. 3 is applied with the conformal quantile loss (f(z). + let fu. (X++1) be the corresponding Venn set predic- tion. As in Section 4.1, we define the multicalibrated Venn CP interval as (x,+) == {y E y : S(((x+1, v)) S x(xx+1.) (X.+)))(xx+))) This multicalibrated CP interval is iden- tical to the interval proposed in the conditional CP frame- work of Gibbs et al. (2023).
model f. and x == X and
For quantile level a E 10, we denote the quantile loss to (g. by (yy 2 a(y-
9) (yy (1-))(1a)(()) y). Let fn.x..1 (X 11) = (S (/. (Xn+1) : y E y} be the Venn quantile prediction set of Sn+1 obtained by
applying Algorithm 2 with the conformal quantile loss fs.a : 2f)2) + (f(f, and let (X be the perfectly calibrated prediction in this set, where fü+1 == ,(x,, I.YY.11) equals Ae(f, {(X,, (=))) The Venn pre-
The following theorem shows that Venn multicalibration outputs a prediction set containing a marginally multicali- brated quantile prediction (Deng et al., 2023), ensuring that the CP interval is multicalibrated in the sense of Gibbs et al. (2023).
diction set fn,x (Xa+z) induces the Venn CP interval:
Ca(Xn-1) == (VEY: S((( S f ((X++1.)) (Xx,)))))))))))) (Xn+1)}
Theorem 4.2 (Quantile Multicalibration). Assume CI holds and S, * fX+1(X,) almost surely for all E [m + 1). Then, the Venn prediction set fn,x.+3 (Xn+1) contains the perfectly multicalibrated prediction (X = fn ((X..1.Yn ()(n+11) which satisfies E ([g(Xx+)((1-0)) - P(S5+1 S (i+1(Xn+1) Xn+1)H]
C10) In-sample calibration: Eat Es Si+1) ming Ets1 Es.a(Zy, (Z,,0 A fat1).
Theorem 4.1 (Calibration of Venn Quantile Prediction). Assume CI, C1O, and that S. # (X,) almost surely for each i E [n + I1.. Then, the Venn prediction set Xa.Xa+i (Xn+1) contains the marginally perfectly cali- brated prediction (X41() = ((Xx=1)Yat)) (Xn+1), where P(S S fit11(X44)) (Xn+1())1)) = 11110 a.
0 for all g E geG.
By definition, Theorem 4.2 implies the multicalibrated cov- erage of the conformal interval: for all g E g.
E [X at) - P(Y++1 E (x | xx--))] = 0,
Theorem 4.1 implies that the Venn CP interval Cx constructed using Venn quantile calibration is perfectly cal- ibrated in that PY( E Cn (X I (++1(Xat1)) =
which agrees with Theorem 2 of Gibbs et al. (2023).
As a consequence, the multicalibrated CP framework for fiiiteddienniionll covariate shifts proposed in Section 2.2
7

---

Generalized Venn and Venn-Abers Calibration
of Gibbs al. (2023) can be interpreted a special case of Venn multicalibration. Similarly, the standard marginal CP approach (Vovk al., 2005; Lei et al., 2018) and Mondrian (or group-conditional) CP (Vovk et al., 2005; Romano et al., 2020) are special cases of this algorithm, with 9 consisting of constant functions and subgroup indicators, respectively.
Table 1. Metries for cach dataset: Marginal Coverage, Conditional Calibration Error (CCE), and Average Width. For CCE. smaller values are preferred, and the minimum value for each dataset bolded. For coverage, values close to 90% are desired, and the average width is ideally minimized while retaining coverage.
Method
Bike
Bio
Star
Meps
Cone
Com
Marginal Coverage
5. Numerical experiments
Uncalibrated
0.81
0.85
0.80
0.86
0.71
0.74
The utility of Venn and Venn-Abers calibration for classi- fication and regression, as well as Venn multicalibration with the quantile loss in the context of conformal predic-
Venn-Abers
0.90
0.90
0.90
0.90
0.90
0.90
CQR Marginal VM (5 bin)
0.90
0.90
0.90
0.90
0,90
0.90
0.90
0.90
0.90
0.90
0.90
0.90
0.90
0.90
0.89
0,90
0.89
0.90
tion (CP), has been demonstrated through synthetic and real data experiments in various works (Vovk and Petej. 2012:
VM (10 bin)
0.90
0,90
0.89
0.90
0.88
0.89
Conditional Calibration Error (CCE)
Nouretdinov et al., 2018; Johansson et al., 2019b;a; 2023;
Uncalibrated
0.11
0.088
0.11
0.053
0.20
0.17
van der Laan and Alaa, 2024; Vovk et al., 2005; Lei al.,
Venn-Abers
0.019
0.017
0.024
0.018
0.035
0.028
2018; Romano et al., 2019; Boström and Johansson, 2020;
CQR
0.031
0.020
0.026
0.020
0.037
0.031
Romano et al., 2020; Gibbs et al., 2023). In this section, we evaluate two novel instances of these methods: CP using Venn-Abers calibration with the quantile loss (Section 4.1) and Venn multicalibration for regression using the squared error loss.
Marginal
0.10
0.053
0.020
0.052
0.057
0,058
VM (5 bin)
0.033
0.025
0.023
0.026
0.044
0.030
VM (10 bin)
0.022
0.020
0.028
0.022
0.049
0.030
Average Width
Uncalibrated
83
12
620
2.4
9.4
0.22
Venn-Abers
100
14
780
2.8
0.40
5.1. Venn-Abers conformal quantile calibration
CQR
98
14
780
2.7
0.38
Marginal
140
15
780
2.9
18
0.46
We evaluate conformal prediction intervals constructed us- ing Venn-Abers quantile calibration on real datasets, includ- ing the Medical Expenditure Panel Survey (MEPS) dataset (Cohen et al., 2009; MEPS, 2021), as well as the Concrete, Community, STAR, Bike, and Bio datasets from Romano et al. (2019), which are available in the eqr package. Each dataset is split into a training set (50%). a calibration set (30%), and a test set (20%). We implement Venn-Abers quantile calibration (VA) using absolute residual error as the conformity score and train the 1 a quantile model f() of the conformity score using xgboost (Chen and Guestrin, 2016). The baselines include uncalibrated intervals derived from f-), symmetric variant of conformalized quantile regression (CQR) (Romano et al., 2019), Marginal confor- mal prediction (CP) (Vovk et al., 2005; Lei et al., 2018), and Mondrian conformal prediction (VM) (Romano et al., 2020), a quan-
VM (5 bin)
99
14
770
2.8
16
0.38
VM (10 bin)
100
14
770
2.8
16
0.38
All calibrated methods achieve adequate marginal coverage, as guaranteed by theory, while the uncalibrated intervals exhibit poor coverage. VA consistently achieves the low- est or comparable CCE across datasets, as expected from Theorems 3.4 and 4. outperforming or matching the state- of-the-art art CQR in terms of coverage, CCE, and width. Al- though VM CP improves with more bins, its CCE remains higher than that of VA, highlighting the advantage of data- adaptive binning via isotonic regression.
5.2. Venn mean multicalibration
with categories based on bins of the estimated tiles. VM corresponds to Venn calibration with Mondrian histogram binning. For direct comparability, all baselines are based the absolute residual error score by μ(=)), where μ((r is a xgboost predictor of the conditional me- dian of y. and intervals are thus centered around f(x)).
We evaluate Venn multicalibration for regression with squared error loss on the same datasets as in the previous experiment. To our knowledge, there is no prior work on set multicalibrators, and thus no existing comparators to Algo- rithm 3. Accordingly, the primary goal of this experiment is to assess the quality of the set-valued predictions in terms of (i) their size and (ii) the calibration error of the oracle multicalibrated prediction that is guaranteed to lie within the set.
Averaged over 100 random data splits, Table summarizes Monte Carlo estimates of marginal coverage, and condi- tional él callibbaatoo error (CCE), and average interval width. For fü the isotonic calibration of f. the CCE is defined
Each dataset is split into a training set (40%), a calibration set (40%). and a test set (20%). We train the model f using median regression with xgboost, such that the model is miscalibrated for the mean when the outcomes are skewed.
Ep (0, P(Y & (x(( (X(X) a [c.]
8

---

Generalized Venn and Venn-Abers Calibration
We apply Alg. 3 with 9 defined as the linear span of additive spline basis of the features, aiming for multicali- bration over additive functions. Specifically, for continuous features, we generate cubic splines with five knot points, and for categorical features, we apply one-hot encoding. As baselines, we consider the uncalibrated model and the point- calibrated model obtained by adjusting / via offset linear regression on C, based on G. All outcomes are rescaled to lie in [0, 1] for comparability across datasets.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Richard E Barlow and Hugh D Brunk. The isotonic re- gression problem and its dual. Journal of the American Statistical Association, 67(337):140-147, 1972.
Averaged averaged over 100 random data splits, Table 2 sum- marizes the sample size (n), feature dimension (p), condi- tional multicalibration errors for the uncalibrated, point cali- brated, and oracle cenn-calibrated predictions, and the aver- age Venn prediction set width. The oracle Venn-calibrated prediction the marginally perfectly calibrated prediction <xx, 1.) necessarily contained in the prediction set. For a basis {b,()) of G. the multicalibration error of a model f is defined as the e² norm of the test-set in-sample calibration errors:
Antonio Bella, Cèsar Ferri, José Hernández- Orallo,, and María José Gamfrez-Quintanee Calibration of machine learning models. In Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods, and Techniques, pages 246. IGI Global, 2010.
Henrik Boström and Ulf Johansson. Mondrian conformal regressors. In Conformal and Probabilistic Prediction and Applications, pages 114-133. PMIR, 2020.
by - j e [ml]
Olivier Bousquet and André Elisseeff. Algorithmic stability and generalization performance. Advances in Neural Information Processing Systems, 13, 2000.
Thestt
This error quantifies how well the model satisfies the multi- calibration criterion across a rich collection of (potentially overlapping) subpopulations defined by the functions by. as defined in (5). In particular, it captures calibration error both for discrete subgroups (e.g., based on binary covari- ates) and for continuous covariates through smooth density ratio weights.
Andrea Caponnetto and Alexander Rakhlin. Stability prop- erties of empirical risk minimization over donsker classes. Journal of Machine Learning Research, 7(12). 2006.
Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Dis- covery and Data Mining, KDD '16, pages 785-794, New York, NY, USA, 2016. ACM. ISBN 978-1-4503- 4232-2. doi: 10. 10.114552939967722999733 URL http: / //doi. acm. http///0.111///936722229999
Table Sample size and feature dimension (n, p), calibration er- rors for the uncalibrated model, calibrated model, calibraab model, and mean prediction set width for each dataset.
Dim.
Calibration Error
Width
(n, p)
Uncal
Calibr
Venn
Venn
Bike
(4354, 18)
0.0019
0.0015
0.0015
0.0086
Joel W Cohen, Steven B Cohen, and Jessica S Banthin. The medical expenditure panel survey: a national information resource to support healthcare cost research and inform policy and practice. Medical care, [t/[plppplemett 1): $44-S50, 2009.
Bio
(18292, 9)
0.0073
0.0100
0.0094
0.0100
Star
(864, 39)
0.0098
0.0113
0.0078
0.3260
Meps
(6262,
139)
0.0032
0,0017
0.0016
0.0088
Cone
(412, 8)
0.0077
0.0081
0.0064
0. 0430
Comm
(797, 101)
0.0099
0.0209
0.0055
0.6650
David R Cox. Two further applications of a model for binary regression. Biometrika, 45(3/4):562-565, 1958.
The oracle Venn-calibrated model consistently achieves smaller calibration errors than the point-calibrated model across all datasets and outperforms the uncalibrated model in all but one dataset. Its improvement is more pronounced in settings with wider Venn prediction sets, which corre- spond to smaller effective sample sizes n. In these cases, naive multicalibration is more variable and prone to overfit- ting. This aligns with expectations, as wider prediction sets reflect greater uncertainty in the finite-sample calibration of point-calibrated predictions.
Sharon Davis, Thomas Lasko, Guanhua Chen, Ed- ward Siew, and Michael E Matheny. Calibration drift in regression and machine learning models for acute kid- ney injury. Journal of the American Medical Informatics Association, 1052 1061, 2017.
Zhun Deng, Cynthia Dwork, and Linjun Zhang. Happymap: A generalized calti-callbbatioo method. arXiv preprint arXiv:2303.04372 2023.

---

Generalized Venn and Venn-Abers Calibration
Bernard Flury and Thaddeus Tarpey. Self-consistency; A fundamental concept in statistics. Statistical Science, 11 (3):229-243, 1996.
Christopher Jung, Changhwa Lee, Mallesh M Pai, Aaron Roth, and Rakesh Vohra. Moment multicalibration for uncertainty estimation. arxiv preprint, 2020. URL: https://arxiv. org/abs, 2008.
Isaac Gibbs, John J Cherian, and Emmanuel J Candès. Con- formal prediction with conditional guarantees. arXiv preprint arXiv:2305. 12616, 2023.
Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Batch multivalid conformal prediction. arXiv preprint wtXiv:2209.15155 2022.
Usman Gohar and Lu Cheng. A survey intersectional faimess in machine learning: Notions, mitigation, and challenges. arXiv preprint wxXiv:335500996 2023.
Michael Kim, Amirata Ghorbani, and James Zou. Mul- tiaceuracy: Black-box posc-proes for fairness in classification. Proceedings of the 2019 AAAI/ACM Conference AI, Ethics, and Society, pages 247-254, 2019.
Piet Groenehoom and HP Lopuhaa. Isotonic estimators of monotone densities and distribution functions: basic facts. Statistica Neerlandica, 10::1775-1333 1993.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Weinberger. On calibration of modern neural networks. In Interna- tional conference on machine learning, pages 1321-1330. PMLR, 2017.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan Tibshi- rani, and Larry Wasserman. Distribution-fret predictive inference for regression. Journal of the American Stalis- tical Association, 1136623):104--111,, 2018.
Chirag Gupta and Aaditya Ramdas. Distribution--ree cali- bration guarantees for histogram binning without sample splitting. In International Conference on Machine Learn- ing, pages 3942-3952. PMLR, 2021.
Sarah Lichtenstein, Baruch Fischhoff, and Lawrence Phillips. Calibration of probabilities: The state of the art. In Decision Making and Change in Human Affairs: Proceedings of the Fifth Research Conference on Subjec- tive Probability, Utility, and Decision Making, Darmstadt, 1-4 September, 1975, pages 275-324. Springer, 1977.
Chirag Gupta, Aleksandr Podkopaev, and Aaditya Ramdas. Distribution free binary classification: prediction sets, confidence intervals and calibration. Advances in Neural Information Processing Systems, 33:3711-37233 2020.
Ellen Mandinach, Margaret Honey, and Daniel Light. theoretical framework for data-driven decision making. In annual meeting of the American Educational Research Association, San Francisco, CA, 2006.
Nika Haghtalab, Michael Jordan, and Eric Zhao. A unifying perspective on multi-calibbation: Game dynamies for multi-objective learning. Advances in Neural Information Processing Systems, 04772464-2500 2023.
MEPS, 2021. Medical expenditure panel survey, panel 21, 2021. hRtttss::/mmeps ahrq gov/mepsweb/ data_ htt__sstts/ddwwoodddadss
Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the coomputationally--deefffia masses. In International Conference on Machine Learning, pages 1939-1948.
aatpelodddddd____eeeeeaaa data daa_dd_daata_________a______eeee lelee_deeail...
Accessed: May,
2024.
PMLR, 2018
Jacob Mincer and Victor Zarnowitz. The evaluation of economic forecasts. In Economic forecasts and expecta- tions; Analysis of forecasting behavior and performance, pages 3-46. NBER, 1969.
Xiaoqian Jiang. Melanie Osl, Jihoon Kim, and Lucila Ohno- Machado. Smooth isotonic regression: new method to calibrate predictive models. AMIA Summits on Transla- tional Science Proceedings, 201 1:16, 2011.
Alexandru Niculescu- Mizil and Rich Caruana. Obtaining calibrated probabilities from boosting, In UAI, volume pages 413-20, 2005.
Ulf Johansson, Tuve Löfström, Henrik Linusson, and Henrik Boström. Efficient venn predictors using random forests. Machine Learning, 008:535-550, 2019a.
Georgy Noarov and Aaron Roth. The scope of multicalibra- tion: Characterizing multicalibration via property elicita- tion. arXiv preprint axXiv:2302.08507, 2023.
Ulf Johansson, Tuwe Löfström, and Henrik Boström. Cali- brating probability estimation trees using venn-abers pre- dictors. In Proceedings of the 2019 SIAM International Conference on Data Mining, pages 28-36. SIAM, 2019b.
Ilia Nouretdinov, Denis Volkhonskiy, Pitt Lim, Paolo Toc- caceli, and Alexander Gammerman. Inductive venn-abers predictive distribution. Conformal and Probabilistic Prediction and Applications, pages 15-36. PMLR, 2018.
Ulf Johansson, Tuwe Löfström, and Cecilia Sönströd. Well- calibrated probabilistic predictive maintenance using venn-abers. arXiv preprint arXiv:2306.0660 2023.
10

---

Generalized Venn and Venn-Abers Calibration
John Platt et al. Probabílistic outputs for support vector ma- chines and comparisons regularized likelihood meth- ods. Advances in large margin classifiers, 10(3):61-74, 1999.
Michael Veale, Max Van Kleek, and Reuben Binns. Fairness and accountability design needs for algorithmic support in high-stakes public sector decision-making, In Pro- ceedings of the 2018 chi conference on human factors in computing systems, pages 1-14, 2018.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Advances in neural information processing systems, 32, 2019.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference machine learning, pages 475-490. PMLR, 2012.
Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès. With malice toward none: Assess- ing uncertainty via equalized coverage. Harvard Data Science Review, 2(2))4, 2020.
Vladimir Vovk and Ivan Petej. Venn-abers predictors. arXiv preprint arXiv: 221120025. 2012.
Vladimir Vovk, Glenn Shafer, and Ilia Nouretdinov. Self-
Aaron Roth. Uncertain: Modern topics in uncertainty esti- mation. Unpublished Lecture Notes, page 2, 2022.
calibrating probability forecasting. Advances in neural information processing systems, 16, 2003.
J Shermen and WJ Morrison. Adjustment of inverse ma- trix corresponding to changes in the elements of given column or a given row of the original matrix. Annual Mathmatical Statistics, 20:621-625, 1949.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29. Springer. 2005.
Justin Whitehouse, Christopher Jung, Vasilis Syrgkanis, Bryan Wilder, and Zhiwei Steven Wu. Orthogonal causal calibration. arXiv preprint arXiv:2406.01933 2024.
Telmo Silva Filho, Hao Song, Miquel Perello-Nieto, Raul Santos-Rodrighen Meelis Kull, and Peter Flach. Classi- fier calibration: survey on how to assess and improve predicted class probabilities. Machine Learning, 112(9): 3211-3260, 2023.
Yachong Yang, Arun Kumar Kuchibhotla, and Eric Tch- etgen Tchetgen. Forster-warmuth counterfactual re- gression: A unified learning approach. arXiv preprint TrXiv:2307.16796 2023.
Paolo Toccaceli. Conformal and Venn Predictors for large, imbalanced and sparse chemoinformaties data. PhD thesis, Royal Holloway, University of London, 2021.
Bianca Zadrozny and Charles Elkan. Obtaining cali- brated probability estimates from decision trees and naive bayesian classifiers. In Icml, volume 1, pages 609-616. Citeseer, 2001.
Lars van der Laan and Ahmed Alaa. Self-calibrating confor- mal prediction. The Tiirty-eighth Annual Conference Neural Information Processing Systems, 2024.
Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass probability estimates. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 694 699, 2002.
Lars van der Laan, Ernesto Ulloa-Pérez, Marco Carone, and Alex Luedtke. Causal isotonic calibration for het- erogeneous treatment effects. In Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202, Honolulu, Hawaii, USA, 2023. PMLR.
Lars van der Laan, Ziming Lin, Marco Carone, and Alex Luedtke. Stabilized inverse probability weighting via isotonic calibration. arXiv preprint arXiv:2411.06344 2024a.
Lars van der Laan, Alex Luedtke, and Marco Carone. Au- tomatic doubly robust inference for linear functionals via calibrated debiased machine learning. arXiv preprint arXiv:2411.027711 2024b.
Aad Van Der Vaart and Jon A Wellner. A local maximal inequality under uniform entropy. Electronic Journal of Statistics, 5(201 192, 2011.
Janette Vazquez and Julio C Facelli. Conformal predic- tion in clinical medical sciences. Journal of Healthcare Informatics Research, 6(3):241-252 2022.

---

Generalized Venn and Venn-Abers Calibration
A. Code Availability
Python code implementing Venn-Abers and Venn multicalibration methods for both squared error and quantile losses available in the VennCalibration package at the following GitHub repository:
https:: http://ww..coo/aaaaaaaeeeeeeeeee /VennnC ibratiion
The repository includes scripts and documentation for reproducing all experiments in this paper.
B. Background on isotonic calibration
Isotonic calibration (Zadrozny and Elkan, 2002; Niculescu-Mizil and Caruana, 2005) is data-adaptive histogram binning method that learns the bins using isotonic regression, nonparametric method traditionally used for estimating monotone functions (Barlow and Brunk, 1972; Groeneboom and Lopuhaa, 1993). Specifically, the bins are selected by minimizing an empirical MSE criterion under the constraint that the calibrated predictor is a non-decreasing monotone transformation of the original predictor. Isotonic calibration motivated by the heuristic that, for good predictor f. the calibration function p should be approximately monotone function of f. For instance, when f(-) Ep[Y X -], the mapping - Op. = f is the identity function. Isotonic calibration is distribution assumptions and, in contrast with histogram binning, it is tuning parameter-fre -ree and naturally preserves the mean-square error of the original predictor (as the identity transform is monotonic) (van der Laan et al., 2023).
does not rely on monotonicity
For clarity, we focus on the regression case where l denotes the squared error loss. Formally, isotonic calibration takes a predictor f and a calibration dataset C2 and produces the calibrated model fn == 0n o f. where 8, RR - R an isotonic step function obtained by solving the optimization problem:
n
nn E argmin IE0..
(Y, ((f(x:)))
(6)
where Os5 denotes the set of all univariate, piecewise constant functions that are monotonically nondecreasing. Following Groeneboom and Lopuhaa (1993), we consider the unique càdlåg piecewise constant solution to the isotonic regression problem, which has jumps only at observed values in {f(X.) convex optimization problem imply that the isotonic solution ,, acts binning calibrator with respect to data-adaptive set of bins determined by the jump points of the step function O.. Thus, isotonic calibration provides perfect in-sample calibration. Specifically, for any transformation g IR - R. the perturbed step function + A, + E(g o f₂) remains isotonic for all sufficiently small such that |e| suPres(x)) (xx) ((g o (l) is less than the maximum jump size of On. given by supte ((x) (t) 0, (t-)]. Since On minimizes the empirical mean square error criterion over all isotonic functions, follows that, for each function g : >> R, the following condition holds:
E [n]]. The first-order optimality conditions of the
1
(Y - ==
O0 0.
de
These orthogonality conditions are equivalent to perfect in in-sample calibration. In particular, by taking as the level set indicator + I[t 0, (x))), we conclude that the isotonic calibrated predictor fx is in-sample calibrated.
C. Proofs
C.1. Proofs for Venn calibration
Proof of Theorem 3.1. From C3, we know that
Σ (T)))))))))))))))00000000 Z.) =
This condition implies, for every transformation g:R-y IR, that
Σ (x.)0 (X),, Z,) 0.
12

---

Generalized Venn and Venn-Abers Calibration
Taking the expectation of both sides, find that
E
E (1
Note that Fü+1 is trained all of C++1 and is thus invariant permutations of {(X,, Y)) Since {(,, Y) exchangeable by C1, it follows that g(f= (X,)))E(fi+z) (X;), 2,) is exchangeable over E [n + 1]. Thus, the previous display implies, for every transformation R + R. that
(Xn+1): E [o( (X)= (X Zn+1)]
i=1
E [9(fū+z (X (00(+) Zn+1)
E ( 11000
2n-1)
where the final equality follows from the law of total expectation. Taking such that ((f+t1(z))
E[0((f++1 (Xnt1)) Zn+1) I (X = f (z)], which exists by C2, we conclude that
E [1 Zn+1) fiti (Xn+a))))
Proof of Theorem 3.2. For uniformly bounded function class F, let (e,, F, LP() denote the e-covering number (?) of F with respect to L2(P) and define the uniform entropy integral of F by
F(. - J. sup N(c, F,
where the supremum is taken over all discrete probability distributions Q. For two quantities x and y, we use the expression S y to mean that is upper bounded by times universal constant that may only depend on global constants that appear in our conditions.
We know that of almost surely belongs to uniformly bounded function class F, consisting of ID functions with at most (nn) constant segments. Then, Fr has finite uniform entropy integral with [6,, F.) & 5</k(n) log(1/8). Define Fj.. = (0 f Fa). We claim that [66 Fy.n) ) S 5 kk(n)) log(1/)). This follows since, by the Shange-of-variablee formula,
J(5 = [
5
sup V NNe,, llQ) de
Q
['d sup /N(E, llQos) ds Q
Fo).
where, with a slight abuse of notation, Q f is the push-forward probability measure for the random variable f(X). By assumption, we have perfect in-sample calibration: for all g R.
Σ ((x YJ) (00r0 (((0)))0((03))))) (f(z),, v)
13

---

Generalized Venn and Venn-Abers Calibration
Take g such that = equals + Ep(or (f(x)) 0g (s(X)) = 1, C.). Then, denoting 75 75(0 ()) x
(f(x))) Ep(0e(0), (f(x)))=') 0h w) (f(x)) - 0% ( (f(z'), Cn], we find that
70(0 ( Y.) + ,00000
By assumption, yy (0, (0) 1) (f(x)), v) is uniformly bounded, such that
1 n
7 (0( x.)00(()=)))(XX))) -(
n
Adding and subtracting, we have that
(000 Onn Prl(0 ((()) + (Pr (h 00000 "0 (f(), 0 P(as(0(am) ).2² + (Pn - Phi,(0 ,0)0 (00000
=0 (f(),)) - ((()))))(((m)))
where, in the final equality, used that Pry (0p (0 -)ee(!! (f(), = P(yy(0! , by the law of total expecta- tion.
The random quantity we wish to bound by Ply (0 ( .)} Then, the previous display implies
[P,, ())1)(0-)00(00000) O(n sup (EF.clly(00))l
By boundedness of (E(O(((),)) (1, (1, (00(0000))))))))))))))))))))))))
1 for some K < cc. Thus,
8
(Pn P)gl On
sup
g
where Gy (0192:0 : 91 E $1. E G with Gl.f {00(0([(),, () 0 e F.) and == (1)(0,-) Fn).
We claim that (66 $ J() & 8vk(() logk))(gg(11 (1g(1)) By assumption, the following Lipschitz condition holds al- surely: (0)(0) (f(X),, -)- (()((((((())) Y) x (s())))) (x(J(X)) It follows that [ G1.)) X (6, Moreover, (6, f2 I [(8,F since (0, .) F is piecewise constant function with at most k(n) constant segments for each 0 E Fn. Therefore, [65, S I( $ Fx) and the claim follows.
Define on (0) == sup gEg, :llll [Pn, P)g). Then, we can write
& h 2n + On
Applying Theorem 2.1 in Van Der Vaart and Wellner (201 1), have that for any 8 satisfying vno² 2 [(6
E (l) (6)] S n (
Consequently, since ((, k( log (166), it follows that for any 5 2 k(n) log(1/8)
E (6) 2 (ogg
It can be shown that 63 : knn) log(n/k(n)) satisfies the critical inequality 8, 2 k(m) log(1/8m)) such that the previous
identifies be applied with 8 8n Showing the asserted stochastic order, 82 0,(5%) with d k(n) log(n/k(()) is equivalent to demonstrating that for all 0, there exists a sufficiently large 2 such that
lim P(5 P 25)= 22+00
14

---

Generalized Venn and Venn-Abers Calibration
To this end, we need to show lim P( % > 28) + 0 as S + oc. Define the event A, = {o E (2", (2",2*t1] 20t for
each s. Using a peeling argument and Markov's inequality, we obtain
30
P(8 > 25) -
P(2 2 3,
> 2*)
P P(A., 84 S (6,)) + ())
P(A,, 82 S (n + -(
P( < on + O()
==
20
Σ
2 < 2n (6,2 + +n
O6 (6, (122))1 } + 0
0
11-1 # v [k(n)
2
+ O(n-1)
8220
62.2"
8=
8=8
00
2 + 0(1)
5-000 0.
Thus, 82 = (6)))) and the result follows.
Proof of Theorem 3.4. This proof follows from a generalization of the proofs of Theorem 1 for treatment effect calibration and propensity score calibration in van der Laan et al. (2023) and van der Laan et al. (2024a).
Recall that c((-.)) = 0.2,0) f. Under C8, up to change of notation, the proof of Lemma 3 establishes that the map + Ep(oE(f (2.0) (x), 2) | fu (2.8) (x) of.-2) (t), has a total variation norm almost surely bounded by 3B, Consequently, the function 7 (0( (1..)) )): x [ (( (X), 2) S (Z..)) (X) = ((x.)) (x) is a transformation of s
with a total variation norm almost surely bounded by 3B.
Let Fry denote the space of ID functions with total variation norm bounded by 3B. Let Fiso denote the space of isotonic functions that are uniformly bounded, such that the isotonic regression solution ((x-2) belongs to this set. Note that J6,, Z /8 and Fo.o) Z V8.
Proceeding exactly in the proof of Theorem 3.2, can show that the quantity we wish to bound, 33 = Plyy(Ola ())3 satisfies
&2
[(P, ())y(0,))0(((((0)))))) +0=
sup F. (0,)) S3.
By the boundedness of (E(O([()), }), we have 11 (0((0))))(((()))))))))))))))) ()))(((()))))l 5 (0 )l for some K < xo. Thus,
(Pn - P)gl + O(n
sup
where 9, : {9192 91 E 91.r.92 E G2,5) with G1 == (ae(B(f(),))) : E Frv) and := == (0, : 8 E Fiso
An argument similar to the proof of Theorem 3.2 shows that ( S [(8, + [6, S Vo.
The result now follows by applying an argument identical to the proof of Theorem 3.2, where we set 0 == n 2/3 and use J J(6.9r) S V8.
15

---

Generalized Venn and Venn-Abers Calibration
C.2. Proofs for Venn multicalibration
Proof of Theorem 3.5. By C9, we have almost surely for each g that
Σ
+ +
((ff+))
(X,), Z,) t=
0.
Ot
Taking the expectations of both sides above and leveraging CI, we have
a+1
i
Ot ((UE+1 + (X)) 7,)
=0
1=
x 1
((((((+t) + tx,( Z
0,
Ot
1=
n+1 1
E
[(fr++ + (g) Zn+1)
0,
Øt
1=1
1=
E
e((Fi+1 + (X 1n+z)
0,
Øt
as desired.
Proof of Corollary 3.6. This result is direct consequence of Theorem 3.5, but we provide an independent proof for clarity and completeness.
Define l++1 == p((nn11.a11), and note that ( (Xa+1) is an element of fn,x,,1 (Xa+1) by construction. The first-order optimality conditions of the empirical risk minimizer gn (N4+1) imply that, for each y E 9.
a+1
71 Σ ((x)) (Y, - ((+1 O.
Taking the expectation of both sides, which we can do by C2, and leveraging C1, we find that
2+1
0 =
[x(),) (Y fü+t (X:)]]
E [ X (Yn+1 futz (Xata))))
E (g(xn+) {Yn+1 (x+t(Xn+1))).
C.3. Proofs for conformal prediction
Proof. Proof of Theorem 4.1 Under the assumption that S; * fi+1 (X;) almost surely for all i e [n [n+1] 11, it is shown in Section 2.2 of Gibbs et al. (2023) that the quantile loss is differentiable almost surely. Moreover, its derivative is given by
(((() = (1 - a) 1{5(x) 2 f(z)).
The result now follows by application of Theorem 3.1.
Proof. Proof of Theorem 4.2 Under the assumption that * (Xt) almost surely for all [n+ [1, shown in Section 2.2 of Gibbs et al. (2023) that the quantile loss is differentiable almost surely. Moreover, its derivative is given by
laf + (z), < g(x) [11 - a) - 1{5(x) 2 f(x)))
de
The result now follows by application of Theorem 3.5.
16


Reviews:
[{"review_id": "vW7wpNU7kw", "reviewer": "Reviewer_vJic", "summary": "Conformal Prediction arrises as a techniques for turning a point predictor to a set predictor, allowing for a guarantee that the set contains the ground-truth target with high probability. Venn-Predictor operates similarly but output a set of probabilistic prediction with the guarantee that at least one of them is calibrated. The core contribution is that the paper extends Venn calibration (originally for multi-class classification) to arbitrary prediction tasks and general loss functions. Provides a unified framework that applies to both classification and regression. Ensures finite-sample marginal calibration while allowing for asymptotic conditional calibration under stronger regularity .", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful questions and suggestions. We will take incorporate your suggestions in the revised version of our manuscript. We clarify the efficiency and practicality of our method below.\n\n1. **Efficient Approximation and Scalability**  \n   The algorithm can be efficiently approximated using the approach described in Section 3.4 of [1] for Venn-Abers calibration with squared error loss, which we also adopt in our implementation. The key observation is that the Venn-Abers algorithm only depends on the test point features through the original model prediction (which is crucially a one-dimensional quantity). As a result, we can discretize the one-dimensional prediction space—e.g., by binning into a grid of 200 bins—and run the algorithm once per grid point. Isotonic regression can be computed efficiently using regression trees with monotonicity constraints, such as those available in XGBoost. Across all datasets (each with tens of thousands of data points), computing the approximate Venn-calibrated sets for all points takes under a minute. This method scales well to large datasets via XGBoost. The isotonic regression step is computationally lightweight and can be parallelized if needed. \n\n2. **Efficiency at Inference Time**   In our implementation, we precompute the Venn-Abers prediction sets over a discretized grid (200 bins) of model predictions. At inference time, we use nearest neighbor matching or linear interpolation to produce calibrated prediction sets, avoiding any calibration computation at run time. The approximation error from this approach is negligible in practice, likely due to the piecewise constant nature of both the isotonic regression solution and the Venn-Abers sets.\n\n3. **Clarification on Disjointness**  We are unsure why disjointness would be required. The Venn-Abers prediction set is defined as the set of predictions obtained when calibrating with a new data point and all possible imputed outcomes. There is no requirement or expectation for this set to be disjoint.\n\n4. **Improving experiments** We will add additional baselines to the conformal prediction experiments, including the conditional conformal prediction method of [1] and approaches based on alternative conformity scores, such as the normalized absolute residual error. We will also include error bars for our evaluation metrics to account for variability across the 200 train–validation–test splits over which the results are averaged.\n\n\n\n[1] van der Laan, Lars, and Ahmed M. Alaa. \"Self-calibrating conformal prediction.\" arXiv preprint arXiv:2402.07307 (2024).\n[2] Gibbs, Isaac, John J. Cherian, and Emmanuel J. Candès. \"Conformal prediction with conditional guarantees.\" arXiv preprint arXiv:2305.12616 (2023).", "claims_and_evidence": "Yes the assumptions and claims are transparently stated.", "methods_and_evaluation_criteria": "The evaluation is reasonable but could be improved in several aspect i.e including more existing CP methods.", "theoretical_claims": "The claims and proofs essentially follows existing works on Venn-predictors with the inclusion of the loss function in the definition of calibration following (Whitehouse etal 2024). I followed the proof of the main results 3.1 which seems correct, and skip the rest.\n\nThe authors might want to revisit the claims of extending VP to *arbitrary loss function* since the latter is quite restricted (smooth, proper loss, finite moment assumptions, lipschitzness etc ...) etc...", "experimental_designs_or_analyses": "The evaluations does not provide errors bars, and compare the methods.\n\nPlus, from table 1, the average width are quite all similar except in the Bike dataset.\n\nThe authors might want include several recents methods other than CQR (published at least 5 years ago). Overall the strict advantages of such proposed methods wrt classical CP is not that clear.", "relation_to_broader_scientific_literature": "Since the introduced method suffer from computational limitations as Full conformal prediction, discussing how to overcome the limitations could be welcomed.\n\nAlso, it is quite well known that calibration metric such as ECE suffers come inconsistency, it should be nice to include smooth version of ECE.", "essential_references_not_discussed": "The recent advances on smooth ECE could be included but does not have negative consequence for understanding the paper.", "other_strengths_and_weaknesses": "The overall proposition of extending VP with a specific loss is quite interesting on its own, but the authors could detail and motivate  a bit more this part.\n\nThe numerical experiments does not demonstrate a clear advantage of the proposed method but seems competitive.", "other_comments_or_suggestions": "NA", "questions_for_authors": "- I appreciate your work on generalized Venn and Venn-Abers calibration. I have some questions regarding the empirical calibration guarantee. From Condition C3, it appears that empirical calibration is enforced by exactly solving isotonic regression and recomputing it for each new test point X_{n+1}, as well as for every possible value of y. This suggests that calibration is dynamically maintained by including the test point in the calibration set before solving isotonic regression, avoiding the usual generalization issues. However, this approach raises computational concerns: (1) Since isotonic regression is recomputed exactly for each new test point, how does this scale in practice? (2) Given that recalibration is done for all possible values of y, does this lead to a significant computational burden, especially for large-scale settings? (3) Does this approach imply that we cannot precompute a single calibrated model but must instead recalibrate dynamically at inference time? I would appreciate any clarifications on these aspects. Overall I am confuse with the computational overhead, and do not see how techniques used in Full CP help Here.\n\n- Often, one needs to have disjoint sets and not only a single interval. Can the proposed method allows such a flexibility?\n\n\n\n\"## update after rebuttal\"\n\nI maintain my score and previous points. I think the authors should clarify more the computational aspect, choice of the grid, how it impacts coverage, computational efficiency etc ... These issues are not fully solved for full conformal prediction, and a transparent discussions in the case of this particular paper could help readers.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IsevD8jkjM", "reviewer": "Reviewer_BPmy", "summary": "The authors propose a unified framework for Venn and Venn-Abers calibration that leverages binning calibrators to construct prediction sets that contain at least one marginally perfect calibrated prediction. Furthermore, they propose a novel method for Venn calibration technique across subpopulations. Their method outperforms the baselines in all but one case.\n\n## Update after rebuttal\nWe have read the authors' responses, and they have addressed our concerns and promised to update the manuscript accordingly in the revised version. We lean toward acceptance and have updated our score to Accept.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your detailed comments and suggestions. We will incorporate them in the revised version of the paper.\n\nWe note our primary contribution is the generalization of Venn and Venn–Abers calibration to arbitrary loss functions. As a secondary contribution, we show that the same techniques yield a multicalibration algorithm with set-valued predictions. Our goal is primarily theoretical: to present a unified framework that generalizes and connects existing methods, including Venn–Abers calibration and conformal prediction.\n\n\n 1) In the revised paper, we will also report multicalibration error over specific subpopulations. In our experiments, we use the $\\ell^2$ norm defined in Equation (4), corresponding to regression multicalibration error. This metric, also used in [1] for quantile multicalibration, ensures multicalibration over finite-dimensional classes of covariate distribution shifts—specific subpopulations being a special case. We define the function class in Equation (4) as linear combinations of binary features, one-hot encoded categorical features, and spline-transformed continuous features (with 5 knots). The reported $\\ell^2$ error is the norm of the vector of calibration errors across these transformed features. For datasets with binary features, this directly captures multicalibration error over the associated subpopulations.\n\n\n\n\n2)  We recognize that the evaluation of our multicalibration experiments can be improved, and we will address this in the revision. To the best of our knowledge, our Venn multicalibration algorithm is the only method that produces prediction sets capturing uncertainty under multicalibration in regression settings, and thus lacks direct baselines. In principle, our approach can be combined with any multicalibrator that outputs empirically multicalibrated point predictions—such as those in the cited references—to generate uncertainty-aware prediction sets. One goal of our experiments is to show how prediction set widths vary across datasets with different sample sizes and feature dimensions. For instance, the \\textsc{Comm} and \\textsc{Star} datasets yield wider prediction sets due to high feature dimensionality and small sample sizes, reflecting greater uncertainty in the multicalibration process.\n\n\n\n3) Thank you for this suggestion. We agree that a clear discussion of calibration quality and appropriate evaluation metrics is important for interpreting and comparing results, and we will include this in the revised version. In the multicalibration experiments, our primary goal is to assess the quality of set-valued predictions in terms of (i) their size and (ii) the calibration error of the oracle multicalibrated prediction guaranteed to lie within the set. Specifically, we aim for multicalibration uniformly over target populations whose density ratios with the source population lie in a linear class derived from a basis transformation of the features. The reported $\\ell^2$ multicalibration error measures how well the predictions satisfy the multicalibration criterion across many overlapping subgroups defined by these density ratios. This approach is motivated by prior work in quantile multicalibration [1] for feature-conditional coverage. We will incorporate this clarification in the final version to better guide practitioners and researchers seeking meaningful evaluation metrics for multicalibrated prediction sets.\n\n \n4) Since the datasets are based on real-world data, we cannot generate independent replicates to compute standard Monte Carlo error estimates. Instead, we averaged all metrics over 200 random train-test-evaluation splits. In the final version, we will report Monte Carlo error estimates reflecting the variation of these metrics across the random splits.\n\n5) In the revised paper, we will also report subpopulation multicalibration errors. The multicalibration definition in Equation (5) extends beyond fixed subgroups to classes of \"covariate shifts\", following the terminology of [1] on quantile multicalibration. Consistent with this work, we adopt a model- and subgroup-agnostic approach, aiming to approximate multicalibration across many subgroups without requiring explicit specification. In our experiments, we achieve this by calibrating over subgroups whose density ratios with the source population are additive functions of the covariates, implemented via adjustments over additive spline basis functions. While we agree that subgroup-specific calibration is also valuable, our experiments focused on guarantees that do not depend on manual subgroup definition.\n\n\n(6) In the revised version, we will add background on multicalibration and clarify how our contributions relate to prior work. While multicalibration is an important aspect, we note our primary focus is on calibration.\n\n\n[1] Gibbs, Isaac, John J. Cherian, and Emmanuel J. Candès. \"Conformal prediction with conditional guarantees.\" arXiv preprint arXiv:2305.12616 (2023).", "claims_and_evidence": "(1)- The authors propose Venn multicalibration, ensuring finite-sample calibration across subpopulations. While they show how based on some preconditions (exchangeability and finite variance) and applying a particular algorithm, the multicalibration can be achieved for Venn calibrators. Neverthelesss, while the authors provide some empirical evidence on this aspect of their research, we consider the experiments should modified to strengthen their claims. In particular, multicalibration requires a calibrator to be calibrated across subpopulations, but the authors fail to identify subpopulations in each of the proposed datasets and to provide insights regarding the quality of calibration for each of those subpopulations.", "methods_and_evaluation_criteria": "(1)- While the authors consider several datasets that have been used in reputed works related to conformal predictions, we would appreciate it if they could ground their choice from the subpopulations perspective. The fact that the datasets present subpopulations is key to their experiments for multicalibration and datasets failing to satisfy that characteristic should be excluded from the multicalibration experiments. \n\n(2)- We would appreciate it if the authors would justify their choice regarding baseline methods, to understand why these are relevant to this particular experiments. In particular, we miss comparisons against multicalibration techniques. While the authors reference some of these works among the cited literature, they do not consider such methods as baselines (e.g., Hébert-Johnson, U., Kim, M., Reingold, O., & Rothblum, G. (2018, July). Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning (pp. 1939-1948). PMLR., or Deng, Z., Dwork, C., & Zhang, L. (2023). Happymap: A generalized multi-calibration method. arXiv preprint arXiv:2303.04379.) \n\n(3)- The authors evaluated the performance of the proposed method against the baselines based on three metrics. We would appreciate it if the authors would describe what aspects need to be assessed to guarantee the quality of the calibration and what metrics best assess those aspects. Furthermore, we would appreciate some insights into commonly used metrics to assess the general calibration and multicalibration scenarios so that they can be used as a reference when comparing to other works from this domain.\n\n(4)- The authors did not perform any assessment on whether the results obtained are statistically significantly better than the baseline approaches. We suggest they perform such assessment.", "theoretical_claims": "(1)- The authors introduce a unified framework for Venn and Venn-Abers calibration, generalizing Vovk and Petej (2012) to arbitrary prediction tasks and loss functions. -> The authors demonstrate that their unified framework is a generalization of Venn and Venn-Abers calibration theoretically. \n\n(2)- For quantile regression, the authors claim that Venn calibration corresponds to a novel CP procedure with quantile-conditional coverage, and that multicalibrated conformal prediction (Gibbs et al., 2023) is a special case of Venn multicalibration, unifying and extending existing calibration methods. -> The authors demonstrate their claim theoretically.", "experimental_designs_or_analyses": "(1)- While multicalibration requires a calibrator to be calibrated across subpopulations, the authors fail to identify subpopulations in each of the proposed datasets. We consider this to be a critical issue to provide insights regarding the quality of calibration for each of those subpopulations.", "relation_to_broader_scientific_literature": "The authors provide many references to the relevant literature. Nevertheless, while they mostly focus on Venn and Venn-Abers calibration and their relationship to conformal predition, while one of their main contributions is Venn multicalibration. Therefore, we consider that the related work must be enhanced to introduce the reader to the state-of-the-art of the multicalibration techniques, showing the research gaps that exist in that domain and how the proposed method bridges them. Furthermore, the authors may be interested considering the following work: Haghtalab, N., Jordan, M., & Zhao, E. (2023). A unifying perspective on multi-calibration: Game dynamics for multi-objective learning. Advances in Neural Information Processing Systems, 36, 72464-72506.", "essential_references_not_discussed": "We consider the following works to be relevant to the manuscript: (a) Gohar, U., & Cheng, L. (2023). A survey on intersectional fairness in machine learning: Notions, mitigation, and challenges. arXiv preprint arXiv:2305.06969.; (b) Silva Filho, T., Song, H., Perello-Nieto, M., Santos-Rodriguez, R., Kull, M., & Flach, P. (2023). Classifier calibration: a survey on how to assess and improve predicted class probabilities. Machine Learning, 112(9), 3211-3260.; and (c) Toccaceli, P. (2021). Conformal and Venn Predictors for large, imbalanced and sparse chemoinformatics data (Doctoral dissertation, Royal Holloway, University of London).", "other_strengths_and_weaknesses": "We consider the paper to be clearly structured and address a relevant problem: providing Venn multicalibration guarantees. The authors made a great effort in providing theoretical demonstrations for their claims and to show how the Venn calibration relates to conformal prediction in multicalibration settings. Nevertheless, the experimental part of the paper is weak on the multicalibration aspect - one of the main contributions of the paper - an should be improved. Furthermore, the related work is weak considering that the main contribution refers to a novel method for multicalibration, but not many works and state-of-the-art from that domain are described.", "other_comments_or_suggestions": "(1) - What do the bolded results mean in the results tables? Why do we bolden results just for certain metrics? Please indicate with an arrow at the header, whether higher/lower results are better.\n\n(2) - Table 2: align values to the right, so that differences in magnitude become evident.\n\n(3) - Figure 1: we encourage the authors to provide the prediction bands of additional methods in order to enable a visual comparison between them and understand, in perspective, the goodness of the proposed method.", "questions_for_authors": "(1)- While the authors consider several datasets that have been used in reputed works related to conformal predictions, we would appreciate it if they could ground their choice from the subpopulations perspective. The fact that the datasets present subpopulations is key to their experiments for multicalibration and datasets failing to satisfy that characteristic should be excluded from the multicalibration experiments. \n\n(2)- We would appreciate it if the authors would justify their choice regarding baseline methods, to understand why these are relevant to this particular experiments. In particular, we miss comparisons against multicalibration techniques. While the authors reference some of these works among the cited literature, they do not consider such methods as baselines (e.g., Hébert-Johnson, U., Kim, M., Reingold, O., & Rothblum, G. (2018, July). Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning (pp. 1939-1948). PMLR., or Deng, Z., Dwork, C., & Zhang, L. (2023). Happymap: A generalized multi-calibration method. arXiv preprint arXiv:2303.04379.) \n\n(3)- The authors evaluated the performance of the proposed method against the baselines based on three metrics. We would appreciate it if the authors would describe what aspects need to be assessed to guarantee the quality of the calibration and what metrics best assess those aspects. Furthermore, we would appreciate some insights into commonly used metrics to assess the general calibration and multicalibration scenarios so that they can be used as a reference when comparing to other works from this domain.\n\n(4)- The authors did not perform any assessment on whether the results obtained are statistically significantly better than the baseline approaches. We suggest they perform such assessment.\n\n(5)- While multicalibration requires a calibrator to be calibrated across subpopulations, the authors fail to identify subpopulations in each of the proposed datasets. We consider this to be a critical issue to provide insights regarding the quality of calibration for each of those subpopulations.\n\n(6)- The related work mostly focuses on Venn and Venn-Abers calibration and their relationship to conformal predition, while the main contribution of the paper is Venn multicalibration. Therefore, we consider that the related work must be enhanced to introduce the reader to the state-of-the-art of the multicalibration techniques, showing the research gaps that exist in that domain and how the proposed method bridges them.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ohzaV8ZsIF", "reviewer": "Reviewer_dpJ8", "summary": "This paper introduces a unified framework for Venn and Venn-Abers calibration, generalizing Venn calibration to hold with respect to arbitrary given loss functions. Unlike point calibrators (e.g., histogram binning, isotonic regression), which map predictions to a single calibrated value, Venn calibration constructs prediction sets that are guaranteed to contain at least one perfectly calibrated prediction in finite samples. The authors show how to set up a Venn calibrator for any loss to produce prediction sets with marginal and conditional calibration guarantees (where here the word \"conditional\" refers to conditioning on the calibration set). The marginal guarantees hold in finite samples, while the conditional guarantees hold in the large sample regime. In particular, using isotonic regression as the point calibrator underlying Venn calibration, the Venn-Abers predictor for general losses is obtained. The authors also propose Venn multicalibration, ensuring calibration across a given family subpopulations. \n\nFor quantile regression (where the loss is chosen to be the pinball loss), they show that Venn calibration aligns with conformal prediction, achieving quantile-conditional coverage, and that multicalibrated conformal prediction is a special case of Venn multicalibration --- thus encompassing some existing methods. In addition, several experiments are provided --- for regular multicalibration (i.e., for Brier score/L_2 loss) and for conformal multicalibration (i.e., for the pinball loss) that verify that these methods are efficiently implementable (at least for finite label spaces) and that their theoretical guarantees lead to reasonable calibration rates in practice.\n\n#######\nUpdate after rebuttal:\n\nI have read the authors' response. It sufficiently addresses my questions, and I therefore keep my original score. I have also read the discussion with the other reviewers, and I appreciate the further future updates proposed by the authors, in particular the addition/refinement of experiments in the empirical part of the paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful comments. \n\n- Thank you for these thoughtful suggestions. We will add clarification on how the Sherman–Morrison approach can be used to efficiently implement the algorithm. We appreciate the request for more detail on the case of infinite $\\mathcal{Y}$, and will revise the relevant sections to more formally explain how analyzing extreme values of $y$ can suffice to determine the range of the Venn prediction set. We also agree that it would be helpful to situate our generalization of calibration within the broader context of elicitable properties. In the revised introduction, we will add background on this connection and clarify how calibration for general losses relates to elicitable properties.\n\n- We will add further details on the computational and implementation aspects of our approach, including how to efficiently handle infinite $\\mathcal{Y}$ and how discretizing the model output can be used to approximate Venn–Abers calibration effectively.", "claims_and_evidence": "Yes, both theoretical and empirical claims are clearly supported in the paper.", "methods_and_evaluation_criteria": "The datasets make sense, having been derived e.g. from prior research on conformal prediction; the evaluation criteria based on calibration are also correct.", "theoretical_claims": "I read all of the proofs in the appendix moderately carefully, and believe them to be generally correct (up to a few technical details that weren't exhaustively checked). (The one instance of a \"typo\" is where the change-of-variables formula is omitted in line 690 in the Supplementary material.)", "experimental_designs_or_analyses": "Yes, the experimental designs are simple and sound.", "relation_to_broader_scientific_literature": "This work provides a clear generalization of preceding work on calibration and multicalibration, extending so-called Venn and Venn-Abers predictors, which originally worked for the calibrated mean setting (that corresponds to L2 loss) to arbitrary well-behaved losses. Each loss induces its own notion of calibration, and in particular for L2 and pinball loss, the Venn and Venn-Abers procedures (and their respective contextual strengthenings) give rise to mean and conformal calibration and multicalibration algorithms similar (but sometimes different) than the ones which have been obtained in prior work.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "As mentioned before, the strength of the paper is that it usefully generalizes previous fundamental set-based algorithms for calibration. While the formulation of these extensions to arbitrary loss functions is natural and appears straightforward, but the proofs for some of the properties of the generalized algorithms derived in this paper are not straightforward and require some care. E.g., conditions on underlying point calibrators for Venn calibration must be established, and verified for isotonic regression to give rise to Venn-Abers; and the conditional calibration Theorem 3.2 is nontrivial. \n\nThe experiments are relatively rudimentary, including few or outdated baselines (such as conformalized quantile regression on the conformal prediction end or one uncalibrated and one group calibrated predictor on the mean calibration end), which is the main weakness; however, viewing this paper as mostly theoretical, I don't consider this to be a big flaw.", "other_comments_or_suggestions": "Several points could use, I think, some further elaboration. \n\nFirst, could you comment on the Sherman-Morrison approach in the context of the implementation of the multicalibration algorithm?\nSecond, in a similar vein, when the case of infinite Y is mentioned in several instances, it is suggested that looking at the extreme values of y will help --- elaborating on this statement somewhat more formally would increase clarity.\nThird, to provide context for the reader as to the extension of calibration to general losses, it may be helpful to elaborate on this in the introduction by placing this in the context of calibration for general elicitable properties (of which means and quantiles are examples). E.g. as observed in the cited paper Statistical Scope of Multicalibration, this relationship is tight (and they give point multicalibrators for all well-behaved losses in parallel to how Venn calibration is generalized here).", "questions_for_authors": "Other than the above mentioned concern that the empirics are not very extensive, I don't have major complaints. A substantively strengthened empirical section (with more baselines, more nonconformity scores, a clear discussion of the differences of the implementation details to existing multicalibration methods, and some further substantiation of the practical feasibility of these methods for infinite Y) would further boost my evaluation of this paper, but that is not strictly required.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "83CLwTXIhr", "reviewer": "Reviewer_jn2h", "summary": "This paper proposes  Venn and Venn-Abers Calibration defined as connected to the loss function. First, the isotonic regression and quantile losses are examined for the marginal calibration. Furthermore, conditional calibration is discussed. There are a series of theoretical results for the proposed algorithms. Some experiments show the relative superiority of the proposed algorithm.\n\n## update after rebuttal", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1: By augmenting the dataset with all possible imputed outcomes for the test point whose outcome we wish to predict we are able to convert a point prediction into set prediction, where the width of this set captures epistemic uncertainty in the calibration process. This augmentation approach is the workhorse of the finite-sample distribution-free calibration guarantees of the original Venn-Abers calibration and conformal prediction procedures of Vovk and similarly is a crucial component of our algorithms.  \n\nQ2: The proposed algorithm applies to any smooth, bounded loss function, including standard choices such as squared error loss and quantile loss. It also accommodates more specialized losses, such as those used in missing data settings, as well as losses tailored to estimating conditional functionals like the conditional average treatment effect or the conditional relative risk, as discussed in several of our cited works. We will include additional examples of representative loss functions in the revised manuscript to clarify the range of settings where our method applies.", "claims_and_evidence": "Calibration is achieved by the post-processing type learning combined with augmentation. The theries seems sound and empirical results looks better.", "methods_and_evaluation_criteria": "The proposed algorithm looks sound, and the metrics are based on the proposed metrics.\nIf the authors consider other metrics used in the conventional metrics, such as the ECE (Guo et al. 2017), the performance can be compared to the conventional ones.", "theoretical_claims": "It is nice to present the series of theorems to validate the proposed algorithms.", "experimental_designs_or_analyses": "The experiments are limited, in my opinion, since some cases in theorems are not addressed thoroughly. For example, using histogram binning is not examined.  The details of datasets, such as the sizes, are not provided.", "relation_to_broader_scientific_literature": "This study is closely related to the reliability or trust AI.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Positive: The theoretical validations can be strong points, and the definition of calibration is general and has potential.\n\nnegative: The applications and comparisons with other definitions are limited.", "other_comments_or_suggestions": "None", "questions_for_authors": "Q1: Let me know the merits or advantages of using augmented data in the proposed alg.\nQ2: What are the representative losses for the proposed algorithm? Can you provide the ten of loss functions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}]

Author rebuttal:

Meta-review: The submission extends Venn calibration from the multi-class setting to arbitrary prediction tasks, outputting a set of probabilistic predictors with the guarantee that at least one of them is calibrated.  This is an important topic, related to conformal prediction.  The claimed contribution is well placed, and supported primarily by theoretical analysis and a few empirical studies.  The reviewers were unanimous in their opinion that the submission be accepted.
Decision: Accept (poster)