On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond

Xiaotong Yuan, Ping Li

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})$.

Table 1: Comparison of Federated Learning algorithms. The authors' results (Theorems 1-4) demonstrate independence from local dissimilarity (LD) and support for non-smooth (NS) functions.

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

Abstract

The \FedProx~algorithm is a simple yet powerful distributed proximal point optimization method widely used for federated learning (FL) over heterogeneous data. Despite its popularity and remarkable success witnessed in practice, the theoretical understanding of FedProx is largely underinvestigated: the appealing convergence behavior of \FedProx~is so far characterized under certain non-standard and unrealistic dissimilarity assumptions of local functions, and the results are limited to smooth optimization problems. In order to remedy these deficiencies, we develop a novel local dissimilarity invariant convergence theory for \FedProx~and its minibatch stochastic extension through the lens of algorithmic stability. As a result, we contribute to derive several new and deeper insights into \FedProx~for non-convex federated optimization including: 1) convergence guarantees invariant to certain stringent local dissimilarity conditions; 2) convergence guarantees for non-smooth FL problems; and 3) linear speedup with respect to size of minibatch and number of sampled devices. Our theory for the first time reveals that local dissimilarity and smoothness are not must-have for \FedProx~to get favorable complexity bounds.
BibTeX
@inproceedings{yuan2022convergence,
  author = {Xiaotong Yuan and Ping Li},
  title = {{On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=_33ynl9VgCX},
}
Figure