Addressing Algorithmic Disparity and Performance Inconsistency in Federated Learning
Year: 2022

Abstract:
Federated learning (FL) has gain growing interests for its capability of learning from distributed data sources collectively without the need of accessing the raw data samples across different sources. So far FL research has mostly focused on improving the performance, how the algorithmic disparity will be impacted for the model learned from FL and the impact of algorithmic disparity on the utility inconsistency are largely unexplored. In this paper, we propose an FL framework to jointly consider performance consistency and algorithmic fairness across different local clients (data sources). We derive our framework from a constrained multiobjective optimization perspective, in which we learn a model satisfying fairness constraints on all clients with consistent performance. Specifically, we treat the algorithm prediction loss at each local client as an objective and maximize the worst-performing client with fairness constraints through optimizing a surrogate maximum function with all objectives involved. A gradient-based procedure is employed to achieve the Pareto optimality of this optimization problem. Theoretical analysis is provided to prove that our method can converge to a Pareto solution that achieves the min-max performance with fairness constraints on all clients. Comprehensive experiments on synthetic and real-world datasets demonstrate the superiority that our approach over baselines and its effectiveness in achieving both fairness and consistency across all local clients.

heading: 1 Introduction
text: Federated learning (FL) [1] refers to the paradigm of learning from fragmented data without sacrificing privacy. FL has aroused broad interests from diverse disciplines including high-stakes scenarios such as loan approvals, criminal justice, healthcare, etc [2]. An increasing concern is whether these FL systems induce disparity in local clients in these cases. For example, ProPublica reported that an algorithm used across the US for predicting a defendant’s risk of future crime produced higher scores to African-Americans than Caucasians on average [3]. This has caused severe concerns from the public on the real deployment of data mining models and made algorithmic fairness an important research theme in recent years.
Existing works on algorithmic fairness in machine learning have mostly focused on individual learning scenarios. There has not been much research on how FL will impact the model fairness at
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
different local clients1. Recently, Du et al. [6] proposed a fairness-aware method, which considered the global fairness of the model learned through a kernel re-weighting mechanism. However, such a mechanism can not guarantee to achieve fairness at local clients in FL scenario, since different clients will have different distributions across protected groups. For example, if we are building a mortality prediction model for COVID-19 patients within a hospital system [7], where each individual hospital can be viewed as a local client. Different hospitals will have different patient populations with distinct demographic compositions including race or gender. In this case, the model fairness at each hospital is important because that’s where the model will be deployed, and it is unlikely that global model fairness can lead to local model fairness.
Due to the potential trade-off between algorithmic fairness and model utility, one aiming to mitigate the algorithmic disparity on local clients can exacerbate the inconsistency of the model performance (i.e., the model performance is different at different local clients). There have been researches [4, 5] trying to address the inconsistency without considering algorithmic fairness. In particular, Mohri et al. [5] proposed an agnostic federated learning (AFL) algorithm that maximizes the performance of the worst performing client. Li et al. [4] proposed a q-Fair Federated Learning (q-FFL) approach to weigh different local clients differently by taking the q-th power of the local empirical loss when constructing the optimization objective of the global model.
In this paper, we consider the problem of enforcing both algorithmic fairness and performance consistency across all local clients in FL. Specifically, suppose we have N local clients, and ui represents the model utility for client i, and gi is the model disparity quantified by some computational fairness metric (e.g., demographic parity [8] or equal opportunity [9]). Following the idea of AFL, we can maximize the utility of the worst-performed client to achieve performance consistency. We also propose to assign each client a "fairness budget" to ensure certain level of local fairness, i.e., gi ≤ i(∀i = 1, 2, · · · , N) with i being a pre-specified fairness budget for client i. Therefore, we can formulate our problem as a constrained multi-objective optimization framework as shown in Figure 1(a), where each local model utility can be viewed as an optimization objective.
Since models with fairness and min-max performance may be not unique, we also require the model to be Pareto optimal. A model is Pareto optimal if and only if the utility of any client cannot be further optimized without degrading some others. A Pareto optimal solution of this problem cannot be achieved by existing linear scalarization methods in federated learning (e.g., federated average, or FedAve in [10]), as the non-i.i.d data distributions across different clients can cause a non-convex Pareto Front of utilities (all Pareto solutions form Pareto Front). Therefore, we propose FCFL, a new federated learning framework to obtain a fair and consistent model for all local clients. Specifically, we first utilize a surrogate maximum function (SMF) that considers the N utilities involved simultaneously instead of the single worst, and then optimize the model to achieve Pareto optimality by controlling the gradient direction without hurting client utilities. Theoretical analysis proves that our method can converge to a fairness-constrained Pareto min-max model and experiments on both synthetic and real-world data sets show that FCFL can achieve a Pareto min-max utility distribution with fairness guarantees in each client. The source codes of FCFL are made publicly available at https://github.com/cuis15/FCFL.

heading: 2 Related Work
text: Algorithm fairness is defined as the disparities in algorithm decisions made across groups formed by protected variables (such as gender and race). Some approaches have been proposed to mathematically define if an algorithm is fair. For example, demographic parity [8] requires the classification results to be independent of the group memberships and equalized opportunity [9] seeks for equal false negative rates across different groups. Besides, there are also recent works focusing on the interpretation of the source of model disparity [11]. Plenty of approaches have been proposed to reduce model disparity. One type of method is to train a classifier first and then post-adjust the prediction by setting different thresholds for different groups [9] or learning a transformation function [12, 13]. Other methods have been developed for optimization of fairness metrics during the model training process through adversarial learning [14, 15, 16, 17, 18] or regularization [19, 20, 21]. Du et al. [6] considered algorithm fairness in the federated learning setting and proposed a regularization method that assigns
1We would like to emphasize that the algorithmic fairness we studied in this paper is not the federated fairness studied in [4] and [5], as their fairness is referring to the performance at different clients, which is consistency.
a reweighing value on each training sample for loss objective and fairness regularization to deal with the global disparity. This method cannot account for the discrepancies among the model disparities at different local clients. In this paper, we propose to treat fairness as a constraint and optimize a multi-objective optimization with multiple fairness constraints for all clients while maximally maintain the model utility.
As we introduced in the introduction, the global consensus model learned from federated learning may have different performances on different clients. There are existing research trying to address such inconsistency issue by maximizing the utility of the worst-performing client. In particular, Li et al. [4] propose q-FFL to obtain a min-max performance of all clients by empirically adjusting the power of the objectives, which cannot always guarantee a more consistent model utility distribution without sufficient searching for appropriate power values. Mohri et al. [5] propose AFL, a min-max optimization scheme which focuses on the single worst client. However, focusing on the single worst objective can cause another client to perform worse, thus we propose to take all objectives into account and optimize a surrogate maximum function to achieve a min-max performance distribution in this paper.
Multi-objective optimization aims to learn a model that gives consideration to all objectives involved. The optimization methods for multi-objective typically involve linear scalarization or its variants, such as those with adaptive weights [22], but it is challenging for these approaches to handling the competing performance among different clients [23]. Martinez et al. [24] proposed a multiobjective optimization framework called Min-Max Pareto Fairness (MMPF) to achieve consistency by inducing a min-max performance of all groups based on convex assumption, which is fairly strong as non-convex objectives are ubiquitous. In this paper, we formulate the problem of achieving both fairness and consistency in federated networks through constrained multi-objective optimization. Previous research on solving this problem has been mostly focusing on gradient-free algorithms such as evolutionary algorithms [25], physics-based and deterministic approaches [26]. Gradient-based methods are still under-explored [27]. We propose a novel gradient-based method FCFL , which searches for the desired gradient direction iteratively by solving constrained Linear Programming (LP) problems to achieve fairness and consistency simultaneously in federated networks.

heading: 3 Problem Setup
text: The problem to be solved in this paper is formally defined in this section. Specifically, we will introduce the algorithmic fairness problem, how to extend existing fairness criteria to federated setting, and the consistency issues of model utility in federated learning.

