Center for Advanced Intelligence Project

Title of the talk: Statistical-Computational Trade-offs for Recursive Adaptive Partitioning Estimators

Speaker: Yan Shuo Tan (National University of Singapore)

Date and time: 2025/Aug 20th, 10:00-11:00 (JST)

Venue: Hybrid (Zoom / RIKEN AIP Nihonbashi Office)
*RIKEN AIP Nihonbashi office is only for AIP members

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* does not satisfy Abbe et al. (2022)’s Merged Staircase Property (MSP), greedy training requires exp(Ω(d)) to achieve low estimation error. Conversely, when f* does satisfy MSP, greedy training can attain small estimation error with only O(log d) 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(log d) 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. This talk is based on recent joint work with Jason Klusowski and Krishnakumar Balasubramanian.

Language: English
Registration required: yes

Bio: Yan Shuo Tan is currently an assistant professor at the Department of Statistics and Data Science at the National University of Singapore. He was previously a Neyman Visiting Assistant Professor at UC Berkeley’s Statistics Department, where he was advised by Bin Yu. He graduated with a PhD in Mathematics at the University of Michigan, where he was advised by Roman Vershynin and Anna Gilbert. His current research is on statistical machine learning, focusing on the theory, methodology and applications of modeling with tree-based models and randomized ensembles.