AdaFed: Fair Federated Learning via Adaptive Common Descent Direction
Authors: Shayan Mohajer Hamidi
EN-HUI YANG
Venue: Accepted by TMLR ()

Abstract: Federated learning (FL) is a promising technology via which some edge devices/clients
collaboratively train a machine learning model orchestrated by a server. Learning an unfair
model is known as a critical problem in federated learning, where the trained model may
unfairly advantage or disadvantage some of the devices. To tackle this problem, in this work,
we propose AdaFed. The goal of AdaFed is to find an updating direction for the server along
which (i) all the clients’ loss functions are decreasing; and (ii) more importantly, the loss
functions for the clients with larger values decrease with a higher rate. AdaFed adaptively
tunes this common direction based on the values of local gradients and loss functions. We
validate the effectiveness of AdaFed on a suite of federated datasets, and demonstrate that
AdaFed outperforms state-of-the-art fair FL methods.

Published in Transactions on Machine Learning Research (01/2024)
AdaFed: Fair Federated Learning via Adaptive Common Descent Direction
Shayan Mohajer Hamidi
smohajer@nuaatrrloo.cr
Deportment of Electrical and Computer Engineering University of Waterloo
En-Hui Yang
chyang@uwatertoo..om
Department of Electricol and Computer Engincering University of Waterloo
Reviewed on OpenReview: https: // openreview. net/ formff id= PFecyPPFUU
Abstract
Federated learning (FL) is promising technology via which some edge devices/clients collaboratively train machine learning model orchestrated by server. Learning unfair model is known critical problem in federated learning, where the trained model may unfairly advantage or disadvantage some of the devices. To tackle this problem, in this work, we propose AdaFed. The goal of AdaFed is to find an updating direction for the server along which (i) all the clients' loss functions are decreasing; and (ii) more importantly, the loss functions for the clients with larger values decrease with a higher rate. AdaFed adaptively tunes this common direction based on the values of local gradients and loss functions. We validate the effectiveness of AdaFed suite of foderated datasets, and demonstrate that AdaFed outperforms state-of-the-ard fair FL methods.
1 Introduction
Conventionally, a machine learning (ML) model is trained in centralized approach where the training data is available at data center or a cloud server. However, in many new applications, devices often do not want to share their private data with a remote server. As a remedy, federated learning (FL) was proposed in McMahan et al. (2077) where each device participates in training using only locally available dataset with the help of a server. Specifically, FI., devices share only their local updates with the server, and not their raw dataset A well-known setup to carry out such decentralized training is FedAvg MMMahan al. 22117) which combines local stochastic gradient descent (SGD) each client with iterative model averaging. The server sends the most recent. global model to some selected clients (Eichner et al. 2019 Wang et al.) 2021a) and then these clients perform a number of epochs of local SGD on their local training data and send the local gradients back to the central server. The server then finds the (weighted) average of the gradients to update the global model, and the process repeats.
In FedAvg, the vector of averaged gradients computed by the server in fact a common dircction along which the global model is updated. However, finding the common direction in this manner may result in a direction which is not descent for some clients. Consequently, the learnt model could perform quite poorly once applied to the private dataset of the clients, yielding an unfair global model (Li et al. 2019a Bonawitz/ et al. 2019 Kairouz et al.) 2021); that is, although the average accuracy might be high, some clients whose data distributions differ from the majority of the clients are prone to perform poorly on the learnt. model.
One possible method find a direction that is descent for all the clients is to treat the FL task as a multi-objective minimization (MoM) problem Hu al. (2022). In this setup, a Pareto-stationary solution of the MoM yields descent direction for all the clients. However, having a common descent direction is not.

---

Published in Transactions on Machine Learning Research (01/2024)
enough per to train fair model with uniform test accuracies across the clients This is because data heterogeneity across different clients makes the local loss functions vary significantly in values, and therefore those loss functions with larger values should decrease with a higher rate to learn fair model.
To address the above-mentionee issues and to train a fair global model, in this work, we propose AdaFed. The aim of AdaFed to help the sever to find common direction d, (i) that descent. for all the clients, which is a necessary condition to decrease the clients' loss functions in the SGD algorithm; and (ii) along which the loss functions with larger values decrease with higher rates. The latter is to enforce obtaining global model with uniform test accuracies across the clients.
We note that if the directional derivatives of clients' loss functions along the normalized common direction dr are all positive, then - is a common descent direction for all the clients. As such, AdaFed adaptively tunes d such that these directional derivatives (i) remain positive over the course of FL process, and (ii) are larger for loss functions with higher values enforcing them to decrease more during the global updation by the server.
The contributions of the paper summarized as follows:
We introduce AdaFed, a method to realize fair FL via adaptive common descent direction.
We provide closed-form solution for the common direction found by AdaFed. This is in contrast with many existing fair FL. methods which deploy itcrative or generic quadratic programming methods.
Under some common assumptions in FL literature, we prove the convergence of Adaled under different FL sctups a Pareto-stationary solution.
By conducting thorough experiments over seven different datasets (six vision datasets, and a language one), we show that AdaFed can yield a higher level of fairness among the clients while achieving similar prediction accuracy compared to the state-of-the-art fair FL algorithms.
The experiments conducted in this paper evaluate many existing fair FL algorithms over different datasets under different FL setups, and therefore can pave the way for future rescarches.
2
Related Works
There are many different perspectives in the literature combat the problem of fairness in FL. These methods include client selection (Nishio & Yonetani
2022 Yang al. 2021 contribution Evaluation (Zhang et al. 2020 Lyu et al. 2020 Song et al. 2021 Le et al. 2021), incentive
2019 Huang al. 2020a.
mechanisms (Zhang et al.) 2021 Kang et al. 2019 Ye et al. 2020 Zhang et al. 2020)]. and the methods based on the loss function. Specifically, our work falls into the latter category. In this approach, the goal is to attain uniform performance across the clients in terms of test accuracy. To this end, the works using this approach target to reduce the variance of test accuracy across the participating clients. In the following, we briefly review some of these works.
One of the pioneering methods in this realm is agnostic federated learning (AFL) (Mohri et al. 2019). AFL optimizes the global model for the worse-case realization of weighted combination of the user distributions. Their approach boils down to solving a saddle-point optimization problem for which they used a fast stochastic optimization algorithm. Yet, AFL performs well only for a small number of clients, and when the size of participating clients becomes large, the generalization guarantecs of the model may not be satisfied. Du et al. (2021) deployed the notation of AFI, and proposed the AgnosticFaii Fair algorithm. Specifically, they linearly parametrized model weights by kernel functions and showed that AFL can be viewed as a special case of AgnosticFair. To overcome the generalization problem in AFL, f-fair federated learning (q-FFL) (Li et al.
2019a proposed to achieve more uniform test accuracy across users. The main idea of F-FFL stemmed
Simmilarly other fields like ML [aaocaas al. 2017), communications Huaizhou al. 2013). and justice (Rawss 2020
the notion of fairness does not have unique definition in FL. However, following (Li ct
2019a 2021 wc standard
deviation of the clients" accuracies and some other metrics discussed Section 7 measure uniform the global model performs across the clients. Please refer Appendix C for more in-depth discussions.
2

---

Published in Transactions on Machine Learning Research (01/2024)
from fair resource allocation methods in wireless communication networks. Afterward, Li et al. developed TERM, a tilted empirical risk minimization algorithm which handles outliers and class imbalance in statistical estimation procedures. Compared to q-FFL, TERM has demonstrated better performance in many FL applications. Deploying a similar notion, Huang et al. (2020b) proposed using training accuracy and Trequency to adjust weights of devices to promote fairness. Furthermore, FCFC Cui et al. (202T) minimizes the loss of the worst-performing client, leading to version of AFL. Later, Li al. (2021 devised Ditto, a multitask personalized FL algorithm. After optimizing global objective function, Ditto allows local devices to run more steps of SGD, subject to some constraints, to minimize their own losses. Ditto can significantly improve testing accuracy among local devices and encourage fairness.
(2020a)
Our approach is more similar to + (Hu et al. 2022), which treats the FL task as multi-objective optimization problem. In this scenario, the goal is to minimize the loss function of each FL client simultaneously. To avoid sacrificing the performance of any client, FedMGDA+ uses Parcto-stationary solutions to find a common descent direction for all selected clients.
3
Notation and Preliminaries
3.1
Notation
We denote by [K] the set of integers (1, 2....... .K.. In addition, we define [s*]ae(K] f2.... .x} for a scalar/function f. We use bold-symbol small letters represent vectors. Denote by u, the i-th element of vector For two vectors u, D E R,, say u S a iff u, S v, for Vi [d]. ie., two vectors compared w.r.t. partial ordering. In addition, denote by u their inner product, and by proj,(b) an the projection of v onto the line spanned by u.
3.2 Preliminaries and Definitions
In Hu et al. 2022),, authors demonstrated that FL can be regarded as multi-objective minimization (MoM) problem. In particular, denote by f(0) = {ff((0){k(j]] the of local clients' objective functions. Then, the aim of MoM is to solve
0* arg min f(0),
(1)
where the minimization is performed w.r.t. the partial ordering. Finding 0" could enforce fairness among the users since by setting setting 0 = 0*, it is not possible to reduce any of the local objective functions fx without increasing at least. another one. Here, 0* called a Pareto-optimal solution of Equation (1). Tn addition, the collection of function values (O"))) of all the Pareto points 0* is called the Pareto front.
Although finding Pareto-optimal solutions be challenging, there are several methods to identify the Pareto-stationary solutions instead, which are defined as follows:
Definition 3.1. Parcto-stationaryy MMuka 1980): The vector 0* is said to be Parcto-stationary iff there exists convex combination of the gradient-vectors (0"))()) which is equal to zero; that is, Σ \u. (0") = 0, where À 2 0, and Σk= As- 1.
Lemma 3.2. MMuaai 1980 Any Pareto-optimal solution is Pareto-stationary. On the other hand, if all (O))))e 's are convex, then any Pareto-stationary solution is weakly Pareto optimal F
There are many methods the literature to find Pareto-stationary solutions among which we elaborate on two well-known ones, namely linear scalarization and Multiple gradient descent algorithm (MGDA) (Mukai 1980: Fliege & Svaiter 2000 Désidéri 2012).
20* callod weakly Pareto-optimal solution of Equation if there docs not exist any such that f(0) < f(0)); meaning that, is not possible improve all of the objective functions f(0)). Obviously, any Pareto optimal solution is also weakly Pareto-optimal but the converse may not hold.
3

---

