Supermartingales in Prediction with Expert Advice

Alexey Chernov, Yuri Kalnishkan, Fedor Zhdanov, Vladimir Vovk

    Research output: Chapter in Book/Report/Conference proceedingConference contribution with ISSN or ISBN

    Abstract

    This paper compares two methods of prediction with expert advice, the Aggregating Algorithm and the Defensive Forecasting, in two different settings. The first setting is traditional, with a countable number of experts and a finite number of outcomes. Surprisingly, these two methods of fundamentally different origin lead to identical procedures. In the second setting the experts can give advice conditional on the learner’s future decision. Both methods can be used in the new setting and give the same performance guarantees as in the traditional setting. However, whereas defensive forecasting can be applied directly, the AA requires substantial modifications.
    LanguageEnglish
    Title of host publication19th International Conference, ALT 2008
    Place of PublicationBerlin
    Pages199-213
    Number of pages15
    Volume5254
    DOIs
    StatePublished - 31 Dec 2008
    Event19th International Conference, ALT 2008 - Budapest, Hungary, October 13-16, 2008
    Duration: 31 Dec 2008 → …

    Conference

    Conference19th International Conference, ALT 2008
    Period31/12/08 → …

    Fingerprint

    Prediction
    Guarantee

    Bibliographical note

    The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-87987-9_19

    Cite this

    Chernov, A., Kalnishkan, Y., Zhdanov, F., & Vovk, V. (2008). Supermartingales in Prediction with Expert Advice. In 19th International Conference, ALT 2008 (Vol. 5254, pp. 199-213). Berlin. DOI: 10.1007/978-3-540-87987-9_19
    Chernov, Alexey ; Kalnishkan, Yuri ; Zhdanov, Fedor ; Vovk, Vladimir. / Supermartingales in Prediction with Expert Advice. 19th International Conference, ALT 2008. Vol. 5254 Berlin, 2008. pp. 199-213
    @inproceedings{0614eec51178427cafc2824a49548abc,
    title = "Supermartingales in Prediction with Expert Advice",
    abstract = "This paper compares two methods of prediction with expert advice, the Aggregating Algorithm and the Defensive Forecasting, in two different settings. The first setting is traditional, with a countable number of experts and a finite number of outcomes. Surprisingly, these two methods of fundamentally different origin lead to identical procedures. In the second setting the experts can give advice conditional on the learner’s future decision. Both methods can be used in the new setting and give the same performance guarantees as in the traditional setting. However, whereas defensive forecasting can be applied directly, the AA requires substantial modifications.",
    author = "Alexey Chernov and Yuri Kalnishkan and Fedor Zhdanov and Vladimir Vovk",
    note = "The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-87987-9_19",
    year = "2008",
    month = "12",
    day = "31",
    doi = "10.1007/978-3-540-87987-9_19",
    language = "English",
    volume = "5254",
    pages = "199--213",
    booktitle = "19th International Conference, ALT 2008",

    }

    Chernov, A, Kalnishkan, Y, Zhdanov, F & Vovk, V 2008, Supermartingales in Prediction with Expert Advice. in 19th International Conference, ALT 2008. vol. 5254, Berlin, pp. 199-213, 19th International Conference, ALT 2008, 31/12/08. DOI: 10.1007/978-3-540-87987-9_19

    Supermartingales in Prediction with Expert Advice. / Chernov, Alexey; Kalnishkan, Yuri; Zhdanov, Fedor; Vovk, Vladimir.

    19th International Conference, ALT 2008. Vol. 5254 Berlin, 2008. p. 199-213.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution with ISSN or ISBN

    TY - GEN

    T1 - Supermartingales in Prediction with Expert Advice

    AU - Chernov,Alexey

    AU - Kalnishkan,Yuri

    AU - Zhdanov,Fedor

    AU - Vovk,Vladimir

    N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-87987-9_19

    PY - 2008/12/31

    Y1 - 2008/12/31

    N2 - This paper compares two methods of prediction with expert advice, the Aggregating Algorithm and the Defensive Forecasting, in two different settings. The first setting is traditional, with a countable number of experts and a finite number of outcomes. Surprisingly, these two methods of fundamentally different origin lead to identical procedures. In the second setting the experts can give advice conditional on the learner’s future decision. Both methods can be used in the new setting and give the same performance guarantees as in the traditional setting. However, whereas defensive forecasting can be applied directly, the AA requires substantial modifications.

    AB - This paper compares two methods of prediction with expert advice, the Aggregating Algorithm and the Defensive Forecasting, in two different settings. The first setting is traditional, with a countable number of experts and a finite number of outcomes. Surprisingly, these two methods of fundamentally different origin lead to identical procedures. In the second setting the experts can give advice conditional on the learner’s future decision. Both methods can be used in the new setting and give the same performance guarantees as in the traditional setting. However, whereas defensive forecasting can be applied directly, the AA requires substantial modifications.

    U2 - 10.1007/978-3-540-87987-9_19

    DO - 10.1007/978-3-540-87987-9_19

    M3 - Conference contribution with ISSN or ISBN

    VL - 5254

    SP - 199

    EP - 213

    BT - 19th International Conference, ALT 2008

    CY - Berlin

    ER -

    Chernov A, Kalnishkan Y, Zhdanov F, Vovk V. Supermartingales in Prediction with Expert Advice. In 19th International Conference, ALT 2008. Vol. 5254. Berlin. 2008. p. 199-213. Available from, DOI: 10.1007/978-3-540-87987-9_19