# FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 51 references that are in the map.
- First posted on arXiv 5 Mar 2021.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [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)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Federated Learning with Non-IID Data](https://mlsanity.com/paper/1806.00582/) (2018)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [LEAF: A Benchmark for Federated Settings](https://mlsanity.com/paper/1812.01097/) (2018)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [FedBN: Federated Learning on Non-IID Features via Local Batch Normalization](https://mlsanity.com/paper/2102.07623/) (2021)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Asynchronous Federated Optimization](https://mlsanity.com/paper/1903.03934/) (2019)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [Federated Learning with Compression: Unified Analysis and Sharp Guarantees](https://mlsanity.com/paper/2007.01154/) (2020)
- [Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning](https://mlsanity.com/paper/2008.03606/) (2020)
- [On the Convergence of Local Descent Methods in Federated Learning](https://mlsanity.com/paper/1910.14425/) (2019)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data](https://mlsanity.com/paper/2005.11418/) (2020)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Lower Bounds and Optimal Algorithms for Personalized Federated Learning](https://mlsanity.com/paper/2010.02372/) (2020)
- [FedSplit: An algorithmic framework for fast federated optimization](https://mlsanity.com/paper/2005.05238/) (2020)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms](https://mlsanity.com/paper/1808.07576/) (2018)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [First Analysis of Local GD on Heterogeneous Data](https://mlsanity.com/paper/1909.04715/) (2019)
- [Federated Composite Optimization](https://mlsanity.com/paper/2011.08474/) (2020)
- [Parallel SGD: When does averaging help?](https://mlsanity.com/paper/1606.07365/) (2016)

## Built on by (most cited first, 29 of 29)

- [Dynamic Regularized Sharpness Aware Minimization in Federated Learning: Approaching Global Consistency and Smooth Landscape](https://mlsanity.com/paper/2305.11584/) (2023)
- [FedADMM: A Federated Primal-Dual Algorithm Allowing Partial Participation](https://mlsanity.com/paper/2203.15104/) (2022)
- [FedSysID: A Federated Approach to Sample-Efficient System Identification](https://mlsanity.com/paper/2211.14393/) (2022)
- [Fast Composite Optimization and Statistical Recovery in Federated Learning](https://mlsanity.com/paper/2207.08204/) (2022)
- [Over-the-Air Federated Learning and Optimization](https://mlsanity.com/paper/2310.10089/) (2023)
- [Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems](https://mlsanity.com/paper/2301.03113/) (2023)
- [Composite federated learning with heterogeneous data](https://mlsanity.com/paper/2309.01795/) (2023)
- [DFedADMM: Dual Constraints Controlled Model Inconsistency for Decentralized Federated Learning](https://mlsanity.com/paper/2308.08290/) (2023)
- [Nonconvex Federated Learning on Compact Smooth Submanifolds With Heterogeneous Data](https://mlsanity.com/paper/2406.08465/) (2024)
- [Clustered Federated Learning based on Nonconvex Pairwise Fusion](https://mlsanity.com/paper/2211.04218/) (2022)
- [Federated Learning with Convex Global and Local Constraints](https://mlsanity.com/paper/2310.10117/) (2023)
- [FedCanon: Non-Convex Composite Federated Learning with Efficient Proximal Operation on Heterogeneous Data](https://mlsanity.com/paper/2504.11903/) (2025)
- [Federated Learning Using Three-Operator ADMM](https://mlsanity.com/paper/2211.04152/) (2022)
- [Distributed Event-Based Learning via ADMM](https://mlsanity.com/paper/2405.10618/) (2024)
- [DualFL: A Duality-based Federated Learning Algorithm with Communication Acceleration in the General Convex Regime](https://mlsanity.com/paper/2305.10294/) (2023)
- [Privacy-preserving Federated Primal-dual Learning for Non-convex and Non-smooth Problems with Model Sparsification](https://mlsanity.com/paper/2310.19558/) (2023)
- [Communication Efficient ConFederated Learning: An Event-Triggered SAGA Approach](https://mlsanity.com/paper/2402.18018/) (2024)
- [A-FedPD: Aligning Dual-Drift is All Federated Primal-Dual Learning Needs](https://mlsanity.com/paper/2409.18915/) (2024)
- [Controlling Participation in Federated Learning with Feedback](https://mlsanity.com/paper/2411.19242/) (2024)
- [FedSLoP: Memory-Efficient Federated Learning with Low-Rank Gradient Projection](https://mlsanity.com/paper/2604.24012/) (2026)
- [FedMap: Iterative Magnitude-Based Pruning for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2406.19050/) (2024)
- [Novel clustered federated learning based on local loss](https://mlsanity.com/paper/2407.09360/) (2024)
- [Federated Frank-Wolfe Algorithm](https://mlsanity.com/paper/2408.10090/) (2024)
- [Cross-Domain Latent Factors Sharing via Implicit Matrix Factorization](https://mlsanity.com/paper/2409.15568/) (2024)
- [Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum](https://mlsanity.com/paper/2504.12742/) (2025)
- [An Asynchronous Decentralised Optimisation Algorithm for Nonconvex Problems](https://mlsanity.com/paper/2507.22311/) (2025)
- [Finding Structure in Continual Learning](https://mlsanity.com/paper/2602.04555/) (2026)
- [Compressed Proximal Federated Learning for Non-Convex Composite Optimization on Heterogeneous Data](https://mlsanity.com/paper/2603.07654/) (2026)
- [Task Switching Without Forgetting via Proximal Decoupling](https://mlsanity.com/paper/2604.18857/) (2026)

## Abstract (arXiv)

We develop two new algorithms, called, FedDR and asyncFedDR, for solving a fundamental nonconvex composite optimization problem in federated learning. Our algorithms rely on a novel combination between a nonconvex Douglas-Rachford splitting method, randomized block-coordinate strategies, and asynchronous implementation. They can also handle convex regularizers. Unlike recent methods in the literature, e.g., FedSplit and FedPD, our algorithms update only a subset of users at each communication round, and possibly in an asynchronous manner, making them more practical. These new algorithms can handle statistical and system heterogeneity, which are the two main challenges in federated learning, while achieving the best known communication complexity. In fact, our new algorithms match the communication complexity lower bound up to a constant factor under standard assumptions. Our numerical experiments illustrate the advantages of our methods over existing algorithms on synthetic and real datasets.