Class Probability Matching with Calibrated Networks for Label Shift Adaption
Authors: Hongwei Wen
Annika Betken
Hanyuan Hang
Venue: ICLR 2024 poster (2024)
Keywords: Domain adaptation
Label shift
Matching methods
Primary area: transfer learning, meta learning, and lifelong learning

Abstract: We consider the domain adaptation problem in the context of label shift, where the label distributions  between source and target domain differ, but the conditional distributions of features given the label are the same. To solve the label shift adaption problem, we develop a novel matching framework named \textit{class probability matching} (\textit{CPM}). It is inspired by a new understanding of the source domain's class probability, as well as a specific relationship between class probability ratios and feature probability ratios between the source and target domains. CPM is able to maintain the same theoretical guarantee with the existing feature probability matching framework, while significantly improving the computational efficiency due to directly matching the probabilities of the label variable. Within the CPM framework, we propose an algorithm named \textit{class probability matching with calibrated networks} (\textit{CPMCN}) for target domain classification. From the theoretical perspective, we establish the generalization bound of the CPMCN method in order to explain the benefits of introducing calibrated networks. From the experimental perspective, real data comparisons show that CPMCN outperforms existing matching-based and EM-based algorithms.

Published as a conference paper at ICLR 2024
CLASS PROBABILITY MATCHING WITH CALIBRATED NETWORKS FOR LABEL SHIFT ADAPTATION
Hongwei Wen, Annika Betken & Hanyuan Hang
Faculty of Electrical Engineering, Mathematics and Computer Science
University of Twente Enschede, The Netherlands {h. wen, a betken, h. haggggae
ABSTRACT
We consider the domain adaptation problem in the context of label shift. where the label distributions between source and target domain differ, but the conditional distributions of features given the label are the same. To solve the label shift adap- tation problem, we develop a novel matching framework named class probability matching (CPM). It is inspired by a new understanding of the source domain's 's class probability, tios and feature probability ratios between the source and target domains. CPM is able maintain the same theoretical guarantees the existing feature probability matching framework, while significantly improving the computational efficiency due to directly matching the probabilities of the label variable. Within the CPM framework, we propose an algorithm named class probability matching with cal- ibrated networks (CPMCN) for target domain classification. From the theoretical perspective, we establish a generalization bound of the CPMCN method in order explain the benefits of introducing calibrated networks. From the experimen- tal perspective, real data comparisons show that CPMCN outperforms existing matching-baat -baed and EM-based algorithms.
well as a specific relationship between class probability ra-
INTRODUCTION
In classification problems, domain adaptation refers to the ability of an algorithm trained on source domain with distribution P successfully fulfill its task in a different, but related, target domain with distribution Q. As one of the most commonly used domain shift assumptions, label shift (Saerens et al. 2002, Storkey 2209) assumes that the class probability varies, i.e. p(y) * g(v), while the class- coss-conditional probability remains unchanged, i.e. p(xly)) ((<ly)) Domain adapta- tion under the label shift assumption has been utilized in a wide range of real-world applications. including disease diagnoses (Zhang et al. 2013 Tasche 2017), visual recognition (Martinez et al. 2017
Yang et al.) 2018) and relation extraction (Hong et al. 2022).
One paradigm solve the label shift adaptation problem matching methods. An example is Zhang et al. (2013). This article extends the kernel mean matching method from from/Gretton et al.) (2009) to label shift settings for estimating the class probability g(y), assigns weights for samples according to the class probability ratio ((y) ppy), and retrains a weighted classifier in the source domain that can be used in the target domain. More recently, network-based methods (Guo al. 2020) achieves high performance via training generative adversarial networks (GANs). These methods are based on feature probability matching on X. They come with strong theoretical guarantees for the solution, but suffer from huge computational costs. To reduce the computational complexity, researchers have sought to match the probabilities of the prediction Y instead of matching the probabilities of the feature X. To this end, Lipton al. (2018); Azizzadenesheli al. (2019) train classifier h on the source domain to obtain predicted labels y = h(x)) the target domain, and then match the estimated target class probability q(7). Recently, motivated by semiparametric models, Tian al. (2023) match the moment of a variable related the prediction 7. However, the cost of these methods is that the variable ÿ. on which the probability matching is conducted, suffers from prediction errors of the fitted classifier h.

---

