Communication-Efficient Local Decentralized SGD Methods

Abstract

Recently, the technique of local updates is a powerful tool in centralized settings to improve communication efficiency via periodical communication. For decentralized settings, it is still unclear how to efficiently combine local updates and decentralized communication. In this work, we propose an algorithm named as LD-SGD, which incorporates arbitrary update schemes that alternate between multiple Local updates and multiple Decentralized SGDs, and provide an analytical framework for LD-SGD. Under the framework, we present a sufficient condition to guarantee the convergence. We show that LD-SGD converges to a critical point for a wide range of update schemes when the objective is non-convex and the training data are non-identically independent distributed. Moreover, our framework brings many insights into the design of update schemes for decentralized optimization. As examples, we specify two update schemes and show how they help improve communication efficiency. Specifically, the first scheme alternates the number of local and global update steps. From our analysis, the ratio of the number of local updates to that of decentralized SGD trades off communication and computation. The second scheme is to periodically shrink the length of local updates. We show that the decaying strategy helps improve communication efficiency both theoretically and empirically.

References in corpus (26)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning with Non-IID Data
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Federated Optimization in Heterogeneous Networks
• Communication-Efficient On-Device Machine Learning: Federated Distillation and Augmentation under Non-IID Private Data
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• ATOMO: Communication-efficient Learning via Atomic Sparsification
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Communication Compression for Decentralized Training
• D${}^2$: Decentralized Training over Decentralized Data
• On the Convergence of Local Descent Methods in Federated Learning
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Stochastic Gradient Push for Distributed Deep Learning
• AIDE: Fast and Communication Efficient Distributed Optimization
• Federated Deep Reinforcement Learning
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions
• Heterogeneity-Aware Asynchronous Decentralized Training

Cited by in corpus (10)

• Personalized Federated Learning with Moreau Envelopes
• Federated Mutual Learning
• Throughput-Optimal Topology Design for Cross-Silo Federated Learning
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• Distributed Learning over Networks with Graph-Attention-Based Personalization
• Training Federated GANs with Theoretical Guarantees: A Universal Aggregation Approach
• Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data
• Adaptive Serverless Learning
• FedPower: Privacy-Preserving Distributed Eigenspace Estimation
• On the Convergence of Quantized Parallel Restarted SGD for Central Server Free Distributed Training