Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: ### Summary
The paper proposes and analyses a distributed learning algorithm for training with Stochastic Gradient Descent a global model on a regular graph, that allows for local and asynchronous gradient updates. Nodes continuously update their local models $X^i$ by gradient descent, while they communicate with their peers (a peer at a time) and update their local model with the pair model average $\frac{X^i + X^j}{2}$. Three extensions of the algorithm are also proposed to relax different constraints, while maintaining the convergence guarantees:
1. synchronous updates and decentralized data: if the number of local gradient updates $H_i$ before an edge update is constant, convergence guarantees hold for decentralized data, as long as partitions are i.i.d. from the original distribution;
1. asynchronous updates: the number of local gradient updates $H_i$ can vary between nodes and between every edge update;
3. reduced communication: model exchanges can be quantized to reduce communication complexity.
Experiments in the distributed setting are carried out for image classification and speech recognition, showing that the algorithm is generally able to achieve performance comparable to a model trained in the centralized setting at increased execution time, but faster than state-of-the-art distributed SGD methods.

### Significance and clarity
Contributions are significant and novel, to the best of my knowledge. They consider several settings, which are all theoretically founded. However, the paper is generally hard to follow, also because it has many contributions that are cited in the main text but deferred to the appendix. Still, it would help to clarify the following points from the beginning:
1. what the authors mean by decentralized, later explained as decentralized model updates, but centralized/distributed data for the experiments;
2. define $T$ (global number of edge updates) and $H$ (number of local updates in between edge communication);
3. where and when quantization is applied and why it helps in reducing communication complexity in the main text.

### Remarks on theoretical analysis
Theorem 4.1 shows that the average second moment of the loss gradient evaluated at the average model $\mu_t$ is bounded and decreases with $T$, proving that the model updates converge to a local minimum. This bound however stands for the average of all models obtained at each global step $t$, meaning that it is not necessarily a tight bound for the second moment of the last obtained model, which is the bound we are ultimately interested in.
It would be also interesting to report communication complexities, with and without quantization, and compare them to state-of-the-art methods.

### UPDATE
I thank the authors for addressing my concerns and confirm my initial rating.
review_title: simple and effective distributed SGD, with asynchronous, decentralized and reduced communication extensions

final_score: rating: 5: Marginally below acceptance threshold
review_content: # Contributions:
1. This paper analyzes the convergence of decentralized SGD with asynchronous updates, quantization and local updates, which is novel and challenging.

2. The proposed algorithm requires significantly less communications to converge.

3. The authors have done extensive analysis of the convergence under different settings with detailed proofs.

4. The authors have done some large-scale experiments and show their algorithm performs great in practice.


# Strong points:

1. The authors have done concrete non-trivial analysis.

2. The algorithm is very general, several existing algorithms can be its special cases by different choice of parameters.

3. The experiment section provides a large amount of empirical evidence.


# Weak points:

1. Assumptions are too strong for Theorem 4.1 and 4.2: 

	- Assuming each node can sample from global data is too strong. Section I removes this assumption but without highlighting key steps.

	- Step size requires the knowledge of the number of total steps.

	- Number of total steps needs to be larger than $n^4$. Even nodes don't communicate, the algorithm should still converge because the global sampling.

2. The benefit of local steps is not clear. For example, if we optimize the convergence rate in Theorem 4.1 over $H$, the best choice is $H = \Big(\frac{\lambda_2^2}{r^2} \cdot \frac{f(\mu_0) - f^*}{L^2 M^2} \Big)^{1/3}$. That is, the optimal $H$ is smaller when $r$ is larger.

3. The $H^2$ term in Theorem 4.1 and 4.2 may not be good enough. If set $H \to \infty$, then this bound should reduce to the single-machine SGD. However, the $H^2$ term will go to $\infty$.
4. Theorem 4.2 requires $T \sim O(*)$. Does it work if $T$ is greater?


5. Definition of $T$ is confusing.

6. Arguments for acceleration is not convincing. The algorithm only have one pair of nodes communicate, it's not clear how to replace $T$ with $nT$.


# Recommendation: 

Weak reject. As of the current version, the proofs need to be improved. However, I believe the authors can improve in the next version.



# Further questions:

1. Is it possible to merge Section I with Theorem 4.1 or show the proof? I think there will be one term that depends on $\rho^2$. When $\rho^2 = 0$, Section I will reduce to Theorem 4.1.

2. Lemma F.3 is confusing. I think $\Gamma_t$ should decrease with $t$, or use diminishing step size $\eta_t$ to control this term. Then there's no need to set $\eta \sim \frac{1}{\sqrt{T}}$.

3. Can you also show the run time plot for ResNet?


# Optional improvements:

 1. It may be better to remove some small terms to make rate more clearer. For example,
	 - For Theorem 4.1, use $1 \leq \frac{r^2}{\lambda_2^2}$ can get rid of the constant $1$.
	 - For (14) and (19), use $\frac{r}{\lambda_2} \leq \frac{r^2}{\lambda_2^2}$ to get rid of the first order term.

2. The 3rd equation in Section D, $\tilde h_i^s$ also depends on $\tilde g_i$, which is not reflected.

3. The 1st equation in Section E has an extra '-'.

4. Is the coefficient $\frac{n - 2}{n}# in Eq (18) missing?

