Lower Bounds and Optimal Algorithms for Personalized Federated Learning

By Filip Hanzely, Slavomír Hanzely, Samuel Horváth, Peter Richtárik. 2020

214 citations recorded by the source corpus.

In this work, we consider the optimization formulation of personalized federated learning recently introduced by Hanzely and Richtarik (2020) which was shown to give an alternative explanation to the workings of local {\tt 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 {\tt FedProx}, and an accelerated variance-reduced version of {\tt FedAvg}/Local {\tt SGD}. We demonstrate the practical superiority of our methods through extensive numerical experiments.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Bingsheng He
2. Qinbin Li
3. Tianyi Zhou
4. Guodong Long
5. Jing Jiang
6. Tian Li
7. Zeyi Wen
8. Zhaomin Wu

Citations in the corpus

• Federated Multi-Task Learning under a Mixture of Distributions (2021, methodology): “Other MTL-based approaches [24, 23, 16, 26, 36] are able to train more general models at the cost of considering simpler penalization terms (e.”
• Federated Learning from Pre-Trained Models: A Contrastive Learning Approach (2022, background): “[27, 28, 29] add an additional term to the original loss function of each client to produce better personalized models according to the private data.”
• Model-Contrastive Federated Learning (2021, background): “Another research direction is personalized federated learning [8, 7, 10, 47, 17], which tries to learn personalized local models for each party.”
• A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection (2019, methodology): “[69] establish the lower bound for the communication complexity and local oracle complexity of the personalized federated learning optimization.”
• Ditto: Fair and Robust Federated Learning Through Personalization (2020, background): “The most closely related works are those that regularize personalized models towards their average (Hanzely & Richtárik, 2020; Hanzely et al., 2020; Dinh et al., 2020), which can be seen as a form of classical mean-regularized MTL (Evgeniou & Pontil, 2004).”
• Federated Learning on Non-IID Data Silos: An Experimental Study (2021, background): “There are also other FL studies related to nonIID data setting, such as personalizing the local models for each party [10, 12, 19] and designing robust algorithms against different combinations of local distributions [8, 49, 53], which are out of the scope of this paper.”