Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis
Authors: Michael Crawshaw
Mingrui Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: federated learning
nonconvex optimization
cross device
heterogeneous data
periodic participation
Primary area: optimization
TL;DR: We propose a new optimization algorithm for federated learning with periodic client participation, and prove that the convergence rate is independent of client heterogeneity and enjoys linear speedup and reduced communication.

Abstract: In federated learning, it is common to assume that clients are always available to participate in training, which may not be feasible with user devices in practice. Recent works analyze federated learning under more realistic participation patterns, such as cyclic client availability or arbitrary participation. However, all such works either require strong assumptions (e.g., all clients participate almost surely within a bounded window), do not achieve linear speedup and reduced communication rounds, or are not applicable in the general non-convex setting. In this work, we focus on nonconvex optimization and consider participation patterns in which the chance of participation over a fixed window of rounds is equal among all clients, which includes cyclic client availability as a special case. Under this setting, we propose a new algorithm, named Amplified SCAFFOLD, and prove that it achieves linear speedup, reduced communication, and resilience to data heterogeneity simultaneously. In particular, for cyclic participation, our algorithm is proved to enjoy $\mathcal{O}(\epsilon^{-2})$ communication rounds to find an $\epsilon$-stationary point in the non-convex stochastic setting. In contrast, the prior work under the same setting requires $\mathcal{O}(\kappa^2 \epsilon^{-4})$ communication rounds, where $\kappa$ denotes the data heterogeneity. Therefore, our algorithm significantly reduces communication rounds due to better dependency in terms of $\epsilon$ and $\kappa$. Our analysis relies on a fine-grained treatment of the nested dependence between client participation and errors in the control variates, which results in tighter guarantees than previous work. We also provide experimental results with (1) synthetic data and (2) real-world data with a large number of clients $(N = 250)$, demonstrating the effectiveness of our algorithm under periodic client participation.

Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-ffficeeen Algorithm and Analysis
Michael Crawshaw
Mingrui Liu
Department of Computer Science George Mason University Fairfax, VA 22030 mcrawsha@gmu, edu edu
Department of Computer Science George Mason University Fairfax, VA 22030 mingruil@gmu edu
Abstract
In federated learning, it is common to assume that clients always available participate in training, which may not be feasible with user devices in practice. Recent works analyze federated learning under more realistic participation patterns, such as cyclic client availability or arbitrary participation. However, all such works either require strong assumptions (e.g., all clients participate almost surely within a bounded window), do not achieve linear speedup and reduced communication rounds, or are not applicable the general non-convex setting. In this work, we focus on nonconvex optimization and consider participation patterns in which the chance of participation over fixed window of rounds is equal among all clients, which includes cyclic client availability a special case. Under this setting, we propose a new algorithm, named Amplified SCAFFOLD, and prove that it achieves linear speedup, reduced communication. and resilience to data particular, for cyclic participation, our algorithm
heterogeneity simultaneously. is proved to enjoy (e) communication rounds to find an e-stationary point in the non-convex stochastic setting. contrast, the prior work under the same setting requires Oxx 4) communication rounds, where к denotes the data heterogeneity. Therefore, our algorithm significantly reduces communication rounds due to better dependency in terms of and к. Our analysis relies fine- fine-grained treatment the nested dependence between client participation and errors in the control variates, which results in tighter guarantees than previous work. We also provide experimental results with (1) synthetic data and (2) real-world data with a large number of clients (N 250), demonstrating the effectiveness of our algorithm under periodic client participation.
Introduction
is a distributed learning paradigm that emphasizes client privacy 22 29]. limited communication [9 25), and data heterogeneity across clients [17 55). FL has attracted attention in recent years due to the ability to leverage data and compute from user devices while respecting privacy [4 [. For large-scale FL., it is common limit the number of simultaneously participating devices, and many works do so by assuming that a random subset of clients be sampled independently each round [27] 50 22 38). However, this pattern of client participation is not always practical. If clients are user devices like mobile phones, they may not have 24/7 availability due to low battery or bad internet connection [15 31] In particular, if client availability is correlated with geographical location (c.g. mobile phones charging at night), then
Federated learning (FL) 27 21 16, 53
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table I: Communication and computation complexity of various methods to find an e-stationary point for L-smohhh, non-convex objectives. N: number of clients, R: data heterogeneity sup,, ff(()) ff())] I S: number of participating clients per round, K: number of groups for cyclic participation. See Section 3.2 for a description of each participation pattern. We say that an algorithm exhibits reduced communication if its dependence in terms of is strictly smaller than ((e Derivation of complexities for Amplified FedAvg can be found in Appendix C
Communication Complexity (R)
Iteration Complexity (RI)
Reduced Communication
Unaffected by Heterogencity
Setting
L.d. Participation (5)
FedAvg [i7
Ax
Ses
(1
vTx
Sct Ale²
L
X
SCAFFOLD
A4
Amplified FedAvg 39
ALNo 84
ALts?
ALe"
X
X
Amplified SCAFFOLD (ours)
AA.
Regularized Participation (P, ,)
Amplified FedAvg (9
ALP44
A
v
X
Amplified SCAFTOLD (ours)
ALP
Cyclic Participation (A. S)
Amplified FedAvg 39
ALNo² Se
SK
ALKI
Ale?
x
x
N
Set
Amplified SCAFFOLD (ours)
ALK
ALe²
Sx
client availability follows a cyclic pattern [54] Therefore, it remains an important open question to design federated optimization algorithms with provable efficiency under non-i.i.d client participation.
Several works have investigated optimization in FL under non-i.i.d. client participation [46] However, to the best of our knowledge, no existing algorithm in a non-i.i.d. participation setting provably exhibits reduced communication cost, linear speedup with respect to the number of clients, and resilience to client data heterogeneity for general non-convex optimization.
10 2 39
In this work, we consider FL under an arbitrary participation framework [39], where client partici- pation during each round is a random variable with potentially unknown distribution. We focus on client participation patterns that periodic, in the sense that all clients expected to participate with equal frequency over a window of multiple training rounds.
For this setting, we propose Amplified SCAFFOLD, an optimization algorithm for FL under periodic client participation. Amplified SCAFFOLD utilizes (a) amplified updates across participation periods and (b) control variates computed across entire participation periods, to eliminate the effect of data heterogeneity even under non-i.i.d. participation. We show that Amplified SCAFFOLD exhibits significantly reduced communication cost, linear speedup, and is unaffected by client data hetero- geneity. To the best of our knowledge, this is the first result demonstrating reduced communication resilience to data heterogeneity without assuming i.i.d. participation. The complexity of Am- plified SCAFFOLD compared against baselines in Table T]. For cyclic participation, Amplified SCAFFOLD improves the previous best communication cost from O to O(c
The main challenges of achieving these properties are (1) simultaneously handling randomness from stochastic gradients and non-i.i.d. participation; and (2) controlling the error of control variates under non-i.i.d. participation. Previous work in this setting [39 performs an in-expectation analysis, by taking expectation only over randomness from stochastic gradients; this avoids (1) but cannot leverage properties of the participation pattern to reduce communication. We present a tighter analysis that addresses (1) by taking expectation over both client participation and the stochastic gradients throughout the analysis, and carefully treating the trajectory variables which depend on both sources of randomness. We address (2) by recursively bounding the control variate errors, which involves non-unifonn non-uniform average of non-uniform averages error terms resulting from non-i.i.d. participation. We show that this nested non-uniform average be bounded using mild regularity conditions on the participation pattern.
Our contributions are summarized below.

---

We introduce Amplified SCAFFOLD, an optimization algorithm for federated learning under non-i.idd. client participation. Our convergence analysis demonstrates its computational and communication efficiency: Amplified SCAFFOLD exhibits reduced communication, linear speedup, and unaffected by data heterogeneity. These guarantees are achieved with a tighter analysis than used in previous work (39), with fine-grained treatment of the two sources of randomness: client participation and stochastic gradients. In the case of cyclic participation, we reduce the previous best communication cost of O(w2e=A) to
Experimental results show that Amplified SCAFFOLD converges faster than baselines on both synthetic and real-world problems under realistic non-i.i.d. client participation patterns. We also include an ablation study which demonstrates the robustness of our algorithm to changes in data heterogeneity, the number of participating clients per round, and the number of client groups in cyclic participation.
The paper outlined as follows. We discuss related work in Section and 3 provides formal specification of the optimization problem. Amplified SCAFFOLD is introduced and theoretically analyzed in Section and we provide experiments in Section We conclude with Section 6
Related Work
Federated Optimization. FedAvg 27 characterizes partial client participation and local updates
in each round. FedAvg was analyzed in the full participation setting 35
37 50 51
43
42
18
12]
Other federated optimization algorithms aim improve communication efficiency
32
52
and
tackle data heterogeneity [22) [7]. The analysis of FL optimization algorithms typically either
assumes full client participation or partial client participation where clients are sampled uniformly
randomly 47 38
23
43 M. (30] provides lower bounds for distributed stochastic, smooth
optimization with intermittent communication and non-convex objectives, both in the full and partial participation settings. They also include algorithms employing variance reduction which match (or closely match) lower bounds in the full and partial participation settings. However, none of the works above are applicable for general participation patterns such as periodic participation.
Client Participation. Cyclic data sampling was considered for stochastic convex optimization in 10 where they propose "pluralistic" solutions instead of learning a single model for all clients. There
is recent line of work considering various participation patterns, including client selection 11 4
33 biased participation [34] 6, 77. independent participation across rounds [7 22 233, unbiased
participation [36] [3), bounded rounds of unavailability [46] [4 48), asynchronous participation [24
21. cyclic participation [8) and arbitrary participation (39 40 However, none of these works enjoy
linear speedup, reduced communication rounds, and resilience to data heterogeneity under the general setting of non-convex objectives and periodic client participation. Concurrent work [44] considers non-stationary client participation under the condition that for every client and every round. the probability of participation is bounded away from zero; for this setting, they propose an algorithm with linear speedup and dependence on gradient dissimilarity for non-convex, Lipschitz objectives.
See Appendix F for detailed discussion comparing our results with a small number of closely related
baselines.
3 Problem Setup
We consider a federated learning problem with N clients, with the overall objective
E ELO x
min #ERd
[(x)
where each fa Rdd RR is the local objective of one client. We consider the stochastic optimization problem, so that fa(x)= = EE-D, [æx:: E) and the optimization algorithm can access F, {) and V.((;; E) for individual values c. We make the following assumptions about the objectives:
Assumption 1. (a) f(xo) min f(x) < A. (b) Each fa is L-smooth, i.e., [[V](()) ff(()) < L||== vll for all x, E Rd. (c) The stochastic gradient has variance o², i.e.
Eg-D, (x; [ < d² for all x e gd.
3

---

Since each fi may be non-convex, we consider the problem of finding an e-stationary point of f. that is, a point æ E F such that [ S
3.1 Participation Framework
We consider a federated learning framework consisting of R rounds. For any round r E {O..... ., R-13 and client i E [N) the availability of client at round is random variable g.., following the arbitrary participation framework of [39]. If q² = O, then client may not participate during round i. For example, under the conventional i..dd sampling of clients, at each round a subset of clients S, [M]
is sampled uniformly without replacement, and the weights are set as q: [(ESS.)
For some P E N, let 2r, be the filtration generated by {q. ro S < ru P. E [N]], let Q be the filtration generated by Qo..... QR-P, and let G be the filtration generated by { : :0 S
R, 0 S < 1, [N]], where E is the random sampling of the stochastic gradient of round step k. client i. We make the following assumptions about the participation distribution.
1 and Ei-(g:)² I p². (b) The distribution of { is unbiased across clients over every window of P rounds, i.e. Eer, I Di - &f = 1/N for every m < R/P and E [N]. (c) Each client has a non- zero probability of being sampled over every window of P rounds, iee, Po.., ( Er=mp
Assumption 2. For all E {O....,R. R 1}: (a) E q²
((++))--
of
0) Psample for every m < R/P and E [N]. (d) Q and G are independent.
For each round, Assumption 2 enforces that the participation weights q.. are normalized to sum to I, and characterizes the spread of participation weights across clients with the constant p². Assumption b) requires that the set of rounds be partitioned into windows of length P within which clients are expected to participate with equal frequency. Lastly, Assumption ([c) enforces that within each window, for each client the probability of being sampled is nonzero. Conventional i.i.d client sampling satisfies Assumption with S S-1/2 P = 1, and Psample = SS/N.
An important difference from conventional i.i.d. participation is that here, client participation is not necessarily independent across rounds. Accordingly, we emphasize that the expectation and probability in Assumptions bb)(C) are taken only over 2ry. Therefore, the mean participation weight in Assumption may itself be random variable if client participation at some rounds is dependent on the outcome of participation in previous rounds. Similarly, the sampling probability in Assumption ((c) may be random variable. For the participation patterns considered in the next section, Assumption 2 is satisfied even when client sampling is not independent across rounds.
3.2 Specific Participation Patterns
Regularized Participation We say that client participation is regularized
33 if T. - almost
surely for all ro and i, where T. is defined on Line 18 of Algorithm as the participation of client i P 1. In this case, Assumption is satisfied with Psample 1, while P and '² are parameters of the participation pattern. Regularized participation is relatively strong constraint, since every client must participate within each window, which may not be practical. However, it is flexible in that there is constraint how clients participate within each window. Regularized participation was also considered for strongly convex objectives [26).
averaged over rounds ro. ro
Cyclic Participation Following the CyCP framework (8] N clients are partitioned into K equally sized subsets, and at round r only clients in group (r mod K) may participate. S clients are sampled without replacement from group (r mod K). for whom the participation weight is qf 1/S. All other clients are assigned of = O. Cyclic participation satisfies Assumption 2 with P P= K, p 1-2 and psample = SK /N. Notice that i.i.d. client sampling is the special case where K = 1.
Cyclic participation can model situation where each client group is available at different time of day. For example, if client devices are mobile phones, then clients are available for participation at night, when phones are charging, likely to have internet connection, and otherwise idle. If devices are spread across the globe, then client groups are naturally formed by time zones. Cyclic participation is less stringent than regularized participation since not all clients are required to participate within each window. FedAvg was analyzed under cyclic participation for PI. objectives [8] although this analysis is not applicable in our setting, which uses general non-convex objectives.

---

Algorithm 1 Amplified SCAFFOLD
1: Initialize Do. Go Go
N Zi=1 Go 0
2: for r R, do
3: for i [ do
4:
F²,0 t- Er 5: for k = 0....,
client
do
6:
Sample Kr, Di
7:
Pi,k f VFi Ri Sr,kk
8:
x x++ t o (
G + Gro)
9:
end for
10:
A t- x.,11 It
11:
end for
12:
Ir+1 t- 3r + Σ N
i=1 A
server
13:
ut + E 9,4,
ifr ro
then
15:
Pro+P f- Zro + +
for E [N] do
Tro t 3 Ls=ro - Ts
9¹ t TP Ertt P-1
18:
kk= 90
G o t (ro +0gg + 1% 0] G
20:
end for
Gro+P f- 1 Eim1 Gi To+P
22:
TO + +P
23:
0
24:
end if
25:
end for
4 Algorithm and Analysis
In this section, we present Amplified SCAFFOLD, algorithm to solve the FL problem described in Section Pseudocode for Amplified SCAFFOLD is shown in Algorithm 1. The main components of the Amplified SCAFFOLD algorithm are (1) amplified updates and (2) long-range control variates.
4.1 Algorithm Overview
To deal with the non-stationarity of client availability, Amplified SCAFFOLD performs amplified updates based on information accumulated over a window of P rounds. In Algorithm the variable u holds a weighted average local updates to client models, weighted by client participation. Every P rounds, the global model is updated in the direction scaled by the amplification factor y Informally, the direction u includes information from all clients with equal representation, according to Assumption b)). Similar amplified updates are used in Amplified FedAvg (39.
Control variates for heterogeneous federated learning were first introduced by SCAFFOLD [7 However, SCAFFOLD-style control variates are updated every time client participates, which may not be appropriate under periodic availability. For example, under non-i.i.d. participation control variates for different clients would be updated with different frequencies, so that some clients may have consistently less accurate control variates than others. Informally, this may lead to a bias in which some clients' objective is underweighted relative others. To deal with this issue, Amplified SCAFFOLD updates control variates based on information accumulated over a window of rounds, which enforces equal representation of all clients in expectation, according to Assumption (
Comparison with [17 39 A Although the two algorithmic components of Amplified SCAFFOLD individually appear in previous work 17 39 we emphasize that our complexity results cannot be achieved by simply combining the analyses of these two works. The analysis of (39) requires -1 communication cost due to their treatment of the randomness in client participation. Here, present
5

---

tighter analysis with é cost from more fine-grained treatment of the two sources of randomness (stochastic gradients and client sampling). See Section 4.4 for more details on our approach.
4.2 Main Results
Let P. where m sampled uniformly from {0..... 11, and re E {0, P...., R/P). Denote w/o N Σソ= I( E 2.9) and 1// = Tr N- Informally, w4, represents
the "non-uniformity" of the client sampling distribution. We also consider variable A₁, that depends only on the client sampling distribution and characterizes the sample size from which G is computed. See Appendix [A.1 for further discussion of these quantities. We consider convergence under the following conditions, which are satisfied by several participation patterns of interest.
p2
Elw
E
for all and N
(
A
S p²
for all ro and
(2)
Theorem 1. Suppose that Assumptions andd hold, and that Equation 7 land Equation hold. If y S
Paseis 60LTP and 1 S GOLIP then Algorithm I satisfies
A MIR
( d2)
Corollary 1. For any c > andd1 I 1, there exist choices of and such that ([] 0(2))
as long as R 2 ALo
ALP
Ie
Posepte??
The complexity of Amplified SCAFFOLDD has several important properties:
Reduced Communication By choosing I - ((pp'o' Psample 22), Amplified SCAFFOLD has communication complexity R OLLPPsappee ?), which improves upon the e- complexity of parallel SGD. We are not aware of any existing work that achieves this communication reduction for non-convex federated optimization with periodic participation.
Unaffected by Heterogeneity The iterations RI and the number of communications R are unaffected by heterogeneity, which is not achieved for periodic participation by any existing work (3,88)
Linear Speedup The number of iterations RI O(ALp'o² will exhibit linear speedup in the number of clients through the term p², depending on the client participation pattern.
4.3 Application to Participation Patterns
The results from Section apply under any participation pattern that satisfies Assumption 2 Equation [ and Equation and below we discuss the participation patterns discussed in Section 3.2 The complexity of Amplified SCAFFOLD for each participation pattern are shown in Table and these results can be obtained by plugging p², P. and Psample into Corollary together with choice The derivations of each result below are given in Appendix B
of / as described in Section 4.2
Regularized Participation Recall that regularized participation satisfies Assumption 2 with Psample and p² are parameters of the participation pattern. Also, under regularized participation. T. = 1/NN almost surely, so that E[ww,, 1/N < P2/N /N and v = 0. Therefore Equation uin Equation are satisfied. Plugging Psample into Corollary [ yields
R (T.P RI O (AT
In this setting, our algorithm exhibits reduced communication and resilience to heterogeneity. To our knowledge, the only existing algorithm with theoretical guarantees for non-convex problems under regularized participation Amplified FedAvg [39]. However, as seen in Table the communication complexity of Amplified FedAvg has order in terms of and suffers from x dependence.

---

Cyclic Participation Recall that cyclic participation satisfies Assumption 2 with P K, S S-1/2
and Psample S/N. Also, Elwi = S/N2 < P2 /N and B( ) = p². so that Equation | and
Equation are satisfied. Based on the above parameter values, the resulting complexities are
LK 2
N RI =I=
(ALL
AALo Sea
R
Again, Amplified SCAFFOLD achieves reduced communication, linear speedup, and resilience to heterogeneity. Amplified FedAvg [39 is the only existing algorithm with theoretical guarantees in this setting. but fails achieve resilience to heterogeneity or reduce communication cost outside of the trivial case of full participation (K = S, N). Also, even for the setting of PL-functions, the convergence rate of FedAvg under cyclic participation from g does not demonstrate an improvement with respect to the number of local steps. See Appendix F for further discussion of their results.
Recall that i.i.d. participation is a special case of cyclic participation with K 1. In this case, Am- plified FedAvg fails to recover the reduced communication usually achieved under i.i.d. participation, such by SCAFFOLD [17]. In fact, Amplified FedAvg fails recover the communication cost of FedAvg under i.idd participation, requiring an additional factor of LN. The larger communication cost of Amplified FedAvg is result of its convergence analysis, which does not leverage the property of unbiased participation (Assumption 2(b) during the analysis, and requires P O in order to converge (see Appendix [ for more details). In contrast, Amplified SCAFFOLD succeeds in recovering the results of SCAFFOLD under i.i.d. participation, with only slightly worse dependence of on N/S. This difference in the order of is due to a potential small issue in the analysis of N We SCAFFOLD, which we intentionally avoided by accepting slightly worse dependence on 3 provide detailed discussion of the N/S dependence in Appendix
4.4 Proof Sketch
The main challenges for demonstrating convergence are (1) simultancously handling randomness
from stochastic gradients and non-i.i.d. client sampling, and (2) controlling error of control variates under non-i.i.d. client sampling. Previous work [39] subverts (1) by conditioning on Q throughout the entire analysis. However, this eliminates the possibility of utilizing the condition ElT., = 1/N,
and ultimately incurs dependence the data heterogeneity (see the term (2() in Theorem 3.1 of 39). Instead, we take expectation over both sources of randomness throughout the analysis, which requires careful treatment of each iterate's dependence, and enables communication reduction. For (2), previous analysis of federated algorithms with control variates [17] recursively bounds the error of control variates between consecutive rounds. However, this recursion crucially depends on ii.d. client participation. We extend this analysis to our setting, establishing a recursion over the control variate error between consecutive windows of P rounds. Esstblishhig this recursion under non-i.i.d. participation involves con-uniform average of non-uniform averages of error terms, which we handle by invoking the regularity conditions stated in Equation and Equation?? 2
Using smoothness of f. the objective function decrease f(āro+P) fft,)) is upper bounded by ( -r 2..)) + 2 | Tr. 2 Letting ã = Σ o be a weighted average of local models, the sum of the previous inner product and quadratic terms can be bounded by -mmIP]IV plus standard noise terms, the additional "drift" terms
N D
Σ df | - -r. 1=1
Mr = [T Tr,
and control variate errors C% ( - 12. Dr, captures the distance between local client models, while Mr captures the distance from local models to the previous global model Br.-
Taking conditional expectation Dr,, E and Mr, ELM, Q]. Lemma bounds the drift terms by establishing and unrolling a mutually recurrent relation between D,, and My The resulting bound involves non- non-uniform average over the control variate errors: Σn1 B 1Q].
7

---

Denoting the average control variate error Cr, = Ei= Cr. we want to bound E| pl in terms of E[Cro]- Cro+P can be decomposed into drift terms, but the result is non-uniform average:
To+P-11 1-11
Σ (DsD, + Ms,a)-
K=
Since the bound for each M.,, + Da,e from Lemma I involves non-uniform average over C the resulting bound of Cr.+P involves non-uniform average of non-uniform averages of Cr instead of the uniform average Cra The regularity conditions in Equation and Equation aaaationnalllww allow us to bound this nested non-uniform average by uniform average, which finishes the recursion.
Putting everything together, we obtain the descent inequality
B[ffo+rl - Eifral PI [ f
mII((mLpp + +n
where fn.:= (ār + P) + (ro + P) and & is a potential function that depends on the control variate errors. Theorem iis then obtained by averaging over ro and isolating the gradient.
5 Experiments
We experimentally validate our algorithm for non-i.i.d client participation under three settings: minimizing synthetic function, logistic regression for Fashion-MNIST 45). and training a CNN for CIFAR-10 (20). We also include an ablation study on Fashion-MNIST, to investigate how each algorithm is affected by changes in data heterogeneity, the number of participating clients, and the number client groups in cyclic participation.
5.1 Setup
All of our experiments utilize non-iidd. client participation pattern similar to cyclic participation (discussed in Section 3.2). We partition the total set of N clients into K equally sized subsets, and each training round only a single client group is available for participation. In our experiments, the available group does not change every round; instead, each group is available for y rounds at a time. Under this pattern, Assumption is satisfied with = gg. We refer to y as the availability time.
We evaluate five algorithms: FedAvg (27,. FedProx (22). SCAFFOLD [17], Amplified FedAvg [39], and Amplified SCAFFOLD (ours). We tune each algorithm's parameters by grid search, including learning rate 7). amplification rate 7, and FedProx's μ. The search ranges and tuned values can be found in Appendix D All experiments were run on a single node with eight NVIDIA A6000 GPUs Code is available the following repository: petps://githhr com/ MoggruiLiu-ML-LLbb/AAA www.uudder-errrddic-aariiiiptpti
difficult objective based on a lower bound for FedAvg [3). The objective maps R R, is convex, and is parameterized by a smoothness L, stochastic gradient variance o², and heterogeneity K, so that it satisfies Assumption ] by construction. The complete definition of the objective can be found in Appendix Since there are only two distinct local objectives, we set the number of clients N 2 and the number of sampled clients S 1, and
Synthetic We evaluate each algorithm's 's convergence
the number of groups K = 2. All other settings can be found in Appendix D
Fashion-MNIST and CIFAR-10 We evaluate each algorithm for training an image classifier, using logistic regression for Fashion-MNIST and a two-layer CNN for CIFAR-10. To simulate heteroge- neous data in federated learning, we use common protocol 17 39 to partition each dataset into client datasets according to data similarity parameter 8. This protocol detailed in Appendix D Following 39, we set the number of clients N 250, data similarity
5%, and the number of sampled clients per round = 10. For client participation, we set the number of groups K so that each group contains clients that have majority label from two different classes. We run all baselines with 5 different random seeds and report the mean results with error bars Section 5.2 (the radius of each error bar is standard deviation). All other settings can be found in Appendix
Additional experimental results are provided in Appendix E. where we compare against extra baselines (FedAdam [32]. Yeg (32), FedAvg-M (5), and Amplified FedAvg with FedProx regularization), and evaluate training under another non-i.i.d. client participation pattern.
Faahionn-MNN MNIST is licensed under the MIT License.

---

Synthetic Objective
CIFAR-10
Objective Value
0.5
0.4
AAAAAAA
Distance to Minimum
0.8
MAAAAAAI
0.007
0.6
0.3
0.6
Train Loss
Test AArn
0.5
0.006
0.2
0.4
0.1
0.2
0.005
0.0
0.0
0.3
2000
4000
2000
4000
5000
10000
5000
10000
Rounds
Rounds
Rounds
Rounds
FedAvg
FedProx
SCAFFOLD
Amplified FedAvg
Amplified SCAFFOLD
Figure 1: Results for synthetic objective and CIFAR-10. Left: Amplified SCAFFOLD and SCAF- FOLD both converge to the global minimum, but Amplified SCAFFOLD converges significantly faster. Right: Amplified SCAFFOLD converges the best solution by significant margin. Note that in both cases, the curves for FedAvg and FedProx are nearly overlapping.
5.2 Main Results
Results for the synthetic experiment and CIFAR-10 shown in Figure I and results for Fashion- MNIST are shown in Figure We make the following observations:
Amplified SCAFFOLD converges the fastest. In all three settings, Amplified SCAFFOLD reaches the best overall solution among all algorithms (by all metrics) and requires the fewest communication rounds. In the synthetic experiment, Amplified SCAFFOLD requires 800 communication rounds to reach an objective value of 0.2, while SCAFFOLD requires 1900 rounds, and both FedAvg and Amplified FedAvg require 4800 rounds to reach the same objective value.
Amplified FedAvg is comparable to FedAvg. Amplified FedAvg shows slight improvement over FedAvg for the synthetic experiment and for Fashion-MNIST. Only for CIFAR- 10 is Amplified FedAvg significantly faster than FedAvg, but there it also exhibits a reduction in stability. The under- whelming experimental performance of Amplified FedAvg corroborates our discussion from Section 4.3 Amplified FedAvg requires many communication rounds and suffers from data heterogencity.
Contrary to our findings, the original evaluation of Amplified FedAvg 33 showed a significant improvement over FedAvg. One explanation is that the original evaluation employed pretraining using FedAvg, so that each algorithm was evaluated only for fine-tuning. Our experiments suggest that Amplified FedAvg may have limited improvement over FedAvg when training from scratch.
SCAFFOLD beats Amplified FedAvg. Despite lack of theoretical guarantees under non-i.i.d. par- ticipation, SCAFFOLD outperforms Amplified FedAvg in all settings. This suggests that SCAFFOLD may have reasonable performance under some non-i.i.d. participation patterns. For the synthetic objective and CIFAR-10, SCAFFOLD is still significantly slower than Amplified SCAFFOLD.
5.3 Ablation Study
To understand how each algorithm's 's performance is affected by data heterogeneity, the number of participating clients, and the number of client groups, we perform an ablation study Fashion- MNIST. First, we fix the data similarity = 5% and number of groups K = 5 while varying the
number of participating clients (S) over (5, 15, 20, 25). Next, we fix S 10, K = 5 while varying the similarity 8 over [2.5%, 10%, 33%, 100%). Lastly, we fix 8 = 5%, S = 10 while varying the number of client groups K (2, 4, 6, 6). In each of these 12 scenarios, we evaluate all five algorithms using the same settings as detailed in Section 3 We train with three random seeds for each algorithm, and report the average results in Figure (night).
Amplified SCAFFOLD reaches the best solution all settings. Similarly to Section 5.2 Amplified SCAFFOLD consistently reaches the best solution in terms of both training loss and testing accuracy. While our theoretical results provide guarantees for optimization, these experiments show that Amplified SCAFFOLD also exhibits superior generalization in variety of settings.
Robustness to data heterogeneity. When changing from completely homogeneous data (s = 100%) to extremely heterogeneous data (s 2.5%), the test accuracy of Amplified SCAFFOLD exhibits

---

Fashion MNIST
Fashion MNIST (Ablation)
0.84
Train LOSS
0.0025
0.0026
0.82
Test Accuracy
Train Loss
0.0024
0.80
0.0015
0.0022
0.78
0.85
0.0020
0.76
Test Acc.
0.80
0.74
0.0016
0.72
0:75
0.0014
5000
10000
5000
10000
Participating Clients
Groups
Rounds
Rounds
Similarity
FedAvg
FedProx
SCAFFOLD
Amplified FedAvg
Amplified SCAFFOLD
Figure 2: Results for Fashion MNIST and ablation study. Left: Amplified SCAFFOLD reaches the best solution, but SCAFFOLD is competitive. Other baselines are much slower. Right: Amplified SCAFFOLD is robust changes in data heterogeneity, number of participating clients, and number of client groups.
very small decrease from 84.6% to 84.45%, so that our algorithm behaves nearly identically with homogeneous data as with extremely heterogeneous data. All baselines suffer larger decrease when transitioning from homogeneous data heterogeneous data.
Robustness to number of participating clients. The number of participating elients has smaller effect on performance than data heferogeneity, but some degradation happens in the extreme
= 5. In particular, SCAFFOLD has competitive performance with large $ 2 15, but its test accuracy drops off significantly compared Amplified SCAFFOLD in the case 5 5.
Robustness to number of client groups. As K increases, FedAvg and Amplified FedAvg get worse, while SCAFFOLD and Amplified SCAFFOLD maintain performance. It makes intuitive sense for an algorithm to degrade as K increases, since a larger means that the participation is in some sense "further" from i.i.d. participation. Still, Amplified SCAFFOLD (and SCAFFOLD) are able to maintain performance even as K increases. While the worst-case communication complexity of Amplified SCAFFOLD (listed in Table I) actually increases with K, these experiments demonstrate that in practice, Amplified SCAFFOLD can maintain performance as K increases.
6 Conclusion
We propose Amplified SCAFFOLD, an optimization algorithm for federated learning under periodic client participation, and prove that it exhibits reduced communication cost, linear speedup, and is un- affected by data heterogeneity. We also show that Amplified SCAFFOLD experimentally outperforms baselines standard benchmarks under non-i.i.d. client participation, and that the performance of our algorithm is robust to changes in data heterogeneity and the number of participating clients.
Limitations While our analysis covers general class of participation patterns, it may not cover some participation patterns that appear in practice. Our framework requires that all clients have an equal chance of participation across well-defined windows of time that are known to the algorithm implementer, which may not always hold. One such practical situation is where clients may freely join leave the federated learning process during training. Extending algorithm and guarantees for this situation would require reformulation of the optimization problem, and possibly additional assumptions about the participation structure. We leave such analysis for future work.
Acknowledgements
We would like thank the anonymous reviewers for their helpful comments. This work is supported by the Institute for Digital Innovation fellowship from George Mason University, a ORIEI seed funding, an IDIA P3 fellowship from George Mason University, a Cisco Faculty Research Award, and NSF award #2436217, #2425687. Experiments were partially run on Hopper, research computing cluster provided by the Office of Research Computing at George Mason University (URL: https://ore.guu.c.
10

---

References
[1] Durmus Alp Emre Acar, Yue Zhao, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based dynamic regularization. In International Conference on Learning Representations, 2021.
[2] Dmitrii Avdiukhin and Shiva Kasiviswanathan. Federated learning under arbitrary communi- cation patterns. In International Conference on Machine Learning, pages 425-435. PMLR, 2021.
[3] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, et al. Towards federated learning at scale: System design. Proceedings of machine learning and systems, 374-388, 2019.
[4] Wenlin Chen, Samuel Horvath, and Peter Richtarik. Optimal client sampling for federated learning, arXiv preprint arXiv:2010.13723, 2020.
[5] Ziheng Cheng. Xinmeng Huang, Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. In The Twelfth International Conference on Learning Representations, 2023.
[6] Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategies. arXiv preprint a:Xiv:2010.01243, 2020.
[7] Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Towards understanding biased client selection in federated learning. In International Conference on Artificial Intelligence and Statisties, pages 10351-10375. PMLR, 2022.
[8] Yae Jee Cho, Pranay Sharma, Gauri Joshi, Zheng Xu, Satyen Kale, and Tong Zhang. On the convergence of federated averaging with cyclic client participation. arXiv preprint arXiv:2302.03109 2023.
[9] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. Advances in Neural Information Processing Systems, 30, 2017.
[10] Hubert Eichner, Tomer Koren, Brendan McMahan, Nathan Srebro, and Kunal Talwar. Semi- cyclic stochastic gradient descent. In International Conference Machine Learning, pages 1764-1773. PMLR, 2019.
[11] Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. Clustered sampling: Low-variance and improved representativity for clients selection in federated learning. In International Conference on Machine Learning, pages 3407-3416. PMLR, 2021.
[12] Margalit Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. In International Conference on Artificial Intelligence and Statistics, pages 9050-9090 PMLR, 2022.
[13] Michal Grudzieú, Grigory Malinovsky, and Peter Richtárik. Improving accelerated federated learning with compression and importance sampling. In Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities, 2023.
[14] 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:12052 120022120666 12064, 2021.
[15] Dzmitry Huba, John Nguyen, Kshitiz Malik, Ruiyu Zhu, Mike Rabbat, Ashkan Yousefpour, Carole-Jean Wu, Hongyuan Zhan, Pavel Ustinov, Harish Srinivas, et al. Papaya: Practical, private, and scalable federated learning. Proceedings of Machine Learning and Systems, 4: 814-832, 2022.
[16] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings. al. Advances and open problems in federated learning. Foundations and trends machine learning, 14(1-2):1-210, 2021.

---

[17] 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 machine learning, pages 5132-5143. PMLR, 2020.
[18] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519-4529, PMLR, 2020.
[19] Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv: 2016.
[20] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[21] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):00-60, 2020.
[22] 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,555000500 2020.
[23] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data, arXiv preprint 1rXiv:1907.02189, 2019.
[24] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pages 3043-3052. PMLR, 2018.
(25] Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao, Ying-Chang Liang, Qiang Yang, Dusit Niyato, and Chunyan Miao. Federated learning in mobile edge networks: A comprehensive survey. IEEE Communications Surveys & Tutorials, (Q3))2031-2066) 2020.
[26] Grigory Malinovsky, Samuel Horváth, Konstantin Burlachenko, and Peter Richtárik. Federated learning with regularized client participation. arXiv preprint arXiv:2332.03666, 2023.
[27] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication efffccient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[28] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint 17X00:/710.006/ 2017.
[29] Viraaji Mothukuri, Reza M Parizi, Seyedamin Pouriyeh, Yan Huang, Ali Dehghantanha, and Gautam Srivastava. A survey on security and privacy of federated learning. Future Generation Computer Systems, 15:6196640, 2021.
[30] Kumar Kshitij Patel, Lingxiao Wang. Blake E Woodworth, Brian Bullins, and Nati Sre- bro. Towards optimal communication complexity in distributed non-convex optimization. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 13316- Curran Associates, Inc., 2022. URL httphhttpp:///rceeeinngg www.ineeiii..ee www.: cctpppccccpppppppe wwwpr/epppppreeeeeeeeeeeeeeeeeee (5662225622eadddcleee00321212222
(tlles/paaer/2022/f111. .dff
[31] Matthias Paulik, Matt Seigel, Henry Mason, Dominic Telaar, Joris Kluivers, Rogier van Dalen, Chi Wai Lau, Luke Carlson, Filip Granqvist, Chris Vandevelde, et al. Federated evaluation and tuning for on-device personalization: System design & applications. arXiv preprint arXiv:2102.08503, 2021.
[32] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecny, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. ICLR, 2021.
[33] Elsa Rizk, Stefan Vlaski, and Ali H Sayed. Federated learning under importance sampling. IEEE Transactions on Signal Processing, 70:5381-532 2022.
12

---

[34] Yichen Ruan, Xiaoxi Zhang, Shu-Che Liang, and Carlee Joe- Wong. Towards flexible device participation in federated learning. In International Conference on Artificial Intelligence and Statistics, pages 3403-3411, PMLR, 2021.
[35] Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprini arXiv: 1805009777 2018.
[36] Alexander Tyurin, Lukang Sun, Konstantin Pavlovich Burlachenko, and Peter Richtárik. Sharper rates and flexible framework for nonconvex sgd with client and data sampling. Transactions on Machine Learning Research, 2022.
[37] Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effieee sgd algorithms. arXiv preprint 1rxivv/808.00576 2018.
[38] Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al- Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to federated optimization. arXiv preprint arXiv:2107.06917 2021.
[39] Shiqiang Wang and Mingyue Ji. unified analysis of federated learning with arbitrary client participation. Advances in Neural Information Processing Systems, 35:19124-1917,, 2022.
[40] Shiqiang Wang and Mingyue Ji. A lightweight method for tackling unknown participation probabilities in federated averaging. arXiv preprint arXiv:2306.0344 2023.
[41] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H. Yang, Farhad Farokhi, Shi Jin, Tony Q. S. Quek, and H. Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. JEEE Transactions on Information Forensics and Security, 15:3454-3469,
2020. doi: 10.
[42] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Memahan, Ohad Shamir, and Nathan Srebro. local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334-10343, PMLR, 2020.
[43] Blake E. Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch local sgd for heteroge- neous distributed learning. Advances in Neural Information Processing Systems, 33:6281-6209 2020.
[44] Ming Xiang, Stratis Ioannidis, Edmund Ych, Carlee Joe-Wong and Lili Su. Efficient federated learning against heterogeneous and non-stationary client unavailability. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[45] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnise a novel image dataset for benchmarking machine learning algorithms. 2017.
[46] 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 arXiv:2002.07399, 2020.
[47] Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker partici- pation in non-iid federated learning. In International Conference on Learning Representations, 2020.
[48] Haibo Yang. Xin Zhang, Prashant Khanduri, and Jia Liu. Anarchic federated learning. In International Conference on Machine Learning, pages
PMLR, 2022.
[49] Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions. arXiv preprint arXiv: /8/2 02200, 2018.
[50] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In Proceedings of the 36th Interna- tional Conference on Machine Learning, ICML. 2019, 9-15 June 2019, Long Beach, California, USA, pages 7184-7193 2019.
13

---

[51] 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 Artificial Intelligence, volume 33, pages 5693-5700, 2019.
[52] Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in Neural Information Processing Systems, 33:5332-5325 2020.
[53] Chen Zhang, Yu Xie, Hang Bai, Bin Yu, Weihong Li, and Yuan Gao. survey on federated learning. Knowledge- Based Systems, 216:106775, 2021.
[54] Chen Zhu, Zheng Xu, Mingqing Chen, Jakub Konečný, Andrew Hard, and Tom Goldstein. Diurnal or nocturnal? federated learning of multi-branch networks from periodically shifting distributions. In International Conference on Learning Representations, 2021.
[55] Hangyu Zhu, Jinjin Xu, Shiqing Liu, and Yaochu Jin. Federated learning on non-iid data: survey. Neurocomputing, 465:371-390, 2021.
14

---

Contents
Introduction
2
Related Work
3
Problem Setup
3.1
Participation Framework
3.2
Specific Participation Patterns
4
Algorithm and Analysis
Algorithm Overview
4.2
Main Results
4.3
Application to Participation Patterns
Proof Sketch
5
Experiments
5.1
Setup
8
5.2
Main Results
5.3
Ablation Study
6
Conclusion
10
A
Proof of Theorem 1
16
Preliminary Definitions
16
A 2
Proofs
17
Proofs for Specific Participation Patterns
45
Complexity of Amplified FedAvg
48
D Experiment Details
49
D.I Client Sampling Parameters
D.2
Heterogeneity Protocol
50
D.3 Hyperparameter Tuning
50
D.4
Synthetic Objective
50
D.5
CNN Architecture
51
Additional Experimental Results
51
Additional Baselines
E.2
CIFAR-10 with Stochastic Client Availability
52
Extended Comparison with Baselines
52
15

---

A Proof of Theorem 1
A.1 Preliminary Definitions
[N]] that is, by the randomness in the stochastic gradients during round Also, let 2.o denote the filtration generated by {g- ro S r < ro + P, 2 E [N]), that is, the randomness in client sampling between rounds rn and To + P - 1 (inclusive). Also, let 9 denote the filtration generated by Go U U... U URR-1 and Q denote the filtration generated by 2o U 12 U... U QR-P. Similarly, let G.r denote the filtration generated by Go U 91 ... J 9--1 and 2.n, denote the filtration generated by 2o 2p U... U 2 Lastly, denote E. | rio Grr.l.
Let G. denote the filtration generated by {s
In order analyze the control variate errors (i.e., [Z.)) G D) introduce notation to
refer the iterates whose stochastic gradients were used construct G These iterates exactly the iterates during the most recent window before vo in which client was sampled, i.e., where
}. D De=mp q. 0. For each fro, ,...,, + P 1}. k fo....,I- 13, and i [M]
(m+1)p-1
Tu
let
((rr) = fr
%
11(r -P P)
4r
with the initialization ((r) = 0 for all r E (-P,..., -1}. Then denote
y =x((r),
2, d(()))
G El()))
Also, denote z = Dr=ro
Drotp-1
2y. Then we can rewrite
G
Ps ro
P
k=0
Define
N
Σ
Br.k
1=1
N
Dr.h
Σ
9,1
|
|||
i=1
Mr.
E
|| k
Zro [2|0]
Fg 11
St
tro
0
IP
$=7a
k=
ro-
N
{ g
> 0}
To+P-1
w
Σ
Σ
9
P7/
Tr
1 -vo-1
A1 70
P
2.
10-1 2 p
As discussed in the main body, Fy is a weighted average over local client models, weighted according to client participation. D,, and Mr are the drift terms described in the proof sketch of Section 4.4 In the proof sketch, we also informally discuss the control variate error Ct.y | fārr)) G
16

---

This error closely related the term So defined above, since E [V E|G 0]1 5.
The quantities w oi, and A arise in our proof from the use of control variates under non-i.i.d. client participation. As discussed in the proof sketch (Section 4.4). bounding the enrors introduced by control variates involves a non-uniform average of non-uniform averages of error terms. This nested non-uniform average can be bounded by uniform average as long as the term w is not too large,
which is exactly the requirement stated in Equation On the other hand, the term A7 arises while bounding the variance of the update || Tro and it represents the sample size for which the correction G ra is computed. When the client sampling distribution is closer uniform, then each client may participate frequently during each window of P rounds, and the effective sample size used to compute each control variate large. this case, the variance of the update || Tr, will be smaller, since larger sample size implies smaller variance. For general client sampling distributions, Ar. describes the reduction of variance of one component of the update (i.e. G due to the sampling of stochastic gradients during the previous window of P rounds. In our analysis, the variance of the update | - Tr,ol |l can be bounded in terms of the variance of G which in turn depends on - The condition in Equation eessetion2 essentially enforces that clients participate sufficiently uniformly, so that the variance of G can be bounded. We note that both Equation | and Equation are satisfied by i..dd participation, regularized participation, and cyclic participation.
Finally, for ease exposition, one clarification must be made about the conditional expectation [||| as it appears in, for example, Mr,k- The filtration Q contains randomness from every round from 0 to R - 1. but the expression of which we are taking expectation may only depend on randomness for smaller subset rounds. For example, in My the expression [ Zr.ll only depends on the randomness up to round r < ro + P. so that
E [| Tre |2 = E [[] Tr. P1r p]
In several places throughout the proof, we will replace [|||Q] by Bl-1Q.ro+22 pl in similar situations.
A.2 Proofs
Lemma 1. If S GOLIP and E,, 1 = N. then
Dr + My, I 10877 12 peg (V |1 + (757 657 o²
+ 2.0 Σ dmn 11 ) sy + 36n
S rg²
(3)
1=1
and
Tro+ P 1-1
E
Σ k=0
(Dr k + Mr.k)
< 13 3gg | (1,)) )1(} + (7 o²
r=no
22
1 N
Σ [
(4)
Proof. Denote
1-1
G 10
Pst
ry
smro
km
N G
1
N
To'
Also, denote L. = Fx k (7,)
G + Gr, and gr.k = =Vi(E>)) G + G G;, is the analogue of G.o, that depends on deterministic gradients V fy instead of stochastic gradients.
17

---

10/
Variance of updates We
errors E G G 112 0 = E
first
compute
the
gian
and
Ei= of (g'. gr.)) |
which will be needed in several places.
-
2
P k=
E
-
Pz
T0
k=0
70
1-1
Ps
s P.--PR P
02.
(5)
where (1) uses Jensen's inequality. Therefore
|| gi.x 11 [/
E
= E
|||
Sh,w - v((()()))) -G G + (Gro - G.,) 17
3E
v F. (x)
mi k2
Vfilot w) |1 3E c G |
G|.... G.a 1/
+3
3E
V F (.,) Vf(( x
3E c G 1/
|| Σ G c%,) o
3E
3E
|||
V..
Ex,
(x
x )1 17/
3E [| G 0
N
+
1
Σ 14
-
12
< 2002
18

---

where the last line uses Equation 5
Also
N
E
T g - Fine)
2
N
Σ 4 ((VE -V - (G (ru) + (Gr, Gru))
N
< 3E
Σ dr (V x
0 + +3 Σ dr (Gi -Gr 2
+ 3E
Σ 4r (rro Gro) 2
N
3E
Σ de (V (Io) x ( - (=
3E
Σ o C -Ghh 0
N
( - -/a) | Q
+ 3E
Σ N
i=1
N
@
E
FFs (2 ((((
+ > E
a (G - -o,))
+3
Σ
N
F.
1
G -
G 1"
1=1
N
33
Σ
(1:)
(
(1)
S/ Vi )) 012 + 3 Σ
(1:) 2 E || - G ||
1=1
+3 N2 1=1
1
Σ
E
[|| ||
& 0/
NV
(9t)² +3 0²
< 60
N
6p² +3 1
1
S 2
N
(8) < 9p²0²
(7)
where (i) uses the fact that stochastic gradient noise is independent across each client, and (ii) uses
19

---

One-step recursive bound for Dr
For any &s 2 0,
N
N
Dr.k11 =
Σ
E
Fy k+
Σ
C
x
r+++1
Q
1=1
1=1
N
N
Σ
E
ng
Σ
( 1 - ngght
2
1=1
1=1
N
Fr k
Σ
- 17
grik
Σ
G. A
1=1
j=1
j=1
Σ 9 E
Dr,k Σ
17 grik Σ
G.
j=1
N
+ 17
B
(gr,k
gr,k) + Σ L -
Q
N
N
N
(4)
4 E
Ky
G. T.
1]
Fr.h
Σ
kk
Q
-367/" 2
2
(
x
1 + スィ
Σ
N
B
w
N
T
x
k.
1=1
J 1=1
21
N
N
+ (1
Σ
Lrr
Σ
g. kk
2
+ 36:7²0
1=1
j=1
N Σ
Dr.k + 1 D A1)
Σ 9
gr,k
9 r.
Q
+ 361 2 02,
(8)
j=1
where (1) uses
E
Σ
( Fmme) Q
==1
N
< 2F
|lohn
-hh 11/0
+ 2
Σ
grieel
2
22
||
11
+ Σ
12
0
(0)
< 2
20

---

(a) uses Equation and (ii) uses Young's inequality. Focusing on the second term of Equation
N
N Trikk
G.B
g.g.
Σ
Σ oe
g
j=1
G.
gr.k
gr.b
2
VSJ( + 6% 1 0
[[i -G
(///0/ - ())
- - + 2F | - 0% 1
21E
1=1
1=1
N
- - [0.]
E
where (i) uses Jensen's inequality. Using the decomposition
(i(a))))) 6% (VSi(a)))) v.((a,)))) + (V)(( - V(((ar))) + (V(( - Go))
have
N
E
gr.k
Tr.k
Q
1=1
1=1
4
dr
3E
V (i(
+ 3E [IV - V -VA(,, 11/
1=1
3E
||
- - 17
121
Σ
|| - 2m
12L Σ 인B -
B,o 13
N
+ 12
Σ
E |
f((( - G% 1
1=1
N 12,L'D,, + 12L + 12
To-1 I-1
Σ E
V (i((o)))
(
2
pz P
i=1
s= P k==0
To 1-1
Dr, + 12T. M,,k + 12 Σ
F.
i=1
rg-
8=Tu-
N
ro-1 [-1
< 12T. Dr, + 12I + 12
Σ
Pzi
i=1
Pr
#=10
k=
122L"D.b + 12L Mr + 12L Σ
1
To
E | vi.
4r
P
s=1g Pk=0
N
< 122.2 + M, + 12T.2
S
1=1
21

---

Plugging back into Equation 8
Dr S
1+ 21
1
Drst + 12
Drik + Mos +
Σ 9
361/20²
N
1
1 A
+ 12n (2+ Druk + 12n22L(11 X1)
Mrik +
g To
+ + 0².
Now choose d1 2I, so that S and
12 L3 = 18 s 361 S 27
where we used the condition 7) 5 60L.P This yields the following recursive bound on k
Dr.++1 (1 (+)) Dr, +
2 I Σ 5 + 361 36
(9)
One-step recursive bound for Mr For any ts 2 0.
M2
E
Σ g 2 x41
Tro
E
q, r.k
Dro
17
9
Q
E
Bro
17
Tr
+ 2BB
Σ o ( Fiac)
E
Σ
Bro
T. *
2
+ 9n1 8²00
1=1
(8)
N
N
1
1 Aı
E
Σ
Zrro
Q
+ 21 22)
Σ
de
+
9n² p202
i=1
N
1 + No
Mr.k + 172 (1 + 22)
Σ
g A
+ 9n2 p²0
1=1
1
Mr,k + 172(1 + Az))
Σ
E
||مامم|1 11 0
11/0]
+ 202
(10)
1=1
22

---

where (i) uses Equation| and (ii) uses Young's inequality. Focusing on the second term in Equa-
tion 10
11
N
Σ
(i(((a - G + +,,oll' 11 [ 0
Σ x
|| - vf((Er,))) + (Vfi(E,,))) Vff(a.)))
+VVi((E,)) G. + -G.. - vf(ā,,)) +
N
$ E
Σ
[ V/(EEN) +5 Σ F V
1=1
N
+ 45
F
[
G [1/0]
+ 5E
||.... () ///00]
+
5E [V 0
N
N + +5.2
< 51.2
||a||
- 11/00
[r,,k Frool 1/
1=1
i=1
N
+57
Σ
d
+
1
E
v (1'
2
+ 5E
)1 []
N
p Pzop-p pl
1=1
s=ro P==0
S <5L L5L2DrA . + 5L2.2 Mr
+5
df + N
R
1
Σ
Σ
+ 5
011
Pz+
pl
1=1
P
< <5L2Drr + 5L2 MM.
+5 Σ
dt + 1
To Σ
Σ
EE
+ 51
[IV
>1 []
psi Pr
==TO
N
< 5L2DD,, + Mr + 5L22
+ N
S + 5E [1
1=1
Plugging back into Equation 10
Mr S ( 1
1x2 Mr. + 5/72 + -22)
Dr.k + Mr.
o N
5%
+ +57 + LE [I [
+ p22
N
S 1+ A22 +5 11 )ao)
Mr, + +577 L2 (12
Dri +
Σ
de +
1 N
St
+ +1 + 11) [ )1/0| + 92?
Now choose Ag= = 2IP, so that 1 - 2 and
15
15 1² S 15
5172 + A2) 5
15L
2
12p2 21P''
23

---

where we used the condition
S
60LTP.
1
This yields the following recursive bound on My,k+1
Mr 1 (1 (1+ IP
Mr + 15 + 1P)
S
N
+ 15 [V] )1 p²0²
(11)
Note that the same argument can be used bound M,,0 in terms of Mr-1,1-1 with the same recurrence relation.
Unrolling the recursion For < L IP, let ro [U/T] and l L -4/T] I. Then let
d, Dr.,k, and m, = Mr Also, let
Q1 1,2
Q2 15n/ LP
N
0r 181 Σ
9,5 + +366200²
i=1
N
b, 1
St + 15
[E.)( ) + 9n2 p'2
Then Equation 9 and Equation
1I imply the following mutually recursive relation over de and m
0 [(1 + 1) de-1 + q-m--1 + are-1
k 0 otherwise
d,
m =
1 TP m4-1 + 92d--1 + br.-1.
(12)
where do = 0. We will unroll this recurrence, showing a bound for m, and de in terms of the following quantities. For any 0 < t < IP and ((s,t) = max(0, (0, t (s + 1).}. For any s,t, if k 0, define
s S Tr, let j(s, t) min s/} and
ag1t+1 0.
Otherwise, define
j(s.t)
-1)(11
((s.))
0..111 Oxgst 1 T)
+ P
(1+
-1
1
1
TP
TP
1-sl-2 Σ
+ 9192
1 1 IP
as1--1-i-
im
Also, define
Batt11 Bo,s
1 IP
1
+1fs re) l2
(1+1)) 1) h;
9192
k--2
(1+7)
1+ 1) 1)²
B
P
1-81-1
1s,141 =
1 +
as
P
IP
i=0
00,411 = P
Σ
+
1=0
under the initial conditions
Φ. = for all 5 < P and SP
0s.AI = 0 for all 8 < P and - k P
Ve.st for s < P
B..t7 = 0 for all S P.
24

---

Now we can unroll the recurrence in Equation 12 on
by proving the following statements by induction
(1+ 1 kz -1 nr,
T2.
de
I 91))
as +
Σ
ag
(13)
s=0
s=0
((1+
1 TP
s(0,0)
1
((.,2)
T
my IP
-1
(1+
921/,
b, + IP
(14)
TP
Equation 13 and Equation 14 hold for the base case = O, since do = my = Now suppose that
Equation 13 and Equation 14 hold for some S IP, and will show that they hold for t + 1. We
consider two cases: k 7 and h = 0.
In the first case, Tr+1 i.e., step / + 1 is in the same round step I and ke+1 k2 + 1. Using Equation together with the inductive hypothesis:
de+1 < [1+ + 1)
(((1+))
1) h -1 Or. 1 + 9il
7)
Σ
a + 1 Σ
anibs
==0
==0
s(m(e)
-1) -1)
E(H,A)
IP
(1
1
1
+ 42
by + TP Σ
Br + ar
TP
TP
s=0
s=0
+ ()
k++1
1
1
| i
+
ar.
I
+ q1l Σ
[
Dalt + PSS.
a=0
(1+
Csst + n P
(1+
1
j(a,1)
1
1 ((x,1)
+ 1192 Poos be
IP
IP
==0
3
1+ +)
ket1
-1
ar. I + qqll
dst++d +
Σ
as,t+
am0
==0
|+ +)
hm-m
-1
Or 1 + g
0.1+10g 0g +1
$=0
#=0
25

---

where (i) uses the fact that 0s,0+1 = (1+ }) 0..1 + Pso. and the definitions of as,t+1, Vo,t. and (11) uses hi++1 = ke + 1 and rz+1 = Tr- Similarly,
1
j(s,8)
-1 -1) (1+
1
((x.e)
m s
+ TP
TP
1 TP
+ +02W/..
by + IP
Ba
TP
==0
5=0
(((1+))
1)
kt
+ 92
-1
ar I + qı!
Σ
1s +
asrll
+ br.
s=0
==0
< TP) n
((11+
1)
s(a.1)
1
((0,1)+1
-1
1
+
TP)
IP
==0
1
((1+
1
p pact) )o0 60
1
+1 [
+ 92
Wast +
IP
IP
+IP)
[1 +
1 TP
Best + 1 {s= =re]
92 P
(
1
+ 7)
ke
-1
+
9192 P
Pzst 0g
==0
1 1+ TP
1(s,+11)
-1) 11 TP
1
((x,++1)
((1+
1
Vaat + P pasi)) )) ba
1
IP
+ 42
TP
8=0
1 1+ TP
42
(1+
he
9192
+IP
Best + 1 [11
p
- 1
p
Dast ag
0=
j(s++1)
((x,++1)
1 TP
-11 |+
1
IP
1 +
+ 122
by - IP
B 1ss
TP
0=0
s=0
(111)
I
1(,,+11)
(1+
1
((e,6-1)
S IP
-1
+ g22/0++1
b. + IP
B Ugs
TP
TP
0=0
8=0
where (i) uses the fact that for s < <rri
{(x,1)
{(,0++1
1
1
-1
|+
+1 r1) TP
TP
TP
1
-1) 1) (1 1+ TP
(+1-(++1)
+ TP
(1+ IP
1
s(aNt1)
-1) (1 (1
((+,+11)
IP
and for s = rr:
(1+
1
i(s,1)
1
{(s,()11
1
-1
1+
+1
IP
IP
IP
(1+
1
l-ol
(1
1
1
1
1+ TP
TP
TP
141-s
1
1
-1
TP
1 1(a8+1)
(1 1+ IP
8(s,+1)
1+ IP
1
(it) uses the fact that th,441 = (1 + } Uhst + $a,, and the definitions of Ba,411, &a,t, and (tit) uses ket1 = h; + and T141 = rt. This completes the inductive step for the first case (kr+1 # 0).
In the second case (i.e., k4 = 0), Equation 13 must hold for I + 1, since di-1 = 0. So it only remains to show Equation holds for + 1. Note that T; T++1 1. As in the first case, we can
26

---

use Equation 12
together with the inductive hypothesis to obtain:
j(s,++))
((,,++1)
m4+1 S SIPY
1+
1+
+ 9222,,111
by + IPP
s,,41
IP
TP
==0
==0
1(a,+11
1
((s,t+1)
T++1
IPP
1+
+ 9214,,0111
bg + IP
0s,1+103
Og:
IP)
IP
9=0
==0
where the second line uses the fact that the T++ element of both sums O. since ((rr) (+1)
Dr 1.+++1 0, and Φr. (iriiddtt d++1 O. This completes the inductive step for both cases, and proves
Equation and Equation 14
We can now bound at and Be.e separately by induction on t. First, for any s S P and f with sl S S IP, we claim that
Cxst S LP.
(15)
which we will show by induction on t. Let I P 1 be given. For the base case, Equation 15 holds when 8/ since ds,ss = O. Now suppose that it holds for all L' S Then
(1+
- 1
IP
IP
t-st
1 0
1+
-1)
(+
IP
IP
t-st
1
1
1,
(16)
TP
and
-----2
t-sl-2
1
0142
Σ
1 TP
0sst-11i
36q2q21P
Σ
1
1
TP
1=0
1=0
((1
1
1-sl-1
= =36q7g212pa
-1)
IP
(1+
t-sl
S P
(17)
TP
where the last line the definition of 91 and Q2 together with the condition 7)
60L
3641 02 1 36 270,) 270,2 p2
270 p
1
S
S 1.
60
TAT4Pi
p2
Plugging Equation 16 and Equation 17 into the definition of as,411 yields
(1+
t-sl
0,,t+1 S astt
1+77
+ 2q1 P
- 1
TP
ki
1-sI-i
1 -
1
2q1 P
1
1 TP
1
1=0
ki
1-st-i
[+ 7
1
s 2q P
1+ TP
1-sl-i
(re-e)1 he
I 6q1 P
1+ IP
S 66h P
1
1
Σ
1
1
IP
IP
1=0
1
(8)
IP-1
1
< 18q1 P Σ
1+ TP
< 18
Σ
1 TP
1=0
1=0
(1+
1
< IP
-1
< 36g IP;
TP
27

---

where (i) unrolls the recurrence on the first line until asr,d 0. (ēi) uses PE (1 + 1)² 2 E (1+ ) since (1 + TP ) is increasing with i, and we repeatedly used (1 + ) <e 3.
This completes the induction and proves Equation T3
We will similarly prove the statement
BBs S 12 921
(18)
p
for all 8 S P - 1 and t with s S by induction on t. Let 8 S PP-1 be given. For the base holds when t sI since Bo,s1 = 0. Now suppose that holds for all t' S t. Then
case, Equation 15
R 2
91931 T
2
11
91
1
3 -e S 12
1
P
-12 91
[1 (1+77 he-1
-1
P
S 12 21 12
[ (1+7) 1
he
-1)
(19)
22
(1+
1 k
- 1
(20)
p
where the last line uses the definition of 91 and q2 together with the condition 1) I GOLIP:
12. 270
12 & 12. 222,2777 2 L'TPP
L'rP
LAI4P4 S p3 1.
604
We now consider two cases: t < (s+ 1) and t 2 (s + I)I. In the first case, we have rr. and plugging Equation into the definition of Baa+1 yields
1 Ri
1 TP
2
(1+)
Ba,t11 S Be,t
1
+
7)
-1
h
1+ 1) ki-d
42
1
2
1
+
-1 1
P
IP
i=
1
1
h.
1 (+
1
he-i
-1)
P
IP
1=0
L2 P
1 TP
I
Σ
1+ 7)
1=0
< 6 I2
(1+77)
1
ku+1
-1
(1+
P
p
< 12 126 p
where (1) unrolls the recurrence on the first line until 8r.t = and we repeatedly used (1+ <
S 3. In the second case, we have > Tt, plugging Equation 19 into the definition of ps,(+1
28

---

yields
+ 12 n
(1 (1+1) | de
(1+1)-11 -1
Bs S Ba,
1+ IP
1
+ 12 9
(1+1) 1 1
Bat
1+
-1
IP
24 21
1+ TP
(1)
9192 11
12
t-sl
1 + 1
S
24
P
IP
i=0
24
(1+ TP)
f-s++
-1)
23
(1++))) IP
-1)
r < 12 92
12 p
where (i) unrolls the recurrence on the previous line until 3x,s1 = 0 and the last inequality uses the definition of qı and d2 together with the condition 1 S 60LIP"
48g 12 =4: 270m) 4 L
48 270
TTp
1
<
12 p3
12 <
604
IAT4p4
P
This completes the induction in both cases and proves Equation 18
We can then use Equation 15 and Equation 18 to yield bounds for the remaining terms of Equation 13 and Equation 14 as follows:
1-81-1
1-81-1
42 =
92
1+
1
as.----55
36q1921
Σ
1
1+
P
IP
IP
1=
1=0
IP-1
1
((1+
IP
< 36q1921
Σ
1
+
< 16
-1 1
IP
IP
1=0
72 72-270
270
$ 22 72 270m
4 12
1 p2
S
60c
L414p4
pg
and
010,, qiPP h-1
1 (1+1) Be,e- S 1291
h1-1
Σ
1 1+ (+
(1+1) -1 -1)
(1+1) -1
-1)
= =12910212
< 12
<
24q1q212
Finally, we can plug these into Equation 13 to yield
1 be -1 (1+11)
rt
d,
ar I 24q1 3
a, 36q1 T2p
Σ b,
< 2a,, I + 24q 24
Σ
a, + 36q 12p
b.r
4=0
a=0
29

---

and into Equation 14
m IP
1 mi
-1
1
(1
1+
1
12
+ p2
1
by
+
12 12
Σ
0,
IP
TP
==0
6
1
IPP
+
b. + 12q2 12
a2
P
P2
8=0
0=0
< 777
bg + 120z 12
as:
0=0
x=0
where (i) uses
1 m1
1
1
1-1
1
(1+1P) IP
- 1+
IP
Σ
1+
IP
IP
1=0
1P-1
(1+
1
IP
I
1+ IP
= P
TP
-
1
- P
1=0
and
1
m2
1
IP
1+
3.
IP
IP
Or, in the original notation:
N
N
DrA 21
180
Σ
S, + 36n7202
+ +6480m 6 1'1 Σ
1887" Σ
S + 361720²
+ L21
LP
15 +
N
1
S
+
IP
1 )| [| + 9 9n2)0022
N < 366/ L22
N
Σ i=1
g. Pg + 18 148-6407 6o
N
+ +9720m 2 p2
9 + NN)
S r0)
- L2 [V |
+ (7227²1 + 36 6480(r - ro) 6 I 15
+ 58 - ro) p 0²
(
N
ro+P-1 N
Σ
S 18 6480m 6 16p0p
Σ Σ S
i=1
ro+ P P-1 N
+ 99720m"
Σ
Σ
g
N
st
i=1
+ +(720"' + 36 6480n/ 1 p2 + 5832n) 4
[V/ |13 []
N
N
36,,,,,2
S + 9720 4 T Σ
Σ N
1
N
+ (18866807)) 1,5 7.5 p2 + 9720 T.
S St
no
+ +(7272 + 36 1666648077 2 ' + 5832n' 4 L L p2 p²)
97200
V []
(6)
N
N
N
< 36n22
Σ 1=1
+7700 p3
Σ N
st + 97537 1 p3
Tr STo
+ 4 L213822
4 1
\ |1 o
(21)
30

---

where (i) uses the fact that the interval fro.....r) r is contained in the interval fro............... ro P P-11 1} and (ti) uses the condition 1 S GOLIF to simplify non-dominating terms. Also
N LPP'
Mr S 71
Σ 1=r0
15n
Σ
9s
S + IPE [IV + 917 9n2 p²2 N
1
N
+
1812 2 L
S.S0 + +367'00 0²
iml
r N
< <105
S% + 33400n Σ Σ 4s + N
2 70
r=
T=
+ (03(r-ro)17 + 6480(r - ro ro) TTTTP) 0² + 105(1- - ro)) PE
V ) [1/
ro P N @ 105m
P-1 N
Σ
s d + ) + 32400 1
1/ 5
+ 1P33)/1P'2 + 6480n' $ 3 p2) o² + 105 2 2 f )1 0
< 10 p 1 N
S -
+ L p2) Σ
Tr S
+ +(63//1Pp² + 6480n 4 122 0² + 105
| ro )1 [
(0)
N
22 N
S + 106 20, p2
Tro StD
1=1
(=1
+ (637221pp + 6480n 22(
+ 105n 12 p2
)1
(22)
where (i) and (ii) use the same operations as in Equation 21 Summing Equation 22
and Equation
21
Dr + Mr S 36, Σ S. + (9720m' p (9720n'''r'p' + 105"7
1
Σ
St
N
Td
N Trp St
+ (0733)
+ 2 TPp² + 6480 o²
+
+ (97201 + 105 2 12 E | / (T )1 |1/00]
< 36n7 1212 2
S + 109 23
Tro N
5
(75m + IPp²) 02 + 12
V r. || [0]
where the last inequality uses S 80L.P. This proves Equation 3 Equation 4 follows by summing
over r' E fro..... To + 1-1 and & E (o...., 1), taking total expectation, and applying the
condition E,, 1..0 = N.
Lemma 2. If S GOLIP. 79 S 6OLIT Erg ( = 2. and E E (1th))
2 Ato] S s then
E - - 12]
< <6 P2B ( |1 + TTIP P (5mm0² + 77p T.) o²
N
+ +11,2,2231222
E st
(23)
31

---

Proof. By the algorithm definition,
ro+ P-1 N I-1
2l r P-1
N 1-1
Pp Pro = -y1
Σ
(V
Gr. = -1
Σ
gigr
k=0
y=70
A=0
To obtain the variance of the update Tr++P Bro.
+
gmit) [
E
de
k=0
= E
d - (G -Gro) + (Gro Gra)
k=
ro+ P Σ
< 2B
df (VB(a -V
k=
A
ro+P N 1
+ 2
ΣΣΣ de (-G + +G + Gro - Gro)
(24)
I= O==
A2
We bound the terms A₁ and A₂ separately follows. For A1
To
A = 2E
Σ
df
Ya
2E
E
Σ /
-
2F
[| (VR -VA60,)
A=
2
E (att² E
VI
1=1 K=o
ro+P N 1-1
20"
Σ ΣΣ (o:)
1= km0
< 2
(25)
where (i) uses the fact that for each i, { (VF((())) v((( is martingale difference sequence with respect to G (when conditioned on Q) and that stochastic gradient noise is independent
32

---

across clients. For A2
ro+ N
ΣΣΣ
g. (-G - G G Gro)
K=
rot N 1-1
rotP N 1-1
= DE
dr (r -G,)) + Σ
gr (rro - Gru)
1= 0=
r= i=1 0=
To
G
-Gr,) + IPP (G.o Gro)
4r
N
ro+s
N C - G + IP
= -TP
Σ
(G - (
P
N
r=r0
N
1
-IP
Σ
( -Grr),
N
80
N
A2 212
Σ
Tru
1
(r
- G
N
N
= =2
E
Tro
(G
2
N
21 PåE
Σ
EE
1
(G
G%,,
0
N
=2
Pro
E
G
1
N
= -222p2
4ro
1
2
E
re
2 (VF
N
Psi
Pi
s=to P k==0
= 222
Pro
1
To
Σ
E
(VF vi (2, v(((E(
N
pzi
f--1
P2E
(x 2 E | - v/:00
Tro
N
p2
gl
2 T2
s=to
k=
212p225 02 E
1
dro
T
N
p2 zi p)
2
1-
(z))² 2
2
Tr
S 22IPp'02
(26)
N
11 - 2/
where (i) uses the fact that, conditioned on Q, the variables G G depend only on stochas- tic gradient noise, which is independent across clients, and the last inequality uses the condition
E Di= (o%))) A p². Plugging Equation 25 and Equation 26 into Equation 24 yields
N
rotP N I-1 인t (g - ghA)
E
Σ r=ro
ΣΣ
< o22
(27)
0=
33

---

Therefore
E Tro+P 1
ho+P-1 Σ
=
g
i=
P-1 N 1-1
ST:1BB
Σ
+ 7
Σ
ΣΣ ofe (g gr.bk
i= k=U
P=
1= k=0
(1)
ro+P-1 Σ r=
N 1-1
g.
-421
1=1 k=0
P- Σ
IP
E ( G + Groll"] 1P72
1=1 k=
(1)
Po+P-1 N I-1
$ IPP
Σ
Σ
E
(
1 - x))
+ +IVL ) - (Z
(. -
|V 1 G.. + 1P
55, E (
PotP-11-1 N
1 Σ
(E [0
2,,1 + E g 12)
r=
km0 i=1
1 ro+P-1
[Z - 1 G..
Σ
Σ o
[ -
- 13
P
(m)
Po+P-11-1 1-1
1 53 [IV 2, |57
Σ
Σ k=0
Dr.k + My
P=Po
+ p10 1
E (V.)) - G 2
(28)
where (1) uses Equation 27 (ii) uses the decomposition
v((()))))) - -Gi + Grr, = + -V - (V.((E)))) - v(()))))
+
+ (V))) -.,) -VS(E,)) - -Gra),
34

---

and (izi) uses G..
N E G
1
and Er, [roo
1
to obtain
N
ro+P-1
E
V
(
Gr 112
+ Σ
Σ of
- 12 11
P
1=1
rero
ro+P-1
Ero
Grol? 1| +
Σ d [V.r((tro) - G
r=
N
P-1
E
[ Gro11++
E ro
[Vrr( -G,
P
i=
(
G.oll"
(
11
N Vf(( - 11
(.T(( - G%oo
N
(.rr))) - 1
1
((. - GG 112
N
The remaining term in Equation 28 can be simplified as:
1-1 IP
E [IV)))))))) - G 2 < E
(Tr
V
r= k=0
< E
(V.((ār)) - vf((((e))
IP
TTO-P
T=T0
P k=
1-1
E
Vf(().)) v.(eiin>1
IP
k=0
TD-
122
m0-1
1-1
*
v |
<
E
IP
7EM0
k=0
-T--P P
To-1
LLB
E
Bro
r=1o
mg
I I''E [S]
35

---

Plugging back to Equation 28 yields
Tro+P - 1
I 1 [1)) 17"
rot To+P-11- +5y21/121PP
Σ
Σ (rr MiA)
+107912221222
E [
N
k=0
(
2 25
|1 f( )13 + 4
108 +57
V )
+ 65 0²
N N
125 1
Σ
B [s
12 1
Σ E [
N
< < (1+ 108 L2 E (T )12)
+ +y (4mp²² +.37 9 1,2 1 p + 325
p22 p2) 0²
N
+ +100212L33222
127,
E S
N
2 p0 (Z )
MII (5-mp² + 7m LI) 0² 13
1
E
N
where (i) uses Equation from Lemma and (it) uses 17 S 60LIP and yn S 60LSP- This proves
Equation 23
Lemma 3. Suppose that Per, ( /Pamp and m N
0) 2 Prample E I 2irol
pa N
E.p (ota
N. and
(vt.)
A
S p². If S
Pronsic 60LIP then
60LIP
St ro+pl
5 3244 p2 +
20
22
12 E [1
N
Psompie
1=1
+
22667² 21 I + 195m 1 +
17
1 0²
Psample
1 2 Psample
1
[SS
N
Proof. Let Sis S N. We can consider the value S + under two cases: 4 > and the
complement. Let A = = > 0}. Denote
Bi 1 (Att) } IP
E
|
DrotP 1| o)
no Put---1 P-1 1-1
B3 = (Ait) }
Il
- Tro+ 17|0]
TP
8=7o
k=0
Then St S Bi + Bíj, and we can consider the two cases separately.
Notice that
| Tro+pl12 S 31|22,n 20,
2 ær.
112 + 3/ Tro+P -Erol1.
36

---

Therefore
r P-1 1-1
= (A7o) } IP
1
B
| - Tr p|| g]
8=10
k=
Po+
5-1
3
< 1 } }
qs 18 [|
- 20.011111 + 1E [| 2r. T..11/10
1P
k=
+ E B - Drall Ira1 [1//|]
3 Po+P-11-1
< { }
2. (Do + M,,x) +31 (4,,) } E || - 2,.1
IP
8=70
k=0
Using Equation
3 from Lemma
T
Po+P-11-
1 1(4%))
3
Σ
Ls (Do,k + Ma,k)
IP
8=70
k=0
$ {4%)
}
3
ro
P-1--11-1
93 1081112p=E [1V [| + 175m/² + 65n IP)) 0²
IP
B=TO
km
N
N
1
+ 1'0
Pro
+ N
5% + 1-3666 2212 Σ 22 St
j=1
<3241
f 2 [ + (2251)² I 195n IP IPP)) 0²
N
3 ro ro %h + )) 8% + 1 (
N
+32772121222 Σ
Σ
360 12
Σ 52
po
s=ro
j=1
= =324 || fa
2/ ② + (225m)² I 195n IPp²) p?) 0²
N
N
1 {Ai | r-+
+ 12 p2) Σ
pro + Nv) ))$t 5% + 108 1,212 Σ
1
Lol' 5%
PTtp
j=l
j=1
smro
Denote who
1(41.)
1 Σ
L.g. so that w = 1. ΣN
wio. Then
PV.
N
B < 324n² 2 1 P2
/ |11| [] + (225n² I + 195n/ 2 IPp)) 0²
N 122
Pa+P-1
+ +327 22 Σ
dro + 1 St + 2
Σ j=1
Σ
g 5
N
PTo
==1
8=70
+31 ( } E || Brp |3|0|
E [B| 2.o]
(5)
p2 [| | f( (122 2.r0] + (225m I + 1957²² 195")11pp²) o²
1 N
N
1 [
P-1
+ 634
Σ
Sy + 108, 21212
E
Σ
goud
2.ro 8%
N
pure
j=l
amr0
+ 33 [1 (4: } 1 - -xr, [m.]
(w)
E [B:]]
< 224mr212 22 || V (T) )1² + (225m)² 1 + 2 1Pp²) o²
+ 654m p2 E [ + 108 1,222 102
Σ f=1
E E [w 2.ro] s%,o
+3E [1 (4 | - 12]
(29)
37

---

where (i) uses Er, 10 1 = 1 and the tower property E [ 111211 = B B-1..rool. and (di) uses the
tower property E. [R 12 = [-]-
Now consider B2. Under A 2f z and yn Vi. for all r E fro...., to + P - 13. Therefore
T0+P-15-1
B2 = 1
1
Σ
Σ
E
Brotel 120] o]
IP
s=70 k=0
1a-1 Σ
1-1
(1
Σ
B
||BE. - t 20 0]
IP P
8=70- 0==
(9)
7o
2 {
(1+ A)E |I1a6. - - 11/0
%/3
IP pr
s=ro
1
+ (1+
E Tr Tro [1]
1 (4%)) (1+ A)
1
Σ
Σ B ||o.
- Troo 17|0]
TP == P==
+1
(1
x)
1
E
|| - Tro 11 x)
1 (4% (1 +ASS (1 [ 2) E || - Tro 1100
(1+)))
where (i) uses Young's inequality with arbitrary x >> 0. Taking conditional expectation 1(.l)
followed by total expectation yields
BBB] 2.rl] S (1 Psample) (1 2)8 + (+ (1+ 2) E 1 (Ath) || - -0,0 (
[1 1 E 1 (Ar.) 1|orotP- -2r01?? (30)
E EBB] < (1 Psample) (1 A)EE [$
Adding Equation 29 and Equation 30 yields
E St [h+pp]
=E[B]]+B[B)
2324
[ )1 + (225n² + 195n)" IPp") 0²
N
+ 2,
1 N
E [ + 108 2 1.2 Σ E Ee (
2.ro] s
+ (3 + x
1
+ (1 Psample) (1 + A)E [
E [| Dro 11
38

---

Averaging over i,
N
E
S
+
N
N
x 3241/ 1 F² E
V (T ]1²] + (225T)²
195/) 0² 65412
Σ
E [
N
+ 10817"
E
E
2.00
N
N
1
+ (1 - Psample)
(1 + A)
E
S
+
3
E
|
Zro 12]
N
V fV )1
+ (225n)1 + 195n IP p²) 0²
+ ((1 Psample) (1+ + 654 62 p2)
E S
j=1
1 3 + x
+ +1081/2L21 1
E
E
2:rol 5 ] +
E
Bro+P - [3]
I <324n/ p2g
f (1 )| |13] + (2257) 1 + 195,) 2 1Pp²) 0²
N
1
+ ((1 - Psample) ) (1+ A) + 762n p2)
E
S
+
3 +
E
[1 Tro
3].
N
where the last inequality uses the condition E choose A
[wtt
2.r0] S
pa N.
We can then apply Lemma
2 and
3pazppl
to obtain
10(1- -Pappl)
N
EE St
stotpl
3++ 1) o9 612)p1222) E [IV
324
+ 225mg I + 195 + 3+
1 2
5Λ + (3+ T 0²
1 N
+ (1- Psample) (1+ + 76277 12 + (3+ 1222
(1+
Σ
[S%
N
5=1
324n 2 12 p2
20
12 E [V)(2,)))
Psample
225m/ I + 195n/ 2 1pp² + Psample
17
?212IPP2
23
7m L1P o²
Psample
1 N
110
+ 1
10 Psample
12
L2
[St
3psample
N
1=1
324n 12 p2
20
12p2 E [V
Psample
+ 2266221 I + 1951/ 2 IPp² +
17
?21)21122
0² + (111) Psumple
1 N Σ
E [$
Psample
N
-=1
39

---

where the last inequality uses the conditions
<
Panple 60LIP
and yn S
and we used that 60LTP
Pumpl
3 +
3pszmp
Theorem (Theorem restated), Suppose Assumptions and 2
hold, and Blu 12:ro S P2 and
E (v%))
A S p².11 1f
Psample 60LIP
Psumple 60LIP
then Algorithm satisfies
Σ E
P
5A
(20mLTp²² + 5.88 0².
R
(OE.0......RR-)
Proof. Recall that
P N
1-1
N
K +ro+P Zr. = -mm
Σ
Σ
(F
ai (..e) + mIPP)
Tro
G
(31)
N
r=mb
k=0
Using the quadratic upper bound for smooth functions and taking total expectation,
( (f(En).
Po+P-1
B[f(Er++P) - f(xrr)) -mmB
Σ
4
V
F
k=
1
+ MIPE
Vf(ān)) ).
Tro
G
N
+ E
[|| Trg+
Ero 13
2
P
N
|>|
(.((Er))
Σ
V
F.
1=1
( (V((E)))
+ mmPP
En [
G
N
+ E [| P1ull
(1)
Po+P-1
N
1-1
||
-mmB
V.((rr))
Σ r=ro
i=1
k=
+ E
|| Troll?
(32)
2
40

---

where (2) uses the law of total expectation E|:] = E [,, F-]. and (ii) uses the condition Br, = N together with
ro P-1
I-1
no P-1 N Σ
Eyg
Σ
Σ
VF. f
Σ
Erg Va Sh,
r=ro
i=1
k=0
r=
P-+111 N Σ
Erg E [ V. Er,ee) [x
t= k=0
ro r P-1 N 1-1
Σ
Σ
Erg 9 F st,e)) x
1=M i=
ro+
Σ
E V.(
1=1 k=0
ro+P-1 N
= =E
Σ
fa (ar
Focusing on the inner product term of Equation 32
PooP-1 N
fi (a |>
V (Frro) Pyoo
Σ
i=1
k=
Tro+P-1 1-1 Σ
V (i 1
M R. TP
(PV
1=1
k=0
< P 18
|V [V )13
77 E
Ero
To Σ
Σ
V vi((
IPV (
21P
i=1
(33)
41

---

where we used -a, = = alI² - 2 lall
1111 - |6 all2 2/la|??
Also
Po+P-1
N
E
Si (
P=TO
k=0
Po+t-1 Σ
N
E
Buro
(VS( (.(())))) ))
r=TO
1=
Prot Σ
(
3E
Ero
4
(f(( -Vf((E,,
Tro+P11 P-1
3E
Ero Σ
4p
Σ
(V/((.))))
TrotP11
+ 3E
E Σ
Σ (V)(
- (a.
P=to
ro+t-1
N
3E
Σ
(V)
-
i=1
Pu+P-1
127
+ +E
Σ
Σ
d
Vf((ā,,)) - v.((Er))))
P=7O
E=
k=0
N
Tro P-1
+ 3E
B
Σ dr
(Vi((ā)) - vf(Et))))
T=TO
(10)
Po+P-1
N
1-1
< 3IP
Σ
E
V - (f.(E,,)))) )1²]
K=U
N
+ +IP
E
Vi (E.
i=
k=
rot p-1
+ p2
Σ
E T
Σ
dt
(V.(((rr)) Vs(Tro))
P
r=ro
(10)
To+P-1 N
ro+P-1 N 1-1
< 3I.2TP
E
||
+ 3T.2TP
ΣΣ
B
of || - Tro 11]
k=
k=
To+P-11-1
3T.
|||
|
1|/0
r=TO
Po+P-1
+3T.TP Σ
E
E
- 1100
k=0
TooP-11- I-1
< 3LP
Σ
Σ
(Dru + Mr.))
k=
where (i) uses the decomposition
42

---

(dd) and (idi) use Jensen's 's inequality, and (iv) uses smoothness of each fü along with the condition Plugging into Equation 33 yields
Eyo
Inu N
-mmB { Vf( Bro
P-+
N
V (i 2 |
Σ
TIP
E
[IV )1
+
3
2711.2
rot P-1 1-1
Σ
(Dr. + Mr
2
2
k=0
(9) .IIIP
[V ) |1 $2 22m [1087 1apppppppp p [ 11
E
2
N
+ (75n + 65n 2 12 P2) 0² + 254n 25 222
E
[s
$ ITIIP (-2 + 1621) p2 2
E (1x))
+ III (1131) + 1TPP)) 11) 0²
+ 381 3 p3
1 N
5
where (1) uses Equation 4
from Lemma
Plugging into Equation and applying Lemma 2 yields
(a - ((+ra)
$ mIIP (-2 2
1
+ 162n) 22
EE f + +mIP (113)) (1 0²
N
+ +881mm L 1
3p p3
1
+
LE
| -r
N
2
1=1
ImIP
1 - +
162n) 2 2 p2
IE [IV |1 + mIP (111 0²
2
+ 381mm3 133
1
E
st
L
6
[| f(
(34)
N
2
+ +IMIP (5ym0² + 77, LI) 0² + 12
ΣE(S'
1 162, + 31mLIP) [
SmIP
+ +mIP
?MLL" + 1177 121 + 9887 L'1P0 o²
N
+ (3817m) I.'88p'
+ +,
E [sh N Σ
(1)
1 16227
I SII
+ IILLIP E [
1 N
+ MII
?LLp'²
9 2 0² + Prample L
Σ
E St
(35)
where (i) uses 17
60LIP and mm
Danmps
Pampl 60L
43

---

Using Lemma
1P
E S |
N
s 22mL2IP
3224)=12p2 +
20
12 E
[I |1(]
Psample
17
(1- 1
+ 22661 + 195n/ IPp² Psample
?2 IPp2 0²
Σ
E
S
N
40
S SMIP
6488)2 +
2 22
E3 f(
Psample
+MIP
552m)"
390n 1 +
34
12 o²
Psample
1
1
+ 2P
E
S ra
Psample 7 IP
S Td.
N
N
j=1
S SmII
6.481 2
40
n21 2
E [[
Psample
+ +mIP (5527) L + 390n)² IP p² + mmppp 0²
+ +2mL
1 IP
E S
Psumple L 2 1
Σ
B
N
N
where the last inequality uses yn
S
Pump G0LIP
Adding this to Equation 35 and rearranging,
[[ + 2 1
E S
N $ E|5(Ero)] + 1PP
N
mpP (-2 +100 + 3.LIP +
40
1221,12p22 [VT((1))))
Psample
7 ?mL + 669n² 2 L2I + 488n 2 o²
+MIP
2
1
[[f((r))
+ 2 IP
IP
E
[
N
1=1
P PI
f f ||
+ P (4ymLp² + L" + 428 0²,
where we used 77 I PTLFP and 17 S S0L/P. Finally, can average over To (0, P.PP ..... R P} and rearrange to obtain
P
R[S(xo) [(ØR))
T,2P
N
Σ
10
Σ
E
S
S
R
MIR
R
N
Po,,,.
i=1
Lp + 33457 2 L2 + 2440m L2 0²
@
5A
3334, TT2 + 2, T.? o²
MIR
(w)
5A
+ (20mmL + L o².
IIR
where (1)
uses 1. EN
B[S
2 and
E E E[Sa]] by initialization, and (M uses P>1
N
N
and p 1.
44

---

Corollary 2 (Corollary ! restated), Let > and I 2 1. Suppose Assumptions 7 and 2 hold, and
that E[w,y 12rol I N and Σ (o
$ p². If
ro
Al
300AT.
R Ica
Prample
A 1/4 2/
P
7 S min
264
L3/4 R /1/1/2///22
LIP
Promple 60LIP
7
min
60v LIRpo
then Algorithm satisfies
P
E
/ S 302c?.
R FoE
Proof. First, 7) S PuPearee
Panppe GOLIP and y are satisfied. Therefore
Pamal:
together with Assumptions and imply that
2IILIP
GOLIF
the conditions of Theorem
54
E
+ (20ymLp² + 5785m22 o.
R
MIR
R-P.
From our choice of '/.
5785 17
A1/2p
p² Psample
L IIP min
2642
T33223//2 R1/2 Pa
12
1/2
5Lp² min
Psample 60LIP
60L1/2/1/2 R212
5pm
Therefore
P
Σ
5A
25yLLp2
MIR
P.....P....R..I..
5A
60 LTRR
60IIP
VA
25Lp''2
IR
VA
Psample
60v LIRpo
301
ALpo
300ALP
VIR
Psample
where we used our choice of 71). Finally, from our choice of It
P
Σ {(,
301 301
Vie²
300ALP
Psample
R
VT
VAL.o
Psample
300
ToE P.........
30222
B Proofs for Specific Participation Patterns
Here we derive the convergence rates for the specific participation patterns discussed in Section In order to apply Corollary [ the conditions in Assumption| 2 Equation [ and Equation 2 must be satisfied. Since we already showed that Assumption 2 is satisfied by regularized participation and cyclic participation (in Section 3.2). only remains to show that Equation aand Equation is satisfied, and plug the appropriate values of p². P. and Psample into Corollary
45

---

Corollary 3 (Regularized Participation). Under regularized participation, for any >> 0, there exist choices of q. Y I. and R such that B V O(+²) and
L.
(T
R R= 0
RI O
c
Proof. We first show that Equation and Equation 2 are satisfied under regularized participation. Let almost surely:
=o,.... R - PJ. Using the fact that Zrg N
ww 2.ro]
=
1
N
Drg
>0}
To+P-1
Loll
2.ro
E
N ro
ro+P-1 P-1
I Te
C.oo
N
prro
P
/=1
8 8
Po+
N
Fro Trot P-1
=
p
T
Q
p
E
L
Coro
5=To
jml
s=To
p2
E [ 2cro]
1
N
N
where used the fact that Σ i= of 1. This shows that Equation is satisfied. Also, d
means that vy 0, so that E (0%) " [ 0 s p², and Equation satisfied. Therefore can apply Corollary [ The complexity result follows by plugging in Psample 1 and choosing A000" P2
I= O
Corollary (Cyelic Participation). Under cyclic participation with K groups and S participating clients each round, for any > there exist choices of 11 "r P, and R such that [+][][@*)II]] s
( and
LK 2
NV RI = O 0
))
(ALO² Set
R R=
s
Proof. Again, we show that Equation 1 and Equation 2 are satisfied under cyclic participation. Let + g()), it holds that, the rounds r E (ru...., To + 1). client i belongs to group g()) and available only during round r(i). Also, let IT(i) denote the set of indices of clients in group g()). To simplify wf,- recall that for client in group (r mod K):
Tu {O.....B. R P}. Denoting g(i) & (i 1)] and r(t)
with probability S
0
with probability 1
46

---

and 9¹ = 0 for all clients i not in group (r mod K). So
N
00}
>
P-1
E [wo
Dirol =
E
Σ
2:ro
N
PTTo
ro
P-1
N
0}
E
2.rO
NP
Tro
j=1
6
N
1
c
0}
(r(1)
2AoO
NP
Tro
J=1
(88) 1
1
Prg
0}
gr(1)
2(0
Q.ro
NP
Tro
JEII(()
(88)
1
1 {
0 1
Gr(()
2roo
NP
1/SP
S
jEIT(()
Σ
1 ( 0} 2.ro
(r(t)
SEN((1)
(10)
E
(1)
2.o
N
S
S
1
5
.0)
+
N
N
N
S
pa
N2
N
where (1) uses df for all r + rii), (ii) uses de for all j $ II(i., (iii) uses the fact that
Py 0 implies (2()) 3/2 and 0/ .T. and (ir) uses the fact that S clients sampled in each
round. This shows that Equation satisfied.
To see that Equation 2 is satisfied:
N
E
Σ
2
A
E
E
Tro
O.
A
N
t=1
(8
1
1
SK
E
[ACH]
SNP
N
1 SNP
SK
To-1 Σ
/
(
1 ro-
N
P
(8H)
SK
1
1
1 1
1
SP
N
S
PS
1
SK
1
p²
5
N
5
where (i) uses the tower property, (ii) uses the variance of Th as computed Appendix C and (iii) uses the fact that 2 > 0 by construction of z and this case z = 1/ for exactly one r E (ro P....,,o ru - 1} and ये = 0 for all other r. Therefore Equation 2 satisfied.
This shows we can apply Corollary | The complexity result follows by plugging in Psample P K, p == 1 and choosing I O V
N
Ant
KNe
47

---

C Complexity of Amplified FedAvg
In this section we derive the computation and communication complexity required for Amplified FedAvg [39] to find an e-stationary point under various client participation patterns, which we listed Table of the main paper. [able compares the complexity under i.i.d. participation, regularized participation, and cyclic participation. Since i.i.d. participation is special case of cyclic participation with K = groups, here we only consider regularized and cyclic participation, and the result for i.i.d. participation follows.
Many works in federated learning characterize data heterogeneity by assuming that there exists constant & such that
[V.(2) V (x))l S R,
for all The previous analysis of Amplified FedAvg 39 instead assumes upper bound 8(P) on a weighted heterogeneity that depends on client sampling. Specifically, they assume that there exists 5(P) such that
1
ro Po+
P-1
N
Σ
Σ
(V
-(())))-V((())))))))))))))))((() < 83((P),
P
=
for all x and ro- We restate their Corollary 3.2 for convenience:
Corollary 5 (Corollary 3.2
33
informally restated). There exist parameter choices such that
Amplified FedAvg satisfies
VAL
A R
o² +
((11))
min E
|| [(,))
0o
(36)
VRI
RIP
As pointed out in their Section 4.2, can interpret 5(P) in terms of the conventional heterogeneity constant & as:
N
(P)) NK
Σ
1
Tro
N
Our Assumption b implies that Ee., 1 can take expecation of the above to obtain
= N If we choose v 2 0 such that Varlø I v then
[P((P) < N
This "conversion" of ((P) to and will allow to compare their complexity to that of algorithms that use the conventional heterogeneity assumption by computing for each participation pattern.
Regularized Participation In this case, o 1 almost surely, so that and accordingly (²(P) = 0. Therefore
VAL.O VRI
ALP +
2
min E [IV so
R
RIP.
Therefore the choices
ALP - 2
ALp²
R
RI O
El
Pe
imply
min E [|V < <
Cyclic Participation We can compute in terms of the parameters of the participation pattern: number of groups K and number of participating clients S in each round. Although we chose P K for Amplified SCAFFOLD, we can satisfy Assumption(b) ( choosing P mk for any E N.
and indeed achieve (P)) < 2 we must choose P = mK with depending
48

---

Let A(2) denote the set of rounds in fro...., + P - 1} during which client i is available. Note
that A(i) has size m, since P mK. Then
1 df
d
Σ rEA())
Σ
Σ
N
N
mK
bk
K
rEA(i)
rEA(1)
where (i) uses the fact that of = 0 for all A(i). Therefore
4
K
171
b
rEA(()
(1)
Σ
E
0r
1)
2
K m
rEA(i)
(1)
1
Σ
1 S
1
8 b
K
m²
$2
TEA(S)
1
(1- 8
SmR2b
b
SK
SNP
N
where (8) uses the fact that { (rEA()) are independent and (ti) uses the fact that q equals times Bernoulli variable for A(i).
With a bound for 2 we can bound the remaining term in Equation 36 as follows:
2² N
SK
E
S
N
Therefore, Amplified FedAvg under cyclic participation can find an e-stationary point with the choices
R²2
N
SK
}
P 2 max
K.
2
S
N
ALK + R2
AL
(1
SK
R O
2
Sea
N
ALo2
RI 0
Set
D Experiment Details
Here we discuss experimental details deferred from the main body: client sampling parameters, heterogeneity protocol, hyperparameter tuming, definition of the synthetic objective, and specification of the CNN architecture used for the image classification experiments.
D.1 Client Sampling Parameters
For the synthetic objective, we set the number of groups K = 2 and the availability time g = 240. and train for R 5000 rounds.
We set the communication interval
For Fashion- MNIS,, we set the communication interval I = 30 and train a logistic regression model for R 2000 rounds, with availability time 9 4.
For CIFAR-10, we set the communication interval and train a two-layer CNN for R 12000 rounds, with availability time g 10.
49

---

Table 2: Hyperparameter search ranges and final values.
Y values
?y values
values
Synthetic
FedAvg
[1)
{0}
FedProx
(1)
1000:10-9.100-111-
{0.01, 0.1, 1.0, 10.0)
SCAFFOLD
[1]
(0)
Amplified FedAvg (1.25, 1,5, 2,
{10 11006.10-3:0--111--
(0)
Amplified SCAFFOLD
[1.25, 1.5, 2,
110-0,100,,10- {0}
Fashion-MNIST
FedAvg
[1]
10-0..00.11--.111 [0)
FedProx
[1]
1100,.10...0-3/11
(0.01,
1.0, 10.0)
SCAFFOLD
[1]
1109.10-1.1-3.100-
(0)
Amplified FedAvg
[1.25, 1.5, 2,3)
110-5.10-..103.110 (0)
Amplified SCAFFOLD
[1.25, 1.5, 2,3)
00
CIFAR-10
FedAvg
(1)
{10 110-6.10-0 10 10 1.00
{0}
FedProx
[1)
[10-6,10-5,100
(0.01, 0.1, 1.0, 10.00
SCAFFOLD
[1]
11000.1000.1-411101
(0)
Amplified FedAvg
[1.25, 2
[10-6, 11000.100,11-44110
(0)
Amplified SCAFFOLD
[1255, 1.5, 2,
[10-9.10-3,10-4110--
(0)
D.2 Heterogeneity Protocol
The following protocol is commonly used the literature I7 39 to convert dataset into collection of heterogeneous local datasets according data similarity parameter s, where 0% creates maximal data heterogeneity across clients, and s = 100% means that data is allocated each client uniformly at random.
single, non-federated dataset (e.g. CIFAR-101 10) is partitioned into two subsets: s% of the samples are allocated to an i.i.d. pool and randomly shuffled, and the remaining (100 - s)% of the sampled are allocated to non-i.i.d. pool and are sorted by label. Samples are allocated to each client so that 5% of each local dataset comes from the i.i.d. pool, and the remaining (100- s)% comes from the non-i.i.d. pool, that with small s, the majority of each local dataset consists of small number of labels.
D.3 Hyperparameter Tuning
For all three experiments in the main body (synthetic objective, Fashion-MNIST, and CIFAR-10) 10), each of the four baselines individually tuned with grid search. For algorithms that amplified updates (Amplified FedAvg and Amplified SCAFFOLD), we tune the amplification rate 7 by searching over fixed range of values. For the other algorithms (FedAvg and SCAFFOLD). over a fixed range of values. For fixed range of values. The search range and final values
indicate the lack
of amplified updates by setting = 1. We tune by allowing FedProx's и parameter, also search for each parameter are written in Table 2 along with the final values adopted for each algorithm.
D.4 Synthetic Objective
For the synthetic experiment, we use difficult objective from a lower bound analysis of FedAvg 43 As defined in the lower bound analysis, the objective is parameterized by H, K, o, c, μ4 and L.
50

---

PashionMNIST
0.84
0.002/5
0.82
0.00250
0.00
0.00225
0.00200
Thrt
0.75
0001755
0.74
0.00150
2000
4000
6000
8000
10000
12000
2000
4000
6000 Pounds
RO00
10000
12000
Rounds
Fedkig
SCAFFOLD
Amplitied SCAFFOLD Amplified FadProx
Redkdam Fechagi
Recking M
FedProx
Ampllled Fodkvg
Figure 3: FashionMNIST with additional baselines. Amplified SCAFFOLD maintains the best performance.
The objective maps R4 to R, and there are only two clients with corresponding local objectives
f1(2)
1 (x) cc)=
H
22
Vic
2
H
[xss+t
+ k34
2
2
H
H
Vpc
H
f2(x)
(x1 c)²
(23
[mal
KT4
2
2
VH
where [x]+ == max fz, 0}. The stochastic gradients for and f2 are sampled from the distributions
(x) fez and V f2()) + feg, respectively, where ~ N/O. o²) and es denotes the third standard
basis vector R We set the parameters of the objective as follows:
= 16, K = 16, o ==1
c= 1, 1 = 2, =
D.5 CNN Architecture
We use simple 2-layer CNN for CIFAR-10. The first layer is convolutional layer with 64 channels, 5 x 5 kernel, stride of 2, padding of 2, and ReI.U activation. The second layer is fully connected layer with no activation.
E Additional Experimental Results
In this section, we provide two additional experimental results. First, Section E. we add four baselines the experimental settings of the main paper: FedAdam (32. Fed
FedAvg-M (5). and Amplified FedAvg with FedProx regularization. Second, in Section E.2 we evaluate nine algorithms (five from the main paper and the four additional baselines) under another non-i.i.d. client participation pattern for the CIFAR-10 dataset, which we refer to as Stochastic Client Availability (SCA).
32
E.1 Additional Baselines
We evaluate the four additional baselines for the Fashion-MNIST and CIFAR- 10 experiments from Section 5 keeping the same experimental setup. We tuned the hyperparameters of all baselines according to the hyperparameter ranges suggested in the original paper of each algorithm, and we allow the same compute budget for tuning each baseline as we did for tuning the algorithms in the original paper, in terms the total number of hyperparameter combinations evaluated. Also, the results averaged over five random seeds. The results are shown in Figures and
For FashionMNIST, FedAdam and FedYogi reach moderate training loss quickly, but are soon overtaken by Amplified SCAFFOLD and later by SCAFFOLD. FedAvg-M exhibits a minor advantage over FedAvg, but performs about the same as Amplified FedAvg. Amplified FedProx (i.e. Amplified FedAvg with FedProx regularization) performs nearly identically to Amplified FedAvg.
51

---

CIFAR-10
0.0075
0.60
0.0070
0.55
Test. Accuracy
0.0065
0.50
Trein
0.0000
0.45
0.0055
0.0050
2000
4000
6000
8000
10000
12000
2000
4000
6000 Rounds
8000
10000
12000
FedAug
SCAFFOLD
Amplified SCAFFOLD
FedAdam redrogi
FedAug M
Amplified Fed/ig
Amplified
Figure 4: CIFAR-10 with additional baselines. FedAdam is competitive, but Amplified SCAFFOLD maintains superiority.
For CIFAR-10, FedAdam is more competitive, but is still outperformed by Amplified SCAFFOLD. Yed and FedAvg-M are further behind, though both still outperform SCAFFOLD. Amplified FedProx is again nearly identical to Amplified FedAvg.
These additional comparisons demonstrate that Amplified SCAFFOLD outperforms strong empirical baselines (FedAdam, Yegio under cyclic client participation, reinforcing the empirical validation of our algorithm. This performance is consistent with the fact that Amplified SCAFFOLD has convergence guarantees under periodic participation, while FedAdam and Fed were not designed for settings beyond i.idd client sampling.
E.2
CIFAR-10 with Stochastic Client Availability
Here, we include an evaluation under another non-i.i.. participation pattern, which we refer to as Stochastic Cyclic Availability (SCA). SCA models device availability which is both periodic and unreliable. Similarly to cyclic participation, the set of clients is divided into groups, and at each round one group deemed the "active" group, while the others are inactive. Unlike cyclic participation, in SCA not every client in the active group is always available: Instead, when group becomes active, the clients in that group become available for sampling with probability 80%, while clients in inactive groups have probability 5% to be available for participation. The active group changes every g rounds. This stochastic availability models the real-life situation where a client device can be unavailable at time of day when is usually available, or vice versa. In this way, SCA is more flexible than cyclic participation and better captures the unreliability of client devices. Lastly, we reused the remaining settings (g. K, I, etc.) and the tuned hyperparameters for each baseline from the CIFAR-10 experiment under eyclic participation. Again, we average each algorithm's 's performance five random seeds.
Results for CIFAR-10 under SCA participation are shown in Figure 5 Again, Amplified SCAFFOLD outperforms all baselines under SCA participation. The relative performance of each baseline is similar as under eyclic participation, with FedAdam staying competitive with Amplified SCAFFOLD, followed by FedYogi and FedAvg-M. The remainder of the baselines have significantly worse performance, and again Amplified FedAvg has not benefitted by adding FedProx regularization.
F Extended Comparison with Baselines
Here we include an extended comparison against two relevant prior works.
FedAvg with Cyclic Participation g analyzes FedAvg under cyclic participation, but the resulting convergence rate does not benefit from local steps unless regularized participation is satisfied. They analyze FedAvg for L-smooth and Jr-PL objective.. Using their notation, K the number of client groups, is the condition number of the objective, 7 is the intra-group heterogeneity, M is the total number of clients, N the number of clients that participate in each round, and is the number of communication rounds. Then the dominating term in their convergence rate for FedAvg under cyclic
52

---

CIFAR-10 (SCA Participation)
0.0075
0.60
0.0070
Test. Accuracy
0.55
0.0065
0.0055
0.0045
0.0040
0.30
2000
4000
6000
8000
10000
12000
2000
4000
6000 Rounds
8000
10000
12000
FedAug
SCAFFOLD
Amplified SCAFFOLD
FedAdam redhogii
FedAug M
Amplified Fed/vg
Amplified
Figure 5: CIFAR-10 under SCA (stochastic cyclic availability). Amplified SCAFFOLD converges fastest.
participation (Theorem 2) is
KEY?
pNT
M/K- -
Notice that the number of local steps (denoted r) does not appear this dominating term, so there is no way to reduce the communication complexity (compared to parallel SGD) by taking local steps. The only exception is when this term is zero from N M/K, which is equivalent to the condition that every client participates within every cycle of availability. Therefore, this result cannot show benefit from local steps unless the client participation is regularized.
SCAFFOLD In Section 4.3 we mentioned a discrepancy between the complexity of SCAFFOLD vs. Amplified SCAFFOLD in terms of the dependence on N/S. In Table the communication complexity of SCAFFOLD and Amplified SCAFFOLD under i.idd. participation differs by their dependence on s'
N. The complexity of Amplified SCAFFOLD is ) while that of SCAFFOLD
(+) 2/3) This difference in the order of N due to a potential small issue in the analysis of 3
SCAFFOLD, which we intentionally avoided by accepting slightly worse dependence on 3'
This difference stems from apparent mistake in the original SCAFFOLDD analysis. In the proof of Lemma 16 (PMLR version of SCAFFOLD), the second-to-last equation of page 32 is obtained with an incorrect step. Namely, while the current version includes
E, KN
Σ Bl 12
1.
S N KN
-
-x12
Σ Elyy -x
(37)
KN
where the last line is obtained by conditioning the event of - and the complement 5 & r-1 v which have probabilities N and N. respectively. However, this condition not 02,61
denoted in Equation 37
corrected version should be written
| - x"112 0 of
KN
1.k
S
E
1 a = v.
KNN
1.k
but this conditional expectation is not specified in the proof of SCAFFOLD. For the remainder of the proof Lemma 16, these terms are treated as total expectation, leading to an inconsistency. Lemma 16 concludes by applying Lemma 15 in order bound the term |E,-1 [Ax]]]]] However, when make the correction to include the conditional expectation, do not have bound of E, in terms
53

---

of E
| Ax"] we instead have bound in terms of EE
E E
Ax"
|
y
[|]
But this term with conditional expectation inside the norm can't be bounded with Lemma 15. A pessimistic solution is to Jensen's inequality bound
E
E Ax
d vrta-i]l' []]]]
E E |Axx1
a
vix-1]]
E
|
where the second line follows from the tower property. This is the step that we perform in our analysis of Amplified SCAFFOLD, and this results in the N dependence.
Fixing their analysis to recover the same ( focused on achieving the best known complexity in terms of a, and other problem parameters.
2/3 dependence may be possible, but we have instead
54

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Every claim made in the abstract is specifically tied to theoretical convergence property of our proposed algorithm, which are stated in Section 4.2 and proven in and B
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discussion limitations in the "limitations" paragraph of Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
55

---

Justification: All of the theoretical results are stated with the full set of assumptions in Sections 3.1 and 4.2 The proofs are contained in Section and B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
Experimental details are fully specified in Section 5.1 and Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
56

---

Answer: [Yes]
Justification: The code for our experiments included in the supplemental material with instructions for reproduction.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https Cot//ooodeeesiseeeeeee wwwpbbmmsssioooooooooooo for more details.
/mips.ccc/pulic//uuu
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The main training details are specified in Section 5.1
Details such as hyperpa-
rameters, tuning protocols, architecture choices, etc. are specified in Section D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All of our experiments show results averaged over 3-5 random seeds, and error bars are shown for learning curves. Error bar calculation specified in Section 5.1
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
57

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Hardware resources are specified in Section 5.1
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httppp/ss/.aaapp....ccppp/////aa
Answer: [Yes]
Justification:
We have read and conformed to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper a theoretical paper on mathematical optimization problems arising in distributed learning. We do not any direct paths to negative applications beyond those existing for any application of distributed learning or machine learning in general.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
58

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not involve the release of any data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Our paper uses existing datasets MNNIS, CIFAR-10), and we cite original sources for both datasets in Section 5.1
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt
package should be provided. For popular datasets, paperswi thcode. cww/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
59

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
60


Reviews:
[{"review_id": "SBft4oDL6x", "reviewer": "Reviewer_3Kpj", "summary": "In this paper, the authors examine realistic participation scenarios, including cyclic client participation and arbitrary participation patterns. They focus on a non-convex optimization setting, which is common in practical applications but challenging to address. To tackle this, they introduce a novel method called Amplified Scaffold, designed to effectively correct client drift—a common issue where clients' updates diverge from the global model. The Amplified Scaffold method builds upon existing techniques but enhances their effectiveness in this more complex setting. The authors not only provide theoretical convergence guarantees, ensuring that their method is mathematically sound, but also back up their claims with extensive experimental results. These experiments demonstrate the practical effectiveness of Amplified Scaffold in various scenarios, highlighting its potential for real-world applications.", "questions": "Please check the Weaknesses section.", "limitations": "The limitations section is well-written, but it should also note that the Amplified Scaffold method does not recover the rate of the original Scaffold method in the i.i.d. setting.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "In this work, the authors provide a detailed convergence analysis of a modified version of the well-known Scaffold method. While the theoretical framework appears to be sound, I did not thoroughly review all the proofs, so there may be some oversights. Nonetheless, the results obtained seem normal, adequate, and align with expectations.\n\nThe authors consider a wide range of settings and sampling schemes, which makes their work relevant to a broad audience, including both researchers and practitioners. This comprehensive approach addresses a significant problem in the field, highlighting its importance for real-world applications.\n\nAdditionally, the proposed method undergoes extensive experimental testing. These experiments validate the method's effectiveness and demonstrate its practical applicability in various scenarios. The combination of theoretical analysis and experimental validation strengthens the credibility and utility of the proposed approach.", "weaknesses": "1) The related work section in your paper is limited and could be significantly strengthened by including discussions of several closely related methods. For instance, a closely related method to Scaffold is ProxSkip (also referred to as Scaffnew), which was proposed as an improved version of Scaffold. Additionally, the Tamuna method, which incorporates partial participation, is relevant. Including a discussion about the connection to these methods will provide a broader context and highlight the advancements in the field.\n\n- Mishchenko, Konstantin, et al. \"Proxskip: Yes! Local gradient steps provably lead to communication acceleration! Finally!\" International Conference on Machine Learning. PMLR, 2022.\n- Condat, Laurent Pierre, Grigory Malinovsky, and Peter Richtárik. \"Tamuna: Accelerated federated learning with local training and partial participation.\" (2023).\n\nFurthermore, an arbitrary sampling framework has been studied in several recent papers. It would be beneficial to compare the assumptions on the sampling schemes used in these studies with those in your work. This will help clarify the differences and similarities, as well as the advantages and limitations of the various approaches.\n\n- Tyurin, Alexander, et al. \"Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling.\" Transactions on Machine Learning Research.\n- Grudzień, Michał, Grigory Malinovsky, and Peter Richtárik. \"Improving Accelerated Federated Learning with Compression and Importance Sampling.\" Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities.\n\nAdditionally, it is worth discussing the paper that addresses optimal complexity for the non-convex federated learning setting. This paper provides insights into achieving optimal communication complexity in distributed non-convex optimization, which is highly relevant to your study.\n\n- Patel, Kumar Kshitij, et al. \"Towards optimal communication complexity in distributed non-convex optimization.\" Advances in Neural Information Processing Systems 35 (2022): 13316-13328.\n\nBy incorporating these discussions, your related work section will be more comprehensive and provide a clearer understanding of how your proposed method fits within the broader landscape of federated learning research. This will not only strengthen your paper but also demonstrate the relevance and impact of your contributions.\n\n2) The major issue in your paper is that in Table 1, the comparison between methods and data heterogeneity is defined using the condition $ \\sup_x \\left\\Vert\\nabla f_i(x) - \\nabla f(x)\\right\\Vert \\leq \\kappa $, which implies uniformly bounded heterogeneity. However, in the original Scaffold paper, the authors used a different measure for bounded gradient dissimilarity:\n$$ \\frac{1}{N} \\sum_{i=1}^N \\left\\Vert \\nabla f_i(x) \\right\\Vert^2 \\leq G^2 + B^2 \\left\\Vert \\nabla f(x) \\right\\Vert^2, \\forall x. $$\n\nThis discrepancy is significant because uniformly bounded heterogeneity is a more restrictive assumption compared to bounded gradient dissimilarity. The latter is a more common and practical assumption in federated learning literature, as it better captures the variations in real-world data distributions.\n\nI strongly recommend revising Table 1 to use the less restrictive assumption of bounded gradient dissimilarity instead of uniformly bounded heterogeneity. This will make your comparisons more relevant and applicable to a broader range of scenarios.\n\nAdditionally, the notation $\\kappa$ used for bounded heterogeneity is potentially confusing. Typically, $\\kappa$ is used to denote the condition number, $\\kappa = \\frac{L}{\\mu}$, in the context of strongly convex functions. To avoid this confusion, I suggest changing the notation for bounded heterogeneity to something more standard and distinct, which will make your paper clearer and more consistent with established conventions in the field.\n\n3) Assumption 2 is quite complex and may be challenging for readers to fully grasp. I recommend providing a more detailed discussion of the class of sampling schemes considered under this assumption. Specifically, elaborating on the types of sampling schemes included, their characteristics, and why they are relevant to your study will help clarify the underlying assumptions. This additional context will make it easier for readers to understand the scope and implications of your assumptions, thereby enhancing the clarity and impact of your paper.\n\n4) In the experimental section, the rationale behind the choice of hyperparameters is not clearly explained. To improve clarity, I recommend providing a detailed explanation of the specific hyperparameters selected for your experiments. This should include the criteria used to choose these values, how they were tuned, and any relevant considerations or trade-offs. Offering this additional context will help readers understand why particular hyperparameter settings were used and how they influence the outcomes of your experiments. This level of detail will enhance the reproducibility of your work and provide valuable insights for others seeking to build upon your research.\n\n5) The main issue with the theoretical results is that they do not generalize the Scaffold method in the i.i.d. setting. For Scaffold, the convergence rate is $ \\frac{\\Delta L}{\\varepsilon^2} \\left(\\frac{N}{S}\\right)^{\\frac{2}{3}} $, while for Amplified Scaffold, the rate is $\\frac{\\Delta L}{\\varepsilon^2} \\left(\\frac{N}{S}\\right) $. This discrepancy means that Amplified Scaffold does not recover the more favorable convergence rate of the original Scaffold method under i.i.d. conditions.\n\nIt would be a significant improvement if Amplified Scaffold could match the original Scaffold's rate in the i.i.d. setting. Demonstrating this equivalence would not only strengthen the theoretical results but also enhance the practical applicability of Amplified Scaffold. If you can achieve this and show that Amplified Scaffold can indeed recover the original Scaffold's rate in the i.i.d. setting, I am willing to increase the score. This adjustment would highlight the robustness and efficiency of the Amplified Scaffold method, making it a more compelling contribution to the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments on our paper. Below we have responded to your questions and concerns.\n\nWeaknesses:\n\n1. **Missing related work.** Thank you for pointing out these works. We agree that including these works in the discussion of our paper will establish a broader context of the FL literature, especially around problems of client sampling. Below we've included a brief comparison of each work you listed against our submission:\n\n    (a) Mischenko et al, 2022 (ProxSkip/ScaffNew): ScaffNew achieves reduced communication rounds for FL with full participation on strongly convex problems.\n\n    (b) Condat el al, 2023 (Tamuna): Tamuna uses communication compression and local steps together to reduce communication in FL with i.i.d. participation on strongly convex problems.\n\n    (c) Tyurin et al, 2023: Improves convergence rate of nonconvex SGD for finite sum problems in terms of the smoothness constants, based on various unbiased data sampling protocols. Includes an application to FL with various client sampling protocols, which is related to our motivating problem of non-i.i.d. client sampling. These client sampling protocols are required to be unbiased.\n\n    (d) Grudzien et al, 2023: Combines local training, client sampling, and communication compression to accelerate convergence in terms of condition number and dimension (strongly convex problems). Similarly to [Tyurin et al, 2023], the client sampling schemes from this paper are required to be unbiased.\n\n    (e) Patel et al, 2022: This paper provides lower bounds for distributed non-convex, stochastic, smooth optimization with intermittent communication, both in the full and partial participation settings. They also include algorithms employing variance reduction which match (or closely match) lower bounds in the full and partial participation settings. These lower bounds are generally important to understand the limits of optimization under i.i.d. client sampling.\n\n    In summary, these works are all relevant for FL in general. With respect to client sampling, (a) applies to full participation, (b) and (e) apply for i.i.d. client sampling, and (c) and (d) apply to unbiased sampling. The analysis of these papers cannot be directly applied to our setting of periodic participation, and our work aims to fill this gap by providing an algorithm with non-convex convergence guarantees even with non-i.i.d. client participation. We will cite and discuss these works in our updated paper.\n\n2. **Different heterogeneity assumptions.** We addressed this point in the general response, but we can further touch on it here. The main point is that we do not use any heterogeneity assumption in our paper. The only reason that the condition $\\lVert \\nabla f_i(x) - \\nabla f(x) \\rVert \\leq \\kappa$ is stated in our table is that this assumption is used by the baselines we compare in Table 1. Our analysis avoids any heterogeneity assumption because our use of control variates eliminates the need for one (this is also the case in the SCAFFOLD analysis). We agree that bounded gradient dissimilarity is less restrictive than uniformly bounded heterogeneity, but even less restrictive is no heterogeneity assumption at all!\n\n3. **Complexity of assumption 2.** We agree that Assumption 2 is somewhat dense, although we have already included in Section 3.2 a detailed discussion of different sampling schemes which satisfy assumption 2. If you have additional suggestions to improve the clarity of this assumption, please let us know. \n\n4. **Explanation of hyperparameters.** As stated on Line 269, all of the hyperparameters for every baseline are tuned with grid search. The search ranges and final values for each hyperparameter are given in Table 2 of Appendix D. To evaluate each hyperparameter combination in the grid, we run the training setup described in the main body (with only one random seed instead of five) and choose the hyperparameter combination that reaches the smallest training loss by the end of training. After each hyperparameter is tuned, we evaluated each algorithm over five random seeds.\n\n5. **Recovering SCAFFOLD's rate.** You are correct that our convergence rate as a slightly worse dependence on $N/S$ than SCAFFOLD. We pointed this out in Section 4.3 (line 223), and we provide a detailed explanation of this discrepancy in Appendix E. Essentially, there is a potential small issue in the analysis of SCAFFOLD for the case of partial participation. Instead of repeating this issue in our analysis, we accept a slightly worse dependence on $N/S$. It is likely that the issue can be fixed to recover the $(N/S)^{2/3}$ rate for both their algorithm and ours, but this is not the focus of our paper. In this paper, we focused on achieving convergence under periodic participation with reduced communication, linear speedup, and resilience to heterogeneity, and by doing so we have improved over previous work. If the $N/S$ dependence is an important issue to you, please read our discussion of the details, which is 1 page in Appendix E (lines 807-829).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uF7HAIxbLc", "reviewer": "Reviewer_ewwQ", "summary": "This work addresses the limitations of federated learning under realistic client participation patterns, specifically focusing on nonconvex optimization. The proposed algorithm, Amplified SCAFFOLD, achieves linear speedup, reduced communication, and resilience to data heterogeneity without requiring strong assumptions. Compared to previous methods, it significantly reduces the required communication rounds for finding a $\\epsilon$-stationary point in cyclic participation scenarios. The analysis provides tighter guarantees, and experimental results on both synthetic and real-world data demonstrate the algorithm's effectiveness.", "questions": "1.) While setting up the problem in section 3, I think having a notation table would have been beneficial. Because there are a ton of notations in the paper, many of which are defined later.\n\n2.) In Assumption 1.(a) what is the $\\Delta$ and what is the intuitive meaning behind this assumption? Does it have anything to do with the non-negativity of the loss function?\n\n3.) Typo: In line 133, the authors have mentioned $\\bar{q}_{r0}$.\n\n4.) Do the authors use the assumption of data heterogeneity mentioned in Table 1 in their proof? If not, then how did they avoid to use it?\n\n5.) As the authors say, the work is a culmination of algorithmic components from references [14] and [34] (references from the paper), and I agree that analysis is by no means trivial. So, combining the algorithmic component of Amplified FedAvg paper and Fedprox would also provide a better result. Can this be checked experimentally, or did the authors observe anything?\n\n6.) Since the papers signify the main contribution to achieving communication efficiency, I would also like to see some experiments with algorithms like FedAdam and FedYogi. Along similar lines of work, in [1] (check below), the authors showed that momentum-based methods can reduce client drift and perform better than methods like SCAFFOLD for full participation.\n\n7.) Did the authors also check the efficacy of the proposed algorithm with different participation strategies, as mentioned in the paper?\n\n\n[1] Cheng, Ziheng, et al. \"Momentum benefits non-iid federated learning simply and provably.\" arXiv preprint arXiv:2306.16504 (2023).", "limitations": "Yes, the authors have mentioned the limitations of the work.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.) The paper is well written\n2.) There is extensive theoretical analysis\n3.) Supported by experiments on baselines.", "weaknesses": "See the questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful suggestions. We have responded to your thoughts and questions below.\n\nQuestions:\n\n1\\. **Table of notation.** Thank you for this suggestion. We agree that it would make the presentation more clear and we will provide a table of notation in the updated version.\n\n2\\. **Meaning of Assumption 1(a).** As we said in the general repsonse, our Assumption 1(a) actually contains a typo: the correct version should say $f(x_0) - \\min_{x \\in \\mathbb{R}^d} f(x) \\leq \\Delta$, which is a standard condition in convergence proofs.\n\n3\\. **Typo on line 133.** Thank you for pointing this out. The variable $\\bar{q}_{r_0}^i$ first appears on Line 132, and immediately after we refer to its definition in Algorithm 1, but the reference should point to line 17 of Algorithm 1, not line 18.\n\n4\\. **Usage of heterogeneity assumption.** Since multiple reviewers addressed this point, we discussed it in our general response. Our main message is that we do not use any heterogeneity assumption in the proof, because the necessity of this assumption is completely eliminated by the use of control variates. This circumstance is the same as in SCAFFOLD: the analysis of SCAFFOLD does not require a heterogeneity assumption, but such an assumption is referenced in their paper because it is used by baselines.\n\n5\\. and 6\\. **Comparison with additional baselines.** In your review, you requested that we compare against additional baselines such as FedAdam, FedYogi, FedAvg-M, and the combination of Amplified FedAvg with FedProx. We agree that these are important baselines to consider, so we have evaluated all four of these baselines in the experimental settings of the main paper. The results are thoroughly discussed in the general response, and the loss curves are shown in Figures 1 and 2, but we highlight the main findings here.\n\nFor both FashionMNIST and CIFAR-10, **Amplified SCAFFOLD achieves the best training loss and testing accuracy among all baselines, including the four new baselines.** In general, FedAdam and FedYogi were competitive, outperforming every algorithm except for Amplified SCAFFOLD for CIFAR-10, and every algorithm except for Amplified SCAFFOLD and SCAFFOLD for FashionMNIST. Ultimately these algorithms fell short of Amplified SCAFFOLD, which is consistent with the fact that these baselines were designed for i.i.d. client participation, whereas Amplified SCAFFOLD has convergence guarantees under periodic participation.\n\nIn response to your question about combining Amplified FedAvg with FedProx, we note that Amplified FedProx did not perform better than Amplified FedAvg. This means that combining amplified updates with control variates is much more effective than combining amplified updates with FedProx regularization.\n\nPlease see the general response for a detailed discussion of this additional experiment.\n\n7\\. **Experiments with different participation strategies.** In response to your question about different participation strategies, we have included an additional experiment under a new non-i.i.d. participation pattern. We refer to this pattern as Stochastic Cyclic Availability (SCA), and we believe that it captures user device availability which is both periodic and unreliable. We thoroughly discussed the details of this participation pattern and the results of the experiment in the general response, and we highlight the results below. Figure 3 of the 1-page PDF shows the loss curves for all algorithms (including the four additional baselines) for CIFAR-10 under SCA participation.\n\nFrom Figure 3, we conclude that **Amplified SCAFFOLD outperforms all baselines under a second non-i.i.d. participation pattern**. Amplified SCAFFOLD reaches the lowest training loss and highest training accuracy out of all algorithms, and even reaches a slightly lower training loss under SCA participation than cyclic participation (shown in Figure 2). We believe that this experiment bolsters the empirical validation of our proposed algorithm, demonstrating that Amplified SCAFFOLD performs well under multiple non-i.i.d. participation patterns.\n\nPlease see the general response for the full details of this experiment.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k1AoNAvFPP", "reviewer": "Reviewer_bD8t", "summary": "The paper proposes a new algorithm named Amplified SCAFFOLD for federated learning in environments with periodic client participation and heterogeneous data. The authors address the realistic setting where clients (e.g., mobile devices) are not always available for participation. The proposed algorithm aims to achieve linear speedup, reduced communication rounds, and resilience to data heterogeneity under non-convex optimization. The paper includes theoretical analysis demonstrating the benefits of Amplified SCAFFOLD over existing methods and provides experimental results to validate the proposed approach.", "questions": "Can the authors explain from a technical point of view how their amplified SCAFFOLD algorithm is robust against data heterogeneity? I can see that the weights of the participating customers are amplified, but no other mechanism to mitigate data heterogeneity has been identified.", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The introduction of Amplified SCAFFOLD is well-motivated. The algorithm's design to handle non-i.i.d. client participation and its ability to provide tighter guarantees than previous work is well-supported by their theoretical analysis.\n2. The experiments with synthetic and real-world data (e.g., Fashion-MNIST and CIFAR-10) demonstrate the algorithm's effectiveness and robustness under various conditions.", "weaknesses": "1. Some assumption is too strong, i.e., bounded objective function gap $f(\\\\mathbf{x}) - f\\_{\\\\min}$ for all $\\\\mathbf{x} \\\\in \\\\mathbb{R}^d$ in assumption 1(a), which is not satisfied for coercive objective function, a commonly used condition in optimization. In addition, previous works [1,2] only utilized the gap between the initial point and the optimum $f(\\\\mathbf{x}_0) - f\\_{\\\\min}$.\n2. While the paper provides comparisons with several baselines, it would be helpful to see related works with more recent state-of-the-art methods that might also address similar challenges, e.g., [3].\n\n\n[1]. Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., & Suresh, A. T. (2020). Scaffold: Stochastic controlled averaging for federated learning. International conference on machine learning.\n\n[2]. Wang, S., & Ji, M. (2022). A unified analysis of federated learning with arbitrary client participation. Advances in Neural Information Processing Systems.\n\n[3]. Crawshaw, M., Bao, Y., & Liu, M. (2024). Federated learning with client subsampling, data heterogeneity, and unbounded smoothness: A new algorithm and lower bounds. Advances in Neural Information Processing Systems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for you effort in reviewing our paper. Below we have responded to your thoughts and answered your questions.\n\nWeaknesses:\n\n1. **Meaning of Assumption 1(a).** We addressed this point in the general response: our Assumption 1(a) contains a typo. Actually, the correct version of our Assumption 1(a) matches the references you mentioned, and we will fix this typo in the updated version.\n\n2. **Comparison against similar methods** In your review, you wrote \"it would be helpful to see related works with more recent state-of-the-art methods that might also address similar challenges, e.g. [3]\". From the empirical perspective, we included additional experiments to compare against several baselines; see \\#1 of the general response for more information. From the theoretical perspective, we are not aware of additional works not cited in our paper that achieve convergence guarantees under non-i.i.d. client participation. The reference you mentioned [3] provides an algorithm for FL under $(L_0, L_1)$-smoothness with i.i.d. client sampling, which is an orthogonal problem to the non-i.i.d. client participation which motivates our paper. In fact, in the smooth setting (i.e. $L_1 = 0$), the algorithm of [3] degenerates to the SCAFFOLD algorithm with i.i.d. client sampling, which we have already compared against. We can refer to this work in the updated version of our paper, and discuss its relation to our work.\n\nQuestions:\n\n1. **How does Amplified SCAFFOLD avoid heterogeneity?** The main algorithmic component that creates robustness against heterogeneity is the joint effect of control variates with amplified updates. We use the control variates to modify the local update for each client in order to approximate an update on the global objective (see Line 8 of Algorithm 1). Our algorithm combines these control variates with amplified updates across windows of multiple rounds; see Section 4.1 for a description of these algorithmic components. Section 4.2 presents convergence guarantees for this algorithm (reduced communication, robustness to heterogeneity, linear speedup), and Section 4.3 explores the implications for various non-i.i.d. participation patterns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QZjmg7bWmE", "reviewer": "Reviewer_2Xef", "summary": "This paper introduces Amplified SCAFFOLD, which is an optimization algorithm for federated learning under periodic client participation. The authors prove that it achieves reduced communication cost, linear speedup, and resilience to data heterogeneity. Numerical experiments are provided to evaluate the performance of Amplified SCAFFOLD.", "questions": "1. For cycle participation, why are the subsets equally sized? Can they have different sizes? In addition, can the clients sampled with replacement?\n2. In the experiments, $\\bar{K}$ is chosen to be 5. What about the other choices? What is its influence?", "limitations": "As the authors stated, this paper only considers periodic client participation. However, this may not always be true in practice. Clients may arbitrarily join and leave the training, and they may perform different numbers of local steps in each round.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "For federated learning under periodic client participation, Amplified SCAFFOLD is proposed and proven to exhibit reduced communication, linear speedup, and resilience to data heterogeneity. Experimental results show that Amplified SCAFFOLD converges faster than baseline algorithms and is robust to changes in data heterogeneity and the number of participating clients.", "weaknesses": "1. It would be better to provide a detailed description of the algorithm rather than just an overview.\n2. Except for the synthetic data, the experiments are based only on two image datasets (Fashion-MNIST and CIFAR-10) with classification tasks. Adding more experiments would better demonstrate the performance of Amplified SCAFFOLD.\n\nMinor:\n1. Line 60-61: Delete \"non-uniform average of\".\n2. Line 99: Assumption 1 (a) is not precise. It should be for all $y$, not for all $x,y$.\n3. Line 110: $P$ first appears without explanation.\n4. Line 145: Delete \"is\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments on our paper. Below we have responded to your comments and questions.\n\nWeaknesses:\n\n1. **Detailed description of the algorithm.** Thank you for the feedback on our presentation. Section 4.1 is meant to describe the key algorithmic components of Amplified Scaffold, while the concrete definition of the algorithm is left to pseudocode in Algorithm 1. To improve the clarity of the updated version, we can include a detailed description of the algorithm, such as:\n\n    Amplified SCAFFOLD has a similar high-level structure as many FL optimization algorithms: in each round, participating clients individually perform local steps without communication (line 8), then aggregate their updates to the global model (line 12). However, the local steps (line 8) include the control variates $G_{r_0}^i$ and $G_{r_0}$, which are used to modify the local steps in order to approximate the gradient of the global objective. The control variate $G_{r_0}^i$ is the average of stochastic gradients seen by client $i$, but the average is not just taken over the last round: instead, the control variates are computed over windows of $P$ rounds (lines 17-21), in order to ensure that all clients are equally represented (in expectation). The other deviation from the conventional structure of FL algorithms is in the amplified updates (line 15). Over each window of $P$ rounds, the updates from each round are accumulated in the variable $u$. At the end of each window, all clients will have participated with equal frequency (in expectation), so $u$ should contain information from all clients. We then use $u$ to update the global model with a potentially large multiplier $\\gamma$ (line 15), leveraging the fact that $u$ contains global information. Together, these two components allow Amplified SCAFFOLD to simultaneously handle non-i.i.d. client participation and heterogeneous objectives.\n\n    Please let us know if this explanation will improve the clarity of our presentation.\n\n2. **Additional experiments.** In response to your comment about additional experiments, and comments from other reviewers, we have made two additions to the experiments of our submission. First, we added four new baselines (FedAdam, FedYogi, FedAvg-M, and Amplified FedAvg + FedProx) to the evaluation of FashionMNIST and CIFAR-10. Second, we evaluated each algorithm (including these new baselines) under a new non-i.i.d. participation pattern, which models user device availability that is both periodic and unreliable. Both of these experiments are described in detail in the general response, and the loss curves are shown in Figures 1-3 of the 1-page PDF. Here, we highlight the main findings.\n\n    The new baselines FedAdam and FedYogi are competitive for both FashionMNIST and CIFAR-10, but **Amplified SCAFFOLD still maintains the best performance in terms of training loss and testing accuracy across all baselines.**. This is consistent with the fact that FedAdam and FedYogi were designed for i.i.d. client sampling, whereas Amplified SCAFFOLD enjoys convergence guarantees under periodic participation.\n\n    We also evaluate all algorithms under a non-i.i.d. participation pattern which we refer to as Stochastic Client Availability (SCA). On CIFAR-10 with SCA participation, Amplified SCAFFOLD again reaches the best training loss and testing accuracy, showing that **Amplified SCAFFOLD performs well under multiple non-i.i.d. participation patterns**.\n\nQuestions:\n\n1. **Variations on group subsampling.** In your review, you asked \"For cycle participation, why are the subsets equally sized? Can they have different sizes?\" In our paper and in related works [4, 34], the subsets in cyclic participation are usually equally sized for simplicity. However, this is not a requirement. In fact, for our additional experiment (see general response \\#2), the number of available clients randomly sampled and changes throughout training. This participation pattern is more flexible than cyclic participation, and may better model the unpredictability of real-life client devices.\n\n    Also, you asked \"In addition, can the clients sampled with replacement?\" If we understand your question correctly, you are asking whether the same client can be sampled between two consecutive rounds. If so, the answer is yes. At every round, $S$ clients are sampled, and these clients are not removed from the set of available clients for the next round. In other words, the sampling mechanism does not cycle through all clients before return to previous clients.\n\n2. **Effect of $\\bar{K}$.** In your review, you asked \"In the experiments, $\\bar{K}$ is chosen to be 5. What about the other choices? What is its influence?\" We chose $\\bar{K} = 5$ following [34], but this parameter can vary. One way to understand the role of this parameter is notice that $\\bar{K} = 1$ corresponds to full client availability, while large values of $\\bar{K}$ mean that there are many small groups of clients which are usually not available. Therefore, larger values of $\\bar{K}$ means that participation is in some sense ``further from i.i.d.\". We expect that larger $\\bar{K}$ means that the optimization problem is more difficult, and will require more communication rounds, which aligns with the communication cost of Amplified SCAFFOLD in the last row of Table 1.\n\n    In our experiments, data heterogeneity is created by allocating different data distributions to different clients. With $N=250$ clients and $C=10$ classes, the first 25 clients have a majority of their data from class 1, the next 25 clients have a majority of class 2, etc. The choice $\\bar{K} = 5$ yields 50 clients per group, so that each group contains clients with a majority label from two different classes. We believe that this is a good intermediate value for $\\bar{K}$: it is not so small that we are too close to the i.i.d. regime ($\\bar{K} = 1$), but it is not so large that one class out of ten dominates training in each round.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you to all of the reviewers for your time and effort in the review process. Here we describe additional experimental results that we have added to address the reviewer comments, and give answers to common questions. We have also responded individually to each review below.

1. **Experiments with additional baselines.** For the FashionMNIST and CIFAR-10 experiments from the original paper, we have evaluated four additional baselines: FedAdam [28], FedYogi [28], FedAvg-M [Cheng, 2023] (see citation below), and Amplified FedAvg + FedProx [34, 19]. The results are shown in Figures 1 and 2 of the 1-page PDF, where you can see that **Amplified SCAFFOLD maintains superior performance against all of the added baselines in terms of both training loss and testing accuracy.**

    We tuned the hyperparameters of all baselines according to the hyperparameter ranges suggested in the original paper of each algorithm, and we allow the same compute budget for tuning each baseline as we did for tuning the algorithms in the original paper, in terms of the total number of hyperparameter combinations evaluated. Also, the results are averaged over five random seeds.

    For FashionMNIST: FedAdam and FedYogi reach moderate training loss quickly, but are soon overtaken by Amplified SCAFFOLD and later by SCAFFOLD. FedAvg-M exhibits a minor advantage over FedAvg, but performs about the same as Amplified FedAvg. Amplified FedProx (i.e. Amplified FedAvg with FedProx regularization) performs nearly identically to Amplified FedAvg.

    For CIFAR-10: FedAdam is more competitive, but is still outperformed by Amplified SCAFFOLD. FedYogi and FedAvg-M are further behind, though both still outperform SCAFFOLD. Amplified FedProx is again nearly identical to Amplified FedAvg.

    These new experiments demonstrate that **Amplified SCAFFOLD outperforms strong empirical baselines (FedAdam, FedYogi) under cyclic client participation**, reinforcing the empirical validation of our algorithm. This performance is consistent with the fact that Amplified SCAFFOLD has convergence guarantees under periodic participation, while FedAdam and FedYogi were not designed for settings beyond i.i.d. client sampling.

2. **Experiments with different participation strategies.** We also added an evaluation under another non-i.i.d. participation pattern. Figure 3 of the 1-page PDF shows the evaluation of all baselines (including the additional baselines from \#1) for CIFAR-10 under this new participation pattern, which is described in the next paragraph. The results show that **Amplified SCAFFOLD outperforms all baselines under a second non-i.i.d. participation pattern**.

    We refer to this new pattern as Stochastic Cyclic Availability (SCA), and it models device availability which is both periodic and unreliable. Similarly to cyclic participation, the set of clients is divided into $\bar{K}$ groups, and at each round one group is deemed the "active" group, while the others are inactive. Unlike cyclic participation, in SCA not every client in the active group is always available: Instead, when a group becomes active, the clients in that group become available for sampling with probability $80\%$, while clients in inactive groups have probability $5\%$ to be available for participation. The active group changes every $g$ rounds. This stochastic availability models the real-life situation where a client device can be unavailable at a time of day when it is usually available, or vice versa. In this way, SCA is more flexible than cyclic participation and better captures the unreliability of client devices. Lastly, we reused the remaining settings ($g, \bar{K}, I$, etc.) and the tuned hyperparameters for each baseline from the CIFAR-10 experiment under cyclic participation. Again, we average each algorithm's performance over five random seeds.

    Results for CIFAR-10 under SCA participation are shown in Figure 3. Again, **Amplified SCAFFOLD outperforms all baselines under SCA participation**. The relative performance of each baseline is similar, with FedAdam staying competitive with Amplified SCAFFOLD, followed by FedYogi and FedAvg-M. The remainder of the baselines have significantly worse performance, and again Amplified FedAvg has not benefitted by adding FedProx regularization.

    This new experiment shows that **Amplified SCAFFOLD performs well in other non-i.i.d. participation patterns beyond cyclic participation.** We will include these new results in the updated version of the paper.

3. **Meaning of assumption 1(a).** Several reviewers pointed out that Assumption 1(a) is too strong or counterintuitive. This confusion is actually just due to a typo in the statement of Assumption 1(a). The correct version should say that $f(x_0) - \min_{x \in \mathbb{R}^d} f(x) \leq \Delta$, which is standard for convergence proofs.

4. **Heterogeneity assumptions.** Two reviewers asked whether the heterogeneity assumption $\lVert \nabla f_i(x) - \nabla f(x) \rVert \leq \kappa$ is used for our proof, and whether this assumption is reasonable in our setting. In short, our proof does not use this assumption or any assumption on the heterogeneity; as stated in Theorem 1, the only assumptions we need are Assumption 1, Assumption 2, and Equations (1) and (2) (both only depend on the client sampling distribution). The heterogeneity assumption with $\kappa$ is only stated in Table 1 because it is used by several baselines. Similarly to SCAFFOLD in the case of i.i.d. sampling, we can avoid this assumption through the use of control variates to approximate the global gradient at each local step. 

[Cheng, 2023] Cheng, Ziheng, et al. "Momentum Benefits Non-iid Federated Learning Simply and Provably." The Twelfth International Conference on Learning Representations.

Meta-review: The authors examine realistic partial participation scenarios in federated learning, including cyclic client participation and arbitrary client participation patterns. The focus is on the non-convex optimization setting which is common in practical applications but challenging to address. To tackle this, they introduce a novel method called Amplified Scaffold, designed to effectively correct client drift --- a common issue where clients' updates diverge from the global model. The Amplified Scaffold method builds upon existing techniques but enhances their effectiveness in this more complex setting. The authors not only provide theoretical convergence guarantees, ensuring that their method is mathematically sound, but also back up their claims with extensive experimental results. These experiments demonstrate the practical effectiveness of Amplified Scaffold in various scenarios, highlighting its potential for real-world applications.

All reviewers proposed the paper to be accepted, with scores 5, 6, 6, 6. The work was praised in several ways, including:
- the problem and method are well motivated
- the theoretical results obtained look adequate, and align with expectations
- the authors consider a wide range of settings and sampling schemes, which makes their work relevant to a broad audience
- extensive experimental testing
- the text is well written

The observed weaknesses were considered minor in comparison to the strengths, and some were addressed in the rebuttal (e.g., insufficient discussion of related work), and the previously lower scores were increased.
Decision: Accept (poster)