TY - GEN

T1 - Asynchronous gossip algorithms for stochastic optimization

AU - Ram, S. Sundhar

AU - Nedić, A.

AU - Veeravalli, V. V.

PY - 2009

Y1 - 2009

N2 - We consider a distributed multi-agent network system where the goal is to minimize an objective function that can be written as the sum of component functions, each of which is known partially (with stochastic errors) to a specific network agent. We propose an asynchronous algorithm that is motivated by random gossip schemes where each agent has a local Poisson clock. At each tick of its local clock, the agent averages its estimate with a randomly chosen neighbor and adjusts the average using the gradient of its local function that is computed with stochastic errors.We investigate the convergence properties of the algorithm for two different classes of functions. First, we consider differentiable, but not necessarily convex functions, and prove that the gradients converge to zero with probability 1. Then, we consider convex, but not necessarily differentiable functions, and show that the iterates converge to an optimal solution almost surely.

AB - We consider a distributed multi-agent network system where the goal is to minimize an objective function that can be written as the sum of component functions, each of which is known partially (with stochastic errors) to a specific network agent. We propose an asynchronous algorithm that is motivated by random gossip schemes where each agent has a local Poisson clock. At each tick of its local clock, the agent averages its estimate with a randomly chosen neighbor and adjusts the average using the gradient of its local function that is computed with stochastic errors.We investigate the convergence properties of the algorithm for two different classes of functions. First, we consider differentiable, but not necessarily convex functions, and prove that the gradients converge to zero with probability 1. Then, we consider convex, but not necessarily differentiable functions, and show that the iterates converge to an optimal solution almost surely.

UR - http://www.scopus.com/inward/record.url?scp=77950803166&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77950803166&partnerID=8YFLogxK

U2 - 10.1109/CDC.2009.5399485

DO - 10.1109/CDC.2009.5399485

M3 - Conference contribution

AN - SCOPUS:77950803166

SN - 9781424438716

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 3581

EP - 3586

BT - Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009

Y2 - 15 December 2009 through 18 December 2009

ER -