A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient Descent

By Alexander Olshevsky, Ioannis Ch. Paschalidis, Shi Pu. 2019

18 citations recorded by the source corpus.

This paper is concerned with minimizing the average of $n$ cost functions over a network, in which agents may communicate and exchange information with their peers in the network. Specifically, we consider the setting where only noisy gradient information is available. To solve the problem, we study the standard distributed stochastic gradient descent (DSGD) method and perform a non-asymptotic convergence analysis. For strongly convex and smooth objective functions, we not only show that DSGD asymptotically achieves the optimal network independent convergence rate compared to centralized stochastic gradient descent (SGD), but also explicitly identify the non-asymptotic convergence rate as a function of characteristics of the objective functions and the network. Furthermore, we derive the time needed for DSGD to approach the asymptotic convergence rate, which behaves as $K_T=\mathcal{O}(\frac{n}{(1-\rho_w)^2})$, where $(1-\rho_w)$ denotes the spectral gap of the mixing matrix of communicating agents. Finally, we construct a "hard" optimization problem for which we show the transient time needed for DSGD to approach the asymptotic convergence rate is lower bounded by $\Omega\left(\frac{n}{(1-\rho_w)^2}\right)$, implying the sharpness of the obtained result.

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

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “This means that decentralized SGD methods are ideal for the optimization in the high-noise regime even when network connectivity is low and number of local steps is large (see also (Chaturapruek et al., 2015) and recent work (Pu et al., 2019)).”
Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks (2019, unknown): “D-SG Olshevsky et al. (2019)† No O ( 1 k ) E ∥∥x̄(k) − x∗∥∥2 ≤ O ( σ(2) μ2Nk + κ 2 (1−γ)2μ2k2 + σ(2)κ(2) (1−γ)μ2k2 )”