Anchor Sampling for Federated Learning with Partial Client Participation
Authors: Feijie Wu
Song Guo
Zhihao Qu
Shiqi He
Ziming Liu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Optimization

Abstract: In federated learning, the support of partial client participation offers a flexible training strategy, but it deteriorates the model training efficiency. In this paper, we propose a framework FedAMD to improve the convergence property and maintain flexibility. The core idea is anchor sampling, which disjoints the partial participants into anchor and miner groups. Each client in the anchor group aims at the local bullseye with the gradient computation using a large batch. Guided by the bullseyes, clients in the miner group steer multiple near-optimal local updates using small batches and update the global model. With the joint efforts from both groups, FedAMD is able to accelerate the training process as well as improve the model performance. Measured by $\epsilon$-approximation and compared to the state-of-the-art first-order methods, FedAMD achieves the convergence by up to $O(1/\epsilon)$ fewer communication rounds under non-convex objectives. In specific, we achieve a linear convergence rate under PL conditions. Empirical studies on real-world datasets validate the effectiveness of FedAMD and demonstrate the superiority of our proposed algorithm: Not only does it considerably save computation and communication costs, but also the test accuracy significantly improves. 

Under review as a conference paper at ICLR 2023
ANCHOR SAMPLING FOR FEDERATED LEARNING WITH PARTIAL CLIENT PARTICIPATION
Anonymous authors Paper under double-blind review
ABSTRACT
In federated learning, the support of partial client participation offers flexible training strategy, but it deteriorates the model training efficiency. In this paper, we propose framework FedAMD to improve the convergence property and maintain flexibility. The core idea is anchor sampling, which disjoints the partial participants into anchor and miner groups. Each client in the anchor group aims the local bullseye with the gradient computation using a large batch. Guided by the bullseyes, clients in the miner group steer multiple near-optimal local updates using small batches and update the global model. With the joint efforts from both groups, FedAMD able to accelerate the training process as well as improve the model performance. Measured by e-approximation and compared to the state-of-the-art first-order methods, FedAMD achieves the convergence by up to O(1 fewer communication rounds under non-convex objectives. In specific, lincar convergence rate under PL conditions. Empirical studies on real-world datasets validate the effectiveness of FedAMD and demonstrate the superiority of our proposed algorithm: Not only does it considerably save computation and communication costs, but also the test accuracy significantly improves.
achieve a
INTRODUCTION
Federated learning (FL) (Konečný et al., 2015; 2016; McMahan et al., 2017) has attained an increasing interest over the past few years. As distributed training paradigm, enables a group of clients to collaboratively train global model from decentralized data under the orchestration of a central server. By this means, sensitive privacy is basically protected because the raw data are not shared across the clients. Due to the unreliable network connection and the rapid proliferation of FI. clients, is infeasible to require recent works (Li et al., 2019b: Philippenko & Dieuleveut, 2020; Gorbunov et al., 2021a; Karimireddy et al., 2020b; Yang et al., 2020; Li et al., 2020; Eichner et al., 2019; Yan et al., 2020; Ruan et al., 2021; Gu et al., 2021; Lai et al., 2021) introduce practical setting where merely portion of clients participates in the training. The partial-clien scenario effectively avoids the network congestion at the FL server and significantly shortens the idle time as compared to traditional large-scale machine learning (Zinkevich et al., 2010; Bottou, 2010; Dean et al., 201 2; Bottou et al., 2018).
clients to be simultaneously involved in the training. To address the issue,
However, a model trained with partial client participation is much worse than the one trained with full client participation (Yang et al., 2020). This phenomenon is account for two reasons, namely, data heterogeneity ka. non-i.i.d. data) and the lack of inactive clients' updates. With data heterogeneity, the optimal model is subject to the local data distribution, and therefore, the local updates on the clients' models greatly deviate from the update towards optimal global parameters (Karimireddy et al., 2020b; Malinovskiy et al., 2020; Pathak & Wainwright, 2020; Wang et al., 2020; 2021; Mitra al., 2021: Rothchild et al., 2020; Zhao et al., 2018; Wu et al., 2021). FedAvg (McMahan et al., 2017; Li et al., 2019b; Yu et al., 2019a;b; Stich, 2018), for example, is less likely to follow a correct update towards the global minimizer because the model aggregation on the active clients critically deviates from the aggregation on the full clients, an expected direction towards global minimizer (Yang et al., 2020).
As family of practical solutions to data heterogeneity, variance reduced techniques (Karimireddy et al., 2020b; Gorbunov et al., 202 la; Wu et al., 2021; Gorbunov et al., 2021b; Liang et al., 2019; Shamir et al., 2014; Li et al., 2019a; 2021b; b;; Karimireddy et al., 2020a; Murata & Suzuki, 2021) achieve an improved convergence rate when compared to FedAvg. With multiple local updates, each client corrects the SGD steps with reference an estimated global target, which is synchronized at

---

