# Learn to Expect the Unexpected: Probably Approximately Correct Domain Generalization

arXiv: https://arxiv.org/abs/2002.05660 · HTML: https://mlsanity.com/paper/2002.05660/

## Key facts

- Cited by 14 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 13 Feb 2020.

## Built on by (most cited first, 14 of 14)

- [Generalizing to Unseen Domains: A Survey on Domain Generalization](https://mlsanity.com/paper/2103.03097/) (2021)
- [Towards Out-Of-Distribution Generalization: A Survey](https://mlsanity.com/paper/2108.13624/) (2021)
- [Invariance Principle Meets Information Bottleneck for Out-of-Distribution Generalization](https://mlsanity.com/paper/2106.06607/) (2021)
- [Probable Domain Generalization via Quantile Risk Minimization](https://mlsanity.com/paper/2207.09944/) (2022)
- [Semantic-Discriminative Mixup for Generalizable Sensor-based Cross-domain Activity Recognition](https://mlsanity.com/paper/2206.06629/) (2022)
- [GLOBEM Dataset: Multi-Year Datasets for Longitudinal Human Behavior Modeling Generalization](https://mlsanity.com/paper/2211.02733/) (2022)
- [Predicting Out-of-Domain Generalization with Neighborhood Invariance](https://mlsanity.com/paper/2207.02093/) (2022)
- [Exploiting Personalized Invariance for Better Out-of-distribution Generalization in Federated Learning](https://mlsanity.com/paper/2211.11243/) (2022)
- [MLDGG: Meta-Learning for Domain Generalization on Graphs](https://mlsanity.com/paper/2411.12913/) (2024)
- [Graphs Generalization under Distribution Shifts](https://mlsanity.com/paper/2403.16334/) (2024)
- [How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension](https://mlsanity.com/paper/2506.16704/) (2025)
- [Domain Generalization Deep Graph Transformation](https://mlsanity.com/paper/2305.11389/) (2023)
- [LangDAug: Langevin Data Augmentation for Multi-Source Domain Generalization in Medical Image Segmentation](https://mlsanity.com/paper/2505.19659/) (2025)
- [Prompting-based Temporal Domain Generalization](https://mlsanity.com/paper/2310.02473/) (2023)

## Abstract (arXiv)

Domain generalization is the problem of machine learning when the training data and the test data come from different data domains. We present a simple theoretical model of learning to generalize across domains in which there is a meta-distribution over data distributions, and those data distributions may even have different supports. In our model, the training data given to a learning algorithm consists of multiple datasets each from a single domain drawn in turn from the meta-distribution. We study this model in three different problem settings---a multi-domain Massart noise setting, a decision tree multi-dataset setting, and a feature selection setting, and find that computationally efficient, polynomial-sample domain generalization is possible in each. Experiments demonstrate that our feature selection algorithm indeed ignores spurious correlations and improves generalization.