{
  "id": "1501.06521",
  "version": "v1",
  "published": "2015-01-26T18:48:55.000Z",
  "updated": "2015-01-26T18:48:55.000Z",
  "title": "Tensor Prediction, Rademacher Complexity and Random 3-XOR",
  "authors": [
    "Boaz Barak",
    "Ankur Moitra"
  ],
  "comment": "20 pages",
  "categories": [
    "cs.LG",
    "cs.DS",
    "stat.ML"
  ],
  "abstract": "Here we study the tensor prediction problem, where the goal is to accurately predict the entries of a low rank, third-order tensor (with noise) given as few observations as possible. We give algorithms based on the sixth level of the sum-of-squares hierarchy that work with $m = \\tilde{O}(n^{3/2})$ observations, and we complement our result by showing that any attempt to solve tensor prediction with $m = O(n^{3/2 - \\epsilon})$ observations through the sum-of-squares hierarchy needs $\\Omega(n^{2 \\epsilon})$ rounds and consequently would run in moderately exponential time. In contrast, information theoretically $m = \\tilde{O}(n)$ observations suffice. Our approach is to characterize the Rademacher complexity of the sequence of norms that arise from the sum-of-squares hierarchy, and both our upper and lower bounds are based on establishing connections between tensor prediction and the task of strongly refuting random $3$-XOR formulas, and the resolution proof system.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-01-26T18:48:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "rademacher complexity",
      "sum-of-squares hierarchy needs",
      "tensor prediction problem",
      "resolution proof system",
      "observations suffice"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150106521B"
    }
  }
}