{
  "id": "cs/0512059",
  "version": "v2",
  "published": "2005-12-14T20:03:30.000Z",
  "updated": "2006-01-25T17:36:52.000Z",
  "title": "Competing with wild prediction rules",
  "authors": [
    "Vladimir Vovk"
  ],
  "comment": "28 pages, 3 figures",
  "categories": [
    "cs.LG"
  ],
  "abstract": "We consider the problem of on-line prediction competitive with a benchmark class of continuous but highly irregular prediction rules. It is known that if the benchmark class is a reproducing kernel Hilbert space, there exists a prediction algorithm whose average loss over the first N examples does not exceed the average loss of any prediction rule in the class plus a \"regret term\" of O(N^(-1/2)). The elements of some natural benchmark classes, however, are so irregular that these classes are not Hilbert spaces. In this paper we develop Banach-space methods to construct a prediction algorithm with a regret term of O(N^(-1/p)), where p is in [2,infty) and p-2 reflects the degree to which the benchmark class fails to be a Hilbert space.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2006-01-25T17:36:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "I.2.6"
    ],
    "keywords": [
      "wild prediction rules",
      "prediction algorithm",
      "average loss",
      "regret term",
      "natural benchmark classes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005cs.......12059V"
    }
  }
}