Gradient Descent with Compressed Iterates
This work addresses communication bottlenecks in federated learning for mobile devices, but it is incremental as it builds on existing compression techniques.
The paper tackles the problem of communication efficiency in federated learning by proposing gradient descent with compressed iterates (GDCI), which compresses the model before each gradient step, achieving a convergence rate that matches uncompressed methods under certain conditions.
We propose and analyze a new type of stochastic first order method: gradient descent with compressed iterates (GDCI). GDCI in each iteration first compresses the current iterate using a lossy randomized compression technique, and subsequently takes a gradient step. This method is a distillation of a key ingredient in the current practice of federated learning, where a model needs to be compressed by a mobile device before it is sent back to a server for aggregation. Our analysis provides a step towards closing the gap between the theory and practice of federated learning, and opens the possibility for many extensions.