Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Distributed Newton Method Over Graphs: Can Sharing of Second-Order Information Eliminate the Condition Number Dependence?
KTH Royal Institute of Technology.ORCID iD: 0000-0002-8872-8885
Stockholm University, Faculty of Social Sciences, Department of Computer and Systems Sciences.ORCID iD: 0000-0002-6617-8683
KTH Royal Institute of Technology.
Number of Authors: 32021 (English)In: IEEE Signal Processing Letters, ISSN 1070-9908, E-ISSN 1558-2361, Vol. 28, p. 1180-1184Article in journal (Refereed) Published
Abstract [en]

One of the main advantages of second-order methods in a centralized setting is that they are insensitive to the condition number of the objective function's Hessian. For applications such as regression analysis, this means that less pre-processing of the data is required for the algorithm to work well, as the ill-conditioning caused by highly correlated variables will not be as problematic. Similar condition number independence has not yet been established for distributed methods. In this paper, we analyze the performance of a simple distributed second-order algorithm on quadratic problems and show that its convergence depends only logarithmically on the condition number. Our empirical results indicate that the use of second-order information can yield large efficiency improvements over first-order methods, both in terms of iterations and communications, when the condition number is of the same order of magnitude as the problem dimension.

Place, publisher, year, edition, pages
2021. Vol. 28, p. 1180-1184
Keywords [en]
Signal processing algorithms, Complexity theory, Optimization, Peer-to-peer computing, Convergence, Gradient methods, Linear regression, Distributed Algorithms, optimization
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:su:diva-196431DOI: 10.1109/LSP.2021.3084510ISI: 000664979700006OAI: oai:DiVA.org:su-196431DiVA, id: diva2:1592154
Available from: 2021-09-08 Created: 2021-09-08 Last updated: 2022-02-25Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Berglund, ErikMagnússon, Sindri

Search in DiVA

By author/editor
Berglund, ErikMagnússon, Sindri
By organisation
Department of Computer and Systems Sciences
In the same journal
IEEE Signal Processing Letters
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 25 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf