Proportional Fairness in Federated Learning
Authors: Guojun Zhang
Saber Malekmohammadi
Xi Chen
Yaoliang Yu
Venue: Accepted by TMLR ()

Abstract: With the increasingly broad deployment of federated learning (FL) systems in the real world, it is critical but challenging to ensure fairness in FL, i.e. reasonably satisfactory performances for each of the numerous diverse clients. In this work, we introduce and study a new fairness notion in FL, called proportional fairness (PF), which is based on the relative change of each client's performance. From its connection with the bargaining games, we propose PropFair, a novel and easy-to-implement algorithm for finding proportionally fair solutions in FL, and study its convergence properties. Through extensive experiments on vision and language datasets, we demonstrate that PropFair can approximately find PF solutions, and it achieves a good balance between the average performances of all clients and of the worst 10% clients.

Published in Transactions on Machine Learning Research (01/2023)
Proportional Fairness in Federated Learning
Guojun Zhang, Saber Malckmohammadi, Xi Chen (guojun.shone maberrmalemmmhammadd zi. zi.chen4) Saaaww/i.hwweemco Huawei Noah Ark Lab
Yaoliang Yu
yaoliang. yo wuswaterrooo.cr University of Waterloo
Reviewed on OpenReview: https: // openreview. net/forun? id=ryUHgEawoQ
Abstract
With the increasingly broad deployment of federated learning (FL) systems in the real world, it critical but challenging to ensure fairness in FL, i.c. reasonably satisfactory performances for each of the numerous diverse clients. In this work, we introduce and study new fairness notion in FL, called proportional fairness (PF), which is based on the relative change of each client's performance. From its connection with the bargaining games, we propose PropFair, a novel and casy-to-implement algorithm for finding proportionally fair solutions in FL, and study its convergence properties. Through exlensive experiments on vision and language datasets, we demonstrate that PropFair can approximately find PF solutions, and achicves good balance between the average performances of all clients and of the worst 10% clients. Our code is available https:///ithub con/huawei-noall httpaeee--eeeaeinneeeeeeaeaaaaaa
1 Introduction
Federated learning (FL, McMahan et al. 2017) has attracted an intensive amount of attention in recent years, due to its great potential in real world applications such as IoT devices (Imteaj et al., 2021). healthcare (Xu et al., 2021) and finance (Long et al., 2020). In FL, different clients collaboratively learn global model that presumably benefits all, without sharing the local data.
However, clients differ. Due the heterogeneity of client objectives and resources, the benefit each client receives may vary. How can we make sure each client is treated fairly in FL?
To answer this question, we first need to define what mean by fairness. Similar to fairness in other fields (Jain et al., 1984; Sen, 1986; Rawls, 1999; Barocas et al., 2017), in FL., there is unified definition of fairness. In social choice theory, two of the most popular definitions are ufilitarianism and egalitarianism. The goal of utilitarian fairness is to maximize the utility of the total society; while egalitarian fairness requires the worst-off people to receive enough benefits. Coincidentally, they correspond two of the fair FL algorithms: Fedcrated Averaging (FedAvg, McMahan et al. 2017) and Agnostic Federated Learning (AFL, Mohri et al. 2019). In FedAvg (AFL), we minimize the averaged (worst-case) loss function, respectively. Utilitarian and egalitarian might be in conflict with each other: one could improve the worst-case clients, but better-off clients would be degraded to a large extent.
To achieve some balance between utilitarian and egalitarian fairness, other notions of fairness have been studied. Inspired by a-fairness from telecommunication (Mo Walrand, 2000), Li et al. (2020c) proposed F-aair Federated Learning FF-F.... By replacing the client weights with the softmax function of the client Josses, Li et al. (2020a) proposed Tilted Empirical Risk Minimization what type of balance these algorithms trying to yield.
CeaaaaiioonTTRR (TERM). However, it remains vague

---

