Active Learning for Decision Trees with Provable Guarantees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915805312057344 |
|---|---|
| author | Moakhar, Arshia Soltani Laoaron, Tanapoom Ghahremani, Faraz Banihashem, Kiarash Hajiaghayi, MohammadTaghi |
| author_facet | Moakhar, Arshia Soltani Laoaron, Tanapoom Ghahremani, Faraz Banihashem, Kiarash Hajiaghayi, MohammadTaghi |
| contents | This paper advances the theoretical understanding of active learning label complexity for decision trees as binary classifiers. We make two main contributions. First, we provide the first analysis of the disagreement coefficient for decision trees-a key parameter governing active learning label complexity. Our analysis holds under two natural assumptions required for achieving polylogarithmic label complexity, (i) each root-to-leaf path queries distinct feature dimensions, and (ii) the input data has a regular, grid-like structure. We show these assumptions are essential, as relaxing them leads to polynomial label complexity. Second, we present the first general active learning algorithm for binary classification that achieves a multiplicative error guarantee, producing a $(1+ε)$-approximate classifier. By combining these results, we design an active learning algorithm for decision trees that uses only a polylogarithmic number of label queries in the dataset size, under the stated assumptions. Finally, we establish a label complexity lower bound, showing our algorithm's dependence on the error tolerance $ε$ is close to optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_20775 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Active Learning for Decision Trees with Provable Guarantees Moakhar, Arshia Soltani Laoaron, Tanapoom Ghahremani, Faraz Banihashem, Kiarash Hajiaghayi, MohammadTaghi Machine Learning Computational Complexity Data Structures and Algorithms This paper advances the theoretical understanding of active learning label complexity for decision trees as binary classifiers. We make two main contributions. First, we provide the first analysis of the disagreement coefficient for decision trees-a key parameter governing active learning label complexity. Our analysis holds under two natural assumptions required for achieving polylogarithmic label complexity, (i) each root-to-leaf path queries distinct feature dimensions, and (ii) the input data has a regular, grid-like structure. We show these assumptions are essential, as relaxing them leads to polynomial label complexity. Second, we present the first general active learning algorithm for binary classification that achieves a multiplicative error guarantee, producing a $(1+ε)$-approximate classifier. By combining these results, we design an active learning algorithm for decision trees that uses only a polylogarithmic number of label queries in the dataset size, under the stated assumptions. Finally, we establish a label complexity lower bound, showing our algorithm's dependence on the error tolerance $ε$ is close to optimal. |
| title | Active Learning for Decision Trees with Provable Guarantees |
| topic | Machine Learning Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.20775 |