{
  "id": "1303.4645",
  "version": "v2",
  "published": "2013-03-19T16:03:17.000Z",
  "updated": "2013-09-08T01:17:22.000Z",
  "title": "Gradient methods for convex minimization: better rates under weaker conditions",
  "authors": [
    "Hui Zhang",
    "Wotao Yin"
  ],
  "comment": "20 pages, 4 figures, typos are corrected, Theorem 2 is new",
  "categories": [
    "math.OC",
    "cs.IT",
    "math.IT",
    "math.NA"
  ],
  "abstract": "The convergence behavior of gradient methods for minimizing convex differentiable functions is one of the core questions in convex optimization. This paper shows that their well-known complexities can be achieved under conditions weaker than the commonly accepted ones. We relax the common gradient Lipschitz-continuity condition and strong convexity condition to ones that hold only over certain line segments. Specifically, we establish complexities $O(\\frac{R}{\\epsilon})$ and $O(\\sqrt{\\frac{R}{\\epsilon}})$ for the ordinary and accelerate gradient methods, respectively, assuming that $\\nabla f$ is Lipschitz continuous with constant $R$ over the line segment joining $x$ and $x-\\frac{1}{R}\\nabla f$ for each $x\\in\\dom f$. Then we improve them to $O(\\frac{R}{\\nu}\\log(\\frac{1}{\\epsilon}))$ and $O(\\sqrt{\\frac{R}{\\nu}}\\log(\\frac{1}{\\epsilon}))$ for function $f$ that also satisfies the secant inequality $\\ < \\nabla f(x), x- x^*\\ > \\ge \\nu\\|x-x^*\\|^2$ for each $x\\in \\dom f$ and its projection $x^*$ to the minimizer set of $f$. The secant condition is also shown to be necessary for the geometric decay of solution error. Not only are the relaxed conditions met by more functions, the restrictions give smaller $R$ and larger $\\nu$ than they are without the restrictions and thus lead to better complexity bounds. We apply these results to sparse optimization and demonstrate a faster algorithm.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-09-08T01:17:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "convex minimization",
      "weaker conditions",
      "better rates",
      "common gradient lipschitz-continuity condition",
      "line segment"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1303.4645Z"
    }
  }
}