  Machine learning models often generalize poorly to out-of-distribution (OOD)
data as a result of relying on features that are spuriously correlated with the
label during training. Recently, the technique of Invariant Risk Minimization
(IRM) was proposed to learn predictors that only use invariant features by
conserving the feature-conditioned label expectation $\mathbb{E}_e[y|f(x)]$
across environments. However, more recent studies have demonstrated that
IRM-v1, a practical version of IRM, can fail in various settings. Here, we
identify a fundamental flaw of IRM formulation that causes the failure. We then
introduce a complementary notion of invariance, MRI, based on conserving the
label-conditioned feature expectation $\mathbb{E}_e[f(x)|y]$, which is free of
this flaw. Further, we introduce a simplified, practical version of the MRI
formulation called MRI-v1. We prove that for general linear problems, MRI-v1
guarantees invariant predictors given sufficient number of environments. We
also empirically demonstrate that MRI-v1 strongly out-performs IRM-v1 and
consistently achieves near-optimal OOD generalization in image-based nonlinear
problems.
