CSL Communications Group Calendar

Back to Listing


Event Type
Coordinated Science Lab
141 CSL; 1308 W. Main Street, Urbana
Sep 30, 2019   4:00 - 5:00 pm  

Speaker:  Professor Sabyasachi Chatterjee, University of Illinois

Title: Adaptive Estimation of Multivariate Piecewise Polynomials and more by Dyadic Cart type methods

Abstract: Dyadic Cart is an important Non Parametric Regression method, first proposed in Donoho[97] who demonstrated it to be optimally adaptive in estimating anisotropically smooth function classes. In this paper we revisit the Dyadic Cart estimator and also introduce a closely related estimator which we call as the Model Selection Cart (MS Cart) estimator. We then study its risk properties for some Non Smooth function classes.  In particular, we are motivated by the problem of estimating $d$ dimensional regression functions which are piecewise polynomial on axis aligned rectangles, where $d \geq 1.$ The main complication in this problem is that the number of level sets of the regression function and their orientation is unknown. We first show that the MS Cart and the Dyadic Cart are efficiently computable estimators with number of basic operations needed bounded by $d O(N^{2 + 1/d})$ and $O(N)$ time respectively. We then prove oracle inequalities for the finite sample risk of MS Cart and Dyadic Cart. These oracle inequalities imply tight bounds for several function classes of interest. Firstly, they imply that the finite sample risk of MS Cart is always bounded by $C k log n/n$ whenever the regression function is piecewise polynomial on a axis aligned rectangular partition of the domain with exactly $k$ rectangles and the partition satisfies some natural regularity conditions. This in particular implies that modulo a log factor, the risk of the MS Cart estimator performs as well as an oracle estimator which knows the number of level sets and their orientation. Such theoretical guarantees are largely absent for CART type estimators in the literature. Secondly, our oracle inequalities help in uncovering optimality of the Dyadic Cart estimator for function spaces with Bounded Variation. We establish that the Dyadic Cart not only is minimax rate optimal over these Bounded Variation spaces but also adapts to further structure in the true function. Such guarantees are not available in these parameter spaces for an estimator which is computable in $O(N)$ time.

Bio: I am an Assistant Professor in the Department of Statistics at UIUC. Broadly, I am interested in the intersection of Statistics, Probability and Information Theory. My research, so far, has been in the field of Statistical Learning/Non Parametric Regression. For more specific information about my research papers, please visit https://publish.illinois.edu/sabyasachi/.

link for robots only