Stochastic gradient descent and different approaches

Question

While dealing with stochastic gradient descent, I got confused by several sources which explained it quite differently.

1. One source explained stochastic gradient descent as standard gradient descent approach but with substantial smaller training set.
2. The other approach first sums the gradients of all training set and then multiplies with learning rate and updates it. $Q_{t+1}<-Q_t - \tau * \frac{n}{|S|}*\sum_{j\in S}\nabla L_j(Q_t)$

What is the difference? and How does it work with matrices since I take just couple of training examples? (see example below)

Here is an example: I have sparse matrix M with user x movies where the value in the matrix represents how much the user rates the movie. I decomposed it into matrices P and Q and using stochastic gradient descent I want to optimize P and Q by minimizing the loss function. Each value of M can be reconstructed by multiplying vector of Q and P.

Let's say I take batches of 10 so it means I take just 10 values from matrix M and respective rows and columns of P and Q which I will optimize. If I take the second approach there is sum of gradients of all point and then I do the update but how can I sum those vectors since they do not correspond to the same place in matrix Q or P? In this case, should I then just make new P and Q just with vectors that corresponds to taken values of M? but then it does not make sense because I should optimize the whole Q and P matrices right?

I hope I made it clear enough.

Answer 1

I think you're actually asking two separate questions: 1) What is stochastic gradient descent (SGD)? and 2) how do I find the matrices $P$ and $Q$ in the matrix factorization of $M$?

For question 1, I don't think either of your explanations is correct. (Explanation 2 sounds to me like normal (batch) gradient descent, although I found your description a little confusing.)

Regardless, both the Wikipedia article and Chapter 5 of the Deep Learning book provides good explanations of SGD. In many machine learning problems, the loss function, $L$ can be decomposed as the sum of losses for individual training examples:

\begin{equation} L(x, y; \theta) = \sum\limits_{i=1}^{m} L(x^{(i)}, y^{(i)}; \theta) \end{equation}

Therefore, in normal gradient descent, the number of terms in the gradient scales with the number of training examples, $m$. Computing this term can be very costly as $m$ grows large. In stochastic gradient descent, we instead approximate the gradient by using a "mini-batch" of samples to compute it. So, instead of

\begin{equation} \nabla_{\theta} L(x, y; \theta) = \sum\limits_{i=1}^{m} \nabla_{\theta} L(x^{(i)}, y^{(i)}; \theta) \end{equation}

we use

\begin{equation} \nabla_{\theta} L(x, y; \theta) \approx \sum\limits_{i=1}^{m_{mini}} \nabla_{\theta} L(x^{(i)}, y^{(i)}; \theta) \end{equation}

where $m_{mini} \ll m$. The key point is that, when running SGD, we randomly shuffle the training examples and iterate through different minibatches during training. So, SGD is not equivalent to normal (batch) gradient descent for a smaller training set. In SGD, we train on all of the training examples, but it just takes us $m/m_{mini}$ iterations to get there. For instance, if $m_{mini} = 1$, and we took $m$ SGD steps, each step would correspond to using a single training example to approximate the gradient, and all $m$ steps would involve using a different training example.

For question 2, solving for the parameters in matrix factorization is usually done via alternating least squares (ALS) or SGD. Here's an excellent blog post explaining how both techniques work in the context of matrix factorization. The post is too long to summarize, but the author carefully and slowly derives all of the relevant equations from scratch, so I recommend you read it!