{
  "id": "1512.09103",
  "version": "v1",
  "published": "2015-12-30T20:30:07.000Z",
  "updated": "2015-12-30T20:30:07.000Z",
  "title": "Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling",
  "authors": [
    "Zeyuan Allen-Zhu",
    "Yang Yuan"
  ],
  "categories": [
    "math.OC",
    "cs.DS",
    "math.NA",
    "stat.ML"
  ],
  "abstract": "Accelerated coordinate descent methods are widely used in optimization and machine learning. By taking cheap-to-compute coordinate gradients in each iteration, they are usually faster than accelerated full gradient descent, and thus suitable for large-scale optimization problems. In this paper, we improve the running time of accelerated coordinate descent, using a clean and novel non-uniform sampling method. In particular, if a function $f$ is coordinate-wise smooth with parameters $L_1,L_2,\\dots,L_n$, we obtain an algorithm that converges in $O(\\sum_i \\sqrt{L_i} / \\sqrt{\\varepsilon})$ iterations for convex $f$ and in $\\tilde{O}(\\sum_i \\sqrt{L_i} / \\sqrt{\\sigma})$ iterations for $\\sigma$-strongly convex $f$. The best known result was $\\tilde{O}(\\sqrt{n \\sum_i L_i} / \\sqrt{\\varepsilon})$ for convex $f$ and $\\tilde{O}(\\sqrt{n \\sum_i L_i} / \\sqrt{\\sigma})$ for $\\sigma$-strongly convex $f$, due to Lee and Sidford. Thus, our algorithm improves the running time by a factor up to $\\sqrt{n}$. Our speed-up naturally applies to important problems such as empirical risk minimizations and solving linear systems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-12-30T20:30:07.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "faster accelerated coordinate descent",
      "strongly convex",
      "running time",
      "novel non-uniform sampling method",
      "accelerated coordinate descent methods"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151209103A"
    }
  }
}