# PAC Generalization via Invariant Representations

arXiv: https://arxiv.org/abs/2205.15196 · HTML: https://mlsanity.com/paper/2205.15196/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 37 references that are in the map.
- First posted on arXiv 30 May 2022.

## Builds on (most cited first, 21 of 21)

- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [In Search of Lost Domain Generalization](https://mlsanity.com/paper/2007.01434/) (2020)
- [Recognition in Terra Incognita](https://mlsanity.com/paper/1807.04975/) (2018)
- [Domain Generalization via Invariant Feature Representation](https://mlsanity.com/paper/1301.2115/) (2013)
- [Causal inference using invariant prediction: identification and confidence intervals](https://mlsanity.com/paper/1501.01332/) (2015)
- [The Risks of Invariant Risk Minimization](https://mlsanity.com/paper/2010.05761/) (2020)
- [Differentiable Causal Discovery from Interventional Data](https://mlsanity.com/paper/2007.01754/) (2020)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [Domain Adaptation by Using Causal Inference to Predict Invariant Conditional Distributions](https://mlsanity.com/paper/1707.06422/) (2017)
- [Anchor regression: heterogeneous data meets causality](https://mlsanity.com/paper/1801.06229/) (2018)
- [Does Invariant Risk Minimization Capture Invariance?](https://mlsanity.com/paper/2101.01134/) (2021)
- [Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions](https://mlsanity.com/paper/1802.06310/) (2018)
- [Permutation-Based Causal Structure Learning with Unknown Intervention Targets](https://mlsanity.com/paper/1910.09007/) (2019)
- [Empirical or Invariant Risk Minimization? A Sample Complexity Perspective](https://mlsanity.com/paper/2010.16412/) (2020)
- [Provable Domain Generalization via Invariant-Feature Subspace Recovery](https://mlsanity.com/paper/2201.12919/) (2022)
- [Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments](https://mlsanity.com/paper/2106.09913/) (2021)
- [A Theory of Multiple-Source Adaptation with Limited Target Labeled Data](https://mlsanity.com/paper/2007.09762/) (2020)
- [Finding Valid Adjustments under Non-ignorability with Minimal DAG Knowledge](https://mlsanity.com/paper/2106.11560/) (2021)
- [Treatment Effect Estimation using Invariant Risk Minimization](https://mlsanity.com/paper/2103.07788/) (2021)

## Built on by (most cited first, 1 of 1)

- [Malign Overfitting: Interpolation Can Provably Preclude Invariance](https://mlsanity.com/paper/2211.15724/) (2022)

## Abstract (arXiv)

One method for obtaining generalizable solutions to machine learning tasks when presented with diverse training environments is to find textitinvariant 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 ε-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 textitprobabilistically 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.