Active Learning for Decision Trees with Provable Guarantees

AI summary

Overview

Research area: Theoretical machine learning — specifically active learning, label complexity, the disagreement coefficient, and the theory of decision tree learning.

Technical level: Advanced. The paper is a theory contribution built on VC dimension, version space arguments, disagreement coefficients, and label complexity bounds.

Scope in one sentence: The paper provides the first analysis of the disagreement coefficient for decision trees, the first active learning algorithm for binary classification with a multiplicative (1+ε) error guarantee, and a combined label complexity bound for actively learning decision trees that is polylogarithmic in the dataset size under two stated assumptions.

The authors are Arshia Soltani Moakhar, Tanapoom Laoaron, Faraz Ghahremani, Kiarash Banihashem, and MohammadTaghi Hajiaghayi, all at the University of Maryland. The paper is arXiv:2601.20775v2 [cs.LG], dated 18 Feb 2026, and is listed under Machine Learning.

What This Paper Is About

Active learning tries to train a model while asking for as few labels as possible, since labels are often expensive to obtain. Decision trees are widely used and interpretable, but until this work there was no rigorous theoretical analysis of how many label queries active learning needs to learn one. This paper fills that gap: it analyzes the key quantity (the disagreement coefficient) that controls how efficiently a decision tree can be actively learned, proves which structural assumptions are necessary to keep that quantity small, and designs a new algorithm that returns a classifier whose error is within a factor of (1+ε) of the best possible.

Key Contributions

1. The first active learning algorithm for a multiplicative error budget in classification. Algorithm 2 returns a (1+ε)-approximate classifier, meaning its error is at most (1+ε) times that of the optimal classifier in the class, with probability greater than 1−δ.

2. The first label complexity bound for active decision tree learning, obtained by combining the new disagreement coefficient bound with the general multiplicative-error algorithm.

3. Proof that two assumptions are necessary for polylogarithmic label complexity in active decision tree learning: the uniform-like (grid) structure of the input distribution, and the constraint that each node on a root-to-leaf path operates on a unique feature dimension.

4. The first label complexity lower bound for active stump learning on discrete datasets: Ω(ln(1/δ) · 1/ε²) queries, showing the algorithm's dependence on ε is close to optimal.

Main Findings

• Disagreement coefficient for decision trees (Theorem 1.1): For input space X = {(a₁, …, a_dim) | ∀i, a_i ∈ ℕ, a_i ≤ w} of n points, if every node tests a feature dimension distinct from its ancestors and the tree height is at most the depth parameter (written as "0pt" in the paper's notation), the disagreement coefficient is upper bounded by θ = O(ln^depth(n)) and lower bounded by θ = Ω(c(ln(n) − c′)^{depth−1}), where c = 2^{−dim}/(depth^{depth−1} · depth!) and c′ = ln(4)·dim.

• The unique-dimension assumption is necessary (Theorem 3.6): If decision tree nodes are allowed to query the same dimension as their ancestors, the disagreement coefficient for trees of height at least 2 is θ = Ω(n^{1/dim}) for any dataset with n distinct points. The proof builds classifiers within radius r = 2n^{−1/dim} of the all-zero classifier whose disagreement region covers at least ((2^dim − 1)/2^dim)·n points.

• The grid-structure assumption is necessary (Theorem 3.7): There exists a dataset of size n for which the disagreement coefficient is Ω(n) even when nodes are restricted to unique dimensions per root-to-leaf path. The construction places all points on the line x₁ = x₂ = … = x_dim; at radius r = 1/n the ball contains a tree that flips any single point, giving the ratio n/((1/n)·n) = n.

• Weighted generalization (Section 3.4): The integer-grid assumption can be relaxed by assigning each point X_i a weight W_i ∈ [1, λ]. The disagreement coefficient for this weighted task is scaled by at most λ² compared to the unweighted case, proved in Theorem D.14, a variant of Theorem 7.6 from Hanneke (2014) for discrete datasets.

• General multiplicative-error bound (Theorem 1.2): Algorithm 2 returns a (1+ε)-approximate classifier with probability greater than 1−δ using O(ln(n)·θ²(V_H ln θ + ln(ln n/δ)) + (θ²/ε²)(V_H ln(θ/ε) + ln(1/δ))) queries, where n is the dataset size, V_H is the VC dimension of the classifier space, and θ is the disagreement coefficient.

• Main label complexity for decision trees (Corollary 1.3): Algorithm 2 returns a (1+ε)-approximate classifier of an optimal decision tree in which each node operates on a dimension distinct from its ancestors, using at most O(ln^{2·depth+2}(n)(2^depth(depth + ln dim)depth + ln(1/δ)) + (ln^{2·depth}(n)/ε²)(2^depth(depth + dim) ln(ln^depth(n)/ε) + ln(1/δ))) queries. The VC dimension of the decision tree class used is 2^depth(depth + ln dim) (Lemma A.3).

• Stump case (Theorem 4.1): For a one-dimensional sorted dataset of size n, Algorithm 1 returns a (1+ε)-approximate decision stump with probability at least 1−δ using O(ln(n)(ln(ln(n)) + ln(1/δ)) + (1/ε²) ln(1/(δε))) label queries.

• Lower bound (Theorem 4.3): Any active learning algorithm requires Ω(ln(1/δ) · 1/ε²) queries to return a (1+ε)-approximate decision stump with probability greater than 1−δ; the proof adapts the coin-tossing lower bound of Kääriäinen (2006) and adds techniques needed for discrete datasets.

• Additive algorithms cannot be adapted (Appendix E): Estimating the optimal error η well enough to set ε_additive = εη requires Ω(1/η) samples, so any such adaptation would need Ω(n) labels. The paper formally argues that guessing-and-verifying strategies hit the same bottleneck.

• Empirical check: Algorithm 1 was validated on datasets of size n = 10⁷ with 0.1 label noise, achieving success rates greater than 90% with constants (c₁, b₁ ≈ 3) significantly smaller than the theoretical worst case. Dataset names and further benchmark details are not reported in the extracted content; the paper points to Appendix F for full details.

• Prior work on this question: Balcan et al. (2010) showed axis-parallel trees on continuous inputs in the [0,1]^n hypercube can be learned efficiently under the uniform distribution, but only asserted that each subclass's disagreement coefficient is finite without computing or quantitatively bounding it. This paper supplies the first explicit calculation on discrete domains.

Methodology in Plain English

The authors work entirely in the theory of active learning, where the algorithm sees all n unlabeled data points up front and can adaptively ask for the binary label of any point it chooses. The goal is to return a classifier whose error is at most (1+ε) times the error of the best classifier in the class, with probability at least 1−δ, while making as few queries as possible.

Their analysis of the decision tree class proceeds by decomposing a tree into simpler pieces called LineTrees. For each leaf, the corresponding line tree labels everything reaching that leaf with the leaf's label and everything else with the opposite label. The disagreement region of a hypothesis ball can then be written as a union over these line trees, and each piece can be bounded. For line trees on a grid-like domain, they show the disagreement coefficient is O((3 ln w)^depth) (Proposition 3.5); combining the pieces with the fact that there are L·C(dim, depth) such sets gives the main bound.

To show the assumptions are essential, they construct adversarial datasets. One construction lets nodes reuse ancestor dimensions so that classifiers very close to the all-zero classifier each flip small slices of the data, covering most of the dataset from a tiny radius. The other places all points on the diagonal line and shows a single point can be isolated and flipped by a tree, again making the disagreement region cover everything.

The algorithm itself follows a shrink-or-stop pattern, first explained for a one-dimensional decision stump and then generalized. At each round it samples a few labels, computes high-probability lower and upper error bounds (with the gap between bounds at most 1/16), and keeps only classifiers whose lower bound is below the best upper bound. If the candidate interval or hypothesis ball does not shrink by at least half, the algorithm concludes that the remaining classifiers all have relatively high error and switches to a "direct estimation" phase, spending O(1/ε² · ln(1/(δε))) additional queries to pick the best remaining candidate. This stagnation signal is what lets the algorithm sidestep the need to know the optimal error η in advance, and it is what the authors describe as the first use of version-space stagnation as a signal for a multiplicative guarantee.

Why This Matters

Impact on research. This is the first theoretical treatment of active learning label complexity for decision trees, and the first multiplicative-error active learning algorithm for classification. Multiplicative error is standard in approximation algorithms and competitive analysis, and it is strictly stronger than the additive model: in realizable settings where the optimal classifier has zero error, a (1+ε)-approximate classifier is perfect, whereas an additive ε guarantee never reaches zero. The paper also gives matching-flavored lower bounds, showing the ε dependence cannot be improved beyond logarithmic factors. It connects a line of work on multiplicative guarantees in regression (Musco et al. (2022), Derezinski et al. (2018), Parulekar et al. (2021), Chen and Price (2019), Chen and Derezinski (2021), Gajjar et al. (2023), Gajjar et al. (2024), Chen et al. (2022)) to classification for the first time.

Real-world applications (the domains the paper itself cites for active learning):

• Medical diagnosis, where labeling requires skilled professionals rather than crowdsourcing
• Autonomous driving, where annotation is expensive and time-consuming
• Webpage classification
• Natural language processing

Industry relevance. Decision trees sit at the core of random forests (Breiman (2001)) and XGBoost (Chen and Guestrin (2016)), which the paper describes as among the most popular algorithms in supervised learning. Because decision trees perform feature selection, are interpretable, and are computationally cheap, any provable reduction in labeling cost for them transfers to settings where expert annotation dominates the budget. The paper's empirical check at n = 10⁷ with 0.1 label noise and success rates above 90% using small constants supports practical viability, though the evaluation is limited to what is reported in Appendix F.

Future Directions

• Relaxing or eliminating the grid-structure assumption. The paper takes a first step here by weighting points with W_i ∈ [1, λ] and showing the coefficient grows by at most λ², but the general distribution case remains open.
• Extending the analysis beyond trees where each root-to-leaf path uses unique dimensions, since Theorem 3.6 shows the coefficient degrades to Ω(n^{1/dim}) once dimensions may repeat, and Theorem 3.7 shows Ω(n) is possible even with uniqueness if the data is degenerate.
• Removing the algorithmic dependence on knowing θ: Algorithm 2 computes θ from Definition 3.3 up front, so an open question is whether the disagreement coefficient can be estimated or bypassed in practice.
• Extending the label complexity results from single decision trees to the ensembles built on them, such as random forests and XGBoost, which the paper identifies as the dominant practical use of decision trees.
• Broadening empirical validation beyond the single reported setting of n = 10⁷ with 0.1 label noise, since dataset names and benchmark comparisons are not reported in the extracted content.

Target Audience

Theoretical machine learning researchers working on active learning, label complexity, and statistical learning theory; researchers interested in the disagreement coefficient and version-space algorithms; and anyone studying the theory of decision tree learning. Practitioners building labeled-data pipelines for interpretable models — particularly in medical diagnosis, autonomous driving, webpage classification, and natural language processing — will benefit from understanding the sample-efficiency guarantees and the assumptions under which they hold, though the paper's content is written for a theory audience.

Authors’ abstract

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.