# Active Learning for Decision Trees with Provable Guarantees

arXiv: https://arxiv.org/abs/2601.20775 · HTML: https://mlsanity.com/paper/2601.20775/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 49 references that are in the map.
- First posted on arXiv 28 Jan 2026.

## Builds on (most cited first, 24 of 24)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [A Survey of Deep Active Learning](https://mlsanity.com/paper/2009.00236/) (2020)
- [Explaining Explanations: An Overview of Interpretability of Machine Learning](https://mlsanity.com/paper/1806.00069/) (2018)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [A Survey on Active Learning and Human-in-the-Loop Deep Learning for Medical Image Analysis](https://mlsanity.com/paper/1910.02923/) (2019)
- [A Survey of Active Learning for Text Classification using Deep Neural Networks](https://mlsanity.com/paper/2008.07267/) (2020)
- [Deep Active Learning for Efficient Training of a LiDAR 3D Object Detector](https://mlsanity.com/paper/1901.10609/) (2019)
- [A Survey of Active Learning for Natural Language Processing](https://mlsanity.com/paper/2210.10109/) (2022)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Top-down induction of decision trees: rigorous guarantees and inherent limitations](https://mlsanity.com/paper/1911.07375/) (2019)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Leveraged volume sampling for linear regression](https://mlsanity.com/paper/1802.06749/) (2018)
- [L1 Regression with Lewis Weights Subsampling](https://mlsanity.com/paper/2105.09433/) (2021)
- [Gradient Boosted Feature Selection](https://mlsanity.com/paper/1901.04055/) (2019)
- [Point Location and Active Learning: Learning Halfspaces Almost Optimally](https://mlsanity.com/paper/2004.11380/) (2020)
- [Decision trees as partitioning machines to characterize their generalization properties](https://mlsanity.com/paper/2010.07374/) (2020)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [Bounded Memory Active Learning through Enriched Queries](https://mlsanity.com/paper/2102.05047/) (2021)
- [Online Active Regression](https://mlsanity.com/paper/2207.05945/) (2022)
- [Optimal Sparse Recovery with Decision Stumps](https://mlsanity.com/paper/2303.04301/) (2023)

## Built on by (most cited first, 1 of 1)

- [Decision Tree Learning on Product Spaces](https://mlsanity.com/paper/2605.12983/) (2026)

## Abstract (arXiv)

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.