Published as a conference paper at ICLR 2024
Another paradigm to address the label shift adaptation problem are EM-based algorithms. For in-
stance. Chan & Ng 2005) propose an EM-based algorithm inspired by Saerens et al. (2002) to
estimate (ly). A corresponding classifier then selects the class label with the maximal estimated probability (.). Furthermore, Storkey (2009) assumes a prior over p(y) and estimates (()) using Bayes' Rule, while Gretton et al. (2012) combine anti-causal learning with the label shift assump- tion to compute gly). However, for most of these methods, the use of intermediate variables like p(xly) or p(z). which themselves are difficult to estimate, hinders the estimation performance of the predictor q(yl (z). Their further development has been limited until Alexandari et al. (2020), which combines the calibrated neural networks (Platt 1999] Guo et al.) (017) and EM methods to estimate ((y) and (lylx)). As modern neural networks are no longer well-calibrated, calibration techniques are introduced to enable estimated conditional probabilities to accurately reflect the true likelihood of correctness (Guo et al. 2017). Experimentally, [Alexanarri et al. (2020) demonstrate that without calibration, EM-based algorithms perform worse than matching methods, while after calibration, EM-based algorithms can outperform matching methods, validating the effectiveness of calibrated networks in label shift adaptation problems.
In this paper, we propose a novel matching framework named class probability matching, which is based on matching the distributions of the label Y. Specifically, we provide new theoretical understanding on the source domain's class probability p(y), well specific relation between the class probability ratio q(v)/p()) and the feature probability ratio p(æ) under the label shift assumption. This results in a new matching framework of two probabilities on the label variable Y to get the class probability ratio. Accordingly, we propose novel algorithm named class probability matching with calibrated networks (CPMCN) for label shift adaptation. Our approach consists of estimating the class probability ratio with the use of calibrated neural networks and obtaining the classifier for the target domain. We provide rigorous theoretical guarantees for the solution of our novel class matching framework on Y, as well as the generalization bound of our proposed CPMCN to demonstrate the benefit of introducing a calibrated network. The proposed algorithm is not only computationally more efficient than the matching methods on the feature vector X, but also avoids introducing additional prediction error in contrast to matching methods predicting Y. The contributions of this paper are summarized as follows.
(i) To solve the label shift adaptation problem, we develop a novel matching framework named class probability matching that directly matches on the probabilities of label Y. Based on this framework we propose a new algorithm called CPMCN for label shift adaptation, which applies the calibrated neural network. CPMCN has low computational complexity and high theoretical guarantees.
(ii) Theoretically, we provide rigorous theoretical guarantees for our proposed matching framework. Moreover, we establish generalization bound for the CPMCN algorithm, which illustrates the benefit of incorporating a calibrated network in the algorithm.
(iii) Experimentallyy we validate that CPMCN outperforms existing matching methods and EM- based methods, in class probability ratio estimation and target domain classification.
2 PRELIMINARIES
2.1 DOMAIN ADAPTATION
In domain adaptation for classification, the input space X C RR and output space y = [K] (1. K} of both, source and target domain, are the same, but the distributions of source and target data, i.e. the corresponding probability distribution P and Q on X x V, differ. In domain adaptation, we observe labeled source domain data D, := {(X,, Yi).... (X,,, Yn,)) and unla- beled target domain data D2 := (X (X,,+h.....
n, +n,, Based these samples D == (Dp. D2),
our goal is to find a classifier Tog X + y for the target domain. It is well-known that the classifi- cation error of classifier h : X²' + y, i.e. the risk Q (h(X)= + Y). is minimzed by the naive Bayes classifier hg(xr) == arg max] ((v( ar). For this reason, we aim at finding an estimator @(y(x)) of (3y(2)) to get the plug-in classifier given by hy(x) == arg [ [yylz). In order to evaluate the quality of an estimator ([y]z), we employ the cross-entropy loss f(y, ((((x)) ;= log 7zy2z)) Then, the corresponding risk is given by (ū())=) ;= Sxxy Cly, q(- ()) dq(2z, (z. y) and the minimal risk is defined R2 == mingtyla) (Tvl(x)) The conditional probability (()](r)) is the optimal (or true) predictor which achieves the minimal risk with respect to l and Q, i.e. RS R.((((/))))
2

---

Published as a conference paper at ICLR 2024
-Bzw ExE(K] (k<{2)) log (k)z)). Moreover, use the notation On 2 b,, to denote that there exists constant 0 such that an c bn, for all n E N.
2.2 LABEL SHIFT
In this paper, we consider the label shift setting (Saerens et al. 2002
Storkey 2009).
Assumption 2.1 (Label shift), Let P and Q be two joint probability distributions defined on X x x).. Suppose that P has non-trivial class probabilities, i.e. p(y). E (0, 1). Vy [K]. We say that P and Q satisfy the label shift assumption if the class-conditional probabilities of P and Q are the same, whereas their class probabilities differ, i.e.
p(x/)) = ((<l)) and ply) + g(v)-
(I)
To better illustrate label shift, we provide a real-world example. Imagine that E X represents symptoms of disease and that the label y E y indicates whether person has been infected with the disease. Moreover, assume that the distributions and Q defined on X' x y correspond to the joint distribution of symptoms and infections in different hospitals, e.g. in different locations, that adopt distinct prevention and control measures so that the disease prevalence differs, i.c. p(y) + g(y). At the same time, it is reasonable to assume that the symptoms of the disease and the mechanism that symptoms caused by diseases are the same in both places, ie. p(zly) = g(xly). To make diagnostic model based data from one of the hospitals work in the other hospital it becomes therefore crucial to study label shift adaptation.
The goal of label shift adaptation is estimate g(ylxr) in the target domain. Estimating g(v (r) can be converted into estimating the class probability ratio w" == (w])vE(K] between q(v) and p(y), i.e.
" = ((v)/p(u),
E [K].
To be specific, given the label-shift assumption 2.1 (())x) can be expressed in terms of the true predictor p(ylar)) in the source domain and the class probability ratio w":
WTy p(ylæ)
<(y|>)
y E [K].
(3)
E wt pkk])))
For a detailed proof of Eq. (3) see Saerens et al. 2002); Alexandari et al. (2020) or Appendix A Note that the predictor ply (z) be learned by fitting calibrated ReLU network with softmax output layer on the labeled samples in the source domain. Thus, in order to estimate the optimal predictor ( (z) in the target domain, suffices to estimate the probability ratio w".
In addition to label shift adaptation, the label shift assumption also exists in long-tailed learning (Zhu al., 2023) and imbalanced sun--supereieed learning (Kim et al., 2020 Wei al., 202T). While these two problems often assume balanced class probability for test data, certain methods still require the estimation of the class probabilities for pre-trained data (Zhu et al., (023) or unlabeled training data (Kim et al., (020) to enhance the quality of pseudo-labels of data. Consequently, studying label shift adaptation can contribute to address the challenges these two problems.
CLASS PROBABILITY MATCHING FRAMEWORK
In this section, in order to estimate w², we introduce a novel matching framework named class probability matching that motivates the proposed algorithm for label shift adaptation in Section 4 Before we proceed, we first revisit the existing feature probability matching framework.
Revisit of feature probability matching methods. Many existing methods that aim at estimating
the ratio w' are based on matching two probability distributions of the feature variable X. To be specific, under the label shift assumption, it is shown in Zhang al. (2013); Garg et al. (2020) that the marginal probability g(z) has the following representation
K
K
(x)) Σ ((v))(al)) = wpp(y)((Zlv) = Σ wGplu)p(zlv--
(4)
3

---

Published as a conference paper at ICLR 2024
In order determine w", feature probability matching methods (Zhang al. 2013 2020 aim to find a weight vector wt := (WK)NE[K] such that
Guo et al.
(
Σ (gp(y)p(xly) y=1
(5)
holds. In other words, they get w" by matching q(x) with a weighted combination of p(rly). Theo- retically, Garg al. (2020) prove that w w² is the unique solution of Eq. (5) under the assumption
of linear independence of the set of distributions {p(r(y) y E [K]].
Unfortunately, existing methods that match probability distributions on X suffer from computational inefficiency. For example, the method proposed in Zhang et al. (203) suffers from the computa- tional complexity of O( Moreover, training GANs implicitly learn the distribution of X in Guo et al. 2020) is computationally extremely costly. Thus, in order to avoid the above problem, we develop a method that matches probability distributions of the label variable Y to get w". It is easy to see that the class probability p(y) is the only probability distribution of Y that can be estimated from the available data. Consequently, we investigate the method matching p(y) to get w".
A new class probability matching framework. By the law of total probability, we get represen- tation of the class probability p(y) as
p(u) = --// p(x)((())))))))))) p(z)p(ylz) dx dx= S. p(x) (())p(())) dz, y V [K], q(x)
(6)
ie. the class probability p(y) can written as a weighted integration with the marginal probability ratios p(æ)/ql (x)) of X the weight. Moreover, find that the marginal probability ratio p(v) (xx)) and the class probability ratios "y = g(v)/p(v)) E
[K]. are related. More precisely, under the
label shift assumption, the representation ((x) in Eq. together with Bayes formula yields p(x)
p(x) ((x) 2 wtp(y)p(aly) Σ (
(7)
From Eq. 7. we can see that under the label shift assumption, the marginal probability ratios p(x)//(x) of X can be parameterized by simple K-dimensional vector w" (wT))E(K)- By incorporating Eq. 77 into Eq. (6). we get
p(yla)
p(ylxr) x)) EmE[Ki wkp(klx)
ply) ER (k(())
((x) dx = Enng
E [K].
Therefore, new strategy to obtain w" is to find a weight vector : (Wk)Re(K) satisfying
p(ylx)
ply) Bawg
Eaag
Cke(K] WEp(kla) y E [K].
Note that in Eq. (8) we match two class probability distributions: the class probability p(y) and weighted expectation of p(y(z) with respect to the target distribution q(x). We therefore call the aforementioned strategy class probability matching (CPM).
Equivalence of class and feature probability matching frameworks. In contrast to matching two distributions of the d-dimensional feature vector X in Eq. (5) we match two distributions of the one-dimensional label Y variable in Eq. (8). Since the label Y only takes K discrete values, class probability matching only needs to match K equations, thereby allowing for reduction of the computational cost of CPM.
The following equivalence theorem provides the theoretical guarantee that the class probability matching framework on Y and the feature probability matching framework on X in Eq. (5) share the same weight solution under the label shift assumption.
Theorem 3.1 (Equivalence of Matching on X and Matching on Y). Let Assumption 2.1 hold.
Then the weight vector w := (wk)ke(K) satisfies the feature probability matching on X in Eq. 5 if and only if it satisfies the class probability matching on Y in Eq. {8)
Through the equivalence between the two matching frameworks, it becomes evident that the class probability ratio w w* is also the unique solution to Eq. (8) under mild assumptions. The class probability matching framework motivates an algorithm which will be introduced Section
4

---

Published as a conference paper at ICLR 2024
4 CLASS PROBABILITY MATCHING ALGORITHM
In this section, based on our proposed framework named class probability matching in Eq. (8) from Section B we present the empirical version of CPM and integrate calibrated networks to obtain an algorithm named Class Probability Matching with Calibrated Networks (CPMCN) for label shift adaptation. The proposed algorithm consists of two parts: the initial phase is to estimate the class probability ratio, while the second step is to obtain the corresponding classifier for the target domain.
Estimation of the Probability Ratio w". On the one hand, based on the source domain data, the left-hand side of Eq. can be estimated by
F(y)
7p Σ 1(Y =) y) y E [K],
where 1(Y; = y) denotes the indicator function which takes the value 1 if Y; y and the value otherwise.
On the other hand, with the aid of target domain samples Dÿ. the right-hand side of Eq. (8 can be approximated by "a" Ex,EDy (p(vl (olvlx../((EEet ()pp(k(X,))) In order to estimate the class membership probabilities p() of target domain data X; Dÿ in the source domain, we first fit calibrated network p(y]ar) with source data D, estimator of the predictor p(y]æ:). Note that we employ calibrated networks here because ordinary neural networks struggle to provide accurate estimates of class membership probabilities, even though they are good classifiers. We construct calibrated networks via bias-corrected temperature scaling (BCTS) (Alexandari et al., 2020). Specifically, let =(x) be the vector of the original softmax logits of the sample æ. BCTS introduces temperature scale 7 and bias vector b := (bs)kEjK] to get the calibrated predictor p(y|z) == exp(2(x)/T + (,)/(EkeIR exp(2(x)//T + bx)) for E [K], where T and b are both optimized with respect to the negative log- liglliiel on the validation data. Then by using the cal- ibrated network P(ylar) to predict the class membership probabilities p(y) for all target domain samples X; E Dÿ. the right-hand side of Eq. 8 can be estimated by
X.)
Σ PH (v) = T4 X.ED E (&P(H)X,)
y [K].
(10)
Since the probability ratio is solution of matching on Y in Eq. (8. w can be estimated by matching the estimates P(y) in Eq. (9) and P. (b) in Eq. (10p. In order to match p(y) and F (v), we have to find the solution @ to the following minimization problem
① = arg min WERK
p(u) - - (v)l²
(11)
which can be solved by the Broyden- Glodeee-
(BFGS) algorithm (Broyden 1970 with a computational complexity of )2) in each iteration. By definition of P3 in Eq. 10
there holds Eve(k) WyP, (v) = 1. Therefore, the weight @ that matches p(y) and P (v) is required Thus, for the solution @ Eq. (11) we take the normalized weight we/ (i (Eye(k) (yy) as the final estimation Tx. for all l E [K].
satisfy Σyenky Wh (ly)
Obtaining classifier for the target domain. Using the weighted predictor representation in Eq. (3. the calibrated network predictor p(y)ær), and the estimate w of the ratio w" in Eq. we are able to estimate (y)(z) in the target domain by
wyP(yla)
(12)
Σ 6,P()
Based on the estimator (2) in Eq.
12 we obtain the plug-in classifier
h (z) = arg max (gylz).
(13)
vE[K]
The above procedures for label shift adaptation are summarized in Algorithm
5

---

Published as a conference paper at ICLR 2024
Comparison with feature probability matching methods. CPMCN keeps the same theoretical guarantee for the weight solution as methods matching on X. but the computational complexity of CPMCN is much smaller: the computational complexity of Eq. (0) is (I,,K²) per iteration, but methods matching on X either require inversion of the Gram matrix which has a high computational complexity of ( or is computationally very intensive due to implicitly learning the distribution of X by GAN model.
Algorithm Class Probability Matching with Calibrated Networks (CPMCN)
Input: Source domain samples Dp == (X,, Y
Target domain samples D2 : (X:)
Compute the class probability p(y) from the source domain by Eq. (
Fit the calibrated networks ply) (x) with the source domain samples Dp. and make predictions
[() on target domain samples X; E Dū;
Compute the weighted combination of X.) to get Py (2) as in Eq. 100;
Solve the minimization problem in Eq. (TT to match p(y) and Pÿ (v) and obtain w;;
Compute the predictor (()(z) by Eq. 12) and the induced classifier hi by Eq. 13
Output: Predicted labels (hg (X:) finn+1 {))
of samples from the target domain.
Comparison with prediction probability matching methods. Matching methods on the prediction y first learn predictor in the source domain and then match the probability q(ū) of the prediction y = h(x). However, there exists an avoidable prediction error between the learned predictor and the true predictor h such that matching ((7) is not an accurate approximation of matching the probability q (((z)) of true prediction h(r). By contrast, p(y) can be easily estimated using the
labels of source domain data, which do not involve such prediction error of h and therefore matching p(y) yields a more accurate estimate of w"
5 THEORETICAL RESULTS
In this section, we present the theoretical results of the proposed class probability matching frame- work in Section 3 and the CPMCN algorithm for label shift adaptation in Section 4 Firstly, we prove that the true ratio w" is the unique solution of the CPM framework formulated in Eq. (8). which justifies the use of the solution T in the CPMCN algorithm to estimate w". Secondly, establish an upper bound for the estimation error of w and the generalization eтror bound for the classification performance of CPMCN, which aims to demonstrate the benefits of using calibrated networks in CPMCN.
Our theoretical results build upon the following assumption which is taken from Zhang al. 2013 Garg et al. (2020).
Assumption 5.1 (Linear Independence). Assume that the class conditional probabilities (p(zly) are linearly independent.
Remark 5.2. Assumption is is weaker than Assumption A.3 in Lipton et al. (0018) which assumes
that the confusiion matrix whose (i, jith entry is p(ū = i, j) is invertible.
The following theorem demonstrates existence and uniqueness of solution to the equation system Eq. (8). In particular, shows that the solution corresponds to the probability ratio w".
Theorem 5.3 (Identifiabilitty. Let Assumptions ratio w" be as in Eq. (2). Then the equation system Eq. (8) holds if and only if " ==.
2.7 and 5.7 hold. Moreover, let the probability
Theorem 5.3 justifies the use of the solution to the minimization problem in Eq. [1] to estimate w", since Eq. T is the empirical version of the system of equations Eq.
8 The next theorem
provides an upper bound on the estimation error of à for estimating w".
Theorem 5.4 (Weight Estimation Error Bound). Let Assumptions 2.7 and 5.1 hold. Moreover, denote the function set of calibrated networks as F. Then, with probability at least 1- 2/T 2/T ngg there holds
l w/ 11 S (juf R,()- + /VC(F) log "p/"t + 2 lll/ogg///g + 2 log nl nng
The upper bound of the estimation enror of w on the right-hane hand side of the above inequality consists of the upper bound of the bias term (first summand) and the variance term (last three summands).

---

Published as a conference paper at ICLR 2024
The following discussion indicates that the utilization of calibrated neural networks in CPMCN significantly reduces the bias term while keeping the variance term almost unchanged, thus reducing the class probability ratio estimation error ||00 1=
Reduction of the Bias Error. The bias error term measures the approximation ability of the neural network function the true p(y]zr). As stated in Alexandari et al. (2020). calibrated neural networks have significantly lower systematic bias and stronger approximation ability to p(ylæ)) Specifically, Alexandari et al. (2020) proposed a calibrated method called BCTS, which learns bias and scaling parameters by optimizing the negative log-likeldhood on a held-out training set to correct the proba- bility output of neural networks p(y)z)) Therefore, the utilization of calibrated networks in CPMCN significantly reduces the bias error term of the estimation error of W.
Negligible Increase in the Variance Error. The variance error term is dominated by the term that includes the VC dimension of the function set F of calibrated neural networks. [Barlettt et al. (2019) proved that the VC dimension of neural network set depends on the number of weights W and layers L. Compared with the commonly used networks, the calibrated networks used the CPMCN algorithm have added only one more layer consisting of K biases and K scaling parameters. As W and L are usually much larger than 2K and 1, respectively, the increase of the VC dimension calibrated networks compared to the original networks can be considered negligible. As result, the increase in the variance eтror term is negligible, as well.
Finally, we present the generalization bound of our algorithm in the target domain.
Theorem 5.5 (Generalization Bound). Let Assumptions 2.1 and 5. Moreover, let VC(F) be the VC dimension of the function set of calibrated neural networks J and let ((y)z)) be the estimator in Eq. 12 Then, with probability at least 1 - 2/np- - 22/ng. there holds
R. (Q((()))) - R2 -
inf R2(f) RR;) +3 33V/C((F) log mpp + 6 log + 6 log na/ /qq fEF
Compared to the error bound of the class probability ratio estimation in Theorem 5.4 the only slight differences in the generalization error bound in Theorem [.5 lie in the different constant coefficients in front of each term. As a result, similar discussions as above yield that the utilization of calibrated neural networks can improve the generalization performance of the CPMCN algorithm. All the proofs of the results presented in this section can be found in Appendix B
EXPERIMENTS
In this section, present experimental results on three benchmark datasets (MNIST LeCun et al. (2010), FFFAR10/Krizevee et al. (2009), and CIFAR Krizhevsky et al. (2009) to validate the effectiveness of the proposed CPMCN algorithm in comparison to existing matching and EM-based methods on label shift adaptation tasks.
Experimental Setups. Based on the original benchmark datasets, the data for the label shift setting are constructed as follows. We take the training set of the benchmark datasets as the data for the source domain Dp and reserve 10000 samples out of Dp as hold-out validation set, which is used to tune the hyper-parameters of the calibrated BCTS model (Alexandari et al., 2020). In order to generate the data for the target domain, Dg. we resample the original test set according to the label distribution (vy). By removing the labels, we obtain the unlabeled target domain data DW For repeating experiments of each method, we use the code from Geifman & EI- Yaniv/ (017) to train ten different network models with different random seeds. For each model, we perform 10 trials, where each trial consists of a different sampling of the validation set and a different sampling of the label-shifted target domain data. The total number of repetitions is 100. Types of Label Shifts. We consider the following two label shift cases. For Dirichlet shift, we generate the class probability q(v) by a Dirichlet distribution with parameters (az) satisfying oj = a for the first ten classes, i.e. for j E [10]. The class probabilities of the remaining classes are set to O. The label shift is more severe with smaller a. For tweak-one shift, we set the class probability of the fourth class as a parameter م and the probabilities qyy) of the remaining nine classes among the first ten classes are set to (1 p)/9. Meanwhile, the class probabilities of all remaining classes are set to We explore the Dirichlet shift with a E {0.1, 0.2, 0.8, 1.0, 10) and the tweak-one shift with p {0.01, 0.02, 0.05, 0.6, 0.8, 0.9).
Comparison Methods. We compare the CPMCN method with the following algorithms for label shift adaptation: the matching methods LTF (Guo et al. 2020), (Zhang et al.) (2013), BBSL (Lip- ton al. 2018). RIL.S (Azizzadenesheli et al. 2019), ELSA (Tian et al. 2023 and the maximum
7

---

Published as a conference paper at ICLR 2024
likelihood method EM (Alexandari al., 2020). The LTF method is feature probability match- ing method on X, rendering the calibrated networks inapplicable. For the remaining comparison algorithms, we employ the BCTS method for calibration. For all methods, the calibrated predictor P(ylz) is reweighted using the ratio estimation @ to determine the predictor ((y(z) in the target do-
main via Eq. (12) and plug-in classifier by Eq. (13). Details the implementation of all algorithms, including CPMCN, can be found in Appendix C.2
Evaluation Metries. We assess the efficacy of the algorithms by addressing the label shift adapta- tion problem from two perspectives. On the one hand, to measure the estimation error of the class probability ratio w", we employ two different metrics,
and MSE EROP, which means the original and weighted mean squared error between w" and its estimate w. respectively. On the other hand, the classification accuracy (ACC) in the target domain is used to directly assess the algo- rithms' performances. Note that better performance is indicated by smaller MSE_ _ROP,, MSE_EVEN EVEN, and larger ACC. Detailed information regarding the three metrics can be found in Appendix C.I
0.1
0.2
0.5
Metries
MSE_EVEN
PROP
ACC
MSE.EVER
MSE.PROP
ACC (%)
ESEN
MSE
ACC (%)
5.91es1
3.8464
63.30
7.73pe1
2.17e43
80.13
2.71eel
9.67e42
80.35
LTF
(1.05++1)
(1,29c-3)
(7.94)
(1,20c+1)
(1.03c43)
(1.63)
(8.01c+0)
(3.82c+2)
(2.86)
BBSL
1.70++0
5.02e+1
1.26c+0
2.64c+1
8,38e-1
I.le+1
89.98
(7.25s-1)
(3.91c+1)
(0.41)
(8,542+0)
(2,94c+1)
(0.40)
(1.02c+1)
(1.54c+1)
(0.36)
RLLS
1.12++0
4,94c+1
9.17e-1
2.37c+1
6.35e-1
1.88+1
90.50
(L.75<+0)
(1,47c+2)
(0.66)
(1.40>+0)
(1.17c+2)
(0.55)
(9.06e-1)
(6,36c+1)
(0.42)
ELSA
5.43++0
6.60l++1
4.24g+0
4,33c+1
2.76c+0
1.62++1
90.88
(1.08++1)
(1.14c+2)
(0,53)
(9 (9.90>+0)
(8,28c+1)
(0.56)
(7,25c+0)
(3.87c+1)
(0,50)
EM
2.31e-1
7,95c+0
1.82e-1
4.15c+0
1.32e-1
2.11e+0
91.30
(8.310-2)
(4,87c-0)
(0.33)
(3.31c-2)
(2,49c+0)
(0.29)
(2.46c-2)
(9.80c-1)
(0.25)
CPMCN
(7.91e-2)
1099-1
(4.74c-0)
(0.33)
(5.07e-2)
1.31e-1
(2.19c-0)
2.30c+0
(0.28)
(2.37e-2)
1.02e1
(9.55e-1)
1.53++0
92.00
(0.25)
0.8
Metries
EVEN
PROP
ACC (8)
MSE EVEN
MSE.
ACC (%)
ESELEVEN EVEN
PROP
PROP
ACC (%)
ITF
(3,30e+0)
1.13+11
(2.13e42)
2.18c+2
(1.14)
84,80
(4.76x+0)
1,20c+1
(1.6le42)
4,64c42
(1.55)
86.45
(3.29c+0)
5,95++0
(3.21e+1)
7,42c+1
(5.86)
83.02
BRSI.
8.480-1
1.07c+1
89.13
9,39c-1
1.lee1
88.72
6.19e-1
4,37c40
87.45
(9.67c+0)
(1.49c+1)
(0.35)
(8,20e=1)
(7.10c40)
(0.36)
(1.42++2)
(7.05e40)
(0.31)
RLIS
5.400-1
9443-00
89.70
5.72c-1
8.31++0
89.52
4,99e-1
4,41c40
87.50
(5,73c-1)
(3 1)288=11
(0.35)
(8.52e-1)
(3.25e+1)
(0.38)
(6.69e-2)
(8.97--1)
(0.14)
2,87c40
1.88++1
89.43
2.770+0
1.32c+1
89.85
1976+0
7,55cc0
87.98
ELSA
(4.61e+0)
(2,49c+1)
(0.37)
(2.840+0)
(1.15e+1)
(0.41)
(2,34e+1)
(2.13c40)
(0.43)
1,42--1
1,55c+0
90.73
1.11e1
1,35c40
90.40
1.53e-1
1,35c40
88.85
BM
(2.06e-2)
(7.21e-1)
(0.22)
(3.06e-2)
(9.69c-1)
(0.26)
(9.63-33
(1.15e-1)
(0.
CPMCN
(L.86-22
1.27-11
(6.67e-1)
1.43+40
(0.22)
91.28
(3.15e-2)
1.32e-1
(1.03e+0)
1.35e+0
(0.26)
90.80
(9.42c-3)
1.4e-1
(1.13e-1)
1,32+00
89.15
(0.13)
Table I: Performance on CIFARIO0 under Dirichlet shift. For each method, the first line corresponds to the median of the considered metrics among 100 repeating experiments. The second line is the standard deviation of these 100 values. The best results marked in bold.
provide the results of label shift adaptation tasks on the CIFAR 100 dataset of the above methods for two types of label shift scenarios and different label shift parameters a and p. Experimental results on the MNIST and CIFARIO datasets are presented in Tables 3 4 S and [ in Appendix C.3 For all datasets, especially for the
Experimental Results. Table I and Table 2 in Appendix C
CIFAR100 dataset, Table I shows that the proposed CPMCN method has the lowest estimation error with respect to the class probability ratio and the highest classification accuracy for different values of a, which shows that matching on Y outperforms the compared methods.
Training Curve. Figure presents the training curve of our CPMCN algorithm and the correspond- ing curve of MSE of class probability ratio estimation on CIFAR100 100 under the tweak-one shift with = 0.01. Both curves exhibit the same trend: as the number of iterations increases, the objective function and the ratio estimation error decrease almost zero. This empirical result validates the ef- fectiveness of the matching method on Y for estimating the ratio w". Furthermore, beyond a certain number of iterations, both criteria maintain their near-zero status.
The effect of the source domain predictor P(y(z)) on the performance. We investigate the impact of the quality of the network predictor p(y(z) trained in the source domain on the performance of [))(z) in the target domain. For this, we vary the number of training epochs for the network in the source domain and based on p(y|z) trained with different epochs, we compute the corresponding predictors (v)(r) in the target domain. Figure 2 presents the classification accuracy and cross- entropy loss of P(y(z) in the source domain and that of (ty|ar) in the target domain at different training epochs under tweak-one shift with p 0.01 on CIFAR 100. As can be seen from Figures
8

---

Published as a conference paper at ICLR 2024
Source Domain Targei Domain
dbyctow hunciion
Waan Squared Entor
Clnsunttuu Lovs
Accurscy
Crossertropp
Source Domain
Targut Domain
Number Earatins
T0. PM
Number Earations
Number Epochs
No Number of Epochs
250
Figure 1: Training curve of CPMCN and ratio estimation curve.
Figure 2:
Effect of the source domain's 's network predictor
the performance the target domain.
the better the network is trained in the source domain, the better the performance of CPMCN in the target domain. This validates the generalization bound of Theorem [.5
Importance of Calibration in CPMCN. To illustrate the role of calibration in CPMCN, we com- pare CPMCN without the calibrated model component (referred to as 'None") and CPMCN inte- grated with common calibration methods, including vector scaling (VS) (Guo et al. 2017), No Bias Vector Scaling (NBVS) (Alexandari et al. 2020), and BCTS. The comparison is conducted on the (IFAR100 dataset under the Dirichlet shift with parameter pared to the non-calibrated version, CPMCN combined with different calibration methods shows significant improvement both in ratio estimation and accuracy in the target domain, demonstrating the importance of calibration in CPMCN. This aligns with the theoretical explanation of the benefits from calibration in Section Furthermore, besides the BCTS used in this paper, VS and NBVS also perform well.
10. As shown in Figure 3 com-
MSE EVEN
MIE PROP
Moow
NEVS
BCT5
Nonz
V5
NEVS
BCTS
Mone
V5
NBVS
BCTS
Figure 3: Boxplots for CPMCN using calibration and various calibration techniques w.r.t. three different criteria. conducted under Dirichlet shift with a = 10 on CIFAR100.
Figure 4: Running time on CIFAR100 under the Dirichlet shift with 0.1.
Less Running Time than Feature Probability Matching Methods. Given that all compared meth- ods use pre-trained network predictors, the time spent on pre- pre-training is not included. We also in- clude the running time of the KMM method from Zhang et al. (2013) in Figure 4 although it does not produce any results even after running for over 10,000 seconds. Figure 4 shows that compared with the feature probability matching methods, KMM and LTF, the class probability matching method CPMCN solved by L-BFGS-B (Zhu et al.) 1997) has a significant computational advantage, which aligns with our complexity analysis. In addition, CPMCN's running time is comparable to and even faster than that of prediction matching methods including BBSL, RLLS, and EM- methods by using the same optimizer.
7 CONCLUSION
To address the label shift adaptation problem. we propose novel matching framework called class probability matching. CPM keeps the same theoretical guarantee as existing methods matching the distributions of the feature variable X, but is computationally more efficient due to directly match- ing the probability distribution of the label variable Y. Motivated by the CPM framework, we develop the CPMCN algorithm by utilizing calibrated neural networks for target domain classifi- cation. Theoretically, we establish CPMCN's generalization bound, highlighting the importance of incorporating calibrated networks. Experimentally, the CPMCN method performs better than other matching methods and EM-based algorithms. For future research, to extend the method to the relaxed label shift setting in Garg et al. (2023): Tachet des Combes et al. 2020), where there is concurrent shift in the class-conditional probability and the class probability.
research question would be

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The authors would like to express the sincere gratitude Tao Huang for his helpful discussions and suggestions throughout the experimental phase of this paper. His expertise and dedicated efforts significantly enhanced the quality and rigor our experiments.
REFERENCES
Amr Alexandari, Anshul Kundaje, and Avanti Shrikumar. Maximum likelihood with bias-corrected calibration is hard-to-beat at label shift adaptation. In Hal Daumé III and Aarti Singh (eds.), Pro- ceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 222-232, 2020.
Kamyar Azizzadenesheli, Anqi Liu, Fanny Yang, and Animashree Anandkumar. Regularized learn- ing for domain adaptation under label shifts. In International Conference Learning Represen- tations, 2019.
Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities Risk bounds and structural results. The Journal of Machine Learning Research, (NNov):463-482, 2002.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1) 1:,285-23011 2019.
Sergei N. Bernstein. The Theory of Probabilities. Gastehizdat Publishing House, Moscow, 1946.
Charles George Broyden. The convergence of class of double-rank minimization algorithms general considerations. IMA Journal of Applied Mathematics, 6(1):76-90, 1970.
Yee Seng Chan and Hwee Tou Ng. Word sense disambiguation with distribution estimation. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, pp. 1010-1015, 2005.
Felipe Cucker and Ding-Xuan Zhou, Learning Theory: An Approximation Theory Viewpoint. Cam- bridge University Press, 2007.
Saurabh Garg, Yifan Wu, Sivaraman Balakrishnan, and Zachary Lipton. A unified view of label shift estimation. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 3290-3300, 2020.
Saurabh Garg, Nick Erickson, James Sharpnack, Alex Smola, Sivaraman Balakrishnan, and Zachary Chase Lipton. Risbench: Domain adaptation under relaxed label shift. In International Conference Machine Learning, pp.
PMLR, 2023.
Yonatan Geifman and Ran El-Ya.iv. Selective classification for deep neural networks. In I. Guyon, U. Von Luxburg, S. Bengio, Wallach, R. Fergus, Vishwanathan, and R. Garnett (eds.), Proceedings of the 31st International Conference on Neural Information Processing Systems, volume 30, pp. 4885-4894 2017.
Arthur Gretton, Alex Smola. Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, and Bernhard Schölkopf. Covariate shift by kernel mean matching. Dataset Shift in Machine Learning, 3(4):5, 2009.
Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp- 1321-1330, 2017.
10

---

Published as a conference paper at ICLR 2024
Jiaxian Guo, Mingming Gong, Tongliang Liu, Kun Zhang, and Dacheng Tao. LTF: A label transfor- mation framework for correcting label shift. In Hal Daumé and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Ma- chine Learning Research, pp. 3843-3853, 2020.
Yu Hong, Zhixu Li, Jianfeng Qu, Jiaqing Liang, Yi Luo, Zhang, Yanghua Xiao, and Wei Wang- Can we have both fish and bear's 's paw? Improving performance, reliability, and both of them for relation extraction under label shift. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pp. 758-767, 2022.
Jachyung Kim, Youngbum Hur, Sejun Park, Eunho Yang, Sung Ju Hwang, and Jinwoo Shin. Dis- tribution aligning refinery of pscudo-label for imbalanced semi-supervised learning. Advances in neural information processing systems, 33:14567-14579, 2020.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 10 and cifar-100 datasets. Available: https://www.cc..oronttt edu/riizeifar.hnmm 2009.
Yann LeCun, Corinna Cortes, and Christopher J.C. Burges. MNIST handwritten digit database. Available:
2010.
Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3122-3130, 2018
Julieta Martinez, Rayat Hossain, Javier Romero, and James Little. A simple yet effective baseline for 3d human pose estimation. Proceedings of the IEEE International Conference on Computer Vision, pp. 2640-2649, 2017.
Pascal Massart. Concentration Inequalities and Model Selection, volume 1896 of Lecture Notes in Mathematics. Springer, Berlin, 2007.
Colin McDiarmid. On the method of bounded differences. Surveys in Combinatorics, 141(1):148- 188, 1989.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT press. 2018.
John A Nelder and Roger Mead. A simplex method for function minimization. journal, 7(4):308-313 313, 1965.
The computer
John Platt. Sequential minimal optimization: A fast algorithm for training support vector machines. 1998.
John Platt. Probabilistic outputs for support vector machines and comparisons to regularized likeli- hood methods. Advances in Large Margin Classifiers, 10(3):61-74, 1999.
Marco Saerens, Patrice Latinne, and Christine Decaestecker. Adjusting the outputs of a classifier to new priori probabilities: a simple procedure. Neural Computation, 14(1):21-41, 2002.
Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer Science & Business Media, 2008
Amos Storkey. When training and test sets are different: characterizing learning transfer. Dataset Shift in Machine Learning, 30:3-28, 2009.
Remi Tachet des Combes, Han Zhao, Yu- Yu-Xiang Wang. and Geoffrey J Gordon. Domain adaptation with conditional distribution matching and generalized label shift. Advances in Neural Informa- fion Processing Systems, 33: 13:19276-19288, 2020.
Dirk Tasche. Fisher consistency for prior probability shift. The Journal of Machine Learning Re- search, 18(1):3338-3333 3369,
2017. 2017.
11

---

Published as a conference paper at ICLR 2024
Qinglong Tian, Xin Zhang, and Jiwei Zhao. ELSA: Efficient label shift adaptation through the lens of semiparametric models. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 34120-34112. PMLR, 23-29 Jul 2023.
Chen Wei, Kihyuk Sohn, Clayton Mellina, Alan Yuille, and Fan Yang. Crest: A class- rebalancing self-training framework for imbalanced supervipee learning. In Proceedings of the IEFF/CVF conference on computer vision and pattern recognition, pp. 10857-10866, 2021.
Xue Yang, Hao Sun, Xian Sun, Menglong Yan, Zhi Guo, and Kun Fu. Position detection and direction prediction for oriitta ships via multitask rotation region convolutional neural network. JEEE Access, 6:50839-50849 2018.
Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 819-827, 2013.
Beier Zhu, Kaihua Tang, Qianru Sun, and Hanwang Zhang. Generalized logit adjustment: Calibrating fine-tuned models by removing label bias in foundation models. arXiv preprint arXiv:2310.08106 2023.
Ciyou Zhu, Richard Byrd, Peihuang Lu, and Jorge Nocedal. Algorithm 778: L-bfgs-b: Fortran subroutines for large-scale bound-constrained optimization. ACM Transactions mathematical software (TOMS), 5355):550,560, 1997.
12

---

and the law of total proba- Published as a conference paper at ICLR 2024
This supplementary material consists of supplementary for both theoretical analysis and experi- ments. In Section[A] we provide the proofs related to Section and Cantionm[ann] In Section the correspond-
ing proofs of Remark 5.2, Theorem 5.3 5.4 and 5.3 are shown in Section B.1 B B.3 and B.4
respectively. In Section C we provide the supplementary for experiments, including description of evaluation metrics and additional experimental results MNIST and CIFAR10 datasets.
A PROOFS RELATED TO SECTION 2 AND
For the sake of completeness, we provide the proof of Eq. 3
Proof of Eq. ( Using Bayes' Formula, the label shift Assumption 2.1 bility, we get
((y(x)) q(blu)q(y)
p(xl)))(V))
Σ k= (()l)))(())
Σ (k))
pla, y
k=1 ((el)))())g(()))))))))))
p(x, p(a,
(p(z,v)/p(z))u ()), Σ (k(
plyla)/y
Here, the third equality holds since the nominator is first multiplied and then divided by p(y) and and the terms in the denominator are first multiplied and then divided by p(k). And the fifth equality holds since the nominator and denominator are divided by the same p(z). This finishes the proof.
Proof of Theorem
3.1 EEq. 8
Eq. 5 Equation Eq. 8 together with Bayes' formula yields
plylær)
p(alu)p())/p(a) = Enzy Σラ=1 wypli)p(xl))
p(y)((xly)
p(y) Engn
w2p(jlæ) Exng Σ w=p(ali)(()/p(())
By Assumption 2.1 we have p(y) > O. Dividing both sides of the above equation by p(y), we get
p(ally
Jx E ()P()())))
p(zyy)
((x) dx / p(rlu) dr.
E Exng
(14)
Using the law of total probability and p(z(k) q(x))) k) for all le E [K] by Assumption 2.1 get
((z) Σ (k)g(=)))) Σ (k))p(z())
(15)
Plugging Eq. (15) into Eq.
14
we obtain
J p(zlv)
((()p(kkk)))) dx f p(al))) dx, 1 wxp(i)p(z1))
which is equivalent to
f p(aly) Σk - - dr 0.
(16)
Σ w,p(i)p(al))
Multiplying both sides of Eq. (6) by (a(v) w,)(()) and taking the summation from y 1 to K, we obtain
k= (q(k) - w.p(H)))(((k)
dx = 0.
E wyp(i)p(z1))
13

---

Published as a conference paper at ICLR 2024
By Assumption 2.1 we have p(z[k) ((<](k)) and thus
k= (g(k)) - w.D(H))((()1))
de = 0.
x
Since ΣØ= myp(i)g(a)) > 0, there must hold (x= (ap(k)) 0 and therefore,
we obtain > (k)g(<]k)) = Ex (xp(k)g(Z((k) Again, using the law of total probability and Assumption
we get
((x) Σ (k))g(=)))) = Σ (xp(())(((())
Σ
wap(H)(((kk),
REA X.
"Eq.
Eq.
8
Using Bayes' formula and Eq. 5p. we obtain
p(y(z)
p(zlv)p(o)/p(z)
p(y)p(xll)
E 1 ビ== ==1 wyp(ilæ)
E.
Baan
j=1 w)p(i)p(zl5)
p(y)p(aly)
((0) dr /
p(y)p(aly) Σラ= wyp(i)((a15)
war(k)p(alkk) dx
k プj= (pnl)((()(
k
J p ply),
y y [K],
which yields Eq.
8 and thus completes the proof.
B PROOFS RELATED TO SECTION 5
B. PROOF OF REMARK
Proof of Remark 5.2 Suppose that Assumption A.3 Lipton et al. (018)) holds, i.e., the expected
confusion matrix (h) == p(((r).)) y) is assumed to be invertible. By Assumption 2.1 we have p(zly) (x(l)). Therefore, we only need prove the linear independence of {p(x }yj])]]] ye[-]- To
K this end, we assume that there exist some weights (Wy)zE(K] such that Σ wyp(xly) = 0. Then for any i [K], we have
p(xly) dx f [1 ( uyx(h(X)= = :lyy) = "ly (b(2)=11
Σ wyp(aly) dx 0.
By definition, we have p(h(X))
ily) p(h(() w)/((y). Therefore,
p(h(X) =
Σ
wy
O, i [K].
ply)
y=1
With the notation p((()).)) = (x(T(x) = - ik the above K equations can be reformulated as
K
Σ
wy
-(f((x))v) = 0.
p(y)
Since the expected confusion matrix (i) p(h(2)) v) is assumed to be invertible, the vectors (p(h(x), y) y)]e are linear independent. Therefore, the coefficients wy/P(y) must be equal to zero, which implies Wy 's are all equal to zero. Thus, (p(xly)lve(k) are linear independent and (a(xly))ve[K) well. This finishes the proof.
14

---

Published as a conference paper at ICLR 2024
B.2 PROOF OF THEOREM 5.3
Proof of Theorem Suppose that the equation system Eq. (8) holds for some weight w
(Wy)gE[K] The equivalence of Eq. (8) and Eq. 5 in Theorem 3. together with Assumption 2.1 yields
K
g(x)
Σ
w (pp(o)p(Fly) = Σ Mop(y)g(zlv))
By Assumption 5.1 we get w wyp(y) = q(y) and thus wy
= w y E [K]. i.e., w w².
Plugging W w" into the right-hand side of Eq. (8) we obtain
p(y1z)
Exng p(zlu)p(u)/pp()
ply)p(xl))
E p
= Eany Σ w
j=1 ((j(ix)
p(v)p(al)) ((x) dr / p(u)p(xly) (z)) dx
q(x))
p(y)p(aly) de = p(u).
which proves the conclusion.
B.3 PROOF OF THEOREM 5.4
Before proceed, provide some basic notations. For 1 S co, the Top-norm of x (... defined as |æı| := +|a/|/+..+++1aa""""" P)1/P, and the Loc defined ||>||>> max;=1,...d /zy]. For any a, b E R, we denote A b == min [a, b} and vb: max 6] as the smaller and larger value of a and b, respectively. In addition, trained in the source domain as follows. Within the neural network space F, the empirical risk minimizer on source domain data Dp with respect to the cross-entropy loss is given by
define the network predictor p(y (x)
n2
F(yl)) = arg min (f( == arg min JEF
log(ff((X,))
(17)
JEF
np i=1
where == 05) are the mappings from X' to the (K 1---dmmension simplex A K-1 with fj X + [0, 1J. and fr( denoting the estimated probability of the label j given the input x.
With these preparations, we provide the proof sketch of Theorem 5.4 as follows.
Step 1: Prove the identifiablity of w". In other words, w" is the unique solution of population CPM (Theorem 5.3)
Step 2: Note that w is the solution of empirical CPM Eq. Prove how the difference between w and w² affected by the excess risk of the predictor P(yl (5) in the source domain (Proposition) B.
Step 3: Analyze the excess risk of the predictor P(ylær) by considering its approximation error inf JEF (J) - Ry and sample error related VC dimension of the network space F (Propo- sition B.6
In Step and 2, we use the label shift Assumption 2.1 and linear independence Assumption 5. which establishes linear independene of the class conditional probabilities (o(=//))y<[k We pro- vide the following example to illustrate Assumption 5.1 If, e.g. J encodes the symptoms a disease and y whether person is infected with that same disease (0 indicating healthy person and an infected person), dependence of (p(xly) ( means that, for all x. p(x = Ap(x+11. From this it easily follows that p(z(0) = p(x 1) and due to the label shift assumption (2x(0) = q(z 1), Le. it is impossible in source and target domain to distinguish healthy from infected persons through consideration of the alleged symptoms encoded in r.
To prove Theorem 5.4 we need the following Propositions B. and B.6 Proposition B.1 shows that the weight estimation error bound can be upper bounded with the aid of the excess risk of the predictor Pyy|ar) in the source domain.
15

---

Then with probability at Published as a conference paper at ICLR 2024
Proposition B.1. Let Assumptions 2.1 and 5.1 hold. Moreover, let the predictor p(y(z) be in Eq. 17
Then with probability at least 1/mp 1/ng. there holds
log fhg
log "p
1 - - Rp(((y)=)) R
+
np
To prove Proposition B. we need the following Lemmas B.2
B.3
B B,4
and B.5 Lemma B.2 was
introduced Bernstein 1946) and can be found many statistical learning textbooks, see e.g., Massart 2007); Cucker & Zhou 2007); (Steinwart & Christmann (2008).
Lemma B.2 (Bernstein's inequality). Let B > 0 and a > 0 be real numbers, and n 2 be be independent random variables satisfying Ep 0.
an inleger. Furthermore, let El,-.., En. .....,,. l1o I B, and Ep5? So² for all i 1,..., Then for all t > O, we have
P (
E
S
20
2BT
SET
3n
Lemma B.3. Let ply) be the estimate of the class probability Eq. 19) least 1 - L/p.. there holds
K p(u))
log lognp np
Σ ==1
ply)
72p
Proof of Lemma
B.3
For i [n] and l E [K], let the random variables &L, 1[Y, = -
Then we have Biik
0. || lloo I 1 and E p(k)(1 p(k)) S p(k). Applying Bernstein's 's
inequality in Lemma
B.
we get
Rp
(2p(k)T npp
2T
Sc
[K()) - p(+)] S
+ 3mp
np
with probability at least
2e 7.
Using the union bound and (a b)2 - 2(nn² + +
obtain
K
K
2p(k)T
2r
4p(k)T
47
((A) - p(k))2 ~
np
3np
np
On?
1=1
A=1
A=
with probability at least - -2K
Taking T = log(2 (2kk))))
we get
4 1og(22Knp)
4 4log2 (2KK))
log np
Σ
(() p(:)12
"p
9m3
11p
with probability at least 1/np. This proves the assertion.
The following lemma shows that the Le-distance between p(y(z) and p(y((z can be upper bounded by the excess risk of P(y) æ)) in the source domain.
Lemma B.4. Let p(ylx) be the estimator of plylz). Then for any y = I,..., K. we have
/ (plya() p(ul=))² do & (x((lxz)) R2.
Proof of Lemma B.4 For any E [K], there holds
(x(((x) -R E Exap p(ula:) 2()122)1
Exao Σ p(j(=)) log p()+z) [p(k| 22
K
(18)
p((z)
j=1
For any vector u == (u),.... ; E (0, (0,1)** we define
hu(w) : Σ pli log
u
luk p(k)2=)), k [K].
p(jxz)
16

---

Published as a conference paper at ICLR 2024
To find the minimum of hu) under the constraints function
R==1 uk
1, consider the Lagrange
Σ Uj 11) j=1
Ju(u)== hx)()) +a
with the multiplier a > 0. Taking the derivative w.r.t Uj. J = ,,... K, and setting them to be zero, L..
QJz(w)
p(((a))
2(ux p{][=)) + = O,
e [K],
(19)
Ouk
Uk
(Jx(u)
p(j(at)
+a = 0, j i k
(20)
du,
Uj
Since
and
Σラ= K
Uj 11 Eq.
(0
yields
1 - pk(p)) = > p(jl))) = Σ
auy = a(1 - ux).
E [K].
jzk
Therefore, we have a (1 pkkl==))/(1 -xx) Plugging this into Eq.
19 we get
pk](z))
2(ux - p(k(x=)) + p(kk xx)
O,
uk
which is equivalent to
(ua p(((==))(1 - 211e11 (1 - ux)) =0
ux uk)
and thus (ux p(k - 2ux(1 ux)) = O. Since us (0, 1). we have ux ux) S 1/4, which implies 2 uz) S. 1/2 < and thus 1 2u ux.) > O. Therefore, there must hold us - pkk[z)) = for any is E []] In other words, 7p the minimizer of hę for any h E [K]. As
result, we have ha (u) 2 (p((k()) = for any u E (0, 1)K satisfying ΣØ uj = 1. By taking
: p(ylz), we get
p(ilx) log p(j(z)
(x)l(())) ha (p(u)))))
[0(k())) - p(b(2)))2 -((k))) 2 O.
p(jaz)
This together with Eq. 18) yields the assertion.
Lemma B.5, Let Assumption 2.1 hold. Then with probability at least - 1/Ti. we have
K
noy + Tl
x,)
Enpny p(k(x))
12
log n4
+ (F(((()))) Ri:
ngg
1= w (()x)))))
Σx=1 w;P(i(z:
ng
K
p()))))
p(k((z))
log ng
-Eeng Σ kop((pz))
+ (f(((() - -R
Tg
=== (()))
1g
Proof of Lemma
B.5
First, we have
p(k(z)
Σ 1= w)
((())) Ejer - p(k|=)) (5
{ wpbl)(rr) < -
Ejee wi
17

---

Published as a conference paper at ICLR 2024
[0 p(k] Σラ w)D(i(z)
p(k]z) E jese w3 (0(l)))))-((11))
(21)
(Σzz) w))(i(z)) R
wyp(i(x)) (
Since for any ls [K], there exists constant 8 (0, (/K) such that p(k) 2 5 and g(k) 2 6, we
get (A) = 1 - -,f 9(1) 2 (K 1) and p(k) = 1- Ejth p(j) 2 1- - (K 1)6. Therefore
we have
6
g(k) pkk)
1 (K- -1)6
- (K 1)6 S w
8
c E (0, 6/ - (K - 1)6)]. Then for any x, we have K (yP(iaz)= 2 c and دس= wyp(jlz) 2 c. This together with the triangle inequality, a S (al a2)² and Σ at S ② ax)² for au 2 0 yields
Therefore, we can set wy E [c, 1/c] with a constant
Eq.
21
K
(())))
p(k)z)
((x) dz
w)P(i>>)
Σラ wyp(ilz)
jml
p(k)z)
p(k(z)
$
((x) dz
プラm K m [x)
Σラ ()p()(=)
[Pt]/a))) - p(k|2))]
) (EA= w) شラز (p )
p(k(a))))))))))(())) Ejjer wy -
2 ((xx)
dr
Σ/= wz)
[0(k)z) -(At))))((
2 +
(Ej= w (z)) E ) )ates de
p(k|z) E je wy 1e |p(llz))= -
22
E w,bb)x)))
2 K
[(k]z) - p({))) (()) do + ct JxZ Σ
K
(p(k)z)) Σ E0sll((lz) - F((+)))) ((x))))))))))))())))))))) dr
6 k=1
k=1
jth
$
2
Σ
K
[(k]()) - p(b))) dx + ct
/
K Σ
wylp(il)) )(ll))) ) g(x) de
x
2
K
[p(k)x) - (1))))(((()))) -(()))) dx +
2
J
Σ
K
1((1)) - -Golo)) 2
q(x) de
c
j=l
K
2
[0(k(z) - p(kl))) dr + Φ J
2K
(P(il))) F((L=))P) 7001))))0la ((1)) dr
K
((k]=) - (p g(z)) dr.
(22)
Using the law of total probability, we get
((x) Σ Ex (E11)99))
Ef Σ (<<())p())
K
9
1- - (K 1)6
<
p(x) EØ=1 p(al))(())
p()
This together with Eq.
(22) and Sauchy-Schwarz Inequality yields
K Σ
p(klz))
p(klz)
((xx) dx
1=1 wnp()
Σ - w,p(ipz)
1=1
2
l0lk (x) ((k))) dx 2 Σ [p(kl-) p(k)-))l?
K
Σ [lp()(/)))) - -1()))))1
(23)
18

---

Published as a conference paper at ICLR 2024
In addition, let
p(k (x)
Et,k =
E
ΣØ= K
w)P(i(x,)
Σj= wyp(j x))
Then we have EingSih 0,
1
+ +ENN
Σ w)P(ixx)
Σf= wj)(i(z)
K
K
-1
w/ E
+
Bang
A
wi Egli
S c
/=1
j=1
j=1
j=1
and
EDG
[(k(z))
1 (1- Egpny
((k()z)
Σド= 1)P(j(z)
Σ K
Σ wyD()(x)
E Eany (N w3 > p(5lz)
K
< Bong
S Exng
$
" w,
Applying Bernstein's 's inequality in Lemma
B.2 to Ei i E [my], we get
p()));)
(kk((z)) Lj=1 w)P()(z)
2Tc
4c
E
Exzn
S V
(24)
ng
f4
2j=1 j= ())())))))
K Taking :=
ng
3ng
with probability at least 7
= 2 log Mag we obtain
1 Blg
X()
((k(2z)
4c 1 log ng
8c 1 log ng
Egng E w;P(j(z)
R4 Σx K j-1 xx,
Rg
3n2
with probability at least 1 1/ng- Using (a + 6)2 2( 12), Eq.
24
and Eq.
23 we obtain
p(k(Xi)
p(k|=)
Enng
=j=1 w)p(i(x.)
ΣØ= Wyp(i ( (x)
i1
K
p(K)X;))
((k(z))
2
E E
Bg im 2i w;D(i(x,)
2j=1 w;D(ila))
k=1
K
[(k((2))
pkk(2)))
+ 2
E Egrn Σj= w)D(ixx))
Exng
EØ=1 Wyp(ji (z)
k=1
K
4c loog nig
Sc 'log ng
2
+
+
((k)=))12
n4
3ng
Am
km
log R4g
24
+ (fyl(()))) Riy:
ng
where the last inequality is due to Lemma B.4 obtain the assertion.
Applying this result to w = w and w == w", we
With the above lemmas, we are able to prove Proposition B.I
Proof of Proposition B.I. Using (a + 1 < 3( 6² + c2), Lemma B.5 and B.3 get
K
p(k(ar))
2
Exng Σソ 1,p(j(z)
-p(k)
19

---

Published as a conference paper at ICLR 2024
K
p(k(z)
1 By tu
12
<3
E 1
By
myp(j(z)
ng i
ΣS= HyPli|x (1))
k=1
1=1
K
2
K
+3 3
((K)
+ 337 Σ
((k) - p(k)
ng
2===1 ()p()(x))
Amm
i=
km
ng + (o(((()) RS. Σ
(()
2 [ikk
log Rpp
(25)
nl
ng xm
Lj=1 xX)
np
with probability at least - 1/1p- - 1/1 By Eq.
we get the optimality of T and thus
Thp +h
[(k((x))
2
T4 i= Ej=1 m,p(ilx,) (kk)
-(())
K
1g
Eド= w5N()x))
k=1
This together with (a b + c)2 S 3( + 132 + x22) yields
By
())
K
12 ((())
E ú xx) ((())
K Σ
fg i=
K
fg i=
2==1 wID()x,)
p(k(æ)
Banng
Bg +
2j=1 woD()Xx)
Σラー wzp(ikz)
A=1
p(k(z))
K
+
E Exay
p(k)
3
pp(k) - }(k)
Σラ= wz](j(z)
k=1
k=1
log Rg
+ log ng
(F(y(=))) Ri
(26)
ng
np
where the last inequality is due to Lemma B.5 and Theorem 5.3 we obtain
Combining Eq. 25
and Eq.
26
p(k (x)
log ng
log np
Exng
E
p(k)
z
+ (PlU((z -R +
(27)
1= 1- Ø)p(jlz)
>k
ng
np
with probability at least 1 - 1/1p- 1/ng- Using Bayes' Formula, the law of total probability and
Assumption 2.1 we get
p(y(
p(zlo)p(w)/p(x) E Eann p(y)a(aly)
E
K Σラ x)p(j(z) Bang Σ ((=p)))))))()))ooot
Σラ ((p())((z1) dr
-v(v) / x ΣØ (pp(i)p(al))
p(zly) ((x) dx = p(u) / p(xlv)
ΣØ ((1)g(z(5)
Σ wppli)p(a1))
de p(y) + +p(u) / ((xl1)) Ex=nlal)) - u6 (((())(() Σx (5p())(<11)
E (0)g(=15)
- -p(U)/ / ((0l1))
do E (,p()))(<1)
K (4()) m,,())) (((l))a(<()) dr
= =p(U)= p(v)
E (3(())(())) (wz 1.j) / p()pww)((a dr.
j=1
K
= =p(V)= > 1=1
Ex ((1)))()))))
Denote the matrix C == (Cw))USE(K) with
Cyj := I (()ppw))((())(((11)) dr Σx ((kk)
j= I....., K.
20

---

Published as a conference paper at ICLR 2024
Then we have
K
p
p(y) = Σ
Cey (w3 Wz).
(28)
(xp(k())
j=1
Now we prove that C is invertible by showing that the rows of C are linear independent. Assume that there exist .,,...., ax E R such that Σg ayCus = 0. j [K], which implies
K
Bry J plin de / Σg axpls))(Z()) Σ wap(k)q(z(k))
p())(()))) da.
y=1
y=1
Multiplying the above equation by aj and taking summation from j = 1 to K, we
get
0= aj Σ wap(k)a(z(k) (()g(z))) /
K
Σ (xplv)g(z())
( K
y= (xp()))(Z)y))
dr.
E (xp(k)g(((k))
1=1
This implies that Σnm anp(y)a(<(v)) = O. By Assumption 5.1
we get ayp(y) 0 and therefore Oy O. This proves that C is invertible. Denote the inverse matrix of C as M (m+z) Then Eq.
28
implies
K Σ
ply
K
p(y(a)
|ug-
mky
Bynng
p(U)
-
E Eang
plu)
2ー=1 wxp(i(z)
This together with (E==1
ax)
< K Σx K
k= of and Eq. 27
yields
K
K
K
p(y(xr
2 p(u) )
wP| 2
25
E
プラ wxp(ikz)
k=1
K
p(y(z)
p(N) )
2
K
Σ/= ;,p(j(z) - -p(s) )
p(y/x)
K
E Exng K
Exng
j-1 1pp(ilz))
1=
y=
p(y|z)
K
p(ylæ)
plu) 12
< KK)
Expoy ΣØ= @pp(ilz)
p())
E Bong K
ΣØ=1 17 x0)()1z)
1=1
y=1
log ng +
log nz
$ (o((vzz)) - Rí +
nly
n2p
with probability at least 1 - 1/ng- - 1/ny.
This finishes the proof.
Proposition B.6. Let plylz) be as in Eq. 1 and VC(F) be the VC dimension of the function set F. Then with probability at least 1/mpp, there holds
VC(F) log log np
log np
log ng ng
Ro,(((())) R2 S inf R₂) R2 JEF
+
Pp
1p
Proof of Proposition B.o By the triangle inequality and the optimality of p(ylx)).ie. i.. R,((()l)) s Ro) where fo E F satisfy (fo == fer (f),), we obtain
(o((((()) - R2 = - + + (Ro(fo) - RR((fo) + (R,(fo) R2)
R,,(fo)
< 2usp (f) - feF
(R,( - -R,)
= 2usp (R)()) - Rx(() + inl R,( - Ri: fef
JEF
21

---

Published as a conference paper at ICLR 2024
Let the calibrated neural networks E F satisfy fx( 8 with the constant 8 (0, ( for any x and y E [K] such that E(y, f(z)) = - log fz(2) is bounded. we replace one sample (X) with another sample (X,, Y,), the change in (R (f))
is not larger than - -log (- (o61116)) -6)) = log((1 - 8)/6). By applying McDiarmid's inequality McDiarmid 1989).
we get with probability least Npp
- - & Epn sup Rp(f) - (f( + log 1 JEF
log Rpp 2np
sup Rx(5) FEF
(29)
Define the function set (gr(x. v) log(f(())) f F} and its expected Rademacher complexity
Rad(G, n) = Dop Bg sup fEF n
1
Σ Exg(( vt).
By applying the symmetrization in Proposition 7.10 of Steinwart & Christmann 20088) we get
Ep sup (f) Rf) S (Rad(G feT
(30)
Since (x) > and [(y f())) Ely', ((''())))) s 1/81f(x) - f(x')), by using Theorem 12 in
Bartlett & Mendelson 20022, we get
Rad np) $ 1/6 Rad(F,1) mpp)
(31)
Moreover, by applying the techniques in Mohri al. (0018), get
2VC(F) log n2
Rad( [F, mp) S
"p
This together with Eq. (31). Eq. 30 and Eq. 29 yields
VC(F) log up
log up
log na ng
(F(ll=))) - R2 S inf (f) - R + fEF
np
Rp
with probability at least
1 1/np. This finishes the proof.
Proof of Theorem 5.4
Combining Proposition B.1 and
B.6
we get
VC(F) log up
log np
log np
log Tig
|1 w--w"l 10 < inf Rp(f) - RR, % +
+1
V
+
2
fEF
np
Pp
n2
ng
VC(F) log np
log n
log ng
inf R2 R2 fEt
+ 2
2
npp with probability at least 2/mpp - 2/ ny. This finishes the proof.
np
14g
B.4 PROOF OF THEOREM 5.5
Firstly, we present the error analysis of Theorem 5.5 define
To derive the excess risk of 7(yl2)) let us
(kkr))
(32)
Σ " (z)
Then able make the error decomposition for the excess risk of q(vlz) in Eq. 12)
(,v(l=) R <
(T((())) - R. (v())z)) + R. (ū())z) R
(33)
The following Propositions B.7 and B.9 provide the upper bound of these two terms in the right-hand
side of Eq. (33 respectively.
22

---

Published as a conference paper at ICLR 2024
Proposition B.7. Let Assumptions 2.1 hold. Moreover, let ((ylx)) and (yyxx) be defined as in
Eq. 12 and Eq. 32 respectively. Then we have
R2
- -R,
& R2(o(k(z)) - R2 + I|00 - 811
In order to prove Proposition B.7 we first prove the following Lemma B.8
Lemma B.8. For any a (a1,..., ag); I (I1, (II....,,H, TK) E IR K with Tg E (0, 1), & [K] K and Σk=1 ag = Ek=1 Iy = 1, les f(x) == - - ak log zk. Then for any x' = (d1.....,31 r'k))
with z/. E 1), & E [K], and > k= Tyz = L. we have
K
ak
ax(2k xxt) Fsl
lf(z) - f(x') -
Ib
xx(IKK A x²r,)
Proof of Lemma B.8 For any x (Zi,..., xx) (x' satisfying 2R. E (0,
E
[K], and) > Tk Ek= J = 1, there holds
/'" (vs(o + +[(=+((s'= ((dd'=)))) (s'-
(((z)))(()))
I'' Vs(x) (x' - z)dt + I'' -V( v)(x))) T (a' - x)dt
x)) < V+(x) - x) =)]+| + 111 (VS(=+ - x)) -((x))) (s' - x)dd (34)
For the first term in Eq. 34 there holds
Vf(z) V
a log IR
01
ak
I1
KKK
Since Σx=1 Ik= =k== 2/2
K
we then have
K
K
Vi(x)) (x)) =
Ok
(3'g
xak)
ax
(x/k x.k)
Fk
Ikk
:=
1=
ak
K
ag
x&
1ar
35
(35)
For the second term in Eq. 334
we have
V ff( + t(x' - -x)) -f))(((()) (a' - r)dt
ak
+
(x's Ix) dt
Ia 111/ xxx)
axllzi xz. )2
K
an (2's xz )2
dt
(36)
I& (ot + t(0/ - xR))
I xx A x.))
1=1
Combining Eq.
Eq. 335 and Eq. 36 we obtain the assertion.
Proof of Proposition B.7 Using the law of total probability and Assumption 2.1 any x su),(Px), there holds
we obtain that for
((x)
K ン Σx (+ (())
K < V J=1 p()
p(x) Ek
=
23

---

Published as a conference paper at ICLR 2024
This together with the definition of Ry implies
2k)zz)
[R,((())z)) R. (((((()) = Brong
2 (k|x)) log
q x))
K
@(k(2z)
S Bana
<(: (r) log
7(<|2z)
k=
(k)
K
<k([x) log ((k)z)
Exuu
(37)
pkk)
((k(z))
A=
Lemma B.8 with a g(/lz), x' = ((y/(r) and = (z) yields
(k((2)) log [(K(|z))
Expp
((A:(z))
[g(k(2z))
[1|1==)1 [0(k)=)) [k/p))
(k)x)) (() 21)=))
< Eapp
((k)z .r)
km
This together with Eq. 37
yields
RR (((Ul=))
Rg(((yl()))
K
g(k)
K
[a(k))z) [({|=)] 17(k))) - @(Ka [x))
- 7(1)2))
E
(38)
p(k)
@(k(2z))
x A ((k))))
k=1
Using the definition of T(vlx) and (ulax) as in Eq. 12 and Eq.
32
respectively, we then have
[x( - [(k[)) = (&P(k)))
W (kka)
Σ x,D(il>) ΣØ wfD(i(x)
Σ F(ilz) u2 - w( ((k())
Ejzn T))() ( K w)Dliz)))
f=1 > Th w + 1 w)
K
-
Σ 3=1
Iw3
(39)
Since for any & E [K], there exists constant 8 E (0, 1/K) such that p(k) > and ((k) 2 6, we
have y(b) = 1 Σ j q()) 2 (K 1)6 and pkk) = Σ Σjzn p(j) (K 1)6. Therefore,
we have
((k)
(K 1)88
S _
p(k) < 8
- (K 1)6
Therefore, we can set W/y E [c, 1/c] with a constant C E (0, (0,8/(1 - (K 1)6)]. Moreover, we have (k(x)
(c2u))
7(k())))))))))))()))))) = Σラ ((jb)
2 k (/
<7(())) 2 (kkp))
(40)
and
w (k(z)
wib(k(a)
7(k[z)
(41)
j w w3](i(z)
V w
Plugging Eq. (40 and Eq.
(41
into Eq. (38
we obtain
R2 (((ylz)) R2 ((yll))
< K
(k) Egpop
(k(k(z))
(())))))))))) 22
k=1 p(k)
(kkaz
((k))) A ((k)))
24

---

Published as a conference paper at ICLR 2024
K
(k)
K
(k(k(z))
[(klz)) [[(kaa)) - [(K((z) -((k))
((kx)) (7(k)))) - )()(2))
p(k)
// Vi= w3
k=1
((k)
[kkl2=)) -
(kkx) [0(k(r)) - 2
B
p(k)
w/ V 1= wj
(k)) j=1 )
k=1
la x) [(k)))] 17(k)))))))))))))))))))))))) - ((H)))) -
- [k1)2))
(42)
(k(())
]()]2))
Using the triangle inequality, we get
(k "[p(k(r)
[](k|=) - [[k[<=]]=
= Σラー wfD(ilz) wz
w شزك w
(2)
3 - +xbbb)))))))) p(il=)))
- p((p)(/)++++(((11
(1 w3)²
K
[p(]))) - p(j|z)).
(43)
j=1
Moreover, we have
wxp(k(x) Ajn mjj
(k|rz)
S p(k(t)).
(44)
Σラ j=ز w
Combining Eq. 42 Eq. 39
Eq.
43 and Eq. (44). and using the Cauchy- Sanchy-Schwarzznnee inequality we
obtain
(Qyl)))) - R. (Q,[((((=))
K
E, [0]]=)) - p()(z))) (p(k)x) E, Iwg - ū,
((k()) E, lw3 - -0,,1 1
$ E Expp
((k())))
k=1
K
K
K
S Expp
[(jk>) - (((1)1))
Σ
lw3 -3:1
+
Jwj - w7g
1=1
1=1
j=l
K Σ
2 (0(1))) )
K
K
<
Expp
Σ
|w3 - أرنت
+
133 وو
j=1
==1
K
Exap
(P()z)) - p((l)o))
+
Σ
|u - رون
j=1
Exmul [0(]x)) p() + Iw3- のū, 12)
R2 (p(k))) - R7, + ||0 3
where the last inequality follows from Lemma B This finishes the proof.
Proposition B.9. Let Assumptions 2.7 hold. Moreover, let Tz)xx and p(ylar) be in Eq. Eq. 17. respectively. Then we have
32 and
Rg(((()))) R S (P(((=))) R
To prove Proposition B.9 need the following basic lemma.
25

---

Published as a conference paper at ICLR 2024
Lemma B.10. For any ko E [K]. let ak by
0. Ck.
(0,1) satisfy
Σ Ck
and
Ex= Ik = 1. Then we have
Ck/ Cx/(E/= K agc))
K
C&Ck
log
Cp log
T&/ [-)=1 ayz:))
Ik
Proof of Lemma B.10
Let the function h: (0, + E be defined by
h(z)= == h(21,...,, IK)
K
CRCh
/k/ [i K djtzz) Cx /x/[E/ m5Cz)
Cx xxx (=x))=
+ > Σ Ik 1) Rm
log
+ c₁ log
k=
j=1 Oj
j==
where A 0 is the Lagrange multiplier. Then it suffices prove that h(x) 2 h((c) for any satisfying Σ Iy = and < xj < 1. E [K]. Taking the partial derivative of h(x) w.r.t. In
and setting to be zero, i.e.
0h(x)
CgCh
K
C2C₁
0g
Ck +x= 0,
== 1=....., K, (45)
Ork
V==1a aj
2b
t=1 j=l aj
Σ} 0j3b
K
which is equivalent to
Σ Li=1aaes ΣØ= azTs
-1)
ajes
+ Xx = 0,
h: == 1,..., ...... K.
k j=1
V 03
Taking the summation from k = 1 to K and using Σx1
T2. >k
= 1, we get
K
Ex age
C&Ck
+ += =0
V/=1a,
aj
which implies x = 1. This together with Eq. (45) yields
K = 0. k= I....... K. (46)
11
ax
)
Ck
ag
+
J=1 ag)
TR
J=1
If Σ ajcj # こ== ajæj, then there must exist some l E [K] such that at # De. Since
= 2==1 Σド = 1, there exist some i,j E [K] such that e > Hg and Cj < Iy. Without loss of generality, we assume that Σ/= agej > Σ5= ayæy. Therefore, we have both 1 - c/ < and - afeg ΣK ajæ, < 0. Thus we have
1 (1-V ai
V V= aj )
(1-
Gi Iy
0; j= aj
1 Σx ag9 <0 Σラ ajozj.
which contradicts with Eq. (46) for = Therefore, we have Ex=1 ajtz = Enn ررية which together with Eq. 46) implics C2 = ag for any &o E [K]. Thus h(x)) attains its minimum at the point Σ 2 = 1, i.e., h(z) 2 h(c) 0 holds for any x with E Ij and xj 10 for any j E [K], which finishes the proof.
x = (ci...., Cx) under the constraint k=
Proof of Proposition B.9 Using the law of total probability and Assumption 2.1 any x supp(Px). there holds
we obtain that for
((x)
= ((13))a)))
K
K < V J=1 p()
(())
(47)
p(x)
26

---

Published as a conference paper at ICLR 2024
Therefore, have
K (k(x) log [k([X)
R2(((ul))) -R, = Ex mi
(k) p(k)
(A(
Exup
[({[X) log
(48)
Using the definitions of 7(y2z) ) in Eq. 32 respectively, and Lemma B.10 with og == q(K)/p(k)
by = (1 (1k)) ca p and I& p(k{2)), we obtain
( log [k][X)
K
(g(+)/)(+))p(kI))
(=ll(()/p())PC log (Q(H)/(()))P())))))))
((k)/((k)
(g(4)/D(H))p((k))) log
k=1
((k)p(k)
Vi (k)/((k)) (a00///tt)0tu/122222000000000100
V
Vi q(k)/p(k)
[k][z) log p(k]z)
A (kk)/(())
K
p(k(l)))
This together with Eq. 488 yields
(T(l)) R.y - (V (b))/p(b))
(Ro(F(ulz)) - R2) s (x(((()>)) Ri
A (kk)/p(k))
which proves the assertion.
With these preparation, give the proof of Theorem
5.5
Proof of Theorem 5.5
Combining Eq. 33 Propositions
B.7
B.9 and B.6
we obtain
R2 (T(()) - R. S 2(Rp R2)
+ I|w"
i
log ng +
log up
$ ((p - R,,) +
np
VC(F) log fp
log ng
log ng
log fg
log ng
<3 inf Rx( R2
+
+
+
+
Up
np
nh
mgg
T2p
VC(F) F log Up
log ntp
2 log my
FEF <3 inf Rp( Rí
+ +
Up
np
rhg
with probability at least 2/np- 22/ng. This finishes the proof.
C SUPPLEMENTARIES FOR EXPERIMENTS
C.1 EVALUATION METRICS
We consider the following three metrics for the evaluations of label shift adaptation problems. To be specific, the first one ACC the classification accuracy in the target domain. The other two metrics, MSE PROP and MSE EVEN, are used to measure the estimation error of t for estimating the class probability ratio w².
(i) ACC is the accuracy of domain--dapted model predictions in the target domain. Mathematically speaking, ACC equals 1. 1
ny 2i= 1(hg(X,) Y.). where [y thy are the true labels of D
27

---

Published as a conference paper at ICLR 2024
(ii) MSE_PROP is the mean squared error weighted by the test set proportion q(k) and calculated by taking the weighted average the squared differences between the estimated weight wy and true weights w Le. Σx ((k)((( - wt)?
(iit) MSE EVEN is the mean squared error with equal weight and calculated by taking the uniform average of the squared differences between the estimated and true weights, i.e., k Σx (0g wx) where the number of classes is denoted by K.
Note that larger ACC and smaller MSE PROP and MSE EVEN indicate better performance.
C.2 IMPLEMENTATION DETAILS OF ALL ALGORITIMMS
The implementation of the CPMCN algorithm is divided into three parts:
Training the network on the first 50,000 training points of the source domain data. The training code and parameters can be found in the eetaaining.rredcttiio folder at https::/github. com/ kundajelaal htt htt.aelessh.ttteeereeeettrrrreee
The MNIST, CIFAR1O, and CIFARI00 folders corrspond to the networks for the respective datasets. We use the codes and hyperparameter values from the above github repository to train the network.
master/noteboooks wtg.eiiiiiinnenenciiiiiiiooooo
We utilize correct the output of the network, resulting in the calibrated ral network. The calibrated method Bias-Corrected Temperature Scaling (BCTS) is implemented based on the code in hhtps: com/ /ttp//kunnaaaaab/////a labstent iereentoooooooeeeooem http://////..eeeeeaaatatat//aaaa
It is invoked us- ing the TempScall ling (bias www.pppsiissss.eee all') method. The last 10,000 data points in the training set are used as validation set to train the calibration parameters of BCTS.
Based on the calibrated neural network, follow Algorithm I to obtain the target domain's classifier. For some target samples X;, the denominator Σk W&P(( [c]] X,) Eq. (10) may be close to zero, leading to the computational issue in calculating P (v)- Conversely, we observe that WyyPg (v) = " E Ei Wyp[yl (illu(x)))) /)) (xP(A|X,)) falls within the range of O to 1. Fortunately, it is easy to see that w" is also the solution of wyP(y) = Wypg (v). Therefore, to address the computational issue, we introduce Σye(x] [w,P(y)
""P""(")" (v) as the objective function with respect to w. We optimize the function by using a variant of sequential minimal optimization (Platt 1998) combined with Nelder-Mead method (Nelder & Mead 1965).
To implement the compared methods BBSL, RLLS and EM, we use the code in https: steper www.eiepeeeeee...e iments provided by Alexandari al. 2020). For the compared method ELSA, we implement it in Python and use L-BFGS-B (Zhu al. 1997) as the optimization method with the solution of BBSL its initial value.
//qithub. http//uunaajaaaaaaaa
C.3 ADDITIONAL RESULTS ON THE CIFAR 100, MNIST AND CIFAR DATASETS
28

---

Published as a conference paper at ICLR 2024
P
Metries
MSE EVEN
MSE PROP
ACC
MSB EVEN
MSE PROP
ACC(8))
MSE EVEN
MSE PROP
ACC (%)
841eet
8.40e+1
84.45
4,93ee0
5.2e+1
85,20
5.1e+D
5,26e+
85:25
LTF
(9.12c+))
(8.51e+1)
(3,38)
(6.23e+0)
(6.81e+1)
(3.04)
(3,43++0)
(3.64e+1)
(1.06)
5.61e:1
3,93e-0
89.15
5.56e:1
3.79c+0
88.75
5,56e-1
3.65e40
88.25
BBSL
(1.95e+2)
(9.12-00)
(0.33)
(2.07e+2)
(9.04c+0)
(0.33)
(2.18e+2)
(8.77040)
(0.32)
4.26e-1
3,56e+U
89.45
4.17e:1
3,30e+0
89.15
4.21e:1
3.15e+0
88.35
RLLS
(4.75e-2)
(4.91e.1)
(0.14)
(4.00e-2)
(4.74c.1)
(0.14)
(4.27e-2)
(4.24e.1)
(0.14)
1900+0
6.8c-00
89.85
1.82+00
7.11c40
89.40
I 182e+0
6.74c40
88.65
ELSA
(7.51e+0)
(1.50e+0)
(0.28)
(6. (6.32e+0)
(1.42e+0)
(0.27)
(5.52e+0)
(1.32e+0)
(0.27)
EM
L176-1
9.32c-1
90.60
1:23e-1
9.30c-1
90.23
1.260-1
9.76e-1
89.65
(9.63e-3)
(9.08e-2)
(0.12)
(9.39e.3)
(8.11e2)
(0.12)
(8.74e-)
(7.92e-2)
(0.12)
CPMCN
Like-1
8.06e-1
90.85
L.0e-1
8.69e-1
90.50
1.99-1
8.65e-1
90.00
(9.77ex3)
19119-2)
(0.12)
(9.35e.3)
(8.76e-2)
(0.11)
(8.53e-3)
(7.57e-2)
(0.12)
0.6
0.8
0.9
Metrics
USE_EVEN
MSE.PROP
ACC (92)
ASE_EVEN
PROP
ACC (9%)
MSE_EVEN
MSE.PROP
(R)
LTF
(8.97e+0)
4.41e+1
(2.06e+2)
144c+3
(2.21)
72.32
(6.27e+0)
5.07e+1
(3.38e+2)
3,53c+3
(0.80)
69.50
(4.77e+0)
5,78c+1
(3.80e+2)
4,86c43
66.30
(1.57)
2.26xe0
3,56e+1
85.15
3.62e+0
8.48c+1
85.20
4.44c+0
1,25e+2
85.93
BBSL
(4.31e+1)
(1.56e+1)
(0.35)
(2.86e+1)
(3.62e+1)
(0.46)
(1.56e+1)
(5.21e+1)
(0.49)
RLLS
5.09600
2.44422
83.40
9.71e40
6,45e42
83005
1,22el1
9.32e42
83.40
(1.40++0)
(8.32e+1)
(0.49)
(2.68e+0)
(2.14c+2)
(0.67)
(3,42++0)
(3.06e+2)
(0.75)
ELSA
6.23e40
5,58e11
85.18
1.0lesl
1.19e42
84.68
1,25611
180042
85.20
(9,05e+0)
(3.69e+1)
(0.65)
(1.40++))
(8.99+1))
(0.93)
(1.72e+1)
(1.28e+2)
(0.99)
EM
(7.70e-2)
6.86-1
(3.37e-0)
2,99es1
(0.25)
87.75
(1.20e-1)
L07oe0
(6.96c+0)
5.53e11
89.90
(0.29)
(1.38e.1)
1.21640
(9.09c+0)
7,09e41
91
(0.32)
CPMCN
6.56-1
2.82e41
87.98
Li7cs00
5.70ce1
90.30
LiMesl
6.02e41
92.18
(7.83e-2)
(3.45e+0)
(0.25)
(1.22e-1)
(6.97e+0)
(0.31)
(1.50e-1)
(9.63e+1)
(0.32)
Table 2: Performance on CIFARI00 under the Tweak-one shift. For each method, the first line is the median of the corresponding metries among 100 repeating experiments and the second line is the standard deviation these 100 metrics. The best results are marked in bold.
0.1
Metries
ESE.EVEN
PROP
ACC (%)
ESE_EVEN
MRE.PROP
ACC (%)
ESENEVEN
PROP
ACC (%)
LTF
(1,25e-2)
3.27e-2 9.47e-2
(8.20e-2)
(0.46)
97.70
(7,29c-3)
3.72e-2
(3.97c-2)
1.43e-1
(0.39)
96.30
(4.98c-3)
1.94e-2
(1.33c-2)
3,38e-2
(0.39)
93.63
BBSL
4.13e-3
8.96e-3
97.50
3.54e-3
7.60e-3
95.75
2.83e-3
4,43e-3
94.03
(6.34e
(3.99e:3)
(0.15)
(S.34e-4
(3.10e:3)
(0.16)
(2,20e-4)
(6.52e-4)
(0.15)
RLLS
3.990-3
9.33e-3
97.50
3.61e-3
7,926-3
95.75
2.83e-3
4,43e-3
93.97
(6.35e-4)
(4.01e:)
(0.15)
(5.36e-4)
(3.11e:3)
(0.16)
(2.19e:4
(6.47e-4
(0.15)
ELSA
8.81e:2
1.04e-1
96.05
2.0le-1
1.43e-1
93.85
2,226.1
1.86e-1
91.78
(4.40e+2)
(4.08e+3)
(2,29)
(5.77e+3)
(6.45e+3)
(1.32)
(1.98e11)
(5.23e+0)
(0.74)
BM
8.49e44
2.14e:3
97.35
La3ee3
2.09e.3
95.88
1,25e.3
2.le..3
91.88
(1.34e 4)
(6.44e.4)
(0.15)
(2.41e-4)
(9.74e-4)
(0.17)
(1.65e-)
(5.44e-4)
(0.16)
CPMCN
8.42-4
2.14e.3
97.35
L.3e-3
2.11e:3
93.88
1,268-3
2.04e:3
91.88
(L.3e-4)
(6.38e.4)
(0.15)
(2.41e-))
49.74e44
(0.17)
(1.64e4)
(5.43e-4)
(0.16)
0.8
1.0
10
Metrics
MSE.EVEN
MSE_PROP
(CC
EVEN
MSE.PROP
ACC (%)
EVELEVEN
MSE_PROP (S)
LTF
1.93e-2
2.96e 2
93.47
2.10e
2.91e-2
92.73
9.94e
9.62e 3
91.70
(4.29e-3)
(1.11e2)
(0.34)
(6.38e-3)
(2.05e-2)
(0.27)
(1,37e-3)
(1.20l-3)
(0.08)
BBSL
1.00e
2.75e.3
91200
2.28e
3.03e33
93.20
1.68e
L69e:3
91.70
(2.02-44)
(6.07e-4)
(0.13)
(1.65e-4)
(4.71e-4
(1.33e4)
(1.23e-4)
(0.07)
RLLS
1500-3
2.76e.3
91.20
2.268
3.le3
93.20
1.88
L69c33
91.70
(2.02e-4)
(6.07e4)
(0.13)
(1.65e-4)
(4.69c-4
(1.33e4)
(1.23e-4)
(0.07)
ELSA
6,76e
2.90
91.23
1.98
161e:1
91.88
2.00l:
1.88e
91.53
(4.02++1)
(1.18e11)
(3.84++0)
(5.94e-1)
(0.34)
(6.91e-3)
(7.676-3)
(0.07)
EM
L46e33
2.10e.3
93.25
1
2.49p.3
93.20
1.57ed3
1.7le3
91.73
(1.25e-4)
(2.68e-4)
(0.13)
(1.18e-4)
(2.62e-4)
(1.12e4)
(1,33c-4)
(0.07)
CPMCN
136e33
2.07e.3
93.25
Lo4ed
2.51e
93.20
1.56e33
1.7le3
91.73
(1.25e-4)
(2.69e-4)
(0.13)
(1.18e44
(2.62e4)
(0.12)
(1.12c4)
(1.32-4)
(0.07)
Table 3: Performance on MNIST under the Dirichlet shift. For each method. the first line is the median of the corresponding metries among 100 repeating experiments and the second line the standard derivation of these 100 metries. The best results are marked as bold.
29

---

Published as a conference paper at ICLR 2024
P
0.01
Metrics
MSE EVEN
MSE PROP
ACC
MSB EVEN
MSE PROP
ACC (%6)
MSE EVEN
MSE PROP
ACC (9))
8.08e.2
7.68e
91.35
5.76e
4.81e-2
91.90
3,32e-2
3.43e
91.70
LTF
(8.83--3)
(9.68-33
(0,16)
(4.97e-3)
(5.14e-3)
(0.16)
(4.88e3)
(5.18c-3)
(0.12)
1.58e-3
L66e:3
92.05
1.5ee33
1.38e-3
91.98
1.6le-3
1.65e
91.73
BBSL
(9.36--5)
(101ec4)
(0,06)
(8.96-55)
(9.64e-5)
(0.06)
(8.38e-5)
(8.76e-5)
(0.06)
RLLS
1.58e-3
166e
92.05
1.54p:3
1.58e.3
91.98
1.6le:3
1.65e
91.73
(9.36--5)
(1.1e-44)
(0.06)
(8.66--5)
(9.44--5
(0.06)
(8.38:55
(8.76e-5)
(0.06)
ELSA
2.450-3
2.69--3
92.00
2.29c-3
2.48c-3
91.95
2.59c-3
2.09e-3
91.75
(8.93e-3)
(221ee3)
(0.07)
(4.66c
(5.08e-4)
(0.06)
(4.40e-4)
(4.64e.4)
(0.06)
EM
(9.58e-5)
LS3e-3
(1.05e-4)
L64e-3
(0.05)
92:00
(9.18e-5)
1.50e3
(1.0c-4)
1.56e-3
(0.06)
91.3
(9.99e-5)
1.34p-3
(9.53e:5)
1.Mle-3
(0.06)
91.73
CPMCN
LS3e-3
L64e-3
92:00
1.1e-3
1.56e-3
91.33
1,33e-3
L.lle33
91.73
(9.56e-5)
(1.05e-4)
(0.05)
59.15e-5)
(9,98e-5)
(0.06)
(9.66e-5)
(9.51e:5)
(0.06)
0.6
0.8
0.9
Metrics
EVEN
MSE.PROP
ACC (%)
MSE_EVEN
MSE.
ACC (S)
ESELEVEN
MSE.PROP
(9)
2.34e-2
7.97e-2
93.53
3.09e-2
1.97e1
95,50
3.44e-2
1.8c-1
96.85
LTF
(3.70e-3)
(1.43e.2)
(0.15)
(4.09e.3)
(2.22e-2)
(0.10)
(5.28e.3)
(3.6le:2)
(0.08)
BBSL
3,89c-1
7.45e.3
93.58
6.45e-3
1.29e-2
95.35
6,23e-3
1.81e22
96.18
(5.56e 4)
(2.49e.3)
(0.06)
(8.25e
(5.15e.3)
(0.07)
(8.69e 4)
(7.40e-3)
(0.06)
RLLS
(5.56e 4)
3.99-1
(2.49e.3)
7.45e33
(0.06)
93.38
(8.14e
6.48333
(5.05e.3)
1.296-2
(0.07)
95.35
(7.82e
6.03e-3
(6.57e-3)
1.78e-2
(0.07)
96.35
ELSA
1988-1
2.68e-3
93.38
1876-3
3,74e-3
95.55
7.276-3
7.00e-3
96.43
(3.26e
(1.53e.3)
(0.06)
(1.66e33
(8.13e.3)
(0.08)
(1.70e+2)
(1.13e+2)
(0.13)
EM
(1.44e
(7.49e-4)
1.72e.3
(0.06)
93365
(8.46e 5)
8.64-44
(5.68c-4)
1.52e43
95.60
(0.05)
(4.77e-5)
5.9164
(3.54c-4)
1,396-
97.00
(0.04)
CPMCN
1.00a3
1.78-3
93365
8.58e-4
1.57e33
95.60
5.97644
1.43e-3
97.00
(1.44e-4)
(7.51e-4)
(0.06)
(8.45e-5)
(5.67e-4)
(0.05)
(4.78e.5)
(3.55e-1) 4)
(0.04)
Table 4: Performance MNIST under the tweak-one shift. For each method, the first line is the median of the corresponding metries among 100 repeating experiments and the second line the standard derivation of these 100 metrics. The best results are marked as bold.
0 Metries
0.1
ESE.EVEN
PROP
ACC (%)
MSE_EVEN
MRE.PROP
ACC (8)
ESENEVEN
MRPP
ACC (%)
LTF
(2.662-3)
6,280-3
(4,91c-3)
9.24e-3
(0.57)
97.65
(1.90e22)
1.26e-2
(6.05c-2)
1.58e-2
(1.49)
94.75
(9.48c-3)
3.38e-2
(2.49c-2)
4,06e-2
(1,04)
92.55
BBSL
2.88e-3
8.60e-3
97.60
2,80e-3
6.57e-3
96.12
2.40e-3
3.68e-3
93.75
(1.82e-3)
(1.54e-2)
(0.20)
(5.47e-4)
(2,94e:3)
(0.20)
(8.78e-)
(4.44e-3)
(0.17)
RLLS
2.840-3
8.23e-3
97.58
2.82e-3
6.53e-3
96.17
2.44e-3
3,66e-3
93.75
(1.53e-3)
(1,25e:2)
(0.20)
(5.36e-4)
(2,90e:3)
(0.20)
(8.76e4)
(4.44e-3)
(0.17)
ELSA
4.02e-1
5.85e-1
95.60
1,58e-1
1.34e-1
94.52
1.876-1
1.52e-1
93.08
(2.74e+2)
(2.08e+2)
(1.68)
(9.67e+1)
(2.17e+1)
(1.09)
(1,26e-1)
(3.29e-1)
(0.42)
BM
An8e-4
1.36e-3
97.70
9.29e:4
2.15e-3
96.18
1.3763
2.11e:3
93.00
(3.35e-4)
(1.73e:3)
(0.20)
(3.02e-4)
(1.30e-3)
(0.20)
(1.77e-4
(5.71e-4)
(0.17)
CPMCN
1.3e.3
97.70
9.28e-4
2.16e-3
96.18
1.376.3
2.10ee3
93.00
(3.32e
(1.71e.3)
(0.20)
(3.01e-4)
(1.30e
(0.20)
(1.77e-4
(5.69c-4)
(0.17)
0.8
1.0
10
Metrics
MSE.EVEN
MSE_PROP
(C)
EVEN
MSE.PROP
ACC (%)
EVEN
MRE_PROP (9)
LTF
3.59e
3.09e 2
92.85
3.40e
6.23e
91.65
1.58e
1.6e 2
90.73
(8.44-3)
(1.69-2)
(1.15)
(9.3e-4)
(1.36e-2)
(0.75)
(4.80e4)
(1.56e-3)
(0.02)
BBSL
2.35e-3
2.93e
91.95
1.71e3
2.58e
91.00
1.76e
1.76e
90.80
(5.75e-4)
(2.76e-3)
(0.16)
(3.09e-4)
(9.77e-4
(0.16)
(1.51e-4
(1.74c4)
(0.09)
RLLS
(5.66e-4)
2.35e-3
(2.74e-3)
3
(0.16)
93000
(3.08e-4
1899
(9.69c44
2.50e
91.00
(1.51e44
1.768-3
(1.74c4)
1.76e
90.80
(0.09)
ELSA
6.77-2
2
91.23
1.7e
1.58e-1
91
2.376:2
2.176
90.75
(8:30e22)
(1.90-11
(0.45)
(8.17e-2)
(181e-1)
(0.29)
(7.18e-3)
(8.04e-)
(0.09)
EM
143e33
2.01ex3
93.18
1226
1,52633
92.98
L61e3
L68e-3
90.85
(2.32e-4)
(8.18e-4)
(0.16)
(1.53e-4)
(4.45c-4)
(1.45e-4)
(1.65e4)
(0.09)
CPMCN
143e33
2.01ex3
93.18
1.5ee3
1.5ee3
92.98
161e3
1.68-33
90LKS
(2.32e-4)
(8.17e-4)
(0.16)
(1.53e-4)
(4.45c-4
(0.16)
(1.45e-4)
(1.65e44
(0.09)
Table 5: Performance CIFARIO under the Dirichlet shift. For each method, the first line is the median of the corresponding metries among 100 repeating experiments and the second line the standard derivation of these 100 metries. The best results are marked as bold.
30

---

Published as a conference paper at ICLR 2024
P
Metries
MSE EVEN
MSE PROP
ACC
MSE EVEN
MSE PROP
ACC (98)
MSE EVEN
MSE PROP
ACC (8)
LIF
3.3e:2
2.45e
91.35
3.1se
2.39e
91.50
2,40e
2.25e
90.33
(4.69e-3
(5.04e-3)
(0.25)
(5.63e-3)
(4.92e-3)
(0.33)
(8.41e3)
(9.36e-3)
(0.72)
BBSL
1.3e:3
1.50
9265
1.55e
1.32e
1.47e
1.42e-3
91.63
(1,02c4)
(9.74-55)
(0.06)
(1.12e-4)
(9.63e-5)
(0.06)
(1.05e-)
(9.44e-5)
(0.06)
1.3e:3
1.50e
92.65
1.55
1.52e:3
1.47e:3
1.42e-3
91.63
RLLS
(9.94e55)
(9.57e:5)
(0.06)
(1.12e-4)
(9.63e-5)
(0.06)
(1.05e4)
(9.44e-5)
(0,06)
ELSA
(6.32e-3)
2.6e:3
(1.42e-3)
3.16e:3
(0.06)
92.65
(4.19e-4)
2.89e
(4.56e-4)
2.75e:3
(0.06)
(4.10e-4
2.56
(4.29c-4)
2.76e:3
(0.06)
91.35
L.2ed
1.lee33
92.70
Lale3
L.3e:3
1.4c.3
1,44e:3
91.63
RM
(8.50e-5)
(8.98e-5)
(0.06)
(8.34e-5)
(8.5ee55
(0.06)
(7.99.-5)
(7,86e-5)
(0.06)
1.32ed
1.3le33
92.70
1ale3
1.4e:33
1.44c33
1.43e
91.63
CPMCN
(8.49--5)
(8.97e-5)
(0.06)
(8.33e-5)
(8.54e-5)
(0.06)
(7.99.-5)
(7.86e-5)
(0,06)
0.6
0.8
0.9
Metries
MSE EVEN
MSE PROP
ACC
MSE EVEN
MSE
ACC
MSE EVEN
MSE
4.13e:3
3.1ee3
91.99
3.18e:
1.23e-2
94.67
4.71e:3
2.21e
96.65
LTT
(1,36e-3)
(1.37e-3)
(9.57c-3)
(1.45e-3)
(5.736-3)
6.33e:3
1.9222
9130
1.12e22
4,30e:2
94.22
1.19e22
6.126
96.23
BBSL.
(1.15e-3)
(5.79e-3)
(2.06c-3)
(1.41e-2)
(2.41e-3)
(1.82-2)
RLLS
(1.15e-3)
6.33e:3
(5.79e-3)
1.92222
90.00
(2.06e-3)
1.12e22
(1.40c-2)
4,30e:2
94.22
(2.41e-3)
1.18e:2
(1.82c2)
3.706
96.20
ELSA
2:24e:3
(1.59e-3)
4.13e.3
91.00
(1.55e-3)
1.29ex3
(4.06e-3)
3.31e:3
94.72
(2.44e-3)
1.29e3
(1.176-2)
5.29e:3
96.35
EM
(3.57-44
2.12e.3
(1.66e-3)
3.63e:3
91.90
(2.97e-4)
1.99:33
(1.74e.3)
6.42e:3
94.75
(2.43e
1.25e:3
(1.44c-3)
4.92e33
96.65
(0.05)
CPMCN
2.12e-3
3.62e:3
91.90
6.36e:3
94.75
124e-3
4.976:3
96.65
(3.57-4)
(1.66e-3)
(0.06)
(2.97e-4)
(1.74e-3)
(0.06)
(2.44c-4)
(1.44e-3)
(0.06)
Table 6: Performance on CIFARIO under the tweak-one shift. For each method, the first line is the median of the corresponding metries among 100 repeating experiments and the second line is the standard derivation of these 100 metrics. The best results are marked as bold.
31


Reviews:
[{"review_id": "qZzGyIDygN", "reviewer": "Reviewer_PKvz", "summary": "This paper introduces a solution for the label shift adaptation problem: a matching framework called \"Class Probability Matching\" (CPM). CPM offers the same theoretical guarantees as the previous framework (feature probability matching framework) and addresses the issue of its low computational efficiency. Inspired by the CPM framework, the authors further develop the CPMCN algorithm, utilizing calibrated neural networks for classification in the target domain, and demonstrate the benefits of calibrated neural networks from the theoretical perspective. In experiments, CPMCN outperforms other matching methods as well as EM-based algorithms.", "questions": "1. Could the authors provide a brief explanation of the calibrated network mentioned in the paper?\n2. Why do the experiments in the 'Performance on MNIST under the tweak-one shift' have so many identical results? Even the standard deviation is the same for the accuracy metric at  \\ro=0.02.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Paper is well written and easy to follow;\n2. The authors compare, analyze, and make improvements to existing frameworks, and these improvements are well-founded; \n3. The proposed method is simple but effective.", "weaknesses": "1. The authors emphasize that the proposed algorithm has made significant improvements in terms of computational efficiency, reducing the computational complexity from O(n_p^3) to O(n_qK^2)  . However, no related experimental evidence has been provided to support this\nclaim;\n2. While this paper is the first to estimate marginal probability ratios from a class probabilistic perspective, such methods have already been explored extensively in the long-tailed domain, especially in approaches like logit adjustment, as seen in prior works such as the one in [1]. I\nbelieve it is essential for the authors to conduct some research and comparisons in this regard;\n3. Previous studies [2] have already demonstrated that calibration can indeed enhance performance, so the calibrated network mentioned in the paper is not very novel.\n\n[1] Generalized Logit Adjustment: Calibrating Fine-tuned Models by Removing Label Bias in Foundation Models. // Main Track, Conference on Neural Information Processing Systems. NeurIPS 2023.\n[2] Alexandari A, Kundaje A, Shrikumar A. Maximum likelihood with bias-corrected calibration is hard-to-beat at label shift adaptation[C]//International Conference on Machine Learning. PMLR,\n2020: 222-232.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PUEdfa0DoQ", "reviewer": "Reviewer_t6VC", "summary": "The paper presents a method which addresses the label shift problem. For dealing with label shift, it rewrites the target class probability as a tractable function with unknown parameters, averaged over the target feature distribution. The parameters are optimized by the BFGS algorithm and serve as weights to construct prediction scores on a target domain. The important condition is that the underlying classifier should be calibrated.", "questions": "The method currently doesn’t allow for a minibatch training; I’m wondering whether the authors thought about adapting the algorithm to handle minibatching?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "While the idea somewhat resembles the probability matching framework, it considers the problem from a different angle of matching class probabilities. The paper is well written and easy to follow. It contains necessary theoretical grounding and experiments which show method’s superiority over the baselines. The method has an advantage in terms of the runtime complexity, and demonstrates better accuracy results.", "weaknesses": "1. While the computational complexity is considered as one of the main advantages of the method, the paper is missing some experimental studies on the runtime. At what point (target domain size) the method becomes computationally prohibitive? How does that compare empirically with the other methods?\n2. A minor comment on writing: introducing “Calibrated networks” as a part of the method might suggest that there is some novelty in designing a proper mechanism of calibration for the label shift scenario. In fact, calibrated networks are used off the shelf as a necessary ingredient of the method to improve the estimation of p(y|x).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eRkF6PE50R", "reviewer": "Reviewer_Y2x9", "summary": "This paper studies the domain adaptation problem under label shift, assuming that the domains' label priors differ while the class-conditional probabilities are the same. Existing algorithms are based on feature probability matching, where the class-conditional probability can be difficult to estimate e.g. using GAN. To cope with this problem, the authors propose a novel matching algorithm based on class probability matching. They proved that the estimated class probability ratio is consistent with previous algorithms and the estimation process enjoys wonderful theoretical guarantees. Experimentally, they show the proposed method achieves better performance than existing algorithms.", "questions": "Is the network fixed and will not be fine-tuned on the target domain?\n\nBTW, I accidentally clicked the check box of 'First Time Reviewer' while I've been an experienced reviewer in the ICLR community.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This paper is well-written and easy to follow.\n\n2. The theoretical analysis is thorough and helpful.\n\n3. The experimental results clearly verified the effectiveness and efficiency. \n\nOverall, I believe this is a solid paper and should be accepted.", "weaknesses": "1. While I vote for clear acceptance, I think the studied problem is not very significant since they simply consider the label shift problem. Notably, this problem can be regarded as an imbalanced semi-supervised learning problem where the labeled set and the unlabeled set have different classes prior. There have been many empirically strong works that study the imbalanced semi-supervised learning problem [1-4] and I suggest the authors discuss these papers properly.\n\n2. Can the proposed method be equipped with existing imbalanced semi-supervised learning algorithms for improved performance? It won't affect my decision, but I would appreciate it if the authors could provide further extensions, which I believe will enhance the empirical significance of this paper. \n\n3. In Eq (11), the authors directly optimize the class prob ratio by searching the $R^K$ space and finally perform normalization. Can we directly obtain the class prob ratio by constraining it in the normalized space $\\sum \\hat{w}_k = 1$?\n\n4. There are some typos, e.g. there is an unexpected bracket on page 13 line 4, 'p(k))'.\n\n[1] Kim J, Hur Y, Park S, et al. Distribution aligning refinery of pseudo-label for imbalanced semi-supervised learning[J]. Advances in neural information processing systems, 2020, 33: 14567-14579.\n\n[2] Oh Y, Kim D J, Kweon I S. Daso: Distribution-aware semantics-oriented pseudo-label for imbalanced semi-supervised learning[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022: 9786-9796.\n\n[3] Wei C, Sohn K, Mellina C, et al. Crest: A class-rebalancing self-training framework for imbalanced semi-supervised learning[C]//Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2021: 10857-10866.\n\n[4] Fan Y, Dai D, Kukleva A, et al. Cossl: Co-learning of representation and classifier for imbalanced semi-supervised learning[C]//Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2022: 14574-14584.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8A2NdXvzmv", "reviewer": "Reviewer_FsKm", "summary": "This paper proposes a novel method for domain adaptation in the context of label shift, where label distributions between the source and target domains differ while the conditional feature-label distribution remains the same. The proposed approach, called \"class probability matching\" (CPM), aims to match class probabilities and significantly improves computational efficiency compared to existing methods. Within the CPM framework, they introduce \"class probability matching with calibrated networks\" (CPMCN) for target domain classification, supported by a theoretical generalization bound.", "questions": "1.\tThe core of class probability matching is to derive that solving problem (11) can obtain an estimator of class probability ratio w*, which is utilized to transform the source domain classifier to the target domain classifier. However, the authors do not provide any analysis of the problem (1). Can its optimal solution be obtained by existing algorithms, e.g., BFGS. If the approximate solution is attained, how the approximation influences the generalization bound. \n2.\tIn figure 1, the curves of other compared matching approaches are expected to be shown. \n3.\tPlease verify that the proposed approach is computational more efficient than compared matching approaches quantitatively in the experimental studies.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper proposes a novel class probability matching method, which is computationally more efficient compared with existing feature distribution matching methods.\n\n2. Theoretical analysis of the generalization bound is obtained for the proposed approach. \n\n3. The algorithm is simple, and the empirical results demonstrate superior performance of CPMCN over existing approaches.", "weaknesses": "The theoretical analysis is not intuitive. Maybe some proof sketches in the paper can help the readers understand the results.  For example, why assumption 5.1 is required and what does it mean.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)