mlsanityData to 7 Oct 2026

Active Learning for Decision Trees with Provable Guarantees

arXiv 2601.20775 ↗First posted 28 Jan 2026cs.LG cs.CC cs.DScited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 24 of its 49 references that are in the map. First posted on arXiv 28 Jan 2026.

Builds on

24 of 49 references.

References · 24

  1. 2016XGBoost: A Scalable Tree Boosting Systemcited by 5,120
  2. 2020A Survey of Deep Active Learningcited by 547
  3. 2018Explaining Explanations: An Overview of Interpretability of Machine Learningcited by 508
  4. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  5. 2019A Survey on Active Learning and Human-in-the-Loop Deep Learning for Medical Image Analysiscited by 150
  6. 2020A Survey of Active Learning for Text Classification using Deep Neural Networkscited by 50
  7. 2019Deep Active Learning for Efficient Training of a LiDAR 3D Object Detectorcited by 45
  8. 2022A Survey of Active Learning for Natural Language Processingcited by 40
  9. 2017Active Regression via Linear-Sample Sparsificationcited by 36
  10. 2017Active classification with comparison queriescited by 27
  11. 2021Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergencecited by 24
  12. 2021Properly learning decision trees in almost polynomial timecited by 20
12 more
  1. 2019Top-down induction of decision trees: rigorous guarantees and inherent limitationscited by 17
  2. 2020Noise-tolerant, Reliable Active Classification with Comparison Queriescited by 17
  3. 2018Leveraged volume sampling for linear regressioncited by 15
  4. 2021L1 Regression with Lewis Weights Subsamplingcited by 14
  5. 2019Gradient Boosted Feature Selectioncited by 13
  6. 2020Point Location and Active Learning: Learning Halfspaces Almost Optimallycited by 13
  7. 2020Decision trees as partitioning machines to characterize their generalization propertiescited by 12
  8. 2022Active Learning for Single Neuron Models with Lipschitz Non-Linearitiescited by 12
  9. 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
  10. 2021Bounded Memory Active Learning through Enriched Queriescited by 8
  11. 2022Online Active Regressioncited by 8
  12. 2023Optimal Sparse Recovery with Decision Stumpscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Decision Tree Learning on Product Spacescited by 0