Predictive models trained at well-resourced data-rich institutions often fail when deployed in new populations. Motivated by the goal of building clinical diagnosis and decision-making algorithms for data-scarce rural populations using the general knowledge learned from data-rich hospitals, we formulate the fundamental question of domain generalization with adversarially chosen domains, which asks a learner to perform on any unseen target domain nearly as well as the worst hypothesis consistent with the evidence from the observed source domains. Assuming only that the hypothesis class contains a "universal" predictor with small error on all k source domains, we characterize the sample complexity of this objective up to logarithmic factors. Letting d denote the VC dimension of the hypothesis class, we find, somewhat surprisingly, that the sample complexity reduces significantly from Ω(dk) to O(d) under a small relaxation of the learning goal in which, roughly speaking, we allow the learned model to compete with hypotheses that perform well on 99% instead of 100% of the source domains. By applying this insight to the meta-distributional setting, in which source domains are selected according to a distribution on distributions, we obtain a corresponding improvement over known sample complexity upper bounds. We also study the effect of data access to the target domain and show that a small labeled sample from the target domain does not improve the worst-case sample complexity on the source domains.
Figures & tables
Figure 1: Geometry of the benchmark FD(β) . Each petal represents the hypotheses whose population error is at most β on one source Di . Their intersection is FD(β) ; the inner region FD(α) contains the universal predictor f⋆ from Definition 1 . The classifier f′∈argmaxf∈FD(β)errD′(f) is the benchmark member with largest target error. Both f⋆ and f′ satisfy the relevant source constraints, but without assumptions relating source and target domains, source evidence alone gives no smaller uniform target guarantee than the error of this worst benchmark member.
source
t
C1
C2
⋯
Ck
D1θ
α
ρ
α
⋯
α
D2θ
α
α
ρ
⋯
α
⋮
⋮
⋮
⋮
⋱
⋮
Dkθ
α
α
α
⋯
ρ
Table 1: The two source families in the proof of Theorem 4 . In part (a), the coordinates are partitioned as [N]={t}⊔C1⊔⋯⊔Ck . Source s assigns error mean ρ to the M coordinates in Cs and error mean α to every other coordinate. Conditioning on all but Cs∪{t} produces an (M+1) -way hidden-coordinate problem for each source, giving the klogM term. Part (b) shows the second family for a fixed possible owner s : the alternatives interchange which of u,v is exceptional, whereas the common reference keeps both at mean α . Applying the two-coordinate reference lemma to every s and summing the reference query counts gives the klog(1/δ) term.
We study hierarchical domain generalization as a problem of extrapolation from finite observed regions to an entire instance space, replacing i.i.d. sampling with arbitrary domain hierarchies. We show that the central obstruction is not only the complexity of the hypothesis class, but the train/test domain partition through which evidence is revealed. In particular, no matter how small the class or how large the training size, some partition makes generalization fail for some target. These results suggest that modern generalization theory must treat domain structure as a first-class object.
Chenxiao Yang, Zhiyuan Li, Shai Ben-David +1
Toyota Technological Institute at Chicago · University of Waterloo
Machine learning models often degrade when they are deployed on a target distribution that differs from the source distributions they were trained on. Recent work in causality-based domain generalization has shown how shared causal structure between domains can induce invariant predictors, e.g., models on a subset of features which have stable risk across structured domain shifts. However, the extent to which such population-level causal invariances can lead to gains in finite-sample settings remains underexplored. In particular, in practice we often have access to a few labeled target samples, a setting called supervised domain adaptation (sDA). In this paper, we explore when (full or partial) causal knowledge can provably improve supervised domain adaptation. As a first step, we study linear regression, where full or partial causal knowledge specifies a collection of invariant or possibly invariant feature subsets, each yielding a source-trained candidate predictor. We derive matching upper and lower bounds showing that finite-sample gains are governed by the target-risk margins separating the candidates, together with the finite-source estimation error. When these margins are sufficiently large relative to nQ, an adaptive aggregation procedure can match the best candidate predictor while avoiding negative transfer relative to target-only learning. On the other hand, when the margins are too small, no algorithm can reliably exploit the candidate collection to obtain faster finite-sample rates. We further connect these margins to structural shift magnitude in linear SCMs and validate the theory on real-world causal benchmarks.
Julia Kostin, Kasra Jalaldoust, Elias Bareinboim +2
Department of Computer Science, ETH Zurich · Causal Artificial Intelligence Lab, Columbia University · Department of Statistics, Columbia University
Prediction models trained under the source distribution do not generalize well to a different target distribution. A valid inference about an unseen data distribution must be anchored by the invariance of certain causal mechanisms that generate the source and target data, however, these structural invariances are non-identifiable from the source data alone. Under mild causal assumptions about the data, we show that the optimal prediction in the target is in fact partially identifiable by the source distribution. The result rests on a simple observation: In any domain, the optimal prediction can be factorized into what we call a pair of abduction and deduction maps, where the abduction map makes inference about some unobserved variables (possibly confounders) from the observed variables and the deduction map predicts the label using both the observed and inferred quantities. Access to large source data pins down the optimal prediction, thus constrains the valid abduction-deduction ensembles that produce it -- a non-identifiability that we call the abduction-deduction entanglement. To leverage this, we parameterize the constrained family using what we call a representation transplant, that is a specific linear transformation in the representation space that manipulates the abduction content of the representation while retaining the deduction component. Invariance of the causal mechanism generating the label implies existence of an invariant deduction map between source and target. Thus, we can search the space of plausible target distributions via a parametric transplant. We use this scheme in a learner-adversary game that, under an idealistic optimization, provably terminates with the learner having the minimax-optimal target prediction. Evaluations verify the theory, showing that the method is competitive in DG benchmarks.
Kasra Jalaldoust, Elias Bareinboum
Department of Computer Science Columbia University New York, NY 10027, USA