Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms

Abstract

Communication-efficient SGD algorithms, which allow nodes to perform local updates and periodically synchronize local models, are highly effective in improving the speed and scalability of distributed SGD. However, a rigorous convergence analysis and comparative study of different communication-reduction strategies remains a largely open problem. This paper presents a unified framework called Cooperative SGD that subsumes existing communication-efficient SGD algorithms such as periodic-averaging, elastic-averaging and decentralized SGD. By analyzing Cooperative SGD, we provide novel convergence guarantees for existing algorithms. Moreover, this framework enables us to design new communication-efficient SGD algorithms that strike the best balance between reducing communication overhead and achieving fast error convergence with low error floor.

References in corpus (19)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Optimal Distributed Online Prediction using Mini-Batches
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• Gradient Sparsification for Communication-Efficient Distributed Optimization
• Parallel training of DNNs with Natural Gradient and Parameter Averaging
• Parallel SGD: When does averaging help?
• SparkNet: Training Deep Networks in Spark
• YellowFin and the Art of Momentum Tuning
• Experiments on Parallel Training of Deep Neural Network using Model Averaging
• Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD
• Parle: parallelizing stochastic gradient descent
• On Nonconvex Decentralized Gradient Descent

Cited by in corpus (98)

• On the Convergence of FedAvg on Non-IID Data
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• Federated Optimization in Heterogeneous Networks
• Personalized Federated Learning: A Meta-Learning Approach
• Fair Resource Allocation in Federated Learning
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• FMore: An Incentive Scheme of Multi-dimensional Auction for Federated Learning in MEC
• Personalized Federated Learning with Moreau Envelopes
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data
• On the Convergence of Local Descent Methods in Federated Learning
• A Field Guide to Federated Optimization
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Adaptive Federated Optimization
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Variance Reduced Local SGD with Lower Communication Complexity
• VAFL: a Method of Vertical Asynchronous Federated Learning
• Adaptive Federated Learning in Resource Constrained Edge Computing Systems
• Joint Optimization of Communications and Federated Learning Over the Air
• Fast Federated Learning by Balancing Communication Trade-Offs
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• First Analysis of Local GD on Heterogeneous Data
• Central Server Free Federated Learning over Single-sided Trust Social Networks
• Throughput-Optimal Topology Design for Cross-Silo Federated Learning
• Federated Learning via Over-the-Air Computation
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Is Local SGD Better than Minibatch SGD?
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• Faster On-Device Training Using New Federated Momentum Algorithm
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Personalized Federated Learning using Hypernetworks
• Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD
• Decentralized Deep Learning with Arbitrary Communication Compression
• SpreadGNN: Serverless Multi-task Federated Learning for Graph Neural Networks
• FedGAN: Federated Generative Adversarial Networks for Distributed Data
• FedAT: A High-Performance and Communication-Efficient Federated Learning System with Asynchronous Tiers
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• Communication-Efficient Local Decentralized SGD Methods
• Communication-Efficient Edge AI: Algorithms and Systems
• Decentralized Bayesian Learning over Graphs
• Cross-Silo Federated Learning for Multi-Tier Networks with Vertical and Horizontal Data Partitioning
• Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates
• On the Outsized Importance of Learning Rates in Local Update Methods
• STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning
• Differentially Private Federated Learning for Resource-Constrained Internet of Things
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
• Personalized Federated Learning for Heterogeneous Clients with Clustered Knowledge Transfer
• LASG: Lazily Aggregated Stochastic Gradients for Communication-Efficient Distributed Learning
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• Gradient Descent with Compressed Iterates
• What Do We Mean by Generalization in Federated Learning?
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• Federated Composite Optimization
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• RingFed: Reducing Communication Costs in Federated Learning on Non-IID Data
• Distributed Deep Learning with Event-Triggered Communication
• FedDANE: A Federated Newton-Type Method
• Concentrated Differentially Private and Utility Preserving Federated Learning
• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent
• Communication-Efficient Distributed SVD via Local Power Iterations
• Anarchic Federated Learning
• Distributed Fixed Point Methods with Compressed Iterates
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization
• MixML: A Unified Analysis of Weakly Consistent Parallel Learning
• Trends and Advancements in Deep Neural Network Communication
• Overlap Local-SGD: An Algorithmic Approach to Hide Communication Delays in Distributed SGD
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• 1-Bit Compressive Sensing for Efficient Federated Learning Over the Air
• Data Selection for Efficient Model Update in Federated Learning
• Multi-Level Local SGD for Heterogeneous Hierarchical Networks
• Optimal Complexity in Decentralized Training
• The Minimax Complexity of Distributed Optimization
• Trajectory Normalized Gradients for Distributed Optimization
• A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate
• Federated Learning via Plurality Vote
• CSER: Communication-efficient SGD with Error Reset
• Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance Reduction
• DaSGD: Squeezing SGD Parallelization Performance in Distributed Training Using Delayed Averaging
• FedPower: Privacy-Preserving Distributed Eigenspace Estimation
• Matrix Sketching for Secure Collaborative Machine Learning
• DEED: A General Quantization Scheme for Communication Efficiency in Bits
• CFedAvg: Achieving Efficient Communication and Fast Convergence in Non-IID Federated Learning
• Statistical Estimation and Inference via Local SGD in Federated Learning
• Decentralized Learning with Lazy and Approximate Dual Gradients
• The Gradient Convergence Bound of Federated Multi-Agent Reinforcement Learning with Efficient Communication
• A Personalized Federated Learning Algorithm: an Application in Anomaly Detection
• Towards Heterogeneous Clients with Elastic Federated Learning
• Trade-offs of Local SGD at Scale: An Empirical Study
• Network-Density-Controlled Decentralized Parallel Stochastic Gradient Descent in Wireless Systems
• Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications