# Efficient non-greedy optimization of decision trees

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2015.

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

- [Optimal randomized classification trees](https://mlsanity.com/paper/2110.11952/) (2021)
- [Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent](https://mlsanity.com/paper/2102.07567/) (2021)
- [GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent](https://mlsanity.com/paper/2305.03515/) (2023)
- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [Breiman meets Bellman: Non-Greedy Decision Trees with MDPs](https://mlsanity.com/paper/2309.12701/) (2023)
- [Marginal Effects for Non-Linear Prediction Functions](https://mlsanity.com/paper/2201.08837/) (2022)
- [SaDe: Learning Models that Provably Satisfy Domain Constraints](https://mlsanity.com/paper/2112.00552/) (2021)
- [Online Learning of Decision Trees with Thompson Sampling](https://mlsanity.com/paper/2404.06403/) (2024)
- [Yet Another Representation of Binary Decision Trees: A Mathematical Demonstration](https://mlsanity.com/paper/2101.07077/) (2021)
- [Tree in Tree: from Decision Trees to Decision Graphs](https://mlsanity.com/paper/2110.00392/) (2021)
- [Learning Prescriptive ReLU Networks](https://mlsanity.com/paper/2306.00651/) (2023)
- [Experiments with Optimal Model Trees](https://mlsanity.com/paper/2503.12902/) (2025)
- [LHT: Statistically-Driven Oblique Decision Trees for Interpretable Classification](https://mlsanity.com/paper/2505.04139/) (2025)
- [Decision Machines: Congruent Decision Trees](https://mlsanity.com/paper/2101.11347/) (2021)
- [Slow-Growing Trees](https://mlsanity.com/paper/2103.01926/) (2021)
- [Loss-Optimal Classification Trees: A Generalized Framework and the Logistic Case](https://mlsanity.com/paper/2306.00857/) (2023)
- [Adaptive Multi-Branching for Shallow Decision Tree Induction](https://mlsanity.com/paper/2608.29262/) (2026)

## Abstract (arXiv)

Decision trees and randomized forests are widely used in computer vision and machine learning. Standard algorithms for decision tree induction optimize the split functions one node at a time according to some splitting criteria. This greedy procedure often leads to suboptimal trees. In this paper, we present an algorithm for optimizing the split functions at all levels of the tree jointly with the leaf parameters, based on a global objective. We show that the problem of finding optimal linear-combination (oblique) splits for decision trees is related to structured prediction with latent variables, and we formulate a convex-concave upper bound on the tree's empirical loss. The run-time of computing the gradient of the proposed surrogate objective with respect to each training exemplar is quadratic in the the tree depth, and thus training deep trees is feasible. The use of stochastic gradient descent for optimization enables effective training with large datasets. Experiments on several classification benchmarks demonstrate that the resulting non-greedy decision trees outperform greedy decision tree baselines.