The price of bandit information in multiclass online classification

Amit Daniely, Tom Helbertal
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:93-104, 2013.

Abstract

We consider two scenarios of multiclass online learning of a hypothesis class H⊆Y^X. In the \em full information scenario, the learner is exposed to instances together with their labels. In the \em bandit scenario, the true label is not exposed, but rather an indication whether the learner’s prediction is correct or not. We show that the ratio between the error rates in the two scenarios is at most 8⋅|Y|⋅\log(|Y|) in the realizable case, and \tildeO(\sqrt|Y|) in the agnostic case. The results are tight up to a logarithmic factor and essentially answer an open question from (Daniely et. al. - Multiclass learnability and the erm principle).We apply these results to the class of γ-margin multiclass linear classifiers in \mathbbR^d. We show that the bandit error rate of this class is \tildeΘ\left(\frac|Y|γ^2\right) in the realizable case and \tildeΘ\left(\frac1γ\sqrt|Y|T\right) in the agnostic case. This resolves an open question from (Kakade et. al. - Efficient bandit algorithms for onlinemulticlass prediction).

Cite this Paper

BibTeX
@InProceedings{pmlr-v30-Daniely13, title = {The price of bandit information in multiclass online classification}, author = {Daniely, Amit and Helbertal, Tom}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {93--104}, 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/Daniely13.pdf}, url = {https://proceedings.mlr.press/v30/Daniely13.html}, abstract = {We consider two scenarios of multiclass online learning of a hypothesis class H⊆Y^X. In the \em full information scenario, the learner is exposed to instances together with their labels. In the \em bandit scenario, the true label is not exposed, but rather an indication whether the learner’s prediction is correct or not. We show that the ratio between the error rates in the two scenarios is at most 8⋅|Y|⋅\log(|Y|) in the realizable case, and \tildeO(\sqrt|Y|) in the agnostic case. The results are tight up to a logarithmic factor and essentially answer an open question from (Daniely et. al. - Multiclass learnability and the erm principle).We apply these results to the class of γ-margin multiclass linear classifiers in \mathbbR^d. We show that the bandit error rate of this class is \tildeΘ\left(\frac|Y|γ^2\right) in the realizable case and \tildeΘ\left(\frac1γ\sqrt|Y|T\right) in the agnostic case. This resolves an open question from (Kakade et. al. - Efficient bandit algorithms for onlinemulticlass prediction).} }
Endnote
%0 Conference Paper %T The price of bandit information in multiclass online classification %A Amit Daniely %A Tom Helbertal %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-Daniely13 %I PMLR %P 93--104 %U https://proceedings.mlr.press/v30/Daniely13.html %V 30 %X We consider two scenarios of multiclass online learning of a hypothesis class H⊆Y^X. In the \em full information scenario, the learner is exposed to instances together with their labels. In the \em bandit scenario, the true label is not exposed, but rather an indication whether the learner’s prediction is correct or not. We show that the ratio between the error rates in the two scenarios is at most 8⋅|Y|⋅\log(|Y|) in the realizable case, and \tildeO(\sqrt|Y|) in the agnostic case. The results are tight up to a logarithmic factor and essentially answer an open question from (Daniely et. al. - Multiclass learnability and the erm principle).We apply these results to the class of γ-margin multiclass linear classifiers in \mathbbR^d. We show that the bandit error rate of this class is \tildeΘ\left(\frac|Y|γ^2\right) in the realizable case and \tildeΘ\left(\frac1γ\sqrt|Y|T\right) in the agnostic case. This resolves an open question from (Kakade et. al. - Efficient bandit algorithms for onlinemulticlass prediction).
RIS
TY - CPAPER TI - The price of bandit information in multiclass online classification AU - Amit Daniely AU - Tom Helbertal BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Daniely13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 93 EP - 104 L1 - http://proceedings.mlr.press/v30/Daniely13.pdf UR - https://proceedings.mlr.press/v30/Daniely13.html AB - We consider two scenarios of multiclass online learning of a hypothesis class H⊆Y^X. In the \em full information scenario, the learner is exposed to instances together with their labels. In the \em bandit scenario, the true label is not exposed, but rather an indication whether the learner’s prediction is correct or not. We show that the ratio between the error rates in the two scenarios is at most 8⋅|Y|⋅\log(|Y|) in the realizable case, and \tildeO(\sqrt|Y|) in the agnostic case. The results are tight up to a logarithmic factor and essentially answer an open question from (Daniely et. al. - Multiclass learnability and the erm principle).We apply these results to the class of γ-margin multiclass linear classifiers in \mathbbR^d. We show that the bandit error rate of this class is \tildeΘ\left(\frac|Y|γ^2\right) in the realizable case and \tildeΘ\left(\frac1γ\sqrt|Y|T\right) in the agnostic case. This resolves an open question from (Kakade et. al. - Efficient bandit algorithms for onlinemulticlass prediction). ER -
APA
Daniely, A. & Helbertal, T.. (2013). The price of bandit information in multiclass online classification. Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:93-104 Available from https://proceedings.mlr.press/v30/Daniely13.html.

Related Material