# Fundamental Limits and Tradeoffs in Invariant Representation Learning

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Dec 2020.

## Built on by (most cited first, 30 of 38)

- [Invariant Information Bottleneck for Domain Generalization](https://mlsanity.com/paper/2106.06333/) (2021)
- [Understanding and Constructing Latent Modality Structures in Multi-modal Representation Learning](https://mlsanity.com/paper/2303.05952/) (2023)
- [A Theory of Label Propagation for Subpopulation Shift](https://mlsanity.com/paper/2102.11203/) (2021)
- [SimMMDG: A Simple and Effective Framework for Multi-modal Domain Generalization](https://mlsanity.com/paper/2310.19795/) (2023)
- [Pareto Invariant Risk Minimization: Towards Mitigating the Optimization Dilemma in Out-of-Distribution Generalization](https://mlsanity.com/paper/2206.07766/) (2022)
- [The Impossibility of Fair LLMs](https://mlsanity.com/paper/2406.03198/) (2024)
- [Understanding and Mitigating Accuracy Disparity in Regression](https://mlsanity.com/paper/2102.12013/) (2021)
- [Causal Context Connects Counterfactual Fairness to Robust Prediction and Group Fairness](https://mlsanity.com/paper/2310.19691/) (2023)
- [On Characterizing the Trade-off in Invariant Representation Learning](https://mlsanity.com/paper/2109.03386/) (2021)
- [Rethinking Fair Representation Learning for Performance-Sensitive Tasks](https://mlsanity.com/paper/2410.04120/) (2024)
- [Text Descriptions are Compressive and Invariant Representations for Visual Learning](https://mlsanity.com/paper/2307.04317/) (2023)
- [Are demographically invariant models and representations in medical imaging fair?](https://mlsanity.com/paper/2305.01397/) (2023)
- [Fundamental Limits of Perfect Concept Erasure](https://mlsanity.com/paper/2503.20098/) (2025)
- [When Shift Happens - Confounding Is to Blame](https://mlsanity.com/paper/2505.21422/) (2025)
- [Efficient Utility-Preserving Machine Unlearning with Implicit Gradient Surgery](https://mlsanity.com/paper/2510.22124/) (2025)
- [Algorithms and Theory for Supervised Gradual Domain Adaptation](https://mlsanity.com/paper/2204.11644/) (2022)
- [Competence-Based Analysis of Language Models](https://mlsanity.com/paper/2303.00333/) (2023)
- [COD: Learning Conditional Invariant Representation for Domain Adaptation Regression](https://mlsanity.com/paper/2408.06638/) (2024)
- [Domain Generalization without Excess Empirical Risk](https://mlsanity.com/paper/2308.15856/) (2023)
- [Towards Understanding the Role of Sharpness-Aware Minimization Algorithms for Out-of-Distribution Generalization](https://mlsanity.com/paper/2412.05169/) (2024)
- [When Invariant Representation Learning Meets Label Shift: Insufficiency and Theoretical Insights](https://mlsanity.com/paper/2406.16608/) (2024)
- [Distribution Shift Is Key to Learning Invariant Prediction](https://mlsanity.com/paper/2601.12296/) (2026)
- [Dataset Dictionary Learning in a Wasserstein Space for Federated Domain Adaptation](https://mlsanity.com/paper/2407.11647/) (2024)
- [Causal Representation Learning with Observational Grouping for CXR Classification](https://mlsanity.com/paper/2506.20582/) (2025)
- [When Personalization Tricks Detectors: The Feature-Inversion Trap in Machine-Generated Text Detection](https://mlsanity.com/paper/2510.12476/) (2025)
- [Robust Multispectral Semantic Segmentation under Missing or Full Modalities via Structured Latent Projection](https://mlsanity.com/paper/2604.15856/) (2026)
- [Repeated Environment Inference for Invariant Learning](https://mlsanity.com/paper/2207.12876/) (2022)
- [FedGTST: Boosting Global Transferability of Federated Models via Statistics Tuning](https://mlsanity.com/paper/2410.13045/) (2024)
- [Information Subtraction: Learning Representations for Conditional Entropy](https://mlsanity.com/paper/2501.02012/) (2025)
- [Multi-Disease-Aware Training Strategy for Cardiac MR Image Segmentation](https://mlsanity.com/paper/2503.17896/) (2025)

## Abstract (arXiv)

A wide range of machine learning applications such as privacy-preserving learning, algorithmic fairness, and domain adaptation/generalization among others, involve learning invariant representations of the data that aim to achieve two competing goals: (a) maximize information or accuracy with respect to a target response, and (b) maximize invariance or independence with respect to a set of protected features (e.g., for fairness, privacy, etc). Despite their wide applicability, theoretical understanding of the optimal tradeoffs -- with respect to accuracy, and invariance -- achievable by invariant representations is still severely lacking. In this paper, we provide an information theoretic analysis of such tradeoffs under both classification and regression settings. More precisely, we provide a geometric characterization of the accuracy and invariance achievable by any representation of the data; we term this feasible region the information plane. We provide an inner bound for this feasible region for the classification case, and an exact characterization for the regression case, which allows us to either bound or exactly characterize the Pareto optimal frontier between accuracy and invariance. Although our contributions are mainly theoretical, a key practical application of our results is in certifying the potential sub-optimality of any given representation learning algorithm for either classification or regression tasks. Our results shed new light on the fundamental interplay between accuracy and invariance, and may be useful in guiding the design of future representation learning algorithms.