Why should validation error be higher than training error? I was reading about learning curve and in a page, this curve is shown:


But I think something is wrong with it. If an estimator tunes it parameters on validation set, then validation error should be lower than training error. Because we have tuned estimator's hyper parameters to achieve the best result on validation error. 
Why is training error lower than validation error in this figure?
 A: Training error tends to be lower than cross validation error. This is an intuitive explanation, ignoring the random effects:
In cross validation, you divide the train set T into two parts T1 and T2, train on T1 and test on T2. You tune the parameter to minimize the error on T2, but the validation error on T2 tends to be higher than the train error on T1 : $$er(T1)<e(T2)$$ because you train the model on T1 and have more opportunity to fit the model on it. On the other hand, er(T1)~er(T) as you train the model with the same tuned parameter on T1 and T. All together $$er(T2)>er(T)$$ which is what you also see in the diagram.
A: In a very simple case, you have one training set and one test set. You train on the training set and then you test on the test set. As you have trained on the training set, the network has already seen the data and the optimization method was optimized for this data. Hence the error on the test set should be higher.
If you have hyper parameters which you want to optimize, you will split your training set into a training and a development set. You train for different choices on the training set, see the error on the development set and at the end, when you think everything is fine, you test on the test set. The test set should NEVER be used for optimization.
n-fold cross-validation makes better use of your data. You make $n$ disjunct sets $b_1, \dots, b_n$ of data. One bin $b_i$ is your test set and the rest $T_i = b_1 \cup \dots \cup b_n \setminus b_i$ is your training data. You train on $T_i$ and test on $b_i$ for all $i \in 1, \dots, n$. Then you average the error. You should not use this for hyper parameter optimization as this will add knowledge of the test set to your system. Hyper parameter optimization should only be done on the training set.
