On the Fundamental Trade-offs in Learning Invariant Representations
Authors: Bashir Sadeghi
Vishnu Boddeti
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Utility
Invariance
Trade-off
Kernel Method
Global Optima

Abstract: Many applications of representation learning, such as privacy-preservation, algorithmic fairness and domain adaptation, desire explicit control over semantic information being discarded. This goal is often formulated as satisfying two potentially competing objectives: maximizing utility for predicting a target attribute while simultaneously being independent or invariant with respect to a known semantic attribute. In this paper, we \emph{identify and determine} two fundamental trade-offs between utility and semantic dependence induced by the statistical dependencies between the data and its corresponding target and semantic attributes. We derive closed-form solutions for the global optima of the underlying optimization problems under mild assumptions, which in turn yields closed formulae for the exact trade-offs. We also derive empirical estimates of the trade-offs and show their convergence to the corresponding population counterparts. Finally, we numerically quantify the trade-offs on representative problems and compare the solutions achieved by baseline representation learning algorithms.

On the Fundamental Trade-offs in Learning Invariant Representations
Anonymous Author(s)
Affiliation
Address
email
Abstract
Many applications of representation learning, such as privacy-pen preaccy-rreervationn, al- gorithmic fairness and domain adaptation, desire explicit control over semantic information being discarded. This goal is often formulated as satisfying two po- tentially competing objectives: maximizing utility for predicting target attribute while simultaneously being independent or invariant with respect to a known seman- tic attribute. In this paper, identify and determine two fundamental trade-offs between utility and semantic dependence induced by the statistical dependencies between the data and its corresponding target and semantic attributes. We derive closed-form solutions for the glohal optima of the underlying optimization prob- lems under mild assumptions, which in turn yields closed formulae for the exact trade-offs. We also derive empirical estimates of the trade-offs and show their convergence to the corresponding population counterparts. Finally, we numeri- cally quantify the trade-off's on representative problems and compare the solutions achieved by baseline representation learning algorithms.
10
11
12
14
Introduction
16
Real-world applications representation learning algorithms often have to contend with objectives beyond predictive performance. These include cost functions pertaining invariance (e.g., to photometric or geometric variations), semantic independence (e.g., w.r.t to age or race for face recognition systems), privacy (e.g., mitigating leakage of sensitive information (.), algorithmic fairness (e.g., demographic parity (2), and generalization across multiple domains 3 to name a few.
18
20
21 At its core, the underlying goal of the aforementioned formulations of representation learning is to
22 satisfy two competing objectives, extracting as much information necessary to predict target label (e.g., face identity) while intentionally and permanently suppressing information pertaining to 24 desired semantic attribute 8 (e.g., age, gender or race). When y is independent s, one can learn a representation that is independent of s with no loss of performance, i.e., no trade-off exists between 26 the two objectives. However, when the two attributes y and are correlated, attaining semantic independence will necessarily reduce the performance of the target predictor, i.e., there is trade-off between the two objectives. The trade-off is unknown yet is important for understanding the limits of existing and future representation learning algorithms that involve semantic independence constraints.
23
28
30 Let /(x) be a representation of input data æ, and f(-) be the encoder (see Fig a)). Invariant learning requires that prediction of the target label, ÿ gy (z) be independent of semantic attribute i.e., ÿj s for all possible downstream target predictors gy This independence condition satisfied if and only if (iff), the representation z is independent of i.e., Jl 8. Therefore, Invariant representation learning (IRL) seeks to optimize two objectives: i) the degree of dependence between data representation and semantic attribute and ii) target task utility. These two objectives can be combined into one, with a parameter 7 controlling the trade-off.
31
32
34
36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

