FERMI: Fair Empirical Risk Minimization via Exponential Rényi Mutual Information
Authors: Rakesh Pavan
Andrew Lowy
Sina Baharlouei
Meisam Razaviyayn
Ahmad Beirami
Venue:  (2021)
Keywords: algorithmic fairness

Abstract: Several notions of fairness, such as demographic parity and equal opportunity, are defined based on statistical independence between a predicted target and a sensitive attribute. In machine learning applications, however, the data distribution is unknown to the learner and statistical independence is not verifiable. Hence, the learner could only resort to empirical evaluation of the degree of fairness violation. Many fairness violation notions are defined as a divergence/distance  between the joint distribution of the target and  sensitive attributes and the Kronecker product of their marginals, such as \Renyi correlation,  mutual information, $L_\infty$ distance, to name a few.
 In this paper, we propose  another notion of fairness violation, called Exponential R\'enyi Mutual Information (ERMI) between sensitive attributes and the predicted target. We show that ERMI is a strong fairness violation notion in the sense that it provides an upper bound guarantee on all of the aforementioned notions of fairness violation. We also propose the Fair Empirical Risk Minimization via ERMI regularization framework, called FERMI. Whereas existing in-processing fairness algorithms are deterministic, we provide a stochastic optimization method for solving FERMI that is amenable to large-scale problems. In addition, we provide a batch (deterministic) method to solve FERMI. Both of our proposed algorithms come with theoretical convergence guarantees. Our experiments show that FERMI achieves the most favorable tradeoffs between fairness violation and accuracy on test data across different problem setups, even when fairness violation is measured in notions other than ERMI. 

