GradConsensus: Linearly Convergent Algorithm for Reducing Disagreement in Multi-Agent Optimization

In this article, we propose a new approach, optimize then agree for minimizing a sum of convex functions, over a directed graph. The optimize then agree approach decouples the optimization step and the consensus step in a multi-agent distributed optimization framework. The key motivation for optimize then agree is to guarantee that the disagreement between the agents' estimates at every iteration of the distributed optimization algorithm remains under any apriori specified tolerance; existing algorithms do not provide such a guarantee which is required in many practical scenarios. In the proposed algorithm, each agent utilizes its locally available function information along with a finite-time approximate consensus protocol to move toward the optimal solution. We establish a global R-linear rate of convergence if the aggregate function is strongly convex and Lipschitz differentiable. We show that under the relaxed assumption of convex and Lipschitz differentiable functions, a Q-linear rate is achieved until reaching a neighborhood of the optimal, that can be managed using the tolerance value specified on the finite-time approximate consensus protocol; no existing method in the literature has such strong convergence guarantees for not necessarily strongly convex functions. The communication overhead for these improved guarantees of our algorithm is within a log k, (at the kth iteration of the algorithm) factor of the traditional algorithms. Further, we numerically demonstrate the efficacy of the proposed algorithm in solving a distributed logistic regression problem.