Unily
s
Intrasille
Data Infeasible Label Fezstblc
a
x
y
Increare Unitty
Fonsblle
f(-)
gr (.)
dep(z,8) 8)
8
dep(/(
(a)
Inarcase Independencee
(b)
Figure 1: (a): Generic frame work of invariant representation learning (IRL) where attributes and y are caused by a latent factor and are not marginally independent. Under this setting, IRL. seeks representation 2 = f(x that contains enough information for downstream target predictor gr (.) while being independent of the semantic attribute s. Consequently, the prediction ÿ gy (z) will also be independent of s for any downstream predictor (-).). (b): We identify and determine two different fundamental trade-offs between utility (i.e., the performance of target task predictor) and dependence measure dep(z, 8) by an optimal learner in the hypothesis class of coael-mmasurable functions. Trade-off I. is induced by the joint distribution of the labels Pye- Trade-off D is induced by the joint distribution of the data Paya- Trade-off a relaxed version of trade-off obtained by either using surrogate measure of dependence, e.g., adversarial learning [3] or from a constrained hypothesis class [4, or from using sub-optimal optimization algorithms.
37 In this paper, we identify and analytically determine two fundamental trade-offs in the invariant representation learning setting introduced above, namely Data Space Trade-Off and Label Space 39 Trade-Off. These trade-off's are illustrated in Figure (b) and formally defined next.
Definition 1. Data Space Trade-Off arises from the statistical dependence between the target attribute 41 and the semantic attribute s conditioned on the given input data æ. When the learner's 's hypothesis
42 class contains all mossuamea function& we have:
inf F(-) measurable
{1 (1-T) inf gy mensarable
En.yy
Cr (I)))) w)] + dep(/(ax), 8)}
(1)
where f(-) is the encoder that extracts representation from æ, gy (-) predicts ÿ from the repre- sentation z, Ly (-.)) is the loss for the desired task of predicting the task label y. The function dep(.,) :) 2 is parametric non-parametric measure of statistical dependence i.e., dep(q, r) 0 means and r are independent, and dep(q, r) > means q and r are dependent with larger values indicating greater degrees of dependence. The scalar
44
46
[0, 1) is a hyper-paramett that controls the trade-off between the two objectives, with 7 = 0 being the standard approach that enforces no enforces representation
48
49
independence the attribute 8, while
be independent of s.
50 Including all measurable functions in the hypothesis class of the encoder f(-) and target predic-
51 for gy(-) ensures that the best possible trade-off is included within the feasible solution space.
52 For example, when T = and (..)) is the mean-squared error, the optimal Bayes estimator, gy (f())) [y ær] is reachable. This definition corresponds to the trade-off D in Figure (b).
54
Definition 2. Label Space Trade-Off arises by ignoring the data æ and is purely determined by the statistical dependence between the target feature y and the semantic attribute Such trade-off can 56 be defined as:
inf xEL
{ (1 (T)
inf BY (-) measurable
Exey (g) va) dep(2, $)
(2)
57 where L the space all random vectors with finite second-order moment (i.c., E. [|| < oo) on the same probability space in which the joint variable (s. y) comes from.
More specifically, consider square-integrable Borel- measurabee functions for boundedness.

---

59
This definition corresponds to the optimal trade-off obtained by an ideal representation 2 that is not constrained by the learnability of the encoder f(.). For example, if 0. the ideal representation is perfectly aligned with the target label i.e., 2 = and gr(-) ()) is the identity function, perfect prediction of target attribute feasible. Therefore, this trade-off corresponds to the best trade-off that any combination of data 2. and learnable encoder f()) can aspire to. This definition corresponds to the trade-off L in Figure (b), and it necessarily dominates the Data Space Trade-Off D.
60
61
62
63
64
65
Contributions: i) Identify two fundamental trade-off's in invariant representation learning. ii) Obtain closed-form solution for the corresponding optimization problems, and consequently determine the trade-offs exactly. iii) Provide consistent empirical closed-form solution for the representations that achieve optimal trade-offs. iv) Numerically quantify the trade-off's defined here and compare them to those obtained by existing solutions.
66
67
68
69
Implications:
Our closed-form empirical estimators for the optimal representations lend themselves to practical invariant representation learning algorithms. ii) Theoretically elucidating and empirically
71
72 quantifying the intrinsic limits of invariant representations will enable researchers and practitioners alike to identify the feasible and infeasible solution space for the trade-off's and lead to informed development and deployment of optimal IRL methods. iii) Our theoretical analysis sheds light on the uilitt-semantic independence trade-off, the role of statistical dependency between target label y, the semantic attribute s, and the input data æ, and the hypothesis class adopted for the learners.
73
74
75
78
2
Related Work
78 Trade-Offs in Representation Learning: While there are abundant empirical approaches for the
79 representation learning applications considered in this paper, to the best of our knowledge, there
80 is no prior work that exactly characterizes and empirically quantifies the trade-offs inherent to representation learning with semantic independence constraints.
81
82 Prior work primarily sought to either obtain lower or upper bounds or characterize the extreme points of the trade-off in specific contexts such as fair representation learning. For instance, (5] uses information theoretic tools and characterizes the utility-fairness trade-off in terms of lower bounds when both y and s are binary labels. Later (6) provided both upper and lower bound for the binary labels. By leveraging Chernoff bound (7] proposed construction method to generate an ideal representation beyond input data achieve perfect fairness while maintaining the best performance on target task for equalized odds. In the case of categorical features, a lower bound on trade-off has been provided by [8. The notion of Pareto optimality was used by P to minimize the maximum possible error among sensitive attributes where both target and sensitive features are categorical. In contrast to this body of work, our trade-off analysis is applicable to dileiiidieenionall discrete and/or continuous attributes where we find the exact optimal trade-offs.
83
84
a5
86
87
88
89
90
91
93
The only prior work that investigates fundamental trade-offs a general setting where both y and can be continuous or discrete features, are 4 and [10). [4] considers only linear dependence between the representation and semantic attribute and proposed a closed-form solution for the -ailitys trade-off. Even though [00] considers non-linear dependencies, optimal losses have been derived only for the extremes of the trade-off (i.e., T - and > 1). In a more general setting where < r < 1, 10 only provides a lower bound on utility- intirriiie trade-off off through information plane analysis.
94
95
96
97
98
99
In contrast to the foregoing, we take a functional analysis approach and utilize covariance operator based measures of dependence that account for all non-linear dependence relations. We exactly characterize and quantify the unility-nvariaance trade-offs, while also providing a means to empirically estimate the encoder that achieves said optimal trade-off. Lastly, in addition to the Data Space Trade-Offt Off, we also introduce and determine the Label Space Trade-Off which is the idcal trade-off that any unrestricted learning algorithm can aspire to.
100
101
102
103
105
Invariant, Fair, Privacy-Prees Preserving Representation Learning: The basic idea of representation learning that discards unwanted semantic information has been explored under different contexts like invariant, fair, or
106
107
learning. In domain adaptation [I] 16
13), the goal is to learn
108
features that are independent of the data domain. In fair learning [14 15
18 19 20 21 22 23 24 25 26 27 4, the goal is to discard the demographic information that leads to unfair outcomes.
17
109
110
Similarly, there is a growing interest in mitigating unintended leakage of private information from
111
data representations (28] 29 I 30 31 vast majority of this body of work empirical in nature.
These methods implicitly look for single or more points in the trade-off between utility and faimess
3

---

113 and do not explicitly seek to characterize the whole trade-off front. Overall, these approaches are
114 not concerned (or aware) about the feasibility and limitations on the -illit-iivariance trade-off. In contrast, this paper determines the fundamental theoretical limits of controlling independence to semantic attributes, and proposes practical learning algorithms that achieve this limit.
115
116
117
Adversarial Representation Learning: Most practical approaches for learning fair, invariant, do- representations discussed above are based on adversarial repre- sentation learning (ARL). This learning problem is typically formulated as,
118
main adaptive or
119
inf SEHz
(11-7 inf Eu.y/ Ly (gr (f(())))))) ey
inf Ez,e [cs (s((((((()))))
(3)
asEH,
120
where Ls(:,)) is the loss function of hypothetical adversary g-(-) who intends to extract the semantic attribute through the best predictor within the hypothesis class H.. ARL is special case of the Data
122
Space Trade-Off in (1) where the negative loss of the adversary, Ey
inf Ez, Cs (gs(f()))) s)
123
However, this form of adversarial learning suffers from a fundamental drawback back as also noted in [32) The measure of dependence induced by ARL does not account
plays the role of
124
125
for all modes of non-linear dependence between and the representation z. The next theorem states this observation precisely,
127
Theorem 1. Let H. contain all Borel-measurable functions and .) be mean squared error (MSE) loss. Then,
128
inf Bi [Es( + E[s [ =[s)]. seEN,
E sup
129
This theorem implies that an optimal adversary does not necessarily lead to a representation = that is statistically independent of 8 (i.e., p[s|z) = p(s)), but rather leads to s being mean independent of representation z i.e., independence with respect to first order moment only. other words, adversarially learned measure of dependence is not a complete measure of dependence and hence does not account for all modes of non-linear dependence between two random variables. As such, ARL is inherently incapable of attaining the trade-offs achievable by complete measures of dependence.
130
131
132
133
3
Theoretical Results
136
3.1
Problem Setting
Consider the probability space F, PP), where Ω is the sample space, F is alagebbra on Ω, and a probability measure on F. We assume that the joint random vector (ax y: 8), containing the input data æ e Rd, the target label y e 12 and the sensitive attribute E R2, random vector on (2, F) with joint distribution Pays.
138
139
140
141
Assumption 1. We assume that the encoder consists of r functions in an Lu-universal RKHS (Ha, Kn (:, )) (e-g.. Gaussian kemnel), where L univeerrrsllity guarantees that H. can approximate any
143
function with arbitrary precision 34
144
Now, the representation vector be expressed
z = f(x) (z) fx())
E RR, f0) Hj = 1,....
(4)
145 where r is the dimensionality of the representation z. As discussed in Corollary 5.1 unlike common
practice where it is chosen arbitrarily, r itself is object of interest for optimization. We consider
147
general scenario where both y and s can be continuous or discrete, or one of y or s is continuous while the other is discrete. To do this, substitute the the target loss, inf E. [Cy (gr (z), 3)] in I
gy 149 with the negative of a non-parametric measure of dependence i.e., dep(z,, y). Furthermore, in
We defer the proof's of all lemmas, theorems and corollaries to the supplementary material.
"Many standard loss functions can be written in term of dependence measures (35) that capture all non- linear dependencies i., Ex, [Ly (f())) y)] x -dep(f(x), y). For example, the mean squared emror is proportional to 1 p(f(w), (a),20 y). where is the Pearson correlation coefficient, plausible dependence measure.

