Why does the training error usually underestimate the test error? I understand that most algorithms are optimized to minimize the training error but why is the test error usually larger then the training error? Is there a statistical reason why?
 A: Training and testing data are not identical. 
As you yourself point out, most training optimizes the model performance on the training set; clearly it would tend to be worse on a different set of data.
Consider a really simple case of two samples (training and testing samples) from one population; the sample mean of the training set is closest (in the specific mean square error sense) to the training set, while its mean square error from the test set includes an additional term that is related to the square of the difference in the two sample means.
A: While the other answers make sense, the most importance aspect is overfitting. Lots of people tend to overfit the training data because they can visualize the data, they can think of some way to minimise the training errors, they can try and tune the model until they are satisfied with training errors.
Statistically, this is like a conditional probability. The expected performance of a model given that you know the data in advance is not the same as the performance but without knowing the data in advance.
A: This may not be as statistical an answer as is possible but hopefully it will help. A professor once mentioned to my class that it is possible to make a model or algorithm that perfectly fits the data, but you have to make it as complex as the data, i.e. it needs to have as many variables or instructions as the data has points. Clearly, this is a little problematic to interpret, so that's why a lot of models assume some sort of underlying distribution like the normal distribution or that a straight line best describes what is going on. In thinking about the idea of an algorithm that perfectly describes your data, what happens when you move from the training data to the testing data is that your perfect model is no longer perfect. What the model from the training set tells you to do no longer matches up perfectly with the data that you are using, so you end up with greater error much of the time.
It is possible that the model is a better fit for the testing data set than the training set, but this would seem to be a remarkable coincidence. Or, I guess it could mean that your model isn't all that good because it fits any set of data and, so, doesn't tell you much (i.e. it is too simple). When you have a sample set of data, you are always pulling from a larger population, so another way to look at it is that you are dealing with two samples from a larger group of all possible samples from the population of data. So, the likelihood of creating a model that accurately fits the next sample is small because your testing data set doesn't include all of the population data.