# Update

Thanks for the authors to address my questions. However, if the analysis can not explain why more local updates can reduce communications, I would not recommend to accept.
review_title: Proof issues.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper considers several techniques to minimize decentralized cost for training neural network models via stochastic gradient descent (SGD). These techniques include asynchronization, local updates, and quantized communication. Theoretical convergence analyses are provided, and numerical experiments are shown. 

Strength:

- The provided convergence rate is well-separated and well-explained, though the reviewer did not check the correctness of all the proofs. 
- Combining these techniques into decentralized SGD is new to the best of the reviewer's knowledge. 

Weakness:

- The number of graphs satisfying the property is very limited. It requires an r-regular graph. That is, the number of edges connected to one node is the same for all nodes. This condition is very difficult to satisfy in applications. Therefore, the application would be limited too. 
- The quantization part is limited comparing to the other two parts. What does the effect of quantization on the convergence rate and the communication cost? What is the benefit of using the quantization method in Davies et al. (2020)?
- In the proposed algorithm, each time an edge is activated and the two nodes connected through the edge are updated. Therefore, there is still synchronization in Alg. 1. Whether is it possible to update one node based on the results from multiple connected nodes (i.e., one node is activated)? 
- Algorithm 2 is unclear. 'avg' is computed but not used. What are j' and 'i''? 


## Update

The authors' response addresses some concerns, and I would like to keep the initial scores. 
review_title: several unclear places; strong assumption on the graph

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary: This paper combines the existing scaling techniques to reduce the communication cost of distributed SGD among a large number of computing nodes. These techniques include asynchronous, decentralized, or quantized communication. The authors prove that this combined algorithm converges to a local optimal point. In the experiments, this algorithm also successfully converges and scales for big data. The authors claim that this is the first work to consider decentralization, local updates, asynchrony, and quantization in conjunction. 

Overall, the contribution of this paper is relatively marginal. The algorithm simply combines many different existing techniques and does not lead to any substantial new development. Below are some comments and questions. 

(1) The first two paragraphs of the introduction look wordy. They introduced the distributed SGD problem and listed the scaling techniques as well as the relevant literature, but the meaning of these techniques is unclear. How these techniques are applied and combined is also unclear. 

(2) The meaning of n and T are not formally defined. 

(3) In Theorem 4.1, the assumption that T>=n^4 (n^4 can be very large) is the disadvantage of this algorithm because the same convergence rate O(1/sqrt(T)) has been achieved without such assumption in some distributed settings, including plain distributed SGD, federated average, etc.

(4) The claim in the abstract that the new algorithm can converge to local minima is not supported, since the theorems only imply gradient convergence. 

(5) In the theoretical part, I did not see in which measure does this new algorithm excel the existing ones. The authors should clarify this. In the experiments, the objective function value of interest is not compared. 

(6) On page 2, the authors said “SwarmSGD has a Θ(n) speedup in the non-convex case, matching results from previous work which considered decentralized dynamics but which synchronize upon every SGD step.” What is the measure, is it the number of communications, local SGD iterations or gradient evaluations? “Matching results” can be interpreted as equal to the previous rate, which seems to contradict with Θ(n) speedup. Please clarify this. 

(7) In the contribution part, the authors mention that their new algorithm has lower average synchronization cost per iteration but more iterations in the experiments, how about the total synchronization cost?  

(8) The authors use multiple variables to denote the number of nodes, including n, P and m. Please use only one. 

(9) The space around the section captions is too narrow. This is not suggested in general. 
review_title: Official Review 2

Meta-review: The reviews were a bit mixed: on one hand, by combining and adapting existing techniques the authors obtained some interesting new results that seem to complement existing ones; on the other hand, there is some concern on the novelty and on the interpretation of the obtained results. Upon independent reading, the AC agrees with the reviewers that this paper's presentation can use some polishing. (The revision that the authors prepared has addressed some concerns and improved a lot compared to the original submission.) Overall, the analysis is interesting but the significance and novelty of this work require further elaboration. In the end, the PCs and AC agreed that this work is not ready for publication at ICLR yet. Please do not take this decision as an under-appreciation of your work. Rather, please use this opportunity to consider further polishing your draft according to the reviews. It is our belief that with proper revision this work can certainly be a useful addition to the field. 

Some of the critical reviews are recalled below to assist the authors' revision:

(a) The result in Theorem 4.1 needs to be contrasted with a single machine setting: do we improve the convergence rate in terms of T here? do we improve the constants in terms of L and M here? What is the advantage one can read off from Theorem 4.1, compared to a single machine implementation? How should we interpret the dependence of (optimal) H on r and lambda_2? 

(b) The justification for $T \geq n^4$ is a bit  weak and requires more thoughts: one applies distributed SGD because n is large. What happens if T does not satisfy this condition in practice, as in the experiments?

(c) Extension 1 perhaps should be more detailed as its setting is much more realistic than Theorem 1. One could use Theorem 1 to motivate and explain some high level ideas but the focus should be on Extension 1-3. In extension 2, the final bound seems to be exactly the same as in Theorem 1, except a new condition on T. Any explanations? Why asynchronous updates only require a larger number of interactions but retain the same bound? These explanations would make the obtained theoretical results more accessible and easier to interpret.
Decision: Reject