Towards a Theoretical Framework of Out-of-Distribution Generalization

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

TL;DR

While many out-of-distribution (OOD) algorithms claim to learn "invariant features," theoretical understanding of when and why invariance guarantees generalization to unseen domains has remained murky. This paper introduces a rigorous theoretical framework centered on an expansion function that quantifies how feature variance is amplified from training domains to unseen test domains. Leveraging this theory, the authors propose an OOD model selection criterion balancing validation accuracy and feature variation, consistently outperforming standard validation accuracy across benchmark datasets.

What Problem Does This Paper Address?

Standard machine learning assumes independent and identically distributed (i.i.d.) training and test data. In the real world, test data distributions routinely shift away from training environments. While the field of domain generalization has exploded with heuristic algorithms aimed at extracting domain-invariant representations, two core issues persist:

  1. Theoretical ambiguity: Arbitrary OOD generalization is fundamentally impossible without assumptions. What formal relationship between available training domains ($\mathcal{E}_{\text{avail}}$) and all unseen domains ($\mathcal{E}_{\text{all}}$) makes a task learnable?
  2. Broken model selection: In benchmark studies (like Gulrajani & Lopez-Paz, 2020), OOD algorithms rarely beat standard Empirical Risk Minimization (ERM) because hyperparameter tuning and model selection rely on validation accuracy on $\mathcal{E}_{\text{avail}}$, which is heavily biased toward spurious, domain-specific features.

Methods

The authors formalize the OOD learning problem using three building blocks:

  • Variation ($V_\rho$): Measures the maximum pairwise divergence (e.g., total variation or KL-divergence) of a feature’s class-conditional distribution across a domain set.
  • Informativeness ($I_\rho$): Quantifies whether a feature helps distinguish class labels, ensuring non-informative noise is filtered out.
  • Expansion Function ($s(\cdot)$) and Learnability: An OOD task is $(s(\cdot), \delta)$-learnable if, for any feature meeting an informativeness threshold $\delta$, its variation across unseen domains is bounded by a monotonic function of its training variation: $V_\rho(\phi, \mathcal{E}_{\text{all}}) \le s(V_\rho(\phi, \mathcal{E}_{\text{avail}}))$ with $s(0) = 0$.

Generalization Error Bounds

Using Fourier analysis and Radon transforms on feature densities, the authors prove bidirectional generalization bounds on the domain error gap $\text{err}(f) = L(\mathcal{E}_{\text{all}}, f) - L(\mathcal{E}_{\text{avail}}, f)$:

  • Upper Bound: For general classifiers, $\text{err}(f) \le \mathcal{O}\left(s\left(V^{\sup}_\rho(h, \mathcal{E}_{\text{avail}})\right)^{\frac{\alpha^2}{(\alpha+d)^2}}\right)$, which tightens to linear $\mathcal{O}(s(V^{\sup}))$ when the final classification head is linear.
  • Lower Bound: For optimal classifiers under 0-1 loss, $\text{err}(f) \ge C_0 \cdot s(V^{\sup}_\rho(h, \mathcal{E}_{\text{avail}}))$.

Variation-Aware Model Selection

Motivated by the upper bound, the authors propose a practical model selection criterion: $$\text{Score}(f) = \text{Acc}_f - r_0 V_f$$ where $\text{Acc}_f$ is the validation accuracy on training domains, $V_f$ is the average feature variation computed via a fast, parallel GPU-based kernel density estimation (KDE), and $r_0$ balances the two metrics using the ratio of standard deviations among high-performing candidate models.

Datasets

The authors evaluate their method across standard computer vision domain generalization benchmarks within the DomainBed framework:

  • PACS (4 domains: Photo, Art, Cartoon, Sketch)
  • OfficeHome (4 domains: Art, Clipart, Product, Real-World)
  • VLCS (4 domains: VOC2007, LabelMe, Caltech101, SUN09)
  • (Illustrative) Colored MNIST is analyzed analytically as an example of an unlearnable task without structural assumptions.

No new datasets were introduced.

Key Insights and Ideas

  • Invariance alone is meaningless without informativeness: Completely useless features (such as image noise or constant backgrounds) can appear invariant in training domains yet diverge wildly on test sets. Bounding generalization requires restricting attention to informative features ($\delta > 0$).
  • The expansion function captures task difficulty: If $s(x)$ grows steeply, even small distribution variations in training explode in unseen domains. If $s(x) = x$, the task collapses to the classical i.i.d. setting.
  • The $\delta$ vs. $s(\cdot)$ trade-off: Raising the informativeness cutoff $\delta$ filters out spurious features, resulting in a flatter (better) expansion function $s(\cdot)$. However, demanding higher informativeness forces models to pick up domain-specific cues, increasing training variation $\varepsilon$. Optimal generalization requires balancing this tension.
  • Model selection needs an invariance regularizer: Relying purely on validation accuracy inevitably selects models that overfit the training domains. Penalizing candidate models by feature variation aligns selection with true worst-domain performance.

Key Results

  • Validation of the Expansion Function: Plotting variation for roughly 2 million features extracted from ResNet-50 models on Office-Home confirmed that when $\delta = 0$, no valid expansion function exists; once $\delta \ge 0.15$, clean, well-behaved expansion functions emerge.
  • Model Selection Performance: Over 200 trained models per environment across multiple algorithms (ERM, CORAL, Mixup, Group DRO, IRM):
  • PACS: Average OOD accuracy rose from 84.91% (validation selection) to 86.57% (+1.66%).
  • OfficeHome: Average OOD accuracy rose from 67.09% to 68.09% (+1.00%).
  • VLCS: Average OOD accuracy rose from 75.69% to 76.32% (+0.63%).

Limitations and Future Work

  • Population vs. Sample Error: The theoretical bounds apply to population distributions; a unified framework bridging these bounds with finite-sample uniform convergence remains an open problem.
  • Practical Approximations: The theory requires evaluating variation over all 1D linear projections ($V^{\sup}$), but the practical algorithm relies on the average coordinate-wise variation to maintain computational feasibility.
  • Unknown Expansion Functions: Because $s(\cdot)$ depends on unseen target domains, the exact penalty weight $r_0$ cannot be computed analytically and must be estimated empirically from candidate model statistics.

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 an OOD generalization error bound. It turns out that OOD generalization largely depends on the expansion function. As recently pointed out by Gulrajani & 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},
}

Loading related content...

Figure