Bandwidth Selection in Nonparametric Regression with Large Sample Size ^†

Abstract

In the context of nonparametric regression estimation, the behaviour of kernel methods such as the Nadaraya-Watson or local linear estimators is heavily influenced by the value of the bandwidth parameter, which determines the trade-off between bias and variance. This clearly implies that the selection of an optimal bandwidth, in the sense of minimizing some risk function (MSE, MISE, etc.), is a crucial issue. However, the task of estimating an optimal bandwidth using the whole sample can be very expensive in terms of computing time in the context of Big Data, due to the computational complexity of some of the most used algorithms for bandwidth selection (leave-one-out cross validation, for example, has $\mathcal{O}\left(n^2\right)$ complexity). To overcome this problem, we propose two methods that estimate the optimal bandwidth for several subsamples of our large dataset and then extrapolate the result to the original sample size making use of the asymptotic expression of the MISE bandwidth. Preliminary simulation studies show that the proposed methods lead to a drastic reduction in computing time, while the statistical precision is only slightly decreased.

1. Scenario

Let us consider a sample of size n, ${\left\{(x_i,y_i)\right\}}_{i=1,\cdots ,n}$, drawn from a nonparametric regression model $y_i=m\left(x_i\right)+{\epsilon }_i$. We assume random design, $\mathbb{E}[\epsilon \mid x]=0$ and $\mathbb{E}[{\epsilon }^2\mid x]={\sigma }^2\left(x\right)<\infty$. In this context, we deal with the Nadaraya-Watson estimator [1] for the regression function, m, which is characterized by the kernel function K and the bandwidth or smoothing parameter $h>0$. Under suitable conditions, the asymptotically optimal (in the sense of minimum AMISE) bandwidth satisfies

$$h_{AMISE,n}=c_0{n}^{-\frac{1}{5}}.$$

(1)

Since we are assuming that the sample size, n, is very large, the task of computing a bandwidth selector using the whole sample would be too computationally expensive. For example, the leave-one-out cross-validation (LOO CV) bandwidth selector has complexity $\mathcal{O}\left(n^2\right)$.

2. Bandwidth Selection

The idea behind our proposal is to find the LOO CV bandwidth for several subsamples and then extrapolate the result to the original sample size using the asymptotic expression of the MISE bandwidth (1).

2.1. One Subsample Size (OSS)

The idea behind this method is to draw several subsamples of size r, much smaller than n, then compute the LOO CV selector and finally use Equation (1) to extrapolate the CV bandwidth for the original sample size (this idea was already proposed in [2] in the context of kernel density estimation to reduce the variance of the CV bandwidth selector).

• Obtain s subsamples of size $r\ll n$ subsampling without replacement from our original dataset.
• For each subsample, find the LOO CV bandwidth.
• Let ${\widehat{h}}_r$ denote the average of these bandwidths.
• We estimate the unknown constant $c_0$ by ${\widehat{c}}_0={\widehat{h}}_r{r}^{\frac{1}{5}}$.
• Therefore, our estimate of the AMISE bandwidth would be ${\widehat{h}}_{AMISE,n}={\widehat{c}}_0{n}^{-\frac{1}{5}}={\widehat{h}}_r{\left(\frac{r}{n}\right)}^{\frac{1}{5}}$.

2.2. Several Subsample Sizes (SSS)

We now propose a method that considers several subsamples of different sizes.

• Consider a grid of subsample sizes, $r_1,\cdots ,r_s$, with $r_j\ll n$.
• For each $r_j$, compute the LOO CV bandwidth, ${\widehat{h}}_j$ (several subsamples of each size could be considered).
• Solve the ordinary least squares problem (or a robust analogue) given by $({\widehat{\beta }}_0,{\widehat{\beta }}_1)=\underset{{\beta }_0,{\beta }_1}{arg\; min}{\displaystyle \sum _{i=1}^s}{(log\left({\widehat{h}}_i\right)-{\beta }_0-{\beta }_{1}log\left(m_i\right))}^2$, in which case $\widehat{c}=e^{{\widehat{\beta }}_0}$ and $\widehat{p}={\widehat{\beta }}_1$ is our estimate of the order of convergence of the AMISE bandwidth.
• Our estimate of the AMISE bandwidth for the original sample size, n, would be ${\widehat{h}}_{AMISE,n}=\widehat{c}{n}^{\widehat{p}}$.

3. Simulation Study

Let us consider samples of size $n={10}^6$ drawn from the model $Y=m\left(X\right)+\epsilon$, where $X\sim Beta(2,2)$, $\epsilon \sim N(0,0.2^2)$ and $m\left(x\right)=1+xsin{\left(5.5\pi x\right)}^2$. Furthermore, we have considered a Gaussian kernel and, as a weight function, $w\left(x\right)=1_{\{F_X^{-1}\left(0.05\right)\le x\le F_X^{-1}\left(0.95\right)\}}$, where $F_X^{-1}$ denotes the marginal quantile function of X.

It is clear from Figure 1 that the OSS selector outperforms the SSS selector in terms of statistical precision. Moreover, in many cases bandwidths that are quite distant from the optimum do not have an associated large error (in terms of AMISE). On the other hand, as we can observe in

Table 1. CPU elapsed times for the OSS selector with $n={10}^6$. 10 subsamples of the corresponding size were considered.

Subsample Size	CPU Elapsed Time (s)
500	1.62
1000	2.82

and 

Table 2. CPU elapsed times for the SSS selector with $n={10}^6$ considering uniform grids (of 20 elements) of subsample sizes ranging from 100 to the corresponding maximum size. 10 subsamples of each of the corresponding sizes were considered.

Maximum Subsample Size	CPU Elapsed Time (s)
500	9.21
1000	17.9
1500	32.1
2000	51.0
2500	75.1

, the OSS selector is substantially faster than the SSS selector due to the fact that the former works with a single subsample size which, in turn, is even smaller than most of those considered for the SSS selector). It should be noted that the source code for both selectors was written in C++ and run in parallel on an Intel Core i5-8600K 3.6 GHz.