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.
Here is a possible explanation (could very well be wrong however), maybe you could try modifying their tutorial code to see if this works or not?
For minibatch descent methods the parameters of our model get updated after each minibatch. It's important to note that in the code you posted the training error of each minibatch is computed using a different set of weights.
On the other hand, note that for the validation error, it is being computed with the same set of weights.
And perhaps more importantly, the MLP is being trained with Dropout. When we are computing training error, again, unlike validation error, we do not turn off Dropout. In particular, note that in the code for the validation function we have Deterministic = True while this is absent from the training function.
In particular note that the very purpose of using Dropout is to prevent overfitting, i.e. lower training error than validation error. And to this end, we see that Dropout is doing a good job as it is very easy for even relatively shallow models to overfit the MNIST dataset these days.
So here's what you can try: after each epoch of training, run the val_fn on the training set as well as the validation set. This will come at the cost of an additional full forward pass through the training set. But for MNIST and a simple model like MLP, it isn't going to cost too much in terms of computation and it might be worth it to get your hands dirty modifying some Lasagne code as well as building some general intuition about minibatch + Dropout training.
Best Answer
A model is considered to be 'underfitting' when both the training and validation error are high. When your validation error is lower than your training error than the fit is obscure and inconclusive.
There are multiple reasons why this can happen but one can't be completely certain. It could be because the test cases during the validation belonged to the type of data that influenced the model the most while training or maybe because the test cases contain the type of data that your model is good at predicting. If there is a very small difference, it could be random.
Although, based on your question it is difficult to comment more specifically without knowing the train-test split method or the evaluation metric.
Regarding underfitting and overfitting you can keep these in mind: