PaperlayerView exact revision on arXiv

Source-linked AI summary

On Stopping Rules and Spatial Adaptation for CART

Zineng Xu, Yuchao Cai, Yan Shuo Tan

arXiv:2608.15649v1stat.MLcs.LGmath.ST

TL;DR

The paper asks whether CART can adapt to spatially varying and anisotropic smoothness, and studies this through its stopping rule. It proves that minimum impurity decrease enables near-minimax pointwise adaptation, whereas minimum leaf size cannot achieve the same adaptation.

  • Problem

    It is unknown whether CART achieves spatially adaptive pointwise rates, despite such adaptation being established for Bayesian and ERM-based regression trees.

    Source: §1 · p. 1, §2.8 · p. 8

  • Method

    The paper analyzes greedy CART with minimum impurity decrease under locally anisotropic Hölder smoothness and structural assumptions on the regression function and covariates.

    Source: §1 · p. 2, §2.5 · p. 5, §3.1 · p. 12

  • Results

    CART-MID achieves minimax-optimal pointwise rates up to logarithmic factors simultaneously over the domain, while minimum leaf size cannot adapt to differing local smoothness.

    Source: §1 · p. 2, §9 · p. 24

  • Takeaways & Limitations

    The results show that CART’s stopping rule is statistically consequential, with MID enabling local adaptation by selecting a scale aligned with splitting.

    Source: §1 · p. 3, §9 · p. 24

    Extending the theory to cost-complexity pruning or random forests requires modifying the parent–child certificate argument.

    Source: §9 · p. 24

Abstract

from arXiv · show

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.

1 Introduction

The introduction identifies stopping rules as an under-theorized component of CART and asks whether greedy CART can achieve pointwise adaptation to heterogeneous, anisotropic smoothness. It previews results showing that CART-MID attains locally adaptive pointwise rates, whereas minimum leaf size cannot.

Motivation

  • Stopping rules regularize tree size and have a less understood statistical role than CART’s widely studied impurity-decrease splitting rule.The introduction frames stopping as central to both split reliability and the terminal cell used for local averaging.Source: §1 · pp. 1–2
  • The paper addresses gaps in existing theory by studying pointwise rather than primarily global L2 risk and by examining adaptation to spatially heterogeneous smoothness and anisotropy.These questions matter for personalized decision-making and remain unresolved for greedy CART despite adaptation results for ERM and Bayesian trees.Source: §1 · pp. 1–2

Stopping-rule mechanism

  • Under the SID condition, stopping when empirical impurity decrease reaches its noise floor both prevents noise-driven splits and selects the local bias-variance tradeoff needed for pointwise averaging.Although split reliability and optimal averaging need not generally occur at the same scale, SID links them for CART-MID.Source: §1 · p. 2

Main contributions

  • CART-MID achieves minimax-optimal pointwise rates up to logarithmic factors for anisotropic locally Hölder functions in one-dimensional and sparse high-dimensional settings, simultaneously across all domain points without knowing local smoothness.The guarantees hold on the same high-probability event and rely on structural assumptions, including the SID condition in the high-dimensional analysis.Source: §1 · p. 2
  • Minimum leaf size cannot simultaneously select correct local bandwidths at points with different smoothness, preventing spatial adaptation.This establishes a statistical mismatch between fixed leaf-size regularization and the locally varying tasks required for pointwise adaptation.Source: §1 · p. 2

Interpretation

  • The results characterize early stopping as essential regularization because MID uses the splitting rule’s empirical scale to preserve reliability and select the bandwidth required for local averaging.This gives stopping a substantive statistical role rather than treating it as a secondary implementation detail.Source: §1 · p. 3

2 Setup and preliminaries

This section defines the regression setting, CART’s cells, splits, impurity decreases, and stopping rules. It also develops concentration tools, the sufficient impurity decrease condition, and the pointwise framework for spatially heterogeneous and anisotropic adaptation.

2.1 Regression model

  • The paper studies pointwise estimation of f* from independent observations under a regression model with potentially heteroskedastic mean-zero noise and regularity assumptions.The covariate density is bounded above and below on [0, 1]^d.Source: §2.1 · p. 3

2.2 Notation

  • Notation distinguishes random variables, fixed vectors, coordinate subsets, probabilities, moments, essential suprema, and universal or parameter-dependent comparison constants.These conventions include [k] = {1, . . . , k}, complements S_c, coordinate subvectors x_S, and the relations ≲ and ≍.Source: §2.2 · p. 3

2.3 Cells

  • Cells are axis-aligned rectangles in [0, 1]^d, described through coordinate-wise side lengths, volume, and classes restricting which coordinates may vary.The notation supports tracking anisotropic changes across selected coordinate sets.Source: §2.3 · p. 4

2.4 Splits and impurity decrease

  • A split partitions a cell along one coordinate, while impurity decrease measures the weighted reduction in response variance empirically or conditional regression-function variance at the population level.The empirical and population quantities correspond respectively to reductions in training and expected test error, and their maxima define empirical and population split signals.Source: §2.4 · pp. 4–5

2.5 CART and stopping rules

  • CART recursively selects the split maximizing empirical impurity decrease until stopping, then predicts by averaging responses in the terminal cell, which acts as a data-adaptive local bandwidth.The section compares minimum impurity decrease stopping with minimum leaf size stopping.Source: §2.5 · p. 5

2.6 Concentration for cell averages and impurity decrease

  • Uniform concentration controls both empirical impurity decreases and cell averages, with impurity fluctuations independent of cell size and a stopping threshold that can prevent unreliable splits and certify child mass.These bounds support applying cell-average concentration along the adaptively constructed tree.Source: §2.6 · pp. 6–7

2.7 Sufficient impurity decrease

  • Sufficient impurity decrease requires every cell to have an axis-aligned split removing a non-negligible fraction of its variation, excluding adversarial cases such as pure interactions.Here SID is used locally along a query point’s root-to-leaf path: combined with MID stopping, it converts empirical split-signal control into residual-variation control in the terminal cell.Source: §2.7 · p. 7

2.8 Spatial adaptation

  • Spatial adaptation is formulated through pointwise rates that vary with local regularity, with CART’s terminal cell serving as an implicitly selected neighborhood under locally anisotropic Hölder smoothness.Unlike kernel methods, CART does not choose a bandwidth directly; greedy splitting and early stopping determine the local neighborhood, while the framework permits extensions to locally varying regularity constants.Source: §2.8 · p. 8

3 Warm-up: 1D pointwise spatial adaptation for CART-MID

This section explains heuristically and rigorously how CART-MID selects locally appropriate bandwidths in one dimension, achieving uniform pointwise adaptation under stated regularity conditions. The proof uses local impurity signals, bias visibility, and only a weak local balance property.

3 Warm-up: 1D pointwise spatial adaptation for CART-MID

  • The one-dimensional heuristic treats terminal-cell length as a local bandwidth, balancing Hölder bias of order h^α(x) against stochastic leaf-averaging error.Unlike regressograms and kernel estimators, CART must discover this bandwidth through greedy splits and stopping.Source: §3 · pp. 8–9
  • CART-MID achieves the correct local bandwidth scale at every query point, up to logarithmic factors, when its threshold is set near the noise floor.The SID condition links empirical maximum impurity decrease to residual variation above the noise floor, without knowing local smoothness.Source: §3 · p. 9
  • Under bounded density, sub-Gaussian responses, local Hölder smoothness, and sufficient impurity decrease, the theorem gives a uniform pointwise upper bound with probability at least 1 − e^-u.The conclusion holds simultaneously for all x ∈ [0, 1].Source: §3 · p. 9, §3.1 · p. 11

3.1 Proof of Theorem 3.1

  • The proof converts terminal-cell and parent-split impurity certificates into local residual-variation and leaf-mass controls, then combines them with bias visibility for pointwise error bounds.The argument follows only the root-to-leaf path containing the query point and uses uniform concentration over intervals and splits.Source: §3.1 · pp. 10–11
  • The analysis does not require balanced splits: competitiveness ensures only that the child containing the query point is not too small relative to its parent’s residual variation.This local lower bound is the sole balance property used in the proof.Source: §3.1 · pp. 9, 12

4 Pointwise spatial adaptation for CART-MID

Under local anisotropic Hölder smoothness, structural regularity, and sparsity-separation conditions, CART-MID achieves a uniform pointwise upper bound in sparse high-dimensional settings. The resulting rate is minimax-optimal up to logarithmic factors and adapts to local harmonic smoothness and the unknown relevant coordinates.

Structural conditions

  • In multiple dimensions, impurity-decrease splitting adaptively refines rougher coordinates more than smoother ones, while the proof requires pathwise split-scale regularity and bias visibility.Sparsity separation additionally ensures that greedy splits select relevant coordinates in high-dimensional settings.Source: §4 · pp. 12–13

