Characterizing Out-of-Distribution Error via Optimal Transport
Authors: Yuzhe Lu
Yilong Qin
Runtian Zhai
Andrew Shen
Ketong Chen
Zhenlin Wang
Soheil Kolouri
Simon Stepputtis
Joseph Campbell
Katia P. Sycara
Venue: NeurIPS 2023 poster (2023)
Keywords: Distribution Shift
OOD Error Prediction
Optimal Transport
Deep Learning
TL;DR: We propose COT and COTT, which provably improve over existing methods of predicting OOD performance by leveraging pseudo-label shift to account for miscalibration. Our methods significantly outperform existing methods on a variety of benchmarks.

Abstract: Out-of-distribution (OOD) data poses serious challenges in deployed machine learning models,
so methods of predicting a model's performance on OOD data without labels are important for machine learning safety.
While a number of methods have been proposed by prior work, they often underestimate the actual error, sometimes by a large margin, which greatly impacts their applicability to real tasks. In this work, we identify *pseudo-label shift*, or the difference between the predicted and true OOD label distributions, as a key indicator of this underestimation. Based on this observation, we introduce a novel method for estimating model performance by leveraging optimal transport theory, Confidence Optimal Transport (COT), and show that it provably provides more robust error estimates in the presence of pseudo-label shift. Additionally, we introduce an empirically-motivated variant of COT, Confidence Optimal Transport with Thresholding (COTT), which applies thresholding to the individual transport costs and further improves the accuracy of COT's error estimates. We evaluate COT and COTT on a variety of standard benchmarks that induce various types of distribution shift -- synthetic, novel subpopulation, and natural -- and show that our approaches significantly outperform existing state-of-the-art methods with up to 3x lower prediction errors.

Characterizing Out-of-Distribution Error via Optimal Transport
Yuzhe Lu Yilong Qin"!, Runtian Zhai', Andrew Shen', Ketong Chen'
Zhenlin Wang', Soheil Kolouri", Simon Stepputtis', Joseph Campbell', Katia Sycara
CCarnegie Mellon University Vaandrbbllt University
lyuzhelu, yilongq, rzhai, andreus, ketonge, zhenlinw)@ca. soheil wtw.::kooorrrvedeeebiiia edu, (sstepput, jcampbell, sycara)ecs. cmu. edu
Abstract
ditoo--distributio (OOD) data poses serious challenges in deployed machine learning models, so methods of predicting a model's performance on OOD data without labels are important for machine learning safety. While number of meth- ods have been proposed by prior work, they often underestimate the actual error, sometimes by a large margin, which greatly impacts their applicability to real tasks. In this work, we identify pseudo-label shift, or the difference hetween the predicted and true OOD label distributions, as key indicator of this under-estimation. Based on this observation, we introduce a novel method for estimating model performance by leveraging optimal transport theory, Confidence Optimal Transport (COT), and show that it provably provides more robust error estimates in the presence pseudo label shift. Additionally, we introduce COT, Confidence Optimal Transport with Thresholding (COTT), which applies thresholding the individual transport costs and further improves the accuracy COT's error estimates. We evaluate COT and COTT on variety of standard benchmarks that induce various types of distribution shift synthetic, novel sub- population, and natural - and show that our approaches significantly outperform existing state-of-the-ar methods with up to 3x lower prediction errors. Our code can be found at http://gihuub.com/llyuuua Mtt//heeeI///OTTTTT 11/COT
cattrricalll-moivattttt variant of
Introduction
Machine Learning methods are largely based on the assumption that test samples are drawn from the same distribution training samples, providing basis for generalization. However, this i.idd. assumption is often violated in real-world applications where test samples are found to be out-of- distribution (OOD) sampled from different distribution than during training. This may result common practice for set of labeled data from the current target data distribution, and update the model if necessary. When labeled data is not available, however, one needs predict the model's performance on the target distribution with unlabeled data, a task known as OOD performance prediction.
in a significant negative impact on model performance [15] 34
25
38
alleviating this issue is regularly gauge the model's performance
Performance prediction unlabeled data has previously been shown be impossible without imposing additional constraints over the unknown target distribution [ 26), due to the fact that target samples may take any label. Thus, the feasibility of this task is dependent we make regarding the shift between the train and target distributions. Prior works often make the assumption that the conditional density P(y[æ) remains fixed in the presence of covariate shift [37]
what assumptions
These authors contributed equally to this work.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

However, this tells us little when r falls outside the support of the train distribution. Despite the theoretical difficulty, prior works have proposed a number of heuristic methods to estimate the performance of a model based on unlabeled target samples. For instance, Average Confidence (AC) 20 [6] estimates error based on the average maximum softmax score for target samples, assuming the model has been calibrated for the train distribution. This method was further improved with the addition of a learned threshold [[3]. for which the error is predicted as the fraction of samples with confidence falling below it. Other approaches estimate model performance based on disagreement score computed between the predictions of two models trained over the same dataset 22 B]] Some works have found that applying transformation over target samples and estimating the effect of the transformation leads to a reliable prediction of model performance in vision tasks ( [0]. However, many of these prior methods have been shown
underestimate
the model's s error when it is miscalibrated in the target distribution [33 22]; that is, the predicted softmax scores differ from the true class likelihoods. We empirically observe that this miscalibration is strongly positively correlated with pseudo- mreudo-label.ao shift, which is the difference between the predicted target label distribution Pr(ū) and the true label distribution Pr(y). Thus, we treat pseudo-label shift as key indicator of error underestimation.
In this work, we propose an approach which provides robust error estimates in the presence of pseudo- label shift. Our approach, Confidence Optimal Transport (COT), leverages the optimal transport framework to predict the error of a model as the Wasserstein distance between the predicted target class probabilities and the true source label distribution. We theoretically derive lower bounds for COT's predicted error. This results in more provably conservative eπror prediction than AC, which is crucial for safety in many real-world machine learning applications. In addition, we introduce variant of COT, Confidence Optimal Transport with Thresholding (COTT), which introduces learned threshold over the optimal transportation costs in line with prior work [33] and empirically improves upon COT's performance. In this work, we mainly target covariate shifts and compare our proposed methods to existing state-of-the-ar approaches in extensive empirical experiments over eleven datasets exhibiting distribution shift from both vision and language domains. These distribution shifts include: visual corruptions (e.g.. blurred image data), novel subpopulation shifts (e.g., novel appearances of a category). and natural shifts in the wild (e.g.. different stain colors for pathology images). all of which are frequently experienced in the real world. We find that COT and COTT consistently avoid the significant error underestimations suffered by previous methods. In particular, COTT achieves significantly lower prediction errors than existing methods for most models and datasets (up to 3x better), establishing new the results.
2 Preliminaries and Motivation
In this section, we introduce the problem setup of OOD error prediction and show how a popular baseline, Average Confidence (AC), can be understood as the Wasserstein Distance (WD) between a reference label distribution and the softmax output distribution from an Optimal Transport (OT) perspective. We then demonstrate why the reference label distribution AC uses is problematic by explaining pseudo-label shift and its correlation with miscalibration. After establishing the relation and utility of OT to OOD error prediction, we formally introduce our proposed methods in Sec. 3
2.1 OOD Performance Prediction
In this work, we address the OOD problem in the domain of classification tasks. Let X' C Idd be the input space of size d, and y = {1. ........ ,,k] be the label space, where à the number of classes. Let the source distribution over X' x y be Ps(x, v) and the target distribution be Pr v). A classifier f: X + A 1 maps an input to a confidence vector (i.e. the output of the softmax layer), where + ---1,(1=,,> ... 24) 21 +2 = 1, v, 2 0} is the k-dimensional unit simplex. Let the training
samples be [ 3 Brrin) Ps v). and the validation samples be (((()) (()))) Ps(a, y). The validation set is used in some previous methods and will also be used in COT and COTT to perform calibration [17].
The OOD performance prediction problem is formally stated as follows: Given an unlabeled test (8) set {-7' } (x) and a classifier ff trained over the training samples, predict the accuracy of
2

---

1ff If over the test set = = Equivalently, we can also predict the error e = 1- a with an estimate
arg max, [y(xT') where yr
(1) is the ground truth label.
In this work, we are further investigating the distribution of confidence vectors. While a confidence vector f(x) itself is distribution of labels in the k-dimensional simplex A the distribution of confidence vectors f (()) is a distribution of distributions, where č A k f P()) is defined
to be the pushforward of a covariate distribution P(x) using J: Jg P(t) = P(f- (c)) Consider the following example: Suppose
É (A, B, C) and ff maps A, B to [0.5, 0.5] T and to [0.7, 0.3] Then, J P(e) will assign 3 mass to [0.5, 0.5] and 3 mass to [0.7, 0.3] To facilitate easy comparison between confidence vectors and labels, we denote T E {0, 1 n A to be the one-hot representation of E y. where the only non-zero element in y is the y-th element, i.e. y/ 1yy .). We denote the distribution of one-hot labels as P For a covariate distribution P(x), we will refer to the distribution of predicted labels from classifier f as the pseudo-label distribution (peeud(()). We reuse the notation denote the probability mass of j also as which is given by the mass of the inputs that give this prediction, i.e. Ppscddo (ū) p( E X' arg max, fz(x) = y}).
have a uniform covariate distribution P(x)
2.2 Wasserstein Distance and Optimal Transport
In recent years, optimal transport theory has found numerous applications in the field of machine learning 2 27 29]. Optimal transport aims to move one distribution of mass to another as efficiently possible under a given cost function. In the Kantorovich formulation of optimal transport, we are given two distributions p(z) over and vly) over y and a cost function c(2, y) that tells us the cost of transporting from location to location y. Here, aim to find transport plan π (ar, y) that minimizes the total transport cost. The transport plan is a joint distribution with marginal (+,37) = pa-) and (Xx,)) .) = v(.). The conditional distribution x(x.a) of the transport plan informs us how much mass is moved from x to y. Let I((,,)) v/) be the set of all transport plans. More formally, the Wasserstein Distance is defined as:
ju(ar)
J clz, vd *Ell(ue)) xxx
inf
The Wasserstein distance satisfies the definition of metric (non negaativti,, symmetry, and sub- additivity), inducing metric space over a space of probability distributions. Unlike other metries, such as total variation, the Wasserstein metric induces weaker topology and provides robust framework for comparing probability distributions that respect the underlying space geometry 22.
For discrete distributions μ4, v such as the empirical distributions, the Wasserstein distance simplifies to the following linear programming problem:
(w,,v) v)
(P. C) min Pell(u.)
min
Σ Pell(a.))
where C, P E Rmxx are the cost matrix and the plan matrix respectively and Cty is the transport cost from sample to sample j. When n = m. the optimal transport problem reduces to the optimal matching problem (Proposition 2.1 in Peyré et al. (32), i.c. the optimal transport plan P' arg milpee(aa.)) (P, C) is a permutation matrix. Not only does this constraint enable efficient algorithms like the Hungarian algorithm, but it will also help draw the connection between pseudo- label shift and target error that is central to our Confidence Optimal Transport method.
2.3 Average Confidence as Wasserstein Distance
We Average Confidence, popular OOD performance prediction method, as the starting point of our analysis. Average Confidence with Max Confidence (AC-MC) estimates the target accuracy by taking the empirical mean of maximum confidence of the classifier over all target samples ( Pr(x), i.e. 1 E max, (2))). Its corresponding target error estimate is therefore n AAc - 1- max; (0) By definition, |e éxcl measures the miscalibration of the model, i.e. how far away the model's 's confidence is from its actual accuracy. In the following proposition, we connect the AC-MC estimates with distances in the Wasserstein Metric Space:
3

