Non-exchangeable Conformal Prediction with Optimal Transport: Tackling Distribution Shift with Unlabeled Data
Authors: Alvaro Correia
Christos Louizos
Venue: NeurIPS 2025 poster ()
Keywords: conformal prediction
optimal transport
non-exchangeability
stochastic dominance
unsupervised adaptation
Primary area: probabilistic_methods
TL;DR: We express the coverage gap from distribution shift in terms of an optimal transport objective between the calibration and unlabelled test distribution, which we then use to optimize weights for non-exchangeable conformal prediction.

Abstract: Conformal prediction is a distribution-free uncertainty quantification method that has gained popularity in the machine learning community due to its finite-sample guarantees and ease of use. Its most common variant, dubbed split conformal prediction, is also computationally efficient as it boils down to collecting statistics of the model predictions on some calibration data not yet seen by the model. Nonetheless, these guarantees only hold if the calibration and test data are exchangeable, a condition that is difficult to verify and often violated in practice due to so-called distribution shifts. The literature is rife with methods to mitigate the loss in coverage in this non-exchangeable setting, but these methods require some prior information on the type of distribution shift to be expected at test time. In this work, we study this problem via a new perspective, through the lens of optimal transport, and show that it is possible to estimate the loss in coverage and mitigate arbitrary distribution shifts, offering a principled and broadly applicable solution.

Non-exchangeable Conformal Prediction with Optimal Transport: Tackling Distribution Shifts with Unlabeled Data
Alvaro H.C. Correial
Christos Louizos!
Qualcomm Al Research"
Amsterdam, The Netherlands facorreia, clouizos]@qti. qww..omm.mmmmmmmmmmmmm com
Abstract
Conformal prediction is distribution-free uncertainty quantification method that has gained popularity in the machine learning community due to its finite-sample guarantees and ease of use. Its most common variant, dubbed split conformal prediction, is also computationally efficient it boils down collecting statis- tics of the model predictions on some calibration data not yet seen by the model. Nonetheless, these guarantees only hold if the calibration and test data are ex- changeable, a condition that is difficult to verify and often violated in practice due to so-called distribution shifts. The literature is rife with methods to mitigate the loss in coverage in this non-exchan eochancaageealee setting, but these methods require some prior information on the type of distribution shift be expected test time. In this work, we study this problem via new perspective, through the lens of optimal transport, and show that is possible estimate the loss coverage and mitigate arbitrary distribution shifts, offering principled and broadly applicable solution.
Introduction
Conformal prediction 445 (CP) works under the assumption that calibration and test data are exchangeable. Exchangeability is weaker requirement than the common i.i.d. assumption but still implies that samples are identically distributed, which hard to verify and ensure in practical applications. Therefore, is important to develop conformal methods capable of adapting potential distribution shifts or, at least, quantifying the gap in coverage caused by such shifts. In this paper, we study the effect of distribution shifts in conformal prediction through the lens of optimal transport, which proved instrumental in not only quantifying coverage gaps, but also alleviating them via reweighting of the calibration data.
We start by introducing the notion of total coverage gap: the expected coverage gap over all possible target coverage rates in [0, 1]. This metric captures the aggregate effect of distribution shift on conformal prediction and motivates the subsequent contributions, which build on this concept to provide theoretical bounds and practical strategies for mitigating the gap.
We derive two new upper bounds to the total coverage gap, formulated in terms optimal transport distances between the distributions of calibration and test nonconformity scores.
2. We show that one of our upper bounds, which requires only unlabeled samples from the test distribution, can used to learn weights w = (w; 1 for the calibration data. These weights can then be used in CP reduce the gap in coverage during test time.
"Qualcomm Research an initiative Qualcomm Technologies, Inc. tEqual contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

3. We evaluate our methods on a (toy) regression task and on the ImageNet- C and iWildCam datasets. For the classification tasks we also consider the more challenging setting which includes covariate and label shift.
The paper is structured as follows. Section 2 provides the necessary background for main theoretical results. Section [3] presents our two new upper bounds on the total coverage gap, and Section demonstrates their application reduce the coverage gap. Finally, we review related work in Section 5 report experimental results in Section 6 and conclude in Section
2
Background
In this section, we lay out the background necessary for our main results. We start with brief introduction to conformal prediction followed by an overview of optimal transport.
2.1 Conformal Prediction
Conformal prediction 45 is framework to extract prediction sets from predictive models that satisfy finite-sample coverage guarantees under specific assumptions More precisely, consider the calibration set (X1, ........ (Xn, Yn) drawn from unknown distribution P on X V. formally (X1, .....,.......................... Xn, Yn) ~ P". Given this set, conformal prediction constructs prediction sets C(X,) for new points X₁ P such that the marginal coverage property holds for any E [0, 1]:
P(Y, C(X,)) 2 1-aa
where the probability taken over the randomness of {(x,, Y) and (X,, Yt). The prediction set C(X,) is constructed using (non Jonfoornoryi scores, which quantify how well a sample fits within other samples in a set. One of the most common conformal prediction methods is that of split- conformal prediction (SCP) [29]. In SCP, score sXx,, Y;) is obtained for each point in calibration set {(x,, Y=) and at test time ())) is constructed as
C(X,) {u E ) s(X,,v) S Qa. (O)=I))
with Qo the a quantile of the empirical distribution defined by the set of scores (s(X,, Y))
The main assumption for the marginal coverage guarantee to hold is that of exchangeability; the new point (X,, Y,) needs be exchangeable with the points in the calibration set ((X,, Y.) i.e., it should follow the same distribution P(X, Y). Unfortunately, violations of the exchangcability assumption are all too common [24] and the naive application of standard SCP when (X,, Y,) comes
from another distribution ((X, Y) could produce misleading prediction sets that do not achieve the
desired coverage rate 2 2 451 Proper usage of conformal prediction in these settings requires
methods to (i) quantify the coverage gap caused by the distribution shift, and (ii) mitigate the effect of the shift on the CP procedure itself to get as close as possible the target coverage rate.
We refer the reader to I
38 for more thorough introductions to conformal prediction.
2.2 Optimal Transport: Couplings and Wasserstein Distance
Consider a complete and separable metric space (Z,c) c). where e: 2 x Z + IR is metric. Let (2) be the set of all probability measures P (Z, c) with finite moments of order p 2 1, i.e. 1z c(=0, 2))) oa for some E Z. The Wasserssti distance is metric (, that is defined for any measures P and Q in (Z( as
1/P
inf / (z QP(P TET(P.)) zxz
(2)
where T(P, Q) denotes the collection of all measures on 2 x Z with marginals P and Q. We refer to any probability measure in [[P,C Q) coupling of P and Q and use x² x((P denote p- Wasserstein optimal couplings, i.e., any coupling that attains the infimum in (2).
*Conformal prediction often described as an uncertainty quantification method, but may be more accurately viewed as an uncertainty representation technique: it conveys uncertainty through the size of prediction sets rather than assigning numerical value uncertainty.

---

Importantly, Wasserstein distances are also defined for discrete measures, and empirical measures in particular. Let Pr. and Qm denote the empirical distributions of samples { 1=; 2i P and (2/17=11 2/} Q, which induce empirical measures P, Σi= dz, and Qm ش5= dgz In that case, coupling can be captured by a matrix F, with Fs the mass to be transported from 2 to z/.
Similarly, for empirical measures the cost function induces cost matrix with Ci. 2; 2/ such that the transportation problem is given by
72
m
min CapT
subject to Irs Tis 1/m Vj E [m],
Σ
Tig = 1/n
In this work, we will be concerned with the distribution over nonconformity scores, which are typically one-dimensional. In this case, the p- p-Wasserstein simplifies to
Ws(P,Q) - -,((P.)) (1:155150--
1/p
dq
where Fp' (resp. ) is the quantile function, i.e., the inverse of the cumulative distribution function (CDF) Fp (resp. FQ) under measure P (resp. Q). For 1, we can also express the Wasserstein distance in terms of the respective CDFs
/ -F(())) dz.
W Wi(P
In this paper, focus the I-Wasserstein distance. Our main results rely solely the definitions and properties outlined here, plus basic properties like the triangle inequality. Nevertheless, the interested reader will be well served by the excellent introductions to optimal transport in [31
Theoretical Results
In this section, we define the notion of total coverage gap and introduce our main theoretical results that allow us to upper bound it. For the sake of conciseness we defer the proof' to Appendix A
We start by laying out the necessary notation. Let X E X' and Y ) be input and output variables and s x y + R be a (non)com (non)conformity score function. Regardless of the type of distribution shift (e.g., covariate label shifts) its effect the conformal prediction guarantees will manifest itself in the distribution over calibration and test scores. Therefore, in this paper we will directly manipulate the distribution of scores S s(X, Y), and to that end and test distributions over the scores, i.c., P s. s.(P) is the pushforward measure of P by 8. When P;P is absolutely continuous with respect to the Lebesgue measure on R, we write its density as P. We also use subscripts to distinguish between scores observed during calibration S, and at test time Sy. As usual, we will use uppercase letters for random variables and lowercase letters for their realizations, e.g., S₁ = St. We reserve calligraphic letters for sets, e.g., S. = {s(X,, Y) is the set of calibration scores obtained from sample of size n drawn from p", and C(X,) denotes prediction set for test variable X,.
sy P and syQ to denote the calibration
3.1 Total Variation Distance Bound
With this notation, we write the coverage under and Q as
P(Y, e c(x))) = P(S, s (a())) = Es P
Es [1 (S. < Q. (S.))
= Q(S, < Qa(S.) = Es ES [1 (S. < Q (S.))]
with Q. (S.) the 1-a quantile of the empirical distribution defined by of calibration scores S.. In general, one cannot guarantee valid coverage under arbitrary test distributions Q, i.e., we cannot ensure Q(Yrest C(Xeeot)) 2 1 Therefore, it is important to quantify the gap in coverage
3

---

induced by the change in distribution from P to Q. To that end, let ((a) denote the coverage gap for specific a value
(a) IPSS S (a.) Q(S: Qo((.))
BsSeeP P E.s.aa 1 (S. Qc((s))]] Es [Ss.aa [1,, [a(s)))]
where 1 (.) is the indicator function. It is easy to show the coverage gap is upper bounded by the total variation distance. We first restate the following well-known result for the total variation between two distributions and Q (see e.g. Farinhas al. [TO]):
Drv 2 [ Eqlgll.
for some function such that [g| S 1. It suffices to take as g(x) = P [1 (x (S.)) which is clearly bounded with [=(x) < 1 for all æ, to get Ap.o(a) S (Tv((,Q)) Unfortunately. estimating the total variation distance between P and Q without access their respective densities is impractical. Instead, in the following we will propose two different ways to get around this difficulty and effectively quantify the coverage gap. In both cases, we leverage optimal transport, which defines valid distances even for empirical measures, i.e., when we only have access to P and Q via samples.
3.2 Upper Bound on the Total Coverage Gap
We begin by defining the total coverage gap as follows.
Definition 3.1 (Total coverage gap). The expected coverage gap across all possible values a E [0. given by
AP. Ap.:= : ApQ(a)da =
with p(a) being the uniform distribution in [].
The following result establishes that the total coverage gap between and Q is upper bounded by a weighted CDF distance and the 1-Wasserstein distance between them, Wi (P, Q).
Theorem 3.2. Let P and Q be probability measures on x y with syP and s4Q their respective pushforward measures by score function : X x y + R. Assume syP is absolutely continuous with respect to the Lebesgue measure with density p., (ss)) Then the total coverage gap can be upper bounded as follows
AP. S / Pasp($e) -s.p(sa)-F dsc
(5)
(sup Pop (()) W1 S.ER
sup
(6)
Naturally, the upper bound of Theorem 3.2 is tight if there is no distribution shift, which case Wi (s, s;Q) evaluates to zero and the coverage gap is also zero by definition. Both (5) and (6) are valid upper bounds to the total coverage gap that are easy to compute in practice. It suffices to
estimate the density of calibration scores-e.g. e.g. via kernel density estimation (KDE)-and compute
the I- Wassersttei distance in (6) or the difference of CDFs in (5), all of which are easily computable from samples, especially since nonconformity scores are typically unidimensional.
3.3 Upper Bound on the Total Coverage Gap without Labels
While the above bounds are informative, they come with one crucial drawback; they require labeled samples from Q. which might be hard to obtain in practice. To overcome the need for labels, we present another upper bound to the total coverage gap that can be computed with unlabeled data from the test distribution Q. The main insight is that, although we may not have access to the score of the ground truth label, in the classification setting, we generally know the scores of all possible labels. This gives meaningful information distribution Q. which we use to construct auxiliary distributions syQ² and syQ1, whose CDFs satisfy F,,e- (t) < (t. & F.,Qu(t) (t) for all t R. This sandwiching of the CDF of (t, corresponds to a stochastic dominance relationship, denoted syQ* > x > s,Qt, and allows us to construct. bounds in the form of (5) and (6) even without access to the unknown sqQ.
the distribution of scores under the shifted test

---

Theorem 3.3. Let P and Q be two probability measures on N' x y with syP and syQ their respective pushforward measures by the score function s X x y + R. Assume syP is absolutely continuous with respect to the Lebesgue measure with density ps,p( Further let 8yQ² and s₁Q² be such that 82QT > 8yQ 7 s²Q². Then, we have that
PP.Q $ \ ʃ po) (Fapp(t)) F (so) + Fopp((s)) P
+ (s,) Fapor((e)) dsc
(7)
1 $ _/2 sup Pe, Ps.p(5o)) (Wi(s)(((())))))))))>) + (W((ssPss:s)++=[<>>sss SEER
Er [S] (x,
(8)
Theorem 3.3 tells that
upper bound the total coverage gap between the calibration distri- bution P and an unknown test distribution Q, if we can somehow find two auxiliary distributions over the test scores sqQ, such that s;Q1 > s i syQ+. Fortunately, in the classification setting, we typically evaluate the scores of all possible classes (e.g., by computing the probability of all classes with softmax activation). Thus, although the true score sxx, y) is not observed, we know must be contained in the set s szx) = {s(2, y²) 3 E V/. We can then use a set of m unlabeled samples from Q and their corresponding scores {s(z;)) V= to construct empirical distributions szQ1, and sz with the required stochastic dominance relation the unknown sy 2mQm. A natural solution is to take the minimum and maximum scores of each instance to get the following empirical distributions
8y Omin
min e(e.)
Sy Q
max
1 m
mmxx s(x.);
m
with 1 1.) the indicator function and 5_ the delta function value It easy the empirical distributions obey syQmmax >> =5Q > szQ2min as needed.
In the common setting where predictions come from a classifier f that outputs class probabilities, a practical alternative we found effective is to construct the auxiliary distributions s and sy Q( as
- Σ 8 8, U(Y)
m
sy $yQ%f.
1 VI
m Σ
S v/ (Y))x
(10)
where take the score of random label j sampled either from a uniform distribution UY) or from (Y|x), the conditional distribution given by model f. The motivation here is that SyQ% captures the scenario where the model is uninformative of the correct label, while 8y 5g reflects the scenario in which the model perfectly captures the true distribution Q(YIX). Although we cannot guarantee 5, > s > sy s,Q we empirically observe this relation hold in most cases (see Fig.
Naturally, the tightmess of the upper bounds in Theorem 3.3 depend heavily on how close s; and siQ1 are to the unknown 8y Q. In the absence of prior knowledge about the nature of the distribution shift, the best we can do is rely on the general auxiliary distributions described above, which may yield relatively loose bounds. Nevertheless, the bounds constructed using (s:Qmin sy Qmax) or (s;Q', "5,"",""UU)) syQ") serve as effective optimization objectives for reducing the coverage gap practice, through a reweighting of the calibration samples, as we explain in the following section.
Before proceeding, we note that upper bounds on the coverage gap can also be derived for restricted ranges of the miscoverage rate a. In Appendix A.4 we present bound for ranging between a and at, with 0 < a I a < 1. Additionally, Appendix A..5 provides a bound for a fixed miscoverage rate a, denoted A Ap.((a), While these bounds are less effective as optimization objectives, they offer useful theoretical insights and are detailed in Appendix A
4 Learning
In the conformal prediction literature, is common to address non-exchangeability by reweighing the calibration points 2 42 In practice, this implies that the quantile of the scores is computed on
5

---

10
5RQ
Raw
28
5
SPQ
2.8
$40 .50 mM
Likelihood ratlos
5RQ
seQ", ssq!
Proportion
SRQ
2.6
Oovervel
0.4
0.
0.2
3.0
0.0
0.2
0.4 0.6
3.8
3.0
0.0
02
0.4 0.6
0.8
1.0
Score Vallues
Target coverage
Figure 1: Empirical CDFs of nonconformity scores in ImageNet-C Gaussian noise under the calibration syP, test syQ, and auxiliary dis- tributions. We can visually verify 8; Quxx & s i siQuin and syQU i s; > sEQ11
Figure 2: Total coverage gap in ImageNet-C Fog with weights learned likelihood ra- tio estimation (orange), optimal transport with (s; Qiin sy s,Qmaxx in green, and (s;Q1, $ in gray.
weighted empirical distribution of the calibration scores By Pe with the following empirical CDF
SyPw p.
(11)
w; 2 are properly normalized weights associated with calibration samples (x,, 34). In the case of covariate shifts, Tibshirani et al. [42] show that we can recover proper coverage by setting the weights in 111 proportionally the likelihood ratio, i.e., Wl; x 4Q(=:)/aP(x.). Barber et al. [2] also rely on a weighted empirical distribution in the form of (TT) but assume the weights to be fixed based on some prior knowledge of the likely deviations from exchangeabilitty
Motivated by these ideas, we propose instead to learn the distribution 8y Pr directly by minimizing the upper bounds of Theorem 3.3 with respect to its weights un. We replace the Wasserstein and CDF distances in these bounds with their empirical counterparts (see Appendix [o. details), enabling optimization from samples. Specifically, from P and unlabeled samples (#; )ittm from the test distribution Q. These are used to construct s² and 8;Q1, As discussed in Section two alternatives we consider are to take the pair (s:Q mmQ) as in (9) or (s;Qf, 2²Q"") as in 10). However, other constructions, potentially leveraging prior information about the distribution shift or the application domain, are possible, as long as sg > s syQ+. We note that, although using unlabeled samples from the test distribution is uncommon in CP, in many cases it is easy to collect such samples in practice.
assume access to labeled samples { y4) y1))
Evaluating the bound of Theorem 3.3 admits an efficient exact solution for empirical distributions: suffices to sort the samples (n from and m from Q) to compute the difference between the empirical CDFs. Crucially, when computing weighted empirical CDFs in (TT), the weights only come into play after the score values are sorted, and thus the operation is trivially differentiable with respect w, with no relaxation needed. Finally, we estimate the density of Ps, by fitting Gaussian kernel density estimator (KDE) to the calibration scores. It is casy to fit Gaussian KDEs to weighted samples, and the estimated density also differentiable with respect to the weights.
Having established how to evaluate the bounds efficiently and differentiate through the weighting, we now tum to how these weights parameterized. We consider strategies:
Free-form weights. We directly optimize set of unnormalized weights {w; } each one tied to specific calibration point (s). After optimization, these weights normalized to form the weighted empirical distribution in (TT). This method is simple and effective, offering maximum flexibility for fixed calibration set, but it remains restricted that set.
Learnable weight function. Alternatively, we learn parametric function wa RR - R2o with W; we (s(z,, v.)) where 0 are the function parameters (c.g., small neural network).

---

Algorithm Learning Weights for Non-exchangeable Conformal Prediction via Optimal Transport
Input:
n labeled samples ((2,, ]i) from P
184m m unlabeled samples {ay [-jij=+11 from Q
score function
Initialize unnormalized weights tü = { or weight function we
Compute calibration scores (s(M;, [x)]
Compute test score vectors {I(r) ) inccludes all candidate labels s(x) (s(2, E }
repeat
Construct Q+ and Qt from {s(ry)}
I| e.g. (min, max) or (f.
Compute normalized weights:
softmax((i) Fit KDE to {s( y:) }:)] with weights w
Update vo or wy to minimize (7) or until convergence
weighted-CDF 1-Wasserstein bound
Unlike the free-form approach, this formulation allows computing weights for additional calibration points or test candidates, thereby recovering the standard weighted split-CP setting and aligning with the importance- weighting principle of Tibshirani al. 42
Both parametrizations involve trade-offs. We focus most of our analysis free-form weights because they align naturally with our bounds- based objectives, require only simple differentiable operations, and avoid extra modeling assumptions. This makes them stable and data-efficient in the small-sample regime, which is our primary concern. Nonetheless, these weights are tied to the specific calibration samples used during training, the same set must be retained for calibration. This introduces dependencies among calibration points and breaks exchangeability with the test set. Under distribution shift, exchangeability is already compromised, this violation is less critical, In this setting, the focus naturally shifts from preserving exchangeability to mitigating its effects, which is exactly what achieve by optimizing calibration weights directly. Weight functions, by contrast, offer a more general solution: by mapping scores to weights through parametric model, they can assign weights to unseen calibration points and recover the standard weighted split-CY setting. This flexibility comes at cost: training the model requires additional labeled samples from P and careful specification of its architecture. Despite these differences, both approaches achieve comparable empirical performance (see experiments in Section and Appendix
See Algorithm [ for sketch of how we optimize the total coverage gap from Theorem A more complete algorithm, including how this optimization fits into split CP is given in Algorithm 2 in Appendix C In practice, during optimization unnormalized weights {w: are mapped to normalized weights via a softmax, regardless of whether v; come from a learnable vector or a weight function wg. This normalization ensures differentiability and proper scaling before computing the empirical distribution used to evaluate the 1- I-Wasserstein or weighted-CDF bounds and fit the KDE. The computational cost remains the same in both cases: evaluating the 1- I-Wasserstein distance requires O((m (m + 12) log(m + n)) for sorting, while fitting Gaussian KDE on calibration samples costs (kk n), where l: the number of evaluation points.
Regression setting In principle, our upper bound to the total coverage gap in Theorem 3.3 is directly applicable to regression tasks. The only caveat is that the true score s(X, Y;) might no longer be restricted to finite set of known values, as in the classification setting, and designing +tQ+ and syQ* is more challenging. One can always construct these auxiliary distributions based on some prior information about the task or the underlying distribution shift, but more generally it is possible to leverage the or (s,Q5, s²QU). as we do successfully in the experiment described in Section 6.1
framework (16), and again use (s;Qumin, (umx)
Related Work
Several works have studied conformal prediction in the non-exchangeable setting, especially in the context of time series, where the exchangeability assumption violated by the very autoregressive
nature of these problems 66
13
44
18
28
46 47 50). Closer to our work, Tibshirani et al. [2
7

---

and Barber et al. 2 have also proposed to mitigate the coverage gap by reweighing the calibration samples. However, 42 their weights only address covariate shifts and correspond to the unknown likelihood ratio dQ(x)) which is hard to estimate in practice, especially under severe distribution our experiments, our methods compare favorably to learned likelihood ratios as proposed in 42 attesting to the difficulty of learning accurate ratios.
shifts and the density chasm problem [4
To our knowledge, our methods and the reweighing scheme of [2] are the only capable of tackling ar- bitrary distribution shifts in split conformal prediction. Still, their approach involves data-independent weights that must be designed priori using some prior knowledge about the underlying distribution shift, whereas we learn appropriate weights directly from few unlabeled samples from the test distribution. With the exception of the work of [32), where label shift is also tackled via likelihood
ratios in a similar fashion to 42] most other works focus on covariate shift [9 21 [25]. Among
these, 15 23
are notable for tackling covariate shifts by approximating conditional coverage
guarantees, i.e., by approximately satisfying P(;; E (X,) 2 1 a. These achieve impressive results but are computationally expensive or limited to specific types of covariate shifts.
Of special note is the work of [15], which proposes to adapt the conformal threshold for each test point, providing conditional coverage guarantees if the distribution shift comes from a known function class. In our experiments, where it is not clear how to define such function class, their method- immeremeteeeeeeeedd in its most general form via radial basis function (RBF) crrmels-producee larger prediction sets than our methods at a much larger computational cost at test time. We also compare against entropy scaled conformal prediction or ECP 2T. ECP consists in dividing the threshold, i.e., (S.). by the (1-a) quantile of the entropy over class predictions for the test points, with the intuition that high entropy (indicating high uncertainty) will decrease the threshold, leading to larger prediction sets. While this heuristic proved effective for covariate shift, the improvements in coverage were modest in the context of label shift. In contrast, our methods demonstrate greater robustness to different types of shift (see Table 6
Finally, our methods are closely related the concurrent work of 48). which also explores the relationship between the coverage gap and the WP,,, Q). However, their results are derived through a different approach and bound (a) for any a. Unfortunately, their bound does not depend on a, and is thus loose for most target coverage rates. Moreover, in practice, their methods are only applicable to distribution shifts where the test distribution is a mixture of different calibration distributions. In contrast, our bound from Theorem 3.3 can be applied to any type distribution shift.
6 Experiments
In this section, we describe and analyze a set of experiments designed to evaluate and validate our methods. In each of them, we have two sets of samples, Dp distributed according some calibration distribution P and Do according to some test distribution Q, with P differing from Q via some form of distribution shift. We divide DQ into two, with (()) reserved for fitting density ratio estimator or
learning the weights in our method as in Algorithm 1 and D4 used for testing. When no pretrained
model is available, we also split Dp, using D for training a model and D for calibration in split CP. Main experiments use 300 samples for Df² and DQ", with D extended 600 for weight functions (split evenly for fitting and calibration). Sample size effects are analyzed in Appendix
For regression tasks, we optimize the 1-Wasserstein variant of our bounds while for image classification tasks, we adopt the weighted- CDF formulation 7 These choices reflect empirical findings; each variant performs best in its respective domain, as discussed in Appendix [C.5 In all cases, we define nonconfommity scores as one minus the probabilities assigned by the model.
6.1 Regression setting with synthetic data
We start with the synthetic data experiment proposed in 44), where the ground truth likelihood ratios are known. We use the regression -asooon----ae clasissiiiiatio method of Guha et al. [16). splitting the output space into 50 equally spaced bins. In F our methods significantly enhance coverage in most cases, with no notable difference between the two variants. In this low-dimensional setting, learning the likelihood ratios also proved effective, albeit with slight tendency to under-cover. contrast, our method exhibited mild bias toward over-coverage. See Appendix C for experimental details.
8

---

16
0.0225
Uncomected
14
True Ikelihond ratios
12
0.0175
Est. likalhhodd ratios
Seg sagmas
Density
10
Density
sx0", _s=0'
0.0125
Target coverage
0.0075
0.0025
0.70
0.75
0.80
0.85
0.90
0.95
1.00
50
100
150
200
250
Coverage
Prediction Set Size
Figure 3: Distribution of coverage and prediction set sizes for the synthetic regression task across 500 simulations and target coverage rate of 90% (blue vertical line). For ease of visualization, we plot the density estimated with KDE fit to the 500 observations.
6.2 Image classification
Imagenet-C We use the established ImageNet-C [17 dataset test our methods under the covariate and label shift settings. ImageNet-C contains total of 15 covariate shifts at different severity levels, from (least severe) distribution shift, we also simulate label shift in ImageNet-C. The details can be found in Appendix C In Table T (and its extended version Appendix C) we observe a drastic drop in coverage for the uncorrected scores; from the target coverage of 90%, we drop to an average of ~ 80% for severity level 1, and to an average of 30% for severity level 5. By introducing weighting to the calibration set, our OT methods improves coverage across the board, achieving similar coverage with and without label shift. In contrast, learned likelihood ratios provided modest improvements in coverage and the ECP method of [21] only produced competitive results in the absence of label shift. Finally, the method of [15] produced good results in terms of coverage in ImageNet-C but at the cost of excessive large prediction sets (see Section 6.3 for discussion on prediction set sizes).
(most severe), but no label shift. Since our methods apply any type of
iWildCam We further use iWildCam [3] as one more dataset that contains natural distribution shifts. We can see Table that the distribution shift incurs roughly a 10% drop in coverage when not correcting the scores. While likelihood ratio weighting produce only modest improvements over the uncorrected scores, both of our OT settings improve coverage. The (min, max) setting increased coverage by more than 7% on average, while the (f, U) setting improved coverage by almost 10%. Finally, the ECP method [21 got almost perfect coverage, even under label shift. Interestingly, the method of [15) actually hurt coverage. This could be either because the distribution shift in iWildCam not well captured by the class of shifts considered their method (given by RBF kernels this experiment) or due to severe class imbalance in iWildCam, which might hamper the optimization.
Notably, the results were consistent across parametrization choices, with both the free-form and weight-function variants yielding very similar performance overall. The only meaningful differences emerged under relatively mild distribution shifts: the weight-function approach performed better on iWildCam, while the free-form variant showed stronger results on ImageNet-C at severity level one.
6.3 Discussion
Prediction set sizes. Our methods, like most other approaches to non-exchangeable CP, including the likelihood ratios proposed by Tibshirani et al. (42). and the weights introduced by Barber et al. (2). do not alter the observed test scores, thereby preserving the ranking of classes under the shifted distribution. Consequently, similar to these other works, our analysis focuses on coverage. The underlying CP algorithm (split CP) remains unchanged, and the variance in prediction set sizes attributed to miscoverage. The best achievable performance mirrors what would be obtained if labeled samples from Q were available: undercoverage results in smaller-than than-optimal prediction sets, while overcoverage leads to larger-than-optimal sets. The only exception to this is the method Gibbs et al.) which aims for conditional coverage and thus changes the conformal threshold for each test point. This decouples coverage and prediction set size, but in our experiments their methods produced larger prediction sets than other methods despite getting close to the target coverage.

---

Table I: Average coverage and prediction set size image classification tasks, with and without label shift. Results for uncorrected distributions, calibrating and testing on Q (Oracle), likelihood ratios (LR), the methods of Kasa et al. (2I) and Gibbs al. [15], and our methods with weighted-CDF objective (7). including (min, max) and U,U) variants, and free-form (FF) and weight function
(WF) parametrizations. The target coverage is set to 90%. Extended version in Table 6
iWildCam
ImageNet-C Sev.
ImageNet-C Sev.
ImageNet-C Sev. 5
Cuv.
Size
Cov.
Size
Cov.
Size
Cov.
Size
Uncorrected
78.213.
22.
78.7 16.0
2.71077
3.3
29.8
3.3
Oracle
89.7
30.5g5
89 8916
10.7272
89.9
80. 1
89.721.9
338.6 118.6
LR
79.0+2.6
23.3+4.5
811+4.9
5.2+5.8
71.3-11.9
12.3-1a.1
27..2
27.7+
Kasa al.
95.2
79.7
96.6
42. 42.4
93.7 93.7
119.3
86.1 16.4
282.0:
label
Gribs ar
67.7+0.0
109 600.6
88.942.8
5-18.5
85.6+a.6
635.7
8/..
751. 751./=1022.7
(min,, max)
4..2
37.5
91.4
15.1
88.2
63.
128.5
WF (min, max)
89.8+2.9
51.7+111
94.6+6.3
34.7+20.0
87.0-14.1
60.7 60.7-46.6
71.5+17.1
130.5+94.1
FF (1.0)
88.2+3.4
46 46.2g111
93.0
19.2::1.4
90.3
79.8
79.5
205. 7:1044
WF (F.0)
88.91a.
49.7
95.712a
36.6120.1
90.1
79.7_5o.1
78.7
200.4_ree..
Uncorrected
79.2
20.9
79.2
2.7io.s
59.2
3.2
29.8
3.3
Oracle
90.214a
43.71m0.7
90.314.5
15.0
90.213.
88.1 L97.4
90.514.
349.0
349.01a00m
label shift
LR
81.5+a.7
24,6244
84.5
6. 6.1+
72.5=12.9
14.3
47.3-221.2
27.7+ss5.5
Kasa al.
88.616
35.91174
19.2
2.7.
_9.7
3.4
$1.2
1...
Gibbs of
38.0g15.6
44.9
88.6 18.6g3.s
652.3246.0
85.5g46
638.6270.a
84.8g5.s
753. 753.5g100.4
(min, max)
13.
22.1
91.01s.7
14.3
88.41x.
62.6_m14
72.0
127.9..44.
WF (min, max]
91.3+4.
52.2215.2
93.7
33.1
87.3-12.8
69.4-47.3
70.4=19.a
129. 2:00.a
FF (f. U)
88.2+4.7
33 33.5+12.9
93.5+s.0
20.7+14.6
90.3+6.8
78.9-51.7
79.8=13.9
206.0= 106.0=108.a
WF (F.U)
91.0ga.
19.8g
95.1
36.3ga1.
90.4g7.0
80.0gs1.4
79.2g1446
201.3g168.
Bound variants. In Theorems 3.2 and 3.3 we have two flavors of upper bounds: one expressed in
the terms of weighted distance of CDFs, and another using the I-Wasserstein distance. The former is always tighter and, likely for this reason, has shown superior performance in image classification tasks. Conversely, the I-Wasserstein bounds, while generally looser, establish more natural connection to optimal transport theory and has shown better empirical performance in regression tasks. This may be due to the weighting by Ps, (s..) in 5 and which might complicate optimization.
Number of samples. Our methods are effective across varying numbers of labeled samples from P and unlabeled samples from Q. As shown in Appendix C.433] coverage improves with more samples as expected, but meaningful gains are observed even with as few as 30 samples from each distribution.
Limitations. The tightness of the unlabeled upper bounds in Theorem 3.3 depends on the auxiliary distributions stQ² and s,Qt. When these closely approximate syQ, the resulting bounds are tight, and optimizing either (7) or (8) is predictably highly effective in reducing the coverage gap. However, in the practically interesting setting of a general and unknown distribution shift we consider, the available choices for s²Q+ and s²Q² are likely less informative and yield a necessarily looser bound. Having
said that, the bounds computed with (s; Quin sy Qxxua and (s/Q1, s,QU) still perform surprisingly well in reducing the coverage gap when used for reweighing the calibration data, demonstrating their practical value and broad applicability. Nevertheless, care must be taken: in cases of minimal or no distribution shift, P may already offer better coverage than the solution to our objective. It therefore advisable first assess the presence of distribution shift, potentially using unlabeled samples from Q, before applying our methods. We explore this issue further in Appendix C
7 Conclusion
In this work, we employ optimal transport theory study the effect of distribution shifts on conformal prediction. Specifically, we derive upper bounds on the total coverage gap induced by a shift from the calibration distribution P the test distribution Q, expressed in terms of (weighted) CDF and Wasserstein distances. Recognizing that labeled examples from Q are often unavailable in practice, we extend our analysis by leveraging the structure inherent in the nonconformity scores of the unlabeled test data. To this end, we construct auxiliary distributions s, and syQT, which enable label-free bounds of the coverage gap. Furthermore, we utilize these bounds as optimization objectives to learn importance weights over the calibration data. Empirically, our approach significantly reduces the coverage gap across range of distribution shift settings.
10

---

References
[1] Angelopoulos, A. N. and Bates, S. A gentle introduction to conformal prediction and distribution- free uncertainty quantification. arXiv preprint arXiv:2107.075/1, 2021.
[2] Barber, R. F., Candes, J., Ramdas, A.. and Tibshirani, R. J. Conformal prediction beyond exchangeability. The Annals of Statistics, (62)))
[3] Beery, S., Cole, E., and Gjoka, A. The iwildcam 2020 competition dataset. arXiv preprint WMXi:2200.113340 2020.
[4] Bellotti, A. Optimized conformal classification using gradient descent approximation. arXiv preprint arXiv:2 1255,, 2021.
[5] Caprio, M., Stutz, D., Li, S., and Doucet, A. Conformalized credal regions for classification with ambiguous ground truth. Transactions Machine Learning Research, 2025, ISSN 2835-8856. URL htt.hhttts//ppeeeiiiiiiiee
[6] Chernozhukov, V., Wüthrich, K., and Yinchu, Z. Exact and robust conformal inference methods for predictive machine learning with dependent data. In Conference on learning theory, pp. 732-749. PMLR, 2018.
[7] Correia, A., Massoli, F. V., Louizos, C., and Behboodi, A. An information theoretic perspective on conformal prediction. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 6 November 2024.
[8] De Angelis, M. and Gray, A. Why the 1-wasserstein distance is the area between the two marginal edfs. arXiv preprint arXiv:2 11.0570, 2021.
[9] Dvoretzky, A., Kiefer, J., and Wolfowitz, J. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pp. 642-669, 1956.
[10] Farinhas, A., Zerva, C., Ulmer, D. T., and Martins, A. Non-exchangeable conformal risk control. In The Twelfth International Conference on Learning Representations, 2024.
[11] Foygel Barber, R., Candes, E. J., Ramdas, A., and Tibshirani, R. J. The limits of distribution- free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2): 455 482, 2021.
[12] Garg, S., Erickson, N., Sharpnack, J., Smola, A., Balakrishnan, S., and Lipton, Z. C. Risbench: Domain adaptation under relaxed label shift. In International Conference on Machine Learning, pp. 100879-19920 PMLR, 2023.
[13] Gibbs, I. and Candes, E. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34:1660-1611 1672, 2021.
[14] Gibbs, I. and Candès, E. J. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 25(162)) 1-36, 2024.
[15] Gibbs, I., Cherian, J. J., and Candès, E. J. Conformal prediction with conditional guarantees. arXiv preprint arXiv:2305.J 12616, 2023.
[16] Guha, E. K., Natarajan, S., Möllenhoff, T., Khan, M. E.,, and Ndiaye, Conformal predic- tion via Representations, 2024.
In The Twelfth International Conference Learning
[17] Hendrycks, D. and Dietterich, T. Benchmarking neural network robustness to common corrup- tions and perturbations. Proceedings of the International Conference Learning Represenia- tions, 2019.
[18] Jensen, V., Bianchi, F. M., and Anfinsen, S. N. Ensemble conformalized quantile regression for probabilistic time series forecasting. IEEE Transactions on Neural Networks and Learning Systems, 2022.

---

[19] Jin, Y.. Ren, Z., and Candès, E. J. Sensitivity analysis of individual treatment effects: A robust conformal inference approach. Proceedings of the National Academy of Sciences, 120(6): 022148891200 2023.
[20] Jones, M. C. Simple boundary correction for kernel density estimation. Statistics and computing, 3:135-146, 1993.
[21] Kasa, K., Zhang. Z., Yang, H., and Taylor, G. W. Adapting conformal prediction to distribution shifts without labels. arXiv preprint arXiv:2406.014460 2024.
[22] Kingma, D. P. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.660 2014.
[23] Kiyani, S., Pappas, G., and Hassani, H. Length optimization in conformal prediction. arXiv preprint arXiv:2406. 18814, 2024.
[24] Koh, P. W. Sagawa, S., Marklund, H., Xie, S. M., Zhang, M., Balsubramani, A., Hu, W., Yasunaga, M., Phillips, R. L.., Gao, I., et al. Wilds: A benchmark of in-lhe-wild distribution shifts. In International conference on machine learning, pp. 5637-5664. PMLR, 2021.
[25] Lei, L. and Candès, J. Conformal inference of counterfactuals and individual treatment effects. Journal of the Royal Statistical Society Series B: Statistical Methodology, 83(5):91 (3(5):911-938, 2021.
[26] Liu, Y., Kothari, P., Van Delft, B., Bellot-Gurlet, B., Mordan, T., and Alahi, A. Ttt+:: When does self-superrised test-time training fail or thrive? Advances Neural Information Processing Systems, 01:21808-2100 2021.
[27] maintainers, T. and contributors. Torchvision: Pytorch's computer vision library. https
//github.com/ http://.wo.mooppto////ossiteteee 2016.
[28] Oliveira, R. I., Orenstein, P., Ramos, T., and Romano, J. V. Split conformal prediction and non non-exchangeable data. Journal of Machine Learning Research, 25(225): 2024.
[29] Papadopoulos, H., Proedrou, K., Vovk, V., and Gammerman, A. Inductive confidence machines for regression. In Machine Learning: ECML 2002: 13th European Conference on Machine Learning Helsinki, Finland, August 19-23, 2002 Proceedings 13, pp. 345-356. Springer, 2002.
[30] Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang. E., Vito,o, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A. Automatic differentiation in pytorch. In NIPS W, 2017.
[31] Peyré, G., Cuturi. M., et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 1 11(5-6):355-610 2019.
[32] Podkopaev, A. and Ramdas, A. Distribution-free uncertainty quantification for classification under label shift. In Uncertainty in artificial intelligence, pp. 853. PMLR, 2021.
[33] Qiu, H., Dobriban, E.,, and Tchetgen Tchetgen, E. Prediction sets adaptive to unknown covariate shift. Journal of the Royal Statistical Society Series B: Statistical Methodology, 1565::1680 1705, 2023.
[34] Rhodes, B., Xu, K., and Gutmann, M. U. Telescoping density-ratio estimation. Advances in neural information processing systems, 33:4905-4916 16, 2020.
[35] Romano, Y., Sesia, M., and Candes, E. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581-3591, 2020.
[36] Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma. S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115:211-255 2015.
[37] Scott, D. W. Multivariate density estimation: theory, practice, and visualization. John Wiley & Sons, 2015.
[38] Shafer, G. and Vovk, V. A Tutorial on Conformal Prediction. Journal of Machine Learning Research, 9(3), 2008
12

---

[39] Stutz, D., Dvijotham, K. D., Cemgil, A. T., and Doucet, A. Learning optimal conformal classifiers. In International Conference on Learning Representations, 2022.
[40] Stutz, D., Roy, A. G., Matejovicova, T., Strachan, P., Cemgil, A. T., and Doucet, A. Conformal prediction under ambiguous ground truth. Trunsactions on Machine Learning Research, 2023, ISSN 2835- 8856. URL htlLhtts:/// httttp::///penreviiee
[41] Sun, Y., Wang, X., Liu, Z., Miller, J., Efros, A., and Hardt, M. Test-time training with self- supervision for generalization under distribution shifts. In International conference machine learning, pp. 9229-9248. PMLR, 2020.
[42] Tibshirani, R. J., Foygel Barber, R., Candes, E., and Ramdas, A. Conformal prediction under covariate shift. Advances in neural information processing systems, 32, 2019.
[43] Villani, C. Optimal Transport: Old and New, volume 338. Springer Science & Business Media, 2008.
[44] Vovk. V. Conditional validity of inductive conformal predictors. In Asian conference machine learning, pp. 475-490. PMLR, 2012.
[45] Vovk, V., Gammerman, A., and Shafer, G. Algorithmic Learning in a Random World. Springer, second edition, December 2022. ISBN 978-3-031-066443 doi: 10. 10.110079978---01--66666
[46] Xu, C. and Xie, Y. Conformal prediction interval for dynamic time-series. In International Conference on Machine Learning, pp. 11559-1 1569. PMLR, 2021.
[47] Xu, C. and Xie, Y. Conformal prediction for time series. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(10):11575- 2023.
[48] Xu, R., Chen, C., Sun, Y., Venkitasubramaniam, P., and Xie, S. Wasserstein-regularizedd confor- mal prediction under general distribution shift. In The Thirteenth Internatiional Conference Learning Representations, 2025. URL /ttctps://opereviiie
[49] Yang, Y., Kuchibhotla, A. K., and Tchetgen Tchetgen, E. Doubly robust calibration of pre- diction sets under covariate shift. Journal of the Royal Statistical Society Series B: Statistical Methodology, pp- qkae009, 2024.
[50] Zaffran, M., Féron, O., Goude, Y., Josse, J., and Dieuleveut, A. Adaptive conformal predictions for time series. In International Conference on Machine Learning, pp. 25834 25866. PMLR, 2022.
13

---

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: Our theoretical results all proved in the supplementary material, and our experiments support the claim that our methods are effective at mitigating the coverage gap in conformal prediction under a variety of distribution shift settings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No 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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We elaborate on the limitations of our method Section 6.3
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 a 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 (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in 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 approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
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 '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 complete (and correct) proof?
14

---

Answer: [Yes]
Justification: All theoretical results are accompanied by the necessary assumptions and thorough derivations. The complete proofs are all in the supplementary material.
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 theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or 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 ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We describe our experimental settings in details in the supplementary material. We also intend to make the source code available, subject to company approval and applicable policies.
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.
If the contribution is 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 fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access 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.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
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 or way to reproduce 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 particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
15

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All datasets used in this paper are already open source and readily available. We intend to make the source code available, subject company approval and applicable policies.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for 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 (https
/ /twpps.cc/puuiie.e wwtpcccppppccccceeeoec
www.eeeee/oeeemmmeeeeeee commmmssions asssonoooicy 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 as much information as 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 understand the results?
Answer:
[Yes]
Justification: All relevant details for all experiments are described in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We repeat all experiments across different random seeds. For the image 10 random seeds and report the mean and standard deviation
classification tasks, of these results. For the synthetic regression task, we use 500 random seeds and plot the distribution of empirical coverage and prediction sizes.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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 error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 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]
Justification: All experiments were run in a single commercial GPU, as mentioned in the supplementary material.
Guidelines:
The answer NA means that the paper does 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 make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
We conform with the NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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 jurisdiciio))
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: All paper primarily theoretical in nature and of limited direct societal impacts. Yet, we do discuss its broader impact in the supplementary material.
17

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or 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 specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that 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 out that a generic algorithm for optimizing neural networks could enable people 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe 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]
Justification: [NA]
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 requiring that users adhere to usage guidelines or restrictions to 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:
All resources used in the paper are appropriately cited and referenced.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or 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.
18

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not introduce any new assets at the moment. We intend to make the source code available, subject company approval and applicable policies. That would come with the proper documentation for reproducing the experiments.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/mmodll 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 anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
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 contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer:[NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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 is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The core methods of this research do not relate to L.MSs.
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 htte:://hberrrre.ccc///oeeeerers for what should or should not be described.
20

---

Broader Impact
This work introduces new methods to enhance the coverage of conformal prediction under distribution shifts, which frequently occur in real-world applications. We believe our contributions will have a positive impact, encouraging practitioners to adopt uncertainty quantification techniques like conformal prediction, provided the underlying guarantees are well understood.
A Proofs and Additional Theoretical Results
In this section, provide detailed proofs of our upper bounds to the coverage gap as well as extra theoretical results. We start by providing the proofs of Theorems 3.2 and 3.3
A.1 Bound to the Total Coverage Gap
Theorem 3.2
Let P and Q be probability measures X x y with sy P and syQ their respective pushforward measures by a score function x y + R. Assume sy P is absolutely continuous with respect to the Lebesgue measure with density (8.)( Then the total coverage gap can be upper bounded as follows
APQ & / Posp((e) (F.p(8))Fa,,10000 dec
$ sup Po Po. (i ( REE
Proof.
AP.Q = /// R.SnsspP Bs ([ (St Sa(()))
- Es pm Es (S. $ [o da
(12)
Es.wsyIn
F (sgr(Qu((.)) - F da
(13)
Ese pm
(ap Ps do
(14)
J0
ESsyaap
F -
-F,
(15)
ESS.ayP"
(5,p(())-
(16)
(sc)
(G.p(s))FFae((52)) dsc
(17)
JR
/ (Papp(se)Faae(ttt) doa
< sup ((ee)
(18)
S.ER
= sup (se) SEER
Ws(ssPss4Q)
(19)
where the first inequality in 14) is due to Jensen's inequality and (15) holds because the empirical
quantile Q. (S.) must evaluate to one of the n values in S, {=e ,...,8e
(())), ). each which takes 1
(n))
n
of the [0, range. In (15), we have the expectation of the sample mean, which equals the expectation
of the population as in (16). Lastly, (18) holds because Ps, ((.)) a density and thus non-negative
everywhere, and [99 follows directly from the definition of the 1- I-Wasserstein distance, as in 44. D
21

---

Remark A.1 (On the expectation under weighted measure). The bound in Theorem 3.2 extends to any weighted calibration measure Pe with density p(s) (s)) where p E [0, 20) satisfies
[ p(s
In this case, the total coverage gap is upper bounded by
(=) P S p(())s,p(s) (s) - (spp)00) (it)) otQ). SER
The proof follows identically by replacing Ps, with p(s) in the argument.
Remark A.2 (On practical weighting). In experiments (Section 4), weights are applied at the sample level, forming weighted empirical measure rather than continuous density. These weights not globally normalized; instead, normalization is enforced through softmax or similar constraint during optimization. Our theoretical result assumes normalized weighting function p. ensuring Po is a probability measure. This is a stronger condition than what is used in practice, but the empirical approach approximates this normalization. Moreover, the bound holds for the empirical distribution defined by calibration dataset as shown in Proposition A.3 below.
Proposition A.3 (Empirical weighted bound). Let s:P Ei= Wy 6 (a) be the weighted empirical measure over calibration scores {s(*) |==1 with weights w, and E
1. Let F frr and o denote the CDFs of PH and an arbitrary test distribution over scores 8; Q. respectively, Define the weighted quantile function Q (a)
(a) and the empirical weighted coverage gap F- P.
A .m.Q = S.'
B Beswes P. [RS
(S. S Q (a)) Es, ~
- ol (St s Q7 (x)))]]]] do.
Then
71
i QuQ S
Σ Wi sy F (s ( Fafo(s
Proof. By definition and the tower property,
iu.Q 1 [ Far (Q) (Q, da.
Applying Jensen's inequality (absolute value is convex),
B Bno S B Pro [ [/ (Q (Q - Fs (Q"
(Q)) (
da
1 im Since syPr is a discrete distribution with atoms {sc Ji=1 and masses {wi)==> its quantile map + (a) takes the value ( on an interval of length exactly wy, Therefore, for any fixed realization of S.,
L (a.A((Q0))) - (., da = Σ w; F (s( Fs.
Taking expectation with respect S. sy fow does change the right-hand side, which is deterministic given PW and the claim follows.
A.2 Unlabeled Bound to the Total Coverage Gap
Before proving Theorem 3.3 we begin by recalling the concept of stochastic dominance, which plays a key role in the argument. Specifically, if A and B are two probability distributions on R. we say A dominates B, denoted A B, if F (1) < (!) for all & E IR. This notion is especially useful in our context, as will made clear in the derivations. In particular, stochastic dominance also simplifies the computation of the 1- I-Wasserstein distance, captured by the following well-known result.
22

---

Lemma A.4 (De Angelis & Gray 8). Let A and B be two probability distributions on R, with > B, then
(), [A[x] [
Theorem
Let P and Q be two probability measures on X with sy P and syQ their respective pushforward measures by the score function s X x y + R. Assume syl is absolutely continuous with respect to the Lebesgue measure with density Ps₂ p(.)). Further let sqQ and sy syQT. be such that syQm t s.Q syQ'n Then, we have that
PP.Q S S / Perp(se) [Fesp((e) F. s0 (5o) + Fo(p(s)) Faggeth (8o)
+ F s. (80) - F so (80) dsc
< sup ps, ploa) (Wi(e)P, WW + +B,0t. [S] s, [5] 151) EcER
Proof of 7 We start from (5) and apply the triangle inequality twice to get
A.. $ / Pa.p(sc) (Fsp((s)) F F. (sc) + Fa.Q(se) F F, (se)) dsc
Ar. / Parp((s) (Fay((s)) F et.. (8o) + [F.e((0)= - st (80)) doc
Since all values in these inequalities are non-negative, we can add them up get
P..Q $ 1 / po.p(se) |Fasp(()) oz (8c) + Fopp(sc) -F e. (sc) (aap((s) - F F. (8o) + |Fase(s)) F, (80) doc
1 / Popp((e) |Fagp(5)) Fr (8c) + FFgp(sc) - F Fr (se)
2
+ Ps)0(()) - F Pejet (8c) + F Fe Fago((e) doc
= f Popp(se) (Pajp(()) (Far(tt) F Fo (8c) + Pa.r(Sc) - - Fr (sc)
+ +F (6c) F Fegqi. (6o) )osee
where the first equality holds because of the stochastic dominance relationship, which tells us that F o. (1) < (t) and (t) < F o, (1) for all e R.
Proof of 8). The result follows from by taking the maximum of P out of the integral as in the
proof of Theorem 3.2 Alternatively, we can also prove (8) directly from (6) in Theorem 33.2 For that, it suffices to show W1 sy) is upper bounded by the term in parentheses in (8) and the proof immediately follows from Theorem 3.2
We start by applying the triangle inequality twice get
Wiss < Wi + (1:
Wigs +, s Wi(s;P, s;QH. + (s;
Since all terms neganegative, sum both incqualities, which gives us
(s; sqQ) s Wi (sy St. + + + (
Qs (20)
23

---

Using stQu > s:Q > s:Q we have from Lemma A.4 that Wi(s;Q. Qm
[S] stt.
@ and (1(s Ex, E ,, tm [S],
and by summing both equalities, the unknown expectations _ cancel out, giving us
Wi (s+ sy (h) + (i(s; 8tQ E 0. [S] E, st.. [S]. Finally, it suffices to plug eq.
(21)
21 into eq
20 and the proof follows directly from Theorem
Remark A.5. It is interesting to note that, if s4Qm & spP & s4Qin the upper bound simplifies to
/ Pasp((s)
P
( Feaaat (5o) - F. F2 (5x) dsc-
A.3 Estimating the Upper Bounds to the Total Coverage Gap from Samples
In practice, we often do not have direct access to the distributions themselves and have to rely only on samples. Next, we show how to estimate our bounds from samples by leveraging the wvoretay-KKifee--ooolow
(DKW) inequality 9 to get finite-sample guarantees. We now proceed to show how the upper bounds from Theorem 3.2 can be estimated from samples.
Theorem A.6. Let P and Q be two probability measures on X x y with syP and syQ their respective pushforward measures by the score function Xx - R. Let sy Pn. and syQ denote their empirical distributions constructed from n and m samples, respectively. Then, we have with probability at least 1 2d that
AP. $ / (pgr(()) Pa - F F((((8)) ds. 1 /og((/d))
log(2/d)
+
2n
2m
+1001(211)
(log(2/d)
log(2/d)
<
(( Wi Wa + SEER
2n
2m
Proof. We start by applying the triangle inequality twice get
APQ / Pay ((sa) Papp(s)) (s))( ds + / payp((e) Fage((e) F (s)) doc
$ / (osp((e) F.gR, (8c) -F,,0(8e) dsc
/ papp(s)) Fsyp(sc) (FF((s)) - F P. (sc) dsc + / papp(se) Fs,g((e) - F ((c) dsc
From here, we get the weighted CDF version of the bound by applying the DKW inequality to the last two terms. This gives us that, with probability at least 2d
/ (s))((s) F.g (sc) FF Fo) ds.
Anq &
f Papplsdy log(2/d)
ds. / Pso Ps.)(
log(2/d)
ds.
2n
2m
/ ps))( Pa (sc) - F (0(60) dsc +
(og(2/d)
log(2/d)
2n
2m
The last equality holds since the DKW correction can be pulled outside of the integral and the integrals then sum to one due to (s,e) being probability density. Finally, once more we can use the fact that Ps, ((e)) is non-negative everywhere to get
I pls) F.PAA (so) F. (sc) ds. <
<tesssss (sup p(,) W1 (spPpn st))), R.ER
which gives us the bound expressed in terms of the I-Wasserstein distance.
24

---

Remark A.7 (Extension to unlabeled bound). The upper bounds in Theorem 3.3 can also be estimated from samples in similar manner. In fact, to get the unlabeled version of Theorem A.6 it suffices to construct two auxiliary empirical distributions such that sy Q o sqQ > sq sqQu and follow the same arguments used to derive Theorem 3.3 from Theorem 3.2
Remark A.8. The DKW inequality only applies to i.i.d. samples. Therefore, to compute the bound after having optimized the weights in syPa" distribution, where nrw 1/E =f is the effective sample size of syPrt We then evaluate the bound in Theorem A.6 using these new samples and replacing n with Rww
first resample Row samples from this weighted
A.4 Restricted Total Coverage Gap
Thus far, we have discussed the total coverage gap, A P.Q. which considers miscoverage rates over the full range [o, I] and underpins the main results of this paper, as well as the coverage gap for specific miscoverage rates, (p)) introduced in Appendix A.5
In some scenarios, interest may lie in restricted range of miscoverage rates rather than the entire interval [0, 1]. To accommodate this, the definition can be extended to a range [a_,a" a,a' with S a S such that
aat An.((a) Ar.(a (aqla"(at)=: = f
at - da
(22)
For the restricted coverage above, have the following result. Proposition A.9 (Restricted total coverage gap). Let P and Q be probability measures on X' y. and let X x y + R be measurable score function with pushforward measures s P and s Q. Assume & P absolutely continuous with respect to the Lebesgue measure on IR with density P
and CDF F. P. For 0 < a- < a < 1, define
pat
A at) = at a Jo- Ar.((a) da,
Then Ap.Q(a ,at) is upper bounded by
- S1 Peup((e) ((gp((s) - ((c) 1 1s5c [Fagplaa), F dds. dsc. (23)
at a
Proof. The proof is close that of Theorem 3.2 following similar steps. By definition and the Jensen's 's inequality, we know that
Ap.)(a)
Es pm (a,P(Qn((.)) (Q, -.
ES pm (a.p(Qu((S)) Fs (Q.
Averaging over E [aT,aa" and applying Fubini to swap the order of integration,
a aa a- [ (Fau((Q((S.)) F. (QQa da
Ar.q(a aa*)== < B
(()) sorted increasingly. Over the full range [0, 1]. each calibration score occupies interval of length 1/n in the quantile map. Restricting [a aa=a+] simply zeroes out scores whose CDF lies outside this range. Thus
Now fix S. = {s. (1)
[_ FagP(Qu((.)) Feg Fe (Qa() da=
Σ
E jaa (F aat)) F Fegr(s!?) - Fsaa(s!!))
25

---

Note that this is the same argument of (15) in the proof of Theorem 3.2 but here we take extra care to restrict the range [a aat]. Plugging back we have
A aat) S Es. N P
Σ
(Fe))(())) (a=a"") |Fa - (
Since the calibration data point is identically distributed, the expectation of the sample mean equals the population mean:
n M(s!2)
E E P
Es (h())]
n
-1 with - (Fan)((())) E la ,itl) [ ( Pa
) Therefore,
at-aa- S Paupls) Foup(s) - Faue(s) 1 ( Ela_aati ds, Ar.Q(a ,at) at at a
which is the desired bound.
Remark A.10 (On Wasserstein relaxations). is also possible to connect the result of Proposition A.9 to the 1- Wasssersteinn distance. Since (-) S 1, a loose relaxation of (23) gives
AP.Q(a ,at a+ a- ( sup Pap ((a))) / Fa (sg)(()) Fs ds E.Ek
sup Pag p(,.) Wi(s R.ER
a++
which may be overly conservative in practice.
While one could optimize the upper bound in Proposition A.9 directly, preliminary experiments show that this approach yields only marginal improvements coverage. We see two likely reasons for this. First, optimizing a bound restricted to a specific coverage range may be inherently more challenging: for instance, the pointwise bound for fixed a in Appendix Al55 failed to deliver better empirical performance. Second, the total coverage gap already provides a strong and well-behaved objective, leaving little room for alternative formulations to offer significant gains. Nevertheless, these more targeted objectives remain an interesting direction for future work, particularly in applications where coverage guarantees over a narrow range of are critical.
A.5
Upper Bound to the Coverage Gap for Specific Target Miscoverage Rate
As discussed in the main paper, similar techniques can also be employed to derive upper bound on (p. the coverage gap corresponding to a given miscoverage rate a. This result formalized in Theorem A.1I which also outlines how it can be estimated from samples using the DKW inequality.
Theorem A.11. Let P and Q be two probability measures on X Y with s and syQ their respective pushforward measures by the score function s : X x y - R. Let sy and sqQm denote their empirical distributions constructed from n and m samples, respectively. Further, let sg Qin and 8, 2t be such that 8; b 2m b 5tQ2t. Then, we have with probability at least 1 2d that
Ap.((a= < 2 Es || (0) - -F Os (2o()
1
(8.)
+ F P.p., (Sa(S))) - Fr (Qa(S))) + F.,Ot. (Sa) F,, (Qa())))
Tog(2/d) (2/d)
(2g(2/d)
+
2n
2m
26

---

Proof. Per definition the coverage gap for a specific target miscoverage rate a is given by Ar.((a) = P((s s Qa()))
- Q(S, = (s.))
Es Bs
[ (S, - Qu. (5.))
- Bs
Ps
[Ss s Qa (S.))
BS pm (apP(Qa(S.)) - Fa F4e (Qee(Q((So))
$ ES (o,p((a((s)) -
where the last inequality follows from Jensen's inequality. At this point we introduce the empirical distributions spPr and s;Qm by applying the triangle inequality twice.
(p. & Es p p (So( - (Qn(())
+ FapP(Q((Ss) F.P.. (Q.(
I Es | (Qo(S.)) P 2m (Qn(
+ F Fapp(Qu((S)) - - s. (Ca(S))) + Fo F. (Qa(s)))
We then apply the DKW inequality to get with probability 1 2-2d
(p.((a) s Pm p [F (Q.) F F.q... (2.(
1oo log(2/d)
log(2/d)
+V
+
2n
2m
Finally, we introduce the two auxiliary distributions 8; st > 8 > 8,Qt. by once more applying the triangle inequality twice and summing the inequalities to get the final result.
Unfortunately, preliminary experiments indicate that the bound presented in Theorem A. is loose and of limited practical utility, unless the auxiliary distributions are close the true score distribution under Q. Further research is required to derive meaningful bounds for specific values of a in the absence of labeled data. Nevertheless, if the goal to enhance coverage
a particular a, one can
directly optimize the bound in Theorem 1. Following prior work 4 7 39 this can be achieved by introducing differentiable relaxations in the computation of quantiles and empirical CDFs, thereby enabling gradient-based optimization with respect to the weights in sy for However, this approach has proven less effective than optimizing upper bounds on the total coverage gap.
27

---

B Applicability, Limitations, and Extensions
Prior-Knowledge-Baaee Sandwiching Design. Our bounds in Theorem 3.3 rely on auxiliary distributions (syQu: ST that stochastically dominate the unknown test score distribution syQ. In the absence of prior knowledge, we use uninformed constructions such as (min, max) or (f. U), which work well empirically but may yield loose bounds. A natural extension is to exploit domain- specific or structural prior information to design tighter sandwiching distributions.
For example, if labels are organized in a hierarchy (e.g., ImageNett superclasses), side information can constrain the feasible set of candidate labels for each test point. This allows constructing 8yQr and stQ+ by selecting the most plausible and least plausible labels within that subset, leading to provably tighter bounds. Similarly, if the distribution shift is known be bounded (c.g.. perturbations within an Loo ball), optimization procedures can identify feasible score ranges that respect these constraints. The smaller the feasible set, the closer the auxiliary distributions approximate S improving both theoretical guarantees and empirical performance.
Exploring these strategies (hierarchical constraints, perturbation models, other structured priors) represents a promising direction for future work, as it bridges the gap between general-purpose bounds and application-specifie robustness.
Robustness to Misspecification. Our bounds in Theorem 3.3 assume that the auxiliary distributions ( satisfy the stochastic dominance relationship s;Q+ ; sy > syQu This condition is guaranteed for the (min, max) construction and was observed to hold in many experiments for (J,U), which uses scores derived from the model's predicted distribution (x({ and from uniform distribution over labels. However, (J, U' does not always satisfy this assumption.
Coverage improvements in these cases can be explained by the fact that the optimization objective remains effective whenever the auxiliary distributions help move the calibration score distribution closer the test score distribution. This alignment, even if imperfect, can still reduce the coverage gap. However, this is an important caveat: if the auxiliary distributions fail to capture the nature the shift, optimization may bias the calibration distribution in the wrong direction and worsen coverage. Handling this risk requires care.
Future work should systematically study these failure modes and develop safeguards. Promising directions include diagnostics to detect dominance violations, adaptive refinement of auxiliary distributions based empirical checks, and regularization strategies prevent extreme deviations when auxiliary distributions are poorly aligned with the test distribution.
Ambiguous ground truth arises in settings where each instance may correspond to multiple plausible labels with associated probabilities, such as in fine-grained classi- fication scenarios with inherent uncertainty. This problem has recently attracted attention in the conformal prediction literature [5] [4]]
Ambiguous Ground Truth.
Our method operates directly on nonconformity scores, which are typically unidimensional, without imposing any assumptions on how the scores are constructed. This property makes it naturally compatible with most CP techniques, including scenarios involving ambiguous ground truth. For example, following Stutz [40], one can define score function as a weighted average of class-specific scores under plausibility vector À E AK, i.c.
8' (c, = Σ N (55 k=1
Once such score is defined, our approach can learn weights over the calibration data and compute threshold that adapts under distribution shift, just as in the standard setting.
The main challenge lies in constructing auxiliary distributions for ambiguous ground truth. Instead of working with discrete of labels, we must consider distributions over the simplex, which complicates the design of (sg Q Q1 8; 2t).. While min-max construction remains possible, it may be overly conservative, the resulting auxiliary distributions could be too far apart yield tight bounds. Future work could explore more informative strategies for building auxiliary distributions in this setting, potentially leveraging prior knowledge or structural constraints on the plausibility vectors.
28

---

C Extra experimental details and results
In this section, we present additional details about our experimental setup and supplementary results. We begin by outlining how our methods fit within the split conformal prediction framework in Section C.I and specifically in Algorithm [ Next, we detail the baseline methods in Section C.3
followed by a description of the datasets used Section C.4 Finally, in Section C.5 we discuss key design choices and ablation studies that may offer valuable insights for future research.
Before proceeding, we comment on few technical details. We note that the code was implemented in Python 3 using Py TyTcrh [30] and all experiments were conducted on a single commercial NVIDIA GPU with 12 GB of memory.
Algorithm 2 End-to-end Non-exchangeable CP with Optimal Transport (Split CP)
Input:
n labeled samples {(Trs )= from P
m unlabeled samples {zy 12+m j=n++1 from Q target miscoverage a E (0, 1)
score function Initialize unnormalized weights v = [w: Ji or weight function wp Compute scores {s(1,, y)))
Compute score vectors (s(x,)) + repeat
I1 aa (s(a, v) y E y}
Construct St and st from {s(x))]j=mH Fit KDE to {s(,,, }:) with weights w Update Ü or wy to minimize either or until convergence or max steps
Il c... (min, max) or (f. U)
weighted--CDD CDF Wassersttii bound
Weighted normalization: Compute normalized weights w Weighted threshold: 91-a + Q" (fs(z;, ys));-n)
If accounting weight of test point
Prediction sets: for each 2t, set C(z,) + { y s(1,, y) S 91-a Output: {C(x)))== (if {xt} provided) and learned weights w
C.1 Split Conformal Prediction Procedure
We follow standard split conformal prediction framework, with the main difference being that introduce weights over the calibration nonconformity scores to better align their empirical distribution with that of test scores. Concretely, we construct prediction sets by thresholding the nonconformity scores given by one minus the model-assigned probabilities. However, our methods are agnostic to the choice of score function and could be applied other approaches like APS 33). We outline the complete split CP algorithm we use, including weight optimization with our bounds, Algorithm
C.1.1 Weighting of Test Samples
In standard split conformal prediction, test data point is implicitly assigned weight of 1/++1, preserving symmetry with the calibration set. Extensions to non-exchangeable settings like 2 42 also address this issue explicitly. Tibshirani et al. 42 propose assigning the test point a weight proportional to its likelihood ratio under the shifted distribution (see details in Section C.3.2). while Barber et al. [2] fix the unnormalized weight of the test point to 1, reflecting the fact that it already comes from the target distribution.
Free-form weights We adopt a similar convention of for free-form weights, assigning test points the unnormalized weight t 1. Intuitively, importance weights are meant to correct for distribution mismatch, and the test point already drawn from the target distribution, which justifies unit weights. In that case, we have the following weighted empirical distribution 8y P
8y fo n
wids(ar)))) with normalized weights
W;
1 Σ 1 17
29

---

Weight Function When using weight function, we adopt similar strategy to that of Tibshirani al. 42). Unlike their setting. where the weight function maps inputs z to weights, our function maps nonconformity scores weights. Consequently, for each candidate label E y we obtain distinct test weight wh (s(x+11 y)). Computing all these weights can be expensive when [>] is large. To mitigate this cost, we approximate the test weight by taking the maximum over the score range [smin 5max] to get a conservative upper bound for the conformal threshold:
Wn+1
max a6 Pmin Amane
We (g)s).
In our classification experiments, we define nonconformity scores as one minus the probabilities assigned by the model, with [smin, Smax] = [0. 1]. For calibration points, we compute unnormal-
ized weights directly as W; = (s ()): for E mZ]. Finally, the weighted empirical distribution st P is given by
P Σ we
with normalized weights
20
m 2j=1 W
C.2 Other Implementation Details
In all experiments, free-form weights are randomly initialized from a uniform distribution in [0. 1] but mapped to log space for stability. When learning a weight function, we implement it as a small multi-layer perceptron (MI.) applied directly to scalars representing nonconformity scores. In all cases, the architecture is simple MI. with shape - 256 + 16 - 8 + 1 and ReI.U activations followed tempered tanh output to bound tog-weights in -20, 20). Optimization follows the exact same procedure for both parametrizations. In particular, for the image classification tasks, we use Adam with learning rate 10 3 for all datasets, varying the number of steps from 1000 to 5000 steps depending on shift severity; see Section for exact details.
C.3 Baselines
C.3.1 "Oracle"
We use the term "oracle" to describe the marginal coverage and expected prediction set size achieved when both calibration and testing are performed samples from Q. This setup guarantees the desired coverage and, in our context where the test scores remain fixed, represents the best possible outcome. We only show these results as a reference for what would get if we knew the true #2Q, highlighting that the prediction set sizes are considerably larger only because the model is less accurate, as it trained on samples from P and not Q.
C.3.2 Likelihood Ratios
Tibshirani et al. 42) also proposed to reweight calibration points from P and apply split CP using a weighted distribution of calibration scores PT = E w,ds(ra..))- Since they only address covariate shifts, it is easy to show the optimal unnormalized weights are given by likelihood ratios of the form (Q(x))/a((xx). Unfortunately, learning accurate likelihood ratios is known to be challenging, especially when the two distributions are far apart. In our experiments, we applied the telescopic density ratio estimation approach of (34], which we found useful in the context of more severe shifts. In all cases, learning likelihood ratios directly on the input space X' proved challenging and we found more success when operating the space of scores, i.e., fitting the density ratio estimator to map vector of scores a (I;) to (approximate) ratios w; Ry dQ(x:)/a((..). The weights w; are then recovered by normalizing the likelihood ratios over the calibration set and the test point in question. That is, at test time, we must first evaluate the density ratio estimator to get Wn+1 &e dQ(s. ((((r))))/P(e))))) and then compute normalized weights as
W
WV
For the large datasets, ImageNet-C and iWildeam, our density ratio estimator was given by a neural network with two hidden layers and ten bridges. In this context, each bridge predicts the density
30

---

ratio between two intermediary distributions defined by mixture of samples from P and Q. In our experiments, we constructed the intermediary distributions via linear combinations as detailed in B4]. We train the density ratio estimator for ten epochs with a learning rate of 1e-3 and weight decay of 1e-3 to avoid overfitting. In the regression task, we also used an ML.P with two hidden layers and the same learning rate of le-3 but forewent the telescopic approach (no bridges) as it did not prove useful. Regarding the architectures, we used ReLU activations and kept the hidden size constant and equal to the input size, i.e., 1000 for ImageNet-C, 182 for iWildCam, and 4 for the regression task.
C.3.3 Entropy scaled Conformal Prediction
We also compare our methods to Entropy scaled Conformal Prediction (ECP) proposed by 21 which constructs prediction sets as
"D Qa (I((((
(Ix(),")0)) (pm) s Qa (8.)
CKasa (X1) = 1/ Ey:: 8 ((x..)) max
where f(X,) (f(X),))) 3 }) is the set of probabilities assigned to each class by the underlying predictor J. and -(f(())) - f(X,, (X, y)) is the entropy of this set of probabilities. Their method designed to work with test-time adaption methods [26 41] which adapt the model f in stream of test samples. However, it can also be applied to our setting where the model is kept fixed and set of test samples D(2) observed all at once, as formulated above.
C.3.4 Conformal Prediction With Conditional Guarantees
Gibbs al. [. proposed method that, under a prespecified function class of covariate shifts, guarantees conditional coverage, i.e., ensuring the prediction set contains the true label for every test point X₁
P(Y, E (())) 2 a
Their approach essentially changes the conformal threshold for each new test point by learning a function (x(x).)) as follows
n
gs arg min gET
Σ (x)) Si) n (x(9(X)),
n2 +
Corobo { e y: s(X,, S 9 (Xi)
(24)
where F is the function class of distribution shifts of interest, la is the pinball loss with target quantile level a, and per test point and providing conditional guarantees, their method is inherently more powerful than ours. However, this extra power comes with extra limitations:
refers to the unknown nonconformity score of X,. By computing a new threshold
Function class F is typically unknown. Conditional guarantees are impossible in the most general case of an arbitrary infinite dimensional class ourselves to a prespecified class of functions, which requires precise knowledge about the types of distribution shift we expect in practice. experiments with large datasets like ImageNet-C or iWildCam, it is not clear how to define F effectively.
44
Therefore, we must constrain
Computational cost at test time. Gibbs et al. [5] propose an efficient algorithm to optimize (24p that leverages the monotonicity of quantile regression to avoid evaluating each possible test score for X,- Yet, this procedure still significantly increases latency at test time, and in our hardware, it took 1.5 seconds per test point when using 300 calibration points, and 30 seconds when using 1000 calibration points. Due to this extra computational cost, we only used 300 calibration points when applying the method of [15)
Prediction set size. In practice, observed that prediction sets produced by the method of [15] to be significantly larger than optimal. This is in part due to the stronger conditional guarantee but might reduce the usefulness of the prediction sets in practice.
In our experiments, we used the official implementation available at atggthuh..om/jgheriaicoonniiiii conformal Similarly to the likelihood ratio baseline described above, applied their method
31

---

to the vector of scores instead of the input space. Since the function class corresponding to the type of distribution shifts observed ImageNet-C and iWildCam are hard define in practice, we applied the most general approach using radial basis function (RBF) kernels with hyperparameters y = 12.5 and 0.005 (see the official implementation for details) for ImageNet-C. and iWildCam experiments, since we found this to work best in preliminary experiments.
C.4 Datasets
C.4.1 Regression Synthetic Data
For the toy regression task we adopt a setting similar to the one proposed in [4)], where we have a regression problem with 4-dimensional input variable X ~ NN 14), and target variable given by Y = 210 + 27. 1 + 13.7X2 + 13.7X3 + 13.7X4 + e, with ~ ()) We will refer to this distribution on X' x 3 as the unshifted distribution P. We then induce a covariate shift to get new distribution Q via exponential tilting by resampling the data with weights (un(2)) exp(-1z1 + 0.5zz 0.25xz - -011z)). This automatically gives us ground-truth likelihood ratios, since Wan (I) = dQ())/ap(=) by design. Note that these tilting weights should still be normalized over the calibration set to define a proper empirical distribution we can apply conformal prediction over.
For the experiment depicted in Figure 3 we repeat 500 simulations, each time sampling new datasets Df". DP) D and D each with 1000 samples. We use the regression aegression-s-classiff cassssssifintno method of Guha al. [6]. splitting the output space into 50 equally spaced bins. For the predictor, train a multilayer perceptron (MLP) with a single hidden layer of 256 units and ReLU activations. For the density ratio estimator, we use an MLP with one hidden layer with 32 neurons, which
we train to distinguish samples from D(" and D by minimizing the logistic loss as common in density estimation tasks. For our methods, we only considered the free-form parametrization for this experiment. We repeat the optimization process in Algorithm for 10 steps, each time updating all the weights using Adam
22 with a learning rate of 0.1.
C.4.2 ImageNet-C
In all cases, the underlying classifier is the pretrained ResNet-50 from torchvision (27. To simulate label shift, as in previous work [2]. we do so by resampling data points (without replacement) according
new label marginal QYY Dir(c) where the concentration parameters e are given by с. = P(Y = k) * y. The parameter y controls the intensity of the label shift, with lower values of y producing more skewed label marginals. However, since we sample without replacement, low values of lead to small sample sizes (< 50) and, consequently, noisy results. For that reason, we set y = 10 which yields significant label shift while producing sample sizes of around 300 samples.
ImageNet-C [17 comprises 15 different types of corruption applied on top of the original validation dataset of ImageNet (36), which contains 50K samples. We repeat each experiment with 10 random seeds. As explained in Section 6.1 each time we randomly split the corrupted data Do into two: D
used to learn the weights or density ratio model, and Q for testing. Since we use a pretrained model as classifier, we do not need to reserve a subset of the clean data Dp (the original validation dataset) for training the model. However, one thing to note is that in ImageNet-C DQ is constructed using the same images in Dp. Thus, we have to ensure the calibration dataset, which we denote D/2) to be consistent with Section 6.1 does not contain any of the images in either DE or DD2)) 'This will affect the sizes of each of these sets, described in the following sections. In all ImageNet-C experiments, unless explicitly stated otherwise, we construct calibration and test sets with the following sizes:
calibration sets with |D) 300 and (D( 300, and test sets with [D{ 30000.
The underlying classifier was a pretrained ResNet-50 available in Torchvision package 27 which was kept fixed in all experiments. We only learn weighting scheme for the calibration data points, and the model as well as the nonconformity score function remain unchanged in all cases. In each optimization step and for both parametrizations, we backprop through all weights (no batching) using Adam with a learning rate of 1e-3 and 3 (0.9, 0.999). These hyperparameters were the same across all runs, with only the number of optimization steps varying: 1000 steps for distribution shifts of severity 1, 3000 steps for severity 3, and 5000 steps for severity 5. We observed our methods to be
32

---

fairly robust to these hyperparameters. One should only keep in mind that the more severe the shift, the longer the optimization or the larger the learning rate should be, as demonstrated in our approach.
In @ we present the empirical coverage obtained for each method and corruption in ImageNet-C, giving more complete picture of the ImageNet-C results reported in Table [
C.4.3 iWildCam
iWildCam involves images of animals from different camera traps that aim to monitor biodiversity loss. The distribution shift arises from the differences in the characteristies of the environment of each camera trap (e.g., changes in illumination, camera angle, background, etc.). We use different subsets of camera traps for training, validation and testing, which induces a distribution shift. For classifier, we train a ResNet-50 model from scratch the training set. As for ImageNet-C, we repeat each experiment with 10 random seeds.
We experiment with two different settings of distribution shift: the natural one (i.c., differences in camera- traps between validation and testing) that already exists in the data, and a combination of the natural shift with a label shift induced by changing the marginal over the labels via a Dirichlet distribution the same way as for the ImageNet-C dataset, also with y = 10. For this experiment, we also used Adam with learning rate of 1c-3 and 8 (0.9, 0.999), running optimization for 1000 steps. As for the ImageNet-C dataset, we use calibration sets with 2 = 300 and [D)]] = 300 for the experiments reported in the main paper, with the test set composed of 10000 samples, i.e.,
[ = 10000. However, we also use the iWildCam dataset to study the effect of variations in sample sizes in our methods, as explained in the next section.
C,5 Further Discussion
In this section, examine key design choices, including the impact of sample size and the perfor- mance differences arising from the selection of bound and auxiliary distributions. For clarity, the empirical results presented in this section focus exclusively the free-form parametrization, i.e., directly optimize the weights over the calibration scores.
C.5.1 Influence of the number of samples from calibration and test distributions
In Tables and we illustrate how the final total coverage gap AP,Q varies with |D)?)), the number of calibration samples from P. and ID{ the number of unlabeled samples from Q. As anticipated, the method's performance improves with an increase in the number of available samples. Interestingly, the number of calibration samples from P appears be more crucial for performance. This is encouraging, as it suggests that collecting or waiting for large number of unlabeled samples from the test distribution is unnecessary, with no significant gains observed beyond 1000 samples.
We observed a significant reduction in the total coverage gap in all cases where the number of calibration samples from P was 100 more. For smaller calibration samples, the observed change in coverage minimal even slightly detrimental, in the case of (s:Qmin, sy Qmax) with ID 30 and ID 100. This is likely because we do not have enough samples from P to represent s well enough via a weighted empirical distribution of the form Ph More broadly, this underscores one of the limitations of approach. The possibility of our method hurting coverage in some cases is not surprising, since we tackle the most general distribution shift case, with no prior information about the shift mechanics. In that setting, there is always risk that optimizing methods could negatively impact coverage. However, the results show a positive trend, indicating that these risks tend to diminish the number of available samples increases.
C.5.2 Choice of Bound
Before applying our methods, two key decisions must be made. The first is whether to use the weighted CDF formulation in 7 or the 1-Wasserstein distance formulation in (8. The second involves selecting the appropriate pair of auxiliary distributions. To guide these choices, we evaluate the total coverage gap achieved after optimization under each configuration. The results for the image classification datasets are summarized in Table 4
33

---

Table 2:
Total coverage gap on iWildCam with ResNet-50 for varying number of calibration samples from P (DF') and Q (D for our method with (syQuin syQuaa). We highlight in blue, the cases where total coverage improved by more than standard deviation. We report mean and standard deviation across 10 random seeds. Lower is better.
Number of unlabeled samples from Q
samples from P
Uncorrected
ID@]
30
[D0]
100
[
300
1000
[D| 2
3000
[D 30
0.11940.046
0.11720.048
0.12220.044
0.115 035
0. 0.118
0.119
[D] 100
0.002
0.107
0.10220.017
0.099
0.096+0.016
0.101=00011
[D)-) 300
0.1451
0.091 10.017
0.085
0.084
0.08310.010
0.085
[D] 2) = 1000
0.139
0.08510.015
0.078
0.07220.005
0.07210.004
0.07310.008
(D) 2 3000
00.09
0.08240.015
0.075=a.008
0.070=a.007
0.069
0.070=a.006
Table 3: Total coverage gap on WWilCCam with ResNet-50 for varying number of calibration samples
from P (1DP2) I> and Q ((D(") |> for our method with (s;Q², s.Q"). We report mean and standard
deviation across 10 random seeds. Lower is better.
Number of unlabeled samples from Q
samples from P
Uncorrected
[D
= 30
100
[D4
300
D 1000
|
3000
[D 30
0.119
0.112
0.117
0.109 20.033
0.112
0. 0.113 0.004
[D ?) 100
0.1 0.002
0.097
0.094g00018
0.090
0.08620.014
0.091
[D] ? = 300
0. 40.044
0.083
0.076g0.010
0.073
0.073+0.010
0.073ga.011
[D 1000
0.13910.0:0
0.07210.018
0.067 10.008
0.061 L0.006
1.059
0.060
[DD 3000
0.13910.005
0.072.0.017
0.064.0.000
0.058
0.057
0.058g0.005
Weighted CDF or 1-Wasserstein
It is clear from the theoretical results that the weighted CDF version of the bound is provably tighter than the I-Wasserstein distance. Therefore, one should expect (7) to produce better results, and this seems be the case for most image classification datasets, with the exception of ImageNet-C with severity level 1. In contrast, for regression tasks, we observed the opposíte trend: the W-Wasserttein distance outperformed the weighted CDF bound, As shown in Figure 4 the weighted CDF bound led to overcoverage when paired with (s:Q),, s;Q!)) and produced less consistent results when used with (s:Qmin Sy Qmxx). We conjecture that this discrepancy arises from the increased complexity of optimizing the weighted CDF bound, which may account for the divergent empirical outcomes. Indeed, the task of finding the density of scores needed for the weighted CDF distance is more intricate and precision-sensitic than simply identifying its maximum. As result, in certain cases, the weighted CDF bound may underperform relative to its 1 I-Wasserstein counterpart.
Choice of auxiliary distributions
The tightness and practical utility of our bounds are influenced by the choice of auxiliary distributions (s;Q+, S²Q+): the closer these are to the true distribution syQ, the tighter the resulting bounds. However, our bounds have proven effective for learning the weights of syP" even when using uninformed and widely applicable auxiliary pairs such as (s;Qmin, sy syQmax) and (s:QA, 2² which in general do not bound s tightly.
The performance of the two auxiliary distribution pairs was comparable in most cases, with (s,Q7, ") generally achieving better coverage, albeit with a tendency to overcover. As mentioned in the main paper, (syQf, s x²Q") is motivated by the observation that $yQU tends to produce noncon- formity scores higher than those from the true distribution s;Q-ir it corresponds an uninformative model in which the correct label is independent of the model output- while s;Q' tends to yield lower nonconformity scores, reflecting a perfect model where the true class is sampled according to the model-assigned probabilities.
Beyond this theoretical motivation, there is also a practical reason for the better performance of (s;Q², sqQU), which relates to the specific form of the nonconformity scores ased-namely, one
34

---

Table 4: Total coverage gap iWildcam and ImageNet-C with severity levels 1, 3 and 5 com- paring optimization via the weighted- CDF (7) and the 1- I-Wasserstein (8) bounds with free-form parametrization. The classifier is given by ResNet-50 and we consider both pairs (s:Qmin smax) and (s,Q², s,Q%). For ImageNet-C we report the average across all 15 corruptions. Lower is better.
iWildCam
ImageNet-C Sev.
ImageNet-C Sev.
ImageNet-C Sev.
Uncorrected
0.13220.016
0.141 20.048
0.267 20.081
0.388
weighted CDF
(min, max) (f,
0.084
0.098
0.171+0.060
0.281+0.076
0.073 1..00.0.00
0.059 10.023
0.102 10,036
0.173 10.071
I-Wasserstein
(min, max) (f.)
0.125
0.009
1.196620.022
0.337=+0.00
0.125g00005
0.044.00020
0..39
0.310 108
minus the model-assignen probability for each class. Under this scoring scheme, the main difference between the two pairs arises from the contrast between sy(2 and syQ"min. Since most classes tend to receive relatively high nonconformity scores, syQU and syQuuxx are typically quite similar. On the other hand, unless the model is highly confident, syQs and sy(Tiin can differ substantially. This explains why szQ* may be more effective in practice. In particular, if we expect the model have low accuracy under Q, s;Quin becomes overly conservative and diverges significantly from the true Therefore,
syQ, a pattern clearly illustrated in Figure 1 towards lower values, for instance, by sampling from the model, potentially with a high temperature.
improve performance by biasing syQ+
Computing the Bounds
We compute the 1 I-Wasserstein version of the bound by estimating maxs,eR Po. with Gaussian KDE and computing Wi (s; 8m)m) analytically. However, for the weighted CDF version of the bound we have couple of options. The first is to treat the bound as expectation under a which can be approximated via the n samples (X,, Yi) we have from P
Dr. $ parr(ss) F Peg (8a) - F. P. (8c) = Beewey [ (Bc) - F =F (0:))
(25)
a n (s(x,, F. (s(X,,
(s
This gives tight estimates and is computationally cheap but did not prove useful as optimization objective for learning a weighting scheme. Alternatively, we could compute the upper bound by numerical integration, which works well for unidimensional data. Since our nonconformity scores are bounded in [0, 1], we use a grid of equally spaced K points sk to get the following estimate
AP.Q S po.p((s)) (Fapps - f. (se)
K
(s.) K
Frpp. (SL) -0 F. (sa) (26)
In this case, we have to estimate the probability P(sk) for each of the points in the grid. We do that with Gaussian KDE, using reflection [0] to deal with the boundaries in [o, 1]. This proved a better optimization objective, facilitating the learning of the weighted distribution P Thus, when computing the weighted-CDF version of the bound we use the numerical integration method as in (26) for both training and evaluation; see Table for an analysis of the tightness of the bound (26) in ImageNet-C with severity 5. Note that in all cases, we can replace sy Pr with sy Ppr.
In terms of complexity, the bounds require computing either weighted CDF or 1 I-Wasserstein distances, which are tractable for unidimensional variables like nonconformity scores. In both cases, we need to compute the difference between the empirical CDFs, which has overall time complexity ((m + n) Iog(m= + n)). The complexity here is dominated by the sorting operation needed to compute the difference between the empirical CDFs, but fortunately this operation is applied only to the score values and not to the weights, and thus we need to compute only once during optimization. Finally, with the exception of the bound in (25 we also need to estimate the density PspP. We do so via a Gaussian KDE defined on the samples from syP. which has cost O(k n)), where h is the number of points the KDE evaluated on, e.g. the grid size (6).. We set the KDE bandwidth using Scott's 's rule (37] but scale it by a factor of 0.1 in classification tasks to improve resolution in the tails.
35

---

1-Wasserstein Distance
Weighted CDF
Uncomected
hood
ratics
... sagmt saggm
12
12
seg"
Density
Density
Target coverage
8
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
Coverage
Coverage
Figure 4: Distribution of coverage for the synthetic regression task across 500 simulations and target coverage rate of 90% (blue vertical line). Results with the W-Wasserstein distance formulation on the left and with the weighted CDF formulation on the right. The baselines remain the same in both plots. For ease visualization, we plot the density estimated with a KDE to the 500 observations.
C.5.3 Tightness of the Bounds
Our upper bounds to the total coverage gap include terms that depend only on the auxiliary distri- butions, such as JR Fe Qu (sc) - o,,0r (s in and E2,qr [S] Qu [S] in 8 Therefore, we cannot hope to have tight bounds, unless 1 and x are close to each other and sandwich 84Q, i.e. satisfy the stochastic dominance relation s;Qt > 84Q > stQ+. To illustrate this point, we evaluate our upper bounds on ImageNet-C with severity level in Table 5 where we can see the upper bounds constructed with the auxiliary distributions are relatively loose, as expected.
As discussed throughout the paper and demonstrated in the experiments, these bounds, although not tight, are still effective in mitigating the coverage gap by serving as a practical optimization objective for learning syP" Nevertheless, these bounds. We leave further improvements for future work, but one promising direction is to learn transformation of the scores under Q jointly with the weights of sy pw, Although this approach would still require auxiliary distributions to evaluate our bounds, it could yield tighter estimates, for instance, by reducing the gap between sy siin and sy Qmax
conjecture that there is still room improve the tightness of
Table Upper bounds to the total coverage gap for ImageNet-C with severity level For each pair of auxiliary distributions we consider, we have the total coverage gap A p Q after optimization, and the weighted-CDF upper bound computed with unlabeled samples and no DKW correction. We report mean and standard deviation across 10 random seeds. Lower is better.
Corruption
A pre Q
(s 94Qmin spQuaxx
Ap
(s:Q$,55''
Gauss
0.377 0220
0.445
0.26440.08 033
0.291
Shot
0.378
0.441
0.291
0.319
Impul
0.378
0.450=0.013
0.274440007
0.306
Defoc
0.258
0.328
0.09440.0r
0.113
Glass
0.316 030
0.389
0.167 032
0.208
Motion
0.291 120.28
0.354L0.011
0.168 0.00
0.20991..01
Zoom
0.252.1o. .0.027
0.306_0.002
0.153 10.027
0.190 00.00
Snow
0.289 0.0026
()333 10.027
0.201 0206
0.226 2.025
Frost
0.2544 026
0.298 20.025
0.162.10.02 0.323
0.189 0.001
Fog
0.246440.0 028
0. 20.00
0.166 029
0.202
Bright
0.095
0.098
0.05641.000
0.060=0.000
Contr
0.327 .3.034
0.413
0.1144n..24
0.134
Elastic
0.298 10.844..020 020
0.354=0.026
0.2322+0.00
0.275
Pixel
0.257 +0.000 027
0.314=0.022
0.147 00.01
0.184+0.00
Jpeg
0.196440.02
0.230=0.030
0.10640..03
0.119
36

---

Table 6: Coverage on ImageNet-C with ResNet-50 with and without label shift (see Section 6.2 Results for uncorrected distributions, calibrating and testing on samples from Q (Oracle), estimated hiiittediikeiihhho likelihood ratios (LR), the methods of Kasa et al. and (andaaannnaa Gibbs et al. and weights Iearned via our weighted CDF objective [ including (min, max) and (f, U) variants with free- fee-form (FF) and weight function (WF) parametizations. Target coverage of 90%. We report mean and standard deviation acToss 10 random sceds.
Avg. Size
2.7
10.7270
6.2as.
12
518.5
31.7.20
19.2a11.
277
15.0am
6.1ss
2.7
662.3..4.
14.32100
33 33.1
20 20.7:144
36.1
80.1
12.
110-9-004
035. 7.09
63,0
79.7
3.2.2a
88.
14.44188
344244
638.0.mo 0.702
638
02.4
00
00.4mm
78.
80.0amt.
3-3
338
27 T-5st
282. 20200.0011
754.4
128 12000200.
180
205,7
200.4
33
319.0.2a0
27.7
4.1
703.0
127
120 200.2.m.
200, 300.0.1003
201.3g
Avg. Cos.
78.2
80.8
81-1549
96 60s.1
88.9.2m
91.453.
91.62na
05 03.0
95. 05.7
20-2
00.3344
81.
70.2
88.0g34
91.
03. 73.3
015 23.5
96.1
80.9
71.3
90.7332
95.6
88.2.77
17.0
90-8250
90. 10.1
50.2 50.2.
90.2
72.0
00.7gm.
55.5
88.435.
S7.32103
M0-3258
90.4
29.8
80-7
47 47.4-20
80.
84.,36
71.3217
715
79.5a123
78.7
29.8 S-20
90.5
47.5.m.
21.2.10
81.855
12.0
70.4 70.4.163
79.8
70-2
70
58
71
83. 83.4
80.7217
86.6
07.0
89.9
98.0g2.
06.511
05.0e22
90.611.
83-349
87.4
83.355
50,9
91.829.8
96.
98.4224
96.4
35.3
89.9
82.9
96.5200
88.8
96.1
95.6119
76.5am
90-455
S6.1200
70.827
87,0
95-5426
95-611
05.6112
90.3115
68.5
95,2
85.4
86. 2000
85,0ems
88.2
87.7
48.1
91.0115
08.3.n.
40.1a9
85.0g42
86.755.
85.2
80.3
90.0g
Pixel
S1.7
80.0
55. 55-1as.
06.6.o.7
50.0
91.753
95-0a2
03.6220
96.0...
50.0
00.
84.675
80.
50.3
90.0a5.1
96.0z21
02.8
06.5
66.3 3..
80.7
78.2
94.511
55.0
91.2.3
829.
92.1611
02.3229
648-nA
90.734
77.3
56.0
90.1
42.4
92-4338
92.0
36.2444
80.911
55
802
85.5
76.859
76.85m
830,g0
80.7
05.6.11.1
02-1:am
47.4007
$4.241
174
84.3
S1
2
Digital
36
92.
Elastic
83.5 53.5=224
00.4
57-3
07:5-uu
01.3.
92.8
96.9-1
us 0.12
96.9.15
84
00 00.1555
84..00
80.2g04
94.5 04.0aaa
7:27
07.4
4-52
90.4
96.7.1
80 00.1-22
941.2n
04.2.2
04.0222
75. 75.4.m0
01.2500
77.2000
75.4 43.4
58 333
04.2004
94
05.621
01.7.33
10-3aa
90-4224
45.9 15.9-x.
78.3.36
75.1.a4
07-2294
07 Jens
08.507
09.5.75
29 0200
96.7
41.74100
17.0g88
6177111
63.0
75.4
73.0g1.0
06.
80.8
05.
20.
Contt
82,8
90.6115
86 8668
07. 47.4
80. 80.7
97.5222
06.8114
90.8113
82.0ano
05-22314
59-3
82.9
90.4gp
94.8293
90.2.2m.
95.1
96.3
60-3
80.8
28.3454
98.3211
80.3
92.9
84.6
94.1
96.1
65.4,104
97.0g11
81.2444
87,8
99.8
93-0464
98-8550
92.6177
80-0144
32 82:0
98.4
95.2
07.0
88.5
90.6
10-4em.
90.7
21.3.144
124464
93.849
08. 08.4.11d
90.3
91.6gs8
65.4
06.4
08.
Bright
88.5 S8..
59.0s222
07 07.6.a..
02. 92.4.21
90.9220
95- 16-1ss
06 G8..
07.5gaM
59.562.4
80
89.0
80.5
91.9g20
94.2333
06.3.31
80.4.m.
557
ST.4.3
07.4000
91.0
00.8
972
97/011
07.
88.6.12
888830
$8.755
N6.0242
91.
07.2
18
96.9
28.0232
80.711
82.944
07.0,0T
87.5224
96 96-0219
05 05.7.21
96.023
96.2
70-4
912:11
530,55
794434
99.363
87.
90..
06.3
90.
85
Fog
30.3
6024 1
86 2441
07. =0.7
02.5 02.8
88.5
04
96.0
78
87
85.8 85...1
7-
60.3-17
045.24
05.8.30
07
89.0
28.2.44
06-4.12
86.7
02.3:12
09.2.4
08-427
08 4844577
07-9-
88.053
78 58.
07.3-4
86.0.44
01.7.16
333344
93 030..44
40.5
30-3-44
775-..
58.2.2
79.3.24
79.
81.
811.a
42
68.0
58.-.a
48.2-76
91.2-44
81.0..
61.2 62.2
62.7
82.0
Weather
50.5
80
02
78
90.3
57
78
Frost
75,
0.
80.
22
96 0.0.
89
01.2209
96
48-4-27
08-
86.8.1.
70
202
80.0
-5
79 2.3
80.4 60.4-43
01. 31
02.
96.7
48
4-3
89.5
63.5 -4
222
83.0
88.
63.4.64
85.0-45
85.3-54
40
80.
80.0_a9
63.3.:34
50.0g:00
814
K2.0ga3
82-
824200
84.7 T:45
86
37.66 17.0
20.2.1.
513-97
86.5 86.5.22
811.1
70.2
76.
80-3:04
79.2.
79.2
37 97.9
89.3
89.3.47
55.0..15
28.3
82-0.41
70.0 70.4
76,
80.1 10.1219
80.3
Swowe
73 a3.2
20.2
79-8
06 333.6..
65. 48.4.30
88.9.34
93.7 93.7
06 003
01.2.21
12.0 72.5
72.
56.7
02
00.2.4
00.0
53
89.3
65.7
65.7
20.2
82 52.2.3
63.
544.50
860
$5.8
541
90.1
07
54.450
515
88.
S15527
38.3.41
56.9
20
80.311
47
1-303
626
78.6.21
10.
10
749:34
73.3
33
90.0
1T.3550
611-133
78.4
74.194
Zoom
71.8 77
214
313-43
95 03.0
87.0
80.5-40
93-0- 93-0-29
7
813 2:
72. 121
00.
00.4.33
82 21
72.1 121-74
85.7-12
87.8-8
020
01. 01.1.53
942
542-44
00.4.14
09.8-74
83.022
86.0
67-9-14
89-033
88
535
60.1
72.9
641
929.34
56.1
85.0.10
8600-.11
888
08.0445
N0.0-11
07
3733100
89.0
62.2.2
78-874
78 S8
818-57
62.9 3-
36 36.5.s
89.3-42
61.--a
38.0
91.0.0
78
1.00
61.4 61.4.10
81.
20.4.0
Motion
82.2 82.2.9.
86-0 65.
07 320.
92.0.29
06-8113
04.0224
96.7 11.
83. 83.8
08.8
88.0-63
K3..55
88.0g91
06.T 11.
04.4 A44:34
90.0g.
56 6-
71.5.84
04-411
853
80.5.43
85.
01-1283
01.2385
58..ma
80.0
70.20.
08
K8.0.9
02 1.
26.8 26.
904210
87.2.0
85.8
73.9
29.
79
26.0e74
91..34
20.2.157
28
85.
50.3165
8
90.8
90.7
86
48
73
72
Blur
Glass
23.2
20.8
81.2545
96 Aec.
N0.0240
91.5224
01.4+17
91.712
767450
00,5443
80.1M
77.0650
87.9
87-0
9L7435
22.9
96.4
303
89.523
48.2 48.2-mm3
87.633
83.5
73.5,00
74..05
N00
79.7
31.4.32
40.0-129
34.0270
62.0
74.9
74.0-11
77-8as1
81.100
184457
80.6225
101-
87.4,3
58.6
08 1215
69 2013
81.2
70.0
19.8
88.813
10 1-n
58.1434
71 7..
70. 125-121
77.2 20-
83-3-11
87.
40
Defor
85-2 250
07 -T
02.9 -2.9.00
96.322
04
1.4..11 1.
78--
78.7-11
KT
78.97a 7a
60.0
98.7.38
151-32
05.0
96.9 38
57
75.3
07-2-00
80.3-18
02
05.0_36
84.7221
57.0
01.830
78.0
07.0
89 2.
92.9-41
927-49
05-4-44
93.8..9
10.2
89.0-00
7-15
96.1.16
02.
84.3007
861sta
02.9-45
93.3 An
29-2-s
20
58.0.146
12.0.x4
91.9-18
86.3.a2
63.8.147
90.7
78.4
80.7
89.5
85
00.0
02.5.
02.7
92.7
57
02.0
92.9
Impol
68.2
20.7415
77-3
05.2111
86. 120
88.0g0
02.0334
88 08.
83.2.22 128
60-22x.
01.7
78.2
093.59
84.
35.7
1:4
80.0
08.5.a
500
68.7
02-0
83.
81.
N6.0
86.4
47.5.mm
02.0gn
64.62:14
80. 150
KR.5
86.2.07
87 T
87.8 87.
6.5-18
89-5226
20.0
75.0
86.3.1
48.24.811
183
05.8
65.1m
77-23
91.0.3
21.8.14
7.4-0
85.8
1800
51.5
08. 18
06.02
77-3
08.5
88
Noise
Slock
20.8
20.2:1
82.0g442
06. 36.l
87.8
N0.555
02.0an3
91.1430
95.1120
77-4663
87.
848
77,462
87.8 878815
30.0
988828
92.5
96.8
76.7
89.512
62.844
9166231
81.725
835
S3.
86.
86.
89.539
64.3-12
08-2-113
84.024
85.655
87.7
8,311
80.2211
23
231-m
71.161
80.420
4690-19
16
0-
61.7-112
57.
8
93.0128
9.0
838844
50 101
47.0 17.0-1
00.3
55-8-10.4
Causs
78.0 7
N0.7 217
2222-32
00:2 00:2.04
88.2
280
03.7 03.7.44
05 05:3-22 =26
95.3 22
79.8 79.8
50.0
85
78.8 :5.
=20
93.9 22
02.3
90.9
3n
80.5 80.5.11
64.2
01.
83.
85.1.64 287
85.7 66.7.ma .64
S7-9
S7.4
51.4 km
50.3-<0
08:2
11.
$2.7 $2.7-2M 2.
$5.0
84.8 $4.8.08
57-0-38
86. 18.
6.0
58.5.28
23 11.4
701.1.61 261
$6.9 22
10.8 80.5.114
06.2.108
06. 36.4,1m mm
5.0.2.
57.4.4m
18.1 -8.
0.2
S7.0
17.6 37.0
48.8 48.5
6155.66
02.1 2143
FF (mii,, mux))
WF (mll, max)
Fy (miin, mox)
WF (mii,, max)
FF (uii,, mux)
WT tuin, max)
FF (unin, max))
WF (min, max)
FF [miin, mMA)
WF (nat,, m8x)
FF (uii,, mIo))
WF (mit, (minc.mmc)) mLc))
Unnommettdd
K c
FF J.
Unnormented
Kasa et al
FF Ur 7.U%
WF (f (7)
Uncomeeted
Giies oF m.
FF L
WF (')
LR Uncomeeted
Ciie et mM
FF (1.0%
WF (1.0)
Lnncomected
WF (1.6)
Lncomretedd
Kam orall
FF FF.... 6.5
(7. ())
Onaile
Cibes
Oneice
Onacle
Kana
Oradle
Onaele
Kass
JR
WF
LR
L.R.
JR
FF
LR
Do lited ahttt
Shii
o mhae Loae ou
wii
37


Reviews:
[{"review_id": "u2UNsEN8bH", "reviewer": "Reviewer_TMey", "summary": "This paper introduces a new conformal prediction algorithm in settings with distribution shift. The authors leverage optimal transport theory to quantify and mitigate the coverage gap, by learning a distribution that minimizes a novel coverage gap upper bound. The method results in smaller coverage gaps and more efficient prediction sets compared to baselines.", "questions": "These are just nice-to-haves if the authors have time; since my score is already high. \n\n- Can you provide some qualitative examples of the UQ provided by your algorithm vs baselines? It will help us understand the experiment setting and your results better. As someone who is not in CV I do not know what ImageNet-C looks like. \n\n- I am curious about the computational costs of this method. The paper fits a Gaussian KDE to the weighted calibration scores ($\\mathcal{O}(n^2)$). How long does it take (and on what machine) on your datasets? Would increasing number of calibration samples beyond 300 point, for better calibration quality? would any approximation method for density estimation or computing the 1-Wasserstein distance work in place of full fitting?", "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": "Strengths \n- the paper's perspective and theoretical contributions are very novel, breathing new light into CP's applicability on distribution shifts.\n- the paper explicitly addresses the issue of unlabeled test data, a common scenario in real-world applications. The construction of auxiliary distributions from unlabeled data for bounding the coverage gap is a clever and practical solution.  \n- overall writing is very good. the math is well-explained and the proofs look correct to me. \n- discussion and comparison with existing work is thorough and done with care. I appreciate the details in experiment implementation in Appendix B.1.\n- empirical performance that corroborates the theory. It is cool to see although the upper bound using auxiliary distributions can be loose, the prediction intervals show large improvements in terms of calibration. The studies in appendix B.3 are also informative of the properties of the algorithm. \n\nWeaknesses\n- I think within the scopes of a conference paper this submission does not have significant weakness.", "was_revised": true, "final_justification": "The authors have answered my questions and I maintain my positive recommendation.", "rebuttal": "Thanks for your review and for the encouraging comments regarding the novelty of our approach and the thoroughness of our experiments. We address your questions below.\n\n> Can you provide some qualitative examples of the UQ provided by your algorithm vs baselines?\n\nWe agree that qualitative examples are helpful for understanding the behavior of uncertainty quantification methods, and we plan to include them in the final version of the paper. Since we cannot share images during the rebuttal phase, we refer to Angelopoulos et al. (2021), who also apply conformal prediction to ImageNet and provide relevant visual examples. \n\nTo help clarify our experimental setting for readers unfamiliar with ImageNet-C: it applies 15 corruption types (e.g., Gaussian noise, motion blur, frost, fog) at 5 severity levels to create realistic distribution shifts that models encounter in deployment. In our setting, we observe that prediction sets increase in size with the degree of distribution shift, as expected. For instance, sets are larger on ImageNet-C with severity five than with severity one, as shown in Table 1.\n\nRegarding other baselines, our primary focus is on improving conformal prediction under distribution shift, so comparisons to non-conformal baselines are not the central aim of this work. That said, we’d be happy to consider including such comparisons if they could help clarify or strengthen the paper. Are there particular baselines you think would be especially valuable to include, or aspects of the comparison that you feel would add meaningful insight?\n\n> How long does it take (and on what machine) on your datasets?\n\nTo be precise, the computational complexity of evaluating the KDE is given by $\\mathcal O(n \\cdot k)$, where $n$ is the number of datapoints where the KDE is defined ($n$ samples from $P$) and $k$ is the number of points where the KDE is evaluated. While $n$ is fixed for a given sample from $P$, the value of $k$ can be tuned according to the compute budget. It directly affects the accuracy of downstream computations: a higher $k$ improves the precision of the approximate integral in the case of the weighted-CDF bound, and enhances the estimation of $\\max s_\\sharp P$ in the context of the 1-Wasserstein bound.\n\nIn practice, fitting the weights is relatively fast. On a standard commercial GPU (RTX 2080 Ti), the process takes under a minute for 300 evaluation points and less than 10 minutes for 10,000 points. These runtimes were sufficient for our use case, but there is still room for optimization. Several techniques exist to accelerate KDE evaluation, including the fast Gauss transform and tree-based approximations, which could be incorporated to reduce computational overhead. See, for example, Yang, Duraiswami, and Gumerov (2003) and the references therein.\n\n> Would increasing number of calibration samples beyond 300 point, for better calibration quality?\n\nYes, we have observed that larger numbers of calibration samples are correlated with better coverage. See Tables 2 and 3 in Appendix B for an analysis of how the number of calibration samples from $P$ and *unlabeled* samples from $Q$ affects coverage. \n\nThis trend is expected. More calibration data typically improves the reliability of coverage estimates, and in our setting, also facilitates learning as it increases the number of points we can use to approximate $Q$ via the weighted empirical distribution over calibration scores. More unlabeled samples from $Q$ are also beneficial, since it increases the amount of information we have from the test distribution. However, we chose to focus our experiments on smaller calibration sets to demonstrate that our method remains effective even in more challenging and realistic scenarios where both labeled calibration data and *unlabeled* test samples from $Q$ are scarce.\n\n> Would any approximation method for density estimation or computing the 1-Wasserstein distance work in place of full fitting?\n\nYes, alternative methods are applicable, provided the resulting bound remains differentiable with respect to the learnable weights. For density estimation, other approaches can be used, including the efficient KDE variants mentioned above. Similarly, various methods exist for approximating the 1-Wasserstein distance. However, since the scores are typically one-dimensional, the 1-Wasserstein distance can be computed exactly in closed form, leaving little room for improvement through approximation.\n\n### References\nAngelopoulos et al. \"Uncertainty Sets for Image Classifiers using Conformal Prediction.\" ICLR, 2021.\n\nYang, Duraiswami, and Gumerov. \"Improved fast gauss transform and efficient kernel density estimation.\" ICCV, 2003."}, {"review_id": "51RnWLqmIS", "reviewer": "Reviewer_XezP", "summary": "The paper revisits the problem of non-exchangeability for conformal prediction, and proposes an optimal-transport-based conformal framework with rigorous guarantees that addresses the preservation of coverage even in the presence of distribution shifts via what they dub Total Coverage Gap: the gaps in coverage at all coverage levels. \n\nStarting off with a simple TV-distance bound on the TCG (which is hard to estimate), the paper then replaces this bound with two further upper bounds, which lead to estimable and/or learnable quantities that can serve as the optimization target for the algorithm. They provide such an algorithm (or rather meta-algorithm) that needs to be given a pair of \"sandwiching distribuitions\" such that, as long as the sandwiching is approximately satisfied, the method will exhibit robustness to distribution shift. \n\nThe paper then moves on to a suite of experiments designed to show that the proposed method is indeed less sensitive to shifts/perturbations in the tested settings (both regression and classification).", "questions": "Several questions, if addressed in the rebuttal productively, can help me increase my score. (Also, see the Weaknesses section above.)\n\n(1) A deeper discussion of the possible choices of sandwiching distributions. Both in theory as well as in empirics. (See also Weaknesses section above.)\n\n(2) Investigation (empirically) of the above proposal to restrict the total coverage gap to a \"natural\" range such as above 85% or 90%. Does it help control coverage better or worse than in the total case considered now? (Both could in principle occur for different reasons.)\n\n(3) Further investigation, and discussion in more detail, of the experiments from the perspective of: (i) How robust are the empirics to the degree of misspecification in the sandwiching distributions? (Can insert, and test for the consequences of, this misspecification in a controlled manner.) (ii) How come the looser 1-Wasserstein bounds overperformed the other upper bound in regression tasks? I'd like to see a deeper dive than in the paper. (iii) Learning weights via the proposed procedure --- is it possible to visualize by how much more efficient/robust/etc the weights learned via this procedure are vs. the Tibshirani et al brute-force density ratio proposal?\n\nTypo: remove \"takes\" in line 77.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Overall, the paper has several strengths which will make it interesting to the conformal community. First, its upper bound that lets one learn weights based on unlabeled data is quite relevant and may/can help the unlabeled data setting in the CP literature become more well-studied. \n\nThe fact that the optimal transport view of the problem results in the to-be-learned objects being sandwiching distributions is also quite simple/memorable, and may lead to some productive investigations around how to choose such a pair of distributions depending on any available prior (but see more on this below).\n\nAdditionally, while one might say that the paper's theory is not very challenging to derive, but I believe the value is contained in the formulation of the bounds themselves, which are shown to be good surrogate optimization objectives in the presence of data shift (with its own set of empirical tradeoffs compared to prior work).\n\nAs for the weaknesses of the paper, one reasonably immediate question that was left empirically unaddressed is: Suppose I only care about certain coverage levels; say I know I will be enforcing coverage over 90%, but am unsure which \\alpha \\geq 0.9 I will pick; then what can I guarantee about total coverage gap just at those levels? In other words, this considers the more general (and arguably more natural in applications) setting where we have a weighting function over the coverage levels that determines which ones are relevant. This setting would also help with the positioning of the paper.\n\nAnother question that skews in a more modeling/theory direction is --- how does one choose the sandwiching distributions? This question has many facets, some best left for future work, but in the context of this paper I would have liked to see a discussion of \n\n--- (possibly stylized) conditions under which the uninformative-informative proposal would be provably stochastically dominating;\n\n--- which stochastically dominating pairs of distributions could one provably choose, given varying amounts of prior knowledge on the sandwiched distribution? (e.g. when nothing is known, we have the proposed min and max pair);\n\n--- what happens empirically when we intentionally misspecify the pair of distributions and it doesn't really sandwich the true distribution.\n\nThese are all relatively straightforward but very informative questions that would strengthen the paper's message as well.", "was_revised": true, "final_justification": "I remain positive about this paper after discussion with the authors and after reading the discussion the authors had with the other reviewers. I believe the method is both practical, and also opens up a number of empirical and theoretical challenges for the future (such as sandwiching bounds; range-of-alpha coverage and other topics; see the review points above). This is a good sign, and thus I believe the paper is a worthy contribution in its current form, even without engaging with all these gaps yet. While there is a concern from some reviewers about the coverage guarantees, in a sense the distribution shift setting justifies a corresponding shift in the coverage amount, and I currently believe it's also fair to relegate bounding that amount in theory and practice to future work.", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback. We address each of the main concerns below.\n\n## Coverage Level Weighting and Restricted Total Coverage Gap\n\nThat is a very interesting point. Thanks for bringing that up.\n\nOne could extend the definition to accept a range $\\alpha^{-}$ and $\\alpha^{+}$ such that \n$ \\Delta_{P,Q}(\\alpha^{-}, \\alpha^{+}) := \\int_{\\alpha^{-}}^{\\alpha^{+}} \\frac{\\Delta_{P,Q}(\\alpha)}{\\alpha^{+} - \\alpha^{-}} d\\alpha$.\n\nThe proof of Theorem 3.2 in appendix A.1 would follow in a similar fashion, except now we only consider score values in a restricted range. We would lose the connection to the 1-Wassertein distance, but for the weighted-CDF version of the bound we would get\n\n$\n\\Delta_{P,Q}(\\alpha^{-}, \\alpha^{+}) \\leq \\frac{1}{\\alpha^{+} - \\alpha^{-}} \\int_\\mathbb{R} s\\sharp P(s_c) | F_{s\\sharp P}(s_c) - F_{s\\sharp Q}(s_c) | \\mathbf{1} (s_c \\in [F_{s\\sharp P}^{-1}(\\alpha^{-}), F_{s\\sharp P}^{-1}(\\alpha^{+})]) ds_c,\n$\nwhere $\\mathbf{1}$ is a indicator function.\n\nWe tried to optimize this weighted-CDF bound during the rebuttal phase, but it underperformed the total coverage gap version of the bound. In the table below, we see the improvement over the unweighted version is small when optimizing $\\Delta_{P,Q}(0.0, 0.15)$. We see two possible reasons for this. First, optimizing the bound for a specific coverage gap range may be inherently more difficult; for example, the upper bound for a fixed $\\alpha$ derived in Appendix A.3 also failed to yield better empirical performance. Second, the total coverage gap may already serve as a strong objective, leaving limited room for improvement through alternative formulations. Yet, these more targeted objectives are a very promising avenue for future work, and we will include this discussion in the paper.\n\n**Empirical Comparison: Total Coverage Gap vs. High Coverage Gap ($\\alpha \\leq 0.15$)**\n\n| Method | Coverage at 90% | Coverage at 95% | Coverage at 99% |\n|--------|-----------------|-----------------|-----------------|\n| **iWildCam** | | | |\n| Uncorrected | 79.6 ± 3.1 | 88.5 ± 2.8 | 98.5 ± 0.6 |\n| (min,max) Total | 85.2 ± 4.1 | 94.3 ± 3.2 | 99.1 ± 0.5 |\n| (min,max) $\\alpha \\leq 0.15$ | 78.5 ± 3.1 | 89.0 ± 2.8 | 98.6 ± 0.5 |\n| (f,U) Total | 88.2 ± 3.4 | 94.9 ± 2.3 | 99.1 ± 0.5 |\n| (f,U) $\\alpha \\leq 0.15$ | 78.6 ± 3.0 | 89.1 ± 2.9 | 98.6 ± 0.5 |\n\n## Empirical Robustness to Sandwiching Distribution Misspecification\n\nThat is an interesting point. As mentioned in the paper, $(s_{\\sharp}\\hat{Q}_f, s_{\\sharp}\\hat{Q}_U)$ might already not safisfy the stochastic dominance relationship in practice. However, our experiments show that coverage often improves even in such cases. This suggests that the sandwiching approach can still yield meaningful bounds, even when the sandwiching distributions are somewhat misspecified. More generally, one can expect improved coverage whenever these distributions better approximate the true test score distribution than the calibration scores do.\n\n## Performance Analysis of 1-Wasserstein vs. Weighted CDF Bounds\n\nOne might expect the weighted-CDF bound to outperform the 1-Wasserstein bound, given that it is provably tighter. However, in some experiments, particularly the regression task, the 1-Wasserstein bound performed better. As discussed in Section~B.3.2, we hypothesize that this is because the 1-Wasserstein bound is easier to optimize. It only requires identifying the maximum value of the score density, while the weighted-CDF bound depends on accurately estimating the entire density. It is not entirely clear why regression tasks are more sensitive to this difference. One possibility is that, in conformal regression-as-classification, the output space must be discretized into bins somewhat arbitrarily. This binning may introduce additional noise into the score function, especially under distribution shift, making density estimation more challenging.\n\n## Comparison with Likelihood Ratio Methods\n\n> Learning weights via the proposed procedure --- is it possible to visualize by how much more efficient/robust/etc the weights learned via this procedure are vs. the Tibshirani et al brute-force density ratio proposal?\n\nCould you clarify what you mean by robustness in this context and what sort of visualization you have in mind? In our experiments, we found that our method consistently outperforms the likelihood ratio approach proposed by Tibshirani et al. across a variety of settings. We believe this is largely because learning accurate likelihood ratios is inherently difficult, especially in high-dimensional spaces. In contrast, our method focuses on unidimensional scores, which are much easier to estimate and optimize.\n\nAdditionally, our approach is not limited to covariate shift scenarios, which makes it more broadly applicable and potentially more robust in diverse real-world conditions.\n\n---\n\nWe thank the reviewer again for the thoughtful and constructive feedback. These questions helped us clarify both theoretical and practical aspects of our method. We hope our responses address the main concerns, but we are happy to discuss further if anything remains unclear."}, {"review_id": "ccURI2P0mt", "reviewer": "Reviewer_zmnD", "summary": "The authors study non-exchangeable conformal prediction via a new perspective, through the lens of optimal transport, and show that it is possible to estimate the loss in coverage and mitigate it in case of distribution shift.", "questions": "See Limitations.", "limitations": "The only two very minor comments are the following. First, CP is not strictly speaking an uncertainty *quantification* technique, but rather an uncertainty *representation* one. This is because it does not attach a number to (different types of) uncertainties faced by the user, but rather it represents them through the prediction set: Larger sets *represent* higher (total) uncertainty. It would be nice to have a footnote about this.\n\nSecond, do the author think that their OT method can generalize to the ambiguous ground truth case of https://openreview.net/forum?id=L7sQ8CW2FY? It would be nice to see a small comment on this in the future research section.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper is of very high quality: It is very well-written, it tackles a very interesting problem, and it does so in an innovative manner. No real weaknesses to signal.", "was_revised": true, "final_justification": "This is a good paper that clears NeurIPS's publishing threshold. I also appreciated the interaction with the authors.", "rebuttal": "Thank you for taking the time to review our work. We sincerely appreciate the encouraging feedback and the thoughtful comments, which we address in detail below.\n\n### Uncertainty representation vs quantification\nThat is a good point. We agree that conformal prediction is more accurately described as an uncertainty representation technique, as it conveys uncertainty through the size of the prediction set rather than assigning a numerical value. We will add a brief footnote to clarify this distinction in the revised version.\n\n### Ambiguous ground-truth\nThanks for highlighting another interesting scenario, where our methods are applicable. We will also include a discussion on ambiguous ground-truth in the paper. \n\nOur approach is designed to operate directly on (non)conformity scores. This is convenient because these scores are typically unidimensional, which greatly facilitates computation. More importantly, it allows us to handle arbitrary distribution shifts. This advantage also extends to cases with ambiguous ground truth. For instance, we can directly apply our method to the unidimensional score proposed by Stutz et al., which is computed by averaging the conformity scores of each class, weighted by their plausibilities. \n\nFormally, assuming $K$ possible classes and plausibilities $\\lambda$ in the simplex $\\Delta^{K-1}$, our method also applies to the score function of the form $s'(x, \\lambda) := \\sum_{K} \\lambda_k s(x, y_k)$. This enables us to fit a new set of weights over the calibration data to obtain a threshold that adapts under distribution shift. Once this threshold is established, one can proceed with the construction of predictive sets as in (Stutz et al. 2023), or following the approach of Caprio et al., as you referenced.\n\nThe main challenge in applying our methods to ambiguous ground truth lies not in the theoretical construction, but in the design of the auxiliary distributions. This is because, rather than working with a discrete set of $K$ classes, we must consider the full simplex $\\Delta^{K-1}$. Although the min-max construction remains straightforward to derive, it may be suboptimal, as the resulting auxiliary distributions can be \"too far apart\" to be effective. Identifying more effective strategies for constructing auxiliary distributions in this setting is a promising direction for future work. We thank the reviewer again for pointing us in this direction.\n\n### References\nStutz et al. \"Conformal prediction under ambiguous ground truth\". TMLR, 2023\n\nCaprio et al. \"Conformalized Credal Regions for Classification with Ambiguous Ground Truth.\" TMLR, 2024."}, {"review_id": "haYe9lwHJx", "reviewer": "Reviewer_RmHi", "summary": "This paper studies conformal prediction when the examples in the calibration set and the test set are no longer exchangeable. Firstly, the paper upper bounds the total coverage gap between the calibration distribution $s_ \\\\# P$ and the test distribution $s _ \\\\# Q$ through the maximal density value of $s_ \\\\# P$ and the $W_ 1$ distance between $s_ \\\\# P$ and $s_ \\\\# Q$. Then, the paper utilizes two auxiliary distributions to further upper bound the above upper bound, which allows us to upper bound the total coverage gap using only unlabeled data from the test distribution. Then, the paper proposes to learning the weights in weighted conformal prediction by minimizing the obtained upper bound and then use the learned weights to run the weighted conformal prediction algorithm. Experiments show that the proposed method achieves promising performance.", "questions": "Please refer to the weaknesses.", "limitations": "The proposed method can not be used in the case with sequential test examples, which is common in our daily life.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 3, "strengths_and_weaknesses": "###  Strengths\n\n- As shown in the experiments, the proposed method seems to work well in the non-exchangeable case.\n\n\n### Weaknesses\n\n- **The total coverage gap is not well motivated**. It seems that we usually care about the performance when $\\alpha$ is small and close to $0$, for example, in traditional statistics, we usually use $\\alpha= 0.05, 0.1$, while $\\alpha = 0.9$ is not used. So, it seems using the total coverage gap as a measure is not appropriate.\n- **There is no theoretical guarantee of the coverage [main issue]**. As a statistical framework, the goal of conformal prediction is to minimize the prediction set size under the constraint that the coverage is above a level of $1-\\alpha$. Although the upper bound of the total coverage gap can somehow control the coverage, there is no explicit result showing how we can control the coverage over a predefined level.\n- **A mismatch between the theory and the algorithm [main issue]**. The upper bounds in this paper are for the total coverage gap of the **conformal prediction algorithm**. However, equation (8) is minimized to learn weights for the **weighted conformal prediction algorithm**. Furthermore, a similar upper bound for weighted conformal prediction algorithms is not trivial, because now the weighted empirical distribution function is not an unbiased estimation of the weighted distribution function due to the dependence between the learned weights $w_ i$ and calibration scores $s(x_ i, y_ i)$.\n- **A mismatch between the theory and experiments.** The theory considers the total coverage gap, while the experiments only consider a specified coverage level.\n- The proposed method needs to use all test examples simultaneously, which means that the proposed method can not be used in the common situations where the test examples come sequentially and we can not see $x_ {n+k}$ until $\\mathcal{C}(x_ {n+k-1})$ is predicted. This issue also implies that **the comparison in the experiments may not be fair** if the baselines only use the information of $x_ i$ while the proposed method uses the information of $x_ 1, \\dots, x_ m$ in the test set.\n\n- Writing issues. The mathematical formulations are not rigorous enough.\n  - In the equation on line 103, $\\mathcal{S}_ c$ should be used instead of $S_ c$. Moreover, it should be $\\mathcal{S}_ c \\sim s_ \\\\# P^n$ but not $S_ c \\sim s_ \\\\# P$.\n  - In equation (16) in Appendix A.1, $s_ \\\\#P(s_ c)$ is used. However, as defined in line 92, $s_ \\\\#P$ is a pushforward measure. As a measure, the input of $s_ \\\\#P$ should be a measurable set, but not a value $s_ c$. So here you should use the density function of $s_ \\\\#P$ with respect to the Lebesgue measure.\n  - In line 63, the separable metric space is defined on $\\mathcal{X}$. However, the $\\mathcal{X}$ notation here is the same as the input space, which may cause a misunderstanding.", "was_revised": true, "final_justification": "After the discussion, the authors solved some issues I proposed. However, one of these issues can not be resolved since the paper focuses on the practical performance of conformal prediction without a theoretical guarantee, which is not acceptable to the conformal prediction field, in my opinion. So I increased my score, but I still lean towards rejection.", "rebuttal": "We thank the reviewer for their detailed feedback and constructive criticism. We address each concern systematically below.\n\n## 1. Motivation for Total Coverage Gap\n\nThe total coverage gap serves two key purposes:\n\n1. **General Optimization Objective**: The total coverage gap captures the overall effect of distribution shift, being zero when the distributions are identical. Similarly, the likelihood ratios of Tibshirani et al. (2019) do not target a specific $\\alpha$, yet learning them remains both reasonable and effective for mitigating covariate shift effects. Both methods aim to learn a set of of weights only once using some unlabeled test data, such that applying standard split CP (with any $\\alpha$) to the weighted calibration data, approximates calibration on the test distribution.\n\n2. **Theoretical Insight**: The total coverage gap also establishes a novel connection between conformal prediction and optimal transport, specifically through the 1-Wasserstein distance. This provides a broader theoretical perspective, even though it is not directly tied to a particular $\\alpha$\n\nThat said, we agree that some values of $\\alpha$ are more relevant in practice. For this reason, we derive a bound for specific $\\alpha$ values (Theorem A.6 in the appendix) and consider the coverage gap over a given range of $\\alpha$ values (see discussion with reviewer XezP). However, in our experiments, these more targeted objectives have so far been less effective for optimization. We believe improving them is a promising direction for future work.\n\n## 2. Lack of Theoretical Coverage Guarantees\n\nWe agree that statistical guarantees are central to conformal prediction. However, our work specifically addresses the setting of arbitrary distribution shifts, where standard conformal guarantees no longer hold. That is, our method does not invalidate any existing guarantees but rather operates in a regime where those guarantees are already compromised.\n\nMoreover, unlike prior approaches, we make no assumptions about the nature of the distribution shift. For example, Tibshirani et al. (2019) rely on specific shift types, and Barber et al. (2023) require prior knowledge of the shift mechanism. In the general setting we consider, deriving formal coverage guarantees is extremely challenging. Nevertheless, we show that it is still possible to bound the coverage gap. Our key contribution is to use these bounds, even if they are not always tight, as a principled and effective objective for optimization. This allows us to approach the desired coverage level using only *unlabeled* samples from $Q$.\n\n## 3. A Mismatch Between the Theory and the Algorithm\n\nWe thank the reviewer for highlighting this important point and will clarify it in the paper. By optimizing the calibration weights, we are directly minimizing the total coverage gap, but indeed this introduces dependence between the weights and the calibration scores. However, this can be easily addressed by fitting a weight function $w: s(x, y) \\rightarrow \\mathbb{R}$ on a separate set of calibration samples from $P$, thereby restoring independence. This is similar to the setup in Tibshirani et al. (2019), where weights are functions of covariates only, i.e., $w: x \\rightarrow \\mathbb{R}$.\n\nTo address this concern, we conducted additional experiments comparing our original method with the weight function approach trained on held-out data. The optimization remains essentially same: we use a set of labeled samples from $P$ and a set of unlabeled samples from $Q$ to learn the weight function $w: s(x, y) \\rightarrow \\mathbb{R}$ via our objectives. Once this function is learned, we apply it to another set of samples from $P$, the calibration set proper, before applying weighted split CP.\n\nThe results for iWildCam and ImageNet-C with severity 3 are shown in Table 1 below. We observe almost no difference in performance between the two approaches. The only downside of learning the weight function is that one needs another set of samples from $P$ (we use 300 samples for calibration in both cases, and another 300 to learn the weight function). However, once more, this is the same scenario considered in Tibshirani et al. (2019).\n\n**Table 1: Comparison of Original Method vs. Weight Function Approach**\n\n| Dataset | Method | Coverage at 90% | Coverage at 95% | Coverage at 99% |\n|---------|--------|-----------------|-----------------|-----------------|\n| **ImageNet-C 3** | Original (min,max) | 89.4 ± 6.9 | 93.8 ± 4.8 | 97.9 ± 4.2 |\n| | Weight Function (min,max) | 89.1 ± 11.3 | 94.4 ± 9.1 | 98.7 ± 8.1 |\n| | | | | |\n| | Original (f,U) | 93.5 ± 4.4 | 95.0 ± 3.9 | 99.5 ± 0.9 |\n| | Weight Function (f,U) | 90.0 ± 6.8 | 95.0 ± 4.2 | 99.3 ± 1.1 |\n| | | | | |\n| **iWildCam** | Original (min,max) | 85.2 ± 4.1 | 94.3 ± 3.2 | 99.1 ± 0.5 |\n| | Weight Function (min,max) | 87.7 ± 1.1 | 95.0 ± 1.8 | 99.2 ± 0.7 |\n| | | | | |\n| | Original (f,U) | 88.2 ± 3.4 | 94.9 ± 2.3 | 99.1 ± 0.5 |\n| | Weight Function (f,U) | 88.1 ± 1.7 | 95.0 ± 1.9 | 99.3 ± 0.6 |\n\n## 4. Mismatch Between Theory and Experiments\n\nThis apparent mismatch is by design and reflects practical considerations. We optimize the total coverage gap (which does require specifying $\\alpha$) but evaluate at specific coverage levels (90%) because that aligns with how conformal prediction is typically used in practice, as you rightly pointed out. \n\nTo provide a more complete picture, we also report the total coverage gap itself in Tables 2, 3, and 4 in the appendix. We are also happy to include coverage results for additional $\\alpha$ values if that would help strengthen the paper.\n\n## 5. Using All Examples Simultaneously\n\nThere seems to be a misunderstanding regarding this point. Similarly to Tibshirani et al. (2019), we assume access to a small unlabeled dataset from the test distribution $Q$, denoted $\\mathcal{D}_Q^{(1)}$, which we use to learn the weights (or weight function). Once the weights are learned, we have standard split conformal prediction but with a weighted calibration set, and it does not depend on how the test samples $\\mathcal{D}_Q^{(2)}$ are observed. Our methods are applicable to sequential test examples to the same extent that standard split CP is and *does not use all examples simultaneously*. Note that we use disjoint subsets of $Q$ for weight learning ($\\mathcal{D}_Q^{(1)}$) and evaluation ($\\mathcal{D}_Q^{(2)}$).\n\nIn the case test samples come sequentially, we can always wait until we have enough samples before learning the weights. As shown, in Appendix B.3.1, we do not need many unlabeled test samples to learn the weights effectively. That means we use standard split CP for first $m$ samples, learn the weights, and then use these weights when applying split CP on the following samples. It should also be possible to refine the weights on the fly as new test samples arrive using the same objectives, but we leave that for future work.\n\n## 6. On the Fairness of the Comparison with Other Baselines\n\n1. **Tibshirani et al. (2019)**: As mentioned previously, our method is directly comparable to the density ratio approach proposed by Tibshirani et al. (2019), and we follow a similar setup for a fair comparison.\n\n2. **Kasa et al. (2024)**: The method of Kasa et al. (2024) is designed for sequential test samples and does not use the unlabeled test samples in $\\mathcal{D}_Q^{(1)}$. However, we adapted their method to the split CP setting as described in Appendix B.1.3 such that the comparison remains informative. In our experiments, we estimate the entropy required by their method using all test samples in $\\mathcal{D}_Q^{(2)}$, which means, in our experiments, their method effectively uses the entire test set simultaneously, unlike ours.\n\n3. **Gibbs et al. (2023)**: The method of Gibbs et al. (2023) targets conditional coverage and also does not use the unlabeled test samples in $\\mathcal{D}_Q^{(1)}$. As discussed in Appendix B.1.4, it offers stronger guarantees, their method comes with significant computational cost and relies on stronger assumptions. Still, we believe the comparison is informative, especially in highlighting the difficulty of prespecifying the class of distribution shifts, as required by their method, in large-scale classification tasks like those we consider.\n\n## 6. Mathematical Formulation Issues\n\nThanks for pointing this out. We will improve the notation accordingly. Specifically, in *Equation (16)**, we will use the density function notation $p_{s \\sharp P}(s_c)$ instead of the measure notation $s \\sharp P(s_c)$, since $s\\sharp P$ is a pushforward measure and should take measurable sets as input, not point values.\n\n## 7. Overall Assessment and Significance\n\nWe believe our work merits higher scores based on several key contributions:\n\n**Novel Theoretical Framework**: We derive new bounds to the coverage via a new connection between conformal prediction and optimal transport theory, establishing new theoretical insights through the 1-Wasserstein distance. This represents a significant theoretical advance in understanding distribution shifts in conformal prediction.\n\n**Practical Algorithm**: Our method handles arbitrary distribution shifts using only unlabeled test data, without requiring prior knowledge of the shift type or mechanism. Strong empirical results across diverse datasets (ImageNet-C, iWildCam, synthetic regression) and shift types demonstrate its practical relevance.\n\n**Methodological Innovation**: The use of auxiliary distributions to derive bounds without labeled test data is a novel and flexible approach that could inspire future work in non-exchangeable conformal prediction.\n\n**Broad Impact**: Our framework applies to both classification and regression tasks and offers a principled solution to a fundamental challenge in deploying conformal prediction under real-world conditions."}]

Author rebuttal:

Meta-review: This paper proposes a weighted conformal prediction algorithm for non-exchangeable data, leveraging optimal transport theory to quantify and mitigate the coverage gap. The method results in smaller coverage gaps and more efficient prediction sets compared to baselines. Most reviewers liked this paper, praising the clarity, novelty, and the possibility of leveraging  unlabeled data for bounding the coverage gap. The main weakness is the lack of statistical coverage guarantees (which are central in conformal prediction methods), however this is a price which has to be paid for extending the theory for arbitrary distribution shifts (non-exchangeable data), where standard conformal guarantees no longer hold, and it is my opinion that the results of this paper are interesting to the community.
Decision: Accept (poster)