Split conformal classification with unsupervised calibration
Authors: Santiago Mazuelas
Venue: NeurIPS 2025 poster ()
Keywords: conformal prediction
performance guarantees
conformal classification
unsupervised split conformal prediction
Primary area: theory
TL;DR: This paper proposes an approach for split conformal prediction with unsupervised calibration samples. Theoretical and experimental results show that the presented methods can achieve performance comparable to that with supervised calibration

Abstract: Methods for split conformal prediction leverage calibration samples to transform any prediction rule into a set-prediction rule that complies with a target coverage probability. Existing methods provide remarkably strong performance guarantees with minimal computational costs. However, they require the use calibration samples composed by labeled examples different to those used for training. This requirement can be highly inconvenient, as it prevents the use of all labeled examples for training and may require acquiring additional labels solely for calibration. This paper presents an effective methodology for split conformal prediction with unsupervised calibration for classification tasks. In the proposed approach, set-prediction rules are obtained using unsupervised calibration samples together with supervised training samples previously used to learn the classification rule. Theoretical and experimental results show that the presented methods can achieve performance comparable to that with supervised calibration, at the expenses of a moderate degradation in performance guarantees and computational efficiency.

Split Conformal Classification with
Unsupervised Calibration
Santiago Mazuelas
(CAM-Basqqus Center for Applied Mathematics and IKERBASQUE-Baspe Foundation for Science Bilbao, Spain
smazueelas@bcamathhoom
Abstract
Methods for split conformal prediction leverage calibration samples to transform any prediction rule into a set-prediction rule that complies with target coverage probability. Existing methods provide remarkably strong performance guarantees with minimal computational costs. However, they require the use calibration sam- ples composed by labeled examples different to those used for training. This requirement can be highly inconvenient, as it prevents the use of all labeled ex- amples for training and may require acquiring additional labels solely for calibra- tion. This paper presents effective methodology for split conformal prediction with unsupervised calibration for classification tasks. In the proposed approach, set-prediction rules are obtained using unsupervised calibration samples together with supervised training samples previously used to learn the classification rule. Theoretical and experimental results show that the presented methods can achieve performance comparable to that with supervised calibration, at the expenses of a moderate degradation in performance guarantees and computational efficiency.
Introduction
Conformal prediction methods can significantly increase the reliability of machine learning tech- niques by providing prediction sets that contain the true response (class) with coverage probability that can be chosen in advance (see e.g., (H3).. .. In particular, methods for split (aka inductive) conformal prediction 2 are particularly convenient since they can transform any prediction rule (possibly highly unreliable) into set eet-prddiction rule that complies with a target coverage probabil- ity. In these methods. the set- prediiciiiion rule is obtained using fresh of examples referred as calibration samples. Existing methods for split conformal prediction provide remarkably strong per- formance guarantees with minimal computational costs. For general data distributions, they ensure small coverage gap between the actual and target coverage probabilities. In addition, these methods only require compute an empirical quantile from the calibration samples, which can be carried out with quasilinear complexity and negligible running time in practice. While conformal predic- tion has been developed for both classification and regression tasks, this paper focuses exclusively on classification problems, in line with other works for conformal prediction using reakky-supervised data 6
4
Conventional methods for split conformal prediction require the use supervised calibration samples composed by accurately labeled examples. This requirement forces to either leave aside portion of labeled examples during the training phase or to acquire new labels solely for calibration. Both cases are problematic, the use of fewer samples for training can increase classification error, and the acquisition of new labeled examples is often costly. It is worth highlighting that obtaining new labels after the training phase may be even unfeasible certain practical scenarios, including cases
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Coverage probabilitt
Prediction set sire
1.03
Supervised Calibration
Supervised Calibration
Unsupervised Calibration
Unsupervised Calibration
samples
samples
samples
samples
samples
samples
Figure 1: Coverage probabilities and prediction set sizes over 400 random partitions of "CIFARIO" dataset with target coverage 1 0.9 and number of calibration samples ranging from 100 000. The presented methods with unsupervised calibration achieve performance that only slightly inferior that of conventional methods with supervised calibration (coverage probabilities slightly less centered around 0.9). With both ap- proaches, the coverage gap between the actual and target coverage probabilities decreases with more calibration samples and remains below 0.02 with high probability using few thousand calibration samples.
where labels are protected by privacy regulations correspond future events that not yet observable. Several methods have been recently proposed for situations with weakkl-supervised calibration samples [ These methods utilize calibration samples with noisy partial labels, and show that small coverage gaps can be achieved with a moderated amount of incorrect or missing labels. However, existing methods cannot handle cases with unsupervised calibration where all the calibration samples are unlabeled. In particular, has been shown that set-prediction rules obtained using only unsupervised samples for calibration provide either uninformative unreliable predictions (see Def. 2 and Thm. 3 in [6).
This paper presents effective methods for split conformal prediction with unsupervised calibration samples. In particular, the proposed approach avoids the negative result for ceakly-supervised cali- bration in [6] because the set-prediction rule is obtained leveraging also supervised training samples previously used to learn the classification rule. Theoretical and experimental results show that the presented methods Figure at the expenses of a moderate weakening of the performance guarantees and an affordable increase in computational complexity. The main contributions presented the paper follows.
achieve performance comparable to that with supervised calibration (see
We present split conformal methods that assign label weights to unsupervised calibration sam- ples so that they are statistically indistinguishable from training data. In particular, the methods proposed minimize two-sample nonparametric test statistic given by family of functions.
We provide performance guarantees for the methods presented terms of high-confidence bounds for coverage probabilities. In addition, the coverage gap achieved characterized in terms of a bias-variance trade-off corresponding to the family of functions used.
We detail the methods' implementation using families of functions given by reproducing kernel Hilbert spaces (RKHSs), which result in particularly advantagcous performance guarantees that also serve to select the most adequate kernel.
We experimentally show that the proposed methods can achieve performance comprpaaaaceeommmabbbbbb that with supervised calibration.
Notations: Vectors and matrices denoted by bold lower and upper case letters, respectively (e.g.. v and M); random variables (RVs) are distinguished from instantiations by using capital upright symbols (e.g., Z); N and denote vector (component-wise) inequalities; 1l denotes the indicator function; for an integer f, [4] denotes the set [{] = {1, 2, 2,..., 1); 1, denotes the vector of size t with all components equal to 1; and I, denotes the identity matrix of size t.

---

2 Preliminaries and conventional approach for split conformal prediction
Let 2 = X be the set of instance-label pairs, with X' C. Rd the set of instances (features) and y= (1,2....,. c) the set of labels (classes), (X, Y) be an RV of instance pairs in 2, and 'D be dataset composed by i.i.d. copies of (X, Y). Conformal prediction methods
the dataset 'D to find a set-prediction rule C X + 2 so that prediction sets (C( C 3) have reduced cardinality and often cover the true label (Y E C(X)). In particular, such methods aim to ensure a coverage probability near target value - or (e.g.. = 0.1).
The most common approach for conformal prediction is known as split conformal prediction. In this approach, the dataset is randomly split into two groups D = Duain U Deat the m samples Dusin = {X; [E) are referred to as training (or pretraining) samples, and the remaining n samples Deat = (X,, Hi) are referred to as calibration samples. Then, prediction sets are obtained as shown in Aggoithh[[]eeoov (see e.g., (2).
Algorithm Supervised split conformal prediction
Input: Training samples ((x, Yi) he[m) labeled calibration samples [(X,, Y:) ke(u). and coverage 1
1: Using the training samples, construct a conformal score function 2 x y + K
2: Compute the conformal scores of the calibration samples (5(X,, Y.))
3: Compute the conformal quantile q = Quantile [[S(X,, Yi), 1/m))ae
a) 1/m))
4: For any test instance X, return the prediction set C(X) (y E y S(X.y) S 5
The m training samples are used learn classification rule that determines conformal score S X' x y - R assessing the plausibility of different instance-label pairs. For instance, the confor- mal score can be defined as S(X, Y) - (Y where ý (YIX) X is the probability estimate (e.g.. softmax output) assigned to label Y by the classification rule at instance (see 2 for other types of conformal scores for classification tasks). Subsequently, the calibration samples are used to ob- tain score values and the corresponding conformal quantile q in Step 3 of Algortihm Specifically, the expression Quantile (( pt) pi)eee 3) denotes the S-quantile of values S1, .2,,.., E E with probabilities p1. P2. ............. P
Pr E [0, 1]. Exegg Ps 1, that is
Quantile (:) 3) = inf {a E I::
S 50) EpIHS.s0)) 23.
(1)
iE
Then, the set-prediction rule is directly obtained using the score S and the conformal quantile q.
The conventional approach for split conformal prediction provides remarkably strong performance guarantees for the resulting prediction sets [1. Specifically, for any data distribution, type of conformal score, and target coverage a, the set-prediction rule C from Algorithm [ satisfies
1
a P(Y E(()) 31 a
(2)
n ++1
log (2/0) < 2n
1
log (2/8)
1 0
P(Y E C(X)) < a
w.p. 2 (3)
n
2n
These performance guarantees satisfied with wide generality. The lower bounds for the marginal coverage and the (training) conditional coverage in (2) and (3). respectively, do not require addi- tional assumptions. As described above, we assume that training, calibration, and test samples are randomly drawn from the same data distribution. The lower bound in (2) does not even require the independence of samples and is valid also if samples are exchangeable. The upper bounds in (2) and (3) additionally require that the score values are distinct with probability one, which can be easily achieved for instance by adding a negligible amount of noise (2]. The bounds for caining-conditionll
training conditional coverage in (3) are arguably more relevant in a practical sense: in a given appli-
cation, there only one dataset D. and the achieved coverage corresponds
specific realization
of P(Y E C(X)DD), rather than its expected value (P E CX)).
Split conformal prediction has been shown to be extremely useful in practice since it allows to obtain reliable set-prediction rules from general prediction rules (possibly highly unreliable) by using an additional set of calibration samples. However, existing methods require the use supervised calibration samples, leading to additional labeling costs. In the following, we describe the proposed approach for split conformal prediction that uses unsupervised calibration samples.
3

---

3 Split conformal prediction with unsupervised calibration samples
In the proposed approach, the labels of the calibration samples are not available, and prediction sets are obtained as shown in Algorithm@2] beloo.
Algorithm 2 Split conformal prediction with unsupervised calibration
Input: Training samples {(X,, Ye) unlabeled calibration samples {X4)ie)n). and coverage 1 - a
1: Using the training samples, construct a conformal score function S X x y +R R
2: Compute the conformal scores of the calibration instances for all possible labels {S(X), (0..))E))
3: Obtain label weights (v) (v) ((.)))))) xy for the calibration instances
4: Compute the conformal quantile q = Quantile ( [[S(X., v). us (v)/n)) (eae (1 1/n))
5: For any test instance return prediction set C(X) {v E y: 9) S 5
The main difference in the proposed approach with respect to conventional split conformal prediction consists of Step 3 in Algorithm 2 that obtains label weights for unsupervised calibration samples. Indeed, the conventional approach can be seen as a particular case of Algorithm iin which the label weights correspond to the actual calibration labels, i.e, wy(y) is taken w. (v) I[v Y for any (i, y) E [m] x V.
In the presented methods, the label weights for calibration instances are obtained using the training samples. naive approach would obtain such weights using the labels predicted by a classifica- tion rule h learned using the training samples, i.c., wr(y) taken W; (v) I(y h(X:)) for any (i.y) y) E [n] y.. However, this naive approach only provides acceptable performance in cases where the classification rule is already highly accurate, making conformation prediction somewhat unnec- essary. The following sections present methods that avoid the limitations of such naive approaches and obtain the label weights by solving tractable optimization problem determined by family of functions. The proposed approach can be seen as obtaining labels that result in calibration and training samples that are statistically indistinguishable by two wwo-sample test based on an integral probability metric (IPM). This type of non non-parametric tests can reliably detect statistical differences between sets of samples without requiring any distributional assumption (see e.g., 111
3.1 Label weights minimizing IPMs
Let w (1), w/ (2). w/ (c), .......... wn (x)(c] Te denote label weights for the cali- bration samples, the Step 3 in Algorithm (2) can be carried out by solving the optimization problem
min sup JEF
Σ
(.(v)((X,.))
Σ 8.) 3E(m)
(4)
(i.)))())x>
s.t. w 0, Aw = 1,, Bwbb
where F is a family of functions f: X' since the supremum of convex functions is a convex function [13), and is tractable for common and general families of functions. In particular, using functions in RKHSs, optimization (4) becomes a quadratic program of size ((nc) (see details in Section 4 below), while using Lipschitz functions, optimization 4 becomes a linear program of size (nem), as a consequence of the Kantorovich- Rubinstein duality theorem [14.
The optimization in 4 convex for any family F
Label weights aim describe the probabilities of different labels, and the linear feasible set in encodes quite general prior knowledge for label probabilities. In particular, the matrix A E Rg just encodes the constraints Eyey wr(y)
for i [n], i... A I, & 1 for the matrix Kronecker product. On the other hand, the matrix B E grxne and vector b E I'' can be used to encode other types of prior knowledge about label probabilities. For instance, upper bound L for the expected loss E E(((h(X). Y)} of a classifier h (e.g., its cross-entropy loss) can be used to have the constraint given by b nL E R and
B- [(()(X,,, 1),
c), ((h(2)), 1)....,((((x))...... E R lxne (5)
((((X.).))
Such feasible sets often contain the label weights corresponding to the actual calibration labels, we (v) = TTyy = Yj) for i E [n], y E V, because w* > 0 and Aw" = 1, are clearly achieved, and we have Bw < b as long as the prior knowledge encoded by B and b is reliable.

---

As shown in the following, Algorithmm2) with label weights obtained by 4 can provide theoretical guarantees and practical performance comparable to those achieved by conventional split conformal prediction with supervised calibration samples. The optimization in 4 can be seen finding the label weights for calibration samples that minimize the IPM between probability distributions corresponding to training and calibration samples, where for family of functions F
IPM Q) sup fEF
[ Ee(s]l-
In particular, for families given by RKHSs, IPMs correspond maximum mean discrepancy metries while for families given by Lipschitz functions, IPMs correspond to L1- -.-Wasserstein metrics (see
e.g., 15)
The objective function in denoted as & (w) corresponds to the IPM between the distribution w/n supported on the ne possible instance-label calibration pairs, and the empirical distribution of the m training samples. IPMs between empirical distributions have been used to design non-parametric two-sample tests in which two sets of samples are considered to be statisti- cally different (draw from different distributions) if the IPM between the corresponding empirical distributions large enough [2]. Therefore, the label weights obtained from i can be inter- preted as those making calibration and training samples to be statistically indistinguishable by non- con-paamettric two-sample test. In particular, at the weights w" corresponding to the actual calibra- tion samples the value of (4) is given by the test statistic achieved by two sets of i..d. samples that are actually drawn from the same distribution.
A key methodological difference in the proposed approach is that the training samples are not only used to learn the score function but also to obtain label weights for calibration samples. particular, the methods presented bypass the negative results in [6] for weakly-superviser calibration because the set prediction function is obtained using unlabeled calibration samples and also labeled training samples. This reuse of the training samples may seem doomed to fail since scores and label weights for calibration samples are no longer independent (both depend on the training samples). The fol- lowing briefly describes the rationale that allows the proposed approach to avoid such concerns, Theorem[]below provides the precise performance guarantees achieved by the methods proposed.
Let Ee: : X x y + {0, 1} C R be the function
{c = T(y C(x)) ((S( v) S 5 {0,
(6)
The coverage gap of the set-prediction rule from Algorithm 2 is small as long as the weighted average of function &e at the calibration instances is the expectation of Xe because
P|Y E C(X)) = [{(c} and Σ
w;(y)Xc(X,, v) 1-
vE(M),EY
by definition of te in (6) and ② in the step 4 of Algorithm 2 that
Since the minimization of 4 ensures
Σ w.(y)s(X,,))
-
Σ f(x Y.). VFEF
n
m
ic(m]
prediction sets given by label weights from have small coverage gap as long the family F utilized: 1) can accurately approximate the function Ee at the calibration instances (e.g.. F can interpolate finite sets of points), and 2) ensures the uniform convergence of i.i.d. averages (e.g., FF has reduced Rademacher complexity). This type of analysis for conformal prediction methods is novel and can be of independent interest beyond split conformal prediction with unsupervised calibration.
3.2 Performance guarantees
The following provides performance bounds for the coverage probability of set-prediction rules obtained using the proposed approach in Algorithm [ In particular, such performance guarantees are given in terms of the Rademacher complexity of the family F. and the quantity
D(Ec,F)
inf 1 fef
Σ
xc(X.,v) 5(Xe, v)
iEinl.VE
5

---

that describes the smallest error achieved approximating the function &e with functions in F at the calibration instances. For the next result we denote by RFF the Rademacher complexity of F for 1. i.i.d. samples, and consider general families of real-valued functions with bounded differences, (i.e., If(=) f(=')l S B, for any f E F and 2, E = X' y). The requirement of bounded differences is satisfied by common families including functions in RKHSs given by bounded kernels or Lipschitz functions defined in bounded sets.
Theorem 1. Let w be label weights with objective value in 4
upper bounded by Vop (i.e.,
& (w) < Vop)). For any data distribution, type of conformal score, and target coverage a, the set-prediction rule C from Algorithm 2 satisfies
log (2/5) 2n
P(Y E C(X)DD) 2 1 a G m..m
(8)
with probability at least 1 1 8, for G n... given by
Gh Vap + D(Ec, 2(R. + Ru (F)) BV
(--
(
log (2/8)
(9)
2
In addition, if the values (S(X, are distinct with probability one, we have
P[Y e ((X)[D) 1 a+ 2
log (2/6)
n + G +
(10)
2n
with probability at least 8. 8.
Proof. See Appendix B
The result above presents performance guarantees for the coverage probability of the methods pro- posed comparable to those in (3) for the conventional approach with supervised calibration. The excess coverage gap G in the bounds of Theorem I describes the effectiveness of Step 3 in Algorithm 2 In particular, the term Vap accounts for the objective value obtained by w in ( and small using appropriate optimization algorithms and number of calibration and training samples. For instance, if the feasible set in optimization (4) includes the label weights w" corresponding to the actual calibration labels, the objective value of n.m (w) satisfies
6. " (w) S. Eopt + ((R + Rm)) By ( (=+1) m ) 1og(1/5)
w.p. 2 1
(1I)
for Eapt the optimization error achieved by the algorithm used to solve 4 (see Appendix (oandixx]for for a de- tailed proof). Hence, the term in (9) due the optimization value generally of the same order as the Rademacher complexity of the family. In addition, Theorem[[]heer sshows that the methods proposed do not require solve the optimization problem 44) with high accuracy, as approximate optimiza- tion algorithms increase the bound only by their optimization error copt- For instance optimization errors on the order of 10-3 do not significantly affect the final coverage probability.
The excess in coverage gap achieved using unsupervised calibration is given by the terms D(Ec, FF) and (F) + R., (F) that describe a bias varianae trade-off for the family F. The bias term FF corresponds to the distance between function Xe and the family F at the calibration instances, while the variance term R,, + Ry, (F) accounts for the usage of finite sample sizes. Both terms are low using appropriate family F and sufficient number of samples. The bias term F) can be made arbitrarily small using functions that are Lipschitz or belong to an RKHS given by strictly positive kernel (e.g., Gaussian, Laplacian, polynomial) since both types of functions can interpolate any finite set of points. The variance term R,, (F) + Rm decreases with the sample sizes at rate O Rn -1/2,, + Rm Rm-21/2 using functions in an RKHS with norm bounded by R (see e.g. Chapter 6 in 16)) On the other hand, using R-L-ipschin functions such a rate becomes O(In 1/d + Rm 11/d
that is significantly affected by the instances' dimensionality d.
Theorem I shows that the coverage gap decreases with both the number of calibration samples n and training samples m. Although the total number of training samples available is commonly much larger than that of calibration samples, there not significant benefit in using m > for calibra- tion, and label weights can be obtained using in 4 only subset of the training samples available. The results in the theorem also expose an important limitation in the methods presented since the performance guarantees deteriorate for an increased number of classes [}] = c. Specifically, both

---

bias and variance terms increase with the number of classes, the bias term D F) is given by the average of approximation errors multiplied by [} and the variance term R, (F) + Rm (F) given by the complexity of functions over X x Y that generally increases with |
The performance guarantees shown in Theorem 1 can also be compared with those of the naive approach that labels calibration instances using a classification rule. It is easy to show that for such a naive approach the coverage gap (Err(h) for Err(h) the error probability of the classification rule h used to label the calibration instances, In particular, such a bound for the coverage gap can be obtained by using the results in [9] since Err(h) coincides with the total variation distance between (X. Y) and (X, h.X)). A coverage gap near Err(h) is not acceptable in common scenarios because it would only be small in cases where a highly accurate classifier available, which would commonly defeat the purpose of conformal prediction.
In this section we have described the general approach presented together with the corresponding performance guarantees. As indicated above, kernel-based methods offer an advantageous balance for optimization efficiency and bias-variance trade-off in general scenarios, that the rest of the paper focuses in such type of approaches. In addition, the kernel-based methods provide enhanced performance guarantees that enable effective model selection, as described in the following.
4 Kernel-based implementation
Let H be an RKHS of real-valued functions over 2 = X x ) given by kernel K x - TR. The
optimization problem in (4) using family F= [f E H [| S R) with R = 1 is equivalent to
2 v T w + m
7
min
W
K Kw-
1 m K1m
(12)
nmm
S.t. W z 0, Aw = In Bw = b
where K E Rnnxxee is the kernel matrix corresponding the ne possible instance-label calibration pairs Z1, Zz...., Zne with (i- 1)o+ = (X,,)) for i E [n]. v E V, that is, the (i.j)-th component of Ki is given by Kij = K(Z,, 2j) for i E [ne]] Similarly, K E Rmxm is the kernel matrix corresponding to the training samples Z,, Zz..... Zm with 2. = (X,, Y) for i E [m]. In addi- tion, E Re is the vector with i-th component given by 2/2 Eje(m) K(Z,, 2,) for i E [nc]. The equivalence between (4) and (12 follows as consequence of the dual characterization of the norm in H (see the detailed derivation in Appendix D). The kernel K can be any joint ker- nel over 2 X' V, for instance K can be given by kernel Ko over X' as the separable kernel K ((x, y). (x', v²)) = Ko( [[y = v'} (see (20 for other types of joint kernels). Separable kernels are simple and convenient computationally since they lead to highly sparse kernel matrices.
The usage of a family with other maximum norm R o results in an optimization problem equiv- alent to 112, namely, problem that has the same solution with optimum value multiplied by R. This fact has important consequences because for families of functions F = {f E H. Il S R] the bias/variance trade-off described in Section 3.2 is given by the value of the norm R. Increased values of R result in more general families of functions at the expenses of an increased Rademacher complexity. Therefore, kernel- based methods provide automatic capacity/complexity control: the trade-off for the value of R does not need to be explicitly addressed because the optimization prob- lem solved does not really change with R. Therefore, solution of (22 enjoys the performance guarantees of Theorem cooresponding to the value of R that achieves the best bias/variance trade- off. In particular, kernel-based methods result in the following enhanced performance guarantees. Theorem 2. Let H be an RKHS given by kernel K over 2 X x y with 0 S K(z, z²) I x² V2, x' E Z, and w be solution of optimization problem 112 with feasible set that includes the label weights w corresponding to the actual calibration labels. For any data distribution, type of conformal score, and target coverage - a, the set-prediction rule C from Algorithm 2 satisfies
log (2/8) 2n
P(Y E C(X))D) 2 1 a G.K C..m
(13)
with probability at least 8,
8, for GK G... given by
G -min- JEH n iEin].VEy
Σ
[x) s(Xt, + 2xx11
Vlo((2/8)
I
1
1f (14)
n
m
7

---

In addition, if the values
are distinct with probability one, we have
2 G.K
log (2/6)
P(Y E (( < a + n +
+
nmm
+
2n
(15)
with probability at least 8. 8.
Proof. See Appendix C
The result above shows that the kernel-based approach in 12) yields an excess coverage gap given by the best bias-variance trade-off in the corresponding RKHS. This best trade-off is described by the term G in (4) as combination of the approximation error and the RKHS norm weighted by the number of samples used. For simplicity, Theorem stated for the case where w is an exact solution of (12) and w* is included in the feasible set. A similar result holds in general cases, by including the term Vopt in the expression of G to account for the optimization value attained, as in [
For RKHSs given by strictly positive definite kernels, Theorem 2 shows that the coverage gap is O(M /I/n+ 1/m) where .M denotes the minimum norm of interpolators of Xc at the calibration instances. More generally, the excess coverage gap can be bounded as Gk,, CE + 2x(1 + v /log(2/0)) /I/n 1/m where M2 denotes the minimum norm of e-approximations of & at the calibration instances, that
M min (Xc((x, v) J(Xi, v) Se, i [m), SEH
(16)
The magnitude of the minimum norm M (or M2) depends the smoothness of the function Xe at the calibration instances and on how well the selected kernel is adapted to such values. The smoothness of Xç determined by that of the conformal score function S(X, Y) defined by the classification rule used. Such a function may be highly non-smooth at the training instances used to learn the classification rule. However, for classifiers that generalize well, the conformal score is expected to be fairly smooth at the calibration instances, which are drawn independently of the training samples. Cases in which the conformal score is highly non-smooth across the instance space are possible but of reduced practical relevance, as such conformal scores would be largely uninformative.
The bounds in Theorem@not only provide theoretical guarantees but can also be used in practice for kernel selection. In particular, kernel can be chosen from candidate set (e.g.. multiple choices of bandwidth for a Gaussian kernel) as the one achieving the smallest minimum norm interpolation (or e-approximation). The minimum norm of interpolating functions can be efficiently computed using standard properties of RKHSs (see e.g., (1I). Specifically, for kernel K the minimum norm of interpolators for Xę at the calibration instances is given by 7 for y that solves the linear system Kr = u. where the kernel matrix K and vector u are given by Ki, = K (Z,, 2j) and = (Z.).. for i [nc]. Notice also that the preprocessing step that selects the most suitable kernel over candidates only change the term (2/() 5) in the bounds of Theorem 2 to the term log(2s/5). as direct consequence of the union bound.
Algorithm B details the implementation of the proposed kernel-based methods to obtain label weights for the calibration instances. The kernel selection process requires to solve linear sys- tems of equations of size nc so that it has time complexity O O(sn3e" (.)) Then, label weights are obtained by solving quadratic program with nc variables and n linear constraints. Highly accurate solutions of such problems can be obtained using interior point methods with complexity per iteration (n"²c²) due to solving a linear system (see Chapter 16 in (22). These methods allow to efficiently solve the quadratic program for number classes e and unlabeled calibration instances in the order of tens and thousands, respectively. For cases with a higher number of classes or cal- ibration samples, first-order methods can result in efficient implementations since their complexity per iteration is D(n2c²) due a matrix- multiplication (see Chapter 16 in (22)) The memory complexity of AlgorithmBjis Bis (n²²²) corresponding to the storage of kernel matrix. Furthermore, the computational complexity of Algorithm [ can be significantly reduced taking into account the common sparsity of the matrices involved. The matrix A corresponding to the linear equality con- straints always highly sparse (ratio of nonzero values 1/n), and the kernel matrix K also highly sparse using separable kernels (ratio of nonzero values 1/c²). Appendix E shows that Algorithm

---

using interior point methods achieves running times ranging from tens to hundreds of seconds for cases with up to 10 classes and up 3,000 calibration samples.
Algorithm 3 famellbased method to obtain label weights for calibration instances
Input:
Unsupervised calibration samples (en)) training samples ((X,, Y.)) Kernels K0),, k(2) ..... k(s), matrix and vector for inequality constraints B and b Output: Label weights (v), i [m]. E
1:
Z( Det () for i [n]. y V. 2i
(Xi, Y:) for i E [m]
Kernel selection
2: Compute rough approximate qo of the quantile using Algorithm 2 with the naive approach given by label weights { (v) = [yy = h{)))}
3: Compute vector E R given by Iu( = 1[ S(z)) - qo } for i E [rxc]
4: for t [s] do
Compute kernel matrix k(t) E ge given by K K k0 2s) for i,j E [nc]]
6:
7(1) <- solution K (1)))))))
7: end for
< arg min(u' 70) (E(s)
Label weights computation
9: K + k(") A In @ 1
10: Compute vector v IR' given by v = Eje(m) K x(t)),,, Zz) for E [nc]
11: w solution of
2
min Kw
m
s.t. w = Aw 1., Bw 3 b
5 Numerical results
The experiments assess the performance obtained by the proposed approach for split confor- mal prediction with unsupervised classification using common benchmark datasets. The cov- erage probabilities and prediction set sizes are compared with those provided by the conven- tional approach that uses supervised calibration samples and by the naive approach that uses label predictions for calibration samples. Due to the amount of theoretical results presented, this section is necessarily concise. The code implementing the methods presented and re- producing the experiments can be found at wtt.:pppiiiiooeuuuur-------
con///achineeeannngggeeeee The supplementary materials provide implementation details and additional results in Appendix F including running time assessments, as well as results for different target coverages and types of conformal scores.
Unsupervised-conf
For each dataset, 400 random realizations are generated by randomly partitioning the samples in training, calibration, and test sets. The training samples are used to learn classification rules: ran- dom forests for tabular datasets and neural networks for image datasets (fine-tuned Resnet50 for "CIFAR10" and 'ImageNet1O" datasets). The results in the main paper use the adaptive conformal score proposed in [2] and the Appendix[[rreporr results with the conformal score directly given by probability estimates [.. Set-prediction rules are obtained from the scoring functions using n calibration samples for multiple values of n, and coverage probabilities and prediction sets sizes are then computed using the test samples. The presented methods are implemented using Algorithm with label weights obtained by Algorithmßusing samples used to learn the classification rule, and a Gaussian kernel selected from a set given by 10 candidate bandwidth (scale) parameters. Full implementation details provided in Appendix
training samples randomly drawn from the
Table shows the coverage probability and prediction set size obtained in the 9 datasets using 1, 000 calibration samples for target coverage of 1 - a 0.9. The results in the table indicate that the performance of the methods presented only slightly inferior that of conventional methods with supervised calibration. In accordance with the discussion in Section 3.2 regarding the weakened guarantees scenarios with many classes, 'Letter' -which includes 26 classes- the only dataset showing significantly poorer performance. The table also shows that the naive approach

---

Table 1: Coverage probability and prediction size for conventional approach with supervised calibration
( ('Supervised"), proposed approach with unsupervised calibration (Unsupervised") ) and naive unsupervised approach ( ("Unsup. Naive'). ). Results are shown as: mean (interquartile interval), and correspond to 1-a = 0.9.
Coverage probability Unsupervised
Prediction set size Unsupervised
Dataset
Supervised
Unsup. Naive
Supervised
Drybean
0.90 10.
0.91 (0.90,0.91)
0.84 (5,85,0855
1.23 (1.20.1.25)
1,25 (1.22,1.27)
Forestcov
0.90 (0.89,0.91)
0.89 (0.89,0.90)
0.62 (0.61,0.63)
1.90 (1.87.1994)
1.87 (1885,1889)
Satellite
0.90 (0.89,0.91)
0.90 (0.89.0.91)
0.84 (0.83,0.85)
1.45 (1.42,1.48)
1.44 (1.41,1.48)
USPS
0,90 (0.89,0.91)
0.90 (0.89.0.91)
0.88 (0.87,0.89)
1.11 (1.09.1.13)
1.11 (1.09,1.14)
MNIST
0.90 (0.89,0.91)
0.90 (0.90.0.91)
0.86 (0.85.0.87)
(1.16.1.111
1.20 (1.18,1.23)
Fashion
0.90 (0.89,0.91)
0.91 (0.90.0.91)
0.80 (0.79.0.81)
1.43 (1.39.1.47)
1.45 (1.42.1.48)
CIFARIO
0.90 (0.89,0.91)
0.91 (0.90.0.92)
0.88 (0.87.0.89)
1.00 (0.98.1.0))
1.01 (0.99,1.02)
Imagnet
0.90 (0.89.0.91)
0.08,0099..009
0.86 (0.85,0.87)
1.65 (1.66,1.70)
1.62 (1.57,1.68)
Letter
0,90 (0.89.0.1)))
0.85 (0.84.0.87)
0.69 (0.68.0.71)
5.58 (5.24.5.90)
4.14 (3.80,4.48)
0.1
0.09
0.07
Avcrage covenge gap
Average coverage gap
0.04
0.00
0.00
-8-
Supervised Calibration
Supervised C Calibration
0.01
Unsupervised Calibration
Unsipervised Calibrution
Unsup Cal. Naive
Unsup. Cal. Naive
10
1000
100
1000
Number calibration samples
Number of calibeation samples i
(a) 'CIFAR10' Dataset
(b) 'Drhhean' Dataset
Figure 2: Decrease of average coverage gap with the number of calibration samples.
can only provide acceptable performance cases where the learned classification rule is highly accurate (e.g.. the classification error in 'CIFAR10' is 4%). Figure 2 shows the average coverage gap (B|[1- 1 a - P[Y E C(X)DH} with a = 0.1) obtained with different number of calibration samples. The results in the figure exhibit that coverage gaps smaller than 0.015 can be obtained with few thousand unsupervised calibration samples. In accordance with the theoretical results in Section [.2] the coverage gap decreases with the number of unsupervised calibration samples comparably to cases with supervised calibration.
6 Conclusion
The paper presents methods for split conformal classification with unsupervised calibration. In the proposed approach, label weights for calibration samples are obtained so that training and calibration samples become statistically indistinguishable by a non-parametric two-sample test. The theoretical and experimental results show that the methods presented can achieve performance comparable to that with supervised calibration, at the expenses of a moderate degradation in performance guaran- tees and computational efficiency. The methodology presented can lead to methods that remove the need to acquire labeled examples at the calibration stage, thus making conformal prediction more cost-efficient in general and viable even when new labels cannot be obtained after training.
The proposed methodology is broadly effective but does not scale well with the num- ber of classes, as discussed in the theoretical and experimental results. As shown in Sections and and 4 the excess coverage gap in the methods presented decreases at a rate O(1/ + 1//m) in general scenarios, but the constants can be large if the conformal score used is highly non-smooth at the calibration samples. Such cases are rare since the score function is learned without calibration sam- ples, and globally non- smooth scores are largely uninformative in the first place. The other main limitation of the methods is a significantly higher computational cost compared to conventional split conformal methods, which only require computing one quantile. This drawback is of limited rele- vance in practice since the computational cost remains small relative to typical learning processes.
Limitations:
10

---

Acknowledgements
Funding in direct support of this work has been provided by project PID2022-1330633BBBBB funded by MCIN/AEI/1O/ 13039/50 10001 1033 and the European Union "NextGencrationEU"PPRRT 000. 13039/501 10001 1033
BCAM Severo Ochoa accreditation funded by the Ministry of Science and Innovation (Spain), and program BERC-2022-2025 funded by the Basque Government.
References
[1] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world. Springer, New York, NY, 2005.
[2] Anastasios N. Angelopoulos and Stephen Bates. Conformal prediction: A gentle introduction. Foundations and Trends in Machine Learning. (6(4):494-591,200
[3] Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution-fres predictive inference for regression. Journal of the American Statistical As- sociation, 1194523):
[4] Maxime Cauchois, Suyash Gupta, and John C. Duchi. Knowing what you know: valid and validated confidence sets in multiclass and multilahel prediction. Journal of Machine Learning Research, 22(81):1 1-2, 2021.
[5] Matteo Sesia, Y X Rachel Wang, and Xin Tong. Adaptive conformal classification with noisy labels. Journal of the Royal Statistical Society Series B: Statistical Methodology, Dec 2024.
[6] Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C. Duchi. Predictive inference with weak supervision. Journal of Machine Learning Research, 25 11):118)115 2024.
[7] Bat-Sheva Einbinder, Shai Feldman, Stephen Bates, Anastasios N. Angelopoulos, Asaf Gendler, and Yaniv Romano. Label noise robustness of conformal prediction. Journal of Machine Learning Research, 25(328):1 2024.
2024.
[8] Shai Feldman and Yaniv Romano. Robust conformal prediction using privileged information. In Advances in Neural Information Processing Systems, volume 37, pages 1 11781--11752. 2024.
[9] Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncer- tainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2021.
[10] Vladimir Vovk. Conditional validity of inductive conformal predictors. In Proceedings of the Asian Conference on Machine Learning, volume 25, pages 475-490, 2012.
[11] Arthur Gretton, Karsten M. Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(25):723-733, 2012.
[12] Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert R. G. Lanckriet. On the empirical estimation of integral probability metrics. Electronic Journal of Statistics, 6:1550- 1599, 2012.
[13) Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, New York, NY, USA, 2004.
[14] Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc.. Providence, Rhode Island, 2021.
[15] Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2): 1997.
[16] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learn- ing. MIT press, Cambridge, MA, second edition, 2018.
[17] Jie Wang, Rui Gao, and Yao Xie. Two-sample test using projected Wasserstein distance. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 3320-3325, 2021. [18] Ulrike von Luxburg and Olivier Bousquet. Distance-based classification with Lipschitz func- tions. Journal of Machine Learning Research, 5(Jun):69-665,, 2000,

---

[19] Rina Foygel Barber, Emmanuel J. Candès, Aaditya Ramdas, and Ryan J. Tibshirani. Confor- mal prediction beyond exchangeability. The Annals of Statistics, 51(2):816 845, 2023.
[20] Mauricio A. Alvarez, Lorenzo Rosasco, and Neil D. Lawrence. Kernels for vector-valued functions: A review. Foundations and Trends in Machine Learning, 4(3):195-266, 2012.
[21] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. Proceedings of the 35th International Conference on Machine Learning, 2018.
[22] Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer, New York, NY, 2006.
[23] Dheeru Dua and Casey Graff. UCI Machine Learning Repository, 2017.
[24] Tom Hope, Oscar Chang, Ehsan Amid, Yoni Halpern, Zachary Nado, Douglas Eck, and Rif A. Saurous. TensorFlow Datasets: A collection of ready-to-use datasets. https: :/wws.
tensorflow.org wttp:oww.wwwddaasssssssssssssss. datasets, 2022.
12

---

Appendices
A Auxiliary lemmas
Lemma 1. For e [n), let (Xi, Y:) be an instance-label pair in X x 3/ and wi((1,, (2:).... ....,,................... wi(() be positive label weights that add to one. I is the quantile
Quantile (X,, y). (esei)o a) 1/n))
(17)
for some a E [0, 11. and given by
E
1 Σ ( Yi)
we w;(() VE(N),Ey
Σ
72 iE(n]
for the function Xe defined in (6. Then, have
q 2 ( 1/m))
(18)
In addition, if the values (15)))))))) are distinct, have
i S Quantile (( K), (n (1 1/(m+11111111 +B/ (1)(+1/))))) 1/n)). (19)
Proof. From the definition of q in 17 we have
(n + 1)(1 a)
w.(y))&c(x.,))
Σ
() 5
(20)
T3
VE
then, directly get
Te(X, Yi)
HS(X, Y)) <
71
(n 1)(1
+
nE n+I
(V) <
(21)
vey
that gives 18)
If the values (8(Xi,))) (5.,):)) ynj are distinct, by the definition of ② in 17 we have
(x(.))e(X..))) - Σ
w((v)I(((x..))) 2 9 kE(m),NE>
(n 1)
1
(22)
n
n
iE E
because < wz) < 1 for any y E V e [n]. Then, analogously the previous case we get
Xc(X,, Y2)
ISS(,, Y2) <
(23)
(n + 1)(1 + #+1
(n+ 1)(1
R+1
m+1
(24)
n
m
that together with 21 gives 19
Lemma 2. Let w [w] (1), wi (2) ... w1 (c), w22 ..... wn (c)] E Re be label weights for the
calibration samples that satisfy $b n. (w) Vapa. and F be family of real-valued functions with
bounded differences, i.c., 1f(z) f(x')l < B, for any f E F and 2, E Z = = Y.
If E is the RV
E
Σ Xc,X,, Y.) Y.) iE|n]
Σ
(x())
iEinl.vyy
13

---

Then, with probability at least 8 we have
1 m
log(1/6) 2
E I Vopt + D(Ec, F) ( + Rm(()) + BV
(25)
Let 7t be the RKHS given by kernel K that satisfies 0 v 22, I n²² for any 2, E Z. w is solution of (4) using the family FR = {f H: Il I R}. and the weights w corresponding to
the actual calibration labels are included in the feasible set of (4), we have
I m
E S FRI,, 2x(11 vlog(1/6) R
for all R > 0
(26)
with probability at least 8.
Proof. For any f E F we have
E = Σ
Ic(X, Y.) -- Σ
wi(v) w)
n [E(m]
Σ
(1w== - w. (v))
<
Σ
(Iyy= (x) f(x,, v))
(27)
n yY
L
Σ
u
(28)
vEiN),EY
We bound separately the two terms
27 and
28
For
27
we directly have
EL Σ
(ul - Y,J - (x))) (Fc)))))))((...)))))))))))) v) f(X., v))
1
Σ
(xc(X,,)) f(X,,
iEIn).BE>
(29)
because < wi( I 1 for any [n] and y E V. For 28 we have
L Σ
(1ly= = Y f(X,,
1
Σ
fXi,, Y.) - m
Σ
f(Xi,
Σ
f(X,, Y.)
Σ wi(r) v)
m
iE(m)
VE [m]
EE mm)
vE(n),Ey
1 Σ
fX,, Y.) Σ
f(x, Y.)
f(x, Y,)
1
Σ
w;())f(Xx,0)
:E|n]
[m)
sm(m]
sEin|.vyy
S sup feF n sEin
Σ f(X,
Σ
f(x, Y.))
$ (w)) (w)
(30)
m 1E/ma]
Therefore, we have
E < F n.m (w) + F) + sup - Σ f(x. Y2) 1 IX, Yo).
(31)
JEF iE(m)
3E[m]
Then, the bound in 255 follows using that n.m (w) < Van. and upper bounding the 'sup' in (T.. Specifically, to bound the expectation of the 'sup' in 31 we use usual argument based on symmetrization. If (X1, Y1), (X2, Y2)..., (X,, Y,) for / = max m) form a different set of i.i.d.

