What is the trade off between having a larger validation set versus a smaller one?

Question

• Suppose I am comparing several models, e,g, $\{ax\}$, $\{ax+b\}$ and $\{ax^2 + bx + c\}$, $\{ax^3\}$ on data set $\mathcal{D} = \{x_i,y_i\}_{i = 1}^N$

  I partition $\mathcal{D}$ into training set ($N-K$ points) and validation set ($K$ points).

  I first train my models on the training set to obtain hypothesis

  e.g., $h_1 = a^\star x$, $h_2 = a^\star x + b^\star$, $h_3 = a^\star x^2 + b^\star x + c^\star, \ldots$

  Then I run my hypothesis $h_i$ on the validation set to obtain the error, and choose the hypothesis with the smallest validation error.

What is the tradeoff between having a larger $K$ versus a smaller $K$?

I considered the extreme cases when $K = 0$ and $K = N$.

For $K = 0$, I am picking my hypothesis directly from the training set. Hence I might have more overfitting, and worse out of sample performance

For $K = N$, I pick each hypothesis from my training set at random, then sending all these random hypothesis through the validation set to obtain the minimum error. Hence I might miss out on the best hypothesis?

I can't seem to put this comparison into words. Can anyone help

Answer 1

As the sample decreases the variance error of your estimates will increase. Thus the trade off will be how certain you are about your parameter estimates - either you are relatively certain about the parameters that result from the training or about those from the test data. You can have a look here.

Using terminology of your question, with small training samples you are validating many weak hypothesis. On the other hand, using small test data makes you uncertain wether your strong hypothesis is true. Both is not very satisfying so you usually want to balance both concerns by deviding the data less extreme, e.g. deviding by 70/30 or so.