Mistake-bounded online learning with operation caps
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918135639048192 |
|---|---|
| author | Geneson, Jesse Li, Meien Tang, Linus |
| author_facet | Geneson, Jesse Li, Meien Tang, Linus |
| contents | We investigate the mistake-bound model of online learning with caps on the number of arithmetic operations per round. We prove general bounds on the minimum number of arithmetic operations per round that are necessary to learn an arbitrary family of functions with finitely many mistakes. We solve a problem on agnostic mistake-bounded online learning with bandit feedback from (Filmus et al, 2024) and (Geneson \& Tang, 2024). We also extend this result to the setting of operation caps. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_03892 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Mistake-bounded online learning with operation caps Geneson, Jesse Li, Meien Tang, Linus Machine Learning Computational Complexity Discrete Mathematics We investigate the mistake-bound model of online learning with caps on the number of arithmetic operations per round. We prove general bounds on the minimum number of arithmetic operations per round that are necessary to learn an arbitrary family of functions with finitely many mistakes. We solve a problem on agnostic mistake-bounded online learning with bandit feedback from (Filmus et al, 2024) and (Geneson \& Tang, 2024). We also extend this result to the setting of operation caps. |
| title | Mistake-bounded online learning with operation caps |
| topic | Machine Learning Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2509.03892 |