Momentum Benefits Non-iid Federated Learning Simply and Provably
Authors: Ziheng Cheng
Xinmeng Huang
Pengfei Wu
Kun Yuan
Venue: ICLR 2024 poster (2024)
Keywords: federated learning
momentum
data heterogeneity
non-convex optimization
Primary area: optimization
TL;DR: We develop momentum variants of FedAvg and SCAFFOLD that attain SOTA (or even better) convergence under weaker assumptions.

Abstract: Federated learning is a powerful paradigm for large-scale machine learning, but it
faces significant challenges due to unreliable network connections, slow commu-
nication, and substantial data heterogeneity across clients. FedAvg and SCAFFOLD are two prominent algorithms to address these challenges. In particular,
FedAvg employs multiple local updates before communicating with a central
server, while SCAFFOLD maintains a control variable on each client to compen-
sate for “client drift” in its local updates. Various methods have been proposed
to enhance the convergence of these two algorithms, but they either make imprac-
tical adjustments to algorithmic structure, or rely on the assumption of bounded
data heterogeneity. This paper explores the utilization of momentum to enhance
the performance of FedAvg and SCAFFOLD. When all clients participate in the
training process, we demonstrate that incorporating momentum allows FedAvg
to converge without relying on the assumption of bounded data heterogeneity even
using a constant local learning rate. This is novel and fairly suprising as existing
analyses for FedAvg require bounded data heterogeneity even with diminishing
local learning rates. In partial client participation, we show that momentum en-
ables SCAFFOLD to converge provably faster without imposing any additional
assumptions. Furthermore, we use momentum to develop new variance-reduced
extensions of FedAvg and SCAFFOLD, which exhibit state-of-the-art conver-
gence rates. Our experimental results support all theoretical findings.

Published as a conference paper at ICLR 2024
MOMENTUM BENEFITS NON-IID FEDERATED LEARN- ING SIMPLY AND PROVABLY
Ziheng Cheng"
Xinmeng Huang"
Peking University
University of Pennsylvania
slex-czhestu.pku.. pku. en
xinmengh@sas. upenn edu
Pengfei Wu
Kun Yuan'
Peking University
Peking University
pengfelwul9999stu..ke pku, cn
kunyuan@pku.edu.
ABSTRACT
Federated learning is powerful paradigm for large-scale machine learning, but it faces significant challenges due to unreliable network connections, slow commu- nication, and substantial data heterogeneity across clients. FEDAVG and SCAF- FOLD are two prominent algorithms to address these challenges. In particular, FEDAVG employs multiple local updates before communicating with a central server, while SCAFFOLD maintains control variable on each client to compen- sate for "client drift" in its local updates. Various methods have been proposed enhance the convergence of these two algorithms, but they either make impracti- cal adjustments to the algorithmic structure or rely on the assumption bounded data heterogeneity. This paper explores the utilization of momentum to enhance the performance of FEDAVG and SCAFFOLD. When all clients participate in the training process, demonstrate that incorporating momentum allows FEDAVG to converge without relying on the assumption of bounded data heterogeneity even using constant local learning rate. This is novel and fairly surprising existing analyses for FEDAVG require bounded data heterogeneity even with diminishing local learning rates. In partial client participation, we show that momentum en- ables SCAFFOLD to converge provably faster without imposing any additional assumptions. Furthermore, we use momentum to develop new variance-reduced extensions of FEDAVG and SCAFFOLD, which exhibit state-of-the fit-hhe-rt art conver- gence rates. Our experimental results support all theoretical findings.
INTRODUCTION
Federated learning (FL) is a powerful paradigm for large-scale machine learning (Konečný et al., 2016; McMahan et al., 2017a). In situations where data and computational resources dispersed among a diverse range of clients, including phones, tablets, sensors, hospitals, and other devices and agents, federated learning facilitates local data processing and collaboration among these clients (Kairouz et al., 2021). Consequently, centralized model can be trained without transmitting decen- tralized data from clients directly to servers, thereby ensuring a fundamental level of privacy.
Federated learning encounters several significant challenges in algorithmic development. Firstly, the reliability and relatively slow nature of network connections between the server and clients pose obstacles to efficient communication during the training process. Secondly, the dynamic availability of only small subset of clients for training at any given time demands strategies that can adapt to this variable environment. Lastly, the presence of substantial heterogeneity of non-iid data across different clients further complicates the training process.
FEDAVG (Konečný et al., 2016; McMahan et al., 2017a; Stich, 2019; Yu al., 2019a; Lin et al., 2020; Wang & Joshi, 2021) emerges as prevalent algorithm for FL, leveraging multiple stochastic gradient descent (SGD) steps within each client before communicating with a central server. While FEDAVG is readily implementable and succeeds in certain applications, its performance is notably
'Equal Contribution. This work is supported in part by National Natural Science Foundation of China (NSFC) Grant 12301392, 92370121, and 12288101
1 'Corresponding Author. Kun Yuan is also affiliated with National Engineering Labratory for Big Data Analytics and Applications, and AT for Science Institute, Beijing, China.

---

Published as a conference paper at ICLR 2024
hindered by the presence of data heterogeneity, i.e., non-iid clients, even when all clients partici- pate in the training process (Li et al., 2019; Yang et al., 2021). To mitigate the influence of data heterogeneity, SCAFFOLD (Karimireddy et al.. 2020b) maintains a control variable on each client to compensate for "client drift" in its local SGD updates, making convergence more robust to data heterogeneity and client sampling. Due to their practicality and effectiveness, FEDAVG and SCAF- FOLD have become foundational algorithms in federated learning, leading to the development of numerous variants that cater to decentralized (Koloskova et al., 2020; Rizk et al., 2022; Nguyen et al., 2022; Alghunaim, 2023), compressed (Haddadpour et al., 2021; Reisizadeh et al., 2020; Mitra al., 2021), asynchronous (Chen et al., 2020a;b; Xu et al., 2021a), and personalized (Fallah al., 2020; Pillutla et al., 2022; Tan et al., 2022; T Dinh et al., 2020) federated learning scenarios.
Various methods have been proposed to enhance the convergence of FEDAVG, SCAFFOLDD, and their variance-reduced extensions. While exhibiting superior convergence rates, these approaches typically make impractical adjustments to algorithmic structures. For instance, STEM (Khanduri et al., 2021) requires increasing either the batch size or the number of local steps with algorithmic iterations, Similarly, CE-LSGD (Patel et al., 2022) and MIME (Karimireddy et al., 2020a) mandate computing a large-batch even full-batcl local gradient per round for each client. Additionally, FEDPROX (Li et al., 2020), FEDPD (Zhang et al., 2021), and FEDDYN (Durmus et al., 2021) rely on solving "local problems" to extremely high precision. These adjustments may not align with the practical constraints in federated learning setups.
Furthermore, many of these algorithms, including FEDAVG, STEM, FEDPROX, MIME, and CE- SGD, still rely on the assumption of bounded data heterogeneity. When this assumption is violated, their theoretical analyses become invalid. While some algorithms, such as LED (Alghunaim, 2023) and VRL-SGD (Liang et al., 2019), can handle unbounded data heterogeneity, their convergence rates are not ofte--of-the-rre as stated in Table 1. These limitations motivate us to develop novel strategies that are easy to implement, robust to data heterogeneity. and exhibit superior convergence.
1.1 MAIN RESULTS AND CONTRIBUTIONS
This paper examines the utilization of momentum to enhance the performance of FEDAVG and SCAFFOLD. To ensure simplicity and practicality in implementations, we only introduce mo- mentum to the local SGI) steps, avoiding any inclusion of impractical elements, such as gradient computation of multiple minibatches or solving local problems high precision. Remarkably, this straightforward approach effectively alleviates the necessity for stringent assumptions regarding bounded data heterogeneity, leading to noteworthy improvements in convergence rates. The main findings and contributions of this paper are summarized below.
First, when all clients participate in the training process:
We show that incorporating momentum allows FEDAVG and its variance-reduced extension to converge under unbounded data heterogeneity, even using constant local learning rates. This is rather surprising as, to our knowledge, all existing analyses for FEDAVG, e.g., Karimireddy et al. (2020b); Yang et al. (2021); Wang et al. (2020b) require bounded data heterogeneity even with diminishing local learning rates.
We further establish that, by effectively removing the influence of data heterogeneity on con- vergence. momentum empowers FEDAvG and its suriance-reduced extension with state-of- the-art convergence rates in the context of full client participation.
Second, when partial clients participate in the training process per iteration:
The proposed SCAFFOLD-M. M that incorporates momentum into SCAFFOLD achieves prov- ably faster convergence. To our knowledge, this the first result that improves SCAFFOLD without imposing additional assumptions beyond those in Karimireddy et al. (2020b).
We further introduce momentum to SCAFFOLD with variance reduction, obtaining the first variance-reduced FL algorithm that converges without bounded data heterogeneity. This method attains the state-of-the-art convergence rate in the context of partial client participa- tion and unbounded data heterogeneity.
Tables and 2 present a comprehensive comparison of the convergence rates and associated assump- tions of prior algorithms and our proposed methods. It is observed that by simply adding momentum
'Throughout the paper, variance reduction refers techniques aiming to mitigate the influence of within- client gradient stochasticity, as opposed to the inter-client data heterogencity.
2

---

