Achieving Faster than O(1/t) Convergence in General Convex Federated Learning
Authors: Jie Liu
Zuang Wang
Yongqiang Wang
Venue: Accepted by TMLR ()

Abstract: This paper aims to achieve faster than O(1/t) convergence in federated learning for general
convex loss functions. Under the independent and identical distribution (IID) condition, we
show that accurate convergence to an optimal solution can be achieved in convex federated
learning even when individual clients select stepsizes locally without any coordination. More
importantly, this local stepsize strategy allows exploitation of the local geometry of individual
clients’ loss functions, and is shown to lead to faster convergence than the case where
a same universal stepsize is used for all clients. Then, when the distribution is non-IID,
we employ the sharing of gradients besides the global model parameter to ensure o(1/t)
convergence to an optimal solution in convex federated learning. For both algorithms, we
theoretically prove that stepsizes that are much larger than existing counterparts are allowed,
which leads to much faster convergence in empirical evaluations. It is worth noting
that, beyond providing a general framework for federated learning with drift correction, our
second algorithm’s achievement of o(1/t) convergence to the exact optimal solution under
general convex loss functions has not been previously reported in the federated learning
literature—except in certain restricted convex cases with additional constraints. We believe
that this is significant because even after incorporating momentum, existing first-order
federated learning algorithms can only ensure O(1/t) convergence for general convex loss
functions when no additional assumptions on heterogeneity are imposed.

Published in Transactions on Machine Learning Research (02/2026)
Achieving Faster than O(1/t) Convergence in General Convex Federated Learning
Jie Liu
jie9Bclemson.cm edu
Department of Electrical and Computer Engineering Clemson University, South Carolina, USA
Zuang Wang
suangu@@demsonn.ct edu
Department of Electrical and Computer Engineering Clemson University, South Carolina, USA
Yongqiang Wang"
yonggjuu@clemmonn.co edu
Department of Electrical and Computer Engineering Clemson University, South Carolina, USA
Reviewed on OpenReview: https: openrevie.. net/ forum? id- dd-aaaejVaal VdPod
Abstract
This paper aims to achieve faster than O(1/t) convergence in federated learning for general convex loss functions. Under the independent and identical distribution (IID) condition, we show that accurate convergence to optimal solution be achieved in convex federated learning even when individual clients select stepsizes locally without any coordination. More importantly, this local stepsize strategy allows exploitation of the local geomelry of individ- ual clients' loss functions, and is shown to lead to faster convergence than the case where a same universal stepsize is used for all clients. Then, when the distribution is non-IID, we employ the sharing of gradients besides the global model parameter to ensure o(1/t) convergence to an optimal solution in convex federated learning. For both algorithms, we theoretically prove that stepsizes that are much larger than existing counterparts are al- lowed, which leads to much faster convergence in empirical evaluations. It is worth noting that, beyond providing general framework for federated learning with drift correction, our second algorithm's 's achievement of o(1/t) convergence to the exact optimal solution under general convex loss functions has not been previously reported in the federated learning literature-exetn in certain restricted convex cases with additional constraints. We be- lieve that this significant, because even after incorporating momentum, existing first-order federated learning algorithms can only ensure O(1/t) convergence for general convex loss functions when additional assumptions heterogeneity are imposed.
1 Introduction
Federated learning has received intensive attention since it was proposed by McMahan et al. (2017). Nowa- days, it has found applications in diverse areas including healthcare (Xu et al. 202 la Nguyen et al. 2022
Antunes et al. 2022), smart cities (Pandya et al. 2023 Jiang et al. 2020 Ramu et al. 2022), natural lan-
guage processing [Lu et al.] 2021 Lin et al. 2021 Zhu et al. 2020 the Internet of things (Nguyen et al. 2021 Zhang et al. 2022b Ghimire Rawat, 2022). among others. In federated lcarning, the training data located on individual clients which cooperatively learn common model via periodically sharing their intermediate learning results with central server (McMahan et al. 2017). Compared to centralized learning where all data are aggregated to a data center, federated learning has many advantages, such as
* *Corresponding author

---

