{
  "id": "1812.08485",
  "version": "v1",
  "published": "2018-12-20T11:13:24.000Z",
  "updated": "2018-12-20T11:13:24.000Z",
  "title": "First-order algorithms converge faster than $O(1/k)$ on convex problems",
  "authors": [
    "Ching-pei Lee",
    "Stephen J. Wright"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "It has been known for many years that both gradient descent and stochastic coordinate descent achieve a global convergence rate of $O(1/k)$ in the objective value, when applied to a scheme for minimizing a Lipschitz-continuously differentiable, unconstrained convex function. In this work, we improve this rate to $o(1/k)$. We extend the result to proximal gradient and proximal coordinate descent on regularized problems to show similar $o(1/k)$ convergence rates. The result is tight in the sense that an $O(1/k^{1+\\epsilon})$ rate is not generally attainable for any $\\epsilon>0$, for any of these methods.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-12-20T11:13:24.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "first-order algorithms converge faster",
      "convex problems",
      "stochastic coordinate descent achieve",
      "proximal coordinate descent",
      "global convergence rate"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}