heading: 3.1 Preliminaries
text: Federated Learning. Suppose there areN local clients c1, c2, ...cN and each client is associated with a specific datasetDk = { Xk, Y k } , k ∈ {1, 2, ..., N}, where the input spaceXk and output space Y k are shared across all N clients. There are nk samples in the k-th client and each sample is denoted as{ xki , y k i } . The goal of the federated learning is to collaboratively learn a global model h with the parameters θ to predict the label Ŷ k as on each client. The classical federated learning aims to minimize the empirical risk over the samples from all clients i.e., minθ 1∑N
k=1 n k
∑N k=1 ∑nk i=1 lk(hθ(x k i ), y k i )
where lk is the loss objective of the k-th client.
Fairness. Fairness refers to the disparities in the algorithm decisions made across different groups formed by the sensitive attribute, such as gender and race. If we denote the dataset on the k-th client as Dk = { Xk, Ak, Y k } , where Ak ∈ A is the binary sensitive attribute, then we can define the multi-client fairness as follows:
Definition 1 (Multi-client fairness (MCF)). A learned model h achieves multi-client fairness if h meets the following condition:
∆Disk(h)− k ≤ 0 ∀k ∈ {1, ., N} (1) where ∆Disk(h) denotes the disparity induced by the model h and k is the given fairness budget of the k-th client. The disparity on the k-th client ∆Disk can be measured by demographic parity
(DP) [8] and Equal Opportunity (EO) [9] as follows:
∆DPk = |P (Ŷ k = 1|Ak = 0)− P (Ŷ k = 1|Ak = 1)| ∆EOk = |P (Ŷ k = 1|Ak = 0, Y k = 1)− P (Ŷ k = 1|Ak = 1, Y k = 1)|
(2)
As data heterogeneity may cause different disparities across all clients, the fairness budgets k in Definition 3.1 specifies the tolerance of model disparity at the k-th client.
Consistency. Due to the discrepancies among data distributions across different clients, the model performance on different clients could be different. Morever, the inconsistency will be magnified when we adjust the model to be fair on local clients. There are existing research trying to improve the model consistency by maximizing the utility of the worst performing client [4, 5]:
min θ max k∈{1,.,N}
1
nk ∑nk i=1 lk(hθ(x k i ), y k i )
where the max is over the losses across all clients.

heading: 3.2 Fair and Consistent Federated Learning (FCFL)
text: Our goal is to learn a model h which 1) satisfies MCF as we defined in Definition 3.1; 2) maintains consistent performances across all clients. We will use ∆DPk defined in Eq.(2) as measurement of disparity in our main text while the same derivations can be developed when adapting other metrics, so we have gk(h(Xk), Ak) = ∆DPk, and gk is the function of calculating model disparity on the k-th client. Similarly, the model utility loss lk(h(Xk), Y k) can be evaluated by different metrics (such as cross-entropy, hinge loss and squared loss, etc). In the rest of this paper we will use lk(h) (gk(h)) for lk(h(Xk), Y k) (gk(h(Xk), Ak)) without causing further confusions. We formulate FCFLas the problem of optimizing the N utility-related objectives {l1(h), l2(h), ..., lN (h)} to achieve Pareto Min-Max performance with N fairness constraints:
min h∈H [l1(h), l2(h), ...lN (h)] s.t. gk(h)− k ≤ 0 ∀k ∈ {1, ., N} . (3) The definitions of Pareto Solution and Pareto Front, which are fundamental concepts in multi-objective optimization, are as follows: Definition 2 (Pareto Solution and Pareto Front). Suppose l(h) = [l1(h), l2(h), ...lN (h)] represents the utility loss vector on N learning tasks with hypothesis h ∈ H, we say h is a Pareto Solution if there is no hypothesis h′ that dominates h: h′ ≺ h, i.e.,
@h′ ∈ H, s.t. ∀i : li(h′) ≤ li(h) and ∃j : lj(h′) < lj(h). All Pareto solutions form Pareto Front P .
From Definition 2, for a given hypothesis set H and the objective vector l(h), the Pareto solution avoids unnecessary harm to client utilities and may not be unique. We prefer a Pareto solution that achieves a higher consistency. Following the work in [4, 5], we want to obtain a Pareto solution h∗ with min-max performance. Figure 1(b) shows the relationships among different model hypothesis sets, and we explain the meanings of different notations therein as follows:
(1)HF is the set of model hypotheses satisfying MCF, i.e., gk(h)− k ≤ 0 ∀k ∈ {1, ., N} , ∀h ∈ HF .
(2)HFU is the set of model hypotheses achieving min-max performance (consistency) with MCF: HFU ⊂ HF and lmax(h′) ≤ lmax(h), ∀h ∈ HF , ∀h′ ∈ HFU . (4)
(3)HFP is the set of model hypotheses achieving Pareto optimality with MCF: HFP ⊂ HF (5a) h′ ⊀ h, ∀h′ ∈ HF , ∀h ∈ HFP (5b)
where Eq.(5a) satisfies ∀h ∈ HFP meets MCF, and Eq.(5b) ensures that ∀h ∈ HFP is a Pareto model with MCF.
(4)H∗ is our desired set of model hypotheses achieving Pareto optimality and min-max performance with MCF:H∗ = HFP ∩HFU .
<latexit sha1_base64="M89WzetrIF5HDjUJN12mHDlNkeU=">AAACyHicjVHLSsNAFD2NrxpfVZdugkVwVRKp6LLgRlxIBVMLtZQkndaheTGZKKW48Qfc6peJf6B/4Z0xBbWITkhy5tx7zsy9109Dnknbfi0Zc/MLi0vlZXNldW19o7K51cqSXATMDZIwEW3fy1jIY+ZKLkPWTgXzIj9kV/7oRMWvbpnIeBJfynHKupE3jPmAB54kyh32zk2zV6naNVsvaxY4BaiiWM2k8oJr9JEgQI4IDDEk4RAeMno6cGAjJa6LCXGCENdxhnuYpM0pi1GGR+yIvkPadQo2pr3yzLQ6oFNCegUpLeyRJqE8QVidZul4rp0V+5v3RHuqu43p7xdeEbESN8T+pZtm/lenapEY4FjXwKmmVDOquqBwyXVX1M2tL1VJckiJU7hPcUE40Mppny2tyXTtqreejr/pTMWqfVDk5nhXt6QBOz/HOQtaBzWnXju8qFcb9WLUZexgF/s0zyM0cIomXPLmeMQTno0zIzXujPFnqlEqNNv4toyHD6YHkE8=</latexit>
<latexit sha1_base64="zEx0Nkzy10T/L74sQQMJuZbQd+4=">AAACxnicjVHLSsNAFD2Nr1pfVZdugkVwVRKp6LLgpsuKthVqKcl0WofmxWSilCL4A27108Q/0L/wzpiCWkQnJDlz7j1n5t7rJ4FIleO8FqyFxaXlleJqaW19Y3OrvL3TTuNMMt5icRDLK99LeSAi3lJCBfwqkdwL/YB3/PGZjnduuUxFHF2qScJ7oTeKxFAwTxF1kfXdfrniVB2z7Hng5qCCfDXj8guuMUAMhgwhOCIowgE8pPR04cJBQlwPU+IkIWHiHPcokTajLE4ZHrFj+o5o183ZiPbaMzVqRqcE9EpS2jggTUx5krA+zTbxzDhr9jfvqfHUd5vQ38+9QmIVboj9SzfL/K9O16IwxKmpQVBNiWF0dSx3yUxX9M3tL1UpckiI03hAcUmYGeWsz7bRpKZ23VvPxN9Mpmb1nuW5Gd71LWnA7s9xzoP2UdWtVY/Pa5V6LR91EXvYxyHN8wR1NNBEi7xHeMQTnq2GFVmZdfeZahVyzS6+LevhAwVHkBg=</latexit>
<latexit sha1_base64="t4Q1d4gpKIXGI7g81ZDcxaM4bhM=">AAACx3icjVHLSsNAFD2Nr1pfVZdugkVwVZJS0WXBje4q2AfUUpLptA1NM2EyKZbiwh9wq38m/oH+hXfGFHwgOiHJmXPvOTP3Xj8Og0Q5zkvOWlpeWV3Lrxc2Nre2d4q7e81EpJLxBhOhkG3fS3gYRLyhAhXydiy5N/FD3vLH5zremnKZBCK6VrOYdyfeMAoGAfOUptJepdArlpyyY5b9E7gZKCFbdVF8xg36EGBIMQFHBEU4hIeEng5cOIiJ62JOnCQUmDjHHQqkTSmLU4ZH7Ji+Q9p1MjaivfZMjJrRKSG9kpQ2jkgjKE8S1qfZJp4aZ83+5j03nvpuM/r7mdeEWIURsX/pFpn/1elaFAY4MzUEVFNsGF0dy1xS0xV9c/tTVYocYuI07lNcEmZGueizbTSJqV331jPxV5OpWb1nWW6KN31LGrD7fZw/QbNSdqvlk6tqqVbNRp3HAQ5xTPM8RQ0XqKNB3iM84BFP1qUlrKl1+5Fq5TLNPr4s6/4dRjGQLQ==</latexit>
<latexit sha1_base64="dDLHTRVsMPSL2VeP70bmxkMMwiQ=">AAACyHicjVHLSsNAFD2NrxpfVZdugkVwVRKp6LLgRlxVMG2hlpJMp3VoXiQTpRQ3/oBb/TLxD/QvvDOmoBbRCUnOnHvPmbn3+kkgMmnbryVjYXFpeaW8aq6tb2xuVbZ3Wlmcp4y7LA7itON7GQ9ExF0pZMA7Scq90A942x+fqXj7lqeZiKMrOUl4L/RGkRgK5kmi3LwvTLNfqdo1Wy9rHjgFqKJYzbjygmsMEIMhRwiOCJJwAA8ZPV04sJEQ18OUuJSQ0HGOe5ikzSmLU4ZH7Ji+I9p1CzaivfLMtJrRKQG9KSktHJAmpryUsDrN0vFcOyv2N++p9lR3m9DfL7xCYiVuiP1LN8v8r07VIjHEqa5BUE2JZlR1rHDJdVfUza0vVUlySIhTeEDxlDDTylmfLa3JdO2qt56Ov+lMxao9K3JzvKtb0oCdn+OcB62jmlOvHV/Wq416Meoy9rCPQ5rnCRo4RxMueQs84gnPxoWRGHfG5DPVKBWaXXxbxsMHB+SQeA==</latexit>
<latexit sha1_base64="qTZzLRS+nptrB0JLYIZj1f7pmKs=">AAACyHicjVHLSsNAFD2NrxpfVZdugkVwVRKp6LLgRlxIBVMLtZQkndaheTGZKKW48Qfc6peJf6B/4Z0xBbWITkhy5tx7zsy9109Dnknbfi0Zc/MLi0vlZXNldW19o7K51cqSXATMDZIwEW3fy1jIY+ZKLkPWTgXzIj9kV/7oRMWvbpnIeBJfynHKupE3jPmAB54kys1756bZq1Ttmq2XNQucAlRRrGZSecE1+kgQIEcEhhiScAgPGT0dOLCREtfFhDhBiOs4wz1M0uaUxSjDI3ZE3yHtOgUb0155Zlod0CkhvYKUFvZIk1CeIKxOs3Q8186K/c17oj3V3cb09wuviFiJG2L/0k0z/6tTtUgMcKxr4FRTqhlVXVC45Lor6ubWl6okOaTEKdynuCAcaOW0z5bWZLp21VtPx990pmLVPihyc7yrW9KAnZ/jnAWtg5pTrx1e1KuNejHqMnawi32a5xEaOEUTLnlzPOIJz8aZkRp3xvgz1SgVmm18W8bDB8d/kF0=</latexit>
<latexit sha1_base64="v+6CtUAUSy3EFDxLCpiiVAVkIpY=">AAACyHicjVHLSsNAFD2NrxpfVZdugkVwVRKp6LLgRlxVMG2hlpKk0zo0LyYTpRQ3/oBb/TLxD/QvvDOmoBbRCUnOnHvPmbn3+mnIM2nbryVjYXFpeaW8aq6tb2xuVbZ3WlmSi4C5QRImouN7GQt5zFzJZcg6qWBe5Ies7Y/PVLx9y0TGk/hKTlLWi7xRzIc88CRR7qjvmGa/UrVrtl7WPHAKUEWxmknlBdcYIEGAHBEYYkjCITxk9HThwEZKXA9T4gQhruMM9zBJm1MWowyP2DF9R7TrFmxMe+WZaXVAp4T0ClJaOCBNQnmCsDrN0vFcOyv2N++p9lR3m9DfL7wiYiVuiP1LN8v8r07VIjHEqa6BU02pZlR1QeGS666om1tfqpLkkBKn8IDignCglbM+W1qT6dpVbz0df9OZilX7oMjN8a5uSQN2fo5zHrSOak69dnxZrzbqxajL2MM+DmmeJ2jgHE245M3xiCc8GxdGatwZk89Uo1RodvFtGQ8fYO2QMg==</latexit>
<latexit sha1_base64="EPqoOzTWfkl9lTQ1ki4TVyrHBRM=">AAACyHicjVHLSsNAFD2NrxpfVZdugkVwVRKp6LLgRlxVMG2hlpKk0zo0LyYTpRQ3/oBb/TLxD/QvvDOmoBbRCUnOnHvPmbn3+mnIM2nbryVjYXFpeaW8aq6tb2xuVbZ3WlmSi4C5QRImouN7GQt5zFzJZcg6qWBe5Ies7Y/PVLx9y0TGk/hKTlLWi7xRzIc88CRR7qh/ZJr9StWu2XpZ88ApQBXFaiaVF1xjgAQBckRgiCEJh/CQ0dOFAxspcT1MiROEuI4z3MMkbU5ZjDI8Ysf0HdGuW7Ax7ZVnptUBnRLSK0hp4YA0CeUJwuo0S8dz7azY37yn2lPdbUJ/v/CKiJW4IfYv3SzzvzpVi8QQp7oGTjWlmlHVBYVLrruibm59qUqSQ0qcwgOKC8KBVs76bGlNpmtXvfV0/E1nKlbtgyI3x7u6JQ3Y+TnOedA6qjn12vFlvdqoF6MuYw/7OKR5nqCBczThkjfHI57wbFwYqXFnTD5TjVKh2cW3ZTx8AGNPkDM=</latexit>
<latexit sha1_base64="CcJBDiOlYKX9h0iduqB/8q3Lf/s=">AAACyHicjVHLSsNAFD2NrxpfVZdugkVwVRKp6LLgRlxVMG2hlpKk0zo0LyYTpRQ3/oBb/TLxD/QvvDOmoBbRCUnOnHvPmbn3+mnIM2nbryVjYXFpeaW8aq6tb2xuVbZ3WlmSi4C5QRImouN7GQt5zFzJZcg6qWBe5Ies7Y/PVLx9y0TGk/hKTlLWi7xRzIc88CRR7qjPTbNfqdo1Wy9rHjgFqKJYzaTygmsMkCBAjggMMSThEB4yerpwYCMlrocpcYIQ13GGe5ikzSmLUYZH7Ji+I9p1CzamvfLMtDqgU0J6BSktHJAmoTxBWJ1m6XiunRX7m/dUe6q7TejvF14RsRI3xP6lm2X+V6dqkRjiVNfAqaZUM6q6oHDJdVfUza0vVUlySIlTeEBxQTjQylmfLa3JdO2qt56Ov+lMxap9UOTmeFe3pAE7P8c5D1pHNadeO76sVxv1YtRl7GEfhzTPEzRwjiZc8uZ4xBOejQsjNe6MyWeqUSo0u/i2jIcP5l2Qag==</latexit>
<latexit sha1_base64="mLNViv2shJumShOVOcz5/d4LTn8=">AAAC8nicjVHLbtNAFD11Cw0pj7Qs2YyIKnURLLsKKstIbLoMEnlIcWTZziQZxS+NZ6pWUb+CXXeILT/QLXwE4g/gL7gzdaXSCNGxbJ85954zc++Ny1RUyvN+bjnbO48e7zaeNPeePnv+orV/MKwKLRM+SIq0kOM4qngqcj5QQqV8XEoeZXHKR/HqvYmPzrisRJF/VBcln2bRIhdzkUSKqLD1JsiicxawIBM5C1I+V8Fah36H6fC447puR4fES7FYquCyGbbanuvZxTaBX4M26tUvWj8QYIYCCTQycORQhFNEqOiZwIeHkrgp1sRJQsLGOS7RJK2mLE4ZEbEr+i5oN6nZnPbGs7LqhE5J6ZWkZDgkTUF5krA5jdm4ts6G/Zf32nqau13QP669MmIVlsT+T3eb+VCdqUVhjne2BkE1lZYx1SW1i7ZdMTdnd6pS5FASZ/CM4pJwYpW3fWZWU9naTW8jG/9lMw1r9kmdq/Hb3JIG7N8f5yYYHrt+1337odvudetRN/AKr3FE8zxBD6foY0Den3CNb/juKOfK+ex8uUl1tmrNS/y1nK9/AOwln7w=</latexit>
<latexit sha1_base64="cOX777D7FIqjtXA2cCRgY9jjdAw=">AAADFnicjVHLbtQwFD0Njz6BAZZsLEaVWLRRUg2CZSU2rEZTiWkr1dUoST2pVeeB7VStRvMf/Ak7dogtO9RFt9D+Ra9NivpQVRwlOT73nGNfO62VNDaKTmaCBw8fPZ6dm19YXHry9Fnn+YtNUzU6E8OsUpXeThMjlCzF0EqrxHatRVKkSmylBx9cfetQaCOr8pM9rsVukeSlHMsssUSNOhvciiM7MaENp4wzXiRHjCsxtnzC8lG8ykVtpCJlvMLCMFzJR322yv6xfcYY1zLft3zqfJ9ZNOp0ozDyg90GcQu6aMeg6vwCxx4qZGhQQKCEJayQwNCzgxgRauJ2MSFOE5K+LjDFAnkbUglSJMQe0Den2U7LljR3mca7M1pF0avJybBMnop0mrBbjfl645Mde1f2xGe6vR3TP22zCmIt9om9z3ep/F+f68VijPe+B0k91Z5x3WVtSuNPxe2cXenKUkJNnMN7VNeEM++8PGfmPcb37s428fUzr3Ssm2ettsG52yVdcHzzOm+DzbUw7oVvN3rd9V571XN4hdd4Q/f5Duv4iAGGlP0Vp/iNP8GX4FvwPfjxVxrMtJ6XuDaCnxdbVq1Z</latexit>
<latexit sha1_base64="pjY/7EbiU9isdHLlRJUuIPlMeiU=">AAAC9nicjVHLSsQwFD3W93vUpZvgILgaWlEUV4IblwqOCo5Im8mMwUxbklRGBr/DnTtx6w+41U8Q/0D/wptYwQeiKW1Pzr3nJPfeJFfS2DB87gv6BwaHhkdGx8YnJqemKzOz+yYrNBd1nqlMHyaxEUqmom6lVeIw1yLuJEocJGdbLn5wLrSRWbpnL3Jx3InbqWxJHluiTipRQ+RGKoKSNVjDiq7tbbBWLHUqjGFJ0WwLy7KUcSVFapm8PKlUw1roF/sJohJUUa6drPKEBprIwFGgA4EUlrBCDEPPESKEyIk7Ro84TUj6uMAlxkhbUJagjJjYM/q2aXdUsintnafxak6nKHo1KRkWSZNRnibsTmM+Xnhnx/7m3fOe7m4X9E9Krw6xFqfE/qX7yPyvztVi0cK6r0FSTblnXHW8dCl8V9zN2aeqLDnkxDncpLgmzL3yo8/Ma4yv3fU29vEXn+lYt+dlboFXd0sacPR9nD/B/nItWqmt7q5UN2vlqEcwjwUs0TzXsIlt7KBO3le4xwMeg25wHdwEt++pQV+pmcOXFdy9ASVCo1I=</latexit>
<latexit sha1_base64="eIoGnVyC7E44h7QsLdGlasrmHP0=">AAAC+nicjVHLSsNAFD3GV31XXboZLELdlFQqiivBjUsFq4KVkkzHOjhNwmQiltovcedO3PoDbvUDxD/Qv/DOGMEHohOSnDn3njNz7w0TJVPj+88D3uDQ8MhoYWx8YnJqeqY4O7efxpnmos5jFevDMEiFkpGoG2mUOEy0CDqhEgfh2ZaNH5wLnco42jPdRBx3gnYkTyQPDFHN4mrWlKzcbspl1mANIy5Mb4NlRippuqzckmkSaILLLI4YV1JEhsk+axZLfsV3i/0E1RyUkK+duPiEBlqIwZGhA4EIhrBCgJSeI1ThIyHuGD3iNCHp4gJ9jJM2oyxBGQGxZ/Rt0+4oZyPaW8/UqTmdoujVpGRYIk1MeZqwPY25eOacLfubd8952rt16R/mXh1iDU6J/Uv3kflfna3F4ATrrgZJNSWOsdXx3CVzXbE3Z5+qMuSQEGdxi+KaMHfKjz4zp0ld7ba3gYu/uEzL2j3PczO82lvSgKvfx/kT7K9UqrXK6m6ttFnJR13AAhZRpnmuYRPb2EGdvK9wjwc8epfetXfj3b6negO5Zh5flnf3BoiRo8E=</latexit>
<latexit sha1_base64="mm6s2JS6dwMK7KPFRjyixAFkcZQ=">AAACznicjVHLSsNAFD2Nr1pfVZdugkVwFRJRdFlw02UF+4C2yGQ6bUPzIpkUSilu/QG3+lniH+hfeGdMQS2iE5KcOfecO3PvdWPfS6VtvxaMldW19Y3iZmlre2d3r7x/0EyjLOGiwSM/StouS4XvhaIhPemLdpwIFri+aLnjaxVvTUSSelF4K6ex6AVsGHoDjzNJVKcbMDnizJ/V5nflim3ZepnLwMlBBfmqR+UXdNFHBI4MAQRCSMI+GFJ6OnBgIyauhxlxCSFPxwXmKJE3I5UgBSN2TN8h7To5G9Je5Uy1m9MpPr0JOU2ckCciXUJYnWbqeKYzK/a33DOdU91tSn83zxUQKzEi9i/fQvlfn6pFYoArXYNHNcWaUdXxPEumu6Jubn6pSlKGmDiF+xRPCHPtXPTZ1J5U1656y3T8TSsVq/Y812Z4V7ekATs/x7kMmmeWc25d3JxXqlY+6iKOcIxTmuclqqihjobu+COe8GzUjYkxN+4/pUYh9xzi2zIePgBzdZPT</latexit>
<latexit sha1_base64="Z8/qr2o4mxqXX7+6cB0bvvs36BA=">AAAC1HicjVHJSsRAEH0Tt3GPevQSHARPISOKHgVBPI7gLDAudNoeDXYWko4g45zEqz/gVb9J/AP9C6vbHnBBtEOS16/eq+6qCjMZFSoIXirOyOjY+ER1cmp6ZnZu3l1YbBVpmXPR5KlM807ICiGjRDRVpKToZLlgcShFO7zc1fH2lciLKE0O1XUmjmN2nkS9iDNF1Kk7fxQzdcGZ7O8PTvp7g1O3FviBWd5PULegBrsaqfuMI5whBUeJGAIJFGEJhoKeLuoIkBF3jD5xOaHIxAUGmCJvSSpBCkbsJX3Pade1bEJ7nbMwbk6nSHpzcnpYJU9KupywPs0z8dJk1uxvufsmp77bNf1DmysmVuGC2L98Q+V/fboWhR62TQ0R1ZQZRlfHbZbSdEXf3PtUlaIMGXEan1E8J8yNc9hnz3gKU7vuLTPxV6PUrN5zqy3xpm9JA65/H+dP0Fr36xv+5sFGbce3o65iGStYo3luYQf7aKBpZv6ARzw5LefGuXXuPqROxXqW8GU59++EI5XI</latexit>
<latexit sha1_base64="Webg+is4hQGFgEoaZWpCj90ZA1I=">AAAC1XicjVHLSsQwFD3W1/iuunRTHARXpSOKLgVBXI7gzAijDmmMWkwfpKkgpTtx6w+41V8S/0D/wptYwQeiKW1Pzr3nJPfeMJNRroPgecgZHhkdG29MTE5Nz8zOufML3TwtFBcdnspUHYYsFzJKREdHWorDTAkWh1L0wssdE+9dCZVHaXKgrzNxHLPzJDqLONNEDVz3KGb6gjNZ7lUn5W67GrjNwA/s8n6CVg2aqFc7dZ9whFOk4CgQQyCBJizBkNPTRwsBMuKOURKnCEU2LlBhkrQFZQnKYMRe0vecdv2aTWhvPHOr5nSKpFeR0sMKaVLKU4TNaZ6NF9bZsL95l9bT3O2a/mHtFROrcUHsX7qPzP/qTC0aZ9iyNURUU2YZUx2vXQrbFXNz71NVmhwy4gw+pbgizK3yo8+e1eS2dtNbZuMvNtOwZs/r3AKv5pY04Nb3cf4E3TW/te5v7K83t/161A0sYRmrNM9NbGMPbXTI+wr3eMCj03Mq58a5fU91hmrNIr4s5+4NbhKWIg==</latexit>
<latexit sha1_base64="lJM0MvPXTTC5tgACn6eeaeEXGxE=">AAAC1XicjVHLSsNAFD3GV31HXboJFsFVSUTRpSBIlxXsA6zKZDqtwbyYTAoSuhO3/oBb/SXxD/QvvDOm4APRCUnOnHvPmbn3+mkYZMp1XyasyanpmdnK3PzC4tLyir261sqSXHLR5EmYyI7PMhEGsWiqQIWik0rBIj8Ubf/6SMfbQyGzIIlP1U0qziM2iIN+wJki6tK2uxFTV5yFRX10URw3R5d21a25Zjk/gVeCKsrVSOxndNFDAo4cEQRiKMIhGDJ6zuDBRUrcOQriJKHAxAVGmCdtTlmCMhix1/Qd0O6sZGPaa8/MqDmdEtIrSelgizQJ5UnC+jTHxHPjrNnfvAvjqe92Q3+/9IqIVbgi9i/dOPO/Ol2LQh8HpoaAakoNo6vjpUtuuqJv7nyqSpFDSpzGPYpLwtwox312jCYzteveMhN/NZma1Xte5uZ407ekAXvfx/kTtHZq3m5t72S3elgrR13BBjaxTfPcxyHqaKBJ3kM84BFPVtsaWbfW3UeqNVFq1vFlWffvefeWJw==</latexit>
<latexit sha1_base64="Webg+is4hQGFgEoaZWpCj90ZA1I=">AAAC1XicjVHLSsQwFD3W1/iuunRTHARXpSOKLgVBXI7gzAijDmmMWkwfpKkgpTtx6w+41V8S/0D/wptYwQeiKW1Pzr3nJPfeMJNRroPgecgZHhkdG29MTE5Nz8zOufML3TwtFBcdnspUHYYsFzJKREdHWorDTAkWh1L0wssdE+9dCZVHaXKgrzNxHLPzJDqLONNEDVz3KGb6gjNZ7lUn5W67GrjNwA/s8n6CVg2aqFc7dZ9whFOk4CgQQyCBJizBkNPTRwsBMuKOURKnCEU2LlBhkrQFZQnKYMRe0vecdv2aTWhvPHOr5nSKpFeR0sMKaVLKU4TNaZ6NF9bZsL95l9bT3O2a/mHtFROrcUHsX7qPzP/qTC0aZ9iyNURUU2YZUx2vXQrbFXNz71NVmhwy4gw+pbgizK3yo8+e1eS2dtNbZuMvNtOwZs/r3AKv5pY04Nb3cf4E3TW/te5v7K83t/161A0sYRmrNM9NbGMPbXTI+wr3eMCj03Mq58a5fU91hmrNIr4s5+4NbhKWIg==</latexit>
<latexit sha1_base64="CMOLEBM7sWO/E6bpLh+ufi3qPiY=">AAAC1HicjVHLSsNAFD3G97vq0k2wCOIipKLosuDGpYKtgtUyGcd2MC+SiVBiV+LWH3Cr3yT+gf6Fd8YpqEV0QpIz555zZ+69QRrKXPn+64gzOjY+MTk1PTM7N7+wWFlabuZJkXHR4EmYZKcBy0UoY9FQUoXiNM0Ei4JQnATX+zp+ciOyXCbxseql4jxinVheSc4UUe3KYitiqstZWB70L8rNfrtS9T3fLHcY1Cyowq7DpPKCFi6RgKNABIEYinAIhpyeM9TgIyXuHCVxGSFp4gJ9zJC3IJUgBSP2mr4d2p1ZNqa9zpkbN6dTQnozcrpYJ09CuoywPs018cJk1uxvuUuTU9+tR//A5oqIVegS+5dvoPyvT9eicIU9U4OkmlLD6Oq4zVKYruibu1+qUpQhJU7jS4pnhLlxDvrsGk9uate9ZSb+ZpSa1XtutQXe9S1pwLWf4xwGzS2vtu3tHG1X654d9RRWsYYNmucu6jjAIRpm5o94wrPTdG6dO+f+U+qMWM8Kvi3n4QNBh5Ws</latexit>
<latexit sha1_base64="mm6s2JS6dwMK7KPFRjyixAFkcZQ=">AAACznicjVHLSsNAFD2Nr1pfVZdugkVwFRJRdFlw02UF+4C2yGQ6bUPzIpkUSilu/QG3+lniH+hfeGdMQS2iE5KcOfecO3PvdWPfS6VtvxaMldW19Y3iZmlre2d3r7x/0EyjLOGiwSM/StouS4XvhaIhPemLdpwIFri+aLnjaxVvTUSSelF4K6ex6AVsGHoDjzNJVKcbMDnizJ/V5nflim3ZepnLwMlBBfmqR+UXdNFHBI4MAQRCSMI+GFJ6OnBgIyauhxlxCSFPxwXmKJE3I5UgBSN2TN8h7To5G9Je5Uy1m9MpPr0JOU2ckCciXUJYnWbqeKYzK/a33DOdU91tSn83zxUQKzEi9i/fQvlfn6pFYoArXYNHNcWaUdXxPEumu6Jubn6pSlKGmDiF+xRPCHPtXPTZ1J5U1656y3T8TSsVq/Y812Z4V7ekATs/x7kMmmeWc25d3JxXqlY+6iKOcIxTmuclqqihjobu+COe8GzUjYkxN+4/pUYh9xzi2zIePgBzdZPT</latexit>
<latexit sha1_base64="Z8/qr2o4mxqXX7+6cB0bvvs36BA=">AAAC1HicjVHJSsRAEH0Tt3GPevQSHARPISOKHgVBPI7gLDAudNoeDXYWko4g45zEqz/gVb9J/AP9C6vbHnBBtEOS16/eq+6qCjMZFSoIXirOyOjY+ER1cmp6ZnZu3l1YbBVpmXPR5KlM807ICiGjRDRVpKToZLlgcShFO7zc1fH2lciLKE0O1XUmjmN2nkS9iDNF1Kk7fxQzdcGZ7O8PTvp7g1O3FviBWd5PULegBrsaqfuMI5whBUeJGAIJFGEJhoKeLuoIkBF3jD5xOaHIxAUGmCJvSSpBCkbsJX3Pade1bEJ7nbMwbk6nSHpzcnpYJU9KupywPs0z8dJk1uxvufsmp77bNf1DmysmVuGC2L98Q+V/fboWhR62TQ0R1ZQZRlfHbZbSdEXf3PtUlaIMGXEan1E8J8yNc9hnz3gKU7vuLTPxV6PUrN5zqy3xpm9JA65/H+dP0Fr36xv+5sFGbce3o65iGStYo3luYQf7aKBpZv6ARzw5LefGuXXuPqROxXqW8GU59++EI5XI</latexit>
<latexit sha1_base64="Webg+is4hQGFgEoaZWpCj90ZA1I=">AAAC1XicjVHLSsQwFD3W1/iuunRTHARXpSOKLgVBXI7gzAijDmmMWkwfpKkgpTtx6w+41V8S/0D/wptYwQeiKW1Pzr3nJPfeMJNRroPgecgZHhkdG29MTE5Nz8zOufML3TwtFBcdnspUHYYsFzJKREdHWorDTAkWh1L0wssdE+9dCZVHaXKgrzNxHLPzJDqLONNEDVz3KGb6gjNZ7lUn5W67GrjNwA/s8n6CVg2aqFc7dZ9whFOk4CgQQyCBJizBkNPTRwsBMuKOURKnCEU2LlBhkrQFZQnKYMRe0vecdv2aTWhvPHOr5nSKpFeR0sMKaVLKU4TNaZ6NF9bZsL95l9bT3O2a/mHtFROrcUHsX7qPzP/qTC0aZ9iyNURUU2YZUx2vXQrbFXNz71NVmhwy4gw+pbgizK3yo8+e1eS2dtNbZuMvNtOwZs/r3AKv5pY04Nb3cf4E3TW/te5v7K83t/161A0sYRmrNM9NbGMPbXTI+wr3eMCj03Mq58a5fU91hmrNIr4s5+4NbhKWIg==</latexit>
<latexit sha1_base64="lJM0MvPXTTC5tgACn6eeaeEXGxE=">AAAC1XicjVHLSsNAFD3GV31HXboJFsFVSUTRpSBIlxXsA6zKZDqtwbyYTAoSuhO3/oBb/SXxD/QvvDOm4APRCUnOnHvPmbn3+mkYZMp1XyasyanpmdnK3PzC4tLyir261sqSXHLR5EmYyI7PMhEGsWiqQIWik0rBIj8Ubf/6SMfbQyGzIIlP1U0qziM2iIN+wJki6tK2uxFTV5yFRX10URw3R5d21a25Zjk/gVeCKsrVSOxndNFDAo4cEQRiKMIhGDJ6zuDBRUrcOQriJKHAxAVGmCdtTlmCMhix1/Qd0O6sZGPaa8/MqDmdEtIrSelgizQJ5UnC+jTHxHPjrNnfvAvjqe92Q3+/9IqIVbgi9i/dOPO/Ol2LQh8HpoaAakoNo6vjpUtuuqJv7nyqSpFDSpzGPYpLwtwox312jCYzteveMhN/NZma1Xte5uZ407ekAXvfx/kTtHZq3m5t72S3elgrR13BBjaxTfPcxyHqaKBJ3kM84BFPVtsaWbfW3UeqNVFq1vFlWffvefeWJw==</latexit>
<latexit sha1_base64="Webg+is4hQGFgEoaZWpCj90ZA1I=">AAAC1XicjVHLSsQwFD3W1/iuunRTHARXpSOKLgVBXI7gzAijDmmMWkwfpKkgpTtx6w+41V8S/0D/wptYwQeiKW1Pzr3nJPfeMJNRroPgecgZHhkdG29MTE5Nz8zOufML3TwtFBcdnspUHYYsFzJKREdHWorDTAkWh1L0wssdE+9dCZVHaXKgrzNxHLPzJDqLONNEDVz3KGb6gjNZ7lUn5W67GrjNwA/s8n6CVg2aqFc7dZ9whFOk4CgQQyCBJizBkNPTRwsBMuKOURKnCEU2LlBhkrQFZQnKYMRe0vecdv2aTWhvPHOr5nSKpFeR0sMKaVLKU4TNaZ6NF9bZsL95l9bT3O2a/mHtFROrcUHsX7qPzP/qTC0aZ9iyNURUU2YZUx2vXQrbFXNz71NVmhwy4gw+pbgizK3yo8+e1eS2dtNbZuMvNtOwZs/r3AKv5pY04Nb3cf4E3TW/te5v7K83t/161A0sYRmrNM9NbGMPbXTI+wr3eMCj03Mq58a5fU91hmrNIr4s5+4NbhKWIg==</latexit>
<latexit sha1_base64="CMOLEBM7sWO/E6bpLh+ufi3qPiY=">AAAC1HicjVHLSsNAFD3G97vq0k2wCOIipKLosuDGpYKtgtUyGcd2MC+SiVBiV+LWH3Cr3yT+gf6Fd8YpqEV0QpIz555zZ+69QRrKXPn+64gzOjY+MTk1PTM7N7+wWFlabuZJkXHR4EmYZKcBy0UoY9FQUoXiNM0Ei4JQnATX+zp+ciOyXCbxseql4jxinVheSc4UUe3KYitiqstZWB70L8rNfrtS9T3fLHcY1Cyowq7DpPKCFi6RgKNABIEYinAIhpyeM9TgIyXuHCVxGSFp4gJ9zJC3IJUgBSP2mr4d2p1ZNqa9zpkbN6dTQnozcrpYJ09CuoywPs018cJk1uxvuUuTU9+tR//A5oqIVegS+5dvoPyvT9eicIU9U4OkmlLD6Oq4zVKYruibu1+qUpQhJU7jS4pnhLlxDvrsGk9uate9ZSb+ZpSa1XtutQXe9S1pwLWf4xwGzS2vtu3tHG1X654d9RRWsYYNmucu6jjAIRpm5o94wrPTdG6dO+f+U+qMWM8Kvi3n4QNBh5Ws</latexit>
<latexit sha1_base64="nTufuzHXRMcLVyVBtlbkNIetpR4=">AAACyHicjVHLSsNAFD2Nr1pfVZdugkVwVZJS0WXBjbiqYNpCfZBMp+3QvEgmSind+ANu9cvEP9C/8M6YglpEJyQ5c+49Z+be68W+SKVlvRaMhcWl5ZXiamltfWNzq7y900qjLGHcYZEfJR3PTbkvQu5IIX3eiRPuBp7P297oVMXbdzxJRRReynHMrwN3EIq+YK4kyhneTKzpbbliVS29zHlg56CCfDWj8guu0EMEhgwBOEJIwj5cpPR0YcNCTNw1JsQlhISOc0xRIm1GWZwyXGJH9B3QrpuzIe2VZ6rVjE7x6U1IaeKANBHlJYTVaaaOZ9pZsb95T7SnutuY/l7uFRArMST2L90s8786VYtEHye6BkE1xZpR1bHcJdNdUTc3v1QlySEmTuEexRPCTCtnfTa1JtW1q966Ov6mMxWr9izPzfCubkkDtn+Ocx60alW7Xj26qFcatXzURexhH4c0z2M0cIYmHPIWeMQTno1zIzbujfFnqlHINbv4toyHD3xMkRM=</latexit>
<latexit sha1_base64="nTufuzHXRMcLVyVBtlbkNIetpR4=">AAACyHicjVHLSsNAFD2Nr1pfVZdugkVwVZJS0WXBjbiqYNpCfZBMp+3QvEgmSind+ANu9cvEP9C/8M6YglpEJyQ5c+49Z+be68W+SKVlvRaMhcWl5ZXiamltfWNzq7y900qjLGHcYZEfJR3PTbkvQu5IIX3eiRPuBp7P297oVMXbdzxJRRReynHMrwN3EIq+YK4kyhneTKzpbbliVS29zHlg56CCfDWj8guu0EMEhgwBOEJIwj5cpPR0YcNCTNw1JsQlhISOc0xRIm1GWZwyXGJH9B3QrpuzIe2VZ6rVjE7x6U1IaeKANBHlJYTVaaaOZ9pZsb95T7SnutuY/l7uFRArMST2L90s8786VYtEHye6BkE1xZpR1bHcJdNdUTc3v1QlySEmTuEexRPCTCtnfTa1JtW1q966Ov6mMxWr9izPzfCubkkDtn+Ocx60alW7Xj26qFcatXzURexhH4c0z2M0cIYmHPIWeMQTno1zIzbujfFnqlHINbv4toyHD3xMkRM=</latexit>
Theorem 1. (proof in Appendix) The hypothesis setH∗ is non-empty, i.e.,
∃h ∈ H, h ∈ H∗. (6)
In summary, from Theorem 1, our goal is to obtain a fair and consistent model h∗ ∈ H∗ to achieve Pareto optimality and min-max performance with MCF.

heading: 4 Fairness-Constrained Min-Max Pareto Optimization

heading: 4.1 Preliminary: Gradient-based Multi-Objective Optimization
text: Pareto solutions of the multi-objective optimization problem can be reached by gradient descent procedures. Specifically, given the initial hypothesis h with parameter θ0 ∈ Rn, we optimize hθt by moving to a specific gradient direction d with a step size η: θt+1 = θt + ηd. d is a descent direction if it decreases the objectives (li(hθt+1) ≤ li(hθt), ∀i). Suppose ∇θli is the gradient of the i-th objective li with respect to the parameter θ, if we select d∗ which satisfies d∗T∇θli ≤ 0 for all i, d∗ is a descent direction and li(hθt) decreases after the t+ 1 iteration.
If we directly search for the descent direction d to achieve dT∇θli ≤ 0,∀i, the computation cost can be tremendous when d is a high-dimensional vector. Désidéri et al. [28] proposed to find a descent direction d in the convex hull of the gradients of all objectives denoted as G = [∇θl1,∇θl2, ...∇θlN ] by searching for a N -dimension vector α∗ (typically N n in deep model), which is formulated as follows:
d = α∗TG ∈ G where G = {∑N
i=1 αi∇θli | αj ≥ 0 ∀j and ∑N j=1 αj = 1 } . (7)

