{
  "id": "cs/0506041",
  "version": "v3",
  "published": "2005-06-11T18:11:22.000Z",
  "updated": "2005-09-02T14:27:18.000Z",
  "title": "Competitive on-line learning with a convex loss function",
  "authors": [
    "Vladimir Vovk"
  ],
  "comment": "26 pages",
  "categories": [
    "cs.LG",
    "cs.AI"
  ],
  "abstract": "We consider the problem of sequential decision making under uncertainty in which the loss caused by a decision depends on the following binary observation. In competitive on-line learning, the goal is to design decision algorithms that are almost as good as the best decision rules in a wide benchmark class, without making any assumptions about the way the observations are generated. However, standard algorithms in this area can only deal with finite-dimensional (often countable) benchmark classes. In this paper we give similar results for decision rules ranging over an arbitrary reproducing kernel Hilbert space. For example, it is shown that for a wide class of loss functions (including the standard square, absolute, and log loss functions) the average loss of the master algorithm, over the first $N$ observations, does not exceed the average loss of the best decision rule with a bounded norm plus $O(N^{-1/2})$. Our proof technique is very different from the standard ones and is based on recent results about defensive forecasting. Given the probabilities produced by a defensive forecasting algorithm, which are known to be well calibrated and to have good resolution in the long run, we use the expected loss minimization principle to find a suitable decision.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2005-09-02T14:27:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "I.2.6",
      "I.5.1"
    ],
    "keywords": [
      "competitive on-line learning",
      "convex loss function",
      "best decision rule",
      "average loss",
      "arbitrary reproducing kernel hilbert space"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005cs........6041V"
    }
  }
}