  Domain generalization asks for models trained over a set of training
environments to perform well in unseen test environments. Recently, a series of
algorithms such as Invariant Risk Minimization (IRM) has been proposed for
domain generalization. However, Rosenfeld et al. (2021) shows that in a simple
linear data model, even if non-convexity issues are ignored, IRM and its
extensions cannot generalize to unseen environments with less than $d_s+1$
training environments, where $d_s$ is the dimension of the spurious-feature
subspace. In this paper, we propose to achieve domain generalization with
Invariant-feature Subspace Recovery (ISR). Our first algorithm, ISR-Mean, can
identify the subspace spanned by invariant features from the first-order
moments of the class-conditional distributions, and achieve provable domain
generalization with $d_s+1$ training environments under the data model of
Rosenfeld et al. (2021). Our second algorithm, ISR-Cov, further reduces the
required number of training environments to $O(1)$ using the information of
second-order moments. Notably, unlike IRM, our algorithms bypass non-convexity
issues and enjoy global convergence guarantees. Empirically, our ISRs can
obtain superior performance compared with IRM on synthetic benchmarks. In
addition, on three real-world image and text datasets, we show that both ISRs
can be used as simple yet effective post-processing methods to improve the
worst-case accuracy of (pre-)trained models against spurious correlations and
group shifts.
