Competitive on-line learning with a convex loss function
| dc.creator | Vovk, Vladimir | |
| dc.date | 2005-06-11 | |
| dc.date | 2005-09-02 | |
| dc.date.accessioned | 2026-07-07T03:23:07Z | |
| dc.date.available | 2026-07-07T03:23:07Z | |
| dc.description | 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. | |
| dc.description | 26 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0506041 | |
| dc.identifier | http://arxiv.org/abs/cs/0506041 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32817 | |
| dc.subject | Machine Learning | |
| dc.subject | Artificial Intelligence | |
| dc.subject | I.2.6; I.5.1 | |
| dc.title | Competitive on-line learning with a convex loss function | |
| dc.type | text |