Main theorem

  • CART-MID achieves a uniform pointwise upper bound under bounded density, sub-Gaussian responses, local anisotropic Hölder smoothness, sufficient impurity decrease, and Assumptions 4.1–4.3.The guarantee holds with probability at least 1 − e^-u when the threshold satisfies the stated parameter and δ ≤ 1 conditions.Source: §4 · p. 13

Minimax optimality

  • The bound attains the pointwise minimax rate up to logarithmic factors over anisotropic Hölder classes, with exponent ᾱ_S(x)/(2ᾱ_S(x)+s).CART-MID does not know the local harmonic smoothness or relevant set, and ambient dimension enters only through the split-search logarithm.Source: §4 · pp. 13–14

Comparison with previous work

  • Unlike earlier global L2(P) CART analyses based on SID, Theorem 4.4 has the usual pointwise smoothness exponent, with SID-like constants entering polynomially through a scale factor.The multidimensional pointwise argument instead requires local geometric conditions: competitive split-scale regularity, bias visibility, and sparsity separation.Source: §4 · p. 14

Threshold selection

  • Cross-validation can select the MID threshold while preserving the corresponding integrated L2(P) rate, but an analogous uniform pointwise guarantee is more difficult.Global validation may miss errors localized to small terminal cells.Source: §4 · p. 14

5 Sufficient conditions for the structural assumptions

This section develops interpretable sufficient conditions for the abstract structural assumptions underlying CART-MID’s pointwise adaptation results. It also constructs multivariate examples satisfying these conditions and identifies a limitation of piecewise-LRP functions.

5.1 Local norm equivalence and bias visibility

  • Local norm equivalence controls sup-norm variation by conditional L2 variation, preventing spiky regression functions from hiding bias and implying bias visibility under a stated compatibility condition.Under bounded density, local norm equivalence on A_S implies bias visibility for any ζ ≥ 1 and χ ∈ (0, 1] satisfying ζ^2 ≥ ρ χ^-1.Source: §5.1 · p. 15

5.2 Pathwise competitive split-scale regularity

  • Under local anisotropic Hölder smoothness, sufficient impurity decrease, and local norm equivalence, pathwise competitive split-scale regularity follows.The proof combines bounds on ancestor split signals, competitive-split balance, and residual variation along paths to lower-bound terminal side lengths.Source: §5.2 · p. 15

5.3 Locally reverse Poincaré as a building block for SID and LNE

  • Locally reverse Poincaré components yield multivariate additive and sums-of-products models satisfying sufficient impurity decrease and local norm equivalence, while independent coordinate blocks preserve both properties.The corresponding constants depend on the LRP constant, bounded component ranges where applicable, dimension, and the individual block constants.Source: §5.3 · pp. 16–17
  • Piecewise LRP can ensure sufficient impurity decrease but not local norm equivalence, because a discontinuity may eliminate residual variance while retaining large oscillation.The section illustrates this with g(x) = 1{x > 1/2}, whose split removes all residual variation despite unit oscillation near the joining point.Source: §5.3 · pp. 16–17

6 Pointwise lower bound for CART-MLS

This section proves a pointwise lower bound showing that CART with minimum leaf size cannot simultaneously attain optimal rates at points with different smoothness. The obstruction is global bandwidth selection, contrasting with CART-MID’s spatial adaptation.

Theorem 6.1

  • Theorem 6.1 establishes pointwise lower bounds for ordinary and honest CART-MLS in a one-dimensional model with bounded density, f*(x)=x^1/2, and Gaussian noise.The result holds for sufficiently large n and every fixed minimum leaf size N.Source: §6 · p. 17
  • The rough endpoint x=0 is optimized at gamma=1/2, whereas the smoother endpoint x=1 is optimized at gamma=2/3 when N_n=floor(n^gamma).Thus one global minimum leaf size cannot optimize pointwise rates at both endpoints.Source: §6 · pp. 17–18, Figure 1 · p. 18

Remark 6.2

  • The failure persists even when relevant splits are reliable, because the MLS rule uses one global leaf-size parameter to choose local bandwidths.The proof relies on endpoint geometry, terminal cell sizes, and the bias and noise of averaging over those cells.Source: §6 · p. 18

Remark 6.3

  • Honesty changes only the stochastic proof component: honest leaves have fixed conditional Gaussian noise, while ordinary CART requires a uniform noise-persistence event.For ordinary CART, the selected leaf depends on the same responses being averaged.Source: §6 · p. 18

