Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs

TLDR

This paper considers the problem of distributed optimization over time‑varying graphs. The authors propose the DIGing algorithm for undirected time‑varying graphs, combining an inexact gradient method with gradient tracking. DIGing employs doubly stochastic mixing matrices and fixed step‑sizes to drive agents to a global minimizer, while Push‑DIGing adapts this framework with a push‑sum protocol and column‑stochastic matrices for directed graphs, and both are validated by numerical experiments. Under strong convexity, both algorithms achieve R‑linear convergence with explicit rate bounds, and DIGing’s performance scales polynomially with the number of agents.

Abstract

This paper considers the problem of distributed optimization over time-varying graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, based on a combination of a distributed inexact gradient method and a gradient tracking technique. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all the agents' iterates to a global and consensual minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining the Push-DIGing algorithm. Push-DIGing uses column stochastic matrices and fixed step-sizes, but it still converges to a global and consensual minimizer. Under the strong convexity assumption, we prove that the algorithms converge at R-linear (geometric) rates as long as the step-sizes do not exceed some upper bounds. We establish explicit estimates for the convergence rates. When the graph is undirected it shows that DIGing scales polynomially in the number of agents. We also provide some numerical experiments to demonstrate the efficacy of the proposed algorithms and to validate our theoretical findings.