On Characterizing the Trade-off in Invariant Representation Learning
Authors: Bashir Sadeghi
Sepehr Dehdashtian
Vishnu Boddeti
Venue: Accepted by TMLR ()

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 formulated as satisfying two objectives: maximizing utility for predicting a target attribute while simultaneously being invariant (independent) to a known semantic attribute. Solutions to invariant representation learning (IRepL) problems lead to a trade-off between utility and invariance when they are competing. While existing works study bounds on this trade-off, two questions remain outstanding: 1) What is the exact trade-off between utility and invariance? and 2) What are the encoders (mapping the data to a representation) that achieve the trade-off, and how can we estimate it from training data? This paper addresses these questions for IRepLs in reproducing kernel Hilbert spaces (RKHS)s. Under the assumption that the distribution of a low-dimensional projection of high-dimensional data is approximately normal, we derive a closed-form solution for the global optima of the underlying optimization problem for encoders in RKHSs. This yields closed formulae for a near-optimal trade-off, corresponding optimal representation dimensionality, and the corresponding encoder(s). We also numerically quantify the trade-off on representative problems and compare them to those achieved by baseline IRepL algorithms.

Published in Transactions on Machine Learning Research (12/2022)
On Characterizing the Trade-off in Invariant Representation Learning
Bashir Sadeghi
sadeghibee msu. edu sepehr @ msu. edu vishmu @ msu. edu
Sepehr Dehdashtian
Vishnu Naresh Boddeti
Department of Computer Science and Engineering
Michigan State University
Reviewed on http:////ppeeeeee//////////////a
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 formulated as satisfying two objectives: maximizing utility for predicting target attribute while simultaneously being invariant (independent) to a known semantic attribute. Solutions to invariant representation learning (IRepL) problems lead to a trade-off between utility and invariance when they are competing. While existing works study bounds on this trade-off, two questions remain outstanding: 1) What is the exact trade-off' between utility and invariance? and 2) What are the encoders (mapping the data to a representation) that achieve the trade-off. and how can we estimate it from training data? This paper addresses these questions for IRepLs in reproducing kernel Hilbert spaces (RKHS)s. Under the assumption that the distribution of a low-dimensional projection of high- dimensional data is approximately normal, we derive closed-form solution for the global optima of the underlying optimization problem for encoders in RKHSs. This yields closed formulae for a near-optimal trade-off, corresponding optimal representation dimensionality, and the corresponding encoder(s). We also numerically quantify the trade-off on representative problems and compare them to those achieved by baseline IRepL algorithms. Code available at htttts://tttttttt com/ com/human anal smaalssss/trrrdes ieviiiiiiinn wew.attreeeeeeeeteeeiiiiii. learning
1 Introduction
Real-world applications of representation learning often have to contend with objectives beyond predictive perfor- mance. These include cost functions corresponding to invariance (c.g.. to photometric or geometric variations), se- mantic independence (e.g., to age race for face recognition systems), privacy (e.g.. mitigating leakage of sensitive information (Roy& & Boddeti 2019)). algorithmic fairness (e.g., demographic parity (Madras al. 2018)), and gener- alization across multiple domains (Ganin et al. 2016), to name few.
At its core, the goal of the aforementioned formulations of representation learning is to satisfy two competing objec- tives: Extracting as much information necessary to predict a target label Y (c.g., face identity) while intentionally and permanently suppressing information about given semantic attribute (e.g., age or gender). See Figure [ (a) for illustration. Let Z be the encoding of the input data from which the target attribute Y be predicted. When the statistical dependency between Y and S is not negligible, learning a representation Z that is invariant to the semantic attribute S (i.c., Z IL S) will necessarily degrade the performance of the target prediction, i.c., there exists trade-off between utility and invariance. The existence of a trade-off has been well established, both theoretically and empiri- cally, under various contexts of representation learning such as fairness (Menon & Williamson, 2018 Zhao & Gordon 2019; Gouic et al. 2020; Zhao 202I), invariance (Zhao et al. 2020). and domain adaptation (Zhao et al. (019b). However, much of this body of work only establishes bounds on the trade-off rather than a precise characterization. As such, two aspects of the trade-off in invariant representation learning (IRepL) are unknown, including i) exact characterization of the trade-off inherent IRepl. and ii) learning algorithm that achieves the trade-off. Under the

---

