{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T21:52:32Z","timestamp":1791323552698,"version":"4.3.1"},"reference-count":59,"publisher":"Institute of Mathematical Statistics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2026,6,1]]},"abstract":"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\u2217 does not satisfy Abbe et al. (In Conference on Learning Theory (2022) 4782\u20134887 PMLR)\u2019s Merged Staircase Property (MSP), a form of heredity restriction similar to that used in classical ANOVA modeling, greedy training requires exp(\u03a9(d)) samples to achieve low estimation error. Conversely, when f\u2217 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\u2217 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.<\/jats:p>","DOI":"10.1214\/25-aos2603","type":"journal-article","created":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T13:49:38Z","timestamp":1782395378000},"page":"1262-1288","source":"Crossref","is-referenced-by-count":0,"title":["Statistical-computational trade-offs for recursive adaptive partitioning estimators"],"prefix":"10.1214","volume":"54","author":[{"given":"Yan Shuo","family":"Tan","sequence":"first","affiliation":[{"name":"Department of Statistics and Data Science, National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jason M.","family":"Klusowski","sequence":"additional","affiliation":[{"name":"Department of Operations Research and Financial Engineering, Princeton University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Krishnakumar","family":"Balasubramanian","sequence":"additional","affiliation":[{"name":"Department of Statistics, University of California, Davis"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"53","doi-asserted-by":"publisher","unstructured":"Wahba, G.<\/small> (1990). Spline Models for Observational Data<\/i>. CBMS-NSF Regional Conference Series in Applied Mathematics<\/i> 59<\/b>. SIAM, Philadelphia, PA.","DOI":"10.1137\/1.9781611970128"},{"key":"13","unstructured":"Breiman, L.<\/small>, Friedman, J. H.<\/small>, Olshen, R. A.<\/small> and Stone, C. J.<\/small> (1984). Classification and Regression Trees<\/i>. Wadsworth Statistics\/Probability Series<\/i>. Wadsworth Advanced Books and Software, Belmont, CA."},{"key":"12","doi-asserted-by":"crossref","unstructured":"Breiman, L.<\/small> (2001). Random forests. Mach. Learn.<\/i> 45<\/b> 5\u201332.","DOI":"10.1023\/A:1010933404324"},{"key":"9","doi-asserted-by":"publisher","unstructured":"ATHEY, S.<\/small> and IMBENS, G.<\/small> (2016). Recursive partitioning for heterogeneous causal effects. Proc. Natl. Acad. Sci. USA<\/i> 113<\/b> 7353\u20137360.","DOI":"10.1073\/pnas.1510489113"},{"key":"28","doi-asserted-by":"publisher","unstructured":"ISHWARAN, H.<\/small>, KOGALUR, U. B.<\/small>, BLACKSTONE, E. H.<\/small> and LAUER, M. S.<\/small> (2008). Random survival forests. Ann. Appl. Stat.<\/i> 2<\/b> 841\u2013860.","DOI":"10.1214\/08-AOAS169"},{"key":"45","unstructured":"SYRGKANIS, V.<\/small> and ZAMPETAKIS, M.<\/small> (2020). Estimation and inference with trees and forests in high dimensions. In Conference on Learning Theory<\/i> 3453\u20133454. PMLR."},{"key":"51","doi-asserted-by":"publisher","unstructured":"UHLER, C.<\/small>, RASKUTTI, G.<\/small>, B\u00dcHLMANN, P.<\/small> and YU, B.<\/small> (2013). Geometry of the faithfulness assumption in causal inference. Ann. Statist.<\/i> 41<\/b> 436\u2013463.","DOI":"10.1214\/12-AOS1080"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Wainwright, M. J.<\/small> (2019). High-Dimensional Statistics<\/i>: A Non-Asymptotic Viewpoint<\/i>. Cambridge Series in Statistical and Probabilistic Mathematics<\/i> 48<\/b>. Cambridge Univ. Press, Cambridge.","DOI":"10.1017\/9781108627771"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Bertsimas, D.<\/small> and Dunn, J.<\/small> (2017). Optimal classification trees. Mach. Learn.<\/i> 106<\/b> 1039\u20131082.","DOI":"10.1007\/s10994-017-5633-9"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Hastie, T.<\/small>, Tibshirani, R.<\/small> and Friedman, J.<\/small> (2001). The Elements of Statistical Learning<\/i>: Data Mining, Inference, and Prediction<\/i>. Springer Series in Statistics<\/i>. Springer, New York.","DOI":"10.1007\/978-0-387-21606-5"},{"key":"42","unstructured":"Pedregosa, F.<\/small>, Varoquaux, G.<\/small>, Gramfort, A.<\/small> et al. (2011). Scikit-learn: Machine learning in Python. J. Mach. Learn. Res.<\/i> 12<\/b> 2825\u20132830."},{"key":"19","doi-asserted-by":"publisher","unstructured":"CHIPMAN, H. A.<\/small>, GEORGE, E. I.<\/small> and MCCULLOCH, R. E.<\/small> (1998). Bayesian CART model search. J. Amer. Statist. Assoc.<\/i> 93<\/b> 935\u2013948.","DOI":"10.1080\/01621459.1998.10473750"},{"key":"57","unstructured":"WU, C. F. J.<\/small> and HAMADA, M. S.<\/small> (2009). Experiments<\/i>: Planning, Analysis, and Optimization<\/i>, 2nd ed. Wiley Series in Probability and Statistics<\/i>. Wiley, Hoboken, NJ."},{"key":"40","doi-asserted-by":"publisher","unstructured":"MURDOCH, W. J.<\/small>, SINGH, C.<\/small>, KUMBIER, K.<\/small>, ABBASI-ASL, R.<\/small> and YU, B.<\/small> (2019). Definitions, methods, and applications in interpretable machine learning. Proc. Natl. Acad. Sci. USA<\/i> 116<\/b> 22071\u201322080.","DOI":"10.1073\/pnas.1900654116"},{"key":"17","doi-asserted-by":"crossref","unstructured":"CHEN, T.<\/small> and GUESTRIN, C.<\/small> (2016). Xgboost: A scalable tree boosting system. In Proceedings of the<\/i> 22nd Acm Sigkdd International Conference on Knowledge Discovery and Data Mining<\/i> 785\u2013794.","DOI":"10.1145\/2939672.2939785"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Mei, S.<\/small>, Montanari, A.<\/small> and Nguyen, P.-M.<\/small> (2018). A mean field view of the landscape of two-layer neural networks. Proc. Natl. Acad. Sci. USA<\/i> 115<\/b> E7665\u2013E7671.","DOI":"10.1073\/pnas.1806579115"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Friedman, J. H.<\/small> (2001). Greedy function approximation: A gradient boosting machine. Ann. Statist.<\/i> 29<\/b> 1189\u20131232.","DOI":"10.1214\/aos\/1013203451"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Chipman, H. A.<\/small>, George, E. I.<\/small> and McCulloch, R. E.<\/small> (2010). BART: Bayesian additive regression trees. Ann. Appl. Stat.<\/i> 4<\/b> 266\u2013298.","DOI":"10.1214\/09-AOAS285"},{"key":"33","doi-asserted-by":"publisher","unstructured":"KLUSOWSKI, J. M.<\/small> and TIAN, P. M.<\/small> (2024). Large scale prediction with decision trees. J. Amer. Statist. Assoc.<\/i> 119<\/b> 525\u2013537.","DOI":"10.1080\/01621459.2022.2126782"},{"key":"1","unstructured":"ABBE, E.<\/small>, ADSERA, E. B.<\/small> and MISIAKIEWICZ, T.<\/small> (2022). The merged-staircase property: A necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks. In Conference on Learning Theory<\/i> 4782\u20134887. PMLR."},{"key":"2","unstructured":"ABBE, E.<\/small>, ADSERA, E. B.<\/small> and MISIAKIEWICZ, T.<\/small> (2023). SGD learning on neural networks: Leap complexity and saddle-to-saddle dynamics. In The Thirty Sixth Annual Conference on Learning Theory<\/i> 2552\u20132623. PMLR."},{"key":"3","doi-asserted-by":"crossref","unstructured":"ABBE, E.<\/small> and BOIX-ADSER\u00c0, E.<\/small> (2022). On the non-universality of deep learning: Quantifying the cost of symmetry. In Advances in Neural Information Processing Systems<\/i> (A. H. Oh, A. Agarwal, D. Belgrave and K. Cho, eds.).","DOI":"10.52202\/068431-1250"},{"key":"4","unstructured":"ABBE, E.<\/small>, BOIX-ADSERA, E.<\/small>, BRENNAN, M.<\/small>, BRESLER, G.<\/small> and NAGARAJ, D.<\/small> (2021). The staircase property: How hierarchical structure can guide deep learning."},{"key":"5","doi-asserted-by":"publisher","unstructured":"ABBE, E.<\/small> and SANDON, C.<\/small> (2023). Polynomial-time universality and limitations of deep learning. Comm. Pure Appl. Math.<\/i> 76<\/b> 3493\u20133549.","DOI":"10.1002\/cpa.22121"},{"key":"6","unstructured":"AGARWAL, A.<\/small>, TAN, Y. S.<\/small>, RONEN, O.<\/small>, SINGH, C.<\/small> and YU, B.<\/small> (2022). Hierarchical shrinkage: Improving the accuracy and interpretability of tree-based models. In International Conference on Machine Learning<\/i> 111\u2013135. PMLR."},{"key":"7","doi-asserted-by":"crossref","unstructured":"AGHAEI, S.<\/small>, G\u00d3MEZ, A.<\/small> and VAYANOS, P.<\/small> (2025). Strong optimal classification trees. Oper. Res.<\/i> 73<\/b> 2223\u20132241.","DOI":"10.1287\/opre.2021.0034"},{"key":"8","doi-asserted-by":"crossref","unstructured":"AGLIN, G.<\/small>, NIJSSEN, S.<\/small> and SCHAUS, P.<\/small> (2020). Learning optimal decision trees using caching branch-and-bound search. Proc. AAAI Conf. Artif. Intell.<\/i> 34<\/b> 3146\u20133153.","DOI":"10.1609\/aaai.v34i04.5711"},{"key":"10","doi-asserted-by":"crossref","unstructured":"BARAK, B.<\/small>, EDELMAN, B.<\/small>, GOEL, S.<\/small>, KAKADE, S.<\/small>, MALACH, E.<\/small> and ZHANG, C.<\/small> (2022). Hidden progress in deep learning: SGD learns parities near the computational limit. Adv. Neural Inf. Process. Syst.<\/i> 35<\/b> 21750\u201321764.","DOI":"10.52202\/068431-1581"},{"key":"14","doi-asserted-by":"crossref","unstructured":"CARUANA, R.<\/small>, KARAMPATZIAKIS, N.<\/small> and YESSENALINA, A.<\/small> (2008). An empirical evaluation of supervised learning in high dimensions. In Proceedings of the<\/i> 25th International Conference on Machine Learning<\/i> 96\u2013103.","DOI":"10.1145\/1390156.1390169"},{"key":"15","doi-asserted-by":"publisher","unstructured":"CATTANEO, M. D.<\/small>, CHANDAK, R.<\/small> and KLUSOWSKI, J. M.<\/small> (2024). Convergence rates of oblique regression trees for flexible function libraries. Ann. Statist.<\/i> 52<\/b> 466\u2013490.","DOI":"10.1214\/24-aos2354"},{"key":"16","unstructured":"CATTANEO, M. D.<\/small>, KLUSOWSKI, J. M.<\/small> and TIAN, P. M.<\/small> (2022). On the pointwise behavior of recursive partitioning and its implications for heterogeneous causal effect estimation. Preprint. Available at arXiv:2211.10805<\/a>."},{"key":"21","unstructured":"DEMIROVI\u0106, E.<\/small>, LUKINA, A.<\/small>, HEBRARD, E.<\/small>, CHAN, J.<\/small>, BAILEY, J.<\/small>, LECKIE, C.<\/small>, RAMAMOHANARAO, K.<\/small> and STUCKEY, P. J.<\/small> (2022). MurTree: Optimal decision trees via dynamic programming and search. J. Mach. Learn. Res.<\/i> 23<\/b> Paper No. [26], 47."},{"key":"22","unstructured":"FERN\u00c1NDEZ-DELGADO, M.<\/small>, CERNADAS, E.<\/small>, BARRO, S.<\/small> and AMORIM, D.<\/small> (2014). Do we need hundreds of classifiers to solve real world classification problems? J. Mach. Learn. Res.<\/i> 15<\/b> 3133\u20133181."},{"key":"24","unstructured":"GLASGOW, M. R.<\/small> (2024). SGD finds then tunes features in two-layer neural networks with near-optimal sample complexity: A case study in the XOR problem. In The Twelfth International Conference on Learning Representations<\/i>."},{"key":"27","unstructured":"HU, X.<\/small>, RUDIN, C.<\/small> and SELTZER, M.<\/small> (2019). Optimal sparse decision trees. Adv. Neural Inf. Process. Syst.<\/i>."},{"key":"29","doi-asserted-by":"crossref","unstructured":"JOSHI, N.<\/small>, MISIAKIEWICZ, T.<\/small> and SREBRO, N.<\/small> (2024). On the complexity of learning sparse functions with statistical and gradient queries. In The Thirty-Eighth Annual Conference on Neural Information Processing Systems<\/i>.","DOI":"10.52202\/079017-3279"},{"key":"30","unstructured":"KE, G.<\/small>, MENG, Q.<\/small>, FINLEY, T.<\/small>, WANG, T.<\/small>, CHEN, W.<\/small>, MA, W.<\/small>, YE, Q.<\/small> and LIU, T.-Y.<\/small> (2017). Lightgbm: A highly efficient gradient boosting decision tree. Adv. Neural Inf. Process. Syst.<\/i> 30<\/b>."},{"key":"31","unstructured":"KLUSOWSKI, J. M.<\/small> (2020). Sparse learning with CART. In Advances in Neural Information Processing Systems<\/i> (H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan and H. Lin, eds.) 33<\/b> 11612\u201311622. Curran Associates, Red Hook."},{"key":"32","unstructured":"KLUSOWSKI, J. M.<\/small> and TIAN, P.<\/small> (2021). Nonparametric variable screening with optimal decision stumps. In Proceedings of the<\/i> 24th International Conference on Artificial Intelligence and Statistics<\/i> (A. Banerjee and K. Fukumizu, eds.). Proceedings of Machine Learning Research<\/i> 130<\/b> 748\u2013756. PMLR."},{"key":"34","unstructured":"KOU, Y.<\/small>, CHEN, Z.<\/small>, GU, Q.<\/small> and KAKADE, S. M.<\/small> (2024). Matching the statistical query lower bound for k-sparse parity problems with stochastic gradient descent. Preprint. Available at arXiv:2404.12376<\/a>."},{"key":"35","unstructured":"LIN, J.<\/small>, ZHONG, C.<\/small>, HU, D.<\/small>, RUDIN, C.<\/small> and SELTZER, M.<\/small> (2020). Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning<\/i> 6150\u20136160. PMLR."},{"key":"36","unstructured":"LOH, W.-Y.<\/small> (2002). Regression trees with unbiased variable selection and interaction detection. Statist. Sinica<\/i> 12<\/b> 361\u2013386."},{"key":"37","doi-asserted-by":"crossref","unstructured":"MAZUMDER, R.<\/small> and WANG, H.<\/small> (2024). On the convergence of CART under sufficient impurity decrease condition. Adv. Neural Inf. Process. Syst.<\/i> 36<\/b>.","DOI":"10.52202\/075280-2517"},{"key":"39","doi-asserted-by":"publisher","unstructured":"MENDELSON, S.<\/small> (2018). Learning without concentration for general loss functions. Probab. Theory Related Fields<\/i> 171<\/b> 459\u2013502.","DOI":"10.1007\/s00440-017-0784-y"},{"key":"41","doi-asserted-by":"crossref","unstructured":"OLSON, R. S.<\/small>, CAVA, W. L.<\/small>, MUSTAHSAN, Z.<\/small>, VARIK, A.<\/small> and MOORE, J. H.<\/small> (2018). Data-driven advice for applying machine learning to bioinformatics problems. In Biocomputing<\/i> 2018: Proceedings of the Pacific Symposium<\/i> 192\u2013203. World Scientific, Singapore.","DOI":"10.1142\/9789813235533_0018"},{"key":"43","doi-asserted-by":"publisher","unstructured":"RUDIN, C.<\/small>, CHEN, C.<\/small>, CHEN, Z.<\/small>, HUANG, H.<\/small>, SEMENOVA, L.<\/small> and ZHONG, C.<\/small> (2022). Interpretable machine learning: Fundamental principles and 10 grand challenges. Stat. Surv.<\/i> 16<\/b> 1\u201385.","DOI":"10.1214\/21-ss133"},{"key":"44","unstructured":"STEIN, E. M.<\/small> and SHAKARCHI, R.<\/small> (2003). Fourier Analysis<\/i>: An Introduction<\/i>. Princeton Lectures in Analysis<\/i> 1<\/b>. Princeton Univ. Press, Princeton, NJ."},{"key":"46","unstructured":"TAN, Y. S.<\/small>, AGARWAL, A.<\/small> and YU, B.<\/small> (2022). A cautionary tale on fitting decision trees to data from additive models: Generalization lower bounds. In International Conference on Artificial Intelligence and Statistics<\/i> 9663-9685. PMLR."},{"key":"47","doi-asserted-by":"crossref","unstructured":"TAN, Y. S<\/small>, KLUSOWSKI, J. M<\/small> and BALASUBRAMANIAN, K.<\/small> (2026). Supplement to \u201cStatistical-computational trade-offs for recursive adaptive partitioning estimators.\u201d https:\/\/doi.org\/10.1214\/25-AOS2603SUPP<\/a>","DOI":"10.1214\/25-AOS2603SUPP"},{"key":"48","unstructured":"TAN, Y. S.<\/small>, RONEN, O.<\/small>, SAARINEN, T.<\/small> and YU, B.<\/small> (2024). The computational curse of big data for Bayesian Additive Regression Trees: a hitting time analysis. Preprint. Available at arXiv:2406.19958<\/a>."},{"key":"50","unstructured":"TANG, C.<\/small>, GARREAU, D.<\/small> and VON LUXBURG, U.<\/small> (2018). When do random forests fail? In Advances in Neural Information Processing Systems<\/i> 31<\/b> (S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, eds.). Curran Associates, Red Hook."},{"key":"52","doi-asserted-by":"crossref","unstructured":"VERWER, S.<\/small> and ZHANG, Y.<\/small> (2019). Learning optimal classification trees using a binary linear program formulation. Proc. AAAI Conf. Artif. Intell.<\/i> 33<\/b> 1625\u20131632.","DOI":"10.1609\/aaai.v33i01.33011624"},{"key":"55","unstructured":"WASSERMAN, L.<\/small> and LAFFERTY, J.<\/small> (2005). Rodeo: Sparse nonparametric regression in high dimensions. Adv. Neural Inf. Process. Syst.<\/i> 18<\/b>."},{"key":"56","doi-asserted-by":"crossref","unstructured":"WRIGHT, M. N.<\/small>, ZIEGLER, A.<\/small> et al. (2017). ranger: A fast implementation of random forests for high dimensional data in C++<\/b> and R. J. Stat. Softw.<\/i> 77<\/b>.","DOI":"10.18637\/jss.v077.i01"},{"key":"58","doi-asserted-by":"crossref","unstructured":"ZHANG, R.<\/small>, XIN, R.<\/small>, SELTZER, M.<\/small> and RUDIN, C.<\/small> (2023). Optimal sparse regression trees. Proc. AAAI Conf. Artif. Intell.<\/i> 37<\/b> 11270\u201311279.","DOI":"10.1609\/aaai.v37i9.26334"},{"key":"59","unstructured":"ZHU, H.<\/small>, MURALI, P.<\/small>, PHAN, D.<\/small>, NGUYEN, L.<\/small> and KALAGNANAM, J.<\/small> (2020). A scalable MIP-based method for learning optimal multivariate decision trees. Adv. Neural Inf. Process. Syst.<\/i> 33<\/b> 1771\u20131781."},{"key":"18","doi-asserted-by":"publisher","unstructured":"CHI, C.-M.<\/small>, VOSSLER, P.<\/small>, FAN, Y.<\/small> and LV, J.<\/small> (2022). Asymptotic properties of high-dimensional random forests. Ann. Statist.<\/i> 50<\/b> 3415\u20133438.","DOI":"10.1214\/22-aos2234"},{"key":"49","unstructured":"TAN, Y. S.<\/small> and VERSHYNIN, R.<\/small> (2023). Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval. J. Mach. Learn. Res.<\/i> 24<\/b> Paper No. [58], 47."},{"key":"25","doi-asserted-by":"crossref","unstructured":"GRINSZTAJN, L.<\/small>, OYALLON, E.<\/small> and VAROQUAUX, G.<\/small> (2022). Why do tree-based models still outperform deep learning on typical tabular data? Adv. Neural Inf. Process. Syst.<\/i> 35<\/b> 507\u2013520.","DOI":"10.52202\/068431-0037"}],"container-title":["The Annals of Statistics"],"original-title":[],"deposited":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T21:19:24Z","timestamp":1791321564000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-54\/issue-3\/Statistical-computational-trade-offs-for-recursive-adaptive-partitioning-estimators\/10.1214\/25-AOS2603.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,1]]},"references-count":59,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2026,6,1]]}},"URL":"https:\/\/doi.org\/10.1214\/25-aos2603","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,1]]}}}