I'm currently studying some basic concepts regarding Deep Learning and Neural Networks with this material.

When discussing the training algorithm for a perceptron, the author states that looping through the training data in constant order is not always a good idea, specially in data sets where some labels could be somewhat ordered.

For example, say the model is being trained on a set of 1000 examples, the first 500 have a "positive" label, and the last 500 have a "negative" label. If these examples are iterated in their original order within the data set, in order to determine the weights of the perceptron, then after evaluating the error of the first few examples (which are "positive") the model would likely decide that every example is "positive", and would stop learning anything. It would perform well for a while, until it begins to evaluate the "negative" examples, when it would begin predicting everything as "negative". In the end, the model would've learned from only a handful of examples.

This makes perfect sense to me, and I understand the need to permute the data before iterating over it in the training algorithm. However, it is said that the convergence could be achieved even faster (about twice as fast), if the data is re-permuted in each iteration.

How does this improvement actually happen? Is there a way to actually quantify the difference in the number of epochs needed for convergence when the data is permuted once and when it is re-permuted with each iteration (maybe a statistical model, or something of the sort)? Also, are there any special cases where permuting the data with each iteration is actually ill-advised?