# understanding overfitting and underfitting and model selection

Is it true that Over-fitting yields a low error rate on the validation set?

I'm a bit confused here. By definition, Overfitting means we have minimized the cost function with a given hyperparameter for all training examples, and that reduced cost is meagre.

Now we are going to find that hyperparameter that gives the smallest error using the validation set.

So then that means after we overfit on the training set with a given hyperparameter, the resulting model would be tested on how well it does on the validation set. And we would or not get a high error.

Under-fitting yields too large an error rate on both the training and validation set. The above is because when you underfit, you get a large error for training data. And so you might or might not get a hight error on the validation set. And so we don't need to care about the validation set, as they don't give many pieces of information.

Hence, when we are given the choice of several learning algorithms, we should choose the one that manages to best the learn examples on the training set.

find that hyperparameter that gives the smallest error using the validation set.

If you use a validation set to optimize hyperparameters, that data is part of your training data (regardless of the name validation set).
In order to avoid confusion with the terminology (because it is not used for validation of the actual model), I'm going to use a new name for this data set and call it optimization set for the rest of this answer.

So then that means after we overfit on the training set with a given hyperparameter, the resulting model would be tested on how well it does on the validation set. And we would or not get a high error.

If this second "validation set" here is the optimization set used before for hyperparamteter optimization, then no: it will yield low error if the model is overfit.

But if you do an actual validation (verification) using data that is completely independent of any data involved in the training of the model ("training set" and "optimization set") that may yield high error. I'm going to call this independent test set verification set for now to be unambiguous.
The difference high error on verification set and low error on optimization set indicates overfitting.

And so we don't need to care about the validation set, as they don't give many pieces of information.

It does, though: overfitting is not a black/white situation but rather there is a continuum of situations ranging from underfit over good, moderately overfit to severely overfit.

If you look at the errors of the three data sets:

                   error: model is
data               underfit   good    moderately overfit   severely overfit
----               --------   ----    ------------------   ----------------
training set        high       low     low                  low
optimization set    high       low     high                 low
verification set    high       low     high                 high


The error on the "training set" will first go down (become uninformative) while the error on the optimization set is still informative and not as low as the error on the training set. The optimization set helps against overfitting, but it is not a magic bullet: it can only help so much. So it does help guarding against slight overfitting, but you may look at severely overfit models that are overfit on training and optimization data sets.

On the other hand, you are right that the optimization set does only carry limited amounts of information (just as any finite data set). So, if you "ask too much" from the optimization set, you'll end up overfitting in the hyperparameter optimization. The recipe for disaster here is comparing many tentative models (hyperparameter sets) on the basis of only few cases in the optimization set.