Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent

Abstract

Most distributed machine learning systems nowadays, including TensorFlow and CNTK, are built in a centralized fashion. One bottleneck of centralized algorithms lies on high communication cost on the central node. Motivated by this, we ask, can decentralized algorithms be faster than its centralized counterpart? Although decentralized PSGD (D-PSGD) algorithms have been studied by the control community, existing analysis and theory do not show any advantage over centralized PSGD (C-PSGD) algorithms, simply assuming the application scenario where only the decentralized network is available. In this paper, we study a D-PSGD algorithm and provide the first theoretical analysis that indicates a regime in which decentralized algorithms might outperform centralized algorithms for distributed stochastic gradient descent. This is because D-PSGD has comparable total computational complexities to C-PSGD but requires much less communication cost on the busiest node. We further conduct an empirical study to validate our theoretical analysis across multiple frameworks (CNTK and Torch), different network configurations, and computation platforms up to 112 GPUs. On network configurations with low bandwidth or high latency, D-PSGD can be up to one order of magnitude faster than its well-optimized centralized counterparts.

References in corpus (7)

• A Structured Self-attentive Sentence Embedding
• Revisiting Distributed Synchronous SGD
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Distributed Delayed Stochastic Optimization
• A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order
• Distributed Deep Learning for Question Answering
• Decentralized Consensus Optimization with Asynchrony and Delays

Cited by in corpus (43)

• Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• Communication optimization strategies for distributed deep neural network training: A survey
• The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning
• Taming Unbalanced Training Workloads in Deep Learning with Partial Collective Operations
• DataLens: Scalable Privacy Preserving Training via Gradient Compression and Aggregation
• SAFELearning: Enable Backdoor Detectability In Federated Learning With Secure Aggregation
• DiNNO: Distributed Neural Network Optimization for Multi-Robot Collaborative Learning
• Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup
• Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
• Edge-assisted Democratized Learning Towards Federated Analytics
• PEPPER: Empowering User-Centric Recommender Systems over Gossip Learning
• SpreadGNN: Serverless Multi-task Federated Learning for Graph Neural Networks
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Decentralized and Model-Free Federated Learning: Consensus-Based Distillation in Function Space
• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• Byzantine-Resilient Decentralized TD Learning with Linear Function Approximation
• Basil: A Fast and Byzantine-Resilient Approach for Decentralized Training
• DACFL: Dynamic Average Consensus Based Federated Learning in Decentralized Topology
• Decentralized Learning Made Easy with DecentralizePy
• Low Precision Decentralized Distributed Training over IID and non-IID Data
• Fast and Robust Sparsity Learning over Networks: A Decentralized Surrogate Median Regression Approach
• EventGraD: Event-Triggered Communication in Parallel Machine Learning
• Improved Convergence Analysis and SNR Control Strategies for Federated Learning in the Presence of Noise
• Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data
• A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints
• Get More for Less in Decentralized Learning Systems
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
• Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications
• Scalable Learning Paradigms for Data-Driven Wireless Communication
• Convergence Analysis of Decentralized ASGD
• Boosting Asynchronous Decentralized Learning with Model Fragmentation
• Practical Federated Learning without a Server
• Accelerating MoE Model Inference with Expert Sharding
• Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging
• Heavy-Tail Phenomenon in Decentralized SGD
• Stochastic Normalized Gradient Descent with Momentum for Large-Batch Training
• From Noisy Fixed-Point Iterations to Private ADMM for Centralized and Federated Learning
• ${\text{A}}^2{\text{CiD}}^2$: Accelerating Asynchronous Communication in Decentralized Deep Learning
• Attacks on Robust Distributed Learning Schemes via Sensitivity Curve Maximization