biscuitの博客

性能这一块-单次迭代时间#

同步 SGD 要等所有 worker 都算完。

所以，一次迭代的时间 = 最慢的那个 worker 的计算时间。

假设每一个worker计算梯度的时间是一个随机变量 $X$

一次迭代的时间 = $T = \max(X_1, X_2, ..., X_m)$，太长了，用 顺序统计量 的知识表示：$T = E[X_{m:m}]$

• 随着 worker 数量 $m$ 的增加，迭代时间会增加。
• X 的变异性越高，迭代时间越长。

特别地，如果 $X$ 是指数分布，$E[X_{m:m}] = \frac{H_m}{\lambda}\approx \frac{\log m}{\mu}$，其中 $H_m$ 是第 $m$ 个调和数。所以迭代时间随着 worker 数量的增加而增加，且增长速度接近对数级别。

性能这一块-收敛性#

当工作节点m增多时，收敛性更佳

优化：K-同步SGD#

思想：不等所有woker,收集到前K个worker的梯度就更新参数

等价于全局batch size = Kb 的mini-batch SGD

迭代时间：$T_{K-sync} = E[X_{K:m}]\sim\frac{1}{\mu}\log\frac{m}{m-K}$，比同步SGD的迭代时间更短。

误差：当K减小时，有效小批量尺寸Kb随之缩小，导致更高的误差下限

优化：K-批次同步SGD#

更激进：快的worker不闲着，可以在同一模型版本上连续计算多个梯度，直到凑齐K个梯度（可来自同一个worker的多次计算）。

仍然等价于 batch size = Kb 的mini-batch SGD

迭代时间：$T_{K-batch} = \frac{K}{m\mu}$，迭代时间更短了。并且m增大时迭代时间会更短了。

TIP

关于T的推导：根据指数分布无记忆性，参数服务器接收相邻两个梯度的时间间隔也是指数分布的，平均时间为 $\frac{1}{m\mu}$，所以收到K个梯度的平均时间为 $T_{K-batch} = \frac{K}{m\mu}$.

收敛性和误差：与K-同步SGD相同，K-批次同步SGD的误差下限也随着K的减小而增加。