{
  "id": "1509.09002",
  "version": "v1",
  "published": "2015-09-30T03:02:59.000Z",
  "updated": "2015-09-30T03:02:59.000Z",
  "title": "Convergence of Stochastic Gradient Descent for PCA",
  "authors": [
    "Ohad Shamir"
  ],
  "comment": "18 pages",
  "categories": [
    "cs.LG",
    "math.OC",
    "stat.ML"
  ],
  "abstract": "We consider the problem of principal component analysis (PCA) in a streaming stochastic setting, where our goal is to find a direction of approximate maximal variance, based on a stream of i.i.d. data points in $\\mathbb{R}^d$. A simple and computationally cheap algorithm for this is stochastic gradient descent (SGD), which incrementally updates its estimate based on each new data point. However, due to the non-convex nature of the problem, analyzing its performance has been a challenge. In particular, existing guarantees rely on a non-trivial eigengap assumption on the covariance matrix, which is intuitively unnecessary. In this note, we provide (to the best of our knowledge) the first eigengap-free convergence guarantees for SGD in the context of PCA. This also partially resolves an open problem posed in [Hardt and Price, 2014].",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-09-30T03:02:59.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "stochastic gradient descent",
      "data point",
      "first eigengap-free convergence guarantees",
      "approximate maximal variance",
      "non-trivial eigengap assumption"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150909002S"
    }
  }
}