Local SGD: Unified Theory and New Efficient Methods

Abstract

We present a unified framework for analyzing local SGD methods in the convex and strongly convex regimes for distributed/federated training of supervised machine learning models. We recover several known methods as a special case of our general framework, including Local-SGD/FedAvg, SCAFFOLD, and several variants of SGD not originally designed for federated learning. Our framework covers both the identical and heterogeneous data settings, supports both random and deterministic number of local steps, and can work with a wide array of local stochastic gradient estimators, including shifted estimators which are able to adjust the fixed points of local iterations for faster convergence. As an application of our framework, we develop multiple novel FL optimizers which are superior to existing methods. In particular, we develop the first linearly converging local SGD method which does not require any data homogeneity or other strong assumptions.

79 pages, 6 figures, 7 tables

References in corpus (24)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Federated Optimization in Heterogeneous Networks
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Federated Learning of a Mixture of Global and Local Models
• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• AIDE: Fast and Communication Efficient Distributed Optimization
• Distributed Learning with Compressed Gradient Differences
• Variance Reduced Local SGD with Lower Communication Complexity
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• FedSplit: An algorithmic framework for fast federated optimization
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• On Biased Compression for Distributed Learning
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Federated Accelerated Stochastic Gradient Descent
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions

Cited by in corpus (5)

• Recent theoretical advances in decentralized distributed convex optimization
• Efficient Algorithms for Federated Saddle Point Optimization
• Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning
• Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions