Beyond Discrepancy: A Closer Look at the Theory of Distribution Shift

Learning theory of distribution shift generally bounds performance on the target distribution as a function of the discrepancy between the source and target, rarely guaranteeing high target accuracy. Instead of relying on the discrepancy, we adopt an assumption inspired by Invariant Risk Minimization, where the source and target distributions are unified by an unknown feature projection. Under this assumption, we show that a learner can leverage the relationship between the source and target distributions to greatly reduce the number of required target samples to achieve high accuracy. To quantify this effect, we introduce a new combinatorial complexity measure—the distance dimension—and derive bounds for linear maps and neural networks.