Asynchronous Distributed Learning Based on Gradient Coding

In this paper, we study the problem of distributed learning (DL), where different devices take varying amounts of response time to complete local computations during training. To deal with this problem, existing gradient coding (GC) techniques are designed in a synchronous setting, where the server waits for a fixed number of the fastest devices to transmit the coded gradients in each iteration to fully recover the global gradient. However, there are significant inefficiencies in these GC techniques, since the computations performed by the slow devices are wasted and their information is not required by the server to update the global model. To overcome this limitation, we propose a novel asynchronous DL method based on GC (AGC). In AGC, the training data subsets are replicated and allocated to the devices redundantly, and the devices encode local gradients of its local subsets and send the coded gradients to the server. The server updates the global model in an asynchronous manner based on the coded gradients received from a certain number of devices, which may be computed from the global models back in history as well as the most recent one. In this way, the computations of the slow devices can also be exploited, helping to increase training efficiency and reduce training time. We provide a convergence analysis for AGC in asynchronous settings with frequent global synchronization, and show that it achieves an $\boldsymbol{O}\mathbf{(1}\boldsymbol{/\sqrt{T}}\mathbf{)}$ convergence rate. Finally, numerical results demonstrate the superiority of the proposed method compared to the baseline methods, where AGC achieves better learning performance after the same training time.