FERMI: Fair Empirical Risk Minimization via Exponential Rényi Mutual Information
Authors: Andrew Lowy
Rakesh Pavan
Sina Baharlouei
Meisam Razaviyayn
Ahmad Beirami
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Algorithmic fairness
nonconvex optimization
information theory.

Abstract: Despite the success of large-scale empirical risk minimization (ERM) at achieving high accuracy across a variety of machine learning tasks, fair ERM is hindered by the incompatibility of fairness constraints with stochastic optimization. In this paper, we propose the fair empirical risk minimization via exponential Rényi mutual information (FERMI) framework. FERMI is built on a stochastic estimator for exponential Rényi mutual information (ERMI), an information divergence measuring the degree of the dependence of predictions on sensitive attributes. Theoretically, we show that ERMI upper bounds existing popular fairness violation metrics, thus controlling ERMI provides guarantees on other commonly used violations, such as $L_\infty$. We derive an unbiased estimator for ERMI, which we use to derive the FERMI algorithm. We prove that FERMI converges for demographic parity, equalized odds, and equal opportunity notions of fairness in stochastic optimization. Empirically, we show that FERMI is amenable to large-scale problems with multiple (non-binary) sensitive attributes and non-binary targets. Extensive experiments show that FERMI achieves the most favorable tradeoffs between fairness violation and test accuracy across all tested setups compared with state-of-the-art baselines for demographic parity, equalized odds, equal opportunity. These benefits are especially significant for non-binary classification with large sensitive sets and small batch sizes, showcasing the effectiveness of the FERMI objective and the developed stochastic algorithm for solving it.

FERMI: Fair Empirical Risk Minimization Via Exponential Rényi Mutual Information
Anonymous Author(s)
Affiliation
Address email
Abstract
Despite the success of large-scale empirical risk minimization (ERM) at achieving high accuracy across variety of machine learning tasks, fair ERM is hindered by the incompatibility fairness constraints with stochastic optimization. per, propose the fair empirical risk minimization via exponential Rényi mutual information (FERMI) framework. FERMI is built on a stochastic estimator for ex- ponential Rényi mutual information (ERMI), information divergence measuring the degree of the dependence of predictions on sensitive attributes. Theoretically, show that ERMI upper bounds existing popular fairness violation metrics, thus controlling ERMI provides guarantees on other commonly used violations, such as T. We derive unbiased estimator for ERMI, which algorithm. We prove that FERMI converges for demographic parity, equalized odds, and equal opportunity notions of fairness in stochastic optimization. Em- pirically, we show that FERMI is amenable to large-scale problems with multiple (non-binary) sensitive attributes and non-binary targets. Extensive experiments show that FERMI achieves the most favorable tradeoff's between fairness violation and test accuracy across all tested setups compared with state-of-the- baselines for demographic parity, equalized odds, equal opportunity. These benefits are especially significant for bonabinary classification with large sensitive sets and small batch sizes, showcasing the effectiveness of the FERMI objective and the developed stochastic algorithm for solving it.
3
this pa-
5
7
derive the FERMI
11
12
13
14
15
16
17
18
20
Introduction
21
22
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 if such discrimination is absent in the training data (Datta al., 2015 Sweeney 2013 Bolukbasi et
23
24
25
26
2016
Angwin et al. 2016 Calmon et al. 2017b; Feldman et al. 2015 Hardi et al. 2016 Fish et al.
27
2016 Woodworth al. 2017; Zatar et al. 2011) Bechavod Ligeti 2017 Kearns al. 2018).
28
Algorithmic fairness literature aims to remedy such discrimination issues.
29
machine learning algorithm satisfies the demographic parity faimess notion, if the predicted target is independent of the sensitive attributes (Dwork et al., 2012). Promoting demographic parity can lead to poor performance, especially the true outcome not independent of the sensitive attributes.
30
31
32 To remedy this, Hardt et al. (2016) proposed equalized odds to ensure that the predicted target is
33 conditionally independent of the sensitive attributes given the true label. A further relaxed version of
34 this notion is equal opportunity which is satisfied if predicted target is conditionally independent of
35 sensitive attributes given that the true label is in an advantaged class (Hardt al. (016). The inherent
36 assumption in such conditional notions is that the true labels are fair. These notions suffer from
37 potential amplification the inherent discrimination that may exist the training data. Tackling
such bias is beyond the scope of this work; cf. Kilbertus al. (020) and Bechavod et al. (2019).
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

Reference
NB
NB
NB
Fairness notion
Beyond logistic
Stoch. alg. (unbiased") ")
Converg. (stoch.)
target
attrib.
code
dp
eod
cop
FERMI (this work)
/
((0)
o (V)
Cho et al.
2020b
/
/
x
/
/ [x)
x
Cho
20200a
/
x
7
7
/
/ (v)
x
Baharlouer et al. 2020
(2)
Rezaei et all 2020
x
x
x
/
x
x
x
x
Jiang et al.
2020
x
/
x
/
x
x
x
x
x
Mary et al..
2019
/
/
/
(2)
Donini al.
2018
X
X
Zhang et al.
2018
x
/ (20
X
Table 1:
Comparison of state-of- tht- in-processing methods. NB = non-binary, dp = demographic parity,
eod = equalized odds, cop equal opportunity. While satisfying eod guarantees satisfying cop, an eod algorithm does not necessarily achieve favorable tradeoff between performance and fairness violation in eop; we only credit those works that provide/implement algorithms for given fairness notion. FERMI the only method compatible with stochastic optimization and guaranteed convergence. The only existing baselines for non- -on-hinary classification with non-binary sensitive attributes are (Mary et al. 2019) Baharlouer et all 2020 Cho et al. 2020b) (NB code). "We refer to the in- processing method of (Jiang et al. (020). not their post-processing method. ** We the term "unbiased" to refer unbiased estimatioo in statistical sense; is not to be confused with bias in the fairness sense, for which we use the term discrimination.
39
Measuring fairness violation. In practice, the learner only has access to finite samples and cannot verify demographic parity, equalized odds, or equal opportunity. This has led the machine learning community to define several fairness violation metries that quantify the degree of (conditional)
40
41
independence between random variables, e.g., Los distance (Dwork et al. 2012 Hardt et al. 2016).
43
mutual information (Kamishima et al.] 201 T Rezaei et al.) 2020; Steinberg et al. 2020 Zhang
44
et al. 2018 Cho et al. 2020aa,, Pearson correlation (afar et al., 2017). false positive/negative rates
45
(Bechavod & Ligett 2017). Hilbert Schmidt independence criterion (HSIC) (Pérez-Suay Suay et all (017),
46
Rényi correlation (Mary et al. 2019 Baharlouci et al. 2020; Grari et al. 2019 2020), and exponential Rényi mutual information (HRM) (Mary et al. (219)). ). In this paper, we focus on three variants of
47
ERMI specialized to demographic parity, equalized odds, and equal opportunity. We prove that ERMI provides an upper bound on the rest of the above existing notions of fairness violation. Consequently, model trained to reduce ERMI will also provide guarantees on these other faimess violations. We also develop a stochastic estimator for ERMI that is compatible with large-scale stochastic optimization, and it as regularizer in within ERM, and call it FERMI. We theoretically show 53 that FERMI is convergent, and empirically demonstrate that it outperforms all other state-of state-of-the-art baselines, including (Mary et al. 2019) which solves the same objective as FERMI.
49
50
51
52
54
55
Related work & contributions. Faimess- prommessp machine learning algorithms can be categorized pre-processing, post-processing. and in-processing methods. Pre- pre-processing algorithms (Feldman et al. 2013 Zemel et al., 2013 Calmon et al.) 7b) transform the biased data features to new space in which the labels and sensitive attributes statistically independent. This transform is oblivious to the training procedure. Post-processing approaches (Hardt et al. 2016 59
in three main classes:
57
Pleiss al. 2017) mitigate the discrimination of the classifier by altering the the final decision. 60
61
In-processing approaches focus on the training procedure and impose the notions of fairness as methods
82
constraints regularization terms in the training procedure. Several regularization-bant
63
are proposed in the literature to promote fairness in decision-trees (Kamiran et al. 2010 Raff ct al.
84
2018 Aghaei al. 2019). support vector machines (Donini et al., 2018). neural networks (Grari
85
et al. 2020g Cho et al. 20205). or (logistic) regression models Zataa et al. 2017 Berk et al. 2017
66
Taskesen et al.] 2020 Chzhen & Schreuder 2020 Baharlouei et al. 2020 Jiang et al.] 2020. Grari
67
et al. 2019). While in- proceessiingg approaches generally give rise to better tradeoff's between fairness
66
violation and performance, existing approaches are mostly incompatible with large-scale stochastic
69
optimization. This paper addresses this problem. See below for a summary of our contributions and
70
Table | for a summary of the main differences between FERMI and existing in in-processing methods.
71
1. We analyze notion of faimess violation called ERMI. We show that ERMI is stronger notion of fairness violation than all existing notions. Therefore, a model that ensures small ERMI violation guaranteed have small fairness violation with respect to all other notions as well.
72
73
74 2. We formulate an empirical objective, called FERMI objective, for using ERMI as a regularizer with empirical risk minimization. We propose a solver for FERMI, which is the first stochastic in prooocsssing fairness algorithm with guaranteed convergence. The existing stochastic fairness
75
2

