Parallel and Asynchronous SGD: Staleness and Convergence Bounds

The analysis in step sizes and the descent lemma assumes the gradient used at iteration t was evaluated at the iterate of iteration t. Any parallel implementation breaks that assumption, because the gradient is produced somewhere else, on another device, in another process, on another machine, and by the time it is applied, the parameters have moved. The size of that mismatch is the central quantity in distributed optimization, and it appears in the convergence bounds multiplied by the step size. Everything else about distributed training is engineering around it: synchronisation schemes trade delay for throughput, and compression schemes trade delay for bandwidth.

Synchronous data parallelism and what it costs to exchange

In the synchronous scheme, k workers each compute a gradient on a batch of b/k examples and the gradients are averaged before the step, so the update is identical to a single-worker step on a batch of b examples. Correctness is free; throughput is not. The exchange volume per step is the size of the gradient in bytes, which is four bytes per parameter in single precision: for a model with 10⁸ parameters that is 400 MB per step, before any overhead. A ring all-reduce achieves this with each worker sending and receiving roughly 2(k−1)/k times the buffer size, so the total communication is close to twice the model size per worker per step and grows with the number of workers only through the (k−1)/k factor. The latency per step, however, grows with k in a ring because the number of sequential hops is proportional to the number of workers, and that cost is independent of the model’s size.

Synchronous schemes also inherit the straggler problem. The step cannot complete until the slowest worker has produced its gradient, so per-step time is set by the maximum over workers rather than the mean, and the gap between the two grows with the number of workers and with any heterogeneity in the hardware, the data layout, or the batch content. Larger batches amortise the fixed cost per step, but as the batch grows the marginal value of a step falls, for the reasons covered in gradient noise and batch size: past the noise-determined crossover, doubling the batch does not halve the number of steps needed.

Lock-free updates and the Hogwild model

The asynchronous alternative removes the barrier. Workers read the parameters, compute a gradient at whatever values they read, and apply it to the shared parameters without locking. The mechanism is a benign race: an update computed from slightly stale parameters is applied to slightly newer ones, and as long as the steps are small, the error introduced is comparable to the error from a noisy gradient. The published analysis makes this precise for sparse problems. If two workers touch disjoint coordinates, their updates commute and no error is introduced at all; when they overlap, one update is based on parameters that the other has since changed. For problems where each example touches a small fraction of the coordinates, as in logistic regression on sparse text features or matrix factorisation with sparse ratings, the probability of a conflict within a step is low, and the method works well with nothing more than atomic reads and writes.

The quantitative statement of the guarantee requires a bound on how far the parameters can move while a worker is computing, and that bound depends on the number of concurrent workers, the step size, and the gradient magnitude. The condition has the same shape as the stochastic gradient descent conditions with an extra factor: the step size must be small not only relative to the smoothness constant but also relative to the maximum overlapping delay. It fails in a specific and diagnostic way: increasing the number of workers with a fixed step size eventually produces divergence, and the threshold moves as the gradient magnitudes grow during training.

import random, threading

params = [1.0] * 8            # shared, never locked
target = [0.0] * 8
eta = 0.1

def worker(seed, steps):
    rng = random.Random(seed)
    for _ in range(steps):
        snapshot = list(params)                    # read, possibly mid-update
        i = rng.randrange(len(params))             # sparse: one coordinate per step
        params[i] -= eta * 2 * (snapshot[i] - target[i])

threads = [threading.Thread(target=worker, args=(s, 1000)) for s in range(4)]

The snippet is illustrative of the ordering, not of the hardware behaviour: in CPython the interpreter serialises the individual list operations, so the interleaving that damages a native implementation is not observable. In a compiled implementation with the parameter array in shared memory, a read that returns a mixture of values from before and after a concurrent write produces the same ordering error, and the aggregate effect over many steps is the staleness that the analysis models.

Where staleness enters the convergence bound

An asynchronous worker computes its gradient at a parameter vector from τ updates ago and applies it to the current one. Under an assumption that τ is bounded by some τ_max, the convergence results for this scheme match the synchronous bounds up to additive terms that grow with τ_max, with larger delays requiring correspondingly smaller step sizes to preserve the same accuracy, and the products of the step size and the per-step gradient magnitude also entering. The exponent structure of the two bounds is otherwise identical, for convex and non-convex objectives alike. The intuition for why the delay hurts at all is worth stating: the update direction is −η∇f(x_{t−τ}), while the direction that would decrease the current objective is −η∇f(x_t). The difference is η(∇f(x_{t−τ}) − ∇f(x_t)), bounded by ηL‖x_t − x_{t−τ}‖. If the parameters moved within a region of diameter Δ during the delay window, the error per step is on the order of ηLΔ, and Δ itself grows with τ and with the step size. This is the same quantity that appears as the change-of-point error in the control variate of variance-reduced methods; the two problems have the same geometry, one at the scale of an inner loop and the other at the scale of a network round trip.

Local steps and the drift they introduce

Communication can also be reduced by computing several steps between exchanges. A worker performs K local steps with its own data and then synchronises, so the communication volume drops by a factor of K relative to the per-step exchange. The consequence is that each worker spends the interval optimising a different objective, its own data’s loss, so the workers drift apart at a rate proportional to how much their local objectives differ from the average. In the federated averaging formulation, clients each take multiple local passes and the server averages the resulting parameters rather than the gradients, which is not the same operation: averaging parameters weights each client equally regardless of how far it travelled, and the drift accumulates with the number of local steps. The convergence results for this family contain an additive term that grows with the degree of data heterogeneity and vanishes only when the local objectives share a minimiser, which is precisely the assumption that fails when the data is partitioned by user or by device.

Failure modes that only appear with several workers

The most common silent failure is the interaction between delayed gradients and stateful optimisers. The per-coordinate accumulators of adaptive step sizes are updated with the gradient that arrives, which was computed at an older parameter vector. The second-moment estimate is thus attributed to the wrong coordinate history, and since the coordinate-wise step size is a ratio of the two accumulators, the error does not average out over workers the way a delayed first moment does. Implementations that apply a stale gradient to a fresh optimiser state therefore require a smaller step size than the same algorithm in a synchronous setting, and the penalty is not expressible as an extra term in the first-order analysis.

Three further failure modes are structural rather than numerical. Unbounded staleness produces divergence rather than noise, because there is always a delay beyond which the direction points against the current gradient; production systems bound it by dropping slow updates or by capping the number of outstanding gradients per worker. Non-uniform data partitioning changes the effective objective from the average loss to a weighted one that depends on how many steps each worker performs, so a worker with more data or more compute shifts the optimum. And asynchronous execution removes determinism by construction: the same code with the same data produces a different sequence of updates every run, which means that a change in the training curve cannot be attributed to a code change without controlling the ordering, and comparison between two configurations requires averaging over several runs rather than reading a single loss curve.