Convergence Analysis in Distributed Machine Learning (Part 4)

0x00 Preface

This article extends the mini-batch SGD analysis from Part 3¹ to the distributed setting. We assume $f$ is a $L$-smooth, $\mu$-strongly convex function on Euclidean space, with an optimal solution existing, $f^{\ast}=f(w^{\ast})$. $m$ denotes the number of workers, $b$ the batch size per worker, and $\sigma^2$ the upper bound on the variance of single-sample gradient noise.

The distributed bounds in this paper rely on conditional unbiasedness, noise variance bounds, and corresponding independence assumptions. For scenarios where different workers hold data from different distributions, workers are selected based on completion speed, or computation time depends on the sample, these conditions must be re-verified. Having more machines or faster updates does not, by itself, guarantee that the convergence bounds hold.

0x01 Distributed Synchronous SGD

All workers use the same $w_t$, computing individually

Given the pre-sampling history $\mathcal F_t$, we assume the workers’ gradients are conditionally unbiased with respect to the global objective, their noises are mutually independent, and the noise variance for each worker does not exceed $\sigma^2/b$. Therefore

defination

For $0<\eta\le1/L$, let $\mathcal E_t=\mathbb E[f(w_t)]-f^{\ast}$, yielding

$$ \mathcal E_T\le C_m+(1-\eta\mu)^T(\mathcal E_0-C_m), \qquad C_m=\frac{\eta L\sigma^2}{2\mu bm}. $$

The proof simply substitutes $\sigma^2/(bm)$ into the one-step recurrence from Part 3 and expands the geometric series. With a fixed step size, this guarantees contraction to an error upper bound plateau, not linear convergence to zero error.

K-Sync and K-Batch-Sync

K-Sync accepts gradients from the fastest $K\le m$ workers and cancels the remaining tasks; K-batch-sync accepts $K$ batches computed on the same parameter, allowing fast workers to contribute multiple batches consecutively.

If the batches after selection remain conditionally unbiased, and their noises are conditionally independent or uncorrelated, replace the variance with $\sigma^2/(bK)$; the error upper bound plateau becomes $C_K=\eta L\sigma^2/(2\mu bK)$. Independence from sampling time and each worker sampling from the same global distribution constitute an ideal model supporting these conditions.

If speed correlates with sample categories, selecting the fastest K may introduce bias. Local gradients from non-IID workers are not necessarily unbiased estimates of the global gradient. Thus, one cannot simply substitute $m$ with $K$ while skipping assumption checks.

0x02 Distributed Asynchronous SGD

Asynchronous updates accept a single worker’s gradient without waiting for all workers:

$\tau_j$ is the parameter version read when computing this gradient, and $d_j=j-\tau_j$ is the staleness step count. $\xi_j$ represents a batch of size $b$; both the model version and the sampled batch may be random.

Assumptions for the Proof

To ensure the subsequent proof holds step-by-step, we explicitly adopt the following conditions.

1. Conditional Noise Model. Let $\mathcal H_j$ contain the server parameter history prior to this update, the selected worker, old parameters, and delay information, but exclude the sample noise of the gradient to be applied. Write $a_j=\nabla f(w_{\tau_j})$, $v_j=a_j+e_j$, requiring

$w_j$ and $w_{\tau_j}$ are measurable with respect to $\mathcal H_j$. This condition is more explicit than unbiasedness given only old parameters; if delay or the selection process leaks sample information, a separate proof is required to establish it.

2. Relative Gradient Staleness Bound. There exists $0\le\gamma\le1$ such that in every round,

This is not a bound on the delay steps $d_j\le d_{\max}$, nor does it follow automatically from smoothness. Especially when the current gradient is small, this condition can be quite strong.

3. Fresh Gradient Probability Lower Bound. Let $\mathcal P_j$ be the history prior to revealing the delay of the current selection, where $w_j$ is measurable. Assume there exists $p_0\in[0,1]$ such that

Thus

This step first applies the probability lower bound given the history, then takes the expectation, avoiding moving the random conditional probability directly outside the expectation.

Convergence Bound

defination

Let $\gamma'=1-\gamma+p_0/2>0$. Under the above conditions and $0<\eta\le1/(2L)$,

$$ \mathcal E_T\le C_{\rm async}+(1-\eta\mu\gamma')^T(\mathcal E_0-C_{\rm async}), \qquad C_{\rm async}=\frac{\eta L\sigma^2}{2\mu b\gamma'}. $$

Proof: Take the conditional expectation under $\mathcal H_j$; the noise cross-terms vanish. Then take the total expectation; smoothness yields

Using $2\langle u,a\rangle=\Vert u\Vert^2+\Vert a\Vert^2-\Vert u-a\Vert^2$, we obtain

The second step uses $1-L\eta\ge1/2$ and the freshness probability lower bound. Then apply the PL inequality:

Since $\mu\le L$, $\gamma’\le3/2$, the step size restriction ensures the contraction coefficient lies within $[0,1)$. Expanding the recurrence yields the theorem. When $\gamma’=0$, we cannot divide by it, nor can we derive this geometric contraction bound from it.

Interpreting Staleness

In the idealized model with homogeneous workers, independent non-shifted exponential service times, and instantaneous server processing and model reads, the next completion occurs with equal probability among $m$ workers. For single-gradient asynchronous updates, the freshness probability of the gradient can be taken as $p_0=1/m$.

After stabilization, the lag steps $d_j$ exhibit a geometric tail; the absolute version index $\tau_j$ does not follow a geometric distribution. The startup phase is constrained by $0\le d_j\le j$ and must be considered separately. For heterogeneous times, shifted exponentials, or general service distributions, this probability conclusion cannot be applied directly.

0x03 K-Async SGD

K-Async aggregates gradients from K distinct workers per update; workers completing in this round wait for this update before reading new parameters, while workers not yet completed retain their old computations. The update is

Given $\mathcal H_j$ containing all selected old parameters and delays, write $v_{i,j}=a_{i,j}+e_{i,j}$, requiring that the noise be conditionally unbiased, conditionally uncorrelated, and that each variance not exceed $\sigma^2/b$. Thus, the average noise variance does not exceed $\sigma^2/(bK)$.

Additionally, we require a lower bound on the average relative lag and the freshness probability for each selected gradient:

Denote $\bar a_j=K^{-1}\sum_i a_{i,j}$. By Jensen’s inequality, $\Vert\bar a_j\Vert^2\le K^{-1}\sum_i\Vert a_{i,j}\Vert^2$. After applying the inner product identity to each $a_{i,j}$ and taking the average, we obtain

Therefore, under the same step-size constraints and $\gamma’>0$ conditions,

Here, one must verify $\gamma$ and $p_0$ for each K separately; they cannot be assumed independent of K, nor can the single-gradient $p_0=1/m$ be blindly copied without conditions. K-batch-async allows a single worker to contribute multiple batches consecutively; it operates under a different runtime model, and the noise and lag conditions must be re-examined.

0x04 What the Analysis Does Not Guarantee

Variance reduction in the synchronous model’s $1/m$ and the asynchronous model’s $1/K$ both rely on the noise structure. The relative gradient lag bound in the asynchronous setting is an additional condition; merely providing the number of delay steps or a faster update rate cannot substitute for it. These strongly convex conclusions do not directly cover general non-convex neural networks or non-IID federated learning.

For combining iteration bounds with stochastic execution times, see Efficiency Analysis in Distributed Machine Learning². When comparing, one must simultaneously consider batch size, the error upper bound plateau, step size, and the time per round.

Reference

This article uses a simplified model with uniformly bounded single-sample variance and explicitly states the conditional noise assumptions required for the proof; the original paper allows more general gradient-dependent variance models, so one cannot omit its additional step-size conditions and directly copy the results.

Sources: ^{3 4 5}.