分布式机器学习：算法、理论与实践——【1】

分布式机器学习笔记

刘铁岩老师出的新书《分布式机器学习：算法、理论与实践》中摘录了一些笔记，总体来说这本书偏向综述，给出了大量的参考文献，可供后续进一步学习

数据与模型并行

数据并行
- 数据样本切分方式
  - 随机采样（有放回）
    - 优点：满足局部数据与原始数据是独立同分布
    - 缺点：1）数据量大时全局采样复杂度比较高2）少量出现的样本有可能
  - 置乱切分（无放回）
    - 优缺点正好与随机采样相反
- 按数据维度切分
  - 只适用特定算法，如：决策树或线性模型
模型并行
- 神经网络
  - 横向按层划分
    - 为避免节点之间等待，可以设计成节点之间的流水线
  - 纵向跨层划分
  - 模型随机划分

通信机制

如果计算与通信的时间占比为1：1，那么根据Amdahl’s law（阿姆达尔定律）无论用多少机器并行计算，其加速比也不会超过两倍
通信拓扑：
- 基于迭代式MapReduce/AllReduce
  - 注意allreduce通信算法的设计，可以减少通信次数和通信量
  - 很多神经网络训练是基于AllReduce的
    - caffe2的gloo
    - nvidia的NCCL
- 基于parameter server
  - cmu的parameter server
  - 微软的multiverso
- 基于图的拓扑（tensorflow）
通信的步调
- 同步通信
- 异步通信
降低通信频率
- 增加通信间隔
  - 异步通信模式在凸优化下可以保证不降低精度
- 非对称的推送和获取
  - 异步通信模式下，推送梯度和更新工作节点的参数步调不一致
- 计算和传输流水线
  - 比较巧妙，通信和计算分两个线程，计算线程每完成一次就把计算线程的结果buffer和通信线程的结果buffer做一次对调，然后两个线程再继续推进
降低传输数据量
- 如果梯度更新小于阈值，则不传输
- 模型用svd分解，降为低秩后，再传输
- 模型量化（bit化）后传输，关键在于量化方法

分布式机器学习算法

收敛速度衡量： $E|| w_T - w^*||^2 leq epsilon(T)$

学术界针对随机梯度优化算法的改进方向：

通过缩减随机优化算法的方差提高对数据的利用率
- SVRG，SAG，SAGA
在基本的随机优化算法的基础上与其他优化算法组合，从而得到更快的收敛速度
常见分布式机器学习算法及其特点

分布式机器学习算法	每个worker优化	划分	通信	聚合
同步SGD	SGD	数据样本划分	同步通信	全部模型梯度加和
模型平均（MA）	不限	数据样本划分	同步通信	全部模型加和
BMUF	SGD	数据样本划分	同步通信	全部模型加和
ADMM	不限	数据样本划分	同步通信	全部模型加和
弹性平均SGD(EASGD)	SGD	数据样本划分	同步/异步通信	全部模型加和
异步SGD（ASGD）	SGD	数据样本划分	异步通信	部分模型加和
Hogwild！	SGD	数据样本划分	异步无锁通信	部分模型加和
AdaDelay	SGD	数据样本划分	异步通信	部分模型加和
。。。

一些研究表明：

凸优化中，随机样本带来的噪声远大于异步延迟带来的噪声，因此ASGD完全能达到单机SGD相同的收敛速率
非凸问题中，异步延迟引入的额外随机性可能帮我们探索更多更好的局部最优点，缓解训练中的过拟合问题
分析异步更新的迭代公式，可以把异步更新理解为冲量的作用，这个角度也说明异步更新机器数量不能太多

Hil_C对《分布式机器学习：算法、理论与实践》的笔记(18)

第43页

数据划分：

通过全局随机采样或者shuffle来进行划分时，前者问题是全局采样代价比较高，并且低频的数据难以被选择出来，后者问题是置乱切割，把全局数据shuffle之后分配到各个节点上，但是问题是乱序操作等价于或者接近于无放回的操作对很多机器学习理论中中的IDD假设不能满足。

数据划分还可以通过对维度的切分来划分，但是这时候适用的优化方法有限，例如坐标下降法，其余的由于不同维度之间计算的依赖，有非常大的通讯代价。

模型划分：

线性模型根据维度划分，深层神经网络划分考虑模型的逐层划分与纵向划分。

逐层划分的依赖关系接口清晰，但是并行度可能不够，因为一层的参数就超出了一个节点的容量了。跨层的纵向划分的依赖关系复杂，实现起来难度很大。

模型划分的随机划分手段：规模更小的骨架网络，骨架网络存在于每个工作节点，传输非骨架结构的参数，探索全局的结构。骨架网络的选取可以是周期性更新的，对全局拓扑结构的探索也是动态/随机的，大大减小模型并行的通信代价，对模型并行的效果有一定保证。

2019-02-17 16:06:54 回应

第47页

数据并行的框架下，通讯内容可以是子模型，或者非常重要的的样本（SVM中可以使用SV）。

模型并行就是中间的计算结果，可以用计算图和数据流来表示，传输量比较大可以考虑对信息进行压缩。

MapReduce通信的拓扑结构：

1.二分图的MapReduce的想法导致的问题是完全依赖硬盘IO逻辑导致的数据互访会使得效率很低。

2.中间状态不能维持，无法高效衔接。

迭代式MapReduce的结构：

1.完全依赖于内存的实现，不需要依赖IO接口（问题是这时候运算节点和逻辑存储节点没有很好的逻辑隔离，所以需要同步通信，Mapper运算步骤结束之后才能开Reuduce过程）

2.perisistent store中间的结果

3.MapReduce的使用范围并不是很大

通过Parameter Server的星型拓扑结构：

1.逻辑隔离的实现，更加灵活地支持不同的通讯模式，不需要时刻保持同步

2.多个参数服务器存储较大的结构，访问一部分参数的时候能够进一步优化

通过局部连接的拓扑结构（之和少数邻居进行信息的交互）：

1.去中心化，减少了瓶颈，不需要考虑全局通信的高昂代价

2019-02-17 18:34:04 1人喜欢回应

第49页

1.同步

早期盛行是由于MapReduce并且同步的方式在逻辑上清晰明了，但是有短板效应和系统宕机的时候

2.异步

有锁：保证写入的完整性，但是影响了吞吐量

无锁：不能保证全局的完整性

步调差异会导致的问题，会导致更新较慢的节点对全局模型的收敛造成问题。

算法：异步SGD HogWild！Cyclades 对延迟不敏感：AdaptiveRevision AdaDelay 补偿延迟：延迟补偿的异步SGD

混合的方法：

SSP，设置一个最快的阈值，最快的节点的超过阈值就要等大。在延迟不太大的时候可以考虑。

或者分组，根据快慢分等级，组内同步，组间异步通讯。

2019-02-17 20:53:14 回应

第51页

通信的频率是一个大问题

1.通信频繁对模型收敛的效果有保障，但是代价很大。

是处理完mini-batch之后开始通信还是全部本地数据处理完之后通信？通信的收发频率是否需要一致？不同的频率对模型的收敛是否有影响？想要基于计算速度，带宽，数据大小，模型大小，计算出一个最优的通信频率，从而取得计算代价和通信代价的最优匹配。

不降低通讯频率想要减小带宽——空域滤波（压缩模型，降低模型精度或者低秩处理或者随机丢弃）

2019-02-17 21:01:22 回应

第52页

聚合的问题

1.简单平均

2.寻求一个一致的优化问题的解：ADMM或者BMUF

凸问题的保证，但是非凸的时候，局部凸函数使得聚合结果劣于局部的。

3.模型集成

通过保留参数来提高精度，但是会模型爆炸。

另外一个问题是是都选择接受所有的局部模型，抛弃速度较慢的是一个选择（带有备份工作节点的SGD以及异步ADMM）

PS给出的全局模型是否全部信任与接受（弹性SGD）

2019-02-17 21:14:51 回应

第53页

机器学习分布式理论的问题：

收敛性：不同方法的收敛速度和性质，每个模块对整体的收敛速度产生怎么样的影响，按照优化目标，本地优化算法，并行模式，通信和聚合方式进行归纳

加速比：除了与算法的收敛速度有关，还受通信-计算的时间比的影响。还有要实现收敛我们需要的最小通信量也是可以研究的方向。

泛化性质

2019-02-17 21:41:01 回应

第54页

1.平台灵活角度：MapReduce最低，需要遵循执行流程，PS最高，数据流由于DAG的形式居中

2.算法效率：同步逻辑的MapReduce最差，后两者因为异步较好

3.处理的任务：Spark MLlib浅层模型，TF提供了很多算子与优化器

2019-02-17 21:46:09 回应

单机优化之确定性算法

常见的非随机优化算法罗列。

2019-02-18 15:26:59 回应

第108页

1.计算并行模式：所有工作节点共享一块内存，对数据有完全的访问权限。

2.数据并行模式：数据样本划分的全局有放回随机抽样或者置乱划分基于维度

3.模型并行模式：线性模型对应不同数据维度的模型参数划分到不同的工作节点上，只需要全局信息和自己参数的信息，就能运算

emmmmm内容与前面重复了

2019-02-18 21:54:46 1人喜欢回应

第133页

对模型参数更新进行通信，往往有利于提高分布式机器学习的效率，因为在很多机器学习任务中，参数以及参数的更新任务往往是稀疏的。同时随着模型趋于收敛，参数的更新也会越来越小，另外可以使用量化或者过滤的方法进一步减少通信数据量。

节点的特性运用到机器学习里面的决策能力与泛化能力感觉可以用传统机器学习的大套路套进来

2019-02-19 23:20:10 回应

第135页

MPI特点是同步吗？把通讯抽象成图的边不合理，通讯的体量和计算的体量差别大小

暑假看的07年的通信拓扑的总结性理论paper要标星星了

2019-02-19 23:32:48 1人喜欢回应

第137页

总结一下现在各大的使用到了的MPI模式的框架

Caffe2中的gloo通信库实现了自定制的AllReuce功能，百度的DeepSpeech系统采用了环状的AllReduce功能，Nvidia提供的集合通讯库NCCL中有AllReduce的原语

2019-02-19 23:38:27 回应

第138页

因为IMR和MPI同步通信中的短板效应

worker对server的访问有push与pull 非常灵活

CMU的Parameter Server和Petuum谷歌的DistBelief和微软的DMTK/Multiverso

2019-02-20 00:35:07 回应

第140页

并不把边设置成通讯而是数据依赖的表示很不错

这种通信拓扑是基于DAG。出现在图中的工作节点不仅包含计算本身，而是一个融合了解包，计算，打包，通信控制等多个功能的逻辑单元，这样各个工作节点才可以相互配合和衔接，从而合作完成整体的运算任务。每个节点需要两个通信通道：控制消息流和计算数据流。

2019-02-20 01:11:33 回应

第175页

同步SGD类

同步SGD相当于一个批量大小增大K倍的minibatch，批量增加K倍后，算法的收敛速度满了K开方，吞吐增加了K倍，所以增加了K倍的速度。但是这并没有包括通讯。

如果每个小批量训练的计算量很大，而模型规模又不大（CNN），通信开销可以忽略。反之，无法忽略。

通过前一章节的内容，可以实现提速。

关于精度的分析，参考SGD的minibatch size选择的论文

1.增大size导致方差变小，减少了跳出了局部最优的可能。实现了尖锐的局部最优，但是更加精确，所以可以增加学习率，逐步增大学习率。

2.减小，会导致收敛到平坦的局部最优，平坦区域泛化能力更强

3.

2019-02-20 23:01:14 回应

第179页

根据通信间隔的不同可以分成最终进行模型交换平均，中间多步以应对非凸问题

2019-02-20 23:06:37 回应

第180页

MA往往比较稳定，所以调高学习率。

