Towards a Theoretical Framework of Out-of-Distribution Generalization

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.

References in corpus (19)

• Domain Generalization via Invariant Feature Representation
• Invariant Risk Minimization
• WILDS: A Benchmark of in-the-Wild Distribution Shifts
• Out-of-Distribution Generalization via Risk Extrapolation (REx)
• Distributionally Robust Logistic Regression
• Invariant Models for Causal Transfer Learning
• Improve Unsupervised Domain Adaptation with Mixup Training
• The Risks of Invariant Risk Minimization
• In Search of Lost Domain Generalization
• Domain Adaptation by Using Causal Inference to Predict Invariant Conditional Distributions
• Learning explanations that are hard to vary
• Understanding the Failure Modes of Out-of-Distribution Generalization
• Invariant Risk Minimization Games
• Does Invariant Risk Minimization Capture Invariance?
• A Generalization Error Bound for Multi-class Domain Generalization
• Empirical or Invariant Risk Minimization? A Sample Complexity Perspective
• Out-of-Distribution Generalization Analysis via Influence Function
• Enforcing Predictive Invariance across Structured Biomedical Domains
• Risk Variance Penalization

Cited by in corpus (11)

• Towards Out-Of-Distribution Generalization: A Survey
• Out-of-distribution generalization for learning quantum dynamics
• Learning Causal Semantic Representation for Out-of-Distribution Prediction
• Robust Domain Misinformation Detection via Multi-modal Feature Alignment
• Towards out of distribution generalization for problems in mechanics
• Causality and Independence Enhancement for Biased Node Classification
• A Theory of Label Propagation for Subpopulation Shift
• Quantifying and Improving Transferability in Domain Generalization
• Revisiting Deep Ensemble for Out-of-Distribution Detection: A Loss Landscape Perspective
• Counterfactual Supervision-based Information Bottleneck for Out-of-Distribution Generalization
• GenEFT: Understanding Statics and Dynamics of Model Generalization via Effective Theory