Abstract
This paper addresses the challenge of achieving optimal convergence rates in private Federated Learning (FL) without sacrificing computational efficiency. By adapting the $\mu^2$-SGD double-momentum mechanism to the Stochastic Convex Optimization (SCO) framework, the authors introduce a method that achieves optimal population loss guarantees with linear computational complexity ($O(|S|)$). This work bridges the gap between theoretical optimality and practical scalability in both trusted and untrusted server environments.
Introduction
Federated Learning (FL) enables collaborative model training across decentralized devices while preserving data locality. However, model updates can still leak sensitive information, necessitating the use of Differential Privacy (DP). The primary hurdle in DP-SCO has been the "Privacy-Utility-Efficiency" triangle: previous state-of-the-art methods achieving optimal accuracy often required super-linear computational complexity ($O(n^{1.5})$), making them impractical for large-scale datasets. This research presents a framework that overcomes these limitations, providing a linear-time solution that maintains high utility.
Methodology
The core innovation lies in the adaptation of the $\mu^2$-SGD algorithm to the federated setting. $\mu^2$-SGD utilizes a double-momentum mechanism that employs a corrected momentum estimate for gradients.
Sensitivity Reduction via Momentum
A key theoretical insight is that the specific momentum approach in $\mu^2$-SGD reduces the sensitivity of the algorithm to individual data points. In the context of DP, lower sensitivity allows for the addition of less noise to achieve a target privacy level ($\epsilon$), thereby improving model accuracy. The authors prove that variance reduction techniques do not just assist convergence speed but inherently "smooth out" the influence of individual samples.
Deployment Scenarios
The framework considers two primary trust models:
- Untrusted Server: Clients apply local DP noise to their updates before transmission. The error term scales as $O\left(\frac{1}{\sqrt{nM}} + \frac{\sqrt{d}}{\epsilon n \sqrt{M}}\right)$.
- Trusted Server: The central aggregator collects clean updates and adds noise globally before broadcasting. The error term scales as $O\left(\frac{1}{\sqrt{nM}} + \frac{\sqrt{d}}{\epsilon nM}\right)$.
Unlike prior optimal methods, this approach requires only a single pass over the data per iteration, ensuring $O(|S|)$ complexity.
Experimental Results
The authors validated their theoretical findings using a logistic regression model on the MNIST dataset. The experiments confirmed that the proposed method maintains high accuracy even under strict privacy budgets.
As shown in Table 1, the DP-$\mu^2$-SGD algorithm demonstrates robust performance in the untrusted server setting. While accuracy slightly decreases as the number of machines ($M$) increases for a fixed total sample size ($M \times T = 60,000$), the results remain competitive. The empirical data confirms that as the privacy parameter $\rho$ increases, the model achieves higher accuracy, reaching up to 70.4% in the single-machine baseline. The results substantiate the theoretical prediction that the trusted server model significantly outperforms the untrusted one as $M$ grows, due to the faster-shrinking privacy error term.
Conclusion
This work refutes the assumption that super-linear complexity is necessary for optimal DP-SCO. By leveraging variance reduction through momentum, the authors provide a scalable and private FL framework. Future research may explore extending these efficiency gains to non-convex deep learning models and investigating the "trusted shuffler" model to further optimize the privacy-utility trade-off.
Summary updated