Rényi Fair Inference
Authors: Sina Baharlouei
Maher Nouiehed
Ahmad Beirami
Meisam Razaviyayn
Venue:  (2020)

Abstract: Machine learning algorithms have been increasingly deployed in critical automated decision-making systems that directly affect human lives. When these algorithms are solely trained to minimize the training/test error, they could suffer from systematic discrimination against individuals based on their sensitive attributes, such as gender or race. Recently, there has been a surge in machine learning society to develop algorithms for fair machine learning. 
In particular, several adversarial learning procedures have been proposed to impose fairness. Unfortunately, these algorithms either can only impose fairness up to linear dependence between the variables, or they lack computational convergence guarantees. In this paper, we use Rényi correlation as a measure of fairness of machine learning models and develop a general training framework to impose fairness. In particular, we propose a min-max formulation which balances the accuracy and fairness when solved to optimality. For the case of discrete sensitive attributes, we suggest an iterative algorithm with theoretical convergence guarantee for solving the proposed min-max problem. Our algorithm and analysis are then specialized to fair classification and fair clustering problems. To demonstrate the performance of the proposed Rényi fair inference framework in practice, we compare it with well-known existing methods on several benchmark datasets. Experiments indicate that the proposed method has favorable empirical performance against state-of-the-art approaches.

Published as a conference paper at ICLR 2020
RÉNYI FAIR INFERENCE
Sina Baharlouei Industrial and Systems Engineering, USC baharlouEuse. edu
Maher Nouiehed
Industrial Engineering and Management, AUB mn 120122uuub..m edu. lb
Ahmad Beirami
Meisam Razaviyayn
EECS, MIT bei rami @mit.edu
Industrial and Systems Engincering, USC razaviya@use edu
ABSTRACT
Machine learning algorithms have been increasingly deployed in critical auto- mated decision-making systems that directly affect human lives. When these algo- rithms are solely trained to minimize the training/test error, they could suffer from systematic discrimination against individuals based on their sensitive attributes, such as gender or race. Recently, there has been a surge society to develop algorithms for fair machine learning. In particular, several adversarial learning procedures have been proposed to impose fairness. Unfortu- nately, these algorithms either can only impose fairness up to linear dependence between the variables, or they lack computational convergence guarantees. this paper, use Rényi correlation models and develop general training framework to impose fairness. In particu- lar, we propose min-max formulation which balances the accuracy and faimess when solved to optimality. For the case of discrete sensitive attributes, we sug- gest an iterative algorithm with theoretical convergence guarantee for solving the proposed min-max problem. Our algorithm and analysis are then specialized to fair classification and fair clustering problems. To demonstrate the performance of the proposed Rényi fair inference framework in practice, we compare it with well- known existing methods on several benchmark datasets. Experiments indicate that the proposed method has favorable empirical performance against state-of-the-art approaches.
machine learning
measure of fairness of machine learning
INTRODUCTION
As we experience the widespread adoption of machine learning models in automated decision- making, we have witnessed increased reports of instances in which the employed model results in discrimination against certain groups of individuals see Datta et al. (2015): Sweeney (2013); Bolukbasi al. (2016); Anggin et al. (2016). In this context, discrimination is defined as the wanted distinction against individuals based on their membership to a specific group. For instance, Angwin al. (2016) present an example of computer-based risk assessment model for recidivism, which is biased against certain ethnicities. In another example, Datta et al. (2015) demonstrate gender discrimination in online advertisements for web pages associated with employment. These observations motivated researchers to pay special attention to fairesss in machine learning in recent years; see Calmon et al.] (2017); Feldman et al. (2015): Hardt al. (2016); Zhang et al. (2018); Xu et al. 2018): Dwork et al. (2018): Fish et al. (2016): Woodworth et al. (2017) 7):: Zafar et al. (0017
2015
Pérez-Suay et al. (2017): Bechavod & Ligett (2017): Liao et al. (2019).
In addition to its ethical standpoint, equal treatment of different groups is legally required by many countries Act. (1944). Anti-discrimination laws imposed by many countries evaluate fairesss by notions such as disparate treatment and disparate impact. We say decision-making process suf- fers from disparate treatment if its decisions discriminate against individuals of a certain protected group based on their sensitive/proteeeedd attribute information. On the other hand, we say it suffers from disparate impact the decisions adversely affect a protected group of individuals with cer- tain sensitive attribute see Zafar et al. (2015). In simpler words, disparate treatment is intentional

---

Published as a conference paper at ICLR 2020
discrimination against a protected group, while the disparate impact is unintentional dispropor- tionate outcome that hurts a protected group. To quantify fairness, several notions of faimess have been proposed in the recent decade [Clderrs et al. (2009); Hardt et al.] (2016). Examples of these notions include demographic parity, equalized odds, and equalized opportunity.
Demographic parity condition requires that the model output (e.g., assigned label) be independent of sensitive attributes. This definition might not be desirable when the base ground-trutt outcome of the Iwo groups are completely different. This shortcoming motivated the use of equalized odds notion Hardt et al. (2016) which requires that the model output is conditionally independent of sensitive attributes given the ground-truth label. Finally, equalized opportunity requires having equal false positive or false negative rates across protected groups.
Machine learning approaches for imposing fairness can be broadly classified into three main categories: pre-processing methods. post-processing methods, and in-processing methods. Pre- processing methods modify the training data to remove discriminatory information before passing data to the decision-making process Calders al. (2009); [eldman et al. (2015); Kamiran & Calders 22100 2009: 2012): Dwork et al.] (2012); Calmon et al. (2017); ); Ruggieri (2014). These methods map the training data to transformed space in which the dependencies between the class label and the
sensitive attributes are removed Edwards & Storkey (2015); Hardt et al. (2016); Xu et al. (2018);
Sattigeni et al. (018);; Raff & Sylvester (2018) Madras et al. (2018) Zemel al. (2013); Louizos
et al. (2015). On the other hand, post-processing methods adjust the output of a trained cl classifier
to remove discrimination while maintaining high classification accuracy Fiish et al. (2016): Dwork
eet al. (2018); Woodworth et al. (017)). The third category is the in-process approach that enforces fairness by either introducing constraints or adding a regularization term the training procedure
Zafar et al. (2017) 2015); Pérez-Suay et al.] (2017): [Bechaodd & Ligetl (2017); Berk et al. (2017); Agarwal et al. (2018); Celis et al. (2019);(oninn Donini al. (2018); Rezaei et al. (2.19)))); Kamishima al.
22011) Zhang et al. 2); Bechavod & Ligett (2017); Kearns et al. (2017) 7); Menon & Williamson
2018 Alabi et al. 2018). The Rényi fair inference framework proposed in this paper also belongs
to this in-process category.
Among in-processing methods, many add a regularization term or constraints to promote statistical independence between the classifier output and the sensitive attributes. To do that, various inde- pendence proxies such as mutual information Kamishima et al. (20IT), false positive/negative rates Bechavod & Ligett (0117), equalized odds Donini et al. (2018) Pearson correlation coefficient Zafar et al. (2015 2017). Hilbert Schmidt independence criterion (HSIC) Pérez-Suay Suay et al. (2017) were used. As will be discussed in Section 2 many of these methods cannot capture nonlinear depen- dence between random variables and/or lead to computationally expensive algorithms. Motivated by these limitations, we propose to use Rényi correlation impose several known group fairness measures. Rényi correlation captures nonlinear dependence between random variables. Moreover, Rényi correlation is normalized measure and can be computed efficiently in certain instances.
Using Rényi correlation coefficient as a regularization term, we propose a min-max optimization framework for fair statistical inference. In particular, we specialize our framework to both classi- fication and clustering tasks. We show that when the sensitive attribute(s) is discrete (c.g., gender and/or race), the learning task can be efficiently solved to optimality, using a simple gradient ascent- descent approach. We summarize our contributions next:
We introduce Rényi correlation as a tool to impose several notions of group fairness. Unlike Pearson correlation and HSIC, which only capture linear dependence, Rényi correlation captures any statistical dependence between random variables as zero Rényi correlation implies indepen- dence. Moreover, it is more computationally efficient than the mutual information regularizers approximated by neural networks.
Using Rényi correlation as a regularization term in training, we propose a min-max formulation for fair statistical inference. Unlike methods that use an adversarial neural network to impose fairness, we show that in particular instances such as binary classification, or discrete sensitive variable(s), it suffices to use simple quadratic function as the adversarial objective. This obser- vation helped us to develop simple multi-step gradient ascent descent algorithm for fair inference and guarantee its theoretical convergence to first-order stationarity.
Our Rényi correlation framework leads to a natural fair classification method and a novel fair K-means clustering algorithm. For K-means clustering problem, show that sufficiently
2

---

Published as a conference paper at ICLR 2020
large regularization coefficient yields perfect faimess under disparate impact doctrine. Unlike the two-phase methods proposed in Chierichetti et al. (2017); Backurs et al. (2019); Rösner & Schmidt (2018); Bereea et al. (2018); Schmidd et al. (2018), our method does not require any pre- processing step, is scalable, and allows for regulating the trade-off between the clustering quality and fairnsss.
RÉNYI CORRELATION
The most widely used notions for group fairness in machine learning are demographic parity, equal- ized odds, and equalized opportunities. These notions require (conditional) independence between certain model output and sensitive attribute. This independence is typically imposed by adding fair- ness constraints or regularization terms to the training objective function. For instance, [Kamishimal et al. (201T) added regularization term based on mutual information. Since estimating mutual in- formation between the model output and sensitive variables during training not computationally tractable, Kamishima al. (2011) approximates the probability density functions using a logistic regression model. To have a tighter estimation, [Song et al. (2019) used an adversarial approach that estimates the joint probability density function using parameterized neural network. Although these works start from well-juse cell-justified objective function, they end up solving approximations of the objective function due to computational barriers. Thus, fairness guarantee is provided even when the resulting optimization problems are solved to global optimality in the large sample size limit.
random variables is the Pearson correla- tion. The Pearson correlation coefficient between the two random variables and B is defined where Cov(-.) denotes the covariance and Var(-) denotes the
A tractable measure of dependence between
as pp(A, B) /Var(A) /ar(
Cov( A.B)
variance. The Pearson correlation coefficient is used in Zafar et al. (2015) to decorrelate the binary sensitive attribute and the decision boundary of the classifier. A major drawback of Pearson corre- lation is that it only captures linear dependencies between random variables. In fact, two random variables A and B may have strong dependence but have zero Pearson correlation. This property raises concerns about the use of the Pearson correlation for imposing fairness. Similar to the Pear- correlation, the HSIC measure proposed in PPérez-Suay et al. (2017) may be zero even if the two variables have strong dependencies. While universal Kernels can be used to alleviate this issue, they could arrive at the expense of computational intractability. In addition, HSIC is not a normalized dependence measure Gretton et al. (2005b which raises concerns about the appropriateness of using it as a measure dependence.
In this paper, we suggest to use Seebbfelld--eeeein---eee correlation Rényi 1959);; Hirschfeld (1955); Gebelein (1941) as a dependence measure between random variables to impose fairness. Rényí correlation, which is also known maximal correlation, between two random variables A and B defined as
Pn(A, B) = ()))))(A))(B))
s.t. [lb(B) O, =
11
f.g
(1)
where the supremum is over the set of measurable functions f(-) and g(-) satisfying the constraints. Unlike HSIC and Pearson correlation. Rényi correlation captures higher-order dependencies be- tween random variables. Rényi correlation between two random variables is zero if and only if the random variables are independent, and it is one if there is strict dependence between the variables Rényí (1559). These favorable statistical properties of PR do not come at the price of computational intractability as opposed to other measures such as mutual information. In fact, Section PR can be used in a computationally tractable framework to impose several group fairness notions.
will discuss in
3 A GENERAL MIN-MAX FRAMEWORK FOR RÉNYI FAIR INFERENCE
Consider a learning task over a given random variable Z. Our goal is to minimize the average inference loss L(.) where loss function is parameterized with parameter 0. To find the optimal
3

---

Published as a conference paper at ICLR 2020
value of parameter 0 with the smallest average loss, we solve the following optimization problem [[ 2)]
min #
where the expectation is taken over Z and possible regularization terms absorbed in the loss function (.). Notice that this formulation is quite general and can include regression, classification, clustering, or dimensionality reduction tasks special cases. As example, in the case of linear regression Z = (x, Y) and L(O, Z) = (Y - 0² X)2 where X is a random vector and Y is the random target variable.
Assume that, in addition to minimizing the average loss, we are interested in bringing faimess to our learning task. Let S be sensitive attribute (such as age or gender) and (Z) be certain output of our inference task using parameter O. Assume we are interested removing/reducing the dependence between the random variable (Z) and the sensitive attribute S. To balance the goodness-of-ff offfftt and fairness, one solve the following optimization problem
min 0
(| + P (Fo)),)
(2)
where À is positive scalar balancing fairness and goodness-of-ftt fft. Notice that the above framework is quite general. For example, Yo may be the assigned label in classification task, the assigned cluster in a clustering task, or the output a regressor a regression task.
Using the definition of Rényí correlation, we can rewrite optimization problem in equation 2 as
min sup f.g
E E[ z)] + (B[r()(())
(3)
s.t.
= -[o()) 00
= =
where the supremum is taken over the set of mcasurable functions. The next natural question to ask is whether this optimization problem can be efficiently solved in practice. This question motivates the discussions of the following subsection.
3.1 COMPUTING RÉNYI CORRELATION
The objective function in equation 3 may be non-convex in 0 in general. Several algorithms have been recently proposed for solving such non-convex min-max optimization problems (Sanjabi et al. (2018): Nouiched al. (2019): Jiin et al. (2019). Most of these methods require solving the inner maximization problem to (approximate) global optimality. More precisely, we need to be able to solve the optimization problem described in equation [ While popular heuristic approaches such as parameterizing the functions ff and with neural networks can be used to solve equation [ we focus on solving this problem in a more rigorous manner. particular, we narrow down our focus to the discrete random variable case. This case holds for many practical sensitive attributes among which are the gender and race. In what follows, we show that in this case, equation T can be solved "efficiently" to global optimality.
Theorem 3.1 (Witsenhausen (1975)). Let a E {aI...., an) and (bi,..., ba) } be two discrete random variables. Then the Rényi coefficient PR(a, b) is equal to the second largest singular value P(a=a;b=b) of the matrix Q = [4b]kss E Reedd where 9i / (((mb)))P(bbb)))
The above theorem provides a computationally tractable approach for computing the Rényi coeffi- cient. This computation could be further simplified when one of the random variables is binary.
Theorem 3.2. Suppose that a cl is a discrete random variable and b {0, 1] binary random variable. Let à be a one-hot encoding of a, i.e., ā e; if i, where e, 00.,..,,,,,0..... 0) is the i-th standard unit vector. Let b b 1/2. Then,
pR(a,b)
P(b 1)F( 0)
where y A minwer E (wTā 8)3]
Equivalently;
A min WER-
Pa = 1) Σ
Wi (P(a = i, - 1) P(a fiaa=;bbii
b,b= 0)) + 1/4.
4

