## 3 The Proposed Method: SHAT
### Asynchronous Distributed Training  
In this section, we review asynchronous distributed training [6; 7] and identify the limitation in updating local models of workers. Figure 2 illustrates the difference between synchronous and asynchronous distributed training. In synchronous distributed training, the local models of all workers are synchronized by PS aggregating the gradients from all workers (see Figure 2a). In each iteration, each worker performs computing operations (i.e., forward/backward passes), sends its computed gradients to PS, and receives the updated global model from PS. Then, each worker replaces its local model with the global model and proceeds to the next training iteration. Here, all workers have the exactly same model since they receive the same global model from PS at the same time. However, the synchronization overhead might be quite significant when some workers fall behind other workers for computing operations (e.g., worker 1 in Figure 2a), which may degrade the overall training performance significantly.  
To improve the performance of synchronous training, asynchronous distributed training aims to reduce the synchronization overhead by adopting asynchronous communication between PS and workers. In asynchronous distributed training, PS processes the gradients from each worker in an asynchronous manner, that is, PS receives the gradients of each worker, updates the global model using them, and then sends the updated global model right back to the worker immediately. Thus, each worker can proceed to the next iteration without waiting for other workers. As clearly illustrated in Figure 2b, in asynchronous distributed training, there is no synchronization barrier.  
However, each worker receives a different version of the global model at a different point since it communicates with PS independently. Such an inevitable difference would increase as the scale of distributed training and the heterogeneity among workers get larger, which would adversely affect the global model convergence (thus, delaying the model convergence). This is because the gradients computed based on the different local models of workers lead to different learning directions, that is, the larger the difference among local models of workers is, the more different directions of gradients are. When the gradients with different directions are applied to the global model in PS, they are likely to interfere with each other in the global model convergence [7; 11; 14]. More specifically, when there is an extremely slow worker (i.e., straggler) in a distributed cluster, other normal workers can update the global model many times while the straggler computes its gradient locally. Thus, the gradient computed by the straggler becomes stale and is highly likely to lead the global model in PS to the wrong direction. Therefore, it is important to reduce the difference among local models of workers by accurately considering the scale of distributed training and the heterogeneity among workers in asynchronous distributed training.  
In existing asynchronous distributed training, however, each worker just replaces its local model with the global model. Thus, when updating the local model of each worker, it does not consider (1) how many workers are joining in distributed training (i.e., the scale of distributed training) and (2) their performance difference (i.e., the heterogeneity among workers), which may cause a serious problem in the model convergence as we explained. Motivated from these limitations, we propose an update strategy for the local model of each worker to speed up the model convergence in asynchronous distributed training by considering the scale of distributed training and the heterogeneity among workers together.