Distributed Stochastic Subgradient Projection Algorithms Based on Weight-Balancing over Time-Varying Directed Graphs

Abstract EN

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 O(ln Γ/Γ).

In addition, we verify the theoretical results through simulations.