Decision Tree Learning on Product Spaces

Technical Summary: Decision Tree Learning on Product Spaces

Problem Statement
Decision tree learning is a cornerstone of machine learning, prized for its interpretability and empirical success. The standard practical approach is the top-down greedy heuristic, which recursively splits nodes based on the most "influential" variable (often measured via impurity reduction like entropy or Gini index). While empirically effective, the theoretical understanding of this heuristic has been limited. Prior rigorous guarantees, such as those by Blanc et al. (ITCS, 2020), were restricted to the uniform distribution over the Boolean hypercube. This assumption fails to capture real-world data, where features often follow heterogeneous, non-uniform product distributions. Furthermore, many theoretical works propose complex, non-greedy algorithms (e.g., bottom-up or brute-force search) that diverge from practical implementations, leaving a gap between theory and practice.

Methodology
The authors extend the theoretical analysis of the top-down greedy heuristic to arbitrary product distributions. The setting involves learning a Boolean function $f: \{0, 1\}^n \to \{\pm 1\}$ under a product distribution $\mu = \mu_1 \times \dots \times \mu_n$, where each bit is 1 with probability $p_i$.

The core algorithm analyzed is BuildTopDownDT, a formalization of the standard greedy approach:

1. Initialization: Start with a single leaf.
2. Scoring: At each step, score every leaf $l$ in the current tree. The score is defined as the probability mass reaching the leaf ($p_l$) multiplied by the maximum influence of any variable on the subfunction at that leaf ($\max_i \text{Inf}_i(f_l)$).
3. Splitting: Select the leaf with the highest score and split it on its most influential variable.
4. Termination: Repeat until the tree's $f$-completion (assigning the majority label to leaves) is an $\epsilon$-approximation of $f$.

To analyze this, the authors introduce a potential function called the cost of a bare tree (unlabeled), defined as the sum of the total influence of the subfunctions at each leaf, weighted by the probability of reaching that leaf. They establish a relationship between this cost, the approximation error, and the structural properties of the optimal tree (maximum depth $D_{\text{opt}}$ and average depth $\Delta_{\text{opt}}$).

Key Contributions

1. Generalization to Product Distributions: The paper provides the first rigorous performance guarantees for the top-down greedy heuristic under arbitrary product distributions, removing the restrictive uniform distribution assumption of prior work.
2. Improved Size Bounds: The main theoretical result (Theorem 1.1) states that for any function computable by an optimal tree of size $s$, maximum depth $D_{\text{opt}}$, and average depth $\Delta_{\text{opt}}$, the greedy heuristic constructs an $\epsilon$-approximating tree of size at most:
   $$\max \left( \left( \frac{e \cdot \Delta_{\text{opt}}}{\epsilon D_{\text{opt}}} \right)^{\Delta_{\text{opt}} D_{\text{opt}}}, e^{\Delta_{\text{opt}} D_{\text{opt}}} \right)$$
   • Balanced Regime: For full binary trees where $D_{\text{opt}} = \Delta_{\text{opt}} = \log s$, the bound simplifies to $s^{O(\log s \cdot \log(e/\epsilon))}$. This is a quasi-polynomial bound that improves upon the bound established by Blanc et al. (2020) and holds for a strictly broader class of distributions.
   • Path-Like Regime: For highly unbalanced trees (e.g., path trees), $D_{\text{opt}}$ can be $O(n)$ while $\Delta_{\text{opt}}$ remains a small constant. The mixed dependence on $\Delta_{\text{opt}}$ and $D_{\text{opt}}$ yields a bound exponentially tighter than one depending solely on $D_{\text{opt}}$ (which would be $e^{O(n^2)}$ vs. the derived $e^{O(n)}$).
3. Parameter-Free Practical Implementation: The authors present Algorithm 2, a practical implementation of the heuristic that is entirely parameter-free. Unlike previous theoretical analyses that assume knowledge of the optimal tree's size ($s$) or depth, this algorithm relies on sample-based estimation of scores and errors. It adaptively increases sample sizes to maintain statistical confidence without prior knowledge of the target function's complexity.
4. Robustness to Estimation: Theoretical guarantees are shown to hold even when the algorithm selects a leaf with a score that is only a constant fraction (e.g., $1/4$) of the maximum possible score, accommodating the noise inherent in sample-based estimation.

Results

• Theoretical: The paper proves that the greedy heuristic achieves quasi-polynomial size bounds in the balanced regime and significantly better bounds in unbalanced regimes compared to bounds depending only on maximum depth. The analysis relies on new lemmas relating the cost of the tree to its error and establishing lower bounds on the score of the selected leaf in terms of the current error and tree depth.
• Empirical: The authors provide an empirical evaluation of their parameter-free algorithm (Algorithm 2) on both balanced and unbalanced decision tree targets under varying product distributions (uniform, moderate bias, heavy bias). The results confirm that the recovered tree sizes remain close to the ground-truth targets and well within the theoretical bounds, with sample complexity growing polynomially in dimension and $1/\epsilon$.

Significance and Claims
The paper claims to bridge the gap between the theoretical analysis of decision tree learning and its practical application. By analyzing the classic, simple greedy heuristic (used in ID3, C4.5, CART) rather than complex, non-greedy variants, the authors provide rigorous justification for the strong empirical performance of these widely used algorithms.

The significance lies in:

• Realism: Moving beyond the uniform distribution to arbitrary product distributions, which better model real-world data.
• Practicality: Providing a parameter-free algorithm that does not require prior knowledge of the optimal tree's size or depth, making the theoretical guarantees directly applicable to real-world scenarios.
• Tightness: Demonstrating that the mixed dependence on average and maximum depth yields strictly tighter bounds for unbalanced trees, a common structure in decision trees.

The authors acknowledge limitations, noting that their analysis focuses on unpruned trees (as rigorous pruning analysis is sparse) and that the current proof relies on discrete product spaces. They identify extending the analysis to continuous features and threshold-based splits as a future direction. They also note that while their bound is quasi-polynomial, super-polynomial lower bounds exist for decision tree learning, suggesting that some dependence on the optimal size $s$ is unavoidable.