Global Optimization of Sparse and Interpretable Decision Trees

This direction is split into other directions: tree depth scalability. Its last version stays readable and citable here.

Version 1 of 161 papers73 conceptsfrozen 2026-10-04

For decades, the construction of decision trees has relied on a "greedy" compromise. Algorithms like CART and C4.5 build trees one split at a time, choosing the best local move without considering how it affects the rest of the structure. While efficient, this approach often produces models that are unnecessarily complex, less accurate, or harder to interpret than they need to be.

The research direction emerging from these papers seeks to move beyond local heuristics toward optimal decision trees: models that are provably the best possible fit for a dataset given specific constraints on size, depth, or sparsity. By reframing tree induction as a global combinatorial optimization problem, researchers are finding ways to navigate an exponential search space to deliver models that are both mathematically rigorous and human-interpretable.

The fundamental challenge in decision tree induction is that "looking ahead" doesn't always help if you only do it partially. In their classic study, Sreerama K. Murthy and Steven Salzberg demonstrated a phenomenon known as "lookahead pathology," where increasing search depth by just one or two levels can actually lead to larger, less accurate trees.

This happens because local heuristics are blind to the global structure. To find a truly minimal or most-accurate tree, one must consider the entire tree architecture simultaneously. However, as Mohammad Norouzi and colleagues note in Efficient Non-greedy Optimization of Decision Trees, the computational cost of this global optimization scales exponentially with tree depth. Every possible path to every possible leaf creates a search space that quickly becomes intractable for standard solvers.

Scaling via SAT and Dynamic Programming

To make global optimization practical, researchers have turned to advanced combinatorial frameworks. A landmark approach by Nina Narodytska, Alexey Ignatiev, and João Marques-Silva 0001 in Learning Optimal Decision Trees with SAT showed that Boolean Satisfiability (SAT) solvers could be used to find the absolute smallest tree for a dataset. By encoding the tree structure as a series of logical constraints, they allowed the solver to "prune" massive sections of the search space that could not possibly contain an optimal solution.

Parallel to SAT-based methods, Dynamic Programming (DP) has emerged as a powerful tool for regression and classification. Emir Demirović and his collaborators have developed several algorithms, such as MurTree and Piecewise Constant and Linear Regression Trees, that decompose the tree-building process into smaller, reusable sub-problems. These methods exploit the fact that many different tree structures share the same sub-trees, allowing the solver to avoid redundant calculations and scale to datasets with tens of thousands of instances.

The Depth Bottleneck

A recurring theme across this research is that the primary enemy of optimality is not the number of data points, but the maximum depth of the tree.

As Louis Jean explains in the Blossom algorithm, while these solvers can handle millions of samples, each incremental increase in depth causes an exponential jump in the search space. This is why most "optimal" solvers focus on shallow trees (depth 3 to 5). Fortunately, shallow trees are exactly what practitioners want for interpretability. In high-stakes domains like medicine or criminal justice, a provably optimal tree of depth 4 is often more valuable than a "good enough" tree of depth 20, as it captures the most essential patterns without over-fitting to noise.

New Frontiers in Sparsity and Constraints

Recent work has expanded these optimal methods to handle more complex objectives beyond simple misclassification count:

By treating the decision tree not as a sequence of greedy splits, but as a single mathematical object to be optimized, this field is bridging the gap between the speed of traditional machine learning and the rigor of combinatorial optimization. The result is a new generation of models that are as simple as possible, but no simpler.

Papers in this version

Showing 60 of 61 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_global_optimization_of_sparse_and_interp_7655b73e,
  title = {Global Optimization of Sparse and Interpretable Decision Trees},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-optimization-of-sparse-and-interpretable-decision-trees/rdr_7655b73ed76c4f6ba57cbed60e69352f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_optimization_of_sparse_and_interp_7655b73e_v1,
  title = {Global Optimization of Sparse and Interpretable Decision Trees},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-optimization-of-sparse-and-interpretable-decision-trees/rdr_7655b73ed76c4f6ba57cbed60e69352f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}