分布式同步SGD与异步SGD

深度学习分布式训练的典型方法是基于异步随机优化，这样的方式往往以增加由异步带来的随机噪音为代价。与之相反，同步的方式常常被认为不实际，这是因为部分workers需要浪费大量空闲时间等待拖后腿的wokers。文献[1]中作者们对同步的随机优化进行了改进，使深度学习算法可被高效的训练且性能得到提升。确切的说，缓和同步随机优化中拖后腿的方法是：只同步计算部分wokers的mini-batch梯度，其余的梯度drop掉。这种方式不仅减轻了拖后腿效应也避免了梯度的过时性。

基本定义

给定数据集$\mathcal{X}=\{x_i:i=1,\ldots,\vert\mathcal{X}\vert\}$，目标为：基于经验损失函数$f(\theta)\triangleq\frac{1}{\vert\mathcal{X}\vert}\sum_{i=1}^{\vert\mathcal{X}\vert}F(x_i;\theta)$更新模型参数$\theta$。其中$F(x_i;\theta)$为模型$\theta$在数据点$x_i$的损失项。

一阶随机优化算法通过随机梯度$G\triangleq\nabla F(x_i;\theta)$迭代性更新$\theta$，从而产生一系列模型$\theta^{(0)},\theta^{(1)},\ldots,\theta^t$。mini-batch版本的随机优化算法计算batch大小为$B$的平均梯度，即$G\triangleq\frac{1}{B}\sum^B_{i=1}\nabla F(\tilde{x}_i;\theta^t)$。

分布式随机优化是利用$N$个worker机器计算随机梯度，再发给$M$个服务器。每个参数服务器$j$负责存储模型部分参数$\theta[j]$，执行参数$\theta[j]$的更新。

异步随机优化

文献[2]中分布式随机梯度下降算法由两个部分组成。第一部分为：模型参数分布在多个服务器上，被称为参数服务器。第二部分为：多个workers并行处理数据，且与参数服务器交流。具体如下：

• worker从参数服务器中取到最新的模型参数，用于处理当前mini-batch数据。
• 计算参数的梯度。
• 计算得到的梯度发送到参数服务器，用于更新模型。

由于每个worker独立的与参数服务器交流，因此该方法被称作异步随机梯度下降。异步随机梯度下降算法，可见图1所示。

异步随机梯度下降算法与串行随机优化算法之间的不同，主要存在两个原因。第一个原因是每个worker从参数服务器读取参数时，可能被其它的workers更新参数服务器中参数所干预，从而导致$\hat{\theta}_k$与任何时刻参数$\theta^t$不一致。第二个原因是workers计算随机梯度时模型可能已经更新，从而导致产生的梯度对应的是过时的参数。文献[1]作者们把这些梯度称为过时梯度。根据算法2，可知，Async-SGD中参数服务器利用指数平均更新参数，用于缓和过时梯度的问题。

同步随机优化

简单来说，同步随机优化算法就是参数服务器等待所有worker发送梯度，再更新模型。最后，发送更新后的参数到所有workers。这种方式虽然解决了过时性的问题，但是真实参数更新取决于最慢的worker，因此大大降低了梯度的更新速度。为了减轻这种问题，文献[1]作者们引入了备份workers，可以理解为：利用$N+b$个workers计算梯度，只要参数服务器收到$N$个workers的梯度，那么就更新参数，其余的$b$个workers的梯度被drop掉。如图2所示，同步随机梯度下降算法伪代码。

参考文献

[1] Chen J, Pan X, Monga R, et al. Revisiting distributed synchronous SGD[J]. arXiv preprint arXiv:1604.00981, 2016.

[2] Dean J, Corrado G, Monga R, et al. Large scale distributed deep networks[J]. Advances in neural information processing systems, 2012, 25.