Fundamental Limits and Tradeoffs in Invariant Representation Learning

Han ZhaoChen DanBryon AragamTommi S. JaakkolaGeoffrey J. GordonPradeep Ravikumar

article2022JMLR62 citations

Establishes an information-theoretic framework that bounds the achievable tradeoffs between predictive accuracy and feature invariance across classification and regression tasks, providing a method to certify the suboptimality of representation learning algorithms.

Listen

Modern machine learning systems frequently face conflicting demands. Models must achieve high predictive accuracy on a primary target while remaining invariant or independent with respect to sensitive or extraneous attributes, such as demographic features in algorithmic fairness, user identifiers in privacy protection, or domain markers in cross-domain generalization. While practitioners widely adopt invariant representation learning to balance these goals, the theoretical limits of what any algorithm can simultaneously achieve have remained poorly understood.

The article addresses this gap by establishing an information-theoretic framework to evaluate the fundamental limits and optimal trade-offs between predictive accuracy and attribute invariance. It provides a formal characterization of the achievable performance region, termed the information plane, across both classification and regression settings.

To conduct this evaluation, the authors used information-theoretic and geometric analysis to map the feasible space of representations. In classification, they evaluated accuracy and invariance using mutual information and conditional entropy under cross-entropy loss. In regression, they framed the relationship using conditional variance under squared error loss. The analysis evaluated extreme operational boundaries and derived optimal frontiers through convex optimization and Lagrangian duality. The theoretical bounds were subsequently validated on benchmark datasets: the UCI Adult dataset for classification and the Law School dataset for regression, benchmarking standard baselines, neural networks, and adversarial training methods.

The investigation produced four central findings. First, the feasible space of accuracy and invariance is mathematically convex, meaning organizations can achieve intermediate trade-offs simply by randomizing between existing models. Second, perfect invariance imposes an unavoidable cost: whenever the target and protected attributes are correlated, no model can achieve full accuracy, as predictive error is bounded below by the statistical dependency between the two variables. Third, for regression tasks, the analysis derived an exact analytical curve representing the optimal Pareto frontier, proving it is fully achievable under standard distributional conditions such as Gaussian features. Fourth, empirical evaluations demonstrated that existing invariant learning methods—including adversarial approaches and neural networks—remain strictly suboptimal and fall significantly short of the theoretical frontier.

These findings have immediate implications for enterprise risk management, compliance, and model deployment. Organizations cannot eliminate demographic disparities or sensitive information leakage without sacrificing performance if the protected attribute shares genuine statistical correlation with the target outcome. Understanding this fundamental barrier protects decision-makers from pursuing mathematically impossible compliance standards while providing a quantitative baseline to audit whether a proprietary model is performing as efficiently as theoretically possible.

Organizations developing or auditing invariant learning pipelines should implement the article's statistical certificates to test whether deployed models reside far from the optimal frontier. If a model is certified as suboptimal, engineering teams should refine feature extraction before accepting excessive accuracy penalties. Where specific trade-offs are required for regulatory adherence, teams can blend existing models using randomized selection rather than retraining entirely new architectures from scratch.

These findings rest on population-level information-theoretic assumptions and focus on the inherent capacity of data representations. While sample-based estimators converge at standard statistical rates, practitioners should account for finite-sample estimation errors, class imbalances, and potential non-linear dependencies when applying these tests to specialized or limited enterprise datasets.

Carnegie Mellon University Massachusetts Institute of Technology University of Chicago University of Illinois Urbana-Champaign classification classification models pareto invariant representation learning domain adaptation fair representations

arXiv: 2012.10713

Paper: Invariant Risk Minimization, Martin Arjovsky et al. (2019). Read IRM first to understand the core goal of learning representations whose predictions remain invariant across environments, which this paper then analyzes through accuracy–invariance limits.
Paper: Deep learning and the information bottleneck principle, Naftali Tishby et al. (2015). Its information-bottleneck framing of representation learning provides the information-theoretic foundation for understanding the source’s mutual-information and conditional-entropy trade-offs.
Paper: Learning Fair Representations, Richard Zemel et al. (2013). This foundational fair-representation approach makes concrete the aim of suppressing sensitive-attribute information while preserving predictive utility, the tension the source formally characterizes.
Paper: Mitigating Unwanted Biases with Adversarial Learning, Brian Hu Zhang et al. (2018). Its adversarial debiasing framework supplies a representative method for reducing protected-attribute predictability whose performance the source’s theoretical frontier helps evaluate.

