Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses

This paper studies the problem of federated learning (FL) in the absence of a trustworthy server/clients. In this setting, each client needs to ensure the privacy of its own data, even if the server or other clients act adversarially. This requirement motivates the study of local differential privacy (LDP) at the client level. We provide tight (up to logarithms) upper and lower bounds for LDP convex/strongly convex federated stochastic optimization with homogeneous (i.i.d.) client data. The LDP rates match the optimal statistical rates in certain practical parameter regimes ("privacy for free"). Remarkably, we show that similar rates are attainable for smooth losses with arbitrary heterogeneous client data distributions, via a linear-time accelerated LDP algorithm. We also provide tight upper and lower bounds for LDP federated empirical risk minimization (ERM). While a tight upper bound for ERM was provided in prior work, we use acceleration to attain this bound in fewer rounds of communication. Finally, with a secure "shuffler" to anonymize client reports (but without the presence of a trusted server), our algorithm attains the optimal central differentially private rates for stochastic convex/strongly convex optimization. Numerical experiments validate our theory and show favorable privacy-accuracy tradeoffs for our algorithm.