0x00 Preface

写分布式收敛性分析1的时候,我手里数的是更新次数。再想一步就有点犯难了。假如两种做法都说走这么多步,一种每次得等最慢的那台,另一种收到梯度就能先走,光知道步数,还是算不出要等多久。所以这次想接着算个更实际的问题,跑到同一个误差,哪边先结束?

这篇有两个数容易看混,我用 $t$ 数更新次数,$T$ 记钟表上过了多久。$m$ 是 worker 数,每台的 batch 大小叫 $b$,一次收进来的 worker 数或 batch 数叫 $K$。函数还是用 $L$ 记光滑常数,$\mu$ 记强凸常数。说到耗时的指数率,我另用 $\lambda$。

0x01 Service-time Model

先把一台机器的这趟活看清楚。从拿到 batch 到把梯度交回来,用掉的时间叫 $X_i$。为了能先算出点东西,假设每台每次的耗时独立同分布,也和这一批样本及梯度噪声无关。真跑的时候,服务器还得平均、发新模型,有时还要取消已经在跑的任务,这几笔要另外计时。

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}$ 就是看见第 K 份结果时的时间。要是事先圈了 K 台指定机器再等它们做完,算的就是另外一组最大值。

用 $H_n=\sum_{r=1}^n1/r$ 记调和数,空的那一项设 $H_0=0$。这 $m$ 台用的是独立指数耗时。第一台做完以后,还剩的机器少一台,等下一份的期望间隔就跟着变。把这些间隔写成 $1/(m\lambda),1/((m-1)\lambda),\ldots$,再加到第 K 次完成为止。

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

这里还有个省事的地方。大家都要先花同样的固定时间 $\Delta$,交回来的先后顺序照旧,等到第 K 名的时间只要再加 $\Delta$。

0x02 Synchronous SGD

Time per Update

先算最老实的同步做法。前面交回来的都先放着,到了最后一台完成,这一轮才算结束。

$$ 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=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$。如果你问的是一条实际训练曲线第一次碰到阈值在什么时候,那得看整条随机轨迹。

要是目标已经到了 $\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)$ 的迭代缩放。步长加到上限以后,机器再加,步数就不会一直按 $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 台是怎么回事。大家从同一个参数出发,收够结果就更新,其余任务取消。给每台配一个偏移指数耗时,就能接着用前面的顺序统计量。

$$ 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$ 或快到边界的地方还是翻回精确的调和数看看。

这里有一处不能只盯着机器快不快。选完后那批梯度若还是条件无偏、噪声独立,误差界用 $C_K=\eta L\sigma^2/(2\mu bK)$。把目标误差先定好,再一起算 $s_Kt_{\epsilon,K}$。$s_K$ 只是其中一轮的时间。K 小一点,这一轮等得少了,界里的噪声项也大了。如果哪类样本特别快,或者各台数据本来就不一样,得先看看选完的结果有没有偏。

K-Batch-Sync

接下来可以换个收法。算得快的一台交了一份,还能在同一个参数上接着算另一批。等所有人加起来交了 K 个独立 batch,就更新,把还没做完的旧任务停掉。

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

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

所以这个 K 数的是 batch,比 m 大也行。要是每次重启还得先等一段固定时间,或者耗时换了别的分布,就要重新算这一轮里有没有泊松完成过程。

0x04 Asynchronous SGD and Renewal Theory

异步的做法是,服务器收到一份就更一次,刚交完的 worker 立即读最新参数,接着算下一份。下面先按服务器和传输都跟得上的设定来算,把排队和传输瓶颈留到测量实际系统时看。

设 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}. $$

看到这个比值我也会先觉得异步挺快。不过再数一眼,异步这一次只收一个 batch,同步收了 m 个,异步还有可能用旧点上的梯度。想问同一个误差什么时候到,还要把 Part 41 的条件噪声假设和相对滞后界带回去一起算。

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

K-Async

收够 K 台才更一次时,想一下上一轮还有谁在忙。已经交回来的等服务器更新再读新参数,没交的继续刚才那份活。到了下一轮,这些任务已经做过一段了,我们要算的是它们还剩多久。

遇到无偏移的独立同质指数耗时,这一步挺省事。前面已经做了多久,对剩余时间的分布没影响。它们仍是独立指数变量,下面这一轮的均值就能继续算。

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

换个分布以后,我会先问做了一半的任务和全新任务比,剩下的时间怎么变。可以用 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

最后这个做法只数收到几份 batch。worker 一算完就读当前参数继续做,收够 K 份服务器就更新。同一台可以交好几份,没算完的也让它继续。

在理想的无偏移指数模型里,等足 K 次完成的均值是 $K/(m\lambda)$。换成一般的有限均值服务时间,就得从更新理论看长跑下来摊到每次服务器更新的时间 $K\mathbb E[X]/m$。如果你手头只数了几轮,那几轮各自的期望还要另算。

回到开头的问题,我现在拿到 K-Async 和 K-batch-async 各自的一轮时间,还得问它们收回来的梯度有多旧、噪声条件还成不成立。把条件无偏、相关性和滞后界各自对上,才能在同一个目标误差下比较谁先跑完。

0x06 Reference

写完回头看,我自己最容易混的是三种数。定好步数要等多久,定好时间还能把误差压到哪里,和跑久了每秒能交多少 batch。我会把它们各自记在旁边,日后画效率的图,先看图上到底画的是哪一个。

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. ↩︎