summaries:     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. 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.   When 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.  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. This paper studies supervised learning models with fairness constraints. They specifically consider equalized loss fairness constraint.  When a traditional (convex) loss minimization problem is cast with additional fairness constraints, the corresponding problem is non-convex. They provide algorithms to efficiently solve this problem up to global optimality. They demonstrate the performance of their algorithms on real-world data. 
abstractText: 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 (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 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 a sequence of convex constrained optimizations. We then propose a simple algorithm that is computationally more efficient compared to ELminimizer and finds a sub-optimal EL fair predictor using unconstrained convex programming tools. Experiments on real-world data show the effectiveness of our algorithms.
references.authors: Alekh Agarwal Alina Beygelzimer Miroslav Dudı́k John Langford Hanna Wallach
references.title: A reductions approach to fair classification
references.venue: In International Conference on Machine Learning,
references.authors: Alekh Agarwal Miroslav Dudik Zhiwei Steven Wu
references.title: Fair regression: Quantitative definitions and reduction-based algorithms
references.venue: In International Conference on Machine Learning,
references.authors: Animashree Anandkumar Rong Ge
references.title: Efficient approaches for escaping higher order saddle points in non-convex optimization
references.venue: In Conference on learning theory,
references.authors: Peter L Bartlett Shahar Mendelson
references.title: Rademacher and gaussian complexities: Risk bounds and structural results
references.venue: Journal of Machine Learning Research,
references.authors: Aharon Ben-Tal Michael Zibulevsky
references.title: Penalty/barrier multiplier methods for convex programming problems
references.venue: SIAM Journal on Optimization,
references.authors: Richard Berk Hoda Heidari Shahin Jabbari Michael Kearns Aaron Roth
references.title: Fairness in criminal justice risk assessments: The state of the art
references.venue: Sociological Methods & Research,
references.authors: Asia J Biega Krishna P Gummadi Gerhard Weikum
references.title: Equity of attention: Amortizing individual fairness in rankings
references.venue: In The 41st international acm sigir conference on research & development in information retrieval,
references.authors: Flavio P Calmon Dennis Wei Bhanukiran Vinzamuri Karthikeyan Natesan Ramamurthy Kush R Varshney
references.title: Optimized pre-processing for discrimination prevention
references.venue: In Proceedings of the 31st International Conference on Neural Information Processing Systems,
references.authors: L Elisa Celis Vijay Keswani Nisheeth Vishnoi
references.title: Data preprocessing to mitigate bias: A maximum entropy based approach
references.venue: In International Conference on Machine Learning,
references.authors: Vincent Conitzer Rupert Freeman Nisarg Shah Jennifer Wortman Vaughan
references.title: Group fairness for the allocation of indivisible goods
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Jeffrey Dastin
references.title: Amazon scraps secret ai recruiting tool that showed bias against women
references.venue: http: //reut.rs/2MXzkly,
references.authors: Julia Dressel Hany Farid
references.title: The accuracy, fairness, and limits of predicting recidivism
references.venue: Science advances,
references.authors: Cynthia Dwork Moritz Hardt Toniann Pitassi Omer Reingold Richard Zemel
references.title: Fairness through awareness
references.venue: In Proceedings of the 3rd innovations in theoretical computer science conference,
references.authors: Jack Fitzsimons AbdulRahman Al Ali Michael Osborne Stephen Roberts
references.title: A general framework for fair regression
references.authors: Rong Ge Furong Huang Chi Jin Yang Yuan
references.title: Escaping from saddle points—online stochastic gradient for tensor decomposition
references.venue: In Conference on learning theory,
references.authors: Swati Gupta Vijay Kamble
references.title: Individual fairness in hindsight
references.venue: In Proceedings of the 2019 ACM Conference on Economics and Computation,
references.authors: Moritz Hardt Eric Price Nati Srebro
references.title: Equality of opportunity in supervised learning
references.venue: Advances in neural information processing systems,
references.authors: Drew Harwell
references.title: The accent gap
references.authors: Christopher Jung Michael Kearns Seth Neel Aaron Roth Logan Stapleton Zhiwei Steven Wu
references.title: Eliciting and enforcing subjective individual fairness
references.authors: Faisal Kamiran Toon Calders
references.title: Data preprocessing techniques for classification without discrimination
references.venue: Knowledge and Information Systems,
references.authors: Mohammad Mahdi Khalili Xueru Zhang Mahed Abroshan Somayeh Sojoudi
references.title: Improving fairness and privacy in selection problems
references.venue: arXiv preprint arXiv:2012.03812,
references.authors: Ron Kohavi
references.title: Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid
references.venue: In Kdd,
references.authors: Junpei Komiyama Akiko Takeda Junya Honda Hajime Shimao
references.title: Nonconvex optimization for regression with fairness constraints
references.venue: In International conference on machine learning,
references.authors: Mehrdad Mahdavi Tianbao Yang Rong Jin Shenghuo Zhu Jinfeng Yi
references.title: Stochastic gradient descent with only one projection
references.venue: Advances in neural information processing systems,
references.authors: Angelia Nedić Asuman Ozdaglar
references.title: Subgradient methods for saddle-point problems
references.venue: Journal of optimization theory and applications,
references.authors: Christian Reimers Paul Bodesheim Jakob Runge Joachim Denzler
references.title: Towards learning an unbiased classifier from biased data via conditional adversarial debiasing
references.venue: arXiv preprint arXiv:2103.06179,
references.authors: Shai Shalev-Shwartz Shai Ben-David
references.title: Understanding machine learning: From theory to algorithms
references.venue: Cambridge university press,
references.authors: Stephen J Wright
references.title: On the convergence of the newton/log-barrier method
references.venue: Mathematical programming,
references.authors: Muhammad Bilal Zafar Isabel Valera Manuel Gomez-Rodriguez Krishna P Gummadi
references.title: Fairness constraints: A flexible approach for fair classification
references.venue: The Journal of Machine Learning Research,
references.authors: Brian Hu Zhang Blake Lemoine Margaret Mitchell
references.title: Mitigating unwanted biases with adversarial learning
references.venue: In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society,
references.authors: Xueru Zhang Mohammadmahdi Khaliligarekani Cem Tekin
references.title: Group retention when using machine learning in sequential decision making: the interplay between user dynamics and fairness
references.venue: Advances in Neural Information Processing Systems,
references.authors: Xueru Zhang Mohammad Mahdi Khalili Mingyan Liu
references.title: Long-term impacts of fair machine learning
references.venue: Ergonomics in Design,
sections.text: 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 (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 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 a sequence of convex constrained optimizations. We then propose a simple algorithm that is computationally more efficient compared to ELminimizer and finds a sub-optimal EL fair predictor using unconstrained convex programming tools. Experiments on real-world data show the effectiveness of our algorithms.
sections.heading: 1 INTRODUCTION
sections.text: As machine learning (ML) algorithms are increasingly being used in applications such as education, lending, recruitment, healthcare, criminal justice, etc., there is 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 at individual level and it requires the similar individuals to be treated similarly (Dwork et 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 al., 2019; Hardt et al., 2016; Conitzer et al., 2019; Zhang et al., 2020; Khalili et al., 2020). Extensive approaches have been developed to satisfying a 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 et al., 2018; 2019; Reimers et al., 2021; Calmon et al., 2017); post-processing, by adjusting the output of the algorithms based on sensitive attributes, e.g., (Hardt et al., 2016).
  In this paper, we focus on group fairness 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 a fair predictor can be found by minimizing the prediction error (i.e., 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 et al., 2016), equalized loss (Zhang et al., 2019), and bounded group loss (Agarwal et al., 2019). Here we are particularly interested in equalized loss which requires the expected loss to be equalized across different groups.
  Constrained optimization problems for finding a fair predictor have been studied in the iterature. In general, imposing a fairness criterion to the optimization problem may lead to a non-convex optimization 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 optimization for regression problems under the coefficient of determination constraint. Agarwal et al. (2019) proposed an approach to finding a fair regression model under bounded group loss and statistical parity fairness constraints. Agarwal et al. (2018) studied classification problems and aimed at finding fair classifiers under various fairness notions including statistical parity and equal opportunity. In particular, they considered zero-one loss as the objective function and trained a randomized fair classifier over a finite hypothesis space; this problem was reduced to a problem of finding the saddle point of a linear Lagrangian function in (Agarwal et al., 2018). Zhang et al. (2018) proposed an adversarial debasing technique to find a 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-processing approaches are as follows: 1) we consider a non-convex problem for finding a 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 overparametrized models. For example, deep neural networks are typically trained by solving unconstrained, non-convex problems, and methods such as gradient descent may not be suitable as they are likely to find saddle points but not optimums. To address this issue, approaches have been proposed in recent works by incorporating the higher order derivatives (Celis et al., 2020; Anandkumar & Ge, 2016) or noisy gradients (Ge et al., 2015). However, these methods only find a local minimum (not a global minimum) and are not applicable to our problem with a non-convex constraint.
  In this work, we 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 to any problem that can be formulated as a constrained optimization problem in the form of minw L0(w)+αL1(w) s.t. |L0(w)−L1(w)| < γ, where α 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 1 and 2 in Section 2.1). These results help policy makers to have a better understanding of these two fairness notions.
  2. We develop an algorithm (ELminimizer) to solve a non-convex constrained optimization problem that finds the optimal (approximate) EL fair solution. We show that such non-convex optimization can be reduced to a sequence of convex constrained optimizations and the convergence property of the algorithm is analyzed (Theorems 3 and 4, Section 3).
  3. We develop a simple algorithm for finding a sub-optimal (approximate) EL fair solution. We show that a sub-optimal solution is a linear combination of optimal solutions to two unconstrained optimizations and it can be found efficiently without solving constrained optimizations (Theorem 5, Section 4).
  4. We conduct sample complexity analysis and provide the guarantee on generalization performance (Theorem 7, Section 5).
  5. We validate the theoretical results by conducting experiments on real-world data (Section 6).
sections.heading: 2 PROBLEM FORMULATION
sections.text: Consider a supervised learning problem where the training dataset consists of triples (X,A, Y ) from two social groups. Random variableX ∈ X ⊂ Rdx is the feature vector (in form of a column vector), A ∈ {0, 1} is the sensitive attribute (e.g., race, gender) indicating the group membership, and Y ∈ Y ⊂ 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 ∈ Rdw .1 Consider loss function l : Y×X → Rwhere l(Y, fw(X )) measures the error of fw in predicting label Y . Denote the expected loss with respect to the joint probability distribution of (X,Y ) by L(w) := E{l(Y, fw(X ))}. Then, La(w) := E{l(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., argminw L(w), can be biased against certain groups. To mitigate the risk of unfairness, various fairness notions have been proposed in the literature. 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 independent, 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., fw(X ) ⊥ A|Y = 1; 3) Equalized Odds (EO) (Hardt et al., 2016) requires the conditional independence between prediction and sensitive attribute given Y , i.e., fw(X ) ⊥ 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., L0(w) = L1(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 vectorw that minimizes total expected loss in predicting Y givenX , subject to certain fairness condition, i.e., minw L(w) s.t. fairness constraint. This is a typical formulation in fair machine learning literature, and above method of finding a fair predictor belongs to in-processing approaches. Because such constrained optimization can be nonconvex, 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 fairness 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 postprocessing approaches have been developed to satisfy these constraints (Dwork et al., 2012; Agarwal et 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 al., 2021) which implies that the prediction error should be the same across different groups,2 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 (γ-EL) A predictor f satisfies γ-EL if the expected losses experienced by different demographic groups satisfy the following,
  − γ ≤ L0(w)− L1(w) ≤ γ. (1)
  Parameter γ controls the degree of fairness; the smaller γ implies the stronger fairness. When γ = 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 is formally defined as follows.
  Definition 2 (γ-BGL) A predictor f satisfies γ-BGL if the expected loss of each demographic group is bounded by γ, i.e.,
  La(w) ≤ γ, ∀a ∈ {0, 1}. (2) 1Predictive models such as logistic regression, linear regression, deep learning models, etc., are parameter-
  ized by a weight vector. 2EL has also been referred to as Overall Accuracy Equality in (Berk et al., 2021; Agarwal et al., 2019).
  2.2 RELATIONS BETWEEN γ-EL AND γ-BGL
  In this section, we formally study the relations between γ-EL and γ-BGL fairness notions. Under γ-EL fairness constraint, finding a fair predictor is equivalent to solving the following constrained optimization problem:
  minw L(w) s.t. |L0(w)− L1(w)| ≤ γ. (3)
  Letw∗ be denoted as the solution to (3) and fw∗ is the optimal γ-EL fair predictor. Theorem 1 below shows that given the existence of a feasible point satisfying γ-BGL fairness, it’s impossible for both groups experiencing loss larger than γ from the optimal γ-EL fair predictor.
  Theorem 1 Consider the following optimization for finding the optimal γ-BGL fair predictor,
  minw L(w) s.t. La(w) ≤ γ, ∀a ∈ {0, 1}. (4)
  If L0(w∗) > γ and L1(w∗) > γ, then optimization problem (4) does not have a feasible point.
  Proof 1 We prove by contradiction. Assume w̃ is a feasible point of optimization (4). Note that w̃ is a feasible point for optimization problem (3) as well. Since both L0(w∗) and L1(w∗) are larger than γ, we have,
  E{l(Y, fw∗)} = Pr{A = 0}L0(w∗) + Pr{A = 1}L1(w∗) > γ, E{l(Y, fw̃)} = Pr{A = 0}L0(w̃) + Pr{A = 1}L1(w̃) ≤ γ.
  Therefore,w∗ can not be the solution to (3). This contradiction proves that the optimization problem (4) cannot have a feasible point.
  Theorem 1 implies that if γ-EL notion leads to an increase of the loss of every demographic group, then there is no optimal predictor under γ-BGL.3 The next theorem further shows that for any predictor satisfying γ-EL, it must satisfy 2γ-BGL.
  Theorem 2 Assume optimization problem (4) has at least one feasible point. Then, we have,
  min{L0(w∗), L1(w∗)} ≤ γ and max{L0(w∗), L1(w∗)} ≤ 2γ.
  Proof 2 Let w̃ be a feasible point of optimization problem (4), then w̃ is also a feasible point to (3). If min{L0(w∗), L1(w∗)} > γ, then L(w∗) > γ ≥ L(w̃) must hold. This is a contradiction because it implies thatw∗ is not an optimal solution to (3). Therefore, min{L0(w∗), L1(w∗)} ≤ γ. Similarly, we can prove max{L0(w∗), L1(w∗)} ≤ 2γ by contradiction. Assume max{L0(w∗), L1(w∗)} > 2γ. Then, max{L0(w∗), L1(w∗)} − min{L0(w∗), L1(w∗)} > γ which shows that w∗ is not a feasible point for (3). This is a contradiction. Therefore, max{L0(w∗), L1(w∗)} ≤ 2γ.
  Theorems 1 and 2 investigated the relations between EL and BGL fairness notions. Since γ-EL implies 2γ-BGL and it additionally requires the approximate equality across different groups, we will focus on γ-EL fairness notion in the rest of the paper. Because optimization problem (3) is a non-convex optimization, finding the optimal fair γ-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.
sections.heading: 3 OPTIMAL FAIR MODEL UNDER EL FAIRNESS
sections.text: In this section, we consider the optimization problem (3) 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 a sequence of convex optimization problems. Before presenting the algorithm, we need to introduce two assumptions.
  Assumption 1 L0(w), L1(w), and L(w) are strictly convex functions inw. 3Theorem 1 is related to (Agarwal et al., 2019). In particular, they considered γ-BGL fairness and mentioned that the equalized loss fairness notion may increase the loss of both groups.
  Algorithm 1: Function ELminimizer 1 ELminimizer(wG0 ,wG1 , , γ): 2 λ0start = L0(wG0) 3 λ0end = L0(wG1) 4 Define L̃1(w) = L1(w) + γ 5 i = 0
  6 while λ(i)end − λ (i) start > do 7 λ (i) mid = (λ (i) end + λ (i) start)/2; 8 Solve the following convex optimization problem,
  w∗i = argmin w L̃1(w) s.t. L0(w) ≤ λ(i)mid (5)
  9 λ(i) = L̃1(w ∗ i );
  10 if λ(i) ≥ λ(i)mid then 11 λ
  (i+1) start = λ (i) mid; λ (i+1) end = λ (i) end;
  12 end 13 else 14 λ
  (i+1) end = λ (i) mid; λ (i+1) start = λ (i) start;
  15 end 16 i = i+ 1; 17 end
  18 Returnw∗i
  Example 1 Consider a linear classifier fw(X ) = wTX with squared loss l(Y, fw(X )) = (wTX − Y )2. In this example, E{l(Y, fw(X ))} = wTE{XXT }w − 2E{YXT }w + E{Y 2} is strictly convex in w if covariance matrix E{XXT } is positive definite. Similarly, La(w) is strictly convex if E{XXT |A = a} is positive definite.
  LetwGa be the weight vector minimizing the loss associated with group A = a. That is,
  wGa = argmin w La(w). (6)
  Since optimization problem (6) is an unconstrained convex optimization problem,wGa can be found efficiently by the first order condition or the gradient descent. We make the following assumption.
  Assumption 2 We assume that the following holds,
  L0(wG0) ≤ L1(wG0) and L1(wG1) ≤ L0(wG1).
  Algorithm 2: Solving Optimization Problem (3) Input: wG0 ,wG1 , ,γ
  1 wγ = ELminimizer(wG0 ,wG1 , , γ); 2 w−γ = ELminimizer(wG0 ,wG1 , ,−γ); 3 if L(wγ) ≤ L(w−γ) then 4 w∗ = wγ ; 5 end 6 else 7 w∗ = w−γ ; 8 end
  Output: w∗
  Assumption 2 implies that when a group experiences its lowest possible loss, it should not be the disadvantaged group. Under Assumption 2, given wG0 and wG1 , Algorithm 1 with γ = 0 (i.e., function ELminimizer(wG0 ,wG1 , , 0)) finds the optimal 0-EL fair solution, where parameter > 0 specifies the stopping criterion; as → 0, the output approaches to the optimal solution. Intuitively, Algorithm 1 solves non-convex optimization (3) by solving a sequence of convex and constrained optimization problems. If γ > 0, Algorithm 2 finds the optimal predictor under γ-EL using function ELminimizer.
  The convergence of Algorithm 1 for finding the optimal 0-EL fair solution, and convergence of Algorithm 2 for finding the optimal γ-EL fair solution are proved in the following theorems.
  Theorem 3 Consider sequences {λ(i)mid|i = 1, 2, . . .} and {w∗i |i = 1, 2, . . .} generated by Algorithm 1 when γ = 0, i.e., ELminimizer(wG0 ,wG1 , → 0, 0). Under Assumptions 1 and 2, we have,
  lim i→∞
  w∗i = w ∗ and lim i→∞ λ (i) mid = E{L(Y, fw∗(X))}
  where fw∗ is the optimal 0-EL fair predictor.
  Similarly, we can prove the convergence for the approximate EL fairness when γ 6= 0.
  Theorem 4 Assume that L0(wG0) − L1(wG0) < −γ and L0(wG1) − L1(wG1) > γ. Then, as → 0, the output of Algorithm 2 goes to the optimal γ-EL fair solutionw∗.
  Complexity Analysis: The While loop in Algorithm 1 is executed for O(log(1/ )) times. Therefore, Algorithm 1 needs to solve a constrained convex optimization problem for O(log(1/ )) times. Note that constrained convex optimization problems can be efficiently solved via sub-gradient methods (Nedić & Ozdaglar, 2009), brier methods (Wright, 2001), stochastic gradient descent with one projection (Mahdavi et al., 2012), etc. For instance, Nedić & Ozdaglar (2009) introduces a subgradient method that finds the saddle point of the Lagrangian function corresponding to (5) and it converges at the rate ofO(1/k) (k is the number of iterations). Therefore, if is the maximum error tolerance for (5), the total time complexity of Algorithm 2 is O(1/ log(1/ )).
  4 SUB-OPTIMAL FAIR MODEL UNDER γ-EL
  In Section 3, we have shown that non-convex optimization problem (3) can be reduced to a sequence of convex constrained optimizations (5), and based on this we proposed an algorithm (Algorithm 2) that finds the optimal γ-EL fair predictor. However, the proposed algorithm still requires solving a convex constrained optimization in each iteration. In this section, we propose another algorithm which finds a sub-optimal solution to optimization (3) 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 a new weight vector satisfying γ-EL fairness with the two weight vectors found in the first phase. Because of the convexity, two unconstrained convex optimization problems in the first phase can be solved efficiently.
  Phase 1: Unconstrained optimization. In this phase, we remove EL fairness constraint and first solve the following uncontrained optimization problem,
  wO = argmin w L(w) (7)
  Because L(w) is strictly convex inw, 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) is the smallest overall expected loss that is attainable. Let â = argmaxa∈{0,1} La(wO), i.e., group â is the group that is disadvantaged under predictor fwO . Then, for the disadvantaged group â, we findwGâ by solving unconstrained optimization problem (6).
  Phase 2: Binary search to find the fair predictor. For β ∈ [0, 1], we define the followings, g(β) = Lâ ( (1− β)wO + βwGâ ) − L1−â ( (1− β)wO + βwGâ ) ;
  h(β) = L ( (1− β)wO + βwGâ ) ,
  where function g(β) can be interpreted as loss disparity between two demographic group under predictor f(1−β)wO+βwGâ , and h(β) is the corresponding overall expected loss. Some properties of functions g(.) and h(.) are summarized in the following theorem.
  Theorem 5 Under Assumptions 1 and 2, the followings hold,
  1. There exists β0 ∈ [0, 1] such that g(β0) = 0. 2. h(β) is strictly increasing in β ∈ [0, 1]; g(β) is strictly decreasing in β ∈ [0, 1].
  Theorem 5 implies that in a dw dimensional space, if we start fromwO and move towardwGâ along a straight line, the overall loss increases and the disparity between two groups decreases until we reach (1 − β0)wO + β0wGâ , at which 0-EL fairness is satisfied. Note that β0 is the unique root of g. Since g(β) is a strictly decreasing function, β0 can be found using binary search. For the approximate γ-EL fairness, there are multiple values of β such that (1− β)wO + βwGâ satisfies γEL. Since h(β) is strictly increasing in β, among all β that satisfies γ-EL fairness, we would choose the smallest one. The method for finding a sub-optimal solution to optimization (3) is described in Algorithm 3.
  Algorithm 3: Sub-optimal solution to optimization problem (3) 1 Input: wGâ ,wO, , γ 2 Initialization: gγ(β) = g(β)− γ, i = 0, β(0)start = 0, β (0) end = 1 3 if gγ(0) ≤ 0 then 4 w = wO, and go to line 16; 5 end 6 while β(i)end − β (i) start > do 7 β (i) mid = (β (i) start + β (i) end)/2; 8 if gγ(β (i) mid) ≥ 0 then 9 β (i+1) start = β (i) mid, β (i+1) end = β (i) end;
  10 end 11 else 12 β
  (i+1) start = β (i) start, β (i+1) end = β (i) mid;
  13 end 14 end 15 w = (1− β(i)mid)wO + β (i) midwGâ ; 16 Output: w
  Note that while loop in Algorithm 3 is repeated for O(log(1/ )) times. Since the time complexity of operations in each loop isO(1), the total time complexity of Algorithm 3 isO(log(1/ )). We can formally prove that the output returned by Algorithm 3 satisfies γ-EL fairness constraint.
  Theorem 6 Assume that Assumption 1 holds. If gγ(0) ≤ 0, then wO satisfies the γ-EL fairness; if gγ(0) > 0, then limi→∞ β (i) mid = β (∞) mid exists, and (1 − β (∞) mid)wO + β (∞) midwGâ satisfies the γ-EL fairness constraint.
  It is worth mentioning, since h(β) is incrasing, we are intrested in finding the smallest possible β that (1 − β)wO + βwGâ satisfies γ-EL. Here, β (∞) mid is the smallest possible β under which (1 − β)wO + βwGâ satisfies γ-EL.
sections.heading: 5 GENERALIZATION PERFORMANCE
sections.text: So far we proposed algorithms for solving optimization (3). In practice, the joint probability distribution of (X,A, Y ) is often unknown and the expected loss needs to be estimated using the empirical loss. Specifically, given n samples (X i, Ai, Yi), i = 1, . . . , n and predictor fw , the empirical losses of entire population and each group are defined as follows,
  L̂(w) = 1
  n n∑ i=1 l(Yi, fw(X i)); L̂a(w) = 1 na ∑ i:Ai=a l(Yi, fw(X i)), (8)
  where na = |{i|Ai = a}|. Because γ-EL fairness constraint is defined in terms of expected loss, the optimization problem of finding an optimal γ-EL fair predictor using empirical losses is as follows,
  ŵ = argmin w
  L̂(w) s.t. |L̂0(w)− L̂1(w)| ≤ γ̂. (9)
  Note that γ̂ 6= γ and one goal in this section is to find relation between γ̂ and γ. We aim to investigate how to determine γ̂ so that with high probability the predictor found by solving problem (9) satisfies
  γ-EL fairness, and meanwhile ŵ is a good estimate of w∗. To present our result, we make the following assumption.
  Assumption 3 With probability 1− δ, we have the following, sup fw∈F |L(w)− L̂(w)| ≤ B(δ, n,F), where B(δ, n,F) is a bound that goes to zero as n goes to infinity.
  Note that if the class F is learnable with respect to loss function l, then there exists such a bound B(δ, n,F) that goes to zero as n goes to infinity (Shalev-Shwartz & Ben-David, 2014).4
  Theorem 7 Let F be a set of learnable functions, and let fŵ and fw∗ be the solution to (9) and (3) respectively with γ̂ = γ + ∑ a∈{0,1}B(δ, na,F). Then, with probability at least 1 − 6δ the followings hold, L(ŵ)− L(w∗) ≤ 2B(δ, n,F) and |L0(ŵ)− L1(ŵ)| ≤ γ + 2B(δ, n0,F) + 2B(δ, n1,F).
  Theorem 7 shows that as n0, n1 go to infinity, γ̂ → γ, and both empirical loss and expected loss satisfy γ-EL. In addition, as n goes to infinity, the expected loss at ŵ 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.
sections.heading: 6 EXPERIMENTS
sections.heading: 6.1 EXPERIMENT 1: QUADRATIC FUNCTIONS
sections.text: First, we solve optimization problem (3) given the following quadratic functions, L0(w) = (w1 + 5) 2 + (w2 + 2) 2 + (w3 + 1)
  2 + 4w1 · w3, L1(w) = (w1 − 9)2 + (w2 − 9)2 + (w3 − 9)2 + w1 · w2 + w2 · w3 + w1 · w3 + 1, L(w) = L0(w) + L1(w).
  By the first order condition, we obtainwG0 ,wG1 ,wO as follows, wG0 = [1,−2,−3]T , wG1 = [4.5, 4.5, 4.5]T , wO = [24.53, 3.0, 26.53]T We use Algorithm 1 to find the optimal solution to (3) and run Algorithm 3 to find a sub-optimal solution. 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 w
  L1(w) + t ·max{0, (L0(w)− λ(i)mid)} 2, (10)
  where t is the penalty parameter. We solve the optimization problem (10) using gradient descent with learning rate 0.001 and 10000 iterations. We set penalty parameter t = 0.5 and increase t by 0.1 after every 250 iterations. Note that optimization (5) is convex and the penalty method for a constrained convex optimization converges to the optimal solution (Ben-Tal & Zibulevsky, 1997).
  We compare the our algorithms with a baseline: the solution to optimization problem (3) found using the penalty method, i.e., by solving the following unconstrained optimization, min w L0(w) +L1(w) + t · [ max{0, (L0(w)− L1(w)− γ)}2 +max{0, (L1(w)− L0(w)− γ)}2 ] . (11) When solving the optimization problem (11), we use learning rate 0.001. We set penalty parameter t = 0.5 and increase it by 0.1 every 250 iterations. Figure 1a illustrates the overall loss L(w) at the (sub-) optimal points obtained from Algorithms 2 and 3 and the baseline. x-axis represents fairness parameter γ. Since Algorithm 2 converges to the optimal solution, it achieves the smallest loss. Figure 1b 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 γ is sufficiently large (less strict fairness constraint), a sub-optimal solution generated by Algorithm 3 is closer to the optimal solution than the solution found using the baseline method.
  4As an example, if F is a compact subset of linear predictors in Reproducing Kernel Hilbert Space (RKHS) and loss l(y, f(x)) is Lipschitz in f(x) (second argument), then Assumption 3 can be satisfied (Bartlett & Mendelson, 2002). Vast majority of linear predictors such as support vector machine and logistic regression can be defined in RKHS.
sections.heading: 6.2 EXPERIMENT 2: LOGISTIC REGRESSION AND THE ADULT INCOME DATASET
sections.text: The adult income dataset is a public dataset containing the information of 48,842 individuals (Kohavi, 1996). Each data point includes 14 features including age, education, race, etc. Consider race (White or Black) as the sensitive attribute, we denote White demographic group byA = 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 data points. Among these data points, 4585 belong to Black demographic group. For each data point, we convert all the categorical features to one-hot vectors and result in dx = 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 γ-EL to predict whether the income of an individual is above $50K or not.
  We use Algorithm 2 and Algorithm 3 with = 0.01 to find the optimal logistic regression model under EL. We use the penalty method described in equation (11) as the baseline. Similar to Experiment 1, we set learning rate as 0.001 for solving (10) and (11). Penalty parameter t is set to be 0.5 and increases by 0.1 every 250 iterations. Figure 1c illustrates the loss of logistic regression model trained by Algorithm 2, Algorithm 3, and the baseline. It shows that Algorithm 2 outperforms the baseline; this is because that the baseline only finds a sub-optimal solution while Algorithm 2 finds the global optimal solution. As mentioned in Section 4, Algorithm 3 finds a sub-optimal solution that satisfies γ-EL, and its performance can vary from case to case. Even though Algorithm 3 has a good performance in Experiment 1, it does not outperform the baseline in Experiment 2. Figure 1d illustrates the distances from the optimal point w∗ to the sub-optimal solutions obtained by Algorithm 3 and the baseline penalty method. It shows that the distance fromw∗ to the solution obtained under Algorithm 3 is slightly larger than that fromw∗ to the solution obtained under the baseline.
sections.heading: 7 CONCLUSION
sections.text: 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 be the same across different demographic groups. By imposing EL constraint, the learning problem can be formulated as a non-convex optimization 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 a simple algorithm for finding a sub-optimal solution to the non-convex problem without solving constrained convex optimization problems. In addition to the theoretical guarantees, we demonstrated the performance of the proposed algorithm through numerical experiments.
sections.heading: 8 REPRODUCIBILITY STATEMENT
sections.text: 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 hyperparameters (including learning and penalty parameter) have been explicitly mentioned in section 6. In the second numerical example, we used the adult income dataset which is a well-known public dataset in our community. We explained the data pre-processing procedure in Section 6.2 in details.
sections.heading: 9 ETHICS STATEMENT
sections.text: In this work, we proposed algorithms to find fair predictors under the EL fairness notion. We want to emphasize that selecting a 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.
sections.heading: APPENDIX
sections.heading: PROOFS
sections.text: In order to prove Theorem 3, we first introduce two lemmas.
  Lemma 1 Under assumption 2, there exists w ∈ Rdw such that L0(w) = L1(w) = L(w) and λ (1) start ≤ L(w) ≤ λ (1) end.
  Proof. Let h0(β) = L0((1 − β)wG0 + βwG1) and h1(β) = L1((1 − β)wG0 + βwG1), and h(β) = h0(β) − h1(β), β ∈ [0, 1]. Note that ∇wLa(wGa) = 0 because wGa is the minimizer of La(w). Moreover, ∇2wLa(w) is positive semi-definit because La(.) is a strictly convex function. First, we show that L0((1− β)wG0 + βwG1) is an increasing function in β, and L1((1− β)wG0 + βwG1) is a decreasing function in β. Note that h ′ 0(0) = (wG1 − wG0)T∇wL0(wG0) = 0, and h′′0(0) = (wG1 −wG0)T∇2wL0(wG0)(wG1 −wG0) ≥ 0. This implies that h′0(β) ≥ 0,∀β ∈ [0, 1]. Similarly, we can show that h′1(β) ≤ 0,∀β ∈ [0, 1]. Note that under Assumption (2), h(0) < 0 and h(1) > 0. Therefore, by the intermediate value theorem, the exists β ∈ (0, 1) such that h(β) = 0. Definew = (1− β)wG0 + βwG1 . We have,
  h(β) = 0 =⇒ L0(w) = L1(w) = L(w) (12) wG0 is minimizer of L0 =⇒ L(w) = L0(w) ≥ λ (1) start (13)
  h′0(β) ≥ 0,∀β ∈ [0, 1] =⇒ h0(1) ≥ h0(β) =⇒ λ (1) end ≥ L0(w) = L(w) (14)
  Lemma 2 L0(w∗i ) = λ (i) mid, wherew ∗ i is the solution to (5).
  Proof. We proceed by contradiction. Assume that L0(w∗i ) < λ (i) mid. SincewG1 is not in the feasible set of (5),∇wL1(w∗i ) 6= 0. This is a contradiction becausew∗i is an interior point of the feasible set of a convex optimization and cannot be optimal if∇wL1(w∗i ) is equal to zero.
sections.heading: Proof [Theorem 3]
sections.text: Let Ii = [λ (i) start, λ (i) end] be a sequence of intervals. It is easy to see that I1 ⊇ I2 ⊇ · · · and λ (i) end−λ (i) start → 0 as i→∞. Therefore, by the Nested Interval Theorem, ∩∞i=1Ii consists of exactly one real number λ∗, and both λ(i)start and λ (i) end converge to λ ∗. Because λ(i)mid = λ (i) start+λ (i) start 2 , λ (i) mid also converges to λ∗.
  Now, we show that L(w∗) ∈ Ii for all i. Note that L(w∗) = L0(w∗) ≥ λ(1)start because wG0 is the minimizer of L0. Moreover, λ (1) end ≥ L(w∗) otherwise L(w) < L(w∗) (w is defined in Lemma 1) andw∗ is not optimal solution under 0-EL. Therefore, L(w∗) ∈ I1. Now we proceed by induction. Suppose L(w∗) ∈ Ii. We show that L(w∗) ∈ Ii+1 as well. We consider two cases.
  • L(w∗) ≤ λ(i)mid. In this case w∗ is a feasible point for (5), and λ(i) ≤ L(w∗) ≤ λ (i) mid.
  Therefore, L(w∗) ∈ Ii+1.
  • L(w∗) < λ(i)mid. In this case, we proceed by contradiction to show that λ (i) ≥ λ(i)mid.
  Assume that λ(i) < λ(i)mid. Define g(β) = g0(β)−g1(β), where gi(β) = Li((1−β)wG0 + βw∗i ). Note that λ (i) = g1(1) By Lemma 2, g0(1) = λ (i) mid. Therefore, g(1) = λ (i) mid − λ(i) > 0. Moreover, under Assumption 2, g(0) < 0. Therefore, by the intermediate value theorem, there exists β ∈ (0, 1) such that g(β) = 0. Similar to the proof of Lemma 1, we can show that g0(β) in an increasing function for all β ∈ [0, 1]. As a result g0(β) <
  g0(1) = λ (i) mid. Definew = (1− β)wG0 + βw∗i . We have,
  g0(β) = L0(w) = L1(w) = L(w) < λ (i) mid (15)
  L(w∗) < λ (i) mid (16)
  The last two equations imply that w∗ is not an optimal fair solution under 0-EL fairness constraint. This is a contradiction. Therefore, if L(w∗) > λ(i)mid, then λ
  (i) ≥ λ(i)mid. As a result, L(w∗) ∈ Ii+1
  By two above cases and the nested interval theorem, we conclude that,
  L(w∗) ∈ ∩∞i=1Ii, lim i→∞ λ (i) mid = L(w ∗)
  For the second part of the theorem, consider the following,
  w∗∞ = argmin w L1(w)s.t., L0(w) ≤ λ∞mid = L(w∗)
  lim i→∞
  w∗i = w ∗ ∞
  In order to show that w∗∞ is equal to w ∗, we proceed by contradiction. Suppose w∗∞ 6= w∗. As a result, L1(w∗∞) < L(w ∗). Define η(β) = η0(β)− η1(β), where ηi(β) = Li((1− β)wG0 + βw∗∞). Note that L1(w∗∞) = η1(1). By Lemma 2, the condition in (5) is binding and η0(1) = L(w ∗). Therefore, η(1) = L(w∗) − L1(w∗∞) > 0. Moreover, under Assumption 2, η(0) < 0. Therefore, by the intermediate value theorem, there exists β ∈ (0, 1) such that η(β) = 0. Similar to the proof of Lemma 1, we can show that η0(β) is an increasing function for all β ∈ [0, 1]. As a result η0(β) < η0(1) = L(w ∗). Definew = (1− β)wG0 + βw∗∞. We have,
  η0(β) = L0(w) = L1(w) = L(w) < L(w ∗) (17)
  The last equation implies thatw∗ is not an optimal fair solution under 0-EL fairness constraint. This a contradiction. As a result,w∗∞ = ŵ.
sections.heading: Proof [Theorem 4 ]
sections.text: Letw∗ be the optimal weight vector under γ-EL.
  Step 1. we show that one of the following holds,
  L0(w ∗)− L1(w∗) = γ (18) L0(w ∗)− L1(w∗) = −γ (19)
  Proof by contradiction. Assume −γ < L0(w∗) − L1(w∗) < γ. This implies that w∗ is an interior point of the feasible set of optimization problem (3). Since w∗ 6= w∗O, then ∇L(w∗) 6= 0. As a result, object function of (3) can be improved at w∗ by moving toward −∇L(w∗). This a contradiction. Therefore, |L0(w∗)− L1(w∗)| = γ. Step 2. Function wγ = ELminimizer(wG0 ,wG0 , , γ) is the solution to the following optimization problem,
  min w
  Pr{A = 0}L0(w) + Pr{A = 1}L1(w), s.t., L0(w∗)− L1(w∗) = γ (20)
  To show the above claim, notice that the solution to optimization problem (20) is the same as the following,
  min w
  Pr{A = 0}L0(w) + Pr{A = 1}L̃1(w), s.t., L0(w∗)− L̃1(w∗) = 0, (21)
  where L̃1(w) = L1(w) + γ. Since L0(wG0) − L̃1(wG0) < 0 and L0(wG1) − L̃1(wG1) > 0, by Theorem 3, we know thatwγ = ELminimizer(wG0 ,wG0 , , γ) find the solution to (21).
  Lastly, because |L0(w∗)− L1(w∗)| = γ, we have,
  w∗ = { wγ if L(wγ) ≤ L(w−γ) w−γ o.w.
  (22)
  Thus, Algorithm 2 finds the solution to (3).
sections.heading: Proof [Theorem 5]
sections.text: 1. Under Assumption 2, g(1) < 0. Moreover, g(0) ≥ 0. Therefore, by the intermediate value theorem, there exists β0 ∈ [0, 1] such that g(β0) = 0. 2. Since wO is the minimizer of L(w), h′(0) = 0. Moreover, since L(w) is strictly convex, h′′(0) > 0. As a result, h′(β) > 0 for β > 0.
  3. SincewGâ is the minimizer ofLâ(w), andLâ(w) is strictly convex, Lâ((1−β)wO+βwGâ) is strictly decreasing function. Note that since h(β) = Pr{A = â}Lâ((1− β)wO + βwGâ) +Pr{A = 1− â}L1−â((1− β)wO + βwGâ) is strictly increasing and Lâ((1 − β)wO + βwGâ) is strictly decreasing, we conclude that L1−â((1− β)wO + βwGâ) is strictly increasing. As a result, g should be strictly decreasing.
  Proof [Theorem 6] First, we show that if gγ(0) ≤ 0, thenwO satisfies γ-EL.
  gγ(0) ≤ 0 =⇒ g(β)− γ ≤ 0 =⇒ Lâ(wO)− L1−â(wO) ≤ γ
  Moreover, Lâ(wO)−L1−â(wO) ≥ 0 because â = argmaxa La(wO). Therefore, γ-EL is satisfied. Secondly, assume that gγ(0) > 0. Under Assumption 1, gγ(1) = Lâ(wGâ)−L1−â(wGâ)− γ < 0. Therefore, by the intermediate value there exists β0 such that gγ(β0) = 0. Moreover, gγ is a strictly decreasing function. Therefore, the binary search proposed in Algorithm 3 converges to root of gγ(β). As a result, (1 − β(∞)mid)wO + β (∞) midwGâ satisfies satisfies γ-EL. Moreover, Lâ(wO) − L1−â(wO) ≥ 0 because â = argmaxa La(wO). Note that since g(β) is decreasing, β(∞)mid is the smallest possible β under which (1 − β)wO + βwGâ γ-EL. Since h is increasing, the smallest possible β gives us a better accuracy.
sections.heading: Proof [Theorem 7]
sections.text: By the triangle inequality, the following holds,
  sup fw∈F ||L0(w)−L1(w)| − |L̂0(w)− L̂1(w)|| ≤ sup fw∈F |L0(w)− L̂0(w)|+ sup fw∈F |L1(w)− L̂1(w)|. (23) Therefore, with probability at least 1− 2δ we have,
  sup fw∈F
  ||L0(w)− L1(w)| − |L̂0(w)− L̂1(w)|| ≤ B(δ, n0,F) +B(δ, n1,F) (24)
  As a result, with probability 1− 2δ holds,
  {w|fw ∈ F , |L0(w)− L1(w)| ≤ γ} ⊆ {w|fw ∈ F , |L̂0(w)− L̂1(w)| ≤ γ̂} (25) Now consider the following,
  L(ŵ)− L(w∗) = L(ŵ)− L̂(ŵ) + L̂(ŵ)− L̂(w∗) + L̂(w∗)− L(w∗) (26) By (25), L̂(ŵ)− L̂(w∗) ≤ 0 with probability 1−2δ. Thus, with probability at least 1−2δ, we have,
  L(ŵ)− L(w∗) ≤ L(ŵ)− L̂(ŵ) + L̂(w∗)− L(w∗). (27) Therefore, under assumption 3, we can conclude with probability at least 1− 6δ, L(ŵ)− L(w∗) ≤ 2B(δ, n,F). In addition, by (24), with probability at least 1− 2δ, we have,
  |L0(ŵ)− L1(ŵ)| ≤ B(δ, n0,F) +B(δ, n1,F) + |L̂0(w)− L̂1(w)| ≤ γ̂ +B(δ, n0,F) +B(δ, n1,F) = γ + 2B(δ, n0,F) + 2B(δ, n1,F)