Convergence Rates for Distributed Stochastic Optimization Over Random Networks

By Dusan Jakovetic, Dragana Bajovic, Anit Kumar Sahu, Soummya Kar. 2018

76 citations recorded by the source corpus.

We establish the $O(\frac{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(\frac{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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “In the context of decentralized optimization, previous works have studied the error convergence in terms of iterations or communication rounds for decentralized gradient descent [1], [2], [3], [4], [5], [6], [7], [8] mostly for (strongly) convex loss functions.”
A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient Descent (2019, background): “Recently, distributed implementation of stochastic gradient algorithms has received considerable interest [37, 41, 12, 3, 5, 42, 6, 7, 22, 17, 18, 30, 31, 38, 40, 14, 33, 29, 44, 1].”
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent (2019, background): “In [39], an O ( 1 k ) convergence rate was established for strongly convex costs and random networks.”
Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates. (2018, methodology): “Reference [18] considers distributed stochastic ﬁrst order methods and establishes the method’s O (1 /k ) convergence rate.”
Distributed stochastic gradient tracking methods (2018, methodology): “In [18], theO( 1 k ) convergence rate was established for strongly convex costs and random networks.”
Optimization over time-varying directed graphs with row and column-stochastic matrices (2018, background): “s two accelerated distributed Nesterov-like gradient methods featuring resiliency to link failures, reduced computational load, and improved convergence rates compared to other gradient methods. Ref. [45] establishes a convergence rate of O(1 k ) for distributed stochastic gradient methods over temp”