Distribution Shift Is a Broken Promise
Every deployed model makes an implicit bet: that the data it sees at inference will look like the data it trained on. When that bet fails, performance degrades silently and sometimes catastrophically. The study of distribution shift tries to answer a simple question: how bad can things get when the source and target domains diverge? Existing theory offers bounds on the target-domain error as a function of source-domain error plus a shift penalty. But these bounds are brittle. They demand deterministic labeling, apply only to binary classification with absolute loss, and, most damagingly, collapse into nonsense the moment the covariate supports of the two domains do not overlap.
This paper from Hongbo Chen and Li Charlie Xia at South China University of Technology, accepted at ICML 2026, tackles both the definitional and the practical failures simultaneously. They fix a long-standing gap in concept shift theory using entropic optimal transport, derive a general learning bound that works across classification, regression, and stochastic labeling, and provide concrete estimators with sample-complexity guarantees. The result is DataShifts, a plug-and-play algorithm that can be applied to any labeled dataset to quantify both covariate and concept shift.
Why Existing Concept Shift Theory Breaks
The standard decomposition splits distribution shift into two pieces. Covariate shift (X shift) occurs when the marginal distribution of inputs changes: the source and target draw features from different distributions, but the relationship between features and labels stays the same. Concept shift (Y|X shift) is the opposite: the input distribution is stable, but the labeling rule itself changes.
Prior work by Zhao et al. (2019) gave a clean bound for soft-label binary classification that adds an H-divergence term for X shift and an expectation over the difference between source and target labeling functions for concept shift. The bound picks the tighter of two expectations: one taken under the source covariate distribution, one under the target. This looks elegant until you realize the concept shift term is undefined when the supports do not overlap.
The issue is subtle but fundamental. Conditional probabilities like P(A|X=x) are only well-defined almost everywhere with respect to the distribution that generates them. When the target distribution assigns positive mass to regions where the source distribution is empty, the labeling function f_S(x) is arbitrary on those regions. The expectation under the target distribution therefore depends on undefined values, making the concept shift term ill-defined and non-estimable from any finite sample. In practice, support mismatch is common: think of a medical imaging model trained on Hospital A's scanner encountering images from Hospital B with different equipment.
Entropic Optimal Transport to the Rescue
The authors' key insight is to use entropic optimal transport to construct a transport coupling between the source and target covariate distributions, and to define concept shift relative to that coupling rather than to either marginal alone.
Entropic optimal transport augments the classical Wasserstein distance with an entropy regularizer. Given source distribution D_X^S and target distribution D_X^T, the entropic Wasserstein distance is:
W_beta(P, Q) = inf_{gamma in Gamma(P, Q)} { integral of rho d gamma + beta * H(gamma | P tensor Q) }
where rho is the transport cost, Gamma(P, Q) is the set of joint distributions with the correct marginals, and H is the relative entropy. The parameter beta controls the regularization strength. When beta is positive, the optimal coupling gamma* is unique, which is critical for the well-definedness results that follow.
The covariate shift S_Cov is simply W_beta(D_X^S, D_X^T). The concept shift is then defined as an expectation over the optimal coupling: for each pair (x_S, x_T) connected by gamma*, compute the Wasserstein distance between the conditional label distributions at those two points, and average over gamma*. This gives S_Cpt^{gamma*}.
The authors prove several properties that make this construction work. The support of gamma* is contained in the product of the supports of the source and target distributions, so every (x_S, x_T) pair that gamma* connects is a valid point in both domains. When beta is positive, gamma* is unique, so the concept shift is a well-defined number. And when the source and target distributions happen to coincide, gamma* collapses to the diagonal coupling, and the definition recovers the standard concept shift from prior work.
The General Learning Bound
With both shift measures defined, the main learning bound follows from a chain of lemmas. For any hypothesis h that is L_h-Lipschitz and any loss function that is separately (L_l, L_l')-Lipschitz, the target error is bounded by:
epsilon_T(h) <= epsilon_S(h) + L_h * L_l' * S_Cov + L_l * S_Cpt^{gamma*}
Three constants control the bound. The source error epsilon_S(h) is the baseline. The covariate shift term is weighted by the product of the hypothesis Lipschitz constant and the loss Lipschitz constant with respect to the prediction. The concept shift term is weighted by the loss Lipschitz constant with respect to the true label.
The separate Lipschitz condition on the loss is mild. Cross-entropy loss, squared error, absolute loss, and most differentiable losses satisfy it. The Lipschitz constants for common learners are worked out in the paper: the sigmoid function is 1/4-Lipschitz, logistic regression is ||w||_2/4-Lipschitz, and for MLPs the Lipschitz constant can be certified via semidefinite programming.
The bound is agnostic to the hypothesis space, the label space, and the loss function. It applies to classification and regression, to deterministic and stochastic labeling, and to any metric space for the covariates. This generality is the main theoretical contribution: prior bounds required binary labels, deterministic labeling, and absolute loss, while this one handles the full range of supervised learning settings.
Estimators That Actually Work From Samples
A bound is only useful if its terms can be estimated from data. The authors develop two estimators, one for each shift type, and prove concentration inequalities showing they converge to the true values as sample size grows.
Covariate Shift Estimation
The naive plug-in estimator for the entropic Wasserstein distance suffers from the curse of dimensionality. As the dimension grows, the empirical distributions become increasingly sparse, and the plug-in tends to overestimate the true distance. The authors develop a debiased estimator that subtracts the leading-order bias term, which depends on the smoothness of the transport cost and the effective dimension of the data. The debiased estimator satisfies a concentration inequality of the form: with probability at least 1 - delta, the absolute error is bounded by a term that scales as O(1/sqrt(n)) where n is the sample size.
Concept Shift Estimation
For concept shift, the estimator first computes the optimal coupling gamma* from the empirical source and target samples, then for each (x_S, x_T) pair in the coupling support, estimates the Wasserstein distance between the conditional label distributions using samples from each domain. The estimator satisfies a more complex concentration bound that involves the Lipschitz constant of the transport coupling, the number of labeled samples at each covariate point, and the regularization parameter beta.
The authors also analyze the bias of the concept shift estimator under stochastic labeling. They show that the bias is bounded by the sum of the irreducible errors (label noise) in the source and target domains. When labeling is deterministic, the bias vanishes exactly.
The DataShifts Algorithm
The two estimators are combined into a single algorithm that takes labeled source and target data as input and returns estimates of covariate shift, concept shift, and the full error bound. The algorithm also requires Lipschitz constants for the loss and the hypothesis, which can be computed analytically for linear models or certified via SDP for neural networks. If the source domain error is known or estimated, the algorithm outputs the predicted target error as well.
Experimental Validation
The authors test DataShifts on three real tasks and one synthetic setting.
Novozymes Enzyme Stability Prediction
This Kaggle competition task predicts enzyme transition temperatures from 20-dimensional features, with 180 enzyme families serving as separate domains. The authors train a 3-layer MLP on the 60 families with lowest training error and use DataShifts to bound the test error on the remaining 120 families. The estimated error bound tracks the actual test error closely across all target families, with the bound sitting just above the diagonal. The decomposition reveals that large concept shift between enzyme families is the primary driver of generalization failure, not covariate shift.
ColoredMNIST and PACS
ColoredMNIST is a 70,000-image binary classification task where digit identity is confounded with color. PACS is a multi-class object recognition benchmark with style shifts across photo, art painting, cartoon, and sketch domains. Both are standard DomainBed tasks. The authors evaluate ERM, CORAL, and MMD, training each with 20 random hyperparameter trials per domain and method. For both tasks, the estimated error bound tracks the actual test error across training checkpoints. On ColoredMNIST, methods that reduce covariate shift (MMD, CORAL) cluster in the lower-left region of the error-vs-bound plot, confirming that smaller shift estimates correspond to better generalization. On PACS, the bound is looser in absolute magnitude but maintains the correct ordering and trend.
Synthetic Binary Classification
To compare directly with the prior bound from Zhao et al. (2019), the authors construct a synthetic task where both source and target concepts are logistic regression models. They vary the covariate shift (by rotating the target distribution) and the concept shift (by changing the angle or bias of the target labeling function). As the covariate shift increases, the new bound becomes significantly tighter than the existing one. As concept shift increases, both bounds grow, but the new bound grows more slowly, remaining closer to the true test error throughout.
Limitations and Trade-offs
The framework has several limitations the authors acknowledge. First, the Lipschitz constants for the hypothesis and loss must be known or estimated. For deep networks, the SDP-based Lipschitz certification is computationally expensive, and the certified constant may be loose. Second, the estimators require sufficient labeled samples at each covariate point to estimate conditional label distributions. In high-dimensional settings with sparse data, this requirement may be hard to satisfy. Third, the regularization parameter beta involves a trade-off: larger beta makes the coupling unique and the estimators faster to compute, but also smooths out fine-grained structure in the transport plan, potentially losing information about localized concept shifts. The sensitivity experiments show that the estimators are stable for small beta values, with coefficients of variation under 1.1% across two orders of magnitude.
The bias analysis under stochastic labeling reveals another constraint. When label noise is high relative to the concept shift, the estimator's bias grows. For noise standard deviation sigma much larger than the true concept shift, the bias can dominate. This is expected: when the signal-to-noise ratio is poor, no estimator can reliably separate concept shift from label noise.
What It Means in Practice
For practitioners, DataShifts offers a diagnostic tool. Before deploying a model, you can run it on both training and held-out deployment data, apply DataShifts, and get a decomposition of expected performance loss into its X-shift and concept-shift components. This tells you whether to invest in domain adaptation (to reduce covariate shift) or in relabeling and concept alignment (to reduce concept shift). The bound also serves as a stopping criterion during active learning: if the estimated bound is already tight, further data collection may not help.
The framework is general enough to apply to tabular data, images, or any domain where you can define a meaningful metric on the covariate space. The Lipschitz constant computation for common architectures is provided, and the SDP approach for MLPs extends to any network with slope-restricted activations.
For researchers, the paper fixes a definitional gap that has been silently undermining distribution shift theory for years. The ill-definedness of concept shift under support mismatch is not just a technicality: it means that existing bounds can be made arbitrarily loose by choosing different completions of the undefined labeling function. The entropic OT construction resolves this cleanly, and the resulting definition has the right limiting behavior: it recovers the standard concept shift when the distributions match and remains finite and estimable when they do not.