Distributed Quasi-Newton Method for Fair and Fast Federated Learning
Authors: Shayan Mohajer Hamidi
Linfeng Ye
Venue: Accepted by TMLR ()

Abstract: Federated learning (FL) is a promising technology that enables edge devices/clients to collaboratively and iteratively train a machine learning model under the coordination of a central server. The most common approach to FL is first-order methods, where clients send their local gradients to the server in each iteration. However, these methods often suffer from slow convergence rates. As a remedy, second-order methods, such as quasi-Newton, can be employed in FL to accelerate its convergence. Unfortunately, similarly to the first-order FL methods, the application of second-order methods in FL can lead to unfair models, achieving high average accuracy while performing poorly on certain clients' local datasets. To tackle this issue, in this paper we introduce  a novel second-order FL framework, dubbed distributed quasi-Newton federated learning (DQN-Fed). This approach seeks to ensure fairness while leveraging the fast convergence properties of quasi-Newton methods in the FL context. Specifically, DQN-Fed helps the server update the global model in such a way that (i) all local loss functions decrease to promote fairness, and (ii) the rate of change in local loss functions aligns with that of the quasi-Newton method. We prove the convergence of DQN-Fed and demonstrate its \textit{linear-quadratic} convergence rate. Moreover, we validate the efficacy of DQN-Fed across a range of federated datasets, showing that it surpasses state-of-the-art fair FL methods in fairness, average accuracy and convergence speed. The Code for paper is publicly available at \url{https://anonymous.4open.science/r/DQN-Fed-FDD2}.

Published in Transactions on Machine Learning Research (01/2025)
Distributed Quasi-Newton Method for Fair and Fast Feder- ated Learning
Shayan Mohajer Hamidi
smohajer@nuuaterloo.cr
Deportment of Electrical & Computer Engineering University of Waterloo
Linfeng Ye
linfeng Seerrnggy@@man ge@emall utoronto.co
Edward S. Rogers Sr. Deportment of Electrical & Computer Engineering University of Toronto
Reviewed on OpenReview: https: openreview. net/ forum? iittormmii--tiee id=Kbted50cns
Abstract
Federated learning (FL) is promising technology that enables edge devices/cliee to collaboratively and iteratively train machine learning model under the coordination of central server. The most common approach to FL is first-order methods, where clients send their local gradients to the server in each iteration. However, these methods often suffer from slow convergence rates. As a remedy, second-order methods, such as quasi-Newton, can be employed in FL accelerate convergence. Unfortunately, similarly the first-order FL methods, the application of second-order mothods in FL can lead unfair models, achieving high average accuracy while performing poorly on certain clients' local datasets. To tackle this issue, in this paper introduce novel second-order FL framework, dubbed distributed quasi-Newton federated lcarning (DQN-Fed). This approach seeks to ensure fairness while leveraging the fast convergence properties of quasi-Newlon methods in the FL context. Specifically, DQN-Fed helps the server update the global model in such a way that (i) all local loss functions decrease to promote fairness, and (ii) the rate of change in local loss functions aligns with that of the quasi-Newton method. We prove the convergence of DQN-Fed and demonstrate its linenr-quadratic convergence rate. Moreover, we validate the efficacy of DQN across a range of federated datasets, showing that it surpasses state-of- the-art fair FL methods in fairness, average accuracy and convergence speed. The Code for paper is publicly available at https://anonymous. http:///woooo.aoooooo..eee/////r
1 Introduction
Traditionally, machine learning (ML) models are trained centrally, with data stored in central server. However, in modern applications, devices often resist sharing private data remotely. To address this, federated learning (FL) was introduced by McMahan et al. (2017), where each device trains locally with a central server. In FL, devices share only local updates, maintaining data privacy. FedAvg, proposed by McMahan popular first-order FI. method. It combines local stochastic gradient descent (SGD) on each client with iterative model averaging. The server sends the global model to selected clients (Eichner let al. 2019 Wang et al. (202aa), which perform local SGD on their training data. Local gradients are sent back to the server, which calculates their (weighted) average update the global model iteratively.
et al. (017),
Nevertheless, first-order FL methods tend to exhibit slow convergence, particularly in terms of the number of ilerations or communication rounds required (Krouka et al. 2022). More precisely, the convergence rate of first-order FL algorithms sublinear, i.e. the required number communication rounds T. to achieve c-accurate solution is T. ( Additionally, their convergence speed highly influenced by the condition number, which is dependent on several factors, including: (i) the architecture of the model being trained, (ii) the choice of loss function, and (ii) the distribution of the training data (Elgabli et al. 2022

---

Published in Transactions on Machine Learning Research (01/2025)
To overcome this limitation, second-order methods can be applied in FL to significantly boost convergence speed (Safaryan et al. 2022 Elgabli et al.
2022 Hamidi et al. 2024a). By est the local curvature of the loss landscape, these methods provide more adaptive and efficient update directions, leading to faster and more reliable convergence (Battiti 1992). Specifically, in second-order FL methods, the clients compute the Newton direction for their respective local loss functions and send these directions to the server. The server then averages the Newton directions from all clients and updates the global model in the direction of this average (Ghosh et al. 2020 Zhang & Lin. 2015). Moreover, since Newton's methods require calculating the inverse of the Hessian matrix at each iteration computationally expensive operation the inverse is typically approximated using iterative techniques, leading to quasi-Newton methods (Wang et al. 2018).
While Newton-type methods accelerate the convergence of FL algorithmss, they do not guarantee that the averaged Newton direction computed by the server is a descent direction for all clients a limitation also present in first-order FL. methods (Hu et al. 2022 Pan et al. 2024 Chen et al. 2024). In other words, upon updating the global model toward this averaged direction, the loss function for some client my not decrease, polentially leading to poor performance on their private datasets. As result, the learned model might. exhibit unfairness, with high average accuracy but poor performance for clients whose data distributions differ from the majority" [ Thus, naively applying Newton methods in FL can lead to the training of an unfair model (see Section for results).
To tackle the issue mentioned above, this paper presents a novel second-order FL framework, dubbed distributed quasi-Newtor federated learning (DQN-Fed). This approach aims to ensure fairness while leveraging the fast convergence properties of quasi-Newton methods in the FL setting. In particular, DQN-Fed Fed is designed to assist the server in updating the global model such that (i) all local loss functions decrease resulting in training fair model, and (ii) the rate of change in local loss functions aligns with the rate of change in the quasi-Newton method. To achieve this, based on the received local quasi-Newton directions and the local gradients, the server identifies an updating direction that satisfies both of the aforementioned conditions. This will in turn yield a fair FL algorithm, as the global updating direction is descont for all the clients. Moreover, the convergence of DQN-Fed fast, as the rale of change in the local loss functions follow quasi-Newtor methods.
In summary, the contributions of the paper are follows:
We introduce distributed quasi-Newton federated learning (DQN-Fed), method designed to assist the server in updating the global model to achieve both fairness and fast convergence in FL.
We present a closed-form solution for calculating the global updating direction, distinguishing our approach from many existing fair FL methods that depend on iterative or generic quadratic programming techniques.
Leveraging common assumptions in FL literature, we establish the convergence proof for DQN-Fed algorithm across various FL setups. In addition, we prove the convergence rate of the proposed method, and show that DQN-Fed exhibits a linear-quadratic convergence rate. Specifically, the convergence is either quadratic, with ( log !) where X, L and are constants.
T. = O (log log! }), or linear, with T. =0 O
Through comprehensiue experiments conducted on seven different datasets (six vision datasets and one language dataset), we demonstrate that DQN-FFed attains superior fairness level among clients, and converges faster compared to the state-of-the-art fair alternatives.
2 Related Works
Fairness in FL. The literature offers a myriad of perspectives to address the challenge of fairness in FL.
These methods include client selection Nishio & Yonetani 2019: Huang et al.] 2020a 2022 Yang et al.
2021), contribution Evaluation (Zhang et al. 2020; Lyu et al. 2020 Song et al. 202 Le et al. 2021). incentive mechanisms (Zhang el al.) 2021 Kang el al. 2019 Ye el al. 2020 Zhang el al. 2020 and the methods based on the loss function. Specifically, our work falls into the latter category. This approach aims
'Learning an unfair model is a common challenge in first-order FL methods as well, and there is substantial body of research dedicated to developing fair FL models (Mohri al. 2019 Du et al. 2021 Li et 2020 Hu al. 2022 Hamidi &
YANG 2024).
2

---

