Optimal transport-based conformal prediction
Authors: Gauthier Thurin
Kimia Nadjahi
Claire Boyer
Venue: ICML 2025 poster (2025)
Keywords: conformal prediction
optimal transport
generalized quantiles
uncertainty quantification
Primary area: general_machine_learning

Abstract: Conformal Prediction (CP) is a principled framework for quantifying uncertainty in black-box learning models, by constructing prediction sets with finite-sample coverage guarantees. Traditional approaches rely on scalar nonconformity scores, which fail to fully exploit the geometric structure of multivariate outputs, such as in multi-output regression or multiclass classification. Recent methods addressing this limitation impose predefined convex shapes for the prediction sets, potentially misaligning with the intrinsic data geometry. We introduce a novel CP procedure handling multivariate score functions through the lens of optimal transport. Specifically, we leverage Monge-Kantorovich vector ranks and quantiles to construct prediction region with flexible, potentially non-convex shapes, better suited to the complex uncertainty patterns encountered in multivariate learning tasks. We prove that our approach ensures finite-sample, distribution-free coverage properties, similar to typical CP methods. We then adapt our method for multi-output regression and multiclass classification, and also propose simple adjustments to generate adaptive prediction regions with asymptotic conditional coverage guarantees. Finally, we evaluate our method on practical regression and classification problems, illustrating its advantages in terms of (conditional) coverage and efficiency.

Optimal Transport-based Conformal Prediction
Gauthier Thurin'
Kimia Nadjahi Claire Boyer? 2
Abstract
ical priority. Conformal Prediction (CP, Vovk al., 2005) has emerged compelling framework to address this need, by generating prediction sets with coverage guaran- tees (ensuring they contain the true outcome with a specified confidence level) regardless of the model or data distribution. Most CP methods are thus model-agnostic and distribution- free while being easy to implement, which explains their growing popularity in recent years.
Conformal Prediction (CP) a principled frame- work for quantifying uncertainty in black-box learning models, by constructing prediction sets with finite-sample coverage guarantees. Tradi- tional approaches rely on scalar nonconformity scores, which fail to fully exploit the geometric structure of multivariate outputs, such as multi- output regression or multiclass classification, Re- cent methods addressing this limitation impose predefined convex shapes for the prediction sets, potentially misaligning with the intrinsic data ge- ometry. We introduce a novel CP procedure hand- ling multivariate score functions through the lens of optimal transport. Specifically, we leverage Monge-Kantorovin vector ranks and quantiles to construct prediction region with flexible, poten- tially non-convex shapes, better suited to the com- plex uncertainty patterns encountered in multivari- ate learning tasks. We prove that our approach ensures finite-sample, distribution-fret coverage properties, similar to typical CP methods. We then adapt our method for multi-output regression and multiclass classification, and also propose simple adjustments generate adaptive predic- tion regions with asymptotic conditional coverage guarantees. Finally, we evaluate our method on practical regression and classification problems. illustrating its advantages in terms of (conditional) coverage and efficiency.
The main idea of CP is to convert set of non-conformity scores into reliable uncertainty sets using quantiles. Non- conformity scores are empirical measurements of how un- usual a prediction is. For example, in regression, the score can be defined as |0 - y/, where ÿ E IR is the model's pre- diction and y E RR the true response (Lei al., 2018). These scores are central to the CP framework as they encapsulate the uncertainty stemming from both the model and the data, directly influencing the size and shape of the resulting pre- diction sets. Therefore, the quality of the prediction sets hinges on the relevance of the chosen non- non-conformity score: while a poorly designed score may still achieve the required coverage guarantee, it often leads to overly conservative or inefficient prediction sets, failing to capture the complex patterns of the underlying data distribution (Angelopoulos & Bates, 2023).
Most CP approaches rely on scalar non-conformity scores (e.g., Angelopoulos & Bates, 2023; Romano et al., 2020b; Cauchois et al., 2021; Sesia & Romano, 2021; Lei et al., 2018). Although conceptually simple, such one- dimensional representations can be too restrictive or poorly suited in applications that require multivariate prediction sets. To circumvent this, recently-propose CP methods seek to incorporate correlations despite the use of scalar scores, by leveraging techniques such as copulas (Messoudi et al., 2021) or ellipsoids (Johnstone & Cox, 2021; Mes- soudi et al., 2022: Henderson et al., 2024). Nevertheless, these approaches either lack finite-sample coverage guar- antees or impose restrictive modeling assumptions that pre- scribe the shape of the prediction region. Feldman al. (2023) recently proposed a CP method able to construct more adaptive prediction regions with non-convex shapes, establishing a connection with multivariate quantiles. How- ever, their method (as conformalized quantile regression, Romano et al., 2019) requires intervening in the way the predictor is trained and, therefore, cannot be directly applied
1. Introduction
In various domains, including high-stakes applications, state-of-the-art performances are often achieved by black- box machine learning models. As a result, accurately quan- tifying the uncertainty of their predictions has become a crit-
'CNRS, Ecole Normale Supérieure, Paris, France 'Laboratoire de Mathématiques d'Orsay (LMO), Université Paris Saclay, France, and Institut universitaire de France. Correspondence to: Gauthier Thurin <gthurin caiiiii@@maille mm..l..ii.ensff....
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Optimal Transport-basee -bsed Conformal Prediction
black-box model.
from typical strategies, which rely on scalar scores. Such multivariate scores can particularly be useful for quantifying uncertainties, as described in the examples below.
Contributions. In this work, we introduce novel general CP framework that accommodates multivariate scores, en- abling more expressive representations of prediction errors. The core idea is to leverage Kange-Kantorovich (MK) quan- tiles (Chernozhukov et al., 2017; Hallin et al., 2021), 1) a mul- tivariate extension of traditional scalar quantiles rooted in optimal transport theory with various applications (see e.g., Carlier et al., 2016; Hallin, 2022; Rosenberg et al., 2023). MK quantiles are constructed by mapping multidimensional scores onto a reference distribution. The resulting CP frame- work, called OT-CP for Optimal Transport- based Conformal Prediction, effectively captures the structure and dependen- cies within multivariate data while ensuring distribution- ranks, thanks to the distinctive properties of MK quantiles (Deb & Sen, 2023; Hallin et al., 2021). We demonstrate that OT-CP constructs prediction regions with finite-sample cov- erage guarantees. These hold for any choice of multivariate score function, which makes OT-CP a robust and practical tool to address complex uncertainty quantification task.
Example 1 (Multi-output regression). In multi-outpus re- gression, both the response Y and prediction f(X) take val- ues in R One can consider multivariate scores s(Y. f(X)) corresponding to component-wie prediction errors (see Sec- tion 3), without the need of aggregating them into a single value (e.g., by considering the mean squared error). Fig- ure I(a) illustrates 2-dimensional scores in context of bivariate regression.
Example 2 (Multiclass classification). Consider a clas- sification setting with K Z 3 classes and let f(x) = ( [z) be the estimated class probabilities returned by classifier for some input Denote by v= {1 the one-hot encoding of a label y. A multivariate score can be formed as the component-wise absolute difference
s(x, y) = |+(=) - E
(1)
This score retains K-dimensional predictive information, allowing for the exploration of correlations between its com- ponents. For instance, when K = 3. consider two inputs I and x2 with output probabilities ((1)) = (0.6, 0.4, 0) and At (xx2) = (0, 0.4, 0.6). For both predictions, assessing the conformity of y = 2 with a typical score 1- h (y(2) used in CP for classification would return the same value of 0.6. This potentially ignores that co-occurrences between labels and 2 might be more frequent than between 2 and 3. In contrast, the multivariate alternative (1) distinguishes these two probability profiles, as s(x,, y) + s(22, y). This can be more helpful to capture the underlying confusion patterns of the predictor across different label modalities.
After presenting the general OT-CP methodology with its theoretical guarantees (Section 2), we apply it two typi- cal learning tasks: multi-output regression (Section 3) and classification (Section 4). For each of these, we use mul- tivariate score functions which, when integrated in OT-CP, yield prediction regions that effectively capture correlations between the score dimensions. In the context of regression, we also develop an extension of OT-CP that conditionally adapts to input covariates, further enhancing the flexibil- ity of our method. Moreover, we show that this adaptive version provably reaches asymptotic conditional coverage. These two case studies serve dual purpose: they highlight the versatility and fise-friendllness of OT-CP while offering concrete frameworks to evaluate its benefits over existing methods through numerical experiments. In doing so, we believe this lays a solid foundation for future explorations of OT-CP across a wider range of applications. The code used to produce the results in this paper can be accessed at this GitHub repository.
In the rest of the paper, we denote by (5:)_=1 = {s(X,, Yi the scores computed on the calibration set.
2.2. Optimal transport toolbox
In the context of conformal prediction, dealing with multi- variate scores implies defining an adequate notion of mul- tivariate quantiles. To do so, we view the non-conformity scores { through the empirical distribution én n E ōs, and leverage optimal transport (OT) tools, more specifically, Monge- Kantorovich quantiles.
2. Methodology
1
2.1. Setting
Definition 2.1 (Empirical Monge-Kantorovicl ranks, Cher- nozhukov et al. (2017); Hallin et al. (2021)). Consider the reference rank vectors { given by
We consider a pre-trained black-box model f: X + V, where X' and y respectively denote the input and output spaces of the learning task. Assume we have access to a set of n exchangeable observations (X,, Y:) E X' x XV, not used during the training of f and referred to as the calibration set. Consider a score function X x y + R. that produces d 21 1 non-conformity scores, measuring the discrepancies between the target Y; and the prediction (X.).
Vi (1......., U, U, -0,
.),
0,
(2)
where Og are i.i.d. random vectors drawn uniformly on the Euclidean sphere gd-1 = {0 E Rd ||0|| 1}. The Monge- Kantorovich rank map is defined for any score 8 E IRd as
Considering a multivariate score in the context of CP departs
R₂ = argmax { {UU,, - -,, (U.)) Uaisign
(3)
2

---

Optimal Transport-basee Conformal Prediction
Remark 2.2. The choice of reference rank vectors (U) in Definition 2.1 is flexible and can be tailored specific needs, provided that [S:) and {U+ J remain indepen- dent (Ghosal & Sen, 2022, Remark 3.11). The convention adopted in Definition 2.1 has the merit to fix the ideas and to be appropriate for regression tasks.
2.3. OT-based conformal prediction (OT-CP)
We present a new methodology, OT-CP, that leverages opti- mal transport to perform (split) conformal prediction with multivariate scores. Unlike traditional CP approaches, our method relies on a multivariate perspective to quantify un- certainties and construct prediction regions through Monge- Kantorovich vector quantiles. Given confidence level a E [0, 1], the proposed framework consists of three steps:
(a) Multivariate scores {5: (b) Reference rank vectors (U:)==)
Figure 1. Ranking multivariate scores using optimal transport. The colormap encodes how the 2-dimensional scores |e in (a) are transported onto the reference rank vectors {U,)__ in (b).
1. Multivariate score computation: Compute the mul- tivariate scores (5 = Y))EE on the cali- bration set ((,,, Y)
with the the potential solving the dual of Kantorovich's OT problem, i.e.,
en = argmin P
(U,) Σ 0 (S.),
2. Quantile region construction:
(a) Split the calibration set into D1 and D2 of respec- tive sizes nı and n2 such that 71 + = n,
where the optimization is performed over the set of onver-semicontinuuus convex functions, and (x) sup,, ((x, u) - (p()) is the Legendre transform of a convex function yp.
(b) Compute the MK rank map R., based on D1, Construct the MK quantile region,
(a) = {s: 8: RR, (s)ll S (m2+1)a)) }. (5)
Note that R, verifies R., (S,) = Uo. (1) for i E .n.........
where on is the solution of the assignment problem
where P](n++])a] is the [(n2 + 1)aaa= small- element of Rl, (s(X,, Y.)) (X,, Y)) D2).
On = argmin
Σ SS - Uo(s)
(4)
P.
for P., the set of all permutations of (1, [1,...,,,) ,n].
Prediction set computation: For a test input Xtest from the same distribution as the calibration set, return the prediction region,
This transport-basee rank map echoes the one-dimensional case, with {U,)== replacing traditional ranks {1, .,,,.....) n) based on univariate quantile levels { 2 ....., 1]. By def- inition, [s)]l E ( 2. : 1} for any RRd. This allows to introduce specific ordering of Rd, namely
(X y s ((Xeet, y) E @n(a))
The key novelty of OT-CP lies in the use of multivariate scores (step 1) along with the construction of an OT-based confidence region (step 2). By definition, this region lever- ages multivariate quantiles of the empirical distribution of calibration scores, accounting for marginal correlations within their components. Our methodology enables the con- struction of confidence regions without predefined shapes, thereby aligning better with the underlying data distribu- tion. In step 3, the prediction set for new input Xtest is evaluated through the preimage by the score function of the quantile region. This generalizes the one-dimensional case, where classical quantiles are used to construct prediction sets in the form of intervals.
$1 SR. $2 if, and only if, [s)]l S [R)(l)
This multivariate ordering is illustrated in Figure A main virtue is its ability to capture the shape of the underlying probability distribution. Another notable advantage of Defi- nition 2.1 is that the ranks are distributton-free: by construc- tion, (S.)ll,
RR,, (S,))l correspond to random permutation of 2 2 1}. regardless of the distribution of the non-conformity scores (S.)
This concept of multivariate rank allows the construction of multivariate quantile regions, which play a central role in our methodology, as we will see in the next section.
3

