Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis

Authors: michael  crawshaw
mingrui  liu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 22:47:20

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.

Main paper: 
 introduction: 
 Federated learning (FL) [26, 20, 15, 51] is a distributed learning paradigm that emphasizes client privacy [27, 40, 28] , limited communication [18, 24] , and data heterogeneity across clients [16, 53] . FL has attracted attention in recent years due to the ability to leverage data and compute from user devices while respecting privacy [47, 8] . For large-scale FL, it is common to limit the number of simultaneously participating devices, and many works do so by assuming that a random subset of clients can be sampled independently at each round [26, 2, 48, 21, 37] . 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 [14, 30] . In particular, if client availability is correlated with geographical location (e.g. mobile phones charging at night), then Table 1 : Communication and computation complexity of various methods to find an ϵ-stationary point for L-smooth, non-convex objectives. N : number of clients, κ: data heterogeneity sup x ∥∇f i (x) -∇f (x)∥ ≤ κ. 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 O(ϵ -4 ). Derivation of complexities for Amplified FedAvg can be found in Appendix C.• We introduce Amplified SCAFFOLD, an optimization algorithm for federated learning under non-i.i.d. client participation. Our convergence analysis demonstrates its computational and communication efficiency: Amplified SCAFFOLD exhibits reduced communication, linear speedup, and is unaffected by data heterogeneity. These guarantees are achieved with a tighter analysis than used in previous work [38] , with a 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(κ 2 ϵ -4 ) to O(ϵ -2 ).• 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 is outlined as follows. We discuss related work in Section 2, and Section 3 provides a formal specification of the optimization problem. Amplified SCAFFOLD is introduced and theoretically analyzed in Section 4, and we provide experiments in Section 5. We conclude with Section 6. 
related work: 
 Federated Optimization. FedAvg [26] characterizes partial client participation and local updates in each round. FedAvg was analyzed in the full participation setting [34, 36, 48, 49, 42, 41, 17, 11] .Other federated optimization algorithms aim to improve communication efficiency [31, 50] and tackle data heterogeneity [21, 16] . The analysis of FL optimization algorithms typically either assumes full client participation or partial client participation where clients are sampled uniformly randomly [45, 37, 16, 22, 42] . [29] 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 [9] , where they propose "pluralistic" solutions instead of learning a single model for all clients. There is a recent line of work considering various participation patterns, including client selection [10, 3, 32] biased participation [33, 5, 6] , independent participation across rounds [16, 21, 22] , unbiased participation [35, 12] , bounded rounds of unavailability [44, 13, 46] , asynchronous participation [23, 1] , cyclic participation [7] , and arbitrary participation [38, 39] . 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.See Appendix F for a detailed discussion comparing our results with a small number of closely related baselines. 
problem setup: 
 We consider a federated learning problem with N clients, with the overall objectivemin x∈R d f (x) := 1 N N i=1 f i (x) ,where each f i : R d → R is the local objective of one client. We consider the stochastic optimization problem, so that f i (x) = E ξ∼Di [F (x; ξ)], and the optimization algorithm can access F i (x; ξ) and ∇F i (x; ξ) for individual values of ξ. We make the following assumptions about the objectives: Assumption 1. (a) f (x 0 ) -min x∈R d f (x) ≤ ∆. (b) Each f i is L-smooth, i.e., ∥∇f i (x) -∇f i (y)∥ ≤ L∥x -y∥ for all x, y ∈ R d . (c) The stochastic gradient has variance σ 2 , i.e., E ξ∼Di [∥∇F i (x; ξ) -∇f i (x)∥ 2 ] ≤ σ 2 for all x ∈ R d .Since each f i may be non-convex, we consider the problem of finding an ϵ-stationary point of f , that is, a point x ∈ R d such that ∥∇f (x)∥ ≤ ϵ.We consider a federated learning framework consisting of R rounds. For any round r ∈ {0, . . . , R-1} and client i ∈ [N ], the availability of client i at round r is a random variable q i r , following the arbitrary participation framework of [38] . If q i r = 0, then client i may not participate during round i. For example, under the conventional i.i.d. sampling of clients, at each round r a subset of clients S r ⊂ [N ] is sampled uniformly without replacement, and the weights are set as q i r = 1{i∈Sr} S .For some P ∈ N, let Q r0 be the filtration generated by {q i r : r 0 ≤ r < r 0 + P, i ∈ [N ]}, let Q be the filtration generated by Q 0 , . . . , Q R-P , and let G be the filtration generated by {ξ i r,k : 0 ≤ r < R, 0 ≤ k < I, i ∈ [N ]}, where ξ i r,k is the random sampling of the stochastic gradient of round r, step k, client i. We make the following assumptions about the participation distribution.Assumption 2. For all r ∈ {0, . . . , R -1}: (a) N i=1 q i r = 1 and N i=1 (q i r ) 2 ≤ ρ 2 . (b) The distribution of {q i r } is unbiased across clients over every window of P rounds, i.e., E Qr 0 [ 1 P (m+1)P -1 r=mP q i r ] = 1/N for every m < R/P and i ∈ [N ]. (c) Each client has a nonzero probability of being sampled over every window of P rounds, i.e., P Qr 0 ( 1 P (m+1)P -1 r=mP q i r > 0) > p sample for every m < R/P and i ∈ [N ]. (d) Q and G are independent.For each round, Assumption 2(a) enforces that the participation weights q i r are normalized to sum to 1, and characterizes the spread of participation weights across clients with the constant ρ 2 . Assumption 2(b) requires that the set of rounds can be partitioned into windows of length P within which clients are expected to participate with equal frequency. Lastly, Assumption 2(c) enforces that within each window, for each client the probability of being sampled is nonzero. Conventional i.i.d client sampling satisfies Assumption 2 with ρ = S -1/2 , P = 1, and p sample = S/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 2(b)-(c) are taken only over Q r0 . Therefore, the mean participation weight in Assumption 2(b) may itself be a random variable if client participation at some rounds is dependent on the outcome of participation in previous rounds. Similarly, the sampling probability in Assumption 2(c) may be a random variable. For the participation patterns considered in the next section, Assumption 2 is satisfied even when client sampling is not independent across rounds.Regularized Participation We say that client participation is regularized [38] if qi r0 = 1 N almost surely for all r 0 and i, where qi r0 is defined on Line 18 of Algorithm 1 as the participation of client i averaged over rounds r 0 , . . . , r 0 + P -1. In this case, Assumption 2 is satisfied with p sample = 1, while P and ρ 2 are parameters of the participation pattern. Regularized participation is a relatively strong constraint, since every client must participate within each window, which may not be practical. However, it is flexible in that there is no constraint on how clients participate within each window. Regularized participation was also considered for strongly convex objectives [25] .Cyclic Participation Following the CyCP framework [7] , 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 q i r = 1/S. All other clients are assigned q i r = 0. Cyclic participation satisfies Assumption 2 with P = K, ρ = S -1/2 , and p sample = S K/N . Notice that i.i.d. client sampling is the special case where K = 1.Cyclic participation can model a situation where each client group is available at a 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 PL objectives [7] , although this analysis is not applicable in our setting, which uses general non-convex objectives. client server 
algorithm and analysis: 
 In this section, we present Amplified SCAFFOLD, our algorithm to solve the FL problem described in Section 3. 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.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 1, the variable u holds a weighted average of local updates to client models, weighted by client participation. Every P rounds, the global model is updated in the direction u scaled by the amplification factor γ. Informally, the direction u includes information from all clients with equal representation, according to Assumption 2(b). Similar amplified updates are used in Amplified FedAvg [38] .Control variates for heterogeneous federated learning were first introduced by SCAFFOLD [16] . However, SCAFFOLD-style control variates are updated every time a 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 to others. To deal with this issue, Amplified SCAFFOLD updates control variates based on information accumulated over a window of P rounds, which enforces equal representation of all clients in expectation, according to Assumption 2(b).Comparison with [16, 38] Although the two algorithmic components of Amplified SCAFFOLD individually appear in previous work [16, 38] , we emphasize that our complexity results cannot be achieved by simply combining the analyses of these two works. The analysis of [38] requires ϵ -4 communication cost due to their treatment of the randomness in client participation. Here, we present a tighter analysis with ϵ -2 cost from a 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.Let x = xmP , where m is sampled uniformly from {0, . . . , R/P -1}, and let r 0 ∈ {0, P, . . . , R/P }.i r0 = 1 N N j=1 1{q j r 0 >0} P qj r 0 r0+P -1 s=r0q i s q j s and v i r0 = qi r0 -1 N . Informally, w i r0 represents the "non-uniformity" of the client sampling distribution. We also consider a variable Λ i r0 that depends only on the client sampling distribution and characterizes the sample size from which G i r0 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.EQUATIONEQUATIONTheorem 1. Suppose that Assumptions 1 and 2 hold, and that Equation E[∥∇f ( x)∥ 2 ] ≤ O ∆ γηIR + γηLρ 2 + η 2 L 2 IP σ 2 .Corollary 1. For any ϵ > 0 and I ≥ 1, there exist choices of γ and η such thatE[∥∇f ( x)∥ 2 ] ≤ O(ϵ 2 ) as long as R ≥ O ∆Lρ 2 σ 2 Iϵ 4 + ∆LP psampleϵ 2 .The complexity of Amplified SCAFFOLD has several important properties:Reduced Communication By choosing I = Θ(∆ρ 2 σ 2 p sample P -1 ϵ -2 ), Amplified SCAFFOLD has communication complexity R = O(LP p -1 sample ϵ -2 ), which improves upon the ϵ -4 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.The iterations RI and the number of communications R are unaffected by heterogeneity, which is not achieved for periodic participation by any existing work [38, 7] .Linear Speedup The number of iterations RI = O(∆Lρ 2 σ 2 ϵ -4 ) will exhibit linear speedup in the number of clients through the term ρ 2 , depending on the client participation pattern.The results from Section 4.2 apply under any participation pattern that satisfies Assumption 2, Equation 1, and Equation 2, 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 1 , and these results can be obtained by plugging ρ 2 , P , and p sample into Corollary 1, together with a choice of I as described in Section 4.2. The derivations of each result below are given in Appendix B.Regularized Participation Recall that regularized participation satisfies Assumption 2 with p sample = 1, and P , ρ 2 are parameters of the participation pattern. Also, under regularized participation, w i r0 = qi r0 = 1/N almost surely, so that E[w i r0 ] = 1/N ≤ P 2 /N and v i r0 = 0. Therefore Equation 1 and Equation 2 are satisfied. Plugging p sample = 1 into Corollary 1 yieldsR = O LP ϵ -2 , RI = O ∆Lρ 2 σ 2 ϵ -4 .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 is Amplified FedAvg [38] . However, as seen in Table 1 , the communication complexity of Amplified FedAvg has order ϵ -4 in terms of ϵ and suffers from a κ 2 dependence.Cyclic Participation Recall that cyclic participation satisfies Assumption 2 with P = K, ρ = S -1/2 , and p sample = S/N . Also, E[w i r0 ] = S/N 2 ≤ P 2 /N and E[(v i r0 ) 2 Λ i r0 ] = ρ 2 , so that Equation 1 and Equation 2 are satisfied. Based on the above parameter values, the resulting complexities areR = O L K ϵ 2 N S , RI = O ∆Lσ 2 Sϵ 4 .Again, Amplified SCAFFOLD achieves reduced communication, linear speedup, and resilience to heterogeneity. Amplified FedAvg [38] is the only existing algorithm with theoretical guarantees in this setting, but it fails to achieve resilience to heterogeneity or reduce communication cost outside of the trivial case of full participation ( K = 1, S = N ). Also, even for the setting of PL-functions, the convergence rate of FedAvg under cyclic participation from [7] 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, Amplified FedAvg fails to recover the reduced communication usually achieved under i.i.d. participation, such as by SCAFFOLD [16] . In fact, Amplified FedAvg fails to recover the communication cost of FedAvg under i.i.d. participation, requiring an additional factor of LN . The larger communication cost of Amplified FedAvg is a result of its convergence analysis, which does not leverage the property of unbiased participation (Assumption 2(b)) during the analysis, and requires P = O(ϵ -2 ) in order to converge (see Appendix C for more details). In contrast, Amplified SCAFFOLD succeeds in recovering the results of SCAFFOLD under i.i.d. participation, with only a slightly worse dependence of R on N/S. This difference in the order of N S is due to a potential small issue in the analysis of SCAFFOLD, which we intentionally avoided by accepting a slightly worse dependence on N S . We provide a detailed discussion of the N/S dependence in Appendix F.The main challenges for demonstrating convergence are (1) simultaneously 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 [38] subverts (1) by conditioning on Q throughout the entire analysis. However, this eliminates the possibility of utilizing the condition E[q i r0 ] = 1/N , and ultimately incurs a dependence on the data heterogeneity (see the term δ2 (P ) in Theorem 3.1 of [38] ). Instead, we take expectation over both sources of randomness throughout the analysis, which requires a careful treatment of each iterate's dependence, and enables communication reduction. For (2) , previous analysis of federated algorithms with control variates [16] recursively bounds the error of control variates between consecutive rounds. However, this recursion crucially depends on i.i.d. client participation. We extend this analysis to our setting, establishing a recursion over the control variate error between consecutive windows of P rounds. Establishing this recursion under non-i.i.d. participation involves a non-uniform average of non-uniform averages of error terms, which we handle by invoking the regularity conditions stated in Equation 1 and Equation 2.Using smoothness of f , the objective function decrease f ( xr0+P ) -f ( xr0 ) is upper bounded by ⟨∇f ( xr0 ), xr0+P -xr0 ⟩ + L 2 ∥ xr0+P -xr0 ∥ 2 .Letting xr,k = N i=1 q i r x i r,k be a weighted average of local models, the sum of the previous inner product and quadratic terms can be bounded by -γηIP ∥∇f ( xr0 )∥ 2 , plus standard noise terms, the additional "drift" termsDr,k = N i=1 q i r x i r,k -xr,k 2 Mr,k = ∥ xr,k -xr0 ∥ 2 ,and control variate errors C i r0 = ∥∇f i ( xr0 ) -G i r0 ∥ 2 .N i=1 q i r E[C i r0 |Q].Denoting the average control variate errorC r0 = 1 N N i=1 C i r0 , we want to bound E[C r0+P ] in terms of E[C r0 ]. C r0+P can be decomposed into drift terms, but the result is a non-uniform average:r0+P -1 s=r0 I-1 k=0 q i s (D s,k + M s,k ).Since the bound for each M s,k + D s,k from Lemma 1 involves a non-uniform average over C i r0 , the resulting bound of C r0+P involves a non-uniform average of non-uniform averages of C i r0 , instead of the uniform average C r0 . The regularity conditions in Equation 1 and Equation 2 allow us to bound this nested non-uniform average by a uniform average, which finishes the recursion.Putting everything together, we obtain the descent inequalityE[ fr0+P ] ≤ E[ fr0 ] -γηIP E ∥∇f ( xr0 )∥ 2 + γηIP (γηLρ 2 + η 2 L 2 IP )σ 2 ,where fr0 := f ( xr0+P ) + Φ(r 0 + P ) and Φ is a potential function that depends on the control variate errors. Theorem 1 is then obtained by averaging over r 0 and isolating the gradient. 
