Regret Minimization for Branching Experts

Eyal Gofer, Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:618-638, 2013.

Abstract

We study regret minimization bounds in which the dependence on the number of experts is replaced by measures of the realized complexity of the expert class. The measures we consider are defined in retrospect given the realized losses. We concentrate on two interesting cases. In the first, our measure of complexity is the number of different “leading experts”, namely, experts that were best at some point in time. We derive regret bounds that depend only on this measure, independent of the total number of experts. We also consider a case where all experts remain grouped in just a few clusters in terms of their realized cumulative losses. Here too, our regret bounds depend only on the number of clusters determined in retrospect, which serves as a measure of complexity. Our results are obtained as special cases of a more general analysis for a setting of branching experts,where the set of experts may grow over time according to a tree-like structure, determined by an adversary. For this setting of branching experts, we give algorithms and analysis that cover both the full information and the bandit scenarios.

Cite this Paper

BibTeX
@InProceedings{pmlr-v30-Gofer13, title = {Regret Minimization for Branching Experts}, author = {Gofer, Eyal and Cesa-Bianchi, Nicolò and Gentile, Claudio and Mansour, Yishay}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {618--638}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Gofer13.pdf}, url = {https://proceedings.mlr.press/v30/Gofer13.html}, abstract = {We study regret minimization bounds in which the dependence on the number of experts is replaced by measures of the realized complexity of the expert class. The measures we consider are defined in retrospect given the realized losses. We concentrate on two interesting cases. In the first, our measure of complexity is the number of different “leading experts”, namely, experts that were best at some point in time. We derive regret bounds that depend only on this measure, independent of the total number of experts. We also consider a case where all experts remain grouped in just a few clusters in terms of their realized cumulative losses. Here too, our regret bounds depend only on the number of clusters determined in retrospect, which serves as a measure of complexity. Our results are obtained as special cases of a more general analysis for a setting of branching experts,where the set of experts may grow over time according to a tree-like structure, determined by an adversary. For this setting of branching experts, we give algorithms and analysis that cover both the full information and the bandit scenarios.} }
Endnote
%0 Conference Paper %T Regret Minimization for Branching Experts %A Eyal Gofer %A Nicolò Cesa-Bianchi %A Claudio Gentile %A Yishay Mansour %B Proceedings of the 26th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Gofer13 %I PMLR %P 618--638 %U https://proceedings.mlr.press/v30/Gofer13.html %V 30 %X We study regret minimization bounds in which the dependence on the number of experts is replaced by measures of the realized complexity of the expert class. The measures we consider are defined in retrospect given the realized losses. We concentrate on two interesting cases. In the first, our measure of complexity is the number of different “leading experts”, namely, experts that were best at some point in time. We derive regret bounds that depend only on this measure, independent of the total number of experts. We also consider a case where all experts remain grouped in just a few clusters in terms of their realized cumulative losses. Here too, our regret bounds depend only on the number of clusters determined in retrospect, which serves as a measure of complexity. Our results are obtained as special cases of a more general analysis for a setting of branching experts,where the set of experts may grow over time according to a tree-like structure, determined by an adversary. For this setting of branching experts, we give algorithms and analysis that cover both the full information and the bandit scenarios.
RIS
TY - CPAPER TI - Regret Minimization for Branching Experts AU - Eyal Gofer AU - Nicolò Cesa-Bianchi AU - Claudio Gentile AU - Yishay Mansour BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Gofer13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 618 EP - 638 L1 - http://proceedings.mlr.press/v30/Gofer13.pdf UR - https://proceedings.mlr.press/v30/Gofer13.html AB - We study regret minimization bounds in which the dependence on the number of experts is replaced by measures of the realized complexity of the expert class. The measures we consider are defined in retrospect given the realized losses. We concentrate on two interesting cases. In the first, our measure of complexity is the number of different “leading experts”, namely, experts that were best at some point in time. We derive regret bounds that depend only on this measure, independent of the total number of experts. We also consider a case where all experts remain grouped in just a few clusters in terms of their realized cumulative losses. Here too, our regret bounds depend only on the number of clusters determined in retrospect, which serves as a measure of complexity. Our results are obtained as special cases of a more general analysis for a setting of branching experts,where the set of experts may grow over time according to a tree-like structure, determined by an adversary. For this setting of branching experts, we give algorithms and analysis that cover both the full information and the bandit scenarios. ER -
APA
Gofer, E., Cesa-Bianchi, N., Gentile, C. & Mansour, Y.. (2013). Regret Minimization for Branching Experts. Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:618-638 Available from https://proceedings.mlr.press/v30/Gofer13.html.

Related Material