Remark 6.4

  • Because f*(x)=x^1/2 satisfies the paper’s structural conditions, Theorems 6.1 and 3.1 establish a rigorous performance gap between CART-MLS and CART-MID.The supporting propositions verify LRP, SID under bounded density, and the relevant smoothness condition.Source: §6 · p. 18

7 Noise-driven splits and end-cut preference

This section shows that end-cut preference does not by itself prevent optimal pointwise rates, but noise-driven splits can create severe prediction problems when local signal is below the noise level. The results therefore support preventing such splits as necessary for optimal pointwise rates, while noting that a full lower-bound proof remains open.

End-cut preference and optimal rates

  • CART’s end-cut preference can coexist with optimal pointwise rates because Theorem 3.1 requires only competitive split-scale regularity, not balanced splits.Thus, unbalanced population splits do not automatically preclude optimal adaptation.Source: §7 · p. 19
  • For a shifted ReLU with uniform covariates, population CART can produce an end split whose child has vanishing mass but length comparable to the residual signal scale, while CART-MID still attains the optimal pointwise rate at 0.The function satisfies the SID condition, so Theorem 3.1 applies.Source: §7 · p. 19

End-cut preference under weak split signal

  • Extending Cattaneo et al. (2026), the paper shows that quantitative end-cut preference persists for nonconstant regression functions when local residual variation falls below the noise level.This strengthens the case that preventing noise-driven splits is necessary for optimal pointwise rates.Source: §7 · p. 19
  • When the MID threshold is o((n log log n)^-1), CART can produce leaves with n^b samples with nonvanishing probability, inflating leaf-average variance to n^-b/2 and potentially worsening minimax rates.A rigorous pointwise lower bound remains open because Theorem 7.2 assumes deterministic cell sequences, whereas CART generates random cells.Source: §7 · pp. 19–20

8 Experiments

The experiments show that CART-MID adapts locally across rough and smooth regions with one global threshold, and adapts terminal-cell shapes to anisotropic smoothness across coordinates. CART-MLS instead exhibits a global tuning conflict between local scales.

Experimental setup

  • The experiments use a rough scaled Brownian segment joined to a Lipschitz linear segment and a two-dimensional additive signal with anisotropic local smoothness.The Brownian path is almost surely α-Hölder for every α < 1/2, while the linear segment is Lipschitz; simulations use 400 Monte Carlo repetitions.Source: Experimental setup · pp. 20, 23

Results

  • A CART-MID fit to the hybrid Brownian–linear signal uses smaller cells in the rough Brownian region and stops earlier in the smooth linear region.Thus one global impurity-decrease threshold produces different local resolutions across the domain.Source: Figure 2 · p. 21, Results · p. 21

CART-MID CART-MLS

  • CART-MID has a broad common threshold range, whereas CART-MLS requires incompatible leaf sizes across rough and smooth regions.CART-MID MSE is minimized near 1.6 × 10−3 at x = 0.25 and 1.07 × 10−3 at x = 0.75; CART-MLS optima are about 45 and 105–135.Source: Results · p. 21, Figure 3 · p. 22
  • CART-MID selects much smaller terminal cells in the rough region than the smooth region, while CART-MLS produces nearly equal cell lengths under a fixed leaf size.Under the uniform design, the common leaf-size constraint explains CART-MLS’s tuning conflict by enforcing comparable cell lengths throughout the domain.Source: CART-MID CART-MLS · p. 22, Figure 4 · p. 23

Results

  • CART-MID’s coordinate-wise cell-shrinkage slopes are −0.320 and −0.529, matching the benchmark ordering −1/4 and −1/2 and showing faster shrinkage along the less smooth coordinate.The second coordinate has local Hölder exponent 1/4 versus 1/2 for the first coordinate at the origin.Source: Results · pp. 23–24, Experimental setup · p. 23, Figure 5 · p. 24

9 Discussion … B.1 Proofs for uniform concentration with empirical Rademacher complexity

The paper establishes that CART achieves spatial adaptation when using the MID stopping rule, while its discussion identifies obstacles to extending the theory and its appendices provide the algorithm and uniform-concentration tools supporting the proofs.

9 Discussion

  • CART achieves spatial adaptation under the MID stopping rule, which is crucial for matching the adaptation known for ERM and Bayesian trees.Source: §9 · p. 24
  • Extending the certificate-based theory to cost-complexity pruning or random forests requires modifying the parent–child argument because each method can fail to certify a strong parent split.Cost-complexity pruning controls aggregate retained-branch gain, while feature subsampling can hide relevant coordinates.Source: §9 · p. 24
  • The discussion also identifies weakening LNE as an open direction because the condition is extremely strong.Source: §9 · p. 24

A Algorithmic details

  • Algorithm 1 grows early-stopped CART from the root by repeatedly selecting an admissible split with maximum impurity decrease at least δ and replacing the active leaf by its two children.Source: A Algorithmic details · p. 27

B.1 Proofs for uniform concentration with empirical Rademacher complexity

  • The concentration proof localizes indicator classes of cells with r active coordinates and uses empirical Rademacher complexity whose governing parameter is rlog(n d).Sample-trace counting, symmetrization, contraction, high-probability bounds, and peeling yield uniform control over the relevant classes.Source: §B.1 · p. 27
  • Under sub-Gaussian responses, the proof obtains simultaneous high-probability control for cell-based multiplier processes and localized deviations over every active-coordinate level r.The argument uses signed classes, localized radii, bounded envelopes and variances, and a peeling union bound.Source: §B.1 · p. 29
  • Uniform concentration extends to cell counts and bounded cell averages, distinguishing large cells—where empirical and population probabilities are comparable—from small cells controlled at the rlog(n d)/n scale.These results support the uniform concentration statement used in the proof of Lemma 2.6.Source: §B.1 · pp. 30–31

B.2 Proof of Lemma 2.5 · C Proofs for the one-dimensional upper bound

The proof establishes uniform concentration for weighted cell means and uses it to control empirical impurity decreases across all cells, coordinates, and split thresholds. These bounds yield the stated lemma and imply that sufficiently large population impurity decreases force both child cells to retain probability mass of order (r log(nd)+u)/n.

B.2 Proof of Lemma 2.5

  • Uniform weighted cell-mean concentration holds simultaneously over resolutions and cells with failure probability at most e^-u.The argument combines concentration for empirical and population masses with conditional sub-Gaussian noise control, sample-trace counting, and union bounds.Source: §B.2 · pp. 32–33
  • The concentration argument handles both well-populated and low-population cells by comparing empirical and population masses or invoking boundedness directly.When p_B is comparable to or larger than ε_n,r,u, the masses are comparable; when p_B is smaller, the empirical mass is also controlled by ε_n,r,u.Source: §B.2 · pp. 32–33
  • Conditional on the covariates, centered noise averages are sub-Gaussian, and a sample-trace counting argument plus union bounds makes the control uniform over all relevant traces.For each resolution r, the number of distinct traces is at most exp{3r log(nd)}, enabling a uniform tail bound.Source: §B.2 · p. 33
  • The resulting event controls the empirical impurity-decrease approximation uniformly, completing the proof of Lemma 2.5.The proof combines the concentration inequalities for weighted means and the associated variance terms, then applies a final union bound.Source: §B.2 · pp. 33–34
  • Applying the uniform cell-mean bound to a parent and its two children preserves the concentration scale up to a universal factor.The child cells lie at resolution min(d,r+1), and the resulting bounds are uniform over r, A, j, and b, including zero-mass cases.Source: §B.2 · pp. 33–34
  • Population and empirical variance-decomposition identities connect impurity decrease to parent and child weighted means, including cells with zero empirical or population mass.These identities provide the algebraic basis for transferring concentration bounds on cell means into bounds on empirical impurity decreases.Source: §B.2 · p. 34
  • If the population impurity decrease is sufficiently large, the left child has probability at least c(r log(nd)+u)/n.The proof chooses the constant C in the population impurity-decrease condition large enough to dominate the concentration error.Source: §B.2 · p. 34
  • The same lower bound applies to the right child because its population probability is at least that of the left child.Thus both children satisfy the required mass condition under the prescribed impurity-decrease threshold.Source: §B.2 · p. 34

C.1 Technical lemmas for Theorem 3.1 · D Proof of the CART-MID upper bound

The technical lemmas establish local lower bounds from Hölder regularity and control variance across competitive CART splits, supporting the CART-MID upper-bound analysis.

