General Quantification of Covariate and Concept Shifts

Hongbo Chen; Li Charlie Xia

Source-linked AI summary

General Quantification of Covariate and Concept Shifts

Hongbo Chen, Li Charlie Xia

arXiv:2609.11918v1Sep 10, 2026cs.LGcs.AIstat.ML

TL;DR

Existing distribution-shift theory becomes ill-defined and non-estimable when source and target supports mismatch. This paper introduces γ*-Y|X shifts through entropic optimal transport, derives a general error bound, and provides estimators and DataShifts for practical quantification.

Problem
Existing Y|X shift theory becomes ill-defined, loose, and non-estimable when source and target covariate supports mismatch.
Method
The paper uses entropic optimal transport to define γ*-Y|X shifts, derives a unified X and γ*-Y|X error bound, and develops concentration-guaranteed estimators and DataShifts.
Results
The resulting framework and DataShifts quantify distribution shifts and estimate learning bounds across broad settings, with experiments validating their effectiveness and tightness.
Takeaways & Limitations
γ*-Y|X shifts provide a well-defined basis for analyzing learning error under support mismatch, including stochastic labeling and general label spaces.
Takeaways & Limitations
In high-dimensional covariate spaces, the plug-in estimator for X shift is substantially overestimated because its upward bias decays only at O(N^-1/d).

Abstract

from arXiv · show

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.

1. Introduction

The paper addresses distribution-shift theory that is too narrow and non-estimable by introducing a support-robust framework for covariate and concept shifts. It derives general bounds, estimators, and DataShifts, then validates them across multiple tasks.

Motivation: Existing theories are limited by restrictive assumptions, including deterministic labeling, binary classification, absolute loss, and non-estimable concept-shift definitions.These limitations hinder rigorous quantification of shifts and their effects on target-domain performance.
Core idea: Support mismatch makes the existing Y|X shift ill-defined, motivating the γ∗-Y|X shift defined through entropic optimal transport.The new notion remains well-defined under mismatched supports and supports stochastic labeling and general label spaces.
Experiments: Experiments on Novozymes, ColoredMNIST, and PACS validate the general effectiveness of the theoretical results.The experiments are presented as validation across three distinct tasks.
Theory: The paper derives a general error bound that unifies X and γ∗-Y|X shifts across broad hypothesis spaces, label spaces, loss functions, and supervised tasks.The bound relies on Lipschitz continuity of the hypothesis and loss.
Estimation and algorithm: Concentration-guaranteed estimators for X and γ∗-Y|X shifts are integrated into DataShifts, enabling rigorous shift quantification from real labeled data.The framework is designed as a plug-and-play tool for practical distribution-shift analysis.

2. Preliminary

This section formulates learning under source–target distribution shift and explains why existing concept-shift theory fails under support mismatch. It motivates entropic optimal transport as the basis for a better-defined shift measure.

Problem setup: The framework seeks to bound target error using source error and distribution-shift measures for covariate and label-condition shifts.It treats the covariate space as either raw input space or a learned representation space.
Problem setup: Stochastic labeling accommodates label noise and latent confounders, whereas existing theories often assume deterministic labeling.The stochastic formulation models labels as draws from conditional label distributions.
Ill-defined concept shift: When source and target covariate supports mismatch, conditional probabilities are defined only almost everywhere under the source measure, making target-weighted expectations arbitrary or ill-defined.This invalidates the usual expectation-based formulation of Y|X shift.
Existing theory: The existing bound is specialized to deterministic labeling, binary classification, and absolute loss, and its ill-defined Y|X terms can make the bound loose and non-estimable.These issues prevent rigorous quantification of concept shift on real data.
Entropic optimal transport: Entropic optimal transport measures distributional distance through transport cost and an entropy regularizer, providing the geometric machinery for defining X and Y|X shifts.At β = 0, the entropic optimal transport distance reduces to the Wasserstein-1 distance.

3. Theoretical Results

The paper defines distribution shifts through entropic optimal transport and derives a general learning bound that remains valid under support mismatch, stochastic labeling, and broad label and loss settings.

General X and Y|X Shifts: Entropic optimal transport defines the X shift and induces a γ*-Y|X shift by averaging paired conditional-distribution differences under the optimal coupling.The coupling emphasizes nearby source-target covariate pairs, making the concept-shift measure operational even when supports differ.
General X and Y|X Shifts: The γ*-Y|X shift is well-defined and unique for β > 0, including mismatched supports, while recovering the existing shift under deterministic labeling and matching supports.The construction also applies to stochastic labeling and general label spaces.
General Learning Bound: The proof constructs a joint coupling by combining the optimal covariate coupling with conditional-label couplings, then applies weak duality to obtain the cross-domain bound.This construction links the shift definitions to the source-to-target error comparison.
General Learning Bound: The general learning bound combines covariate and γ*-concept shifts through the learner and loss Lipschitz factors.Its assumptions use separate Lipschitz continuity of the loss and Lipschitz continuity of the hypothesis.
General Learning Bound: Because it imposes no specific restriction on the label space or loss beyond Lipschitz conditions, the bound covers regression, binary and multiclass classification, multi-label tasks, and stochastic labeling.The framework also permits asymmetric losses and can operate on raw inputs or learned representations.

4. Statistical Results

The paper develops sample-level estimators for covariate and γ*-Y|X shifts, proves concentration guarantees, and combines them in DataShifts to estimate distribution shifts and learning-error bounds. A debiased entropic optimal-transport estimator addresses high-dimensional overestimation, while the γ*-Y|X estimator remains well-defined under support mismatch.

4.1. Estimation of X Shift: The debiased estimator reduces plug-in overestimation and remains accurate across high dimension, sample size, and true distribution distance.In high-dimensional standard-normal experiments with zero true distance, the traditional estimator overestimates as dimension increases and improves only slightly with larger samples.
4.1. Estimation of X Shift: The debiased estimator concentrates exponentially with sample sizes and approximates the true entropic optimal-transport distance with high probability.Its concentration depends on distribution scales and the true distance between the distributions.
4.2. Estimation of Y|X Shift: The γ*-Y|X shift estimator also has exponentially decaying deviation probability and approximates the target shift with high probability under the stated assumptions.The result assumes Euclidean covariates with finite squared-exponential moments and a bounded Euclidean label space.
4.2. Estimation of Y|X Shift: Under deterministic labeling, the γ*-Y|X estimator accurately estimates the shift, while under stochastic labeling its bias is bounded by irreducible error.For learnable problems, the irreducible error is small relative to overall label variability, limiting substantial overestimation.
4.3. DataShifts Algorithm: DataShifts combines estimators for X and γ*-Y|X shifts to quantify distribution shifts and estimate learning-error bounds from finite samples.The algorithm is presented as a plug-and-play procedure based on the preceding theoretical results.

5. Experiments

Experiments evaluate the framework on regression, binary classification, and multi-class classification, finding that estimated bounds track test error across practical tasks. Synthetic comparisons further show that the proposed bound becomes tighter than the existing bound as distribution shifts increase.

5.1. Practical Tasks: Estimated error bounds track test error across tabular regression, ColoredMNIST, and PACS, supporting the general effectiveness of the bound and estimators.The bound is tight on the enzyme-family regression task, tracks checkpoints on ColoredMNIST, and preserves the test-error trend on PACS despite looser magnitude.
5.1. Novozymes Enzyme Prediction: Large γ*-Y|X shifts across enzyme families drive the generalization failure in the Novozymes regression competition.The estimated bound lies just above the diagonal between test error and bound across target domains.
5.3. Synthetic Binary Classification: As synthetic X or Y|X shifts increase, the proposed bound becomes tighter than the existing bound.The existing bound becomes especially looser as Y|X shift increases, while X shift has only a minor effect on test error in the logistic-regression setup.
5.2. ColoredMNIST and PACS: On ColoredMNIST, MMD and CORAL produce smaller estimated bounds and consequently lower error than the other evaluated settings.Their points lie closer to the lower-left region of the bound-versus-error plot.
5.2. ColoredMNIST and PACS: On PACS, the estimated bound is looser in magnitude but remains consistently aligned with test-error trends across runs.PACS is the more complex multi-class image-classification task in this comparison.

6. Conclusion

The paper develops a general, estimable framework for learning under distribution shift by defining γ∗-Y|X shift through entropic optimal transport and deriving corresponding bounds and estimators.

Concentration-guaranteed estimators and the plug-and-play DataShifts algorithm enable sample-based quantification of both shifts and the learning bound.The authors report validation on practical and synthetic tasks.
The framework introduces a well-defined γ∗-Y|X shift and a learning bound that jointly characterizes covariate and concept shifts.The construction addresses support mismatch and extends beyond restrictive existing settings.
Existing theories are limited by deterministic labeling, narrow classification losses, and non-estimable concept-shift definitions.These restrictions impede rigorous analysis of distribution shift in applications.
Entropic optimal transport yields a unique optimizer under the stated positive-regularization setting, supporting the framework’s well-defined shift construction.The proof establishes uniqueness through strict convexity of the entropic objective.

C.5. Proof of Lemma 3.6

This proof establishes structural properties of the optimal coupling and uses them to derive the learning-bound decomposition.

When β = 0, the entropic optimal transport problem reduces to Wasserstein-1 transport.The optimal value is zero when the source and target distributions coincide, forcing the coupling onto the diagonal.
For β > 0, strict convexity of the entropy-regularized objective makes the optimal coupling unique.The uniqueness removes ambiguity in the concept-shift quantity defined from that coupling.
The coupling preserves the source and target covariate marginals and assigns no mass outside their support-product region.This support property ensures that conditional distributions are evaluated only where the coupling places mass.
The theorem’s bound follows by combining the coupling construction with separate covariate and label-space transport terms.The proof explicitly bounds the covariate term and then combines the intermediate inequalities.

C.12. Proof of Theorem 4.2

The proof derives concentration for a debiased Wasserstein-based estimator by controlling empirical transport errors through sample splitting, algebraic inequalities, and marginal concentration.

Sample splitting creates independent half-sample empirical measures, enabling separate control of within-domain and cross-domain transport errors.The proof then applies triangle inequalities and quadratic bounds to assemble a clean error bound.
The estimator’s deviation is reduced to deviations of empirical Wasserstein distances from their population counterparts.A deterministic inequality links the absolute deviation to an auxiliary squared-distance statistic.
Finite squared-exponential moments yield concentration for the marginal empirical Wasserstein distances when the source and target sample sizes are sufficiently large.The argument invokes transport-entropy and empirical-Wasserstein concentration results.
The final deviation guarantee is obtained by choosing the auxiliary threshold to match the target error level and combining the resulting exponential terms.The proof concludes after substituting the threshold into the concentration inequality.

C.14. Proof of Theorem 4.5

The proof establishes concentration for the concept-shift estimator by separating label noise from coupling instability and controlling each component with bounded differences, Lipschitzness, and entropic-transport stability.

The estimator’s error decomposes into a label-noise term and a coupling-stability term.This separates randomness from labels from the effect of estimating the optimal coupling.
Conditioning on covariates makes the empirical coupling fixed, allowing McDiarmid’s inequality to control label-induced deviations.The resulting conditional bound is then integrated over the covariates.
The relevant population function is Lipschitz in the paired covariates, with the label-space Lipschitz constant controlling its sensitivity.Kantorovich–Rubinstein duality converts this Lipschitz property into a Wasserstein bound between couplings.
Entropic optimal-transport stability and concentration of the marginal empirical measures control the coupling-stability term.Combining both components yields the theorem’s concentration guarantee.

C.16. Proof of Proposition 4.7

The proof establishes nonnegativity of the estimator gap and bounds it using conditional means and irreducible errors under stochastic labeling.

The estimator gap is nonnegative because the product coupling cannot outperform the optimal coupling defining S_pair.The pointwise difference f(xS, xT) − S_pair(xS, xT) is nonnegative, so integrating yields Δ ≥ 0.
The upper bound follows by applying the triangle inequality to independent source and target labels around their conditional means.The decomposition separates source variability, the distance between conditional means, and target variability.
Jensen’s inequality lower-bounds the optimal transport distance by the distance between source and target conditional means.This converts the coupling-based transport term into a mean-distance expression.
Combining the bounds and integrating over γ* yields the proposition’s final inequality.The proof takes expectation over the γ* coupling, uses its source and target marginals, and combines the resulting terms.
Under squared loss, conditional expectations minimize the conditional prediction risk and attain the irreducible-error infima.The source and target conditional means therefore connect the transport bound to irreducible errors.

D. Analysis of Lipschitz Constants: Results and Proofs

This section derives Lipschitz constants for sigmoid, logistic, linear multiclass, and MLP models under several norm choices.

D.1–D.2: The sigmoid is 1/4-Lipschitz, yielding a logistic-regression constant of ∥w∥2/4 under the ℓ2 norm.The derivative is bounded through σ′(x)=σ(x)(1−σ(x)), and the mean value theorem transfers this bound to logistic regression.
D.3: The linear classifier’s optimal ℓ2-to-ℓ2 constant is given by the corresponding matrix operator norm.The derivation uses the softmax Jacobian and bounds its variance-based quadratic form.
D.3: The linear-classifier proof attains the range-based bound by concentrating mass on indices achieving the maximum and minimum row projections.The extremal distribution produces the range-squared-over-eight expression used in the bound.
D.3: The linear classifier has an optimal ℓ2-to-ℓ1 Lipschitz constant characterized by the induced operator norm ∥·∥2→1.The proof reduces the softmax Jacobian bound to the maximum mean absolute deviation over the row vectors of W.
D.4: For MLPs, the section formulates an SDP-certified Lipschitz bound for slope-restricted activations using block-diagonal layer variables.The construction defines the network recursion, layer matrices, and a block-diagonal decision variable for the SDP.

E.1. Experiments on Estimator Sensitivity

The estimator sensitivity experiment evaluates β on ColoredMNIST and finds stable estimates across magnitude changes, while selecting β = 0.2 for later experiments.

The coefficients of variation are 1.076% for ŜCov and 0.990% for ŜCpt across magnitude changes in β.The experiment samples 10,000 representation-label pairs per domain and repeats the DataShifts estimation procedure.
β = 0.2 is used in the main experiments to balance entropic-OT speed and accuracy.The choice follows the observation that entropic OT becomes faster as β grows.

E.2. Experiments on the Bias under Stochastic Labeling

The stochastic-labeling experiment tests estimator bias as label noise increases and finds small bias at low noise, with bounded overestimation at high noise.

When σ is small, the bias remains very small and ŜCpt stays close to the true Y|X shift Sγ* Cpt = 1.0.The synthetic source and target shifts differ by 1.0 in their conditional-label means.
At σ = 0.5, the estimator still does not notably overestimate despite noise reaching half the true Y|X shift.The experiment estimates average bias over repeated samples using β = 0.2.
As σ grows far beyond 1.0, identifiability worsens and overestimation appears, but the bias remains below the irreducible-error bound.This behavior matches the bound established in Proposition 4.7.