# Optimal Decision Trees for Nonlinear Metrics

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2020.

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

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Scalable Optimal Multiway-Split Decision Trees with Constraints](https://mlsanity.com/paper/2302.06812/) (2023)
- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [Multiclass Optimal Classification Trees with SVM-splits](https://mlsanity.com/paper/2111.08674/) (2021)
- [SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration](https://mlsanity.com/paper/2511.03344/) (2025)
- [Causal Fair Metric: Bridging Causality, Individual Fairness, and Adversarial Robustness](https://mlsanity.com/paper/2310.19391/) (2023)
- [Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach](https://mlsanity.com/paper/2602.02173/) (2026)
- [ODTE -- An ensemble of multi-class SVM-based oblique decision trees](https://mlsanity.com/paper/2411.13376/) (2024)
- [Efficient & Correct Predictive Equivalence for Decision Trees](https://mlsanity.com/paper/2509.17774/) (2025)
- [Surrogate Graph Partitioning for Spatial Prediction](https://mlsanity.com/paper/2510.07832/) (2025)
- [Algebraic Model Counting for Global Analysis of Optimal Decision Trees](https://mlsanity.com/paper/2607.02069/) (2026)

## Abstract (arXiv)

Nonlinear metrics, such as the F1-score, Matthews correlation coefficient, and Fowlkes-Mallows index, are often used to evaluate the performance of machine learning models, in particular, when facing imbalanced datasets that contain more samples of one class than the other. Recent optimal decision tree algorithms have shown remarkable progress in producing trees that are optimal with respect to linear criteria, such as accuracy, but unfortunately nonlinear metrics remain a challenge. To address this gap, we propose a novel algorithm based on bi-objective optimisation, which treats misclassifications of each binary class as a separate objective. We show that, for a large class of metrics, the optimal tree lies on the Pareto frontier. Consequently, we obtain the optimal tree by using our method to generate the set of all nondominated trees. To the best of our knowledge, this is the first method to compute provably optimal decision trees for nonlinear metrics. Our approach leads to a trade-off when compared to optimising linear metrics: the resulting trees may be more desirable according to the given nonlinear metric at the expense of higher runtimes. Nevertheless, the experiments illustrate that runtimes are reasonable for majority of the tested datasets.