Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes "multi-stage FL algorithms" to bridge the gap between local step methods (that are theoretically known to be optimal for a no-heterogeneity regime where $\zeta=0$) and SGD type methods that are known to be good for high heterogeneity regimes. The goal of the paper is to find methods that are optimal across all values of $\zeta$, esp $0<\zeta^2< \beta^{3/2}\Delta/{\mu^{1/2}}$.
main_review: - The paper is not well-written. I had difficulty following some key parts of the paper. see the comments below.
- The writing of the paper is misleading about the methods. It took me a while to figure out that all the methods and analyses that are covered in the paper require full participation from the clients. First of all, this limits the applicability of the results in any realistic FL scenarios as all FL algorithms across many devices can only work with limited participation. It is important to note that the dominating terms in convergence guarantees would actually change when one looks at the limited participation regime for each of these methods and it is not clear how much of the results translate to that regime. Moreover, this means that the methods that are called SGD, FedAvg, and .... are not what they are called. For example, FedAvg sub-samples the clients in each step and does not use full participation. 
- The assumptions and many other necessary details about algorithms and theorems are unnecessarily relegated to the appendix. This made it very hard to understand the paper and results. 
- I never understood what is difference between $\zeta$ and $\zeta_*$. Only one is defined in the assumptions.
- The StageWeightedAverage step of algorithm 1 has a lot of implications for the communication and memory of the method (as it requires access to the intermediate local updates of the clients). I believe this makes the algorithm impractical.
- In most of the rates, e.g. eq (9), the non-exponential terms are actually more important/dominant practically than the exponential part. But the authors are mainly focused on the exponential part (which is not dominating in practice). The only reasonable justification for that is assuming $K=\infty$ or very large, which is not necessarily the case and limits the significance of the results in practice. At the minimum, such a scenario should be elaborated in the paper and authors should refrain from over-claiming the significance of their results.
- Theorem 3 was very difficult to understand due to the complications in the definition of M-FedAvg and M-ASG.
- In Theorem 3 it seems that the regime in which the authors have proven the optimality of their methods ($\zeta^2<\kappa \mu \Delta$) is only a very small fraction of the original target regime ($\zeta^2<\sqrt{\kappa}\beta\Delta$) and gets even smaller with higher $\kappa$.
- The experimental section is very limited. 
  - It is not very clear to me how the HP tuning is done for each algorithm. what HPs are tuned, and based on what metric and which values. This is of utmost importance because there are many algorithms with many different HPs. And in fact, one selling point of some multi-stage algorithms is their capability to be independent of many constants. But it is not clear to me how it plays in practice and is different from the other algorithms.
  - There is only one result on the test accuracy and it is very low (far from the state of the art) which makes the results not very convincing. The other result on accuracies in L.2 is not even clear which experimental setup it is referring to.

It is worth noting that I did not check the proofs thoroughly and in detail, but the claims of the paper seem to be reasonable and correct.

Minor comments:
- the authors mention that FedAvg's lower bound can only result in lower communication complexity than AC-SA when $\zeta_*^2\leq \mu \epsilon$. Is it possible to elaborate on how this result is driven?
- why is there a need to consider a batch size of B for Theorem 3; it seems to only affect the variance.

===================== After reading other reviews and the authors' responses ========================
- I agree with other reviewers that the novelty of the work is limited, especially given the fact that it applies to limited scenarios and does not even consider the general convex setting (which in my opinion would be more informative as the local updates can converge to different solutions of the same problem). Also, the obtained results are not as strong as advertised (for example as I mentioned Theorem 3 results are far from closing the gap). But at the same time, I commend the authors for improving the paper and including partial participation scenarios. Because of this, I will increase my score to 6.
- One point that was brought up by reviewer AN2w and I think does actually question the need and possible insight from the results is the fact that you do not need to run two stages with multiple steps, and the local update could all be done in 1 step and then run centralized method afterwards and get the same rate. This limits the importance of the achieved results (basically just changing the initialization for the centralized approach based on a local method could result in an optimal rate). I do not think that this is translatable to more complicated cases (other than strongly convex cases), but the authors have not empirically or theoretically studied the limitations of such an approach.
summary_of_the_review: Based on the above comments, I believe the paper lacks in the areas of contribution, applicability, significance, practicality, experiments, and writing. As a result, I believe the current version of the paper is slightly below the acceptance criteria. I would like the authors to address the comments above before I can increase the score of the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces the multistage optimization technique for federated learning applications. Specifically, multistage optimization first uses federated optimization algorithms like FedAvg and SCAFFOLD and converges to some budget, and then uses minibatch algorithms like SGD or accelerated SGD in order to converge faster to a point with very small error. Because centralized methods are optimal when data are heterogeneous and local methods are optimal when data are purely homogeneous, using a multistage optimization technique can incorporate the benefits from both sides.

The theoretical part is relatively easy. The proof is to choose an appropriate error budget to which federated optimization algorithms converge, and then choose the hyperparameters for the federated optimization algorithms in the first stage and the minibatch algorithms in the second stage, e.g. learning rate, momentum, etc. The theoretical part only includes the convergence results for the strongly convex case.

The empirical part includes two experiments: logistic regression and neural network, which belongs to strongly convex case and nonconvex case respectively. For each experiment, the authors compare different minibatch algorithms like SGD, AGD, different local methods like FedAvg, SCAFFOLD, and some multistage procedures that combine local methods with minibatch methods. For the convex setting, multistage procedures perform the best, and for the nonconvex setting, multistage algorithms also perform generally the best.


main_review: Please see the "Summary Of The Paper" for the brief summary.

From the theoretical point of view, in the strongly convex case, multistage algorithms indeed outperform the other methods like SCAFFOLD or minibatch algorithms.

From the empirical perspective, this paper considers the strongly convex case with logistic regression and the nonconvex case with neural networks. It also compares many algorithms, and I think the experiment part is generally enough.

However, I think this paper suffers from the following weaknesses:

1. In my point of view, neither the algorithm itself nor its analysis is interesting enough. The algorithm seems like a direct combination of different algorithms and the proof is also very straightforward: directly applying and combining the convergence analysis from the algorithm algorithms.

2. Missing important citation "Federated Accelerated Stochastic Gradient Descent" by Honglin Yuan, Tengyu Ma. This paper presents accelerated local methods. The results are not discussed in Table 1.

3. Although in the contribution part, the author claims: "This multistage has the added benefit of not requiring the knowledge of the noise bound $\sigma^2$, the heterogeneity $\xi^2$, or the initial distance to the optimum $\Delta$." However, in my understanding, the algorithm also needs to know the heterogeneity parameter $\xi^2$ in advance in order to choose the appropriate local steps $K$ in the first stage. Otherwise, I can choose all the functions $f_i$ to be the same thus $\xi^2 = 0$, and choosing $\sigma^2 = 0$. Theorem 4 and 5 imply that if $\xi^2 = \sigma^2 = 0$, it requires 0 communication rounds to achieve 0 training loss. Without knowing the heterogeneity parameters in advance, it seems impossible to do that. Also, please do not use "large enough $K$" in the theorems (e.g. Theorem 4 and Theorem 5), directly write out the constraints on $K$.

4. For the experiment hyperparameter selection, I think that the comparison is not very fair. In Appendix K "Experiment Setup Details", for single-stage algorithms, the global learning rate $\eta_g$ and the local learning rate $\eta_l$ are the same and they do not change during the training procedure. However, for two-stage algorithms, the learning rate for the second stage is $K$ times smaller than the global learning rate in the first stage. Even for one-stage algorithms, using two different learning rates may also speed up the training (i.e. we may not need to choose the local learning rate in the second stage to be 0, shrinking global and local LR in the second stage may also work).

Based on the previous concerns, I have the following suggestions and questions:
1. In terms of the algorithm, I think that it is better to analyze a single algorithm with different learning rates in different stages, e.g. only running FedAvg or SCAFFOLD with different learning rates. As minibatch algorithms are special cases for local step algorithms by choosing $\eta_l = 0$ (local learning rate), I believe that, in fact, we do not need to choose $\eta_l = 0$ in the second stage, we just need $\eta_l$ to be smaller.

2. Please have a check on the paper "Federated Accelerated Stochastic Gradient Descent" by Honglin Yuan, Tengyu Ma, and compare the results with multi-stage procedures. Or see if the results from that paper can improve the results for multi-stage algorithms.

3. This paper only analyzes the strongly convex case. I think that adding the analysis (just using different $\eta_g$ and $\eta_l$ in different stages, but not choosing $\eta_l = 0$ in the second stage) for the nonconvex case will make the results more interesting.

4. Please write the theorem more formally. Especially, should specify how $K$ is chosen.

5. I suggest adding some experiment results when keeping the same $\eta_g$ in different stages, or when decaying $\eta_g$ for a single algorithm, e.g. for FedAvg, using $\eta_{1,g} = \eta_{1,l} = 0.01, \eta_{2,g} = \eta_{2,l} = 0.005$.

Please point out if I have conceptual errors or misunderstandings.
summary_of_the_review: In summary, I think this paper needs to be revised because of the following reasons:
1. The algorithm and the analysis seem a little incremental.
2. Missing important citation and comparison.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: It is known that if the level of heterogeneity is sufficiently high, then accelerated minibatch SGD is optimal for federated optimization matching the known lower bound of (Woodworth et al., 2020a). On the other hand, when the level of heterogeneity is very low, then FedAvg/LocalSGD outperforms the former in terms of communication complexity and needs only a few communication rounds given enough local computation. This paper *proposes* a multi-stage optimization procedure and *claims* that it nearly matches the lower bound for all heterogeneity levels.
main_review: - **Writing**

