Achieving Globally Superlinear Convergence for Distributed Optimization with Adaptive Newton Method

Jiaqi Zhang, Keyou You, Tamer Basar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we study the distributed optimization problem over a peer-to-peer network, where nodes optimize the sum of local objective functions via local computation and communicating with neighbors. Most existing algorithms cannot achieve globally superlinear convergence since they rely on either asymptotic consensus methods with linear convergence rates that bottleneck the global rate, or the pure Newton method that converges only locally. To this end, we introduce a finite-time set-consensus method, and then incorporate it into Polyak's adaptive Newton method, leading to our distributed adaptive Newton algorithm (DAN). Then, we propose a communication-efficient version of DAN called DAN-LA, which adopts a low-rank approximation idea to compress the Hessian and reduce the size of transmitted messages from O(p2) to O(p), where p is the dimension of decision vectors. We show that DAN and DAN-LA can globally achieve quadratic and superlinear convergence rates, respectively. Numerical experiments are conducted to show the advantages over existing methods.

Original languageEnglish (US)
Title of host publication2020 59th IEEE Conference on Decision and Control, CDC 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2329-2334
Number of pages6
ISBN (Electronic)9781728174471
DOIs
StatePublished - Dec 14 2020
Externally publishedYes
Event59th IEEE Conference on Decision and Control, CDC 2020 - Virtual, Jeju Island, Korea, Republic of
Duration: Dec 14 2020Dec 18 2020

Publication series

NameProceedings of the IEEE Conference on Decision and Control
Volume2020-December
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370

Conference

Conference59th IEEE Conference on Decision and Control, CDC 2020
Country/TerritoryKorea, Republic of
CityVirtual, Jeju Island
Period12/14/2012/18/20

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint

Dive into the research topics of 'Achieving Globally Superlinear Convergence for Distributed Optimization with Adaptive Newton Method'. Together they form a unique fingerprint.

Cite this