# What does the “randomly shuffle training samples” in stochastic gradient descent attain?

What does the "randomly shuffle training samples" in stochastic gradient descent attain?

I interpreted that since the training samples are used to compute

$$\hat{y}=f(w^t x)$$

so if the order of $$x$$s changes, then the weights will be assigned "based on different order"?

Although, since $$w^tx$$ is linear (order doesn't matter), then where is the effect of this seen?

Or maybe it's not seen in $$\hat{y}$$ but in the LMS update rule:

$$\Delta w_{ij}^k=\lambda(\hat{y}_i^k-y_i^k)\color{red}{x^î_j}$$

If you are not training with minibatches, but just one batch per epoch, then random shuffle does nothing. However, if you are training with minibatches, and the data in the first minibatch is related and vastly different from the last minibatch, the error that is back propagated from the first could be totally the opposite of the error in the final.

By shuffling the records, the minibatches as presumably more representative of the entire training data and so the back-propagation of the errors will be, hopefully, making slow but stead progress towards the global minima, not whipsawing back and forth chasing what would essentially be a class based minima.

• But shouldn't the LMS update rule also perform differently, if $f$ is a non-linear activation function? Since then one will have a term of the form $\lambda \hat{y}_i^k x_j^i$, which is not linear and will not therefore be order-independent. Or perhaps the phenomenon that you argue is the same as that occuring in the LMS update rule? – mavavilj Dec 8 '18 at 16:36
• Although even if $\hat{y}$ was linear, then e.g. the product $\hat{y}_i^k x_j^i$ may not, since $\hat{y}$ is not fixed, like $y_i^k$. – mavavilj Dec 8 '18 at 16:43
• I did not catch it in the first reading, but I think the issue is in this statement: 'so if the order of xs changes, then the weights will be assigned "based on different order"?' The order of $x$ changes, but the order of the inputs $x_1 ...x_n$ does not change. So the weights are applied in a uniform manner even though the order of the instances changes, the weight to input variable is constant. – Skiddles Dec 8 '18 at 16:48
• Ah ok. I was thinking of shuffling at a lower than required level. In that case this reminds a bit of the ideas in k-fold cross-validation/similar. upload.wikimedia.org/wikipedia/commons/1/1c/… – mavavilj Dec 8 '18 at 16:53
• That's a great comparison. – Skiddles Dec 8 '18 at 16:54

I agree with Skiddles, but would like to add an extreme example: let the training examples be ordered by class. Hence you only have training samples of one class in the data.

You could make a two class example. Assuming one hot encoding of the targets, gradient descent would push weights to make one output 1 and all others 0. There is no balancing between classes for that single step.

To convince yourself that sorting is a bad idea, just train MNIST on a sorted dataset and an unsorted one (I'll post training curves in roughly 15 hours, after work)