Communication Efficient Curvature Aided Primal-Dual Algorithms for Decentralized Optimization

Yichuan Li, Petros G Voulgaris, Dušan M. Stipanović, Nikolaos M. Freris

Research output: Contribution to journalArticlepeer-review

Abstract

—This article presents a family of algorithms for decentralized convex composite problems. We consider the setting of a network of agents that cooperatively minimize a global objective function composed of a sum of local functions plus a regularizer. Through the use of intermediate consensus variables, we remove the need for inner communication loops between agents when computing curvature-guided updates. A general scheme is presented, which unifies the analysis for a plethora of computing choices, including gradient descent, Newton updates, and Broyden, Fletcher, Goldfarb, and Shanno updates. Our analysis establishes sublinear convergence rates under convex objective functions with Lipschitz continuous gradients, as well as linear convergence rates when the local functions are further assumed to be strongly convex. Moreover, we explicitly characterize the acceleration due to curvature information. Last but not the least, we present an asynchronous implementation for the proposed algorithms, which removes the need for a central clock, with linear convergence rates established in expectation under strongly convex objectives. We ascertain the effectiveness of the proposed methods with numerical experiments on benchmark datasets.

Original languageEnglish (US)
Pages (from-to)6573-6588
Number of pages16
JournalIEEE Transactions on Automatic Control
Volume68
Issue number11
DOIs
StatePublished - Nov 1 2023
Externally publishedYes

Keywords

  • Asynchronous algorithms
  • control
  • decentralized optimization
  • network analysis
  • primal-dual algorithms

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Communication Efficient Curvature Aided Primal-Dual Algorithms for Decentralized Optimization'. Together they form a unique fingerprint.

Cite this