Convergence rates for distributed stochastic optimization over random networks

Authors Dusan Jakovetic, Dragana Bajovic, Anit Kumar Sahu, Soummya Kar
Title Convergence rates for distributed stochastic optimization over random networks
Abstract We establish the O([1/k]) convergence rate for distributed stochastic gradient methods that operate over strongly convex costs and random networks. The considered class of methods is standard - each node performs a weighted average of its own and its neighbors' solution estimates (consensus), and takes a negative step with respect to a noisy version of its local function's gradient (innovation). The underlying communication network is modeled through a sequence of temporally independent identically distributed (i.i.d.) Laplacian matrices such that the underlying graphs are connected on average; the local gradient noises are also i.i.d. in time, have finite second moment, and possibly unbounded support. We show that, after a careful setting of the consensus and innovations potentials (weights), the distributed stochastic gradient method achieves a (order-optimal) O([1/k]) convergence rate in the mean square distance from the solution. To the best of our knowledge, this is the first order-optimal convergence rate result on distributed strongly convex stochastic optimization when the network is random and the gradient noises have unbounded support. Simulation examples confirm the theoretical findings.
ISBN 978-1-5386-1395-5
Conference 2018 IEEE Conference on Decision and Control (CDC)
Date 17-19 December, 2018
Location Miami Beach, FL, USA