Rural Readiness: Domain Generalization with Adversarially Chosen Domains

Cynthia Dwork; Andisheh Ghasemi; Lunjia Hu

cs.LGOct 29, 2026

Rural Readiness: Domain Generalization with Adversarially Chosen Domains

Authors: Cynthia Dwork, Andisheh Ghasemi, Lunjia Hu

Organizations: Harvard University · Northeastern University

Abstract

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

Panel of Figure 1 — Figure 1: Geometry of the benchmark $\mathcal{F}_{\mathcal{D}}(\beta)$ . Each petal represents the hypotheses whose population error is at most $\beta$ on one source $D_{i}$ . Their intersection is $\mathcal{F}_{\mathcal{D}}(\beta)$ ; the inner region $\mathcal{F}_{\mathcal{D}}(\alpha)$ contains the universal predictor $f^{\star}$ from Definition 1 . The classifier $f^{\prime}\in\argmax_{f\in\mathcal{F}_{\mathcal{D}}(\beta)}\mathrm{err}_{D^{\prime}}(f)$ is the benchmark member with largest target error. Both $f^{\star}$ and $f^{\prime}$ 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$	$C_{1}$	$C_{2}$	$\cdots$	$C_{k}$
$D_{1}^{\theta}$	$\alpha$	$\rho$	$\alpha$	$\cdots$	$\alpha$
$D_{2}^{\theta}$	$\alpha$	$\alpha$	$\rho$	$\cdots$	$\alpha$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$
$D_{k}^{\theta}$	$\alpha$	$\alpha$	$\alpha$	$\cdots$	$\rho$

Table 1: The two source families in the proof of Theorem 4 . In part (a), the coordinates are partitioned as

[N]=\{t\}\sqcup C_{1}\sqcup\cdots\sqcup C_{k}

. Source

s

assigns error mean

\rho

to the

M

coordinates in

C_{s}

and error mean

\alpha

to every other coordinate. Conditioning on all but

C_{s}\cup\{t\}

produces an

(M+1)

-way hidden-coordinate problem for each source, giving the

k\log M

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

\alpha

. Applying the two-coordinate reference lemma to every

s

and summing the reference query counts gives the

k\log(1/\delta)

term.

Domain Generalization

Domain generalization develops models that perform reliably in new environments without training on target-domain data.

See all 376 papers

Hierarchical Domain Generalization
Jul 17, 2026Chenxiao Yang, Zhiyuan Li, Shai Ben-David +1Domain Generalization Statistical Learning Theory
Toyota Technological Institute at Chicago · University of Waterloo
How Useful is Causal Invariance for Domain Adaptation in Finite-Sample Settings?
Jun 10, 2026Julia Kostin, Kasra Jalaldoust, Elias Bareinboim +2Structural Causal Models Statistical Learning Theory
Department of Computer Science, ETH Zurich · Causal Artificial Intelligence Lab, Columbia University · Department of Statistics, Columbia University
Abduction-Deduction Entanglement: Domain Generalization via Representation Transplants
May 24, 2026Kasra Jalaldoust, Elias BareinboumDomain Generalization OOD Generalization
Department of Computer Science Columbia University New York, NY 10027, USA

Jul 17, 2026J/K move · Enter open · S save

Hierarchical Domain Generalization

Chenxiao Yang, Zhiyuan Li, Shai Ben-David, Nathan Srebro

Toyota Technological Institute at Chicago · University of Waterloo

Domain Generalization Statistical Learning Theory Generalization Bounds

Open paper AskPDF arXiv

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.

Abstract

Domain Generalization

Explore similar work

Hierarchical Domain Generalization

How Useful is Causal Invariance for Domain Adaptation in Finite-Sample Settings?

Abduction-Deduction Entanglement: Domain Generalization via Representation Transplants