Gradient Descent with Compressed Iterates

Abstract

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.

NeurIPS 2019 Workshop on Federated Learning for Data Privacy and Confidentiality. 10 pages, 1 algorithm, 1 theorem, 5 lemmas