Local SGD Converges Fast and Communicates Little

Abstract

Mini-batch stochastic gradient descent (SGD) is state of the art in large scale distributed training. The scheme can reach a linear speedup with respect to the number of workers, but this is rarely seen in practice as the scheme often suffers from large network delays and bandwidth limits. To overcome this communication bottleneck recent works propose to reduce the communication frequency. An algorithm of this type is local SGD that runs SGD independently in parallel on different workers and averages the sequences only once in a while. This scheme shows promising results in practice, but eluded thorough theoretical analysis. We prove concise convergence rates for local SGD on convex problems and show that it converges at the same rate as mini-batch SGD in terms of number of evaluated gradients, that is, the scheme achieves linear speedup in the number of workers and mini-batch size. The number of communication rounds can be reduced up to a factor of T^{1/2}---where T denotes the number of total steps---compared to mini-batch SGD. This also holds for asynchronous implementations. Local SGD can also be used for large scale training of deep learning models. The results shown here aim serving as a guideline to further explore the theoretical and practical aspects of local SGD in these applications.

arXiv commentto appear at ICLR 2019, 19 pages

References in corpus (20)

• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• 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
• Revisiting Distributed Synchronous SGD
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Optimal Distributed Online Prediction using Mini-Batches
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Sparsified SGD with Memory
• Don't Use Large Mini-Batches, Use Local SGD
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
• meProp: Sparsified Back Propagation for Accelerated Deep Learning with Reduced Overfitting
• Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
• Parallel SGD: When does averaging help?
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
• On Data Dependence in Distributed Stochastic Optimization

Cited by in corpus (121)

