AD-PSGD (Asynchronous Decentralized Parallel Stochastic Gradient Descent)

Because every realization of the random gossip matrix W_k is doubly stochastic (W_k (1/n) 1 1^T = (1/n) 1 1^T), multiplying X_{k+1} = X_k W_k - gamma G_bar(hat_X_k; xi_k) by (1/n) 1 yields an exact centralized asynchronous recursion X_{k+1} (1/n) 1 = X_k (1/n) 1 - (gamma / n) g(hat_x^{i_k}; xi^{i_k}) for the network mean while the spectral gap rho = ||E[W_k^T (I - (1/n) 1 1^T) W_k]||_2 < 1 contracts consensus error, yielding the non-convex ergodic gradient rate (1/K) sum_{k=0}^{K-1} E[||nabla f(bar_x_k)||^2] <= O(1 / sqrt(K)) + O(n sigma^2 / K) (Theorem 1, Corollary 1), which achieves optimal O(1 / sqrt(K_1 n)) iteration speedup in epoch steps K_1 = K / n whenever K >= O(n^3 (N^2 + 1 / (1 - rho)^2)).

By splitting each worker into a gradient-computation thread and a gossip-averaging thread that updates X_k <- X_k W_k atomically with a single neighbor without global barriers, AD-PSGD completes K updates in wall-clock time proportional to the harmonic mean of worker speeds rather than the slowest straggler max_i t_i (Section 3, Figures 1-2).

To avoid pairwise gossip deadlocks in practice, workers must be partitioned into active and passive communication roles (e.g., a bipartite graph), and the transient iteration horizon before linear speedup scales with the staleness bound N^2 and inverse spectral gap 1 / (1 - rho)^2.

Applied to distributed training of ResNet-50 and VGG neural networks on CIFAR-10 and ImageNet across up to 128 GPUs under heterogeneous compute and network speeds.