Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Authors provide a technique to compensate for error introduced by stale or infrequent synchronization updates in distributed deep learning.

Their solution is to use local gradient information to update the model, and once delayed gradient information from other workers arrives, the use it to provide a correction which would give an equivalent result to "no delay" synchronization in the case of linear model training.

The three approaches are:
1. Delayed update -- use local gradients for immediate update, apply correction when stale averaged update arrives. 
2. Sparse update -- only update once every p iterations, the averaged update includes p steps
3. Combined -- 1. and 2. combined

Authors evaluate on ImageNet, showing some improvement, and promise to release their implementation for PyTorch/Horovod. Their technique, combined with a reference implementation in a popular framework stands a good chance of having impact. Given the increase in cloud training workloads, even a small improvement in this setting is significant.

Comments:
- "scalability" is never defined. I would recommend defining it, or referencing a paper which defines it. I assume it refers to training throughput divided by ideal training throughput.
- Evaluation is one on resnet-50. Because it's mostly convolutions, such network has high compute/network ratio and is not frequently bottlenecked by network. A more convincing experiment would rely on lower computation intensity architecture such as Transformer/BERT training.
- Section 1 states that without their technique, they expect SGD to exhibit 0.008 scalability for 100 servers, compared to 0.72 for their method. However, the number 0.72 was not supported by data, their largest experiment used 16 servers.


review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper tackles the issue of scalability in distributed SGD over a high-latency network.
Along with experiments, this paper contributes two ideas: delayed updates and temporally sparse updates.

- strengths: 

· Clear-looking overall presentation.
  Good efforts to explain the network problems (latency, congestion) and how they are tackled by delayed updates and temporally sparse updates.

- weaknesses:

· While the overall presentation looks clean, the paper does not talk about the setting (one parameter server and many workers, only workers, etc).
  This is arguably basic information, and the readers is left to understand by themselves that the setting consists in many workers without a parameter server.

· There is no theoretical analysis of the soundness of the proposed algorithm.
  For instance in ASGD (that the authors cite), stale gradients are dampened before being used, which in turn is used to guarantee convergence.
  In the proposed algorithm, there is no dampening nor apparent limit of the maximum value of t; such a difference with prior art should entail a serious (theoretical) analysis.

· Finally, using SSGD for comparison is not very "fair", as communication-efficient algorithms have already been published for quite some time [1, 2, and follow-ups (e.g. searching for "local sgd")].
  At the very least a comparison with ASGD (cited) is necessary, as in a realistic setting latency is indeed a problem but arguably not bandwidth
  (plus, orthogonal gradient compression techniques do exist, e.g. as in "Federated Learning: Strategies for Improving Communication Efficiency").

questions to the authors: 

- Can you clarify the setting?

- Can you give at least an intuition why accepting stale gradient is correct (i.e. does not impede convergence)?
  There is no theoretical limit on the value of t; can workers take any arbitrary old gradient?
  So when the training is close to convergence (if it reaches it), i.e., when the norm of the gradients are close to 0,  the algorithm could then use very old gradients (which norms could be orders of magnitude larger) to "correct the mismatch" caused by the local training; is this correct?
  To solve that issue, ASGD introduces a simple dampening mechanism (which is necessary in the convergence proof), which your algorithm does not have.


The related work section focuses on gradient compression techniques (which tackle low bandwidth, not latency) and asynchronous SGD (which is more prone to congestion, with a single parameter server),
but seems to overlook that sparse communication techniques already exist (this fact should at least be mentioned).

The idea of sparse communication for SGD exists since at least 2012 [1, Algorithm 3].
A first mention of the use of such techniques for "communication efficiency" dates from (at least) 2015 [2].

[1] Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao.
    Optimal distributed online prediction using mini-batches.
    J. Mach. Learn. Res., 13(1):165–202, January 2012.

[2] Sixin Zhang, Anna E. Choromanska, Yann LeCun.
    Deep learning with Elastic Averaging SGD.
    NeurIPS, 2015.


I do not see a clear novelty, nor a proof (or even intuitions) that the proposed algorithm is theoretically sound.
The comparison with SSGD is arguably unfair, since SSGD is arguably not at all the state-of-the-art in the proposed setting (hence the claimed speedup of x90 can be very misleading).
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: The paper presents an approach - Delayed and Temporally Sparse Update (DTS) - to do distributed training on nodes that are very distant from each other in terms of latency. The approach relies on delayed updates to tolerate latencies and temporally sparse updates to reduce traffic. The approach is implemented in a synchronous stochastic gradient decent (SGD) scheme. 

The paper's approach with delayed updates, i.e., delaying gradient updates to other nodes, sends the updates in a later iteration. In this way, very long latencies can be hidden (covered by computation) since the gradient updates can be postponed to an arbitrary iteration (barrier synchronization) in the future. 

Unfortunately, delaying the updates opens up for the same problems as asynchronous SGD (ASGD), i.e., slower (none) convergence or staleness problems. These problems are coped with using a compensation factor, that adjusts the momentum and weights accordingly. 

A critical aspect of ASGD is to provide convergence guarantees, and DTS is similar in that aspect. However, the paper does not provide any convergence analysis or convergence guarantees. 

Using only one dataset / network to evaluate the approach is too little. In order to show the generality, more benchmarks need to be evaluated.

In general, I like the paper. It is well written and easy to read. However, the novelty and contribution is relatively low. A lot of work has been done in the HPC and distributed systems communities over decades on how to tolerate latencies, trade-offs between communication and computation, proper synchronization points, etc. The ideas presented in this paper are well-known and extensively applied in those communities. None of that work is referensed or acknowledged in this paper. 

The term "scalability" is used as an evaluation metric, but never clearly defined in the paper.

review_title: Official Blind Review #3

Meta-review: The paper introduces a distributed algorithm for training deep nets in clusters with high-latency (i.e. very remote) nodes. While the motivation and clarity are the strengths of the paper, the reviewers have some concerns regarding novelty and insufficient theoretical analysis. 
Decision: Reject