Skip to yearly menu bar Skip to main content


Lower Bounds and Optimal Algorithms for Personalized Federated Learning

Filip Hanzely · Slavomír Hanzely · Samuel Horváth · Peter Richtarik

Poster Session 2 #659

Keywords: [ Learning Theory ] [ Theory ]


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.

Chat is not available.