Federated Accelerated Stochastic Gradient Descent

Abstract

We propose Federated Accelerated Stochastic Gradient Descent (FedAc), a principled acceleration of Federated Averaging (FedAvg, also known as Local SGD) for distributed optimization. FedAc is the first provable acceleration of FedAvg that improves convergence speed and communication efficiency on various types of convex functions. For example, for strongly convex and smooth functions, when using $M$ workers, the previous state-of-the-art FedAvg analysis can achieve a linear speedup in $M$ if given $M$ rounds of synchronization, whereas FedAc only requires $M^{\frac{1}{3}}$ rounds. Moreover, we prove stronger guarantees for FedAc when the objectives are third-order smooth. Our technique is based on a potential-based perturbed iterate analysis, a novel stability analysis of generalized accelerated SGD, and a strategic tradeoff between acceleration and stability.

Accepted to NeurIPS 2020. Best paper in International Workshop on Federated Learning for User Privacy and Data Confidentiality in Conjunction with ICML 2020 (FL-ICML'20). Code repository see https://github.com/hongliny/FedAc-NeurIPS20

References in corpus (9)

• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• On the Convergence of Local Descent Methods in Federated Learning
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• FedSplit: An algorithmic framework for fast federated optimization
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization

Cited by in corpus (9)

• FedCM: Federated Learning with Client-level Momentum
• Federated Data Analytics: A Study on Linear Models
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Local SGD: Unified Theory and New Efficient Methods
• Efficient Algorithms for Federated Saddle Point Optimization
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Towards Scheduling Federated Deep Learning using Meta-Gradients for Inter-Hospital Learning
• Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions