On the Convergence of Decentralized Gradient Descent

Consider the consensus problem of minimizing f(x)=∑ᵢ₌₁ⁿ fᵢ(x) where each fᵢ is only known to one individual agent i out of a connected network of n agents. All the agents shall collaboratively solve this problem and obtain the solution subject to data exchanges restricted to between neighboring agents. Such algorithms avoid the need of a fusion center, offer better network load balance, and improve data privacy. We study the decentralized gradient descent method in which each agent i updates its variable x₍ᵢ₎, which is a local approximate to the unknown variable x, by combining the average of its neighbors' with the negative gradient step -α∇ fᵢ(x₍ᵢ₎). The iteration is x₍ᵢ₎(k+1) ∑neighbor j of i wᵢⱼ x₍ⱼ₎(k) - α∇ fᵢ(x₍ᵢ₎(k)), each agent i, where the averaging coefficients form a symmetric doubly stochastic matrix W=[wᵢⱼ] ∈ Rn × n. We analyze the convergence of this iteration and derive its converge rate, assuming that each fᵢ is proper closed convex and lower bounded, ∇ fᵢ is Lipschitz continuous with constant Lfᵢ, and stepsize $α$ is fixed. Provided that α< O(1/Lₕ) where Lₕ=maxᵢᵢ\, the objective error at the averaged solution, f(1/n∑ᵢ x₍ᵢ₎(k))-f^*, reduces at a speed of $O(1/k)$ until it reaches $O(α)$. If fᵢ are further (restricted) strongly convex, then both 1/n∑ᵢ x₍ᵢ₎(k) and each x₍ᵢ₎(k) converge to the global minimizer x^* at a linear rate until reaching an $O(α)$-neighborhood of x^*. We also develop an iteration for decentralized basis pursuit and establish its linear convergence to an $O(α)$-neighborhood of the true unknown sparse signal.