# Harnessing the Power of Choices in Decision Tree Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 53 references that are in the map.
- First posted on arXiv 2 Oct 2023.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Adaptive Neural Trees](https://mlsanity.com/paper/1807.06699/) (2018)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Fast Sparse Decision Tree Optimization via Reference Ensembles](https://mlsanity.com/paper/2112.00798/) (2021)
- [A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees](https://mlsanity.com/paper/2011.03375/) (2020)
- [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)
- [ID3 Learns Juntas for Smoothed Product Distributions](https://mlsanity.com/paper/1906.08654/) (2019)
- [Decision tree heuristics can fail, even in the smoothed setting](https://mlsanity.com/paper/2107.00819/) (2021)
- [Provable guarantees for decision tree induction: the agnostic setting](https://mlsanity.com/paper/2006.00743/) (2020)
- [On the Optimality of Trees Generated by ID3](https://mlsanity.com/paper/1907.05444/) (2019)

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

- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [Near Optimal Decision Trees in a SPLIT Second](https://mlsanity.com/paper/2502.15988/) (2025)

## Abstract (arXiv)

We propose a simple generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4.5, and CART. These algorithms, which have been central to machine learning for decades, are greedy in nature: they grow a decision tree by iteratively splitting on the best attribute. Our algorithm, Top-k, considers the k best attributes as possible splits instead of just the single best attribute. We demonstrate, theoretically and empirically, the power of this simple generalization. We first prove a sl greediness hierarchy theorem showing that for every k ∈ mathbbN, Top-(k+1) can be dramatically more powerful than Top-k: there are data distributions for which the former achieves accuracy 1-varepsilon, whereas the latter only achieves accuracy frac12+varepsilon. We then show, through extensive experiments, that Top-k outperforms the two main approaches to decision tree learning: classic greedy algorithms and more recent "optimal decision tree" algorithms. On one hand, Top-k consistently enjoys significant accuracy gains over greedy algorithms across a wide range of benchmarks. On the other hand, Top-k is markedly more scalable than optimal decision tree algorithms and is able to handle dataset and feature set sizes that remain far beyond the reach of these algorithms.