We consider speeding up stochastic gradient descent (SGD) by parallelizing it across multiple workers. We assume the same data set is shared among $n$ workers, who can take SGD steps and coordinate with a central server. Unfortunately, this could require a lot of communication between the workers and the server, which can dramatically reduce the gains from parallelism. The Local SGD method, proposed and analyzed in the earlier literature, suggests machines should make many local steps between such communications. While the initial analysis of Local SGD showed it needs $\Omega ( \sqrt{T} )$ communications for $T$ local gradient steps in order for the error to scale proportionately to $1/(nT)$, this has been successively improved in a string of papers, with the state-of-the-art requiring $\Omega \left( n \left( \mbox{ polynomial in log } (T) \right) \right)$ communications. In this paper, we give a new analysis of Local SGD. A consequence of our analysis is that Local SGD can achieve an error that scales as $1/(nT)$ with only a fixed number of communications independent of $T$: specifically, only $\Omega(n)$ communications are required.

本文探讨了同时跨越多个工作者并进行随机梯度下降（SGD）来加速SGD的方法。通过对Local SGD的新分析，本文证明当机器在通信变现之间进行多个本地步骤时，Local SGD方法可以实现错误按照$1/（nT）$的比例缩放，只需进行固定数量的通信，而无需不断增加通信次数。

基于工作者数量的通信开销仅受限于本地化随机梯度下降