Published in Transactions on Machine Learning Research (01/2024)
Linear scalarization: this approach is essentially the core principle behind the FedAvg algorithm. To elucidate, in Avg,vg, the server updates 0 by minimizing the weighted average of clients' loss functions:
min f(0) (xfx(())
(2)
where the weights [AR are assigned by the server and satisfy Σk=1 Au 1. These fixed {Ac are assigned based on priori information about the clients such the size of their datasets. We note that different values for {>R yield different Pareto-stationary solutions.
Referring to Definition 3.1 any solutions of Equation (2) is a Pareto-stationary solution of Equation T To perform FedAvg, at iteration t, client k, k E [K] sends its gradient vector ga (0,) to the server, and server updates the global model as
K Σ
Oc+1 0, 22, where D.
Ax (0z).
(3)
However, linear scalarization can only converge to Pareto points that lie on the conver envelop of the Pareto front [Boyd& & Vandenberghe 2004). Furthermore, the weighted average of the gradients with pre-defined weights yields a vector D, whose direction might not be descent for all the clients; because some clients may have conflicting gradients with opposing directions due to the heterogeneity of their local datasots (Wang 2021b As a result, FedAvg may result in an unfair accuracy distribution among the clients (Li el al.
et al.
2019a Mohri al. 2019).
To mitigate the above issuc, Hu et al. 2022 proposed to exploit MGDA algorithm in FL to converge to a fair solution on the Pareto front. Unlike linear scalarization, MGDA adaptively lunes (AAkeeKK by finding the minimal-norm element of the convex hull of the gradient vectors defined as follows (we drop the dependence of Di to O, for ease of notation hereafter)
MGDA:
K
K
G = {g E
R
AuDu: d
2
0;
Σ k=1
A
1).
(4)
k=1
Denote the minimal-norm element of G by dG).. Then, either (i) (()) and therefore based on Lemma 3.2 (G) is Pareto-stationaty point; (ii) dG)) * and the direction of og)) is a common descent direction for all the objective functions {f& (0) [E([K] Désiidéri 2009), meaning that all the directional derivatives {ou ((G))x][]] are positive. Having positive directional derivatives is a necessary condition to ensure that the common direction is descent for all the objective functions.
4 Motivation and Methodology
We first discuss our motivation in Section and then elaborate on the methodology Section 4.2
4.1
Motivation
Although any solutions on the Pareto front fair the sense that decreasing one of the loss functions not. possible without sacrificing some others, not all of such solutions impose uniformity among the loss functions (see Figure lap. As such, aim to find solutions on the Pareto front which enjoy such uniformity.
First note that having a common descent direction is necessary condition to find such uniform solutions; but not enough. Additionally, we stipulate that the rate of decrease in the loss function should be greater for clients whose loss functions are larger. In fact, the purpose of this paper is to find an updation direction for the server that satisfies both the following conditions at the same time:
Condition (I): It is descent direction for all {fr (fa(0) which necessary condition for the loss functions to decrease when the server updates the global model along that direction.
4

---

Published in Transactions on Machine Learning Research (01/2024)
fi
MGDA may converge to any points on the Parelo front.
g1
(0) and (2(0) are moore uniform region.
91
g1.b(G)
b
b(9)
Pareto front
(2(0)
92- b
92
(a)
(b)
Figure 1: (a) The Pareto front for two objective functions f1) and fz(0) is depicted. MGDA may converge to any points on the Pareto front. (b)-(c) Mlussraation of convex hull g and minimal-norm vector d()) for two gradient vectors di and g2- In (b), || 1 l|g2lle, where the direction of (g) is more inclined toward 01- In (c), ll 2 1, where the direction of d(g) is the same that of the bisection of gi and g2-
Condition (IT It is more inclined toward the clients with larger losses, and therefore the directional derivatives of loss functions over the common direction are larger for those with larger loss functions.
To satisfy Condition (I), it is enough to find d()) using MGDA algorithm (as Hu et al. 2022 uses MGDA to enforce fairness in FL setup). Nevertheless, we aim to further satisfy Condilion (IT) on top of Condition (1). To this end, we investigate the direction of d(G), and note that is more inclined toward that of min (lnn l [E[K]. For instance, consider the simple example depicted in Figure 1b where || < 1l
The Convex hull G and the dg) are depicted for gi and Ø2. As seen, the direction (()) is mostly influenced by that of g1-
However, this phenomenon is not favourable for satisfying Condition (II) since after some rounds of commu- nication between the server and clients, the value of becomes small for those objective functions which are close to their minimum points. Consequently, the direction of dg)) is mostly controlled by these small g's, which is undesirable. Note that ga d(G) represents how fast (0) changes changes in the direction of (g). In fact, the direction of (g) should be more inclined toward the gradients of those clients with larger loss functions.
One possible solution could be to naively normalize {B&]εeK by their norm to obtain [|o=|| )E[K] whose convex hull is denoted by Goorm, and then use this normalized set of gradients to find d (gnorm). Yet, the normalization makes all the {Øk ((Guorm) [NE[K] equal (see Figure Ic which is still undesirable as the rate of decrease becomes equal for all (f((O)))kE[K)
gr
Based on these observations, the gradient vectors should be somehow scoled one aims also satisfy Condition (II). Finding such scaling factor is not straight-forwate in general. To tackle this issue, and to be able to find a closed-form formula, we find the minimal-norm vector in the convex hull of mutually-orthogonal scaled gradients instead, and prove that this yields a common direction for which both Conditions (I) and (IT) are satisfied.
4.2 Methodology
To devise appropriate scaling as explained above, we carry out the following two phases.
4.2.1
Phase 1, orthogonalization
In order to be able to find a closed-form formula for the common descent. direction, in the first phase, we orthogonalize the gradients.
Once the gradient updates [BEK]] are transmitted by the clients, the server first generates a mutually orthogonal set (ōx [ that spans the same K-dimensional subspace in Rd as that spanned by {øx [gæ]k][K]-
Here, orthogonaltty the sense of standard inner product Fuclidean space.
5

---

Published in Transactions on Machine Learning Research (01/2024)
To this aim, the server exploits modified Gram-Schmide Schmidt orthogonalization process over (gktReja] in the following manner
gi g1/lSk|
(5)
d Bk > k-1 proj (gk)
g.
for 2.3...., K,K,
(6)
l/2/ Σ Ei=1
B.-Bi
9. 8:
where y > 0 is scalar.
Why such orthogonalization is possible?
First, note that the orthogonalization approach in phase 1 is feasible if we assume that the K gradiont vectors {Dx ]εeC]] are linearly independent. Indeed, this assumption is reasonable considering that (i) the gradient vectors {gx [e(K]] are K vectors in d-dimensional space, and d >> K for the current deep neural networks (DNNs and (ii) the random nature of the gradient vectors due to the non-iid distributions of the local datasets. The validity of this assumption is further confirmed in our thorough experiments over different datasets and models.
4.2.2 Phase 2, finding optimal X
In this phase, aim to find the minimum-norm vector in the convex hull of the mutually-orrtoogonal gradients found in Phase (I).
First, denote by the convex hull of gradient vectors {gk hKENK
obtained in Phase 1; that is,
K
K A
g = {gg E
Rd
Angis
d 2 0;
1}.
A=1
In the following, we find the minimal-norm element in G and then we show that this element is descent direction for all the objective functions.
Denote by x the weights corresponding to the minimal-norm vector G. To find the weight vector X", we solve
= arg min geg
|
(8)
which accordingly finds X" For an element G, have
K
K
gg
A
12
(9)
where used the fact that {gk ME[K] orthogonal.
To solve Equation [), we first ignore the inequality A 2 0, for k E [K], and then we observe that this constraint will be automatically satisfied. Therefore, we make the following Lagrangian to solve the minimization problem in Equation
L(ū, A) 1g
Σ Av -1-1
Σ
(10)
Hence,
aL 0Λ
2 llkk a.
(11)
4The reason for such normalization satisfy Conditions I and II. This will be proven later in this section. 5 Also, that tackle non-iid distribution user-specific data, it is common practice that selects different. subset, of clients in each round (McMahan et. 2017).

---

Published in Transactions on Machine Learning Research (01/2024)
and by setting Equation 11 to zero, we obtain:
X
(12)
2|
2
1
On the other hand, since Σ A 1, from Equation
12 we obtain
2
(13)
1
from which the optimal X is obtained follows
for k E [K].
(14)
0 E
Note that 2g > 0, and therefore the minimum norm vector we found belongs to G.
can calculate D, Ek=1 Aigi the minimum norm element in the convex hull G. In the following (Th (Theorem 4.1 we show that the negate of d, satisfies both Conditions (T) and (IT).
Using the X found in 14
Theorem 4.1. The negate of D. Di=1 Aigh satisfies both Conditions (I) and (II).
Proof. We find the directional derivatives of loss functions [JaJKE[K] over d.,. For Vk E [K] we have
k-1
gk D.
gi (Ifiel
Σ
Ok O:
proj (0k)
(15)
De ge
k-1
A
Sk g
+
Ghe 9:
X 11
(16)
9i
g g.
1=1
1-
a
[fall
9k gi
0
0k 0a
(17)
2
9. g
2
0: 0:
| 0,
2 fxl
(18)
2k=1
11
where (i) Equation 15 is obtained by using definition of qk in Equation G (ii) Equation 16
follows from
the orthogonality of L A= vectors, and (iii) Equation
is obtained by using Equation 12
As seen in Equation 18 the directional derivatives over d, are positive, meaning that the direction of dd is descent for all [ In addition, the value of these directional derivatives are proportional to [/a|", This implies that if the server changes the global model in the direction of D,, the rate of decrease is higher for those functions with larger loss function values. Thus, - satisfies both Conditions (I) and (II). J
Remark 4.2. As seen, Equation 14 yields a closed-form formula to find the optimal weights for the orthogonal scaled gradients [gi]kejk]] based on which the common direction is obtained. On the contrary, +edMGDA+ (Hu et al.) 2022) solves an iterative algorithm to find the updating directions. The complexity of such algorithms is greatly controlled by the size of the model (and the number of participating devices). As the recent. DNNs are large in size, deploying such iterative algorithms slows down the FL process. Furthermore, note that the computational cost of proposed algorithm is negligible (see Appendix F for details).
5 The AdaFed algorithm
At iteration t, the server computes o, using the methodology described in Section global model as
4.2 and then updates the
0+1 0: - Dr
(19)
Similarly to the conventional GD, we note that updating the global model as 19 necessary condition have f(0+1)) f().). Tn Theorem 5.1 we state the sufficient condition to satisfy f(0+1) S f0.)-
7

---

Published in Transactions on Machine Learning Research (01/2024)
Theorem 5.1. Assume that f = [ejk are L-Lipschitz smooth. If the step-size na [0, E. min(/fa/ Meeelll then f(0++1) & f()),, and equality is achieved iff d, = 0.
Proof. all the ([a)kejk] are I-smooth, then
L 10.+1 - 02112-
5(0 f(0,) + (0 00)
(20)
Now, for client [K], by using the update rule Equation 19 in Equation
20
we obtain
fa S (O.) - 0r D. + 1/ L 2
p 10.12.
(21)
To impose (0+++)) fs,())), we should have
K
| 1
9h d. 2 1/1 2
0z
Bk d. 2
(22)
2
k=1
||gi=l2
K
2i=1
lle
|
T)
(23)
k=1
Σ
k=
K
1Ball
2 4 S T, [al1
(24)
Therefore, if the step-size 1/ E [0, min (7 ]ε]]]], then f(0++1) S f(O)).
Lastly, similar to many recent FL algorithms McMahan et al. (2017): Li et al. (2019a); Hu et al. (022 wo allow each client to perform a couple of local epochs e before sending its gradient update to the server.
this case, the pseudo-gradients (the opposite of the local updates) will be abusively used as the gradient vectors. It is important to note that we provide a convergence guarantee for this scenario in Section 5.1 We summarize AdaFed in Algorithm
Remark 5.2. When 1, alternative approach is to use the accumulated loss rather than the loss from the last iteration in line (9) of Algorithm [ However, based on our experiments, observed that using the accumulated loss does not affect the overall performance of the algorithm, including its convergence speed, accuracy and fairness. This stands in contrast to the use of pseudo-gradients, which serves clear purposes of accelerating convergence and reducing communication costs.
5.1 Convergence results
In the following, we prove the convergence guarantee of AdaFed based on how the clients update the local models: (i) using SGD with e = 1, (ii) using GD with > 1, and (iii) using GD with e = 1. Of course the strongest convergence guarantee is provided for the latter case.
Theorem 5.3 (e = & local SGD). Assume that f [fe]ke[K]] are L-Lisschitz continuous and L-Lipschitz smooth, and that the global step-size N satisfies the following three conditions: (i) me E (0, 2. (ii)
lim Et 7/ 20, and (iii) 1om ΣT THo < oo; where of ElllÄA ".A, is the variance of stochastic common descent direction. Then
lim T
min EI
+
(25)
t=
Theorem 5.4 (e > 1 & local GD). Assume that f= [[]j]]] are LLLischitzz continuous and L-Lipschitz
smooth. Denote by 7) and the global and local learning rates, respectively. Also, define & = ||> - A:ll, where A is the optimum weights obtained from pseudo-gradients after local epochs. We have
lim T-00
min D + 0.
(26)
8

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm AdaFed
Input: Number of global epochs T, number local epochs e, global learning rate T), local learning rate
17, initial global model o. local datasets {D&)eek) do
for t= 0, 1,.....,
3: Server randomly selects subset of devices S and sends 0g to them.
4: for device E Sz in parallel do [local training]
5: Store the value 0, in miics that is mit f- 0,. for e epochs do Perform (stochastic) gradient descent over local dataset D update: 0, - 0- 0.,-n1V.i(0,, end for Send the gpeudo-gradiens Ok Oint 0, and local loss value (0i) to the server. end for
10:
11:
for k == 1,2...., S do
12:
Find g form Equations and 6
13:
end for
14: Find X' from Equation 14
15: Calculate D; = Σx=1 Azgk-
16:
0,+1 + 0: 1/
17:
end for
18: Output: Global model Or.
if the following conditions are satisfied: (i) ne (0, 1. (ii) limy- oo0 Eizo + co, (iii) lim, Joc - 0, (iv) lim 1) + 0, and (v) lim,- 6--0
Before introducing Theorem 5.5 we first introduce some notations. Denote by 0 the Pareto-stationary
solution sel of minimization problem arg ming f()). Then, demote by 0, the projection of 0, onto the set v;
that is, 0 arg mingee 00 - 01..
Theorem 5.5 (e = 1 & local GD). Assume that f [ are LLiischitzz continuous and a-convex, and that the global step-size π satisfies the following two conditions: (i) limy-+00 Σj= 77 co, and (ii)
lim E/= ni < co. Then almost surely 0 + 0;; that is,
P lim (0, 0,) =0) =1, 60000
(27)
where P(E) denotes the probability of event E.
The proofs for Theorems 5.3 to 5.5
are provided in Appendices A.1 to A.3 respectively, and we further discuss that the assumptions we made in the theorems are common in the FL literature.
Note that all the Theorems 5.3 optimization problem in Equation are reaching to Pareto-optimal point (Désidéri 2009). On the other hand, Theorem 5.5 explicitly provides this convergence guarantee in an almost surely fashion.
5.5 provide some types of convergence to Pareto-optimal solution of
Specifically, diminishing in Theorems 5.3 and 5.4
implies that
6
AdaFed features and a comparative analysis with FedAdam
6.1
AdaFed features
Aside from satisfying fairness among the users, we mention some notable features of AdaFed in this section.
The incquality f(0++1) < f(0)) gives motivation to the clients to participate in the FL task as thoir loss functions would decrease upon participating. In addition, since the common direction is more inclined toward
In general, the Pareto-stationary solution of multi-ohjective minimization problem forms with cardinality infinity Mukai 1980
9

---

Published in Transactions on Machine Learning Research (01/2024)
that of the gradients of loss functions with bigger values, new client could possibly join the FL task in the middle of FL process. In this case, for some consecutive rounds, the loss function for the newly-joined client decreases more compared to those for the other clients.
The parameter y is a hyper-parameter of AdaFed. In fact, different y values yield variable levels of fairness. Thus, y should be tuned to achieve the desired fairness leve Tn general, a moderate y value enforces a larger respective directional derivative for the devices with the worst performance (larger loss functions), imposing more uniformity to the training accuracy distribution.
Lastly, we note that AdaFed is orthogonal to the popular FL, methods such as Fedprox (Li et al. 2020b and q-FFL (Li et al. 2019a). Therefore, it could be combined with the existing FL algorithms to achieve a better performance, especially with those using personalization (Li et al. 2021
6.2 Comparison with FedAdam and its variants
Similarly to AdaFed, there are some FL, algorithms in the literature in which the server adaptively updates the global model. Despite this similarity, we note that the purpose of AdaFed is rather different from these algorithms. For instance, let us consider FedAdam (Reddi et al.) 2020); this algorithm changes the global update rule of FedAvg from one-step SGD to one-step adaptive gradient optimization by adopting an Adam optimizer on the server side. Specifically, after gathering local G. [ ExES, of, the server updates the global model by Adam optimizer:
and finding their average as
m: mmm, + (1 (11-11)0 31)
(28)
V, = 3,0,-1 + (1- B2)
(29)
m.
0++1 = 0, +
(30)
U +
where $1 and 82 are two hyper-parametors of the algorithm, and e is used for numerical stabilization purposc. We note that other variants this algorithm, such as Fed FedAragaa and Fed Yogi (Reddi et al. 2020 and FedAMSGrad (Tong et al. 2020), involve slight changes in the variance term ot-
The primary objective of FedAdam (as well as its variants) is to enhance convergence behavior Reddi et al. 2020); this is achieved by retaining information from previous epochs, which helps prevent significant fluctuations in the server update. In contrast, AdaFed is designed to promote fairness among clients. Such
differences could be confirmed by comparing Algorithm | with Equations (28 to (30
7 Experiments
In this section, we conclude the paper with several experiments to demonstrate the performance of AdaFed, and compare its effectiveness with state-of-the-art alternatives under some performance metries.
Datascts: We conduct a thorough set of experiments over seven datasets. The results for four datasets, namely CIFAR-10 10 and CIFAR-100 Krizhevsky et al.] 2009), FEMNIST (Caldas et al. 2018) and Shakespear McMahan et al., 2017) are reported in this section; and those for Fashion MNIST (Xiao et al. 2017), Tiny IinylmageNet (Le & Yang, 2015), CINIC-10 (Darlow et al. 2018) are reported in Appendix [ Particularly, in order to demonstrate the effectiveness of AdaFed in different FL scenarios, for each of the datasets reported in this section, we consider two different FT. setups. In addition, we tested the effectiveness of AdaFed over a real-world noisy datasct, namely ClothingIM (Xiao et al. 2015), in Appendix [
Benchmarks: We compare the performance of AdaFed against various fair FL algorithms in the literature including: q-FFL (Li et al. 2019a). TERM (Li et al.) (220a)), FedMGDA+ (Hu et al.) 2022). AFL (Mohri et al.] 2011), Ditto (Li et al. 2021). FodFA (Huang et al.] 2020b). and lastly FodAvg (McMahan al. 2017
In our experiments, we conduct grid-search find the best pypee-paaraeeerss for each of the benchmark
Most (if not all) of the fair FL methods introduce extra pyper-paramcter to tunc order establish trade-off between fairness and accuracy, for instance: (i) in FEDMGDA+ (Hu et 2022 ,, (ii) g Q-FFI & FFL [Li al. 2019a and (iil)
in TERM [T.i al. 2020a). Similarly, AdaFed introduces new parameter to make this trade-off.
10

---

Published in Transactions on Machine Learning Research (01/2024)
Table 1: Test accuracy on CIFAR-10. The reported results are averaged over different random seeds.
Setup
Setup
Algorithm
a
Worst 5%
Best 5%
Worst 10%
Best 10%
FedAvg
46.85
3.54
19.84
69.28
63.55
5.44
53.40
72.24
Q-FFL
46.30
3.27
23.39
68.02
57.27
5.60
47.29
66.92
+
45.34
3.37
24.00
68.51
62.05
4.88
52.69
70.77
FedEA
46.40
3.61
19.33
69.30
63.05
4.95
48.69
70.88
TERM
47.11
3.66
28.21
69.51
64.15
5.90
56.21
72.20
Ditto
46.31
3.44
27.14
68.44
63.49
5.70
55.99
71.34
AdaFed
46.42
3.01
31.12
69.41
64.80
4.50
58.24
72.45
Table 2: Test accuracy on CIFAR-100. The reported results are averaged over 5 different random sceds.
Setup
Setup 2
Algorithm
de
Worst 10%
Best 10%
a
da
Worst 10%
Best 10%
FedAvg
30.05
4.03
25.20
40.31
20. 15
6.40
11.20
33.80
q-FFL
28.86
4.44
25.38
39.77
20.20
6.21
11.09
34.02
+
29.12
4.17
25.67
39.71
20.15
5.41
11.12
33.92
AFL
30.28
3.68
25.33
39.45
18.92
4.90
11.29
28.60
TERM
30.34
3.51
27.03
39.35
17.88
5.98
10.09
31.68
Ditto
29.81
3.79
26.90
39.39
17.52
5.65
10.21
31.25
AdaFed
31.42
3.03
28.91
40.41
20.02
4.45
11.81
34.11
methods inchuding AdaFed. The details reported in Appendix E and here only report the results obtained from the best hyper-parameters.
Performance metrics: Denote by on the prediction accuracy on device k. We use ā = K Σ dg as
the average test accuracy of the underlying FL algorithm, and use 0a deviation of the accuracy across the clients (similarly to (Li et al. 2019a 2021 Furthermore, we report worst 10% (5%) and best. 10% (5%) accuracies as a common metric in fair FL algorithms (Li et al. 2020a
Ek= (ax a)2 as the standard
Notations: We use bold and underlined numbers denote the best and second best performance, respectively. We use and K represent the number of local epochs and that of clients, respectively.
7.1 CIFAR-10
CIFAR-10 dataset (Krizhevsky et al. 2009 contains 40K training and 10K test colour images of size 32 32, which are labeled for 10 classes. The batch size is equal to 64 for both of the following setups.
Setup Following (Wang et al. 2021b), we sort the dataset based on their classes, and then split them into 200 shards. Fach client randomly selects two shards without replacement so that each has the same local dataset size. We use feedforward neural network with 2 hidden layers. We fix and K 100. We carry out 2000 rounds of communication, and sample 10% of the clients in each round. We run SGD local datasets with stepsize
0.1.
Setup 2: We distribute the dataset among the clients deploying Dirichlet allocation (Wang et al. 2020 with 3 = 0.5. We use ResNet-18 He et al. 2016) with Group Normalization (Wu & He 2018). We perform 100 communication rounds in each of which all clients participate. We set e = 1, K 10 and 7 = 0.01.
Results for both setups are reported in Table Additionally, we depict the average accuracy over the course of training for setup 1 in Appendix G.1
11

---

Published in Transactions on Machine Learning Research (01/2024)
Table 3: Test accuracy on FEMNIST. The reported results are averaged over different random seeds,
FEMNIST-originnll
FEMNIST-skewed
Algorithm
@
Angle ())
KL (allu)
a
Angle (?)
KL (allu)
FedAvg
80.42
11.16
10.18
0.017
79.24
22.30
12.29
0.054
q-FFL
80.91
10.62
9.71
0.016
84.65
18.56
12.01
0.038
+edMGDA+
81.00
10.41
10.04
0.016
85.41
17.36
11.63
0.032
TERM
81.08
10.32
9.15
0.015
84.29
13.88
11.27
0.025
AFL
82.45
9.85
9.01
0.012
85.21
14.92
11.44
0.027
Ditto
83.77
10.13
9.34
0.014
92.51
14.32
11.45
0.022
AdaRed
82.26
6.58
8.12
0.009
92.21
7.56
9.44
0.011
7.2 CIFAR-100
CIFAR-100 Krizhevsky et al. 2009 contains the same number of samples as those in CIFAR-10, yet it contains 100 classes instead.
The model for both setups is ResNet-18 (He et al. 2016) with Group Normalization (Wu & He 2018 where all clients participate in each round. We also set 1 and 7 0.01. The batch size is equal to 64. The results are reported in Table 2 for both of the following setups:
Setup 1: We set K = 10 and B = 0.5 for Dirichlet allocation, and use 400 communication rounds.
Setup We set 50 and 0.05 for Dirichlet allocation, and use 200 communication rounds.
Additionally, we perform the same experiments with more local epochs, specifically 10, 20 as presented in
Appendix H
7.3 FEMNIST
FEMNIST (Federated Extended MNIST) Caldas et al. (2018) is a federated image classification dataset distributed over 3,550 devices by the dataset creators. This dataset has 62 classes containing 28 x 28-pixel images of digits (0-9) and English characters (A-7, a-z) written by different people.
For implementation, use CNN model with 2 convolutional layers followed by 2 fully-connected layers. The batch size is 32, and = for both of the following setups:
FEMNIST-original: We use the setting in Li et al. [202)), ) and randomly sample K = 500 devices (from the 3550 ones) and train models using the default data stored in each device.
FEM:ISTT-kkwee:: Here K 100. We first sample 10 lower case characters ('a'-i") from Extended MNIST (EMNIST), and then randomly assign 5 classes to each of the 100 devices.
Similarly to
Li et al., 2019a), we use two new fairness metrics for this dataset: (i) the angle between the accuracy distribution and the all-ones vector denoted by Angle (*), and (ii) the KL divergence between the normalized accuracy a and uniform distribution u denoted by KL (allu). Results for both sctups are reported
in Table 3 In addition, we report the distribution of accuracies across clients in Appendix G.2
7.4 Text Data
We use The Complete Works of William Shakespeare McMahan et al. 2017) as the datasct, and train an RNN whose input is 50-character sequence to predict the next character. In this dataset, there are about 1,129 speaking roles. Naturally, each speaking role the play is treated as device. Each device stored several text data and those information will be used to train RNN on each device. The dataset is available on the LEAF website (Caldas The results reported in Table for the following two setups:
20188. We use 1, and let all the devices participate in each round.
12

---

Published in Transactions on Machine Learning Research (01/2024)
Table 4: Test accuracy on Shakespeare. The reported results are averaged over 5 different random seeds.
Sctup
Setup 2
Algorithm
Worst 10%
Best 10%
@
aa
Worst 10%
Best 10%
FedAvg
53.21
9.25
51.01
54.41
50.48
1.24
48.20
52.10
q-FFL
53.90
7.52
51.52
54.47
50.72
1.07
48.90
52.29
++
53.08
8.14
52.84
54.51
50.41
1.09
48.18
51.99
AFL
54.58
8.44
52.87
55.84
52.45
1.23
50.02
54.17
TERM
54.16
8.21
52.09
55.15
52.17
1.11
19.14
53.62
Ditto
60.74
8.32
53.57
55.92
53.12
1.20
50.94
55.23
AdaFed 55.65
6.55
53.79
55.86
52.89
0.98
51.02
54.48
Setup 1: Following McMahan et al. (017 we subsample 31 speaking roles, and assign each role a client to complete 500 communication rounds. We use model with two LSTM layers (Hochreiter & Schmidhuber 1997) and one densely-conmeeted layer. The initial v = 0.8 with decay rate of 0.95.
Setup 2: Among the 31 speaking roles, the 20 ones with more than 10000 samples selected, and assigned to 20 clients (K =0). We use one LSTM followed by a fully-connected layer. 2, and the nunber of communication rounds is 100.
7.5 Analysis of Results
Based on Tables 1 to we can attain some notable insights. Compared to other benchmark models, AdaFed leads to significantly more fair solutions. addition, the average accuracy is not scarified, yet interestingly for some cases it improved. We also note that the performance AdaFed becomes more superior when the level of non-iidness high. For instance, by referring to FEMNIST--kewed in Table we observe a considerable superiority of AdaFed. Note that the average accuracy of Ditto over FEMNIST greater than that of AdaFed. This is comprchensible, since Ditto provides personalized solution to each device, while AdaFed only returns global parameter 0.
We also observe similar trend in three other datasets reported in Appendix D We further analyse the effect of prpem-parrmeter y in AdaFed in Appendix
7.5.1 Percentage of improved clients
We measure the training loss before and after each communication round for all participating clients and report the percentage of clients whose loss function decreased or remained unchanged, as defined below
Pt Eves, H(fx(0++1) - fx(0,)
(31)
S
where S₁ is the participating clients in round t, and I(-) is the indicator function. Then, plot Pt versus communication rounds for different fair FL benchmarks, including AdaFed. The curves for CIFAR-10 and CIFAR-100 datasets are reported in Figure 2a and Figure 26 respectively. As seen, both AdaFed and FedMGDA+ consistently outperform other benchmark methods in that fewer clients' performances get worse after participation. This is a unique feature these two methods. We further note that after enough number of communication rounds, curves for both AdaFed and FedMGDA+ converge to 100% (with a bit of fluctuation).
7.5.2 Rate of decrease in loss function
In this part, we observe the loss function values for two clients over the course training to verify Theorem 4.1 This theorem asserts that the rate of docrease the loss function is higher for clients with larger initial loss function values. To this end, we select two clients one with a low initial loss function and one with a high initial loss function- and depict their respective training loss function of communication rounds.
-ne
13

---

Published in Transactions on Machine Learning Research (01/2024)
FedMGDA+
FedMGAAA+
90
FeddAgg
FFL
90
g.P.L
FedAvg
Torm AdaFed
Temm
(9)
AdaFed
Communication rounds
Communication rounds
(b)
Figure 2: The percentage improved clients as a function of communicatio rounds for (a) CIFAR-10 sctup
one in Section 7.1: and (b) CIFAR-100 setup one in Section 7.2
3.5
Clieat 1
Cleatt
Client
Cláent
4.5
2.5
Training loss
Training loes
3.5
3
2.5
1.5
1.5
0.5
0.5
2000
Communication rounds
Communicatin rounds
(a)
(b)
Figure 3: The training loss function for two clients trained in AdaFed framework Vs. the communication
rounds for (a) CIFAR-10 setup one in Section 7.1 and (b) CIFAR-100 setup one in Section 7.2
The curves are illustrated in Figure 3a and Figure 3b for CIFAR-10 and CIFAR-100 datasets, respectively. As observed both curves, the rate decrease in the loss function of the client with a larger initial loss function higher. Additionally, close to the end the training task, the values for the loss function of the clients converge almost the same value, indicating fairness among the clients.
7.5.3 Convergence of |
In this part, we aim observe the behaviour of | over the course of training. Particularly, we consider three cases following Theorems 5.3
5.5 namely (i) =1 & local SGD, (ii) e > 1 & local GD, and (iit)
== 1 & local GD.
For training, we follow the setup in Section however, we change and the local training method either GD or SGD-1 to generated the three cases mentioned above. Then, for these three cases, we normalize ||>,||, and depict it versus the communication rounds.
As observed in Figures 4a to 4c in all the three cases, || tends to zero Nonetheless, the curve for e & local GD more smooth.
14

---

Published in Transactions on Machine Learning Research (01/2024)
SGD
c I and local CD
and local GD
|aill
[oil
0.5
0
500
1000
1500
2000
500
1000
1.000
2000
500
1000
1500
2000
Communicatiin (a)
Communication rounda
Communication rounds
(b)
(c)
Figure 4: The convergence of ||De|| as a function of communication rounds for (a) e and local SGD, (b)
and local GD, and (c) e 1 and local GD. The datasct CIFAR-10.
8 Conclusion
In this paper, we proposed a method to enforce fairness in FL task dubbed AdaFed. In AdaFed, the aim is to adaptively tune common direction along which the server updates the global model. The common direction found by AdaFed enjoys two properties: (i) is descent for all the local loss functions, and (ii) the loss functions for the clients with worst performance decrease with higher rate along this direction. These properties were satisfied by using the notion of directional derivative in the multi-objective optimization task. We then derived closed-form formula for such common direction, and proved that AdaFed converges to a Pareto-stationary point. The effectiveness of AdaFed was demonstrated via thorough experimental results.
References
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness in machine learning. Nips Iutorial, 1:2017, 2017.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, et al. Towards foderated learning at scale: System design. Proceedings of machine learning and systems, 1.374-388, 2019.
Stephen P 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 Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv:1812.01099 2018.
Sen Cui, Weishen Pan, Jian Liang, Changshui Zhang, and Fei Wang. Addressing algorithmic disparity and performance inconsistency in federated learning. Advances in Neural Informalion Processing Systems, 34: 26091 221002, 2021.
Luke N Darlow, Elliot J Crowley, Antreas Antoniou, and Amos J Storkey. Cinic-10 is not imagenet or cifar-10. arXiv preprint arxiv: 035000 2018.
Jcan-Antoine Désidóri. Multiple-gradiend descent algorithm (MGDA). PhD thesis, INRIA, 2009.
Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization. Comples Rendus Mothematique, 350(5-6):313 318, 2012.
Wei Du, Depeng Xu, Xintao Wu, and Hanghang Tong. Fairness- aware agnostic federated learning. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 181-189. STAM, 2021.
Hubert Eichner, Tomer Koren, Brendan McMahan, Nathan Srebro, and Kunal Talwar. Semi-cyclic stochastic gradient descent. In International Conference on Machine Learning, pp. 1764-1773. PMLR, 2019.
Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathematical methods of operations research, (3):4779 494, 2000.
15

---

Published in Transactions on Machine Learning Research (01/2024)
Shayan Mohajer Hamidi and Oussama Damen. Fair wireless federated learning through the identification of a common descent direction. IEEE Commaniications Letlers, pp- 1-1, 2024. doi: 10.1 (0.109/T.COMM.2000 3350378.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pottern recognition, pp. 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1335-1780, 1997.
Zeou Hu, Kiarash Shaloudegi, Guojun Zhang, and Yaoliang Yu. Federated learning meets multi-objective optimization. IEEE Transactions on Network Science and Engineering. 2022.
SHI Huaizhou, R Venkatesha Prasad, Ertan Onur, and IGMM Niemegeers. Fairness in wireless networks:
Issues, measures and challenges. IEEE Communications Surveys & Tutorials, 16(1):5-24, 2013.
Tiansheng Huang, Weiwei Lin, Wentai Wu, Ligang He, Keqin Li, and Albert Y Zomaya. An fffciency-boostinn client. selection scheme for federated learning with fairness guarantee. IEEE Transactions on Parallel and Distributed Systems, 32(7):1552-1664 2020a.
Tiansheng Huang, Weiwei Lin, Li Shen, Keqin Li, and Albert Y Zoomaa. Stochastic client selection for federated learning with volatile clients. IEEE Internet of Things Journal, 9(20):20055 20070, 2022.
Wei Huang, Tianrui Li, Dexian Wang, Shengdong Du, and Junbo Zhang, Fairness and accuracy in federated learning. arXiv preprint arXiv:2012 2020b.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends0 in Machine Learning, 14(1 2):1 210, 2021.
Jiawen Kang, Zehui Xiong, Dusit Niyato, Han Yu, Sing-Chang Liang, and Dong In Kim. Incentive design for efficient federated learning in mobile networks: A contract theory approach. In 2019 IEEE VTS Asia Pacific Wireless Communications Symposium (APWCS), pp. 1-5. IEFE, 2019.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
P. Langley. Crafting papers on machine learning. In Pat Langley (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pp. 1207 1216, Stanford, CA, 2000. Morgan Kaufmann.
Tra Huong Thi Le, Nguyen H Tran, Yan Kyaw Tun, Minh NH Nguyen, Shashi Raj Pandey, Zhu Han, and Choong Seon Hong. An incentive mechanism for federated learning in wireless cellular networks: An auction approach. IEEE Transactions on Wireless Communications, 20(8):4874 4887, 2021.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-233) 2324, 1998.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations, 2019a.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. Tn
International Conference on Learning Representations, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogencous networks. Proceedings of Machine Learning and Systems, 2:429-450, 2020b.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pp. 6357-6366 PMT.R, 2021.
16

---

Published in Transactions on Machine Learning Research (01/2024)
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. orXiv preprint arxiv: 1et:199770289. 2019b.
Lingjuan Lyu, Xinyi Xu, Qian Wang, and Han Yu. Collaborative fairness in federated learning. Federated Learning: Privacy and Incentive, pp. 189- 189-204, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient. learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282. PMLR, 2017.
Quentin Mercier, Fabrice Poirion, and Jean-Antoine Désidéri. A stochastic multiple gradient descent algorithm. European Journal of Operational Research, 23) 817, 2018.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference on Machine Learning, pp. 4615-4625. PMLR, 2019.
Hiroaki Mukai. Algorithms for multicriterion optimization. IEEE transactions on automatic control, 25(2): 176,186, 1980.
Takayuki Nishio and Ryo Yonetani. Client selection for federated learning with heterogeneous resources in mobile edge. In TCC 2019-2019 IEEE international conference on communications (ICC), pp. 1-7. IEFF, 2019.
John Rawls. A theory of justice: Revised edition. Harvard university press, 2020.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Koncčný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference Learning Representations, 2020.
Zhendong Song, Hongguang Sun, Howard Yang, Xijun Wang, Yan Zhang, and Tony QS Quek. Reputation- based federated learning for secure wireless networks. JEEE Internet of Things Journal, (2))11122- 2021.
Qianqian Tong, Guannan Liang, and Jinbo Bi. Effective federated adaptive gradient methods with non-iid decentralized data. arXiv preprint (tfe:20000065577 2020.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. arXio preprint Xrxv:2000 06440, 2020.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to foderated optimization. arXiv preprint arXic:2107.060) 2021a.
Zheng Wang, Xiaoliang Fan, Jianzhong Qi, Chenglu Wen, Cheng Wang, and Rongshan Yu. Federated learning with fair averaging. arXiv preprint arXi::2104,14997, 2021b.
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference computer vision (ECCV), pp. 3-19, 2018
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint 1rXiv:108.00774 708.07747, 2017.
Tong Xiao, Tian Xia, Yi Yang. Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. In Proceedings of the IEFE conference on computer vision and pottern recognition, pp. 2691 2699, 2015.
Jingyi Xu, Zihan Chen, Tony QS Quek, and Kai Fong Ernest Chong. Fedcorr: Multi-stage federated learning for label noise correction. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 10184-10193, 2022.
17

---

Published in Transactions on Machine Learning Research (01/2024)
Miao Yang, Ximin Wang, Hongbin Zhu, Haifeng Wang, and Hua Qian. Federated learning with class imbalance reduction. In 2021 29th Europeon Signal Processing Conference (EUSIPCO), pp. 2174-2178. TEEE, 2021.
Dongdong Ye, Rong Yu, Miao Pan, and Zhu Han. Federated learning in vehicular edge computing: selective model aggregation approach. TEEE Access, 8:23920 23935, 2020.
Jingfeng Zhang, Cheng Li, Antonio Relles-Kelly, and Mohan Kankanhalli. Hierarchically fair federated learning. arXiv preprint arXiv:200,,10380 2020.
Jingwen Zhang, Yuezhou Wu, and Rong Pan. Incentive mechanism for horizontal federated learning based on reputation and reverse auction. In Proceedings of the Web Conference 2021, pp. 947 956, 2021.
18

---

Published in Transactions on Machine Learning Research (01/2024)
A Convergence of AdaFed
In the following, we provide three theorems to analyse the convergence of AdaFed under different. scenarios. Specifically, we consider three cases: (i) Theorem A.1 considers and using SGD for local updates. (īi) Theorem A.2 considers arbitrary value for and using GD for local updates, and (iii) Theorem A.4 considers = and using GD for local updates.
A.1 Case 1: & local SGD
Notations: We use subscript (:)s to indicate stochastic value. Using this notation for the values we introduced in the paper, our notations used in the proof of Theorem A.1 are summarized in Table 5
Table 5: Notations used in Theorem A. for e 1 & local SGD.
Notation
Description
g
Stochastic gradient vector of client
9,
Matrix of Stochastic gradient vectors (81,a..... [K,s]
Stochastic gradient vector of client. k after orthogonalization process.
g.
Matrix of orthogonalized Stochastic gradient vectors [i1,...... 0k.)).
Ni.s
Optimum weights obtained from Equation 14 using Stochastic gradients g.-
D.
Optimum dircction obtained using Stochastic g,; that is, D. = ER= Ai.
Theorem A.1. Assume that = {fx ke(k] are L-Lipschitz continuous and L-Lipschitz smooth, and that the step-size satisfies the following three conditions: (i) ve E (0, H (ii) limr E - oo and (iii) 1im Er nht oo; where of El 2.llll the variance of stochastic common descent. direction. Then
lim
min
D.ll +
(32)
T-000 t=.....
Proof. Since orthogonal vectors {gie [e(k] span the same K-dimensional space as that spanned by gradient.
vectors [g then
K
K Nea
[(Ce s.t. d
X
gX'
(33)
A=1
Similarly, for the stochastic gradients we have
K
K Ne g.X
TAAaaEEIK s.t. d.
Σ
Ni
Ük.
(34)
k=1
Define A, g\' 9.Y, -gx- 9. where the last equality is due to the definitions Equations
and 34
19

---

Published in Transactions on Machine Learning Research (01/2024)
We can find an upper bound for f(0++1) follows
f(0++1) = f(0, me)
(35)
K
f(0, E
(36)
kml
f(0. 7'
(37)
S f(0,) n: g. X₂ Lnt llg x112
(38)
S f(0.) " g + Lniill" 21I2 + g A. + Ln
(39)
S f(0.) ()e(1 Im:)ll laallll""/// X12 + 1m | Ln A.
(40)
where 33 uses stochastic gradients in the updating rule AdaFed, 37
obtained from the definition
38 holds following the quadratic bound for smooth functions (fkketk) and lastly (40) holds
considering the Lipschits continuity of ʃ [e(])
Assuming f) (0, 1 and taking expectation from both sides, obtain:
min E 11 f(0.) - Eif(Or- + E m(lo, + Lmio?)
(41)
Using the assumptions (i) limm Σ/= + 00, and (ii) limr Ei nh < 00, the theorem will be concluded. Note that vanishing D, implics reaching to a Paroto-stationary point of original MoM problem. Yet, the convergence rate different different scenarios as we see the following theorems.
A.1.1 Discussing the assumptions
The assumptions I-Lipschitz continuous and L- L-piscctitz smooth over the local loss functions are two standard assumptions in FL papers providing some sorts of convergence guarantee (Li et al. 2019b).
The assumptions
the local loss functions:
The assumptions over the step-size: The three assumptions we enforced over the step-size could be easily satisfied as explained in the sequel. For instance, one can pick π = = for some constant Ky such that TI: E (0, I is satisfied. Then even if o, has a extremely loose upper-bound, let's say o, < to for small IR+ and constant number N2, then all the three assumptions over the step-size in the theorem will be satisfied. Note that the convergence rate of AdaFed depends how fast o, diminishes which depends how heterogeneous the users are.
A.2 Case 2: >> & local GD
The notations used in this subsection are elaborated in Table G
Theorem A.2. Assume that f [fw are Hippshittz continuous and L-Lipschitz smooth. Denote by Ne and n the global and local learning rate, respectively. Also, define & || A where X is the optimum weights obtained from pseudo-gradients after local epochs. Then,
lim T- t=
min D +
(42)
if the following conditions are satisfied: (1) n (0, J.l. (ii) limy- EJ no and (iii) limy ne + 0,
(iv) lime-so 7) 0, and (v) lim G + 0.
20

---

Published in Transactions on Machine Learning Research (01/2024)
Table 6: Notations used in the Theorem A.2 for and local GD.
Notation
Description
(k.e))
Updated weight for client & after local epochs at the i-th round of FL.
Ok,e
02 0 (R.a))t that is, the update vector of client k after local epochs.
ge
Matrix of update vectors [ 0K.e]-
Update vector of client k after orthogonalization process.
0.
Matrix of orthogonalized update vectors lā..
Ak.e
Optimum weights obtained from Equation 14 using Be-
d.
Optimum direction obtained using 0ei that is, D. - &k.ee
Proof. As discussed in the proof of Theorem
A.1
we can write
K
K
3 3(MakkeKK]
s.t. d
=
Σ
1aBxx = gx,
(43)
k=1
k=
K
K Nr g.
3(% s.t. de =
Σ
(44)
k=1
To prove Theorem A.2 we first introduce a lemma whose proof is provided in Appendix B
Lemma A.3. Using the notations used in Theorem A.2 and assumming that = {fe are L-Lipschitz smooth, we have [lkk. - gall < nel.
Using Lemma A.3 we have
||0 - d =11
-B.
S [8 @A + 8A 8.A.1
(45)
< ||@ll||A X + 1gX g.A.
(46)
< |@|l||A X + nel
(47)
< GIVK +nel,
(48)
where Equation 45 follows triangular incquality, Equation 46 is obtained from Equations
43 and
44
and Equation 47 uses Lemma
A.3
As seen, if lim 77 + 0, and lim 300 Ge + 0, then 1 del + 0. Now, by writing the quadratic upper bound we obtain:
f(0 S f(0.) n 8 X + Lin ! X2
(49)
2
< f(.)) n. g" X' Lnglllg TT 11 m/ T (0-de) + Lm || Dell
(50)
< f(0)) - (1 Ln)) X11 + In P Dell + Lnd d. 12.
(51)
Noting that ne E (0, 1. and utilizing telescoping yields
| < f(0v) ( + ΣT_ 1/ (1100 Dell + Lmp Dell²)
min I
(52)
EEr nt
Using D Dell + 0, the Theorem A.2 is concluded.
21

---

Published in Transactions on Machine Learning Research (01/2024)
A.3 Case 3: & local GD
Denote by & the Pareto-stationary solution set of minimization problem arg ming f()). Then, define 0- arg mingoo ||0 - 01
Theorem A.4. Assume that f = hejk are I-Lipschitz continuous and o-convex, and that the step-size Th satisfies the following two conditions: (i) lime-+c Σj=o n - oo and (ii) lim Σj= nz < oc. Then almost surely 0, + 00;; that is,
P lim (0, 07) =0)= =1, t-000
(53)
where P(E) denotes the probability of event E.
Proof. The proof is inspired from Mercier et al. 2018
Without loss of generality, assume that all users
participate in all rounds.
Based on the definition of 0r we can say
r+ 0 10++1
0, - = 10: 1700; 07
(54)
= =I0, 0,1
2n
07) de + 111::112.
(55)
To bound the third term in Equation 55 we note that from Equation 23
we have:
(56)
K
B
To bound the second term, first note that since orthogonal vectors {øx hEEKk] span the same K-dimensional space as that spanned by gradient vectors {g)) then
K
K
3(%))E[[K] s.t. d Ao
=
(57)
1=1
Using Equation and the a-convexity of (fk [k(Kk]]K] we obtain
K
(0: -0- 07) D. = (0: 0;)
Aag
(58)
(0, 0,)
Xegx
(59)
10,
0,
X/ (f. fx(()))
(60)
2
k=1
X₂ .M
00
0
|10 -0,12 +0
(61)
2
2
X₂ M +
10, 0,
12-
(62)
2
Now, we return back to Equation
55
and find the conditional expectation w.r.t. O, as follows
1 K
E 0
0 11 0.1 < (1 E.Y + 00.1)00 0, +
(63)
Assume that E + 2 c, taking another expectation obtain:
01 0211 < (1 - mc) 0,11 + 7 1
(64)
K
22

---

Published in Transactions on Machine Learning Research (01/2024)
which is recursive expression. By solving Equation 64 obtain
m (1 15c) 12
Oi| 0.+1
- II ==0
ny E 0. 0112 +
(65)
K 1 n7,))
First term
Second
It is observed that if the limit of both First term and Second term in Equation 65 O1 11+1118 For the First term, from the crchmetii-goomettie mean incquality we have
go to zero, then
Ej=o(1 N5c) t
(1 - E
Ej=o
lim II n/c) S lim ==0
lim t-000
(66)
10000
lim Ei=o 96
(67)
From Equation 67 it is seen that if lim,-soe Ej=o fij + oo, then the First term also converges to zero as - 00.
On the other hand, consider the Second term in Equation 65 Second term converges to as t -
Obviously, if lim Σj= ni oc, then the
Hence, if (i) lim Ej-o 1/ + co and (ii) lim, 10o 7
< co, then E[][0,+1 - -0:+1 - 0. Consequently,
based on standard supermartingale (Mercier et al. 2018 we have
P lim (0: 0,) = 0) =
(68)
10000
B Proof of Lemma A.3
Proof.
Ok,e = 0. =(kke)) (0, - ((.11))) + (0 (k.1)) - -((x22))) +... (0 (k.e-1))) 0 ((k,e))
(69)
(0:) + - 10k.e-1
(70)
Hence,
l0ke
gell ||m Σ
gk.ill S Σ
|gae S nel.
(71)
j=1
j=1
C More about fairness in FL
C.1 Sources of unfairness in federated learning
Unfairness in FL can arise from various sources and is concern that needs to be addressed in FL systems. Here some of the key reasons for unfairness in FL:
1. Non- non-Representative Data Distribution: Unfairness can occur when the distribution of data across participating devices or clients is non-representative of the overall population. Some devices may have more or less relevant. data, leading to biased model updates.
2. Data Bias:
If the data collected or used by different clients is inherently biased due to the data collection process, it can lead unfairness. For example, if certain demographic groups are underrepresented in the training data of some clients, the federated model may not perform well for those groups.
23

---

Published in Transactions on Machine Learning Research (01/2024)
3. Heterogencous Data Sources: Federated learning often involves data from diverse set of sources, including different device types, locations, or user demographics. Variability in data sources can introduce unfairness as the models may not generalize equally well across all sources.
4. Varying Data Quality: Data quality can vary among clients, leading to unfairness. Some clients may have noisy or less reliable data, while others may have high-quality data, affecting the model's performance.
5. Data Sampling: The way data sampled and used for local updates can introduce unfairness. If some clients have imbalanced non-representative data sampling strategies, it can lead to biased model updates.
6. Aggregation Bias: The learned model may exhibit a bias towards devices with larger amounts of data or, if devices are weighted equally, it may favor more commonly occurring devices.
C.2 Fairness in conventional ML Vs. FL
The concept of fairness is often used to address social biases performance disparities among different individuals or groups in the machine learming (ML) literature (Barocas et al. 2017). However, in the context of FI., the notion of fairness differs slightly from traditional MT. In FI., fairness primarily pertains to the consistency performance across various clients. In fact, the difference the notion of fairness between traditional ML and FL arises from the distinct contexts and challenges of these two scttings:
1. Centralized vs. decentralized data distribution:
In Iraditional ML, data is lypically centralized, and fairness often defined in terms of mitigating biases or disparities within a single, homogeneous dataset. Fairness evaluated based on how the model treats different individuals or groups within that dataset.
In FL, data is distributed across multiple decentralized clients or devices. Each client may have its unique data distribution, and fairness considerations extend to addressing disparitics across these clients, ensuring that the federated model provides uniform and equitable performance for all clients.
2. Client autonomy and data heterogeneity:
In FL, clients are autonomous and may have different data sources, labeling processes, and data collection practices. Fairness in this context involves adapting to the heterogeneity and diversity among clients while still achieving equitable outcomes.
Traditional ML operates under a centralized, unified data schema and is not inherently designed to handle data heterogeneity across sources.
We should note that in certain cases where devices can be naturally clustered into groups with specific attributes, the definition of fairness in FL can be seen as a relaxed version of that in ML, i.e., we optimize for similar but not necossarily identical performance across devices (Li et al. 2019a).
Nevertheless, despite the differences mentioned above, to maintain consistency with the terminology used the FL literature and the papers we have cited in the main body of this work, we will continue use the term "fairness" to denote the uniformity of performance across different devicos.
D Additional three datasets
In this section, we evaluate the performance of AdaFed against some benchmarks over some other datasets, namely Fashion MNIST, CINIC-10, and TinylmageNet whose respective results are reported in Appendices D.1
to D.3
24

---

Published in Transactions on Machine Learning Research (01/2024)
D.1 Fashion MNIST
Fashion MNIST (Xiao et al. 2017 is an extension of MNIST dataset (LeCun et al. 1998 with images resized to 32 x 32 pixels.
We use fully-connected neural network with 2 hidden layers, and use the same setting as that used in et al. (2019a) for our experiments. We set e= and use full batchsize, and use 0.1. Then, conduct 300 rounds of communications. For the benchmarks, use the samne as those used for CIFAR-10 experiments.
The results are reported in Table 7
By observing the three different classes reported in Table 7 wC observe that the fairness level attained AdaFed not limited to a dominate class.
Table Test accuracy on Fashion MNIST. The reported results are averaged over different random seeds.
ALCORITHM
ā
SMIRT
PULLOVER
T-SHITT
FEDAVG
80.42
3.39
64.26
87.00
89.90
Q-FFL
78.53
2.27
71.29
81.46
82.86
FEDMGDA+
79.29
2.53
72.46
79.74
85.66
FEDFA
80.22
3.41
63.71
86.87
89.94
ADAFED
79.14
2.12
72.49
79.81
86.99
D.2 CINIC-10
CINIC-10 (Darlow et al. 2018 has 4.5 times as many images as those in CIFAR-10 dataset (270,000 sample images in total). In fact, it is obtained from ImageNet and CIFAR-10 datasets. As result, this dataset fits FL scenarios since the constituent elements of CINIC-10 are not drawn from the same distribution. Furthermore, we add more non-iidness to the datasct by distributing the data among the clients using Dirichlet allocation with B ===01, 0.5.
For the model, we use ResNet-15 18 with group normalization, and set = 0.01. There are 200 communication rounds in which all the clients participate with 1. Also, K 50. Results are reported in Table
Table 8: Test accuracy on CINIC-10. The reported results are averaged over 5 different random seeds.
ALGORITHM
ā
aa
WORST 10%
BEST 10%
Q-FFL
86.57
14.91
57.70
100.00
DrrTO
86.31
15.14
56.91
100.00
AFL
86.49
15.12
57.62
100.00
TERM
86.40
15.10
57.30
100.00
ADAFED
86.34
14.85
57.88
99.99
D.3 TinylmageNet
Tmny-Im (Le & Yang 2015) a subset of ImageNet. with 100k samples of 200 classes. We distribute the dataset among 20 clients using Dirichlet allocation with 0.05
We use ResNet-18 with group normalization, and r 0.02. There are 400 communication rounds in which all the clients participate with The results reported in Table
25

---

Published in Transactions on Machine Learning Research (01/2024)
Table 9: Test accuracy on TinylmageNet. The reported results are averaged over different random seeds.
ALGORITHM
a
0a
WORST 10%
BEST 10%
Q-FFL
18.90
3.20
13.12
23.72
AFL
16.55
2.38
12.40
20.25
TERM
16.41
2.77
11.52
21.02
F
14.00
2.71
9.88
19.21
ADAFED
18.05
2.35
13.24
23.08
E
Experiments details, tuning hyper-parameters
For the benchmark methods and also AdaFed, used grid-search to find the best hyper-parameters for the underlying algorithms. The parameters we tested for each method are as follows:
AdaFed: ? E {0, 0.00, 0.1, 1,
q-FFL: E (0, 0.001, 0.01, 0.1, 5, 10).
TERM: E 1,2,0.,,,,2,55
AFL: n 0.1,,,1,
Ditto: À E 0.00,,0.0,,01,00.. 5.
FedMGDA+: E 0,,
FedFA: (a. 3) = (0.5, (c)) = ((0.5.
To have a better understanding about how the parameter y in AdaFed affects the performance of the FL task, report the results for different values of y in AdaFed in this section.
E.1 CIFAR-10
The best hyper-parameters for the benchmark methods are: g 10 for q-FFL, 0.5 for FedMGDA+, and (a, B) (0.5,0.5)), (Ys, Ne) {00.5, 0.9) for FedFA. The detailed results for different y in AdaFed are reported in Table 10 We used = 5 as the best point for Table 1
Table 10: Tuning 7 in AdaFed over CIFAR-10. Reported results are averaged over different random seeds.
SETUP
SETUP 2
ALGORITHM
aa
WORST 5%
BEST 5%
Ø
WORST 10%
BEST 10%
ADAFRD
45.44
3.43
20.18
68.04
59.88
4.89
48.12
70.62
ADAFED,=0.01
45.77
3.36
23.55
68.07
60.39
4.81
49.43
70.63
ADAFED,=0.11
46.01
3.18
27.12
68.12
60.98
4.70
50.91
70.70
ADAFED,=1
46.55
3.18
27.75
68.20
63.24
4.54
54.55
71.12
ADAFED,=3
46.42
3.01
31.12
67.73
64.80
4.50
58.24
72.45
ADAFED,=10
46.00
2.88
35.21
67.35
63.25
4.66
51.74
71.25
E.2 CIFAR-100
The best hyper-parameters for the benchmark methods are: q 0.1 for FFFL,, 0.5 in TERM, and
T) 0.5 in AFL. In addition, the detailed results for different y in AdaFed are reported in Table I1 We used 7 as the best point for Table 2
26

---

Published in Transactions on Machine Learning Research (01/2024)
Table 11: Tuning y in AdaFed over CIFAR-100. Reported results are averaged over different random seeds.
Setup
Setup 2
Algorithm
Worst 10%
Best 10%
Worst 10%
Best 10%
=
29.41
4.45
24.41
39.21
17.05
6.71
10.04
27.41
AdaFedy=o.or
30.12
4.05
25.23
39.41
17.77
6.09
10.43
28.42
odaFedy=o.1
31.05
3.52
26.13
40.12
19.51
4.95
10.89
32.10
A
31.42
3.03
28.91
40.41
20.02
4.45
11.81
34.11
AdaFedy=5
31.23
2.95
28.12
40.20
19.79
4.31
11.86
33.67
AdaFedy=10
31.34
2.91
28.52
40.15
19.61
4.56
11.42
32.91
E.3 Fashion MNIST
The best hyper-parameters for the benchmark methods are: = 0.5 for FedMGDA+, q = 0.1 for q-FFL, (a, 3) = {00.5, 0.5)), (1s, Te) (0.5, 0.9) for FedFA, The detailed results for different y in AdaFed are reported in Table 12 We used 7 as the best point for Table 7
Table 12: Tuming y in AdaFed over Fashion MNIST. Reported results are averaged over 5 different seeds.
ALGORITHM
a
SHIRT
T-SHIRT PULLOVER
ADAFED,=
78.84
2.55
71.77
78.34
84.12
ADAFED,=0.01
78.88
2.41
71.73
78.66
85.62
ADAFED..=O..
79.24
2.30
72.46
79.14
85.66
ADAFED,=11
79.14
2.12
72.33
79.81
83.99
ADAFED,-5
79.04
2.09
71.55
78.37
85.41
ADAFED,=11
78.91
1.96
71.43
78.04
85.82
E.4 FEMNIST
The best hyper- parameersss for the benchmark methods are: À = 0.1 for Ditto, 0.1 for q-FFL, t = 0.5 for TERM, ?tt = 0.5 for AFL. Also, the detailed results for different y AdaFed are reported in Table 3 We
used 7 = 1 as the best point for Table 13
Table 13: Tuning y AdaFed over FEMNIST. Reported results are averaged over different seeds.
FEMNIST-origine
FEMNIST-skeweed
Algorithm
To
Angle (9)
KL (allu)
a
Angle (9)
KL (allu)
=d
81.32
13.59
10.85
0.019
84.39
13.54
11.32
0.024
AdaFed
82.67
12.03
10.68
0.018
87.66
12.02
10.91
0.019
81.60
8.72
9.23
0.011
88.62
10.59
10.75
0.017
A
82.26
6.58
8.12
0.009
92.21
7.56
9.44
0.011
AdaFed,=5
80.10
5.16
7.29
0.007
90.12
5.82
7.31
0.009
AdaFed,=
80.05
3.03
6.44
0.007
84.38
4.49
6.99
0.008
27

---

Published in Transactions on Machine Learning Research (01/2024)
E.5 Shakespeare
The best hyper-parameters for the benchmark methods are: q= 0.1 for q-FFI, À = 0.1 for Ditto, and 1/1 0.5 for AFL. Furthermore, the results obtained for different y values in AdaFed reported in Table 14 We used y 0.1 as the best point for Table
Table 14: Tuning y in AdaFed over Shakespeare. Reported results are averaged over different seeds.
Setup
Setup
Algorithm
a
aa
Worst 10%
Best 10%
ā
aa
Worst 10%
Best 10%
-o
48.40
13.5
44.12
51.29
48.80
1.58
46.23
51.12
o0.Fed
53.55
8.01
50.96
54.46
51.67
1.10
48.71
53.16
od.
55.65
6.55
53.79
55.86
52.89
0.98
51.02
54.48
AdaFedy=1
53.91
5.10
51.94
54.06
51.44
1.06
50.88
54.52
Ad
54.40
4.15
52.17
54.77
51.20
1.05
50.72
54.61
AdaFedy=10
54.56
4.22
52.20
54.73
51.19
1.07
50.70
54.01
E.6 CINIC-10
The best hyper-parameters for the benchmark methods are: t= 0.5 for TERM, 1 0.1 for q-FFT, À = 0.1 for Ditto, and = 0.5 for AFL. Furthermore, the results obtained for different y values in AdaFed are reported in Table 15 We used = as the best point for Table S
Table 15: Tuning in AdaFed over CINIC-10. Reported results averaged over 5 different seeds.
ALCORITHM
da
WORST 10%
BEST 10%
ADAFED,-0
85.17
15.71
54.67
99.92
ADAFED,=0001
85.87
15.54
56.12
99.95
ADAFED,=0.1
86.13
15.32
57.01
99.98
ADAFED,=1
86.34
14.85
57.88
99.99
ADAFED,-55
86.03
15.01
57.72
99.98
ADAFED,=10
85.49
15.08
57.23
99.99
E.7 TinylmageNet
The best hyper-parameters for the benchmark methods are: 6 0.05 for FedMGDA+ t. 0.5 for TERM, = 0.1 for F-FFL, and Th = 0.5 for AFL. Furthermore, the results obtained for different 7 values in AdaFed
are reported Table 16 We used y = 1 as the best point for Table
E.8 The effect of parameter
In this section, we reported the results for AdaFed over differont datascts when 7 takes different values. Basod on the tables reported in this section, we observe almost. a similar trend over all the dalaset. As a rule of thumb, a higher (lower) y yields a higher (lower) fairness and slightly lower (higher) accuracy. Nevertheless, the best performance of AdaFed (in terms of establishing an appropriate trade-off between average accuracy and fairness) achieved for a moderate value 7. This is also consistent with the other fairness methods in the literature, where in most cases, the best hyper-parameter is moderate one.
28

---

Published in Transactions on Machine Learning Research (01/2024)
Table 16: Tuning y in AdaFed over TinylmageNet. Reported results are averaged over 5 different seeds.
ALGGRRITM
ā
aa
WORST 10%
BEST 10%
A
13.25
3.14
9.82
19.24
ADAFEDD=0000
14.38
2.72
10.12
19.97
ADAFEDD;00.1
16.20
2.65
11.65
21.12
ADAFED;=1
18.05
2.35
13.24
23.08
ADAFED,=5
17.76
2.31
12.44
22.84
ADAFED;=10
17.05
2.38
12.58
23.67
F Computation cost of Adafed
F.1 Comparing to FedMGDA+
First, note that AdaFed concept is built upon that of FedMGDA+ (Hu et al. 2022) (and FairWire in Hamidi & Damen (2024)), in that both use Pareto-optimal notion to enforce fairness in FL task. Note that the optimal solutions in MoM usually forms a set (in general of infinite cardinality). As discussed, what distinguishes FedMGDA+ and AdaFed that to which point of this set these algorithms converge. Particularly, AdaFed converges more uniform solutions Figure Ta This is because FedMGDA+ algorithm only satisfies Condition (I), yet in AdaFed, both Conditions (1) and (II) are held.
Interestingly, the cost of performing AdaFed is less than that of performing FedMGDA+ To elucidate, FedMGDA+ also finds the minimum-norm vector in the convex hull of the gradients' space in order to find a common descent direction. To this end, they used generic quadratic programming which entails iteratively finding the minimum-norm vector in the convex hull the local gradients. One the pros of AdaFed is that it finds the common descent direction without performing any ilerations over the gradient vectors. Thus, AdaFed not only yields a higher level of fairness compared FedMGDA+ but also solves its complexity issue.
F.2 Running time for AdaFed
Assume that the number of clients K, and the dimension of the gradient vectors is d. Then, the orthogonalization for k-th client, [K], needs O(2dk) operations (by operations we meant multiplications and additions). Hence, the total number of operations needed for orthogonalization process in equal to O(2dk2) (Also note that Gram-Schmice is the most efficient algorithm for orthogonalization)
In our experimental setup, we realized that the overhead of AdaFed is negligible, resulting almost the same overall running time for FedAvg and AdaFed. To justify this fact, please refer to FedMGDA+ paper where they discussed the overhead their proposed method; as they claimed, the overhead is negligible yielding the same running time as FedAVG. On the other hand, as explained Appendix F.I the complexity of AdaFed is lower than that of FedMGDA+.
G Curves and histograms
G.1 Training curves for CIFAR-10 and CIFAR-100
In this subsection, we depict the average test accuracy over the course of training for CIFAR-10 dataset using setup one (see Scction 7.1). In particular, we depict the average test accuracy across all the clients Vs. the number of communication rounds. Additionally, to demonstrate the convergence of the FL algorithms after 2000 communication rounds, we have depicted the training curve for 4000 rounds.
29

---

Published in Transactions on Machine Learning Research (01/2024)
The curve for each method is obtained by using the best hyper-parameter of the respective method (we discussed the details of hyper-parameter tuning in Appendix Furthermore, the curves are averaged over five different seeds.
The results are shown in Figure and Figure for CIFAR-10 and CIFAR-100, respectively. Particularly in Figure S AdaFed converges faster than the benchmark methods. Specifically, AdaFed reaches average test accuracy of 40% after around 400 communication rounds; however, the benchmark methods reach this accuracy after around 900 rounds. Indeed, this is another advantage of AdaFed in addition to imposing fairness across the clients.
50
Average of test accuracy %
45
40
35
FodAvg
q-FodAVG FodMGDA
25
FedEA
20
AdaFed
15
10
500
1000
1500
2000
2500
3000
3500
4000
communication rounds
Figure Average test accuracy across clients for different FL methods on CIFAR-10. The sctup for the experiments is elaborated in Section 7.1 setup 1.
35
Average of test accuracy %
30
25
20
15
FedAvg
q-FedAVG
10
AFL
TERM
AdaFed
0
50
100
150
200
250
300
350
400
communication rounds
Figure Average test accuracy across clients for different FL methods CIFAR-100. The setup for the experiments is elaborated in Section 7.2 setup 1.
G.2 Histogram of accuracies
To better observe the spread of clients accuracy, we depict the histogram of accuracy across 500 clients for the Original FEMNIST dataset (the setup for the experiment discussed in Appendix D.I. To this end, we depict the histogram of the clients' accuracies for three different methods: FedAvg, (ii) Q-FFI, and (iii)
30

---

Published in Transactions on Machine Learning Research (01/2024)
AdaFed(y = 5); all using their well-tuned syper-parametee The result is depicted in Appendix G.2 As seen, the distribution of the accuracy is more concentrated (fair) for AdaFed.
FedAvg
Q-FFL
AdaFed 5
of clients
50
40
30
20
40
50
60
70
90
100
Test Accuracy
Figure 7: The distribution of clients accuracy for Original FEMNIST dataset using three different methods,
namely: (i) FedAvg, (ii) Q-FFL, and (iii) AdaFed.
H CIFAR-100 results with more local epochs
In this section, want to lest the performance of AdaFed using larger number of local epochs e. To this end, use the same setups as those used in the main body of the paper to produce the results for CIFAR-100, but change the number of local epochs to 10 and 20. [ The results for 10 and 20 are reported in Table 17 and Table 18 respectively. We highlight two key observations from the tables:
AdaFed can still provide higher level of fairness compared to the benehmark methods;
While increasing the number of local epochs from 1 10 results in higher average accuracy, this trend is not observed when further increasing 20.
Table 17: Test accuracy CIFAR-100 with random seeds.
10. The reported results are averaged over 5 different.
Setup
Setup 2
Algorithm
aa
Worst 10%
Best 10%
aa
Worst 10%
Best 10%
FedAvg
31.14
4.09
25.30
40.54
20.54
6.42
11.12
33.47
q-FFL
29.45
4.66
25.35
39.91
20.77
6.20
11.05
33.52
AFL
31.17
3.69
25.12
39.52
19.32
4.85
11.23
28.93
TERM
30.56
3.63
27.19
39.46
17.91
5.87
10.11
32.00
AdaFed
31.19
3.14
28.81
40.42
20.41
4.71
11.39
34.08
Integration with a Label Noise Correction method
1.1 What is label noise in FL?
Label noise in FL refers to inaccuracies errors in the ground truth labels associated with the data used for training. occurs when the labels assigned to data points are incorrect or noisy due to various reasons.
We selected {10,20) 20} because these values have been commonly mtilized in the literature for the CIFAR-100 dataset.
31

---

Published in Transactions on Machine Learning Research (01/2024)
Table 18:
Test accuracy on CIFAR-100 with 20. The reported results are averaged over 5 different
random seeds.
Setup
Setup 2
Algorithm
aa
Worst 10%
Best 10%
aa
Worst 10%
Best 10%
FedAvg
29.11
4.31
24.61
39.45
18.05
6.12
9.15
30.12
Q-FFI.
29.15
4.23
12
39.67
19.02
6.15
8.41
31.66
AFL
30.38
3.78
25.00
39.12
17.74
4.96
10.01
27.08
TERM
31.15
3.62
27.02
40.41
15.81
5.68
8.17
29.26
AdaFed
30.41
3.19
27.35
40.18
18.37
4.21
10.55
31.78
Label noise can introduced at different stages of data collection, annotation, or transmission, and it can have a significant impact on the performance and reliability of FL models.
Label noise in FL. is particularly challenging to address because FT. relies decentralized data sources, and participants may have limited control over label quality in remote environments. Dealing with label noise often involves developing robust models and FL algorithms that can adapt to the presence of inaccuracies in the labels.
1.2 Are the fair FL algorithms robust against label noise?
The primary intention of the fair FI. algorithms including AdaFed is to ensure fairness among the clients while maintaining the average accuracy across them. Yet, these algorithms are not robust against label noise (mislabeled instances).
Nonetheless, AdaFed could be integrated with label-noise resistant methods the literature yielding an FL method which (i) satisfics fairness among the clients, and (ii) robust against the label noise. In particular, among the label-noise resistant FL algorithms in the literature, we select FedCorr (Xu et al. 2022 to be integrated with AdaFed.
FedCorr introduces a dimensionality-basoe filter to identify noisy clients, which is accomplished by mcasuring the local rntrissic dimensionality (LID) of local model prediction subspaces. They demonstrate that is possible to distinguish clean datasets from noisy ones by observing the behavior of LID scores during the training process (we omit further discussions about FedCorr, and refer interested readers to their paper for more details).
Similarly to FedCorr, exactly the same setting they used for this datase 10 In particular, use local SGD with momentum of 0.5, with batch size of 16, and five local epochs, and set the hyper-parameter T1 = 2 in their algorithm. In addition, when integrated with AdaFed, we set 7 = 5 for AdaFed.
real-world noisy dataset, namely Clothing Xiao et al. 2015). and
The results are summarized Table 2.2% lower than that obtained from FedCorr which shows that AdaFed not robust against label-noise. Moreover, expected AdaFed results in fair client accuracy. On the other hand, when AdaFed is combined with FedCorr, the average accuracy improves while maintaining satisfactory fairness among the clients.
observed, the average accuracy obtained by AdaFed is around
9ClothingIM contains 1M clothing images in classes. It is dataset with noisy labels, since the data is collected from several online shopping websites and include many mislabelled samples. 10 /tttps://githuub. com/Xu- /Fedore
32

---

Published in Transactions on Machine Learning Research (01/2024)
Table 19: Test accuracy on ClothingIM dataset. The reported results averaged over 5 different random seeds.
ALGORITHM
de
WORST 10%
BEST 10%
FEDAvG
70.49
13.25
43.09
91.05
FEDCORR
72.55
13.27
43.12
91.15
ADAFED
70.35
5.17
49.91
90.77
FEDCORR + ADAFEd
72.29
8.12
46.52
91.02
33


Reviews:
[{"review_id": "oOmWln02FX", "reviewer": "Reviewer_LveH", "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": "Strengths:\n1. The paper is solid and well motivated, and generally well written.\n2. The method is very well presented and analyzed, with theoretical results supporting the main claims.\n3. Experiments are extensive over many FL datasets and settings, results are consistently better than baselines.\n\nWeaknesses:\n1. Although the authors have acknowledged the lack of standard definition of fairness, I am wondering if there is another more suitable term - fairness is commonly used to refer to social biases or performance disparities across different individuals or groups in the ML literature. Furthermore, the authors have not really analyzed why unfairness can occur - is it mostly due to imbalanced client dataset sizes? out of distribution clients, clients with data from a different modality? Analyzing these reasons seems important to built solutions.\n2. Quite a few missing baselines, in particular FedMGDA which is directly built-upon for motivation is a missing baseline in Tables 2,3,4. TERM and Ditto are also missing in some of the Tables.\n3. Section 7.5 Analysis of Results can be significantly expanded. It would be good if the main theorems regarding convergence and scaling are analyzed empirically here as well. Another experiment would to more closely analyze which populations/devices the model found to be unfair and ended up scaling to improve fairness. Any insights here for how to better design FL distributions/study fairness/improve modeling?\n4. Not a critical change, but the paper would be much more impactful if there were some real-world FL experiments with actual data distributions that exhibit unfairness when trained normally, such as certain hospitals, demographic groups, etc.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 studies the problem of learning an unfair model in federated learning, where the trained model may unfairly advantage or disadvantage some of the devices. The authors propose AdaFed which adaptively finds an updating direction for the server along\nwhich (i) all the clients’ loss functions are decreasing; and (ii) the loss functions for the clients with larger values decrease with a higher rate. This results in a method which better balances the training across multiple devices which is effective on a suite of federated datasets in improving fairness.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "see weakness points 1-4", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "F8HEPlyp7w", "reviewer": "Reviewer_6yn3", "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": "Strengths:\n- Well-motivated, good exposition, good writing\n- Wide selection of datasets, tasks, models and baselines for experimental evaluation\n- relevant topic\n\nWeaknesses: \n- While the experimental setup is extensive, I see potential red flags that I would ask the authors to address (detailed below)\n- Baselines: A common approach to improved server-side averaging is to use FedAdam (or other higher-moment optimizers) at the server (https://arxiv.org/abs/2003.00295). I would like to understand why the authors did not compare against these algorithms", "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": "The authors introduce a new server-side averaging method for federated learning. For each clients' update vector that is sent to the server, a scalar multiplicative value is found such that the average of the scaled update vectors results in a fairer model at convergence. \nThe authors motivate their method thoroughly, providing analysis and intuition. Their approach is accompanied by convergence proofs (that I have not read in detail), as well as experimental results across a wide variety of datasets & benchmarks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The experimental evaluation is very extensive, but I am surprised by the decision to optimize only 200 or 400 rounds for Cifar100. In my own experience with this dataset and model in the FL context, convergence is achieved only after a higher number of rounds - I have not replicated the exact setting of course, but I would be curious to see a learning curve. Along the same lines Figure 2 for Cifar10 seems to suggest that in terms of average test accuracy, the differently trained algorithms have not converged yet. I would like to understand how much of a compromise AdaFed makes in terms of accuracy compared to these baselines when trained to convergence. \n\nAs mentioned above, I would like to understand if adaptive server-side optimizers should not serve as a relevant baseline to these settings and if yes, please include one in your baselines. \n\nThat being said, I really enjoyed reading this paper and believe it to be strong.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pjdw4EkdMa", "reviewer": "Reviewer_KkcE", "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": "# Strengths\n\n1. This work successfully correlates the loss variance with the aggregation algorithm using principles derived from multi-objective optimization (MOO). This is a unique and well-crafted concept.\n2. Further analysis has been undertaken to rationalize the choice of global learning rate and to prove the convergence, adding to the paper's reliability.\n3. This work clearly clarifies how the proposed approach is derived, making the work accessible to the audience not working directly on MOO. This has the advantage of attracting more researchers in the field of FL to study MOO.\n4. Experimental results show that the variance in accuracy is efficiently reduced compared with the baselines, proving the effectiveness of AdaFed. \n\n# Weaknesses\n\n1. The derivation of AdaFed is essentially based on distributed SGD instead of FL. The main difference between these two approaches is that one performs aggregation at every iteration, while the other performs aggregation after many epochs of local training. While I believe some insights from distributed SGD can be transferred to FL, they are not always generalizable. This work lacks discussion regarding this.\n2. When applied to a real FL application, accumulated gradients are regarded as pseudo-gradients. However, only the loss of the last iteration is used to re-scale the gradient (Line 9, Algorithm 1). Can the author explain the reason of choosing this approach instead of accumulated loss?\n3. The experimental results and settings are not very convincing. In particular, the number of epochs is mostly set to 1 which is rare for FL applications due to the concern about communication overhead. Additionally, data splitting does not seem to impose a very difficult learning task and the networks are not small for the respective dataset. However, the reported accuracies are too small.", "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 work proposes a way to tackle the fairness problem in federated learning (FL). Defining the problem as the variance in accuracies  across clients, this work employs multi-objective minimization to develop a novel approach of global model aggregation, such that this problem can be addressed. Additionally, some theoretical analysis has been conduct to reason the choice of global learning rate and to prove the convergence. In the experimental section, results of extensive datasets show the promise of the proposed AdaFed approach. In particular, AdaFed performs outstandingly in reducing the variance of accuracies across the clients, i.e. the problem attempt to address in this paper.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The following changes can strengthen the work in my view:\n\n1. More experiments with a larger number of epochs. Even negative results can add credibility to this work.\n2. Discussion regarding the weaknesses.\n3. Modern datasets usually contain mis-labeled instances. It seems the proposed approach is susceptible to such problems. Discussion and experiments to show the limitation are preferred.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers unanimously commended the exposition of the paper citing that it is clear and coherent. The reviewers also found the claims to be correct. The problem considered by the paper is also of potential interest to the federated learning community. Some suggestions made by reviewers were partially addressed but they are not critical.
Decision: Accept (poster)