A Computation and Communication Efficient Method for Distributed Nonconvex Problems in the Partial Participation Setting

05/31/2022
by   Alexander Tyurin, et al.
7

We present a new method that includes three key components of distributed optimization and federated learning: variance reduction of stochastic gradients, compressed communication, and partial participation. We prove that the new method has optimal oracle complexity and state-of-the-art communication complexity in the partial participation setting. Moreover, we observe that "1 + 1 + 1 is not 3": by mixing variance reduction of stochastic gradients with compressed communication and partial participation, we do not obtain a fully synergetic effect. We explain the nature of this phenomenon, argue that this is to be expected, and propose possible workarounds.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset