Active Learning for Decision Trees with Provable Guarantees

Theorem 1.1 — Disagreement Coefficient

For a decision tree classification task over a dataset of n points where each node tests a distinct feature dimension and tree height is at most d, the disagreement coefficient satisfies:

$$\theta = O\!\left(\ln^d(n)\right)$$

with a matching lower bound of Ω(c(ln(n) - c')^d-1).

Proof approach: We decompose each decision tree into simpler components called LineTrees—classifiers that isolate a single leaf. By fixing a tree h and analyzing DIS(B_H(h, r)), we break the disagreement region according to which leaf each point reaches and the dimension set of the corresponding leaf in a nearby tree h'. Using Lemma D.2, we reduce the analysis of full trees to line trees, and then apply a counting argument (Proposition 3.5) bounding the number of integer tuples whose product is at most nr, yielding the O(ln^d(n)) bound.

Theorem 1.2 — Multiplicative Error Algorithm

Algorithm 2 returns a (1 + ε)-approximate classifier with probability > 1 - δ using:

$$O\!\left(\ln(n)\theta^2\!\left(V_H \ln \theta + \ln \frac{\ln n}{\delta}\right) + \frac{\theta^2}{\epsilon^2}\!\left(V_H \ln \frac{\theta}{\epsilon} + \ln \frac{1}{\delta}\right)\right)$$

queries, where V_H is the VC dimension and θ is the disagreement coefficient.

Proof approach: The algorithm iteratively prunes the hypothesis set by sampling from the disagreement region and eliminating classifiers whose error lower bound exceeds the best upper bound. The key insight is a two-regime argument: if the optimal error on the disagreement region is small (below 1/(16θ)), the hypothesis set radius must halve, so the loop progresses. If it is large, the algorithm enters a direct estimation phase where (1+ε)-approximation becomes easy because the high error provides a large denominator. The disagreement coefficient θ bridges hypothesis ball radius and disagreement region size, enabling this critical inference.

Corollary 1.3 — Decision Tree Label Complexity

Combining the disagreement coefficient bound with the multiplicative error algorithm, the total number of label queries is:

$$O\!\left(\ln^{2d+2}(n)\!\left(2^d(d + \ln \text{dim})d + \ln \frac{1}{\delta}\right) + \frac{\ln^{2d}(n)}{\epsilon^2}\!\left(2^d(d + \text{dim}) \ln \frac{\ln^d(n)}{\epsilon} + \ln \frac{1}{\delta}\right)\right)$$

which is polylogarithmic in n.

Proof approach: This follows directly by substituting the disagreement coefficient θ = O(ln^d(n)) from Theorem 1.1 and the VC dimension V_H = O(2^d(d + ln dim)) of bounded-depth decision trees into the general label complexity bound of Theorem 1.2. Since θ is polylogarithmic in n, all terms in the resulting expression remain polylogarithmic in n, with the dependence on tree depth d and feature dimensionality dim appearing in the constant factors.

Theorem 4.3 — Label Complexity Lower Bound

Any active learning algorithm requires at least:

$$\Omega\!\left(\ln\!\left(\frac{1}{\delta}\right) \cdot \frac{1}{\epsilon^2}\right)$$

queries to return a (1 + ε)-approximate decision stump with probability > 1 - δ. This shows our algorithm's dependence on ε is close to optimal (up to logarithmic factors).