Generating Fair Universal Representations using Adversarial Models
Peter Kairouz Jiachun Liao Chong Huang Maunil Vyas Monica Welfert Lalitha Sankar




Generating Fair Universal Representations using Adversarial Models
    Yusuf Said Eroglu, Fatih Erden, and Ismail Guvenc

Department of Electrical and Computer Engineering, North Carolina State University, Raleigh, NC

Email: {yeroglu, ferden, iguvenc}@ncsu.edu
This work is supported in part by NSF CNS award 1422062.

    December 30, 2023
============================================================================================================================================================================================================================================================

./



We present a data-driven framework for learning fair universal representations (FUR) that guarantee statistical fairness for any learning task that may not be known a priori. 
Our framework leverages recent advances in adversarial learning to allow a data holder to learn representations in which a set of sensitive attributes are decoupled from the rest of the dataset. We formulate this as a constrained minimax game between an encoder and an adversary where the constraint ensures a measure of usefulness (utility) of the representation. The resulting problem is that of censoring, i.e., finding a representation that is least informative about the sensitive attributes given a utility constraint. For appropriately chosen adversarial loss functions, our censoring framework precisely clarifies the optimal adversarial strategy against strong information-theoretic adversaries; it also achieves the fairness measure of demographic parity for the resulting constrained representations. We evaluate the performance of our proposed framework on both synthetic and publicly available datasets.

For these datasets, we use two tradeoff measures: censoring vs. representation fidelity and fairness vs. utility for downstream tasks, to amply demonstrate that multiple sensitive features can be effectively censored even as the resulting fair representations ensure accuracy for multiple downstream tasks.













Fair universal representations, algorithmic fairness, generative adversarial networks, minimax games. 








§ INTRODUCTION




The use of data-driven machine learning (ML) has recently seen unprecedented success in a variety of automated decision-making systems including facial recognition, natural language processing, mortgage lending, and even parole prediction. The success of these approaches hinges on the availability of large datasets that often include sensitive personal information. 
It has been shown that models learned from such datasets can inherit 
societal bias and discrimination patterns <cit.> and learn sensitive features even when they are not explicitly used during training <cit.>. 


Concerns about the fairness, bias, and privacy of learning algorithms have led to a growing body of research focused on both defining meaningful fairness measures and designing algorithms with such guarantees. 





A key challenge in algorithmic fairness is the quantification of disparate treatment and impact – legal notions developed to ensure that societal decisions neither hinder nor discriminate against specific groups. Addressing this has broadly lead to two classes of measures: (i) group fairness measures which require similar outcomes for all groups <cit.>; (ii) individual fairness measures which require treating similar individuals 
similarly <cit.>. Approaches combining both fairness requirements have also been considered <cit.>. In the context of supervised learning of intended tasks (our setting here), two key group fairness measures have emerged <cit.>: (i) demographic parity (DemP) which requires predicted outcomes to be independent of the sensitive features, and (ii) equalized odds (EO) wherein such an independence holds only when conditioned on the true outcome. The EO measure was introduced to ensure accurate predictions within groups, a limitation of DemP <cit.>.




Three distinct approaches have been considered to enforce fairness in learning: 
in-processing, pre-processing, and post-processing. In-processing approaches are most commonly used in the supervised setting where the learning objective is known (e.g., <cit.>); the resulting trained model guarantees fairness for the specific objective. 
Pre-processing generally produces fair representations of data tuned for a chosen learning objective <cit.> while post-processing provides fairness by properly altering decision outputs <cit.>. 


Recently, censoring has emerged as a compelling pre-processing approach wherein protected features (e.g., race, gender, and their correlates) are actively decorrelated from the rest of the data to explicitly limit their effect on decisions. Censoring is inspired by information-theoretic privacy methods to limit leakage of sensitive features
<cit.> and can be achieved in practice using generative adversarial networks (GANs) <cit.>. 

Thus far, censoring for fairness has largely focused on learning fair predictors <cit.>. 





















Our Contributions: Taking a preprocessing approach, the main contribution of this work is to use censoring to generate fair representations that are universal. These are representations from which the sensitive features have been actively decoupled and can be universally used for a variety of a priori unknown learning tasks. We show that such fair universal representations (FURs) can assure DemP group fairness 
for all downstream predictions (from the data processing inequality). 

We now detail our contributions:


  * We present a framework for learning FURs as a constrained minimax game between an encoder[referred to interchangeably throughout the paper as fair encoder or generator or decorrelator] and an adversary, where the encoder generates a noisy representation of the original data, subject to a distortion constraint, 
to thwart an adversary that actively tries to infer the sensitive features (see Fig. <ref>).  There has been recent work on using adversarial methods to generate transferable fair representations <cit.>; our universal FUR approach, while similar in philosophy, goes a step further by enforcing a hard distortion constraint that allows better control of the learned representations, and therefore, better downstream utility guarantees. 
Algorithmically, we showcase how Lagrange penalty methods <cit.> can be leveraged to enforce the hard constraint in a GAN-setting[Recently TensorFlow updated its package to allow enforcing hard constraints <cit.> using a similar approach.].


  * Building on existing definitions of fair predictors, we formally define demographic parity for FRs.  We use censoring (of the sensitive features) to ensure DemP FRs and provide information-theoretic assurances on both. Censoring methods, used often for assuring information-theoretic privacy of sensitive features when releasing data (e.g., <cit.>), can also ensure DemP fairness (relative to the sensitive feature). Building on this, we formally define censored representations (Definition <ref>) for the setting when adversaries are limited to practical ML models and loss functions. This has a broader value in auditing fairness/censoring guarantees.


    


  * Our prior work <cit.> shows that the constrained FUR minimax game captures a range of adversarial actions through the choice of loss functions and identifies the corresponding information-theoretic optimal adversarial strategies. 


Focusing here on high-dimensional Gaussian mixture models with independent components, we present the optimal additive Gaussian noise distribution that minimizes the adversary's probability of detecting the mixture class (sensitive feature), i.e., the game-theoretic optimal under the strongest MAP (maximum a posteriori) adversary. We then use normalized mutual information estimates to show that the empirical FUR framework, using neural networks and log-loss, performs very well relative to this game-theoretic optimal.  




  * Our most important contribution is in illustrating the utility of FURs for multiple publicly available datasets including the
	UCI Adult <cit.>, 
	UTKFace <cit.>,  
	GENKI <cit.>,
	and HAR <cit.> datasets. 
	Our visual results demonstrate our success in creating high quality representations that increasingly erase the sensitive attributes with decreasing fidelity requirements. In contrast to state-of-the-art <cit.>, our theoretical framework and experiments are the first to include non-binary sensitive attributes, multiple downstream tasks, as well as hard distortion constraints. Our results show that one can still learn high accuracy DemP (and even EO) fair classifiers from DemP FURs. In particular, via the UCI dataset, that is often used in fair ML analyses, we showcase the advantage of our approach relative to related approaches (e.g., <cit.>,  <cit.>).
	
	
	Our results also straddle a wide range of values for the chosen fairness measure (DemP) and include perfect fairness, in contrast to the above works.  


    
































































































 








    




	







    

































































































 

























The remainder of our paper is organized as follows. We set up the problem and review known measures for fair predictors in Section <ref>. In Section  <ref>, we formalize our FUR model, introduce definitions for censored and fair representations, and highlight the theoretical guarantees of this approach. In Section <ref>, we present theoretical results for datasets modeled as multi-dimensional Gaussian mixtures. Finally, we showcase the performance of the FUR framework on the UCI Adult, UTKFace, GENKI, and HAR datasets in Section <ref>. 
Proofs for the key results are in the appendix. All proofs that build on prior results in <cit.> can be found in an extended version <cit.>. 
Finally, details of the FUR architecture for all datasets are in the accompanying supplementary material.









§ PRELIMINARIES







Consider a dataset 𝒟 with n entries where each entry is a random tuple (S,X,Y)∈𝒮×𝒳×𝒴 where S, X, and Y are sensitive, non-sensitive, and target (non-sensitive) features, respectively, and Ŷ∈𝒴 is a predictor of Y.

Note that S and Y can be a collection of features or labels (e.g., S can be gender, race, sexual orientation, or a combination of these, while Y could be age, facial expression, etc.); for ease of writing, we use the term variable to denote both single and multiple features/labels. 


Instances of X, S, and Y are denoted by x, s and y, respectively. The entries (X,S,Y) of 𝒟 are independent and identically distributed (i.i.d.)
according to P(X,S,Y). 


Recent results on algorithmic fairness guarantee that, for a specific target Y, the prediction of a machine learning model is accurate with respect to (w.r.t.) Y but unbiased w.r.t. the sensitive S. While more than two dozen measures for fairness have been proposed, two oft-used fairness measures are demographic parity and equalized odds (and variants thereof). 

Demographic parity (DemP) ensures complete independence between the prediction of the target Ŷ and the sensitive S; this notion of fairness favors utility the least, especially when Y and S are correlated <cit.>. Equalized odds (EO) enforces this independence conditioned on Y, thereby ensuring equal rates for true and false positives (when Y is binary) for all demographics. We now define DemP and EO formally (for binary S and Y as originally introduced). These definitions can be generalized to the non-binary setting and we do so in the sequel for fair representations. 









A predictor f(S,X)=Ŷ satisfies 

    
  * demographic parity (DemP) w.r.t. S, if Ŷ⊥ S, i.e., 

=2mu

    Pr(Ŷ=1|S=1)=Pr(Ŷ=1|S=0)

    
  * equalized odds (EO) w.r.t. (S,Y), if Ŷ⊥ S|Y, for y∈{0, 1}:
    

    Pr(Ŷ=1|S=1, Y=y)=Pr(Ŷ=1|S=0, Y=y).









In the following section, we present our FUR framework which includes definitions for both demographically fair and censored representations.

We now define censoring and fairness for representations. Our censoring definition clarifies the representation that 
best limits an adversary from inferring S. We then define DemP for FRs; we combine the two definitions to show how and when adversarial learning can help ensure demographic parity.  


A representation X_r of X is censored w.r.t. the sensitive features S 
against a learning adversary h(·), whose performance is evaluated via a loss function ℓ(h(X_r),S), if for an optimal adversarial strategy h^*=_h𝔼[ℓ(h(X_r),S)],

    𝔼[ℓ(h^*(g(·)),S)] ≤𝔼[ℓ(h^*(X_r),S)],

where g(·) is any (randomized) function of X (or (X,S)) and the expectation is over h, g, X, and S.






The above definition suggests that the best censored representation X_r is the least informative about S to an adversary whose inferential action is captured by a loss function ℓ(·,·), i.e., the average loss is the worst for X_r than for any other arbitrary function g(·). While the comparison in (<ref>) is w.r.t. the best h^*(X_r) for X_r, choosing the optimal h(·) for any g(·) will only serve as a lower bound to the left side of (<ref>).


We now define DemP for representations; we then prove that a demographically fair representation X_r guarantees that any downstream algorithm using X_r satisfies DemP w.r.t. S. 