In general, the writing of the main paper is good and well organized, which is not the case for the appendix, where there are many typos and missing details in the proofs.

I would point the following statement in the main paper. At the end of page 4, it is mentioned that $\zeta_*^2$ is scaled by exponentially decaying term in the lower bound (6), while $\zeta^2$ is scaled by $\frac{1}{R^2}$ in the rate of FedAvg (6). Then, Theorem 1 claims to improve exponentially the dependence on heterogeneity from $\frac{\zeta^2}{R^2}$ to $\frac{\zeta^2}{R^2} \textrm{exp}(-\frac{R}{\kappa})$. What about the rate of SCAFFOLD, where instead of $\zeta^2$ it is (smaller term) $\zeta_*^2$ and dependence is $\frac{\zeta_*^2}{\beta^2} \textrm{exp}(-\frac{R}{\kappa})$ ?


- **Correctness and optimality of the rates.**

First, the sub-optimality rates of FedAvg$\to$SGD and FedAvg$\to$ASG given in Table 1 are slightly different from those shown in Theorems 4&5. For example, for FedAvg$\to$ASG, it $\min(\Delta, \frac{\beta\zeta^2}{\mu^2 R^2})$ in Table 1, and $ \frac{\beta\zeta^2}{\mu^2 R^2}$ in Theorem 5 (see (27)). More importantly, I failed to get the claimed sub-optimality rates from the proof.

Let me provide some details for the proof of FedAvg$\to$ASG. From the proof of Theorem 5, we get (28) (ignoring constants and poly-log factors) by running FedAvg.
$$
\mathbb{E}[F(x^{(1)})] - F(x^*) \le  \Delta_1 := \beta \\,\textrm{exp}(-\frac{KR}{\kappa})\||x^{(0)} - x^*\||^2 + \frac{\sigma^2}{\mu N K R} + \frac{\beta \sigma^2}{\mu^2 K R^2} + \frac{\beta \zeta^2}{\mu^2 R^2} \qquad (28)
$$


Then switching to ASG, we have (31)
$$
\mathbb{E}[F(x^{(2)})] - F(x^*) \le  2\Delta_1 \\,\textrm{exp}(-\frac{R}{\sqrt{\kappa}}) + \frac{\sigma^2}{\mu N K R} + \frac{\beta \sigma^2}{\mu^2 K R^3} \qquad (31)
$$

The proof is terminated by plugging $\Delta_1$ in (31). However, it is easy to see that then we have (among others) the term $\beta \textrm{exp}(-\frac{K R}{\kappa}) \textrm{exp}(-\frac{R}{\sqrt{\kappa}})$, which remains even in the case when $\zeta^2=\sigma^2=0$. On the other hand, the rates shown in Table 1 and in Theorem 5 vanish in this case. Furthermore, if we let $\zeta^2=\zeta_*^2=0$, then the lower bound becomes $\frac{\sigma^2}{\mu N K R}$, while the actual rate of FedAvg$\to$ASG includes other terms like $\frac{\beta \sigma^2}{\mu^2 K R^2}\textrm{exp}(-\frac{R}{\sqrt{\kappa}})$.

A similar argument can be made for FedAvg$\to$SGD in the proof of Theorem 4 when plugging (24) into (26).

Could you please provide complete proofs of the theorems, addressing the above points, either in the rebuttal or updating the paper (if possible)?


- **Technical novelty**

Most of the analyses heavily use the results of previous works. Besides, the analyses of the central claims of Theorems 4 (1 in the main paper) and 5 (2 in the main paper) are direct concatenations of the previous rates. I did not find anything new in the analyses.

- **Experiments**

Experiments do not seem to be aligned with the given theory.  In the convex experiment in Figure 2, the best performing method is SCAFFOLD$\to$SGD, which (i) has an inferior rate than, say SCAFFOLD$\to$ASG, and (ii) as far as I get, the presented theory for SCAFFOLD$\to$SGD is the same as FedAvg$\to$SGD, which is not the case for SCAFFOLD versus FedAvg. It is mentioned that the good performance of SCAFFOLD$\to$SGD can be attributed to small $K$ in the experiment. Do you have an experiment with large $K$ with the predicted behavior?

The non-convex experiment in Figure 3 is strange too. Multi-staging does improve over the two-stage method, and in the second plot, FedAvg almost reaches to FedAvg$\to$SGD.








summary_of_the_review: The paper provides a clear intuition on why multistage algorithms are useful in practice. However, I made several critical comments in my main review regarding the correctness of the results, the technical novelty of the proofs, and the connection between experiments and theory. As of now, the paper seems weak (at least the way it is presented now). However, I am looking forward to reading the authors' rebuttal.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposed a provable multi-stage algorithm to match the lower bound established by Woodworth for intermediate heterogeneity levels in federated optimization.

main_review: The paper tries to answer a theoretical problem in federated optimization.
The paper proposed a multi-stage algorithm to match the lower bound established by Woodworth for intermediate heterogeneity levels.
In particular, they first run a local method up to reach certain error floor and then switch to a centralized method for the rest steps.
The method is intuitive and supported with theoretical analysis assuming strongly-convex objective functions.
The result is new for FL.
The proof seems correct and the writing is clear and easy to follow.
They also demonstrate the effectiveness of their method in mage classification tasks.

I have the following concerns:
1. In the proof of Theorem 1, the $n$ in the expression of $\Phi$ and $\eta$ of the first stage should be $N$. 
2. I find that both Theorem 1 and Theorem 2 require sufficiently large $K$, which is important to make the $\widetilde{O}(\frac{\beta\zeta^2}{\mu^2R^2})$ dominate the error (e.g., see (25) and (29)). Besides, Section 3.1 provides a two-stage instantiation of proposed algorithm. It first lets each device run Local SGD and then run SGD to approach the local optimal point. The two results make me to wonder, why not we first run pure local training, letting each device obtain a local minimizer, and the run (accelerated) SGD. This is equivalent to let the first stage be a pure local training rather than local SGD. In this way, the communication cost is saved as much as possible, since it only requires one communication round. By contrast, current result (Theorem 1 and Theorem 2) requires $R/2$ rounds. 
3. The paper only analyzes the strongly-convex case and omit the generally-convex case. Woodworth et al. (2020a) provides analysis for Local SGD under both cases. Considering the analysis method used in the paper is just to combine convergence rates of outputs from two (super)stages, I think it is not hard to extend the result to the generally-convex case. However, it is quite interesting and unclear to see the theoretical performance of proposed multistage algorithms for non-convex functions. 
4. I don’t quite see why the work explains empirically-successful stepsize decay methods in FL, which is declaimed in the abstract. I feel it is exaggerated and should be supported with more evidence. In my opinion, what makes the proposed algorithm have a better dependence on $\zeta^2$ is not the stepsize decay but the switch to centralize methods. It supports my point that most of theorems is derived under constant small step sizes. The discussion in Appendix A is weak and farfetched. I think the author should support the claim with other suppport analysis, for example, analysis for simple cases or additional experiments to show the adaptive optimization methods indeed swtich to a centralized counterpart. 

============================================

I have read the authors’ responses as well as other reviewers’ feedback.
At the moment, I think the proposed two-stage method is more like a trick rather than a universal method that can be implemented to other scenarios. There are two reasons supporting my thought.
First, the author can’t extend the theory to general convex and nonconvex settings, which implies the method replies on the strong-convexity, which brings great convenience for analysis.
Second, the author didn’t justify the necessity of the first-stage. From the author’s feedback (the added footnote 3), using one-round even has better performance. In this case, the two-stage algorithm is reduced to the last stage which is the accelerated SGD. Hence, it is not surprising it has so good performance. At this moment, I feel the proposed method is more like a trick rather than a universal component.
Therefore, I think the paper could provide limited insights for future work.

I think the author could improve their work in the following directions: (i) provide analysis for general convex and nonconvex settings, (ii) find a more distinguishable method to close the gap. For example, a softer decay of local update length.
summary_of_the_review: The theoretical result is new in FL.
The proposed method has strong empirical performance in typical datasets.
Their match the lower bound and  fill the blank. 
Though it has some limitations, I think it is worth to be published.
review_title: null

Meta-review: The paper analyzes a 2-stage method for federated learning, first using FL with local steps, followed by a final phase of 'always-communicate' centralized SGD. For the convex case, the paper studies the influence of the data heterogeneity, a key parameter in FL, on the convergence of related schemes. Surprisingly the results of the 2-stage method seem to be basically identical to pure local training followed by the final centralized phase, and almost match the lower bound for communication.

Reviewers liked the interesting aspect of the heterogeneity-induced error floor when the phases are switched, and its impact on the convergence rates, which can be substantial. Downsides are that the analysis only works for strongly convex setting, and the combination of the two methods and proof being relatively straight-forward. Simplicity of the algorithm is a plus, while of the proof depends on novelty, about which reviewers are border-line but positive. 

Deep learning experiments should be expanded, as there the very opposite order of the two phases https://arxiv.org/abs/1808.07217 is more commonly used (i.e. more communication in early phase can help), which should be discussed. Also, in the experiments the tuning of hyperparameters in the single-stage baselines needs to be improved to be more fair, which the authors have started but not fully finished for the Cifar case.

We hope the authors will incorporate the open points as mentioned by the reviewers.
Decision: Accept (Poster)