کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8941845 | 1645039 | 2018 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On minimaxity of Follow the Leader strategy in the stochastic setting
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On minimaxity of Follow the Leader strategy in the stochastic setting On minimaxity of Follow the Leader strategy in the stochastic setting](/preview/png/8941845.png)
چکیده انگلیسی
We consider the setting of prediction with expert advice with an additional assumption that each expert generates its losses i.i.d. according to some distribution. We first identify a class of “admissible” strategies, which we call permutation invariant, and show that every strategy outside this class will perform not better than some permutation invariant strategy. We then show that when the losses are binary, a simple Follow the Leader (FL) algorithm is the minimax strategy for this game, where minimaxity is simultaneously achieved for the expected regret, the pseudo-regret, and the excess risk. Furthermore, FL has also the smallest regret, pseudo-regret, and excess risk over all permutation invariant prediction strategies, simultaneously for all distributions over binary losses. We generalize these minimax results to the case in which each expert generates its losses from a distribution belonging to a one-dimensional exponential family, as well as to the case of loss vectors generated jointly from a multinomial distribution. We also show that when the losses are in the interval [0,1] and the learner competes against all distributions over [0,1], FL remains minimax only when an additional trick called “loss binarization” is applied.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 742, 19 September 2018, Pages 50-65
Journal: Theoretical Computer Science - Volume 742, 19 September 2018, Pages 50-65
نویسندگان
Wojciech KotÅowski,