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’s stopping rule determines its ability to adapt to spatially varying smoothness and anisotropy. It proves that CART with minimum impurity decrease achieves near-minimax pointwise adaptation, whereas minimum leaf size cannot.

  • Problem

    Existing theory leaves the statistical role of CART stopping rules unclear, including whether CART achieves spatially adaptive pointwise performance under heterogeneous and anisotropic smoothness.

  • Method

    The paper analyzes CART with minimum impurity decrease stopping under structural assumptions for anisotropic locally Hölder functions in one-dimensional and sparse high-dimensional settings.

  • Results

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

  • Takeaways & Limitations

    Minimum impurity decrease is a statistically consequential stopping rule because it can select locally appropriate averaging scales for spatial adaptation.

  • Takeaways & Limitations

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

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 paper studies whether CART can achieve locally adaptive pointwise rates and shows that early stopping is central to doing so. Under structural assumptions, CART with minimum impurity decrease stopping attains near-minimax adaptation, whereas minimum leaf size need not.

  • Motivation: Existing CART theory largely emphasizes global L2 risk and global smoothness, leaving pointwise behavior and spatial adaptation under stopping rules insufficiently understood.Pointwise risk matters for personalized and high-stakes decision-making, while prior work found CART can be pointwise inconsistent even for constant regression functions.
  • Role of stopping: CART stopping must prevent noise-driven splits while selecting terminal-cell neighborhoods that achieve the appropriate pointwise bias-variance tradeoff.The stopping rule determines the local averaging bandwidth around each query point.
  • Main results: MID succeeds because it regularizes CART on the same empirical scale used for splitting, preserving split reliability while selecting the bandwidth needed for local averaging.The empirical impurity-decrease threshold can stop the tree before split selection becomes noise-dominated, although reliability and bandwidth scales need not automatically coincide.
  • Main results: CART-MID achieves pointwise rates for anisotropic locally Hölder functions in one-dimensional and sparse high-dimensional settings that are minimax optimal up to logarithmic factors.The rates hold simultaneously over all domain points on one high-probability event and do not require local-smoothness knowledge.

2 Setup and preliminaries

This section formulates CART as an adaptive local averaging estimator under a regression model, defines its cell and split machinery, and introduces the MID and MLS stopping rules. It also states the structural and concentration tools used to analyze pointwise behavior.

  • Statistical setup: The setup assumes independent observations from (X, Y) ∈ [0, 1]^d × R, with conditionally mean-zero noise and covariate density bounded between p_min and p_max.The noise may be heteroskedastic unless stated otherwise.
  • Split criteria: Impurity decrease is defined empirically as a weighted reduction in response variance and at the population level as a weighted reduction in conditional variance.The empirical and population quantities correspond to reductions in training error and expected test error, respectively.
  • CART construction: CART recursively maximizes empirical impurity decrease to partition [0, 1]^d, then predicts by averaging responses in the terminal cell containing x.The terminal cell serves as a data-adaptive local bandwidth for pointwise estimation.
  • Stopping rules: The analysis compares MID stopping, which terminates cells below an impurity-decrease threshold, with MLS stopping, which requires at least N observations in each child.These rules define CART-MID(δ) and CART-MLS(N), respectively.
  • Structural assumptions and concentration: SID requires every cell to admit an axis-aligned split removing a non-negligible fraction of its variation, excluding adversarial cases such as pure interactions.The analysis also uses concentration inequalities for empirical impurity decreases and leaf averages.

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

This section explains why CART-MID can achieve pointwise spatial adaptation in one dimension despite selecting bandwidths indirectly through greedy splits and stopping. The argument links MID to local residual variation, yielding the correct bandwidth scale uniformly over the domain up to logarithmic factors.

  • Motivation: CART must recover a query-point bandwidth indirectly because greedy empirical splits and the stopping rule determine the terminal interval.The interval length acts as the local bandwidth for leaf averaging, but CART does not choose it directly.
  • Adaptation mechanism: Setting the MID threshold near the noise floor lets SID connect empirical impurity decrease to residual variation and recover the correct bandwidth scale at every query point up to log factors.The residual-variation scale is in one-to-one correspondence with the optimal local bandwidth, while the relevant threshold value is independent of x.
  • Main theorem: Under bounded density, sub-Gaussian responses, local Hölder smoothness, and sufficient impurity decrease, Theorem 3.1 establishes a one-dimensional pointwise upper bound for CART-MID.The theorem uses a sufficiently large universal constant in the threshold and assumes the threshold satisfies δ≤1.
  • Proof strategy: The proof controls terminal-cell length, leaf-average error, residual variation, and bias through competitive split-scale regularity and bias visibility.These lemmas translate parent split signals and terminal stopping signals into local geometric and bias bounds.
  • Uniform guarantee: The resulting conclusion holds simultaneously for every x∈[0, 1] with probability at least 1−e^−u.Uniform concentration over intervals and splits supports the simultaneous pointwise conclusion.
  • Proof strategy: The proof does not require balanced splits: when a split is competitive, only a local lower bound on the query-containing child’s size is used.Lemma 3.2 supplies the needed regularity relative to the parent residual variation.

4 Pointwise spatial adaptation for CART-MID

CART-MID achieves pointwise spatial adaptation in sparse, anisotropic settings under local geometric and sparsity conditions. Its rate is minimax-optimal up to logarithmic factors and adapts to unknown local smoothness and relevant coordinates.

  • Spatial adaptation: The adaptation is achieved without knowing the local harmonic smoothness or relevant coordinate set, while ambient dimension enters only through the split-search logarithm.The harmonic mean of relevant-coordinate smoothness determines the local rate.
  • Assumptions: CART-MID’s multidimensional upper bound requires pathwise competitive split-scale regularity, bias visibility on large cells, and sparsity separation.These assumptions extend the one-dimensional argument and ensure adaptive local refinement and selection of relevant coordinates.
  • Theorem 4.4: With the stated model, density, response-tail, smoothness, impurity, geometric, visibility, and sparsity assumptions, the theorem gives a uniform pointwise bound over all x ∈ [0, 1]^d.The result applies to locally anisotropic Hölder regression functions with a nonempty sparse support set.
  • Minimax optimality: Up to logarithmic factors, CART-MID attains the pointwise minimax rate for an s-dimensional anisotropic Hölder class with local harmonic smoothness.The rate balances local bias against leaf-average variance in relevant coordinates.
  • Comparison with previous work: Theorem 4.4 uses the usual pointwise smoothness exponent ᾱ_S(x)/(2ᾱ_S(x) + s), unlike earlier global L2(P) contraction analyses.Those earlier analyses balance geometrically decaying integrated squared bias against leaf-estimation error, whereas CART-MID uses local geometric conditions.
  • Threshold choice: Cross-validation can select the threshold δ over a finite candidate grid for an integrated L2(P) guarantee, but an analogous uniform pointwise guarantee is more difficult.A grid containing a threshold of the specified order preserves the integrated rate up to the usual validation remainder.

5 Sufficient conditions for the structural assumptions

This section gives interpretable sufficient conditions for the abstract structural assumptions underlying CART-MID’s pointwise-adaptation argument. It shows that local norm equivalence implies bias visibility and, with smoothness and sufficient impurity decrease, pathwise split-scale regularity, while locally reverse Poincaré models provide broad examples satisfying these conditions.

  • Local norm equivalence: Local norm equivalence compares conditional sup-norm variation with conditional L2(P) variation, making it a natural condition for bias visibility.Without it, spiky regression functions can have large leaf-averaging bias but little residual variation.
  • Local norm equivalence: Under bounded density, local norm equivalence implies bias visibility on large cells whenever ζ^2 ≥ ρχ^-1.The implication holds for any ζ ≥ 1 and χ ∈ (0, 1].
  • Pathwise regularity: Under local anisotropic Hölder smoothness, sufficient impurity decrease and local norm equivalence imply pathwise competitive split-scale regularity.The resulting regularity holds on A_S with a positive constant depending on p_min, p_max, ρ, α_min, and ||f*||∞.
  • Constructing examples: Locally reverse Poincaré components yield multivariate examples satisfying sufficient impurity decrease and local norm equivalence in additive and sums-of-products models.For sums of products, the components satisfy locally reverse Poincaré and take values in [h_min, h_max], with independent covariates.
  • Constructing examples: The sufficient impurity decrease and local norm equivalence conditions are preserved when component functions are combined across mutually independent coordinate blocks.The result applies to a decomposition over a disjoint partition of the coordinate set.

