Leveraging Recursive Methods for Efficient Federated Learning
Authors: Jie Liu
Zuang Wang
Yongqiang Wang
Venue: Accepted by TMLR ()

Abstract: Federated learning algorithms perform multiple local updates on clients before communicating with the parameter server to reduce communication overhead and improve overall training efficiency.
However, local updates also lead to the “client-drift” problem under
non-IID data, which avoids convergence to the exact optimal solution under heterogeneous
data distributions. To ensure accurate convergence, existing federated-learning algorithms
employ auxiliary variables to locally estimate the global gradient or the drift from the global
gradient, which, however, also incurs extra communication and storage overhead. In this
paper, we propose a new recursion-based federated-learning architecture that completely
eliminates the need for auxiliary variables while ensuring accurate convergence under het-
erogeneous data distributions. This new federated-learning architecture, called FedRecu, can
significantly reduce communication and storage overhead compared with existing federated-
learning algorithms with accurate convergence guarantees. More importantly, this novel ar-
chitecture enables FedRecu to employ much larger stepsizes than existing federated-learning
algorithms, thereby leading to much faster convergence. We provide rigorous convergence
analysis of FedRecu under both convex and nonconvex loss functions, in both the determin-
istic gradient case and the stochastic gradient case. In fact, our theoretical analysis shows
that FedRecu ensures o(1/K) convergence to an accurate solution under general convex loss
functions, which improves upon the existing achievable O(1/K) convergence rate for general
convex loss functions. Numerical experiments
on benchmark datasets confirm the effectiveness of the proposed algorithm

Published in Transactions on Machine Learning Research (03/2026)
Leveraging Recursive Methods for Efficient Federated Learn- ing
Jie Liu'
jie9@clemson.cd edu
Department of Electrionl and Computer Engineering Clemson University, South Carolina, USA
Zuang Wang!
zuangu@clemson.edd
Department of Electrical and Computer Engineering Clemson University, South Carolina, USA
Yongqiang Wang"
yonggjio@ldemsonnccd edu
Deportment Electrical and Computer Engineering Clemson University, South Carolina, USA
Reviewed on OpenReview: https: // openreview. net/ formm? id= /GggktiV
Abstract
Federated learning algorithms perform multiple local updates on clients before communi- cating with the parameter server to reduce communication overhead and improve overall training efficiency. However, local updates also lead to the "client-drift" problem under non-IID data, which avoids convergence to the exact optimal solution under heterogeneous data distributions. To ensure accurate convergence, existing federated-learninn algorithms employ auxiliary variables to locally estimate the global gradient the drift from the global gradient, which, however, also incurs extra communication and storage overhead. In this paper, we propose a new recursion- based literated-learnigg architecture that completely eliminates the need for auxiliary variables while ensuring accurate convergence under het- erogeneous data distributions. This new dederated-learning architecture, called FedRecu, can significantly reduce communication and storage overhead compared with existing federated- learning algorithms with accurate convergence guarantees. More importantly, this novel ar- chitecture enables FedRecu to employ much larger stepsizes than existing dnderated-leariinne algorithms,, thereby leading to much faster convergence. We provide rigorous convergence analysis of FedRecu under both convex and nonconvex loss functions, in both the determin- istic gradient case and the stochastic gradient case. In fact, our theoretical analysis shows that FodRecu ensures o1/KK) convergence to an accurate solution under general convex loss fonstions, which improves upon the existing achievable O(1KK) convergence rate for general convex loss functions. Numerical experiments on benchmark datasets confirm the effectiveness of the proposed algorithm.
1
Introduction
Since its introduction in McMahan et al. (2017) federated learning has been extensively studied and widely
applied across range of domains, including natural language processing (Gupta et al. 2022 Ye et al.
2024
Liu et al.
2021 Lin et al. 2021). wireless networks Tran et al.
2019
Chen et al.] 2021
Niknam et al.
2020:
Yang et al. 2019) neural- training (Yrrochiin et al.
2019
Venkatesha et al.
2021
Li et. al.
2023
He et al. 2021). and mobile edge networks (Lim et al. 2020b
Luo et al. 2021
Khan et al. 2020 Lim et al.
These authors contributed equally this work.
Corresponding author

---

Published in Transactions on Machine Learning Research (03/2026)
Unlike centralized learning which requires aggregating all data to central server, federated learning allows training datasets to remain on individual clients. By letting individual clients perform local training on their respective datasets and periodically sharing model updates with a parameter server, federated learning cnhances scalability, data privacy, and fault tolcrance compared with contralized learning, and has garnerod
2020aj.
widespread attention in recent years (Ma et al.) 2020; Glasgow et al.] 2022:
Woodworth et al. 2020; Y Yuan
& Ma 2020 Patel et al. 2024 Agarwal et al., 2018 M Ghari & Shen
2024 Duan et al.. 2023 Acar et al.
2021
Reisizadeh et al. 2020).
In federated learning, to reduce communication overhead, each client performs multiple local updates based on its local dataset before communictting with the parameter server to synchronize its local model param- eter with those of other clients. However, this asynchronicity between local updates and communication operations leads to convergence errors when the data distribution is not IID (independent and identically distributed) across clients. More specifically, as pointed out in many existing results such as Karimireddy
ct al. (020);; Li ct al. (2019): Malinovskiy et al. (2020); Charles & Koncčný (2020); Charles & Koncčný [2021] ; Pathak & Wainwright (2020); Liu et al. (2026). the incorporation of multiple local updates bet two communication rounds introduces a drift in a local client's update as it tends to let local clients con- verge to their own local optimal solutions rather than the global optimal solution, leading to inaccurate and unstable convergence. Although diminishing stepsize can mitigate this "client-drift" problem, it inevitably slows down convergence and is often undesirable in many applications.
Recently, several algorithus have been proposed to tackle the "client-drift" problem and ensure accurate federated learning under a constant stepsize, with typical examples including SCAFFOLD (Karimireddy et al. 2020), FedLin (Mitra et al., 2021b), and FedTrack (Mitra et al.) 2021ap. SCAFFOLD mitigates the drift problem by using control variates that correct each client 's local update direction to stay aligned with the global loss function, while FedLin and FedTTrack addresses the "client-drift" problem by applying a linearized global correction to the aggregated gradient without requiring per-client control variates. The basic idca of these approaches is to let cach client locally store and maintain auxiliary variables (in addition to the model parameters) to locally estimate the global gradient or the drift from it. However, these auxiliary variables incur significant overhead in storage and communication, particularly in high-dimensional federated- learning problems, because these auxiliary variables have the same dimension the model parameters. In this paper, we propose federated- architecture that can avoid using auxiliary variables while ensuring accurate convergence under non-III) data with a constant stepsize. The main contributions are summarized as follows:
New Algorithm: We propose FedRecu which ensures accurate convergence in federated learning under non-IID data without using auxiliary variables. A key idea is the introduction of a recursive mechanism which enables each client to use gradients in both the current and previous steps in the update. The integration of the previous-step gradient is significant in that, through a judiciously designed update mechanism, it enables each client to locally correct its local drift and ensure accurate convergence. This design is inspired by EXTRA (Shi et al.] 2015) but has a significant difference: EXTRA does not allow multiple local updates between communication rounds (it may diverge under multiple local updates), whereas our design of the update and interaction mechanisms ensures accurate convergence under multiple local updates.
Enhanced Communication and Memory Efficiency: Our recursive mechanism significantly reduces communication overhead compared with existing federated-learning algorithms with "client- drift"" correction. Our FedRecu only shares one variable (a linear combination of model parameters and gradients), which is drastically different from existing "client-drift" correction algorithms that have to share both the model parameter and an additional drift-correcting auxiliary variable. More- over, our recursive mechanism eliminates the need for auxiliary variables used by existing methods (c.g., SCAFFOLD (Karimireddy et al. 2020), FodLin (Mitra et al.] (221b)) FodTrack (Mitra et al., 2021ab and Scaffnew (Mishchenko et al., 2 to correct client drift, resulting in significantly lower memory requirements for storing intermediate variables compared to these algorithms.
Faster Convergence: We prove that FedRecu achieves o(/KK) convergence under general convex loss functions. This represents significant. improvement. over the standard O(1/K) convergence
2

---

Published in Transactions on Machine Learning Research (03/2026)
typically observed in federated learning (for instance, the famous FedAvg has been shown in Glas- gow et al. (2022) to be incapable of achieving faster than O(1KK) convergence for general convex objectives, even under IID distributions; even after incorporating momentum, current algorithms still guarantee only O(1/K) convergence when no additional heterogencity constraints are imposed
on convex loss functions (Xu al. 2021 Liu et al. 2020; Cheng et al. 2023 Yang el al. 2022) ). To
the best our knowledge, apart from Liu al. (2026). FedRecu is among the first algorithms
ensure ((/KK) convergence for federated learning under general convex loss functions. This stands in contrast to prior results, where o(1/K) convergence have only been established under special conditions-sucl as gradient difference being uniformly bounded (Jiang et al. 2024), Hessian difference being uniformly bounded (Kovalev et al.) 2022). We also characterize the convergence of our algorithm under nonconvex loss functions and stochastic gradients, yielding results that outperform existing algorithms.
We theoretically prove that our new algorithm structure allows using much larger stepsizes than existing federated-learning algorithms tackling "client-drift" caused by non-ITD data. Our thcoretical analysis finds that our stepsize can be at Icast 6, 8, 6, and 49 times larger Ihan those used Khaled et al. (2020), Mitra el al. (2021a), Mitra et al. (2021b), and Karimireddy et al. (2020), respectively (see Table 2
Larger Stepsizes:
2 Preliminaries
Notations We use Z and Rn to denote the sets of positive integers and real n-dimensional vectors, respectively. We write the inner product as (x, v) = =-==l= for æ, E I", where [x], and [u], are the jth elements of the vectors and y, respectively. We use [Ali to denote the (i,j)th element of mairix A E Rm We denote the transposes of y E R2 and A E Ruxn as y and AT, respectively. We represent the Euclidean norm of E R. as ||^||| = V 1o.. Given a Z+ and b E Zt, mod b represents the remainder of the division of by b. We use Oc((t) and o(c(t)) represent sequences d(t) satisfying 0, respectively.
lim sup
d( < co and oo
dir) e(t)
c(t)
2.1 Problem Setting
We consider the following federated-leaminn problem over client set S 21, NJ:
min EE
fxx
Σ M(x),
(1)
N
where f: _R" + R is the local loss function and is solely dependent on the local training data of client E S. Due to non-IID data, the local optimum of f((x) is generally different from the global optimum of f(x). We make the following standard assumption on the local loss functions f((z):
Assumption 1. The loss function f((z) of client i E is L-smooth over R", that is, there exists a constant L > 0 such that
[V)f(z)) - V.)( s L| vll
holds for any E RR.
From Assumption D and the definition of f(x) in 1 we can easily obtain that f(x) is also L-smooth. In addition, we make the following standard assumption to make sure that has a solution:
Assumption 2. The optimal solution set X = fx² E [R" = arg minzer= f(x) is not emply, L.e., there exists at least one x² gm such that f(x*) < f(x) holds for any x E R".
Assumptions and 2 are widely used in federated learning Mitra et al. 2021a b
Mukherjee et al., 2023
Qin et al. 2022 Karimireddy et al. 20200 Khaled et al. 2020). They are more general than assuming strong convexity or Polyak-Lojasieviez (PL) condition on f(x). is worth noting that under Assumptions and
2 the global optimal solution may not be unique.
3

---

Published in Transactions on Machine Learning Research (03/2026)
3 Main Results
In this section, we first describe the core recursion-based update mechanism in Section 3.1
Then we sum-
marize the detailed algorithm in Algorithm | in Section 3.2 and characterize its convergence performance for both general convex loss functions and nonconvex loss functions in Section 3.3 (deterministic gradients) and Section 3.4 (stochastic gradients).
3.1 Recursion- Beaees Mechanism
The core idea of our now algorithmic framework is using recursion to employ information in both the current step and the past step to generate the new model parameter. Specifically, the local update for agent has the following form:
for kt < (k: 1)7: (1(1 + = (l) (V(((!!)) - (1 1) + V
(2)
Current
Past
end
where (t) is the local model parameter and denotes the stepsize. Our design is inspired by the decentral- ized optimization algorithm EXTRA (Shi el al. 2015) but has fundamental difference: EXTRA has two different consensus matrices multiplied on (t) and 2, (), respectively, whereas we remove such consen- sus coupling. This difference is key to ensuring the convergence of our algorithm when multiple updates are performed between communication rounds, whereas EXTRA only has provable convergence when one local update conducted between two consecutive communication rounds (under multiple local updates, EXTRA is subject to the "client-drift" problem and can even diverge). The detailed algorithu is given in Section 3.2.
Remark 1. The update P effectively addresses client drifts by incorporating both the current local gradiend, (((r((())), and the past local gradient, V [((xx(( ( 1]), inlo the updale rule. This dual-grudient- based mechonism ensures that the global optimum x" is fixed point of the iteration process- tercsssthaat is, the iterates will remain unchanged when initialized at the global optimum x². This stands in stark contrast to most existing algorithms wilhout drift correction, whose updales rely solely on the current local gradient. Since the local gradient is generally nonzero at the global optimum x² due to non-IID data (i.e., generally V fa(")) o O holds), the nonzero force exerted by the local gradient V f((")) will move such algorithms away from x² even when initialized at x²
3.2 Algorithm Descriptions
Some notations should be introduced before introducing our algorithm. The stepsize and the number of local updates are denoted as a > and r 2 1, respectively. The model parameter of client E S at iteration time is denoted as (t). Owing to the recursive update mechanism, FedRecu requires two initial values (-;) and ar( (=(-), which should follow the rules: zx(-2) can be arbitrarily chosen in R whereas 2x(-1) should be set as (-1) = xz 2) (V)((z(-22). Now, we are in a position to present. the algorithm in Algorithm 1:
Unlike existing federated learning algorithms that rely on auxiliary variables to track the global gradient or the drift from it (e.g., SCAFFOLD (Karimireddy et al.] 2020), FedLin (Mitra et al.] 2021b), and Fed- Track (Mitra et al. 2)21aa), FedRecu does not use any additional variables. This leads improved memory efficiency, despite the need store model parameters from the previous step. To illustrate this, we compare FedRecu with FedLin in the convex setting. Each client in FedLin is required to store four n-dimensional variables: the local model parameter, the global model parameter, the auxiliary variable used to track the global gradient, and rumning average of the local model parameter. (We exclude gradients from this count, as they can be recomputed from model parameters.) In contrast, FedRecu only requires each client to store two n-dimensional variables the current and previous model parameters. A detailed memory comparison is provided in Table
In addition, in FedRocu, the information shared between clients and the parameter server always one n- dimensional vector, which is linear combination of the model parameter and the gradient (more specifically,
4

---

Published in Transactions on Machine Learning Research (03/2026)
Algorithm 1 FedReecu
Initialization: the local training period 1, the stepsize a > O, the initial values #;(-2), and Iy (-1) for any i E for -= - to T do 1,2,...,. ,N in parallel do
for each client if t 1 mod = 0 then
Client i Iransmits (1) A 2c:(1) - x;(1 - 1) - aVI((a(()) + VV 1)) to the parameter
server and receives Σ j-11 (t(() from the parameter server. Then, each client updates its model
parameter as
N vy(1).
(3)
N
else if mod T then
Client i transmits wo;(t) (t 1) + (Vf(((((() a (t. 1)) to the parameter server and receives x Eÿ= (t) from the parameter server. Then, each client updates model parameter
as
N ()) N ==1
1;(1 + 1) = 2x:(1)
(4)
else
Each client i does local updates
+ = (10000-(((-))--//(((()))aaa/-)-- 1)).
(5)
end if end for end for
at tit=pp pr 1, (t) is shared between local clients and the parameter server and, at t pT, wx(t) shared). This is fundamentally different. from existing "client-drift" correcting algorithms such as SCAFFOLD, FedLin, and FodTrack, where in each communication round, two n-dimensional vectors (the model parameter and an auxiliary variable estimating the global gradient or the derivation from it caused by non-III data) are shared between each client and the parameter server. In fact, when 1, it can be seen that only one variable is shared in each communication round in our algorithm, which makes our communication overhead only half of that in SCAFFOLD, FedLin, and Fed'Track. Table [ provides a detailed comparison of FedRecu with existing algorithms regarding memory and communication requirements, which clearly shows the ad advantage of FedRecu in storage and communication overhead over existing counterpart algorithms.
Remark 2.
The recursive mechanism in FedRecu is inspired by the distributed optimization algorithm EX- TRA (Shi et al.) 2015). However, EXTRA only allows one local update in each communication round and directly exlending it to incorporate reultiple local updates still suffers from "client drifts" or even divergence. In contrast, FedRecu fundamentally revises the recursion and interaction mechanisms, and the associated proof techniques to accommodate multtple local updates. Specifically, we judiciously introduce different com- munication and update strategies for iterations t pr and pr (see (3) and 4 in Algorithm 7 to ensure accurale convergence under mullipple local updates. It importand lo note that neither process 3 nor alone guarantee accurate convergence, both processes essential to eliminating "client drifts".
Remark 3. We can explain why EXTRA behaves differently from our approach, FedRecu, under multiple local updates by enamining their respective equivalent formulations in this setting. To this end, we define: X(t) [2](()). (t), (T) (t), (x)(" (t)( (v)((=](tt) (f)) (f)() W(t + 1) 1 1 TV for I Tk, and W(1 +t++1) Iy for + + Tk. rk.

---

Published in Transactions on Machine Learning Research (03/2026)
Directly applying multiple local updates in EXTRA yields the following matriz form:
X(t + 1)++ IN X( (() - (X +aVxxxx)))
2
By defining Y(t) (x - - X(t) aVf(( 1))}, can verify that EXTRA is equivalent to the Sollowing form:
Y(+ + =t)
2a (IN - -VV---- (Y))))
(6)
X(++ () =X(t) -V
Similarly, by defining (t + 1) W(t () + (f(((t++] V with inital value (--1) v/(X(-1)), we can have an equivalent form of FedRecu as (see Lemena of Appendia B for the proof of equivalence)
1) ;
(7)
1))
From the equivalent formulation of our algorithm in 7 observe that our algorithm, FedRecu, applies the averaging matrix (t)) twice-once in updating the variable (t) and once in updating Y(t). In contrast, from the equivalent formulation of EXTRA in O,, one can see that EXTRA applies the averaging malric (t)) only once (to (t),, but not to (())) This double application of (t)) in FedRecu enforces a stronger consensus at each iteration, whereas EXTRA'S 's single application yields weaker consensus enforcement.
Under multiple local updates, where local-model drift naturally arises, maintaining consensus is crucial for effective drift correction. and accurate convergence. This difference explains why FedRecu provides strong convergence guarantees in the setting of multiple local updates (see Section 3.3) whereas EXTRA cannot. Numerical experiments in Appendix A.3 further corroborate this observation.
Remark 4. Based on the definitions in Remark 3 FedRecu can be expressed in the equivalent form given in W. To provide intuitive explanation for FedRecu, we will explain that Y(t) lu? (t), vo (t),... u. (t) is an estimate of the global gradient. Based on the deforition of ((), laking the network average gives
1(++ = V 1)) - VF(((t)).
where vf(((t)) = + EN vf((x(()) and y(t) = E (t).. The initial value setting Y(-2) = (-(((-2)) further implies
Y(I) V(((()))
Therefore, the average of (t)) coincides with the true global gradient at every iteration, and the consensus action of (t) ensures that all local yt( converge to this average. Hence, (t) is mathematically an accurate estimate of the global gradient. At each ileration, the local model parameters (i.e., x()) are updated based on the global gradient estimate (i.e., (t)) rather than the local gradients. This mechanism ensures that the local model porameters converge to the optimal solution of the global loss function, rather than to the optima of the individual local loss functions resulting from non-IID data.
3.3 Convergence Analysis under Deterministic Gradients
In this subsection, we analyze the convergence of FedRecu under both convex and nonconvex loss functions in the delerministic gradient case. We would like lo emphasize that the results apply to both the IID and non-lID data cases, as we do not require the local optima of f((x) to identical to the global optima of fxx) Given that the information exchange between clients and the parameter server occurs periodically, we characterize the convergence behavior of the model parameter at iterations when communication is conducted, Lee, i = kr.

---

Published in Transactions on Machine Learning Research (03/2026)
Theorem 1 (Convex and Deterministic Case). Under Assumption 1 and Assumption & if the loss function 8
f1(x) of client i E S is conver over Ie" and the stepsize salisfies 0 < S I3rL. then for any i E S, FedRecu guarantees that (Kzi(KT) converges to }( at a rate of o(1/K), i.e.
lim - = 0. K-000
Proof. See Appendix
Theorem I demonstrates that FedRecu effectively eliminates "client drifts" and ensures accurate convergence, Notably, we prove that FedRecu achieves convergence rate of o(/KK) for general convex loss functions, which is a significant improvement over the O(1/K) rate obtained cxisting results. In fact, to our knowledge, apart from Liu et al. (2026). FedRecu among the first algorithms to ensure o(1/K) convergenie for federated learning under general convex loss functions (note that o(I/K) convergence have only been gradient difference being uniformly bounded (Jiang et al., 2024), or Hessian difference being uniformly bounded (Kovalev et al. 2022 In addition, FedRecu supports much larger stepsize compared with existing federated-learning algorithms tackling "client drifts" (see detailed comparison in Table which, as confirmed in the numerical experiments, enables FedRecu to converge much faster than existing counterpart algorithms.
established in the literature under special convex conditions-sude
Under general nonconvex loss functions, FedRocu can also enable accurate convergence:
Theorem (Nonconvex and Deterministic Case). Under Assumption 1 and Assumption 8
2 if the stepsize
satisfies < a S 177L. then for any i S, the ilerates under FedRecu satisfy
[((aa(
13 (s(z,(0)) ((x'))
8
Proof. See Appendix
Theorem shows that even in the nonconvex setting, FedRecu can also avoid "client drifts" and ensure convergence to a desired solution. It is worth noting that the proposed stepsize range 0 < S ITFL is significantly larger than those permitted in existing federated--carrinng algorithms (sce Table 2 for detailed comparison).
8
Remark 5.
We have eslablished the convergence rales of o(1/K) and O(1KK) for FedRecu in the general convez case and the general nonconver case, respectively. In the special case where the global loss function f(x) j-strongly conver or satisfies the p-PL condition, following the presented proof techniques, the linear convergence of [<,((T))) f(x") con be direclly oblained with the proposed slepsizes in Theorem and Theorem 4 respectively-
Remark 6. Based on the reformulation in Remark 4 one can see that FedRecu is mathematically equivalent to maadient-rrccking-unn
algorithms that incorporate multiple local updotes. However, it is crucial note that FedRecu offers more than a mere equivalence. Specifically, it introduces several key advantages over conventional grudient-trucking methods, which we detail below.
Sharper Convergence Guarantee: A key theoretical contribution of FedRecu is the establishment of monotonicity property (see Appendir (): f<x,(K + T)) S (kx;()T)) Vi V, for general convez loss functions. Leveroging this property, we prove that FedRecu achieves o(1/K) con- vergence rate for general conver loss functions. This rate constitutes a strict improvement over the standard O(1/T) rate attainable by eristing mudieett-tracknng methods under general conver loss functions. To the best of our knowledgee oparl from Liu el al.) (2026), FedRecu is among the first fed- erated learning algorithms to guarantee o(1/K) convergence under general convex loss functions. Previous results establishing such o(1/K) ()) convergence rate must rely on stronger assumptions, such as uniformly bounded gradient differences [Jiang et al. 2024) or uniformly bounded Hession differences (Jiang et al.) (204))

---

Published in Transactions on Machine Learning Research (03/2026)
Memory Efficiency: To quantify memory overhead, measure the number of n-dimensional vectors that must. be stored, where n is the dimension of the model parameler. It is worth noling that we do not consider gradients since they can be computed directly using the model paremeters. In the standard gradient-tracking formulation, each client must maintain three n- n-dimensional vectors: the currenl model parometer, the previous model parameler, and an auziliary gradient- brucking vari- able. In contrast, the recursive formalation of FedRecu eliminates the explicit gradient- tracknnng variable. Consequently, each client in FedRecu needs to store only two n-dimensional vectors: the current and the previous model parameters. Therefore, this recursive design yields fundamen- tally more memory-efficiett algorithm by inherentlyy incorporating past gradient information into the variable.
local update rule, thereby obviating the need for a separate quriliary gradient-tracet
Communication Efficiency: In addition to memory efficiency, FedRecu also improves commani- cation efficiency compared with trudient-tracking-baee based algorithms. In each communication round, clients in our FedRecu only need to share a single n n-dimensional vector (a simple linear combination of model parameters and gradients) with the parameter server. In contrast, gradient-tracking- based algorithms require the transmission of two n-dimensional vectors: the model porameter and the grudient-tree trackingg variable.
3.4 Convergence Analysis under Stochastic Gradients
In this subsection, extend our analysis to the more practical setting of stochastic gradients (the mini-batch setting). In this case, the local loss function fz) is determined by
f((x) (f,.
(8)
where & denotes a stochastic data sample drawn from the local distribution D; of client i. As a result, client can only access a stochastic estimate ff(( E,) of the true gradient f((z) for any x E R", We use the following standard assumption regarding the stochastic gradient (Karimireddy et al. (2020) Mukherjee et al. (2023: ; Jhunjhunwala al. )2023)):
Assumption 3. The stochastic gradient fi Ei) is an unbiased estimate of the accurate gradient f.))), with ils variance bounded by o². Specifically, we have
D.. E.)] = Vf(()), and
for any x E Rd and i S.
In the stochastic gradient setting, the exact gradients Vf((z((t) and (f - 1)) of FedRecu should be replaced with their stochastic counterparts (,,,,,
respectively, where Ei(1) Dj are samples drawn from the local data distribution at each iteration. Next, we establish the convergence properties of FedReeu in this stochastic setting for both convex and nonconvex loss functions. Again, the results apply to both the IID and non-IID data cases, as we do not require the local optima of fa()) to be identical to the global optima of (xx)
and (1)
Theorem 3 (Convex and Stochastic Case). Under Assumption 1 Assumption and Assumption 3 if the
loss function f((x) of client E S is convex and the stepsize satisfies 0 < a GTL then for any i E S the iterates under FedRecu satisfy
(l]lz,()) x 121 +
3472a²
B
Σ (KT)
((x)) -((t)) (2ar 12- Lo²
K
2ar 12r La
k=
Proof. See Appendix G
Theorem 4 (Nonconvex and Stochastic Case). Under Assumption 1 Assumption and Assumption 3 if the slepsize satisfies 0 < a < I then for any i E S, the iterates under FedRecu satisfy
K K [[(()((()))]
(0)) - + at 1-- La [zz - 13 (2)
2
<
8

---

Published in Transactions on Machine Learning Research (03/2026)
Proof. See Appendix
Theorem 8 and Theorem show that, in the presence of noisy gradients, constant stepsize only ensure convergence to neighborhood of the optinal solution. The size of this neighborhood depends on the local update period T, the stepsize a, the smoothness constant L, and the variance o² of the stochastic gradients. Remark 7. In the stochastic gradient setting, FedRecu can still guarantee accurate convergence by adopting a diminishing stepsize. For instance, following similar line of reasoning in Theorem 3 and Theorem 4 one can easily obtain that setting a = O(1/VK) yields
K-1
K-1 (xT() - f(=²)= S (LIVVK), and K
E
f( K
Σ k=
for conver and noncoweer loss functions, respectively. However, despite ensuring accurate convergence, diminishing slepsize slows down convergence compored to the consland slepsize case.
4 Comparisons with Existing Works
In this section, systematically show that FedRecu has advantages in storage and communication overheads, stepsize, and convergences rates with respect to existing counterpart algorithms.
Table 1: Comparison the required memory and communicated messages between FedRocu and existing algorithms addressing "client drifts" in federated learning.
MEMORY OVERHEAD
COMMUNICATION OVERIEAD
ALGORITHM
STRONGLY CONVIX
CONVEX
NONCONVEX
T22
T=
This work"
2
2
3
2
1
MITRA ET AL.
2021B
3
4
2
2
K KARIMIREDDY ET
AT.
2020
4
5
5
2
2
MITRA ET AL.
202 LA
3
4
2
2
HUANG ET
(2023
4
2
2
HUANG ET AL..
(202
5
2
2
SUN & WEI
(0022)
4
2
2
To quantify memory overhead, mcasure the number of n-dimensional variables that must be stored, where is the dimension the model parameter. It. worth noting that not consider gradlents
since they can be computed directly using the model parameter.
2 To quantify communication overhead, we measure the number ve-dimensional variables shared after every
7 local updates.
3 The convergence result this work for the convex case relies on the last-iterate terms (see Theorem
contrast to the nonconvex setting, no running-averr
iterate needs to be stored.
4 Note that message compression addressed the paper is orthogonal to the message count-based baste commu-
nication efficiency discussed here.
4.1 More Efficient Memory and Communication
A significant advantage of FedRecu lies its memory-efficient design. Existing Sederated-leariing algorithms, such as SCAFFOLD (Karimireddy et al. 2020). FedLin (Mitra et al. 2021b), FedTrack (Mitra et al. 2021a), and Scaffnew (Mishchenko tracking variables, to address the "client-drift" problem. However, storing and updating these variables incur significant extra overhead in memory consumption. In contrast, FedRecu leverages recursive mechanism that naturally incorporates both current and past gradient information into the local update rule, eliminating the need for using auxiliary variables and resulting in reduced memory requirement (despite requiring to store the past model parameter).
al.] 2022 rely on auxiliary variables, such as control or gradient
In addition to memory efficiency, FodRecu also improves communication efficiency compared with existing counterpart algorithms. In each communication round, clients in our FedRecu only need to share a single n-dimensional vector (a simple linear combination of model parameters and gradients, vz(() and wx(() (1)
9

---

Published in Transactions on Machine Learning Research (03/2026)
in Algorithm 1 for details) with the parameter server. In contrast, existing federated- learning algorithms addressing "client drifts", such SCAFFOLDD, FedLin, and FedTrack, require the transmission of multiple variables. In fact, when T = I, FedRecu reduces to
1 N -0000--0(-))-////000000--0-- 1, +
this case, FedRecu only shares one variable between local clients and the parameter server each com- munication round, which reduces the communication overhead in SCAFFOLD, FedLin, and FedTrack by half. Table | provides detailed comparison of FedRecu with existing counterpart algorithms regarding memory and communication requirements.
Table 2: Comparison of allowable stepsizes and obtained convergence rates between FedRecu and existing lederated-learning algorithms (under local training steps)
CONVERGENCE
GRADIENT SETTING'
ASSUMPTION
ALCORITIM
STEPSIZE
RATE
L/(13TL)
o1/K)
EG
THIS WORK (ours)
1/(6rL)
O(L/K)
SG
MITRA ET AL.
(2021
L/(10rL)
O(/KK)
EG
CONVEX
KARIMIREDDY
2020
1/(81=L)
O(1/K)
SG
MUKHERJEE ET AL.
023
1/(20TL)
O(L/K)
SG
KHALED ET AL. 2020
1/(10rL)
O(L/K)
SG
QU ET 2021
00/VK)
O(L/VK)
SG
8/(17TL)
O(1/K)
SG
THIS WORK (ours)
1/(13rL)
O(/KK
EG
MITRA ET AL.
202 B
L)(26rL)
O(//K)
EG
MITRA ET AL.
2021
1/(18rL)
O(L/K)
EG
KARIMIREDDY ET AL.
2020
1/(24TL)
O(1/K)
SG
ALLOUAH FT AT..
2004
1/(16rT)
O(1/K)
SG
BRIKMOHAMMADI ET AL.
2025
NONCONVEX
HADDADPOUR & MAHDAVI
22019
YANG ET AL. (2021:: ZHU ET AL.
2021
Yu 2019:: CHENG
2024
0(1/VK)
O(LVKK)
SG
WANG ET AL. 2020 YAN ET AL.
2025
REISIZADEH ET (2020): Li & Li
(2023)
XIANG ET AT. (2024); HUANG ET AT..
(2023
KIM RT AL..
(2023
ADAPTIVE
0(1/VK)
SG
1 F.G denotes the exact gradient setting; SG denotes the stochastic gradient setting.
4.2 Improved Convergence Rates
FedRecu offers significant advantages in terms of convergence rates. Unlike many existing methods that are subject to steady-state optimization errors (see, e.g., JJunjhunnala et al. (2023); Wang et al. (2020):
Cho et al. (2020): Wang et al. (2021) ) or achieve a convergence rate of O(1 K) for general convex loss functions (see, e.g., Mitra et al. (022aa b); Karimireddy et al. (2020) Haddadpour et al. (2019)) ), FedRecu ensures accurate convergence al rate of o(1/K) for general convex loss functions. This contrasts sharply with existing results, which establish o(/KK) convergence only for special classes of convex functions such
as those with uniformly bounded gradient differences (Jiang al. 2024) or uniformly bounded Hcssian
differences (Kovalev et al. 2022
4.3 Larger Stepsizes
FedRecu allows larger constant stepsizes than existing counterpart algorithms that tackle "client drifts" in federated learning. While some prior methods exploit diminishing stepsizes to mitigate "client. drifts", this
10

---

Published in Transactions on Machine Learning Research (03/2026)
approach inevitably results in slow convergence and is not considered here. The stepsize comparisons are summarized in Table 2 Tt can be seen that FedRecu's stepsize can be at least 6, 8, 6, and 49 times larger than those used in Khaled et al. (2020), Mitra et al. (2021a), Mitra et al. (2021b), and Karimireddy et al. 2020 respectively.
5 Experiments
We evaluate our proposed algorithm by training a CNN on 10 clients using the benchmark datasets CIFAR- 10 and CIEAR-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 fully connected layer with 256 wnits and ReLU activation, dropout layer with a rate of 0.25 for regularization, and final dense output layer with 10 units that produces the class logits. In our experiments, we compare the proposed algorithm against existing federated learning methods specifically designed to address client drift, including SCAFFOLDD (Karimireddy et al.) 2020), FedLin (Mitra eet al. 2021b), and Scaffnew [Mishchenko et al., 2022). Following Hssu et al. (2019) and Kim et al. (0023) we generate heterogencous data distributions across the 10 agents using a Dirichlet distribution, with the heterogeneity parameter set to 0.1, 1, and 10, respectively. A higher value 3 yields a nearly uniform distribution of data across classes for each elient, resulting in approximately IID local datasots. In contrast, lower 8 leads highly skewed distributions, where clients tend specialize in only few classes,
Figures 1 and 2 report results for 3 = which corresponds to moderately heterogeneous setting. For all the stepsizes for FedReeu, SCAFFOLD. FedLin, and Scalfnew are selected according to the guidelines from Theorem [ Karimireddy el al. (2200) Mitra et al. 2021b), and Mishchenko et al. (2022), respectively, using an estimated smoothness parameter of L= For FedRecu, SCAFFOLD, and FedLin, the local training period is set to r 10. For Scaffnew, the communication probability is set to 1 to ensure that the total number of communicated messages remains consistent across methods. As shown in the figures, our algorithm achieves faster convergence and higher accuracy both the CIFAR-10 and CIFAR-100 datasets.
results shown in Figure (CIFAR-10) and Figure (CIFAR-100), (
Under the same experimental setup, we also conducted experiments with Dirichlet distribution parameters B = 0.1 (reflecting a high degree of heterogeneity). The results are presented Tigures|p 3 and is evident that FedRecu achicves a substantial speodup compared with the bascline methods. Additional experiments with Dirichlet distribution parameters 10 (reflecting a low degree of heterogeneity) and experiments for the least squares problem are presented in Appendix A which also confirm the effectiveness of our proposed algorithm.
Scaffnew
FedRecu
SCAFFOLD FedLin
TRact Accuracy
Train Accuracy
Scaftnew
Scaffnew
32
FedRecu
FedRecu
SCAFFOLD
FeoLin
FedLin
1500
1358
2030
Icea
1ss8
Communication
Communication Rounds
Communication Rounds
(a)
(b)
(c)
Figure 1: Comparison of FedReeu with state-of-the-art foderated learning algorithms SCAFFOLD, FedLin, and Scaffnew the CIFAR-10 dataset. Each curve represents the average of six independent runs. The Dirichlet distribution parameter was set to 3 = 1, which corresponds to moderate heterogeneity.
"ode available http:///wwaaaooo...oo../o//////a
11

---

Published in Transactions on Machine Learning Research (03/2026)
Scaffnew FedRecu SCAFFOLD
Fedlin
Test Accuracy
Train Accuracy
35
Scaffnew FedRecu SCAFFOLD
Scaffnew
FedRecu
25-
SCAFFOLD
Fedlin
FedLin
3506
3900
4350
2590 si0e
2990
Co Communicaten cation Rounds
Communication Rounds
Com munication Rounds
(b)
Comparison of FedRecu with state-of-the-art federated learning algorithms SCAFFOLD, FedLin, and Scaffnew- the CIFAR-100 dataset. Each represents the average of six independent runs. Note that the test accuracy in Figure 2(b) is top-5 accuracy. The Dirichlet distribution paramcter was set to B 1, which corresponds to moderate helerogeneily.
Figure 2:
17-
FedRacu
SCAFFOLD
14-
FedLin
Toct Tocuurocy
Train Accuracy
Scaffnew
Scaffnew
FedRecu
FedRecu
SCAFFOLD
SCAFFOLD
FeoLin
FedLin
2250
Communication Rounds
Communikallo Rounds
Communication Rounds
Figure 3: Comparison of FedRecu with state-of-the-art federated learning algorithms SCAFFOLD, FedLin, and Scaffnew the CIFAR-10 dataset. Each curve represents the average of five independent runs. The Dirichlet distribution parameter was set to 8 = 0.1, which corresponds to a relatively high level of heterogeneity.
Scaffnew
FadRecu SCAFFOLD FedLin
41-
Train Accuracy acy
Test Accurso
35-
0.2
ScafTnew
Scaffnew
25-
FedRecu SCAFFOLD
011
FedRecu
SCAFFOLD
FedLin
FedLin
3
268
1009 1000
2008
35M
3000
2006
1690
3099
1966
208
3000
2043 4300
500
1000
150
4006 2008
2500
3006
2500
Communication Rounds
Communication Rounds
Communication Rounds
(b)
(c)
Figure 4: Comparison of RedRecu with state-of-the-ard federated learning algorithms SCAFFOLD, FedLin, and Scaffnew on the CIFAR-101 100 dataset. Each curve represents the average of three independent runs. Note that the test accuracy Figure 2(b) is top-5 accuracy. The Dirichlet distribution parameter was set to 3 = 0.1, which corresponds to a relatively high level heterogencity.
12

---

Published in Transactions on Machine Learning Research (03/2026)
6 Conclusion
We have proposed FedRecu, novel recursion-based algorithm that can address "client drifts" in federated learning. Different from all existing federated- algorithms that have to employ auxiliary variables to estimate the global gradient or the amounts of drift. from it, the novel recursion-based architecture of our algorithm enables climinating "client drifts" without introducing any auxiliary variables. This climination of auxiliary variables enables our algorithm to significantly reduce the communication overhead and memory requirement in combating "client drifts" in federated learning. The novel architecture also enables employing larger constant stepsizes than existing counterpart algorithms with drift correction, resulting in much faster convergence. We provide rigorous convergence analysis of the proposed algorithı under both convex and nonconvex loss functions, in both the deterministic gradient case and the stochastic gradient case. Notably, we prove that FedRecu guarantees an K) convergence rate under general convex loss functions, improving upon the existing federated learning literature, which achieves this rate only under restricted convex scttings with heterogeneily consts Numerical experiments further confirm that FedRecu converges faster than existing counterpart algorithms that can tackle "client drifts."
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 N Whatmough, and Venkatesh Saligrana. Federated learning based on dynamic regularization. arXiv preprinl arXiv:2111.04263, 2021.
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. cpSGD: Commuicctionn-fffcientt and differentialll-priiate distributed SGD. In Advances in Neural Infor- malion Processing Systems, volume 31, pp. 7564 7575, 2018.
Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, Geovani Rizk, and Sasha Voitovych. Byzantin federated learning: Impact of client subsampling and local updates. arXiv preprint Xrx:222402. 12780, 2024.
Ali Beikmohammadi, Sarit Khirirat, and Sindri Magnússon. On the convergence of federated learning algorithms without data similarity. IEEE Transactions on Big Data, 11(2):659 668, 2025.
Zachary Charles and Jakub Koncčný. On the outsized importance of learning rates in local update methods. arXio preprinl ar (xXxx:2007.00077 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 2021.
Mingzhe Chen, Zhaohui Yang, Walid Saad, Changchuan Yin, H. Vincent Poor, and Shuguang Cui. A joint learning and communications framework for federated learning over wireless net works IEEE Transactions on Wireless Communications, 20(1):269-29) 283, 2021.
Ziheng Cheng, Xinmeng Huang, Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. arXiv preprint arXix:2306. 16504, 2023.
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 Representations, 2024.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategies. Xixio preprint ar arx:::2000000 249, 2020.
13

---

Published in Transactions on Machine Learning Research (03/2026)
Jian-hui Duan, Wenzhong Li, Derum Zou, Ruichen Li, and Sanglu Lu. Federated learning with data-agnostic distribution fusion. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recog- nition, pp. 8074 8083, 2023.
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 Slatislies, pp. 9050 9090, 2022.
Samyak Gupta, Yangsibo Huang, Zexuan Zhong, Tianyu Gao, Kai Li, and Danqi Chen. Recovering private text in federated learning of language models. In Advances in Newral Information Processing Systems, volume 35, pp. 8130-8143, 2022.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint arXiv:1111 1911. 14425, 2019.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, volume 32, pp. 11082 11094, 2019.
Chaoyang He, Keshav Balasubramanian, Emir Ceyani, Carl Yang, Han Xie, Lichao Sun, Lifang He, Liangwei Yang, Philip S Yu, Yu Rong, et al. Fedgraphnn: A federated learning system and benchmark for graph neural networks. arxie preprint urXiv:2104.0711 2021.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXic: 1909.06359, 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-10000 -40599, 2023.
Xinmeng Huang, Ping Li, and Xiaoyun Li. Stochastic coutrolled averaging for federated learning with
communication compression. In International Conference on Representation Learning, pp. 27956-27994 2024.
Divyansh Jhunjhunwala, Shiqiang Wang, and Gauri Joshi. Fedexp: Speeding up federated averaging via extrapolation. arXiv preprint (al::3301.00044, 2023.
Xiaowen Jiang, Anton Rodomanov, and Scbastian U Stich. Stabilized proximal-point methods for federated optimization. Advances in Neural 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 foderated learning. In Pro- ceedings of the 37th International Conference on Machine Learning, volume 119, pp. 5132 5143, 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, 2020.
Latif U. Khan, Shashi Raj Pandey, Nguyen H. Tran, Walid Saad, Zhu Han, Minh N. Н. Nguyen, and Choong Scon Hong. Federated learning for edge networks: Resource optimization and incentive mechanism. IEEE Communications Magazine, 58(10):88 93, 2020.
Junhyung Lyle Kim, Mohammad Taha Toghani, César A Uribe, and Anastasios Kyrillidis. Adaptive feder- ated learning with auto-tuned clients. arXiv preprint arXiw:2906.11 11201, 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, 15:33494-33500 2022.
14

---

Published in Transactions on Machine Learning Research (03/2026)
Ching-Pei Lee and Stephen Wright. First-order algorithms converge faster than o(1/k) on convex problems. 2019.
In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang, On the convergence of fedavg on non-iid data. arXiv preprint arXi::1907.02189, 2019.
Xiaoyun Li and Ping Li. Analysis of error feedback in federated non-convex optimization with biased com- pression: Fast convergence and partial participation. In International Conference on Machine Learning, pp. 19638 19688, 2023.
Zexi Li, Tao Lin, Xinyi Shang, and Chao Wu. Revisiting weighted aggregation in federated learning with neural networks. In International Conference on Machine Learning, pp- 19767-19788, 2023.
Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao, Ying- Chang Liang, Qiang Yang, Dusit Niyato, and Chunyan Miao. Federated learning in mobile odge networks: comprchensive survey. IEEE Communnicationss Surveys & Tulorials, 22(3):2031 2063, 2020a.
Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao, Ying-Chang Liang, Qiang Yang, Dusit Niyato, and Chunyan Miao. Federated learning in mobile edge networks: A comprehensive survey. IEEE Communications Surveys & Tutorials, 22(3):2031 2031-23333 2020b.
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 lasks. arXiv preprint arXiv:2144.08815 2021.
Jie Liu, Zuang Wang, and Yongqiang Wang. Achieving faster than O(1/t) convergence in general convex federated learning. Transactions on Machine Learning Research, 2026.
Ming Liu, Stella Ho, Mengqi Wang, Longxiang Gao, Yuan Jin, and He Zhang, Federated learning meets natural language processing: A survey. arXiv preprint arXiv:2107. 12609, 2021.
Wei Liu, Li Chen, Yunfei Chen, and Wenyi Zhang. Accelerating federated learning via momentum gradient descent. IEEE Transactions on Porallel and Distributed Systems, 31(4):1754-1766, 2020.
Bing Luo, Xiang Li, Shiqiang Wang, Jianwei Huang, and Leandros Tassiulas. Cost-effective federated learning in mobile edge networks. IEEE Journal on Selected Areas in Communécations, 39(12):3606 3621, 2021.
Pouya M Ghari and Yanning Shen. Personalized federated learning with mixture of models for adaptive prediction and model fine-tuning. Advances in Neural Information Processing Systems, 2024.
Chuan Ma, Jun Li, Ming Ding, Howard H. Yang, Feng Shu, Tony Q S. Quek, and H. Vincent Poor. On safeguarding privacy and security in the framework of federated learning. IEEE Network, 34(4):242-248, 2020.
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. 6692 6701, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. CommuniicttinnEEfiiiii Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pp. 1273 178-2 2017.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: 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.
15

---

Published in Transactions on Machine Learning Research (03/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.
Sohom Mukherjee, Nicolas Loizou, and Sebastian U Stich. Locally adaptive federated learning. arv preprint arXiv:2307.0633 2023.
Solmaz Niknam, Harprect S. Dhillon, and Jeffrey H. Reod. Federated learning for wireless communications: Motivation, opportunities, and challenges. IEEE Communications Magazine, 58(6):46 51, 2020.
Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Scbastian U Stich, Ziheng Cheng, Nirmit Joshi, and Nathan Srebro. The limits and potentials of local sgd for distributed heterogeneous learning with intermittent communication. In The Thirty Seventh Annual Conference on Learning Theory, pp. 4115-4157, 2024.
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.
Tiancheng Qin, S Rasoul Etesami, and César A Uribe. Faster convergence of local sgd for ver-parameterized models. arXiv preprint orXiv:2201.12111 2022.
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.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-effiienn federated learning method with periodic averaging and quantization. In Pro- ceedlings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pp. 2021 2031, 2020.
Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2):944 966, 2015.
Zhenyu Sun and Ermin Wei. A communicaiion-fficcentt algorithm with linear convergence for federated minimax learning, Advances in Neural Information Processing Systems, 35:6060 6073, 2022.
Nguyen H. Tran, Wei Bao, Albort Zomaya, Minh N. H. Nguyen, and Choong Scon Hong. Federated learning over wireless networks: Optimization model design and analysis. In IEEE INFOCOM 2019 IEEE Conference on Computer Communications, pp. 1387- 1395, 2019.
Yeshwanth Venkatesha, Youngeun Kim, Leandros Tassiulas, and Priyadarshini Panda. Federated learning with spiking neural networks. IEEE Transactions on Signal Processing, 69:6183 6194, 2021.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the objective incon- sistency problem in heterogeneous federated optimization. In Advances in Neural Information Processing Systems, volume 33, pp. 7611 7623, 2020.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. A novel framework for the analysis and design of heterogeneous federated learning. IEEE Transactions on Signal Processing, 69:5234-5249, 2021.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Memahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-10343, 2020.
Ming Xiang, Stratis loannidis, Edmund Yeh, Carlee Joe- Joe-Wonn Wong, and Lili Su. Efficient federated learning against heterogencous and non-stationary client unavailability. Advances in Neural Information Processing Systems, 17:104281-104322 2024.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. Xiu preprint arXiv:206.. 10874, 2021.
16

---

Published in Transactions on Machine Learning Research (03/2026)
Wenjing Yan, Kai Zhang, Xinolu Wang, and Xuanyu Cao. Problem-parameter--ne federated learning. In The Thirleenth International Conference on Learning Represenlations, 2025.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-lID federated learning. arXiv preprint 0rXw:2101.11203, 2021.
Howard H Yang, Zuozzuu Liu, Tony QS Quek, and H Vincent Poor. Scheduling policies for federated learning in wireless networks. IEEE Transactions on Communications, 68(1):317 333, 2019.
Zhengjie Yang, Wei Bao, Dong Yuan, Nguyen H. Tran, and Albert Y. Zomaya. Federated learning with nesterov accelerated gradient. IEEE Transactions on Parallel and Distributed Systems, 33(12))4963-4773 2022.
Rui Ye, Rui Ge, Xinyu Zhu, Jingyi Chai, Yaxin Du, Yang Liu, Yanfeng Wang, and Siheng Chen. Fedllm- bench: Realistic benchmarks for federated learning of large language models. In Advances in Neural Information Processing Systems, volume 37, pp. 111106-111130, 2024.
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 AAAI conference on artificial intelligence, volume 33, pp. 5693-5700, 2019.
Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in Neural Information Processing Systems, 33:5332 5344, 2020.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nomparametric federated learning of neural networks. In International conference on machine learning, pp. 7252-7261, 2019.
Ligeng Zhu, Hongzhou Lin, Yao Lu, Yujum Lin, and Song Han. Delayed gradient averaging: Tolerate the communication latency for federated learning. In Advances in Neural Information Processing Systems, 2021.
volume 34, pp.
A Additional Numerical Experiments
A.1 Additional CNN Training Results with A Different Non-IID Level
Additional CNN training experiments on the CIFAR-10 and CIFAR-100 datasets are presented in Figures 5 respectively, using a non-llD data distribution characterized by a Dirichlet distribution with hetero- geneity parameter 3 10. The other setup is the same as that presented in Section 5.
and G
Scaffnew
FedRezu
35-
SCAFFOLD
FedLin
Tort: Accuracc
Train Accuracy
0.5
0006
1..
Scaffnow FedRecu
6..
Scaffnew
42-
FedRecu
18-
FedLin
FedLin
34-
204
Communication 1990
Communication
Communication
(a)
(b)
(c)
Figure 5: Comparison of FedRecu with state-of-the-art federated learning algorithms SCAFFOLD, FedLin, and Scaffnew using their prescribed stepsizes on the CIFAR-10 dataset. Each curve represents the average of five independent runs. Each curve represents the average of three independent runs. Note that the test accuracy in Figure 5(b) is top-5 accuracy. The Dirichlet distribution paraneter was set to 10, which corresponds to relatively low level of heterogencity.
17

---

Published in Transactions on Machine Learning Research (03/2026)
Scaffnew FedRecu SCAFFOLD
9.-
FedLnn
Test Accurocy
Train Accurscy
30.
62.
ScafTnew SCAFFOLD
Scaffnew
SCAFFOLD
sle usea isfo
2008
iáe 2000 xãde
<600
Lske
Zee
aalo
2048 460
Uso
adoo
adke
2áo0 4x0
Communication Rounds
Communication Rounds
Communication Rounds
(b)
(c)
Figure 6: Comparison of FedRecu with state-of-the-arr federated learning algorithms SCAFFOLD, FedLin, and Scaffnew using their prescribed stepsizes the CIFAR-100 dataset. Each curve represents the average of three independent runs. Note that the test. accuracy in Figure 6 () is top-5 accuracy. The Dirichlet distribution parameter was set to B = 10, which corresponds to a relatively low level of hetcrogeneity.
A.2 Comparison of FedRecu, SCAFFOLD, FedTrack, and FedLin Using Their Best-Found Stepsizes for CNN Training
Additional CNN training experiments on the CIFAR-10 dataset are presented in Figure 7 using non- IID data distribution characterized by a Dirichlet distribution with different heterogeneity parameters 0.1, 1, In Figure we compared the convergence of FodRocu with SCAFFOLD (Karimireddy et al., 2020), FedLin (Mitra al., 2021b), and FedTrack (Mitra al.) 2021a) using the best-found stepsize for each algorithm. These experiments show that our algorithm achieve faster convergence than the competing methods. These results confirm the effectiveness of the proposed algorithm.
FedLin
FedLin
FedLin
FedRecu
FedRecu
FedRecu
304
FedTrack SCAFFOLD
FedTrack
FedTrack
SCAFFOLD
SCAFFOLD
16.
50
1.4
10
3750
200e
3750
25a
3990 tthe
Number of Shared Messages
Number of Shared Messages
Number of Shared Messages
(a)
(b)
(c)
Figure 7: Comparison of FedRecu with statc-of-the-art federated learning algorithms SCAFFOLD, FedLin, and Fed'Track under their respective best-found stepsizes on the CIFAR-10 dataset. Each curve represents the average of six independent runs. To study different heterogeneity in data distribution, the Dirichlet distribution parameter was set 0.1, 1, 10 for Figures (a), (b), (c), respectively. The results demonstrate that our proposed FedRecu achieves significant speedup compared these baseline methods.
A.3 Comparison of FedRecu and EXTRA for CNN Training
Additional comparison between FedRocu and EXTRA Shi et al. 2015 on the CIFAR-10 datasct are pre- sented in Figures 8 and 10 respectively, using non-lID data distributions generated by Dirichlet. partitions 0.1, 1, 10, respectively. For both FedRecu and EXTRA (Shi et al. 2015). the local training period is to 10 and the stepsize a 0.1. As shown Figures 8 and 10 FedRecu achieves convergence, whereas EXTRA fails converge. These numerical results further support the statement in Remark 3 that FedRecu allows larger stepsize than EXTRA.
with heterogeneity parameters
18

---

Published in Transactions on Machine Learning Research (03/2026)
27
67-
24
Test Accurory
Train Accuracy cy
EXTRA
FedRecu
FedRecu
FedRecu
14.
Communication Rounds
Communication
(b)
(c)
Figure 8: Comparison of FedRecu with EXTRA on the CIFAR-10 10 dataset. Each curve represents the average of six independent runs. To induce greater hetcrogencity in data distribution, the Dirichlet distribution parameter was set to B 0.1.
Movilyy wemm Anngpon
28-
Test Accuraty
2.5
Train Accuracy
1005
EXTRA
EXTRA
84
11-
EXTRA
FedRecu
de
toke 1250 Lode
1960
2ide
1250 Communication Rounds
150
1009
1789
3750
590
de
sike
ubo 1he
1756 2003
Communication Rounds
Communication Rounds
(a) Figure 9: Comparison of FedRecu with EXTRA the CIFAR-10 dataset. Each curve represents the average of six independent runs. To induce greater hetcrogeneity in data distribution, the Dirichlet distribution parameter was set to B
(b)
(c)
Test Accurscy
Train Accuracy
0.
Lo55
FedRecu
FeoRecu
2.4
Mymnn Www.-A Sateee
62.
EXTRA FedRecu
Communication
Communication
Communication
(a)
(b)
(c)
Figure 10:
Comparison of FedRocu with EXTRA on the CIFAR-10 dataset. Each curve represents the average of six independent runs. To induce greater heterogeneity in data distribution, the Dirichlet distri- bution parameter was set to = 10.
A.4 Comparison of FedRecu, SCAFFOLD, SCAFFOLD-M, Scaffnew, and FedLin for CNN Training
Additional CNN training experiments on the CIFAR-10 datasct are presented in Figures 12 and
respectively, using non-IID data distributions generated by Dirichlet partitions with helerogeneity parameters
3 = 0.1, 1, 10, respectively. The stepsizes for FedRecu, SCAFFOLD, SCAFFOLD-M, FedLin, and Scaffnew are sclected according to the guidelines from Thcorem 1 Karimireddy al. (2020). Cheng al.) (2023). Mitra et al. (2021b), and Mishchenko of T. = 2. For FedRecu, SCAFFOLD, SCAFFOLD-MM and FedLin, the local training period is set 10.
(2022), respectively, using an estimated smoothness parameter
19

---

Published in Transactions on Machine Learning Research (03/2026)
For Scaffnew, the communication probability is set to i ensure that the total number of communicated messages remains consistent across methods. These experiments in Figures algorithm can achieve faster convergence than the competing methods.
12 and
13
show that our
Scaffnew
FedRecu
SCAFFOLD
FedLin
Test Accurscy
Train Accuracy
SCAFFOLD-M
Scaffnew
Scafmew
FedRecu
FedRocu
SCAFFOLD
SCAFFOLD
18-
FedLin SCAFFOLD-M
FedLin
SCAFFOLD-M
700 1o0s 2250 Lo0e 1750 2006
150
1009
1200
3750
22c
500 75
2006
125
10k
1756
Communication Rounds
Communicaat on Rounds
Communication Rounds
(c) Figure 11: Comparison of FodRocu with state-of-the-art federated learning algorithms SCAFFOLD, SCAFFOLD-M, FedLin, and Scaffnew- the CIFAR-10 dataset. Each curve represents the average of six independent runs. Note that the test accuracy in Figure [i(b) is top-5 accuracy. To induce greater heterogeneity in data distribution, the Dirichlet distribution parameter was set to B = 0.1.
(a)
(b)
Scaffnew
22-
FedRecu
SCAFFOLD
Test Accuraoy
Train Accuracy
SCAFFOLD-M
Scaffnew
Scaftnew
12-
SCAFFOLD
SCAFFOLD
18-
FedLin SCAFFOLD
FedLin
SCAFFOLD.M
20
520 de
like 2250 Like 1793 2006
26
23
10:9
1568
3750
2008
25
503
sice
Laka
Lise
2003
Communication Rounds
Communicaa on Rounds
Communication Rounds
(c) Figure 12: Comparison of FedRecu with state-of-hhe-art federated learning algorithms SCAFFOLD. SCAFFOLD-M, FedLin, and Scaffnew the CIFAR-10 dataset. Each curve represents the average of six independent runs. Note that the test accuracy in Figure [2 is top-5 accuracy. To induce greater heterogeneity in data distribution, the Dirichlet distribution parameter was set to 3 =
(a)
(b)
Scaffnew
FedRecu
SCAFFOLD
FedLin
Train Accuracy
SCAFFOLD-M
Bozz Acccura
16
Scaffnew
Scaffnew
14.
SCAF
SCAFFOLD
FedLin
SCAFFOLD.M
SCAFFOLD-M
1791 L9k 1991 2ire
1808 xaln
19e8
17.0
2008
xile 1991 15m the
Communication Rounds
Communication on Rounds
Communication
(a)
(b)
(c)
Figure 13: Comparison of FedRecu with stale-of-the-ar federated learning algorithms SCAFFOLD. SCAFFOLD-M, FedLin, and Scaffnew- on the CIFAR-10 dataset. Each curve represents the average of six independent runs. Note that the test accuracy in Figure (3(b) is top-5 accuracy. To induce greater heterogencity in data distribution, the Dirichlet distribution parameter was set to 3 10.
20

---

Published in Transactions on Machine Learning Research (03/2026)
A.5 Additional evaluation results using least squares regression
We also used the following least squares regression problem to evaluate the convergence performance of the proposed algorithm
1 N
min f(x)
min EER
Σ 2
-bil1,
(9)
#ER"
where A, R050010 b. 10 x E R10 and n is set 20. We consider [A.]gx and [be], generated from [0. 1] randomly for 1 S S and k
We compare algorithm with existing federated algorithms that can tackle "client drifts," includ- ing SCAFFOLD (Karimiredly et al. 2020), FedLin (Mitra et al. 2021b), and FedTTrcck (Mitra et al. 2021a
The stepsizes for FedRecu, SCAFFOLD, FedLin, and FeacTrack are selected based on the guidelines provided in Theorem Karimireddy et al. 2020), Mitra et al. (2021b). and Mitra et al. (2021a), respectively. We use
the convergence error (=((k)) f (x") where z(kT) ト 2i=1 (KT),,, to quantify the learning accuracy of each algorithm. We implement all algorithms using accurate gradients for fairness. Figure [4 illustrates the convergence errors of all algorithms under different local training periods t = 4, 8, 12, 16, respectively. These numerical results clearly confirm that FedRocu achioves much faster convergence than SCAFFOLD, FedLin, and Fed across all lested settings despite its reduced overhead storage.
f(xkr)) f(at)
f(((kr) Ract
SCAPFOLD
SCAFFOLD
FedTrack
FedTrack
FedLin
FedLin
FedRecu
RedRecu
106
1.20
1.50
152
100
120
160
10"
10
fxxke) ffaxt)
fx(ke)) -f(x))
SCAFFOLD
SCAFFOLD
FedTrack
FedTrack
FedLin
FedLin
FedRecu
FedRecu
r == 12
7 16
Figure 14: Comparisons FedRecu with SCAFFOLD Karimireddy et al.} 2020 FedLin Mitra et al.
2021b), and FedTrack (Mitra et al. 2021a) under different. local training periods
B
Supporting Lemmas For the Proof of Theorem 1
Lemma 1
Lee & Wright 2019 ). Let (A(()} be nonnegative sequence satisfying the following conditions:
(1) (A(1)
is monolonically decreasing;
2Code available at http:///mmmayooooooooo.mm/////ts
21

---

Published in Transactions on Machine Learning Research (03/2026)
(2) (A(t)} is summable, that is, Ex=o (k) <c. Then, we have (tt) = o(1/t,, L.., lim (t(t) = 0.
Lemma 2. Algorithm can be equivalently expressed in the following matrix form:
ki + = + -j - ao + j- 1), lkt + (kT + - 1) f. j)) ())
(10)
+j 1)).
for any j 1,2,
Proof. For the convenience of expression, (((2)())), (0) and
define X(t)
(=F()),5((0...... vf(()
ININ No
1+1= =k,
1)
N
(11)
I. t+1#10 th.
Thus, Algorithm 1 can be rewritten as the following matrix form:
-2 + - -
+ ta ( (WW(///))))
(12)
Rearranging the terms of 12
arrive at
(U x(0}
+ + - -V/0///00010001111---1--------})
(13)
Defining
Z(t) 1)x(t))((())----))) (X(
we can obtain
((t)
- 1)Z(( () W ()t - 100p::/:--777-----------///-0--- -
-
(14)
based the structure of
13
From 11b and
12
construct (t) satisfying
7(1) W()+)))(()
Thus, from 13 and
14
we have
W(+ -W---------OO-------------------
From the definition
11
of W(), we have
X(t) =W(f)X -) -)
(() (( - -))+ -
where Y(t) (y) (10.2200 (t),
v2 (T)T, which completes the proof.
Lemma 3 Mitra et al. (201bb)). Suppose [i(x) L-smooth and convex. Then, for any S a S 1 we
have
w--r-a(Vfll - s ll - æ|1
for any xr, y E T
22

---

Published in Transactions on Machine Learning Research (03/2026)
Lemma 4. For any & O, have
vi(k)) (x(()(
(15)
for any E S.
Proof. We use mathematical induction to prove Lemma It is clear that the relation holds for k = 0.
Next, we assume that the relation holds at time instant k, i.e.,
1 N
(k (((x)()TT) = N (k)()))
Σ
(16)
and prove that the relation also hold at time instant & ++1 1.
Using Lemma 2 we can obtain the following relation based on 16
Vk + 1) yi(k)) + (ia 1)) (i(()(())).
(17)
Similarly, for any j 1,2,
1, obtain
vi(kT + sk(k)) + (Ki ()) -((=0)())
Thus, we have
(18)
Using Lemma
leads
likk + T)
j=1
Therefore, we have
1 N
Vkkk + =
N
j=1
N
1
((((z((T++)))
1=1
where the first and second equalities follow from (6 and 18 respectively. Namely, the relation in the lemma statement also holds at time instant h + 1, which completes the proof.
Lemma 5. For 0 S < and 0 < aL < 1, we have
|KT: + Solluat
Proof. From Lemma we obtain
|k:(kT + + - (kT))
= [kT + 1;;(k ((u( Vflla,(k + - ((((=,(kT)))]
From the above equation and Lemma 3 we have
(kT + j + 1) - (kT) < (kT +) - zz (kT) (kl))
which further implies
(KT + + xz (KT))l (all)a(k)]]1
for any 0 5 < T.
23

---

Published in Transactions on Machine Learning Research (03/2026)
C
Proof of Theorem 1
From Lemma
we have
N
Ty (KT +T)
nz 1i +T- oxys(k +T 1)}
(19)
N
N
1
y: (KT + =
(20)
N
Thus,
10
implics
r-2 Vyi hh).
T; (KT +
1) (kT) a Σ
h=0
From the above equation and
19 we have
By (KT + k))
1 (,, - Σ
2ky + +1)
(21)
h=0
which, in combination with 20
yields
N N
Iz (Ko + k)
(KT) Σ (k)( + V + -V)
(22)
h=0
Lemma and 22 imply
<e(kr + k)) =xT)))
[5 h))
(23)
N
From 23
we have
[kxT kb) x1 [|xx(kT) x=1
N
N
= - 2(
a
(K 11),, -x)) +
a
Σ
+
N
N
k=
h=0
Then, using Assumption and the convex property of fa(x), we can obtain
2
V (k) x*)
N
20
-
N
20
(z(5((kT) + I. 112z((k
11 + h) - =k7))1
+
N
1=
24

---

Published in Transactions on Machine Learning Research (03/2026)
which further implies
2
+k)) x²))
h=0
20
(1(²*) - (25
20
h)) -5(os(kT))
N
N
j=1
h=0
al.
N
(kx( + h) - n4 (kT) 112
N
j=1
h=0
Combining Lemma and Lemma
we arrive at
N
2
v (a((t + ())) - -x")
h=0
7-1
<2aT(f(0 - f(aa()T)) + La
Σ h2 (V)( Am0
which further implies the following relationship based on Assumption
|/ ΣΣΣ L ()) (10 N
(
The above incquality, Lemma and the condition 0 < arL S 1 imply
3 -
(kT
[V
(24)
2
Thus, we can obtain
(kT + k)) x²
2=1 1| |1, - 2' -
(25)
where A₁ Lo 1 12 3 )a
From 23 and Assumption I we have
f(r
1
-((
-
(kT hh)) h)))
LLL
Σ
(1 +))l
2
==
From
24 Lemma and Lemma
5 we have
f(I,(kT+T))
a²I(3T -1)2
<f(x;(AT)) - aT [[(x{(())))
| ((x
8
a² T2I [V
which further implies
[az(kT + 7)) <[(x((kT)) + { LL2 - 1)2
a² -1]
aT [I]
2
25

---

Published in Transactions on Machine Learning Research (03/2026)
Thus, if < 1377 holds, we have
a² L(3 - a² 1(3--11) 1)²
at < 0.
8
2
Combining the preceding two relations yields that there exists > such that
>| [ s [(xikT 7)) (xi(kT))
(26)
holds under 0 < a S 1327
From 25 we have
20T (Jxi(k))))) - ((x')) s =1)(())) - x01 11
[,, + k) x²1
A1
(f(2,(kT + f(e,)((
for any E S. Thus, obtain
- f(x))} co.
(27)
From 26
27
and Lemma
we have
lim -(f(z((k))- 0,
which completes the proof.
D Supporting Lemmas for the Proof of Theorem 2
Lemma 6. For 0 2 have
[x,(kT xx,(k))]] 2ja (x;
(28)
for any 0 S <T.
Proof. From 314, we can obtain
| +J +j++1 (kT)
= =kk + + - xz (ATT) a(vi(k))+++ (f((x,(kT+))) - ((((),()))))
(29)
Combining 29 and Assumption 1
implies
||x,(kr + + 2, & (1 aL) +5) 2,(k)) + (kr)))
(30)
Next use mathematical induction to prove the lemma.
We first assume that (28) holds for 0 O
|k, + + x (KT))l < 2ja]lu
for any e S and 0 Aijss-1 Then, we will prove that 28 also holds for j 1.
Combining the above inequality and 30 implies
| + j + 1) z. (KT) < (2j 2oLj 1)o(llu
If a stepsize satisfies 0 < a S IF,.
I we have
IkT, + j + 1) (k())] <(2j + 2)al((
which completes the proof.
26

---

Published in Transactions on Machine Learning Research (03/2026)
E
Proof of Theorem 2
From Appendix
for any j = 1,2,
1, we have
(KT + +) = ciT +j 1) - agi(kT +j- 1),
Vit + +) = Vi( + - 1) + -
(31)
vi(kT + (kTT + (k, + j]) - (V)(()(kT))-
Moreover, from Lemma
we have
(i(K)) = (x(x;((T))
(32)
for any E S.
Combining 31 and 32 implies
N 8-1
x. (KT + k.) = =,(TT)
Σ
(33)
N
f=1k=0 k=0
for any E S.
From Assumption
!
we have
(2z(k
h1)ll
L
j=1 h=
j=1
From
32
Lemina
G
and 0 < a S
I we have
I
1
3
Vf((e((t++h)l
(34)
2
j=1
Combining Assumption and
13
implies
1 N T-1
f(x:(kT + +)) (
Σ
(k((t,(k++h))
N
a²1
Σ
(k(k
f=1 h=0
From the above inequality and Asumption
1 we arrive
a LLL - 112
f(a,(kT 7)) (/([6r)))))///[((((((((((11) +
V (KT)))1
8
T-1
a +
Σ 2h.
h=0
The above inequality and 34 imply
( aa [a2 -12 + + - 1) ((/))))))))
[<x(kk + +)) < (k,() +
Tf the stepsize satisfies 0 0<a5 < 1 we can obtain
LLL + LTL((( 5 0,
27

---

Published in Transactions on Machine Learning Research (03/2026)
i.e.
a3 1) a² I - 1) 2 0,
8
where 7 13ax Lr Lr 8
Thus, combining the preceding three relations yields
[VV[<<((+))]]] & [(x((k))) (2i + +T);
and hence
K K k=
[[[x) < f(x:(0)) - (ai((TT)) f(x:(0)) - -(xx)
7K
for any i E S.
F Supporting Lemmas for the Proof of Theorem 3
Lemma 7. Under Assumption ! and Assumption 2 if the loss function f((x) of client E S is conver, we
have
E [k + h) [xTT)] s 12r² La f(x;((T))- f(x*) 27Ta2o²
for 0 E h < and i e S.
Proof. From
39 and 40 we have
(kT + + 1) (kT +5) - aaf N
Σ
(k(()((T)) - (x(a((T))) + (K5 (k))) ==1
i.e.,
(,T + + - =xx(kT)
(kT +) - (kT) - a
1
- + (z V/y(((( 1))
N
N
N
N Σ () - N
Σ
(((T)))) -x(x((kT))
1=1
+ (z (f
Further using Assumption yiclds
E
bz kTr + + v, (A:T) )1
E
2. (KT + 5) 2x(k) a (
Σ
Vf (((((((k))) + (Z + +))) +)) []]
N
j=l
N
+ a 2
N Σ (x(()((T))
v ( + ( (k((k)
N 1=1
+ (g -)) - (1 j)) ;)){ [1]
(35)
28

---

Published in Transactions on Machine Learning Research (03/2026)
For the first term of the right hand side of (35 using the incquality
||a b112 < (1 + e)||a|1 + (1 +1+ 1 111b1
and Lemma
3 yields
N
E
2, (KT + + - 2 a
v (z)( - + (z +
N 1=1
<1 ||||| (KT + (kT) | + (1 + e) E (
(36)
for any e under a stepsize satisfying 0 < aL S 1.
For the second term of the right hand side of 33 we have
1 (fz(z,(kT) + + -V(a(()))-
E
Σ (o(o)((T)))
N
+ gg + j)) f + و)
N (2lg)(2,(kTt) +/
+ 3R (0g (kT + 1))
(k) + 1111
(37)
for any E S. Using Assumption
and
37
leads to
1
B
9 (kg(k)))
(x(x;((TT)
N
V5 + )>> 2902
(3 (KT + 1))
(38)
for any i S.
Combining 35
36
and
38
we can obtain
E x j 1) x. (1+))1
<(1 + 1 Bl|l= + 5) (KT)) (1 (40+://))H-(H-0////////////1)111 9022
Moreover, for any 0 S < T, we can obtain
(1 22
L lkt(kT + x (KT)) s ( ((
(1+
Selecting <= r implies
E [ + (KT)|| < L La ((+) -77+
since we have (Z)(( (L f(x*)) from Assumption and the convex property of f((z)
for any E S. The proof of Lemma is complete.
29

---

Published in Transactions on Machine Learning Research (03/2026)
G Proof of Theorem 3
For the convenience of expression, we use (z(()(t) denote (f( for any i and 2
From Appendix
C for any j 1,2,' ,
have
ckT + + = 12(kT + - 1) - aui(k j-1,
WkT + = yi(kT + - 1) + 9/ (2; + (: + - 1))
(39)
WkT + yı(kT) + g; + j)) (kx()))))
Moreover, similar to the derivation of Lemma
we have
N Σ (x,((1)))) ==1
u((k) = N
(40)
for any S.
Combining (39 and 40
we have
<x(k + kk) =x((k)
(kTx(k++hi)
N
and further
(KoT + k)
x²1 - -1x=;(TT) - x²12
1
(kT 1)), x²) + a 1
2a2 N 1=
+
(41)
For the term -2a / Σø=
Σ 9y (KT +1)) - x²), have
N Σ
2aB
g (z,( b)), - 27)
1=1/=
20
B
=,( h), (f
N
1=1
N
20
E
(k,
- (x))), Vf ( h)))
N
==
From Assumption D and the convexity of f((x), we can obtain
2aR
95 (a, (kr + h)), (((k)) x²))
N
20
55(2²) - (x( hi]
E
N
h=0
N
2a
T.
[5 - 1)) fo (c:T)) + 2 |,, (ke + h) - ((T))
N
1= 0=
30

---

Published in Transactions on Machine Learning Research (03/2026)
which further implies
2aTE (kT + h)) xi(KT) x3)
A=0
S2aTB ((x*) ((+T) (((=))-(<a((kT))
+ ot
Σ Σ
N
[ky (KT xz (kT))
N
From Lemma
we have
(KT + ht) - xx(())11 s 12r La? [(z)(kT)) (22 - -(x0))
+ 27Ta²o
for S <..
Combining the preceding two inequalities leads to
2aBB
1 N h
ΣΣ
(ky + h)),, x¹)]
52aTB f(x')( - (xx(( + 12 $ ((x) - f(x*)] + La"
If the stepsize satisfies 0 < 6TaL S 1, have
2aEE ( N ΣΣ Σ (KT + 1)), 21)) - zz)
N
j=1 h=0
220TB[1(x*) - (kT()) + + 2B (kg -((t)) + 2020
(42)
For the term a
Σラ= En Os +1]l in 41 we have
N
a²
g (5(2,(k7 (kr + +))
N
N
N T-1
<2a²
Σ
+ h)) -
H|| 2a²
Σ Σ
(
(43)
N
N
0=0
j=1h=0
Using the inequality ||a + cl12 < 3||a|1 + 3|bb112 + 3||c|2,,
have
2
By (2, +1) (
2
V (k) -
3ra² N
Σ
(05(2,( + +h) - (z5 + +n))
+
N
N
#=1 h=0
h=0
2
N
+
(
(4
N
31

---

Published in Transactions on Machine Learning Research (03/2026)
Using Assumption
we have the following inequality from
44
a²
gy (2( + +1) - (g)(,
1
o
x 1,T -)) xx))
a N 7-1
91 (2, + (k) hi))
+ j=1
N
1=1
3ra
Σ
Vf((2)(k7)
(45)
Combining 45
and Assumption
we arrive at
2a 2x
E
95( + h)) - (x(()(()T)) |
1=0
G 2 L
N
12 + +1) =2g + 12a2
(46)
N
1=
h=
Lemma 7 and
46
imply
N
(x, + h)) (,( |111
20 E
<72 L'
12a2?-0²
(47)
For the term 1 E
Ex= 9/ (, (kT))]
433
we have
N
22 N N
20
Σ
(1,
(k:
Σ
N h=0
j=
j=l
Thus, from Lemma and Assumption
we have
2a Ell
4a27202 2 f(x*))
(48)
N
Combining
43
47
and
48
have
N
9 (I (KT + 11))|9]
a² E
h=
<722- + 2 E
162 + 160
If the stepsize satisfies 0 < 6Tab < then we have
a E
Σ 9 (
+
m))l 107 =00 1 f(x") 2502
(49)
Combining
41 42 and
49
we have
E (KT + k) x =11
((xs(kT)) E (k+) - x2'1]]] < (2ar 1 2 -(=0))((((((())) a0
32

---

Published in Transactions on Machine Learning Research (03/2026)
If the stepsize satisfies 0 <
1 GrL
have
K-1
x1 - xx=
Σ K=
-((
((x)())))
+ Ao
K
(2at- 12
where
347 2
A 2at 12T2
Thus, we have
E
f( Σ (kT))))
-
K-1
f((0)
(2aT 12 + Ao
10)=
for any E S, which completes the proof.
H Supporting Lemmas for the Proof of Theorem 4
Lemma 8. Under Assumption i if the stepsize satisfies 0 < a<as + we have
(kT + h) zz(kk)]l3] ( 81Ta000
for any 1 S h < t and i S.
Proof. From
56 and 57
we have
1 N
x (kT +j+ 1) = 2,( + - af
Σ
(k(zx(kT)) - (x(x((()))++ + 0 +1)) (x)(
N
j=1
The above equation implies
(KT + j + 1) - (kT)
(kT +) - (kT) - of 1 - V/lltt +51)
NN
j=1
N Σ (k) - N Σ ( (x(T)(kT))
1=1
+ (, (k, +1)}
From Assumption
we obtain
E
b. lT + 1) - x. (R:T) (1:T) )13]
E
2. (KT (KT
+ 5) (x(k)T) a (
Σ
Vf ((((e((k))) + (Z + +5)) }))
N
j=1
N
+ a 2
N Σ (x(()((TT))
v (k)r) + ( - (x((()
N 1=1
+ ( -)) - (1 j)) 5
(50)
33

---

Published in Transactions on Machine Learning Research (03/2026)
For the first term of (50
we have
B
My (KT
( Σ V[)(zz((T))) V[((o(kT))
V[(((()))VV(b((tt)) V/i (olkkk+++)00 +5))) [']
<(1 + ) pi 1 -2,)
(ffi ( +
+ +(++)a& E (=)())
(51)
Assumption
and 51 imply
B
24 (KT j) - (kT) - aa1, N
Σ
Vf((o(())) + + + [|]
5=1
S(1 a(1+aL)
1 E |1 [kT +
z, (kT) |2| +
(52)
For the second term of 50 from Assumption we have
N
N Σ ( - (I(
1
B
Σ
(,(x)((T)))
1=1
j=1
- +x) 1
+
3
E (19 ( + 3E -
N
+
3E
[lgs (x, (KT + + - (f((
Combining the above inequality and Assumption
implies
E
Σ (z
1 N Σ ((((())) -x((s((T))
1 + j)) (=5 + 1))
م 5902.
(53)
Combining 50
52
and 53
leads to
1r (KT j 1) x. [1T) ]
<(1 <(1+aL) + | [1T + +) (KT)))] + + (e + 9a2
Because the stepsize satisfies 0 << S t, have
1-1 (/ +a 3
Σ (1+ 5)+ A=U
E
which further implies
(1 (1+ ++33
E [oa(kT + -
<((1 (1))0<((((///((+00==00>)/11////0 (1))))22(((/////(((()+))))+)))) 90202)
(54)
(1+ 11+1)3=1
34

---

Published in Transactions on Machine Learning Research (03/2026)
for any 0 1 j and e S. In addition, we have
1 ) 15
1 3 7 (1+²)) 12
(1+
(55)
for any j <. Therefore, combining 54 and 55
leads to
p (KT + j) - [1
which completes the proof.
Proof of Theorem
For the convenience of expression, (t)((t)) to denote (f(( for any E S and t 0. From Appendix C for any 1., 1, we have
(kT + =x:(kT (k) --)), WkT + - (k(kT + - 9
(=, + j)) - (kT + - 1))
(56)
Va(k + = vr(kr) + (x, + j)) - (xr()))))).
Moreover, similar to the derivation of Lemma we have
N Σ ==1
(i N
9 (1 (KT))
(57)
for any i S.
From 56 and 57
we have
Dy (kT + k) (kT)
(kT h)),
j=1
for any i S. Thus, using Assumption
we arrive at
f(ri(kr +T)
- (((f))
1 r-1 N
Σ
Σ (z)(
a²I. |1
1
N N-1
r-1
N
j=
j=1
N
1
ff (ko + h))
(z)(((()))))
N
j=1 h=0
hm0
N
N Σ
- a(Vf(z;(kT))
Σ
(K, (kT + h))
Σ
(kT(z,(A++h)))
(58)
N h=
N
1=1
Taking the expectation of both sides of 58 leads
((f(z((T++))) + T))]
a²T E
<B(((z((kT)) Br
+
g (ky + +))
N
h=0
N
+ + (VF(2 N
Σ
[5z + h))
V (5((z((T))]]]
(59)
N
J=1 h
J=1
35

---

Published in Transactions on Machine Learning Research (03/2026)
Using the inequality 2ab - a² b², the relation in 59 and Assumption 3 have
+(((2((k++>))
aZL - I (V]()( +
N
<[[s(Za((>))
23 ( (KT + +1))1]]
2
h=0
aL2
|,y((k h -
(60)
2N
1=
For the term a
スッ Bl h) - (AT))]] on the right hand side of the preceding inequality,
from Lemma
we have
aL?
aL?
E
(k7 h) -) (AT)) <
(61)
2N
2N
A=0
h=0
The stepsize condition
GFL and 61 imply
aL?
||2, h) x, (kT))
S 3r?aa LE [V]((,((+)) L77
(62)
2N
j=1
h=
For the term 1/
Eソ= 11
1])l12
60 we have
N
2
9 (k)((T++
1 N
<aa²
h))
2a²
Σ
Σ
(63)
j=
For the term 1 Ei
-1 in
60
we have
N
a²
N
Ta 2
N
T-1
+ (0,(2, + -1))t+++))-/// (f) -ii +)))
N
1=
+
gz
which further implies
2
9 (5 +1) (kT)) 1?
N
3r 2
N
3ra² N
((((z)(k)))- (x5( |
(KT + h) (kT))
+
N
N
j=1 0=0
==1 h=0
2
N
+
os ( + +h)) - (15(I,(kT + +n))
(64)
N
1= 0=0
36

---

Published in Transactions on Machine Learning Research (03/2026)
From 64 and Assumption 3 have
(k) - (x,(()))) ||]
2a 2
j=
6
+ 12a 2²
h=0
Combining Lemma and the above inequality yields
20 11 ΣE
(kT h)) - -
1088 4 L² B [<) 486 1202
(65)
For the term
N - 2 95 (zg (KT))
N
||
in 63), we have
2a 2
Σ 9o (zr (kT))
[|
(h(r
(66)
From 666 and Assumption 3
we have
2a 20
<4a27202 + ((()((
(67)
h=0
for any S.
Using the inequality ||a b112 < 2||a|12 211b112, we have
a²
(
+h)]
NN
<2a²
2a²
1
ΣΣ Σ
g,(t((kT))|
N
j=1 h=0
j=1
Combining 63
65
and
67
leads to
(1 (KT + h))
h=
(| 16a27202 / (kT))
43
Plugging the stepsize condition
6ral into the preceding inequality leads
i.e.,
Tax2
ΣΣ
g
(0, +
(>>k<++))]]+ m))l
(68)
2
N
1=
37

---

Published in Transactions on Machine Learning Research (03/2026)
From 60
62
and 68
have
- at
13 13,²
(a + -)) (E]
2 + 22 a²2
2
i.e.,
aTT
13
La 2
B11 [ -(f(aat))))+ 22r'
2
2
Under a stepsize satisfing
< a <
13rL>
we have
a L
E (
K
(
2 2² K
0T - 137 La
for any E S, which completes the proof.
38


Reviews:
[{"review_id": "7dmUOfX1sO", "reviewer": "Reviewer_N36A", "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": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The author introduced a new framework for federal learning, dealing with client-draft problem in lower overhead, and analyzed its performance in both convex and non-convex cases.", "claims_and_evidence_yn": "No", "claims_explanation": "1) The update rule itself is clearly presented in Section 3.1. \n    However, beyond the surface-level clarity of the formulation, it would be beneficial to provide \n    more intuitive insight into the underlying mechanism of client-drift cancellation. \n    In particular, a deeper explanation of why the proposed recursion works, rather than only \n    how it is constructed, would significantly improve the understanding of the method.\n    Furthermore, it would be helpful to include a discussion comparing the proposed mechanism with \n    related approaches such as gradient tracking, momentum-based methods, or extrapolation techniques, \n    highlighting both the connections and the key differences. \n    Such a comparison could clarify whether the drift correction is implicitly related to these \n    existing ideas or represents a fundamentally distinct mechanism. \n\n 2) In Section 3.2, the algorithm initializes both $x_i(-2)$ and $x_i(-1)$ with a specific relationship. \n    It would be useful to clarify how sensitive FedRecu is to this initialization. \n    In particular, if the condition on $x_i(-1)$ is not satisfied, does the method still converge, \n    or is this assumption crucial for stability or correctness?\n\n3) Under stochastic setting, let $\\nabla f(x_t; \\xi_t):= \\nabla f(x_t)+e_t $.  I notice the update is exactly\n\n    $$\n        (x_{t+1} - x_t) = (x_t-x_{t-1})-\\alpha  (\\nabla f(x_t)-\\nabla f(x_{t-1}))-\\alpha (e_t - e_{t-1} ) ,\n   $$ which indicates that the stochastic noise directly affects the “speed” variable $x_{t+1}-x_t$, rather than the position $x_t$ itself. This suggests a second-order stochastic dynamics with a potentially different stability structure. It would be helpful if the authors could clarify whether this recursion induces distinct oscillatory or stability behavior compared to standard first-order stochastic methods.", "audience_yn": "Yes", "audience_explanation": "Yes. The paper would be of interest to a subset of the TMLR audience, particularly readers working on machine learning theory.", "requested_changes": "Mentioned as weakness", "broader_impact_concerns": "I do not see any significant broader impact or ethical concerns associated with this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "aeHJXRv8tn", "reviewer": "Reviewer_LB71", "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": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes FedRecu, a federated learning (FL) algorithm designed to address client drift under non-IID data. The method replaces commonly used control variates by leveraging a two-step recursion that incorporates both current and previous gradients during local updates. The paper claims that this design reduces communication/storage overhead, allows larger stepsizes, and achieves an O(1/K) convergence rate under deterministic convex settings, with additional results for nonconvex and stochastic cases. Experiments on CIFAR-10/100 compare FedRecu with several existing FL baselines.", "claims_and_evidence_yn": "No", "claims_explanation": "After reading the paper, it is still unclear why combining the current and previous gradients is sufficient to correct client drift. The manuscript does not provide a clear derivation showing how the recursion removes the local bias term, nor does it justify the claim in Remark 1 that the iteration remains well-behaved when initialized at the global optimum. As a result, it is also unclear why this mechanism would eliminate the need for auxiliary control variates used in prior work.\n\nThe experimental evidence is similarly not fully convincing.\n(1) Table 2 states that FedRecu supports step sizes 6–49× larger than prior methods, but the experiments do not include any systematic stepsize choices or sweeps across baselines to substantiate this claim.\n(2) Several more recent and relevant baselines—such as momentum-based FL methods [1]—are missing, which limits the strength of the empirical comparison.\n\n[1] Cheng et al., Momentum benefits non-IID federated learning simply and provably, ICLR 2024.", "audience_yn": "Yes", "audience_explanation": "The topic—client drift reduction and communication-efficient FL—is of interest to the TMLR and broader machine-learning community. Many researchers study FL optimization, and a method that removes control variates while maintaining fast convergence could be impactful.\n\nHowever, while the area is relevant, the current submission does not yet present the contributions with enough clarity, rigor, and empirical robustness to fully engage the intended audience.", "requested_changes": "Please refer to the weaknesses as shown above.", "broader_impact_concerns": "I do not identify any major ethical concerns with the work as presented.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Q7XQRftBAU", "reviewer": "Reviewer_LnKP", "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": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces FedRecu, a recursion-based federated learning algorithm that mitigates client drift without relying on explicit control variates. The method performs a two-step recursive update that couples the current and previous model parameters and gradients, effectively creating an implicit gradient-difference tracker that compensates for the bias caused by heterogeneous local objectives. The authors provide both deterministic and stochastic convergence analyses, establishing an o(1/K) rate for general convex problems and showing that FedRecu supports significantly larger step sizes than existing drift-correction methods. Experiments on CIFAR-10/100 and synthetic regression tasks demonstrate faster convergence and reduced communication overhead.\n\nStrengths:\n- The proposed recursion guarantees that the global optimum remains a fixed point even when local gradients differ at that point, offering a compelling and intuitive explanation for how the method eliminates client drift.\n- Compared with SCAFFOLD, FedLin, and FedTrack, FedRecu supports substantially larger step sizes, which translates into faster convergence in theory.\n\nWeakness:\n- The reviewer might consider the reduction in memory overhead to be limited; moreover, given that memory on edge devices is relatively inexpensive, this improvement may not be particularly compelling.\n- The comparison of convergence rates in Table 2 may be somewhat unfair, as most of the referenced works use stochastic gradient settings, whereas the results reported for FedRecu are based on a deterministic scenario\n- Concerning the larger step size, there may be insufficient experimental evidence to fully support this claim.", "claims_and_evidence_yn": "No", "claims_explanation": "- Only some analytical results are provided in terms of different step sizes in Table 2, while the claim on this benefit may not be convincing. \n- It is stated that FedRecu is inspired by EXTRA, but it is unclear why EXTRA behaves differently in the multiple updates cases, which may lower the novelty.\n- It is quite strange that the test accuracy of FedRecu, SCAFFOLD, and FedLin achieves very similar results in different Non-IID settings. Additionally, it lacks an explanation of the performance gain.", "audience_yn": "Yes", "audience_explanation": "- The paper addresses an important challenge in federated learning, namely, non-IID data, and presents promising results. \n- Unlike prior work, the focus is on local updates, and the convergence analysis does not require explicitly accounting for non-IID heterogeneity.", "requested_changes": "Besides the mentioned weakness, the reviewer suggests the following changes:\n- Adding detailed descriptions of other \"client-drift\" correction algorithms.\n- Providing a detailed comparison with EXTRA, which can enhance the novelty.\n- Justifying the results reported in Table 2 and different non-IID settings.\n- A better illustration is suggested. For example, pages 10 and 11 contain too many figures.", "broader_impact_concerns": "Nah", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)