Communication-efficient SGD: From Local SGD to One-Shot Averaging
Communication-efficient SGD: From Local SGD to One-Shot Averaging
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Artin Spiridonoff;Alexander Olshevsky;I. Paschalidis
中科院分区：
文献类型：
--
作者：
Artin Spiridonoff;Alexander Olshevsky;I. Paschalidis
我们考虑通过在多个工作人员之间并行化来加速随机梯度下降（SGD）。我们假设相同的数据集在 $N$ 工作人员之间共享，他们可以采取 SGD 步骤并与中央服务器协调。虽然可以通过对每一步的所有随机梯度进行平均来获得方差的线性减少，但这需要工作人员和服务器之间进行大量通信，这会大大减少并行性的收益。早期文献中提出并分析的本地 SGD 方法建议机器应该在此类通信之间执行许多本地步骤。虽然局部 SGD 的初步分析表明它需要 $\Omega ( \sqrt{T} )$ 通信来进行 $T$ 局部梯度步长，以便误差按比例缩放到 $1/(NT)$，但这已在一系列论文中相继得到改进，最先进的技术需要 $\Omega \left( N \left( \mbox{ poly} (\log T) \right) \right)$ 通讯。在本文中，我们建议采用一种局部 SGD 方案，随着迭代次数的增加，通信频率会降低，从而减少总体通信量。我们的分析表明，对于完全独立于 $T$ 的大量通信，这可能会导致 $1/(NT)$ 的误差。特别是，我们表明 $\Omega(N)$ 通信就足够了。经验证据表明，当我们进一步表明 $\sqrt{N}$ 或 $N^{3/4}$ 通信无法在模拟中实现线性加速时，这个界限接近紧密。此外，我们表明，在温和的假设下，主要是最优解的任何邻域上的两次可微分，仅使用单轮通信的一次性平均也可以渐近地达到最优收敛速度。
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. While it is possible to obtain a linear reduction in the variance by averaging all the stochastic gradients at every step, this requires 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{ poly} (\log T) \right) \right)$ communications. In this paper, we suggest a Local SGD scheme that communicates less overall by communicating less frequently as the number of iterations grows. Our analysis shows that this can achieve an error that scales as $1/(NT)$ with a number of communications that is completely independent of $T$. In particular, we show that $\Omega(N)$ communications are sufficient. Empirical evidence suggests this bound is close to tight as we further show that $\sqrt{N}$ or $N^{3/4}$ communications fail to achieve linear speed-up in simulations. Moreover, we show that under mild assumptions, the main of which is twice differentiability on any neighborhood of the optimal solution, one-shot averaging which only uses a single round of communication can also achieve the optimal convergence rate asymptotically.