• On the Convergence of FedAvg on Non-IID Data
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air
• Personalized Federated Learning: A Meta-Learning Approach
• Adaptive Personalized Federated Learning
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• A Crowdsourcing Framework for On-Device Federated Learning
• Three Approaches for Personalization with Applications to Federated Learning
• Multi-Armed Bandit Based Client Scheduling for Federated Learning
• Over-the-Air Federated Learning from Heterogeneous Data
• 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
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• A Decentralized Federated Learning Framework via Committee Mechanism with Convergence Guarantee
• Attack of the Tails: Yes, You Really Can Backdoor Federated Learning
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
• First Analysis of Local GD on Heterogeneous Data
• Natural Compression for Distributed Deep Learning
• Robust Federated Learning: The Case of Affine Distribution Shifts
• Central Server Free Federated Learning over Single-sided Trust Social Networks
• Is Local SGD Better than Minibatch SGD?
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• A Reputation Mechanism Is All You Need: Collaborative Fairness and Adversarial Robustness in Federated Learning
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• Federated Learning with Buffered Asynchronous Aggregation
• Faster On-Device Training Using New Federated Momentum Algorithm
• Personalized Federated Learning using Hypernetworks
• Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD
• Linearly Converging Error Compensated SGD
• Moniqua: Modulo Quantized Communication in Decentralized SGD
• Hierarchical Federated Learning through LAN-WAN Orchestration
• FedGAN: Federated Generative Adversarial Networks for Distributed Data
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• FedBE: Making Bayesian Model Ensemble Applicable to Federated Learning
• Communication-Efficient Local Decentralized SGD Methods
• Recent theoretical advances in decentralized distributed convex optimization
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• FedCM: Federated Learning with Client-level Momentum
• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates
• STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning
• Securing Secure Aggregation: Mitigating Multi-Round Privacy Leakage in Federated Learning
• Differentially Private Federated Learning for Resource-Constrained Internet of Things
• Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients
• Asynchronous Federated Learning with Reduced Number of Rounds and with Differential Privacy from Less Aggregated Gaussian Noise
• BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning
• Client Selection and Bandwidth Allocation in Wireless Federated Learning Networks: A Long-Term Perspective
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• 1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed
• Stochastic Weight Averaging in Parallel: Large-Batch Training that Generalizes Well
• Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
• Memorized Sparse Backpropagation
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
• Gradient Descent with Compressed Iterates
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Sustainable Federated Learning
• Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training?
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Local SGD: Unified Theory and New Efficient Methods
• RingFed: Reducing Communication Costs in Federated Learning on Non-IID Data
• Efficient Algorithms for Federated Saddle Point Optimization
• Periodic Stochastic Gradient Descent with Momentum for Decentralized Training
• Federated Semi-Supervised Learning with Class Distribution Mismatch
• A Distributed Hierarchical SGD Algorithm with Sparse Global Reduction
• Concentrated Differentially Private and Utility Preserving Federated Learning
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent
• Communication-Efficient Distributed SVD via Local Power Iterations
• Anarchic Federated Learning
• DBS: Dynamic Batch Size For Distributed Deep Neural Network Training
• OCTOPUS: Overcoming Performance andPrivatization Bottlenecks in Distributed Learning
• Local and Global Uniform Convexity Conditions
• Distributed Optimization for Over-Parameterized Learning
• Efficient and Less Centralized Federated Learning
• LocalNewton: Reducing Communication Bottleneck for Distributed Learning
• A Closer Look at Codistillation for Distributed Training
• On the Convergence of Nested Decentralized Gradient Methods with Multiple Consensus and Gradient Steps
• Trends and Advancements in Deep Neural Network Communication
• New Bounds For Distributed Mean Estimation and Variance Reduction
• Faster Distributed Deep Net Training: Computation and Communication Decoupled Stochastic Gradient Descent
• SLSGD: Secure and Efficient Distributed On-device Machine Learning
• Federated Learning with Fair Averaging
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• Communication-Efficient Policy Gradient Methods for Distributed Reinforcement Learning
• Data Selection for Efficient Model Update in Federated Learning
• State-of-the-art Techniques in Deep Edge Intelligence
• Overlap Local-SGD: An Algorithmic Approach to Hide Communication Delays in Distributed SGD
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Step-Ahead Error Feedback for Distributed Training with Compressed Gradient
• Hogwild! over Distributed Local Data Sets with Linearly Increasing Mini-Batch Sizes
• The Minimax Complexity of Distributed Optimization
• Matrix Sketching for Secure Collaborative Machine Learning
• CFedAvg: Achieving Efficient Communication and Fast Convergence in Non-IID Federated Learning
• Statistical Estimation and Inference via Local SGD in Federated Learning
• CD-SGD: Distributed Stochastic Gradient Descent with Compression and Delay Compensation
• Federated Learning with Unreliable Clients: Performance Analysis and Mechanism Design
• DEED: A General Quantization Scheme for Communication Efficiency in Bits
• FedPower: Privacy-Preserving Distributed Eigenspace Estimation
• On Second-order Optimization Methods for Federated Learning
• MergeComp: A Compression Scheduler for Scalable Communication-Efficient Distributed Training
• The Gradient Convergence Bound of Federated Multi-Agent Reinforcement Learning with Efficient Communication
• Escaping Saddle Points with Compressed SGD
• Distributed Learning and its Application for Time-Series Prediction
• Towards Heterogeneous Clients with Elastic Federated Learning
• Asynchronous Parallel Nonconvex Optimization Under the Polyak-Lojasiewicz Condition
• Addressing Algorithmic Bottlenecks in Elastic Machine Learning with Chicle
• Toward Efficient Federated Learning in Multi-Channeled Mobile Edge Network with Layerd Gradient Compression
• Trade-offs of Local SGD at Scale: An Empirical Study
• TESSERACT: Gradient Flip Score to Secure Federated Learning Against Model Poisoning Attacks
• Multilayer Lookahead: a Nested Version of Lookahead
• A Personalized Federated Learning Algorithm: an Application in Anomaly Detection
• Oscars: Adaptive Semi-Synchronous Parallel Model for Distributed Deep Learning with Global View
• HPSGD: Hierarchical Parallel SGD With Stale Gradients Featuring