Published in Transactions on Machine Learning Research (01/2023)
In this work, we bring another fairness notion into the zoo of fair FL, called proportional fairness (PF, Kelly 1997). It also balances between utilitarian and egalitarian fairness, but is more intuitive. As a illustrative example, suppose we only have two clients and if we can improve the performance of one client relatively by 2% while decreasing another one by 1,, then the solution more proportionally fair. In practice, this view of relative change quotidian. In slock market, people care more about how much they gain/lose compared to the cost; in telecommunication, people worry about the data transmission speed compared to the bandwidth. In word, PF studies the relative change of each client, rather than the absolute change.
Under convexity, PF is equivalent to the Nash bargaining solution (NBS, Nash 1950), well-known concept from cooperative game theory. Based on the notion of PF and its related NBS, we propose new FI a algorithm called PropFair. Our contributions are the following:
With the utility perspective and Nash bargaining solutions, we propose a surrogate loss for achieving proportionally fair FL. This provides new insights to fair FL and is distinct from existing literature which uses the loss perspective for fairness (sce Scction 2).
Theorelical guarantee: we prove the convergence of PropFair to a stationary point of our objec- tive, under mild assumptions. This proof can generalize to any other FL algorithm in the unified framework we propose.
Empirioal viability: we test our algorithm on several popular vision and language datasets, and modern neural architectures. Our results show that PropFair not only approximately obtains pro- portionally fair FL solutions, but also allains more favorable balance between the averaged and worst-case performances.
Compared to previous works (Mohri et al., 2019; Li al., 2020c; 2021), we provide a comprehensive benchmark for popular fair FL algorithms with systematic hyperparameter tuning. This could facilitate future fairness research in FL.
Note that we mainly focus on fairness in federated learning. Perhaps more widely known and orthogonal to fair FL, fairness has also been studied in general machine learning (Appendix F.3.3), such demographic parity (Dwork et al., 2012), equalized odds (Hardt et al., 2016) and calibration (Gebel, 2009). These definitions require knowledge of sensitive attributes and true labels. Although it is possible to adapt these fairness definitions into FL, by e.g,, treating each sensitive attribute as a client, the adaplation may not always be straightforward due to the unique challenge of privacy in FL. Such adaptation can be interesting future work and we do not consider it here.
Notations. We use O to denote the model parameters, and {(O, (x, v)) represent. the prediction loss of 0 on the sample (x, y). Es denotes the average prediction loss on batch S. For each client i, the data distribution is D; and the expected loss of O on D; is f.. We denote f = (f1,.... fn) with the number of clients, and use Pt as the linear weight of client i. Usually, we choose = n,/N with n, the number of samples of client i, and N the total number of samples across all clients. We use + IR" + R to denote the scalarization of f and &p R + R for some scalar function that operates on each ft. We denote E R" as the dual parameter, and Ag as Kolmogorov's generalizod mean. The utilities of each client is 4, E R whose exact definition depends on the context, and u (u1,-... (u1.-..,u,) up) denotes the vector all client utilities. A more complete notation table can be found in Appendix A.
2 A Unified Framework of Fair FL Algorithms
Suppose we have n clients, and a model parameterized by 0. Because of data heterogeneity, for each client the data distribution D, is different. The corresponding loss function becomes:
f((0) := Em (f(0, ())]
(2.1)
where the prediction loss (such as cross entropy) model 0 for each sample. The goal of FL is essentially to learn model 0 that every clement in the vector f (f....,ffa is small, a.k.a. multi- objective optimization (MOO, Jahn et al. 2009). Hu et al. (2022) took this approach and used Multiple Gradient Descent Algorithm (MGDA) to find Pareto stationary points.
2

---

Published in Transactions on Machine Learning Research (01/2023)
Another popular approach to MOO is scalarization of f (Chapter 5, Jahn et al., 2009), by changing the vector optimization to some scalar optimization: m f) with Φ; R - R. In this work, we mainly focus on & being (additively) separable function:
min Σ pi(pof)(0) 9: R:
(2.2)
The linear weights p.s are usually pre-defined and satisfy 2 0 =1 In FL, a usual choice of is p. = nn/N with n, the number of samples for client and N the total number of samples. Here op is a monotonically increasing function, since if any fi increases, the total loss should also increase.
In order to properly locate proportional fairness in the fairness literature, we first review existing fairness definitions that have been applied to FL. In the following subsections, we show that different choices of scalar function y lead to different fair FL algorithms with their respective fairness principles.
2.1 Utilitarianism
The simplest choice of ip would be the identity function, ((fi) fc:
min F(O)= = Σ Pisi(0), with 2 0 pre-defined, and Σn: 1.
(2.3)
This corresponds to the first FL algorithm, Federated Averaging (FedArg, McMahan et al. 2017). Combined with eq. 2.1, the objective eq. 2.3 is equivalent to centralized training with all the client samples in one place.
From a fairness perspective, eq. 2.3 can be called utilitarianism, which can be traced back to at least Bentham (1780). From a utilitarian perspective, a solution 0 is fair if it maximizes an average of the client utilities. (Here we treat client i's utility u, as -fi. In general, U4 E R is some value client i wishes to maximize.)
2.2 Egalitarianism (Maximin Criterion)
In contrast to FedAvg, Agnostic Federated Learning (AFL, Mohri et al. 2019) does not assume a pre-defined weight for each client, but aims to minimize the worst convex combination:
min max P
En,s(()) with 1T 1p== 1, and p > 0.
(2.4)
Note that p Rd is a vector on the probability simplex. An equivalent formulation is:
min max f0).
(2.5)
In other words, we minimize the worst-case client loss. In social choice, this corresponds to the cgalitarian rule (or more specifically, the maximin criterion, see Rawls 1974). In MOO, this corresponds to ((f) = max, fi (above eq. 2.2). There is one important caveat of AFI. worth mentioning: the generalization. In practice, each client loss f; is in fact the expected loss on the empirical distribution D., i.c.,
(()))) E
[C(0, v)).
(2.6)
In FL., some clients may have few samples and the empirical estimate 8ú may not faithfully reflect the underlying distribution. If such a client happens to be the worst-case client, then AFL would suffer from defective generalization. We provide concrete example Appendix C, and this phenomenon has also been observed in our experiments.
2.3 Q- Fairness
/(q + 1): Last but not least, we may slightly modify the function y FedAvg to be p(fi)= = "0=1=tt////>>>>>
min a
1
Σ prl. (0), with P: 2 0 pre-defined, and Σ Pt = 1.
(2.7)
3

---

Published in Transactions on Machine Learning Research (01/2023)
This is called q-Fair Federated Learning (q-FFL, Li et al. 2020c), and 9 2 0 is required. If q 0, then we retrieve FedAvg; if q 0o, then the client who has the largest loss Ji will be emphasized more, which corresponds to AFL. In general, q-FFL interpolates between the two. From a fairness perspective, q-FFL can relate to a-fairness (Mo & Walrand, 2000), a popular concept from the field of communication. Suppose each client has utility u, E IR and u = (u1..... "n) Eu S R", with U the feasible set of client utilities, then a-fairness associates with the following problem:
log ui /11
if a = 1,
m1XX
Σ [i)) with pre-defined p; 0 and (u(u)) KEE
u 11-0 ox) ax)
if a > 0 and a +
(2.8)
g-FFL modifies the a-fairness with two changes: (1) lake = -4 and allow S 0; (2) replace u, with the loss Ji. Therefore, q-FFI. is an analogy of a-fairness. However, the objective eq. 2.7 misses the important case with a = 1, also known as proportional fairness (PF, Kelly et al. 1998), which we will study in $ 3. Note that the formulation eq. 2.7 is not fit for studying PF, since if we take q - -1 (corresponding to a = 1), then we obtain E P: log fi, which need not be convex even when each ʃs (see also $ 3.1.1).
2.4 Dual View of Fair FL Algorithms
In this subsection, we show that many existing fair FL algorithms can be treated a surprisingly unified way. In fact, eq. 2.2 is equivalent to minimizing the Kolmogorov's generalized mean (Kolmogorov, 1930);
Σ (pieU(io))
Ap(s(0)) = x-
(2.9)
Examples include (ffi) = fo (FedAvg), plf() = f (q-FFL, q 2 0) and (ff)) = exp(aft) (a 2 0). The last choice is known as Tilted Empirical Risk Minimization (TERM, Li et al. 2020a).
We can now supply a dual view of the aforementioned FI. algorithms that is perhaps more revealing. Con- cretely, let yp be (strictly) increasing, convex and thrice differentiable. Then, the generalized mean function Ag is convex iff /y0 is convex (Theorem 1, Ben-Tal& & Teboulle, 1986). Applying the convex conjugate of Ap we obtain the equivalent problem:
min A (f(()) = min max EAS((0) - (A AG(A): == sup Af(())
(2.10)
0 A20
f
where A5(A) is the conver conjugate of Ag. Note that f 2 O and thus we require À 2 O. Under strong duality, we may find the optimal dual variable X", with which our fair FL algorithms are essentially FedAvg with the fine-tuned weighting vector X².
Constraints of X. Solving the convex conjugate AG often gives additional constraints on A. For example, for FedAvg we can find that (A) = if A = p. for all E [n] and (A = co otherwise. For p(ft) fo+1 we obtain the conjugate function corresponding to q-FFL:
(A) = 0, i 0 and Σ p. 1/9 Va < 1, and co otherwise.
(2.11)
Bringing eq. 2.11 into eq. 2.10 and using Hölder's inequality we obtain the maximizer A x p.f.. Similarly, can derive the convex conjugate of TERM (Li et al., 2020a) as:
A5(A)= = Σ log A ff 1 and oo otherwise.
(2.12)
Pt
The maximizer is achieved at A; & a In other words, TERM gives a higher weight to clients with worse losses. Detailed derivations of the convex conjugates can be found in Appendix E.
In Table 1, we summarize all the algorithms we have discussed, including their motivating principles, objec- tives as well as the constraints of X induced by AG Although the fair FL algorithms are motivated from different principles, most of them achieve a balance between utilitarianism and egalitarianism, thus allowing to compare them the same ground (S 5).
4

---

Published in Transactions on Machine Learning Research (01/2023)
Table 1: Different fairness concepts and their corresponding FL algorithms. fa the loss function for the tt client. The requirement of À can be found in $ 2.4 and 3.2. We defer the description and the dual view of PropFair to $ 3.
FL algorithm
Principle
Objective
Constraints of X
FedAvg
Utilitarian
E. max; St E,Pifft Espras
X - P: X 1
AFL q-FFL TERM
Egalitarian
a-fairness
\ & X
n/a
X m X 0, 0
PropFair
Proportional
EiP: (o ft)
X x
M-T. (1.()
3 Adapting Proportional Fairness to FL
Now we study how to add the missing piece mentioned in Section 2.3 FL: proportional fairness. From a utility perspective, eq. 2.8 with a reduces to:
max WEH
Σ ps log with p; 2 0 pre-defined, and Pp:=1
(3.1)
Note that we now specify the domain of u to be 4 S R The objective in eq. 3.1 is sometimes known as the Nash product (up to logarithmic transformation), and the maximizer also called the Nash bargaining solution (NBS, Nash 1950). Axiomatic characterizations of the Nash bargaining solution are well-known, for instance by the following four axioms: Pareto optimality, symmetry, scale equivariance and monotonicity (e.g., Maschler et al., 2020, Theorem 16.35). Moreover, Figure 1 gives an illustration of the NBS. Among all the solutions that maximize the total utility, the Nash bargaining solution achieves equal utility for the two players, and the largest worst-case utility.
The first-order optimality condition (Bertsekas, 1997) of eq. 3.1 can be written as:
(u uu ps log v S for any u E U
(3.2)
resulting in the following definition of proportional fairness (Kelly et al., 1998):
u² E l is proportionally fair if Σ
p: ui u < 0, for any u E U.
(3.3)
u
Intuitively, (w:- - u/)/u² q is the relative utility gain for player given its utility switched from ug to u, PF simply states that the solution u", the average relative utility cannot be improved. For instance, for two players with p1 = p2 1/2 have;
U1 wi u
U2
u u,
(3.4)
which says that if by deviating from the optimal solution (uf, uz), player 2 could gain percentage more in terms of utility, then player will have to lose a percentage at least as large as p.
The Nash bargaining solution is equivalent to the PF solution according to the following proposition:
Proposition 3.1 (equivalence, e.g. Kelly 1997; Boche Schubert 2009). For any conver set U E R a point u the Nash bargaining solution iff is proportionally fair. LA is non-convez, then a PF solution, when erists, is Nash bargaining solution.
A PF solution, whenever exists, is a Nash bargaining solution over U. While the converse also holds l is convex, for nonconvex U1 PF solutions may not exist. In contrast, NBS always exists if 24 is compact, and
5

---

Published in Transactions on Machine Learning Research (01/2023)
M2
Mi M/ = 0.25
2
(0.5, 0.5)
U
0/ 02
81
0
0.5
Figure 1: Figure inspired by Nash (1950). U: the feasible set of utilities. Blue line: maximizers of the total utility, on which the Nash bargaining solution u' stands out the fairest.
thus we solve 3.1 as necessary condition of PF. From Jensen's inequality, we can show that:
Ep. u, S log Σ p.u.
(3.5)
In other words, solving the NBS yields a lower bound the averaged utility. On the other hand, any of the utilities close to zero, then the left hand side eq. 3.5 would decrease to -cc. Therefore, the NBS does not yield extremely undesirable performance for any client. In a mutshell, the NBS achieves balance between maximizing the average and the worst-case utilities.
3.1 The PropFair algorithm for federated learning
In order to realize proportional fairness in FI., we need to solve eq. 3.1. With parametrization of u, the utility set U becomes the set of all possible choices of (u, (O), (O)), and our goal is to find global model 0 to solve eq. 3.1:
max Σ
Ps log (0).
(3.6)
3.1.1 What is the right choice of utilities?
One immediate question is: how do we define these utilities in FL? Ideally, the utility should be the test accuracy, which is unforunattely not amenable to optimize. Instead, we could use the training loss f.. There are a few allernatives:
Replace u, with f. as done g-FFL, and minimize the aggregate loss, E, P. log
Replace u, with fi as done F-FFL, and maximize the aggregate utility, Σ, Pi log fa:
Choose u, = M and maximize P. log(Al-f)) with M some hyperparameter to be determined.
The first approach will encourage the client losses to be even more disparate. For instance, suppose Pi
P2 1; and then (f1, f2) (3. 3) has smaller product than (f1, (2 The second approach is not choice either as it is at odds with minimizing client losses. Therefore, are left with the third option. 1/2, one can show that (f1.f) (2 2) always gives better solution than (f1, = ( 3) The resulting objective becomes:
By contrast, for any M > 1 and
min (0)) = Σ -((())))(()))
(3.7)
3.1.2 Huberization
However, the objective eq. 3.7 also raises issues: what if M fo is small and blows up the gradient, even worse, what if M fa is negative and the logarithm does not make sense at all? Inspired by Huber's

---

Published in Transactions on Machine Learning Research (01/2023)
Algorithm 1: PropFair
Input:
global epoch T, client number n, loss function fi for client i, number of samples for client i,
initial global model 0o: local step number K;, baseline M, threshold c, P; = n./N, batch size m, learning rate for & in 1.....-11 do randomly select C, S [n]
0 0 0, for 1 Ct, N N Eiec," nh
for i in Ct do in parallel
j= 1, draw K; mini-batches of samples from client
for S in the K; botches do
(0) 5.1 (a..)s. ((0, (x,y))
1 (0) =1ogga (M (0))
()) 0 0 V ( (0 (0 j +
0
0.+1 Eies, piO....
11
12 Output: global model 0r
approach of robust estimation (Huber, 1964), we propose a "huberized" version of eq. 3.7:
log((M M f), i min- Σ ps logge (M -x()),,()), with logge (M- - -))= log c [t M +), ff
(3.8)
0
Essentially, (M - t) is a robust C³ extension of log(M - from [0, M e] to R4;: its linear part ensures that at = M e, both the value and the derivative are contimuous. any fa is close or greater than M, then eq. 3.8 switches from logarithm PropFair. It modifies FedAvg (MeMahan al., 2017) with simple drop-in replacement, by replacing the loss of each batch Ess with (M (0)). This allows easy adaptation of PropFair with minimal change into any of the current FL platforms, such as Flower (Beutel et al., 2020) and Tensorflow Federated. Also note that in Algorithm we average over the batch before the composition with log This order cannot be switched since otherwise the local variance will be m times larger (see eq. B.52).
its linear version. Based on eq. 3.8 we propose Algorithm 1 called
Remark. When M - and f((0) is small compared to M, the loss function for client i becomes:
S((0)
(0) = log(M f())) ~ - log M + ())
M
Thus, FedAvg can be regarded as first-order approximation of PropFair. We utilize this approsimation in our implementation. Another way to obtain FedAvg is to take c = M and thus log, (M - -t) always uses the linear branch. In contrast, if - O, then eq. 3.8 becomes more similar to eq. 3.7.
3.2 Dual view of PropFair
With the dual view from Section 2.4, we can also treat PropFair as minimizing a weighted combination of loss functions (plus constants), similar to other fair FT. algorithms. Note that if ((f)) = - logg - eq. 2.9, then we have PropFair (see Table 1): Proposition 3.2 (dual view of PropFair). The generalized mean eq. 2.9 for PropFair can be written
Af(f)=
max X20 (A/P))E
AT M
1), 1-1).
(3.9)
Solving the inner marimization of eq. 2.10 gives Ih
Ae and A x Pi M-
Similar FERM/ PropFair puts larger weight on worsc-off clients with larger loss.
http::///wwwttessff...o htt.://tmmoooll...ooo//eeeeeeedd

---

Published in Transactions on Machine Learning Research (01/2023)
4 The optimization side of PropFair
In this section, we discuss the convexity of our PropPair objective and show the convergence guarantee of Algorithm 1. This gives formal fairness guarantee for algorithm, and potentially for the convergence of many others in the scalarization class, eq. 2.2. For simplicity only study the case when ft I M for all i.
4.1 Convexity of the PropFair objective
Convexity is important and desirable property in optimization (Boyd & Vandenberghe, 2004). With convexity, every stationary point is optimal (Bertsekas, 1997). From the composition rule, if fi is convex for each client i, then M - fi is concave, and thus P: log(AM f())) is concave as well (e.g., Boyd & Vandenberghe; 2004). In other words, for convex losses, our optimization problem eq. 3.7 is still convex as we are maximizing over concave functions. Morcover, our PropFair objective is convex even when fi's are not. For example, this could happen [i(0)= = M - exp(0 A,0) and each A, a positive definile matrix. In fact, it suffices to require each M ft to be log-coneave (Boyd & Vandenberghe, 2004).
4.2 Adaptive learning rate and curvature
Denote (tt) = log(Al - t). We can compute the _st and 2nd-order derivatives of y fa:
VS. V( = f (i) (M f.) f. + (VI)(V (M- f.)
(4.1)
This equation tells us that at each local gradient step; the gradient Vip fi) has the same direction as fi, and the only difference the step size. Compared FedAvg, PropFair automatically has an adoptive learning rate for each client. When the local client loss function fi small, the learning rate is smaller; when f is large, the learning rate is larger. This agrees with our intuition that to achieve fairness, worse-off client should be allowed to take a more aggressive step, while better-off client moves more slowly to "wait for" other clients.
In the Hessian (2(pp o fi), an additional positive semi-definite (p.s.d.) term (V.) is added. Thus, (2( o fi) can be p.s.d. even if the original Hessian 2 not. Moreover, the denominator (M- - fi)² has similar effect of coordinating the curvatures of various clients as in the gradients.
4.3 Convergence results
Let us now formally prove the convergence of PropFair by bounding its progress, using standard assumptions (Li et al., 2019; Reddi et al., 2020) such as Lipschitz smoothness and bounded variance. Every norm discussod in this subsection Euclidean (including the proofs in Appendix B).
In fact, PropFair can be treated as an easy variant of FedAvg, with the local objective f; replaced with g! Therefore, we just need to prove the convergence of FedAvg and the convergence of PropFair would follow similarly. In general, similar results also hold for objectives in the form of eq. 2.2.
Let us state the assumptions first. Since in practice we use stochastic gradient descent (SGD) for training, we consider the effect of mini-batches, We also assume that the (local) variance of mini-batches and the (global) variance among clients are bounded.
Assumption 4.1 (Lipschitz smoothness and bounded variances). Each function fi is L-Lipschitz smooth, i.c., for any 0, 0' E Rd and any E [n], we have [ ((')l s L| -0Il; ; For any i.j E [m], fi fy is a Lipscchit continuous and E( [[ (x, v)) - (0)) S o² v0 E Rd.
Following the notations of Reddi et al. (2020), we use r² and of to denote the global and local variances for client i. This assumption allows us to obtain the convergence result for FedAvg (see Algorithm 2). For easy reference, we include FedAvg (McMahan et al., 2017) in Algorithm 2, whose goal is to optimize the overall performance. At cach round, each client takes local SGD stops to minimize the loss function based on the client data. Afterwards, the server computes weighted average of the parameters of these participating clients, and shares this average among them. Note that for client i, the number of local steps is K; with
8

---

Published in Transactions on Machine Learning Research (01/2023)
Algorithm 2: FedAvg
Input: global epoch T, client number loss function fi, mumber of samples n, for client i, imitial global model 0, local step number K2 for client i, batch size m, learning rate 7), P: = n,/N
2 for t in O, 0.....T-1 do randomly select C, S [n]
0 = for i E C,, N = EiEc, T4
for i in C, do // in parallel
starting from 0,0) take K; local SGD steps on ft to find (
0.t1 = Eiec, P:0 (i) t+1
Output: global model Or
learning rate n, In line 3 of Algorithm 2, if C, [n] then we call it full participation, otherwise it is called partial participation. We prove the following convergence result of FedAvg. Note that we defined F in eq. 2.3, and m is the batch size.
Theorem 4.2 (FedAvg). Given Assumption 4.1, assume that the local learning rate satisfies nR; S oz for any i E [n] and
n S T. 24(e - (ile-2)(E: 2t) K?)
(4.2)
Rumning Algoritim 2 for T global epochs we have:
12 (11p 9)n
Fo F*
min E|VF
1
0SKST-1
T
with μ EiPiKi for full participation and μ min; K; for partial participation, Fo = F(0o), F* ming F(0) the optimal value, and
v, = =1lpp
Σ
K?
[ 2m
+ +0²) +
Σ 1=1
K2
oi + o p (pI.....,,,)).
]
Our result is quite general: we allow for both full and partial participation; multiple and heterogeneous local steps; and non-uniform aggregation with weight p;. The variance term V decreases with smaller local steps Kü, which agrees with our intuition that each K; should be as small as possible given the communication constraint. Moreover, minimize ||p|| we should take p; = 1/n for each client i, which means if the samples are more evenly distributed across clients, the error is smaller. In presence of convexity, FedAvg converges to neighborhood of the optimal solution, and the size of the neighborhood is controlled by the heterogeneity of clients and the variance of mini-batches. When we have the global variance term a = 0, our rcsult reduces to the standard result of stochastic gradient descont (c.g., Ghadimi Lan 2013), since we have
can see that
Fo F* +011).
min B| (11 9)m
OSIST-1
and by taking 77 O(L/TT), obtain minos =FFos =
We note that we are not the first to prove the convergence of FedAvg. For instance, Li ct al. (2019) assumes that each function fa is strongly convex and each client takes the same number of local steps; Karimireddy et al. (2020) assumes the same number of local steps, gradient bounded similarity and uniform weights P R==1 1/n. These assumptions may not reflect the practical use of FedAvg. For example, usually each client has different number of samples and they may take different numbers of local updates. Moreover, for neural networks, (global) strong convexity is usually not present. Compared to these results, consider
9

---

Published in Transactions on Machine Learning Research (01/2023)
different local client steps, heterogencous weights and partial participation in the non-convex case, which is more realistic.
Based on Theorem 4.2, we can similarly prove the convergence of other FL algorithms which minimize eq. 2.2, if there are some additional assumptions. For the PropFair algorithm, as an example, we need to additionally assume the Tipschitzness and bounded variances for the client. losses:
Assumption 4.3 (boundedness, Lipschitz continuity and bounded variances for client losses). For any E [n], 0 E R and any batch St ~ Di of m i..dd samples, we have:
0 es,
1
Σ
layies. E(0, v)) < M
IS
and for any 0 R (1((0) - f(0'')| & Lo 0'l holds. We also assume that for any i, E [m] and 0 E R ():(0) (0) z or and (( |E (x. v)) [((0)ll & ob, hold.
we can obtain the convergence guarantee of PropFair to neighborhood of some stationary point: Theorem 4.4 (PropFair). Denote T. = n²² x ML + T.)) and pi = N Given Assumptions 4.1 and 4.9, assume that the local learning rate satisfies:
S min
min iEin
(4.3)
6LK, 8i. (e 2) (
By running Algorithm 1 for T global epochs we have:
min
12
To
+ Vo
0S1ST-1
(11p - 9)n
with μ= E,pK for full participation and μ min, Ki for partiol participation, To =(f)), x² ming T()) the optimal value, and
V, = ?
K?
0
27
+ +16(e - 2)n 2?2
Σ
K
6 + 
1=1
where o7 8 (9M2 4.303,)) and ő 1 (30 + Le o0).
Our Thcorem 4.4 inherits similar advantages from Theorem 4.2. One major difference is that when ă one cannot. retrieve the same rale of SGD. This is expected since each batch po pols, is no longer an unbiased estimator oo fi due to the composition. Nevertheless, due to data heterogeneity in FL, the global variance ā is often large, in which case the local variance term o?/m m in V can be comparable to x² by controlling the batch size m.
5 Experiments
In this section, we verify properties of PropFair by answering the following questions: (1) can PropFair achieve proportional fairness as in eq. 3.3? (2) what balance does PropFair achieve between the average and worst-case performances? We report them separately in Scction 5.2 and Scction 5.3.
5.1 Experimental setup
We first give details on our datasets, models and hyperparameters, which are in accordance with existing works. See Appendix D for additional experimental setup. A comprehensive survey of benchnarking FL algorithms can be found in e.g. Caldas et al. (2018); He et al. (2020).
Datasets. We follow standard benchmark datasets in the existing literature, including CIFAR- (10, 100) (Krizhevsky al., 2009), TinyImageNet (Le & Yang, 2015) and Shakespeare (McMahan al., 2017).
10

---

Published in Transactions on Machine Learning Research (01/2023)
0.0
7.5
-25
5.0
reletive change
-75
-10.
-25
-3.0
-150
-175
-10.0
dient
dient
dient
dient
Figure 2: The relative improvement//eetrrioon /deteioratiin (u: (u:uu)/u; of the test accuracy u; of each client of other baseline algorithms compared to PropFair. The dataset is CIFAR-10. The (weighted) average of the relative changes for FedAvg, AFL, q-FFL, and TERM are respectively: -2.11%, -1.32% - -2..95% -1.9%% We choose the hyperparameters based on Table 4 in Appendix D.
For vision datasets (CTFAR-(10, ho0//inyImageNett the task is image classification, and following Wang et al. (2019b) we use Dirichlet allocation to split the dataset into different clients. For the language dataset (Shakespeare), the task next-character prediction. We use the default realistic partition based on different users. We first partition the dataset into different clients, and further split each client dataset into its own training and test sets. This reflects the real scenario, where cach client evaluates the performance by itsclf.
Models, optimizer and loss function. For vision datasets we ResNet-18 (He et al., 2016) with Group Normalization (Wu & He, 2018). As discussed by Hsieh et al. (2020), Group Normalization (with (im_groups=2) works better than batch normalization, especially in the federated settings. For the Shake- speare dataset, we use LSTM (Hochreiter & Schmidhuber, 1997). We find the best learning rates through grid search (see Appendix D).
Other hyperparameters. We implement full participation and one local epoch throughout (with many local steps for each client). Due to data heterogeneity, the number of local steps K, for each client varies. For CIFAR-(10, 100} we partition the data into 10 clients; for TinylmageNet/SSnkkeppa clients.
choose 20
Evaluation metrics. We validate proportional fairness eq. 3.3 of our PropFair algorithm, where we treat each Uj as the test accuracy of client To show that PropFair achieves a proper balance between utilitarian and egalitarian fairness, we use the average and the worst 10% test accuracies. These are standard fairness metrics used the literature (e.g. Li al., 2020a;c). In Appendix D we also present other standard metrics such standard deviation and worst 20%.
5.2 Verification of proportional fairness
In this subsection, we show that PropFair can, some extent, achieve proportional fairness defined in eq. 3.3. We treat u, the test accuracy of client i, and compute
Σ
u4 4
(5.1)
U
with p: nn/N and == (ui,..., ........00 (x))) the test accuracies obtained by the PropFair model. Although we cannot verify eq, 5.1 for every u, we can at least validate the negativity for some competitive u's, of, e.g., models learned by other fair FL algorithms.
5.2.1 CIFAR-10
We first compule eq, 5.1 where u² is the test accuracies obtained by PropFair and u is the test accuracies found by one of the other fair FL algorithms, including FedAvg, AFL, FFL and TERM. Figure 2 shows the relative changes of each elient, (u, - u/)/u², from which we can see that compared to the solution found by PropFair, for another fair FL solution, most clients are degraded by a large relative amount, and only a few clients improved by small amount.
11

---

Published in Transactions on Machine Learning Research (01/2023)
FedAvg
GFFL
relative change (h)
Cient
dient
dient
dient
Figure 3: The relative pearrovemenn/deteeiirnaat (u,uu))/u; the test accuracy of each client i, pretrained with PropFair and fine-tuned with another baseline. The dataset CIFAR-100. The average of the relative changes for FedAvg, AFL, q-FFL and TERM are respectively: 0.86%, +0.05%, -0.67%, 1.01%.
FodAug
AFL
OFFL
TERM
20
20
relatve change
15
15
15
10
20
30
Figure 4: The relative improvement/deternn /dteriooattiinnnnnnnnnoooo (u, --,)/u, of test accuracy of each client i, pretrained with another baseline and fine-tuned with PropFair. The dataset. is CIFAR-100. The average of the relative changes over FedAvg, AFL, q-FFL and TERM are respectively: 10.88% 13 13.93%, 11.58%, 8.67%.
5.2.2 CIFAR-100
In fact, we may compute eq. 5.1 with stronger u. For CIFAR-100, we still treat. u² as the test accuracies obtained by PropFair. The difference that we use u as the initialization, and fine-tune with other fair FL algorithms, to find u. If other fair FL algorithms cannot improve the proportional fairness of u", then eq. 5.1 should be negative. As improvement for AFL).
in Figure 3, this result indeed holds approximately (except the slight
By contrast, none of the baseline fair FL algorithms can achieve the same level of proportional fairness as our PropFair. Figure 4, we see that if we start from a model pretrained with a baseline fair FL algorithm, and fine-tune with our Propfair, most client performances are improved, sometimes by large margin.
5.3 Comparison between PropFair and existing fair FL algorithms on other metrics
In Figure 5, we compare PropFair with existing fair FL algorithms using the average and the worst 10% test accuracies across clients, including FodAvg (McMahan al., 2017), q-FFL (Li et al., 2020c), AFT (Mohri al., 2019) and TERM (Li al., 2020a).
that PropFair does not always yield the best average performance, e.g., compared to q-FFL TinyImagoNet. This is expected, since maximizing the Nash product does not necessarily give the best average performance. Nevertheless, PropFair remains competitive. Somewhat surprisingly, FedAvg does not always achieve the best average performance, which might be due to optimization issues (Pathak & Wainwright, 2020).
Average performance. From Figure 5
Worst 10% performance. We also compare the worst 10% performance of various fair FL algorithms. We observe that PropFair achieves the state-of-the-art. in terms of the worst 10% performance, across various
12

---

Published in Transactions on Machine Learning Research (01/2023)
CIFAR10
CIFAR100
34
31
58
32
29
56
61
54
30
27
mean
mean
26
23
PropFair
24
21
FedAvg
mean
TinylmageNet
worst 10%
mean
Shakespeare
worst 10%
AFL
53
51
qFFL
51
49
16
13
15
12
50
48
14
11
13 mean
10 49
47
mean
Figure 5: Mean and worst 10% test accuracies for different algorithms. The accuracies are in percentage. (top left): CIFAR-10; (top right): CIFAR-100; (bottom left): TinylmageNet; (bottom right): Shakespeare. All subfigures share the same legends and axis labels.
vision and language datasets. This is within our expectation, since from eq. 3.5 and eq. 3.7 we can see that low utility any of the clients would result in a small Nash product.
Specifically, although AFL directly maximizes the worst-case loss function, it does not always achieve the best worst-case performances (see Table in Appendix D), especially for vision datasets. This might be due to the generalization issue of AFL (see Appendix C).
6 Related Work in Fair FL
We review recent related work fair federated learning. In additional to AFL (Mohri el al., 2019), F-FFL (Li al., 2020c) and TERM (Li al., 2020a), there have been other approaches for fairness in FL. For example, FedMGDA+ (Hu et al., 2022) defines fairness achieving the Pareto frontier and they proposed to use the MGDA algorithm. As another example, GIFAIR-FL (Yue et al., 2022) encourages the similarity of the client losses by adding regularization term of the pairwise é distances. Last but not least, Ditto (Li et al., 2021) proposed a personalization approach to obtain fairness and robustness. A comprehensive recent survey of fairness in FL can be found Shi et al. (2021), and we have included additional papers of lairness (in FL and in general) in Appendix F.
7 Conclusions
Based the necessity of considering relative changes, we introduce the concept of Proportional Fairness (PF) into the field of federated learning (FL), which is deeply rooted in cooperative game theory. By showing the connection between PF and the Nash bargaining solution, we propose PropFair that maximizes the product of client utilities, where the total relative utility cannot be improved. This guarantees PropPair to have good worst-case performance without sacrificing the total utility much. We verify proportional fairness and the balance between utilitarian and egalitarian fairness our extensive experiments. As we have shown, many fair FL algorithms, including PropFair, can be unified using Kolmogorov's generalized mean, the deeper understanding of which may lead to future design of fair FL algorithms.
13

---

Published in Transactions on Machine Learning Research (01/2023)
Broader Impact Statement
With the wide deployment of federated learning, how to ensure fairness in FL algorithms has become major concern. In this work, study proportional fairness in FL to make FL systems fairer and thus more trustworthy. This could have important positive social impacts as well. We are not aware of potential negative socictal impacts yet but we welcome discussions on them.
Acknowledgments
We thank the reviewers and the action editor for constructive comments that largely improved our draft. GZ would like to thank Changjian Shui for his constructive feedback on an earlier draft, and Mahdi Beitollahi for pointing out typos. YY is supported by NSERC and WHJII.
References
Charles Audet, Gilles Savard, and Walid Zghal. Multiobjective optimization through a series of single- objective formulations. SIAM Journal on Optimization, 19(1):188-2) -2000 2008
Pranjal Awasthi, Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Beyond individual and group fairness. Xixie preprint arXix:2008.0 wrXi::2008.04400 2020.
Sina. Baharlouei, Maher Nouiched, Ahmad Beirami, and Meisam Razaviyayn. Rényi fair inference. In International Conference on Learning Representations, 2019.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness in machine learning. NIPS tutorial, 2017.
Aharon Ben- Tal and Marc Teboulle. Expected utility, penalty functions, and duality in stochastic nonlinear programming. Management Science, 32((1):1445 1466-116646666, 1986. URL https://doi. org/orog//// 11. 1445.
Jeremy Bentham. An Introduction to the Principles of Morals and Legislation. For T. Payne and Son, at the Mews Gate, 1780.
Dimitri Bertsekas and Robert Gallager. Data networks. Athena Scientific, 1987.
Dimitri Bertsekas. Nonlinear programming. Journal of the Operational Research Society, (8(3):334-333 1997.
Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. The price of fairness. Operations research, (1):17-31, 2011.
Daniel Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Titouan Parcollet, Pedro PB de Gusmão, and Nicholas D Lanc. Flower: A friendly foderated learning rescarch framework. arXir preprint arXiv:2007.14300 2020.
Holger Boche and Martin Schubert. Nash Bargaining and proportional fairness for wireless systems. TEEE/ACM Transactions on Networking, 17(5):1453-144 October 2009.
Stephen Boyd and Lieven Vandenberghe. Conver optimization. Cambridge university press, 2004.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwakkar. LEAF: A benchmark for federated settings. arXiv preprint arXiv:1812.01097, 2018.
Mina Dashti, Paciz Azmi, and Keivan Navaie. Harmonic mean rate fairness for cognitive radio networks with heterogencous traffic. Transactions on Emerging Telecommunications Technologies, 24(2), 2013. ISSN 2161-3915. URL
wiley. wwtp//////bb////.000///22 1002e//t..... 2541.
14

---

Published in Transactions on Machine Learning Research (01/2023)
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, pp. 214 226, New York, NY, USA, Jamuary 2012. Association for Computing Machinery. ISBN 978-1- 4503-1115-1. doi: 10.1145/2000236..20000 2090255. URL http::/doo..oopg 1144/20902226666. 209002255.2.
2090255.
Martin Gebel. Multivoriate calibration of classifier scores into the probability space. PhD thesis, Citescer, 2009.
Arthur M Geoffrion. Proper efficiency and the theory of vector maximization. Journal of mathematical analysis and applications, 22(3):618 630, 1968.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, (344)22341-2 12668, 2013.
Tan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pp. 2672 2680, 2014.
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. October 2016. URL https: /arxivv wwwg/ag//////eeeeee.eeeeeeeeeeee ab60/ 02413v1.
Chaoyang He, Songze Li, Jinhyun So, Xiao Zeng, Mi Zhang, Hongyi Wang, Xiaoyang Wang, Praneeth Vepakomma, Abhishek Singh, Hang Qiu, al. FedML: A research library and benchmark for federated machine learning. arXiv preprint 1xXx:2007..3516 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Tn Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770 778, 2016.
Sepp Hochreiter and Jürgen Schmidluber. Long short-term memory. Newral computation, 98)::1335-178) 1997.
Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-iid data quagmire of de- centralized machine learning. In International Conference on Machine Learning, pp. 4387-4398. PMLR, 2020.
Zeou Hu, Kiarash Shaloudegi, Guojun Zhang, and Yaoliang Yu. Federated learning meets multi-objective optimization. IEEE Transactions on Network Science and Engineering, 9()::0039 2051, 2022. doi: 10. 1109/TNSE.2022.316911
Peter J. Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1): 73 101, 1964. doi: 22211//0//111777372222 URL https://doo org/ 10. 22114/0mm/1177703/333
Ahmed Imteaj, Urmish Thakker, Shiqiang Wang, Jian Li, and M Hadi Amini. A survey on federated learning for resource-oossrrinned loT devices. IEEE Internet of Things Journal, 9(1):1-24, 2021.
Johannes Jahn et al. Veclor oplimization. Springer, 2009.
Rajendra K Jain, Dah-Ming W Chiu, William R Hawe, et al. A quantitative mcasure of fairness and discrimination. Eastern Research Laboratory, Digital Equipment Corporation, Hudson, MA, 1984.
Jiawen Kang, Zehui Xiong, Dusit Niyalo, Yuze Zou, Yang Zhang, and Mohsen Guizani. Reliable federated learning for mobile networks. IEEE Wireless Communications, 27(2):72 80, April 2020.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: stochastic controlled averaging for federated learning. In In- ternational Conference on Machine Learning, pp. 5132 5143. PMLR, 2020.
FP Kelly, AK Maulloo, and DKH Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 233):322725 March 1998. ISSN 1476- 9360. URL https:/ //doi. org/10. /0. 1057 1at71100lgg//eeeeeee 20t.://a11.aeee.rrrr280000003 2600523.
15

---

Published in Transactions on Machine Learning Research (01/2023)
Frank Kelly. Charging and rate control for clastic traffic. European transactions Telecommunications, 8 (1):33 37, 1997.
Andrey Kolmogorov. On the notion of mean. Atti della Academia Nazionale dei Lincei, 12(9):388 391, 1930. URL https://iink.sprrate
com /tt/////////007777661111 reprinted in "Selected Works of Andrey Kolmogorov: Mathematics and Mechanics", pp. 144 146, 1991.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images, 2009. Technical report.
Matt Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 4069 4079, 2017.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231n, 2015.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. In International Conference on Learning Representations, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450, 2020b.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning.
In International Conference on Learning Representations, 2020c.
Tian Li, Shengyuan Hu, Ahmad Beirami,, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In ICML, volume 139 of Proceedings of Machine Learning Research, pp. 6357- 6368. PMLR, 2021.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-iid data. In International Conference on Learning Representations, 2019.
Guodong Long, Yue Tan, Jing Jiang, and Chengqi Zhang. Federated learning for open banking. In Federated learning, pp. 240-254 Springer, 2020.
FA Lootsma, TW Athan, and PY Papalambros. Controlling the search for a compromise solution in multi- objective optimization. Engineering Optimization+ A35, 25()):65-81, 1995.
Lingjuan Lyu, Jiangshan Yu, Karthik Nandakumar, Yitong Li, Xingiun Ma, Jiong Jin, Han Yu, and Kee Siong Ng. Towards fair and and Distributed Systems, 31(11):2524 2541,,,,,222 November 2020.
federated deep models. IEEE Transactions on Parallel
Michael Maschler, Eilon Solan, and Shmuel Zamir. Game theory. Cambridge University Press, Cambridge, second edition, 2020.
Eric Maskin. A theorem on utilitarianism. The Review of Economic Studies, 45(1):93 96, 1978.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-cffiinn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273 1282. PMLR, 2017.
Jeonghoon Mo and Jean Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Trans- actions on Networking, 8(5):556 567, October 2000. ISSN 1063-6692. doi: 10.1109/900 99.87933. URL http::///do..or/1000// 11099/90..00901.11 879343.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference on Machine Learning, pp. 4615 4625, PMLR, 2019.
John Forbes Nash. The bargaining problem. Bomomelrion 18(2):155 -6001155-161,,,, 1950.
Reese Pathak and Martin J Wainwright. FedSplit: an algorithmic framework for fast federated optimization. Advances in Neural Information Processing Systems, 33:7057-7066 2020.
16

---

Published in Transactions on Machine Learning Research (01/2023)
Judea Pearl. Models, reasoning and inference. Cambridge University Press, 19, 2000.
Geoff Pleiss, Manish Raghavan, Felix Wu, Jon M Kleinberg, and Kilian Q Weinberger. On fairness and calibration. In NIPS, 2017.
John Rawls. Some reasons for the maximin criterion. The American Economic Review, 64(2):141-146, 1974.
John Rawls. A theory of justice: Revised edition. Harvard university press, 1999.
Sashank J Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Koncčný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Represendations, 2020.
Amartya Sen. Chapter 22 Social choice theory. volume 3 of Handbook of Mathematical Eco- nomics, pp. 1073-1181. Elsevier, 1986. URI. http:///wwwt....acccacccccccc/ta http://ccennc//rtiicleee//
$1573436286030047. ISSN: 1573-4382.
Hanbyul Seo and Byeong Gi Lee. Proportional-fair power allocation with CDF--bsed scheduling for fair and efficient multiuser OFDM systems. IEEE Transactions on Wireless Communications, 5(5):978-988, May 2006.
William Shakespeare. The complete works of William Shakespeare. 1614. URL https://ww.gutenber org/ebooks//00.
Yuxin Shi, Han Yu, and Cyril Leung. A survey of fairness-aware federated learning. arXiv preprint arXiv:2111.01872 2021.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. In International Conference on Learning Representations, 2019a.
Kangkang Wang, Rajiv Mathows, Chloé Kiddon, Hubert Eichner, Françoise Beaufays, and Daniel Ramage. Federated evaluation of on-device personalization. October 2019b. URL https:///axii: http::://aardi..ogaaa/////// arg/abs//910. 10252v1. arXiv: 1910.10252.
Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song. A principled approach to data valuation for federated learning. In Qiang Yang, Lixin Fan, and Han Yu (eds.), Federated Learning: Prinacy and Incentive, Lecture Notes in Computer Science, pp. 153 167. Springer International Publishing, 2020.
Yuxin Wu and Kaiming He. Group normalization. Proceedings of the European conference on computer vision (ECCV), pp. 3-19, 2018.
Jie Xu, Benjamin S Glicksberg, Chang Su, Peter Walker, Jiang Bian, and Fei Wang. Federated learning for healthcare informatics. Journal of Healthcare Informatics Research, 5(1):1-19, 2021.
Han Yu, Zelei Liu, Yang Liu, Tianjian Chen, Mingshu Cong, Xi Weng, Dusit Niyato, and Qiang Yang. A fairness-aware incentive scheme for federated learning. In Proceedings of the AAAT/ACM Conference AI, Ethics, and Society, AIES '20, pp. 393 393-399, New York, NY, USA, February 2020. Association for Computing Machinery.
Po-Lung Yu and Milan Zeleny. The set of all nondominated solutions in lincar cases and multicriteria simplex method. Journal of Mathemalical Analysis and Applications, 49(2):430 468, 1975.
Xubo Yuc, Maher Nouiched, and Raed Al Kontar. GIFAIR-FL: A framcwork for group and individual fairness in federated learning. INFORMS Journal on Data Science, 0(0).ull,, 2022. doi:
URL httpps://oi..o/ org/ 100 12w.//13s..2022..0000. 2022.0022.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P. Gummadi. Fairness beyond disparate treatment & disparate impact: learning classification without disparate mistreatment. Proceedings of the 26th International Conference on World Wide Web, pp. 1171-1180, April 2017. doi: 011144/3038912.355533 URL http://arxiv. http:///arxi..rrr/aa//11000 2.820 08452. arXiv: 1610.08452.
17

---

Published in Transactions on Machine Learning Research (01/2023)
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In
Proceedings of the 30th International Conference on Machine Learning, pp. 325-333. PMLR, May 2013. mlr www..perreee/eeeeeeeeeeeee http://mmee1..... html.. ISSN: 1938-7228.
URL
Han Zhao and Geoff Gordon. Inherent tradeoffs in learning fair representations. Aduances in neural infor- mation processing systems, 32:15675-15685, 2019.
18

---

Published in Transactions on Machine Learning Research (01/2023)
Notation
Meaning
0
model parameters
n
the number of clients
m
batch size
a: E Rd
raw input
y E [C]
output label
the number of samples from client
N
= Ei
the total number of samples from all clients
S;
batch of samples from client
D;
data distribution of client
E(0, (x,, 3))
prediction loss (e.g. cross entropy) of model O on sample (æ, y)
ls:
average loss over batch S;
St
expected loss distribution D vector of client losses utility of client
f = (fi,...: fnn)
Ui
u (WI,,..,,u Un)
vector of client utilities
K;
the number of local steps of client i
Pi
pre-defined weight of each client i, usually pt = n:/N
p (P1..... . PP))
vector of client weights
① : R² +
scalarization function of f
:p R + IR
scalar function that acts each client loss fi
A,
Kolmogorov's generalized mean with scalar function y
X
(AI,...;>u)
dual parameter
7
local learning rate local variance on distribution i
of
o²
global variance among clients
F -,E,as Pife
objective of FedAvg
log,o (M -1)
huberization of log( M - t), see eq. 3.8
E₁ Pi logia((M fi)
objective of PropFair
Lipschitz constant of all V
natural logarithm
IR+
(strictly) positive orthant of Rt
Table Notation table.
A Notations
We include notation table for easy navigation. The reader can refer to Table for quick access the notations.
19

---

Published in Transactions on Machine Learning Research (01/2023)
B Proofs
Boche & Schubert 2009). For any conver set U E R a point u E U is the Nash bargaining solution iff it is proportionally fair. If U is non-convez, then PF solution, when erists, is Nash bargaining solution.
Proposition 3.1 (equivalence, c.g. Kelly 1997;
Proof. The Nash bargaining solution u* is equivalent to the maximum of the following:
max
pi log ug.
(B.1)
WEL
Since U is convex and Ei= Ps log u, is concave in u, the necessary and sufficient optimality condition (e.g. Bertsekas, 1997)
(u ui V
ps log ui) S for any u U
(B.2)
equivalently, eq. 3.3. If U is non-convex, then the optimality condition eq. B.2 also holds for the convex hull of u. Therefore, u is maximizer of Σx= log in the convex hull of u and thus U.
7
Theorem 4.2 (FedAvg). Given Assumption 4.1, assume that the local learning rate satisfies nk; S 1 for any i E [n] and
n V 24(e- 20le-2(2 2)
(4.2)
Running Algorithm 2 for T global epochs we have:
12
Fo - F*
min VI (11p 9)n
V
0SKST-1
T
with l EiPiKi for full participation and = min; K₁ for partial participation, Fo = F(oo), F* ming F(0) the optimal value, and
[yg? 2m + +02) + (c-
o + ox)O)) K3
] p (p.......,,p)))
v. = nlppl
K? Σ
Proof. We first assume full participation in the following theorem. The partial participation version is an easy extension and we discuss it in the end. We use (.) to denote the model parameters of client at global epoch and local step j. Due to the synchronization step, we have g( 0.0 = 0,, the global model at step t, and
O++1
Σ 1=1
O ( L,
P.
n4
(B.3)
N
where K; is the local number of steps of client i. We also have:
0 - - - - for all j E [K,].
(B.4)
where 96. = Vlgy (0()-)) is an unbiased estimator of ( for j E [Ki], with Sf the jth batch from
client i. Combining eq. B.3 and eq. B.4 have:
0 0, 11
Σ
Pi Σ
9
(
(B.5)
1=1
20

---

Published in Transactions on Machine Learning Research (01/2023)
Part I Since each fi is L-Lipschitz smooth, so is their average F = E,Pafe from which we obtain that:
/ 2 |10 - 0:1²²
F(0++1) & F(O,) + (VF(O.), - 0²) +
(B.6)
Plugging in eq. B.5 yiclds:
Lij²
n
1(O S P(O.) 11 VF)),), Σ pt
9
pi
(B.7)
f=1
From the identity Di.j = VF().) (F)),), write eq. B.7 as:
(1) (1)
9i.)
K;
F(0++1) S F().)
K, VF(
VF(())) Σ
Pj
- VF(01))
j=1
Laj²
Σ Pt 9i. VF(O)) Σ kK.VF((O.)
(B.8)
By further expanding the last term we have:
K.
F(0++1) S F(()))
Σ P.k. IVFOOII - 17 VF((O),
Σ
Σ
VF(O,))
1=1
/=1
2
Lap
K,
LaZ
+ 2
Ps
gi - VF((.))
+
Σ pulke
|VF
2
1=1
j=1
K,
+ LT²²
Σ VO..).
Σ p4
Σ
9
(
VF(O.))
(B.9)
For simplicity we use as a shorthand for Σi= Kg Grouping similar terms together gives:
Ln
F(0(+1) MH I (1-2) 2
2 VF())))
K,
Lai
K. Pt
- (1( - Imppa (F.).))
Σ P:
b.j
(1)
VF(O.))
+
Σ
9
VF(O.))
(B.10)
#=1
j=1
Taking the expectation on both sides and with Cauchy Schwarz inequality, we have:
Ln
10++1) S EF(O.) nu 1
EE
|F
K; (1 - VF(O))
+ 111 - L
|VF(()))1-
Σ
+
i=1
Li
E
Pi
(g
(5)
VF(O.))
1=1
j=1
L1 11
< EF((..) +
77
1
+ (1 Enj) El VF(0))++
2
L E
Σ
Pi
K;
9
(3) V V((O.))
+5n(1 -
LE
Σ P4
K
VF(0.))
1=1
==1
(B.11)
21

---

Published in Transactions on Machine Learning Research (01/2023)
where we used Egi.j ( and the inequality ab S 1 {(² b²) in the second line. Let us now study the two coefficients separately. From the assumption, 6nLK, I 1 for any i [nz], and thus 6mum S 1. Hence we have:
-Tl (1
Ln 21) + 2 Lmp)) s -1 11
Ln 11"
1
Lay
2
11p -
6
+ Lnμ
S 11
12
11 6
(B.12)
12
Therefore, eq. B.11 becomes:
11p
Li
K,
E S EF(0,)
E VF
E
Σ P
g
(
VF((.))
+
12
j=1
K
t1 Ln
1
f (
15-1 -
(B.13)
Part II
With the following identity:
g
9 (2) - V4. + vF(())
=
(B.14)
the second last term of eq.
B.11 can be simplified as:
K
K2 p: j=1
E
Σ
())
E
Σ i=1
(B.15)
where we note that Li. is an unbiased estimator of (.((
(.-1))
We first bound the first term of eq. B.15:
2
2
F
9
SE
Σ
Ps
9
K
V -|1||
gi.
1=1
K,
2
Elpp!
K
96.
V (1)
(
i=1
j=1
K, Σ
= || Σ
K;
E
9
1=1
j=l
K o2
<
|p
(B.16)
1=1
where in the first line, we used triangle inequality; in the second and third lines, we used the Cauchy Schwarz inequality; in the fourth line we used the linearity expectation; in the final line we note that given the last part of Assumption 4.1, we have:
E( (2,00 V af
ES
Σ (a.))S.
ve(0, - -V)())))))))))))))))))))))))))))
Σ
[S
S
(m.))S;
(B.17)
22

---

