Non-convex Optimization for Learning a Fair Predictor under Equalized Loss Fairness Constraint
Authors: Mohammad Mahdi Khalili
Xueru Zhang
Mahed Abroshan
Iman Vakilinia
Venue: ICLR 2022 Submitted (2022)
Keywords: Non-convex Optimization
Fairness
Supervised Learning

Abstract: Supervised learning models have been increasingly used in various domains such as lending, college admission, natural language processing, face recognition, etc.  These models may inherit pre-existing biases from training datasets and exhibit discrimination against protected social groups. Various fairness notions have been introduced to address fairness issues. In general, finding a fair predictor leads to a constrained optimization problem, and depending on the fairness notion, it may be non-convex. In this work, we focus on Equalized Loss ($\textsf{EL}$), a fairness notion that requires the prediction error/loss to be equalized across different demographic groups. Imposing this constraint to the learning process leads to a non-convex optimization problem even if the loss function is convex. We introduce algorithms that can leverage off-the-shelf convex programming tools and efficiently find the $\textit{global}$ optimum of this non-convex problem. In particular, we first propose the $\mathtt{ELminimizer}$ algorithm, which finds the optimal $\textsf{EL}$ fair predictor by reducing the non-convex optimization problem to a sequence of convex constrained optimizations. We then propose a simple algorithm that is computationally more efficient compared to $\mathtt{ELminimizer}$ and finds a sub-optimal $\textsf{EL}$ fair predictor using $\textit{unconstrained}$ convex programming tools. Experiments on real-world data show the effectiveness of our algorithms.  

Under review as a conference paper at ICLR 2022
NON-CONVEX OPTIMIZATION FOR LEARNING A FAIR PREDICTOR UNDER EQUALIZED Loss FAIRNESS CON- STRAINT
Anonymous authors Paper under double-blind review
ABSTRACT
Supervised learning models have been increasingly used in various domains such as lending, college admission, natural language processing, face recognition, etc. These models may inherit pre-existing biases from training datasets and exhibit discrimination against protected social groups. Various fairness notions have been introduced to address faimess issues. In general, finding a fair predictor leads a constrained optimization problem, and depending on the fairness notion, may be non-convex. In this work, focus Equalized Loss (EL), fairness notion that requires the prediction error/loss to be equalized across different demographic groups. Imposing this constraint the learning process leads non-convex op- timization problem even if the loss function is convex. We introduce algorithms that can leverage off-the-shelf convex programming tools and efficiently find the global optimum of this non-convex problem. In particular, we first propose the ELminimizer algorithm, which finds the optimal EL fair predictor by reducing the non-convex optimization problem to sequence of convex constrained opti- mizations. We then propose simple algorithm that computationally more effi- cient compared to Elminimizer and finds sub-optimal EL fair predictor using unconstrained convex programming tools. Experiments on real-world data show the effectiveness of our algorithms.
INTRODUCTION
As machine learning (ML) algorithms are increasingly being used in applications such as education, lending, recruitment, healthcare, criminal justice, etc., there a growing concern that the algorithms may exhibit discrimination against protected population groups. For example, speech recognition products such as Google Home and Amazon Alexa were shown to have accent bias (Harwell) 2018). The COMPAS recidivism prediction tool, used by courts in the US in parole decisions, has been shown to have a substantially higher false positive rate for African Americans compared to the general population (Dressel & Farid 2018). Amazon had been using automated software since 2014 to assess applicants' resumes, which were found to be biased against women (Dastin) 2018).
Various fairness notions have been proposed in the literature to measure and remedy the biases in ML systems; they can be roughly classified into two classes: 1) individual fairness focuses on the equity individual level and requires the similar individuals to be treated similarly (Dwork al. 2012 Biega et al.) 2018 Jung et al. 2019 Gupta & Kamble 2019): 2) group fairness requires certain statistical measures to be (approximately equalized across different groups distinguished by some sensitive attributes. Their suitability for use is often application dependent, and many of them are incompatible with each other (Zhang et 2019 Hardt et al. 2016 Conitzer al., 2019 /hhng et al. 2020; Khalili et al.) 2020). Extensive approaches have been developed to satistying given definition of fairness and they generally fall under three categories: pre-processing, by modifying the original dataset such as removing certain features and reweighing, e.g., (Kamiran & Calders 2012 Celis et al., 2020); in-processing, by modifying the algorithms such as imposing fairness constraints or changing objective functions, e.g., (Zhang et al.) 2018: Agarwal al., 2018; 2019;
Reimers et al. 2021 Calmon et 2017); post-ppoe post-processing by adjusting the output of the algorithms
based sensitive attributes, e.g., (Hardt al. 2016).

---

Under review as a conference paper at ICLR 2022
In this paper, we focus group fairesss and we aim to mitigate unfairness issues in supervised learning using in-processing approaches. The problem can be cast as a constrained optimization problem where fair predictor can be found by minimizing the prediction error (i.c., loss) subject to certain group fairness constraint. In Section 2.1 we present a number of definitions of commonly used group fairness notions, namely, statistical parity (Dwork et al. 2012). equal opportunity (Hardt iet al. (016), equalized loss (Zhang et al. 2011)), and bounded group loss (Agarwal et al.) (211)) Here we are particularly interested in equalized loss which requires the expected loss be equalized across different groups.
Constrained optimization problems for finding a fair predictor have been studied in the iterature. In general, imposing fairness criterion to the optimization problem may lead to non-convex opti- mization problem. Existing works have proposed various approaches to solving such a non-convex optimization in different settings. For example, Komiyama et al. (2018) studied the non-convex op- timization for regression problems under the coefficient of determination constraint. [Agarwal et al. 2019) proposed an approach to finding fair regression model under bounded group loss and statis- tical parity fairness constraints. AAgawaa et al. (018)) studied classification problems and aimed at finding fair classifiers under various faimesss notions including statistical parity and equal opportu- nity. In particular, they considered zero-one loss as the objective function and trained a randomized fair classifier over finite hypothesis space; this problem was reduced problem of finding the saddle point of a linear Lagrangian function in (Agarwal et al.) (018). /Zhang et al. (2018) proposed an adversarial debasing technique to find fair classifier under equalized odd, equal opportunity, and statistical parity. However, there is no guarantee that this technique finds the global optimal solution. The main difference between the present work and the existing in- in-processing approaches are as follows: 1) we consider a non-convex problem for finding fair predictor satisfying Equalized Loss fairness notion, which has not been studied in the literature to the best of our knowledge. 2) We propose algorithms for finding the global optimal solution to this non-convex problem efficiently. 3) Our algorithms are easy to implement and are applicable to both regression and classification problems. 4) Unlike (Agarwal et al., 2018), our algorithms are not limited to finite hypothesis space.
Non-convex optimization problems have also been studied in other contexts such as learning over- parametrized models. For example, deep neural networks are typically trained by solving uncon- strained, non-convex problems, and methods such as gradient descent may not be suitable as they likely to find saddle points but not optimums. To address this issue, approaches have been pro- posed in recent works by incorporating the higher order derivatives (Celis et al., 2020: Anandkumar & Ge 2016) noisy gradients (Ge et al. 2015). However, these methods only find local minimum (not a global minimum) and are not applicable to our problem with a non-convex constraint.
In this work, develop novel algorithms that find the fair (sub-)optimal solutions under Equalized Loss fairness constraint efficiently. Note that while our approach and algorithms are presented in the context of fair machine learning, they are applicable any problem that can be formulated as constrained optimization problem in the form of min Lo(w) aaL (w) s.t. [w( [ww) < % where a is a constant
Our main contributions and findings are as follows.
1. We study the relationship between Equalized Loss (EL) and Bounded Group Loss (BGL) fairness notions. We show that given the existence of feasible solutions satisfying (approximate) BGL fairness, imposing (approximate) EL fairness constraint never increase losses of both groups simultaneously (Theorems I and 2 in Section I. These results help policy makers to have a better understanding of these two fairness notions.
We develop an algorithm (ELminimizer) to solve a non-convex constrained optimization prob- lem that finds the optimal (approximate) EL fair solution. We show that such non-conved opti- mization can be reduced to a sequence of convex constrained optimizations and the convergence property of the algorithm is analyzed (Theorems [nd Section 3)
We develop a simple algorithm for finding a sub-optimal (approximate) EL fair solution. We show that a sub-optimal solution is linear combination of optimal solutions to two uncon- strained optimizations and it can be found efficiently without solving constrained optimizations (Theorem 3] Section 4
4. We conduct sample complexity analysis and provide the guarantee on generalization performance Section5)..
(Theorem 7
5. We validate the theoretical results by conducting experiments on real-world data (Section 6).
2

---

Under review as a conference paper at ICLR 2022
2 PROBLEM FORMULATION
Consider a supervised learning problem where the training dataset consists of triples (X,A,Y) from two social groups. Random variable X E X' Rd= is the feature vector (in form of a column vector), A E {0, } is the sensitive attribute (c.g., race, gender) indicating the group membership, and Y y C R is the label. The feature vector X may or may not include sensitive attribute A. Label Y can be either discrete or continuous depending on the given problem: if Y is discrete (resp. continuous), then the problem is a classification (resp. regression) problem. Let F be a set of predictors fw X' - R. parameterized by weight vector w E Rd Consider loss function / y'X + R. where I(Y: (x) measures the error of fw predicting label Y. Denote the expected loss with respect to the joint probability distribution of (X, Y) by [(w)= == E(((Y, fw (X)) Then, (w = (Y fw (X)) A = a} denotes the expected loss of the group with attribute A = a.
A predictor that minimizes the total expected loss, i.e., arg minl.r L(w), can be biased against certain groups. To mitigate the risk of unfairness, various fairness notions have been proposed in the litera- ture. Some of the most commonly used notions of group fairness are as follows: 1) Statistical Parity (SP) (Dwork et al. 2012 implies that the predictor and the sensitive attribute should be indepen- dent, i.e., fw (X) A: 2) Equal Opportunity (EqOpt) (Hardt et al. 2016) requires that conditional on Y = 1, prediction and sensitive attribute are independent, i.e., Jw (X) A 1; 3) Equalized Odds (EO) (Hardt al.] 2016) requires the conditional independence between prediction and sen-
sitive attribute given Y. i.e., fw (X) T A|Y: ; 4) Equalized Loss (EL) (Zhang et al. 2019 Berk et al.
2021 requires that the losses experienced by different groups are equalized, i.e., Lo w LI(w)
5) Bounded Group Loss (BGL) (Agarwal et al., 2019) requires that the loss experienced by each group is bounded.
With fairness consideration, the goal is to find weight vector w that minimizes total expected loss in predicting Y given X, subject to certain fairness condition, i.e., ming I(w)) s.t. fairness constraint. This is a typical formulation in fair machine learning literature, and above method of finding fair predictor belongs to in-p pr-processing approaches. Because such constrained optimization can be non- convex, finding the optimal solution efficiently can be challenging. In this work, we develop novel algorithms that solves such an optimization problem udder EL fairness constraint.
2.1 EQUALIZED Loss (EL) AND BOUNDED GROUP Loss (BGL)
As mentioned in Section 2 various faimess notions have been introduced in the literature. Among them, Statistical Parity (SP), Equal Opportunity (EqOpt). Equalized Odds (EO), and Bounded Group Loss (BGL) have been studied extensively in the literature, and both in-processing and post- processing approaches have been developed to satisfy these constraints (Dwork et al. 2012 Agarwal al. 2018 Hardt et al., 2016 Zafar et al.. 2019 Fitzsimons et al., 2019). Note that different fairness notions may be conflict with each other and which one to adopt is application and context dependent. In this work, we are interested in Equalized Loss (EL) fairness notion (Zhang et al. 2019 Berk et a 2021) which implies that the prediction error should be the same across different groups and Group Bounded Loss (BGL) fairness notion (Agarwal et al. 2019) which requires the prediction error of every group to be bounded. We consider a relaxed version of EL fairness defined as follows.
Definition 1 (v-EL) A predictor f satisfies 7- 7-EL if the expected losses experienced by different demographic groups satisfy the following,
S Lo(w) - Lww) S 7.
(1)
Parameter 7 controls the degree of fairness; the smaller y implies the stronger fairness. When y 0, the exact EL fairness is attained. We say a group is disadvantaged if it experiences a larger loss. Similarly, Group Bounded Loss (BGL) fairness notion formally defined as follows.
Definition 2 (GLB A predictor f sattisfees BBL if the expected loss of each demographic group is bounded by 7, i...
L,, (w) S 7; Va E {0, 1).
Predicttive models such as logistic regression, linear regression, deep learning models, etc., are parameter- ized by weight vector. EL has also been referred to as Overall Accuracy Equality in (Berk al. 2021 Agarwal al. 2019.
3

---

Under review as a conference paper at ICLR 2022
2.2 RELATIONS BETWEEN 7-EL AND B-BGL
In this section, we formally study the relations between 7-EL and --BGL fairness notions. Under 7-EL fairness constraint, finding fair predictor is equivalent solving the following constrained optimization problem:
min L(w) s.t. [o(w)) L1 (w) 5
Let w" be denoted as the solution to and fw- is the optimal y-EL fair predictor. Theorem below shows that given the existence a feasible point satisfying 7-BGL fairness, it's impossible for both groups experiencing loss larger than from the optimal 7-EL fair predictor.
Theorem Consider the following optimization for finding the optimal 7 B-LL predictor.
min L(w) s.t. (w) S 7, Va E {0,
(4)
If Lo(w") > y and L1 (w=) > 7/, then optimization problem 4 does not have a feasible point.
We prove by contradiction. Assume w a feasible point of optimization (4 Note that w is feasible point for optimization problem well. Since both Lo(w") and L1 (w") are larger than ?,, we have,
Proof
EE fw Pr(A = 000=000-oou0 Pr 1 (w) 7 Ei fa)] = Pr (t) Pr 1)11 S.
Therefore, w can not be the solution to This contradiction proves that the optimization problem cannot have feasible point.
Theorem I iimpiis that if y-EL notion leads increase of the loss of every demographic group, then there is no optimal predictor under y-BGL The next theorem further shows that for any pre- dictor satisfying 7-EL, must satisfy 2--BGL.
Theorem Assume optimization problem 4 has at least one feasible point. Then, have,
min(Lo(w") (w")) S and max{Lo I, (ww )} < 27y
Proof 2
Let w be a feasible point of optimization problem (4), then w is also feasible point to 3}. If min{La Lo((")) La Liww")) (w*)} > %, then L(w") > 72 L(w) must hold. This is a contrudiction because implies that w" is not optimal solution to (3). Therefore. min{Lo(w") L1 (w") }} I Similarly,
we can prove max Lo(w") _L[[ww)) < 2% by contradiction. Assume max Lo(w") L1 (ww))
27. Then, max { Ta (w"), Ta (w")) min T (=n(w"), (w")} > which shows that w" is not feasible point for 3 This is a contradiction. Therefore, max (oo(")) [, (w")) 2%
Theorems 1 and investigated the relations between EL and BGL faimess notions. Since 7EEL
implies BGL and it additionally requires the approximate equality across different groups, will focus on 7-EL fairness notion in the rest of the paper. Because optimization problem (3) is non-convex optimization, finding the optimal fair y-EL solution efficiently can be challenging. In the next sections, we propose a number of algorithms that are easy to implement and can solve the optimization 3 efficiently.
OPTIMAL FAIR MODEL UNDER EL FAIRNESS
In this section, we consider the optimization problem under the EL fairness constraint. Note that this optimization problem is non-convex and finding the global optimal solution is difficult. However, we propose an algorithm which is able to find the solution to non-convex optimization (3) by solving sequence of convex optimization problems. Before presenting the algorithm, need to introduce two assumptions.
Assumption Lo(w). L, (w), and L(w) are strictly convex functiion in w.
Thhoorem iis related to Agarwal et al. 2019). In particular, they considered -BGL. that the equalized loss fairness notion may increase the loss of hoth groups.
fairness B-BGL.fairess
and mentioned

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Function SLminimman
ELminimizer" zer (WG., WG, 7
20 Agtar: -Lo(WG))
Lend = Lo(wG,)
Define Ł, (w) 1 (w) +Y
1=0
while (0)
and (1)
start do
(8) Aiid = (x()) (3)
end start)//:
Solve the following convex optimization problem,
: arg min I, (w) s.t. Lo(w) 1
(5)
( = I, (w:);
if (() 2 (5)
10
A (i+1) mid then
ssarr =1 midi and
(6+1)
X andi
12
end else
13
A ((+1)
(0) (6+1)
= (1) starts
14
end
15
end
16
i i- i
17
end
Return w
Example Consider a linear classifier fw (X) w with squared loss IYY [x ) (w
Y)². In this example, B(Z(Y, fw })) w BOTE(XXT convex in w if covariance matrix [E } is positive definite. Similarly, La (w) is strictly convex
(E(YXT)uu + E is strictly
i a} is positive definite.
Let WG. be the weight vector minimizing the loss associated with group A = a. That is,
WG_ arg min (w).
(6)
Since optimization problem (6) is an unconstrained convex optimization problem, wG, can be found efficiently by the first order condition or the gradient descent. We make the following assumption.
Assumption We assume that the following holds,
Lo(wG,) S (wG.)) and Ln (WG,) s Lo(wo,)
Assumption impples that when a group ex- periences its lowest possible loss, it should not be the disadvantaged group. Under Assumption 2 given WG, and wG., Al- gorithm D with = (i.., function ELmi nimi zer WG, e, 0)) finds the optimal 0-EL fair solution, where parame- ter > 0 specifies the stopping criterion; as + 0, the output approaches to the opti- mal solution. Intuitively, Algorithm solves non-convex optimization (3) by solving a se- quence of convex and constrained optimiza- tion problems. If > 0, Algorithm 2 finds the optimal predictor under EL using func- tion ELminimi zer.
Algorithm 2: Solving Optimization Problem
Input: WG, WG,
w. = ELminimizer(warr
e,);; - ELminimizer(ur) WG, , YY);
if L(w,) < L(w then
w" w,:
end
else
w" w.ii end
Output: w
The convergence of Algorithm I for finding the optimal 0-EL fair solution, and convergence of Al Algorithm for finding the optimal y-EL fair solution are proved in the following theorems.
5

---

Under review as a conference paper at ICLR 2022
Theorem Consider sequences (Amill 2....... and {wī /i 1,2..... generaled by Algo- rithm when = 0, ie., ELmi Slminimii zer zerzeerree (WG Wo, + 0, 0). Under Assumptions and we
have,
lim w w" and lim X 1-000
E fw (X)))
i-000
where fwr is the optimal 0- fair predictor.
Similarly, we can prove the convergence for the approximate EL fairness when 7 # 0.
Theorem Assume that Lo (Ww..) L1 (w.)) < -y and Lo(we,) I (ww,,) > 7-- Then, as c- O, the output of Algorithm goes to the optimal y- E-EL fair solution w".
The While le loop in Algorithm 1 is executed for (llog(1/e) times. There- fore, Algorithm|] [ needs to solve constrained convex optimization problem for (logg( times. Note that constrained convex optimization problems can be efficiently solved via sub-gradient meth- ods (Nedié & Ozdaglar 2009), brier methods (Wright 2001). stochastic gradient descent with one projection (Mahdavi al. 2012), etc. For instance, Nedié & Ozdaglar (2009) introduces a sub- gradient method that tinds the saddle point of the Lagrangian function corresponding to (5) and converges at the rate of (1 (k is the number of iterations). Therefore, if is the maximum error tolerance for (5), the total time complexity of Algorithm is O(1/e log(1/e))
Complexity Analysis:
4 SUB-OPTIMAL FAIR MODEL UNDER Y -EL
In Section we have shown that non-convex optimization problem can be reduced to a sequence of convex constrained optimizations (5) and based this we proposed algorithm (Algorithm 2 that finds the optimal 7-EL fair predictor. However, the proposed algorithm still requires solving convex constrained optimization in each iteration. In this section, we propose another algorithm which finds a sub-optimal solution to optimization without solving constrained optimization in each iteration.
The algorithm consists of two phases in sequence: (1) finding two weight vectors by solving two unconstrained convex optimization problems; (2) generating new weight vector satisfying 7-EL fairness with the two weight vectors found in the first phase. Because of the convexity, two uncon- strained convex optimization problems the first phase can be solved efficiently.
Unconstrained optimization. In this phase, remove EL fairmess constraint and first solve the following uncontrained optimization problem,
Phase 1:
wo arg min L(w)
Because L(w) strictly convex in w, the above optimization problem can be solved efficiently using the gradient descent method. Predictor fwo is the optimal predictor without fairness constraint, and L(wo) the smallest overall expected loss that is attainable. Let arg m Lg (wo), i.e. group à is the group that is disadvantaged under predictor fwo- Then, for the disadvantaged group à, we find wG, by solving unconstrained optimization problem (6).
Phase Binary search find the fair predictor.
For [0, 1], we define the followings,
g( La ((1 B'wo (Bw..) L1-a ((1 3 wwoo + SwG.):
I((3) = T.((1 - 3ywo + fWG.).
where function g(3) can be interpreted as loss disparity between two demographic group under predictor f(=-8)oo+ and h((3) is the corresponding overall expected loss. Some properties of functions g()) and h()) are summarized in the following theorem.
Theorem Under Assumptions and 2 the followings hold,
1. There exists 3o E [0, 1] such that g(Ba) = 0.
2. 1(99 is strictly increasing in 33 [0, 1}; g(3) strictly decreasing in B [0, 1).

---

Under review as a conference paper at ICLR 2022
Theorem 5 implies that in dw dimensional space, if we start from wo and move toward wG, along a straight line, the overall loss increases and the disparity between two groups decreases until we reach (1 8- w + Go which O-EL fairness is satisfied. Note that Sn is the unique root of Since g( is a strictly decreasing function, P can be found using binary search. For the approximate >-EL fairness, there are multiple values of such that (1 - B)wo + Swa,, satisfies y EL. Since (3) is strictly increasing in 3, among all & that satisfies y-EL faireess, we would choose the smallest one. The method for finding sub-optimal solution optimization 3 is described in Algorithm
Algorithm 3: Sub-optimal solution to optimization problem
Input: WG., Wo. 6,
Initialization: g,((B) = (3) - 7/ = O, S = 0, -0,3 if' (0) - 0 then
w wo and go to line 16;
end
while ((1) 3(1)
g(()) end start c do
(B(1) + ((9) /2n /
if g. (B midd
then
3(++1) = g(0) glit1)
g(3)
end 10
else 11
((+1) g(6) start starts onnd" g
end 13
14 end
mid wo + g(( Wa:
16 Output: w
Note that wh i le loop in Algorithm 3 is repeated for (log(1/cc) times. Since the time complexity of operations in each loop is O1), the total time complexity Algorithm (log((//e), We can formally prove that the output returned by Algorithm 3 satisfies 7-EL faimess constraint.
Theorem Assume that Assumption 7 holds. If 97(0) S 0, then wo satisfies the 7-EL fairnes; if (0(0) > 0, then lim;-soc (((8) mid (/0c exists, and (1 //ox) wo (/(00) satisfies the - fairness constraint.
worth mentioning, since h(3) incrasing, we are intrested in finding the smallest possible that (1 3)wo + Swa, satisfies y-EL. Here, ( is the smallest possible 3 under which (1
B)w + SwG, satisfies E-EL.
GENERALIZATION PERFORMANCE
So far we proposed algorithms for solving optimization 3 In practice, the joint probability distribu- tion of (X, A. Y is often unknown and the expected loss needs to be estimated using the empirical loss. Specifically, given samples (X;, Ai, YY), = 1,.., n and predictor fw. the empirical losses of entire population and each group are defined as follows,
i(w))
Σ IY Sw (x(;))) (.
1 Σ (YY,,
Th #:A,=
where n. = |(i|A = a.l. Because EL fairness constraint is defined terms of expected loss, the optimization problem of finding an optimal 7-EL fair predictor using empirical losses is follows,
S arg min ((w) s.t. (Lo(w) (w) (ww) < f.
Note that / * y and one goal in this section is to find relation between 6 and 7. We aim to investigate how to determine that with high probability the predictor found by solving problem p satisfies

---

Under review as a conference paper at ICLR 2022
y-EL faireess, and meanwhile v is good estimate of w". To present result, make the following assumption.
Assumption With probability 1 1-ô, we have the following,
sup EE
[L()] L(w)] S B(6, n, F),
where B(6, n, F) is a bound that goes to zero as n goes to infinity.
Note that the class F is learnable with respect to loss function 1, then there exists such a bound B(ô, n, F) that goes
goes infinity (Shalev-Shwartz & Ben-David 2014
Theorem Let be a set of learnable functions, and let fw and fw be the solution to and B respectively with 9
Lne(o.)) na, Then, with probability at least 1 60 the
followings hold,
[(()) I(w") n,, and [o( [1(1a S + 2B(6, no, FF + 2B(6, n1,
Theorem 7 shows that as no. n1 go to infinity, 9 + 7 and both empirical loss and expected loss satisfy 7-EL. In addition, n goes to infinity, the expected loss á goes to the minimum possible expected loss. Therefore, solving (9) using empirical loss is equivalent to solving (3) if the number of data points from each group is sufficiently large.
6 EXPERIMENTS
6.1 EXPERIMENT 1: QUADRATIC FUNCTIONS
First, we solve optimization problem 3 given the following quadratic functions,
(o(w) (wi + 5)2 (we + 2)² + (wy + 1)2 + Aw Wy.
(w) = (w) - 9) (w2 9)2 + (wa 9)2 + w1 w2 + W2 W3 + W1 w3 + 1,
[(w) = Lo(w) + L (w)
By the first order condition, we obtain W Wa, wo follows, WG, -,, wG. = [4.5, 4.5, 4.5)"
|24.53, 3.0, 26.53)
We use Algorithm| to find the optimal solution (3) and run Algorithm to find a sub-optimal so- lution. In particular, we adopt the penalty method (Ben- Tal & Zibulevsky 1997 to solve constrained convex optimization (5), i.e., by solving the following unconstrained optimization,
min Li (w) + max(0, (Lo(w) )
(10)
where / is the penalty parameter. We solve the optimization problem 10 using gradient descent with learning rate 0.001 and 10000 itcrations. We set penalty parameter = 0.5 and increase by 0.1 after every 250 iterations. Note that optimization (5) is convex and the penalty method for constrained convex optimization converges to the optimal solution (Ben- Tal & Zibulevsky 1997).
We compare the algorithms with baseline: the solution to optimization problem using the penalty method, i.e., by solving the following unconstrained optimization. min (w)
3 found
w) + T. (w) +t- [max (0, (To(w) [w - 3) + max (0, (T, (w) - To(w) 7
(11)
learning rate 0.001. We penalty parameter t = 0.5 and increase it by 0.1 every 250 iterations. Figure la illustrates the overall loss L(w) at the (sub-) optimal points obtained from Algorithms and and the baseline. z-axis represents fairness parameter 7, Since Algorithm 2 converges to the optimal solution, it achieves the smallest loss. Figure [b] illustrates the distance of the optimal point w" from the sub-optimal solutions obtained by Algorithm 3 and the baseline penalty method. It shows that when 7 is sufficiently large (less strict fairness constraint), a sub-optimal solution generated by Algorithm closer the optimal solution than the solution found using the baseline method.
When solving the optimization problem (1])
1 As an example, if F is compact subset of linear predictors in Reproducing Kernel Hilbert Space (RKHS) and loss Iyy, f (x)) is Lipschitz in f() (second argument). then Assumption 3 can be satisfied (Bartlett & Mendelson 2002). Vast majority of linear predictors such support vector machine and logistic regression be defined in RKHS.
8

---

Under review as a conference paper at ICLR 2022
267
279
Ajanieez booslire
2.8
0.40
290
-.4
255
3
Alprttmm3
263
Alpe Algortmm2
6.36
20
10
20
30
35 0.1
02
0.
0.1
(a)
Figure 1: a) Experiment 1: loss as a function of fairness parameter y. Algorithm 2 and Algorithm 3 significantly improve the loss compared to the baseline. b) Experiment 1: distance between the sub-optimal solution and the optimal solution. Algorithm 3 generates sub-optimal solution closer to the optimal solution compared to the baseline. c) Experiment 2: loss as a function of fairness parameter y. Both Algorithm and Algorithm outperform the baseline. Experiment distance between the sub-optimal solution and the optimal solution.
6.2 EXPERIMENT 2: LOGISTIC REGRESSION AND THE ADULT INCOME DATASET
The adult income dataset is a public dataset containing the information of 48,842 individuals (Ko- havi 1996). Each data point includes 14 features including age, education, race, etc. Consider race (White Black) as the sensitive attribute, denote White demographic group by A = 0 and Black group by A 1.
We first pre-process the dataset by removing the data points with a missing value or with the race other than Black and White and obtain 41,961 I data points. Among these data points, 4585 belong to Black demographic group. For each data point, we convert all the categorical features one-hot vectors and result in dæ = 110 dimensional features. We then normalize the feature vectors such that they have zero mean value and unit variance. Our goal is to find a logistic regression model satisfying E- to predict whether the income of an individual is above $50K or not.
We use Algorithm 2 and Algorithm 3 with c = 0.01 to find the optimal logistic regression model under EL. We use the penalty method described in equation (TT as the baseline. Similar to Experi- ment 1, we set learning rate as 0.001 for solving (10) and (TI). Penalty parameter é is set to be 0.5 and increases by 0.1 every 250 iterations. Figure Tc illustrates the loss of logistic regression model trained by Algorithm 2. Algorithm 3, and the baselmne It shows that Algorithm 2 outperforms the baseline; this is because that the baseline only finds sub-optimal solution while Algorithm finds the global optimal solution. As mentioned in Section 4 Algorithm 3 finds a sub-optimal solution that satisfies E-L,, and its performance can vary from good performance in Experiment 1, it does not outperform the bascline in Experiment 2. Figure [d illustrates the distances from the optimal point w" the sub-optimal solutions obtained by Algo- rithm 3 and the baseline penalty method. It shows that the distance from w" to the solution obtained under Algorithm is slightly larger than that from to the solution obtained under the baseline.
case. Even though Algorithm 3 has
7 CONCLUSION
In this work, we studied the problem of fair supervised learning under the Equalized Loss (EL) fairness notion which requires the prediction error/loss to the same across different demographic groups. By imposing EL constraint, the learning problem can be formulated as non-convex op- timization problem. We introduce a number of algorithms that find the global optimal solution to this non-convex optimization problem. In particular, we showed that the optimal solution to such a non-convex problem can be found by solving a sequence of convex constrained optimizations. We also introduced simple algorithm for finding sub-optimal solution to the non-convex problem without solving constrained convex optimization problems. addition to the theoretical guarantees, demonstrated the performance of the proposed algorithm through numerical experiments.

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
Regarding the theoretical results: This paper includes six Theorems. The proof of Theorem 1 and Theorem 2 have been provided in the main text. Due to the page limit, the proofs of the other theorems have been provided in the appendix.
Regarding the numerical examples: the first experiment does not use any dataset, and we study the performance of our proposed method on quadratic objective functions. The values for hyper- parameters (including learning and penalty parameter) have been explicitly mentioned in section 6. In the second numerical example, used the adult income dataset which is well-known public dataset our community. We explained the data pre-processing procedure Section 6.2 in details.
ETHICS STATEMENT
In this work, we proposed algorithms to find fair predictors under the EL faimesss notion. We want emphasize that selecting right fairness notion depends on the application and the authors do not make any suggestions to policy/law makers about choosing or avoiding this fairness notion.
REFERENCES
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. re- ductions approach to fair classification. In International Conference on Machine Learning, pp- 60-69, PMLR, 2018.
Alekh Agarwal, Miroslav Dudik, and Zhiwei Steven Wu. Fair regression: Quantitative definitions and ieduuction-based algorithms. In International Conference on Machine Learning, pp. 120-129. PMLR, 2019.
Animashree Anandkumar and Rong Ge. Efficient approaches for escaping higher order saddle points in non-convex optimization. In Conference on learning theory, pp. 81-102. PMLR, 2016.
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 4822 2002.
Aharon Ben-Tal and Michael Zibulevsky. Penalty/barrier multiplier methods for convex program- ming problems. SIAM Journal on Optimization, 7(2):347-366, 1997.
Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, 50(1):3-44 44, 2021.
Asia Biega, Krishna P Gummadi, and Gerhard Weikum. Equity of attention: Amortizing individual fairness in rankings. The 41st international acm sigir conference on research & development in information retrieval, pp. 405-414, 2018.
Flavio P Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. Optimized pre-processing for discrimination prevention. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 3995-4004, 2017.
Elisa Celis, Vijay Keswani, and Nisheeth Vishnoi. Data preprocessing to mitigate bias: A maxi- mum entropy based approach. In International Conference on Machine Learning, pp. 1349-1359.
PMLR. 2020.
Vincent Conitzer. Rupert Freeman, Nisarg Shah, and Jennifer Wortman Vaughan. Group faireess for the allocation of indivisible goods. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 33, pp. 1853 1860. 2019.
Jeffrey Dastin. Amazon scraps secret ai recruiting tool that showed bias against women. http: 7/reut.. rs/2Mxzkly 2018.
10

---

Under review as a conference paper at ICLR 2022
Julia Dressel and Hany Farid. The accuracy, faimess, and limits of predicting recidivism. Science advances, 4( xeaaa05558, 2018.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations theoretical computer science confer- ence, pp. 214 226, 2012.
Jack Fitzsimons, AbdulRahman Al Ali, Michael Osborne, and Stephen Roberts. A general frame- work for fair regression. Entropy, (1) 2019.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-onling online stochastic gradient for tensor decomposition. In Conference learning theory, pp. 797-842. PMLR, 2015.
Swati Gupta and Vijay Kamble. Individual fairness in hindsight. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 805-806, 2019.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29:3315-3323,, 2016.
Drew Harwell. The accent gap.
2018.
Christopher Jung, Michael Kearns, Seth Neel, Aaron Roth, Logan Stapleton, and Zhiwei Steven Wu. Eliciting and enforcing subjective individual fairness. arXiv preprint arXiv: 10660, 2019.
Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrim- ination. Knowledge and Information Systems, 33(1):1-33, 2012.
Mohammad Mahdi Khalili, Xueru Zhang, Mahed Abroshan, and Somaych Sojoudi. Improving fairness and privacy in selection problems, arXiv preprint arXiv:2012.03812, 2020.
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: decision-tree hybrid. In Kdd, volume 96, pp. 20222022222222 402-207,20 1996.
Junpei Komiyama, Akiko Takeda, Junya Honda, and Hajime Shimao. Nonconvex optimization for regression with fairness constraints. In International conference on machine learning, pp. 2737- 2746. PMLR, 2018
Mehrdad Mahdavi, Tianbao Yang, Rong Jin, Shenghuo Zhu, and Jinfeng Yi. Stochastic gradient descent with only one projection. Advances in neural information processing systems, 25:494- 502, 2012.
Angelia Nedić and Asuman Ozdaglar. Subgradient methods for saddle-point problems. Journal of optimization theory and applications, 142(():205-225) 2009.
Christian Reimers, Paul Bodesheim, Jakob Runge, and Joachim Denzler. Towards learning an unbiased classifier from biased data via conditional adversarial debiasing. arXiv preprint arXiv:2103.06179, 2021.
Shai Shalev-Shwarte and Shai Ben-David. Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
Stephen J Wright. On the convergence of the newton/log- barrier method. Mathematical program- ming, 90(1):71-100, 2001.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez- and Krishna P Gummadi. Fair- ness constraints: A flexible approach for fair classification. The Journal of Machine Learning Research, 20(1):273) ((1)))237-2278 2019.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adver- sarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp. 335-340, 2018.
Xueru Zhang, Mohammadmahdi Khaliligarekani, Cem Tekin, et. Group retention when using ma- chine learning in sequential decision making: the interplay between user dynamics and faimesss Advances in Neural Information Processing Systems, 32:15269-15278. 2019.
Xueru Zhang, Mohammad Mahdi Khalili, and Mingyan Liu. Long-term impacts of fair machine learning. Ergonomics in Design, 28(3):7-11, 2020.

---

Under review as a conference paper at ICLR 2022
APPENDIX
PROOFS
In order to prove Theorem 3
we first introduce two lemmas.
Lemma Under assumption 2
there exists w E Rdd such that [o( T1 (w)
[(ww) and
start L(w)= I x(1)
Proof. Let ho(B) Lo((1 - BywGo + (wG, ) and h1 (3) Li((1 B. + 3wG,), ). and h(3) ho( (1(3), [0, 1]. Note that V La (wG.) because wG is the minimizer of (w)). Moreover, (ww) is positive semi-defini because (.).) is a strictly convex function.
First, show that Lo((1 B)wG. + (ww,) is increasing function in 3. and L 8 B)wG, + Swe, ) is a decreasing function in 3. Note that (g(0) = (WG, wG. )" Wooooo = 0, and (0) (wa, wG.) V (Wa. (wo, WGa 2 0. This implies that (3) 2 0, A E [0, 1]. Similarly, we can show that h1 (B) I 0, V E [o. 1|.
Note that under Assumption 2 h(0) 0 and h(1) > 0. Therefore, by the intermediate value theorem, the exists 1) such that h 0. Define w 3)wG. + +wa,, We have,
h(3) = 0 =
Lo(w) = Li (T) = L(w
(12)
Wa, minimizer of Lo L(w) Lo (W) > (1)
(13)
start
K6(8) 2 E = ho(1) 2 ho(3)
A 2 (w) = l(W))
(14)
(5) Lemma 2 Lo(w;)= = mid where w is the solution to
Proof. We proceed by contradiction. Assume that Lo(w)) A mid' Since wG, is not in the feasible set of (5) V L, (w:) + O. This is a contradiction because w is an interior point of the feasible set of convex optimization and cannot be optimal if V. is equal to zero
Proof [Theorem] 3
Let 4; (A A be a sequence of intervals. It is easy to see that 11 2 12 2 ... and
(+) Astart >> 0as > co. Therefore, by the Nested Interval Theorem, n T consists of exactly
(6)
one real number X", and both (0) also converges X
start and (5) end converge to X" Because (() X +N (t)
2
mid
Now, we show that L(w")= E I for all i. Note that L(w") )- = Lo(w)) 2 (1) because wG, is the minimizer of Lo- Moreover, X(1) 2 L(w") otherwise L(w) L(w") and w" is not optimal solution under O-EL. Therefore, L(w*) E I1.
) (w is defined in Lemma I
Now proceed by induction. Suppose L(w") 1, We show that L(w") E 441 well. We consider two cases.
L(w")= S midd In this case w" is a feasible point for 5). and 1 L(ww) S (1) Therefore, L(w") E I+11-
(4)
T(ww) < (() In this case, we proceed by contradiction to show that (1) 2 (1)) Assume that (+) A
mid
(0) Define g(3) = go( 91()). where g. = L2((1 3)wG, +
(w?). Note that ( 91 (1) By Lemma 2 (1) x Therefore, g(1) = (
A0 > O. Moreover, under Assumption 2 g(0) 0. Therefore, by the intermediate value
theorem, there exists 3 E (0. such that ( 0. Similar to the proof of Lemma i
we can show that (3) in an increasing function for all E [0, 1]. As result (3)
12

---

Under review as a conference paper at ICLR 2022
9o(1) (0) Define (1 B) + B.o.. We have,
( Lo(w) L1(w) L(w) < X mid
(15)
L(w") < mid
(16)
The last two equations imply that w" is not an optimal fair solution under O-EL fairness constraint. This is contradiction. Therefore, if L(w") A then ( result, L(w") J++1
2
(0)
mid' As
By two above cases and the nested interval theorem, conclude that,
L(w") E 1 lim A L(w")
For the second part of the theorem, consider the following.
w arg min In (w)s.1., Toww) Amid T.ww))
lim W = w 1000
In order to show that w is equal to w", we proceed by contradiction. Suppose w # w" As a result, La (w T(w"). Define n(3) = (n((3) m (9), where (B) [11((1 100-3)yu0 B)WG, Sw 771 (1). By Lemma 2 the condition in (5) is binding and (o(1) = L(w")
Note that (
Therefore, (11) L(w") (www > Moreover, under Assumption 2 n70) 0. Therefore, by the intermediate value theorem, there exists B E (0, such that 7)
Similar to the
proof of Lemma [ we can show that (3) is an increasing function for all B E [0, As result
(B) < 7o = L(w"). Define w = 3)WG. + Bw We have,
(3 Lo (w) ( L(w) L(w")
(17)
The last equation implies that w" is not an optimal fair solution under O-EL fairness constraint. This a contradiction. As result, w = +.
Proof [Theorem]]
Let w" be the optimal weight vector under y-EL. Step 1. we show that one of the following holds,
Lo(w") L (w") = La(w") Li (w0) = -7
(18)
(19)
Proof by contradiction. Assume -7 < Lo(w") (ww) < 7. This implies that w" is an inte-
rior point of the feasible set of optimization problem B3) Since w" # wo, then (L(w") # 0. As a result, object function of (3) can be improved at w" by moving toward - (Lww"). This contradiction. Therefore, [[(ww) [L(ww)
Step 2. Function w, www.nimiiereiieeeeeee...em.eieee tion problem,
WG.: C, 7) is the solution to the following optimiza-
min Pr (r - -A=A0) (n(w) Pr(A = T s.l., To(w") In (=w") =
(20)
To show the above claim, notice that the solution optimization problem 20 is the as the following,
min P Low) Pr(A = 11 (w), s.t., Lo(w") )- - E (w0) = =0,
(21)
where (w) = L, (w) + yy Since Lo (W..) - ł, (W < and Lo (WG,) - L, (Wa,
> 0, by
Theorem we know that w. E.m! nimi - WG 77 find the solution to 21
13

---

Under review as a conference paper at ICLR 2022
Lastly, because [Lo(w") L1 (ww") 7, have,
w if ((w,) S ((w-g)
(22)
- O.W.
Thus, Algorithm finds the solution to 33. Proof [Theorem
1. Under Assumption 2 (g1) O. Moreover, g(0) 2 0. Therefore, by the intermediate value theorem, there exists 30 E [o, 1] such that ((8)) = 0.
2. Since wo is the minimizer of L(w). (0) 0. Moreover, since L(w) strictly convex,
(0) > 0. As result, (B) > 0 for 3 > 0.
3. Since wG, is the minimizer of La (w), and (w(w) is strictly convex, (1 is strictly decreasing function. Note that since ((3 = Pr = à La B)wo + Swa.) Pr(A ---a- B)wo + (wG.) is strictly increasing and La La((1 3w 3wG.. ) is strictly decreasing, we conclude that Lı-a 1 3)wo + SwG.) ) is strictly increasing. As result, should be strictly decreasing.
Proof [Theorem 6 First, we show that if (0) < 0, then wo satisfies 7-EL.
g. 0 9(3) S La(wo) - (I-á(wo) S
Moreover, La(w)) - LI (wo) 2 0 because arg max, La (wo). Therefore, 7-EL is satisfied.
< 0. Therefore, by the intermediate value there exists Bu such that g- (B.) O. Moreover, 9, strictly decreasing function. Therefore, the binary search proposed in Algorithm 3 converges to root of 9, (3). As a result, (1 ( ww + /loo) satisfies satisfies ELEL. Moreover, La Laww) L 2 because à arg max, La(w)). Note that since g(3) is decreasing, 3f is the smallest possible 3 under which (1 - 3)wo + fwG., 7-EL. Since h is increasing, the smallest possible 3 gives better accuracy.
Secondly, assume that 9- (0) > 0. Under Assumption 1, 9, (1) La (WG.) Li-a
Proof [Theorem]] 7
By the triangle inequality, the following holds,
[[ L, (w) - (w) - (w)ll < sup Lo(w) Lo(w)] + sup [L L, (w)). foeF
sup WEEF
LwEF
(23)
Therefore, with probability at least 28 we have,
sup [ow) L, (w)) (Lo(w) (.)ll S B(ō, no. F)+ + B(,,
(24)
f
As result, with probability 1 28 holds,
fw F, (Lo(w) L1 (w)) S < (w fw e F, F. L,(w) 5
(25)
Now consider the following.
L(w0) - L(w")= = L(0) - i(w) + i(10) - I(w")= i(w")= - L(w")
(26)
By 25 [(w) i(w") < 0 with probability 1 25. Thus, with probability at least 1- 26, we have,
L( L(w") < L( i(w) i(w") )- L(w") Therefore, under assumption
(27)
3 we can conclude with probability at least 1 65, L( L(w")
2 2B (2,6,,, F). In addition, by 24 with probability at least 28, we have,
14

---

Under review as a conference paper at ICLR 2022
(O( - [
< B(ó, no, F) + F) - [w))
$ 3y + B6,, no: F)+ + (6, F) = 7 -BB(6, no. no. 2-((,,, F)
15


Reviews:
[{"review_id": "sBY2g826HMU", "reviewer": "Reviewer_Cpty", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n- This paper considers a meaningful fairness notion EL, which is an important topic in fairness.\n- This paper provides a complete analysis on how to handle the non-convex constrained fair learning problem. Their algorithms have provable guarantees.\n\nWeakness:\n- The theoretical proof is standard but seems not hard. There is no discussion on the technical contributions.\n- The intuition of proposed algorithms seems to be dividing the constraint space into pieces, i.e., solving (5) for multiple \\lambda_mid and then selecting an optimal one from satisfiable solutions. This idea seems also appeared in a prior paper [L. Elisa Celis, Lingxiao Huang, Vijay Keswani, Nisheeth K. Vishnoi: Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees. FAT 2019: 319-328]. Could the authors provide a technical comparison?\n- I have read the comment of Reviewer toHL. I agree that the missing conference (arXiv:1802.08626) is very important. The authors should provide a detailed comparison with this work.\n", "summary_of_the_paper": "    This paper studies the problem of fair supervised learning under the Equalized Loss (EL) fairness notion, which is formulated as a non-convex constrained optimization problem. The authors introduce two algorithms that find the global (sub-)optimal solution by solving a sequence of convex (constrained) optimizations. Empirically, the algorithms perform well.", "summary_of_the_review": "The paper considers an important fairness notion EL and provides algorithms with provable guarantees. Though their technique seems not hard, this may not be the main issue in the direction of fairness. Empirically, the proposed algorithms outperform baselines. The main weakness is the missing of several important prior works.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "qKSDeivsRZE", "reviewer": "Reviewer_toHL", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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 is a well-known and closely related work in the literature, which is (arXiv:1802.08626). I am surprised that this paper was not cited in the paper. (arXiv:1802.08626) studies empirical risk minimization under fairness constraints as in this paper. (arXiv:1802.08626) also, propose to use equalized group loss as in this paper. See Definition 1 in (arXiv:1802.08626). (Their equalized loss definition is also conditioned on $y=1$ as in equal opportunity but I think their method can be also applied to equalized group loss that is defined as in this paper.) The similarities and the differences between the two papers should have been put clearly. \nHow does Theorem 7 be different than Theorem 1 in (arXiv:1802.08626)? Both theorems seem to be using the same assumption.\nThere are obvious similarities between the two papers.\n\nI think the paper is very well-written, other than the fact that the related literature part should be improved. I am not convinced by the novelty of the paper given the existing work in (arXiv:1802.08626).\nThe contribution is limited in my point of view to the introduction of the algorithms to find the fair predictor, which is interesting but it is not enough to meet the barrier of acceptance. \n\nThe fact that the paper (arXiv:1802.08626) is not mentioned at all is worrying, given that even the notation of Assumption1 and Theorem 7 is the same with (arXiv:1802.08626).\n\nThe experiment section is far away from being complete. Only one real-world dataset is considered, while there are several real-world datasets publicly available and there is no comparison with the state-of-the-art.\n\nIn proof of Lemma 1, there is the gradient of L_a(w). But it could be the case that L is not smooth and thus L_a may not be smooth too. Then, instead of talking about the gradients, one should talk about the subgradients.\nI am not sure in this case the proof of Lemma 2 goes through. \nMinor comment: In the appendix, the {s.t.}'s should be put in math mode.", "summary_of_the_paper": "This paper studies supervised learning models with fairness constraints.\nThey specifically consider equalized loss fairness constraint. \nWhen a traditional (convex) loss minimization problem is cast with additional fairness constraints, the corresponding problem is non-convex.\nThey provide algorithms to efficiently solve this problem up to global optimality.\nThey demonstrate the performance of their algorithms on real-world data.\n", "summary_of_the_review": "The contribution of the paper is not good enough given the existing literature on fair machine learning. It seems to me that this paper provides an extension to (arXiv:1802.08626). There are no numerical experiments to compare their framework with the state-of-the-art fair learning algorithms such as (arXiv:1802.08626, arXiv:1610.08452).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "irhBBGuGuS9", "reviewer": "Reviewer_2B6v", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "I found this paper to be interesting and well-motivated (finding the best classifier subject to fairness constraints is a real problem), but the results were not as compelling as I hoped. For instance, most of section 3 seems to stem from Assumption 1, wherein the loss functions L0, L1, and L are all assumed to be strictly convex. What happens if they are non-convex? \n\nI would have appreciated some analysis of Algorithm 3’s performance — how much worse than Algorithm 2 can it be in theory? The results in the second experiment suggest that it can be quite a bit worse (even worse than the baseline).\n\nThere were also issues with writing quality, which is under the bar for ICLR. There were many missing articles (a/an/the) throughout the paper, and some of the exposition was very difficult to intuitively understand. Also, just a minor note, but expectation and probability are generally encased in [] or (), not {}, which is a convention I haven’t seen before.\n\nPerhaps add a bit more motivation for the quadratic functions used in the first experiment (Section 6.1). How were they generated / chosen?\n\nAlso, just wondering: how likely is Assumption 2 to be satisfied in practice? Are there settings in which even the best loss for a certain group still means they're disadvantaged?\n", "summary_of_the_paper": "The authors study fair prediction subject to Equalized Loss (EL), and they introduce a variety of approaches for exactly and approximately solving the problem of finding the globally optimal predictor that satisfies EL. First, they show how to solve a sequence of convex constrained optimization problems in order to solve the larger non-convex problem. Next, they show how to approximately solve this problem more efficiently by using unconstrained convex optimization. Lastly, they evaluate both of their approaches on two datasets.", "summary_of_the_review": "I think the problem is a natural one (finding a good classifier subject to fairness constraints), but the technical results were not compelling and the writing quality was below the bar.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UDW3bBiXpUB", "reviewer": "Reviewer_YrTG", "summary": "", "questions": "", "limitations": "", "rating": 6, "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- Theorem 1 and 2 are interesting. Bounded loss constrained minimization does not increase the maximum loss per group \"too much\" for classification problems. This can be a nice point to make to policy makers. \n- The authors give a binary-search based thresholding method for optimizing bounded group loss constrained problems, which is also interesting, and might potentially have connections to existing optimization algorithms that use monotonicity of bounds to solve iterative subproblems. \n\nWeaknesses: \n- Assumptions: If the condition of feasibility of (4) in Theorem 2 is not true, then bounded increase in loss may not hold any more. For example, it is not true for facility location between two groups, where one can ask to minimize distance of a facility to each of two groups (for e.g., see, Too Many Fairness Metrics: Is There a Solution? By Gupta et.al. ). Placing a facility at infinity can make \"absolute diff of group distances\" to be zero, while there may be no facility that minimizes the total distances to both groups of populations. What happens in the case of classification losses? I suspect that the losses could then be unbounded. Which case might arise more frequently in practice? (if we want to think about relevance to policy). \n\n- Assumption 2 implies that when a group experiences its lowest possible loss, it should not be the disadvantaged group. -- What is the rationale for this assumption? This might be misleading a bit -- as by disadvantaged the authors simply mean the non-optimized group, but since this is a \"fairness\" paper, it can also mean demographics groups which are at a disadvantage (minorities). Is Assumption 2 even needed, since the convex functions are assumed \"strictly\" convex? \n\n- Related work - there is a lot of recent work on solving non-convex constrained formulations that result from \"fair\" objectives. To give a few examples: \n1. Nonconvex optimization for regression with fairness constraints. http://proceedings.mlr.press/v80/komiyama18a/komiyama18a.pdf \n2. Implicit Rate-Constrained Optimization of Non-decomposable Objectives http://proceedings.mlr.press/v139/kumar21b/kumar21b.pdf \n3. Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals https://jmlr.csail.mit.edu/papers/volume20/18-616/18-616.pdf \n4. Decomposition approach using monotonicity of parameters: e.g., Separable Convex Optimization with Nested Lower and Upper Constraints. https://pubsonline.informs.org/doi/10.1287/ijoo.2018.0004 \n\n\nHow does the current work compare to these - in theory and experiments? ", "summary_of_the_paper": "The authors consider minimization of convex losses constrained by either bounded loss on each group, or bounded difference of losses over two groups. The second formulation is non-convex, whereas the first formulation is convex. \n\nWhen the losses are strictly convex on both the demographic groups, so that their optima are distinct (I think this is the condition they need, but they use a more restrictive condition in the paper), they can find the \"EL\" fair predictor by solving a sequence of convex constrained optimizations, by exploiting a monotonicity property. They next give a more computationally efficient approximate algorithm for finding the EL fair predictor. ", "summary_of_the_review": "I like the way the authors approach the fairness constrained problem, and their study of property of feasible optimal solutions. However, I think the writing lacks justifications of the various assumptions, which makes the results very narrow. Further, there are many many results that consider the non-convex formulations resulting from minimum norm over demographic groups and composite objectives, and so though I think the algorithms proposed by the authors are nice, I suspect that these can be subsumed by existing literation in constrained optimization, and I would like the authors to comment on that. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers learning classifiers under a fairness constraint which enforces the loss to be equal on certain subgroups. Reviewers found the work to be well-motivated, but raised concerns on the lack of discussion and comparison to relevant prior work. Notable examples in the fairness literature are Donini et al., "Empirical Risk Minimization under Fairness Constraints", Celis et al., "Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees", while in the more broader constrained optimization literature, Kumar et al. "Implicit Rate-Constrained Optimization of Non-decomposable Objectives". The authors are encouraged to incorporate reviewers' detailed comments for a revised version of this work.
Decision: Reject