On Stopping Rules and Spatial Adaptation for CART

Zineng Xu; Yuchao Cai; Yan Shuo Tan

stat.MLAug 16, 2026

On Stopping Rules and Spatial Adaptation for CART

Authors: Zineng Xu, Yuchao Cai, Yan Shuo Tan

Organizations: Department of Statistics and Data Science, National University of Singapore

Abstract

The popular CART algorithm for regression trees combines a greedy splitting rule with a stopping rule, but while the splitting rule has been well studied, the statistical role of stopping rules is less well understood. Meanwhile, although regression trees fit using Bayesian methods or via empirical risk minimization (ERM) have been shown to be spatially adaptive to local smoothness and anisotropy, it is unknown whether CART can achieve the same adaptation. We address these gaps by proving that, under spatially heterogeneous and anisotropic smoothness and appropriate structural assumptions on the regression function and covariate distribution, CART with the minimum impurity decrease (MID) stopping rule and a suitable threshold achieves pointwise rates that are minimax up to logarithmic factors. These rates hold simultaneously over all points in the domain. Moreover, we prove that spatial adaptation cannot be achieved under the widely used minimum leaf size stopping rule. Together, these results establish a precise statistical role for the MID stopping rule and provide a theoretical basis for the empirical success of CART.

Figures & tables

Panel of Figure 1 — Figure 1: The exponent functions $\beta_{0}(\gamma)$ and $\beta_{1}(\gamma)$ .

Figure 2: A CART-MID fit to the hybrid Brownian–linear signal. The regression function is shown in black, the training sample in gray, and the fitted tree in red.

Panel of Figure 3 — Figure 3: Pointwise Monte Carlo bias–variance decomposition for the hybrid Brownian–linear signal. The columns compare CART-MID and CART-MLS, and the rows correspond to $x=0.25$ and $x=0.75$ . The vertical scale is allowed to differ across panels so that all three components remain visible.

Panel of Figure 4 — Figure 4: Mean terminal-cell lengths for the hybrid Brownian–linear signal. Points are Monte Carlo averages over 400 repetitions, with error bars indicating $\pm 1$ standard error. The panels compare CART-MID and CART-MLS; each panel shows both $x=0.25$ and $x=0.75$ .

Figure 5: Coordinate-wise terminal-cell side lengths for $f^{*}(\mathbf{x})=x_{1}^{1/2}+x_{2}^{1/4}$ at $\mathbf{x}=\mathbf{0}$ . Points show Monte Carlo averages of $\log\ell_{j}(\mathbf{0})$ over 400 repetitions, error bars show $\pm 1$ standard error on the log scale, and dashed lines show least-squares fits of $\log\ell_{j}(\mathbf{0})$ on $\log n$ .

Decision Tree Learning

Decision tree learning builds hierarchical, rule-based models for prediction, balancing accuracy, computational cost, and interpretability.

See all 69 papers

A Bregman Perspective on Classification and Regression Trees
Jun 12, 2026Mathias BourelFunctional Bregman Divergences Decision Tree Learning
IESTA, Facultad de Ciencias Económicas y de Administración, Universidad de la República, Uruguay · IRL-2030, Instituto Franco-Uruguayo de Matemática e Interacciones (IFUMI)
Learned Look-Ahead Splitting Rule for CART
Sep 14, 2026Andrew Gao, Tianlin Liu, Ruichen Han +1Decision Tree Learning Classification
Thomas Jefferson High School for Science and Technology, Alexandria, VA 22312, USA · Lynbrook High School, San Jose, CA 95129, USA · Department of Biomedical Data Science, Stanford University, Stanford, CA 94305, USA
CART Random Forests as Sequential Allocation over Random Opportunity Sets: A Stochastic-Control Theory of Ensemble Risk
May 26, 2026Tianxing Mei, Yingying Fan, Mingming Leng +1Ensemble Learning Statistical Learning Theory
Faculty of Business, Lingnan University · Data Sciences and Operations Department, University of Southern California

Jun 12, 2026J/K move · Enter open · S save

A Bregman Perspective on Classification and Regression Trees

Mathias Bourel

IESTA, Facultad de Ciencias Económicas y de Administración, Universidad de la República, Uruguay · IRL-2030, Instituto Franco-Uruguayo de Matemática e Interacciones (IFUMI)

Functional Bregman Divergences Decision Tree Learning Classification Statistical Learning Theory

Open paper AskPDF arXiv

Classification and Regression Trees (CART) constitute one of the most influential paradigms in statistical learning. Although a variety of impurity measures have been proposed for different statistical models, these criteria are typically introduced on a case-by-case basis and analyzed separately. In this paper, we study CART through the lens of Bregman divergences. This perspective places the classical least-squares criterion, Poisson deviance, Kullback-Leibler-type losses, and other impurity measures associated with exponential-family models within a common framework. As a result, key ingredients of the CART methodology -- including node representatives, impurity measures, and split selection rules -- can be expressed and analyzed through general properties of convex functions rather than through separate model-specific constructions. Beyond the algorithmic formulation, we investigate theoretical properties of Bregman-based CART procedures. In particular, we analyze how geometric properties of the generating convex function influence impurity reductions and stability of recursive partitions. We also establish consistency results within the proposed framework, providing a unified theoretical treatment for a broad family of CART type procedures. Our results provide a geometric interpretation of impurity-based tree construction and show that many classical CART impurity criteria admit a common interpretation within a Bregman framework.

Abstract

Decision Tree Learning

Explore similar work

A Bregman Perspective on Classification and Regression Trees

Learned Look-Ahead Splitting Rule for CART

CART Random Forests as Sequential Allocation over Random Opportunity Sets: A Stochastic-Control Theory of Ensemble Risk