Supermartingales in prediction with expert advice. / Chernov, Alexey; Kalnishkan, Yuri; Zhdanov, Fedor; Vovk, Vladimir.

In: Theoretical Computer Science, Vol. 411, No. 29-30, 17.06.2010, p. 2647-2669.

Research output: Contribution to journalArticle

Published

Standard

Supermartingales in prediction with expert advice. / Chernov, Alexey; Kalnishkan, Yuri; Zhdanov, Fedor; Vovk, Vladimir.

In: Theoretical Computer Science, Vol. 411, No. 29-30, 17.06.2010, p. 2647-2669.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Chernov, Alexey ; Kalnishkan, Yuri ; Zhdanov, Fedor ; Vovk, Vladimir. / Supermartingales in prediction with expert advice. In: Theoretical Computer Science. 2010 ; Vol. 411, No. 29-30. pp. 2647-2669.

BibTeX

@article{4dd8483e28074f63b6c495f269a6f73b,
title = "Supermartingales in prediction with expert advice",
abstract = "The paper applies the method of defensive forecasting, based on the use of game-theoretic supermartingales, to prediction with expert advice. In the traditional setting of a countable number of experts and a finite number of outcomes, the Defensive Forecasting algorithm is very close to the well-known Aggregating Algorithm. Not only the performance guarantees but also the predictions are the same for these two methods of fundamentally different nature.The paper introduces a new setting where the experts can give advice conditional on the learner's future decision. Both the Defensive Forecasting algorithm and the Aggregating Algorithm can be adapted to the new setting and give the same performance guarantees as in the traditional setting. Also the paper outlines an application of the Defensive Forecasting algorithm to a setting with multiple loss functions.",
keywords = "Prediction with expert advice, Defensive forecasting algorithm, Aggregating algorithm, PROPER SCORING RULES, INTERNAL REGRET",
author = "Alexey Chernov and Yuri Kalnishkan and Fedor Zhdanov and Vladimir Vovk",
year = "2010",
month = jun,
day = "17",
doi = "10.1016/j.tcs.2010.04.003",
language = "English",
volume = "411",
pages = "2647--2669",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "29-30",

}

RIS

TY - JOUR

T1 - Supermartingales in prediction with expert advice

AU - Chernov, Alexey

AU - Kalnishkan, Yuri

AU - Zhdanov, Fedor

AU - Vovk, Vladimir

PY - 2010/6/17

Y1 - 2010/6/17

N2 - The paper applies the method of defensive forecasting, based on the use of game-theoretic supermartingales, to prediction with expert advice. In the traditional setting of a countable number of experts and a finite number of outcomes, the Defensive Forecasting algorithm is very close to the well-known Aggregating Algorithm. Not only the performance guarantees but also the predictions are the same for these two methods of fundamentally different nature.The paper introduces a new setting where the experts can give advice conditional on the learner's future decision. Both the Defensive Forecasting algorithm and the Aggregating Algorithm can be adapted to the new setting and give the same performance guarantees as in the traditional setting. Also the paper outlines an application of the Defensive Forecasting algorithm to a setting with multiple loss functions.

AB - The paper applies the method of defensive forecasting, based on the use of game-theoretic supermartingales, to prediction with expert advice. In the traditional setting of a countable number of experts and a finite number of outcomes, the Defensive Forecasting algorithm is very close to the well-known Aggregating Algorithm. Not only the performance guarantees but also the predictions are the same for these two methods of fundamentally different nature.The paper introduces a new setting where the experts can give advice conditional on the learner's future decision. Both the Defensive Forecasting algorithm and the Aggregating Algorithm can be adapted to the new setting and give the same performance guarantees as in the traditional setting. Also the paper outlines an application of the Defensive Forecasting algorithm to a setting with multiple loss functions.

KW - Prediction with expert advice

KW - Defensive forecasting algorithm

KW - Aggregating algorithm

KW - PROPER SCORING RULES

KW - INTERNAL REGRET

U2 - 10.1016/j.tcs.2010.04.003

DO - 10.1016/j.tcs.2010.04.003

M3 - Article

VL - 411

SP - 2647

EP - 2669

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 29-30

ER -