Permutation Compressors for Provably Faster Distributed Nonconvex Optimization

Abstract

We study the MARINA method of Gorbunov et al (2021) -- the current state-of-the-art distributed non-convex optimization method in terms of theoretical communication complexity. Theoretical superiority of this method can be largely attributed to two sources: the use of a carefully engineered biased stochastic gradient estimator, which leads to a reduction in the number of communication rounds, and the reliance on {\em independent} stochastic communication compression operators, which leads to a reduction in the number of transmitted bits within each communication round. In this paper we i) extend the theory of MARINA to support a much wider class of potentially {\em correlated} compressors, extending the reach of the method beyond the classical independent compressors setting, ii) show that a new quantity, for which we coin the name {\em Hessian variance}, allows us to significantly refine the original analysis of MARINA without any additional assumptions, and iii) identify a special class of correlated compressors based on the idea of {\em random permutations}, for which we coin the term Perm$K$, the use of which leads to $O(\sqrt{n})$ (resp. $O(1+d/\sqrt{n})$) improvement in the theoretical communication complexity of MARINA in the low Hessian variance regime when $d\ge n$ (resp. $d\le n$), where $n$ is the number of workers and $d$ is the number of parameters describing the model we are learning. We corroborate our theoretical results with carefully engineered synthetic experiments with minimizing the average of nonconvex quadratics, and on autoencoder training with the MNIST dataset.

arXiv comment53 pages

References in corpus (15)

• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Sparsified SGD with Memory
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• Distributed Learning with Compressed Gradient Differences
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Natural Compression for Distributed Deep Learning
• Better Theory for SGD in the Nonconvex World
• On Biased Compression for Distributed Learning
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• Distributed learning with compressed gradients
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees

Cited by in corpus (1)

• Federated Learning is Better with Non-Homomorphic Encryption