---

(x)(f()),
(-)))
f(:)
f(x)
(ov(f()),,..8)
(.(+)
Figure 2: Our IRL model consists of three components: An r-dimensional encoder f(.) in RKHS
Hz. ii) A measure of dependence that accounts for all kinds of linear or non-linear dependencies between the representation z and the semantic attribute s via the covariance between f()) and (s) where x is the input data and B, (.) belongs to RKHS Ha- iii) A measure of dependency between (()) and the target attribute y defined similar to the one for 8.
unsupervised settings, when there is target attribute y. the target dependence dep(z,, y) can be replaced with dep(z, æ), which implicitly forces the representation to retain as much information is necessary for reconstructing the input data This scenario is of practical interest when data producer aims to provide a representation of data that is independent of a desired semantic attribute for any arbitrary downstream task.
151
153
154
155
start by designing dep(z, 8). and dep(z. y) follows similarly. key desiderata of dependence measures is that they should be able to account for all possible non-linear dependence relations between the random variables (or vectors). Examples of such measures include information theoretic measures such as mutual information (c.g.. MINE (36) covariance operator based measures such as Hillert-Schmidt Independence Criterion (37. Constrained Covariance [38] and Kernel Canonical Correlation [39] The underlying principle behind the latter class of dependence measures is that finite dimensional spaces with non-linear dependencies behave as linearly dependent spaces when mapped appropriately to higher dimensional spaces. In this paper adopt the covariance operator based measures as our choice of dependence measure for analytical tractability.
157
159
161
163
Principally, and are independent iff Cov(a(z), (, (s)) is zero for all a(-) and B.(+) belong- ing to some universal RKHSs (38). Since z = f(x) and f(-) E Hys Cov(a())) Cov(a(f(z)) (. (s)). which necessitates application of kernel on top of another kernel. This limits the analytical tractability of our solution. However, as we argue below, is almost sufficient to consider transformation s, only, in which case it reduces to Cov(f(x), (s))) Let (H,, kg (;)))) )) be separable RKHSs of functions defined on Rdd and Rd,,, respectively. Consider
165
=
167
and (Ny. .)) the bi-linear functional,
170
h(.-)) He x H. + E2 hy B.) Cov
(5)
Assumption 2. We assume in the rest of this paper that the positive definite kernel functions are bounded, i.e..
172
Eyg (xr, m²) oo, (k, s)] 0o, and Eyylky v)) 80.
173
The assumptions in 6 guarantee that h(::-) ) in 5 is bounded [40] and therefore, invoking Riesz representation theorem (1). there exists unique and bounded linear operator Ean, such that
174
hf, Ba) = (f
(B,, EanI) vS E Has vB, E Ha.
175
Based h(:;-), we define the linear operator h : H.s
Rr as
Cov (f
(Ba, Ea fo fi
h (3,)
:
(Bs, Enw Se) Se)
176 The operator hy.s captures all modes of non-lineat dependence, since the distribution of a low- dimensional projection of high-dimensional data is approximately normal 42 43 In other words, 178 we assume that (f))), (s)) is an approximately Gaussian random vector.
By separable mean having countable orthonormal basis set.
5

---

179
Among the different dependence measures that have been defined through the covariance operator
180 we adopt the Hilbert-Schmide Independence Criterion (HSIC) 337 which is defined the Hilbert- Schmidt norm (HS-norm) of the covariance operator,
dep(2, s) == [ = Σ Ihy ( B.EUL
Σ 3.) J,EU,
(8)
where Un is countable orthonormal basis set for H.. Note that, based on this definition, if the distribution (3)),,.()) fails to be normal distribution, we end up measuring mean dependency of f(x) from which is still much stronger than the lincar dependency between # and [44).
185
185
Even under this assumption, empirically (Section 4 we observe that tradc-offs we obtain significantly dominate those from existing invariant representation learning algorithms.
187
The following Lemma introduces a well-defined population expression for dep(z, 8) in (8).
Lemma 2.
d)
Σ F F [B)(0) [5(2²) (s, (ar) (5 Bx, (8,)
-2 Em,
[5((z) Ea' (5)(0')) Ey Iki (8,, (s.
188
where (x, s) and (x', s') are independently drawn from the joint distribution Pas.
189
In practice, it is necessary empirically estimate dep(z, s), since the population distributions are typically unknown in most real-world scenarios.
181
Definition 3. Let D = { 81, y1), ... (æn, 8n, yn)} be the training data, containing n i.i.d. realizations from the joint distribution Pasy- Using, the representer theorem [45), it follows that
192
f(x) Og ka (e..x). ... (I x)]| where + E R"*= is a free parameter matrix.
193
194
Lemma 3. Let an empirical estimation of covariance be
22
(L,())))) Σ ((a)))..8s.)
n2
195
Then, the empirical estimator of dep(z, s) is given by
depomp (z, = n² OK,
(9)
where Kg K. E RR are Gram matrices corresponding to Hi and H.. respectively, H 196
111" and L, is full column-rank matrix in which L,L K, (Cholesky factorization). This empirical estimator in 9 has a bias of O(n -1) and a convergence rate of O(n (n12))
197
198
The population and empirical dependence measures between z and y i.e., dep(z, y) and d y). respectively, can be defined and obtained similarly.
200
201
3.2
Trade-Off D
We now turn the the optimization problem corresponding to the trade-off D in Recall that z f (x) is r-dimensional, where the dimensionality r is a free variable. common desiderata of learned representations is that of compactness (46) in order avoid learning representations with
203
205
redundant information where different dimensions are highly correlated with each other. Therefore,
going beyond the assumption that each component of f(-) (i.e., fy)+)) belongs to T
207
RKHS Hz. we impose additional constraints on the representation. Specifically, we constrain the search space of the encoder f(-) to learn disentangled representation (46) follows,
208
4, = (110)
fs. He. Cov= (z)) + + f)),, = (10)
209
where the regularization term HH... encourages orthogonality and boundedness, which in turn forces the representation to be compact or non-redundant. Such disentangled representations have

---