Published in Transactions on Machine Learning Research (01/2025)
to achieve uniform test accuracy across clients. In particular, works within this framework focus reducing the variance of test accuracy among participating clients. We provide a thorough review on fairness issue in ML and FL in Appendix J
Second-Order FL methods. DistributedNeewton (Ghosh et al. 2020 and LocalNewton Guupta et al, 2021 perform Newton's method instead of SGD on local machines to accelerate the convergence of local models. FedNew (Elgabli et al, (022) utilized one pass ADMM on local machines calculating local directions and approximate Newton method to update the global model. FedNL (Safaryan et al.) 2022) send the compressed local Hessian updates to global server and performed Newton step globally. Based cigendecomposition of the local Hessian matrices, SHED (Dal Fabbro et al. 2024) incrementally updated eigenvector-eigenvalle pairs to the global server and recovered the Hessian to use Newton method. Recently, Li et al. (202)) proposed federated Newton sketch methods (FedNS) to approximate the centralized Newton's method by communicating the sketched square-root Hessian instead of the exact Hessian.
3
Notation and Preliminaries
3.1 Notation
We denote by [K] the set of integers {1, K, In addition, we define {f<]ke(K]] = f... for a scalar/function f. We use bold small letters to represent vectors, and bold capital letters to represent matrices. Denote by u, the i-th element of vector u. For two vectors u, b E RR, we say u S b iff u, I b, for Vi E [d] Denote by u their inner product, and by proj,(v) p. u the projection of a onto the line spanned by u.
wa
3.2 Preliminaries and Definitions
Since methodology is based techniques in multi-objoctive minimization (MoM), first review some concepts from MoM, particularly the multiple gradient descent algorithm (MGDA).
3.2.1 Multi-Objective Minimization for Fairness
Denote by f(0) (fe((0)AkEKK) the set of local clients' loss functions; 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", it is not possible to reduce any of the local objective functions fi without increasing at lcast another one. Here, 0" called a Parcto-optimal solution of Equation { Although finding Pareto-optimal solutions can be challenging, there are several methods identify the Pareto-stationary solutions instead, which are defined as follows:
Definition 3.1. Parelo-stationary Mukai 1980 The vector 0* is said to be Pareto-stationary iff there exists convex combination of the gradient-vectors (0%)))) which is equal to zero; that is, ΣK (00%(0%) = 0, where A > 0, and Σk As- 1.
Lemma 3.2. Mukai 1980 Any Parcto-optimal solution is Pareto-stationary. On the other hand, all (O)) 's are convex, then any Pareto-stationary solution is weakly Pareto optimal
There many methods in the literature to find Pareto-stationary solutions among which MGDA is popular one Mukai 1980 Fliege & Svaiter 2000 Désidéri 2012)
20* called weakly Pareto-optimal solution of Equation if there docs 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/2025)
MGDA adaptively tunes {>x [e([]] by finding the minimal-norm element of the convex hull of the gradient vectors defined as follows (we drop the dependence of gy to O for ease of notation hereafter)
g = [g E R =
ANgus 2 1220
0:
A 1}.
(2)
R=1
Denote the minimal-norm element of G by dg)) Then, either (i) o(g) and therefore based on Lemma 3.2 (g) is Pareto-stationayy ionary point; or (ii) (G) + and the direction of - (G) is a common descent direction for all the objective functions (()) Désiidéri 2009), meaning that all the directional derivatives {øx (EG) are positive. Having positive directional derivatives is a necessary condition to ensure that the common direction is descent for all the objective functions.
3.2.2 Newton-type methods
First-order FL methods face challenges with slow convergence, measured in terms of the number of iterations or communication rounds. Additionally, their convergence speed is intricately linked to the condition number, inftuenced by factors such as the model's structure, choice of loss function, and distribution of training data. contrast, second-order methods exhibit significantly faster performance due their additional computational effort in estimating the local curvature of the loss landscape. This, in turn, yields faster and more adaptive update directions. Despite requiring more computations per communication round, second-order methods achieve fewer communication rounds. In the context of FL, where communication often poses bottleneck rather than computation (Yang & Hamidi 2024 Mohajer Hamidi & Bereyhi 2024), the appeal of sccond-order methods has grown. Notably, the Newton's 's direction is obtained as
N = (V -V=
(3)
4
Motivation and Methodology
We discuss our motivation in Section 4.1 based on which we elaborate on the inner-working of DQN-FI. in Section
4.1 Motivation
We begin with finding out how much the local loss function fa(+), & E [K]. changes when the server updates the global model as 0²+1 0º o7'o' at round t. In other words, we want to determine the rate of change Afk ) E fx(0t+1) (e') for the local loss functions. To do this, by writing the first-order Taylor expansion for the local loss function fs(.), we obtain:
fx(tt(l) = (0' -n'0') = fa((") -n'gi
(4)
(f = -n'gi
o'
(5)
As per Equation (5) f.) changes by amount of -n' g of when the server updates the global model. Hence, if g). d 2 0, the global updating direction is descent for client k. and (e') < 0.
Nevertheless, updating toward a descent direction does not guarantee any meaningful convergence. Indeed, what can guarantee the convergence of GD-like algorithms the rate of change in the loss function in each iteration This is fact. what makes the second-order methods to converge faster as the rale of change the loss functions automatically determined by the Hessian matrix.
This motivates us to see how the server update the global model such that the rate of change in the local loss functions is the same that when local clients update their local loss function using second-order methods.
ST fa(-) is L-smooth, the convergence of gradient descent algorithm guaranteed for of E Jo, 2
4

---

Published in Transactions on Machine Learning Research (01/2025)
Specifically, let di denote the rate of change in local loss function fx when it updates its local model using Newton method; then, we have
dk = gi ON si ((T))) s1) (g) (+1))((1+))
Our goal is to assist the server in updating the global model such that, after the update, the rate of change for client becomes di Achieving this not straightforward task. In the following section, we derive a closed-form solution to meet this criterion.
4.2 Methodology
Our method is partially inspired from MGDA algorithm, but incorporates several key modifications. Specifi- cally, our approach comprises two stages: (i) gradient orthogonalization with tailored scaling strategy; and (ii) finding the optimal weights to combine these orthogonal gradients.
4.2.1 Stage 1, Gradient Orthogonalization
The clients send the local gradients [Øg]eejK] the server, and then the server first generates mutually orthogonal set [0æ]ke[k] that spans the same K-dimensional subspace I&d as that spanned by [gk] To this aim, the server exploits a modified Gram-Schmidt orthogonalization process over [g*]ke[k] in the following manner 5
Ø1 = 0ı/di,
(7)
9. 9:
Σ
1i=1 proig, (gx)
for 2,.... K,
(8)
di
6: 0:
where > 0 is scalar. Note that the orthogonalization approach in stage 1 is feasible if we assume that the K gradient vectors [gatke[k] are linearly independent. Indeed, this assumption is reasonable considering that (i) the gradient vectors { are K vectors in d-dimensional space, and d >>> K for the DNN 6 and that (ii) the random nature of the gradient vectors due the non-iid distributions of the local datasels.
4.2.2 Stage 2, finding optimal weights
this stage, we aim to find the minimum-normy norm vector the convex hull of the orthogonal gradients found in Stage (I). First, denote by 9 the convex hull of gradient vectors {0x that is,
g = (g E
Au
A
0:
A4 = 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
g" = arg min gec
(9)
which accordingly finds X" For an element E G, we have
K
K
|1
Σ AR
0 11
(10)
k=1
'Here, orthogonality is in the of standard inner product in Euclidean space.
8The reason for such normalization will be clarified later. 6 Also, that tackle non-iid distribution user-specific data, it is common practice that selects different. subset, of clients in each round (McMahan et. al. 2017).
5

---

Published in Transactions on Machine Learning Research (01/2025)
where used the fact that (ekk are orthogonal.
To solve Equation (9 we first ignore the inequality A 2 0, for &o E [K], and then we observe that it is automatically satisfied. Thus, we make the following Lagrangian to solve the minimization problem in Equation (9
aL Hence, 8yg
2 0 a; and by setting this equation to zero we obtain
(11)
2 2 12
On the other hand, since E Av- = 1, from Equation 11 we have a > 2i T6g
from which the optimal
X is obtained follows
for le E [K].
(12)
Σx= k= @
Note that Ag > O, and therefore the minimum norm vector we found belongs to G. Using the X found in calculate d' -E Ag the minimum norm clement in the convex hull g.
12
Theorem 4.1. the server updates the model toward of Ek= Ag0s, the rate of change for client k is proportional to di Ak E [K].
Proof. We shall find the directional derivative of loss function Sas Vk [K], over di:
k
k-1
K
9x 00'
d2
9
9
proj
B. (gx)
No
(13)
9:
1=1
>ill@all
di
9
0
1111111
(14)
9, 9,
1= 9, 9
d3
9k 9
9k 9:
(15)
0 9
9. 9
df
2 d
0,
(16)
2k K
T
where (i) Equation
13 is obtained by using definition of â. in Equation (8) (ii) Equation 14 follows from
the orthogonality of [gx k= vectors, and (iii) Equation 150 is obtained by using Equation
K
Hence, to realize rate of change similar to the Newton step, at iteration t, the server set the global learning rate as 17 Ek= [
,, and update the global model as:
K
r+ = -00-01"' n = 0¹
(17)
R= g
To sunmarize, updating the global model as in Equation 17 provides two key advantages:
(i) All local loss decreases (as shown by the inequality in Equation (66)):
(ii) The rate of change for each local loss function aligns with that of the Newton method.
Similarly to the conventional GD, we note that updating the global model as 17 necessary condition to have 1(0+1) < f(0'). In Theorem 4.2 whose proof is differed to Appendix we state the sufficient condition to satisfy f -1) < f(0").
Theorem 4.2. Assume that f (fa]ee[k] are L-Lipschitz smooth. If the step-size 1f =EK I e [0, i min(d' (ettk)) then f(0'+1) < f(0)) and equality is achieved iff of 0.

---

Published in Transactions on Machine Learning Research (01/2025)
4.3 DQN-Fed Algorithm
Since Newton's method requires the computation of the inverse Hessian matrix, which is computationally expensive, employ quasi-Newton methods that approximate the inverse of the Hessian using gradient information. The BFGS algorithm (Broyden 1970h is one such approach. Let B denote the matrix obtained
using BFGS algorithm, where B R (H Using B dz in Equation 6 can be approximated by
d = Blgh-
(18)
Lastly, similar to many recent FL algorithms McMahan et al. perform couple of local epochs E We summarize DQN-Fed in Algorithm
2017 Li et al.
2019a), allow each client to
Algorithm 1: DQN-Fod.
Input: Number of global epochs T, global learning rate n/, number of local epochs E, local datascts [Da]aek.
for t= o
do Server randomly selects a subset of devices St and sends of to them. for device &o E St in porallel do
Set 0. = 0' and 00 for e e= = ..... do Perform BFGS algorithm as follows
Sel & 0% 0 and y ( V
Iteratively update matrix B using information from B Si, yi according to:
( B
yi(y))
B B
(19)
B
(sf)
end
Use _ to calculate dz from Equation 18
Send local gradient 92 ( and dz to the server.
end
Server finds [āx (REKK) form Equations and g
Server finds A from Equation 12
Server calculates d' > Agg..
k==
Server updates the global model as 0 + 0¹ - 1
end
Output: Global model 0¹.
4.4 Convergence results
In this section, we analyze the convergence behavior of DQN-Fed by presenting two sets of theorems:
Set 1: Theorems 4.3 to 4.5 which focuses on the fairness of DQN-Fed and establishes various types of convergence to Pareto-optimal points under different settings. Specifically, we examine the following cases based on how clients update their local models: (i) using SGD with E (ii) using GD with 1, and (iii) using GD with E 1. Among these, the strongest convergence guarantee provided for the third scenario.
Set. 2: Theorem 4.6 which addresses the oplámality gap by analyzing the number of communication rounds, Te, required to achieve an e-accurate solution. This provides convergence rate for DQN-Fed.
Theorem 4.3 (E
& local SGD). Assume that f {fa]ee(K) are I-Lipschitz continuous and L- Lipschitz smooth, and that the global step-size of satisfies the following three conditions: (i) n/ (0, +.1. (ii) limm-zae Et" 1²th oc, and (iii) lim Σt n' < oo; where of E[llgA 0.\i112 is the variance of

---

Published in Transactions on Machine Learning Research (01/2025)
stochastic common descent direction. Then
lim T-000 t=...... B|||o1|| + 0.
min
(20)
In Theorem 4.3 the variance of arises from the stochastic nature of the gradient estimates. Controlling of is intimately related to ensuring that the variance of the stochastic common descent direction diminishes, at least does not accumulate too quickly. The condition limr Li= n' oc essentially states that the global step sizes nf must shrink at a rate that sufficienlyy "smooths out" variance over time.
But how can the condition limy- Et n < oc be guaranteed in practico? In the following, we provide two possible ways to meet this condition:
First, by choosing non-increasing global step-size schedule {17²) that decays to zero at sufficiently fast rate, the effective "weighted sum" " Σ 7'0, < oo remains finite. For example, if n/ = O(t))), for some a > 0, and if a, does not grow faster than O(19) for some B < a, then E, will converge.
Second, implementing variance reduction methods (e.g., control variates, variance-reduced stochastic gradient estimators) within local updates can ensure that d, does not persistently remain large. In federated settings, this can be achieved by techniques such as periodically synchronizing with global model (which reduces drift and variance), incorporating momentum-bant based methods, or employing mini-batching strategios that limit stochastic fluctuations.
Theorem 4.4 (E >> 1 & local GD). Assume that f = (/x kE[K] are L-iischiizz continuous and L-Lipschitz smooth. Denote by 'f' and y the global and local learning rates, respectively. Also, define ç = ||A* Xgel. where Xy the optimum weights obtained from pscudo-gradients after E local epochs. We have
min ||'||| + 0, T t
lim
(21)
if the following conditions satisfied: (i) n/ (0, 1 (ii) limp oo Ex co, (iii) lime 0, (iv) lim 17 0, and (v) lim 5t -0000 O.
In Theorem 4.4 c || Agll measures the deviation between the true optimum X and the optimum after E local epochs, X The condition lim 5 + 0 reflects the
obtained from the requirement that local model updates become increasingly aligned with the true global optimum as training progresses. Below, we discuss two strategics to ensure this condition is satisfied.
First, as stated, both the global and local learning rates should diminish over time: lim, nt' and lime 7) + 0. As these rates decrease, the updates become more conservative, allowing the local solutions X/z to approach the global solution x
Second, adjusting the frequency of global synchronization over time helps ensure that local models do not drift too far from the global model. By increasing synchronization frequency or using adaptive synchronization stratogics as training progresscs, one can reduce the gap Ç*.
Before introducing Theorem 4.5 we first introduce some notations. Denote by 0 the Pareto-stationary solution set of minimization problem arg ming f0)). Then, denote by 0* the projection of 0* onto the set 0; that is, 0" arg minøe
0 0112
Theorem 4.5 (E 1 & local GD). Assume that (fee [e(KR are I-Lipschitz continuous and o-convex, and that the global step-size v/' satisfies the following two conditions: (i) lim4 E/ fi - co, and (ii)
lim Ej < co. Then almost surely 0r + 0"; that is,
P lim (0' - 0-) =0) =
(22)
1+000
where PPEE) denoles the probability of event E.
In general, the Pareto-stationary solution of multi-objective minimization problem forms with cardinality infinity Mukai 1980
8

---

Published in Transactions on Machine Learning Research (01/2025)
The proofs for Theorems
are provided in Appendices B.1 to B.3 respectively. Note that all the provide some types of convergence to a Pareto-optimal solution of optimization problem Specifically, diminishing d' in Theorems 4.3 and
4.3 to 4.5
Theorems 4.3 to 4.5
in Equation Pareto-optimal point (Désidéri 2009.. On the other hand, Theorem 4.5 guaranlee in an almost. surely lashion.
4.4
implies that we are reaching to a
explicitly provides this convergence
In addition, the following theorem shows that DQN-Fed has linear-quadratic convergence rate.
Theorem 4.6 (Convergence rate of DQN-Fed). Assume that = 1 and clients perform local GD. In addition, assume that the global loss function is twice continuously differentiable, L-Lipschitz gradient (L-smooth) and A-strongly convex. Note that the strong convexily of the global loss function implies that there exists a unique optimal model parameter, which we denote by gopt, In addition, assume that the matrix B, is a H,
6-approximate true inverse Hessian H, that |
1| S 8|| Then,
L8
0o p00t|
+ -1/
t S to
00 0opt|
(23)
0o
000t
+ 11 > to
where A/ and A are defined as follows
( 1 1r>
27
}
16
(lo- +
(24a)
L8 -1 1
I
1 7
(4) 1
2X²²" 2
1(1 - 20- + +1.
A/
(24b)
Le -1 1
with
to = max f0,
00
12l Dol -
2L
(24c)
L
and
7 21a
Poll
(24d)
Proof. The proof is differed to Appendix D
As per Theorem 4.6 DQN--Fed method has linear-quadratic convergence rate, In fact, the quadratic term in (23 is exactly the same as that of Polyak & Tremba (2020); yet, the lincar term is the result of approximating the local Hessian matrices using BFGS method.
In the following corollaries, our objective is to determine the required number communication rounds T. such that |0., - - S
Corollary 4.7. [Quadratic convergence rate] Tf |00 @opt]
A then DQN-Fed has quadratic
convergence rate:
||0, - 0opt| | I 2A'.
(25)
X Also, if LR < 1, we have
T, = o (10g log log !)
(26)
which is also called super-linear convergence rate.
Corollary 4.8. [Linear convergence rale] On the other hand, II 100 DQN-Feed method has a linear convergence rate:
0o0i||
2
4
and
L8
1, then
X
L8 x )
|0 - popt|
<
1100
0
(27)
and,
T. =0
log
(28)
log( L5
9

---

Published in Transactions on Machine Learning Research (01/2025)
The proof for Corollary 4.7 and 4.8 can be found in Appendix E and respectively.
Remark 4.9. is worth noting that for distributed GD-like methods, the number of commuicatiin rounds nceded to achieve a desired precision c, follows a linear convergence rate. Specifically, we have T. O (f log 4). This underscores the superiority of DQN-Fed in terms of convergence rate.
5 Experiments
In this section, we conclude the paper by presenting scries of experiments demonstrate the performance of DQN-Fed. We also conduct a comparative analysis to assess its effectiveness against stale-of-the-arl alternatives using various performance metrics.
We conduct comprchensive set of experiments across seven datascts. In this section, we present results for four datasets: CIFAR-(100 (10, 100} (Krizhessky et al. 2009). FEMNIST (Caldas et al. 2018) and Shakespeare [McMahan et al. 2017)- Results for Fashion MNIST (Xiao et al., 2017). Tiny Inageeeteee
Datasets:
Le & Yang 2015), and CINIC-10 (Darlow et al. 2018) are discussed in Appendix G To demonstrate
DQN-Fed's effectiveness across different FL scenarios, we examine two FL setups for each dataset in this
section. Furthermore, we evaluate DQN-Fed's performance on real-world noisy dataset, Clothing1M (Xiao
al. 2015): in Appendix T
Benchmarks: We compare the performance of DQN-Fed against some fair first-order FL and some second-order FL methods. The fair FL algorithms include q-FFL (Li et al.) 2019a), TERM (Li et al. 2020). FedMGDA+ (Hu ct al.] (022). Ditto (Li et al. 2021 FedLF (Pan et al. 2024). FedHEAL (Chen et al.
2024). and conventional FedAvg (McMahan al. 2017 and also second-order FL methods include FedNL
[Safaryan et al. 2022) and FedNew (Elgabli et al.
2022
It is worth noting that we conduct grid-scarch to find the best syper-paramoters for cach of the benchmark methods including DQN-Fed in our experiments. The details of this hyper-parameles tuning are reported in Appendix
Performance metrics: Denote by a the prediction accuracy on device We use ā = 1
K Σx a as
the average test accuracy of the underlying FL algorithm, and use 0a = V / Ea= - a)² as the standard deviation of the accuracy across the clients. Furthermore, we report Worst 10% (5%) and Best 10% (5%) accuracies as a common metric in fair FL algorithms (Li et al. 2020).
Notations: We use bold and underlinod numbers to denote the best and second best performance, respectively. We use and K to represent. the number of local epochs and that of clients, respectively.
5.1 CIFAR-10
CIFAR-10 datasot [Krizhevsky et al. 2009 has 50K training and 10K test images of size 32 32 labeled for 10 classes. The batch size is equal to 64 for both of the following setups.
Setup 1: Following Wang al. (2021b), we sort the dataset based on their classes, and then split them into 200 shards. Each client randomly selects two shards without replacement so that cach has the same local dataset size. We use a feedforward neural network with 2 hidden layers. We fix E = 1 and K = 100. We carry out 2000 rounds communication, and sample 10% of the clients in each round. We run SGD on local datasets with stepsize 7) = 0.1.
Setup We distribute the dataset among the clients deploying Dirichlet allocation with B 0.5. We use ResNet-18 (e et al.) 2016) with Group Normalization Wu & He 2018). We perform 100 communication rounds in each of which all clients participate. We set == 1, K 10 and 1 0.01.
Waagg et al. 2020
5.1.1 Wall-Clock Time
For the first setting, we also measure and report the wall-clock time (in seconds) for both the benchmark methods and DQN-Fed. These results, presented in Table were obtained using single NVIDIA RTX 3090
10

---

Published in Transactions on Machine Learning Research (01/2025)
Table Test accuracy on CIFAR-10. The reported results are averaged over seeds.
Setup
Setup 2
Algorithm
Oa
W(5%)
B5%%
a
Oa
W(10%)
B(10%)
Naive Orrer
FedAvg
46.85
3.54
19.84
69.28
63.55
5.44
53.40
72.24
q-PFL.
46.30
3.27
23.39
68.02
57.27
5.60
47.29
66.92
FedMGDA
45.34
3.37
24.00
68.51
62.05
4.88
52.69
70.77
Fair First-Order
FodHEAL
46.40
3.61
19.33
69.30
63.05
4.95
48. 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
FedNL
47.33
3.92
24.41
69.52
64.72
6.02
56.20
72.33
Second-Ores
FedNew
47.51
3.68
25.77
69.74
64.58
6.11
56.96
72.12
DQN-Fed
47.72
3.20
29.34
69.37
64.88
4.90
58.01
72.88
As shown, the second-order methods (last three columns) exhibit higher computational times. Notably, among the second-order methods, DQN-Fed demonstrates the fastest runtime.
GPU.
Table 2: Wall-clock time (in seconds) for benchmark methods and DQN-Fed on CIFAR-10, Setup 1.
Algorithm
FedAvg
q-FFL
FedMGDA
TERM
Ditto
FedNL
FedNew
DQN-Fet
Wall-clock (s) 1250
1360
1333
1312
1320
2320
2140
1810
5.1.2 Ablation Study the Percentage of Client Participation
In this subsection, examine the impact of varying client participation rates the performance of DQN-Fed and the benchmark methods. Specifically, reproduce the results from CIFAR-10 (Setup 2) using 10% and 50% client participation, while the previously reported results in Table correspond to 100% participation. The results are summarized in Table 3
The following obsorvations are made:
(i) DQN-Fee continues to outperform the benchmark methods in both fairness and average accuracy across all participation levels.
(ii) As the percentage of client participation decreases, the performance of all methods shows slight decline, highlighting the importance of client participation in federated learning settings.
Table Ablation study on client participation for Setup on CIFAR-10. Test accuracy results are averaged over seeds.
10% Participation
50%
Participation
Participation
Algorithm
à
B(10%)
da
B(10%)
Naive First- Orste-Order
FedAvg
61.41
6.36
68.12
62.74
6.01
70.15
q-FFL
56.55
6.24
65.89
58.97
5.95
68.22
FedMGDA
61.05
5.80
69.07
62.57
5.54
70.52
Fair First-Order
FedHEAL
61.26
6.12
68.52
62.92
5.71
70.72
TERM
63.22
5.93
70.56
63.81
5.66
71.83
Ditto
62.87
6.07
69.92
63.51
5.76
71.24
FedNL
63.25
6.16
70.81
64.15
5.90
71.92
Second-Order
FedNew
63.80
6.07
71.21
64.56
5.80
72.08
DQN-Fed
64.14
5.67
72.21
64.71
5.48
72.55
11

---

Published in Transactions on Machine Learning Research (01/2025)
5.2 CIFAR-100
C1FAR-100 (Krizhevsky et al. 2009) has the same number of samples as CIFAR-10, but comprises 100 classes compared to the 10 classes found in CIEAR-10.
The model for both setups ResNet-18 (He et al. 2016 with Group Normalization (Wu He 2018 where
all clients participate each round. We also E' ==1 and n 0.01. The batch size equal to 64. The
results are reported in Table 4 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 2: We set K = 50 and B = 0.05 for Dirichlet allocation, and use 200 communication rounds.
Table 4: Test accuracy on CIFAR-100. The reported results are averaged over 5 different seeds.
Setup
Setup
Algorithm
a
aa
W(10%)
B(10%)
ā
Oa
W(10%)
B(10%)
Naive First-Order
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.24
11.09
34.02
FedMGDA
29.12
4.17
25.67
39.71
20.15
5.41
11.12
33.92
Fair First-Order
FedLF
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
FedNL
31.58
4.55
27.14
40.62
22.74
6.02
12.15
34.44
Fair Orrst
FedNew
30.95
4.39
27.19
40.55
21.16
5.27
11.77
34.27
DQN-Fed
32.58
3.60
27.91
40.99
23.15
4.45
12.81
35.11
5.3 FEMNIST
FEMNIST (Federated Extended MNIST) Caldas et al. 2018 a federated image dataset distributed over 3,550 devices which has 62 classes containing 28 x 28-pixel images of digits (0-9) and English characters (A-Z, a-z). For implementation, we use CNN model with 2 convolutional layers followed by fully-connected layers. The batch size is 32, and E = 2 for both of the following setups:
FEMNIST-original: We use the setting in Li et al. 2021 1 and randomly sample K = 500 devices and train models using the default data stored in each device.
FEMNIIST-Sewwdd: = 100. We sample 10 lower case characters ('a'-9') from Extended MNIST (EMNIST), and randomly assign classes each of the 100 devices.
Consistent with Li al. (2019a), use two other fairness metrics for this dataset: (i) the angle between the accuracy distribution and the all-ones vector denoted by Angle (?), and (fi) the KL divergence between the normalized accuracy and uniform distribution denoted by KT. (allu). Results for both setups are reported
in Table 5
5.4 Text Data
We use The Complete Works of William Shakespeare (MMMahan et al. 2017 as the dataset, and train an RNN whose input is 50-character sequence to predict the next character. We use E = 1, and let all the devices participate in each round. The results are reported in Table 5 for the following setups:
Sctup 1: Following McMahan et al. (2017), we subsample 31 speaking roles, and assign each role a client (K 31) to complete 500 communicatin rounds. We use model with two LSTM layers (Hochreiter & Schmidhuber 1997) and one densely-connected layer. The initial n 0.8 with decay rate of 0.95.
12

---

Published in Transactions on Machine Learning Research (01/2025)
Table Test accuracy on FEMNIST. The reported results are averaged over different seeds.
FEMNIST-origgnal
FEMNIST-skene
Algorithm
a
Qa
Ang (9)
KL (allu)
a
Fa
Ang (9)
KL. (allu)
Naive Orsser
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
FedMGDA
81.00
10.41
10.04
0.016
85.41
17.36
11.63
0.032
Fair First-Order
TERM
81.08
10.32
9.15
0.015
84.29
13.88
11.27
0.025
FedLF
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
FedNL
84.21
11.22
10.07
0.015
92.94
16.45
12.56
0.045
Fair First-Orde
FedNew
84.25
10.88
9.78
0.014
92.25
15.21
11.92
0.037
DQN-Fod
85.15
9.58
8.14
0.010
93.80
13.91
11.41
0.011
Setup 2: Among the 31 speaking roles, the 20 with more than 10000 samples are selected, and assigned to 20 clients. We LSTM followed by fully-connected layer. 7 2, and the number of communication is 100. Table 6: Test accuracy on Shakespeare. The reported results are averaged over 5 different seeds.
Setup
Setup
Algorithu
a
W(10%)
B(10%)
á
Oa
W(10%)
B(10%)
Naive First-Order
FedAvg
53.21
9.25
51.01
58.41
50.48
1.24
48.20
52.10
q-FFL
53.90
7.52
51.52
58.47
50.72
1.07
48.90
52.29
FedMGDA
53.08
8.14
52.84
58.51
50.41
1.09
48.18
51.99
Fair First-Order
FedLF
54.58
8.44
52.87
59.84
52.45
1.23
50.02
54.17
TERM
54.16
8.21
52.09
59.15
52.17
1.11
49.14
53.62
Ditto
60.74
8.32
53.57
64.92
53.12
1.20
50.94
55.23
FodNL
60.25
8.24
53.15
64.15
52.24
1.25
50.77
54.41
Fair First-Order
FodNew
60.59
7.55
53.18
64.09
52.49
1.19
50.82
54.36
DQN-Fed
61.65
6.55
53.79
64.86
52.89
0.98
51.02
54.48
6 Experimental Analysis
6.1 Analysis of Results
Based on the insights gleaned from Tables D and 4 to several noteworthy observations emerge:
(i) Naive socond-order FL methods, namely FedNL and FedNew, tend to train unfair models, despite achieving high average accuracy across clients.
(ii) Compared to the benchmark models, DQN-Fed consistently trains models that demonstrate significantly higher levels of fairness across clients.
(iii) The average accuracy of the model learned by DQN-Fed is higher compared to both first-order and second-order FL methods.
6.2 Comparison of Convergence Rate
In this subsection, we empirically compare the convergence speed DQN-Fed against several fair first-order methods. To do so, we use the four datasets from setup 1 described in Section 5 and plot the validation accuracy of different methods as function of commuication rounds. The results are shown in Figure [ As observed, DQN-Fed demonstrates faster convergence rate compared to all benchmark methods.
13

---

Published in Transactions on Machine Learning Research (01/2025)
Validation accuracy
Validation accuracy
40
FedAvg
FedAvg
q-FFL
20
q-FFL
30
+edMGDA+
AFL
FedFA
TERM
20
Ditto
10
Ditto
DQN-Fed
DQN-Fed
10
1000
2000
3000
4000
100
200
300
400
Communication rounds
Communication rounds
(a) CIFAR-10
(b) CIFAR-100
Validation accuracy
80
Validation accuracy
80
FedAvg
q-FFL
60
FedAvg
AFL
q-FFL
40
TERM
40
AFL
20
Ditto
TERM
DQN-Fed
20
DQN-Fed
1000
2000
3000
4000
5000
50
100
150
200
250
300
Communication rounds
Communication rounds
(c) FEMNIST
(d) PashionMNIST
Figure 1: The test accuracy curves Vs. communication rounds for DQN-Fed and the benchmark methods.
FedAvg
q-FFL
DON-Fed
60
# of clients
40
20
40
50
60
70
80
90
100
Test Accuracy
Figure 2: The histogram of clients accuracy for models trained via FodAvg, q-FFL and DQN-Fed.
6.3 Histogram of the Clients Accuracy
To gain deeper insight into the variability in client accuracy, we plot the accuracy histograms of 500 clients drawn from the original FEMNIST dataset. In particular, we compare three methods (i) FedAvg, (ii) FFFFL, and (iii) DQN-Fod Fod- optimized with well-tuned hyperparameters. As shown in Figure 2 the accuracy distribution under DQN-Fed is notably more concentratod, indicating a fairer spread of performance across clients.
14

---

Published in Transactions on Machine Learning Research (01/2025)
100
+
100
FodAvg
clients %
90
q- q-FFL
Improved clients %
TTrm
DQN--Fed
80
80
70
Improved
60
60
500
1000
1500
2000
100
200
300
400
Communication rounds
Communication rounds
(a) CIFAR-10
(b) CIFAR-100
Figure The number of improved clients Vs. communication rounds for DQN-Fed and the benchmark methods.
6.4 Percentage of Improved Clients
We measure the training loss before and after each communication round for all participating clients and report the percentage clients whose loss function decreased or remained unchanged, defined as
Pt Eres, I($x(0+)) < $x(09)
(29)
Se
where S. the participating clients in round I, and T(-) the indicator function. Then, we plot Pt versus communication rounds for different fair FL methods. The curves for CIFAR-10 and CIFAR-100 datasets are reported in Figure 3a and Figure 3b respectively. As scen, both DQN-Fed and FedMGDA+ consistently oulperform other benchmark methods in that fewer clients' performances get worse after participation. We further note that after enough number of commuication rounds, curves for both DQN-Fed and FedMGDA+ converge to 100%.
7
Conclusion
This paper introduced distributed quasi-Newton federated learning (DQN-Fed), a novel approach designed to ensure fairness while harnessing the fast convergence properties of quasi-Newton methods in FL setting, DQN- Fed aids the server in updating the global model by ensuring (i) all local loss functions decrease, promoting fairness; and (ii) the rate of change local loss functions matches that of the quasi-Newton method. We proved the convergence of DQN-Fed and establish its linear-quadratic convergence rate. Furthermore, we validated DQN-Fed's effectiveness across various federated datasets, demonstrating its superiority over state-of-the-ar fair FL methods.
References
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness in machine learning. Nips Iulorial, 1:2017, 2017.
Roberto Battiti. First-and second-order met for learning: between steepest descent and newlon's method. Neural computation, 4(2):141-166) 1992.
Charles G Broyden. The convergence class of double-rank minimization algorithms: the new algorithm. TMA journal of applied mathemalics, 6(3):222 231, 1970.
15

---

Published in Transactions on Machine Learning Research (01/2025)
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. ar Xiv preprint arXiv:1812.01097, 2018.
Yuhang Chen, Wenke Huang, and Mang Ye. Fair federated learning under domain skew with local consistency and domain diversity. In Proceedings of the IEEE/CVE Conference Computer Vision and Pattern Recognition, pp. 12077-12086 12086, 2024.
Sen Cui, Weishen Pan, Jian Liang, Changshui Zhang, and Fei Wang. Addressing algorithmic disparity and performance inconsistency in federated learning. Aduances in Neural Informalion Processing Systems, 34: 26091-26102, 2021.
Nicolò Dal Fabbro, Subhrakanti Dey, Michele Rossi, and Luca Schenato. Shed: A newton-type algorithm for federated learning based on incremental hossian cigenvector sharing. Automatica, 160:111460, 2024.
Luke N Darlow, Elliot J Crowley, Antreas Antoniou, and Amos J Storkey. Cinic-10 is not imagenet or cifar-10. arviv preprint Xrxi::1800, 03505, 2018.
Jean-Antoine Désidéri. Multiple-gradient descent algorithm (MGDA). PhD thesis, INRIA, 2009.
Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization. Comptes Rendus Mathemalique, 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. SIAM, 2021.
Hubert Eichner, Tomer Koren, Brendan McMahan, Nathan Srebro, and Kunal Talwar. Semi-cyclic stochastic gradient descent. In International Conference Machine Learning, pp. 7773. PMLR, 2019.
Anis Elgabli, Chaouki Ben Issaid, Amrit Singh Bedi, Ketan Rajawat, Mehdi Bennis, and Vaneet Aggarwal. newton-type method for federated learning. Tn International conference on machine learning, pp. 5861 5877. PMLR, 2022.
Fednew: A communication--ffiienn and privacy-presere
Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathematical methods of operations research, 51(3))479-4944 2000.
Avishek Ghosh, Raj Kumar Maity, and Arya Mazundar. Distributed newton communicate less and resist
byzantine workers. Advances in Neural Information Processing Systems, 33:18028-18033 2020.
Vipul Gupta, Avishek Ghosh, Michal Derezinski, Rajiv Khanna, Kannan Ramchandran, and Michael Mahoney. Localnewton: Reducing communication bottleneck for distributed learning. arXiv preprinl. arXiv:2105.07320, 2021.
Shayan Mohajer Hamidi and EN-HUI YANG. Adafed: Fair federated learning via adaptive common
descent direction. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https
Shayan Mohajer Hamidi, Mohammad Mchrabi, Amir K. Khandani, and Deniz Gündüzz. Over-the-air fedorated learning exploiting channel perturbation. In 2022 IEEE 23rd International Workshop on Signal Processing Advances Wireless Communication (SPAWC), pp. 1-5, 2022. doi: D0.100//PAANC553842200...333
Shayan Mohajer Hamidi, Ali Bereyhi, Saba Asaad, and H Vincent Poor. Gp-fl: Model-based hessian estimation for second-order over-the-air federated learning. arXio preprint 2x 2024a.
Shayan Mohajer Hamidi, Renhao Tan, Linfeng Ye, and En-Hui Yang. Fed-it: Addressing class imbalance in federated learning through an information- theoretic lens. In 2024 IEEE International Symposium Information Theory (ISIT), pp.
2024b. doi: 10.1109 1LL10//1ST133864222240001111
Shayan Mohajer Hamidi, Ali Bereyhi, Saba Asaad, and H Vincent Poor. Over-the-air fair federated learning via multi-objective optimization. Xix preprint ar arxiv:2501.00 033992 2025.
16

---

Published in Transactions on Machine Learning Research (01/2025)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the TEEE conference on compuler vision and pollern recognilion, pp- 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735-14 -1880, 1997.
Zcou Hu, Kiarash Shaloudegi, Guojun Zhang, and Yaoliang Yu. Federated learning moets multi-objoctive optimization. IEEE Transactions on Network Science and Engineering. 2022.
SHI Huaizhou, R Venkatesha Prasad, Frtan Onur, and IGMM Niemegeers. Fairness wireless networks: Issucs, 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 efficiency-boostiie client selection scheme for federated learning with fairness guarantee. IEEE Transactions Parallel and Distributed Systems, 32(():1552 1564, 2020a.
Tiansheng Huang, Weiwei Lin, Li Shen, Keqin Li, and Albert Y Zomaya. Stochastic client selection for federated learning with volatile clients. IEEE Internet of Things Journal, 2/20):20055-20077, 2022.
Wei Huang, Tianrui Li, Dexian Wang, Shengdong Du, and Junbo Zhang, Fairness and accuracy in federated learning. Xix preprint or 2r1::2012 10069, 2020b.
Jiawen Kang, Zehui Xiong, Dusit Niyato, Han Yu, Ying Chag-Chang Liang and Dong In Kim. Incentive design for efficient foderated learning mobile networks: contract theory approach. In 2019 IEEE VTS Asia Pacific Wireless Communications Symposium (APWCS), pp. 1-5. IEEE, 2019.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Mounssif Krouka, Anis Elgabli, Chaouki Ben Issaid, and Mehdi Bennis. Commuiication-eficient federated learning: A second order newton-type method with analog over-the-air aggregation. IEEE Trans. Green Commun. Netw., 6(3):1862-188) 2022.
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, 4874444844 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 Haffnrr. Gradient-based learning applied to document. recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998.
Jian Li, Yong Liu, and Weiping Wang. Fedns: A fast sketching newton-type algorithm for federated learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pp. 13509-13517, 2024.
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. In
International Conference on Learning Representations, 2020.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pp. 6368. PMLR, 2021.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence fedavg on non-iid data. arXiv preprint wtt::1111000180.0000 2019b.
Lingjuan Lyu, Xinyi Xu, Qian Wang, and Han Yu. Collaborative fairness in federated learning. Federated Learning: Privacy and Incentive, pp. 189 204, 2020.
17

---

Published in Transactions on Machine Learning Research (01/2025)
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, (71(3)8008-814 2018.
Shayan Mohajer Hamidi and Ali Bereyhi. Rate- constrannt quantization for communication--ffiiieee federated learning. arxiv e-prints, pp. arXiv-2409, 2024.
Shayan Mohajer Hamidi and Oussama Damen. Fair wireless federated learning through the identification of common descent direction. IEEE Communications Letters, 28(3):567 571, 2024. doi: 10.1109/LCOMM. 2024.3350378.
Mchryar Mohri, Gary Sivck, 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):
177-186, 1980.
Takayuki Nishio and Ryo Yonetani. Client selection for federated learning with heterogeneous resources in mobile edge. In ICC 2019-2019 IEEE international conference on communications (ICC), pp. 1-7. IEEE, 2019.
Zibin Pan, Chi Li, Fangchen Yu, Shuyi Wang, Haijin Wang, Xiaoying Tang, and Junhua Zhao. Fedlf: Layer- wise fair federated learning. In Proceedings of the AAA! Conference on Artificial Intelligence, volume 38, pp. 14527-14535, 2024.
Boris Polyak and Andrey Tremba. New versions of newton method: step-size choice, convergence domain and under-determined equations. Optimization Methods and Software, 35(6):1272 1303, 2020.
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtarik. Fednl: Making newton-type methods applicable to federated learning. In International Conference Machine Learning, pp. 18959-19010.
PMLR, 2022.
Zhendong Song, Hongguang Sun, Howard H Yang, Xijum Wang, Yan Zhang, and Tony QS Quek. Reputation- based federated learning for secure wireless networks. IEEE Internet of Things Journal, 9(2):1212-12 1226, 2021.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. arXiv preprint ar arXi::2002. 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 federated optimization. arXiv preprint arXiv:210700911 2021a.
Shusen Wang, Fred Roosta, Peng Xu, and Michael W Mahoney. Giant: Globally improved approximate newton method for distributed optimization. In Adv. Neural Inf. Process. Syst., pp. 2332 2342, 2018.
Zheng Wang, Xiaoliang Fan, Jianzhong Qi, Chenglu Wen, Cheng Wang, and Rongshan Yu. Federated learning with fair averaging. arXiv preprint arXiv:2144.14997 2021b.
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pp. 3-19, 2018
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image datasct for benchmarking 2017.
machine learning algorithms. arXie preprint
Tong Xiao, Tian Xia, Yi Yang. Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. In Proceedings of the IEEE conference on computer vision and pottern recognition, pp. 2015.
18

---

Published in Transactions on Machine Learning Research (01/2025)
En-hui Yang and Shayan Mohajer Hamidi. Systems and methods for training deep learning models, Novem- ber 21 2024. US Patent App. 18/666,958.
En-Hui Yang, Shayan Mohajer Hamidi, Linfeng Ye, Renhao Tan, and Beverly Yang. Conditional mutual information constrained deep learning for classification, 2023. URL
En-Hui Yang, Shayan Mohajer Hamidi, Linfeng Ye, Renhao Tan, and Beverly Yang. Conditional mutual information constrained deep learning: Framework and preliminary results. In 2024 IEEE International Symposium on Information Theory (ISIT), pp. 569-574, 2024. doi: 01L100/11T1378642224...000
Miao Yang, Ximin Wang, Hongbin Zhu, Haifeng Wang, and Hua Qian. Federated learning with class imbalance reduction. In 2021 29th European Signal Processing Conference (EUSIPCO), pp. 2174 1177. IEEE, 2021.
Dongdong Ye, Rong Yu, Miao Pan, and Zhu Han. Federated learning in vehicular edge computing: A selective model aggregation approach. IEEE Access, 8:23920 23935, 2020.
Linfeng Ye, Shayan Mohajer Hamidi, Renhao Tan, and EN-HUI YANG. Bayes conditional distribution estimation for knowledge distillation based on conditional mutual information. In The Twelfth International Conference Learning Representations, 2024. URL /ttrps://pparrevie.nntt///e wtt.////oororr//../////..lll
Jingfeng Zhang, Cheng Li, Antonio Gtobles-Kellyy and Mohan Kankanhalli. Hierarchically fair federated learning. Xiv preprint urXiv:2004.1033 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.
Yuchen Zhang and Xiao Lin. Disco: Distributed optimization for self-concoddant empirical loss. In ICML, pp. 362-33 370. PMLR, 2015.
19

---

Published in Transactions on Machine Learning Research (01/2025)
A Proof of Theorem 4.2
Proof. If all the (fa)kejK] are L-smooth, then
f(0¹ f(0') + (0 0¹) + | -
(30)
Now, for client [K], by using the update rule Equation 17 in Equation
30
we obtain
) S Sk((0') - v/ ga d' (1/)) L 10!1.
(31)
To impose f& (0 S f0()",, we should have
v'gk d' 2 (17") |0'11
(32)
2
T
| 1|
Ok dz Z
Σ
(33)
2
k=1
||
Σ i=
1
01
%/
1 T.
(34)
>k=1 1
K
2
<k==
K
10
2
17 <
(35)
L k-
B Convergence of DQN-Fed
In the following, provide three theorems analyse the convergence of DQN-Fed under different scenarios. Specifically, consider three cases: (i) Theorem [.1 considers E' = 1 and using SGD for local updates, (ii) Theorem B.2 considers an arbitrary value for and using GD for local updates, and (iii) Theorem B.4 considers E and using GD for local updates.
B.1 Case 1: & local SGD
Notations: We use subscript (.)s to indicate a stochastic value. Using this notation for the values wo introduced in the paper, our notations used the proof Theorem B.I are summarized in Table
Table 7: Notations used in Theorem B.1 for E & local SGD.
Notation
Description
gk..
Stochastic gradient vector of client
g,
Matrix of Stochastic gradient vectors (g., 9K.z|-
Stochastic gradient vector of client & after orthogonalization process.
g.
Matrix of orthogonalized Stochastic gradient vectors [.........ã..
Optimum weights obtained from Equation 12 using Stochastic gradients g..
0
Optimum direction obtained using Stochastic g.: that is, d, Σk=1 Tk.s.
20

---

Published in Transactions on Machine Learning Research (01/2025)
Theorem B.1. Assume that == [ff Me[K] are 1-Lipschitz continuous and L-Lipschitz smooth, and that the step-size of' satisfics the following three conditions: (i) of E (0, 2 (ii) limr->x Ei r/ + oo and
(iii) lim Ei n' oe; where of Æl 0.>, the variance of stochastic common descent direction. Then
B|| + 0. 7-000 t=.....
lim
min
(36)
Proof. Since orthogonal voctors (ōr (KERE span the same K-dimensional space as that spanned by gradient vectors {[æ) then
K
K
[(cehee[K] s.t. ==
Σ
X = gx'
(37)
k=1
1=1
Similarly, for the stochastic gradients we have
H. s.t. D. Σ
Ok. Okis
Σ
(38)
Define A, = gg' 9.X; gx' D.Y. where the last equality is due to the definitions Equations
and 38
We can find upper bound for f(0't1) follows
f(0'+1)= = f(0' 1/ n'0,)
(39)
f(0' n¹ Σ (kc,)
(40)
k=1
f(0' x'9,X,)
(41)
L(n²)²
S s00) n'0"
l1 X1I2
(42)
2
S f(0)) 7'' g X
((7') X1I22 + T/' 9 A. LOT
(43)
S f(0') - 7/(11 Ln)) x 1 A. + 117
(44)
where 40 uses stochastic gradients in the updating rule of DQN-
41
is obtained from the definition
in 38 42 holds following the quadratic bound for smooth functions considering the Lipschits continuity of
ff ffukee[K] and lastly 44h
holds
{fx he(k)-
Assuming 17' (0, }.] and taking expectation from both sides, obtain:
min Bl|le|ll < f(0o) - -E + Ens of (lo, + Lnfo L=0.....
(45)
Using the assumptions (i) lim Ey=0 n' + co, and (ii) lim El n' co, the theorem will be concluded. Note that vanishing d' implies reaching to a Pareto-stationary point original MoM problem. Yet, the convergence rate different in different scenarios as we see in the following theorems.
B.1.1 Discussing the assumptions
The assumptions over the local loss functions: The two assumptions I-Lipschitz continuous and L-Lipschitz smooth over the local loss functions are two standard assumptions in FI. papers providing some sorts of convergence guarantee (Li et al. 2019b
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 1y Kn 7 for some constant Kn such that
21

---

Published in Transactions on Machine Learning Research (01/2025)
rf E (0, 2r. is satisfied. Then even if of has extremely loose upper-bound, let's say dr f2 for small E 1R, 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 DQN-Fed depends on how fast diminishes which depends on how heterogencous the users arc.
B.2 Case 2: E >>> & local GD
The notations used in this subsection are elaborated in Table
g
Table 8: Notations used in the Theorem B.2 for E' > 1 and local GD.
Notation
Description
0 (),
Updated weight for client k after local epochs at the t-th round of FL.
OR,E = 0 (K,E)) that is, the update vector of client & after local epochs.
g
Matrix of update vectors [gI. 0K.c]
Update vector of client l after orthogonalization process.
g
Matrix of orthogonalized update vectors E0.,E...., @K.e].
X
Optinum weights obtained from Equation 12 using g
D.
Optimum direction obtained using 0g: that is, d Ek=1 N E.,
Theorem B.2. Assume that f fff ]e(K]] are 1-Lipschitz continuous and L-Lipschitz smooth. Denote by '/' and the global and local learning rate, respectively. Also, define = Agll, where Xg is the optimum weights obtained from
after E' local epochs. Then,
lim min ||"||| + T t=
(46)
if the following conditions are satisfied: (i) n/ e (0, d.l. (ii) limg to Σt ni and (iii) lime n/' 0,
(iv) lime-so0 1) + 0, and (v) lim 5² - 0.
Proof. As discussed in the proof of Theorem B.1 we can write
3(X s.t. d=
Σ Moox Σ
N.Ox 8X,
(47)
k=1
K
K
3 [(x,Elxe(K) s.t. Dr Σ
Xi Nr. = Σ EO. = BE
(48)
To prove Theorem B.2
first introduce a lemma whose proof is provided in Appendix C
Lemma B.3. Using the notations used in Theorem B.2 and assumming that f = {fatkelK] are L-Lipschitz smooth, we have || - g I nel.
Using Lemma B.3 we have
d = -.A-
A
< _g - - + [ 0E\E
(49)
<
g AA A + 11g88 - X
(50)
| |X - + nel
(51)
ClIKK nel,
(52)
22

---

Published in Transactions on Machine Learning Research (01/2025)
where Equation (4 follows triangular incquality, Equation 50 is obtained from Equations 47 and
48
and Equation 51 uses Lemma
B.3
As seen, if lim 7 + O, and 1o 5² + O, then || døl + O. Now, by writing the quadratic upper bound we obtain:
f(0'+1) sf(0' n/9" x L(7")² 9 11 -
(53)
- - x + ((7"'>> 110 XII
+ + 0z) ((77) d=ll
(54)
f(0') (1- Lry") 1
g 11112 bn 1 + 1(n d=l1²
(55)
Noting that 1/' E (0, 21., and utilizing telescoping yields
min | < f(0o) - f(0 + Ei= 1/ (1]0 - dEl + Laf 0 dzl 12)
(56)
Ei= 17
Using | dell + 0, the Theorem B.2 is concluded.
B.3 Case 3: & local GD
Denote by I the Paroto-stationary solution set of minimization problem arg ming f0). Then, define 0- arggen ||0" 01
Theorem B.4. Assume that f = (Jakeej]) are H-pischitz continuous and a-convex, and that the step-size o satisfies the following two conditions: (i) lim Ej=o thj - and (ii) lim Σj=o 13 <
Then
almost surely 0f + 00; that is,
P lim (0' 10'-09 -y--0)) =0) =1, (+000
(57)
where P(E) denotes the probability of event E.
Proof. The proof is inspired from Mercier et al. 2018 participate all rounds.
Without loss of generality, we assume that all users
Based on the definition of 0" can say
|0 01+1l1 & ||0 2 = ||0 1/ 1
(58)
100 - 0, - 2n' (e' - 07,) -0, + (n')2
(59)
To bound the third term in Equation 59 we note that from Equation 34 we have:
(12
(17
(17
(60)
Σ
K
1
To bound the second term, first note that since orthogonal vectors {ōx (ōkkKEjK] span the same K-ddimensional space as that spanned by gradient voctors {gı)ee[K], then
3(NebeeAA) s.t. d
(61)
1=1
1=1
23

---

Published in Transactions on Machine Learning Research (01/2025)
Using Equation 61 and the o-convexity of {fk [k(K]
obtain
(0' 0. -00' -0'
01)
(62)
K
= (0' - 01)
1a.0
(63)
k=1
K
X (Ja(0') - [x(O,)) + | - 1
(64)
k=1
X₂ M
10 0
||0|
0711
+
(65)
2
X, M
071
(66)
2
Now, we return back to Equation 59 and find the conditional expectation w.r.t. O' as follows
Ellle*t1 0111 0'I = (1 - E|, o 01113 + (7
(67)
K
Assume that E|X,M M +o 2 e, taking another expectation we obtain:
E 1 (1- 0,119+ (17))212
(68)
K
which is a recursive expression. By solving Equation 68 we obtain
j= (1 - (1-7))))mm 1
E| 11+1 S II no E 111
(69)
K 11 nTc)
First term
Second term
It is observed that if the limit of both First term and Second term in Equation E|||0*+1 ++ - 0'+1 + O. For the First term, from the arithmelic--eoneeriic mean inequality we have
69
go to zero, then
E)=o(1 m))) )
( 1- 11- Ei=o "b
lim II n²c) s lim j=0
lim t0
(70)
t0000
lim
c j-- %
(71)
From Equation
71 it is seen that if som Ej=o fl + 0o, then the First term is also converges to zero as
+ 00.
On the other hand, consider the Second term in Equation 669 Second term converges to zero as + co.
Obviously, if lim Ej= nz < co, then the
Hence, if (i) lim Ej 1i + and (ii) lim >x based on standard supermartingale (Mercier et al. 2018
1 < co, then 11100+1-0i+-0 + 0. Consequently, we have
P lim (0' 0*) = 0) = 1. 11000
(72)
C Proof of Lemma
B.3
Proof.
g = 0¹ 0'-0 = (0' -k(x.)))) + (0 0 (u.22)) + ... (0 (.ee-1))' - -O(k,E))
(73)
=0' + 1/0b.1 +... 7-
(74)
24

---

Published in Transactions on Machine Learning Research (01/2025)
Hence,
|
gkl
=1 Σ
0k ll S 7) Σ
| S nel.
(75)
/=1
D Proof of Theorem Theorem 4.6
Throughout the proofs in this section, we frequently use the triangular inequality for two vectors and u: d ull < |v|| + ||u]|.
Our goal is to prove the theorem by deriving recursive relation for the distance between the optimal global model gopt and the global model at the t-th round 0,, specifically |10, - 100 First, noting that
Oct1 = 02 + T/. B, gt, we have
0 10 000t| 0r n, g:
- 0
H g:
gopt
Mi
+ 7
H2 gi
B, M2
81
(76)
To bound M1, we use the results Polyak Tremba (2020). particular, define to max(o,
-2]
xa ri1l
2x2 1001| to then,
( t+ 22
t t to 1 >>> 0
M1 S
20-20
M(1 111-3a1103
Next, we bound M2 in the sequel.
M2 < H
B
ge
+ B g: B, g+
(78)
< H B,
+ [
g:
g:||
(79)
where in 78 we used triangular inequality. Note that using the assumption 2, have 6 H| and by A-strong convexity of the loss function, we have
H, B, 1
H S X Hence,
6 x
H B,
(80)
In addition, the L-smoothness of the global loss function yields
|g S L 0, gopt
(81)
Hence, from
S0 and 81 the first term in
79 could be bounded. Now, bound the second term in
(79
note that
B
< B,
H.
H
(82)
++1 X
(83)
Using
80
and 82
the inequality
78 we obtain
L8
8 + 1 +
M2 <
0, 0o0t
g:
(84)
X
X
25

---

Published in Transactions on Machine Learning Research (01/2025)
Next, have (note that 7/t -
0, 0pp
+ Ao.
1 lo
0
0opt
X
(85a)
Lg
0 - 000
+ A1, > to
2
where
Ao =
(to - -t +
(85b)
L
2 c0
and
A1
(85c)
L(1 - -g2² 10)
Applying 85
recursively yields
(x)
0 0
+ A/;
S to
10, 0Opt 5
(86a)
(1A)
00 8oPt
A t> to
(x)
where
Ab
A0
(86b)
Le -
(X) -
and
A1
A1.
(86c)
Le
X
E Proof of Corollary 4.7
As per Theorem (.6
0.
0
A
then
(44)
(T8) 8
A
0,
0o0e S
+ A 24
(87)
(B8)
Hence, to find Tú, shall have
2A Se
(88)
L8
22g to
2
72 20) Se.
(89)
L8
-1
T.(
diminishing term
(44)' 4-
Since (44 < 1, as t. becomes larger,
(44)² Re 0, and therefore 2
R
--
2 In addition, since y E [0, 4
2A
22,2'- Thus, by inverting the inequality (89). and then laking log
for the large values of 1, L(1 1(1-32t-10) from both sides have
log( ) s -log(
4A 20 log(?)-
log( L 126
(90)
4 Note that log(>) 0, and therefore the second term the RHS of 900 is positive. Also, since logg -2--to log(7), then
7. 135
T. S O log log 2
(91)
26

---

Published in Transactions on Machine Learning Research (01/2025)
F
Proof of Corollary 4.8
Based on Theorem 4.6 if 0o - 0000|| 2
A
then
(
10:
0
-
L6
|100 0
110. ~00
(92)
Lg
1100
000
(93)
Thus, to find Te, shall have
Ld X
100 - 0000| S
(94)
A
2 2
0pr
Te log(
2 log
(95)
T
Hence
T. = 0
log
(96)
log( 7.8
G
Additional datasets
In this section, we assess the performance of DQN-Fed against several benchmarks using additional datasets, namely Fashion MNIST, CINIC-10, and TinylmageNet. The corresponding results for each dataset are detailed in Appendices G.1 to G.3
G.1 Fashion MNIST
Fashion MNIST (Xiao et al. 2017 is an extension of MNIST dataset LeCCun et al. 1998) with images resized to 32 x 32 pixels.
We use a fully-connected neural network with hidden layers, and use the same setting as that used Li al. (2019a) for our experiments. We set E == and use full batchsize, and use 1 = 0.1. Then, we conduct 300 rounds of communications. For the benchmarks, we use the same as those we used for CIFAR-10 experiments. The results are reported in Table g
By observing the three different classes reported in Table g we observe that the fairness level attained in D-d is not limited to a dominate class.
Table 9: Test accuracy on Fashion MNIST. The reported results are averaged over 5 different seeds.
ALGORITIM
SHIRT
PULLOVER
T-SHIRT
FEDAVG
80.42
3.39
64.26
87.00
89.90
Q-FFI
78.53
2.27
71.29
81.46
82.86
FEDMGDA+
79.29
2.53
72.46
79.74
85.66
FEDHEAL
80.22
3.41
63.71
86.87
89.94
DQN-FED
81.27
2.31
72.57
88.21
90.99
G.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 FT.
27

---

Published in Transactions on Machine Learning Research (01/2025)
scenarios since the constituent elements of CINIC-10 are not drawn from the same distribution. Furthermore, we add more non-iidness to the dataset by distributing the data among the clients using Dirichlet allocation with 3 = 0.5.
For the model, we use ResNet-18 18 with group normalization, and set = 0.01. There are 200 communication rounds which all the clients participate with 1. Also, K 50. Results are reported Table 10
Table 10: Test accuracy on CINIC-10. The reported results are averaged over 5 different seeds.
ALGORITHM
0a
WORST 10%
BEST 10%
Q-FFL
86.57
14.91
57.70
100.00
DITTO
15.14
56.91
100.00
FEDLF
86,49
15.12
57.62
100.00
TERM
86.40
15.10
57.30
100.00
DQN-FRD
87.34
14.85
57.88
99.99
G.3 TinylmageNet
Tiny-ImageNet (Le & Yang 2015) is subset of ImageNet with 100k samples of 200 classes. We distribute
the dataset among K 20 clients using Dirichlet allocation with B 0.05
We use ResNet-18 with group normalization, and set 0.02. There are 400 communication rounds in which the clients participate with E = The results are reported in Table
Table 11: Test accuracy on TinylmageNet. The reported results are averaged over 5 different seeds.
ALGORITHM
WORST 10%
BEST 10%
Q-FFL
18.90
3.20
13.12
23.72
FEDLF
16.55
2.38
12.40
20.
TERM
16.41
2.77
11.52
21.02
FEDMGDA+
14.00
2.71
9.88
19.21
DQN-FED
19.05
2.35
13.24
23.58
H
Experiments details, tuning hyper-parameters
For all benchmark methods, conducted grid-search to identify the optimal hyper-parameten for the underlying algorithms. The parameters tested for each method are outlined below:
q-FFL: E (0, 0.001, 0.01, 0.1, 10).
TERM: E 00.1,0.5,1,2,
FedLF: o (0.01,
Ditto: À (0.01,0.05,011,,000 1,2,
FedMGDA+: E (0.01, 0.5,
FedHEAL: (a, B) (.5.5,0.5)), (74:7)) = ((0.5, 0.9)).
Integration with a Label Noise Correction method
1.1 Understanding Label Noise in FL
Label noise in FL refers inaccuracies or errors in the ground truth labels of training data, which can arise due to various factors. These errors may occur during data collection, annotation, transmission, leading
28

---

Published in Transactions on Machine Learning Research (01/2025)
to incorrect noisy labels. In wircless FL settings, label noise can also result from transmission errors over unreliable communication channels, where data packets may be corrupted or lost, causing mislabeling (Hamidi et al. 2022). Addressing label noise is critical, as it can significantly degrade the performance and reliability of FL models, necessitating the development robust techniques to mitigate its impact.
Addressing label noise in FL, presents unique challenges due to its reliance on decentralized data sources, where participants may have limited control over label quality in remote environments. Mitigating label noise in FL requires the development of robust models and FL algorithms capable of adapting to inaccuracies in the labels. This adaptation is essential for maintaining model performance and reliability in real-world FL scenarios where label noise is prevalent.
1.2 Robustness of Fair FL Algorithms to Label Noise
The core objective of fair FL algorithms, such as DQN-Fod, is to uphold fairness among clients while preserving average accuracy across them. However, it's important to note that these algorithms are not inherently robust against. label noise, which refers to instances where data points are mislabeled.
However, by integrating DQN-Fed with label-noise resistant methods from existing literature, we can develop a FL approach that not only ensures fairness among clients but also exhibits robustness against label noise. Specifically, among the label-noise resistant FT, algorithms available in the literature, we choose FedCorr (Xu et al., 2022) to be integrated with DQN-Fed. This integration offers promising avenue for enhancing the performance and resilience of FL models in real-world scenarios affected by label noisc.
filter to identify noisy clients, achieved through the measurement of local intrinsic dimensionality (LID) within local model prediction subspaces. They illustrate the feasibility of distinguishing between clean and noisy datasets by monitoring the behavior of LID scores throughout the training process. For further insights into FedCorr, we defer interested readers to the original paper for a comprehensive discussion.
FedCorr introduces dimensionality-
Following methodology similar to FedCorr, we utilize real-world noisy dataset known as Clothing1M, This dataset comprises 1 million clothing images across 14 classes and is characterized by noisy labels, as it is sourced from various online shopping websites, incorporating numerous mislabeled samples.
For our experiments with Clothing1 we adopt. the identical settings as utilized by FedCorr, which are available in their GitHub repository (https:/ httes//ggituubcom/ /Xu-Jinggg FFerii/FFCCrr...... Specifically, we employ local SGD with a momentum 0.5, utilizing a batch size of 16 and conducting five local epochs. Additionally, we set the hyper-paramete parameter Tj in accordance with their algorithm.
The results summarized in Table 12 It is evident that the average accuracy achieved by DQN-Fed is approximately 2.2% lower compared to that obtained with FedCorr, indicating DQN-Fed's susceptibility to label noise. However, DQN-Fed demonstrates notable improvement in ensuring fair client accuracy, aligning with expectations.
Conversely, when DQN-Fed is combined with FedCorr, there a noticeable enhancement average accuracy while still preserving satisfactory fairness among clients. This integration showcases the potential of leveraging both methodologics to achieve improved performance and fairness in FL scenarios affected by label noisc
Table 12: Test accuracy on Clothing1M M dataset. The reported results are averaged over 5 different seeds.
ALGORITHM
ā
W(10%)
B(10%)
AVD
70.49
13.25
43.09
91.05
FEDCORr
72.55
13.27
43.12
91.15
DQN-FED
70.35
5.17
49.91
90.77
FEDCORR + DQN-FED
72.36
8.07
46.77
91.15
29

---

Published in Transactions on Machine Learning Research (01/2025)
J More on Fairness in FL and ML
J.1 Sources of unfairness in federated learning
Unfairness in FL can arise from various sources and is a concern that needs to be addressed in FT. systems. Here are some of the key reasons for unfairness FL:
1. noo-eeepreeetttivee Data Distribution: Unfairness can occur when the distribution of data across participating devices clients is non-representative of the overall population. Some devices may have more 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 to 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.
3. Heterogeneous Data Sources: Federated learning often involves data from diverse of sources, including different device types, locations, or demographics. Variabilityy in data sources can introduce unfairness 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.
The way data sampled and used for local updates can introduce unfairness. If some clients have imbalanced or non-representative data sampling strategies, it can lead to biased model updates (Hamidi al. 2024b).
5. Data Sampling:
6. Aggregation Bias: The learned model may exhibit bias towards devices with larger amounts of data if devices are weighted equally, it may favor more commonly occurring devices.
J.2 Fairness in conventional ML Vs. FL
The concept of fairness is often used to address social biases performance disparities among different. individuals groups in the machine learning (ML) literature (Barocas et al. 2017). However, in the context of FL, the notion of fairness differs slightly from traditional ML. In FL, fairness primarily pertains to the consistency of performance across various clients. In fact, the difference in the notion of fairness between traditional ML. and FL arises from the distinct contexts and challenges of these two settings:
1. Centralized vs. decentralized data distribution:
In traditional ML, data is typically centralized, and fairness is often defined in terms of mitigating biases disparities within single, homogeneous dataset. Fairness is 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 own unique data distribution, and fairness considerations extend to addressing disparities 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 this context involves adapting to the heterogeneity and diversity among clients while still achieving equitable outcomes.
Traditional ML operates under centralized, unified data schema and is not inherently designed handle data heterogeneity across sources.
30

---

Published in Transactions on Machine Learning Research (01/2025)
We should note that in certain cases where devices be naturally clustered into groups with specific attributes, the definition of fairness in FI. can be seen relaxed version of that in MI, Le., we optimize for similar but not necessarily identical performance across devices (Li et al. 2019a).
Nevertheless, despite the differences mentioned above, to maintain consistency with the terminology used in the FL literature and the papers we have cited in the main body of this work, we will continue use the term "fairness" denote the uniformity of performance across different devices.
J.3 Fair Algorithms in FL
A seminal method in this domain is agnostic federated learning (AFL) (Morri et al. 2019]. AFL optimizes the global model for the worst-case realization of the weighted combination of user distributions. Their approach involves solving saddle-point optimization problem, and they employ fast stochastic optimization algorithm for this purpose. However, AFL exhibits strong performance only for a limited number of clients. In addition, Du el al. 2021) adopted the framework of FedLF and introduced the AgnosticFair algorithm. They linearly parameterized model weights using kernel functions and demonstrated that FedLF can be considered as a specific instance of AgnosticFair. To address the challenges in FedLF, the q-fair Federated Learning (q-FFL) method was introduced by Li et al. (2019a). q-FFL airns to achieve a more uniform test accuracy across users, drawing inspiration from fair resource allocation methods employed in wireless communication networks (Huaizhou al., 2013). Following this, Li al. (2020) introduced TERM, tilted empirical risk minimization algorithm designed to address outliers and class imbalance in statistical estimation procedures. In numerous FL. applications, TERM has shown superior performance compared to q-FFL. Adopl.igg a similar concept, Huang et al. (2020b) introduced a method that adjusts device weights based on training accuracy and frequency to promote fairness. Additionally, FCFC (Cui et al.) (021) minimizes the loss of the worst-performing client, effectively presenting a variant of FedLF. Subsequently, Li et al. (2021) introduced Ditto, a multitask personalized FL. algorithm. By optimizing a global objective function, Ditto enables local devices perform additional steps of SGD, within certain constraints, minimize their individual losses. Ditto proves effective in enhancing testing accuracy among local devices and promoting fairness. Ideas from information theory such conditional mutual information could also be used to promote fairness in FL
Yang et al. 2023 2024
Ye et al. 2024).
Our approach shares similarities with +edMGDA+ (Hu et al. 2022) which treats the FL task as a multi- objective optimization problem. The objective here to simultaneously minimize the loss function of each FL client. To ensure that the performance of any client is not compromised, FedMGDA leverages Pareto-stationary solutions to identify common descent direction for all selected clients. In similar
approach, Hamidi & YANG (2024); Mohajer Hamidi & Damen (024);; Hamidi et al. 2025 use ideas from multi-objective optimization to ensure fairness in FL models.
31


Reviews:
[{"review_id": "PoUQQiIFe8", "reviewer": "Reviewer_7QYN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength:**\nNovel algorithm: this paper proposes combining the MGDA and BFGS methods for federated learning.\nSolid theoretical result: The paper provides the asymptotic convergence result for the algorithm under different settings (local GD, local SGD). And provide the convergence rate when the problem is strongly convex.\nNumerical results are clean and demonstrate that the proposed algorithm achieves better accuracy and fairness.\n\n**Weakness:**\n1. The paper fails to discuss the convergence rate for general cases (Thms. 4.3-4.5).\n2. More discussion on the theoretical result is needed. E.g., in TThms. 4.3 and 4.4., how the requirements on $\\sigma_t$ and $\\zeta^t$ can be guaranteed.\n3. In Figures 1 and 2, the color for the same algorithm in the subplots should be consistent.\n4. In addition to  $\\sigma_2$, the author can provide a histogram of $a_k$ for at least one experiment to illustrate the fairness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on federated learning and proposes a quasi-Newton algorithm to improve its fairness and convergence speed. \nThe paper provides the proposed algorithm's asymptotic convergence result and, under additional assumptions, its convergence rate. The numerical results on FEMNIST, CIFAR-10, CIFAR-100, and Shakespeare datasets show that the proposed algorithm outperforms existing algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weakness above. \n\nMinor points: The author uses $\\|\\cdot\\|_2$ and $\\|\\cdot\\|$ the same time. Please unify the notations.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dMVmUVTEmd", "reviewer": "Reviewer_XbPL", "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. The paper is generally well-organized, with each component of the proposed method clearly explained and supported by well-defined motivations.\n2. The experimental settings are mostly reasonable, as they consider both image and text tasks. Additionally, the proposed method is compared with both first-order and second-order methods, providing a comprehensive evaluation.\n\n**Weaknesses**:\n1. I believe the theoretical convergence analysis in Section 4.4 could be improved in several ways:\n\n* At the beginning of Section 4.4, the authors categorize the proof of the theoretical guarantee based on $e = 1$ and $e > 1$. However, it seems that this $e$ is likely related to $E$, which represents the number of local steps per communication round. Clarifying this relationship would improve the presentation and avoid potential confusion.\n\n* Regarding Theorem 4.6, the authors provide convergence analysis for two settings (as inferred from Corollaries D.3 and D.4), leading to the conclusion that the convergence rate “is either quadratic or linear.” However, I find this conclusion of “either quadratic or linear” somewhat confusing when referring only to the main paper. Providing additional clarification or context in the main paper would help readers better understand this distinction.\n\n* Does the analysis in Theorem 4.6 correspond to local GD with $e=1$?\n\n2. Although the proposed method inherits the computational efficiency of the quasi-Newton method, which eliminates the need to compute the inverse Hessian matrix, it still requires higher computational cost and significantly greater memory overhead on each client compared to most first-order FL methods. Furthermore, as shown in the experimental results in Table 3 and Table 4, the proposed DQN-Fed does not consistently outperform first-order fairness methods such as TERM and Ditto. This raises concerns about the effectiveness of incurring higher computational and memory overhead when the performance gain is sometimes marginal.\n\n3. It appears that the proposed DQN-Fed algorithm considers partial participation cases, as shown in the algorithm. However, the effect of the partial participation ratio does not seem to be significantly demonstrated in the experiments. Moreover, in the experiments, all clients participate in each communication round. I guess that the number of clients participating in the training, whether fewer or more, would have a different impact on fairness. Additionally, the number of local epochs is $e$ in Section 5. \n\n4. A minor point of confusion: the proposed method is called “distributed quasi-Newton federated learning.” Why do the terms “distributed” and “federated” appear together? Do these two words represent different concepts or address different aspects of the algorithm?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the fairness aspect of second-order federated learning (FL) methods by proposing a quasi-Newton method for FL. The proposed approach ensures fairness while leveraging the fast convergence properties of quasi-Newton methods in FL. The authors provide sufficient theoretical analysis for several scenarios in their convergence study. Extensive experiments are conducted on both image classification and text classification tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Regarding the aforementioned W1, I suggest the authors include a discussion to clarify the notation and the specific settings.\n* Regarding W2, I recommend that the authors provide a wall-clock time comparison between the proposed DQN-Fed and other first- and second-order baselines. Additionally, including memory usage comparisons would be helpful.\n* Regarding W3, I suggest the authors conduct ablation studies on the client participation ratio to better understand its impact.\n* Some citation styles in the paper need to be corrected. The authors should clarify the use of \\citep and \\citet, e.g., it should be CIFAR-{10, 100} (Krizhevsky et al., 2009) and FEMNIST (Caldas et al., 2018) mentioned in Section 5.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "56kFgnurMQ", "reviewer": "Reviewer_Y28g", "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.\n* The proposed method considers many aspects, including fairness, convergence, and accuracy.\n* Well written and easy to follow.\n* Both theoretical analysis and empirical results are provided.\n\n\n\nWeaknesses:\n* Wall clock time in each round (iterations in local clients) is unknown.\n* Data distribution among clients is unknown.", "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 paper introduces DQN-Fed, a second-order federated learning framework that combines fast convergence with fairness. DQN-Fed ensures fairness by reducing all local loss functions and leverages quasi-Newton methods to accelerate convergence. The paper proves its convergence with a linear-quadratic rate and demonstrates through experiments that DQN-Fed outperforms state-of-the-art methods in fairness, accuracy, and convergence speed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces DQN-Fed, a second-order federated learning framework combining fast convergence with fairness. It ensures fairness by reducing local loss functions and leverages quasi-Newton methods for faster convergence. Theoretical analysis and extensive experiments on image and text classification tasks demonstrate DQN-Fed's superior performance in fairness, accuracy, and convergence speed.

Weakness: Lacks discussion on the convergence rate for general cases and needs more theoretical result discussions. It has inconsistent color usage in figures and requires unification of notations. Additionally, the proposed method incurs higher computational cost and memory overhead compared to first-order methods, and the effect of partial client participation is not well demonstrated.

As above weakness have been mostly addressed in the discussion pharse. A minor revision is suggested.
Decision: Accept (poster)