A Unified Analysis of Federated Learning with Arbitrary Client Participation
Authors: Shiqiang Wang
Mingyue Ji
Venue: NeurIPS 2022 Accept (2022)
Keywords: federated learning
partial client participation
convergence analysis

Abstract: Federated learning (FL) faces challenges of intermittent client availability and computation/communication efficiency. As a result, only a small subset of clients can participate in FL at a given time. It is important to understand how partial client participation affects convergence, but most existing works have either considered idealized participation patterns or obtained results with non-zero optimality error for generic patterns. In this paper, we provide a unified convergence analysis for FL with arbitrary client participation. We first introduce a generalized version of federated averaging (FedAvg) that amplifies parameter updates at an interval of multiple FL rounds. Then, we present a novel analysis that captures the effect of client participation in a single term. By analyzing this term, we obtain convergence upper bounds for a wide range of participation patterns, including both non-stochastic and stochastic cases, which match either the lower bound of stochastic gradient descent (SGD) or the state-of-the-art results in specific settings. We also discuss various insights, recommendations, and experimental results. 


A Unified Analysis of Federated Learning with Arbitrary Client Participation
Shiqiang Wang
Mingyue Ji
IBM J. Watson Research Center Yorktown Heights, NY 10598
Department of ECE, University of Utah Salt Lake City, UT 84112 mingyue we.jjjitteheeee.. edu
wangshiquus imm. com
Abstract
Federated learning (FI.) faces challenges of intermittent client availability and computation/commuiiaaaii efficiency. As result, only small subset of clients can participate in FL at given time. It is important to understand how partial client participation affects convergence, but most existing works have either considered idealized participation patterns or obtained results with non-zero optimality error for generic patterns. In this paper, we provide unified convergence analysis for FL with arbitrary client participation. We first introduce generalized version of feder- ated averaging (FedAvg) that amplifies parameter updates at an interval of multiple FL rounds. Then, we present a novel analysis that captures the effect of client participation in single term. By analyzing this term, we obtain convergence upper bounds for wide range of participation patterss, including both non-stochastic and stochastic cases, which match either the lower bound of stochastic gradient descent (SGD) or the state-of-te of-te-of-the-ar results in specific settings. We also discuss various insights, recommendations, and experimental results.
Introduction
We consider federated learning (FL) problem with clients
17
20
38
Our goal to minimize:
f(x) = ( (x)x).
(1)
where x E RT is an m-dimensional model parameter. The local objective (x) of each client n is usually defined (x) EE,,D,, 1en (x, En. where D, is the distribution of client n's local data, which cannot be observed globally because the data remains private, and (x, {) is the per-sample weighted loss function for parameter and input data ç. The objective (I) can be extended
average, but we do not write out the weights and consider them as part of fx, {) and F, (x). A canonical way solving (T) is to use federated averaging (FedAvg) (24), which is form of stochastic gradient descent (SGD) that operates in multiple rounds, where each round includes multiple local update steps followed by communication between clients and a server to synchronize the updates.
Partial Participation. A major challenge in FL is that clients only intermittently participate in the collaborative training process (3]. The reason is twofold. First, FL applications usually have large pool of clients. It is impractical to have all clients participating in all FL rounds, because would require computation and communication that can consume large amount of energy and also lead to network congestion. Second, clients may become unavailable from time to time. For example, if the client devices are smartphones, they may be willing to participate FL only when they are charging (usually at night), to avoid draining the battery in outdoor environments where no charger is available.
Open Problem. The convergence of FL algorithms with realistic client participation patterns has not been fully understood. Most existing works on partial participation have only considered idealized scenarios, such those where clients randomly selected according to given probability distribution that is independent across rounds
22 36). They cannot incorporate cases
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Summary and comparison of results (only showing baselines without constant error term)
Method
Participation
Convergence error upper bound
Remark
Unavailable
(1402)N
VE
Add't assumption: bounded gradient norm
Yan et al. B5
o
< E' rounds
VST
Unavailable
(1+
Add'l assumptions: Hessian
Gu et al.
12
0
x E rounds
VNIT
Lipschitz, a.s. bounded noise
Regularized
0
Cor, 4.3 matching
VSIT
centralized
SttrrlizeddGGD SGD lower bound
Ours (this paper)
Ergodic
Approaches zero as T +00
Prop 4.4
Mixing
0 1+o2 VSIT
i.E.; ( 1+
(vVSIT)
w.p.
1-c
matching Idcalized bound
Prop, 4.6 & Cor, 4.8
Independent
1+ V8IT
i.F.;
O (1++a In(2/c)
VSIT
w.p. 1-c
matching idcalized bound
Prop. 4.7 & Cor. 4.8
We let p= / in our results a direct comparison with other works, see Section 5 for more details. We consider sufficiently large T in all cases and only show the dominant term in this table, with other variables ignored in ((-). Definitions: i.E. expectation, w.p. with probability, a.s. almost surely, St number of participating clients in cach round (S < N), other definitions are given throughout the paper.
Note:
where clients are unavailable for period of time. Some recent results considering general scenarios either include constant error term that does not vanish at convergence [5] 37
otherwise less competitive than state-of-the-ae results obtained in idealized settings [12 35 Therefore, we ask:
1. What classes of participation patterns have guaranteed convergence to zero error?
For these classes, can the convergence rate match with that obtained in idealized scenarios?
To answer these questions, we need to overcome two challenges. First, we need to devise a unified analytical methodology for obtaining the convergence rates under various participation patterns. Second, we need general and realistic algorithm for cross-device FI., with appropriate control options that can be configured to make the convergence rate competitive.
Our Contributions. In this paper, we overcome these challenges and give answers to the two questions above. We first introduce a generalized version of FedAvg, which amplifies the parameter updates after every P rounds, for some P 2 1. When P = 1, our setting is the same as FedAvg with two-sided learning rates [8 36), but we focus on an extended setup where P can be greater than one. For this generalized FedAvg algorithm, we perform new convergence analysis that unifies the effect of partial participation into single term (P) in Section 3). This allows us to decouple our main convergence analysis from the analysis on partial participation, which largely simplifies the analytical procedure. Our novel methodology gives the results shown in Table [ for broad range of participation patterns. These patterns include -tochaacc and regularized participation, where all clients participate equally but not simultaneously within P rounds, and stochastic participation settings including ergodic, stationary and strongly mixing (e.g.. Markov process), and independent. For the stochastic participation, we provide both expected and high probability convergence bounds, where the expected rates match the state-of-the-ae FedAvg convergence rates that were derived for the idcalized setting of random participation following independent distribution. Furthermore, provide new insights related to non- IID data, amplification of updates, "lincar speedup" [39], etc.
To summarize, our main contributions are as follows:
We introduce generalized FedAvg algorithm which amplifies the updates aggregated over multiple rounds, where the amplification interval P can be tuned for the best convergence.
We present novel analysis and unified methodology for obtaining competitive convergence upper bounds with arbitrary client participation patterns.
We discuss important insights from both the theoretical and experimental results.
Related Work. FedAvg (4 is characterized by partial client participation and multiple local updates in each round. In the case of full participation, FedAvg is also known as local SGD [O0 14, 23 28 30
and parallel restarted SGD 40) Partial participation was considered 4 the assumption that clients are selected to participate probabilistically according to a given distribution that is independent across rounds. Some recent works have started to incorporate unavailable clients. For example, the work in (27] allows inactive clients, but the theoretical result does not guarantee
& 9
18
21 22 36 with

---

convergence if a client participates with zero probability in a certain round. Similarly, the result in 5 includes constant error term in the case of general participation in cross-device FL. Other works have obtained convergence rates related to the maximum number of inactive rounds, based on additional assumptions such as Hessian Lipschitz [12 and bounded gradient norm 35 Their theory also requires all clients to participate once at the heginning (see [12] Remark 5.2]). In contrast, our result in this paper is based on a minimal set of assumptions. We consider a simple algorithm without requiring initial full participation, and we provide a better rate of convergence to zero error (see Table D. Moreover, existing methods usually have separate analyses and results for each specific class of participation pattem, whereas we present unified framework that largely simplifies the analytical procedure. Some more discussions on related works are in Appendix A. Note that all the appendices of this paper are in the supplementary material.
2 Generalized AvdAvg with Amplified Updates
We consider a generalized version of FedAvg as shown in Algorithm | In this algorithm, we define qf to be the participation weight of client in round t. If qf O. the client does not participate in this round. Each client n participates whenever g" > 0, where the weight qf' is applied in the global update step in Line 9 For mathematical convenience in our analysis, we assume in Algorithm that all clients compute their local updates in Lines 8 regardless of whether they participate in the current round or not. We emphasize that this is logically equivalent the practical setting where non- con-patiicipaiing clients do not compute, because their computations have no effect in subsequent rounds when of (see Line 9.. every round I, each client n computes T steps of local updates according to Line where y > Ó is the local learning rate and g (yT,)) is the stochastic gradient of (y2,)) such that E B (yF,)) v2, - (y,,).))
Starting at round to. the global updates are accumulated in u for P rounds (Line 10.. At the end of every interval of P rounds, amplification is applied to the accumulated updates (Line Since x is first updated without amplification in rounds ,o...., to + P 1, Line 12 adds u after multiplying " -- 1, which is equivalent to setting X to Xt, 1ju. When 17 1, there is no amplification and Line 12 has no effect in this case. In general, we allow any 1) > 0 including values of v) that are less reduce (instead of amplify) the updates. Intuitively, amplification with >>> 1 is usually preferred over reduction, because we can compute the gradients on similar model parameters in each round where only a small number of clients participates. After P rounds, the accumulated updates provide a better estimation for the overall client population, and amplifying the updates allows the model parameter to progress towards the descent direction for the majority of clients (see Appendix B.1 for an example). Also note that although P is parameter in our algorithm, the dominant terms of our convergence upper bounds shown in Table [ do not depend on P.
than one. When 7)
Algorithm 1: Generalized FedAvg with amplified updates and arbitrary participation
Input: 7. 1/, Xg. I, P, T; Output: (x, :V)
2 Initialize to + 0, + 0; 3 for 0...., T
do
X++1 + x; + +> N
n=1 o. AY: //update
for n = , N in parallel do yi, <- Xt;
10
u u Σm= 07 A.:
/accumulate
ift to = P then
for O,...,
do
12
X4+1 + X + (1 - 1)u; //amplify
y Vi.+11 y2, 7g (v7,))
to +++
A Vo.1 Xx;
14
0;
3 Convergence Analysis and Main Result
We analyze Algorithm 1 as follows. For ease of analysis, we assume that > q6" 1 for of 2 for all We also define such that EN>n(a?)) < p² for all t. As E l = 1, there always
When >> qi" # 1, the algorithm is equivalent to the case of {g } normalized to one and a global learning rate applied to the updates in each round. Since we already amplify the updates every I' rounds, we do not apply separate global learning rate to each round.
3

---

exists p such that p² < 1. We define Q : p& Vn, tj. Mathematically, we use the conditional expectation E 2 denote the case where Q given and the expectation is only over the stochastic gradient noise. In the case where Q is stochastic, the full expectation E, [-] is taken over both the noise and Q. We make the following assumptions that are commonly used in the literature.
Assumption (Lipschitz gradient).
[V (y)l S -|| yll, vx,y,n.
(2)
Assumption 2 (Unbiased stochastic gradient with bounded variance).
E [g (x) x] (x) and E [Il).(x) V.
x S vx,
(3)
Assumption 3 (Bounded gradient divergence).
[V - v 2 S d, Vx
(4)
The gradient divergence in Assumption B is related to the degree of non-IlD data distribution across
clients. To better interpret how different divergence components affect the convergence, we introduce an alternative set of divergence bounds in Assumption 3 as follows. We will show later (in Section 4 that if Assumption 3 holds, then Assumption 3" also holds with properly chosen 3 8², and 8² (P).
Assumption 3' (Alternative gradient divergence bound).
Ex oi
[ (x) [x))||
S 3 VX
(5)
N oi FFn(x) - Ex of (x) || s vi,
(6)
P tt En of (VFx(x) {((x)|| S SP)) Vx, ln-
In the above, 32 and 8² capture the gradient divergence in an arbitrary round and (P)) captures the divergence of time-averaged gradients over rounds, which a function of P. In particular, 3 is an upper bound of the divergence between the original objective's 's gradient fxx) and the averaged gradient among participating clients weighted by } When all the clients participate, we have qf" = 1 and (5) holds with 32 O. The quantity 172 is an upper bound of the divergence between each client's gradient and the averaged gradient of participating clients, where the average is also weighted by {4' }- We will show in Section 4.1 that the overall divergence d' in Assumption 3 can be expressed as a sum of 32 and i², as intuition suggests. The quantity (2(P) in 7 extends 32 in (5) by computing the average over 1 rounds (inside the norm) instead of a single round. When the weights {g") J are properly chosen, as P' gets large, the average q', over /' rounds gets close to each other for different n, and 8² (P) becomes small. We will formally analyze this behavior in Section 4.2
In the following, let F = f(xo) f", where f* is the true minimum of ①1 i.e., f minx (xx). Theorem 3.1. When Assumptions / and 3' hold, 7 S 12LIP 79) S LIP, and P < 2. we have
| |V o]
min E.
F MIT + +
s
0
+ (8P) (12 + (111118-----0---------------- + mL) 02
(8)
Proof Sketch. We first use smoothness to relate +() and f(x,,), which includes inner- product term that can be expanded into several terms. One of these terms includes V Fa(y?
v(((.). We upper bound this term with three other terms including yT. Ew= of y:
Σw= of yn Xto and 82 (P)). The upper bounds of the first two terms are found by solving recurrence relations, where the recurrence for the second term includes the first term. This nested recurrence is uniqueness in this proof. The full proof is given Appendix C.
For two specific (but differentt learning rate configurations,
obtain the following corollaries.

---

Corollary 3.2. Choosing 7 I2LIPVT and 1j min
12P
:12VT] for P P T
we have
op
min E [VF((x)] o so OPVLF LPF
32
0²
(P)+
IPT (9)
VIT T
PeT
T
Corollary 3.3. If JF PVLIT
S Ltp, choosing 7 12LJPVT and 11 12PVLIE for P S I
we have
min [V o] so (1+ VIT
8
B2 T +0
o²
(10)
PPT
IPT
These two corollaries are key building blocks of our unified convergence analysis framework. The choice between them depends on whether and how fast grows with T. We will also see in the next section that (P) is key in capturing the effect different participation patterns. After deriving (P) such that ( holds, plugging it back to one the above corollaries gives the results in Table
4 Interpreting and Applying the Unified Framework
4.1 Discussion on 32 and i²:
Decomposition of Divergence
In Corollaries 3.2 and we have an interesting observation that the term involving ū decreases with P. whereas the term involving 3 does not decrease with P. This suggests that when P large, the divergence term 3 has the main effect on convergence. We recall that captures the divergence between the gradient of each client and the average gradient of clients that participate in a round t. Since the learning rate y inversely proportional to both and P, large gives smaller learning rate which makes the divergence (related to Di) after iterations in each round less significant. For the term with 3, increasing P does not have the same effect, because parameter averaging is only conducted across the participating clients instead of all the clients, and 8 captures the divergence with respect all the clients. The effect of all clients' participation pattern is captured by the term 8 (P)..
From Assumption by adding and subtracting Ew= qi F (x) inside the norm and expanding the square, we can obtain
Σn Tf (x) fx())
-N Lf (x) - Ew VF + EN o. (x) T/(x)| -V) S de, (11)
because ΣN df 1 and the inner-product term is zero. The two terms in the right-hand side (RHS) of (II) are equal to the left-hand side (LHS) of (5) and (6). respectively. We thus have the following result showing that f²2 and i? can be seen as a decomposition of the original divergence d²
Proposition 4.1. There exist 32 and i? such that 32 + 2 < de while satisfying and (6)
4.2 Discussion on (P))): Effecc of Partial Participation
The results Theorem 3.1 and Corollaries 3.2 and 3.3 include term of 8P To guarantee convergence to zero error, (2()) needs to be either equal to zero or decrease in T.
Condition for (P) O. From
we know that 0 = IN Fx(x) - f(x) =
N (F,,)((())) (Fr(x) f(x)). Hence,
Pio ΣN
- (x)
(12)
for an arbitrary constant Mto which can possibly depend on to. Then, we obtain
| Eist 1o+P-1 'N of (VFx(x)
((()))
D - 1ot--- of (VFa(x) -V
Po to oe Mmo
(x) (x)-
(13)
where the last equality is due to
12
Since
13 is equal to the LHS of (7) have the following.
5

---

Proposition 4.2 (Regularized participation). If P Li=ta qi Pto 0 for some Pto and all n [I,...,,N,, NJ. to P.,,..P..... then 7 holds with 8²( =0.
Il++P-1
This implies that if P is chosen so that the averaged participation weights over every interval of NN, ie., regularized, then (P) O. O. Together with Corollary 3.2 and Proposition 4.1 we have the following.
P rounds ( Po+ P-1 4²') are equal to each other among all the clients E
Corollary 4.3 (Regularized participation). If the condition of Proposition 4.2 holds for P S T.2 and we choose the learning rates according to Corollary 3.2 then
OOVLF ( VIT
LPF + d +
min E [IV
2) S
(14)
T
If Proposition 4.2 holds for a finite P that does not depend on T, we obtain a convergence rate of for T 2 2P, where all the other constants are ignored in the O (-) notation here. For full gradient descent with o² = 0, this convergence rate is improved to O (#).
O
Interpreting (P) Using Variance. The condition for 8 (P) 0 may be too stringent for some practical scenarios of FI.. Next, we show that 82 (P) be expressed the variance of client participation weights averaged over P rounds. We first express (P) with de by further bounding:
13 S N
Ln
Pto] 1 d:
(15)
where we first use Jensen's 's inequality on the sum over n in (13), then move the term gh Pto to the outside of the norm, where we define 8% == P Ei=to EittP-1 qf for any n [l....,N]] NV. and afterwards (x)il by d' according to Assumption 3 We note that 7 holds if the RHS of 15 is upper bounded by (P). Therefore, we obtain (P) by analyzing the statistical properties of gh Pro and then choosing (P) to be equal to the RHS of (15).
bound V Fx (x)
In the following, we assume that (eg is chosen such that Pt. = E [q" for all n E [1....,N] and I E (40, 40 - 1,...., 40 + 11. This implies that the mean participation weights of all the clients within the same cycle of P rounds are equal. Note that this condition is the same as unbiased client
sampling in existing works [8] |9, [8 21 22 36), because we consider an unweighted average in ( and any weighting is included in the local objective function F,, (x). However, differently from these existing works, we do not assume independence here (we will only assume independence in a special case later). Under this condition, is apparent that Var (4%) E -Hoo)" is the variance of of averaged over P rounds, for any E .L.....NN. We immediately have the following result. Proposition 4.4 (Ergodic participation). If {4E VI} is a mean-ergodic process for any E NJ. which means that limp E (g% - mi.) = for any n and to, then there exists (P) such that limp- (P( = 0 while satisfying 77 in expectation.
Next, we consider the class of stationary and strongly mixing processes. Informally, a random process is said to be strongly mixing with coefficient ax( P) if the outcomes that are at least P steps apart are nearly independent, where the distance between the joint probability distribution of the outcomes and their independent counterpart is at most ar( P). See 2 Sec. 27] for formal definition. A specific example of stationary and strongly mixing processes is finite-state irreducible and aperiodic Markov chains, which have an a(P) that exponentially decreases in P (2) Thm. 8.9]. It is known that the following (generalized) central limit theorem holds for stationary and strongly mixing processes, where we adapt the result to participation weights.
Lemma 4.5 ((2) Thm. 27.4)). If (ge Vt} is stationary and strongly mixing with a(P) = 0(P-5), 6²) for any n E NN, then g. ~ N (Mror FF) for any to when P + cc, where A(...) denotes the normal distribution and 8² = Var(g))) + + Ep- Cov(gl, Pbyp))
From the definition of strongly mixing, we know that Cov(gi, L Pb) in the definition of 8² ap- proaches zero p gets large, hence Dp= Cov(gl po+ converges to finite value. When P - co

---

and (PP) ((P-5), Lemma 4.5 shows that Var (0%g)
6²
Chebyshev's inequality gives
p.
Pr Aho meo
02 cP
2 c.c.
(16)
Plugging Var (
0% mo P and C Mco) cP into the RHS of (13) gives the fol-
lowing expected and high-probability results, respectively, where "w.p." stands for "with probability".
Proposition 4.6 (Stationary and strongly mixing participation). If (f VII is stationary and strongly mixing with ox P) = (P(5)), )) for any n (1....,N) NN, then as - 0o: Choosing (P) d² 8² satisfies 7 in expectation; (P() = cP
N2 satisfies 7 w.p. 1
P
For independent participation, we can obtain a similar result while not requiring
cc. Assuming
that Var(g") ) I x² for any and n, it is evident that Var (geg S pr. because the variance of the sum of independent random variables is equal to the sum of the variance, and Var(oZ) = varr (2), for
an arbitrary constant and random variable Z. We note that Hoeffding's inequality [T6] gives
Pr
pto
In(2/o) 2P
21-c.
(17)
We have the following result by plugging into the RHS of (1)). Proposition 4.7 (Independent participation). If {g Vt} is independent across t, for any n, then:
Choosing (P) = 2² satisfies in expectation; o² = N'd' ln(3/a) satisfies 7 w.p. 1 1-c.
2P
Note that the independence here is only assumed across I, so of and of for the same / but + n' can still be dependent of each other. Compared to Proposition 4.6 the high-probability bound in Proposition 4.7 has in the logarithmic term, which is tighter since 2 In I
(ignoring 63).
Choosing P Function of T. The choices of (P)) in Propositions 4.6 and 4.7 include P in the denominator. Hence, we can guarantee convergence to zero error if we choose to be an increasing function of T, which also ensures that P - oc as T > co. If we choose P x N / IT, we can obtain the following convergence rate from Corollary 3.3 together with Proposition 4.1
Corollary 4.8 (Stochastic participation). If the conditions of either Proposition (4 Proposition 4.7 hold, and we choose P G2N! VTT or P N²N VIT, respectively, and the learning rates according to Corollary
3.3 then the convergence error in expectation over Q satisfies
(1 (V+
d²
d +02
min [ 0
(18)
VIT
VNIT
T
for 1 NLF and - oo when using conditions of Proposition 4.6 or I JeN and T 2 1N5 when using condition of Proposition 4.7
Remark. Although the upper bound of I in Corollary 4.8 may appear restrictive, note that the optimal solution x" T remains the same when the objective f(x) is scaled by multiplicative positive constant, which in turn scales v VLF More specifically, consider an arbitrary a >> 0, we define D
F'(x) == aF (x) and f'(x) == N m= F (x) = (x). Then, we have f'(xx) - -f' (xp) af* = aF. We also have [[ Assumption
(y)] = a (x) - VI, (y)l S a||||x yll from with Fx),,, [ due to the linearity of gradients. Hence, by choosing
(0, and replacing F(x) make VLF arbitrarily small and / u2N (the upper bound of I in Corollary (48) arbitrarily large without affecting the optimal solution x". Thus, we can potentially allow arbitrarily large by scaling f(x without changing the optimal solution x". We leave the in-depth study of this phenomenon for future work, where we recognize that such a scaling will affect the LHS of the convergence bound too, although the optimal solution x* does not change.
We also give the following further insight related to Corollary 4.8 In Corollary 4.8 we choose P to be proportional to the variance 62 or v². This is intuitive because when the clients' participation weights have higher variance, we would like to wait for more rounds before amplifying, contributions of clients are more balanced. In the same way, P increases with the number of clients
that the
N. Recall that En 1 z. = 1, Intuitively, when the participation patterns of individual clients remain
7

---

"unchanged", of scales with 1 and its variance 6² or v² scales with 32. NZ, so the product N2 ~ VN or N VN, implying that P effectively scales with VN when this intuition holds.
N
While the result in Corollary 4.8 is in expectation, the high-probability bound is similar (see Table D
In general, since 7 is used as an upper bound in the proof of Theorem 3.1 if ( (PP) is chosen so that
77) holds in expectation with certain probability, such in Propositions 4.4 4.6 andd then the
final convergence result also holds in expectation or with a certain probability, respectively.
5 Discussions and Insights
Interpretation of "Linear Speedup".. Linear speedup is a desirable property seen in existing works that consider idealized client participation [36 (3 40). It essence, it means that the same convergence error can be achieved by increasing the number participating clients (with S S N) and reducing the number of rounds T, while keeping the product ST unchanged. In our case of arbitrary client participation, the coefficient P is a generalization of the 1/Vs term for linear speedup in existing works that select fixed number of S clients in each round. When S clients participate with equal weight, because Σn q. = we have of 1/s for the participating clients and q = 0 for the
non-participaainng clients, so p - results, we achieve convergence rate of O ("/VSTT) in Corollary 4.3 and O (a++ (()ST) in Corollary [4.8 for sufficiently large T while ignoring the other variables in O()). as shown in Table [ This shows that we can achieve linear speedup in S in this special case. We can also generalize
N - ) 1/2 1/V3. Plugging this p back to the convergence
to having at least Smin clients participating with equal weight in each round. Following the same
argument, we have p S 1//Smii. in this case, giving linear speedup in Smin. In general, we achieve a linear speedup factor of 1/p² in the case of arbitrary participation.
Matching Lower Bound or State-of-the-Art Results. We continue to assume sufficiently large T. For regularized participation (Corollary (43), our convergence rate of O (*/VSTT) matches the lower bound of convergence error for centralized SGD [1. The lower bound states that to reach a convergence error of e, there exists an objective function such that at least Q (e²/2) stochastic gradient oracle calls are required [ We have SIT oracle calls to reach = O (o (/Isr) according to our result, thus our upper bound matches this lower bound and is asymptotically optimal. Note that our upper bound still matches the lower bound if we include the coefficient VLF in O (.) and LF in Ω (-). For stochastic participation (Corollary 4.8), our convergence rate of O (a + ////STT)) matches state-of-the oaate-o-thhe-ur the-art results of FedAvg [8 18 36 that were obtained for the more idealized case of clients being selected participate according to specific independent sampling scheme.
Special Case of Waiting for All Clients. We consider a specific configuration of FedAvg where all the clients wait for P rounds before proceeding with SGD. In every iteration i of round f within these P rounds, each participating client n may call the stochastic gradient oracle to obtain g. (x:). but it does not perform local updates. Instead, it accumulates and averages the sampled instances of ga (x.). SGD is performed once after these P rounds using the average gn (x,) from each client n. Assume that P is large enough averaged afterwards. If the M instances of gn (xx) are all independent from each other, the noise o² (defined in Assumption 2) becomes o² /M. This configuration can be considered Algorithm| [ where all N clients perform SGD once in P rounds, so there are T/P updates in total, with reduced stochastic gradient noise of o² o²/M.. By replacing a and STT in our bound O (*/VSTT) with o/vTT and NT/P, respectively, we obtain a convergence rate of O /./F///TT] for regularized participation with this "wait-for-all" method.
that each client n computes gn (x)) at least M > 1 times that are
special case of
In theory, when considering regularized participation and M is large enough, the convergence rate of this "wait-for-all" method can potentially match with that of the original configuration of Algorithm [] In this way, the convergence error upper bound of both methods can match the lower bound of SGD convergence error (sec discussion above). However, in practice, reducing the stochastic gradient noise as in this "wait-for-all method may only give limited improvement. One reason is that practical settings have finite number of training data samples, so the noise can only be reduced by a certain degree. In addition, having some noise in SGD can prevent the model parameter from being trapped in saddle points and local minima in practice. The empirical results in Section 6 show that Algorithm T
Note that M defines the convergence error as [xx))) whereas we define it as [[,]( Hence, the order of our is different from that in (
8

---

with amplification performs better than waiting for all the clients. We also note that our results for stochastic participation (Corollary (48) does not require all the clients to participate within P rounds.
Achieving Regularized Participation in Practice. In theory, regularized participation requires that p -1== - qi" is equal to each other for all the clients n E .l....... N for a properly chosen P. When all the clients are connected to the system and client sampling is performed to limit the compu- tation and communication overhead, this condition holds when the clients are selected according to permutation, i.e., all the clients participate once before the same client can be selected again. In the case where clients get disconnected from time to time, the system can try to properly schedule the participation of connected clients and their weights {q²) ). so that within a cycle of P rounds, all the clients participate with equal averaged weights. In practice, it can be sufficient if this regularized condition is only approximately satisfied, especially when multiple clients have similar datasets so that (P) is small although not necessarily zero. The empirical results in Section 6 show that Algorithm T with amplification can give good performance even if P is less than the participation cycle of all clients. This suggests that, as long as the subset of clients that participate in P rounds are more representative of the overall data distribution than the (usually much smaller) subset of clients that participate in single round, amplifying the updates every P rounds can be useful.
1
Experiments
We ran experiments of training convolutional neural networks (CNNs) with FashionMNIST [34] and CIFAR-IO [9] datasets, each of which has images in 10 different classes. We set the total number of clients to N 250. Similar to existing works 6 7 36,, we partition the data into clients so that each client has data of one majority class label, with 5% of data of other (minority) labels, to simulate a setup with non-IlD data distribution which is often encountered in FL scenarios. We assume that the clients' availability exhibits a periodic pattern inspired by 6 Namely, in the first 100 rounds, only clients with the first two majority labels are available; in the next 100 rounds, only clients with the next two majority labels are available, and so on. In each round, S 10 clients participate in a regularized manner, out of all the currently available clients. To speed up initial rounds of training, similar to practical deep learning implementations, we start with standard FedAvg with a relatively large initial learning rate. The initial rates are 0.1 and 7 0.05 without amplification (i.e., 7 = 1) for FashionMNIST and CIFAR-10, respectively, which were obtained using grid search in a separate scenario of always participation. After an initial training of 2, 000 rounds for FaShionMNIST and 4, 000 rounds for CIFAR-10, we study the performance of different approaches with their own learning rates. Additional setup details and results are given in Appendix D.
Comparing Different Methods. We show the results of Algorithm T both with and without amplification. When using amplification, we set 1) = 10 and P 500. We also compare to an algorithm that waits for all the clients, related to our discussion in Section for two settings where each client computes its gradients either minibatch or the entire dataset, which we refer to as separately found on grid that is {1, 0.1, 0.01, 0.001, 0.0001) times the initial learning rate, with the periodic participation pattern described above. The results are shown in Figure
" and "wait-full", respectively. The best learning rate y of each approach was
We make few key observations as follows. First, we clearly see that Algorithm 7 with amplification gives the best performance. By choosing 500, we match with the participation period of clients, as described in the setup above. This corresponds to our setting with regularized participation. In
weil-minibetch
wait-full
Alg. 1 without amplificatonn
Alp. 1 with amplification
FashionMNIST
FashionMNIST
x10
CIFAR-10
CIFAR-10
1.1
0.90
Aig. with empilcation
3.0
0.76
Ap with arrofiication
Glotal training
1.0
accuracy
0.89
Global training
2.5
lest accuracy
0.74
0.9
0.88
0.72
0.8
4/. with ticaton
0.87
with carpi cation
0.85
0.60
150000
300000
0
150000
300000
300000
600000
300000
600000
Taining rounds
Training
Training
Triinin
Figure 1: Results for different approaches with periodically connected clients (P = 500).

---

P-1
P-100
P- 300
P- 500
P- 700
P- 900
FashionMNIST
FashienMNIST
CIFAR-10
CIFAR-10
0.51
0.00350
0.76
0.0014
Gubbal tranit Issa
0.50
Ioce
6.00325
0.74
0.0012
0.00100
Tel aUTHFAry
0.72
0.00275
0.00
0.70
0.0008
0.00250
0.67
0.00225
0.68
0.0006
0.00200
0.66
100000
200000
300000
100000
200080
200000
100000
200000
500000
0
100000
200000
300000
Trining rounds
Traning rounds
Traniing rounds
Trining rounds
Figure 2: Algorithm with amplification and different P. with periodically connected clients.
this case, Algorithm D with amplification allows different groups of clients make small progress among themselves first. After P rounds, each client has made its own share of contribution, and the updates get amplified so that the model parameter progresses faster towards the direction that is overall beneficial for all the clients. As our theory predicts, this approach gives desirable convergence rate, which is now verified by experiments. Next, we observe that the "wail-minibatch and "wait-full" methods perform worse than Algorithm with with amplification. We also observe that
"wait-full", which computes the gradient on the entire dataset, does not provide substantial gain compared to await-minibatchi in the experiments. These observations align with discussion in Section on the practical performance of different methods. Finally, we observe that standard FedAvg (i.e., Algorithm 7 without amplification) gives the lowest performance. This is because without amplification, the algorithm cannot put more emphasis on the collective updates by the cohort of all clients, and the parameter updates may diverge from the overall optimal direction.
Different Values P. Next, we fix v = 10 in Algorithm and study the effect choosing different values of P. We use the same learning rate that is obtained from grid search in the previous experiment. Note that the clients' availability pattern remains the same as described above. The choice of different P simulates the practical scenario where the estimation of P may not perfectly align with the actual participation cycle. The results are shown in Figure
We observe that P = 1, which corresponds to the "classical" setting of FedAvg with two-sided does not give the best performance. Interestingly, compared P 500, we see that P = 100 and P = 300 give a similar performance, and even slightly better performance in the case of CIFAR-10 data. Due to the random offset applied the first participation cycle in each experiment (see Appendix D.1 for details), every interval of 100 rounds can include the "partial" contributions by two subsets of clients (with data in 4, out of 10, majority classes). The results suggest that amplifying such partial contributions by multiple subsets of clients can still improve performance. the case of CIFAR- data, the reason for 500 being slightly worse may be that the accumulated update within P rounds generally becomes larger as P gets larger, in which amplification causes a bigger change in the model parameter. Depending on the landscape of the loss function, this change may be too big so that the model performance decreases. For similar reason, the performances of P = 700 and P = 900 are even worse. Nevertheless, we expect that choosing a smaller learning rate y can improve the performance for large P values.
learning rates 8
7 Conclusion
In this paper, we have studied FL with arbitrary client participation. For a generalized FedAvg algorithm that amplifies parameter updates every P rounds, we have developed a unified framework for convergence analysis and obtained convergence rates for variety of client participation patterns. Our findings suggest that regularized participation with finite P gives the best performance and matches the lower bound of SGD convergence eтror when T is sufficiently large. For stochastic participation, first, we have formally proven that convergence is guaranteed when the participation process is ergodic. Then, for two generic classes of participation processes, have proven that with a properly chosen P, our convergence rate matches state-of-the-ae FedAvg convergence rates that were derived for the idealized case of independent and unbiased participation. The empirical results have confirmed that amplification is useful and also provided further insights. Future directions include analysis of advanced FL algorithms and more detailed empirical study.
10

---

References
[1] Y. Arjevani. Y. Carmon, C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming. 2022.
[2] P. Billingsley. Probability and measure. John Wiley & Sons, 1995.
[3] K. Bonawitz, H. Eichner, W. Grieskamp, D. Huba, A. Ingerman, V. Ivanov, C. Kiddon, J. Konečný, S. Mazzocchi, B. McMahan, T. Van Overveldt, D. Petrou, D. Ramage, and J. Rose- lander. Towards federated learning at scale: System design. In Proceedings of Machine Learning and Systems, volume 1, pages 374-388, 2019.
[4] W. Chen, S. Horvath, and P. Richtarik. Optimal client sampling for federated learning, arXiv preprint arXiv:2010. 13723, 2020.
[5] Y. J. Cho, J. Wang, and G. Joshi. Towards understanding biased client selection in federated learning. In International Conference on Artificial Intelligence and Statistics, pages 10351- 10375. PMLR, 2022.
[6] Y. Ding, C. Niu, Y. Yan, Z. Zheng, F. Wu, G. Chen, S. Tang, and R. Jia. Distributed optimization over block-cyclic data, arXiv preprint arXiv:2002.07454 2020.
[7] H. Eichner, T. Koren, B. McMahan, N. Srebro, and K. Talwar. Semi-cyclic stochastic gradient descent. In International Conference on Machine Learning, pages 1764-1773. PMLR, 2019.
[8] Y. Fraboni, R. Vidal, L. Kameni, and M. Lorenzi. Clustered sampling: Low-variance and improved representativity for clients selection in federated learning. In International Conference on Machine Learning, volume 139, pages 3407-3416. PMLR, Jul. 2021.
[9] Y. Fraboni, R. Vidal, L. Kameni, and M. Lorenzi. On the impact of client sampling on federated learning convergence. arXiv preprint arXiv:2107112111 2021.
[10] E. Gorbunov, Hanzely, and P. Richtarik. Local SGD: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Stutistics, volume 130 of PMLR, pages 3556-3566 2021.
[11] R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and P. Richtárik. SGD: General analysis and improved rates. In International Conference on Machine Learning, pages 5200- 5209. PMLR, 2019.
[12] X. Gu, K. Huang. J. Zhang, and L. Huang. Fast federated learning in the presence of arbitrary device unavailability. In Advances in Neural Information Processing Systems, 2021.
[13] M. Gürbüzzalaban, A. Ozdaglar, and P. A. Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, 186(1))49-84, 2021.
[14] Haddadpour, M. M. Kamani, M. Mahdavi, and V. Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, 2019.
[15] K. He, X. Zhang, S. Ren, and J. Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In IEEE International Conference on Computer Vision, pages 1026-1034, 2015.
[16] W. Hoeffding. Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffding, pages 409-426. Springer, 1994.
[17] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, 7. Charles, G. Cormode, R. Cummings, et al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2)11-100, 2021.
[18] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.

---

[19] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[20] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-66) 60,0060020000 2020.
[21] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450, 2020.
[22] X. Li, K. Huang, W. Yang, S. Wang, and 7. Zhang. On the convergence of fedavg non-iid data. In International Conference on Learning Representations, 2020.
[23] T. Lin, S. U. Stich, K. K. Patel, and M. Jaggi. Don't use large mini-batcher use local SGD, In International Conference on Learning Representations, 2020.
[24] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication--ffiiini learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[25] K. Mishchenko, A. Khaled Ragab Bayoumi, and P. Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33, 2020.
[26] J. Reddi, Z. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Konečný, S. Kumar, and H. B. McMa- han. Adaptive federated optimization. In International Conference on Learning Representations, 2021.
[27] Y. Ruan, X. Zhang, S.-C. Liang, and C. Joe-Wong Towards flexible device participation in federated learning. In International Conference on Artificial Intelligence and Statistics, pages 3403-3411. PMLR, 2021.
[28] S. U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.
[29] J. Wang and G. Joshi. Adaptive communication strategies to achieve the best error-runtime trade-off in local-update SGD. In Proceedings of Machine Learning and Systems, volume 1, pages 212-229, 2019.
[30] J. Wang and G. Joshi. Cooperative SGD: A unified framework for the design and analysis of local-update SGD algorithms. Journal of Machine Learning Research, 22(213):1-50, 2021.
[31] J. Wang, V. Tantia, N. Ballas, and M. Rabbat. Lookahead converges to stationary points of smooth non-convex functions. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8604-8608, 2020.
[32] B. Woodworth, K. K. Patel, S. Stich, Z. Dai, B. Bullins, B. Memahan, O. Shamir, and N. Srebro. local SGD better than minibatch SGD? In International Conference on Muchine Learning, pages 10334-10343, PMLR, 2020.
[33] B. E. Woodworth, K. K. Patel, and N. Srebro. Minibatch local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 16222, 2020.
[34] H. Xiao, K. Rasul, and R. Vollgraf. Fashion novel image dataset for benchmarking machine learning algorithms. arXiv preprint 17877:1708.07747, 2017.
[35] Y. Yan, C. Niu, Y. Ding, Z. Zheng, Wu, G. Chen, S. Tang, and Z. Wu. Distributed non- convex optimization with sublinear speedup under intermittent client availability. arXiv preprint arXiv:2002.07399, 2020.
[36] H. Yang, M. Fang, and J. Liu. Achieving linear speedup with partial worker participation in IID federated learning. In International Conference on Learning Representations, 2021.
[37] H. Yang, X. Zhang, P. Khanduri, and J. Liu. Anarchic federated learning. In International Conference Machine Learning, pages 25331-25363 PMLR, 2022.
12

---

[38] Q. Yang, Y. Liu, T. Chen, and Y. Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):12, 2019.
[39] H. Yu, R. Jin, and S. Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In International Conference Machine Learning, volume 97 of PMLR, pages 7184-7193, 2019.
[40] H. Yu, S. Yang, and S. Zhu. Parallel restarted SGD with faster convergence and less communi- cation: Demystifying why model averaging works for deep learning. In AAAI Conference Artificial Intelligence, pages 5693-5700, 2019.
[41] C. Yun, S. Rajput, and S. Sra. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In International Conference on Learning Representations, 2022.
[42] M. Zhang, J. Lucas, J. Ba, and G. Hinton. Lookahead optimizer: k steps forward, step back. Advances in Neural Information Processing Systems, 32, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] Limitations are described where
necessary. More discussions are also available in the appendix.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is foundational work that is widely applicable to various domains. The societal impact would depend the specific application, which we believe is beyond the scope of this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Included in the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yss] Please visit
https://shi /aiiiig///iiingg...../g. wang/ wang/ code/fl arbitrary www.ppaatttttiio. prbbtraryyyprrtttpppptiiii
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] More details are included in the appendix.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] The shaded areas in the figures represent the standard deviation. More details are explained the appendix.
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Included in the appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] Mentioned in the appendix.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "n8nTa8hYMoO", "reviewer": "Reviewer_m3NC", "summary": "The paper considers federated learning with arbitrary patterns of client participation and provides a novel analysis. Several participation patterns have been studied and analyzed.", "questions": "1. In all the results, it is assumed that $P \\leq T/2$. And for the $\\delta^2$ term to be zero, the average participation weights need to be equal over any $P$ interval. Will these results be able to accommodate the case when $N$ is huge, such that a client will likely only participate once?\n2. With $\\sigma = $ in Corollary 4.3, the bound reduces to $O(1/T)$, which is what one gets with gradient descent. However, the bound in Corollary 4.7 does not reduce to $O(1/T)$ in this special case. Can the authors comment on this difference, and is there a way to address apparent sub-optimality?\n3. I'm not sure if I follow the reasoning in the remark following Corollary 4.8, explaining how $I$ need not be small. Can you elaborate?", "limitations": "The main limitation of the paper for me is the large $N$ case, where Proposition 4.2 may be difficult to satisfy. To get a decent convergence rate, $P$ will have to be smaller than $\\sqrt T$ (see Corollary 3.2, 3.3). However, for large $N$, each client may not even be sampled in each $P$ length interval.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is largely well-written and provides adequate intuition and explanation for the math introduced.\n2. The paper makes a relevant and significant contribution, addressing the problem of arbitrary client participation.\n\nWeaknesses:\n1. Although the authors have made a good effort toward explaining all the math, in quite a few places I found myself scrolling back and forth to remind myself of the terms being discussed. I understand that the authors were working under a hard page limit. Therefore, if accepted, I would suggest the authors expand the description, especially in Sections 4.2 and 5. It might even help to remind the authors what some terms mean, even if they are defined earlier.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "is9lqsc9Hx4", "reviewer": "Reviewer_aHyK", "summary": "This paper mainly provides a general convergence analysis of federated learning when there is arbitrary client participation and proposes an amplification method to update gradients in federated learning under the arbitrary participation of clients. More specifically, there are four main client participation patterns that the authors consider in their analysis: regularized, ergodic participation, mixing, and independent. The paper shows that under these participation patterns, their proposed application method for federated learning can achieve convergence to zero, and also some patterns can match the linear speed-up in the convergence rate (shown in prev. works) with the increase in the number of participating clients. The experiments on FMNIST and CIFAR-10 are presented to show validation of the speed-up that the proposed method can achieve.", "questions": "I have questions related to the three weaknesses mentioned in the section above. In short the following three questions:\n- What is the intuition for the amplification method in algorithm 1?\n- How does the hyperparameter $\\eta$ effect the algorithm performance? How sensitive is the algorithm to this parameter? Is there an ablation study that can show this?\n- What are some realistic scenarios that represent the four main different client participation patterns?", "limitations": "The authors have clearly stated the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:\nIn general, the paper is well written and provides meaningful insight into federated learning with a unified convergence analysis for arbitrary client participation. Specifically, these are the main strength of the paper:  \n- The paper theoretically and empirically addresses an important problem of federated learning which is arbitrary client participation. While many work in federated learning considers a fixed client participation pattern, in real implementations of cross-device federated learning, clients can leave or join arbitrarily depending on their circumstances. There are not much work that has a unified analysis of different patterns (including stochastic) of client participation, and this paper contributes to the federated learning community largely by presenting such analysis. \n- The paper compares its analysis with relevant other work including [11], [27] referenced in the paper as well as the other work which shows linear speedup in convergence with partial client participation in federated learning [31]. It is interesting to see in what scenarios for arbitrary client participation we can achieve a similar linear speedup which the paper thoroughly provides insights on. \n- Although the contribution of this paper is more on the theoretical side, it proposes an interesting amplification method (line 11-14 in Algo. 1) which does not really need additional computation/communication at the client side, and only requires additional memory saving at the server side (which in general is a plus for federated learning). This method also achieves 0 convergence error in some client participation patterns which is interesting and validated in the experiments.\n\n\n*Weaknesses:  In general, the paper has several weaknesses but they do not surpass the strength of the paper in my opinion. Here are some of the weaknesses:\n- The intuition behind the amplification method in Algorithm 1 is unclear. Although it is a strength that using this method can assist in achieving 0 convergence error in the analysis, the insight/reason for this is unclear. The paper also lacks a bit in explaining the main intuition behind algorithm 1.\n- In addition to the point above, the $\\eta$ seems like a very important hyperparameter that can largely affect the performance/convergence of the algorithm. However, the clear effect of these hyperparameters has not been viewed much either theoretically or empirically throughout the paper. Perhaps having some ablation study on the $\\eta$ can help further understand the implications/effectiveness of the proposed algorithm 1.\n- The four main different client participation patterns that the paper considers are quite general, partly I assume is because they are defined to be applied to the theoretical analysis. It would be more interesting if the authors gave some connection with the arbitrary client participation patterns that exist in the real-world federated learning applications such as periodic shifts [6-7] (as cited in the paper). \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0wugga5zRYK", "reviewer": "Reviewer_Th7z", "summary": "This paper studies the partial participation aspect in local SGD method. In previous works uniform sampling of clients is usually assumed, which is not close to real situation in practice. In this work authors introduce a new general framework for analyzing and understanding different strategies of partial participation. \n\nThe framework allows to decouple terms such that it is possible to analyze effect of partial participation separately. Authors firstly provide general results and then analyze some special cases and reflect results. \n\nIn the end of the paper a wide range of experimental results was provided.", "questions": "Can you please explain if it is possible to do such analysis for local methods which can tackle heterogeneity? (https://arxiv.org/pdf/1910.06378.pdf, https://arxiv.org/abs/2202.09357)\n\nIs it possible to extend the analysis for the case when bounded heterogeneity is not used?", "limitations": "There are two main limitations: \n\n1) No analysis for convex objectives \n\n2) Bounded heterogeneity assumption\n\n3) No analysis for local methods that can tackle client drift (heterogeneity): SCAFFOLD, ProxSkip, FedLin.\n\nOverall, contribution is quite good and despite all limitations I lean towards to accept. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe provided framework is general and it covers many practical examples. The paper is well-written in general, all assumptions and definitions are clearly stated. All formulations of theorems are clear.\n\nTheoretical analysis seems to be correct. I checked the appendix and I did not find mistakes, but I might miss something.\n\nObtained results are interesting and they lead to new prospectives and insights. \n\nThe experimental comparison is meaningful and illustrative.\n\nWeaknesses:\n\nThe analysis relies on Bounded gradient divergence assumption. It means that level heterogeneity is limited. This assumption contradicts to experimental design, where they \"partition the data into clients so that each client has data of one majority class label.\" It would be interesting to see analysis without bounded heterogeneity. \n\nThe analysis is done only for non-convex objectives. It would be interesting to see analysis for strongly convex and general convex objectives. Also it is interesting to study PL condition. \n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept