Distributed stochastic subgradient projection algorithms for convex optimization

DOI10.1007/S10957-010-9737-7MaRDI QIDQ620442zbMATH OpenOpenAlexFDO

Authors S. Sundhar Ram, Venugopal V. Veeravalli, Angelia Nedić

Publication date 19 January 2011

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0811.2595

zbMATH Keywords

Distributed algorithm Stochastic approximation Subgradient methods

Mathematics Subject Classification ID

Stochastic network models in operations research (90B15) Stochastic programming (90C15) Convex programming (90C25)

Abstract: We consider 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. The goal of this paper is to explore the effects of stochastic subgradient errors on the convergence of the algorithm. We first consider the behavior of the algorithm in mean, and then the convergence with probability 1 and in mean square. We consider general stochastic errors that have uniformly bounded second moments and obtain bounds on the limiting performance of the algorithm in mean for diminishing and non-diminishing stepsizes. When the means of the errors diminish, we prove that there is mean consensus between the agents and mean convergence to the optimum function value for diminishing stepsizes. When the mean errors diminish sufficiently fast, we strengthen the results to consensus and convergence of the iterates to an optimal solution with probability 1 and in mean square.

Review text

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.

Recommendations

Cites work

Cited in

(only showing first 100 items - show all)

This page was built for publication: Distributed stochastic subgradient projection algorithms for convex optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q620442)