TY - GEN
T1 - Max-Gossip Subgradient Method for Distributed Optimization
AU - Verma, Ashwin
AU - Vasconcelos, Marcos M.
AU - Mitra, Urbashi
AU - Touri, Behrouz
N1 - U. Mitra was supported in part by the following agencies: ONR under grant N00014-15-1-2550, NSF under grants CCF-1817200 and CCF-2008927, ARO under grant W911NF1910269, and DOE DE-SC0021417. M. M. Vasconcelos was supported by funding from the Commonwealth Cyber Initiative (CCI).
PY - 2021
Y1 - 2021
N2 - We study the problem of distributed optimization over a network of agents where the agents strive to minimize the sum of local objective functions through an exchange of information between the nodes based on an underlying communication topology. Motivated by the need for low communication algorithms with better convergence rates in broadcast settings, we propose a subgradient method based on a state-dependent gossip algorithm. The state-dependent gossip algorithm operates by averaging the edge with the maximum disagreement over the network. We prove that agents employing the state-dependent subgradient method achieve consensus on an optimal solution. By exploiting the convergence properties of a Lyapunov function, we obviate the need for results on time-normalized information flow between any node pairs.
AB - We study the problem of distributed optimization over a network of agents where the agents strive to minimize the sum of local objective functions through an exchange of information between the nodes based on an underlying communication topology. Motivated by the need for low communication algorithms with better convergence rates in broadcast settings, we propose a subgradient method based on a state-dependent gossip algorithm. The state-dependent gossip algorithm operates by averaging the edge with the maximum disagreement over the network. We prove that agents employing the state-dependent subgradient method achieve consensus on an optimal solution. By exploiting the convergence properties of a Lyapunov function, we obviate the need for results on time-normalized information flow between any node pairs.
UR - http://www.scopus.com/inward/record.url?scp=85126000264&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85126000264&partnerID=8YFLogxK
U2 - 10.1109/CDC45484.2021.9683138
DO - 10.1109/CDC45484.2021.9683138
M3 - Conference contribution
AN - SCOPUS:85126000264
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 3130
EP - 3136
BT - 60th IEEE Conference on Decision and Control, CDC 2021
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 60th IEEE Conference on Decision and Control, CDC 2021
Y2 - 13 December 2021 through 17 December 2021
ER -