Conceptio › Archive › arXiv CS

arXiv CSopen access

General Quantification of Covariate and Concept Shifts

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

General Quantification of Covariate and Concept Shifts

Hongbo Chen 1 Li Charlie Xia 1

arXiv:2609.11918v1 [cs.LG] 10 Sep 2026

Abstract

domain adaptation and domain generalization.

Generalization under distribution shift remains a core challenge in modern machine learning, yet existing learning bound theory is limited to narrow, idealized settings and is non-estimable from samples. In this paper, we bridge the gap between theory and practical applications. We first show that existing definition of concept shift breaks when the source and target supports mismatch. Leveraging entropic optimal transport, we propose a key notion: γ ∗-concept shifts, and derive a general error bound unifying covariate and γ ∗concept shifts, which applies to broad loss functions, label spaces, and stochastic labeling. We further develop estimators for these shifts with concentration guarantees, and the DataShifts algorithm, which can quantify distribution shifts and estimate the error bound in most applications - a rigorous and general tool for analyzing learning error under distribution shift.

Theoretical results on distribution shift usually bound a model’s target domain error by its source domain error plus a measure of the distribution shift. The shift is further dissected into X (covariate) and Y|X (concept) shifts (Moreno-Torres et al., 2012; Liu et al., 2021; Zhang et al., 2023). Early studies proposed using H-divergence to measure X shift and derived an error bound for binary classification (Ben-David et al., 2006; 2010). Later works improved X shift using the maximum mean discrepancy (Long et al., 2015) and the Wasserstein distance (Shen et al., 2018; Courty et al., 2017). Further studies proposed more complex metrics for the X shift to obtain bounds for multiclass classification (Zhang et al., 2020; 2019). These results focused only on X shift and additionally relied on a joint-error term between the source and target domains. Lately, Zhao et al. (2019) improved this loose joint-error term and proposed a bound that explicitly considers both X and Y|X shifts for binary classification, and Zhang et al. (2023) extended the theory to multiclass classification. In this paper, we focus on two remaining key problems in the existing theoretical frameworks, which significantly hinder researchers from analyzing X and Y|X shifts in applications:

1. Introduction With the growth of data and computing power, supervised learning has achieved remarkable success. Nonetheless, traditional supervised learning assumes that the training data (source domain) and the test or deployment data (target domain) share the same distribution. However, in many real-world applications, the test data distribution can differ substantially from the training distribution, and this discrepancy can significantly impact model performance in the target domain. To analyze such challenges, researchers theorized that the distributions between the source and target domains are shifted and developed methods to assess how learners trained in the source domain could perform on the target domain. Depending on whether the target domain data is accessible, the problems are further categorized into

• Generalizability. Existing theories rely on restrictive assumptions: they require deterministic labeling, omitting label noise and latent confounders commonly seen in practice; moreover, they only apply to classification with absolute error, excluding broader tasks such as regression and loss families. • Estimability. Although existing theories provide a preliminary definition of Y|X shift, this definition and the accompanying error bounds—are not estimable. As a result, one cannot rigorously quantify Y|X shift on real data, nor assess its impact on model performance. We aim to provide a general theoretical framework unifying X and Y|X shifts that widely applies to stochastic labeling, most supervised tasks, and broader loss functions. Moreover, these two shifts can be accurately estimated from samples, thereby offering a rigorous, plug-and-play tool for quantifying and analyzing distribution shifts in real applications.

Department of Statistics and Financial Mathematics, School of Mathematics, South China University of Technology, Guangzhou, China. First author: Hongbo Chen <[email protected]>. Correspondence to: Li Charlie Xia <[email protected]>. Proceedings of the 43 rd International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026. Copyright 2026 by the author(s).

Specifically, our key observation is that if X shift occurs, the 1

General Quantification of Covariate and Concept Shifts

2. Preliminary

supports of the source and target covariate distributions may not overlap. Such a support mismatch renders the existing theories’ Y|X shift ill-defined, fundamentally causing the error bounds non-estimable and loose. Our key innovation is to employ the entropic optimal transport to give a general definition for X and Y|X shift. The γ ∗ -Y|X shift we propose, which depends on the entropic optimal transport coupling of X shift, stays well-defined even when supports mismatch, and applies to the stochastic labeling and general label space. Based on that, we derived a new error bound that considers both the X and the γ ∗ -Y|X shifts. Our new bound relies only on the Lipschitz continuity of the hypothesis h and loss ℓ, and is agnostic to specific hypothesis space, label space, or loss function, which naturally generalizes to binary and multiclass classification, regression and other tasks.

2.1. Problem Setup Our problem is to bound the error of models under distribution shift. Let X and Y be the covariate space and the label S T space, respectively. Let DXY and DXY be the joint distributions of covariates and labels on X × Y for the source S T and target domains, respectively. DX , DX are their covariate marginals on X . For any x ∈ X , we let DYS |X=x and DYT |X=x be the conditional label distributions at x in the source and target domain. Let Y ′ be the output space of the learner, ℓ : Y × Y ′ → R the loss, and H ⊆ {g : X → Y ′ } the hypothesis space. For a hypothesis h ∈ H, the learning errors for source and target domains are: S ϵS (h) = E(xS ,yS )∼DXY ℓ(yS , h(xS )) T ϵT (h) = E(xT ,yT )∼DXY ℓ(yT , h(xT ))

Since our γ ∗ -Y|X shift is well-defined regardless of support mismatch, X and Y|X shifts, and our new error bound becomes estimable from samples. Nonetheless, for X shift, the traditional plug-in estimator for entropic optimal transport tends to overestimate due to the curse of dimensionality. We thus further developed a debiased estimator that remains accurate in high dimensions. For our γ ∗ -Y|X shift, we also proposed an estimator. We proved both estimators’ concentration inequalities to their true values. Leveraging these two estimators, we presented the DataShifts algorithm, enabling quantification of X and Y|X shifts on general labeled data. Finally, we apply our theoretical framework and DataShifts to three distinct tasks: Novozymes enzyme prediction, ColoredMNIST, and PACS, clearly validating the general effectiveness of our theoretical results.

We hope to bound ϵT (h) by ϵS (h) and a measure of distribution shift, consistent with existing theoretical results (Ben-David et al., 2006; Zhao et al., 2019). Notably, the space X can be the raw input space or a representation space output by an upstream learner (Ben-David et al., 2006). Our theory treats them in the same way, so it applies to both raw data and learned representations. Stochastic and deterministic labeling. Above, we assume that the label y follows the conditional distribution at point x: y ∼ DY |X=x , namely the stochastic labeling setting (Zhao et al., 2019). It enables our theory to accommodate latent confounders and label noise, which are common in practice. In contrast, existing theories oversimplify by using deterministic labeling: a labeling function f : X → Y with y = f (x), a special case of stochastic labeling in which the conditional distribution collapses to a Dirac mass at f (x), i.e., DY |X=x = δf (x) .

Contributions. In summary, our major contributions are: • We show that support mismatch makes the existing Y|X shift ill-defined—hence loose and non-estimable. We introduce the γ ∗ -Y|X shift as a well-defined concept shift, which possesses many desirable properties. • We derive a general error bound unifying covariate and γ ∗-concept shifts. Our bound covers broader learning scenarios, far beyond traditional binary classification.

2.2. Existing Theory and Ill-Defined Y|X Shift We first demonstrate that support mismatch leads to an illdefined Y|X shift, a key flaw in existing theory.

• For the X and γ ∗ -Y|X shifts in our theory, we propose two estimators and prove their concentration inequalities, ensuring that these shifts can be rigorously estimated from finite samples.

Definition 2.1 (Support). Let µ be a probability measure on the topological space (X , τ ). Its support is defined as: supp(µ) = { x ∈ X | ∀ U ∈ τ, x ∈ U, µ(U ) > 0}

• We integrate our theoretical results into the DataShifts algorithm, which can estimate X and γ ∗ -Y|X shifts from real data, supplying a rigorous and general tool for quantifying and analyzing distribution shifts.

