Apple Tasting: Combinatorial Dimensions and Minimax Rates
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917698574745600 |
|---|---|
| author | Raman, Vinod Subedi, Unique Raman, Ananth Tewari, Ambuj |
| author_facet | Raman, Vinod Subedi, Unique Raman, Ananth Tewari, Ambuj |
| contents | In online binary classification under \emph{apple tasting} feedback, the learner only observes the true label if it predicts ``1". First studied by \cite{helmbold2000apple}, 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 \cite{helmbold2000apple}. In addition, we give a new combinatorial parameter, called the Effective width, that tightly quantifies the minimax expected 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 be $Θ(1), Θ(\sqrt{T})$, or $Θ(T)$. This is in contrast to the full-information realizable setting where only $Θ(1)$ and $Θ(T)$ are possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_19064 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Apple Tasting: Combinatorial Dimensions and Minimax Rates Raman, Vinod Subedi, Unique Raman, Ananth Tewari, Ambuj Machine Learning In online binary classification under \emph{apple tasting} feedback, the learner only observes the true label if it predicts ``1". First studied by \cite{helmbold2000apple}, 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 \cite{helmbold2000apple}. In addition, we give a new combinatorial parameter, called the Effective width, that tightly quantifies the minimax expected 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 be $Θ(1), Θ(\sqrt{T})$, or $Θ(T)$. This is in contrast to the full-information realizable setting where only $Θ(1)$ and $Θ(T)$ are possible. |
| title | Apple Tasting: Combinatorial Dimensions and Minimax Rates |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2310.19064 |