Fundamental Limits and Tradeoffs in Invariant Representation Learning
Authors: Han Zhao
Chen Dan
Bryon Aragam
Tommi S. Jaakkola
Geoff Gordon
Pradeep Kumar Ravikumar
Venue:  (2021)
Keywords: Representation learning

Abstract: Many machine learning applications involve learning representations that achieve two competing goals: To maximize information or accuracy with respect to a target while simultaneously maximizing invariance or independence with respect to a subset of features. Typical examples include privacy-preserving learning, domain adaptation, and algorithmic fairness, just to name a few. In fact, all of the above problems admit a common minimax game-theoretic formulation, whose equilibrium represents a fundamental tradeoff between accuracy and invariance. In this paper, we provide an information-theoretic analysis of this general and important problem under both classification and regression settings. In both cases, we analyze the inherent tradeoffs between accuracy and invariance by providing a geometric characterization of the feasible region in the information plane, where we connect the geometric properties of this feasible region to the fundamental limitations of the tradeoff problem. In the regression setting, we also derive a tight lower bound on the Lagrangian objective that quantifies the tradeoff between accuracy and invariance. Our results shed new light on this fundamental problem by providing insights on the interplay between accuracy and invariance. These results deepen our understanding of this fundamental problem and may be useful in guiding the design of adversarial representation learning algorithms.


Under review as a conference paper at ICLR 2021
FUNDAMENTAL LIMITS AND TRADEOFFS IN INVARIANT REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Many machine learning applications involve learning representations that achieve competing goals: To maximize information or accuracy with respect to target while simultaneously maximizing invariance or independence with respect subset of features. Typical examples include privacy-preserving learning, domain adaptation, and algorithmic faimess, just to name few. In fact, all of the above problems admit common minimax theeethe formulation, whose equilibrium represents a fundamental tradeoff between accuracy and invariance. this paper, we provide an information theoretic analysis of this general and important problem under both classification and regression settings. In both cases, we analyze the inherent tradeoffs between accuracy and invariance by providing a geometric characterization of the feasible region in the information plane, where we connect the geometric properties of this feasible region to the fundamental limitations of the tradeoff problem. In the regression setting, we also derive a tight lower bound on the Lagrangian objective that quantifies the tradeoff between accuracy and invariance. Our results shed new light on this fundamental problem by providing insights on the interplay between accuracy and invariance. These results deepen our understanding of this fundamental problem and may be useful in guiding the design of adversarial representation learning algorithms.
INTRODUCTION
One of the fundamental tasks in both supervised and unsupervised learning is to learn proper representations of data for various downstream tasks. Due the recent advances in deep learning, there has been surge of interest in learning so-called invariant representations, Roughly speaking, the underlying problem of invariant representation learning data that balances two goals simultaneously. First, the features should preserve enough information with respect to the target task of interest, e-g., good predictive accuracy. On the other hand, the representations should be invariant to the change of a pre-defined attribute, e.g., in visual perceptions the representations should invariant to the change of perspective or lighting conditions, etc. Clearly, in general there is often tension between these two competing goals of error minimization and invariance maximization. Understanding the fundamental limits and tradeoff' therein remains an important open problem.
find a feature transformation of the
In practice, the problem learning invariant representations is often formulated as solving a minimax sequential game between two agents, feature encoder and adversary. Under this framework, the goal of the feature encoder is to learn representations that could confuse a worst-case adversary in discriminating the pre-defined attribute. Meanwhile, the representations given by the feature encoder should be amenable for a follow-up predictor of target task. In this paper, we consider the situation where both the adversary and the predictor have infinity capacity, so that the tradeoff between accuracy and invariance solely depends on the representations given by the feature encoder. In particular, our results shed light on the best possible tradeoff attainable by any algorithm. This leads to Lagrangian objective with tradeoff parameter between these two competing goals, and we study the fundamental limitations of this tradeoff by analyzing the extremal values of this Lagrangian in both classification and regression settings. Our results shed new light the fundamental tradeoff between accuracy and invariance, and give a crisp characterization of how the dependence between the target task and the pre-defined attribute affects the limits of representation learning.

---

Under review as a conference paper at ICLR 2021
Contributions We geometrically characterize the tradeoff between accuracy and invariance via the information plane (Shwartz-ZZi Ziv & Tishby 2017) analysis under both classification and regression settings, where each feature transformation correspond to point on the information plane. For the classification setting, we provide a fundamental characterization of the feasible region in the informa- tion plane, including its boundedness, convexity, and extremal vertices. For the regression setting, we provide an analogous characterization of the feasible region by replacing mutual information with conditional variances. Finally, in the regression setting, we prove tight cermattiontthooreeee lower bound on Lagrangian objective that trades off accuracy and invariance. The proof relies on an interesting SDP relaxation, which may be of independent interest.
Related Work There are abundant applications of learning invariant representations in various downstream tasks, including domain adaptation (Ben- et al.
2007 2010 Ganin et al., 2016
Zhao et al. 2018), algorithmic fairness (Edwards & Storkey| [015 Zemel et al. 2013|Zhang et al.
2018 Zhao et al. 2019b), privacy-
learning (Hamm) [015] 2017: Coavoux et al. 2018
Xiao et al., (2019), invariant visual representations (Quiroga et al. [005] Gens & Domingos 20
Bouvric al. 2009; Mallat 2012, Anselmi et al. 2016), and causal inference (Johansson et al. 2016
Shalit et a 2017| Johansson et al. 2020), just to name a few. To the best of our knowledge, no
previous work studies the particu lar tradeoff problem in this paper. Closest to our work are results in domain adaptation (Zhao et al. 2019a) and algorithmic fairness (Menon & Williamson 2018 (Zhao & Gordon 2019), showing lower bound on the classification accuracy on two groups. e-g., source vs. target in domain adaptation and majority vs. minority in algorithmic faimesss. Compared to these previous results, our work directly characterizes the tradeoff between accuracy and invariance using information theoretic concepts in both classification and regression settings, Furthermore, we also give an approximation to the Pareto frontier between accuracy and invariance in both cases.
BACKGROUND AND PRELIMINARIES
Notation We adopt the usual setup given (X, x V, where Y is the response, X TRP represents the input vector, and we seek a clasiffication/regressio function f(X) that minimizes (X()(X), Y) where é 3 y + RR is some loss function depending on the context of the underlying problem. In this paper, we consider two typical choices of f: (1) the cross entropy loss, i.e. Ely v/)
y Ioog(y') (1 (1-y) log(1-1) yy). which typically used when Y is a discrete variable in classification; (2) the squared loss, i.e. E(y. 3/) (y- y 2 which is suitable for Y continuous, as in regression.
Throughout the paper, we will assume that all random variables have finite second-order moments.
Problem Setup Apart from the input/output pairs, in our setting there is a third variable A, which corresponds to a variable that a predictor should be invariant to. Depending on the particular application, A could correspond to potential protected attributes in algorithmic faimess, e.g., the ethnicity or gender of an individual; or could be the identity of domain index in domain adaptation, etc. In general, we assume that there is joint distribution D over the triple (X, A, Y), from which our observational data are sampled from. Upon receiving the data, the goal of the learner has two folds. On one hand, the learner aims to accurately predict the target Y. On the other hand, it also tries to be insensitive to variation in A. To achieve this dual goal, one standard approach in the literature (Zemel et al., 2013); Edwards & Storkey| 2015 Hamm 2015 Ganin et al. 2016 Zhao et al. 2018) is through the lens of representation learning. Specifically, let 7 = g(X) where g(.) is a (possibly randomized) transformation function that takes X as input and gives the corresponding feature encoding Z. The hope is that, by learning the transformation function g(-), Z contains as much information as possible about the target Y while at the same time filtering out information related to A. This problem is often phrased as an adversarial game:
min max f.g f
ED[((f o ox(X), Y) X ED|e(f' o A))),
where the two competing agents are the feature transformation g and the adversary f', and 0 tradeoff hyperparameter between the task variable Y and the attribute A. For example, the adversary f' could be understood as a domain discriminator in applications related to domain adaptation, or an auditor of sensitive attribute in algorithmic fairness. In the above minimax game, the first term corresponds to the accuracy of the target task, and the second term is the loss incurred by the adversary. It is worth pointing out that the minimax problem in ① is separable for any fixed feature transformation g, in the sense that once g has been fixed, the optimization of ff and f' are independent of each other. Formally, define Ry (g) inf, [ Y) to be the optimal risk in predicting
2

---

Under review as a conference paper at ICLR 2021
Y using Z 2= (X) under loss E, and similarly define R2) The separation structure of the problem leads to the following compact form:
OPT(A) min Ry (g) X RZ)
9
The minimization here is taken over a family of (possibly randomized) transformations g. Intuitively, (2) characterizes the situation where for given transformation Z = g(X), both f and f" play their optimal responses. Hence this objective function characterizes a fundamental limit of what the best possible representation there is an inherent tension between the minimization of Rt- (g) and the maximization of R2 (9), and realization of such tradeoff.
hope achieve for a fixed value A. In general, with 0 < X oc,
choice of the tradeoff hyperparameter À essentially corresponds
Motivating Examples We discuss several examples to which the above framework is applicable.
In privacy applications, the goal is to make it difficult to predict sensitive data, represented by the attribute A, while retaining information about Y (Hamm 2015)
Example 2.1
2017 Coavoux et al. 2018 Xiao et al.] 2019). A way to achieve this is to pass information through 7, the "privatized" or "sanitized" data.
Example 2.2 (Algorithmic Fairness). In fairness applications, we seek to make predictions about the response Y without discriminating based on the information contained in the protected attributes A. For example, A may represent protected class of individuals defined by, e.g. race or gender. This definition of fairness is also known as statistical parity in the literature, and has received increasing attention recently from an information -eeematton-tthortiic perspective (McNamara et al. 2019: Zhao & Gordon 2019 Dutta et al. 2019).
Example 2.3 (Domain Adaptation). In domain adaptation, our goal is to train a predictor using labeled data from the source domain that generalizes to the target domain. In this case, A corresponds to the identity of domains, and the hope here is to learn a domain-invariinn representation that is informative about the target Y (Ben-David al. 2007 2010 Ganin et al., 2016 Zhao al. 2018).
Example 2.4 (Group Invariance). In many applications in computer vision, it is desirable to learn predictors that are invariant to the action of group G' on the input space. Typical examples include rotation, translation, and scale. By considering random variables that take their values G, one approach to this problem is to learn a representation Z that "ignores" changes in A (Quiroga et al.) 2005 Gens & Domingos 2014 Bouvric et al., 2009| Mallat, 2012 Anselmi et al. (2016).
Example 2.5 (Information bottleneck). The information bottleneck (Tishby et al., 2000 is the problem of finding representation Z that minimizes the objective I(Z; Y) AZ (Z;X) in an unsupervised manner. This is closely related to, but not the same as the problem we study, owing to the invariant attribute A.
FEASIBLE REGION ON THE INFORMATION PLANE
We begin by defining the feasible region associated with the adversarial game ① and discussing its relevance to the problem we study. Formally, we define the information plane to the 2D coordinate plane with axes - R2y (g) and - R2, (g), respectively. The feasible region then corresponds to the two-dimensional region defined by the pairs (-Rt (g), -R (g)) over all possible representations Z = g(X) the information plane. More concretely, in the classification and regression settings, these pairs can be given a more intuitive interpretation terms of mutual information and conditional variances, respectively. In particular, it is easy to show the following:
1. (Classification) Under cross- loss, using standard citemattion-therredd identities the adversarial game (2) can be rewritten
min Z=a(X)
H(Y Z) A- ((A) 2)
max (x
1(); - X- ((A;
(3)
2. (Regression) Under the least-squares loss, by the law of total variance, the adversarial game can be rewritten as
min E[Var(Y Z)] 101---E3 A-E[Var(A Z)] ==)(X)
max Z=9(X)
Var E A Z]. (4)
These equivalences motivate the following definitions:
(Classification): RCE := (), IR²),
(Regression):
RRS ((V Z), Var E[A Z R²).
3

---

Under review as a conference paper at ICLR 2021
1(::2)
Var [[A 2]
((A)
X
Var( (4)
2 X
E
I(Y:2)
Var B|Y
2 c
Ey
H(Y)
7 =
B
Var(Y)
(a) Information plane of classification.
(b) Information plane of regression.
Figure 1: 2D information plane. The shaded area correspond to the feasible region.
We call both ReE and Ris the feasible region for the classification and regression settings, respectively. See Fig. I for an illustration of the information planes and the feasible regions. At this point, may not be immediately clear what the relevance of the feasible region is. To see this, recall that our high-level goal is to find representations Z that maximize accuracy (i.e. Ep [((](()) Y)D while simultaneously maximizing invariance (i.e. ED (Z)) A)), and consider the four vertices (not necessarily a part of the feasible region) in Fig. These four corners have intuitive interpretations:
(Red) The so-called "informationless" regime, which all of the information regarding both Y and A is destroyed. This is achieved by choosing a constant representation 2 = (Yellow) Here, we retain all of the information in A while removing of the information about Y. This is not particularly interesting regime for the aforementioned applications. X and no information is lost. This the
(Blue) The full information regime, where "classical" setting, wherein information about A is allowed to leak into Y.
(Green) This is the ideal representation that we would like to attain: we preserve all the relevant information about Y while simultancously removing all the information about A.
Unfortunately, in general, the ideal representation may not be attainable due to the potential correlation between Y and A. As result, are interested in characterizing how "close" this ideal transformation given the distribution over (X, A, Y). More precisely, we can describe the various extremal points on the boundary of the feasible region follows:
get attaining
F This point corresponds to a representation that maximizes accuracy subject to a hard constraint the invariance (ef. (5 10)) i.e. there is no leakage of information about A into the representation Z. In classification, we enforce this via the mutual information constraint [(A; Z) and in regression via the conditional variance constraint Var E[A] Z] = O. E;: This point corresponds to representation Z that maximizes invariance subject to a hard constraint on the accuracy (cf. 8. (2)) i.e. there is no loss of information about Y in the representation Z. In classification, we enforee this via the mutual information constraint T(Y; ) = (YY and regression we enforce this via the conditional variance constraint Var R|Y 2] Var(Y).
As we vary À E (0, 20). we carve out a path OPT(A) between E& and E that corresponds to the optimal values of (I). This is the Pareto frontier of the accuracy-inee -ccrrac-invariance tradeoff, and represents the best possible tradeoff attainable for a given X.
Due to the symmetry between Y and A in (2), the feasible regions in both cases symmetric with respect to the diagonal of the bounding rectangle. With the feasible region more clearly exposed, we concretely outline our objective: To analytically characterize the solutions to the extremal problems corresponding to the lower and upper right points on the boundaries, and to provide lower bounds on the objective OPT(A). Due to the page limit, we defer all the detailed proofs appendix and mainly focus on providing interpretations and insights of our results in the main paper.
CLASSIFICATION
In order to understand the tradcoff between these two competing goals, it is the most interesting to study the case where the original input X contains full information to predict both Y and A, so that
4

---

Under review as a conference paper at ICLR 2021
any loss of accuracy is not due to the noninformative input X. To this end, our following analysis focuses on the noiseless setting Assumption 4.1. There exist functions f (-) and fā(+), such that Y = (X) and A = (X)..
In order to characterize the feasible region ReF, first note that from the data processing inequality, the following inequalities hold:
0 S [Y; 2) S (
0 S [A; 2) - ((A:)) (A),
which means that for any transformation Z ( the point (I(Y; ; 2), [[A; Z)) must lie within rectangle shown in Fig. 2a The following lemma shows that the feasible region ReE convex: Lemma 4.1. RCF is convex.
Here, the convexity of RRE is guaranteed by a construction of randomized feature transformation. As we briefly discussed before, we know that two vertices of the bounding rectangle are attainable, i.c. the "informationless" origin and the "full information" diagonal vertex. Now with Lemma 4.1 it is clear that all the points on the diagonal of the bounding rectangle are also attainable.
4.1 MAXIMAI. MUTUAL INFORMATION UNDER THE INDEPENDENCE CONSTRAINT
In this section explore the extremal point Ey. This means that would like to maximize the mutual information Z w.r.t and simultaneously being independent of A:
max I):
subject to I[A: Z) =.
(5)
First of all, realize that the optimal solution of (5) clearly depends the coupling between A and Y. To see this, consider the following two extreme cases:
Example 4.1. A = Y almost surely, then [(A; Z) = 0 directly implies I(Y; = 0, hence
maxz [Y; 2) under the constraint that [AA; 2) = O.
Example 4.2. If A 1 Y, then = f6 (X) Y satisfies the constraint that [AA; 2) 1(A 0. Furthermore, I(Y; Z) = I(Y: Y) = H(Y) 2 I(Y; I AZ AZ' + Y. Hence maxz [(Y; 2) = H(Y.
The above two examples show that the optimal solution of (5). if exists analytically, must include quantity that characterizes the dependency between A and Y. We first define such quantity:
Definition 4.1. Define y == Prp (Y A = 0) Pr
A
1))-
is easy to verify that the following claims hold about ÁYiA:
5 AyJa I and ΔAΙд 0 A 1 Y. and ArJa = = A A= or A (6)
With this introduced notation, the following theorem gives an analytic solution to 5 Theorem 4.1. The optimal solution of optimization problem (5) is
max 7,I(A:)) -
1(Y; H(Y) AYIA (IAA).
Let us have a sanity check of this result: First, A T Y, then Aria = 0, and in this case the optimal solution given by Theorem 4.1 reduces to H(Y) 0 H(A) = H(Y), which consistent with Example 4.2) Next, consider the other extreme case where A = Y. In this case
AriA 1 and HYY = (A), therefore the optimal solution given by Theorem becomes H(Y) - 1 (AA = HYY - HYY = 0. This is consistent with Example 4.1
Moreover, due to the symmetry between A and Y, we can now characterize the locations of the two extremal points on the lower and left boundaries. The updated figure is plotted in Fig. In Fig. 2b A AjY is defined analogously Arja by swapping Y and A.
4.2 MINIMUM MUTUAL INFORMATION UNDER THE SUFFICIENT STATISTICS CONSTRAINT
Next, we characterize the other extremal point, i.e. E Again, by the symmetry between A and Y, suffices to solve the following optimization problem, whose optimal solution is E
min [(A; Z),
subject to 1(Y: Z) = H(Y)
(8)
EExtensions to the general noisy setting are feasible, hut the results are less interpretable. Hence we mainly focus the noiseless setting in this paper.
5

---

Under review as a conference paper at ICLR 2021
[(A:)) Z)
I(A:Z)
2 = X
[A)
Lan(d) AiY
X
((4)
Ai BY
tan(0) Ayja
2)
I(Y;
7
H(Y)
Z
Avia H(a)H(()
(a) Rectangle bounding box.
(b) Maximal I(:-)) under the independence constraint.
I(A:2)
I(A; 2)
H(4)
I(A.Y)
1 X
H(A)
K(YY
tan(d)
AAY
2 = X
tant = IAA
HOAI
AAY HIY
tan( Ayia
10'
d''
tant
I(A:Y)
I(A:Y)
I(Y;))
10'
I(Y:2)
Z = (0') =
((A.3)
M(P)
HYY)
Z
tan(0')
I[A: WYY
AYiA
(Y))
(c) Minimum ((5.) under the sufficient-ste stat constraint.
(d) The convex polygon characterization Ree.
Figure 2: Information plane in classification. Shaded corresponds the known feasible region.
Theorem 4.2. The optimal solution of optimization problem
min I(A; ((AY)). 2.((YZ)=H(())
(9)
Clearly, if and Y are independent, then the gap I)A:Y) = O, meaning that we can simultaneously preserve all the target related information and filter out all the information related A. With the above result, we can now characterize the locations the remaining two extremal points on the top and right boundaries of bounding rectangle. The updated figure is shown in Fig. 2c
4.3 THE INFORMATION PLANE IN LEARNING REPRESENTATIONS Z
To get the full picture, we combine our results in Section 4.1 and Section 4.2 and use the fact that RcE must be convex (Lemma 4.1) This allows to complete the analysis by connecting the black dots on the four boundaries the bounding rectangle, as shown in Fig. 2d The feasible region RCE is convex polygon. Furthermore, both the constrained accuracy optimal solution and the constrained invariance optimal solution can be readily read from Fig. 2d as well.
As mentioned before, ideally would like to find representation Z that attains the green vertex of the bounding rectangle. Unfortunately, due to the potential coupling between Y and A, this solution is not always feasible. Nevertheless, it is instructive see the gaps between the optimal solutions we could hope to achieve and the ideal one:
Maximal information: The gap is given by АYΙA (A). On one hand, if A L Y, then ArJa so the gap is O. On the other hand, if A = Y, then Aria 1 and H(A) H(Y).
the gap achieves the maximum value (Y).
Maximal invariance: The gap is given by (AA On one hand, 1 Y, then [(A: Y) = 0 so the gap is O. On the other hand, if A Y. then ((A H (A), again, the gap achieves the maximum value H (A).
One open question that do not answer here is whether the feasible region ReE is strictly convex or not. That is, whether the Pareto-frontier between Ey and E is strictly convex or not? On the other hand, for each value of X, the line segment connecting Fyy and E forms lower bound of

---

Under review as a conference paper at ICLR 2021
Var 2]
Var 3|4 2
2 X
(ar(A)
Var(4)
Var BlY [2]
Var B[Y
Var(Y)
2 ==c
Veri oa. (0.0
(n, Var(2)
(a) Rectangle bounding box.
(b) Maximal Variance.
VarB|A| 2
|
(ar(A)
Z X
Var(A) (4)
Santhn ipai
Varci vi? 10037"
Var E(Y |2]
Var K.y
Z
Var(Y)
Vari-4)-c.uu
(a. Var(Y))
(4.4)
Seuel
(c) Minimum Variance.
(d) The convex polygon characterization of Ris.
Figure 3: Information plane in regression. Shaded area corresponds to the known feasible region.
the Lagrangian. For the aforementioned applications, our approximation of the frontier is critical order be able to certify that given model is not optimal. For example, given some practically computed representation Z and by using known optimal estimators of the mutual information, is possible to estimate I(A; Y). T(Y; Z). [AA; Z) order directly bound the (sub)-optimality of Z using Fig. [d] i.e., how far away the point (I(Y; Z), I (A; Z)) is from the line segment between Ey
and E This distance lower bounds the distance to the optimal representations on the Pareto frontier.
5 REGRESSION
Similar to what we have before, in regression we assume a noiseless setting for better interpretability of our results. The generalization to the noisy setting is included in the appendix. Let H be an RKHS.
Assumption 5.1. There exist functions fý, fA E H, such that =
= (X) and A = fx)).
Let (..)) be the canonical inner product in RKHS H. Under this assumption, there exists feature map (X) and a * 0, * O, such that Y = (X) = (xx y) and = fā (X) = (p((),, ) a). This feature map does not have to be fnite-dimensional, and our analysis works for the case where fý, fA are infinite-dimensinnal Next, by the law of total variance, the following inequalities hold:
S Var E Z] < Ea
X] = Var(Y),
0 S Var E[A 21 S Var E[A X = Var(A),
which means that for any transformation Z g the point (Var Y 2), Var Z]) must lie within rectangle shown in Fig. 3a To simplify the notation, we define Σ = Cov( (X),, ((())
to be the covariance operator of (x)).
Again, if we consider all the possible feature transformations Z = 9(X), then the points (Var E[Y 7), Var [ Z)) will form a feasible region Ris- Similar to what we have in classification, the following lemma shows that the feasible region RLs is convex:
Lemma 5.1. R1s is convex.
The convexity of Ris is guaranteed by a construction of randomized feature transformation. Similarly, both the "informationles"" origin and the "full information" diagonal vertex attainable.
7

---

Under review as a conference paper at ICLR 2021
5.1 THE BOUNDING VERTICES ON THE PLANE
In this section we explore the extremal point Ey and EAA for regression. For Ey, this means that we would like to maximize the variance of Z w.r.t Y and simultaneously minimizing that of A:
max Z
Var 1 Z],
subject to Var V|A 2] =
(10)
It is clear that the optimal solution of (T)) depends on the coupling between A and Y, and the following theorem precisely characterizes this relationship:
Theorem 5.1. The optimal solution of optimization problem (00) is upper bounded by
max Var E|| Z] S Var(Y) (2. Σa) Var(A) (aa y) (a, y). (a.a)²
(11)
V, E[A|]=00 Again, let us sanity check this result: First, if a is orthogonal y. i.e., (a, v) O, then the gap is O. and the optimal solution becomes Var(Y). Next, consider the other extreme case where is parallel to y. In this case it can readily verified that the optimal solution reduces to With these two results, we can now characterize the locations of the two extremal points the bottom and left boundaries of bounding rectangle. The updated figure is plotted in Fig. 36
(a.
Similarly, for E it suffices to solve the following problem, whose optimal solution is E;:
min Var B[A] Z],
subject to Var E|y Z] = Var(Y)
(12)
Theorem 5.2. The optimal solution of optimization problem
12) is lower bounded by
Var(Y) -aa.v) y/
min 2. Var Varr)))))
Var E[A|
(13)
(y. y)
Again, if is orthogonal to y, then the optimal solution is O. meaning that can simultaneously preserve all the target variance and filter out all the variance related to A. On the other hand, if a is parallel to y. then Var(Y)- y). (y, y)² Var(A). The updated plot is shown in Fig. 3c
5.2 A SPECTRAL LOWER BOUND OF THE LAGRANGIAN
Combining our results in Thm. 5.1 and Thm. 5.2 along with the fact that Ris must be convex, we plot the full picture about the feasible region in the regression setting in Fig. 3d
Both the constrained accuracy optimal solution and the constrained invariance optimal solution can be readily read from Fig. [3 as well. In fact, in the regression setting, we can say even more: We can derive a tight lower bound to the Lagrangian problem OPT(A) == minz=g(X) E Var(( Z)] - X B[Var(A (A1 Z)).
Theorem 5.3. The optimal solution of the Lagrangian has the following lower bound:
OPT(A) 2 1 VVrr(Y) X VAr(A) v(Var(YY + A Var(2))² 4A(y, Ea)²
(14)
Evidently, the key quantity in the lower bound (14) is the quadratic term (y. Ea). which effectively measures the dependence between the Y and under the feature covariance E.
The proof of Thm. 5.1 5.2 and 5.3 rely on finic-dimennsonall SDP relaxation, and constructs an explicit optimal solution this relaxation. We corfomulltee the objective as linear functional of : (ov(B((p(X) Z]. (X) ZI), which satisfies the semi-definite constraint 0 < V < Σ Cov(y(X), (X)). Therefore, the optimal value of the SDP is an upper/lower bound of the objective. Furthermore, we show that under certain regularity conditions, the SDP relaxation is exact. One particularly interesting setting where the regularity condition holds when (xX) follows a Gaussian distribution. More discussions about the tightness of our bounds are presented in appendix C.5
6 CONCLUSION
We provide an information plane analysis to study the general and important problem for learning invariant representations in both classification and regression settings. In both cases, we analyze the inherent tradeoffs between accuracy and invariance by providing a geometric characterization of the feasible region on the information plane, in terms of its boundedness, convexity, as well as its its extremal vertices. Furthermore, in the regression setting, we also derive a tight lower bound that for the Lagrangian form of accuracy and invariance. Given the wide applications of invariant representations in machine learning, we believe theoretical results could contribute to better understandings of the fundamental tradeoffs between accuracy and invariance under various settings, e.g., domain adaptation, algorithmic faimess, invariant visual representations, and privacy-preservate learning.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
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, 2016.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Percira. Analysis of representations for domain adaptation. In Advances in neural information processing systems, pp. 137-144, 2007.
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)1151-1555 2010.
Jake Bouvrie, Lorenzo Rosasco, and Tomaso Poggio. On invariance in hierarchical models. In Advances in Neural Information Processing Systems. pp. 162-170, 2009.
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, pp. 1-10, 2018.
Sanghamitra Dutta, Dennis Wei, Hazar Yueksel, Pin- Yu Chen, Sijia Liu, and Kush R Varshney. An information -inemaattoon-hhoteiic perspective on the relationship between fairness and accuracy. arXiv preprint arXiv:1910.07870 2019.
Harrison Edwards and Amos Storkey. Censoring representations with an adversary. arXiv preprint arXiv:151.05589, 2015.
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):209--2300, 2016.
Robert Gens and Pedro Domingos. Deep symmetry networks. In Advances neural information processing systems, pp. 2537-2545, 2014.
Jihun Hamm. Preserving privacy of continuous high-dimensional data with minimax filters. In Artificial Intelligence and Statistics, pp. 324-332, 2015.
Jihun Hamm. Minimax filter: learning to preserve privacy from inference attacks. The Journal of Machine Learning Research, 18(1):4704447) 4734, 2017.
Fredrik Johansson, Uri Shalit, and David Sontag. Learning representations for counterfactual inference. In International conference on machine learning, pp. 3020-3029, 2016.
Fredrik 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.
Stéphane Mallat, Group invariant scattering, Communications on Pure and Applied Mathematics, 65 (10):1331-1398, 2012.
Daniel McNamara, Cheng Soon Ong, and Robert Williamson. Costs and benefits of fair representa- tion learning. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 263-270, 2019.
Aditya Krishna Menon and Robert C Williamson. The cost of fairness in binary classification. In Conference on Fairness, Accountability and Transparency, pp. 107-118, 2018.
Quian Quiroga, Leila Reddy, Gabriel Kreiman, Christof Koch, and Itzhak Fried. Invariant visual representation by single neurons in the human brain. Nature, 435(7045): 102-11077 2005.
Uri Shalit, Fredrik D Johansson, and David Sontag. Estimating individual treatment effect: general- ization bounds and algorithms. In Proceedings of the 34th International Conference on Machine Learning-Volle Volume 70, pp. 3076-3085. JMLR. org, 2017.
Ravid Shwartz- Ziv and Naftali Tishby. Opening the black box of deep neural networks via information. arXiv preprint arXiv: 700.00080.. 2017.

---

Under review as a conference paper at ICLR 2021
Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physics/0004057, 2000.
Taihong Xiao, Yi-Hsuan Tsai, Kihyuk Sohn, Manmohan Chandraker, and Ming-Hsuan Yang. Adversarial learning of privacy-preserving and task-oriented representations. arXiv preprint 1rXiv:1911.1014 2019.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In Interaational Conference on Machine Learning, pp. 325-333, 2013.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference AI, Ethics, and Society, pp. 335- 340, 2018
Han Zhao and Geoff Gordon. Inherent tradeoffss in learning fair representations. In Advances in neural information processing systems, pp. 15675-15685, 2019.
Han Zhao, Shanghang Zhang, Guanhang Wu, José MF Moura, Joao P Costeira, and Geoffrey Gordon. Adversarial multiple source domain adaptation. In Advances in neural information processing systems, pp. 8559-8570, 2018.
Han Zhao, Remi Tachet des Combes, Kun Zhang, and Geoffrey Gordon. On learning invariant representation for domain adaptation. arXiv preprint arXiv:1901.09443 2019a.
Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey J Gordon. Conditional learning of fair representations. arXiv preprint arXiv:1910.0710 2019b.
10

---

Under review as a conference paper at ICLR 2021
A PROOFS FOR CLAIMS IN SECTION 3
In this section we give detailed arguments to derive the objective functions of Eq. 33) and (4) respectively from the original minimax formulation in Eq. TT. First, let consider the classification setting.
Classification Given fixed feature map = (XX), due to the symmetry between and A in
Eq. [ it suffices for us to consider the case of finding f that minimizes Ep [e[ o g ). Y) and analogous result follows for the case of finding the optimal f' that minimizes ED[e( ((x) A)]
similarly. By definition of the cross-entropy loss, we have:
Eff o g(X), Y)]
-ED [I(Y 0) log(1 f(((X))) + I[Y 1) ()g((((f())]]
-Ep [I(Y 0) log(1 f(2)) + +(Y = 1) 1))))((((2)
By [T(Y 0) log(11 - f(Z)) + +1((Y 1))
--z [Pr(Y = 0 log(( - f(()) = -Pr(Y =1 Z) log(f
Ez [KL((P(Y))) [ f())) + IZ)
H(Y Z).
is also clear from the above proof that the minimum value of the cross-entropy loss is achieved when f(Z) is randomized classifier such that [[f(Z)] = Pr(Y = Z). This shows that
min Ep [e(f () H(Y Z): and min Enleff gX), A)] H (A Z).
To see the second part of Eq. (3), simply use the identity that H Σ) = μ(Y) - I(;; Z) and H (A Z) (A) [(A; 2) with the fact that both HYY and (A) are constants that only depend on the joint distribution D.
Regression Again, given fixed feature map Z = (X), because of the symmetry between and A let focus the analysis of finding f that minimizes Ep [e(f g(X), Y)]. In this case since ((.e)) :) is the mean squared error, it follows that
EDlE(f o g(X). Y)] Ep [(f o ( y)
Ep [[f(Z)-]] - YY)
= Ez [(f(Z) - E[Y Z)) + Ez By - E|Y 2))
2 Ez [ - E[(Y ]]
E[Var(Y Z)),
where the third equality is due the Pythagorean theorem. Furthermore, is clear that the optimal mean-squared error is obtained by the conditional mean f(Z) = E 2]. This shows that
min [ff g(X), Y)] EaVar(Y Z)]. and p Ed(e(f' xX). A)] E[Var(A) Z)).
For the second part, use the law of total variance Var(Y) = E(Var(Y) =\Var\ Z)] + Var(E 2T) and (A) (ar (A Z)] + (ar(E[A Z)). Realizing that both Var(Y) and Var(A) are constants
that only depend on the joint distribution DD we finish the proof.
B MISSING PROOFS IN CLASSIFICATION (SECTION
In what follows we first restate the propositions, lemmas and theorems in the main text, and then provide the corresponding proofs.
B. CONVEXITY OF RCE
Lemma 4.1. RCE is convex.
Proof. Let Z, = (X) for E 10,1} with corresponding points ((A; E ReR-
Then only need to prove that for Vu E 1), (Y Zn) + +11 (1-w)/(YY; w)/(Y; u))(Y:))),u[AAAA) +(1
11

---

Under review as a conference paper at ICLR 2021
(A; Z1)) RcB well. For any u e 10, 1]. let S ~ (0, 1). the uniform distribution over (0, 1), such that S 1 AY. Consider the following randomized transformation Z:
Zo 2
If S S u,
7
(15)
otherwise.
To compute (Y;Z), we have:
I(Y: 2) = B| [|]() [S]
Pr(S - - 2o) Pr(S u) I(;
= (Y; Zo) + (1-11)1)))) 21)
Similar argument could be used to show that Z) = (I + (1- u)I(A: Z1). So by construction we now find a randomized transformation Z g(X) such that (ul(Y; Zo) + w))(Y; 21), ul( Zo) (1 - u) (A; Z)) E Rcr.
B.2 PROOF OF THEOREM 4.1
We proceed to provide the proof that the optimal value of (5) is the one given by Theorem 4.1 Theorem 4.1. The optimal solution of optimization problem
[(Y; HY) Ayia H(A).
Z.((A:))=0
Proof. For a joint distribution D over (X, A.Y) and function X' + Z, in what follows we use g:D to denote the induced distribution of D under 9 over (Z, Y). We first make the following claim: without loss of generality, for any joint distribution 9z over (Z, A, Y), we could find (Zo, A', Y") ~ 9: DD and deterministic function f. such that Y = [(A,, Zo. S) where S (O, 1), S L. (A', Zo) and T(Y'; 2') 2 T(Y; 2) with Z' (Zo. S). To see this, consider the following
construction:
A', Zo ~ D), S~ (0,
Let (a, 2, 5) be the sample the above sampling process and construct
Y' = [1 If B|Y A a, Z z/,
(0 Otherwise.
Now is easy to verify that (Zo, A', Y') ~ Dr and Pr(Y' ='= u, Zo 2) E A a, Z z]. To see the last claim, we have the following inequality hold:
I(Y: I(Y;; Zo. S) 2 I(Y; Zo) I):
Now upper bound 2); we have
I(Y; H(Y) H(Y Z))
hence it suffices to lower bound H(Y Z). To this end, define
Da {2,6 E (0, 1) 2(0, = 1}, D = {z,8 E (0, f(1,2,5) = 1}.
Then,
Pr((z,e) E Do) = Pr([[0,2,,) = 1)
-Pr(f(0,2,)) 4
= -Pr(f(A,2,)) = A= 4=0) 0)
Prr(Y 0).
Analogously, the following equation also holds:
Pr((z,e) Di) Pr(Y 1 A A=1)
12

---

Under review as a conference paper at ICLR 2021
Without loss of generality, assume that Pr(Y = A= Pr(Y 1 A 0), then
Pr((z,E) E DI Do) 2 Pr((z,e) E Pr((2e)) Db)
=|rr( = 1- Pr(Y = A 0)}-
But on the other hand, we know that if (2,4) E D1 Do. then f(), = 1 and f(0, 2,E) = 0, and this implies that Y AA, hence:
H 2) z H(Y S)
Pr((Z,E) D1 H( (z,E) D1)Do) + P Di)Do) H(Y (z,E) $ Di)
2 Pr((Z,E) E Di)Po) H(Y (z,E) E D))Do)
Pr((2,E) Do) (AA)
2 1Pr(Y = Pr(Y =1| A ((A).
which implies that
Z) & H(Y) Pr(Y = A -
Pr(Y = - -vi) (A).
To see that the upper bound could be attained, let consider the following construction. Denote a := Pr(Y = = 0) and [3 := Pr(Y= = = 1). Construct a uniformly random ~ U(0, 1) and then sample A independently from Z according to the corresponding marginal distribution of A
in DD. Next, define:
if <a 0 Z S
Y = 0 otherwise.
It is easy to see that Z 1 A by construction. Furthermore, by the construction of Y, we also have A. ~ D(A,Y Y) hold. Since I(Y; = H(Y) HY Z). we only need to verify 8, there are three
H(Y Z) = AYJA (A) in this case. Assume without loss of generality different cases depending on the value of Z:
Z In this
matter what the value of A, we always have Y == 1. Z > 3: In this case no matter what the value of A, we always have Y = 0.
a 7 S 3: In this case Y A, hence the conditional distribution of Y given 7 (a,,3) is equal to the conditional distribution of A given Z E (a, 3). But by our construction, A is independent of Z, which means that in this case the conditional distribution of A given
Z E (a, 38] is just the distribution of A.
Combine all the above three cases, we have:
HY 2) = Pr(Z S a)- HY Z S a) + Pr( B) H(Y Z + < < <65)) HIY a a<
0 0 +0+0+13-00 al (AA a< 3)
| A1 Pr(Y = 1 A = 0) H(A)
AAYJ (A),,
which completes the proof.
B.3 PROOF OF THEOREM 4.2
Theorem 4.2. The optimal solution of optimization problem / (A; Z) = ((AY))
min =)
Proof. First, realize that H(Z) I(Y: = (Y) by constraint. Furthermore, also know
that 0 < H(Y A) & H(Y = -
= O, which means H Z, A) = 0. With
these two observations, we have:
I(A; Z) = H(Z) H(Z A)
2 H(Y) H(Z A)
2 H(Y)- H(Y, 2 A)
H(Y) H(Y [ AY) Z,A)
H(Y) - H(Y (A)
T(A:Y).
To attain the equality, simply set = fy (X) = Y. Specifically, this implics that 1-bit sufficient to encode all the information for the optimal solution, which completes the proof.
13

---

Under review as a conference paper at ICLR 2021
C MISSING PROOFS IN REGRESSION (SECTION 5
C.I CONVEXITY OF RLS
Analogous to the classification setting, here we first show that the feasible region Rys is convex:
Lemma 5.1. RLS is convex.
Proof. Let Zi = (X) for i E {0, 13 with corresponding points (Var B|Y Z:I, Var E Z.)) RLS- Then it suffices if could show for Vu E [0, 1], (u Var E[Y Zu
+ (1 u) Var B
|
21], a Var [[A| Zol) + (1 - u) Var E Zil) E RLs as well.
We give constructive proof. Due to the symmetry between A and Y, will only prove the result for Y, and the same analysis could be directly applied to A as well. For any E [0. let U ~ ( 1), the uniform distribution over (0, 1), such that U 1 (Y,A). Consider the following randomized transformation Z:
Zo
If S u.
Z
(16)
1
otherwise.
To compute Var B|y 2]. define K := E| 2]. then by the law of total variance, we have:
Var Z] = Var = E\Var(K U)] + Var E[K] U].
We first compute Var [|[ | U]:
Var E[K U] Var VEr / U1]
Var U]
(The law of total expectation) Y U)
[Y
O.
On the other hand, for [ K U)], we have:
B[Var(K) U'] = Pr(U = 0) Var(K U = 0) + Pr(U = 1). Var(K U ==11 =1
u Var K U 0) + (1 -u) Var(K K U 1)
= u Var E(Y Zo] + (1 u) Var E[Y Z1].
Combining both equations above yields:
[,] + (1 u) Var B|Y [1]. Similar argument could be used to show that Var E[A | Z] u Var E[A Zo] + (1- w) Var E[A ] So by construction we now find a randomized transformation Z = =xX) such that
ElY Z] = u Var E[Y
(u Var E| Zo] + (1-uj u) Var Z1]. u. Var E[A Zo] (1 u) Var E[A [1]) Ris.
which completes the proof.
C.2 PROOF OF THEOREM 5.1 AND THROREM 5.2
In this section, we will prove Theorem 5. and Theorem 5.2
We will provide proofs to both theorems in a generalized noisy setting, i.e., longer assume the noiseless condition that the corresponding theorems in the noiseless setting follow as special case. To this end, we first re-define
(x) == E X
(17)
(X) == LEAA X]
(18)
and fV E H.. We reuse the notations a, y to denote
(x) E| X] (y, (X))) (x) E[A[X] (a, p(X)).
(19)
(20)
It is easy to that the noiseless setting is indeed special case where Y E|Y XX, A = E[A[X] almost surely.
For readers' convenience, restate the Theorem 5.1
below:
14

---

Under review as a conference paper at ICLR 2021
Theorem 5.1. The optimal solution of optimization problem (00) is upper bounded by
2y, Ea) (a, a)
Var(A) (a, y)
v))
max Var =/
Var B| Z S Var(Y)
(a,a)
(a, v)-
(11)
The following theorem is the generalized version of Theorem
5.1
in noisy setting:
Theorem C.1. The optimal solution of optimization problem
upper bounded by
(2 Σa)
Var(E[A|X]) (a, y) (a,a) a)²
u (a. y). (21)
max Var =[A
Var EY Z I
Var (ar(B[
(a, a)
easy to see Theorem i. an immediate corollary of this result: under the noiseless assumption, we have Var(E[Y X)) = Var(Y) and Var(B[A[X]) = Var(A).
Proof. Using the law of total expectation,
E Z E
E
Z
E[Y 2 p(X 2) dx.
Since Z 9(X) is function of X, we have Z 1 Y X, so E X, - E|Y X] = fy
Therefore,
E[y X, 2] p(X 2) dx
xx
(x( p(X () dx
(X) z/.
Hence,
Var(E[y 2)) = Var(E[[((X) Z))-
(22)
Therefore,
Var
Z] Var(E[ff (X) Z])
= Var (y, (XX) Z]
Varly, (Xx Z]}
(Linearity of Expectation)
= (u. Cov Cov(El (X) Z], ((p( 2l))).
Similarly, for A= (a, ((X)), we have:
Var E[A| Z (a, (ov(E(((X) Z),E(((X) Z))a).
To simplify the notation, define == (ov(BlppX ((p() of total variance, it is easy to verify that 0 V maximization problem could be relaxed as follows:
2]). Then again, by the law Cov (p (X), ((X)). Hence the original
max Z
(y. Vz),
subject to 0 0 V 1 E, (a, Vo) = 0.
To proceed, we first decompose y orthogonally w.r.t. a:
+ yll
where y is the component of y that is perpendicular to and واl is the parallel component of y to Using this orthogonal decomposition, we have vV:
(y. Vy) ((yta + ylle), tg- + vl
= (y- Vyda) < to Eyda)
(V1/2gla=0) 0)
(V Σ).
where the equality above can be attained by choosing V so that the corresponding eigenvalues of V along the direction of a coincide with those of Σ. Note that this is also feasible since the constraint
15

---

Under review as a conference paper at ICLR 2021
of eigenvalues being 0 only applies to the direction yll which is orthogonal to y To complete the proof, realize that the vector a could be constructed as follows:
y-" (I agag )y,
where = a/|lall the unit vector of a. The last step is to simplify the above equation as:
wyta Eyta,) ((I agd ) E(I anoz) )y)
2(v, Ea)
Var(E[A x]) (a.1) (a, a)²
) (a, y),
-Var(B[y x7)
(a,a)
by using the fact that Var(B[y XJ) (y, Ey) and Var(B[A X]) (a, Ea).
To show when the equality is attained, let V be the optimal solution of (??). which could be con- structed by first eigendecomposing 2 and then set all the eigenvalues of 2 to whose corresponding cigenvectors are not orthogonal to a. It is worth pointing out that V is positive semidefinite but not necessarily invertible. Nevertheless, we could still define the projection matrix of V that projects to the column space of V as follows:
Pv- V*VVVV
where Qf denotes the Moore-Penneee pscudoinverse of matrix Q. With Pv-, it is easy to verify that the optimal transformation given by such that
B[p(X) 2] = Pv-)p(X).
To see this, we have:
Cov(Elp(X) Z], E(p(() Z]) Varllp((X) [
Var()v-((X))
Pv Varls)(X))
Pv.EPPt. V",
completing the proof.
Next, we will prove Theorem 5.2
restated below:
Theorem 5.2. The optimal solution of optimization problem 12 is lower bounded by
Var(Y) (a, w)²
min Var 2
Var E[A Z]
(13)
(y. v)
The following theorem is the generalized version of Theorem 5.2 in noisy setting:
Theorem C.2. The optimal solution of optimization problem 12 is
Var Var(E[Y|[]) (a, ya,
min
Var [[A Z
(23)
2,Var B (|
(g. y)
is easy to see Theorem 5.2 is an immediate corollary of this result: under the noiseless assumption, we have XY) VYr(Y) and Var(B[A|X]) = Var(A).
Proof. Due the symmetry between Y and A, here only prove the first part of the theorem. As in the proof of Theorem 5.1 we have the following identities hold:
Var E[A Z| = (a, Cov(E((p(X) Z], ((p()) Zl)a),
Var EEY
Z] (y. (o. Blp(x) Z])y).
Again, let V == Cov (X) follows:
Z]. [[(((X
Z]) that we can relax the optimization problem as
min
(a, Va),
subject to
V Σ, (v. Vv) Var(Y) (y. Ey).
16

---

Under review as a conference paper at ICLR 2021
To proceed, we first decompose orthogonally w.r.t yz
a = at + allar
where a is the component of a that is perpendicular to and ally is the parallel component of to y. Using this orthogonal decomposition, we have VV:
{a, Va) ((a+v +a V + +all))
2 llyy Vall"),
(V > 0),
where the equality could be attained by choosing V such that V1/2 = 0. On the other hand, is clear that
allv = yo) yo:
where yo = / |y|| is the unit vector of y. Plug allv = (a, yo) yo into (al v, Valls) with the fact that
(y. Vy) Var ( (y, En), we get
(a M Valluy- = Var(E[ (a,y)²
(v. y)²
Again, to attain the equality, should first construct the optimal V matrix by cigendecomposing Σ. Specifically, this time we set all the eigenvalues of whose corresponding eigenvectors are perpendicular to y 0. Similar what argue in the proof of Theorem 5.1 V is positive semidefinite but not necessarily invertible. Nevertheless, we could still define the projection matrix of V* that projects the column space of V follows:
py- == V*(V"=V
where Qt denotes the Moore-Penrose pseudoinverse of matrix Q. With Pv-, it is easy verify that the optimal transformation given by such that
(xp(X) Z = Pv-
To this, have: Cov(Elp(X)) | Elx)) Z]} Var 0
Var(Pv- (o())
Pv- (x)(
Pv.EPt. V*,
completing the proof.
C.3
PROOF OF THEOREM 5.3
To prove Theorem 5.3 we first introduce the following decompositions of the loss functions:
The following lemma is refined version of the Data-Processing Inequality, which gives exact characterization of the Bayes optimality gap for a given Z. Recall that the Bayes error is [xrVar X]]. Lemma C.1 (I2² Error Decomposition).
[y[ Ex[Var[ = Ez Var (E [ (2) 2 0.
(24)
Similarly,
Ez [|
Ex Ex [ar[A Ez Var (E [||]] Z 2 0.
(25)
Proof. Since Z g(X) is function of X, we have p(y]=r) plyz 2). or equivalently, (Y 1 X)
By law of total variance,
Var(Y 2) = Ex (Y + Var (E [, Z]
= Ex [Var(Y|x)]z] Var E X [Z)
17

---

Under review as a conference paper at ICLR 2021
Taking expectation over Z,
Ex (ar(Y|z)
ExEx [Var(Y] + Ez Var (E [ (Z)
ExEz [Var(Y 2 + Ez Var (E [ (2)
Exx Var(Y]X) + Ez Var [E| (2),
where the last equality is due to the law total expectation.
The following lemma is direct consequence of the law of total variance. Lemma C.2 (L² Invariance Decomposition).
Var(A) - Ez Var (Z) Var(E[A|2) 2 0.
We will prove generalized version of Theorem 5.3
without noiseless assumption, stated below:
Theorem C.3. The optimal solution of the Lagrangian has the following lower bound:
1 Var(B[A[x]) + Var(B[Y|x]) - v (AVa((B(A))))) Var(E(Y]|])) 42(a, Eny OPT(A) 2 + (a(Var(Y Var(A)).
When the noiseless assumption holds, we have Var(E[A[X]) Var(A), Var(E[Y||]) Var(Y). and [[[ar(Y| = O, hence the bound above simplifies to:
{ Var(Y) > Var(A) Var(A) Var(Y))² - 4A(a, En)
21
which is exactly Theorem
5.3
Proof of Theurem 5.3
By Lemma C.1 and Lemma C.2
we can decompose the objective as:
[E[arr(Y AE 2a)(
= [E[[Vrr(Y|Z)) ([[aa(Y + A(Var(A) ([Va((AA2)) + (E[Var(Y||X]] Var(A))
Ez Var (E Y X /Z) + Var(B[A|Z] + [E[Var(Y]X)) Var(A))
Since V.Var(Y X)] A Var(A) does not depend on we will focus on the first terms:
min 2=g(X)
Ez Var (E 2) + Var(B[A|Z))
(26)
Recall that for the squared loss
fā(X) E[[
We will first simplify the objective in 26
We have
Var [ ()) = E Var (FF())ZZ,
(27)
and using the law of total expectation,
[(A B(AIX, [(AIIx ()
Since Z = x(X) is a function of X, we have 1 A|X, so E(A[X,)) = ={(AX) = f2(X).
Therefore,
B[A]Z]
XXXX)XXX22XX -(FA(X)2
Hence,
Var Var(E(A|Z)) Var(E1/((X)122
(28)
18

---

Under review as a conference paper at ICLR 2021
Now substitute 27
28
into
26). which gives the following equivalent form of (26):
min
Var Var (fi(()) + Var(BI52((3)122)
Z (x)(X)
In this case, the objective
becomes:
E Var (JF(X)
+ A Var(([(((((
(29)
E Var ((v, (or((( (ar (
+
(30)
(w, I Cov(s<(X), Z)y)+
(31)
A(a, Cox/E
(32)
By the law of total covariance,
E Cov(ip(X), (xX) Co
Let V = Cov Cov Cov((p(X), (0 (X)) =
which satisfies E = V = 0. Then, finding the feature
transform Z gXX) that minimizes 32 is equivalent to:
min V=Coo((lpc(x)2]]]]e=xx
(y. (E V)y + X/a Va)
The key technique of our lower bound is to relax the constraint V Cov(Bl)(XX)2 by the semi-definite constraint 2 V = 0.
min (y, vE
V)y) + Ma, Va)
This is an SDP whose optimal solution lower bounds the objective 26 Moreover, we can show that
there is simplified form for the SDP optimal solution using eigenvalues and eigenvectors:
(v. (2 - V)y} + A(a, Va)
= -y, Ey) (V, Aaa -yy²)
= -yy, Ey) - 1/2 11/2 (Xaa" "
Note that / > := --////E-17 > 0. and R = E1/2 yyy ) is a matrix with rank at most
When the matrix R is positive definite or negative definite. the minimum is achieved at Q = 0 or Otherwise, the only possibility is that R rank-2 matrix with one positive eigenvalue and one negative eigenvalue. By Von-Neumann's 's trace inequality,
R)
o. (R)oaaitt1)())
Since oi (R) > 0 = (2(R) = 0d ( = 0 > σal ( R)) and 0 S aa(Q)= < 1, we have
R) > (R) σ. (>' (Xaa" - -y )/
The minimizer is
Q ww T V Σ 2/w 101/2
where is the unit eigenvector of R with eigenvalue (R). By Lemma C.3
oa(R)= _ (aa, Ea) (y. En) / (2(a, Ea) + (y. Ey) 4a En)
Therefore,
OPT(A) = (y. (Σ - V)y) + Maa Va) + (E|V)r(Y| - A (ar(
(v. Ey) aaa(F) (R) + (E[Var
Var(A)
1
M(a Ea) + (y. En) / (A(a, Ea) wy 2n) 41 Eny
2
+ (E[Var(Y Var(A))
2 (a[[E( + Var(E -
(A Vara(((())) + Var(E - 4A(a, Ey)
+ (L[[Var(Y [)] Var(A))
Hence have completed the proof.
19

---

Under review as a conference paper at ICLR 2021
C.4 EXPLICIT FORMULA FOR EIGENVALUES
The following lemma is used the in the last step of the proof of Theorem 5.3 to simplify the expression
involving (R) = 0x(21/2 (Aaa" yy" )
Lemma C.3. Let Σ1/2 (Xaa" -yy² / then the eigenvalues of R are
σ1 (R) 2
M/a, Σa) - (y. Ey) + v (A(a, Σa) + (y. Σy))² 4X(a, Σy)
1
oa(R) (R) 2 Maa, Σa}
-y: Ey) v (M(a, Ea) (y. Enj)² 4N(a, Ey)²
o2(R)
0d-1(R) =0
Proof. Since (R) v Fank(Aaa* - yuj²) S 2, has at most two non-zero eigenvalues 0 (
and (a( Notice that
(r(R) Σ - (o)))
d
tr((²)) Σ
of(()) = of( + +
We can write tr(R) and tr R²) explicitly:
tr(R) = X Atr(E 1/2 an 112) tr//1//22 / _1/22 = M(a, Σa) - (v. Ey)
tr(R²)= = (={{))2(\aa yy TE(Xaa" )
=u/(2//2 (2²(a (²(aa"Ea)ad Ea)aa" >aa" T "y((acy)) - Ay T Ea(yZaa) - (a" (("aaaaaa)) 221
=X?(aT - 22(a" Ey)² + (x=TD)) En)²
Therefore,
(1 + +o((H) = Ma, Σa) (y, Enj
a1 (P)Raaa(R) = 2 ((01 + ( (o) +()()
= M(a Σy)² - Ma, Ea) (y, Σv)
Thus 01 (R) and (R) are the roots the quadratic equation:
x² (A(a, Σa) - (y, Σn) ar + X(a, En) M(a, Ea) (y. En) = 0
We complete the proof by solving this quadratic equation.
C.5 ACHIEVABILITY LOWER BOUND
In the proof of Theorem 5.3 we showed a lower bound on the tradeoff via an SDP relaxation.
Therefore, the lower bound is achievable whenever the SDP relaxation is tight. We state this regularity condition on (X,+
Definition C.1. (X (p) is called regular, if for any positive semidefinite matrix M: E > M > 0,
there exists Z (XX), such that
= M
Theorem C.4. When (X, (p) is regular, the lower bound in Theorem 5.3 is achievable.
Proof. From the proof of Theorem 5.3 we can see that if there exists g(X), such that = wl/ 1//2
where w is the unit eigenvector of R with eigenvalue a (R), then the equality is achievable. is easy to see that
Σ x Σ ww T 2
ww
Therefore, choosing M = 1/2 ww /21/ the definition of regularity guarantees the existence of Z. Hence have completed the proof.
20

---

Under review as a conference paper at ICLR 2021
A sufficient condition the regularity of (x) is the Gaussianity of (xX), in which case choosing gXX) as linear transform sufficient:
Theorem C.S. (X, sp) is regular if ((X) follows Gaussian distribution.
Proof. Note that when (X) Gaussian, (x((),, (X)) jointly Gaussian for any Rixd Let Z = Lxp(X), then the conditional distribution y [Z is Gaussian, with mean and covariance
Blc(X)]Z] "L"((""") (o
=
Hence,
E
= EL'("")'
We will prove that for any E 2 M ž 0, there exists linear transform L, such that M ELT (LEL""))--LL
Consider the eigenvalue decomposition of Σ -/ 1/2 DU, rank(M),
Rkxd E lg D invertible. Then, let 1-11/22 1/2 we have
LEL" D-1
- = D 1-1/2
EL (LEI") -I = M.
Therefore we have completed the proof.
We conjecture that this regularity condition holds for more general distributions beyond Gaussian.
21


Reviews:
[{"review_id": "hbmz8M2IBlf", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper formulates the problems of learning in invariant representations as a min-max game, exploring tradeoffs between accuracy and invariance of these representations via a geometric plane analysis. Specifically. the paper considers both classification (cross entropy loss) and regressions settings (squared loss).The related minimax problem is separable in the sense that for any fixed feature transformation, the optimization for the min and max agent are independent of each other, resulting is a simple, concise representation of the resulting optimization problem.  The symmetric nature of this description allows for a geometric description of the feasible set in regards to the actions of both min-max agents and the paper goes on to provide some characterizations of external points and other properties (e.g. convexity) of this region/set. The paper also derives a tight lower bound that for the Lagrangian form of accuracy and invariance.\n\nThis is an interesting theoretical take on the issue of exploring tradeoffs between accuracy and invariance of representations, but I am not sure to what extend this theoretical analysis provides actionable insights about real world problems (e.g. what doe convexity of the feasible set imply for algorithmic fairness?). The paper would be much more convincing if it offered some concrete use of these ideas in examples/applications. \n\nAlong these lines, I am not sure about whether some modelling assumptions are always satisfied in practice. For example, it seems to me that in the analysis both Y/A tasks are considered to be either jointly classification or jointly regression tasks but in many of the examples put forward it could be the Y is a continuous variable e.g. salary where A could correspond to a discrete one e.g. gender. What does this framework imply in this case?  How sensitive is it on the choice of the loss functions?\n\nOverall, this geometric approach seems like a cute idea but at least in its current form maybe it is not overly insightful for the concrete applications that it aims to model. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "YoWUBrmWS9", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work studies a fundamental and important problem in representation learning, the tradeoff between accuracy and invariance of the learned representations. For classification and regression problems, the paper analyzed the inherent tradeoffs by providing a geometric characterization of the feasible region in the information plane, where it connects the geometric properties of this feasible region to the fundamental limitations of the tradeoff problem. The work is well written and well presented overall, but the implication of the result is not very clear and the work lacks experimental validations.\nBelow are some major comments/concerns from the reviewer:\n\n1. One of the major questions the reviewer has is what is the implication of the result. In the other words, given the characterization of the feasible region in the information plane, including its boundedness, convexity, and extremal vertices, how can the result in this paper improve representation learning? What is the right balance of classification and invariance? It seems quite vague in the current form of the work.\n\n2. Does Assumption 4.1 and Assumption 5.1 hold in general? Does the mapping f always exist, or under what condition does the mapping f exist? More discussion about the assumptions is needed. It is not how stringent the assumptions are in practice.\n\n3. Another question the paper does not address, is how to construct g(X) to achieve certain points on the information plane.\n\n4. Although the result is theoretical, it could be better if the authors provide some experimental justifications, which is completely missing.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ThJ2hzsetDe", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors extend the information bottleneck by Tishby to also include an additional auxiliary variable that represents either domain index or private information. Using this generalined IB the authors study tradeoffs/fundamental limtis on achievalbe accuracy in predicting labels while maintaining invariance against the auxialiary variable. \n\nThe proposed approach seems promising but much more work is needed: \n- it is unclear how the proposed frameworl relates precisely to plain vanilla IB. I feeld that convential IB could be obtained somehow when using the auxiliary variable to identify individual traning samples instead of larger domains. \n\n- how can the obtained characterization be used ? can one use these characterizations to verify sub-optimiality of existing methods for privacy-preserving ML or algorithmic fairness \n\n- how can the proposed model be turned into practical algorithms that (nearly) achieve the fundamental limits/tradeoffs. \n\nminor issues: \n- pls indicate the optimization domain for every optimization problem (e.g. (1)) \n- unclear what is meant by \"could be the identity of domain index in domain adaptation,\" \n- \"..Lagrangian has the following lower bound:..\"\n- \"Evidently, the key quantity in the lower bound...\" why is this evident ? ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies an interesting information-theoretic trade-off between accuracy and invariance by posing it as a minimax problem. The results are of theoretical nature. However, the implications of the results are not clear. Also, the model/assumptions authors consider are not completely justified. Therefore, the paper at this stage is not recommended for acceptance. However, I highly encourage the authors to improve upon their existing work and resubmit to the next ML conference. 
Decision: Reject