betaFeedback

WorksComputer Science

Rural Readiness: Domain Generalization with Adversarially Chosen Domains

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 kk source domains, we characterize the sample complexity of this objective up to logarithmic factors. Letting dd denote the VC dimension of the hypothesis class, we find, somewhat surprisingly, that the sample complexity reduces significantly from Ω(dk)Ω(dk) to O(d)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.

Introduction

Consider the task of creating a diagnostic tool that, given information about a patient such as lab results and vitals, outputs a score in [0,1][0,1], with higher numbers viewed as a positive diagnosis. Suppose well-funded, data-rich medical research centers have developed diagnostic tools that perform well on the local populations on which they were trained. It is well known among medical researchers that a scoring function developed in one facility can be significantly less effective at other facilities [13, 36]. This can arise from technical factors such as the methods and batches of chemicals used for specimen collection, as well as population differences involving diets, environmental exposures, and genetic factors. These factors can change the joint probability distribution over patient information and ground-truth diagnoses; we call such a distribution a domain. The source domains on which a diagnostic tool is trained may differ from the target domains on which it is evaluated. The resulting performance degradation from source to target is known as the Harvard–Stanford problem: letting DHD_H and DSD_S denote the distributions on which Harvard and Stanford predictors fHf_H and fSf_S are trained, respectively, the cross-domain errors err⁡DS(fH)\operatorname{err}_{D_S}(f_H) and err⁡DH(fS)\operatorname{err}_{D_H}(f_S) can be higher than the within-domain errors err⁡DH(fH)\operatorname{err}_{D_H}(f_H) and err⁡DS(fS)\operatorname{err}_{D_S}(f_S). As long as in practice each predictor is used only for the distribution on which it is trained, there is no immediate problem.

Unfortunately, not all populations live near well-resourced, data-rich, cutting-edge medical research centers. At the same time, it is believed that human populations are not all so different from one another. This led Deng et al. [13] to pose the following question: assuming the existence of an “α\alpha-universal” predictor, meaning, informally, that it has error at most α\alpha on all populations of interest, for some small α>0\alpha> 0 (although it might not be optimal for any single population), can we leverage samples from the observed populations to construct a β\beta-universal predictor, for some β≥α\beta\ge\alpha? We call this goal achieving rural readiness; it is closely related to domain generalization. Our formulation without assumptions relating different populations is one of our principal contributions. As noted in Deng et al. [13], rural readiness “provides a new dimension of fairness, transferring the benefit of federal research dollars from preeminent bench to geographically remote bedside.”

A simple example shows that, absent assumptions relating populations, achieving absolute rural readiness using data collected from even a large set of observed populations can be impossible: if all observed populations are identical, and if these identical distributions differ markedly from an unobserved population, then there is little reason to think lessons learned from the observed populations will generalize to the new population. This suggests a competitive notion capturing the goal of building a scoring function that generalizes to unseen target domains “as well as possible” given the source domains that have been observed. We call this conditional rural readiness, or simply rural readiness, since the absolute version is impossible. We describe the competitive learning goal as follows.

Fix a hypothesis class F⊆{f:X→{0,1}}\mathcal{F} \subseteq\{f : \mathcal{X} \to\{0,1\}\}, where X\mathcal{X} is an instance space (in our discussion, its elements describe patients). Although in the motivating discussion, we assume there is an α\alpha-universal predictor that has error at most α\alpha on all populations of interest, in our formal treatment we assume only that F\mathcal{F} contains a predictor f⋆f^\star with error at most α\alpha on each of the observed source domains. We call any hypothesis f⋆∈Ff^\star\in\mathcal{F} satisfying this property α\alpha-universal. This weaker assumption suffices for our competitive learning goal. In particular, f⋆f^\star need not have low error on the unobserved target domain.1 Throughout the paper, our upper bounds hold under this source-only assumption, whereas our lower bounds hold even in the easier setting where f⋆f^\star has zero error on the target domain.

Each observed source domain eliminates hypotheses whose error exceeds β\beta on that domain. The survivors form a benchmark set. Without assumptions relating sources to targets, the source data provide no basis for preferring one surviving hypothesis over another on an unseen target DD. We therefore require the learned classifier to perform, up to an additive slack, at least as well as the worst-performing benchmark hypothesis on DD. If the sources are informative, every benchmark hypothesis performs well on the target domain; if they are not, the benchmark permits large target error and the guarantee appropriately becomes vacuous.

We also consider a larger, relaxed benchmark. If a function f∈Ff \in\mathcal{F} performs well on, say, 99% rather than 100% of the observed sources, this may still be evidence that it may perform well on target distributions. The relaxed benchmark therefore permits a hypothesis to fail on a γ\gamma fraction of the sources. It contains the strict benchmark, which permits no failures, but may include additional members of F\mathcal{F}.

We study the sample complexity of achieving (conditional) rural readiness, assuming only the existence of an α\alpha-universal predictor in F\mathcal{F}, obtaining upper and lower bounds that match up to logarithmic factors for both the strict and relaxed benchmark sets. A key insight from our analysis is that, perhaps surprisingly, the sample complexity for the relaxed version is dramatically smaller than for the strict version.

Rural readiness is a domain generalization problem in which the source and target domains can all be chosen adversarially. The formulation has applications beyond the medical scenario that originally motivated our research, so in our technical results we use the term adversarial domain generalization for this learning goal.2

Summary of Contributions

We formalize the problem of achieving (conditional) rural readiness without assumptions relating the source and target distributions, and characterize its sample complexity. Our key modeling contribution is a competitive formulation with an appropriate choice of benchmark that formalizes the goal of doing as well as possible given what has been observed.

Adversarial Domain Generalization. We formalize the objective of conditional rural readiness using the adversarial domain generalization task in § 2. In this task, the goal is to design a learning algorithm that collects data from kk adversarially chosen source domains D=(D1,…,Dk)\mathcal{D} = (D_1, \ldots, D_k), and outputs a model that achieves competitive error on unseen target domains. We make the α\alpha-universality assumption: there exists an unknown f⋆f^\star from a hypothesis class F\mathcal{F} achieving error at most α\alpha on every source domain. The competitive error goal is defined with respect to the benchmark set FD(β)\mathcal{F}_{\mathcal{D}}(\beta) consisting of hypotheses f∈Ff \in\mathcal{F} whose error on every source domain is at most β\beta, for β≥α\beta\ge\alpha. We say a model achieves competitive error on a target domain if its error is at most the maximum error of a benchmark f∈FD(β)f \in\mathcal{F}_{\mathcal{D}}(\beta) on that target domain, plus ϵ\epsilon. We also consider the larger, relaxed benchmark set FD(γ)(β)\mathcal{F}_{\mathcal{D}}^{(\gamma)}(\beta) consisting of hypotheses f∈Ff \in\mathcal{F} that achieve error at most β\beta on at least a (1−γ)(1-\gamma) fraction of the kk source domains.

Near-Matching Bounds for the Strict Benchmark. We prove near-matching upper and lower bounds on the sample complexity of adversarial domain generalization in § 3 and § 4. We start with the setting with the strict benchmark set FD(β)\mathcal{F}_{\mathcal{D}}(\beta):

Theorem 1 (informal, see Corollary 6 and Theorem 9). Assume $0 \le \alpha < \beta < 1/4$, 0≤ϵ<1/40 \le\epsilon< 1/4, 0<δ<1/40 < \delta< 1/4, and d≥10log⁡kd \ge10 \log k. In the worst case over hypothesis classes of VC dimension at most $d, the sample complexity of adversarial domain generalization is, up to logarithmic factors,

β(β−α)2⋅k(d+log⁡(1/δ)).\frac{\beta}{(\beta-\alpha)^2} \cdot k\bigl(d+\log(1/\delta)\bigr).

The Ω(kd)\Omega(kd) lower bound is in sharp contrast to recent results on multi-distribution learning Zhang et al. [49], where the sample complexity for finding a predictor that performs well on kk given distributions is only an additive k+dk+d. When β>2α\beta> 2\alpha, these better bounds apply to our problem if the family F\mathcal{F} satisfies a strong majority-closure condition: for every finite multiset f1,…,fT∈Ff_1,\ldots,f_T \in\mathcal{F},

the function that assigns to xx the majority value assigned to xx by f1,…,fTf_1,\ldots,f_T is also in F\mathcal{F}; see Appendix § 12.

A strength of our sample complexity lower bound in Theorem 1 is that it holds for an easier task. Our adversarial domain generalization task requires the learner to output a single model that achieves a competitive error guarantee for all target domains. Our lower bound holds even if the error guarantee is only required for a single target domain that depends solely on the source domains and is independent of the sampled data points and the learner’s randomness. Moreover, that single target domain is fully realizable: the α\alpha-universal hypothesis f⋆∈Ff^\star\in\mathcal{F} is the only member of the benchmark family FD(β)\mathcal{F}_{\mathcal{D}}(\beta) and it achieves zero error on the target domain.

To prove the lower bound, we carefully construct a family of hard instances, where solving the adversarial domain generalization problem requires the learner to fully identify f⋆f^\star. This construction allows us to use an adversarial domain generalization learner to solve hidden-coordinate identification problems. These problems isolate the key information-theoretic insight in our proof. We describe these problems in § 3.1 and apply standard information-theoretic tools (e.g. Fano’s inequality and the information processing inequality for KL divergences) to prove lower bounds for them in Appendix § 10. This allows us to present the rest of the proof in a modular way in § 3.

To prove the sample complexity upper bound in Theorem 1, we design an algorithm that achieves a stronger goal: with probability at least 1−δ1-\delta, the algorithm outputs a member of the benchmark set FD(β)\mathcal{F}_{\mathcal{D}}(\beta). Since our competitive error goal is with respect to the worst hypotheses in the benchmark set, any member of the benchmark set is a valid solution to the adversarial domain generalization problem. Our algorithm uses source data points to estimate the error of hypotheses f∈Ff \in\mathcal{F} on every source domain, in order to rule out all hypotheses not in the benchmark set FD(β)\mathcal{F}_{\mathcal{D}}(\beta). The α\alpha-universality assumption ensures that the algorithm does not rule out all hypotheses, allowing the algorithm to choose its output from the remaining hypotheses. Obtaining a tight upper bound requires carefully designing the criterion for ruling out hypotheses, which we describe in more detail in § 4.

Near-Matching Bounds for a Relaxed Benchmark. Our results make no distributional assumptions, but they do reflect a distributional optimism: the observed distributions are sufficiently informative to teach us how to make predictions for as-yet-unobserved distributions. Our relaxed benchmark captures even greater optimism, specifically, that the information needed to make good predictions on an unobserved distribution can be learned even while disregarding a small fraction of the observed sources. This could happen, for example, if we believe some observed sources may be pathological or anomalous.

If there is reason to be strongly optimistic in the above sense, we can aim for a relaxed benchmark class FD(γ)(β)\mathcal{F}_{\mathcal{D}}^{(\gamma)}(\beta) in which we retain candidates from F\mathcal{F} that may fail to be accurate on up to a small constant fraction γ\gamma of the observed domains. This fully eliminates the linear dependence on kk in Theorem 1:

Theorem 2 (informal, see Corollary 6 and theorem 9). In the setting of Theorem 1, assume γ∈[1/k,1/4]\gamma\in[1/k,1/4]. In the worst case over hypothesis classes of VC dimension at most dd, the source-sample complexity of γ\gamma-relaxed adversarial domain generalization is, up to logarithmic factors,

β(β−α)2⋅1γ⋅(d+log⁡(1/δ)).\frac{\beta}{(\beta-\alpha)^2}\cdot\frac{1}{\gamma}\cdot\left(d+\log(1/\delta)\right).

Interestingly, the sample complexity bound in Theorem 2 is independent of kk, demonstrating the power of the benchmark relaxation. As an application of this result, we use it to achieve improved sample complexity for the domain generalization problem studied by Dwork et al. [16].

We prove the lower bound in Theorem 2 by reducing to the strict-benchmark bound in Theorem 1. Set r=⌊γk⌋+1r = \lfloor\gamma k \rfloor+ 1 and B=⌊k/r⌋B = \lfloor k/r \rfloor, start from a strict instance with BB sources, and repeat each source at least rr times. A hypothesis that violates the threshold on one original source then violates it on more than γk\gamma k copies. The relaxed benchmark of the repeated instance is therefore exactly the strict benchmark of the original instance.

Since the sample complexity upper bound in Theorem 2 is independent of kk, our algorithm need not collect data from every source domain when kk is large. The key idea is to sample a subset of the source domains and collect data only from those sampled domains. The size of this subset needs to be chosen carefully to obtain a tight bound. We describe the details in § 4.

Improved Upper Bounds for Meta-Generalization. There is a large literature on domain generalization when the observed distributions are themselves drawn from a distribution over distributions. Dwork, Hu, and Shao ([16]) model this in the PAC framework, introduce the domain shattering dimension, and give tight bounds on the number of randomly sampled domains needed to achieve absolute rural readiness. In this setting, we prove that every member of the relaxed benchmark generalizes to new domains from the meta-distribution. For constant parameters, combining this transfer result with our learner gives total labeled sample complexity O~(VC⁡(F))\widetilde{O}(\operatorname{VC}(\mathcal{F})), independent of kk, rather than the O~(kVC⁡(F))\widetilde{O}(k\operatorname{VC}(\mathcal{F})) used by the min–max ERM implementation analyzed in Dwork et al. [16]. This saving concerns labeled examples: the number kk of observed domains must still scale with the domain shattering dimension, and the transferred bad-domain probability includes an additive γ\gamma.

Data Access to the Target Domain. Our results above assume that no target data are available. Perhaps surprisingly, a small labeled target sample does not improve the worst-case source-sample complexity: the source lower bound persists until the target sample is large enough for target-only learning.

Theorem 3 (informal, see Theorem 12). Given data access to the target domain, the source-domain lower bounds in Theorems 1 and 2 continue to hold up to constant factors whenever the number of labeled target examples is smaller than a constant multiple of

d+log⁡(1/δ)ϵ2(1)\frac{d + \log(1/\delta)}{\epsilon^2} \tag*{(1)}

data points from the target domain, where ϵ\epsilon is the additive slack in the competitive error goal.

Conversely, standard agnostic learning uses O((d+log⁡(1/δ))/ϵ2)O((d + \log(1/\delta))/\epsilon^2) labeled target examples and no source examples. We also prove a realizable counterpart: even when the benchmark has zero target error, the source lower bound persists below the (d+log⁡(1/δ))/ϵ(d + \log(1/\delta))/\epsilon target-sample scale; see Theorem 21. This matches the usual realizable target-only sample complexity. These results hold in the relaxed-benchmark setting by the same repeated-source reduction (see Corollary 13).

Related Work

Speaking intuitively, both similarities and differences across observed populations can be leveraged to achieve rural readiness. Similarities help isolate invariant mechanisms that reliably transfer to unseen populations, whereas differences alert the learner to spurious or domain-specific features that must be avoided.

Approaches exploiting similarities typically seek stable causal mechanisms via invariant risk minimization [3]. Conversely, other approaches explicitly exploit domain or group differences, for example through adversarial domain discrimination [13], distributionally robust optimization across environments [38], or adversarial fairness and transfer objectives [29]. Theoretical work by Rosenfeld et al. (2021) and Gouk et al. [20] identifies specific formal settings in which invariant or general-purpose domain-generalization methods cannot improve fundamentally over empirical risk minimization (pooling-ERM). Empirical work, including Teterwak et al. [41], likewise emphasizes that carefully tuned ERM-style baselines can be highly competitive against specialized domain generalization methods on standard benchmarks. For comprehensive overviews of domain generalization and transfer learning, see Zhou et al. [50]; Wang et al. [46].

Multi-Distribution and Collaborative Learning (Observed Sources). A rich line of work investigates learning predictors evaluated exclusively across kk known source distributions. Initiated by Blum et al. [9], collaborative PAC learning characterizes the sample complexity of finding a shared classifier that simultaneously satisfies all participating domains, with matching logarithmic-overhead bounds established in relevant collaborative-PAC regimes by Nguyen and Zakynthinou [35] and Chen et al. [10]. Recent work has studied demand-driven on-demand query allocation [21], formalized open questions regarding sample complexity for VC classes [4], settled the minimax sample complexity of multi-distribution learning [37, 49], and developed derandomized collaborative algorithms [27]. Extending multi-distribution learning to noisy settings, Hanashiro et al. [22] show that in personalized multi-distribution learning, bounded label noise can preclude fast 1/ϵ1/\epsilon-type rates, leading instead to k/ϵ2k/\epsilon^{2}-type dependence or multiplicative penalties under stronger benchmarks. These frameworks assess performance strictly in-sample on observed distributions D1,…,DkD_{1},\ldots,D_{k}; in contrast, our goal is out-of-domain generalization to an unobserved, potentially adversarial target distribution D′D'.

