Regression Trees Know Calculus

Nathan Wycoff

Abstract

Regression trees have emerged as a preeminent tool for solving real-world regression problems due to their ability to deal with nonlinearities, interaction effects and sharp discontinuities. In this article, we rather study regression trees applied to well-behaved, differentiable functions, and determine the relationship between node parameters and the local gradient of the function being approximated. We find a simple estimate of the gradient which can be efficiently computed using quantities exposed by popular tree learning libraries. This allows the tools developed in the context of differentiable algorithms, like neural nets and Gaussian processes, to be deployed to tree-based models. To demonstrate this, we study measures of model sensitivity defined in terms of integrals of gradients and demonstrate how to compute them for regression trees using the proposed gradient estimates. Quantitative and qualitative numerical experiments reveal the capability of gradients estimated by regression trees to improve predictive analysis, solve tasks in uncertainty quantification, and provide interpretation of model behavior.

Introduction

Regression trees and their ensemble variants, such as Random Forests and XGBoost, are the "workhorses" of modern data science. Their popularity stems from their robustness in handling non-linearities and discontinuities without extensive feature engineering. However, these models have historically been viewed as non-differentiable "staircase" functions. Because standard trees are piecewise-constant, their mathematical gradient is zero almost everywhere and undefined at split boundaries.

This lack of differentiability makes it difficult to apply gradient-based interpretability methods—like Integrated Gradients—or dimension reduction techniques like the Active Subspace Method. This paper bridges the gap by introducing a method to extract meaningful "implicit" gradients from the internal structure of regression trees.

Methodology: The Tree-Based Gradient Estimator (TBGE)

The core innovation is the Tree-Based Gradient Estimator (TBGE). Rather than treating a leaf node as a flat surface, the authors interpret the splits themselves as finite differences.

When a tree splits a node into a left child (with mean $\hat{\mu}_l$) and a right child (with mean $\hat{\mu}_r$) along a specific variable, the difference between these means, normalized by the node's width, serves as a proxy for a partial derivative. By traversing the tree to a specific point $x$ and aggregating these split-based partial derivatives from all upstream nodes, a full gradient vector $\nabla f(x)$ can be constructed using only existing tree parameters.

Convergence of the TBGE gradient estimate to the true vector field as tree depth increases.

As shown in the figure above, as the depth of the tree increases, the estimated vector field increasingly resembles the true gradient of the underlying function. This allows for the computation of Integrated Gradients for local feature importance and Tree-Based Active Subspaces (TBAS) for global dimension reduction.

Key Insights and Results

The paper validates the TBGE across several benchmarks, including UCI regression datasets, MNIST, and the NHEFS mortality dataset. Several key findings emerged:

  • Scalability: For large datasets ($N > 10,000$), tree-based gradient estimation is significantly faster than Gaussian Processes or Neural Networks, often providing the best trade-off between error and compute time.
  • Sparse Inductive Bias: Trees naturally split on one variable at a time, giving them an inherent bias toward coordinate-sparse subspaces. This makes them highly effective at identifying key features in high-dimensional spaces where only a few variables are truly influential.
  • Improved Prediction via Rotation: Using TBAS to identify an "active subspace" and then rotating the data into that space before training a final tree significantly improved RMSE on datasets like kin40k and keggu.
  • Interpretability: On MNIST, the method produced saliency maps that intuitively highlighted critical features, such as the crossbar of a '7' or the center intersection of an '8'.

Conclusion and Future Work

While the TBGE offers a powerful new tool for tree-based modeling, it faces challenges with slow convergence—requiring large datasets and deep trees for high precision—and inconsistent performance on classification tasks. Future research may extend this framework to categorical data and explore the estimation of higher-order derivatives, such as Hessians, directly from tree structures. By revealing that regression trees "know" calculus, this work opens the door for tree-based models to utilize the sophisticated analytical tools previously reserved for smooth, differentiable architectures.

Summary updated

Abstract

Regression trees have emerged as a preeminent tool for solving real-world regression problems due to their ability to deal with nonlinearities, interaction effects and sharp discontinuities. In this article, we rather study regression trees applied to well-behaved, differentiable functions, and determine the relationship between node parameters and the local gradient of the function being approximated. We find a simple estimate of the gradient which can be efficiently computed using quantities exposed by popular tree learning libraries. This allows the tools developed in the context of differentiable algorithms, like neural nets and Gaussian processes, to be deployed to tree-based models. To demonstrate this, we study measures of model sensitivity defined in terms of integrals of gradients and demonstrate how to compute them for regression trees using the proposed gradient estimates. Quantitative and qualitative numerical experiments reveal the capability of gradients estimated by regression trees to improve predictive analysis, solve tasks in uncertainty quantification, and provide interpretation of model behavior.
BibTeX
@inproceedings{wycoff2025regression,
  author = {Nathan Wycoff},
  title = {{Regression Trees Know Calculus}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=wFXvD83mhb},
}
Figure