Impossibility Of Unrestricted Distribution-Shift Adaptation

What Can Unlabeled Target Data Identify?

Suppose a learning procedure receives labeled observations from a source population and covariates, but no labels, from a target population. The target population is where predictions will be used, so a central question is whether these observations determine how well a prediction rule performs there. Without restrictions linking the two populations, they need not: target covariates reveal where target observations lie, but do not reveal how their labels relate to those covariates.

An impossibility result makes this limitation exact. It exhibits two possible target environments that produce the same distribution of all available observations, yet have different target risks or require different optimal predictions. Since a procedure has the same information in both environments, it cannot reliably distinguish which answer is correct.

Definition: Let $P_S$ be a source distribution for a labeled pair $(X,Y)$, and let $P_T$ be a target distribution for $(X,Y)$. The available data consist of $n$ independent observations from $P_S$ and $m$ independent observations from the target covariate marginal $P_T^X$, with the two samples independent. For a prediction rule $h$ and loss function $L$, its target risk is $$ R_T(h)=E_{(X,Y)\sim P_T}[L(h(X),Y)]. $$ The unrestricted setting places no condition relating $P_S$ to $P_T$.

We use binary classification with $X,Y\in\{0,1\}$ and zero-one loss $L(a,y)=\mathbf{1}\{a\ne y\}$. The constructions below need only finite sample spaces, so there are no measure-theoretic complications. In a uniform claim, an estimator must work over every source and target distribution permitted by the stated assumptions, not merely over a convenient subset.

Worked Examples of Indistinguishable Environments

Worked Example: One Covariate Value, Two Target Risks

Let $X$ always equal $0$ in the target population. Consider two target distributions: under $P_T^{(0)}$, $Y=0$ with probability one; under $P_T^{(1)}$, $Y=1$ with probability one. In both environments the target covariate sample consists only of zeros, whatever $m$ is.

Fix the prediction rule $h_0(x)=0$. Its target risk in the first environment is $$ R_T^{(0)}(h_0)=P_T^{(0)}(Y\ne 0)=0, $$ whereas in the second it is $$ R_T^{(1)}(h_0)=P_T^{(1)}(Y\ne 0)=1. $$ Choose any one common source distribution in the two environments. The labeled source data then have the same distribution in both, and so do the unlabeled target covariates. The available data cannot reveal whether the target risk of $h_0$ is zero or one.

Worked Example: Same Target Covariates, Different Optimal Rules

Let the target covariate be uniform on $\{0,1\}$. In environment A set $Y=X$ with probability one; in environment B set $Y=1-X$ with probability one. Thus each environment assigns probability $1/2$ to each target covariate value.

The rule $h_A(x)=x$ has risk zero in A, since it always predicts the target label correctly. In B it is wrong at both covariate values, so its risk is one. Conversely, $h_B(x)=1-x$ has risk one in A and zero in B. Each is the unique target-optimal rule on the two covariate values.

If the source distribution is fixed and identical in both environments, then the labeled source samples have identical laws. The target covariate samples also have identical laws because the target marginals $P_T^X$ match. Even unlimited observations of these available data cannot identify which target labeling mechanism holds.

Worked Example: The Best Possible Randomized Choice

Return to the single target covariate value $X=0$, with the two possible target labels $Y=0$ and $Y=1$. A learner may use randomization, or random data, to output the prediction $1$ with probability $a$, where $0\le a\le 1$. Because the observed-data distribution is the same in both environments, the value of $a$ is the same in each.

In the environment with label zero, the learner's expected zero-one risk is $a$. In the environment with label one, its expected risk is $1-a$. Therefore its larger expected risk is $$ \max\{a,1-a\}\ge \frac{a+(1-a)}{2}=\frac12. $$ The bound is attained by $a=1/2$, which gives risk $1/2$ in each environment. Randomization can balance the two possibilities, but cannot guarantee risk below $1/2$ in both.

A Lower Bound for Target-Risk Estimation

The first formal consequence concerns estimating risk, even for a fixed prediction rule. Uniform consistency would require that, for every positive tolerance, the probability of an estimation error exceeding that tolerance becomes uniformly small as the sample sizes grow. The following theorem shows that this is impossible without restrictions linking the distributions.

Theorem: Consider the class of all source and target distributions on the binary spaces above. For every sample size $n,m$, every estimator $\widehat R$ based on $n$ labeled source observations and $m$ unlabeled target covariates, and every $\epsilon$ with $0<\epsilon<1/2$, there is one of two target environments with the same available-data distribution such that $$ P\bigl(|\widehat R-R_T(h_0)|>\epsilon\bigr)\ge \frac12, $$ where $h_0(x)=0$.

