PaperlayerView exact revision on arXiv

Source-linked AI summary

Asynchronous Decentralized Parallel Stochastic Gradient Descent

Xiangru Lian, Wei Zhang, Ce Zhang, Ji Liu

arXiv:1710.06952v3math.OCcs.LGstat.ML

TL;DR

Distributed learning must handle stragglers without the bottleneck of centralized asynchronous systems while retaining strong convergence. AD-PSGD addresses this with asynchronous decentralized communication, achieving the convergence rate of synchronous or centralized methods and linear speedup, with empirical validation in heterogeneous environments.

  • Problem

    The paper asks whether asynchronous distributed learning can remove the central server bottleneck while maintaining the best possible convergence rate.

  • Method

    AD-PSGD combines asynchronous updates with decentralized communication, allowing workers to proceed without waiting for all others.

  • Results

    AD-PSGD has the same convergence rate as synchronous and centralized counterparts, achieves linear speedup with the number of workers, and is validated by extensive experiments.

  • Takeaways & Limitations

    AD-PSGD is robust in heterogeneous environments and can converge similarly to AllReduce while outperforming synchronous counterparts in per-epoch speed.

  • Takeaways & Limitations

    When stochastic-gradient variance among workers is nonzero, AD-PSGD does not achieve linear speedup with minibatch size.

Abstract

from arXiv · show

Most commonly used distributed machine learning systems are either synchronous or centralized asynchronous. Synchronous algorithms like AllReduce-SGD perform poorly in a heterogeneous environment, while asynchronous algorithms using a parameter server suffer from 1) communication bottleneck at parameter servers when workers are many, and 2) significantly worse convergence when the traffic to parameter server is congested. Can we design an algorithm that is robust in a heterogeneous environment, while being communication efficient and maintaining the best-possible convergence rate? In this paper, we propose an asynchronous decentralized stochastic gradient decent algorithm (AD-PSGD) satisfying all above expectations. Our theoretical analysis shows AD-PSGD converges at the optimal $O(1/\sqrt{K})$ rate as SGD and has linear speedup w.r.t. number of workers. Empirically, AD-PSGD outperforms the best of decentralized parallel SGD (D-PSGD), asynchronous parallel SGD (A-PSGD), and standard data parallel SGD (AllReduce-SGD), often by orders of magnitude in a heterogeneous environment. When training ResNet-50 on ImageNet with up to 128 GPUs, AD-PSGD converges (w.r.t epochs) similarly to the AllReduce-SGD, but each epoch can be up to 4-8X faster than its synchronous counterparts in a network-sharing HPC environment. To the best of our knowledge, AD-PSGD is the first asynchronous algorithm that achieves a similar epoch-wise convergence rate as AllReduce-SGD, at an over 100-GPU scale.

1 Introduction

AD-PSGD combines asynchronous, decentralized communication to avoid central-server bottlenecks and synchronization barriers while preserving SGD-like convergence and worker scalability. Experiments report similar epoch-wise convergence to synchronous methods, with substantial speedups in shared-network settings.

  • Motivation and approach: AD-PSGD removes the central server bottleneck by combining asynchronous updates with decentralized worker communication.Workers do not wait for all others and communicate only with decentralized peers.
  • Theoretical properties: O(1/sqrt(K)) convergence is consistent with SGD and D-PSGD, while the method achieves linear speedup with respect to the number of workers.K denotes the number of updates.
  • Theoretical properties: AD-PSGD supports wait-free computation and communication, allowing more frequent information exchange than D-PSGD.This design is reported to improve convergence relative to D-PSGD with respect to epochs or wall time.
  • Empirical evaluation: On an IBM S822LC cluster with up to 128 P100 GPUs, AD-PSGD matched centralized or synchronous empirical convergence on real-world datasets.The experiments included ImageNet and heterogeneous computing environments.
  • Contributions: The paper identifies both theoretical analysis and system implementation as non-trivial technical contributions.

2 Related work

Related work spans centralized synchronous and asynchronous SGD, AllReduce-SGD, and decentralized methods. These approaches trade off convergence, synchronization delays, parameter-server communication, and resilience to stragglers.

  • Centralized SGD: SGD achieves the optimal O(1/sqrt(K)) convergence rate on nonconvex problems.
  • Centralized SGD: Synchronous parallel SGD achieves O(1/sqrt(nK)) convergence on nonconvex problems but idles workers behind the slowest worker and burdens the parameter server with O(n) synchronization.
  • Asynchronous SGD: A-PSGD avoids synchronization and tolerates unavailable workers, while bounded weight staleness supports the same convergence rate as synchronous parallel SGD.
  • Decentralized and collective communication: AllReduce-SGD matches synchronous SGD's update rule and convergence rate without a parameter server, using a ring network with O(deg(G)) = O(1) degree.
  • Decentralized and collective communication: D-PSGD averages neighboring local models on a connected graph, limiting the busiest worker to O(deg(G)) model transfers and handshakes per iteration.
  • Prior decentralized methods: Prior asynchronous decentralized methods differ from this work by omitting old-model gradients, worker-count linear-speedup guarantees, or deadlock-free wait-free implementation guarantees.

