韭零后

公元1996 - ?

0%

分布式学习通信优化综述（2020香港大学）

发表于 更新于 分类于 ， ， ， 阅读次数： Valine：
本文字数： 10k 阅读时长 ≈ 9 分钟

综述名：Communication-Efficient Distributed Deep Learning: A Comprehensive Survey

发表年限：2020

简介：从以下四个维度对分布式训练算法进行介绍

  1. 通信同步和频次

    主要有以下两个方向：

    （1）宽松同步条件为异步并行（ASGD）或延迟同步并行（SSP）

    （2）本地多次迭代后进行通信

  2. 系统架构和梯度聚合

    （1）宽松参数服务器架构中的拥塞问题，MPI的去中心化拓扑

    （2）Gossip架构

    工作节点能够从听一个或多个节点中获取模型，解决拥塞问题，并且减少了通信量

  3. 压缩技术

    （1）量化

    （2）编码

    （3）稀疏化

  4. 通信和计算的并行

    简称为流水线算法，使得通信和计算充分并行。

分布式SGD通信优化——以表格方式归纳如下：

维度 方法
通信同步和频次 同步方法（SGD）
延迟受限同步
异步方法（ASGD）
本地SGD
系统架构 参数服务器架构
All-Reduce架构
Gossip架构
压缩技术 量化
编码
稀疏化
计算和同行并行 流水线方法
调度方法

分布式学习分类

通信同步和频次

同步并行

受限同步并行

[Chen et al.] [1]提出了候补节点\(n_e\)。主要思想是当有\(n\)个节点到达之后，就不再等待梯度还未到达的\(n_e\)个节点。它们的梯度值将会被舍去。

[Ho et al.] [2]提出了SSP模型，设定了一个阈值，允许在阈值之内，计算较快的工作节点迭代更多次数并更新全局参数，但是当最快节点和最慢节点到达阈值时，快速的节点需要等待慢速的节点回归合理阈值。

对于拥塞问题，[Chen et al] 提出了Round-Robin同步并行方法，该算法在整个训练过程中均匀交错工作节点更新，并以固定的循环顺序协调工作节点更新梯度。

异步并行

[Mote et al.] [3]提出了高通信效率的分布式交替方向乘数法（D-ADMM），他是对ADMM算法的扩展。[Wei et al.] [6][7]将其拓展为去中心化的ADMM算法。

之后有更多的学者对ADMM算法进行优化 [7]，[Li et al.] [8]提出了延迟闭塞近端梯度法（Delayed Block Proximal Gradient Method），该算法只在每次迭代过程中异步更新参数中的一块内容，因此在通信的过程中只需要上传一部分参数。

[Grishchenko et al.]提出了一种异步分配算法，其特点是向上通信(从工人到主人)的稀疏化，他们通过对本地更新条目的统一抽样选择来实现稀疏化，这使得通信更加高效。

但是异步的方法往往收敛性得不到保证。

本地SGD

基本思想是在多轮迭代之后进行通信[9][10][11][12][13][14][15][16][17]。

[Yu et al.] [18]结合了分布式动量的SGD方法和PR-SGD[19]方法来提高了本地SGD方法的性能，并且证明了线性加速比。

[Jiang et al.] [20]将量化方法和本地SGD方法做了结合，降低了通信的复杂度。

其他能够减少通信数据量的方法是提高批量大小。[Yu et al.] [21]提出了Catalyst-like[22][23]算法，能够在每轮迭代之后动态提高批量大小，并达到和SSP方法下沟通的收敛速率。

大批量的SGD方法会使得泛化性能降低。[Lin et al.] [24]提出了post-local SGD方法来解决这个问题。该算法将整个训练过程分为两个阶段，第一阶段采用小批量SGD，第二阶段采用局部SGD。

中心化和去中心化架构

量化方法

方法一

数据并行下的梯度量化方法其实是一种分布式平均估计问题[25][26]。[Suresh et al] [25]和[Jakub et al] [26]对分布式平均估计进行了通信效率算法的分析。他们使用均方误差的方法，并提出了一种在给定通信成本下的编码策略以达到最佳的MSE。为了减少通信成本，[Suresh et al.] [25] 提出了两种方法，随机旋转量化（Stochastic Rotated Quantization），所有工作节点和中央服务器生成一个全局随机旋转矩阵，并尝试找到一个正交矩阵\(\mathbb{R}\)。变长编码（Variable Length Coding）采用对应每个量化值出现次数的霍夫曼编码算法。

方法二

[Sei et al.] [27] 为了降低量化误差带来的负面影响，作者使用了误差补偿技术：每次量化时，把上一次迭代的量化误差加到本次迭代的梯度上，然后再进行量化，接着求出本次量化操作的误差。这种误差补偿机制可以确保所有的梯度都会再一定程度上对模型更新产生作用，只不过这种作用分散在不同的迭代中——类似于一种延迟更新的形式。作者指出，使用误差补偿后，就可以在几乎不损失模型精度的情况下将梯度由32位量化成1位。 \[ \begin{aligned} G_{i j \ell}^{\text {quant }}(t) &=\mathcal{Q}\left(G_{i j \ell}(t)+\Delta_{i j \ell}(t-N)\right) \\ \Delta_{i j \ell}(t) &=G_{i j \ell}(t)-\mathcal{Q}^{-1}\left(G_{i j \ell}^{\text {quant }}(t)\right) \end{aligned} \] 其中\(\mathcal{Q}(\cdot)\)表示量化函数，\(G_{i j \ell}^{\text {quant }}(t)\)表示量化之后的整型数值。我们在量化过程中会保证\(\Delta_{i j \ell}(t)\)被加到下一轮的梯度过程中（也称为了误差补偿机制）。

举个例子，在具体的实现上，比较简单的方法是将大于\(0\)的梯度值编码成为\(1\)，小于等于\(0\)的梯度值编码为\(0\)。在解码的时候，将\(1\)编码为\(+1\)，将\(0\)解码为\(-1\)，在进行聚合操作。

其他一些研究采用不精确的近端梯度提出了自适应的量化方法[168][169]，但是这些方法缺乏在深度学习模型种的实践。

考虑到需要同时具备高通信效率和好的收敛性，[Alistarh et al.] [28] 提出了一种基于量化的算法，而不仅仅只是量化方法。这种量化算法叫做QSGD，可以平衡传输的比特数与压缩梯度的方差。

方法三

[Wen et al.] [29] 提出了另一种叫做TernGrad的压缩通信量的模式，它可以使用三元梯度来加速分布式深度学习。在TernGrad中，梯度\(G(x)\)被量化为三元组\(\{-1,0,1\}\)来减少通信量化大小。梯度\(G(x)\)量化如下： \[ \tilde{Q}_{t}\left(G\left(\mathbf{x}_{t}\right)\right)=\operatorname{ternarize}\left(G\left(\mathbf{x}_{t}\right)\right)=s_{t} \cdot \operatorname{sign}\left(G\left(\mathbf{x}_{t}\right)\right) \circ \mathbf{b}_{t} \] 其中\(s_{t}:=\max \left(a b s\left(G\left(\mathbf{x}_{t}\right)\right)\right)\)以及$ \(表示哈达玛积。\)()\(和SGD中的\)()\(是一致的。每个\)b_t$元素遵循如下分布： \[ \begin{array}{l} P\left(b_{t, j}=1 \mid G_{t}\left(\mathbf{x}_{t}\right)\right)=\left|G_{t, j}\left(\mathbf{x}_{t}\right) / s_{t}\right| \\ P\left(b_{t, j}=0 \mid G_{t}\left(\mathbf{x}_{t}\right)\right)=1-\left|G_{t, j}\left(\mathbf{x}_{t}\right) / s_{t}\right| \end{array} \]

方法四

Sign-SGD是另外一种量化方法 [30]。在Sign-SGD中，每个工作节点将梯度量化为二进制值，它是梯度向量的每个坐标的符号。[Bernstein et al.] [31]提供了基于该方法在非凸优化上的理论分析。他们证明了当梯度与随机度和曲率一样稠密或更密集时，Sign-SGD可以以一个理论速率收敛。[Bernstein et al.] [31]还提出了一种具有大多数投票的Sign-SGD方法。在工作节点将他们的梯度向量的符号交换到服务器后，整体的更新由多数人投票决定。通过这种方法，将通信成本降低了32倍。

方法五

[Wang et al.] [32]提出了一种新的方法叫做原子稀疏化方法（Atomic Sparsification (ATOMO)）。他证明了梯度稀疏化和量化是原子分解过程中梯度稀疏化的一般方法的一部分，例如QSGD、奇异值分解（SVD）、傅里叶分解等。ATOMO的目标是最小化在原子基础上稀疏的稀疏梯度的方差，并保持它作为原始梯度的无偏估计量。它们说明了1位的QSGD和TernGrad是ATOMO的特殊情况。此外，他们用SVD改进了ATOMO，称为Spectral-ATOMO。在他们的实验中，与QSGD和TernGrad相比，Spectral-ATOMO分别减少了2倍和3倍的训练时间。

方法六

[Mishchenko et al.] [33]介绍了DIANA这种创新方法，它扩展了QSGD和Terngrad这两种方法，将这个梯度向量划分成多个子向量，并将每个子向量进行独立压缩。

方法七

[Sun et al.] [34]的LAQ方法

方法八

[Horvth et al.] [36]提出了一种新的压缩方法，叫做自然压缩(Natural Compression)。这种压缩方法定义如下： \[ C_{n a t}(t):=\left\{\begin{array}{ll} \operatorname{sign}(t) \cdot 2^{\left\lfloor\log _{2}|t|\right\rfloor}, & \text { with probability } p(t) \\ \operatorname{sign}(t) \cdot 2^{\left\lfloor\log _{2}|t|\right\rfloor}, & \text { with probability } 1-p(t) \end{array}\right. \]

其中\(p(t):=\frac{2^{\left\lceil\log _{2}|t|-|t|\right\rceil}}{2^{\left\lfloor\log _{2}|t|\right\rfloor}}\)。他们提出的这种压缩方法能够将方差忽略不计，因此有较好的收敛性。这个方法的一个优势是\(C_{nat}\)能够去掉二进制表示中的尾数。他们提出了与QSGD的抖动是类似的。

[Yu et al.] [35]提出了名为AsyLPGd低精度算法，在异步框架中使用，同时量化梯度和模型参数。它使用额外的要求来限制量化级别。他们将稀疏化方法和AsyLPG相结合，进一步降低通信的复杂度。

稀疏化方法

计算和通信流水线调度

未来优化方向

参考文献

相关文章推荐