Assumptions on Source–Target Similarity and Divergences. To generalize to an unobserved target domain, the dominant paradigm in domain adaptation and domain generalization is to restrict the discrepancy between source and target distributions through explicit geometric, statistical, or algebraic bounds. In domain adaptation, classical theory bounds target risk using discrepancy measures such as HΔH\mathcal{H}\Delta\mathcal{H}-divergence [7], while target-specific inference often uses propensity-score reweighting [25]. In domain generalization without target data, early theoretical frameworks control transfer to an unseen target by bounding distribution discrepancies in an RKHS, either by embedding domain marginal distributions [8] or minimizing maximum mean discrepancy to learn domain-invariant representations [34]. Alternatively, agnostic multi-distribution learning restricts the target domain to lie within the convex mixture simplex of the observed source distributions [32], while group-theoretic approaches bound worst-case generalization by assuming target distributions are generated by known transformation-group symmetries acting on the source data [40, 33]. In contrast to all these approaches, our adversarial domain generalization framework operates under zero target data and imposes no divergence bounds, distribution-distance constraints, mixture simplex assumptions, or transformation symmetries between the observed sources and the unseen target.

Causal Mechanisms, Drift, and Representation Learning. Beyond direct distance bounds between domains, related lines of work generalize across environments by isolating invariant causal mechanisms or shared feature representations. Causal frameworks rely on structural causal models and causal DAGs to identify invariant conditional distributions [39, 48, 19], while other works address transfer under posterior and decision-rule drift [30, 47] (Zhu et al. 2024; Zhu et al. 2025), where P(Y∣X)P(Y|X) shifts across domains. In empirical representation learning, adversarial domain generalization methods align feature representations across source domains (Zhu et al., 2022), adapting gradient-reversal techniques originally developed for source-target alignment in domain adaptation [17]. A parallel theoretical line in multi-task and representation learning guarantees transfer by assuming that all tasks share a common low-dimensional linear representation or subspace [5, 31, 26, 43, 44, 14, 42, 11]. Recent advances in this setting establish optimal subspace recovery under heterogeneous noise [15] and in extreme regimes with only constant samples per task [1]. Rather than restricting the data-generating process to specific parametric forms, causal graphs, or low-dimensional linear representations, we operate solely under the α\alpha-universality assumption over general hypothesis classes F\mathcal{F}.

Meta-Learning and Meta-Distributional Generalization. Meta-learning typically models domains as independent draws from an underlying meta-distribution M\mathcal{M}. Several formulations evaluate average performance over domains drawn from a meta-distribution [18]; in some cases this reduces to learning under the induced mixture, while other formulations retain explicit domain-level structure. Recent work also investigates fundamental ERM principles and sample requirements in meta-learning [2], or studies online meta-learning for fast parameter initialization [23, 24, 6]. When bounding uniform error across unseen domains supported on M\mathcal{M}, prior work relies on domain complexity measures such as the domain-shattering dimension introduced by Dwork et al. [16]. While the min-max ERM algorithm of Dwork et al. [16] achieves optimal domain complexity (kk), its literal implementation requires estimating observed-domain empirical errors uniformly to high precision, incurring a total sample cost of O~(k⋅VC⁡(F))\widetilde{O}(k \cdot\operatorname{VC}(\mathcal{F})). By framing meta-generalization through our relaxed benchmark, we reduce this total hospital-side sample burden to O~(VC⁡(F))\widetilde{O}(\operatorname{VC}(\mathcal{F})) for constant parameters, independent of kk, while maintaining strong out-of-domain guarantees.

Paper Organization

The rest of the paper is organized as follows. Section 2 formalizes adversarial domain generalization, universality, and the strict and relaxed benchmarks. Section 3 proves the strict and relaxed sample-complexity lower bounds, while Section 4 gives near-matching upper bounds via subset certificates and random-domain batches. Section 5 studies how labeled target samples change the lower bounds, and Section 6 applies the relaxed benchmark to meta-distribution generalization.

Appendix A collects the information-theoretic and VC tools, Appendix B proves the two upper bounds, Appendix C proves the hidden-coordinate lemmas, Appendix D gives the detailed target-access lower bounds, and Appendix E develops improved guarantees under majority closure.

Problem Setup: Adversarial Domain Generalization

In this section, we formally define the adversarial domain generalization problem, starting from two key concepts: the universality assumption and the benchmark set.

The Universality Assumption

Let X\mathcal{X} be an instance space and let Y={0,1}\mathcal{Y} = \{0,1\} be the binary label space. A hypothesis class is a family F\mathcal{F} of binary classifiers f:X→{0,1}f : \mathcal{X} \to\{0,1\}. For a distribution DD on X×Y\mathcal{X} \times\mathcal{Y} and a classifier f:X→{0,1}f : \mathcal{X} \to\{0,1\}, we define

err⁡D(f):=Pr⁡(x,y)∼D[f(x)≠y].\operatorname{err}_{D}(f) := \Pr_{(x,y)\sim D}[f(x) \ne y].

Suppose we have data access to kk source distributions D:=(D1,…,Dk)\mathcal{D} := (D_1,\ldots,D_k). (Note that D\mathcal{D} is a list, not a distribution.) For example, each DiD_i represents the distribution of patients xx in a specific hospital with their corresponding labels yy. The learner may request labeled examples from any source; each request to DiD_i returns a fresh i.i.d. draw from that distribution. Following the terminology in domain generalization, we call these distributions source domains.

We make the following α\alpha-universality assumption on the hypothesis class F\mathcal{F} and the source distributions D1,…,DkD_1,\ldots,D_k:

Definition 1 (α\alpha-universality). We say a hypothesis class F\mathcal{F} satisfies α\alpha-universality on distributions D1,…,DkD_1,\ldots,D_k if there exists f⋆∈Ff^\star\in\mathcal{F} such that

err⁡Di(f⋆)≤αfor all i=1,…,k.\operatorname{err}_{D_i}(f^\star) \le\alpha\quad\text{for all } i=1,\ldots,k.

References

  1. [1]Maryam Aliakbarpour, Konstantina Bairaktari, Gavin Brown, Adam Smith, Nathan Srebro, and Jonathan Ullman. Metalearning with very few samples per task. In The Thirty Seventh Annual Conference on Learning Theory, pages 46–93. PMLR, 2024.arxiv.org/abs/2312.13978
  2. [2]Yannay Alon, Steve Hanneke, Shay Moran, and Uri Shalit. On the erm principle in meta-learning. arXiv preprint arXiv:2411.17898, 2024.arxiv.org/abs/2411.17898
  3. [3]Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:1907.02893, 2019.arxiv.org/abs/1907.02893
  4. [4]Pranjal Awasthi, Nika Haghtalab, and Eric Zhao. Open problem: The sample complexity of multi-distribution learning for VC classes. In Proceedings of the Thirty-Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5943–5949. PMLR, 2023. URL https://proceedings.mlr.press/v195/awasthi23a.html.arxiv.org/abs/2307.12135
  5. [5]Maria-Florina Balcan, Avrim Blum, and Santosh Vempala. Efficient representations for lifelong learning and autoencoding. In Conference on Learning Theory, pages 191–210. PMLR, 2015.arxiv.org/abs/1411.1490
  6. [6]Maria-Florina F Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Learning-to-learn non-convex piecewise-lipschitz functions. Advances in Neural Information Processing Systems, 34:15056–15069, 2021.arxiv.org/abs/2108.08770
  7. [7]Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1):151–175, 2010.
  8. [8]Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks to a new unlabeled sample. Advances in neural information processing systems, 24, 2011.
  9. [9]Avrim Blum, Nika Haghtalab, Ariel Procaccia, and Mingda Qiao. Collaborative pac learning. Advances in Neural Information Processing Systems, 30, 2017.
  10. [10]Jiecao Chen, Qin Zhang, and Yuan Zhou. Tight bounds for collaborative pac learning via multiplicative weights. Advances in neural information processing systems, 31, 2018.arxiv.org/abs/1805.09217
  11. [11]Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. In International conference on machine learning, pages 2089–2099. PMLR, 2021.arxiv.org/abs/2102.07078
  12. [12]Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, Hoboken, NJ, 2 edition, 2006. doi: 10.1002/047174882X.DOI
  13. [13]Zhun Deng, Frances Ding, Cynthia Dwork, Rachel Hong, Giovanni Parmigiani, Prasad Patil, and Pragya Sur. Representation via representations: Domain generalization via adversarially learned invariant representations. CoRR, abs/2006.11478, 2020. URL https://arxiv.org/abs/2006.11478.
  14. [14]Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=pW2Q2xLwIMD.arxiv.org/abs/2002.09434
  15. [15]John C Duchi, Vitaly Feldman, Lunjia Hu, and Kunal Talwar. Subspace recovery from heterogeneous data with non-isotropic noise. Advances in Neural Information Processing Systems, 35: 5854–5866, 2022.arxiv.org/abs/2210.13497
  16. [16]Cynthia Dwork, Lunjia Hu, and Han Shao. How many domains suffice for domain generalization? A tight characterization via the domain shattering dimension. In D. Belgrave, C. Zhang, H. Lin, R. Pascanu, P. Koniusz, M. Ghassemi, and N. Chen, editors, Advances in Neural Information Processing Systems, volume 38, Main Conference, pages 115008–115034. Curran Associates, Inc., 2025. doi: 10.52202/085713-3835. URL https://proceedings.neurips.cc/paper_files/paper/2025/file/a6e072cfc12794cba1e861f57be8f4de-Paper-Conference.pdf.
  17. [17]Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural networks. Journal of Machine Learning Research, 17(59):1–35, 2016. URL http://jmlr.org/papers/v17/15-239.html.arxiv.org/abs/1505.07818
  18. [18]Vikas Garg, Adam Tauman Kalai, Katrina Ligett, and Steven Wu. Learn to expect the unexpected: Probably approximately correct domain generalization. In International Conference on Artificial Intelligence and Statistics, pages 3574–3582. PMLR, 2021.arxiv.org/abs/2002.05660
  19. [19]Mingming Gong, Kun Zhang, Tongliang Liu, Dacheng Tao, Clark Glymour, and Bernhard Schölkopf. Domain adaptation with conditional transferable components. In International conference on machine learning, pages 2839–2848. PMLR, 2016.pubmed.ncbi.nlm.nih.gov/28239433
  20. [20]Henry Gouk, Ondrej Bohdal, Da Li, and Timothy Hospedales. On the limitations of general purpose domain generalisation methods. arXiv preprint arXiv:2202.00563, 2022.arxiv.org/abs/2202.00563
  21. [21]Nika Haghtalab, Michael Jordan, and Eric Zhao. On-demand sampling: Learning optimally from multiple distributions. Advances in Neural Information Processing Systems, 35:406–419, 2022.arxiv.org/abs/2210.12529
  22. [22]Rafael Hanashiro, Abhishek Shetty, and Patrick Jaillet. Is multi-distribution learning as easy as PAC learning: Sharp rates with bounded label noise. In Steve Hanneke and Tor Lattimore, editors, The Thirty Ninth Annual Conference on Learning Theory, June 29 - July 3, 2026, San Diego, California, USA, volume 336 of Proceedings of Machine Learning Research, pages 3109–3142. PMLR, 2026. URL https://proceedings.mlr.press/v336/hanashiro26a.html.arxiv.org/abs/2602.21039
  23. [23]Mikhail Khodak, Maria-Florina F Balcan, and Ameet S Talwalkar. Adaptive gradient-based meta-learning methods. Advances in neural information processing systems, 32, 2019.arxiv.org/abs/1906.02717
  24. [24]Misha Khodak, Ilya Osadchiy, Keegan Harris, Maria-Florina F Balcan, Kfir Y Levy, Ron Meir, and Steven Z Wu. Meta-learning adversarial bandit algorithms. Advances in Neural Information Processing Systems, 36:35441–35471, 2023.arxiv.org/abs/2307.02295
  25. [25]Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold. Universal adaptability: Target-independent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences, 119(4):e2108097119, 2022.DOI
  26. [26]Weihao Kong, Raghav Somani, Zhao Song, Sham Kakade, and Sewoong Oh. Meta-learning for mixed linear regression. In International Conference on Machine Learning, pages 5394–5404. PMLR, 2020.arxiv.org/abs/2002.08936
  27. [27]Kasper Green Larsen, Omar Montasser, and Nikita Zhivotovskiy. Derandomizing multi-distribution learning. Advances in Neural Information Processing Systems, 37:94246–94264, 2024.arxiv.org/abs/2409.17567
  28. [28]Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. doi: 10.1017/9781108571401.DOI
  29. [29]David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference on Machine Learning, pages 3384–3393. PMLR, 2018.arxiv.org/abs/1802.06309
  30. [30]Subha Maity, Diptavo Dutta, Jonathan Terhorst, Yuekai Sun, and Moulinath Banerjee. A linear adjustment-based approach to posterior drift in transfer learning. Biometrika, 111(1):31–50, 2024.DOI
  31. [31]Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1–32, 2016.arxiv.org/abs/1505.06279
  32. [32]Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International conference on machine learning, pages 4615–4625. PMLR, 2019.arxiv.org/abs/1902.00146
  33. [33]Omar Montasser, Han Shao, and Emmanuel Abbe. Transformation-invariant learning and theoretical guarantees for ood generalization. Advances in Neural Information Processing Systems, 37:108649–108673, 2024.arxiv.org/abs/2410.23461
  34. [34]Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International conference on machine learning, pages 10–18. PMLR, 2013.arxiv.org/abs/1301.2115
  35. [35]Huy Nguyen and Lydia Zakynthinou. Improved algorithms for collaborative pac learning. Advances in Neural Information Processing Systems, 31, 2018.arxiv.org/abs/1805.08356
  36. [36]Prasad Patil and Giovanni Parmigiani. Training replicable predictors in multiple studies. Proceedings of the National Academy of Sciences, 115(11):2578–2583, 2018.DOI
  37. [37]Binghui Peng. The sample complexity of multi-distribution learning. In The Thirty Seventh Annual Conference on Learning Theory, pages 4185–4204. PMLR, 2024. Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id= BbNIbVPJ-42.DOI
  38. [38]Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=ryxGuJrFvS.arxiv.org/abs/1911.08731
  39. [39]Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal learning. arXiv preprint arXiv:1206.6471, 2012.
  40. [40]Han Shao, Omar Montasser, and Avrim Blum. A theory of pac learnability under transformation invariances. Advances in Neural Information Processing Systems, 35:13989–14001, 2022.arxiv.org/abs/2202.07552
  41. [41]Piotr Teterwak, Kuniaki Saito, Theodoros Tsiligkaridis, Kate Saenko, and Bryan Plummer. Erm++: An improved baseline for domain generalization. In Proceedings of the Winter Conference on Applications of Computer Vision, pages 8514–8524, 2025.arxiv.org/abs/2304.01973
  42. [42]Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Sample efficient linear meta-learning by alternating minimization. arXiv preprint arXiv:2105.08306, 2021.arxiv.org/abs/2105.08306
  43. [43]Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Advances in neural information processing systems, 33:7852–7862, 2020.arxiv.org/abs/2006.11650
  44. [44]Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. In International conference on machine learning, pages 10434–10443. Pmlr, 2021.arxiv.org/abs/2002.11684
  45. [45]V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16(2):264–280, 1971. doi: 10.1137/1116025.DOI
  46. [46]Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Tao Qin, Wang Lu, Yiqiang Chen, Wenjun Zeng, and Philip S Yu. Generalizing to unseen domains: A survey on domain generalization. IEEE transactions on knowledge and data engineering, 35(8):8052–8072, 2022.
  47. [47]Xiaohan Wang and Yang Ning. Transfer learning for classification under decision rule drift with application to optimal individualized treatment rule estimation. arXiv preprint arXiv:2508.20942, 2025.arxiv.org/abs/2508.20942
  48. [48]Kun Zhang, Mingming Gong, and Bernhard Schölkopf. Multi-source domain adaptation: A causal view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.DOI
  49. [49]Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S. Du, and Jason D. Lee. Optimal multi-distribution learning. J. ACM, 72(5):36:1–36:71, 2025. doi: 10.1145/3760256. URL https://doi.org/10.1145/3760256.
  50. [50]Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization: A survey. IEEE transactions on pattern analysis and machine intelligence, 45(4):4396–4415, 2022.DOI

Paper details

vlnc:W_9296a57h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, Codex

View statement
Looking for related papers…
Contents