On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization

Abstract

Recent developments on large-scale distributed machine learning applications, e.g., deep neural networks, benefit enormously from the advances in distributed non-convex optimization techniques, e.g., distributed Stochastic Gradient Descent (SGD). A series of recent works study the linear speedup property of distributed SGD variants with reduced communication. The linear speedup property enable us to scale out the computing capability by adding more computing nodes into our system. The reduced communication complexity is desirable since communication overhead is often the performance bottleneck in distributed systems. Recently, momentum methods are more and more widely adopted in training machine learning models and can often converge faster and generalize better. For example, many practitioners use distributed SGD with momentum to train deep neural networks with big data. However, it remains unclear whether any distributed momentum SGD possesses the same linear speedup property as distributed SGD and has reduced communication complexity. This paper fills the gap by considering a distributed communication efficient momentum SGD method and proving its linear speedup property.

A short version of this paper is accepted to ICML 2019

Cited by in corpus (42)

• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• A Field Guide to Federated Optimization
• Variance Reduced Local SGD with Lower Communication Complexity
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• Robust Federated Learning: The Case of Affine Distribution Shifts
• Privacy-preserving Federated Brain Tumour Segmentation
• Federated Learning with Buffered Asynchronous Aggregation
• An Improved Analysis of Stochastic Gradient Descent with Momentum
• Secure Federated Submodel Learning
• Fast Federated Learning in the Presence of Arbitrary Device Unavailability
• Learning from History for Byzantine Robust Optimization
• Learn Electronic Health Records by Fully Decentralized Federated Learning
• Local Adaptivity in Federated Learning: Convergence and Consistency
• STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning
• Adversarial training in communication constrained federated learning
• Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Acceleration
• Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
• SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization
• To Talk or to Work: Flexible Communication Compression for Energy Efficient Federated Learning over Heterogeneous Mobile Edge Devices
• SGD_Tucker: A Novel Stochastic Optimization Strategy for Parallel Sparse Tucker Decomposition
• What Do We Mean by Generalization in Federated Learning?
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• Byzantine Resilient Non-Convex SVRG with Distributed Batch Gradient Computations
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• Distributed Optimization over Block-Cyclic Data
• Training Federated GANs with Theoretical Guarantees: A Universal Aggregation Approach
• Anarchic Federated Learning
• Adaptive Serverless Learning
• Distributed Machine Learning for Wireless Communication Networks: Techniques, Architectures, and Applications
• Cross-Gradient Aggregation for Decentralized Learning from Non-IID data
• Extrapolation for Large-batch Training in Deep Learning
• Distributed Sparse SGD with Majority Voting
• CFedAvg: Achieving Efficient Communication and Fast Convergence in Non-IID Federated Learning
• CADA: Communication-Adaptive Distributed Adam
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping
• Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance Reduction
• Federated Submodel Optimization for Hot and Cold Data Features
• Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexity
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization
• Toward Communication Efficient Adaptive Gradient Method