PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards a Theoretical Framework of Out-of-Distribution Generalization

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

arXiv:2106.04496v3cs.LG

TL;DR

OOD generalization lacks a rigorous account of which invariances transfer to unseen domains, while arbitrary OOD generalization is impossible. The paper formalizes learnability through feature distributions and expansion functions, derives error bounds, and uses them to design model selection; experiments report an advantage over traditional selection methods.

  • Problem

    Existing OOD methods often seek invariant features, but theory remains limited on which invariance guarantees generalization, and arbitrary OOD generalization is impossible.

  • Method

    The paper quantitatively relates feature distributions across Eavail and Eall using expansion functions, derives OOD error bounds, and proposes variation-aware model selection.

  • Results

    The bounds show that OOD difficulty depends on the expansion function and feature variation, while experiments show the proposed criterion selects models with higher OOD accuracy than baselines.

  • Takeaways & Limitations

    Expansion functions provide a quantitative basis for assessing OOD difficulty and selecting models using both validation performance and feature variation.

  • Takeaways & Limitations

    The paper calls for future work combining its generalization bound with traditional bounds, and notes a trade-off between variation and informativeness in model selection.

Abstract

from arXiv · show

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.

1 Introduction

The paper formalizes when OOD generalization is learnable by relating invariant features across available and all domains. It derives bounds governed by feature variation and proposes a variation-aware model-selection criterion that improves OOD accuracy over baselines.

  • 1 Introduction: The paper formalizes OOD generalization by characterizing how feature invariance transfers from available domains Eavail to the larger domain set Eall.This addresses limited theory for invariant features and the impossibility of generalizing to arbitrary OOD domains.
  • 1 Introduction: Expansion functions quantify how feature variance changes between Eavail and Eall and determine the difficulty of an OOD generalization problem.The framework uses this quantity to connect training-domain invariance with test-domain behavior.
  • 1 Introduction: OOD generalization bounds depend on the expansion function and learned-feature variation, with faster expansion producing harder problems and worse guarantees.The bounds include both upper and lower bounds for the OOD error gap.
  • 1 Introduction: The proposed model-selection criterion combines validation accuracy with low feature variation instead of relying on validation accuracy alone.The criterion is motivated by the bounds and is intended to reduce selection of models that overfit available domains.
  • 1 Introduction: Experiments show that the proposed criterion outperforms baselines and selects models with higher OOD accuracy.The introduction identifies this as an empirical advantage over traditional selection methods.

2 Preliminary

The paper formulates OOD generalization over available and target domains for multi-class classification, using feature extractors and top classifiers under a balanced-domain assumption.

  • OOD learning seeks a classifier that minimizes worst-domain loss over the target domain set Eall, using only available domains Eavail during training.
  • The classifier is decomposed as g ◦ h, where h maps inputs to d-dimensional features and g maps those features to K-class outputs.
  • The framework represents each scalar feature as a map from X to R and distinguishes the vector representation h(Xe) from individual features φ(Xe).
  • Data distributions are assumed balanced across labels and domains, while removing this assumption adds an imbalance term to the generalization bounds.

3 Framework of OOD Generalization Problem

The framework quantifies OOD generalization through feature variation, informativeness, and an expansion function linking available and target domains. Learnability requires informative available-domain features to retain controlled variation in the target domains.

  • The framework addresses how available domains Eavail relate to target domains Eall, using an expansion function to bridge feature-distribution quantities across them.
  • Variation measures feature stability across domains, while informativeness measures the feature’s ability to distinguish labels.
  • The framework defines learnability when an expansion function s and threshold δ ensure s(Vρ(φ, Eavail)) ≥ Vρ(φ, Eall) for every feature with Iρ(φ, Eavail) ≥ δ.
  • The expansion-function scale reflects OOD difficulty: larger target domain sets induce larger functions and are harder to generalize to.
  • Informativeness is necessary because invariant but non-informative features may capture noise that varies substantially in unseen domains.
  • The framework identifies both learnable and unlearnable extremes: identical domains use s(x)=x, whereas reversed color-label relationships can make OOD generalization unlearnable.

4 Generalization Bound

The paper bounds OOD generalization error using learned-feature variation and the expansion function, establishing both upper and lower controls on the domain gap. The bounds show that smaller variation and slower expansion yield stronger guarantees, with improved rates for linear top models.

  • Generalization bounds: Theorems provide upper and lower bounds on OOD generalization error in terms of expansion and learned-feature variation.Together, the bounds give bidirectional control of the gap between Eavail and Eall.
  • Generalization bounds: The main bound applies to general classifiers and makes the gap depend on variation of the learned representation over Eavail.Under the stated regularity conditions, the gap converges to zero as variation approaches zero.
  • Linear top model: With a linear top model, the paper obtains a linear convergence rate under mild integrability assumptions instead of the stronger concentration conditions.The rate matches the convergence rate of the expansion function.
  • Role of expansion: For fixed feature variation, a larger expansion function produces a larger OOD gap and harder generalization.The expansion function therefore captures how difficulty increases from available to all domains.
  • Proof strategy: The analysis uses distributional distances, Fourier transforms, and Radon transforms to connect OOD error with variation of linear combinations of learned features.Supremum variation over normalized linear combinations is used to control joint feature-distribution distance.
  • Lower bound: The lower bound shows that even an Eavail-optimal classifier cannot avoid OOD error when its learned representation has nonzero variation.Here optimal means minimizing loss on Eavail.

5 Variation as a Factor of Model Selection Criterion

The paper turns its generalization bounds into a model-selection criterion that combines validation accuracy with feature variation. This addresses the bias of accuracy-only selection toward models that overfit available domains.

  • Motivation: Validation accuracy alone can select models that fit available domains while relying on spurious features that fail on Eall.The paper uses Colored MNIST to illustrate why accuracy-only selection can favor ERM over OOD algorithms.
  • Selection criterion: The proposed criterion selects models with high validation accuracy and low feature variation simultaneously.Variation is estimated from feature-wise variation over the available data.
  • Procedure: The selection procedure computes candidate-model variation and validation accuracy, then combines them through a criterion motivated by the OOD error bound.The hyperparameter r0 represents the relationship between variation and accuracy.
  • Procedure: The method uses average feature variation in practice, although the theoretical bounds use supremum variation for worst-case top models.The paper reports that the average is sufficient to improve selection empirically.
  • Empirical implication: Experiments reported in the selection section show that the criterion can select models with higher OOD accuracy across varied OOD datasets.The paper states that the improvement holds across multiple datasets.

6 Experiments

Experiments evaluate the proposed selection rule on benchmark OOD datasets and examine the expansion function on Office-Home. The selection rule outperforms validation-accuracy selection in average OOD accuracy across all reported datasets and setups.

  • 6.1 Experiments on Model Selection: The benchmark study uses PACS, OfficeHome, and VLCS with ResNet-50 and models trained across ERM and four OOD algorithms.Each environment setup includes models trained with different penalties, learning rates, and epochs.
  • 6.1 Experiments on Model Selection: Across all evaluated datasets, the proposed selection criterion significantly outperforms validation-accuracy selection in average OOD accuracy.The comparison is summarized in Table 1 across the reported environment setups.
  • 6.1 Experiments on Model Selection: The method improves OOD accuracy in most of the 12 environment setups.The experiments compare models selected by Algorithm 1 with models selected by validation accuracy.
  • 6.2 Learnability of Real-World OOD Problem: On Office-Home, the expansion-function analysis plots approximately 2 million learned features using V(φ, Eavail) on the x-axis and V(φ, Eall) on the y-axis.Feature colors represent informativeness, and the red curve represents the expansion function for a given δ.
  • 6.2 Learnability of Real-World OOD Problem: When δ=0, non-informative features can be nearly invariant on Eavail while varying on Eall, so no expansion function makes the task learnable.Increasing δ removes these non-informative features and permits an appropriate expansion function.
  • 6.2 Learnability of Real-World OOD Problem: The expansion function and δ trade off: flatter expansion gives tighter bounds but requires higher informativeness, which can increase representation variation.The paper connects this trade-off to the practical balance between informativeness and variation in model selection.