Paper: Fair and Optimal Classification via Post-Processing, Ruicheng Xian et al. (2023). Building on the source’s formal treatment of unavoidable accuracy–invariance costs, this work derives an optimal accuracy–demographic-parity trade-off and an algorithm to attain it through post-processing.

Cover for Fundamental Limits and Tradeoffs in Invariant Representation Learning

Abstract

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.

Topics

classification classification models pareto pareto-optimal representation learning feasible regions online learning individual privacy scale invariant

Keywords

invariant representation learning domain adaptation fair representations privacy-preserving learning information bottleneck method generalization bounds adversarial training maximal mutual information fundamental limits

1. Introduction
1.1 Our Contributions
1.2 Related Work
2. Preliminaries
2.1 Motivating Examples
3. Feasible Region for Accuracy & Invariance
4. Classification
4.1 E∗Y : Maximal Mutual Information under the Independence Constraint
4.2 E∗A : Minimal Mutual Information under the Sufficient Statistics Constraint
4.3 Application: Bounds on the Classification Loss
4.4 Application: Certifying Sub-optimality
4.5 Application: Implications for Learning Invariant Representations in Domain Generalization
5. Regression
5.1 E∗Y : Maximal Variance under the Invariance Constraint
5.2 E∗A : Minimal Variance under the Sufficient Statistics Constraint
5.3 An Exact Characterization of the Frontier
5.4 When are These Bounds Tight?
6. Numerical Experiments
6.1 Datasets
6.2 Representation Learning Algorithms
6.3 Results and Analysis
7. Conclusion
Acknowledgments
References
Appendix A. Proofs of Claims in Section 3
Appendix B. Missing Proofs in Classification (Section 4)
B.1 Convexity of R CE
B.2 Proof of Theorem 4.1
B.3 Proof of Theorem 4.2
B.4 Missing Proofs in Section 4.3 and Section 4.4
Appendix C. Missing Proofs in Regression (Section 5)
C.1 Convexity of R LS
C.2 Proof of Theorem 5.1
C.3 Proof of Theorem 5.2
C.4 Proof of Theorem 5.4
C.5 Explicit formula for eigenvalues
C.6 Proof of Theorem 5.3
C.7 Tightness of the Bounds
C.7.1 TIGHTNESS OF THE BOUND IN THEOREM 5.1
C.7.2 TIGHTNESS OF THE BOUND IN THEOREM 5.2
C.7.3 TIGHTNESS OF THE BOUND IN THEOREM 5.4
C.8 Proof without RKHS assumption

Knowls

Knowl 1 — Information plane for accuracy–invariance tradeoffs
definition
Let $X$ be an input, $Y$ a target, $A$ an attribute to be suppressed, and $Z=g(X)$ a possibly randomized representation. For binary classification evaluated with cross-entropy, the optimal prediction risks from $Z$ are $H(Y\mid Z)$ and $H(A\mid Z)$ ; equivalently, accuracy and leakage can be measured by $I(Y;Z)$ and $I(A;Z)$ , respectively. The classification feasible region is $\mathcal R_{\mathrm{CE}}=\{(I(Y;Z),I(A;Z)):Z=g(X)\}$ .

