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

Jérémy Bettinger, François Portier, Adrien Saumard [email protected] ; [email protected] ; [email protected] Department of Statistics, University of Rennes, ENSAI, CNRS, CREST-UMR 9194, F-35000 Rennes, France · 2025

Read On the pointwise and sup-norm errors for local regression estimators by Jérémy Bettinger, François Portier, Adrien Saumard [email protected] ; [email protected] ; [email protected] Department of Statistics, University of Rennes, ENSAI, CNRS, CREST-UMR 9194, F-35000 Rennes, France (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-07132.txt.

Introduction

Jeremy Bettinger, Francois Portier, and Adrien Saumard analyze local regression error in a 2025 statistics paper. Local methods estimate a curve by averaging nearby points. The paper asks when such averaging reaches the best possible accuracy, both at one point and across the whole curve at once.

The key turns out to be the shape of the averaging neighborhoods. Roundish, shape-regular neighborhoods are both needed and enough for optimal rates, up to small factors. The team also studies nearest-neighbor variants and a new tree method that hits the optimal uniform rate. Random tree rules get their own error bounds. Readers get a shape-based theory of local estimation.

Catalog record

CREATORJérémy Bettinger, François Portier, Adrien Saumard [email protected] ; [email protected] ; [email protected] Department of Statistics, University of Rennes, ENSAI, CNRS, CREST-UMR 9194, F-35000 Rennes, France
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE149 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-07132

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the pointwise and sup-norm errors for local regression estimators Jérémy Bettinger, François Portier, Adrien Saumard [email protected] ; [email protected] ; [email protected] Department of Statistics, University of Rennes, ENSAI, CNRS, CREST-UMR 9194, F-35000 Rennes, France Abstract 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. 1 Introduction Consider the standard regression problem where the goal is to estimate the regression function of a random variable Y\in\mathbb{R} given the covariates vector X\in\mathbb{R}^{d} , defined as g(x):=\mathbb{E}[Y|X=x] , x\in\mathbb{R}^{d} . One leading approach, called local regression or local averaging , consists in averaging the observed response variables, restricted to covariates that lie in a small region of the domain \mathbb{R}^{d} . Local regression methods include kernel smoothing regression [ 37 ] , nearest neighbors algorithm [ 18 , 14 ] and regression trees or, more generally, partitioning regression estimators [ 6 , 38 ] . We refer to the books [ 16 , 20 ] for an overview of local regression methods and to [ 4 ] for a precise theoretical account on the nearest neighbors algorithm. Concerning the estimation problem, when the error is measured in terms of the mean squared error ( L_{2} error), the optimal convergence rates are known [ 43 ] and depend on the smoothness of the regression function g . Whether or not these convergence rates are achieved often serves as a theoretical baseline to evaluate the accuracy of local regression methods. For example, a Lipschitz function g can only be approximated at the rate n^{-1/(d+2)} in general, when n independent observations are given. Many of the above estimators are known to achieve optimal convergence rates. The nearest neighbors, the Nadaraya-Watson and the fixed partitioning (histogram) regression estimators are all optimal for Lipschitz functions (as well as for twice differentiable functions for the first two listed methods), as explained in [ 4 ] , [ 44 ] and Chapter 4 of [ 20 ] , respectively. Furthermore, the Nadaraya-Watson [ 17 , 19 ] and the nearest neighbors [ 27 , 39 ] estimators are both known to achieve a rate of sup-norm convergence that is of the same order as the L_{2} -rate (up to a logarithmic term). Other local regression estimators based on purely random trees are of interest [ 11 ] , despite the independence of the leaves with respect to the original data, notably because of their ability to explain certain patterns in the success or failure of different tree constructions and to illustrate the success of random forest regression. Among purely random trees, Mondrian trees, as introduced in [ 32 ] , indeed achieve the optimal convergence rate [ 34 ] for Lipschitz functions, while, in contrast, centered trees do not reach it [ 7 , 28 ] . It is also worth highlighting that partitioning the space with Voronoi cells based on another sample (independent of the original data) can also lead to the optimal rate of convergence [ 24 , 30 ] . This type of approach is known as nearest neighbor-based prototype learning rules (as described in [ 16 ] , Chapter 19). They have recently receive much attention [ 22 , 29 , 25 , 24 , 49 , 30 ] due to (a) their ability to compress data - offering interesting ways to reduce time complexity and memory use - and (b) their surprisingly good statistical performances. A prototype learning algorithm follows from the construction of some “prototype data”, based on the initial sample, and training a learning rule based on these prototypes. Hence, good prototype learning algorithms would require a small number of prototypes while maintaining good statistical performance. One first remarkable fact is that prototype learning acts as regularization: the overfitting 1 -NN algorithm may be consistent when applied to a good prototype sample [ 29 , 25 , 24 , 49 , 30 ] . Another notable fact is that some prototype rules are universally consistent in general metric spaces, while k -NN is not [ 29 , 25 , 24 ] . Despite the many existing results available for the Nadaraya-Watson and nearest neighbors regression estimators, and also fixed or purely random partitioning regression rules, only a few are known about local regression based on data-dependent partitions, such as the well-known CART regression tree [ 6 ] . Such an algorithm is indeed much harder to analyze mathematically. First results on data dependent partitions can be found in [ 42 ] , but they are restricted to cases where the partition depends only on the covariates, as in nearest neighbors regression or for statistically equivalent blocks [ 2 ] . More advanced results, that are valid for general data dependent partitioning estimators, are obtained in [ 23 , 6 , 38 ] , where conditions are given to ensure almost sure L_{2} -consistency. The typical assumptions that are required in the previous works include (i) large enough points in each partition element and (ii) small diameter, while having (iii) a reduced complexity on the partition elements. Note also that Theorem 1 in [ 41 ] can be applied to CART regression algorithm and gives sufficient conditions for the L_{2} -consistency. Beyond consistency, few is known about the convergence rates of data-dependent, CART-like regression tree estimators. Recent studies [ 15 , 36 ] have obtained convergence rates for the L_{2} -error under the so-called sufficient impurity decrease (SID) condition, that is directly linked to the behavior of the precise splitting rule of CART in the regression context. The rate of convergence obtained depends on a parameter - denoted \lambda in [ 36 ] - quantifying the strength of the SID condition, and it is not a priori easy to discuss the rate optimality. Nonetheless, it is shown in [

Read the complete text