Decentralized Personalized Federated Learning: Lower Bounds and Optimal Algorithm For All Personalization Modes

Abdurakhmon Sadiev, Moscow Institute of Physics and Technology & Mohamed bin Zayed University of Artificial Intelligence
Ekaterina Borodich, Moscow Institute of Physics and Technology & HSE University, Russia
Aleksandr Beznosikov, Moscow Institute of Physics and Technology & Mohamed bin Zayed University of Artificial Intelligence & HSE University, Russia
Darina Dvinskikh, Moscow Institute of Physics and Technology & Mohamed bin Zayed University of Artificial Intelligence & Institute for Information Transmission Problems, Russia
Rachael Chezhegov, Moscow Institute of Physics and Technology, Russia
E.H. Tappenden, University of Canterbury, New Zealand
Martin Takáč, Mohamed bin Zayed University of Artificial Intelligence
Alexander V. Gasnikov, Moscow Institute of Physics and Technology, Russia & Mohamed bin Zayed University of Artificial Intelligence & HSE University, Russia

Archived with thanks to ScienceDirect

License: CC by NC-ND 4.0

Uploaded 03 November 2022

IR Deposit conditions:

OA version (pathway b) Accepted version

License: CC BY-NC-ND

No embargo

Published source must be acknowledged

Must link to publisher version with DOI

Abstract

This paper considers the problem of decentralized, personalized federated learning. For centralized personalized federated learning, a penalty that measures the deviation from the local model and its average, is often added to the objective function. However, in a decentralized setting this penalty is expensive in terms of communication costs, so here, a different penalty — one that is built to respect the structure of the underlying computational network — is used instead. We present lower bounds on the communication and local computation costs for this problem formulation and we also present provably optimal methods for decentralized personalized federated learning. Numerical experiments are presented to demonstrate the practical performance of our methods. © 2022 The Authors