在单机模型做SGD更新的时候，常常会加入冲量以有效地利用历史更新信息来减小随机梯度下降中的梯度噪音的影响。那么类似的，我们也可以考虑在MA中对每次全局变量的更新采用冲量的该概念。Block-wise Model Update Filtering，使得历史上小批量迭代对全局模型更新的影响有一定的延续性，也能够达到加速模型优化进程的作用。

2019-02-20 23:55:00 回应

第181页

ADMM引入一个辅助变量z来控制各个工作节点上模型的差异，使他们都比较接近。

每次计算复杂，实际收敛速度并不快，但是通信代价小，并行效率很高。

MA与ADMM，前者没有全局一致的拉格朗日正则项，因此，从本地优化的角度来看MA更加直接，计算量也更小泛化能力来看ADMM中的正则项使得模型聚合之后不容易出现过拟合。

2019-02-21 00:17:58 回应

第2章：

第3章：

2017

Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling

https://arxiv.org/pdf/1709.10432.pdf

引用次数

	总计	2014 年至今
引用	472	472
h 指数	6	6
i10 指数	4	4

240

120

180

2016201720182019

关注

Qi Meng

Microsoft Research Asia

在 microsoft.com 的电子邮件经过验证


标题	引用次数	年份
Lightgbm: A highly efficient gradient boosting decision tree G Ke, Q Meng, T Finley, T Wang, W Chen, W Ma, Q Ye, TY Liu Advances in Neural Information Processing Systems, 3146-3154	350	2017
Asynchronous stochastic gradient descent with delay compensation S Zheng, Q Meng, T Wang, W Chen, N Yu, ZM Ma, TY Liu Proceedings of the 34th International Conference on Machine Learning-Volume …	52	2017
A communication-efficient parallel algorithm for decision tree Q Meng, G Ke, T Wang, W Chen, Q Ye, ZM Ma, TY Liu Advances in Neural Information Processing Systems, 1279-1287	28	2016
Asynchronous stochastic proximal optimization algorithms with variance reduction Q Meng, W Chen, J Yu, T Wang, ZM Ma, TY Liu Thirty-First AAAI Conference on Artificial Intelligence	11	2017
Asynchronous Accelerated Stochastic Gradient Descent. Q Meng, W Chen, J Yu, T Wang, Z Ma, TY Liu IJCAI, 1853-1859	8	2016
Convergence analysis of distributed stochastic gradient descent with shuffling Q Meng, W Chen, Y Wang, ZM Ma, TY Liu arXiv preprint arXiv:1709.10432	7	2017
Convergence analysis of distributed stochastic gradient descent with shuffling Q Meng, W Chen, Y Wang, ZM Ma, TY Liu Neurocomputing 337, 46-57	4	2019
Capacity control of relu neural networks by basis-path norm S Zheng, Q Meng, H Zhang, W Chen, N Yu, TY Liu Proceedings of the AAAI Conference on Artificial Intelligence 33, 5925-5932	3	2019
Target transfer q-learning and its convergence analysis Y Wang, Q Meng, W Cheng, Y Liug, ZM Ma, TY Liu arXiv preprint arXiv:1809.08923	2	2018
Differential equations for modeling asynchronous algorithms L He, Q Meng, W Chen, ZM Ma, TY Liu arXiv preprint arXiv:1805.02991	2	2018
-SGD: Optimizing ReLU Neural Networks in its Positively Scale-Invariant Space Q Meng, S Zheng, H Zhang, W Chen, ZM Ma, TY Liu arXiv preprint arXiv:1802.03713	2	2018
Generalization error bounds for optimization algorithms via stability Q Meng, Y Wang, W Chen, T Wang, ZM Ma, TY Liu Thirty-First AAAI Conference on Artificial Intelligence	2	2017
Optimizing Neural Networks in the Equivalent Class Space. Q Meng, W Chen, S Zheng, Q Ye, TY Liu arXiv preprint arXiv:1802.03713	1	2018
Reinforcement Learning with Dynamic Boltzmann Softmax Updates L Pan, Q Cai, Q Meng, L Huang, TY Liu arXiv preprint arXiv:1903.05926		2019