---

77
algorithms by Zhang et al. (2018): Mary et al. 2019): Cho et al. (2020a b are not guaranteed to converge.
78
79
3. We demonstrate through extensive numerical experiments that FERMI achieves superior fair- ness-accuracy tradeoff curves against all comparable baselines, even when faimess violation is measured in terms of commonly used Loo (for demographie parity, equalized odds, and equal opportunity). In partieular, the performance gap is very large when minibatch size is small (as is practically necessary for large-scale problems), and the number of sensitive attributes is large.
80
81
82
83
Fairness notions: demographic parity, equalized odds, equal opportunity
84
85 In this section, we state a notion of fairness that generalizes demographic parity, equalized odds, and equal opportunity faimess definitions (the three notions considered in this paper). This will be convenient for presenting our theoretical results, Consider a learner who trains a model to make a prediction, Y, e.g., whether or not to extend a loan, supported on 3 which can be discrete or continuous. The prediction is made using a set of features, X, e-g., financial history features. We 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 S y denote an advantaged outcome class, e.g., the outcome where a loan is extended.
87
88
89
90
91
93
Definition ((Z, fairmess),. Given a random variable Z, let Z be a subset of values that Z can 94 take. We say that a learning machine satisfies (Z, ffiiress ffr every z E 2, Y is conditionally independent of S given Z z, i.e. Vÿ EY. E S, 2 E Z, PV,s|z (ū. s|2) = Přiz (7) p)ss z (s|2).
95
Z, 2) -faimesss includes the popular demographic parity, equalized odds, and equal opportunity notions of fairness as special cases:
97
96
and Z {0]. In this case, conditioning on Z has no effect, and hence (0, {0)) fairness is equivalent to the independence between Y and S (see Definition Appendix
(Z, 2) )-farrness recovers demographic parity (Dwork al. 2012
99
100
101
2. (Z Z) ))ffairnsss recovers equalized odds (Hardt et al. 2016) if Z = Y and 2 = In this case, Z E Z is trivially satisfied. Hence, conditioning on Z is equivalent to conditioning on Y. which
102
recovers the equalized odds notion of fairness, i.e., conditional independence of & and S given Y
103
(see Definition 7 Appendix AA.
104
105
3. (Z, -fairness 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
106
107
Note that verifying (Z, Z) )-fainness requires having access to the joint distribution of random variables (Z, Y,YYO S). This joint distribution is unavailable to the learner in the context of machine learning, and
109
hence the learner would resort to empirical estimation of the amount of violation of independence, measured through some divergence. See (Williamson & Menon 2019) for related discussion.
110
Measuring fairness violation using exponential Rényi mutual information
111
112
Most existing fairness violations can be viewed as a (conditional) f-divergence between the joint distribution of sensitive attributes and predicted targets, py,s)z' and the Kronecker proudct of the marginals, Přiz @ Psiz. z. In this section, we focus on ERMI and show that several existing fairness violations are upper bounded by ERMI. For brevity, we present all definitions and results (Z,2). Definition 2 (ERMI- exponential Rényi mutual information). We define the exponential Rényi mutual information between Y and S given Z E Z
114
115
116
DR(Y; 2) = Eg {
PP Pl. (1,)) Py ( (S12)
Z E Z
-.
(ERMI)
118 In Appendix B we unravel the definition for the special cases of interest corresponding to demo- graphic parity, equalied odds, and equal opportunity. We also discuss that ERMI is the diveeregee (which an f-divergence) between the joint distribution, Py, "y,s and the Kronecker product of marginals, py: z 2 Psiz (Calmon et al. 2017a). In particular, ERMI is non-negative, and zero
119
120
121
122
and only if (Z. 2) -ffirness is satisfied. In the context of algorithmic fairness, ERMI was first used by Mary et al. 2019) as a regularizer. We will provide new stochastic solver/estimator for ERMI,
123
which theoretically converges and empirically outperforms the one by Mary et al. (011).
3

---

125 Definition 3 (Rényi mutual information Rényi
1961).. ). Let the Rényi mutual information of order
between random variables Y and S given Z E Z be defined
Pp. (P,
To 2) log Ezyys
(RMI)
(912((12)9911((121)
127
which generalizes Shannon mutual information
py. pV, S1Z)
ZEZ
E(Y: := Ez
log
(MI)
2812 (8 [s)
and recovers it lim I. LY 2) LY: E Z).
129
Note that L. (Y; S|Z E 2 0 with equality if and only if (Z, Z --firmess is satisfied. Theorem (ERMI is stronger than Shannon mutual information). We have
0 $ (Y; S E Z) & SIZ E Z) S (2iZZE - 1= DR(P; E Z).
(I)
131
132
All proof' are relegated to the appendix. Theorem establishes that ERMI is a stronger measure of fairness violation in the sense that driving it zero would also bound the Shannon mutual information, which is used for promoting fairness in recent literature (Cho et al. 2020a). It also shows that ERMI
133
134
135
exponentially related the Rényi mutual information of order 2.
138
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, By (f(;)))} =
137
Es (g(S: 2)) O, EE (J(P;))) = =E {g(S; for all 2 E 2. Rényi correlation is:
138
p S f.gefig
sup ZzP,, { ((()2219(5;)) ZEZ].
(RC)
139
140
Rényi correlation generalizes Pearson correlation,
By (P.s(VSS7))
, S|Z e 2) : Bz
Z E 2
(PC)
By (F11))s(5511)
141
142
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(Y,, Z Z)= > 0 with equality if and only if (Z, Z) ))ffiimesss is satisfied. Rényi correlation has gained popularity as a measure of fairness violation (Mary et al. 2019: Baharlouei et al. 2020; Grari et al., 2020). Rényi correlation is also upper bounded by ERMI. The following result has already been shown by Mary et al. (2019) and we present it for completeness.
145
147
148
Theorem (ERMI is stronger than Rényi correlation). We have
0 5 |p( Sz E 2) S pr SIZ Z) DR(Y:SIZE Z),
(2)
and is|S = P E 2) = pnnpp E 149
Definition 5 (Li, fairness violation). We define the Lig fairness violation for 2 by:
E 2) = EZ (
1/2 2 e 2
Σ 2
(9. pp ( (1) dy
(L4)
Note that LY, SIZ Z) if and only if f)-irressssss is satisfied. In particular, Loo fairness
152
violation recovers demographic parity violation (Keanss et al. 2018 Definition 2.1) if we let Z {0) and Z 0. It also recovers equal opportunity violation (Hardt al. 2016) if Z = A and Z Y.
Theorem 3 (ERMI stronger than Los faimess violation). Let Y be discrete or continuous random variable, and S be a discrete random variable supported on finite set. Then for any 2 1,
154
155
0 S (Ý, SIZ E 2) S D S) ()
33)

---

