Statistical-computational trade-offs for recursive adaptive partitioning estimators
研究了基于递归自适应划分的模型（如决策树）在训练中的统计计算权衡，发现当真实函数不满足合并阶梯性质时，贪婪训练需要指数级样本才能达到低误差，而满足时仅需对数级样本。
Models based on recursive adaptive partitioning such as decision trees and their ensembles are popular for high-dimensional regression as they can potentially avoid the curse of dimensionality. Because empirical risk minimization (ERM) is computationally infeasible, these models are typically trained using greedy algorithms. Although effective in many cases, these algorithms have been empirically observed to get stuck at local optima. We explore this phenomenon in the context of learning sparse regression functions over d binary features, showing that when the true regression function f∗ does not satisfy Abbe et al. (In Conference on Learning Theory (2022) 4782–4887 PMLR)’s Merged Staircase Property (MSP), a form of heredity restriction similar to that used in classical ANOVA modeling, greedy training requires exp(Ω(d)) samples to achieve low estimation error. Conversely, when f∗ does satisfy MSP, greedy training can attain small estimation error with only O(logd) samples. This dichotomy mirrors that of two-layer neural networks trained with stochastic gradient descent (SGD) in the mean-field regime, thereby establishing a head-to-head comparison between SGD-trained neural networks and greedy recursive partitioning estimators. Furthermore, ERM-trained recursive partitioning estimators achieve low estimation error with O(logd) samples irrespective of whether f∗ satisfies MSP, thereby demonstrating a statistical-computational trade-off for greedy training. Our proofs are based on a novel interpretation of greedy recursive partitioning using stochastic process theory and a coupling technique that may be of independent interest.