# FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data

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

## Key facts

- Cited by 144 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2020.

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

- [FedBN: Federated Learning on Non-IID Features via Local Batch Normalization](https://mlsanity.com/paper/2102.07623/) (2021)
- [Federated Learning Based on Dynamic Regularization](https://mlsanity.com/paper/2111.04263/) (2021)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [FedCM: Federated Learning with Client-level Momentum](https://mlsanity.com/paper/2106.10874/) (2021)
- [On Large-Cohort Training for Federated Learning](https://mlsanity.com/paper/2106.07820/) (2021)
- [Where to Begin? On the Impact of Pre-Training and Initialization in Federated Learning](https://mlsanity.com/paper/2210.08090/) (2022)
- [Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy](https://mlsanity.com/paper/2106.13673/) (2021)
- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning](https://mlsanity.com/paper/2201.09531/) (2022)
- [FedSpeed: Larger Local Interval, Less Communication Round, and Higher Generalization Accuracy](https://mlsanity.com/paper/2302.10429/) (2023)
- [Dynamic Regularized Sharpness Aware Minimization in Federated Learning: Approaching Global Consistency and Smooth Landscape](https://mlsanity.com/paper/2305.11584/) (2023)
- [Federated Learning via Inexact ADMM](https://mlsanity.com/paper/2204.10607/) (2022)
- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [Anarchic Federated Learning](https://mlsanity.com/paper/2108.09875/) (2021)
- [Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective](https://mlsanity.com/paper/2111.03741/) (2021)
- [Momentum Benefits Non-IID Federated Learning Simply and Provably](https://mlsanity.com/paper/2306.16504/) (2023)
- [FedADMM: A Federated Primal-Dual Algorithm Allowing Partial Participation](https://mlsanity.com/paper/2203.15104/) (2022)
- [Local Adaptivity in Federated Learning: Convergence and Consistency](https://mlsanity.com/paper/2106.02305/) (2021)
- [Architecture Agnostic Federated Learning for Neural Networks](https://mlsanity.com/paper/2202.07757/) (2022)
- [FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization](https://mlsanity.com/paper/2103.03452/) (2021)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [FeDeRA:Efficient Fine-tuning of Language Models in Federated Learning Leveraging Weight Decomposition](https://mlsanity.com/paper/2404.18848/) (2024)
- [FedADMM: A Robust Federated Deep Learning Framework with Adaptivity to System Heterogeneity](https://mlsanity.com/paper/2204.03529/) (2022)
- [FedSWA: Improving Generalization in Federated Learning with Highly Heterogeneous Data via Momentum-Based Stochastic Controlled Weight Averaging](https://mlsanity.com/paper/2507.20016/) (2025)
- [Personalized Federated Learning for Heterogeneous Clients with Clustered Knowledge Transfer](https://mlsanity.com/paper/2109.08119/) (2021)
- [The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning](https://mlsanity.com/paper/2111.05326/) (2021)
- [Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedup](https://mlsanity.com/paper/2308.00522/) (2023)
- [Bayesian Federated Learning: A Survey](https://mlsanity.com/paper/2304.13267/) (2023)

## Abstract (arXiv)

Federated Learning (FL) has become a popular paradigm for learning from distributed data. To effectively utilize data at different devices without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a "computation then aggregation" (CTA) model, in which multiple local updates are performed using local data, before sending the local models to the cloud for aggregation. However, these schemes typically require strong assumptions, such as the local data are identically independent distributed (i.i.d), or the size of the local gradients are bounded. In this paper, we first explicitly characterize the behavior of the FedAvg algorithm, and show that without strong and unrealistic assumptions on the problem structure, the algorithm can behave erratically for non-convex problems (e.g., diverge to infinity). Aiming at designing FL algorithms that are provably fast and require as few assumptions as possible, we propose a new algorithm design strategy from the primal-dual optimization perspective. Our strategy yields a family of algorithms that take the same CTA model as existing algorithms, but they can deal with the non-convex objective, achieve the best possible optimization and communication complexity while being able to deal with both the full batch and mini-batch local computation models. Most importantly, the proposed algorithms are it communication efficient, in the sense that the communication pattern can be adaptive to the level of heterogeneity among the local data. To the best of our knowledge, this is the first algorithmic framework for FL that achieves all the above properties.