Abstract
Federated Learning (FL) often faces challenges due to data heterogeneity and the computational demands of local updates. This paper provides a new theoretical foundation for FedProx, a popular FL algorithm, demonstrating its effectiveness under more realistic conditions than previously established. By leveraging algorithmic stability, we prove convergence for non-smooth problems and introduce FedMSPP (Federated Minibatch Stochastic Proximal Point), a variant that achieves linear speedup in training. Our analysis eliminates the need for restrictive "local dissimilarity" assumptions, broadening the applicability of FedProx to highly heterogeneous real-world data.
Introduction
Federated Learning aims to train models across decentralized devices while maintaining data privacy. FedProx was designed to handle system heterogeneity by allowing inexact local updates. However, its theoretical guarantees have historically been limited by three major factors: the requirement for "local dissimilarity" (LD) assumptions, a restriction to smooth objective functions, and the high computational cost of full-batch local optimization. This work addresses these gaps by providing LD-independent bounds and extending guarantees to non-smooth, weakly convex problems.
Theoretical Framework: Algorithmic Stability
Traditional convergence proofs for FL algorithms often rely on the assumption that local data distributions are somewhat similar to the global average. In practice, data is often highly skewed. We shift the analytical lens to algorithmic stability theory, which examines how much a model changes when a single data point is modified. This approach allows us to derive convergence bounds that are invariant to local dissimilarity, proving that FedProx remains robust even when local datasets are significantly different.
FedMSPP: Scaling Federated Learning
To address the computational intensity of standard FedProx, we propose FedMSPP. This algorithm replaces the expensive full-batch local updates with efficient minibatch stochastic updates. This modification makes local computation more balanced and scalable, particularly for large-scale networks with varying device capabilities.
Convergence Results and Comparison
Our theoretical analysis establishes new benchmarks for FedProx and FedMSPP. For smooth problems, we prove that FedMSPP enjoys a "linear speedup," where increasing the minibatch size ($b$) or the number of participating devices ($I$) directly reduces the required communication rounds. Furthermore, we provide the first convergence guarantees for FedProx on non-smooth, weakly convex problems, establishing a rate of $\mathcal{O}(1/\sqrt{T})$.
As shown in the comparison table, our work (Theorems 1-4) fills critical gaps in existing literature by providing LD-independent bounds and supporting non-smooth objectives, features often missing in state-of-the-art methods like FedAvg or SCAFFOLD.
Experimental Evaluation
We evaluated our approach on standard FL benchmarks, including MNIST, FEMNIST, and Sent140. The results confirm our theoretical findings:
- Sample Efficiency: FedMSPP consistently requires fewer data points to reach target accuracies. On MNIST, it achieved 95% accuracy using significantly less data than vanilla FedProx or FedAvg.
- Communication Complexity: For smooth problems, the derived complexity of $\mathcal{O}(\frac{1}{bI\epsilon^2} + \frac{1}{\epsilon^{3/2}})$ highlights the benefits of minibatching and increased device participation.
Conclusion
This work provides a robust theoretical grounding for FedProx, proving it is more versatile than previously understood. By removing the necessity for local dissimilarity assumptions and extending support to non-smooth models, we bridge the gap between FL theory and practice. Future work will focus on achieving linear speedups for non-smooth problems and extending the experimental validation to larger architectures like Transformers.
Summary updated