3 Algorithm

AD-PSGD combines asynchronous execution with decentralized model exchange: workers compute and communicate independently without global synchronization. Its design uses local objectives, stochastic gradient updates, pairwise averaging, flexible doubly stochastic matrices, and topologies intended to avoid deadlock and improve information dissemination.

  • Problem formulation: A worker graph connects machines or GPUs owning local data, and the resulting objective aggregates their local loss functions.The paper permits either shared data across workers or appropriately partitioned data to match the target objective.
  • Problem formulation: The algorithm models heterogeneous worker speeds through updating frequencies pi, with faster workers performing a larger percentage of updates.This weighting reflects that faster workers run more epochs in the same time and therefore contribute more updates.
  • Algorithm overview: AD-PSGD lets each worker maintain a local model and run sampling, gradient computation, gradient updating, and neighbor averaging independently.Workers do not wait for all others, reducing idle time when workers or network components slow down.
  • Algorithm overview: Each worker samples a mini-batch, computes a stochastic gradient from its local model, and updates that model using the learning rate.The sampled mini-batch has size M, and the gradient is computed from local data.
  • Algorithm overview: A randomly selected neighboring pair averages its local models, with both workers adopting the averaged model.The averaging step exchanges information only along a decentralized communication edge.
  • System design: AD-PSGD supports arbitrary doubly stochastic averaging matrices and uses bipartite communication to prevent deadlock during atomic pairwise updates.A ring is the simplest topology; longer-range ring connections reduce exchange time to at most O(log(n)) steps and provide multiple dissemination routes.

4 Theoretical analysis

The analysis represents asynchronous decentralized execution through a virtual update counter and worker-specific local models, then studies convergence under smoothness, doubly stochastic averaging, and delayed model reads. It establishes consistency with SGD and D-PSGD and identifies linear speedup with more workers.

  • Convergence results: AD-PSGD’s convergence rate is consistent with SGD and D-PSGD, with the corollary stated as O(1/√K) when the iteration count is sufficiently large.The theoretical analysis treats each stochastic-gradient update as one iteration.
  • Analytical model: Algorithm 1 counts every stochastic-gradient update as one iteration, regardless of which worker performs it.A virtual counter k records the update number, while i_k identifies the worker making the kth update.
  • Analytical model: At iteration k, x_i^k denotes worker i’s local model, and the global model state is represented by the collection of all local models.The algorithm initializes local models with the same initialization, learning rate, batch size, and total iteration count.
  • Analytical model: The stochastic gradient may be computed from a delayed read, represented as x̂^k = X^{k−τ_k} for a nonnegative delay τ_k.This captures asynchronous access to model states in the analysis.
  • Assumptions: The analysis assumes Lipschitzian gradients and doubly stochastic averaging matrices at every iteration.These are stated as the paper’s common assumptions for the theoretical results.

5. Bounded variance: Assume the variance of the stochastic gradient

Under stated assumptions and theorem conditions, AD-PSGD’s convergence is characterized for the average local model, with an O(1/√K) rate obtained by choosing the learning rate appropriately.

  • The main theorem applies when C3 ≤ 1, C2 ≥ 0, and C1 > 0.
  • AD-PSGD’s convergence analysis characterizes the average of all local models.
  • O(1/√K) convergence follows when the iteration number is sufficiently large.
  • AD-PSGD reduces to vanilla SGD when T = 0 and n = 1, yielding a convergence rate consistent with SGD.
  • O(1/(MK)) convergence in the zero-worker-variance case supports linear speedup with mini-batch size, matching mini-batch SGD.
  • When worker-gradient variance is nonzero, increasing mini-batch size does not provide linear speedup because that variance is independent of batch size.

5 Experiments

