假设你要整理一堆包裹，每次只挑眼下最省事的分法，速度很快，却可能越分越乱。决策树也有类似问题：它反复按特征切分数据，在各区域分别预测。完整搜索训练误差最低的树通常算不动，所以实际训练常用贪心算法——每一步只选当前最佳切分。这项研究追问：省下计算后，要多付出多少数据？
作者研究了含 d 个二元特征的稀疏回归。当真实函数不满足 Merged Staircase Property（MSP，一种类似经典 ANOVA“遗传限制”的结构条件）时，贪心训练要达到较低估计误差，需要 exp(Ω(d)) 个样本，也就是样本需求随维度至少呈指数级增长；满足 MSP 时，则只需 O(log d) 个样本。相比之下，采用经验风险最小化（ERM，即在候选模型中寻找训练误差最低者）的递归分区估计器，无论是否满足 MSP，都能用 O(log d) 个样本达到较低误差。
说白了，树模型的扩展性并非免费：贪心训练让计算变得可行，但面对某些函数结构，统计效率可能急剧下降。以上范围和结论来自论文作者的理论分析。