{
  "id": "1504.06017",
  "version": "v1",
  "published": "2015-04-23T00:57:23.000Z",
  "updated": "2015-04-23T00:57:23.000Z",
  "title": "Network Newton-Part I: Algorithm and Convergence",
  "authors": [
    "Aryan Mokhtari",
    "Qing Ling",
    "Alejandro Ribeiro"
  ],
  "comment": "13 pages, submitted to a journal",
  "categories": [
    "math.OC"
  ],
  "abstract": "We study the problem of minimizing a sum of convex objective functions where the components of the objective are available at different nodes of a network and nodes are allowed to only communicate with their neighbors. The use of distributed gradient methods is a common approach to solve this problem. Their popularity notwithstanding, these methods exhibit slow convergence and a consequent large number of communications between nodes to approach the optimal argument because they rely on first order information only. This paper proposes the network Newton (NN) method as a distributed algorithm that incorporates second order information. This is done via distributed implementation of approximations of a suitably chosen Newton step. The approximations are obtained by truncation of the Newton step's Taylor expansion. This leads to a family of methods defined by the number $K$ of Taylor series terms kept in the approximation. When keeping $K$ terms of the Taylor series, the method is called NN-$K$ and can be implemented through the aggregation of information in $K$-hop neighborhoods. Convergence to a point close to the optimal argument at a rate that is at least linear is proven and the existence of a tradeoff between convergence time and the distance to the optimal argument is shown. Convergence rate, several practical implementation matters, and numerical analyses are presented in a companion paper [3].",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-04-23T00:57:23.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "convergence",
      "network newton-part",
      "optimal argument",
      "taylor series terms kept",
      "newton steps taylor expansion"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150406017M"
    }
  }
}