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

Vivek Khatana

doi:10.1109/TNSE.2023.3321757

2024-01-01

PRE

DOI：10.1109/TNSE.2023.3321757

原文链接

原文求助

摘要

En 中文

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 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.

Keyword:

Optimization

Approximation algorithms

Convergence

Directed graphs

Consensus protocol

Robots

Optimization methods

distributed control

distributed optimization

finite-time consensus

linear convergence