The original article is in Chinese. The English version is automatically translated by AI.

0x00 Preface

In the post on distributed convergence1, I was counting updates. Then I got stuck on a more practical question. Two methods might need the same number of steps, but one waits for the slowest worker while the other moves as soon as a gradient arrives. A step count alone leaves me wondering how long I’ll actually wait. That’s what I’d like to work out here. Which one reaches the same error first?

Two numbers are easy to mix up here. I use $t$ for the update count and $T$ for elapsed time. There are $m$ workers, each with batch size $b$, and $K$ is the number of workers or batches collected for an update. I still use $L$ for smoothness and $\mu$ for strong convexity. For the exponential rate of the service time, I’ll use $\lambda$.

0x01 Service-time Model

Start by watching one worker. Call the time from getting a batch to returning its gradient $X_i$. To get a model we can calculate with, assume these times are independent and identically distributed across workers and tasks, and independent of the samples and gradient noise. In a real run the server also averages results, broadcasts the model, and sometimes cancels work already in progress. Those costs need their own measurements.

Distributions

Here are a few models to try. Use $p_X(x)$ for the density and $F_X(x)=\Pr(X\le x)$ for the chance the work is already finished by a given time.

  • Exponential distribution: $p_X(x)=\lambda e^{-\lambda x}$, $F_X(x)=1-e^{-\lambda x}$, $x\ge0$, $\lambda>0$.
  • Shifted exponential distribution: $X=\Delta+E$, $E\sim\operatorname{Exp}(\lambda)$, $\Delta\ge0$, therefore $\mathbb E[X]=\Delta+1/\lambda$.
  • Pareto distribution: When $x\ge x_m>0$, $p_X(x)=\alpha x_m^\alpha/x^{\alpha+1}$, $F_X(x)=1-(x_m/x)^\alpha$; when $x<x_m$, both are zero.

With Pareto it’s the tail that can get you when you try to take an average. At $\alpha>1$ the mean is $\alpha x_m/(\alpha-1)$, and at $0<\alpha\le1$ it diverges. A finite variance requires $\alpha>2$, giving $\alpha x_m^2/((\alpha-1)^2(\alpha-2))$. In the range $1<\alpha\le2$ the mean still exists and the variance is infinite. I’d check this before using any later expression that needs a finite mean.

One small wrinkle with fitting an ordinary Gaussian to timings is the bit below zero. If that’s the approximation we use, check how much probability lands there or use a truncated distribution. The harmonic-number formulas below are worked out for exponential service times and the stated shifted exponential cases.

Order Statistics

Picture watching the server log as the $m$ workers return. Sort the times as $X_{1:m}\le\cdots\le X_{m:m}$, and $X_{K:m}$ is when the K-th result arrives. If we picked K particular workers in advance and waited for them all, we’d be taking the maximum of a different group.

Write the harmonic number as $H_n=\sum_{r=1}^n1/r$, with $H_0=0$ for the empty sum. There are $m$ independent exponential times. After the first worker finishes, one fewer remains, so the expected wait for the next result changes. Write those intervals as $1/(m\lambda),1/((m-1)\lambda),\ldots$ and add them up to the K-th completion.

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

Here’s one shortcut. If everyone first spends the same fixed time $\Delta$, the order of arrivals stays the same. Add $\Delta$ to the wait for K completions.

0x02 Synchronous SGD

Time per Update

Let’s count the straightforward synchronous round first. Set aside the early results, then call the round done when the last worker finishes.

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

It’s tempting to approximate the harmonic number right away. The fuller expression is $H_m=\log m+\gamma_{\rm E}+O(1/m)$, with Euler’s constant $\gamma_{\rm E}$. For many workers the leading term is $\log m$. With $m=1$, we’re counting one worker, so use $H_1=1$.

Put the rounds end to end. Finishing a fixed t updates takes $W_t=\sum_{j=0}^{t-1}S_j$, so the mean time per round we just found gives the expected total.

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

We can also look at it the other way around. For independent, identically distributed round times of finite mean, the count $N(T)$ satisfies $N(T)/T\to1/s_m$ almost surely as the observation window grows. Include the batches per round and the long-run throughput is $m/s_m$. If you only watch the log for a short window, its finite-time throughput takes a separate calculation.

Expected Time to Complete Enough Updates

Assume the target is $L$-smooth and $\mu$-strongly convex, with gradients satisfying the unbiased and independent noise conditions. With a fixed step size $0<\eta\le1/L$, let

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

Knowing the average round time leaves us with the number of rounds. The previous post gives $\mathcal E_t\le C_m+q^t(\mathcal E_0-C_m)$. With $0<q<1$ and a target satisfying $\mathcal E_0>\epsilon>C_m$, we can work out the update count below.

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

At this point I fix the number of steps. After those t updates the expected objective gap is within $\epsilon$, and finishing them takes $s_m t_\epsilon$ in expectation. If you’re asking when one actual training run first hits the threshold, that calls for looking at the whole random trajectory.

For a target with $\epsilon\le C_m$, I’d go back and see how to lower the plateau of the bound first. If the starting point already meets the target, stop there. With $q=0$, read the one-step recursion directly.

Choosing a Step Size for a Target Accuracy

If we get to choose the step size, work backward from the target. Assume $\sigma^2>0$ and $\mathcal E_0>\epsilon>0$. The following choice leaves half the error allowance for the plateau.

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

This gives $C_m\le\epsilon/2$. The other half is for the power that shrinks along the way. Use $q^t\le e^{-\eta\mu t}$ to count how many steps we need.

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

That suffices. Multiply the update count by the mean round time. You can still see the deterministic, noise, and logarithmic terms in the expression, and check which one sets the time scale.

$$ \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]. $$

So where do extra workers actually save iterations? The approximate $1/(m\epsilon)$ scaling shows up when the noise term dominates, ignoring fixed constants and keeping the logarithmic dependence. Once the step size hits its cap, the count stops scaling indefinitely as $1/m$, and we still wait for the slowest worker. With $\sigma^2=0$, go straight to the deterministic strongly convex GD complexity.

Error at a Fixed Wall-clock Time

Sometimes I’m given a time limit and asked how far the error can come down. I keep in mind that $N(T)$ is random and $T/s_m$ describes its long-run scale. With timing independent of gradient sampling, we can first condition on the number of steps we actually got, $N(T)$.

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

The tempting shortcut here is to write $q^{\mathbb E[N(T)]}$ for $\mathbb E[q^{N(T)}]$. Look at the exponential for $0<q<1$ and Jensen puts the power of the mean below the mean of the powers. With $\mathcal E_0>C_m$, that shortcut underestimates the error bound.

Try checking with one worker. At $m=1,\Delta=0$, $N(T)$ is Poisson with parameter $\lambda T$ and we can calculate $\mathbb E[q^{N(T)}]=\exp(\lambda T(q-1))$. Put it beside $q^{\lambda T}$ to see the difference. For a quick look at the trend I’d write $N(T)\approx T/s_m$ and label it as an approximation.

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

K-Sync

If waiting for the last worker feels expensive, try taking the fastest K workers. Everyone starts at the same parameter. Update when those results arrive and cancel the remaining tasks. With shifted exponential times, the order statistics from above apply.

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

A quick check is to plug in both ends. At $K=1$, we wait $\Delta+1/(m\lambda)$ for the first worker. At $K=m$, we’re waiting for the full synchronous round again. If you’re using $\lambda^{-1}\log(m/(m-K))$ as a shortcut, go back to the exact harmonic numbers at $K=m$ and near that boundary.

There’s more to check than which machines are quick. If the selected gradients are still conditionally unbiased with independent noise, use $C_K=\eta L\sigma^2/(2\mu bK)$ in the error bound. Set the target error first and work out $s_Kt_{\epsilon,K}$. The quantity $s_K$ is just the time for one round. A smaller K cuts the wait and makes the noise term larger. If some samples finish especially fast or workers have different data, check for bias after selection.

K-Batch-Sync

We can collect the work another way. A fast worker returns a batch and starts another at the same parameter. Once we have K independent batches in total, update and stop the old tasks that are still running.

Under shifted exponential service times, immediate restart, and zero cancellation overhead, m independent Poisson completion processes superimpose; each round waits for K completion events, hence

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

Here K counts batches, so it can exceed m. If restarting adds a fixed wait or the service distribution changes, check again whether the completions in a round form a Poisson process.

0x04 Asynchronous SGD and Renewal Theory

In the asynchronous case the server updates with each arrival. The worker that just finished reads the current parameter and starts another batch. For now assume the server and network keep up. Queuing and transfer bottlenecks are things to measure in a real system.

Let worker i’s consecutive service times $X_{i,1},X_{i,2},\ldots$ be independent and identically distributed, strictly positive, and $0<\mathbb E[X]<\infty$. Let

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

Picture an ongoing completion counter for each worker. The strong law gives $A_i(T)/T\to1/\mathbb E[X]$ almost surely for a long enough run. The elementary renewal theorem gives $\mathbb E[A_i(T)]/T\to1/\mathbb E[X]$ when we average the counts across runs.

The long-term total update rate for all workers is $m/\mathbb E[X]$, so the long-term average time per update is

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

Compare startup with a system that’s already been running. If every task takes exactly one time unit, the first result still takes one unit to arrive. Afterward several can arrive together. That helps explain why the long-run average and the wait in the first round are separate quantities.

Comparing Sync and Async

Start the comparison with unshifted exponentials. For the next asynchronous result, the wait is $\operatorname{Exp}(m\lambda)$, with mean $1/(m\lambda)$. Synchronization waits for the batch, with mean $H_m/\lambda$. Dividing those gives $mH_m$.

Under the shifted exponential model, comparing the long-term asynchronous average with the synchronous single-round mean yields

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

That ratio makes asynchronous updates look quick. Count the work once more, though. The asynchronous update uses one batch and may use an old gradient, and the synchronous update uses m batches. To see when they reach the same error, bring back the conditional-noise and relative-staleness assumptions from Part 41.

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

K-Async

When an update waits for K workers, think about who’s still busy at the end of that round. The workers that returned results wait for the update and then read the new parameter. The others keep going. At the next round we’re looking at how much work those jobs have left.

Independent, identical unshifted exponential times give us a shortcut. How long the task has already run doesn’t alter the distribution of the time left. Those remaining times are still independent exponentials, so we can calculate the next round’s mean.

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

With another distribution I’d first ask how the remaining time of a job in progress compares with a fresh job. The new-longer-than-used condition expresses that comparison. Assume the following for every nonnegative a and u whenever the conditioning event has positive probability.

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

Under this condition the remaining time is stochastically no longer than the time for a fresh task, giving $\mathbb E[S_{K\text{-async}}]\le\mathbb E[X_{K:m}]$. Shifted exponentials satisfy it, with $\Delta+(H_m-H_{m-K})/\lambda$ on the right. Read that as an upper bound. If we change distributions again, work out that distribution’s own order statistics.

K-Batch-Async

For the last variant, just count how many batches arrive. A worker reads the current parameter when it finishes and keeps going. The server updates at K results. One worker can return several, and jobs still in progress keep running.

In the ideal unshifted exponential model, the mean wait for K completions is $K/(m\lambda)$. For general finite-mean service times, renewal theory gives $K\mathbb E[X]/m$ averaged over a long run per server update. For just a few rounds, their individual expected waits still take a separate calculation.

Back to where we started. Once I have the waits for K-Async and K-batch-async, I still need to ask how old their gradients are and whether the noise assumptions hold. Check conditional unbiasedness, correlations, and staleness for each method before comparing how long they take to reach the same error.

0x06 Reference

Looking back, these are the three numbers I find easiest to mix up. Time to finish a set of updates, error after a time budget, and the long-run number of batches per second. I keep them labeled in my notes. When I get to a plot of efficiency, I first check which one it’s showing.

Sources: 2 3 4 5.


  1. Distributed Convergence Analysis  ↩︎ ↩︎

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