{
  "id": "1611.08022",
  "version": "v1",
  "published": "2016-11-23T22:27:29.000Z",
  "updated": "2016-11-23T22:27:29.000Z",
  "title": "A Stronger Convergence Result on the Proximal Incremental Aggregated Gradient Method",
  "authors": [
    "Nuri Denizcan Vanli",
    "Mert Gurbuzbalaban",
    "Asu Ozdaglar"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "We study the convergence rate of the proximal incremental aggregated gradient (PIAG) method for minimizing the sum of a large number of smooth component functions (where the sum is strongly convex) and a non-smooth convex function. At each iteration, the PIAG method moves along an aggregated gradient formed by incrementally updating gradients of component functions at least once in the last $K$ iterations and takes a proximal step with respect to the non-smooth function. We show that the PIAG algorithm attains an iteration complexity that grows linear in the condition number of the problem and the delay parameter $K$. This improves upon the previously best known global linear convergence rate of the PIAG algorithm in the literature which has a quadratic dependence on $K$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-11-23T22:27:29.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "proximal incremental aggregated gradient method",
      "stronger convergence result",
      "global linear convergence rate",
      "piag algorithm",
      "component functions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}