Published in Transactions on Machine Learning Research (12/2022)
Utility
100%
Infeasible
To
Tub
gy (Z)
Y
Increase Utiliyy
X
f(x)
Feasible
Dep(Z,
S
Increase Independence
Dep(Z, S)
(b)
Figure 1: (a): Invariant representation learning seeks representation Z = f(X that contains much information necessary for the downstream target predictor gy while being independent of the semantic attribute S. (b): The trade- off (denoted by Tom) between utility (target task performance) and invariance (measured by the dependence metric ()) is induced by a controlled representation learner the hypothesis class of all Borel functions.
assumption that the distribution of low-dimensional projection of high- high-dimensional data approximately normal, this paper studies and establishes the aforementioned properties by constraining function classes to reproducing kernel Hilbert spaces (RKHS)s.
Ideally, the unility-nvarriance trade-off is defined as bi-objective optimization problem:
inf Exy [Ly (gy (f(X)),)) such that Dep (f(X), Se
(1)
JE CHy
where f is the encoder that extracts the representation Z = f(X from X, gy predicts Ý from the representation Z, Hx and Hy are corresponding hypothesis classes, and Ly the loss function for predicting the target attribute Y The function Dep(-.)) 0 parametric or con-aaraettri measure of statistical dependence, i.c., Dep(Q, U) implies and U are independent, and Dep(Q, > implies Q and U are dependent with larger values indicating greater degrees of dependence. The scalar 2 0 is a user-defined parameter that controls the trade-off between the two objectives, with + oc being the standard scenario that has no invariance constraints with respect to (w.r.t) S. In contrast, e - 0 enforces Z IL S (i.e., total invariance). Involving all Borel functions in Hxx and Hy ensures that the best possible trade-off is included within the feasible solution space. For example, when e + oo and Ly is MSE loss, the optimal Bayes estimator, gy (f(X)) = [Y] X] is attainable.
In this paper, we consider the linear combination of utility and invariance in ① and define the optimal utility-invariance trade-off (denoted by Top) single objective optimization problem:
Definition
Topt = inf JEHx (1-
{
inf Ex,y [Ly (gy (f()))))) + Aepp (X), 0 05A=1, gy Eyy
(2)
where À controls the trade-off between utility and invariance. For example, invariance and only optimizing the utility, while - 1 corresponds 1L S.
corresponds to ignoring the
The motivations behind considering this single-objective IRepL are (i) any solution this simplified problem is solution the bi-objective problem in (1). (ii) even ( is challenging to solve, and (iii) existing works have not
2

---

Published in Transactions on Machine Learning Research (12/2022)
thoroughly investigated 2 An illustration of the utility--nvariinn trade-off is illustrated in Figure[[bb (b). In this paper. we restrict Hx to be some RKHSs and Dep(Z, S) to be simplified version of the Hilbert-Schmidt Independence Criterion (HSIC) (Gretton et al. 2005a). Further, we replace the target loss function in 2 by Dep(Z, Y) as presented
and justified in Sections 3.2 and 5.2
Summary of Contributions: i) We design dependence measure that accounts for all modes of dependence between Z and S (under mild assumption) while allowing for analytical tractability. ii) We employ functionn in RKHSs and obtain closed-form solutions for the IRepL optimization problem. Consequently, we precisely characterize near-optimal approximation of Topt via encoders restricted to RKHSs. iii) We obtain closed-form estimator for the encoder that achieves a near-optimal trade-off and establish its numerical convergence. iv) Using random Fourier features (RFF) (Rahimi et al., (007), we provide a scalable version (in terms of both memory and computation) of our IRepL algorithm. v) We numerically quantify our Topt (denoted by K-Topp) on an illustrative problem as well as large-scale real-world datasets, Folktables (Ding et al. (02T) and CelebA (Liu et al. 2015), where we compare K-Top to those obtained by existing works.
2 Related Work
2.1 Invariant Representation Learning
The basic idea of representation learning that discards unwanted semantic information has been explored under many contexts like invariant, fair, or privacy-preseree
learning. In domain adaptation (Ganin & Lempitsky| 2015 Tzeng 2018), the goal is to learn features that independent of the data domain. In fair learning
et al.
2017: Zhao et al.
Dwork et al. 2012
Ruggieri
2014 Feldman et al. [015 Calmon et al.] 2017:Zemel et al. 2013 Edwards & Storkey
2015
Beutel et al.
2017
Xie et al., 2017 Zhang et al. 2018; Song et al. [219]] Madras et al. 2018 Bertran et al.
2019: Martinez et al. 2020; Sadeghi et al. 2019), the goal is to discard the demographic information that leads to unfair outcomes. Similarly, there is growing interest in
2019
Creager et al.
2019
Locatello et al. 2019 Mary et al.
mitigating unintended leakage of private information from representations (Hamm 2017 Coavoux et al. 2018 Roy
& Boddeei 2019:
Xiao et al. 2020 Dusmanu al., 2021).
A vast majority of this body of work is empirical. They implicitly look for single or multiple points the trade-off between utility and semantic information and do not explicitly seek to characterize the whole trade-off front. Overall, these approaches are not concerned with or aware of the inherent utility-invariane trade-off. In contrast, with the cost of restricting encoders to lie in some RKHSs, we precisely characterize the trade-off and propose a practical learning algorithm that achieves this trade-off.
2.2 Adversarial Representation Learning
Most practical approaches for learning fair, invariant, domain adaptive, or above are based on adversarial representation learning (ARL). ARL is typically formulated as
representations discussed
inf {11 - JEHx
inf Ex,y [LY (gr (J(X)), Y) X inf Ex,s [Ls (gs ((X))) } Eyy
(3)
gsEHs
where Ls is the loss function of a hypothetical adversary gs, who intends to extract the semantic attribute S ttroughh the best estimator within the hypothesis class Hss and 0 < X < 1 is the urility-invariance trade-off parameter. ARL is a special case of (2) where the negative loss of the adversary, - inf Ex,s [Ls (gs (f(x)) SS) plays the role of E
(X)( However, this form of adversarial learning suffers from critical drawback. The induced independence measure is not guaranteed to account for all modes of non-linear dependence between S and 2 if the adversary loss function Lg is not bounded like MSE or cross- cross-entropy (Adeli et al. 2021 Grari et al., 2020). In the case of MSE loss, even if the loss is maximized at a bounded value, where the corresponding representation Z = f(X) is also bounded, it still does not guarantee that Z IL S is attainable (see Appendix H for more details). This implics that designing the adversary loss in ARL to account for all types of dependence is challenging and can be infeasible for some loss functions.
By "all modes of dependence" we mean types of linear and non-linear relations, contrast to only linear monotonic relations.
3

---

Published in Transactions on Machine Learning Research (12/2022)
2.3 Trade-Offs in Invariant Representation Learning:
Prior work has established the existence of trade-offs in IRepL, both empirically and theoretically. In the following, we categorize them based on properties of interest.
Restricted Class of Attributes: majority of existing work considers IRepI. trade-offs under restricted settings, e.g., binary and/or categorical attributes Y and S. For instance. Zhao al. (2019a) uses informmtiin-thherreicc tools and characterizes the utility- utility-faimess trade-off in terms of lower bounds when both Y and S are binary labels. Later McNamara et al. (2019) provided both upper and lower bounds for binary labels. By leveraging Chernoff bound, Dutta et al. (2200) proposed a construction method to generate an ideal representation beyond the input data to achieve perfect fairness while maintaining the best performance on the target task. In the case of categorical features, a lower bound on utility-faimmen trade-off has been provided by Zhao & Gordon (2019) for the total invariance scenario (i.c.. Z S). contrast to this body of work, our trade-off analysis applies to multi-dimensional continuous/dissrett attributes. To our knowledge, the only prior results under general setting are [aadehhi al. (2019) and Zhao et al.) (2020). However, in /Zao et al. (2020), both S and Y are restricted be continuous/discrett binary simultaneously (e.g., it is not possible to have Y binary while S is continuous).
Characterizing Exact versus Bounds on Trade-Off: To the best of our knowledge, all existing approaches ex- cept Sadeghi et al. (2019), which obtains the trade-off for the linear dependence only, characterize the trade-off in terms of upper and/or lower bounds. In contrast, we precisely characterize a near-optimal trade-off with closed-form expressions for encoders belonging to some RKHSs.
Optimal Encoder and Representation: Another property of practical interest is the optimal encoder that achieves the desired point on the utility-nvarriance trade-off and the corresponding representation(s). Existing works which only study bounds on the trade-off do not obtain the encoder that achieves those bounds. For example, Sadeehi et al. (2019) develop a learning algorithm that obtains a globally optimal encoder, but only under a linear dependence measure between Z and S. HSIC, a universal measure of dependence, has been adopted by prior work (e.g.. Quaddianto et al. (2019)) to quantify all types of dependencies between Z and However, these methods adopt stochastic gradient descent for optimizing the underlying non-convex optimization problem. As such, they fail to provide guarantees that the representation learning problem converges global optimum. In contrast, we obtain a closed-fore solution for the globally optimal encoder and its corresponding representation while detecting all modes of dependence between Z and S.
2.4 Kernel Method
The technical machinery of our kernel method for representation learning is closely related to kernelized component analysis (Schölkopf et al. 1998). Kernel methods have been previously used for fair representation learning by Pérez- Suay et al. (2017) where the Rayleigh quotient is employed to only search for a single point in the utility-invariance trade-off. To find the entire trade-off, (Sadeghi et al. (2019) used kernelized ARL with linear adversary and target
estimator. Kernel methods also have been used to measure all modes of dependence between two RVs, pioneered by [Bach & Jordan (2002) in kernel canonical correlation (KCC). Building upon KCC, later, Gretton al. (2005a] by 2006) have introduced HSIC, constrained covariance (COCO), and maximum mean discrepancy (MMD), to name few. Inspired by these works, a variation of HSIC is adopted as measure of dependence in this paper.
3
Problem Setting
3.1 Notation
Scalars are denoted by regular lowercase letters, e.g., r, X. Deterministic vectors are denoted by boldface lowercase letters, e.g., x, 8. We denote both scalar-valued and multidimensioonll random variables (RV)s by regular upper case letters, e.g., X, S. Deterministic matrices are denoted by boldface upper case letters, e.g., H, O. The entry at i-th j-w, column of matrix M is denoted by (M),, or mig- I, or simply denotes an n x n identity matrix; 1, and O, denote n-tuple vectors of ones and zeros, respectively. We denote the trace of a square matrix K by Tr The pseudo-inverse of matrix U is denoted by Ut, We denote finite or infinite sets by calligraphy letters, e.g., H. A.
4

---

Published in Transactions on Machine Learning Research (12/2022)
Dep(Z,Y)
Σ Σ
Cov2 (2,,
(-(-) Y
j=1 Evlly
X - Z f(X) = + Xx
Dep(Z,S)= := Σ J= AsEus
Σ
Cov (Z,.
3s(() 5
Figure 2: Our IRepL. model consists of three components: i) An r-dimensional encoder f belonging to the universal RKHS Hx. ii) A measure of dependence that accounts for dependence modes between data representation Z and semantic attribute induced by the covariance between Z f(X) and Bs(S) where 33 belongs to universal RKHS Hy. iii) A measure of dependency between Z and the target attribute Y defined similarly as that for S.
3.2 Problem Setup
Consider the probability space F,,,,, where is the sample space, is a a-lleeraa on St and F is probability measure on F. We assume that the joint RV, (X,Y, S.YY S) containing the input data X E R the target label Y E Re and the semantic attribute S dRds, is a RV on (2, F) with joint distribution Px,y,s- Furthermore, Y and S can also belong any finite set, such as categorical set. This setting enables us work with both classification and multidimensional regression tasks, where the semantic attribute can be either categorical or multidimensional continuous/discrete RV.
We assume that the encoder consists of functions from Rd to R in universal RKHS (Hx, ; Ax (): (e.g., RBF Gaussian kernel,, where universality ensures that Hx approximate any Borel function with arbitrary precision (Sriperumbudur et al. 2011).
Assumption 1.
Hence, the representation RV Z can be expressed as
Z = f(x) = [2,, .., ".,,,,,,,, 2 E R", 1 E Hx = 1j,,,.,
(4)
where r is the dimensionality of the representation. As we will discuss in Corollary 4.1 unlike common practice where r is chosen on an ad-hoc basis, is an object of interest for optimization. We consider a general scenario where both Y and S can be continuous/discrete or categorical, or one of Y or is continuous/discrete while the other is categorical. To accomplish this, we replace the target loss, inf Ex [Ly (Z), in (2 by the negative of gy Eity
non-parametric measure of dependence, i.e., -Dep (Z, Y). The main reason for this replacement is that maximizing statistical dependency between the representation Z and the target attribute Y can flexibly learn a representation ap- plicable to different downstream target tasks, including regression, classification, clustering, etc (Barshan et al. 2011). Particularly, Theorem 6 in Section 5.2 indicates that with an appropriate choice of involved RKHS for Dep (Z, Y), we can learn representation that lends itself an estimator that performs as optimally as Bayes estimator i.e., Ex [.] Furthermore, in unsupervised setting, where there is no target attribute Y, the target loss can be replaced by Dep (Z, X), which implicitly forces the representation Z to be as dependent on the input data X. This scenario is of practical interest when data producer aims to provide an invariant representation for an unknown downstream target task.
4 Choice of Dependence Measure
We only discuss Dep S) since we adopt the same dependence measure for Dep (2, Y). Accounting for all possible non-linear relations between RVs is a key desideratum of dependence measures. A well-known example of such measures is mutual information (MI) (e.g.. MINE (Belghazi et al. 2018).. However, calculating MI for continuous multidimensional representations analytically challenging and computationally intractable. Kernel-based measures are an alternative solution with the attractive properties of being computationally feasible/efficient and analytically tractable (Gretton al. 2005b).
Definition Let D { V/, $1)..... (I., Un. s,)) } be the training data, containing n i..dd. samples from the joint distribution Px,y.s- Invoking the representer theorem (Shawe-Taylor & Cristianini 2004). it follows that for
5

---

Published in Transactions on Machine Learning Research (12/2022)
each fy Hx G = 1, .,) we have Z₁ fx( = Ei=1 Ogckx (2), where fiys the learnable linear
weights. Consequently, it follows that
f(X) = ( [2x, ,. (2n, x)]²;
(5)
where θ E _ and (+) Ozi.
Principally, Z S if and only if (iff) Cov(a(2). = 0 for all Borel functions ar IR" - R and As RRds - R
belonging to the universal RKHSs Hz and Hss respectively. Alternatively, IL S iff HSIC(Z, 0 where
HSIC (Gretton et al. 2005a) is defined as
HSIC(Z, = Σ
Σ Cov2 (a(Z),Bs(S))
(6)
oEEiz ByElds
where Uz and Us are countable orthonormal basis sets for the separable universal RKHSs Hz and H.s, respectively, However, since Z = fX) where f is defined in (4), calculating Cov(a(Z), (s)) necessitates the application of a cascade of kernels, which limits the analytical tractability of our solution. Therefore, we adopt a simplified version of HSIC that considers transformation on S only but affords analytical tractability for solving the IRepl. optimization problem. We define this measure as
Dep( (2 = Σ Σ Cov2 (Z,.8s(8)). Bs
where Z, = (X) for fys defined in We note that Dep( unlike HSIC and other kernelization sereeliztionnbaaed de- pendence measures, is not symmetric. However, symmetry is not necessary for measuring statistical dependence. To guarantee the boundedness of S)) and f(X), we make the following assumption in the remainder of this paper. Assumption 2. We assume that (Hs, ks(-,)) and (Hy, ky(,,)) +)) are separable and the kernel functions are bounded:
and
Ey [U,( < co, for U = =,Y,S
(8)
The measure Dep( S) in 7 captures all modes of non-linear dependence under the assumption that the distribution of a low-dimensional projection of high-dimensiooal data is approximately normal (Diaconis & Freedman 1984).
(Hall & Li 1993). To see why this reasoning is relevant, we note from (5) that Z can be expressed as 2 = @V, where V E R" and E Rr*" This indicates that for large n and small r (which is the case for most real-world datasets). Z is indeed a low-dimensional projection of high-dimensional data. other words, (Z, (S)) )) is approximately a jointly Gaussian RV. In our numerical experiments in Section 6 we empirically observe that Dep( Dep(Z,5) S) enjoys an almost monotonic relation with the underlying invariance measure and captures all modes of dependency in practice, especially as Z IL S. Nevertheless, if the normality assumption the distribution of (Z, (S)) fails. Dep(Z, S) reduces to measuring the linear dependency between Z and Bs(S) for all Borel functions Bs. This corresponds to measuring the mean independency of Z from S, i.e., how much information a predictor (linear and non-linear) can infer (in the sense of MSE) about Z from S. See Appendix H for more technical details on mean independency.
Lemma Let Kx, Kg E Rnx= be the Gram matrices corresponding to Hx and H.s. respectively, i.c., (Kx);j = kx (2,, 2.) and (Ks).) kgg (s,, sj), where covariance is empirically estimated as
1 (
1
Cov (f)(X),
It follows that, the corresponding empirical estimator for Dep (2,5) is
Dep (Z.S) = n H0
where H= = I, 1" is the centering matrix, Lg is a full column-rank matrix in which Ls = K3 (Cholesky factorization), and Ks is the Gram matrix corresponding to Hy. Furthermore, the empirical estimator in 9 has a bias of (nn-))))))))))) and a convergence rate of O(n -1/2).
2A Hilbert space is separable iff has countable orthonormal basis

---

Published in Transactions on Machine Learning Research (12/2022)
Proof. The main idea for proving equality ( is to employ the representer theorem to express fy and 3s. For the bias and convergence rate, one can express equation ( in terms of trace and then employ U-statistics together with Hoeffdig's 's inequality (Hoeffding 1994). For complete proof, see Appendix B
Finally, we note that the dependence measure between Z and Y can be defined similarly.
5 Exact Kernelized Trade-Off
Consider the optimization problem corresponding to Topt in 2 Recall that Z = f(x is an r-dimensional RV, where the embedding dimensionality r is also a variable to be optimized. A common desideratum of learned representations is that of compactness (Bengio et al. 2013) to avoid learning representations with redundant information where different dimensions are highly correlated to each other. Therefore, going beyond the assumption that each component of f (i.e., fys) belongs the universal RKHS Hx, we impose additional constraints the representation. Specifically, we constrain the search space of the encoder (-) to learn a disentangled representation (Bengio et al. 2013) follows
A, :- ((fi....,.. .f)) fa. Hx, Cov
+ + fixx ( -
(10)
In the above set, the Cov [J part enforces the covariance matrix of = fXX to be an identity matrix. Such disentanglement also used in principal component analysis (PCA). encourages the variance of each entry of Z to be one and different entries of Z to be uncorrelated with each other. The regularization part, (fi, f Hx encourages the encoder components to be as orthogonal as possible to each other and to be of unit norm, which aids with numerical stability during empirical estimation (Fukumizu et al., 2007). As the following theorem states formally, such disentanglement an invertible transformation; therefore, it does not nullify any information.
Theorem Let Z = f(X) be an arbitrary representation of the input data, where f E Hxx Then, there exists an invertible Borel function h, such that o f belongs Ap.
Proof. The main idea is to search for an explicit expression for h in terms of the invertible operator Σxx + y Ix. where Xxx is induced by the bi-linear functional Cov (fi(X), f; (Exx [i) and Ix is the identity operator from Hx to itself. See Appendix C for complete proof.
This Theorem implies that the disentanglement preserves the performance of the downstream task since any target network can revert the disentanglement h and access the original representation Z. In addition, any deterministic measurable transformation of Z will not add any information about S' that does not already exist in Z.
We define our K- Top as
sup ( X) Dep (f(X), - fEA.
- Dep (f(),,)) OSA<1,
(11)
where À is the dullity-invariane trade-off parameter. Fortunately, the above optimization problem lends itself to closed-form solution.
Theorem 3. Consider the operator Σsx to be induced by the bi-linear functional (ova((X,$ss($)) (Esxa, a. As)u, and define Σy x and Σxx, similarly. Then, a global optimizer for the optimization problem in the eigenfunctions corresponding to the r largest eigenvalues of the following generalized eigenvalue problem
11) is
((1 - A) Eyx - XE f = (Exx + + xxx f.
(12)
where is the disentanglement regularization parameter defined in (10). and Σ" is the adjoint of Σ.
Proof. The first step is to express Dep(f(X), and (ep(f(X).SS in terms of Σyx and Σsx, respectively. The resulting expression can be restated as a generalized Rayleigh quotient (Strawderman 1999) which can be solved via generalized eigenvalue formulation. For complete proof, see Appendix D
Remark 1. If the trade-off parameter À = (i.c., no semantic independence constraint is imposed) and y + 0, the solution in Theorem is equivalent to a supervised kernel- On the other hand, if X - 1 (i.e., utility is ignored and only semantic independence is considered), the solution in Theorem is the eigenfunctions corresponding to the smallest eigenvalues of Σ Egx, which are the directions that are the least explanatory of the semantic attribute S.

---

Published in Transactions on Machine Learning Research (12/2022)
Now, consider the empirical counterpart of the optimization problem
sup (JemP( (f; = (1 X) "mp (f(X), "e (f(X),)), 05Λ<1
(13)
feA,
where Dep (f(X), is given in and Dep ( is defined similarly.
Theorem 4. Let the Cholesky factorization of Kx be Kx Lx Lx where Lx E RRud (d S n) is full column- rank matrix. Let & d, then solution to (13) is
(X) a [xx (21, X), X): 1x ( X))"
where Opt = U and the columns are eigenvectors corresponding to the r largest eigenvalues the following generalized cigenvalue problem.
x ((1 - AJHK Lxu (EK ( + t41
(14)
Further, the objective value of (13) is equal to Ej=1 Ty. where , are the r largest eigenvalues of 14
Proof. The main idea to employ empirical expressions obtained in equality The resulting expression on can be expressed trace optimization problem which be solved by eigenvalue formulation (Kokiopoulou et al. 2011). See Appendix E for detailed proof.
Corollary 4.1. Embedding Dimensionality: A useful corollary of Theorem is characterizing optimal embedding dimensionality as a function of the trade-off parameter, A:
(P) = arg sup sup (Jomp (.AI] number of non-negative eigenvalues of 14 uSrSd SEA,
To examine these results, consider extreme cases: i) there is no semantic independence constraint (i.c., À 0), all eigenvalues of (14) non-negative since HKy H is non-negative definite matrix and L HLx + II is a positive definite matrix. This indicates that Ops is equal to the maximum possible value (that is equal to d), and therefore it is not required for Z to nullify any information in X. îi) If we are only concerned about semantic independence and want to ignore the target task utility (i.e., >> 1), all eigenvalues of (14) are non-positive and emi therefore Op would be the number of zero eigenvalues of (14). This indicates that Dep (Z. S) in (9) is equal to zero, since opt Kx x is zero for zero eigenvalues of (14) when + 1. In this case, adding more dimension Z will necessarily increase Sep S).
The following Theorem characterizes the convergence behavior of empirical K K-Top: to its population counterpart.
Theorem 5. Assume that ks and ky are bounded by one and (x;) S M for any L...., r and i 1,..., for which (fi,..., A,. Then, for any and < with probability at least 5, have
log(6/8) 0.22 + O (
sup J(F,)) sup j (f, S SrMy fEA.
JEA,
Proof. This Theorem can be proved by using the results of the convergence rate of Dep(Z,S) Lemma ! For detailed proof, see Appendix
Note that, for any in the training set, fy (œ) can be calculated as fx) Ei= 0j (æ;, We can assume that kx (:) is bounded. For example, in RBF Gaussian and Laplacian RKHSs, both of which are universal, (x(:,)) < 1. This implies that (z()) < / where 0, is j-th row of in equation (5). One always can normalize (=) () by dividing by the maximum of /n|0,, (0 over js, or by dividing by the maximum of (2,)) over and js. Notice that this normalization is only scalar multiplication and has no effect on the invariance of f(X) to and the utility of any downstream target task predictor gy (Z).
8

---

Published in Transactions on Machine Learning Research (12/2022)
5.1 Numerical Complexity
Computational Complexity: If Lx in (14) is provided in the training dataset, then the computational complexity of obtaining the optimal encoder is ((1)), where / S is the numerical rank of the Gram matrix Kx. However, the dominating part of the computational complexity is due to the Cholesky factorization, Kx = Lx LX. which is (n²). Using random Fourier features (RFF) (Rahimi et al. 2007). 1x (æ, x') can be approximated by rx (x)" rx (z²), where rx (a:) IR. this situation, the Cholesky factorization can be directly calculated as
(x(x)))
Lx
Rand
(15)
Tx (x,)
As a result, the computational complexity of obtaining the optimal encoder becomes O(d), where the RFF dimen- sion, d, can be significantly less than the sample size n with negligible error on the approximation xx (x x') rx (x:" rx (x').
Memory Complexity: The memory complexity of (14), if caleulated naively, is O(n²) since Ky and Kg by n matrices. However, using RFF together with Cholesky factorization KY Ly Ks L the left-hand side of (14) can be re-arranged
(1- 1) Lr)
(ΣōLx),
(16)
where if Ly Ly) and therefore, the required memory complexity is O(nd). Note that L and HLx can be calculated similarly.
5.2 Target Task Performance in T-Topt
Assume that the desired target loss function is MSE. Then, in the following Theorem, we show that maximizing Dep (f()), Y) over f E A, can learn a representation Z that is informative enough for a target predictor on to achieve the most optimal estimation, i.e., the Bayes estimator [E]
Theorem 6. Let f* be the optimal encoder by maximizing (X), Y), where y - 0 and Hy is a linear RKHS. Then, there exist W E Bdy xr and E Rd such that W (X) +
the Bayes estimator, i.e.,
Exy f(X)* + b--1 =
inf
Ex.y (X) Y
à is Borel
E [| Y
Proof. This Theorem corresponds a linear least square target predictor on top of kernelized encoder with a solu- tion(s) similar to supervised kemel-PCA. Recall from Remark that if À 0, optimizing Dep(f(X), Y) will result in a supervised kemel-PCA. See Appendix G for formal proof.
This Theorem implies that not only can Dep (f(X), preserve all the necessary information in Z to predict Y optimally, the learned representation is simple enough for linear regressor to achieve optimal performance.
6 Experiments
In this section, numerically quantify our K-Top through the closed-form solution for the encoder obtained in Section on an illustrative toy example and two real-world datasets, Folktables and CelebA.
6.1 Baselines
We consider two types of baselines: (1) ARL (the main framework for IRepL.) with MSE or Cross-Entte Eotsr-E as the
adversarial loss. Such methods are expected fail learn fully invariant representation (Adeli et 2021 Grari
et al. 2020). These include (Xie al. 2017 Zhang al. 2018 Madras et al., 2018), and SARL (Sadeghi et al.

---

Published in Transactions on Machine Learning Research (12/2022)
2019). Among these baselines, except for SARL, all baselines are optimized via iterative minimax optimization, which is often unstable and not guaranteed to converge. On the other hand, SARL obtains a closed-form solution for the global optima of the minimax optimization under a linear dependence measure between Z and S, which may fail to capture all modes of dependence between Z and S. (2) HSIC-based adversarial loss that accounts for all modes of dependence, and as such, is theoretically expected to learn a fully invariant representation (Quadrianto et al., 2019). However, since stochastic gradient descent is used for learning, it lacks convergence guarantees to the global optima.
6.2 Datasets
Gaussian Toy Example: We design an illustrative toy example where X and S are mean independent in some dimensions but not fully independent in those dimensions. Specifically, X and S are 4-dimensional continuous RVs and generated as follows,
U = UU1, U2, Us, UN ~ (O2, (O,, ~~NN(1,,L)) UL N
ạ U) + 0.005N, S sin (6 [U, Usl: cos ( UUs U.
X = cos
(17)
6
where sin(.) and cos(-) are applied point-wise. To generate the target attribute, we define four binary RVs follows.
Y; = 1QUA)ST i = 1,2,3,4,
where 1x(-) is the indicator function, and we set T 0.6744, so it holds that P[Y: 0] PlY; - 1| = 0.5 for i 3, 4. Finally, we define Y 16-class categorical RV concatenated by Y,s. Since S is dependent X through all the dimensions of X, a wholly invariant Z (i.e., Z 1. S) should not contain any information about X. However, since [S S2] is only mean independent of [X,, X2] (i.e., IE S1, S2 X1, baselines with MSE as the adversary loss, i.e., Xie et al. (0117) Zhang et al. (2018) Madras et al. (2018) and SARL cannot capture the dependency of Z to So] and result in a representation that always dependent on [S|, St] (see Section H for theoretical details). We sample 18, 000 instances from px,Y, independently and split these samples equally into training, validation, and testing partitions.
E , ARL
We consider a fair representation learning task Folktables (Ding et al. 2021 dataset (a derivation of the US census data). Specifically, we consider 2018-WA WA (Washington) and 2018-NY (New York) census data where the target attribute Y is the employment status (binary for WA and 4 categories for NY and the semantic attribute S is age (discrete value between O and 95 years). We seek to learn a representation that predicts employment status while being fair in demographic parity (DP) w.r.t. age. DP requires that the prediction Y be independent of S, which can achieved by enforcing Z IL S. The WA and NY datasets contain 76, 225 and 196, 967 samples, each constructed from 16 different features. We randomly split the data into training (70%), validation (15%), and testing (15%) partitions. Further, we adopt embeddings for categorical features (learned in supervised fashion to predict Y) and normalization for continuous/discrete features (dividing by the maximum value).
Folktables:
CelebA: CelebA dataset (Liu et al., 2015) contains 202, 599 face images of 10, 177 different celebrities with standard training, validation, and testing splits. Each image is annotated with 40 different attributes. We choose the target attribute Y as the high cheekbone attribute (binary) and the semantic attribute as the concatenation of gender and age (a 4-class categorical RV). The objective of this experiment is similar to that of Folktables. Since raw image data is not appropriate for kernel methods, we pre-train a ResNet- 18 (He et al.) (0166) (supervised to predict Y) on CelebA images and extract features of dimension 256. These features used as the input data for all methods.
6.3 Evaluation Metrics
We use the accuracy of the classification tasks (16-class classification for Gaussian toy example, employment pre- diction for Folktables, and high cheekbone prediction for CelebA) as the utility metric. For Folktables and CelebA datasets, we define DP violation
D = Eg Vars [1]
(18)
and use it as metric to measure the variance (unfairness) of the prediction Ý w.n.t. the semantic attribute S. For the Gaussian toy example, the above metric is not suitable since S is continuous RV. To circumvent this difficulty, we
10

---

Published in Transactions on Machine Learning Research (12/2022)
Enshoaling Din.
Enbeeliicg
(4)
(1)
Figure 3: Plots of (A) versus the dependence trade-off parameter 1 1 À for (a) the Gaussian toy dataset and (b) Folktables-NY dataset. There is non-decreasing relation between y (00 and 1 A.
employ KCC (Bach & Jordan 2002)
Cov(a(Z).8(S))
KCC(2,S) = sup aEHz.DENs Var
(19)
measure of invariance of Z to S, where Hzz and H.s are RBF-Gaussian RKHS. The reason for using KCC instead of HSIC is that, unlike HSIC, KCC is normalized. Therefore it is more readily interpretable measure for comparing the invariance of representations between different methods.
6.4 Choice of (Y.S) Pair
The existence of a utllity-invariance trade-off ultimately depends the statistical dependency between target and semantic attributes. If SS)(Z,S) is negligible, trade-off does not exist. Keeping this in mind, first chose the semantic attribute to be a sensitive attribute for Folktables (i.e., age) and CelebA (i.e., concatenation of age and gender) datasets. Then, we calculated the data imbalance (i.e., [|[[Y = 0] 0.5) and KCC(Y, for all possible Ys. Finally, we chose Y with a small data imbalance and moderate KCC(Y, S). For Folk- tables dataset, |P(employment = 0] - 0.5| 0.04 and KCC(employment, age) = 0.4. For CelebA dataset, [Plhigh cheekbone = 0j 0.5| = 0.05 and KCC(high cheekbone, (age, gender)) 0.1.
6.5 Implementation Details
For all methods, we pick different values of X (100 As for the Gaussian toy example and 70 As for Folktables and CelebA datasets) between zero and one for obtaining the -ulitt-invarriace trade-off. We train the baselines that use a neural network for encoder five times with different random seeds. We the random seed also change the training- validation-testing split for the Folktables dataset (CelebA and Gaussian datasets have fixed splits).
Embedding Dimensionality: None of the baseline methods have any strategy to find the optimum embedding di- mensionality (r), and they all set to constant w.r.t. A. Therefore, for baseline methods, we set r 15 (i.e., the minimum dimensionality required to classify 16 different categories linearly) for the Gaussian toy example and r= 3 (i.e., the minimum dimensionality required to classify different categories linearly) for Folktables-NY dataset, that is also equal to Opt when = 0. For K- K-Togt we use ort (A) in Corollary 4.1 See Figure for the plot of o versus for the toy Gaussian and Folktables-NY datasets. For Folktables- WA and CelebA datasets, OOtt( 0) equal to one, and therefore we let
for all methods and all < 1.
K-Topt (Ours): We let Hx. H.s, and Hy be RBF Gaussian RKHS, where we compute the corresponding band-widths (i.c., σs) using the median strategy introduced by Gretton et al. (2007). We optimize the regular- ization parameter in the disentanglement set (10) by minimizing the corresponding target losses over rs in (10-6, 10-5, 10-4, datasets. For RFF dimensionality, we started with small value. Then, we gradually increased it until we reached the maximum possible performance for = 0 (i.e,, the standard unconstrained representation learning) on the corre- sponding validation sets. Through this process, the final RFF dimensionality is 100 for the Gaussian dataset, 5000 for the Folktables dataset, and 1000 for the CelebA dataset.
10-3, 10-3,
10 10-1, 1 on validation sets. RFF (as discussed in Section 5.1 is adopted for all

---

Published in Transactions on Machine Learning Research (12/2022)
HSII AKL
Accuras
Accunacy
0-4
Tou
ARL
AKL
ARL
SAR
SAXL
SAIL
KCC 80
DPV
DPV
DPV
6g
(h)
(2)
Figure 4: Utility versus invariance trade-offs obtained by K-Topi and other baselines for (a) Gaussian, (b) Folktables- WA, (c) Folktables-NY, and (d) CelebA datasets. K-Topt stably spans the entire trade-off front and considerably dominates other methods for all datasets. (a) ARL and SARLeSadeghi et al. (2019) span a small portion of the tra front since S is mean independent (but not fully independent) of X in some dimensions for the Gaussian toy example. Despite using a universal dependence measure, HSIC-IRepL Quadrianto et al. (0019) performs sub-optimally due to the lack of convergence guarantees to the global optima.
0.2
044
0.35
Dep
D.p
0,2
2000
0.1
0.35
0013
0.1
0.10
0.2
0005
16.3
0.30
6.2
022
2,
()
Dep
2.
Figure 5: De)(Z,Y) versus S) in K K-Top for (a) Gaussian, (b) Folktables WA, (c) Folktables-NY, and (d) CelebA datasets. We can observe that there is the same trend Dep(Z,Y) Y)Depp(, S) trade-off as uillit--nvarriance trade-off in Figure
SARL (Sadeghi et al. 2019): SARL method is similar to our K- K-Topt except that Hy and Hs are linear RKHSs, and therefore we set dx and similar to that of K- TToi-
ARL (Xie et al., 2017: Zhang et al. 2018; Madras et al. 2018): The representation Z = (X) is extracted via the encoder f. which is an MLP (4 hidden layers and 15, 15 neurons for Gaussian data; 3 hidden layers and 128, 64 neurons for Folktables and CelebA datasets). The architectural choices were based on starting with a single linear layer and gradually increasing the number layers and neurons until over-fitting was observed. This results in the number of encoder parameters for the Gaussian toy example to be 735, while K-Top has 100 100 POM(A 1) 100 (A) < 100 (x 0) = 1500. For Folktables and CelebA number of parameters is 41,024 024 and 15, 616, respectively, for ARL and 5000 and 1000 for K-Tog- The representation Z is then fed to a target task predictor gY and proxy adversary gs. both of which are MLPs with 2 hidden layers with 16 neurons for Gaussian data and hidden layers with 128 neurons for Folktables and CelebA. All involved networks (f ...Y.9s) 99) are trained end-to-end. We use stochastic gradient descent-ascent XiG et al. (2017) with AdamW (Loshchilov & Hutter 2017) as an optimizer alternately train the encoder, target predictor, and proxy adversary. We use batch size of 500 for Gaussian data; and 128 for Folktables and CelebA. Then, the corresponding learning rates are optimized over f10-2,10* 10.3,003000 5,5% x
10 10- 10-51
5 by minimizing the target loss on the corresponding validation sets.
HSIC-IRepL (Quadrianto et al. 2019): This method can be formulated as 2 where Dep( Z, S) is replaced by HSIC(Z, S). The encoder and target predictor networks have the same architecture as ARL. And we use stochastic gradient descent to train the involved neural networks.
6.6 Results
Utility-Invariinee Trade-offs: Figures and 5 show the utility-nnvriiance and Dep(Z, Y.-.ye(DD.. trade-offs for the toy Gaussian, Folktables- WA, Folktables-NY, and CelebA datasets. The invariance measure for the Gaussian
12

---

Published in Transactions on Machine Learning Research (12/2022)
62
95
811
0:15
KCC/2.5)
0.4
DPV
DWv
6-10
6.15
0.2
De 8)
Dept2 5) (b)
Depl (4)
Dep(2,
(a)
(d)
Figure 6: Invariance versus Dep( 2, of Top for (a) Gaussian, (b) Folktables-WA, WA, (c) Folktables-NY, and (d) CelebA datasets. Ze S) enjoys a monotonic relation with the underlying invariance measures.
toy example is KCC 19 and the invariance measure for Folktables and CelebA datasets is the fairness measure, DPV (18). We make the following observations: 1) K-Ton is highly stable and almost spans the entire trade-off front for all datasets except Folktables-NY, which can be due the inability of scalarized single-objective formulation in (2). in contrast to the constrained optimization in (T). to find all Pareto-optimal points. 2) There is almost the same trend in the trade-off between Dep(2, Y) and Dep(Z, (Figure 5) as the utility-inarriance trade-off (Figure This is desirable observation since Dep( --Dep) S) trade-off is what we optimized in (IT) as surrogate to utility- invariance trade-off. 3) The baseline method HSIC-IRepL, despite using a universal dependence measure, leads to a sub-optimal trade-off off front due to the lack of convergence guarantees to the global optima. 4) The baselines, ARL and SARL, span only a small portion of the trade-off front in the Gaussian toy example since some dimensions of the semantic attribute S in [17) are mean independent (but not entirely independent) to some dimensions of X. Therefore the adversary does not provide any information to the encoder discard [S1, S2] from the representation. Moreover, in this dataset, ARL and SARL baselines do not approach Z 1L S, i.e., KCC(Z, S) O cannot be attained for any value of the trade-off parameter X. 5) ARL shows high deviation on the Folktables dataset due to the unstable nature of the minimax optimization. 6) SARL performs as well as our K-Topt for CelebA dataset. This is because both S and Y are categorical for the CelebA dataset, and therefore linear RKHS on one-hot encoded attribute performs just as well as universal RKHSs (Li et al. 202T).
Universality of Dep(Z, S): We empirically examine the practical validity of our assumption in Section and verify if our dependence measure SS, defined in 77. can capture all modes of dependency between Z and S. Figure (a) shows the plot of the universal dependence measure KCC(Z,S) versus Dep(Z, S) for the Gaussian dataset and Figures
6 (b, c) illustrate the relationship between DP S) and Dep( S) for Folktables and CelebA datasets, respectively. We observe non-decreasing relation between the corresponding invariance measures and Dep ()). More importantly, as KCC(Z, S) + 0 (or DPV(Ý, - 0) so does Dep(Z, These observations verify that Dep(Z,, S) accounts for all modes of dependence between and S.
6.7 Ablation Study
Effect of Embedding Dimensionality: In this experiment, examine the significance of the embedding dimension- ality, (A), discussed in Corollary 4.1 We obtain the utllity-nvariaace trade-off when the embedding dimension- ality is fixed to = pP 0) = 15. A comparison between the utility-inaariance trade-off induced by ,ol(()) and the fixed r = 15 is illustrated in Figure (a). We observe that not only the utility-invariance trade-off for fixed dominated by that of (X), but also, using fixed is unable to achieve the total invariance representation, i.e., Z IL S. Further, some of the largest eigenvalues of (14) versus the invariance trade-off parameter À are plotted in Figure (b). We recall from Corollary 4.1 that, for any given X, Opt is the number of non-negative eigenvalues of (14).
Effect of Semantic Attribute Removal: In this experiment, we examine the effect of removing S (i.e., age) from the input data in the Folktables-WA dataset and examine whether this removal helps the utility-invariance trade-off. Figure shows the -nilityinvariiacce trade-off resulting from all methods, and Figure (d) compares removing and keeping the age information from the input data for K K-Topt- Observe that: 1) There is almost the same trend in both keeping and removing the age attribute from the input data for all methods. 2) Removing the age attribute from input data slightly degrades the quility-ivaarian trade-off due to the lower information contained in the input data.
13

---

Published in Transactions on Machine Learning Research (12/2022)
3.6
K-Tap
Accuray
60
Higensstes
Acconacy
3.7
0.7
6.4
ARL
Kir Prieeo "ag (Ape Rerowod)
SARL
XCCC22 5) 69
DPV
DPV (
(h)
(0)
690
Figure 7: (a) Comparison between the utility-invariance trade-off's induced by the optimal embedding dimensionality y (A) and that of fixed 15. Fixed 15 is significantly dominated by that of (A) and fails attain Z TL S. (b) The first, fifth, tenth, and fifteenth largest eigenvalues in (14) versus 1 - A. Given X, r is equal to the number of decreases, the largest eigenvalues approach negative numbers. (c) Utility versus
non-negative eigenvalues. As
invariance trade-offss for all methods when age (i.e., the sensitive attribute) is discarded from the input data. (d) A comparison between trade-offs of K-Tope when age is present versus age is discarded from the input data. Removing the age attribute slightly degrades the trade-off due information discarding.
7 Conclusion
Invariant representation learning (IRepL) often involves trade-off between utility and invariance. While the existence of such trade-off and its bounds have been studied, its exact characterization has not been investigated. This paper took steps towards addressing this problem by i) establishing the exact kernelized trade-off (denoted by K-Top). ii) determining the optimal dimensionality of the data representation necessary to achieve a desired optimal trade-off point, and iii) developing a scalable learning algorithm for encoders in some RKHSs to achieve K-Tope. Numerical results on an illustrative example and two real-world datasets show that commonly used adversarial representation learning- based techniques cannot attain the optimal trade-off estimated by our solution.
Our theoretical results and empirical solutions shed light on the utility-invariance trade-off for various settings, such learning under the scalarization of the bi-objective trade-off formulation.
algorithmic fairness and Furthermore, the trade-off in IRepL is also a function of the involved dependence measure that quantifies the depen- dence of learned representations on the semantic attribute. As such, the trade-off obtained in this paper is optimal for HSIC-like dependence measures. Studying the bi-objective trade-off (rather than the scalarization) and employing other universal measures are possible directions for future work.
Broader Impact
IRepL can enable many machine learning systems to generalize to the domains that have not been trained on or pre- vent the leakage of private (sensitive) information while being effective for the desired prediction task(s). In particular, IRepl. has direct application in fairness which is significant societal problem. Even though this paper aims char- acterize the utility-invariance trade-off as a byproduct, our paper proposes an algorithm that learns fair representations of data. More generally, these approaches can enable machine learning systems discard specific data before making predictions. We point out that demographic parity, the fairness criterion considered in this paper, can be unsuitable as a fairness criterion in some practical scenarios (Hardt et al. 2016 Chouldechova 2017) and other fairness criteria like equalized odds (EO) or equality of opportunity (EOO) (Hardt et al., 2016) should be considered. The method proposed in this paper can be extended to other notions of fairness, such as EO and EOO, by modifying Dep (Z, S) to capture the dependency between Z and S, given Y. We leave this extension future work.
This work was supported in part by financial assistance from the U.S. Department of Com- merce, National Institute of Standards and Technology (award #60NANB18D2100 and the National Science Founda- tion (award #2147116).
Acknowledgements::
14

---

Published in Transactions on Machine Learning Research (12/2022)
References
Ehsan Adeli, Qingyu Zhao, Adolf Pfefferbaum, Edith V Sullivan, Li Fei-Fei, Juan Carlos Niebles, and Kilian M Pohl. Representation learning with statistical independence mitigate bias. IEEE/CVF Winter Conference Applications of Computer Vision, pp. 2513-2523, 2021.
Francis Bach and Michael I Jordan. Kernel independent component analysis. Journal of Machine Learning Re- search, 3(6): 2002.
Elnaz Barshan, Ali Ghodsi, Zohreh Azimifar, and Mansoor Zolghadri Jahromi. Supervised principal component analysis: Visualization, classification and regression on subspaces and submanifolds. Pattern Recognition, 44(7): 1357-1371, 2011.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. International Conference on Machine Learning, pp. 531-540, 2018.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Inielligence, (118)))798-188888 2013.
Martin Bertran, Natalia Martinez, Afroditi Papadaki, Qiang Qiu, Miguel Rodrigues, Galen Reeves, and Guillermo Sapiro. Adversarially learned representations for information obfuscation and inference. International Conference Machine Learning, 2019.
Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint arXiv: 2017.
Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. Op- timized pre-processing for discrimination prevention. Advances in Neural Information Processing Systems, pp. 3992-4001, 2017.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. big data 5, 2 (2017), 153-163, arXiv preprint 1r1:v:1610 2017.
Maximin Coavoux, Shashi Narayan, and Shay Cohen.
neural representations of text. arXiv
preprint /80.:00000 2018.
Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa A Weis, Kevin Swersky. Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. International Conference on Machine Learning. 2019.
Persi Diaconis and David Freedman. Asymptotics of graphical projection pursuit. The Annals of Statistics, pp. 793- 815, 1984.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. arXiv preprint arXiv:2108.0488. 04884, 2021.
Mihai Dusmanu, Johannes Schönberger, Sudipta Sinha, and Marc Pollefeys.
visual feature descriptors through adversarial affine subspace embedding. IEEE Conference on Computer Vision and Puttern Recognition, 2021.
Sanghamitra Dutta, Dennis Wei, Hazar Yueksel, Pin- Yu Chen, Sijia Liu, and Kush Varshney. Is there a trade-off between faimess and accuracy? perspective using mismatched hypothesis testing. International Conference on Machine Learning, pp. 2803-2813, 2020.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Faimess through awareness. Innovations in Theoretical Computer Science Conference, pp. 214-226, 2012.
Harrison Edwards and Amos Storkey. Censoring representations with an adversary. arXiv preprint 1rXiv:5511.05897. 2015.
15

---

Published in Transactions on Machine Learning Research (12/2022)
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. Certify- ing and removing disparate impact. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 259-268, 2015.
Kenji Fukumizu, Francis R Bach, and Arthur Gretton. Statistical consistency of kernel canonical correlation analysis. Journal of Machine Learning Research, 8(2), 2007.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. Intiraaaiionnnteettttoionnn International Conference on Machine Learning, 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. Journal of Machine Learning Research, 17(1):2096-200 2016.
Thibaut Le Gouic, Jean-Michel Loubes, and Philippe Rigollet. Projection to fairness in statistical learning. arXiv preprint arXiv:2005.1122. 2020.
Vincent Grari, Oualid El Hajouji, Sylvain Lamprier, and Marcin Detyniecki. Learning unbiased representations via Rényi minimization. arXiv preprint (xXi::200900388,, 2020.
Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical dependence with Hilbert-Schmidt norms. International Conference Algorithmic Learning Theory, pp. 63-77, 2005a.
Arthur Gretton, Ralf Herbrich, Alexander Smola, Olivier Bousquet, and Bernhard Schölkopf. Kernel methods for measuring independence. Journal of Machine Learning Research, 6(12):005--2229, 2005b.
Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel method for the two-sample-problem. Advances in Neural Information Processing Systems, 19, 2006.
Arthur Gretton, Kenji Fukumizu, Choon Hui Teo, Le Song, Bernhard Schölkopf, and Alexander J. Smola. A kernel statistical test of independence. Advances in Neural Information Processing Systems, 20:585 592, 2007.
Peter Hall and Ker-Chau Li. On almost linearity of low dimensional projections from high dimensional data. The Annals of Statistics, pp. 867-889, 1993.
Jihun Hamm. Minimax filter: Learning to preserve privacy from inference attacks. Journal of Machine Learning Research, 18(1):400444744 2017.
Moritz Hardt, Eric Price, Nati Srebro, et al. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, pp. 3315-3323, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Wassily Hoeffding. Probability incqualities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pp. 409-426. Springer, 1994.
Jean Jacod and Philip Protter. Probability essentials. Springer Science & Business Media, 2012.
Effrosini Kokiopoulou, Jie Chen, and Yousef Saad. Trace optimization and eigenproblems in dimension reduction methods. Numerical Linear Algebra with Applications, 18(3):565-602. 2011. 2011.
Yazhe Ii, Roman Pogodin, Danica Sutherland, and Arthur Gretton. Self-supervised learning with kernel dependence maximization. arXiv preprint (xXiv:2206608322 2021.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. IEEE International Conference on Computer Vision, 2015.
Francesco Locatello, Gabriele Abbati, Thomas Rainforth, Stefan Bauer, Bernhard Schölkopf, and Olivier Bachem. On the fairness of disentangled representations. Advances in Neural Information Processing Systems, pp. 1461 1-16244. 2019.
16

---

Published in Transactions on Machine Learning Research (12/2022)
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv: 2017.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable repre- sentations. arXiv preprini arXiv: 1802.0630, 2018.
Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax pareto fairness: multi objective perspective. International Conference on Machine Learning, pp. 6755-6764, 2050.
Jérémic Mary, Clément Calauzenes, and Noureddine El Karoui. Fairness-aware learning for continuous attributes and treatments. International Conference on Machine Learning, pp. 4382-4391, 2019.
Daniel McNamara, Cheng Soon Ong, and Robert C Williamson, Costs and benefits of fair representation learning. 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. Conference on Fairness, Accountability and Transparency, pp. 107-118, 2018.
Adrián Pérez-Suay, Valero Laparra, Gonzalo Mateo- Gareía, Jordi Muñoz-Mari, Luis Gómez-Chova, and Gustau Camps-Valls, Fair kernel learning. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 339-355, 2017.
Novi Quadrianto, Viktoriia Sharmanska, and Oliver Thomas. Discovering fair representations in the data domain. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8227-8236, 2019.
Ali Rahimi, Benjamin Recht, et al. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems, 3(4):5, 2007.
Proteck Roy and Vishnu Naresh Boddeti. Mitigating information leakage in image representations: A maximum entropy approach. IEEE Conference on Computer Vision and Pattern Recognition, 2019.
Salvatore Ruggieri. Using t-closeness anonymity control for non-discrimination. Transactions on Data Privacy, 7 (2):99-129, 2014.
Bashir Sadeghi, Runyi Yu, and Vishnu Boddeti. On the global optima of kernelized adversarial representation learning. IEEE International Conference Computer Vision, pp. 7971-79799 2019.
Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Nonlinear component analysis as kernel eigen- value problem. Neural Computation, 1095):199-1319, 1998.
John Shawe-Taylor and Nello Cristianini. Kernel methods for pattern analysis. Cambridge University Press, 2004.
Jiaming Song, Pratyusha Kalluri, Aditya Grover, Shengjia Zhao, and Stefano Ermon. Learning controllable fair representations. International Conference on Artificial Intelligence and Statistics, 2019.
Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet. Universality, characteristic kernels and RKHS embedding of measures. Journal of Machine Learning Research, 12(7), 2011.
Robert L Strawderman. The symmetric eigenvalue problem (classics in applied mathematics, number 20). Journal of the American Statistical Association, 94(446):657, 1999.
Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. IEEE Conference on Computer Vision and Pattern Recognition, 2017.
Taihong Xiao, Yi-Hsuan Tsai, Kihyuk Sohn, Manmohan Chandraker, and Ming-Hsuan Yang. Adversarial learning of privacy-preservie and tosk-oriented representations. Proceedings of the AAAI Conference Artificial Intelligence, pp. 12434-12441, 2020.
Qizhe Xie, Zihang Dai, Yulun Du, Eduard Hovy, and Graham Neubig. Controllable invariance through adversarial feature learning. Advances in Neural Information Processing Systems, pp. 585-596. 2017.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. International Conference on Machine Learning, pp. 325-333, 2013.
17

---

Published in Transactions on Machine Learning Research (12/2022)
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. AAAT/ACM Conference AI, Ethics, and Society, 2018.
Han Zhao. Costs and benefits of wasserstein fair regression. arXiv preprint arXiv:2106.08812, 2021.
Han Zhao and Geoffrey J Gordon. Inherent tradeoff's in learning fair representations. arXiv preprint arXiv:1906.08386, 2019.
Han Zhao, Shanghang Zhang, Guanhang Wu, José MF Moura, Joao P Costeira, and Geoffrey Gordon. Adversarial multiple source domain adaptation. Advances in Neural Information Processing Systems, 31:8559-8577 2018.
Han Zhao, Jianfeng Chi, Yuan Tian, and Geoffrey J Gordon. Trade-offs and guarantees of adversarial representation learning for information obfuscation. arXiv preprint arXiv: 190p.07902, 2019a.
Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon. On learning invariant representations for domain adaptation. International Conference on Machine Learning, pp. 7523-7532, 2019b.
Han Zhao, Chen Dan, Bryon Aragam, Tommi S Jaakkola, Geoffrey J Gordon, and Pradeep Ravikumar. Fundamental limits and tradeoffs in invariant representation learning, arXiv preprint arXiv:2012.107133 2020.
18

---

Published in Transactions on Machine Learning Research (12/2022)
A A Population Expression for Definition in 7
A population expression for Dep( 2, S) in 7 is given in the following.
Sep(Z, Ex,sx''s k(X, Exx [6 [X') Es.s (xs(X, 80]
where (X', 5²) is independent of (X, with the same distribution as pxs-
Proof. We first note that this population expression is inspired by that of HSIC (Gretton et al. 2005a).
Consider the operator Esx induced by the linear functional Cov (a (x(X), (s)))(()) = (Bs, Es Then, it follows that
Dep(Z.S)
Cov (f(())Bs(S))
j=1
Σ
(Bs. Esx fil
jml Rg
Σ
(Bs DssxissfJle
BeEul
(a)
Esx fili
Σ (Exx Jj. Esxli)m
Σ Cov (X)(X), (Esxf))())
j=1
Σ Cov (f)(X), (ks(: S), Esxfilns)
1=
Σ Cov Cox(X)))) ks(S",
Σ Cov Bxx.s) Es (S, S')]
Σ Ex.SX's
Ex [x (x)) Es.s (S,
Ex,s (X) Ex (X')) [kg (S, }
where (a) is due Parseval relation for orthonormal basis and (b) is from the definition of Σsx-
B Proof of Lemma 1
Lemma 1. Let Kx. Ks E R be Gram matrices corresponding to Hx and H.s respectively, i.e., (Kx)g
xx (I:;, a.)) and (Ks);; = (s,, 8j), where covariance is empirically estimated as
Cov (1)()),ss(S)
1 Σ (2,)))8(s3) ~ n i=1
n ΣΣ (())))s(
19

---

Published in Transactions on Machine Learning Research (12/2022)
It follows that, the corresponding empirical estimation for Dep (Z, is
1 |0KxHLsl
Dep"" (Z
(20)
where H = I, - nn 1 is the centering matrix, and Ls is a full column-rank matrix in which L Ks (Cholesky factorization), and Ks is the Gram matrix corresponding to Hss Furthermore, the empirical estimator in has a bias of ((n-1) and a convergence rate of O(n-1/3)
are given. Invoking Proof. Firstly, let us reconstruct the orthonormal set Us when n ii.d. observations { representer theorem, for two arbitrary elements 3 and Bm in Uss we have
(Bi, Bm)
Σ askk(B),))) ) Σ mkk((B..))
Hs
= Σ
j=1 1=1
a Ksn
(L L
where Lg E Raxy is full column-rant matrix and K L is the Cholesky factorization of Ks. As result, searching for 3 E Us is equivalent to searching for L' Ug where Uy is any complete orthonormal set for R. Using empirical expression for covariance, we get
Dep (Z,
Σ AgEMs j=l
fa(x)Bs(ss) n2
Ef (z.)
(s(sK)
1=1
k=1
Σ
Σ
Kx Ksa 1 0 Kx1, K saa {
2
n
LgacM j=l
Σ
0 K Kx KxHKaa
LyEE j=l
Σ
07 K H Ls LLs
Lacu j=l
0 Kx HxH
CEL,, J=1
Σ CEll,
OOK x HLSS13
|Kx
=
where f(x) @ @(A:x(23) X), kx (2n, x)) T and + 0..
20

---

Published in Transactions on Machine Learning Research (12/2022)
We now show that the bias of Dep"I"(Z,, SZ for estimating De, in 9 is O (+). To achieve this, split Dep (2, S) into three terms as,
| HLsle
Tr HK
n
n²
OKx [ (1- Ks -1- KxO7}
Ir
n
TKK
n²
n
1 O
(21)
n
Let oj denote the set of all p-tuples drawn without replacement from (1...... nJ. Moreover, let O = 00,''....01''" e grx and (A) denote the element of an arbitrary matrix A at i-th row and j-th column. Then, it follows that (I):
Tr Kx O :
E Tr OKx
Tr { a Ks]]
E
Σ (aaafii
Σ (exaa)s(Kg)
(b.j)Ec
n!
Ex,s (5), + (n (n- Exss.'' (((())
=
n k=1
n!
(nn) + (n 2)!
Ex.xxx (X(X))((())SSSSSS
(22)
where (X,S) and S'' are independently drawn from the joint distribution pxs-
(II:
E O1"K'00
E T Kx0
Kx
k=
E
1
asa
E
(a mi (Ks (Ks)mj
k=
m=1
i= j=1
E
(Ks) +
Σ
(ao Omom (Ks)mn
(m.j)Ec
Σ
(een )m +
Σ
(x my (K (Ks)
1=1
(m.i)Ecs
(m.j))e
21

---

Published in Transactions on Machine Learning Research (12/2022)
Σ (oxaa) mi (Ks)m
(m.t..))e
n! Σ
Ex,s [f(())s(5,S)]
+
Ex [+(())As(S
(n 2)! 1m
n!
Ex,.xx (X)s))
n
2)
n!!
Ex,.Xx, (x(()))(())ss(((5
(n 2)
k=1
n!!
Σ
Ex,s
(n 3)!
k=1
n!
O(n²)
Ex,s BX
(23)
(n 3)!
(II):
E OK"KI'"' Ks1
Σ k=1
E
1 Kx0 0 K xx11xx11K55
Σ
E
[17
a T 11 Ks1
ΣE E
Σ
(araf si (m)
k=1
k.imm
= O(n²) +
Σ
(((K))
k=
(i..m.))Ect
n!!
= O(n3) +
Ex (fa(X)) Ex [f((X') Es.s (Ss(S,
(n 4)!
(24)
Using above calculations together with Lemma 2 lead to
Dep( 2, = DDep emp (2, + + (1)
We now obtain the convergence of (2,S). Consider the decomposition in 21 together with and 24 Let ag == Kx0,, then follows that
22
23
P (Dep(2,.5) Dep (2,S) 2 t)
Ex.s.x's' (x(()))((XX))(((555) (n 2)
(y +0 (0!1)
P
Σ
Σ
2 at
n! k= (K.))
n2
+
Ex,s (XX")
(n 3)!
Σ
Σ
)mi (Ks) +
2
n!
k= (i..m)Ee
+ P
Σ k=
Ex (X)] Ex [xx) Es.sy (S, S')]
22

---

Published in Transactions on Machine Learning Research (12/2022)
4)1
( 2 (1 a b)b
Σ
+
n! k=1 (f).m,)))e?
where a, > and a + For convenience, we omit the term O (*) and add back in the last stage.
Define Ç := == SX and consider the following U-statisties (Hoeffding 1994)
(n-2)!
ui Si)
( (K()))))))))
n!! (t.))Ee
(n - -3)!
u2(Si, Sy: Sm)
Σ
(a m ( s)
n!!
(b.im)Eeg k=1
(n - ()!
wa(Si Szz Sm. Ci)
Σ
(aaa)) (K))
n!
(s..m..))ee km
Then, from Hoeffding's 's inequality (Hoeffding 1994) it follows that
2, 2
2,
201 201-----9922
PP [Dep(2, Z, Dep (2, 2 1 S
+
4r M
where we assumed that (-.-) is bounded by one and (X,) is bounded by for any 1, 1, and ,, n. Further, if 0.22 S 1, holds that
2,,
2,22,2
211 a 2
-0 30 1-322"""
6.-
Consequently, we have
-a3.2
(|Dep( S) Dep (Z,S) 2t 2 < 6e
,2M2
Therefore, with probability least - 6, it holds
p2 log//o066/0
Dep( () - Dep smp (2,5)l S
+ +0
(25)
an
71
C Proof of Theorem 2
Theorem 2. Let Z = f(X) be an arbitrary representation of the input data, where f E Hx. Then, there exist an invertible Borel function h, such that, h belongs to Ap.
Proof. Recall that the space of disentangled representation is
Ar { f+) ft.Js fs Hx. Cov (f(()) + firx = ō2.
where > 0. Let Xx denote the identity operator from Hx to Hx. We claim that h = " hrr), where
(fi.fims
(fr.frux
Go
(fr,
G - Go -1/2
h f = Σ
Jim (Exx + x 1/2 f3, =j=1, -1,.rr
m=
23

---

Published in Transactions on Machine Learning Research (12/2022)
is the desired invertible transformation. To this, construct
Cov (M)()((()))))))(((()))) + +7(,, o f. fixx o (Exx + 71x) hy o fl
Dim (Exx + 71x)
1/2 Ji, Σ
gikk Exxx +xxx) +xlx) 1/2 ʃj
k=1
Hx
Fim 9ikk Ji)xx (G G) = -i.j
The inverse of h is h = 1 .,] where
H = _/
N1 o Σ m=1
hym (Exx + 71x) hy. Vj = 1,
D Proof of Theorem 3
Theorem 3. Consider the operator Esx to be induced by the bi-linear functional Cov(a(X), Bs()) (Esxa, Bs)Hg and define E and Σxx. similarly. Then, a global optimizer for the optimization problem in the eigenfunctions corresponding to the r largest eigenvalues of the following generalized cigenvalue problem
is
((1- A) Ey Eyx A -i Esx) f = (Exx +71x) f,
(26)
where is the disentanglement regularization parameter defined in (10), and Σ* is the adjoint of Σ.
Proof. Consider S)) in
S)
Σ
Σ
Covè (f)(X),
Beells j=l
Σ
Σ
Esx
j= Beeus
= Σ
Esxf
where the last step is due to Parseval's identity for orthonormal basis set. Similarly, we have dep( Y) Ey Recall that Z = f(X) = [X), ... fr(X),, then it follows that
J(f(X) (1 (1-1) A) Σ
Ey S - Σ
Esx f1l
==1
#=1
= (1-1) Σ
Σyxff Σxxfily
X Σ
EExx fy. Esxfilns
jml
Σ (b.
~ Esx)
where En is the adjoint operator of E. Further, note that Cov (f((X); Cov()((X), is equal to (xi,Exx]i) Hxx
As result,
the optimization problem in 26 can be restated as
sup
Σ (fs, ((1 xj2ixxExx A Xixx) falxx
1sikksr
=6.
24

---

Published in Transactions on Machine Learning Research (12/2022)
where Ix denotes identity operator from H.x Hx. This optimization problem is known generalized Rayleigh
quotient (Strawderman) 1999) and a possible solution to it is given by the eigenfunctions corresponding to the r largest cigenvalues of the following generalized problem
- Ayxxxxxx Sexyyxxx-Exxx250 ExsDsxx (Exx +xlx)
E Proofs of Theorem and Corollary 4.1
Theorem 4. Let the Cholesky factorization of Kx Kx = Lx Lx where Lx E RRuxd (d S ni) full column- rank matrix, Let I d, then solution to 13) is
(X) = Opt [x (21, X). 1x (2n, X))²
where opt L and the columns of U eigenvectors corresponding the largest eigenvalues of the following generalized eigenvalue problem.
1, + + u.
x ((1 A)HK, X -U
(27)
Further, the supremum value of 13 equal to Ej=1 Tjs where , are r largest eigenvalues of 14
Proof. Consider the Cholesky factorization, Kx Lx where Lx is a full column-rank matrix. Using the
representer theorem, the disentanglement property in (TO) can be expressed
Cov (J((),, [2(X)) + (Ji,J))H
f((x)f, (wx)
1
Σ f((xx)
(emm) + (fér
173
m=1
n
Kx (x 04
Kx 2m) Σ
Kx Kx
+ (fe. firux
n
n²
n
(Kx (Kx0,)
0
K 1 K +7
Σ 1 Σ (:;
n
n
Hx
0. KxHKxx0 + + 0 Kx0;
1 07 Lx (L HLx + ny 15
6i.j-
As a result, f E A, is equivalent to
@Lx
L L HLx + 71) e I,.
where θ [0,,...,,]] E Rrxn
25

---

Published in Transactions on Machine Learning Research (12/2022)
Let V O and consider the optimization problem in (13):
sup {(1 - X) Dep (f(X), - Dep (fe)
(f(X).
SEA.
sup SEA. n² (1- 2) |k |0KxHLs||f]
sup SEA. n²
max Tr [T(OLxBLje] vrcV=I, n²
1 Tr ( BV}
max vicV=I, n²
(28)
where the second step is due to 99) and
B
(1
Lx
It is shown in Kokiopoulou al. 2011) that an optimizer of 28 is any matrix U whose columns are eigenvectors corresponding to r largest eigenvalues of generalized problem
Bu = Cu
(29)
and the maximum value is the summation of largest eigenvalues. Once U determined, then, any O in which O = U is optimal @ (denoted Drt) Note that Opp is not unique and has general form of
θ = (LX) U Au, R(Ao) S (L*)
However, setting Au to zero would lead to minimum norm for θ Therefore, we opt 0 = L.
Corollary 4.1. Embedding Dimensionality: A useful corollary of Theorem is characterizing optimal embedding dimensionality as a function of trade-off parameter, A:
OP (A) arg sup sup (Jomp (f:A)1 number of non-negative eigenvalues of 14 osrsi SEA,
Proof. From proof of Theorem we know that
sup
{(1 A) (f( (f(X), (f(Xm = T3
fEA.
where [TI,-.. } are cigenvalues of the generalized problem in (14) in decreasing order. It follows immediately that
arg sup
T5
number of non-negative elements of {mi,"-,, m.).
F Proof of Theorem 5
Theorem 5. Assume that ky and ky are bounded by one and (7, S M for any j = 1,,..,, and 1, .,...
......,, n for
which f (fi,...,fr) Ar. Then, for any and
< 1, with probability at least we have
(6/8)
1
sup J(F,)) sup Jemp jemp(f.)) (f,A) < <rM SEA.
+ O
0.22²
JEAr
Optimmll V unique.
26

---

Published in Transactions on Machine Learning Research (12/2022)
Proof. Recall that in the proof of Lemma | we have shown that with probability at least 1 - 6, the following inequality holds
22 log(6/o) 0.22 n
+ +0 1
S)) - omp (2, &
Using the same reasoning for dep(Z, Y), with probability at least
8, we have
1og(//0) + + -
Dep(Z, Y) - smp ( -
0.22 n
Since J(f(X)) (1 A) ( Aeep( S) and jemp follows that with probability at least 1 8,
jomp (f(X)) (1 - A) dep cmp (Z, Y) d (Z, S), it
log 1og(6/o) 0.22 n
+ O (1)
(J( Jom (f. X) S rMy
12
We complete the proof by noting that, the following incquality holds for any bounded J and jemp;
sup fEA,
J(f sup yEA.
JemP (f, sup yEA.
(J(f - Jemp (f - ({)))-
G Optimality of Target Task Performance in K Topt
We show that maximizing dep(S(XX,)))) Y) can lead to a representation 2 that is sufficient to result in the optimal Bayes prediction of Y.
Theorem 6. Let f be the optimal encoder by maximizing (e)(f Y). where y - O and Hy is a linear RKHS. Then, there exist W E igd xr and E Rdd such that (x) + b the Bayes estimator, i.c.,
Ex,y [[ b- --1
inf Borel
Ex,y [[](X)= Y
= E [ X] Y
Proof. We only prove this theorem for the empirical version due to its convergence to the population counterpart. The optimal Bayes estimator can be the composition of the kernelized encoder 2 = f(X) and a linear regressor on top of it. More specifically, y W (X) + b can approach to E|Y X] if we optimize f. W, and b all together. This is because f Hxx can approximate any Borel function (due to the universality of Hxx and, since r 2 dy. W can be surjective. Let := [=1,-.. zn] E RR and := ......., .y]] IRd,xx, xn, Further, let 2 and ğ be the centered (i.e., mean subtracted) version of and Y. respectively. We firstly optimize b for any given f. r, and W:
bept = arg min
W z; + 1
π
1
n W
yi
z4.
n
11
Then, optimizing over W would lead to
min
wz
1/2
= - min 1 WT - 8T13
W
1 - - PTT
=1|2 &-
= min
W
1 | 8T = y
2 1
P2 P
n
27

---

Published in Transactions on Machine Learning Research (12/2022)
where Pz denotes the orthogonal projector onto the column space of Z" and possible minimizer is W (Z" (Z")ly y or equivalently Wopt = Y (Z)1. Since the MSE loss a function the range (column space) of Z we
can consider only 2" with orthonormal columns or equivalently = I,- In this setting, it holds Pz 2 Z.
Now, consider optimizing f(X) @ xxx (x1, ( kx (æ,, x)]". We have, Z OKxH where H is the centering matrix. Let V = - eT and C = HLx then it follows that
1
|
|| P2 111 =
P2 P F Tr O'
min @ x 6 =nI,
max @ HK or=
1
Y
n
cVV
| n²
1
max cV=,, HOKXHY
n
Y
|
Tr TT[V
max
VTCV=I, n
n
j=1
where A Ay are largest eigenvalues of the following generalized problem
Buu = X Cuu
and B, : LŞYTÝ This resembles the eigenvalue problem in Section E
equation 29
where À = 0, 7y is
linear RKHS and + 0.
]
H Deficiency of Mean-Squared Error as A Measure of Dependence
Theorem. Let Hy contain all Borel functions, S be de-dimensional RV, and Ls(:)) be MSE loss. Then,
Z arg sugsup [ss
inf Ex,s [Ls (gs (Z), (2), E Z E[S].
Proof. Let St (gs(Z)), and (E[S) Z denote the i-th entries of S, 9s (Z), and E|$| Z), respectively. Then, it follows that
ds
Ex.s Lss (gs (Z), gsEHs
inf
inf Hss
Ex.s ((gs(Z)); s:)²
ds
Ex.s ((ETS) 21); - S:)
==1
Es ((E[S)) ) - Var (Si).
where the second step is due to the optimality of conditional mean (i.c., Bayes estimation) for MSE (Jacod & Protter
2012) and the last step is because independence between Z and S leads to an upper bound on MSE. Therefore, if Z E arg sup (inf Σx,s LLs (gs ()]}, then E|S Z = E[S]. On the other hand, if E[S Z] E[S], then it follows immediately that Z E arg finf Ex.s [Ls (gs (Z),
This theorem implies that an optimal adversary does not necessarily lead to a representation Z that is statistically independent of S, but rather leads to being mean independent of the representation Z.
28


Reviews:
[{"review_id": "qGnc37IZol", "reviewer": "Reviewer_Web1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- The results in this paper are strong and non-trivial. It is very interesting to see that the RKHS formulation leads to closed form results.\n- The method is very general and can be applied to lots of settings.\n- The proofs in this paper are comprehensive and easy to follow.\n- This topic (invariant representation learning) is very relevant.\n\n# Weaknesses\n\nOverall, I believe that the strengths of this paper outweighs its weaknesses. Nevertheless, here are several points that should be addressed by the authors\n\n## Claims in the introduction are a bit too strong?\n\nThe paper claims that this paper derives \"a closed-form solution for the global optima of the underlying optimization problem...\" However, it should be stated that this closed-form optimum only holds for a non-standard objective function (Dep), and requires that the empirical risk function and the invariance constraint use the same function (Dep). While I don't think that this hurts the results of the paper, the authors may wish to tone down the language used in the introduction and abstract.\n\n## Properties of Dep are not explored\n\nThe `Dep` function introduced by the authors is motivated to be a tractable version of the HSIC function. The authors discuss the desirable properties of HSIC (i.e. it is zero when the two functions are independent) but they do not discuss how the `Dep` approximation affects these properties. (This point is related to the first point: I think that the author's claims in the introduction are somewhat incomplete since the \"exact tradeoff\" is not totally exact - due to the Dep approximation - and the authors never quantify how much this approximation affects their guarantees.)\n\n## How does Theorem 6 support the claims in Section 5.2?\n\nIn Section 5.2, the authors argue that optimizing the proposed Dep objective function can achieve the Bayes estimator, and demonstrate this with Theorem 6. I was not able to connect the dots between how Theorem 6 implies this claim. The Theorem states that \"there exists a representation `\\boldsymbol f^*`\" that achieves the Bayes estimator; however, it does not state that optimizing the proposed objective function yields `\\boldsymbol f^*`.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates a general-purpose invariant representation learning setup (usable for domain adaptation, fairness applications, etc.) where the class of functions for the representation are restricted to an RKHS. The authors demonstrate that it is possible to derive Pareto-optimal models in closed form (where Pareto-optimality balances predictive performance versus invariance). The authors further derive rates of convergence.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# Critical changes\n\n- The HSIC-IRL method is not mentioned in the related work. It seems highly related to your proposed method (is the only difference using Dep instead of HSIC?). Please explain how your method differs from HSIC-IRL.\n- Explain how the `Dep` approximation to HSIC affects the guarantees of HSIC.\n- Clarify how Theorem 6 implies the claims in Section 5.2\n\n# Minor changes:\n\n- You use the phrase \"modes of dependence\" frequently. However, I have no idea what this means; it is never defined.                                                                                                                                                                                                                                                                             \n- The convergence rate proofs require `f` to be bounded. However, this will not be the case generally if using a universal RKHS. Please comment about why this assumption is okay.                                                                                                                                                                                            \n- It is worth mentioning in the paper that Dep, unlike HSIC and other metrics, is asymmetric.\n- `\\boldsymbol K_S` (below equation 9) is not defined.\n- Theorem 3: what is `f` (not bolded)?\n- Figure 2: Why do you use `Cov` and not `Dep` in the diagram?", "broader_impact_concerns": "One of the primary motivations for this method is fair representation learning (in the form of demographic parity). Many who have studied algorithmic fairness have mentioned that this can be a flawed notion of fairness (e.g. https://arxiv.org/abs/1610.07524 and https://arxiv.org/abs/1610.02413). It is worth mentioning this fact in the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Eqj9AQjKXN", "reviewer": "Reviewer_tLLR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- Good descriptions of/comparisons to related work, including how the proposed method differs from them\n- Elegant, principled formulation\n- Clearly written and generally well organized\n\n### Weaknesses\n- Some details in the experimental setup are missing and/or nonstandard. If $r^{Opt}(\\lambda)$ provides a better tradeoff than $r^{Opt}(0)$ (shown in Section 6.7, Figure 5a), then the experiments/figures in Section 6.6 should also use the former. Additionally, setting $r=1$ does not capture the full complexity of $K\\mbox{-}\\mathcal{T}_{Opt}$ ; for example Equation (10) becomes trivial. The authors should confirm that empirical findings on real datasets still hold when $r>1$.\n- Organization: The paper's presentation would be improved greatly if proof sketches/methods were included in the main text (e.g. Hoeffding's inequality, generalized Rayleigh quotient)\n- The Introduction motivates invariant representation learning with multiple applications (privacy, multi-domain generalization). However, real-world experiments only focus on the use case of demographic parity.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the tradeoff between utility and independence when learning representations for classification/regression tasks. Given a dataset $X$, the goal is to learn a representation $f(X)$ which predicts a target $Y$ while remaining invariant w.r.t attributes $S$. By assuming the encoder belongs to a reproducing kernel Hilbert space (RKHS) and defining a modified dependence measure based on Hilbert-Schmidt Independence Criterion (HSIC), the authors characterize an exact closed-form tradeoff between these two competing desiderata. The paper then describes an efficient, approximate implementation and shows that the proposed method attains a better empirical tradeoff than previous approaches on synthetic and real-world datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Critical\n- Include experiments/figures in Section 6.6 that vary $r$ rather than setting $r=1$ or $r=r^{Opt}(0)$ \n- Include proof sketches in the main text\n- Implementation details: describe how neural architectures for ARL were selected. Are the number of network parameters comparable to the number of kernel parameters for $K\\mbox{-}\\mathcal{T}_{Opt}$?\n- In addition to Figures 3-4, since Equation (11) characterizes the tradeoff between $Dep(Z, Y)$ and $Dep(Z, S)$ it would be good to include this tradeoff in Section 6.6\n\n### Non-Critical\n- Renaming the Invariant Representation Learning optimization problem may help avoid confusion with Inverse Reinforcement Learning, which uses the same acronym.\n- If possible, it would be good to calculate theoretical upper/lower bounds for this experimental setup, and include them in Figures 3-4\n- Include additional experiments on applications other than demographic parity (e.g. privacy, multi-domain generalization)\n\n### Typos\n- \"reverse of a non-parametric measure\" should be \"negative of a non-parametric measure\"\n- \"performs as optimum as\" should be \"performs as optimally as\"\n", "broader_impact_concerns": "No major concerns, but the authors could comment on the distinction between characterizing tradeoffs and designing models/datasets to obtain specific invariance/fairness properties", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nFVGg2fwJ5", "reviewer": "Reviewer_LPRL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "First, I stress that I am completely new to the IRL problem and this review is an educated guess. \n\n# Strengths :\n\n- The paper is well-written from my perspective, in sense that it introduces the problem in an understandable way for the non-expert, and the different steps are motivated. \n- From what I can tell, the experimental section is fairly expanded and validate the proposed approach in various ways. \n- While I did not proofread the appendices in details, proofs seem well-written and I did not identify a major flaw at first glance. \n\n# Weaknesses : \n- As far as I understand, the proposed model deviates quite significantly from the initial IRL problem. While each step is motivated, and the result satisfactory, I cannot assess if the resulting problem is, or is not, \"too simplified\" or \"too different\". In particular, I guess that using the same type of loss for the terms $(Z,Y)$ and $(Z,S)$ is important for the tractability of the solution and I cannot assess whether this is a reasonable setting or not. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In its seminal form, the Invariance Representation Learning (IRL) consists of finding an encoder $f$ and a model $g$ that would minimize \n$$ L(g(f(X)), Y) $$\nunder a constraint $D(f(X), S) < \\epsilon$, where \n- $(X,Y,S)$ is a joint distribution of observations, labels and semantic attributes (e.g. $X$ is some person, $S$ their gender, and $Y$ an math score for a job offer).\n- Minimization is understood in expectation w.r.t. this joint distribution\n- $D$ is a correlation-like loss measuring the dependency between the representation $Z = f(X)$ and the semantic attribute $S$, and $\\epsilon$ a control parameter. Typically, setting $\\epsilon = 0$ would enforce that the representation $f(X)$ (hence the model $g \\circ f (X)$) is independent of the semantic attribute $S$. \n\nWhile interesting in itself, this problem is hard to handle from both an analytic and computational perspective. In order to overcome this issue, the authors consider a different (though similar model), that eventually reads \n\n$$\\sup_{f_1,\\dots,f_r \\in A_r} (1 - \\lambda) D(f(X), Y) - \\lambda D(f(X), S), $$\n\nwhere \n- $\\lambda \\in (0,1)$ is a tradeoff parameter\n- $D(Z, S) = \\sum_{j=1}^r \\sum_\\beta \\mathrm{Cov}(f_j(Z), \\beta(S))$, where $r$ is (roughly) an embedding dimension (that can be chosen optimally), the $\\beta$s wander an orthonormal basis of a universal RKHS, \n- $A_r$ denotes a space of functions $(f_1,\\dots, f_r)$ that encourage the disantanglement of the $(Z_j)_{j=1}^r$ (through an additional parameter $\\gamma$). The $f_j$ belong to an RKHS. \n\nTherefore, the proposer model tends to learn a representation $Z = f(X)$ that has roughly independent coordinates, that is correlated to $Y$ while being independent of $S$, as much as possible. \n\nThe authors demonstrate the practicability of their formalism, thanks to the representer theorem in RKHS, most expression boils down to matrix manipulation and a solution of their problem can be estimated by solving an eigenvalue problem (Thm 4). \nThe authors showcase their approach through different numerical experiments on synthetic and real-life datasets.  \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I do not feel qualified to request major changes. \n\nOn the minor remark / clarification side : \n\n- In Eq. (1), in which sense the inequality $D(f(X), S) \\leq \\epsilon$ should hold? Is this a.e., or in expectation ? \n- In Eq. (2), shouln't the right braket $]$ in $\\mathbb{E}_{XY}$ end after the term $D(f(X), S)$? And also, shouldn't the expectation be taken with respect to the join law $(X, Y, S)$ and not only $(X,Y)$ ? ", "broader_impact_concerns": "From my understanding, the Invariant Representation Learning field is intrinsically related to ethical question, as (one of) its goal is to design models that can be guaranteed to be insensitive (to some extend) to attribute such as gender, age, etc. \nI think this work proposes an improvement in this direction and may have some impact in fairness/ethic-ML etc. (though I'm not an expert on those topics either). Perhaps a specific paragraph on this kind of question may be worth it (though the related work section is already fairly instructive on that matter). ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)