C.1 Technical lemmas for Theorem 3.1

  • A local Hölder condition yields a neighborhood A1 around x where |g(t)| remains at least U0/2.Choosing r := (U0/(2L))^(1/α0) gives A1 := A ∩ (x−r, x+r).Source: §C.1 · pp. 34–35
  • The resulting neighborhood-size and variance bounds are handled by separate cases according to whether 2r is at most Vol(A).The proof factors the variance into powers 1/(1 + 2α0) and 2α0/(1 + 2α0) to recover the claimed order.Source: §C.1 · p. 35
  • Together, the local signal and competitive-split lemmas establish the claimed order needed for the CART-MID upper-bound proof.The local argument concludes by identifying the bound with equation (16).Source: §C.1 · p. 35
  • For a competitive split, the proof sets θ0 := α0/(1 + 2α0) and r0 := 1/(1 + 2α0), while sufficient impurity decrease permits λ ≤ 1.These exponents organize the split-dependent variance and approximation bounds.Source: §C.1 · p. 35
  • When the child containing x is the smaller child and has probability at least 1/3, density regularity lower-bounds its volume relative to the parent.The comparison uses p := P(A_sm)/P(A′) and ρ := Vol(A_sm)/Vol(A′), together with p_min and p_max.Source: §C.1 · p. 36
  • For the complementary case p < 1/3, impurity and tower identities reduce the relevant conditional-mean error to a term bounded by L^2 r0 V(A′)^(2θ0).The argument combines Lemma 3.3 with V(A_sm) ≤ V(A′).Source: §C.1 · p. 36

D.1 Intermediate results for CART-MID · D.2 Proof of the CART-MID upper bound · D.3 Proofs of the CART-MID intermediate results

These sections establish the high-probability path regularity, approximation, and estimation ingredients behind the CART-MID upper bound. They combine concentration, sparsity preservation, competitive splitting, and the MID stopping rule to obtain uniform pointwise control.

D.1 Intermediate results for CART-MID

  • Propositions D.2 and D.3 separately bound CART-MID’s approximation and estimation errors under Theorem 4.4’s conditions and the prescribed threshold.The empirical estimator is decomposed into bias from averaging over the terminal cell and sampling fluctuation of its leaf average.Source: §D.1 · pp. 37–38
  • The MID stopping threshold links empirical impurity, terminal-cell bias, and leaf volume, yielding the local bandwidth scale required for pointwise adaptation.Stopping controls maximal terminal impurity, sufficient decrease controls residual variation, and competitive split-scale regularity supplies a terminal-volume lower bound.Source: §D.1 · pp. 37–38
  • CART-MID paths preserve sparsity and use competitive splits simultaneously for every x with probability at least 1 − e^-u.The regularity proposition establishes these properties under Theorem 4.4’s conditions when the threshold exceeds the impurity concentration scale.Source: §D.1 · p. 37

D.3 Proofs of the CART-MID intermediate results

  • Uniform concentration and the sparsity-separation condition prevent empirical CART-MID from splitting on irrelevant coordinates.The proof uses induction along each path: an irrelevant split would contradict empirical optimality combined with concentration and the separation gap.Source: §D.1 · p. 37, §D.3 · p. 39

D.2 Proof of the CART-MID upper bound

  • Theorem 4.4 follows by intersecting the high-probability events for approximation, estimation, and path regularity, then showing the estimation term is bounded by the approximation rate.A union bound provides simultaneous validity, while parameter constraints allow the estimation contribution to be absorbed into the same rate after substituting the chosen δ.Source: §D.2 · pp. 38–39

D.3 Proofs of the CART-MID intermediate results

  • At every nonterminal ancestor, the selected split captures at least a constant fraction of the population’s maximal impurity decrease, making the entire path competitive.The proof derives Δ(A, ĵ, b̂) ≥ C_rel Δ_max(A) with C_rel ∈ [1/2, 1).Source: §D.3 · p. 40
  • The intermediate proofs convert terminal stopping and competitive paths into uniform volume and approximation bounds, including the no-split root case.The terminal-cell volume lower bound supplies the mass condition, after which bounded density and the bias-visibility assumption yield the desired bound uniformly over [0, 1]^d.Source: §D.3 · pp. 41–43
  • The estimation proof combines path sparsity, sufficient impurity decrease, bounded density, and the terminal-volume lower bound to control leaf-average fluctuations uniformly.The argument applies the high-probability concentration events jointly and absorbs logarithmic constants into the final constant.Source: §D.3 · p. 44

E Proofs for the sufficient conditions … F.3 Gaussian endpoint-walk lemmas

This section develops the geometric, stochastic, and impurity-decrease ingredients underlying the CART-MLS lower bound, including density comparisons, local norm equivalence, LRP witnesses, endpoint-cell control, and Gaussian endpoint-walk bounds. It also derives consequences for bias visibility and competitive split regularity in honest and ordinary trees.

E.1 Auxiliary density-comparison lemmas

  • Under uniformly bounded covariate density, conditional moments and coordinate-wise densities on rectangular cells are comparable to their uniform-measure counterparts.The density bounds yield conditional density ratios controlled by c1 and c2, supporting expectation and variance comparisons.Source: §E.1 · pp. 44–45

E.2 Closure under independent blocks

  • For independent coordinate blocks, cellwise sufficient impurity decrease extends to the full product cell and yields local norm equivalence between variance and function oscillation.The proof uses block independence, blockwise local norm equivalence, Cauchy–Schwarz, and conditional-mean bounds.Source: §E.2 · pp. 46–47

E.3 LRP witness lemmas

  • A cellwise LRP witness with positive variance and uniformly strong correlation with the target implies sufficient impurity decrease, whereas arbitrary oscillatory witnesses may evade threshold splits.The LRP condition ensures a threshold split captures the witness’s variation; the accompanying discussion relates this to conditional Pearson correlation and Klusowski (2020).Source: §E.3 · pp. 47–48

E.4 LRP-based multivariate models

  • For LRP-based multivariate models, bounded density and independent coordinates let component functions supply cellwise witnesses, proving sufficient impurity decrease and local norm equivalence.The resulting constants depend only on density bounds, dimension, block structure, LRP parameters, and the component regularity bounds.Source: §E.4 · pp. 49, 50, 52

E.5 Bias visibility from local norm equivalence

  • Local norm equivalence makes zero conditional variance imply zero oscillation and zero bias, while positive variance yields the bias-visibility condition used later.The proof separates the zero-variance case from the positive-variance case and verifies Assumption 4.2.Source: §E.5 · p. 52

E.6 Pathwise competitive split-scale regularity

  • Along paths with competitive nonterminal splits, bounded density, local Hölder regularity, and sufficient impurity decrease control terminal-parent contrasts through the last split scale of each coordinate.The proof establishes a uniformly positive conditional-density denominator and bounds the relevant conditional mean by the oscillation of a coordinate-wise conditional mean.Source: §E.6 · pp. 52–54

F Proofs for the CART-MLS lower bound

  • The CART-MLS lower-bound proof shares endpoint-leaf geometry between honest and ordinary trees but uses different stochastic arguments because ordinary leaves depend on observed noise.For honest trees, endpoint leaves are fixed before noises are observed; for ordinary trees, a persistence event must hold over every admissible endpoint leaf size.Source: F Proofs for the CART-MLS lower bound · p. 56

F.1 LRP property of the square-root example

  • The square-root function g(x) = √x satisfies the locally reverse Poincaré condition with constant R = 18, linking the example to the LRP class.Together with Proposition 5.8(i), this shows the lower bound reflects minimum-leaf-size non-adaptivity rather than insufficient impurity decrease.Source: §F.1 · p. 56

F.2 Endpoint geometry and design

  • Endpoint geometry and design lemmas establish high-probability size, bias, and occupancy controls for endpoint leaves under bounded density and f∗(x) = √x.For N ≥ C log n, the assertions hold simultaneously with probability 1 − O(n^-2); for N < C log n, endpoint leaves selected from one sample contain between 1 and C log n observations from an independent sample with universal positive probability.Source: §F.2 · pp. 57–58

F.3 Gaussian endpoint-walk lemmas

  • Endpoint-walk lemmas control Gaussian partial sums by proving mixed-sign persistence for the left and right walks and small-window anti-concentration for windows M ≤ C0 log n.The persistence argument uses independent endpoint walks when 4N ≤ n, while the anti-concentration failure probability is bounded by C C0 log log n.Source: §F.3 · pp. 58–59

F.4 Proof of Theorem 6.1 · G Proofs for noise-driven splits · G.1 Calculation for Example 7.1

The appendices prove Theorem 6.1 by controlling signal biases against noise in CART endpoint leaves, explain the bridge-based stochastic argument for noise-driven splits, and calculate the population-optimal split for a hinge example.

F.4 Proof of Theorem 6.1

  • F.4 Proof of Theorem 6.1: For intermediate leaf sizes, endpoint leaves are disjoint and have averaging counts of order N, enabling constant-probability Gaussian sign events that reinforce deterministic biases.The honest argument conditions on both designs, while the ordinary argument handles response-dependent endpoint counts between N and 2N.Source: §F.4 · pp. 59–60
  • F.4 Proof of Theorem 6.1: For N > n/4, maximal inequalities bound the endpoint noise walks, making the noise terms smaller than half the corresponding positive biases.The resulting noise averages are O(σ/√n), and the two bounds in (30) follow for either estimator.Source: §F.4 · p. 60
  • F.4 Proof of Theorem 6.1: The proof establishes the endpoint bounds by showing deterministic biases dominate Gaussian noise across large-, moderate-, and small-leaf regimes for both honest and ordinary CART-MLS.For large leaves, noise averages are O(σ/√n), while small-leaf arguments use occupancy and Gaussian sign events; the proof combines five cases.Source: §F.4 · p. 60
  • F.4 Proof of Theorem 6.1: For small N, occupancy events and Gaussian sign or maximal inequalities control honest and ordinary CART-MLS endpoint noise, while signal errors remain negligible.The proof concludes the ordinary bound in (31) by comparing the noise bound with signal errors of order log n/n.Source: §F.4 · p. 60

G Proofs for noise-driven splits

  • G Proofs for noise-driven splits: The stochastic analysis uses an ordered Gaussian noise walk, but CART’s criterion depends on its centered, variance-standardized bridge rather than directly on endpoint averages.This distinguishes the noise-driven split analysis from the endpoint-average argument used in Appendix F.Source: G Proofs for noise-driven splits · p. 60

G.1 Calculation for Example 7.1

  • G.1 Calculation for Example 7.1: For f(x) = (2x−1)+ on X∼Unif[0,1], population impurity optimization reduces to minimizing post-split residual variation over the two child cells.Splits are analyzed separately when they lie before the sloped region and when they lie inside it.Source: §G.1 · p. 61
  • G.1 Calculation for Example 7.1: 1/3 is the limiting optimal fraction of the sloped tail assigned to the left child as the tail length t decreases to zero.Writing b = 1/2 + s and u = s/t, the leading term is strictly minimized at u = 1/3, so s/t→1/3.Source: §G.1 · p. 61
  • G.1 Calculation for Example 7.1: The optimal split can have a vanishing child–parent length ratio even though the smaller child’s length is of order V(A_a)^(1/3).Thus the example exhibits a shrinking split ratio while retaining a smaller child whose scale is controlled by the parent impurity variation.Source: §G.1 · p. 61

G.2 Proof of Theorem 7.2 · H General local Hölder function class

Theorem 7.2 is proved by showing that, under weak-signal conditions, stochastic fluctuations dominate the signal bridge and force CART’s greedy split toward near-boundary indices with nonvanishing probability. The local anisotropic Hölder class is shown to admit unit locality radii under regularity assumptions, reducing the analysis to an unrestricted Hölder condition with an explicit dimension-free radius.

G.2 Proof of Theorem 7.2

  • Under the weak-signal certificate, the deterministic impurity-decrease component is uniformly dominated by extreme stochastic fluctuations, yielding a nonvanishing probability that CART’s greedy split lies near either cell boundary.The lower bound concerns the reliability of the greedy split itself, not the bias-variance performance of the resulting leaf average.Source: §G.2 · p. 62
  • A Gaussian boundary-maximizer lemma, strong approximation, and corrected Darling–Erdős limit establish the same separated near-boundary lower bound after the allowed perturbation.The conclusion is transferred back through the coupling, and the same conditioning argument applies to the right boundary range.Source: §G.2 · pp. 62–64
  • The proof represents the empirical CART split as the argmax of a standardized bridge decomposed into Gaussian noise and signal components, then transfers the noise-only boundary-maximizer result through a perturbation bound.Conditional on the design, the noise bridge depends on the design only through the in-cell sample size, while the signal bridge is uniformly negligible on a high-probability event.Source: §G.2 · pp. 63–64

H General local Hölder function class

  • If the coordinate-wise exponents are Hölder continuous and locality radii are uniformly bounded below by c, local anisotropic Hölder regularity implies an equivalent condition with locality radii γ_j≡1.The reduction uses coordinate-wise paths and a one-dimensional chaining argument.Source: H General local Hölder function class · p. 65
  • The one-dimensional chaining construction uses at most 2/c admissible steps, with exponent continuity controlling the comparison between local exponents along the chain.This is the only role of the exponent-continuity and lower-radius assumptions in the chaining proof.Source: H General local Hölder function class · pp. 65–66
  • The resulting unrestricted Hölder condition holds with radius L′ = (2/c)^(1+L_α)L, independent of dimension.The proof reduces multivariate increments to one-dimensional coordinate increments and sums them using the explicit constant.Source: H General local Hölder function class · pp. 65–66
  • The lemma also implies sup_x,x′ |f*(x)−f*(x′)| ≤ L′d, so boundedness follows automatically within this function class.The bound uses α_j(x_j)≤1 for every coordinate.Source: H General local Hölder function class · p. 67

Related papers

Loading 2608.15649v1…