---

P precioo !
pecudo (g)
I Pyter
F (r(()
poeuddo (3)
6
Pr(
60
80
Pr(y)
(T(
Figure 1: The AC-COT Triangle in the Wasserstein Space (P(R*), Wso). where dp (Dirac delta over the zero vector) represents the origin. Red line: AC-MC error estimate. Blue line: (our) COT error estimate (assuming (1) x Ps(y)) Green line: Pseudo-label shift. Left: AC-MC predicts the target error as the distance between the distribution of confidence vectors and its projection on the unit sphere, the smallest among all label distributions. This makes AC-MC prone to underestimating
the target error. Middle: Mild pseudo-label shift. Right: Severe pseudo-label shift.
Proposition (Cac-Woo Equivalence). Let (P(R*), Wo ) be the metric space of all distributions over IR& where W is the Wasserstein distance with c(t, y) || yllxx- Then, the estimated error of AC is given by Êsc W (f P(e), Procudo
We defer all proof's to the supplementary material. Here, we appeal to pictorial intuition in Figure D where do (Dirac delta over the zero vector) represents the origin. All one-hot label distributions, including (3) and P Prseddo (ū), are represented as points on the (dashed) unit sphere around ög- distribution of confidence vectors f P(C) is simply a point within the unit ball around 8g. The AC-MC accuracy estimate measures how far the point is to the origin og. Additionally, we can project the point to the unit sphere, resulting in the projection point P peeutoo()) (y)) which is the pseudo-label distribution. The AC-MC error estimate measures the length of the projection.
Corollary 1 ((pseudo (V7) is closest to F P()). Let P') P(10, 11th n be one-hot label distribution. Then Wf ('( 2 Wo P(C), P (T)).
This suggests that AC-MC, among all possible reference one-hot label distributions, selects the closest one and reports the distance be the predicted error. Thus, we can that AC-MC is a very optimistic prediction strategy, so it is not surprising that AC-MC is widely reported to be over-estimating the performance real tasks [3 16 22
2.4 Pseudo-Label Shift and its Correlation with Miscalibration
The pseudo-label shift is defined as 5 (PPeaato (7), Pr(7)), i.e. the distance from the pseudo label distribution P Ppeudaa (1)) to the ground truth target label distribution Pr(j), which is also the length of the green line segment in Figure 1. An important property is Wx (PPseadd (5), Pr S e 1, i.e. the pseudo-label shift is a lower bound of the true target error of the model (as true target error be interpreted as the average transport cost of a suboptimal matching). We can clearly see how large pseudo-labe shift could potentially destroy the prediction of AC-MC from Figure T (right), where the red line segment is much shorter than the green one which should be a lower bound of the true error. This lower bound, however, can be loose when it is small, as shown in Figure (middle).
Most existing prediction methods heavily rely on the model being well-calibrated, as pointed out by Jiang et al. (22), Garg et al. [13, yet the underlying difficulty is a lack of precise understanding of when and by how much neural networks become miscalibrated. This evident in the large-scale empirical study conducted in 30 showing that the variance of the error becomes much larger among the different types of shift studied, despite some positive correlation between the expected calibration error and the strength of the distribution shift. In this section, we empirically show that there is a strong positive correlation between the pseudo-label shift and JE - EAcl. which we define as the model's 'ss miscalibration. Because of this correlation, we consider pseudo-label shift the key signal to why existing methods have undesirable performance.
We evaluate the pseudo label shift and the prediction error of AC-MC |c Excl on CIFAR-10 and CIFAR-10M under different distribution shifts, and plot the results Figure 2 (left). The plots demonstrate a strong positive correlation between these two quantities, which not only means that the performance of AC-MC worsens as the pseudo-label shift gets larger, but also implies that the performance of existing methods [16] 13 22 that depend on model calibration will drop.

---

CIFAR-10
CIFAR-100
comuption
shol
CIFAR-10
CIFAR-100
anow
0.4
contrnet
spaller
defocus bir
speckle mobe
ebatic Fransfomm
Eror of dOE
1000
severity
02
frost
gaussian bur
0.2
gaustaan noien
0.1
joeg comppession
impulse rois
4
6
0.1
motion
0.506
0. 0.8
0.00.1 0.2 0.3 04 0.506
0.0
0.2 04
0.6
0.6
Psoudo Label Shin
caturate
Pcoudo Label Shift
Poeudo Label Shim
Figure 2: Left: Absolute difference between the model's Average Confidence and its true error under different levels of pseudo-label shift. This difference measures the degree of miscalibration. We see strong correlation between the miscalibration and pseudo-label shift on the common corruption benchmarks (CIFAR-IO-C, CIFAR- -00-C).. Right: Absolute difference between GDE error estimate and true error under different levels of pseudo-labed shift. The strong correlation is also observed.
CIFAR-10
CIFAR-100
comupttin
nolee
CIFAR-10
CIFAR-100
contrast
spattor
0.4
Bror norercot
defocus bur
elstie FFenafomm
speckle, noiso
zoom
Errer COTt
0.3
severity
0.2
froel
gaussion blu
0.2
0.11
jpeg compresaion
gauseian molee
impulse,
5
4
0.1
0.0
motion, bur
0.0.11 0.2 03 D4 0,506
0.0
0.2 3.4
0.6
0.0
0.00.1 0.2
Psoudo Label Shift
Paeudo Label Bhift
saturale
Psoudo
Peeudo
Figure 3: We further compare the sensitivity of COT and COTT's estimation error to the degree of pseudo-label shift. Compared to Figure 2 we can clearly that the correlation between the prediction error and pseudo-label shift weakens significantly. Moreover, COTT is even more robust to pseudo-label shift compared to COT.
Our exploration of miscalibration and pseudo-label shift reveals a previously unexplored tradeoff:
When the pseudo-lahel shift is small, prior work has given us some reassurance to trust the calibration of neural networks, which motivated methods such as AC (20] and ATC [3] More critically, as miscalibration worsens, the pseudo-label shift becomes a tighter low bound of the error and thus a more trustworthy estimate the error.
Motivated by this observation, we leverage the information of the pseudo-label shift to improve the performance of confidence-baie based prediction methods for miscalibrated models. The problem, as mentioned carlier, is that without any information about the target label distribution, it is theoretically impossible to estimate the pseudo-label shift when the test set contains data from unseen domains. Thus, the only option is to make assumptions on the target label distribution.
In our proposed method, make natural assumption: the target label distribution is close the source label distribution. This assumption aligns with most natural shifts that can be observed in real-world datasets. This extra assumption allows much better than existing methods in most cases (See Table [ especially when the pseudo-label shift is large. Given this assumption, 3 pseudo-label shift. We can see that equipped with the extra information, COT is able to maintain low prediction error even under very large pseudo-label shift, and the correlation between COT performance and the pscudo-label shift is weak. Since the pseudo-label shift is strongly correlated with miscalibration, this implies that COT is much more robust to miscalibration than existing miscalibration--ennn sensitive prediction methods.
develop COT and COTT, which perform
shows the prediction error of COT versus the
3 Methods
In this section, we formally introduce our proposed method - Confidence Optimal Transport - and propose an additional variation, COTT, that utilizes a threshold over the optimal transportation costs between two distributions, instead of taking simple average.
5

---

3.1 Confidence Optimal Transport
Let (T( denote the empirical source label distribution. The predicted error of COT, which is the length of the blue line segment (assuming (V( Ps(T)) in Figure | is given by
écor = (S Pr (r) Ps(T)).
By Corollary | écor 2 ÉAC. which means that COT provably predicts larger error than AC-MC, which empirically tends to produce more accurate predictions as we find overestimation of the eπror far less common than underestimation. As mentioned earlier, in the case where the pseudo-label shift is large, such as in Figure (Right), AC-MC can have arbitrarily large prediction error, while COT always has the following guarantee:
Proposition 2 (Calibration independent lower bound of COT). Under the assumption that Pr(y) (V) we always have čcor 2 0.5W (P preado (T), (r1).
Thus, we can see that COT is by nature different from existing methods because it a miscalibration- robust method. Its success is dependent the difference between (r) and (T) which is relatively small in most real-world scenarios, while the dependency on calibration of existing methods not always be controlled. The geometric explanation of this is that COT measures fundamentally different length in the Wasserstein Space (P(RR)) ). Woe), allowing for the above guarantee which does not exist in previous methods. Moreover, as we will empirically demonstrate in the next section, large pseudo-label shift is prevalent in real models and datasets. Consequentl,, COT performs much better than miscalibration-seniiie methods in most cases.
3.2 Thresholding as a Robust Transport Cost Stastistic
Computationally. COT (or Wasserstein Distance in general) is implemented two-step process: 1) calculating individual transport costs for all samples; 2) returning the mean across all transport costs as the error estimate. While we have seen that COT has some protection against miscalibration, is not completely immune. Another outstanding issue lies in the second step computing the mean of all transport costs. statistics, is well known that the mean is less robust to outliers than the median [21]. In the supplemental material, we show that the empirical transport cost distribution is also heavy-tailed and therefore COT is susceptible to outlier costs. large fluctuation in the outliers impacts the mean much more than it does to the median. Therefore, more robust statistic is desired to protect COT against these outliers.
To search for such robust statistic that is suitable for our purpose, we turn to Average Thresholded Confidence (ATC) [3 for inspiration. ATC tremendously improves the performance of AC precisely by offering such protection against the overconfident outlier predictions (shown in supp material) by returning the percentile above the threshold rather than the mean. In a similar vein, we safeguard COT against outlier costs by introducing COT with Thresholding, COTT.
Specifically, to compute the threshold E [0. 1], we first sample validation set (1 Moal 1 (2 y). Let P.al denote the empirical validation distribution. We compute the optimal transport plan P. = arg minpen(fa (()) (P, C). where C is the cost matrix determined by the L-infinity distance. Note that P E {0, 1 vectors and one-hot labels (Proposition 2.1 in (32). Then the threshold & is set such that the validation of error the classifier equals the fraction of samples with transport cost higher than f, i.e.
(1) (1)
" is permutation matrix due to the equal number of confidence
1 - (C 2 P vally 1H
Eval
With the threshold learned from the validation set, we can compute the COTT target error estimate. Let (1) denote the empirical source label distribution and f Pr()) denote the empirical distribu- tion of confidence vectors of samples from the target distribution Pr(z). We compute the optimal transport plan P arg milpem fg Ps(sn) IP.C). Our COTT estimate is then defined
1 éCOTT
(Ct 2 t (P 1H
n

---

While solving the linear program of optimal transport for COT and COTT is rather straightforward with existing solvers such as POT [12], its time complexity O(n²) prohibits large-scale inputs. We bypass this problem by breaking the test dataset into small batches with a maximum size of 10,000. Concretely, given a test samples, we sample with replacement for [n/10 10, 000] batches and compute an error estimate for each batch. We get the final error estimation of COT and COTT by taking an average of batch estimates.
Note on Implementation:
Experiments
In this section, empirically compare COT and COTT with existing methods on various benchmark datasets. For all experiments, we trained the model on in-distribution data and froze the model after convergance. To predict the model's performance on the target domain, we only used unlabeled data from the target domain. When we have a test set size greater than 10,000, we show the results of utilizing the batched version of COT and COTT detailed in Section For context, solving the OT problem of size 10,000 only takes around 10s, thus adding only negligible computation overhead.
4.1 Datasets and Nature of Shift
In comprehensive evaluation, consider more than 10 benchmark datasets across multiple modalities, including vision and language, with a variety of distribution shifts, Each type of shift is introduced in the following paragraphs:
Synthetic Shift:
First, we consider distribution shifts caused by common visual corruptions, such as brightness, defocusing, and blurriness, which are common in real-world settings. We used the corrupted versions of CIFAR1O, CIFAR100, and ImageNet proposed in [19), which includes 19 types of common visual corruptions across 5 levels of severity.
Novel Subpopulation Shift: Next, we consider novel subpopulation shifts, where the subpopulations in the train and test sets differ. For example, models might have only observed golden retrievers for the dog class but not huskies. In our experiments, we used the BREEDS benchmark [36], which leveraged the ImageNet class hierarchy to create 4 datasets, 17, Nonliving-266 Entity 13, and Entity-30. With this benchmark, we aim to understand if error estimation methods could capture challenges in an increasingly diverse world.
Finally, we consider non-simulated shifts in which the distribution shifts are induced through differences in the data collection process, such as ImageNet-V2 V2 and CIFAR1O-VE proposed 40), which consists of sketched images of the original ImageNet classes. Additionally, we consider distribution shifts faced in the wild, such as ones curated in the WILDS benchmark (24). We consider four WILDS datasets, two for language tasks (Amazon- -onaZon-WILDS, CivilComments- WWILDS) and two for vision tasks (Camelyon17, RxRx1). These datasets reflect various discrepancies between data sources happening in the real world. For example, hospitals might use different stain colors for pathological images. Different groups might follow distinct standards assigning star ratings for their reviews.
Natural Shift:
in (34. We also include ImageNet-
4.2 Architectures and Evaluations
For vision tasks, We trained ResNet18 (CIFARIO, CIFAR100) and ResNet50 [18 (ImageNet, Living17, Nonliving26, Entity Entity30, Camelyon17-WILDS. RxRxI-WILDS); for language tasks -Amazon-WILDD CivilComments-WIL.
we fine-tuned BasiilBERT-baae-unaaa
335 We
followed training setups from previous works [13] and provided the full details the supplemental material. After training, we calibrated models using Temperature Scaling (TS) 17 on the in- distribution validation data, effectively adjusting the output probabilities of the neural network to match the actual correctness likelihood. This approach has previously demonstrated that TS consistently improves error estimation performance for all methods [33]. To evaluate different methods, we utilized the mean absolute difference between their predicted errors and the true errors, which are obtained using ground truth labels. We refer to this metric as Mean Absolute Error (MAE).
4.3 Baselines
We consider array of baselines to compare against methods: COT and COTT.
7

---

Table Mean Absolute Error (MAE) between the estimated error and ground truth error compare different methods. The "shift" column denotes the nature of distribution shifts for each dataset. For vision datasets, we reported results for ResNet18 and ResNer50; for language datasets, we reported results for best-performing method. We defer the full table with std the supplemental material.
The results are averaged over 3 random seeds. We highlight the
Baselines GDE
Ours
Dataset
Shift
AC
DoC
ATC-MC
ATC-NE
COT
COTT
Natural Synthetic
5,97
5,38
5.87
5.9
3.38
3.15
5,41
3.33
CIFAR1O
9.1
8.53
9.26
8.84
4.2
3.37
2.17
1.7
CIFAR100
Synthetic
10.83
8.76
12.07
11.36
6.63
2.09
2.59
Natural
8.5
7.43
8.62
5.62
3.57
2.6
3.88
2.41
ImageNet
Synthetic
10.34
9.28
12.87
6,54
1.59
3.41
3.24
1.42
Same
19.63
19.2
17.5
15.37
8.09
8.47
2.61
Entity13
Novel
29.61
29.18
27.22
24.48
14.54
9.49
15.9
5.46
Entity30
Same Novel
16.97
16.21
13.56
13.98
8,19
9.08
5.9
2.46
27.57
26.81
23.96
23.4
13.46
8.57
15.11
5.94
Same Novel
14.84
14.67
11.22
9.94
4.88
5.43
6.25
2.94
Living17
29.61
29.18
27.22
24.48
14.54
9.49
15.9
5.53
Nonliving26
Same Novel
19.25
18.43
16.6
12.77
11.18
7.06
3.34
31.37
30.54
28.79
23.37
19.93
16.56
17.8
10.46
Camelyon17-WIL
Natural
9.44
9.44
10.24
5.19
7.73
7.73
7.27
5.71
RxRx1-WIIDDS
Natural
5.21
8.44
8.09
6.86
3.25
Amazon- WILDS
Natural
2.62
2.35
2.34
17.04
1.63
1.54
2,43
2.01
CivilCom. WILDS
Natural
1.54
0.96
0.86
1.23
4.68
Average Confidence (AC) estimates target error by taking the average one minus the maximum softmax confidence of target data. AAC = E,- maxjey [z)).
Difference of Confidence (DoC a.k.a. DOC-Feat) [6] estimates target error through the dif- ference between the confidence of source data and the confidence of target data. êDvC Bgwig 11 larg maxjey (z) # v]] E maxjey [z(2)) E Pa [1 maxjey (x)).
Importance Re-weighting (IM) estimates target error as a re- re-weighted source error. The weights are calculated as the ratio between the number of data points in each bin in target data and source data. This is equivalent to 6 using one slice based on the underlying classifier confidence.
Generalized Disagreement Equality (GDE) [2 estimates target error the disagreement ratio of predictions the target data using two independently trained models f(x: and f (x)). ÊGDE
B [1 larg maxjey (x) & arg maxjey (x))
Average Thresholded Confidence (ATC) [13 first identifies threshold such that the fraction of source data points that have scores below the threshold matches the source error on in-distribution validation data. Target enror is estimated as the expected number of target data points that fall
below the identified threshold. êxTC(s) E 1, (1(((() t]], where is the score function mapping the softmax vector scalar. Two different score functions are used, Maximum Confidence (ATC-MC) and Negative Entropy (ATC-NE).
ProjNorm cannot provide a direct In addition, we also compare our method to ProjNorm 41
estimate, instead, the authors demonstrated their metric has the strongest linear correlation to true target error compared to existing baselines. In this case, we followed their setup and performed correlation analysis to draw a direct comparison. We included results the supplemental material and showed that our method consistently outperforms ProjNorm.

---

CIFAR-100
Nonliving-26
ImageNet
1.0
1.0
1.0
Metric
AC
0.8
0.8
ATC-NE
True Error
True Error
True Error
COT
0.8
0.6
COTT
0.4
0.4
0.4
0.2
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6 0.8 1.0
0.2
0.4
0.8
0.8
1.0
Predicted Error
Predicted Error
Predicted Error
Figure 4: Qualitative results for AC, ATC, COT, and COTT, comparing error estimates vs. ground truth target enror. Accurate estimates should be close to y 2 (dashed black line). Notably, COT and COTT remain accurate even when the shifts are large. By contrast, AC and ATC often severely underestimate the error, which is particularly evident in the Nonliving-26 dataset.
4.4 Results
In T report the MAE results grouped by datasets and nature of shifts. Across all benchmarks, we observe that COT always obtains lower estimation error than AC, supporting our theoretical analysis that COT additionally leverages pseudo-label shift to fight miscalibration. On synthetic shift benchmarks (CIFAR CLFFARO-Synite 10-Synthetic, CIFAR 100-Synthetic, ImageNer-Synthetic BREEDS-Same). COT is 4x better than AC, drastically reducing the estimation error. On novel subpopulation shift (BREEDS-novel), COT cuts about half of the AC error. On natural shift, COT also improves upon AC. On ImageNet natural shift datasets, COT reduces the error from 8.5 3.88 compared to AC. COTT, presents the best overall results, surpassing the best current method (ATC) by notable margin. On synthetic shift benchmarks, COTT is 2-3x better than ATC-NE, the stronger version of ATC that uses negative entropy score function. On novel subpopulation shift benchmarks, COTT is least 4 absolute percent better than ATC-NE. On natural shift benchmarks, however, we observed mixed results. On ImageNet-Nature
COTT is better than ATC-NE while on CIFAR10-Natural COTT is marginally worse. On WILDS benchmarks, no single method dominantly outperforms others. Note that the WILDS benchmark datasets contain label shift, meaning (v) 7 Pr(y). This leads COTT to overestimate the error on the CivilComments- Co Nonetheless, COTT has smallest worst-case error of 5.82 compared to ATC-NE's 7.73, demonstrating its robustness even on distribution shifts faced in the wild.
In Figure 4 we use scatterplots to visualize estimations given by different methods, notably AC, ATC, COT, and COTT, where we plot the predicted error against the true error. Ideally, these scattered points should demonstrate strong linear correlation and closely follow the true for COT and COTT, AC and ATC often underestimate, sometimes by large margin. In Nonliving-26, we can see data points representing shifts whose ATC predicted errors are around 0.1 while true errors are close to 1. These observations corroborate the necessity of leveraging pseudo-label shifts to guard against such catastrophic failures of existing confidence-based methods. We include the scatterplots for all datasets the supplemental material, where we show that COT and COTT successfully prevent severe underestimation seen in other methods.
line. While this
5 Conclusion
In this work, we proposed COT and COTT, simple yet effective methods leveraging the optimal transport framework to estimate a classifier's 's performance on out-of-distribution data with only unlabeled samples. Our method is motivated by the observation that existing methods failed to take into account the fact that classifiers often demonstrate pseudo-label shifts when performance drops on an unseen target domain. We formalized this observation by connecting AC and COT under the Wasserstein metric and showing that COT provably provides more conservative estimates by assuming a target marginal distribution. Combining COT with a thresholding strategy that has shown extensive empirical success, we further introduced COTT. On all eleven benchmark tasks, COT and COTT manage to avoid severe underestimation of the model's error seen in current methods. In particular, COTT achieves significantly lower prediction errors than existing methods for most models and datasets (up to 3x better), establishing new state-of-the- results. We believe our work makes

---

an important step forward in making performance estimation methods more reliable and theoretically grounded and thus more applicable in real-world applications.
Limitations: Despite the strong empirical performance, our method does suffer from several limitations. First, our method is currently only applicable to multi-class classification problems under the assumption that the marginal label distribution must remain constant between the train and test distributions, though as we will show in the supplemental material, our method still quite robust when the difference between source and target marginal is small. In addition, while we have derived lower bound for error estimates, we have not currently formulated an upper bound; however, we have not observed overestimating the error to be common problem empirically. Lastly, the relationship between miscalibration and pseudo-labe shift currently only empirical in nature, not theoretical.
References
[1] David Alvarez-Melis and Nicolo Fusi. Geometric dataset distances via optimal transport. Advances in Neural Information Processing Systems, 33:21423 11-21428-21438 21439, 2020.
[2] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pages 214-223. PMLR, 2017.
[3] Christina Baek, Yiding Jiang, Aditi Raghunathan, and Zico Kolter. Agreement-on-the- Predicting the performance of neural networks under distribution shift, 2023.
[4] Yogesh Balaji, Rama Chellappa, and Soheil Feizi. Normalized wasserstein for mixture distribu- tions with applications in adversarial learning and domain adaptation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6500-6508, 2019.
[5] Krishnakumar Balasubramanian, Pinar Donmez, and Guy Lebanon. Unsupervised supervised learning ii: Margin- based classification without labels. In Proceedings of the Fourteenth Inter- national Conference on Artificial Intelligence and Statistics, pages 137-145. JMLR Workshop and Conference Proceedings, 2011.
[6] Mayee Chen, Karan Goel, Nimit S Sohoni, Fait Poms, Kayvon Fatahalian, and Christopher Ré Mandoline: Model evaluation under distribution shift. In International Conference on Machine Learning, pages 1617-1629, PMLR, 2021.
[7] Shai Ben David, Tyler Lu, Teresa Luu, and Dávid Pâl. Impossibility theorems for domain adaptation. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 129-136. JMLR Workshop and Conference Proceedings, 2010.
[8] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image datahase. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. leee, 2009.
[9] Weijian Deng and Liang Zheng. Are labels always necessary for classifier accuracy evaluation? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pages 15069-15078, 2021.
[10] Weijian Deng, Stephen Gould, and Liang Zheng. What does rotation prediction tell us about classifier accuracy under varying testing environments? In International Conference on Machine Learning, pages
PMLR, 2021.
[11] Pinar Donmez, Guy Lebanon, and Krishnakumar Balasubramanian. Unsupervised supervised learning i: Estimating classification and regression errors without labels. Journal of Machine Learning Research, 144). 2010.
[12] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78): 1-8, 2021. URL http: // /m/rr. org/ wttgg/pprr////eeeee//eegeeeeeeee hppppes//22//22222 451. html
10

---

[13] Saurabh Garg, Sivaraman Balakrishnan, Zachary C Lipton. Behnam Neyshabur, and Hanie Sedghi. Leveraging unlabeled data to predict ------i-iitiitttion performance. arXiv preprint N:Xiv:2201.042:4 2022.
[14] Saurabh Garg, Nick Brickson, James Sharpnack, Alex Smola, Sivaraman Balakrishnan, and Zachary Lipton. Risbench: Domain adaptation under relaxed label shift. In International Conference Machine Learning (ICML), 2023.
[15] Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix Wichmann, and Wieland Brendel. imagenet-trained cmns are biased towards texture; increasing shape bias improves accuracy and robustness. arXiv preprint arXiv: 12231, 2018.
[16] Devin Guillory. Vaishaal Shankar, Sayna Ebrahimi, Trevor Darrell, and Ludwig Schmidt. Pre- dicting with confidence on unseen distributions. Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1 1134-1 144, 2021.
[17] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pages 1321-1330. PMLR, 2017.
[18] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[19] Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In International Conference on Learning Representations, 2018. 8.
[20] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribuiis examples neural networks. arXiv preprint 160.0:16 2016.
[21] Peter J Huber. Robust statistics. In International encyclopedia of statistical science, pages 1248-1251. Springer, 2011.
[22] Yiding Jiang, Vaishnavh Nagarajan, Christina Baek, and Zico Kolter. Assessing generalization of sgd via disagreement. arXiv preprint arXiv:2106. 13799, 2021.
[23] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[24] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness. Wei Guo, Berton A. Earnshaw. Imran S. Haque, Sara Beery, Jure Leskovee, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. WILDS: A benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning (ICML), 2021.
[25] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of wild distribution shifts. In International Conference on Machine Learning, pages 5637-5664. PMLR, 2021.
[26] Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International conference on machine learning, pages 3122-3130. PMLR, 2018
[27] Xinran Liu, Yikun Bai, Yuzhe Lu, Andrea Soltoggio, and Soheil Kolouri. Wasserstein task embedding for measuring task similarities. arXiv preprint MxXiv:2208.//720 2022.
[28] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization, arXiv preprint 17X1v 2017.
[29] Yuzhe Lu, Xinran Liu, Andrea Soltoggio, and Soheil Kolouri. Slosh: Set locality sensitive hashing via sliced- wasserstein embeddings. Proceedings of the IEFF/CVF Winter Conference on Applications of Computer Vision (WACV), pages 2566-2576, January 2024.
11

---

[30] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan. and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Advances in neural information processing systems, 32, 2019.
[31] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-periie pettheeeffrmacc deep learning library. Advances in neural information processing systems, 32, 2019.
[32] Gabriel Peyré, Marco Cuturi, al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 116-6))3555667, 2019.
[33] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do cifar-10 classifiers generalize cifar- 10? arXiv preprint (8060008060004) 2018.
[34] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International conference machine learning, pages 5389-5400. PMLR, 2019.
[35] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv: 108, 2019.
[36] Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry. Breeds: Benchmarks for subpopu- lation shift. arXiv preprint arXiv:2008. 04859, 2020.
[37] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the ligeliikl function. Journal of statistical planning and inference, 90(2):227-24 2000.
[38] Simon Stepputtis, Joseph Campbell, Mariano Phielipp, Stefan Lee, Chitta Baral, and Heni Ben Amor. Language-condditoned imitation learning for robot manipulation tasks. Advances in Neural Information Processing Systems, 33:13139-13150 2020.
[39]
Cédric Villani et al. Optimal transport: old and new, volume 338. Springer, 2009.
[40] Haohan Wang, Songwei Ge, Zachary Lipton, and Eric P Xing. Learning robust global represen- tations by penalizing local predictive power. In Advances Neural Information Processing Systems, pages 10506-10518, 2019.
[41] Yaodong Yu. Zitong Yang. Alexander Wei, Yi Ma, and Jacob Steinhardt. Predicting out-of- distribution error with the projection norm. arXiv preprint arXhv:2202.0583. 2022.
12

---

A Deferred Proofs
For readers' convenience, we review the statements of the propositions and corollaries and provide the full proofs below.
A.1 Proof of Proposition
Proposition 1 (EAC-Woo Equivalence). Let (P(IR)) Woo be the metric space of all distributions over TR,, where W is the Wasserstein distance with c(x,)) v) = 1| ylloo. Then, the estimated error of AC is given by êsc W (f P(O), (((C),PPsnieee Ppscudo(())
Proof. We first show the following equality. Let 5 arg max, (2)
1 F-- (x) = 11 f(x))l>
where ū, = 1 = j"]. Let f-j- (2) denote the vector f(x) with j"-th element removed. Since for confidence vector [If(x)]1 1,
(s) (z) 11lh221116 (z)l
Therefore, we have obtained the desired Equality
| [x)]l = max(1lf-x (1)) (x)) 15- (5-(x)
Next, we consider the optimal transport plan between F P()) and Precuto(3) Namely, we show all confidence vectors (() coupled with their one-hot pseudo-labels g( This can be observed by the fact that the one-hot pseudo-label is the one-hot label that achieves the lowest L-infinity cost, i.e.
[l(()() - llx S (lf()(()) J loo Vy' E {0, 13 n
Suppose there exist confidence vectors that are not coupled with their one-hot pseudo-labels, then all individual costs are suboptimal and the total cost suboptimal well, contradicting the assumption that the transport plan is optimal. Therefore,
W (f P(e), Proccto (7)) 1 Σ (1) 1
Combining Equality [ and Equality and Wo distance
we obtain the desired relationship between AC error estimate
AAC
Σ max (z()))) n1 i=1
n
1 2 1lf(z(1)
of = Wor Wor Prscudo (v))
71 1=1
A.2 Proof of Corollary 1
Corollary (Pp (Pscudo(7) is closest to F+ P()). Let P'( E 1 be one-hot label distribution. Then W P(O) P') 2 Woo (fx P()), Preudo (7)).
Proof. We first show the following equality, which establishes the relationship between AC accuracy estimate with Wo distance:
1 ĆAC = Wx ((O)))))
Since Woo (fz P(c), 56) transports f to do. the optimal transport plan couples every element in f P()) to 0. For each (00) its confidence vector f P(č) has a transport cost (x(()() 0 Ollec- Hence,
1 - ĆAC
1 Σ max (z((
Σ - 0/
Wo 8())
13

---

With this, our inequality is simply the Triangle Inequality in (P(R*), Wo),
W (f P(C), 6o) + W (f=
W (P (g), =1
Combined with Equation 3 we obtain the desired inequality so (C), pscudo (1))
W (f s P(O),
A.3 Proof of Proposition 2
Notations:
Cet - (ī A arg maxj Cj - arg maxj }j} be the of confidence vectors
whose one-hot pseudo-labels that match with that of E A k-1, Let P(Λ be the set of all distributions of confidence vectors and Pe PalPpeetoo
(P'(2) E P(A (TA=-))) Preedoo (j) P' (arg max, ? arg max, Øi}} } be the set of distributions of confidence vectors that share the same pseudo-label distribution (
PalPreetoo (3)) defines an equivalence class for the space of distributions of confidence vectors (P(Ak R-1) Woo) that share the same pseudo-label distribution P Ppscado(y). Pictorially, in Figure | Pel PelP preedoo (μ)) represents the line between do and Ppscudo On this line, every distribution confidence vectors shares the same pseudo-label distribution P ('
To prove Proposition 2. need the following lemma, which intuitively allows to change the metric from measuring the distance between two points to the distance between an equivalence class and point D
Lemma (Change-of-metric)) T. E [0,1]* n A k-1 be two one-hot labels. Then the following holds
inf | 11 = 0.5 x 1 (EC(G)
Proof.
If g = V. then we know the optimal ē=
inf
|| 7 |ox |1 - 7 10 =
aEC(
i T7. then we proceed by showing equality with two inequalities. First, observe {00.5 + 8) (0.5- (0.5-8)2 8)
(0, 0.5]] C C(g).
inf ||2 loo inf [10.5 + 8) + (0.5 - -5) Vl1 6E(0.0.5]
inf (0.5 5) 0.5 5E(0,0.5)
dEC(S)
If ق| 7 ~0 0.5, arg maxj 2y arg max; D7 # arg max, My i.e. ē & C(ÿ). Therefore, infaec(o) 2| 1/ xo 2 0.5, which further implies inf ||ē 11 0.5.
We are now in a position to prove Proposition] that the left-hand side of the incquality is simply the distance between f (c) and (r with change-of- metric the metric defined above.
2 which follows from the somewhat surprising fact
Proposition 2 (Calibration independent lower bound of COT). Under the assumption that Pr( = Ps(7), we always have écor 2 0.5Woe oc (Pooendo (g), (r))).
Proof. Since Pr(T)- Ps(T)) ēcor Wo (f Pr(o,,
inf (
inf f
inf l| dz (EC(CE)
(4)
inf x(7 Mell Pamds (T)
inf 2| dT (7. ECC(r)
(5)
'This is closely related to the Hausdorff distance between sets in metric space.
14

---

Equation follows from the observation that ((²) = ( for confidence vector č and its cone- sponding one-hot pseudo-label y7. Furthermore, since our new metric inf ecfr) || yo is only defined up the equivalence class, replacing each č E C()) with its pseudo-label g does change the distance.
Plugging in Lemma
/ 0.5 15 + ( ( 5)
éCOT 2
inf
xl M)M (p))
/ 11 dol (y. .0)
0.5
inf
0.5 20 (P preuto Pr
A.4 Tightness of Proposition] 2
While Meequlity[4seeeme loose, our bound is, in fact, tight if further assumptions the calibration status of the classifier f are made. We need the following lemma that establishes the relationship between pseudo-label shift and the total variation distance between target label distribution and pseudo-label distribution. Note this equivalence only makes sense in the context of measuring Woc distance between two one-hot label distributions, but not under other contexts presented in the paper.
Lemma (Pseudo-label shift is total variation).
Wo (P pseedoo (1), (r) || pseudo (0) Pr(j))lTV
Proof. For two J. {0. 1 n A-1 the transport cost c(g.g") = 1 + 77.. Then, the standard result on optimal transport [39 gives the desired equality.
Corollary 2.
W ( Pr =
Σ
Prrendo (V), Pr(())
Proof.
Woo (Poseudo PT(T))
P Precdoo (1)) Pr(TiIITV
Σ
|P IPponddo (17 - PT(
2
Te (
Σ
pseudo max (ppeuuo (J), Pr())) min (P (pecuo(()) (T))
Ge (0(0.1)=AA
Σ
max ( Pr + min ( Psscddo (T),
2
Je (o.1)
Σ
min (P (p Pr
ge (n
Σ
P Procudo (7) + Pr(j))
Σ
min (reeuto Pr(T))
2
(o
(E(0.1)=na**
Σ
min Ppeento Pr(T)
DE(0.1)^AAM11
Finally, we show Proposition tight by constructing a sequence of distributions of confidence vectors, the limit of which is exactly 0.5W (pscudo())) (g), Pr())) away from Pr
15

---

Lemma 3 (Proposition 2 is tight).
inf P(O)eP Pana
(P(),, = 0.5 (P preudd (j), Pr(1))
Proof. First, construct the following family of distributions (Ps(o) E (0,). where Pa(c) is the following mixture distribution
Po = -Pp(() + (t)
where Pn( = 7- min (rinndp (1), (T)) ? = Eje (o.))ra min
poeudo (0), Pr( }.
Px (t) is a distribution supported on A k n (0.5 6,0.5 6, 0}* (i.e. one element is 0.5 another 0.5 6, and the rest are 0). Additionally, Px 0.5 5) Preesoo(f (y) = 1) and
(t = 0.5 5) Pr. = 1). easy to check that Pa(c) E PalPpaeudo (t))
Next, we construct an explicit transport plan ((, E [I(,s(C), Pr(1)). We construct it via the factorization (, 17) Ps (77 where
{
i or (7. 57 = 0.5
otherwise
The cost of this transport plan is therefore
/ | M- (0.5 + 6) - -7) = (0.5 5) (Ppeeudo Pr(T))
where the last equality follows from Lemma 2 Taking infimum.
/ ||č dT 7) = 0.5W (P Pespudo (T), Pr),
inf 6e(0.0.5)
Combining everything far, obtain the desired result:
/ (1E--loodTEE
0.5W c0 (P (Peccudo (r)))(
inf 6E(0,0.5)
inf
W (Po(t), Pr(j))
(6)
60,00
inf
W (P()
(7)
P. Poeusa (7)) 0.5W (P (reuudo Pr(7))
(8)
Inequality follows from the fact that the optimal transport plan cannot have greater cost than our explicit plan π. Inequality is due to the fact that the family of distribution we are considering is subset of P. Pe[Ppeudo (T)). Inequality 8 is an application of the lower bound which holds for all P(c) E P.[P prepuud (7)).
B Extended Results
B.1 Results with Standard Deviation
We show the full experimental results with standard deviation in Table
B.2 Qualitative Results
We show the qualitative results (scatter plots) in Fig
16

---

Table Mean Absolute Error (MAE) between the estimated error and ground truth error compare different methods. The "shift" column denotes the nature of distribution shifts for each dataset. For vision datasets, we reported results for ResNet18 and ResNer50; for language datasets, we reported results for best-performing method. The number in the parentheses denotes the standard deviation.
The results are averaged over 3 random seeds. We highlight the
Baselines GDE
Ours
Dataset
Shift
DoC
ATC-MC
ATC-NE
COT
COTT
5.97
5.38
5.87
5.9
3.38
3.15
5.41
3.33
Natural
(0.10)
(0.08)
(0.09)
(0.15)
(0.14)
(0,28)
(0.09)
(0.13)
CIFARIO
8.84
4.2
2.17
1.7
Synthetic
(0.25)
(0.28)
(0.35)
(0.11)
(0.38)
(0.30)
(0.09)
(0.26)
CIFARI00
Synthetic
10.83
8,76
12.07
11.36
6.8
6.63
2.09
2.59
(0.08)
(0.22)
(0.37)
(0.25)
(0.39)
(0.43)
(0.27)
(0.01)
Natural
8.5
7.43
8.62
5.62
3.57
2.6
3.88
2,41
(0.39)
(0.41)
(0.47)
(0.33)
(0.46)
(0.66)
(0.04)
(0.11)
ImageNet
10.34
9.28
12.87
6.54
1.59
3,41
3.24
1.42
Synthttic
(0.83)
(0.86)
(0.77)
(0.37)
(0.08)
(0.53)
(0.28)
(0.29)
19.63
19.2
17.5
15.37
8.09
7.23
8.47
2.61
Same
(2.17)
(2.51)
(0.90)
(1.06)
(0.49)
(0.49)
(0.66)
(0.31)
Entity13
Novel
29.61
14.54
(2.61)
(2.95)
(1.08)
(0.61)
(0.95)
(0.70)
(0.80)
(0.75)
16.97
16.21
13.56
13.98
8.19
9.08
5.9
2.46
Same
(0.35)
(0,36)
(2.53)
(0.26)
(1.07)
(0.42)
(0.29)
(0.65)
Entity30
27.57
26.81
23,96
23.4
13.46
15.11
5.94
Novel
(0.06)
(0.61)
(2.79)
(0.1)
(2,55)
(2.2)
(0.38)
(1.17)
14.84
14.67
11.22
9.94
4.88
6.25
2,94
Same
(3.36)
(3.30)
(2.06)
(0.48)
(0.42)
(1.91)
(1.21)
Living17
29.61
29.18
27.22
24.48
14.54
9.49
15.9
5,53
Novel
(3.76)
(3.71)
(3.45)
(0.74)
(2.87)
(3.25)
(2.04)
(1.93)
12.77
11.18
7.06
3.34
Same
26
(2.45)
(3.13)
(0.96)
(0.85)
(2.77)
(0.70)
(1.17)
(0.90)
31.37
30.54
28.79
23.37
19.93
16.56
17.8
10.46
Novel
(2.99)
(3.65)
(1.4)
(0.61)
(4.02)
(1.28)
(1.53)
(3.08)
Camelyon1 1-WWLDS WILDS
Natural
9.44
9.44
10.24
5.19
7.73
7,73
7.27
5.71
(0.50)
(0.49)
(0.38)
(0.44)
(0.72)
(0.72)
(0.57)
(0.94)
8.44
8.09
7.48
6.53
6.86
3.25
5.82
RxRxI-WILDS
Natural
(0.26)
(0.15)
(0.16)
(0.26)
(0.10)
(0.28)
(0.16)
(0.31)
2.62
2.35
2.34
17.04
1.63
1.54
2.43
2.01
Amazon Amazon-WII.JD WILDS
Natural
(0.16)
(0.06)
(0.06)
(0.84)
(0.1)
(0.11)
(0.04)
(0.42)
1.54
0.96
0.86
8.7
2.3
2.3
1.23
4.68
CivilCom. -WILDS
Natural
(0.23)
(0.19)
(0.20)
(0.14)
(0.34)
(0.34)
(0.05)
(0.39)
B.3
Correlation Analysis
leverages pseudo labels on the target domain to retrain copy of the reference model trained on the source domain. The authors show that the difference between the two models' parameters has a strong linear correlation to the true target eтror. Following the paper's experimental setup, we conducted the correlation analysis on CIFARIO and CIFAR 100 using three architectures. ResNet18, ResNet50, and VGG1I. I. We note that ProjNorm in fact implicitly leverages the assumption that Pr (y) (3) as this condition holds for both CIFARIO and CIFAR100. As Fig. 18 of their paper 41 shows, ProjNorm tends to overestimate when label shift exists.
ProjNorm [41]
B.4 Mild Label Shift
We motivate our methods under the assumption no label shift. In Proposition 2 we showed that the worst-case underestimate of COT is half of the pseudo-label shift. Under mild label shifts, the guarantee for such worst-case underestimation becomes weaker. This can be observed from the following corollary of Proposition] 2
17

---

Table 3: Mean Absolute Error (MAE) between the estimated enror and ground truth error to compare different methods under mild label shift. The results are averaged over random seeds. We highlight the best- best-performing method. The number in the parentheses denotes the standard deviation.
Baselines GDE
Ours
Dataset
Shift
AC
DoC
IM
ATC-MC
ATC-NE
COT
COTT
5.58
4.99
5.50
5.69
2.76
2.47
3.75
1.68
Natural
(0.26)
(0.23)
(0.22)
(0.04)
(0.32)
(0.43)
(0.28)
(0.34)
CIFARIO
8.67
8.10
8.82
8.47
3.93
3.13
2.76
4,0
Synthetic
(0.29)
(0.31)
(0.38)
(0.15)
(0.38)
(0.32)
(0.04)
(0.30)
10.89
8.85
12.14
11.33
6.93
6.76
1.89
2,81
CIFARI00
Synthetic
(0.15)
(0.22)
(0.37)
(0.23)
(0.44)
(0:48)
(0.30)
(0.07)
8.36
7.29
8.46
5.54
3.53
2.47
3.74
2.05
Natural
(0.37)
(0.42)
(0.48)
(0.36)
(0.48)
(0.71)
(0.20)
(0.26)
ImageNet
10.26
9.19
12.79
6,50
3.51
3.03
1.75
Synthetic
(0.83)
(0.86)
(0.77)
(0.40)
(0.08)
(0.52)
(0.25)
(0.33)
14.60
15.49
15.18
4.59
3.24
Same
(0.38)
(0.34)
(0.22)
(1.03)
(0.80)
(0.57)
(0.23)
(0.12)
Entity13
24.39
23.49
24.56
14.99
11.19
Novel
(0.23)
(0.19)
(0.05)
(0.62)
(0.82)
(0.64)
(0.34)
(0.38)
15.46
13.93
15.55
13.83
8.80
8.26
4.75
2.16
Sume
(0.70)
(0.65)
(0.74)
(0.27)
(0.64)
(0.83)
(0.29)
(0.15)
Entity30
25.98
24.45
26.72
23.28
15.56
13.21
13.96
7.07
Novel
(0.53)
(0.46)
(0.68)
(0.14)
(0.56)
(0.90)
(0.17)
(0.27)
11.38
10.90
11.83
9.85
4,46
4.39
4.40
2.71
Same
(0.67)
(0.48)
(1.31)
(0.41)
(0.31)
(0.18)
(0.34)
(0.81)
Living17
25.72
25.13
26.32
21.61
14.09
11.48
16.94
9.31
Novel
(0.46)
(0.76)
(1.98)
(0.68)
(2.31)
(1.99)
(0.78)
(1.79)
16.28
14.48
15.69
12.88
9.63
9.69
5.33
2.18
Same
(0.37)
(0.29)
(0.19)
(0.84)
(0.43)
(0.66
(0.73)
(0.23)
Nonliving26
27.93
26.13
27.76
23.25
18.15
16.08
15.66
8.71
Novel
(0.08)
(0.25)
(0.29)
(0.69)
(0.38)
(0.38)
(0.45)
(0.42)
Table 4: Coefficients of determination (R²) and rank correlations (p) to measure the linear correlation between a method's output quantity and the true target error (the higher the better). COT achieves superior performance than all existing methods across different models and datasets.
AC
Eatropy
GDE
ATC
ProjNorm
COT
Dutaset
Network
n2
Rt2
R12
π22
nt
R²
P
ResNet18
0.825
0.980
0.862
0.982
0.842
0.981
0.875
0.987
0.947
0.988
0.996
0.998
ResNer50
0.950
0.995
0.949
0.995
0.959
0.995
0.885
0.989
0.936
0.989
0.993
0.996
CIFARIO
VGG11
0.710
0.938
0.762
0.958
0.723
0.948
0.548
0.851
0.756
0.949
0,994
0.993
Average
0.828
0.971
0.858
0.978
0.841
0.975
0.769
0.942
0.880
0.975
0.994
0.996
ResNet18
0.943
0.987
0.932
0.984
0.950
0.988
0.927
0.985
0.969
0.974
0.995
0.997
CIFAR100
01948
0.984
0.955
0.991
0.991
VGG1I
0.794
0.959
0.821
0.973
0.870
0.978
0.736
0.975
0.653
0.849
0,996
0.997
Average
0.898
0.978
0.900
0.980
0.927
0.985
0.873
0.984
0.868
0.938
0,994
0.997
18

---

CIFAR-10
CIFAR-100
ImageNet
1.0
0.8
Metric
AC
Thus Error
True Error
0.8
0.8
ATC-MC
True
COT
COTT
0.2
02
0.0
0.2
0.4
0.8
0.8
0.2
0.4
3.6
0.8
0.2
0.4
0.6
0.8
1.0
Predicted
Predicted
Predicted
Living-17
Nonliving-26
Entity-13
Entity-30
1.0
1.0
0.8
0.8
0.8
True Error
True Error
True Error
0.8
0.4
True
0..
0.4
02
0.2
0.2
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.8
Predicted Error
Prediicted Error
Predicted Error Amazon
Predicted Error
Camelyon
RxRx1
CivilComments
0.5
0.35
0.4
True Error
0.20
True Error
True Emor
0.30
True Enar
0.3
0.15
0.2
0.10
0.08
0.20
0.1
0.00
3.00
0.10
0.20
0.30
0.6
0.7
0.8
0.9
0.15
0.25
0.35
0.5 0.0
Predicted Error
Predicted
Predicted Error
Figure 5: Qualitative results for AC, ATC, COT, and COTT. In these scatterplots, the x-axis is the target еиrоr estimate and the y-axis the ground truth target error. Accurate estimates should be close to y x (dashed black line). We can see that for all datasets, COT and COTT avoid the severe underestimation seen on ATC.
Corollary (Calibration independent lower bound of COT under mild label shift).
écor 2 0.5W o0 (Ppendd(() Pr( Woo Pr())
Proof. By Triangle Incquality in (P(R*), Wo.).
W Pr(), + Wo (Ps(T), (F (=(FFP((O)
Combined with Proposition we obtain the desired result.
As the label shift increases, we have weaker guarantee of the worst-case underestimation error of COT as long as Wx (P) (r) S 0.5W (P (Ppseudo Pr(j)). However, we perform additional controlled experiments which suggest our methods remain to be the most performant despite the theoretical guarantee is not as strong as the case without label shift.
To simulate mild label shift for datasets with (T) = (7)),, we first calculate the original target marginal and then sample the shifted target marginal from Dirichlet distribution in 14 with parameter 50. The parameter controls the severity of the label shift, and a smaller a means a larger label shift. Concretely, let the shifted target marginal be (T) Then (g) Dir(3) where (1)) estimate the performance. We conducted this mild label shift experiment for CIFAR1O, CIFARIO0 ImageNet, Living17, Nonliving26. Entity 13, and Entity30 as these datasets have the same source and target marginal. We showed the results in Table 3 methods under this relaxed condition.
(T) Finally, based on (7)) we sample new set of test samples for which we
As we can see, our methods still dominate existing
19

---

ATC > AC
ATC = AC
COTT COT
COTT>CO
density
density
10
densi
density
2
2
0
0
0.0
0.5
0.0
0 0,5
0.0
1.0
0.0
0.5
1.0
cost
cost
cost
cost
Figure 6: We demonstrate cases where using thresholding improves over taking averages. The x-axis denotes the max norm between confidence vector and the corresponding one-hot label. For AC and ATC-MC, the corresponding label is always the argmax of the confidence vector as mentioned in section 2.3 For COT and COTT, the corresponding label is the one matched via optimal transport. We observe that thresholding improves over averaging when the cost distribution is less concentrated around 0, which corresponds to situations where model very confident on most samples.
B.5
When does thresholding improve averaging?
In this section, we provide some intuitions on when using a threshold provides better estimates than taking the average. From Fig. [6] show that thresholding yields larger and more accurate estimates when the cost distribution on the OOD data is more spread out and less concentrated around By contrast, when the cost distribution is mostly near 0, thresholding leads similar estimates as averaging. Interestingly, even on OOD data where the model has very low performance, there is still decent amount of samples whose cost near O. Thus, when taking the average, we will end up with smaller value which suggests a low error. In these cases, thresholding will give larger error estimates than averaging.
C
Datasets
CIFARI0:
The synthetic shifts included 19 common visual corruptions across 5 levels of severity
from 19].
The natural shift is CIFARIO-V2 33
CIFAR100:
The synthetic shifts included 19 common visual corruptions across levels of severity
from [9]
The synthetic shifts included 19 common visual corruptions across 5 levels of severity from 19 The natural shifts include 4 datasets from ImageNet-Vi (3 and ImageNet-Sketch [40].
ImageNet:
The BREEDS benchmark contains 4 datasets, Living-17, 17, Nonliving26, Entity 13, Entity30. For each of the datasets, the same subpopulation shifts include the corrupted versions of the test set with the same subpopulation; the novel subpopulation shifts include the clean as well as corrupted versions
BREEDS:
the test set with novel subpopulation.
WILDS:
For all WILDS datasets, we used the official OOD datasets provided in their paper (25
D Experiment Setup
We performed training PyTorch 31, and we used RTX 6000 Ada GPUs.
For datasets without an official validation set, we randomly sampled subset of the official training set as the validation set to perform calibration and learn thresholds for ATC and COTT. We trained models for each dataset with random seeds {0, 10).
We reserved 10000 images from the training set as the validation set. We trained ResNet18 from scratch, using SGD with momentum equal to 0,9 for 300 epochs. We set
CIFARIO and CIFARI00:
20

---

weight decay to 5 x 10-4 and batch size to 200. We set the initial learning rate to 0.1 and multiply it by 0.1 every 100 epochs.
We reserved 50000 images from the training set the validation set. We used ResNet50. While ImageNet pretrained weights are available in PyTorch, we needed multiple ones trained using different initializations. Due to limited computation resources, we reused the upper layer weights but reinitialized the last layer with different random seeds. We finetuned the whole model using Adam 23 with batch size of 64 and learning rate of 10- for 10 epochs.
ImageNet:
We used the intersection we set aside and the BREEDS dataset as the validation set. For all BREEDS datasets (Living17, Nonliving26, Entity 13, Entity30), we trained ResNet50 from scratch.
BREEDS:
images that are both the ImageNet validation images
For Living 17 and Nonliving26, we used SGD with weight decay of 10-4 and batch size of 128. We trained for 450 epochs. We set the initial learning rate 0.1 and multiplied it by 0.1 every 150 epochs.
For Entity 13 and Entity30, we used SGD with weight decay of 10 and batch size of 128. We trained for 300 epochs. We set the initial learning rate to 0.1 and multiplied it by 0.1 every 100 epochs.
Camelyon17-WILD We used the id_val group as the validation set. We fine-tumed ImageNet pretrained ResNet50 using SGD with momentum of 0.9, weight decay of 5 x 10 4, and batch size of 32, for 5 epochs.
RxRxI-WILDSS We used the id_ text group the validation set. We followed 25 to fine-tune an ImageNet pretrained ResNet50. We used Adam with weight decay 10-5 and batch size of 75, for 90 epochs. We increased the learning rate from 0 to 10-4 linearly for the first 10 epochs and decayed it following a cosine learning rate schedule.
Amazon-We : We used the id val group the validation set. We followed 25 to fine-tune
a DistiBBERT--ass--nnaaedd model (35). We used AdamW (28) with weight decay 10-2, 2 learning rate of 10-5, and batch size of for 3 epochs. We set the maximum number of tokens 512.
CovilComments-Wiie WILDS:
We used the val group as the validation set. We followed 25 to
fine-tune DistilBERT--ase-une learning rate of 10-5, and batch size of 16, for 5 epochs. We set the maximum number of tokens to 300.
model (35) We used AdamW 28 with weight decay of 10
21


Reviews:
[{"review_id": "SNevgYzRQT", "reviewer": "Reviewer_HB65", "summary": "The manuscript studies the challenges caused by out-of-distribution (OOD) data in machine learning models. They identify \"the difference between the predicted and true OOD label distributions\" (called pseudo-label shift) as the main reason many existing works underestimate OOD errors. They propose a new approach called Confidence Optimal Transport (COT), which uses optimal transport theory to provide more robust error estimates in the presence of pseudo-label shift. Another approach they propose is COT with Thresholding (COTT), which further applies thresholding to individual transport costs to improve the accuracy of COT's error estimates. The authors present impressive experiments to conclude that the COTT approach outperforms existing state-of-the-art OOD error-predicting methods. Predicting a classifier's performance on out-of-distribution (OOD) data is a significant challenge in machine learning, so this manuscript is timely and important.", "questions": "- The performance of COTT depends on the threshold. The choice of the threshold could impact the performance of COTT. How sensitive is COTT to the threshold value? Is thresholding effective in reducing the impact of outliers?  ", "limitations": "The paper has a particular section addressing the limitations of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Due to the use of the Wassienstien distance, COT is robust to miscalibration, meaning it performs well even when the predicted probabilities of the model are not well-calibrated. This is a significant advantage as most other metrics are sensitive to miscalibration. \n\n- It looks like COT and COTT are better at handling pseudo-label shifts, i.e., when there are differences between the predicted and true OOD label distributions. Table 1 extensively compares COT and COTT against other metrics for measuring the OOD errors.\n\n- It is very welcomed that COT provides some performance guarantee. Under the assumption that the true and predicted label distributions are the same, COT predicts an error of less than half the Wasserstein distance between the pseudo-label distribution and the true label distribution", "weaknesses": "- The computation of COT and COTT involves solving a linear program of optimal transport. Yes, the authors propose a batching technique to make their methods scalable, but there is a concern that COTT is computationally infeasible for large-scale inputs. \n\n- In most practical setups, COT doesn't have any performance guarantees because the assumption that the true and predicted label distributions are the same is rarely valid. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review and for the recognition that our methods “have a significant advantage” over other metrics, our experiments are extensive, and we provide performance guarantees. We would like to address the concerns and questions raised by the reviewer as follows:\n\n### On Weakness 1\n\nWe thank the reviewer for raising concerns over the scalability of our algorithm. Indeed, using COT/COTT requires solving a linear program with $O(n^3)$ time complexity. That’s why we proposed the batched version of COT and conducted all experiments with this setup. For a batch of 10,000, COT finishes the prediction in 7 seconds when using the Python Optimal Transport (POT) library [1].  Thus, we think batched COT is reasonably fast, especially considering the current problem setting where we want to estimate the performance of a bunch of samples instead of single ones, which, most likely, do not require real-time response. We have added this discussion to our paper.\n\n### On Weakness 2\n\nWe assume the reviewer refers to our assumption that the target label marginal is similar to the source label marginal. In that case, we agree that this assumption may not hold in real-world cases. That’s why we conducted experiments where we simulate mild label shift in Section B4 of our supplemental material and demonstrated that COT/COTT still provides superior performance. We also agree that COT/COTT might fail in extreme cases but ultimately, all works tackling distribution shift have to make some assumptions about the data as it is theoretically impossible to have an OOD error prediction algorithm that works for any distribution shift (See section 3.1 in Garg et al. 2022 [2] ). Thus, we think one significance of our work is that we specify a specific assumption that, when held true, makes our method a more desirable one compared to other methods.\n\n### On Question 1\n\nWe thank the reviewer for this great question regarding the threshold of COTT. We would like to point out that in our implementation, the threshold of COTT is not a hyperparameter, but is learned based on the transportation costs such that the number of validation samples whose costs are above the threshold matches the number of mistakes (See Section 3.2, paragraph 3 of our paper). While it is interesting to see the impact of varying the threshold, the current way of setting the threshold makes it a consistent estimator of in-distribution test errors (see Supp D.3 in Garg et al. 2022 [2]).  Empirically, thresholding is effective in reducing the impact of outliers as evidenced by the performance improvement of COTT over COT, and ATC over AC. \n\n### References\n\n[1] Flamary, Rémi, et al. \"Pot: Python optimal transport.\" The Journal of Machine Learning Research 22.1 (2021): 3571-3578.\n\n[2] Garg, S. and Balakrishnan, S., 2022. Leveraging Unlabeled Data to Predict Out-of-Distribution Performance. ICLR.\n"}, {"review_id": "4cdhxM2hkV", "reviewer": "Reviewer_1Jqy", "summary": "The paper proposes to compute OOD error estimates using a Wassertein distance between the target label distribution and the distribution of confidence vectors. This is in contrast to AC-MC which compare the pseudo-label distribution and the confidence distribution. The paper motivates COT (confidence optimal transport) and COT - threshold to handle outliers and shows they are useful metrics in understanding OOD error. The paper does a variety of experiments to evaluate how the proposed methods do in fact estimate OOD error bettter than existing work.", "questions": "See weaknesses.", "limitations": "In one sense. The weaknesses section outlines the issue of understanding what kind of OOD the method is really testing.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The experiments in the paper show clear advantage of COT and COTT for predicting OOD error using unlabelled samples.\n2. The presentation in the paper is clear, barring some organization issues.\n3. The paper tackles the important problem of estimating OOD error without labels and the proposed method is not very complicated.", "weaknesses": "1. The paper does not specify the kind of distribution shift under which the method works; causal shift, anticausal shift, covariate etc.. For example, there are distribution shifts where p_S(X)  = p_T(X), which, given good prediction, would mean small COT and COTT (because confidences are concentrated around the correct label). Could the authors explain how this may not be an issue? Better, could the authors evaluate the methods on a dataset like ColoredMNIST with a flipped spurious correlation between train and test.\n\n\n2. The writing could be improved by introducing COT and COTT before showing plots with them.\n\n3. I'm a little fuzzy on the intuition of which AC-MC does not work as well as COT. Is it that the confidence distribution becomes more diffuse with distribution shift and AC-MC does not scale with that \"diffusion\" because the pseudo-label distribution also depends on the confidence distribution, but COT being that it looks at the $p_T(Y)$, breaks that dependennce?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback and for the compliment that the experiments demonstrate clear advantages of our method, the presentation of the paper is clear, and we tackle an important problem of estimating OOD error without a complicated solution. We would like to address your questions and concerns as follows:\n\n### On Weakness 1\n\nWe thank the reviewer for this great point, and have added clarifications about the shift we studied in the updated version our paper. To clarify, we mainly experimented with covariate shift datasets. For cases where $P _{S} (X)$ = $P _T (X)$, this means we are essentially estimating the model’s performance on in-distribution data. Since we calibrate the model using temperature scaling on the in-distribution validation set, as mentioned in Section 4.2 of our paper, the confidence scores will be close to the in-distribution accuracy on average. As a result, the particular case brought up by the reviewer would not be an issue. \n\nPer the reviewer’s suggestion, we performed additional experiments on the ColorMNIST dataset. We found that COT/COTT provides consistently strong performance as well. Please refer to the PDF file attached to our global response for more detailed experimental results. \n\n### On Weakness 2\n\nWe thank the reviewer for this great suggestion! We have updated the paper accordingly.\n\n\n### On Weakness 3\n\nThe reviewer’s intuition on why AC-MC does not work as well as COT sounds mostly correct to us. Here is a more detailed elaboration on this intuition. Modern neural networks are well known to be overconfident and miscalibrated. While calibration methods such as temperature scaling help in the in-distribution setting, they fail miserably under distribution shift. See Ovidia et al. 2019 [1] for a comprehensive study. Now, AC-MC by definition only works when the calibration is good, which as we mentioned is a poor assumption in practice under OOD settings. This corresponds to the reviewer’s intuition where the confidence becomes “diffused” but not enough, due to overconfidence and failure of OOD calibration. By contrast, COT is able to adjust for these overconfident mispredictions using the assumed label distribution\n\nTo provide a more concrete example, a model might have 80% accuracy on in-distribution data and since it’s calibrated its average confidence (AC) is around 80%. Now, on the OOD data, it can have an accuracy of 50% but AC of 70% due to overconfidence. But if pseudo-label shift exists on this OOD data, which we empirically observed to be true in extensive experiments, COT will be able to leverage this information to provide a more accurate estimate of the performance. \n\n### References\n\n[1] Ovadia, Yaniv, et al. \"Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift.\" Advances in neural information processing systems 32 (2019)."}, {"review_id": "upDU9y1Fmj", "reviewer": "Reviewer_1ruP", "summary": "This paper proposed Confidence Optimal Transport (COT) and a variant, Confidence Optimal Transport with Thresholding (COTT) based on pseudo-label shift to characterize the error between predicted and true OOD label distribution. ", "questions": "1. I don't understand the assumption: \"the target label distribution is close to the source label distribution\" and think this assumption conflicts with the purpose of detecting OOD error --the test set should be assumed to behave differently from the training set and that's where the error come from. I wonder if authors could help clarify this assumption.\n2. Figure 2 and 3 do not seem clear to me, could authors elaborate more on the purpose of including types of corruption in the figure?", "limitations": "Yes, the authors have addressed their limitations.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The idea of using pseudo-label shift to characterize error is natural and straight-forward.\n2. Experiment results are reasonable.", "weaknesses": "1. This work does not have sufficient theoretical support for the method.\n2. I am not fully convinced that the main assumption of same source label distribution and target label distribution is reasonable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful feedback and for the recognition that our idea is natural and straightforward, and our experiment results are reasonable. We address concerns and questions below. \n\n### On Weakness 1\n\nPrevious works have established that no theoretical guarantee is possible for OOD error estimation on arbitrary distribution shifts (See section 3.1 in Garg et al. 2022 [1] ). Therefore, assumptions are essential to make progress on theoretical guarantees. We believe that one significance of this work is that we specify a specific assumption (no/mild label shift) that, when held true, makes our method more desirable than other methods. Most previous methods rely on the assumption that the model is well-calibrated. However, modern neural networks are well known to be overconfident and miscalibrated. While calibration methods such as temperature scaling help in the in-distribution setting, they fail miserably under distribution shift. See Ovidia et al. 2019 [2] for a comprehensive study. Under the no/mild label shift assumption, we additionally showed that COT provides provably more conservative estimates than AC, and established the relationship between COT and pseudo-label shift. We would appreciate it if the reviewer could elaborate on what their ideal theoretical support looks like so we could further discuss if such desired results are attainable. \n\n### On Weakness 2 and Question 1\n\nTo start with, we would like to clarify that we mainly focus on covariate shifts in this work. For example, different hospitals might use different stain colors for their pathology samples. This will have the effect that their images look very different, but their respective label marginals (distribution of classes of diseases) should be very similar. For another example, when a self-driving car operates on rainy days, the images it collects might be very different from ones from sunny days, but the occurrence of objects, for example, traffic lights, stop signs, etc should still be the same. We hope these examples help to clarify why the assumption that the source and label distributions are the same does not defeat the purpose of estimating OOD errors. Additionally, building upon our response regarding weakness 1, since some assumptions are required, we have chosen an assumption that is frequently satisfied, theoretically convenient to work with, and produces strong empirical results. We again thank the reviewer for raising this concern over our assumption. We have updated our paper to explicitly state the distribution shifts we aim to tackle.\n\n### On Question 2: \n\nWe thank the reviewer for pointing out their confusion over Figure 2 and 3 and have updated the captions for them to make it clear.  For Figures 2 and 3, we showed the corruption types and severities to provide readers with the specific distribution shifts we test on in CIFAR-10-C and CIFAR-100-C datasets.\n\n### References\n\n[1] Garg, S. and Balakrishnan, S., 2022. Leveraging Unlabeled Data to Predict Out-of-Distribution Performance. ICLR.\n\n[2] Ovadia, Yaniv, et al. \"Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift.\" Advances in neural information processing systems 32 (2019)."}, {"review_id": "CbwqTeOXZ0", "reviewer": "Reviewer_dn4Z", "summary": "Authors develop a methodology for estimating the accuracy of a classifier in the case where the distribution of the test set is different from the one used in the training data. Their methodology is based on computing a certain Wasserstein distance between suitable distributions on labels. Authors argue this definition is robust to pseudo label shift and validate their claims through extensive experimental validation.", "questions": "1)Proposition 2 is nice but it is unclear how such lower bound can be ever applied. In other words, the estimated error could be 1 always and the result is useless. Authors should elaborate more on the significance of this result.\n\n2)Similarly, Corollary 1 is helpful (line 189) but again, doesn't say the proposed method is always good. What AC got it just right while COT overestimates the error? The fact that there is a GAP between great experimental results and these somewhat weak theoretical results is a bit too bad and authors (although perhaps not here) should aim to clarify this.\n\n3)Authors may try to better explain the role of the Wasserstein infinity distance here. Is there anything special about this metric space that makes things work or it is just a mathematical convenience? The proofs are based on geometrical intuitions, but is there anything special about the Wasserstein geometry here?\n\n4) It would be great if the authors could elaborate more on why the Pseudo label shift is the right quantity to focus on.  By line 147 I am worried that the observed correlation showed in the experiments could be an artifact of the fact that the pseudo label shift is bounded by \\epsilon. How can this be ruled out?\n\n5) The definition of Pppseuudi in line 95 page 3 is awkward as it is not immediately clear whether it refers to domain X or Y.\n\n6) inline equation in line 188 page 5 seems wrong. Could you please correct?", "limitations": "n.a.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "StrengthsI think overall it is a good, strong paper. It addresses an important problem and it provides a highly innovative perspective on that problem. Experiments are compelling and make a strong point that the method is able to combat otherwise pervasive underestimation of error for of out of distribution samples.", "weaknesses": "The main weakness is the lack of sufficient clarity. The entire argument is subtle and required a super clear explanation. Unfortunately, the way the manuscript is written does not help much. Another weakness is that while this is promoted as an OT based method, the theoretical results (while seemingly correct) don’t enlighten much about what the role of Optimal transport is.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review and are encouraged to hear that our work was perceived as a good and strong contribution, providing a highly innovative perspective on the problem of OOD detection. Further, we appreciate the reviewer’s comment that our experiments are compelling in supporting our claims. In the following paragraphs, we will provide further clarifications on our method, which we have also incorporated into the updated version of our manuscript.\n\n### On Weakness:\n\nWe thank the reviewer for the advice to improve the writing of our paper to make our argument stronger. We have added more explanations and details to make our messages clearer. On role of OT, we think Figure 1 can provide some intuition. Essentially, using OT, our method can provide an error estimate that is aware of the assumed label distribution. From here, we proved formal guarantees of our estimation, i.e., COT provides provably more conservative estimates than AC, and COT is never lower than half the pseudo-label shift, which is the lower bound of true target error. We hope this gives a clearer picture of our work but welcome any follow-up questions.\n\n### On Question 1 and 2:\nThe reviewer insightfully pointed out the fact that both Corollary 1 and Proposition 2 are lower bounds of COT and there is no upper bound guarantee. These lower bounds are useful because NNs tend to be overconfident [1], resulting in overly optimistic performance estimates for existing confidence-based methods. Given this observation, lower bounds are actually more useful than upper bounds.  On the other hand, we believe upper bounds are difficult to obtain and require a much deeper theoretical understanding of issues like calibration. While more calibration methods have been proposed over the years, the reason why and when neural networks are miscalibrated is still not well understood [2]. \n\nWe admit that it is indeed possible for AC to be just right and COT to overestimate. However, we rarely observe this phenomenon empirically, because when the model makes a lot of mistakes, very low confidence is required to have a large overestimation of the correct set, but we know neural nets are more prone to be overconfident than not [1]. As a result, AC almost always underestimates the error. Thus, we think the two lower bounds of COT we proved are helpful in explaining the success of our methods on a large number of datasets. We hope this explanation helps clarify things but welcome any follow-up questions during the discussion period.  \n\n### On Question 3:\n\nRole of Wasserstein infinity distance: the reviewer’s observation is astute. The infinity norm is the most natural distance for AC-MC, which computes the maximum confidence in a confidence vector. This is precisely the definition of the infinity norm of a confidence vector. The infinity norm enables us to shine a new light on AC that is previously unexplored. Bringing AC into the abstract geometric framework allows us to obtain results previously unattainable: \n1. Understanding the well-known failure mode in AC-MC via projection optimality, an inherent geometric notion.\n2. Design COT and provide a guarantee that safeguards the method from similar issues. While similar results may be obtainable with enough effort through other perspectives, we believe our novel geometric insights are interesting to the community.\n\nAs a side note, it is a simple exercise to show that the L-1 norm and the L-infinity norm are equivalent to COT. However, the L-1 norm does not provide a unified perspective for AC-MC, which is why the L-infinity norm is important here.\n\n### On Question 4:\n\nThe reasons why we consider the pseudo-label shift are the following: \n- When source and target label marginals are the same, pseudo-label shift is the lower bound of the true error, because as we mentioned in Section 2.4, it is the Wasserstein distance between $P_{pseudo} (y)$ and $P_T (y)$, defined as the minimum transport cost over all transport maps between these two distributions. Meanwhile, the true error corresponds to a specific transport map: where the pseudo label of each sample is mapped to its true label, so that is why it is lower bounded by the pseudo-label shift.\n- Under the assumption that the target label distribution is close to the source one, pseudo-label shift is a quantity that we can actually estimate in practice, and this quantity provides us with additional information about the true target error.\n- It also has an intuitive triangular relationship with AC-MC and COT, as illustrated in Figure 1. Using the additional information about the target label distribution allows us to get a more accurate prediction when the model is miscalibrated, as we discussed in Sections 2.3 and 2.4.\n\nHow to Interpret the correlation between pseudo-label shift and AC-MC’s estimation error: \n- The reviewer is correct that the pseudo-label shift lower bounds the true error. Assuming reference to Figure 2, we would like to clarify that the y-axis is AC-MC’s estimation error instead of the true error. We hope this helps clarify things but if not, we welcome any follow-up questions during the discussion period. \n\n### On Question 5 and 6:\n\nWe thank the reviewer for their writing suggestions. The $\\vec{c}$ in line 188 should be $\\vec{y}$. We have incorporated them and corrected the typos in our paper. \n\n### References: \n\n[1] Ovadia, Yaniv, et al. \"Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift.\" Advances in neural information processing systems 32 (2019).\n\n[2] Wang, Cheng. \"Calibration in Deep Learning: A Survey of the State-of-the-Art.\" arXiv preprint arXiv:2308.01222 (2023).\n\n\n\n \n\n"}, {"review_id": "EpfsCtmfSP", "reviewer": "Reviewer_chpC", "summary": "In this work, the authors aim to predict model’s performance on out-of-distribution (OOD) data without access to labels during testing. Specifically, they identify pseudo-label shift, which gauges  the difference between the predicted and the true OOD label distributions, to indicate the under-estimation issue suffered by the existing methods. Based on the obervision, they propose Confidence Optimal Transport (COT) and an empirically-motivated variant of COT, Confidence Optimal Transport with Thresholding (COTT), for more robust OOD error estimation. Experiments are conducted on 10 datasets with various types of distribution shift to verify the effectiveness of the proposed method.", "questions": "See the weaknesses.", "limitations": "The author provides the limitations of their work. It would be better if the authors discuss more cases such as the two cases mentioned in the main review. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The motivation in this work is clear. The authors explain the under-estimation issue encountered by previous studies through the lens of pseudo-label drift, and propose a method leveraging optimal transport theory based on the observision.\n\n2. The code is available with the submission which improves the reproducibility index of the paper.", "weaknesses": "1. Since this paper contains many mathematical symbols, the meaning of some symbols is confused, which increases the difficulty of understanding. For example, in Section 2.1, you mention to predict the error $\\epsilon = 1-\\alpha$, but later the predicted error is denoted as $\\hat{\\epsilon}$. Comparing Figure 1 with Section 3.1, I find the assumption changes from $P_T(\\vec{y}) \\approx P_S(\\vec{y})$ to $P_T(\\vec{c}) \\approx P_S(\\vec{y})$. Is the meaning of $P_T(\\vec{y})$ equivalent to that of $P_T(\\vec{c})$? In addition, in Section 3.1, what is the meaning of $\\hat{P}_S(\\vec{y})$ and $\\hat{P}_T(\\vec{y})$? I suggest that the authors explain them after every equation and use harmonized symbols.\n\n2. The relationships between pseudo-label drift and the true target error is not clear. In Section 2.4, you briefly mention that the pseudo-label shift is a lower bound of the true target error of the model. Can you explain the property in details? Specifically, I prefer to know the relationships between your method (or miscalibration) and the true target error. Can you give some insights?\n\n3. This work is potentially vulnerable to two cases: 1) imbalanced test set.  2) The label space of the test set is only the subset of that of the training set. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable review of our work! In particular, we are excited that our motivation reads clear to the reviewer and our code submission alongside this contribution improves the reproducibility of our method. \n\n### On Weakness 1\n\nWe thank the reviewer for pointing out the confusion and will clarify them below. We have updated our paper to incorporate the suggestions and corrections suggested by the reviewer to make it more readable.\n- Regarding the notation for test error, we would like to clarify that ${\\epsilon}$ is the true test error (that is assumed to be inaccessible and must be estimated/predicted), while $\\hat{\\epsilon}$ is the predicted test error (given by an error estimation algorithm), as defined in line 84 of our paper. Our goal is to output $\\hat{\\epsilon}$ as close to ${\\epsilon}$ as possible. \n- The $\\vec{c}$ in line 188 should be $\\vec{y}$. \n- In Section 3.1, the hat notations denote the empirical distributions, that is the distributions over the finite samples.\n\n### On Weakness 2\n\nWe thank the reviewer for asking for more details and intuitions on pseudo-label shift. We provide a more detailed explanation below and have updated our paper correspondingly. \nPseudo label shift is the lower bound of the true error because as we mentioned in Section 2.4, it is the Wasserstein distance between $P_{pseudo} (y)$ and $P _T (y)$, defined as the minimum transport cost over all transport maps between these two distributions. Meanwhile, the true error corresponds to a specific transport map: where the pseudo label of each sample is mapped to its true label, so that is why it is lower bounded by the pseudo-label shift. For the relationship between our method and true target error, we would like to direct the reviewer to Proposition 2 (line 194) of our paper, where we established that the error estimate of COT is never smaller than half the pseudo-label shift, which is the lower bound of true target error. \n\n### On Weakness 3\n\nWe thank the reviewer for pointing out potential vulnerable cases and will address them below. We have incorporated the discussion on these two cases in our paper. \n- Imbalanced test set: Theoretically, our method is agnostic to different label distributions, assuming no/mild label shift between in-distribution and out-of-distribution label distributions. Empirically, We would like to note that RxRx1-WILDS, Amazon-WILDS, and CivilCom.-WILDS are all imbalanced datasets and COT/COTT provides competitive performance on these datasets. \n- The label space of the test set is only the subset of that of the training set: If a big fraction of the training set labels do not show up in the test set, this will cause a large label shift, which would lead our methods to overestimate the error. However, this setting is outside the scope of this paper as we currently consider no/mild label shift between in-distribution and out-of-distribution test sets. In the future, we plan to explore the use of Partial Optimal Transport for this more challenging setting.  \n"}]

Author rebuttal:
We would like to thank all reviewers for their time and effort in reviewing our work. We are glad that our work receives the following compliments from our reviewers:
- It shows “clear advantage of COT and COTT for predicting OOD error” (1Jqy) over “most other metrics that are sensitive to miscalibration” (HB65), and “provides some performance guarantee” (HB65).
- “The motivation in this work is clear” (chpC), “addresses an important problem and provides a highly innovative perspective” (dn4Z), “the idea of using pseudo-label shift to characterize error is natural and straight-forward” (1ruP), and “the proposed method is not very complicated” (1Jqy), "this manuscript is timely and important" (HB65).
- “The authors present impressive experiments” (HB65), “experiments results are reasonable” (1ruP), “experiments are compelling and make a strong point” (dn4Z),  “the code is available which improves the reproducibility” (chpC).

We have responded to all reviewer concerns and completed all the additional experiments that were requested. The attached PDF file contains experimental results for ColoredMNIST, per reviewer 1Jqy’s request. 


Meta-review: This paper offers a fresh perspective on addressing the OOD problem, specifically focusing on the pseudo-label shift. It presents a rigorous theoretical analysis accompanied by valid empirical results, garnering approval from all reviewers. However, some statements could benefit from further clarification for enhanced presentation. Overall, the AC is inclined to recommend acceptance.
Decision: Accept (poster)