A Computation and Communication Efficient Method for Distributed Nonconvex Problems in the Partial Participation Setting
We present a new method that includes three key components of distributed optimization and federated learning: variance reduction of stochastic gradients, partial participation, and compressed communication. We prove that the new method has optimal oracle complexity and state-of-the-art communication complexity in the partial participation setting. Regardless of the communication compression feature, our method successfully combines variance reduction and partial participation: we get the optimal oracle complexity, never need the participation of all nodes, and do not require the bounded gradients (dissimilarity) assumption.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationFederated LearningSimilar Papers 제목 키워드 기반
Communication-Efficient Stochastic Distributed Learning
We address distributed learning problems, both nonconvex and convex, over undirected networks. In particular, we design a novel algorithm based on the distributed Alternating Direction Method of Multipliers (ADMM) to add…
A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
This paper proposes and analyzes a communication-efficient distributed optimization framework for general nonconvex nonsmooth signal processing and machine learning problems under an asynchronous protocol. At each iterat…
Distributed OptimizationDistributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
While many distributed optimization algorithms have been proposed for solving smooth or convex problems over the networks, few of them can handle non-convex and non-smooth problems. Based on a proximal primal-dual approa…
Distributed OptimizationShadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity
We consider nonconvex stochastic optimization problems in the asynchronous centralized distributed setup where the communication times from workers to a server can not be ignored, and the computation and communication ti…
Stochastic OptimizationLocal Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
Local SGD is a promising approach to overcome the communication overhead in distributed learning by reducing the synchronization frequency among worker nodes. Despite the recent theoretical advances of local SGD in empir…