Unclear fact about difference between Gradient Descent to Stochastic Gradient Decent in wikipedia

Question

From wikipedia page it mentioned:

To economize on the computational cost at every iteration, stochastic gradient descent samples a subset of summand functions at every step. This is very effective in the case of large-scale machine learning problems

And later on it demonstrates the pseudo code with shuffle, and not sub-setting the samples. I don't get it how come applying shuffle improves the Gradient descent:

Can somebody shed some light on this issue?

Answer 1

That paragraph is incomplete and unclear indeed. Let's crack the difference with a concrete example: logistic regression.

The objective we want to minimize is:

$J_{train}(\theta)=\frac{1}{2m}\sum_{i=1}^{m}(h_{\theta}(x^{i})-y^{i})^{2}$

Notice how this loss formulation requires us to iterate trough all our data to sum the squared errors. Gradient descent does precisely that:

$\theta_{j} := \theta_{j} - \alpha\frac{1}{m}\sum_{i=1}^{m}(h_{\theta}(x^{i})-y^{i})x^{i}_{j}$

Also here, to compute a single descent step we are iterating through to all our data, while keep summing the gradients. This is why normal gradient descent is so memory inefficient.

One work around to this problem is to redefine our initial loss $J$ in order to allow us to perform a descent step without having to look at all our data. We usually call this new formulation cost:

$cost(\theta, (x^{i}, y^{i})) = \frac{1}{2}(h_{\theta}(x^{i})-y^{i})^{2}$

This allows us to rewrite also our descent step in a way that doesn't require to look at all our data.

$\theta_{j} := \theta_{j} - \alpha\frac{1}{2}(h_{\theta}(x^{i})-y^{i})x^{i}_{j}$

Since the sum now it's gone it means that we don't need to sum gradients or keep in memory extra stuff, so this is much more efficient. And this is basically Stochastic gradient descent.

Problem is that because we're updating on a fraction of our data at the time, order becomes relevant. If our data are ordered in some strange fashion, we'll risk to introduce biases in our parameters do to biases in the subset we selected to perform the update. And even if other subsets of data would normally account for that, now it's not the case anymore, cause we already performed an update step, and when applying our model to the new subset the parameters are therefore already biased. The only strategy we have to prevent this is precisely randomizing the order of our data.