experiments: 
 We experimentally validate our algorithm for non-i.i.d client participation under three settings: minimizing a synthetic function, logistic regression for Fashion-MNIST1 [43] , and training a CNN for CIFAR-10 [19] . 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 of client groups in cyclic participation.All of our experiments utilize a non-i.i.d. 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 at 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 g rounds at a time. Under this pattern, Assumption 2 is satisfied with P = g K. We refer to g as the availability time.We evaluate five algorithms: FedAvg [26] , FedProx [21] , SCAFFOLD [16] , Amplified FedAvg [38] , and Amplified SCAFFOLD (ours). We tune each algorithm's parameters by grid search, including learning rate η, amplification rate γ, 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 at the following repository: https://github.com/ MingruiLiu-ML-Lab/FL-under-Periodic-Participation Synthetic We evaluate each algorithm's convergence on a difficult objective based on a lower bound for FedAvg [42] . The objective maps R 4 to R, is convex, and is parameterized by a smoothness L, stochastic gradient variance σ 2 , and heterogeneity κ, so that it satisfies Assumption 1 by construction. The complete definition of the objective can be found in Appendix D. 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 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 heterogeneous data in federated learning, we use a common protocol [16, 38] , to partition each dataset into client datasets according to a data similarity parameter s. This protocol is detailed in Appendix D. Following [38] , we set the number of clients N = 250, data similarity s = 5%, and the number of sampled clients per round S = 10. For client participation, we set the number of groups K = 5, 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 in Section 5.2 (the radius of each error bar is 1 standard deviation). All other settings can be found in Appendix D.Additional experimental results are provided in Appendix E, where we compare against extra baselines (FedAdam [31] , FedYogi [31] , FedAvg-M [4] , and Amplified FedAvg with FedProx regularization), and evaluate training under another non-i.i.d. client participation pattern.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 to the best solution by a significant margin. Note that in both cases, the curves for FedAvg and FedProx are nearly overlapping.Results for the synthetic experiment and CIFAR-10 are shown in Figure 1 , and results for Fashion-MNIST are shown in Figure 2 . 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 underwhelming experimental performance of Amplified FedAvg corroborates our discussion from Section 4.3; Amplified FedAvg requires many communication rounds and suffers from data heterogeneity. Contrary to our findings, the original evaluation of Amplified FedAvg [38] 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 a lack of theoretical guarantees under non-i.i.d. participation, 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.To understand how each algorithm's performance is affected by data heterogeneity, the number of participating clients, and the number of client groups, we perform an ablation study on Fashion-MNIST. First, we fix the data similarity s = 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 s over {2.5%, 10%, 33%, 100%}. Lastly, we fix s = 5%, S = 10 while varying the number of client groups K ∈ {2, 4, 6, 8}. 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 2 (right).Amplified SCAFFOLD reaches the best solution in 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 a 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 a 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 a larger decrease when transitioning from homogeneous data to heterogeneous data.Robustness to number of participating clients. The number of participating clients has a smaller effect on performance than data heterogeneity, but some degradation happens in the extreme case S = 5. In particular, SCAFFOLD has competitive performance with large S ≥ 15, but its test accuracy drops off significantly compared to Amplified SCAFFOLD in the case S = 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 K 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 1 ) actually increases with K, these experiments demonstrate that in practice, Amplified SCAFFOLD can maintain performance as K increases. 
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 unaffected by data heterogeneity. We also show that Amplified SCAFFOLD experimentally outperforms baselines on 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 a 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 or leave the federated learning process during training. Extending our algorithm and guarantees for this situation would require a reformulation of the optimization problem, and possibly additional assumptions about the participation structure. We leave such analysis for future work.  
safeguards: 
 Question: 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, or scraped datasets)?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 a 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 (Fashion-MNIST, 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.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 package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Let G r denote the filtration generated by {ξ i r,k : 0≤ k ≤ I -1, i ∈ [N ]}, that is, by the randomness in the stochastic gradients during round r. Also, let Q r0 denote the filtration generated by {q i r : r 0 ≤ r < r 0 + P, i ∈ [N ]}, that is, the randomness in client sampling between rounds r 0 and r 0 + P -1 (inclusive). Also, let G denote the filtration generated byG 0 ∪ G 1 ∪ . . . ∪ G R-1 and Q denote the filtration generated by Q 0 ∪ Q P ∪ . . . ∪ Q R-P . Similarly, let G :r denote the filtration generated by G 0 ∪ G 1 ∪ . . . ∪ G r-1 and Q :r0 denote the filtration generated by Q 0 ∪ Q P ∪ . . . ∪ Q r0-P . Lastly, denote E r0 [•] = E[•|Q :r0 , G :r0 ].In order to analyze the control variate errors (i.e., ∥∇f i ( xr0 ) -G i r0 ∥), we introduce notation to refer to the iterates whose stochastic gradients were used to construct G i r0 . These iterates are exactly the iterates during the most recent window before r 0 in which client i was sampled, i.e., where1 P (m+1)P -1 s=mP q i s > 0. For each r ∈ {r 0 , r 0 + 1, . . . , r 0 + P -1}, k ∈ {0, . . . , I -1}, and i ∈ [N ], let t i (r) = r if qi r0 > 0 t i (r -P ) if qi r0 = 0with the initialization t i (r) = 0 for all r ∈ {-P, . . . , -1}. Then denotey i r,k = x i ti(r),k z i r = q i ti(r) ζ i r,k = ξ i ti(r),k . Also, denote zi r0 = 1 P r0+P -1 r=r0 z i r .Then we can rewriteG i r0 = 1 P zi r0-P I r0-1 s=r0-P z i s I-1 k=0 ∇F i (y i s,k ; ζ i s,k ). Define xr,k = N i=1 q i r x i r,k D r,k = N i=1 q i r E x i r,k -xr,k 2 Q M r,k = E ∥ xr,k -xr0 ∥ 2 Q S i r0 = 1 IP r0-1 s=r0-P I-1 k=0 z i s zi r0-P E y i s,k -xr0 2 Q w i r0 = 1 N N j=1 1 qj r0 > 0 P qj r0 r0+P -1 s=r0 q i s q j s v i r0 = qi r0 - 1 N Λ i r0 = 1 P r0-1 s=r0-P z i s 2 1 P r0-1 s=r0-P z i s 2 .As discussed in the main body, xr,k is a weighted average over local client models, weighted according to client participation. D r,k and M r,k are the drift terms described in the proof sketch of Section 4.4.In the proof sketch, we also informally discuss the control variate errorC i r0 = ∥∇f i ( xr0 ) -G i r0 ∥ 2 .This error is closely related to the term S i r0 defined above, sinceE ∇f i ( xr0 ) -E[G i r0 |Q] 2 Q = L 2 S i r0 .The quantities w i r0 , v i r0 and Λ i r0 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 errors 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 a uniform average as long as the term w i r0 is not too large, which is exactly the requirement stated in Equation 1. On the other hand, the term Λ i r0 arises while bounding the variance of the update ∥ xr0+P -xr0 ∥, and it represents the sample size for which the correction G i r0 is computed. When the client sampling distribution is closer to uniform, then each client may participate frequently during each window of P rounds, and the effective sample size used to compute each control variate is large. In this case, the variance of the update ∥ xr0+P -xr0 ∥ will be smaller, since larger sample size implies smaller variance. For general client sampling distributions, Λ i r0 describes the reduction of variance of one component of the update (i.e. G i r0 ) due to the sampling of stochastic gradients during the previous window of P rounds. In our analysis, the variance of the update ∥ xr0+P -xr0 ∥ can be bounded in terms of the variance of G i r0 , which in turn depends on Λ i r0 . The condition in Equation 2 essentially enforces that clients participate sufficiently uniformly, so that the variance of G i r0 can be bounded. We note that both Equation 1 and Equation 2 are satisfied by i.i.d. participation, regularized participation, and cyclic participation.Finally, for ease of exposition, one clarification must be made about the conditional expectation E[•|Q] as it appears in, for example, M r,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 a smaller subset rounds. For example, in M r,k , the expression ∥ xr,k -xr0 ∥ 2 only depends on the randomness up to round r ≤ r 0 + P , so thatE ∥ xr,k -xr0 ∥ 2 Q = E ∥ xr,k -xr0 ∥ 2 Q :r0+P .In several places throughout the proof, we will replaceEQUATIONandEQUATIONProof. DenoteḠi r0 = 1 P zi r0-P I r0-1 s=r0-P z i s I-1 k=0 ∇f i (y i s,k ) Ḡr0 = 1 N N i=1 Ḡi r0 . Also, denote g i r,k = ∇F i (x i r,k ; ξ i r,k ) -G i r0 + G r0 and ḡi r,k = ∇f i (x i r,k ) -Ḡi r0 + Ḡr0 . Ḡi r0is the analogue of Ḡr0 that depends on deterministic gradients ∇f i (y i s,k ) instead of stochastic gradients.We first compute the errorsEQUATIONQ , which will be needed in several places.EQUATIONwhere (i) uses Jensen's inequality. ThereforeEQUATIONwhere the last line uses Equation 5. AlsoEQUATIONwhere (i) uses the fact that stochastic gradient noise is independent across each client, and (ii) uses ρ 2 ≥ 1 N .One-step recursive bound for D r,k For any k ≥ 0,EQUATIONwhere (i) usesE    (g i r,k -ḡi r,k ) + N j=1 q j r (g j r,k -ḡj r,k ) 2 Q    ≤ 2E g i r,k -ḡi r,k 2 Q + 2E    N j=1 q j r (g j r,k -ḡj r,k ) 2 Q    ≤ 2E g i r,k -ḡi r,k 2 Q + 2 N j=1 q j r E g j r,k -ḡj r,k 2 Q (a) ≤ 36σ 2 ,(a) uses Equation 6, and (ii) uses Young's inequality. Focusing on the second term of Equation 8:N i=1 q i r E    ḡi r,k - N j=1 q j r ḡj r,k 2 Q    = N i=1 q i r E    N j=1 q j r (ḡ i r,k -ḡj r,k ) 2 Q    (i) ≤ N i=1 q i r N j=1 q j r E ḡi r,k -ḡj r,k 2 Q ≤ N i=1 q i r N j=1 q j r E ∇f i (x i r,k ) -Ḡi r0 -∇f j (x j r,k ) + Ḡj r0 2 Q ≤ N i=1 q i r N j=1 q j r 2E ∇f i (x i r,k ) -Ḡi r0 2 Q + 2E ∇f j (x j r,k ) -Ḡj r0 2 Q = 4 N i=1 q i r E ∇f i (x i r,k ) -Ḡi r0 2 Q ,where (i) uses Jensen's inequality. Using the decomposition∇f i (x i r,k ) -Ḡi r0 = (∇f i (x i r,k ) -∇f i ( xr,k )) + (∇f i ( xr,k ) -∇f i ( xr0 )) + (∇f i ( xr0 ) -Ḡi r0 ), we have N i=1 q i r E    ḡi r,k - N j=1 q j r ḡj r,k 2 Q    ≤ 4 N i=1 q i r 3E ∇f i (x i r,k ) -∇f i ( xr,k ) 2 Q + 3E ∥∇f i ( xr,k ) -∇f i ( xr0 )∥ 2 Q + 3E ∇f i ( xr0 ) -Ḡi r0 2 Q ≤ 12L 2 N i=1 q i r E x i r,k -xr,k 2 Q + 12L 2 N i=1 q i r E ∥ xr,k -xr0 ∥ 2 Q + 12 N i=1 q i r E ∇f i ( xr0 ) -Ḡi r0 2 Q = 12L 2 D r,k + 12L 2 M r,k + 12 N i=1 q i r E   ∇f i ( xr0 ) - 1 P zi r0-P I r0-1 s=r0-P I-1 k=0 z i s ∇f i (y i s,k ) 2 Q   = 12L 2 D r,k + 12L 2 M r,k + 12 N i=1 q i r E   1 P zi r0-P I r0-1 s=r0-P I-1 k=0 z i s (∇f i ( xr0 ) -∇f i (y i s,k )) 2 Q   ≤ 12L 2 D r,k + 12L 2 M r,k + 12 N i=1 q i r 1 P zi r0-P I r0-1 s=r0-P I-1 k=0 z i s E ∇f i ( xr0 ) -∇f i (y i s,k ) 2 Q ≤ 12L 2 D r,k + 12L 2 M r,k + 12L 2 N i=1 q i r 1 P zi r0-P I r0-1 s=r0-P I-1 k=0 z i s E xr0 -y i s,k 2 Q ≤ 12L 2 D r,k + 12L 2 M r,k + 12L 2 N i=1 q i r S i r0 .Plugging back into Equation 8,D r,k+1 ≤ 1 + 1 λ 1 D r,k + 12η 2 L 2 (1 + λ 1 ) D r,k + M r,k + N i=1 q i r S i r0 + 36η 2 σ 2 ≤ 1 + 1 λ 1 + 12η 2 L 2 (1 + λ 1 ) D r,k + 12η 2 L 2 (1 + λ 1 ) M r,k + N i=1 q i r S i r0 + 36η 2 σ 2 .Now choose λ 1 = 2I, so that 1 ≤ λ1 2 and12η 2 L 2 (1 + λ 1 ) ≤ 18η 2 L 2 λ 1 ≤ 36η 2 L 2 I ≤ 1 2I ,where we used the condition η ≤ 1 60LIP . This yields the following recursive bound on D r,k+1 :EQUATIONOne-step recursive bound for M r,k For any k ≥ 0,EQUATIONwhere (i) uses Equation 7and (ii) uses Young's inequality. Focusing on the second term in Equation 10:N i=1 q i r E ḡi r,k 2 Q = N i=1 q i r E ∇f i (x i r,k ) -Ḡi r0 + Ḡr0 2 Q = N i=1 q i r E (∇f i (x i r,k ) -∇f i ( xr,k )) + (∇f i ( xr,k ) -∇f i ( xr0 )) + (∇f i ( xr0 ) -Ḡi r0 ) + ( Ḡr0 -∇f ( xr0 )) + ∇f ( xr0 ) 2 Q ≤ 5 N i=1 q i r E ∇f i (x i r,k ) -∇f i ( xr,k ) 2 Q + 5 N i=1 q i r E ∥∇f i ( xr,k ) -∇f i ( xr0 )∥ 2 Q + 5 N i=1 q i r E ∇f i ( xr0 ) -Ḡi r0 2 Q + 5E Ḡr0 -∇f ( xr0 ) 2 Q + 5E ∥∇f ( xr0 )∥ 2 Q ≤ 5L 2 N i=1 q i r E x i r,k -xr,k 2 Q + 5L 2 N i=1 q i r E ∥ xr,k -xr0 ∥ 2 Q + 5 N i=1 q i r + 1 N E   ∇f i ( xr0 ) - 1 P zi r0-P I r0-1 s=r0-P I-1 k=0 z i s ∇f i (y i s,k ) 2 Q   + 5E ∥∇f ( xr0 )∥ 2 Q ≤ 5L 2 D r,k + 5L 2 M r,k + 5 N i=1 q i r + 1 N E   1 P zi r0-P I r0-1 s=r0-P I-1 k=0 z i s (∇f i ( xr0 ) -∇f i (y i s,k )) 2 Q   + 5E ∥∇f ( xr0 )∥ 2 Q ≤ 5L 2 D r,k + 5L 2 M r,k + 5 N i=1 q i r + 1 N 1 P zi r0-P I r0-1 s=r0-P I-1 k=0 z i s E ∇f i ( xr0 ) -∇f i (y i s,k ) 2 Q + 5E ∥∇f ( xr0 )∥ 2 Q ≤ 5L 2 D r,k + 5L 2 M r,k + 5L 2 N i=1 q i r + 1 N S i r0 + 5E ∥∇f ( xr0 )∥ 2 Q .Plugging back into Equation 10:M r,k+1 ≤ 1 + 1 λ 2 M r,k + 5η 2 L 2 (1 + λ 2 ) D r,k + M r,k + N i=1 q i r + 1 N S i r0 + 5η 2 (1 + λ 2 )E ∥∇f ( xr0 )∥ 2 Q + 9η 2 ρ 2 σ 2 ≤ 1 + 1 λ 2 + 5η 2 L 2 (1 + λ 2 ) M r,k + 5η 2 L 2 (1 + λ 2 ) D r,k + N i=1 q i r + 1 N S i r0 + 5η 2 (1 + λ 2 )E ∥∇f ( xr0 )∥ 2 Q + 9η 2 ρ 2 σ 2 .Now choose λ 2 = 2IP , so that 1 ≤ λ2 2 and5η 2 L 2 (1 + λ 2 ) ≤ 15 2 η 2 L 2 λ 2 ≤ 15η 2 L 2 IP ≤ 15L 2 IP 1 72L 2 I 2 P 2 ≤ 1 2IP,where we used the condition η ≤ 1 60LIP . This yields the following recursive bound on M r,k+1 :EQUATION)Note that the same argument can be used to bound M r,0 in terms of M r-1,I-1 with the same recurrence relation.Unrolling the recursion For 0 ≤ t ≤ IP , let r t = r 0 + ⌊t/I⌋ and k t = t -⌊t/I⌋ * I. Then let d t = D rt,kt and m t = M rt,kt . Also, letq 1 = 18η 2 L 2 I q 2 = 15η 2 L 2 IP a r = 18η 2 L 2 I N i=1 q i r S i r0 + 36η 2 σ 2 b r = 15η 2 L 2 IP N i=1 q i r + 1 N S i r0 + 15η 2 IP E ∥∇f ( xr0 )∥ 2 Q + 9η 2 ρ 2 σ 2 .Then Equation 9and Equation 11 imply the following mutually recursive relation over d t and m t :EQUATIONwhere d 0 = m 0 = 0. We will unroll this recurrence, showing a bound for m t and d t in terms of the following quantities. For any 0 ≤ t ≤ IP -1 and 0 ≤ s ≤ r t , let j(s, t) = min{I, t -sI} and ℓ(s, t) = max{0, t -(s + 1)I}. For any s, t, if k t+1 = 0, define α s,t+1 = 0.Otherwise, defineα s,t+1 = α s,t 1 + 1 I + q 1 P 1 + 1 IP j(s,t) -1 1 + 1 IP ℓ(s,t) + q 1 q 2 t-sI-2 i=0 1 + 1 IP i α s,t-1-i .Also, defineβ s,t+1 = β s,t 1 + 1 IP + 1 {s = r t } q 2 P 1 + 1 I kt -1 + q 1 q 2 kt-2 i=0 1 + 1 I i β s,t-1-i ψ s,t+1 = 1 P t-sI-1 i=0 1 + 1 IP i α s,t-i ϕ s,t+1 = P kt-1 i=0 1 + 1 I i β s,t-i ,under the initial conditions ϕ s,kI = 0 for all s ≤ P and s ≤ k ≤ P α s,kI = 0 for all s ≤ P and s ≤ k ≤ P ψ s,sI = 0 for all s ≤ P β s,sI = 0 for all s ≤ P.Now we can unroll the recurrence in Equation 12, by proving the following statements by induction on t:EQUATION)EQUATION)Equation 13 and Equation 14 hold for the base case t = 0, since d 0 = m 0 = 0. Now suppose that Equation 13and Equation 14 hold for some t ≤ IP , and we will show that they hold for t + 1. We consider two cases: k t+1 ̸ = 0 and k t+1 = 0.In the first case, r t+1 = r t , i.e., step t + 1 is in the same round as step t, and k t+1 = k t + 1. Using Equation 12 together with the inductive hypothesis:d t+1 ≤ 1 + 1 I 1 + 1 I kt -1 a rt I + q 1 I rt s=0 ϕ s,t a s + I rt s=0 α s,t b s + q 1 IP rt s=0 1 + 1 IP j(s,t) -1 1 + 1 IP ℓ(s,t) + q 2 ψ s,t b s + IP rt s=0 β s,t a s + a rt ≤ 1 + 1 I kt+1 -1 + 1 I + 1 I a rt I + q 1 I rt s=0 1 + 1 I ϕ s,t + P β s,t a s + I rt s=0 1 + 1 I α s,t + q 1 P 1 + 1 IP j(s,t) -1 1 + 1 IP ℓ(s,t) + q 1 q 2 P ψ s,t b s (i) ≤ 1 + 1 I kt+1 -1 a rt I + q 1 I rt s=0 ϕ s,t+1 a s + I rt s=0 α s,t+1 b s (ii) ≤ 1 + 1 I kt+1 -1 a rt+1 I + q 1 I rt+1 s=0 ϕ s,t+1 a s + I rt+1 s=0 α s,t+1 b s ,where (i) uses the fact that ϕ s,t+1 = 1 + 1 I ϕ s,t + P β s,t and the definitions of α s,t+1 , ψ s,t , and (ii) uses k t+1 = k t + 1 and r t+1 = r t . Similarly,m t+1 ≤ 1 + 1 IP IP rt s=0 1 + 1 IP j(s,t) -1 1 + 1 IP ℓ(s,t) + q 2 ψ s,t b s + IP rt s=0 β s,t a s + q 2 1 + 1 I kt -1 a rt I + q 1 I rt s=0 ϕ s,t a s + I rt s=0 α s,t b s + b rt ≤ IP rt s=0 1 + 1 IP j(s,t) -1 1 + 1 IP ℓ(s,t)+1 + 1 {s = r t } 1 IP + q 2 1 + 1 IP ψ s,t + 1 P α s,t b s + IP rt s=0 1 + 1 IP β s,t + 1 {s = r t } q 2 P 1 + 1 I kt -1 + q 1 q 2 P ϕ s,t a s (i) ≤ IP rt s=0 1 + 1 IP j(s,t+1) -1 1 + 1 IP ℓ(s,t+1) + q 2 1 + 1 IP ψ s,t + 1 P α s,t b s + IP rt s=0 1 + 1 IP β s,t + 1 {s = r t } q 2 P 1 + 1 I kt -1 + q 1 q 2 P ϕ s,t a s (ii) ≤ IP rt s=0 1 + 1 IP j(s,t+1) -1 1 + 1 IP ℓ(s,t+1) + q 2 ψ s,t+1 b s + IP rt s=0 β s,t+1 a s (iii) ≤ IP rt+1 s=0 1 + 1 IP j(s,t+1) -1 1 + 1 IP ℓ(s,t+1) + q 2 ψ s,t+1 b s + IP rt+1 s=0 β s,t+1 a s ,where (i) uses the fact that for s < r t :1 + 1 IP j(s,t) -1 1 + 1 IP ℓ(s,t)+1 + 1 {s = r t } 1 IP = 1 + 1 IP I -1 1 + 1 IP t+1-(s+1)I = 1 + 1 IP j(s,t+1) -1 1 + 1 IP ℓ(s,t+1)and for s = r t :1 + 1 IP j(s,t) -1 1 + 1 IP ℓ(s,t)+1 + 1 {s = r t } 1 IP = 1 + 1 IP t-sI -1 1 + 1 IP + 1 IP = 1 + 1 IP t+1-sI -1 = 1 + 1 IP j(s,t+1) -1 1 + 1 IP ℓ(s,t+1), (ii) uses the fact that ψ s,t+1 = 1 + 1 IP ψ s,t + 1 P α s,t and the definitions of β s,t+1 , ϕ s,t , and (iii) uses k t+1 = k t + 1 and r t+1 = r t . This completes the inductive step for the first case (k t+1 ̸ = 0). In the second case (i.e., k t+1 = 0), Equation 13 must hold for t + 1, since d t+1 = 0. So it only remains to show Equation 14 holds for t + 1. Note that r t = r t+1 -1. As in the first case, we can use Equation 12together with the inductive hypothesis to obtain:m t+1 ≤ IP rt s=0 1 + 1 IP j(s,t+1) -1 1 + 1 IP ℓ(s,t+1) + q 2 ψ s,t+1 b s + IP rt s=0 ϕ s,t+1 a s ≤ IP rt+1 s=0 1 + 1 IP j(s,t+1) -1 1 + 1 IP ℓ(s,t+1) + q 2 ψ s,t+1 b s + IP rt+1 s=0 ϕ s,t+1 a s ,where the second line uses the fact that the r t+1 -st element of both sums is 0, since j(r t+1 , t + 1) = 0, ψ rt+1,t+1 = 0, and ϕ rt+1,t+1 = 0. This completes the inductive step for both cases, and proves Equation 13 and Equation 14.We can now bound α s,t and β s,t separately by induction on t. First, for any s ≤ P -1 and t with sI ≤ t ≤ IP , we claim that α s,t ≤ 36q 1 IP, (15) which we will show by induction on t. Let s ≤ P -1 be given. For the base case, Equation 15 holds when t = sI since α s,sI = 0. Now suppose that it holds for all t ′ ≤ t. ThenEQUATIONandEQUATIONwhere the last line uses the definition of q 1 and q 2 together with the condition η ≤ 1 60LIP :36q 1 q 2 I 2 P = 36 • 270η 4 L 4 I 4 P 2 ≤ 36 • 270 60 4 L 4 I 4 P 2 1 L 4 I 4 P 4 ≤ 1 P 2 ≤ 1.Plugging Equation 16and Equation 17 into the definition of α s,t+1 yieldsα s,t+1 ≤ α s,t 1 + 1 I + 2q 1 P 1 + 1 IP t-sI -1 (i) ≤ 2q 1 P kt i=0 1 + 1 I i 1 + 1 IP t-sI-i -1 ≤ 2q 1 P 1 + 1 I I kt i=0 1 + 1 IP t-sI-i -1 ≤ 6q 1 P kt i=0 1 + 1 IP t-sI-i ≤ 6q 1 P 1 + 1 IP (rt-s)I kt i=0 1 + 1 IP i ≤ 18q 1 P I-1 i=0 1 + 1 IP i (ii) ≤ 18q 1 IP -1 i=0 1 + 1 IP i ≤ 18q 1 IP 1 + 1 IP IP -1 ≤ 36q 1 IP,where (i) unrolls the recurrence on the first line until α s,rtI = 0, (ii) uses PI-1 i=0 1 + 1 IP i ≤ IP -1 i=0 1 + 1 IP i since 1 + 1 IPi is increasing with i, and we repeatedly used 1 + 1xx < e ≤ 3.This completes the induction and proves Equation 15.We will similarly prove the statementEQUATION)for all s ≤ P -1 and t with sI ≤ t ≤ IP by induction on t. Let s ≤ P -1 be given. For the base case, Equation 15 holds when t = sI since β s,sI = 0. Now suppose that it holds for all t ′ ≤ t. ThenEQUATIONEQUATIONwhere the last line uses the definition of q 1 and q 2 together with the condition η ≤ 1 60LIP :12q 1 q 2 I 2 ≤ 12 • 270η 4 L 4 I 4 P ≤ 12 • 270 60 4 L 4 I 4 P 1 L 4 I 4 P 4 ≤ 1 P 3 ≤ 1.We now consider two cases: t < (s + 1)I and t ≥ (s + 1)I. In the first case, we have s = r t , and plugging Equation 20 into the definition of β s,t+1 yieldsβ s,t+1 ≤ β s,t 1 + 1 IP + 2 q 2 P 1 + 1 I kt -1 (i) ≤ 2 q 2 P kt i=0 1 + 1 IP i 1 + 1 I kt-i -1 ≤ 2 q 2 P 1 + 1 IP kt kt i=0 1 + 1 I kt-i -1 ≤ 2 q 2 P 1 + 1 IP I kt i=0 1 + 1 I i ≤ 6 q 2 I P 1 + 1 I kt+1 -1 ≤ 6 q 2 I P 1 + 1 I I -1 ≤ 12 q 2 I P ,where (i) unrolls the recurrence on the first line until β s,sI = 0 and we repeatedly used 1 + 1xx < e ≤ 3. In the second case, we have s > r t , so plugging Equation 19 into the definition of β s,t+1 yieldsβ s,t+1 ≤ β s,t 1 + 1 IP + 12 q 1 q 2 2 I 2 P 1 + 1 I kt -1 ≤ β s,t 1 + 1 IP + 12 q 1 q 2 2 I 2 P 1 + 1 I I -1 ≤ β s,t 1 + 1 IP + 24 q 1 q 2 2 I 2 P (i) ≤ 24 q 1 q 2 2 I 2 P t-sI i=0 1 + 1 IP i = 24q 1 q 2 2 I 3 1 + 1 IP t-sI+1 -1 ≤ 24q 1 q 2 2 I 3 1 + 1 IP IP - ≤ 48q 1 q 2 2 I 3 ≤ 12 q 2 I P ,where (i) unrolls the recurrence on the previous line until β s,sI = 0 and the last inequality uses the definition of q 1 and q 2 together with the condition η ≤ 1 60LIP :48q 1 q 2 I 2 = 48 • 270η 4 L 4 I 4 P ≤ 48 • 270 60 4 L 4 I 4 P 1 L 4 I 4 P 4 ≤ 12 P 3 ≤ 12 P .This completes the induction in both cases and proves Equation 18.We can then use Equation 15and Equation 18to yield bounds for the remaining terms of Equation 13and Equation 14 as follows:q 2 ψ s,t = q 2 P t-sI-1 i=0 1 + 1 IP i α s,t-1-i ≤ 36q 1 q 2 I t-sI-1 i=0 1 + 1 IP i ≤ 36q 1 q 2 I IP -1 i=0 1 + 1 IP i ≤ 36q 1 q 2 I 2 P 1 + 1 IP IP -1 ≤ 72q 1 q 2 I 2 P ≤ 72 • 270η 4 L 4 I 4 P 2 ≤ 72 • 270 60 4 L 4 I 4 P 2 1 L 4 I 4 P 4 ≤ P ,andq 1 ϕ s,t = q 1 P kt-1 i=0 1 + 1 I i β s,t-i ≤ 12q 1 q 2 I kt-1 i=0 1 + 1 I i = 12q 1 q 2 I 2 1 + 1 I kt -1 ≤ 12q 1 q 2 I 2 1 + 1 I I -1 ≤ 24q 1 q 2 I 2 .Finally, we can plug these into Equation 13 to yieldd t ≤ 1 + 1 I kt -1 a rt I + 24q 1 q 2 I 3 rt s=0 a s + 36q 1 I 2 P rt s=0 b s ≤ 2a rt I + 24q 1 q 2 I 3 rt s=0 a s + 36q 1 I 2 P rt s=0 b s ,and into Equation 14m t ≤ IP rt s=0 1 + 1 IP m1 -1 1 + 1 IP m2 + 1 P 2 b s + 12q 2 I 2 rt s=0 a s (i) ≤ IP rt s=0 6 P + 1 P 2 b s + 12q 2 I 2 rt s=0 a s ≤ 7I rt s=0 b s + 12q 2 I 2 rt s=0 a s ,where (i) usesEQUATION1 + 1 IP m2 ≤ 1 + 1 IP IP ≤ 3.Or, in the original notation:EQUATIONwhere (i) uses the fact that the interval {r 0 , . . . , r} is contained in the interval {r 0 , . . . , r 0 + P -1} and (ii) uses the condition η ≤ 1 60LIP to simplify non-dominating terms. AlsoEQUATIONwhere (i) and (ii) use the same operations as in Equation 21. Summing Equation 22and Equation 21,D r,k + M r,k ≤ 36η 2 L 2 I 2 N i=1 q i r S i r0 + 9720η 4 L 4 I 4 P 3 + 105η 2 L 2 I 2 P 2 1 N N i=1 S i r0 + 9753η 4 L 4 I 4 P 3 + 106η 2 L 2 I 2 P 2 N i=1 qi r0 S i r0 + 73η 2 I + 5832η 4 L 2 I 3 P 2 ρ 2 + 63η 2 IP ρ 2 + 6480η 4 L 2 I 3 P 2 σ 2 + 9720η 4 L 2 I 4 P 3 + 105η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 Q ≤ 36η 2 L 2 I 2 N i=1 q i r S i r0 + 109η 2 L 2 I 2 P 2 N i=1 qi r0 + 1 N S i r0 + 75η 2 I + 65η 2 IP ρ 2 σ 2 + 108η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 Q ,where the last inequality uses η ≤ 1 60LIP . This proves Equation 3. Equation 4follows by summing over r ∈ {r 0 , . . . , r 0 + P -1} and k ∈ {0, . . . , I -1}, taking total expectation, and applying the conditionEQUATION)Proof. By the algorithm definition,xr0+P -xr0 = -γη r0+P -1 r=r0 N i=1 I-1 k=0 q i r (∇F i (x i r,k ; ξ i r,k )-G i r0 +G r0 ) = -γη r0+P -1 r=r0 N i=1 I-1 k=0 q i r g i r,k .To obtain the variance of the update xr0+P -xr0 ,EQUATION)We can bound the two terms A 1 and A 2 separately as follows. For A 1 ,EQUATION)where (i) uses the fact that for each i,q i r ∇F i (x i r,k ) -∇f i (x i r,k ) r,kis a martingale difference sequence with respect to G (when conditioned on Q) and that stochastic gradient noise is independent across clients. For A 2 ,EQUATION)where (i) uses the fact that, conditioned on Q, the variables G i r0 -Ḡi r0 depend only on stochastic gradient noise, which is independent across clients, and the last inequality uses the conditionE N i=1 v i r0 2 Λ i r0 ≤ ρ 2 .Plugging Equation 25and Equation 26 into Equation 24yieldsEQUATION)ThereforeEQUATION)where (i) uses Equation 27, (ii) uses the decomposition∇f i (x i r,k ) -Ḡi r0 + Ḡr0 = ∇f ( xr0 ) + (∇f i (x i r,k ) -∇f i ( xr,k )) + (∇f i ( xr,k ) -∇f i ( xr0 )) + (∇f i ( xr0 ) -Ḡi r0 ) + (∇f ( xr0 ) -Ḡr0 ),and(iii) uses G r0 = 1 N N i=1 G i r0 and E r0 qi r0 = 1 N to obtain E ∥∇f ( xr0 ) -Ḡr0 ∥ 2 + N i=1 1 P r0+P -1 r=r0 q i r ∥∇f i ( xr0 ) -Ḡi r0 ∥ 2 = E E r0 ∥∇f ( xr0 ) -Ḡr0 ∥ 2 + N i=1 1 P r0+P -1 r=r0 q i r ∥∇f i ( xr0 ) -Ḡi r0 ∥ 2 = E ∥∇f ( xr0 ) -Ḡr0 ∥ 2 + N i=1 E r0 1 P r0+P -1 r=r0 q i r ∥∇f i ( xr0 ) -Ḡi r0 ∥ 2 = E ∥∇f ( xr0 ) -Ḡr0 ∥ 2 + 1 N N i=1 ∥∇f i ( xr0 ) -Ḡi r0 ∥ 2 = E   1 N N i=1 ∇f i ( xr0 ) -Ḡi r0 2 + 1 N N i=1 ∥∇f i ( xr0 ) -Ḡi r0 ∥ 2   ≤ E 1 N N i=1 ∇f i ( xr0 ) -Ḡi r0 2 + 1 N N i=1 ∥∇f i ( xr0 ) -Ḡi r0 ∥ 2 .The remaining term in Equation 28 can be simplified as:E ∥∇f i ( xr0 ) -Ḡi r0 ∥ 2 ≤ E   ∇f i ( xr0 ) - 1 IP r0-1 r=r0-P I-1 k=0 z i r zi r0-P ∇f i (y i r,k ) 2   ≤ E   1 IP r0-1 r=r0-P I-1 k=0 z i r zi r0-P ∇f i ( xr0 ) -∇f i (y i r,k ) 2   ≤ 1 IP r0-1 r=r0-P I-1 k=0 E z i r zi r0-P ∇f i ( xr0 ) -∇f i (y i r,k ) 2 ≤ L 2 IP r0-1 r=r0-P I-1 k=0 E z i r zi r0-P xr0 -y i r,k 2 = L 2 E 1 IP r0-1 r=r0-P I-1 k=0 z i r zi r0-P E xr0 -y i r,k 2 Q = L 2 E S i r0 .Plugging back to Equation 28yieldsE ∥ xr0+P -xr0 ∥ 2 ≤ 5γ 2 η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + 4γ 2 η 2 IP ρ 2 σ 2 + 5γ 2 η 2 L 2 IP E r0+P -1 r=r0 I-1 k=0 (D r,k + M r,k ) + 10γ 2 η 2 L 2 I 2 P 2 1 N N i=1 E S i r0 (i) ≤ 5γ 2 η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + 4γ 2 η 2 IP ρ 2 σ 2 + 5γ 2 η 2 L 2 IP 108η 2 I 3 P 3 E ∥∇f ( xr0 )∥ 2 + 75η 2 I 2 P + 65η 2 I 2 P 2 ρ 2 σ 2 + 254η 2 L 2 I 3 P 3 1 N N i=1 E S i r0 + 10γ 2 η 2 L 2 I 2 P 2 1 N N i=1 E S i r0 ≤ 5γ 2 η 2 I 2 P 2 1 + 108η 2 L 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + γηIP 4γηρ 2 + 375γη 3 L 2 I 2 P + 325γη 3 L 2 I 2 P 2 ρ 2 σ 2 + 10γ 2 η 2 L 2 I 2 P 2 1 + 127η 2 L 2 I 2 P 2 1 N N i=1 E S i r0 (ii) ≤ 6γ 2 η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + γηIP 5γηρ 2 + 7η 2 LI σ 2 + 11γ 2 η 2 L 2 I 2 P 2 1 N N i=1 E S i r0 .where (i) uses Equation 4from Lemma 1 and (ii) uses η ≤ 1 60LIP and γη ≤ 1 60LIP . This proves Equation 23.Lemma 3. Suppose that P Qr 0 (q i r0 > 0) ≥ p sample , E w i r0 Q :r0 ≤ P 2 N , E r0 [q i r0 ] = 1 N , and E N i=1 v i r0 2 Λ i r0 ≤ ρ 2 . If η ≤ √ psample 60LIP and γη ≤ psample 60LIP , then 1 N N i=1 E S i r0+P ≤ 324η 2 I 2 P 2 + 20 p sample γ 2 η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + 226η 2 I + 195η 2 IP ρ 2 + 17 p sample γ 2 η 2 IP ρ 2 σ 2 + 1 - 1 2 p sample 1 N N j=1 E S j r0 .Proof. Let 1 ≤ i ≤ N . We can consider the value S i r0+P under two cases: qi r0 > 0 and the complement.Let A i r0 = {q i r0 > 0}. Denote B i 1 = 1 A i r0 1 IP qi r0 r0+P -1 s=r0 I-1 k=0 q i s E x i s,k -xr0+P 2 Q B i 2 = 1 Āi r0 1 IP zi r0 r0+P -1 s=r0 I-1 k=0 z i s E y i s,k -xr0+P 2 Q . Then S i r0+P = B i 1 + B i 2 ,and we can consider the two cases separately. Notice that∥x i s,k -xr0+P ∥ 2 ≤ 3∥x i s,k -xs,k ∥ 2 + 3∥ xs,k -xr0 ∥ 2 + 3∥ xr0+P -xr0 ∥ 2 .ThereforeB i 1 = 1 A i r0 1 IP qi r0 r0+P -1 s=r0 I-1 k=0 q i s E x i s,k -xr0+P 2 Q ≤ 1 A i r0 3 IP qi r0 r0+P -1 s=r0 I-1 k=0 q i s E ∥x i s,k -xs,k ∥ 2 Q + E ∥ xs,k -xr0 ∥ 2 Q + E ∥ xr0+P -xr0 ∥ 2 Q ≤ 1 A i r0 3 IP qi r0 r0+P -1 s=r0 I-1 k=0 q i s (D s,k + M s,k ) + 31 A i r0 E ∥ xr0+P -xr0 ∥ 2 Q .Using Equation 3 from Lemma 1,EQUATIONwhere (i) uses E r0 [q i r0 ] = 1 N and the tower propertyE [E [•|Q]|Q :r0 ] = E [•|Q :r0 ], and (ii) uses the tower property E [E [•|Q :r0 ]] = E [•].2 . Under Āi r0 , z i r = z i r-P and y i r,k = y i r-P,k for all r ∈ {r 0 , . . . , r 0 + P -1}. ThereforeB i 2 = 1 Āi r0 1 IP zi r0 r0+P -1 s=r0 I-1 k=0 z i s E y i s,k -xr0+P 2 Q = 1 Āi r0 1 IP zi r0-P r0-1 s=r0-P I-1 k=0 z i s E y i s,k -xr0+P 2 Q (i) ≤ 1 Āi r0 1 IP zi r0-P r0-1 s=r0-P I-1 k=0 z i s (1 + λ)E y i s,k -xr0 2 Q + 1 + 1 λ E ∥ xr0+P -xr0 ∥ 2 Q = 1 Āi r0 (1 + λ) 1 IP zi r0-P r0-1 s=r0-P I-1 k=0 z i s E y i s,k -xr0 2 Q + 1 Āi r0 1 + 1 λ E ∥ xr0+P -xr0 ∥ 2 Q = 1 Āi r0 (1 + λ)S i r0 + 1 Āi r0 1 + 1 λ E ∥ xr0+P -xr0 ∥ 2 Qwhere (i) uses Young's inequality with an arbitrary λ > 0. Taking conditional expectation E[•|Q :r0 ] followed by total expectation yieldsEQUATION)Adding Equation 29and Equation 30 yieldsE S i r0+P = E[B i 1 ] + E[B i 2 ] ≤ 324η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + 225η 2 I + 195η 2 IP ρ 2 σ 2 + 654η 2 L 2 I 2 P 2 1 N N j=1 E S j r0 + 108η 2 L 2 I 2 N j=1 E E w i,j r0 Q :r0 S j r0 + (1 -p sample ) (1 + λ)E S i r0 + 3 + 1 λ E ∥ xr0+P -xr0 ∥ 2 .Averaging over i,1 N N i=1 E S i r0+P ≤ 324η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + 225η 2 I + 195η 2 IP ρ 2 σ 2 + 654η 2 L 2 I 2 P 2 1 N N j=1 E S j r0 + 108η 2 L 2 I 2 N j=1 E E 1 N N i=1 w i,j r0 Q :r0 S j r0 + (1 -p sample ) (1 + λ) 1 N N i=1 E S i r0 + 3 + 1 λ E ∥ xr0+P -xr0 ∥ 2 ≤ 324η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + 225η 2 I + 195η 2 IP ρ 2 σ 2 + (1 -p sample ) (1 + λ) + 654η 2 L 2 I 2 P 2 1 N N j=1 E S j r0 + 108η 2 L 2 I 2 N j=1 E E w j r0 Q :r0 S j r0 + 3 + 1 λ E ∥ xr0+P -xr0 ∥ 2 ≤ 324η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + 225η 2 I + 195η 2 IP ρ 2 σ 2 + (1 -p sample ) (1 + λ) + 762η 2 L 2 I 2 P 2 1 N N j=1 E S j r0 + 3 + 1 λ E ∥ xr0+P -xr0 ∥ 2 ,where the last inequality uses the condition E w i r0 Q :r0 ≤ P 2 N . We can then apply Lemma 2 and choose λ = 3psample 10(1-psample) to obtain1 N N i=1 E S i r0+P ≤ 324η 2 I 2 P 2 + 3 + 1 λ 6γ 2 η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + 225η 2 I + 195η 2 IP ρ 2 + 3 + 1 λ 5γ 2 η 2 IP ρ 2 + 3 + 1 λ 7γη 3 LI 2 P σ 2 + (1 -p sample ) (1 + λ) + 762η 2 L 2 I 2 P 2 + 3 + 1 λ 11γ 2 η 2 L 2 I 2 P 2 1 N N j=1 E S j r0 ≤ 324η 2 I 2 P 2 + 20 p sample γ 2 η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + 225η 2 I + 195η 2 IP ρ 2 + 17 p sample γ 2 η 2 IP ρ 2 + 23 p sample γη 3 LI 2 P σ 2 + 1 - 7 10 p sample + 762η 2 L 2 I 2 P 2 + 110 3p sample γ 2 η 2 L 2 I 2 P 2 1 N N j=1 E S j r0 ≤ 324η 2 I 2 P 2 + 20 p sample γ 2 η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + 226η 2 I + 195η 2 IP ρ 2 + 17 p sample γ 2 η 2 IP ρ 2 σ 2 + 1 - 1 2 p sample 1 N N j=1 E S j r0 ,where the last inequality uses the conditions η ≤ √ psample 60LIP and γη ≤ psample 60LIP , and we used that 3 + 1 λ ≤ 10 3psample .Theorem 2 (Theorem 1 restated). Suppose Assumptions 1 and 2 hold, and E[w i r0 |Q :r0 ] ≤ P 2 N , andE N i=1 v i r0 2 Λ i r0 ≤ ρ 2 . If γη ≤ p sample 60LIP , η ≤ √ p sample 60LIP ,then Algorithm 1 satisfiesP R r0∈{0,P,...,R-P } E[∥∇f ( xr0 )∥ 2 ] ≤ 5∆ γηIR + 20γηLρ 2 + 5785η 2 L 2 IP σ 2 .Proof. Recall thatEQUATIONUsing the quadratic upper bound for smooth functions and taking total expectation,EQUATIONwhere (i) uses the law of total expectationE[•] = E[E r0 [•]], and (ii) uses the condition E r0 [q i r0 ] = 1together withE r0 r0+P -1 r=r0 N i=1 q i r I-1 k=0 ∇F i (x i r,k ; ξ i r,k ) = r0+P -1 r=r0 N i=1 I-1 k=0 E r0 q i r ∇F i (x i r,k ; ξ i r,k ) = r0+P -1 r=r0 N i=1 I-1 k=0 E r0 E q i r ∇F i (x i r,k ; ξ i r,k ) x i r,k = r0+P -1 r=r0 N i=1 I-1 k=0 E r0 q i r E ∇F i (x i r,k ; ξ i r,k ) x i r,k = r0+P -1 r=r0 N i=1 I-1 k=0 E r0 q i r ∇f i (x i r,k ) = E r0 r0+P -1 r=r0 N i=1 q i r I-1 k=0 ∇f i (x i r,k ) .Focusing on the inner product term of Equation 32:-γηE ∇f ( xr0 ), E r0 r0+P -1 r=r0 N i=1 q i r I-1 k=0 ∇f i (x i r,k ) = - γη IP E IP ∇f ( xr0 ), E r0 r0+P -1 r=r0 N i=1 q i r I-1 k=0 ∇f i (x i r,k ) ≤ - γηIP 2 E ∥∇f ( xr0 )∥ 2 + γη 2IP E   E r0 r0+P -1 r=r0 N i=1 q i r I-1 k=0 ∇f i (x i r,k ) -IP ∇f ( xr0 )where we used -⟨a, b⟩= 1 2 ∥b -a∥ 2 -1 2 ∥a∥ 2 -1 2 ∥b∥ 2 ≤ 1 2 ∥b -a∥ 2 -1 2 ∥a∥ 2 . Also E   E r0 r0+P -1 r=r0 N i=1 q i r I-1 k=0 ∇f i (x i r,k ) -IP ∇f ( xr0 ) 2   = E   E r0 r0+P -1 r=r0 N i=1 q i r I-1 k=0 ∇f i (x i r,k ) -∇f ( xr0 ) 2   (i) ≤ 3E   E r0 r0+P -1 r=r0 N i=1 q i r I-1 k=0 ∇f i (x i r,k ) -∇f i ( xr,k ) 2   + 3E   E r0 r0+P -1 r=r0 N i=1 q i r I-1 k=0 (∇f i ( xr,k ) -∇f i ( xr0 )) 2   + 3E   E r0 r0+P -1 r=r0 N i=1 q i r I-1 k=0 (∇f i ( xr0 ) -∇f ( xr0 )) 2   (ii) ≤ 3E   r0+P -1 r=r0 N i=1 q i r I-1 k=0 ∇f i (x i r,k ) -∇f i ( xr,k ) 2   + 3E   r0+P -1 r=r0 N i=1 q i r I-1 k=0 (∇f i ( xr,k ) -∇f i ( xr0 )) 2   + 3E   I N i=1 E r0 r0+P -1 r=r0 q i r (∇f i ( xr0 ) -∇f ( xr0 )) 2   (iii) ≤ 3IP r0+P -1 r=r0 N i=1 I-1 k=0 E q i r ∇f i (x i r,k ) -∇f i ( xr,k ) 2 + 3IP r0+P -1 r=r0 N i=1 I-1 k=0 E q i r ∥∇f i ( xr,k ) -∇f i ( xr0 )∥ 2 + 3I 2 P 2 E   N i=1 E r0 1 P r0+P -1 r=r0 q i r (∇f i ( xr0 ) -∇f ( xr0 )) 2   (iv) ≤ 3L 2 IP r0+P -1 r=r0 N i=1 I-1 k=0 E q i r x i r,k -xr,k 2 + 3L 2 IP r0+P -1 r=r0 N i=1 I-1 k=0 E q i r ∥ xr,k -xr0 ∥ 2 = 3L 2 IP r0+P -1 r=r0 I-1 k=0 E N i=1 q i r E x i r,k -xr,k 2 Q + 3L 2 IP r0+P -1 r=r0 I-1 k=0 E N i=1 q i r E ∥ xr,k -xr0 ∥ 2 Q ≤ 3L 2 IP E r0+P -1 r=r0 I-1 k=0 (D r,k + M r,k ) ,where (i) uses the decomposition∇f i (x i r,k )-∇f ( xr0 ) = (∇f i (x i r,k )-∇f i ( xr,k ))+(∇f i ( xr,k )-∇f i ( xr0 ))+(∇f i ( xr0 )-∇f ( xr0 )),(ii) and (iii) use Jensen's inequality, and (iv) uses smoothness of each f i along with the condition E r0 qi r0 = 1 N . Plugging into Equation 33yields-γηE ∇f ( xr0 ), E r0 r0+P -1 r=r0 N i=1 q i r I-1 k=0 ∇f i (x i r,k ) ≤ - γηIP 2 E ∥∇f ( xr0 )∥ 2 + 3 2 γηL 2 E r0+P -1 r=r0 I-1 k=0 (D r,k + M r,k ) (i) ≤ - γηIP 2 E ∥∇f ( xr0 )∥ 2 + 3 2 γηL 2 108η 2 I 3 P 3 E ∥∇f ( xr0 )∥ 2 + 75η 2 I 2 P + 65η 2 I 2 P 2 ρ 2 σ 2 + 254η 2 L 2 I 3 P 3 1 N N i=1 E S i r0 ≤ γηIP - 1 2 + 162η 2 L 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + γηIP 113η 2 L 2 I + 98η 2 L 2 IP ρ 2 σ 2 + 381γη 3 L 4 I 3 P 3 1 N N i=1 E S i r0 ,where (i) uses Equation 4from Lemma 1.Plugging into Equation 32 and applying Lemma 2 yieldsEQUATIONEQUATIONwhere (i) uses η ≤ √ psample 60LIP and γη ≤ psample 60LIP .Using Lemma 3,2γηL 2 IP 1 N N i=1 E S i r0+P ≤ 2γηL 2 IP 324η 2 I 2 P 2 + 20 p sample γ 2 η 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + 226η 2 I + 195η 2 IP ρ 2 + 17 p sample γ 2 η 2 IP ρ 2 σ 2 + 1 - 1 2 p sample 1 N N j=1 E S j r0 ≤ γηIP 648η 2 L 2 I 2 P 2 + 40 p sample γ 2 η 2 L 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + γηIP 552η 2 L 2 I + 390η 2 L 2 IP ρ 2 + 34 p sample γ 2 η 2 L 2 IP ρ 2 σ 2 + 2γηL 2 IP 1 N N j=1 E S j r0 -p sample γηL 2 IP 1 N N j=1 E S j r0 ≤ γηIP 648η 2 L 2 I 2 P 2 + 40 p sample γ 2 η 2 L 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + γηIP 552η 2 L 2 I + 390η 2 L 2 IP ρ 2 + γηLρ 2 σ 2 + 2γηL 2 IP 1 N N j=1 E S j r0 -p sample γηL 2 IP 1 N N j=1 E S j r0 ,where the last inequality uses γη ≤ psample 60LIP . Adding this to Equation 35 and rearranging,E[f ( xr0+P )] + 2γηL 2 IP 1 N N i=1 E S i r0+P ≤ E[f ( xr0 )] + 2γηL 2 IP 1 N N i=1 E S i r0 γηIP - 1 2 + 810η 2 L 2 I 2 P 2 + 3γηLIP + 40 p sample η 2 L 2 I 2 P 2 E ∥∇f ( xr0 )∥ 2 + γηIP 7 2 γηLρ 2 + 669η 2 L 2 I + 488η 2 L 2 IP ρ 2 σ 2 ≤ E[f ( xr0 )] + 2γηL 2 IP 1 N N i=1 E S i r0 - 1 5 γηIP E ∥∇f ( xr0 )∥ 2 + γηIP 4γηLρ 2 + 669η 2 L 2 I + 488η 2 L 2 IP ρ 2 σ 2 ,where we used γη ≤ 1 60LIP and η ≤ 1 60LIP . Finally, we can average over r 0 ∈ {0, P, 2P, . . . , R -P } and rearrange to obtainP R r0∈{0,P,...,R-P } E[∥∇f ( xr0 )∥ 2 ] ≤ 5 E[f ( x0 ) -f ( xR )] γηIR + 10 L 2 P R 1 N N i=1 E S i 0 -S i R + 20γηLρ 2 + 3345η 2 L 2 I + 2440η 2 L 2 IP ρ 2 σ 2 (i) ≤ 5∆ γηIR + 20γηLρ 2 + 3345η 2 L 2 I + 2440η 2 L 2 IP ρ 2 σ 2 (ii) ≤ 5∆ γηIR + 20γηLρ 2 + 5785η 2 L 2 IP σ 2 ,where Proof. We first show that Equation 1 and Equation 2 are satisfied under regularized participation. Let r 0 ∈ {0, . . . , R -P }. Using the fact that qi r0 = 1 N almost surely:E w i r0 Q :r0 = E   1 N N j=1 1 qj r0 > 0 P qj r0 r0+P -1 s=r0 q i s q j s Q :r0   = 1 P E   N j=1 r0+P -1 s=r0 q i s q j s Q :r0   = 1 P E   r0+P -1 s=r0 q i s N j=1 q j s Q :r0   = 1 P E r0+P -1 s=r0 q i s Q :r0 = E q i r0 Q :r0 = 1 N ≤ P 2 N ,where we used the fact that N i=1 q i r = 1. This shows that Equation 1 is satisfied. Also,qi r0 = 1 N means that v i r0 = 0, so that E v i r0 2 Λ i r0 = 0 ≤ ρ 2, and Equation 2 is satisfied. Therefore we can apply Corollary 1. The complexity result follows by plugging in p sample = 1 and choosingI = O ∆ρ 2 σ 2 P ϵ 2 .Corollary 4 (Cyclic Participation). Under cyclic participation with K groups and S participating clients in each round, for any ϵ > 0, there exist choices of η, γ, P, I, and R such thatE[∥∇f ( x)∥ 2 ] ≤ O(ϵ 2 ) and R = O L K ϵ 2 N S , RI = O ∆Lσ 2 Sϵ 4 .Proof. Again, we show that Equation 1 and Equation 2 are satisfied under cyclic participation. Let r 0 ∈ {0, . . . , R -P }. Denoting g(i) = ⌊ K N (i -1)⌋ and r(i) = r 0 + g(i), it holds that, over the rounds r ∈ {r 0 , . . . , r 0 + P -1}, client i belongs to group g(i) and is available only during round r(i). Also, let Π(i) denote the set of indices of clients in group g(i). To simplify w i r0 , recall that for client i in group (r mod K):q i r = 1 Swith probability S N 0 with probability 1 -S N , and q i r = 0 for all clients i not in group (r mod K). SoE w i r0 Q :r0 = E   1 N N j=1 1 qj r0 > 0 P qj r0 r0+P -1 s=r0 q i s q j s Q :r0   = 1 N P E   r0+P -1 s=r0 q i s N j=1 1 qj r0 > 0 qj r0 q j s Q :r0   (i) = 1 N P E   q i r(i) N j=1 1 qj r0 > 0 qj r0 q j r(i) Q :r0   (ii) = 1 N P E   q i r(i) j∈Π(i) 1 qj r0 > 0 qj r0 q j r(i) Q :r0   (iii) = 1 N P E   q i r(i) j∈Π(i) 1 qj r0 > 0 1/SP 1 S Q :r0   = 1 N E   q i r(i) j∈Π(i) 1 qj r0 > 0 Q :r0   (iv) = S N E q i r(i) Q :r0 = S N S N 1 S + 1 - S N • 0 = S N 2 ≤ P 2 N ,where (i) uses q i r = 0 for all r ̸ = r(i), (ii) uses q j r(i) = 0 for all j / ∈ Π(i), (iii) uses the fact that qj r0 > 0 implies q j r(i) = 1 S and qj r0 = 1 SP , and (iv) uses the fact that S clients are sampled in each round. This shows that Equation 1 is satisfied.To see that Equation 2 is satisfied:E N i=1 v i r0 2 Λ i r0 (i) = E N i=1 E qi r0 - 1 N 2 Q :r0 Λ i r0 (ii) = 1 SN P 1 - S K N N i=1 E Λ i r0 = 1 SN P 1 - S K N N i=1   1 P r0-1 s=r0-P z i s 2 1 P r0-1 s=r0-P z i s 2   (iii) = 1 SP 1 - S K N 1 P 1 S 2 1 P 1 S 2 = 1 S 1 - S K N ≤ 1 S = ρ 2 ,where (i) uses the tower property, (ii) uses the variance of qi r0 as computed in Appendix C, and (iii) uses the fact that zi r0 > 0 by construction of zi r0 , and in this case z i r = 1 S for exactly one r ∈ {r 0 -P, . . . , r 0 -1} and z i r = 0 for all other r. Therefore Equation 2 is satisfied. This shows we can apply Corollary 1. The complexity result follows by plugging in p sample = S N , P = K, ρ = 1 √ S , and choosingI = O ∆σ 2 KN ϵ 2 .In this section we derive the computation and communication complexity required for Amplified FedAvg [38] to find an ϵ-stationary point under various client participation patterns, which we listed in Table 1 of the main paper. Table 1 compares the complexity under i.i.d. participation, regularized participation, and cyclic participation. Since i.i.d. participation is a special case of cyclic participation with K = 1 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 a constant κ such that ∥∇f i (x) -∇f (x)∥ ≤ κ, for all x. The previous analysis of Amplified FedAvg [38] instead assumes an upper bound δ(P ) on a weighted heterogeneity that depends on client sampling. Specifically, they assume that there exists δ(P ) such that1 P r0+P -1 r=r0 N i=1 q i r (∇f i (x) -∇f (x)) 2 ≤ δ2 (P ),for all x and r 0 . We restate their Corollary 3.2 for convenience: Corollary 5 (Corollary 3.2 [38] informally restated). There exist parameter choices such that Amplified FedAvg satisfiesEQUATIONAs pointed out in their Section 4.2, we can interpret δ(P ) in terms of the conventional heterogeneity constant κ as:δ2 (P ) ≤ N κ 2 N i=1 qi r0 - 1 N 2 .Our Assumption 2(b) implies that E Qr 0 [q i r0 ] = 1 N . If we choose v ≥ 0 such that Var[q i r0 ] ≤ v 2 , then we can take expecation of the above to obtainE δ2 (P ) ≤ N 2 κ 2 v 2 .This "conversion" of δ(P ) to κ and v will allow us to compare their complexity to that of algorithms that use the conventional heterogeneity assumption by computing v for each participation pattern.Regularized Participation In this case, qi r0 = 1 N almost surely, so that v = 0 and accordingly δ2 (P ) = 0. Thereforemin r E ∥∇f ( xr )∥ 2 ≤ O √ ∆Lρσ √ RI + ∆LP + κ 2 R + σ 2 RIP .Therefore the choicesR ≥ O ∆LP + κ 2 ϵ 2 , RI ≥ O ∆Lρ 2 σ 2 ϵ 4 + σ 2 P ϵ 2 , imply min r E ∥∇f ( xr )∥ 2 ≤ O ϵ 2 .Cyclic Participation We can compute v 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) 2 by choosing P = m K for any m ∈ N, and indeed to achieve E[ δ2 (P )] ≤ ϵ 2 we must choose P = m K with m depending on ϵ. The objective maps R 4 to R, and there are only two clients with corresponding local objectivesf 1 (x) = µ 2 (x 1 -c) 2 + H 2 x 2 - √ µc √ H 2 + H 8 x 2 3 + [x 3 ] 2 + + κx 4 f 2 (x) = µ 2 (x 1 -c) 2 + H 2 x 2 - √ µc √ H 2 + H 8 x 2 3 + [x 3 ] 2 + -κx 4 ,where [x] + := max {x, 0}. The stochastic gradients for f 1 and f 2 are sampled from the distributions ∇f 1 (x)+ξe 3 and ∇f 2 (x)+ξe 3 , respectively, where ξ ∼ N (0, σ 2 ) and e 3 denotes the third standard basis vector in R 4 . We set the parameters of the objective as follows:H = 16, κ = 16, σ = 1 c = 1, µ = 2, L = 2.We use a simple 2-layer CNN for CIFAR-10. The first layer is a convolutional layer with 64 channels, a 5 × 5 kernel, stride of 2, padding of 2, and a ReLU activation. The second layer is a fully connected layer with no activation.In this section, we provide two additional experimental results. First, in Section E.1, we add four baselines to the experimental settings of the main paper: FedAdam [31] , FedYogi [31] , FedAvg-M [4] , and Amplified FedAvg with FedProx regularization. Second, in Section E.2, we evaluate all 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).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 of the total number of hyperparameter combinations evaluated. Also, the results are averaged over five random seeds. The results are shown in Figures 3 and 4 .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 additional comparisons 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.Here, we include an evaluation under another non-i.i.d. 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 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, 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 5 . Again, Amplified SCAFFOLD outperforms all baselines under SCA participation. The relative performance of each baseline is similar as under cyclic 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.Here we include an extended comparison against two relevant prior works.FedAvg with Cyclic Participation [7] 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 µ-PL objectives. Using their notation, K is the number of client groups, κ is the condition number of the objective, γ is the intra-group heterogeneity, M is the total number of clients, N is the number of clients that participate in each round, and T is the number of communication rounds. Then the dominating term in their convergence rate for FedAvg under cyclic Õ Kκγ 2 µN T M/ K -N M/ K -1 .Notice that the number of local steps (denoted τ ) does not appear in 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 a 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 1 , the communication complexity of SCAFFOLD and Amplified SCAFFOLD under i.i.d. participation differs by their dependence on N S . The complexity of Amplified SCAFFOLD is O N S , while that of SCAFFOLD is O N S 2/3 . This difference in the order of N S is due to a potential small issue in the analysis of SCAFFOLD, which we intentionally avoided by accepting a slightly worse dependence on N S . This difference stems from an apparent mistake in the original SCAFFOLD 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 includesEQUATION)where the last line is obtained by conditioning on the event α r i,k-1 = α r-1 i,k-1 and the complement α r-1 i,k-1 = y r i,k-1 , which have probabilities 1 -S N and S N , respectively. However, this condition is not denoted in Equation 37. A corrected version should be writtenΞ r = 1 - S N 1 KN i,k E ∥α r-1 i,k-1 -x r ∥ 2 | α r i,k-1 = α r-1 i,k-1 + S N 1 KN i,k E ∥y r i,k-1 -x r ∥ 2 | α r-1 i,k-1 = y r i,k-1 ,but this conditional expectation is not specified in the proof of SCAFFOLD. For the remainder of the proof of Lemma 16, these terms are treated as total expectation, leading to an inconsistency. Lemma 16 concludes by applying Lemma 15 in order to bound the term E ∥E r-1 [∆x r ]∥ 2 . However, when we make the correction to include the conditional expectation, we do not have a bound of Ξ r in terms of E ∥E r-1 [∆x r ]∥ 2 , we instead have a bound in terms of E E r-1 ∆x r | α r-1 i,k-1 = y r i,k-1.But this term with a conditional expectation inside the norm can't be bounded with Lemma 15.A pessimistic solution is to use Jensen's inequality to boundE E r-1 ∆x r | α r-1 i,k-1 = y r i,k-1 2 ≤ E E r-1 ∥∆x r ∥ 2 | α r-1 i,k-1 = y r i,k-1 = E ∥∆x r ∥ 2 ,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 S dependence.Fixing their analysis to recover the same N S 2/3 dependence may be possible, but we have instead focused on achieving the best known complexity in terms of ϵ, κ, σ, and other problem parameters.• 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. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 error rates). • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our paper is a theoretical paper on mathematical optimization problems arising in distributed learning. We do not see 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024).Fashion-MNIST is licensed under the MIT License.  ,(33) 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

- Mishchenko, Konstantin, et al. "Proxskip: Yes! Local gradient steps provably lead to communication acceleration! Finally!" International Conference on Machine Learning. PMLR, 2022.
- Condat, Laurent Pierre, Grigory Malinovsky, and Peter Richtárik. "Tamuna: Accelerated federated learning with local training and partial participation." (2023).

Furthermore, 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.

- Tyurin, Alexander, et al. "Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling." Transactions on Machine Learning Research.
- 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.

Additionally, 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.

- Patel, Kumar Kshitij, et al. "Towards optimal communication complexity in distributed non-convex optimization." Advances in Neural Information Processing Systems 35 (2022): 13316-13328.

By 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.

2) 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:
$$ \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. $$

This 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.

I 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.

Additionally, 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.

3) 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.

4) 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.

5) 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.

It 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.
questions: questions: Please check the Weaknesses section.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: See the questions section.
questions: 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.

2.) 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?

3.) Typo: In line 133, the authors have mentioned $\bar{q}_{r0}$.

4.) 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?

5.) 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?

6.) 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.

7.) Did the authors also check the efficacy of the proposed algorithm with different participation strategies, as mentioned in the paper?


[1] Cheng, Ziheng, et al. "Momentum benefits non-iid federated learning simply and provably." arXiv preprint arXiv:2306.16504 (2023).
limitations: limitations: Yes, the authors have mentioned the limitations of the work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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}$.
2. 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].


