Trading-off Accuracy and Communication Cost in Federated Learning

Leveraging the training-by-pruning paradigm introduced by Zhou et al. and Isik et al. introduced a federated learning protocol that achieves a 34-fold reduction in communication cost. We achieve a compression improvements of orders of orders of magnitude over the state-of-the-art. The central idea of our framework is to encode the network weights vec w by a the vector of trainable parameters vec p, such that vec w = Q· vec p where Q is a carefully-generate sparse random matrix (that remains fixed throughout training). In such framework, the previous work of Zhou et al. [NeurIPS'19] is retrieved when Q is diagonal and vec p has the same dimension of vec w. We instead show that vec p can effectively be chosen much smaller than vec w, while retaining the same accuracy at the price of a decrease of the sparsity of Q. Since server and clients only need to share vec p, such a trade-off leads to a substantial improvement in communication cost. Moreover, we provide theoretical insight into our framework and establish a novel link between training-by-sampling and random convex geometry.