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.

arXiv commentA short version of this paper is accepted to ICML 2019

Cited by in corpus (62)

• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• Federated Optimization in Heterogeneous Networks
• Personalized Federated Learning with Moreau Envelopes
• A Field Guide to Federated Optimization
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Variance Reduced Local SGD with Lower Communication Complexity
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• First Analysis of Local GD on Heterogeneous Data
• Robust Federated Learning: The Case of Affine Distribution Shifts
• Privacy-preserving Federated Brain Tumour Segmentation
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
• Federated Learning with Buffered Asynchronous Aggregation
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• An Improved Analysis of Stochastic Gradient Descent with Momentum
• Decentralized Deep Learning with Arbitrary Communication Compression
• Communication-Efficient Local Decentralized SGD Methods
• Secure Federated Submodel Learning
• Recent theoretical advances in decentralized distributed convex optimization
• Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
• 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
• Federated Accelerated Stochastic Gradient Descent
• Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates
• 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
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• 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
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• What Do We Mean by Generalization in Federated Learning?
• 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
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• Communication Efficient Distributed Learning with Censored, Quantized, and Generalized Group ADMM
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• Federated Composite Optimization
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• 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
• Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization
• 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
• CFedAvg: Achieving Efficient Communication and Fast Convergence in Non-IID Federated Learning
• Federated Submodel Optimization for Hot and Cold Data Features
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping
• Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexity
• On the Convergence of Quantized Parallel Restarted SGD for Central Server Free Distributed Training
• Distributed Sparse SGD with Majority Voting
• CADA: Communication-Adaptive Distributed Adam
• Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance Reduction
• Toward Communication Efficient Adaptive Gradient Method
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization