TY - JOUR
T1 - AB/Push-Pull method for distributed optimization in time-varying directed networks
AU - Nedić, Angelia
AU - Nguyen, Duong Thuy Anh
AU - Nguyen, Duong Tung
N1 - Publisher Copyright:
© 2023 Informa UK Limited, trading as Taylor & Francis Group.
PY - 2023
Y1 - 2023
N2 - In this paper, we study the distributed optimization problem for a system of agents embedded in time-varying directed communication networks. Each agent has its own cost function and agents cooperate to determine the global decision that minimizes the summation of all individual cost functions. We consider the so-called push-pull gradient-based algorithm (termed as AB/Push-Pull) which employs both row- and column-stochastic weights simultaneously to track the optimal decision and the gradient of the global cost while ensuring consensus and optimality. We show that the algorithm converges linearly to the optimal solution over a time-varying directed network for a constant stepsize when the agent's cost function is smooth and strongly convex. The linear convergence of the method has been shown in [F. Saadatniaki, R. Xin, and U.A. Khan, Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices, IEEE Trans. Autom. Control 65(11) (2020), pp. 4769–4780], where the multi-step consensus contraction parameters for row- and column-stochastic mixing matrices are not directly related to the underlying graph structure, and the explicit range for the stepsize value is not provided. With respect to [F. Saadatniaki, R. Xin, and U.A. Khan, Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices, IEEE Trans. Autom. Control 65(11) (2020), pp. 4769–4780], the novelty of this work is twofold: (1) we establish the one-step consensus contraction for both row- and column-stochastic mixing matrices with the contraction parameters given explicitly in terms of the graph diameter and other graph properties; and (2) we provide explicit upper bounds for the stepsize value in terms of the properties of the cost functions, the mixing matrices, and the graph connectivity structure.
AB - In this paper, we study the distributed optimization problem for a system of agents embedded in time-varying directed communication networks. Each agent has its own cost function and agents cooperate to determine the global decision that minimizes the summation of all individual cost functions. We consider the so-called push-pull gradient-based algorithm (termed as AB/Push-Pull) which employs both row- and column-stochastic weights simultaneously to track the optimal decision and the gradient of the global cost while ensuring consensus and optimality. We show that the algorithm converges linearly to the optimal solution over a time-varying directed network for a constant stepsize when the agent's cost function is smooth and strongly convex. The linear convergence of the method has been shown in [F. Saadatniaki, R. Xin, and U.A. Khan, Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices, IEEE Trans. Autom. Control 65(11) (2020), pp. 4769–4780], where the multi-step consensus contraction parameters for row- and column-stochastic mixing matrices are not directly related to the underlying graph structure, and the explicit range for the stepsize value is not provided. With respect to [F. Saadatniaki, R. Xin, and U.A. Khan, Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices, IEEE Trans. Autom. Control 65(11) (2020), pp. 4769–4780], the novelty of this work is twofold: (1) we establish the one-step consensus contraction for both row- and column-stochastic mixing matrices with the contraction parameters given explicitly in terms of the graph diameter and other graph properties; and (2) we provide explicit upper bounds for the stepsize value in terms of the properties of the cost functions, the mixing matrices, and the graph connectivity structure.
KW - Distributed optimization
KW - directed graphs
KW - gradient tracking
KW - time-varying graphs
UR - http://www.scopus.com/inward/record.url?scp=85174238394&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85174238394&partnerID=8YFLogxK
U2 - 10.1080/10556788.2023.2261602
DO - 10.1080/10556788.2023.2261602
M3 - Article
AN - SCOPUS:85174238394
SN - 1055-6788
JO - Optimization Methods and Software
JF - Optimization Methods and Software
ER -