{
  "id": "1712.06585",
  "version": "v1",
  "published": "2017-12-18T18:57:44.000Z",
  "updated": "2017-12-18T18:57:44.000Z",
  "title": "Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima",
  "authors": [
    "Yaodong Yu",
    "Pan Xu",
    "Quanquan Gu"
  ],
  "comment": "25 pages",
  "categories": [
    "math.OC",
    "cs.LG"
  ],
  "abstract": "We propose stochastic optimization algorithms that can find local minima faster than existing algorithms for nonconvex optimization problems, by exploiting the third-order smoothness to escape non-degenerate saddle points more efficiently. More specifically, the proposed algorithm only needs $\\tilde{O}(\\epsilon^{-10/3})$ stochastic gradient evaluations to converge to an approximate local minimum $\\mathbf{x}$, which satisfies $\\|\\nabla f(\\mathbf{x})\\|_2\\leq\\epsilon$ and $\\lambda_{\\min}(\\nabla^2 f(\\mathbf{x}))\\geq -\\sqrt{\\epsilon}$ in the general stochastic optimization setting, where $\\tilde{O}(\\cdot)$ hides logarithm polynomial terms and constants. This improves upon the $\\tilde{O}(\\epsilon^{-7/2})$ gradient complexity achieved by the state-of-the-art stochastic local minima finding algorithms by a factor of $\\tilde{O}(\\epsilon^{-1/6})$. For nonconvex finite-sum optimization, our algorithm also outperforms the best known algorithms in a certain regime.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-12-18T18:57:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "local minimum",
      "faster stochastic optimization algorithms",
      "third-order smoothness helps",
      "finding local minima",
      "local minima finding algorithms"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}