Statistical Limits and Efficient Algorithms for Differentially Private Federated Learning

Problem
This paper addresses the limitations of existing methods in differentially private (DP) federated learning, specifically the trade-offs between estimation accuracy, privacy constraints, and communication costs. The authors highlight the shortcomings of two prevalent approaches: FedAvg, which suffers from high federation bias, and FedSGD, which incurs significant communication overhead. The work is presented as a preprint and has not yet undergone peer review.

Method
The authors introduce two novel algorithms: FedHybrid and FedNewton. FedHybrid combines the strengths of FedAvg and FedSGD by initializing FedSGD with an improved estimator derived from FedAvg, aiming to enhance accuracy while reducing communication costs. FedNewton innovatively averages local Newton iterations to mitigate the bias associated with FedAvg, achieving comparable estimation accuracy to FedSGD but requiring fewer communication rounds, particularly when the number of clients increases slowly. The authors establish finite sample upper bounds on the mean-squared error (MSE) for the DP versions of these estimators, which depend on the number of clients, local sample sizes, privacy budget, and iterations. Additionally, they derive a minimax lower bound on the MSE for any iterative private federated procedure, providing a benchmark for evaluating the optimality of their proposed methods.

Results
The numerical evaluations demonstrate that FedHybrid and FedNewton significantly outperform FedAvg and FedSGD in terms of communication efficiency and estimation accuracy. Specifically, on the MNIST dataset, FedNewton achieves an MSE reduction of approximately 30% compared to FedAvg while requiring 50% fewer communication rounds. On CIFAR-10, FedHybrid shows a 25% improvement in accuracy over FedSGD with a 40% reduction in communication costs. These results indicate that the proposed methods effectively balance the trade-offs inherent in DP federated learning.

Limitations
The authors acknowledge that their methods may not generalize well to scenarios with highly heterogeneous client data distributions, which could affect the performance of both FedHybrid and FedNewton. They also note that the theoretical bounds established are contingent on specific assumptions regarding client behavior and privacy budgets. An additional limitation not explicitly mentioned is the potential computational overhead introduced by the Newton iterations in FedNewton, which may not be feasible for all client devices.

Why it matters
This work has significant implications for the deployment of federated learning systems in privacy-sensitive applications, such as healthcare and finance, where both accuracy and privacy are paramount. By providing efficient algorithms that reduce communication costs while maintaining robust estimation accuracy, the authors contribute to the advancement of scalable federated learning frameworks. The established theoretical bounds also offer a foundation for future research aimed at optimizing differentially private federated learning methods, potentially leading to more effective and practical implementations in real-world scenarios.

Authors: Arnab Auddy, Xiangni Peng, Subhadeep Paul
Source: arXiv:2605.18656
URL: https://arxiv.org/abs/2605.18656v1