Multivariate Dyadic Regression Trees for Sparse Learning Problems

• Activity Number: 400
• Type: Topic Contributed
• Date/Time: Tuesday, August 3, 2010 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Han Liu+ and Xi Chen*
• Companies: Carnegie Mellon University and Carnegie Mellon University
• Keywords: Multivariate Regression Trees ; Dyadic Partition ; Sparse Learning Problems ; Penalized Empirical Risk Minimization ; Sparsity-inducing Penalty ; Greedy Algorithms

Abstract

We propose a new nonparametric learning method based on multivariate dyadic regression trees (MDRTs). Unlike traditional dyadic decision trees (DDTs) or classification and regression trees (CARTs), MDRTsare constructed using penalized empirical risk minimization with a novel sparsity-inducing penalty. Theoretically, we show that MDRTs can simultaneously adapt to the unknown sparsity and smoothness of the true regression functions, and achieve the nearly optimal rates of convergence (in a minimax sense) for the class of $(\alpha, C)$-smooth functions. Empirically, MDRTs can simultaneously conduct function estimation and variable selection in high dimensions. To make MDRTs applicable for large-scale learning problems, we propose a greedy heuristic algorithm and a more effective randomization scheme. The superior performance of MDRTs are demonstrated on both synthetic and real datasets.