Published in Transactions on Machine Learning Research (01/2023)
where we used the property that each (a, y) is ii.d. sample from D,, and that the estimation is unbiased (by the definition of fi). Similarly we bound the second term of eq. B.15:
7
E
Σ p
Σ
- vF((.))
K;
E
VL
-
(B.18)
With the following identity:
vi V.(0)) VI(0 -- V).(0)) + VV.(0. VF(O.).
(B.19)
and taking the squared norm on both sides, we have:
v.(( + +
VF(0.))1
$ 2 - 20
(B.20)
where we note that:
V.((0)) Σ PJ ())) (V)(0))) VF
==1
Σ (V(()) VSS(O.))
P5 P)(
(0)
50.
(B.21)
where in the third line we used the triangle inequality and in the last line we used Assumption 4.1. Plugging eq. B.20 into eq. B.18 yields:
Ke
K.
E
Ps
(5-11
VF(O.))
2l Σ K200 +
2T
Σ K;
E
- 0.12
(B.22)
1=1
j=1
Bringing eq. B.16 and eq. B.22 into eq. B.15 write:
K:
E
P
VF(O.))
lp
2
K2
20
2L
||p1 Σ
K;
E
11 0c11
m
j=1
j=1
1
K;
Ip
2
K?
0i
+ 2L 20²
1ppl2
K3
0.11
(B.23)
m
j=U
Part III
Now let us give an upper bound for El(e(() 1.j 0. From eq. B.23, we only need to focus on
K; 2 2 and = l,..., K; - since ( = 0. For j E [K; 1]. we have from eq. B.4:
0 0, 2| 0 b.j -- 0, ng:.) 12)
() 0 v f.
(e (0) + VV - m9.
(6) (99
0, 1. ( )12 1
h. -9.9
0, 10 DP o0
(B.24)
23

---

Published in Transactions on Machine Learning Research (01/2023)
where in the third line we note that Pt is an unbiased estimator of V.: and in the last line we used eq. B.17. The first term in the last line above can be bounded
(
(9) ElO 2.j-1 0. - - ( = 1 2K:
El
() ( 0,11 2K, VV
(B.25)
where we used ||a + b1|2 (1 + Since
|a|| (1 + a) (b|2 for any vectors a, with the same dimension and or 0.
vfi( (V.. Vf.( = (Vf) (F()))) VF(O.)
(B.26)
taking the squared norm on both sides we have (note that (a+ b b+ s 3(a² + + +c)):
V D- v 3/V vf.00l + +3 ( VF VF
s 323110 2 0.1 2 3 3 3
(B.27)
where the second line we used eq. B.21 and Assumption 4.1. Plugging eq. B.27 into eq. B.25 we find:
--- - 0. - 0V 1+ 2K, -1 6K,n) EiOo 0.12 +KK 6K
(B.28)
Combined with eq. B.24, we obtain:
El 0 0.11
s 2
1+
2K, - + L2 EiI0! 0ol12 +n²
1
( m
+6KK0²)
(B.29)
Recall that we assumed S mini 6K. have:
min:lokkZ) }. For K; 2 2 (note the assumption at the beginning of Part III, we
1
26 < 1
+
S 11
(B.30)
2K:
2K: 1
6K,
K;
Therefore, eq. B.29 becomes:
o 6K, + + +6Km
E 0.11 <
1 Ki
E10 1-j- - 0111 + 1?
E
(B.31)
We can treat (a; = EE k.j
- 1111 k as a sequence. Unrolling this sequence and with ag = 0, we have:
1 1 )
E E (
0.113 v
-1
n¹
o, m
+ 6k:O² + +6K, V
+ Ki -
Ki
|+ K;
1 i
1
( 112
o m
+ +6Ki07 + ( +
(B.32)
Summing over j == 0, 1,
K;
gives:
K.
E 0
0 < K?
(1+
1
K.
-2
1 (1p -
+oK10²) + +6K:"
Kg
m
0=
I (e - 2)K? (T²
0-2
+ 6K,0² + (
m
( (
= (e - -e K3
[ 6K +6K.EIVF(0.)1
(B.33)
where in the first line we used the geometric series formula + + ..... g--l= T- in the second line we
used the fact that (1+ x.)
K.
<e for K₂ 2 1, with e the natural logarithm.
24

---

Published in Transactions on Machine Learning Research (01/2023)
Part IV
We finally put things together and finish proof. From eq. B.13 we have:
11p
6
Ln²
K; VF(O.))
(F(()+1) EF(O.)
B
E
Σ P
9
12
j=1
K;
+ 2 70(1
P
-F(O.))
==1
2
EF((0))
11
EII)F(0.)
Ln²
E
Ps
9
(4)
V
+
12
2
j=1
Lmp
K,
+
+ 2 n1(1 Imju)
E
Σ
Ps
fi (
VF((.))
2
j=l
EF)())) 1 11 (())
LT²
|p
KT
" E
Vi VF(6.))
Pi
12
2
S EF(O,) -
11p 6
E (IVF(())
Ln
|p|
K? 0i
12
2
1=1
K;
+
2|pl2 Σ
K20² + 22211pp1
Σ (=1
K;
E
0 1.-
- 0,11
2
i=1
j=1
11p 6
n2
$ EF(O.)
1
(I.)
+ +6 2)n 1
||| 2
KE + V..
(B.34)
12
where in the third line we used eq.
B.15; in the fifth line we used eq. B.16 and note that
L
n1 Lmn) 2/ 2
17 Lm²
n1) 5ー n
(B.35)
in the seventh line we used eq. B.22; and in the final line we used eq. B.33 and denoted
V
1
Σ K?
+02)
+ (c- 20c-2)n>>>>>
Ki m
of
6K(0²)
(B.36)
2m
Since we assumed:
1
n S EV
(B.37)
24(e - 2A(e-2)|lp122) K.)
we have:
11 - 6
6(e -2),.?(ppl Σ 2
11 - 6
1
11p 9
(B.38)
12
12
4
12
Therefore, eq. B.34 becomes:
11p
EF((++1) S EF(O,)
E (F))))) + V..
(B.39)
12
With some algebra we obtain:
11 11
EE
VF { - F(O++1)) + V...
(B.40)
12
25

---

Published in Transactions on Machine Learning Research (01/2023)
Summing both sides over t O,..., T and dividing by T, we have:
11 91 1) T
F(Oo) F
Vo.
(B.41)
T
which gives:
12
F((O)= F
min El))
+ vo
(B.42)
(11 9)n
T
with F ming F(0) the optimal value.
Finally, for the partial participation, it suffices to replace the client set {I...., n2 with its subset. Note that after this substitution, the new variance term satisfies V I Vo since this term increases with more participants, and eq. B.38 still holds since we subtract a smaller term with partial participation. We also need to modify eq. B.38 so we further lower bound eq. B.38 with 2 min, Kg.
Theorem 4.4 (PropFair). Denote i ( + L and ps N Given Assumptions 4.1 and 4.3, assume that the local learning rate salisfies:
S min
min iE(n)
(4.3)
6LK, sL (e 2)
By running Algorithm 1 for T global epochs we hove:
12
To π
min
(0,)I & (11 9)n
+
1/
OS1ST-1
T
with μz= Eipik for full participalion and μ = min; K₁ for purtial parlicipation, no T(0o), === ming r(0) the optimal value, and
V. = n|pp|
n
K?
0
27
+16(e 2)),
K
+ + ] ]
m
m
where o.
8 Mr (9M2 + 4L3o3,) and ō M
@
+ Le
oo).
Proof. The proof follows similarly the proof of FedAvg (Theorem 4.2). Denote pp() -log(M changes of PropFair compared to FedAvg follows:
M t). The
The aggregate loss for each client i is not Si, but &o fi;
The objective function is not Prfe but π Pipi fú:
For each batch S, D.dh from client i, the batch loss is not ts., but 4 ls,
Note that in Assumption 4.1 we implicitly required eq. 2.1:
((( = ( [E(O, (x, y))];
or in other words, ((,, (z, y)) is an unbiased estimator of f.. This is no longer true if we replace & with yp é and f with o f.. Similarly, ip o És, is no longer an unbiased estimator of go o f.. We will take care of this fitfall in our proof.
First, from the Lipschitzness assumption in Assumption 4.3 we can obtain an upper bound for the gradient: (0)] < Lo for any Rd. We will use this result, as well as the rest of Assumption 4.3, to derive similar bounds as in Assumption 4.1:
26

---

Published in Transactions on Machine Learning Research (01/2023)
the Lipschitz constant of Vip ft:
the Lipschitz constant of po fi - 4o fji
the variance of each batch V Es..
For the Lipschitz smooth constant of yp fas we write:
V(((0) VS((0)
( (0) V f1)(0'I
M 1:(0)
M M--((0))
M(Vf((0)
- - (((
(M -M- -M0
$ M
- (1)))/0)))//0)))+110000000111110 (110))0011)
M2 (ML - 0''
(B.43)
The second term in the parenthesis above can be computed as:
[Vff(0)).(() - vf((0) = ((()). 0100:000000000000000000000000000
< [[ - 111000000000000000100000000
-1V/ - 011
- -V00
.M
Lalle'
(B.44)
where in the second line used triangle inequality; in the fourth line used Assumptions 4.1 and 4.3.
Plugging in back to eq. B.43 we have:
4 3 ( +33) 110 -01l-
VV o ( - v(po fi) S M
(B.45)
Let us now figure out the variance terms. For the global variance term, we similarly write:
V((())
(f((0)
[V ()())))) - V(p (0)(
- [1(0)
M- f)
M(Vf.(0) +T(1))))0000000000+++000
(M (M-A(0)(M-1(00)
4
M (MIVV)) +1(00))++++++ (1)(0))0))))))))))))))())
4
(Mo + -
(B.46)
2
The second term in the parenthesis above can be computed as:
[V))(()),(0)) V1, = - - -
< (V
= ([) (If - + + - M
Laga +
(B.47)
2
where in the second line we used triangle incquality; in the last line we used Assumptions 4.1 and 4.3. Plugging eq. B.47 into eq. B.46 we find:
4
(3
Lo
[V (2) v(go ())(
<
(B.48)
M
2
M
27

---

Published in Transactions on Machine Learning Research (01/2023)
Let finally compute the new local variance term for each batch. Recall that denoted (s) [ST Lieyes ((0, (2, v)), with S ~ D.r. We can write
VSi(0)
(ls
|V e (0) V(p (s)
M - f((0)
M Ls. (0)
3M
[V - vls + Lollf((0) - ( (0)1)
$
(B.49)
M
2
and the derivation follows similarly eq. B.46. Taking the square on both sides and taking the expectation over S D.", obtain:
16
9M2
E V(p (1) (ipo (s)))
2
ES
Vf((0) (Vi(())
ves((0)1
M4
4
+ 2L
Es
S.-D [lf ts (0)11
8
9M o
+ AL0 To.
(B,50)
M1
where in the first line we used (a b) < 2(a² +1 and in the second line we used Assumptions 4.1 and 4.3. For convenience we will use the following notations:
8 4 3 ML 12) oī Ma (DM?o + 41308.) 7= M 2 M
4
(3 0.).
Lo
7= M²
(B.51)
which are the new Lipschitz constant of Vip fi the new local variance term of Vip Ls,, and the new Lipschitz constant of 8o o fi - go o fj. Note that we average after the composition, then the local variance would be:
ES
Σ (..y)E.,
Vp (0, v) - Vpo f(()
Σ (æ.8)ss.
E ((0, Vip f())
|S
S
(B.52)
where can only Cauchy-Schwarz Schwarz inequality since yo o l is biased. Therefore, if we do it in this way, the variance (upper bound) will be m times larger than the current way, which will slow down the convergence.
Let us now follow the proof of FedAvg (Theorem 4.2) to prove the convergence of PropFair. Our proof follows the one of Theorem 4.2. Note that the global update now is:
K Pr
0.11 0, - 1)
(B.53)
-11 with Drd V ls: (5 (0()-)) and S the jth batch from client i. Similar to eq. B.10 we obtain:
7(0(41) S T()))) ah (1 (1- ?
Ln
(0.))12
Lnj
17 -mqp) (.,),,) Σ
Pi
9
(1)
VT((.)) )
p3
9
VT((.))
(B.54)
k=1
1=1
28

---

Published in Transactions on Machine Learning Research (01/2023)
(1) However, since Di.j is longer unbiased, we need to rewrite eq. B.11
ET (0++0+))) S (0i - 1711 (1 (1-2) 2 11
In
K2
B[) + (1 - LE
[
Σ
Ps
Σ
G
VT((.))
+
:=1
j=1
Ln²
n
Ki
+
E
Σ
ps
9t.j
(6)
Vo((+))
i=1
1=1
S (0,) +
(116 (1-
Ln
+
1
71
Lmji)
El| (0,)1++
2
2
Lnj²
+
+ 171(1 - Lmmua
E
P5
G
VT((O.))
2
i=1
K:
< (0,) - 11p- (0,)
|2
+
E
9
VT((,))
(B.55)
12
j=1
where we recycled eq. B.12 and eq. B.35. Similar to eq. B.14 we write:
5 (T,),) /. Vęo f( + vp - (=())).
(B.56)
and using |a + bll2 < 2(1|a|2 2 + [b] eq. B.55 becomes:
11p 6
(T++1)
ET)( 1)
E (0)))
+n
Σ Ps
9r Vi (-1))
+
12
K:
+ wE
Σ
P
-
(B.57)
1=1
with Je shorthand for o Si- With eq. B.50 and similar to eq. B.16, we have:
K
E
Σ
P
((O0-)))
S 1
K2
(B.58)
==
J=1
and similar to eq. B.22, we obtain:
2
K.
n
K, K;
Σ Ps (.
V-((1))
$ 2||p|| Σ
KPOa + 2/
Σ
> E
(0 6- - -,1122
(B.59)
im
j=1
For jE E [K₃ 1], we can write similarly to eq. B.25:
E ( 0.11 = Eil!! - 0, -ng!.)12
1
001 2 2 Ell0!
(B.60)
2K,
With the following equality:
= - (v)(0.) VT.()) VT(()), (+)(0)))
(B.61)
we use ||a
d| || - [|d]2) to obtain:
12 < -
v 1/
v + 4E) - -v + 4E V (0.))
< 4 ह.
+ 4 0 1-
0.1 4 + 4E V
(B.62)
m
29

---

Published in Transactions on Machine Learning Research (01/2023)
Plugging it back into eq. B.60 we have:
B 0
0:11 -
+ 2K; -1 + 8Kin 18100 - 0.11² + 8Km7
1
+0² +
m
1
|F| 1=l (1) 1 0.11 + +8,
ot
+ += +
+ K;
m
(1+ 1.) K; ) -1) (KKn7
(ot
s K,
+ {k.T)
(B.63)
m
where in the sccond line we used r I mins Gk, J. and the last line telescoping. Similar eq. B.33, summing over j = 0, 1,..., K; - gives:
K.
[ E 1 - Ool1² s 8(e - 2)KK3?
02 + [
(B.64)
0=
From eq. B.57 we have:
Ex (0+11) S (.)(O:)
1
11p 6
E. (0.))l1 + +,F
n2
Pi Σ 0
K,
V
()))))
+
12
1=1
==1
K
+ nE
Σ
Ps
V
( (1)
1--1)) - V=()
:=1
1=1
$ (0,)
1)
11p 6
(0.))1 + 11lpp| Σ
n
K? + 2n |ll
0
n
KJO2+
12
m
K.
+ -2ni211p11
Σ K;
E 1- - 0.12
1=1
j=1
< (0,)
1
1 11 6
(0,)l1 + #l/pp|
K?
σ7 +
+222 +22²)+
+
12
m
+ 2n1211p11 Σ
8(c 2)
0 + 82 + El| [
(=1
-E,(O,) 11
11p - 6
16(e - 2)n i 1121
Σ 1=1
K2 E
(T))I1 1 +
12
11 (0,)(1 V..
S (T.) 1 12
(B.65)
where in the second inequality we used eq. B.58 and eq. B.59; in the third incquality we used eq. B.64, in the second last inequality, we denoted:
J = ?
Σ
K?
+ 27
+ 166e - 2)n 1.2
Kt
of
+ +
(B.66)
m
m
and in the last line, we note that:
11p -
11p - 9
16(e 2)ni(>11pp1?
Σ K <
(B.67)
12
12
1=1
since we assumed:
1 17 S
(B.68)
84. V (e - K!)'
30

---

Published in Transactions on Machine Learning Research (01/2023)
22
12
0.9 X
+ + x
-1
1
-1
0
+
Figure 6: The visualization of the distribution shown in eq. C.1. The plus sign means the positive label y = and the negative sign means the negative label y -1.
Similar to eq. B.42 obtain:
12
((())) x
min BT)))(
11
(B.69)
(11 9)m
T
C A Failure Case of Agnostic Federated Learning
In this section we show that AFL might suffer from the generalization issue, in the case when some of the clients have very few samples that are outliers. Suppose the input space R² and the classification task is binary with a linear classifier. We assume the simple case where every client has the same underlying distribution:
0.9U((-1,0) x 1-1, + ((0, 1-1, y- 1, p(zly) 0.9 []), 0.10' x (-),,1] yf= -1.
(C.1)
Note that UT) represents the density of the uniform distribution on interval A visualization of eq. C.1 can found Figure 6.
In practice, we draw samples from each of the client. However, if one of the clients do have enough samples, AFL might have issuc. For instance, two clients could have to opposite sample sets:
S = (((0.5, +0.5), 1), ((-0.5, +0.5), -1)} S2 {((0.5, +0.5), 11), ((-0.5, +0.5), 1)).
In this case, AFL could give an unfavorable generalization error, since the optimal training error is 50%. For example, this optimal AFL solution can be reached one chooses the linear classifier be perpendicular to the -axis,, resulting in the test error to be 50%. However, there exists an optimal classifier (-1,0) such that the test error is 10%.
We can also verify this claim from the proof of Theorem 1 in Appendix C.2, Mohri et al. (2019). If one of the clients has too few samples (i.e., some my is small), then the generalization bound on the right can be very large or even vacuous.
Note that our PropFair algorithm does not suffer from this generalization problem, since if some client has too few samples, then the corresponding weight p: = n./N will be small, and thus according equation 3.7 the overall performance will not be heavily affected.
31

---

Published in Transactions on Machine Learning Research (01/2023)
D Additional Experiments
In this section, provide more details about our experimental results. Results for all experiments are provided based on an average over three runs with different seeds.
D.1 Datasets and models
We describe the benchmark datasets in this subsection. For all datasets we fix the batch size to be 64.
CIFAR-(10, 1003 (Krizhevsky et al., 2009) are standard image classification datasets. There are 50000 samples with 10/100 100 balanced classes for CIFAR-(10, 1003. By doing Dirichlet allocation (Wang et al., 2019a) we achieve the heterogeneity of label distributions. For all samples in each class k, denoted as the set Sk, we split S = Sk U Sk.n into n clients according a symmetric Dirichlet distribution Dir(3). .......... we have C classes total, We note that some
Then we gather the samples for client j as of the clients might have too few samples (a few hundred). In this case the FL algorithm might overfit for such clients and regenerate the data split. We choose the number of clients to be 10 for both CIFAR-(10, 100}. For each of the client dataset, split it further into 80% training data and 20% test data.
Nit is from the course project of Stanford CS231N.2 It contains 200 classes and each class has 500 images. Our FL split setting is the same as CIFAR-(10, 100), except that we choose 20 clients and the Dirichlet parameter B 0.05.
Shakespeare (Shakespeare, 1614; McMahan et al., 2017) is a text dataset of Shakespeare dialogues, and we use for the task next character prediction. We treat each speaking role as a client resulting in a natural heterogencous partition. We first filter out the clients with less than 10,000 samples and sample clients from the remaining. Also, each client's dataset is split into 50% for training and 50% for test.
In Table 3, we summarize these datasets, our partition methods, well as the models implement.
Table 3: Details of the experiments and the used datasets, ResNet-18 is the residual neural network defined in He et al. (2016). GN: Group Normalization (Wu & He, 2018); FC: fully connected layer; CNN: Convolu- tional Neural Network; Conv: convolution layer; RNN: Recurrent Neural Network; LSTM: Long Short-Term Memory layer. The plus sign means composition.
Datasets Training set size Test set size
Partition method
# of clients
Model
CIFAR-10
39963
10037
Dirichlet partition (3 0.5)
10
ResNet-18 + GN
CIFAR-100
39764
10236
Dirichlet partition (8 0.1)
10
ResNet-18 + GN
TinylmageNet
78044
20135
Dirichlet partition (8 0.05)
20
ResNet-118 + GN
Shakespeare 178796
177231
realistic partition
20
RNN (1 LSTM + FC)
D.2 Algorithms to compare and tuning hyperparameters
We compare our PropFair algorithm with common FL basclines, including FodAvg (McMahan al., 2017), q-FFL (Li et al., 2020c) and AFL (Mohri et al., 2019). For each dataset and each algorithm (algorithms with different hyperparameters are the grids used for each dataset:
counted different), we find the best learning rate from grid. Here
CIFAR-10: (5e-3, 1e-2, 2e-2, 5e-2);
CIFAR-100: (5e-3, 1e-2, 20 20-2, 2)=
TinyImageNet: (5e-3, 1e-2, 2e-2, 5e-2];
2htt:://ce2tnn.ttafoordd. sttaroodd...ttnoodeee....
32

---

Published in Transactions on Machine Learning Research (01/2023)
Shakespeare: (1e-1, 5e-1, 1, 2};
Table 4: The best values of hyperparameters used for different datasets, chosen based on grid search.
Algorithm Hyperparameter CIFAR-10 CIFAR- 100 TinyImageNet Shakespeare
q-FFL TERM GIFAIR-FL
0.1
0.1
0.1
0.1
0.5
0.5
0.5
0.5
X/Amax
0.9
0.1
0.1
0.5
FedMGDA+
0.5
0.05
0.05
0.5
PropFair
M
5.0
2.0
2.0
2.0
Table 5: The best learning rates used for different dalasets and algorithms, based on grid search.
Datasets
FedAvg
q-FFL AFL PropFair TERM GIFAIR-FL FedMGDA+
CIFAR-10
5e-3
5e-2
1e-2
5e-2
1e-2
1e-2
CIFAR-100 100
5e-3
2e-2
1e-2
1e-2
5e-3
1e-2
1e-2
TiteemageNet
2e-2
2e-2
2e-2
5e-2
2e-2
2e-2
1e-2
Shakespeare
2
2
2
2
2
We adapt hierarchical TERM from Li et al. (2020a), with client-level fairness (a 0) and no sample- level fairness (r = 0). For each dataset, we tune a (user-level parameter) from {0.01, 0.1, 0.5}. Table 4 shows the optimal value of a used for different datasets is 0.5. For AFL we tune the learning rate The from the corresponding grid and choose the default hyperparameter ? = 0.1. For q-FFL, we run the g- FedAvg algorithm from learning rate.3 For each dataset we tune q from {0.1, 1.0, 5.0). For all datasets we find g 0.1 has the best performance. We also find that == often leads to divergence during training.
al. (2020c) with the default Lipschitz constant L 1/n from where v is the
For PropFair we fix 0.2 and Lune M (Algorithm 1) from M = 2, 4,5. Table shows the optimal values of M used for different datasets. A rule of thumb is to first take large M (say M = 10) and then gradually roduce this value so as to obtain better performance. Given a learning rate y,, we use the lcarning rate " when the loss is greater than M c, and otherwise.
In addition the fair FL algorithms in the main text, we compare with two additional baselines in our appendices: GIFAIR-FL (Yue et al., 2022) and FedMGDA+ (Hu al., 2022). For GIFAIR-FL we first com- pute Amax and choose from (0.1Amax. 0.5Amax 0.9Amax] For FedMGDA+ as implemented in Hu et al. (2022). One minor difference is that we fix the global learning rate to be 1.0.
choose from {0.05, 0.1, 0.5}
After finding the best hyperparameters for each algorithm, we record the best learning rates in Table 5. For SFFAR-1O/CIFARII00 La1B-100//Tnylmageeee Daaaaaeeee//Saaaeeprrrree /Shakespeare, we take 100/400/400/100 communication rounds respectively, in which cases we find most fair FL algorithms converge.
D.3 Detailed results
In Table 6, report different statistics across clients, for all the algorithms and datasets we study in this work. These statistical quantities include:
The mean of test accuracies of all clients;
The standard deviation of client accuracies;
The worst test accuracy among the clients;
The mean of test accuracies across the worst 10% clients;
htatp:://github..cm//itiitt
33

---

Published in Transactions on Machine Learning Research (01/2023)
The best test accuracy among the clients.
The mean of test accuracies across the best 10% clients.
For cach algorithm we take three different runs and report the mean and standard deviation of different statistical indices. In all the experiments we have used 64 as the default batch size. Table shows that PropFair comparable with state-of-the-art algorithms across various datasets.
Table 6: Comparison among federated learning algorithms CIFAR-10, CTFAR-100, TinyImageNet and Shakespeare datasets with test accuracies (%) from clients. All algorithms are fine-tuned. Mean: the average of performances across all clients; Std: standard deviation of client test accuracies; Worst/Best: the worst/best test accuracy from clients; Worst (10%) Best the average of performance across the worst/best. 10% clients. Note that for CIFAR-(10, 100) the worst (best) case accuracy is the same as the worst (best) 10% accuracy since we have clients.
Dataset
Algorithm
Mean
Std
Worst
Worst (10%)
Best
Best (10%)
FedAvg 63.63
4.
53.49.1.67
53.49
72.37 10.53
72.37
q-FFL 57.27 5.682011
47.28
40.28
66. 66.71+1.24
66.7141.24
AFL 64.2920.40
4.48
56.1641.66
56.1641.06
71.55+0.84
71.5540.84
CIFAR-10
TERM
60.62
4.9620.42
56. 16.22.11.2
56. 1.22
71.51
71.5140.2
CIFAIR-FL
23.81
5.05
51..24.1.44
54.244.114
72.41
72.41
FedMGDA+
61.9220.03
4.93
52.84.1.12
52.84
70.42+1.72
70.42+1.72
PropFair
64.75 10
4.46 40.63
58.14
58.1 0..89
72.72 +2.35
72.72+1.30
FedAvg
29.94 4.06
25.26 +
25.26 26.00
40.29 40.85
40.29 +0.85
q-FFL
28.53 4.53
23.33
23.33
39.82
39.82
AFL
30.33 3.
25.4944.12
25.49 1.11
39.21
39.2 39.21
110
TERM
30.35-0.28
3.5020.3
26.
26.4640.36
26, 26.4640.36
39.39+0.00
39. 39.3940.90
GIFAIR-FL.
30.6320.37
3.58
26.992a.38
26.99=0.38
40.03+0.62
10.03+0.62
FedMGDA+
23.6 23.6920.08
3.5220.33
19.01
19.01
32.51
32.51
PropFair
31.84
3.10
28.85
28.85 #0.94
40.12
40.12
FedAvg
16.14_0.59 2.33
11.07
11.81 20.67
20.23+1.11
19.91
q-FFL
18.8420.02 2.23
12.1220.58
13.0620.68
24.1910.25
23.6940.19
AFL
16.43 2.34
11.3441.24
12.32
20.70+0.64
20.21+0049
TinyImage
TERM
16.41
2.75
10.67
11.55
21.75.+1.19
20.97
GIFAIR-FL
16.54_0.41
2.7020.17
11.3420.47
11.9220.15
22.28+0.46
21.47+0.50
+edMGDA+
13.94-0.20
2.70 2.7020.30
9.45+4.03
9.73+0.12
19. 19.15
18. 18.6244.58
PropFair
18.0410.74
12.63 2.69
13.51
23.68
23.02
FedAvg
50.54_0.12
48.18 1.22
48.26
52.33
52.1540.12
q-FFL
50.6920.14 1.05.2.02
18.7420.21
48.83
52.35
52.25
AFL
52.5422.08
1.25
49.86-20229
50.13
54..7710.20
54.22.40118
Shakespeare
TERM
50.90
1.27
48. 48.1044.15
48.45
52.65
52.47
GIFAIR-FL.
50.67 20.28
1.25
48.2244..26
48.3240.30
52.50+0.24
52.45
+
44.17
0.99
42.42.+0.10
42.67
46.30
46. 10.2
PropFair
52.28
1.20
49.50
49.7640.20
54.10
53.8840.12
D.4 Additional evaluation metrics
In this subsoction, we perform comparison with bascline algorithms on CIFAR-100 using additional evaluating metrics, including worst 20% and 30% test accuracies. One can see that our algorithm remains the state-of- the-art among large variety of algorithms.
34

---

Published in Transactions on Machine Learning Research (01/2023)
Table 7: Comparison using worst 20% and 30% test accuracies on the CIFAR-100 dataset. The hyperpa- rameters and learning rates are the same as in Table 4 and Table 5.
Metric
PropFair
AFL
FedAvg
TERM
q-FFL
GIFAIR-FL
FedMGDA+
worst 20%
29.08
26.15 16.15
15.6811.66
26.9010.33
23.9410.51 24.53
27.33 10.35
19.77
worst 30%
29.2940.63
26.6340.24
26. 26.2641.48
27. 27.25
27.66
20.3341.10
E
Dual View of Fair FL Algorithms
In this section we derive the convex conjugates the generalized mcans for each algorithm. We sometimes exlend the domain of f to obtain a clear form of Ap while ensuring the equality of eq. 2.10.
E.1 Dual View of FedAvg
For FedAvg, we have p(t) = t and the generalized mean can be written as:
Ap(f) = Σ plls
(F.1)
where we extend the domain of f to be R The convex conjugate can be written as:
AG(A)= = sup (A - p)
(E.2)
SER
Solving it yields:
f A 0o
(A(A)
(E.3)
otherwise.
Bringing the equation above to eq. 2.10 we obtain the original form of FedAvg.
E.2 Dual View of q- F-L and AFL
Let us now derive the conjugate function for q-FFL. With sp(1) = 19+1 (g > 0) we have:
Ao(f)= = Σ Epspttt
(E.4)
where we assume dom f RT. The convex conjugate can thus be written as:
AA(() sup A AT E [Enfftta) f20
(E.5)
II 1/ 1/xx(0t)/9 > 1, we can take fi= >
p; - 1/2 and the maximand of eq. E.5 becomes:
Epdsttt ttr
x
Σ (g+1)/ 1/84
Σ (9t11// 1/4
t
Σ (0+1)/
- 1/9
Σ X
(
- 1//
t.
(F.6)
35

---

Published in Transactions on Machine Learning Research (01/2023)
By laking - we have (x) Therefore must constrain E.p; 1/1 can utilize Hölder's inequality to obtain AŞ(A)= O. In summary, the convex conjugate for À 2 is:
x -
< 1. In this case, we
0, if E,P, 1/ 1
(9t1///
AC(A)
(E.7)
x otherwise.
Taking + oo the function above becomes the one for AFL:
- 0,
if |||| 1 { x otherwise.
A5(A)
(E.8)
E.3 Dual View of TERM
We continue to derive the convex conjugate of the generalized mean of TERM. Recall that cp(t) ea with & > 0. The generalized mcan can be written as:
1 a A₂(5)
log Emerr))
(E.9)
where extend the domain of f to be R The convex conjugate is:
AA sup A 1 log
Emient)
(E.10)
fER"
a
If any A < 0, we can take the corresponding f: + -0 and thus AŞ(A) 0o. If ETAT1 + 1, we can impose
f = (1 and obtain:
A f log Emeeh ) - 1
(E.11)
By taking -> 50 or t + -0 we get (A) co. Now let assume 2 and A 1. By requiring stationarity eq. E.10 find the necessary and sufficient optimality condition:
X Epp.e
(E.12)
which can always to satisfied with our assumption. Denote E.p.e we can solve eq. E.12 obtain fs a log Bringing back eq. E.10 the convex conjugate becomes:
1
AC(A):
Σ
di
log
(ch;
log
e
a
pi
a
Σ
A
log
X
(E.13)
pi
where we used the condition A 1. Therefore, get:
Since we have the constraint that A > O, eq. 2.10 still holds.
Σ: d log A
11
AA(A) =
(E.14)
2
otherwise.
36

---

Published in Transactions on Machine Learning Research (01/2023)
E.4 Dual View of PropFair
Let us derive the dual of the generalized mean for PropFair in the same framework as in Section 2.4. Note that
(01) log(M - 1),
(E.15)
and therefore the generalized mean is:
[ = = - II (M - f.)
Ax(f)= = -
(E.16)
where we require f & M1. We observe that Ag is a convex function, since it is composition of the generalized geometric mean (which is concave) and affine transformation. Now we compute the dual function
AC(2)=
sup A - As( FSMI
(M- - fi) - M sup AT + JSMI
(E.17)
==1
If any entry X is non-positive, clearly we can let ft + -0 so that Ag(A) + 0o. For positive X, and
II )7:)* < 1, we can take Si = M c and get:
Pj M
A A + M - p.) M (M): - -p) +
#=1
P:
M(A 1) +
-1
(E.18)
Since e 2 0 is arbitrary, we can lake e + do and thus A5(A) xc. Otherwise,
A1
2 1, then we
i=1
have:
A A (M- - M
II (M- - fi) - XT f) 1(ATI-1)
A P:
(M f1)
II
I ft) + 1
ps
[=1 < 1-11-1),
(F.19)
where in the second line used the AM-GM inequality and in the last line we used I1 (2)) )2)/ 1. This equality can always be achieved by taking f = M1. In summary, we have:
M 1), if 0 and I xc,
Ae P
P.
2 1,
AC(2)
(E.20)
otherwise.
We remark that AG is closed (since its domain is closed). If we want to enforce f 2 0 when computing the dual function, simply apply the convolution formula:
A²(2) inf AC(Y).
(E.21)
XST
However, the formula for A suffices for our purpose so need not compute the above explicitly.
37

---

Published in Transactions on Machine Learning Research (01/2023)
Applying the above conjugation result can rewrite PropFair's generalized mean as:
min A (f(0)) min max A f(0) - AC(A). X20
(E.22)
0
We focus the inner maximization that we know the weights we put each client:
A 5(0) (())-A((A)
max A (A 1)M
max X
X20.
(A/R))22
max
M X (M1 f).
(E.23)
A20
Using the AM-GM inequality we have:
Pi T
XT
f)
I A.)x 2
II (M- f.)
(E.24)
where the equality is attained iff
I[
de
P1
and
Pi
Pi
A x
(E.25)
M fi
Thus, verify again that the optimal value of eq. E.23 is:
M II (M 11) = Af(f),
(F.26)
1=1
and we retrieve our original objective. eq. E.25 tells us that we are essentially solving a linearly weighted combination fi....,f Sn, but with more weights on the worse-off clients, since M-F.
Pr_ is larger for larger f..
F More Related Work
In this appendix we introduce more related work, including multi-objective optimization, fairness in FL, as well as various definitions of fairness from multiple fields.
F.1 Multi-objective optimization
Multi-Objective Optimization (MOO) has been intensively studied in the field of operation research (Geof- frion, 1968; Yu & Zeleny, 1975; Jahn et al., 2009). The goal of MOO is to minimize series of objectives f1, fu based on their best trade-offs. This is directly related to federated learning (Hu et al., 2022) because one can treat the loss function of each client as an objective.
MOO, Pareto optimality often desired. To find a Pareto optimum, one way to use an aggregating objective ka.k.a. scalarizing function, Lootsina et al. 1995). We list. some common choices of this aggregating objective:
Linear weighting method (Geoffrion, 1968): this method converts MOO into the problem of mini- mizing the convex combination of clicnt objectives:
min TEX
A.f(())
(F.1)
with À An-1 the (n 1)-simplex, and X the domain of æ. Such solution always Parcto optimal and the method has been used in FedArg (MeMahan al., 2017). A well-known difficulty that it cannot generate point in the nonconvex part of the Pareto front (Audet et al., 2008).
38

---

Published in Transactions on Machine Learning Research (01/2023)
Reference point (Andet et al., 2008): This method requires proximity to the ideal point: (mingex (i()),.... min Ln (m)), measured by f--norm:
min ll(()) r1: (ff(())-r) rr:), =EX
(F.2)
with f(x) == fn(=)) and || 1lg the f--norm (g2 1). This method has been applied to federated learning as q-FFL (Li et al., 2020c) (by assuming r = 0).
Weighted geometric mean (Lootsma al., 1995): this method converts MOO to single-objective formulation by maximizing the weighted geometric mean between elements of the nadir point and the client objectives:
max II fi(=))))))++ such that fi(x)) S qi for any i and a E X,
(F.3)
TEX
where q is called a nadir point, defined as (Lootsma et al., 1995):
qi max fi(z)))
(F.4)
j=1.2.....
with w] = arg min (ax) the optimizer of function ʃz- The A are the weights for each client and they are positive. If we take À = (AI,...,AA)) 1, then it resembles our objective in eq. 3.7.
F.2 Fairmess in Federated Learning
As FL has been deployed to more and more real-world applications, it has become major challenge to guarantee that FL models has no discrimination against certain clients and/or sensitive attributes. Since different participants may contribute differently to the final model's quality, it is necessary to provide fair mechanism to encourage user participation.
Besides the related work we mentioned in the main paper (McMahan et al., 2017; Mohri et al., 2019; et al., 2020b), another direction of research tries directly encourage the involvement of user participation, by providing some rewards to fairly recognize the contributions of clients. For example, Lyu et al. (2020) designed a local credibility mutual evaluation mechanism to enforce good contributors get more credits. Concretely, each client computes the contribution of every other client by investigating the label similarities of the synthetic samples generated by the clients' differential private GANs (Goodfellow et al., 2014). Kang et al. (2020) proposed a pairwise measurement contribution. Reputation scores are kept at each client for all other clients, and are updated by multi-weight subjective logic model. Yu et al. (2020) proposed Federated Learning Incentivizer (FLI) payoff-sharing scheme, which dynamically divides given budget among clients by optimizing their joint utility while minimizing their discrepancy. The objective function takes into account the amount of payoff and the waiting time to receive the payoff. Wang et al. (2020) analyzed the contribution from the data side, and proposed the federated Shapley Value (SV) for data valuation. While preserving the desirable properties of the canonical SV, this federated SV can be calculated with no extra communication overhead, making it suitable for the FL. scenarios.
The above methods alrcady applied some objective functions that reflect the concept of proportional fair- ness, e.g.; payoff proportional to the contribution. However, they mostly apply fixed contributtonnrewward assignment rules, without explicit definitions of proportional fairness or theoretical guarantee.
F.3 Definitions of fairness
Fairness has been perennial topic in social choice (Sen, 1986), communication (Jain et al., 1984), law (Rawls, 1999) and machine learning (Barocas et al., 2017). Whenever we have multiple agents and limited resources, we need fairness to allocate the resources. There have been many definitions of fairness, such as individual fairness (Dwork et al., 2012), demographic fairness, counterfactual fairness and proportional fairness.
In this section, we introduce definitions of fairness from various perspectives including social choice, com- munication and machine learning, and study the implications in the setting of FT..
39

---

Published in Transactions on Machine Learning Research (01/2023)
F.3.1 Social Choice and Law
We review some principles for fairness and justice in social choice (Sen, 1986) and law (Rawls, 1999), which resembles FL: we can treat the shared global model as public policy and clients as social agents.
Utilitarian rule (Maskin, 1978): suppose have clients and their loss functions are fi, the utilitarian rule aims to minimize the sum of the loss functions, e.g.,
min Σ1(0).
(F.5)
with 0 the global model parameters. This utilitarian rule represents the utilitarian philosophy: as long as the overall performance of the whole society is optimal, we call the society to be fair. A utilitarian policy is Pareto-optimal but not vice versa. With model homogeneity, equation eq. F.5 is nothing but the objective for FedAvg (McMahan et al., 2017), although the Fed algorithm may not always converge to the global optimum even in linear regression (Pathak & Wainwright, 2020).
Egalitarian rule (Rawls, 1974; 1999): The egalitarian rule, also known as the maximin criterion represents egalitarianism in political philosophy. Instead of maximizing the overall performance in eq. F.5, an egalitarian wants to maximizing the performance of the worst-case client, i..., we solve the following optimization problem:
min max (O)..
(F.6)
This accords with Agnostic FL (Mohri et al., 2019). The egalitarian problem eq. F.6 may not always be Pareto optimal, o.g., (fi, f2, fs) (1, 1) and (f1, f2, fa) (1. 0.9, 0.8) can both be the optimal solution of eq. F.6, but the former is not Pareto optimal.
F.3.2 Fairness in wireless communications
Since resource allocation common communication, different notions of fairness have also been proposod and studied. We review some common fairness definitions in communication:
Mar-min fairness / Pareto optimal (Bertsckas & Gallager, 1987): this definition says at the fair solution, one cannot simultaneously improve the performance of all clients, which is equivalent to the definition of Pareto optimal. The corresponding algorithm in FL for finding a Pareto optimum is FedMGDA+ (Hu et al., 2022).
Proportional- rule (Kelly, 1997; Bertsimas et al., 2011): proportional fairness aims to find a solution 0* such that for all in the domain:
Σ ( (0') 00,
(F.7)
with in the utility function of client i, e.g., the test accuracy. This problem aims to find policy such that the total relative utility cannot be improved. Proportional fairness has been studied in communictton (c.g. Sco & Lee, 2006) for scheduling but the application in FL has not been seon.
Harmonic mean (Dashti et al., 2013): the method maximizes the harmonic mean of the utility functions of each client, that is, we solve the following optimization problem:
mHBX
Σ. (0)
(F.8)
In a similar vein we can find its optimality condition, assuming the utility set U is convex:
u < 0, for all u EU. (μ))²
(F.9)
Compared to proportional fairness, it simply amounts to squaring the denominator.
40

---

Published in Transactions on Machine Learning Research (01/2023)
F.3.3 Fairness in machine learning
Fairness has been studied machine learning for almost a decade (Barocas al., 2017). A large body of work focuses on proposing machine learning algorithms for achieving different definitions of fairness. These definitions are often incompatible with each other, ie., one cannot achieve two definitions of fairness simultancously. Let us review some common definitions, using classification
illustrating example:
Group fairness / statistioal parity / demographic parity (DP, Dwork et al., 2012; Zemel et al., 2013): this definition requires that the prediction is independent of the subgroup (e.g., race, gender). Denote Y the prediction and as the sensitive attribute, this definition requires Y S, where the symbol I denotes statistical independence. This is the simplest definition of fairness, and probably what people think of at first thought. However, this definition can be problernatic. For instance, suppose subgroup of clients have poor performance (e.g. due to communication, memory), and then to achieve better group fairness one can deliberately lower the performance of high-performing clients, and thus the overall performance is lower. Moreover, DP would forbid us to achieve the optimal performance if the true labels are not independent of the sensitive attribute (Hardt et al., 2016; Zhao & Gordon, 2019).
Equalized odds (EO) (Hardt et al., 2016): this defintion requires demographic parity given each true label class. Define as the random variable for the true label. Equalized odds requires that T for any and equal opportunity requires that Y .. T for some T. Different from DP, this conditioning allows the prediction to align with the true label. In the binary setting, EO and DP cannot be simultancously achieved (Barocas et al., 2017).
Calibration / Predictive Rate Pority (Gebel, 2009): this definition requires that among the samples having a prediction score Y, the expectation the true label T should match the prediction score, ie., E[[[y] In the context of fairness, calibration says that - s|Y. Under mild assumptions, calibration and EO cannot be simultancously achieved (Pleiss et al., 2017). Similarly, calibration and DP cannot be simultaneously achieved.
Individual fairness (Dwork et al., 2012): this concept requires that similar samples, as measured by some metric, should have similar predictions.
Counterfactual fairness (Kusner et al., 2017): this definition requires that from any sample, the prediction should be the same had the sensitive attribute taken different values. It follows the notion of counterfactual from casual inference (Pearl, 2000).
Accuracy parily (Zalar et al., 2017): the accuracy for each group remains the same.
Since many concepts conflict with each other (Barocas al., 2017), there is no unified definition of fairness.
In light of this, dynamical definition of fairness has been proposed (Awasthi et al., 2020)- Algorithms for achieving different definitions of fairness include mutual information (Zenel et al., 2013), representation learning (Zemel et al., 2013; Zhao & Gordon, 2019) and Rényi correlation (Baharlouei et al., 2019).
41


Reviews:
[{"review_id": "hVccITjknN", "reviewer": "Reviewer_zcsx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n- This work provides a uniformed framework for fair FL (Equation 2.9) that generalizes prior works (e.g. q-FFL, TERM, AFL).\n- This work provides a new perspective of fairness in federated learning (namely proportional fairness). \n- Experimental results seem to show that the proposed method achieves stronger average / worst 10% performance.\n\nWeakness:\n\n- The definition of proportional fairness seems more closely related to some kind of equilibrium rather than fairness. Specifically, what is the domain $\\mathcal{U}$ here. By definition, it could be the case where, for example taking $u$ as the train accuracy, we have $u_1^*=1$ while $u_2^*=0$, without specifying what $\\mathcal{U}$ is, which does not seem to be consistent / similar to other fairness definitions like representation disparity.\n- It is not clear to me why we average the loss over the batch before applying $\\-log_{[\\varepsilon]}$ in line 9 of Algorithm 1. Could the authors explain why not directly apply the proposed loss function and then average the loss over a batch?\n- The authors didn't provide formal fairness guarantee (for example, how does the model output by the algorithm satisfy the proportional fairness definition).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- This paper proposes a novel fair federated learning objective based on the notion of proportional fairness. The proposed framework extends q-FFL and capture a case where q-FFL fails to capture.\n- The authors provide convergence guarantee for the proposed objective.\n- Empirical results from 4 different datasets show that the proposed method outperforms previous baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Providing formal fairness guarantee would be great. With the current definition, it is not clear to me that 1. on the train distribution, how is proportional fairness different from perfect prediction (Note that different from other fairness metrics like representation parity or demographic parity where perfect prediction is just a special case for achieving fairness, proportional fairness seems to be suggesting a unique solution globally, which is essentially perfect prediction)? 2. on the test distribution, does the proposed algorithm provides any guarantee?\n- Could the authors explain how proportional fairness relate to other fairness notions? (Like representation disparity, the one used in q-FFL)\n- Could the authors provide ablation study on how the choice of $q$ affects the comparison between q-FFL and the proposed algorithm. As the authors stated, the proposed method could be viewed as 1-fairness. Therefore, I'm wondering whether we could view it as a special case of q-FFL by setting q to be values close to -1.\n\nNit:\n- Section 2.1: 'approach to for' -> 'approach for'\n- Section 2.2: 'constract' -> 'contrast'", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KJjepCAvFv", "reviewer": "Reviewer_CEYg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall it is a work of high quality. The paper proposes a new fairness notion for federated learning and conducts a comprehensive and solid analysis of the proposed notion. The connection between the proposed notion and the Nash bargaining solution makes the whole story quite convincing. The experiments using both image and language data verify that the developed objective function and algorithm indeed achieve proportional fairness. \n\nThe only issue I have is that the fairness notions in federated learning are quite different from those in the traditional machine learning context, like demographic parity, equal opportunity, etc. The authors can include a paragraph in the introduction for explaining their differences to the audience from general fair machine learning fields.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new fairness notion for federated learning, named proportional fairness, which is rooted in cooperative game theory. The paper first presents a unified framework of existing fairness notions. Then, the paper shows the connection between a special case of $\\alpha$-fairness and the Nash bargaining solution, which leads to the notion of proportional fairness. The idea of proportional fairness is that the average relative utility cannot be improved anymore. The paper shows that proportional fairness achieves a balance between maximizing the average and the worst-case utilities. Then, the paper derives the objective function for achieving proportional fairness, develops the PropFair algorithm for federated learning, and analyzes its convergence. Experiments verify the properties of the PropFair algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Add a paragraph in the introduction to explain the difference between fair federated learning and general fair machine learning.\n\nAdd a notation table, since there are many notations in the paper.\n\nBoth “eq” and “equation” are used in the paper. The notations should be consistent throughout the paper.\n\nExplain why in Section 3.1.1 the authors consider both minimizing and maximizing the same objective function.\n", "broader_impact_concerns": "I have no concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CgoxdWaghR", "reviewer": "Reviewer_zYYU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general, I find the idea of thinking about different notions of fairness in federated learning is interesting. This paper proposes proportional fairness, formulates another fair FL objective, discusses its solvers, provides some analysis, and conducts experiments. I like the unified view of summarizing some previous objectives using generalized mean, and I also enjoyed reading the dual formulations. My major concerns are as follows.\n\n* It is not clear what proportional fairness means in practice, and what additional benefits it has relative to prior works. It is an interesting new objective, but the implications of minimizing such a formulation are not well illustrated. There are some nice mathematical interpretations of the proposed objective, but intuitively why proportional fairness is important is unclear. What are the limitations of previous fairness definitions? It provides a failure case of AFL on a simple problem, but does not discuss how/why the proposed approach can prevent such deficiencies. Throughout the paper, the submission measures fairness similarly to previous works (e.g., how uniform the performance is, and how good the tail performance is), and I am wondering why PropFair is better than q-FFL/TERM in terms of optimizing for tail performance.\n\n\n* I am not sure if I understand why the convergence of PorpFair can follow the convergence of FedAvg. One major challenge is that the local mini-batch gradient at each local step is not an unbiased estimator of the full local gradient, unless f_i in Eq. (4.1) is the actual average loss of all samples on client i (which may be very expensive if there are many samples or computing f_i is costly). \n\n    Please correct me if I am wrong. I briefly checked the proof, and it seems that In Algorithm 1, if K_i batches mean K_i mini-batches, then the current proof cannot go through, due to the issue I mentioned above. \n\nOthers:\n\n* This submission mentions the equivalence between PropFair and Nash Bargaining solutions. It would be better if the paper can further explain why readers should care about such equivalence, as well as those axiomatic characterizations. Similarly, it spends much text on multi-objective optimization, but not clear how this is connected to the main message of the paper.\n\n* section 2.4: ‘when s’/s’’ is convex’—what is s?\n\n\n* after theorem 4.2: What does ‘uniform aggregation for Adam-type methods’ mean? It is a bit confusing because the discussion jumps from FedAvg to FedAdam, but the convergence here doesn’t consider adaptive optimizers. I am also wondering if it is easy to extend Reddi et al 2018 to support different number of local steps and aggregation by p_k (as those don’t seem to require lots of changes of the proof Reddi et al, but i am just guessing). It would be better to make this point more clear.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In general, I find the idea of thinking about different notions of fairness in federated learning is interesting. This paper proposes proportional fairness, formulates another fair FL objective, discusses its solvers, provides some analysis, and conducts experiments. I like the unified view of summarizing some previous objectives using generalized mean, and I also enjoyed reading the dual formulations. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. clearly discuss the rationale of mentioning NBS (along with axiomatic characterization) and multi-objective optimization, and why the dual view is important/how that helps \n\n2. address my concerns about the correctness of convergence proof\n\n3. explain more clearly why proportional fairness is important, and how it addresses limitations of previous fairness notions [because the paper in its current form is talking about what it is/how to interpret it, instead of why it is needed]", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers had positive feedback on the paper, but suggested that the authors address certain issues in order to improve the clarity and completeness of the work. These issues include providing formal fairness guarantees, clarifying the relationship between the proposed fairness notion and other fairness notions, providing more details on the implementation and experimental setup, and fixing the convergence proof. The authors successfully addressed these issues during the revision. I recommend accepting the paper as it is.
Decision: Accept (poster)