  Invariant Causal Prediction (Peters et al., 2016) is a technique for
out-of-distribution generalization which assumes that some aspects of the data
distribution vary across the training set but that the underlying causal
mechanisms remain constant. Recently, Arjovsky et al. (2019) proposed Invariant
Risk Minimization (IRM), an objective based on this idea for learning deep,
invariant features of data which are a complex function of latent variables;
many alternatives have subsequently been suggested. However, formal guarantees
for all of these works are severely lacking. In this paper, we present the
first analysis of classification under the IRM objective--as well as these
recently proposed alternatives--under a fairly natural and general model. In
the linear case, we show simple conditions under which the optimal solution
succeeds or, more often, fails to recover the optimal invariant predictor. We
furthermore present the very first results in the non-linear regime: we
demonstrate that IRM can fail catastrophically unless the test data are
sufficiently similar to the training distribution--this is precisely the issue
that it was intended to solve. Thus, in this setting we find that IRM and its
alternatives fundamentally do not improve over standard Empirical Risk
Minimization.
