Supermartingales in prediction with expert advice

Alexey Chernov, Yuri Kalnishkan, Fedor Zhdanov

    Research output: Contribution to journalArticle

    Abstract

    We apply 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. We discuss also a new setting where the experts can give advice conditional on the learner's future decision. Both the algorithms can be adapted to the new setting and give the same performance guarantees as in the traditional setting. Finally, we outline an application of defensive forecasting to a setting with several loss functions.
    LanguageEnglish
    Pages2647-2669
    Number of pages23
    JournalTheoretical Computer Science
    Volume411
    Issue number29-30
    DOIs
    StatePublished - 17 Jun 2010

    Bibliographical note

    © 2010. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/

    Keywords

    • Prediction with expert advice
    • Defensive forecasting algorithm
    • Aggregating algorithm

    Cite this

    Chernov, A., Kalnishkan, Y., & Zhdanov, F. (2010). Supermartingales in prediction with expert advice. 411(29-30), 2647-2669. DOI: 10.1016/j.tcs.2010.04.003
    Chernov, Alexey ; Kalnishkan, Yuri ; Zhdanov, Fedor. / Supermartingales in prediction with expert advice. 2010 ; Vol. 411, No. 29-30. pp. 2647-2669
    @article{2e92bf8478514714b3477f7b7dad016a,
    title = "Supermartingales in prediction with expert advice",
    abstract = "We apply 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. We discuss also a new setting where the experts can give advice conditional on the learner's future decision. Both the algorithms can be adapted to the new setting and give the same performance guarantees as in the traditional setting. Finally, we outline an application of defensive forecasting to a setting with several loss functions.",
    keywords = "Prediction with expert advice, Defensive forecasting algorithm, Aggregating algorithm",
    author = "Alexey Chernov and Yuri Kalnishkan and Fedor Zhdanov",
    note = "\{circledC} 2010. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/",
    year = "2010",
    month = "6",
    day = "17",
    doi = "10.1016/j.tcs.2010.04.003",
    language = "English",
    volume = "411",
    pages = "2647--2669",
    number = "29-30",

    }

    Chernov, A, Kalnishkan, Y & Zhdanov, F 2010, 'Supermartingales in prediction with expert advice' vol 411, no. 29-30, pp. 2647-2669. DOI: 10.1016/j.tcs.2010.04.003

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

    Vol. 411, No. 29-30, 17.06.2010, p. 2647-2669.

    Research output: Contribution to journalArticle

    TY - JOUR

    T1 - Supermartingales in prediction with expert advice

    AU - Chernov,Alexey

    AU - Kalnishkan,Yuri

    AU - Zhdanov,Fedor

    N1 - © 2010. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/

    PY - 2010/6/17

    Y1 - 2010/6/17

    N2 - We apply 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. We discuss also a new setting where the experts can give advice conditional on the learner's future decision. Both the algorithms can be adapted to the new setting and give the same performance guarantees as in the traditional setting. Finally, we outline an application of defensive forecasting to a setting with several loss functions.

    AB - We apply 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. We discuss also a new setting where the experts can give advice conditional on the learner's future decision. Both the algorithms can be adapted to the new setting and give the same performance guarantees as in the traditional setting. Finally, we outline an application of defensive forecasting to a setting with several loss functions.

    KW - Prediction with expert advice

    KW - Defensive forecasting algorithm

    KW - Aggregating algorithm

    U2 - 10.1016/j.tcs.2010.04.003

    DO - 10.1016/j.tcs.2010.04.003

    M3 - Article

    VL - 411

    SP - 2647

    EP - 2669

    IS - 29-30

    ER -

    Chernov A, Kalnishkan Y, Zhdanov F. Supermartingales in prediction with expert advice. 2010 Jun 17;411(29-30):2647-2669. Available from, DOI: 10.1016/j.tcs.2010.04.003