How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension
Not on the map. Why?
Abstract (arXiv)
We study a fundamental question of domain generalization: given a family of domains (i.e., data distributions), how many randomly sampled domains do we need to collect data from in order to learn a model that performs reasonably well on every seen and unseen domain in the family? We model this problem in the PAC framework and introduce a new combinatorial measure, which we call the domain shattering dimension. We show that this dimension characterizes the domain sample complexity. Furthermore, we establish a tight quantitative relationship between the domain shattering dimension and the classic VC dimension, demonstrating that every hypothesis class that is learnable in the standard PAC setting is also learnable in our setting.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 33 of its 50 references that are in the map. First posted on arXiv 20 Jun 2025.
Builds on
33 of 50 references.
References · 33
- 2019Invariant Risk Minimizationcited by 1,854
- 2021Generalizing to Unseen Domains: A Survey on Domain Generalizationcited by 766
- 2021Domain Generalization: A Surveycited by 764
- 2013Domain Generalization via Invariant Feature Representationcited by 623
- 2021Exploiting Shared Representations for Personalized Federated Learningcited by 541
- 2019Agnostic Federated Learningcited by 456
- 2018Learning Adversarially Fair and Transferable Representationscited by 353
- 2020Few-Shot Learning via Learning the Representation, Provablycited by 214
- 2015The Benefit of Multitask Representation Learningcited by 195
- 2020On the Theory of Transfer Learning: The Importance of Task Diversitycited by 186
- 2019Adaptive Gradient-Based Meta-Learning Methodscited by 183
- 2020Provable Meta-Learning of Linear Representationscited by 161
21 more
- 2021A Theory of PAC Learnability of Partial Concept Classescited by 60
- 2020Meta-learning for mixed linear regressioncited by 44
- 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
- 2020Representation via Representations: Domain Generalization via Adversarially Learned Invariant Representationscited by 26
- 2021Sample Efficient Linear Meta-Learning by Alternating Minimizationcited by 25
- 2014Efficient Representations for Life-Long Learning and Autoencodingcited by 23
- 2022A Theory of PAC Learnability under Transformation Invariancescited by 21
- 2018Improved Algorithms for Collaborative PAC Learningcited by 20
- 2018Tight Bounds for Collaborative PAC Learning via Multiplicative Weightscited by 15
- 2021Learning-to-learn non-convex piecewise-Lipschitz functionscited by 15
- 2020Learn to Expect the Unexpected: Probably Approximately Correct Domain Generalizationcited by 14
- 2022Subspace Recovery from Heterogeneous Data with Non-isotropic Noisecited by 14
- 2023Optimal Multi-Distribution Learningcited by 13
- 2023The sample complexity of multi-distribution learningcited by 12
- 2023Metalearning with Very Few Samples Per Taskcited by 11
- 2022Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classescited by 8
- 2023Meta-Learning Adversarial Bandit Algorithmscited by 8
- 2022Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishabilitycited by 7
- 2024Derandomizing Multi-Distribution Learningcited by 5
- 2024Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalizationcited by 4
- 2024On the ERM Principle in Meta-Learningcited by 1
Built on by
Citing papers per year: 2025: 1; 2026: 2.
3 papers.