# Soft regression trees: a model variant and a decomposition training algorithm

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 44 references that are in the map.
- First posted on arXiv 10 Jan 2025.

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

- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Robust Decision Trees Against Adversarial Examples](https://mlsanity.com/paper/1902.10660/) (2019)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [A Universal Approximation Theorem for Mixture of Experts Models](https://mlsanity.com/paper/1602.03683/) (2016)
- [Interpretable Optimal Stopping](https://mlsanity.com/paper/1812.07211/) (2018)
- [Sparsity in Optimal Randomized Classification Trees](https://mlsanity.com/paper/2002.09191/) (2020)
- [Optimal Sparse Regression Trees](https://mlsanity.com/paper/2211.14980/) (2022)

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

- [Binary Kernel Logistic Regression: a sparsity-inducing formulation and a convergent decomposition training algorithm](https://mlsanity.com/paper/2512.19440/) (2025)

## Abstract (arXiv)

Decision trees are widely used for classification and regression tasks in a variety of application fields due to their interpretability and good accuracy. During the past decade, growing attention has been devoted to globally optimized decision trees with deterministic or soft splitting rules at branch nodes, which are trained by optimizing the error function over all the tree parameters. In this work, we propose a new variant of soft multivariate regression trees (SRTs) where, for every input vector, the prediction is defined as the linear regression associated to a single leaf node, namely, the leaf node obtained by routing the input vector from the root along the branches with higher probability. SRTs exhibit the conditional computational property, i.e., each prediction depends on a small number of nodes (parameters), and our nonlinear optimization formulation for training them is amenable to decomposition. After showing a universal approximation result for SRTs, we present a decomposition training algorithm including a clustering-based initialization procedure and a heuristic for reassigning the input vectors along the tree. Under mild assumptions, we establish asymptotic convergence guarantees. Experiments on 15 wellknown datasets indicate that our SRTs and decomposition algorithm yield higher accuracy and robustness compared with traditional soft regression trees trained using the nonlinear optimization formulation of Blanquero et al., and a significant reduction in training times as well as a slightly better average accuracy compared with the mixed-integer optimization approach of Bertsimas and Dunn. We also report a comparison with the Random Forest ensemble method.