Decentralized stochastic subgradient projection optimization algorithms over random networks

We study decentralized constrained stochastic optimization by networked nodes which cooperatively minimize a sum of convex cost functions. The network is modeled by a sequence of time-varying random digraphs which may be spatially and temporally dependent. Each node of the network represents a local optimizer which only knows its own local cost function and local constraint set. And the global constraint set is the intersection of the local constraint sets. We consider a decentralized subgradient projection algorithm with noisy measurements of subgradients of local cost functions. By the non-expansive property of the projection operator, algebraic graph theory, convex analysis and the nonnegative supermartingale convergence theorem, it is proved that proper step sizes can be designed so that the states of all local optimizers converge to the same global optimal solution almost surely provided that the local subgradient functions grow linearly and the sequence of digraphs is conditionally balanced and uniformly conditionally jointly connected. Besides, convergence rates with different step sizes are given for the case with strongly convex local cost functions.