A Hessian Inversion-Free Exact Second Order Method for Distributed Consensus Optimization

doi:10.1109/TSIPN.2022.3203860

2022-01-01

Dušan Jakovetić *

Nataša Krejić

Nataša Krklec Jerinkić

DOI：10.1109/TSIPN.2022.3203860

原文链接

原文求助

摘要

En 中文

We consider a standard distributed consensus optimization problem where a set of agents connected over an undirected network minimize the sum of their individual (local) strongly convex costs. Alternating Direction Method of Multipliers (ADMM) and Proximal Method of Multipliers (PMM) have been proved to be effective frameworks for design of exact distributed second order methods (involving calculation of local cost Hessians). However, existing methods involve explicit calculation of local Hessian inverses at each iteration that may be very costly when the dimension of the optimization variable is large. In this article, we develop a novel method, termed Inexact Newton method for Distributed Optimization (INDO), that alleviates the need for Hessian inverse calculation. INDO follows the PMM framework but, unlike existing work, approximates the Newton direction through a generic fixed point method (e.g., Jacobi Overrelaxation) that does not involve Hessian inverses. We prove exact global linear convergence of INDO and provide analytical studies on how the degree of inexactness in the Newton direction calculation affects the overall method's convergence factor. Numerical experiments on several real data sets demonstrate that INDO's speed is on par (or better) as state of the art methods iteration-wise, hence having a comparable communication cost. At the same time, for sufficiently large optimization problem dimensions n (even at n on the order of couple of hundreds), INDO achieves savings in computational cost by at least an order of magnitude.

Keyword:

Inexact Newton

proximal method of multipliers

distributed optimization

exact convergence

strongly convex problems

期刊

IEEE Transactions on Signal and Information Processing over Networks

IF:

4.9

论文数:

728

被引数:

1.9K

机构

University of Novi Sad

学者数:

9.3K

论文数: 6.2K

被引数: 5.0K

引用论文

IF0

PREAI

A comparative analysis of speech signal processing algorithms for Parkinson's disease classification and the use of the tunable Q-factor wavelet transform

APPLIED SOFT COMPUTING

IF6.6

2019-01-01

271

PREAI

Sakar, C. Okan; Serbes, Gorkem; Gunduz, Aysegul; Tunc, Hunkar C.; Nizam, Hatice; Sakar, Betul Erdogdu; Tutuncu, Melih; Aydin, Tarkan; Isenkul, M. Erdem; Apaydin, Hulya

Harnessing Smoothness to Accelerate Distributed Optimization

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS

IF5

2018-09-01

489