Communication-efficient Decentralized Machine Learning over Heterogeneous Networks（笔记）

文章目录 问题设计定义问题定义符号定义迭代步迭代时间通信策略矩阵 方法概述Network Monitor 训练通信策略生成优化问题生成算法

问题

机器内部的链路速度和机器之间以及机架之间的链路速度差别很大。对于在数据中心中的模型训练，广域网的链路速度又与地理的分布相关，距离近的链路速度快。不同分布式学习任务之间的网络竞争也很容易增大链路速度之间的差异。除此之外，由于其他学习任务的到达离开或者网络带宽的重新分配，链路速度可能会动态变化。

因此，此文试图解决的问题就是：在保证收敛性的条件下，在链路速度动态变化的异构网络中，充分利用高速链路传输参数来加速分布式机器学习。

设计

作者设计了NetMax，创新点有三个：(1) 工作节点使用consensus SGD算法在本地数据上异步地训练模型，每个节点每次迭代随机选择一个邻居进行通信，(2) 有高速链路的邻居有高概率被选中，(3) 根据检测到的链路速度，通信策略生成算法更新选择邻居通信的概率，使训练适应动态的网络。

定义

首先定义标记如下表：

问题定义

定义此去中心化训练为一个无约束一致优化问题：

其中 x i x_i xi​和 f ( x i ; D i ) f(x_i;D_i) f(xi​;Di​)分别是工作节点的模型参数和损失函数。 d i , m d_{i, m} di,m​是连接指示符，是1代表工作节点i和m是邻居，是0则不是邻居。 ∥ x i − x m ∥ 2 \left\| x_i - x_m \right\|^2 ∥xi​−xm​∥2 衡量节点i和m之间的模型差异（如果它们是邻居）。权重 ρ \rho ρ指示在目标函数中邻居之间模型差异的重要性。综上，以上公式的目标是最小化分布式工作节点的损失函数和它们的模型差异，确保所有节点都能收敛到同样的最优解。

符号定义 迭代步

n是一个工作节点的局部迭代步数，当此节点和一个邻居通信时加1。k是全局迭代步数，任何工作节点的局部迭代步数增加都会导致k增加。在一个全局迭代步骤中，只有一个工作节点和邻居通信。

迭代时间

对于一个工作节点i， C i C_i Ci​表示局部计算时间， N i , m N_{i, m} Ni,m​表示节点i和邻居节点m的网络通信时间。标记迭代时间（整个局部迭代步的持续时间）为 t i , m t_{i,m} ti,m​。在这篇论文中，作者并行化节点中的局部计算和网络通信，所以迭代时间被计算为：
t i , m = m a x { C i , N i , m } t_{i,m} = max\{C_i, N_{i,m}\} ti,m​=max{Ci​,Ni,m​}
经观察，通信时间往往占主导地位。

通信策略矩阵

P = [ p i , m ] M × M P=[p_{i,m}]_{M\times M} P=[pi,m​]M×M​是通信策略矩阵，其中 p i , m p_{i,m} pi,m​表示节点i选择节点m作为邻居进行通信的概率。 t i ‾ \overline{t_i} ti​​表示节点i的平均迭代时间：
t i ‾ = ∑ m = 1 M t i , m ⋅ p i , m ⋅ d i , m \overline{t_i}=\sum_{m=1}^{M}t_{i,m}\cdot p_{i,m}\cdot d_{i,m} ti​​=m=1∑M​ti,m​⋅pi,m​⋅di,m​

方法 概述

整体设计如下：

Network Monitor

为了估计网络状态，Network Monitor周期性地收集每个工作节点的迭代时间，迭代时间反映了工作节点之间的链路速度。收集周期记为 T s T_s Ts​，能够根据网络条件动态调整。下面的算法展示了Network Monitor的计算过程：

计算结果是通信策略矩阵P和差异权重 ρ \rho ρ，它们被动态调整以加快训练收敛。

训练

对上面的公式(1)求导，工作节点i的梯度可由以下公式计算得到：

其中 x i n x_i^n xin​是模型参数， D i , n D_{i,n} Di,n​是从节点i的数据集 D i D_i Di​抽样来的数据，n代表第n个局部迭代步。

但是，这样做一个工作节点要从它所有的邻居拉取参数，这导致了训练过程会被低速链路拉慢。为了减少通信时间，每次迭代工作节点只从一个选中的邻居那里拉取模型参数，有高速链路连接的邻居更可能被选中。

总之，在每次迭代中，一个工作节点首先根据局部数据计算来的梯度更新模型，然后拉取一个邻居的模型参数再次对模型进行更新。以下为具体细节：

值得注意的是，梯度的计算和参数的传输是并行的，可以进一步减少训练时间。而且，在13行，梯度除以了一个 p i , m p_{i,m} pi,m​，含义是，如果一个邻居以一个更低的概率被选中，那么算法会赋予此次模型更新更高的权重。这使得这个节点能够从低概率选中的节点中获取足够的信息。

算法根据指数移动平均（EMA）计算迭代时间，参数 β \beta β代表了移动平均的窗口大小。当链路速度变化较快时，应使用较小的 β \beta β来获取最新的速度，Network Monitor的策略计算周期 T s T_s Ts​也应较短。

通信策略生成 优化问题

通信策略生成的目的是最小化收敛时间，即最小化 k t ‾ k\overline{t} kt，其中 t ‾ \overline{t} t是全局的平均迭代时间，k是全局迭代步数。提出以下优化问题：

以下内容的具体推理可以看文章

工作节点的训练可以写成矩阵形式：

x k x^k xk和 g k g^k gk分别是第k个全局步中的所有节点的模型参数和梯度。 D k D^k Dk是在第k个全局步中和通信策略矩阵P相关的随机矩阵。模型和最优解 x ∗ x^* x∗的偏移可以表示为：

其中 λ \lambda λ是矩阵 E [ ( D k ) T D k ] E[(D^k)^TD^k] E[(Dk)TDk]的第二大特征值，其值严格小于1。所以式(9)永远满足。而且 λ \lambda λ越小，k越小，收敛越快。

式(10)通过让 E [ ( D k ) T D k ] E[(D^k)^TD^k] E[(Dk)TDk]的行加和为1得到。让 E [ ( D k ) T D k ] E[(D^k)^TD^k] E[(Dk)TDk]中 d i , m ≠ 0 d_{i,m}\neq0 di,m​=0对应的项大于0，得到式(11)。

生成算法

通信策略生成算法如下：

核心思想是找到一个策略矩阵P，得到目标值的一个可行的次优解。(此时也得到了对应的 ρ \rho ρ的值)

外层循环在可行区间 [ L ρ , U ρ ] [L_{\rho},U_{\rho}] [Lρ​,Uρ​]中搜索K个 ρ \rho ρ值，对于每个给定的 ρ \rho ρ，使用一个内层循环得到次优矩阵P，最后在这些矩阵中选择一个使目标值最小的矩阵。内层循环INNERLOOP在可行区间 [ L , U ] [L,U] [L,U]中搜索R个 t ‾ \overline{t} t值（ ρ \rho ρ给定）。对于每个 t ‾ \overline{t} t值，解决一个线性规划问题得到次优矩阵P，线性规划问题如下：

式(14)寻求最小化分布式工作节点选择自己通信的概率。这样的设计鼓励节点和邻居交换信息，期望达到一个较高的收敛速度。