# A Gap Between Decision Trees and Neural Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 33 references that are in the map.
- First posted on arXiv 7 Jan 2026.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Distilling a Neural Network Into a Soft Decision Tree](https://mlsanity.com/paper/1711.09784/) (2017)
- [Neural Oblivious Decision Ensembles for Deep Learning on Tabular Data](https://mlsanity.com/paper/1909.06312/) (2019)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018)
- [Path-SGD: Path-Normalized Optimization in Deep Neural Networks](https://mlsanity.com/paper/1506.02617/) (2015)
- [A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case](https://mlsanity.com/paper/1910.01635/) (2019)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Adaptive Neural Trees](https://mlsanity.com/paper/1807.06699/) (2018)
- [The Tree Ensemble Layer: Differentiability meets Conditional Computation](https://mlsanity.com/paper/2002.07772/) (2020)
- [GRANDE: Gradient-Based Decision Tree Ensembles for Tabular Data](https://mlsanity.com/paper/2309.17130/) (2023)
- [Approximation Rates for Shallow ReLUk Neural Networks on Sobolev Spaces via the Radon Transform](https://mlsanity.com/paper/2408.10996/) (2024)
- [Demystifying the Accuracy-Interpretability Trade-Off: A Case Study of Inferring Ratings from Reviews](https://mlsanity.com/paper/2503.07914/) (2025)
- [Tackling the Accuracy-Interpretability Trade-off in a Hierarchy of Machine Learning Models for the Prediction of Extreme Heatwaves](https://mlsanity.com/paper/2410.00984/) (2024)
- [Mirror Descent on Reproducing Kernel Banach Spaces](https://mlsanity.com/paper/2411.11242/) (2024)
- [A Gap Between the Gaussian RKHS and Neural Networks: An Infinite-Center Asymptotic Analysis](https://mlsanity.com/paper/2502.16331/) (2025)

## Abstract (arXiv)

We study when geometric simplicity of decision boundaries, used here as a notion of interpretability, can conflict with accurate approximation of axis-aligned decision trees by shallow neural networks. Decision trees induce rule-based, axis-aligned decision regions (finite unions of boxes), whereas shallow ReLU networks are typically trained as score models whose predictions are obtained by thresholding. We analyze the infinite-width, bounded-norm, single-hidden-layer ReLU class through the Radon total variation (RTV) seminorm, which controls the geometric complexity of level sets. We first show that the hard tree indicator 1A has infinite RTV. Moreover, two natural split-wise continuous surrogates--piecewise-linear ramp smoothing and sigmoidal (logistic) smoothing--also have infinite RTV in dimensions d>1, while Gaussian convolution yields finite RTV but with an explicit exponential dependence on d. We then separate two goals that are often conflated: classification after thresholding (recovering the decision set) versus score learning (learning a calibrated score close to 1A). For classification, we construct a smooth barrier score SA with finite RTV whose fixed threshold τ=1 exactly recovers the box. Under a mild tube-mass condition near partial A, we prove an L1(P) calibration bound that decays polynomially in a sharpness parameter, along with an explicit RTV upper bound in terms of face measures. Experiments on synthetic unions of rectangles illustrate the resulting accuracy--complexity tradeoff and how threshold selection shifts where training lands along it.