[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.

[2]. Wang, S., & Ji, M. (2022). A unified analysis of federated learning with arbitrary client participation. Advances in Neural Information Processing Systems.

[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.
questions: 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: limitations: The authors adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. It would be better to provide a detailed description of the algorithm rather than just an overview.
2. 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.

Minor:
1. Line 60-61: Delete "non-uniform average of".
2. Line 99: Assumption 1 (a) is not precise. It should be for all $y$, not for all $x,y$.
3. Line 110: $P$ first appears without explanation.
4. Line 145: Delete "is".
questions: questions: 1. For cycle participation, why are the subsets equally sized? Can they have different sizes? In addition, can the clients sampled with replacement?
2. In the experiments, $\bar{K}$ is chosen to be 5. What about the other choices? What is its influence?
limitations: 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.

Comments: title: Response to authors
comment: Thank the authors for the explanation. It might be interesting to further investigate the underlying reasons.
It is difficult to explain this observation from a theoretical perspective: SCAFFOLD does not have any theoretical guarantees under cyclic participation, while the communication complexity of Amplified SCAFFOLD indeed increases with $\bar{K}$. One explanation is that the complexity in Table 1 represents the worst-case over all objectives satisfying the assumptions, and the performance for this particular task could be much better than the worst case.

Empirically, it appears that the information contained the control variates of SCAFFOLD and Amplified SCAFFOLD is sufficient to avoid the affect of longer participation cycles. Essentially, the modified update direction using the control variate appears to be a good estimator for the global gradient, even when the control variates are not updated for a long time due to larger values of $\bar{K}$. However, it is difficult to say for sure without further investigation.
Thank the authors for conducting the additional experiments. It's great to see that Amplified SCAFFOLD outperforms all the baselines across different values of $\bar{K}$. I am willing to increase my score.

The conclusion that "SCAFFOLD and Amplified SCAFFOLD get better as $\bar{K}$ increases" might not be accurate. I am curious about how Amplified SCAFFOLD and SCAFFOLD are able to maintain performance as $\bar{K}$ increases. Could the authors provide some insights or reasons behind this observation?
We agree that the theory may not perfectly predict the practical performance, so that it is important to evaluate different values of $\bar{K}$. Below we included the results of an additional experiment that evaluates Amplified SCAFFOLD and the four major baselines considered in the paper: FedAvg, SCAFFOLD, and Amplified FedAvg. We evaluated each algorithm for the Fashion-MNIST dataset, keeping all of the same settings as stated in the main paper, other than setting $P = 24$ and varying $\bar{K}$ over $\bar{K} = 2, 4, 6, 8$. We only change $P$ from $20$ to $24$ so that $P / \bar{K}$ is an integer, for the sake of simplicity. The training loss and testing accuracy reached at the end of training is shown in the tables below:

| Train Loss | $\bar{K}=2$ | $\bar{K}=4$ | $\bar{K}=6$ | $\bar{K}=8$ |
|---|---|---|---|---|
| FedAvg | 0.00216 | 0.00222 | 0.00229 | 0.00236 |
| SCAFFOLD | 0.00156 | 0.00154 | 0.00161 | 0.00160 |
| Amplified FedAvg | 0.00206 | 0.00208 | 0.00210 | 0.00213 |
| Amplified SCAFFOLD | **0.00150** | **0.00147** | **0.00150** | **0.00148** |

| Test Accuracy | $\bar{K}=2$ | $\bar{K}=4$ | $\bar{K}=6$ | $\bar{K}=8$ |
|---|---|---|---|---|
| FedAvg | 79.596% | 78.527% | 77.69% | 76.999% |
| SCAFFOLD | 83.064% | 83.357% | 82.695% | 83.072% |
| Amplified FedAvg | 80.902% | 80.507% | 80.243% | 79.891% |
| Amplified SCAFFOLD | **83.643%** | **83.964%** | **83.715%** | **83.957%** |

We draw several conclusions from these results:
1. Amplified SCAFFOLD achieves the best training accuracy and testing loss across all algorithms, for every choice of $\bar{K}$.
2. FedAvg and Amplified FedAvg get worse as $\bar{K}$ increases, while SCAFFOLD and Amplified SCAFFOLD get better as $\bar{K}$ increases. It makes intuitive sense for an algorithm to degrade as $\bar{K}$ increases, since a larger $\bar{K}$ 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 $\bar{K}$ increases.
3. Amplified SCAFFOLD is the only algorithm whose final training loss with $\bar{K} = 8$ is better than the final training loss with $\bar{K} = 2$.

These experimental results show that Amplified SCAFFOLD is robust to changes in the number of groups $\bar{K}$ under cyclic participation. While the worst-case communication complexity of Amplified SCAFFOLD (listed in Table 1) actually increases with $\bar{K}$, our experiments demonstrate that in practice, Amplified SCAFFOLD can maintain performance as $\bar{K}$ increases. We hope that this addresses your concern that different values of $\bar{K}$ should be evaluated: please let us know if you are satisfied.

Best,
Authors
Thanks for the further clarification. This clears my confusion and I do not have questions. Thus, I will increase my score accordingly.
Thank you for the clarification. I am going to raise my score accordingly.
You're right, thank you for clarifying your question: the results in [1] do show that SCAFFOLD is close to FedAvg and FedProx. The discrepancy between [1] and our results is likely due to differences in neural network architectures, due to the fact that the performance of SCAFFOLD seems to be very sensitive to network depth [(Yu et al, 2022)](https://arxiv.org/abs/2207.06343). Indeed, Table 3 of the original SCAFFOLD paper [(Karimireddy et al, 2019)](https://arxiv.org/abs/1910.06378) shows that SCAFFOLD outperforms FedAvg and FedProx when training a logistic regression model (1 layer), while [(Yu et al, 2022)](https://arxiv.org/abs/2207.06343) showed that SCAFFOLD can struggle even with 4 layer networks. Our Fashion-MNIST results you refer to are using a logistic regression model, so our results are consistent with Table 3 of [(Karimireddy et al, 2019)](https://arxiv.org/abs/1910.06378). Notice that in our CIFAR-10 experiments, we use a two layer NN and already SCAFFOLD not much better than FedAvg and FedProx, which is consistent with Table III of [1], while Amplified SCAFFOLD maintains a significant advantange.

Thank you for the thought-provoking question! We hope that this clears up our experimental results in the context of the literature.
Thank you for the response. I understand that FedAvg and Fedprox perform very closely without system heterogeneity, but according to [1], SCAFFOLD also performs very closely in settings without system heterogeneity. I am not convinced about this gap in Amplified SCAFFOLD and Amplified Fedprox for the FMNIST dataset. I am sorry if I am missing something.
**Amplified FedProx**: Our implementation of Amplified FedProx is obtained by starting from the implementation of Amplified FedAvg [(Wang & Ji, 2022)](https://arxiv.org/abs/2205.13648), and adding the FedProx regularization term $\mu/2 \lVert x - x_r \rVert^2$ to the objective of each local client, where $x_r$ denotes the global model from the last synchronization step. Table III from [1] shows that FedAvg and FedProx perform very closely in most settings without systems heterogeneity, and this is consistent with our results: The curves for FedProx are almost overlapping with those of FedAvg, and the curves for Amplified FedProx are almost overlapping with those of Amplified FedAvg. We believe that the experimental results of [1] are consistent with ours.

**Avoiding heterogeneity assumption**: The essential technique that allows SCAFFOLD (and Amplified SCAFFOLD) to avoid the heterogeneity assumption is to modify the direction of each local update to approximate an update on the global gradient: we show some details below.

The standard analysis of FedAvg wants to show descent of the global objective $f$, but the update directions depend on $\nabla f_i$ (i.e. the local gradients), so the rate of descent will be slowed down by the difference between $\nabla f$ and $\nabla f_i$. More concretely, the analysis involves the difference between the global gradient $\nabla f(x_{r,k}^i)$ and the update direction $\nabla f_i(x_{r,k}^i)$, which is: $\lVert \nabla f_i(x_{r,k}^i) - \nabla f(x_{r,k}^i) \rVert$. **Bounding this term requires the heterogeneity assumption**, but this might not be necessary if we change the update direction...

For SCAFFOLD, the update direction is changed to $\nabla f_i(x_{r,k}^i) - G_r^i + G_r$, where $G_r^i$ is the average of stochastic gradients encountered by client $i$ during the round before $r$, and $G_r$ is the average of $G_r^i$ over $i$. Therefore, we can bound $\lVert G_r^i - \nabla f_i(x_{r,k}^i) \Vert$ and $\lVert G_r - \nabla f(x_{r,k}^i) \rVert$ **by smoothness alone, without requiring any additional assumptions**. This is very helpful for the convergence analysis for the following reason: when we have to compare the descent direction $\nabla f(x_{r,k}^i)$ against the local update direction $\nabla f_i(x_{r,k}^i) - G_r^i + G_r$, we can use the triangle inequality to bound $$
    \lVert (\nabla f_i(x_{r,k}^i) - G_r^i + G_r) - \nabla f(x_{r,k}^i) \rVert \leq \lVert \nabla f_i(x_{r,k}^i) - G_r^i \rVert + \lVert \nabla f(x_{r,k}^i) - G_r \rVert.
$$ Again, both of the terms on the RHS can be bounded with smoothness alone. Therefore, **the difference between the global gradient and the update direction can be bounded only with smoothness: no heterogeneity assumption necessary**.

Please note that the above analysis omits certain details for the sake of brevity, but the key idea is there: control variates eliminate the need for bounded gradient dissimilarity. We use a similar essential idea in our analysis, but the proof is technically more complicated due to the added difficulty of non-i.i.d. participation. Please let us know if you have further questions on this topic.
There are a couple of reasons why I did not increase my score. Firstly, I am not sure about the results of Amplified Fedprox for the Fashion-MNIST dataset. Can you please describe the algorithm that you used for Amplified Fedprox? The reason for my concern is that a standard setting [1] shows that the test accuracy is close. Secondly, I understand that the SCAFFOLD did not use the data heterogeneity assumption, but how did they or the authors avoid using it?



[1] Li, Qinbin, et al. "Federated learning on non-iid data silos: An experimental study." 2022 IEEE 38th international conference on data engineering (ICDE). IEEE, 2022.
Thank the authors for response. I acknowledge that $\bar{K}$ should be fixed in one setting. However, evaluating different values of $\bar{K}$ does not imply that $\bar{K}$ is dynamic during a single training session. Instead, it allows for a more comprehensive comparison of the performance of Amplified SCAFFOLD across different settings. Since the experiments are simulations, it is both possible and reasonable to choose a value for $\bar{K}$ other than 5.

I also acknowledge that changes to $\bar{K}$ should not affect the relative performance of Amplified SCAFFOLD compared to Amplified FedAvg **theoretically**. However, there may be inconsistencies between empirical and theoretical performance. Therefore, I believe it is still necessary to evaluate different values of $\bar{K}$.
Please let us know if we have answered your question, and if you have any remaining concerns. Since we addressed both weaknesses and the question in your original review, we kindly request that you consider raising the score. Thank you.

Best,
Authors
There seems to be some confusion around the notation, so let us clarify. In our paper, $\bar{K}$ represents the number of groups for a cyclic participation pattern, and we do not use the variable $K$ anywhere in the paper (other than when using the notation of related works in Appendix E, where $K$ represents the number of local steps). In your previous comment you asked about $K$, and we assumed that you meant $\bar{K}$, and we used the notation $K$ to remain consistent with your question. We apologize for the inconsistency. With this in mind, we can restate the answer to your previous question as: the number of groups $\bar{K}$ does not affect the heterogeneity among client data, it only affects how clients participate in training. Again, we follow the experimental setting of [(Wang & Ji, 2022)](https://arxiv.org/abs/2205.13648), which uses a single choice for $\bar{K}$.

The communication complexity of Amplified SCAFFOLD depends on $\bar{K}$, and the same dependence is present in the complexity of Amplified FedAvg, while Amplified FedAvg also contains a much larger term of order $\epsilon^{-4}$. Therefore changes to $\bar{K}$ should not affect the relative performance of Amplified SCAFFOLD compared to Amplified FedAvg. Also, the choice of a single $\bar{K}$ in both our experiments and those of [(Wang & Ji, 2022)](https://arxiv.org/abs/2205.13648) is consistent with practical scenarios where cyclic participation might arise: when device availability corresponds to geographic location, the number of groups $\bar{K}$ should remain fixed even as the number of users $N$ increases, because there are a limited number of time-zones around the world.
Thank the authors for the clarification.  Just to confirm, does $\bar{K}$ represent the heterogeneity between participations? Additionally, $\bar{K}$ impacts the communication complexity of Amplified SCAFFOLD. I still believe that evaluating different values of $\bar{K}$ is necessary.
"Does a larger $K$ imply a greater data heterogeneity?" In our experiments, $K$ is not related to the data heterogeneity. Once the data similarity parameter $s$ is fixed, the partitioning of data to individual clients is determined, regardless of the value of $K$. This means that even with different values of $K$, all clients have the same objective function, so heterogeneity remains the same.

Further, our choice of $K$ follows the experimental setup of [(Wang & Ji, 2022)](https://arxiv.org/abs/2205.13648), who also evaluated with a single choice of $K$.
Thank the authors for the rebuttal. I still have some concerns about $K$. Does a larger $K$ imply greater data heterogeneity? If so, it would be better to experimentally demonstrate the impact of $K$, as this would better show the effectiveness of Amplified SCAFFOLD.
Thank you for your rebuttal!

You have addressed my concerns, and as a result, I will be increasing my score accordingly.

Let me clarify the concerns I had and highlight the aspects that addressed them:

1) Thank you for providing a discussion of related work. This aspect is resolved.

2) Let me clarify the aspect of the heterogeneity assumption. I agree that in your results, you do not use the heterogeneity assumption. This is straightforward since you use a client drift reduction mechanism, such as SCAFFOLD. The idea behind the SCAFFOLD mechanism is to allow a method to work without the heterogeneity assumption, and this is clear.

However, I must mention that when you provide information about previous results, you must be precise in describing the details and assumptions made in those results. This helps prevent confusion for readers, as they are not expected to read all the papers in the field. I requested clarification on the aspects related to the table.

3) Under Assumption 2, you briefly described what conditions (a), (b), and (c) mean, with basically one sentence for each. I suggest providing more detailed explanations. For example, why did you specifically use equal frequency in condition (b)? Additionally, there is no mention of condition (d). While I understand the meaning of this assumption, it is not easy to grasp with such a compressed explanation. In Section 3.2, you provide examples, which are valuable, but the examples do not fully explain the assumptions themselves.

4) Let me clarify this aspect once again to avoid any confusion. I understand that you used a grid search for step sizes. What I meant is that the selection of client sampling parameters—such as the number of groups, availability time, communication interval, and number of communication rounds—is not described. These could also be considered hyperparameters. To avoid confusion, let us refer to them as experimental setup parameters. All I asked for was some explanation of how these parameters were selected. In Section D.1, these parameters are simply stated without clarification (lines 756-762).

5) I did indeed miss the explanation in Appendix E. Thank you for pointing this out. This clarification is indeed valuable. I recommend mentioning it earlier in the text (not at the end of the entire paper).

Since aspects 1 and 5 are fully resolved, I have increased my score.
Thank you for the feedback. Do you have any additional concerns which limit the paper from receiving a higher score? If not, we kindly suggest that you consider raising the score, since we have fulfilled the request for more experiments and answered all questions. Thank you.

Best,
Authors
Thank you for your response; my concerns have been addressed. I want to keep my score.
To fully clarify the comparison between our submission and [3], we must fully state the settings of the two papers. Our paper focuses on periodic participation with smooth functions, while [3] focuses on i.i.d. participation with relaxed smooth functions. It is true that i.i.d. participation is a special case of periodic participation, and similarly the class of smooth functions is a subset of the class of relaxed smooth functions. The special case which is common to the settings of these works is i.i.d. participation for smooth functions. In this special case, our work achieves communication cost of $\Delta L \epsilon^{-2} N/S$ (see Table 1), while [3] requires communication cost of at least $O(\epsilon^{-3})$ (see Table 1 of [3]). Notice that [3] reports their communication complexity in terms of $I$, but their best complexity can be computed by choosing the value of $I$ reported in the fourth column of their Table 1. Therefore, **when we reduce to the special case of smooth functions with i.i.d. participation, our algorithm's communication of $O(\epsilon^{-2})$ is a significant improvement over the complexity $O(\epsilon^{-3})$ of [3]**.
Thanks to the authors for their response. I appreciate additional experiments made by the authors. However, I'm a bit confused when the authors responded #2: *'[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'*. They mentioned around line 216 that *'i.i.d. participation is a special case of cyclic participation'*, implying that i.i.d. client sampling should be a subset of non-i.i.d. client participation. Therefore, I think it is appropriate to ask for clarification on the theoretical advancement of this work over the result in [3] in the case of i.i.d. participation. In other words, will the error bound be tighter than what has been proposed in [3] under i.i.d. participation?
Thank you for your efforts in reviewing our paper. In our rebuttal, we responded to the questions and concerns in your review. In particular, we included a detailed description of the algorithm which we can use to improve presentation, additional experiments including an evaluation under a new client participation pattern, and a discussion of the parameters determining participation. Please let us know if we have addressed your concerns, or if you have any more questions. We are happy to continue discussion.

Best,
Authors
Thank you for reviewing our paper. In our rebuttal, we responded to your questions and concerns. We pointed out that your skepticism of assumption 1(a) is due to a typo, included an empirical comparison against more baselines (general response) and a discussion of [3] (weakness #2), and described our algorithm's mechanism for avoiding heterogeneity. Please let us know if we have addressed your concerns.

Best,
Authors
Thank you again for your efforst in the review process. We responded to your questions and concerns in our rebuttal. Specifically, we addressed your request for additional experiments (#5-7) and discussed the heterogeneity assumption (#4). Please let us know if we have addressed your concerns, and if you have any more questions. We are happy to continue discussion.

Best,
Authors
Thank you again for reviewing our paper. In our rebuttal, we responded to the points from your review. Of particular importance is our discussion of the different heterogeneity assumptions (#2) and a comparison with SCAFFOLD's rate in the i.i.d. case (#5). Also, we included a discussion of new experimental results in the general response. Please let us know if we have addressed your concerns. We are happy to continue discussion.

Best, Authors