Optimal Complexity in Decentralized Training
Decentralization is a promising method of scaling up parallel machine learning systems. In this paper, we provide a tight lower bound on the iteration complexity for such methods in a stochastic non-convex setting. Our lower bound reveals a theoretical gap in known convergence rates of many existing decentralized training algorithms, such as D-PSGD. We prove by construction this lower bound is tight and achievable. Motivated by our insights, we further propose DeTAG, a practical gossip-style decentralized algorithm that achieves the lower bound with only a logarithm gap. Empirically, we compare DeTAG with other decentralized algorithms on image classification tasks, and we show DeTAG enjoys faster convergence compared to baselines, especially on unshuffled data and in sparse networks.
Code (0)
등록된 구현이 없습니다.
Tasks
image-classificationImage ClassificationSimilar Papers 제목 키워드 기반
Decentralized Accelerated Proximal Gradient Descent
Decentralized optimization has wide applications in machine learning, signal processing, and control. In this paper, we study the decentralized composite optimization problem with a non-smooth regularization term…
BIG-bench Machine LearningOptimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networks
Decentralized optimization with time-varying networks is an emerging paradigm in machine learning. It saves remarkable communication overhead in large-scale deep training and is more robust in wireless scenarios especial…
Federated LearningStochastic OptimizationFaster Adaptive Decentralized Learning Algorithms
Decentralized learning recently has received increasing attention in machine learning due to its advantages in implementation simplicity and system robustness, data privacy. Meanwhile, the adaptive gradient methods show …
Stochastic OptimizationNear-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise
This paper studies decentralized stochastic nonconvex optimization problem over row-stochastic networks. We consider the heavy-tailed gradient noise which is empirically observed in many popular real-world applications. …
Decentralized and Equitable Optimal Transport
This paper considers the decentralized (discrete) optimal transport (D-OT) problem. In this setting, a network of agents seeks to design a transportation plan jointly, where the cost function is the sum of privately held…