# Cross validation and the Bias Variance trade-off

So I know that there have been a lot of questions about this topic but I try to understand it from a bit more theoretical/mathematical point of view. I have some basic questions of how cross-validation works and then I will have some more specific questions with respect to the Bias-Variance trade-off in K-fold cross-validation.

So let's first write down the formula of the error of CV which is used to estimate the prediction/test error: $$CV(\lambda)= \frac{1}{N}\sum_{k=1}^{K}\sum_{i\in S_k}L\left[y_i, \hat{f}_{\lambda}^{-k}(\vec{x}_i)\right].$$ In this above formula, $$L$$ is some loss function like the squared error, $$S_k$$ are the K sets in which we split our data $${(y_i,\vec{x}_i)}$$, $$i=1,...,N$$, $$\hat{f}_{\lambda}^{-k}$$ denotes the fitted model when we left out the $$k$$-th fold for testing and $$\lambda$$ is the parameter that regulates the model complexity. This is the averaged error over all K folds and should estimate the true prediction error.

For the Bias variance trade-off we now assume the model $$y_i = f(x_i) + \epsilon_i$$ where the errors are gaussian with $$\epsilon_i$$~$$N(0, \sigma^2)$$. We then estimate $$f$$ by fitting our model $$\hat{f}$$ on the training set $${(y_i, x_i)}$$. The Bias Variance decomposition can be obtained from the prediction/test error (the expected MSE) for the case of prediction, i.e. that we have a unseen training set $${(y_0, x_0)}$$: $$E\left[\left(y_0 - \hat{f}(x_0)\right)^2\right] = \left(E\left[\hat{f}(x_0)\right]-f(x_0)\right)^2 + E\left[\left(\hat{f}(x_0)-E\left[\hat{f}(x_0)\right]\right)^2\right] + E\left[\left(y_0 - f(x_0)\right)^2\right]$$ which is nothing else than: $$E\left[\left(y_0 - \hat{f}(x_0)\right)^2\right] = \left(Bias\left(\hat{f}(x_0)\right)\right)^2 + Var \left(\hat{f}(x_0)\right) + \sigma^2$$

So first the basic questions:

1.) If we want to find the parameter $$\lambda$$ that is optimal, will we chosse a range of values for $$\lambda$$ for each of which we will perfrom a whole cross-validation process (i.e., for each $$\lambda$$, we fit K different $$\hat{f}_{\lambda}^{-k}$$) and then we choose from the different results that $$\lambda$$ that delivered the smallest CV error?

2.) If we perform a cross-validation with fixed $$\lambda$$, we will get K different $$\hat{f}_{\lambda}^{-k}$$ for the same model (i.e., they only vary in the estimated paramters due to the different training sets, but they all have the same functional form). How will we obtain now the estimate $$\hat{f}_{\lambda}$$ which we might want to compare to a completely new test set to assess the bias or variance of this estimate (like in the bias variance trade-off)? Will we average over the K models fitted to different subsets, and if so how do we average over models? Or would we just train the model used for CV on a completely new training set?

3.) How can we obtain $$E\left[\hat{f}_{\lambda}(x_0)\right]$$? Do we have to estimate this expected value as well by averaging over all $$\hat{f}_{\lambda}^{-k}$$? Or do we actually first have to get $$\hat{f}_{\lambda}$$ and then estimate the mean somehow from this?

Now the more specific questions:

They are all with respect to the question of how the choice of K influences the Bias and the Variance of our estimated model. Again, I would like to discuss theoretical arguments and intuition rather than actual experimental results.

So let's keep $$\lambda$$ fixed and the number of total training samples $$N$$ as well such that we only vary K, the number of folds. I know that the bias is mainly influenced by the fact that for a different number of folds K, the size of the training set varies, i.e. for small K we have small training sets and for big K we have big traning sets, in general, number of training data=$$(K-1)\frac{N}{K}$$. The variance however is mainly influenced by the overlap of the training set, i.e., for small K we have only few overlap and for big K we have huge overlap. I know that for small K the bias is high and the variance is low and for large K the bias is low and the variance is high. I just dont understand theoretical arguments.

4.) For small K, i.e. small training samples, we introduce a bias because $$\hat{f}_{\lambda}^{-k}$$ is likely to be far off $$E[\hat{f}_{\lambda}]$$ which will add to the prediction error on an independent test set. (This is what I found in a text book). On the other hand, if K approaches N, $$\hat{f}_{\lambda}^{-k}$$ will approach the best fit $$E[\hat{f}_{\lambda}]$$, which should decrease the bias. However, in my understanding this is not the defintion of bias as in the formula of the bias variance trade off above, but the definition of the variance of $$\hat{f}_{\lambda}$$. In general this brings up the question how the bias is related to the sample size. As I understand it, a biased estimator is biased no matter if it was obtained using a small sample or the whole population, unless it is an efficient estimator but here we can hardly say anything about wheather or not our estimate of f is efficient.

5.) Also I do not understand why a huge overlap of the training sets will lead to a high variance. I do understand that all the K models will be similar and if we take the average of these models (again question 2. how do we do that?) the resulting one will be overfitted to the data used for CV. But why does this introduce a high variance? I know that overfitting means that we have probably modelled noise which is bad for generalization, but to me this would rather introduce a bias, because we have a model that tries to model noise rather than the actual data and therefore will be systematically off from the true model. Can this be explained somehow with the quantities in the bias variance trade-off?