On the pointwise and sup-norm errors for local regression estimators

In this paper, we analyze the behavior of various non-parametric local regression estimators, i.e. estimators that are based on local averaging, for estimating a Lipschitz regression function at a fixed point, or in sup-norm. We first prove some deviation bounds for local estimators that can be indexed by a VC class of sets in the covariates space. We then introduce the general concept of shape-regular local maps, corresponding to the situation where the local averaging is done on sets which, in some sense, have ``almost isotropic'' shapes. On the one hand, we prove that, in general, shape-regularity is necessary to achieve the minimax rates of convergence. On the other hand, we prove that it is sufficient to ensure the optimal rates, up to some logarithmic factors. Next, we prove some deviation bounds for specific estimators, that are based on data-dependent local maps, such as nearest neighbors, their recent prototype variants, as well as a new algorithm, which is a modified and generalized version of CART, and that is minimax rate optimal in sup-norm. In particular, the latter algorithm is based on a random tree construction that depends on both the covariates and the response data. For each of the estimators, we provide insights on the shape-regularity of their respective local maps. Finally, we conclude the paper by establishing some probability bounds for local estimators based on purely random trees, such as centered, uniform or Mondrian trees. Again, we discuss the relations between the rates of the estimators and the shape-regularity of their local maps.