标题： 具有更低通信复杂度的方差减少局部SGD 显示英文标题

标题： Variance Reduced Local SGD with Lower Communication Complexity

摘要： 为了加速机器学习模型的训练，分布式随机梯度下降（SGD）及其变体被广泛采用，这些方法通过并行使用多个工作器来加快训练速度。其中，由于本地SGD具有较低的通信成本而备受关注。然而，当工作器上的数据分布不同时，本地SGD需要进行 $O(T^{\frac{3}{4}} N^{\frac{3}{4}})$ 次通信以保持其 \emph{线性迭代加速} 特性，其中 $T$ 是总迭代次数， $N$ 是工作器的数量。 本文中，我们提出了方差减少的本地SGD（VRL-SGD），进一步降低了通信复杂度。得益于消除了工作器之间梯度方差的依赖性，我们在理论上证明了即使工作器访问的是非相同的数据集，VRL-SGD也能达到一个 \emph{线性迭代加速} 的结果，并且具有更低的通信复杂度 $O(T^{\frac{1}{2}} N^{\frac{3}{2}})$。我们针对三个机器学习任务进行了实验，实验结果表明，当工作器之间的数据非常多样化时，VRL-SGD的表现明显优于本地SGD。 显示英文摘要

摘要： To accelerate the training of machine learning models, distributed stochastic gradient descent (SGD) and its variants have been widely adopted, which apply multiple workers in parallel to speed up training. Among them, Local SGD has gained much attention due to its lower communication cost. Nevertheless, when the data distribution on workers is non-identical, Local SGD requires $O(T^{\frac{3}{4}} N^{\frac{3}{4}})$ communications to maintain its \emph{linear iteration speedup} property, where $T$ is the total number of iterations and $N$ is the number of workers. In this paper, we propose Variance Reduced Local SGD (VRL-SGD) to further reduce the communication complexity. Benefiting from eliminating the dependency on the gradient variance among workers, we theoretically prove that VRL-SGD achieves a \emph{linear iteration speedup} with a lower communication complexity $O(T^{\frac{1}{2}} N^{\frac{3}{2}})$ even if workers access non-identical datasets. We conduct experiments on three machine learning tasks, and the experimental results demonstrate that VRL-SGD performs impressively better than Local SGD when the data among workers are quite diverse.