---

Optimal Transport-basee based Conformal Prediction
Extending conformal prediction to the multivariate setting using optimal transport quantiles poses non-trivial chal- lenges, as standard distribution-free arguments do not di- rectly apply. To address these subtleties, we introduce a careful splitting strategy (Kuchibhotla, 2020, $3.3.1) in step 2. which helps to provide explicit theoretical coverage guar- antees for our OT-CP method.
region Ea (Xtett with probability at least a. Moreover, this coverage probability is shown to be of the order of o, heing upper-bounded by a + /ities (n2 + 1) with n2 the size of the subset D2 and Riiie E {1..... R2 + 1}. The factor in this upper bound naturally arises from the discrete feature of the MK rank map (3) and our splitting procedure, which may introduce ties in the ranking process, Note that a tie- breaking rule can be applied if ties occur, as usually done in CP (Angelopoulos & Bates, 2023) to enforce fliies = 1.
Remark 2.3 (Computational aspects). Our approach re- quires solving an optimal transport problem between two discrete distributions, each consisting of n points. In the case of univariate scores, this OT problem simplifies to a sorting operation, thus one recovers the standard On log n) cost. In the multivariate case, the OT problem is generally solved via linear programming, inducing a computational complexity of (n²)). For the numerical experiments carried out in this paper, the computational times remain reasonable, as reported in Appendix D.4. In large-scale settings, effi- cient approximation methods can reduce the computational complexity to (n²²) (Peyré et al., 2019), as exploited in the entropic OT-CP methodology of Klein et al. (2025).
While OT-CP can be applied to any model and score func- tion, the next sections focus on specific settings to clearly demonstrate its benefits and potential.
3. Multi-Output Regression
This section examines the application of OT-CP for multi- output regression. First, we demonstrate how this approach accommodates arbitrary score distributions, enabling the cre- ation of diverse and data-tailored prediction region shapes. Next, we introduce an extension of our method, called OT- CP+, which incorporates conditional adaptivity to input covariates. We demonstrate its effectiveness both empiri- cally and theoretically, establishing an asymptotic coverage guarantee for OT-CP+.
2.4. Coverage guarantees
Next, we show that the prediction regions constructed with OT-CP are valid, meaning they satisfy the coverage property. guarantee). Suppoxe {(Xeest Yiest) are exchangeable.
Theorem 2.4
(Coverage
3.1. OT-CP can output non-convex prediction sets
{(X,, v.)) Let a (0,1) such that [a([12 + +1)1 S n22 The prediction region Co constructed on {(X,, 1.) satisfies
For any feature vector X E R2 and response vector Y Rd. we aim to conformalize the prediction f(X) returned by given black-box regressor.
a S P(Yeest E (Xtest))
+
Otiis
122 +11
CP methods for multi-output regression. To further motivate OT-CP in this context, we first review existing conformal strategies, that can be reinterpreted as leaning on multivariate quantile regions. A more comprehensive discussion can be found in Appendix C. One could con- sider vanilla CP relying on univariate aggregated score, s(z,8) v) = Ily - f(x)].- This yields spherical prediction regions (f(x)) + Ball (Ta)) where Ball (Ta) is the Fu- clidean ball of radius To > O. One can also treat the d components of Y E Rd separately to produce prediction regions based on hyperrectangles, (Neeven & Smirnov, 2018). However, these approaches are often ill-suited to accurately capture the geometry of multi- variate distributions. In particular, the output prediction sets (whether spherical or hyperrectangles) can be too large when handling anisotropic uncertainty that varies across different output dimensions. To mitigate this, prior works have intro- duced scores that account for anisotropy and correlations among the residual dimensions, with ellipsoidal predic- tion sets (Messoudi et al., 2020; Johnstone & Cox, 2021; Henderson et al., 2024). Still, this implicitly assumes an
where the probability is taken over the joint distribution of (X,,Y))) U {(Xust; Yrest) and Diies (1,..... n2
1) is the maximum number of ties in BlI (x(X,, Y.)II (X,,)) E D2) U Rl, (Sres))l ) (ie., each distinct value in this sample appears at most Tries times).
We present two proof strategies for Theorem 2.4 in Ap- pendices B.1 and B.2. The main challenge lies in extend- ing the desirable properties of univariate quantiles, namely cecributtion-rrennss (see, e.g., Hallin et al., 2021) and sta- bility, to the multivariate setting, However, the stability arguments invoked in standard proofs of the quantile lemma (see, e.g., Tibshirani et al., 2019) do not directly apply here, as they rely on unresolved theoretical questions in optimal transport. To address this difficulty, inspired by Kuchibhotla (2020), we adopt a splitting strategy that enables us derive multivariate analogue of the quantile lemma. Indeed, the rank of a new sample score among the n22 calibration scores D2 is guaranteed to follow a uniform distribution, ensuring valid prediction regions without distributional assumptions.
{f(x)) + II [a,, by]
Theorem 2.4 ensures that, for a given coverage level a E (0, 1), the true label Yeest belongs to the OT--aase prediction
'The expression involves the Minkowski sum between two sets: for two sets A and B, A + B {a + b, E A, b E B}.
4

---

Optimal Transport-ber -based Conformal Prediction
samples
Rx)
MKK prediction sets
0.8
Volune of www.ertddnnnnnnoo 243
0.6
10350
0.
0 75 04 29 75.595
02
01-57
REET
(a) Prediction fx) and prediction (b) Scores (residuals) with differ- ent quantile regions
(c) Coverage
(d) Volumes
sets (1)
Figure 2. Conformal multi-outpul regression with OT-CP on simulated data
elliptical distribution for the non-conformity score, thereby compromising the distribution-Pi -rree nature of the method.
the a-coverage guarantee OT-CP achieves greater efficiency, producing smaller and more precise prediction regions. This highlights that MK quantiles help effectively address uncer- tainty quantification challenges for multi-output regression.
OT-CP for multi-output regression. Our strategy consists applying OT-CP with multivariate residual as the score,
s s(x y) = - f(x) e Rd
(7)
3.2. OT-CP+: an adaptive version
and yields the following prediction regions
So far, the form of the constructed prediction regions (8) does not depend on the input X, as illustrated in Figure 2(a). This uniformity stems from computing quantile regions over the distribution of scores {S:) marginalized over ((x, Y=) In other words, {S.) are treated as i.i.d. realizations of quantile regions provided by OT-CP effectively capture the global geometry of the scores, they do not adapt variations in X. This lack of adaptivity is inadequate in applications where prediction uncertainties vary between input exam- ples, as discussed by Foygel Barber et al. (2020). The quest for adaptivity led to a rich and diverse literature, see Cher- nozhukov et al. (2021); Gibbs et al. (2023); Sesia & Romano (2021); Romano al. (2020a) and references therein, fo- cusing mainly on the design of the univariate score function. We also refer to the concomitant work of Dheur al. (2025) for a benchmark of CP methods in the case of multi-output regression. In the following, we propose a complementary perspective through conditional MK quantiles on multivari- ate scores to accommodate input adaptiveness.
Vx E R", (x)x) = {())} + (a).
These sets can take on flexible, arbitrary shapes, that adapt the calibration error distribution and the underlying data geometry. This key advantage is illustrated concretely in numerical experiments below.
f(X). As result, while the
Numerical experiments. In what follows, we study prac- tical regression problem and compare several CP methods described above: OT-CP for forming prediction regions as in (8), a CP approach producing ellipses (ELL, Johnstone & Cox, 2021),, and simple method creating hyperrectan- gle (REC, Neeven & Smirnoy, 2018), with the miscoverage level adjusted by the Bonferroni correction. We simulate univariate inputs X ~ Unif([0,2) 2]) with responses Y e R², and we assume that we are given a pre-trained predictor f(x) = (2x², (x + 1)?), E R. We interpret the score -Y
as random vector Ç distributed from mixture of Gaussians and independent of X, meaning that the distribution of s (X,YV Y) remains unchanged when condi- tioned on X. Quantile regions for a 0.9 are constructed using n 1000 calibration instances. More implementation details can be found in Appendix D. As expected, OT-CP prediction regions exhibit superior adaptability the dis- tribution of residuals, whereas hyperrectangles and ellipses tend to be overly conservative (Figures 2(a) and 2(b)). We also compare the methods in terms of empirical coverage on test data (Figure 2(c)) and efficiency (volume of predic- tion regions, Figure 2(d)). While all approaches adhere to
Methodology. To account for input-dependent uncertainty in the predictions, we introduce OT-CP+, a conformal pro- cedure that computes adaptive MK quantile region by lever- aging multiple-outph quantile regression (del Barrio et al., 2024). Consider the calibration data splitting into D, and D2, as in step 2 of OT-CP. Given a test point Xtest, we compute the conditional MK rank map (- based on the k-neessst neighbors in Dj of Xtest (and subsam- ple of k reference vectors). Given coverage (0, 1),
5

---

Optimal Transport-ber -base Conformal Prediction
samples
1.0
Worol Word Coveage
Predittio foo
Went Ooverigg
MK prdd
0.6
Veleed DECP
0.
02-
04
0.0
10.0
000 20 25,44.25 2,00
02
Dat
X
(a) Low data regime (s 1500 total (b) Medium data regime samples)
0.0
Maggm (0.25, 0.5] [1,5,2]
(9000 total samples)
(a) Adaptive prediction regions
(b) Conditional coverage
Figure 4. Conditional coverage on real datasets of two adaptive conformal procedures for multi-output regression
Figure 3. Adaptive conformal regression with OT-CP+
model as the regressor. Both methods use a kNN step that selects 10% of the calibration set as neighbors for each test point Xtest- As a coverage metric, we consider the worst-set coverage, minje(l......)) P(Yeest (X E A,,), a partition of the input space tailored to the test data. This metric is conceptually similar the worst- slab coverage (Cauchois et al., 2021), which considers spe- cific partitions in the form of slabs. In our approach, we obtain J = 5 regions {Aj (A))ee( by clustering, i.e. em- ploying (i) a random selection of centroids, and (ii) a KNN procedure ensuring that each region contains 10% the test samples. Empirical results presented in Figure 4 provide evidence supporting the approximate conditional coverage achieved by OT-CP+. Indeed, the worst-set coverage of OT- CP+ remains consistently close to the target level a 0.9 across all datasets, regardless of the sample size or the data dimension. This contrasts with the adaptive ellipsoidal ap- proach, which does not achieve such a-coverage and ex- hibits greater variability. We note, however, that OT-CP+ tend overcover for datasets with the lowest sample sizes (namely 'atpld' and 'jura', both with around 350 samples; see Table 1). We also report the marginal coverage, vol- ume and computational time in Figure 13: our results show that OT-CP+ satisfies approximate conditional coverage at the price of larger set sizes on average and runtimes when compared with local ellipsoids.
calibrate the threshold 1]a)++)aa] using the conditional rank maps Rx(-lz) for the inputs associated with D2. The obtained quantile region is given by,
= {s: [| teet)) S P[(
with {A;
We defer to Appendix A for a detailed methodology. Hence, OT-CP+ relies on the distribution of s(X, Y) given X, which is upproximated on a neighborhood of X. The pre- diction regions returned by OT-CP+ thus given by
(Xtest) {f(ees))) + Qu(al(Xeat)
(9)
Experiments on simulated data. We first consider simi- lar setting as that of Section 3.1, where the score s(X, Y) is now distributed as VXÇ. Consequently, the variance of the residual increases with X, which suggests that wider quantiles should be constructed for larger values of X. Fig- ure 3 confirms that OT-CP+ effectively constructs adaptive prediction regions with the desired a-coverage. To quan- tify this more precisely, we evaluate the empirical cover- age conditionally on X: Figure 3(b) reports box plots of PY E (X E Z) for several choices of sub- sets I C [0, 2]. showing that OT-CP+ satisfies approximate conditional coverage. Note that computational time is larger for OT-CP+ than OT-CP, as it requires to solve multiple OT problems (see Figure 12 in Appendix D.4).
Asymptotic conditional coverage. In the one-dimensional case (d 1), Lei et al. (2018) established the inherent limitation of achieving exact distribution free conditional coverage in finite samples. However, asymptotic conditional coverage remains attainable under regularity assumptions (Lei et al., 2018; Chernozhukov et al., 2021). OT-CP+ bene- fits from such a guarantee, leveraging asymptotic properties of quantile regression for MK quantiles (del Barrio et al., 2024). The following assumption is needed.
Experiments on real data. Next, we evaluate OT-CP+ on real datasets sourced from Mulan (Tsoumakas et al., 201 1),
with dataset statistics summarized in Table 1. We also im- plement a concurrent CP method (Messoudi et al., 2022), that is an adaptive extension of the previous ellipsoidal ap- proach (Johnstone & Cox, 2021). Specifically, Messoudi et al. (2022) construct ellipsoidal prediction sets that ac- count for local geometry, by estimating the covariance of Y|X with the k-nearest neighbors (kNN) of X.
Assumption 3.1. Suppose that (Y),,) (X,....,,......... Yn). (Xrea, Yuea) are i..dd Assume that for almost every x. the distribution Ps|x=z of s(X Nesst Yust)) ) given X
We split each dataset into training, calibration, and testing subsets (5%%-25%. 25% ratio) and train a random forest
6

---

Optimal Transport-basee Conformal Prediction
is Lebesgne-absoluutly continuous on its convex support Supp(Pssx==e) For any R > O, suppose that its density p(11z) verifies for all s E (upp(Ps|x=z) A S p(s|r) S At--
Bally--((B)
Theorem 3.2. Let k. be the number of nearest neighbors used to estimate Rx(-(x). Assume that k + too and k/nn - O as n, - +oc. Under Assumption 3.1, the following holds for any a E [0, as R22 + +00,
(a) 8 ys (2%)
(b) s yi (xx)]
P( E (Xesst))))) X =
Figure 5. Ordering must depend on the chosen scores: (a) Center- outward for signed errors, (b) Left-to-right for absolute errors
(10)
where Ca) = {f(x)] + 2x (alx) depends on f previ- ously learned on (fxxdd training data.
where the absolute value is taken component- and Y = +1y=+)}= denotes the one-hot encoding of Y. One can remark in passing that [[s(x, = 2(1 (z)), which corresponds to the aforementioned IP scalar score. Our OT-CP procedure builds upon generalized quantiles to take into account all the components of fy(x)) (and not only the largest values) and to capture the correlations between them. The score in (11) takes values in R and naturally in- duces left-to-right ordering. This contrasts with the score function used in our previous application, multi-output re- gression, where the ordering is center-outward. To further clarify this difference, let us focus on a single component of the score, s(x, y)k, for simplicity. A center-outward interval of the form of [4a/2 41-a/2 applied to s(x, y) excludes lower values from [0, 9a/2) (Figure 5(a)). This exclusion problematic for the score structure induced by (11), since lower values of s(z, y) indicate greater conformity be- tween x and the ground-truth y. In this context, left-to-right ordering is more appropriate, as illustrated in Figure 5(b).
We note that OT-CP+ is not the only way to make OT-CP adaptive: our proposed methodology aims to demonstrate that conditional coverage can be achieved with only slight modification of the generic OT-CP framework. In addition to being easy to implement, the added A-NN step allows us to leverage established results on the consistency of quantiles (Biau& & Devroye, 2015; del Barrio et al., 2024), which serve as the foundation for our Theorem 3.2.
4. Classification
In this section, we apply OT-CP to multiclass classification. Each data point consists of a feature-lahel pair (X,Y) Y) E IR (I,....K with K the number of classes. The given black-box classifier outputs, for any input X IR, vector # (XX) of estimated class probabilities, where the k-th component (X) is the probability estimate that X belongs class l (hence, Σk= मn (X) = 1).
CP methods for classification. Commonly used scores for multiclass classification include the Inverse Probabil- ity (IP), s(x, = 1 ( and the Margin Score (MS), s(x, y) = +y (x) - (xx) (Johansson et al., 2017). IP only considers the probability estimate for the correct class label (z), whereas MS also involves the most likely incorrect class label (maxy'*y Fy ft- (2)). More adap- tive options argue in favor of incorporating more class labels in the score function (Romano et al., 2020b; Angelopoulos et al., 2021; Melki et al., 2024). The idea is to rank the labels from highest to lowest confidence (by sorting the probabil- ity estimates as (x) 2 (1x)) 2 ... 2 (xx) (a:)), then return the labels such that the total confidence (i.e., the cumulative sum) is at least a. It is worth noting that this strategy stems from a notion of generalized conditional quantile function (Romano et al., 2020b), by analogy with infoER (P <|,-- = x) 2 a).
(a) Multivariate scores (b) Positive reference rank
{S corresponding absolute errors in R
vectors (U))e ja
Figure 6. Positive reference ranks for a left-to-right ordering. The colormap encodes how the 2-dimensional scores {S. in (a) are transported onto the reference rank vectors [U:)2 in (b)
A left-to-right ordering can be easily achieved by making a slight adjustment to Definition 2.1: we choose the reference rank vectors as U, = * where 6 is uniformly sampled in {e E R4. : ||0]] = 1}. As depicted in Figure 6, the resulting MK ranks reflect the desired left-to-right ordering.
OT-CP for multiclass classification. As an alternative CP method for this problem, we propose using OT-CP with the following multivariate score,
s ((,Y)) A --((X] E RK
(11)
7

---

Optimal Transport-ber -base Conformal Prediction
6.9
0.0
0.9
4.4
0.7
0.6
OTCP
Methed
Mehhod
(a) Simulated data
(b) WSC coverage
(c) Average size
(d) Informativeness
Figure Conformal classification by Quadratic Discriminant Analysis on simulated data
worth noting that this adjustment is fully compatible with the general definition of MK quantiles, which is flexi- ble enough accommodate arbitrary reference distributions (see Remark 2.2). Based on this choice of score (11) and reference rank vectors, OT-CP generates the following pre- diction sets.
in Figure 8. We finally emphasize that the numerical ex- periments were designed as prototypes to demonstrate how OT-CP can be seamlessly and effectively adapted to typical classification tasks. The focus is on demonstrating a useful application of our general framework, which already shows several benefits while remaining conceptually simple.
(x) E +x)] E @n(a)).
5. Conclusion and perspectives
where the region (-) is constructed from {U:] (
We have introduced general and versatile framework for conformal prediction grounded in optimal transport theory, This approach not only revisits classical CP methods based scalar scores, but also extends easily to handle multi- variate scores in a novel and robust manner, thanks to the inherent properties of Monge-Kantorovin quantiles. The OT-CP methodology is flexible, enabling the construction of prediction regions tailored to diverse scenarios, besides being well-suited to capture complex uncertainty structures.
Numerical experiments. We compare OT-CP against IP, MS and APS scores in terms of worst-case coverage (WSC, measuring conditional coverage, as proposed in Romano et al. (2020b)), efficiency (average size of the predicted set) and informativeness (average number of predicted sin- gletons). More implementation details are given in Ap- pendix
We start by simulating data according Gaussian mixture model, represented in Figure 7(a) and we consider pre- trained classifier based on Quadratic Discriminant Analysis. Figures 7(b) to 7(d) outline that OT-CP successfully retains the efficiency and Soormativeness-alllaaatttt of IP and Mh-while simultancously enhancing conditional coverage on X, akin to the improvements achieved by APS. These results highlight that OT-CP effectively handles arbitrary probability profiles by leveraging the entire softmax output, rather than relying solely its sum, construct more informative and meaningful prediction sets.
However, in the setting of multi-output regression, ap- proach may be observed to be more conservative than the ellipsoidal one. We identify opportunities for improvement in this direction by employing more suitable reference dis- tributions for instance. Moreover, the flexibility of the ap- proach, rooted in the Monge- Kantorovich quantile formu- lation, comes the cost of increased computational com- plexity compared to conformal methods based univariate scores. An alternative transport- based method to achieve better computational and statistical efficiency with respect to the scale of the problem is to use entropic maps, as in the concomitant work by Klein et al. (2025).
The relevance of OT-CP is also confirmed on real datasets. In Figure and Figure 9, we present the results for a random forest on MNIST and Pashion-MNIST Additional numeri- cal experiments are provided in Appendix D. Interestingly, despite not being explicitly designed for this purpose, OT- CP achieves conditional coverage with respect to the label on par with APS, where IP and MS fall short, as highlighted in Figure 9. In addition, OT-CP maintains the efficiency and informativeness of IP and MS, offering a convenient balance across all the considered metrics, as one can observe
In addition, the OT-CP methodology could be adapted to new learning tasks. One might think of multi-label clas- sification where the multivariate score (11) immediately applies by replacing the one-hot encoding by a multi-hot en- coding, see, e.g., Katsios & Papadopoulos (2024) for related ellipsoidal inference. One could also explore the develop- ment more sophisticated multivariate scores, potentially building on existing alternatives (e.g., Tumu et al. (2024);
8

---

Optimal Transport-basee Conformal Prediction
APS
OTCP
1.0
1.50
1.00
0.0
0.76
04
0.50
0.26
0.00
MNIST
FASHION
MNIST
FABHION
Dete
Data
(a) Average size
(b) Informativeness
Figure 8. Classification metries MNIST and Fashion-MNIST results averaged over the 10 labels
Method
Method
1.0
1.0
0.9
Coverage
0.8
Coverage
0.8
0.7
0.6
0.5
0.5
3
7
Label
Label
(a) MNIST
(b) Fashion-MNIST
Figure Label-wise coverage on K 10 classes of MNIST and Pashion-MNIST
Wang et al. (2023); Plassier et al. (2024) for regression; and Angelopoulos et al. (2021); Melki et al. (2024) for classi- fication). Indeed, our numerical experiments demonstrate that basic multivariate scores can outperform classical uni- variate counterparts, providing supplementary motivation for pursuing into this direction.
References
Angelopoulos, A. N. and Bates, S. Conformal predic- tion: gentle introduction. Foundations and Trends@ in Machine Learning, 16(4):494-591 2023. ISSN 1935- 8237. doi: 10.1561/2200001001.
Angelopoulos, A. N., Bates, S., Jordan, M., and Malik, J. Uncertainty for image classifiers using confor- mal prediction. In International Conference Learning Representations, 2021.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Biau, G. and Devroye, L. Lectures on the nearest neighbor method, volume 246. Springer, 2015.
Acknowledgments
Bogachev, V. I. and Ruas, M. A. S. Measure theory, vol- ume 1. Springer, 2007.
The authors would like to thank Gilles Blanchard for help- ful discussions regarding exchangeability and sampee guarantees. This work benefited from state aid managed by the National Research Agency ANR-23-IACL--00S under France 2030, for the project PR[AIJRIE-PSAL
Bogoya, M., Böttcher, A., and Maximenko, E. A. From
convergence distribution to uniform convergence. Boletín de la Sociedad Matemática Mexicana, 22:695- 710, 2016.
Braun, S., Aolaritei, I.., Jordan, M. I,, and Bach, F. Mini-

---

Optimal Transport-basee Conformal Prediction
mum volume conformal sets for multivariate regression. arXiv preprint arXiv:2503.19063 2025.
Ghosal, P. and Sen, B. Multivariate ranks and quantiles using optimal transport: Consistency, rates, and non- parametric testing. The Annals of Statistics, 5012):0012- 1037, 2022.
Carlier, G., Cheroozuukov, V., and Galichon, A. Vector quantile regression: optimal transport approach. The Annals of Statistics, 44(3):1165-114) 2016.
Gibbs, I, Cherian, J. J., and Candès, E. J. Conformal prediction with conditional guarantees. arXiv preprint MIXiv:2305.12114 2023.
Cauchois, M., Gupta, S., and Duchi, J. C. Knowing what you know: valid and validated confidence sets in mul- ticlass and multilabel prediction. Journal of machine learning research, ((81)):142, 2021.
Hallin, M. Measure transportation and statistical decision
theory. Annual Review of Statistics and Its Application, 91):401-424, 2022.
Chemoohukov V., Galichon, A., Hallin, M., and Henry, M. Monge-Kantorovich depth, quantiles, ranks and signs. The Annals of Statistics, 45(1):223 - 256, 2017. doi: 10.1214/16-A0S1455
Hallin, M. and Paindaveine, D. Optimal tests for mul- tivariate location based on interdirections and pseudo- mahalanobis ranks. The Annals of Statistics, 30(4): 103- 1133, 2002.
Chernozhukov, V., Wüthrich, K., and Zhu, Y. Distribu- tional conformal prediction. Proceedings of the National Academy of Sciences, 118(49):e1107794118 2021.
Hallin, M., del Barrio, E., Ahesst--Abertos, J., and Matrán, C. Distribution and quantile functions, ranks and signs in dimension A measure transportation approach. The Annals of Statistics, 49(2):1139 1165, 2021. doi: 10.
Deb, N. and Sen, B. Multivariate rank-based distribution- free nonparametric testing using measure transporta- tion. Journal of the American Statistical Association, 118 (541):192- 207, 2023.
1214/20-AOS
Henderson, I., Mazoyer, A., and Gamboa, Adap- tive inference with random ellipsoids through confor- mal conditional linear expectation. arXiv preprint arXiv:2409.18500 2024.
del Barrio, E., Sanz, A. G., and Hallin, M. Nonparamet- ric multiple-output center-outward quantile regression. Journal of the American Statistical Association, pp. 1- 15, 2024.
Hlávka, Z., Hlubinka, D., and Hudecová, š. Multivari- ate quantile-based permutation tests with application functional data. Journal of Computational and Graphical Statistics, pp. 1 1-15, 2025.
Dheur, V., Fontana, M., Estievenart, Y., Desobry, N., and Taieb, S. B. Multi-output conformal regression: A unified comparative study with new conformity scores. arXiv preprint arXiv:2501.1053: 2025.
Izbicki, R., Shimizu, G., and Stern, R. B. Cd-split and hpd-split: Efficient conformal regions in high dimen- sions. Journal of Machine Learning Research, 23(87): 1-32, 2022.
Eisenberg, B. and Gan, S. X. Uniform convergence of distribution functions. Proceedings of the American Mathematical Society, 88(1):145-146, 1983.
Johansson, U., Linusson, H., Löfström, T., and Boström, H. Model-agnostic nonconformity functions for conformal classification. In 2017 International Joint Conference on Neural Networks (JJCNN) pp. 2072-2079, IEEE, 2017.
Feldman, S., Bates, S., and Romano, Y. Calibrated multiple- output quantile regression with representation learning. Journal of Machine Learning Research, 24(24):1-48, 2023.
Johnstone, C. and Cox, B. Conformal uncertainty sets for robust optimization. In Conformal and Probabilistic Prediction and Applications, pp. 72-90. PMLR, 2021.
Flamary, R., Courty, N., Gramfort, A., Alaya, M. Z., Bois- bunon, A., Chambon, S., Chapel, L.,, Corenfios, A., Fa- tras, K., Fournier, N., et al. Pot: Python optimal trans- port. Journal of Machine Learning Research, 22(78):1-8, 2021.
Katsios, K. and Papadopoulos, H. Multi-label conformal prediction with a mahalanobis distance nonconformity measure. Proceedings Machine Learning Research, 230:1-14. 2024.
Klein, M., Bethune, L., Ndiaye, E.,, and Cuturi, M. Mul- tivariate conformal prediction using optimal transport. arXiv preprint arXiv:2502.03609, 2025.
Foygel Barber, R., Candès, F. J., Ramdas, A., and Tibshirani, J. J. The limits of distribution- free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455 482, 08 2020. ISSN 2049-8772. doi: 10. 10100//aaaa//aaaa17.
Kuchibhotla, A. K. Exchangcability, conformal prediction, and rank tests. arXiv preprint 1xXi::200500609) 2020.
10

---

Optimal Transport-based Conformal Prediction
Lei, J., G'Sell, M., Rinaldo, A., Tibshirani, R. J., and Wasserman, L. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113652):1094-1111, 2018.
Romano, Y., Sesia, M., and Candes, E. Classification
with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581-3591, 2020b.
Rosenberg, A. A., Vedula, S., Romano, Y., and Bronstein, Fast nonlinear vector quantile regression. In The Eleventh International Conference Learning Representations, 2023.
Luo, R. and Zhou, Z. Volume-sorted prediction set: Efficient conformal prediction for multi-target regression. arXiv preprint trXiv:2503.02205. 2025.
Sesia, M. and Romano, Conformal prediction using conditional histograms. Advances in Neural Information Processing Systems, 34:6304-6315, 2021.
Melki, P., Bombrun, I.., Diallo, B., Dias, J., and Da Costa, J.-P. The penalized inverse probability mea- sure for conformal classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3512-3521 2024.
Sun, S. H. and Yu, R. Copula conformal prediction for multi- step time series prediction. In The Twelfth International Conference on Learning Representations, 2024.
Messoudi, S., Destercke, S., and Rousseau, S. Con- formal multi-target regression using neural net- works. In Conformal and Probabilistic Prediction and Applications, pp. 65-83, PMLR, 2020.
Tibshirani, R. J., Foygel Barber, R., Candes, E., and Ramdas, A. Conformal prediction under covariate shift. Advances neural information processing systems, 32, 2019.
Messoudi, S., Destercke, S., and Rousseau, S. Copula-based conformal prediction for multi-target regression. Pattern Recognition, 120:108101, 2021.
Timans, A., Straehle, C.-N., Sakmann, K., Naesseth, C. A., and Nalisnick, E. Max-rank: Efficient mul- tiple testing for conformal prediction. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
Messoudi, S., Destercke, S., and Rousseau, S. EI- lipsoidal conformal inference for multi-target regres- sion. In Conformal and Probabilistic Prediction with Applications, pp. 294-306. PMLR, 2022.
Tsoumakas, G., Spyromitros-Xioute E., Vilcek, J., and Vlahavas, Mulan: A java library for multi-label learn- ing. The Journal of Machine Learning Research, 12: 2411 2414, 2011.
Neeven, J. and Smirnov, E. Conformal stacked weather forecasting. In Conformal and Probabilistic Prediction and Applications, pp. 220 203. PMLR, 2018.
Tumu, R., Cleaveland, M., Mangharam, R., Pappas, G., and Lindemann, L. Multi-modal conformal prediction regions by optimizing convex shape templates. In 6th Annual Learning for Dynamics & Control Conference. pp. 1343-1356. PMLR, 2024.
Park, J. W., Tibshirani, R., and Cho, K. Semiparametric conformal prediction. arXiv preprint arXiv:2411 1000:24411.021144 1.021 2024.
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic learning in random world, volume 29, Springer, 2005.
Peyré, G., Cuturi, M., et al. Computational optimal trans- port: With applications to data science. Foundations and Trends@ in Machine Learning, 11(5-6)3355660 6075 2019.
Wang. Z. Gao, R., Yin, M., Zhou, M., and Blei, D. Prob- abilistic conformal prediction using conditional random samples. In Ruiz, F., Dy, J., and van de Meent, J.-W. (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 8814- 8836. PMLR, 25-27 Apr 2023.
Plassier, V., Fishkov, A., Guizani, M., Panov, M., and Moulines, E. Probabilistic conformal prediction with approximate conditional validity. arXiv preprint MxXiv:2407.01794 2024.
Puri, M. L.. and Sen, P. K. Nonparametric methods in multi- variate analysis. John Wiley & Sons, New York, 1971.
Romano, Y., Patterson, E., and Candes, E. Conformal- ized quantile regression. Advances in neural information processing systems, 32, 2019.
Romano, Y. Barber, R. F., Sabatti, C., and Candès, E. With malice toward none: Assessing uncertainty via equalized coverage. Harvard Data Science Review, 2(2):4, 2020a.

---

Optimal Transport-based Conformal Prediction
A. Detailed methodology for OT-CP+
The OT-CP+ procedure described detail below.
1. Multivariate score computation: Compute the multivariate scores (s(X,, X)) ;=1 on the calibration set (X,, Y))
2. Conditional quantile region construction:
(a) Split the calibration set into D, and D2 of respective sizes ny and n2 such that ni + n.. In what follows, for any æ, we refer to R+ = x) as the conditional MK rank map based on the k-nearest neighbors in Di (using & reference vectors).
(b) For each (X,, Yi) E 22, compute the conditional MK rank map R&(-IX- = X;), then compute P[ 1)a] as the [(n2 + 1)aa-ttt smallest element of,
(| X.I = x,)II (X), E D2}.
(c) For any v, compute the conditional MK rank map R = 2) and define the conditional MK quantile region as =)) = {s: (s ( x)|l S P[(m++1)a) }
(12)
3. Prediction set computation: For test input Xuest drawn from the same distribution the calibration set, return the prediction region
(X = E : v) E @u(alx = Xxest)
Hence, the main difference from OT-CP lies in using the procedure by del Barrio et al. (2024) to compute conditional MK rank maps R = z), thereby providing greater adaptivity compared to the standard MK rank map R.,(.) defined (3).
B. Proofs
This section contains the detailed proofs of our theoretical results. For clarity, and without loss of generality, we assume that the calibration set ((x,, } is split into D2 {(X, Ki) and D2 = {(X Yn fi)+t)) 1=1
) where nı n2
B.1. Proof of Theorem 2.4 (marginal coverage guarantee)
The proof of Theorem 2.4 consists in extending the reasoning for the traditional quantile lemma (e.g., Lemma 2 in Romano et al. (2019)) to a multivariate setting.
Proof of Theorem 2.4. For h E (1..... n2). , let S(k,n)) be the k-th smallest score among (Sn M2 where Sayti s( s(Xn Yns +s) and the ordering is induced by the transport map Rn, computed on Dj. Hence,
R (S(1, S R., (S(2..))) $ ... < Rn, (S (S(m)
(13)
which, using the definition of SR.,, is equivalently written as
S(1.22) SR., S(2.22) SR., SR.., ((ng
(14)
By construction, P[a(=2+1)] = |RR, (S((a(rat))) where a E (0, and [a(n2 + 1)] S n2, ensuring that the order statistic P[a(na+1]] is well defined. The quantile region (a) can be characterized as
Stest @a(a)
Stest SRn, S([o(ma+1]],ma))
(15)
Denote by m(k, the k-th smallest value (with respect to SR,,,) within (Sm + l...... Sn, Stost ). Here, we view Stest as inserted into the ordered list ( yielding new ordered list of size ne + 1. Then, Steet = S(io with
S(1 SRm, ... SRn, S(fo.))) SRn, Steet SR., S(6ot1,92) SRn, ... SRn, S(mz,n2)
(16)
As direct consequence of (16), we have
12

---

Optimal Transport-basee Conformal Prediction
for k ig. (km (k.res)
for ig + 1, 1,1++1 Stest SRn, ((1o+1,
for k > in + 1, S (k, 1(1)-1,82) SR.ng S(kmma)
Therefore, for any k E fl....,,zll n2). We show that the reciprocal also holds, Assume that Stest SRn, S(k,ns) By (16), this implies 2 in + 1, and in this case, S(B,a++)) is the larger of Stest and 1(k-1,wa) (with respect to Snm,, ). Putting everything together, we showed that
1(k, SR., ((k,2))- Hence, if Sust SR., S(k,m2+ 1)- then Stest SR., ((,,)))
Stest SR., S(K,02)
Swst SR., S(k,n+
Thus, P(Srest SR.. S(ken))) = IP(Suee Stest SRn. +1k) Hence, for any a E [0. 1].
P(Suest E (n)) = PPSSestt SR., S((a(no+))),x2-11>>>
(17)
Recall that Ories denotes the maximum number ties in (Rin (5m++),..... Ry, (Sm)+n2); R,, (Stest)). By definition of 1(), the proportion of elements from (Si,... Sn Stest } that are less than equal to S(smm++1) (with respect to mries)/(n2 + 1), due to the possible presence of ties.
SR.,) lies between (n(22 + 1) and
Since {(X,, X:) is assumed to be exchangeable, and Rn, is computed using D1. then [[]Rm,, (S,, +1 .,, RR,, (S., +n2)ll+ )ll, |Rz, (Stea))l is exchangeable (see Kuchibhotla, 2020, Proposition 3).
Therefore, by (17),
[a(n2 + +1]
S P(Seat E 2n(a)) - [a(n2 1)] + Thiies
122 +
n22 +
and we can conclude that
a: S P(Sest E @n(a)) $ a +
Thies
122 1
B.2. Alternative proof of Theorem 2.4
We provide an alternative proof of Theorem 2.4, which is similar in essence the previous but based on another perspective. To this end, we recall variant of the traditional quantile lemma adapted to our needs (i.c., when there are ties in the ranks) and detail its proof for completeness.
Lemma B.1. (Quantile lemma, Lei et al., 2018) Suppose (UI...., Un+1) is an exchangeable sequence of random variables in R. Then, for any 3 E (0, 1).
P(Un+1 S U((((n-11)) 2
(18)
Additionally, assume that the maximum number ties (iee, identical values) in (UI,..., Un+1) Atties Then,
P(Un+1 S (((T((+D))) S S
Thiiss
(19)
n+1
The probabilities are taken over the joint distribution of Unt1).
Proof. By exchangeability of (UI...., Un+1), for any i .n....,nt..
P(Un+1 U(T3((41))) P(U, < U((S(+41)))
(20)
Therefore,
n+1
P(Un+1 S (((((+1)))))
P(U, & U((3(+))))
(21)
n +
1
E
1 (
(22)
n +
a+1
1
E
10 10:
+ IL
(23)
71 +
13

---

Optimal Transport-based Conformal Prediction
Since U1(((+1)11) the [3(nn + 1)]-th smallest value of (U1,...;Une,, then E1= 1 (( 2 [3(n + 1)], and by (22),
1
P(Un+1 S U((P(n+1j)))
n n+ [[ 1)1] [B(n + 1)]
n + 23.
Additionally, under the assumption that value appears more than Thies times among the exchangeable variables, and based on (23), Ei= LulsU(ppoa11)) - [p(n + 1)1 - 1 Pties-
We conclude that,
P(Un+1 U((B(n+1)))) -
[B(n + 1)1
1 1 Mrics
SB+
Thics
n ++1
n
By using Lemma B.1 along with the properties of Kantorvcnto rank maps on our split calibration set, we can prove Theorem 2.4 as follows.
Alternative proof of Theorem 2.4. By construction of the prediction region, we have
(Fesst Ca (Xesst) Stest [n((a) || (Sust)ll S P((m2+1)a))
Therefore,
P(Yust E E, (x( (Xuss)) PP) (I) (Swst) S P((nu+1)a))
(24)
For k E (1....,ng) let S(k,2)) be the k-th smallest score among {Smiti) ta where Sniti s(Xaiti, Yiy+i) with respect to the ordering SR., (4). Hence,
Rm, (S(1.)))) S R.,, (8 S .... Rm, (S (w2.:))))
(25)
Additionally, denote by +(km)+1)) the k-th smallest value (with respect to SR.,. within (Sm Sn, Swet J. We know that [R,, (Stest) )l < Rn, (k,,g))) if, and only if, Rn, (Stest)l S |Rn, (S(k, (e.g., see the proof of Lemma' 2 in Romano et al. (2019)).
For a (0, 1) such that [1)] S n2, recall that Pfa(n2+1) the [a(nu++)]] 1)7-th smallest value {I]R,, (sn)++)))?? i.e. Pfa(ng+1)] [R,, (S (1)) Therefore. |RR,, (Stest)ll I P]a(na+1)] if and only if RR,, (Stest) ]| S
RR, (S(mat)+ By (24), deduce that
P(Yest E (Xtes))) Bn, (Stest)l & RR, ([(a(mm=+))ma+
(26)
As mentioned in Appendix B. R[, (Sny +i) 12 U Rm, (Stest) is exchangeable since {(X,, Y)) is assumed to be exchangeable and R,, is computed D, and then applied on scores computed separated set, namely D2 U {(Xtest, Yeett) (see Kuchibhotla, 2020, Proposition 3). We can thus conclude by applying the quantile lemma to ([[R,, (Sn U [ (Stest)l which is stated and proved in Lemma B.1 for completeness.
B.3. Proof of Theorem 3.2 (asymptotic conditional coverage)
As in Section 3.2, we denote by Re(-(2) (z) the conditional empirical MK rank map based on the k-nearest neighbors in Dj of and by (x(a))) the conditional MK quantile region of level a E [0, 1] (del Barrio et al., 2024). By assumption, k is function of n, satisfying k + +o and k/nj + 0 as n + +oo. For clarity, we omit the explicit dependence of k on ni in our notation.
By definition of our prediction regions (9), the desired result (10) can also be written as,
P [Ra (Sweet (xost)) S P[(n++1)a
Xersn) B a as n1, f22 + 400.
14

---

Optimal Transport-based Conformal Prediction
By applying Corollary 3.4 from del Barrio et al. (2024), we know that
Vo E [O, 1], ((IRR,(Stest (esst) )1 S X 1x as kn - +00.
(27)
Therefore, the main technical challenge of our proof is understand how the asymptotic convergence guarantee in (27) interacts with our coverage level P[]]++ To address this, will rely the following lemma.
Lemma B.2. For all E [0, 1] and n n1 + n2 lim P][ a.
Proof. Let [0. 1] and for & N let (Xtes) ([ (eeest) a Xtest) The sequence (Xxeat))) converges to in probability by (27), and is uniformly integrable since (Xt(st) S 1. Therefore, by the Lebesgue- Vitali theorem (Bogachev & Ruas, 2007, Theorem 4.5.4), limg-+00 E[fa (Xees)) )] = a, which can be written as
lim IP( (Seesa Xust)l s sa)= a
(28)
where we have used k - +00 as 121 - +0o. Hence, the sequence of random variables () R& (Stest (SStet//tesss Xteest) converges in distribution to random variable drawn from the uniform distribution in [0, 1]. Unif([O, 1]).
In addition, ([|Rg (S ++)) is a sequence of i.i.d. random variables, drawn from the same distribution as [R (Stese) uest)]: Il-- This implies that the quantile function of R, (Sn ax +1)) (denoted by q.) converges pointwise the quantile function of (S [test)l when 722 7 +00 and n is held fixed (this follows from the Clivenko-aantele theorem). Since we showed that (Stest [Xust )l)s)) converges in distribution to random variable distributed from [0, 1J). we conclude that d.. converges pointwise to the quantile function of Unif(0, (0, 1J) (denoted by g, which is continuous) as n22 + +o0.
Moreover, in our setting where all distributions are bounded, 4n converges uniformly to g. see egg. Bogoya et al. (2016). In particular, since +]]a] = Qn ([ + 1)a(//2)) limag-roo [(12 + 1)a2/n2 = a and g is continuous, one can show that lim,, 02 t0 1]] = g(a) a.
Proof of Theorem 3.2. Let R(-(Xtest) be the OT rank map associated to the conditional distribution of given Xtest For a continuous distribution, the reference distribution of such OT rank map is associated the random vector R$ for two independent random variables R and & drawn respectively from uniform distribution [0, 1] and the unit sphere. Then.
PP [1 (Stest Xxest)l S P[(m2 [)a] (rest) = An In,
(29)
where we have defined,
A F(I]R [ S P[(na+1)ai (Xreat) P
S [12+1]aa] Xtest)
r, P (( X Il S P[(m++)))] X(est) a.
Both terms can be expressed in terms of cumulative distribution functions, i.e.,
A = F& (PT(ng +1) (Xees) - (P[[(1 (Xtes)
r, F (P((m=+))a) (xest) Ox,
where F- F( ((e)Xtest) denote the c.d.f of RR |l given Xtest and [[(stest (xest) given X respec- tively. On the one hand, by the definition of conditional MK quantiles (del Barrio et al., 2024), || XXeet)] given Xtest is distributed from Uni 1)). Since limmy,ng - P[(n++]aa] by Lemma B.2, and the c.d.f of [0, 1J) is continu-
ous, then to In O. On the other hand, by eq. (27), (T(eet) _ F(T(Xtest) for every E [0, 1]. which implies the uniform convergence of FA (-e)) ) to (-e)Xtest) by continuity of F, see e.g., Eisenberg & Gan (1983). Therefore, An < sup, (reeat) - [((r[Xtest)] _4 0 as n + +o0. By (29), P P[[[ (Stert (Xest)) S P1(m)+ Xreat) _ as 11, 72 + too, which concludes the proof.
15

---

Optimal Transport-based Conformal Prediction
C. Related works in multi-output regression
Multi-output conformal regression gathers increasing interest, as exemplified by several works (Braun et al., 2025; Luo Zhou, 2025; Dheur al., 2025; Klein et al., 2025) released concomitantly to the present paper. In particular, Klein et al. (2025) also motivate the use of transport-based quantiles to deal with multivariate scores. In this section, we provide an overview of possible methods for multivariate prediction regions and we refer the interested reader to Dheur et al. (2025) for more complete comparison.
Methods based on component-wise univariate quantiles (Neeven & Smirnov, 2018) or ellipsoids (Messoudi et al., 2020; Johnstone & Cox, 2021; Henderson et al., 2024) were proposed as real-valued scores amenable to conformal multi-output regression. However, these methods could be phrased as multivariate center-outward quantiles in a generalized CP framework, hence the comparison in Section Indeed, hyperrectangle regions based on componentwise quantiles and ranks have long history when dealing with quantiles of multivariate data (Puri & Sen, 1971), although it implicitly assumes independent components. Under elliptic assumptions, Mahalanobis ranks are distribution-fiee and the associated quantiles provide an appropriate center-outward ordering (Hallin & Paindaveine, 2002). As comparison, transport-based quantiles do not make any assumption on the shape of the underlying distributions. We refer to Hallin et al. (2021) for recent review of existing notions of multivariate quantiles, with an emphasis on the distribution-freenes, of ranks.
Hereafter, we point out other existing works to design real-valued scores while adapting to the underlying data structure. To ease the readibility, we follow the terminology proposed by Braun al. (2025).
Copula-based approaches. Messoudi et al. (2021) introduced copulas in CP to model dependence in multivariate distributions. Copulas were also studied by Sun & Yu (2024) for time series datasets, and main challenge addressed by Park al. (2024) is their accurate estimation.
Multiple testing approaches. With a different perspective, Timans et al. (2025) propose a correction for CP phrased as multiple permutation testing. The reader might be interested in discussions and references therein for comparison with the classical Bonferroni correction. Additionally, one can note that multiple permutation tests were also proposed based on transport-based quantiles in Hlávka et al. (2025), although not dealing with CP.
Latent-space approaches. Recently, Feldman al. (2023) combined multivariate quantiles and CP to obtain flexible prediction sets. Their method is based on conditional variational auto-encoder for quantile regression, and they propose a calibration step to conformalize any quantile regression algorithms. In doing so, multivariate quantiles are used to accurately model the distribution of Y|X. By the way, note that OT-CP+ targets instead the conditional distribution of multivariate scores sX, X) X, in order to cope with an arbitrary underlying algorithm f(x). We also mention very recent work (Luo & Zhou, 2025) that transforms the distribution Y|X to a Gaussian distribution based on Conditional Normalizing Flows, and combines this with volume minimization.
Density-based and sampling-bass based approaches. Other flexible approaches use density estimation (Izbicki al., 2022), generative models (Wang et al., 2023) or both (Plassier al., 2024) within the real-valued score function. We also mention the work of Sesia & Romano (2021) that incorporates conditional histograms. These approaches can provide discontinuous prediction regions, which is appropriate for multi-modal datasets.
Optimization over template shapes. Regions with convex shapes can be fitted to several clusters by volume minimization (Tumu et al., 2024), to induce multi mudti-modal prediction regions. A similar optimization procedure has been recently proposed by Braun al. (2025) to design the minimum-volume set that contains a proportion a of the data. Therein, the building blocks are arbitrary norm-based sets, with potentially multiple norms yielding non-convex prediction regions.
D. Experimental Details
D.I. Optimal transport solver
In all of our experiments, optimal transport problems are solved using the network simplex method implemented in the Python Optimal Transport library (Flamary et al., 2021). This solver is written in C++/Cython, making it generally faster than pure Python implementations.
16

---

Optimal Transport-base Conformal Prediction
Method
Melhod
M5
APS
OTOP
IP
MB
AP8
OTCP
IP
MB
APB
OTCP
1.0
0.
2.0
0.8
Informaivensse
0.8
1.0
0.5
0.0
0.0
Label
Label
Label
(a) Coverage
(b) Average size
(c) Informativeness
Figure 10. Label-wiss wise results on K 10 classes of MNIST
D.2. Implementation details for regression
In Figure 2, the score s(X, Y) = Y - f(X) can be seen random vector distribbtedd 3 Ti _/. T3 = 3. m2 5 122 MM,, m2 (o) E ("3 4). Dg (3
Sm,, Ee), where
4) Lg = 6 ))
For our real data experiments, we used datasets available in Tsoumakas et al. (2011). Table specifies the number of observations and variables (for the features X and for the output Y) for each dataset.
Name
Instances
# Features
# 4'Targets
atpld
337
411
6
rfl
9125
64
8
scm20d
8966
61
16
jura
359
15
3
wq
1060
16
14
enb
768
8
2
Table 1. Details of datasets used for multiple-output regression
In the experiments involving OT-CP+ and a k-nearest neighbor search, setting = nn/10 for datasets of medium size and vn for larger datasets provides tradeoff between adaptive results and fast computational complexity.
D.3. Implementation details for classification
The implementation the ARS score relies on codes made available in the original paper (Romano et al., 2020b).
Experiments on MNIST and the Python library scikit-learn. We used 25 000 data splitted in train/calibration/eess with ratio 10%/45%/44% since this is sufficient for the classifier reach 90% accuracy and to ensure reasonable size for the test data. Metrics are computed and averaged over N = 10 repeated random draws. Additional figures 10 and 11 related to these experiments are provided below, showing detailed label-wise results.
in Figure and Figure involve a random forest classifier implemented with
D.4. Additional experiments
Computational time. In Figure 12, report the runtimes of OT-CP and OT-CP+ for the empirical settings corresponding to Figures 2 and 3, with a varying number of calibration instances. As expected, OT-CP+ is slower than OT-CP, especially as the size of the calibration set increases.
Experiments on real datasets. Figure 13 complements experiments from Figure 4 with marginal coverage, volume and computational time. One can verify the appropriate marginal coverage of both methods, which legitimates the benefits of OT-CP+ in terms of adaptivity in Figure One can observe that, for datasets with the lowest amount of samples, 'atpld' and 'jura', OT-CP may tend to slightly overcover. Figure also illustrates that OT-CP+ is more computationally intensive
17

---

Optimal Transport-basee Conformal Prediction
Method
Melhod
M5
APS
OTOP
IP
MB
APB
OTCP
IP
MB
APB
OTCP
08
Informaiveresss
0.8
0.6
0.5
0.0
0.0
Label
Label
Label
(a) Coverage
(b) Average size
(c) Informativeness
Figure 11. Label-wat wise results on K 10 classes of Fashion-MNIST
MNIST
OT-CP OT-CP+
100
Time (seconds)
40
1000
2000
3000
4000
5000
6000
Size of calibration data
Figure 12. Computational time for OT-CP and OT-CP+ against the number of calibration instances
1.0
3.0
2.5
0.8
Method OT:OP+
1.5
Mehood
Method OT-CP+
OT-CP+
1.0
0.0
0.0
won2lld
D0ta
Data
Dato
Figure 13. Marginal coverage, volume and calibration time (in seconds) for experiments Figure 4
than computing covariances in the ellipsoidal approach ELL. Nevertheless, the experiments considered here take at most few minutes, which remains reasonable.
Additional results for classification. Figure 7 illustrates OT-CP's ability to adapt to label confusions. Therein, classes O and tend to be confused by the QDA classifier. In such cases, OT-CP achieves better trade-off between coverage and efficiencyinnfommaiiveeess. When the distribution made casier (classes 0 and become more distinct for QDA) all methods yield similar efficiency and informativeness. The latter setting depicted in Figure 14. This supports that OT-CP can
18

---

Optimal Transport taanspert-baeed Conformal Prediction
1.0
0.8
0.9
Informalivenees
0.6
Efficiency
0.4
0.7
labels
0.2
0.2
0.0
MS
APS
OTCP
IP
MS
APS
OTCP
Method
Method
Figure 14. Classification by Quadratic Discriminant Analysis on simulated data, with different uncertainty pattern
Method
IP
MB
APB
OTCP
IP
MB
APB
OTOP
1.0
0.8
Informtirentt eolommlreenes
0.8
0.7
0.2
Label
Label
Label
(a) Coverage
(b) Average size
(c) Informativeness
Figure 15. Label-wise results K classes of MNIST
Method
Method
APS
APS
OFCP
IP
AP8
OTCP
1.0
1.50
0.8
Coveraga
0.8
1.00
Informslinnno
0.8
0.25
0.5
Label
Label
Label
(a) Coverage
(b) Average size
(c) Informativeness
Figure 16. Label-wise results on classes of Fashion-MNIST
effectively adapt to classification patterns where certain labels are prone to confusion.
In Figures 15 and 16, we conduct the same experiment as in Figure 9, but with subset of K 5 labels ((0, 2, 4, 6, 9} for MNIST, and { ('T-shirt/top'. 'Pullover', "Coat', 'Shirt,, 'Ankle boot'), } for Fashion-MNIST), Similar conclusions for Figure 9 apply here. Results in Figures 15 and 16 are averaged over 10 runs, each with 10 000 randomly chosen observations split in train/calibrationntess with ratio 50%, 40%, 10%. We observe that OT-CP performs better for K than for K = 10. achieving the efficiency of the IP and MS scores while improving adaptivity, akin to the APS score. This suggests that for large K, OT-CP could benefit from more tailored score functions than s(x, y) = lū *x)) E RRKK inspired e.g., by univariate penalized approaches (Angelopoulos et al., 2021; Melki et al., 2024).
19


Reviews:
[{"review_id": "PDkJWBng16", "reviewer": "Reviewer_RqtM", "summary": "The authors tackle the problem of conformal prediction in regression and classification settings when the target random variable is multivariate. To do so, they use the quantiles definition as in [1], that defines the quantile function of a r.v. $Y \\in R^n$ as the euclidean optimal transport map between a uniform random variable $U \\in R^n$ and and $Y$.\n\n[1] Chernozhukov, V., Galichon, A., Hallin, M., and Henry, M. Monge–Kantorovich depth, quantiles, ranks and signs. The Annals of Statistics, 2017\n\n## update after rebuttal\nMy novelty considerations have been addressed in the rebuttal and so I increased the recommendation to weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## General comment\n\nWe would like to thank all the reviewers for their time and feedback. We have revised the paper accordingly and provide detailed responses below.\n\n1. We emphasize that integrating multivariate quantiles into the conformal prediction framework while ensuring theoretical coverage guarantees is non-trivial. The property that ranks follow a uniform distribution, under exchangeability, is crucial. In the literature of multivariate quantiles, optimal transport tools extend this critical property (see, e.g., Hallin et al. 2021). However, the stability arguments invoked in standard proofs of the quantile lemma (see, e.g., Tibshirani et al. 2019) do not directly apply here, as they rely on unresolved theoretical questions in optimal transport. To better highlight this subtle point, we clarified Step 2 of our OT-CP methodology and explicitly demonstrate how our approach provides theoretical coverage guarantees.\n2. We have added the suggested references to improve the discussion on related work.\n3. We systematically computed the volumes of the prediction regions, precised the running times of the method, and conducted new numerical experiments to better support our claims.\n\nWe now provide detailed reponses below. While we have carefully considered all reviewer comments, we are sometimes unable to provide an exhaustive answer for every point raised due to the character limit.\n\n[Tibshirani et al.,2019] Tibshirani, Foygel Barber, Candès, Ramdas, Conformal prediction under covariate shift, Neurips 2019\n\n[Hallin et al.,2021] Hallin, Del Barrio,  Cuesta-Albertos, Carlos Matràn, Distribution and quantile functions, ranks and signs in dimension d: A measure transportation approach, Annals of Statistics, 2021\n\n## Answer to Reviewer RqtM\n\nWe thank the reviewer for their comments. We appreciate the opportunity to clarify our contribution.\n\n*\"However, since the concepts of multivariate quantiles, ranks and confidence sets are already defined in [1] and derivative work, it is not clear to me what the main contribution is.\"*\n\nWhile optimal transport-based quantiles are not new, the novelty of our work lies in integrating them into an effective and flexible conformal prediction (CP) framework designed for multivariate scores. This aligns with the CP literature, where quantiles typically serve as building blocks for uncertainty quantification strategies, rather than primary contributions. More precisely, unlike [1], we address several nontrivial challenges specific to Monge-Kantorovich quantiles for CP, including establishing both nonasymptotic and asymptotic coverage guarantees, selecting reference rank vectors $\\{U_i\\}_{i=1}^n$ that are appropriate for multivariate scores, and comparing performance with existing CP methods. \n\n*\"The paper follows the work of [1] and its derivative papers but it is not clear to me what the main novelty is.\"*\n\nOur paper goes beyond prior work on transport quantiles, including [1], by integrating them in conformal prediction, which had not been explored before. By combining these two lines of work, we make the contributions outlined above but also offer a novel perspective that could be of interest to both the machine learning and optimal transport communities.\n\n*\"May be worth noting/including in the benchmarks the paper [2], that also applies the multivariate quantile function defined in [1] to regression tasks.\"*\n\nWe thank the reviewer for the additional reference [2], which we have added to the introduction. Nevertheless, we emphasize that this paper leverages the Monge-Kantorovich quantiles from [1] to address quantile regression, and not conformal prediction.", "claims_and_evidence": "They claim to \"introduce a novel general CP framework\" for multivariate conformal prediction. However, since the concepts of multivariate quantiles, ranks and confidence sets are already defined in [1] and derivative work, it is not clear to me what the main contribution is.", "methods_and_evaluation_criteria": "Method and evaluation are sound, there is both synthetic and real data and the target dimension is reasonable.", "theoretical_claims": "I did not check.", "experimental_designs_or_analyses": "The experiment design seems sound as it is described in the paper and the code is provided. I did not check the code.", "relation_to_broader_scientific_literature": "The paper follows the work of [1] and its derivative papers but it is not clear to me what the main novelty is.", "essential_references_not_discussed": "May be worth noting/including in the benchmarks the paper [2], that also applies the multivariate quantile function defined in [1] to regression tasks.\n \n[2] Fast Nonlinear Vector Quantile Regression, AA Rosenberg, S Vedula, Y Romano, AM Bronstein, ICLR 2023", "other_strengths_and_weaknesses": "The paper is not super clear and the figures need clearer descriptions.", "other_comments_or_suggestions": "No.", "questions_for_authors": "I would like to have the main contribution of the paper better clarified.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "d2aKxXgK0U", "reviewer": "Reviewer_1SF7", "summary": "In the paper Optimal Transport-based Conformal Prediction, the authors propose a new conformal prediction framework leveraging optimal transport to produce multivariate score functions. They prove that such a framework also achieves distribution-free coverage. They validate the method for multi-output regression and multiclass classification using synthetic and real datasets. The results show how the proposed method is able to achieve asymptotic conditional coverage and provide adaptive predictive sets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive and detailed feedback.\n\n*(OT-CP+ and the use of k-nearest neighbor)*. We agree that OT-CP+ is not the only way to make OT-CP adaptive: our proposed methodology aims to demonstrate that conditional coverage can be achieved with only a slight modification of the generic OT-CP framework. In addition to being easy to implent, the added k-NN step allows us to leverage established results on the consistency of quantiles (del Barrio et al., 2024), which serve as the foundation for our Theorem 3.2. Therefore, OT-CP+ should be seen as evidence of OT-CP's inherent flexibility, showing its ability to incorporate refinements to achieve specific properties, such as adaptivity.\n\n*(OT-CP or OT-CP+)*. The results for base OT-CP and OT-CP+ are resp. presented in Sections 3.1 and 3.2: Figure 2 for OT-CP, and Figures 3 and 4 for OT-CP+. The figure titles now explicitly indicate the used method.\n\n*(Numerical results per class)*. We will add results marginalized over $Y$ to improve readability: https://ibb.co/1GV3bsdq ; https://ibb.co/nqTH1VCq ; https://ibb.co/p6jGSmXj\nSee also our answer \"OT-CP in Figures 8, 9, and 10\" for reviewer bVvm.\n\n*(Real datasets)*. In addition to the reference, we included a table in Appendix B.1 summarizing the main statistics for each dataset. Since these are directly sourced from the literature rather than created in our work, we felt that no further details were necessary. That said, we are open to add any relevant information if needed.\n\n*(Reference not discussed)*. Thank you for the suggestion. We will expand Remark 2.3 by referencing Sections 3 and 4 of Peyré & Cuturi (2019) for an overview of solvers for OT.\n\n*(Computational comparison between baselines and the OT-CP)*. The calibration time corresponding to Fig. 4 (OT-CP+ compared with ELL) will be added in the appendix, https://ibb.co/YTtv36ZM\n\n*(Computational complexity)*. Including the k-NN increases the required complexity, as illustrated in https://ibb.co/hpyCyFN. For all the experiments carried out in this paper (up to $n=10\\,000$ points), the computational time of OT-CP is fast thanks to the Python Optimal Transport library (which solves OT with a simplex implemented in C++). OT-CP+ is more demanding than OT-CP, as it solves one OT problem per new test point. The parameter $k$ drives the computational time, and our Theorem 3.2 only requires that it grows slower than $n$ (see next answers).\n\n*(Choice of k in k-NN)*. As the reviewer correctly pointed out, $k$ should be chosen carefully to ensure asymptotic conditional coverage. More precisely, our Theorem 3.2 shows that k should grow to $+\\infty$ as $n \\to +\\infty$ at a slower rate than $n$ (this point is further clarified below, in \"Questions for Authors\"). In our experiments, setting $k = n/10$ provides a tradeoff between adaptive results and fast computational complexity. Thank you for your comment: we agree that this is an important aspect to highlight that has been added in our paper.\n\n*(OT-CP and full CP)*. OT-CP can be adapted to full CP and would consist in solving OT on the entire training dataset and every candidate $(X_{test}, y)$. Similar to full CP methods, this would improve statistical efficiency and reduce variability by avoiding data splitting, at a price of increased computational cost.\n\n*(Asymptotic conditional coverage)*. Indeed, Theorem 3.2 applies to the quantile region computed with the $k$NN step, under some mild assumptions on $k$ as a function of $n$. We provide more explanations on this point below.\n\n*(Assumption on k and n)*. The assumption is $k \\to +\\infty$ as $n \\to +\\infty$ **and** $\\frac{k}{n} \\to +\\infty$. This means $k$ grows to $+\\infty$ as $n \\to +\\infty$, and at a slower rate than $n$ (for instance, $k = \\log(n)$). This assumption is taken from del Barrio et al. (2024) and ensures the consistency of the sequence of weight functions in their Theorem 3.3, which we use (through their ensuing Corollary 3.4) to prove our Theorem 3.2. Note that this is a classical assumption to ensure the universal consistency of $k$NN estimators (e.g., Corollary 19.1 in [R1]).\n\n*(Classification with K>=3)*. Our method can also be applied to binary classification ($K = 2$) but our score (11) would have an intrinsic dimensionality of 1, since the vector of estimated class probabilities belongs to the simplex. Because this setting is not the most relevant for us, we chose to focus on $K \\geq 3$.\n\n*(One-vs-all strategy)*. OT-CP can be applied to one-vs-all classification by simply selecting an appropriate score function (i.e., based on K sigmoids). Our theoretical results remain valid in this setting. This is an interesting research direction that could further broaden the applicability of OT-CP.\n\n*(ELL)*. ELL refers to the ellipsoidal approach with adaptive covariance estimation from Messoudi et al. (2022): see l.292-297. We have made this point clearer in our revised paper.\n\n[R1] Biau, Devroye (2015). Lectures on the nearest neighbor method.", "claims_and_evidence": "Everything seems reasonable to me. \n\nThe most conflicting point I find is the use of the k-nearest neighbor to extend OT-CP to OT-CP +. I would expect that the fix of the standard OT-CP to achieve conditional coverage could be solved in a more fundamental way. That is, using the k-nearest neighbor approach seems more like an approximation than a natural solution to the problem. The dependence on the $k$ hyperparameter", "methods_and_evaluation_criteria": "It wasn’t very clear when OT-CP+ or base OT-CP was being used during the experiments. I would make that more explicit, or even add both in the comparison. \n\nRegarding the evaluation criteria, I think results per class in the classification section are a bit difficult to read. Maybe averaging across classes for the coverage and size of prediction sets is a more informative metric to report for the readers. And the refer to the Appendix the more granular results for class-specific coverage.", "theoretical_claims": "Without diving very deep into the proofs, all claims made sense to me.", "experimental_designs_or_analyses": "The real datasets (lines 272) for the multi-output regression problem are not really explained, just referred to the reference work. I would add more information about which kind of datasets these are. Otherwise, it’s very difficult to tell the kind of regression problem we are facing.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "Most references w.r.t conformal prediction are discussed. Maybe regarding optimal transport more works could have been included, e.g. how to make more efficient the optimal transport problem. I believe this might be pointed out by other reviewers with more background on this field.", "other_strengths_and_weaknesses": "I think the use of optimal transport to construct the conformity scores, both for classification and regression, is quite interesting and novel. This way the conformity score is able to adapt to the data distribution as shown in Figure 2b). \n\nRegarding some weaknesses, I missed a computational comparison between baselines and the OT-CP in some tables or Figures. As far as I know, optimal-transport algorithms can be computationally quite demanding, and I worry about how practical would be the application of this work compared to simpler solutions already proposed in the conformal prediction literature. How does including the k-nearest neighbor step affect the computational complexity? Is it negligible? \n\nRelated to the point above, I missed the comments about the choice of the $k$ parameter in the $k$-nearest neighbor. How is this selected? Given that this is what yields to (asymptotic) conditional coverage, I think this is rather important.", "other_comments_or_suggestions": "- In Figure 2 a), I would change the color of the prediction and MK prediction set, maybe: two different colors, or two shades of blue. It’s a bit difficult to read the dashed line with that shade of blue over the grey points.\n- I find Figure 8 a bit difficult to read. At a first glance, it seems all methods are comparable. Would it make sense to average result for all classes, instead of outputting results per class? Maybe this way it’s easier to see the improvement using OT-CP. If following this suggestion, I would probably add the results for the other benchmark datasets, rather than having them in Appendix B.\n- The use of $k$ for the $k$-nearest neighbor and $K$ for the number of classes in the classification problem can lead to errors when reading. I would maybe change the number of classes to a different variable (e.g. $L$, $M$?).\n- For the results for regression, are we using OT-CP+, or OT-CP? It’s not clear from the caption and legends in the figures (Figure 2,3,4).", "questions_for_authors": "- How computationally complex is it to apply OT-CP? How much time does it take compared to the baselines?\n- Can OT-CP be applied on full conformal prediction?\n- Is the asymptotic conditional coverage determined by the k-nearest neighbor step of the algorithm?\n- In Theorem 3.2, you state that, assuming $k \\to \\inf$ as $n \\to \\inf$, then $k/n \\to 0$. Maybe I’m missing something trivial, but why? We also assume $n$ goes faster to infinity? \n   - I just checked that it’s mentioned in the Appendix A.3 - $k$ is a function on $n$. You mention that you omit this dependency for clarity - could you add some note on that on the main paper/referral to the Appendix? Thanks\n- Why do you assume $K \\gt 3$ in the classification setup?\n- How would OT-CP behave for a classification problem where we assume a One-vs-all strategy, i.e. using binary-to-multiclass framework based on sigmoids rather than softmax? Would results and assumptions still hold? Does this align with your future lines of work (lines 429-434?\n- Figure 4, what is ELL? _ELL_ not really mentioned in the text.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2pNQ7alikt", "reviewer": "Reviewer_bVvM", "summary": "The paper introduces OT-CP, a novel conformal prediction method for multi-output tasks based on optimal transport. The method constructs quantile regions for multivariate conformity scores while ensuring finite-sample coverage and achieving asymptotic conditional coverage. It introduces a new nonconformity score composed of two functions: a multivariate scoring function that preserves information about the error and a mapping function leveraging optimal transport to transform the multivariate score into a real-valued measure. This approach extends univariate conformal prediction by establishing a mapping between the predicted distribution and the uniform distribution on the unit ball. Applications in regression and classification demonstrate improvements in conditional coverage and/or volume.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive evaluation and address their comments with additional discussion and empirical results to illustrate the relevance and computational properties of OT-CP. \n\n*(Region size in regression)*. In Fig. 2, we reported the volumes to demonstrate that OT-CP achieves the desired coverage while producing smaller prediction sets than ELL, RECT. In Fig. 4, we initially did not include volumes since ELL fails to attain the desired conditional coverage, unlike OT-CP+. Based on your suggestion, we now monitor the volumes: https://ibb.co/ymW5Mym6\nOverall, our results suggest that OT-CP(+) achieve coverage while ensuring efficiency, whereas other CP methods either fail to attain coverage or do so by producing unnecessarily large prediction sets. ELL generates smaller regions than OT-CP+, which may explain why it fails to achieve the desired coverage. We will add these results in our paper. \n\n*(OT-CP in Figures 8, 9, and 10)*.  OT-CP provides more balanced coverage across classes, despite not being specifically designed for this task, while non-adaptive scores IP/MS can have low coverage (e.g., label 6 in Fig. 8). This benefit comes with better efficiency/informativeness than APS. This justifies our claim that OT-CP strikes \"a favorable balance across all the considered metrics\". Our revised version includes results averaged over labels: https://ibb.co/1GV3bsdq , https://ibb.co/nqTH1VCq.\n\n*(Average size of the prediction sets and other metrics  with OT-CP+)*. Additional metrics complementing Fig. 4 will be included: https://ibb.co/ymW5Mym6 , https://ibb.co/YTtv36ZM\nVolumes of OT-CP+ are often larger than those from the ellipsoidal approach, but the smallest average set size is not necessarily the best as argued in Angelopoulos and Bates (2023). The motivation for OT-CP+ is precisely to enhance adaptivity with respect to the input.\n\n*([1] could be mentioned)*. This relevant reference was already included in the initial submission (\"Conclusion and Perspectives\"). \n\n*(OT-CP+ and marginal coverage).* We agree that the core guarantee of CP is finite-sample coverage. However, achieving adaptivity (i.e., obtaining prediction intervals with length adapted to the uncertainty relative to the considered test point), which is also a desirable property, is unattainable in finite samples. To introduce adaptivity, a sound strategy is to leverage universal consistent estimators, such as $k$NN. While this improves flexibility, it offers only asymptotic coverage, providing a different trade-off. \n\n*(OT-CP+ vs. [1], [2], and [3])*. A general comparison with [1-3] is an interesting direction for future work, but we explain below why it is beyond our current scope.\n\n*(Other relevant baselines)*. [1,2] were already cited and discussed in our initial submission. We now cite [3] and note that this work proposes a CP method tailored for time series forecasting. Comparing our approach to theirs would thus require adapting OT-CP to handle time series, which is challenging since extensions of MK quantiles to such data have never been studied.\n\n*(Multivariate prediction regions of [1], [2], and [3])*. Thank you for the question, which helps us refine our conclusions: \n- We do not claim OT-CP outperforms all CP methods across every metric, but rather present it as a general methodology, valid in regression settings, improving simple baselines with basic multivariate scores via optimal transport.\n- The suggested references are certainly relevant but appear to be more complementary than concurrent: [1] does not apply to black-box models, unlike OT-CP+ ; [2,3] propose CP strategies for handling complex univariate scores or time series. \n- Combining OT-CP and [1-3] can foster interesting future work. For instance, one can replace the ball-shaped regions with conformalized radii from [3] by our MK quantile regions for greater flexibility. \n\n\n*(Available code)*. We provided the code in the supplementary material.\n\n*(Assumption 3.1).* It implies $p(\\cdot | x)$ is bounded away from $0$ and $+\\infty$ on any compact subset of its convex support, a common assumption for transport quantiles (e.g., del Barrio et al., 2024).\n\n*(\"isn’t there a high likelihood that the ranking induced by this mapping would still assign very similar ranks to these two vectors?\")*. Our mapping does not necessarily lead to similar rankings for these vectors, precisely because we use optimal transport rather than simple normalization. Therefore, MK ranks are $d$-dimensional vectors that integrate the overall geometry of the underlying distributions and capture directional differences (and not just the magnitude).\n\n*(Choice of the reference distribution)*. This is a relevant question, as choosing a reference distribution is an open research problem (even beyond CP) and is largely guided by heuristics. We chose the $L_1$-norm ball because the $L_1$-norm of our score yields IP, a commonly used univariate score in CP for classification: see below eq.(11).", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "The method is evaluated on relevant synthetic and benchmark datasets using appropriate metrics, including marginal coverage, average size, and worst slab coverage. Experiments on synthetic and real data demonstrate that OT-CP outperforms ELL in regression (in terms of conditional coverage) and effectively balances coverage and informativeness in classification compared to IP, MS, and APS. However, the region size is not reported in the regression setting.", "theoretical_claims": "I checked the proof of Theorem 2.4 and the proof of Theorem 3.2, both of which appear to be correct.", "experimental_designs_or_analyses": "I find the empirical results unconvincing. OT-CP does not appear to stand out significantly in Figures 8, 9, and 10. The coverage is not necessarily better; in some cases, the prediction regions are larger, and the informativeness often seems lower compared to the IP and MS methods.  \n\nIn instances where OT-CP appears to perform better, additional analysis is needed. For example, in the *Experiments on real data* section for regression with OT-CP+, it would have been helpful to report the average size of the prediction sets and other metrics evaluating conditional coverage in comparison to ELL.", "relation_to_broader_scientific_literature": "This paper lies at the intersection of optimal transport and conformal prediction, both of which are active research areas.  \n\nRecent notable works in optimal transport include the introduction of quantile regions by Hallin et al. (2021), where vectors are ordered based on optimal transport, and their extension to regression by del Barrio et al. (2024).  \n\nIn conformal prediction, several new methods have been proposed. The paper appropriately references copula- and ellipsoid-based approaches. Additionally, it acknowledges the more flexible method introduced by Feldman et al. (2023), which is particularly relevant to the discussion.", "essential_references_not_discussed": "[1], based on a generative model, is another generative model that could be mentioned.\n\n[1] Wang et al. “Probabilistic Conformal Prediction Using Conditional Random Samples.” AISTATS 2023.", "other_strengths_and_weaknesses": "#### **Strengths:**  \n- Exploring quantile regions for multivariate scores is a natural and worthwhile research direction.  \n- The framework is general and supports any multivariate conformity scores, making it applicable to both regression (e.g., residual-based scores) and classification (e.g., inverse probability scores).  \n- Theoretical guarantees are provided for both marginal and asymptotic conditional coverage.  \n\n#### **Weaknesses:**  \n- The **OT-CP+** method does not satisfy finite-sample marginal coverage, which is a fundamental requirement in conformal prediction.  \n- While computational aspects are briefly discussed, it remains unclear how **OT-CP+** compares computationally to **[1], [2], and [3]**. If I am not mistaken, the method requires computing the optimal transport map for each test input \\( x \\), which has a high computational complexity ($O(n^3)$ or $O(n^2)$ for approximations**), making it computationally demanding.  \n- Several relevant baselines are missing, particularly **[1], [2], and [3]** in regression. Notably, **[2]** can handle multimodal distributions, a capability that has not been discussed in this paper.  \n- In regression, the volume of the quantile regions has not been compared, limiting the assessment of efficiency.  \n- The motivation for using multivariate conformity scores is not entirely clear. Existing methods such as **[1], [2], and [3]** can already generate multivariate prediction regions without requiring multivariate conformity scores.  \n- The lack of publicly available code hinders reproducibility.  \n\n#### **References:**  \n- **[1]** Feldman, Shai et al. *Calibrated Multiple-Output Quantile Regression with Representation Learning.* JMLR (2023).  \n- **[2]** Wang, Zhendong et al. *Probabilistic Conformal Prediction Using Conditional Random Samples.* AISTATS (2023).  \n- **[3]** Sun, Sophia et al. *Copula Conformal Prediction for Multi-Step Time Series Prediction.* ICLR (2024).", "other_comments_or_suggestions": "1) In Assumption 3.1, two quantities are denoted by $ \\lambda $. Where do these quantities originate from?  \n\n2) In Example 2, the authors illustrate that a univariate score may fail to distinguish between the vectors (0.6,0.4,0) and (0,0.4,0.6), whereas a multivariate score can. I agree with this argument; however, later in the method, these vectors are mapped onto the unit ball. Given this transformation, isn’t there a high likelihood that the ranking induced by this mapping would still assign very similar ranks to these two vectors?  \n\n3) Could the choice of the unit ball shape influence the final prediction regions? If so, what is the rationale behind selecting the $ L_1 $-norm ball over other possible choices?", "questions_for_authors": "Please sea above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6ayoXxJRHZ", "reviewer": "Reviewer_Gw2r", "summary": "The paper addresses multivariate conformal prediction and proposes an approach based on multivariate quantiles derived from optimal transport (OT), using a notion of multivariate statistical depth (MK depth) to define ranks. The application to both multivariate regression and classification is discussed, including a section on improved input-conditional coverage (with asymptotic guarantees). The approach is experimentally shown to improve conditional coverage while retaining useful set sizes against a few (simpler) baselines.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and evaluation. We agree that our numerical experiments primarily compare against simple baselines. Our goal, however, is not to claim superiority over all methods but rather to motivate the use of transport-based quantiles in fundamental settings. We acknowledge that this may not have been sufficiently clear and we clarify this below. Thanks to your feedback, we also report additional metrics and results to provide a more comprehensive evaluation.\n\n*(computational costs and runtimes)*. We thank your for this comment which allows us to precise key properties of our methodology. Indeed, OT-CP+ requires solving multiple OT problems, which might be costly, especially for large-scale datasets. However, for the numerical experiments carried out in Fig.4, the computational time remains reasonable. An additional figure supporting this claim is now included: https://ibb.co/YTtv36ZM\n\n*(Comparison to existing related work)*. Our revised version now includes more related works as well as a discussion of limitations. Our main objective is to motivate the possibility of replacing univariate quantiles in the CP recipe by multivariate ones. OTCP should only be seen as a multivariate sorting of scores, which stands in contrast with the design of scores in applied settings. Our experiments suggest benefits of MK quantiles in terms of flexibility, but we do not claim to outperform all existing methods in multivariate regression. Rather, future work might profitably combine OTCP with more advanced multiple scores, different from componentwise residuals. Further numerical comparison is beyond the scope of our proposal and may perturbate the key message.\n\n*(Fig. 2)*. First, we stress that the ellipsoidal approaches do exploit correlations. Second, we intentionally only consider methods that can be interpreted as center-outward quantile regions, just as OT-CP, to ensure fair comparison. The mentioned references [1,2] differ in that they assume positive dependence, more related to a left-to-right ordering than a center-outward one.\n\n*(Fig 3b)*. We reported the empirical coverage averaged across subsets, which is drastically different from strategies that divide calibration examples into fixed groups (e.g., Mondrian CP). We also do not claim to achieve exact input-conditional coverage. We acknowledge the potential confusion and have revised our claim in Sec 3.2.\n\n*(Runtime cost of OT-CP+)*. Indeed, computational times is a limitation of OT-CP+, that is more costly than OT-CP. This cost depends on the parameter k. However, for experiments carried out in our paper, the price to pay seems relatively cheap, as illustrated in the new figure https://ibb.co/hpyCyFN comparing the time between OT-CP and OT-CP+ in the setting of Fig. 4.\n\n*(Type of coverage in Fig 4)*. The considered baseline shares our purpose of improving adaptivity, which is a common desiderata in CP. We agree that it does not guarantee asymptotic conditional coverage. In contrast, OT-CP+ satisfies this property at the price of larger set sizes on average when compared with local ellipsoids https://ibb.co/ymW5Mym6 A potential reason is that having more balanced conditional coverage requires including more points. We added a new figure tracking the marginal coverage of OT-CP+, to highlight that it does not tend to overcover https://ibb.co/1YNdSDny\n\n*(Recent CP methods for conditional coverage)*. As argued previously, our purpose is not to outperform all existing methods in conformal regression. This point has been clarified in the main body to ensure clarity when expressing our purposes.\n\n*(Discussion on related works)*. We discussed related work in \"Introduction\" and other paragraphs (CP methods for multi-output regression, in Sec. 3; CP methods for classification, in Sec. 4). We will integrate all these bibliographical elements into a dedicated subsection of the introduction.\n\n*Other Strengths And Weaknesses:* We appreciate your comments on the writing, structure and illustrative figures. We have added more details on how to solve OT in practice.\n\n*(Motivation for Example 2)* We believe that the results in Fig. 4 demonstrate OT-CP's ability to adapt to label confusions. Therein, classes 0 and 1 tend to be confused by the QDA classifier. In such cases, OT-CP achieves better trade-off between coverage and efficiency/informativeness. When the distribution is made easier (classes 0 and 1 become more distinct for QDA) all methods yield similar efficiency and informativeness: https://ibb.co/mVwMbsF6. This supports that OT-CP can effectively adapt to classification patterns where certain labels are prone to confusion.\n\n*(Solving the OT problem in practice)* We used POT library [R2], which solves OT with the simplex algorithm. This solver is written in C++/Cython and is thus generally faster than pure Python implementations. We have added these details in Appendix.\n[R2] Flamary et al. “POT: Python Optimal Transport.” JMLR 2021", "claims_and_evidence": "The key contribution is the use of OT-based multivariate quantiles which allows the handling of multivariate scores and does not pre-define prediction set shapes (e.g. rectangle = independence, or ellipsoids etc.) while incorporating data-dependent correlations. This results in perhaps less interpretable prediction set shapes but also makes it more data-driven, in line with CP goals. In general, the claims are backed up and convincing, albeit I remain a bit unconvinced of the practical usefulness of the method (see below) since shown experimental results and metrics seem carefully selected to support their method.", "methods_and_evaluation_criteria": "Experiments are provided for both regression and classification, against (only very few) relevant baselines. Results are compared in terms of common CP metrics which include (worst-case) coverage, set size, and fraction of singleton sets. Given the requirements to solve an OT problem for $n$ points (potentially multiple times if doing input-conditional) I would wish to also see more discussion and experimental results on computational costs and runtimes.", "theoretical_claims": "The use of OT-based multivariate quantiles is well-founded based on recent works in that direction, and well explained. The included Theorem 3.2 on asymptotic coverage under some assumptions seems reasonable, albeit I did not carefully check the proof. I appreciate that the regularity assumptions are clearly stated.", "experimental_designs_or_analyses": "I do not argue against the novelty of the proposed approach. My main gripe with this paper is the slightly insufficient experimental comparison and critical analysis of the method against related works, of which there exist many. For starters, the paper is lacking *both* a related works section and a discussion of limitations, namely practicality and computational complexity (it is only briefly mentioned in Remark 2.3).\n\nTo state a few more explicit experimental points:\n- Fig. 2 seems a bit of an unfair comparison in the sense that OT-CP (their method) effectively accounts for data correlations, whereas the considered baselines are corrected with Bonferroni, subsuming an independence assumption across test dimensions. Given this fact, it is actually a bit surprising to see that their approach only fairs a bit better in terms of prediction set size. It would seem more fair to compare to other recent proposals exploiting correlations, e.g. [1,2].\n- In Fig. 3b coverage within each partition / bucket is still marginal, right? And I would assume that as the buckets (I think of this as partition-conditional or mondrian CP) shrink, the conditional coverage would worsen as it approaches sample-conditional? So the claims on some sort of (exact) input-conditional coverage in finite samples do not hold true, e.g. as alluded in the caption of Fig. 3. \n- Relatedly, sec. 3.2. with OT-CP would mean repeatedly solving the OT problem for every input sample based on its k neighbours. I am missing a proper discussion on practicality and runtime costs here. Is this really a useful approach? \n- In Fig. 4 only worst-case coverage is shown, and the results seem to support the fact that OT-CP provides more balanced coverage. This is nice to have, but the considered baseline does not actually promise this form of coverage, right? Could we also see the marginal coverage results and prediction set sizes for the experiment in Fig. 4? Since if OT-CP tends to strongly overcover or provide overly large set sizes, then the worst-slab coverage results are not surprising.\n- Since the empirical benefits (also for regression tasks) seem mainly in the realm of improving empirical conditional coverage (across various partitions), I would expect some comparisons to the multitude of recent CP methods addressing such tasks of conditional coverage, e.g. [4,5,6]. \n- Overall, there is substantially more recent work for multivariate CP that is entirely missed or omitted from this paper. I strongly encourage to have a look at e.g. [3] to see how a more thorough empirical evaluation could look like. I am not suggesting to implement the same breadth of comparisons, but it seems reasonable to consider or at the very least discuss a few more recent proposals. And again, in particular a meaningful discussion and reporting of empirical computational costs and runtimes seems necessary.\n\n[1] Messoudi, Soundouss, Sébastien Destercke, and Sylvain Rousseau. \"Copula-based conformal prediction for multi-target regression.\" Pattern Recognition 120 (2021): 108101.\n\n[2] Timans, Alexander, et al. “Max-Rank: Efficient Multiple Testing for Conformal Prediction.” AISTATS (2025).\n\n[3] Dheur, Victor, et al. \"Multi-Output Conformal Regression: A Unified Comparative Study with New Conformity Scores.\" arXiv preprint arXiv:2501.10533 (2025).\n\n[4] Romano, Yaniv, et al. \"With malice toward none: Assessing uncertainty via equalized coverage.\" Harvard Data Science Review 2.2 (2020): 4.\n\n[5] Sesia, Matteo, and Yaniv Romano. \"Conformal prediction using conditional histograms.\" Advances in Neural Information Processing Systems 34 (2021): 6304-6315.\n\n[6] Gibbs, Isaac, John J. Cherian, and Emmanuel J. Candès. \"Conformal prediction with conditional guarantees.\" Journal of the Royal Statistical Society Series B: Statistical Methodology (2025):", "relation_to_broader_scientific_literature": "There is no proper discussion of related works, so I believe the paper does not appropriately address the recent body of work (both on CP for conditional coverage and multivariate CP)", "essential_references_not_discussed": "I've provided some suggested references above.", "other_strengths_and_weaknesses": "- In Example 2 the motivation to use multivariate scores includes \"This can be more helpful to capture the underlying confusion patterns of the predictor across different label modalities.\". This motivation is never followed up on or shown in any way, so the exact benefit of working with multivariate scores versus collapsing them into a single dimension (but still accounting for correlations) remains a bit lacking\n- How is the OT problem exactly solved in the experiments? It would be helpful to provide details on this (e.g. in the Appendix) to actually permit CP practitioners unfamiliar with OT to leverage this approach, beyond stating the OT problem only.\n- Overall the paper reads quite well and is well structured, and I did not see any obvious typos. I appreciate that the authors provide several illustrative figures (e.g. Fig 1, 2a, 5, 6) that help visualize the concepts and make the intuitively understandable. The OT side of things is kept at a relatively high level which is fine, but could use a more thorough practical description in the appendix.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "Please see my comments and questions especially on the experimental design above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}]

Author rebuttal:

Meta-review: The paper presents an OT based method for CP. Multiple reviewers found this interesting and useful for the CP community at large. One key advantage is that the prediction sets could potentially be non-convex. Simulations illustrate the advantage of the methodology.

All the reviewers opined an acceptance and three suggested clear acceptance. It is requested that the authors to incorporate all the reviewer suggestions appropriately in the final draft.
Decision: Accept (poster)