On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization

Abstract

In decentralized optimization, it is common algorithmic practice to have nodes interleave (local) gradient descent iterations with gossip (i.e. averaging over the network) steps. Motivated by the training of large-scale machine learning models, it is also increasingly common to require that messages be {\em lossy compressed} versions of the local parameters. In this paper, we show that, in such compressed decentralized optimization settings, there are benefits to having {\em multiple} gossip steps between subsequent gradient iterations, even when the cost of doing so is appropriately accounted for e.g. by means of reducing the precision of compressed information. In particular, we show that having $O(\log \frac{1}{\epsilon })$ gradient iterations {with constant step size} - and $O(\log \frac{1}{\epsilon })$ gossip steps between every pair of these iterations - enables convergence to within $\epsilon$ of the optimal value for smooth non-convex objectives satisfying Polyak-Łojasiewicz condition. This result also holds for smooth strongly convex objectives. To our knowledge, this is the first work that derives convergence results for nonconvex optimization under arbitrary communication compression.

References in corpus (17)

• 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
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Sparsified SGD with Memory
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Communication Compression for Decentralized Training
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Stochastic Gradient Push for Distributed Deep Learning
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• Communication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradients
• COLA: Decentralized Linear Learning
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• Projected Gradient Method for Decentralized Optimization over Time-Varying Networks
• Linear Convergence of First- and Zeroth-Order Primal-Dual Algorithms for Distributed Nonconvex Optimization

Cited by in corpus (1)

• Faster Non-Convex Federated Learning via Global and Local Momentum