Cloud computing is becoming increasingly popular as a platform for distributed training of deep neural networks. Synchronous stochastic gradient descent (SSGD) suffers from substantial slowdowns due to stragglers if the environment is nondedicated, as is common in cloud computing. Asynchronous SGD (ASGD) methods are immune to these slowdowns but are scarcely used due to gradient staleness, which encumbers the convergence process. Recent techniques have had limited success mitigating the gradient staleness when scaling up to many workers (computing nodes). In this paper we define the Gap as a measure of gradient staleness and propose Gap-Aware (GA), a novel asynchronous-distributed method that penalizes stale gradients linearly to the Gap and performs well even when scaling to large numbers of workers. Our evaluation on the CIFAR, ImageNet, and WikiText-103 datasets shows that GA outperforms the currently acceptable gradient penalization method, in final test accuracy. We also provide convergence rate proof for GA. Despite prior beliefs, we show that if GA is applied, momentum becomes beneficial in asynchronous environments, even when the number of workers scales up.
The paper introduces a new variant of asynchronous SGD, GA-ASGD, for distributed training. The goal is to mitigate the gradient staleness issue caused by asynchronously applying gradients to an old version of parameters. Prior work addresses this issue by penalizing the learning step of a worker linearly to its missed updates since getting a replica of parameters. However, that approach does not consider the differences between the old and new versions of parameters, which can cause over-penalization and under-penalization. The main contribution of this paper is to introduce a new way of measuring weight staleness and to explore the idea of penalizing the gradient itself to mitigate the staleness issue. The paper does a good job of discussing how GA can be applied to existing optimizers such as Adam. It performs empirical studies on ImageNet and Transformers-XL to conclude that GA-ASGD outperforms ASGD and the prior staleness aware approach. It also demonstrates the scalability of GA by scaling up to training with 128 asynchronous workers.
Strengths:
+ Introduced a novel approach to measure the parameter staleness, which helps penalize the gradients instead of the learning step. 
+ The approach seems to be easily applicable without much additional hyperparameter tuning. 
+ Evaluation on both image and NLP tasks demonstrate that GA leads to improvement over prior staleness aware approaches.
Weaknesses:
- Despite great improvements over prior ASGD based approaches, there is still a quite noticeable accuracy degradation compared to the SGD baseline. 
- The evaluation is done with simulation, and no report of the number of training steps to converge and end-to-end training time, making it difficult to compare the efficiency with SGD based approaches. 
Overall, I think this is good work. The idea of defining weights stableness as the minimal number of updates required to traverse the current distance between the master and worker weights seems to be reasonable. The comparison to prior ASGD based approaches are extensive, and the improvements seem decent. The fact that it does not require much or additional hyperparameter tuning also seems neat. 
My major concern comes from results compared to SGD and motivation. The fact that almost all ASGD based workloads, even with the help of GA, cannot get on-par accuracy as the SGD baseline bothers me. In particular, the accuracy drops considerably as the number of asynchronous workers grows (Fig 1. and Fig. 2, and Table 3). For example,  the gap between the accuracy of GA vs. SGD can be as large as 3.46% when there are 128 workers. That gap might be closed with additional hyperparameter tuning, but it is unclear from the current draft and results. In the Transformer-XL example, GA has to limit the number of asynchronous workers to 4 in order to get close to baseline accuracy. It would have been better to show the trade-off between accuracy and performance in comparison with SGD. 
On the other hand, the recent advance of SGD using large-batch training achieves great results on large model training such as BERT [1]. It helps to improve the compute/communication ratio, which seems to mitigate the straggler issue. Given that today's cloud service largely uses homogenous accelerators (TPU/GPU of the same SKU), it is less clear whether it is really beneficial to train with ASGD despite the improvements from GA.
Question:
One question is about how the batch size should be changed as the number of workers increases. The convergence analysis indicates that by increasing the batch size, the convergence speed of GA-ASGD will decrease. Does that mean the batch size should remain relatively unchanged to avoid negatively impacting the end-to-end training?
Is there any benefit to applying Gap to model parallelism paradigm such as pipeline parallelism?
[1] "Large Batch Optimization for Deep Learning: Training BERT in 76 minutes", by You et. al.