FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
arXiv:2103.03452
Abstract
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.
arXiv comment39 pages, and 12 figures
References in corpus (20)
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- Federated Learning with Non-IID Data
- Federated Optimization: Distributed Machine Learning for On-Device Intelligence
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Asynchronous Federated Optimization
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method
- FedBN: Federated Learning on Non-IID Features via Local Batch Normalization
- LEAF: A Benchmark for Federated Settings
- ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
- Don't Use Large Mini-Batches, Use Local SGD
- Local SGD Converges Fast and Communicates Little
- On the Convergence of Local Descent Methods in Federated Learning
- Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
- Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
- SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
- Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
- FedSplit: An algorithmic framework for fast federated optimization
- Parallel SGD: When does averaging help?
- First Analysis of Local GD on Heterogeneous Data
- Lower Bounds and Optimal Algorithms for Personalized Federated Learning