Under review as a conference paper at ICLR 2023
Partial Clients
Convexity
Method
Communication Rounds
Minibutch SGD (Wang Srebro, 2019)
X
MRke
FedAvg (Yang et al., 2020)
SCAFFOLD (Karimireddy et al., 2020b)
/
(M)
2/3
Non-convex
BVR-L-SGD (Murata & Suzuki, 2021)
X
MR
VR-MARINA(Gorbunov al., 2021a)
X
Meki
FedAMD (Sequential) (Corollary 1)
FedAMD (Constant) (Corollary 2)
M
A
Minibatch SGD* (Woodworth et al., 2020b)
X
pMKe
log
FedAvg (Karimireddy al., 2020a)
14 v /4 +1 log
puke
PL condition (or "strongly- convex)
SCAFFOLD* (Kurimireddy et al., 2020b)
mAKe
+
1 log
VR-MARINA (Gorbunov al., 2021a)
X
+
par M log
p.M.
FedAMD (Constant) (Corollary 3)
M
log
Table 1: Number of communication rounds that achieve E V (Roo:) S for non-convex objectives (or (. F. S e for PL. condition strongly-convex with the parameter of μ)). We optimize an online scenario and set the small batch size to 1. The symbol / or for "Partial Clients" is determined by the following footnote 1.
the beginning of every round. Although, in each transmission round, variance-reduced algorithms require the communication overhead twice as more as FedAvg, their improved performances are likely to eliminate the cost increments. Recent studies (Gorbunov et al., 2021a; Murata & Suzuki, 2021; Tyurin & Richtárik, 2022; Zhao et al., 2021) have demonstrated great potential using large batches under full client participation! Measured by e-approximation, MARINA (Gorbunov et al., 2021a), for instance, realizes O(L/Me 2/2) faster while using large batches, where M indicates the number of clients.
However, none of the prior studies address the drawbacks of using large batches. Typically, large batch update involves several gradient computations compared to a small batch update. This increases the burden of FL clients, especially on IoT devices like smartphones, because their hardware hardly accommodates all samples in a large batch simultaneously. Instead, they must partition the large batch into several small batches obtain the final gradient. Furthermore, regarding the critical convergent differences between various participation modes, the effect of using large batches under partial client participation cannot be affirmative. BVR-L-SGD (Murata & Suzuki, 2021) and FedPAGE (Zhao et al., 2021) claim that they can work under partial client participation, but they require all clients' participation when the algorithms come the synchronization using large batch.
Motivated by the observation above, we propose framework named FedAMD under federated learning with anchor sampling that disjoints the partial participants into two groups, i.e., anchor and miner group. In the anchor group, clients (a.k.a. anchors) compute the gradient using large batch cached in the server to estimate the global orientation. In the miner group, clients (a.k.a. miners) perform multiple updates corrected according to the previous and the current local parameters and the last local update volume. The objective for the latter group is twofold. First, multiple local updates without serious deviation can effectively accelerate the training process. Second, we update the global model using the local models from the latter group only. Since anchor sampling disjoints the clients with time-varying probability, we separately consider constant and sequential probability settings.
Contributions. We summarize our contributions as follows:
Algorithmically, we propose a unified federated learning framework FedAMD that identifies a participant an anchor or miner. Clients in the anchor group aim to obtain the bullseyes of their local data with a large batch, while the miners target to accelerate the training with multiple local updates using small batches.
Theoretically, we establish the convergence rate for FedAMD under non-convex objectives under both constant and sequential probability settings. To the best of our knowledge, this is the first work to analyze the effectiveness of large batches under partial client participation. Our theoretical
In this paper, partial client participation refers to the case where only portion of clients take part every round during the entire training.
2

---

Under review as a conference paper at ICLR 2023
results indicate that, with the proper setting for the probability, FedAMD achieve a convergence (MM rate of O( AT under non-convex objective, and linear convergence under condition (Polyak, 1963; Lojasiewicz, 1963). Comprchensive comparisons with previous works are presented in Table 1.
(PL)
Empirically, conduct extensive experiments to compare FedAMD with the most representative approaches. The numerical results provide evidence of the superiority of our proposed algorithm. Achieving the same test accuracy, FedAMD utilizes less computational power metered by the cumulative gradient complexity.
RELATED WORK
In this section, we discuss the state-of-the-an works that are strongly relevant to our research. A more comprehensive review is provided in Appendix A.
Mini-batch SGD vs. Local SGD. Distributed optimization is required to train large-scale deep learning systems. Local SGD (also known as FedAvg) (Stich, 2018; Dieuleveut Patel, 2019; Haddadpour et al., 2019; Haddadpour & Mahdavi, 2019) performs multiple (i.e., K 2 1) local updates with K small batches, while mini-batch SGD computes the gradients averaged by K small batches (Woodworth et al., 2020b;a) (or a large batches (Shallue et al., 2019; You et al., 2018; Goyal et al., 2017)) on given model. There has been a long discussion on which one is better (Lin et al., 2019; Woodworth et al., 2020a;b; Yun et al., 2021), but no existing work considers how to disjoint the nodes such that both can be trained at the same time.
Variance Reduction in FL. The variance-reduced techniques have critically driven the advent of FL algorithms (Karimireddy et al., 2020b; Wu et al., 2021; Liang et al., 2019; Karimireddy et al., 2020a; Murata & Suzuki, 2021; Mitra al., 2021) by correcting each local computed gradient with respect to the estimated global orientation. However, concern is addressed on how to attain an accurate global orientation to mitigate the update drift from the global model. Roughly, the estimation lies in two types, namely, precalculated and cached. The former methods (Murata & Suzuki, 2021; Mitra et al., 2021) required precalculation typically require full worker participation, which is infeasible for federated learning settings. As for the global orientation estimated by cached information, existing approaches (Karimireddy et al., 2020b; Wu et al., 2021; Liang et al., 2019; Karimireddy et al., 2020a) utilize small batches, which derives biased estimation and misleads the training. This work explores the effectiveness of large-batch estimation for the global orientation under partial client participation.
FEDAMD
In this section, we comprehensively describe the technical details of FedAMD, federated learning framework with anchor sampling. In specific. it disjoints the active participants into the anchor group and the miner group with time-varying probabilities. The pseudo-code is illustrated in Algorithm
Problem Formulation. In an FL system with total of M clients, the objective function is formalized as
min F(x) XERU
Σ Fm(() mE[M]
(1)
M
where we define [M] for a of M clients. (-)(-) indicates the local expected loss function for client m. which is unbiased estimated by empirical loss f.)(.) using a random realization B,, from the local training data D,,, i.e., BB,,,-D.., fm,, B.,) Fmn (x)... We denote n by the size of a client's for all m E [M]. and can be infinite large in the streaming/online
local dataset, i.e., [Dml cases. F. represents the minimum loss for Equation (1).
Algorithm Description. In FedAMD, a global model is initialized with arbitrary parameters Tp E Rd. By distributing the model to all clients (Line 1), clients m E [M] are required to generate a
b-sample batch Bm,o and compute the gradient vo c(m)) (Line 3). Then, clients send vi to the server
(()
(Line 4), and server caches these gradients and span them matrix vo { (()m))
(m)
(Line 6).
mE[M]
After the initialization steps above, the algorithm comes to the model training (Line 7-27). At the beginning of each round the server randomly picks A-client subset A from M clients (Line 8). Since each client is independently selected without replacement, under the setting of Equation (1), clients have equal chance be selected with the probability of n Subsequently, the server
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1 FedAMD
Input: local learning rate Mes global learning rate 7,,, minibatch size b, V/ < b, local updates K probability {pe E [0, 1|]r2o. initial model øo.
1: Communicate the initial model Po with all clients [M]
2: for m E [M] in parallel do
3: U0
(m)
vn (æo, Bm,o) using Bm.o Din with the size of b
4: Communicate (mm) with the server
5: end for
Initialize caching gradient Uo = {160 (m))
6:
mE(M]
7: for = 0, 0, 2.... do
8: Sample clients A S [M]
9: Communicate the model ã₁ and the caching gradient 9: avg(t:) with clients i E A Initialize subsequent caching gradient U/+11 2/2
11:
for i E A in parallel do
if Bernoulli(p)) = then
13:
141 Vi (æ,, Bi,,) using B Dj with the size of b
14:
Communicate Vi+1 with the server and indicate the update of caching gradient
else
16:
Initialize zt = 200 tt, 92.0 9.
for k = ...... K do
Generate random realization B D, with the size of b
19:
(8) 9r,k41
91,k Vff ( B + V.s (i B
(6)
20:
a k+1
(i)
Tit
(5)
III gi.k+1
end for
22:
Ax -; Li,K
(5)
23:
end Communicate Ax(") with the server and indicate the update of the model
(i)
24:
25:
end for
26: Ø1+1 -; - 115 (Ax.) where Ax, aggregates Axt where client i updates model
27: end for
distributes the global model 2; to the clients in the set A, accompanying the global bullseye (i.c., the averaged caching gradient) J. ग Eme(m) (m) (Line 9). With the probability of pt. client E A classified for the anchor group (Line 13-14) the miner group (Line 16-23), and different groups have different objectives and focus on different tasks.
Anchor group (Line 13-14). Clients in this group target to discover the bullseyes based on their local data distribution. According Line 12, client AA has the probability of pt become a member of this group. Then, the client utilizes large batch Bi, with b samples to obtain the gradient (i)
Wi+1 (Line 13). Therefore, following the gradient v241 can find an optimal or near-optimal solution for client i. Next, the client pushes the gradient to the server and updates the caching gradient (Line 14). In view that some clients do not participate in the anchor group for obtaining the bullseyes at round 6, the server spontaneously inherits their previous calculation from et (Line 10), As a result, Tr in Line 9 indicates an approximate orientation towards global optimal parameters, which directs the local update in the miner group and affects the final global update. Besides, v(() influences the training from round & + up to the next time when client is a member of anchor group.
Miner group (Line 16-23). Guided by the global bullseye, clients in the miner group perform multiple local updates and finally drive the update of the global model. First, client initializes the model with Z, and the target direction with IJ (Line 16). Ideally, in the subsequent K updates (Line
17). client update the model with the gradient (= for l [O..... ......K 1}. This impractical because clients cannot access all others' training sets to compute the noise-free gradients. Instead, the client ke-th iteration generates b' -aamle realization B., (Line 18) and caleulates the update
P6.41 via a variance-reduced technique, i.e., p6. -r,k V.f (.) (, B'.e)) + V. (1i B(.))
(
4

---

Under review as a conference paper at ICLR 2023
(0) for two reasons: (i) the first term is used (Line 19). The update I is approximate to V
(0)
to estimate the global update because Ii.0 stores the global bullseye; and (ii) the rest terms remove the perturbation of data heterogeneity and reflect the true update at 2 Therefore, the local model (6) update follows Fi,k+1 Ft,6 q 9i,++1 (Line 20). After K local updates, the model changes
(4)
on client Aa, = 3; - Ki,K. Then, the client transmits Art") (1) to the server for the purpose of global model update.
The proposed approach possesses threefold advantages when compared to SCAFFOLD (Karimireddy al., 2020b) and FedLin (Mitra et al., 2021) using a consistent correction term, i.c., 9: - e Firstly, it is a memory-efficien approach that is unnecessary to maintain the obsolete gradient. Secondly, it dynamically calibrates the local updates subject to the local model. Although BVR-L-SGD (Murata & Suzuki, 2021) 1) also achieves such functionality, it requires all clients to jointly obtain the global direction at the beginning of each round, leading to considerable training time. As for FedAMD, here comes the third advantage that avoids the precalculation on a global bullseye under partial-client scenarios. To the best of our knowledge, this is the first work to achieve dynamic calibration under partial-client scenarios.
Server (Line 14 and Line 26). Therefore, after the separate local training on the participants,
the server merges the model changes from the miner group into Ax, (Line 26) and updates the caching gradients from the anchor group (Line 14). It is noted that the size of Ax, (a.k.a. |Ax,)) can within the range between and A. When the size is 0, Te+1 = 3t, or otherwise, Pt++1 = T 18-7, 17, E / (Line 26). The reason why we solely use the changes from the miner group is that clients perform multiple local updates regulated by the global target such that the model changes walk towards the global optimal solution. While directly incorporating the new gradients from the anchor group, the global model has a degraded performance because they perform single update that aims to find out the local bullseye deviated from the global target. Implicitly, clients in the miner group take in the update of caching gradients at iteration k = 0 to update the local model, which will affect the next global parameters.
Previous Algorithms as Special Cases. The probabilities can vary among the rounds that disjoint the participants into the anchor group and the miner group. By setting A = M, and the probability {p.} following the sequence of (1, 0, 1,0,... ........ ). FedAMD reduces distributed minibatch SGD (K = 1) or BVR-L-SGD (K > 1). Therefore, FedAMD subsumes the existing algorithms and takes partial client participation into consideration. To obtain the best performance, we should tune the settings of } and K. However, accounting for the generality of FedAMD, it faces substantial additional hurdles its convergence analysis, which is one of our main contributions, as detailed in the following section.
Discussion on Communication Overhead. As the anchors are not necessary to obtain the averaged caching gradient (i.e., gr) 1-th round, the centralized server solely distributes Z. to the miners. Compared to FedAvg, the proposed algorithm requires (1 - pt)/2 more communication costs, but it achieves convergence with at least O less communication rounds (see Table 1). Therefore, from the perspective of model training progress, FedAMD is more communication efficient than FedAvg.
Discussion on Massive- Client Settings. A typical example of this scenario is cross-device FL (Kairouz et al., 2019). In this setting, is a wise option for the server to preserve all the caching gradients for clients. Therefore, the clients retain their caching gradients while the server keeps their average. Firstly, 1-th round, client [M] copies their caching gradient to
1)-th round, i.e.,
(i) For the client i in the anchor group, they will follow Line 13 in Algorithm I to update 2i 0i
2 and push A = u ot to the server. After the server receives the updates of all local
caching gradients, it performs 0441 = U4 + MM Σ Ac, where A aggregates Ag where client is in anchor group
THEORETICAL ANALYSIS
In this section, we analyze the convergence rate of FedAMD under non-convex objectives with respect to e-approximation, i.e., min F (i)) < e. Specifically, when it comes PL condition, e-approximation refers to F(ør)- F(x.) In the following discussion, we particularly highlight
5

---

Under review as a conference paper at ICLR 2023
the setting of {pe} to obtain the best performance. Before showing the convergence result, make the following assumptions, where the first two assumptions have been widely used machine learning studies (Karimireddy al., 2020b; Li et al., 2020), while the last has been adopted in some recent works (Gorbunov et al., 2021a; a; Tyurin & Richtárik, 2022; Murata & Suzuki, 2021).
Assumption (L-smooth). The local objective functions are Lipschitz. smooth: For all B E Rd.
VE(()))V S Lllu - -112, Vi [M].
Assumption (Bounded Noise). For all Rd, there exists a scalar such that
o²
Eg_D, [V VVF(
B Vi [M].
Assumption (Average L-smooth). For all u, 6 E Rd, there exists a scalar Lg such that
L
EB-D.
- - VF(D))I -
v 8 a
E [M].
B
Remark. Assumption 3 definitely provides a tighter bound for the patterns of variance reduction. In fact, solely with Assumption 2, the term EB-D, I| [[(,, ( BB (f, - (VF((v) - (F) can be bounded by constant. Therefore, we can easily obtain the coefficient for ||e U|6 which could be with the same structure as the constant in RHS Assumption Furthermore, if the loss function is Lipschitz smooth, e.g., cross-entropy loss (Tewari & Chaudhuri. 2015), we derive similar structure as presented in Assumption 3.
4.1 SEQUENTIAL PROBABILITY SETTINGS
As mentioned in Section 3, a recursive pattern appeared the probability sequence {pr E {0, 122 can reduce FedAMD to the existing works. We assume that the caching gradient updates every r(2 2) rounds, such that
{1, t mod T == ==
== {00 Otherwise
We derive the following results under sequential probability settings. The corresponding proof is provided in Appendix D.
Theorem 1. Suppose that Assumption 1, 2 and hold. Let the local updates K 2 the minibatch size b min Me n and b' < b. Additionally, the settings for the local learning rate th and the
global learning rate T]s satisfy the following two constraints: (1) Mem KE (1+ -1 and
VV Then, to find an e-approximation of non-convex objectives, i.e.
(2) mp S min
2V6KL 4/3L,
min
[VF (1:)11 < c, the number of communication rounds T performed by FedAMD is
==o =0((11+ 2MM
T 7-1 -.
where we treat VF (#o) F, and L as constants.
Discussion the selection of According Theorem notice that 2 achieves min V (a:) < with the fewest communication rounds. The following corollary discloses the relation between computation overhead and the value of т.
Corollary 1. Under the setting of Theorem 1, FedAMD computes (ML TMKE gradients and
consumes communication overhead of O
Mr Ac
during the model training.
Remark. FedAMD requires an increasing computation and communication cost as T gets larger. Therefore, = 2 possesses the most outstanding performance in the sequential probability settings. In this case, FedAMD requires the communication rounds of O Ae the communication overhead
of Ar , and the computation cost of O the size of local dataset is infinity large.
MK while optimizing an online scenario where

---

Under review as a conference paper at ICLR 2023
Comparison with BVR-L-SGD. As discussed in Section 3. FedAMD reduces to BVR-L-SGD (Murata Suzuki, 2021) when T = and all clients participate in the training. this case, Theorem 1 shows total of T O(1/e) communication rounds is needed. This result coincides with the complexity of BVR-L-SGD in Table by the setting that (1) nM S f. and (2) K Z Vn/M. In other words, we theoretically prove that BVR-L-SGD still achieves minke(T] VF (#t)l S with (1/cc) in a looser constraint. As for computation overhead, our proposed method requires MK
which is less than BVR-L-SGD (i.e., O ( + MM+MK + MK)).
4.2 CONSTANT PROBABILITY SETTINGS
Apparently, when we set the constant probability as all participants are in the anchor group such that the model cannot be updated. Likewise, when the constant probability is O, all participants are in the miner group such that the global target cannot be updated, leading to degraded performance. Therefore, we manually define a constant E (0. 1) such that {pr = p1220- In this section, we derive the following results with partial client participation. Detailed proof provided in Appendix E. Specifically, Appendix E.2 and Appendix E.3 proves the convergence rate for Theorem 2 and Theorem 3, respectively.
Theorem 2. Suppose that Assumption 1, and 3 hold. Let the local updates K 2 max (1,
222 (
the minibatch size b min
o² Mc. n) and V/ < b, the local learning rale тii 2/6KL' and the global
learning rate T7s- 1+ 2M V VI-pA" Then, to find an e-approximation of non-convex objectives, i.e.
2/6
minger |VF (2:))12 S e, the number of communication rounds T performed by FedAMD
T= ( I- (-
M
ApVI - D
where we treat V (ão) - F,, and L as constants.
With the constant probability p approaching 0 or 1, Theorem 2 shows that FedAMD requires significant number of communication rounds. Hence, there an optimal p such that FedAMD achieves convergence with the fewest communication rounds. In view that M 2 A, the number of
communication rounds is dominated by O
1 Based on this observation, the following
M
ApVi-pa
corollary provides the settings for the constant probability p that leads to the optimal convergence result. Based on the value of p. we further refine the settings for other parameters. The following corollary takes D' into consideration, i.e., the small batch size is 1.
2 1/A
Corollary 2. Suppose that Assumption 1, and hold. Let the constant probability p =
A+2
where e is constant greater than or equal to 1, the local updates K 2 max (1,
21.2 1,2 the mini-
batch size b min n) and b' 1, the local learning rate Ti: 2/6KI. and the global learning rate Ys = 2/66 A+3Me Then, after the communication rounds of T O (M) we have mintery ||V (2:))l2 < Therefore, the number of total samples called by all clients (i.e., cumula- live gradient complexity) is O ( MK) ) when it optimizes an online scenario.
Discussion on the effectiveness of c. When c= 1, we can obtain the minimum value for the term (MV1-1 p44 with the constant devised in Corollary 2. As the number of participants (i.e., A) gets larger, the optimal p increases as well and tends to be 1, indicating that most participants are in the anchor group. When we optimize an online scenario, the anchors compute gradient with massive samples. As result, the computation overhead of a single round is not acceptable. By deducting the anchor sampling probability to its 1/c, FedAMD consumes up to (c 1)/c less computation overhead, while its convergence performance remains.
Comparison with FedAvg. As classical algorithm, FedAvg (Yang al., 2020) requires O + !) communication rounds to achieve minge(T) V (6)) with the total computation
7

---

Under review as a conference paper at ICLR 2023
consumption of 0 ( + 1k)
Apparently, FedAMD needs O fewer communication rounds.
As mentioned in Section 3, FedAMD consumes p)/2 more communication overhead than FedAvg. As is close to 0, the total communication overhead for FedAMD is far less than the cost of FedAvg. As for computation overhead, (Yang et al., 2020) implicitly assumes that 2 o² FedAMD) more communication friendly than FedAvg.
In addition to the generalized non-convex objectives, we investigate the convergence rate of the PL condition, a special case under non-convex objectives. The following assumption describes this case:
Assumption 4 (PL Condition (Karimi et al., 2016)). The objective function F' satisfies the PL condition when there exists a scalar >> such that
VFFu) 2p (F(o)- F.), Vu E
Under PL condition, the rest of the section draws the convergence performance of FedAMD with partial client participation.
Theorem Suppose that Assumption 1, 2, 3 and hold. Let the local updates K 2 max (1, V
21,2
the minibatch size b min
and b' < b, the local learning rate 2/6KL' and the Mpee
Then, to find an e-approximation of PL condition, Le., F( Fxx.)= S c, the number of communication rounds T performed by FedAMD is
global learning rate = min
2v6LAp Mu(1-p"T}> 1+ 1937
2/6
pap
T T= 0 111 (A) (1+
M
Mp(1 Mp(11p"))
log 1
+
μAp
Ap
where we treat F (āo) - F. and L as constants.
Similar to Theorem 2, the number of communication rounds of FedAMD is mainly occupied by M According to such an approximation, we provide mathematical expression
M O pp Ap
for the setting of in Corollary 3. Subsequently, we adjust the value of the hyper-panne parameters such that we can obtain the best result for Theorem
Corollary Suppose that Assumption 1, 2, and hold. Let the constant probability p 1/A
((
A+1 2q
A+1 2
+
where e is a constant greater than or equal to 1, the local
updates K 2 max (1,
212 1.2
the minibatch size = min
( o² ( and b' = 1, the local learning
JeAL 2v6 (1+ 32MC ) Then,
rate in 2V6KL' and the global learning rute 1)s = min Myc
log )) we have F(wr) F(xx) S Therefore, the number of total samples called by all clients (i.e., cumulative gradient complexity) is log !) when it optimizes an online scenario.
after the communication rounds of Tf (( M + 1 AA
O (
Mar + Kogg
Remark. When c = 1, the probability p for anchor sampling approaches 100% as the number of participants is increasing. Likewise, it is necessary to consumption each round. Besides, FedAMD achieves a linear convergence under PL. conditions. In view that strongly-convex objectives possess looser setting than PL. conditions, FedAMD can also achieve linear convergence under strongly-convex objectives.
1 reduce the computation
EXPERIMENTS
This section presents the experiments our proposed approach and other existing baselines that are most relative to this work. We also investigate the effectiveness of probability {pe (pe) Account for the limited space, numerical analysis on other factors like the number of local updates are presented in the supplementary materials.
8

---

Under review as a conference paper at ICLR 2023
A5t-Ararrcyy/ (18)
70
800
18
coneait 0-33
censint, pm
coneart p-33
Communication Roundist
Communicatton Poundss)
Communccaoon Roundial
(a) 20 clients
(b) 40 clients
(c) 100 clients
Figure 1: Comparison of different probability settings using test accuracy against the communication rounds for FedAMD.
20 clients
40 clients
100 clients
Method
Grad.
Comm.
Round
Acc.
Grad.
Comm.
Round
Acc.
Grad.
Coru.
Round
Acc.
BVR-L-SGD
101.9
853.9
310
77.0
177.4
1492.3
275
78.6
463.8
3908.7
291
78.0
FedAvg
40.8
366.9
318
76.4
78.3
1087.5
305
76.7
186.9
2594.5
291
77.0
FedPAGE
148.6
1670.4
271
79.2
164.3
1622.4
203
80.6
525.5
4540.3
339
77.1
SCAFFOLD
47.5
1318.6
370
75.9
91.4
2537.8
356
76.0
250.9
6966.0
391
75.1
TedAMD (constant)
35.5
489.8
2.59
80.6
55.0
776.3
209
82.7
153.9
2147.8
229
83.4
RedAMD (sequential)
40.2
475.3
213
79.5
80.4
904.5
190
80.8
253.8
2998.8
269
78.7
Table 2: Comparison among baselines in terms of cumulative gradient complexity (x
(x100 10a samples), communication costs (x32 Mbits), and rounds reaching the accuracy of 75%. and the final accuracy (%) after 400 rounds. Bold: The best result each column; underline: The best result of the baselines in each column; Italy: The results that FedAMD outperforms all baselines in each column.
Experimental setup. We train convolutional neural network LeNet-5 (LeCun al., 2015; 1989) (non-convex) using Fashion MNIST (Xiao et al., 2017) which consists of 10 classes that equally disjoint the training set of 60K samples and the test set of 10K samples. We conduct the experiments with a total of 100 clients. To simulate the non-i..d. features, each client holds the data from 2 classes with a total of 600 samples, and each label is held by 20 clients. Let the number of local updates K be 10, the mini- size D' be 64 and b be 600. For different experiments, unless some ryper-parameters have been defined, we leverage the best setting (e.g.. learning rate) to obtain the best results. All the numerical results in this section represent the average performance of three experiments using different random seeds. More empirical results are put in Appendix F. Effectiveness of probahility {pe (2e0 Figure demonstrates the performance of various probability settings under the scenarios of different participants. In Figure la with 20 clients, both sequential probability setting and constant probability setting achieve the best performance. In Figure 1b and ic, where 40 and 100 clients are selected in each round, constant probability setting outperforms sequential probability setting. In all three scenarios, with sequential probability settings, the pattern of (,,0, 0, 1) has a much worse performance than the pattern of 10. This empirically validates Theorem for the best setting r = 2 in terms of communication complexity. Similarly, with constant probability settings, the best performance is achieved when p approximates or equals optimal, which validates the statement in Corollary 2.
Comparison with the sate-off-thearre works. Table compares FedAMD with the existing works under partial/full client participation. At first glance, FedAMD outperforms other basclines because the texts in bold are all appeared in FedAMD. With 20-client participation, our proposed method surpasses four baselines all aroundness. As for 40-client participation, FedAMD with constant probability saves at least 30% computation and communication cost, and the final accuracy realizes up to 6% improvement. In terms of the training with full client participation, FedAMD requires 10%-20% fewer communication rounds, and its final accuracy has significant improvement, i.e., within the range of 0.7%-8.3 8.3%. Also, it is well noted that B BVR-L-SGD has similar performance as FedAMD using sequential probability in terms of communication rounds and test accuracy, but the former needs more computation and communication overhead. This is because BVR-L-SGDD computes the bullseye using multiple D' size batches rather than a large batch.
6 CONCLUSION
In this work, we investigate a federated learning framework FedAMD that disjoints the partial participants into anchor and miner groups. We provide the convergence analysis of our proposed algorithm for constant and sequential probability settings. Under the partial-client scenario, FedAMD achieves sublinear speedup under non-convex objectives and linear speedup under the PL condition. To the best of our knowledge, this is the first work to analyze the effectiveness of large batches under partial client participation. Experimental results demonstrate that FedAMD is superior to sfate-of-the works. It is interesting to explore anchor sampling in the other scenarios of FL, e.g., arbitrary device unavailability.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference machine learning, pp. 699-707. PMLR, 2016.
Dmitrii Avdiukhin and Shiva Kasiviswanathan. Federated learning under arbitrary communication patterns. In Proceedings of the 38th International Conference on Machine Learning, pp. 435.
PMLR. 2021.
Alberto Bietti and Julien Mairal. Stochastic optimization with variance reduction for infinite datasets with finite sum structure. Advances in Neural Information Processing Systems, 30, 2017.
Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. arXiv preprint arXiv:1103.03228, 2021.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of C0MPSTAT"2010, pp. 177-186. Springer, 2010.
Léon Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pp. 421 421-436. Springer, 2012.
Léon Bottou and Yann Cun. Large scale online learning. Advances in neural information processing systems, 16, 2003.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311 2018.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 international joinl conference on neural networks (IJCNN), pp.
2921-2926. IEEE, 2017.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, al. Large scale distributed deep networks. Advances in neural information processing systems, 25, 2012.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient federated learning for heterogeneous clients. arXiv preprint arXiv:2010.01264, 2020.
Aymeric Dieuleveut and Kumar Kshitij Patel. Communication trade-offs for local-sgd with large step size. Advances in Neural Information Processing Systems, 32, 2019.
Hubert Eichner, Tomer Koren, Brendan McMahan, Nathan Srebro, and Kunal Talwar. Semi-cyclic stochastic gradient descent. In International Conference on Machine Leurning, pp. 1764-1773. PMLR, 2019.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path- intt-inteerated differential estimator. Advances Neural Information Processing Systems, 31, 2018
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini- stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, (55 155(1):2673305, 2016.
Eduard Gorbunov, Konstantin P Burlachenko, Zhize Li, and Peter Richtárik. Marina: Faster non- convex distributed learning with compression. In International Conference on Machine Learning, pp. 3788-3799, PMLR, 2021a.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pp. 3556-3564.
PMLR, 2021b.
10

---

Under review as a conference paper at ICLR 2023
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in I hour. arXiv preprint
2017.
Xinran Gu, Kaixuan Huang, Jingzhao Zhang, and Longbo Huang. Fast federated learning in the presence of arbitrary device unavailability, Advances in Neural Information Processing Systems, 34, 2021.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint arXiv: 1910,44,,, 2019.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. Advances in Neural Information Processing Systems, 32, 2019.
Samuel Horváth and Peter Richtárik. Nonconvex variance reduced optimization with arbitrary sampling. In International Conference on Machine Learning, pp. 2781 2789.. PMLR, 2019.
Samuel Horváth, Lihua Lei, Peter Richtárik, and Michael I Jordan. Adaptivity of stochastic gradient methods for nonconvex optimization. arXiv preprint arXiv:2002.05359, 2020.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, and et al. Advances and open problems federated learning. arXiv preprint 11X14979/..04977, 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewin condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-811. Springer, 2016.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mchryar Mohri. Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008. 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.
Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint arXiv:2002.03329 2020.
Jakub Konečný, Brendan McMahan, and Daniel Ramage. Federated optimization: Distributed optimization beyond the datacenter. arXiv preprint 1..05555 2015.
Jakub Konečný, Brendan McMahan, Felix X Yu, Peter Richtárík, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492. 2016.
Fan Lai, Xiangfeng Zhu, Harsha V Madhyastha, and Mosharaf Chowdhury. Oort:
Efficient federated learning via guided participant selection. In 15th {USENIX) Symposium on Operating Systems Design and Implementation ((OSDI) 2/), pp. 19-35, 2021.
Guanghui Lan and Yi Zhou. optimal randomized incremental gradient method. Mathematical programming, 171 171(1):177-215, 2018a.
Guanghui Lan and Yi Zhou. Random gradient extrapolation for distributed and stochastic optimization. SIAM Journal on Optimization, 28(4):2753-2785 2018b.
Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel. Backpropagation applied to handwritten zip code recognition. Neural computation, 1(4):541-551) 1989.
11

---

Under review as a conference paper at ICLR 2023
Yann LeCun al. Lenet-5, convolutional neural networks. URL: http://yann. lecun. com/exdb/lenet, 20(5):14, 2015.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via sesg methods. Advances in Neural Information Prucessing Systems, 30, 2017.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy, Feddane: A federated newton-type -tppe method. 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pp. 1237-1231. IEEE, 2019a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450. 2020.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2019b.
Zhize Li. Ssrgd: Simple stochastic recursive gradient descent for escaping saddle points. Advances in Neural Information Processing Systems, 32, 2019.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pp. 6286-6295, PMLR, 2021a.
Zhize Li, Slavomír Hanzely, and Peter Richtárik. Zerosarah: Efficient nonconvex finite-sum opti- mization with zero full gradient computation. arXiv preprint arXiv:2103.01447, 2021b.
Xiangru Lian, Mengdi Wang, and Liu. Finite-sum composition optimization via variance reduced gradient descent. In Artificial Intelligence and Statistics, pp. 1159-1167. PMLR, 2017.
Xianfeng Liang. Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local sgd with lower communication complexity. arXiv preprint arXiv: 1912. 2019.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. In International Conference Learning Representations, 2019.
Stanislaw Lojasiewiez. topological property of real analytic subsets. Coll. du CNRS, Les équations aux dérivées partielles, 117(87-89):2, 1963.
Grigory Malinovskiy, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik. From local sgd to local fixed-point methods for federated learning. In International Conference on Machine Learning, pp. 6692-6701. PMLR, 2020.
Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting algorithms as gradient descent. Advances in neural information processing systems, 12, 1999.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficinn learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282, PMLR, 2017.
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. arXiv preprint arXiv: 102.03/99 2021.
Yurii Nesterov. Introductory lecfures on conver optimization: A busic course, volume 87. Springer Science & Business Media, 2003.
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.
12

---

Under review as a conference paper at ICLR 2023
Reese Pathak and Martin J Wainwright. Fedsplit: an algorithmic framework for fast federated optimization. Advances in Neural Information Processing Systems, 33:7057-7066, 2020.
Constantin Philippenko and Aymeric Dieuleveut. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint arXiv:2006.144 14591, 2020.
Boris T Polyak. Gradient methods for the minimisation functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):864-875 1963.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference machine learning, pp- 314-323. PMLR, 2016.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. Fetchsgd: Communication-effcienn federated learning with sketching. In International Conference on Machine Learning, pp. 8253-8265. PMLR, 2020.
Nicolas Roux, Mark Schmidt, and Francis Bach. stochastic gradient method with an exponential convergence __tate for finite training sets. Advances neural information processing systems, 25, 2012.
Yichen Ruan, Xiaoxi Zhang, Shu-Che Liang, and Carlee Joe-Wong. Towards flexible device partici- pation in federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 3403-3411. PMLR, 2021.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint arXiv: 1609.660..000 04747, 2016.
Christopher Shallue, Jachoon Lee, Joseph Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George E Dahl. Measuring the effects of data parallelism on neural network training. Journal of Machine Learning Research, 20:1-49: 2019.
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication- distributed optimization using an approximate newton-type method. In International conference on machine learning, pp. 1000-1008, PMLR, 2014.
Aviv Shamsian, Aviv Navon, Ethan Fetaya, and Gal Chechik. Personalized federated learning using hypernetworks. Proceedings of the 38th International Conference on Machine Learning, pp. 9489-9502. PMLR, 2021.
Sebastian Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representationss 2018.
Ambuj Tewari and Sougata Chaudhuri. Generalization error bounds for learning to rank: Does the length of document lists matter? In International Conference Machine Learning, pp. 315-323. PMLR, 2015.
Alexander Tyurin and Peter Richtárik. Dasha: Distributed nonconvex optimization with commu- nication compression, optimal oracle complexity, and no client synchronization. arXiv preprint arXiv:2202.01268. 2022.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in Neural Information Processing Systems, 33, 2020.
Janyy Wang, Qinghua Liu, Hao Liang Gauri Joshi, and H Vincent Poor. A novel framework for the analysis and design of heterogeneous federated learning. IEEE Transactions on Signal Processing. 69:5234-5244 2021.
13

---

Under review as a conference paper at ICLR 2023
Weiran Wang and Nathan Srebro. Stochastic nonconvex optimization with large minibatches. In Algorithmic Learning Theory, pp. 882- PMLR, 2019.
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost: A class of faster variance-reduced algorithms for nonconvex optimization. arXiv, 2018, 2018.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? International Conference Machine Learning, pp. 10334-10343. PMLR, 2020a.
Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch local sgd for heterogencous distributed learning, Advances in Neural Information Processing Systems, 33:6281-622 2020b.
Feijie Wu, Song Guo, Haozhao Wang, Zhihao Qu, Haobo Zhang, Jie Zhang, and Ziming Liu. From deterioration to acceleration: A calibration approach to rehabilitating step asynchronism in federated optimization. arXiv preprint arXiv:21 2021.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint TrXiv:/708.07744 2017.
Yikai Yan, Chaoyue Niu, Yucheng Ding, Zhenzhe Zheng, Fan Wu, Guihai Chen, Shaojie Tang, and Zhihua Wu. Distributed non-convex optimization with sublinear speedup under intermittent client
availability. arXiv preprint wrxi::2002.073999 2020.
Haibo Yang. Minghong Fang. and Jia Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. In International Conference on Learning Representations, 2020.
Yang You, Zhao Zhang, Cho-Jui Hsich, James Demmel, and Kurt Keutzer. Imagenet training in minutes. In Proceedings of the 47th International Conference on Parallel Processing, pp. 1-10, 2018.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis communication efficient momentum sgd for distributed non-convex optimization. In International Conference Machine Learning, pp. 1184-7193.1 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, pp. 5693-5700, 2019b.
Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. arXiv preprint arXiv:2006. 08950. 2020.
Zhuoning Yuan, Zhishuai Guo, Yi Xu, Yiming Ying, and Tianbao Yang. Federated deep auc maximization for hetergeneous data with a constant communication complexity. In Proceedings of the 38th International Conference on Machine Learning, pp. 12219-12229. PMLR, 2021.
Kai Yue, Richeng Jin, Ryan Pilgrim, Chau-Wai Wong, Dror Baron, and Huaiyu Dai. Neural tangent kernel empowered federated learning. In International Conference on Machine Learning, pp. 25783-25803. PMLR, 2022.
Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local sgd with shuffling: Tight convergence bounds and beyond. arXiv preprint arXiv:2 10. 10342, 2021.
Hongyi Zhang, Sashank J Reddi, and Suvrit Sra. Riemannian svrg: Fast stochastic optimization on riemannian manifolds. Advances in Neural Information Processing Systems, 29, 2016.
Jie Zhang, Song Guo, Xiaosong Ma, Haozhao Wang, Wenchao Xu, and Feijie Wu. Parameterized knowledge transfer for personalized federated learning. Advances in Neural Information Processing Systems, 34, 2021.
Haoyu Zhao, Zhize Li, and Peter Richtárik. Fedpage: A fast local stochastic gradient method for communication-efficii federated learning. arXiv preprint 1rXiv:2108.0475: 2021.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint /a00:/000000888 2018.
14

---

Under review as a conference paper at ICLR 2023
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. Advances in neural information processing systems, 23, 2010.
15

---

Under review as a conference paper at ICLR 2023
A RELATED WORK
Mini-batch SGD vs. Local SGD. Distributed optimization is required to train large-scale deep learning systems. Local SGD (also known as FedAvg) (Stich, 2018; Dieuleveut Patel, 2019; Haddadpour et al., 2019; Haddadpour & Mahdavi, 2019) performs multiple (i.e., K 2 1) local updates with K small batches, while mini-batch SGD computes the gradients averaged by K small batches (Woodworth et al., 2020b;a) (or a large batches (Shallue et al., 2019; You et al., 2018; Goyal et al., 2017)) on a given model. There has been a long discussion on which one is better (Lin et al., 2019; Woodworth et al., 2020a;b; Yun et al., 2021), but no existing work considers how to disjoint the nodes such that both can be trained at the same time.
Federated Learning. FL was proposed ensure data privacy and security (Kairouz et al., 2019), and now it has become a hot field in the distributed system (Yuan & Ma, 2020; Shamsian et al., 2021; Zhang et al., 2021; Avdiukhin & Kasiviswanathan, 2021; Yuan et al., 2021; Diao al., 2020; Blum et al., 2021). The FL training methods in the past few years usually require all trainers to participate in each training session (Kairouzee et al., 2019), but this is obviously impractical when facing the increase in FL clients. To enhance the systems" feasibility, this work assumes that a fixed number of clients are sampled at each round, which is widely adopted in (Li et al., 2019b; Philippenko & Dieuleveut, 2020; Gorbunov et al., 202 la; Karimireddy al., 2020b; Yang et al., 2020: Li et al., 2020; Eichner et al., 2019; Ruan et al., 2021). Therefore, the server collects the data from this participation every synchronization to update the model parameters (Li al., 2019b; Philippenko & Dieuleveut, 2020; Gorbunov et al., 2021 a; Karimireddy et al., 2020b; Yang et al., 2020; Li et al., 2020; Eichner et al., 2019; Yan al., 2020; Ruan et al., 2021; Lai al., 2021: Gu et al., 2021).
Variance Reduction in Finite-sum Problems. Variance reduction techniques (Johnson & Zhang, 2013; Defazio et al., 2014; Nguyen et al., 2017: Li et al., 2021a; Lan & Zhou, 201 8a;b; Allen-Zhu & Hazan, 2016; Reddi et al., 2016; Lei et al., 2017: Zhou et al., 2018; Horváth & Richtárik, 2019; Horváth et al., 2020; Fang et al., 2018; Wang et al., 2018; Li, 2019; Roux et al., 2012; Lian et al., 2017; Zhang al., 2016) was once proposed for traditional centralized machine learning to optimize finite-sum problems (Bietti & Mairal, 2017; Bottou & Cun, 2003; Robbins & Monro, 1951) by mitigating the estimation gap between small-batch (Bottou, 2012: Ghadimi et al., 2016; Khaled & Richtárik, 2020) and large-batch (Nesterov, 2003; Ruder, 2016; Mason et al., 1999). SGD randomly samples small-batch and computes the gradient in order to approach the optimal solution. Since the data are generally noisy, an insufficiently large batch results in convergence rate degradation. By utilizing all data in every update, GD can remove the noise affecting the training process. However, is time-consune monscmnnu because the period for single GD step can implement multiple SGD updates. Based on the tfa variance-reduced methods periodically perform GD steps while correcting SGD updates with reference to the most recent GD steps.
Variance Reduction in FI.. The variance-reduced techniques have critically driven the advent of FL algorithms (Karimireddy et al., 2020b; Wu et al., 2021; Liang al., 2019; Karimireddy al., 2020a; Murata & Suzuki, 2021; Mitra et al., 2021) by correcting each local computed gradient with respect to the estimated global orientation. However, concern addressed on how to attain an accurate global orientation to mitigate the update drift from the global model. Roughly, the estimation lies in two types. namely, precalculated and cached. The former methods (Murata & Suzuki, 2021: Mitra et al., 2021) required precalculation typically require full worker participation, which is infeasible for federated learning settings. As for the global orientation estimated by cached information, existing approaches (Karimireddy et al., 2020b; Wu et al., 2021; Liang et al., 2019; Karimireddy et al., 2020a) utilize small batches, which derives a biased estimation and misleads the training. This work explores the effecttivneess of large-batch estimation for the global orientation under partial client participation.
16

---

Under review as a conference paper at ICLR 2023
B USEFUL LEMMAS
Prior to giving detailed proofs of the theorems, we cover some technical lemmas this section, and all of them are valid in general cases.
Lemma 1. Let g {EI...., Ea be the set of random variables in Raxd, Every element in is independent with others. For i {1, ;l,...,,), a). the value for es follows the setting below:
0, (0.
et probability =
E,
otherwise
where is a constant real number between O and 1, i.e., q E [0, 1]. Let I- indicate the length a set, {0) represent set in which element is in but not O. Then, there is probability of q) for le {0} = O, let avg(E) be the averaged result with the exception of zero vectors, i.e.
E Eir
|e {OH # le (0)) =
avg(e)
Then, the the following formulas hold for E (avg(E)) and its second norm E (aag(())
E (avg(e)) (1- 1 (1 4)
c Ellavg(e)11 s (1 -1- --)
Σ
1e:12 (4)
Proof. When 0, the formulas in Equation 4 obviously hold because E (avg(e)) = 0 and E [a)agg()) 12 0. As for q 1, since arg(E) E Ci leverage Cauchy- Schwarrz inequality and get E [Iaug(=)]] = || Σi= c; - E ||e 11 which is consistent with the formulas in Equation 4. addition to the preceding cases, we consider some general cases for the probability within 0 and i.e., q (0, 1).
<
Firstly, we show the proof details for (avg(e)). For in (l,...,a) a). given that e; not a zero vector, the coefficient of is based on the binomial distribution on how many non-zero elements in the set (E1....: 1 (E++1..... Ea). Therefore, with the probability q that E, is equal to e;, the coefficient of in the expected form is
1
(o=') g)-11
a a- 0
+
+
a -
(a- non-zern
non-zero element
Then, the coefficient of Le; can be expressed and simplified for
a 1) a
+ a
(a-1)
(1 -gaa-
(5)
g (1 g)a-1
9"h
(6)
+ (1)
+(1) q(( aa-1
(i)
(1 - 9)a
(8)
where Equation (7) follows
(8)
(a - 1) x ... x (a- 1
aaa- a 1 B 1
Va > 3>0 0
1x... (3- (3-1) 1)
and Equation (8) follows
(1-1)))) (()
(1)
11
(1 a)a
Thus, the equation E (av)(E)) (1 9) ))) -a 6 holds.
17

---

Under review as a conference paper at ICLR 2023
Secondly, we provide the analysis for E [|arg(=)]22 Based the definition for avg(E) in Equation (3), we discuss the case | following inequality:
\ {O}] # 0. By means of Fauchy-Schware inequality, we can obtain the
S
Σ
|e:ll
(9)
[0)
{0)
1 (0)
1=1
Geiz0
1,5,
Therefore,
bo E
|
1 (0) 0
[aug(E)]l
(10)
0,
1s (0)
=0
Apparently, Equation (10) is very similar to Equation (3) terms of the expression. As result, we can adopt the same proof framework in the analysis of E (avg(E)). Then, we can directly draw
conclusion E [egg(s) z (1 (1 q)*) -E=lle) 1e
Lemma 2. Let fEI,... (ei....,Ed =a} be the set of random variables in Rd with the number of These random variables are not necessarily independent. We can suppose that E [E:] = and the variance
is bounded as E [le: elll2] s o². After that we can gel
a
E
Σ
E
+ o
(11)
2
If we make another suppose that the conditional mean of these random variables is E [E. e,, and the variables {e, - -e form martingale difference sequence, and the
bound of the variance is |lec ei < o². So we can make much lighter bound
4
E
2
E
2a0
(12)
2
Proof. For any random variable X, E
X2
= (E
X - E {(]]) + (E (X)) implying
2
2
27
a
a
E
E
e
Σ 2 E
(13)
2
Expanding above expression using relaxed triangle inequality:
Σ 5 e,
< a
[|s ea123 s azo
(14)
For the second statement, depends on inequality
[ [ 1,,
E1). Thus we choose to use relaxed triangle
a
E
E
<
2
e
+ 2E
Σ 5 - E
(15)
then we use a much tighter expansion and we can get:
E
e:
=
>> E
< ao2
(16)
When (e, - ex) form martingale difference sequence, the cross terms will have means.
18

---

Under review as a conference paper at ICLR 2023
Lemma 3. Suppose there is sequence {yr E 122 satisfying recursive function Yt+1
Yt nAy, where rj 0 is constant and Ay: E R2 is vector. Given L-smooth function G, the following inequality holds for any ni and Ay::
mh G(y++1) G(y)) 2
4) IVG())) - 20m7y 2)
|1 -1112
|
2n'
(17)
where o/ > can be any constant.
Proof. Since G' is a L-smooth function, for any 8 E R4, the following inequality holds:
(( ((T)=G(() + ! 8G(c + (()--)) dl
(18)
= G(t) + /
VG(u+ +(B - 0)) (8 v)dt
(19)
= G(()) + +G())+VG()CC - o) + // (VG(v + ((ō - u)) - G(v)) (o - v)
(20)
s 5(()) + VG +)+ + / Ll|t(E e)11211 2112dt
(21)
- + VG v) + v1.2-
(22)
Based on the conclusion on L-smooth drawn from Equation (22), we derive Equation (17) step by step:
L
G (V++1) S G (3)) + (VG (v6) 36+1 - -y:) +
2 11 V/ 1
(23)
I.
(y:) + (v.) -nAy,) + 2/2 11 - 1e112
(24)
2
G (y:)
" ( (w:). Au:) + 11 - yell2
(25)
G (v:)
"
(ff2 VG (we)1 + A 11 1/ (m))i))
L
|1
vel12
2Ty'
2
(26)
GG Gyi)
'/e' 2
VG (v0)22
(21
2mm² - 1 ||uet1 - voll2+ +
" | 1f VG (yc)
2ny
(27)
where Equation (26) is in accordance with (a, = (a² + 332 - (a -a--3)²) and Equation (27)
follows ||A 112 # ll
yoll2-
19

---

Under review as a conference paper at ICLR 2023
C PRELIMINARY FOR FEDAMD
Algorithm I describes FedAMD in details. The objective in this part is to find the recursive function for the sequence of models, i.c., (200 As mentioned in Line 26 in Algorithm I, let Aæ, aggregate Ax,") (+) where client updates model, then the difference between Lt+1 and ã, follows the recursive function written as
1++1 0t aug( Aa:))
(28)
where oug() is same as defined in Lemma As we know, the length of Ar, changes over rounds but does exceed the number of participants, i.e., | I A. Then, suppose that Aw, (m)) ae can be expressed as
is in Aw,
(m)
K
K
Art
(m)
(
FitK (m)
(m) T7.
a
#1,4+1
(m)
Ft,k++1
(m)
Σ
(m) 799.141
(29)
k=
k=0
where the last equal sign is according to Line 20 in Algorithm 1. Next, with the recursive formula in Line 19, we have
(m)
(m)
(m) 21,--11 : + V fm
(m) Fiik BBmn))
9t,k+
9i.k
V fm
(30)
9t
mm
[m) xx B Bmm.)
Jm (m/(m) (m) Bmm))
(31)
Then, Equation (29) can be rewritten as
K-1
K-1
AZ (m)
Kg
M
V fm
(m)
BB,r) + m
Vmn Lix
(m)
(32)
km0
x=0
1==0 k=U
D PROOFS UNDER SEQUENTIAL PROBABILISTIC SETTINGS
D. PRELIMINARY
Lemma Suppose that Assumption 2 and 3 hold. Let the local learning rate satisfy m S min
(m) (m)) | represents the sum of the second norm of every iteration's difference. Therefore, the bound for such a summation in the expected form should be
1 V (K). -Wtt FedAMD, Ek=1 - k
W/KK' 2/313
Σ
(m) Li.k
Ft
(m) r.
1|2
6n, K l19. VF (#e) V (2:)
(33)
Proof. According Equation (31), the update at (I- 1)-th iteration is
)
(m)
-t -7K9t (m)
(m)
-m T1 Ev
(m) vm (x)m))
B m,
Σ v.
(2/mm) B
Fihh
(34)
To find the bound for the expected value of its second norm, the analysis presented as follows:
(m)
(m)
2
E
Pitk-1
2
(355)
ni'
E
51
V fm
1z B m,
(m)
+
V
Vmm
ot,x
(m) B
mz,e)
(36)
k=0
R=0
< 3nf
1
(
+ 3r/
F (2x))12
h-1
1-1
2
+ +37f
Σ
V fm
(m)) By,,)
Σ
V
sm
Fi,m t. m.ns
(m)
(37)
K=0
20

---

Under review as a conference paper at ICLR 2023
=nf 19.
VF (2;))11 + अrे IVF (#:)12 + 3
Σ
V VF (2/m-1) V Fm
Lt,N
(m))
k-1
+ 3nf E
Σ
V mm 1, Bmmx) V.m ( Bmmn) - V F'm (mi + F'm
(11)
(38)
R
(m7) 12
< <nn 19.
VF (2,))12 2 + 3r/ | (#:)l2 + 3n K
E
2t,x
1
==
k-1
2
+ =37F
Σ
v fm (2 : V fm (ii,
(m)
Bmmm)
V F'm (z ) + V Fi
(m))
k=
(39)
33n 19:
V (ā::)12
3nd ( + 3rे KL
Σ
E2
x xixx
(m)
22,x
(m7)
==0
L
3m
E
(m)
(m)
(40)
where Equation (37) is based on Cauchy-Schwand inequality; Equation (38) is based the variance expansion on the third term of Equation (37); Equation (39) is based on Sauchy-Schward inequality and Assumption 1 the third term of Equation (38); Equation (40) is based on Lemma 2 and Assumption on the fourth term of Equation (39).
Therefore, by summing Equation (40) for 1,..., K, we have
x Likk x 2
(m)
(m)
x (m)
2
(m)
(41)
S 3n K 11
VF (#x))l
+ 3n K | (2:) + +3f K KL² +
L3 b'
K
E
x
(m)
x:
t,
(m)
2
(42)
Obviously, according to the setting of the local learning rate the description above, the inequality 3rt K (KL2 + + 1 holds. Therefore, easily obtain the bound for the sum of the second norm of every iteration's 's difference, which is consistent with Equation (33).
D.2 FULL CLIENT PARTICIPATION
Theorem 4. Suppose that Assumption and 3 hold, and all clients participate in the training.
ie., A M. Let the local updates K 2 and the local learning rate y and the global learning
VV Therefore, the convergence rate
rate Ns be nom = KL(1427)' where S min 2/6KL' 4/3L.)
of FedAMD for non-convex objectives should be
1 27
0² [6bnnt Mb
min RE(T]
|| (w.) S
+ +0
(43)
T T-17/7]
where we treat F( F@o)) - F. and L as constants.
Proof. When Pt 1, according to Algorithm 1, there is no model update between two consecutive rounds, i.e., # = á..
Next, we consider the case when = O. Based on Lemma 3, we have
BF -F(()) $ 7 K
L
V ( 1)
E
| - 32
2
2n K
2
21

---

Under review as a conference paper at ICLR 2023
7 E
(ang((ar)) - 1p KVF (2:)112
(44)
2mp K
Knowing that when pt. and all clients involve in the training,
K-1
& Σ M
aug(Ax.)
=
Kg:
Y
Σ
Sm
11 Bmm))
M
[M]MM] k=0 ===
K k
+
Σ
v fm
B Bmm)). (ii
(m))
(45)
M
12
MMIM]
k=0 k=0
we have the bound for IE lavg(( (Am,)
mp KVF (+t)
according to the following derivation:
E avvg (Ax,) KVFFF (ix))1
(46)
K
Vm (m) :l.mBBmm. Bm...) V. (m) B m.k)
K (ūr- - VF (ix)) + M E
M
R=0 xm
12
(47)
$ 2n) K2 119c
VF (1))
K
+ 2E
V fm
(Di Bmxx)
(m)
vm
(m² B
(48)
M
mM(M] k= k=0
2
K
k
= =2 11
VF (x))1
2E
T
(m))
VV
(m)
M
ve [M k== km
K-1
2E
M
Σ ΣΣ
Σ
V fm (zi
B Brax))
v.m
(x/m) xxx Bmmx))
V
Fm
(m)
M
mE[M]
0=
(49)
21f 1|
VF (
KT2
Σ
K-1 1
k EE
x
x
(112
122
M
mE[ad]
km0 x=O
K-1
+ 2E
sm
(Dr, BBmx)
(m)
x
(m²
B m,x))
V
V.m
(m)
V
Fm
(
(m)
M
mc[M]
k= k=0
(50)
< 2nf 11::
VF
2n
k E
(m))
x
(m))
1/2
M
me[ad]
R=0 x=0
Σ
E
(m)
x
(m)
(51)
M
1
mc M M
k=U x=
< K2 ||
VF (xx))
K3
Σ E
(m)
x
(m) 2
M
2
mE[M]
21 KL
Σ
Σ
K
B
(mm)
x
(m)
2
(52)
M2
2
me [M] A=ū
< 2T/ 1|
VF (a+)11
K2
I
+ +k22²) (10.
VF (+:)11
V/F (2:)11²
MM
(53)
22

---

Under review as a conference paper at ICLR 2023
where Equation (48) follows (a + 3)² < 2a + 2232; Equation (49) is based on variance expansion; Equation (50) is based on Bauchy-Schware inequality and Assumption 1; Equation (51) is based on Lemma 2 and Assumption 3; Equation (53) is based on Lemma 4. According to the constraints the local learning rate, we can further simplify Equation (53) as
Th K 2
E (loo((Ar)) - Tn K KVF (#:)l < 4n 11
VF (
VF
(xt)
(54)
Plugging Equation (54) into Equation (44), we have
7. K
L
EF(#L+1) F(t,) S
|VF (2))12
E
0++1 - Tz112
4
2
2
+ 2 K
0
VF FF (2
(55)
Let (t) indicate the most recent round where PA()) = and A(4) * t. It is noted that recursively
using A() can achieve the value of 0, i... (()(...(tt)) = 0 By summing Equation (55) from A(t)
multiple A
to 1. we have
1-1
EF(#;) F ( =
Σ
(BF(#e+)) - F(io))
(56)
(=A(1)
7.m K
<
Σ
IVF (x0))1
E
Ø8+1
-0o12
4
2
0=A(0+1
8=A(0)1
+ mmmmKK K
Σ
Eliee - VF (2
(57)
(=A(++1
The bound for the last term of Equation (57)
E Igge
VF (za) = E [lāA(0) VF (āx))
(58)
E (ÂΛ[0)
FF (αx(0))
1| +
VF (εx(o)) - VF (z+)
(59)
< E (ÂΛ(0)
VF (εx(0))
11 L'B
[ 2000))1
(60)
8-1
< E (Âλσ)) - VF (ū)
1| +
Σ
E
Ø=+1
2212
(61)
E=A(0)
0²
0-1
[((be) Mb
+ L,2T
Σ E=1(0)
D - क=
(62)
where Equation (59) is based on the variance expansion; Equation (60) is based on Assumption
Equation (61) is according to Cahwhy-Schwarz inequality and 0 1 A(()) < т; Equation (62) follows Assumption Based on the definition of A(-), for all {A(t) L,..., & 1}. A() A(t).
Therefore, with Equation (62), Equation (57) can be further simplified as:
EF(#.) F (#A(0)
(63)
< n K
t-1
Σ (=A(1+1
I/V |VFF (io)
E 10t1 - -00l2
22mmK
6=A(0)1
o²
+ 22 K (1 - A(1) - 1) ((cen) Mb
+ 2n
Σ
E [ - (64)
1
nstp K
|VF (io)11
2nm 2 KT?22
E El -5ol
12mmm
2
(=1()+1
23

---

Under review as a conference paper at ICLR 2023
d²
+ 2 (t A(t) - 1) (b-en
(65)
M6
Since T7T KL(1-2r)' Equation (65) can be further simplified as
EF( (#A(0) & 16 K
E
IV VFF
2n (1-A(1) A(t) -1) - [b<n) Mb
a²
0=)+++1
(66)
Therefore, based on the equation above, by summing up all e (T 1,A ,), we can obtain the following inequality:
F. - F(to)= S EF(ĀT+1) F(
(67)
7
Σ
IVF( 2 (T- (b<n) Mb
a²
(68)
4
t=0 mod T=0
Thus, we have
T
(F F.) nmm K (T-
d²
Σ
IVF (+:)1
+8. [bcn)
(69)
T T-
Mb
t=0; mod T=0
By using the settings of the local learning rate and the global learning rate in the description, we can obtain the desired result.
D.3 PARTIAL CLIENT PARTICIPATION
Theorem 5. Suppose that Assumption 1, and 3 hold. Let the local updates K 2 1, and the local learning rate Vi and the global learning rate UJs qal = 4 (1 2Mz where vp S
VIK
min
Therefore, the convergence rate of FedAMD for non-convex objectives
2V6KL' A/3L.)
should be
VF [F (2:)112 5 (- (1+ 2MT
)) +0 1 [(ben) Mb
a²
min
(70)
AE
A
where we treat F F. and L as constants.
Proof. When = 1, according to Algorithm 1, there no model update between two consecutive rounds, i.c., 0 Zt.
Next, we consider the case when = O. Based on Lemma 3, we have
T4TH K
L
EF( - F((,) _
|VF (x;))1
E [
-
2
211TTTKK
+
7s
E |aag(( Aaa)) - 1)1 KVF (2:)
(71)
2mp K
Knowing that when ps and a set clients A involve the training,
K
k
avg(Axz) Kg.
M
fm
12,x B B'n..)
(m²)
A
k=
k=0
1
k
11t
V
fm
x
B B,me)
(72)
4
we have the bound for TE |lang( (Am.) mp KVF (.:) 1/2 according to the following derivation:
E. (aug((Aa)) Tp KVF (..))l
(73)
24

---

Under review as a conference paper at ICLR 2023
E
M (g.
VF (+.))
+
M
K-
Σ
V
Fi Bl,x)
-Vf (z((0)
( Br,x) ))
(74)
KEA k=
2
S 2n/ 2²
1
VF (x:)11
2
+ +2E 2B
(8)
Blr)
Vic (1 1
(3)
Br,n.)
(75)
AEA R=0 x=0
2
K-1 &
21 K2 110e - VF (
+ 2B
m
Σ
Σ Σ
VP, ( - -VF, (m(A
A
iEA km K=0
K-1
Vii Tiine Bix) - Vic 1z Bi.e) (,
+ +2R 2R
VFF
(iip))
+ ViF
A
EEA k= 0=
(76)
21
18
VF (
2n K22
K- k
k EE
(4)
x
1,
(1)
2
2
iEA k=0 k=0
2
K-1
+ +2E
Vi
Bin)
Vf
(1)
(i. - VF;
+
VF,
(0)
A
TEA
0
x
(77)
< 21/ K2
1:0
(
2 KL
K-1
k
IF
(1)
(0)
2
2
EEA k=0 x=0
21
K-
+
(8)
(78)
1
1
iEA
k=0 k=
22
1,
VF (m:)11
2npK1²
Σ
K-1
k
E
2
(1)
2
(8)
2
M
mE[M]
k==
2n5
K k
Σ
(6)
(79)
AM
2
mE[M]
===
$ 21 2 K2 1
V (l:)1
13 1,2
(m)
(m)
2
M
x
1,,-1
2
me
[M
0=0
2n KL
AMV
Σ
K-1 Σ
E
t,k
(m)
x
(m))
2
2
(80)
me [M] K=U
S 21 K2
110e
V (mx)11
12 R2
12 AV
x²T.2)
(115- - VF (.:) VVF 122
-
(81)
where Equation (75) follows (a: + 3)² < 2n²2 + 2,3 Equation (76) is based on variance expansion; Equation (77) is based on Cauchy- Schwarz inequality and Assumption 1; Equation (78) is based on Lemma 2 and Assumption 3; Equation (79) is based the setting of client selection, where each client is selected with a probability of A/M; Equation (81) is based on Lemma 4. According to the
constraints on the local learning rate, we can further simplify Equation (81)
T2²² 2
E [vv((xx)) - KVF (ax)1 < 4nf K2 llā.
VF (2:)1++ +
|F (1))1
(82)
Plugging Equation (82) into Equation (71), we have RF((++1) F(x:)
(83)
25

---

Under review as a conference paper at ICLR 2023
MoTKKK K
4
S 4
(0:)112 - (2
E ||+ - #2.22 + 21 KE l1 - VF (
2
(84)
n K
1.
|VF (0x))12
E ||+ 2
4
2
+ +2n K
[ 110e - E0el2 + E. 1Bigt
V (.:)1
(85)
L
0²
|F ( - 2 K
E |
2e + 2 1 (bea) M6
4
2
+ 22.mm KE [gg VF (ā:)
(86)
where Equation (85) is based on variance expansion, and Equation (86) is based on Assumption 2. By summing Equation (86) for all E (0,..., T}, we have
F S EF((r)+) F(oo) Σ (EF (# F(t)))
(87)
S 15 K
T
1.)
T
Σ
VF (2:)
Σ
E | xxl12
4
2m-mi
2
t= med r=0
t=0tt mad r=0
T
a²
+ 21 K
E El
VF (+:) + 2 -T/T///T) 1 (bc)))
(88)
Mb
O= mod r=0
Let (t) indicate the most recent round where PA(e) = 1 and A(t) * t. It is noted that recursively
using A(-) can achieve the value of O, i.e., A(A(...A(I))) O.
multiple A
To find the bound for Σ D1= med r=0 E Egg F (Z:) the first step is to provide the bound for E ||g VF (.:) When p: = 1, a client updates the caching gradient with probability
of A/M, and therefore, Eg, (1 W) E@s(
A
M VF (ā:). Based this fact, the bound for
1gg. FF (3:))12 can be derived as follows:
|E F (#:) EāACo VF (#:)
(89)
A
E
E (DACACH) VF (εA(1)) + (VF (εx() VF
(æ:)) (
(90)
M
A
1 M
E
V (#
(ixe:) VF (2:))12 VF(#))1
(91)
M
[1/T|
11/T-00
M
T,2T Too 3<01)> 112+
M I [ - 1
(92)
M
A
A
9=0
a v73)² 5
where Equation (91) follows (a 3)² <
o2
(1+4) o² (1+ 7) 52 and 7 M-A, With Equation (92), we sum up all {I....,
and obtain the following result:
E |E
VF (
(93)
W1/1-1
W
Σ 1
A
M L'2
|oor 1
M. LL'B 12=
M
A
A
0=0
(94)
26

---

Under review as a conference paper at ICLR 2023
1-/1-1
M(M A)
M
L''E f
0(0+1)=112
L
Σ
Acccil22
(95)
A²
A
8=0
1=U
TT/
(0+1)T-1
((M A)
Σ
1227²
Σ
B| - ă=l12
A2
0=
E=0++1
M
1-1
+
L2
(t A(t) -1
Σ
T=+1 E=11
(96)
A
t=U
E=A(1)+1
M
A)
T-1
M
T-1
Σ
E 84+1 - xel12 +
-²
Σ
E B - xel12 (97)
A
A
Oct mod T
Out mod 7m0
where Equation (95) follows that, for 0 E {O...., [T/T] - 1}, the coefficient for M LL includes (1- (1-1) ......................... (1- A M
A
1T/=1-0 and each of them has a maximum of T Is, meaning that the upper
bound of the coefficient should be
(11- (I-M) -1-
(1-
(T/T]-
M
M
S T
2A
M ;
(98)
Equation (96) follows Cauchy-Schward inequality.
Plugging Equation (97) back to Equation (88), we have:
Dark K
F. F(0o)) S
Σ
IVF |VF((:))
t= mod ==0
- 2n.mKK
1
L 2
7TTH 1Tt KT,,2
M
Σ
T
E E| - -2ell3
A2
1=0; mod r=0
a²
+ 2m. K (T - (T/T]) [bcn)
(99)
Mb
Since 7/ =
1
(1 + 2M/7 -1
n K I.2,2
2 A2
2 such that the term
KL
2n.n
Σ Ei= med 7=0 [6++1 - iz 2 can be omitted in Equation (99). Hence, we can easily obtain
the following inequality:
(F - F.) +8 1.8.1(665))) (ben) Mb T K (T [T/r])
d²
Σ
VF (
(100)
T- TT/
t= mod r=0
By using the settings of the local learning rate and the global learning rate in the description, obtain the desired result.
27

---

Under review as a conference paper at ICLR 2023
E PROOFS UNDER CONSTANT PROBABILISTIC SETTINGS
E. PRELIMINARY
Lemma Suppose that Assumption holds, and Pt E 1). Let Dt the definition of Line of Algorithm I, i.e., the average of the caching gradients. Therefore, the recursive expression for (ie J120 2 in the expected form
[(1 M PI-1) Eği-1 + MP--1 VF V (To):
t> t=
Egi
(101)
Furthermore, when > O we can obtain the following inequality:
M
E | VF (zx)112 &
Pt-1
E -
VF (a.-1)1
L. |
ã, 1121
M
Apr-1
(102)
As for t 0, we have E |E
VF [
00 O.
Proof. According the definition of Line 9 of Algorithm 1,1++1 ang (U++1) to EmeiMi (m)
1/+1-
Hence, for each element in Ut+1, e(m) where m [M]] they have probability of (1 Pt)
to retain the previous value, or otherwise update as anchor clients using large batches. Thus, the expected value for Eu!ml is:
(m)
Ee ++1
(m)
EV fm (āz, Bmne)l 1)) +
1
M Pt
Ee(!m)
(103)
M
Vm (āx) + 11
M Pt) Eus (m))
A
(104)
M
Therefore, we have
Bgz+1
M
M
Eu
(m) 2+1
MPr
A (f,)) +
Pr.
(1
M
EEgr
(105)
m=11
It is worth noting that Eğo = V (@o) as it is initialized at the beginning of the training, i.e., Line 2
4 in Algorithm 1. Therefore, E
EEg
FF (2:)112 0.
Next, we find the recursive bound for [ F (#++1)
|[
VF (i
(106)
A
=R
M
Pt
(Eee
VF (æ:)) + (#,) VF (+
(107)
Ape
1
1
+
M Pt
E [B - VF VF (2x)112
M
Apr
M
Apt
+
1
+
VE (+.)
VF (i++1)11
(108)
Api
M L'EE || - 2x112
<
Pt
E ||
VF (2))1 +
(109)
M
Apt
where Equation (108) follows (a + B)² < (1 (1+ a² 81+ ( + v78)² <
(1+2)ar a² + (1+7) 3 and Equation (109) follows Assumption 1.
Lemma 6. Suppose that Assumption 2 and 3 hold. Let the local learning rate satisfy m S
min 2/3KT. 2/313 V
V K
With FedAMD, Ek-1 a
(mmm)))) ar k- || represents the sum of the
(m)
28

---

Under review as a conference paper at ICLR 2023
second norm of every iteration's difference. Therefore, the bound for such summation in the expected form should be
K-1
a² +6n (K+1) |E VF (6) | (a:)l
(m) 1,k
(m)) 2 1,k-1
S 2n (K+1)
Mb
k=
(110)
Proof. According to Equation (31), the update at (k 1)-th iteration is
k-1
t,k
(m)
-x, 11 -1,.i.,
(m)) (m) = -1 9r,0
(m)
Σ
(zr.-11
B,,x
Vim
(iix Bm.x)
(m)
k=0
k=0
(111)
To find the bound for the expected value of its second norm, the analysis is presented as follows:
E
x t
(m)
(m) 12 x.
1 12
(112)
k-1 1
1-1
of E
91
V fm
(2)m)
( (2in-1,,Bm m.rr)
B
+
V fm
x
(m) Bm,,))
(113)
x=0
K=U
k-1
n/ E
Egj
Vm 1 Bm..)B)))))))
- 5m (arg Bmma)) - V Fm
(2
(m)
+ V Fm (m))
0=0
--1 1
1-1
+ T/
Bgg
V Fm
(m)))
xt,,-11
+
V Fm
(m))
(114)
==0
~=0
ni
1 (bbm)
2 E
(m)
xr [m)
12
Mb
2
E
Rij
V
m
(m))
V Fm
(m)
(115)
k=0
o2
k-1
(m)
(m)
|2
1 ((ben)
+
x
M6
b'
x=0
+ m/ E
Eg: VF
(it)
+
VF (xx)
+
Fm (m))
+ VF
(x(
(116)
k=0
2
0²
(2)
S <ni
[(ben)
+
R
(m)
(m)
Mb
b
+ +3n1 -11E
VF (z.) ) 1|
3 | (3.)112 + 3m K
2
(m) (m)
|
(117)
0²
u 1(0m)) Mb
+ +3/
E Bgg - VF
V (1:)
12 B
+ +m?
KT' +
Σ x=U
E
(m)
(118)
where Equation (114) is based on the variance expansion on the first term Equation (113); Equation (117) is based on Cauchy- Schwarz inequality.
Therefore, by summing Equation (118) for k = 1...., K, we have
K
K
(m)
(m)
(m)
(m)
E
x
x
-
1
<
t
x
k
(119)
0=
k=0
29

---

Under review as a conference paper at ICLR 2023
0²
I ( (hen)
+ +-3r
+ 1) ||E - VF (2:))11 अगे (K + |VF (æ:)11
Mb
22
K-1
+ +37 K
(KL
ΣE
Σ
E
(m)
(m) -t
(120)
b'
Obviously, according to the setting of the local learning rate in the description above, the inequality 3qे K [KL + -0 < holds. Therefore,
easily obtain the bound for the sum of the second norm of every iteration's difference, which is consistent with Equation (110).
E.2 PROOFS FOR NON-CONVEX OBJECTIVES
The following lemma provides recursive expression on EF (i++1) F (ãz) for time-varying probability settings.
Lemma 7. Suppose that Assumption 1, 2 and 3 hold, and the time-varying probability sequence {pe E
/ujK (0, 1))2) Let the local updates K 2 1, and the local learning rate rp S min 2V6KL' 2/3L.
With the model training using FedAMD, the recursive function between F (#1+1) and F (āx) in expected form is
MstR K EF (#++1) F (
(1 (p:))*) |VF (#::)12
4 2) 2
| 2..12
Am (1 (p [Bğr VF (x:)
+ 3 K (1 (1- (pe) 1 [(ben) Mb
a²
(121)
Proof. According to Lemma 4, we have:
EF (i1+1) F (#t)
(122)
( 22
4) || - #el12
14 E. |A 7 KKF (i:
2m K
2n
(123)
When | = 0, the probability will be (1 - 4)% and when | * O, the probability will be
(1 - (1" Next, we find the bound for the third term of Equation (123), i.e., E Axx m/ KVF F (+. ) 2
By Lemma 1, we have the following derivation:
E Ar, RKFF F (
(124)
(1 (pt) )
M Σ
1
E
Az (m)
KKVF (3x) ||3 (IKKFFFFF))
(125)
M
EAA," (mn) 12 | + E EA TH KVFF (i:)
2
= (1 )p.)
EE
Aax
M m=1
+ (px) ni K
|VF (1)
(126)
where Equation (126) follows variance equation. To find the bound for Equation (126), first analyze its first term, i.c., E
Az (m) EAx, According to Section C, we have:
(m)
Am! (m)
EAn (m) 2
E
(127)
< 2n K2E ll - Eqg 112 + 2n2
K K-1
Σ k=
(K - 1)
I
(m)
- x
(m) 2
(128)
b'
(+ 2n2 12
o²
L2
< 2n/ K2
1 (bbn)
+ 12 1 122
(IE9. - VF ( + V/ (a:))13
Mb
(129)
30

---

Under review as a conference paper at ICLR 2023
where Equation (129) follows Lemma 6. According to the local learning rate setting in the description, we have
E Aa (m))
EAx, (m) 2 1| 4n 1 (bben)
o²
(130)
Mb
1.2
12m x²
(1
VF (+:))11
+
(131)
After finding the bound for the first term of Equation (126), we now give the bound for its second term, i.e.
EAx,"" (m)
'7. VVKE F (it)
E
EdAt (m))
77: VKFF (ātz)
(132)
K-
E
K (Eo.
(F((()) + m
Vm
Fiix
(m))
Vm
(2
(m)
(133)
k= k=
K-1
< K2² |Eg
VF (F.))11 + 2T
Σ
Vm
(m))
V Fm
(m)
(134)
k= K=0
K-1 k
$ K2 |Eq - (= + 2n KL
(m)
D 1
(m)
(135)
1
k==0 k=0
s < | (#:))11 + 27j K
K K(K -
L
K-1
x
(m)
(m)
(136)
2
k=0
o²
< K l[bent Mb
+ 2n 2n K2 (1 + 3n8 K2 K2L2) ||g
VF (F+)))11 + 6n 1 |[F F' (i:))12
(137)
where Equation (134) follows (a + B)² < 2a² + 2,3;; Equation (135) follows Cauchy- -chhwar
inequality and Assumption 1; Equation (137) is based on Lemma 6. Then, according to the setting for the local learning rate in the description above, we can further simplify Equation (137):
a²
E EAr, (mm) - MKFF (aa))
S 2n 1 1 (b<n) Mb
+ 4nf K2
|Eg
V (#:)11
+ 6n Kー |V (2:)
(138)
Plugging Equation (131) and Equation (138) back to Equation (126), we can primarily obtain the inequality below:
k2 E |z KKVF (2:)112 < 2n x² (1- (1-(p)))) (2 + n x222) 1 (ben)
Mb
+ K2 (1 (1-(p))) (p)) (1
1 (1+3/) 3nF
12
| - VF (#:)
(2L2
6nf K² 1 (po)))
+ +k222 (F)(1
(139)
+ (p.) 1/ K2 | (ā:)
(140)
With the setting described in the Lemma, we have:
E || KVF / < 6nZ kn x2 (1- (pi) (1-(1)))) 1 ((bkn) o²
Mb
8nf K² (1-(p))) ||Lgg, - VF (f:))1
Gnst K2 (1 - ((p)))) ( (212 + x22.3 /VF(2))
(141)
31

---

Under review as a conference paper at ICLR 2023
(pi) =2² | F
(142)
Therefore, according to the upper bound analyzed in the previous inequalities, Equation (123) can be reformulated as
EF (i(+1) - F (ix)
(143)
(2L3 S nTTKK (1- (px) (1-6r)) 6nî ( + =322 IIVE (#x)1
(2
2
| #2ll2
2
2
r²
+ 4n (1-(p)) |Eğ. - VF VF (#01l2 + 3nonk (p)) [(ben)) Mb
(144)
By means of the setting in the description above, we can obtain the desired conclusion.
Theorem 6. Suppose that Assumption 1, and hold. Let the local updates K 2 1, and the local learning rate Tp and the global learning rate be dal KL (1+
2M
/L V1-pa)
where
Ap
VorK 2VGKL A/3L.) ) Therefore, the convergence rate of FedAMD for non-convex objectives
S min
1
should be
(
M
)) +0 [(ben) Mb
o²
min (E(T)
VF (i:))l2 0
Apv1- ApVI-p")
(145)
T 1-
where treat F(oo) F. and L as constants.
Proof. With Lemma 5 and Lemma 7, we can find the following recursive function under the constant probability settings:
EF (it+1) + 4M K (1 p²) M
E [ie+1
V
11:+1)111
(146)
Ap
Am K (1 (1- E Eli - VF (#x) 1/2
To K
< EF (F.)
+
(1 (1-1a)
(VFF(()))
Ap
4
I.
4n K (1 p²) M M I
0141
km
2
Ap
Ap
o²
+ K3 K (1 -1-18 11= l(ben) Mb
(147)
Since 77,7 KL 1 +
2M
V1 11-p1 11-pa) we have:
Ap
F, < EF (T))= < EF (wt) + AmamKK (1- A² M
E Eggr VF (#7)1l2
(148)
Ap
< EF (ĀT-1) + 4n,m1 K (1 pAA M
E [E VF (#r-1)11
Ap
Bon K
0²
(1-p²) |IV (HT-1) 37.nK (1 - *² 1 [(ben)
(149)
M6
4m K (1 Aa M
< F (mo) +
|gg - VF (#n))l1
Ap
BonK K
T-1
o²
(1-pa)
VF ( 3T.nKT (1 A queett Mb
(150)
1=0
According to Lemma 5, |11go attain the following inequality:
VF ( = 0. Therefore, based on the derivation above, we can
T
4(F(@)) - F.)
0²
Σ
7TKKT (1 A) + 31 (b<n) Mb
(151)
T
32

---

Under review as a conference paper at ICLR 2023
By using the settings of the local learning rate and the global learning rate in the description, obtain the desired result.
E.3 PROOFS FOR PL CONDITION
Theorem 7. Suppose that Assumption 1, 2, 3 and hold. Let the local updates K 2 1, and the local learning rate ty and the global learning rate Tss Ta7] min
Ap
MMK(11pPy KL(I+ yey 1)
where Qj S min (11
VV/K 2V6KKL' IV3L. ) Therefore, the convergence rate of FedAMD for PL condition
should be
))
T
m Ap
EF (KT) - F. S 1 1- -1-p) min (Kk(1-p1) KL (1+
(F (ão)
F.)
16M
uAp
o² +0 ( (bbe))
11 Mb
(152)
Proof. With Lemma 7, we have the recursive function on the time-varying probability settings under PL condition:
EF (#++1)= - (
(153)
Bam
(1-(pt)))
|VF (2:)1 22
4)
||ē2+1 - -
4
2
(1-(p)))) 1 ((ben) o²
(1- (pi) ||g - (F()ill + +3
+ Ano M
(154)
Mb
Mm K
(1-(p))))
(pc) a) (F (ã+)) FF))= 2 K
1
L
|| 22112
2
2
+ mi K (1- |Eg VF (a:))1
3n m.KK K
(1 (1- (pi) (1-(n))*) (ben) Mb
(155)
According to the description, we consider the probability Pt and have:
EF (i++1)= F.
(156)
s <(1 pnan K
(1 - (1pp))) (F (āt)) - -F.) F 22 K
( 2)) || - #x.12
o²
+ 4no K (1 (1- El VF (a:)11 + 37 K (1 -) [(ben) Mb
(157)
Ap Since 7.m S 3Ku(l-paj have:
EF (Ā1+1) FF, + E EE FF VF
(#++1)l12
(158)
WhlTi K
(F((.) (1-pa)
F. 8 RR VF (s:))1
2
1
L
8 M 1?2
r²
||ā241 11 + 3n K (1 p² 1 1,sent Mb
(159)
2
l Ap
According to the description nam S KL(1+ 1832 1 L)¹ we have:
EF (a:+1) - F. S EF (#++1) - F. + - |ije+ V (w
(160)
MmnM K
(1 - (1-p)))
(at.)
+ E BBg VF (ax)113
2
o²
+ 3 K. (1 1) 1 [(hen)
(161)
Mb
33

---

Under review as a conference paper at ICLR 2023
(1 Mmlamkkk K
r²) 1+1
1
(F (f00) F.)
2
(1 mankk
(1 1-)))) 3n.nK (1 p*) (ben)
o²
(162)
2
M6
Mml K
(1 (1- p()) (F (āo) F.) + - (ben)
o²
1
(163)
2
Mb
By using the settings of the local learning rate and the global learning rate in the description, we can obtain the desired result.
34

---

Under review as a conference paper at ICLR 2023
F ADDITIONAL EXPERIMENTS
In the main text, we have analyzed some experimental results in Section 5. In this part, we conduct more thorough experiments by setting different numbers of local updates and different secondary mini-batch sizes.
F.I DETAILED EXPERIMENTAI. SETUP
Training on Fashion MNIST. Section 5, the experiment conducts on Fashion MNIST (Xiao al., 2017), an image classification task to categorize 28 x88 greyscale image into 10 labels (including T-shirt/top, Trouser, Pullover, Dress, Coat, Sandal, Shirt, Sneaker, Bag, Ankle boot). In the training dataset, each class owns 6K samples. Then, follow the setting of (Konečný et al., 2016; Li et al., 2019b) and partition the dataset into 100 clients (M = 100) such that each client holds two classes with total of 600 samples. By this means, we simulate the heterogeneous data setting. To obtain recognizable model on the images in the test dataset, we utilize a convolutional neural network structure LeNet-5 (LeCun al., 1989; 2015). Below comprehensively presents the structure of LeNet-5 on Fashion MNIST:
Table 3: Details for LeNet-5 on Fashion-MNIST.
Layer
Output Shape
Trainable Parameters
Activation
Hyperparameters
Input
(1, 28, 28)
0
Conv2d
(6, 24, 24)
156
ReLU
kernel size=5
MaxPool2d
(6, 12, 12)
0
kernel size=2
Conv2d
(16, 8, 8)
2416
ReLU
kernel size=5
MaxPool2d
(16, 4, 4)
0
kernel size=2
Flatten
256
0
Dense
120
30840
ReLU ReLU
Dense
84
10164
Dense
10
850
softmax
Training on EMNIST digits. In addition to Fashion MNIST, we utilize one more dataset EMNIST (Cohen et al., 2017) digits further assess our approach efficiency. This task is to recognize 10 handwritten digits with total of 240K training samples and 40K test samples. Similar to Fashion MNIST, we equally disjoint the dataset into 100 clients (M 100), and each client possesses two classes. The model is trained with a 2-layer MLP (Yue et al., 2022), i.e.,
Table 4: Details for 2-layer MLP on EMNIST digits.
Layer
Output Shape
Trainable Parameters
Activation
Hyperparameters
Input
(I, 28, 28)
Flatten
784
0
Dense 100
78500
ReLU softmax
Dense
10
1010
Validation metrics. The training loss is calculated by the clients who perform local SGD on the average loss of all iterations. As for the test accuracy, the server utilizes the entire test dataset after the global model updates. The gradient complexity is the sum of all samples used for gradient calculation by all clients throughout the training. The communication overhead is measured by the transmission between the server and the clients.
Miscellaneous. Our simulation experiment runs on Ubuntu 18.04 with Intel(R) Xcon(R) Gold 6254 CPU, NVIDIA RTX A6000 GPU, and CUDA 11.2. Our code is implemented using Python and PyTorch 1.1. Clients are picked randomly and uniformly, without replacement in one round but with replacement subsequent rounds. For each baseline, the local learning (7)) rate picks the best one from the set 10.1, 0.03, 0.02, 0.01, 0.008, 0.005). while the global learning rate (11.) is selected from the set {1.0, 0.8, 0.13. Without the annotation, we implicitly assume Fashion MNIST follows these settings: small minibatch size b' = 64, large minibatch size b full, and the number of local updates K = 10. As for EMNIST, we suppose the anchor nodes utilize the entire dataset for the caching gradient, i.e., b- full, and the number of participants in each round is 20, i.e., A 20.
35

---

Under review as a conference paper at ICLR 2023
Besides, to make BVR-L-SGD (Murata & Suzuki, 2021) compatible with partial participation in FL training, we only use sampled clients to compute the full gradients of local objectives instead using all clients.
F.2 MORE NUMERICAL RESULTS ON FASIIION MNIST
In addition to the empirical results in Section 5, we evaluate the performance of FedAMD by using different large minibatch settings. Then, considering the number of local updates K, we assess performance of the algorithm under various probability settings and compare it with other baselines.
F.2.1 COMPARISON AMONG VARIOUS TEPPER-PAAMMTTIR SETTINGS
The setting of large mini-batch b. Figure 2 - 4 depict the performance of FedAMD under constant probability 0.9, optimal constant probability, and optimal sequential probability, respectively, when the algorithm uses different bs. Overall, b sull always outperform b 256 and 64. Although there is no distinct difference between = 256 and = 64 terms of final test accuracy and training loss, b 256 is casier to attain lower training loss during the training.
80
80
Text Accuraty 150
150
70
Test Accuracy
60
Teat
300
Commanication Roundiss
Communication
(a) 20 clients
(b) 40 clients
(c) 100 clients
2.5
2.5
2.5
b-ful
b-full
b-
2.0
b-256
2.0
2-2
2.0
b 2566
b-64
bw64
2.5
1.5
Taining
2.5
2.0
1.0
0.5
0.5
0.5
300
(d) 20 clients
(e) 40 clients
(f) 100 clients
Figure 2: Comparison of test accuracy and training loss against the communication rounds for FedAMD with constant 0.9.
80
80
80
Teat Aucuracy (5G
7.0
Tuu Apouacy
70
Text Acruney
70
60
60
60
50
.00
200
300
400
100
200
300
400
100
200
300
400
Communication Roundis)
Communication Roundis!
Communication Roundis)
(a) 20 clients
40 clients
(c) 100 clients
2.5
2.5
2.5
betul
bu-tul
bulull
2.0
b-256
2.0
b-256
2.0
b- 2566
b-64
Trinking.o
2.5
Tranning
2.0
1.0
1.0
0.5
0.5
0.5
100
200
3.00
600
100
300 Communication Rounddss
200
100
200
300
400
Roundis)
Communication Roundis)
(d) 20 clients
40 clients
(f) 100 clients
Figure 3: Comparison of test accuracy and training loss against the communication rounds for FedAMD with optimal constant probability p.
36

---

Under review as a conference paper at ICLR 2023
80
Tea Noc.ccurao
Teas Accurac)
60
50
50
50
40
40
40
100
200
3.00
400
100
200
300
400
100
200
300
400
Communicattoo Roundis)
Communication Roundiss
Communicatton Roundis)
(a) 20 clients
(b) 40 clients
(c) clients
2.5
2.5
b-ful be64
b-full bw64
b-
b-
2.5
1.5
Training
4.5
1.0
1.0
1.0-
100
200
300
400
100
200
300
400
100
200
300
400
Communica Roundis)
Communkcation Roundiss
Communicattin Roundis)
(d) 20 clients
(e) 40 clients
(f) 100 clients
Figure 4: Comparison of test accuracy and training loss against the communication rounds for FedAMD with sequential {0, 1}.
Number of local updates K. Figure 5 - present the performance of FedAMD under the setting of 10, K 20, and K 5, respectively. In Section 5, we present the results under К 10 (Figure 5), which manifests that: (I) The setting {0, 11 is the most efficient performance under the sequential probability setting; (II) The setting near the optimal probability can attain the best result under the constant probability settings. In this part, we verify whether these two statements still hold two more examples. As for constant probability is set to be near the theoretical optimal one. However, statement (I) does not always hold in both settings. Specifically, when all clients participate in the training, {0, 0, 1} even outperforms {0, 1). A possible reason is that {0, O, 1} has more rounds to update the global model while the caching gradient does not significantly change compared to the situation running for one more round.
20 and
5, it can provide the best performance when the
80
80
Accurary 1500
Accuraty (60
70
70
Accuraoy
60
60
60
50
30
100
200
100
200
300
100
200
300
Communication Roundis)
Communication Round5s)
Communication Roundis)
(a) 20 clients
(b) 40 clients
(c) 100 clients
2.0
2.0
2.0
remiert
2.5
Traiing Loss
2.5.
2.5
aquartal
Taking
2.0
2.0
2.0
300
(d) 20 clients
(e) 40 clients
(f) 100 clients
Figure 5: Comparison different probability settings using training loss and test accuracy against the communication rounds for FedAMD by setting K 10.
37

---

Under review as a conference paper at ICLR 2023
80
60
Bust.uuuraac (16)
BustAocuracy (16)
MettArcuracy (56)
70-
70
600
60
50
100
300 Roundist
100
200
300
Communication Roundis)
Communication Roundis)
(a) 20 clients
(h) 40 clients
(c) 100 clients
2.0
2.0
2.0
conparts 6.5
denibri 6.
2.5
censarts
Traring Loss
1.5
1.5
Traring
Thaning
5.0
1.0
2.0
100
200
100
200
300
100
700
500
Communication Roundis)
Communication Roundist
Communication Roundis)
(d) 20 clients
(c) 40 clients
(f) 100 clients
Figure 6: Comparison of different probability settings using training loss and test accuracy against the communication rounds for FedAMD by setting K 20.
Test Accuraty 1880
Te0t Accuracy 150
Accuraccy 190
70
60
60
50
40
40
40
100
400
100
200
100
200
300
Communication Roundis)
Communication RoundEs
Communication Roundis)
(a) 20 clients
(b) 40 clients
(c) 100 clients
CuECIat Eit sequeiall
CENIDIEE
1.5
mianinng Less
Traiing Lass
Taaning
sigaeraa U...1
8.1.1
3.0
0.5
0.5
0.5
100
200
300
400
100
200
300
400
100
200
300
400
Communication Roundis)
Communication Roundist
Communication Roundis)
(d) 20 clients
(e) 40 clients
(f) 100 clients
Figure 7: Comparison of different probability settings using training loss and test accuracy against the communication rounds for FedAMD by setting K = 5.
F.2.2 COMPARISON AMONG VARIOUS BASELINES
In Section 5, we present the comparison in tabular format. Then, in this part, we visualize the training progress as well introduce more results under different Ks with the help of Figure In specific, Figure 8a 8f are summarized into Table 2, while the rest explore the efficiency of FedAMD under more scenarios. As described in Table 2 and the first six figures, when the conclusions we can draw include: (I) the final test accuracy of FedAMD exceeds that of the baselines; (II) FedAMD able to attain an accurate model with less communication and computation consumption. Next, evaluate the performance of FedAMD when K 20 and K 5.
10,
K 20 (Figure 8g - 81): In this case, the gradient computation of miner is around twice as that of an anchor. Therefore, FedAMD may consume less computation overhead than FedAvg and SCAFFOLD. In terms of final test accuracy, these baselines achieve similar results in all cases, while FedAMD achieves the performance with less computation overhead.
K (Figure 8m 8r): FedAMD eventually achieves the best accuracy compared to the existing works. Additionally, we can obtain well- rell-performed model with less computational consumption. These two phenomena are in support of the statements mentioned above.
38

---

Under review as a conference paper at ICLR 2023
80
80
80-
Text AcCurac 180
70-
Test Accuracy
70-
Text Accuracy
70-
60
60
60
-50
50
50
40
40
100
200
300
400
100
200
300
400
100
200
300
400
Communication Roundis)
Communication Roundist
Communication Round(s)
(a) 20 clients (K= 10)
(h) 40 clients (K 10)
(c) 100 clients (K 10)
2.5
2.5
2.5
2.0
TRAMP Sequurtte
2.0
TezAnD (onestrn
TEOAND (xqurrial
2.0
Festart lommano FaslaO incuente
2.5
Fadieg
2.5
Teckig
Thaiiing
2.5
Fackip
1.0
1.0
2.0
0.5
0.5
0.5
50
100
150
200
100
200
300
200
400
600
Gradient Complexity (x10P)
Gradiett Complexity (x2
Cradent Complexity 1x10.)
(d) 20 clients (K~ 10)
(c) 40 clients (K 10)
(f) 100 clients (K- 10)
80
80
80
Accuaacy (36
Accutacy
70
70
Accurry
70
60
60
60-
50
500
50
40
40
40
100
200
300
400
100
200
300
400
100
200
300
400
Communication Roundis)
Communication Roundtst
Communication Roundis)
(g) 20 clients (K~ 20)
(h) 40 clients (K 20)
(i) 100 clients (K- 20)
2.5
2.5
2.5
DVRLECE
2.0
2.0
TeSAnD (onster!!
PuEANE Degantidd
Taileo Feckap
2.5
Tadiug
Training
2.5
Tecky
2.5
2.0
1.0-
2.0
0.5
0.5
50
100
150 20o 250
160
200
300 460
250
500
750
1000
Gradient Complexity 6x10")
Gradient Grodeettt (220))
Gradient Complexity bx10'>
(j) 20 clients (K- = 20)
(k) 40 clients (K 20)
(I) 100 clients (K- = 20)
80
Text Accuracy (83)
Test Accuraoi 150
70
70
Accurncy
70-
60
60
60
30
50
50-
40
40
40
100
200
300
400
100
200
300
400
100
200
300
400
Communication Roundis)
Communication Rounddis
Communication Roundis)
(m) 20 clients (K = 5)
(n) 40 clients (K = 5)
(o) 100 clients (K = 5)
2.5
2.5
2.5
DVNLOCO
FvRL000
EVELSCD
2.0
Tedtar Sequertedd
TRAAND Deqarraa
Tassaro becuents Foilee) SCAFTOLD
2.5
SOMFOOLD
1.5
Nichy SCATTOLD
1.5
1.0
1.0
2.0
0.5
0.5
0.5
50
100
150
200
50
100
150
200 250
100
200
300
400
500
Gradient Complexity (x10")
Gr Gradient Complexity (x20")
Gradient Complexity 1x10")
(p) 20 clients (K- 5)
(q) 40 clients (K = 5)
(t) 100 clients (K" 5)
Figure 8: Comparison of different algorithms using test accuracy against the communication rounds and training loss against gradient complexity.
39

---

Under review as a conference paper at ICLR 2023
F.3 NUMERICAL RESULTS ON EMNIST DIGITS
In this section, Figure 9 analyzes our algorithm with one more dataset, i.e., EMNIST. In the first three figures, evaluate different probability settings. As for the rest of the figures, compare FedAMD with other baselines.
With regards different probability settings (Figure 9a 9c), we are still able draw conclusions as stated in Appendix F.2.1. As for the comparison among different algorithms, our proposed algorithm is able to outperform the state-of-the-ar works when we take the test accuracy and the computation overhead into joint consideration.
95
Test Accurary 180
Tor Acculio 190)
Text Accusarty
90
90
90
sawarip--
3 auampp
85
2sparip-t8
auwari GaEna
avang spana
sigaria
D.1
80
100
200
300
400
800
100
200
300
80
100
200
300
Roundis)
Roundss
Communication Roundis)
(a) K 10, D' 256
(b) K 20,
128
(c) K 10, 128
90
90
E
-90
60
DVILGOO Po tarn Segerdid
EviLaoo Peaare Desamnids
30
50
50
Pritar bopedto)
40
SCHFOLD
SCATTOLD
SCMPOLD
30
50
100
250
200
30
50
100
150
200
30
20
60
80
Gradlent Complexity (x10))
Gradient Complexity (K2
Gradient Complexity 1x10")
(d) K 10,
256
(e) K 20,
128
K 10, b' 128
Figure 9: Comparison of different baselines and probability settings using test accuracy against communication rounds and gradient complexity, respectively.
40


Reviews:
[{"review_id": "ntAG4Ck5qz", "reviewer": "Reviewer_Moju", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of improving convergence in Federated Learning especially under partial client participation settings. Differently from previous work, which either used large batch sizes or variance reduction techniques while resorting to full client participation, the authors propose a randomization of FedAvg and FedSGD. In that, the clients switch from being either anchor or minor groups. Convergence results are derived for non-convex losses under general conditions. Experimental results illustrate the efficacy of the approach. ", "summary_of_the_review": "The paper has weaknesses in terms of the convergence proofs with the dependence on the total number of clients being significantly worse as compared to other schemes.  The applicability, usability and originality of the paper is undermined by some assumptions which either don't hold or are difficult to verify in practice. Moreover, the randomization of a client either doing a local-SGD style update or no update, can lead to stretches with very few clients contributing to the update. Having said that, I would be more than happy to increase my score if my concerns are addressed.", "strength_and_weaknesses": "Strengths\n+ The paper is very well written and the algorithm is well motivated.\n+ The convergence results show an $O\\left(\\frac{1}{\\epsilon}\\right)$ for general non-convex losses and linear convergence with the extra PL assumptions which is an improvement over the state of the art.\n+ The proposed algorithm FedAMP also shows the efficacy of schemes which resort to heterogeneous batch sizes and updating schemes while resorting to variance reduction.\n+ The experimental results are comprehensive in terms of comparison with other baselines and tends to outperform other baselines.\n\n\nWeaknesses\n\n- Though the algorithm claims to use partial client participation; it requires a full client participation at the first step which in turn requires each gradient from each client to be individually available to the server and that too persisted over time instead of being available in an aggregated manner. This severely undermines the privacy-preserving nature of FL as it makes each client susceptible to gradient inversion attacks. It is also not clear how can this be alleviated without resorting to additional storage in each device.\n- The convergence results while improving in terms of $\\epsilon$-accuracy of the error, is substantially worse as compared to other baselines in terms of dependence on the total number of clients. While other algorithms scale inversely with respect to the total number of clients, FedAMP scales linearly with the number of clients in the setup. Unless, the number of selected clients is always a function of the total number of clients, it seems the performance of FedAMP gets worse with increasing number of clients, if the number of clients selected per round is constant. It is also worth noting the performance benefit comes at the expense of additional assumption 3.\n- An inherent assumption made by the authors is that the number of samples across clients is the same. The method by which a client is assigned to being an anchor or minor is solely decided by a coin toss and not based on the number of samples. In the general case, some clients may have fewer samples, in the case of which the number of local epochs and the batch size can't be uniform. It is also not clear how the choice $b$ and $b^{'}$ affects the algorithm performance.\n- The authors miss comparing and contrasting with FedNova by Wang et.al., which especially takes care of the case where different clients undergo different number of rounds along with the flexibility of running different local solvers. It would be good to add comparisons with FedDyn and FedOPT which are highly performant baselines.\n- While a theoretically optimal $p$ is derived, it can't be derived in practice as quantities such as the number of samples on each device and $\\sigma^{2}$ is unknown to the server. \n- For the variance reduction phase, it requires additional storage of the past gradient which is the same size as that of the model. This can be particularly prohibitive with larger model and resource constrained devices.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YKgmUEja4HP", "reviewer": "Reviewer_UWdf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a framework FedAMD, that disjoints the partial participants into anchor and miner groups. Clients in anchor group target to discover the bullseyes based on their local data distribution, while clients in the miner group perform multiple local updates and finally drive the update of the global model guided by the global bullseye. Under the partial-client scenario, this paper gives many theoretical proofs that FedAMD achieves sublinear speedup under non-convex objectives and linear speedup under the PL condition. Experimental results demonstrate that FedAMD is superior to SOTA works compared with BVR-L-SGD, FedAvg, FedPAGE, SCAFFOLD on Fashion MNIST.", "summary_of_the_review": "In general, it is a good paper. It has the SOTA results, many theoretical proofs and analysis. However, there are some weaknesses in the setting and analysis of the experiments section.", "strength_and_weaknesses": "Strength:\n1.The proposed FedAMD achieves sublinear speedup under non-convex objectives and linear speedup under the PL condition.\n2.The proposed FedAMD is superior to SOTA works compared with BVR-L-SGD, FedAvg, FedPAGE, SCAFFOLD on Fashion MNIST.\n3.The proofs of theories are detailed and correct, and they are consistent with the experimental results.\n\nWeaknesses:\n1.It seems that there is no analysis about the influence of initial model (line 1) on the experimental results in this paper. In fact, the influence of initial model exists (assuming that the best model is set at the beginning). It is suggested to add analysis about the influence of initial model.\n2.The experiment is too simple. \"We train a convolutional neural network LeNet-5 using Fashion MNIST\". Such a specific experiment may affect the degree of confidence of the experiment results.\n3.This paper proposes two strategies(constant and sequential) for selecting anchor and miner groups. But it would be better if there were a strategy based on the performance of each client.\n4.The analysis of g(i)t,k (line 19)is reasonable, but it is worth discussing whether a factor α is needed for second and third items.\n5.For the analysis of Figure 1, it seems that only Communication Rounds=400 is considered(why is 400?). Such analysis seems to be one-sided, and there are other considerations in fact, such as the change rate of the training loss.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "1Ah36DRJdF", "reviewer": "Reviewer_B281", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new federated learning algorithm which allows clients to perform their updates on the model using the gradient of the model obtained by other clients. This involves data samples stored on other clients memory in updating the model locally by a client. The paper provides convergence analysis for the proposed algorithm and examines its performance through experiments.", "summary_of_the_review": "In summary, the paper proposes a new federated learning algorithm at the cost of the need for a server with a large memory capacity. The paper proves the convergence of the algorithm. However, the paper lacks a detailed comparison of the proposed algorithm's convergence with the convergence of FedAvg. ", "strength_and_weaknesses": "Strength: The paper proposes a novel way to enable clients to share their gradients and use this information to update the model locally. The paper proves the convergence of the proposed algorithm and provide convincing experimental results to validate the theoretical analysis provided in the paper.\n\nWeaknesses:\n\n- Using the proposed algorithm, the server has to store a caching gradient matrix whose dimensions scales with the number of clients. When the number of clients is so large, to implement the proposed algorithm a server with a very large memory is required.\n\n- It is beneficial for the paper if the convergence rate of the proposed FedAMD is compared to FedAvg to see what are the benefits of FedAMD compared to FedAvg in terms of convergence. FedAMD requires larger memory from the server side and it is interesting to see if FedAMD uses this memory successfully to obtain better convergence rate than that of FedAvg.\n\n- From reading the Algorithm 1 on page 4, the role of cached gradients in updating models is not clear. It would be great if Algorithm 1 can be revised such that the role of cached gradient become obvious.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject