{
  "id": "1807.01280",
  "version": "v1",
  "published": "2018-07-03T16:56:14.000Z",
  "updated": "2018-07-03T16:56:14.000Z",
  "title": "On the Computational Power of Online Gradient Descent",
  "authors": [
    "Vaggos Chatziafratis",
    "Tim Roughgarden",
    "Joshua R. Wang"
  ],
  "categories": [
    "cs.LG",
    "stat.ML"
  ],
  "abstract": "We prove that the evolution of weight vectors in online gradient descent can encode arbitrary polynomial-space computations, even in the special case of soft-margin support vector machines. Our results imply that, under weak complexity-theoretic assumptions, it is impossible to reason efficiently about the fine-grained behavior of online gradient descent.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-07-03T16:56:14.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "online gradient descent",
      "computational power",
      "encode arbitrary polynomial-space computations",
      "soft-margin support vector machines",
      "weak complexity-theoretic assumptions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}