Convergence Rates for Distributed Stochastic Optimization Over Random Networks
Authors:
Open Access
- 1 December 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 4238-4245
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.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Stochastic Subgradient Algorithms for Strongly Convex Optimization Over Distributed NetworksIEEE Transactions on Network Science and Engineering, 2017
- Excess-Risk of Distributed Stochastic LearnersIEEE Transactions on Information Theory, 2016
- Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed GraphsIEEE Transactions on Automatic Control, 2016
- Hybrid Random/Deterministic Parallel Algorithms for Convex and Nonconvex Big Data OptimizationIEEE Transactions on Signal Processing, 2015
- Diffusion strategies for adaptation and learning over networks: an examination of distributed strategies and network behaviorIEEE Signal Processing Magazine, 2013
- Distributed multi-agent optimization with state-dependent communicationMathematical Programming, 2011
- Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and TradeoffsIEEE Journal of Selected Topics in Signal Processing, 2011
- Stochastic consensus over noisy networks with Markovian and arbitrary switchesAutomatica, 2010
- Distributed Consensus Algorithms in Sensor Networks With Imperfect Communication: Link Failures and Channel NoiseIEEE Transactions on Signal Processing, 2008
- Distributed average consensus with least-mean-square deviationJournal of Parallel and Distributed Computing, 2007