What is the penalty for not using all available points in cross-validation?

Cross-validation is an extremely useful and popular technique, as shown by the inspired name of this site. However, it can often be quite expensive. For example, take Nadaraya-Watson regression, where cross-validation requires $O(n^2)$ operations where $n$ is the number of data points. So there is a motivation to speed up the cross-validation process, especially if the number of points you ultimately want to predict is $\ll n$ and therefore quick to compute in comparison.

So I'm wondering about the effect of using only part of the data - say randomly choose $p$ training points and $q$ test points where $p, q \ll n$. I'm wondering whether there is a general rule for the effect of this approach. There is such a general rule for using only part of the data in a model fit, since the variance generically goes as $O(1/n)$ for large $n$. I suspect cross-validation is somewhat more tolerant of small sample sizes, but don't know how to formulate a general rule. Can anyone help?

Edit: a specific example: Suppose we have points $(X_i, Y_i)$ where $Y$ is $r(x)$ plus a noise term. We estimate $r$ as $\hat{r}$ by Nadaraya-Watson with a bandwidth $h$. Let us estimate the leave-one-out cross-validation score as $(1/p) \sum_i^p (Y_i - \hat{r}_{-{s(i)}}(X_{s(i)}))^2$ where $\hat{r}_{(-i)}$ is the estimator obtained by leaving out $i$ and $i$ runs over a randomly chosen subset of 1 to n. $h$ is chosen by minimizing this score. Consider the limit of large $n$ and small $p/n$. Is it possible to expand the mean and variance of $\hat{r}$ in terms proportional to some power of $p$?

Feel free to substitute any other preferred cross-validation technique, the key point is the use of only a subsample of the data as evaluation points for the cross-validation score (but use of all of the data in the estimator).

• In statistical classification problems their is leave-one out cross-validation where only one observation is left out at a time. But the process is repeated using leaving out a different observation and done n times so that the classifier gets constructed n times and each time classification error rates are computed. These estimates are combined in a way that leads to a nearly unbiased estimate of error rate. This has a long history dating back to Lachenbruch & Mickey in the 1960s. Brad Efron in 1983 introduced a bootstrap approach that improved on leave-one-out. Many other papers followed. – Michael Chernick Jan 6 '17 at 19:46
• @MichaelChernick I'm asking what would happen if you ran for example the leave-one-out approach with a subsample of only p << n points, instead of using all n points. How would the variance of the predictions change? – mfardal Jan 6 '17 at 20:52
• Th.at wouldn't be leave-one-out. In fact I thought the version of cross validation was very different from leave one out. I am not understanding your question very well. I just thought that maybe you weren't aware of leave-one-out because it seemed that you were taking it for granted that cross-validation had to have a subset of the data for fitting and a separate set for testing (evaluating) the model. – Michael Chernick Jan 6 '17 at 22:12
• Your question nevertheless seems to not be specific enough to get a reasonable answer. There are very many forms of cross-validation. What version do you have in mind? Are you focused on regression and does Nadaraya-Watson play a role in this or are you just using it as an example? – Michael Chernick Jan 6 '17 at 22:20
• Cross-validation is a general technique, and in principle my question is equally general. Personally I mainly use cross-validation for locally constant and linear regression as well as kernel density estimation, so you can consider those as the motivating examples. – mfardal Jan 7 '17 at 0:59