Distributed stochastic subgradient projection algorithms based on weight-balancing over time-varying directed graphs (Q2331322)

Summary: 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 \Gamma/\Gamma\) under local strong convexity, where \(\Gamma\) is the number of iterations. In addition, under local convexity, we prove that our proposed algorithm can converge with rate \(O(\ln\Gamma /\sqrt{\Gamma})\). In addition, we verify the theoretical results through simulations.