---

Published as a conference paper at ICLR 2020
Proof. The proof is relegated to the appendix.
Let us specialize our framework to classification and clustering problems in the next two sections.
4 RÉNYI FAIR CLASSIFICATION
In typical (multi-class) classification problem, we are given samples from random variable Z - (X, Y) and the goal is predict Y from X. Here X Rd is the input feature vector, and y - (1....,c) c} is the class label. Let Yo be the output of our classifier taking different values in the set (I). Assume further that
PVV = = F( =i= c.
Here 0 is that parameter of the classifier that needs to be tuned. For example, F(O,X, (Fi (0, F,, X)) could represent the output of neural network after softmax layer: the soft probability label assigned by a logistic regression model; or the 0-1 probability values obtained by deterministic classifier. In order find the optimal parameter 0, we need to solve the optimiza- tion problem
min E ((F
where is the loss function and the expectation is taken over the random variable = (X, Y). Let S be the sensitive attribute. We say a model satisfies demographic parity if the assigned label Y is independent of the sensitive attribute S, see Dwork et al. (2012). Using our regularization frame- work, to find the optimal parameter θ balancing classification accuracy and fairness objective, we need solve
min E [(((F(0,)),)) + Apri(Po. 0
(5)
4.1 GENERAL DISCRETE CASE
When S E {81,,..,8dl 8a} is discrete, Theorem 3.1 implies that equation 5 can be rewritten as
(JD(0, 2 ((F(O,x). x) + Q
min vlvi. |
max
(6)
Here V1 = PPSS= s1, PP(S= E RRd is the right singular vector corresponding to
P(Yo i|s s;)IP(S = 5;)
the largest singular value of Qa laglis Rexd, with qú
V P i) PPS 5n)
Given training data (xn; Un W sampled from the random variable Z = (X, Y), we can estimate
the entries of the matrix Qo using P = =) E(P
x) N Σ F.
and P PVo i15 85) [X, ExEx, F. x), where X2 is the set of samples with sensitive
attribute 8,. Motivated by the algorithm proposed in Jin et al. (2019), we present Algorithm for solving equation 6
Algorithm Rényi Fair Classifier for Discrete Sensitive Attributes
1: Input: 0¹ E θ step-size 7).
2: for t 0, 1....,T do
3: Set v 1+1 +- max Lvi Lvr si fo(0', v) by finding the second singular vector of Qo
4: Set 0++1 +- 0' - Voln(0', v(+1)
5: end for
To understand the convergence behavior Algorithm D for the nonconvex optimization prob-
lem equation 6 we need to first define an approximate stationary solution. Let us define g(0)
5

---

Published as a conference paper at ICLR 2020
maxve vi.livi|st f(0, v). Assume further that f(. v) has L1 Li-Lipschitz gradient, then g(-) is L1- weakly convex; for more details check Rafique et al. (2018). For such weakly convex function, we say 0* is a e-stationary solution if the gradient of its Moreau envelop is smaller than epsilon, i.e.,
[[Vge())I S & with g
ming g(0") 2,3 0 0'| and {<
a given constant. The fol-
2L1
lowing theorem demonstrates the convergence of Algorithm This theorem is direct consequence of Theorem 27 in Jin al. (2019).
Theorem 4.1. Suppose that f is Lo-Lipschitz and L1 La-gradient Lipschitz. Then Algorithml | com- putes an s-stationary solution of the objective function in equation in O( iterations.
4.2 BINARY CASE
When S is binary, we can obtain a more efficient algorithm compared to Algorithm I by exploiting
Theorem 3.2 Particularly, by simple scaling of À and ignoring the constant terms, the optimization problem in equation 5 can be written as
min max w
f(0,v) & [[ w/ Fo =
E ui (P(Vo -(o= P(P i, =
Defining 3 == 1, the above problem can be rewritten as
min max
E(C(F(0,x),))
F w,
Y=1
Thus, given training data (Xn, Un )= sampled from the random variable (X,Y). we solve
N
min max fo(0, w)
A
[(F(O.
w
( x..) +
F. x.,)
N n=1
Notice that the maximization problem in equation g is concave, separable, and has a closed-form solution. We propose Algorithm for solving equation
Algorithm Rényi Fair Classifier for Binary Sensitive Attributes
1: Input: 0 E θ, step-size 7).
2: for = 0, 1,..... .,....,T T do
Set w++1 +- arg max (O',, w), i... set wit1 4: Set 0++1 0¹ VO' w(t))
EN 5.FF(00 xx)) 2 " x0t,),,)
Vi I....,c
5: end for
While the result in Theorem 4.1 can be applied to Algorithm can show a superior convergence rate.
2 under the following assumption,
Assumption 4.1. We assume that there exists a constant scalar μ 0 such that En F.(0, xn. 2 14, Vi 1,,.,,, C.
This assumption reasonable when soft-max is used. This is because we can always assume 0 lies in compact set in practice, and hence the output of the softmax layer cannot be arbitrarily small.
Theorem 4.2. Suppose that f is LA -raddidnent Lipschitz. Then Algorithm 2 computes an e-stationary solution of the objective function in equation in (( (2) iterations.
Proof. The proof is relegated to the appendix.
Notice that this convergence rate is clearly a faster rate than the one obtained in Theorem 4.1 More- over, this rate of convergence matches the oracle lower bound for general non-convex optimization;

---

Published as a conference paper at ICLR 2020
see Carmon al. 2019). This observation shows that the computational overhead of imposing fair- ness is negligible as compared to solving the original non-convex training problem without imposing faireess.
Remark 4.3 (Extension to multiple sensitive attributes). Our discrete Rényi classification frame- work can naturally be extended to the case of multiple discrete sensitivity attributes by concatenat- ing all attributes into one. For instance, when we have two sensitivity attribute S {0, 1} and S E {0, 1}. we can consider them as single attribute S E {0, 1, 2, corresponding to the four combinations of {(S) = 0, S² 0), (5' = 0, = =), (S' = 0, S² (S' =1, = 1)}-
Remark 4.4 (Extension to other notions of fairness). Our proposed framework imposes the demo- fairness. However, other notions of group fairness may be represented graphic parity notion of group
by (conditional) independence conditions. For such cases, we can again apply our framework. For example, we say a predictor Ye satisfies equalized odds condition if the predictor Ye is conditionally independent of the sensitive attribute S given the true label Y. Similar to formulation equation the equalized odds fairness notion can be achieved by the following min-max problem
min E [[((F(0.))))
+ E PR +xE
Y
(9)
DEY
5 RÉNYI FAIR CLUSTERING
In this section, apply the proposed fair Rényí framework to the widespread K-means clustering problem. Given set of data points X XN E Nxd in the K K-means problem, we seek to partition them into K clusters such that the following objective function is minimized:
N
K
K
min
Okn |x,= cx|l2
s.L.
Okn 1, Vn, Oen E (0,1), vk,
(10)
where C is the centroid of cluster k; the variable aun if data point x,, belongs cluster and it is zero otherwise; A = [n k. and C [c),...,CK, Cx] represent the association matrix and the cluster centroids respectively. Now, suppose we have an additional sensitive attribute S for each one of the given data points. In order to have fair clustering under disparate impact doctrine, need to make the random variable a, = [a....... [xn] (nn] independent of S. In other words, we need framework in equation 2 we can easily add a regularizer to this problem to impose fairness under disparate impact doctrine. In particular, for binary sensitive attribute S, using Theorem 3.2] and absorbing the constants into the hyper-parameter X, we need to solve
to make the clustering assignment independent of the sensitive attribute S. Using
K Qknl|xn 1 Σ [ w sn))²
min max
Σ
A.C WERK
(11)
S.L.
Σ akn 1, Vn,
Okn E (0,1), vk,n
where a, = (ain....,, aKa) )² encodes the clustering information of data point x,, and 8, is the sensitive attribute for data point n.
Fixing the assignment matrix A, and cluster centers C, the vector w can be updated in dloeed-frm More specifically, Wy at each iteration equals the current proportion of the privileged group in the k-th cluster. Combining this idea with the update rules of assignments and cluster centers in the standard K-means algorithm, we propose Algorithm 3, which is a fair K-means algorithm under disparate impact doctrine. To illustrate the behavior of the algorithm, toy example is presented in Appendix
The main difference between this algorithm and the popular K-means algorithm is in Step 6 of Algorithm This step is a result of optimizing equation [T over A when both C and w are fixed. When X this step would be identical to the update of cluster assignment variables in K- means. However, when À > O. Step considers fairness when computing the distance considered in updating the cluster assignments.
7

---

Published as a conference paper at ICLR 2020
Algorithm 3 Rényi Fair K-means
1: Input: X
(xi....,, ".l....,yy XN) and S {s1....,
2: Initialize: Random assignment s.l. Ex=1 ukn A and aen E {0, 1}. Set A prev 0.
while Aprev * A do
4: Set A pree = A
5: for 1...., N do
Update A
6: k- = arg min; 1|x,, cxl A(W& )n)²
7:
Set ax-n = and akn = 0 for K +
Σ n= Snakn
8:
Set wk
Wk 1, K.
> Update w
n=1 Okn
9:
end for
En= n= akn
10: Set C₁:
4k = l...,, K.
D Update
Em Okn
11: end while
Remark 5.1. Note that in Algorithm 3 the parameter is being updated after each assignment of point to cluster. More specifically, for every iteration of the algorithm, w is updated N times. If we otherwise update w after completely updating the matrix A, then with a simple counterexample can show that the algorithm can get stuck; see more details in Appendix C.1
NUMERICAL EXPERIMENTS
In this section, evaluate the performance of the proposed Rényi fair classifier and Rényi fair k- means algorithm on three standard datasets: Bank, German Credit, and Adult datasets. The detailed description of these datasets available in the supplementary material.
We evaluate the performance of our proposed Rényi classifier under both demographic parity, and equality of opportunity notions. We have implemented logistic regression classifier regular- ized by Rényi correlation on Adult dataset considering gender as the sensitive feature. To mea- sure the equality of opportunity we use the Equality of Opportunity (BO) violation, defined as EO Violation represent the predicted, and true labels respectively. Smaller EO violation corresponds to a more fair solution. Figure [ parts (a) and (b) demonstrate that by increasing X, the Rényí regularizer co- efficient decreases implying a more fair classifier at the price of higher training and testing errors. Figure part (c) compares the fair Rényi logistic regression model to several existing methods in the literature Hardt al. (2016); Zafar et al. (2015); Rezaci et al, (2019); Donini et al. (2018). As can see in plot (c), the Rényi classifier outperforms other methods in terms of accuracy for a given level of EO violation.
IP 1|S 1,Y = 1) P(Ý = 1|5 O. 1)), where Y and Y
The better performance of the Rényi fair classifier compared to the baselines could attributed to the following. Hardt et al. (2016) is a post-processing approach where the output of the classi- fication is modified to promote a fair prediction. This modification is done without changing the classification process. Clearly, this approach limits the design space and cannot explore the possibil- ities that can reach with "in-processinn" methods where both fairness and classification objectives optimized jointly. Zafar al. (2015) imposes faimess by using linear covariance and thus can only capture linear dependence between the predictor and the sensitive attribute. Consequently, there might exist nonlinear dependencies which are revealed in fairness measures such DP or EO violation. Rezaei et al. (2019): Donini et al. (2018), on the other hand, propose to use nonlinear measures dependence as regularizers. However, due to computational barriers, they approximate the regularizer and solve the approximate problem. The approximation step could potentially have an adverse effect on the performance of the resulting classifier. Notice that while these methods are different in terms of the way they impose fairness, they all implemented for logistic regression model (with the exception SVM model used Donini et al. (2018)). Thus, the difference in the performance is not due to the classification model used in the experiments.
To show the practical benefits Rényi correlation over Pearson correlation and HSIC regulariz- under the demographic parity notion, we evaluate the logistic regression classifier regularized
8

---

Published as a conference paper at ICLR 2020
by these three measures Adult, Bank, and German Credit datasets. For the first two plots, PO==1IS=1) PiY=1IS=01)
we use p% min( P(Y=1)S=0) P[Y=1|S=I]/ as measure of fairness. Since p% is defined only for binary sensitive variables, for the last two plots in Figure Z (German dataset with gender and marital status, and Adult dataset with gender and race as the sensitive features), we use the in- verse of demographic parity (DP) violation as the fairness measure. We define DP violation as DP Violation = max,,6 PPY = 1|5 = a) P( = 1|s = 6)]. As it is evident from the figure, Rényi classifier outperforms both HSIC and Pearson classifiers, especially when targeting high lev- els of fairness. For the last two experiments in Figure 2 we could not further increase fairness by increasing the regularization coefficient for Pearson and HSIC regularizers (see green and red curves cannot go beyond a certain point on the fairness axis). This can be explained by the nonlinear corre- lation between the predictor and the sensitive variables in these two scenarios which cannot be fully captured using linear or quadratic independence measures. Interestingly, our experiments indicate that minimizing Rényi correlation eventually minimizes the Normalized Mutual Information (NMI) between the variables (See Supplementary Figure (6) Recall that similar to Rényi correlation. NMI can capture any dependence between two given random variables.
Finally, to evaluate the performance of our fair k-means algorithm, we implement Algorithm S to find clusters of Adult and Bank datasets. We use the deviation of the elements of the vector w as a measure of fairness. The element Wμ of w represents the ratio of the number of data points that belong to the privileged group (S = 1) in cluster over the number data points in that cluster. This notion of fairness is closely related to minimum balance introduced by Chierichetti et al. (2017). The deviation of these elements is a measure for the deviation of these ratios across different clusters. A clustering solution is exactly fair if all entries of w the same. For K 14, plot in Figure B the minimum, maximum, average, and average + standard deviation of the entries of w vector for different values of A. For an exactly fair clustering solution, these values should be the same. As can see in Figure 3
increasing À yields exact fair clustering at the price of a higher clustering loss.
(a)
CO vOlddo
Twilinn Dror
(b)
DO Vodaatio
Text Droo
Funch
JAW
EQ Visaeiin
1443
Donini
14.08
0:34
14AM
14.0
1400
Ronaei
04.92
6:0
1440
Biry
Lambda
Lambda
Violation
Figure 1: Trade-off between the accuracy of classifier and fairness on the adult dataset under the equality of opportunity notion. (a, b) By increasing X from to 1000, EO violation (the blue curve on the left axis) approaches to O. The fairer solution comes at the price of slight increase of the training/test error (Red curve, right axis). (c) Comparison of the existing approaches with Rényi classifier, under the equality of opportunity notion. Rényi classifier demonstrates a better accuracy for a given level of fairness measured by EO violation.
7 CONCLUSION
In this paper, we proposed Rényi fair inference as an in-process method impose faimnsss in em- pirical risk minimization. Fairness is defined as (conditional) independence between a sensitive attribute and the inference output from the learning machine. As statistical independence only measurable when the data distributions are fully known, we can only hope to promote independence through empirical surrogates in this framework. Our method imposes regularizer in the form of the Rényi correlation (maximal correlation) between a sensitive attribute(s) and the inference output. Rényi correlation between two random variables zero if and only if they are independent, which is desirable property for an independence surrogate. We pose Rényi fair correlation optimization problem. In the case where the sensitive attributes are discrete (e.g., race), we present an algorithm that finds first-order optimal solution to the problem with convergence guarantees. In the special case where the sensitive attribute is binary (c.g.. gender), we show an algorithm with op- timal convergence guarantees. Our numerical experiments show that Rényi fair inference captures
minimax

---

Published as a conference paper at ICLR 2020
nonlinear correlations better than Pearson correlation HSIC. We also show that increasing the regularization hyperparameter results in near statistical independence between the sensitive attribute and the inference output. Future work would naturally consider extension to continuous sensitive attributes and problems with missing or non-explicit sensitive labels such as fair word embedding problem.
Adult Dataset
Bank Dataset
01.3
Accuracy (96)
Accuracy (%u
Regularizer Rényl
664
Regularizer
Rényí HSIC
HSIC
725
P9-rule
P%-rule
Adult Dataset with 2 Sensitive Features
German Dataset
Regularizer
Accuracy (%)
Accuracy (9)
Rényl
Pearson
Regularizer Rényl
Pearson
HSIC
1ADP Violation)
1/DP Violation)
Figure 2: Trade-off between accuracy and fairness for logistic regression classifier regularized with Rényi, HSIC, and Pearson measures, German Credit, Adult, and Bank datasets. (Top) The drop in the accuracy the model regularized by Rényi, is less than the same model regularized by HSIC, and Pearson correlation. Moreover, as can be observed for both Bank and Adult datasets, Pearson and HSIC regularizers usually cannot increase p% beyond a certain limit, due to the fact that removing all linear correlations does not guarantee independence between the predictor and the sensitive attribute. (Down) When the sensitive attribute is not binary (or we have more than one sensitive attribute), obtaining fair model for HSIC and Pearson regularizers is harder. The model regularized by HSIC or Pearson, cannot minimize the DP violation (or maximize its reciprocal) beyond a threshold.
Locu
Mausrati
Meani Side
Maan
Mean Std
Macsun
Loaa
Resa 2td
Kaan
Muani Sil
Manstur
Bank Dataset
Adult Dataset
Propartion of provlged Group (%)
82
Proporton of the Prottged Group (%)
60
1907
1007
52
32
Lambda
Lambda
Figure 3: Performance and faimess of K K-means algorithm in terms of Rényi regularizer hyper- parameter By increasing X. the standard deviation of the w vector components (each component represents the relative proportion of the privileged group in the corresponding cluster) is reduced accordingly. Both plots demonstrate that the standard deviation X, and the increase in loss is small when X < 0.005. However, to reach a completely fair clustering, a must be chosen that can increase the loss (the right axis, red curve) drastically.
w is reduced fast with respect to
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Civil Rights Act. Civil rights act of 1964, title vii,equal employment opportunities. 1964.
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A reduc- tions approach to fair classification, arXiv preprint arXiv: 1833:0::10030255,, 2018.
Daniel Alabi, Nicole Immorlica, and Adam Kalai. Unleashing linear optimizers for group-fair learn- ing and optimization. Conference On Learning Theory, pp- 2043-2066 2018
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. ProPublica, 2016.
Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scal- able fair clustering. arXiv preprint arXiv:1902.035199 2019.
Yahav Bechavod and Katrina Ligett. Penalizing unfairness in binary classification, arXiv preprint arXiv:1707.00044 2017.
Ioana O Bercea, Martin GroB, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R Schmidt, and Melanic Schmidt. On the cost of essentially fair clusterings. arXiv preprint 1rXIv:1811.10319, 2018.
Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgen- stern, Seth Neel, and Aaron Roth. A convex framework for fair regression. arXiv preprint arXiv: 2017.
Dimitri P Bertsekas. Control of uncertain systems with set-membership description of the uncer- tainty. PhD thesis, Massachusetts Institute of Technology. 1971.
Tolga Bolukbasi, Kai- Kei Chang. James Y Zou, Venkatesh Saligrama, and Adam Kalai. Man is to computer programmer as woman is to homemaker? debiasing word embeddings. In Advances in neural information processing systems, pp. 4349-4357 207,,201 2016.
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. 2009 IEEE International Conference on Data Mining Workshops, pp. 13-18.
IEEE, 2009.
Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. Optimized pre-processing for discrimination prevention. In Advances in Neural Infor- mation Processing Systems, pp. 3992-4001, 2017.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, pp. 1-50, 2019.
Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K Vishnoi. Classification with fairness constraints: A meta-algorithm with provable guarantees. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 319. ACM, 2019.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Advances in Neural Information Processing Systems, pp. 5029-5037, 2017.
John M Danskin. The theory of max-min and its application to weapons allocation problems, vol- ume 5. Springer Science & Business Media, 1967.
Amit Datta, Michael Carl Tschantz, and Anupam Datta. Automated experiments on ad privacy settings. Proceedings on privacy enhancing technologies, 2015(1):92-112, 2015.
Michele Donini, Luca Oneto, Shai Ben- Devid, John S Shawe-Taylon and Massimiliano Pontil. Em- pirical risk minimization under fairness constraints. In Advances in Neural Information Process- ing Systems, pp. 2791-2801, 2018.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations theoretical computer science confer- ence, pp. 214-226. ACM, 2012.
11

---

Published as a conference paper at ICLR 2020
Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, and Max Leiserson. Decoupled classifiers for group-fair and efficient machine learning. Conference on Fairness, Accountability and Transparency, pp. 119-133, 2018.
Harrison Edwards and Amos Storkey, Censoring representations with an adversary. arXiv preprint arXiv:/511.05897 2015.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp- 259-268. ACM, 2015.
Benjamin Fish, Jeremy Kun, and Ádám Lelkes. A confidence-basee approach for balancing fair- and accuracy. In Proceedings of the 2016 SIAM International Conference Data Mining, pp. 144-152. SIAM, 2016.
Hans Gebelein. Das statistische problem der korrelation als variations-und eigenwertproblem und sein zusammenhang mit der ausgleichsrechnung. ZAMM-Journal of Applied Mathematics and Mechanicc/Zeiischrifff für Angewandte Mathematik und Mechanik, 21(6):364-379 1941.
Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical de- pendence with hilbert-schmidt norms. In International conference on algorithmic learning theory, pp. 63-77. Springer, 2005a.
Arthur Gretton, Ralf Herbrich, Alexander Smola, Olivier Bousquet, and Bernhard Schölkopf. Kernel methods for measuring independence. Journal of Machine Learning Research, 6(Dec):2075- 2129, 2005b.
Moritz Hardt, Eric Price, Nati Srebro, et al. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pp. 3315-3323, 2016.
Hermann O Hirschfeld. A connection between correlation and contingency. In Mathematical Pro- ceedings the Cambridge Philosophical Society, volume 31, pp. 520-524. Cambridge University Press, 1935.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprint arXiv: 1902.00690 2019.
Faisal Kamiran and Toon Calders. Classifying without discriminating. In 2009 2nd International Conference on Computer, Control and Communicution, pp. 1-6. IEEE, 2009.
Faisal Kamiran and Toon Calders. Classification with no discrimination by preferential sampling. In Proc. 19th Machine Learning Conf. Belgium and The Netherlands, pp. 1-6. Citeseer, 2010.
Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrim- ination. Knowledge and Information Systems, 33(1):1-33, 2012.
Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma. Fairness-aware learning through regular- ization approach. In 2011 IEEE 11th International Conference Data Mining Workshops, pp. 643-650. IEEE, 2011.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimess gerrymander- ing: Auditing and learning for subgroup faireess. arXiv preprint arXiv:1711.05144 2017.
Jiachun Liao, Oliver Kosut, Lalitha Sankar, and Flavio du Pin Calmon. Tunable measures for infor- mation leakage and applications to privacy-utility tradcoffs. IEEE Transactions on Information Theory, 2019.
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel. The variational fair autoencoder. arXiv preprint arXiv: / 150000000000....1100 2015.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. arXiv preprint arXiv: 1802.80000000 2018.
12

---

Published as a conference paper at ICLR 2020
Aditya Krishna Menon and Robert C Williamson. The cost of fairesss in binary classification. In
Conference on Faimess,, Accountability and Transparency, pp. 107-118, 2018.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
Maher Nouiehed, Maziar Sanjabi, Jason D Lee, and Meisam Razaviyayn. Solving a class of non- convex min-max games using iterative first order methods. arXiv preprint arXiv:1902.0822 2019.
Adrián Pérez-Suay, Valero Laparra, Gonzalo Matco-Garcia, Jordi Muñoz-Mari, Luis Gómez-Chova, and Gustau Camps- Valls. Fair kernel learning. Joint European Conference on Machine Learn- ing and Knowledge Discovery Databases, pp. 339-355. Springer, 2017.
Edward Raff and Jared Sylvester. Gradient reversal against discrimination: A fair neural network learning approach. In 2018 IEEE 5th International Conference on Data Science and Advanced Analytics (DSAA), pp. 198. IEEE, 2018.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.02060 2018.
Alfréd Rényi. On measures of dependence. Acta mathematica hungarica, 10(3-4):441-5511 1959.
Ashkan Rezaei, Rizal Fathony, Omid Memarrast, and Brian Ziebart. Fair logistic regression: An adversarial perspective. arXiv preprint 190300900 2019.
Clemens Rösner and Melanie Schmidt. Privacy preserving clustering with constraints. arXiv preprint 1rX2v:1802.02497,, 2018.
Salvatore Ruggieri. Using t-closeness anonymity to control for non-discrimination. Trans. Data Privacy, 7(2):99-229, 2014.
Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason Lee. the convergence and ro- bustness of training gans with regularized optimal transport. In Advances in Neural Information Processing Systems, pp. 7091-7101, 2018.
Prasanna Sattigeri, Samuel C Hoffman, Vijil Chenthamarakshan, and Kush R Varshney. Fairness gan. arXiv preprint arXiv:1805.0980 09910, 2018.
Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. Fair coresets and streaming algo- rithms for fair k-means clustering. arXiv preprint urXiv:/812 10854, 2018.
Jiaming Song, Pratyusha Kalluri, Aditya Grover, Shengjia Zhao, and Stefano Ermon. Learning controllable fair representations. arXiv preprint 1rXiv:1812.0422 2019.
Latanya Sweeney. Discrimination in online ad delivery. arXiv preprint arXiv: IrXiv:1301.668 1301.6822, 2013.
Hans S Witsenhausen. On sequences of pairs of dependent random variables. SIAM Journal
Applied Mathematics, 28(1)100-113, 1975.
Blake Woodworth, Suriya Gunasckar, Mesrob Ohamnessian, and Nathan Srebro. Learning non- discriminatory predictors. arXiv preprint arXiv: Dwxivv/702..0e /00..0002200 2017.
Depeng Xu, Shuhan Yuan, Lu Zhang, and Xintao Wu. Fairgan: Fairness-aware generative adver- sarial networks. In 2018 IEEE International Conference on Big Data (Big Data), pp. 570-575. IEEE, 2018.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fair- ness constraints: Mechanisms for fair classification. arXiv preprint arXiv:1507.00 05259,, 2015.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fair- beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th International Conference on World Wide Web, pp- 1171-1180. International World Wide Web Conferences Steering Committee, 2017.
13

---

Published as a conference paper at ICLR 2020
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International Conference on Machine Learning, pp. 325-333, 2013.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adver- sarial learning. In Proceedings of the 2018 AAAI/ACM Conference AI, Ethics, and Society, pp. 335-340. ACM, 2018.
14

---

Published as a conference paper at ICLR 2020
A APPENDIX: PROOF OF THEOREM 3.2
Proof. First, notice that since à is one-hot encoding of a, any function f: [1....,c) R can be equivalently represented as ʃ(ā) = u á for some u E R Therefore, following the definition of Rényi correlation, write
pn(a,b)
max u.g
E [u"a) [b))
Elu T al [[g²(b) S 1, [lg(b)] 0
E [u)a)] 1
s.t.
Notice that since 6 is binary, there is a unique function g(b) where q _ P(b 1). Therefore, the above optimization problem can be written as
b-q satisfying the constraints Vv(1-9)
pa(a, b) u E [bg
s.t.
u EE aa uus
Ela -0
The last constraint simply implies that should be orthogonal to p A E[ā], which is a stochastic vector capturing the distribution of a. Equivalently, we can write RS. Thus, we can simplify the above optimization problem as
(I- pp"
for some |pi|2
Pp"
pR(a.b) b) max r
| E [g]b
pp"
pp" |
s.L.
T
I
diag (p)
I
v 11
||||
where in the constraint, we used the equality [aa"]] diag(p), which follows the definition. Let us do the change of variable simplified to
pp" )v. Then the above optimization can be pil
pn(a, max diag/// [b]]
s.t. | <
Clearly, this leads to
1
b) diag
E [b]
vp/
(12)
(P(a = b, 1)V
T-q
P(a = i, 0)
q q
P(a = i)
q
where the last equality we use the fact that 9(1) = - 1-4 and g(0) = - g Define Pao A
P(a- i, 0) and pa A P(a i, 0). ps - P(a i) pio Pa. Then, using simple
15

---

Published as a conference paper at ICLR 2020
algebraic manipulations, we have that
2
())
4
pal q
Pio
== Pi
1
(2p (1 q) 2pxog)²
(Pio - Pi1)2
+ Σ
(pio - -Pi1)²
4p:0(1 - 9)
4p:9(1 - 9)
4p;9(1 ②)
1=1
==1
(3 2q)pe1 (1 + 24) ( 24)pii + 2q)pio)
(pio pit )a
4p.9(1 9)
4p:g q)
- 24 ((3 24)9 (1 21) - -q))
(pto pi1)
49(1 q)
4p.g(1 9)
i=1
1 Ei= (pio p=1)2/110 /p:
7
4q(1 -q)
q(1 - 9)
where in the last equality used the definition of y and the optimal value of equation 3.2
B PROOF OF THEOREM 4.2
Proof. Define g0) maxw (0,0 w). Since the optimization problem maxw fa(0, w) is strongly concave in w. using Danskin's 's theorem (see Danskin (1967) and Bertsekas (1971)). we conclude that the function ( is differentiable. Moreover.
(o)n(O) = Vofn(0,w)
where w = arg max (8 w). Thus Algorithm is in fact equivalent to the gradient descent algorithm applied to (6). Thus according to (Nesterov) 2018 Chapter 1), the algorithm finds point with (0)] S in ((e-2) iterations.
C RÉNYI FAIR K-MEANS
To illustrate the behavior of Algorithm we deployed a simple two-dimensional toy example. In this example generated data by randomly selecting 5 center points and then randomly generating 500 data points around each center according to normal distribution with small enough variance. The data is shown in Figure with different colors corresponding different clusters. Moreover, we assigned for each data point 2; a binary value E {0, }} that corresponds to its sensitive attribute. This assignment was also performed randomly except for points generated around center (green points in Figure which were assigned value of 1 and points generated around center 4 (blue points in Figure which were assigned a value of O. Without imposing fairness, traditional K- means algorithm would group points generated around center 2 in one cluster regardless of the fact that they all belong to the same protected group. Similarly, points generated around center will belong to the same cluster. Hence, according to traditional K-means clustering shown in Figure 4 the proportion of the protected group in clusters 2 and 4 are and 0 respectively. However, when imposing faimess scheme, expect these points be distributed among various clusters to achieve balanced clustering. This is illustrated in Figure It evident from Figure 5 that increasing lambda, data points corresponding centers 2 and are distributed among different clusters.
16

---

Published as a conference paper at ICLR 2020
20
uster
uster
10
-5
-10
-29
-25
-10
15
20
Figure 4: Applying K-means algorithm without fairness on the synthetic dataset.
CANE CLAMM g
Darter
CLAbe
A 100
Figure 5: Applying fair K-means algorithm with different values of À on the synthetic dataset.
C.1 UPDATING W AFTER UPDATING THE ASSIGNMENT OF EACH DATA POINT IN ALGORITHM
To understand the reasoning behind updating the vector of proportions after updating each a; which the assignment of data point we discuss simple one- oie-dimensional counterexample. Consider the following four data points X, -5, X₂ 4, X3 4, and X₂ 5 with their corresponding sensitive attributes S S2 = and S3 S4 = Moreover, assume the following initial A and C
1
07
1
A
C = 1-4.,44...5 4.5).
0
1
0
1
Hence, X1 and X2 which both have sensitive attribute are assigned to cluster 1 with center C -.5 and X3 and X, which both have sensitive attribute of 0 are assigned to cluster 2 with center C 4.5. Then w which is the current proportion of the privileged group in the clusters will be 0 [1, 0J. Now, for sufficiently large À if we update A according to Step Algorithm 3 get the following new assignment
0
1
A 1
C²
[4.5, -455), w == 10.
1
0
1
0
Hence, the points just switch their clusters. Then, performing another iteration will get back to the initial setup and the algorithm will get stuck between these two states that are both not fair. To overcome this issue update the proportions after updating the assignment of each data point.
17

---

Published as a conference paper at ICLR 2020
D DATASETS DESCRIPTION
In this section we introduce the datasets used in numerical experiment discussed in Section 6 All of these datasets are publicly available at UCI repository.
German Credit Dataset | German Credit dataset consists of 20 features (13 categorical and 7 numerical) regarding to social, and economic status of 1000 customers. The assigned task to classify customers as good or bad credit risks. Without imposing fairness, the DP violation of the trained model is larger than 20%. We chose first 800 customers as the training data, and last 200 customers as the test data. The sensitive attributes are gender, and marital-statur
Bank Dataset D Bank dataset contains the information of individuals contacted by Por- tuguese bank institution. The assigned classification task is to predict whether the client will subscribe a term deposit. For the classification task consider all 17 attributes (ex- cept martial status as the sensitive attribute). Removing the sensitive attribute, and train a logistic regression model the dataset, yields to solution that is biased under the de- mographic parity notion (p% = 70.75%) To evaluate the performance of the classifier, we split data into the training (32000 data points), and test set (13211 1 data points). For the clustering task, we sampled continuous features: Age, balance, and duration. The sensitive attribute is the marital status of the individuals.
Adult Dataset F Adult dataset contains the census information of individuals including education, gender, and capital gain. The assigned classification task is to predict whether a person earns over 50K annually. The train and test sets are separated files consisting of 32000 and 16000 samples respectively. We consider gender and race as the sensitive attributes (For the experiments involving one sensitive attribute, we have chosen gender). Learning a logistic regression model on the training dataset (without imposing fairness) shows that only features out of 14 have larger weights than the gender attribute. Note that removing the sensitive attribute (gender), and retraining the model does not eliminate the bias of the classifier. the optimal logistic regression classifier this case still highly biased (v% 31.49% ). For the clustering task, we have chosen 5 continuous features (Capital-gain, age, fnlwgt, capital-loss, hours-pert peurs,, and 10000 samples to cluster. The sensitive attribute of each individual is gender.
E SUPPLEMENTARY FIGURES
0.3
0.12
Independence Function
0.18
0.12
Independence Function
0.010
Normalized Mutual Information
Rényi Correlation
Rényi
Rényi Correlation
Rényl
Pearson
NMI
0.005
0.08
0.08
0,006
0.06
0.08
0.08
0.01
0.04
6,002
0.02
0.000
200000 400500 302000
500000
1500000 1200000
200000 400020 600300
500200 1030000 1200000
Lambda Values
Lambda Values
Figure 6: The relationship between Rényi correlation, Pearson correlation, and normalized mutual information. Direct optimization of normalized mutual information is intractable due to its non- convexity. However, as we can observe on the right-hand-sides by minimizing Rényi correlation to 0, the normalized mutual information is converging to 0 accordingly.
18

---

Published as a conference paper at ICLR 2020
F FAIR NEURAL NETWORK
In this section, we train a 2-layers neural network on the adult dataset regularized by the Rényi correlation. this experiment, the sensitive attribute gender. We the number of nodes in the hidden layer, the batch-size, and the number of epochs to 12, 128, and 50, respectively. The following table depicts the performance of the trained model.
p%
Test Accuracy
Time (Seconds)
31.49%
85.33
731
80.42%
83.34
915
Table 1: Performance and training time of a neural network trained on the Adult dataset. The first and second rows correspond the networks regularized, and regularized by Rényi correlation respectively. As can be seen in the table, while adding Rényi regularizer makes the classifier more fair, it does so by bringing minimum amount of additional computational overhead.
19


Reviews:
[{"review_id": "r1gYZ0Tg5B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method to use renyi correlation to improve fairness of ML models by reducing the dependence of outputs wrt sensitive inputs such as gender. Previous models either use a linear dependence measure or use more complex optimization objectives; this paper improves upon them. They first build a min-max objective where the goodness-of-fit and fairness are jointly optimized. This non-convex objective is difficult to optimize and the authors propose a reformulation of the renyi correlation for discrete random variable case where it reduces to finding second largest eigenvalue. Based on this, they reformulate the objective which can be optimized more efficiently. They show the performance of their model for supervised and unsupervised learning problems on 4 different dataset by comparing to standard correlations such as Pearson.\n\nOverall the paper is clearly written and I liked the idea of using renyi correlation which also has a nice theoretical formulation allowing to be optimized more efficiently. But, the experimental results are a bit weak since the only model they experiment with is logistic regression. Given that their main motivation is to capture non-linear dependencies, I think some results with neural networks is necessary. Since their main focus is on discrete case, the authors can show if training a word embedding model with renyi regularization helps improve fairness of word embeddings.\n\nI have several question regarding the paper:\n\nThe datasets that authors use have a predefined feature space. Can you show if the sensitive feature is really important for high accuracy? Can we get the same performance without the sensitive features?\nSince the model is trained with gradient descent, how would a more simple baseline where the gradient of the sensitive feature is penalized work?\nHow would this algorithm generalize to larger problems such as language models since Q_{theta} is regenerated at every iteration? ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyxTwiqAKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a novel approach to fair inference/learning by using the Renyi correlation in place of the standard correlation measures (e.g. Pearson correlation) as a measure of \"unfairness\" expressed as a form of dependence between an outcome and a sensitive variable (which includes a number of standard group fairness definitions including demographic parity and equality of odds). This is motivated by the limitation of standard notions of correlation that they only capture linear correlations. \nThe proposed approach is a formulation using the Renyi correlation as a regularization term, which leads to a min-max formulation due to the definition of Renyi correlation as the maximum correlation between any functionals of the variables in question.\nThe paper then describes in detail how the computation can be done by making use of the fact that Renyi correlation can be computed using singular values of the relevant matrix, and provides computation time analyses for a couple of different assumptions. \nThe authors also apply the analogous idea to (k means) clustering to derive what they call the Renyi fair clustering. \nIn the experimental evaluation section, they evaluate the performance of the proposed methods with respect to the accuracy fairness trade-off, using 3 publicly available real world data sets and with the 2 standard definition of group fairness. The experimental results show quite convincingly that the trade of is improved by Renyi correlation as compared to the use of standard correlations.  They also evaluate the Renyi fair clustering method using a fairness metric they propose for evaluating the uniformity of clustering results.\nOverall the paper presents a crisp new idea, develops sound theoretical analysis and algorithms, and validate their superiority with satisfactory experiments. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlAucY_qB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work shows an interesting approach to introduce fairness to machine learning. The introduction and presenation of the approach are well written. The introduction provides a valuable overview and characterization of existing work and motivates the approach proposed in this work. Sections 2 through 5, together with the supplementary material provide a comprehensible description and derivation of the approaches to classification and clustering, together with the corresponding algorithms.\nHowever, experimental section leaves open a number of questions. First of all, for readers not familiar with the task used here, a more detailed description would be desirable, including moving Supplementary Section D into the main text. In Suppl. Sec. D also a succinct definition of the classification task should be provided. What exactly are the classiffication tasks you solve for the Bank and Adult dataset, i.e. what is the set (and number) of classes in both cases?\nFigs. 1 (a) and (b): you should provide a legend defining the red and blue curves.\nFig 1 (c): without knowing the other approaches cited here, some comment on the differences in the classifier models used would be helpful to evaluate the differences in test error. Effectively, the reader would like to get an indication, what the differences in test error are induced by: difference in the regulatory fairness terms, or also differences in the classifier models.\nOverall, the three datasets used to test the approach seem to be fairly limited, as are the corresponding classifier models used. It would be interesting to get an indication of how the approach would perform on/scale to much larger tasks with (much) deeper classification models?\nCompletely missing is a final overall conclusion section.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses the problem of fair representation learning. The authors propose to use Rényi correlation as a measure of (in)dependence between the predictor and the sensitive attribute and developed a general training framework to impose fairness with theoretical properties. The empirical evaluations have been performed using standard benchmarks for fairness methods and the SOTA baselines -- all this supports the main claims of this work's contributions. 
All the reviewers and AC agree that this work has made a valuable contribution and recommend acceptance. Congratulations to the authors! 

Decision: Accept (Poster)