been studied in the context of independent component analysis (ICA) [39]. Now, the optimization problem in reduces to, 212
sup [(f(x)) == (1- (1-)) (edp((dd)) OST<L, SEA,
(1I)
where as justified earlier the target loss function inf E ylyy (fr((())) y)] is substituted by 213
fv
dep (x), y). Fortunately, the above optimization problem lends itself to closed-form solu- tion as given by the next theorem.
215
216
Theorem 4. A solution to the optimization problem in
11 is the eigenfunctions corresponding r largest eigenvalues of the following generalized problem
217
(1 T)
> 2ix
(12)
218
where Man and Eye are the covariance operators defined and Di and Vig are the adjoint operators of Eew and Eye, respectively.
220
(i.c., no semantic independence constraint imposed), the solution in Theorem resembles a supervised version of ICA in [39] which is essentially a kernelized
Remark. If the trade-off parameter
221
222
dimensionality reduction supervised by the target attribute y. On the other hand, if r + 1 (i.e.,
223
utility is ignored and only semantic independence is considered), the solution in Theorem is the eigenfunctions corresponding to the negative eigenvalues of Σ Esz. which are the directions that are least explanatory of the semantic attribute 8.
224
An empirical version of is the following optimization problem
jemp (f(x)) = (1 T) dep (f fx)) y) T dep emp (f(z), 8)} SEA,
sup
05
(13)
227 where dmp (f (a)) and de (f(x), y) are given in
228
Theorem 5. Consider the Cholesky factorization K = L L where Lu is a full volumn-rant
229 matrix. A solution to
13 is
Niw (211 hiw (zn. " Opp
fopt
where OPT = U (Lx) and the columns of U are eigenvectors corresponding to largest eigenval- ues, '1. :., >r of the following generalized problem.
231
[ K, -7K,--K,,) Lx,) u X X HL + mT
(14)
where y is the regularization parameter from (0) and the supremum value of 13 is j== Az.
233
Corollary 5.1. Embedding Dimensionality; A useful corollary of Theorem 5 is optimal embedding
234
dimensionality:
sup sup jomP SEA,
dep (f(x), y) dep (f()).((())) })}
235
which the number of positive eigenvalues of the generalized eigenvalue problem in To intuitively examine this result, consider two extreme cases: i) If there is no semantic independence constraint (i.e., 7 0), adding more dimensions to the optimum will not harm the representation power of z. ii) If we only care about semantic independence and ignore the target task (i.c., - 1). the optimal r would be equal to zero, indicating that null representation the best for discarding all semantic information. In this case, adding more dimension to will necessarily violate the semantic independence constraint. More discussion can be found in the supplementary material.
236
237
238
239
241
242
In the following Theorem, we prove that the empirical solution converges to its population counterpart. Theorem 6. Assume that Ka (-x-) and ky(-,)) are bounded by one and f (x:) is bounded by A for any k 1...., J' and i I,...,m for which (fi,..,, fr) A.. For any and 8 1,
243
244
245
with probability at least - 8, we have
1og(6/8) a
O (
sup ((f()) sup Jemp (f(x)) S SrMV feA.
feA-
where 0.22 < < 1 is a constant.
'The term 'solution' in any optimization problem in this paper refers to global optima.
7

---

247
3.3
Trade-Off L
248
We recall that label space trade-off arises when the representation z ideal and is free be designed optimally i.e., it does not necessarily depend on the input data æ or the encoder's 's hypothesis class. However, we assume that the representation is a direct effect of the target and sensitive variables (y
249
250
and s). Following [47. we use an additive noise model as
= = (y, 8) + e, Il y. 11
(15)
where fe(:,)) : TR x Rdd - R is a Borel-measurable function. Following Section 3.1 252
we deploy dep((z, 2, y), defined similar to dep(z, 8) in (8 as proxy for the loss function
inf (x,y(C((rr())) (z), Recall that, the desired optimization problem given in (2). Instead
254
gy Hy
255 of directly optimizing over z E T.2, we optimize over all Borel-measurable functions fz(:-) by ignoring e since it is independent of both y and s:
sup fr. (v.s)
(L- dep( (y. s). y) T dep((f((y.s))
(16)
257
where (y s) defined similar A, in (10) by using (y. s) instead of in the definition. Recall that A, (y. s) ensures that z will not contain highly correlated (entangled) dimensions, and thus be
258
259
minimally redundant or maximally compact.
Remark. The optimization problem in (16) and its empirical counterpart can be solved similar to that of trade-off D in Theorems and where æ replaced with (y, 8).
261
262
3.4
Trade-Off F
263
Here we define and discuss the trade-off achievable by practical realizations of representation learning algorithms with either fairness, invariance or semantic independence constraints.
254
285
Definition 4. Feasible Space Trade-Off arises from the statistical dependence between the target
288
feature y and the sensitive attribute s conditioned on the given input data æ. the choice of hypothesis
257
class for the learners involved, and the choice of dependence measure adopted. This setting can be formalized as,
268
inf {(1-7) inf Fun.y (Ox u) + dep(s(m),,)) s)) OsT<l, E96
(17)
FEHL,
269
where Hy and Hl are the hypothesis class for the encoder network and target predictor, respectively,
(.)) denotes the loss function of target task, and dep( s) is parametric non-parametric
271
surrogate measure of dependency quantifying the dependency between representation vector z =
f(x) and the sensitive attribute
273
This setting corresponds the trade-off F in Figure [bb,, and is necessarily dominated by the Data Space Trade-Off D. Multiple factors may lead to such sub-optimal trade-offs. These include, hypothesis classes that are not universal RKHSs (e.g.. g.. considered the case where Hi universal,
274
275
276
but H. and Hy are linear RKHSs), the surrogate dependence measure (f)(f((),.)) s) does not account for all non-linear dependencies (e.g., 3 2 21 4 which consider adversarialyy learned dependence measures), sub-optimal optimization of (17 in terms of achieving only local optima but not the global optima (e.g., when the hypothesis class is deep neural networks that optimized through stochastic gradient descent, or through stochastic gradient descent- ascent in the case of adversarial representation learning 3 21 2), and combinations thereof.
277
278
279
280
281
4
Numerical Estimation of Trade-Offs
282
283
In this section, we demonstrate the practical utility of the analytical results developed in the paper and validate theoretical insights. For this purpose, we design an illustrative toy example that conforms to the setting studied in the paper and numerically quantify the tradc-off's that we introduced. Experimental validation on more tasks can be found in the supplementary material.
285
286
287
Consider the following Gaussian mixture model from which we generate 4000, 2000, and 2000
(N(m. Σ) + +N(m'))) m 1], m' [1,1], 1]. Σ diag (0.10.....) 0.1
U2]
8

---

12
Teabs of) AlL-12
005
dep 15 x)
(a)
(b)
(d)
Figure 3: (a): A mixture of two Gaussians which generates the input data as a U1, the sensitive
attribute as 8 = v/. and the target attribute as y = [11, uš]. (b): Two fundamental trade-offs, and D, together with two baseline feasible trade-off's F, ARL optimized with SGDA [21] and global optima of ARL with a linear RKHS 44. (c), (d): The learned embedding for T = and r = 0.5, respectively. An invariant representation should collapse 1 i.e., the two colors should fully overlap with each other in the embedding. The overlap is partial for T = 0.5 and as T + 1, the optimal representation is zero.
independent samples for training, validation and testing, respectively. Figure Bla) shows the test 289 samples where the samples generated with m and m' are in blue and red, respectively. The input data
288
230 x set to v1 (the first entry of v), the sensitive attribute s is vf, and the target attribute y is [vi, vž] In this problem both input data and target attribute are dependent on the sensitive attribute. We choose learned
292
all three RKHS Hz. Hy. and Hl to be Gaussian, which is universal RKHS. The optimal for the trade-off D through the closed-form solution in Theorem for different invariance parameter values T in [0, 1). Then, this optimal embedding is fed to a target task predictor which a multi-layer perceptron (MLP) with two hidden layers, and 4, 8 neurons and optimize the meean-squared error (MSE). The x-axis a normalized version of the dependence measure used in our optimization, while the y-axis quantifies utility normalized [0, as exp(-MSE). The same procedure is implemented for trade-off L, except that the imput data is v, instead of x. These trade-offs are shown in Figure ()). We choose the input data to be v instead of (y,, s) for trade-off L since (3/ s) is fully generated from v and therefore, v perfectly explains (y, 8). For r 0 and r = 0.5, the optimal embeddings are illustrated in Figure (c) and (d), respectively. Since the sensitive attribute is only related to en, an invariant embedding should collapse the corresponding dimension and cause the two colors to overlap with each other.
294
296
298
300
302
303
304
We make the following observations, (a) Trade-off L dominates trade-off D as expected. (b) The trade-offs F obtained by the baselines dominated by trade-off D. Adversarial representation learning B [21] uses sub-optimal optimization (SGDA), while Spectral-ARL. [4] uses global optimum solution but restricts the hypothesis class in (3) to linear RKHS. As such, the baselines are
306
308
unable to match the global optimal solution of (13). and (c) At r = 0.5 the embedding does indeed
309
collapse v) to extent leading to partial overlap between the two mixtures.
5
Conclusions and Societal Impact
310
311
This paper developed the theoretical underpinnings for identifying and determining the fundamental trade-offs and limits of representation learning under competing objectives. These trade-offs included i) label space trade-off which solely induced by the statistical relation between target task and semantic attribute; ii) data space trade-off which is due to the statistical dependence between the input data and both target and semantic attributes. Further, we found closed-from solutions for the global optima, both the population and empirical versions, for the underlying optimization problems, and thus quantify the trade-offs exactly. Our results shed light on the regions of the trade-off that are feasible or impossible to achieve by learning algorithms. Numerical results suggest that commonly used adversarial representation learning based techniques are unable to reach the optimal trade-offs.
312
313
315
316
317
319
320
The theoretical results in this paper are useful for algorithmic fairesss, privacy- privacy-preservee preservation, and domain generalization applications of representation learning. Such systems are being widely deployed in a variety of practical applications: search engines, social media, law enforcement, healthcare, consumer devices, financial and judicial risk assessments, face analysis, and many more. Therefore, providing theoretical limits of performance is critically important for informed framing of regulatory policies, deployment of such solutions, and gaining societal trust. As such, we do not anticipate any adverse socictal impacts from this work.
321
322
323
325

---

References
327
328
[1] P. Roy and V. N. Boddeti, "Mitigating information leakage in image representations: A max- imum entropy approach," in IEEE Conference Computer Vision and Pattern Recognition, 2019.
330
331
[2] D. Madras, E. Creager, T. Pitassi, and R. Zemel. "Learning adversarially fair and transferable
332
representations." arXiv preprint arXiv:1802.06 06009, 2018.
338
[3] Y. Ganin, F. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and V. Lempitsky, "Domain-adversan
334
training of neural networks," The Journal of Machine Learning Research, vol. 17, no. 1, pp. 2096-20300 2016.
335
338 [4] B. Sadeghi, R. Yu, and V. Boddeti, "On the global optima of kernelized adversarial representation learning," in JEEE International Conference on Computer Vision, pp. 7971 2019.
337
338 [5] H. Zhao and G. J. Gordon, "Inherent tradeoff's in learning fair representations," arXiv preprint ar:iv: 190.00896 2019.
339
340
[6] D. McNamara, C. S. Ong, and R. C. Williamson, "Costs and benefits of fair representation learning," in AAAI/ACM Conference on AI, Ethics, and Society, pp. 263-270, 2019.
341
[7] S. Dutta, D. Wei, H. Yueksel, P.-Y. Chen, S. Liu, and K. Varshney. "Is there trade-off between fairness and accuracy? a perspective using mismatched hypothesis testing," " in International Conference on Machine Learning. pp. 2803-2813, PMLR, 2020.
343
[8] H. Zhao, J. Chi, Y. Tian, and G. J. Gordon, "Trade-offs and guarantees of adversarial representa- tion learning for information obfuscation," " arXiv preprint
346
2019.
347 [9] N. Martinez, M. Bertran, and G. Sapiro. "Minimax pareto fairness: A multi objective perspec- tive," in International Conference on Machine Learning, pp. 6755-6764, PMLR, 2020.
349
[10] H. Zhao, C. Dan, B. Aragam, T. S. Jaakkola, G. J. Gordon, and P. Ravikumar, "Fundamental limits and tradeoffs in invariant representation learning," " arXiv preprint 1011133012.00713, 2020.
350
[1]] Y. Ganin and V. Lempitsky, "Unsupervised domain adaptation by backpropagation." in Interna- tional Conference on Machine Learning, 2015.
352
353
354
[12] E. Tzeng, J. Hoffman, K. Saenko, and T. Darrell, "Adversarial discriminative domain adaptation." "
355
in IEEE Conference on Computer Vision and Pattern Recognition, 2017.
356
[13] H. Zhao, S. Zhang, G. Wu, J. M. Moura, Costeira, and G. J. Gordon, "Adversarial multiple
357
source domain adaptation." Advances in Neural Information Processing Systems, vol. 31, pp. 8559-8570, 2018
358
359
[14] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel, "Fairness through awareness," in Innovations in Theoretical Computer Science Conference, pp. 214-226, 2012.
[15] S. Ruggieri, "Using t-closeness anonymity to control for non-discrimination.. " Trans. Data Priv., vol. 7, no. 2, pp. 99-129, 2014.
382
363
[16] M. Feldman, S. A. Friedler, J. Moeller, C. Scheidegger, and S. Venkatasaurammaninn "Certifying
364
and removing disparate impact," in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 259-268, 2015.
365
366
[17] F. Calmon, D. Wei, B. Vinzamuri, K. N. Ramamurthy, and K. R. Varshney, "Optimized pre- processing for discrimination prevention," in Advances in Neural Information Processing Systems, pp. 3992-4001, 2017.
387
388
389
[18] R. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork, "Learning fair representations," " in International Conference on Machine Learning. pp. 325-333, 2013.
370
371
[19] H. Edwards and A. Storkey, "Censoring representations with an adversary," arXiv preprint
372
arXiv: arXiv:1511.05897, 2015.
[20] A. Beutel, J. Chen, Z. Zhao, and F. H. Chi, "Data decisions and theoretical implications when
374
adversarially learning fair representations." arXiv preprint 1rXiv:/707.000: 2017.
375
[21] Q Xie, 7. Dai, Y. Du, E. Hovy, and G. Neubig, "Controllable invariance through adversarial feature learning." in Advances in Neural Information Processing Systems, pp. 585-596, 2017.
10

---

377
[22] B. H. Zhang, B. Lemoine. and M. Mitchell, "Mitigating unwanted biases with adversarial learning." " in AAAI/ACM Conference on Al. Ethics, and Society, 2018.
378
379
[23] Song, P. Kalluri, A. Grover, Zhao, and S. Ermon, "Learning controllable fair representa- tions." in International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
[24] M. Bertran, N. Martinez, A. Papadaki, Q. Qiu, M. Rodrigues, G. Reeves, and G. Sapiro, "Ad- versarially learned representations for information obfuscation and inference," in International Conference Machine Learning. 2019.
382
[25] E. Creager, D. Madras, J.HH. Jacobsen, M. A. Weis, K. Swersky, T. Pitassi, and R. Zemel, "Flexibly fair representation learning by disentanglement" in International Conference on Machine Learning (ICML), 2019.
385
[26] F. Locatello, G. Abbati, T. Rainforth, S. Bauer, B. Schölkopf, and O. Bachem, "On the fair- ness of disentangled representations"" in Advances in Neural Information Processing Systems, pp. 14611-14624, 2019.
388
[27] J. Mary, C. Calauzenes, and N. El Karoui, "Fairess--waar learning for continuous attributes and treatments," in International Conference on Machine Learning, pp. 4382-4391, PMLR, 2019.
381
382
383
(88) J. Hamm, "Minimax filter: Learning preserve privacy from inference attacks," The Journal of Machine Learning Research, vol. 18, no. 1, pp. 4704-4734, 2017.
394
385
[29] M. Coavoux, S. Narayan, and S. B. Cohen,
neural representations of text,"
398
arXiv preprint arXiv: 09408, 2018.
397
[30] T. Xiao, Y.-H. Tsai, K. Sohn, M. Chandraker, and M.-H. Yang, "Adversarial learning of privacy-preserving and task-oriented representations," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 12434-12441 2020.
398
389
400
[3]] M. Dusmanu, L.. Schönberger, S. N. Sinha, and M. Pollefeys, "Privacy-preservinn visual feature descriptors through adversarial affine subspace embedding." in IEEE Conference on Computer Vision and Pattern Recognition, 2021.
402
403
[32] E. Adeli, Q. Zhao, A. Přefferbaum, E. V. Sullivan, L. Fei-Fei, J. C. Niebles, and K. M. Pohl, "Representation learning with statistical independence to mitigate bias," in IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 2513-2523, 2021.
405
406
[33] V. Grari, O. E. Hajouji, S. Lamprier, and M. Detyniecki, "Learning unbiased representations via re' nyi minimization,"" arXiv preprint arXiv:2009.05. 200900333. 2020.
[34] B. K. Sriperumbudur, K. Fukumizu, and G. R. Lanckriet, "Universality, characteristic kernels and rkhs embedding of measures.," " Journal of Machine Learning Research, vol. 12, no. 7, 2011.
409
410
[35] D. Greenfeld and U. Shalit, "Robust learning with the hilbert-schmidd independence criterion," in International Conference on Machine Learning, pp. 3759-37666 1769, PMLR, 2020.
[36] M. I. Belghazi, A. Baratin, S. Rajeshwar, S. Ozair, Y. Bengio, A. Courville, and D. Hjelm, "Mutual information neural estimation," in International Conference on Machine Learning,
413
pp. 531-540, PMLR, 2018.
415
[37] A. Gretton, O. Bousquet, A. Smola, and B. Schölkopf, "Measuring statistical dependence with hilbert-schmidt norms," in International Conference on Algorithmic Learning Theory,
416
417
pp. 63-77, Springer, 2005.
418
[38] A. Gretton, R. Herbrich, A. Smola, O. Bousquet, and B. Schölkopf, "Kernel methods for measuring independence," Journal of Machine Learning Research, vol. 6, no. Dec, pp. 2075- 2129, 2005.
419
420
421
[39] R. Bach and M. I. Jordan, "Kernel independent component analysis." " Journal of Machine Learning Research, vol. 3, no. Jul, pp. 1-48, 2002.
422
[40] K. Fukumizu, F. R. Bach, and A. Gretton, "Statistical consistency of kernel canonical correlation analysis.." Journal of Machine Learning Research, vol. 8, no. 2. 2007.
424
425
[41] E. Kreyszig, Introductory functional analysis with applications, vol. 1. wiley New York, 1978.
426
[42] Diaconis and Freedman, "Asymptotics of graphical projection pursuit," The Annals of Statistics, pp. 793-815, 1984.
11

