# Learning Optimal Classification Trees Robust to Distribution Shifts

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 26 Oct 2023.

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

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Data-Driven Robust Optimization](https://mlsanity.com/paper/1401.0212/) (2013)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Decision Trees for Decision-Making under the Predict-then-Optimize Framework](https://mlsanity.com/paper/2003.00360/) (2020)
- [Distributionally Robust Learning](https://mlsanity.com/paper/2108.08993/) (2021)
- [Robust Decision Trees Against Adversarial Examples](https://mlsanity.com/paper/1902.10660/) (2019)
- [Recursive Partitioning for Personalization using Observational Data](https://mlsanity.com/paper/1608.08925/) (2016)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Optimization of Tree Ensembles](https://mlsanity.com/paper/1705.10883/) (2017)
- [Efficient Training of Robust Decision Trees Against Adversarial Examples](https://mlsanity.com/paper/2012.10438/) (2020)
- [Learning Optimal Fair Classification Trees: Trade-offs Between Interpretability, Fairness, and Accuracy](https://mlsanity.com/paper/2201.09932/) (2022)
- [Learning Optimal Prescriptive Trees from Observational Data](https://mlsanity.com/paper/2108.13628/) (2021)
- [Extended Formulations in Mixed Integer Conic Quadratic Programming](https://mlsanity.com/paper/1505.07857/) (2015)

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

- [Toward AI Matching Policies in Homeless Services: A Qualitative Study with Policymakers](https://mlsanity.com/paper/2508.07129/) (2025)
- [Trustworthy Machine Learning through the Lens of Combinatorial Optimization: Survey and Research Perspectives](https://mlsanity.com/paper/2607.07762/) (2026)

## Abstract (arXiv)

We consider the problem of learning classification trees that are robust to distribution shifts between training and testing/deployment data. This problem arises frequently in high stakes settings such as public health and social work where data is often collected using self-reported surveys which are highly sensitive to e.g., the framing of the questions, the time when and place where the survey is conducted, and the level of comfort the interviewee has in sharing information with the interviewer. We propose a method for learning optimal robust classification trees based on mixed-integer robust optimization technology. In particular, we demonstrate that the problem of learning an optimal robust tree can be cast as a single-stage mixed-integer robust optimization problem with a highly nonlinear and discontinuous objective. We reformulate this problem equivalently as a two-stage linear robust optimization problem for which we devise a tailored solution procedure based on constraint generation. We evaluate the performance of our approach on numerous publicly available datasets, and compare the performance to a regularized, non-robust optimal tree. We show an increase of up to 12.48% in worst-case accuracy and of up to 4.85% in average-case accuracy across several datasets and distribution shifts from using our robust solution in comparison to the non-robust one.