# On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality

arXiv: https://arxiv.org/abs/2310.00419 · HTML: https://mlsanity.com/paper/2310.00419/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 23 references that are in the map.
- First posted on arXiv 30 Sep 2023.

## Builds on (most cited first, 11 of 11)

- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [On the Linear Convergence of the ADMM in Decentralized Consensus Optimization](https://mlsanity.com/paper/1307.5561/) (2013)
- [Multi-consensus Decentralized Accelerated Gradient Descent](https://mlsanity.com/paper/2005.00797/) (2020)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [Revisiting EXTRA for Smooth Distributed Optimization](https://mlsanity.com/paper/2002.10110/) (2020)
- [Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication](https://mlsanity.com/paper/1401.4432/) (2014)
- [Towards accelerated rates for distributed optimization over time-varying networks](https://mlsanity.com/paper/2009.11069/) (2020)
- [Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters](https://mlsanity.com/paper/1810.01053/) (2018)
- [Exponential Convergence for Distributed Smooth Optimization Under the Restricted Secant Inequality Condition](https://mlsanity.com/paper/1909.03282/) (2019)
- [Passivity-Based Distributed Optimization with Communication Delays Using PI Consensus Algorithm](https://mlsanity.com/paper/1609.04666/) (2016)

## Abstract (arXiv)

This paper considers solving distributed optimization problems in peer-to-peer multi-agent networks. The network is synchronous and connected. By using the proportional-integral (PI) control strategy, various algorithms with fixed stepsize have been developed. Two notable among them are the PI algorithm and the PI consensus algorithm. Although the PI algorithm has provable linear or exponential convergence without the standard requirement of (strong) convexity, a similar guarantee for the PI consensus algorithm is unavailable. In this paper, using Lyapunov theory, we guarantee exponential convergence of the PI consensus algorithm for global cost functions that satisfy the restricted secant inequality, with rate-matching discretization, without requiring convexity. To accelerate the PI consensus algorithm, we incorporate local pre-conditioning in the form of constant positive definite matrices and numerically validate its efficiency compared to the prominent distributed convex optimization algorithms. Unlike classical pre-conditioning, where only the gradients are multiplied by a pre-conditioner, the proposed pre-conditioning modifies both the gradients and the consensus terms, thereby controlling the effect of the communication graph on the algorithm.