REVIEW 2 major objections 4 minor 4 cited by
Optimal Transport-based Conformal Prediction
T0 review · 2 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read The paper introduces OT-CP, a conformal prediction method that builds prediction regions for multivariate nonconformity scores via Monge-Kantorovich ranks and quantiles, and proves finite-sample distribution-free coverage under…
desk verdict OT-CP is a genuinely useful combination and the lower-bound coverage proof is sound; the printed two-sided bound has a real but fixable formal defect. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The empirical Monge-Kantorovich rank map $R_{n_1}(s) = \operatorname{argmax}_{U_i}\{\langle U_i, s\rangle - \psi_{n_1}(U_i)\}$, where the $U_i$ are reference rank vectors on the sphere and $\psi_{n_1}$ solves the dual Kantorovich problem, assigns each score a transport-based rank. Ordering scores by $\lVert R_{n_1}(s)\rVert$ turns a level set of these rank norms into the quantile region $\hat{Q}_n(\alpha)$. The load-bearing device is the split: the rank map is built on $D_1$, the threshold quantile is taken on $D_2$, so the rank of the test score is exchangeable with the $D_2$ ranks and the standard quantile lemma applies. A second device, choosing the reference distribution on the positive orthant, realigns the ordering for absolute-error classification scores.
What would settle it
One concrete check: take a discrete score distribution with atoms on the boundary cells of the empirical transport map, choose any deterministic tie-breaking rule, and test whether empirical coverage over many splits stays within $\alpha$ and $\alpha + n_{\text{ties}}/(n_2+1)$; a rule that makes coverage fall below $\alpha$ on such data would refute the 'any distribution' reading of the theorem.
Extended reading notes
Core claim
The paper's central claim is that conformal prediction can be extended to multivariate nonconformity scores without losing distribution-free finite-sample coverage, by replacing scalar quantiles with Monge-Kantorovich (MK) ranks and quantiles. The prediction region is the set of scores whose MK rank norm falls below the $\lceil (n_2+1)\alpha\rceil$-th order statistic of calibration ranks computed on a separate split, and Theorem 2.4 bounds its coverage between $\alpha$ and $\alpha + n_{\text{ties}}/(n_2+1)$ for exchangeable data. Because the MK rank map is built from an optimal transport coupling between the score distribution and a reference distribution on the sphere, the resulting regions inherit the shape of the empirical score distribution and can be non-convex. The paper also shows that choosing a reference distribution on the positive orthant gives a left-to-right order suited to classification scores, and that a k-nearest-neighbor conditional version of the rank map yields asymptotically valid conditional coverage.
Load-bearing premise
The rank map's argmax defines a single rank for every score, but for scores lying on cell boundaries in the transport geometry, or for discrete score distributions, this argmax can be multi-valued; the paper specifies no tie-breaking rule, yet the coverage guarantee and the prediction region require one.
Editorial extensions
If this is right
- Prediction regions for multi-output regression can be non-convex and mirror the residual geometry while still satisfying the finite-sample coverage bound.
- For multiclass classification, using the full softmax score vector gives label-conditional coverage comparable to adaptive scores while retaining the efficiency of simpler scores.
- The adaptive OT-CP+ variant with k-nearest-neighbor conditional rank maps achieves asymptotic conditional coverage under mild density assumptions.
- When the score is univariate, the optimal transport problem reduces to sorting and OT-CP recovers standard conformal prediction at $O(n \log n)$ cost.
- With a specified tie-breaking rule, the upper coverage gap becomes $1/(n_2+1)$, matching the usual conformal guarantee up to discretization.
Reading between the lines
- The coverage theorem is silent about how to resolve ties when the argmax in the rank map is set-valued, so the 'any distribution' claim implicitly depends on a tie-breaking convention; a careful empirical study on discrete or boundary-atom score distributions would show whether coverage stays within the stated bounds for each convention.
- The splitting strategy makes the transport rank of a test point distribution-free, so it could be reused for other transport-based ranks or quantile maps beyond the Monge-Kantorovich construction.
- A natural extension is to align the reference distribution with the geometry of the task, for instance using the positive-orthant reference for multi-label or multi-hot scores, which the paper suggests as a direction.
- Replacing the exact OT solver with entropic approximations could cut the $O(n^3)$ cost and make OT-CP practical for large calibration sets, at the price of a bias that the current theory does not cover.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes OT-CP, a split-conformal prediction method that handles multivariate non-conformity scores by using empirical Monge-Kantorovich (MK) vector ranks and quantiles built on optimal transport. The procedure constructs flexible, potentially non-convex prediction regions, and the authors claim a finite-sample distribution-free coverage guarantee in Theorem 2.4. They also introduce an adaptive variant, OT-CP+, for multi-output regression with an asymptotic conditional coverage guarantee, and an adaptation to multiclass classification. The numerical experiments compare the proposed methods against ellipsoidal, rectangular, and scalar-score baselines on simulated and real data.
Significance. If the coverage guarantee is stated and proved correctly, the paper makes a valuable contribution: it provides a principled way to use multivariate scores in conformal prediction without imposing convex or predefined set shapes, while retaining a finite-sample, distribution-free validity statement. The explicit split of the calibration set to handle the dependence introduced by the estimated transport rank map is a sensible and nontrivial device. The OT-CP+ extension toward conditional coverage and the classification experiments with worst-slice and label-wise coverage metrics give the paper useful practical scope. The theoretical results are not machine-checked and no code is released, but the proofs are sufficiently detailed to allow verification of the main mechanism.
major comments (2)
- [Theorem 2.4, Eq. (6), and Appendix B.1] The two-sided bound is not a well-formed scalar probability inequality as stated. The quantity nties is defined as the maximum number of ties in the realized sample {∥Rn1(s(X_i,Y_i))∥ : (X_i,Y_i) ∈ D2} ∪ {∥Rn1(Stest)∥}, so it is a random variable depending on the data, whereas P(Ytest ∈ Cα(Xtest)) is a fixed real number. In the proof of Lemma B.1, the step bounding the count of entries ≤ U(k) by k−1+nties is only valid for a realized tie count; after taking expectations the upper bound must involve E[nties] (or an almost-sure upper bound), not nties itself. The same issue transfers to Eq. (6). The lower bound α is unaffected, but the claimed sharp upper bound needs to be restated either conditionally on the realized tie pattern or as a marginal bound with E[nties]. This is a load-bearing correction to the central theorem.
- [Eq. (3) and Section 2.3, step 2] The empirical MK rank map is defined as an argmax over the finite reference set {U_i}. For scores lying on cell boundaries of the piecewise-linear convex potential, or for discrete score distributions, this argmax can be set-valued, and the paper specifies no tie-breaking rule. Since the prediction region in Eq. (5) and the coverage event in Theorem 2.4 are only defined for a single-valued rank map, the claim that the guarantee holds 'for any score' silently presupposes a deterministic selection rule. A concrete rule (e.g., lexicographic or smallest-index selection) should be stated, and the proof adjusted accordingly; the lower-bound argument is robust to this choice, but the theorem is not fully well-defined without it.
minor comments (4)
- [Section 2.4, paragraph after Theorem 2.4] The sentence 'a tie-breaking rule can be applied if ties occur, as usually done in CP, to enforce nties = 1' is imprecise: tie-breaking in the ordering of equal-norm ranks does not change the multiplicity of identical values in the realized sample, so it cannot by itself force nties = 1 for all score distributions.
- [Definition 2.1 and Section 2.3, step 2] The notation Rn1 used in step 2 is not formally introduced; Definition 2.1 defines Rn for a sample of size n. Please state explicitly that Rn1 denotes the empirical MK rank map computed from D1, with reference vectors {U_i}_{i=1}^{n1}.
- [Section 4, Figure 5] The captions of Figure 5 and the surrounding text use 'center-outward' versus 'left-to-right' ordering before the positive reference simplex is defined; a one-sentence precise definition of the positive reference rank vectors in the main text would improve readability.
- [Appendix B.3, proof of Lemma B.2] The uniform convergence of the empirical quantile function is invoked via Bogoya et al. (2016); please state the exact conditions (boundedness and continuity of the limiting quantile) that justify this step, since the argument otherwise relies on an implicit regularity assumption.
Circularity Check
No significant circularity: the coverage guarantee follows from exchangeability and the standard quantile lemma, and no fitted parameter is renamed as a prediction.
full rationale
The paper's central claim, Theorem 2.4, is a split-conformal coverage bound. The MK rank map is computed on D1, then the scalar values ∥Rn1(·)∥ for D2 and the test point are exchangeable by a standard external result (Kuchibhotla 2020, Proposition 3), and the quantile lemma (Lemma B.1) yields the probability bounds. The MK rank construction ensures that the calibration ranks are a permutation of the reference vectors, which is a mathematical property rather than a fitted parameter; the threshold ρ is an order statistic of D2, not optimized to match the test outcome. The asymptotic conditional coverage result (Theorem 3.2) imports consistency of conditional MK quantile regression from del Barrio et al. (2024), an external source with no author overlap with the present paper. No parameter is fitted to the calibration data and then renamed as a prediction, and no load-bearing self-citation appears. The data-dependence of nties in the upper bound of Theorem 2.4 is a formal correctness concern about the statement of the bound, not a circularity: the derivation does not assume the conclusion it aims to prove. The derivation is therefore self-contained with respect to its stated inputs.
Assumptions & free parameters
free parameters (1)
- k (number of neighbors in OT-CP+) =
n/10 or sqrt(n) depending on dataset (Appendix D.2)
assumptions (5)
- domain assumption Exchangeability of calibration and test data
- domain assumption Score function is fixed and independent of calibration data
- ad hoc to paper The MK rank map argmax in Eq. (3) has a well-defined single-valued selection
- domain assumption Consistency of conditional MK quantile regression (del Barrio et al., 2024, Corollary 3.4)
- standard math Exchangeability of ranks under a fixed rank map (Kuchibhotla, 2020, Proposition 3)
Cite this review
Pith. "Pith review of Optimal Transport-based Conformal Prediction." pith.science (2026). https://pith.science/paper/PNGZJHKK
@misc{pith2026250118991,
author = {Pith},
title = {Pith review of: Optimal Transport-based Conformal Prediction},
year = {2026},
howpublished = {\url{https://pith.science/paper/PNGZJHKK}},
note = {Machine review of arXiv:2501.18991}
}
read the original abstract
Conformal Prediction (CP) is a principled framework for quantifying uncertainty in blackbox 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.
Figures
Figures from the paper (13 more)
Forward citations
Cited by 4 Pith papers
-
Manifold Constrained Conformal Prediction for Spatial Events
Manifold-constrained conformal prediction with sliced Wasserstein scores yields near-nominal coverage and lower energy/manifold distances for spatial event clouds than HDR or generative baselines.
-
Denoised Conformal Alignment for Reliable Selection of Conditional Average Treatment Effect Predictions
Variance-subtracted doubly robust proxy errors plus conformal p-values and Benjamini–Hochberg yield asymptotic FDR control for selecting reliable CATE predictions under heteroskedasticity.
-
Multivariate Conformal Prediction using Optimal Transport
Using the norm of an optimal transport map as a conformity score gives distribution-free, finite-sample coverage for multivariate conformal prediction sets.
-
Conformal Graph Prediction with Z-Gromov-Wasserstein Distances
Conformal prediction on graph outputs is built from Z-Gromov-Wasserstein nonconformity scores, with a one-sided CQR variant (SCQR) for adaptive set sizes.
Reference graph
Works this paper leans on
-
[1]
Angelopoulos, A. N. and Bates, S. (2023). Conformal prediction: A gentle introduction. Foundations and Trends® in Machine Learning , 16(4):494--591
work page 2023
-
[2]
N., Bates, S., Jordan, M., and Malik, J
Angelopoulos, A. N., Bates, S., Jordan, M., and Malik, J. (2021). Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations
work page 2021
-
[3]
Cauchois, M., Gupta, S., and Duchi, J. C. (2021). Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. Journal of machine learning research , 22(81):1--42
work page 2021
-
[4]
Chernozhukov, V., Galichon, A., Hallin, M., and Henry, M. (2017). Monge--Kantorovich depth, quantiles, ranks and signs . The Annals of Statistics , 45(1):223 -- 256
work page 2017
-
[5]
Chernozhukov, V., W \"u thrich, K., and Zhu, Y. (2021). Distributional conformal prediction. Proceedings of the National Academy of Sciences , 118(48):e2107794118
2021
-
[6]
Deb, N. and Sen, B. (2023). Multivariate rank-based distribution-free nonparametric testing using measure transportation. Journal of the American Statistical Association , 118(541):192--207
work page 2023
-
[7]
del Barrio, E., Sanz, A. G., and Hallin, M. (2024). Nonparametric multiple-output center-outward quantile regression. Journal of the American Statistical Association , pages 1--15
work page 2024
-
[8]
Feldman, S., Bates, S., and Romano, Y. (2023). Calibrated multiple-output quantile regression with representation learning. Journal of Machine Learning Research , 24(24):1--48
work page 2023
Show all 31 references
-
[9]
J., Ramdas, A., and Tibshirani, R
Foygel Barber, R., Candès, E. J., Ramdas, A., and Tibshirani, R. J. (2020). The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA , 10(2):455--482
2020
-
[10]
and Sen, B
Ghosal, P. and Sen, B. (2022). Multivariate ranks and quantiles using optimal transport: Consistency, rates, and nonparametric testing. The Annals of Statistics , 50(2):1012--1037
2022
-
[11]
Hallin, M., del Barrio, E., Cuesta-Albertos, J., and Matr \'a n, C. (2021). Distribution and quantile functions, ranks and signs in dimension d: A measure transportation approach . The Annals of Statistics , 49(2):1139 -- 1165
2021
-
[12]
Henderson, I., Mazoyer, A., and Gamboa, F. (2024). Adaptive inference with random ellipsoids through conformal conditional linear expectation. arXiv preprint arXiv:2409.18508
2024 arXiv
-
[13]
o fstr \
Johansson, U., Linusson, H., L \"o fstr \"o m, T., and Bostr \"o m, H. (2017). Model-agnostic nonconformity functions for conformal classification. In 2017 International Joint Conference on Neural Networks (IJCNN) , pages 2072--2079. IEEE
2017
-
[14]
and Cox, B
Johnstone, C. and Cox, B. (2021). Conformal uncertainty sets for robust optimization. In Conformal and Probabilistic Prediction and Applications , pages 72--90. PMLR
2021
-
[15]
and Papadopoulos, H
Katsios, K. and Papadopoulos, H. (2024). Multi-label conformal prediction with a mahalanobis distance nonconformity measure. Proceedings of Machine Learning Research , 230:1--14
2024
-
[16]
Kuchibhotla, A. K. (2020). Exchangeability, conformal prediction, and rank tests. arXiv preprint arXiv:2005.06095
2020 arXiv
-
[17]
J., and Wasserman, L
Lei, J., G’Sell, M., Rinaldo, A., Tibshirani, R. J., and Wasserman, L. (2018). Distribution-free predictive inference for regression. Journal of the American Statistical Association , 113(523):1094--1111
2018
-
[18]
Melki, P., Bombrun, L., Diallo, B., Dias, J., and Da Costa, J.-P. (2024). The penalized inverse probability measure for conformal classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition , pages 3512--3521
2024
-
[19]
Messoudi, S., Destercke, S., and Rousseau, S. (2020). Conformal multi-target regression using neural networks. In Conformal and Probabilistic Prediction and Applications , pages 65--83. PMLR
2020
-
[20]
Messoudi, S., Destercke, S., and Rousseau, S. (2021). Copula-based conformal prediction for multi-target regression. Pattern Recognition , 120:108101
2021
-
[21]
Messoudi, S., Destercke, S., and Rousseau, S. (2022). Ellipsoidal conformal inference for multi-target regression. In Conformal and Probabilistic Prediction with Applications , pages 294--306. PMLR
2022
-
[22]
and Smirnov, E
Neeven, J. and Smirnov, E. (2018). Conformal stacked weather forecasting. In Conformal and Probabilistic Prediction and Applications , pages 220--233. PMLR
2018
-
[23]
Peyr \'e , G., Cuturi, M., et al. (2019). Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning , 11(5-6):355--607
2019
-
[24]
Plassier, V., Fishkov, A., Guizani, M., Panov, M., and Moulines, E. (2024). Probabilistic conformal prediction with approximate conditional validity. arXiv preprint arXiv:2407.01794
2024 arXiv
-
[25]
Romano, Y., Patterson, E., and Candes, E. (2019). Conformalized quantile regression. Advances in neural information processing systems , 32
2019
-
[26]
Romano, Y., Sesia, M., and Candes, E. (2020). Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems , 33:3581--3591
2020
-
[27]
and Romano, Y
Sesia, M. and Romano, Y. (2021). Conformal prediction using conditional histograms. Advances in Neural Information Processing Systems , 34:6304--6315
2021
-
[28]
Tsoumakas, G., Spyromitros-Xioufis, E., Vilcek, J., and Vlahavas, I. (2011). Mulan: A java library for multi-label learning. The Journal of Machine Learning Research , 12:2411--2414
2011
-
[29]
Tumu, R., Cleaveland, M., Mangharam, R., Pappas, G., and Lindemann, L. (2024). Multi-modal conformal prediction regions by optimizing convex shape templates. In 6th Annual Learning for Dynamics & Control Conference , pages 1343--1356. PMLR
2024
-
[30]
Vovk, V., Gammerman, A., and Shafer, G. (2005). Algorithmic learning in a random world , volume 29. Springer
2005
-
[31]
Wang, Z., Gao, R., Yin, M., Zhou, M., and Blei, D. (2023). Probabilistic conformal prediction using conditional random samples. In Ruiz, F., Dy, J., and van de Meent, J.-W., editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics , v...
2023
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.