DISH: A Distributed Hybrid Primal-Dual Optimization Framework to Utilize System Heterogeneity
arXiv:2206.03624 · doi:10.1109/CDC51059.2022.9993156
Abstract
We consider solving distributed consensus optimization problems over multi-agent networks. Current distributed methods fail to capture the heterogeneity among agents' local computation capacities. We propose DISH as a distributed hybrid primal-dual algorithmic framework to handle and utilize system heterogeneity. Specifically, DISH allows those agents with higher computational capabilities or cheaper computational costs to implement Newton-type updates locally, while other agents can adopt the much simpler gradient-type updates. We show that DISH is a general framework and includes EXTRA, DIGing, and ESOM-0 as special cases. Moreover, when all agents take both primal and dual Newton-type updates, DISH approximates Newton's method by estimating both primal and dual Hessians. Theoretically, we show that DISH achieves a linear (Q-linear) convergence rate to the exact optimal solution for strongly convex functions, regardless of agents' choices of gradient-type and Newton-type updates. Finally, we perform numerical studies to demonstrate the efficacy of DISH in practice. To the best of our knowledge, DISH is the first hybrid method allowing heterogeneous local updates for distributed consensus optimization under general network topology with provable convergence and rate guarantees.
References in corpus (6)
- MXNet: A Flexible and Efficient Machine Learning Library for Heterogeneous Distributed Systems
- Federated Optimization: Distributed Machine Learning for On-Device Intelligence
- Harnessing Smoothness to Accelerate Distributed Optimization
- Breaking the Hierarchy: Distributed Control & Economic Optimality in Microgrids
- Monitoring and Optimization for Power Grids: A Signal Processing Perspective
- A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization