On the Minimax Excess Risk and $O(1)$-Communication Algorithm for Federated Learning under Statistical Heterogeneity

We study the minimax excess risk in federated learning (FL) with strongly convex and smooth loss functions under statistical heterogeneity. Previous work established a minimax excess risk lower bound that depends on the degree of statistical heterogeneity, but leaves large gaps with existing upper bounds in terms of problem-dependent parameters. In this work, we establish sharper lower bounds, which improve previous lower bound by $O({\mu }^{-2})$ in the stochastic gradient regime where $\mu$ is strong convexity constant, is applicable to the exact gradient regime, and match existing upper bounds, resolving an open problem raised by Chen2023Minimax. We also design a two-stage FL algorithm that is nearly optimal and only requires a $O(\kappa \ln M)$ communication rounds where $\kappa$ is the condition number and $M$ is the number of clients, while previous algorithms require a $O(T)$ communication rounds where $T$ is the local sample size. The lower bound analysis requires a non-trivial extension of the local Fano's method proposed for the minimax risk analysis of centralized learning to deal with FL. The algorithmic novelties include a multistage stochastic gradient and a two-stage federated training strategy coupled with a model initialization scheme. Our results fully characterize the condition under which FL is better than non-cooperative learning, showing its advantages and limitations. Our algorithm provides a simple and communication-efficient FL framework that holds independent interest.