Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper analyzes local SGD with progressively decreasing communication frequency under the homogeneous data assumption. Unfortunately, the obtained convergence rates are worse than the best-known convergence rates for FedAC (Yuan and Ma) under the same set of assumptions. The paper also analyses One-shot averaging under a slightly different set of assumptions, showing it retains its linear convergence in settings less restrictive than pre-existing literature. Since the major result of this paper is worse than FedAC's guarantee, it is very incremental.  

**References**

Yuan, Honglin, and Tengyu Ma. "Federated Accelerated Stochastic Gradient Descent." Advances in Neural Information Processing Systems 33 (2020).
main_review: It seems the authors are unaware of FedAC, which requires $N^{1/3}$ synchronization for a linear speedup, and is a first-order algorithm analyzed under strong convexity, smoothness and uniform bounded variance. This is my major concern with the paper, since proving a lower communication complexity for Local SGD was its main (claimed) contribution. 

One-shot averaging is known to be minimax optimal for quadratic functions (after adding acceleration) (Woodworth et. al.). Previous works require higher-order assumptions (satisfied by quadratics) to show such speed-up for one-shot SGD. Thus, I understand the appeal to somehow push the result for OSA to a larger class of functions. But again, in absence of comparison to results from FedAC for both their A1 and A2 assumptions, I am hesitant to make a judgment on these results. 

Finally, I don't think the real-data experiments demonstrate any statistically significant advantage. Moreover, without comparison to FedAC, I am not ready to buy any experimental claims here. 

# After a discussion about FedAC

After the authors acknowledged that they missed a fair comparison to FedAC, and have listed some of its theoretical limitations, I am increasing my score to 5. If my concerns regarding empirical comparison to FedAC are resolved then I will further increase my score. 

# Final Verdict

After the authors made the required empirical comparison with FedAC, I am more satisfied with the paper. I would urge the authors to include more experiments in the final version of the paper with a larger tuning grid, larger condition number, with clear comparison against FedAC and the other baselines. In light of all the back and forth discussion, as well as the proposed changes I am increasing my score to a 6 and am fine with the paper being accepted.

**References**

Woodworth, Blake, et al. "Is local SGD better than minibatch SGD?." International Conference on Machine Learning. PMLR, 2020.
limitations_and_societal_impact: The authors have not compared to the most important baseline FedAC, which is detrimental for this paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: ## Update after rebuttall

I am satisfied with the authors' response and elevate my score to 6.

##

This paper presents several new theoretical results on the convergence of Local SGD as well as numerical experiments to check the tightness of the theory. In particular, the authors try and remove logarithmic terms from the bounds of Local SGD by making the communication less frequent as the iteration counter increases. The main results of the paper are:

1. Theorem 1 gives convergence for strongly convex functions under uniform-with-strong-growth noise. I argue in my detailed review that this result looks suboptimal.

2. Theorem 2 gives a result for PL functions with sub-Gaussian noise for one-shot averaging. This result is interesting as it promises a linear speed-up, although under somewhat restrictive assumptions. 

3. The experiments show that linear speed-up is lost when the number of communication rounds is chosen smaller than predicted by the theory of Theorem 1.

I tend to vote for rejection of this work, even though I appreciate some of the results obtained here. My main concerns are 1) applicability of the message to neural network training, which is highly relevant to FL; 2) the theoretical improvements appear to be small; 3) some small flaws in the proofs.
main_review: ## Weaknesses
1. From the numerical studies on Local SGD in training neural networks one can see that the proposed ideas are unrealistic. For instance, by reading the paper (Lin et al. "Don't Use Large Mini-Batches, Use Local SGD") one can mention that a relatively small number of local steps, such as 16, is used in practice. Increasing this number linearly as in Theorem 1 seems exotic, and without a numerical study by the authors I cannot conclude positively on the promise of such ideas.

2. Theorem 1 does not look very good to me. Since beta is lower bounded by kappa^2, it also holds that the stepsize is smaller than 1/(kappa * L), which does not seem to be a good assumption. Moreover, the upper bound in Theorem 1 includes the term kappa^2/(R*T), which seems to be kappa times worse than the similar term kappa*H/T^2 in Corollary 1 of Khaled et al. I am also puzzled as to why the authors used beta=1 in their experiments as explained in Appendix A, which is clearly against their theoretical results.

3. The proofs are a bit unexplained, some definitions seem missing. For instance, I guess from some equations that g_i^t (without any hats or bars) is the expectation of \hat g_i^t, but I didn't find the definition in the text. As far as I can see, the epsilon in the proof of Lemma 4 was not introduced either.

I did not understand the first step in equation (16). Why does it hold that sum_i ||g_i^t - overline g^t||^2 <= sum_i ||g_i^t - nabla f(\overline x^t)||^2 ?

## Proposed improvements
1. In the strongly convex case, the analysis could be done with the variance of gradients measured at the optimum instead of the global bound.
2. (Completely optional) I have a wild guess that additional results can be obtained under the setting of statistical similarity (Hendrikx et al., 2020), because for homogeneous data (sigma=0) the bounds significantly improve. Since the authors already perform analysis based on the Hessian at the optimum. I only suggest this in case the authors decide to resubmit their paper to a different venue or to write a new paper,  I do not ask the authors to do this during the rebuttal period.

Hendrikx et al., 2020, "Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization"

## Missing references
"Parallel Gradient Distribution in Unconstrained Optimization" by O. Mangasarian (1995) is probably the first work to introduce the idea if Local SGD and do (asymptotic) analysis. I believe this paper should be cited

## Typos and minor comments
1. Abstract: I suggest writing Omega(poly(log T)) instead of Omega(polynomial in log T)  
2. Abstract line 11: "state-of-the-art" is adjective and "state of the art" is a noun, so please fix it
3. Page 2, line 64: "strongly-convex" -> "strongly convex"
4. Page 3, line 89: "at the optimizer" -> "at the optimum"
5. "Charles, Papailiopoulos (2018) shows" (and many other examples): it feels rather strange that you refer to papers with multiple authors as to a singular noun.
6. "Lohasiewicz" -> "{\L}ojasiewicz"
7. Page 4, line 208: "for t\in I and i." What does this mean?
8. Page 8, line 293: "to obtain a linear up" -> "to obtain a linear speed-up"
9. Page 15, line 552: "the the"
10. Page 17, equation (13) and the lines after: "f(x^t) - F*" -> "f(x^t) - f*", "smoothness of F" -> "smoothness of f"
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this paper, the authors study the theoretical speedup of local SGD and one-shot averaging. A synchronization scheme that communicates more frequently at the beginning is also suggested. Some simple numerical experiments are provided to verify the theoretical results.
main_review: The paper is well-written. I recommend highlighting the communication scheme in Theorem 1 by putting it into a standalone definition, which will make it more friendly to the readers. 
This paper focuses on the theoretical analysis of the speedup of local SGD and one-shot averaging, and provides some improved results compared to the previous work. 
Some typos: line 140: sever -> server

limitations_and_societal_impact: 1. This paper uses the homogeneous data assumption. However, most of the recent deep-learning applications require non-iid settings, especially for large-scale problems where communication reduction via local SGD is more useful. Since the results of this paper only applies to the iid cases, such results are less useful in practical work.
2. Some strong assumptions such as strong convexity or PL condition are used. It will be more interesting to have the theoretical results under the assumption of smoothness without strong convexity or PL.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper investigates the gap between local SGD and One-Shot averaging in communication efficacy and linear speed-up with respect to the number of workers. Through extensive analysis, they show that they can tighten the bound for the number of communication required for local SGD to $\Omega\left(N\right)$, which is the number of workers. They have proved this bound for strongly convex and objectives with PL condition, where the strong convexity can be a special case of it. They use the idea of adaptive local step to have a more frequent communication at the beginning of the training and less frequent one at the end. In their experimental section, they show that their proposal can converge to the same rate as other local SGD approaches and Sync SGD using  $\Omega\left(N\right)$ communication rounds.
main_review: This paper bridges the gap from the local SGD and one-shot averaging to tighten the communication bound required for linear speed-up in local SGD. They are using heuristic ideas from Haddadpour et al. (2019) to use an adaptive and increasing number of iterations for each round of communication. Their theoretical analysis proves the effectiveness of this approach for strongly convex and PL-condition objectives. From the theoretical perspective, the contribution of this paper is important for tightening the bounds on the number of communication rounds required for linear speed-up, and hence it is a significant improvement over the previous works in this domain. The claims of the paper are clear and the comparison with other SOTA methods in this domain is fair. The empirical results are consistent with the theoretical results claimed in the paper and show the effectiveness of the proposed approach. I have some questions regarding the claims in the paper:

1. Although the theoretical results are focused on strongly convex and PL-condition objectives. However, I would like to know how this approach would work in non-convex objectives using local SGD.
 2. The theoretical results are mainly based on the adaptive local step sizes, however, in practice the difference between adaptive and non-adaptive cases are marginal. Could you please explain the difference and the significance of the adaptive local step?
3. How does the value of $a$ is decided? Are there any theoretical bounds on the size of local steps for this algorithm?

limitations_and_societal_impact: I do not think that this will be applied to this paper.
review_title: null

Meta-review: This paper studies the oracle (gradient) complexity of the local SGD algorithm (and one-shot averaging as a special case). The paper makes two main contributions (see additional comments below), (1) a slightly improved complexity estimate for local SGD with non-equally spaced (linearly increasing) intermissions between communication rounds, and (2) a novel asymptotic result for one-shot averaging under PL and second order smoothness assumption.

The paper has prompted lengthy discussions, both publicly and internally among the reviewers. 

The main focus of the paper is currently on result (1). However, all reviewers unanimously find this result not very significant, since, for example a discussion of a corresponding lower complexity bound is missing and thus a log factor improvement seems very marginal. For the final version, we urge the authors 
- to carefully discuss the improvement over Theorem 2 (strongly convex case) in [[Woodworth et al, ICML 2020](https://arxiv.org/pdf/2002.07839.pdf)] (essentially, it seems the new result improves under the condition $\kappa \leq \log (T)$ only.
- the reviewers mentioned the suboptimal dependence on e.g. the condition number and found the author's response (speculating on an inherent trade-off) very interesting. However, I would strongly encourage authors to be very precise when including such claims, as the trade-off may just be a consequence of the proof technique.

The reviewers found result (2) interesting. Although strong assumptions are being made at the moment, the result could possibly stipulate further research.

To conclude, the contribution regarding (2), as well as the proposed modifications in the discussion with the reviewers (including discussion on FedAC and additional numerical results), gave the impetus to argue for acceptance for this work.
Decision: Accept (Poster)