Variance Reduced Local SGD with Lower Communication Complexity

Abstract

To accelerate the training of machine learning models, distributed stochastic gradient descent (SGD) and its variants have been widely adopted, which apply multiple workers in parallel to speed up training. Among them, Local SGD has gained much attention due to its lower communication cost. Nevertheless, when the data distribution on workers is non-identical, Local SGD requires $O(T^{\frac{3}{4}}{N}^{\frac{3}{4}})$ communications to maintain its \emph{linear iteration speedup} property, where $T$ is the total number of iterations and $N$ is the number of workers. In this paper, we propose Variance Reduced Local SGD (VRL-SGD) to further reduce the communication complexity. Benefiting from eliminating the dependency on the gradient variance among workers, we theoretically prove that VRL-SGD achieves a \emph{linear iteration speedup} with a lower communication complexity $O(T^{\frac{1}{2}}{N}^{\frac{3}{2}})$ even if workers access non-identical datasets. We conduct experiments on three machine learning tasks, and the experimental results demonstrate that VRL-SGD performs impressively better than Local SGD when the data among workers are quite diverse.

25 pages, 6 figures. The paper presents a novel variance reduction algorithm for Local SGD

References in corpus (16)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Federated Learning: Strategies for Improving Communication Efficiency
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Optimal Distributed Online Prediction using Mini-Batches
• Deep Learning Autoencoder Approach for Handwritten Arabic Digits Recognition
• Don't Use Large Mini-Batches, Use Local SGD
• D${}^2$: Decentralized Training over Decentralized Data
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• signSGD with Majority Vote is Communication Efficient And Fault Tolerant
• Parallel training of DNNs with Natural Gradient and Parameter Averaging
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• Experiments on Parallel Training of Deep Neural Network using Model Averaging
• Faster Distributed Deep Net Training: Computation and Communication Decoupled Stochastic Gradient Descent

Cited by in corpus (39)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• Federated Learning of a Mixture of Global and Local Models
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data
• A Field Guide to Federated Optimization
• Federated Learning Based on Dynamic Regularization
• The Non-IID Data Quagmire of Decentralized Machine Learning
• Towards Efficient and Stable K-Asynchronous Federated Learning with Unbounded Stale Gradients on Non-IID Data
• Federated Graph Classification over Non-IID Graphs
• FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• Confederated Learning: Federated Learning with Decentralized Edge Servers
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• FedBE: Making Bayesian Model Ensemble Applicable to Federated Learning
• Communication-Efficient Robust Federated Learning with Noisy Labels
• FedCM: Federated Learning with Client-level Momentum
• Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy
• 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
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• Local SGD: Unified Theory and New Efficient Methods
• Federated Learning for Commercial Image Sources
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• Joint Local Relational Augmentation and Global Nash Equilibrium for Federated Learning with Non-IID Data
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Federated Semi-Supervised Learning with Class Distribution Mismatch
• Efficient Algorithms for Federated Saddle Point Optimization
• FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
• Cost-Effective Federated Learning in Mobile Edge Networks
• Privacy-preserving Federated Primal-dual Learning for Non-convex and Non-smooth Problems with Model Sparsification
• Federated Multiple Label Hashing (FedMLH): Communication Efficient Federated Learning on Extreme Classification Tasks
• Behavior Mimics Distribution: Combining Individual and Group Behaviors for Federated Learning
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Statistical Estimation and Inference via Local SGD in Federated Learning
• Local Methods with Adaptivity via Scaling
• Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions
• Towards Heterogeneous Clients with Elastic Federated Learning
• Compositional federated learning: Applications in distributionally robust averaging and meta learning
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters