A Gap Between Decision Trees and Neural Networks

Akash Kumar · 2026

Read A Gap Between Decision Trees and Neural Networks by Akash Kumar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-03919.txt.

Introduction

Akash Kumar, writing alone, studies a tension between decision trees and shallow neural networks: the geometric simplicity that makes trees interpretable may make them impossible for small networks to imitate accurately. Trees carve space into axis-aligned boxes. Shallow ReLU networks, by contrast, are usually trained as scoring models whose decisions come from thresholding, and a geometric complexity measure governs the shapes they can draw cheaply.

Kumar shows the hard tree indicator has infinite complexity under that measure. Two natural smoothed surrogates, ramp smoothing and logistic smoothing, are also infinitely complex in more than one dimension. Gaussian smoothing stays finite but its cost grows exponentially with dimension. The results separate goals that are often conflated and warn that interpretability of a target rule does not make it easy for a network to learn.

Catalog record

CREATORAkash Kumar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-03919

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Gap Between Decision Trees and Neural Networks Akash Kumar Abstract 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 ( ℛ ​ TV \mathcal{R}\mathrm{TV} ) seminorm, which controls the geometric complexity of level sets. We first show that the hard tree indicator 1 A 1_{A} has infinite ℛ ​ TV \mathcal{R}\mathrm{TV} . Moreover, two natural split-wise continuous surrogates–piecewise-linear ramp smoothing and sigmoidal (logistic) smoothing–also have infinite ℛ ​ TV \mathcal{R}\mathrm{TV} in dimensions d > 1 d>1 , while Gaussian convolution yields finite ℛ ​ TV \mathcal{R}\mathrm{TV} but with an explicit exponential dependence on d 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 1 A 1_{A} ). For classification, we construct a smooth barrier score S A S_{A} with finite ℛ ​ TV \mathcal{R}\mathrm{TV} whose fixed threshold τ = 1 \tau=1 exactly recovers the box. Under a mild tube-mass condition near ∂ A \partial A , we prove an L 1 ​ ( P ) L_{1}(P) calibration bound that decays polynomially in a sharpness parameter, along with an explicit ℛ ​ TV \mathcal{R}\mathrm{TV} 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. † † shortheadings: / Decision Trees vs Neural Networks † † firstpage: 1 1 Introduction In safety-critical and socially sensitive applications, it is often desirable to deploy predictors whose behavior can be explained and audited. A common interpretable baseline is the axis-aligned decision tree: it classifies x\in\mathbb{R}^{d} by a sequence of one-dimensional threshold tests. Equivalently, it induces a piecewise-constant classifier of the form \hskip-17.07164ptf_{\mathrm{DT}}(x)\;=\;\mathbf{1}\{x\in A\},\hskip 14.22636pt where A\subseteq\mathbb{R}^{d} is a finite union of axis-aligned boxes. Figure 1: Width– \mathcal{R}\mathrm{TV} frontier (depth-1 ReLU, box task). In contrast, a single-hidden-layer network forms a score x\;\mapsto\;\sum_{k=1}^{K}v_{k}\,\sigma(w_{k}^{\top}x-b_{k}), and typically produces a classifier only after applying a nonlinearity and/or threshold. We analyze the infinite-width, bounded-norm counterpart of this model through the Radon total variation ( \mathcal{R}\mathrm{TV} ) seminorm \|\cdot\|_{\mathcal{R}} ( 28 ; 22 ; 23 ) . Intuitively, \|\cdot\|_{\mathcal{R}} controls the amount of geometric complexity in level sets of a function and coincides with the minimum-mass ridgelet (infinite-width ReLU) representation norm. This makes \mathcal{R}\mathrm{TV} a natural lens for asking when shallow networks can represent tree-like decision structure without becoming geometrically complex. Two learning goals that should be separated. There are (at least) two distinct objectives when “learning a tree” with a shallow net: 1. Classification via thresholding. Learn a score s:\mathbb{R}^{d}\to[0,1] such that \{x:s(x)\geq\tau\}=A for some threshold \tau (possibly fixed or tuned on validation data). 2. Score learning / regression. Learn a calibrated score close to 1_{A} (e.g., in L_{1}(P) ), so that the score’s level sets and gradients align with the symbolic features of the tree. These goals are often conflated in empirical evaluations: many very different score functions can induce the same thresholded classifier, so near-perfect classification accuracy can mask large differences in calibration and geometry. This paper. We formalize the distinction above and show that it matters sharply under \mathcal{R}\mathrm{TV} control. Structurally, we prove that the hard tree indicator 1_{A} has infinite \mathcal{R}\mathrm{TV} . We then show that several natural continuous surrogates retain this pathology in d>1 : ramp smoothing is continuous piecewise-linear but typically has infinite \mathcal{R}\mathrm{TV} when multiple split normals are present, and sigmoidal smoothing has infinite \mathcal{R}\mathrm{TV} as soon as the depth is at least two. In contrast, Gaussian smoothing yields a finite \mathcal{R}\mathrm{TV} bound, but with an explicit exponential dependence on the ambient dimension. On the learning side, we show that classification itself is easy if one only requires correct thresholded decisions: we construct a smooth barrier score S_{B} for an axis-aligned box B such that a fixed cutoff \tau=1 exactly recovers B . Under a mild tube-mass condition near \partial B , S_{B} is also L_{1}(P) -close to \mathbf{1}_{B} with a polynomial rate in a sharpness parameter, and it has an explicit finite \mathcal{R}\mathrm{TV} bound. Thus, shallow nets can match tree decisions via thresholding without approximating the discontinuous tree function in any strong sense. In contrast, insisting on a score that is both calibrated and geometrically simple reveals a quantitative accuracy–complexity frontier. Contributions (informal). Let A be a finite union of axis-aligned boxes in \mathbb{R}^{d} . 1. Hard trees lie outside bounded- \mathcal{R}\mathrm{TV} balls. For every d\geq 1 , \|1_{A}\|_{\mathcal{R}}=+\infty . 2. Naive smoothings can still have infinite \mathcal{R}\mathrm{TV} in d>1 . Ramp and sigmoidal split-wise smoothings retain infinite \mathcal{R}\mathrm{TV} under mild conditions (in particular, multiple split directions / depth \geq 2 ). 3. Gaussian smoothing yields finite \mathcal{R}\mathrm{TV} but is dimension-dependent. Convolution with an isotropic Gaussian produces \|f_{\sigma}\|_{\mathcal{R}}<\infty with an explicit bound that scales exponentially in d . 4. Classification via thresholding admits finite- \mathcal{R}\mathrm{TV} exact recovery. We construct a smooth barrier score S_{B} with \{S_{B}\geq 1\}=B and prove (i) an L_{1}(P) calibration bound under a tube-mass condition and (ii) an explicit \mathcal{R}\mathrm{TV} upper bound in terms of the box face measures. 5. Experiments. On synthetic unions of rectangles, we empirically trace the calibration–complexity frontier and illustrate how post hoc threshold tuning changes the induced decision set without changing the underlying learned score. So, if one only cares about the thresholded classifier , shallow nets can represent trees easily. If one cares about learning a score that is both interpretable (low \mathcal{R}\mathrm{TV} , gradients aligned to splits) and close to the symbolic model, a quantitative trade-off emerges. This clarifies what exactly is in tension and why thresholding alone can mask feature misalignment. 2 Related Work The accuracy–interpretability debate. Early empirical work reported an apparent performance gap between transparent models (linear regressions, GAMs, decision trees) and deep neural nets ( 4 ) . More recent benchmarks and case studies nuance this picture: in some regimes, carefully tuned interpretable models can rival black-box baselines, and the relationship between interpretability and predictive performance can be non-monotonic ( 16 ; 1 ) . In high-stakes settings, some authors argue that the presumed trade-off is overstated and advocate for interpretable-by-design predictors ( 27 ) . Our analysis sharpens this discussion by identifying a dimension-dependent regime—captured through a geometric complexity measure—in which high accuracy necessarily coincides with large complexity. Complexity measures for neural functions. Generalisation guarantees for neural networks are typically phrased in weight-space norms, e.g., the path-norm ( 21 ) , products of spectral norms ( 2 ) , or Neural Tangent Kernel radii ( 11 ) . While these quantities can correlate with test error (and sometimes robustness), their connection to geometric properties of decision boundaries is indirect. A complementary viewpoint is provided by the Radon bounded-variation space \mathcal{R}\mathrm{BV}^{2}({\Omega}) ( \Omega\subseteq\mathbb{R}^{d} ), defined via bounded Radon-domain total variation ( \mathcal{R}\mathrm{TV} ) ( 28 ) . Representer theorems show that shallow ReLU networks trained with weight decay admit \mathcal{R}\mathrm{BV}^{2}({\Omega}) solutions ( 24

Read the complete text