Empirical or Invariant Risk Minimization? A Sample Complexity Perspective

Abstract

Recently, invariant risk minimization (IRM) was proposed as a promising solution to address out-of-distribution (OOD) generalization. However, it is unclear when IRM should be preferred over the widely-employed empirical risk minimization (ERM) framework. In this work, we analyze both these frameworks from the perspective of sample complexity, thus taking a firm step towards answering this important question. We find that depending on the type of data generation mechanism, the two approaches might have very different finite sample and asymptotic behavior. For example, in the covariate shift setting we see that the two approaches not only arrive at the same asymptotic solution, but also have similar finite sample behavior with no clear winner. For other distribution shifts such as those involving confounders or anti-causal variables, however, the two approaches arrive at different asymptotic solutions where IRM is guaranteed to be close to the desired OOD solutions in the finite sample regime, while ERM is biased even asymptotically. We further investigate how different factors -- the number of environments, complexity of the model, and IRM penalty weight -- impact the sample complexity of IRM in relation to its distance from the OOD solutions

References in corpus (8)

• Domain Generalization via Invariant Feature Representation
• Domain-Adversarial Neural Networks
• On Learning Invariant Representation for Domain Adaptation
• In Search of Lost Domain Generalization
• Efficient Domain Generalization via Common-Specific Low-Rank Decomposition
• When is invariance useful in an Out-of-Distribution Generalization problem ?
• Representation via Representations: Domain Generalization via Adversarially Learned Invariant Representations
• PAC Learning Guarantees Under Covariate Shift

Cited by in corpus (7)

• Towards Out-Of-Distribution Generalization: A Survey
• Towards a Theoretical Framework of Out-of-Distribution Generalization
• Nonlinear Invariant Risk Minimization: A Causal Approach
• Out-of-distribution Prediction with Invariant Risk Minimization: The Limitation and An Effective Fix
• Model-Based Domain Generalization
• Meta-Learned Invariant Risk Minimization
• An Empirical Framework for Domain Generalization in Clinical Settings