# Lower Bounds and Optimal Algorithms for Personalized Federated Learning

arXiv: https://arxiv.org/abs/2010.02372 · HTML: https://mlsanity.com/paper/2010.02372/

## Key facts

- Cited by 123 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2020.

## Built on by (most cited first, 30 of 123)

- [Model-Contrastive Federated Learning](https://mlsanity.com/paper/2103.16257/) (2021)
- [Federated Learning on Non-IID Data Silos: An Experimental Study](https://mlsanity.com/paper/2102.02079/) (2021)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Federated Multi-Task Learning under a Mixture of Distributions](https://mlsanity.com/paper/2108.10252/) (2021)
- [Federated Learning from Pre-Trained Models: A Contrastive Learning Approach](https://mlsanity.com/paper/2209.10083/) (2022)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Parameterized Knowledge Transfer for Personalized Federated Learning](https://mlsanity.com/paper/2111.02862/) (2021)
- [FedProc: Prototypical Contrastive Federated Learning on Non-IID data](https://mlsanity.com/paper/2109.12273/) (2021)
- [FedCM: Federated Learning with Client-level Momentum](https://mlsanity.com/paper/2106.10874/) (2021)
- [Divergence-aware Federated Self-Supervised Learning](https://mlsanity.com/paper/2204.04385/) (2022)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [Personalized Federated Learning through Local Memorization](https://mlsanity.com/paper/2111.09360/) (2021)
- [Towards Understanding and Mitigating Dimensional Collapse in Heterogeneous Federated Learning](https://mlsanity.com/paper/2210.00226/) (2022)
- [pFL-Bench: A Comprehensive Benchmark for Personalized Federated Learning](https://mlsanity.com/paper/2206.03655/) (2022)
- [Recent Advances on Federated Learning: A Systematic Survey](https://mlsanity.com/paper/2301.01299/) (2023)
- [Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective](https://mlsanity.com/paper/2111.03741/) (2021)
- [On Privacy and Personalization in Cross-Silo Federated Learning](https://mlsanity.com/paper/2206.07902/) (2022)
- [FedPop: A Bayesian Approach for Personalised Federated Learning](https://mlsanity.com/paper/2206.03611/) (2022)
- [Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques](https://mlsanity.com/paper/2102.09743/) (2021)
- [QuPeD: Quantized Personalization via Distillation with Applications to Federated Learning](https://mlsanity.com/paper/2107.13892/) (2021)
- [Motley: Benchmarking Heterogeneity and Personalization in Federated Learning](https://mlsanity.com/paper/2206.09262/) (2022)
- [FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization](https://mlsanity.com/paper/2103.03452/) (2021)
- [Federated Adaptive Prompt Tuning for Multi-Domain Collaborative Learning](https://mlsanity.com/paper/2211.07864/) (2022)
- [On the Impossible Safety of Large AI Models](https://mlsanity.com/paper/2209.15259/) (2022)
- [A New Look and Convergence Rate of Federated Multi-Task Learning with Laplacian Regularization](https://mlsanity.com/paper/2102.07148/) (2021)
- [Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity](https://mlsanity.com/paper/2302.02212/) (2023)
- [Differentially Private Label Protection in Split Learning](https://mlsanity.com/paper/2203.02073/) (2022)
- [The Best of Both Worlds: Accurate Global and Personalized Models through Federated Learning with Data-Free Hyper-Knowledge Distillation](https://mlsanity.com/paper/2301.08968/) (2023)
- [Personalized Federated Learning with Contextualized Generalization](https://mlsanity.com/paper/2106.13044/) (2021)
- [DYNAFED: Tackling Client Data Heterogeneity with Global Dynamics](https://mlsanity.com/paper/2211.10878/) (2022)

## Abstract (arXiv)

In this work, we consider the optimization formulation of personalized federated learning recently introduced by Hanzely and Richt'arik (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.