FedHybrid: A Hybrid Primal-Dual Algorithm Framework for Federated Optimization
arXiv:2106.01279 · doi:10.1109/TSP.2023.3240083
Abstract
We consider a multi-agent consensus optimization problem over a server-client (federated) network, where all clients are connected to a central server. Current distributed algorithms fail to capture the heterogeneity in clients' local computation capacities. Motivated by the generalized Method of Multipliers in centralized optimization, we derive an approximate Newton-type primal-dual method with a practical distributed implementation by utilizing the server-client topology. Then we propose a new primal-dual algorithm framework FedHybrid that allows different clients to perform various types of updates. Specifically, each client can choose to perform either gradient-type or Newton-type updates. We propose a novel analysis framework for primal-dual methods and obtain a linear convergence rate of FedHybrid for strongly convex functions, regardless of clients' choices of gradient-type or Newton-type updates. Numerical studies are provided to demonstrate the efficacy of our method in practice. To the best of our knowledge, this is the first hybrid algorithmic framework allowing heterogeneous local updates for distributed consensus optimization with a provable convergence and rate guarantee.
References in corpus (6)
- Federated Learning: Challenges, Methods, and Future Directions
- MXNet: A Flexible and Efficient Machine Learning Library for Heterogeneous Distributed Systems
- Federated Optimization: Distributed Machine Learning for On-Device Intelligence
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data
- Newton-type Methods for Minimax Optimization