Lower bounds and optimal algorithms for personalized federated learning

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

Research output: Contribution to conferencePaperpeer-review

61 Scopus citations

Abstract

In this work, we consider the optimization formulation of personalized federated learning recently introduced by [19] 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.

Original languageEnglish (US)
StatePublished - 2020
Event34th Conference on Neural Information Processing Systems, NeurIPS 2020 - Virtual, Online
Duration: Dec 6 2020Dec 12 2020

Conference

Conference34th Conference on Neural Information Processing Systems, NeurIPS 2020
CityVirtual, Online
Period12/6/2012/12/20

Bibliographical note

Funding Information:
All authors were supported by the KAUST Baseline Research Scheme, and are thankful to support offered by the KAUST Visual Computing Center.

Publisher Copyright:
© 2020 Neural information processing systems foundation. All rights reserved.

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint

Dive into the research topics of 'Lower bounds and optimal algorithms for personalized federated learning'. Together they form a unique fingerprint.

Cite this