Efficiency Analysis in Distributed Machine Learning

0x00 Preface

The efficiency of distributed optimization requires measuring both iteration effectiveness and real-world elapsed time: how fast a single update completes, and how fast a certain accuracy is reached, are two distinct questions. This article combines the error bounds from Distributed Convergence Analysis ¹ to analyze the time models for synchronous and asynchronous SGD.

Notation: $m$ denotes the number of workers, $b$ the batch size per worker, $K$ the number of workers or batches received per update, $t$ the number of updates, and $T$ the wall-clock time. $L$ and $\mu$ are the smoothness and strong convexity constants of the objective function, respectively; the exponential rate of service time is denoted by $\lambda$ and should not be confused with the strong convexity constant.

0x01 Service-time Model

Let $X_i$ represent the time required for a worker to process a batch and return the gradient. To obtain a computable theoretical model, we assume service times are independent and identically distributed (i.i.d.) across workers and different tasks, and do not depend on the current sample or gradient noise. Server aggregation, broadcasting, and task cancellation overheads are not separately accounted for here; in real systems, these overheads must be measured and cannot be assumed to be included in each worker’s independent time.

Distributions

The probability density function is denoted by $p_X(x)$, and the cumulative distribution function by $F_X(x)=\Pr(X\le x)$.

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

The mean of the Pareto distribution is $\alpha x_m/(\alpha-1)$ when $\alpha>1$, and diverges when $0<\alpha\le1$; the variance is $\alpha x_m^2/((\alpha-1)^2(\alpha-2))$ when $\alpha>2$. When $1<\alpha\le2$, the variance is infinite; when the mean is infinite, the variance is not treated as a quantity under a finite mean model.

The standard Gaussian distribution allows negative values and cannot directly serve as a strict runtime model. If used to approximate measured values, one must specify the probability of negative values or use a truncated distribution. The exact harmonic number formulas below apply only to exponential or specifically noted shifted exponential models, not to arbitrary service distributions.

Order Statistics

Sort the $m$ runtimes as $X_{1:m}\le\cdots\le X_{m:m}$. $X_{K:m}$ is the K-th smallest value among all m times, not the maximum time of a pre-specified set of K workers.

Let $H_n=\sum_{r=1}^n1/r$, $H_0=0$. For $m$ independent exponential variables, the expected intervals between adjacent order statistics are $1/(m\lambda),1/((m-1)\lambda),\ldots$, so

If a constant offset $\Delta$ is added to each time, the corresponding result also increases by $\Delta$.

0x02 Synchronous SGD

Time per Update

Synchronous updates wait for all workers, therefore

$H_m=\log m+\gamma_{\rm E}+O(1/m)$, where $\gamma_{\rm E}$ is the Euler constant. $\log m$ is the dominant term only for large m; when $m=1$, one must use $H_1=1$.

The total time to complete a fixed number t of updates is $W_t=\sum_{j=0}^{t-1}S_j$, hence

If each round’s time is i.i.d. with finite mean, the number of updates completed within a fixed time $N(T)$ satisfies $N(T)/T\to1/s_m$ (almost surely). The long-term batch throughput is $m/s_m$. This is not the exact expectation of an arbitrary throughput random variable within a finite time.

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

Then $\mathcal E_t\le C_m+q^t(\mathcal E_0-C_m)$. If $0<q<1$ and $\mathcal E_0>\epsilon>C_m$, define

After completing these t updates, the expected function value error does not exceed $\epsilon$, with an expected elapsed time of $s_m t_\epsilon$. This is not the expected hitting time for a specific random training trajectory to first reach the error threshold.

If $\epsilon\le C_m$, the current bound cannot guarantee reaching the target. If the initial error already satisfies the target, one may stop; when using $q=0$, employ single-step recursion without computing logarithms.

Choosing a Step Size for a Target Accuracy

Let $\sigma^2>0$ and $\mathcal E_0>\epsilon>0$. One may choose

to make $C_m\le\epsilon/2$. Utilizing $q^t\le e^{-\eta\mu t}$, take

sufficient to reach the target. Thus, we can provide an upper bound on runtime retaining the deterministic term, the noise term, and the logarithmic term:

Approximate iterative scaling of $1/(m\epsilon)$ occurs only within the corresponding range where the noise term dominates, other fixed constants are ignored, and necessary logarithmic terms are retained. Once m increases to the point where the step-size upper bound becomes active, the number of iterations no longer decreases indefinitely according to $1/m$; the waiting cost per round still increases. When $\sigma^2=0$, directly adopt the complexity of deterministic strongly convex GD.

Error at a Fixed Wall-clock Time

$N(T)$ is a random variable; one cannot replace it with $T/s_m$ and still write the formula as a strict upper bound. In models where the runtime process and gradient sampling are independent, one should first condition on $N(T)$:

Even if these independence assumptions hold, one cannot directly substitute $\mathbb E[q^{N(T)}]$ with $q^{\mathbb E[N(T)]}$. For $0<q<1$, the latter is a lower bound of the former by Jensen’s inequality; when $\mathcal E_0>C_m$, this substitution would underestimate the current error upper bound.

For example, when $m=1,\Delta=0$, $N(T)$ is a Poisson variable with parameter $\lambda T$, hence $\mathbb E[q^{N(T)}]=\exp(\lambda T(q-1))$ generally does not equal $q^{\lambda T}$. $N(T)\approx T/s_m$ can be used to illustrate trends but must be labeled as an approximation.

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

K-Sync

Each round starts from the same parameter, receiving results from the fastest K distinct workers and canceling the remaining tasks. Therefore, for shifted exponential latency,

when $K=1$ it becomes $\Delta+1/(m\lambda)$, and when $K=m$ it reverts to synchronous results. The logarithmic approximation $\lambda^{-1}\log(m/(m-K))$ does not apply to $K=m$ and should also be avoided near boundaries in place of exact harmonic numbers.

Under models where the selected batch remains conditionally unbiased and noise-independent, the error bound uses $C_K=\eta L\sigma^2/(2\mu bK)$. Given the same target error, compare $s_Kt_{\epsilon,K}$ rather than only comparing $s_K$. Choosing a smaller K can reduce waiting time but increases the noise term in the bound. If speed correlates with samples or local data distributions, selection bias must be addressed first.

K-Batch-Sync

All workers compute on the current parameter; once a worker finishes, it continues computing the next independent batch until a total of K batches are received, after which an update occurs and unfinished old tasks are canceled.

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

Here K is the number of batches and need not be less than m. Under shifted or general service times, the completion process within a round is typically not a Poisson process, so this formula cannot be used directly.

0x04 Asynchronous SGD and Renewal Theory

In single-gradient asynchronous SGD, workers upload immediately upon completion, read the current parameter, and start the next batch; the server updates once for every gradient received. Server queuing and model transmission bottlenecks are not considered here.

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

This defines the renewal process. The renewal count limit derived from the strong law of large numbers is $A_i(T)/T\to1/\mathbb E[X]$ (almost surely); the basic renewal theorem provides the expected version $\mathbb E[A_i(T)]/T\to1/\mathbb E[X]$. These two should be distinguished.

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

It does not guarantee that the expected waiting time for each update is identical from initialization. For example, if all service times are fixed at 1, the first completion event still waits 1; afterward, simultaneous arrival events may occur.

Comparing Sync and Async

Under non-shifted exponential times, the waiting time for single-gradient asynchronous updates is $\operatorname{Exp}(m\lambda)$, hence the mean is $1/(m\lambda)$. The synchronous mean per round is $H_m/\lambda$, with a ratio of $mH_m$.

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

Asynchronous single updates are faster, but synchronous updates use m batches per round while asynchronous uses one batch per update, and asynchronous suffers from stale gradients. This time ratio is not the training speedup to achieve the same accuracy. Asynchronous error bounds also depend on the relative staleness and conditional noise assumptions from Part 4 ¹.

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

K-Async

K-Async receives results from K distinct workers each time. Workers that have already returned results in the current round wait for the server’s update before reading new parameters; those not yet finished continue their old computations, so the remaining service time at the start of the next round typically differs from a fresh service time.

Under independent, homogeneous, non-shifted exponential service times, the memoryless property ensures the remaining time is still an independent exponential variable, hence the mean per round is

The general distribution cannot use this equality. If X satisfies the new-longer-than-used condition, meaning that for all non-negative a, u (when the conditional event probability is non-zero),

then the remaining time of the running task is stochastically less than or equal to the fresh time, yielding $\mathbb E[S_{K\text{-async}}]\le\mathbb E[X_{K:m}]$. For example, the shifted exponential distribution satisfies this condition, with the right-hand side being $\Delta+(H_m-H_{m-K})/\lambda$, but generally there is no equality. Any other distribution still requires computing its own order statistics rather than using the exponential harmonic number formula.

K-Batch-Async

This variant updates after the server receives every K batches; workers read the current parameters and continue working upon completing each batch, without requiring contributors to be K distinct workers and without canceling in-progress batches.

Under the ideal unbiased exponential model, the mean time to wait for K total completion events is $K/(m\lambda)$. For general finite-mean service times, renewal theory provides the long-run average time per server update, $K\mathbb E[X]/m$, rather than an exact expectation equation for any finite number of rounds.

K-Async and K-batch-async have different waiting and lagging mechanisms. When comparing them, one should simultaneously verify their respective conditionally unbiasedness, noise correlation, and lag bounds, and then compare the time required to achieve the same target accuracy.

0x06 Reference

This paper treats the expected completion time for a fixed number of updates, the expected error within a fixed time, and the long-term throughput separately, avoiding treating asymptotic or mean approximations as strict guarantees for finite time.

Sources: ^{2 3 4 5}.