0x00 Preface

分布式优化的效率需要同时衡量迭代效果和真实耗时：完成一次更新有多快，与达到某个精度有多快，是两个问题。本篇结合 分布式收敛性分析1 的误差界，分析同步和异步 SGD 的时间模型。

符号约定：$m$ 为 worker 数，$b$ 为每个 worker 的 batch 大小，$K$ 为一次更新接收的 worker 或 batch 数，$t$ 为更新次数，$T$ 为 wall-clock time。$L$ 和 $\mu$ 分别为目标函数的光滑与强凸常数；服务时间的指数率使用 $\lambda$，不与强凸常数混用。

0x01 Service-time Model

令 $X_i$ 表示 worker 处理一个 batch 并传回梯度的耗时。为得到可计算的理论模型，假设服务时间在 worker 之间、不同任务之间独立同分布，且不依赖本次样本或梯度噪声。服务器聚合、广播和任务取消开销暂不另计；真实系统中需要测量这些开销，不能默认都包含在每个 worker 的独立时间中。

Distributions

密度函数记为 $p_X(x)$，累计分布函数为 $F_X(x)=\Pr(X\le x)$。

  • 指数分布：$p_X(x)=\lambda e^{-\lambda x}$，$F_X(x)=1-e^{-\lambda x}$，$x\ge0$，$\lambda>0$。
  • 偏移指数分布：$X=\Delta+E$，$E\sim\operatorname{Exp}(\lambda)$，$\Delta\ge0$，因此 $\mathbb E[X]=\Delta+1/\lambda$。
  • Pareto 分布：当 $x\ge x_m>0$ 时，$p_X(x)=\alpha x_m^\alpha/x^{\alpha+1}$，$F_X(x)=1-(x_m/x)^\alpha$；$x<x_m$ 时二者为零。

Pareto 的均值在 $\alpha>1$ 时为 $\alpha x_m/(\alpha-1)$，在 $0<\alpha\le1$ 时发散；方差在 $\alpha>2$ 时为 $\alpha x_m^2/((\alpha-1)^2(\alpha-2))$。当 $1<\alpha\le2$ 时方差无限；均值无限时，不将方差当作有限均值模型下的量使用。

普通高斯分布允许负值，不直接作为严格的耗时模型。如果用它近似测量值，需要说明负值概率或使用截断分布。下面的精确调和数公式只针对指数或特别注明的偏移指数模型，不适用于任意服务分布。

Order Statistics

将 $m$ 个耗时排序为 $X_{1:m}\le\cdots\le X_{m:m}$。$X_{K:m}$ 是所有 m 个时间中的第 K 小值，不是预先指定的 K 个 worker 的最大耗时。

记 $H_n=\sum_{r=1}^n1/r$，$H_0=0$。对于 $m$ 个独立指数变量，相邻顺序统计量的期望间隔分别为 $1/(m\lambda),1/((m-1)\lambda),\ldots$，所以

$$ \mathbb E[X_{K:m}]=\frac{H_m-H_{m-K}}{\lambda}. $$

若每个时间都加同一个确定偏移 $\Delta$，对应结果也加 $\Delta$。

0x02 Synchronous SGD

Time per Update

同步更新等待所有 worker，因此

$$ S_t=\max_{1\le i\le m}X_{i,t},\qquad s_m:=\mathbb E[S_t]=\Delta+\frac{H_m}{\lambda}. $$

$H_m=\log m+\gamma_{\rm E}+O(1/m)$，其中 $\gamma_{\rm E}$ 为欧拉常数。$\log m$ 仅是大 m 时的主导项；$m=1$ 时必须使用 $H_1=1$。

完成固定 t 次更新的总耗时 $W_t=\sum_{j=0}^{t-1}S_j$，故

$$ \mathbb E[W_t]=ts_m. $$

若每轮耗时独立同分布且均值有限，固定时间内完成的更新次数 $N(T)$ 满足 $N(T)/T\to1/s_m$（几乎必然）。长期 batch 吞吐量为 $m/s_m$。这不是有限时间内任意吞吐量随机变量的精确期望。

Expected Time to Complete Enough Updates

假设目标为 $L$-光滑、$\mu$-强凸，梯度满足条件无偏和独立噪声条件。固定步长 $0<\eta\le1/L$ 时，令

$$ \mathcal E_t=\mathbb E[f(w_t)]-f^*,\quad q=1-\eta\mu,\quad C_m=\frac{\eta L\sigma^2}{2\mu bm}. $$

有 $\mathcal E_t\le C_m+q^t(\mathcal E_0-C_m)$。若 $0<q<1$ 且 $\mathcal E_0>\epsilon>C_m$，定义

$$ t_\epsilon=\left\lceil \frac{\log((\mathcal E_0-C_m)/(\epsilon-C_m))}{-\log q} \right\rceil. $$

完成这 t 次更新后，期望函数值误差不超过 $\epsilon$，其期望耗时为 $s_m t_\epsilon$。这不是某条随机训练轨迹首次达到误差阈值的期望 hitting time。

如果 $\epsilon\le C_m$，当前界不能保证达到目标。若初始误差已满足目标，可以停止；$q=0$ 时使用单步递推，不计算对数。

Choosing a Step Size for a Target Accuracy

设 $\sigma^2>0$、$\mathcal E_0>\epsilon>0$。可以选择

$$ \eta=\min\left\{\frac1L,\frac{\mu bm\epsilon}{L\sigma^2}\right\}, $$

使 $C_m\le\epsilon/2$。利用 $q^t\le e^{-\eta\mu t}$，取

$$ t\ge\left\lceil\frac1{\eta\mu}\log\frac{2\mathcal E_0}{\epsilon}\right\rceil $$

足够达到目标。于是可给出保留确定性项、噪声项和对数项的运行时间上界：

$$ \mathbb E[W_t] =O\left[ \left(\Delta+\frac{H_m}{\lambda}\right) \left(1+\max\left\{\frac L\mu,\frac{L\sigma^2}{\mu^2bm\epsilon}\right\} \log\frac{2\mathcal E_0}{\epsilon}\right) \right]. $$

只有在噪声项主导、忽略其他固定常数并保留必要对数项的相应范围内，才出现近似 $1/(m\epsilon)$ 的迭代缩放。m 增加到步长上限起作用后，迭代数不再按 $1/m$ 无限降低；每轮等待成本仍然增加。$\sigma^2=0$ 时直接采用确定性强凸 GD 的复杂度。

Error at a Fixed Wall-clock Time

$N(T)$ 是随机变量，不能用 $T/s_m$ 替换它后，仍把公式写成严格上界。在运行时间过程与梯度采样独立的模型中，应当先条件于 $N(T)$：

$$ \mathbb E[f(w_{N(T)})]-f^* \le C_m+(\mathcal E_0-C_m)\mathbb E[q^{N(T)}]. $$

即使这些独立性成立，也不能将 $\mathbb E[q^{N(T)}]$ 直接换成 $q^{\mathbb E[N(T)]}$。对 $0<q<1$，后者由 Jensen 是前者的下界；当 $\mathcal E_0>C_m$ 时，该替换会低估当前误差上界。

例如 $m=1,\Delta=0$ 时，$N(T)$ 为参数 $\lambda T$ 的泊松变量，因此 $\mathbb E[q^{N(T)}]=\exp(\lambda T(q-1))$，一般不等于 $q^{\lambda T}$。$N(T)\approx T/s_m$ 可以用于说明趋势，但必须标为近似。

0x03 K-Sync and K-Batch-Sync SGD

K-Sync

每轮从同一个参数开始，接收最快 K 个不同 worker 的结果，取消其余任务。因此对偏移指数耗时，

$$ s_K:=\mathbb E[S_{K\text{-sync}}] =\Delta+\frac{H_m-H_{m-K}}{\lambda},\qquad1\le K\le m. $$

$K=1$ 时为 $\Delta+1/(m\lambda)$，$K=m$ 时恢复同步结果。对数近似 $\lambda^{-1}\log(m/(m-K))$ 不适用于 $K=m$，也应避免在边界附近替代精确调和数。

在入选 batch 仍条件无偏且噪声独立的模型下，误差界使用 $C_K=\eta L\sigma^2/(2\mu bK)$。给定同一目标误差，比较 $s_Kt_{\epsilon,K}$，而不是只比较 $s_K$。选择更小 K 可以减小等待时间，但会增加界中的噪声项。若快慢与样本或局部数据分布相关，必须先处理选择偏差。

K-Batch-Sync

所有 worker 在当前参数上计算；一个 worker 完成后继续计算下一个独立 batch，直到总共收到 K 个 batch 后更新并取消尚未完成的旧任务。

在无偏移指数服务时间、即时重启和零取消开销下，m 个独立泊松完成过程叠加，每轮等待 K 次完成事件，故

$$ \mathbb E[S_{K\text{-batch-sync}}]=\frac K{m\lambda}. $$

这里 K 是 batch 数，不必小于 m。带偏移或一般服务时间下，该轮内的完成过程通常不是泊松过程，不能原样使用此公式。

0x04 Asynchronous SGD and Renewal Theory