157
The above theorem says that if a method controls ERMI value for imposing faimess, then Lee violation is controlled. In particular, the variant of ERMI that is specialized to demographic parity also controls Too demographic parity violation (Kaars et al. 2018). The variant of ERMI that is specialized equal opportunity also controls the To equal opportunity violation (Hardr al. 2016). While our algorithm uses ERMI as a regularizer, in our experiments, we measure fairess violation through the more commonly used Lix Violation. Despite this, we show that our approach leads to better tradeoff' curves between fairnsss violation and performance.
158
159
160
162
184
The bounds in Theorems 1-3 are not tight in general, but this is not of practical concern. They show that bounding ERMI is sufficient because any model that achieves small ERMI is guaranteed to satisfy any other fairness violation. This makes ERMI an effective regularizer for D
Remark.
185
186
187
promoting fairness. In fact, in Sec. we see that the proposed algorithm, FERMI, achieves the best tradeoffs between fairness violation and performance across state-of-the-an baselines.
168
4
FERMI: fair empirical risk minimization through ERMI regularization
170
Our goal is train a model that balances fairesss and accuracy objectives. To this end, we introduce fair risk minimization through exponential Rényi mutual information framework defined below
171
min (FRMI(0= == yxsy {((X, ())) + ADR((((X:));
(FRMI obj.)
172
where & denotes the loss function, such as L2 loss or cross entropy loss; À >> 0 is a scalar balancing the accuracy versus fairesss objectives; D (Y (X; 0); S) is the notion of ERMI given in Eq. (RRM)
173
particularized to demographic parity (see Eq. 5 and ((x; 0) is the output of the learned model (e.g., the output of classification or regression task, the cluster number in clustering task).
174
175
While ((x: 0) inherently depends on X and 0, in the rest of this paper, we sometimes leave the dependence of Y 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.
176
177
178
In practice, the true joint distribution of (X, S, Y, ) is unknown and we only have N samples at our disposal, making impossible to solve FRMI. Let {x,, St, Vr. Dr (x;; [)] denote the features, sensitive attributes, targets, and the predictions of the model parameterized by 0 for these samples.
179
180
181
182
Mary al. (2019) considered the same objective Eq. (FRMI obj.). and tried to empirically solve through a kernel approximation. We propose completely different approach to solving this problem: fair empirical risk minimization via exponential Rényi mutual information (FERMI). FERMI results in provably convergent algorithm, and empirically outperforms the algorithm by Mary et al. (2019). is straightforward to derive an unbiased estimate for Ex { 0)] through the empirical risk e.g.. [8T EieB (xx, yi; 0) where B C [N] is a random minibatch of data points. However,
183
184
185
186
187
estimating D S) in the objective function in Eq. FRMI obj. is more difficult. In what follows, we present our approach to deriving an unbiased stochastic estimator of DR((Y, S) given a random batch of data points B. The following theorem is the key tool we use to obtain an unbiased estimator:
188
190
Theorem 4. For discrete random variables Y Ý(X; 0) and S where Y E [m], S E [k]. we have
;)
.mx WeR
{ TWWPPWW 2TTTTWP P. 1/2) - 1
(4)
where Pg = diag(pp (1),...,PP (m)), P. dddig(sss()) (s(k)) and 192
PP,s (1,)(
py k(,k(
P3.5 =
Pp PP.s (m.1
ps (
198 Let Y, 8. E 10m and S, s; E (0, 1 & be the one-hot encodings of γ, Ti and S. S. respectively. Then, the above theorem implies that we can compute an unbiased estimate of Eq. (FRMI obj.):
194
In this section, present all results in the context of Z 0 and 2 {0) (demographic parity), leaving off all conditional expectations for clarity of presentation. The results readily generalized for general (Z, 2) by using Dn(Y, SIZ Z) in Eq. FRMI )bj.)): have used the resulting algorithms for empirical experiments.
5

---

195
Lemma (Unbiased estimator of ERMI). Let S,Y, (X:0) be random draw from Px X
196
Further, let
197
Then, maXWeR (X, S.S.Y. W) is unbiased estimator of ERMI in Eq. FRMI obj. i.e.
Ex,S max WE
& X. S. S. S.YYYY,,..)
199
The stochastic estimator, (X,
W); in Lemma requires the knowledge of Pss and computation of P. 1/2 This can be estimated with high fidelity (for small to moderate sensitive set) through single initial pass the entire dataset in practice. Hence, consider it to be known. Now, we are equipped to state the empirical objective function that we solve in this paper:
201
203
1 N
min max WeR
FERMI W)
[[(x,, y4: 0) + Xp, ()]
(FERMI obj.)
204 where
(0, () == = Tr(Wy.
1/11)) "
(x + (
205
In particular, Lemma D says that, for any N, Eq. FERMI ob (and its gradients) is an unbiased and consistent estimator of the Eq. (RMM obj.) objective function (and its gradients) by an empirical
208
207
contrast the density estimation methods used by Mary et al.) (0199 and |Baharlouei et al. (2020) which are biased but consistent. We will see in the experiments that the unbiased estimator empirically offers large performance improvements.
average over the minibatch. This
208
209
210
This observations leads us to deriving a stochastic algorithm, presented in Algorithm || which is guaranteed converge for any batch size 1 < B < N since the stochastic gradients unbiased.
Algorithm 1 (FERMI Algorithm). Two-Time Scale SGDA for solving FERMI objective
1: Input: 0 E Rdo T E W C kk step-sizes (No. nw), mini-batch B C [N], fairness 0, iteration number R.
parameter
2: for wrt= 0, 1,..., .....,Ro R do
3: Draw mini-batch B of data points {xx;, Si, Mc) hien
4: Set 0t+1 +- 0º
no Eie [ (Vl(x; Mi; 09) + XV ooris(O' W
5: Set W II W 2AT
ΣieB (x; 0¹ >57 (x;00) P.- P.-1/3 1.7 (x)
[B]
6: end for
7: Pick f uniformly at random from (1, (1....,R) R).
8: Return: 0f.
Theorem 5. (Informal statement) Algorithm D converges to the set of e-first order stationary points 213 of the Eq. FERMI obj.) objective in ( ilerations (stochastic gradient evaluations).
214
The formal statement of this theorem can be found in Theorem I0 in Appendix D A faster convergence rate ( could obtained by using the (more complicated) SREDA method Luo al (020) instead of SGDA to solve FERMI objective. We omit the details here. In the next section, we numerically evaluate the performance FERMI algorithm in several numerical experiments.
215
217
Numerical experiments
216
5.1
Binary classification and binary sensitive attribute
220
For our first set of experiments, we evaluate the lairness-accuran tradeoffs of FERMI in binary classification problems with binary sensitive attribute. This is common setup, so we are able to
222
compare against many existing baseline methods (atar et al. 2017 Feldman et al. 2013 Kamishima
223
et
al.
2011
Diang et al. 2020 Hardt et al. 2016 Baharlouei al. 2020 Rezaei et al.) 2020 Donini
et al.
2018 Cho al. 2020b). We run experiments on three data sets: Adult, German Credit, and
225
CASP implement FERMI, we train logistic regression model (same model for all baselines)
with ERMI regularizer. Details about the datasets and experiments can be found in Appendix B

---

a) Adult Dataset
Denggrapic Volattn
Mo00 ct 2017
Equalized Odts Vistetion
Zolor ot
Equality Opportunity Vitealion
Zarle el
2017
0.18
WCoho stall 2020
ang stall p022
0.10
Domntttttt 2010
Dorkh 2018
Redpel stal. 2020
0.15
Bar prove at 2000 2000 mrraal
0.08
Chs waa 2020
0.08
Baharoouii et 2020
0.10
0.06
FERAI
0.06
0.08
0.04
0.03
0.02
0.02
0.00
0.16 0.18 0. 0.20
0.20 Test Error
0.19
0.16
0.17
0.19 Test Error
0.20
Test Error
German Credit Dataset
Equaliy of Opportunity Volalion
Damographi Volaton
0.20
2atar et 2017
2000
Equalied Octs Vilatoo
0.16
0.14
2artrehat:2001
Contn al. 2010
0.14
Zater an 2017
Dones 2215
Chi at. 2000
Recnel 2020
0.12
Aposel 2020
0.15
il Dahhrrlosse 2020
0.12
0.12
0.10
Banarious etal. 2000
0.10
0.08
0.08
0.06
0.06
0.05
0.04
0.04
0.03
0.02
0.02
0.26
0.20
Test Error
Test Error
Test Error
<) COMPAS Datasel
Equality Opportunity Volation
Dencgraphic Parity Viclation
0.14
Zata etal. 2017
Equaltzer Odds Videtiion
0.25
0.20
Dowe
0.12
2010
0.15
Baharlouck of al, 2020 FERVI
Cho at 2020
0.20
Rozed ot 2020
Cho et 2020
0.10
+yousse ot wi, 2000
Bizerurtoia at 2000 WpPerts
0.15
Banerbousi 2000
0.08
PEROVI
0.10
0.10
0.06
0.04
0.05
0.05
0.02
0.00
0.26
0.28
0.30
0.32 0.34
0.36
0.26
0.27
0.28 0.29 0.30 0.31 0.32
0.26
0.27
0.28
0.29 0.30 0.31 0.32 Test Error
Test Error
Test Error
Figure 1: Binary classification with binary sensitive attribute using logistic regression. Tradeoff of fairness
violation vs. test error for state-of-the-art fair classifiers on German Credit, Adult, and COMPAS datasets.
FERMI offers the best fairness vs. accuracy tradeoff curve in all experiments against all baselines. Rezaai et al.
2020) only allow for a single output and do not yield tradeoff' curve. Further, the algorithms by Mary al.
2019) and Baharlouei et al. (2020) are equivalent in this bimary setting and shown by the red curve. FERMI.
Mary et al. (2019) and [Baharlouei et al. 2020) try to empirically solve the same risk function Eq. (FRM obj However, the empirical formulation used by FERMI, Eq. (FFRM obj.) and its solver result in a hetter performance even-though
using full-batch for all baselines in this experiment.
227 In Fig. we report the fairness violation vs. test error, for three notions of fairness: demographic parity, equalized odds, and equal opportunity. We have only included in-processing methods, which outperform pre-processing and post-processing methods. Complete experimental results are included in the appendix. We measure fairness violation through conditional demographic parity Loe violation (Definition D. conditional equal opportunity Loo violation (Definition I0 and its generalization, conditional equalized odds violation. As can be seen, FERMI offers
228
229
230
231
232
tradeoff curve that dominates all existing state-of-the-a baselines in each experiment and with respect to each notion of fairness. This demonstrates the efficacy of having a strong regularizer such as ERMI: by enforcing small ERMI violation, our model simultaneously achieves small fairness violation with respect to these other notions which are upper bounded by ERMI.
233
234
235
237
It is noteworthy that the empirical objective function of Mary et al. (019) and Baharlouei al. 2020) is exactly the same in this setting, and their algorithms also coincide to the red curve in Additionally, like FERMI, they are trying to empirically solve Eq. (FRMI obj.). albeit using different estimation techniques, i.c., their empirical objective is different from Eq. (FERMI p. This demonstrates the effectiveness of our empirical formulation (EERI obj.) which is both unbiased and consistent whereas theirs is biased. It also shows the effectiveness of our solver (Algorithm
238
239
Fig.
240
241
242
243
D even -hough we are using all baselines in full batch mode in this experiment. In the following experiments, we will demonstrate that using smaller batch sizes results in much more pronounced advantages of FERMI over these baselines.
244
245
2 Exponential Rényi mutual information is equal to Rényi correlation for binary targets and/or binary sensitive attributes (see Theorem 2) which is the setting of all experiments in Sec. 5.1
7

---

Cwits.3300 3120e
0.500
0.303
Daharkual
0.367
0.303
20330
0.365
Cridal 11208
May
0.205
2014
May
2018
May 2012
0.350
1:350
250
5.315
0.240
0355
0.340
0.300
0.325
0300
0.0
11
0.330
13
15
0.333
33
15 17
11
17
0.355
Eo vilitioion... 0.07
0.373
5D vreittnn in 0.00
2.500
50 doaddon in 2:04
0.50
Eo sidittinnn 0.05
Jananuu 2008
Cauatal 2014
Gatarkul g.a. 2023
2019
Detoriall etat, 1020
0.20
Baneroue 2004
Chueta ZINE
0.355
IEMM
0.355
FENM
2.55
0.00
1MM
00355
6.355
6.305
345
0:300
0383
0.543
9:359
0350
0.300
No. of 977
Sant.
Figure 2: Comparison between FERMI, Mary ct al. (219)) Bahhalouci et al. 2020 and Cho al. (020b) on
Communities datasct. (aary et al. 2019) outperforms (Baharlouei al. 2020 Cho et al. 2020b). which we believe could be attributed to the effectiveness of ERMI as regularizer. FERMI outperforms Mary el all (019). which we attribute to our empirical formulation of ERMI and the effectiveness of its solver, given that we try to empirically solve the same risk function with different formulations.
248
5.2
Non-binary fair classification with a non-binary sensitive attribute
Next, we consider a non-binary classification problem with non-binary sensitive set. In this case, consider the Communities and Crime dataset, which has 18 binary sensitive attributes in total, and we pick subset of 1, 2, 3, 18 sensitive attributes out of those for our experiments, which corresponds
248
249
to |S] E {2, 4, 8, 218] j. We discretize the target into three classes [high, medium, low]. The only
250
251
baselines that we are aware of that can handle non-binary classification with non-binary sensitive
252
attributes are (Mary et al. 2019). (Baharlouci et al. 2020). (Cho et al. 2020b). (Cho et al., 2020a)).
253
and (Zhagg et al. 2018). We used the publicly available implementations of (Baharlouei al. (0200 and (Cho et al. 2020bb and extended their binary classification algorithms to the non- monnbbinary setting.
254
The results are presented in Fig. where use conditional demographic parity L violation (Definition D and conditional equal opportunity Lx violation (Definition TO) as the fairness violation notions for the two experiments. For all baselines, test error increases the number of sensitive attributes increases. As can be seen, compared to the baselines, FERMI offers the most favorable test error vs. fairness violation tradeoffs, particularly as the number of sensitive attributes increases and for the more stringent fairness violation levels, e.g., 0.02.
256
258
259
280
281
5.3
Domain generalization through FERMI
262
In our last experiment, our goal is to showcase the efficacy of FERMI in stochastic optimization with neural network approximation. For this experiment, we consider the Color MNIST dataset (Li & Vasconcelos| 2019). where all 60,000 training MNIST digits are colored with different colors drawn from class conditional Gaussian distribution with variance around certain average color for each digit, while the test set remains black and white. Li & Vasconcelos (209)) show that as a + 0, convolutional network model overfits significantly to each digit's color the training set, and achieves vanishing training accuracy. However, the learned representation does not generalize to the regular black and white test set, in absence of the spurious correlation between digits and color.
264
266
268
270 Conceptually, the goal of the classifier in this problem is to achieve high classification accuracy with predictions that are independent of the color of the digit. We view color as the sensitive attribute in this experiment, and apply fairness basclines for the demographic parity notion of fairness. One would expect that by promoting such independence through fairness regularizer generalization would improve (i.e. lower test error on the black and white test set), at the cost of increased training error (on the colored training set). We compare against Mary et al. 20199) Baharlouci et al. 2020)) and Cho et al. 2020bb as baselines in this experiment.
272
274
276
277
The results of this experiment are as illustrated in Fig. The details about the dataset and experimental setup is provided in Appendix E In the left panel, we see that with no regularization (A = 0); the test error is around 80%. As X increases, all methods achieve smaller test error while training error increases. We also observe that FERMI offers the best test error in this setup. the right panel, observe that decreasing the batch size results in significantly worse generalization for all three
278
280
8

---

0.8
0.9
Sehurias 2000
0.70
0.65
20205
2000
0.7
TERMI
0.60
Mary HEW. 2010
0.55
0.50
0.4
0.3
Thet Enor
0.45
0.2
0.40
0.1
0.35
0.30
1058
Figure 3: Domain generalization on Color MNIST Li & Vasconcelos 2019) using in-process fair algorithms for demographic parity. Left panel: The dashed line is the training error and the solid line is test error. As increases, fairness regularization results in a learned representation that is less dependent on color; hence training error increases while test error decreases (all algorithms reach plateau around À = 8). We use [B] = 512 for all baselines. Right panel: We plot test error batch size using optimized value of À for each algorithm selected via a validation set. The performance of all baselines drops 10-20% as batch size becomes small whereas FERMI is relatively insensitive to batch size.
baselines considered (due to their biased estimators for the regularizer). However, the impact is much less on FERMI. In particular, the performance gap between FERMI and other baselines is more than 20% for B = 64. Finally, FERMI with minibatch size B 64 still outperforms all other baselines with B > 1, 000. Finally, notice that the test error achieved by FERMI when o = 0 is ~ 30,, as compared to more than 50% obtained using REPAIR (Li & Vasconcelos 2019) for I 0.05.
283
284
285
286
Discussion & concluding remarks
287
288
In this paper, we studied three variants of a notion of fairness violation, called exponential Rényi mutual information (ERMI), developed for demographic parity, equalized odds, and equal opportunity notions of fairness. We showed that ERMI is a strong fairness violation divergence providing upper bound guarantees other popular violation divergences, namely Shannon mutual information, Rényi mutual information (Theorem distance violation (Theorem
289
290
292
D.. Pearson correlation, Rényi correlation (Theorem 2 and Ly
293
294
We derived an unbiased estimator for ERMI (Lemma based on which we formulated an empirical objective (FERMI obj.) for solving fair empirical risk minimization with ERMI regularization to balance performance and faimess. We provided a stochastic algorithm for solving FERMI IT) and proved its convergence (Theorem 5); for non-binary sensitive attributes, non-binary target variables, regardless of the batch size. From an experimental perspective, we showed that FERMI leads to better fairnsss-accuracy tradeoff's than all of the state-of-the-art baselines wide
296
(Algorithm(I)
298
289
300
variety of binary and non-binary classification tasks (for demographic parity, equalized odds, and equal opportunity). We also showed that these benefits are particularly sigmificant when the number of sensitive attributes grows or the batch size is small. In particular, we observed that FERMI consistently outperforms Mary al. 2019) (which tries to empirically solve the same objective Eq. (FRMI obj
301
302
303
304
by up to 20% when the batch size is small, suggesting that the unbiasedness of the FERMI estimator essential in achieving good empirical performance.
305
306
There are several possible explanations for the superior empirical performance of FERMI compared baselines. One possible reason is that the objective function Eq. (FEMI obj.) is easier optimize than the objectives of competing in-processing methods: ERMI is smooth; and in the discrete case, is
307
308
309
equal to the trace of matrix (see Theorem 7 appendix), which is easy compute. Contrast this with
310
the larger computational overhead of Rényi correlation used by |Baharlouei et al. (2020). 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 e
311
312
S as compared to Shannon mutual information which scales as ((( log (S) (Acharya et al. 2014 Moreover, the fact that ERMI is a stronger fairness violation seems to imply that FERMI would
313
314
315
generalize well to other fairness notions, hypothesis that is supported by our experimental results. Together, these facts suggest that ERMI serves as an efficient and easily optimizable proxy for these other fairness notions, making Eq. (FEMI obj.) good surrogate objective to optimize for all three notions of fairness considered (demographic parity, equalized odds, and equal opportunity). We leave
316
317
318
it future work to rigorously understand which of these (or other) factors are most responsible for
320
the favorable performance tradeoffs observed from FERMI.

---

References
321
322
Acharya, J., Orlitsky, A., Suresh, A. T., and Tyagi, H. The complexity of estimating Rényi entropy. 1rX1::1408.1000// 2014.
Aghaei, S., Azizi, M. J., and Vayanos, P. Learning optimal and fair decision trees for non- discriminative decision-making. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1418-1426, 2019.
325
327
Angwin, J., Larson, J., Mattu, S., and Kirchner, L. Machine bias. ProPublica, 2016.
328
Baharlouei, S., Nouiched, M., Beirami, A., and Razaviyayn, M. Rényi fair inference. In ICLR, 2020.
329
Bechavod, Y. and Ligett, K. Penalizing unfairness in binary classification. arXiv preprint (007:0777700044 2017.
330
Bechavod, Y., Ligett, K., Roth, A., Waggoner, B., and Wu, Z. S. Equal opportunity in online
332
classification with partial feedback. arXiv preprint arXiv: 1902.02200 2019.
333
Berk, R., Heidari, H., Jabbari, S.. Joseph, M., Kearns, M., Morgenstem. J., Neel, S., and Roth, A. A convex framework for fair regression. arXiv preprint arXiv:1706.02444 2017.
Bolukbasi, T., Chang, K.-W., Zou, J. Y., Saligrama, V., and Kalai, A. T. Man is computer programmer as woman is to homemaker? debiasing word embeddings. In Advances in neural information processing systems, pp. 4349 4357, 2016.
336
Calmon, F., Makhdoumi, A., Médard, M., Varia, M., Christiansen, M., and Duffy, K. R. Principal inertia components and applications. IEEE Transactions on Information Theory, 6318)5501,-5038, 2017a.
339
Calmon, F. Wei, D., Vinzamuri, B., Ramamurthy, K. N., and Varshney, K. R. Optimized pre- processing for discrimination prevention. In Advances in Neural Information Processing Systems, pp. 3992-4001, 2017b.
342
Cho, J., Hwang, G., and Suh, C. A fair classifier using mutual information. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2521-2526. IEFE, 2020a.
345
346
Cho, J., Hwang, G., and Suh, C. A fair classifier using kernel density estimation. Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, viriual, 2020b.
347
348
350
Chzhen, E. and Schreuder, N. A minimax framework for quantifying risk-fairness trade-off in regression. arXiv preprint arXiv:2007. 14265, 2020.
351
352
Cover. T. M. and Thomas, A. Information theory and statistics. Elements of Information Theory, 1 (1):279-335, 1991.
353
354
Csiszár, I. and Shields, P. C. Information theory and statistics: A tutorial. Now Publishers Inc, 2004.
355
Datta, A., Tschantz, M. C., and Datta, A. Automated experiments on ad privacy settings. Proceedings on privacy enhancing technologies, 2015(1):92-122, 2015.
Dembo, A. and Zeitouni, O. Large deviations techniques and applications. Springer Science & Business Media, 2009.
358
359
Donini, M., Oneto, L., Ben-David, S., Shawe-Taylor, J. S., and Pontil, M. Empirical risk minimization under faimess constraints. In Advances in Neural Information Processing Systems, pp. 2791-2801, 2018
361
362
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226, 2012.
Feldman, M., Friedler, S. A., Moeller, J., Scheidegger, C.,, and Venkatasubramannian, S. Certifying and removing disparate impact. proceedings of the 2 ACM SIGKDD international conference on knowledge discovery and data mining, pp. 259-2658 268, 2015.
365
10

---

Fish, B., Kum, J., and Lelkes, A. D. A confidence- based approach for balancing faimesss and accuracy. In Proceedings of the 2016 SIAM International Conference on Data Mining, pp. 144-152. SIAM, 2016.
367
368
Gebelein, H. Das statistische problem der korrelation als variations-une und eigenwertproblem und sein zusammenhang mit der ausgleichsrechhung, ZAMM-Journe of Applied Mathematics and Mechanics/Zeitschrrfff für Angewandte Mathematik und Mechanik, 21(6)364-3733 1941.
371
373
Grari, V., Ruf, B., Lamprier, S., and Detyniecki, M. Fairnes--aware neural Réyni minimization for continuous features, arXiv preprint arXiv:1911.0492,, 2019.
374
Grari, V., Hajouji, O. E., Lamprier, S., and Detyniecki, M. Learning unbiased representations via Rényi minimization. arXiv preprint arXiv:2009.03188, 2020.
376
377
Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. Advances in neural information processing systems, pp. 3315-3325 2016.
379
Hirschfeld, H. O. A connection between correlation and contingency. In Proceedings of the Cambridge Philosophical Society, volume 31, 520-524, 1935.
Jiang, R., Pacchiano, A., Stepleton, T., Jiang, H., and Chiappa. S. Wasserstein fair classification. In Uncertainty in Artificial Intelligence, pp. 662-872. PMLR, 2020.
382
385
Kamiran, F., Calders, T., and Pechenizkiy, M. Discrimination aware decision tree learning. In 2010 IEEE International Conference on Data Mining, pp. 869-874. IEBE, 2010.
384
385
Kamishima, T., Akaho, S., and Sakuma, aware learning through regularization approach.
In 2011 IEEE 1 11th International Conference Data Mining Workshops, pp. 643-650. IEEE, 2011.
387
388
Kearns, M., Neel, S., Roth, A., and Wu, S. Preventing fairnsss gerrymandering: Auditing and learning for subgroup fairness. In International Conference Machine Learning, pp. 2564-25522 2018.
390
381
Kilbertus, N., Rodriguez, M. G., Schölkopf, B., Muandet, K., and Valera, I. Fair decisions despite imperfect predictions. In Chiappa, S. and Calandra, R. (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 277 277-287, PMLR, 26-28 Aug 2020.
382
393
394
395
Lecun, Y., Bottou, L., Bengio, Y., and Haffner, Gradient- based learning applied to document
recognition. Proceedings of the IEEE, (6(11):2278-22) 1998. doi: 10. 10.1109/5.726991.
397
Li, Y. and Vasconcelos, N. Repair: Removing representation bias by dataset resampling. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9572-9581, 2019.
398
399
400
Lin, T., Jin, C., and Jordan, M. On gradient descent ascent for nonconvex-coneave minimax problems. arXiv: 1906.000 0003vv0 2020.
402
Luo, L.,, Ye, H., and Zhang. T. Stochastic recursive gradient descent ascent for stochastic nonconvex- strongly-concave minimax problems. arXiv: 2001.03724, 2020.
403
404
Mary, J., Calauzenes, C., and El Karoui, N. Fairness-aware learning for continuous attributes and
405
treatments. In International Conference on Machine Learning, pp. 4382 4391. PMLR, 2019.
406
Kérez-Suay, A., Laparra, V., Mateo-García, G., Muñoz-Mari, J., Köômez-Chova L., and Camps- Valls, G. Fair kernel learning. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 339-355. Springer, 2017.
408
409
Pleiss, G., Raghavan, M., Wu, F., Kleinberg, J., and Weinberger, K. Q. On faimess and calibration. In Advances Neural Information Processing Systems, pp. 5680-5689, 2017.
410
411
Raff, F.,, Sylvester, J., and Mills, S. Fair forests: Regularized tree induction to minimize model bias. In Proceedings of the 2018 AAAI/ACM Conference on Al, Ethics, and Society, pp. 243-250, 2018.
11

---

Rényi, A. On measures of dependence. Acta Mathematica Academiae Scientiarum Hungarica, 10 (3-4):41-451, 1959.
414
415
Rényi, A. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium Mathematical Statistics and Probability, Volume I: Contributions to the Theory of Statistics. The Regents of the University of California, 1961.
417
418
Rezaei, A., Fathony, R., Memarrast, O., and Ziebart, B. D. Fairness for robust log loss classification. In AAAI, pp. 5511-5518 2020.
420
Steinberg, D., Reid, A., O'Callaghan, S., Lattimore, F., McCalman, L., and Cactano, T. Fast fair
421
regression via efficient approximations of mutual information. arXiv preprint w002ix:2002062000 2020.
422
423
Sweeney, Discrimination online ad delivery. arXiv preprini arXiv:1301.688 2013.
424
Taskesen, B., Nguyen, V. A., Kuhn, D., and Blanchet, A distributionally robust approach to fair
classification. arXiv preprint arXiv:2007.09530, 2020.
Williamson, R. and Menon, A. Fairness risk measures. In International Conference Machine
427
Learning, pp. 6786-6797 6797. PMLR, 2019.
428
Witsenhausen, H. S. On sequences of pairs of dependent random variables. SIAM Journal on Applied
429
Mathematics, 28(1):100-113, 1975.
430
Woodworth, B., Gunasekar, S., Ohannessian, M. I., and Srebro, N. Learning non-discriminatory
predictors. arXiv preprint arXiv: 170.00601, 2017.
Zafar, M. B., Valera, I., Rogriguez, M. G., and Gummadi, K. P. Faimess constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pp. 962-970. PMLR, 2017.
435
434
Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. Learning fair representations. In International Conference Machine Learning, pp. 225--33,,1 2013.
436
Zhang, B. H., Lemoine, B., and Mitchell, M. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp. 335-340, 2018.
437
12

---

Checklist
438
439
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
441
contributions and scope? [Yes]
442
(b) Did you descrihe the limitations of your work? [Yes]
443
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
445
446
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
448
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes]
451
452
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
453
454
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
455
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [No]
457
458
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
459
(a) If your work uses existing assets, did you cite the creators? [Yes]
460
(b) Did you mention the license of the assets? [N/A]
481
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
462
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No]
463
464
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
465
466
5. If you used crowdsourcing or conducted research with human subjects...
487
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
469
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
470
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
472
13


Reviews:
[{"review_id": "z00Ok6YKM-c", "reviewer": "Reviewer_JwMW", "summary": "This paper looks to extends existing work on fairness-arawe learning with continuous attributes/labels by improving estimation of (ideal) regularizer. It proposes an unbiased estimator of a regularizer based on $\\\\chi^2$ divergence using a variational formulation. It then proposes a set of experiments to illustrate the performance of the method.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Core idea**\n* Overall, I like the core idea of using a variational approach to obtain an unbiased estimator of the $\\\\chi^2$ divergence used in previous works (previous estimators not being unbiased).\n* I think the paper could focus more on this aspect, in particular, showing how its estimator converges towards the $\\\\chi^2$ divergence, versus the previously proposed ones (ex: Mary 2019). And this, independently of its use as a fairness regulariser.\n\n**Exposition and positioning**\n* I found the paper tends to oversell its results and would generally be improved by a better and more fair discussion of its limitation and comparaison to SOTA. Few examples of imprecise/misleading things:\n  * I don't see the need to define a new notion (ERMI), to then explain it is already existing: the $\\\\chi^2$ divergence between the joint distribution and the kronecker product of marginals.\n  * The *non-binary* label/attribute positioning should be more precise, as it means \"discrete\" rather than \"continuous\". Indeed, as main SOTA compared in the experiments are designed for continuous label/attributes (Mary 2019, Cho 2020...), this imprecise naming is *misleading*. I was believing the paper treats about the continuous case until Th. 4 (end of page 5).\n  * This is even more confusing when the comment after Lemma 1 compares the resulting estimator (for discrete variables) to the bias introduced by *continuous* density estimation methods introduced in (Mary 2019, Baharlouei 2020).\n  * Many methods designed for binary variables have strait-forward extensions to discrete variables.\n* Thm 1,2,3 show that the $\\\\chi^2$ divergence upper-bounds some other existing coefficients that characterize independence.\n  * Some are coming from the literature, or are strait-forward.\n  * I find the statements \"ERMI is stronger than MI/HGR\" imprecise. It is unclear what \"stronger\" means. It is an upper-bound, yes. But MI or HGR also characterize completely independence. So I don't see in what sense it is \"stronger\".\n  * I'm not sure these 3 results bring anything to the paper, as the main contribution is not the use of the $\\\\chi^2$ divergence but rather the variational form to build an unbiased estimator.\n* In Table 1: even \"while satisfying eod guarantees satisfying eop [...] we only credit those works that provide/implement algorithms for a given fairness notion\" -> That mis-characterizes previous work.\n\n**Experimentation**\n* Experiments seems OK overall.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review", "review_text": "", "extra_scores": {"ethical_concerns": "Not that I can think of.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "mWsLuNrR19l", "reviewer": "Reviewer_VsBW", "summary": "This paper proposes a new characterization of the exponentiated (second-order) Rényi mutual information (ERMI). It then uses an empirical version of this idealized characterization as a fairness regularizer. (Many notions of fairness can be written as conditional independence statements, whose approximation can be expressed using mutual information.) The benefit of the new characterization is that the overall optimization can be written as a min-max optimization where the objective function is sum-decomposable. This allows using stochastic gradient descent-ascent to converge to a stationary point. Experimental evidence is given that shows the new approach achieves better fairness-accuracy tradeoff, even compared to prior methods using a different empirical version of ERMI as a fairness regularizer.", "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": "### Strengths:\n\n+ The characterization of ERMI in a variational form (Theorem 4, maximizer of a quadratic expression) is interesting and could be useful in other situations too. _(originality)_\n\n+ The experimental results seem quite strong, showing clearly that there is merit in this approach. _(significance)_\n\n### Weaknesses:\n\n- There are a couple of issues with the claims. First, Lemma 1 as stated is not correct. It claims that the proposed ERMI estimator (the empirical version of the variational characterization) is unbiased. This is stated without proof, as an immediate consequence of the characterization itself (Theorem 4), perhaps due to the linear expression within the maximizer (if $P_s$ is indeed assumed known.)  While unbiasedness holds without the max, it’s not obvious at all why it would with the max, and very likely doesn’t. Considering this is one of the repeated selling points, it requires an explanation from the authors. _(quality)_\n\n- Second, assuming $P_s$  known or easily learnable from the data sounds reasonable, but considering how much the convergence results hinge on the gradient being unbiased, I’m not sure it can be swept under the carpet that easily. This is particularly important because it’s the _inverse_ of $P_s$ that shows up. The problem can be particularly pronounced when there are many sensitive attributes, some of them observed rarely in the data, and inaccuracy near zero can create a large bias and variance in the inverse of the estimated $P_s$. Considering the paper makes claims of unequivocal convergence to distinguish itself from alternatives, this also needs addressing. _(quality)_\n\n- The presentation is often unnecessarily repetitive, with the effect of selling the paper’s results rather than clearly presenting its contributions. _(clarity)_\n\n- Most of the comparison results between Renyi mutual information and other measures of independence are previously known (Theorems 1 through 3). _(originality)_\n\n### Suggestions:\n\n* In the proof of Theorem 4, `line 607` and `line 608` (second equation) the expression for $W^*$ has swapped matrices. In the end everything works out, so it just needs a clean-up. Also at the end of the proof, you get $D_R + 1$.\n\n* In Lemma 1, once clarified, `line 198` needs also a $\\frac{1}{N}$ factor.\n\n* Typos: `line 113` product, `line 119` equalized.\n\n[Edit: Thank you authors for the active discussions. Lemma 1 is now correct, although it's not a lemma but rather a corollary to Theorem 4. The flow makes sense, in that if SGDA targets the min-max expected objective, it's true that the max expected-objective is FRMI, and your samples give you access to unbiased gradients of the min-max expected objective. You need to change references to unbiasedness throughout the paper to make sure this change is properly reflected. The strong experimental results that you have show merit, but  I believe a reworking of the theoretical insight with clarity and modesty will make a better case for the paper. I will leave my evaluation unchanged.]", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal impact has been discussed through the topic of fairness itself.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "S60E6Xb21V5", "reviewer": "Reviewer_GUFw", "summary": "The authors examine the demographic parity, equalized odds, and equality of opportunity fairness constraints, and show that the Exponential Rényi Mutual Information of various random variables related to these quantities is a unifying continuous relaxation of these concepts.  Moreover they show that the FERMI upper bounds Shannon Mutual information, Rényi correlation, and Lq fairness violations. Finally, they claim an unbiased estimator for the FERMI, which seems to be the main advantage of FERMI over (non-exponential) Rényi Mutual information, and with it derive a stochastic gradient descent based algorithm for fair machine learning. Finally they close with experiments showing that FERMI controls fairness with similar effectiveness to prior results.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is not the first paper to use FERMI in a fairness context, however here we see more technical rigor, and there are certainly new ideas.\nI take issue with a technical points regarding unbiasedness that I would like to see addressed.\nI also find the sample complexity discussion quite limited and unsatisfying.\nI also have concerns over whether ERMI is chosen for its computational convenience, or its inherent value as a fairness concept. This is not an issue of correctness, but rather a criticism of how significant or relevant this concept really is.\nOverall, the paper is good, but unless my concerns can be addressed, I do not think it meets the high bar of a NeurIPS publication.\n\nUnbiasedness:\n\nThe discussion around theorem 4 and lemma one I find unsatisfying.  The $P_s$ matrix of course can be estimated unbiasedly from a sample, but this does not necessarily lead to an unbiased estimator.\nThis is rather like claiming one can derive an unbiased estimator for the variance of sums of dependent random variables. Given the expectation, this is rather straightforward, but without it, even though an unbiased expectation estimator is easily derived, it does not translate into an unbiased variance estimator!\nAt best, it yields an unbiased estimator for the ERMI with respect to the empirical measure of the sample, rather than the underlying distribution over samples.\nThis is important for the correctness of their stochastic gradient descent model, but does not have the same importance to the analysis of the overfitting of the model, specifically w.r.t. overfitting to fairness.\n\nFurthermore, no proof of lemma 1 is given, and I am skeptical about any kind of unbiased estimator using a max over matrices $W$ (this seems to be a convex nonlinear operator).  This is not impossible (e.g., the Rademacher average or weak variance), but it is not inevitable (e.g. the wimpy variance) for estimators involving suprema to be unbiased.  I would like to see further substantiation of this claim.\n\nI don't have a problem claiming that we have a convergent or consistent estimator for ERMI, but I want to see all sources of bias and estimation error fully analyzed.\n\n\n\nSample complexity:\n\nI disagree with the statement on 311: “Furthermore, the sample complexity of estimating Rényi mutual information of order 2 (and consequently that of ERMI) scales as Θ( |S|).”  Composition of unbounded functions with the exponential operator does not preserve any definition of sample complexity of which I am aware, and if the range of RMI is |S|, I would conjecture an increase to roughly Θ( |S| exp(|S|) ) to estimate ERMI (or would appreciate an argument as to why this is not the case).  Furthermore, this is all for a single function, and presumably uniform convergence and related techniques would be required to bound ERMI over an entire family. \n\n\nChoice of ERMI:\n\nI find the specific use of ERMI a bit unsatisfying and unmotivated. My inference is that it was selected as it leads to a simple unbiased estimator, which was convenient for the SGD algorithm, rather than for its fundamental fairness properties. The claim “We show that ERMI is a stronger notion of fairness violation than... existing notions” is valid, but not necessarily a positive; one could equally well claim it is a loose bound on existing fairness concepts.\nWhile the authors do relate ERMI to various quantities of interest, the relations are not as sharp as one may desire.\n\nIn particular:\nFrom a (pseudo)dimensional analysis (technically it’s all unitless) perspective, I do not find theorems 1, 2, or 3 particularly surprising or interesting. The exponential in the exponential Rényi information Mutual information is very powerful, and it is unsurprising that it allows one to bound the remaining (essentially logarithmic) information quantities.\nI suppose the results might be interesting when we consider a small range of possible $\\hat{Y}$ and $S$, in which case the exponential can't do too much, but in general I would be much more interested in seeing what can be done with (non-exponential) Rényi mutual informations. Theorem one essentially does this, but similar hold for any RMI, theorem 2, I have little insight on but I would be interested in further exploring the idea behind the $|S| = 2$ special case, and theorem 3 in particular seems like there should be some connection between the $q$ and $\\alpha$ parameters, or at least a family of similar results for arbitrary $\\alpha$, where the square root is a consequence of the $\\alpha=2$ choice in ERMI.\n\n\nSpecifics:\n\n\n\nIn table 1, you make a point that controlling EOD is stronger than EOP, which may harm accuracy.  I agree with this point, however can it not be applied to FERMI in general, as compared to the “less strong” fairness violation metrics you discuss?\n\nLine 39 is a bit of a non-sequitur: measuring degree is important in and of itself, and these estimates are subject to statistical error as well. For hard properties, null hypothesis testing is perfectly valid way of relating samples to distributions, just as tail bounds and sample complexity analyze the statistics of soft properties.\nIn fact, I would argue that null hypothesis testing arose to answer questions like whether a particular binary property holds on a distribution given a sample. Developing continuous properties analogues of such discrete properties is of orthogonal interest.\n\n71: This is not necessarily a good thing; again EOD, is “stronger than” EOP.\n\n76 Convergence in samples or convergence in computation? I believe the latter but the writing is unclear.\n\n82: Does large-scale mean large training set? If so what does that have to do with minibatch size?  If you mean the size of individual instances, perhaps, but in the practical world, are we not generally memory-constrained by the size of the model?\n\nLine 115 “for brevity” sentence is unclear.\n\n\n\nThm. 1: Stronger is one way to put it, but one could also refer to it as looser. Is there an argument that one should be more interested in the Rényi information itself rather than the Shannon information?\n\n\nLine 164 remark: I disagree with this conclusion. While it is true that bounding ERMI is sufficient when possible, it may not always be possible to control the ERMI without huge sacrifices to accuracy. I would either need to be convinced that the gap between ERMI and other fairness concepts is small, or that in situations where other fairness concepts are small but ERMI  is large, the model is, in some sense not captured by alternative fairness concepts, deeply unfair.\n\n\n171: Why call it FRMI rather than FERMI?\n\n\n*Score raised from 4 to 6 based on author response.*\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I express concerns as to the looseness of the relationship between fairness violation concepts, and the resulting impact on model quality (and difficulty of satisfying fairness constraints) in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "13"}, "extra_text": {}}, {"review_id": "7p5VKgMsjnA", "reviewer": "Reviewer_4DYT", "summary": "The paper explores fair empirical risk minimization through ERMI regularization. In particular, the paper provides an approach a stochastic algorithm to minimize the regularized objective with convergence guarantees.\n\nMain Contributions:\n - Thm. 1-3: Shows that ERMI fairness violation upper bounds Shannon information, Pearson correlation, and $ L_{\\infty} $ fairness violation definitions.\n - Thm. 4: Gives an unbiased estimator of ERMI regularization term.\n - Alg 1. + Thm 5.: Method of minimization which converges.\n - A number of experimental test verifying the theoretical results.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the provides a good exploration of fair empirical risk minimization through ERMI regulation. The clarity and structure of the paper is very good, with the progression through theoretical results and then the experiments following logically.\n\nOriginality & Significance: The work seems to be significant, with Algo. 1 providing convergence guarantees on for fair empirical risk minimization. Furthermore, the results are experimentally compared to a large number of baselines and performs better despite Thm. 1-3 only giving (possibly loose) upper bounds.\n\nQuality & Clarity: The structure and clarity of the paper is very good. Both the theoretical and experimental results seem to be sound.\n\nStrengths:\n - Thm 1-3 motivate (FRMI obj.) nicely.\n - Alg 1. and its guarantee seems significant.\n - The experimental verification seems extensive. \n\nWeaknesses/Suggestions/Questions:\n - Line 113: \"proudct\" -> \"product\"\n - Experiments (including SI) don't seem to include details of the machine used to run the experiments.\n - Furthermore, a rough runtime comparison between baselines and Alg 1. would be useful to add.\n - I think an informal disclaimer for the differentiability, smoothness, and Lipschitz assumption on $ \\ell $ should be added to Thm 5.\n\nEdit:\nAfter quite a bit of reviewer discussion, I have come to the conclusion of lowering my score regarding the paper. The following are my main reasons:\n\n  - I believe that I have overestimated the novelty of Thm 1-3 after some discussions with other reviewers. In particular, Thm 1 is only a minor change from well known results (Sason and Verdu, Eq. (94)) and Thm 3 is Pinsker's inequality with Thm 1. Although having these results being completely novel is not necessary for this paper, these results need additional clarification and reframing with respect to their novelty.\n\n  - I missed the missing assumption / known distribution needed for the unbiased estimator, which is a major technical limitation of the work. I would argue that this assumption is not negligible. Although the authors have mentioned in other rebuttals that $ P_{s} $ \"[...] in a certain population is usually public knowledge\", I find that this is a rather troubling normative assumption to hold given the nature of sensitive attributes. I do believe that there is an improvement from assuming the joint distribution. However, with this, a detailed discussion of the implication of the assumption (+ its improvement from prior work) is warranted.\n\n - In addition to the clarification of assumption and the additional comments picked up by other reviewers (e.g., precision of large-scale models), I believe there is a non-trivial amount of restructuring which would be required to clarify the above points regarding related work and contributions.\n\nOverall, I would like to note that I am still positive (high 6) about the paper with its unbiased estimator and strong experimental result despite the flaws listed above.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitation and societal impact adequately addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers like the variational approach in order to obtain an unbiased estimator for ERMI, and (modulo concerns about the assumption that $P_s$ is known), the revised Lemma 1 does fix the issue with unbiasedness that was highlighted in some of the review. Also, there is agreement that the experimental results are impressive. So, from the method and experiments side, this could make for a very strong paper. However, very unfortunately, there are some significant weaknesses when it comes to a key assumption (which is related to a key selling point of the paper), some of the results not being original as a few reviewers had originally thought, and also some important issues with the current presentation. I stress that this paper can be a strong paper, and it was very close to being accepted, but ultimately the concerns are numerous enough to warrant the review of a new, restructured/revised version of the paper prior to the paper being accepted at NeurIPS. The remainder of this review focuses on the various issues that came out in the reviews and the ensuing discussion.

First — and this was not the most major factor in the decision on this paper — it seems that Theorems 1 and 3 are not novel (I acknowledge that the authors did cite Theorem 2 from Mary et al.). In the discussion phase, some reviewers gave pointers to where these results can be essentially found. For pointers for Theorems 1 and 3, please see the review of 4DYT. For Theorem 2, one reviewer mentioned that it "is already stated in Mary et al. (2019) and derives from Witsenhausen's characterization of Renyi correlation." They also mentioned that the part of the theorem stating that Renyi's coefficient upper bounds Pearson is imprecise, because Pearson's definition does not hold when $S$ is multi-dimensional (which is the case of interest here), and in 1 dimension, the inequality is by definition of Renyi's coefficient. Overall, the lack of novelty of Theorems 1 through 3 is not a severe weakness, but in light of what was already known, some changes to the presentation are in order.

One of the major criticisms is the assumption that $P_s$ is known; there was consensus among the reviewers that this is an important limitation. I especially see this as problematic since (as mentioned by Reviewer 4DYT) this can be a troubling normative assumption and (as Reviewer VsBW mentions) the inverse of $P_s$ is what we need to deal with, and so one needs to be very careful with estimation errors for $P_s$. Still, as the authors mention, previous important related works assumed the joint, and so the authors do operate under weaker assumptions. At a minimum, a detailed discussion regarding assumptions is in order. With so much of this work focusing on unbiasedness and convergence, the assumption of what is known (rather than estimated) deserves higher scrutiny and needs serious discussion in the main text of the paper.

The last point I discuss is a significant issue (whether or not the authors realize it), but I stress that this issue was not in isolation the reason for the paper not being accepted. The issue is best summarized by the following line from Reviewer VsBW (also essentially conveyed by Reviewer JwMW): "The presentation is often unnecessarily repetitive, with the effect of selling the paper’s results rather than clearly presenting its contributions." From my detailed read, there is significant repetitiveness and also some overselling is very apparent to me. Given that two reviewers and I independently came to this conclusion, I really do think this is an important issue. I urge the authors to solicit feedback from their peers if the authors are unable to see what parts of their paper are repetitive and to also consider reducing the overselling; this is an exercise that overall will benefit the authors by improving their scientific writing in the future and also which will allow them more space to present their contributions. One reviewer lamented that there was not much precision in what is being estimated, and there also was a lack of precision when discussing sample complexity in the paper. Having more space will allow you to properly discuss these important points.

I will now provide some guidance here about the repetition that I found and the overselling I found (again, in isolation the below is not the reason for the paper not being accepted, and also, it is not the major reason either, but it is also not a minor one).

Regarding overselling: The authors often mention that ERMI is stronger than other fairness measures (see Theorems 1 through 3). However, stronger here just means that if ERMI is small, the other measures are small. Basically, ERMI can be viewed as a looser upper bound. Saying "stronger" in many places, as the authors do, give the connotation that ERMI is better, while a more scientific presentation would mention how it's simply looser (yet, the authors can highlight the benefit of ERMI in their experiments, so all is not lost).

Regarding repetitiveness: In three different places, the authors mention that Mary et al. (2019) has an estimator that is biased, and they repeatedly mention that theirs is unbiased. Also, they mention exactly once that the estimator of Mary et al. is biased but consistent (which, of course, means asymptotically unbiased). The scholarly way to say this would be that the method of Mary et al. is asymptotically unbiased (not saying it this way is, to me, mild overselling, so this should also be included in the "overselling" paragraph above). They also mention 4 times in the paper, even before the experiments section, that their methods outperform those of Mary et al. (2019). This amount of repetition seems less than scholarly.
    
In conclusion, this paper definitely has strong merit, but it needs a serious rewriting/restructuring though in order to appear at venue of the caliber of NeurIPS. As one reviewer stated, "The strong experimental results that you have show merit, but I believe a reworking of the theoretical insight with clarity and modesty will make a better case for the paper". 
Decision: Reject