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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Forthcoming

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Adamskiy, M, Koolen, W, Chernov, A & Vovk, V 2012, A closer look at adaptive regret. in N Bshouty, G Stoltz, N Vayatis & T Zeugmann (eds), *Proceedings of the Twenty Third International Conference on Algorithmic Learning Theory.* vol. 7568, Lecture Notes in Artificial Intelligence, Springer, Berlin, pp. 290 - 304.

Adamskiy, M., Koolen, W., Chernov, A., & Vovk, V. (Accepted/In press). A closer look at adaptive regret. In N. Bshouty, G. Stoltz, N. Vayatis, & T. Zeugmann (Eds.), *Proceedings of the Twenty Third International Conference on Algorithmic Learning Theory *(Vol. 7568, pp. 290 - 304). (Lecture Notes in Artificial Intelligence). Springer.

Adamskiy M, Koolen W, Chernov A, Vovk V. A closer look at adaptive regret. In Bshouty N, Stoltz G, Vayatis N, Zeugmann T, editors, Proceedings of the Twenty Third International Conference on Algorithmic Learning Theory. Vol. 7568. Berlin: Springer. 2012. p. 290 - 304. (Lecture Notes in Artificial Intelligence).

@inproceedings{f7c5d8d8c04348f39c2b3680bc6b3ff4,

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_1,t_2] is the loss of the algorithm there minus the loss of the best expert. Adaptive regret measures how well the algorithm approximates the best expert locally, and it is therefore somewhere between the classical regret (measured on all outcomes) and the tracking regret, where the algorithm is compared to a good sequence of experts.We investigate two existing intuitive methods to derive 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. Our main result is a thorough analysis of the adaptive regret of Fixed Share. We obtain the exact worst-case adaptive regret for Fixed Share, from which the classical tracking bounds can be derived. We also prove that Fixed Share is optimal, in the sense that no algorithm can have a better adaptive regret bound.",

keywords = "online learning, adaptive regret, Fixed Share, specialist experts",

author = "Mitya Adamskiy and Wouter Koolen and Alexey Chernov and Vladimir Vovk",

year = "2012",

language = "English",

volume = "7568",

series = "Lecture Notes in Artificial Intelligence",

publisher = "Springer",

pages = "290 -- 304",

editor = "Nader Bshouty and Gilles Stoltz and Nicolas Vayatis and Thomas Zeugmann",

booktitle = "Proceedings of the Twenty Third International Conference on Algorithmic Learning Theory",

}

TY - GEN

T1 - A closer look at adaptive regret

AU - Adamskiy, Mitya

AU - Koolen, Wouter

AU - Chernov, Alexey

AU - Vovk, Vladimir

PY - 2012

Y1 - 2012

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_1,t_2] is the loss of the algorithm there minus the loss of the best expert. Adaptive regret measures how well the algorithm approximates the best expert locally, and it is therefore somewhere between the classical regret (measured on all outcomes) and the tracking regret, where the algorithm is compared to a good sequence of experts.We investigate two existing intuitive methods to derive 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. Our main result is a thorough analysis of the adaptive regret of Fixed Share. We obtain the exact worst-case adaptive regret for Fixed Share, from which the classical tracking bounds can be derived. We also prove that Fixed Share is optimal, in the sense that no algorithm can have a better adaptive regret bound.

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_1,t_2] is the loss of the algorithm there minus the loss of the best expert. Adaptive regret measures how well the algorithm approximates the best expert locally, and it is therefore somewhere between the classical regret (measured on all outcomes) and the tracking regret, where the algorithm is compared to a good sequence of experts.We investigate two existing intuitive methods to derive 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. Our main result is a thorough analysis of the adaptive regret of Fixed Share. We obtain the exact worst-case adaptive regret for Fixed Share, from which the classical tracking bounds can be derived. We also prove that Fixed Share is optimal, in the sense that no algorithm can have a better adaptive regret bound.

KW - online learning

KW - adaptive regret

KW - Fixed Share

KW - specialist experts

M3 - Conference contribution

VL - 7568

T3 - Lecture Notes in Artificial Intelligence

SP - 290

EP - 304

BT - Proceedings of the Twenty Third International Conference on Algorithmic Learning Theory

A2 - Bshouty, Nader

A2 - Stoltz, Gilles

A2 - Vayatis, Nicolas

A2 - Zeugmann, Thomas

PB - Springer

CY - Berlin

ER -