Published as a conference paper at ICLR 2024
Table I: The comparison of convergence rates of FL algorithms when all clients participate in training. No-
tation L is the smoothness constant of objective functions, A = f(=²) min, f(z) is the initialization gap, o² is the variance of gradient noises, N is the number of clients, K is the number of local steps per round, and R is the number of communication rounds, < and C are uniform bounds of data heterogeneity
E [V)))))) V f=()ll and gradient norm == sup, maxi [(x)il with C
typically. The "Assumptions" column lists all assumptions beyond Assumption and 3.
Algorithm
Convergence Rate E V | [+)))
Assumptions
FEDAVG
(Yu et al., 2019b)
LAg
1/2
LAG
2/3
LA π
Bounded grad.
NK
R
1/2
(Koloskova et al., 2020)
LAc2
+
LAKE
+
LAK
Bounded hetero.
NR
(Karimireddy et al., 2020b)
NKT
LAg
1/2
+
LAC
2/3
+
LA
R
Bounded hetero.
1/2
(Yang et al., 2021)
LAe
LA
Bounded hetero."
NKR
R
2
LA(a2 NKG
LA(a/VR
2/3
Bounded grad.
(Xu et al., 2021b)
NKR
K
Bounded hetero.
LED
(Alghunaim, 2023)
LAn?
NKR
+
VKR
LAe
+
LA
R
VRI-SGD?
(Liang al., 2019)
NKR
LAa
1/2
+
VKR
LAo
2/3
+
LA
FEDAvG-M (Thm. 1)
LAg
+ LA
NKR
R
CRIIANCEREEDCTTOO
BVR-L-SGD
2/3
+ d² + LA
Sample smooth O(K) minibatches
(Murata & Suzuki, 2021)
NKR
NKR
R
CE-LSGD
LAo
2/3
Φ LA + NKR H
Sample smooth O(K) minibatches
(Patel et al., 2022)
(KR
STEM
24 LA (NKR)33 R
Sample smooth Bounded hetero.
(Khanduri et al., 2021)
FEDAVG-M-VR (Thm. 2)
LAo 2/3
+ LA
Sample smooth
NKR
FEDAVG-M- VR (Thm. 15)
NKR
LAo 2/3
+ NKR
LA R
Sample smooth
The local learning rate vanishes to zero when data heterogeneity unbounded, i.e., Ç 00.
The works have not been published in peer-reviewed venues.
A large number of minibatches are utilized on each client per communication round.
The difference roots in the amount of batches used for initialization. See the values of B in Thm. 15.
to local steps, FEDAVG, SCAFFOLD, and their aariance-reduced variants all attain state-of-the-art convergence rates without resorting to further assumptions such as bounded data heterogeneity. We support our theoretical findings with extensive numerical experiments.
1.2 RELATED WORK
FL with homogeneous clients. FEDAVG is well-known algorithm introduced by McMahan al. (2017b) as a heuristic to enhance communication efficiency and data privacy in federated learning. Numerous subsequent studies have focused analyzing its convergence under the assumption of homogeneous datasets, where clients are independent and identically distributed (iid) and all clients participate fully (Stich, 2019; Yu al., 2019h Wang & Joshi, 2021; Lin et al., 2020; Zhou & Cong. 2017). However, when dealing with heterogeneous clients and partial client participation, FEDAVG found to be vulnerable data heterogeneity because of the "client drift" effect (Karimireddy et al., 2020b; Yang et al., 2021; Wang et al., 2020b; Li et al., 2019).
FL with heterogeneous clients. Numerous research efforts are devoted to mitigating the impact of data heterogeneity in FL. For example, Li et al. (2020) propose FEDPROX, which introduces a proximal term to the objective function. Yang et al. (2021) utilize two-sided learning rate approach, while Wang et al. (2020a) propose FEDNOVA, a normalized averaging method. Additionally, Zhang et al. (2021) presents FEDPD, which addresses data heterogeneity from primal-dual optimization perspective. Notably, Karimireddy et al. (2020b) introduces SCAFFOLD, an effective algorithm that employs control variables mitigate the influence of data heterogeneity and partial client partic- ipation. FEDGATE (Haddadpour et al., 2021) l) and LED (Alghunaim, 2023) are two recent effective algorithms that have alleviated the impact of data heterogeneity, utilizing gradient tracking (Xu et al.,
3

---

Published as a conference paper at ICLR 2024
Table 2:
The comparison convergence rates of FL algorithms when S out of N clients participate in training per itcration. Notations are the same as those in Table 1.
Algorithm
Convergence Rate ([V)))
Assumptions
SCAFFOLD
LA02)
+ )
LA R
(Karimireddy et al., 2020b)
9KR)
SCAFFOLD-M (Thm.
LAga
SKR
+
LA
x
+
N2/3
MARIANCE-REDUCTION
MIMELITEMVR'
LA(o-()
2/3
L
Sample smooth Noiseless grad. Sample smooth Bounded hetero. O (') minibatches Sumple smooth Bounded hetero. O(K) minibatches
(Karimireddy et al., 2020a)
R
MB-STORM
(Patel et al., 2022)
SVRR
LAo
2/3
+
LAC SR
2/3
BR
LA
SKR
CE-LSGD
(Patel et al., 2022)
5VRR
2/3
+
SR
LAC
2/3
SKR
SCAFFOLD-M-VR (Thm.4)
LAx
2/3
LA
1 1
N1/2
Sample smooth
3VKR
R
5
CCAFFOLD-M-VE (Thm. 22)
SVRR
LAg
2/3
+
LA R
1 +
N1/2
5
SKR
Sample smooth
MIMELITEMVR and CE-LSGD consider the setting of streaming clients.
large number minibatches are utilized on each client per communication round.
3 The difference roots in the amount of batches used for initialization. See the values of B in Thm. 22,
2015: Di Lorenzo & Scutari, 2016; Pu & Nedić, 2020; Xin et al., 2020; Alghunaim & Yuan, 2021; Huang et al., 2024) and exact-diffusion (Yuan et al., 2019; 2020; 2023) techniques, respectively.
FL with momentum. The momentum mechanism dates back to Nesterov's acceleration (Yurri, 2004) and Polyak's heavy-ball method (Polyak, 1964), which later flourishes in the stochastic opti- mization (Yan et al., 2018; Yu et al., 2019 9a; Liu et al., 2020) and other areas (Yuan et al., 2021; He al., 2023b;a; Chen al., 2023; Huang et al., 2024). Extensive research has explored incorporat- ing momentum into FL (Reddi et al., 2021; Wang et al., 2020b; Karimireddy et al., 2020a; Khanduri et al., 2021; Patel et al., 2022; Das al., 2022; Yu et al., 2019a; Xu et al., 2021b), and have demon- strated its impact on enhancing the empirical performance of FL methods (Wang et al., 2020b; Xu et al., b02 Reddi et al., 2021; Jin et al., 2022; Kim et al., 2022). However, whether momentum can offer theoretical benefits FL, especially in mitigating the impact of data heterogeneity, remains unclear. This work demonstrates that momentum can benefit non iid federated learning simply and provably. Notably, the utility of momentum is demonstrated in domains other than FL.. For instance, Guo et al. (2021) proves that momentum can correct the bias experienced by the ADAM method, while recently Fatkhullin et al. (2023) shows that momentum can improve the error feedback tech- nique in communication compression. The analysis presented in this work distinguishes from prior works including Guo al. (2021): Fatkhullin al. (2023) due to the unique challenges encountered in FL including multiple local updates, data heterogeneity, and partial client participation.
PROBLEM SETUP
This section formulates the problem of non-iid federated learning. Formally, we consider minimiz- ing the following objective with the fewest number of client-server communication rounds:
1 N Σ f((x)
min ZERd
f(z)
where f(()) Eg,,D, [F(x
Here, the random variable & represents a local data point available at client i, while the function fa(z)) denotes the non-convex local loss function associated with client i. This function takes expec- tation concerning the local data distribution D, In practice, the local data distributions D; among different clients typically differ from each other, resulting in the inequality fe(x) + f5(x) for any pair of nodes i and j. This phenomenon is commonly referred as data heterogeneify. If all local clients were homogencous, meaning that all local data samples follow the same distribution D, we would have f((x) = fz) for any and j. In addition, throughout the paper, we assume that the function if is bounded from below and possesses a global minimum f*. To facilitate convergence analysis, we also introduce the following standard assumptions.
Assumption 1 (STANDARD SMOOTHNESS). Each local objective fi is L-smooth, i.e., [V) - ff((i)l < [| - yll. for any x. y E TRd and iigh N.
Assumption (SAMPLE- WISE SMOOTHNESS). Each sample-wise objective F(x; is L-smooth, ie. &+) VF(r;&)) < T.I vll for any x, y E Rdd, 1 < i < N, and & itd D;.
4

---

Published as a conference paper at ICLR 2024
Algorithm FEDAVG-M: FEDAVG with momentum
Require: initial model nº and gradient estimate g², local learning rate global learning rate 7 momentum /
for - -0,--0--. .... for each client i (1, ; N) in parallel do Initialize local model -0:0 x²
R- do
for k: = 0, K do
Compute g.¹t BV r.k cT.k) )+ + (1 3)9"
3 = implles FEDAVG
Update local model 1z 1.t xith 199;"
r.k
end for end for
Aggregate local updates g"+1 NNK Update global model x=+1 x² 79" r+1 end for
N Di=1
x x
worth noting that Assumption 2 implies Assumption 1, which is typically used in variance- reduced algorithms, e.g., Karimireddy et al. (2020a); Khanduri et al. (2021); Fang et al. (2018); in different algorithms. It is
Cutkosky & Orabona (2019). We will utilize either Assumption worth highlighting that, these are the only assumptions required for all our theoretical analyses.
Assumption 3 (STOCHASTIC GRADIENT). There exists 2 0 such that for any I E Rd and IsiS N, EE,.EV (v;(,;; = (ax) and Eg, VIIIIIFF (.) (+) S o² where & sid D..
ACCELERATING FEDAVG WITH MOMENTUM
This section focuses on full client participation. We will introduce momentum to both FEDAVG and its variance-reduced extension. Furthermore, will justify that the incorporation of momentum effectively mitigates the impact of data heterogeneity, leading to improved convergence rates.
3.1 FEDAYG WITH MOMENTUM
Algorithm. We introduce momentum enhance the estimation of the stochastic gradient, sulting in the algorithm FEDAVG-M, as presented in Algorithm 1. In FEDAVG-M, the subscript i represents the client index, while the superscripts and denote the outer loop index and inner local update index, respectively. The structure of FEDAVG-M remains identical to the vanilla FEDAVG, except for the inclusion of momentum in gradient computation (see highlight in Algorithm 1):
9; k
Fz
r.k < + (1 -3)g",
where 8 E [0, 1] the momentum coefficient, and g represents a global gradient estimate updated in the outer loop r. It is important to note that FEDAVG-M will reduce to the vanilla FEDAvG when 3 1. Furthermore, FEDAVG-M is easy to implement, as it maintains the same algorithmic structure and incurs no additional uplink communication overhead compared to FEDAVG. Notably, no extra downlink commmunication cost needed if clients store the last iterate model x" so that momentum th can recovered through (x*+1 x²)/7.
Convergence property. The inclusion of momentum in FEDAYG yields notable theoretical im- provements. Firstly, it eliminates the need for the data heterogeneity assumption, also known as the gradient similarity assumption. The assumption can be expressed
VreR Rd
(Bounded data heterogeneity)
where 2 measures the magnitude data heterogeneity. By incorporating momentum, the above assumption is no longer required for the convergence analysis of FEDAYG. Secondly, momentum enables FEDAVG to converge at state-of-the-art rate. These improvements are justified as follows: Theorem 1. Under Assumption I and 3, if we set go = = 8, y, and as in (5), FEDAVG-M enjoys R-1
LAo? LA
Σ
R
NKR
R
where A a f(x0) ((z²)-a miny f(x) and absorbs numeric numbers. See proof in Appendix B.
5

---

Published as a conference paper at ICLR 2024
Comparison with FEDAVG. Table compares FEDAVG-M with prior algorithms when all clients participate in the training process. The results demonstrate that FEDAvG-M attains the most fa- vorable convergence rate without relying any assumption of data heterogeneity. Moreover, this rate matches the lower bound provided by Arjevani et al. (2019). Notably, a recent work (Huang al., 2023) establishes the convergence of FEDAVG by relaxing the bounded data heterogeneity to a bound on f* 1 Σ Si where f & ming f (() and f _ fz(z). However, their con- vergence does not benefit from local updates. Moreover, it still suffers from data heterogeneity f' Ei=1 and gets slow as the number of clients N increases, resulting in suboptimal rate.
N
Comparison with FRDCM. FEDAVG-M coincides with the FEDCM algorithm proposed by Xu al. (2021b). However, our result outperforms that of Xu et al. (2021b) in several aspects. First, our convergence only utilizes the standard smoothness of objectives and gradient stochasticity while Xu et al. (2021b) additionally require bounded data heterogeneity and bounded gradients which are rarely valid in practice, suggesting the limitation of their result. Second, the convergence established by Xu et al. (2021b) is significantly weaker than ours and cannot even asymptotically approach the R) in non-convex FI., as demonstrated by the results stated in Table 1.
customary rate
Constant local learning rate. Based on Theorem I, it can be inferred that when 2 NKTA FRDAVG-M M allows the utilization of constant local learning rate 1) which does not necessarily decay as the number of communication rounds R increases. This characteristic eases the tuning of the local learning rate and improves empirical performance. In contrast, many existing convergence results of FEDAVG necessitate the adoption of local learning rates that diminish as R increases, as exemplified by e.g., Yang et al. (2021); Li et al. (2019); Karimireddy et al. (2020b); Koloskova et al. (2020).
Intuition on the effectiveness of momentum. The momentum mechanism relies on an accumu- 3
lated gradient estimate g". which is updated through g g²+1 = NK Σ ΣR V ;F(a," + (1 (1-3)) 3)g". While g" is a biased gradient estimate, it exhibits reduced variance due to its accumula- tion nature compared a stochastic gradient Fx cTah) computed with a single data minibatch. Importantly, by utilizing directions Fx e, + (1 - 3) for local updates, an "anchoring" effect is achieved, effectively mitigating the "client-drift" phenomenon. In the extreme case where 3 = 0, all clients remain synchronized in their local updates, eliminating the drift incurred by data heterogeneity in the vanilla FEDAVG. By appropriately tuning the coefficient 13, FEDAVG-M maintains the same convergence rate as (Yang et al., 2021) while removing the requirement of data heterogeneity assumption utilized in their analysis.
3.2 VARIANCE- REDUCED FEDAVG WITH MOMENTUM
When each local loss function is further assumed to be sample-wing wise smooth (i.e., Assumption 2), can replace the local descent direction in Algorithm with a variance-reduced momentum direction
9, r.k = F :5." + 3) - VF(x" ))
(2)
to further enhance convergence, leading to variance-reduced FEDAVG with momentum, or FEDAVG-M-VR for short, see the detailed algorithm in Appendix B.2. The variable x--1 is the last-iterate global model maintained in the server. The construction of the variance-reduced direc- tion (2) effectively mitigates the influence of within-client gradient noise and can be traced back to SARAH (Nguyen et al., 2017) 7) and STORM (Cutkosky & Orabona, 2019) in stochastic optimization; more discussion can be found in Tan al. (2022). Same as FEDAVG-M, turning off the variance- reduced momentum of FEDAVG-ME VR, i.e., setting 3 1, recovers FEDAVG. FEDAVG-NA M- VR shares the same algorithmic structure and uplink communication workload as FEDAVG.
Theorem 2. Under Assumption and 3, if we take go = NB EN Ee VF(4"; cby2 with
1
B
B idd Tb=1 ~
D; and set 3, Y,
and B as in (8), FEDAVG- VR enjoys R-1
LAO 2/3
LA
A Σ BUTS
NKR
R
Comparison with prior works. FEDAVG-M-VE outperforms existing variance-reduced FL methods in convergence rate, as justified by the results listed in Table 1. Additionally, compared to BVR-L-SGD (Murata Suzuki, 2021) and CE-LSGD (Patel et al., 2022). FEDAVG-M- conducts each local update using + 1/K 0(1) minibatches on average, contrasting with the
We use B data minibatches per client to initialize the gradient estimate g with small variance Rlllg ff ) after which only one minibatch utilized per local gradient computation. The same applies below.

---

Published as a conference paper at ICLR 2024
Algorithm 2 SCAFFOLD-M: SCAFFOLD with momentum
Require:
initial model zo, gradient estimator g", control variables {c [e and c", local learning rate 1/. global learning rate 7, momentum for for 0.... R do Uniformly sample clients S, S [1,..., .N) with |S, for each client i S, in parallel do Initialize local model r.." x²
for l 0, K 1 do
Compute 9, t - ((VF(s, R ct cj - + (1 33g" >Ø = 1 implics SCAFFOLD
Update local model u; x+1 vi N. r.K
-199;
end for
Update control variable ct+ = 1 end for
Ek=o VF(x, :5 (for i Sr, ctt = c))
K
Aggregate local updates g=+1 15K Eies, (x"-27"k) I.K
Update global model x=+1 x² --g"t1 ++ Update control variable c_+1 cº' + No Eies, (c c))
end for
O(K) minibatches in BVR-L-SGU and CE-LSGD Furthermore, in comparison to STEM (Khan- duri al., 2021), FEDAVG-N M-VR does not rely on the assumption of bounded data heterogeneity.
Based on discussions in Sections 3.1 and 3.2, we demonstrate that FEDAVG-M and TEDAvG-M- VR, in the context of full client participation, can achieve the state-of-the-ate convergence rate with- out resorting any stronger assumption, e-g., bounded data heterogeneity impractical a algorithmic structures such as large number minibatches in local gradient computation.
4 ACCELERATING SCAFFOLD WITH MOMENTUM
This section addresses the scenario where a random subset of clients participates in each training round. To tackle the challenges of partial participation, SCAFFOLD employs a control variable in each client counteract the "client drift" effect during local updates. We will introduce momentum to both SCAFFOLD and its variance-reduced extension to gain better convergence results.
4.1 SCAFFOLD WITH MOMENTUM
Algorithm. We introduce momentum to enhance the estimation of the stochastic gradient, result- ing in the newly proposed algorithm SCAFFOLD-M, outlined in Algorithm 2. In SCAFFOLD- M. S clients are randomly selected from a pool of N clients for each training itcration. The control variables c; and e are maintained by the client and server, respectively. SCAFFOLD,, the local +c. In contrast, SCAFFOLD-M incorporates
descent direction given by ; kr - of + c..
momentum directions for local updates:
9, ((VF(2/* :5 - - of + +c") (1-
(3)
where g" represents the global stochastic gradient vector maintained by the server. it worth noting that SCAFFOLD-M. can reduce to SCAFFOLD by setting 3 = 1.
Convergence property. Our momentum yields notable theoretical improvements to SCAFFOLD:
Theorem 3. Under Assumption and 3, we take go
of
SF < with
B üdd Dr,
1/ AiN+ of and set 3, 7, T, and B as in (9), SCAFFOLD-M enjoys
R-1
LAO2 SKR + R (1+ S
LA
(
N2/3
R BUNSSOOIIS
Σ
Comparison with SCAFFOLD. Compared to SCAFFOLD, SCAFFOLD-M exhibits provably
faster convergence under partial participation, as justified in the comparison in Table 2. Specifically, when the gradients are noiseless (i.e., o² 0). achieving the same level of stationarity E[] [ requires ratio, between SCAFFOLD- - and SCAFFOLD, of communication rounds:
1 N2/3/5
S
2/3
(N/S)2/3
N
81/3

---

Published as a conference paper at ICLR 2024
2.1
Feddig-M Scaffold
Fedding
2.2
MB- MB-STORM
2.30
2.25
Scaffold
Scaffold-M
2.0
FedAvg-Hie MAVR
Scaffold-M-VR
2.1
2.20
2.15
2.10
1.9
2.05
1.7
1.95
10
20
30
40
50
60
10
20
30
40
50
0
20
40
60
80
100
(a) Acceleration by momentum
(b) Comparison of VR methods
(c) Partial participation
Figure 1: Test loss of three-layer MLP versus the number of communication rounds
Thus, if x N2/3, SCAFFOLD-M achieves up to N2/9 times improvement in comparison to the vanilla SCAFFOLD, when aiming for the same level of stationarity. This improvement is significant as N, the number of clients in FL, is typically large. It is also worth highlighting that prior to SCAFFOLD-M, SCAFFOLD of our knowledge, that is robust to both unbounded data heterogeneity and partial client sampling, and capable of attaining linear speedup without relying on impractical algorithmic structures. The development of SCAFFOLD- M provides an alternative and superior choice.
the only known non-iid FL method, the best
4.2 VARIANCE-REDUCCHS SCAFFOLD WITH MOMENTUM
Similar to FEDAVG-M-VER when the loss functions further enjoy the sample-wise smoothness prop- crty, we can obtain SCAFFOLD-M-VE by replacing momentum directions in Algorithm 2 with variance-reduced momentum directions
F= + B(c] - c²) -1- 3) VF
The detailed algorithm in Appendix C.2, and the convergence shown below.
Theorem 4. Under Assumption and 3. if we take ef = B
E VF(x"; { with {st B iid
1b=1 D.
g" d E ol and set 3. 7, T, and B as in (11). SCAFFOLD-M enjoys
R-1
T.O 2/3
L.
(
N1/2 S
Σ
+
R
SVKR
R
Comparison with variance-reduced methods. SCAFFOLD-M- outperforms all existing variance-reduced federated learning methods under partial participation terms of convergence rate when data heterogeneity is severe (i.e., Ç is large), see results listed in Table 2. Moreover, SCAFFOLD-M-VV has the following additional advantages. Compared to MIMELITEMVR (Karimireddy et al., 2020a), MAFFOLL----VE does not need access to noiseless (full-batch) local gradients per iteration. Compared to MB-STORM (Patel et al., 2022) and CE-LSGD (Patel al., 2022), SCAFFOLD M--M--V VR does not require bounded data heterogeneity and conducts each local update using + 1/K = O(1) minibatches on average, instead of O(K).
Based on Sections 4.1 and 4.2, demonstrate that SCAFFOLD-M and SCAFFOLD-M-
in the context of partial client participation, can achieve state-of-the-art convergence rates without resorting any stronger assumption, e.g., bounded data heterogeneity impractical algorithmic structures such as large number of minibatches in local gradient computation.
5 EXPERIMENTS
We present experiments on the CIFAR- dataset (Krizhevsky & Hinton, 2009) with two neural net- works (three-layer MLP, ResNet- 18) justify the efficacy of our proposed algorithms. We evaluate them along with baselines including FEDAVG (Konečný et al., 2016), SCAFFOLD (Karimireddy et al.. 2020b), MB-STORM, CE-LSGD (Patel al., 2022). Parameters (such learning rates) in our implementation are set by grid search. We defer more experimental details and results (e.g., investigating the impact of momentum value 8, setups with large N) to Appendix D.
5.1 MLP EXPERIMENTS
The MLP experiments involve K 32 local updates and N 10 clients with data generated via the Dirichlet distribution (Hsu et al., 2019) with a parameter of 0.5 and 0.2 for full and partial client participation, respectively (small parameter value implies severe heterogeneity).
Firstly, we compare the performance of FEDAVG-M and SCAFFOLD-M with their momentum- free counterparts, namely the vanilla FEDAVG and SCAFFOLD, under full client participation.
8

---

Published as a conference paper at ICLR 2024
0.9
0.9
0.7
0.7
0.5
0.5
FedAug FedAvg M
0.4
Redbug
0.3
0.3
FodAvg-M
Scaffold X
0.2
Scaffold M
10
20
30
40
50
60
10
20
30
40
50
60
(a) Full (left) & partial (right) participation under mild data heterogeneity
0.8
0.8
0.6
0.6
0.5
0.5
0.4
FedAug
FedAyg
0.3
RadAug-M M
0.3
Rodkvg-M1
Scaffold
Scatfold
0.2
Scaffold-M
Scaffold-M
0.1
10
20
30
40
50
60
10
20
(b) Full (left) & partial (right, best-so-far) participation under severe heterogeneity
Figure 2: Test accuracy of ResNet18 versus the number of communication rounds
The results are presented in Figure ((a), which can be observed that incorporating momentum significantly accelerates the convergence of both FEDAVG and SCAFFOLD.
Secondly, we compare four momentum- CE-LSGD, TEDAVG-M-VE (our Algorithm 3), and SCAFFOLD-ME SETFODD-M-EE M-VR (our Algorithm 4), un- der full client participation. The comparison illustrated in Figure I(b). Our proposed methods outperform MINIBATCH-STORM. and CE-LSGD with substantial margins.
variance-reducet methods: CINIBATC-SSTORM
Lastly, we investigate the case of partial client participation with $ and compare the perfor- mance of SCAFFOLD-M and SCAFFOLD-M-VE with vanilla SCAFFOLD. The results presented in Figure Icc), Once again, we observe that the introduction of momentum leads to sig- nificant improvements even when only few clients participate in each round of training.
5.2 RESNETI8 EXPERIMENTS
We further compare the above algorithms with larger model: ResNet18 (He et al., 2016) under varying data heterogeneity by setting the parameter of Dirichlet distribution as 0.5 and 0.1, respec- tively, where small parameter value suggests severe data heterogeneity. The experiment involves N 10 clients and K 16 local updates. We set S = 2 in partial client participation.
Figure 2(a) reports the test accuracy of full and partial client participation under mild data het- erogeneity while Figure 2(b) presents the counterparts under severe data heterogeneity. where the bottom right one is smoothed by plotting the best-so-far result. Again, we observe that FRDAVG-M and SCAFFOLD-M significantly outperform the vanilla FEDAVG and SCAFFOLD. Moreover, for ResNet18 and severe data heterogeneity, FEDAvG-M and SCAFFOLD-M exhibit notably greater advantages over their momentumless counterparts than for MLP scenarios under milder data het- erogeneity. The observation demonstrates amplified advantages of the introduced momentum in larger models and severely heterogeneous data, which is aligned with our theoretical predictions and suggests the promising utility of our proposed methods in real-world applications.
6 CONCLUSION
We propose momentum variants of FEDAVG and SCAFFOLD under various client participation situations and objectives' smoothness. All the momentum variants make simple and practical ad- justments to FEDAVG and SCAFFOLD yet obtain state-of-the-an performance among their peers, especially under severe data heterogeneity or small gradient variance. In particular, FEDAVG-M converges under unbounded data heterogeneity and admits constant local learning rates, giving the first neat convergence for FEDAvG-type methods; SCAFFOLD D- is the first FL method that out- performs SCAFFOLD unconditionally. Experiments conducted support our theoretical findings.

---

Published as a conference paper at ICLR 2024
REFERENCES
Sulaiman Alghunaim. Local exact-diffusion for decentralized optimization and learning. arXiv:2302. 00620, 2023.
Sulaiman A Alghunaim and Kun Yuan. A unified and refined convergence analysis for non-convex decentralized learning. arXiv preprint arXiv22110.09993 2021.
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake E. Wood- worth. Lower bounds for non-convex stochastic optimization. ArXiv, abs/1912.02365,, 2019.
Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. Vafl: method of vertical asynchronous federated learning. arXiv preprint arXiv:2007. S00i::2007.00881,, 2020a.
Xuxing Chen, Tesi Xiao, and Krishnakumar Balasubramanian. Optimal algorithms for stochas- tic bilevel optimization under relaxed smoothness conditions. arXiv preprint arXiv:2306. 2023.
Yujing Chen, Yue Ning, Martin Slawski, and Huzefa Rangwala. Asynchronous online federated learning for edge devices with non-iid data. In 2020 IEEE International Conference on Big Data (Big Data), pp. 15-24. IEEE, 2020b.
Ashok Cutkosky and Francesco Orabona. Momentum-basse variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topcu. Faster non-convex federated learning via global and local momentum. In Uncertainty in Artificial Intelligence, pp. 496-506. PMLR, 2022.
Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120-136, 2016.
Alp Emre Durmus, Zhao Yue, Matas Ramon, Mattina Matthew, Whatmough Paul, and Saligrama Venkatesh. Federated learning based on dynamic regularization. International Conference on Learning Representations, 2021.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning with the- oretical guarantees: A model-agnostic meta-learning approach. Advances in Neural Information Processing Systems, 33:3557-3566 2020.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex op- timization via stochastic path integrated differential estimator. In Advances Neural Information Processing Systems, 2018.
Ilyas Fatkhullin, Alexander Tyurin, and Peter Richtárik. Momentum provably improves error feed- back! arXiv preprint arXiv:2305.15155. 2023.
Zhishuai Guo, Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the adam family. arXiv preprini urXiv:2112.03499 2021.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Feder- ated learning with compression: Unified analysis and sharp guarantees. In International Confer- ence on Artificial Intelligence and Statistics, pp. 2350-2358. PMLR, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Yutong He, Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and accel- crated algorithms in distributed stochastic optimization with communication compression. arXiv preprint NXXv:2305.07612 2023a.
Yutong He, Xinmeng Huang, and Kun Yuan. Unbiased compression saves communication in dis- tributed optimization: When and how much? In shirth-eeventh Conference on Neural Information Processing Systems, 2023b.
10

---

Published as a conference paper at ICLR 2024
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.06333. 2019.
Kun Huang, Xiao Li, and Shi Pu. Distributed stochastic optimization under a general variance condition. arXiv preprint arXiv:2301.12611 2023.
Xinmeng Huang, Ping Li, and Xiaoyun Li. Stochastic controlled averaging for federated learning with communication compression. In The Twelfth International Conference on Learning Repre- sentations, 2024.
Jiayin Jin, Jiaxiang Ren, Yang Zhou, Lingjuan Lyu, Ji Liu, and Dejing Dou. Accelerated federated learning with decoupled adaptive optimization. In International Conference on Machine Learn- ing, pp. 10298-10322. PMLR, 2022.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Ad- vances and open problems in federated learning, Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebas- tian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv:2008.0366 03606, 2020a.
Sai Praneeth Karimireddy, Satyen Kale. Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143. PMLR, 2020b.
Prashant Khanduri, Pranay Sharma, Haibo Yang. Mingyi Hong, Jia Liu, Ketan Rajawat, and Pramod Varshney. Stem: A stochastic two-sided momentum algorithm achieving near-optimal sample and communication complexities for federated learning. Advances in Neural Information Processing Systems, 14:6050-6061. 2021.
Geeho Kim, Jinkyu Kim, and Bohyung Han. Communication-effiieenn federated learning with ac- celeration of global momentum. rrXiv:2201003122 2022.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Confer- ence on Machine Learning, pp. 5381-5393. PMLR, 2020.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint /610.0600.0550
2016.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Master's thesis. Department of Computer Science, University of Toronto, 2009.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and sys- tems, 2:4, 2020.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. In International Conference on Learning Representations, 2019.
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local sgd with lower communication complexity. arXiv preprint arXiv: 1rXiv:1912. 12844, 2019.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. In International Conference on Learning Representations, 2020.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33:18261-18271 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficcee learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, 2017a.
11

---

Published as a conference paper at ICLR 2024
H. B. McMahan, Eider Moore. Daniel Ramage, Seth Hampson, and Blaise Agüira y Arcas. Communication--ffiiiee learning of deep networks from decentralized data. In AISTATS, 2017b.
Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances Neural Information Processing Systems, 34:14606-14619, 2021.
Tomoya Murata and Taiji Suzuki. Bias-variance reduced local sgd for less heterogeneous federated learning. In International Conference on Machine Learning, pp. 7872-7881, PMLR, 2021.
Edward Due Hien Nguyen, Sulaiman A Alghunaim, Kun Yuan, and César A Uribe. On the perfor- mance of gradient tracking with local updates. arXiv:2210.04757, 2022.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pp. 2613-2621. PMLR, 2017.
Kumar Kshitij Patel, Lingxiao Wang, Blake E Woodworth, Brian Bullins, and Nati Srebro. Towards optimal communication complexity in distributed non-convex optimization. Advances in Neural Information Processing Systems, 35:13316 13328, 2022.
Krishna Pillutla, Kshitiz Malik, Abdel-Rahman Mohamed, Mike Rabbat, Maziar Sanjabi, and Lin Xiao. Federated learning with partial model personalization. International Conference on Machine Learning, pp. 17716-17758, PMLR, 2022.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr compu- tational mathematics and mathematical physics, 4(5):1-17, 1964.
Shi Pu and Angelia Nedić. Distributed stochastic gradient tracking methods. Mathematical Pro- gramming, pp. 1-49, 2020.
Sashank J Reddi, Zachary Charles, Manzil Zaheer, 7achary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2021.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-efficcii federated learning method with periodic averaging and quan- tization. In International Conference Artificial Intelligence and Statistics, pp. 2021-2031. PMLR, 2020.
Elsa Rizk, Stefan Vlaski, and Ali H Sayed. Privatized graph federated learning. arXiv:2203.07105, 2022.
Sebastian Urban Stich. Local sgd converges fast and communicates little. In International Confer- ence on Learning Representations, 2019.
Canh T Dinh, Nguyen Tran, and Josh Nguyen. Personalized federated learning with moreau en- velopes. Advances in Neural Information Processing Systems, 33:21394-21 2020.
Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang. Towards personalized federated learning-
IEEE Transactions Neural Networks and Learning Systems, 2022.
Janyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of local- upcate sgd algorithms. The Journal of Machine Learning Research, 22(1):9709 9758, 2021.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 13:7611-7622 2020a.
Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. SlowMo: Improving communication-effoee distributed sgd with slow momentum. In International Conference on Learning Representations, 2020b.
12

---

Published as a conference paper at ICLR 2024
Ran Xin, Usman A Khan, and Soummya Kar. An improved convergence analysis for decentralized online stochastic non-convex optimization. IEEE Transactions on Signal Processing, 2020.
Chenhao Xu, Youyang Qu, Yong Xiang, and Longxiang Gao, Asynchronous federated learning on heterogeneous devices: survey, arXiv preprini urXiv:2109.042000 2021a.
Xu, Zhu, Y. Soh, and L. Xie. Augmented distributed gradient methods for multi-agent op- timization under uncoordinated constant stepsizes. In /EEE Conference on Decision and Control (CDC). pp. 2055-2005000 2060, Osaka, Japan, 2015.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. FedCM: Federated learning with client-level momentum. arXiv:2/06. 10874, 2021b.
Yan Yan, Tianbao Yang. Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic mo- mentum methods for deep learning. In International Joint Conference on Artificial Intelligence, 2018.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker partici- pation in non-iid federated learning. In International Conference Learning Representations, 2021.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis communication efficient mo- mentum SGD for distributed non-convex optimization. In International Conference Machine Learning, pp. 7184-7193. PMLR, 2019a.
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, 2019b.
Kun Yuan, Bicheng Ying, Xiaochuan Zhao, and Ali H. Sayed. Exact diffusion for distributed opti- mization and tearning-part i: Algorithm development. IEEE Transactions on Signal Processing, 67:708-722 2019.
Kun Yuan, Sulaiman A Alghunaim, Bicheng Ying, and Ali H Sayed. On the influence of bias- correction on distributed stochastic optimization. IEEE Transactions on Signal Processing, 2020.
Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. DecentLaM: Decentralized momentum sgd for large-batch deep training. International Confer- ence on Computer Vision, pp. 3009-3011 2021.
Kun Yuan, Sulaiman A Alghunaim, and Xinmeng Huang. Removing data heterogeneity influence enhances network topology dependence of decentralized sgd. Journal of Machine Learning Re- search, 24(280): 2023.
Nesterov Yurri. Introductory Lectures Convex Optimization: A Basic Course. Kluwer Academic Publishers, Norwell, 2004.
Xinwei Zhang, Mingyi Hong. Sairaj Dhople, Wotao Yin, and Yang Liu. FedPD: A federated learning framework with adaptivity to non-iid data. IEEE Transactions on Signal Processing, 69:6055- 6070, 2021.
Fan Zhou and Guojing Cong. On the convergence properties of k-step averaging stochastic gradi- ent descent algorithm for nonconvex optimization. arXiv preprint 1708. 01012, 2017.
13

---

Published as a conference paper at ICLR 2024
A PRELIMINARIES OF PROOFS
Let F = 0 and Fi == (2 Josjsk U F²) and F = o(U,F; for all where a o()) indicates the o-algebra. Let E,1. == : [ be the expectation, conditioned on the filtration F³, with respect to the random variables (S", (c. ( hoigN.os<<k] in the r-th iteration. We also use E|-] denote the global expectation over all randomness in algorithms. Through out the proofs, use E; to represent the sum over i E [I,...,NN while Lies" denotes the sum over i E S Similarly, we use Σx to represent the sum of k E {O...., K - 1}. For all 2 0, we define the following auxiliary variables facilitate proofs:
& = |||| f(x")(")))))))))"))) g**],
U, 1
NK ΣΣ
Bllla x 1111
G = 1|x k+1 2. 1
E, $11KT9913
ElIE Vf (11]
We remark that quantity V, is only used in the analysis of SCAFFOLD based algorithms. Through- out the appendix, let A f(=²)= Go == 3/4 E, (z x- == 2d and E-1
[[I[V[(x') go1|²]. We will use the following foundational lemma for all algorithms.
Lemma 5. Under Assumption 1, > S b44 the following holds all 2
117 E Vf(*))
13%
Eff(x++)) - B[f(x') 24
24 Ep.
Proof. Since f is L-smooth, we have
)( + x x²) + L
マ 2 r+ 1 x²11
L
=5(x²) , V)(")
g
+ 2
11
Since x² x- 71 using Young's inequality, we further have
f(x+11)
Sf(x")
?
1Vv 2 [Vf((") ( 112)
2
117
137
<f(x")
|
+
24
24
where the last inequality is due to L S 24 Taking the global expectation completes the proof.
To handle local updates and client sampling, we will also use the following technical lemmas.
Lemma 6 (Karimireddy et al. (2020b)). Suppose (X1. ,x] C. Rd be random variables that potentially dependent. If their marginal means and variances satisfy E[X,] μ4s and E|||X; 1 & o², then it holds that
E
X
Σ 44 i=1
+
If they are correlated in the Markov way such that E[X,|X,-11. ... I.... X1] = 44 and E[I|X;- - 11
[s] o2, i.e., the variables (X; p4) form a martingale. Then the following tighter bound holds:
27
5
Σ
x
<
2
Σ
m4
+ 2To
14

---

Published as a conference paper at ICLR 2024
Lemma 7. Given vectors U1,-.. UN E R and ē Ei= Uo if we sample & {1,-.. .N} uniformly randomly such that |S| = S, then it holds that
N ul|
1 S
N S
E
|
+
1/
S(N 1) N
SES
1=1
Proof. Letting 1[i E
S} be the indicator for the event i E S,, we prove this lemma by direct
calculation as follows:
1 Σ S
E
E
e
ii E S}
S
YES
1=1
+2 Σ (ogit.e
E
52
i<
|| +
82 N(N 11 2
S(S 1) 1)
Σ
1/2 Dj
SN
Kイj
-(S-
N
||,11 52 N(N 1)
Σ 2/
Σ
||:/1
SN
/=1
t=1
N
S 1
|uul1 + N(S - 1)
|,
S(N 1) N
S(N - 1)
N 5 1
N
||us u1I + 1|0113.
S(N
1) N
In the following subsections, we present complete proofs of our main results. For FRDAVG-M and SCAFFOLDD-M, our proofs only rely on Assumption and 3, while for FRDAVG-M-VV VR and SCAFFOLD-M- M-- our proofs rely on Assumption 2 and 3.
15

---

Published as a conference paper at ICLR 2024
B FEDAVG WITH MOMENTM
B.I FEDAVG-M
In this subsection, we present the proofs for the FEDAVG-M algorithm.
Lemma 8. If S き.. the following holds forr 2 1:
83 - = 9
L2
28'00²
E
+
1
+ NK
+ U.
B
Additionally, it holds for 0 that
23
Eo S (1- -)1
NK
Proof. For r 2 1, E, = B f( (x')
1-7
- =E (1- -9)) + (F(6E)
VF En
NK
h
= E
- [] [-iGC + BBB //(07
1
Σ
VF ( g
NK
i,k
v'). ( (I- (1-B)V -
+ +23E
Σ
NK
1
Note that (VF(x MOSAEK are sequentially correlated. Applying the AM-GM inequality and Lemma 6, we have
3 BlI(11 - (V g") 1+ - 2,3 23L +
( 0² NN
E S
1+ 2
+ZUU))
Using the AM-GM inequality again and Assumption 1, we have
3
[
3 2) E + (1+ L L' ----===--~~101 111
2
2,320²
E, S (1- - 8)
[+ 2)
+
UU
2
NK
2
2,2002
$ $(1 -1--80 (1--8),,-1 +
L
E'll" x² 11
+ 48L2U,
8
NK
< 1 86
E 12 12223
|| 2,3002
EE
NK + +43L2U
B
where we plug in - ||--- the last inequality. Similarly for r = 0.
- 112 < (1V + 1lgg" [[((--1)113 and use 7L S ah in
Eo
1
3 2
Bil[ - (xx)
+ -23² (NK + L2U0)
28202
<1 3)8
NK + 4.
Lemma 9. If < g. the following holds for r 2 0:
U, < 2ek= + K 1² 22 (1
Proof. Recall that 5h = B|r  - -ズ * | = - (11 8)g" + +VV(((a)))) Then we have
ElK - - || < 1² L 8 1113
< 82 +
16

---

Published as a conference paper at ICLR 2024
For any isisk - 1 K - 2, using 7L
1 S B(k+I) we have
3K
EII 113] S 1 B11Kc---1111 (1 -
< 2
B + (A: +
S e BlIc [|]] + 4 12
where the last inequality is by unrolling the recursive bound and using (1 + 2 S By Lemma 6, it holds that for k 2 2,
B|lbo, [13] S 2E
Σ
+ 2kT)
==
k-1
< 2k Σ
Billc + 32
3=0
< 2 [= 2km 2k72 11
This is also valid for A 0, Summing up over and &o finishes the proof.
Lemma 10. If LL 3)2 + e(BYR)) S then it holds for r 2 that
1 Σ (E, + B(I + 3 eR..
E
72eK2T2
Proof. Note that c7:00 = =n((1 B)9" + (z)x)x)))
112 < 277² (1- 11=13)211''11 12 32 Σ V
Using Young's inequality, we have for any > that
E[ITA((>")]] (1 + 3 V f. (x"->)) + (1 + - 12' - 11-
( ||
+ 2(1 21 (E, [= (11)
2 3,21² >
(E + +
Take g = and we have
E BI[V <E[]V 26(r + 1)m2 Σ (3, -(]l)/('))1 (4)
==
17

---

Published as a conference paper at ICLR 2024
Note that this inequality is valid for 0. Therefore, using (4), have
R-1
R-1
Σ
E
2
(1 - 3) 8² 1
Vf((="))
N
1=0
r=
R-1
N N
21
2(1 13)) B
32
1=0
41f - ()
EI|l /
21) 32
E||
26 1)(7 _ (Eg + II (
N
417(11 - B)²
(E +
E(1 Vf
R-2
eRGo + 2e(
Σ EE, + ((V\((()))
Rearranging the equation and applying the upper bound of r completes the proof.
Theorem 11. Under Assumption I and 3, we take go 0,
NKLA o²R
min
for any constant c E (0, 1], 7 = min
24L 6L
(5)
LA
1/2
KKL S min
1,
ByLR
Go
(BN) (SONK)
then FEDAVG-M converges as
1
LAG" LA
R
NKR
R
Here Go = N [V
DN
Proof. Combining Lemma 8 and 9, we have
8,3
E, + (7L)
2820²
E,
E
9
B
NK
+ 4,LL (2eK2E, +
22
and
2820²
51- (1-
+33L2 (2eK² + (1+ +2
NK
18

---

Published as a conference paper at ICLR 2024
Summing over r from 0 to R and applying Lemma 10,
Σ
R-1
E
1
88)
R-2
Σ E +
R-2
B
8oo NK
R
9
B
1=
+,3122
KE Σ
E, RK
(1
+ 22
==0
78
R-2
(7L)²
8
n 2
Σ E, +
4
Σ
16
B
9
252
1
R + 4680 (nKL)²
+
+((nK33))) O²R
NK
K
<
7
R-2
23
R-2
452
Σ
E, +
Σ
EII
1633 ()nKL)2RG) +
NK R.
9
y=-1
Here in the last inequality we apply
4
+ +2(kLB3))
S NK
2
and
7 S 8
K
6'
Therefore,
R-1
9
2
R-2
144
36,00 7NK
E E-1 +
E
Σ
[+(("))1++
+
7 ((8nKL)GoRR.
R.
73
r=0
Combine this inequality with Lemma 5 and we get
1 -1f(=())(((")) f(x))(())))))
1 n-1
Σ E ((=))
39
E-1 Ge
78
3930² 14NK
R.
7 #=0
563
Finally, noticing that 9d = 0 implies E-1 S 2=( (-) = 2LA, we obtain
R-
LA
E-1
+ (BnnKI) + 30²
E| F[I
+
R
3R
NK
LA
LA
30²
+ +BnKL)
R
BR
NK
LA
LAGZ
+
R
NKR
B.2 FEDAVG-M-VR
In this subsection, we present the proofs for the FEDAVG-M-VR algorithm, shown as in Algorithm 3.
Lemma 12. 1fyL S / |NK
the following holds for r 2 1:
E, S (1
83
/
) + 4 1, + 3320²
NK + 6(>L)2
NK B -IIV
9
3
Also for r = 0, it holds that
4 I,P,+ + 35302
E S (1
M) +
NK
19

---

Published as a conference paper at ICLR 2024
Algorithm 3 FEDAVG-M-VER FEDAVG FEDAVG with variance-reduced momentum
Require:
initial model x = x0 and gradient estimate g", local learning rate 1, global learning rate y, momentum |
for for==0 0, ... R - do
for each client i (I...., N in parallel do
Initial local model x
for k = 0, .............................. K
do
Compute direction Sं = FF :5
:5+ + (1 3)(0" (F(x"-1:55 15xr))
Update local model x.! k r.k
199;
end for
end for
Aggregate local updates g"+1 nNK Li=1
x-' - - k
Update global model global x²+1 end for
x²= -gg
Proof.
+ +1 -0) (0-00 _ IVP())55)) Vi(xa)
& =
NK 1
NK
=E
13) vf(( + 1
NK Σ
(FRlott) NK 1 k
+(1 3)
(1- (00 - v)(6--1)) )), NK
Σ [ - -
=(1 - -3 + +2
i
A1
+
1
EVF(GA - (1 (3) | (1
1 Σ IVF(T-1;E11t))
NK
NK
k
By the AM-GM inequality and Assumption 2,
A1 ()) + L
By Assumption 2,
1 NK i
1 EVFlO -
A = E
+
NK
+ (1 - 3)
Σ
- -- -f(x') (/(0--)
NK
i
8²0²
3(1 8)² L
<3L + 3
E -=||"~~-'"
NK
NK
Therefore, for r 2 1,
4
L'U, + 3820²
+ +3(1 3)² I22
& < (1 - 8) +
NK EI|a=" - -
NK
83
9 1 + L2U, + 332
6(7L)2
< <
EE \
3
NK
NK
20

---

Published as a conference paper at ICLR 2024
The last inequality is derived by ||~" - -1- - 2 (f 2 ||| + -19"" - vf(x*-1)] 1133)
and
L S V
ANK Similarly, for & $ (1 -) 4 U NK
0, we can obtain
54
3820²
Lemma 13. lf S 4e the following holds:
U, S 4cK + ((n)))(((KI))) + 1 (5'00 + -21-1(1a--=--1111
Proof. Note that ÇT = - (V + ()- - Vf((2" Then we have
Billc - - s B11xx, - 11
= r,² [B1 + EVVaraa -
Here use bias- decomposition and Var[-I-] stands for the conditional variance. Since E[Var[æ; 2 -.
-1piE
VF (1:
-1 B) (V -1 )
[|]
Sa²² (23300² + 2(1 - -
then
Blllc [19]
< 1 L? (B 233 22 B -(,
< 1²² (111 2 L'E 201 + 1| - -15
Therefore for any s 2-
E
S 2 1 S (1+
+ |]11(<²0=111 + (1 +)EIII -h 11
<
+
2 k
B + (k: + 1)n² L2 (233 + 4n² L L EE1l - x² x2122 + 1|00 - -0 -11111
-x2)0-1131)
1 + + L3 12 (28300 + +4L'
x-- 112)) --111131 + 46 (
Σ E|l - 1--
j
Here the second inequality is by nT. < K S K+I The last inequality is by unrolling the recursive bound and using (1 +
2) < e². By Lemma 6, it holds that
1 E
r.k x=1 [|
<2EE
Σ 2
+
E (a -
1=0
j=0
<2k Σ
B
2 [13]
+ Σ
2,,32, + 1, x/1 + 1|00" 22.5121)= (7)
/=0
1=0
Summing up (7) over k: = 0,..., K 1, using (6) and 8(1TT)2 (n2( S 1/2 due to the
condition on 7), we have
B r.kk x11 s 2e 2ek "1 (8 22 2 - xx x- 111)
2K
K=O
This implies
U, < 4eK2z, + x
22 + 1
21

---

Published as a conference paper at ICLR 2024
Lemma 14. yf I 24 and 288c(nKL)² holds:
(1 B)² + 8e(1BLL))) B then the following
72
7 Σ
g
n
E
Σ
(& + =(+//(/())) + B4
288eK212
P 0
pm-1
Proof. Recall that 5: 7((1 B)(g" (V((---V=))))++ Consequenty, we have
||< 1p 2n/² ( (1--991119-1111/)))--0-000-11111
2n - --90 144
289 2
Using Young's inequality, we can obtain that for any q > 0,
[[[[{( < (1+ () (1 (1 + 1 1 r² - 112
< (1+ + <4
(T (E,,1 + IB|| ["x''\'
2 (TL)²
r-1
s (1 (1+
E(E (E) +
9
Taking g = 1 in the above, we have
y.
r-1
E E (1)) <EII 2e(r 1)
Σ (E) + ((I((((()))
f=0
This inequality holds as well trivially for 0. Therefore, we have
R
R-1
289
21
3)
|| + 30 N Σ |Vf((=")11
144
r=0
R-
289
172 -
E1
72
r=0
R-1
+ 3n
Σ
[| 20(r + 1)(7L) I (E, + EI ((>))(1
N
P=0
289
1) - 3)²
(E, +
H
V
72
7=0
R-2
2n² 82
eRGo 2e(7T.R)2
Σ
(1g B(IVS(()))
32
R-2
Σ (8, (+++ + 4n 3 eRR..
K2
Here the last inequality is due to the upper bound of r7.
Theorem 15. Under Assumption 2 and 3, if we take 9d
NB Ei=l 2b=1
VF(x0; with
rid D: and set
(St 1b=1
8 = min {a.
NKLLA
1/3
BNK
for any constant e E 1],
? min
R2
24T.
5412
LA
1/2
1/2
1/4
K
KK. S min
GoyLR
N
NK
R232
(8)
22

---

Published as a conference paper at ICLR 2024
FEDAVG-M- M-VR converges
R-1
LAo NKR
2/3
LA
Σ
Bl|
Vf{2')1
R
Alteraaively, B i and min {
h:
(NKLPA))
1/3)
then FEDAVG-M-VE converges
as
LĂo
2/3
0² LA
+
NKR
NKR
R
Proof. Combine Lemma 12, 13 and we have
8, & S (1
) + L2
NK E | 33'0²
NK K 10800000000000000000000000 22 -121)1"---111 111)
4
2 (4eK² + ((1k)) (
3
& $ (1 3) +
30-0²
N 1 L2 (4eK + (())) + +K11)33000)
Summing over from 0 to R and applying Lemma 14,
R
Σ
E
83
R-2
6(7
R--2
[+(x))? + 3.302
5(1
Er +
E
NK R
NK
h=-1
R-1
E, + 8(1n) ((())())))))) + + [R3802 + +2L2 R
Bllaa" xx -x- 1r91)
+
2
4eK² 2
Σ
Σ
3
1=
73
R-2
(6(7))
R-2
<(1
Er +
+
9
NK
1=-1
r=-1
032022
1 +2(KKD}²
R + (233((KK
o²R
NK
K
78
R-2
28
R-2
48
<(1
Σ
&
E
Σ
K4) +
NK R.
9
Here in the second inequality, we apply
32 ( + +((nK))² <
8²
NK
K + (( <
B
18:
7I. S /
BNK
54
Therefore, we obtain
R-1 E
2
R-2
+ 7 (enKL) 36,80
576
E E
E-1+
Σ
\f(x'))2
7NK R.
73
7
0=0
P--1
Combine this inequality with Lemma 5 and we get
1 - -
f(x")) <
-
Σ
R-1
39
E +
312
(en
3930² 14NK R.
56,3
7
23

---

Published as a conference paper at ICLR 2024
Finally, for 3 and thus NK
K n2
noticing that go
1 Ei
EbE vF(=";)) implies E-1 S
o² NB
NB
LA
E-1
Ao²
+
+nnKI)
YLR
BR
NK
LA
Ba²
LR
NK
LA
LA
30²
VBNKR
NK
LA
LAo
2/3
NKR
Similarly, for B = KR, E-1 S
NB E NKR
and we have
R-1
LA
E-
Ba²
|[[VS("')|
+
(nKL)
+
RRR
3R
NK
LA
o²
302
LR
3NKR
NK
LA
LA
d²
Ba²
R
VENKR
BNKR NK
LA
LAo
2/3
o²
+
NKR
NKR
24

---

Published as a conference paper at ICLR 2024
C SCAFFOLD WITH MOMENTUM
C.I SCAFFOLD-M
In this subsection, we present the proofs for the SCAFFOLD-M algorithm.
Lemma 16.
If S f.. the following holds for r
2 1:
8, - +
16
4,200²
+ +100LUU + 6,52 N N-S S8
& S 1
((
>| +
Vr.
9
SK
S(N - 1)
In addition,
E, $ (1 -1-11) -3)-1++ 0f
+ 8 + 4.8 N 5-5 S
S(N - 1) Vo-
SK
Proof. Note that
1 N
E ci = c² holds for any r 2 0. Using Lemma 7, we have
N
E, =
(x(')
1
Σ
St
N S
E
9
k
of
NK
S(N 1) N
NK
i
k.k
E
1- --
- +B
1
Σ
V ((x'))
NK
A1
BN - 5) 1
E
VF
VF
-
-
S(N - 1) N
K
NK
3.k
A2
For 2 1, similar to the proof of Lemma 8, we have
2
282002
A S (1 3)
+43L'U,..
NK
Besides, by AM-GM inequality and Lemma 6,
1 E
1
Aa S
Σ
of
N
K
.2
20
+
2
Σ E
1 1
Σ
((( -
K
N
K
20
S
+ =6(,, + 1, R - 119 + Vr).
K
Since E[[| 112]
< 2 (E,-1 + V/ and (3 + 3(N 2(7 5
N-S
16
22 < g. we have
8,
16
2 | (f 1 |111+ + 4520²
SK + 103T,3U, + 6,3² S V,.
& < 1
E, (7
1)
9
B
5(N - 1)
The case for 0 is similar.
Lemma 17. 1f < 723 and 1KT, T. S 4. it holds for all 2 that
U, S 1²² 22 (Se(E,-1 + 2 V fx - ~1p- + v.) + 3 0² (K-1 +
Proof. Since Gt Elu x k ,o = -n [x
(1 B)gr -B(c - d²)) and
Varlz] x-r T. b
S 022 with exactly the same procedures of Lemma 9, we have
U, < 2e = + 82p + 2k ,,,,,
25

---

Published as a conference paper at ICLR 2024
Additionally, by AM-GM inequality,
E, [lllVV(((=)++ + (1 -1-331--- - c')1']
7 N Σ E [[I((V)((')) - V/(C0 -/<() + (1- B)(5" ()((--1))
-8 (c) c' - Vf(c2' VV - Vf
S 41 2 (5 L' - ( =
S 4n 2B ()
Plug this inequality into the above bound completes the proof.
Lemma 18. Under the same conditions of Lemma 17, if KT S 24 and nnK S
N 53 7,
then we
have
R-1
3N
4SR
8N
R-2
Σ
V
Vo +
0²
(nL)
Σ
(E+ =(V
s
NK
S
T=0
Proof. Since
=
cf
with probability
1 with probability $ N
$
1 En VF
N
using Young's inequality repeatedly, we have
N
V1+1
1
S
EllG
SI
Σ E
-
N
NN
K
1=1
S
N
(20²
Ell
V((T"))+
+ +2L2U,
N
N
N K
S
Σ E
11
S
1 - v/ + 1
2N
1 1 |2" - 11-
N
N
2N
s
==1
25
d2
L2U,)
N
K
S
V,+ 2.N
2So²
28
12?,,.
2N
NK
N
Here we apply Lemma to obtain the second inequality. Combine this with Lemma 17,
16e N ((onKL)) V + 20
2S
(K- +((n)(())))+))))))))))) 2(3
V++1 <
1 -
+
NK + N
2N
+
4N
(7L) + 32eS
(nKL)))
(E, (6-1-1IV((==))11
S
N
(1-
4S
SN
-1-30 3N/
V,
NK 0
S (TL) + BII
where we apply the upper bound of n, Therefore, we finish the proof by summing up over r from 0 to R 1 and rearranging the inequality.
Theorem 19. Under Assumption and 3, if we take 9o = 0. cf = EE v=(2"; gb) with
B üd D., cº = 1/2 ENI of and set
S
LASK
LAS²
7 L' B min
C,
N2/3' V
R2R
|V GoN
S1/2
NK
KL S min
B
51/2' 3K1/4'
N
SR
26

---

Published as a conference paper at ICLR 2024
then SCAFFOLD-M converges
R-1
LAo2 SKR
LA R
N2/3
+
1+
R
S
Proof. By Lemma 16, sum over r from 0 to R
1 and plug Lemma 17, Lemma 18 in,
Σ E
R-1
1
8.
Σ
R-2
&
16
(72)
R-2
E ((
7=0
r=0
4.3g02
R-1
N S R-1
R R+ 103L2
Σ
U, + 6,9
Σ Vr
SK
S(N - 1 1=0
< 1
83
16 Σ Er +
R-2
R-2 =/g (TL) + (60
+ (0e3()
Σ f(')((=))
9
1=-1
+ B02OR
R
4
+ +1GRED)(KK+++60R00)))
+
SK
N S S
R-1
+ +.3
+ 80eB(nKL))
Σ Vr
S(N 1)
11 <
73
Σ & + ( [+ +
R-2
16
3
Σ
R-2
B||Vf(=*)1
803302
R +
30,32 N
Vo-
9
SK
S
r=
Here the coefficients in the last inequality are derived by the following bounds:
160e3()KL)2 + 24( م ya (6 SIN- + 80e 30e,((KK)))) S 5
10(nKL)((K 2(3nKL) 960e (nKL)² < 4
SK:
80eB(nKT.) 5
which can be guaranteed by
S 53/2 BoPTN:
nKL 2 31/3.
Therefore,
Σ
R-1
E 73
9 E-1
E
Σ
R-2
2703N
V. + 72030²
R.
7S
7SK
Combining this inequality with Lemma 5, we obtain
1 -B((((() (((0) < - Σ BIIVS(
R-1
39
585,NN
390Bo²
E-1
Vo +
R.
5633
28.52
7SK
Finally, noticing that 9d = 0 implies & S 2LA and G = we reach
1
V
Fx 5 implies Vo < g² B
S
B
SRo² NK
R B
LA
E-1
IN
30²
+
Vo +
R
LR
3R
S²R
SK
LA
LA
30²
N/1/2
3R
53/2R
SK
LA
N2/3
T.A02
+
R
S
SKR.
27

---

Published as a conference paper at ICLR 2024
C.2 SCAFFOLD-M MR
In this subsection, we present the proofs for the SCAFFOLD M- VR algorithm, shown as in Algo- rithm
Algorithm 4 SCAFFOLD--M-VE SCAFFOLD with variance-reduced momentum
Require: initial model x learning rate 77, global learning rate ", momentum 3 for = 0....... R 1 do
gradient estimator gb, control variables (c]) and c local
Uniformly sample clients S, S (I, with |S, =
for each client i S, in parallel do Initialize local model rr,00 xx for k: = 0, ... K do
Compute 9. r V F(
c - B(e - c²)) + (1 3)0 - vF(x"-1, ((:
15
Update local model x. 22j r.h
-19:; r.k
end for
Update control variable et = K En VF ; (for i Sr. c))
end for
Aggregate local updates g² WSK Eies, xx" (x"-2; xxt
Update global model -=+ = x² - 79"
Update control variable t1 cº + N Eies, (ctt1 -c] end for
Lemma 20. If S
V
126
38
then the following holds for r 2 1:
83
14
8
78202 4(N - -5) 3
E 5
1+
E
E[IVf(=-~
U
SK +
9
S
B
S(N - 1)
In addition,
8
7
4(N S) 3
& S (1 - B)E-1 + 1. +
SK
5(N 1)
Proof. By Lemma 6, we have
E, < E
Vf(x')
Σ
v
NK
k
+ -
N
Σ E
V (1--
9c,
S(N 1) N
K
k
Applying the same derivation as Lemma 12, we can show that
4
82
2
A - (1 - 3)E,11 + T, + + 3(1 - 8)²
E Blll - 11)
8 NK
NK
28

---

Published as a conference paper at ICLR 2024
Additionally, by the AM-GM inequality,
A2 -
AE
1
:47")) -
VF
K
(F('' V (: -c]1
+ B²
K
k
B(V - Vfi(2' 1- 3
- VF :
+
K
<a(LU,, L2U
880²
+ 3V + L L3 - 1111 119)
K
Further notice that for r 2 1, B[||=" - 112 1 2272(E, + / 1))
and
8(N 8) 6(1 - 3)3 ) -s 14(7L)² B
(7l))
S(N 1) NK
5 9.
Hence we obtain
83
14(;
8 T. 7 02
4(N 8) 8ºV,
& S (1
BIIV (x 1112
9
S
SK
S(N 1)
The case for r = 0 can be established similarly.
Lemma 21. If <
1
nK <
YN 10
and L S 1.
then it holds that
Te'
24.
R-1 1
3N
4
6.N
R-2
Σ r=0
Vr S
Vo +
0² +
LT) Σ
(E2 +
S
NK
s
r=-1
Proof. Note that 4 = -- (V[((t + + (1-3) -)i((=-1)) - B(G - c))), with the same procedures in Lemma 13, we have
U, S =e + 8(1K )( (2 -- ( + 22 21'11112" - x- 1-1))
Additionally, by the AM-GM inequality,
2 N 3, BlIV (1 (1- 3) vf((2-11 - B(c - -c']
n
[[((((()))) V (1 B)(3" vf((=-11)
N
-B B (c) c -/ V/
Vf 11
< E -1
< + 1111
V + [V}
Hence, by applying 32( + < 2, we obtain
U, S "0<
+ ( 221""l1'' - 121
(10)
< ()( (E,- + E| V
8V,, + ((3n)) (2(nk<)))))))))) + 102
Also, similar to Lemma 18, still holds that
S
2N
2S0² + 2$ L?
VA+1 S
1
V, +
- 1
1.
2N
5
NK
N
29

---

Published as a conference paper at ICLR 2024
Combine this with the upper bound of U,,
V
S
180(3nKT)25)
V,+ (AN( 180(nKT)) S +
+
2N
N
N
0²
28
=(65KL))((kL))+++ +K-))
NK
S
6N(
4So²
V, +
S (E-_1 + /
+
3N
NK
where we apply the upper hound of in the last inequality. Iterating the above inequality completes the proof.
Theorem 22. Under Assumption and 3, if we take cf=
1
Eb
VF(+9;
with ( in D..
B
gd = &V Em=1
of and set
min
1
VBS
B = min
IS N
KLA
2/3
S1/3
T L
(11)
(3
1/2
3
1/4)
SK
NK)
K T. S min
B =
max
SK
N R332'
SR
CCAFFOLD-M-VE VR converges as
1 R-1
LAo
2/3
LA ( N1/2
Σ
+
1+
R
SVKR
R
S
Alternatively, R and 3= min { converges as
N S
(KIA)Z
(FR
(KLA
2/3
$1/3
J.
B
O (N))
)
SCAFFOLD-M-VR
LAo
2/3
LA
N1/2 0²
1+
R
SVKR
R
5
SKR
Proof. By Lemma 20, sum over from 0 to R - 1 and plug (10), Lemma 21 in,
R-1
83 E,
R-2
1)
R-2
73
Σ E S1
E
SK R
9
S
0=
8
2
R-1
U, 4
N S
R-1
Σ
V,
S(N - 1)
83
(nKL)²
R-2
E 14(7L)3
(2KL)2 R-2
S
720
Σ
+ 720
E
V f(>")\
9
B
S
3
r=-1
7
64(nKL)²
8 2R R
(K + +((KL)31
SK
B
3 (4(N- - 5)
(nKL)²
720
Σ
V,
S(N - 1)
B
< 73 R-2
9 Σ E 14(7L)2
3
R-2
8202
B
60
R
+ 15
Vo.
S
9
SK
52
30

---

Published as a conference paper at ICLR 2024
Here the coefficients in the last inequality are derived by the following bounds:
720 (2
B + 18( BaL y² (4 5(N-1) 720
(nKL)*
B
9
+ 64 (4( (K-1+ 2(nKK)²) + 8640 ()
B
OK
SK 1
720 (nKL)² B S s
which can be guaranteed by
y 2
ga12 31/2N1
KT S min(y
1 )1/2).
Therefore, it holds that
R
R-2 |V((")|
1353N
540,0² 2
E 73
Σ
E
+
V/ +
R.
7,5
7SK
r=0
Combine this inequality with Lemma 5 and we get
[[] -f(x0)(( - - |
1 R-1
Σ
39
E-1 + 5853N
V.8 +
585
14SK R.
563
56.
Finally, for = max { SK
NK sn
}1. noticing that 9¹
NB Σ.D VF : implies E-1 1
NR
8²O²R R and Cj = 13 E. V (xx:; (c) implies Vo
0²
S
SR
we reach
NB
SK
B
NK
LA
E-
3N
302
B[]Vf(>')
+
Vo +
LL
BR
5
SK
LA
LA
LA
Bo²
N3
R
(B5)
53/2R
SK
LA
N1/2
LAO
2/3
1+
R
S
S/KR
Similarly, for B = SKR
and R RZ43
N
8-1
S
S
g²
Vo
S o²
S
No² SKR
and thus we have
3
NE
3KR
B
R
LA
E-1
3N
30²
11)
+
V. +
R
LR
3R
S2R
SK
r=0
LA
LA
LA
302
N22122
+ 3SKR2
R
(BS)
53/2R
SK
LA
N1/2
LAO
2/3
0²
1
+
+
R
S
SVRR
SKR
31

---

Published as a conference paper at ICLR 2024
D IMPLEMENTATION DETAILS & MORE EXPERIMENTS
D.1 TRAINING SETUP OF MLP
We generate non-iid data for the clients, we sample label ratios from the Dirichlet distribution (Hsu et al., 2019) with parameter of 0.5 for the full participation setting and 0.2 for the partial participa- tion setting. Our experimental setup involves N decay is set as 10-4, The global learning rate is fixed as 1 for all the algorithms, and we perform grid search for the local learning rate 1j values {0.005, 0.01, 0.05, 0.1, 0.5}. Similarly, search for the momentum parameter in values {0.1, 0.2, 0.8..
clients and K 32 local updates. The weight
D.2 TRAINING SETUP OF RESNET18
We generate non-iid data by setting the parameter of Dirichlet distribution as 0.1, which implies higher heterogeneity. The experiment involves N 10 clients and K 16 local updates. We set S = 2 in the partial participation setting. The local learning is fixed as = 0.001 and global learning rate 7 i.k The momentum parameter is / = 0.1 and batchsize 128.
Reparameterizing momentum. transformation of hyperparameters of
The update rule of FEDAVG-M M in (1) is equivalent to, with 91 18, 9" = g" /B Bn, 9 : Br,
.r. 03
VF
3)g",
23 r.1 x/t 9, x++1 = ="" -g
This is typically used in the current Pytorch implementation of momentum--assed methods. When
3 = still reduces to vanilla FEDAVG. Similarly, in SCAFFOLD-M, the update rule (3) is equivalent
(VF(2)) (/ (1- -1
In all the experiments ResNet18, implement our proposed FEDAYG-M and SCAFFOLD-M with this reparameterization.
D.3 MORE EXPERIMENTS OF RESNET18
We conduct more algorithms under mild heterogeneity with the parameter of Dirichlet distribu- tion being 0.5. We set S 5 in the partial participation setting. Other hyperparameters the same as described Section D.2. We plot the evolution test loss in Figures 3(a) and 3(b), re- spectively. Again, vanilla FEDAVG and SCAFFOLD with evident margins. We also evaluate VR methods terms of test accuracy in the context of full client participation. The results presented in Figure 4, which demonstrates the advantage of our proposed VR methods over the prior methods.
observe that proposed FEDAVG-M and SCAFFOLD-M. outperform the
2.25
FedAvg
2.25
FedAvg
2.00
FedAvg-M
2.00
FedAvg-M
Scaffold
Scaffold
1.75
1.75
Scaffold-M
Scaffold-M
1.50
1.50
1.25
1.25
1.00
1.00
0.75
0.50
0.50
0.25
10
20
30
40
50
60
10
20
30
40
50
60
(a) Full participation
(b) Partial participation
Figure 3: Test loss of ResNet18 versus the number of communication rounds
32

---

Published as a conference paper at ICLR 2024
0.8
0.7
MB-STORM
CE-LSGD
Fed
0.4
Scaffold-M-VV
0.3
0.2
0
10
20
30
40
50
60
Figure 4: Comparing the test accuracy VR methods with ResNet-
D.4
EXPERIMENTS WITH MORE CLIENTS
Fed/wg
Fed/vg
2.25
FedAwg
2.0
FedAug-M
2.0
FedAug-M
2,00
FedAug-M
Scaffold
Scaffold
Scaffeld
Scaffold-M
Scaffold-A
1.75
Scaffeld-M
1.50
1.0
1.00
0.75
0.5
0.25
10
20
30
40
50
10
2.0
30
40
50
60
10
20
30
40
50
(a) Full participation
(b) Partial participation, S = 10
(c) Partial participation, S
Figure 5: Test loss of MNIST versus the number of communication rounds
0.7
0.6
0.6
0.4
FadAig
0.4
FedAvg
0.4
RedAvg
FedAingMM
FedAugg
0.3
FedAwo
Scaffold
Scaffold
Scaffeld
Scaffold
Scatfold
Scaffeld-M
(a) Full participation
(b) Partial participation, S
(c) Partial participation, S
Figure Test accuracy MNIST versus the number of communication rounds
We further conduct experiments with N 100 on the MNIST dataset and two-layer fully connected ReLU neural network. The parameter of Dirichlet distribution is 0.2 and the batchsize is 32. We set the number of local steps K 16. For FEDAVG-M and SCAFFOLD-M. we set plot the test loss and test accuracy of our proposed algorithms in the regime of full participation (S N) and partial participation (S 10 and S = 5). The results are shown in Figure and 6. Compared to former experiments where N, observe that our proposed momentum-based algorithms scale well to FL setups with large N. Moreover, we observe that the advantage of our momentum-basee variants over the vanilla FEDAVG and SCAFFOLD becomes more evident when fewer clients participate in training, suggesting a great utility of our algorithms in practical FL setups.
0.2. We
33

---

Published as a conference paper at ICLR 2024
D.5 IMPACT OF MOMENTUM VALUE 3
To further illustrate the effect of momentum, we examine different choices of in both FEDAVG- M and SCAFFOLD-M under partial participation setting with S 5 and N 100. We again simulate with the MNIST dataset and two-layer fully connected ReLU neural networks. The results are shown in Figure 7 and 8. is worth noting that when - 1, the momentum will anneal down to off, recovering the vanilla FEDAVG and SCAFFOLD. We observe that the stronger the momentum used, the better performance we eventually obtain. This directly demonstrates the benefit of momentum.
2.25
B 0.9
B 0.9
2.00
0
2.00
- 0.5
0.5
0.3
=
1.50
1.50
B 0.1
1.25
1.00
1.00
0.75
0.75
0.50
0.50
0.25
0.25
30
20
30
(a) FEDAVG-M
(b) SCAFFOLD-M
Figure 7: Test loss versus communication rounds with different momentum values
0.9
0.8
0.8
0.7
0.6
0.5
0.9
0.4
0.4
0=0.7
0=5
0=5.5
0.3
0.2
0.3
B
0.1
0.2
0 0.1
10
20
30
40
50
0
10
20
30
40
50
(a) FEDAVG-M
(b) SCAFFOLD-M
Figure 8: Test accuracy versus communication rounds with different momentum values
34


Reviews:
[{"review_id": "ib2oHVna9s", "reviewer": "Reviewer_XBW2", "summary": "This paper focuses on the FedAvg and SCAFFOLD algorithm in federated learning. In literature, many works that analyze the performance of these two algorithms have to rely on bounded heterogeneity assumptions, which is unrealistic. In this works, momentum methods is employed to solve the data heterogeneity issue in federated learning. Without any other modification on Fedavg and SCAFFOLD, plain SGD with momentum updates can achieve similar convergence rate as literature. Furthermore, this work show that in the setting of partial client participation, momentum update can accelerate convergence.", "questions": "What is the major difference or difficulty of SGD momentum analysis compared to Adam algorithm? Reddi, Sashank, et al. \"Adaptive federated optimization.\" arXiv preprint arXiv:2003.00295 (2020)", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This work overcomes one of the most common problem in FL analysis, the data heterogeneity issue. Although a lot of works in literature analyzes the convergence result of the two algorithm, most of the works have bounded heterogeneity assumptions. This is the most basic problem in FL analysis. This work utilizes momentum method to overcome the difficulty.\n2. The experiment result is encouraging and directly validate the theory.", "weaknesses": "The major concern is novelty. FedAvg and SCALFFOLD are well-known methods in FL. Momentum method is also a popular optimization algorithm. Thus the algorithm design lacks novelty. Further, some work has analyzed the performance of FedAvg with Adam update, e.g, Reddi, Sashank, et al. \"Adaptive federated optimization.\" arXiv preprint arXiv:2003.00295 (2020). Adam algorithm is closely related to SGD with momentum, thus the proposed analysis lacks novelty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "g45b1bQZcN", "reviewer": "Reviewer_ELLH", "summary": "This paper studies the impact of adding a simple momentum term to standard Federated Learning algorithms (namely, FedAVG and SCAFFOLD) to mitigate client drift by \"anchoring\" local gradients closer to an estimate of the gradient of the global function computed at the server side. State-of-the-art convergence rates are obtained in the non-convex and smooth setting, without relying on the common assumption of bounded data heterogeneity. Variance-reduced extensions of the algorithms are also studied. Baseline empirical evaluations of the methods are provided with a three-layer MLP and a ResNet18 on CIFAR-10, hinting that the introduced momentum term does indeed help generalizing on test data.", "questions": "* Does the performances of adding a momentum scales to settings with greater values of $N$ ? (Or does scaling leads to a collapses as could be observed for SCAFFOLD, see Fig.10 of [[3]](https://arxiv.org/abs/2102.02079 ) )? \n* Although the last sentence of section 1.2 states *\"The analysis presented in this work distinguishes from [[4]](https://arxiv.org/abs/2305.15155)\"*, [[4]](https://arxiv.org/abs/2305.15155) state in their paper that *\"We also hope that our proof techniques can be useful to establish linear speedup for other classes of distributed methods, e.g, algorithms based on local training such as SCAFFOLD and ProxSkip without relying on data similarity assumptions.\"* Thus, it raises the question: how different is your analysis from [[4]](https://arxiv.org/abs/2305.15155) ?\n\n**Typos:**\n\n* after equation (1): *\"represents a~n~ global gradient\"*.\n* Second line of the proof of Lemma 5: the scalar product seems to be missing a term, shouldn't it rather read $\\gamma \\langle \\nabla f(x^r), \\nabla f(x^r) - g^{r+1} \\rangle$  ? (this does not impact the following lines)\n\n\n**Final comment:**\n\nI recognize the interest of the theoretical contributions of this paper, thus, I am ready to increase my score if my concerns concerning the convergence rates and the experiments are correctly addressed.\n\n[4] Ilyas Fatkhullin and Alexander Tyurin and Peter Richtárik. *Momentum Provably Improves Error Feedback!* ArXiv eprint 2305.15155, 2023.\n\n=== **After Rebuttal** ===\n\nMy concerns and questions were correctly addressed by the authors, I subsequently raise my score and recommend to accept this paper.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* **SOTA CV rates:** State-of-the-art convergence rates are obtained for the introduced methods.\n* **No data heterogeneity assumption**: The proof technique gets rid of the bounded data heterogeneity assumption, improving theoretical convergence rates and hinting that the method mitigates the impact of arbitrary data heterogeneity.\n* **No additional uplink load**: The introduced momentum term is simple, its effect is intuitive to understand, and does not lead to any additional client to server communication.\n* **Constant step-size:** If the training is sufficiently long ($R$ sufficiently high), the theoretical analysis allows for a constant step size for the stochastic gradients (contrary to vanishing ones standard in the literature).\n* **VR variants:** Variance-reduced variants of the methods are presented and analyzed.", "weaknesses": "* **Algorithm not new**: Contrary to what is claimed in section 3.1 (*\"resulting in the new algorithm FEDAVG-M\"*), the added momentum is not new: FedCM [[1]](https://arxiv.org/pdf/2106.10874.pdf) is exactly the same algorithm as FedAVG-M, although their theoretical analysis does use the bounded heterogeneity assumptions. Comparison with FedCM rates is lacking in Table 1.\n* **Surprising rates for the VR variants**: [[2]](https://link.springer.com/article/10.1007/s10107-022-01822-7) states that *\"every randomized algorithm requires $\\mathcal O \\left( \\frac{\\Delta L \\sigma}{\\epsilon^3} + \\frac{\\Delta L}{\\epsilon^2} + \\frac{\\sigma^2}{\\epsilon^2} \\right)$  oracle queries\"*, however, the rate reported in Table 1 and Theorem 2 for FedAVG-M-VR seems to improve on this lower bound as a it leads to an oracle complexity of $\\mathcal O \\left( \\frac{\\Delta L \\sigma}{NK \\epsilon^3} + \\frac{\\Delta L}{\\epsilon^2} \\right)$. Setting aside the variance-reduction effect of running a distributed algorithm (leading to the $NK$ term), is it normal to get rid of the $\\frac{\\sigma^2}{\\epsilon^2}$ term or am I wrongly worried ? (This question also holds for the VR version of SCAFFOLD-M)\n* **Experiments seem light:** A value of $N=10$ is pretty low for the standards of the literature in Federated Learning (see, e.g., experiments in [1] where a value of $N=100$ is used), especially since a different behavior for the optimization algorithms can be expected at scale in the partial participation setting (see, e.g. [[3]](https://arxiv.org/abs/2102.02079 ) ). Are the runs averaged over several random seeds ?\n* **Additional downlink load**: Although no additional client-to-server communication is necessary, the server-to-client communications are doubled in size with the addition of the momentum for FedAVG-M.\n* **Lacking discussion on link between $R$ and $\\beta$**: While a constant step-size can be considered for sufficiently high values of $R$, the direct corollary is that, before that regime arrives, Theorem 1 sets a value of $\\beta=1$, meaning that the theory seems to predict that the momentum could only be used for sufficiently long training. However, experiments in Fig. 2 seem to show that using a momentum would help even if the training stopped early.\n\n\n\n[1] Jing Xu and Sen Wang and Liwei Wang and Andrew Chi-Chih Yao, *FedCM: Federated Learning with Client-level Momentum*, ArXiv eprint 2106.10874, 2021.\n\n[2] Arjevani, Yossi, Carmon, Yair, Duchi, John C., Foster, Dylan J., Srebro, Nathan and Woodworth, Blake. *Lower bounds for non-convex stochastic optimization*, Mathematical Programming, 2023.\n\n[3] Li, Qinbin and Diao, Yiqun and Chen, Quan and He, Bingsheng. *Federated Learning on Non-IID Data Silos: An Experimental Study*, 2022 IEEE 38th International Conference on Data Engineering (ICDE).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "7kDdQ79Z2p", "reviewer": "Reviewer_CZuh", "summary": "This paper explores the application of momentum to enhance the performance of FEDAVG and SCAFFOLD, two leading federated learning algorithms. It achieves a faster convergence without relying on the bounded data heterogeneity assumptions and introduces new variance-reduced extensions, exhibiting state-of-the-art convergence rates.", "questions": "This paper lacks a comprehensive discussion regarding the limitations of the proposed algorithms. It is evident, for instance, that SCAFFOLD exhibits a suboptimal performance at very low sampling rates [2], leaving uncertainty regarding the extent to which the authors' improved algorithm can address this issue.\n\nPost-rebuttal Comments:\nI would like to thank the authors for their responses. Many of my concerns have been addressed, including both the theoretical and experimental analyses of the hyperparameter $\\beta$. But I may still be a little concerned with the authors' claims on their theoretical contributions of the convergence, which is particularly defeated by the faster convergence rate achieved by FedDyn (though FedDyn requires a clients’ solution optimizer). Overall, I would raise my score to 5.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper is easy to follow.\n2. The incorporation of momentum enhances the convergence rates of both FedAvg and SCAFFOLD. And this improvement has been substantiated through both theoretical analysis and experimental validation.", "weaknesses": "1. The final convergence rate achieved by the authors does not sufficiently account for the impact of the momentum coefficient. Please clarify this issue.\n2. In fact, FedDyn [1] demonstrates a faster convergence rate compared to the authors' findings in this paper, which is also without the need of clients’ variance assumptions. This observation may highlight the potential limitations in the author's theoretical contributions.\n3. The authors' work seriously lacks comparative experiments, including comparison with various momentum-based federated algorithms [2].\n4. The author's experimental work lacks a comprehensive discussion of a key hyperparameter, momentum coefficient.\n\n[1] Acar, Durmus Alp Emre, et al. \"Federated learning based on dynamic regularization.\"  ICLR, 2021.\n\n[2] Reddi, Sashank, et al. \"Adaptive federated optimization.\" ICLR, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "S0MAhdHonl", "reviewer": "Reviewer_W4SM", "summary": "Under the federated learning paradigm, this work tries to validate the effectiveness of adding a momentum item to local client updating. Specifically, in each communication round, the proposed method will require the center server to broadcast the global gradient information to all clients (along with the updated model parameters). Then, the local clients embed the global gradient information into the local updating steps as a momentum item.\n\nThe strategy is simple and straightforward, just as the title highlighted. Particularly, this work gives detailed proof to validate the effectiveness of the simple strategy, which is appreciated (but with some mistakes). This work also empirically shows the effectiveness of the proposed method through some easy experiments.", "questions": "1.\tI am totally not sure how to build the relationship between ∇fi(x) and ∇f(x) without the bounded data heterogeneity assumption. I.e., without the popular bounded data heterogeneity assumption, how the local gradient information contribute to the global convergence? Can you briefly explain it?\n\n2.\tThe second question is independent but may be correlated with the first one. I checked the proof of Theorem 1 (Theorem 11 in the Appendix), and the building of the above relation can track the source back to Lemma 5. However, the very second inequality of the proof of Lemma 5 (Page-14), which builds the above relationship, seems to be wrong to me. Considering the updating step is x^{r+1} = x^{r} – γg^{r+1}, the item −γ||∇f(x^{r})||2 comes out from nowhere, and the sign of the item γ⟨∇f(x^{r}),g^{r+1}⟩ should be negative, and it is the real descent item.\nThen, without Lemma 5, the most important result in this work, Theorem 1, may be wrong.\n\n3.\tThis work uses Young’s inequality four times (Page 14, 17, 22 and 25), but actually, I am not really sure how to get the derived inequality by applying Young’s inequality each time. Please elaborate on each one.\n\n4.\tThis question is correlated with the Question 1 and 3. Basically, each time when you use the Young’s inequality, you will use the relation, E||x^{r} – x{r−1}||^2 <= γ^{2}E(ξ_{r-1} + E||∇f(x^{r-1})||^{2}) in next step, for example, it has been used to derive the second inequality in Page 22.\nIt is not true to me without any assumptions. Basically, you are saying the averaged gradient can be bounded by the true gradient with some error, this is basically a (new) variant assumption of the assumption you claim you have abandoned (bounded data heterogeneity assumption). I believe you should not abandon the more standard bounded data heterogeneity assumption.\n\n5.\tI checked the mentioned work VRL-SGD that can handle unbounded data heterogeneity. It is not published, and the soundness of the proof is being doubted in the previously peer-reviewing stage. You should be careful to present the conclusions of VRL-SGD as formal results in your work.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The presentation is clear and logically consistent.\nFurthermore, the proposed method, momentum acceleration by transiting the global gradient information to local clients, should be empirically useful and improve practical performance.", "weaknesses": "1.\tThe same algorithm has been proposed by multiple works [1,2]. FedCM in [1] is exactly the same as the proposed method, and [1] also gives theoretical guarantees under general convex or non-convex smooth assumptions, it is not the case as this work claimed: “However, whether momentum can offer theoretical benefits to FL remains underexplored”.\n\n2.\tThere are mistakes with the proof of the main result (Theorem 1) and implicitly using of extra assumptions, so the correctness of the main results is doubtful. Please check the following Questions 2 and 4.\n\n3.\tThe problem complexity is studied over the convergence rate under the same fixed hardware budget, such as communication cost or memory consumption. However, this work forgets to mention the extra requirement over the communication budget or the local storage.\n(a)\tFirstly, the costs of the downlink communication may be two times more expensive than other methods since the proposed method requires the broadcast of the extra averaged gradient information from the center server to each client, together with the new model parameters.\n(b)\tIf the algorithm tries to maintain the same communication cost, then it can only broadcast the averaged gradient information. But it will require the local client to save a copy of the initial parameters of (r-1)-step, i.e., transferring the global updating step to local clients.\n\n4.\tDespite the doubt about proof, the method itself is not novel. Embedding local or global momentum seems straightforward. Meanwhile, considering the broad application scenarios of FL, the experiment is too simple, which is not valid to show the effectiveness of the method. However, if the proof can be validated, those shortages can be largely mitigated.\n\n[1] Xu J, Wang S, Wang L, et al. Fedcm: Federated learning with client-level momentum[J]. arXiv preprint arXiv:2106.10874, 2021.\n[2] Kim, Geeho, Jinkyu Kim, and Bohyung Han. \"Communication-efficient federated learning with acceleration of global momentum.\" arXiv preprint arXiv:2201.03172 (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)