Towards a Theoretical Framework of Out-of-Distribution Generalization

Haotian Ye, Chuanlong Xie, Tianle Cai, Ruichen Li, Zhenguo Li, Liwei Wang

Abstract

Generalization to out-of-distribution (OOD) data is a central challenge in modern machine learning. While many algorithms aim to extract invariant features, theoretical understanding of which invariances guarantee generalization remains limited. This work introduces rigorous definitions for OOD learnability and a new "expansion function" that quantifies how feature variance amplifies from training to test domains. Based on this framework, we derive OOD generalization error bounds and a novel model selection criterion. Extensive experiments on benchmark datasets show that our criterion significantly outperforms standard validation-based approaches.

Introduction

Standard machine learning models typically rely on the i.i.d. assumption—that training and test data are drawn from the same distribution. However, real-world applications often encounter distribution shifts, such as medical models trained on data from one hospital failing when deployed at another. While "Domain Generalization" (DG) methods seek "invariant features," the field lacks a formal framework to define what makes an OOD problem learnable and how to select models without access to the target distribution.

Theoretical Framework

The authors formalize OOD generalization by relating available training domains ($E_{avail}$) to the set of all possible domains ($E_{all}$). They introduce three fundamental concepts:

  1. Variation ($V$): Quantifies how much a feature's distribution shifts across domains.
  2. Informativeness ($I$): Measures the predictive power of a feature for the target labels.
  3. Expansion Function ($s(\cdot)$): A critical "bridge" characterizing the amplification of feature variance when moving from training to unseen domains.

The theory proves that for learnable OOD problems, features that are both informative and stable (low variation) in training will likely remain stable in unseen domains. The resulting generalization error bounds show that OOD error is primarily controlled by the product of the expansion function and the observed feature variation.

Model Selection Criterion

A significant contribution of this work is a theory-driven model selection criterion. Traditional validation accuracy ($Acc_{val}$) often fails in OOD settings because it may favor models that exploit domain-specific "spurious" correlations. The proposed criterion selects the model $f$ that maximizes: $$Acc_f - r_0 V_f$$ where $V_f$ represents the average variation of the model's features and $r_0$ is a regularization hyperparameter. This approach explicitly penalizes models whose features fluctuate significantly across training environments, favoring those with more robust, invariant representations.

Experimental Results

The framework was evaluated on standard OOD benchmarks, including PACS, OfficeHome, and VLCS. The results demonstrate that the proposed criterion consistently identifies models with superior OOD performance compared to standard validation accuracy.

Table 1: Performance comparison of the proposed model selection criterion against standard validation accuracy across PACS, OfficeHome, and VLCS datasets.

On the Colored MNIST dataset—a benchmark where standard validation accuracy is often negatively correlated with OOD performance—the variation-based metric correctly identified robust models by maintaining a positive correlation with true OOD accuracy.

Discussion and Conclusion

This work moves OOD generalization from heuristic-driven approaches toward a rigorous mathematical foundation. By quantifying the "difficulty" of an OOD task through the expansion function, it provides a clear signal for model selection. While the exact form of the expansion function for complex real-world data remains an open question, the empirical success of the $Acc - r_0 V$ criterion suggests that feature stability is a powerful proxy for OOD robustness. Future work will focus on integrating these population-level bounds with finite-sample generalization theory and optimizing the computational cost of feature variation estimation.

Summary updated

Abstract

Generalization to out-of-distribution (OOD) data is one of the central problems in modern machine learning. Recently, there is a surge of attempts to propose algorithms that mainly build upon the idea of extracting invariant features. Although intuitively reasonable, theoretical understanding of what kind of invariance can guarantee OOD generalization is still limited, and generalization to arbitrary out-of-distribution is clearly impossible. In this work, we take the first step towards rigorous and quantitative definitions of 1) what is OOD; and 2) what does it mean by saying an OOD problem is learnable. We also introduce a new concept of expansion function, which characterizes to what extent the variance is amplified in the test domains over the training domains, and therefore give a quantitative meaning of invariant features. Based on these, we prove OOD generalization error bounds. It turns out that OOD generalization largely depends on the expansion function. As recently pointed out by Gulrajani and Lopez-Paz (2020), any OOD learning algorithm without a model selection module is incomplete. Our theory naturally induces a model selection criterion. Extensive experiments on benchmark OOD datasets demonstrate that our model selection criterion has a significant advantage over baselines.
BibTeX
@inproceedings{ye2021towards,
  author = {Haotian Ye and Chuanlong Xie and Tianle Cai and Ruichen Li and Zhenguo Li and Liwei Wang},
  title = {{Towards a Theoretical Framework of Out-of-Distribution Generalization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=0WASBV4xkhy},
}
Figure