heading: 4.2 Overview of the Optimization Framework
text: To obtain a fair Pareto min-max model, there are two optimization paths shown in Figure 1(c). The gray dotted line denotes the optimization path where we first achieve Pareto optimality with MCF, then we try to achieve min-max performance while keeping Pareto optimality. However, it’s hard to adjust a Pareto model to another [23]. Therefore, we propose to first achieve min-max performance with MCF then achieve Pareto optimality as the black solid line in Figure 1(c). In particular, we propose a two-stage optimization method for this constrained multi-objective problem: 1) constrained min-max optimization to achieve a fair min-max model; 2) constrained Pareto optimization to continue to optimize the model to achieve Pareto optimality while keeping min-max performance with MCF.
Constrained Min-Max Optimization We define a constrained min-max optimization problem on the hypothesis setH:
min h∈H lmax(h)
lmax(h) = max (li(h)) i ∈ {1, ., N} s.t. g′max(h) ≤ 0
g′max(h) = max (g ′ i(h)) = max (gi(h)− i) i ∈ {1, ., N}
(8)
where i is the given fairness budget on the i-th client. By optimizing the constrained objective in Eq.(8), we obtain a model h1 ∈ HFU that 1) h1 satisfies MCF; 2) h1 achieves the optimal utility on the worst performing client.
Constrained Pareto Optimization Caring only about the utility of the worst-performing client can lead to unnecessary harm to other clients since the rest objectives can be further optimized. Therefore, we then continue to optimize h1 ∈ HFU to achieve Pareto optimality:
min h∈H
1
N ∑N i=1 li(h) (9a)
s.t. li(h) ≤ li(h1) ∀i ∈ {1, ., N} (9b) g′max(h) ≤ 0 (9c) g′max(h) = max (g ′ i(h)) = max (gi(h)− i) i ∈ {1, ., N} (9d)
where we optimize h without hurting the model utility on any client so that the converged Pareto model h∗ of Eq.(9) satisfies lmax(h∗) ≤ lmax(h1). Morever, h∗ satisfies MCF as the constraint in Eq.(9c), so h∗ ∈ H∗ is a Pareto min-max model with N fairness constraints on all clients.

