  One method for obtaining generalizable solutions to machine learning tasks
when presented with diverse training environments is to find \textit{invariant
representations} of the data. These are representations of the covariates such
that the best model on top of the representation is invariant across training
environments. In the context of linear Structural Equation Models (SEMs),
invariant representations might allow us to learn models with
out-of-distribution guarantees, i.e., models that are robust to interventions
in the SEM. To address the invariant representation problem in a {\em finite
sample} setting, we consider the notion of $\epsilon$-approximate invariance.
We study the following question: If a representation is approximately invariant
with respect to a given number of training interventions, will it continue to
be approximately invariant on a larger collection of unseen SEMs? This larger
collection of SEMs is generated through a parameterized family of
interventions. Inspired by PAC learning, we obtain finite-sample
out-of-distribution generalization guarantees for approximate invariance that
holds \textit{probabilistically} over a family of linear SEMs without
faithfulness assumptions. Our results show bounds that do not scale in ambient
dimension when intervention sites are restricted to lie in a constant size
subset of in-degree bounded nodes. We also show how to extend our results to a
linear indirect observation model that incorporates latent variables.
