Can Primal Methods Outperform Primal-Dual Methods in Decentralized Dynamic Optimization?
- 24 July 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 68 (1053587X) , 4466-4480
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.Keywords
All Related Versions
Funding Information
- NSF (61573331, 61573331, 61973324)
- Fundamental Research Funds for the Central Universities
This publication has 46 references indexed in Scilit:
- DLM: Decentralized Linearized Alternating Direction Method of MultipliersIEEE Transactions on Signal Processing, 2015
- Stability and Performance Limits of Adaptive Primal-Dual NetworksIEEE Transactions on Signal Processing, 2015
- EXTRA: An Exact First-Order Algorithm for Decentralized Consensus OptimizationSIAM Journal on Optimization, 2015
- Double smoothing for time-varying distributed multiuser optimization2014
- Multi-Agent Distributed Optimization via Inexact Consensus ADMMIEEE Transactions on Signal Processing, 2014
- Adaptation, Learning, and Optimization over NetworksFoundations and Trends in Machine Learning, 2014
- On distributed online classification in the midst of concept driftsNeurocomputing, 2013
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network ScalingIEEE Transactions on Automatic Control, 2011
- Discrete-time dynamic average consensusAutomatica, 2010
- Gradient Methods for Nonstationary Unconstrained Optimization ProblemsAutomation and Remote Control, 2005