Group-Aware Threshold Adaptation for Fair Classification
Authors: Taeuk Jang
Pengyi Shi
Xiaoqian Wang
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Fairness
Post-Processing Method
Fairness-Accuracy Trade-Off

Abstract: The fairness in machine learning is getting increasing attention, as its applications in different fields continue to expand and diversify. To mitigate the discriminated model behaviors between different demographic groups, we introduce a novel post-processing method to optimize over multiple fairness constraints through group-aware threshold adaptation. We propose to learn adaptive classification thresholds for each demographic group by optimizing the confusion matrix estimated from the probability distribution of a classification model output. As we only need an estimated probability distribution of model output instead of the classification model structure, our post-processing model can be applied to a wide range of classification models and improve fairness in a model-agnostic manner to ensure privacy. This even allows us to post-process existing fairness methods to further improve the trade-off between accuracy and fairness. Moreover, our model is efficient with low computational cost by alternating optimization and flexible with the optimization over multiple fairness constraints. We provide Pareto frontier to characterize fairness-accuracy trade-off. Also, we provide a theoretical analysis of the optimal thresholds obtained from our model in terms of both accuracy and fairness in classification. Experimental results demonstrate that our method outperforms state-of-the-art methods and obtains the result that is closest to the theoretical accuracy-fairness trade-off boundary.

Group-Aware Threshold Adaptation for Fair Classification
Anonymous Author(s) Affiliation Address ema i
Abstract
The fairness in machine learning is getting increasing attention, as its applications in different fields continue expand and diversify. To mitigate the discriminated model behaviors between different demographic groups, we introduce novel post- processing method to optimize over multiple fairness constraints through group- aware threshold adaptation. We propose to learn adaptive classification thresholds for each demographic group by optimizing the confusion matrix estimated from the probability distribution of classification model output. As only need an estimated probability distribution model output instead of the classification model structure, our processcnssing model be applied to wide range of classification models and improve fairness in a model-agnostic manner to ensure privacy. This even allows to post-process existing fairness methods to further improve the trade-off between accuracy and fairness. Moreover, our model is efficient with low computational cost by alternating optimization and flexible with the optimization over multiple fairness constraints. We provide Pareto frontier to characterize fairness-accuracy trade-off. Also, provide theoretical analysis of the optimal thresholds obtained from our model in terms of both accuracy and fairness in classification. Experimental results demonstrate that our method outperforms state-of-the-ar methods and obtains the result that is closest to the theoretical accuracy-faimess, trade-off boundary.
2
10
12
14
18
17
18
19
Introduction
20
21
Machine learning is broadening its impact in various fields including autonomous driving, credit analysis, and job application screening. a consequence, the role and importance of fairness in machine learning are emerging. However, recent models have been found to behave differently between demographic groups favorable predictions. For example, it has been discovered that COMPAS, the criminal risk assessment software currently used to help pretrial release decisions, has biases between different races 4 Specifically, blacks got higher risk scores predicted from the model than whites with similar profiles. Therefore, discrimination truly exists and resolving it in machine learning is very important and urgent because direct and potential impact growing tremendously.
22
23
24
25
26
27
28
30 However, obtaining fairness is not trivial problem, because the data set itself will be biased when
31 is accumulated artificially. Simply removing or manipulating sensitive features (such race, gender)
32 from the data does not solve the bias. because there is indirect discrimination [19 or disparate
33 treatment [1] due to the feature redundancy and relevance, which means sensitive information can be
34 inferred from other features.
35 In order to alleviate discrimination from different perspectives, various quantitative measurements 13) have been proposed. has been proven that the pursuit of fairness is
38 of group equity 7
Submitted to Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

37 subject to trade-off between faimess and accuracy [14 10, i.e., if we want to improve fairesss, we need sacrifice accuracy.
38
39
Moreover, Pleiss et al. [20] studied the trade-offs between fairness notions that cannot be satisfied the same time. Therefore, recent works usually target certain fairness notion in different approaches such as pre-processing [6], in-processing [24], and post-processing 77] methods. However, these approaches suffer from the lack of flexibility, since it is difficult to adapt a fair model that is trained w.r.t. one certain fairness criterion so as to optimize over other fairness measures. If the fairness constraints change under some circumstances, traditional fairness models need to be re- re-trained from scratch, which is computationally demanding and sometimes inapplicable due to model settings. To overcome the limitations above, we propose novel post- post-processing method to improve faimess in a model-agnostic manner. Our GSTAR (Group Specific Threshold Adaptation for faiR classification) model learns adaptive classification thresholds for each demographic group
40
41
42
43
44
45
46
47
48
49 in classification task for improving the trade-off between fairness and accuracy. Given an existing classification model, GSTAR approximates the probability distribution of the model output via maximum likelihood estimation and utilizes confusion matrix to quantify accuracy and fairness w.r.t. the group-aware classification thresholds. This allows us to: 1) prevent from burdening additional complexity or deteriorate the stability of the training process of the classifier; 2) integrate different faimness notions into one unified objective function; 3) easily adapt one pre-trained model to other fairesss constraints. We summarize our contributions of this paper as follows:
50
51
52
53
54
56
1.
We propose novel post-processing method, GSTAR, which can learn group-aware thresh- olds to optimize the trade-off between fairness and accuracy in classification. We derive rigorous theoretical analysis on the trade-off in our model, and empirically show that GSTAR outperforms state-of-theaar methods.
57
58
59
60
2. With GSTAR, we can simultaneously optimize over multiple fairess constraints with low computational cost. GSTAR does not require multiple iterations over data, instead, it takes at most one pass of data in training for fast computation.
61
62
63
3. GSTAR can be adapted to wide range of classification models in model-agnostic manner and can adapt an existing classification model from one fairness criterion to another without re- re-training the classifier.
64
65
66
4. We derive Pareto frontiers of our model for the fairness-accuracy trade-offs that contextualize the quality of fair classification.
67
68 2
Related Works
69 In order to achieve group fairness, which quantifies the discrimination among different sensitive groups, diverse notion of fairness has been introduced. Equalized odds (7] enforce equality of true
70
71 positive rates and false positive rates between different demographic groups Pleiss et al. [20] relaxed
72 cqualized odds to satisfy the calibration. Demographic parity or disparate impact [1] suggests that a model is unbiased if the model prediction is independent of the protected attribute.
73
Among different fairness methods, post-processing techniques propose to improve fairness by mod- ifying the output of a black-box classifier. Hardt et al. [7] propose to ensure equalized odds by constraining the model output. Kamiran et al. [9] propose to give favorable outcome unprivileged and an unfavorable outcome to the privileged group when the confidence of the prediction is beyond a certain range. However, such static confidence window keeps the same regardless of the demographic group and is determined by grid search, so it is less efficient.
75
77
78
79
80
Threshold adjustment (a.k.a. thresholding) was introduced to improve the performance of static thresholds. In the literature, Menon et al. [8] prove that instance-dependent thresholding of the predictive probability function is the optimal classifier in cost-sensitive fairness measures. Also, when considering immediate utility, Corbett-Davie from group-spe -souu-speccfic threshold which is determined by group statistics. However, to the best of our knowledge, the threshold adjustment approach has not been deeply studied that neither encompasses 85
81
83
et al. [ show that optimal algorithm is achieved
84
86 broad group fairness metrics nor describes an explicit method to achieve the threshold.
87
Trade-off between fairness and accuracy exists when we impose fairness constraint to model. Recent studies 2 25 prove that models targeting at such fairness notions conform to an information theoretic

---

89
lower bound on the joint error across different sensitive groups. Therefore, our work presents a practical upper bound of the best achievable aceuracy given the fairness constraints.
90
91
Moreover, trade-offs between different fairness notions also exist if one has to consider multiple
92
fairness criteria. Some of them are theoretically proven to be incompatible 66 18 14]. To express and formulate fairness, recent work (10) utilize confusion matrix and propose least-square accuracy- fairness optimization problem on multiple fairness notions, and categorize the trade-off's between the fairness notions.
93
94
95
Here, our work is the most related to the post-processing methods 7 10] Hardt et al. 7 propose a post-pree post-processing method that utilizes the mixing rate to meet the equalized odds. Ours is similar to Hardt et al. 77] in the manner that achieving group-wise threshold from the feasible region that is geometrically generated by the intersection between the receiver operating characteristic (ROC) curves conditioned on sensitive feature. Ours differ from 7 by generalizing the concept beyond equalized odds to other multiple fairness constraints into consideration. FACT [00] utilizes a single point (static) from the classifier be post-processed as a reference which does not fully utilize the classifier for the post-processing. In contrast, by approximating the distribution of the continuous predicted logits, our GSTAR model enables larger feasible region than [0) with a better fairness- accuracy trade-off. We validate the improvement in trade-off via both theoretical and empical results. is notable that these related methods 7 10 can be considered as a special case of GSTAR.
97
89
100
101
102
103
104
105
106
3
GSTAR for Fair Classification
107
108
3.1
Motivation
109
Consider binary classification problem with a binary sensitive feature, such that the sensitive feature A E (0, 1} and label Y E {0, 1]. In general, for a given data X, a binary classification model outputs an unnormalized logit h(X) E IR with the class label probability p p(X)= ar (b())) E [0, 1), where a is an activation function (sigmoid function in logistic regression and neural network). is not necessary to calculate in a classification model, e.g. support vector machines directly use the positiveness/neeattveeee of logit (XX) to determine classification outcome. For traditional models, we use cut-off threshold 0₁2 0 for h(X) (i.e., 0p (0) = 0.5 for p(X)) in classification, such that the predicted label is determined by Y I(h(X) 2 02.. In the following context, unless otherwise mentioned, we use 0 to refer to the threshold 6) on logit h since it is applicable to a wider range of classification models, and the corresponding threshold on label probability Op can be easily inferred from the threshold on logit h. Traditional models use the same cut-off threshold @ for different demographic groups. However, since the distribution of logits in different demographic groups can be different, using the same threshold @ brings biased classification.
110
112
113
114
116
117
118
119
120
122
In Figure 1. we show real-world example of image classification on CelebA dataset with ResNet50 g to show that the default setting of classification thresholds affects both accuracy and fairness in classification. The goal of this classification example to predict the image of a person is whether attractive or not, and consider sensitive attribute as gender. This can be generalized to different sensitive attributes such as age or race [22] [6]. We can observe an obvious difference in the distribution of logit h between two gender groups. In this case, if we use unified classification
123
124
125
126
127
128
threshold 0, = A = 0, it naturally brings a difference in the true positive rate and true negative rate between two gender groups, thus renders bias in classification. Instead, we observe that the optimal group-specifie threshold obtained from GSTAR (0) > 6), and fj < 0)) can adapt to such discrepancy in distribution between two demographic groups to improve both fairness and accuracy.
129
130
132
3.2
Group-Aware Classification Thresholds
Given existing classification model and sensitive attribute a, can denote true positive rate (TP,), false positive rate (FPa), true negative rate (TN,), and false negative rate (FN,) in the confusion matrix. Most fairness notions can be represented with entries in the confusion matrix. For instance,
134
135
136
Equal Opportunity (EOp) / requires TP, = TP,, and Demographic Parity (DP) [ requires TPan + FP To + Fo
N₂
No
137
where Nyya denotes the number of samples in the subset (Y y, A = a}, No N-= E, Rya denotes the number of samples in (Y y}, and N = Eygo Rya is the total number of samples.
3

---

00
0g
estimaated pur Am
540
Creferancca Femare
033 Y=0
estmmaned pol on And 0.838
640
Traferance) Hale
3.5
644
0. 07
Figure I: Histograms of logit distribution from logistic regression on CelebA data, where logit is used to determine the predicted label Ý = [()(X)= 2 0}. and 0 is the classification threshold. The top plot is for positive samples (Y' = 1, attractive), and the bottom plot for negative samples (Y = O, unattractive). In each plot, yellow/green bars represent the distribution of logit h in different sensitive groups, and blue/red curves are estimated probability density functions of logit h in different sensitive groups. 6n = 01 = 0 (black dashed line) are the default classification thresholds, that are identical for groups. The default thresholds result in biased prediction towards the unprivileged
A = 0 and A group A = 0 due to the different logit / distributions in different sensitive groups 0% (red dashed line), 04 (blue dashed line) are group-aware thresholds from GSTAR for each sensitive group.
Consider the group-aware classification threshold 0 = (0),0)), where O2 is the classification threshold for sensitive group A a. We can formulate the entries the confusion matrix w.r.t. 0 as
140
below:
6= FNa Re S fia(T)dr,
IPa(0.) 2 1
fia())dæ,
0n (na(x)d
(O.) R I (oa(x)ddr,
FP. ~
where (1) is estimated parametric probability density function of the distribution of output logit & in the subset (Y y, = a}. Here, we consider gamma, Student's t, and normal distribution as the candidates for the estimated distribution, and select the one that has the maximum likelihood with the output distribution. Without loss of generality, this can be generalized with other parametric probability density function based on the needs or prior knowledge.
143
144
145
148
147 Then, we formulate the classification error into a least-squared optimization problem. We denote objective function as (()) which consists of the performance loss Lper (0) and fairness loss faair Lper (0) and
classification problem with the objective of minimizing
149
f fair (0) measures the error in performance and fairness respectively that are represented with the
150
151
entries of the confusion matrix. In other words, our goal is to minimize the objective function L())
152
below:
fasr (()) = (p) (0) + AC (0),
(2)
153
where À is hyperparameter that determines how much fairness enforced in the optimization.
154
The performance error Lpee (0) can be written as
Eper (8)=
T1o1 NN
FP (01) 71 FN, (0,) +
T:00 FPo +
1110
N FNo(B)))
(3)
N