Proof. Use the two target environments from the first worked example, and choose the same source distribution in both. The full available data therefore have one common probability law, say $Q$, in the two environments. Write $A_0=\{|\widehat R-0|\le\epsilon\}$ and $A_1=\{|\widehat R-1|\le\epsilon\}$. Since $\epsilon<1/2$, the intervals $[-\epsilon,\epsilon]$ and $[1-\epsilon,1+\epsilon]$ are disjoint. Thus $A_0$ and $A_1$ are disjoint events under $Q$, and $$ Q(A_0)+Q(A_1)\le 1. $$ At least one of these two accuracy probabilities is at most $1/2$. In the corresponding environment, the probability of error greater than $\epsilon$ is at least $1/2$. This holds for every $n,m$, so increasing either sample size cannot make the estimator uniformly consistent over this unrestricted class. $\square$

The event distinction matters. The disjoint events above are accuracy events: they say the estimate is within $\epsilon$ of the true risk. Their probabilities cannot both be large. The conclusion is that in at least one environment the probability of error greater than $\epsilon$ is at least $1/2$—not that the probability of error is small.

A Lower Bound for Target-Optimal Prediction

A parallel argument applies to learning a rule rather than estimating the risk of a fixed rule. Define the target Bayes risk as the smallest target risk achievable by any prediction rule. In the deterministic-label examples, this risk is zero, and the target-optimal prediction is known if the environment is known. The learner, however, does not know which indistinguishable environment it faces.

Theorem: For the two single-covariate target environments with deterministic labels zero and one, any learning procedure based on labeled source data and unlabeled target covariates has expected target excess risk at least $1/2$ in one of the environments. Here excess risk is $R_T(\widehat h)-\inf_h R_T(h)$, with expectation taken over the observed data and any learner randomization.

Proof. The available-data law is identical in the two environments, so the learner's output distribution is also identical. Let $a$ be the probability, under that shared output distribution, that its prediction at $X=0$ is one. The Bayes risk in each environment is zero. In the environment with target label zero, the expected excess risk is $a$, because precisely the predictions equal to one are wrong. In the environment with target label one, the expected excess risk is $1-a$. Since $$ \max\{a,1-a\}\ge \frac12, $$ at least one environment has expected excess risk at least $1/2$. This reasoning includes randomized procedures, because $a$ accounts for both data-induced and internal randomization. $\square$

The bound is not a claim that learning is always futile. It says that, over an unrestricted class, no procedure can promise small target excess risk uniformly. The same construction also shows why knowing the target covariate distribution alone cannot determine which prediction is optimal: that distribution is identical in the two cases.

What the Impossibility Does—and Does Not—Say

These results concern the absence of any assumptions linking source and target labels. They do not rule out adaptation when the problem supplies such a link. Standard approaches impose conditions such as covariate shift, label shift, or a specified model for the change between populations. These assumptions restrict the possible target environments; whether they are credible and whether their consequences are identifiable must be assessed for the application.

The key issue is not simply sample size. In the constructions, the observed-data distributions are exactly equal across environments. Consequently, even infinitely many source labels and target covariates would not distinguish them. More data of the same observable types cannot resolve a difference that those data never encode.

A common mistake is to argue that because two accuracy events are disjoint, the estimator's error probability must be small in at least one environment. That reverses the conclusion. Disjointness bounds the sum of the accuracy probabilities above by one, so one accuracy probability is at most $1/2$; equivalently, in that environment the probability of error greater than $\epsilon$ is at least $1/2$. Always name whether an event represents accuracy or error before interpreting its probability.

Key takeaway: Without restrictions linking source and target distributions, labeled source data and unlabeled target covariates can be identical under environments with different target risks and different optimal predictions. Uniform target-risk estimation and uniformly reliable target adaptation are therefore impossible over the unrestricted class.

Check Your Understanding

Use the definitions and arguments above to answer these questions.

Why do the two single-covariate environments give exactly the same distribution for all available observations?
For what values of $\epsilon$ are the two risk-accuracy intervals in the theorem disjoint? What changes at $\epsilon=1/2$?
In the two-covariate example, calculate the risks of $h_A(x)=x$ in both target environments.
Why does the risk-estimation lower bound still apply when the sample sizes increase without bound?
What assumption would need to be added before the impossibility result could be avoided, and why must it restrict the possible target environments?