Published in Transactions on Machine Learning Research (02/2026)
enhanced security (Ma et al.
2020
Mothukuri et al. 2021 Zhang et al. 2022a), better privacy Yang et al,
2019 A Agarwal et al.
2018
Li et al.
2020), and higher communication efficiency (Sattler et al. 2019 Chen
et al. 2021 Hamer et al.)
2020j.
To date, many aspects of federated learning have been extensively studied,
including stepsize design
(soc, e.g., Kim ct al. (2023): Mukkherjee et al. (2023 Pan et al. (0223) communi-
cation elficiency (see, e.g-: Nori et al. (2021): 1; Tran et al. (2019) : Liu et al. (2022)), oplimization mechanism
(sce, c-g., Luo et al.] (2021): ; Wei et al. (2024) Feng et al. (2021) ) among others.
In federated learning, clients perform multiple local training steps before communicating with central server to reduce the burden of information transmission (McMahan et al 2017]. However, these local training steps move local optimization variables toward the minima of local loss functions and introduce drift from the optimal solution of the global loss function. Therefore, when the data distribution is non-IID among the clients, local training steps result in slow convergence and learning errors, which is called the "client-dri drift phenomenon" (Karimireddy et al.] 2020 Li et al., 2019; Malinovskiy et al., 2020 Charles & Koncěný 2020: Charles & Koncčný] 2021 Pathak Wainwright 2020). In fact, under non-IID data, popular federated learning algorithms, such as FedAvg, can only ensure accurate convergence under diminishing stepsizes, which, however, results in slow convergence MMtrr et al. (2021b). It is worth noting that by imposing additional assumptions on the loss function (e.g., the interpolation and the strong growth condition used in Ma et al. (2018); Meng et al. (2020): Qin et al. (2022b); Kim et al. (2023)) or introducing additional information sharing (e.g., gradient in Mitra et al. (2021a bl), accurate convergence can be ensured under a constant stepsize. However, these results only prove O(1/t) convergence for general convex loss functions.
Inspired by the result in Lee & Wright (2019) which proves that o(L/t) convergence rate can be obtained in first-order centralized gradient methods by employing large stepsizes, we prove that o(1/t) convergence can be achieved in general convex federated learning, in contrast to existing state-of-the-arr algorithms which
either guarantee only O(1/t) convergence (Mitra et al., 2021b Mukherjee et al.) 2023 Qin et al. 2022b;
Khaled et al. 2020), or rely on additional assumptions beyond convexity to establish o(1/t) rates
(Jiang ct al. 2024 Kovalev et al.) 2022
The main contributions of this paper are summarized as follows:
Under the IID condition of data distribution (also called strong growth condition in Schmidt & Roux (003)), we prove that the conventional FedAvg algorithm (called Algorithm [ in this paper after incorporating local stepsizes) can converge under a stepsize that is much larger than existing counterparts (our theoretically obtained stepsize is at least two and four times larger than the ones in Qin et al.] (2022b) and Khaled et al. (2020), respectively). More importantly, we prove that our stepsize can lcad to an o(1/t) convergence to an accurate optimal solution, faster than the commonly believed O(1/t) convergence. To our knowledge, no o(1/l) convergence results have been reported in the literature for general convex federated learning, even after incorporating momentum
(see, e.g., Xu et al. 2021bb; Liu et al. 2020 Cheng et al. (2023) Yang et al. (2022) ).
Under the same condition, prove that FedAvg can converge accurately when individual clients select their (constant) stepsizes in an uncoordinated way. This allows individual clients to exploit their local geometry of loss functions and is proven in our numerical experiments to provide a faster convergence compared with the case where a same universal stepsize is used by all clients. To our knowledge, this is the first time that such results are reported for general convex loss functions.
Under non-IID data, we show that our Algorithm 2 can ensure accurate convergence under constant stepsizes. Compared with existing counterparts, we allow much larger stepsizes (our theoretically obtained stepsize is at least 162/5 and 4 times larger than the ones in Karimireddy et al. (2020) and Mitra et al. (2021b), respectively). More importantly, we prove that under our stpesizes, the algorithm can ensure o(1/t) convergence under general convex loss function, which has not been reported before for first-order federated learning a algorithms,, even after incorporating momentum [Xu et al., 2021bb Liu et al.) 2020 Cheng et al. 2023 Yang et al.) 2022). This stands in stark contrast to existing results on convex federated learning, where o(1/K) convergence has only been established under subclasses of convex functions- as gradient difference being uniformly
bounded (Jiang et al.) 2024), or Hessian difference being uniformly bounded (Kovalev et al. 2022
2

---

Published in Transactions on Machine Learning Research (02/2026)
Algorithm 2 introduces general framework for federated learning with drift correction, unifying and extending a broad class of methods that ensure convergence under non-IID data, including FedLin (Mitra et al., 2021b), FedcT (Mitra et al. 2021a), Scaffnew (Mishchenko et al., 2022), and SCAFFOLD Karimireddy et al., 20200. In addition, we develop a novel analytical framework that establishes a key monotonic descent properly, enabling us to prove an improved o(1 (l1/)) convergence rate under general convex objectives- an achievement that, the best of our knowledge, has previously only been attained for specific subclasses of convex functions in federated learning (see, e.g., Jiang al. (0024); Kovalev et al. (2022)). It is worth noting that extending the monotonic descent property from centralized optimization in Lee & Wright (2019) to federated learning is highly nontrivial, due to the presence of multiple heterogeneous local loss functions arising from non-llD data distributions To the best of our knowledge, this is the first work to rigorously establish such
monotonicity in the context of convex federated learning.
2 Preliminaries
Notations R" and Rax= denote the set of real n-dimensional vectors and the set of n x n-dimensional matrices, respectively. For x R and A RTx", [xl, and [Ali denote the jth element of the vector æ and the (i,j)th element of the matrix A, respectively. For 5, E IR", we define (Jr, v)
[<)l): and ||||| - 10 For a matrix A E R=x", we define ||Al|2 suP || 0, IR" and 1, E R" are n-dimensional vectors with all elements being 0 and 1, respectively. We use O(c(()) and o(c(l)) to dil represent sequences d(t) satisfying lim sup (()) < oo and lim a())
= O, respectively.
2.1 Problem Settings
We consider the following federated learning problem with clients set S = 21,2, ... ,N as follows:
N N f((x).
min ZER
f(z)
(1)
where fs R -> R the local loss function of client í. The local loss function fa(x) is dependent on the local training data of client i. We use the following standard assumptions about the loss functions (see Milra et al. 22021a b): Qin et al. (2022b): Mukheejee al. (2023): Acar et al. (2021))
Assumption 1. For any i S, f((z) Li-smooth over R" i.e. there erists constont L; such that [V)(==) Vf((i) L,llæ yll holds for any i E S and x, y R". This implies
[Vf()) - vf(wil S L| vll
where L= 1/2 EN Li, de., f(x) is also L-smooth over R Assumption 2. For any E S, fi(x) is conver over R", Moreover, the optimal solution set
x = =x" E R²
arg min f(x)
zER"
is not empty, i.e., there exists at least one x² E RD such that vf(=*) = O,, holds.
In existing results for federated learning (see, e.g., Mitra et al. 2021b Qin et al. (202bb): Khaled et al.
p2 Mukherjee et al. (2023) ), the theoretically obtained convergence rates are all on the order of (111)) for general convex loss functions, where is the number of communications between clients and the central
server. In this paper, we will show that we can prove faster o(1/t) convergence rate by using larger
stepsize. To this end, we first introduce the following lemma (see Debnath & Mikusinski (2005 Lee &
Wright (2019)).
Lemma 1. Let (A(I)) be nonnegative sequence satisfying the following conditions:
(1) (A(1) is monotonically decreasing;
3

---

Published in Transactions on Machine Learning Research (02/2026)
(2) (A(t)} is summable, that is, Ex=o Ak) <c.
Then, we have (1) o(1/t), d.e., lo (A(1)
3 Convergence under IID Data
In this section, we consider the case where the data all clients are IID. In the literature, this is usually formulated the following assumption (see, e.g. Schmidt & Roux 2013 Qin et al. (202bb] Kim et al. (203)):
Assumption 3. There exists constant rj 0 such that [V V f())]l holds for any client i E 8 and 2 E R".
2013 and has been widely used in machine learning (Ma et al.) 2018 Vaswani et al. 2019a b Gower et al. 2021 Meng et al, 2020). In fact, Qin et al. (202bb) recently experimentally verified that this condition is satisfied for over- parameterized models. Next, we will prove that the classic federated learning algorithm FedAvg can converge an o(L/t) rate under judiciously designed stepsizes under Assumption 3 In Section we will consider the more general non-IID case.
This assumption is also sometimes called Strong Growth Condition (Shhmidt & Roux
3.1 Algorithm Description
For the sake of completeness, we restate FodAvg McMahan al. (2017) as Algorithm | (with an extension that allow clients use heterogeneous local stepsizes). Specifically, in this algorithm, instead of using universal stepsize a, each client selects its own stepsize a, without coordination with other clients. As proven in the next subscction and the numerical experimental evaluation, this enables our algorithm to obtain faster convergence than existing counterparis.
Algorithm (FedAvg with local stepsizes)
Input: Initial value T(1), local training period т, the stepsize a, for client for f = 1 to T do
for i = 1 to N do
Each client sets (t) = =(1) for & = 0 r - do
Each client i does local training
(t) = aa
(2)
end for end for Each client i transmits (t) to the central server and receives + 1/ EN Fs from the central server.
end for
3.2 Convergence Analysis
Theorem 1. Under Assumptions and 3 if the stepsize of client satisfies a, = > 0 for all i e s
and
87
min
(3)
LLT I(2r + n1(T - 1))2 4n (1) ISi5
where L & EN Li, then f(f(t) converges to f(x") with the comvergence rate o(1/t), ie.,
lim ({((((() - f(x))) 0.
1000

---

Published in Transactions on Machine Learning Research (02/2026)
Proof. See Appendix
In fact, we can allow the stepsize a; of the client i E S in Theorem | to be larger to achieve faster convergence of Algorithm [ which is detailed in Theorem 2
Theorem 2. Under Assumplions
7
and
is the slepsize os for client i E S in Algorilhm 7
salisfies
1
0 < 04 Li"
(4)
we have lim ((((t)) = f(x*) and
T , -())
[[ā(]) - x=12 min miiniignN(2 (2a; 2L,aa yT
Proof- See Appendix D
The proposed stepsize in Theorem 2 is larger than designed stepsizes for FedAvg in existing theoretical results. For example, Qin et al (022b) and Khaled et al. (2020) obtained stepsizes that should satisfy a<as ZI and 0 < a TI, respectively. A simple comparison with (4 shows that our stepsize can be two and four times as large besides the additional flexibility of allowing different clients to select their local stepsizes to exploit local geometry to speed up convergence. In fact, our numerical experiments in Figure confirm that our stepsize strategy indeed leads to much faster convergence than the ones in Qin et al. ) Khaled et al. (2020); Mukherjee et al. (2023) (see Table I for detailed comparison of stepsizes).
Theorem can also be obtained under a weaker interpolation assumption: [V(((")) 0 for all S. E RR", and x² EX", which is also widely investigated in machine learning (see Ma et al. 2018 Vaswani et al. 22019a b): Gower et al. (2021) | Meng et al. (2020)). Compared with Theorem T Theorem 2 does not
require client i to know information about the global loss function to determine its stepsize. In addition, it
allows stepsize that is maxigs5N 41, 1(27+0(T- 1))++)))(4(1)))))) times larger than that in (3) In fact, our
SL.T
numerical experimental results in Appendix 6.1.2 show that allowing clients to use local stepsizes achieves faster convergence than the case with a global stepsize. This is intuitive in that utilizing local Lipschitz constants allows the gradient descent steps to exploit the local geometry of loss functions, and hence, enables faster convergence. It is worth noting that although such a phenomenon has been reported in Mukherjee et al. 2023 for one specific example of quadratic functions, we are the first to theoretically establish that local stepsizes can be exploited to achieve faster convergence for a general class of loss functions in federated learning.
Remark 1. It is worth noting that the o(1/t) convergence rate established in Theorem 1 does not contradict the result in Glasgow et al.) (2022), which proves that FedAug cannot achieve rate faster than O(1/t) for general conver objectives. The key distinction lies in the fact that Theorem 4 relies on the additional Strong Growth Condilion (see Assumption 3. The strong growth condition. is slandard ussumplion of federated learning in the over-parameterized setting ( (Vaswani et al., [2019o; Qin et al.) 2022b al,, i.e., when the model can interpolate the data completely, such that the loss at every data point is minimized simultannously (usually means zero empirical loss). The strong growth condition posils that the squared norm of anyy client's 's local gradient is bounded by a constant multiple of the squared norm of the global gradient, i.e., [:V S ][)[(())] This condition implies that client-level gradients align with the global direction, ensuring that local gradient descent updates do not diverge excessively. That is the reason why we can prove the improved convergence rate o(1 /t). In the nent section, we introduce a new algorithm that achieves o(1 convergence for general conver objectives under non-l1D data, without requiring any additional restrictive conditions.
Remark 2. The stepsize in Theorem 2 is larger than that in Theorem D allowing greater flezibility in prac- lice. However, the convergence rale eslablished in Theorem 1 is o(1/l), which is sharper than the O(1/1) rate in Theorem 2 This reflects a trade-off: the relazed stepsize condition in Theorem 2 leads to a more conservative theoretical guarantee. Nonetheless, using local stepsizes tailored to individual smoothness con- stonts as in Theorem g gields significantly better empirical convergence performance, as demonstrated in
Sections 6.1.1 and 6. 6.1.9
5

---

Published in Transactions on Machine Learning Research (02/2026)
4 Convergence under non-IID Data
4.1 Algorithm Description
Under non-llD data, it has been known that except the trivial case where the number of local iterations is
one (T = 1), Algorithm [ will be subject to errors [Mukherjee et al.) 2023: Orvieto et al. 2022 Wang et al.
2020 Karimireddy et al. 2020). Inspired by traliennttrakkng--eee baased distributed optimization algorithms Pu Nodić [021]] [odic et al. 2017), we propose Algorithm to address this issuc and ensure accurato convergence under non-IID data.
Algorithm 2
Input: Initial values #(1), Vf()(1)), local training period T; and stepsize a; for f = 1 to 7 do for i = to N do
Each client i sets
=1,0(t)= =1)))=((1)) x(t) and 31,0(t) (t(()t)).
(5)
for k = 0 to r 1 do Client i does local updating
F (t) at),a(t),
(6)
( (1) + V[((I1,+110) - V)((a,(()).
(7)
end for end for
The central server calculates and transmits #( = + Li= (t, to each client. Each client i then transmits Vf((ā(t 1)) to the central server and reccives (f( n/2 Em Vf((a(t + 1)) from the central server. end for
Unlike Algorithm which exchanges only the model parameters x1,4+1(() between clients and the server, Algorithm 2 requires exchanging additional variable for the gradient. More specifically, in Algorithm 2 each client uses the global gradient information (z((()) to initialize its local variable (,,(() after each communication round (see (5). This variable (t),+1(t), which serves as an estimate of the global gradient, is then used to update the model parameter f1,++((t) (see This is key to eliminating the drift caused by non-lID data.
Our Algorithm X provides a general framework for federated learning with drift correction, encompassing a wide range of existing algorithms special cases. Specifically, by substituting equation (5) into equation and applying mathematical induction, the auxiliary variable (t) can be expressed
Vi.A (.(. - - (f((((t)) Vf
for = 0,1,..., Substituting this expression into the update rule 6 leads to
(t) = =,, ((((()))(((((e)()))) ()(((()) (()()) Vf(E(1)).
which recovers the specific update mechanisms used in FedLin (Mitra et al. 2021b and FedTrack MMitra et al. 2021a). In addition, as (t) converges to x", it follows from equation 7 that (r.("") [x("')
key idea leveraged in the "drift-correction" federated learning algorithms Scaffnew (Mishchenko et al. 2022
and SCAFFOLD (Karimireddy et al.) 2020). This demonstrates that Algorithm not only generaline lizes but also unifies prior drift-corrected federated learning methods within a broader and more flexible structure.
Next, we prove that the new framework allows obtain o(1/t) convergence in general convex federated learning, which is only established in the literature for special classes of convex functions with restrictions

---

Published in Transactions on Machine Learning Research (02/2026)
data heterogeneity (see, e.g., under the bounded gradient difference condition in Jiang et al. (2024 and under the bounded Hessian difference condition in Kovalev et al. (2022) ). For the general convex case without any restrictions, existing federated learning algorithms even those incorporating momentum only achieve an ((1/t) convergence rate. In addition, the new framework allows using significantly larger step sizes compared existing drilt-corrected lederated learning algorithms, as detailed Section 4.2
4.2 Convergence Analysis
Theorem 3. For Algorithm under Assumplions 7 and 2 if the stepsize a of client E S satisfies
0<as < min ISISN Tig" 5LT T.S
(8)
where L 1. EN Li, then f(((t) converyes fo fa=) with the convergence rate o(1/t), i.e.,
N
lim {{f(E(t)) f(x))}
Proof. See Appendix B
In Theorem we establish an o(1/t) convergence rate for federated learning with general convex functions under non-lID data. A key step in this analysis, shown in Lemma I is proving that the sequence (f(x(t))) is monotonically decrcasing, i.c.,
M( + 1)) < (((()).
We emphasize that proving this monotonicity under general smooth and convex conditions highly non- trivial. Our proof of this property, presented in Lemma constitutes significant technical contribution of this work.
Lemma 2. If the stepsize of Algorithm satisfies 0 < <<a< 5L7-1: there erists constant such that
aa V f(((t))) f(ø(t + 1)).
Moreover, the sequence f(((t) is monotonically decreasing.
The proof of Lemma provided in Appendix F
We provide a bricf proof sketch here. Because F(t+ +1
F(L)= a ΣE ΣL= (a(s,, (see (37)), the proof begins by applying the T-smoothness property to
N
bound (x(t+ The deviation (((aa Vf(((()) then bounded using smoothness, together with
carefully derived inequality I MN iE D (A(,)((()) S (2r ()(({((((()] (see 447) ), yielding the
refined descent inequality
5LT2 LT
[[((()))| < f(((1) - f(ā(t + 1))
aT
2
(see (56) Finally, under the step-size condition 0 < a < 5LT-L this inequality guarantees a strict decrease
2
in f (I((t) establishing its monotonic convergence.
Notably, other federated learning algorithms in Mitra et al. 2021a b), which also follow a gradient-tracking: based framework, only establish an O(L(t) convergence rate under general convex functions in their analyses. In contrast, our work develops more refined analysis technique--peeiffeally the nontrivial proof of the monolonically decreasing property, i.c., f(ā(t 1)) & (((()) (see Lemma 2 -which enables us to establish an o(1/t) convergence rate in Theorem 3 Importantly, this analysis framework is not limited to our algorithm and can also be applied lo other pradient-tracckin-bbsee methods to improve their theoretical guarantees from ((1t)) to o(1/t) under general convex settings. This general methodology, therefore, represents a significant contribution of our work.
Remark 3. It is worth noting that Lee & Wright (019)) proves that centralized first-order gradient descent algorithms can achieve the convergence rate o(1/t), which is better than the existing well-known convergence rate O(//t). The key to this improvement lães in establishing the monotonic descent properly. This paper
7

---

Published in Transactions on Machine Learning Research (02/2026)
eatends the monotonic descent property from centralized optimization in Lee & Wright 2019 to federated learning, which is highly nontrisial due to the presence of mulliple helerogeneous local loss functions arising from non-lID data distributions. To the best of our knowledge, this work provides the first rigorous proof of such monotonicity in convex federated learning and, as a result, achieves the improved o(1/t) convergence
rale.
Remark To illustrate why Algorithm g is well suited for non-IID cases and why its sharing of the addilional gradient variable can overcome the need for Assumplion 3, we define: X(k) [ (xr (k)), V12 (zz(k))), (VM))""")VV(( ([((x(()))", W(k + 1)
ok), " 2N (k))", Vf(((k)) tt, and W(k + 1) IN for k + 1 # st. It can be verified that Algorithm 2 can be expressed equivalently as:
& INvlN for k +
(1++1= (x(()) aY()),
+1) -1)+)))W(K++ 1) + VS(X (I)()+)))))--) -V)((=+)))VV((((0))
To link the notation, the variable X(K)) 1x] (k (KT), xx (KT) )" in the form above corresponds precisely to the variable z(t) in the original description of Algorithm satisfying rı(kT) z(t) for any iSiS.. We next show that ((t) = (t), vī (t), ... (t)) is an estimate of the global gradient. Based on the definition of W(1), laking the network average gives
((++)=+(()) ( -V)+))(((((()))
where Vf(((t)) 1 EN Vf((E(()) and F(t)= = N Ei (t).). Based on the initialization rule 5) i.e., (0) = VS(((0)), we can obtain V(I)= = (()(()). Therefore, the average of Y coincides with the true global gradient at every iteration, and the consensus force of W(t) ensures that all local y:(t) converge this average, and hence that all local (t) converge to the global gradient. Therefore, the local model parameters (i.e., X())) are updated based the global gradient. estimate rather than local gradients. This mechanism ensures that the local model parameters converye to the optimal solution of the global loss function, vather than to the optima of the individual local loss functions resulling from non-IID data, effectively overcoming the need for Assumption
each iteration,
Remark 5. We acknowledge that, compared with the classic federated learning algorithm FedAug, our Al- gorithm 2 requires additional communication. However, we argue that this overhead is a necessary cost for effectively addressing non-ITD data. To the best of our knowledge, all existing federated learning algorithms that guarantee accurate convergence under non-llD data require sharing additional information beyond the gradients used in FedAug, in order to correct the drift induced by data heterogeneity. In fact, Karimireddy et al. 2020) provides counterezample demonstrating that FedAug (Algorithm [ vergence under non-IID data distributions. Compared with FedAug, Algorithm g requires ezchanging an additional variable alongside the gradient. This addilional communication is essential for eliminating the drift caused by non-IID data (heterogeneity in the clients' loss functions). Therefore, this increased commu- nication is a necessary price to pay for ensuring exact convergence of federated learning under non-IlD client data distributions.
cannot ensure eract con-
4.3 Comparison with Existing Results
From Theorem 3 Algorithm 2 allows a much larger stepsize and a better convergence rate compared with existing works. Specifically, the stepsize in Karimireddy et al.] (2020) is required to satisfy 0 < a S minigign( ( In contrast, the stepsize upper bound in Theorem 3 given by minigien ( 5
It can be verified that our permissible stepsize is at least 162 times larger than that in Karimireddy et al. "5
(2020). Similarly, Mitra et al. (2021b) requires the stepsize to satisfy 0 < S minigign 104, J. In contrast, our Theorem permits a stepsize that at least max 2014) 2 4 times larger than that in Mitra et al. (2021b). Table I provides detailed comparison between our proposed stepsize and convergence rate with existing works.
8

---

Published in Transactions on Machine Learning Research (02/2026)
Table 1: Comparison of the proposed stepsizes and obtained convergence rates for Algorithm and Algorithm with existing results. In this table, we represent the total communication round t, the local training period T, and assume that the local loss function fi(x)) satislies L-smooth property.
CONVERGENCE
GRADIENT SETTING'
ASSUMPTION
ALGORITHM
STEPSIZE
RATE
1/L
0(1/t)
EG
ALGORITHM
1/L
0(1/t)
SG
TDD
QIN AL. 2022B
1/(2L)
O(1/t)
SG
KHALED ET AL.
2020
1/(AL)
0(1/t)
SG
2/(TT L)
o(1/6)
EG
ALGORITHM 2
1/(12TL)
0(1/t)
SG
MITRA ET AL,
(021AA]
I/(I8L)
O(1/t)
EG
MITRA ET AL.
2021B
1/(10LL)
O(1/t)
EG
ALLOUAH ET
2024]
1/(16TL)
O(1/L)
SG
KARIMIREDDY ET AL..
(0200)
1/(81TL)
O(1/t)
SG
REISIZADEH
(0200)
NON-IID
ВEIKMOHAMMADI ET AL. 2025
HADDADPOUR & MAHDAVI 2011
QU ET AL. [2021]: Yo ET AL.
2019
0(Ivi))
0(1vV))
SG
CHENG
(2021
Li
2023
YANG ET AL.
20210
Zm1 ET AL.
2021
WANG AL.
(220))
YAn BT
XIANG ET AL.
22024
HUANG ET AL.
(0223)
KIM FT AL.,
(002))
ADAPTIVE
O(1/Vt)
SG
EG denotes the exact gradient setting; SG denotes the stochastic gradient setting.
5
Convergence Analysis under Stochastic Gradients
We extend our analysis to the more practical setting of stochastic gradients (the mini-batch setting). In this case, the local loss function f((x) determined by
= Bf,,
(9)
where & denotes stochastic data sample drawn from the local distribution D; of client i. As result, client can only access a stochastic estimate ff(, &i) of the true gradient Vf((x) for any x E R". We use the following standard assumption regarding the stochastic gradient (Karimireddy et al. (0200 Mukherjee et al. b2 Jhunjhunwalk et al. (2023))
Assumption 4. The stochastic gradient V fa {i) is an unbiased estimate of the accurate gradient V fi(),, with its variance bounded by o². Speciificlll, we have
Ba.DDiifil (f(x,.))) Ex) = Vf( and Eg Bg. [
for any a E RD and E S.
Theorem establishes the convergence of Algorithm 1 in the stochastic and IID case:
Theorem (Stochastic and IID Case). Under Assumptions 1 and if the stepsize os in Algoritim i satisfies a, < +, for any E S, have
B
B [ =0) f(x))
|x(11) x=
2r IN Li=1 a²
minigieN {2a; 2L,a,
min {2a; 1N,
Proof- See Appendix

---

Published in Transactions on Machine Learning Research (02/2026)
Theorem establishes the convergence of Algorithm 2 in this stochastic and non-IID setting:
Theorem 5 (Stochastic and Non-IID Case). Under Assumptions and if the stepsize a of Algorithm
salisfies 0 < & minisigN I, 12rL ). we have
E
-
2(1) f(())
[ - x² x²
34
atT
Proof. See Appendix H
6 Experiments
6.1
Evaluation using generated data
6.1.1
Comparison under IID distribution
We use the following regression problem to compare the performance of Algorithm [and Algorithm the proposed stepsizes with existing counterparte]
under
min f(x) min FER HER
| bill? -
(10)
N
where A, E 50500x 100, b, 5000 and x E R.000 for each client E S (1,22... 20). [Ailak are generated
from [0, 1] randomly for j E 21,2. 500), k E (1,2. 1000, and E S, and we also set [Ai]í, = [Al]
for E (1,2, 500) to obtain convex but not strongly convex loss function (xx). We b, A,30 for
all i E S with 2o 10x x 1n rather than generating b, randomly. In this setting, f((x) 11lA z0)1 and
AA la hence, there exists a constant 7 maxisisn( IKC Σ., (.) Σ AJ]I2
such that [[v]( S f())]
holds for all E S.
We compare Algorithm and Algorithm 2 under the proposed stepsize strategy with existing counterparts including Qin et al. (2022b); Mukherjee et al. (2023); Mitra et al. (2021b); Khaled et al. (2020). In the evaluation, we use the error
e(t) = -( f(x")
-
to measure the learning accuracy. Moreover, implement all algorithms using accurate gradients to ensure fair comparison of them. The corresponding convergence performances with different local training periods r == 2,3,4,5, 5, are presented in Figure !
In Figure the legends' 'A 'Algorithm| 1 with Universal Stepsizes' and 'Algorithm 1 with Local Stepsizes' denote Algorithum with stepsizes (3) and (4), respectively. Specifically, in the universal stepsize case, we set the universal stepsize for all clients as minigisN ( L.7 D2
according to (3 where
L = I L, the global Lipschitz constant. In the local stepsize case, we set the stepsize client as 0; based on individual Lipschitz constants L, From Figure [] we know that the convergence of Algorithm D with the stepsize prescribed in 44) is much faster than other cases, including the case with the universal stepsize
3
Additional experiments with non-IID data are presented in Appendix A.1 A.1
6.1.2 Local Stepsize Strategy Outperforms Universal Stepsize Strategy for Algorithm under = 1
We show that better convergence performance Algorithm can be achieved with local stepsizes << az < 1. than universal stepsize 0 t. where L = /
For case of comparison, we continue to consider the regression problem [0) described in Section 6. specifying
[Ai]ja BB and b, A
Code available http://aanammmooossopnnnccceeeer F-814/RFADME... md
2Code available hit http:///ooooooyooossaaaaasssasa C.PI1/README..
10

---

Published in Transactions on Machine Learning Research (02/2026)
Mukherjee (2023)
Mitra et al. (2021b)
Errors elt)
Errors e(0)
Algorithm
Algoritim with Universal Stepsizes
Khaled al. (2020)
Gin et al. (2022)
Algorithm Local Stepsizes
17
Communication Rounds [ -
Communication Rounds (TT
Errus
10"
403 12 Communication Rounds (r=55)
14
77
302
24g
20
Communication Rounds
Communication Rounds (x
Figure 1: Comparisons of the performance of Algorithm and Algorithm 2 under the proposed stepsize with
Qin et al. 2022b); Mukherjee et al. (2023); Mitra et al. 2202 Khaled et al. (2020) under different local training periods T.
for j E 21, ,00), h E (1,2, ,100,, and i E S, where [Biljk is generated from [0, 1] randomly, p measures the heterogeneity in loss functions, and zo = 10 x 1n. It can be seen that larger parameter p leads to more heterogeneity in the local loss functions. Moreover, one can verify that the loss function fx of client i E satisfies Ly-smooth property with L, = if || B2 Then, under т 1, we present Figure the convergence of Algorithm under the local stepsize strategy where a; = 1 of client S and the I. universal stepsize strategy where = 1/2 for all clients, where Lg is the individual Lipschitz constant of client E S and L - + ΣM" L, is the global Lipschitz constant.
In Figure 2 to compare the convergence between the local and the universal stepsize strategies, we plot the learning errors (t)( f(=") and f(Fg(t) f(x*) under different heterogencity parameters p E (1,1.5 2, 3), where (t) and (t) are generated under the local and the universal stepsize strategies, respectively. From Figure 2 it is clear that the local stepsize designed based on local Lipschitz constants obtains faster convergence than the case with the universal stepsize designed based on the global Lipschitz constant, Moreover, to quantify the improvement in convergence speed, in Figure 2 we also plot the learning error ratio
r(1) = f(n((() - f(x*) [(E,(0) - (x*
under different heterogeneity parameters E (1, 1.5, 2, 2.5, respectively. A smaller r(t) (r(t) < 1) means more advantage of the convergence speed of the local stepsize strategy over the universal stepsize strategy. Figure 2 shows that smaller r(I) is obtained under a larger heterogeneity parameter p. Thus, it can be concluded that the local stepsize strategy of Algorithm | can achieve faster convergence than the global stepsize strategy, especially for large heterogeneity casos.
6.2 Evaluation using CIFAR-10 and CIFAR-100 under non-IID distribution
We also evaluate our algorithms by training CNN on 10 clients using the benchmark datascts CIFAR-10 and CIFAR-100, respectively The CNN architecture consists of three convolutional layers with 32, 64, and 128 filters, respectively, each followed by max-pooling layer. After the final convolutional and pooling layers, the network includes a fully connected layer with 256 units and ReLU activation, a dropout layer with a rate of 0.25 for regularization, and a final dense output layer with 10 units that produces the class
&Code available at httpe///mmooonnoooo..aeeeoeeeeee Btt.:///____PPPAAAAAAPPA
11

---

Published in Transactions on Machine Learning Research (02/2026)
18
Stepsize
Global Stepsize
Global Stepsize
Local Stepsize
Local Stepsize
Local Stepsize
Erro
Emror
Emnors
16"
101
120
Xi
100
10g
11a Communication Rounds (o=
340
us
Communication Rounds [p=
Communication Rounds Cip
Global Stepsize Local Stepsice
12-
Global Stepsize
Local Stepsice
p 1.5
2
127
Ratios iCC)
p 2.5
18"
Communication Rounds 2.5)
Communication Rounds (p
Communisc Rounds Retio Comperisons
Figure 2: Comparisons of Algorithm Twith the local stepsize strategy and universal stepsize strategy under different heterogeneity parameters p.
logits. In our experiments, we compare the proposed algorithm against existing federated learning met hods specifically designed to address client drift, including SCAFFOLD (Karimiredyy et al. 2020), FedLin Miirra ctt al., 2021b), and Scaffnew (Mishchenko et al., 2022). Following Hsu et al. (2019) and Kim et al. (2023) we generate heterogeneous data distributions across the 10 agents using Dirichlet. distribution, with the heterogeneity parameter set to 0.1, and 10, respectively. A higher value of , yields a nearly uniform
distribution of data across classes for each client, resulting in approximately IID local datasets. In contrast, lower 8 leads to highly skewed distributions, where clients tend to specialize in only few classes.
Figures 3 and Figures 5 and and Figures 7 and g present results for / set to 1, 0.1 and 10, respectively, corresponding to moderate, high, and low heterogeneity in the data distributions. For all results shown in
Figures 3 5 (CIFAR-10) and Figures | 6 S (UFAR--10), the stepsizes for Algorithm 2 SCAFFOLD,
FedLin, and Scaffnew are selected according to the guidelines from Theorem 3 Karimireddy et al. 2020))
Mitra et al. (0211b), and Mishchenko et al. (2022), respectively, using an estimated smoothness paramcter
of L = 2. For Algorithm 2 SCAFFOLD, and FedLin, the local training period is set to T = 10. For Scaffnew, the communicatinn probability is set to TI to ensure that the total number of communicated messages remains consistent across methods. A summary of the experimental sctup is given in Table 2 As shown in the figures, our algorithm achieves faster convergence and higher accuracy on both the CIFAR-10 dataset and the CIFAR-100 dataset. Note that the large variance of Scaffnew arises from the additional randomness introduced by its communication mechanism.
1
Table 2: Experimental Setup in Figures
FIGURE
FICURE
FIGURE
5
FIGURE 6
FIGURE
FIGURE
DATASET HETEROGENETTY
CIFAR-10
CIFAR- 100
CIFAR-10
CIFAR- 100
CIFAR- 10
CIFAR 100
3 =
B = 1
8 = 0.1
8 0.1
8 = 10
3 3= 10
LOCAL TRAINING PERIOD
10
T 10
T 10
7= 10
10
T 10
NUMBER OF AGENTS OPTIMIZER
10
10
10
10
10
10
SEE LABBL
SEE LABEL
SEE LABEL
SEE LABEL.
SEE LABEL
SEE LABEL
1 For Scaffnew, the communication probability is set to to ensure that the total number communicated messages remains consistent across methods.
2 The stepsizes for Algorithu
2 SCAFFOLD, FedLin, and Scaffnew are selected according to the guidelines from Theorem Karimireddy et al. 2020). Mitra et all 2021bb and Mishchenko of al. (2022), respectively, using an estimated smoothness
parameter of 1.
12

---

Published in Transactions on Machine Learning Research (02/2020)
240
Test Accuracy
Train Accur BCy
08
66
132
64
Scalfnew
Scaffnew
ScafTnww
Algonithm2
Algerihm22
Algorithm2
SCAFFOLD
SCAFFOLD
SCAFFOLD
FedLin
FedLnn
FedLin
025
2006 Communication Rounds
26
3530
Communicalion Rounds
Communication Rounds
(b)
(c)
Figure Comparison of Algorithm 2 with statc-of-the-art federated learning algorithms SCAFFOLD, FedLin, and Scaffnew on the CIFAR-10 dataset. The Dirichlet distribution parameter was set to 1. Each curve represents the average of five independent runs. The test accuracy in Figure 3 (b) is Lop-5 accuracy.
4.5
Scaffnew
Scaffnew
Algorithm2 SCAFFOLD
Aigorithm2
SCAFFOLD
FeaLin
Train Accuracy
FedLin
044
2.8
Alganithm2
FedLin
use
1093
1892 13:2 J0E3 Communication Rounds
12.0
2000 25:0
2503
Com unication
Communication
(a)
(b)
(c)
Figure 4: FedLin, and Scaffnew on the CIFAR-100 dataset. the Dirichlet distribution parameter was set to 3 = 1. Each curve represents the average five independent runs. The test accuracy in Figure [(b) is top-5 accuracy.
Comparison of Algorithm 2 with state-of-the-art federated learning algorithms SCAFFOLD,
175
Train Acc
Test Accurso
Scaffnew
Scaffnew
ScafTnew
Algorithm2
Algorithm2
SCAFFOLD
SCAFFOLD
SCAFFOLD
203
1009
3500
2008
2000
300
2009
1249
2009
20
3956
200
3800
3000
2000
2000
Communication Rounds
Communicattin Rounds
Communication Rounds
(b)
(c)
Figure 5: FedLin, and Scaffnew on the CIFAR-10 dataset. The Dirichlet distribution parameter was set to $ = 0.1. Each curve represents the average of five independent runs. The test accuracy in Figure ((b) is top-5 accuracy.
Comparison of Algorithm 2 with state-of-the-arl federated learning algorithms SCAFFOLD,
13

---

Published in Transactions on Machine Learning Research (02/2026)
Sraftnew
08
Scaftnow
Algorithm2
Algorithm2
SCAFFOLD
SCAFFOLD
35
Test Accuracy
FedLin
Train Accuracy
FedLin
0
Scaffnew
Algorithm2
SCAFFOLD
15
FedLin
20
26
Communication Rounds
Communicalion Rounds
Communication Rounds
(b)
(c)
Figure Comparison of Algorithm 2 with state-of-the-art federated learning algorithms SCAFFOLD,
FedLin, and Scaffnew- the CIFAR- 100 dataset. The Dirichlet distribution parameter set to 8 0.1.
Each curve represents the average of five independent runs. The test accuracy in Figure B (bb is top-5 accuracy.
ScafTnew
Algorithm2 SCAFFOLD
FodLin
Train Accuracy
Lo55
2.
Test
Scaffnew Algorihhm2 SCAFFOLD
Scartnew
Algorithm?
SCAFFOLD
1093
mis
Com Communication Rounds
Communication Rounds
Communication Rounds
(b)
(c)
Figure 7:
Comparison of Algorithm 2 with stato-of-tho-art federated learning algorithms SCAFFOLD.
FedLin, and Scalfnew on the CIFAR-10 dataset. the Dirichlet distribution parameter sel to 8 10. Each curve represents the average of five independent runs. The test accuracy in Figure 7 b) is top-5 accuracy.
Scaftnew
Scaftnew
Algorithm2
Algorithm?
SCAFFOLD
SCAFFOLD
Test Accuracy
FedLin
Train Accuracy
FedLin
25
Scaffnew
Algorithm2
SCAFFOLD
FedLin
500
1006
2008
1866
3500
2000
300
2009 Communication Rounds
2009
1249
220
3358
208
3300
3000
2000
2500
Communication Rounds
Communication Rounds
(b)
(c)
Figure 8: FedLin, and Scaffnew on the CIFAR-100 dataset. The Dirichlet distribution parameter was set to 8 = 10. Each curve represents the average of five independent runs. The test accuracy in Figure ((b) is top-5 accuracy.
Comparison of Algorithm 2 with state-of-the-art federated learning algorithms SCAFFOLD,
14

---

Published in Transactions on Machine Learning Research (02/2026)
7 Conclusion
Enhancing convergence accuracy and speed is key for federated learning. We prove that much larger stepsizes can be used in FedAvg, and hence, much faster convergence can be achieved. In fact, we theoretically show that the proposed stepsize strategy can guarantee (1) convergence to an exact optimal solution for general convex loss functions, under both IID data distribution and non-lID data distribution among local clients. This is significant since existing federated learning results can only theoretically establish O(1/t) convergence under general convex loss functions when no additional restrictions are made, even after incorporating momentum. Moreover, in the ITD data distribution setting, we theoretically establish convergence when clients set stepsizes individually using local Lipschitz parameters, and show that such a local stepsize strategy enables exploiting local geometry to expedite convergence. To our knowledge, this is the first time that local stepsizes designed using local Lipschitz parameters is systemtically shown to outperform universal stepsize designed using the global Lipschitz parameter. Morcover, we propose a general gradient-tracking based framework that unifies and exlends many existing drift-corrected federated learning algorithms. By establishing key monotonic descent property, our framework broadens the theoretical understanding of gradient tracking and enables improved o1//t) convergence rate under non-IID data distributions. This represents a significant advancement, existing results establish o(1/t) convergence for convex federated learning only under additional restrictions on heterogeneity.
Acknowledgments
The work was supported in part by the National Science Foundation under Grants CCF-2106293, CCF- 2215088, CNS-2219487, CCF-2334449, and CNS-2422312.
References
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Foderatod learning based on dynamic regularization. arXiv preprint arXiv:2111.044 2021.
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. epSGD: Commmication--fficeen and differentially-private distributed SGD. In Advances in Neural Infor- mation Processing Systems, volume 31, pp. 7564 7575, 2018.
Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, Geovaní Rizk, and Sasha Voitovych. Byzantine-robust federated learning: Impact of client subsampling and local updates.
arXiv preprint (x4f::2402.1788)) 2024.
Rodolfo Stoffel Antunes, Cristiano André da Costa, Arne Küderle, Imrana Abdullahi Yari, and Björn Es- kofier. Federated learning for healthcare: Systematic review and architecture proposal. ACM Transactions on Intelligent Systems and Technology, 13(4):1-23, 2022.
Ali Beikmohammadi, Sarit Khirirat, and Sindri Magnússon. On the convergence of foderated learning algorithms without data similarity. IEEE Transactions on Big Dato, 11(2))659-66 668, 2025.
Zachary Charles and Jakub Konečný. On the outsized importance of learning rates in local update methods. arXiv preprint ar Xix:20007 00878, 2020.
Zachary Charles and Jakub Konečný. Convergence and accuracy trade-offs in federated learning and meta- learning. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pp. 2575 2583. PMLR, 2021.
Mingzhe Chen, Nir Shlezinger, H. Vincent Poor, Yonina C. Eldar, and Shuguang Cui. Commmicationn efficient federated learning. Proceedings of the National Academy of Sciences, 118(17):1 8, 2021.
Ziheng Cheng, Xinmeng Huang, Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. aixio preprint arXi::2306.1653
2023.
15

---

Published in Transactions on Machine Learning Research (02/2026)
Ziheng Cheng, Xinmeng Huang, Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. In The Twelfth International Conference on Learning Represenlations, 2024.
Lokenath Debnath and Piotr Mikusinski. Introduction Hilbert spaces with applications. Academic press, 2005.
Chenyuan Feng, Zhongyuan Zhao, Yidong Wang, Tony Q. S. Quek, and Mugen Peng. On the design of federated learning the mobile edge computing systems. IEEE Transactions on Communications, 69(9): 5902 5916, 2021.
Bimal Ghimire and Danda B. Rawat. Recent advances on federated learning for cybersccurity and cyber- security for federated learning for internet of things. IEEE Internet of Things Journal, 9(1)):8229 8249, 2022.
Margalit R Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local SGD) and continuous perspective. In International Conference on Artificial Intelligence and Statistics, pp. 9050- 9090, 2022.
Robert Gower, Othmane Sebbouh, and Nicolas Loizou. SGD for structured nonconvex functions: Learning rates, minibatching and interpolation. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pp. 1315 1323, 2021.
Farzin Haddadpour and Mchrdad Mahdavi. On the convergence of local descent methods in federated learning. Xi preprint arxiv:1911 19:0. 14425, 2019.
Jenny Hamer, Mehryar Mohri, and Ananda Theertha Suresh. FedBoost: A commuication.-fffieent algo- rithm for federated learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 3973 3983. PMLR, 2020.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint 1rXXic:109.006 2019.
Minhui Huang, Dewei Zhang, and Kaiyi Ji. Achieving linear speedup in non-IID federated bilevel learning. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pp. 14039 14059, 2023.
Divyansh Jhunjhunwala, Shiqiang Wang, and Gauri Joshi. Fedexp: Speeding up federated averaging via extrapolation. arXiv preprint orXiv:2301.0960, 2023.
Ji Chu Jiang, Burak Kantarci, Sema Oktug, and Tolga Soyata. Federated learning in smart city sensing: Challenges and opportumities. Sensors, 6230 2020.
Xiaowen Jiang, Anton Rodomanov, and Sebastian U Stich. Stabilized proximal-point methods for federated optimization. Advances in Newral Information Processing Systems, 37:99735 99772, 2024.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and
Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning, In Pro- ceedings of the 37th International Conference on Machine Learning, volume 119, pp. 5132-5143. PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pp. 4519-4529. PMLR, 2020.
Junhyung Lyle Kim, Mohammad Taha Toghani, César Uribe, and Anastasios Kyrillidis. Adaptive feder- ated learning with auto-tuned clietts. arXiv preprint ar arXin:2306.1120 112001, 2023.
Dmitry Kovalev, Alcksandr Beznosikov, Ekaterina. Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal gradient sliding and its application to optimal distributed optimization under similarity. Advances in Neural Information Processing Systems, 35:33494-3338 044494473377, 2022.
16

---

Published in Transactions on Machine Learning Research (02/2026)
Ching-Pei Lee and Stephen Wright. First-order algorithms converge faster than o(/kk on convex problems. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 3764-3762. PMLR, 2019.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang, On the convergence of fedavg on non-fid data, arViv preprint arXiv:1907.02189, 2019.
Xiaoyun Li and Ping Li. Analysis of error leedback in federated non-convex optimization with biased com- pression: Fast convergence and partial participation. In International Conference on Machine Learning, pp. 19638-19688, 2023.
Zengpeng Li, Vishal Sharma, and Saraju P. Mohanty. Preserving data privacy via federated learning: Challenges and solutions. IEEE Consumer Electronics Magazine, (18):8-16, 2020.
Bill Yuchen Lin, Chaoyang He, Zihang Zeng, Hulin Wang, Yufen Huang, Christophe Dupuy, Rahul Gupta, Mahdi Soltanolkotabi, Xiang Ren, and Salman Avestimehr. Fedulp: Benchmarking federated learning methods for natural language processing tasks. arXiv preprint ar 0rX80:2104.08815 2021.
Ming Liu, Stella Ho, Menggi Wang, Longxiang Gao, Yuan Jin, and He Zhang. Federated learning meets natural language processing: A survey. arXiv preprint arXic:2107.1200 2021.
Shengli Liu, Guanding Yu, Rui Yin, Jiantao Yuan, Lei Shen, and Chonghe Liu. Joint model pruning and de- vice selection for communication-effeiee federated edge learning. TEEE Transactions on Communications, 70(1):231 244, 2022.
Wei Liu, Li Chen, Yunfci Chen, and Wenyi Zhang. Accelcrating federated learning via momentum gradient descent. IEEE Transaclions Purallel and Distribuled Systems, 31(5):1754-1000 2020.
Bing Luo, Xiang Li, Shiqiang Wang, Jianwei Huang, and Leandros Tassiulas. Cost-elfective federated learning design. In IEEE INFOCOM 2021 IEEE Conference on Computer Communications, pp. 1-10, 2021.
Chuan Ma, Jun Li, Ming Ding, Howard H. Yang. Feng Shu, Tony Q. S. Quck, and H. Vincent Poor. On saleguarding privacy and security in the framework of federated learning. IEEE Network, 34(4):242 248, 2020.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern over- weerparametrized learning. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 3325-3334. PMLR, 2018
Grigory Malinovskiy, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik. From local SGD to local fixed-point methods for federated learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 0692-6701. PMIRR 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-Eiiee Efficient Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pp. 1273-1282. PMLR, 2017.
Si Yi Meng, Sharan Vaswani, Issam Hadj Laradji, Mark Schmidt, and Simon Lacoste-Julien. Fast and furious convergence: Stochastic second order methods under interpolation. In Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108, pp. 1375-13866 PMLR, 2020.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Prosskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Conference on Machine Learning, pp. 15750 15769. PMLR, 2022.
Aritra Mitra, Rayana Jaafar, George Pappas, and Hamed Hassani. Federated learning with incrementally aggregated gradients. In 2021 60th IEF. Conference Decision and Control (CDC), pp- 775 77577, 2021a.
17

---

Published in Transactions on Machine Learning Research (02/2026)
Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Newral Information Processing Systems, 34:14606 14619, 2021b.
Viraaji Mothukuri, Reza M. Parizi, Seyedamin Pouriyeh, Yan Huang, Ali Dehghantanha, and Gautam Srivastava. survey on security and privacy of federated learning. Fulure Generation Computer Systems, 115:619-644 640, 2021.
Sohom Mukherjee, Nicolas Loizou, and Sebastian U Stich. Locally adaptive federated learning. arXiv preprint arXiv:2307.06306, 2023.
Angelia Nedić, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-286) 2633, 2017.
Dinh C. Nguyen, Ming Ding, Pubudu N. Pathirana, Aruna Seneviratne, Jun Li, and H. Vincent Poor, Federated learning for internet of things: comprehensive survey. IEEE Communications Surveys & Tutorials, 23(3) 23333:203122 2021.
Dinh C. Nguyen, Quoc- Viet Pham, Pubudu N. Pathirana, Ming Ding, Aruna Seneviratne, Zihuai Lin, Octavia Dobre, and Won-Joo Hwang. Federated learning for smart healthcare: A survey. ACM Compuling Surveys, 55 55(3):1-37, 2022.
Milad Khademi Nori, Sangseok Yun, and TI-Min Kim. Fast federated learning by balancing communication trade-offs. IEEE Transactions on Communications, 69(8):5168 5182, 2021.
Antonio Orvicto, Simon Lacoste-Julien, and Nicolas Loizou. Dynamics of sgd with stochastic polyak stepsizes: Truly adaptive variants and convergence to exact solution. In Advances in Newral Information Processing Systems, volume 35, pp. 26943-294220 26954,, 2022.
Zibin Pan, Shuyi Wang, Chi Li, Hajjin Wang, Xiaoying Tang, and Junhua Zhao. Fedmdfg: Federated learning with multi-gradient descent and fair guidance. Proceedings of the AAAI Conference on Artificial Intelligence, 37(8))9364 9371, 2023.
Sharnil Pandya, Gautam Srivastava, Rutvij Jhaveri, M. Rajasekhara Babu, Sweta Bhattacharya, Praveen Kumar Reddy Maddikunta, Spyridon Mastorakis, Md. Jalil Piran, and Thippa Reddy Gadekallu. Feder- ated lcarning for smart cities: A comprehensive survey. Sustainable Energy Technologies and Assessments, 55: 55:102987, 2023.
Reese Pathak and Martin J Wainwright. Fedsplit: an algorithmic framework for fast federated optimization. In Advances in Neural Information Processing Systems, volume 33, pp. 7057-7066) 2020.
Shi Pu and Angelia Nedié. Distributed stochastic gradient tracking methods. Mathematical Programming, 187(1):409 457, 2021.
Tiancheng Qin, S. Rasoul Etesami, and Cesar A. Uribe, Decentralized federated learning for over- parameterized models. In 2022 TEFE 61st Conference on Decision and Control (CDC), pp. 5205, 2022a.
Tiancheng Qin, S Rasoul Etesami, and César A Uribe. Faster convergence of local sgd for parapaaamteeieeedd models. arXiv preprint arXiv:2201.122 12719 2022b.
Zhaonan Qu, Kaixiang Lin, Zhaojian Li, and Jiayu Zhou. Federated learning's ' blessing: Fedavg has linear speedup. In International Conference on Learning Representations, pp. 1-47, 2021.
Swarna Priya Ramu, Parimala Boopalan, Quoc- Pham, Praveen Kumar Reddy Maddikunta, Thien Huynh-The, Mamoun Alazab, Thanh Thi Nguyen, and Thippa Reddy Gadckallu. Federated lcarning enabled digital twins for smart cities: Concepts, recent advances, and future directions. Sustainable Cities and Society, 79:103663, 2022.
18

---

Published in Transactions on Machine Learning Research (02/2026)
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. ar preprint or orXim:2003.002: 00295, 2020.
Amirhosscin Reisizadch, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaic, and Ramtin Pedarsani. Fedpaq: A communical ion-efficient federated learning method with periodic averaging and quantization. In Pro- ceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pp. 2021-2031 PMLR, 2020.
Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek. Robust and communication- efficient federated learning from non-iid data, IEEE Network, (1(9):3400 3413, 2019.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under strong growth condition. Xix preprint ArX80:1308. 6370, 2013.
Nguyen H. Tran, Wei Bao, Albert Zomaya, Minh N. H. Nguyen, and Choong Seon Hong. Federated learning over wireless networks: Optimization model design and analysis. In IEFE INFOCOM 2019 IEEE Conference Computer Communications, pp. 1387 1395, 2019.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over- parameterized models and an accelerated perceptron. In Proceedings of the Twenly-Secome International Conference on Artificial Intelligence and Statistics, volume 89, pp. 1195-1 1204. PMLR, 16 18 Apr 2019a.
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. In Advances in Newral 2019b.
Information Processing Systems, volume 32, pp.
Jianyu Wang, Qinghua Liu, Hao Liang Gauri Joshi, and H. Vincent Poor. Tackling the objective incon- sistency problem in heterogeneous federated optimization. Advances in Neural Information Processing Systems, volume 33, pp. 7611-7623, 2020.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Yo-Seb Jeon, and H. Vincent Poor. Covert model poisoning against federated learning: Algorithm design and optimization. IEEE Transactions on Dependable and Secure Computing, (1(3):119-1200)) 2024.
Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong and Lili Su. Efficient federated learning against heterogeneous and non-stationary client unavailability. Advances in Newral Information Processing Systems, 37:104281-104328 2024.
Jie Xu, Benjamin S. Glicksberg, Chang Su, Peter Walker, Jiang Bian, and Fei Wang. Federated learning for healthcare informatics. Journal of Healtheare Informatics Research, 5:1-19, 2021a.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. arXiv preprint arXiv:2106.110 10874, 2021b.
Wenjing Yan, Kai Zhang, Xiaolu Wang, and Xuanyu Cao. Problen-paramneee--rree federated learning. In The Thirteenth International Conference on Learning Representations, 2025.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving lincar speedup with partial worker participation in non-iid federated learning. arx preprint urXiv:2101.11203, 2021.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology, 10(2):1-19, 2019.
Zhengjic Yang, Wei Bao, Dong Yuan, Nguyen H. Tran, and Albert Y. Zomaya. Federated learning with nesterov accelerated gradient. IEFE Transactions on Parallel and Distributed Systems, 33(12))4863-44 48733 2022.
19

---

Published in Transactions on Machine Learning Research (02/2026)
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAT conference artificial intelligence, volume 33, pp. 5693 5700, 2019.
Xiaotong Yuan and Ping Li. On convergence of fedprox: Local dissimilarity invariant bounds, smoothness and beyond. Advances in Neural Information Processing Systems, 35:10752-10765, 2022.
Kaiyue Zhang, Xuan Song, Chenhan Zhang, and Shui Yu. Challenges and futuure directions of secure federated learning: a survey. Frontiers of Computer Science, 16(3):163817 2022a.
Tuo Zhang, Lei Gao, Chaoyang Hc, Mi Zhang, Bhaskar Krishnamachari, and A. Salman Avestimchr. Fed- erated learning for the internet of things: Applications, challenges, and opportunities. IEEE Internet of Things Magazine, 5(1):24-22) 29, 2022b.
Xingyu Zhou. On the fenchel duality between strong convexity and lipschitz continuous gradient. arXiv preprint Xrv: 06578, 2018.
Ligeng Zhu, Hongzhou Lin, Yao Lu, Yujun Lin, and Song Han. Delayed gradient averaging: Tolerate the communication lateney for federated learning. In Advances in Neural Information Processing Systems, volume 34, pp. 29995-30007, 2021.
Xinghua Zhu, Jianzong Wang, Zhenhou Hong, and Jing Xiao. Empirical studies of institutional federated learning for natural language processing. Findings of the Association for Computational Linguisties: EMNLP 2020, pp. 625 634, 2020.
A Additional Experiments
A.1 Comparison of Algorithm with Existing Works in Least Squares Regression
We consider [A,]sk and [bily generated from 10 randomly for S 500, 1 s k 100, and E S. After the initial random generation of data, purposely set [A1],,1 [A1],, for 1 S < 500 to make A₃ not full
rank. By doing so, we can obtain a local loss function (1 2 | by 2| that is convex but not strongly convex.
We compared the performance of Algorithm 2 under the proposed stepsize {8] in Theorem with those in Mitra et al. 2021a b). The convergence performances Algorithm 2 and algorithms in Mitra al. (2021a b) under different local training periods т 2,3, 5, 6, are shown as Figure g It is clear that the proposed stepsize strategy indeed yields much faster convergence than the compared counterparts.
A.2 Additional Comparison under IID distribution
compares Algorithm and Algorithm 2 with existing methods Qin al. (2022b): Mukherjee et al. (2023) Mitra al. (2021b): Khaled al. (2020) using universal stepsizes. For further
In Section 6.1.1 Figure
comparison, Figure 10 illustrates the behavior of the same existing methods when equipped with local
stepsizes. Both Figures
and 10 highlight the superior performance of Algorithm
| over the existing
approaches.
A.3 Additional Evaluation using CIFAR-10 under non-lID distribution
In this subsection, conduct additional numerical experiments CIFAR-10 to compare method with several federated lcarning basclines: FedAdam (Reddi et al. 2020), FedProx (Yuan & Li 2022), SCAFFOLD (Kariniredyy et al., 2020), FedLin (Mitra et al. 2021b), and Scalfnew (Mishchenko el al. 2022). Figures
[1 12 and 13 present results for 3 set to 1, 0.1 and 10, respectively, corresponding to moderate, high, and low heterogeneity in the data distributions. For all results shown in Figures [1] 12 and [3 the stepsizes for
Algorithm FedAdam, FedProx, SCAFFOLD, FedLin, and Scaffnew are selected according to the guidelines
from Theorem Reddi et al. 2020 Yuan & Li (2022). Karimireddy et. al. 2020 Mitra al. (2021b), and
20

---

Published in Transactions on Machine Learning Research (02/2026)
0.75
6130
8.150
0250
Errors ett)
Errors e(t)
0.122
0:10
0.300
0.21
1150
0622
0.00
1000
25
22
60)
830
1000
12a.
26
40
600
331
1001
1381
25
48
463
130
1000
1280
100
Communication Rounds (t=
Communication Rounds (t
Communication Rounds ( 4)
0.12
Errors ett
Errors ett
1:10
0.10
26
26
36
Communication Rounds (T
Communication Rounds t (r=
Communication Rounds ((T= 7]
Figure 9: Comparisons the performance of Algorithm 2
under the proposed stepsize with Mitra et al.
2021a under different local training periods т
Mukherjee al. (2023)
Mitra (2021b)
Erars elc)
Eirors etco
Algorithm 2
Algorithm 1 with Universal Stepsizes
10"
Khaled (2020)
Qin al. (2022)
Algorithm 1 with Local Stepsizes
40
200
26
400
41
Communication Rounds (T 2)
Communication Rounds (T 3)
Errors 688) ((t)
Errorss
208
30
220
250
380
222 300
281
231
240
150 130
Communication Rounds c (T-44) 4)
Communication Rounds [T
Communication Rounds (TT 6)
Figure 10: Comparisons Algorithm 1 and Algorithm 2 with Qin et al. 2022bb Mukherjee et al. (0023
Mitra et al. (2021b): Khaled et al. (2200) with local stepsizes under different local training periods т.
21

---

Published in Transactions on Machine Learning Research (02/2026)
respectively, using an estimated smoothness parameter of L 2. For Algorithm 2 FedAdam, FedProx, SCAFFOLD,, and FedLin, the local training period is set to 10. For Scaffnew, the communication probability is set to TT to ensure that the total number of communicated messages remains consistent acToss methods. summary of the experimental setup is given in Table 3 As shown in the ligures, our algorithm achieves faster convergence and higher accuracy than other baseline federateddlearningg algorithms. Note that the large variance of Scaffnew arises from the additional randomness introduced by its communication mechanism.
Mishchenko al. 2022
Table Experimental Setup in Figures 11
and 13
FIGURE
11
FIGURE
12
FIGURE 13
DATASET HETEROGENEITY LOCAL TRAINING PERIOD
CIFAR-10
CIFAR-10
CIFAR-10
0.1
8 8=1
3 == 10
10
== 10
10
NUMBER OF AGENTS OPTIMIEE
10
10
10
SEE LABEL
SEE LABEL
SEE LABEL
For Scaffnew, the communication probability set to II
that the total number of communicated
messages remains consistent
methods.
The stepsizes for Algorithm FedAdam, FedProx, SCAFFOLD, FedLin, and Scaffnew selected according
guidelines from Theorem Reddi (2020), Yuan (2022), Karimireddy al. (2020) Mitra ot al.
22021),, and Mishchenko al. 2022 respectively, using an estimated smoothness parameter
Scaffrew
2
SCAFFOLD
Test Accurccy
3.5
Train Accuracy
2.0
FedAdam
FedPrax
Scaffnew
ScafTnew
Algorithm2
Algerithm2
SCAFFOLD
SCAFFOLD
Fediin
RedLin
FedAdam
FedAram
FedProx
FedProx
1984 Communication Rounds
2ide
1502 2003
1098
10.9
J003
1003
2003
2503
1803
Communicaat Rounds
Communicatio Rounds
(a)
(b)
(c)
Figure 11: Comparison of Algorithm 2 with state-of-the-ard federated learning algorithms FedAdam, Fed- Prox, SCAFFOLD, FedLin, and Scaffnew on the CIFAR-10 dataset. The Dirichlet distribution parameter was set to 3 = 0.1. Each curve represents the average of five independent runs.
Scaffnew
Scaffnew
Algorithm2
Algorithm2
SCAFFOLD
SCAFFOL
175
FedLin
L75
Fediin
Train Accuracy
FodAdam
FadAdam
FedPrax
FedProx
Algorithm2
SCAFFOLD
455
675-
FedLin
FodAcam
352
63
FedProx
1089 Communication Rounds
2016
1093
993
3899
2003
1250
126
3900
3000
2099
2903
1099
Communication Rounds
Communication Rounds
(a)
(b)
(c)
Figure 12: Comparison of Algorithm 2 with state-of the-arr federated learning algorithms FedAdam, FedProx, SCAFFOLD, FedLin, FedAdam, FodProx, and Scaffnew- on the CIFAR-10 datasot. The Dirichlet distribution parameter was set to 3 = Each curve represents the average of five independent runs.
22

---

Published in Transactions on Machine Learning Research (02/2026)
24
Scaffnew
A
SCMFOLD
FedLin
Test Accuracy
Scaffnew
Fedhdam
Algorithm2
Train Accuracc
FedPrax
SCAFFOLD
Fedlin
Scarfnow
FadAdam
Algorithm2
1.9
FedProx
SCAFFOLD
FedLin
FedAsam
FedProx
26
1500
Communication Rounds
Communicalion Rounds
Communication Rounds
(b)
(c)
Figure Comparison of Algorithm with state-of-the-art federated learning algorithms Fed Adam, FedProx, SCAFFOLD, FedLin, FedAdam, FedProx, and Scaffnew the CIFAR-10 dataset. The Dirichlet distribution parameter set to 3 10. Each curve represents the average of five independent runs.
A.4 Sensitivity of smoothness constants in CIFAR-10 experiments under non-IID settings.
The numerical experiments in Section 6.2 employ an estimated smoothness constant = To assess the sensitivity of the results to this parameter, we perform additional tests on the CIFAR-10 datasct using estimated values of L (Figure 14] and L 1.5 (Figure 15). Figures 14 and 15 demonstrate that algorithm maintains faster convergence and higher accuracy with these varying estimated values.
28-
Thst Accuracy
Train Accuracy
Algorithm2 Scaffnew SCAFFOLD
Algorithm22 Scaffnew SCAFFOLD
Algerithm2
26-
SCAFFOLD
34
FedLin
16"
1008
3000
3550
2300
Communication Rounds
(b)
(c)
Figure 14: Comparison of Algorithm 2 with state-of-tho-art federated learning algorithms SCAFFOLD, FedLin, and Scaffnew on the CIFAR-10 dataset. The Dirichlet distribution parameter was set to = and the smooth constant is estimated as 1. Each curve represents the average of five independent runs.
252
Algorithm2
235
Scarfnow
SCAFFOLD
FedLin
Train Accuracy
3.50
115
Algorithm2 Scaffnew
Algorithm?
Scarfnew
a1
SCAFFOLD
Fedlin
FedLin
33
1088
3000
2000
2006
1093
300
1099 Communication
1988
2009
2003
12
226
3900
3500
2009
2593
1099
Communication Rounds
Communication
(a)
(b)
(c)
Comparison of Algorithm 2 with state-of-the-ae federated learning algorithms SCAFFOLD, FedLin, and Scaffnew- on the CIFAR-10 dataset. The Dirichlet distribution parameter was set to B = 1 and the smooth constant is estimated as 1.5. Each curve represents the average of five independent runs.
Figure 15:
23

---

Published in Transactions on Machine Learning Research (02/2026)
B
Supporting Lemmas for the Proof of Theorem
I
Lemma 3
Zhou 2018
For every Ls-smooth and conver function fi(x) over R", we have
1
f(()) 2 f((x) (Vf(()).v-
Vf((z) f
2L,
for any 2, y E R" and i e S.
Lemma 4 [Mitra et al. (2021b)) ) Suppose that fa( is Lm-sthoth and convex. Then, for any 0 a S 1 T. we have
lly - -V-=-(VVV)--Voo))) s llv æ!l
for any 2, y E 18"
Lemma 5 Zhou 2018 ) For the conver and L-smooth function f(x), we have
L |1y x/|
f() S f(x) + (VI(x), -
x) xx)
2
for any x, y E IR".
C Proof of Theorem 1
Proof. The sequence ((x)) satisfies
f(ā(t)) - f(x*)( 20
for any t 2 1. From Lemma to prove Theorem we only need to prove that the nonnegative sequence (f(((t) - [(=)) satisfies the summable and monotonically decreasing properties.
Summable Property: Firstly, we establish the summable property.
From 2 in Algorithm we have
| (1) ==1
=1|x,,,(11) ==1 20 2o(V/[(r,((() (,,() x²) +
(11)
From the convexity of f((x), we have
2a (V(VV(C))))) x²) 2aff((x') (t))
(12)
Using the strong growth condition (see Assumption
yields
[+(('*]] =
(13)
for any i E S and x² X
Then, from Lemma and 13 have
V VVA < 2L, ((c,)(0)))) {((x))) ((00))
(14)
Combining 11
2 and 14 we arrive at
(xt)++((t) x= [xt,(t) x2112 (2a -
(15)
24

---

Published in Transactions on Machine Learning Research (02/2026)
It is worth noting that the following inequality holds
1
| + 1)
2=11
1 (t) x=11?
N
Thus, from Algorithm and 15 we have
| + 1) x²1
N
Σ (((()))(())())) + ||x(() - x²1
2a 20
(16)
N
Under the stepsize setting
3 we have
2a 22,2a
for any E Morcover, from Assumption Thus, in 16 we have
we have |[Vf((*))] for any X and i E S.
-(xx)~ f((uu(tt) so
for any i E and k = -T
Thus, using 16). we have
1) S [[x(() x²112 + {2a 2T.a " (
(17)
From 17 we can obtain
f(a(t)) f(x*) |T((1) x²11 - =0112-1115(1
+ +1) x=-11
2a 2La²
Thus, for any T 2 1, have
Σ ((G(0)) f(x))) < | - 112
(18)
2a 2L
which establishes the summable property of the sequence (f(ā(t))-faa)
Monotonically Decreasing:
Next, we show that (ā((t) is monotonically decrcasing.
From Algorithm have
| (1) Z(()
<1) =(t) - a (V.i(aa,(()) =(()=a(VV(()a)()) - -
Using Lemma and the stepsize setting in we arrive at
[x) - a(1) <
+ + =4
(19)
Using the update rule in Algorithm we obtain
[xx =(t)]l kallV/A(E(t)]
(20)
for k k= 0,1,,
25

---

Published in Transactions on Machine Learning Research (02/2026)
It is worth noting that the following inequality always holds:
1
vi((nn(t))
1
+
From Assumption and
we have
1 N ΣΣ (0) =(1| ( - N
( (1)
Further using Assumption 3 and the update rule in Algorithm 3
we arrive at
77 IV
ΣΣ
S ++ 2
(21)
N
From 2
we have
N
1) =(t)
a N
(x(,)((t)).
k=0 0
The global loss function f(z) is L-smooth with L = N Em L. From Lemma 5 and Assumption we have
((o(++1)) 1))
L
S/(F(()) (V)()())),
(i((((())
(((L((
N M
- (V)(E))) N ΣΣ aVA(=(())
a (V((((()))
N
=
As for the last term of the above inequality, we have
N T-1 ΣV
(VS((()),
Vi(aL - N
a (
<IV)(E(())
Vi((E VA(E()))I
<IV)(E(()
(t)),,((==(()l))
(22)
where the first inequality follows from Schwarz incquality and the second incquality follows Furthermore, using Assumption and
from the L-smooth assumption (see Assumption
(2), we have
f(a(t+1))
+ a² (2((T+
L n7( 1) (f(()t))) 2 ++
- ar (or
2
+
ΣΣ L. (1) (1)-)((1)))
(23)
26

---

Published in Transactions on Machine Learning Research (02/2026)
Taking 20
into 23
yields
+(z(t+1))
- - ar (f + L 2
a2
(o2((=+ T+
71T - [
+ Σ
L,ka [[[[(
(24)
From Assumption
and 24
we arrive at
f(a(t+
-or OT ar + _ a²
L
fa²(T+
nT( 111 11
[Vf((tt))
2
2
+allV/((())I Σ kallV
Σ Loj.
(25)
which further implics
f
L 202 1/(T
-1)1 ] |V
-
ILT(T-1)a² (
2
Therefore, the stepsize should satisfy
L [ T 2
n/T 1312 a² nIr(T- - a² <0
to guarantee the monotonically decreasing property of f(((t)) f(x"). Equivalently, stepsize satis-
fying
a Σ L(27 + n(r 1))2 + 4TL
guarantees the monotonically decreasing property of f()).
D Proof of Theorem 2
Proof. From in Algorithm we can obtain
| (t) 1²1
=| (t) x=1² 20, ((((aa())) -10
(26)
From the convexity property of fz),, have
2a, (V (t, - x²) 2ax(f((x") (((of((("==(xxxxx()))) (t))
(27)
Assumption 3
implies
[+{(**] -0
27

---

Published in Transactions on Machine Learning Research (02/2026)
for any E S and x² X² Thus, combining with Lemma 3 we have
[V)((=))()))) & 221 (illa()))))) - - -((x))
(28)
Combining 26
27
and 28
we can obtain
| (1)
x= (() - x²11 (20; 2T fi(x') (i(o)a(1))
(29)
Note that the following inequality always holds:
N
[ + - 1=1 -x
[xi (1) x=1
N
Hence, Algorithm and
29 imply
| 1) - x" 11?
2a; 2L,a
Σ (((="))((((xxt))) + ||=(t) - -x"112
(30)
k=0
Under the stepsize setting
have
20; 2L,0,
for any E S. Moreover, Assumption 3 ensures
f((x*) - f((x,,(t)) 5o
for any E S and 0,,,..,,.7 1. Substituting the above inequality into
30 yields
| 1) 21 s (t(()) x
min {2ar 24.a7 - ((5(1)) ISSN
(31)
From 31
we can obtain
(((()))(<>"> |5(1) | + x=1
minigisN {20g; 2L,a
Thus, for any T 2 1, we have
Σ -((t()))
[T(1) - 11
(32)
min minisiin 2L,aa
Since f(ā(t)) f(x*) 2 0 holds for any t, we have
lim f(i(t)) f(x).
In addition, from 32 for any T 2 1, we can obtain
f T Σ a()) - -(x))
Σ {(((()) (((())))(('')
T
|[5(1) x²
T
finis - 2L,a,
which completes the proof.
28

---

Published in Transactions on Machine Learning Research (02/2026)
E
Proof Theorem 3
Proof. From Algorithm 2 the updated rules 6 and 7 can be equivalently expressed as
(t) = (t) - f((((t)) - VV(rLtt)))+++
(33)
The relation in 33 we further implies
+ (1) =(t) < [aa a()) + a (VI((,,,)))) (V)))) +((0)\)))))))
(34)
From Lemma and (34). the stepsize satisfies
S +.. we have
[[] =(()]l < (t, (()] +a|Vs((((\)]
(35)
Using induction, we obtain
[x,,((t) z(t)ll S ka ka
(36)
Using the update rule in Algorithm
obtain
(t) z(t) Vi((aa)(() TA -aa----aaaata -(((()
k=
Therefore, the average parameter ø(t + 1) satisfies
+(++1) N
(1) =5(()= Σ (()x((())
(37)
which further implics
|i 1) ->x'11'
11
[T((t) x=12
N
N
= = 2- a
V (t), x² )
+
v (((x((t)))
(38)
N
1=1 k=0
For the first term on the right hand side of 38 we have
V (()) x²)
N
N
n. (1), VA((.)()) +
Σ
(1),((1) =(1), VA((()))
N
K=
N
(2) zt)), (f(.. - v((((t))).
(39)
1=1
k=0
Furthermore, using Assumption and the convexity property of fi(z), we can obtain
(0)) x²)
N N
N
[(x=)) - fa((a((t)())))))))))))))))))))))
Σ
-
N
(1) - -Z()1
(40)
29

---

Published in Transactions on Machine Learning Research (02/2026)
Combining 136 and
40
arrive at
(()
xx)
k=
1 N ΣΣ L,K² (21
(41)
Plugging the stepsize condition 0 al S into
41 yields
(()) x²) S f((((x)- (((()))))((())
-((0))
+
Σ k2
(42)
k=
Applying the relation Ek=1 12a m(++ 1(2+1)(2+1)
to the second term on the right hand side of 42
yields
(0), - x²) S - + Ara))
(43)
where A (r-11)2--1)
For the second term on the right hand side of (38 we have
v((aa((t)||
v f((x,((()) Vf((E(t) -((aa())-TT((()))))))))))))))))) ++]V++((()))
+
(44)
k
Using the smoothness condition in Assumption 1 we can further obtain
1 A((, -
-
(45)
Combining 336 and
45
can obtain
S Σ
L 44ko/17//330001111100000000
(46)
K=
Applying the stepsize condition 0 < raL; S 11t to
46
yields
N
v)(E)((()) & (b)I)((())))
(47)
N
where A2 2r -
Then, combining (38)
43
and 47
can obtain
[ x [a(tt) - x 11 2Ta - + {2Λ, + 13)02115(((0)))
(48)
Using the relation established in Lemma 2 we can obtain the following inequality from
48
|æ(t 1) 211 - ||=(t) ==1
2A, A3 52ra 5(x0) (((0)))(((()))
{((((t) f(x(t+
(49)
7
30

---

Published in Transactions on Machine Learning Research (02/2026)
Rearranging terms yields
((a(((((t) - f(x²)) - || + 1) - x²1 2A + AB - - f(((t+
(50)
Thus, for any T 0, summarizing
50 from / t= to / - T leads to
Σ -
T
f(x0)) f(())))((x'))))
[a(1) =x112= + 2A1 + A3 ((((1))
(51)
2ra
2
Using [51 Lemma 2 and Lemma 1 we can conclude that f(ā(t) converges to f(x") with the convergence rate of (1/)), which completes the proof.
F Proof of Lemma 2
Under Assumption know that ((x) is T-smooth. Thus, from Lemma
have
f(x(++
<f(E()) -a (((3() 1 N ΣΣ
(((L)(()))+ + 1 ΣΣ v (
(52)
Substituting
47
into
52
leads to
f(r(t + 1)) sf(((t)) - ar ( +2 -
+allVf(<(t)|]
(f(aa.(() VfA
(53)
k=0
Using the smoothness condition in Assumption 1
we can have the following relationship for
53
S(ū(1 + 1)) ()) (()()))) V 2T. 2
N r-1
+ +
Σ (()=))())-=((}}
(54)
N
k=
Plugging
33b into
54
yields
5-2
- - -
La (()()
(55)
2
Rearranging like terms leads
{Or 5LT - LT 2 [V S({()) S(ō(1 1))-
(56)
Since the stepsize satisfies 0 < < I:
2
there exist. > 0 such that
57
La ya?
aT
2
Thus, we have
aa v
= f(ø(t + +));
implying that the sequence f(((1) is monotonically decreasing, which completes the proof.
31

---

Published in Transactions on Machine Learning Research (02/2026)
G Proof of Theorem 4
Proof. We use (z())) to represent the unbiased estimate of the gradient Vf(r). From 2 in Algorithm
we
can obtain
(t) - (oi++1()-xx1) x²12
[x,((t) -x" 2a, - (0
(57)
Using the convexity of fe(x)), we arrive
-20 (L(r,, x²) 20,([((x") (()))(())))
(58)
Assumption implies
[+)((=*]| =0
for any E S and x² X Thus, combining the procoding relation with Lemma 3
we can obtain
[V((LL())) 2l((f((()(() f((x))}
(59)
Combining 57
58
and 59
we arrive
| 1 (1) x= 1|2
< (t) - x² $122 (2a; - 2L,0 - f((x,,(()))
20: (xx, (fi(
- x²) (a) - (()))((())).
(60)
Using 60 and the property of the stochastic gradient, we have
E|ll E|| x= 1 s (t) 2²1 +(a; 2L,a3) - (t)((,)(()))] + 2aç0².
(61)
Note that the following incquality always holds:
N
E[| - 111 -
N Σ
Ell (f))).((t) - x=11
Using the update rule in Algorithm
and 60
we arrive at
El| +1 - 11
(2a: 2L.a Σ [n(00)
- ( B[M(EL(001]] + -11=(()=211p - x11 2Ta
(62)
Under the slepsize selting we can obtain 20r - 2Laa for any i S.
Moreover, Assumption ensures f(xx)) (lf((x,,,()) < 0 for any E S and 0, I,... ,
Thus, from 62 we have
E Ellla(t 1) x-11
min { 2a; 2L,a ( -
20a + El](((t) - x=11%,,
(63)
N 1
32

---

Published in Transactions on Machine Learning Research (02/2026)
which further implies
[[[(E(())] - [(x") [1
x= -
E [t + 1) x= x=1
ΣN 2Ta
minggig (2a; 2[, 0².
minigien (2a; 2[,aa]
Thus, for any T 2 1, we have
T
[ x=1
N ii=1= 2Ta
Σ -
+ minigisN {2ar; - 2[,00?] 0².
(64)
minigign (2a; 20,0,]
From 64) for any T 1, we obtain
T ( Σ =(t) - f(x*) - minigien (2a; 2L,a,
- x=1
1 Li=1 N 2Ta
E
minigigN {2a; - 2L, 0²,
which completes the proof.
H Proof of Theorem 5
We use (r) to represent the unbiased estimate of the gradient fz()). We need the following Lemma 6 to prove Corollary 5
Lemma 6. If the stepsize satisfies 0 < a < minpssigs we have
(1) =()) 12 I2+"La²B(J(<())) [(x))] + 27
for 0 S < and i S.
Proof. From Algorithm g we can obtain
N
x.x+1 = =x, af Σ - - (((0)) a(ax(())))
Thus, we have
Li (1) Z(1)
(t) - =(t) of (v((((()) (z)( ()())a(()))
1 N
Σ (T(() N Σ V(}((()) V)((((() ((())) (,)))(()) v((a)(())))
From the property of stochastic gradients, we have
E
[0) (1) =())
=R
(i.le(()) - -((() a ()(((()) - VZ(()) + V(( +
aFB
Σ gz N Σ
- ( (65)
For the first torm of the right hand side of 65 we can obtain
vs((((()) + vs(a)((()) ||]
E (() a(1) (V)(((())))
< (1 + b)B B (1)
- VA(TMM) (1 (1+++)++3 =)(
33

---

Published in Transactions on Machine Learning Research (02/2026)
From Lemma 4 we obtain
I i(t) - -v v.((((()))))))))))))))))))())))) V((au()))) [']
<( + 1
(66)
if the stepsize satisfies < al, 1 for any 1 s
For the second term of the right hand side of 65 we have
N
N
93 (T(1))
(zz()(1)) + (F((()) - 9:(3()) + (((x((() -V)(oax))))
N
3
+ V 33 9:: (3(a)(()))))) (B000000000000000000000-0--00000 -
(((())((()11))
N
for any E S.
Using the propertics of stochastic gradients, we have
N
N
E
Σ
9y
(z(t))
+ - (z(()) + ( V(((TL(tt)
-V((L)t))))))) $ (67)
N
N
for any E.S.
Combining 65
66
and
67
arrive at
Bl =t))1 s (1+
(1+ (etlle/000000001--0--ooee//////0
9a?0?
Using induction, we obtain the following relation holding for any 0 k<k<n <:
E 11:x((1) < (( 9a² 02
Σ 11+
4=0
which further implies
- -[())] s ( +1 (1 (1+ -1
E
(1+
Using the relation can obtain
f(x*)) from Assumption [nd the convex property of f((x),
E (1))(())=(01)) < 12)= f(x))) 27ra202
which completes the proof.
Next we proceed to prove Corollary From the update rule Algorithm
wc have
r-1
1) = x(t)
Σ
9
(t),
N h
j=
which further implies
( + 1) 2=1 -1=(t( 1
N
N T-1
2a N
9z (
x2. (1) xz)
+ 2
ΣΣ カ=
95 ()()a1()))|
(68)
N
j=1 h=
34

---

Published in Transactions on Machine Learning Research (02/2026)
For the term 2a Nv Eÿ=
-xx) in (68) we have
g3 (1)3 - =x+)
2a.F
2a
(1). ([)((z((()) +
20 ΣΣ
R (1)a(1) =(1), (()())((0))
N
N
1=1/=0
==
Using the convexity of fi(x) and Assumption we arrive at
N
((
(l) -x06))>xx]] x²)]
2alE
j=1 h=0
N
20 N T-1
E [1(x*) - [(()(())
Σ Σ
( [(((()) + L 11 - =(013
+
N
h=0
jml h=
which further implies
20T (
1 Σ
9j (1)),)())) - -xa)
j=1/= 1=0
+ al ΣΣ
<2aTB
[3(())
(1) -
(69)
N
k=
From Lemma we have
E| (1)))((t) =(tt (lf f(x*)]++++++ + 20
(70)
for 1 <.
Combining (69 and 70 yields
(())) -260)-xx) =')
2n
j=1k=0
22arB1[(2") - ((7(1)) + 12, 12,
-(x"))(277> 2a
When the stepsize satisfies 0 6raL < we have
1 N ΣΣ
2aE (
(t)) x")
<2aTB[J - 330
(71)
For the term a
-1=1 >
21 (Z (t)) in
68 we have
2
93 (1))
N
N
<2a²
95 (0)(0))(00) oos((()))
20²
ΣΣ (=()))
(72)
N
N
j=1
0=0
j=1
35

---

Published in Transactions on Machine Learning Research (02/2026)
Using the smoothness conditon in Assumption 1
and the inequality || |E= asll? < > ||a;|?? we have
(5)=)((()) (()))))))(((())
L L2
N
3ra² N
( - -(())
ΣΣ
(g((()(t)) V[(E)((0)1I
N
1=1
ΣΣ
(73)
N
From 73
and the property of stochastic gradient, we have
T-1
9,) s Gra N T-1
T
ΣΣ
(o)((s(()))
-,
[l) =(1)1l) + 2702. (74)
ド=
j=1k=0
Plugging the inequality in Lemma 6 into
74
leads
N
2a 2
E
(t))
h=0
<72 L [[f(x(t))
f -1-
12a2700
(75)
For the term
1
EN
Σx 91 (z, (kT))
72 we have
2
1
Σ
r-1
9, (3(0)|
-
2a
Σ 1 (=(() -2
N
j=1
h=0
Using Lemma 6 and the property of stochastic gradients, have
2a P
ΣΣ Σ
()((())
4a2700² ( f(x"))
(76)
Combining 72
75
and
76
have
N
2
Σ
g ( (z,m
(727" (12---=---0020000)))))1)111-)-1- 1(= 16027002
0=
When the stepsize satisfies 0 < 6raL S we have
E
9 ( 100=La(B(f((()) f(**)] 25
(77)
Combining
68
71 and
77 have
E| [l + 1) - x | B[| - x² x=1 S (2ar Lo²"La²) ((((() +373
3472
(78)
When the stepsize satisfies 0 < a < I we have at - - 2 0. Plugging the preceding inequality into
78
yileds
1
-f('){ [mx(11) x=112
34 0² at
B[f(E(t)
T
atT
1=1
36

---

Published in Transactions on Machine Learning Research (02/2026)
Moreover, using the stepsize condition 0 < S minigignt tyy 12rz) } and the convexity of f(x), we obtain
[ क -(x")
< [1((1) - x2
aTT + 34T00²
for any E S, which completes the proof.
37


Reviews:
[{"review_id": "bs23M0wMGw", "reviewer": "Reviewer_XCiD", "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": "", "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 the convergence of the federated learning problem. \nFor the iid case, it theoretically proves o(1/t) convergence rate with a global stepsize, and this stepsize is larger than existing results. \nFor the iid case, it proposes to use a local stepsize without knowing the global Lipschitz constant. Convergence is established, and numerically, the performance is even better than the global stepsize algorithm.\nFor non-iid case, it proves that algorithm 2 can use a larger stepsize and achieve o(1/t) rate. Both are better than the results in the literature.\nThe paper also discussed the impact of using stochastic gradient.\nThe core contribution is on the mathematical technicality.\n\nLimitation: \n1. The paper focuses on the GD-based algorithm, not the SGD-based algorithm. The authors repeatedly compare their results against papers of SGD; it seems unfair. Actually, all simulation results on the IID (Fig 1 and 2) look like all methods actually achieve a linear convergence rate $O(e^{-t})$. It somehow implies the presented results are still far from sharp.\n2. Also the Assumption 3 seems very strong to me. In fact, the assumption assumes that the local solution is equal to the global solution. If that is the case, one only needs to run GD on one local node without any communication and can already achieve a good rate.\n\nThe paper needs a careful round of proofreading, as I notice a few typos. For example\n\nP5, second paragraph: \"Compared with Theorem 2, Theorem 2\" --> \"Compared with Theorem 1, Theorem 2\"\n\nP6, third line below the algorithm box: \"$y_{i,k}(t)=\\nabla f(x_{i,k}(t)) $\" -->  \"$y_{i,k}(t)=\\nabla f_i(x_{i,k}(t)) $\"\n\nequation 7, mismatch left parentheses and right parentheses\n\nequation 17 and the equation above it: the \"L_i\" in the denominator --> \"$L$\"\n\nP20, line 3: \"From algorithm 3\" --> \"From algorithm 1\"\n\nP20, the line above equation 20: \"rull\" --> \"rule\"\n\nIn terms of the proof, I have one question:\nP20, last equation, the third term on the rhs: I don't know where the factor $L$ comes from. Please clarify.\n\nFor the comparison of Theorem 1 and Theorem 2:\n\nWhat is the technical difficulty to show o(1/t) rate in Theorem 2, or more directly, the difficulty to prove the monotonicity?\n\nIn the current presentation form, it leaves a wrong impression that Theorem 2 leads to only an O(1/T) rate. A clearer discussion is needed. Maybe the author can point out the comparison between (17) and (17).\n\nFor non-iid case, a non-convex experiment is presented. The paper is all about convex objectives. I will suggest a simulation of non-iid case.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The mathematical derivation is sound (except for the one I asked in the review)\nThe simulation results show the advantage and justify a better empirical performance.", "audience_yn": "No", "audience_explanation": "While I believe the community will be more thrilled for results on SGD, non-convex loss. \n\nSomeone will be interested in sharpening existing results for simplified scenarios. I don't think the technique in the proof is completely groundbreaking, but readers may learn some tricks from it. But unfortunately, the proof relies on a strong assumption A3. Thus the proof technique cannot easily generalize.", "requested_changes": "Please refer to my review in \"Summary Of Contributions\". Please correct typos and add more discussions.", "broader_impact_concerns": "none", "additional_comments": "none", "extra_scores": {}, "extra_text": {}}, {"review_id": "fRmN65XGKV", "reviewer": "Reviewer_1U7T", "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": "", "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 presents a method to reduce communation costs in federated learning (FL). Specifically, the authors propose two strategies that allow models to converge faster than the standard rate of $O(1/t). For IID setting, the authors analyze FedAvg and propose to let clients with smoother loss taking larger steps without waiting for coordination, and thus achiving better convergence. For non-IID settings, the authors track gradients in a recursive fashion to correct the gradient drifts across steps (this is in some sense comparable to SGD with momentum). The authors analyze both algorithms theoretically and empirically show that by using their proposed approaches, FedAvg can converge faster than previous baseline methods.\n\nStrengths:\n\n1. The authors provide theoretical analysis that FL algorithms can achieve a convergence rate of o(1/t), they also show this empirically with extensive experiments.\n\n2. Under non-IID settings, the authors introduce gradients tracking to correct the drift caused by heterogeneous data, which proves to be more effective than existing baseline methods.\n\nWeaknesses:\n\n1. As stated by the authors, Algorithm 2 requires exchanging an additional variable for the gradient, which adds to communication costs and is subject to data leakage from gradients.\n\n2. Experiment datasets / baselines are a bit limited, methods like FedAdam, and further datasets should be consideded for a more comphrehensive evaluation. Also, more implementation details and experiment settings can help improve the understanding of exp and eval of the proposed algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors support their primary claim of convergence with mathematical proofs (e.g., Theorems 1, 2, and 4). Empirically, the evaluation results are also showing the effectiveness of the authors' proposed algorithms, with the majority the of experiments performed on CIFAR and comparison to a few FL baselines, which can be further reinforced to achieve a more comphrehensive evaluation.", "audience_yn": "Yes", "audience_explanation": "FL community should be generally interested in the findings of this paper, which improves communication efficiency upon existing methods.", "requested_changes": "1. Additional experiments with more baselines like FedProx and FedAdam, if the proposed methods still achieve superior results, the eval results can be be more convincing.\n\n2. More experiment details, how clients are set up, what optimizers are used, all hyperparameters used in the experiments. I suggest the authors summerize this in a table if possible.", "broader_impact_concerns": "1. Authors should also discuss potential data leakage in algorithm 2 (which can potentially caused by gradients communication).", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nkj52jmWjg", "reviewer": "Reviewer_ub9E", "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": "", "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": "**Summary**\nThis paper lies in the field of federated learning and considers general convex loss functions for individual clients.  \nThe authors first investigate convergence of FedAvg [1] to an optimal solution under the IID condition. They show that the convergence rate improves from $O(1/t)$ to $o(1/t)$ (where $t$ is the number of communication rounds between the central server and the individual clients) when clients choose step sizes individually (based on the geometry of their local objective functions) rather than following a globally coordinated step-size schedule. This result is shown to hold in the case of exact gradients and under an additional assumption, namely the Strong Growth Condition, which the authors use to explain why the lower bound established in [2] is not contradicted. Finally, for IID data, the authors provide insights into what happens when stochastic gradients are employed.  \nFurthermore, the authors investigate the case in which individual clients have access to non-IID data. They propose a framework that requires sharing gradients at each interaction with the central server. The authors claim that this framework encompasses other methods [3,4]. They show that this method achieves a convergence rate of order $o(1/T)$ (where $t$ is again the number of communication rounds between the clients and the central server) in the exact-gradient case, without relying on the Strong Growth Condition and considering the a global constant step-size. In this setting as well, the authors provide insights for the case of stochastic gradients.  \nFinally, the authors numerically validate their methods against baseline approaches.\n\n**Strengths**\nThe main strengths of the paper are the following:  \n- The authors pose in a relevant framework and they make steps towards a deeper theoretical understanding of Federated Learning convergence, especially regarding the more realistic case of considering individual clients to have access to non-IID data.\n- The paper is well written and easy to follow. The authors present all the necessary details to understand the work.  \n- The authors present results with exact gradients, then relaxing them to consider stochastic gradients.  \n- The authors validate their methods against baselines and their methods seem to outperform the competitors.\n\n**Weaknesses**\nThe main weaknesses of the paper are the following:  \n- [W1] It seems that the main argument of the paper comes from [5], where it is shown that, for convex and $L$-Lipschitz Smooth (LS) functions, first order methods achieving $$f(x_{k}) - f^{\\*} \\\\le \\\\frac{\\\\| x_{0} - x^{*} \\\\|_{2}^{2}}{2 \\\\alpha k}$$ are order of $o(1/k)$ rather than $O(1/k)$ (where $\\alpha \\in (0, 1/L]$). In my opinion, clearly stating this fact would enforce the paper and would make the presented results more appreciable.\n- [W2] Given the previous point, I suggest to include more commentary on Assumption 3 (Strong Growth Condition) as it enables to lower the rate of FedAvg. I suggest to discuss if it is reasonable, whether it is holding, and (most importantly), why it enables to provide a derivation leading to a similar result to the one cited in W1.\n- [W3] The extension of the results to the stochastic gradient case (Corollaries 3 and 5) is very important in my opinion since the setting is near to real-life settings, and because most of the related work [3,6] directly consider this scenario. Thus, I suggest to give more weight to those corollaries, even presenting them more formally.\n- [W4] The reported optimality condition considers the average iterate case, i.e., $f \\left( \\frac{1}{T}\\sum_{i=0}^{T-1} \\bar{x}(i) \\right) ...$, which is common as objective for non-convex optimization. However, for convex federated learning, it seems that some other works [6] consider just the aggregated model in the last iterate, which of course makes the convergence result stronger. Would it be possible to switch to the last iterate case even in the results proposed in the paper? \n- [W5] The authors just consider the setting in which individual clients are associated with convex functions to optimize, while it is possible to find results for non-convex functions [6]. For the sake of generality, I would appreciate a commentary on what happens to the results when the convexity assumption falls, or when such functions are characterized by other conditions (as the gradient domination one [7]).\n- [W6] Algorithm 2 proposes as a method handling the non-IID setting via gradient sharing. The authors claim it achieves a rate of $o(1/t)$ without the need of Assumption 3 and just setting a global constant step size (conversely to what happened with FedAvg). I have the following concerns about this method: $(i)$ it is unclear from the main text the intuition under which Algorithm 2 was built on and why it is well suited for the non-IID case; $(ii)$ it is unclear why the additional sharing gradient can overcome the need for Assumption 3; $(iii)$ the authors claim that the update rules of [8,9] are recovered, but I suggest that this needs more commentary on why Algorithm 2 keeps more general than the cited methods and on showing more formally why it is encompassing those ones.\n- [W7] Since Lemma 5 is *\"significant technical contribution of this work\"*, I suggest to move it into the main paper with a brief proof sketch.\n- [W8] All the figures in the experimental section are the output of $5$ trials, but no confidence intervals are shown. Figure 1: it would be interesting to see how the competitors behave with the local step sizes. Moreover, why in Figure 1 Algorithm 2 is not performing well? Is it about the fact that it is thought for the non-IID scenario? In real-life experiments (as the one in Section 5.2) the smoothness constants are not known, indeed, the authors use an estimated one. It would be very interesting to see an ablation on the sensitivity to such values, to see if a misspecification of them could hinder the algorithmic effectiveness.\n\n**References**  \n[1] McMahan, B., Moore, E., Ramage, D., Hampson, S., & y Arcas, B. A. (2017, April). Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics (pp. 1273-1282). PMLR.  \n[2] Glasgow, M. R., Yuan, H., & Ma, T. (2022, May). Sharp bounds for federated averaging (local sgd) and continuous perspective. In International Conference on Artificial Intelligence and Statistics (pp. 9050-9090). PMLR.  \n[3] Mitra, A., Jaafar, R., Pappas, G. J., & Hassani, H. (2021). Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34, 14606-14619.  \n[4] Mitra, A., Jaafar, R., Pappas, G. J., & Hassani, H. (2021, December). Federated learning with incrementally aggregated gradients. In 2021 60th IEEE Conference on Decision and Control (CDC) (pp. 775-782). IEEE.  \n[5] Lee, C. P., & Wright, S. (2019, May). First-order algorithms converge faster than $O (1/k)$ on convex problems. In International Conference on Machine Learning (pp. 3754-3762). PMLR.  \n[6] Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., & Suresh, A. T. (2020, November). Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning (pp. 5132-5143). PMLR.\n[7] Masiha, S., Salehkaleybar, S., He, N., Kiyavash, N., & Thiran, P. (2022). Stochastic second-order methods improve best-known sample complexity of sgd for gradient-dominated functions. Advances in Neural Information Processing Systems, 35, 10862-10875.  \n[8] Mitra, A., Jaafar, R., Pappas, G. J., & Hassani, H. (2021). Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34, 14606-14619.  \n[9] Mitra, A., Jaafar, R., Pappas, G. J., & Hassani, H. (2021, December). Federated learning with incrementally aggregated gradients. In 2021 60th IEEE Conference on Decision and Control (CDC) (pp. 775-782). IEEE.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Actually mostly.  \nThe theoretical claims are supported with proofs in the appendix.  \nThe proposed methods are also validated in practice and (except for the absence of the confidence intervals), the reported mean curves seem to support the authors' claim.  \nAdditional issues on claims regard Algorithm 2. Please refer to W6.", "audience_yn": "Yes", "audience_explanation": "This paper attempt to make steps towards a deeper theoretical understanding of (Convex) Federated Learning in both the cases in which the individual clients have access to IID data or to non-IID data, thus trying to pose in settings resembling real-life conditions.", "requested_changes": "Critical changes:\n- [C1] Addressing W1 and W2 would strengthen the paper in my opinion and would make the presented results more appreciable. Moreover, adding some more comments on whether Assumption 3 is reasonable and why (technically) it enables to reach $o(1/t)$ convergence.\n- [C2] I believe that the extension of the results to the stochastic gradient case is very important (and interesting). I suggest to give it more weight and to present this result more formally.\n- [C3] Addressing W6 is fundamental in my opinion. Especially $(i)$ clearly stating why the proposed update scheme is well-suited for addressing the non-IID scenario; $(ii)$ showing more formally why other methods' update schemes are recovered (maybe briefly reporting those methods in appendix); $(iii)$ discussing why the sharing of the gradient overcome the need of Assumption 3.\n- [C4] Please add the confidence intervals to the presented plots.\n\nRecommended changes:\n- [R1] Addressing W4 and W5 would be interesting in my opinion, but I understand that it may require a huge effort. I just thing that providing some insights would be nice, especially paving the way to possible future work.\n- [R2] Addressing W7 would enrich the discussion and the whole Section 4.\n- [R3] The additional experiments and commentary described in W8 would enrich the paper and would strengthen the presented results. Besides the comment on why Algorithm 2 does not perform well in the IID case, I believe that trying the baselines with local step sizes and adding a sensitivity study on the misspecification of the smoothness constant would be valuable.", "broader_impact_concerns": "I have no concerns on ethical implications of the work.", "additional_comments": "1. In the whole paper, most of the times parentheses or norms in math mode are not adapted to the actual size of formulas (the authors do not use \\\\left and \\\\right commands).\n2. At page 6, Equation (8) is referenced before being presented.\n3. In Table 1, I suggest to highlight better Algorithm 1 and Algorithm 2. \n4. In the experimental section, when presenting the used values for a hyperparameters, they are not stated as sets. (Example $\\\\rho = 1, 2, ... \\\\to \\\\rho \\\\in \\\\{1, 2, ...\\\\}$).\n5. Caption of Figure 2 does not says that the tested method is Algorithm 1.\n6. From Figure 3 on, all the captions seem to be the same, not allowing for distinguishing (without looking at the main text) which experiment we are looking at.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)