分布式机器学习笔记

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

数据与模型并行

数据并行
- 数据样本切分方式
  - 随机采样（有放回）
    - 优点：满足局部数据与原始数据是独立同分布
    - 缺点：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相同的收敛速率
非凸问题中，异步延迟引入的额外随机性可能帮我们探索更多更好的局部最优点，缓解训练中的过拟合问题
分析异步更新的迭代公式，可以把异步更新理解为冲量的作用，这个角度也说明异步更新机器数量不能太多

reference

《分布式机器学习：算法、理论与实践》

联系我: personal email address