The experiments evaluate AD-PSGD across datasets, models, hardware, network conditions, worker counts, and heterogeneous slowdowns. Across these settings, it matches strong baselines in epoch-wise convergence while offering faster runtime and greater robustness.

  • Convergence w.r.t. epochs: AD-PSGD, AllReduce-SGD, and D-PSGD converge similarly on CIFAR10, while ASGD converges worse without sacrificing AD-PSGD’s test accuracy.The comparison uses VGG and ResNet-20 with 16 workers.
  • Convergence w.r.t. epochs: AD-PSGD converges similarly to AllReduce-SGD and better than D-PSGD w.r.t. epochs with 16, 32, 64, and 128 workers.Learning-rate warm-up and linear scaling were used for 64 and 128 workers.
  • Speedup and convergence w.r.t. runtime: AD-PSGD achieves the best speedup, with ResNet-20 scaling better than VGG because ResNet-20 is computation intensive.The speedup comparison covers both IBM HPC and x86 environments.
  • Convergence w.r.t. runtime: AD-PSGD consistently converges fastest w.r.t. runtime across communication-intensive and computation-intensive workloads on both fast and slow networks.The CIFAR10 runtime experiments use VGG and ResNet-20 on 100Gbit/s IBM HPC and 10Gbit/s x86 systems.
  • Speedup and convergence w.r.t. runtime: 264 seconds per epoch: AD-PSGD on 64 GPUs versus over 1000 sec/epoch for AllReduce-SGD and D-PSGD under shared network links.The ImageNet experiment uses ResNet-50 on IBM HPC.
  • Robustness in a heterogeneous environment: AD-PSGD remains robust to slow computation and communication, converging faster than synchronous baselines under very slow workers and avoiding EAMSGD’s slowdown under slower links.The robustness tests randomly slow one worker or its incoming and outgoing network links by 2X-100X.

6 Conclusion

The paper concludes that AD-PSGD combines decentralization and asynchronization to support heterogeneous environments while retaining convergence guarantees and linear worker speedup. Its robustness is also reflected in the computation-slowdown experiment.

  • Conclusion: AD-PSGD combines decentralization and asynchronization to remain robust in heterogeneous environments.The paper presents this combination as the basis of its robustness.
  • Conclusion: AD-PSGD is theoretically justified to match synchronous and centralized convergence rates and achieve linear speedup with respect to worker count.The conclusion also reports extensive experimental validation.
  • Conclusion: Orders of magnitude faster: AD-PSGD than AllReduce-SGD and D-PSGD when a computation device slows down by 2X-100X.The runtime-efficiency comparison uses ResNet-20 on CIFAR-10 with 16 workers.

A Wait-free (continuous) training and communication

AD-PSGD separates computation and communication into wait-free worker threads while maintaining local models and exchanging models with randomly selected neighbors. The design accommodates stale-model pulls through a local computation-thread update.

  • Implementation constraint: Atomic averaging between workers is required by the doubly stochastic matrix W used in the theoretical guarantee.This creates an implementation challenge when computation runs on GPUs and communication runs on CPUs or peripherals.
  • Algorithm structure: Each worker maintains a local model and repeatedly performs computation and communication without waiting for all other workers.The algorithm is organized around active and passive worker threads.
  • Computation thread: The computation thread pulls a local model, computes a stochastic gradient from a batch, and can compensate for stale models with a local update.The paper reports that this compensation helps scaling.
  • Communication thread: The active communication thread initializes the local model and learning rate, applies local gradient updates, randomly selects a neighbor, and exchanges models.The exchange sends x_i and fetches the neighbor’s model.

B NLC experiments

The NLC experiments evaluate AD-PSGD on proprietary and public sentence-classification workloads using a CNN model. AD-PSGD converges similarly to AllReduce-SGD and D-PSGD w.r.t. epochs.

  • NLC workloads: The IBM NLC task classifies input sentences into target categories using a CNN with word embedding, convolutional, fully connected, and softmax layers.The evaluated datasets are Joule and Yelp.
  • NLC workloads: Joule contains 2.5K training samples, 1K test samples, and 311 classes, while Yelp contains 500K training samples, 2K test samples, and 5 classes.Joule is an in-house customer dataset and Yelp is public.
  • Results: AD-PSGD converges similarly to AllReduce-SGD and D-PSGD w.r.t. epochs on the IBM NLC workload.The result is reported for both Joule and Yelp datasets.

C Appendix: proofs

The appendix proves the paper’s theoretical results by controlling consensus and optimization-error terms, then verifying step-size conditions for the main theorem and corollary.

  • Main theorem: Theorem 1 is established by combining upper bounds derived from the preceding lemmas and rearranging the resulting terms.The proof explicitly invokes bounds from equations (11) and (12) before concluding.
  • Consensus analysis: The proof constructs an eigenvector basis for a symmetric doubly stochastic matrix to bound disagreement components orthogonal to the consensus vector.The non-consensus eigenvalues are bounded in magnitude by ρ, enabling the disagreement analysis.
  • Consensus analysis: The analysis uses identical initial worker models and doubly stochasticity to simplify the evolution of the averaged model.Because all columns of X0 are identical, X0W^k = X0 for every k.
  • Main theorem: The proof decomposes intermediate quantities into terms A1–A4, bounds them separately, and recombines the bounds to complete the main inequality.Arithmetic–geometric mean inequalities and tunable positive coefficients α_j,j′ are used in several bounds.
  • Corollary: The corollary follows by imposing step-size requirements that ensure C1 ≥ 1/2, C2 ≥ 0, and C3 ≤ 1.The appendix derives sufficient constraints on γ by bounding the final terms and then applies Theorem 1.
Loading 1710.06952v3…