For scalar regression evaluated with squared loss, the corresponding risks are $\mathbb E[\operatorname{Var}(Y\mid Z)]$ and $\mathbb E[\operatorname{Var}(A\mid Z)]$ . Equivalently, use the explained-variance coordinates $\operatorname{Var}(\mathbb E[Y\mid Z])$ and $\operatorname{Var}(\mathbb E[A\mid Z])$ , and define $\mathcal R_{\mathrm{LS}}=\{(\operatorname{Var}(\mathbb E[Y\mid Z]),\operatorname{Var}(\mathbb E[A\mid Z])):Z=g(X)\}$ . In either plane, desirable representations have a large target coordinate and a small attribute coordinate; the data-processing inequality or total variance bounds the coordinates by their values when $Z=X$ .
Knowl 2 — Randomized representations make both feasible regions convex
model/method
For either classification or regression, take two representations $Z_0=g_0(X)$ and $Z_1=g_1(X)$ and an independent selector $S\sim\operatorname{Uniform}(0,1)$ . For any $u\in[0,1]$ , output the selected representation together with the selector:

$Z=(Z_S,S),\qquad Z_S=\begin{cases}Z_0,&S\leq u,\\Z_1,&S>u.\end{cases}$

The resulting accuracy–invariance coordinate pair is $u$ times the pair for $Z_0$ plus $1-u$ times the pair for $Z_1$ . Thus both $\mathcal R_{\mathrm{CE}}$ and $\mathcal R_{\mathrm{LS}}$ are convex. This also gives a construction for interpolating between the measured performance of two existing representations.
Knowl 3 — Classification utility achievable under perfect invariance
theoretical result
Assume binary $Y,A\in\{0,1\}$ and that both are deterministic functions of $X$ . Define the conditional-rate disparity

$\Delta_{Y\mid A}=\left|\Pr(Y=1\mid A=0)-\Pr(Y=1\mid A=1)\right|.$

Among representations $Z=g(X)$ that are independent of $A$ , the maximum target information is

$\max_{Z:I(A;Z)=0} I(Y;Z)=H(Y)-\Delta_{Y\mid A}H(A).$

The optimum is attainable. Consequently, any perfectly invariant representation has optimal cross-entropy prediction risk for $Y$ of at least $\Delta_{Y\mid A}H(A)$ , even though $X$ itself permits perfect prediction. The cost vanishes when $A$ and $Y$ are independent and is largest when the disparity and attribute entropy are large.
Knowl 4 — Minimum attribute leakage when target information is fully retained
theoretical result
Assume that $Y$ is recoverable from $X$ , and consider representations satisfying $I(Y;Z)=H(Y)$ , so that $Z$ retains all information about the target. The least possible leakage about $A$ is

$\min_{Z:I(Y;Z)=H(Y)} I(A;Z)=I(A;Y).$

The minimum is attained by representing $Y$ itself. Therefore, preserving all target information cannot in general reduce attribute leakage below the information about $A$ already present in $Y$ . Under cross-entropy, an adversary predicting $A$ from any such representation has optimal risk no greater than $H(A\mid Y)$ .
Knowl 5 — A classification certificate for representation suboptimality
theoretical result
Under the binary, deterministic classification assumptions, suppose $I(A;Y)>0$ and $\Delta_{Y\mid A}H(A)>0$ . A representation $Z$ is suboptimal if

$\frac{I(A;Z)}{I(A;Y)}+\frac{H(Y\mid Z)}{\Delta_{Y\mid A}H(A)}>1.$

Here suboptimal means that another representation can strictly increase $I(Y;Z)$ without increasing $I(A;Z)$ , or strictly reduce $I(A;Z)$ without reducing $I(Y;Z)$ . The criterion can be estimated from samples. In particular, for discrete $Z$ with alphabet size at most $k$ , the paper gives a plug-in certificate: if the estimated left-hand side exceeds $1+\varepsilon$ , the representation is certifiably suboptimal with probability at least $1-\exp(-\Omega(n\varepsilon^2))$ for sample size $n$ . When $\Delta_{Y\mid A}$ , $H(Y)$ , and $I(A;Y)$ are bounded below by positive constants, the estimator converges at rate $1/\sqrt n$ .
Knowl 6 — Regression tradeoffs at the perfect-invariance and perfect-utility endpoints
theoretical result
In the noiseless regression setting, assume scalar $Y,A$ are functions of $X$ represented in a reproducing kernel Hilbert space. Let $\rho_{YA}=\operatorname{Corr}(Y,A)$ . The explained target variance under perfect invariance, and the explained attribute variance when all target variance is preserved, satisfy

$\max_{Z:\,\operatorname{Var}(\mathbb E[A\mid Z])=0}\operatorname{Var}(\mathbb E[Y\mid Z])\leq \operatorname{Var}(Y)(1-\rho_{YA}^{2}),$

$\min_{Z:\,\operatorname{Var}(\mathbb E[Y\mid Z])=\operatorname{Var}(Y)}\operatorname{Var}(\mathbb E[A\mid Z])\geq \operatorname{Var}(A)\rho_{YA}^{2}.$

Thus correlation quantifies endpoint tradeoffs. In squared-error terms, perfect invariance forces target risk of at least $\operatorname{Var}(Y)\rho_{YA}^{2}$ ; retaining all target variance limits the attribute-prediction risk to at most $\operatorname{Var}(A)(1-\rho_{YA}^{2})$ . These bounds are attainable under the paper’s regularity condition.

The paper also gives noisy-setting endpoint bounds when $\mathbb E[Y\mid X]$ and $\mathbb E[A\mid X]$ lie in the RKHS. Writing $m_Y=\operatorname{Var}(\mathbb E[Y\mid X])$ , $m_A=\operatorname{Var}(\mathbb E[A\mid X])$ , and $c_{YA}=\operatorname{Cov}(\mathbb E[Y\mid X],\mathbb E[A\mid X])$ , the corresponding bounds are $\max_{Z:\,\operatorname{Var}(\mathbb E[A\mid Z])=0}\operatorname{Var}(\mathbb E[Y\mid Z])\leq m_Y-c_{YA}^{2}/m_A$ and $\min_{Z:\,\operatorname{Var}(\mathbb E[Y\mid Z])=m_Y}\operatorname{Var}(\mathbb E[A\mid Z])\geq c_{YA}^{2}/m_Y$ , for positive denominators.
Knowl 7 — Analytic regression frontier under a leakage constraint
theoretical result
In the noiseless regression setting, let $c$ be an upper bound on explained attribute variance, $\alpha=c/\operatorname{Var}(A)$ , and $\rho_{YA}=\operatorname{Corr}(Y,A)$ . For $0\leq c\leq \rho_{YA}^{2}\operatorname{Var}(A)$ , the best achievable target explained variance satisfies

$\max_{Z:\,\operatorname{Var}(\mathbb E[A\mid Z])\leq c}\operatorname{Var}(\mathbb E[Y\mid Z])\leq \operatorname{Var}(Y)\left(2\rho_{YA}\sqrt{(1-\rho_{YA}^{2})\alpha(1-\alpha)}+1-\alpha-\rho_{YA}^{2}+2\alpha\rho_{YA}^{2}\right).$

At $c=0$ this reduces to the perfect-invariance endpoint bound; at $c=\rho_{YA}^{2}\operatorname{Var}(A)$ it permits full target explained variance $\operatorname{Var}(Y)$ . The bound therefore interpolates between the endpoint tradeoffs. When the feature distribution satisfies the regularity condition defined in the next statement, this curve is achievable and exactly describes the Pareto frontier.
Knowl 8 — Condition for the regression bounds and frontier to be tight
definition
Let $\phi(X)$ be the RKHS feature vector with covariance operator $\Sigma=\operatorname{Var}(\phi(X))$ . The paper calls $(X,\phi)$ regular if, for every positive semidefinite operator $M$ satisfying $0\preceq M\preceq\Sigma$ , some possibly randomized representation $Z=g(X)$ realizes $\operatorname{Var}(\mathbb E[\phi(X)\mid Z])=M$ . If $(X,\phi)$ is regular, the endpoint bounds and the Lagrangian bound underlying the regression frontier are achievable. In particular, if $\phi(X)$ is Gaussian, then $(X,\phi)$ is regular, so the regression frontier stated above is exact.

Knowl 9 — Empirical comparison of representation methods on Adult and Law School

data/table

The experiments estimate the information-plane coordinates for four learned representations and compare them with theoretical endpoint bounds. On Adult, the task is binary income prediction, gender is the protected attribute, and the processed input has 114 attributes. The dataset has 30,162 training and 15,060 test examples; the reported group proportions are $\Pr(A=0)=0.673$ and $\Pr(A=1)=0.327$ , with income-positive rates $0.310$ and $0.113$ in those groups. Logit is a logistic-regression score, Linear is a learned linear representation, MLP uses one hidden ReLU layer, and Adv uses the MLP architecture with adversarial Wasserstein regularization. On Law School, the task is undergraduate-GPA regression and gender is treated as a continuous protected attribute in $[0,1]$ ; there are 1,823 records, with an 80/20 train/test split and $\Pr(A=1)=0.452$ . OLS uses its one-dimensional prediction as a representation; Linear, MLP, and Adv are regression counterparts, with a three-hidden-layer MLP on this dataset.

The reported numbers show that every evaluated method is strictly inside the corresponding theoretical frontier. On Adult, MLP and Adv dominate Logit and Linear, while MLP has higher target information and Adv has lower attribute information than MLP. On Law School, no method dominates another; MLP and Adv attain greater target explained variance than OLS and Linear, at the cost of greater attribute explained variance.

Adult metric	Lower bound	Logit	Linear	MLP	Adv	Upper bound
$I(Y;Z)$	0	0.170	0.171	0.216	0.202	$E_Y^*: 0.628$
$I(A;Z)$	$E_A^*: 0.037$	0.103	0.109	0.092	0.068	$H(A): 0.909$

Knowl 10 — Implication for domain-generalization impossibility bounds
empirical result
For domain generalization, interpret $A$ as the index of the source domain and require the learned representation $Z$ to satisfy $I(A;Z)=0$ . In the binary classification setting, the population cross-entropy risk of any predictor $h$ based on such a representation is bounded below by $\Delta_{Y\mid A}H(A)$ , where $\Delta_{Y\mid A}=|\Pr(Y=1\mid A=0)-\Pr(Y=1\mid A=1)|$ and $H(A)$ reflects the source-domain proportions. The bound expresses the accuracy cost of removing domain information when domain membership is associated with the target. The paper notes that the domain-generalization implication extends to settings with more than two source domains; the displayed disparity formula is for the binary case.

Coverage note — Proofs, intermediate semidefinite-programming and eigenvalue results, and the detailed finite-sample estimator derivations are omitted because they support the stated bounds rather than add separate conclusions; the paper’s future-work question about mixed discrete and continuous attributes is not a contributed result.

References

1.Roee Aharoni, Melvin Johnson, and Orhan Firat. Massively multilingual neural machine translation. arXiv preprint arXiv:1903.00089, 2019.
2.Isabela Albuquerque, João Monteiro, Mohammad Darvishi, Tiago H Falk, and Ioannis Mitliagkas. Generalizing to unseen domains via distribution matching. arXiv preprint arXiv:1911.00804, 2019.
3.Fabio Anselmi, Joel Z Leibo, Lorenzo Rosasco, Jim Mutch, Andrea Tacchetti, and Tomaso Poggio. Unsupervised learning of invariant representations. Theoretical Computer Science, 633:112–121, 2016a.
4.Fabio Anselmi, Lorenzo Rosasco, and Tomaso Poggio. On invariance and selectivity in representation learning. Information and Inference: A Journal of the IMA, 5(2):134–158, 2016b.
5.Arthur Asuncion and David Newman. Uci machine learning repository, 2007.
6.Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In Advances in neural information processing systems, pages 137–144, 2007.
7.Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1-2):151–175, 2010.
8.Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597–1607. PMLR, 2020.
9.Jianfeng Chi, Yuan Tian, Geoffrey J Gordon, and Han Zhao. Understanding and mitigating accuracy disparity in regression. arXiv preprint arXiv:2102.12013, 2021.
10.Maximin Coavoux, Shashi Narayan, and Shay B Cohen. Privacy-preserving neural representations of text. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1–10, 2018.
11.Zhun Deng, Frances Ding, Cynthia Dwork, Rachel Hong, Giovanni Parmigiani, Prasad Patil, and Pragya Sur. Representation via representations: Domain generalization via adversarially learned invariant representations. arXiv preprint arXiv:2006.11478, 2020.
12.Jing Dong, Shiji Zhou, Baoxiang Wang, and Han Zhao. Algorithms and theory for supervised gradual domain adaptation. arXiv preprint arXiv:2204.11644, 2022.
13.Sanghamitra Dutta, Dennis Wei, Hazar Yueksel, Pin-Yu Chen, Sijia Liu, and Kush R Varshney. An information-theoretic perspective on the relationship between fairness and accuracy. arXiv preprint arXiv:1910.07870, 2019.
14.Harrison Edwards and Amos Storkey. Censoring representations with an adversary. arXiv preprint arXiv:1511.05897, 2015.
15.Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural networks. The Journal of Machine Learning Research, 17(1):2096–2030, 2016.
16.Weihao Gao, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Estimating mutual information for discrete-continuous mixtures. In Proceedings of the 31st Neural Information Processing Systems, pages 5988–5999, 2017.
17.Jihun Hamm. Preserving privacy of continuous high-dimensional data with minimax filters. In Artificial Intelligence and Statistics, pages 324–332, 2015.
18.Jihun Hamm. Minimax filter: learning to preserve privacy from inference attacks. The Journal of Machine Learning Research, 18(1):4704–4734, 2017.
19.Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9729–9738, 2020.
20.Fredrik Johansson, Uri Shalit, and David Sontag. Learning representations for counterfactual inference. In International conference on machine learning, pages 3020–3029, 2016.
21.Fredrik D Johansson, Uri Shalit, Nathan Kallus, and David Sontag. Generalization bounds and representation learning for estimation of potential outcomes and causal effects. arXiv preprint arXiv:2001.07426, 2020.
22.Melvin Johnson, Mike Schuster, Quoc V Le, Maxim Krikun, Yonghui Wu, Zhifeng Chen, Nikhil Thorat, Fernanda Viégas, Martin Wattenberg, Greg Corrado, et al. Google’s multilingual neural machine translation system: Enabling zero-shot translation. Transactions of the Association for Computational Linguistics, 5:339–351, 2017.
23.Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. Advances in Neural Information Processing Systems, 33, 2020.
24.Ya Li, Xinmei Tian, Mingming Gong, Yajing Liu, Tongliang Liu, Kun Zhang, and Dacheng Tao. Deep domain generalization via conditional invariant adversarial networks. In Proceedings of the European Conference on Computer Vision (ECCV), pages 624–639, 2018.
25.David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. arXiv preprint arXiv:1802.06309, 2018.
26.Stéphane Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10):1331–1398, 2012.
27.Daniel McNamara, Cheng Soon Ong, and Robert C Williamson. Costs and benefits of fair representation learning. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 263–270, 2019.
28.Aditya Krishna Menon and Robert C Williamson. The cost of fairness in binary classification. In Conference on Fairness, Accountability and Transparency, pages 107–118, 2018.
29.Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International Conference on Machine Learning, pages 10–18, 2013.
30.A Tuan Nguyen, Toan Tran, Yarin Gal, and Atilim Gunes Baydin. Domain invariant representation learning with domain density transformations. Advances in Neural Information Processing Systems, 34:5264–5275, 2021.
31.R Quian Quiroga, Leila Reddy, Gabriel Kreiman, Christof Koch, and Itzhak Fried. Invariant visual representation by single neurons in the human brain. Nature, 435(7045):1102–1107, 2005.
32.Brian C Ross. Mutual information between discrete and continuous data sets. PloS one, 9(2):e87357, 2014.
33.Uri Shalit, Fredrik D Johansson, and David Sontag. Estimating individual treatment effect: generalization bounds and algorithms. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 3076–3085. JMLR. org, 2017.
34.Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 IEEE Information Theory Workshop (ITW), pages 1–5. IEEE, 2015.
35.Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physics/0004057, 2000.
36.Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984.
37.Linda F Wightman. Lsac national longitudinal bar passage study. lsac research report series. 1998.
38.Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory, 62(6):3702–3720, 2016.
39.Taihong Xiao, Yi-Hsuan Tsai, Kihyuk Sohn, Manmohan Chandraker, and Ming-Hsuan Yang. Adversarial learning of privacy-preserving and task-oriented representations. arXiv preprint arXiv:1911.10143, 2019.
40.Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International Conference on Machine Learning, pages 325–333, 2013.
41.Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pages 335–340, 2018.
42.Han Zhao and Geoff Gordon. Inherent tradeoffs in learning fair representations. In Advances in neural information processing systems, pages 15675–15685, 2019.
43.Han Zhao, Shanghang Zhang, Guanhang Wu, José MF Moura, Joao P Costeira, and Geoffrey J Gordon. Adversarial multiple source domain adaptation. In Advances in neural information processing systems, pages 8559–8570, 2018.
44.Han Zhao, Remi Tachet des Combes, Kun Zhang, and Geoffrey J Gordon. On learning invariant representation for domain adaptation. arXiv preprint arXiv:1901.09453, 2019a.
45.Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey J Gordon. Conditional learning of fair representations. arXiv preprint arXiv:1910.07162, 2019b.
46.Han Zhao, Junjie Hu, and Andrej Risteski. On learning language-invariant representations for universal machine translation. arXiv preprint arXiv:2008.04510, 2020.

