Lower Bounds and Optimal Algorithms for Personalized Federated Learning
Filip Hanzely, Slavomír Hanzely, Samuel Horváth, Peter Richtarik
Abstract
In this work, we consider the optimization formulation of personalized federated learning recently introduced by Hanzely & Richtarik (2020) which was shown to give an alternative explanation to the workings of local SGD methods. Our first contribution is establishing the first lower bounds for this formulation, for both the communication complexity and the local oracle complexity. Our second contribution is the design of several optimal methods matching these lower bounds in almost all regimes. These are the first provably optimal methods for personalized federated learning. Our optimal methods include an accelerated variant of FedProx, and an accelerated variance-reduced version of FedAvg/Local SGD. We demonstrate the practical superiority of our methods through extensive numerical experiments.
BibTeX
@inproceedings{NEURIPS2020_187acf79,
author = {Hanzely, Filip and Hanzely, Slavom\'{\i}r and Horv\'{a}th, Samuel and Richtarik, Peter},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {2304--2315},
publisher = {Curran Associates, Inc.},
title = {Lower Bounds and Optimal Algorithms for Personalized Federated Learning},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/187acf7982f3c169b3075132380986e4-Paper.pdf},
volume = {33},
year = {2020}
}