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
Figure 1: The exponent functions β0(γ) and β1(γ) .
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.
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.
Figure 4: Mean terminal-cell lengths for the hybrid Brownian–linear signal. Points are Monte Carlo averages over 400 repetitions, with error bars indicating ±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∗(x)=x11/2+x21/4 at x=0 . Points show Monte Carlo averages of logℓj(0) over 400 repetitions, error bars show ±1 standard error on the log scale, and dashed lines show least-squares fits of logℓj(0) on logn .
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.
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)
Classification and regression trees are typically constructed using a greedy splitting rule that maximizes the immediate reduction in prediction error at each node. Although this strategy is computationally efficient, it can miss splits that yield small short-term gains but create substantial downstream improvements after further partitioning. We propose a look-ahead tree-building method that evaluates each candidate split by the prediction error reduction achieved after growing a conventional CART subtree below that split. Because the full look-ahead procedure can be computationally expensive, we also describe a smart look-ahead algorithm that learns downstream split values using node-level features. The proposed framework preserves the interpretability of recursive partitioning while improving split selection in hierarchical or interaction-driven settings. We conduct a simulation study comparing conventional, full look-ahead, and smart look-ahead methods under several settings and apply the proposed methods to analyze two real data examples demonstrating the merit of the new methods.
Andrew Gao, Tianlin Liu, Ruichen Han +1
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 are among the most widely used modern predictive methods, with well-documented empirical success. Yet, at the mechanistic level, the algorithm is often treated as a black box because of its complexity. In this paper, we develop a stochastic-control perspective on feature-subsampled CART random forests, named CART random opportunity-set allocation (CART-ROSA). At each node, the random subset of features is interpreted as a random feasible action set, and the CART split rule as a masked-action allocation policy. This policy induces a controlled stochastic process over informative split-count states, whose terminal law determines both single-tree error and cross-tree interaction terms in the forest mean squared error (MSE). Such representation opens the black box of CART-forests by separating two design levers: the informative-opportunity rate induced by feature subsampling, and the contraction strength from the within-mask split policy. We establish that the CART policy is locally stabilizing: it contracts imbalances in informative split allocations and concentrates terminal tree geometry. At the system level, however, it can be globally suboptimal for the forest objective. Specializing to the linear model, we derive the MSE risk expansion explicitly. Our results show how an operations-research perspective makes tractable a theoretical gap difficult to access from the standard algorithmic description of CART forests.
Tianxing Mei, Yingying Fan, Mingming Leng +1
Faculty of Business, Lingnan University · Data Sciences and Operations Department, University of Southern California