For (X,S)∈𝒳×𝒮, a representation X_r=g(X,S)∈𝒳_r satisfies demographic parity w.r.t. S if for any x_r∈𝒳_r and s,s'∈𝒮


    Pr(X_r=x_r|S=s)=Pr(X_r=x_r|S=s')

where g:𝒳×𝒮→𝒳_r is any (possibly randomized) function.












If X_r=g(X,S) satisfies demographic parity w.r.t. S, then any algorithm f:𝒳_r →𝒴 satisfies demographic parity w.r.t. S.

The proof of Theorem <ref> follows from the data-processing inequality of mutual information as detailed in Appendix <ref>.

 Note that equalized odds in Def. <ref> explicitly involves a downstream task, and therefore, the design of an EO fair X_r needs to include a predictor explicitly. In contrast to the FUR setting considered here, such targeted representations and the ensuing fair predictors provide guarantees only for specific target Y. In this limited context, however, one can still define an X_r as ensuring EO w.r.t. to (S,Y) if Ŷ(X_r)⊥ S|Y.




One simple approach to obtain a fair/censored representation X_r is by choosing X_r=N where N ⊥ (X,S). 
However, such an X_r has no utility (quantified, for example, via downstream task accuracy). The design of X_r has to ensure utility, and thus, there is a tradeoff between guaranteeing fairness/censoring and assuring a desired level of utility. We now quantify such tradeoffs using FUR framework. 










§ FURS VIA GENERATIVE ADVERSARIAL MODELS






Formally, the FUR model consists of two components, an encoder and an adversary, as shown in Fig. <ref>. The goal of the encoder g:𝒳×𝒮→𝒳_r is to actively eliminate the dependence between S and X while that of the adversary h:𝒳_r →𝒮 is to infer S. In general, g(X,S) is a randomized mapping that outputs a representation X_r = g(X,S). Note that S may not always be available to the curator; however, it will always affect the design of g via the adversarial training process. For brevity, we henceforth write g(·) to include both possibilities (just X or (X,S) as inputs). 
On the other hand, the role of the adversary is captured via h(X_r), which is the adversarial decision rule 
in inferring the sensitive variable S as Ŝ=h(X_r=g(·)) from the representation g(·). In general, the hypothesis h can be a hard decision rule under which h(g(·)) is a direct estimate of S or a soft decision rule under which h(g(·)) = P_h(·|g(·)) is a distribution over 𝒮.

To quantify the adversary's performance, we use a loss function ℓ(h(g(X=x,S=s)),S=s) defined for every pair (x,s). Thus, the adversary's expected loss w.r.t. X and S is L(h, g)≜𝔼[ℓ(h(g(·)),S)], where the expectation is taken over P(X,S) and the randomness in g and h.
To ensure utility, we introduce a constraint on the fidelity of X_r via a distortion function 

d(x_r,x), which measures the goodness of X_r = x_r w.r.t. X = x. Ensuring statistical utility, in turn, requires constraining the average distortion 𝔼[d(g(·),X)], where the expectation is taken over P(X,S) and the randomness in g.



















































 §.§ FUR: Framework and Theoretical Results

To publish a fair representation X_r, the data curator wishes to learn an encoder g that guarantees censoring (i.e., it is difficult for the adversary to learn S from X_r), and therefore, fair X_r under DemP, as well as utility (g guarantees bounded distortion of X). In contrast, for a fixed g, the adversary would like to find a (potentially randomized) function h that minimizes its expected loss, or equivalently maximizes the negative expected loss. This leads to a constrained minimax game between the encoder and the adversary given by

    min_g(·)max_h(·) -𝔼[ℓ(h(g(·)),S)],  s.t. 𝔼[d(g(·),X)]≤ D.

where D≥0 determines the distortion constraint on X_r. The optimization in (<ref>) highlights that the input to g depends on whether the curator has access to both (X,S) or just X. Having access to both (X,S)

in general will yield a better decorrelator (e.g., see Section <ref> for the UCI dataset).













Finally, without the constraint in (<ref>), the optimal X_r=g(·)⊥ S. One can approximate this in practice via arbitrarily large distortions as we show in Proposition <ref>; as a setup to these results, we first 


define censoring and fairness for representations. Our censoring definition clarifies the representation that 
best limits an adversary from inferring S. We then define DemP for FRs; we combine the two definitions to show how and when adversarial learning can help ensure demographic parity.  


A representation X_r of X is censored w.r.t. the sensitive features S 
against a learning adversary h(·), whose performance is evaluated via a loss function ℓ(h(X_r),S), if for an optimal adversarial strategy h^*=_h𝔼[ℓ(h(X_r),S)],

    𝔼[ℓ(h^*(g(·)),S)] ≤𝔼[ℓ(h^*(X_r),S)],

where g(·) is any (randomized) function of X (or (X,S)) and the expectation is over h, g, X, and S.






The above definition suggests that the best censored representation X_r is the least informative about S to an adversary whose inferential action is captured by a loss function ℓ(·,·), i.e., the average loss is the worst for X_r than for any other arbitrary function g(·). While the comparison in (<ref>) is w.r.t. the best h^*(X_r) for X_r, choosing the optimal h(·) for any g(·) will only serve as a lower bound to the left side of (<ref>).


We now define DemP for representations; we then prove that a demographically fair representation X_r guarantees that any downstream algorithm using X_r satisfies DemP w.r.t. S. In the following, we assume that X, and therefore, X_r are discrete random variables with arbitrarily large alphabets; however, the definition below can be extended to continuous-valued X and X_r by considering all Borel subsets and an appropriately defined measure on the space. 



For (X,S)∈𝒳×𝒮, a representation X_r=g(X,S)∈𝒳_r satisfies demographic parity w.r.t. S if for any x_r∈𝒳_r and s,s'∈𝒮


    Pr(X_r=x_r|S=s)=Pr(X_r=x_r|S=s')

where g:𝒳×𝒮→𝒳_r is any (possibly randomized) function.












If X_r=g(X,S) satisfies demographic parity w.r.t. S, then any algorithm f:𝒳_r →𝒴 satisfies demographic parity w.r.t. S.


0
The proof of Theorem <ref> follows from a direct application of the data-processing inequality for mutual information since (X,S)-X_r-Y form a Markov chain; details can be found in <cit.>. 

1 The proof of Theorem <ref> follows from the data-processing inequality of mutual information as detailed in Appendix <ref>. 

 Note that equalized odds in Def. <ref> explicitly involves a downstream task, and therefore, the design of an EO fair X_r needs to include a predictor explicitly. In contrast to the FUR setting considered here, such targeted representations and the ensuing fair predictors provide guarantees only for specific target Y. In this limited context, however, one can still define an X_r as ensuring EO w.r.t. to (S,Y) if Ŷ(X_r)⊥ S|Y.




One simple approach to obtain a fair/censored representation X_r is by choosing X_r=N where N ⊥ (X,S). 
However, such an X_r has no utility (quantified, for example, via downstream task accuracy). The design of X_r has to ensure utility, and thus, there is a tradeoff between guaranteeing fairness/censoring and assuring a desired level of utility. We now quantify such tradeoffs using FUR framework. 




For sufficiently large distortion bound D, (<ref>) yields a universal representation X_r censored w.r.t. to S.

 




The proof follows by observing that for sufficiently large D, X_r can be arbitrarily noisy, reducing (<ref>) to an unconstrained optimization.

For this X_r with h^*=_h𝔼[ℓ(h(X_r),S)], 


    𝔼[ℓ(h^*(X_r),S)]    =-min_g(·)max_h(·)-𝔼[ℓ(h(g(·)),S)]
       ≥𝔼[ℓ(h^*(g(·)),S)],

thus satisfying Definition <ref>. 









The FUR framework in (<ref>) places no restrictions on the adversary. Indeed, different loss functions and decision rules lead to different adversarial models (see Table <ref>). This versatility to a large class of (inferring) adversarial models is captured by the last entry in Table <ref> by using the recently introduced tunable α-loss <cit.>, defined for α∈ (0,1) ∪ (1,∞) as :

    ℓ_α (h(g(·)),s) =α/α  - 1( 1- P_h(s|g(·))^α-1/α)
 
with continuous extensions at α=1 and α=∞ (the loss simplifies to a constant for α=0). Note that the loss in (<ref>) operates on a soft decision P_h(·|·), the output of the adversary h. 

By tuning α∈ [0,∞], α-loss captures a variety of information-theoretic adversaries as listed in Table <ref> (see also <cit.>):
 
(i) a hard-decision adversary for α=∞ captured by ℓ_∞(h(g(·)),s) = 1-Pr[h(g(·)) = s][For α=∞, α-loss reduces to probability of error, for which the optimal rule that minimizes the expected loss is the maximal a posteriori (MAP) estimation, a hard decision. The same rule results when minimizing the 0-1 loss which is given by 𝕀(h(g(·))≠ s) where 𝕀 is the indicator function.], and 
 
(ii) a soft-decision adversary for α=1 via the oft-used log-loss  ℓ_1(h(g(·)),s) = -logP_h(s|g(·)) (this follows directly by applying L'Hôpital's rule).


(iii) Values of α>1 allow interpolating between the NP-hard to implement MAP rule (α=∞) and log-loss (α=1) and allow some robustness to noisy data <cit.>. On the other hand, choosing α<1 leads to more convex losses than log-loss (α=1/2 yields a soft exponential loss used in boosting algorithms) that are more sensitive to outliers <cit.>. 

For any encoder g(·), the following proposition (see also the last row of Table <ref>) summarizes the optimal P^*_h(s|g(·)) under α-loss.  




















For a fixed g, under α-loss, the optimal adversary decision rule that minimizes the expected loss is a `α-tilted' conditional distribution
P^*_h(s|g(·)) = P(s|g(·))^α/∑_s∈𝒮 P(s|g(·))^α. For α=1 and α=∞, we obtain the optimal strategies for log-loss and 0-1 loss, respectively, as the true conditional distribution and the maximal a posteriori (MAP) estimator. Then, (<ref>) reduces to


min_g(·) -H^A_α(S|g(·)), 
where H^A_α(·|·)[H^A_α(U|V)≜ 1/(1-α)log(∑_u,vP_U,V^α(u,v))] is the Arimoto conditional entropy. 


Proposition <ref> states that if the adversary uses ℓ_∞, 
(<ref>) simplifies to min_g(·) P(g(·))max_s∈ S P(s|g(·))-1, i.e., we choose the most likely s for every g(·) (the MAP rule) <cit.>.



On the other hand, if the adversary uses log-loss, 

(<ref>) simplifies to min_g(·)I(g(·);S) for any prior on S, 
where I(g(·);S) is the mutual information (MI) between g(·) and S. More generally, using α-loss in (<ref>), the optimal P_h^* in Proposition <ref> simplifies the objective in (<ref>) to min_g(·)I_α^A(g(·);S), where I_α^A(g(·);S) is the Arimoto MI[I_α^A(g(·);S)=H_α(S)-H_α^A(S|g(·)) where H_α(S)≜ H_α^A(S) is the Rényi entropy of order α and is also the unconditioned α-Arimoto entropy.] of order α. These MIs can be effective proxies for guaranteeing DemP FURs, since they are minimized only when S ⊥ g(·), thus leading to the following theorem.



























































Under α-loss, for all α, (<ref>) enforces fairness subject to a distortion constraint. As the distortion increases, the ensuing fairness guarantee approaches ideal DemP. 





Proposition <ref> 
was proved in <cit.>; Theorem <ref> involves similar arguments to Theorem <ref>. 0
All proofs can be found in <cit.>. 1 We combine the proofs for Proposition <ref> 
and Theorem <ref> in Appendix <ref>. 
Many notions of fairness (cf. Definition <ref>) require computing conditional probabilities for every sample x to ensure independence, and thus, are not easy to optimize in a data-driven fashion. The FUR framework via loss functions captures mutual information-like surrogates for such independence conditions; to this end, Theorem <ref> justifies using α-loss (and thus, log-loss too) as a proxy for enforcing fairness. 

We remark that mutual information (MI) is a common surrogate fairness measure for demographic/statistical parity <cit.>. In  <cit.>, the authors use MI for both fairness and the distortion measure leading to an (non-convex) information bottleneck problem; we recover this formulation by choosing d(x,x_r)=-log p(x_r|x). Thus the FUR framework is more general and allows choosing application-dependent meaningful fidelity measures (for example, different measures of representation similarity are used in natural language processing and healthcare data).  
Finally, we remark that the optimal adversarial strategy in Proposition <ref> requires estimating a posterior; as described in Section <ref>, in practice, one can use deep learning models for h and g to do so.




A predominant approach in the literature in the context of fair representations is to explicitly include the intended classification/prediction task, i.e., design representations that guarantee DemP for the specific task <cit.>. In fact, the FUR formulation in (<ref>) can be extended to include this case by adding an additional term in the objective function to ensure high accuracy in learning Y. The resulting minimax game is given by




    min_g̃(·),f(·)max_h(·) -   𝔼[ℓ(h(g̃(·)),S)]+λ𝔼[ℓ'(f(g̃(·)),Y)],
    s.t.     𝔼[d(g̃(·),X)]≤ D,






where f(·) is a classifier for a target Y, λ> 0, and g̃(·)[In general, g̃(·) can be a function of both X and S; the dependence on S is implicit when S is not directly available.]  
and h(·) are the encoder and the adversarial classifier, respectively, as in (<ref>).  








Note that the loss functions ℓ(·) and ℓ'(·) can be different.
The setup in (<ref>) involves an additional term ensuring fair classification and is, thus, a more constrained optimization than the FUR framework; in fact, we recover the FUR setup with λ=0. However, even while generating intermediate representations g(·), (<ref>) is primarily intended to design fair classifiers, and therefore, requires knowing the intended tasks on Y. In contrast, our FUR framework allows generating DemP-guaranteeing fair X_r that in turn guarantee DemP fairness to all downstream tasks on any subset of Y.  












One can also design fair classifiers directly without intermediate representations by setting g̃(·)≜Ŷ; such classifiers g̃ can be designed with either DemP or EO guarantees. 


We first consider the more general problem of designing EO-fair predictors/classifiers g̃(·) for the target Y and show that our FUR framework subsumes this problem (and therefore, that of generating DemP predictors/classifiers). Let h be the adversary decision rule to infer S as Ŝ=h(g̃(·)|Y) for every choice of Y via the soft predictor g̃(·)=P_Ŷ|·. 
Then, analogous to (<ref>), the design of a fair predictor/classifier can be formulated as

















    min_g̃(·)max_h(·)  -𝔼[ℓ(h(g̃(·)|Y),S)],  s.t. 𝔼[ℓ(g̃(·),Y)]≤ϵ,

where the expectation now includes Y too. 



Under α-loss, 
the formulation in (<ref>) enforces EO fairness subject to a performance constraint ϵ. As ϵ increases, the ensuing fairness guarantee approaches the ideal EO guarantees achievable by g̃ w.r.t. S and Y. 


0
The proof of Theorem <ref> is similar to that for Theorem <ref> and can be found in <cit.>. 
1 The proof of Theorem <ref> is in Appendix <ref>. Note that the formulation in (<ref>) also holds for generating a fair predictor/classifier satisfying DemP in Definition <ref>. In contrast to EO where the adversary needs both g̃(·) and Y as inputs, for DemP, only g̃(·) is input to the adversary. 

The adversarial models and the resulting game-theoeretic solutions in Table <ref> highlight the formal guarantees of the FUR framework. Recently, Sypherd et al. have demonstrated the robustness of training deep learning models with α-loss to both noise and class imbalances <cit.>, thus promising to be applicable for learning FURs with GANs. The rest of the sequel focuses on data-driven GANs with α=1, i.e., log-loss, to highlight the value of FURs in guaranteeing fairness for multiple downstream tasks relative to the state-of-the-art fair classifiers. Future work will include enhancing such results to include tuning over α.  







 §.§ Data-driven FUR

Thus far, we have focused on a setting where the curator has access to the statistics P(X,S) thereby solving the constrained minimax optimization problem in (<ref>) (game-theoretic version of the FUR formulation) to obtain a g that performs best against a chosen adversary. In practice, P(X,S) is impossible to compute. To this end, we propose a data-driven version of the FUR formulation that allows the data holder to learn a generative decorrelator from an n-sample dataset 𝒟 = {(x_(i),s_(i))}_i = 1^n via a generative model g(X;θ_p) that is parameterized by θ_p. This generative model takes X (or (X,S)) as input and outputs X_r. In the training phase, the data holder learns the optimal parameters θ_p by competing against a computational adversary: a classifier modeled by a neural network h(g(X;θ_p); θ_a) that is parameterized by θ_a. In the evaluation phase, the performance of the learned decorrelation scheme can be tested under a strong adversary that is computationally unbounded and has access to dataset statistics. We follow this procedure in the next section.



While, in theory, the functions h and g can be arbitrary, in practice, they are best approximated by a well-chosen rich hypothesis class. Fig. <ref> illustrates a FUR model in which h and g 
are both modeled as deep neural networks (DNNs). For a fixed h and g, binary S and ℓ=ℓ_1 (log-loss for α=1), the adversary's empirical loss using cross entropy is given by

    L_n(θ_p,θ_a)   =  -1/n∑_i=1^ns_(i)log h(g(x_(i); θ_p);θ_a) 
          +(1-s_(i))log(1-h(g(x_(i); θ_p);θ_a)).






The optimal model parameters (θ_p,θ_a) are then solutions of






    min_θ_pmax_θ_a -L_n(θ_p,θ_a),  s.t. 1/n∑_i=1^nd(g(x_(i);θ_p), x_(i))≤ D.



































































The minimax optimization in (<ref>) is a two-player non-cooperative game between the generative decorrelator and the adversary with strategies θ_p and θ_a, respectively. In practice, for chosen hypothesis classes for g and h (e.g., DNN architectures), we can learn the equilibrium of the game using an iterative algorithm as follows. 
(i) For a fixed θ_p, maximize the negative of the adversary's loss to compute the parameters of h. (ii) Then, minimize the decorrelator's loss (negative adversary loss) to compute θ_p for a fixed h. 

It is crucial to note that the hard distortion constraint in (<ref>) makes our minimax problem different from what has been extensively studied in the literature. 
To incorporate the distortion constraint, we use the penalty method <cit.> to replace the constrained optimization problem by adding a penalty to the objective function. This is done via a penalty parameter ρ_t that captures a measure of violation of the constraint at the t^th iteration. The constrained optimization problem of g is then approximated by a series of unconstrained optimization problems with an objective



    -L_n(θ_p,θ_a)+ρ_t(max{0,1/n∑_i=1^nd(g(x_(i);θ_p), x_(i))-D})^2,

where the penalty coefficient ρ_t decreases with the number of iterations t. 
We note that both the augmented Lagrangian and the penalty methods have similar performance in practice; we chose the penalty method but our results can also be obtained with the augmented Lagrangian method <cit.>.
We provide detailed steps of the algorithm and the parameters for the penalty method in Appendix <ref>; we also clarify our methodology for choosing both ρ_t and the learning rate η_t there. Finally, we note that one can easily generalize (<ref>) to the multi-class setting (non-binary S) using the softmax function; one can also generalize (<ref>) using α-loss.





In the following sections, we detail our results for synthetic multi-dimensional Gaussian mixture data and four publicly available datasets: UCI Adult, UTKFace, GENKI, and HAR.
All code is available via GitHub at <cit.>. 




















§ FUR FOR GAUSSIAN MIXTURE MODELS


In this section, we focus on a setting where S ∈{0, 1} and X is an m-dimensional Gaussian mixture random vector whose mean is dependent on S. Let P(S =1) = q. Let X|S =0 ∼𝒩(-μ, Σ) and X|S =1 ∼𝒩(μ, Σ), where  μ=(μ_1,...,μ_m). We assume that X|S=0 and X|S=1 have the same covariance Σ.




 §.§ Game-Theoretical Approach

We consider a MAP adversary that has access to P(X, S) and g. The goal is to censor X in a way that minimizes the adversary's probability of correctly inferring S from X_r. In order to have a tractable model for the encoder, we mainly focus on affine representations X_r=g(X)=X+ Z+β, where for tractability reasons, we choose Z as a zero-mean multi-dimensional Gaussian random vector independent of X. 
This linear representation enables controlling both the mean and covariance of X_r.
To quantify utility of the privatized data, we use the ℓ_2 distance between X and X_r as a distortion measure to obtain a constraint 𝔼_X,X_r‖X-X_r‖^2≤ D.







We assume that β=(β_1,...,β_m) is a constant parameter vector and Z∼𝒩(0,Σ_p). Building on the analysis in <cit.>, for the standard Gaussian Q(·) function, we can derive the adversary's detection probability P^(G)_d as

    P^(G)_d   = q Q(-  γ 2  + 1 γln(  1  - q   q) ) 
          + (1 - q) Q(-  γ 2  - 1 γln(  1  - q   q) ),

where 
γ=√((2μ)^T(Σ+Σ_p)^-12μ). From the constraint, we have 
𝔼_X,X_r‖X-X_r‖^2= 
‖β‖^2+tr(Σ_p) ≤ D. The mixture Gaussian classification problem, especially for the same covariance for both classes S=0 and S=1, is a tractable problem that has been studied in a variety of settings including communication systems <cit.> and machine learning <cit.>, to name a few. The result in (<ref>) builds directly on <cit.>, and so, for reasons of brevity, we leave it out. 
The following theorem summarizes the optimal noising strategy when X|S and Z are multi-dimensional i.i.d. Gaussians. 







Consider the representation given by g(X)=X+ Z+β, where X|S and Z are Gaussian random vectors with diagonal covariance matrices Σ and Σ_p, respectively, and X|S⊥Z. Let {σ^2_1,...,σ^2_m} and {σ^2_p_1,...,σ^2_p_m} be the diagonal entries of Σ and Σ_p, respectively. The parameters of the minimax optimal censoring mechanism g^* are

    β_i^*=0,   σ^*_p_i^2=(|μ_i|/√(λ^*_0)-σ_i^2)^+,  ∀ i={1,2,...,m},

where λ^*_0, the dual variable enforcing the distortion constraint in (<ref>), is chosen such that ∑_i=1^mσ^*_p_i^2=D.
For this optimal mechanism, the accuracy of the MAP adversary is given by (<ref>) with
γ=2√(∑_i=1^mμ_i^2/(σ_i^2+σ^*_p_i^2)).

The proof of Theorem <ref> is in Appendix <ref>. We observe that when σ^2_i>|μ_i|/√(λ^*_0), no noise is added to the data on this dimension due to the high variance. In contrast, when σ^2_i < |μ_i|/√(λ^*_0), the variance of the noise added to this dimension is proportional to |μ_i|; this is intuitive since a large |μ_i| indicates the two conditionally Gaussian distributions are further away on this dimension, and thus, require more noise to reduce the MAP adversary's inference accuracy. 

We note that we could have considered a more general non-affine model for the encoder. Since synthetic datasets provide a verifiable way to formally evaluate the FUR framework, we chose a simpler affine generative model that is tractable and yields closed-form information-theoretic results, i.e., we can derive the best adversarial decoder. This in turn is helpful in comparing the data-driven approach with the game-theoretic optimal solution on these canonical data models as a much-needed sanity check. Finally, the analysis here can be generalized to correlated Gaussian distributions for each sensitive group and one expects a similar behavior as the features can be whitened when the covariance is the same for both classes.






 §.§ Data-driven Approach

To learn the data-driven representation X_r=g(X)=X+ Z+β using our FUR framework, we assume that g only has access to the dataset 𝒟 with n data samples (not P(X,S)). Computing the optimal g^* is then a learning problem. In the training phase, we learn the parameters θ_p of g by competing against a computational adversary h(g(θ_p);θ_a) modeled by a multi-layer neural network. When convergence is reached, we evaluate the performance of the learned mechanism by comparing with the one obtained from the game-theoretic approach. To quantify the performance of the learned X_r, we compute the accuracy of inferring S under a strong MAP adversary that has access to both the joint distribution of (X, S) and the censoring mechanism.

Since the sensitive variable S is binary, we measure the training loss of the adversary network using the empirical log-loss function in (<ref>). 

We model the encoder using a two-layer neural network with parameters θ_p={β_1, ..., β_m, σ_p_1,..., σ_p_m}, where β_k and σ_p_k represent the mean and standard deviation for each dimension k∈{1,...,m}, respectively. The random noise Z is drawn from a m-dimensional independent zero-mean standard Gaussian distribution such that {σ_p_kZ_k}_k=1^m jointly have a covariance Σ_p=(σ^2_p_1,...,σ^2_p_m). Thus,  X̂_k=X_k+β_k+σ_p_kZ_k. The adversary 
is modeled by a three-layer neural network classifier with leaky ReLU activations. Finally, as detailed in Algorithm <ref>, we use the penalty method to ensure the distortion constraint.






















































































































 §.§ Illustration of Results




We generate two synthetic datasets to illustrate our results; each dataset has 20K training samples and 2K test samples. Each dataset is generated by sampling from an independent multi-dimensional Gaussian mixture model.

The two datasets correspond to two distinct values for the prior P(S=1) as 0.75 and 0.5. Both encoder and adversary are trained via Tensorflow <cit.> using the Adam optimizer <cit.> with a learning rate of 0.005 and a minibatch size of 1000. 


Fig. <ref> illustrates the performance of the learned FUR scheme against a strong theoretical MAP adversary for a 32-dimensional Gaussian mixture model for both P(S = 1)=0.75 and 0.5. We observe that the inference accuracy of the MAP adversary decreases as the distortion increases and asymptotically approaches (as expected) the prior P(S = 1). The encoder obtained via the data-driven approach performs very well when pitted against the MAP adversary (maximum accuracy difference around 0.7 % compared to the theoretical optimal). As another measure of censoring, we estimate the MI of X_r and S using k-nearest neighbor method as detailed below. Normalizing it with its theoretical maximum I(X;S) (i.e., with X_r=X for D=0), in Fig. <ref>, we show that MI Î(X_r;S)/I(X;S) decreases, as expected, when the distortion increases. In other words, for Gaussian mixture data with binary S, the data-driven FUR formulation can learn decorrelation schemes that perform as well as those computed under the game-theoretical FUR formulation where the generative decorrelator has access to the data statistics. 


We estimate MI using the k-nearest neighbor method <cit.>; in particular, for n d-dimensional FUR outputs X_r, we first 
estimate the entropy Ĥ(X_r) as

    Ĥ(X_r) = ψ(N) - ψ(k) + log(c_d) + d/n∑_i=1^n log r_i

where r_i is the distance of the i-th sample x̂_i to its k-th nearest neighbor, ψ is the digamma function (logarithmic derivative of the gamma function Γ(·)), and c_d = π^d/2/Γ(1+d/2). 
We then calculate MI as Î(X_r; S) = Ĥ(X_r) - P(S=1)Ĥ(X_r|S=1) 
- P(S=0)Ĥ(X_r|S=0), 












where P(S=1) and P(S=0) are empirically estimated.










§ FUR  FOR PUBLICLY AVAILABLE DATASETS



We apply our FUR  framework to four real-world datasets, namely,
UCI Adult <cit.>,
UTKFace <cit.>,
GENKI <cit.>, and HAR <cit.>, briefly described below. For all four datasets, we restrict the architecture of h, g, and the downstream predictive models to neural networks. Note that for tabular datasets (e.g., UCI, HAR), boosting methods including decision trees or support vector models achieve at least comparable predictive performance <cit.> but are out of scope of this work. 










(i) The UCI Adult dataset <cit.>

consists of 10 categorical and 4 continuous features and is used to predict a binary salary label (1: salary > 50k or  0: salary ≤ 50k). We choose gender or the tuple (gender, relationship) as the sensitive S, the remaining features except salary as non-sensitive X (Table SIV in the supplement lists all features), and salary as the target Y.


(ii) The UTKFace dataset <cit.> 
consists of more than 20k 200× 200 color images of faces labeled by age, ethnicity, and gender. Individuals in the dataset have ages from 0 to 116 years and are divided into 5 ethnicities: White, Black, Asian, Indian, and others including Hispanic, Latino and Middle Eastern.
We take gender as S, the image as X, and age and ethnicity as two target labels Y. Further, we also restrict the data to contain images for ages between 10 and 65.


(iii) The GENKI dataset <cit.> consists of 1,740 training and 200 test samples. Each data sample is a 16×16 greyscale face image with varying facial expressions.

We choose gender 
as S and the image as X.

(iv) The HAR dataset <cit.> consists of 561 features of motion sensor data collected by a smartphone from 30 subjects performing six activities (walking, walking upstairs, walking downstairs, sitting, standing, laying). Each feature is normalized between -1 and 1. We choose subject identity as S and the features of motion sensor data as X.





























As shown in Definition <ref>, demographic parity requires zero difference between the conditional probabilities of predicting the binary target feature to be positive, i.e., Ŷ=1, given different realizations of the sensitive feature S. In the experiments, we calculate the largest distance between these conditional probabilities given by 

    Δ_DemP=max_s,s'∈𝒮 |P(Ŷ=1|S=s)-P(Ŷ=1|S=s')|

and a smaller value of Δ_DemP implies a better approximation of the demographic parity fairness.




We use the accuracy of predicting S as the measure of censoring. We evaluate the fairness guarantees of X_r by computing the DemP obtained on tasks using Y. To this end, 

 
we compute the following maximal difference as a proxy for DemP in Definition <ref> (includes non-binary Y and S):
=2mu

    Δ_DemP(y)=max_s,s'∈𝒮 |P(Ŷ=y|S=s)-P(Ŷ=y|S=s')|

with smaller values of Δ_DemP(y) suggesting better DemP fairness guarantees. For binary Y, Δ_DemP(y) in (<ref>) simplifies to a single value that we denote as Δ_DemP. In our experiments, we use the empirical frequencies to estimate P(Ŷ=y|S=s) for a chosen (y,s). We illustrate both censoring and fairness results for the abovementioned datasets in the following subsections. Experimental and model details are in the supplement. 




















 
 
























































































































































































































 §.§ Illustration of Results for UCI Adult Dataset



























For the UCI Adult dataset with both categorical and continuous features as shown in Table SIV in the supplement, we consider two cases: 
(i) Case I: binary S by choosing `gender' as sensitive feature  
 
(ii) Case II: non-binary S by considering both `gender' and `relationship' as sensitive. For UCI, `relationship' has 6 distinct values, and therefore, S has 12 possibilities. 

For both cases, `salary' is the binary target Y∈{0,1}, with Y=1 denoting salary >50K. 

Since the two values for Δ_DemP(y) in (<ref>) are the same for binary Y, we write Δ_DemP when illustrating results. 




Case I: Binary Sensitive Feature.


Fig. <ref> illustrates the censoring and fairness performance of the generated X_r for the UCI dataset. For censoring, the performance is evaluated via the tradeoff between the classification accuracies of salary (utility of X_r) and gender (censoring of S). Note that salary accuracy is evaluated as a downstream task via a separately learned classifier that uses X_r while gender accuracy is a measure of performance of the neural network adversary h in the FUR model. We evaluate fairness via the tradeoff between salary accuracy and Δ_DemP. We consider two possible inputs to the encoder g(·) in (<ref>), i.e., only X or both (X,S). 




As illustrated in Fig. <ref>, the baseline[The baseline performances are the salary and gender accuracies as well as Δ_DemP obtained from the original uncensored test dataset.] salary and gender accuracies for the UCI dataset are about 84.5% and 85%, respectively. Further, for the FUR X_r and downstream Ŷ: 

(i) the smallest gender accuracy achievable is about 66%, 20% below its baseline, while the lowest salary accuracy is about 82%, 2.5% below its baseline. Since the likelihood of a male in the original test data is 66%, with increasing distortion, the FUR gender accuracy is as good as a random guess, i.e., the generated X_r hides gender effectively while maintaining high salary accuracy. 

(ii) For the same gender accuracy, using both (X,S) seems useful only in the high utility setting (salary accuracy ≥ 83%). 

From Fig. <ref>, we make the following two observations:


 (i) salary classification accuracy and Δ_DemP have an approximately affine relationship, and when Δ_DemP≈ 0, the salary accuracy is ≥ 79%, i.e., the FUR framework is effective in approaching perfect DemP with a small reduction in utility; 
(ii) the FURs X_r generated from either X or (S,X) lead to similar fairness guarantees.




For Δ_DemP=0.06, state-of-the-art approaches in <cit.> and <cit.> achieve 2% and 2.5% higher salary accuracy than ours, respectively;

however, 
our approach is distinct in achieving 
Δ_DemP≈ 0 with salary accuracy ≥ 79%. 

From Fig. <ref>, we see that gender accuracy saturates at 67% while achieving a salary accuracy of at least 81% for a specific value of distortion bound D, and therefore, test distortion; in turn, this choice of D corresponds in Fig. <ref> to Δ_DemP≈ 0.06. Further reducing Δ_DemP requires further increasing D, thus lowering the salary accuracy to 79% for Δ_DemP≈ 0. This is because classification accuracy captures an average measure of correctness and is dominated by the performance over the majority class. On the other hand, Δ_DemP captures the difference in performance of the intended classifier on each of the two classes. Thus, enforcing fairness via Δ_DemP reduces salary accuracy thereby highlighting the tradeoff between guaranteeing fairness and utility.








We can also evaluate the fairness performance of the generated X_r by using the EO measure in Definition <ref>. Thus, for Y ∈{0,1} where Y=1 when salary >50K, S ∈{0,1} (female:1 and male:0), and Ŷ∈{0,1}, we write Δ_EO(y), ∀ y∈{0,1} as:







=1mu







    Δ_EO(y)≜|P(Ŷ=y|S=0,Y=y) -P(Ŷ=y|S=1,Y=y)|.

=3mu



















Note that for binary Y, as is the case here, (<ref>) is the same as the definition of EO in (<ref>). 
From Fig. <ref>, which plots salary accuracy vs. DemP or EO measures of fairness, we observe that while the salary accuracy is above 82.4%, 
the values of Δ_EO(1) and Δ_EO(0) decrease to 0.0007 and 0.0254, respectively. 

To understand the significance of these results, we compare against the state-of-the-art in <cit.>, wherein fair salary classifiers for both DemP and EO measures, referred to as LAFTR-DP[Learned Adversarially Fair and Transferable Representations (LAFTR)] and LAFTR-EO, respectively, are learned for the UCI dataset. For the LAFTR-DP, the authors also compute the resulting EO of the DemP classifier. As a preamble to the following comparisons, we note that fair predictors, trained on specific tasks, will do at least as well as the same predictors learned on fair representations.




We make the following observations: (i) when Δ_EO(1)+Δ_EO(0)=0.04[<cit.> introduced an EO measure as Δ_EO≜Δ_EO(1)+Δ_EO(0)],

our salary accuracy is 1.3% smaller than that achieved by LAFTR-DP (cf. Fig. 2(b) in <cit.>), but our minimal achieved value of Δ_EO(1)+Δ_EO(0) is only 72% of that achieved by LAFTR-DP and is the same as the value achieved by LAFTR-EO, which uses EO as the fairness metric to train a salary classifier; (ii) the decrease of Δ_EO(1)+Δ_EO(0) is even larger than Δ_DemP. That is, even though the representation is generated to satisfy DemP, it can also provide competitive downstream EO fairness guarantees. This, in turn, justifies the rationality of generating fair representations under DemP. 




Case II: Non-binary Sensitive Feature.

Figs. <ref> and <ref> illustrate the censoring and fairness performances of the generated X_r in hiding `gender' and `relationship', respectively, while preserving `salary' information. 

Fig. <ref> illustrates the tradeoff between salary and sensitive feature S accuracies when S is either gender, or relationship, or both. 

From Fig. <ref>, we observe that while the salary accuracy is above 79%, the classification accuracies of gender and/or relationship are about 66% (Fig. <ref>), 45% (Fig. <ref>) and 41% (Fig. <ref>), respectively. Note that the probabilities of male, husband, and the combination (male, husband) are 66%, 40% and 40%, respectively, in the original test data. Therefore, while the salary accuracy is preserved at 79%, the inferences of gender, relationship, and combination (gender, relationship) approach random guessing with these priors. Thus, our FUR framework can effectively hide one or more sensitive features. However, suppressing multiple correlated sensitive features comes at a cost of a reduction in salary accuracy. 
Thus, comparing Figs. <ref> and <ref>, we see a maximal reduction of 3% in salary accuracy for a given gender accuracy[In Figs., <ref> and <ref>, the baseline performances are different because for Case II, the feature variable X does not contain `relationship'.].




For Case II, Figs. <ref> and <ref> illustrate the tradeoffs between the salary accuracy and Δ_DemP for S chosen as gender or relationship or both.

We observe that while salary accuracy is above 94% of the baseline performance, 
the value of Δ_DemP is dropped to 25% for gender and to about 34% for both relationship and their combination. In short, X_r works well in decorrelating gender and relationship both separately and jointly without affecting downstream classifier performance. From Fig. <ref>, we observe that the value of Δ_DemP for the combination is almost the same as that for relationship. In addition, comparing the results in Figs. <ref> and <ref>, for any given Δ_DemP for gender, the salary accuracy in Case II is about 1% lower

than that in Case I; this can be viewed as the cost of eliminating a potentially sensitive feature (relationship) that is also correlated with the target feature (see also, footnote <ref>).
Finally, comparing the results in Figs. <ref> and <ref>, for any given salary accuracy, Δ_DemP for gender in Case II is about 0.25 
 higher

than that in Case I; this can be viewed as the effect of using non-binary sensitive features on Δ_DemP, now defined as the maximum over all values taken by the non-binary sensitive feature.








 §.§ Illustration of Results for UTKFace Dataset

In the UTKFace dataset, the face images are the non-sensitive X. We choose `gender' as the sensitive S; focusing on multiple downstream tasks, we consider both ethnicity classification and age regression, for which we choose `ethnicity' or `age' as the target variable Y, respectively. 

For the two downstream applications, the corresponding supports of Y are 𝒴={White, Black, Asian, Indian} and  𝒴={i∈ℤ: 10≤ i≤ 65}=[10,65], respectively. We use the maximum of the DemP measure (defined in (<ref>)) over the support Y, i.e., Δ_DemP= max_y∈𝒴Δ_DemP(y), as the achieved fairness level.







Fig. <ref> illustrates the output X_r for 16 typical[The 16 typical faces covers the 8 possible combination of 2 gender (male and female) and 4 ethnicities (White, Black, Asian and Indian) and includes young, adult and old faces.] faces in the UTKFace dataset for increasing per-pixel distortion.  From Fig. <ref>, we observe that: (i) for a small per-pixel distortion (e.g., 0.003), gender-distinguishing features such as lip color are smoothed out; and (ii) at higher per-pixel distortion (e.g., 0.006), the FUR framework can generate a face with an opposite gender (see the highlighted examples in Fig. <ref>) thereby completely obfuscating this sensitive feature; 
(iii) when the average per-pixel distortion is too large (e.g., 0.01), the representations generated are often too blurred. 


Figs. <ref> and <ref> show the tradeoffs between gender classification accuracy and appropriate measures for ethnicity classification and age regression, respectively. In Fig. <ref>, while gender classification accuracy is about 62% and decreases about 35% from the baseline performance, the classification accuracy of ethnicity is above 74% and only decreases 14% from its baseline performance. Note that in the original testing data, the highest marginal probabilities for gender and ethnicity are 54.6% (likelihood of male) and 43.2% (likelihood of White), respectively. Therefore, gender accuracy is better than a random guess by only 7.4% while ethnicity accuracy is better than a random guess by 30.8%, i.e., the generated X_r hides gender information well while maintaining ethnicity. For age regression, we use the mean absolute error (MAE), i.e., the average absolute difference between the predicted age and the true age, as the utility measure. In Fig. <ref>, we observe that while the classification accuracy for gender is about 62%, which is a 35% decrease from the baseline performance of 94%, the increase in the MAE is 1.5 which is about a 20% increase from the baseline performance of 7.2 years. Fig. <ref> shows the cumulative distribution function (CDF) of the difference between the true and predicted age for various distortions, from which we can see that the drop of the cumulative probability is at most 1%. Thus, the generated FUR guarantees reliable performance for both age and ethnicity prediction; thus, constraining the distortion of the generated X_r can be effective in guaranteeing utility for multiple tasks.


In Figs. <ref> and <ref>, we illustrate the tradeoff between the utility measure and Δ_DemP of the generated X_r in ethnicity classification and age regression, respectively. In Fig. <ref>, we observe that while achieving about 86% of the baseline classification accuracy, the Δ_DemP is reduced

to 0.03, which is 20% of the Δ_DemP=0.14 in the original testing data. 
Table <ref> shows the decrease of Δ_DemP  for each of the four ethnicities as the distortion increases.  
In Fig. <ref>, while preserving 86% of the utility baseline performance, the Δ_DemP, i.e., the maximal value of demographic parity measure over the 56 age values, decreases to 0.015, which is less than 33% of the Δ_DemP=0.046 in the original testing data. Fig. <ref> shows the demographic measure Δ_DemP(y) , y∈[10,65], for various distortions; we observe that when the pixel distortion is 0.01, even while Δ_DemP=0.015, Δ_DemP(y)=0 for 17 distinct ages. That is, the predictions of these 17 ages are completely independent of gender and DemP is achieved for those predictions.








g>yellowc













 §.§ Illustration of Results for GENKI Dataset


For the GENKI dataset, we consider the following two approaches to decorrelating the data (X,S): the feedforward neural
network decorrelator (FNND) and the transposed convolution neural network decorrelator (TCNND). Specific architectural details for both can be found in the supplement. Fig. <ref> illustrates the gender classification accuracy of the adversary for different values of distortion. It can be seen that the adversary's accuracy of classifying S (gender) decreases
as the distortion increases. Given the same distortion value, the FNND achieves lower gender classification accuracy compared to the TCNND. 
An intuitive explanation for this is that the FNND uses both the noise vector and the original image to generate the processed image, while the TCNND generates the noise mask independently of the original image and then adds this mask to the original image in the final step. 



Censoring vs. differential privacy guarantees: For this dataset, in addition to highlighting the role of GAN-like architectures to learn fair representations, we also explore the effect of censoring on assuring privacy of the sensitive (here, gender) feature. 
Differential privacy (DP) has emerged as the gold standard for data privacy <cit.>. 
Thus, one way to censor and privatize data is to add noise with differential privacy guarantees <cit.>. Since the dataset is continuous valued, we consider two types of additive DP noise mechanisms at the pixel level: Gaussian and Laplacian. We vary the variances of the Laplace and Gaussian noise to then obtain a specific local DP guarantee[DP, by definition, guarantees that the output of a differentially private (randomizing) mechanism cannot aid in distinguishing between two neighboring (defined appropriately) datasets. Local DP is stronger than DP in that it provides such a guarantee for any pair of inputs.] building on <cit.>. 
We compute the resulting DP guarantees provided by independent Laplace and Gaussian noise-adding mechanisms for different distortion values. The details are provided in the supplement (see Section SII-B). 
In Fig. <ref>, we compare the gender classification accuracy of the learned FUR schemes with those obtained by adding Laplace or Gaussian noise. 
We see that for the same distortion, the learned FUR schemes achieve much lower gender classification accuracy. In Table <ref>, we observe that even when a large amount of noise is added to each pixel, the privacy risk (ϵ) is still significantly high. Furthermore, such noise levels deteriorate the expression classification accuracy (cf. Fig. <ref>). It is worth noting that the distortion constraint for the FUR framework is an average over the entire image.














Evaluating adversarial performance via mutual information estimation: Our FUR framework offers a scalable way to find a (local) equilibrium in the constrained min-max optimization for certain adversarial attacks (e.g. inference attacks on S using a neural network). Yet the privatized data, through our approach, should be immune to any general attacks and should ultimately achieve the goal of decreasing the correlation between the X_r and S. To this end, we use the estimated MI, using the k-nearest neighbor method as detailed in Section <ref>, to verify that our framework protects S.  





































One noteworthy difficulty is that X, and therefore, X_r are usually high dimensional objects (each image in the GENKI dataset has 256 dimensions), so it is almost impossible to calculate the empirical entropy based on raw data due to the sample complexity.  Thus, we train a neural network that classifies S from the learned data representation to reduce the dimension of the data. We choose the layer before the softmax outputs of the adversary (denoted by X̂_g) to be the feature embedding that has a much lower dimension than the original X_r which still captures the information about S. We use this X̂_g as a surrogate for X_r in (<ref>) to first estimate Ĥ(X̂_g) and then compute Î(X̂_g; S) as the approximate MI between X_r and S.  





We similarly extract an X̂_f by training a neural network that now classifies Y; we then compute Ĥ(X̂_f) from which we obtain Î(X̂_f; Y) as the approximate MI between X_r and Y.  
The details of the common neural network architecture we use to extract X̂_f and X̂_g can be found in the supplement (see Section SII-C).






Utility-fairness tradeoffs: To evaluate the value of the representation generated by the FUR  framework for the GENKI dataset, we consider the task of classifying the facial expression (non-sensitive feature Y) as smiling or non-smiling (i.e., the task that the GENKI dataset was intended for). To this end, we train another CNN (see Fig. S4 in the supplement for architecture details) to perform facial expression classification on datasets processed by different decorrelation schemes. The trained model is then tested on the original test data. In Fig. <ref>, we observe that the expression classification accuracy decreases gradually as the distortion increases. However, even for a large distortion value (5 per image), the expression classification accuracy only decreases by 10%. To make meaningful comparisons using MI, we normalize Î(X̂_f; Y) by Î(X_f;Y) where X_f is the low-dimensional representation of X (=X_r for D=0); we similarly normalize Î(X̂_g; S) by Î(X_g;S) where X_g is defined similarly. As shown in Fig. <ref>, the estimated normalized MI Î(X̂_f; Y)/Î(X_f;Y) decreases at a much slower rate than Î(X̂_g; S)/Î(X_g;S) as the distortion increases thus verifying that X_r preserves relatively more information about Y than it does about S at every distortion level.

Tables <ref> and <ref> present different error rates for the facial expression classifiers trained using data representations created by different decorrelator architectures. For the GENKI dataset, a smiling expression is considered as the positive label for the expression classification task. We observe that as distortion increases, the difference across the two sensitive groups (male vs. female) for each error rate decreases. This implies the classifier's decision is less biased with respect to S when trained using X_r. When D = 5, the differences are quite small. In particular, the FNND architecture performs better in enforcing fairness but suffers from a slightly higher error rate relative to TCNND.
The images processed by FNND are shown in Fig. <ref>. As highlighted in the figure, the dominant features that the decorrelator changes are those that capture gender, namely eyes, nose, mouth, beard, and hair.







 §.§ Illustration of Results for HAR Dataset


For the HAR dataset, we recall that the X features are motion sensor data from 30 subjects performing six different activities; the goal is to classify activity (intended task Y) without revealing subject identity (sensitive S).
In Fig. <ref>, for different values of distortion, we illustrate the accuracy in classifying activity against that of identification. We see that classification accuracy of identity decreases 
as the distortion increases. In fact, when distortion is small (D=2), the identity accuracy is down to 27%. If we increase the distortion to 8, the identity accuracy further decreases to 3.8%. 
However, we note that for an even large distortion value (D=8), the activity classification accuracy only decreases by at most 18%. Finally, in Fig. <ref>, we demonstrate that the estimated normalized mutual information Î(X̂_f; Y)/Î(X_f;Y) decreases at a much slower rate than Î(X̂_g; S)/Î(X_g;S) as the distortion increases, thereby assuring that the adversarial model chosen assures censoring of identity without compromising accuracy of the intended task from X_r. Details on the architecture for the FUR model, the classifier, and for obtaining the representations used to estimate MI can be found in the supplement. 






















§ CONCLUSION


We have introduced an adversarial learning framework with verifiable guarantees for learning generative models that can create censored and fair universal representations for datasets with known sensitive features. The novelty of our approach is in producing representations that are fair with respect to the sensitive features for any a priori unknown downstream learning task. We have shown that our FUR framework allows the data holder to learn the fair encoding scheme (a randomized mapping that decorrelates the sensitive and non-sensitive features) directly from the dataset without requiring access to dataset statistics. 
One of our key results is that for appropriately chosen loss functions, the minimax game generating FURs can provide guarantees against strong information-theoretic adversaries, such as MAP (0-1 loss) and MI (log-loss) adversaries. We have also shown that our framework also allows approaching (ideal) demographic parity fairness using a tunable class of α-loss functions (which includes both log-loss and 0-1 loss) that capture a range of adversarial actions. For the setting with a known classification task, we have also shown that our FUR framework can be modified to approximate either DemP or EO fairness measures. 


Finally, we have also validated the performance of the FUR framework on both synthetic and publicly available real datasets, including Gaussian mixture models, images, and datasets involving a mix of categorical and continuous features. Our results have allowed us to visually highlight three key results: (a) the tradeoff between representation fidelity and censoring guarantees (via accuracy in adversarially learning sensitive features); (b) the tradeoff between the adversarial accuracy in learning the sensitive features and the accuracy of multiple downstream tasks learned from the censored representation for a variety of datasets; and (c) the tradeoff between accuracy for a downstream learning task and the DemP or EO guarantees achieved by a predictor that is learned using a DemP fair representation. Result (c) further suggests that, for some datasets, DemP FURs do not adversely affect the downstream EO guarantees despite lack of access to the task labels Y, where the latter has been highlighted as a limitation of DemP fair predictors <cit.>. However, more work is needed to understand the conditions under which DemP FURs suffice to achieve meaningful EO guarantees. Such an exploration can also clarify if the definition of Δ_DemP as the worst case over all task output values y∈𝒴 and sensitive values s ∈𝒮 is too strong, especially for settings where 𝒴 and/or 𝒮 are large, as our age prediction results suggest for the UTKFace dataset.

 

Going beyond this work, there are several questions that can be addressed. 
An immediate one is to explore the robustness of using α-loss (for α 1) in ensuring censoring and fairness for highly imbalanced datasets. Yet another is to explore the usefulness of FURs for unsupervised tasks building on recent work in <cit.>.

More broadly, it will be interesting to investigate the robustness and convergence guarantees of the generative encoder learned in a data-driven fashion. 














 






 













§ ACKNOWLEDGEMENT

We would also like to thank Prof. Ram Rajagopal and Xiao Chen at Stanford for their help with estimating mutual information for the GENKI and HAR datasets and would like to thank Mit Patel and Harshit Laddha at ASU for their help with the experiments on the UTKFace dataset.







1


 §.§ Proof of Theorem <ref>




A demographically fair encoder g(X,S) ensures that X_r⊥ S,
i.e., the mutual information I(S;X_r)=0. Further, the downstream learning algorithm acts only on X_r to predict Ŷ; thus, (S,X)-X_r-Ŷ form a Markov chain.

From the data processing inequality and non-negativity of mutual information, we have 0≤ I(S;Ŷ)≤ I(S;X_r)=0, i.e.,



S is independent of Ŷ; thus, from Definition <ref>, Ŷ satisfies DemP w.r.t. S.

Finally, from the chain rule and non-negativity of mutual information, we have I(X_r;S_t)=0 for any S_t ⊂ S, i.e., Ŷ satisfies DemP w.r.t. any subset of sensitive features S_t.






§ PROOFS FOR RESULTS IN SECTION <REF>







 §.§ Proofs of Proposition <ref>, Results in Table  <ref>, and Theorem <ref>

In the FUR framework, different loss functions and decision rules lead to different adversarial models. We now prove the optimal adversarial rule for different loss functions in Table <ref>. 



Hard Decision Rules.  When the adversary adopts a hard decision rule, h(g(X)) is an estimate of S. Under this setting, we can choose ℓ(h(g(X)), S) in a variety of ways. For instance, if S is continuous, the adversary can attempt to minimize the difference between the estimated and true sensitive variables using a squared loss (ℓ_2 loss) as

    ℓ(h(g(X)),S)= (h(g(X)) - S)^2.


One can verify that the optimal h^* = 𝔼[S|g(X)], the conditional mean of S given g(X). Then, (<ref>) simplifies to

    min_g(·) - mmse(S|g(X)) = - max_g(·)mmse(S|g(X)),

subject to the distortion constraint and mmse is the minimum mean square error (MMSE). 

Thus, for the ℓ_2 loss, the FUR framework provides censoring guarantees against an MMSE adversary. On the other hand, when S is discrete (e.g., age, gender, etc.), the adversary can maximize its classification accuracy by considering the 0-1 loss <cit.> given by

    ℓ(h(g(X)),S)=
    {[         0 h(g(X))=S;         1           ].

One can verify that the adversary's optimal strategy is the maximum a posteriori probability (MAP) rule: h^* = _s ∈𝒮 P(s|g(X)), with ties broken uniformly at random. For this MAP rule, the objective in (<ref>) reduces to

    min_g(·) - (1 - max_s ∈𝒮 P(s, g(X))) = min _g(·)max_s ∈𝒮 P(s, g(X))  - 1,


i.e., under 0-1 loss, the FUR formulation provides censoring guarantees against a MAP adversary.


Soft Decision Rules.  Instead of a hard decision, we can also consider a broader class of soft decision rules where h(g(X)) is a distribution over 𝒮; i.e., h(g(X)) = P_h(s|g(X)) for s ∈𝒮. We first consider log-loss given by


    ℓ(h(g(X)),s) = log1/P_h(s|g(X)).

In this case, the objective of the adversary simplifies to

    max_h(·)  -𝔼[log1/P_h(s|g(X))] = - H(S|g(X)),

where H(X|Y) is the conditional entropy of X given Y and, given the true posterior P(s|g(X)), P^*_h(s|g(X)) = P(s|g(X)). 

Then, the objective in (<ref>) reduces to

    min_g(·)  - H(S|g(X)) = min_g(·) I(g(X);S) - H(S),


i.e., under log-loss, the FUR formulation is equivalent to using mutual information as the censoring (or privacy) metric.
 

Tunable α-loss family. For ℓ(h(g(x)),s) chosen as α-loss in (<ref>), we have for α∈ (0, ∞),

    max_h(·)  -𝔼[α/α  - 1( 1- P_h(S|g(X))^1 - 1/α)]  =
       α/α-1 (∑_x P(g(x)) max_h(·)∑_s P(s|g(x))  P_h(s|g(x))^1 - 1/α - 1 ),

with limits taken appropriately for α=0,1, and ∞. For each x ∈𝒳 with P(g(x)) > 0, the maximization in (<ref>) can be written as

    max_h(·)     α/α -1 ∑_s ∈𝒮 P(s|g(x)) P_h(s|g(x))^1 - 1/α
    s.t.     ∑_s ∈𝒮 P_h(s|g(x)) = 1, 
        P_h(s|g(x))≥0,   for all  s ∈𝒮.

For α∈ [0, ∞], the optimization in (<ref>) is convex in P_h(s|g(x)). Hence, we can use Karush Kuhn-Tucker (KKT) conditions to solve for the optimal h^*, ignoring the inequality constraint at first and then checking that the resulting h^* satisfies the constraint. Consider the following Lagrangian:

    L(h(·),λ) = α/α -1 ∑_s ∈𝒮    P(s|g(x)) P_h(s|g(x))^1 - 1/α
    
        +    λ(∑_s ∈𝒮  P_h(s|g(x)) - 1).

Noting that P_h(s|g(x)) is a vector of probabilities over all S for a given g(x), for every s, at the optimal h^*(g(x))=P_h^*(s|g(x)), we obtain the following KKT conditions:

    ∇_h(·) L(P_h^*(s|g(x)),λ^*) = 0,   i.e.






    P(s|g(x)) P_h^*(s|g(x))^- 1/α + λ^* = 0,

such that

    ∑_s ∈𝒮 P_h^*(s|g(x)) = 1.

Solving (<ref>) for h^*, we get

    P_h^*(s|g(x)) = λ^' P(s|g(x))^α,


where λ^' = (-1/λ^*)^α. Enforcing (<ref>), we find that λ^' = 1/∑_s ∈𝒮 P(s|g(x))^α, and therefore, the optimal h^* is a `α-tilted' conditional distribution

    P^*_h(s|g(X)) = P(s|g(X))^α/∑_s'∈𝒮 P(s'|g(X))^α.

Thus, for the optimal adversarial strategy P^*_h(s|g(X)) in (<ref>), the objective simplifies as:

    max_h(·)     -𝔼[α/α  - 1( 1- P_h(S|g(X))^1 - 1/α)] 
        = α/1-α(1-exp(1-α/αH_α^A(S|g(X))))

where  H^A_α(U|V) for two discrete random variables (U,V)∼ P_U,V(u,x)

is the Arimoto conditional entropy of order α defined as

    H^A_α(U|V)≜1/(1-α)log(∑_u,vP_U,V^α(u,v)).






The resulting minimax game reduces to

    min_g(·)  I^A_α(S;g(X)) - H_α(S),

where H_α(S) is the Rényi entropy of order α defined as H^A_α(S)≜ 1/(1-α)log(∑_sP_S^α(s)) and we have used the fact that for two discrete random variables (U,V)∼ P_U,V(u,x), the Arimoto MI is I_α(U;V)=H_α(U)-H_α(U|V). As a side-note, we observe that generalizing the Renyi entropy to a conditional form leads to many different formulations and the Arimoto conditional entropy in (<ref>) is one such form introduced by Arimoto <cit.>. 

For α=1, (<ref>) simplifies to (<ref>) since the Arimoto conditional entropy (resp. MI) simplifies to the Shannon conditional entropy (resp. MI) <cit.>. 
From the non-negativity of Arimoto MI I_α^A(S;g(X)), we also have H_α^A(S|g(X))≤ H_α(S) <cit.>



with equality if and only if g(X) is independent of S. Thus, the minimization in (<ref>) serves as a proxy for generating DemP fair representations with perfect DemP achieved when I_α^A=0.


Near perfect DemP is achievable for very large distortions as this allows X_r to be increasingly decoupled from S and X. Indeed, as the bound D in (<ref>) increases, from Proposition <ref>, the FUR formulation in (<ref>) will approach ideal DemP by achieving  I_α^A(S|g(X))≈ 0, thus proving Theorem <ref>. 





































































































 §.§ Proof of Theorem <ref>

The optimization in (<ref>) differs from that in (<ref>) in including the target Y in learning both g and h^⋆. In fact, for a fixed g, one can verify that the optimal adversarial strategy in (<ref>) is the same as (<ref>) with an additional conditioning on Y. Thus, for ℓ=ℓ_α in (<ref>), the optimization in (<ref>) reduces to 



























    min_g(·)  I_α^A(S;g(·)|Y),
     s.t. 𝔼[ℓ(g(·),Y)]≤ϵ.





Since I_α^A(S;g̃(·)|Y)≥ 0




with equality if and only if g(·) ⊥ S|Y, minimizing (<ref>) with α-loss achieves EO. In practice, as the performance constraint ϵ in (<ref>) increases, the FUR formulation in (<ref>) will approach perfect EO of g(·) w.r.t. Y and S by enforcing H_α^A(S|g(S, X),Y)= H_α^A(S|Y).






 §.§ Alternate Minimax Algorithm




























Algorithm <ref> details the steps used to learn the FUR model in a data-driven manner. To incorporate the distortion constraint, we use the penalty method <cit.> 
to replace the constrained optimization problem by a series of unconstrained problems. 
The unconstrained optimization problem is formed by adding a penalty to the objective function as a product of a parameter ρ_t and an appropriate measure of violation of the constraint.  









We start with a large value of ρ_t to enforce distortion from the outset and decrease ρ_t in exponential steps with respect to the number of training epochs. Such a decrease allows enforcing a smaller penalty when the model is closer to convergence. Finally, we also vary the learning rate η_t over training epochs as follows: we pick a small value of η_t at the beginning and compare the relative values of the adversarial loss and the average distortion. We adjust the initial η_t so that the adversarial loss and the distortion penalty values are on a similar scale in the first few epochs during training. When the algorithm terminates, we check the average distortion and manually fine tune the initial η_t and the update rule to make sure the distortion is within bounds after termination. 





























































 §.§ Proof of Theorem <ref>






















Since 𝔼_X,X̂[ d(X̂, X)] =𝔼_X,X̂‖X-X̂‖^2=𝔼‖Z+β‖^2= ‖β‖^2+tr(Σ_p), the distortion constraint implies that ‖β‖^2+tr(Σ_p) ≤ D. Let us consider X̂ = X + Z + β, where β∈ℝ^m and Σ_p is a diagonal covariance whose diagonal entries are given by {σ^2_p_1,...,σ^2_p_m}. Given the MAP adversary's optimal inference accuracy in (<ref>), the objective of the decorrelator is

    min_β,Σ_pP^(G)_d,  s.t. ‖β‖^2+tr(Σ_p) ≤ D.


Define 1/γln1-q/q=η.
After some algebra, the gradient of P^(G)_d w.r.t. γ is given by

    ∂P^(G)_d/∂γ
    =   1/2√(2π)(qe^-(η -  γ/2) ^2/2+(1-q)e^-(η +  γ/2) ^2/2),

which is always positive. Thus, P^(G)_d is monotonically increasing in γ. As a result, (<ref>) is equivalent to













    min_β,σ_p_1^2,...,σ_p_m^2     ∑_i=1^mμ_i^2/σ_i^2+σ_p_i^2,
    s.t.     ‖β‖^2+tr(Σ_p) ≤ D
       σ_p_i^2≥ 0   ∀ i∈{1,2,...m}.


Since a non-zero β does not affect the objective function, the optimal scheme satisfies β=(0,...,0). The Lagrangian is

    L(σ^2_p_1,   ...,σ^2_p_m, λ) 
        =∑_i=1^mμ_i^2/σ_i^2+σ_p_i^2+λ_0 (∑_i=1^mσ_p_i^2-D)-∑_i=1^mλ_iσ_p_i^2,

where λ={λ_0,..., λ_m} denotes the Lagrangian multipliers associated with the constraints.




Since the objective function in (<ref>) is decreasing in σ_p_i^2 for all i,  

∑_i=1^mσ^*_p_i^2=D. By the KKT conditions, we have

    ∂ L(σ^2_p_1,...,σ^2_p_m, λ)/∂σ^2_p_i   |_σ^2_p_i=σ^*_p_i^2, λ=λ^*
       =-μ_i^2/(σ_i^2+σ^*_p_i^2)^2+λ^*_0-λ^*_i=0.

Since λ^*_i, i∈{0,1,...,m} is dual feasible, we have λ^*_i≥ 0, i∈{0,1,...,m}. Therefore

    λ^*_0≥μ_i^2/(σ_i^2+σ^*_p_i^2)^2.


If λ^*_0>μ_i^2/σ_i^4, we have λ^*_0>μ_i^2/(σ_i^2+σ^*_p_i^2)^2. This implies λ^*_i>0. Thus, by complementary slackness, σ^*_p_i^2=0. On the other hand, if λ^*_0<μ_i^2/σ_i^4, we have σ^*_p_i^2>0. Furthermore, by the complementary slackness condition, λ^*_iσ^*_p_i^2=0,∀σ^*_p_i^2. This implies λ^*_i=0, ∀σ^*_p_i^2>0. As a result, for all σ^*_p_i^2>0, we have

    |μ_i|/√(λ^*_0)=σ_i^2+σ^*_p_i^2.


The optimization in (<ref>) is analogous to the well-studied rate-distortion problem for independent Gaussian sources and the optimal solution given by reverse water-filling <cit.>. Using similar techniques, we obtain σ^*_p_i^2=max{|μ_i|/√(λ^*_0)-σ_i^2,0}=(|μ_i|/√(λ^*_0)-σ_i^2)^+ with ∑_i=1^mσ^*_p_i^2=D leading to the results in the theorem. 


































































 §.§ Mutual Information Estimation


Our FUR framework offers a scalable way to find a (local) equilibrium in the constrained min-max optimization, under certain attacks (e.g. attacks based on a neural network). Yet the privatized data, through our approach, should be immune to any general attacks and ultimately achieving the goal of decreasing the correlation between the privatized data and the sensitive labels. Therefore we use the estimated mutual information to certify that the sensitive data indeed is protected via our framework.   

We use the nearest k-th neighbor method<cit.> to estimate the entropy Ĥ given by 

    Ĥ(X̂) = ψ(N) - ψ(k) + log(c_d) + d/N∑_i=1^N log r_i

where r_i is the distance of the i-th sample x̂_i to its k-th nearest neighbor, ψ is the digamma function, c_d = π^d/2/Γ(1+d/2) in Euclidean norm, and N is the number of samples. Notice that X̂ is learned representation and S is the sensitive variable. Then, we calculate the mutual information using Î(X̂; S) = Ĥ(X̂) - Ĥ(X̂|S)

For a binary sensitive variable, we can simplify the empirical MI to

    Î(X̂; S)    = Ĥ(X̂) 
        - ( P(S=1)Ĥ(X̂|S=1) + P(S=0)Ĥ(X̂|S=0) ),

where P(S=1) and P(S=0) can be approximated by the empirical probability.




















One noteworthy difficulty is that X̂ usually lives in high dimensions (e.g. each image has 256 dimensions in GENKI dataset) which is almost impossible to calculate the empirical entropy based on raw data due to the sample complexity. Thus, we train a neural network that classifies the sensitive variable from the learned data representation to reduce the dimension of the data. We choose the layer before the softmax outputs (denoted by X̂_f) to be the feature embedding that has a much lower dimension than original X̂ and also captures the information about the sensitive variable. We use X̂_f as a surrogate of X̂ for estimating the entropy. The resulting approximate MI is  

    Î(X̂_f; S)     = Ĥ(X̂_f) - Ĥ(X̂_f|S) 
    
        = Ĥ(X̂_f) - ( P(S=1)Ĥ(X̂_f|S=1) 
                   + P(S=0)Ĥ(X̂_f|S=0) ).

Following the same manner, the MI between the learned representation X̂ and the label Y is approximated by Î(X̂_f; Y), where X̂_f is the feature embedding that represents a privatized image X̂. 

For the GENKI dataset, we construct a CNN initialized by two conv blocks, then followed by two fully connected (FC) layers, and lastly ended with two neurons having the softmax activations. In each conv block, we have a convolution layer consisting of filters with the size equals 3 × 3 and the stride equals 1, a 2× 2 max-pooling layer with the stride equals 2, and a ReLU activation function. Those two conv blocks have 32 and 64 filters respectively. We flatten out the output of second conv block yielding a 256 dimension vector. The extracted features from the second conv layers is passed through the first FC layer with batch normalization and ReLU activation to get a 8-dimensional vector, followed with the second FC layer to output a 2 dimensional vector that applied with the softmax function. The aforementioned 8-dimensional vector is the feature embedding vector X̂_f in our empirical MI estimation.        




Estimating mutual information for HAR dataset has a slightly different challenge, as the size of the alphabet for the sensitive label (i.e. identity) is 30. Thus, it requires at least 30 neurons prior to the output layer of the corresponding classification task. In fact we pose 128 neurons before the final softmax output layer in order to get a reasonably good classification accuracy. Using the 128-dimensional vector as our feature embedding to calculate mutual information is almost impossible due to the curse of dimensionality. Therefore, we apply Principal Component Analysis (PCA), shown in Figure <ref>, and pick the first 12 components to circumvent this issue. The resulting 12-dimensional vector is considered to be an approximate feature embedding that encapsulates the major information of the processed data.    


























































§ COMPUTE DIFFERENTIAL CENSORING RISK FOR THE LAPLACE AND GAUSSIAN NOISE ADDING MECHANISMS


In the local differential privacy setting, we consider the value of each pixel as the output of the query function. Since the pixel values of the GENKI dataset are normalized between 0 and 1, we can use the dimension of the image to bound the sensitivities for both Laplace mechanism and Gaussian mechanism. For the Laplace mechanism, let X and X' be two different image vectors. Since the value of X and X' in each dimension is between 0 and 1, |X_i - X'_i| <= 1 for the i^th dimension. Thus, the L_1 sensitivity can be bounded by the dimension of the image d. Notice that the variance of the Laplace noise parameterized by λ is 2λ^2. Since we are adding independent Laplace noise to each pixel, given the per image distortion D, we have 
    D/d = 2d^2/ϵ^2ϵ = d√(2d/D).

Similarly, for the Gaussian mechanism, we can bound the L_2 sensitivity by √(d). For a fixed δ, the privacy risk ϵ for adding Gaussian noise with variance σ^2 is given by 
    ϵ = 2√(d)/σ√(ln(1.25/δ)).
 Since we are adding Gaussian noise independently to each pixel, the variance of the per pixel noise in given by σ = D/d. As a result, we have 
    ϵ = 2d/√(D)√(ln(1.25/δ)).
 






§ DETAILS OF EXPERIMENTS

We train our models based on the data-driven version of the FUR formulation presented in Section <ref> using TensorFlow <cit.>.




 §.§ GENKI Dataset






























ARCHITECTURE. The FNND is modeled by a four-layer feedforward neural network. We first reshape each image to a vector (256×1), and then concatenate it with a 100×1 Gaussian random noise vector. Each entry in the noise vector is sampled independently from a standard Gaussian distribution. We feed the entire vector to a four-layer fully connected (FC) neural network. Each layer has 256 neurons with a leaky ReLU activation function. Finally, we reshape the output of the last layer to a 16×16 image.


To model the TCNND, we first generate a 100×1 Gaussian random vector and use a linear projection to map the noise vector to a 4×4×256 feature tensor. The feature tensor is then fed to an initial transposed convolution layer (DeCONV) with 128 filters (filter size 3×3, stride 2) and a ReLU activation, followed by another DeCONV layer with 1 filter (filter size 3×3, stride 2) and a tanh activation. The output of the DeCONV layer is added to the original image to generate the processed data. For both decorrelators, we add batch normalization <cit.> on each hidden layer to prevent covariance shift and help gradients to flow. We model the adversary using convolutional neural networks (CNNs). This architecture outperforms most of other models for image classification <cit.>. 

The processed images are fed to the adversary's two convolution layers (CONV), whose sizes are 3×3×32 and 3×3×64, respectively. Each convolution layer is followed by ReLU activation and batch normalization. The output of each convolution layer is fed to a 2×2 maxpool layer (POOL) to extract features for classification. The second maxpool layer is followed by two fully connected layers, each contains 1024 neurons with a batch normalization and a ReLU activation. Finally, the output of the last fully connected layer is mapped to the output layer, which contains two neurons capturing the belief of the subject being a male or a female.



 §.§ HAR Dataset




ARCHITECTURE. We first concatenate the original data with a 100×1 Gaussian random noise vector. We then feed the entire 661 × 1 vector to a Feed Forward neural network with three hidden fully connected (FC) layers. Each hidden layer has 512 neurons with a leaky ReLU activation. Finally, we use another FC layer with 561 neurons to generate the processed data. For the adversary, we use a five-layer feedforward neural network. The hidden layers have 512, 512, 256, and 128 neurons with leaky ReLU activation, respectively. The output of the last hidden layer is mapped to the output layer, which contains 30 neurons capturing the belief of the subject's identity. For both decorrelator and adversary, we add a batch normalization after the output of each hidden layer.





 §.§ UCI Adult

Each sample in the UCI Adult dataset has both continuous and categorical features. Table <ref> lists all the considered features. We perform a one hot encoding on each categorical feature in (S,X) and store the mapping function from the onehot encoding to the categorical data. For the continuous features in X, we restrict them into the interval (0,1) by normalization.


















ARCHITECTURE. We concatenate the pre-processed data with a same size standard Gaussian random vector, and feed the entire vector to the encoder. The encoder consists of two full-connected (FC) hidden layers with the number of neurons as 170 and 130, respectively. Since the output representation X_r has the same dimension as the feature variable X, the output layer of the encoder has 113 and 107 neurons for Case I and Case II, respectively. We use a leaky Rectified linear unit (ReLU) activation function in the encoder. Finally, recall that we consider two cases for this dataset: Case I with binary (gender) sensitive feature and Case II with non-binary (gender and relationship) sensitive features. Furthermore, for Case I, the inputs can be either X only or both X and S. Therefore, with only X as input to the encoder, the length of the input vector is 226 and when both X and S (binary) are inputs, the input length is 230. For both scenarios, the length of the encoder's output is 113. For Case II, since the input is X and S, the length of the input vector is 230; on the other hand, the length of the encoder's output is 107 since S is non-binary in this case. 


For Case I, the adversarial classifier consists of three full-connected (FC) layers with the number of neurons as 10, 5 and 2, respectively, and it takes X_r as the input and outputs a belief distribution for the binary sensitive variable S (i.e., gender). Here a ReLU is used as the activation function in the two hidden layers and the soft-max is used in the output layer to generate a belief distribution for gender. The same architecture is used for the downstream application of salary classification. For Case II, the adversarial classifier consists of three full-connected (FC) layers with the number of neurons as 50, 30 as well as 12, respectively. Here a Leaky ReLU is used as the activation function in the two hidden layers and the soft-max is used in the output layer.
All of the above models use log-loss as the loss function and are optimized by a Adam optimizer. 








 §.§ UTKFace Dataset

We reshape 200× 200 aligned-colorful faces in the UTKFace dataset consists into  64× 64 colorful images.






















ARCHITECTURE. The FUR model consists of an encoder and an adversarial classifier. The encoder is implemented by a noisy auto-encoder whose encoder transforms the original 64×64 RGB-images to a 4096-dimensional feature vector. Different from standard auto-encoder, which directly feeds the feature vector into the encoder part. Here, the feature vector is mixed with a 4096-dimensional standard normal random vector[A random vector is a standard normal random vector if all of its components are independent and identically following the standard normal distribution.], and then, fed into a decoder to reconstruct a 64× 64 colorful image, which is the universal representation X_r. Specifically, the encoder part of the autoencoder consists of 4 convolution layers with 128, 64, 64 and 64 output channels, respectively, and 3 2× 2-max pooling layers following the first 3 convolution layers. The encoder part is followed by 2 fully-connected layers with 4096 neurons which mixes the  noise and the output feature vector. 
The following decoder part  
consists of 5 convolution layers with 64, 64, 64, 128 and 3 output channels, respectively, and 3 2× 2-up-sampling layers following the first 3 convolution layers. The adversarial classifier takes into the representation X_r and outputs the prediction of the sensitive information gender. It consists of 2 convolution layers with 20 and 40 output channels, respectively, 2 2× 2-max pooling layers following each of the convolution layers and 2 full-connected layers with 40 and 2 neurons, respectively. 
The size of kernels in convolution layers is 3× 3. All convolution and full-connected layers use ReLU as the activation function except the last layers of the decoder and the adversarial which use sigmoid  and softmax, respectively. The encoder and adversarial classifier use the square-loss and log-loss as the loss functions, respectively, and both of them are optimized by Adam Optimizer.

The downstream non-binary classifier for ethnicity is built by changing the top (last) 3 fully-connected layers of the VGG 16 model[https://keras.io/applications/#vgg16] pre-trained on ImageNet. The first one layer has 256 neurons with ReLU as the activation function and is followed by a Dropout layer with the rate 0.5, and the second one has 4 neurons with softmax as the activation function. The classifier uses log-loss and is optimized by a Stochastic Gradient Descent Optimizer.
The neural network used in the downstream application of age regression consists of three 3× 3 convolution layers with 128, 64 and 32 output channels, three 2× 2-max pooling layers following each of the convolution layers, and three fully-connected layers with 512, 128 and 1 neurons, respectively. All layers use ReLU as the activation function except the last layer which uses a linear activation. The model uses the squared loss as the loss function and is optimized by a Adam Optimizer. 

































 

IEEEtran


