Distributed Stochastic Subgradient Projection Algorithms Based on Weight‐Balancing over Time‐Varying Directed Graphs
Junlong Zhu, Ping Xie, Mingchuan Zhang, Ruijuan Zheng, Ling Xing, Qingtao Wu · Complexity · 2019
We consider a distributed constrained optimization problem over graphs, where cost function of each agent is private. Moreover, we assume that the graphs are time‐varying and directed. In order to address such problem, a fully decentralized stochastic subgradient projection algorithm is proposed over time‐varying directed graphs. However, since the graphs are directed, the weight matrix may not be a doubly stochastic matrix. Therefore, we overcome this difficulty by using weight‐balancing technique. By choosing appropriate step‐sizes, we show that iterations of all agents asymptotically converge to some optimal solutions. Further, by our analysis, convergence rate of our proposed algorithm is O(ln Γ/Γ) under local strong convexity, where Γ is the number of iterations. In addition, under local convexity, we prove that our proposed algorithm can converge with rate . In addition, we verify the theoretical results through simulations.