Linear Convergence of Decentralized FedAvg for PL Objectives: The Interpolation Regime

Abstract

Federated Learning (FL) is a distributed learning paradigm where multiple clients each having access to a local dataset collaborate to solve a joint problem. Federated Averaging (FedAvg) the algorithm of choice has been widely explored in the classical {\em server} setting where the server coordinates the information sharing among clients. However, the performance of FedAvg in the {\em decentralized} setting where only the neighboring clients communicate with each other depending on the network topology is not well understood, especially in the interpolation regime, a common phenomenon observed in modern overparameterized neural networks. In this work, we address this challenge and perform a thorough theoretical performance analysis of FedAvg in the interpolation regime under {\em decentralized} setting. We consider a class of non-convex functions satisfying the Polyak-{\L}ojasiewicz (PL) inequality, a condition satisfied by overparameterized neural networks. For the first time, we establish that {\em Decentralized} FedAvg achieves linear convergence rates of $\mathcal{O}({T^2} \log ({1}/{\epsilon}))$, where $\epsilon$ is the solution accuracy, and $T$ is the number of local updates at each client. We also extend our analysis to the classical {\em Server} FedAvg and establish a convergence rate of $\mathcal{O}(\log ({1}/{\epsilon}))$ which significantly improves upon the best-known rates for the simpler strongly-convex setting. In contrast to the standard FedAvg analyses, our work does not require bounded heterogeneity and gradient assumptions. Instead, we show that sample-wise (and local) smoothness of the local objectives suffice to capture the effect of heterogeneity. Experiments on multiple real datasets corroborate our theoretical findings.