GradConsensus: Linearly Convergent Algorithm for Reducing Disagreement in Multi-Agent Optimization
Vivek Khatana, Govind Saraswat, Sourav Patel, Murti V. Salapaka · IEEE Transactions on Network Science and Engineering · 2023
In this article, we propose a new approach,optimize then agreefor 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 foroptimize then agreeis to guarantee that the disagreement between the agents' estimates at every iteration of the distributed optimization algorithm remains under anyapriorispecified 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$k{\text{th}}$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.