What's the function that SGD takes to calculate the gradient?

Question

I'm struggling to fully understand the stochastic gradient descent algorithm. I know that gradient descent allows you to find the local minimum of a function. What I don't know is what exactly that function IS. More specifically, the algorithm should work by initializing the network with random weights. Then, if I'm not mistaken, it forward-propagates $n$ times (where $n$ is the mini-batch size). At this point, I've no idea about what function should I search for, with over hundreds of neurons each having hundreds of parameters.

Answer 1

Welcome to AI Stack exchange!

You're right, as the network is initialised randomly, the resultant function is essentially impossible to get your head around. This is because most of the time the network has >4 dimensions (4 can be graphed with some effort and a lot of color), and as such is literally beyond human comprehension via graphing.

So what do we do? Well, conveniently, it is possible to find the gradient of segments of a function, without having to know the entirety of the function itself (it's worth noting that it actually is possible to find the resultant function and with a lot of effort find it's derivative. This proves to be much more work than it's worth though, as we don't need the general derivative that tells us what the gradient is for whatever input we give it, we only need the derivative at the specific input we just fed through the network).

This might be hard to understand, but if you're familiar with the chain rule, it might make a bit more sense. The chain rule essentially allows you to split a function into components, and find the gradient of those specific components. By combining all of that, you end up with some nice gradients at each weight/bias with respect to the loss function. Take the negative of the gradient, and you now have the change required to decrease the loss function.

This is obviously quite hard to understand without an example, so here's the best one I've ever found, that helped me very much.

Also, as a side note, the whole mini batch thing is used to minimise catastrophic forgetting (where the network begins to "unlearn" old inputs). To deal with minibatchs, what you do is take input individually, then find the gradient for all weights and bias' for that specific input and remember the changes you want to make. Do that for all inputs in the minibatch, then finally add all the changes together to get the resultant best change for each weight and bias. Only then do you update the weights and bias'.

Let me know if you have any further questions

Answer 2

I know that gradient descent allows you to find the local minimum of a function. What I don't know is what exactly that function IS.

It's usually called the loss function (and, in general, objective function) and often denoted as $\mathcal{L}$ or $L$ (or something like that, i.e. it is not really important how you denote it). The specific function used as a loss function depends on the problem (ask another question if you want to know the details). For example, in the case of regression, the loss function may be the mean squared error. In classification, the loss function may be the cross-entropy. However, the most important thing to note is that the loss function depends on the parameters of the neural network (NN), so you can differentiate it with respect to the parameters of the NN (i.e. you can take the partial derivative of the loss function with respect to each of the parameters of the NN).

Let's take the example of the mean squared error function, which is defined as

$$ \mathcal{L}(\boldsymbol{\theta}) ={\frac {1}{n}}\sum _{i=1}^{n}(y_i-f_{\boldsymbol{\theta}}(x_i))^{2}. $$ where $n$ is the number of training examples used (the batch size), $y_i$ is the true class (or target) of the input example $x_i$ and $f(x_i)$ is the prediction of the neural network $f_{\boldsymbol{\theta}}$ with parameters (or weights) $\boldsymbol{\theta} = [\theta_i, \dots, \theta_M] \in \mathbb{R}^M$, where $M$ is the number of parameters.

Given the loss function $\mathcal{L}(\boldsymbol{\theta})$, we can now take the derivative of $\mathcal{L}$, with respect to $\boldsymbol{\theta}$, using the famous back-propagation (BP) algorithm, which essentially applies the chain rule of calculus. The BP algorithm produces the gradient of the loss function $\mathcal{L}(\boldsymbol{\theta})$. The gradient can be denoted as $\nabla \mathcal{L}(\boldsymbol{\theta})$ and it contains the partial derivatives of $\mathcal{L}(\boldsymbol{\theta})$ with respect to each parameter $\theta_i$, that is, $\nabla \mathcal{L}(\boldsymbol{\theta}) = \left[ \frac{\partial \mathcal{L}(\boldsymbol{\theta})}{\partial \theta_i}, \dots, \frac{\partial \mathcal{L}(\boldsymbol{\theta})}{\partial \theta_M} \right] \in \mathbb{R}^M$. (If you want to know the details of the back-propagation algorithm, you should ask another question, but make sure you get informed first, because it may not be easy to fully explain it in an answer.)

Afterward, we just apply the gradient descent step

$$ \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \gamma \nabla \mathcal{L}(\boldsymbol{\theta}) $$

where $\gamma \in \mathbb{R}$ is often called the learning rate and is used to weight the contribution of the gradient $\nabla \mathcal{L}(\boldsymbol{\theta})$ to the new values of the parameters, and $\leftarrow$ represents an assignment (like in programming).

It is worth emphasizing that both $\boldsymbol{\theta}$ and $\nabla \mathcal{L}(\boldsymbol{\theta})$ are vectors and have the same dimensionality ($M$).

Have also a look at this answer where I explain the difference between gradient descent and stochastic gradient descent.

Answer 3

After I've learned a little bit more about the topic, I think I figured out the exact sequence of the algorithm. So, here's my own answer. Please, correct me if I'm wrong.

1. Give an input, forward-propagate it, and generate an output

2. For each output neuron: for each weight connected to the neuron: Given the function C = f(w) (which represents the cost in function to the weight value), calculate the derivative of that function at the point where the current weight actually is)

3. Calculate the actual derivative of all the weights by combining all the partial derivatives in respect to the weight: now you have a gradient of the weights

4. Repeat this process to calculate the gradient for each of the batch elements. If you have a batch size of 8, then you'll have 8 gradients.

5. Find the average gradient ((gradient_1+gradient2+gradient3...)/n_gradients)

6. Move the weights of that gradient

Am I right? How does this apply to deeper layers?