Under review as a conference paper at ICLR 2021
FERMI: FAIR EMPIRICAL RISK MINIMIZATION VIA EXPONENTIAL RÉNYI MUTUAL INFORMATION
Anonymous authors Paper under double-blind review
ABSTRACT
Several notions of fairness, such as demographic parity and equal opportunity, are defined based statistical independence between a predicted target and sen- sitive attribute. machine learning applications, however, the data distribution is unknown the learner and statistical independence is not verifiable. Hence, the learner could only resort to empirical evaluation of the degree of fairness vi- olation. Many faimess violation notions are defined as divergennc/distance be- tween the joint distribution of the target and sensitive attributes and the Kronecker product of their marginals, such as Rényi correlation, mutual information, Too distance, to name few. In this paper, we propose another notion of fairness vi- olation, called Exponential Rényi Mutual Information (ERMI) between sensitive attributes and the predicted target. We show that ERMI is a strong fairness vio- lation notion in the sense that provides an upper bound guarantee on all of the aforementioned notions of fairesss violation. We also propose the Fair Empirical Risk Minimization via ERMI regularization framework, called FERMI. Whereas existing in- in-processing fairness algorithms are deterministic, we provide a stochas- tic optimization method for solving FERMI that is amenable to large-scale prob- lems. In addition, we provide batch (deterministic) method to solve FERMI. Both of our proposed algorithms come with theoretical convergence guarantees. Our experiments show that FERMI achieves the most favorable tradeoffs between fairness violation and accuracy on test data across different problem setups, even when fairness violation is measured in notions other than ERMI.
INTRODUCTION
Ensuring that decisions made using machine learning algorithms are fair to different subgroups is of utmost importance. Without any mitigation strategy, machine learning algorithms may result in discrimination against certain subgroups based on sensitive attributes, such as gender or race, even such discrimination is absent in the training data (Datta et al. SWeeneyy 2013 Bolukbasi et al. 2016 Angwin et al., 20166] du Pin Calmon et al. [0116]] Feldman et al., 2015) Hardt et al. 2016 Fish et al. [016 Woodworth al. 2017 et al. [201 Bechavod & Ligett 2 Kearns al. 2018). To remedy such discrimination issues, several notions for imposing algorithmic fairness have been proposed in the literature.
A learning machine satisfies the demographic parity notion, if the predicted target is independent of the sensitive attributes (Dwork et al.] 2012). Promoting demographic parity can lead to poor performance, especially if the true outcome is not independent of the sensitive attributes. To remedy this, (Hardt et al. 2016) proposed equalized odds to ensure that the predicted target conditionally independent of the sensitive attributes given the true label. A further relaxed version of this notion equal opportunity which is satisfied predicted target is conditionally independent of sensitive attributes given that the true label is in advantaged class (Hardt et al., (0016). Note that the inherent assumption such conditional notions that the true labels are unbiased. These notions suffer from a potential amplification of the inherent biases that may exist in the targets/labels in the training data (e.g., data collection bias). Tackling such bias is beyond the scope of this work.
In practice, the learner cannot empirically verify independence of random variables, and hence can- not verify demographic parity, equalized odds, or equal opportunity. This has led the machine learning community to define several notions of fairness violation that quantify the degree of inde- pendence between random variables, e.g., demographic parity/equalized odds, Lxe distance (Dwork)
et al. 2012 Hardt al. 2016), mutual information (Kamishima al. 2011 Rezaei et al. 2020

---

Under review as a conference paper at ICLR 2021
Steinberg et al. 2020 Zhang et al., 2018 Cho et al. 2020), Pearson correlation ZZaaar et al. 2017
false positive/negative rates (Bechavod & Ligett 2017). Hilbert Schmidt independence criterion (HSIC) (Pérez-Suay al.] 2017), and Rényi correlation (Baharlouci al. 2020 Grari et al. 2020 2019). to name a few. In this paper, we define yet another notion of fairness violation, cal called ex- ponential Rényi mutual information (ERMI). We show that ERMI is easy compute empirically and prove that ERMI provides an upper bound on the existing notions of fairness violation such as demographic parity, equalized odds, and equal opportunity.
Given a notion of fairness violation, it is still not straightforward to train an algorithm that satisfies a fairness violation constraint (Cotter et al., 2019). The barness-promoting machine learning algo- rithms can be categorized in three main classes: pre- pre-processing. processio,s,,ngg. and in-processing methods. Pre-processing algorithms (Feldman et al. 2015 Zemel et al. 2013 du Pin Calmon et al., 2017h) transform the biased data features to new space in which the labels and sensitive attributes are statistically independent. This transform oblivious to the training procedure. Post-processing approaches (Hardt et al. 2016 Pleiss et al. 2017) mitigate the discrimination of the classifier by altering the the final decision, e.g., by changing the thresholds on soft labels, or reassigning the labels to impose notions of fairness. In-processing approaches focus on the training procedure and impose the notions of fairness as constraints or regularization terms in the optimization procedure. Several regularization-basel methods are proposed in the literature impose measures of fairness to decision-trees (Kamiran et al., 2010 Raff et al. 2018
Aghaei et al. 2019), support vector machines (Donini et al. 2018), neural networks (Grari et al. 2020), or (logistic) regression models (Zafar
et al. 2017| Berk et al. 2017: Taskesen et al. 20200 Chzhen & Schreuder 2020 Baharlouei et al., 2020 Jiang et al. 2020 Grani et al. 2019). To the best of our knowledge, existing in-processing methods are all deterministic, making them impractical for large-scale problems. Furthermore, most in-processing methods (with the exception of (Baharlouei et al.. (0200) are designed for problems in which the sensitive attribute and/or the target is binary. In this paper, we introduce a new fair empirical risk minimization framework via ERMI regularization, and call FERMI. We provide novel batch and stochastic gradient-baset methods with guarantees for solving FERMI and demon- strate their effectiveness on multiple numerical experiments, which include a large-scale problem and problem with both non-binary sensitive attributes and targets. We show that FERMI can be used to achieve the most favorable tradeoffs between performance and fairness, even fairness violation is measured in notions other than ERMI.
(Z, -FAIRIES:: A GENERAL NOTION OF FAIRNESS
We consider a learner who trains a model to predict target, Y, c.g., whether or not to extend a loan, supported on y which can be discrete or continuous. The prediction is made using a set of features, X, e.g., financial history features, length of credit, and amount of debt. We also assume that there is a set of discrete sensitive attributes, S, e.g., race and sex, supported on S, associated with each sample. Further, let A C y denote an advantaged outcome class, e.g., the outcome where loan is extended. Next, we will present the main fairness notion considered in this paper, which generalizes several existing ones.
Definition 1 ((Z, f--mmiesss), Given a random variable Z, let 2 be subset of values that Z can take. We say that learning machine satisfies (Z, fairmesss for every E Z, Y is conditionally independent of S given 7. = 2. More precisely.
py 2|2 (ū. s/22 - P812 ( (())(((()))) Vî V EZ
Notice that 2 -fiirnsssss recovers several important existing notions of faimess as special cases:
1. (Z, -firiinssss recovers demographic parity (Dwork al. 2012) if Z and Z {0). In this case, conditioning on Z has no effect, and hence (0, (OF) faimess is equivalent to the independence between Y and S, i.c., demographic parity (see 7 Appendix A)) 2. (Z, -firiness recovers equalized odds (Hardt al., 2016) if Z Y and Z y In the case, Z E Z is trivially satisfied and could be dropped. Hence, conditioning on Z is equivalent conditioning on Y. which recovers the equalized odds notion of fairness, i.c., conditional independence of Y and S given Y (see Definition 8) Appendix [A).
3. (Z, -faiinessss recovers equal opportunity (Hardt et al. 2016) if Z = Y and Z = A. This is also similar to the previous case with ) replaced with A (see Definition Appendix A).
2

---

Under review as a conference paper at ICLR 2021
Demographic parity amounts requiring equality of outcomes across sensitive groups. However, it can result in poor performance of a learned model, particularly if the true outcome Y is not inde- pendent of S. Equalized odds and equal opportunity remedy this issue by relaxing the independece constraint (Hardt et al., 2016). In the binary classification setting with binary sensitive attributes (e.g.. male female), equalized odds ensures equality of false negatives and false positives of classifier across sensitive groups. Equal opportunity is further relaxation of the equalized odds cri- terion, which, in the binary setting, requires just equality of false negatives across sensitive groups. For example, this could be used to enforce that face recognition software does not falsely classify people of one race as criminals more often than people of other races.
Note that verifying (Z, 2 -ffirressss requires having access to the joint distribution of random vari- ables (Z,Y, SS. This joint distribution is unavailable to the learner in the context of machine learn- ing, and hence the learner would resort to empirical estimation the amount of violation inde- pendence. In the next section, we propose exponential Rényi mutual information violation of (Z, 2) )fairness, and show that it is a stronger notion compared to several existing fair- ness violation notions, including demographic parity L distance (Kearns al. 2018). equalized odds Loo distance (Hardt et al. 2016). and equal opportunity Loo distance (Hardt et al. 2016).
notion of the
EXPONENTIAL RÉNYI MUTUAL INFORMATION
In this section, we define ERMI and show that several existing fairness violation notions (which are mostly instances of f-divergences distance metries between the joint probability distribution and the Kronecker product of the marginals) are also upper bounded by ERMI, implying that ERMI stronger notion of fairness violation. In particular, this means that if ERMI is small, then automatically obtain guarantees that all other notions of fairness violation must be small as well. We present all definitions and results for general (Z, Z) fairness notion, which requires careful extension of several existing notions to the conditional case. These defimitions and results will simplify significantly when Z 0 and
{0}, which will eliminate all conditional expectations.
Definition 2 (ERMI- exponential Rényi mutual information). We define the exponential Rényi mutual information between Y and S given Z E Z
PP Pr,siz (Y,
[x(PP5IZEE)
Z -
In Appendix B we unravel the definition for the special cases of interest corresponding to the exist- ing notions of fairness. We also discuss that ERMI is the x2 -dvieeegee (which an f f-divergence) between the joint distribution, PY,siz and the Kronecker product of marginals, Pýiz ? Psiz- In particular, ERMI is non-negative, and zero and only (Z, Z) fairness is satisfied. Hence, ERMI is a valid notion of fairness violation.
Definition 3 (Rényi mutual information (Rényi 1961).. Let the Rényi mutual information of order between random variables Y and given 7 E be defined as: a-1
PV (
2E2))
La LY; E 2)
log
E 2,
Z
(3)
a a-1
P912 (Ý (Y)))
which generalizes Shannon mutual information
pp P9.s12 (f, SIZ) P9iz ( (2))))((
T(Y E 2) =)==Ezy8s log
7E3
and recovers it as lim La (Y; SIZ E 2)= = ( Z).
Note that I, (Y;Y; (Y:S1 S Z E 2) 2 0 with equality if and only if (Z, 2) -fiiriesss is satisfied. Theorem (ERMI is stronger than Shannon mutual information). We have
0 < ( SIZ e Z) < ( 2) (1
D Z).
(5)
All proofs relegated the appendix. Theorem I establishes that ERMI is stronger notion of fairness in the sense that driving it to zero would also bound the Shannon mutual information. also shows that ERMI is exponentially related to the Rényi mutual information of order 2.
3

---

Under review as a conference paper at ICLR 2021
Definition 4 (Rényi correlation (Hirschfeld 1935 Gebelein 1941 Rényi 1959)). Let F and g be the set of measurable functions such that for random variables Y and S, B (J(; Es (g(S;z)) =)} = O, Bo( = Es {9({==)²} for all E 2. Rényi correlation is:
Pn(Y,S Z) :- sup E z is { ((Y::))(S::0) (E ZEZ].
(6)
/eF,gEg
Rényi correlation generalizes Pearson correlation coefficient
yy ( S|
2) = Ezz ,i 2
ZEZ
Ep (
to capture nonlinear dependencies between the random variables by finding functions of random variables that maximize the Pearson correlation coefficient between the random variables. In fact, it is true that PR S 2) 0 with equality if and only if (Z, 2) - is satisfied. Due to these favorable properties. Rényi correlation has gained popularity as a measure of faimess viola- tion (Baharlouei al. 2020 Grari et al., 2020).
Theorem (ERMI is stronger than Rényi correlation.). We have
5 1Y S 2)1 S pn(Y, S|Z 2) DR(Y:SIZ E 2),
(8)
and if|s = 2, (Y: E 2) Pn 2).
Next, we turn to another popular notion of faimess violation and establish similar relationships.
Definition 5 (Ly fairness violation). We define the Ly fairness violation for 2 1 by:
L, e 2) : Ez :=E> ( E.cso Pp Pl, (7. Z) p912 (7 220g2)))0 ()ssz 2) dyy ) 2 E 2
and only if (Z, 2)-fairness is satisfied. In particular, Loo fairness violation recovers the demographic parity violation (Kearns et al., 2018 Definition 2.1) if we let 2 {0} and Z 0. It also recovers equal opportunity violation (Hardt et al. 2016) if we let Z = A and = Y. Lg faimness violation generalizes this notion by considering the Lg norm of the difference between the joint distribution py,s and the Kronecker product of the marginal distributions pp & ps-
Note that (Y, S, 2) =0
Theorem 3 (ERMI is stronger than Loo faimess violation). Let Y be discrete or continuous random variable, and a discrete random variable supported on a finite set. Then for any q 122
00 (P, S
Dn(PP SS,E2,
(10)
The above theorem says that if method controls ERMI value for imposing fairness, T.x demo- graphic parity violation (Kearns et al.] 2018), Le equal opportunity violation (Hardt et al. 2016),
or Loo equalized odds violation (Hardt al. 2016 is also guaranteed be bounded.
4 FAIR RISK MINIMIZATION VIA ERMI
Our goal to train a model that balances fairness and accuracy objectives. To this end, we introduce fair risk minimization through exponential Rényi mutual information framework defined below
Definition 6 (FRMI fair risk minimization through exponential Rényi mutual information). To balance fairness and accuracy, we consider the learning objective function:
min 0
Ex.s (((X.Y:0)) + +DD (Yo):))
(11)
I Note that similar relationship with TV could he established as well.
'n this section, we present all results in the context of Z - 0 and Z = {0}, leaving off all conditional expectations for clarity of presentation. The results could be generalized for general (7, 2), we have used the resulting algorithms for empirical experiments.
4

---

Under review as a conference paper at ICLR 2021
where E denotes the loss function, such Lo loss or cross entropy loss; X 0 is scalar balancing the accuracy versus fairness objectives; D DieYo (Y)(((X);;)) is the notion of ERMI given in Eq. 17); and Ygl (X) is the output of the learned model (e.g., the oulput of classification or a regression task, or the cluster number in a clustering task).
While (X) inherently depends on X and O, in the rest this paper, we sometimes leave the dependence of on X and/or 0 implicit for brevity of notation. Notice that we have also left the dependence of the loss on the predicted outcome Y implicit. FRMI is the objective we should solve demographic parity is the desired fairness notion; instead we are interested in equalized odds or equal opportunity. then Dx .) should be replaced by DR Siz E Z) for an appropriate (Z, 2) pair, per the discussion in Section Since the theory is very similar in both cases, stick with FRMI as defined in Definition 6 practice, the true joint distribution of (X, S, Y, Y) is un- known and we only have N samples our disposal, making it impossible to solve FRMI. Hence, we turn into fair empirical risk minimization via exponential Rényí mutual information (FERMI) approach. While it is natural to estimate Ex,y.9 {{(X, () } through the empirical risk, the esti- mation of DR(Y, S) in the objective function in Eq. (11 is not as straightforward. In what follows, we propose two approaches for estimating Dy S). These two approaches result in two different algorithms for balancing fairness and accuracy, where we discuss the benefits and shortcomings of each.
4.1 FERMI VIA EMPIRICAL ESTIMATION OF THE PROBABILITY DISTRIBUTIONS
Let {xs, 8t, Vi, Di VEtN denote the features, sensitive attributes, targets, and the predictions of the model parameterized by 0 for samples E [N]. A natural approach to estimate the objective function in Eq. 11 and learning the parameter 0 is through solving the problem
min 0
Σ M
(x..Vi00 + >DR((o:
(12)
Here DR(YO:S) == EvES STEv (1) dō - 1 is an empirical estimate of DR(Ye. S) where (s(#), , Po (1), and Fy VT.
By (.,a)
(T),)) 8) are the empirical estimation of the corresponding probability func- tions. To make the objective function differentiable with respect to 0, we make the following as- sumption:
Assumption 1. Assume the sensitive attribute is deterministic function of the features, i.e., S (X). This trivially holds the sensitive attribute is available as part of the features. Further, assume the following soft conditional densiry:
PV. s) 11f(())
=
(13)
SYEY e -(()
where r >> O controls the softness of the decision and r + oo would recover the hard decision made by choosing that minimizes the loss function.
Assumption 1 is generalization of the assumption in RFI (Baharlouei et al. 2020 and is natural in problem instances where the decisions made by the learning algorithm are soft decisions. In particular, logistic regression neural networks with soft-max layer and cross entropy loss satisfy Assumption We can further find psls Py: and ps from Eq. (33
Under this assumption, we will have the following empirical estimate of the joint distribution of the predicted target and the sensitive attribute:
c-(((x.5:1))
P% (oo 8)
Σ 1fs: 1[8==) =) SWEY e e
(14)
N
SE[N]
which could be marginalized to define (s) and pp (.) as well. These empirical probabilities make Drx(Yo S) differentiable function of 0. Notice that these empirical quantities converge to the
5

---

Under review as a conference paper at ICLR 2021
true distributions for finite S and V however, the sample complexity required for their estimation scales linearly with |S] and [Y/, which implies an exponential scaling with the number of sensitive attributes. Our stochastic algorithm that will be presented in the next section will aim to remedy this potential problem.
To solve Eq. [2). can apply the gradient descent algorithm and use the dynamics
0 ---=00 - -V'
Σ NE[N]
e(xs 0') + + DDR
(15)
N
where > is the learning rate/step-size. Note that when the sensitive attribute is binary, our algorithm is the same as the one in (Baharlouei et al. 2020) since then (Yo: pR(Y, S), the Rényi correlation, by Theorem [ However, the non-binary case, our algorithm is different from (Baharlouei et al., 2020) in general, and we show in Sec. | that it achieves a more favorable accurayy tradeoff curve. Under standard assumptions on the loss function and the learning rate, one can show that the dynamics in Eq. 155 find an 6 stationary point, (i.e., point with the norm of gradient being smaller than e) in O iterations (Nesterov 2013).
Theorem 4. (Informal statement) Gradient descent (i.e. Eq. (15) converges to the set of e-first order stationary points of the FERMI objective (Eq. (2) ( iterations (gradient evaluations),
While this algorithm achieves the optimal rate first-order methods general smooth non-convex optimization problems, the empirical ERMI term in the objective in Eq. of ERMI in Eq. (TT.. This bias makes the optimization problem in Eq. (12) not suitable for using stochastic methods. For example, in the extreme case, where only one sample is available to the
(12) is biased estimator
learner for updating the objective each turn, DR(G-) can be severely biased due the nonlin- earities in how it is defined. In the next subsection, we propose another approach for estimation of DR(:-) -) that results in an unbiased estimator, which is amenable stochastic optimization.
Algorithm Two- Time Scale SGDA for FERMI
1: Input: 8º E Rdo, 8 E W c R step-sizes (17 me.,, mini-batch size M, fairness param- eter 0, iteration number T. do
2: for = 0......, T
3: Draw batch B of data points Ui)iEB
4: Set 0++1 0 no D
EiEB Vol(xi, yr. 0) 2XV, (e)) vec(W"W)) +
2 Ve (0)s vec(WT P. 1=1)
5: Set W++1 + 1lw (w* + nww Eier 2A)3)(0)) + +2PP. 1/P.-1/3s.5.. v2s:).(0)))
6: end for
7: Pick f uniformly at random from (1....,TT}
8: Return: 0²
4.2 STOCHASTIC FERMI
In order to solve the population level objective in Eq. [T]) using stochastic methods (such as stochas- tic gradient descent), one needs to obtain an unbiased estimate of the objective in equation [I] i.e., Ex,y. {e(x, 0) AD Yo (X); S). Clearly, the empirical average [03 Eien n (xx, ye; 0) is an unbiased estimator of Ex,y.s (c(
), where B S [N] is batch of data points. Thus, to develop a stochastic algorithm. we need to have an unbiased estimator of D (X)): given a batch of data points B. The following Theorem will help us obtain such estimator.
Theorem 5. For discrete random variables Y and S where Y [mr] S E [k], we have
DR(
max W
TH(WP 2TF(W Py..
(16)

---

Under review as a conference paper at ICLR 2021
a) Adult Dataset
Equalit of Opportunity Volation
0.155
Equilbeed Chdds CiddiWiiiiiiio Vollttan
0.10
0.550
2:20
1000
0.000
2,00
0003
0.02
038
Test Errrr
Tost Enror
Tost Error
b) German Credit Dataset
Equalry Orparuuity Viobato
Eqalaedd Coloo Codt ColtsVoooatioo
3.12
0.05
0.755
0.54
0.03
3.22
0.20
0.22
0.24
3.55
8:30
0.20 0.22
3.34
0.35
6.8
0.50
0.24
9.20
Test Error
Test Emoo
Tost Error
Figure Tradeoff of faimesss violation vs test error for different baselines on German Credit Adult datasets. The desired operation point is the lower left corner where both fairness violation and test error are small. FERMI achieves the hest fairnss vs performance tradeoff across all baselines.
pp (P(1) (1)
0
where Pg-
(m(m) pv (1,,))
Pp (1,1)
(s(1)
0
P3. =
P. =
PV. (m, 1)
pP (m,s(m,)))
ps
Let Y (0, 1)" and S {0, 1h be the one hot encoded version of y and S, respectively. Then, the above theorem implies that Eq. (ITb can be re-written as
min max E ( 0: T(WYY +2TH P. 1/2) - 1
O WER
Hence, given ased estimator of the above objective function by the empirical average
batch of data points B. we can obtain
unbi-
[B ELEB ((x, ve: 0) ItWW.s?W")) 2" 1/13))
This observation leads to the stochastic algorithm presented in Algorithm [ Notice that this algorithm is based on
the assumption that P. is known. This assumption practical since the distribution of sensitive attributes (such as male vs female) is known in many applications (or it can be estimated accurately using the training data). The convergence rate of Algorithm analyzed in Theorem 6
Theorem 6. (Informal statement) Algorithm 7 converges to the set of c-first order stationary points of the FERMI objective (c.f. Eq. 12 in 0 + iterations (stochastic gradient evaluations).
The formal statement of this theorem can be found in Theorem I in Appendix D Notice that while this algorithm has a slower rate of convergence than the batch algorithm, it is stochastic (each iteration is computationally cheap) and amenable to large-scale problems. Note also that faster convergence rate of 0 could be obtained by using the (more complicated) SREDA method of (Luo et al. 2020) instead of SGDA to solve FERMI objective. We omit the details here. In the next section, we numerically evaluate the performance the algorithms described in this section.
NUMERICAL EXPERIMENTS
5.1 BINARY FAIR CLASSIFICATION WITH A BINARY SENSITIVE ATTRIBUTE
We start the experimental setup for binary classification problem with a binary sensitive attribute. This is common setup among most existing baseline methods. Per Theorem 2 in this binary
7

---

Under review as a conference paper at ICLR 2021
Tradeat Clime
Tradeeff on Conera Crima hamary larget
207
300
TOM
630
202
022
0.24
X000
Figure 2: Comparison between FERMI and RFI (Baharlouci et al. 2020 FERMI achieves better faimess vs performance tradeoff. Moreover, due to computationally expensive operations like performing singular value decomposition (SVD), RFI has poor scalability with the cardinality of sensitive features and target classes.
classification case ERMI is equivalent to Rényi correlation (Baharlouei al. 2020 and per the discussion in Sec. 4.1 our batch algorithm is exactly the same as RFI (Baharlous et al.) 2020).
While we solve FERMI to impose an ERMI regularizer, we still measure fairness violation via pop- ular fairness violation notions, such as conditional demographic parity Lee violation (Definition I0), conditional equal opportunity T. violation (Definition [T). and conditional equalized odds viola- tion. In Fig. we report the fairness violation vs error for German Credit and Adult datasets. As can seen, for all three popular notions of fairness, FERMI achieves the best trade-off between fairness and error probability on the test data. This could be partly due smoothness of FERMI optimization problem, and partly due to the fact that ERMI upper bounds other fairness notions as discussed in Sec. 3 We will have more detailed discussion this in Section
5.2 NON-BINARY FAIR CLASSIFICATION WITH A NON-BINARY SENSITIVE ATTRIBUTE
Next, we consider general classification problem with |S] 2. In this case, consider the Communities and Crime dataset, which has 18 binary sensitive attributes in total, and we pick {7. 10, 14, 18] sensitive attributes out of those for different experiments, which corresponds to |S E {2?, 1 200 214 218]. We discretize the target into three classes (high, medium, low} (ternary classification). The only baseline that we are aware of that can handle non-binary classification with non-binary is sensitive attributes is RFI (Baharlouei et al. 2020). The results are presented in Fig 2 where we use conditional demographic parity Lo violation (Definition [0] and conditional equal opportunity Loo violation (Definition 11) the fairness violation notion. As can be seen, FERMI achieves a better tradeoff curve as compared with RFI. It is noteworthy that the per-iteration com- plexity of FERMI is far less than that of RFI, which requires solving singular value decomposition at each iteration. Finally, the convergence rate for FERMI given in Theorem 4 guarantees an O (
convergence vs ((2)) for RFI (Baharlouei et al. 2020 Theorem 4.1). Empirically, we observed that FERMI converges ~ 10x faster on this problem instance. Finally, we also show that conditional de- mographic parity L violation (Definition 10) and square root of ERMI are approximately linearly related, which further justifies the use of ERMI regularizer in the FERMI framework.
5.3 LARGE-SCALE CLASSIFICATION WITH FERMI
Gokend trais bamples
In this experiment, we consider the color MNIST dataset Li & Vasconcelos] 2019) where MNIST digits are colored with dif- Terent colors drawn from Gaussian distribution with variance around certain average color. It is shown in (Li & Vas- ccnnelos 2019) that as + convolutional network model overfits significantly to the color on this dataset, and hence will not be able generalize on regular black and white test set. Our goal in this experiment is to show that FERMI can promote independence between the predicted target and color
J
3
2
7 Figure 3: Color MNIST.
(which use the sensitive attribute within FERMI) improve generalization in this setup. This also allows us to examine the scaling of stochastic FERMI when used in convolutional neural networks. We consider
O, where the test performance is the lowest due overfitting.
The result of the experiment is presented in Fig. 4 As expected, FERMI results in learning rep- resentations that have less dependence on the color, hence leading to better generalization. It is
8

---

Under review as a conference paper at ICLR 2021
Tracecff on M4&ST
Tradeaff Color MAIST
Tradeeff Coler PRIST
22-
4. 3.5 0.
3.00
0.44
4.35
3.08
0.30
Figure 4: The application of FERMI Color MNIST dataset (Li & Vasconcelos 2019 As expected, FERM achieves a tradcoff between demographic parity I. violation and train error on the colored training samples. On test data, however, reducing the demographic parity violation translates to less dependence on the color, which avoids overfitting and decreases the test error. Finally, as À increases train error and test error significantly decreases which shows that FERMI avoid overfitting. For stochastic FERMI, we use mini-batch size 512 and achieve a speedup 100x per iteration. Along with scalability, we also observe that the stochastic variant (Algorithm 1 has better generalization performance (lower test error).
that the gap between
noteworthy that the test error achieved by FERMI when o = is 22.6%, as compared to 23.3% obtained using REPAIR (Li & Vasconcelos 2019) for o 0.1. Further decreasing I 0.05 the test error using REPAIR sharply goes above 50%. We were unable to run REPAIR for o = 0.
6 DISCUSSION & CONCLUDING REMARKS
In this paper, we proposed a new notion of fairness, called exponential Rényi mutual information (ERMI). We showed that ERMI is strong notion of faimess violation providing guarantees on several other popular notions, namely Pearson correlation, Rényi correlation, Shannon mutual infor- mation, Rényi mutual information, and T, distance violation. We proposed a Fair Empirical Risk Minimization framework with an ERMI regularizer to balance performance and faimess, and called FERMI. Additionally, we showed that FERMI could be efficiently solved for non-binary sensitive attributes and non-binary target variables. We proposed batch and stochastic algorithms for solving FERMI with convergence guarantees for smooth losses. particular, Algorithm is unique among existing fair algorithms as it is stochastic, making it much more practical for large-scale problems (as demonstrated Sec. (.3). This is made possible by Theorem [5] which leads to an unbiased es- timator of the gradient of ERMI It is not at all clear if replacing ERMI by another regularizer, such as Rényi correlation or Shannon mutual information, in Eq. 112) would be amenable to stochastic optimization.
From an experimental perspective, we showed that FERMI leads to better accrnessyaccuacyy tradeoffs than the existing baselines. There several possible explanations for the superior empirical per- formance of FERMI compared to existing methods. One possible reason is that the objective func- tion Eq. 12) is easier to optimize than the objectives of competing in- po-processing methods: ERMI is smooth; and in the discrete case, is equal to the trace of a matrix (see Theorem (). which is easy to compute. Contrast this with the larger computational overhead of Rényi correlation, for example, which requires finding the second singular value of a matrix. Furthermore, the sample complexity of estimating Rényi mutual information of order 2 (and consequently that of ERMI) scales as O / as compared to Shannon mutual information which scales as (([ log (S]) (Acharya al. 2014). Another possible explanation is that ERMI is a stronger notion of faimess than all of the most widely used fairness notions, as shown Sec. 3 which might lead to better generalization. Together, these facts suggest that ERMI serves as efficient and easily optimizable proxy for these other notions, leading to better practical performance regardless of which fairness measure is used. We leave as future work to rigorously understand which of these (or other) factors are responsible for the favorable performance tradeoffs observed from FERMI. Finally, on the Color MNIST experiment with neural network function approximation, FERMI. In this case, we suspect that the randomness in stochastic FERMI supposedly contributes to its convergence local minimum with superior generalization performance compared batch FERMI (see (Kleinberg et al. 2018) and the references therein).
observed that stochastic FERMI outperforms batch

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. The complexity of estimating Rényi entropy. arXiv: 1000vI, 2014.
Sina Aghaci, Mohammad Javad Azizi, and Phebe Vayanos. Learning optimal and fair decision trees for non-discriminative decision-making. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1418-141888 1426, 2019.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. ProPublica, 2016.
Sina Baharlouei, Maher Nouiched, Ahmad Beirami, and Meisam Razaviyayn. Rényi fair inference. In ICLR, 2020.
Yahav Bechavod and Katrina Ligett. Penalizing unfairness in binary classification. arXiv preprint arXiv:1707.0004 2017.
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 1rXiv:1706.02409, 2017.
Tolga Bolukbasi, Kai- Wei Chang. James Y Zou, Venkatesh Saligrama, and Adam T Kalai. Man is to computer programmer as woman is to homemaker? debiasing word embeddings. In Advances in neurul information processing systems, pp. 4349-4357, 2016.
Jaewoong Cho, Gyeongjo Hwang, and Changho Suh. A fair classifier using mutual information. In 2020 IEEE International Symposium on Information Theory (ISIT), pp-
IEEE, 2020.
Evgenii Chzhen and Nicolas Schreuder. A minimax framework for quantifying risk-faimess trade- off regression. arXiv preprint arXiv:2007. 010000//42633 /4265, 2020.
Andrew Cotter, Heinrich Jiang, Maya R Gupta, Serena Wang, Taman Narayan, Seungil You, and Karthik Sridharan. Optimization with non con-differentiable constraints with applications to fairness, recall, churn, and other goals. Journal of Machine Learning Research, 20(172):1-59, 2019.
Thomas M Cover and Joy A Thomas. Information theory and statistics. Elements of Information Theory, 1(1):279-335, 1991.
Imre Csiszár and Paul C Shields. Information theory and statistics: A tutorial. Now Publishers Inc, 2004.
Amit Datta, Michael Carl Tschantz, and Anupam Datta. Automated experiments on ad privacy settings. Proceedings on privacy enhancing technologies, 2015(1):9--122, 2015.
A. Dembo and O. Zeitouni. Large deviations techniques and applications. Springer Science & Business Media, 2009.
Michele Donini, Luca Oneto, Shai Ben-David, John Shawe-Taylor, and Massimiliano Pontil. Em- pirical risk minimization under faimess constraints. In Advances in Neural Information Process- ing Systems, pp. 2791-2801, 2018.
Flavio du Pin Calmon, Ali Makhdoumi, Muriel Médard, Mayank Varia, Mark Christiansen, and Ken R Duffy. Principal inertia components and applications. IEEE Transactions on Information Theory, 63(8):501 I 15338, 2017a.
Flavio du Pin Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. Optimized pre-processing for discrimination prevention. In Advances in Neural Information Processing Systems, pp. 4992-4001, 2017b.
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, 2012.
10

---

Under review as a conference paper at ICLR 2021
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 knowledge discovery and data mining, pp. 259 268,,668,10 2015.
Benjamin Fish, Jeremy Kun, and Ádám D Lelkes. A confidence-basee approach for balancing fair- ness and accuracy. In Proceedings of the 2016 SIAM International Conference on 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 Mechanice/Zeitschriff für Angewandte Mathematik und Mechanik, 21(6):364-379, 1941.
Vincent Grari, Boris Ruf, Sylvain Lamprier, and Marcin Detyniecki. Faimess-aware neural Réyni minimization for continuous features. arXiv preprint arXiv: /9/1 1.04929, 2019.
Vincent Grari, Oualid El Hajouji, Sylvain Lamprier, and Marcin Detyniecki. Learning unbiased representations via Rényi minimization. arXiv preprint arXiv:200.003883 2020.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pp. 3315-3323, 2016.
Hermann Hirschfeld. A connection between correlation and contingency. In Proceedings of the Cambridge Philosophical Society, volume 31, pp. 520-524, 1935.
Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. In Uncertainty in Artificial Intelligence, pp. 862-872. PMLR, 2020.
Faisal Kamiran, Toon Calders, and Mykola Pechenizkiy. Discrimination aware decision tree learn- ing. In 2010 IEEE International Conference on Data Mining, pp. 869-874. IEEE, 2010.
Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma. Fairness-aware learning through regular- ization approach. In 2011 IEEE 11th International Conference on Data Mining Workshops, pp. 643-650, IEEE, 2011.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimess gerryman- dering: Auditing and learning for subgroup fairness. In International Conference on Machine Learning, pp. 2564-2572, 2018.
Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? In International Conference Machine Learning, pp. 2698 2707, 2018.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recog- nition. Proceedings of the IEEE, 86(11):2278 2324, 1998. doi: 10.1 10995776699.
Yi Li and Nuno Vasconcelos. Repair: Removing representation bias by dataset resampling. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9572- 9581, 2019.
Tianyi Lin, Chi Jin, and Michael I. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. arXiv: 1906.0033/v6. 2020.
Luo Luo, Haishan Ye, and Tony Zhang. Stochastic recursive gradient descent ascent for stochastic minimax problems. arXiv: 2001.03724, 2020.
nonconvex--ttrongly-oom
Yurii Nesterov. Introductory lectures on convex optimization: basic course, volume 87, Springer Science & Business Media, 2013.
Adrián Pérez-Suay, Valero Laparra, Gonzalo Mateo-Gareía, Jordi Muñoz-Mari, Luis Gómez-Chova. and Gustau Camps- Valls. Fair kernel learning. Joint European Conference on Machine Leam- ing and Knowledge Discovery Databases, pp. 339-355. Springer, 2017.
Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. In Advances in Neural Information Processing Systems, pp. 5680-5689, 2017.

---

Under review as a conference paper at ICLR 2021
Edward Raff, Jared Sylvester, and Steven Mills. Fair forests: Regularized tree induction to minimize model bias. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp- 243-250, 2018.
Alfréd Rényi. On measures of dependence. Acta Mathematica Academiae Scientiarum Hungarica. 10(3-4):441455,, 1959.
Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume I: Contributions the Theory of Statistics. The Regents of the University of California, 1961.
Ashkan Rezaci, Rizal Fathony, Omid Memarrast, and Brian D Ziebart. Fairness for robust log loss classification. In AAAI, pp. 5511-5518, 2020.
Daniel Steinberg, Alistair Reid, Simon O' O'Callaghan, Finnian Lattimore, Lachlan McCalman, and Tiberio Caetano, Fast fair regression via efficient approximations mutual information. arXiv preprint arXiv:2002.06200 2020.
Latanya Sweeney. Discrimination in online ad delivery. arXiv preprint arXiv: arXiv: 1301.6822, 2013.
Bahar Taskesen, Viet Anh Nguyen, Daniel Kuhn, and Jose Blanchet. A distributionally robust approach fair classification. arXiv preprint arXiv:2007.09530, 2020.
Hans S Witsenhausen. On sequences of pairs of dependent random variables. SIAM Journal on Applied Mathematics, 2801)1100-113, 1975.
Blake Woodworth, Suriya Gunasekar, Mesrob Ohannessian, and Nathan Srebro. Learning non- discriminatory predictors. arXiv preprint arXiv: 2017.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fair- ness constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pp- 962-970. PMLR, 2017.
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 on AI, Ethics, and Society, pp. 335-340, 2018.
12

---

Under review as a conference paper at ICLR 2021
A EXISTING NOTIONS OF FAIRNESS
Let (Y,Y, () denote the true target, predicted target, the advantaged outcome class, and the sensitive attribute, respectively. We review three major notions of fairness.
Definition 7 (demographic parity (woor et al. 2012 We say that a learning machine satisfies demographic parity if Y is independent of S.
Definition 8 (equalized odds (Hardt et al. odds, if Y is conditionally independent of given Y.
2016)). We say that a learning machine satisfies equalized
Definition (equal opportunity (Hardt et al. 2016)). We say that learning machine satisfies equal opportunity with respect to A, Y Y is conditionally independent of S given Y for all E A.
Notice that the equal opportunity as defined here generalizes the definition in (Hardt et al. 2016). It recovers equalized odds if A V/ and it recovers equal opportunity of (Hardt et al. 2016) for A = {1} in binary classification.
B PROPERTIES AND SPECIAL CASES OF ERMI
Notice that ERMI is in fact the divergeee between the conditional joint distribution, Py.s and
the Kronecker product of conditional marginals, Py @ ps; where the conditioning is Z 2. Further, x -dvveeegeee an f-divergence with f(t (t 1) See (Csiszár Shields 2004
Section 4) for a discussion. As an immediate result of this observation and well-known properties of f-divergences,
state the following property of ERMI:
Remark 7. Dn(Y;
2) 0 with equality if and only if for all E 2, y and S are conditionally independent given Z = 2.
To further clarify the definition of ERMI, especially as it relates to demographic parity, equalized odds, and equal opportunity, we will unravel the definition explicitly few special cases.
First, let Z = and Z = {0}. In this case, Z E Z trivially holds, and conditioning on Z has no effect, resulting in:
DR(Ý;S)= DR(Y; E Z)
z=0,z=(0)
P& (P,s(Y,S))
Ey.g
pp (Y (Ps(S)
Py. P9.s (ū. 8) Pp (T)s((s
Σ
Dy, (D. 8)dj.
(17)
Pp ps))s
#ES BEY
DR(P;S) is the notion of ERMI that should be used when the desired notion of faireess is de- mographic parity. In particular, DR(Y; ; S) implies that x2 divergence between py.s: ss and the Kronecker product of marginals, & ps is zero. This in turn implics that Ý and are independent, which is the definition of demographic parity. We note that when y and S are discrete, this special case (Z = and Z = {0)) of ERMI referred to as x² ---iformmtioon ddu Pin Calmon et al, 2017a).
13

---

Under review as a conference paper at ICLR 2021
Next, consider Z Y and 2 V. In this case, Z 2 is trivially satisfied, and hence,
DR(Y:S|Y) ; Z) 2=Y
Pp/s/ (8,
Eyp
(PqIx (Y y)
Pp.s (T, sly) ppiy (iW))ssyy
Σ #ES VEY JEEY
/
Py PY. 0, s)dddy
Prly (71))s
PYSS 1 y
Σ
NEY JäE PpTy WTDPss (s|y) py (v)dydy 1.
(18)
; ;)Y) should be used when the desired notion of fairness equalized odds. In particular, ;a(Y;S|V directly implies the conditional independence of Y and S given Y. Finally, consider Z Y and Z A. In this case, have
DA(Y)SM)) Dıa S1 2)
Z=Y pV. Y (8,5)))
= =yyss
YE A
PP (SSI(
Pr (ū, sly)
ppjr (01))ss
Σ/ SES' MEA JEY
p (y)dydy
pily (T1y)s (sly)
Py PP (T/ sly)²
Σ
EES yEA JEY Prly (0 (0u)ps (s|y) ps s| (T. sly)p+
(19)
where
pr
pv( = Py
(20)
Py (y') ddy
This notion what should be used when the desired notion of fairness equal opportunity. This can be further simplified when the advantaged class is singleton (which is the case in binary classification). Z Y and 2 {y). then
P y) = 1(1)
(v) (1:
Pp S|Y (T, sly) pp (1u))s(y(sss))
Σ
Ps.sly P sly)dg
(0.
Prly (oy(()) (sly)
#ES DEy
PP PP (ū. 22
dÿ 1.
(21)
SES JEY Py 1 (sly)
Finally, we note that the notation Dn Y S and Dra Y: S v) to be consistent with the definition of conditional mutual information in Cover & Thomas 1991).
C RELATIONS BETWEEN ERMI AND OTHER FAIRNESS VIOLATION NOTIONS
Proof of Theorem
L We proceed to prove all the (in)equalities one by one:
0 < [ S Z). This is well known and the proof can be found in any information theory textbook (Cover& & Thomas 1991).
LYYY512 E Z) < (²: sIZ e 2). This a known property of Rényi mutual informa- tion, but provide proof for completeness in Lemma
14

---

Under review as a conference paper at ICLR 2021
1(0:5IZ 2) ed((P:s) 1. This follows from the fact that x S 6 cl(Pi9)zZZ -1 = (r((;
; , 2). This follows from simple algebraic manipulation.
Lemma 1. Let Y,S,2 S
Z be discrete or continuous random variables. Then:
(a) For any a, 3 E [1, 2t
2)
(b) lim Ia (Y; E 2) = LY: := Bz DEL (DL (Py, .iz .szz lpg @ ps|z) Z z) where 11(--) denotes the Shannon mutual information and DEL is Kullback-Leibler di- vergence (relative entropy).
(c) For all E [1, oo), 1Y SIZ 2) 2 0 with equality if and only for all 2 E Z, y and S are conditionally independent given 2.
Proof. (a) First assume 0 < 3 < and that 3 1. Define a 1, and b = B - 1. Then the function Φ(t) = bb/a convex for 2 O, so by Jensen's incquality we have:
1 b
log (B) {B{
Pf p( (P((1))(SSZ))
ZEZ 1)
{B{ B
(((11)((S(z) (
p( p(Y. ZIZ)
b/a
log
ZEZI
b
p(F. (((1Z)p(SIZ)
1)
log
E
Z Z
(22)
Now suppose a = 1. Then by the monotonicity for a * proved above, we have :): = lim : = (u, (Y;5) I infa>1 la (Y; Also, 1o0 (Y;))
lima-so0 Ia (Y: S) supa>o Ia (Y:
(b) This is standard property of the cumulant generating function (see (Dembo & Zeitouni 2009
(c) It is straightforward to observe that independence implics that Rényi mutual information van- ishes. On the other hand, if Rényi mutual information vanishes, then part (a) implies that Shannon mutual information also vanishes, which implies the desired conditional independence.
Proof of Theorem
The proof completed using the following pieces.
3)| < p SIZ E Z). This is obvious from the definition of pR( Z).
0 S |p(Y
PR(Y, S|Z Z) (Y: Z). This follows from Theorem g
Notice that if [| = 2, Theorem implies that DR(Y; Z) P 2).
Theorem 8. Suppose that S [k:]. Let the k l matrix P be defined P {Po).CENM())
where
PV. i)pp.) sw..))
Pg (J) vEY
dy.
(23)
pp
Let 1= =
200 ....2 0k 2 0 be the eigenvalues of P. Then,
Pn(Y,5) =02,
(24)
k
DR(Y;S) = Tr(P) - 1- Σ
oi.
(25)
1=2
15

---

Under review as a conference paper at ICLR 2021
Proof. Eq.
24
is proved in (Witsenhausen 1975
Section 3). To prove Eq.
25
notice that
Tr(P) Σ
Pa
iE(R)
PV,s(V:0)2 Pp(1)) }
Σ EE[R]
dy
Ps(i)
yEE
(P..((P.))
PP
Epss
(p)()ss(S))
+ Dix( (P:),,
which completes the proof.
Proof of Theorem suffices to prove the inequality for L1, as Lg is bounded above by L1 for
all 2 1. The proof for the case where Z 0 and Z {0} follows from the following set of inequalities:
= #ES vey
E/
P8 (T,,(,, py (w)ps(s) dy
(26)
(u,,) po (z)ps(s)
Σ /
#ES BEY VPs(W)ps(s)
dy
(27)
VPp (s)
/E/// WES DEY
(pV,s(U,)) pp (v)ps(s))
Σ HES DEy
Pp PV(U)p((sddy)
Pp (p(()ps(s)
(28)
(pp,s(uis) pp (U))s(())) Pp Pp(l)ps(s)
Σ
<
dy
(29)
SES vEY
Pn(P:))
(30)
where Eq. 28 follows from Cauchy- Schwwaz inequality, and Eq. (30) follows from Lemma
The extension to general Z and Z is immediate by observing that (Y, E 2)
Ez p( S|z) Z E 2
pR(Y, SIZ 2) Ez [PR(Y, Z 2 and DR(Y 8|z
2) Ez Dn s|Z) Z E Z
Lemma 2. We have
(pp.s(y,s) Pp (v)ps(s))²
D
dy.
(31)
pq (
*E. NEY
16

---

Under review as a conference paper at ICLR 2021
Proof.
The proof follows from the following set of identities:
(py,s(U, 8) P0-ppplu ppp(y)s(()))
(pp p 8))
Σ 8E8 yEy
dy Σ
#ES MEY py (y))ps(() dy
Py (v)ps(s)
Σ
Pp,s(1,0 s)dy
#ES NEY
Σ
Pp Pq(y)p(()dd
(32)
#ES VEY
Py (Y
E
-
(33)
(P)s))ps())
DR(P;S)-
(34)
Next, present some alternative fairness definitions and show that they also upper bounded by ERMI.
Definition 10 (conditional demographic parity Los violation). Given a predictor Y supported on y and discrele sensitive atribule S supported a finite set S, define the conditional demo- graphic parity violation by:
dp = sup max gey #ES (p]s(0 py pp)
(35)
First, we show that dp(P is reasonable notion of fairesss violation.
Lemma 3. dp(P)s) = 0 iff (if and only if) & and S are independent.
Proof. By definition, dp(P1s) = 0 iff for all ÿ E v, E S. Pv (7,s(0)))) = Py (T) iff Φ and S are independent (since we always assume p(s) > 0 for all E S).
Theorem (ERMI is stronger than conditional demographic parity L violation). Let Y be dis- crete or continuous random variable supported on y, and S be discrete random variable supported on a finite set S. Denote min min.es ps (s(s) > Then,
< dp( < pmin V DR((:)).
(36)
Proof. The proof follows from the following set of (in)equalities:
(áp(P1s))
2
sup max Bey #ES pp (P)))())s)) - pp (7)
(37)
x sup max Jey RES
Pp (p. 8) - -pp (p)s)
(38)
(p
< (pmin)²
pp.s (p.s(0.s) s) py (8)s()))
(39)
JEy SES
Die(P; Pr
(40)
(pmin
where Eq. 440) follows from Theorem
3
17

---

Under review as a conference paper at ICLR 2021
Definition 11 (conditional equal opportunity Lx violation (Hardt al. 2016)). Let Y, take val- ues in y and let A S y be a compact subset denoting the advantaged outcomes (For example. the decision "to interview" an individual classify an individual "low risk" for financial pur- poses), We define the conditional equal opportunity Loo violation of Y with respect the sensitive attribute S and the advantaged outcome A by
20 Eo E A): Ey sup max jEY sES Pt pr - ( r - ae...
(41)
Theorem 10 (ERMI is stronger than generalized equal opportunity Kolmogorov violation alterna- tive definition). Let Y, Y, be discrete continuous random variables supported Y, and let S be a discrete random variable supported on a finite set S. Let Let C y be a compact subset of y. Denote minn min, AS/Y (sly)- Then,
0 S ēo E)) pmin DD(FF e A).
(42)
Proof. Notice that the same proof for Theorem would give that for all E A:
S sup max jey sES
(018, pry (7lv) = eP
D = y)
Psly
5
DR(P; = 9).
min PSc
Hence,
co(Pisy EA) = Ey { co (o(P))))) Y YEA}
By {VDA(P:SIY) Y EEA
<
PS
Ey (D
min
PIA
Pn(Y:S(Y A),
PS
where the last inequality follows from Jensen's inequality. This completes the proof.
D STOCHASTIC FERMI
Let W* E arg maXWe - TT(WP, Tr(WPs Pg..Pr P-1/2). We will compute W* and plug it in the RHS of Eq. (16) to show the equality in Eq. (66). Seuting the derivative of the expression on the RHS equal to zero leads to:
Proof of Theurem 5
2W Pg + 2P 1/2pT V. = = W Pr
p-1pT P- 1/2
8.a
Plugging this expression for W we have
Tr(WP,WT Tr(
Tw Pg P.
W V
-T((P--122p p- 1 p-1/2) 2TP
P
1. P 1-1/
0.5
1/2P,-1/2p! P P Po..P-112 1/1
J.5 g
=Tr(P, -TrPP-pPT p Pr.e)
1,8
18

---

Under review as a conference paper at ICLR 2021
Writing out the matrix multiplication explicitly in the last expression, have
P.- p. 3. 5.0 P PB = UV
where Un, s(,,)) and Vi, b (i) " ((.,s,,,i,, for i [k], E [m]. Hence
max WeR*xm
(W/)))))) Tr(WP3W")) + TT Ps.
P.. P.
=TrUVT))
pp if, ΣΣ
ps( (i)
ie jE(m)
D (Y;(S)).
which completes the proof.
Next, we move to the statement and proof of the precise version of Theorem 6 We first recall some basic definitions:
Definition 12. A function is B-smooth for all u, u', have [V V B u'll-
Definition 13. A point 0 is an e-stationary point of a differentiable function & V s e. E twice differentiable, Le-iiscchiz, and Be-smooth O.
Assumption 2.
NoPalle
Ve vec S by and maxiemm Va ((P3)1a) S Ly
maxie(m]
V 00
Py)t. 12 s By.
IV 0 = V vecl pP ll1 S Lay and maxie/m)JEMM Ve ((Pg))). lle Lyy
maxig(m]Je(( Vi (i.)))lll I By.s.
Theorem 11 (Precise version Theorem 6). Denote
S(0,W) = N
Σ iE[N]
((x; Ms; 0) + x (-T+(P?W"))+ + TT Po..P- -1)
Set W (D) R (Frobenius norm ball of radius 2D), D
Denote gratn pan
Dq = (fv) ming (()), where (()) == maxwew f(0, W). In Algorithm choose the step-
sizes as = 0 / and f/ = (1) and mini-batch size as M = θ (max {1 1xo26-2)
Then under Assumption
2 the iteration complexity of Algorithm to return an e-stationary point of
f is bounded by
x22 123 1=,3222 D2
22
which gives the total stochastic gradient complexity of
kv BA + k,92 D
max (1, Lo, (L, 22)
62
where
3t BAD
=
4A
(Vrhk3/2 + 2A + 4a
DLy +
Lys
p imin
v Vinin
= 2Xp min
K = 3/1,
8² 22 Le 2XI, 4) Vik )
D
+22 (2AD 1/ghiinnnl////niin 11/2
pmin
The theorem follows from Lin et al. 2020 Theorem 4.5) combined with the following technical lemmas. We assume Assumption holds for the remainder of the proof of Theorem 11
19

---

Under review as a conference paper at ICLR 2021
Lemma 4. Let
S(0. N
Σ
((x;, Vs: 0) + (00))(+((WTT)))) +2T P. -1)
eE[N]
Σ N
g(0. k;,
Then
1. I is B-smooth, where 3 Br + SAD23, + 4A Vopa (Vmk3/2DByy)) + 2A +
4X Dly +
Lyy Vinua
2. f(0,-) 2Xp7 -strongly concave for all O.
3. |W $ D. where D is defined in Theorem 11 and W denotes any maximizer of f(0. W).
Proof. By Assumption 2 9 is twice continuously differentiable. Hence for part 1, it suffices to upper bound the spectral norm of the second derivative of g(:..,) by 8 for all (x, y). where we vectorize and then differentiate with respect to w == vec W and/or 0, so that the resulting first and second derivatives always vectors matrices (not tensors). Notice that g w. z)
f(z, 0) \w (Py & I)w + 2\( 2X(vec(W))) Ps
P/1/2 À and
V g0, w. 2)
V A
( 22
V ( w. ww0 10, W.
woS w2
Further, by the definition of operator norm, we have
I 90, w, 2) - (e (,,00 w. x)](2 + 2/ V w, 2) 2)|12 +
w, x)1l2.
Now we vectorize all matrices and then compute derivatives of g with respect to and vec rec(W):
Veg(O, w. = Vol(z, 0) 2AV a vec(Pt)" vec(W" + 2AVo vec(Pa..) vec(WT p-
(43)
= Vol(z, - 22
Σ
W ((Pg)1))
[c(m])iE(k]
21
Σ
WiS (P (.))) (P
(44)
jjE(m
V.. v..(0,w.. w2) = 22W Pg 2AP. 1/2 PT
(45)
Differentiating again yields:
V w (0, w. z) 2XP; S Ta;
0g(0, (0, w. z)
2 (0, w. z) = 00 dw
2A(I, & WWV + 2A(1, @ P.-1/2)V vec(Pf.))
2 10, w.z) = Vol(z, 0) 2X
Σ
W ((P))t))
[E(m),
+ 2A
Σ
( (Pon)s.) (P-111))
jE(m]
20

---

Under review as a conference paper at ICLR 2021
Then to establish part use Assumption 2 Clairaut's theorem, the definitions of the matrices and fact that their entries are in [0, 1]. the relations ||AB||2 l Σ || and || vec 11 I
vmkll vec 2 = W and the fact that || & 2 = || to bound the spectral
norm of each second derivative above.
The strong concavity statement follows by noticing V (w W) < - iff Pg min;gjm]] (i( #
I
Part 3 follows from the expression for W* in the proof of Theorem 5
Lemma 5, Consider f and as defined above. Then we have
E2 V W,z) z) = vf(o.W),
Ex Vg(0, V/ W) 2 L 22 D2 42 Vpnin
D
v Vkklays
1122 + 2 2AD + 2(0 -11/ 11/2/mk/
where both expectations are with respect to the empirical distribution on {ZibelN)
Proof.
The first statement is obvious. The second follows from Eq. 44 in the proof of Lemma
since
V W. z)
f(0 w
N
N
Vg(e, W, 22)1
Vgl
N
N2
< 2sup
Vg(0,, W, W,2.)
< 2sup
[1 "g 22)) + || (00 W, W1
< 2sup
Vol(z, 0) 21
Σ
W ((P)).)
[E(m],i[(k)
+ 2A
WV (Pos)ja) (P-
jEim],iE[k]
+ 2 2AW Pg 2XP. 1/2 PT
7.
Then use Assumption 2 and basic norm inequalities to bound the norm of each term.
E EXPERIMENT DETAILS
E. MODEL DESCRIPTION
For all the experiments, the model's output is of the form O softmax(Wa b). The model outputs are treated as conditional probabilities p(ū i|æ) O; which are then used to estimate the ERMI regularizer. We encode the true class label Y and sensitive attribute S using one-hot encoding. We define f() as the cross-entropy measure between the one-hot encoded class label Y and the predicted output vector O.
We perform the experiments in sections 5. and 5.2 with a linear model (with softmax activation). The model parameters are estimated using the algorithm described section 4.1. In section 5.2, the data set is cleaned and processed described in (Kearns et al.) 2018). The trade-off curves for FERMI are generated by sweeping across different values for X in [0, 100], learning rate n in [0.0005, 0.01], and number of iterations T in [50, 200).
21

---

Under review as a conference paper at ICLR 2021
For the experiments in section 5.3, create the synthetic color MNIST described in Li & Vasconcelos) 2019). We set the value a = O. In figure 4 we compare the performance of stochastic solver (section 4.2) against the GD algorithm (section 4.1). We use mini-batch of size 512 when using the stochastic solver. The color MNIST data has 60000 training samples, so using the stochas- tic solver gives speedup of around 100x for each iteration, and an overall speedup of around 40x. We present our results on two neural network architectures; namely, LeNet-5 (Lecun et al. 1998) and Multi-layer perceptron (MLP). We set the MLP with two hidden layers (with 300 and 100 nodes) and an output layer with ten nodes. A ReLU activation follows each hidden layer, and softmax activation follows the output layer.
Some general advice for tuning A: Larger value for À generally translates to better faireess, but one must be careful to not use very large value for À as it could lead to poor generalization performance of the model. The optimal values for X, 17, and 7 largely depend on the data and intended application. We recommend starting with 10. In Appendix (F.2 we can observe the effect of changing on the model accuracy and fairness for the COMPAS dataset.
E.2 EFFECT OF HYPER-PARANE PAEER-PRRAMEERR TUNING ON THE ACCURACY-FAIRNESS TRADE-OFF
We rum ERMI algorithm for the binary case to COMPAS dataset to investigate the effect of hyper- parameter tuning the accuracy-faiin fairness trade-off of the algorithm. As it can be observed in Fig. [5] by increasing À from to 1000, test error (left axis, red curves) is slightly increased. On the other hand, the fairness violation (right axis, green curves) is decreased over, for both notions of fairness (demographic parity with the solid curves and equality of opportu- nity with the dashed curves) the trade-off between test error and fairness follows the similar pattern. To measure the fairness violation, we use demographic parity violation and equality of opportunity violation defined in Section equation 5 for the solid and dashed curves respectively.
increase À to 1000. More-
0.31
0.225
0.200
0.30
0.175
Fairness Violation
Test Error
0.150
0.29
0.125
Demographic Parity Notion
0.100
Equality of Opportunity Notion
0.28
0.075
0.050
0.27
0.025
0
200
400
600
800
1000
Lambda
Figure 5: Tradeoff of fairness violation vs test error for ERMI algorithm on COMPAS dataset. The solid and dashed curves correspond to ERMI algorithm under the demographic parity and equality of opportunity notions accordingly. The left axis demonstrates the effect of changing À on the test emor (red curves), while the right axis shows violations) depends on changing X.
fairesss of model (measured by equality opportunity or demographic parity
22

---

Under review as a conference paper at ICLR 2021
E.3 DATASETS DESCRIPTION
All of the following datasets are publicly available at UCI repository.
German Credit Dataset [ German Credit dataset consists of 20 features (13 categorical and numerical) regarding to social, and economic status of 1000 customers. The assigned task to classify customers good 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 the test data. The sensitive attributes are gender, and marital-status.
Adult Dataset - Adult dataset contains the census information of individuals including education, gender, and capital gain. The assigned classification task to predict whether a person earns over 50k annually. The train and test sets are two separated files consisting of 32,000 and 16,000 samples respectively. We consider gender and race as the sensitive attributes (For the experiments involving one sensitive attribute, we have chosen gender). Learning logistic regression model on the training dataset (without imposing fairness) shows that only 3 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 in this case is still highly biased. For the clustering task, we have chosen 5 continuous features (Capital-gaad -gii,, age, fnlwgt, capital hours-per-weede and 10,000 samples to cluster. The sensitive attribute of each individual is gender.
Communities and Crime Dataset [ The dataset is cleaned and processed as described in (Kearns al.) 2018). Briefly, each record in this dataset summarizes aggregate socioeconomic information about both the citizens and police force in a particular U.S. community, and the problem is to predict whether the community has high rate of violent crime.
COMPAS Dataset Correctional Offender Management Profiling for Alternative Sanctions (COM- PAS) is a famous algorithm which widely used by judges for the estimation of likelihood of re- offending crimes. It is observed that the algorithm is highly biased against the black defendants. The dataset contains features used by COMPAS algorithm alongside with the assigned score by the algorithm within two years of the decision.
23


Reviews:
[{"review_id": "wXxnSBiRYJ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies fair classification by using the notion of Exponential Renyi Mutual Information. As certain notions of fairness can be encoded using (conditional) independence, this paper propose to use some information theory notions of mutual information to quantify this degree of (conditional) independence, which indirectly translates to the degree of fairness. A classification algorithm with low value of mutual information between the prediction and the sensitive attributes can be considered as fair.\n\nThe paper establishes that the Exponential Renyi Mutual Information is a strong notion to ensure fairness: the authors show that this notion is stronger than many existing notions such as Lq fairness, etc. The authors propose an algorithm to train a fair classifier, with the mutual information being penalized in the objective function.\n\nStrength:\n- The idea of combining information theory notions to measure independency and applying it to fair machine learning is natural.\n\nWeakness:\n- I have some concerns with the mathematical notations in this paper.\ni) The definition 2 is very misleading. Consider for equalized odds with \\mathcal Z = \\{0, 1\\}: it is not clear to me why this definition correctly capture the conditional independence. To my best understanding, the conditioning here should be taken as 2 separate conditional expectation: one conditional expectation with Z = 0, and another conditional expectation with Z = 1. The mathematical definition in equation (2) does not seem to segregate the values of Z. Moreover, why is the expectation taken over Z when we already condition on Z \\in \\mathcal Z?\nii) What is D_R(\\hat Y_\\theta, S) in equation (11)? I guess the authors mean the D_R function with condition as in equation (2)?\n\n- The authors show that ERMI is stronger than existing notions, which is nice. However, it is not clear why a stronger notion is preferable for the penalized optimization of the form (11). One can think of penalizing the Shannon mutual information with higher penalty parameter lambda, and one may expect to see similar end results as problem (11) -- especially if we plot the accuracy-fairness tradeoff similar to Figure 1.\n\nMinor comments:\n- Lemma 1 is quite trivial. I think this lemma should be put as discussion in the paper, and not a separate lemma.\n- Why are the expectation in equation (15) taken with X?\n- The proof of Theorem 5 does not seem to prove what is stated in Theorem 5.\n- The notations in equation (11) can be made more explicit. For example, I think there is a dependence of \\hat Y_\\theta on X which is not made explicit.", "extra_scores": {}, "extra_text": {}}, {"review_id": "toJeYkk9mX_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors provide a unified view of the existing fairness violation notions and propose a new notion: Exponential Rényi Mutual Information (ERMI) between sensitive attributes and the label. ERMI is easy to compute and provides an upper bound on existing notions. Based on ERMI, the authors propose a framework, FERMI, which can be optimized with SGD with convergence guarantee. In experiments, results show that FERMI leads to a better tradeoff between performance and fairness even if fairness is not measured by ERMI.\n\nMy major concern about the methodology is that it depends on the quality of the empirical estimate of the probability distributions P(s), P(y) and P(y,s). In the experiments, these distributions are relatively simple as S takes either binary values or are samples from Gaussian distribution. And Y is discrete and takes few values. I wonder how the performance of the FERMI would be influenced by the quality of estimates of the three probability distributions. It would be interesting if the authors can show results on the estimation error of the three vs. the performance of FERMI.\n\nIn section 3, the authors show that ERMI is an upperbound of several popular notions: Shannon MI, Renyi correlation, and Lq fairness violation. I have several suggestions and questions: (1) It would be better to specify whether some of them are known before this work. (2) In addition, is there any other transformation of Renyi Mutual Information that can achieve the same goal? (3) Is it possible to specify how tight those bounds are?\n\nIn 5.1, the authors mentioned that one reason FERMI outperforms baselines is that ERMI upperbounds the other notions. I would appreciate it if the authors can clarify this point.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "T7eXVvxbuJ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \n\nThis paper introduces a new fairness notion that takes an exponential form of Renyi mutual information. The strongness of the notion is claimed via the proof (Theorems 1/2/3) that the notion is an upper bound of other well-known notions like mutual information, Renyi mutual information, Renyi correlation, L1 fairness violation. Two methods for estimating the notion via samples are developed under some assumptions. The performances of the methods are then demonstrated on three datasets and compared with some prior algorithms.\n\nStrengths: \n\n1. An interesting observation is made via Theorems 1/2/3: ERMI is an upper bound of other popular notions.  \n2. Explicit algorithms are developed for estimating the notion as differential functions w.r.t. model parameters.\n\nWeaknesses:\n\n1. While the observation in Theorems 1/2/3 is interesting, the proof relies upon the techniques in well-known literature and/or some standard tricks. Perhaps more importantly, it is not investigated in depth how tight the proposed notion is relative to other notions, except for the binary classification case. I believe the tightness analysis is more important, as a loose upper bound plays a less role. \n\n2. Algorithm 1: No justification is provided behind the assumption, in particular (13). Also no analysis is provided regarding the accuracy of the density estimates (16). In particular, this reviewer wonders whether or not the condition density estimate (the 2nd in (16)) is accurate – usually, a precise accuracy requires an exponential number of samples w.r.t. the cardinality of yhat. \n\n3. Experiments: Some baselines based on mutual information are missing, e.g., [A], [B]. Also in the 1st experiment (Fig. 1), (Baharlouei et al 2020) is missing – I think it is needed to compare, since the notion estimation method may be different although ERMI is equivalent to Renyi correlation. Moreover, it is not clear which algorithm to use in all experiments between Algorithms 1 and 2.  \n\n[A] B. Zhang, B. Lemoine, and M. Mitchell. Mitigating unwanted biases with adversarial learning. AIES, 2018.\n[B] J. Cho, G. Hwang and C. Suh, “A fair classifier using mutual information,” ISIT 2020. \n\nClarity: Overall it is well-written and easy to follow. \n\nOther comments: \ni. Why italic in the last sentence in the 2nd paragraph on page 1? \nii. Details on hyperparameter tuning are entirely missing in all experiments.\niii.  A benchmark dataset, COMPAS, is missing. \niv. Not clear why the proposed algorithms offer greater performances. No insight/analysis is provided.\nv. Figure 2: Only RFI is compared, although many other baselines can readily be extentisible to the non-binary classification.\niv. Figure 4: Not clear as to what points the authors wish to make here.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed a new in-processing approach to train fair predictors under several notions of statistical fairness. Tho this end, the author rely  on  the Exponential Renyi Mutual Information (ERMI) between sensitive attributes and the target variable as notion f fairness, and show that it is a strong notion of fairness that provides guarantees on several previously discussed fairness metrics. 

The paper is overall well written and interesting, but as with many other papers on this area, I wonder even after rebuttal whether the paper indeed constitute a step forward in the field. I find the concern raised by the reviewers about the tightness of the bound important and, while the authors properly addressed this point in the rebuttal period, I still believe this is an open question which probably does not have a better answer. On the positive side, the experimental evaluation support the theoretical results. However, comparisons to previous methods are only performed on the Adult and the German dataset, which makes me wonder if the advantages of the proposed approach generalize beyond these two well-studied datasets. As a consequence, the paper remains borderline, as it is an interesting paper but its impact and significance remain limited.  

Moreover, I believe that there are some missing recent related works, that I believe the authors should also compare to. For example, see the recent Neurips 2020 paper, "A Fair Classifier Using Kernel Density Estimation" by Cho et al.  Also, as a side note, previous approached have already considered non-binary (although most of the times categorical) sensitive features, see e.g., [42]. Finally, the author may want to consider complementing their italic comment on the second paragraph of the Intro with existing works that already discussed biased in the labels, due to e.g., the selective labeling problem (see [1-3] below).   

[1] Lakkaraju, Himabindu, et al. "The selective labels problem: Evaluating algorithmic predictions in the presence of unobservables." Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017.
[2] Kilbertus, Niki, et al. "Fair decisions despite imperfect predictions." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.
[3] Bechavod, Yahav, et al. "Equal opportunity in online classification with partial feedback." Advances in Neural Information Processing Systems. 2019.





Decision: Reject