Research map / Learning theory and algorithms / Combinatorial and search optimization
Optimal Survival Trees: A Dynamic Programming Approach
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SurTree, the first globally optimal survival tree method, using dynamic programming with a specialized depth-two algorithm, and compares it against OST and CTree on synthetic and SurvSet real data.
Problem
Survival trees are learned greedily or by local search, so there is no guarantee of global optimality and no way to measure the optimality gap of heuristics for right-censored survival data.
Approach
Adapts the dynamic programming formulation of optimal decision trees to survival analysis by using a proportional-hazards likelihood loss with Nelson-Aalen baseline hazard, and adds a precomputation-based algorithm for depth-two trees that reduces the cost of searching splits.
Key results
- On SurvSet datasets at depth three, SurTree achieves the best Harrell's C-index on 10 of 16 datasets (average rank 1.83), versus OST (2.03) and CTree (2.07).
- SurTree's average run time on real data is more than 100 times faster than OST (geometric mean), and the depth-two algorithm reduces run time 45 times on average (geometric mean, excluding time-outs).
- On training scores with n=5000, SurTree's training score is 4% better than OST at depth 5 and 34% higher than CTree at depth 2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SurTree instead of CTree | Survival-tree prediction on synthetic data · Synthetic datasets with moderate and high censoring | Harrell's C-index | Helped |
| Use SurTree instead of OST | Survival-tree prediction on synthetic data · Synthetic datasets with moderate and high censoring, n=200, 500 | Harrell's C-index | Helped |
| Use SurTree instead of OST | Survival-tree prediction · SurvSet real datasets, d=3 | Harrell's C-index | No clear effect |
| Use OST instead of CTree | Survival-tree prediction · SurvSet real datasets, d=3 | Harrell's C-index and integrated Brier score | Helped |
| Add the specialized depth-two solver (ablation) | SurTree · Runtime on evaluated datasets | runtime reduction: 45 times | Helped |
| Use SurTree instead of OST | Survival-tree optimization · Real data, trees of maximum depth three | runtime: more than 100 times faster | Helped |
| Increase maximum tree depth | SurTree · Synthetic data, f=1 up to depth 5 and f=2 up to depth 4 | runtime relative to OST | Mixed |
| Use SurTree instead of OST | Training on synthetic data with n=5000 and c=0.5 · Depth 5 | normalized training score: 4% better | Helped |
| Use SurTree instead of CTree | Training on synthetic data with n=5000 and c=0.5 · Depth 2 | normalized training score: 34% higher | Helped |
| Use SurTree instead of CTree | Survival-tree prediction · SurvSet real datasets, d=4 | integrated Brier score | Helped |
Surprising findings
- CTree's run time is approximately constant with increasing depth and number of features, and its slower real-data performance is attributed to its cross-validation procedure rather than tree search.
- At depth four, no significant out-of-sample differences were found between methods except SurTree having a better integrated Brier score than CTree.
Limitations
- SurTree's run time scales exponentially with maximum depth, limiting it to shallow trees.
- Each leaf uses only a single constant proportional hazard parameter rather than a richer per-leaf model.
- CTree timed out on the largest real dataset (Hdfail) and OST timed out on synthetic n=5000 settings.
Experimental setup
Datasets: SurvSet (16 real datasets with more than 2000 instances) synthetic survival data generated from random ground-truth trees
Benchmarks: SurvSet real datasets synthetic survival data
Metrics: Harrell's C-index integrated Brier score run time training score
Baselines: OST CTree
Builds on: STreeD Optimal Survival Trees (OST) CTree
Closest papers by meaning
- SurvivalPFN: Amortizing Survival Prediction via In-Context Bayesian Inference (NeurIPS 2026 · similarity 0.85)
- Survival Analysis via Density Estimation (ICML 2025 · similarity 0.83)
- Gradient-based Explanations for Deep Learning Survival Models (ICML 2025 · similarity 0.83)
- Toward Conditional Distribution Calibration in Survival Prediction (NeurIPS 2024 · similarity 0.82)
- Conformalized Survival Distributions: A Generic Post-Process to Increase Calibration (ICML 2024 · similarity 0.82)
- Deep Copula-Based Survival Analysis for Dependent Censoring with Identifiability Guarantees (AAAI 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.