Jason Klusowski (Princeton University) will be our final seminar speaker for the spring semester on Monday April 28, 2025. We will have a social time at 10:30 and the seminar will follow at 11:00. Both will take place in 3105 Snedecor Hall.

Title: Statistical-computational Trade-offs for Recursive Adaptive Partitioning Estimators

Abstract: Recursive adaptive partitioning estimators, like decision trees and their ensembles, are effective for high-dimensional regression but usually rely on greedy training, which can become stuck at suboptimal solutions. We study this phenomenon in estimating sparse regression functions over binary features, showing that when the true function satisfies a certain structural property—Abbe et al. (2022)’s Merged Staircase Property (MSP)—greedy training achieves low estimation error with only a logarithmic number of samples in the feature count. In contrast, when MSP is absent, estimation becomes exponentially more difficult. Interestingly, this dichotomy between efficient and inefficient estimation resembles the behavior of two-layer neural networks trained with SGD in the mean-field regime. Meanwhile, ERM-trained recursive adaptive partitioning estimators achieve low estimation error with logarithmically many samples, regardless of MSP, revealing a fundamental statistical-computational trade-off for greedy training.

Biography

Jason M. Klusowski is an Assistant Professor in the at Princeton University, where he is also a Participating Faculty in the Center for Statistics and Machine Learning (CSML). His research interests broadly span statistical machine learning for complex, large-scale models, focusing on the trade-offs between interpretability, statistical accuracy, and computational feasibility. He works on topics such as decision trees and ensemble learning (CART, random forests, stacking), neural networks (approximation theory and statistical properties), gradient-based optimization (ADAM, SGD), and the large limit behavior of statistical models (Lasso, Slope). Recently, his research has expanded to include the study of transformers and large language models.