mlsanityData to 7 Oct 2026

Optimal Sparse Decision Trees

arXiv 1904.12847 ↗First posted 29 Apr 2019cs.LG stat.MLcited by 104

Not on the map. Why?

Abstract (arXiv)

Decision tree algorithms have been among the most popular algorithms for interpretable (transparent) machine learning since the early 1980's. The problem that has plagued decision tree algorithms since their inception is their lack of optimality, or lack of guarantees of closeness to optimality: decision tree algorithms are often greedy or myopic, and sometimes produce unquestionably suboptimal models. Hardness of decision tree optimization is both a theoretical and practical obstacle, and even careful mathematical programming approaches have not been able to solve these problems efficiently. This work introduces the first practical algorithm for optimal decision trees for binary variables. The algorithm is a co-design of analytical bounds that reduce the search space and modern systems techniques, including data structures and a custom bit-vector library. Our experiments highlight advantages in scalability, speed, and proof of optimality. The code is available at https://github.com/xiyanghu/OSDT.

Key facts. Cited by 104 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Apr 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 16; 2022: 22; 2023: 16; 2024: 18; 2025: 18; 2026: 14.

104 papers.

Sort:

By area:

  1. 2021Interpretable Machine Learning: Fundamental Principles and 10 Grand Challengescited by 364
  2. 2022ECOD: Unsupervised Outlier Detection Using Empirical Cumulative Distribution Functionscited by 153
  3. 2022Exploring the Whole Rashomon Set of Sparse Decision Treescited by 80
  4. 2022Symbolic Regression is NP-hardcited by 68
  5. 2022Framework for Evaluating Faithfulness of Local Explanationscited by 55
  6. 2022Logic-Based Explainability in Machine Learningcited by 47
  7. 2022On Tackling Explanation Redundancy in Decision Treescited by 44
  8. 2021Fast Sparse Decision Tree Optimization via Reference Ensemblescited by 37
  9. 2022Augmenting Interpretable Models with LLMs during Trainingcited by 36
  10. 2021Strong Optimal Classification Treescited by 27
  11. 2024The Quest for the Right Mediator: Surveying Mechanistic Interpretability Through the Lens of Causal Mediation Analysiscited by 24
  12. 2022A Taxonomy of Human and ML Strengths in Decision-Making to Investigate Human-ML Complementaritycited by 22
38 more
  1. 2022Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Featurescited by 19
  2. 2023Tree Prompting: Efficient Task Adaptation without Fine-Tuningcited by 17
  3. 2021Connecting Interpretability and Robustness in Decision Trees through Separationcited by 16
  4. 2022Learning Interpretable Decision Rule Sets: A Submodular Optimization Approachcited by 13
  5. 2022TimberTrek: Exploring and Curating Sparse Decision Trees with Interactive Visualizationcited by 13
  6. 2022Optimal Sparse Regression Treescited by 13
  7. 2023Disproving XAI Myths with Formal Methods -- Initial Resultscited by 12
  8. 2021Robust Optimal Classification Trees Against Adversarial Examplescited by 11
  9. 2021Coresets for Decision Trees of Signalscited by 10
  10. 2021Interpretable and Fair Boolean Rule Sets via Column Generationcited by 10
  11. 2024Optimization Over Trained Neural Networks: Taking a Relaxing Walkcited by 10
  12. 2024Efficient Exploration of the Rashomon Set of Rule Set Modelscited by 10
  13. 2022Provably Precise, Succinct and Efficient Explanations for Decision Treescited by 8
  14. 2024Tree-Based Leakage Inspection and Control in Concept Bottleneck Modelscited by 8
  15. 2025Near Optimal Decision Trees in a SPLIT Secondcited by 8
  16. 2021A Scalable Two Stage Approach to Computing Optimal Decision Setscited by 7
  17. 2022Margin Optimal Classification Treescited by 7
  18. 2024Learning Decision Trees and Forests with Algorithmic Recoursecited by 7
  19. 2024Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performancecited by 7
  20. 2021Multiclass Optimal Classification Trees with SVM-splitscited by 6
  21. 2022Sparse Bayesian Optimizationcited by 6
  22. 2024Learning a Decision Tree Algorithm with Transformerscited by 6
  23. 2025Decision Tree Induction Through LLMs via Semantically-Aware Evolutioncited by 6
  24. 2023MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Treescited by 5
  25. 2024Optimal Sparse Survival Treescited by 5
  26. 2025SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumerationcited by 5
  27. 2021Rule Generation for Classification: Scalability, Interpretability, and Fairnesscited by 4
  28. 2022Mixed integer linear optimization formulations for learning optimal binary classification treescited by 4
  29. 2024Optimal Survival Trees: A Dynamic Programming Approachcited by 4
  30. 2024Conditional Density Estimation with Histogram Treescited by 4
  31. 2026Actionable Interpretability Must Be Defined in Terms of Symmetriescited by 4
  32. 2021Synthesizing Pareto-Optimal Interpretations for Black-Box Modelscited by 3
  33. 2022bsnsing: A decision tree induction method based on recursive optimal boolean rule compositioncited by 3
  34. 2023Learning Hybrid Interpretable Models: Theory, Taxonomy, and Methodscited by 3
  35. 2024Online Learning of Decision Trees with Thompson Samplingcited by 3
  36. 2024Learning accurate and interpretable tree-based modelscited by 3
  37. 2024Practical Attribution Guidance for Rashomon Setscited by 3
  38. 2022A Mathematical Programming Approach to Optimal Classification Forestscited by 2

50 most cited of 104 All 104 (JSON)