{
  "id": "1206.4678",
  "version": "v1",
  "published": "2012-06-18T15:37:23.000Z",
  "updated": "2012-06-18T15:37:23.000Z",
  "title": "Linear Regression with Limited Observation",
  "authors": [
    "Elad Hazan",
    "Tomer Koren"
  ],
  "comment": "ICML2012",
  "categories": [
    "cs.LG",
    "stat.ML"
  ],
  "abstract": "We consider the most common variants of linear regression, including Ridge, Lasso and Support-vector regression, in a setting where the learner is allowed to observe only a fixed number of attributes of each example at training time. We present simple and efficient algorithms for these problems: for Lasso and Ridge regression they need the same total number of attributes (up to constants) as do full-information algorithms, for reaching a certain accuracy. For Support-vector regression, we require exponentially less attributes compared to the state of the art. By that, we resolve an open problem recently posed by Cesa-Bianchi et al. (2010). Experiments show the theoretical bounds to be justified by superior performance compared to the state of the art.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-06-18T15:37:23.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "linear regression",
      "limited observation",
      "support-vector regression",
      "attributes",
      "common variants"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1206.4678H"
    }
  }
}