Timezone: »

 
Poster
Lower Bounds and Optimal Algorithms for Personalized Federated Learning
Filip Hanzely · Slavomír Hanzely · Samuel Horváth · Peter Richtarik

Tue Dec 08 09:00 PM -- 11:00 PM (PST) @ Poster Session 2 #659
in Poster Session 3 »

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.

Keywords: Learning Theory · Theory

Author Information

Filip Hanzely (Toyota Technological Institute at Chicago)

Research Assistant Professor, optimization/machine learning

Slavomír Hanzely (KAUST)
Samuel Horváth (King Abdullah University of Science and Technology)
Peter Richtarik (KAUST)

More from the Same Authors