6 Pointwise lower bound for CART-MLS

This section proves that CART with a global minimum leaf size cannot achieve simultaneous pointwise adaptation, because optimal local bandwidths differ across endpoint smoothness levels. The resulting lower bound contrasts with CART-MID’s adaptation and establishes a rigorous performance gap.

  • Lower bound: For f*(x) = x^1/2 in one dimension, Theorem 6.1 gives pointwise lower bounds for both ordinary and honest CART-MLS estimators.The result applies under bounded covariate density and Gaussian noise, for sufficiently large n and fixed minimum leaf size N.
  • Bandwidth-selection obstruction: The rough endpoint x = 0 is optimized at γ = 1/2, whereas the smoother endpoint x = 1 is optimized at γ = 2/3.Here N_n = ⌊n^γ⌋ for fixed γ ∈ (0, 1].
  • Bandwidth-selection obstruction: Because no single γ optimizes both endpoints, one global minimum leaf size cannot simultaneously achieve optimal pointwise rates.This is the bandwidth-selection failure identified for CART-MLS.
  • Bandwidth-selection obstruction: The obstruction persists even when all relevant splits are reliable, since it arises from using one global leaf-size parameter to choose local bandwidths.The argument relies on endpoint geometry, terminal cell sizes, and the bias and noise of averaging over those cells.
  • Performance gap: Contrasting Theorems 6.1 and 3.1 establishes a rigorous performance gap between CART-MLS and CART-MID.The example satisfies the required structural conditions through LRP, SID under bounded density, and the stated smoothness definition.

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 severely undersized leaves and undermine them. CART-MID attains optimal rates in a ReLU example, while weak split signals make preventing noise-driven splits necessary for optimality.

  • Noise-driven splits: Noise-driven splits can select irrelevant features in multidimensional settings, potentially causing poor generalization and motivating their prevention for optimal pointwise rates.The section asks whether preventing such splits is necessary for optimal pointwise rates or good prediction more generally.
  • End-cut preference: End-cut preference does not preclude optimal pointwise rates because Theorem 3.1 requires only competitive split-scale regularity, not balanced splits.The result permits substantially unbalanced recursive splits.
  • End-cut preference: In the shifted-ReLU example, the population split creates a child with a vanishing sample fraction but a length commensurate with the residual signal scale, and CART-MID still achieves the optimal pointwise rate at 0.The example uses X∼Unif[0, 1] and satisfies the SID condition.
  • Noise-driven splits: Under weak split signals, quantitative end-cut preference persists for nonconstant regression functions, strengthening the case that preventing noise-driven splits is necessary for optimal pointwise rates.Theorem 7.2 extends the noise-only phenomenon when local residual variation is beneath the noise level.
  • Noise-driven splits: For MID thresholds of o((n log log n)^-1), CART has nonvanishing probability of producing a leaf with only n^b samples, inflating its leaf-average variance to n^-b/2.For sufficiently small b, this variance can be worse than the minimax rate, although a rigorous pointwise lower bound requires an additional theoretical bridge.

8 Experiments

The experiments show that CART-MID adapts its local resolution across spatially varying smoothness and across anisotropic coordinates. CART-MLS instead enforces globally comparable cell sizes, creating incompatible tuning requirements across regions.

  • One-dimensional adaptation: CART-MID creates smaller cells in the rough Brownian region and stops earlier in the smooth linear region using one global threshold.The signal is almost surely Hölder for every α<1/2 on the Brownian segment and Lipschitz on the linear segment.
  • One-dimensional adaptation: CART-MID’s mean squared error is minimized near 1.6 × 10−3 at x=0.25 and 1.07 × 10−3 at x=0.75, with a stable common range near 1.07 × 10−3.This indicates that a single impurity-decrease threshold can provide a favorable bias–variance trade-off in both regions.
  • One-dimensional adaptation: CART-MLS requires minimum leaf sizes of about 45 at x=0.25 and 105–135 at x=0.75, so one global value cannot select both local scales.Smaller leaves control rough-region bias, whereas larger leaves reduce smooth-region variance.
  • Terminal-cell geometry: Under the same threshold, CART-MID produces much smaller terminal cells at x=0.25 than x=0.75, while CART-MLS produces nearly equal cell lengths.With uniform design, a common leaf-size constraint enforces comparable cell lengths regardless of local smoothness.
  • Anisotropic adaptation: The fitted terminal-cell slopes are −0.320 for coordinate 1 and −0.529 for coordinate 2, with faster shrinkage along the less smooth second coordinate.At the origin, the local Hölder exponents are α1=1/2 and α2=1/4; the theoretical benchmark slopes are −1/4 and −1/2, respectively.

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

The paper establishes that CART achieves spatial adaptation through the MID stopping rule, while outlining limitations for pruning and random forests and developing uniform concentration tools for cells indexed by active coordinates.

  • 9 Discussion: CART achieves spatial adaptation, and the MID stopping rule is crucial for enabling it.This answers affirmatively whether CART can match spatial adaptation known for ERM and Bayesian trees.
  • 9 Discussion: Cost-complexity pruning may certify small terminal-cell variation without certifying sufficient parent impurity decrease.Strong descendant splits can subsidize a weak parent split under pruning’s aggregate-gain condition.
  • 9 Discussion: Feature subsampling in random forests can prevent spatial adaptation because a relevant coordinate may be unavailable.A small best split among sampled coordinates need not imply small residual variation.
  • 9 Discussion: LNE is identified as an extremely strong sufficient condition that may be weakened in future work.The discussion asks whether other sufficient conditions can guarantee spatial adaptation for CART.
  • A Algorithmic details: Early-stopped CART initializes the root cell and repeatedly splits an active leaf when its maximum admissible impurity decrease satisfies bΔmax(A) ≥ δ.The algorithm uses threshold δ > 0 and replaces each split leaf with its left and right children.
  • B.1 Proofs for uniform concentration with empirical Rademacher complexity: Uniform concentration is developed by localizing indicator classes V_r,a and controlling their empirical Rademacher complexity through the number of active coordinates r.The resulting argument yields self-normalized deviation bounds uniformly over V_r.
  • B.1 Proofs for uniform concentration with empirical Rademacher complexity: With probability at least 1 − e^−u, concentration bounds hold simultaneously over r ∈ [d] and cells, using ε_n,r,u = (rlog(nd) + u)/n.The proofs combine sub-Gaussian response control, cell-count concentration, bounded cell averages, localization, peeling, and a union bound.
  • B.1 Proofs for uniform concentration with empirical Rademacher complexity: Cell-count concentration distinguishes large and small cells using the threshold (rlog(nd) + u)/n, while bounded cell averages follow by combining cell-count and response-multiplier bounds.These results support the concentration statement proved for the CART analysis.

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 CART’s empirical impurity decreases across all cells, depths, coordinates, and split points. These bounds yield the key population-to-empirical comparison underlying the stopping analysis.

  • B.2 Proof of Lemma 2.5: Lemma B.7 provides a high-probability bound uniformly over every depth r and cell B.The bound holds with probability at least 1 − e^-u under sub-Gaussian responses.
  • B.2 Proof of Lemma 2.5: Empirical and population cell masses are compared separately in regimes above and below the concentration scale.When p_B is large, concentration gives comparability; when p_B is small, boundedness controls the claim.
  • B.2 Proof of Lemma 2.5: Conditional on covariates, the noise terms are independent, centered, and conditionally sub-Gaussian with norms bounded by C K.This conditional structure enables uniform control over sample traces.
  • B.2 Proof of Lemma 2.5: A sample-trace counting argument and a union bound control noise uniformly over cells and depths with failure probability at most e^-u1.For each r, at most exp{3r log(n d)} distinct traces occur; summing over r preserves the stated failure bound.
  • B.2 Proof of Lemma 2.5: Lemma 2.5 applies the uniform cell-mean event to compare a parent’s population impurity decrease with its empirical counterpart.The argument handles parent and child cells, including zero-mass cases, through the stated conventions and variance-decomposition identities.
  • B.2 Proof of Lemma 2.5: The resulting event and bounds are uniform over depth r, cell A, coordinate j, and split point b.This completes the proof of Lemma 2.5 and supplies the uniformity needed for subsequent stopping-rule arguments.
  • B.2 Proof of Lemma 2.5: A sufficiently large C makes the population impurity decrease exceed a prescribed multiple of (r log(n d) + u)/n.This yields P(A_L) ≥ c(r log(n d) + u)/n, with the same conclusion for A_R because P(A_R) ≥ P(A_L).

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