---

428
[43] P. Hall and K.-C. Li, "On almost linearity of low dimensional projections from high dimensional data," " The Annals of Statistics. pp. 867-889, 1993.
429
430
[44] A. Rényi, "On measures of dependence." " Acta Mathematica Academiae Scientiarum Hungarica, vol. 10, no. 3-4, pp. 441-451, 1959.
[45] J. Shawe- Taylerr N. Cristianini, al., Kernel methods for pattern analysis. Cambridge university press, 2004.
433
434
[46] Y. Bengio, A. Courville, and P. Vincent, "Representation learning: A review and new per- spectives," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 8, pp. 1798-1828, 2013.
436
437
[47] J. M. Mooij. J. Peters, D. Janzing, J. Zscheischler, and B. Schölkopf, "Distinguishing cause from effect using observational data: methods and benchmarks," The Journal of Machine Learning Research, vol. 17, no. 1, pp. 1103-1204, 2016.
438
439
Checklist
440
441
1. For all authors...
442
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s
443
contributions and scope? [Yes] See Section 3.2 and Section 3.3 Partieularly, see
444
Theoremgaand Theorem 5
(b) Did you describe the limitations of your work? [Yes] See the discussion above equation
446
(5) and below equation (8).
(c) Did you discuss any potential negative societal impacts of your work? [N/A] See
Section 5]
448
449
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
450
451
2. If you are including theoretical results...
452
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3.1 Particularly, see Assumption [ and Assumption 2 and discussion above equation (5) and below equation (8)
454
455
(b) Did you include complete proofs of all theoretical results? [Yes] See supplementary material for the proofs of all Lemmas and Theorems.
456
457
3. If you ran experiments...
458
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplemen-
459
460
tary material.
461
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4 and supplementary material.
462
463
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Only one of the baseline methods, ARL, requires running multiple times with different random seeds. The error bar of ARL results is given in supplementary material.
465
466
467
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] This paper is not about computational complexity and/or execution time.
469
470
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
471
(a) If your work uses cxisting assets, did you cite the creators? [Yes]] See supplementary material for the citation to the publicly available repository that we used.
473
(b) Did you mention the license of the assets? [N/A]
474
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
We not using any new assets.
476
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [N/A]
12

---

478
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
479
480
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
482
489
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
484
485
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "uETiSclqhBt", "reviewer": "Reviewer_9fPS", "summary": "This paper studies the utility-invariance trade-off problem and characterizes closed-form expressions for two types of trade-offs. This is an important problem since it's relevant to privacy, fairness and representation learning. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "This paper studies the utility-invariance trade-off problem and characterizes closed-form expressions for two types of trade-offs. This is an important problem since it's relevant to privacy, fairness and representation learning. The results are theoretically sound and the paper is mostly well-written.\n\nHowever, there are a few aspects that the current version of the work is lacking, detailed below.\n\nComparison to [10]: The authors did not provide much comparison with the most closely related work [10]  (the only relevant part I found is line 96-98).  Both of these two papers work on very similar problem with only a few small differences in the choice of loss functions, and the results are similar from high level as well (and they even have nearly identical titles). While some comparison will be mentioned in this review, I think it's necessary to include a thorough comparison in the future version of this work.\n\nClarity: This paper is mostly well-written. However, there are some mathematical details that are not clearly explained. \n\n(1) In equation (10), the definition of the constrained function space $A_r$ involves an additional (tunable) parameter $\\gamma$, whose role is not discussed in detail (apart from mentioning it as a trade-off parameter), nor is there any theoretical/empirical suggestion for how to choose the parameter. Furthermore, the main result (Theorem 4) holds regardless how $\\gamma$ is chosen - which appears to be strange since $A_r$ itself depends on $\\gamma$.  \n\n(2) In Definition 1 & Definition 2, the trade-off objectives are stated as a linear combination of (a) prediction loss on y and (b) dependence between z and s. However, in the main theorem (Theorem 4), the part (a) is replaced with dependence between z and y. While the authors mentioned in line 213 and line 129-134 some explanations about this change, this not only causes confusion for the reader, but also (to some extent) hides a flaw in the reasoning about the design choice of loss, detailed below.\n\nChoice of the loss function and Technical difficulty: As mentioned above, the authors replaced the target loss with the dependence (HSIC) loss. But this choice is poorly justified - while it was mentioned in Theorem 1 that the MSE loss does not guarantee statistical independence, this reasoning only applies to the sensitive feature ($s$) part, where one hopes to achieve independence with The same reasoning does apply to the target loss $y$ part, where the goal is to make accurate prediction, rather than strong dependence. \n\nFurthermore, the improvement over [10] mentioned in line 99-102, are mostly due to this change - the original formulation in eqn (1) appears to be much more difficult to deal with comparing to the setting in theorem 4, while theorem 4 bypasses this difficulty and only require simple eigenvector/eigenvalue analysis. The weaker characterization in [10] (only lower bounds are provided there) involves significantly more challenging analysis, for which I suspect that the authors would encounter similar challenge if they didn't made this simplification.\n\nExperiments: The experiment section is very short and only toy dataset  (mixture of two Gaussians) is included. It is also unclear how the theory would impact the applications mentioned in the paper like domain adaptation and fairness.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "lqY1Jm4pNLw", "reviewer": "Reviewer_aNqn", "summary": "This paper studies the tradeoffs between accurately predicting the target and being invariant with respect to a known sensitive attribute in representation learning. When the features are functions in a RKHS, the paper derives closed-form solutions to the tradeoff optimization program. Finite sample guarantees are also given.", "questions": "", "limitations": "", "rating": 3, "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": "The paper tries to establish theoretical foundations for invariant representation learning, which is an important direction. The proposed method improves over baseline ARL. However, there are several major weaknesses:\n\n1. The objective of optimization isn't well motivated. Why should one use HSIC as the dependence measure instead of mutual information?\n2. The feature model is very restrictive, i.e. orthogonal kernel functions (eq 10) and the theory doesn't seem to be able to generalize to more commonly used models like neural networks.\n3. The tradeoffs D, L, F seem to only differ in hypotheses classes. I don't see how the distinctions are meaningful.\n4. No experiments on realistic datasets to demonstrate the usefulness of the theory.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "fLrEVzgBYPu", "reviewer": "Reviewer_zJby", "summary": "This paper identifies and determines two fundamental trade-offs between utility and semantic dependence induced by the statistical dependencies between the data and its corresponding target and semantic attributes. The authors derived closed form expressions for the global optima of the proposed optimization problems (for Tradeoff D, Tradeoff L and Tradeoff F among others), exposing the nature of the tradeoffs. Some convergence guarantees and experiments on synthetic data are also provided. ", "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": "Strengths:\n\n+ Learning invariant representations and quantifying the tradeoffs between target and semantic attributes is an important topic in machine learning today in view of privacy protection and fairness. \n\n+ The authors' formulation of these issues in terms of the mathematical optimization problems in Section 3 is rather neat. The fact that the solutions can be obtained in closed form is also very nice. It provides neat insights.\n\nWeaknesses:\n\n- The experimental section is rather weak. I would have expected a more extensive set of experiments, possibly on real-life data to be done. Given the extensive theory that has been developed, it is surprising that the authors have not exploited the theory more on real-world (or at least larger synthetic) datasets to corroborate for example the tightness of the bounds in Theorem 6. This is a missed opportunity. It would have been nice to experiment with various kernels. The dependence on the parameter \\tau is also not well explained. It seems like a hyperparameter that is important in real-life applications.  \n\nHaving said this, I must confess that I'm not an expert in this area of invariant representation learning.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper may have some impact in the study of fairness, privacy and other contemporary areas in machine learning. ", "review_text": "", "extra_scores": {"ethical_concerns": "NIL", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "VuJ48dKerA", "reviewer": "Reviewer_3Zq1", "summary": "This paper identifies and determines two tradeoffs between utility and dependence in learning invariant representations. The main contributions claimed by the authors are two folds: 1). closed-form solution for the global optima of the underlying optimization problem; 2). empirical estimates of the tradeoff terms that converge to the population counterpart in the large data limit. \n", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "Overall, I find this paper a little bit hard to follow. I think the overall presentation would be significantly improved if the authors could justify the claims made in the paper. For example, to motivate the problem, the authors claimed between Line 133-134 that \"As such, ARL is inherently incapable of attaining the trade-offs achievable by complete measures of dependence\". I personally think this is an overstatement, since the conclusion of Theorem 1 only applies to the mean-squared error in the regression setting, and conclusion of this theorem completely fails as long as one uses either the variational form of Wasserstein or TV distances as the score function of the discriminator. Hence I felt it is inappropriate to say that ARL is inherently incapable of attaining the trade-offs. In fact, it's just a matter on the choice of your adversarial loss function and the hypothesis class of your adversarial.  \n\nPerhaps my main concern is the lack of detailed comparisons with previous works and the overstatements of the contributions made in this work:\n-   The authors mentioned in the related work that \"In contrast to this body of work, our trade-off analysis is applicable to multi-dimensional discrete and/or continuous attributes where we find the exact optimal trade-offs.\" It seems to me that the conclusion in this paper only holds for continuous random vectors where the space of both S and Y are R. To see this, following the discussion between Line 164 to Line 170, the authors used Cov(\\alpha(z), \\beta(s)) where \\alpha and \\beta are in some RKHS. Per the original paper on HSIC [1], this criterion is for univariate continuous random variables, right?  \n\n[1]. Kernel Methods for Measuring Independence, https://www.jmlr.org/papers/volume6/gretton05a/gretton05a.pdf\n\n-   A detailed comparison with a previous work is missing. In particular, this work makes the normality assumption of the joint distribution (Line 176 to 178) in the feature space and furthermore an independent assumption on the learned features (Eq. 10) in order to derive the tradeoff result. Similarly, [2] also makes the normal assumption but is free of the disentanglement assumption. In terms of technical results, it appears that the results in [2] (in the regression section) give similar bounds, i.e., the optimal representations are given by the top two eigenvectors of the kernel covariance matrix, and the authors also show that under the Gaussian assumption their lower bound becomes tight. I was wondering what's the difference between the results of this paper to that of [2]? Given the close relationship between these two works, the authors should make a clear cut comparison w.r.t. the bounds in [2]. So far such a comparison is completely missing. \n\n[2]. Fundamental Limits and Tradeoffs in Invariant Representation Learning, https://arxiv.org/abs/2012.10713\n\n-   The authors claimed that their closed-form empirical estimators lend themselves to practical invariant representation learning algorithms. Where are the proposed invariant representation learning algorithms in the paper? It seems to me that the experiments are mainly used to verify the theoretical results in the paper. This is totally fine, but the claims made in the introduction does not reflect what's going on in the experiment section.  \n\nFurthermore, there are several claims in the paper that are not justified and do not seem correct to me, including:\n-   Line 33, the authors claim that \"This independence condition is satisfied if and only if (iff), the representation z is independent of s\". I don't think this is true. To see a simple counterexample, it's certainly possible that z is not independent of s while the predictor \\hat{y} being independent of s -- simply making \\hat{y} to be a constant function of s. \n\n-   Line 50-51, the authors claim that \"Including all measurable functions in the hypothesis class of the encoder f(·) and target predic51 tor gY (·) ensures that the best possible trade-off is included within the feasible solution space.\" I was wondering why this is true? Presumably, even if one works with all the Borel-measurable functions, these functions are still determnistic mappings. Would this be sufficient to achieve all the feasible solutions? \n\n-   Line 192-193: could the authors further elaborate on why this statement is true? \"Using, the representer theorem [45], it follows that f(x) = ΘE[kx(x1, x), · · · , kx(xn, x)]T, where Θ ∈ R r×n is a free parameter matrix.\"\n\n===============================================================\n\nI have read the authors' responses as well as other reviews. Please see my detailed comments below. Overall, I am not convinced by the response and I will adjust my rating from 4 to 3. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "28ShGqYE92k", "reviewer": "Reviewer_q5TL", "summary": "The paper proposes an MMD-style regularizer on the representation learned by a classifier in order to enforce invariance to a sensitive attribute. This is similar to existing work on invariant representation learning with an adversary, but using a measure of feature correlation which enforces more invariance than just the first-order statistics.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "I think this paper is decent, but not quite at the point where it's ready for publication.\n\nThere's quite a bit of overclaiming in the earlier writing when compared to the actual contribution presented. For example, the title of the work mentions the \"tradeoffs and limitations\" in invariant representation learning, and the earlier sections prepare the reader for some sort of new insight. However, upon a full read through, it is apparent that the tradeoffs and limitations to which the title refers is just the existing discussion on the \"bottleneck principle\" of Tishby et al, and the inherent tension between expressivity and invariance of a set of features when the label and sensitive attribute are correlated. This Pareto frontier is well-discussed in the literature (off the top of my head, see: \"The cost of fairness in binary classification\", \"Costs and Benefits of Wasserstein Fair Regression\" [which is concurrent with this submission, but further demonstrates that this perspective is not unique], in addition to all the works cited by this paper [8, 9, 10]).\n\nInstead, the contribution of this paper (and what I believe the writing should more clearly focus on) is an MMD-like regularization penalty which under appropriate conditions correctly captures higher-order non-linear dependence between the learned features and the sensitive attribute in question. Theorem 1, while making an interesting observation about the limitations of adversarially invariant representation learning, is not the first time this has been pointed out (the authors acknowledge this). Furthermore, this is not an inherent fault of adversarial representation learning as claimed; rather, it is inherent to losses which are evaluated pointwise, such as MSE (the example used in the theorem statement). If, for example, we were to introduce a \"critic\" to regularize the distribution divergences (for example, to estimate mutual information or Wasserstein divergence), then adversarial representation learning would be able to identify higher-order dependencies. This is partially acknowledged, but much later (line 277), and it should be made clear earlier.\n\nUltimately, **I think the theoretical results for the proposed penalty term are valuable; I just think that there is too much focus on everything else, which is not newly presented in this work.** I should also note that I'm not very familiar with existing MMD-like divergence penalties for feature invariance. This general idea is being used in a lot of places: I've seen many such regularizers proposed, particularly recently, for OOD generalization [e.g., \"Causally-motivated Shortcut Removal Using Auxiliary Labels\", \"An Information-theoretic Approach to Distribution Shifts\", there are many more but I'm just picking a few to demonstrate that I'm not making this up]. As such, the overall novelty of this penalty term is questionable to me---it is possible that I'm just unaware of the previous literature.\n\nBeyond these issues, the earlier notation of this work is very problematic:\n* Are **x**, **y**, **z**, **s** fixed (after drawing the training distribution) or not? They are initially presented as random, but then the discussion of the label tradeoff treats the **x, y, s** as fixed (such that we can define the ideal **z** for each observation). And then **z** is presented as both fixed (chosen to be ideal for the particular training observation) *and* random (assumed to have a distribution with bounded second moment)?\n* As far as I can tell, in the space of arbitrary measurable square-integrable functions f, shouldn't the label tradeoff be exactly equivalent to the data tradeoff? If **z** is assumed to have bounded second moment, then wouldn't the function f defined as f(**x**) = **z** satisfy square integrability? In which case, there always exists a function which achieves the \"ideal\" representation, regardless of the data distribution... I think the difference between the two in the experiments is actually the result of the \"function tradeoff\" idea, where such an f is undiscoverable.\n* In the proof of Theorem 1, the distributional expectation of the loss is equated with the empirical loss over the training set. How does this make sense? The statement itself is trivial but it was surprisingly difficult to fully understand due to the notation.\n\nOf course it's possible I'm misunderstanding all of these points, but I would argue that this is due to extremely inconsistent notation. I did not check the proofs in great detail because my functional analysis is not very strong, but these notational issues worry me.\n\nI'm also unclear on why learning the \"label-tradeoff\" representation is at all meaningful? It requires access to the true label and sensitive feature, so of course it's useless in practice. I guess instead it's intended to show the gap between \"label-tradeoff\" and \"data-tradeoff\", but as I mentioned above I think this is actually an issue of estimation (finding the correct featurizer *f*) rather than one of approximation. In other words, I believe the \"L -> D\" gap as presented by the paper is actually a \"D -> F\" gap, and that the \"L -> D\" gap does not exist. If the authors disagree, it would go a long way to clean up the notation here.\n\n\n--------------\n**Update after rebuttal**\n\nThe authors have clarified some of my confusion, but I still feel that the emphasis of this work is too much on existing material and the material which is new is unclear and confusing, to the point that it requires significant revision. I am maintaining my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sure", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes various tradeoffs in invariant representation learning. During review, several concerns have been raised including missing comparisons with closely related work, clarity and exposition, and some misunderstandings at a conceptual level. These concerns were not adequately addressed during the discussion phase. In the end, there was a consensus amongst the reviewers that this paper is not ready for publication in its current form.
Decision: Reject