Citation

MLA

Zhao, H., et al. “Fundamental Limits and Tradeoffs in Invariant Representation Learning”. Journal of Machine Learning Research, vol. 23, no. 340, 2022, pp. 1–9, https://www.jmlr.org/papers/v23/21-1078.html.

APA

Zhao, H., Dan, C., Aragam, B., Jaakkola, T. S., Gordon, G. J., & Ravikumar, P. (2022). Fundamental Limits and Tradeoffs in Invariant Representation Learning. Journal of Machine Learning Research, 23(340), 1–49. https://www.jmlr.org/papers/v23/21-1078.html

Chicago

Zhao, H., C. Dan, B. Aragam, T. S. Jaakkola, G. J. Gordon, and P. Ravikumar. 2022. “Fundamental Limits and Tradeoffs in Invariant Representation Learning”. Journal of Machine Learning Research 23 (340): 1–49. https://www.jmlr.org/papers/v23/21-1078.html.

Harvard

Zhao, H. et al. (2022) “Fundamental Limits and Tradeoffs in Invariant Representation Learning”, Journal of Machine Learning Research, 23(340), pp. 1–49. Available at: https://www.jmlr.org/papers/v23/21-1078.html.

Vancouver

1. Zhao H, Dan C, Aragam B, Jaakkola TS, Gordon GJ, Ravikumar P (2022) Fundamental Limits and Tradeoffs in Invariant Representation Learning. Journal of Machine Learning Research 23:1–49

BibTeX

@article{JMLR:v23:21-1078,
  author  = {Han Zhao and Chen Dan and Bryon Aragam and Tommi S. Jaakkola and Geoffrey J. Gordon and Pradeep Ravikumar},
  title   = {Fundamental Limits and Tradeoffs in Invariant Representation Learning},
  journal = {Journal of Machine Learning Research},
  year    = {2022},
  volume  = {23},
  number  = {340},
  pages   = {1--49},
  url     = {http://jmlr.org/papers/v23/21-1078.html}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Fundamental Limits and Tradeoffs in Invariant Representation Learning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Information plane for accuracy–invariance tradeoffs

Knowl 2 — Randomized representations make both feasible regions convex

Knowl 3 — Classification utility achievable under perfect invariance

Knowl 4 — Minimum attribute leakage when target information is fully retained

Knowl 5 — A classification certificate for representation suboptimality

Knowl 6 — Regression tradeoffs at the perfect-invariance and perfect-utility endpoints

Knowl 7 — Analytic regression frontier under a leakage constraint

Knowl 8 — Condition for the regression bounds and frontier to be tight

Knowl 9 — Empirical comparison of representation methods on Adult and Law School

Knowl 10 — Implication for domain-generalization impossibility bounds

References

Citation

BibTeX

Access the Paper