{
  "id": "1611.04982",
  "version": "v1",
  "published": "2016-11-15T18:41:55.000Z",
  "updated": "2016-11-15T18:41:55.000Z",
  "title": "Oracle Complexity of Second-Order Methods for Finite-Sum Problems",
  "authors": [
    "Yossi Arjevani",
    "Ohad Shamir"
  ],
  "comment": "23 pages",
  "categories": [
    "math.OC",
    "cs.LG",
    "stat.ML"
  ],
  "abstract": "Finite-sum optimization problems are ubiquitous in machine learning, and are commonly solved using first-order methods which rely on gradient computations. Recently, there has been growing interest in \\emph{second-order} methods, which rely on both gradients and Hessians. In principle, second-order methods can require much fewer iterations than first-order methods, and hold the promise for more efficient algorithms. Although computing and manipulating Hessians is prohibitive for high-dimensional problems in general, the Hessians of individual functions in finite-sum problems can often be efficiently computed, e.g. because they possess a low-rank structure. Can second-order information indeed be used to solve such problems more efficiently? In this paper, we provide evidence that the answer -- perhaps surprisingly -- is negative, at least in terms of worst-case guarantees. However, we also discuss what additional assumptions and algorithmic approaches might potentially circumvent this negative result.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-11-15T18:41:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "second-order methods",
      "finite-sum problems",
      "oracle complexity",
      "first-order methods",
      "finite-sum optimization problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}