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

arXiv: https://arxiv.org/abs/2206.05187 · HTML: https://mlsanity.com/paper/2206.05187/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 65 references that are in the map.
- First posted on arXiv 10 Jun 2022.

## Builds on (most cited first, 30 of 40)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [FedSplit: An algorithmic framework for fast federated optimization](https://mlsanity.com/paper/2005.05238/) (2020)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Variance Reduced Local SGD with Lower Communication Complexity](https://mlsanity.com/paper/1912.12844/) (2019)
- [FedDANE: A Federated Newton-Type Method](https://mlsanity.com/paper/2001.01920/) (2020)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [Fast-Convergent Federated Learning](https://mlsanity.com/paper/2007.13137/) (2020)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Federated Composite Optimization](https://mlsanity.com/paper/2011.08474/) (2020)
- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Training Keyword Spotting Models on Non-IID Data with Federated Learning](https://mlsanity.com/paper/2005.10406/) (2020)
- [FedCV: A Federated Learning Framework for Diverse Computer Vision Tasks](https://mlsanity.com/paper/2111.11066/) (2021)
- [Toward Communication Efficient Adaptive Gradient Method](https://mlsanity.com/paper/2109.05109/) (2021)

## Built on by (most cited first, 30 of 38)

- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [Understanding Generalization of Federated Learning via Stability: Heterogeneity Matters](https://mlsanity.com/paper/2306.03824/) (2023)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [LCFed: An Efficient Clustered Federated Learning Framework for Heterogeneous Data](https://mlsanity.com/paper/2501.01850/) (2025)
- [Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailability](https://mlsanity.com/paper/2409.17446/) (2024)
- [Sporadic Federated Learning Approach in Quantum Environment to Tackle Quantum Noise](https://mlsanity.com/paper/2507.12492/) (2025)
- [Mitigating Catastrophic Forgetting with Adaptive Transformer Block Expansion in Federated Fine-Tuning](https://mlsanity.com/paper/2506.05977/) (2025)
- [Towards Bias Correction of FedAvg over Nonuniform and Time-Varying Communications](https://mlsanity.com/paper/2306.00280/) (2023)
- [Federated Learning for Cyber Physical Systems: A Comprehensive Survey](https://mlsanity.com/paper/2505.04873/) (2025)
- [Federated Learning in the Presence of Adversarial Client Unavailability](https://mlsanity.com/paper/2305.19971/) (2023)
- [Adaptive Parameterization of Deep Learning Models for Federated Learning](https://mlsanity.com/paper/2302.02949/) (2023)
- [Empowering Federated Learning with Implicit Gossiping: Mitigating Connection Unreliability Amidst Unknown and Arbitrary Dynamics](https://mlsanity.com/paper/2404.10091/) (2024)
- [SPAM: Stochastic Proximal Point Method with Momentum Variance Reduction for Non-convex Cross-Device Federated Learning](https://mlsanity.com/paper/2405.20127/) (2024)
- [Unity is Power: Semi-Asynchronous Collaborative Training of Large-Scale Models with Structured Pruning in Resource-Limited Clients](https://mlsanity.com/paper/2410.08457/) (2024)
- [FedSC: Federated Learning with Semantic-Aware Collaboration](https://mlsanity.com/paper/2506.21012/) (2025)
- [On the Convergence of Federated Learning Algorithms without Data Similarity](https://mlsanity.com/paper/2403.02347/) (2024)
- [Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learning](https://mlsanity.com/paper/2406.01115/) (2024)
- [IPMN Risk Assessment under Federated Learning Paradigm](https://mlsanity.com/paper/2411.05697/) (2024)
- [FLARE: A Wireless Side-Channel Fingerprinting Attack on Federated Learning](https://mlsanity.com/paper/2512.10296/) (2025)
- [FedSPDnet: Geometry-Aware Federated Deep Learning with SPDnet](https://mlsanity.com/paper/2604.22494/) (2026)
- [Balancing Privacy and Performance for Private Federated Learning Algorithms](https://mlsanity.com/paper/2304.05127/) (2023)
- [UFed-GAN: A Secure Federated Learning Framework with Constrained Computation and Unlabeled Data](https://mlsanity.com/paper/2308.05870/) (2023)
- [A Theoretical Analysis of Efficiency Constrained Utility-Privacy Bi-Objective Optimization in Federated Learning](https://mlsanity.com/paper/2312.16554/) (2023)
- [PAFedFV: Personalized and Asynchronous Federated Learning for Finger Vein Recognition](https://mlsanity.com/paper/2404.13237/) (2024)
- [FedSat: A Statistical Aggregation Approach for Class Imbalanced Clients in Federated Learning](https://mlsanity.com/paper/2407.03862/) (2024)
- [Universally Harmonizing Differential Privacy Mechanisms for Federated Learning: Boosting Accuracy and Convergence](https://mlsanity.com/paper/2407.14710/) (2024)
- [Noise Resilient Over-The-Air Federated Learning In Heterogeneous Wireless Networks](https://mlsanity.com/paper/2503.19549/) (2025)
- [An LLM-Empowered Low-Resolution Vision System for On-Device Human Behavior Understanding](https://mlsanity.com/paper/2505.01743/) (2025)
- [FedSKC: Federated Learning with Non-IID Data via Structural Knowledge Collaboration](https://mlsanity.com/paper/2505.18981/) (2025)
- [GFPL: Generative Federated Prototype Learning for Resource-Constrained and Data-Imbalanced Vision Task](https://mlsanity.com/paper/2602.21873/) (2026)

## Abstract (arXiv)

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 independent on local dissimilarity type 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. Preliminary experimental results on a series of benchmark FL datasets are reported to demonstrate the benefit of minibatching for improving the sample efficiency of FedProx.