---

samples, we have
E sup fer n
= Σ 1x,, Y.) - m
1
Σ
[Xi, Y.)
EE m
SE [m]]
= E
sup
f(X,, Y.) - { Σ
f(X,, f(X,, 8N)}
FEt
sEin|
:EIm!
_ m
Σ f(Xi, Y:)
1
Σ
f(L,, {:y1}
ve(m)
m
rc(m!
< EE
sup
Σ
f(xi, 1;)- - 5(Xs, xx) } + 1Bg
sup fEF
1 (x,,, (32)
FEF
xE|n]
iE(m)
{ sup /EF sEin|
1
Σ
(f(,, Y.) -f(,, {.11/
+ { sup 1 SEF m EE(m]
Σ
(f(,, Y.) - f(x,, XI))
s 2( (F) (F))
(33)
where in 322 we have used Jensen's and triangular inequalities, and 01,02, Ts are ii.d Rademacher variables o, E {-1, 1). Then, using McDiarmid's inequality (see e.g., [16), with probability at least 1 d we get
sup fer
Σ J(,, YJ) kE(m)
1
Σ =E(m]
((x. s ((R + (.)(())) + B 2
log g
(34)
because changing any (X,, Y;) or (X,, Y.) by other sample in the left hand side of (34g changes the 'sup' at most B/n or B/m, m. since f'xx, y) - f(x, [[x',y/] y')l < B, for any f E F and pairs (I, v), ,').
Therefore, the bound in (25) is directly obtained from 31 and 34
The bound in (26) for families in RKHSs is obtained similarly from (30). The term corresponding to maximum deviations of empirical averages can be bounded more tightly in the RKHS case, without resorting to Rademacher complexities, as follows. Firstly, for the case R = 1 we have
Σ fxx, Y,) fEFi 1E|m]
Σ f(x,, Y.)
sup
m [m(m)
Σ f(x, Y.)
Σ f(x,,
Y.)
sup
SEH.IIfINSS!
m
3E/ml
1 K (E(n)
K(X, Y.,))
Σ K(X, Y..))
(35)
H
cE(m)
as a consequence of the dual characterization of the norm in H. In addition, the expression in also bounds i (w) since is solution of (2) and w" is feasible in (2).
35
The expectation of (35) can be bounded using Jensen's ' inequality (E{s) I v [B())] and the bound
Σ K(X,, Y.,.)
Σ K(X,, Y,, :>
n
:E(m]
1E|m]
E nz
Σ
K(X,, Yi, Xig: Yi,) + m² [lm)
Σ
K(X,, VY. K,, Vin)
Σ
K(X, Y,, X,, {
nm
VE[m]
L
{+ 1 R²
2(K(2 - < F2
(36)
15

---

where Z and Z' denote two independent copies of the RV (X, Y).
Therefore, the bound in (26) follows using McDiarmid's inequality. Specifically, with probability least 1 we get
1 f(X, Y.) Yi)
1 Σ f(x, Y.)l
sup feFi
T iE(n)
m iE(m]
K(X,, Y,,))
Σ 2E|m
K k(X,, V& 111
(37)
iE|n
R ( log
(38)
12
m
because changing any (X,, Yi) or (X, Y,) by other sample in 37 changes the norm at most /2// n or /2k/m, as a consequence of the triangular inequality. Moreover, the bound in (26) is satisfied simultaneously for all R > 0 with probability at least because
sup 1 Σ f(X,, Y,) 1 Σ m kE[m]
f(xx, Y.) = sup Σ SEF iEim
(X,,
Σ sE(m)
f(X,, Y.))
JEFn
n
m
iE|n]
for any R > 0.
B Proof of Theorem I
Let ④ be the quantile obtained in Step 4 of Algorithm Using 18 in Lemma we have
Quantile([(S(X,, Y,), 1/m)) (1 nF. (n 1))(1 1/n))
for
E
(X, Y.)
(c)
*E|n]
iEin).vEy
In addition, using 25 in Lemma we have
E op D(Ee, F) (F) + Rm) + BV (_ =
log log(2/6) G n,m
(39)
1
m
with probability at least - 5/2.. Therefore, with probability at least 1 - 5/2 we have
q Quantile(f(S((X))) Y,). 1/n)) (1 - nG n (n + 1)) + 1/n))
due to the monotonicity of the quantile function. Therefore, with probability least 5/2 we have
P(Y E D) = P(S(X, Y) < {DD ((((X, Y) < Quantile (uuntile((S(X,, Y.), 1/m) (1- nG 1))( + 1/n)) [D}.
(40)
Using standard results for prediction (see e.g., 22 10),, cases with a G. n/(nnnnnnnn S 1, the probability in (40) is lower bounded by
www.aaagepobbbbllitiee... in conventional split conformal
log(2/8)
log(2/8)
GJ
2 1
G n.m
(41)
n n.m
2n
2n
with probability at least 1 - 5/2. In addition, the lower bound in (41) is also satisfied in other cases because if 1 a - G. n/(n + 1) < the lower bound trivially valid and the case 1 - - GF m. n/ (n + 1>> 1 is not possible because both and G.F are positive. Therefore, the inequality in ( follows directly from the lower bound in 41 using the union bound.
In case the values (5(Xx,)))) are distinct with probability one, using 11 in Lemmal ] have
q < Quantile Y.), Ys), (1 + n mm (n + + 1/(n+ 1)) +1/n)
16

---

with probability at least - 8/2..
Therefore, with probability least 5/2 we have
P(Y E C(X)[D) P(S(X, Y) < - P(S(X, Y) - ( 1i), (1- A) ((1)) (D}
(42)
with A a 1--a-G
- 1/)
Using standard results for training-conditional coverage probabbiips in conventional split conformal prediction (see e.g.. (1T0]), in cases with 0 < 1-x+ n. ( (1/(+++))++ 1, the probability
in 42 follows Beta distribution Beta(n n + [(n + 1)AJ, [n + 1)AJ) where [.] denotes the
largest integer that lower bounds the argument. Such a Beta distribution has mean
72 +
(n + 1)A 1 - A+
n
n+1
++1
1 a
n n+l
n n+1 n,m
and is Lub-Gaussian with parameter at most 1/4n. Hence, using a Chernoff bound the probability in can be upper bounded by
42
2
(2/()
1og(2/5)
G n.m n +
1 a+ n+1
G
(43)
72 +2+1
2n
with probability at least 1-6/1 5/2. In addition, the upper bound in 443 is also satisfied in other cases because
1 - G // n.m / + +) + 1/(n + 1) > the upper bound is trivially valid and the case + 1/(n+ 1) 0 is not possible because S 1 and G 2 0. Therefore, the inequality in (10) follows directly from the upper bound (43) using the union bound.
G.F
C Proof of Theorem 2
The proof is analogous to that of Theorem 1 above. The main difference lies in the high-probability bound of E] for
E
(X, Y,)
Σ
=E|n]
aEinlyvy
If FR= H: |fllx & R}. using 26 in Lemma
we have
E S D(Ec, Fn) + 2n R
+ (log(2/5)) for all R>6
with probability at least - 88/2. Therefore,
[E| < inf D(Ec, Fr) + 2v R=0
v /log(2/5)
min JEH REin)yyy
Σ
Ee(Xi, 5 s() 2x(1 + Tog(2/8)
+ Ilfl
G.K Gn,m
(44)
with probability at least - 5/2.
The rest of the proof is totally analogous to that for Theorem (see Appendix B for the details). In particular, the bound for [E] in (44) results in
8 i Quantile(((S(X.) Yz), 1/m) (1 - 1--a-nCee nic / 1))(1++)++1/////) w.p. 2 1 2
using (88 Lemma 0 and
w.p. 8
q < Quantile Y.), 10,11/))eein) (+==++=((((((+++)))))))))))(++)1
if (S(X,, () x are distinct with probability one, using (19 in Lemma 0
Therefore, 13 and 15) are obtained taking into account that
IP(Y C(X) P(S(X, Y) s Q
and that, for any 0 S o the RV P(S(X, Y) < Quantile(((S(X,, Y.), (1
follows distribution that is dominated by a Beta(n (Ia') [m+1)aa and equal to such a Beta distribution in the case where (5(X,, y) ((.))))))))) are distinct with probability one.
17

---

D Additional results
The following provides the detailed derivations leading (1 and (2) in the main paper.
Proposition 1. Eopt be an upper bound for the difference between $ (w( and the optimum value of (.. If the feasible set in 4 includes the label weights w corresponding the actual calibration labels, with probability at least
8 we have
B ( n
= 1og m
(w) S Eopt + +((Rn(F) + Rm Rm)(F)
(45)
Proof. If q= denotes the optimum value (4, we have
Φ n,m (w) = ( n,m (w) - xx) + + S Copt + $"
(46)
and since w is included in the feasible set of (4), we have
Φ S sup fEF
Σ
f(x. Y.)
1 Σ f(e Y.)
(47)
m [E(m]
sein
Using McDiarmid's inequality (see e.g..
16)) with probability at least 1 - 8 we have
sup Σ fEF
f(X,, Y,)
1 Σ
1(x Y.) s ((R.(F) + (m)( B
log
n iE(m]
m iE(m]
m
(48)
because changing any (X;, Yj) or (X,, Yj) by other sample in the left hand side of 48 'sup' at most B/n or B/m, and we have
changes the
E sup
f(X, Y.) VE[N)
Σ
f(,
Yall s 2(R.(F) Rm (F))
(49)
JEF
iE|m]
using a symmetrization argument, as in the proof of Lemma 2
Therefore, the result in 4 is obtained by combining the inequalities in 46 and 48
Proposition Let be an RKHS given by kernel K over X' y. If F is the family of real-valued functions F = {f E H: Ifll < 1}, we have
Σ wx(v)f(X..) 1 Σ ((.,
2
sup SEF (sa))lllxy
m sE(m]
v.)
Kw
nm
m²
K1
(50)
Proof. Using the reproducing property of RKHSs and the dual characterization of the norm in H. have
1 Σ J(X,,
sup SI
(x)))((X..))
8E(m
= sup S1
1 Σ wely) < J, {((,,)))))
SH
Σ
< (,,
sE(m)
sup AllfINEi
< Σ
((x))((X,,))).)))
< f, m 3E(m]
1
Σ (((X,,,)))))
2
((.)))())x
(51)

---

< 1
E (.)))((())))))))
1 Σ
K ((X,,, >H
sup
fi
8E(m]
||
wi wxx))K((X,,))..)
E K(X,, Mi),
VE[m]
Σ
wi, (y)))i
(Xig:
n²
2
Σ
Us, (v1 01);
(X (X v))
(52)
nm
Σ
(() (Xiz )12))
m
(1
where < -, iH denotes the inner product in H. Then, the result in (50) is directly obtained using the definition of K E Rnexne, K E " and v E Ruc as
Kij ((2,, Zj), for i,j [nc], Kis- K(Z,, Zz), for i,j E [m]]
V; = Σ ,ZZ 2,), for [nc]
jE(m]
for ((1-1)++v (X,.)) for [n]. y E and Z, (X,, Y.) for e [m].
E Implementation details and additional experimental results
In the following we provide further implementation details and describe the datasets used in the experimental results. Then, we complement the results the main paper by includ- ing the results for the running times of the methods presented as well additional results with other target coverages and conformal scores. addition, the Github httpps//giithbb hww.ahineeeLaaaangggg/////uuuue
wow.oooaooooooooooooooooo www.ooareddiciooonn-ooo Seweeiittoo-NNeIIP220000 New. and the folder Implementation Unsupervised Conformal in the supplementary materials provide Matlab code corresponding to the presented methods with the setting used in the numerical results.
E.1 Implementation and datasets details
We utilize 9 publicly available and common benchmark datasets for classification tasks: 'Drybean', 'Forestcov', 'Satellite.. 'USPS', 'MNIST', 'FashionMNISTT, 'CIFAR10', 'ImageNet10' (first 10 classes of ImageNet), and 'Letter'. These datasets can be found in the UCI repository (23), Tensor Flow datasets [24] and Kaggle website https: //www kaggle com. The main characteristics of the datasets used is provided in 2
Table Key characteristies of benchmark datasets used in the experiments.
Dataset
# Samples
# Classes
Input Dimensionality
Drybean
13,611
Forestcov
581,012
54
Satellite
6,435
6
36
Letter
20,000
26
USPS
9,298
10
256
MNIST
70,000
10
784
FashionMNIST
70,000
10
784
CIFARI0
60,000
10
3,072
ImageNet10
13,000
150,528
In each random realization, the datasets are randomly partitioned in training, calibration, and test sets. The sizes of the training and test sets are 3, 000 samples and 1, 000, and that of the calibra- tion set varied from to 3, 000. The classification rules are obtained using random forests in the tabular datasets ( ('Drybean', 'Forestcov', 'Satellite,, and 'Letter") and using neural networks in
19

---

Drybean CIFARIO
300
Letter
Running time [seconds)
200
100
1,000
2,000
3,000
Number of culibration samples
Figure 3: Running times of the methods presented as the number of calibration samples increases. For datasets with up 10 classes, the running times range from tens to hundreds of seconds using few thousands of samples.
the image datasets ('USPS', 'MNIST', 'FashionMNIST', 'CIFARIO', and 'ImageNet10"), Specifi- cally, the random forests are given by 200 decision trees and learning is carried out with 20 maxi- mum number of splits and minimum leaf size. The neural networks for 'USPS', 'MNIST' and "FashionMNIST" datasets have two hidden layers of sizes 128 and 64 and learning is carried out with regularization parameter 0.001. The implementation for 'CIFAR10' and 'ImageNet10" datasets is slightly different due their higher complexity. In particular, the classification rule for those datasets learned only once by fine-tuning Resnet50 until a validation error of 4% in 'CIFAR1O' and 11% in 'ImageNetlO" datasets, using SGD with momentum, initial learning rate of 0.001, minibatch size of 64, and regularization parameter 0.001.
Set-prediag eeteprediction rules are obtained using the adaptive conformal score proposed in and also using the conformal score directly given by probability estimates (T] Such scores are computed from the probability estimates provided by the classification rules (proportion of votes from trees in random forest methods, and soft-max outputs in neural networks methods). The conventional approach for split conformal prediction with supervised calibration is implemented using Algorithm (see also, e.g., 22.. The naive approach with unsupervised calibration is implemented using Algorithm [ with labels corresponding to the predictions obtained by the classification rules.
The presented method is implemented using Algorithm 2 with label weights obtained by Algorithm using a Gaussian kernel selected from a set given by 10 candidate bandwidth (scale) parameters
v d/2, for oo E {10-1+t/3 t = 0, I,..., 9}. and m = n training samples randomly drawn from the samples used learn the classification rule. The inequality constraints (2) given by B and b correspond to estimates for the cross-entropy loss of the classification rule obtained in the training stage. Specifically, B Rxmee is given in ( and the pross-entrppy plus its sample standard deviation obtained using validation samples (10-fold cross validation in all datasets but 'CIFAR10' and 'ImageNet10' datasets for which 1, 000 validation samples were used for those estimates). In addition, for "CIFAR10' and 'ImageNet10" datasets the
nL E with the estimate of
instances (X, (X,)ve [e[m] and { [X, {x))e(m) (e(m) used in Algorithm 3 are given by the 312-dimensional feature [m]
representations given by the penultimate layer of the pre-trained Resnet18 network.
E.2 Running times of the methods presented
The main computational burden of the methods presented corresponds to the Step 11 in Algorithm S that solves quadratic optimization problem. In the experimental results carried out, such opti- mization problem is solved using interior point methods with Mosek solver https: com Figure 3 shows the running time achieved by Algorithm 3 using regular desktop machine in the datasets 'Drybean', 'CIFAR10', and 'Letter". These datasets are representative of the over- all running time because they have assorted characteristics. In particular the number of classes in those datasets is 7 ('Drybean'), 10 (" ('CIFARIO'), and 26 ('Letter'). As shown in the figure, the pre-
mosek.
20

---

sented methods have running times ranging from tens to hundreds of seconds for cases with up to 10 classes and up to 3,000 calibration samples. In line with the discussion in Sf the paper, the only problematic cases are those composed by sizable number of classes since the computational complexity of the methods presented increases cubically with the number of classes.
E.3 Additional results with the adaptive conformal score
The main paper shows experimental results using the adaptive conformal score 2 given by
S(XY))
Σ T( > ((]])) UU((XX) sE(c]
for U random value from Unif(O, 1) and p the probability estimate provided by the classification rule used. This section complements the results in the main paper with other target probabilities and with other datases for figures such as those in Fig. and Fig. 2 Specifically, Tables Bl and 4 show coverage probabilities and prediction set sizes analogous to those in Table i the main paper but using target probabilities
a 0.95 and violin plots such those in Fig. Uusing "lmaaeNer10"" 10', FashionMMISTT,, and datasets, and Figure
a 0.85. In addition, Figures
S and 6 show
shows the decrease of coverage gap with the number of calibration samples using 'ImageNet10" and 'MNIST" datasets.
Table 3: Coverage probability and prediction set size for conventional approach with supervised calibration (' ("Supervised"), ) proposed approach with unsupervised calibration ("Unsupervised), and naive unsupervised approach ('Unsup. Naive'). Results are shown as: (interquartile interval), and correspond to 1 .95.
Coverage probability Unsupervised
Prediction set size Unsupervised
Dataset
Supervised
Unsup. Naive
Supervised
Drybean
0.95 (0.94.0.96)
0.95 (0.94,0.96)
0.91 (0.91,0.92)
1.52 (1.47,1.56)
1,51 (1.47.1.55)
Forestcov
0.95 (0.94.0.96)
0.94 (0.93,0.95)
0.68 (0.67,0.69)
2.24 (2.18.2229)
2.15 (2.1,,219)
Satellite
0.95 (0.94.0.96)
0.95 (0.94.0.96)
0.91 (0.90.0.92)
1.77 (1.71,1.82)
1.79 (1.73,1.8)))
USPS
0.95 (0.94.0.96)
0.95 (0.95.0.96)
0.94 (0.93.0.94)
(1.28,)))))))
1.33 (1.29,1..3)
MNIST
0.95 (0.94.0.95)
0.95 (0.95,0.96)
0.93 (0.92,0.93)
1.43 (1.38,1148)
1.45 (1.41,1.50)
Fashion
0.95 (0.94.0.96)
0.95 (0.95,0.96)
0.87 (0.86,0.88)
1.84 (1.76,1.90)
1.84 (1.79.1.89)
CIFARIO
0.95 (0.94.0.96)
0.95 (0.95.0.96)
0.93 (0.93.0.94)
1.10 (1.08.
1.11 (1.10,1.13)
ImagNet10
0.95 (0.94.0.96)
0.94 (0.94.0.95)
0.93 (0.92.0.94)
2.20 (2.13,2.27)
2.07 (2.00.2.14)
Letter
0.95 (0.94,0.96)
0.90 (0.89,0.92)
0.80 (0.79,00088)
9.06 (8.38,9.64)
5.63 (4.99,6.33)
Table 4: Coverage probability and prediction set size for conventional approach with supervised calibration (' ("Supervised"), ), proposed approach with unsupervised calibration ('Unsupervised"), and naive unsupervised approach ('Unsup. Naive"). Results are shown mean (interquartile interval), and correspond to 1-a .85.
Coverage probability Unsupervised
Prediction set Unsupervised
Dataset
Supervised
Unsup. Naive
Supervised
Drybean
0.85 (0.84.0.86)
0.86 (0.85,0.87)
0.78 (0.76,0.79) 79)
1.09 (1.06,1.111
1.11 (1.09.1.13)
Forestcov
0.85 (0.84.0.8))
0.86 (0.85,0.87)
0.57 (0.56,0.58)
1.65 (1.61.1.69)
1.70 (1.67.1.72)
Satellite
0,85 (0.84.0.86)
0.85 (0.84.0.86)
0.78 (0.76.0.79) 79)
1,27 (1.24,1.30)
1.26 (1.23,1.29)
USPS
0.85 (0.84.0.86)
0.85 (0.84.0.86)
0.83 (0.81,0.84)
1.00 (0.97.1.01)
1.01 (0.98,1.03)
MNIST
0.85 (0. 84.0..6
0.86 (0.84.0.87)
0.81 (0.80,0.82)
1.06 (1.03,1.08)
1.07 (1.05,1.09)
Fashion
0.85 (0.84.)))) (0.84.0.66)
0.86 (0.85,0.87)
0.74 (0.72,0.55)
1.24 (1.21,1.27)
1.26 (1.24.1.29)
CIFAR10 10
0.85 (0.84,0.86)
0.86 (0.85,0.87)
0.82 (0.81.0.83
0.93 (0.91,0.94)
0.94 (0.92,0.95)
ImagNet10
0.85 (0.84.0.66)
0.85 (0.84.0.87)
0.80 (0.79.0.81)
1.37 (1.32,1.41)
1.38 (1.33,1.43)
Letter
0.85 (0.84.0.86)
0.81 (0.80.0.83)
0.60 (0.58.0.62)
4.07 (3.84,4.28)
3.38 (3.18,3.58)
21

---

Covengg probability
Prediction set size
L
Supervised Calibration
Supervised Calibration
Unsupervised Calibration
Unsupervised Calibration
samples
sumples
samples
samples
samples
samples
Figure 4: Coverage probabilities and prediction set sizes over 400 random partitions of 'lmageNettO" dataset with target coverage
0.9 and number of calibration samples ranging from 100 to 2, 000.
0.98
Coverige probability
0.94
Prediction set size
0.90
0.86
Supervised Calibration Unsupervised Calibration
Supervised Calibration
Unsupervised Calibration
0.82
100 samples
500 samples
2,000 samples
100 samples
500 samples
2,000 samples
Figure Coverage probabilities and prediction set sizes over 400 random partitions of FashionMMIST dataset with target coverage - a 0.9 and number of calibration samples ranging from 100 to 2, 000.
Coverage probabiity
0.9
Prediction set size
0.900
Supervised Calibration
Supervised Calibration Unsupervised Calibration
Unsupervised Calibration
samples
samples
samples
samples
samples
2,000 samples
Figure 6: Coverage probabilities and prediction set sizes over 400 random partitions of "orcescoov dataset with target coverage
0.9 and number of calibration samples ranging from 100 2, 000.
22

---

027
Averago coverige gap
Arerago coverage gap
a ain
0.04-
0.00
Supervised Calibration
Supervised Calibration
Unsupervised Calibration
0.01
Unsupervised Calibration
Unsup.
Unsup. Cal.
100
500
1000
1000
100
1000
1000
Number of calibration samples a
Number of calibration samples 12
(a) 'ImageNet10" Dataset
(b) 'MNIST" Dataset
Figure 7: Decrease of average coverage gap with the number of calibration samples.
E.4 Additional results with the conformal score given by probability estimates
This section complements the results provided above by using the conformal score given by proba- bility estimates, i.e., S(X, y) = 1 - 5 (Y X) for e the probability estimate provided by the clas- sification rule used. Specifically, Tables 5 and 7 show coverage probabilities and prediction set for target coverages FARIO", 'FashionMNISTT', and 'Forestcov' datasets, and Figures II and showw decrease of cov- erage gap with the number of calibration samples using 'CIFAR1O', 'Drybean', 'FashionMNIST', and 'MNIST" datasets.
E {0.9, 0.95, 0.85 Figures 8 g and 10 show violin plots using 'CI-
Table 5: Coverage probability and prediction size for conventional approach with supervised calibration ('Supervised"). proposed approach with unsupervised calibration (' ('Unsupervised'), naive unsupervised ap- proach ('Unsup. Naive"). Results are shown as: mean (interquartile interval), and correspond to the conformal score given by prohability estimates with - a = 0.9.
Coverage probability Unsupervised
Prediction set size
Dataset
Supervised
Unsup. Naive
Supervised
Unsupervised
Drybean
0.90 (0.89,0.91)
0.89 (0.89,0.90)
0.84 (0.83,0.85)
1.02 (1.01,1.04)
1.01 (1.00,
Forestcov
0.90 (0.89,0.91)
0.90 (0.89.0.91)
0.64 (0.63.0.65)
1.74 (1.69,1.79)
1.75 (1.72,1.77)
Satellite
0.90 (0.89,0.91)
0.90 (0.89.0.91)
0.84 (0.83,0.86)
1.44 (1.40,1.48)
1.44 (1.41,1448
USPS
0.90 (0.89.0.91)
0.91 (0.90.0.92)
0.89 (0.88.0.90)
0.91 (0.90,0.92)
0.93 (0.92,0,94)
MNIST
0.90 (0.89,0.91)
0.92 (0.91,0.92)
0.87 (0.86,0.88)
0.94 (0.93,0.95)
0.97 (0.96,0.98)
Fashion
0.90 (0.89,0.91)
0.91 (0.90,0.92)
0.79 (0.78,0.80)
1.19 (1.16.1.22)
1.24 (1.23.1.26)
CIFARIO
0.90 (0.89.0.91)
0.91 (0.90,0.92)
0.89 (0.88,0.90)
0.91 (0.90,0.92)
0,92 (0.91,0.93)
Letter
0.90 (0.89.0.11))
0.86 (0.85.0.87)
0.72 (0.70,0.73)
5.22 (4.85,5.56)
3.91 (3.72.4.09)
Table 6: Coverage probability and prediction set size for conventional approach with supervised calibration (' ('Supervised"), ), proposed approach with unsupervised calibration ('Unsupervised") and naive unsupervised ap- proach ("Unsup. Naive'). Results shown as: (interquartile interval), and correspond to the conformal score given by probability estimates with a 0.95.
Coverage probability Unsupervised
Prediction set size
Dataset
Supervised
Unsup. Naive
Supervised
Unsupervised
Drybcan
0.95 (0.94.0.9)
0.95 (0. (0.94.0.96)
0.86 (0.86,0.87)
1.16 11.13,1.18)
1.16 14.118888)
Forestcov
0.95 (0.94.0.96)
0.94 (0.93.0.94)
0.67 (0.66,0.68)
2.10 (2.06,2.14)
2.00 (1.98,2.02)
Satellite
0.95 (0.94.0.96)
0.95 (0.94.0.96)
0.91 (0.90.0.92)
1.78 (1.72,1.83)
1.79 (1.71,1.84)
USPS
0.95 (0.94.0.96)
0.96 (0.95.0.97)
0.93 (0.92,0.93)
0.99 (0.98,1.00)
1.01 1.000,1.02)
MNIST
0.95 (0.94.0.96
0.96 (0.95.0.96)
0,90 (0.90,0.91)
1.07 (1.05,1.09)
1.11 (1.09,1.13)
Fashion
0.95 (0.94.0.96)
0.95 (0.94.0.96)
0.82 (0.81.0.82)
1.55 (1.49,1.63)
1.56 (1.53,1660)
CIFAR10
0.95 (0.94,0.96)
0.96 (0.96.0.97)
0.93 (0.92,0.94)
0.98 (0.98,0.99)
1.01 1..00,1.02)
Letter
0.95 (0.94.0.96)
0.90 (0.90.0.91)
0.75 (0.74.0.76)
8.66 18,9..1)
5.46 18.55)))72)
23

---

Table 7: Coverage probability and prediction size for conventional approach with supervised calibration ('Supervised"), ) proposed approach with unsupervised calibration ('Unsupervised") naive unsupervised ap- proach ("Unsup. Naive"). Results are shown as: mean (interquartile interval), and correspond to the conformal score given by probability estimates with - a = 0.85.
Coverage probability Unsupervised
Prediction set size
Datasct
Supervised
Unsup. Naive
Supervised
Unsupervised
Drybean
0.85 (0.84,0.66)
0.85 (0.84.0.86)
0.81 (0.80,0.82)
0.92 (0.90,0.93)
0.92 (0.91,0.93)
Forestcov
0.85 (0.84,0.86)
(0.85,0.87)
0.62 (0.61,0.63)
1.49 11.46)
1.54 (1.51,
Satellite
0.85 (0.84,0.86)
0.86 (0.85,0.87)
0.62 (0.61,0.63)
1.49 11.46,1.52)
1.54 (1.51,1.56)
USPS
0.85 (0.84.0.8)
0.86 (0.85.0.87)
0.84 (0.83,0.85)
0.86 (0.85,0.87)
0.87 (0.86,0.88)
MNIST
0.85 (0.84.0.66
0.86 (0.85,0.87)
0.83 (0.82.0.84)
0.87 (0.86,0.88)
0.89 (0.88,0.90)
Fashion
0.85 (0.84.0.86)
(0.86.0.88)
0.76 (0.75.0.88)
(1.00,1.04)
1.08 (1.06.1009)
CIFARIO
0.85 (0.84,0.86)
(0.84.0.86)
0.84 (0.83,0.85)
0.86 (0.84,0.87)
0.86 (0.85.0.87)
Letter
0.85 (0.84.0.86)
0.82 (0.81,0.83)
0.69 (0.68,0.70)
3.59 (3.34,3.82)
3.04 (2.92.3.17)
Coverage probubility
Prediction set size
1150-
Supervised Calibration
Supervised Calibration Unsupervised Calibration
Unsupervised Calibration
samples
samples
samples
samples
samples
samples
Figure& 8: Coverage probabilities and prediction set sizes over 400 random partitions of 'CIFARIO' dataset with conformal score given be probability estimates, target coverage - 0.9 and number of calibration samples ranging from 100 2, 000.
1.4
Coverage probabiiity
Prediction set size
1.2
Supervised Culibration Unsapervised Calibration
Supervised Calibration
Unsupervised Calibration
100 samples
500 samples
2,000 samples
100 samples
500 samples
2,000 samples.
Figure 9: Coverage probabilities and prediction set sizes over 400 random partitions of 'FashionMNIST' dataset with conformal score given be probability estimates, target coverage 1 - = 0.9 and number of calibration samples ranging from 100 to 000.
24

---

Covenge probability
Prediction set size
Supervised Calibration
Supervised Calibration
Unsupervised Calibration
Unsupervised Calibration
samples
sumples
samples
samples
samples
2,000 samples
Figure 10: Coverage probabilities and prediction set sizes over 400 random partitions of 'Forestcov' dataset 0.9 and number of calibration
with conformal score given be probability estimates, target coverage samples ranging from 100 000.
0.1
0.07
Average coverage gap
Average covergee gapp
0.94
0.0
Supervised Calibration
Supervised Calibration
Unsupervised Calibration
Unsupervised Calibration
Unsup Cal. Naive
Unsup. Cal. Naive
100
1000
3000
100
1000
3000
Number of calibration samples
Number of calibration samples
(a) 'CIFAR1O' Dataset
(b) 'Drybean' Dataset
Figure 11: Decrease of average coverage gap with the number of calibration samples with conformal score given by probability estimates.
0.1
Supervised Calibration
0.07
Unsapervised Calibration
Unsup. Cal. Naive
Average coverage gap
Average coverage gap
0.04
0.0
0.02
Supervised Calibration
0.01
Unsupervised Calibration
001
Unsup. Cal. Naive
1000
Number of calibration samples vo
Number of calihration samples 12
(a) 'FashionMNIST' Dataset
(b) 'MNIST' Dataset
Figure 12: Decrease of average coverage gap with the number of calibration samples with conformal score given by probability estimates.
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims in abstract and introduction accurately describe the paper contri- butions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed over the paper. In particular the theorems state the hypothesis required.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
26

---

Answer: [Yes]
Justification:
The detailed proofs appear in the appendices and the theorems state all the assumptions made.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided or not)?
Answer: [Yes]
Justification: The experimentation carried out in the paper is described in Section 5 and detailed in Appendix together with the details needed to reproduce the results. In addition, the supplementary material provides Matlab code that implements the methods presented in the experimental setting used.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture the contribution it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
fully might suffice,
specific model and empirical evaluation.
While NeurIPS does not require releasing code, the conference does require sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in
27

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code is provided in the supplementary materials and the data used is publicly available through the UCI repository and Tensor Flow datasets, as described in Appendix E.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurIPS code and data submission guidelines luttps://nips.. https////iip.cccpuubiii//////// h//g//ddd//coessse
(wooeeuumissiooooolllloioe ssionpolicy) for more details,
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer:
[Yes]
Justification: The experimental settings/details described in Section 5, detailed in Ap- pendix E, and in the code provided in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [es]
Justification: The experimental results provide error bars in terms of interquartile ranges and violin plots over different random partitions of the data.
Guidelines:
The answer NA means that the paper does not include experiments.
28

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the eπror bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
The experimental results in the paper can be carried out in a regular desktop machine in few hours, as described in Appendix E.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary failed experiments that didn't It make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
htt:://uurrrccccce/e httprrpppp..cppp..ccccctctaataaa
Answer:
[Yes]
Justification:
The research conducted conform with such Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
The paper presents foundational research that is not tied particular applica- tions.
Justification:
29

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
The paper presents foundational research that is not tied to particular applica- tions/datasets.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The paper refers to all the relevant previous works.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
30

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the pack- age should be provided. For popular datasets, paperswithcode www.coo//aaa.aac datasets has curated licenses for some datasets. Their licensing guide can help determine the
cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
The code provided documented and easy to use.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should paid at least the minimum wage the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
31

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
32


Reviews:
[{"review_id": "5yLKnq6SbL", "reviewer": "Reviewer_bFNU", "summary": "This paper considers the problem of obtaining a conformal prediction set where the conformal score thresholds are calibrated using an unlabeled calibration set. The proposed method learns class probabilities by matching the joint distribution between the labeled training set (X̃, Ỹ) and the pseudo-labeled calibration set $(X = x, Y = j)$, where each is weighted by its estimated probability $P(Y = j | X = x)$, measured using an integral probability metric (IPM). The paper then shows that, under mild assumptions on the function space used for distribution matching and on the relationship between this space and the conformal set indicator function, the proposed approach can provide bounds on the coverage rate.", "questions": "As discussed above, a central claim of the paper is that the proposed class-probability optimization does not require a highly accurate base classifier trained on the labeled data. However, the constraint involving the base classifier predictions (specifically the bound on Bp) appears to implicitly require that the learned probabilities align reasonably well with those from a classifier. Could the authors clarify: how accurate does the base classifier need to be in practice for the method to perform well? Is there a failure mode if the base classifier is poorly calibrated or highly inaccurate?\n\nIn addition, it would be helpful to include a more practical comparison with existing approaches for conformal prediction using unlabeled calibration data, as well as standard classifier calibration methods (e.g., temperature scaling, Dirichlet calibration, use splits of the labelled training set to calibrate). This would help contextualize the proposed method’s strengths and limitations in applied settings.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "(+) The proposed approach is sound and, to the best of the reviewer’s knowledge, novel. This is the first work to leverage the idea of joint distribution matching on an unlabeled calibration set to construct conformal prediction sets. The theoretical framework is compelling and naturally connects to the literature on two-sample testing, particularly via maximum mean discrepancy (MMD) (Gretton et al., 2012). The authors also extend their method to a kernel-based version, making this connection explicit and providing a practical implementation pathway.\n\n\n\n(–) That said, a key weakness of the paper lies in the lack of discussion of related work and practical guidance on method selection. Specifically:\n\n* Conformal prediction with unlabeled calibration data has been studied in prior work [1,2,3], A detailed comparison of assumptions, theoretical guarantees, and empirical performance would strengthen the paper: \n\n\n\n\n* Prediction-powered inference (PPI) [4] is a related framework where unlabeled data is paired with predicted probabilities to perform valid inference. While this paper does not directly use hard classifier outputs, the optimization still implicitly assumes reasonable prediction quality, creating conceptual overlap worth acknowledging.\n\n* The literature on classifier probability calibration [5, 6] focuses on adjusting individual predictive confidence. While such methods lack coverage guarantees like conformal prediction, they offer fine-grained, per-instance calibration that may be practically useful in similar contexts. A clearer discussion of the tradeoffs could help position this work.\n\n\n(1) Zhou et al., SemiCP: Semi-Supervised Conformal Prediction With Unlabeled Nonconformity Score \n\n(2) Han et al., Conformal Calibration under Distribution Shift\n\n(3) Lienen et al., Conformal Prediction with Weak or Credal Labels\n\n(4) Gibbs & Jordan, Prediction-powered inference\n\n(5) Guo et al. (2017), On Calibration of Modern Neural Networks\n\n(6) ull et al., Beyond Temperature Scaling: Obtaining Well-Calibrated Multi-Class Probabilities with Dirichlet Calibration", "was_revised": true, "final_justification": "After discussing with the authors, I would like change my position to be (5: Accept). In general it is sounding approach for the domain of conformal prediction. If there is anything, I would suggest to investigate further the links to related works as in PPI and post-hoc calibration, as well as added some case studies on the impact of the base predictive models.", "rebuttal": "We would like to thank the Reviewer for his/her appreciation of the paper and for the suggestions and comments provided. We are confident that the comments and questions raised are fully addressed below, and we would be happy to answer any further questions the Reviewer may have during the authors/reviewers discussion period.\n\n**Prior work on conformal prediction with unlabeled calibration data**\n\nTo the best of our knowledge, there are not previous works on conformal prediction with unlabeled calibration data. Regarding the papers [1,2,3] suggested by the reviewer: the semi-supervised approach in [1] requires both labeled and unlabeled calibration samples, while the presented method only uses unlabeled calibration samples. In addition, such a paper is currently under review and was submitted to arxiv 12 days after the full paper submission deadline for this conference, so it was not possible for us to discuss such a work. In the final version of the paper, we will use the extra space allowed to include a discussion of the semi-supervised approach in the description of methods for split conformal prediction with weakly supervised calibration (currently lines 35-41). Regarding references [2] and [3] suggested by the Reviewer, we have not been able to find them, so it is not clear for us what prior work the Reviewer is referring to.\n\n\n**Relation with prediction-powered inference and calibration methods**\n\nAs described by the Reviewer, there is some conceptual overlap with the methods proposed in the paper and methods for prediction-powered inference and calibration. Such relation will be discussed in the final version of the paper together with the relevant references. \n\nThe naive approach used as a baseline for split conformal prediction can be seen as an application of prediction-powered inference where a classification model is used to obtain labels for the calibration samples. As described in the paper, such type of approaches have inferior performance than the proposed methods (lines 111-115, 225-232, and 337-339). The proposed approach, can be thought of as obtaining \"pseudolabels\" for the calibration samples in terms of probabilities. However, the proposed methods do not aim to maximize the number of \"pseudolabels\" that agree with actual labels but to find \"pseudolabels\" that enable to estimate general expectations (and hence quantiles) similarly as the actual labels.\n\nCalibration methods are related to conformal prediction techniques since both frameworks aim to better account for the predictive uncertainty of learning methods. However, calibration and conformal prediction methods account for such uncertainty in rather different ways. Conformal prediction aims to obtain set-predictions that contain the true label with high probability while calibration methods aim to obtain probabilistic predictions that are consistent (calibrated) with the actual frequency of different labels. Therefore a quantitative comparison of both types of approaches is hardly possible.\n\n**Relation between the accuracy of the base classifier and the performance achieved by the proposed methods** \n\nThe accuracy of the base classifier is closely related to the performance of the naive approach used as baseline, but not to the performance of the proposed methods. In particular, the coverage gap for the naive approach is of the order of the base classifier error, while the coverage gap for the methods proposed decreases as $O(\\sqrt{1/n+1/m})$ regardless of the error of the base classifier (see also lines 111-115, lines 225-232, and lines 275-277). These theoretical results are also in agreement with the experimental results, which demonstrate that the naive approach only provides acceptable performance in cases where the base classifier has very low error (\"CIFAR10\" and  \"USPS\" datasets). On the other hand, the proposed methods obtain a performance very close to that with supervised calibration samples in all the experimental results. Specifically, the error of the base classifier used in each dataset is as shown in the following table\n\n| Dataset             | Drybean | Forestcov | Satellite | USPS | MNIST | Fashion | CIFAR10 | Letter |\n|---------------------|---------|-----------|-----------|------|--------|---------|---------|--------|\n| Base classifier error | 0.12    | 0.33      | 0.12      | 0.04 | 0.06   | 0.18    | 0.04    | 0.34   |\n\n\nSuch errors are significantly higher than the coverage gap of the proposed methods.\n\nThe constraint involving the base classifier predictions ($\\mathbf{B}\\mathbf{p} \\preceq \\mathbf{b}$) does not imply that the probabilities obtained by solving optimization (4) (or (12)) align with those provided by the base classifier. Such a constraint implies that expected losses of the base classifier, estimated using the optimized label probabilities, are not larger than an upper bound on that expected loss. For instance, if the upper bound for the expected loss is obtained as\n\n$$\n\\mathbf{b} = \\frac{1}{m} \\sum_{i \\in [m]} \\ell(h(\\widetilde{X}_i), \\widetilde{Y}_i) + S\n$$\nfor $S$ being the sample standard deviation of the above sample mean, then the constraint ($\\mathbf{B}\\mathbf{p} \\preceq \\mathbf{b}$) becomes\n\n$$\n\\sum_{i \\in [n]\\, y \\in \\mathcal{Y}} p_i(y) \\ell(h(X_i), y) \\leq \\frac{1}{m} \\sum_{i \\in [m]} \\ell(h(\\widetilde{X}_i), \\widetilde{Y}_i) + S\n$$\nSuch a constraint is not directly related to the alignment between the outputs of the base classifier ($h(X_i)$) and the optimized label probabilities ($p_i(y)$). Instead, the constraint is related to how well the probabilities $\\lbrace p_i(y)\\rbrace$ align with the empirical distribution of the labeled training samples, in terms of matching expected values of the function $g(X,Y) = \\ell(h(X), Y)$. An expectation estimate of any function $g(X,Y)$ could be used in optimization problem (4); the use of expected loss estimates for the base classifier is a convenient choice because most methods return such estimates as part of the training process."}, {"review_id": "ZNEjgvtF2r", "reviewer": "Reviewer_Nrn4", "summary": "This paper proposes a novel method for conformal prediction using unsupervised calibration data. The authors introduce a technique for assigning label probabilities to each calibration example by leveraging the labeled training data. These probabilities are obtained by solving an optimization problem that minimizes the integral probability metric between the distribution of labeled training samples and the pseudo-labeled calibration data.", "questions": "1-\tCould the authors provide experimental results on runtime to compare the proposed method with supervised and naive unsupervised approaches?\n\n2-\tTheorem 2 states that the guarantees hold for any data distribution. Does this imply that the proposed algorithm remains valid even when the exchangeability assumption between test and calibration data is violated?\n\n3-\tHow does the proposed method compare to existing weakly-supervised conformal prediction methods in terms of coverage and prediction set size?\n\n4-\tAs noted in the paper, achieving a small coverage gap requires the function class $\\mathcal{F}$ to accurately approximate the indicator function $\\mathcal{X}_C$. Could the authors elaborate on how the choice of $\\mathcal{F}$ affects the prediction set size in practice", "limitations": "The proposed method may not scale well to settings with a large number of labels. Its performance relies on the chosen function class $\\mathcal{F}$ being able to accurately approximate the function $\\mathcal{X}$,", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: The paper provides a solid theoretical foundation for the proposed method, including performance guarantees and computational complexity analysis. It is also well-written and clearly presented.\n\nWeakness: Please check the questions.", "was_revised": true, "final_justification": "The paper provides a solid theoretical foundation for the proposed method. During the rebuttal, the authors addressed my concerns; therefore, I have decided to increase my confidence in the score.", "rebuttal": "We would like to thank the Reviewer for his/her appreciation of the solid theoretical foundation presented, and for the suggestions and comments provided. We are confident that the comments and questions raised are fully addressed below, and we would be happy to answer any further questions the Reviewer may have during the authors/reviewers discussion period.\n\n**Runtime of the methods proposed with respect to conventional split conformal prediction**\n\nAppendix E.2 in the supplementary materials experimentally assess the runtime of the methods proposed (lines 294-310 in Section 4 describe the theoretical computational complexity). We plan to use the additional space allowed in the final version to incorporate in the main paper the running times in the experimental results. Figure 3 in Appendix E.2 shows the running times of the methods presented as the number of calibration samples increases in 3 datasets with different number of classes (7 in \"Drybean\", 10 in \"CIFAR10\", and 26 in \"Letter\"). As shown in the figure, the presented methods have running times ranging from tens to hundreds of seconds for cases with up to 10 classes and up to 3,000 calibration samples. In line with the discussion in Section 4 of the paper regarding the computational complexity of the methods presented, the only problematic cases are those composed by a sizable number of classes, since the computational complexity of the methods presented increases cubically with the number of classes. On the other hand, the conventional approaches for conformal prediction (supervised and naive) have much smaller running times (less than a second) since they only require to computed one quantile. \n\nThe significant difference in complexity and the unsuitability for cases with many classes are the main limitations of the methods proposed, as pointed out on lines 47-48, 220-224, 294-310, and 335-337. The increase in complexity does not limit the practicality of the methods proposed. In particular, the running time of the methods presented is significantly lower than that of usual training stages. In addition, it can be argued that a running time as low as that of the supervised approach is not needed in practice since the calibration stage is commonly carried out only once. These aspects will be further discussed in the final version of the paper. In particular, we will add a new paragraph “Limitations” dedicated to state the main limitations of the methods proposed.\n\n**Exchangeability between test and calibration data**\n\nIn the paper, all data samples (instance-label pairs) are described by the same random variable $(X,Y)$ (see lines 66-69) so that they are samples from the same distribution, that is, the paper does not address scenarios affected by distribution shifts. The theoretical guarantees of the methods proposed (as those in conventional supervised split conformal prediction, see line 87) are valid for any data distribution, that is, for any distribution of the random variable $(X,Y)$ describing instance-label pairs of training, calibration, and test samples. As in the conventional approach, this generality does not affect the exchangeability of calibration and test samples, it just describes that the results are valid for an arbitrary data distribution (of both calibration and test samples). \n\n**Comparison with existing methods for weakly-supervised conformal prediction**\n\nTo the best of our knowledge, the paper presents the first method for conformal prediction that can utilize unsupervised calibration samples. Existing methods for weakly-supervised conformal prediction cannot be used with unlabeled calibration samples. Specifically, the methods in [5] and [7] require to have fully labeled calibration samples (the labels are allowed to be affected by random noise). In the methods [6] and [8], some of the calibration samples can be unlabeled (missing labels) but a significant proportion of the calibration samples need to be accurately labeled. Therefore, it is not really possible to carry out a fair comparison between the proposed methods and existing methods for weakly-supervised conformal prediction. \n\nThe comparisons carried out in the paper are with respect to the benchmark approach of supervised conformal prediction that describes the best possible performance and with respect to a naive approach devised by us to have a reference for the performance with a simple approach. The results presented show that the proposed methods can achieve performances near to the benchmark of supervised calibration and significantly better than the naive approach.\n\n**Relation between the choice of the function class and prediction set sizes**\n\nThe choice of the function class can directly affect the coverage gap (as described in Theorems 1 and 2). However, its influence on the prediction set size is only indirect. Specifically, cases with a negative coverage gap (i.e., the actual coverage is smaller than the target coverage) result in somehow smaller prediction set sizes since the conformal quantile obtained in those cases is smaller than the ($1-\\alpha$)-quantile of the distribution. Reciprocally, cases with a positive coverage gap results in somehow bigger prediction set sizes. These facts can be observed in the experimental results, for instance the coverage gap in Figure 1 with unsupervised calibration tends to be slightly higher than that with supervised calibration (left panel), and the prediction set size with unsupervised calibration tends to be slightly higher (right panel). Similar behavior can be observed in other results like in Table 1.\n\nThe choice of the function class affects the coverage gap, but such a gap is small for a large-enough number of samples. In particular, the usage of too small or too complex function classes would result in larger coverage gaps (see discussion for the bias-variance trade-off for the choice of the function class on lines 205-215). As discussed on lines 275-284, the usage of function classes defined by positive definite kernels (e.g., Gaussian, Laplacian, and polynomial) results in coverage gaps that decrease with the number of samples as $O(\\sqrt{1/n+1/m})$, with smaller proportionality constant in cases where the kernel used is well-adapted to the dataset at hand. As shown on lines 285-293 and lines 2-7 in Algorithm 3, the proposed methods enable to effectively select the kernel used so that the corresponding coverage gap is small (as corroborated in the experimental results)."}, {"review_id": "Eb0YmknUq5", "reviewer": "Reviewer_85zz", "summary": "This paper proposes a novel method to split conformal prediction for classification tasks, utilizing unsupervised calibration. The proposed method constructs set-prediction rules by integrating unsupervised calibration samples with supervised training samples previously employed to train the classification rule.", "questions": "- If supervised training samples are directly incorporated into the calibration set, can the coverage guarantee still be maintained?\n- Can eq (4) ensure that the calibration and training samples become statistically indistinguishable? Could you provide a more detailed explanation to support this?\n- Does eq (4) ensure the validity of the formula presented on line 168?\n- The coverage on the Letter dataset appears consistently low; is this within an acceptable range?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- This paper is well-written and easy to follow.\n- To the best of my knowledge, this paper is the first to investigate the use of unsupervised calibration for split conformal prediction.\n\nWeaknesses:\n- The paper lacks a proof of exchangeability between the calibration set and the test set, which is a critical assumption for the validity of conformal prediction methods.\n- The experimental validation is limited to small datasets; extending the evaluation to larger datasets, such as ImageNet, would significantly strengthen the robustness of the findings.", "was_revised": true, "final_justification": "The authors have provided detailed clarifications and additional experiments that satisfactorily address my main concerns. In particular, they explained the assumption of exchangeability, added results on ImageNet10 to strengthen empirical validation, and elaborated on the role of Eq. (4) and its implications for statistical equivalence. Therefore, I have decided to raise my score to 4.", "rebuttal": "We thank the Reviewer for the valuable suggestions and comments. We are confident that all points raised have been fully addressed below. Should the Reviewer feel that any aspect of the response requires further clarification, we would be happy to provide additional details during the authors/reviewers discussion period.\n\n**Exchangeability between the calibration set and the test set**\n\nWe do not fully understand the comment from the Reviewer regarding a proof for exchangeability. As described on lines 67-68 the paper considers data samples (instance-label pairs) from the same random variable $(X,Y)$ that are drawn i.i.d. from the same data distribution. Therefore, the exchangeability between calibration and tests samples follows from the setting considered in the paper, which is the same as that in conventional split conformal prediction. We do not consider scenarios affected by distribution shifts in which the distribution of calibration samples is different to that of test samples (or that of training samples).\n\nIn order to avoid any possible confusion, we will stress this fact in the preliminaries section by slightly modifying the first paragraphs as:\n\"Let ... $\\mathcal{D}$ be a dataset composed by i.i.d. copies of $(X,Y)$. The dataset is split into two groups .... All the data samples (for training, calibration, and test) are randomly drawn from the same data distribution, so that they are independent and, hence, exchangeable.\"\n\nIn case we have misinterpreted the comment from the Reviewer, we would appreciate further guidance during the Author-Reviewers discussion period, so that we can completely clarify this aspect. We would also like to point out that an important contribution in the paper is that the theoretical analysis followed is novel (as briefly described on lines 164-174, and detailed in the proofs shown in the Appendices). Besides these technical novelties, the theoretical results presented also rely on the independence (exchangeability) of calibration and test samples (e.g., all the pairs $(X_i,Y_i), (\\widetilde{X}_i,\\widetilde{Y}_i), (X,Y)$ in the proofs are independently drawn from the same data distribution). \n\n**Additional experiments with ImageNet dataset**\n\nWe agree with the Reviewer that the usage of ImageNet dataset in the experiments can further strengthen the experimental assessment, so that we have obtained new results with this dataset. In particular, we have utilized ImageNet10 composed by the first 10 classes of ImageNet because the methods proposed are not meant to be used in problems with a sizeable number of classes. This limitation is described on lines 220-224, 294-310, and 335-337, and will be further pointed out in a new paragraph “Limitations” describing the main two limitations of the methods proposed: the inadequacy to address problems with a significant number of classes, and the increase in complexity with respect to conventional split conformal prediction with supervised calibration. \n\nThe results obtained with ImageNet10 dataset with a Resnet50 neural network are as follows:\n\nRow for Table 1 ($1-\\alpha=0.9$)\n\n| Dataset    | Coverage Probability - Supervised | Coverage Probability - Unsupervised | Coverage Probability - Unsup. Naive | Prediction Set Size - Supervised | Prediction Set Size - Unsupervised |\n|------------|-----------------------------------|-------------------------------------|-------------------------------------|----------------------------------|-------------------------------------|\n| ImageNet10 | 0.9 (0.89, 0.91)                  | 0.89 (0.88, 0.90)                   | 0.86 (0.85, 0.87)                   | 1.66 (1.60, 1.71)                | 1.61 (1.55, 1.68)                   |\n\n\nRow for Table 3 ($1-\\alpha=0.95$)\n\n| Dataset    | Coverage Probability (Supervised) | Coverage Probability (Unsupervised) | Coverage Probability (Unsup. Naive) | Prediction Set Size (Supervised) | Prediction Set Size (Unsupervised) |\n|------------|-----------------------------------|--------------------------------------|-------------------------------------|-----------------------------------|--------------------------------------|\n| ImageNet10 | 0.95 (0.94, 0.96)                 | 0.94 (0.93, 0.95)                    | 0.93 (0.92, 0.93)                   | 2.22 (2.13, 2.29)                 | 2.05 (1.98, 2.13)                    |\n\n\nRow for Table 4 ($1-\\alpha=0.85$)\n\n| Dataset    | Coverage Probability (Supervised) | Coverage Probability (Unsupervised) | Coverage Probability (Unsup. Naive) | Prediction Set Size (Supervised) | Prediction Set Size (Unsupervised) |\n|------------|-----------------------------------|--------------------------------------|-------------------------------------|-----------------------------------|--------------------------------------|\n| ImageNet10 | 0.85 (0.85, 0.86)                 | 0.85 (0.84, 0.86)                    | 0.80 (0.79, 0.81)                   | 1.37 (1.33, 1.41)                 | 1.37 (1.32, 1.41)                    |\n\n&nbsp;\n\nThese new results show that the methods proposed are also effective in the dataset ImageNet10. As in the other experimental results in the paper, the performance of the methods proposed is only slightly inferior to that of conventional methods with supervised calibration. \n\nOverall, the paper shows experimental results with 8 datasets (9 counting ImageNet10) with number of samples ranging from 6k to 581k (ImageNet10 has 13k samples), number of classes ranging from 6 to 26, and input dimensionality ranging from 16 to 150k (ImageNet10 is composed by 3x224x224 images).\n\n**Coverage guarantees if training samples are incorporated in the calibration set**\n\nThe performance guarantees presented in the paper rely on the independence among the samples used for training and calibration (stated on lines 67-68). For instance, the bounds in (33), (34), (36), and (38) (among others) are obtained using such independence. As described in a previous response, we will further stress the independence among samples at the end of the second paragraph of the preliminaries section. Nevertheless, the Reviewer raises a quite interesting and subtle point. If supervised training samples are directly incorporated into the calibration set, performance bounds somehow similar (in form) to those in the paper could be obtained. However, such type of approaches would not be effective in practice and the quantitative values of the bounds would be much higher, at least using common modern classifiers that often fit almost perfectly the training samples. As discussed on lines 280-284, the performance guarantees of the methods proposed rely on the smoothness at the calibration instances of the function 𝔛$_C$ (obtained from the base classifier score). Such a function is often highly non-smooth at the training instances (e.g., using classifiers that perfectly interpolate the training samples). On the other hand, in common cases the function 𝔛$_C$ is fairly smooth at calibration instances that are randomly drawn independently from the training instances. Notice that cases in which the classifier score is highly non-smooth for samples independent to those in the training set would correspond to highly poor classifiers. In the final version of the paper, we will expand the paragraph on lines 280-284 to discuss these aspects.\n\n**Optimization in (4), statistical equivalence of calibration and training samples, and formula on line 168**\n\nSolutions of optimization problem (4) correspond to training and calibration sets that are statistically indistinguishable by the corresponding IPM-based two-sample test. The optimal value of (4) is not larger than the value of the IPM test achieved using the labeled calibration and training samples $\\lbrace(X_i,Y_i)\\rbrace$ and $\\lbrace(\\widetilde{X}_i,\\widetilde{Y}_i)\\rbrace$ because the value of such IPM test coincides with the value of (4) for the specific label probabilities $p_i^*(y)=\\mathbb{I}\\lbrace y=Y_i\\rbrace$. Then, an IPM-based test would not find a significant statistical difference between training and calibration sets corresponding to solutions of (4) since the value of the test statistic would be not larger than that achieved by two sets that are composed by independent samples from the same distribution.\n\nWe would also like to point out that we see such statistical equivalence as an insightful way to illustrate the methodology presented. The technical proofs of Theorem 1 and Theorem 2 in Appendices B and C are not consequences of such statistical equivalence. For instance, Theorem 1 is valid also in cases where the label probabilities $p_i^*(y)=\\mathbb{I}\\lbrace y=Y_i\\rbrace$ do not correspond to a feasible solution for (4).\n\nLabel probabilities found solving optimization in (4) ensure the validity of the formula on line 168 due to a similar rationale as above. Specifically, the objective value in (4) is $O(\\sqrt{1/n+1/m})$ for the label probabilities that correspond to the actual calibration labels  because samples $\\lbrace (X_i,Y_i)\\rbrace$, $\\lbrace (\\widetilde{X}_i,\\widetilde{Y}_i)\\rbrace$ are i.i.d. Therefore, the optimal value of (4) is small for a sufficient number of calibration and training samples, leading to the approximation on line 168.\n\n**Coverage gap in \"Letter\" dataset and in other cases with a sizeable number of classes**\n\nAs described above (and on lines 220-224, 294-310), the proposed methods provide poor performance in cases with a sizeable number of classes (\"letter\" dataset has 26 classes). The poor coverage achieved in \"letter\" is specifically accounted in lines 335-337 “In accordance with the discussion in Section 3.2 regarding the weakened guarantees in scenarios with many classes, \"Letter\" –which includes 26 classes– is the only dataset showing significantly poorer performance.” As described in previous responses, the final version of the paper will include a specific paragraph dedicated to state the limitations of the proposed methods in terms of the number of classes."}, {"review_id": "jvARkMDNsw", "reviewer": "Reviewer_cxnj", "summary": "This paper proposes an interesting new idea for using unlabelled calibrated examples for doing split CP. This comes with a worse coverage guarantee, but gives the benefit of using unlabelled data.", "questions": "1)\nThis paper claims that the theoretical guarantee (validity) is \"comparable\" to that of split CP. However, there is no understanding of what the $G^F_{n,m}$ means in practical terms. What is its magnitude? Can you estimate its value?\nI fully appreciate the discussion provided in 3.2 surrounding this, but it's still very hard to understand what the validity guarantee means in practical terms.\nI think the claim that the proposal is comparable to split CP is unsubstantiated unless concrete numbers (or a more interpretable expression for this term) is given.\n\n2)\nThe method is only compared against split CP. However, there's numerous methods which try to achieve the same (i.e., to maximize the information available to CP's prediction sets with little data). I suggest a comparison is made with them (e.g., cross-CP and full CP) under the following setup:\n- the proposal works as usual, by seeing both training and unlabelled sets\n- the other two methods are only given the training data (i.e., no calibration data, for fairness).\nPresumably, the proposal should perform better, because it has access to additional data. However, it is possible that the other two better exploit the information that is available in the training set.\n\n3)\nThe fact that coverage guarantees are worse for larger $n$ and $m$ should be emphasized from the beginning.\n\n4)\nThe term \"probabilities\" is confusing (and wrong); a more appropriate one is \"confidence values\".\n\n>  the conventional approach can be seen as a particular case of Algorithm 2\n\nThis isn't correct. In Algorithm 2, the quantile is evaluated over a much larger multiset than the original algorithm, since it looks at all the possible labels.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- new method that enables calibrating split CP on unlabelled points\n- well-presented results\n- good theoretical analysis\n\nWeaknesses:\n- it's hard to understand in practice what is the price to pay in the validity guarantee (excess coverage gap)\n- no comparison against methods that try to achieve the same", "was_revised": true, "final_justification": "Thanks for the rebuttal. I encourage the authors to include the cross-CP experiments in a revised version, along with an explanation on pros/cons.", "rebuttal": "We would like to thank the Reviewer for his/her appreciation of the approach novelty and the theoretical analysis, and for the suggestions and comments provided. We are confident that the comments and questions raised are fully addressed below, and we would be happy to answer any further questions the Reviewer may have during the Authors/Reviewers discussion period.\n\n**Excess coverage gap with respect to conventional supervised split conformal prediction**\n\nAs pointed out by the Reviewer, the difference in performance guarantees between the proposed methods and conventional supervised approaches is given by the term $G_{n,m}^F$ (excess coverage gap). As discussed qualitatively in Section 3.2 (Theorem 1) for general families of functions $\\mathcal{F}$, such a term is small using broad families of functions and a sufficient number of samples. The result in Theorem 1 is applicable with wide generality, while more interpretable expressions of the excess coverage gap can be obtained for specific choices of family of functions. In particular, Theorem 2 presents a significantly more interpretable excess coverage gap for kernel-based families (equation (14)). In that case, the excess coverage gap corresponds to the optimum value achieved in a ridge-regression fit (with L1 loss) of the function 𝔛$_C$ using functions in a RKHS. As described on lines 275-284, the excess coverage gap decreases with the number of samples as $O(\\sqrt{1/n +1/m})$ for any strictly positive definite kernel (e.g., Gaussian, Laplacian, and polynomial), with proportionality constant given by the minimum norm of functions that interpolate 𝔛$_C$ at the calibration instances. The magnitude of  such minimum norm depends on the smoothness of the function 𝔛$_C$ at the calibration instances. Such function may be highly non-smooth at the training instances, but is expected to be fairly smooth at the calibration instances for prediction rules that generalize. \n\nNotice also that the upper bounds for the excess coverage gap on lines 275-284 are computable in practice by solving a simple interpolation problem with closed-form solution, as described on lines 285-293. This fact allows to have a practical data-based method to select the kernel, as described in that paragraph and detailed on lines 2-7 of Algorithm 3.\n\n**Comparison with methods beyond split conformal prediction**\n\nThe main contribution in the paper is a methodology that enables to carry out split conformal prediction without acquiring labels for the calibration samples. As described by the Reviewer, other methods for conformal prediction that are not based on split (or inductive) conformal prediction (e.g., cross-CP and full CP) do not rely on labeled calibration data as well, since they do not use calibration samples at all. However, split conformal prediction offers important intrinsic advantages with respect to other approaches such as cross-CP and full CP. In particular, split conformal prediction can be applied to any prediction model, including “black box” models with opaque or poorly understood training procedures, to produce valid predictive sets. On the other hand, methods such as cross-CP and full CP cannot be used with “black box” prediction rules and require to carry out multiple training stages in order to obtain the set-prediction rule. Full CP is highly inefficient and hardly implementable in practice since it requires to learn multiple prediction rules for each new test instance. Cross-CP is more efficient since it requires to carry out a fixed number of training stages (e.g., 5 or 10). However, Cross-CP does not provide performance guarantees for general types of prediction rules [R]. \n\nNevertheless, we agree with the Reviewer that it can be valuable to compare the proposed methods with alternative approaches beyond split conformal prediction. Therefore, we have carried out the experimental results suggested by the Reviewer using Cross-CP with 10-fold partitions (the implementation with full CP is not computationally feasible with strong prediction rules and sizable test sets). The following table shows the results achieved in \"MNIST\", \"FashionMNIST\" and \"USPS\"  datasets by Cross-CP and the proposed methods for unsupervised split conformal prediction. Specifically, the tables show the average coverage gap achieved using $m=1,000$ training samples and varying the number $n$ of unsupervised calibration samples.\n\n`MNIST’ dataset:\n\n|  | Cross-CP | Proposed (n=50) | Proposed (n=100) | Proposed (n=500) | Proposed (n=1000) | Proposed (n=2000) | Proposed (n=3000) |\n|--------------|----------|------------------|-------------------|-------------------|--------------------|--------------------|--------------------|\n|           Coverage Gap  | 0.011    | 0.033            | 0.024             | 0.014             | 0.014              | 0.012              | 0.011              |\n\n\n`FashionMNIST’ dataset:\n\n| | Cross-CP | Proposed (n=50) | Proposed (n=100) | Proposed (n=500) | Proposed (n=1000) | Proposed (n=2000) | Proposed (n=3000) |\n|--------------|----------|------------------|-------------------|-------------------|--------------------|--------------------|--------------------|\n|         Coverage Gap      | 0.013    | 0.027            | 0.022             | 0.016             | 0.014              | 0.013              | 0.012              |\n\n\n`USPS’ dataset:\n\t\n| | Cross-CP | Proposed (n=50) | Proposed (n=100) | Proposed (n=500) | Proposed (n=1000) | Proposed (n=2000) | Proposed (n=3000) |\n|--------------|----------|------------------|-------------------|-------------------|--------------------|--------------------|--------------------|\n|        Coverage Gap       | 0.012    | 0.033            | 0.024             | 0.014             | 0.013              | 0.012              | 0.012              |\n\n&nbsp; \n\nThe new results show that, as the Reviewer correctly predicted, Cross-CP better exploits the information in the training samples and the proposed methods start to have better results than cross-CP for a sizable number of calibration samples. This behavior is completely sensible, both cross-CP and the proposed methods utilize the training samples, but the proposed methods use them only in a indirect manner to find probability distributions (weights) for calibration labels that match general expectations of training and calibration samples. On the other hand, cross-CP methods directly use the training samples to evaluate scores and determine quantiles. Therefore, cross-CP extracts more information from training samples but does not provide general performance guarantees, require multiple training stages, and cannot be used with “black-box” prediction rules. The indirect usage of training samples in the proposed methods allows to safely reuse these samples to obtain label probabilities (weights) for calibration samples even when they have been used to train the base classifier utilized.\n\n[R] Vovk, V. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74(1), 9-28. 2015\n\n**Relation between coverage guarantees and number of samples $n$ and $m$**\n\nWe do not really understand the comment from the Reviewer, since the coverage guarantees are indeed better for larger values of $n$ and $m$. In particular, the excess coverage gap decreases with n and m as $O(\\sqrt{1/n+1/m})$ using kernel-based families of functions, as described on lines 275-284. For general families of functions, the excess coverage gap decreases with n and m with an order given by the Rademacher complexity of the family as described on lines 205-215.  In case we have misinterpreted the comment from the Reviewer, we would appreciate further guidance during the Author-Reviewers discussion period, so that we can completely clarify this aspect. \n\n**Change of terminology from “label probabilities” to “label weights”**\n\nWe agree with the Reviewer that the usage of “label probabilities” for the solutions of optimization problem (4) can be somehow confusing since such terminology may indicate an unintended probabilistic interpretation. The term “confidence” suggested by the reviewer is better, but we feel it may lead to some different misleading interpretations. We think the term “label weights” is less prone to misinterpretation and we plan to use it in the final version of the paper. We would appreciate if the Reviewer let us know if such terminology is also appropriate in his/her view.\n\n**Conventional approach for supervised split conformal prediction as a particular case of Algorithm 2**\n\nAs described by the Reviewer, the quantile obtained in the conventional approach for split conformal prediction is computed ranging only over the actual labels of calibration samples, while the quantile computed in the proposed methods ranges over all possible labels of calibration samples. The conventional approach in Algorithm 1 is a particular case of Algorithm 2 because taking in step 3 of Algorithm 2 the label probabilities (weights) corresponding to the actual calibration labels $p^*_i(y)=\\mathbb{I}\\lbrace y=Y_i\\rbrace$, the quantile obtained by Algorithm 2 would be equal to that obtained by Algorithm 1. Notice that such label probabilities (weights) are 1 for the actual labels of calibration samples and 0 for the remaining labels so that the quantiles of Algorithm 1 and Algorithm 2 would coincide since the additional values computed for the quantile in Algorithm 2 would have zero weight."}]

Author rebuttal:

Meta-review: This paper introduces a novel and theoretically sound method for split conformal prediction using unsupervised calibration, a significant departure from standard approaches that require labeled data. The core contribution is leveraging joint distribution matching to learn classification rule thresholds, which reviewers found to be a compelling and well-grounded idea. Initially, reviewers raised valid concerns regarding the empirical evaluation on larger datasets, the comparison to related work like prediction-powered inference, and practical aspects such as runtime. The authors provided a thorough and convincing rebuttal. They included new experimental results on ImageNet10, which strengthened the paper's empirical claims. Furthermore, they clarified the theoretical assumptions and contextualized their work effectively against existing literature, satisfying the reviewers' questions. The productive discussion period solidified the reviewers' confidence in the work, leading to a consensus that this is a valuable contribution.
Decision: Accept (poster)