Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping

Abstract

Distributed learning has become an integral tool for scaling up machine learning and addressing the growing need for data privacy. Although more robust to the network topology, decentralized learning schemes have not gained the same level of popularity as their centralized counterparts for being less competitive performance-wise. In this work, we attribute this issue to the lack of synchronization among decentralized learning workers, showing both empirically and theoretically that the convergence rate is tied to the synchronization level among the workers. Such motivated, we present a novel decentralized learning framework based on nonlinear gossiping (NGO), that enjoys an appealing finite-time consensus property to achieve better synchronization. We provide a careful analysis of its convergence and discuss its merits for modern distributed optimization applications, such as deep neural networks. Our analysis on how communication delay and randomized chats affect learning further enables the derivation of practical variants that accommodate asynchronous and randomized communications. To validate the effectiveness of our proposal, we benchmark NGO against competing solutions through an extensive set of tests, with encouraging results reported.

References in corpus (23)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• An overview of gradient descent optimization algorithms
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Speeding Up Distributed Machine Learning Using Codes
• Spontaneous synchrony in power-grid networks
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• On Lazy Training in Differentiable Programming
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Communication Compression for Decentralized Training
• Byzantine Stochastic Gradient Descent
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Asynchronous Stochastic Gradient Descent with Delay Compensation
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Communication-Computation Efficient Gradient Coding
• Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
• Distributed Learning over Unreliable Networks
• Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Variational Inference with Holder Bounds

Cited by in corpus (1)

• Variational Inference with Holder Bounds