# Optimal Survival Trees: A Dynamic Programming Approach

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 42 references that are in the map.
- First posted on arXiv 9 Jan 2024.

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

- [Machine Learning for Survival Analysis: A Survey](https://mlsanity.com/paper/1708.04649/) (2017)
- [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)
- [A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees](https://mlsanity.com/paper/2011.03375/) (2020)
- [SurvSet: An open-source time-to-event dataset repository](https://mlsanity.com/paper/2203.03094/) (2022)

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

- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [FastSurvival: Hidden Computational Blessings in Training Cox Proportional Hazards Models](https://mlsanity.com/paper/2410.19081/) (2024)
- [Discovering Subgroups with Exceptional Survival Characteristics](https://mlsanity.com/paper/2602.22179/) (2026)
- [Evolving Features vs Evolving Entire Trees with GP for Interpretable Survival Analysis](https://mlsanity.com/paper/2605.30119/) (2026)
- [A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees](https://mlsanity.com/paper/2609.38194/) (2026)

## Abstract (arXiv)

Survival analysis studies and predicts the time of death, or other singular unrepeated events, based on historical data, while the true time of death for some instances is unknown. Survival trees enable the discovery of complex nonlinear relations in a compact human comprehensible model, by recursively splitting the population and predicting a distinct survival distribution in each leaf node. We use dynamic programming to provide the first survival tree method with optimality guarantees, enabling the assessment of the optimality gap of heuristics. We improve the scalability of our method through a special algorithm for computing trees up to depth two. The experiments show that our method's run time even outperforms some heuristics for realistic cases while obtaining similar out-of-sample performance with the state-of-the-art.