MARINA: Faster Non-Convex Distributed Learning with Compression

Abstract

We develop and analyze MARINA: a new communication efficient method for non-convex distributed learning over heterogeneous datasets. MARINA employs a novel communication compression strategy based on the compression of gradient differences that is reminiscent of but different from the strategy employed in the DIANA method of Mishchenko et al. (2019). Unlike virtually all competing distributed first-order methods, including DIANA, ours is based on a carefully designed biased gradient estimator, which is the key to its superior theoretical and practical performance. The communication complexity bounds we prove for MARINA are evidently better than those of all previous first-order methods. Further, we develop and analyze two variants of MARINA: VR-MARINA and PP-MARINA. The first method is designed for the case when the local loss functions owned by clients are either of a finite sum or of an expectation form, and the second method allows for a partial participation of clients -- a feature important in federated learning. All our methods are superior to previous state-of-the-art methods in terms of oracle/communication complexity. Finally, we provide a convergence analysis of all methods for problems satisfying the Polyak-Lojasiewicz condition.

arXiv commentICML 2021; v2 contains additional experiments; v3 contains small fixes of the typos in the complexity results for online case for VR-MARINA; 42 pages, 6 figures, 3 algorithms

References in corpus (20)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• Distributed Mean Estimation with Limited Communication
• Optimization for deep learning: theory and algorithms
• Distributed Learning with Compressed Gradient Differences
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Natural Compression for Distributed Deep Learning
• On Biased Compression for Distributed Learning
• Linearly Converging Error Compensated SGD
• 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
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance Reduction

Cited by in corpus (8)

• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
• Activations and Gradients Compression for Model-Parallel Training
• Optimal Data Splitting in Distributed Optimization for Machine Learning
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Secure Distributed Training at Scale