Decentralized Learning with Lazy and Approximate Dual Gradients

Abstract

This paper develops algorithms for decentralized machine learning over a network, where data are distributed, computation is localized, and communication is restricted between neighbors. A line of recent research in this area focuses on improving both computation and communication complexities. The methods SSDA and MSDA \cite{scaman2017optimal} have optimal communication complexity when the objective is smooth and strongly convex, and are simple to derive. However, they require solving a subproblem at each step. We propose new algorithms that save computation through using (stochastic) gradients and saves communications when previous information is sufficiently useful. Our methods remain relatively simple -- rather than solving a subproblem, they run Katyusha for a small, fixed number of steps from the latest point. An easy-to-compute, local rule is used to decide if a worker can skip a round of communication. Furthermore, our methods provably reduce communication and computation complexities of SSDA and MSDA. In numerical experiments, our algorithms achieve significant computation and communication reduction compared with the state-of-the-art.

References in corpus (15)

• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
• Sparsified SGD with Memory
• Don't Use Large Mini-Batches, Use Local SGD
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• A Lyapunov Analysis of Momentum Methods in Optimization
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• COLA: Decentralized Linear Learning
• Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives
• An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach