Apple Tasting: Combinatorial Dimensions and Minimax Rates

Vinod Raman, Unique Subedi, Ananth Raman, Ambuj Tewari
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4358-4380, 2024.

Abstract

In online binary classification under \emph{apple tasting} feedback, the learner only observes the true label if it predicts “1". First studied by Helmbold et al. (2000a), we revisit this classical partial-feedback setting and study online learnability from a combinatorial perspective. We show that the Littlestone dimension continues to provide a tight quantitative characterization of apple tasting in the agnostic setting, closing an open question posed by Helmbold et al. (2000a). In addition, we give a new combinatorial parameter, called the Effective width, that tightly quantifies the minimax expected number of mistakes in the realizable setting. As a corollary, we use the Effective width to establish a \emph{trichotomy} of the minimax expected number of mistakes in the realizable setting. In particular, we show that in the realizable setting, the expected number of mistakes of any learner, under apple tasting feedback, can only be either $\Theta(1), \Theta(\sqrt{T})$, or $\Theta(T)$. This is in contrast to the full-information realizable setting where only $\Theta(1)$ and $\Theta(T)$ are possible.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-raman24a, title = {Apple Tasting: Combinatorial Dimensions and Minimax Rates}, author = {Raman, Vinod and Subedi, Unique and Raman, Ananth and Tewari, Ambuj}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {4358--4380}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/raman24a/raman24a.pdf}, url = {https://proceedings.mlr.press/v247/raman24a.html}, abstract = {In online binary classification under \emph{apple tasting} feedback, the learner only observes the true label if it predicts “1". First studied by Helmbold et al. (2000a), we revisit this classical partial-feedback setting and study online learnability from a combinatorial perspective. We show that the Littlestone dimension continues to provide a tight quantitative characterization of apple tasting in the agnostic setting, closing an open question posed by Helmbold et al. (2000a). In addition, we give a new combinatorial parameter, called the Effective width, that tightly quantifies the minimax expected number of mistakes in the realizable setting. As a corollary, we use the Effective width to establish a \emph{trichotomy} of the minimax expected number of mistakes in the realizable setting. In particular, we show that in the realizable setting, the expected number of mistakes of any learner, under apple tasting feedback, can only be either $\Theta(1), \Theta(\sqrt{T})$, or $\Theta(T)$. This is in contrast to the full-information realizable setting where only $\Theta(1)$ and $\Theta(T)$ are possible. } }
Endnote
%0 Conference Paper %T Apple Tasting: Combinatorial Dimensions and Minimax Rates %A Vinod Raman %A Unique Subedi %A Ananth Raman %A Ambuj Tewari %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-raman24a %I PMLR %P 4358--4380 %U https://proceedings.mlr.press/v247/raman24a.html %V 247 %X In online binary classification under \emph{apple tasting} feedback, the learner only observes the true label if it predicts “1". First studied by Helmbold et al. (2000a), we revisit this classical partial-feedback setting and study online learnability from a combinatorial perspective. We show that the Littlestone dimension continues to provide a tight quantitative characterization of apple tasting in the agnostic setting, closing an open question posed by Helmbold et al. (2000a). In addition, we give a new combinatorial parameter, called the Effective width, that tightly quantifies the minimax expected number of mistakes in the realizable setting. As a corollary, we use the Effective width to establish a \emph{trichotomy} of the minimax expected number of mistakes in the realizable setting. In particular, we show that in the realizable setting, the expected number of mistakes of any learner, under apple tasting feedback, can only be either $\Theta(1), \Theta(\sqrt{T})$, or $\Theta(T)$. This is in contrast to the full-information realizable setting where only $\Theta(1)$ and $\Theta(T)$ are possible.
APA
Raman, V., Subedi, U., Raman, A. & Tewari, A.. (2024). Apple Tasting: Combinatorial Dimensions and Minimax Rates. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:4358-4380 Available from https://proceedings.mlr.press/v247/raman24a.html.

Related Material