A closer look at adaptive regret

Dmitry Adamskiy, Wouter Koolen, Alexey Chernov, Vladimir Vovk

    Research output: Contribution to journalArticle

    Abstract

    For the prediction with expert advice setting, we consider methods to construct algorithms that have low adaptive regret. The adaptive regret of an algorithm on a time interval [t,T] is the loss of the algorithm minus the loss of the best expert over that interval. Adaptive regret measures how well the algorithm approximates the best expert locally, and so is different from, although closely related to, both the classical regret, measured over an initial time interval [1,t], and the tracking regret, where the algorithm is compared to a good sequence of experts over [1,t]. We investigate two existing intuitive methods for deriving algorithms with low adaptive regret, one based on specialist experts and the other based on restarts. Quite surprisingly, we show that both methods lead to the same algorithm, namely Fixed Share, which is known for its tracking regret. We provide a thorough analysis of the adaptive regret of Fixed Share. We obtain the exact worst-case adaptive regret for Fixed Share, from whichthe classical tracking bounds follow. We prove that Fixed Share is optimal for adaptive regret: the worst-case adaptive regret of any algorithm is at least that of an instance ofFixed Share.
    LanguageEnglish
    Pages1-21
    Number of pages21
    JournalThe Journal of Machine Learning Research
    Volume17
    Issue number23
    StatePublished - 1 Apr 2016

    Bibliographical note

    © 2016 Dmitry Adamskiy, Wouter M. Koolen, Alexey Chernov and Vladimir Vovk

    Keywords

    • Online learning
    • adaptive regret
    • Fixed Share
    • specialist experts

    Cite this

    Adamskiy, D., Koolen, W., Chernov, A., & Vovk, V. (2016). A closer look at adaptive regret. 17(23), 1-21.
    Adamskiy, Dmitry ; Koolen, Wouter ; Chernov, Alexey ; Vovk, Vladimir. / A closer look at adaptive regret. 2016 ; Vol. 17, No. 23. pp. 1-21
    @article{d779a7129c8d44daa435908e644334b5,
    title = "A closer look at adaptive regret",
    abstract = "For the prediction with expert advice setting, we consider methods to construct algorithms that have low adaptive regret. The adaptive regret of an algorithm on a time interval [t,T] is the loss of the algorithm minus the loss of the best expert over that interval. Adaptive regret measures how well the algorithm approximates the best expert locally, and so is different from, although closely related to, both the classical regret, measured over an initial time interval [1,t], and the tracking regret, where the algorithm is compared to a good sequence of experts over [1,t]. We investigate two existing intuitive methods for deriving algorithms with low adaptive regret, one based on specialist experts and the other based on restarts. Quite surprisingly, we show that both methods lead to the same algorithm, namely Fixed Share, which is known for its tracking regret. We provide a thorough analysis of the adaptive regret of Fixed Share. We obtain the exact worst-case adaptive regret for Fixed Share, from whichthe classical tracking bounds follow. We prove that Fixed Share is optimal for adaptive regret: the worst-case adaptive regret of any algorithm is at least that of an instance ofFixed Share.",
    keywords = "Online learning, adaptive regret, Fixed Share, specialist experts",
    author = "Dmitry Adamskiy and Wouter Koolen and Alexey Chernov and Vladimir Vovk",
    note = "\{circledC} 2016 Dmitry Adamskiy, Wouter M. Koolen, Alexey Chernov and Vladimir Vovk",
    year = "2016",
    month = "4",
    day = "1",
    language = "English",
    volume = "17",
    pages = "1--21",
    number = "23",

    }

    Adamskiy, D, Koolen, W, Chernov, A & Vovk, V 2016, 'A closer look at adaptive regret' vol 17, no. 23, pp. 1-21.

    A closer look at adaptive regret. / Adamskiy, Dmitry; Koolen, Wouter; Chernov, Alexey; Vovk, Vladimir.

    Vol. 17, No. 23, 01.04.2016, p. 1-21.

    Research output: Contribution to journalArticle

    TY - JOUR

    T1 - A closer look at adaptive regret

    AU - Adamskiy,Dmitry

    AU - Koolen,Wouter

    AU - Chernov,Alexey

    AU - Vovk,Vladimir

    N1 - © 2016 Dmitry Adamskiy, Wouter M. Koolen, Alexey Chernov and Vladimir Vovk

    PY - 2016/4/1

    Y1 - 2016/4/1

    N2 - For the prediction with expert advice setting, we consider methods to construct algorithms that have low adaptive regret. The adaptive regret of an algorithm on a time interval [t,T] is the loss of the algorithm minus the loss of the best expert over that interval. Adaptive regret measures how well the algorithm approximates the best expert locally, and so is different from, although closely related to, both the classical regret, measured over an initial time interval [1,t], and the tracking regret, where the algorithm is compared to a good sequence of experts over [1,t]. We investigate two existing intuitive methods for deriving algorithms with low adaptive regret, one based on specialist experts and the other based on restarts. Quite surprisingly, we show that both methods lead to the same algorithm, namely Fixed Share, which is known for its tracking regret. We provide a thorough analysis of the adaptive regret of Fixed Share. We obtain the exact worst-case adaptive regret for Fixed Share, from whichthe classical tracking bounds follow. We prove that Fixed Share is optimal for adaptive regret: the worst-case adaptive regret of any algorithm is at least that of an instance ofFixed Share.

    AB - For the prediction with expert advice setting, we consider methods to construct algorithms that have low adaptive regret. The adaptive regret of an algorithm on a time interval [t,T] is the loss of the algorithm minus the loss of the best expert over that interval. Adaptive regret measures how well the algorithm approximates the best expert locally, and so is different from, although closely related to, both the classical regret, measured over an initial time interval [1,t], and the tracking regret, where the algorithm is compared to a good sequence of experts over [1,t]. We investigate two existing intuitive methods for deriving algorithms with low adaptive regret, one based on specialist experts and the other based on restarts. Quite surprisingly, we show that both methods lead to the same algorithm, namely Fixed Share, which is known for its tracking regret. We provide a thorough analysis of the adaptive regret of Fixed Share. We obtain the exact worst-case adaptive regret for Fixed Share, from whichthe classical tracking bounds follow. We prove that Fixed Share is optimal for adaptive regret: the worst-case adaptive regret of any algorithm is at least that of an instance ofFixed Share.

    KW - Online learning

    KW - adaptive regret

    KW - Fixed Share

    KW - specialist experts

    M3 - Article

    VL - 17

    SP - 1

    EP - 21

    IS - 23

    ER -

    Adamskiy D, Koolen W, Chernov A, Vovk V. A closer look at adaptive regret. 2016 Apr 1;17(23):1-21.