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

In this paper, we consider the formulation of the federated learning problem that is relevant to both decentralized personalized federated learning and multi-task learning. This formulation is widespread in the literature and represents the minimization of local losses with regularization taking into account the communication matrix of the network. First of all, we give lower bounds for the considered problem in different regularization regimes. We also constructed an optimal algorithm that matches these lower bounds. Additionally, we check the theoretical results with experiments.