0x00 Preface

本文着眼于分布式机器学习中的效率分析，在分布式机器学习中，efficiency 通常指的是效率，即在一定的时间内，算法能够达到的最优解的质量，或者是需要得到一定的质量时，算法所需要的时间，参考1。

0x01 Synchronous SGD

Gradient Computation and Communication Time

通常，我们会假设梯度计算和通信的时间服从一个关于随机变量 $X$ 的概率分布，即 $F_{X}(x)$，这个分布往往取决于计算机的性能、网络的带宽、所用的通信协议等等。常见的分布有：

  • 指数分布：$F_{X}(x) = \text{Exp}(\lambda) = \lambda e^{-\lambda x}, x \geq 0, \lambda > 0$
  • 高斯分布：$F_{X}(x) = \text{N}(\mu, \sigma^2) = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}, x \in \mathbb{R}, \mu \in \mathbb{R}, \sigma > 0$
  • 帕累托（Pareto）分布：
$$ F_{X}(x) = \text{Pareto}(x_{m}, \alpha) = \begin{cases} \frac{\alpha x_{m}^{\alpha}}{x^{\alpha +1}}, & x \geq x_{m} \\ 0, & x < x_{m} \end{cases}, x_{m} > 0, \alpha > 0 $$

其中，$x_{m}$ 和 $\alpha$ 分别是范围和形状参数，越大的 $\alpha$ 表示越快的衰减。帕累托随机变量的均值和方差分别为：

$$ \mathbb{E}[X] = \begin{cases} \infty, & \alpha \leq 1 \\ \frac{\alpha x_{m}}{\alpha - 1}, & \alpha > 1 \end{cases} \\ \mathrm{Var}[X] = \begin{cases} \infty, & \alpha \leq 2 \\ \frac{\alpha x_{m}^2}{(\alpha - 1)^2 (\alpha - 2)}, & \alpha > 2 \end{cases} $$

tip

帕累托分布是从真实世界现象中发现的幂次定律分布，除了用于 cloud server delay 之外，还常用于硬件的错误和失败率、在线文件大小、社会财富分布（意大利20%人口拥有80%的财产）等等。

在这些分布假设下，实际的梯度计算和通信时间是偏移的（shifted），即 $\Delta + \text{Exp}(\lambda)$，其中 $\Delta$ 是一个常数时间，如通信和本地计算的开销。

同时，通常我们会假设 $X$ 是独立同分布的（i.i.d.），即在每个 worker node 上的梯度计算和通信时间服从同一个分布。

有了上面的假设，我们就可以开始着手分析了。

Efficiency/Runtime Analysis

假设一轮的迭代时间为 $T_{\text{sync}}$，共有 $m$ 个 worker node。

那么

$$ \mathbb{E}[T_{\text{sync}}] = \mathbb{E}[\max \{X_{1}, X_{2}, \cdots, X_{m}\}] = \mathbb{E}[X_{m:m}] $$

其中，$X_{m:m}$ 表示 $m$ 个随机变量中的最大值，因为根据木桶原理，我们应该关注最慢的那个 worker node。

当 $X$ 服从指数分布时，即 $X \sim \Delta + \text{Exp}(\lambda)$，我们有

$$ \mathbb{E}[X]=\frac{1}{\lambda}+\Delta \\ \mathbb{E}[T_{\text{sync}}] = \mathbb{E}[X_{m:m}] = \Delta + \frac{H_{m}}{\lambda} \approx \Delta + \frac{\ln m}{\lambda} $$

其中，$H_{m} = \sum_{i=1}^{m} \frac{1}{i}$ 是第 $m$ 个调和数。

因此，我们可以认为，分布式机器学习中，使用同步 SGD 单位时间处理 minibatches 的期望是 $\frac{m}{\mathbb{E}[T_{\text{sync}}]}$。

为了防止和迭代次数 $t$ 混淆，我们用 $T_{\text{wall}}$ 表示 wall-clock time，即 $T$ 个单位时间。在 $T_{\text{wall}}$ 时间内，同步 SGD 进行的迭次数 $t$，随机变量 $X\sim \text{Exp}(\lambda)$，我们有

$$ \lim_{T_{\text{wall}} \rightarrow \infty} \frac{t}{T_{\text{wall}}} = \frac{1}{\mathbb{E}[T_{\text{sync}}]} \approx \frac{\lambda}{\ln m} $$

于是，有 $t \approx \frac{\lambda T_{\text{wall}}}{\ln m}$。

同样的，如果我们限制的是迭代次数 $t$，那么 wall-clock time 为 $T_{\text{wall}}\approx \frac{t\ln m}{\lambda}$。

从 分布式机器学习中的收敛性分析 中我们知道，这个误差，代入 $t$ 得到

$$ \mathbb{E}[f(w_{T})] - f(w^{*}) - \frac{\eta L \sigma^{2}}{2\mu bm} \leq (1- \eta \mu)^{\frac{\lambda T_{\text{wall}}}{\ln m}}\left (\mathbb{E}[f(w_{0})] - f(w^{*}) - \frac{\eta L \sigma^{2}}{2\mu bm} \right ) $$

从上式可以看出存在一个关于 $m$ 的实际运行时间和误差的 trade-off，$m$ 越大，每轮迭代的期望运行时间变大了，但是实现了更小的误差。实现误差 $\epsilon$ 所需要的 wallclock time 是 $O(\frac{\ln m}{\lambda \epsilon m})$，同时迭代次数 $t$ 是 $O(\frac{1}{\epsilon m})$，每轮运行时间是 $O(\frac{\ln m}{\lambda})$。

0x02 K-Sync SGD

在 K-Sync SGD 中，PS 会首先接收前 K 的 worker node 的梯度，然后进行平均，同时取消掉剩余的 worker node 的计算，保证每次迭代的初始参数是相同的。

此时一轮迭代的期望时间为

$$ \begin{align} \mathbb{E}[T_{\text{k-sync}}] &= \mathbb{E}[\max \{X_{1}, X_{2}, \cdots, X_{k}\}] = \mathbb{E}[X_{k:m}] \\ &= \frac{1}{m\lambda} + \frac{1}{(m-1)\lambda} + \cdots + \frac{1}{(m-k+1)\lambda} \\ &= \frac{1}{\lambda} (H_{m} - H_{m-k}) \\ &\approx \frac{1}{\lambda} \ln(\frac{m}{m-k}) \end{align} $$

在经过 $t$ 次迭代后，误差被 bound 如下：

$$ \mathbb{E}[f(w_{t})] - f(w^{*}) - \frac{\eta L \sigma^{2}}{2\mu bK} \leq (1- \eta \mu)^{t}\left (\mathbb{E}[f(w_{0})] - f(w^{*}) - \frac{\eta L \sigma^{2}}{2\mu bK} \right ) $$

同样，这也存在一个 Trade-off，更小的 $K$ 能够让单轮迭代变快，但是误差会增加。

这里多说一个 K-batch-sync 的情况，这种情况下，一个 worker 上传完梯度后，并不是停止等待，而是继续计算，直到 PS 收到 K 个梯度为止。这种情况下，一轮迭代的期望时间为 $\mathbb{E}[T_{\text{k-batch-sync}}] = \frac{K}{m\lambda}$，随着 $m$ 增加而降低，随着 $K$ 增加而增加。

0x03 Asynchronous SGD

在异步的情况下，需要用到 Renewal Theorem2。

defination

Renewal Theorem：假设 $S_{1}, S_{2}, \cdots$ 是独立同分布的随机变量序列，并且期望是有界的 $0< \mathbb{E}[S_{i}] < \infty$。对于 $S_{i}$，我们指的是第 $i$ 个占用时间（$i$-th holding time）。同时定义 $J_{n} = \sum_{i=1}^{n} S_{i}$，即第 $n$ 个跳跃时间（$n$-th jump time），而 $[J_{n}, J_{n+1})$ 也叫做更新间隔（renewal interval）。那么，对于任意的 $t \geq 0$，我们有

$$ X_{t} = \sum_{n=1}^{\infty} \mathbb{I}_{{J_{n} \leq t}}=\text{sup} \{n: J_{n} \leq t\} $$

其中，$\mathbb{I}_{\{J_{n} \leq t\}}$ 表示 $J_{n} \leq t$ 的指示函数（成立时为1，其他情况为0）。$X_{t}$ 表示在 $t$ 时刻的跳跃次数，这个过程也叫做更新过程（renewal process）。

更新过程是泊松过程的推广。本质上，泊松过程是正整数（通常从零开始）的连续时间马尔可夫过程，每个整数具有独立的指数分布保持时间 $i$ 在前进到下一个整数之前，$i+1$。

每次迭代的期望运行时间 $\mathbb{E}[T_{\text{async}}] = \frac{\mathbb{E}[X]}{m}$，分析如下：

对于第 $i$ 个 worker，$A_{i}(t)$ 表示第 $i$ 个 worker 在 $t$ 时间内给 PS 发送的梯度个数，由更新理论的基本更新定理（Elementary renewal theorem）。

$$ \lim_{t \rightarrow \infty} \frac{A_{i}(t)}{t} = \frac{1}{\mathbb{E}[X]} $$

对于所有 worker 的梯度个数，我们有

$$ \lim_{t \rightarrow \infty} \frac{\sum_{i=1}^{m} A_{i}(t)}{t} = \frac{m}{\mathbb{E}[X]} $$

因此每轮的运行时间为 $\mathbb{E}[T_{\text{async}}] = \frac{\mathbb{E}[X]}{m}$。

相较于同步的情况，两者的比值 $\frac{\mathbb{E}[T_{\text{sync}}]}{\mathbb{E}[T_{\text{async}}]} \approx m\ln m$，因此，异步的情况下，每轮迭代的时间是同步的 $O(m\ln m)$ 倍。

0x04 K-Async SGD

在 K-Async SGD 中，每次迭代，PS 会接收前 K 个 worker 的梯度，然后进行平均。

此时，每轮迭代的期望时间为

$$ \mathbb{E}[T_{\text{k-async}}] = \mathbb{E}[X_{k:m}] = \frac{1}{\lambda} (H_{m} - H_{m-k}) \approx \frac{1}{\lambda} \ln(\frac{m}{m-k}) $$

如果 $X$ 服从 new-longer-than-used 分布，上式是 upper bound。

0x05 Reference

  1. 《Optimization Algorithms for Distributed Machine Learning》，Gauri Joshi ↩︎

  2. Wikipedia, https://en.wikipedia.org/wiki/Renewal_theory ↩︎