{
  "id": "1805.08370",
  "version": "v1",
  "published": "2018-05-22T03:00:12.000Z",
  "updated": "2018-05-22T03:00:12.000Z",
  "title": "Cutting plane methods can be extended into nonconvex optimization",
  "authors": [
    "Oliver Hinder"
  ],
  "categories": [
    "math.OC",
    "cs.CC"
  ],
  "abstract": "We show that it is possible to obtain an $O(\\epsilon^{-4/3})$ runtime --- including computational cost --- for finding $\\epsilon$-stationary points of nonconvex functions using cutting plane methods. This improves on the best known epsilon dependence achieved by cubic regularized Newton of $O(\\epsilon^{-3/2})$ as proved by Nesterov and Polyak (2006)\\nocite{nesterov2006cubic}. Our techniques utilize the convex until proven guilty principle proposed by Carmon, Duchi, Hinder, and Sidford (2017)\\nocite{carmon2017convex}.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-22T03:00:12.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cutting plane methods",
      "nonconvex optimization",
      "proven guilty principle",
      "epsilon dependence",
      "computational cost"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}