Distributed stochastic subgradient projection algorithms for convex optimization (Q620442)

The problem considered in this paper is a distributed multi-agent network system where the goal is to minimize a sum of convex objective functions of the agents subject to a common convex constraint set. Each agent maintains an iterate sequence and communicates the iterates to its neighbors. Then, each agent combines weighted averages of the received iterates with its own iterate, and adjusts the iterate by using subgradient information (known with stochastic errors) of its own function and by projecting onto the constraint set. One of the methods proposed for this problem is the distributed subgradient algorithm [\textit{A. Nedić} and \textit{A. Ozdaglar}, Distributed subgradient methods for multi-agent optimization. Trans. Automat. Control 54, 48--61 (2009); \textit{A. Nedić, A. Ozdaglar} and \textit{P. A. Parrilo}, ``Constrained consensus and optimization for multi-agent networks'', LIDS report 2779, IEEE Transactions on Automatic Control 55, No. 4, 922--938 (2010)]. This paper studies the effect of stochastic errors on the distributed subgradient algorithm, where the errors are due to the agents computing the noisy subgradients of their respective objective functions. First, the authors consider general stochastic errors and stepsizes, and obtain error bounds on the limiting performance of the algorithm. Then, they consider errors whose mean and stepsize diminish sufficiently fast, and prove consensus and convergence of the iterates to an optimal solution both with probability 1 and in mean square.