Asynchronous stochastic convex optimization over random networks: Error bounds

We consider a distributed multi-agent network system where the goal is to minimize the sum of convex functions, each of which is known (with stochastic errors) to a specific network agent. We are interested in asynchronous algorithms for solving the problem over a connected network where the communications among the agent are random. At each time, a random set of agents communicate and update their information. When updating, an agent uses the (sub)gradient of its individual objective function and its own stepsize value. The algorithm is completely asynchronous as it neither requires the coordination of agent actions nor the coordination of the stepsize values. We investigate the asymptotic error bounds of the algorithm with a constant stepsize for strongly convex and just convex functions. Our error bounds capture the effects of agent stepsize choices and the structure of the agent connectivity graph. The error bound scales at best as m in the number m of agents when the agent objective functions are strongly convex.