Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
arXiv:2003.00816 · doi:10.1109/TSP.2020.3011640
Abstract
In this paper, we consider the decentralized dynamic optimization problem defined over a multi-agent network. Each agent possesses a time-varying local objective function, and all agents aim to collaboratively track the drifting global optimal solution that minimizes the summation of all local objective functions. The decentralized dynamic optimization problem can be solved by primal or primal-dual methods, and when the problem degenerates to be static, it has been proved in literature that primal-dual methods are superior to primal ones. This motivates us to ask: are primal-dual methods necessarily better than primal ones in decentralized dynamic optimization? To answer this question, we investigate and compare convergence properties of the primal method, diffusion, and the primal-dual approach, decentralized gradient tracking (DGT). Theoretical analysis reveals that diffusion can outperform DGT in certain dynamic settings. We find that DGT and diffusion are significantly affected by the drifts and the magnitudes of optimal gradients, respectively. In addition, we show that DGT is more sensitive to the network topology, and a badly-connected network can greatly deteriorate its convergence performance. These conclusions provide guidelines on how to choose proper dynamic algorithms in various application scenarios. Numerical experiments are constructed to validate the theoretical analysis.
arXiv commentSubmitted for publication; 13 pages; 6 figures
References in corpus (19)
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Harnessing Smoothness to Accelerate Distributed Optimization
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
- Distributed Convex Optimization for Continuous-Time Dynamics with Time-Varying Cost Function
- A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
- A linear algorithm for optimization over directed graphs with geometric convergence
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- Distributed Pareto Optimization via Diffusion Strategies
- D: Decentralized Training over Decentralized Data
- A Class of Prediction-Correction Methods for Time-Varying Convex Optimization
- Optimization and Learning with Information Streams: Time-varying Algorithms and Applications
- On the Influence of Bias-Correction on Distributed Stochastic Optimization
- Stability and Performance Limits of Adaptive Primal-Dual Networks
- Distributed Decision-Making over Adaptive Networks
- On Distributed Online Classification in the Midst of Concept Drifts
- An introduction to decentralized stochastic optimization with gradient tracking
- Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
Cited by in corpus (8)
- Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data
- Distributed and Inexact Proximal Gradient Method for Online Convex Optimization
- ADMM-Tracking Gradient for Distributed Optimization over Asynchronous and Unreliable Networks
- Robust Online Learning over Networks
- Linear Convergent Decentralized Optimization with Compression
- Tracking Performance of Online Stochastic Learners
- Online Distributed Learning with Quantized Finite-Time Coordination
- Distributed Prediction-Correction ADMM for Time-Varying Convex Optimization