Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913318364512256 |
|---|---|
| author | Chen, Xi Fei, Yumou Patel, Shyamal |
| author_facet | Chen, Xi Fei, Yumou Patel, Shyamal |
| contents | We give a distribution-free testing algorithm for decision lists with $\tilde{O}(n^{11/12}/\varepsilon^3)$ queries. This is the first sublinear algorithm for this problem, which shows that, unlike halfspaces, testing is strictly easier than learning for decision lists. Complementing the algorithm, we show that any distribution-free tester for decision lists must make $\tildeΩ(\sqrt{n})$ queries, or draw $\tildeΩ(n)$ samples when the algorithm is sample-based. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_11103 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries Chen, Xi Fei, Yumou Patel, Shyamal Data Structures and Algorithms We give a distribution-free testing algorithm for decision lists with $\tilde{O}(n^{11/12}/\varepsilon^3)$ queries. This is the first sublinear algorithm for this problem, which shows that, unlike halfspaces, testing is strictly easier than learning for decision lists. Complementing the algorithm, we show that any distribution-free tester for decision lists must make $\tildeΩ(\sqrt{n})$ queries, or draw $\tildeΩ(n)$ samples when the algorithm is sample-based. |
| title | Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.11103 |