Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments

Abstract

Domain generalization aims at performing well on unseen test environments with data from a limited number of training environments. Despite a proliferation of proposal algorithms for this task, assessing their performance both theoretically and empirically is still very challenging. Distributional matching algorithms such as (Conditional) Domain Adversarial Networks [Ganin et al., 2016, Long et al., 2018] are popular and enjoy empirical success, but they lack formal guarantees. Other approaches such as Invariant Risk Minimization (IRM) require a prohibitively large number of training environments -- linear in the dimension of the spurious feature space $d_s$ -- even on simple data models like the one proposed by [Rosenfeld et al., 2021]. Under a variant of this model, we show that both ERM and IRM cannot generalize with $o(d_s)$ environments. We then present an iterative feature matching algorithm that is guaranteed with high probability to yield a predictor that generalizes after seeing only $O(\log d_s)$ environments. Our results provide the first theoretical justification for a family of distribution-matching algorithms widely used in practice under a concrete nontrivial data model.

We acknowledge that the previous version of this paper (v1) contained an error - Theorem 3.2 was incorrect. We removed this theorem and updated the rest of the paper in v2

References in corpus (8)

• Learning Transferable Features with Deep Adaptation Networks
• Domain Generalization via Invariant Feature Representation
• Out-of-Distribution Generalization via Risk Extrapolation (REx)
• The Risks of Invariant Risk Minimization
• Domain Generalization using Causal Matching
• Does Invariant Risk Minimization Capture Invariance?
• Linear unit-tests for invariance discovery
• An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization