On the Convergence of Decentralized Gradient Descent

Consider the consensus problem of minimizing f(x)=∑ᵢ₌₁ⁿ fᵢ(x), where x∈Rᵖ and each fᵢ is only known to the individual agent i in a connected network of n agents. To solve this problem and obtain the solution, all the agents collaborate with their neighbors through information exchange. This type of decentralized computation does not need a fusion center, offers better network load balance, and improves data privacy. This paper studies the decentralized gradient descent method [A. Nedic and A. Ozdaglar, IEEE Trans. Automat. Control, 54 (2009), pp. 48--61], in which each agent i updates its local variable x₍ᵢ₎∈Rⁿ by combining the average of its neighbors' with a local negative-gradient step -α ∇ fᵢ(x₍ᵢ₎). The method is described by the iteration x₍ᵢ₎(k+1) ∑ⱼ₌₁ⁿ wᵢⱼ x₍ⱼ₎(k) - α ∇ fᵢ(x₍ᵢ₎(k)),\ for each agent~i, where wᵢⱼ is nonzero only if i and j are neighbors or $i=j$ and the matrix W=[wᵢⱼ] ∈ Rn × n is symmetric and doubly stochastic. This paper analyzes the convergence of this iteration and derives its rate of convergence under the assumption that each fᵢ is proper closed convex and lower bounded, ∇ fᵢ is Lipschitz continuous with constant Lfᵢ>0, and the stepsize α is fixed. Provided that α ≤ min\(1+λₙ(W))/Lₕ,1/Lf̄\, where Lₕ=maxᵢᵢ\ and Lf̄=1/n∑ᵢ₌₁ⁿLfᵢ, the objective errors of all the local solutions and the networkwide mean solution reduce at rates of $O(1/k)$ until they reach a level of O(α). If fᵢ are strongly convex with modulus μfᵢ and α ≤ min\(1+λₙ(W))/Lₕ,1/(Lf̄+μf̄)\, where μf̄=1/n∑ᵢ₌₁ⁿμfᵢ, then all the local solutions and the mean solution 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 sparse signal. This analysis reveals how the convergence of x₍ᵢ₎(k+1) ∑ⱼ₌₁ⁿ wᵢⱼ x₍ⱼ₎(k) - α ∇ fᵢ(x₍ᵢ₎(k)),\ for each agent~i, depends on the stepsize, function convexity, and network spectrum.