mlsanityData to 13 Oct 2026

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

arXiv 2206.05187 ↗First posted 10 Jun 2022stat.ML cs.LGcited by 38

Not on the map. Why?

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.

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

Builds on

40 of 65 references.

References · 40

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,653
  2. 2018Federated Optimization in Heterogeneous Networkscited by 2,981
  3. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,538
  4. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,470
  5. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,227
  6. 2020Adaptive Federated Optimizationcited by 1,041
  7. 2018Local SGD Converges Fast and Communicates Littlecited by 601
  8. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 563
  9. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 549
  10. 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 278
  11. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  12. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
28 more
  1. 2018Stochastic model-based minimization of weakly convex functionscited by 158
  2. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  3. 2018Protection Against Reconstruction and Its Applications in Private Federated Learningcited by 129
  4. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  5. 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
  6. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  7. 2019Sharper bounds for uniformly stable algorithmscited by 92
  8. 2019Variance Reduced Local SGD with Lower Communication Complexitycited by 80
  9. 2020FedDANE: A Federated Newton-Type Methodcited by 76
  10. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
  11. 2020Fast-Convergent Federated Learningcited by 61
  12. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  13. 2020Federated Composite Optimizationcited by 49
  14. 2021STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learningcited by 43
  15. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  16. 2020Training Keyword Spotting Models on Non-IID Data with Federated Learningcited by 36
  17. 2021FedCV: A Federated Learning Framework for Diverse Computer Vision Taskscited by 32
  18. 2021Toward Communication Efficient Adaptive Gradient Methodcited by 25
  19. 2018PAC-Bayes bounds for stable algorithms with instance-dependent priorscited by 21
  20. 2020FedSKETCH: Communication-Efficient and Private Federated Learning via Sketchingcited by 20
  21. 2022On Distributed Adaptive Optimization with Gradient Compressioncited by 19
  22. 2021On the Convergence of Decentralized Adaptive Gradient Methodscited by 17
  23. 2017Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Proxcited by 12
  24. 2020Federated Nonconvex Sparse Learningcited by 10
  25. 2021Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimizationcited by 10
  26. 2021On Addressing Heterogeneity in Federated Learning for Autonomous Vehicles Connected to a Drone Orchestratorcited by 6
  27. 2022Communication-Efficient TeraByte-Scale Model Training Framework for Online Advertisingcited by 5
  28. 2022Boosting the Confidence of Generalization for L2-Stable Randomized Learning Algorithmscited by 3

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2022: 1; 2023: 8; 2024: 11; 2025: 12; 2026: 6.

38 papers.

Sort:

By area:

  1. 2023Stochastic Controlled Averaging for Federated Learning with Communication Compressioncited by 100
  2. 2023Understanding Generalization of Federated Learning via Stability: Heterogeneity Matterscited by 27
  3. 2022Faster federated optimization under second-order similaritycited by 18
  4. 2025LCFed: An Efficient Clustered Federated Learning Framework for Heterogeneous Datacited by 15
  5. 2024Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailabilitycited by 9
  6. 2025Sporadic Federated Learning Approach in Quantum Environment to Tackle Quantum Noisecited by 8
  7. 2025Mitigating Catastrophic Forgetting with Adaptive Transformer Block Expansion in Federated Fine-Tuningcited by 7
  8. 2023Towards Bias Correction of FedAvg over Nonuniform and Time-Varying Communicationscited by 6
  9. 2025Federated Learning for Cyber Physical Systems: A Comprehensive Surveycited by 6
  10. 2023Federated Learning in the Presence of Adversarial Client Unavailabilitycited by 5
  11. 2023Adaptive Parameterization of Deep Learning Models for Federated Learningcited by 3
  12. 2024Empowering Federated Learning with Implicit Gossiping: Mitigating Connection Unreliability Amidst Unknown and Arbitrary Dynamicscited by 3
26 more
  1. 2024SPAM: Stochastic Proximal Point Method with Momentum Variance Reduction for Non-convex Cross-Device Federated Learningcited by 3
  2. 2024Unity is Power: Semi-Asynchronous Collaborative Training of Large-Scale Models with Structured Pruning in Resource-Limited Clientscited by 3
  3. 2025FedSC: Federated Learning with Semantic-Aware Collaborationcited by 3
  4. 2024On the Convergence of Federated Learning Algorithms without Data Similaritycited by 2
  5. 2024Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learningcited by 2
  6. 2024IPMN Risk Assessment under Federated Learning Paradigmcited by 2
  7. 2025FLARE: A Wireless Side-Channel Fingerprinting Attack on Federated Learningcited by 2
  8. 2026FedSPDnet: Geometry-Aware Federated Deep Learning with SPDnetcited by 2
  9. 2023Balancing Privacy and Performance for Private Federated Learning Algorithmscited by 1
  10. 2023UFed-GAN: A Secure Federated Learning Framework with Constrained Computation and Unlabeled Datacited by 1
  11. 2023A Theoretical Analysis of Efficiency Constrained Utility-Privacy Bi-Objective Optimization in Federated Learningcited by 1
  12. 2024PAFedFV: Personalized and Asynchronous Federated Learning for Finger Vein Recognitioncited by 1
  13. 2024FedSat: A Statistical Aggregation Approach for Class Imbalanced Clients in Federated Learningcited by 1
  14. 2024Universally Harmonizing Differential Privacy Mechanisms for Federated Learning: Boosting Accuracy and Convergencecited by 1
  15. 2025Noise Resilient Over-The-Air Federated Learning In Heterogeneous Wireless Networkscited by 1
  16. 2025An LLM-Empowered Low-Resolution Vision System for On-Device Human Behavior Understandingcited by 1
  17. 2025FedSKC: Federated Learning with Non-IID Data via Structural Knowledge Collaborationcited by 1
  18. 2026GFPL: Generative Federated Prototype Learning for Resource-Constrained and Data-Imbalanced Vision Taskcited by 1
  19. 2024Augmenting the FedProx Algorithm by Minimizing Convergencecited by 0
  20. 2025Traversal Learning: A Lossless And Efficient Distributed Learning Frameworkcited by 0
  21. 2025FRAIN to Train: A Fast-and-Reliable Solution for Decentralized Federated Learningcited by 0
  22. 2025FairEnergy: Contribution-Based Fairness meets Energy Efficiency in Federated Learningcited by 0
  23. 2026FedPBS: Proximal-Balanced Scaling Federated Learning Model for Robust Personalized Training for Non-IID Datacited by 0
  24. 2026Distributed Direct Preference Optimizationcited by 0
  25. 2026Over-the-Air Federated Learning in Heterogeneous Mobile Wireless Networkscited by 0
  26. 2026Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devicescited by 0