heading: 4.3 Achieving Min-Max Performance with MCF
text: Minimizing the current maximum value of all objectives directly in Eq.(8) can cause another worse objective and can be computationally hard when faced with a tremendous amount of clients. We will use lm(h) (g′m(h)) to denote lmax(h) (g ′ max(h)) without causing further confusions for expression simplicity. We propose to use a smooth surrogate maximum function (SMF) [29] to approximate an upper bound of lm(h) and gm(h) as follows:
l̂m(h, δl) = δl ln ∑N
i=1 exp
( li(h)
δl
) , ĝ′m(h, δg) = δg ln ∑N i=1 exp ( g′i(h) δg ) , (δg, δl > 0).
(10) It is obvious that lm(h) ≤ l̂m(h, δl) ≤ lm(h) + δm ln(N) and limδl→0+ l̂m(h(x), δl) = lm(h). For ĝ′m(h, δg), we can get a similar conclusion. The objective in Eq.(8) is approximated as follows:
min h∈H l̂m(h, δl) (11a)
s.t. ĝ′m(h, δg) ≤ 0. (11b)
Property 1. There always exists an initial trivial model which satisfies the MCF criterion by treating all samples equally (e.g., h(x) = 1,∀x).
From Property 1, we can always initialize h to satisfy ĝ′m(h, δg) ≤ 0 in Eq.(11b). Then we optimize the upper bound of lm(h) when ensuring MCF. As the hypothesis h owns the parameter θ, we use ∇θ l̂ and∇θĝ′ to represent the gradient ∇θ l̂m(hθ, δl) and∇θĝ′m(hθ, δg), respectively. We propose to search for a descent direction d for Eq.(11) in the convex hull of G = [∇θ l̂,∇θĝ′] in two cases where d is defined in Eq.(7). For the t-th iteration: (1) if hθt satisfies the fairness constraint defined in Eq.(11b), we focus on the descent of l̂m(hθt , δtl ):
min d∈G
dT∇θt l̂ if ĝ′m(hθt , δtg) ≤ 0, (12)
(2) if hθt violates the fairness constraint, we aim to the descent of ĝ′m(hθt , δtg) without causing the ascent of l̂m(hθt , δtl ) :
min d∈G
dT∇θt ĝ′, s.t. dT∇θt l̂ ≤ 0. (13a)
If the obtained gradient d satisfies ||d||2 ≤ d, we decrease the parameter δtl , δtg as: δt+1l = β · δtl , δt+1g = β · δtg if ||d||2 ≤ d δt+1l = δ t l , δ t+1 g = δ t g otherwise,
(14)
where β is the decay ratio that 0 < β < 1. From Eq.(14), we narrow the gap between l̂m(h, δl) and lmax(h) by decreasing the parameter δl as every time the algorithm approaches convergence. From Eq.(12) and Eq.(13), we optimize either l̂m or ĝ′m and keep l̂m without ascent in each iteration.
4.4 Achieving Pareto Optimality and Min-Max Performance with MCF
As the model h1θ ∈ HFU obtained from constrained min-max optimization cannot guarantee Pareto optimality, we continue to optimize h1θ to be a Pareto model without causing the utility descent on any client. We propose a constrained linear scalarization objective to reach a Pareto model and the t-th iteration is formulated as follows:
min d∈G
1
N N∑ i=1 dT∇θt li (15a)
s.t. dT∇θt li ≤ 0 ∀i ∈ {1, ., N} (15b) dT∇θt ĝ′m ≤ 0, (15c)
where G = [∇θl1,∇θl2, ...∇θlN ,∇θg1,∇θg2, ...,∇θgN ] and G is the convex hull of G. The nonpositive angle of d with each gradient∇θt li ensures that all objective values decrease. Similarly, if we aim to reach the Pareto solution without causing utility descent only on the worst performing client, the constraint in Eq.(15b) is replaced by dT∇θt l̂ ≤ 0. Different from constrained min-max optimization in Section 4.3 where the objective to be optimized in each iteration depends on whether ĝm(hθt , δtg) ≤ 0, in constrained Pareto optimization procedure, as we have achieved MCF, we optimize the objective in Eq.(15) for a dominate model in each iteration. Specifically, we restrict ĝ′m ≤ 0 to keep fairness on each client given the reached hypothesis h1 ∈ HFU . Meanwhile, we constrain li(h) to descend or remain unchanged until any objective cannot be further minimized. Algorithm 1 in Appendix shows all steps of our method. The convergence analysis and the time complexity analysis of our framework are in Appendix. Moreover, we also present our discussion about the fairness budget in Appendix.

heading: 5 Experiments
text: We intuitively demonstrate the behavior of our method by conducting experiments on synthetic data. For the experiments on two real-world federated datasets with fairness issues, we select two different settings to verify the effectiveness of our method: (1) assign equal fairness budgets for all local clients; (2) assign client-specific fairness budgets. More experimental results and detailed implementation are in Appendix.

heading: 5.1 Experimental Setup
text: Federated Datasets (1) Synthetic dataset: following the setting in [30, 23], the synthetic data is from two given non-convex objectives; (2) UCI Adult dataset [5]: Adult contains more than 40000 adult records and the task is to predict whether an individual earns more than 50K/year given other features. Following the federated setting in [4, 5], we split the dataset into two clients. One is PhD client in which all individuals are PhDs and the other is non-PhD client. In our experiments, we select race and gender as sensitive attributes, respectively. (3)eICU dataset: We select [31], a clinical dataset collecting patients about their admissions to ICUs with hospital information. Each instance
is a specific ICU stay. We follow the data preprocessing procedure in [32] and naturally treat 11 hospitals as 11 local clients in federated networks. We conduct the task of predicting the prolonged length of stay (whether the ICU stay is longer than 1 week, ) and select race as the sensitive attribute.
Evaluation Metrics (1) Utility metric: we use accuracy to measure the model utility in our experiments; (2) Disparity metrics: our method is compatible with various of fairness metrics. In our experiments, we select two metrics (marginal-based metric Demographic Parity [8] and conditionalbased metric Equal Opportunity [9] (The results of Equal Opportunity are in the Appendix) to measure the disparities defined in Eq.(2); (3) Consistency: following the work [4, 5], we use the utility on the worst-performing client to measure consistency.
Baselines As we do not find prior works proposed for achieving fairness in each client, we select FA [6], MMPF [24] and build FedAve+FairReg as baselines in our experiments. For all baselines, we try to train the models to achieve the optimal utility with fairness constraints. If the model cannot satisfy the fairness constraints, we keep the minimum of disparities with reasonable utilities. (1) MMPF [24], Martinez et al. develop MMPF which optimizes all objectives on convex assumption to induce a min-max utility of all groups; (2) FA [6], Du et al. propose FA, a kernel-based model-agnostic method with regularizations for addressing fairness problem on a new unknown client instead of all involved clients; (3) FedAve+FairReg, we build FedAve+FairReg, which optimizes the linear scalarized objective with the fairness regularizations of all clients.

heading: 5.2 Experiments on Synthetic Dataset
text: Non-convex Pareto Front means that linear scalarization methods (e.g., FedAve) miss any solution in the concave part of the Pareto Front. In this experiment, we optimize l1 under the constraint l2 ≤
, ∈ {0.2, 0.4, 0.6, 0.8}. Considering the effect of the initialization in our experiment, we conduct experiments when the initialization θ0 satisfies the constraints and violates the constraints.
From the results in Figure 2, when the initialization θ0 violates the constraints in Figure 2(a), the objective l2 decreases in each step until it satisfies the constraint and finally FCFL reaches the constrained optimal l1(h∗). As the initialization θ0 satisfies the constraints in Figure 2(b), our method focuses on optimizing l1 until it achieves the optimal l1(h∗) with the constraint l2 ≤ .

heading: 5.3 Experiments on Real-world Datasets with Equal Fairness Budgets

heading: 5.3.1 Income Prediction on Adult Dataset
text: We show the results with the sensitive attribute being race in our main text and the results when gender is the sensitive attribute are in Appendix. We set the fairness budgets defined in Eq.(1) in two different cases, (1) looser constraint: ∆DPi ≤ i = 0.05 ∀i ∈ {1, ., N}; (2) stricter constraint: ∆DPi ≤ i = 0.01 ∀i ∈ {1, ., N}. From Figure 3, FCFL achieves min-max performance on PhD client in the two cases with MCF. MMPF fails to achieve MCF as i = 0.05. FA and FedAve+FairReg achieve MCF with i = 0.05 but violate fairness constraint as i = 0.01. From Figure 3, our method achieves a comparable performance on non-PhD client compared to baselines.

heading: 5.3.2 Prolonged Length of Stay Prediction on eICU Dataset
text: The length of the patient’s hospitalization is critical for the arrangement of the medical institutions as it is related to the allocation of limited ICU resources. We conduct experiments on the prediction of prolonged length of stay(whether the ICU stay is longer than 1 week) on eICU dataset. We use race as sensitive attribute and set the fairness budgets defined in Eq.(1) in two cases: (1) looser constraint: ∆DPi ≤ i = 0.1 ∀i ∈ {1, ., N}; (2) stricter constraint: ∆DPi ≤ i = 0.05 ∀i ∈ {1, ., N}
From Figure 4, our method achieves min-max performance with fairness budget = 0.1 compared to the baselines. When we constrain ∆DPi ≤ 0.05 ∀i, all baselines fail to satisfy the constraints and the disparities are about 0.1 while our method significantly decreases the disparities and the maximum of the disparities is 0.68. Besides, we maintain comparable utilities on all clients compared to baselines.

heading: 5.4 Experiments with Client-Specific Fairness Budgets
text: Data heterogeneity encourages the different levels of the disparities on different clients. Consistent fairness budgets can cause unexpected hurt on some specific clients with severe disparities. We explore the performance of our method given client-specific fairness budgets. Specifically, we firstly conduct unconstrained min-max experiments and measure the original disparities ∆DP = [∆DP1, .,∆DPN ] on all clients, then we constrain the model disparities based on the original disparities of all clients, i.e., [ 1, 2, ., N ] = w ·∆DP , w ∈ {1.0, 0.9, 0.8, ., 0.2}.
From Figure 5(a) and Figure 5(b), we show the effect of the client-specific fairness budgets on model disparities and utilities. The decreasing w means the stricter constraints on both clients and FCFL reduces the disparities significantly as shown in Figure 5(a). With the stricter client-specific constraints on both clients, the utilities on both clients decrease slightly as shown in Figure 5(b),
which implies that FCFL achieves a great balance between the fairness and the utility of all clients. FCFL is compatible with client-specific fairness budgets which enhances its flexibility and avoids severe hurt to the specific clients.
The results of LoS prediction task with client-specific fairness budgets are shown in Figure 5(c) and Figure 5(d). As w decreases from 1.0 to 0.2, the maximum of all client disparities in Figure 5(c) decrease from 0.2 to 0.05 which means the model becomes fairer on all clients. Figure 5(d) shows the minimum of the utilities which slightly decreases from 0.62 to 0.6 and our method achieves an acceptable trade-off between model fairness and utility as the amount of clients increases in this task.

heading: 6 Conclusion
text: In this paper, we investigate the consistency and fairness issues in federated networks as the learned model deployed on local clients can cause inconsistent performances and disparities without elaborate design. We propose a novel method called FCFL to overcome the disparity and inconsistency concerns in the favored direction of gradient-based constrained multi-objective optimization. Comprehensive empirical evaluation results measured by quantitative metrics demonstrate the effectiveness, superiority, and reliability of our proposed method.

heading: Acknowledgments
text: Sen Cui, Weishen Pan and Changshui Zhang would like to acknowledge the funding by the National Key Research and Development Program of China (No. 2018AAA0100701). Fei Wang acknowledges the support from AWS Machine Learning for Research Award and Google Faculty Research Award.

Review summaries:
This paper first introduces a new task about federated learning in which fairness and consistency are jointly considered, then proposes a solution named FCFL to solve the problem. After introducing fairness, the problem is transferred to a min-max optimization problem, and the two-stage optimization algorithm works well on it. The main contributions are as follows:  1) Introduce a new task which jointly considers model fairness and consistency in federated learning, 2) Propose an optimization method called FCFL to address the problem, 3) Conduct experiments on a synthetic dataset and two public datasets and compare the proposed algorithm with three baseline methods, and show that the proposed method outperforms the rest.

This paper proposes a federated learning algorithm which is fair and gives consistent performance across different clients in the following sense.  To achieve fairness, some measure of disparity is considered and enforced as a constraint for each client (i.e. each client has an upper bound on how high the disparity measure can go).  To achieve consistency, the objective is to find model parameters that minimize the maximum loss incurred across the clients.  This contrasts with prior work which does not directly address the fairness locally at each client.  Compared to [21], this paper adds constraints on a disparity measure for each client, in addition to the min-max objective.  Compared to [6], this paper considers a fairness constraint at each client as opposed to a single, global fairness constraint.  The proposed gradient descent-based algorithm first aims to satisfy the fairness constraints, and then it aims to find a Pareto optimal solution (w.r.t the clients’ utilities) while continuing to satisfy the fairness constraints.  The proposed algorithm replaces the (non-smooth) max’s in the problem formulation with a smooth surrogate, which is basically the log-sum-exp trick.  The proposed method is evaluated on three datasets with respect to prediction accuracy as the loss/utility metric and two different fairness metrics: demographic parity and equal opportunity.  The results show that the proposed method typically performs significantly better with respect to the fairness measure, with a small loss in accuracy compared to other methods which do not achieve the same level of fairness. 

The paper studies how to solve the model fairness and performance consistency among clients in federated learning. There exist work on model fairness and performance inconsistency separately as mentioned in the paper and the contribution of this work is to provide a FL framework which considers both effects. The problem is formulated as a constrained min-max pareto optimization problem. The authors use a two-stage optimization method to approximate the optimal solution.