CART算法的停止规则影响其自适应能力，本文证明MID规则可实现最优局部拟合。
On Stopping Rules and Spatial Adaptation for CART
- 采用最小不纯度减少（MID）停止规则，结合合适阈值
- 在异质光滑性和各向异性条件下，点态收敛率达到极小极大最优（对数因子内）
- 揭示了MID规则的理论优势，适合研究树模型统计性质的研究者
CART回归树算法通过贪心分裂与停止规则结合，虽分裂规则研究充分，但停止规则的统计作用仍不清晰。现有方法（如贝叶斯或经验风险最小化）已被证明能自适应局部光滑性与各向异性，但尚不清楚CART是否具备类似能力。本文在回归函数和协变量分布满足适当结构假设下，证明：使用最小不纯度减少（MID）停止规则并设置合适阈值时，CART可在全定义域上实现点态收敛率，达到极小极大最优（对数因子内）。而广泛使用的最小叶节点大小停止规则则无法实现空间自适应。该结果明确了MID规则的统计角色，为CART的实证成功提供了理论依据。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。