7 More Related Works

Related work approaches OOD generalization through invariant features, distributional restrictions, causal assumptions, and hyper-distribution models. These approaches differ in how they constrain unseen domains and analyze generalization.

  • OOD generalization: Domain generalization seeks models trained on several domains that perform well on unseen test domains.The literature also describes this setting as OOD generalization.
  • Invariant features: Many methods learn domain-invariant representations, including distributional matching and invariant prediction approaches.Related work also connects invariance to causal discovery, distributional robustness, and conditional independence.
  • Distributional restrictions: Some approaches define test domains near training domains using distribution-distance measures.This route restricts how target distributions may differ from the training distributions.
  • Causal framework: Causal approaches analyze robustness to test distributions generated by interventions on variables.Their principle is that a causal model is invariant and can achieve minimal worst-case risk.
  • Alternative analyses: Other analyses assume domains are generated from a hyper-distribution and bound average risk-estimation error.Related domain-adaptation work also considers settings where test domains are visible but unlabeled.

8 Conclusion

The paper formalizes OOD generalization, proves bounds, and uses them to design a model-selection criterion based on variation and validation accuracy.

  • The paper proposes a rigorous mathematical formulation of OOD generalization and proves corresponding generalization-error guarantees.
  • The proposed model-selection criterion evaluates models using variation together with validation accuracy.
  • Experiments show that the proposed metric has a significant advantage over traditional model-selection methods.

9 Appendix: Illustration of Model’s Variation

The appendix shows why controlling each feature’s marginal variation is insufficient: feature vectors can vary substantially even when individual features appear invariant.

  • The construction considers binary classification with a two-dimensional feature extractor and compares domain-conditional feature distributions.
  • The failure case has identical marginal distributions for both features across domains, while their joint feature distributions differ substantially.
  • A classifier’s variation is defined more strongly than the supremum of individual feature variations because marginal control alone cannot bound total variation or classification error.

10 Appendix: Proofs

The proofs establish OOD error bounds and show that expansion functions characterize both learnability and lower-bound behavior for optimal classifiers.

  • The proofs derive bounds for classifiers under bounded loss, feature regularity assumptions, and linear top models.
  • The proof decomposes the loss gap across domains and controls its terms using projected-feature distributions and Fourier or Radon-transform arguments.
  • Theorem 4.3 lower bounds the OOD error of an optimal classifier by the variation of its learned features.
  • For linear expansion functions, the appendix constructs learnable OOD problems whose optimal classifiers have variation-dependent generalization error.

11 Appendix: Experiment on Colored MNIST

Colored MNIST illustrates that validation accuracy can select models with poor OOD accuracy, whereas lower feature variation is associated with higher OOD accuracy.

  • Colored MNIST uses invariant digit shape and domain-varying color, which can be more informative than shape in some domains.
  • The appendix proves that Colored MNIST is an (s(·), δ)-learnable OOD problem under the proposed framework.
  • High validation accuracy is negatively correlated with OOD accuracy on Colored MNIST, making validation accuracy alone a poor selection metric.
  • Low variation is negatively correlated with higher OOD accuracy, supporting variation as a model-selection signal.

12 Appendix: Experiment Details

The experiments evaluate several OOD algorithms on three real-world datasets using ResNet50, repeated training settings, and per-environment validation and test splits.

  • Each environment is split into 20% validation and 80% training/OOD-test data, enabling comparison of the proposed criterion with environment-level validation.
  • Data augmentation follows the GLP20 setting, combining random resized crops, horizontal flips, color jitter, 10% grayscale conversion, and ImageNet normalization.
  • The study searches ERM, Inter-domain Mixup, Group DRO, CORAL, and IRM across algorithm-specific hyperparameters, training each setting five times.
Loading 2106.04496v3…