---

155
As for C (0), it can be formulated to any faimess metrics that are expressible with confusion matrix. For instance, when we impose EOp (TP; TPo) and predictive equality (PE) (FP, = FPo) (2), we can get the corresponding fair by summing over the least squared form of each constraint. Also, satisfying EOp and PP is equivalent to satisfying Equalized Odds (FOd) 7 This can be formulated
156
158
159 in our fair
CEOd (0) fasr (0) fair (0)
(T - TP)()))) (PP((0))-F(((O))
Note that a lower foir value indicates a fairer threshold. When (air(()) = 0, we can interpret as the O satisfies the perfect EOd fairness.
180
161
Similar to 4. we can enforce multiple fairness constraints by summing over the least squared of each metric with different weight constant each fairness constraints if needed.
165
184
Also, it is notable that compared to the recent paper [10] that enforces fairness through confusion tensor, our formulation of fairness in fasr( represents direct notion of fairness metrics and improves the measures that allows us to achieve better performance and Pareto frontiers that is shown Section and Figure 2 For example, Agoa the paper is calculated M0 + MgPE, where M, nyo + R.y,, such that EOd is weighted sum of EOp and PE with weights being the number of samples each class. this expression, the imbalance between the two fairness criteria will grow as
165
186
167
168
169
170
the degree of imbalance in the data increases. In contrast, our formulation expresses the constraints
171
as the exact notion of each metric that is not biased by the statistics of the datset and we observe improved Pareto frontier as in Figure 2
We propose to optimize threshold 0 with alternating optimization method. Here take EOp constraint as an example to show the alternating optimization steps, then fair can be written as
174
C E ( (TP, (0)) (P)())))
The first step is to fix O, and update 0,, We can approximate the terms that are related to 0 (e.g.. TP1, FP1, TN1, FN,) in (I with first-order Taylor expansion at 8T For example,
178
8TP1
(P1( x TPI
(01 07 0
(6)
00,
0, 0,
From II.
easily derive that
07-
TP (0T ) = 1-
fu(z)dæ,
(7)
0TP
00,
Similarly, we can find the first order Taylor expansion of FP,, FNI, and TN, Then, the update of 0 179 w.r.t. can be approximated with the following minimization problem w.r.t. A
A argmin(n" + a A1)² A(e" ABA,)²
(8)
A
where A, = 01 0 and
180
af 111
Sn1 (11
no1 N
for (09-)))
N
87 fu f1 (0)-)))
oi
+ N (1 for fon(x)) 1 1
n/
n1
fu(())
(" f1o(x) +
Y400
N (1 fo)( dr. (9)
N
N
0
0
G
fu(x)dr-
(x)dr.
181 Taking the derivative of w.r.t. A and setting it to O, we can easily obtain the closed-form solution
182 of A as
a²n + 6T
A
(10)
(aT)² + A(3T)2
5

---

Algorithm 1 Optimization Algorithm of GSTAR Model
Input dataset X' x A x ) {(x, a. y,) y,) |==1- classification model h(X), hyperparameter X. Output Group-specific threshold 0 (01, On). Initialize 0 = (01, fb) )= = (0, 0).
1. Given classifier H (z). estimate probability density function faa y, a E {0,1} by maximum likelihood estimation.
while not converge do
2. Calculate the optimal step A as A1 =
013 Acher with a1, 22,,1,,1 72, 61 values shown in af+A3f
3. Update the threshold: 01 < 01 A1;
4. Calculate the optimal step Ao Ao
ao ABoto with ag, So. no, co values calculated in +g
similar way as in
(
5. Update the threshold:0o 0o + Do.
end while
The second step is to fix 01 and update 0o. and this can be achieved in similar way of updating 01- Then we can finalize the alternating optimization as:
184
T = 0u Ag 07 ----++47
(11)
185
is notable that each iteration we derive the optimal update step 8, which eliminates the burden of tuming hyperparameter (such as learning rate) in iterative algorithm. The optimization step is summarized in Algorithm [ The above algorithm can easily extend to multiple fairness constraints
186
187
by adding corresponding squared-loss fairness terms to (2)
Time Complexity:
The alternating optimization of GSTAR model of low computational cost. We take at most one pass of the data for learning the estimated probability density functions Sgo in (T) (we do not even need to traverse the data if the parameters (such mean and variance in Gaussian distribution) for the estimated probability density functions fya can be provided). The optimization
190
191
192
of O with alternating optimization is efficient since only need fya as we have seen in (9) and (TO).
193
R is vector with fixed small size. Therefore, need constant time for each update. Overall, the time complexity of GSTAR is (n + 7), where n is the number of samples, and T is the number of iterations in alternating optimization.
194
185
196
197
We further derive the theoretical analysis our GSTAR model on the balance between fairness and accuracy, which indicates that the optimal solution provides guarantees model accuracy under the optimal fairness constraint. Details of the theoretical analysis is in the Supplementary material. Besides, if unified threshold is necessary
199
[3, i.e., 0 ou. the optimization algorithm also applies and we only have one scalar variable in 2b. When we have a unified threshold, we do not require sensitive information in the testing phase that
201
conform more strict privacy regulations than group-awaad aware thresholding. However, we have to sacrifice both fairness and accuracy as the thresholding is less flexible.
203
205
4
Experiments
206
In this section, we validate GSTAR model on four well-known fairness datasets and compare with other state-of-the-arr methods. First, plot Pareto frontiers of ours and FACT (MS) [10] to demonstrate the trade-offs between fairness and accuracy. Second, we evaluate the models with different fairness metrics and validate that our model is highly adaptive any fairness metries that are expressible with confusion matrix 7 11, 2 D. Third, we use our model as a post-processing method to existing fair models and show that model further improves existing fair models in efficient and model-agnostic manner.
208
210
212
213
4.1
Experimental Setup
We compare with multiple fairness approaches in the experiments. For clear demonstration of results, 215
we use different shapes of marker for each comparing methods in Figure 2 annd_Figure 4 The compar- ing methods include: Learning fair representations for kernel models (abbreviated as FGP) [2]].

---

FACT
PACT
COd tanater better)
Cod tamallar the bettart
(a) CelebA Dataset
(b) Adult Dataset
0.28
COd tunaler better)
COd tonalar the betteri
(c) Compas Dataset
(d) German Dataset
Figure 2: Model-specific Pareto frontiers of equalized odds to show the upper bound of best achievable accuracy under different fairness constraints. Upper right region under the boundary shows better fairness and higher accuracy. We plot three variations of GSTAR (star-shaped) with different faimesss objectives. GSTAR is the closest to the Pareto frontier which indicates the best trade-offs.
217 Fairness confusion tensor (abbreviated as FACT) [00, Disparate impact remover (abbreviated as DIR) (6). Adversarial de-biasing (abbreviated as AdvDeb) 224, Calibrated equalized odds post-processing (abbreviated as CEOPost) (20). Equality of opportunity in supervised learning (abbreviated as Odds) 7. Learning ad adversarially fair and transferable representations (abbrevi- ated as LAFTR) [7]. and Baseline: For CelebA dataset, we use ResNet50 (8) as a reference, and logistic regression for all other datasets. Our method is optimized with À in the range of [10-1 10*] with alternating optimization method. All experiments are implemented with Pytorch framework on 19. 9960X CPU and Quadro RTX 6000 GPU.
219
221
223
225
We choose broadly used fairness metries in evaluation including: equal opportunity difference and equalized odds difference (abbreviated as EOp, and EOd respectively) 7 1 1-disparate impact (abbreviated as 1-DIMP) [: balanced accuracy difference (abbreviated as BD).
227
228
We evaluate the methods on four fairess datasets: CelebA image datase [1]. Adult dataset from the UCI repository (12). COMPAS (Correctional Offender Management Profiling for Alternative Sanctions) dataset, and German credit dataset from the UCI repository (5). All data is split as 70%
229
230
231
for training and 30% for testing. More details of the comparing methods, evaluation metrics, and datasets are provided in the Supplementary material.
232
233
4.2
Performance and Fairness-Accuracy Trade-Off's
234
In this subsection, we look into the performance evaluation of GSTAR comparing with other state-of- the-art methods. We consider Pareto frontier to visualize the trade-off's between fairness and accuracy demonstrate the measure of performance.
235
236
237
we plot Pareto frontier, which is the upper bound for the accuracy- fairness trade-offs, desired output locates the upper right region under the boundary which corresponds to higher values in accuracy and lower values in fairness discrepancy. With the same fairness constraints given, achieve better frontier than the FACT 10 as equally weigh on demographic statistics and have a better feasible region. To obtain our results (star points), we first estimate the
In Figure 2,
239
240
241
logit distribution from the output of the baseline model, and then we get optimal adaptive thresholds with corresponding fairness metric by updating w.r.t. the objective function in (2.. Here we have three combinations of fairness imposed to GSTAR: demographic parity (DP), equalized odds (EOd), and
243
244
http://mmlab.. ie. cuhk edu
https::/github http:///hhaaooooooorroooooo////p
7

---

(a) CelebA Dataset
(b) Adult Dataset
145
(c) Compas Dataset
(d) German Dataset
Figure Quantitative evaluation on fairness and performance metries. The bar plots indicate fairness measures (EOp, EOd, BD, 1-DISP) of each model. Lower fairness values in the left y-axis shows better fairness. The line plots indicate the performance measure (balanced accuracy (BA) and accuracy (ACC) of each model. Higher performance values in the right y-axis shows better classifcation performance. We consider three variations of GSTAR models (DP, EOd, DP+EOd).
245
with both constraints (DP+EOd), By post-processing on simple baseline, we achieved significantly better fairness with small sacrifice in accuracy. In all datasets, GSATR got competitive or better results than other ofate-of-the-arr methods on both fairness and accuracy.
247
248
For example, we got ggo = (0.640, -0.627) for the CelebA dataset. This shows that we have 249 a higher threshold for the privileged group and lower threshold for the unprivileged group. This optimal thresholding from GSTAR allows more samples from the privileged group to be correctly predicted as unattractive that would compensate for the discrimination the original model, In other words, this improves predictive equality [2] with huge amount from 0.235 to 0.014. Also, true positive rate difference (also known as equality of opportunity (7) got reduced from 0.282 to 0.018. It is notable that GSTAR only sacrificed 2.2% of accuracy to bring the big improvement in faimess.
251
253
255
Since the objective function of our model is independent data dimensionality, our model is much more efficient especially for high dimensional data. We mostly outperform the computational cost comparing to the other methods. The comparison of computational time on the datasets can be found in the Supplementary material.
256
257
259
4.3
Flexibility and Multiple Fairness Constraints
260
Since each fairness metric has different interests, has been theoretically proven that they cannot be perfectly satisfied all together (20 2 ITI Because of this inherent trade-off' between fairness metrics, most of the recent works focus on single metric at a time to achieve fairness. However with GSTAR, have the flcxibility to optimize
282
multiple fairness constraints that can be represented in the confusion matrix format. Morcover, given the estimated distribution fyo of a black-box classification model, we can adjust the optimal 0 based on the needs by accommodating different fairness criteria.
264
266
Figure 3 demonstrates the result of the methods with fairness metrics and accuracy trade-off eval- uations. Overall, the variations of GSTAR achieve the best fairness on each target faimess while preserving the performance. For example in Figuure 3(a) GSTAR with E0d constraint has outstanding performance in most fairness metrics with comparable accuracy (80.3%). Comparing with GSTAR (EOd), when we introduce FOd and DP together (DP+EOd), we achieve significantly better w.r.t. DP fairness with sacrificing small amount of accuracy and EOd.
267
268
270

---

FACT PaRnO
F4TT Paamo
0.1
DEEAA dakbre
0.82
0.3
CSTAT.On
CSTASoon
035
DSTAP-PO
DSTAR-P0
10
107
10"
23
10
20"2
10'1
10"
EDd (smalle the better]
EDd (smalee Use better]
Adult Dataset
(b) Compas Dataset
Figure 4: Illustration of post-processing (magenta colored points) existing faimess models (blue colored points). Given the outputs of each model, we efficiently improve existing fairness models with optimized group-aware thresholds from GSTAR.
272 In general, by sacrificing individual fairness performance, we could introduce multiple constraints. Also, we implicitly observe that the more fairness constraints are introduced, the more accuracy is sacrificed. We empirically found that in some cases (e.g. [Figure 3(c)). introducing multiple fairness
273
274
275
is complementary to each other that improves both conditions.
276
4.4
Post-Processing on an Existing Fair Model
277
For a binary classifier that has single fixed classification threshold for out logit, and 0.5 for label probability), we can improve the trade-off between fairness and accuracy via GSTAR post- processing. Given the logit/probability of the dataset from a black-box model, we can improve the faimeess as illustrated in FFgiuree 4 In most cases, we observe improvement in fairness after GSTAR also interesting to note that by optimizing the different thresholds for each protected group, we even obtain better performance on both fairness and accuracy, which indicates that the threshold optimization can not only improve fairness but also accuracy.
278
279
280
281
pooc-pro.....
285
284
However, when the distribution of the logits/poobability is highly extreme (such as the results of using GSTAR post-process CEOPost), it is difficult to estimate the distribution and thus causes erroneous optimization in GSTAR. We empirically found that when the dataset is extremely imbalanced such that we do not have enough samples to estimate the logit/probabiiltyy distribution, or black-box model is too certain to the prediction that samples are concentrated to certain output, this problem arises.
285
286
287
Conclusion and Discussion
289
290
In this paper, we propose a group-aware threshold adaptation method (GSTAR) to post-process a black- box model and optimize over multiple fairness constraints. We directly optimize the classification threshold for each demographic group w.r.t. the classification error and multiple fairness constraints unified objective function, such that we can practically achieve an optimal trade-off between accuracy and fairness in fair classification. Our method is applicable to diverse notions of group fairness as the majority of fairness notions can be expressed as linear or quadratic equation through confusion matrix. We empirically show that GSTAR is flexible with fairness regularization, efficient with low computational cost. We also notice that the adaptive thresholds benefit accuracy some cases. GSTAR agrees to protect privacy such as article 17 of EU's GDPR [11] with model-agnostic post-processing. We only require the estimated distribution the output from a black- model ic., our post-processing method is oblivious to features. Thus training data is no longer needed and allowed to be discarded after training the black-box model.
291
292
293
294
295
297
299
301
302
Further, we empirically find that GSTAR is not applicable to post-process some classification models in the following situations: 1) the model does not provide logitprobability as the outcome; 2) The model provides an extreme distribution of the output logit/probability. For example, when the model
303
304
305
too certain about its prediction, will be difficult to perform probability density estimation. In our future work, we will study possible strategies to solve the above limitations, and extend GSTAR to mllsi-class, multi-sensitive group problems and improve the fairness- accuracy trade-off in a more
307
general scheme.

---

References
309
310
[1] Solon Barocas and Andrew D Selbst. Big data's disparate impact. Calif. L. Rev. 104:671, 2016.
311
[2] Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism
312
prediction instruments. Big data, 5(2):153-163, 2017.
313
[3] Sam Corbett-Davies Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of fairess. In KDD, pages 797-806, 2017.
[4] Julia Dressel and Hany Farid. The accuracy, faimess, and limits of predicting recidivism. Sci. Adv, (())eeaa55880, 2018.
316
317
[5] Dheeru Dua and Casey Graff. UCI machine learning repository. 2019.
318
[6] Michael Feldman. Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkata- subramanian. Certifying and removing disparate impact. In KDD, pages 259-268, 2015.
319
320
[7] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In NeurlPS, pages 3315-3323 2016.
322
[8] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pages 770-778, 2016.
325
324
[9] Faisal Kamiran, Asim Karim, and Xiangliang Zhang. Decision theory for discrimination-aware classification. ICDM, pages 924-929 IEEE, 2012.
325
326
[10] Joon Sik Kim, Jiahao Chen, and Amect Talwalkar. Model-agnostic characterization of fairness trade-offs. arXiv preprint arXiv:2004.0344 2020.
328
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. arXiv preprint urXiv: 05807, 2016.
329
330
[12]
Ron Kohavi. Scaling up the accuracy of uuive-bayes classifiers: A decision-tred hybrid. In KDD, volume 96, pages 202-207, 1996.
331
332
[13] Lydia T Liu, Sarah Dean, Esther Rolf, Max Simchowitz, and Moritz Hardt. Delayed impact of fair machine learning. arXiv preprint 3rXiv:/803.04338 2018.
[14] Lydia Liu, Max Simchowitz, and Moritz Hardt. The implicit faimees criterion of unconstrained learning. In ICML, pages 4051-4060, 2019.
335
115] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In ICCV, pages 3730-3738, 2015.
337
338
[16] Vishnu Suresh Lokhande, Aditya Kumar Akash, Sathya Ravi, and Vikas Singh. Fairalm: Augmented lagrangian method for training fair models with little regret. In ECCV, pages 061-381. Springer, 2020.
340
341
[17] David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. arXiv preprint arXiv:1802.06300 2018.
342
343
[18]
Aditya Krishna Menon and Robert C Williamson. The cost of fairness in binary classification. In ACM FAccT, pages 107-118, 2018.
[19] Dino Pedreshi, Salvatore Ruggieri, and Franco Turini. Discrimination-awanl data mining. In KDD, pages 560-568, 2008
346
347
[20] Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinherger. On faimess and calibration. In NeurlPS, pages 5680-5689, 2017.
348
349
[2]]
General Data Protection Regulation. Regulation eu 2016/679 of the european parliament and of the council of 27 april 2016. Official Journal of the European Union. Available at: hitp:/lec. europa.
351
on_en. pdf (accessed 20 September
2017), 2016.
10

---

353
[22] Hee Jung Ryu, Hartwig Adam, and Margaret Mitchell. Inclusivefacenet: Improving face
354
attribute detection with race and gender diversity. arXiv preprint arXiv:1712.00193, 2017.
355
[23]
Zilong Tan, Samuel Yeom, Matt Fredrikson, and Ameet Talwalkar. Learning fair representations for kernel models. In AISTATS, pages 166- 2020.
356
357
[24] Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In A/ES, pages 335-340, 2018.
358
359
[25] Han Zhao and Geoff Gordon. Inherent tradeoffs in learning fair representations. In NeurlPS, pages 15675-15685, 2019.
380
Checklist
361
362
1. For all authors...
363
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
5
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
367
Section 5
388
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
389
2. If you are including theoretical results...
371
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 1 in the Supplementary material.
372
373
(b) Did you include complete proofs of all theoretical results? [Yes] See Section in the Supplementary material.
375
3. If you ran experiments...
376
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] We will provide the code and instructions at request. The data used in the experiments are public available. See Section 2.3 in the Supplementary material.
377
378
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4.1
381
382
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Section 4.3
383
384
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 4.1
385
386
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
387
(a) If your work uses existing assets, did you eite the creators? [N/A]
308
(b) Did you mention the license of the assets? [N/A]
389
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you' 're using/curating? [N/A]
392
393
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
394
5. If you used crowdsoureing conducted research with human subjects...
396
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
397
398
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
401
11


Reviews:
[{"review_id": "iBAj-zTyurJ", "reviewer": "Reviewer_qnqF", "summary": "The authors propose a new post-processing group-aware threshold search procedure for fair classification. The procedure is efficient, amenable to different types of underlying classification models, and is empirically shown to be working with multiple fairness criteria. The authors also derive  Pareto frontier of their model for the fairness-accuracy trade-off. Lastly, the authors conclude with experiments on four datasets showing the efficacy of their method.", "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": "Strengths:\n1. Relevant problem to the NeurIPS community.\n2. Rigorous treatment to an important problem.\n3. Experimental evaluation is good that includes multiple datasets along with relevant baselines.\n\nWeaknesses:\n1. Novelty: The idea of using multiple thresholds for different demographic groups seems to be an obvious thing to do. Prior work may not have done analysis of the type that is provided in this paper, but my guess is it could have been used in the previous papers (maybe as baselines). I would let other reviewers who are more aware of the fairness literature to decide on the novelty of the paper. \n2. The authors have not provided any convergence analysis of the proposed procedure. Is it guaranteed to converge to a good solution (good thresholds)?\n2. Minor point: The entire theoretical analysis has been pushed to appendix including the results on Pareto frontier. If the paper is accepted, I would encourage authors to bring some results in the main paper. \n\nDetailed Comments:\nOverall, I liked the paper and do not have any major concern other than novelty of the idea. The following points may further help to clarify/improve the paper.\n\n1. In related works, especially, lines 74-79, can you please specify how your work is different from prior work?\n\n2. Why is there a square in equation 3? Is it because it helps in derivation? Can we also use weighted measures for L_per and L_fair as done in the following papers:\nHiranandani, Gaurush, et al. \"Fair Performance Metric Elicitation.\" NeurIPS (2020). -- Definition 1, Equation (6)\nHiranandani, Gaurush, et al. \"Quadratic Metric Elicitation with Application to Fairness.\" arXiv preprint arXiv:2011.01516 (2020). -- Definition 4, equation (13)\n\n3. Equation (8) does not contain any subscripts; whereas, the terms below line 180 do. Can you please clarify?\n\n4. As mentioned before, the authors have not provided any convergence analysis of the proposed procedure. Is it guaranteed to converge to a good solution (good thresholds)?\nAlso, what happens to their procedure in case of multiple sensitive groups? Does a coordinate wise optimization for thresholds work in this case?\n\n5. The graphs are not readable. Authors can increase the legend size, if possible, remove some trivial baselines to make the graphs more readable.\n\n6. There are good insights in lines 272-275.\n\n7. As the authors mention in their limitations that their method may not work if the underlying models gives over-confident probability distributions. One suggestion to the authors is that they can use calibration or label-smoothening in that case. \n\nMinor:\nThe authors can remove bold  text while explaining baselines. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "c2MVBQ2C3OB", "reviewer": "Reviewer_MyCa", "summary": "This paper proposes a threshold modification method to post-process the trained classifiers. The threshold learning is formulated as an optimization task and an efficient technique is proposed to learn the thresholds for groups. The proposed adaptive threshold learning is able to work with multiple fairness constraints.", "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": "originality: fair\nquality: good\nclarity: good\nsignificance: good\n\nStrength:\n\n1. The proposed method learns adaptive thresholds for various groups to achieve fairness. The learning technique is efficient. by using Taylor expansion. The efficient algorithm works for multiple fairness constraints.\n2. There theoretical results in Appendix are very interesting. \n\nWeakness:\n\n1. The proposed method requires a pre-defined parametric probability distribution. The requirement is kind of difficult for many real-world applications.  It is unclear whether the proposed method is sensitive to the selection of distribution.\n2. The alternative optimization method is fast but there is a lack of guarantee for the optimum. It is unclear how close the approximation to the optimal solution.\n\nOverall, the contribution of the proposed idea (threshold adjusting) is interesting. The attempt to develop an efficient learning algorithm is also interesting.  My major concern is the efficient algorithm incurs approximation errors due to the Taylor expansion. The learning algorithm requires the density function. It is unclear how the proposed alternative optimization is sensitive to the density estimation.\n\n## Post response\n\nI truly appreciate the response. It is informative and helpful for better understanding the manuscript.\n\nI had two major concerns on the density assumption and convergence. The convergence analysis is more like a practical solution to an optimization task. It shows how to approximate a solution but raises some new concerns such as how sensitive the solution is w.r.t. the relaxation and Taylor expansion. The empirical results show the sensitivity of accuracy and fairness w.r.t. the density estimation. I understand the theoretical challenge behind but I think it deserves further investigation as the optimization later requires a good estimation. In summary, my opinions and rating are unchanged. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "Yes", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "YwpN-wdXAMI", "reviewer": "Reviewer_aSYp", "summary": "The paper proposes a post-processing approach to achieve different notions of fairness. To do this, the paper first approximates the probability distribution of the output model. Group-specific confusion matrices can be derived by thresholding this distribution. The entries of such a matrix can be used to compute accuracy and various fairness metrics. The authors experimentally evaluate their approach on several datasets.", "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": "There are several concerns I have about this paper.\n\n--First of all, while it is known that to achieve fairness optimal thresholding of the risk scores/output probabilities of the model should be group-specific, there are many instances in practice where the use of the sensitive attribute is forbidden. So it is not clear to me that the model can be used in practical applications.\n\n--Connecting to the previous point, it is not clear where the benefit of the current approach compared to previous approaches is coming from. Is it because of a more clear technical approach or is it due to allowing group-specific thresholds (which would obviously perform better than approaches that utilize a single threshold). So in that respect, in the response, I would like to see the same curves being generated with only one threshold for all groups.\n\n--The approach relies on utilizing models that output probabilistic decisions as opposed to deterministic ones. This certainly does not fall into the category of utilizing black-box models. So I found the use of the term \"black-box\" misleading. \n\n--The approach also relies on good estimates of the distribution over probabilistic decisions of the model. According to the authors, the approach won't work when this distribution is mainly concentrated on the extremes. Hence, the approach is not suitable for truly black-box models. Moreover, the approach relies on a good estimation of this distribution. The authors propose several parametric families of distributions and choose the parameter which maximizes the likelihood. Is there a justification for why these families of distributions are sufficient? How does the error in estimating the probability distribution propagate to the result?\n\n--By looking at the experimental results, it is not clear that the approach provides a better Pareto frontier than FACT. The more interesting regime in practice is where the fairness violation is at most 1%. In this regime, it seems like FACT consistently outperforms the current approach. Though for fairness violations that are much smaller (like 0.1% and lower), it seems the proposed approach is doing better. But how often in practice do we care about such small values of fairness violations?\n\n--The optimization problem is not solved exactly. Are there any approximation guarantees?\n\n--Many details of the experiments are missing. For example, what lambda values are used to derive the Pareto frontiers? Why there is only one accuracy/balanced accuracy are reported for different notions of fairness in Figure 3? Is this averaged over different notions of fairness?\n\nMinor comments:\n\n--The use of the log scale for the x-axis is a bit misleading in the figures. Is it because the approach only outperforms FACT in really small fairness violation values?\n\n--The figures are very crowded. I have to zoom in to read the legend. \n\n--It seems a bit suspicious that adding multiple notions of fairness, can improve the total fairness violation compared to using only one fairness metric in Figure 3. Is there any justification for this observation?\n\n-------------------------------\nPost-rebuttal: please see my official comment\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I found the discussion on the limitation and societal impact to be satisfactory.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "PztY5eL1XT0", "reviewer": "Reviewer_5UxG", "summary": "This paper introduces a method for finding fair and optimal thresholds for binary classification. It considers the mean squared error as the objective function. Instead of solving a constrained optimization problem, they add a  fairness loss to the objective function. \n\nThen using Taylor approximation,  the optimization problem is reduced to an optimization function with a quadratic utility. The proposed method has low complexity ($\\mathcal{O}(n+T)$). Moreover, it improves the fairness accuracy tradeoff as compared to existing works. ", "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": "While Algorithm 1 is pretty clear, the experiment results are not clear at all. \n\nFor instance, in Figure 2, LAFTR is an adversarial method for fair learning. LAFTR works for different fairness notions (e.g., equal opportunity, statistical party (SP), etc.). However, in figure 2, is not clear which fairness notions have been considered for LAFTR.  Also, there are different points for a single algorithm in each plot. What does that mean? \nThe x-axis in figure 2 is EOd. What does this mean? EOd imposes two constraints. how do you measure it in one dimension?\n\nThe same issue exists in Figure 3.  Eq.Odds [7] can be used to satisfy EOd or EOp.  LAFTR can be used for EOD EOp and SP. Which constraint are you using when training LAFTR or Eq.Odds. If LAFTR is trained for satisfying EOp, and GSTAR is designed to satisfy EOp, then we cannot compare the fairness accuracy tradeoff. \n\nYou should clarify in detail that what each element in figure 2 and 3 mean. Without clarification, I am not able to compare your method with other methods.  It is very likely that I change my score after the authors' response. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, They have.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a post-processing technique to tune group-specific thresholds on a classifier to satisfy fairness constraints. The consensus from a majority of the reviewers is that the paper needs more work and is not ready for publication in its current form.

One of the main concerns is the assumption that the "estimated probability density function" follows a parametric form, and that it's unclear how practical this assumption is, and what happens when it fails or only holds approximately. A second concern is that the proposed threshold-tuning procedure does not come with a convergence guarantee. In response, the authors provide two separate results: (i) an asymptotic convergence guarantee for their optimization algorithm under some initial conditions, (ii) an adaptation of a result from Hardt et al. (2016) to show that the fairness constraint is approximately satisfied under some conditions on the estimated probability density. 

Both these are however substantial additions to the paper, and would require another round of review. Hence we strongly encourage the authors to use the feedback provided to improve their manuscript and submit it to a future venue. 

P.S. I appreciate the authors clarification on the similarities between the requirements in their paper and that in Hardt et al. (and the potential advantage that their approach offers in providing a tighter bound), but would have to give it some more thought. Bringing out some of these differences/similarities with Hardt et al. would make the paper more compelling.
Decision: Reject