Why doesn't overfitting devastate neural networks for MNIST classification?
I have replicated your results using Keras, and got very similar numbers so I don't think you are doing anything wrong.

Out of interest, I ran for many more epochs to see what would happen. The accuracy of test and train results remained pretty stable. However, the loss values drifted further apart over time. After 10 epochs or so, I was getting 100% train accuracy, 94.3% test accuracy - with loss values around 0.01 and 0.22 respectively. After 20,000 epochs, the accuracies had barely changed, but I had training loss 0.000005 and test loss 0.36. The losses were also still diverging, albeit very slowly. In my opinion, the network is clearly over-fitting.

So the question could be re-phrased: Why, despite over-fitting, does a neural network trained to the MNIST data set still generalise apparently reasonably well in terms of accuracy? 

It is worth comparing this 94.3% accuracy with what is possible using more naive approaches.

For instance, a simple linear softmax regression (essentially the same neural network without the hidden layers), gives a quick stable accuracy of 95.1% train, and 90.7% test. This shows that a lot of the data separates linearly - you can draw hyperplanes in the 784 dimensions and 90% of the digit images will sit inside the correct "box" with no further refinement required. From this, you might expect an overfit non-linear solution to get a worse result than 90%, but maybe no worse than 80% because intuitively forming an over-complex boundary around e.g. a "5" found inside the box for "3" will only incorrectly assign a small amount of this naive 3 manifold. But we're better than this 80% lower bound guesstimate from the linear model.

Another possible naive model is template matching, or nearest-neighbour. This is a reasonable analogy to what the over-fitting is doing - it creates a local area close to each training example where it will predict the same class. Problems with over-fitting occur in the space in-between where the values of activation will follow whatever the network "naturally" does. Note the worst case, and what you often see in explanatory diagrams, would be some highly curved almost-chaotic surface which travels through other classifications. But actually it may be more natural for the neural network to more smoothly interpolate between points - what it actually does depends on the nature of the higher order curves that the network combines into approximations, and how well those already fit to the data.

I borrowed the code for a KNN solution from this blog on MNIST with K Nearest Neighbours. Using k=1 - i.e. choosing the label of the nearest from the 6000 training examples just by matching pixel values, gives an accuracy of 91%. The 3% extra that the over-trained neural network achieves does not seem quite so impressive given the simplicity of pixel-match counting that KNN with k=1 is doing.

I tried a few variations of network architecture, different activation functions, different number and sizes of layers - none using regularisation. However, with 6000 training examples, I could not get any of them to overfit in a way where test accuracy dropped dramatically. Even reducing to just 600 training examples just made the plateau lower, at ~86% accuracy. 

My basic conclusion is that MNIST examples have relatively smooth transitions between classes in feature space, and that neural networks can fit to these and interpolate between the classes in a "natural" manner given NN building blocks for function approximation - without adding high frequency components to the approximation that could cause issues in an overfit scenario.

It might be an interesting experiment to try with a "noisy MNIST" set where an amount of random noise or distortion is added to both training and test examples. Regularized models would be expected to perform OK on this dataset, but perhaps in that scenario the over-fitting would cause more obvious problems with accuracy.



This is from before the update with further tests by OP.

From your comments, you say that your test results are all taken after running a single epoch. You have essentially used early stopping, despite writing that you have not, because you have stopped the training at the earliest possible point given your training data.

I would suggest running for many more epochs if you want to see how the network is truly converging. Start with 10 epochs, consider going up to 100. One epoch is not many for this problem, especially on 6000 samples. 

Although increasing number of iterations is not guaranteed to make your network overfit worse than it already has, you haven't really given it much of a chance, and your experimental results so far are not conclusive.

In fact I would half expect your test data results to improve following a 2nd, 3rd epoch, before starting to fall away from the training metrics as the epoch numbers increase. I would also expect your training error to approach 0% as the network approached convergence.