supp(µ) is the closure of every region where µ has positive measure, or equivalently, the complement of the union of all µ-null open sets: n[ o supp(µ) = X \ { U ∈ τ | µ(U ) = 0}

The paper is organized as follows: Section 2 covers the preliminaries, Section 3 presents the population-level theoretical results, Section 4 focuses on the statistical results, and Section 5 presents experiments validating our theory.

Lemma 2.2 (Ill-Defined Expectation of Conditional Probability). For probability measure PX , a PX -measurable 2

General Quantification of Covariate and Concept Shifts S supp(DX ); hence, under support mismatch the expecT |fS (x) − fT (x)| is non-estimable, as tations Ex∼DX S |fS (x) − fT (x)| . well as Ex∼DX

function P (A | X = x) : X → [0, 1] is the conditional probability of event A given X = x. For probability mea′ ′ sure PX satisfying supp(PX ) \ supp(PX ) ̸= ∅, the expectation EPX′ [P (A | X = x)] is arbitrary.

2.3. Entropic Optimal Transport

Remark This problem arises because the conditional probability P (A | X = x) is unique almost everywhere with ′ respect to PX (unique PX -a.e.), rather than to PX . When ′ ′ supp(PX ) \ supp(PX ) ̸= ∅, PX assigns positive mass to some PX -null sets. In this case, EPX′ [P (A | X = x)] depends on the values of P (A | X = x) on sets where it is not uniquely determined. Hence, support mismatch leads to the ill-defined expectation of conditional probability. This issue directly impacts the definition and computation of Y|X shift in existing theories, since the Y|X shift is typically formulated as an expectation over conditional labeling distributions or its collapsed labeling functions.

We introduce entropic optimal transport, which we will employ to give the general definitions of X and Y|X shifts properly. It measures the distance between two probability distributions, augmenting conventional optimal transport with a relative-entropy regularizer. Given two probability distributions P and Q on the metric space (Ω, ρ) and a parameter β ≥ 0, the order-1 entropic optimal transport is: Z Wβ (P, Q) = inf ρ dγ + β H γ P ⊗ Q (2) γ∈Γ(P,Q)

where H γ

With deterministic labeling, Zhao et al. (2019) used Hdivergence (Ben-David et al., 2006) to derive an error bound for soft-label binary classification under X and Y|X shifts: Theorem 2.3 (Existing Learning Bound on Distribution S T Shift). Let DX , DX be the covariate distributions and fS , fT : X → [0, 1] be the labeling functions for the source and target domain. Using absolute error loss | · |, for any hypothesis space H ⊆ [0, 1]X define: H̃ = sgn(|h(x) − h′ (x)| − t) h, h′ ∈ H, t ∈ [0, 1] ,

R dγ(x1 ,x2 ) P ⊗ Q = log dP(x dγ(x1 , x2 ). ) dQ(x ) 1 2

Here, ρ(x1 , x2 ) is the cost of transporting mass between points, Γ(P, Q) is the set of joint distributions with marginals P and Q, and γ(x1 , x2 ) is a transport coupling. Hence, Wβ (P, Q) is the minimum total transport cost between P and Q under an entropy regularizer. When β = 0, this reduces to the Wasserstein-1 distance, denoted by W1 (P, Q). Compared with other distribution distances, (entropic) optimal transport has a well-established geometric meaning (Gangbo & McCann, 1996), and we will consistently use it to measure distribution shifts.

then for any h ∈ H, n S T S ϵT (h) ≤ ϵS (h) + dH̃ DX , DX + min Ex∼DX |fS (x) o T − fT (x)| , Ex∼DX |fS (x) − fT (x)| (1)

3. Theoretical Results In this section, we focus on population-level theoretical results. We assume that covariate X and label Y are distributed on the metric spaces (X , ρX ) and (Y, ρY ), respectively, and give the rigorous and general definitions of their distribution shifts and essential theorems below.

3.1. General X and Y|X Shifts Definition 3.1 (X Shift). Using entropic optimal transport, the X (covariate) shift is defined as: nZ S T SCov = Wβ DX , DX = inf ρX (xS , xT )

Remark* (Limitations of Theorem 2.3) First, it is highly specialized, applying only to deterministic labeling, binary classification, and absolute loss. Moreover, when X shift T S causes support mismatch : supp(DX )\supp(DX ) ̸= ∅, the S conditional distribution DY |X=x (i.e., fS (x)) is only unique S DX -a.e. and arbitrary on the mismatched region, so the Y|X T [|fS (x) − fT (x)|] is ill-defined. Similarly, if shift Ex∼DX S T supp(DX ) \ supp(DX ) ̸= ∅, the other Y|X shift term is also ill-defined. This additionally causes two problems:

S ,D T ) γ∈Γ(DX X

S T dγ(xS , xT ) + β H γ DX ⊗ DX

(3)

where the optimal coupling is denoted as γ ∗ , a joint distriS T bution of DX , DX that gives the minimum transport cost.

• Loose bound. The ill-defined Y |X shifts can take arbitrary values, making the bound in Eq. (1) loose.

With realistic stochastic labeling, the label follows a conditional distribution given the covariate; we give a general and rigorous definition of Y|X shift below:

• Non-estimable. When the real concept DYS |X=x or fS (x) is unknown, we cannot sample it outside

Definition 3.2 (γ ∗ -Y|X Shift). Let γ ∗ be the optimal transport coupling as in Definition 3.1, Spair (xS , xT ) = 3

General Quantification of Covariate and Concept Shifts

Remark The above γ ∗ -Y|X shift, defined via the entropic optimal transport coupling γ ∗ , applies to general settings S T including stochastic labeling. When DX = DX , it recovers S the existing Y|X shift; and when the supports of DX and T DX are mismatched, it still remains rigorous. 3.2. General Learning Bound

This definition is based on the optimal transport coupling γ ∗ for X shift. Spair (xS , xT ) denotes the paired conditional distribution shift between the source domain at xS and the target domain at xT . Intuitively, since optimal transport coupling γ ∗ places most of its mass on nearby pairs (xS , xT ), γ∗ SCpt is evaluated mainly on such neighboring points.

We now give a new cross-domain learning error bound based on X and γ ∗ -Y|X shift. To be general, the output space of the learner is a metric space (Y ′ , ρ′Y ), possibly different from the true label space (Y, ρY ). For the loss function ℓ : Y × Y ′ → R, we require the following basic assumption from them:

Corollary 3.3 (Consistency under Deterministic Labeling). Assume deterministic labeling DYS |X=x = δfS (x) , DYT |X=x = δfT (x) , then:

Assumption 3.9 (Separately Lipschitz Continuity). For metric spaces (Y, ρY ) and (Y ′ , ρ′Y ), a function ℓ : Y × Y ′ → R satisfies separately (Lℓ , L′ℓ )-Lipschitz if there exist Lℓ , L′ℓ ≥ 0 such that for any y1 , y2 ∈ Y and y1′ , y2′ ∈ Y ′ , there is:

γ∗ SCpt = Eγ ∗ Spair (xS , xT ) = Eγ ∗ ρY (fS (xS ), fT (xT ))

ℓ(y1 , y1′ )−ℓ(y2 , y2′ ) ≤ Lℓ ρY (y1 , y2 )+L′ℓ ρ′Y (y1′ , y2′ ) (5)

The following three lemmas guarantee the good properties of γ ∗ -Y|X Shift.

Remark This is a mild assumption: most loss functions are differentiable, which already implies continuity. And their stable optimization usually needs bounded gradients in a region, further ensuring Lipschitz continuity (Boyd & Vandenberghe, 2004). Note that this assumption also covers asymmetric losses. For instance, for binary classification with label space [0, 1], output space is typically [a, 1 − a] (a ∈ (0, 0.5)) by Sigmoid function and ρY = ρ′Y = | · |, the cross-entropy loss: ℓCE (y, ŷ) = − y log ŷ − (1 − y) log(1 − ŷ) satisfies separately (Lℓ , L′ℓ )-Lipschitz with 1−a ′ Lℓ = log a and Lℓ = a1 .

With deterministic labeling, this definition reduces to:

S T Lemma 3.4 (Support of γ ∗ ). For any γ ∈ Γ(DX , DX ), S T supp(γ) ⊆ supp(DX ) × supp(DX ).

Lemma 3.5 (Uniqueness of γ ∗ ). If β > 0, then the entropic optimal transport coupling γ ∗ in Definition 3.1 is unique. S Lemma 3.6 (Collapse of γ ∗ ). If β = 0 and DX = T ∗ DX , γ collapses to diagonal (identity) coupling γ ∗ = S (Id, Id)# DX , equivalently, for every measurable A ⊆ R ∗ S X × X , γ (A) = 1{(x,x)∈A} dDX (x), where 1{·} is the indicator function.

Corollary 3.10 (Composition Preserves Separate Lipschitzness). Let h : X → Y ′ be Lh -Lipschitz and let ′ ℓ : Y × Y ′ → R be separately (Lℓ , Lℓ )-Lipschitz. Then composite function ℓ y, h(x) : Y × X → R is separately (Lℓ , Lh L′ℓ )-Lipschitz.

Combining Lemmas 3.4 and 3.5, the rigor of γ ∗ -Y|X Shift is ensured: Theorem 3.7 (Well-Definedness of γ ∗ -Y|X Shift). For β > γ∗ 0, the γ ∗ -Y|X shift SCpt in Definition 3.2 is unique even S T when supp(DX ) ̸= supp(DX ). Remark Such γ ∗ -Y|X shift not only avoids the illdefinition encountered by existing theory, but also makes Y|X shift tight and estimable. On the other hand, combining Corollary 3.3 and Lemma 3.6, the relationship between γ ∗ -Y|X shift and existing Y|X shift is shown as follows:

The following two lemmas characterize the transport couS T pling of joint distributions DXY and DXY : Lemma 3.11 (Separately Weak Duality). Let G y, x : Y × X → R is separately (LY , LX )-Lipschitz, for any coupling S T of joint distributions γXY ∈ Γ(DXY , DXY ), there exists: S T EDXY G −EDXY G ≤ LX EγXY ρX +LY EγXY ρY (6)

Lemma 3.12 (Gluing Construction for Joint Coupling). Let γ ∗ be the optimal transport coupling of X shift in Definition 3.1, γY∗ |(xS ,xT ) be the optimal transport coupling of Spair (xS , xT ) in Definition 3.2, construct the joint distribution of couplings: γXY (dxS , dxT , dyS , dyT ) = γ ∗ (dxS , dxT )γY∗ |(xS ,xT ) (dyS , dyT ), then γXY is the couS T pling of joint distributions: γXY ∈ Γ(DXY , DXY ). 4

General Quantification of Covariate and Concept Shifts

Traditional Plug-in Estimator Given i.i.d. samples (S) (T ) S T {Xi } ∼ DX , {Xj } ∼ DX with sample sizes d S NS , NT respectively, set the empirical measures: D X = P P NS NT 1 1 d T i=1 δX (S) , DX = NT j=1 δX (T ) , their entropic opNS

Combining Corollary 3.10, Lemmas 3.11 and 3.12, we obtain the general cross-domain error bound as follows: Theorem 3.13 (General Learning Bound). Given the covariate space (X , ρX ), the label space (Y, ρY ), and the output space (Y ′ , ρ′Y ), the source and target distributions S T are (DX , DYS |X=x ) and (DX , DYT |X=x ), respectively. If the loss ℓ : Y × Y ′ → R satisfies separately (Lℓ , L′ℓ )Lipschitz, then for any hypothesis h : X → Y ′ that satisfies Lh -Lipschitz, the following bound holds: ϵT (h) ≤ ϵS (h) +

Lh L′ℓ SCov

d S d T Wβ D X , DX = min ⟨C, γ̂⟩ + β γ̂

+ β log NS NT

∗

γ Lℓ SCpt

timal transport is:

NS X NT X

γ̂ij log γ̂ij

i=1 j=1

γ̂1 = N1S 1, γ̂ ⊤ 1 = N1T 1 (8)

s.t.

(7)

S ×NT where C ∈ RN is the cost matrix with cij = + (S) (T ) NS ×NT represents any disρX Xi , Xj , and γ̂ ∈ R+ cretized transport coupling satisfying the given linear constraints. Such an optimization problem can be solved efficiently at a large scale by the Sinkhorn algorithm (Cuturi, 2013; Genevay et al., 2016).

γ∗ where SCov is the X shift in Definition 3.1 and SCpt is the ∗

γ -Y|X shift in Definition 3.2.

Remark This elegant bound unifies the covariate shift γ∗ SCov and the concept shift (γ ∗ -Y|X shift) SCpt ’s effect on target error via the Lipschitz factors Lh L′ℓ and Lℓ . Notably, it depends only on the Lipschitz continuity of the hypothesis h and the loss ℓ, without any other specific restriction on the label space Y or loss ℓ. It naturally covers binary classification or regression tasks when Y is one-dimensional, and multiclass classification or multi-label tasks when Y is multi-dimensional. Besides, since the bound holds under stochastic labeling, it applies to a wide range of supervised learning scenarios in practice. On the other hand, by using the well-defined γ ∗ -Y|X shift, our bound can be tighter than the existing bound, and more crucially, both the covariate and concept shifts in our theory can be robustly estimated from the finite samples. Additionally, since the entropic optimal transport SCov increases with the hyperparameter β, we recommend choosing β as a small non-zero value to balance the tightness and the rigor of the theory.

Curse of Dimensionality. However, in modern applications, the covariate space X is often high-dimensional. Even when two distributions are very close, their samples’ distance can be large. Such curse of dimensionality makes the plug-in estimator greatly overestimated (Verleysen & François, 2005; Panaretos & Zemel, 2019) (Fig.1(a)). When β is small, entropic optimal transport behaves similarly to Wasserstein distance (Carlier et al., 2017; 2023), and the upward bias decays only in O(N −1/d ) order (Fournier & Guillin, 2015), which implies that increasing N has a very limited debiasing effect when d is high (Fig.1(b)). To address the overestimation problem of the traditional plug-in estimator, we propose the following debiased estimator. Definition 4.1 (Debiased Estimator). Given i.i.d. samples (S) (T ) S T {Xi } ∼ DX , {Xj } ∼ DX with sample sizes NS , NT respectively, split the samples in half to obtain four inde′ PNS /2 d S pendent empirical measures: D = 2 δ (S) ,

4. Statistical Results In practice, true domain distributions are all unknown. We wish to estimate the shifts from domain samples and analyze how these shifts will influence model performance. In this section, we focus on sample-level theoretical re(S) (S) sults. Suppose we have i.i.d. samples {(Xi , Yi )} and (T ) (T ) S T {(Xj , Yj )} drawn from DXY and DXY with sizes NS and NT , respectively. This section involves three parts: the estimation of X shift, the estimation of Y|X shift, and the DataShifts algorithm to estimate the overall bound.

i=1

′′ ′ PNS PNT /2 2 2 d d S T D X = NS j=1 δXj(T ) , i=NS /2+1 δXi(S) , DX = NT ′′ P NT 2 d T D X = NT j=NT /2+1 δX (T ) . The debiased estimator is: j

′ ′′ ′ ′′ 2 1 d d d d S d T S d S T 2+ 1W D T Wβdeb D β X , DX = 2 Wβ DX , DX X , DX 2 ′ ′′ 2 ′ ′′ 2 d d S d S T d T − 12 Wβ D − 12 Wβ D X , DX X , DX

1/2

(9)

4.1. Estimation of X Shift By Definition 3.1, the X shift is the entropic optimal transS T port between DX and DX . The traditional estimation method uses the entropic optimal transport of empirical distributions—known as the plug-in estimator.

Remark This debiased estimator uses four plug-in es′ ′ d S d T timators. The first two terms, Wβ D and X , DX ′′ ′′ d d S S T Wβ DX , DX , estimate the distance between DX and 5

General Quantification of Covariate and Concept Shifts W ( , 0)(N = 1000) W ( , 0)(N = 50000) W deb( , 0)(N = 1000)(ours) W deb( , 0)(N = 50000)(ours)

W ( , 0)(d = 90) W ( , 0)(d = 70) W ( , 0)(d = 50)

12 11

W ( , t)(N = 1000) W ( , t)(N = 50000) W deb( , t)(N = 1000)(ours) W deb( , t)(N = 50000)(ours) diagonal

Empirical Distance

6 4

N = 50000

Empirical Distance

9 8

N = 100

7 2

6 0 0

Dimension(d)

100

(a) Empirical distance vs. dimension (d)

0.75

0.80

0.85

N 1d

0.90

0.95

1.00

True Wasserstein-1 Distance ( t )

(b) Empirical distance vs. sample size (N )

Figure 1. (a)–(c) show the empirical distance from entropic optimal transport (β = 0.001) versus dimension d, sample size N , and true Wasserstein-1 distance. In (a)–(b), η̂ and η̂ ′ are independent empirical measures from high-dimensional standard normals, thus the true distance is zero. The traditional estimator Wβ (η̂, η̂ ′ ) greatly overestimates as d increases, as shown in (a), and even a much larger N only brings a small improvement, as shown in (b). In (c), with d = 70, η̂t is the empirical measure of shifted standard normal N (t, I), whose true Wasserstein-1 distance to the standard normal is ∥t∥. Our debiased estimator remains accurate in every case.

T DX , including the sample bias. And the last two terms, ′ ′′ ′ ′′ d d d d S ,D S T ,D T W D and W D estimate the distance β

4.2. Estimation of Y|X Shift ∗

γ As above, we defined the γ ∗ -Y|X shift SCpt in Definition 3.2; we now estimate it from samples. Definition 4.3 (Estimator for γ ∗ -Y|X Shift). Given i.i.d. (S) (S) (T ) (T ) S samples {(Xi , Yi )} ∼ DXY , {(Xj , Yj )} ∼ T DXY with sample sizes NS , NT respectively, the estimator of γ ∗ -Y|X shift is defined as:

arising from sample bias only. Subtracting the two parts reduces the sample bias, thus giving a better estimate of S T Wβ (DX , DX ). Compared with the traditional plug-in estimator, our debiased estimator Wβdeb reduces the overestimation and remains accurate regardless of the true distribution distance (see Fig.1(a) and 1(c)). Moreover, when the covariate space is Euclidean, we derived a concentration inequality guaranteeing that the debiased estimator converges to the true distance: Theorem 4.2 (Concentration Inequality of Debiased EsS T timator). Let DX , DX be two distributions on (Rd , ∥ · ∥) with finite squared-exponential moments. For i.i.d. samples (S) (T ) S T {Xi } ∼ DX , {Xj } ∼ DX with sample sizes NS , NT respectively, when β = 0, and for any ε > 0, there exists N such that if NS , NT > N , then: S T d S d T P Wβdeb (D X , DX ) − Wβ (DX , DX ) > ε ≤ 2 2 S Vε ε T Vε ε 2 exp − λS N32 + 2 exp − λT N32 (10)

ŜCpt =

NS X NT X

(S)

ρY Yi

(T )

, Yj

∗ γ̂ij ,

(11)

i=1 j=1 S ×NT where γ̂ ∗ ∈ RN represents the discrete optimal trans+ d d S ,D T ). port coupling for W (D

Remark In Section 4.1, we use the debiased estimator d S d T Wβdeb D X , DX for X shift, whereas Definition 4.3 still estimates γ ∗ -Y|X shift via the optimal transport coupling d S d T from the plug-in estimator Wβ (D X , DX ). This is because the curse of dimensionality mainly affects the transport cost (i.e., inter-sample distances), rather than the transport coupling. Leveraging the stability of entropic optimal transport (Eckstein & Nutz, 2022), the following lemma establishes the convergence of the coupling for plug-in estimator: Lemma 4.4 (Stability of Entropic Optimal Transport S T Coupling). Let DX , DX be two distributions on (X , ρX ) with finite squared-exponential moments. γ ∗ and γ̂ ∗ S T are the optimal transport couplings of Wβ (DX , DX ) and d d S T Wβ (DX , DX ) respectively, then: s 2 √ ∗ ∗ W1 (γ , γ̂ ) ≤ Λ + 2 Λ βλγ ∗ S d T d S T Λ = W1 DX , DX + W1 DX , DX (12)

where λS , λT > 0 depend only on squared-exponential √ S T moments of DX , DX , respectively, and Vε ∈ [2 − 3, 2) S T depends only on Wβ (DX , DX )/ε. Remark This theorem implies that the deviation probability of the debiased estimator decays exponentially with sample sizes, so with high probability, our debiased estimator can well approximate the true entropic optimal transport S T distance Wβ (DX , DX ). Notably, it also shows the enlightening fact that our estimator’s concentration depends not only on each distribution’s scale characterized by λS , λT but also on the true distance between two distributions. 6

General Quantification of Covariate and Concept Shifts ∗

γ shift SCpt itself. For stochastic labeling, we show that ∆ can be bounded by the irreducible error (James et al., 2013) (also known as the Bayes risk (Berger, 2013)) in traditional statistical learning.

where W1 (γ ∗ , γ̂ ∗ ) is computed on X × X with metric ρ (x1 , x2 ), (x′1 , x′2 ) := ρX (x1 , x′1 ) + ρX (x2 , x′2 ), λγ ∗ > S T 0 depend only on squared-exponential moments of DX , DX . Remark This lemma shows that the Wasserstein-1 distance between the plug-in estimator coupling and the population optimal transport coupling, is bounded by the sum of the marginal Wasserstein-1 distance between each population and its empirical distribution, with the bound scaled by the parameter β. Such a uniform bound is guaranteed only when β > 0, which further highlights the necessity of using entropic optimal transport.

Proposition 4.7 (∆ in Stochastic Labeling). When ′ (Y, ρY ) = (Rd , ∥ · ∥), the irreducible error of joint dis2 tribution DXY under squared loss as: ∥ · ∥ is 2defined I(DXY ) = inf g:X →Y E(x,y)∼DXY ∥y − g(x)∥ , then the ∆ in Theorem 4.5 satisfies: q q S ) + T ) 0 ≤ ∆ ≤ I(DXY I(DXY (15)

By Lemma 4.4, when covariate space X is Euclidean and label space Y is a bounded set in an Euclidean space, we derive a concentration inequality guaranteeing estimator in Definition 4.3 approximates true value:

Remark The irreducible error is the fundamental error inherent to stochastic labeling that no model can overcome. When the problem is learnable, covariate and label are often well correlated, and the irreducible error is small relative to the overall label variability. In this case, Proposition 4.7 guarantees that the estimator ŜCpt does not substantially γ∗ overestimate the Y|X shift SCpt .

Theorem 4.5 (Concentration Inequality for Definition 4.3). S T Let DX , DX be two distributions on (Rd , ∥ · ∥) with finite squared-exponential moments. Let the label space ′ Y ⊂ Rd be bounded by M = supy,y′ ∈Y ∥ y − y ′ ∥, on which conditional distributions DYS |X=xS , DYT |X=xT satisfy LY |X -Lipschitz respectively: dTV DY |X=x , DY |X=x′ ≤ (S)

(S)

LY |X ∥ x − x′ ∥. For i.i.d. samples {(Xi , Yi (T )

4.3. DataShifts Algorithm On the Lipschitz Constant of Learners. The Lipschitz constant of the learner have been well studied, such as logistic regression (Roux et al., 2012), multi-layer perceptron (MLP) (Fazlyab et al., 2019), convolutional neural networks (CNN) (Virmaux & Scaman, 2018; Zou et al., 2019) and attention mechanism (Kim et al., 2021; Castin et al., 2023). Although the Lipschitz constants of modern large-scale neural networks such as ResNet-50 or Transformers remain difficult to analyze, researchers are more concerned with whether these models learn distribution-robust representations (Hendrycks et al., 2020), rather than distribution shift in the raw input space. In this setting, the covariate space X is the representation space, and the downstream model (the hypothesis h in our theory) is often a simple learner—such as a linear classifier—whose Lipschitz constant is still easy to handle. We summarize the Lipschitz constants of various learners in Appendix D.

S )} ∼ DXY ,

(T )

T {(Xj , Yj )} ∼ DXY with sample sizes NS , NT , when β > 0, and for any ε > 0, there exists N such that if NS , NT > N , then: NS NT Φ ε2 γ∗ P |ŜCpt − SCpt − ∆| > ε ≤ 2 exp − (NS + NT )M 2

λ1/2 N Φ ε2 λ1/2 N Φ ε2 T S + exp − T 1/2 (13) +exp − S 1/2 2 4 λT M 4 λS M 2 where dTV is total-variation distance, λS , λT > 0 depend S T only on the squared-exponential moments of DX , DX ,Φ> 0 depends on LY |X , λS , λT , β, the bias ∆ is a constant. Remark This theorem implies that the deviation probability of the γ ∗ -Y|X Shift estimator ŜCpt decays exponentially with sample sizes, so with high probability, the estimator can γ∗ well approximate the SCpt +∆. The bias term ∆ arises be(S) (T ) cause Definition 4.3 uses ρY Yi , Yj as a single-point (S) (T ) estimate of Spair Xi , Xj in Definition 3.2. The following two propositions show that the bias ∆ is controlled.

Algorithm 1 DataShifts Input: hyperparameter β (default 0.01), (S) (S) (T ) (T ) samples {(Xi , Yi )}, {(Xj , Yj )}, Lipschitz constants Lℓ , L′ℓ , Lh (optional), source domain empirical error ϵ̂S (optional) Do: Estimate X shift by 4.1 as ŜCov Estimate γ ∗ -Y|X shift by 4.3 as ŜCpt if Lℓ , L′ℓ , Lh , and ϵ̂S are provided then Estimate bound: B = ϵ̂S + Lh L′ℓ ŜCov + Lℓ ŜCpt end if Return: ŜCov , ŜCpt and B (optional)

Proposition 4.6 (∆ in Deterministic Labeling). Assume deterministic labeling DYS |X=x = δfS (x) , DYT |X=x = δfT (x) , then the ∆ in Theorem 4.5 satisfies: ∆=0

(14)

Remark This proposition shows that under deterministic labeling, the estimator ŜCpt accurately estimates the Y|X 7

General Quantification of Covariate and Concept Shifts

12.5 10.0 7.5

1.8

1.6

1.4

5.0

CORAL / env(P) CORAL / env(S) MMD / env(A) MMD / env(C) MMD / env(P) MMD / env(S)

7 6 5 4

1.2

(algorithm, test environment)

2.5 0.00.0

(algorithm, test environment)

ERM / env(A) ERM / env(C) ERM / env(P) ERM / env(S) CORAL / env(A) CORAL / env(C)

Estimated Error Bound

15.0

2.0

Estimated Error Bound

17.5

Estimated Error Bound

2.2

Indomain error X shift term Y|X shift term diagonal domains

20.0

2.5

5.0

7.5

10.0

12.5

Test Error (a) Novozymes

15.0

17.5

20.0

1.0

MMD / env(+90%) MMD / env(+80%) CORAL / env(+90%)

0.7

0.8

0.9

Test Error

CORAL / env(+80%) ERM / env(+90%) ERM / env(+80%)

1.0

1.1

3 0.00

0.25

0.50

(b) ColoredMNIST

0.75

1.00

Test Error

1.25

1.50

1.75

Figure 2. (a)–(c) show that the estimated error bounds track the test error well across three distinct tasks, corroborating the general effectiveness of our learning bound and estimators.

By leveraging the theoretical results above, we give the plugand-play Algorithm 1 (DataShifts) for quantifying X and Y|X shifts from finite samples and estimating error bounds.

We plot the test error and the estimated error bound on each target domain in Fig. 2(a). In this figure, the overall trend of the test error and the error bound lies just above the diagonal, indicating that our bound is tight and effectively captures the test error under distribution shift. Meanwhile, it directly shows the contributions of X and Y|X shifts on the error bound. The large Y|X shift across enzyme families is what drives the generalization failure in this contest.

5. Experiments In this section, we apply our estimable general theory to three distinct practical tasks: tabular regression, image binary classification, and image multi-class classification – to validate the general effectiveness of our bound and estimators. We also conduct experiments on synthetic tasks where existing theory apply, demonstrating our bound is tighter.

5.2. ColoredMNIST and PACS ColoredMNIST and PACS are two standard tasks in the DomainBed benchmark(Gulrajani & Lopez-Paz, 2020). ColoredMNIST is a binary classification task with 70,000 handwritten digit images exhibiting color shift, while PACS is a multi-class object recognition task with 9,991 images exhibiting style shift. For both tasks, we treat the model’s representation space as the covariate space X . Following the DomainBed setup, we use the simple CNN with a 128dimensional representation for ColoredMNIST, and ResNet50 with a 2048-dimensional representation for PACS. In this setting, the hypothesis h in our theory corresponds to the model’s final layer (a linear classifier), whose Lipschitz constant is analyzed in the Appendix D.3.

5.1. Novozymes Enzyme Stability Prediction The Novozymes Enzyme Prediction Competition (Pultz et al., 2022) is a large-scale Kaggle contest. It is a tabular regression task, with 9,000 point-mutation samples spanning 180 enzyme families, aiming to predict transition temperatures for unseen families. Each enzyme family is treated as a separate domain; due to distribution shifts between them, thousands of participants found it difficult to develop any effective solution. We select the 60 enzyme families with the smallest pretraining error as the source domain, and treat each of the remaining 120 enzyme families as a target domain. In this task, we focus on the distribution shift between the raw data of different enzyme families, taking the 20-dimensional input feature space as covariate space X . We train a 3-layer MLP on the source domain; an analysis of its Lipschitz constant is provided in the Appendix D.4. We use the absolute loss (separately (1, 1)-Lipschitz) to evaluate the source domain error and the test error on each target domain, and apply our DataShifts algorithm(β = 0.2) to estimate an error bound for each target domain.

We evaluate three methods: ERM, CORAL, and MMD. Adhering to DomainBed, we select the best hyperparameters via training-domain validation over 20 random hyperparameter trials for each method, domain, and trial. For ColoredMNIST, we train each best-hyperparameter run for 5,000 steps and save checkpoints every 100 steps. For PACS, since the model converges earlier, we train for 1,000 steps and save checkpoints every 20 steps. At each checkpoint, we regard the mixture distribution over training domains as the source domain and the test domain as the target domain. We still use the absolute loss to measure source and target errors, 8

General Quantification of Covariate and Concept Shifts 0.8 0.7

existing bound general bound (ours) test error

0.5

existing bound general bound (ours) test error

0.6 0.5

existing bound general bound (ours) test error

0.4 0.4

0.5

0.3

Error

0.6

0.2

0.4 0.1

0.1

0.3

0.0

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5

X Shift

(a) Error vs. X shift

0.3

0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180

Y|X Shift ( )

(b) Error vs. Y|X shift (θ)

0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0 2.2 2.4 2.6 2.8 3.0

Y|X Shift (b)

Figure 3. (a)–(c) respectively show the relationship between the estimated learning bounds and the X or Y|X shift in synthetic binary classification tasks. As these shifts increase, our bound becomes significantly tighter than the existing bound.

and run our DataShifts algorithm (β = 0.2) using each domain’s representation-label pairs to estimate the test domain error bound at every checkpoint.

We also use logistic regression as the learner and train it on the source domain. Its Lipschitz constant is analyzed in Appendix D.2. For each target domain, we estimate the test error, the existing and our bounds under the absolute loss.

We plot the test error and the estimated error bound for both tasks in Fig. 2(b) and 2(c). In Fig. 2(b), the bound tracks the test error well across checkpoints. The MMD (purple) and CORAL (yellow) points lie closer to the lower-left region, indicating that these X shift-reducing methods indeed yield smaller bounds, and consequently lower error on ColoredMNIST. In Fig. 2(c), although the bound becomes looser in magnitude when applied to PACS, a more complex image classification task, it still exhibits a consistent trend with the test error in each run.

We plot the learning bounds with respect to the X shift and the Y|X shifts (θ and bT ) in Fig. 3. In Fig. 3(a), since both the source concept and the learner are logistic regression models, the learner can fit the source concept well, and the X shift in the target domain has only a minor effect on the test error. As the X shift increases, our bound becomes tighter than the existing bound. In Figs. 3(b) and 3(c), as the Y|X shift increases, the existing bound becomes looser than ours. This verifies our point in Remark*: the ill-defined Y|X shift in the existing bound is loose, whereas our γ ∗ -Y|X shift and the accompanying learning bound can be tighter.

5.3. Synthetic Binary Classification

In addition to the above results, sensitivity experiments of the proposed estimators with respect to the parameter β are provided in Appendix E.1. Experiments on the bias of the γ ∗ -Y|X shift estimator under stochastic labeling are presented in Appendix E.2.

We compare our theory with the existing bound in Zhao et al. (2019), which is shown to be tighter than previous learning bounds. As discussed in Remark*, the existing learning bound only applies to soft-label binary classification with deterministic labeling and absolute loss. Since its estimation requires sampling the true concepts fS and fT outside the S T supports of the covariate distributions DX , DX (oracle), it can only be estimated on synthetic tasks where the true concepts are known.

6. Conclusion In this paper, we focus on a general and estimable theoretical framework for learning under distribution shift. We first introduce a key notion, γ ∗ -Y|X shift, via entropic optimal transport, which addresses the ill-definedness in existing theory. Then we derive a general learning bound unifying X shift and γ ∗ -Y|X shift. We further develop concentrationguaranteed estimators for both shifts, and integrate our theory into the plug-and-play DataShifts algorithm, enabling researchers to quantify and analyze distribution shift in broad settings. Experiments on practical and synthetic tasks validate the general effectiveness and tightness of our theory. We believe our theoretical framework takes an important step toward learning under distribution shift and will spur further algorithmic advances.

We construct a synthetic binary classification task using logistic regression. Let the covariate space be 10-dimensional, and the source inputs are sampled from standard normal S distribution: DX = N (0, I), with labels √ generated by ⊤ fS (x) = σ(wS x + bS ), where wS = 1/ 10, bS = 0 and σ is the sigmoid function. The target inputs are generated by S shifting DX along a random direction, thereby controlling the X shift. And the target labels are generated by another logistic regression: fT (x) = σ(wT⊤ x + bT ), where wT is obtained by rotating wS by angle θ toward a random direction. θ and bT further control the Y|X shift. By varying the X shift, θ, and bT , we obtain a series of target domains. 9

General Quantification of Covariate and Concept Shifts

Acknowledgements

Castin, V., Ablin, P., and Peyré, G. How smooth is attention? arXiv preprint arXiv:2312.14820, 2023.

We also thank Dr. Jie Ren for suggestions and feedback on this work. This study was funded by the National Natural Science Foundation of China (12571529) and Guangdong Basic and Applied Basic Research Foundation (2024A1515010699) to LCX.

Cole, S. R. and Frangakis, C. E. The consistency statement in causal inference: a definition or an assumption? Epidemiology, 20(1):3–5, 2009. doi: 10.1097/ EDE.0b013e31818ef366. URL https://doi.org/ 10.1097/EDE.0b013e31818ef366.

Impact Statement

Courty, N., Flamary, R., Habrard, A., and Rakotomamonjy, A. Joint distribution optimal transportation for domain adaptation. Advances in neural information processing systems, 30, 2017.

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.

References Arjovsky, M., Bottou, L., Gulrajani, I., and LopezPaz, D. Invariant risk minimization. arXiv preprint arXiv:1907.02893, 2019.

Duncan, T. E. On the absolute continuity of measures. The Annals of Mathematical Statistics, 41(1):30–38, 1970. Eckstein, S. and Nutz, M. Quantitative stability of regularized optimal transport and convergence of sinkhorn’s algorithm. SIAM Journal on Mathematical Analysis, 54 (6):5922–5948, 2022.

Ben-David, S., Blitzer, J., Crammer, K., and Pereira, F. Analysis of representations for domain adaptation. Advances in neural information processing systems, 19, 2006. Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., and Vaughan, J. W. A theory of learning from different domains. Machine learning, 79:151–175, 2010.

El Hamri, M., Bennani, Y., and Falih, I. Theoretical guarantees for domain adaptation with hierarchical optimal transport. Machine Learning, 114(5):119, 2025.

Berger, J. O. Statistical decision theory and Bayesian analysis. Springer Science & Business Media, 2013. Bolley, F., Guillin, A., and Villani, C. Quantitative concentration inequalities for empirical measures on non-compact spaces. Probability Theory and Related Fields, 137(3–4):541–593, 2007. doi: 10.1007/ s00440-006-0004-7. URL https://doi.org/10. 1007/s00440-006-0004-7. Bonet, C., Vauthier, C., and Korba, A. Flowing datasets with wasserstein over wasserstein gradient flows. arXiv preprint arXiv:2506.07534, 2025.

Fazlyab, M., Robey, A., Hassani, H., Morari, M., and Pappas, G. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in neural information processing systems, 32, 2019. Fazlyab, M., Morari, M., and Pappas, G. J. Safety verification and robustness analysis of neural networks via quadratic constraints and semidefinite programming. IEEE Transactions on Automatic Control, 67(1):1–15, 2020. Fournier, N. and Guillin, A. On the rate of convergence in wasserstein distance of the empirical measure. Probability theory and related fields, 162(3):707–738, 2015.

Boyd, S. P. and Vandenberghe, L. Convex optimization. Cambridge university press, 2004.

Gangbo, W. and McCann, R. J. The geometry of optimal transportation. 1996.

Carlier, G., Duval, V., Peyré, G., and Schmitzer, B. Convergence of entropic schemes for optimal transport and gradient flows. SIAM Journal on Mathematical Analysis, 49(2):1385–1418, 2017.

Ganin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle, H., Laviolette, F., March, M., and Lempitsky, V. Domainadversarial training of neural networks. Journal of machine learning research, 17(59):1–35, 2016.

Carlier, G., Pegon, P., and Tamanini, L. Convergence rate of general entropic optimal transport costs. Calculus of Variations and Partial Differential Equations, 62(4):116, 2023.

Gelman, A. and Meng, X.-L. Simulating normalizing constants: From importance sampling to bridge sampling to path sampling. Statistical science, pp. 163–185, 1998. 10

General Quantification of Covariate and Concept Shifts

Genevay, A., Cuturi, M., Peyré, G., and Bach, F. Stochastic optimization for large-scale optimal transport. Advances in neural information processing systems, 29, 2016.

Pultz, D., Friis, E., Salomon, J., Hallin, P. F., Jørgensen, S. B., Reade, W., and Demkin, M. Novozymes enzyme stability prediction. https://kaggle.com/competitions/ novozymes-enzyme-stability-prediction, 2022. Kaggle.

Glorot, X., Bordes, A., and Bengio, Y. Domain adaptation for large-scale sentiment classification: A deep learning approach. In Proceedings of the 28th international conference on machine learning (ICML-11), pp. 513–520, 2011.

Rame, A., Dancette, C., and Cord, M. Fishr: Invariant gradient variances for out-of-distribution generalization. In International Conference on Machine Learning, pp. 18347–18377. PMLR, 2022.

Gulrajani, I. and Lopez-Paz, D. In search of lost domain generalization. arXiv preprint arXiv:2007.01434, 2020.

Redko, I., Habrard, A., and Sebban, M. Theoretical analysis of domain adaptation with optimal transport. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 737–753. Springer, 2017.

Hájek, A. What conditional probability could not be. Synthese, 137(3):273–323, 2003. Hendrycks, D., Liu, X., Wallace, E., Dziedzic, A., Krishnan, R., and Song, D. Pretrained transformers improve out-ofdistribution robustness. arXiv preprint arXiv:2004.06100, 2020.

Roux, N., Schmidt, M., and Bach, F. A stochastic gradient method with an exponential convergence rate for finite training sets. Advances in neural information processing systems, 25, 2012.

James, G., Witten, D., Hastie, T., Tibshirani, R., et al. An introduction to statistical learning, volume 112. Springer, 2013. Kallenberg, O. and Kallenberg, O. Foundations of modern probability, volume 2. Springer, 1997.

Shen, J., Qu, Y., Zhang, W., and Yu, Y. Wasserstein distance guided representation learning for domain adaptation. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.

Kim, H., Papamakarios, G., and Mnih, A. The lipschitz constant of self-attention. In International Conference on Machine Learning, pp. 5562–5571. PMLR, 2021.

Sugiyama, M., Krauledat, M., and Müller, K.-R. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8(5), 2007.

Krueger, D., Caballero, E., Jacobsen, J.-H., Zhang, A., Binas, J., Zhang, D., Le Priol, R., and Courville, A. Out-ofdistribution generalization via risk extrapolation (rex). In International conference on machine learning, pp. 5815– 5826. PMLR, 2021.

Sun, B. and Saenko, K. Deep coral: Correlation alignment for deep domain adaptation. In Computer vision–ECCV 2016 workshops: Amsterdam, the Netherlands, October 8-10 and 15-16, 2016, proceedings, part III 14, pp. 443– 450. Springer, 2016.

Liu, J., Shen, Z., He, Y., Zhang, X., Xu, R., Yu, H., and Cui, P. Towards out-of-distribution generalization: A survey. arXiv preprint arXiv:2108.13624, 2021.

Verleysen, M. and François, D. The curse of dimensionality in data mining and time series prediction. In International work-conference on artificial neural networks, pp. 758– 770. Springer, 2005.

Long, M., Cao, Y., Wang, J., and Jordan, M. Learning transferable features with deep adaptation networks. In International conference on machine learning, pp. 97– 105. PMLR, 2015.

Virmaux, A. and Scaman, K. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.

Moreno-Torres, J. G., Raeder, T., Alaiz-Rodrı́guez, R., Chawla, N. V., and Herrera, F. A unifying view on dataset shift in classification. Pattern recognition, 45(1):521–530, 2012.

Zhang, X., He, Y., Xu, R., Yu, H., Shen, Z., and Cui, P. Nico++: Towards better benchmarking for domain generalization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16036– 16047, 2023.

Panaretos, V. M. and Zemel, Y. Statistical aspects of wasserstein distances. Annual review of statistics and its application, 6(1):405–431, 2019.

Zhang, Y., Liu, T., Long, M., and Jordan, M. Bridging theory and algorithm for domain adaptation. In International conference on machine learning, pp. 7404–7413. PMLR, 2019.

Pei, Z., Cao, Z., Long, M., and Wang, J. Multi-adversarial domain adaptation. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018. 11

General Quantification of Covariate and Concept Shifts

Zhang, Y., Deng, B., Tang, H., Zhang, L., and Jia, K. Unsupervised multi-class domain adaptation: Theory, algorithms, and practice. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(5):2775–2792, 2020. Zhao, H., Des Combes, R. T., Zhang, K., and Gordon, G. On learning invariant representations for domain adaptation. In International conference on machine learning, pp. 7523–7532. PMLR, 2019. Zou, D., Balan, R., and Singh, M. On lipschitz bounds of general convolutional neural networks. IEEE Transactions on Information Theory, 66(3):1738–1759, 2019.

General Quantification of Covariate and Concept Shifts

A. Related Work Generalization theory under distribution shift is an important and long-standing problem. Researchers usually seek to measure distribution shift using some distribution divergence and derive corresponding learning bounds. Early theoretical works mainly focused on the X (covariate) shift. Ben-David et al. (2006; 2010) used the H-divergence to measure X shift between the source and target domains for binary classification, thereby deriving learning bounds for domain adaptation. Subsequent studies characterized the X shift via maximum mean discrepancy (MMD), leading to new learning bounds and improved domain adaptation algorithms (Long et al., 2015). Redko et al. (2017); Courty et al. (2017); Shen et al. (2018) adopted optimal transport (OT) to characterize X shift and obtained similar bounds. Further studies proposed more complex metrics for the X shift to extend the theory to multiclass classification (Zhang et al., 2019; 2020; El Hamri et al., 2025). Most of these theories focus only on the X shift and follow a similar proof strategy, resulting in a joint error term between the source and target domains, λ = minh ϵS (h) + ϵT (h), which is widely recognized as loose and non-estimable. Our baseline, Zhao et al. (2019), showed that the Y|X (concept) shift is implicitly contained in this joint error term λ, and derived a tighter learning bound by explicitly introducing the Y|X shift instead. Zhang et al. (2023) extended this theory to multiclass classification. We follow this path of explicitly characterizing the Y|X shift, and point out that the existing definition of the Y|X shift becomes ill-defined when the supports of the covariate distributions are mismatched, which still makes the Y|X shift loose and non-estimable. Through entropic optimal transport, we introduce a well-defined γ ∗ -Y|X shift and the corresponding learning bound, which can be rigorously estimated from samples. Our theory can be tighter than existing bounds and further generalizes to a broader tasks, losses, and stochastic labeling. Table 1. Comparison of learning bounds for distribution shift. Bound

Terms

Divergence X shift

Ben-David et al. (2006) Ben-David et al. (2010) Long et al. (2015) Redko et al. (2017) Courty et al. (2017) Shen et al. (2018) Zhao et al. (2019) Zhang et al. (2023) El Hamri et al. (2025) Ours

H-divergence H-divergence MMD OT OT OT H-divergence H-divergence hierarchical OT entropic OT

Y|X shift

✓ ✓ ✓ ✓ estimated XY shift ✓ ✓ ✓ ✓ ✓

Properties Remaining Term

Tight

Estimable General

joint-error λ joint-error λ joint-error λ joint-error λ joint-error λ, kM Φ joint-error λ

✓(ill-defined) ✓(ill-defined)

✓ ✓ ✓

✓

joint-error λ ✓

✓✓

✓

✓✓

✓✓indicates a stronger degree than ✓.

Distribution shift theory often serves as a theoretical framework for domain adaptation and domain generalization, where many algorithms have been developed (Sugiyama et al., 2007; Glorot et al., 2011; Sun & Saenko, 2016; Ganin et al., 2016; Pei et al., 2018; Arjovsky et al., 2019; Krueger et al., 2021; Rame et al., 2022). However, the DomainBed benchmark (Gulrajani & Lopez-Paz, 2020) shows that many algorithms do not outperform standard empirical risk minimization. This calls for tighter and more general theoretical frameworks to explain the generalization failures of these algorithms. In addition, the proposed γ ∗ -Y|X shift takes a nested OT form, whose other mathematical properties have also been studied recently, such as the gradient flow of the Wasserstein-over-Wasserstein distance (Bonet et al., 2025).

B. Technical Tools In this section, we introduce several existing mathematical tools to prove the propositions in Appendix C. B.1. Conditional Probability Definition B.1 (Conditional Probability). Let (Ω, F, P ) be a probability space and X : Ω → X a random variable with distribution PX . For event A ∈ F, a PX -measurable function P (A | X = x) : X → [0, 1] is the conditional probability of 13

General Quantification of Covariate and Concept Shifts

A given X if: Z ∀B ∈ BX , P (A ∩ {X ∈ B}) =

P (A | X = x) dPX (x) B

where BX denotes the Borel σ-algebra on X . The conditional probability is unique almost everywhereR with respect to PX (unique PX -a.e.) (Kallenberg & Kallenberg, 1997). That is, for any PX -null set Z with PX (Z) = 0, Z P (A | X = x) dPX (x) = 0, implying that P (A | X = x) can be assigned arbitrarily on Z without affecting its overall properties. Intuitively, it means discussing conditional probabilities on a null set is meaningless (Hájek, 2003). B.2. McDiarmid’s Inequality Lemma B.2 (McDiarmid’s Inequality). Let Z1 , . . . , Zn be independent random variables taking values in sets Z1 , . . . , Zn , and let F : Z1 × · · · × Zn → R. Assume F satisfies the bounded-differences property: there exist constants c1 , . . . , cn ≥ 0 such that for every i ∈ [n] and any two inputs (z1 , . . . , zn ) and (z1 , . . . , zi′ , . . . , zn ) differing only at the i-th coordinate, F (z1 , . . . , zi , . . . , zn ) − F (z1 , . . . , zi′ , . . . , zn ) ≤ ci . Then for any ε > 0, 2ε2 P F (Z1 , . . . , Zn ) − E F (Z1 , . . . , Zn ) ≥ ε ≤ exp − Pn 2 , i=1 ci and 2ε2 P F (Z1 , . . . , Zn ) − E[F (Z1 , . . . , Zn )] ≥ ε ≤ 2 exp − Pn 2 . i=1 ci B.3. Concentration for Empirical W1 Lemma B.3 (Square-Exponential Moment Implies T1 (Bolley et al., 2007)). Let (X , ρ) be a Polish metric space and µ a Borel probability measure on X . Assume µ admits a square-exponential moment: there exist a > 0 and x0 ∈ X such that Z

exp a ρ(x, x0 )2 dµ(x) < ∞.

Then µ satisfies a T1 (λ) transport-entropy inequality for some λ > 0: for all probability measures ν on X , r W1 (µ, ν) ≤

2 H(ν | µ). λ

Lemma B.4 (Bolley–Guillin Concentration for Empirical W1 (Bolley et al., 2007)). Let µ be a probability measure on (Rd , ∥ · ∥) that satisfies the transport inequality T1 (λ) for some λ > 0, namely for all probability measures ν, r W1 (µ, ν) ≤

2 H(ν | µ), λ

PN where H(ν | µ) denotes the relative entropy. Let µ̂ = N1 i=1 δXi be the empirical measure of i.i.d. samples X1 , . . . , XN ∼ µ. Then for any d′ > d and any λµ ∈ (0, λ), there exists a constant N0 depending only on λµ , d′ , and the squared-exponential moments of µ such that for any ε > 0 and any ′ N ≥ N0 max ε−(d +2) , 1 , we have P W1 (µ, µ̂) > ε

λµ ≤ exp − N ε2 . 2 14

General Quantification of Covariate and Concept Shifts

C. Full proofs C.1. Proof of Lemma 2.2 ′ ′ Proof. Since supp(PX ) \ supp(PX ) ̸= ∅, pick x0 ∈ supp(PX ) \ supp(PX ). By Definition 2.1, x0 ∈ / supp(PX ) implies that there exists an open neighborhood U ⊆ X with x0 ∈ U such that

PX (U ) = 0. ′ ′ On the other hand, x0 ∈ supp(PX ) implies PX (V ) > 0 for every open neighborhood V ∋ x0 , hence in particular ′ PX (U ) > 0. Let Z := U . Then Z ∈ BX and ′ PX (Z) > 0.

PX (Z) = 0,

Let P (A | X = x) : X → [0, 1] be a conditional probability in Definition B.1, i.e., for all B ∈ BX , P A ∩ {X ∈ B} =

Z P (A | X = x) dPX (x). B

For any constant c ∈ [0, 1], define a modified function ( Pe(A | X = x) :=

P (A | X = x), c,

x∈ / Z, x ∈ Z.

For any B ∈ BX , Z

Pe(A | X = x) dPX (x) =

P (A | X = x) dPX (x) +

B\Z

c dPX (x) B∩Z

Z P (A | X = x) dPX (x) + c PX (B ∩ Z)

= B\Z

Z P (A | X = x) dPX (x)

(since PX (Z) = 0)

B\Z

P (A | X = x) dPX (x) = P A ∩ {X ∈ B} ,

= B

so Pe(A | X = x) is also a valid conditional probability of A given X by Definition B.1, as another version of P (A | X = x). ′ Now take expectation under PX :

Z EPX′ [ Pe(A | X = x) ] =

′ Pe(A | X = x) dPX (x)

′ P (A | X = x) dPX (x) +

X \Z

Z =

′ c dPX (x)

Z ′ ′ P (A | X = x) dPX (x) + c PX (Z).

X \Z ′ Since PX (Z) > 0 and c ∈ [0, 1] is arbitrary, the value of EPX′ [P (A | X = x)] can be changed by choosing different c while preserving the defining property of conditional probability under PX . Hence EPX′ [P (A | X = x)] is arbitrary.

Remark The above proof shows that support mismatch leads to arbitrariness. Broadly speaking, support mismatch commonly breaks the rigor of theoretical analyses. Some studies explicitly exclude it from analysis by extra assumptions, such as done in the absolute continuity in measure theory (Duncan, 1970), the positivity assumption in causal inference (Cole & Frangakis, 2009), or support overlap in importance sampling (Gelman & Meng, 1998). 15

General Quantification of Covariate and Concept Shifts

C.2. Proof of Corollary 3.3 Proof. By Definition 3.2, h i γ∗ SCpt = E(xS ,xT )∼γ ∗ W1 DYS |X=xS , DYT |X=xT . Under deterministic labeling, DYS |X=xS = δfS (xS ) and DYT |X=xT = δfT (xT ) , hence Spair (xS , xT ) = W1 δfS (xS ) , δfT (xT ) . For any a, b ∈ Y, any coupling π ∈ Γ(δa , δb ) must satisfy π({a} × Y) = 1 and π(Y × {b}) = 1, hence π = δ(a,b) is the unique coupling. Therefore, Z Z W1 (δa , δb ) = inf ρY (y1 , y2 ) dπ = ρY (y1 , y2 ) dδ(a,b) (y1 , y2 ) = ρY (a, b). π∈Γ(δa ,δb )

Applying this with a = fS (xS ) and b = fT (xT ) yields Spair (xS , xT ) = ρY (fS (xS ), fT (xT )), and thus γ∗ SCpt = E(xS ,xT )∼γ ∗ ρY (fS (xS ), fT (xT )) , as claimed. C.3. Proof of Lemma 3.4 T S T S T S . and its second marginal is DX , hence its first marginal is DX and DX ) is a coupling of DX , DX Proof. Any γ ∈ Γ(DX T S T S ). ) or xT ∈ / supp(DX ). Then either xS ∈ / supp(DX ) × supp(DX Take any (xS , xT ) ∈ / supp(DX S S If xS ∈ / supp(DX ), by Definition 2.1 there exists an open neighborhood U ⊆ X of xS such that DX (U ) = 0. Since the S first marginal of γ is DX , S γ(U × X ) = DX (U ) = 0.

In particular, for any open neighborhood V of xT we have γ(U × V ) ≤ γ(U × X ) = 0, so γ(U × V ) = 0. Thus, taking the product open set U × V containing (xS , xT ), we conclude that (xS , xT ) ∈ / supp(γ) by Definition 2.1 applied on the product topology of X × X . T T The case xT ∈ / supp(DX ) is symmetric: there exists an open V ∋ xT with DX (V ) = 0, and using the second marginal of γ gives γ(X × V ) = 0, hence γ(U × V ) = 0 for any open U ∋ xS , implying (xS , xT ) ∈ / supp(γ). S T Therefore every point outside supp(DX ) × supp(DX ) is outside supp(γ), i.e., S T supp(γ) ⊆ supp(DX ) × supp(DX ).

C.4. Proof of Lemma 3.5 S T Proof. Let ν := DX ⊗ DX and consider the entropic optimal transport objective Z S T J(γ) := ρX (xS , xT ) dγ(xS , xT ) + β H(γ | ν), γ ∈ Γ(DX , DX ).

S T We claim that J is strictly convex over the convex set Γ(DX , DX ). Indeed, the transport cost term γ 7→ dγ γ. For the entropy term, write r = dν ; then Z H(γ | ν) = r log r dν. S T For any γ1 , γ2 ∈ Γ(DX , DX ) with γ1 ̸= γ2 , by Lemma 3.4, S T supp(γ1 ) ⊆ supp(DX ) × supp(DX ) = supp(ν).

ρX dγ is linear in

General Quantification of Covariate and Concept Shifts S T supp(γ2 ) ⊆ supp(DX ) × supp(DX ) = supp(ν).

Because φ(t) = t log t is strictly convex on [0, ∞), for and any λ ∈ (0, 1), H λγ1 + (1 − λ)γ2 | ν < λH(γ1 | ν) + (1 − λ)H(γ2 | ν), hence (multiplying by β > 0) the whole objective satisfies J λγ1 + (1 − λ)γ2 < λJ(γ1 ) + (1 − λ)J(γ2 ). S T Now suppose, toward a contradiction, that there are two distinct optimal couplings γ1 ̸= γ2 minimizing J over Γ(DX , DX ). S T By convexity of Γ(DX , DX ), their mixture γλ := λγ1 + (1 − λ)γ2 is feasible. Strict convexity then yields

J(γλ ) < λJ(γ1 ) + (1 − λ)J(γ2 ) = inf J(γ), γ∈Γ

a contradiction. Therefore the optimizer γ ∗ is unique. C.5. Proof of Lemma 3.6 Proof. When β = 0, Definition 3.1 reduces to the Wasserstein-1 problem Z inf ρX (xS , xT ) dγ(xS , xT ), S ,D T ) γ∈Γ(DX X

where ρX is a metric, hence ρX ≥ 0 and ρX (xS , xT ) = 0 if xS = xT . S , i.e., Consider the diagonal (identity) coupling γ̄ := (Id, Id)# DX Z S γ̄(A) = 1{(x,x)∈A} dDX (x). S S ), and its transport cost is , DX It is immediate that γ̄ ∈ Γ(DX Z Z S ρX (xS , xT ) dγ̄(xS , xT ) = ρX (x, x) dDX (x) = 0.

Therefore the optimal value is at most 0, hence equals 0. S S ) be any optimal coupling. Then , DX Let γ ∗ ∈ Γ(DX Z 0 = ρX (xS , xT ) dγ ∗ (xS , xT ).

Since the integrand is nonnegative, this implies ρX (xS , xT ) = 0 holds γ ∗ -almost surely, i.e., (xS , xT ) ∈ ζ := {(x, x) : x ∈ X } γ ∗ -a.s. Hence supp(γ ∗ ) ⊆ ζ. S Finally, because γ ∗ is supported on ζ and has first marginal DX , for every measurable A ⊆ X × X we have Z S S γ ∗ (A) = γ ∗ (A ∩ ζ) = 1{(x,x)∈A} dDX (x) = (Id, Id)# DX (A), S which proves γ ∗ = (Id, Id)# DX and the stated equivalent form.

C.6. Proof of Theorem 3.7 Proof. For β > 0, Lemma 3.5 ensures that the entropic optimal transport coupling γ ∗ in Definition 3.1 is unique. Hence γ∗ any potential ambiguity of SCpt can only come from the choice of versions of the conditional distributions. eS Given any two versions of the source conditionals {DYS |X=x }x∈X and {D Y |X=x }x∈X , and any two versions of the target T T S S e e eT conditionals {D }x∈X and {D }x∈X , such that D =D holds DS -a.e., and DT =D Y |X=x

Y |X=x

General Quantification of Covariate and Concept Shifts T S T holds DX -a.e. Therefore, there exist measurable sets ES , ET ⊆ X with DX (ES ) = 0 and DX (ET ) = 0 such that the equalities hold for all x ∈ / ES and all x ∈ / ET , respectively.

Define the γ ∗ -Y|X shift under the two choices as Z γ∗ SCpt := W1 DYS |X=xS , DYT |X=xT dγ ∗ (xS , xT ), ∗

γ SeCpt :=

∗ eS eT W1 D Y |X=xS , DY |X=xT dγ (xS , xT ).

Let E := (ES × X ) ∪ (X × ET ). For any (xS , xT ) ∈ E c we have xS ∈ / ES and xT ∈ / ET , hence eT DYT |X=xT = D Y |X=xT ,

eS DYS |X=xS = D Y |X=xS , which implies

eS eT W1 DYS |X=xS , DYT |X=xT = W1 D Y |X=xS , DY |X=xT

for all (xS , xT ) ∈ E c .

Consequently, the difference between the two versions satisfies Z h i ∗ γ∗ γ∗ eS eT SCpt − SeCpt = W1 DYS |X=xS , DYT |X=xT − W1 D dγ (xS , xT ), Y |X=xS , DY |X=xT E

∗

S T By Lemma 3.4, supp(γ ) ⊆ supp(DX ) × supp(DX ), so γ ∗ never places mass outside the support product region. ∗ S T Furthermore, since γ ∈ Γ(DX , DX ), hence S γ ∗ (ES × X ) = DX (ES ) = 0,

and therefore γ ∗ (E) = 0, and thus

T γ ∗ (X × ET ) = DX (ET ) = 0,

∗

γ γ SCpt − SeCpt = 0. ∗

∗

γ γ Therefore SCpt does not depend on the choice of versions of the conditional distributions. This proves that SCpt is unique, S T regardless of whether supp(DX ) ̸= supp(DX ).

C.7. Proof of Proposition 3.8 T S , Lemma 3.6 gives that the optimal coupling collapses to the diagonal: = DX Proof. Since β = 0 and DX S γ ∗ = (Id, Id)# DX .

γ∗ S |fS (x) − fT (x)| = Ex∼D T |fS (x) − fT (x)| , SCpt = Ex∼DX X as claimed. C.8. Proof of Corollary 3.10 Proof. Take any y1 , y2 ∈ Y and x1 , x2 ∈ X . By the separate (Lℓ , L′ℓ )-Lipschitzness of ℓ, ℓ(y1 , h(x1 )) − ℓ(y2 , h(x2 )) ≤ Lℓ ρY (y1 , y2 ) + L′ℓ ρY ′ h(x1 ), h(x2 ) . By the Lh -Lipschitzness of h, we further have ρY ′ h(x1 ), h(x2 ) ≤ Lh ρX (x1 , x2 ). Substituting this bound yields ℓ(y1 , h(x1 )) − ℓ(y2 , h(x2 )) ≤ Lℓ ρY (y1 , y2 ) + (Lh L′ℓ ) ρX (x1 , x2 ), which is exactly the separate (Lℓ , Lh L′ℓ )-Lipschitz condition for the composite function ℓ y, h(x) . 18

General Quantification of Covariate and Concept Shifts

C.9. Proof of Lemma 3.11 Proof. Write the two expectations explicitly: Z S S EDXY [G] = G(yS , xS ) dDXY (xS , yS ),

Z T EDXY [G] =

X ×Y

T G(yT , xT ) dDXY (xT , yT ).

X ×Y

S T S Let γXY ∈ Γ(DXY , DXY ) be any coupling on (X × Y) × (X × Y), i.e., its first marginal is DXY and second marginal is T DXY . Hence, for any integrable functions φ, ψ, Z Z S φ(xS , yS ) dγXY (xS , yS , xT , yT ) = φ(xS , yS ) dDXY (xS , yS ), Z Z T ψ(xT , yT ) dγXY (xS , yS , xT , yT ) = ψ(xT , yT ) dDXY (xT , yT ).

Applying these identities to φ(xS , yS ) = G(yS , xS ) and ψ(xT , yT ) = G(yT , xT ) gives Z Z S T S T EDXY [G] − EDXY [G] = G(yS , xS ) dDXY (xS , yS ) − G(yT , xT ) dDXY (xT , yT ) Z Z = G(yS , xS ) dγXY (xS , yS , xT , yT ) − G(yT , xT ) dγXY (xS , yS , xT , yT ) Z = G(yS , xS ) − G(yT , xT ) dγXY (xS , yS , xT , yT ). R R Taking absolute values and using | f dµ| ≤ |f | dµ yields Z S T EDXY [G] − EDXY [G] ≤ G(yS , xS ) − G(yT , xT ) dγXY (xS , yS , xT , yT ). By the separate (LY , LX )-Lipschitz property of G, we have G(yS , xS ) − G(yT , xT ) ≤ LY ρY (yS , yT ) + LX ρX (xS , xT ). Substituting and splitting the integral, Z S T EDXY [G] − EDXY [G] ≤ LY ρY (yS , yT ) + LX ρX (xS , xT ) dγXY (xS , yS , xT , yT ) Z Z = LY ρY (yS , yT ) dγXY (xS , yS , xT , yT ) + LX ρX (xS , xT ) dγXY (xS , yS , xT , yT ) = LY EγXY ρY (yS , yT ) + LX EγXY ρX (xS , xT ) , as claimed. C.10. Proof of Lemma 3.12 S T Proof. We show that the first marginal of γXY equals DXY and the second marginal equals DXY .

Take any measurable A ⊆ X and B ⊆ Y. By the definition of γXY , Z γXY (A × B) × (X × Y) = γY∗ |(xS ,xT ) (B × Y) 1{xS ∈A} dγ ∗ (xS , xT ).

First marginal.

(xS ,xT )∈X ×X

γXY (A × B) × (X × Y) =

1{xS ∈A} DYS |X=xS (B) dγ ∗ (xS , xT ).

S Finally, since the first marginal of γ ∗ is DX , integrating out xT yields Z S S γXY (A × B) × (X × Y) = DYS |X=xS (B) dDX (xS ) = DXY (A × B), xS ∈A

General Quantification of Covariate and Concept Shifts

Second marginal.

Similarly, for measurable A ⊆ X and B ⊆ Y, Z γXY (X × Y) × (A × B) = γY∗ |(xS ,xT ) (Y × B) 1{xT ∈A} dγ ∗ (xS , xT ) Z = 1{xT ∈A} DYT |X=xT (B) dγ ∗ (xS , xT ) Z T T = DYT |X=xT (B) dDX (xT ) = DXY (A × B). xT ∈A

S T Therefore γXY ∈ Γ(DXY , DXY ).

C.11. Proof of Theorem 3.13 Proof. Define the composite function G(y, x) := ℓ y, h(x) ,

(y, x) ∈ Y × X .

By Corollary 3.10, G is separately (Lℓ , Lh L′ℓ )-Lipschitz, i.e., G(y1 , x1 ) − G(y2 , x2 ) ≤ Lℓ ρY (y1 , y2 ) + (Lh L′ℓ ) ρX (x1 , x2 ). Hence ϵT (h) = ϵS (h) + ϵT (h) − ϵS (h) ≤ ϵS (h) + ϵT (h) − ϵS (h) T S = ϵS (h) + EDXY [G] − EDXY [G] .

S T Step 1: construct a specific joint coupling. Let γ ∗ ∈ Γ(DX , DX ) be the optimal coupling in Definition 3.1. For each ∗ S T (xS , xT ), let γY |(xS ,xT ) ∈ Γ(DY |X=xS , DY |X=xT ) be an optimal coupling of Spair (xS , xT ) in Definition 3.2, define the joint distribution of couplings

γXY (dxS , dxT , dyS , dyT ) := γ ∗ (dxS , dxT ) γY∗ |(xS ,xT ) (dyS , dyT ). S T By Lemma 3.12, γXY ∈ Γ(DXY , DXY ).

Apply Lemma 3.11 to G with the coupling γXY , we obtain: S T EDXY [G] − EDXY [G] ≤ (Lh L′ℓ ) EγXY ρX (xS , xT ) + Lℓ EγXY ρY (yS , yT ) .

Step 2: apply Lemma 3.11.

It remains to bound the two expectations on the right-hand side. Step 3: bound the X -term by SCov .

By the construction of γXY , Z EγXY ρX (xS , xT ) = ρX (xS , xT ) γ ∗ (dxS , dxT ) γY∗ |(xS ,xT ) (dyS , dyT ) Z = ρX (xS , xT ) γ ∗ (dxS , dxT ) = Eγ ∗ ρX (xS , xT ) .

S T Since SCov = Wβ (DX , DX ) and γ ∗ is optimal, Z Z S T SCov = ρX (xS , xT ) dγ ∗ (xS , xT ) + β H γ ∗ | DX ⊗ DX ≥ ρX (xS , xT ) dγ ∗ (xS , xT ),

because β ≥ 0 and relative entropy is nonnegative. Therefore, EγXY ρX (xS , xT ) = Eγ ∗ ρX (xS , xT ) ≤ SCov . 20

General Quantification of Covariate and Concept Shifts ∗

γ Step 4: identify the Y-term with SCpt .

Again by the construction of γXY , Z

ρY (yS , yT ) γ ∗ (dxS , dxT ) γY∗ |(xS ,xT ) (dyS , dyT ) Z Z ∗ = ρY (yS , yT ) dγY |(xS ,xT ) (yS , yT ) dγ ∗ (xS , xT ) X ×X Y×Y Z = W1 DYS |X=xS , DYT |X=xT dγ ∗ (xS , xT )

EγXY ρY (yS , yT ) =

X ×X

γ∗ = E(xS ,xT )∼γ ∗ Spair (xS , xT ) = SCpt , Step 5: conclude the bound.

Combining Steps 2–4 yields ∗

γ S T . EDXY [G] − EDXY [G] ≤ (Lh L′ℓ ) SCov + Lℓ SCpt

Substituting this into the earlier inequality for ϵT (h) gives ∗

γ ϵT (h) ≤ ϵS (h) + (Lh L′ℓ ) SCov + Lℓ SCpt ,

which proves the theorem. C.12. Proof of Theorem 4.2 Proof. We work with β = 0, hence Wβ = W1 . For brevity, denote S µ := DX ,

T ν := DX ,

c := W1 (µ, ν).

Let µ̂′ , µ̂′′ (resp. ν̂ ′ , ν̂ ′′ ) be the two half-sample empirical measures constructed in Definition 4.1. They are independent within each domain because they are built from disjoint halves of i.i.d. samples. A useful inequality.

Indeed, if a ≥ b then

We will use the elementary fact: for any a, b ≥ 0, p √ √ a − b ≤ |a − b|. √

a−

√

√ ≤ √a−b = b = √a−b a−b a+ b

√

a − b, and the case b ≥ a is symmetric.

Step 1: rewrite the debiased estimator and introduce an auxiliary statistic.

Define

S := 21 W1 (µ̂′ , ν̂ ′ )2 + 12 W1 (µ̂′′ , ν̂ ′′ )2 − 21 W1 (µ̂′ , µ̂′′ )2 − 12 W1 (ν̂ ′ , ν̂ ′′ )2 . Then Definition 4.1 (with β = 0) gives p d S d T W1deb D |S|. X , DX = Introduce the auxiliary random variable T := Step 2: reduce {|W1deb − c| > ε} to an event on T .

S − c2 .

First note the deterministic inequality

|S| − c2 ≤ |S − c2 | = T, which holds because c2 ≥ 0. Hence, using the inequality in the first paragraph, q √ p √ |W1deb − c| = |S| − c2 ≤ |S| − c2 ≤ T . Therefore, for any ε > 0,

√ P |W1deb − c| > ε ≤ P T > ε = P T > ε2 . 21

General Quantification of Covariate and Concept Shifts

This bound is always valid and is particularly useful when c is small. When c ≥ ε, we can obtain a complementary reduction by squaring the deviation event. Indeed, |W1deb − c| > ε implies either W1deb > c + ε or W1deb < c − ε. In both cases, (W1deb )2 − c2 > (c + ε)2 − c2 = 2cε + ε2

c2 − (c − ε)2 = 2cε − ε2 ,

hence in particular (W1deb )2 − c2 > 2cε − ε2 . Since (W1deb )2 = |S|, we have {|W1deb − c| > ε} ⊆

|S| − c2 > 2cε − ε2 ⊆ {T > 2cε − ε2 }.

Combining both regimes, define the threshold ( ε2 , c < ε, t(c, ε) := 2cε − ε2 , c ≥ ε, so that for all c ≥ 0, P |W1deb − c| > ε ≤ P T > t(c, ε) . Step 3: bound T by marginal empirical Wasserstein errors. for | · |:

Start from the definition of T and use the triangle inequality

′ ′ 2 ′′ ′′ 2 ′ ′′ 2 ′ ′′ 2 2 1 1 1 1 2 W1 (µ̂ , ν̂ ) + 2 W1 (µ̂ , ν̂ ) − 2 W1 (µ̂ , µ̂ ) − 2 W1 (ν̂ , ν̂ ) − c

T =

≤ 21 W1 (µ̂′ , ν̂ ′ )2 − c2 + 12 W1 (µ̂′′ , ν̂ ′′ )2 − c2 + 21 W1 (µ̂′ , µ̂′′ )2 + 12 W1 (ν̂ ′ , ν̂ ′′ )2 . Step 3.1: control the cross-domain square terms. Let u := W1 (µ̂′ , ν̂ ′ ). Then |u2 − c2 | = |u − c| |u + c| ≤ |u − c| (|u − c| + 2c) = 2c|u − c| + |u − c|2 . Multiplying by 21 gives

2 2 1 2 1 2 |u − c | ≤ c|u − c| + 2 |u − c| .

Applying this with u = W1 (µ̂′ , ν̂ ′ ) and again with u = W1 (µ̂′′ , ν̂ ′′ ) yields 2

′ ′ 2 2 1 2 W1 (µ̂ , ν̂ ) − c

≤ c W1 (µ̂′ , ν̂ ′ ) − c + 12 W1 (µ̂′ , ν̂ ′ ) − c ,

′′ ′′ 2 2 1 2 W1 (µ̂ , ν̂ ) − c

≤ c W1 (µ̂′′ , ν̂ ′′ ) − c + 21 W1 (µ̂′′ , ν̂ ′′ ) − c .

Step 3.2: relate |W1 (µ̂′ , ν̂ ′ ) − c| to W1 (µ, µ̂′ ) and W1 (ν, ν̂ ′ ). Using the triangle inequality for W1 , W1 (µ̂′ , ν̂ ′ ) ≤ W1 (µ̂′ , µ) + W1 (µ, ν) + W1 (ν, ν̂ ′ ) = W1 (µ̂′ , µ) + c + W1 (ν, ν̂ ′ ), hence W1 (µ̂′ , ν̂ ′ ) − c ≤ W1 (µ̂′ , µ) + W1 (ν, ν̂ ′ ). Similarly, c = W1 (µ, ν) ≤ W1 (µ, µ̂′ ) + W1 (µ̂′ , ν̂ ′ ) + W1 (ν̂ ′ , ν), so c − W1 (µ̂′ , ν̂ ′ ) ≤ W1 (µ, µ̂′ ) + W1 (ν, ν̂ ′ ). Combining the two inequalities, W1 (µ̂′ , ν̂ ′ ) − c ≤ W1 (µ, µ̂′ ) + W1 (ν, ν̂ ′ ). The same argument gives W1 (µ̂′′ , ν̂ ′′ ) − c ≤ W1 (µ, µ̂′′ ) + W1 (ν, ν̂ ′′ ). 22

General Quantification of Covariate and Concept Shifts

Step 3.3: relate W1 (µ̂′ , µ̂′′ ) and W1 (ν̂ ′ , ν̂ ′′ ) to the same marginal errors. Again by the triangle inequality, W1 (µ̂′ , µ̂′′ ) ≤ W1 (µ̂′ , µ) + W1 (µ, µ̂′′ ),

W1 (ν̂ ′ , ν̂ ′′ ) ≤ W1 (ν̂ ′ , ν) + W1 (ν, ν̂ ′′ ).

Step 3.4: assemble the bound. Introduce the shorthand nonnegative random variables u′ := W1 (µ, µ̂′ ),

u′′ := W1 (µ, µ̂′′ ),

v ′ := W1 (ν, ν̂ ′ ),

v ′′ := W1 (ν, ν̂ ′′ ).

Then Steps 3.1–3.3 imply T ≤ c(u′ + v ′ ) + 21 (u′ + v ′ )2 + c(u′′ + v ′′ ) + 21 (u′′ + v ′′ )2 + 12 (u′ + u′′ )2 + 12 (v ′ + v ′′ )2 . Now use (a + b)2 ≤ 2a2 + 2b2 repeatedly to simplify: ′ ′ 2 ′2 ′2 1 2 (u + v ) ≤ u + v ,

′′ ′′ 2 ′′2 1 + v ′′2 , 2 (u + v ) ≤ u

′ ′′ 2 ′2 ′′2 1 2 (u + u ) ≤ u + u ,

′′ 2 ′2 ′′2 1 ′ 2 (v + v ) ≤ v + v .

Substituting yields the clean bound T ≤ c(u′ + u′′ + v ′ + v ′′ ) + 2 u′2 + u′′2 + v ′2 + v ′′2 . In particular, on the event {u′ ≤ ε0 , u′′ ≤ ε0 , v ′ ≤ ε0 , v ′′ ≤ ε0 }, we have T ≤ 4cε0 + 8ε20 . Hence, {T > 4cε0 + 8ε20 } ⊆ {u′ > ε0 } ∪ {u′′ > ε0 } ∪ {v ′ > ε0 } ∪ {v ′′ > ε0 }, and by the union bound, P T > 4cε0 + 8ε20 ≤ P(u′ > ε0 ) + P(u′′ > ε0 ) + P(v ′ > ε0 ) + P(v ′′ > ε0 ). Step 4: apply traditional concentration inequality. By assumption, µ and ν have finite squared-exponential moments on Rd . Lemma B.3 and B.4 implies that there exist constants λS , λT > 0, depending only on the squared-exponential moments of µ and ν respectively, such that for any ε0 > 0 there exists N with the following property: whenever NS /2 ≥ N and NT /2 ≥ N , λ N ε2 λ N ε2 P W1 (µ, µ̂′ ) > ε0 ≤ exp − S 4S 0 , P W1 (µ, µ̂′′ ) > ε0 ≤ exp − S 4S 0 , and similarly λ N ε2 P W1 (ν, ν̂ ′′ ) > ε0 ≤ exp − T 4T 0 .

λ N ε2 P W1 (ν, ν̂ ′ ) > ε0 ≤ exp − T 4T 0 , Therefore, for NS , NT large enough,

λ N ε2 λ N ε2 P T > 4cε0 + 8ε20 ≤ 2 exp − S 4S 0 + 2 exp − T 4T 0 . Step 5: choose ε0 to match the deviation level ε.

Recall from Step 2 that (

P |W1deb − c| > ε

≤ P T > t(c, ε) ,

t(c, ε) =

ε2 , c < ε, 2 2cε − ε , c ≥ ε.

We now select ε0 so that 4cε0 + 8ε20 = t(c, ε). Let a := c/ε ≥ 0. Solving this quadratic in the two regimes yields the closed-form expression ε20 =

V (a) ε2 , 8 23

General Quantification of Covariate and Concept Shifts

where

( √ a2 + 1 − a a2 + 2, a < 1, √ V (a) = a2 + 2a − 1 − a a2 + 4a − 2, a ≥ 1. √ Define Vε := V c/ε = V W1 (µ, ν)/ε . As shown in the “Range of V (a)” derivation, Vε ∈ [2 − 3, 2) and depends only on c/ε.

With this choice, {T > t(c, ε)} = {T > 4cε0 + 8ε20 }, hence P |W1deb − c| > ε ≤ P T > 4cε0 + 8ε20 λ N ε2 λ N ε2 ≤ 2 exp − S 4S 0 + 2 exp − T 4T 0 2 2 T Vε ε S Vε ε + 2 exp − λT N32 . = 2 exp − λS N32 S T Finally, note c = W1 (µ, ν) = Wβ (DX , DX ) when β = 0, and W1deb = Wβdeb when β = 0, so the above inequality is exactly (10). This completes the proof.

Range of V (a).

Recall ( V (a) =

√ V1 (a) := a2 + 1 − a a2 + 2, 0 ≤ a < 1, √ V2 (a) := a2 + 2a − 1 − a a2 + 4a − 2, a ≥ 1.

First, the two branches agree at a = 1: V1 (1) = 2 −

√

V2 (1) = 2 −

√

(i) Monotonicity on [0, 1]. Differentiate V1 on (0, 1): V1′ (a) = 2a −

p a2 2(a2 + 1) a2 + 2 − √ = 2a − √ . a2 + 2 a2 + 2

√ For a ≥ 0, we have a a2 + 2 ≤ a2 + 1 since (a2 + 1)2 − a2 (a2 + 2) = 1 > 0. 2

Thus √aa2+1 ≥ a, which implies V1′ (a) ≤ 0 on (0, 1). Hence V1 is decreasing on [0, 1], so +2 √ V1 (a) ∈ V1 (1), V1 (0) = [ 2 − 3, 1 ]. (ii) Monotonicity on [1, ∞). Let s(a) :=

√

a2 + 4a − 2. Then for a > 1,

V2′ (a) = 2a + 2 − s(a) −

a(a + 2) . s(a)

Since s(a) > 0, the inequality V2′ (a) ≥ 0 is equivalent to (a + 1)s(a) ≥ a2 + 3a − 1. Squaring both sides (both sides are nonnegative for a ≥ 1) gives (a + 1)2 (a2 + 4a − 2) ≥ (a2 + 3a − 1)2 , and the difference factors as (a + 1)2 (a2 + 4a − 2) − (a2 + 3a − 1)2 = 3(2a − 1) ≥ 0 24

(a ≥ 1).

General Quantification of Covariate and Concept Shifts

Therefore V2′ (a) ≥ 0 for all a ≥ 1, i.e., V2 is increasing on [1, ∞). In particular, √ (a ≥ 1). V2 (a) ≥ V2 (1) = 2 − 3 (iii) Upper bound V (a) < 2 and lima→∞ V (a) = 2. For a ≥ 1, write s(a) = (a + 2 − s(a))(a + 2 + s(a)) = (a + 2)2 − s(a)2 = 6,

p (a + 2)2 − 6. Then

a + 2 − s(a) =

6 . a + 2 + s(a)

Using V2 (a) = a(a + 2) − 1 − a s(a), we get 2 − V2 (a) = 3 − a (a + 2 − s(a)) = 3 −

6a . a + 2 + s(a)

√ 6a Since s(a) > a − 2 for a ≥ 1 (indeed s(a) = a2 + 4a − 2 > a), we have a + 2 + s(a) > 2a, hence a+2+s(a) < 3, which implies 2 − V2 (a) > 0 and thus V2 (a) < 2 for every finite a. Moreover, as a → ∞, one has a + 2 + s(a) ∼ 2a, hence 6a a+2+s(a) → 3 and therefore V2 (a) → 2. Conclusion. Combining (i)–(iii), the global minimum is attained at a = 1 with √ min V (a) = 2 − 3, a≥0

and the supremum equals 2 but is not attained: V (a) ∈ [ 2 −

√

3, 2 ),

a ≥ 0.

C.13. Proof of Lemma 4.4 Proof. We follow (Eckstein & Nutz, 2022). Recall that the entropically regularized OT problem is Z ε Sent (µ, ν, c) := inf c dπ + ε KL(π ∥ µ ⊗ ν), π∈Π(µ,ν)

and for fixed ε > 0 one may assume ε = 1 by dividing the objective by ε and using the cost c/ε. Step 1 (Reduction to ε = 1 and identification of L = 1/β). Let c(x1 , x2 ) := ρX (x1 , x2 ). The β-entropic OT objective Z c dπ + β KL(π ∥ µ ⊗ ν) has the same optimizer as Z

1 c dπ + KL(π ∥ µ ⊗ ν), β

since the two objectives differ only by a multiplicative factor β. Hence the optimal coupling for Wβ (µ, ν) equals the 1 optimizer of Sent (µ, ν, cβ ) with cβ := c/β. Consider the product space X × X with metric ρ (x1 , x2 ), (x′1 , x′2 ) := ρX (x1 , x′1 ) + ρX (x2 , x′2 ). By the triangle inequality, c(x1 , x2 ) − c(x′1 , x′2 ) = ρX (x1 , x2 ) − ρX (x′1 , x′2 ) ≤ ρX (x1 , x′1 ) + ρX (x2 , x′2 ) = ρ((x1 , x2 ), (x′1 , x′2 )), so c is 1-Lipschitz w.r.t. ρ, and therefore cβ = c/β satisfies the Lipschitz condition (AL) of Eckstein & Nutz (2022) with constant 1 L = Lip(cβ ) = . β 25

General Quantification of Covariate and Concept Shifts

d d S T ∗ ∗ S T Step 2 (Apply Theorem 3.11). Let µ := DX , ν := DX , and similarly µ̂ := D X , ν̂ := DX . Let γ and γ̂ be the optimizers 1 1 of Sent (µ, ν, cβ ) and Sent (µ̂, ν̂, cβ ), respectively. Assume µ and ν have finite squared-exponential moments. Then by Lemma 3.10(ii) in Eckstein & Nutz (2022), the pair of marginals satisfies the inequality (I1 ) with some finite constant C1 > 0 depending only on these squared-exponential moments. Now apply Theorem 3.11 of Eckstein & Nutz (2022) with N = 2 and p = q = 1. Since N 1/q−1/p = 1, we obtain W1 (γ ∗ , γ̂ ∗ ) ≤ ∆ + C1 (2L∆)1/2 , ∆ := W1 (µ, ν); (µ̂, ν̂) , . Step 3 (Upper bound ∆ by Λ). Let πS be an optimal coupling between µ and µ̂, and πT an optimal coupling between ν and ν̂. Then πS ⊗ πT is a coupling between (µ, ν) and (µ̂, ν̂) on X × X , and its expected ρ-cost equals Z Z ′ ′ ρX (x, x ) dπS (x, x ) + ρX (y, y ′ ) dπT (y, y ′ ) = W1 (µ, µ̂) + W1 (ν, ν̂) =: Λ. Taking the infimum over all couplings yields ∆ ≤ Λ. Therefore, ∗

√

⇐⇒

2 . C1 = p λγ ∗

∗

W1 (γ , γ̂ ) ≤ Λ + C1 2LΛ = Λ + C1

2 Λ. β

√ Step 4 (Definition of λγ ∗ and the factor 2 2). Define λγ ∗ :=

4 C12

Then r C1

2 2 Λ= p β λγ ∗

s 2√ 2 √ Λ=2 Λ, β βλγ ∗

which yields the claimed bound. Finally, λγ ∗ > 0 depends only on the squared-exponential moments of µ and ν because C1 does via Lemma 3.10(ii) (Eckstein & Nutz, 2022). C.14. Proof of Theorem 4.5 Proof. Let S µ := DX ,

T ν := DX ,

NS X d S = 1 µ̂ := D δ (S) , X NS i=1 Xi

NT X d T = 1 ν̂ := D δ (T ) . X NT j=1 Xj

∗ S ×NT Let γ ∗ be the population entropic OT coupling between µ and ν (with β > 0), and let γ̂ ∗ = (γ̂ij ) ∈ RN be the discrete + optimal coupling solving Wβ (µ̂, ν̂). It satisfies the marginal constraints NT X

∗ γ̂ij =

j=1

1 NS

NS X

(∀i),

∗ γ̂ij =

i=1

1 NT

(∀j).

Associate to γ̂ ∗ a probability measure on Rd × Rd : γ̄ ∗ :=

NS X NT X i=1 j=1

∗ γ̂ij δ(X (S) , X (T ) ) ∈ Γ(µ̂, ν̂). i

Throughout, Wasserstein–1 distances on Rd use the Euclidean norm ∥ · ∥, and on Rd × Rd we use the metric ρ (xS , xT ), (x′S , x′T ) := ∥xS − x′S ∥ + ∥xT − x′T ∥. 26

General Quantification of Covariate and Concept Shifts

Step 1: define the population quantity we will concentrate around and the bias ∆. Define the function f : Rd × Rd → R+ by f (xS , xT ) := E yS ∼DS ∥yS − yT ∥ . , yT ∼D T Y |X=xS

d′

Y |X=xT

′

Since Y ⊂ R is bounded with M = supy,y′ ∈Y ∥y − y ∥, we have 0 ≤ f (xS , xT ) ≤ M for all (xS , xT ). Recall that

γ∗ SCpt = E(xS ,xT )∼γ ∗ Spair (xS , xT ) .

Spair (xS , xT ) = W1 DYS |X=xS , DYT |X=xT ,

Because f (xS , xT ) is the transport cost under the independent coupling DYS |xS ⊗ DYT |xT , while Spair (xS , xT ) is the infimum over all couplings, we have f (xS , xT ) − Spair (xS , xT ) ≥ 0. Define the (constant) bias term h i ∆ := E(xS ,xT )∼γ ∗ f (xS , xT ) − Spair (xS , xT ) . Then

γ∗ SCpt + ∆ = Eγ ∗ f (xS , xT ) .

Hence it suffices to prove concentration of ŜCpt around Eγ ∗ [f ]. Step 2: decompose the error into a Y -noise term and a coupling-stability term. ŜCpt =

NS X NT X

(S)

(T )

∥Yi

− Yj

By Definition 4.3,

∗ ∥ γ̂ij .

i=1 j=1

Add and subtract Eγ̄ ∗ [f ]: |ŜCpt − Eγ ∗ [f ]| ≤ ŜCpt − Eγ̄ ∗ [f ] + Eγ̄ ∗ [f ] − Eγ ∗ [f ] . {z } | {z } | =:A

=:B

We will bound A by McDiarmid’s inequality and B by Lipschitzness of f and stability of entropic OT. (S)

(T ) NT }j=1 .

S Condition on all covariates {Xi }N i=1 and {Xj

Step 3: concentration of A via McDiarmid inequality B.2.

(S)

Under this conditioning, γ̂ ∗ is fixed (it depends only on the covariates), and the labels {Yi (S) (T ) (T ) Yi ∼ DS } are independent with Yj ∼ DT (S) , and similarly {Yj (T ) . Y |X=Xi

} are independent with

Y |X=Xj

Define the function of all labels (S) NS (T ) T }i=1 , {Yj }N j=1 :=

F {Yi

NS X NT X

(S)

∥Yi

(T )

− Yj

∗ ∥ γ̂ij .

i=1 j=1

Then A = F − E[F | {X}] . (S)

Bounded differences for changing one source label. Fix an index i and replace Yi all other labels the same. Then, by the triangle inequality, (S)

F (. . . , Yi =

NT X

(S) ′

, . . .) − F (. . . , Yi

(S)

∥Yi

(T )

− Yj

, . . .)

(S) ′

∥ − ∥Yi

(T )

− Yj

∗ ∥ γ̂ij

j=1

≤

NT X

(S)

− Yj

(S)

− Yi

∥Yi

(T )

(S) ′

∥ − ∥Yi

(T )

− Yj

∗ ∥ γ̂ij

j=1

≤

NT X

∥Yi

(S) ′

∗ ∥ γ̂ij ≤ M

j=1

NT X j=1

∗ γ̂ij =

(S) ′

by another value Yi

M . NS

in Y, keeping

General Quantification of Covariate and Concept Shifts (T )

Bounded differences for changing one target label. Similarly, replacing one Yj

(T ) ′

by Yj

changes F by at most

M . NT Apply McDiarmid. By McDiarmid nequality B.2, for any ε1 > 0, P |F − E[F | {X}]| > ε1 {X} ≤ 2 exp − PNS

2ε21 P NT 2 2 j=1 (M/NT ) i=1 (M/NS ) + 2ε2 = 2 exp − 2 1 1 1 M NS + NT 2NS NT ε21 . = 2 exp − (NS + NT ) M 2

Taking expectation over {X} gives the unconditional bound P(A > ε1 ) ≤ 2 exp −

2NS NT ε21 . (NS + NT ) M 2 (S)

(T )

Compute the conditional mean E[F | {X}] and identify Eγ̄ ∗ [f ]. Since Yi and Yj are independent given {X}, we have (S) (T ) (S) (T ) E ∥Yi − Yj ∥ | {X} = f Xi , Xj , hence E[F | {X}] =

NS X NT X

(S)

(T )

f Xi , Xj

∗ γ̂ij = E(xS ,xT )∼γ̄ ∗ f (xS , xT ) = Eγ̄ ∗ [f ].

i=1 j=1

Therefore A = |F − E[F | {X}]| is exactly the deviation term we bounded. Step 4: bound B using Lipschitzness of f and stability of entropic OT. Step 4.1: show f is (M LY |X )-Lipschitz on Rd × Rd . We prove Lipschitzness in the first coordinate; the second is symmetric. Fix xT and let xS , x′S ∈ Rd . Write πxSS := DYS |X=xS and πxTT := DYT |X=xT . Then f (xS , xT ) − f (x′S , xT ) Z Z = ∥yS − yT ∥ dπxSS (yS ) − dπxS′ (yS ) dπxTT (yT ). Y

Taking absolute values and using Fubini, f (xS , xT ) − f (x′S , xT ) ≤

Z Z Y

∥yS − yT ∥ dπxSS (yS ) − dπxS′ (yS ) dπxTT (yT ). S

For each fixed yT , define

2 ∥yS − yT ∥ − 1. M Since ∥yS − yT ∥ ∈ [0, M ] for yS , yT ∈ Y, we have gyT ∈ [−1, 1] and thus ∥gyT ∥∞ ≤ 1. Also note that gyT (yS ) :=

∥yS − yT ∥ = and

M gyT (yS ) + 1 , 2

1 (dπxSS − dπxS′ ) = 0, hence S Z Z M ∥yS − yT ∥ dπxSS − dπxS′ = gyT (yS ) dπxSS − dπxS′ S S 2 Y Y ≤ M dTV (πxSS , πxS′ ), S

General Quantification of Covariate and Concept Shifts

where we used the dual representation 1 dTV (P, Q) = sup 2 ∥g∥∞ ≤1

Z g d(P − Q) .

Plugging this into the previous bound and using that πxTT has total mass 1 gives f (xS , xT ) − f (x′S , xT ) ≤ M dTV DYS |X=xS , DYS |X=x′ ≤ M LY |X ∥xS − x′S ∥. S

Similarly, f (xS , xT ) − f (xS , x′T ) ≤ M LY |X ∥xT − x′T ∥. Combining both, for all (xS , xT ), (x′S , x′T ), f (xS , xT ) − f (x′S , x′T ) ≤ M LY |X ∥xS − x′S ∥ + ∥xT − x′T ∥ = M LY |X ρ (xS , xT ), (x′S , x′T ) . Thus f is (M LY |X )-Lipschitz on (Rd × Rd , ρ). Step 4.2: convert B to a Wasserstein distance on couplings. (Rd × Rd , ρ), for any K-Lipschitz function φ,

By the Kantorovich–Rubinstein duality for W1 on

Eπ [φ] − Eπ′ [φ] ≤ K W1 (π, π ′ ). Apply this with φ = f and K = M LY |X , π = γ̄ ∗ , π ′ = γ ∗ : B = Eγ̄ ∗ [f ] − Eγ ∗ [f ] ≤ M LY |X W1 (γ ∗ , γ̄ ∗ ). Step 4.3: apply entropic OT stability and then concentration of marginals. By Lemma 4.4, s 2 √ ∗ ∗ W1 (γ , γ̄ ) ≤ Λ + 2 Λ, Λ := W1 (µ, µ̂) + W1 (ν, ν̂). βλγ ∗ Therefore, s

B ≤ M LY |X Λ + 2

2 √ Λ . βλγ ∗

Fix ε2 > 0. If Λ ≤ 2ε2 , then √

Λ≤

√

s 2ε2 ,

Λ+2

2 √ Λ ≤ 2ε2 + 4 βλγ ∗

and hence B ≤ 2M LY |X ε2 + 4M LY |X

ε2 , βλγ ∗

ε2 . βλγ ∗

Consequently, r n ε2 o B > 2M LY |X ε2 + 4M LY |X ⊆ {Λ > 2ε2 }. βλγ ∗ By the union bound, P(Λ > 2ε2 ) ≤ P W1 (µ, µ̂) > ε2 + P W1 (ν, ν̂) > ε2 . Since µ, ν have finite squared-exponential moments on Rd , by Lemma B.3 and B.4, there exist constants λS , λT > 0 depending only on these moments such that for any ε2 > 0 there exists N with, whenever NS , NT > N , λ N ε2 λ N ε2 S S 2 T T 2 P W1 (µ, µ̂) > ε2 ≤ exp − , P W1 (ν, ν̂) > ε2 ≤ exp − . 2 2 Thus we conclude r λ N ε2 λ N ε2 ε2 S S 2 T T 2 P B > 2M LY |X ε2 + 4M LY |X ≤ exp − + exp − . βλγ ∗ 2 2 29

General Quantification of Covariate and Concept Shifts

≤ 2 exp −

∗

γ γ Recalling Eγ ∗ [f ] = SCpt + ∆, the left-hand side is exactly P(|ŜCpt − SCpt − ∆| > · · · ).

Step 6: parameter tying and the explicit Φ.

Introduce a single auxiliary parameter ε0 > 0 and set −1/4 −1/4 λT ε0 .

ε1 := M ε0 ,

ε2 := λS

Then the three exponential terms become 2 exp −

2N N ε2 2NS NT ε21 S T 0 = 2 exp − , (NS + NT ) M 2 NS + N T λ N ε2 λ1/2 N ε2 S S S 2 exp − = exp − S 1/2 0 , 2 2λT λ N ε2 λ1/2 N ε2 T T T 2 exp − = exp − T 1/2 0 . 2 2λS

The deviation level on the left-hand side becomes q −1/2 −1/8 −1/8 1/2 −1/4 −1/4 ε1 + 2M LY |X ε2 + 4M LY |X βλε2γ ∗ = M ε0 + 2M LY |X λS λT ε0 + 4M LY |X β −1/2 λγ ∗ λS λT ε0 . Define the constants −1/4 −1/4 λT .

−1/4 −1/4 λT ,

c1 := 16L2Y |X β −1 λ−1 γ ∗ λS

c2 := 1 + 2LY |X λS

Then the deviation level can be written compactly as √ M c2 ε0 + c1 ε0 . Now choose ε0 so that

Let u :=

√

√ M c2 ε0 + c1 ε0 = ε.

ε0 . The equation becomes c2 u2 + p u=

√

c1 u = ε/M , whose positive solution is

c1 + 4c2 (ε/M ) − 2c2

√

ε0 = u2 .

Φε It is convenient to express ε20 in the form ε20 = 2M 2 . Let

a :=

c1 M c2 ε

(> 0),

Λ(a) := a2 + 4a + 2 − (a + 2)

A direct algebraic simplification (expanding (a + 2 −

√

a2 + 4a)2 ) shows

ε20 =

Φ ε2 . 2M 2

p a2 + 4a,

Φ :=

Λ(a) . c22

General Quantification of Covariate and Concept Shifts

Substituting this ε20 into the exponential terms yields 2N N ε2 NS NT Φ ε2 S T 0 , 2 exp − = 2 exp − NS + N T (NS + NT ) M 2 λ1/2 N ε2 λ1/2 N Φ ε2 S S exp − S 1/2 0 = exp − S 1/2 , 2λT 4λT M 2 λ1/2 N ε2 λ1/2 N Φ ε2 T T exp − T 1/2 0 = exp − T 1/2 . 2λS 4λS M 2 This is exactly the claimed bound, completing the proof. C.15. Proof of Proposition 4.6 Proof. Recall the notation used in the proof of Theorem 4.5: for (xS , xT ) ∈ X × X define f (xS , xT ) := EyS ∼DS

Y |X=xS

T , yT ∼DY |X=x

Spair (xS , xT ) := W1 DYS |X=xS , DYT |X=xT ,

ρY (yS , yT ) , T

and the bias is ∆ = E(xS ,xT )∼γ ∗ f (xS , xT ) − Spair (xS , xT ) . Under deterministic labeling, DYS |X=xS = δfS (xS ) and DYT |X=xT = δfT (xT ) . Hence the random variables yS , yT are almost surely equal to fS (xS ), fT (xT ), and thus f (xS , xT ) = E ρY (yS , yT ) = ρY fS (xS ), fT (xT ) . On the other hand, the Wasserstein-1 distance between two Dirac measures is exactly the ground metric: Spair (xS , xT ) = W1 δfS (xS ) , δfT (xT ) = ρY fS (xS ), fT (xT ) . Therefore f (xS , xT ) − Spair (xS , xT ) = 0 for all (xS , xT ), and so ∆ = Eγ ∗ f (xS , xT ) − Spair (xS , xT ) = 0. This concludes the proof. C.16. Proof of Proposition 4.7 Proof. We follow the notation used in the proof of Theorem 4.5. For (xS , xT ) ∈ X × X , define f (xS , xT ) := EyS ∼DS

Y |X=xS

T , yT ∼DY |X=x

Spair (xS , xT ) := W1 DYS |X=xS , DYT |X=xT ,

∥yS − yT ∥ , T

and recall that ∆ = E(xS ,xT )∼γ ∗ f (xS , xT ) − Spair (xS , xT ) . Lower bound ∆ ≥ 0. For each fixed (xS , xT ), the product measure DYS |X=xS ⊗ DYT |X=xT belongs to Γ DYS |X=xS , DYT |X=xT . Since Spair (xS , xT ) is the infimum of E[∥yS − yT ∥] over all such couplings, Spair (xS , xT ) ≤ EDS

Y |X=xS

T ⊗DY |X=x

Thus f (xS , xT ) − Spair (xS , xT ) ≥ 0 pointwise, hence ∆ ≥ 0. 31

∥yS − yT ∥ = f (xS , xT ).

General Quantification of Covariate and Concept Shifts

An upper bound for each pair (xS , xT ). Fix (xS , xT ) and write P := DYS |X=xS and Q := DYT |X=xT . Let their means be mS (xS ) := Ey∼P [y], mT (xT ) := Ey∼Q [y], For independent draws yS ∼ P and yT ∼ Q, the triangle inequality yields ∥yS − yT ∥ ≤ ∥yS − mS (xS )∥ + ∥mS (xS ) − mT (xT )∥ + ∥mT (xT ) − yT ∥. Taking expectation gives f (xS , xT ) ≤ Ey∼P ∥y − mS (xS )∥ + ∥mS (xS ) − mT (xT )∥ + Ey∼Q ∥y − mT (xT )∥ . Next we lower bound Spair (xS , xT ) = W1 (P, Q) by the distance between the means. Let π ∈ Γ(P, Q) be any coupling, and denote mP := Ey∼P [y], mQ := Ey∼Q [y]. Since ∥ · ∥ is convex, Jensen’s inequality yields E(y,y′ )∼π ∥y − y ′ ∥ ≥ E(y,y′ )∼π [ y − y ′ ] . By the marginal constraints of π, we have E(y,y′ )∼π [y] = mP and E(y,y′ )∼π [y ′ ] = mQ , hence E(y,y′ )∼π [ y − y ′ ] = ∥mP − mQ ∥. Therefore, for every π ∈ Γ(P, Q), E(y,y′ )∼π ∥y − y ′ ∥ ≥ ∥mP − mQ ∥. Taking the infimum over π ∈ Γ(P, Q) gives W1 (P, Q) =

inf π∈Γ(P,Q)

E(y,y′ )∼π ∥y − y ′ ∥ ≥ ∥mP − mQ ∥.

Combining the two displays and canceling the middle term yields f (xS , xT ) − Spair (xS , xT ) ≤ Ey∼P ∥y − mS (xS )∥ + Ey∼Q ∥y − mT (xT )∥ . Integrate over γ ∗ and relate to irreducible errors. Taking expectation over (xS , xT ) ∼ γ ∗ and using that the marginals S T of γ ∗ are DX and DX , h h i i (S) (T ) S E ∥Y T E ∥Y ∆ ≤ Ex∼DX − mS (x)∥ | X (S) = x + Ex∼DX − mT (x)∥ | X (T ) = x . p For any random variable Z ≥ 0, E[Z] ≤ E[Z 2 ], hence q E ∥Y (S) − mS (x)∥ | X (S) = x ≤ E ∥Y (S) − mS (x)∥2 | X (S) = x , and similarly for the target term. Thus hq hq i i S T ∆ ≤ Ex∼DX E ∥Y (S) − mS (x)∥2 | X (S) = x + Ex∼DX E ∥Y (T ) − mT (x)∥2 | X (T ) = x . √ Since · is concave on R+ , Jensen’s inequality gives hq i q S S Ex∼DX E ∥Y (S) − mS (x)∥2 | X (S) = x ≤ E(x,y)∼DXY ∥y − mS (x)∥2 , hq i q T T Ex∼DX E ∥Y (T ) − mT (x)∥2 | X (T ) = x ≤ E(x,y)∼DXY ∥y − mT (x)∥2 . ′

Finally, under squared loss on Rd , the minimizer of E[∥Y − g(x)∥2 | X = x] is g(x) = E[Y | X = x]. Therefore the S T functions mS (x) = E[Y (S) | X (S) = x] and mT (x) = E[Y (T ) | X (T ) = x] achieve the infima of I(DXY ) and I(DXY ), i.e., 2 S 2 T S T E(x,y)∼DXY ∥y − mS (x)∥ = I(DXY ), E(x,y)∼DXY ∥y − mT (x)∥ = I(DXY ). Putting the above bounds together yields ∆≤

S )+ I(DXY

which completes the proof. 32

q T ), I(DXY

General Quantification of Covariate and Concept Shifts

D. Analysis of Lipschitz Constants: Results and Proofs D.1. Lipschitz Constant of the Sigmoid Function Proposition D.1 (Lipschitz constant of the sigmoid). Let σ : R → R be the sigmoid function 1 . 1 + e−x

σ(x) = Then σ is globally 14 -Lipschitz on R. Proof. We first compute the derivative: σ ′ (x) =

−1 d e−x 1 + e−x = 2 . dx 1 + e−x

−x

e Using σ(x) = 1+e1−x and 1 − σ(x) = 1+e −x , we can rewrite

σ ′ (x) = σ(x) 1 − σ(x) . Let u = σ(x) ∈ (0, 1). Then σ ′ (x) = u(1 − u), and for all u ∈ [0, 1], u(1 − u) = u − u2 ≤ max (t − t2 ) = t∈[0,1]

1 , 4

where the maximum is attained at t = 21 . Hence 0 < σ ′ (x) ≤ 14 for all x. Now fix any x, y ∈ R. Since σ is differentiable on R (hence continuous), by the mean value theorem, there exists c between x and y such that σ(x) − σ(y) = σ ′ (c) (x − y). Taking absolute values and using σ ′ (c) ≤ 14 yields |σ(x) − σ(y)| = |σ ′ (c)| |x − y| ≤

1 |x − y|, 4

so σ is 14 -Lipschitz. D.2. Lipschitz Constant of the Logistic Regression Proposition D.2 (Lipschitz constant of logistic regression under ℓp /ℓq ). Fix w ∈ Rd and b ∈ R. Define hw,b (x) = σ w⊤ x + b ,

σ(t) =

1 . 1 + e−t

Let p ∈ [1, ∞] and let q ∈ [1, ∞] be its Hölder conjugate, i.e., p1 + 1q = 1. Then hw,b is globally to ∥ · ∥p , namely for all x, x′ ∈ Rd , hw,b (x) − hw,b (x′ ) ≤

∥w∥q 4 -Lipschitz with respect

∥w∥q ∥x − x′ ∥p . 4

In particular, under ∥ · ∥2 , the Lipschitz constant equals ∥w∥2 /4. Proof. For any x, x′ ∈ Rd , apply the mean value theorem to σ to obtain some ξ between w⊤ x + b and w⊤ x′ + b such that hw,b (x) − hw,b (x′ ) = σ ′ (ξ) w⊤ (x − x′ ). Thus hw,b (x) − hw,b (x′ ) ≤ |σ ′ (ξ)| w⊤ (x − x′ ) . 33

General Quantification of Covariate and Concept Shifts

By Proposition D.1, we have |σ ′ (ξ)| ≤ 14 . By Hölder’s inequality with conjugate exponents (p, q), w⊤ (x − x′ ) ≤ ∥w∥q ∥x − x′ ∥p . Combining the two inequalities yields hw,b (x) − hw,b (x′ ) ≤

1 ∥w∥q ∥x − x′ ∥p , 4

which proves the claim. D.3. Lipschitz Constant of the Linear Multi-class Classifier Proposition D.3.1 (Lipschitz constant of the linear classifier under ∥ · ∥2 ). Let W ∈ RN ×d and b ∈ RN . Define f (x) = softmax(W x + b) ∈ ∆N −1 , Here ∆N −1 := {p ∈ RN : pi ≥ 0, ∀i, and define

x ∈ Rd .

⊤ i=1 pi = 1} denotes the probability simplex. Let wi denote the i-th row of W

D(W ) := max ∥wi − wj ∥2 . i,j∈[N ]

Then f is Lipschitz from (Rd , ∥ · ∥2 ) to (RN , ∥ · ∥2 ) and its optimal Lipschitz constant equals 1 sup ∥∇f (x)∥2 = √ D(W ), 2 2 x∈Rd where ∥ · ∥2 denotes the matrix operator norm induced by the vector ∥ · ∥2 norm. Proof. For z ∈ RN , write p = softmax(z) ∈ ∆N −1 . The Jacobian of softmax is J(p) = ∇z softmax(z) = Diag(p) − pp⊤ , where Diag(p) is the diagonal matrix with diagonal entries p1 , . . . , pN . By the chain rule, for p = softmax(W x + b), ∇f (x) = J(p) W. Therefore, sup ∥∇f (x)∥2 =

sup ∥J(p)W ∥2 .

(16)

p∈∆N −1

x∈Rd

Fix p ∈ ∆N −1 and a unit vector u ∈ Rd with ∥u∥2 = 1. Let µ := p⊤ v.

v := W u ∈ RN ,

and µ represents the mean of v under the probability distribution p. We have J(p)v = Diag(p) − pp⊤ v = Diag(p) v − µ1 , hence ∥J(p)W u∥22 = ∥J(p)v∥22 =

N X

p2i (vi − µ)2 .

i=1

Now fix v ∈ RN and consider the quantity Φ(v) :=

sup p∈∆N −1

N X i=1

p2i (vi − p⊤ v)2 .

(17)

General Quantification of Covariate and Concept Shifts

Indeed, for any p ∈ ∆N −1 , N X

p2i (vi − µ)2 ≤

max pi

N X

i=1

pi (vi − µ)2 =

i=1

max pi Varp (v), i

P where Varp (v) := i pi (vi − µ)2 , which represents the variance of v under the probability distribution p. If p is supported on two values m := mini vi and M := maxi vi with masses α and 1 − α, let r := M − m, then N X

p2i (vi − µ)2 = 2α2 (1 − α)2 r2 ≤

i=1

r2 , 8

with equality at α = 12 . Since any mass placed at intermediate values of v cannot increase the range-based extremum, we obtain Φ(v) = r2 /8, and the optimal p is supported on indices attaining M and m. Combining (17), for any unit u, 1 sup ∥J(p)W u∥2 = √ max(W u)i − min(W u)j . i j 2 2 p∈∆N −1

(18)

Finally, maximize the range over u. Writing (W u)i = wi⊤ u, we have max(W u)i − min(W u)j = max(wi − wj )⊤ u. i

i,j

Thus, sup ∥u∥2 =1

max(W u)i − min(W u)j = max sup (wi − wj )⊤ u = max ∥wi − wj ∥2 = D(W ). i

i,j ∥u∥ =1 2

i,j

Plugging this into (18) and then into (16) yields sup ∥∇f (x)∥2 x∈Rd

= sup ∥J(p)W ∥2 p∈∆N −1

= sup

sup ∥J(p)W u∥2

p∈∆N −1 ∥u∥2 =1

= sup

sup ∥J(p)W u∥2

∥u∥2 =1 p∈∆N −1

1 = √ D(W ) 2 2 This completes the proof. Proposition D.3.2 (Lipschitz constant of the linear classifier under ∥ · ∥2 → ∥ · ∥1 ). Let W ∈ RN ×d and b ∈ RN . Define f (x) = softmax(W x + b) ∈ ∆N −1 , Here ∆N −1 := {p ∈ RN : pi ≥ 0, ∀i, and define

x ∈ Rd .

⊤ i=1 pi = 1} denotes the probability simplex. Let wi denote the i-th row of W

D(W ) := max ∥wi − wj ∥2 . i,j∈[N ]

Then f is Lipschitz from (R , ∥ · ∥2 ) to (R , ∥ · ∥1 ), and its optimal Lipschitz constant equals sup ∥∇f (x)∥2→1 = x∈Rd

1 D(W ), 2

where ∥ · ∥2→1 denotes the operator norm induced by ∥ · ∥2 on the input and ∥ · ∥1 on the output. 35

General Quantification of Covariate and Concept Shifts

Proof. For z ∈ RN , write p = softmax(z) ∈ ∆N −1 and recall J(p) = ∇z softmax(z) = Diag(p) − pp⊤ . By the chain rule, for p = softmax(W x + b) we have ∇f (x) = J(p) W. Hence sup ∥∇f (x)∥2→1 =

sup ∥J(p)W ∥2→1 .

(19)

p∈∆N −1

x∈Rd

Fix p ∈ ∆N −1 and v ∈ RN . Let µ := p⊤ v. Using J(p)v = (Diag(p) − pp⊤ )v = Diag(p) v − µ1 , we obtain ∥J(p)v∥1 =

N X

pi |vi − µ|.

(20)

i=1

The right-hand side is the mean absolute deviation of v under the probability distribution p. Fix v ∈ RN and define m := mini vi , M := maxi vi , and r := M − m. We claim that N X

sup

pi |vi − p⊤ v| =

p∈∆N −1 i=1

r . 2

(21)

Upper bound. Let µ = p⊤ v. By Cauchy–Schwarz, N X

pi |vi − µ| ≤

N X

N 1/2 X

i=1

pi (vi − µ)2

1/2

Varp (v).

i=1

By Popoviciu’s inequality for bounded random variables, Varp (v) ≤ r2 /4, hence N X

pi |vi − µ| ≤

i=1

r . 2

Lower bound (attainability). Let imax ∈ arg maxi vi and imin ∈ arg mini vi , and take p=

1 (ei + eimin ). 2 max

Here ei ∈ RN denotes the i-th standard basis vector, i.e., (ei )j = 1{j = i}. Then µ = (M + m)/2, and N X

pi |vi − µ| =

i=1

1 M +m 1 M +m r M− + m− = . 2 2 2 2 2

This proves (21). Combining (20) and (21), for any u ∈ Rd with ∥u∥2 = 1, sup ∥J(p)W u∥1 = p∈∆N −1

1 max(W u)i − min(W u)j . i j 2

Writing (W u)i = wi⊤ u, we have max(W u)i − min(W u)j = max(wi − wj )⊤ u. i

i,j

(22)

General Quantification of Covariate and Concept Shifts

Therefore, sup

∥u∥2 =1

max(W u)i − min(W u)j = max sup (wi − wj )⊤ u = max ∥wi − wj ∥2 = D(W ). i

i,j ∥u∥ =1 2

i,j

From (19) and (22), sup ∥∇f (x)∥2→1 x∈Rd

sup ∥J(p)W u∥1

= sup

p∈∆N −1 ∥u∥2 =1

= sup

sup ∥J(p)W u∥1

∥u∥2 =1 p∈∆N −1

1 max(W u)i − min(W u)j sup i j 2 ∥u∥2 =1

1 = D(W ). 2 This completes the proof. D.4. Lipschitz Constant of MLPs Based on the previous theory for the Lipschitz constant of MLPs by Fazlyab et al. (2020), we obtain the following direct result: Proposition D.4 (SDP-certified Lipschitz constant for MLPs). Consider the ℓ-hidden-layer MLP x 0 = x ∈ R n0 ,

xk = ϕ(Wk−1 xk−1 + bk−1 ) ∈ Rnk (k = 1, . . . , ℓ), f (x) = Wℓ xℓ + bℓ ∈ Rm ,

where ϕ(z) = [φ(z1 ), . . . , φ(znk )]⊤ acts componentwise and the scalar activation φ is slope-restricted on [0, β] (i.e., 0 ≤ φ(u)−φ(v) ≤ β for all u ̸= v). u−v Let N := n0 + n1 + · · · + nℓ and n := n1 + · · · + nℓ . Define the matrices A ∈ Rn×N and B ∈ Rn×N by     0 In1 0 ··· 0 W0 0 · · · 0 0 0 0 In2 · · · 0   0 W1 · · · 0 0     , B = A= .  ..  .. .. ..  . .. .. .. .. ..    .. . . . . . .  . . . 0

···

Wℓ−1

···

Inℓ

Let the decision variable Tn ∈ S be block-diagonal across layers: Tn = blkdiag(Tn1 , . . . , Tnℓ ),

Tnk = diag(tk,1 , . . . , tk,nk ),

tk,i ≥ 0.

Consider the SDP (with variable H ≥ 0): min

{tk,i }, H

s.t.

H M ⪰ 0, M = − ML (H) + MA (Tn ) ,  −HIn0  0  ML (H) =  .  .. 0 MA (Tn ) =

0 ··· 0 ··· .. . . . . 0

⊤ A 0 B βTn 37

···

0 0 .. . Wℓ⊤ Wℓ

βTn −2Tn

    ∈ SN , 

A ∈ SN . B

General Quantification of Covariate and Concept Shifts

Let H ⋆ be the optimal value and define LSDP :=

√

H ⋆ . Then LSDP is a global ∥ · ∥2 -Lipschitz constant of f , i.e.,

∥f (x) − f (y)∥2 ≤ LSDP ∥x − y∥2 ,

∀x, y ∈ Rn0 .

E. Additional Experiments E.1. Experiments on Estimator Sensitivity In this section, we conduct a sensitivity analysis of the proposed estimators ŜCov and ŜCpt with respect to the parameter β. We take the ”-90%” domain of ColoredMNIST as the target domain and regard the mixture of the other two domains as the source domain. We train the model on the source domain using ERM with the best hyperparameters in DomainBed. At the last checkpoint, we store all representation-label pairs from both the source and target domains. For each β, we randomly sample 10,000 pairs from each domain, run the DataShifts algorithm to obtain the estimated results, repeat this procedure 50 times, and report the average. The results are shown below: Table 2. Sensitivity analysis with respect to β. β

0.001

0.002

0.005

0.01

0.02

0.05

0.1

0.2

ŜCov ŜCpt Time (s)

0.5081 1.4456 15.12

0.5080 1.4458 14.09

0.5078 1.4467 12.62

0.5074 1.4478 11.60

0.5066 1.4501 10.54

0.5041 1.4567 9.09

0.4995 1.4674 8.03

0.4916 1.4895 6.83

Across magnitude changes in β, the coefficients of variation of ŜCov and ŜCpt are 1.076% and 0.990%, so both estimators are stable for small β. Since entropic OT gets faster as β grows, we use β = 0.2 in the main experiments to balance speed and accuracy. E.2. Experiments on the Bias under Stochastic Labeling We test the bias of our γ ∗ -Y|X shift estimator ŜCpt on the following stochastic-labeling synthetic data. In both source and target domains, covariates are drawn from a 10-dim standard normal distributions. At each x, scalar labels are sampled from γ∗ normal distribution N (∥x∥2 , σ 2 ) in the source and N (∥x∥2 + 1.0, σ 2 ) in the target. Thus, the true Y|X shift SCpt = 1.0, and standard deviation σ controls the noise. By Proposition 4.7, the irreducible errors of both domains are σ 2 , and the bias ∗ ˆ = ŜCpt − S γ is an estimate of the bias ∆. For each σ, we randomly ∆ ≥ 0 of our estimator should be bounded by 2σ. ∆ Cpt sample 10,000 points from each domain, and run DataShifts algorithm with β = 0.2, repeat this procedure 50 times, and ˆ The results are shown below: report the average ∆. Table 3. Bias of ŜCpt under different noise levels σ. σ

0.01

0.1

0.3

0.5

1.0

2.0

5.0

10.0

Irreducible error bound (2σ) ˆ Bias (∆)

0.02 0.0036

0.2 0.0389

0.6 0.0702

1.0 0.1440

2.0 0.4865

4.0 1.4524

10.0 4.7314

20.0 10.3467

ˆ is also very small, which means our estimator ŜCpt stays close to the true Y|X shift When the noise σ is small, the bias ∆ γ∗ ˆ remains small, SCpt = 1.0. Even when the noise in both domains reaches half of the true Y|X shift (σ = 0.5), the bias ∆ and the ŜCpt still does not notably overestimate. As σ grows far beyond 1.0, Y|X shift becomes less identifiable. The bias increases and overestimation appears, but it stays below the bound set by irreducible error, as proved in Proposition 4.7.

Record · ID 673489 · SHA-256 a9df1408b1522c7e
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.