单梯度异步 SGD 中，worker 完成后立即上传、读取当前参数并开始下一个 batch；服务器每收到一个梯度就更新一次。这里暂不考虑服务器排队和模型传输瓶颈。

设 worker i 的连续服务时间 $X_{i,1},X_{i,2},\ldots$ 独立同分布、严格为正，且 $0<\mathbb E[X]<\infty$。令

$$ J_{i,n}=\sum_{r=1}^nX_{i,r},\qquad A_i(T)=\max\{n\ge0:J_{i,n}\le T\},\qquad J_{i,0}=0. $$

这定义了更新过程。由强大数定律得到的更新计数极限为 $A_i(T)/T\to1/\mathbb E[X]$（几乎必然）；基本更新定理则给出期望版本 $\mathbb E[A_i(T)]/T\to1/\mathbb E[X]$。两者应区分。

所有 worker 的长期总更新速率为 $m/\mathbb E[X]$，因此长期平均每次更新的耗时为

$$ \bar s_{\rm async}=\frac{\mathbb E[X]}m. $$

它不保证从初始化开始每次更新的期望等待时间都相同。例如所有服务时间固定为 1，第一次完成事件仍然等待 1；之后可能出现同时到达的事件。

Comparing Sync and Async

无偏移指数时间下，单梯度异步更新的等待时间为 $\operatorname{Exp}(m\lambda)$，因此均值为 $1/(m\lambda)$。同步每轮均值为 $H_m/\lambda$，比值为 $mH_m$。

偏移指数模型下，用长期异步平均与同步单轮均值比较，得到

$$ \frac{s_m}{\bar s_{\rm async}} =m\frac{\lambda\Delta+H_m}{\lambda\Delta+1}. $$

异步单次更新更快，但同步一次使用 m 个 batch、异步一次使用一个 batch，而且异步有滞后梯度。这个时间比不是达到相同精度的训练加速比。异步误差界还依赖 Part 41 的相对滞后和条件噪声假设。

0x05 K-Async and K-Batch-Async SGD

K-Async

K-Async 每次接收 K 个不同 worker 的结果。已经在本轮交回结果的 worker 等待本次服务器更新后再读取新参数；未完成者继续旧计算，因而下一轮开始时的剩余服务时间通常不同于全新服务时间。

在独立、同质、无偏移指数服务时间下，无记忆性使剩余时间仍是独立指数变量，因此每轮均值为

$$ \mathbb E[S_{K\text{-async}}]=\frac{H_m-H_{m-K}}\lambda,\qquad1\le K\le m. $$

一般分布不能使用这个等式。若 X 满足 new-longer-than-used 条件，即对所有非负 a,u（在条件事件概率非零时）有

$$ \Pr(X>a+u\mid X>a)\le\Pr(X>u), $$

则已运行任务的剩余时间随机小于等于全新时间，可得到 $\mathbb E[S_{K\text{-async}}]\le\mathbb E[X_{K:m}]$。例如偏移指数分布满足此条件，右侧为 $\Delta+(H_m-H_{m-K})/\lambda$，但一般没有等号。任意其他分布仍需计算其自己的顺序统计量，而不是使用指数调和数公式。

K-Batch-Async

这个变体在服务器每收到 K 个 batch 后更新；worker 每完成一个 batch 就读取当前参数并继续工作，不要求贡献者是 K 个不同 worker，也不取消尚未完成的 batch。

理想的无偏移指数模型下，等待 K 次总完成事件的均值为 $K/(m\lambda)$。对一般有限均值服务时间，更新理论给出的是长期每次服务器更新的平均耗时 $K\mathbb E[X]/m$，不是任意有限轮次的精确期望等式。

K-Async 与 K-batch-async 有不同的等待和滞后机制。比较二者时，应同时验证各自的条件无偏、噪声相关性和滞后界，再比较达到相同目标精度的时间。

0x06 Reference

本文将固定更新次数的期望完成时间、固定时间内的期望误差和长期吞吐量分别处理，避免把渐近或均值近似当作有限时间的严格保证。

Sources: 2 3 4 5.

  1. 分布式收敛性分析 ↩︎ ↩︎

  2. Dutta, S., Joshi, G., Ghosh, S., Dube, P. and Nagpurkar, P., Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD, AISTATS 2018, Section 4 and Supplement, Section 7. ↩︎

  3. Dutta, S., Joshi, G., Ghosh, S., Dube, P. and Nagpurkar, P., Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD, AISTATS 2018, Section 4 and Supplement, Section 7. ↩︎

  4. Joshi, G., Optimization Algorithms for Distributed Machine Learning, Springer. ↩︎

  5. Gallager, R. G., Discrete Stochastic Processes, Chapter 4: Renewal Processes. ↩︎