The technical lemmas establish local lower bounds on the regression signal and variance, then use impurity decrease and competitiveness to control the child interval containing a target point. These ingredients yield the variance-order bound required for the CART-MID upper-bound proof.

  • C.1 Technical lemmas for Theorem 3.1: For a fixed x, local Hölder smoothness gives |g(t)| ≥ U_0/2 within radius r = (U_0/(2L))^(1/α_0).The argument defines A_1 := A ∩ (x − r, x + r) and obtains the local signal lower bound there.
  • C.1 Technical lemmas for Theorem 3.1: The proof lower-bounds Vol(A_1) and the resulting variance by analyzing the relative size of the signal neighborhood and parent interval.Writing A = [a,b] and assuming x is no farther from a than from b supports the volume calculation.
  • C.1 Technical lemmas for Theorem 3.1: Both cases in the radius-versus-volume analysis produce the same claimed variance order, completing equation (16).The proof explicitly states that the alternative case yields the same order and identifies the result with (16).
  • C.1 Technical lemmas for Theorem 3.1: For a competitive split, the proof tracks the smaller and larger children, the child containing x, and exponents θ_0 = α_0/(1 + 2α_0) and r_0 = 1/(1 + 2α_0).The split notation sets Δ as the impurity decrease and uses λ ≤ 1 because Δ_max(A′) ≤ V(A′).
  • C.1 Technical lemmas for Theorem 3.1: When the target lies in the smaller child and its probability share is at least 1/3, density regularity converts probability mass into a volume lower bound.The bound uses the ratio p = P(A_sm)/P(A′) and compares Vol(A_sm) with Vol(A′).
  • C.1 Technical lemmas for Theorem 3.1: When p < 1/3, the impurity and tower identities reduce the child-control argument to the technical variance lemma.Lemma 3.3 is applied to A′ and A_sm, together with V(A_sm) ≤ V(A′).
  • D Proof of the CART-MID upper bound: The resulting conditional-bias expression is bounded by L^2 r_0 V(A′)^(2θ_0), and hence by L^2 r_0.This is the displayed bound obtained after combining the lemma with the variance comparison.

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

The appendices establish high-probability path regularity for CART-MID, then combine terminal-cell approximation and estimation bounds to prove the upper bound uniformly over the domain. The proofs show how concentration, sparsity preservation, competitive splits, and the MID stopping rule yield the required terminal-cell geometry.

  • D.1 Intermediate results for CART-MID: With probability at least 1 −e^−u, CART-MID paths satisfy sparsity preservation, competitive splitting, and path competitiveness simultaneously for all x ∈[0, 1]^d.The threshold δ is chosen above the impurity concentration scale under Theorem 4.4’s conditions.
  • D.1 Intermediate results for CART-MID: Concentration preserves the relevant-versus-irrelevant population-gain separation, allowing empirical split maximizers to retain the sparse structure in high dimensions.The argument uses sparsity separation and concentration to keep empirical error below the separation gap.
  • D.1 Intermediate results for CART-MID: The MID stopping rule and competitive path conditions imply a terminal-volume lower bound that supplies the bandwidth needed for the pointwise bias bound.The proof converts terminal stopping, sufficient impurity decrease, and bounded density into the mass condition required for bias visibility.
  • D.1 Intermediate results for CART-MID: Propositions D.2 and D.3 separately establish high-probability approximation and estimation error bounds for CART-MID under Theorem 4.4’s conditions.The approximation result concerns f_δ, while the estimation result concerns the empirical estimator f̂_δ relative to f_δ.
  • 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 applying the error decomposition.The estimation term is bounded by the same rate as the approximation term after substituting the chosen δ.
  • D.3 Proofs of the CART-MID intermediate results: Uniform concentration over coordinates and thresholds transfers population split regularity to empirical maximizers, yielding the competitive split guarantee Δ(𝐴, ˆ𝑗, ˆ𝑏) ≥ C_relΔ_max(𝐴).The proof sets C_rel = q^2 ∈[1/2, 1) and uses root concentration at both the selected split and a population maximizer.
  • D.3 Proofs of the CART-MID intermediate results: The terminal-volume argument yields a uniform approximation bound over [0, 1]^d after combining the stopping inequality, sufficient impurity decrease, bounded density, and bias visibility.The proof handles both split and root terminal cells and concludes that the bound holds uniformly because x was arbitrary.
  • D.3 Proofs of the CART-MID intermediate results: For estimation, the proof combines the regularity event with high-probability leaf-mass control and concentration, then simplifies the smoothness exponent using 0 < ω ≤ 1.The resulting constant absorbs the additive log 3 and replaces ω^−s/(s+2) by the weaker factor ω^−1.

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

The appendix establishes the sufficient conditions behind CART’s impurity-decrease guarantees, then proves the endpoint geometry and Gaussian-walk ingredients used for the CART-MLS lower bound. Its arguments rely on bounded-density comparisons, independent-block structure, LRP witnesses, local norm equivalence, and persistence properties of endpoint leaves.

  • E.1 Auxiliary density-comparison lemmas: Bounded joint-density assumptions yield uniform comparisons between conditional coordinate densities and between moments under the design law and uniform measure.These comparisons are derived using density bounds and variance’s variational characterization.
  • E.2 Closure under independent blocks: Independent coordinate blocks preserve sufficient impurity decrease and imply local norm equivalence, with constants depending only on the stated structural parameters.The proof combines blockwise independence, local norm-equivalence assumptions, Cauchy–Schwarz, and oscillation bounds.
  • E.3 LRP witness lemmas: A cellwise LRP witness with positive variance and uniformly strong covariance implies sufficient impurity decrease, whereas arbitrary oscillatory univariate correlation may not be captured by one threshold split.The LRP condition supplies a univariate direction whose variation can be converted into a threshold-split signal.
  • E.4 LRP-based multivariate models: For LRP-based multivariate models, density comparisons and block independence establish sufficient impurity decrease and local norm equivalence for the full regression function.The argument reduces componentwise variation and covariance to the witness lemma, then controls function differences by coordinatewise contributions.
  • E.5 Bias visibility from local norm equivalence: Local norm equivalence makes nonzero cell variance visible as nonzero oscillation and supports the bias-visibility assumption used in the main results.When conditional variance vanishes, local norm equivalence forces zero oscillation and zero bias.
  • E.6 Pathwise competitive split-scale regularity: Along paths with competitive nonterminal splits, bounded density, sufficient impurity decrease, and local Hölder regularity control terminal-parent contrasts through prior split signals and coordinate scales.The proof also establishes uniformly bounded conditional-mean denominators and bounds the relevant conditional mean’s oscillation.
  • F Proofs for the CART-MLS lower bound; F.1 LRP property of the square-root example: The CART-MLS lower-bound proof separates common endpoint geometry from estimator-specific stochastic arguments: honest leaves are fixed before noise observation, while ordinary leaves require persistence over admissible sizes.The square-root example satisfies LRP with constant R=18, so the lower bound reflects minimum-leaf-size non-adaptivity rather than failure of sufficient impurity decrease.

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

The proofs establish endpoint bounds for CART-MLS across leaf-size regimes by showing that deterministic endpoint biases dominate noise, while the noise-driven analysis uses a standardized Gaussian bridge and identifies the population-optimal split scaling in Example 7.1.

  • F.4 Proof of Theorem 6.1: For honest CART-MLS with C log n ≤ N ≤ n/4, endpoint leaves are disjoint and have second-sample counts m_z ≍ N.The proof conditions on both designs and works on the occupancy event, where the tree has at least one split.
  • F.4 Proof of Theorem 6.1: For ordinary CART-MLS with C log n ≤ N ≤ n/4, endpoint leaves contain order-statistic observations with N ≤ m_z < 2N despite response-dependent selection.A mixed-sign persistence event makes the noise signs reinforce the deterministic endpoint biases.
  • F.4 Proof of Theorem 6.1: When N > n/4, maximal Gaussian-walk control bounds endpoint noise averages by O(σ/√n), allowing deterministic biases to dominate.The proof applies Doob’s maximal inequality for ordinary CART and conditional Gaussian tails for honest CART.
  • F.4 Proof of Theorem 6.1: For small N, honest CART-MLS uses endpoint leaves with averaging counts 1 ≤ m_z ≤ C log n, while ordinary CART controls selected noise averages through a logarithmic-size intersection event.In both cases, noise signs reinforce endpoint signal errors, yielding the corresponding bound in (31).
  • G Proofs for noise-driven splits: The noise-driven-split analysis uses the centered and variance-standardized Gaussian bridge underlying the CART criterion, rather than endpoint averages directly.This extends the ordered Gaussian noise-walk framework used in the preceding appendix.
  • G.1 Calculation for Example 7.1: For X ∼ Unif[0, 1] and f(x) = (2x−1)+, population impurity optimization reduces to minimizing post-split residual variation over the two child intervals.The calculation considers cells A_a = [0, a] with a > 1/2 and t = a − 1/2.
  • G.1 Calculation for Example 7.1: The leading term is strictly minimized at u = 1/3, so any population-optimal split satisfies s/t → 1/3 as t ↓ 0.Here splits inside the sloped portion are parameterized by b = 1/2 + s with 0 ≤ s ≤ t.
  • G.1 Calculation for Example 7.1: The resulting split can have a vanishing child–parent length ratio even though the smaller child has length of order V(A_a)^(1/3).Thus the example exhibits highly unbalanced population-optimal splits near the kink.

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

The proof shows that under weak-signal control, CART’s greedy split can be driven by a Gaussian noise bridge and attain a nonvanishing probability of selecting near-boundary splits. The general local anisotropic Hölder class reduces to the unrestricted unit-locality form with a dimension-free radius constant.

  • G.2 Proof of Theorem 7.2: Under weak-signal control, empirical impurity decrease decomposes into deterministic and stochastic terms, with the deterministic signal contribution negligible at the relevant scale.The argument uses local reverse Poincaré control and small conditional signal variance.
  • G.2 Proof of Theorem 7.2: With probability bounded away from zero, the maximizing split lies in either of two near-endpoint index ranges.This follows from order-statistic and extreme-value arguments for the noise process, transferred to the full bridge through a perturbation bound.
  • G.2 Proof of Theorem 7.2: Theorem 7.2 therefore establishes a nonvanishing lower bound for the reliability of the greedy split itself, not for the bias-variance performance of the final leaf average.The perturbation transfer preserves the noise-only lower bound under the high-probability design event.
  • G.2 Proof of Theorem 7.2: The CART split index maximizes the absolute standardized bridge, which decomposes additively into Gaussian noise and signal bridges.Conditional on the design, the noise component is a standardized Gaussian bridge indexed by the in-cell order statistics.
  • H General local Hölder function class: If the local exponents are Hölder continuous and locality radii are uniformly bounded below by c, local anisotropic Hölder regularity extends to unit locality.The resulting function has the same exponents, radius L′, and locality radii γ_j ≡ 1.
  • H General local Hölder function class: The extension is proved by reducing the multivariate bound to one-dimensional coordinate paths and applying a chaining argument.Assumption (i) controls exponent comparisons, while assumption (ii) bounds the number of chain steps by 2/c.
  • H General local Hölder function class: The resulting dimension-free Hölder radius is L′ = (2/𝑐)1+𝐿𝛼𝐿.The constant applies after summing the coordinatewise one-dimensional bounds.
  • H General local Hölder function class: The lemma also implies supx,x′ | 𝑓∗(x)−𝑓∗(x′)| ≤𝐿′𝑑, so boundedness follows automatically from the stated regularity conditions.This conclusion uses that each exponent satisfies 𝛼_j(x_j) ≤ 1.
Loading 2608.15649v1…