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

Thank you for your helpful comments on our paper. Below we have responded to your comments and questions.

Weaknesses:

1. Detailed description of the algorithm. Thank you for the feedback on our presentation. Section 4.1 is meant to describe the key algorithmic components of Amplified Scaffold, while the concrete definition of the algorithm is left to pseudocode in Algorithm 1. To improve the clarity of the updated version, we can include a detailed description of the algorithm, such as:

   Amplified SCAFFOLD has a similar high-level structure as many FL optimization algorithms: in each round, participating clients individually perform local steps without communication (line 8), then aggregate their updates to the global model (line 12). However, the local steps (line 8) include the control variates $G_{r_0}^i$ and $G_{r_0}$, which are used to modify the local steps in order to approximate the gradient of the global objective. The control variate $G_{r_0}^i$ is the average of stochastic gradients seen by client $i$, but the average is not just taken over the last round: instead, the control variates are computed over windows of $P$ rounds (lines 17-21), in order to ensure that all clients are equally represented (in expectation). The other deviation from the conventional structure of FL algorithms is in the amplified updates (line 15). Over each window of $P$ rounds, the updates from each round are accumulated in the variable $u$. At the end of each window, all clients will have participated with equal frequency (in expectation), so $u$ should contain information from all clients. We then use $u$ to update the global model with a potentially large multiplier $\gamma$ (line 15), leveraging the fact that $u$ contains global information. Together, these two components allow Amplified SCAFFOLD to simultaneously handle non-i.i.d. client participation and heterogeneous objectives.

   Please let us know if this explanation will improve the clarity of our presentation.

2. Additional experiments. In response to your comment about additional experiments, and comments from other reviewers, we have made two additions to the experiments of our submission. First, we added four new baselines (FedAdam, FedYogi, FedAvg-M, and Amplified FedAvg + FedProx) to the evaluation of FashionMNIST and CIFAR-10. Second, we evaluated each algorithm (including these new baselines) under a new non-i.i.d. participation pattern, which models user device availability that is both periodic and unreliable. Both of these experiments are described in detail in the general response, and the loss curves are shown in Figures 1-3 of the 1-page PDF. Here, we highlight the main findings.

   The new baselines FedAdam and FedYogi are competitive for both FashionMNIST and CIFAR-10, but Amplified SCAFFOLD still maintains the best performance in terms of training loss and testing accuracy across all baselines.. This is consistent with the fact that FedAdam and FedYogi were designed for i.i.d. client sampling, whereas Amplified SCAFFOLD enjoys convergence guarantees under periodic participation.

   We also evaluate all algorithms under a non-i.i.d. participation pattern which we refer to as Stochastic Client Availability (SCA). On CIFAR-10 with SCA participation, Amplified SCAFFOLD again reaches the best training loss and testing accuracy, showing that Amplified SCAFFOLD performs well under multiple non-i.i.d. participation patterns.

Questions:

1. Variations on group subsampling. In your review, you asked "For cycle participation, why are the subsets equally sized? Can they have different sizes?" In our paper and in related works [4, 34], the subsets in cyclic participation are usually equally sized for simplicity. However, this is not a requirement. In fact, for our additional experiment (see general response #2), the number of available clients randomly sampled and changes throughout training. This participation pattern is more flexible than cyclic participation, and may better model the unpredictability of real-life client devices.

   Also, you asked "In addition, can the clients sampled with replacement?" If we understand your question correctly, you are asking whether the same client can be sampled between two consecutive rounds. If so, the answer is yes. At every round, $S$ clients are sampled, and these clients are not removed from the set of available clients for the next round. In other words, the sampling mechanism does not cycle through all clients before return to previous clients.

2. Effect of $\bar{K}$. In your review, you asked "In the experiments, $\bar{K}$ is chosen to be 5. What about the other choices? What is its influence?" We chose $\bar{K} = 5$ following [34], but this parameter can vary. One way to understand the role of this parameter is notice that $\bar{K} = 1$ corresponds to full client availability, while large values of $\bar{K}$ mean that there are many small groups of clients which are usually not available. Therefore, larger values of $\bar{K}$ means that participation is in some sense ``further from i.i.d.". We expect that larger $\bar{K}$ means that the optimization problem is more difficult, and will require more communication rounds, which aligns with the communication cost of Amplified SCAFFOLD in the last row of Table 1.

   In our experiments, data heterogeneity is created by allocating different data distributions to different clients. With $N=250$ clients and $C=10$ classes, the first 25 clients have a majority of their data from class 1, the next 25 clients have a majority of class 2, etc. The choice $\bar{K} = 5$ yields 50 clients per group, so that each group contains clients with a majority label from two different classes. We believe that this is a good intermediate value for $\bar{K}$: it is not so small that we are too close to the i.i.d. regime ($\bar{K} = 1$), but it is not so large that one class out of ten dominates training in each round.

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

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:

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

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 you for you effort in reviewing our paper. Below we have responded to your thoughts and answered your questions.

Weaknesses:

1. Meaning of Assumption 1(a). We addressed this point in the general response: our Assumption 1(a) contains a typo. Actually, the correct version of our Assumption 1(a) matches the references you mentioned, and we will fix this typo in the updated version.

2. Comparison against similar methods In your review, you wrote "it would be helpful to see related works with more recent state-of-the-art methods that might also address similar challenges, e.g. [3]". From the empirical perspective, we included additional experiments to compare against several baselines; see #1 of the general response for more information. From the theoretical perspective, we are not aware of additional works not cited in our paper that achieve convergence guarantees under non-i.i.d. client participation. The reference you mentioned [3] provides an algorithm for FL under $(L_0, L_1)$-smoothness with i.i.d. client sampling, which is an orthogonal problem to the non-i.i.d. client participation which motivates our paper. In fact, in the smooth setting (i.e. $L_1 = 0$), the algorithm of [3] degenerates to the SCAFFOLD algorithm with i.i.d. client sampling, which we have already compared against. We can refer to this work in the updated version of our paper, and discuss its relation to our work.

Questions:

1. How does Amplified SCAFFOLD avoid heterogeneity? The main algorithmic component that creates robustness against heterogeneity is the joint effect of control variates with amplified updates. We use the control variates to modify the local update for each client in order to approximate an update on the global objective (see Line 8 of Algorithm 1). Our algorithm combines these control variates with amplified updates across windows of multiple rounds; see Section 4.1 for a description of these algorithmic components. Section 4.2 presents convergence guarantees for this algorithm (reduced communication, robustness to heterogeneity, linear speedup), and Section 4.3 explores the implications for various non-i.i.d. participation patterns.

Thank you for your insightful suggestions. We have responded to your thoughts and questions below.

Questions:

1. Table of notation. Thank you for this suggestion. We agree that it would make the presentation more clear and we will provide a table of notation in the updated version.

2. Meaning of Assumption 1(a). As we said in the general repsonse, our Assumption 1(a) actually contains a typo: the correct version should say $f(x_0) - \min_{x \in \mathbb{R}^d} f(x) \leq \Delta$, which is a standard condition in convergence proofs.

3. Typo on line 133. Thank you for pointing this out. The variable $\bar{q}_{r_0}^i$ first appears on Line 132, and immediately after we refer to its definition in Algorithm 1, but the reference should point to line 17 of Algorithm 1, not line 18.

4. Usage of heterogeneity assumption. Since multiple reviewers addressed this point, we discussed it in our general response. Our main message is that we do not use any heterogeneity assumption in the proof, because the necessity of this assumption is completely eliminated by the use of control variates. This circumstance is the same as in SCAFFOLD: the analysis of SCAFFOLD does not require a heterogeneity assumption, but such an assumption is referenced in their paper because it is used by baselines.

5. and 6. Comparison with additional baselines. In your review, you requested that we compare against additional baselines such as FedAdam, FedYogi, FedAvg-M, and the combination of Amplified FedAvg with FedProx. We agree that these are important baselines to consider, so we have evaluated all four of these baselines in the experimental settings of the main paper. The results are thoroughly discussed in the general response, and the loss curves are shown in Figures 1 and 2, but we highlight the main findings here.

For both FashionMNIST and CIFAR-10, Amplified SCAFFOLD achieves the best training loss and testing accuracy among all baselines, including the four new baselines. In general, FedAdam and FedYogi were competitive, outperforming every algorithm except for Amplified SCAFFOLD for CIFAR-10, and every algorithm except for Amplified SCAFFOLD and SCAFFOLD for FashionMNIST. Ultimately these algorithms fell short of Amplified SCAFFOLD, which is consistent with the fact that these baselines were designed for i.i.d. client participation, whereas Amplified SCAFFOLD has convergence guarantees under periodic participation.

In response to your question about combining Amplified FedAvg with FedProx, we note that Amplified FedProx did not perform better than Amplified FedAvg. This means that combining amplified updates with control variates is much more effective than combining amplified updates with FedProx regularization.

Please see the general response for a detailed discussion of this additional experiment.

7. Experiments with different participation strategies. In response to your question about different participation strategies, we have included an additional experiment under a new non-i.i.d. participation pattern. We refer to this pattern as Stochastic Cyclic Availability (SCA), and we believe that it captures user device availability which is both periodic and unreliable. We thoroughly discussed the details of this participation pattern and the results of the experiment in the general response, and we highlight the results below. Figure 3 of the 1-page PDF shows the loss curves for all algorithms (including the four additional baselines) for CIFAR-10 under SCA participation.

From Figure 3, we conclude that Amplified SCAFFOLD outperforms all baselines under a second non-i.i.d. participation pattern. Amplified SCAFFOLD reaches the lowest training loss and highest training accuracy out of all algorithms, and even reaches a slightly lower training loss under SCA participation than cyclic participation (shown in Figure 2). We believe that this experiment bolsters the empirical validation of our proposed algorithm, demonstrating that Amplified SCAFFOLD performs well under multiple non-i.i.d. participation patterns.

Please see the general response for the full details of this experiment.

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

Amplified FedProx: Our implementation of Amplified FedProx is obtained by starting from the implementation of Amplified FedAvg (Wang & Ji, 2022), 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.

Thank you for your helpful comments on our paper. Below we have responded to your questions and concerns.

Weaknesses:

1. Missing related work. Thank you for pointing out these works. We agree that including these works in the discussion of our paper will establish a broader context of the FL literature, especially around problems of client sampling. Below we've included a brief comparison of each work you listed against our submission:

   (a) Mischenko et al, 2022 (ProxSkip/ScaffNew): ScaffNew achieves reduced communication rounds for FL with full participation on strongly convex problems.

   (b) Condat el al, 2023 (Tamuna): Tamuna uses communication compression and local steps together to reduce communication in FL with i.i.d. participation on strongly convex problems.

   (c) Tyurin et al, 2023: Improves convergence rate of nonconvex SGD for finite sum problems in terms of the smoothness constants, based on various unbiased data sampling protocols. Includes an application to FL with various client sampling protocols, which is related to our motivating problem of non-i.i.d. client sampling. These client sampling protocols are required to be unbiased.

   (d) Grudzien et al, 2023: Combines local training, client sampling, and communication compression to accelerate convergence in terms of condition number and dimension (strongly convex problems). Similarly to [Tyurin et al, 2023], the client sampling schemes from this paper are required to be unbiased.

   (e) Patel et al, 2022: This paper provides lower bounds for distributed non-convex, stochastic, smooth optimization with intermittent communication, both in the full and partial participation settings. They also include algorithms employing variance reduction which match (or closely match) lower bounds in the full and partial participation settings. These lower bounds are generally important to understand the limits of optimization under i.i.d. client sampling.

   In summary, these works are all relevant for FL in general. With respect to client sampling, (a) applies to full participation, (b) and (e) apply for i.i.d. client sampling, and (c) and (d) apply to unbiased sampling. The analysis of these papers cannot be directly applied to our setting of periodic participation, and our work aims to fill this gap by providing an algorithm with non-convex convergence guarantees even with non-i.i.d. client participation. We will cite and discuss these works in our updated paper.

2. Different heterogeneity assumptions. We addressed this point in the general response, but we can further touch on it here. The main point is that we do not use any heterogeneity assumption in our paper. The only reason that the condition $\lVert \nabla f_i(x) - \nabla f(x) \rVert \leq \kappa$ is stated in our table is that this assumption is used by the baselines we compare in Table 1. Our analysis avoids any heterogeneity assumption because our use of control variates eliminates the need for one (this is also the case in the SCAFFOLD analysis). We agree that bounded gradient dissimilarity is less restrictive than uniformly bounded heterogeneity, but even less restrictive is no heterogeneity assumption at all!

3. Complexity of assumption 2. We agree that Assumption 2 is somewhat dense, although we have already included in Section 3.2 a detailed discussion of different sampling schemes which satisfy assumption 2. If you have additional suggestions to improve the clarity of this assumption, please let us know.

4. Explanation of hyperparameters. As stated on Line 269, all of the hyperparameters for every baseline are tuned with grid search. The search ranges and final values for each hyperparameter are given in Table 2 of Appendix D. To evaluate each hyperparameter combination in the grid, we run the training setup described in the main body (with only one random seed instead of five) and choose the hyperparameter combination that reaches the smallest training loss by the end of training. After each hyperparameter is tuned, we evaluated each algorithm over five random seeds.

5. Recovering SCAFFOLD's rate. You are correct that our convergence rate as a slightly worse dependence on $N/S$ than SCAFFOLD. We pointed this out in Section 4.3 (line 223), and we provide a detailed explanation of this discrepancy in Appendix E. Essentially, there is a potential small issue in the analysis of SCAFFOLD for the case of partial participation. Instead of repeating this issue in our analysis, we accept a slightly worse dependence on $N/S$. It is likely that the issue can be fixed to recover the $(N/S)^{2/3}$ rate for both their algorithm and ours, but this is not the focus of our paper. In this paper, we focused on achieving convergence under periodic participation with reduced communication, linear speedup, and resilience to heterogeneity, and by doing so we have improved over previous work. If the $N/S$ dependence is an important issue to you, please read our discussion of the details, which is 1 page in Appendix E (lines 807-829).

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.