Neural Network training accuracy better than validation accuracy, using the same samples. Shouldn't they converge?

Question

I'm training a neural network to classify the MNIST digits. For this, I am using this mnist library which states:

It includes 10000 different samples of mnist digits.

And:

Both sets [training and validation] are shuffled, and there are no samples repeated in both sets.

So, what I'm doing is create a 8000 samples training set, and a 2000 validation set, train against the first one, validate against the second one, and measuring accuracy in both. With each epoch I create new training/validation sets.

Witch each training run, I can see the training set accuracy increasing, reaching +98%. But validation set accuracy gets stuck at around 88% consistently.

So my question is, given the fact that both training and validation are randomly selected in each iteration from the same total samples (the 10.000 samples cited above), how can validation accuracy and training accuracies converge to different values?

At the end of the day, with each iteration, each new 8000/2000 pair would contain a large number of overlapping samples with sets of previous iterations, specially if taken out of only 10.000 total. I mean, it says that validation set has no repeated sets with the training set, but that's only for each training/validation creation. Why does validation behave differently, and not converge to training accuracy in the long run?

Answer 1

As it was suggested in some of the comments, this seems to be a case of overfitting. However, what was counter-intuitive IMHO is the behavior of the MNIST library I am using.

If you take a closer look to the library code, you can see that every time you call mnist.set(8000,2000) to generate a training set of 8000 samples, and a validation set of 2000 samples, it generates the exact same two sets every time. The samples are shuffled within each set and after the total sets are partitioned in trainingSet<->validationSet, but the first 8000 samples are training, and the last 2000 are validation, that does not change. At first, I thought the library would randomize the total sets so each subsequent mnist.set invocation would create a different trainingSet/validationSet pair (regardless of internal randomization in each set), but that was not the case.

In other words, it doesn't make sense, with this library, to make something like this (in pseudo-code):

for each epoch {
   aSet = mnist.set(8000, 2000)
   trainingSet = aSet.training
   validationSet = aSet.validation

   doTraining(trainingSet)
   doValidation(validationSet)
}

The code above would produce the same aSet.training and aSet.validation every time, only that each set would be randomized, but never mixed with each other.

Having clarified this, now I can see that I am training always with the same training set, and validating always with the same validation set, so I am not using "the same samples" for validation and training as I thought I was.