A Combinatorial Characterization of Supervised Online Learnability
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916118977839104 |
|---|---|
| author | Raman, Vinod Subedi, Unique Tewari, Ambuj |
| author_facet | Raman, Vinod Subedi, Unique Tewari, Ambuj |
| contents | We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions. No characterization of online learnability is known at this level of generality. We give a new scale-sensitive combinatorial dimension, named the sequential minimax dimension, and show that it gives a tight quantitative characterization of online learnability. In addition, we show that the sequential minimax dimension subsumes most existing combinatorial dimensions in online learning theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_03816 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Combinatorial Characterization of Supervised Online Learnability Raman, Vinod Subedi, Unique Tewari, Ambuj Machine Learning We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions. No characterization of online learnability is known at this level of generality. We give a new scale-sensitive combinatorial dimension, named the sequential minimax dimension, and show that it gives a tight quantitative characterization of online learnability. In addition, we show that the sequential minimax dimension subsumes most existing combinatorial dimensions in online learning theory. |
| title | A Combinatorial Characterization of Supervised Online Learnability |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2307.03816 |