Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization

Abstract

Due to the high communication cost in distributed and federated learning problems, methods relying on compression of communicated messages are becoming increasingly popular. While in other contexts the best performing gradient-type methods invariably rely on some form of acceleration/momentum to reduce the number of iterations, there are no methods which combine the benefits of both gradient compression and acceleration. In this paper, we remedy this situation and propose the first accelerated compressed gradient descent (ACGD) methods. In the single machine regime, we prove that ACGD enjoys the rate $O((1+\omega )\sqrt{\frac{L}{\mu }}\log \frac{1}{\epsilon })$ for $\mu$-strongly convex problems and $O((1+\omega )\sqrt{\frac{L}{\epsilon }})$ for convex problems, respectively, where $\omega$ is the compression parameter. Our results improve upon the existing non-accelerated rates $O((1+\omega )\frac{L}{\mu }\log \frac{1}{\epsilon })$ and $O((1+\omega )\frac{L}{\epsilon })$, respectively, and recover the optimal rates of accelerated gradient descent as a special case when no compression ($\omega =0$) is applied. We further propose a distributed variant of ACGD (called ADIANA) and prove the convergence rate $\tilde{O}(\omega +\sqrt{\frac{L}{\mu }}+\sqrt{(\frac{\omega }{n}+\sqrt{\frac{\omega }{n}})\frac{\omega L}{\mu }})$, where $n$ is the number of devices/workers and $\tilde{O}$ hides the logarithmic factor $\log \frac{1}{\epsilon }$. This improves upon the previous best result $\tilde{O}(\omega +\frac{L}{\mu }+\frac{\omega L}{n\mu })$ achieved by the DIANA method of Mishchenko et al. (2019). Finally, we conduct several experiments on real-world datasets which corroborate our theoretical results and confirm the practical superiority of our accelerated methods.

ICML 2020

References in corpus (16)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Sparsified SGD with Memory
• Distributed Learning with Compressed Gradient Differences
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Natural Compression for Distributed Deep Learning
• First Analysis of Local GD on Heterogeneous Data
• Distributed learning with compressed gradients
• SEGA: Variance Reduction via Gradient Sketching
• A unified variance-reduced accelerated gradient method for convex optimization
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• L-SVRG and L-Katyusha with Arbitrary Sampling
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods

Cited by in corpus (21)

• Personalized Federated Learning: A Meta-Learning Approach
• FedML: A Research Library and Benchmark for Federated Machine Learning
• FedCV: A Federated Learning Framework for Diverse Computer Vision Tasks
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Optimal Gradient Compression for Distributed and Federated Learning
• Personalized Federated Learning using Hypernetworks
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• FedEval: A Holistic Evaluation Framework for Federated Learning
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• Synthetic data shuffling accelerates the convergence of federated learning under data heterogeneity
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
• EasyFL: A Low-code Federated Learning Platform For Dummies
• An Operator Splitting View of Federated Learning
• Optimal Gradient Tracking for Decentralized Optimization
• Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization
• Towards Heterogeneous Clients with Elastic Federated Learning