Lecture 14 Fall 2025: Gradient Descent and Stochastic Gradient Descent transcript

Okay. So, what I want to do now is to talk about optimization. And this has come up a number of times. Um, and we're just going to talk about some of the basics. Okay. So, in particular today we're going to talk about basic convex optimization. And next time on Thursday we are going to talk about a very important non-convex optimization problem back propagation for training neural networks. Okay. So today I really want to get through some of the basics of convex optimization so that we can hit the ground running on back propagation on Thursday.

So in particular what we're interested in is the following. So our goal with optimization in general is to find some point W and I'm just going to call it W star. That is the argument that minimizes overall W. Some loss function L of W. And so this could be hinge loss plus squared uh norm regularizer like with an SVM. This could be squared error. This could be ridge regression. It could be any number of different things, but we've defined how we're going to measure how good a weight vector W is.

And now we want to find which weight vector minimizes that loss. And today we're going to focus on the setting where this function L is convex. And we touched on this very briefly in the context of le squares when we were talking about positive definite matrices but it's a much more general concept. So to define it more precisely, a function L is convex if if I look at that function and evaluate it at some W and that is greater than or equal to that function at some other point V plus the gradient of that function at W transpose times I just want to make sure I get my signs right w minus v and this has to be true for all w and v and I'm assuming for this that just like we've done with every example in this class we're considering all w's in pd- dimensional space.

So if we had more constraints on what W's could be, then this would change a little bit. We're just going to consider the case where we're um optimizing over all possible p-dimensional vectors. And so this is what makes a function convex. Now this is a abstract definition. So first let me just verbally say that this means that L is above all of its tangents. And this is something that we can show um in a plot. And I'm just going to give myself a lot of colors and space now to illustrate this.

Right. Here we go. Where did white go? No. All right. So, let's consider the example where L of W is equal to Y - XW which we've considered uh before where the columns of X are linearly independent. So this is a convex function as we talked about before and in this setting we know we've derived that the weight vector that solves this optimization problem is equal to xrpose x inverse xrpose y. Okay. But now what I want to do is I want to think about this definition of convexity in the context of this example.

So imagine that W is one-dimensional. So we just have one w here and then we are going to plot L of W. And here is my function. And so in this picture right here is W star. And now if I think about my definition of convexity, I should be able to choose two points. And I want this to yeah, I'm going to choose a point here that's my V and another point here which is some other W, not necessarily W star. And for V, I can look up here.

And this is L of V. And I can also look up here. And this is my loss at point W. Okay. So I've got two points and two losses. And now what I'm going to do is I'm going to draw a tangent line right here at V L of V. And so that tangent line looks like this. So in green I am plotting the function L of V plus the gradient. Did I do? Yeah. So, I'm sorry. Shoot. It's going to mess up my video. This is V here. Okay. L of V transpose W minus V.

So the slope of the green line is my gradient or derivative at V. So I've got this my tangent has the same slope as my function as tangents do. And I have then offset it by L of V. So it's the right height. So it's touching my function right there. And now for any point W, let's just call this thing F of W. So my green line is F of W. And remember we said that when L of W is convex that or maybe I'll call it FV of W then this loss L of W is going to be greater than or equal to this FV of W.

And so in this picture we are seeing that because what I've got right here at W, this is F V of W. And so I've drawn my tangent at point V. And now for any point W along here, my function in white, my loss is above that tangent. And this has to be true, like I said, for all V and W. So no matter where I choose this point V, no matter where I put my tangent, my function in white always has to be greater than the tangent.

Okay, so this is all actually true even when we don't have squared error loss. Um so this example is an example function that is um convex and where we know what war star is in terms of the definition of convexity. This picture is hopefully giving you a little bit of intuition about what that definition means. So we've said before that it roughly is Bshaped. And more formally when we talk about that we mean that no matter where I draw a tangent my function is going to be above that tangent.

And so I can also do something similar to this in three dimensions, though it's it's quite a bit harder to draw. So I could have a function like this. So this is supposed to be sort of a B-shaped function here. So here would be my W star. So my axes here, I've got W1 and weight 2. And my vertical axis is the loss of these two-dimensional weights. And there's some point in this plane W star that corresponds to the minimum.

And so again what I can do is I can choose any other point V and I can look at my function at V and then I can try to make a tangent plane at that point. This is where the drawing gets a little bit harder to see. But the point I'm trying to make is that when my function in white is convex, then when I draw that tangent plane, the whole function in white is above that orange tangent plane, no matter where I look at that tangent plane or where no matter where I look at the function.

In contrast, if I were to have a non-convex function, so over here I will draw I'll just do this in 1D. So I've got W and I've got nonconvex L of W. And so here's my function. So now if I were to look at a point, let's say here V, and I try to draw a tangent line to the function there. Then I'm looking at the derivative to choose my slope. And so I get my tangent function like this. And I can see that there are many places where my function is below that tangent.

And so this is not a convex function. Good. Okay. So now what we want to do is we want to say when our function is convex, how do we find the minimum of it? And what we are going to do first, first we're going to talk about gradient descent. Um, okay. So, we're going to consider settings where L is convex. people will use gradient descent even when L is not convex and we'll talk about that a little bit more at the end of the lecture.

Um and so most generally what we are going to do is initialize with some initial guess W and then I'm going to put in a superscript here of one where the superscript is going to correspond to my iteration. So at my first iteration, my guess of the optimum is W1. And then what I'm going to do is the following. So for t = 1 2 3 maybe forever. I'm going to update this guess. So I'm going to compute my weight vector for the t + one iteration by taking my weight vector at iteration t and making an adjustment and in particular by taking a step in the direction of the negative gradient.

So I take my loss function L and I compute its gradient with respect to W and I evaluate that gradient at wherever my current iterate is located. And that's really it. And then I look and I see if I should stop. So for instance, if wt and wt + one are close then I would stop. In this I have TOAO. TOAO is a parameter greater than zero. And we call this the step size or sometimes people will call it the learning rate. So the gradient L of of L evaluated at W is telling me in which direction to change my weight vector and tow is telling me how big of a step or how big of a change I should make.

So let's first look at a special case of this for our lease squares example just to be very concrete and then we will draw a picture of the iterates in a toy example. Okay, so we've got y - x w 2^ 2. And if we foil that out, we've got yranspose y - 2 um w transpose xrpose y + 2 w transpose xrpose xw. Okay, so this is our objective function and as we derived in the past the gradient of this function with respect to w was equal to -2 xrpose y + 2 xrpose x w.

Sorry, there's no two here. There we go. Okay, so this is our gradient. And so what we're going to do is we start with an initial guess W1. And then for t = 1 2 3 etc. Wt + 1 is going to equal wt minus tow. And now we plug in our gradient which is going to be -2 xrpose y + 2 xrpose x. And now we're evaluating our gradient at wt. We're at our current estimate. Or if it's easier, we can write this as w t + 1 is equal to wt + 2 tow xrpose y - 2 to xrpose x wt. t and then if wt and wt + 1 are sufficiently close we would stop.

Okay, so this is something that we talked about before and now we have this much more general expression for gradient descent. And if we make a plot of what's happening here where w is a scalar now and my vertical axis is l of w and so my function is this nice quadratic function and right here is my w star. This is the thing that I'm going after. Okay. So I'm going to start with some initial guess W1. And what am I going to do?

What I'm going to do is I'm going to compute my new guess W hat by first of all computing the gradient of my loss at this point and taking a step at this direction. So, in particular, at this point, my loss is sloped downwards. And that tells me that the way I need to adjust my weight is to move to the right in order to make it smaller. And I'm going to compute my gradient here. And that gradient is going to tell me how steep the slope is.

When the slope is steeper, I can take a larger step. And so, my new weight W2 would be for instance here. And so then what I would do is I would repeat this process. I would compute my gradient at this point. And then I would move in the direction that the gradient is telling me. So I'm still moving to the right, but my slope is a little bit shallower now, which means that I'm closer to the minimum. At the minimum, the slope is equal to zero.

Since I'm closer to the minimum, I'm going to be taking a smaller step. It's still scaled by toao, but it also depends on how big this slope is. And so, my next step is going to be in the same direction, but a slightly less big step size. And then again, I would repeat this. I would compute my slope at this point. It's a little bit shallower. It's telling me still to move to the right, etc. And I would keep on repeating this until basically the distance between successive iterates is super small which means that basically my gradient is close to zero.

So I'm not moving very much anymore. >> Yes. >> Yes. Excellent question. Can we ever overstep? Okay, here's my loss function and here is my initial point. All right. So now I can have different observations of what happens depending on different W. So I could have I'm sorry, TOAO. So I could have TOAO being I'll just make this red because it's bad. Towa is really big. And we're going to talk about how big is too big in a little bit.

So now I am correctly saying from here I need to go right. But I overstep and I overstep way too much. In fact, I go so far to the right that my loss function even increases. I'm in worse shape than I was before. And so that just continues and I diverge very bad. So I'm doing gradient descent, but I chose too big of a step size and so I don't actually find a minimum. So that's one possibility. Then I could have tao somewhere in the middle and I could have the situation that I drew on the other board.

But I could also have a situation that looks something for instance like this. So I am overstepping but I'm not overstepping too much and eventually I do find the minimum. So this is fine. This is not a problem. And then I could also have a towel that looks like that's very small. And then I get this. So I'm overstepping or sorry it's not very small. It's it's um it's too big but not so big that I diverge but still too big.

So this is so I've got yeah maybe wrong order medium big um so I have to do a lot of steps or similarly um I could have tow tiny and when tow is tiny I'm going like this all my steps are super close together. And so if I do it long enough, I will eventually hit the bottom. I don't diverge, but it takes forever. So, okay. So, these really make the electric company very happy. And so this is where people spend a lot of time thinking about well how do I choose a good step size or a good learning rate so that I first of all primarily don't diverge but also so that it doesn't take forever to converge.

I want to do it in a relatively small number of steps. And in fact, when we go beyond gradient descent in optimization classes that you might take after this class, they'll talk about ways in which you can try to in reduce the number of steps you need to take in order to reach the minimum or to get very close to the minimum. So there are a lot of things that you can do is that can exploit structure in your loss function that can help you find the minimum more quickly with fewer steps.

So yes, you can overstep. Overstepping is not necessarily a bad problem like we had in our yellow example. But if you overstep way too much, you diverge. If you overstep um too much but not way too much, then it can just take a really long time to converge. So there's a bit of a balancing act. in the lecture notes. We're not going to have time to go through it in class today, but we can show how big is too big. So, there's an upper bound on tow that we can derive explicitly for certain problems, including these squares, that tells us we need to be below that upper bound in order to ensure that we're going to find the minimum.

Um, and so I do encourage you to look at that because it's using a lot of the different things that we talked about in this class. Um, and has some really nice mathematics involved. Okay. more pictures. So like I said sometimes people will try to apply gradient descent to non-convex optimization problems. So for instance you have a loss function like this. So it can work, right? If I were to choose my W1 here and then do gradient descent, then I might see a series of iterates like this and I reach the bottom, no problem.

But if I had chosen to start let's say here and I do gradient descent then gradient descent is telling me to follow the direction of descent and I end up in a place that's a local minimum and not a global minimum. So this is a local minimum. So I started off by talking about convexity. And so the key point is if L of W is convex then we um for tow um not too large we are going to find [clears throat] the global minimum. no matter where we start.

So we don't have to really be worried. So in this case, this is the global minimum. And when we've got convexity, we don't have to worry about how we initialize. We're always going to wind up at a glob at a global minimum. Um if it's not convex though like in my picture then where you minimize or where you initialize will make a big difference. Okay. There's some additional illustrations and examples in the um lecture notes that I really encourage you to look at.

They're pretty. They also talk a little bit about how we can think about the um shape of the loss function. four le squares using the singular value decomposition that I think gives some nice intuition. But in the last few minutes here I want to talk about a core tool that we are going to use for back propagation and that is stochastic gradient descent. The idea is very simple. So we are going to consider the case where we can write our loss function L of W as being an average over a bunch of other little loss functions LI of W.

Let's say N of them. So for instance, this could be if L of W is just our squared error loss. We could write this as 1 / N the sum i = 1 to n. I do this right or I'm sorry if I lost function was 1 / n out here too of yi minus xirpose w^ squar and so in this case this is what we would call li i of w. So we're thinking about our overall loss as being a sum of little losses over all of our different samples. Okay, we're not really doing anything different.

But what stochastic gradient descent is going to do is the following. So first of all, regular gradient descent we can write in terms of these mini loss functions. So we've got wt + 1 is going to be wt minus tow. And now we're going to have divided by n sum i = 1 to n of the gradient of all of our little individual loss functions. Okay, this is equivalent. I'm just plugging in the fact that we've got multiple loss functions that add up to give us our overall loss function.

Okay. Um or just want to make sure I'm doing my one over instant. Yeah. Okay. So that's what regular gradient descent does. And now when we talk about stochastic gradient descent, what we're going to do is we're going to only use one sample at a time. So at iteration t, we are going to select a sample i subt. And then what we are going to do is we are going to update our weight vector wt + 1 to be wt minus toao times the gradient l i t of w at t.

So all we're doing is instead of doing gradient descent with all of our samples at each step with stochastic gradient descent, we're going to choose one sample and use it to update the weight vector. And then at the next iteration, we choose another sample and we use it to update the weight vector. Um, this can be helpful if we've got huge data sets. So for instance, when OpenAI is training Chat GPT's um neural network, right, they've got billions, maybe even trillions of training samples.

And so every time they want to update the wave factor, loading all of that into memory alone is a huge amount of computation. And so what they're doing is they are just loading a subset of the data into memory at a time and making updates based on that. Okay, so this can give us big computational savings. Um and so there's a couple of variants of this and when people yeah so uh let's see one version of this would be what I would call random permutations.

And by this what I mean is that every n iterations I'm going to reshuffle my samples. So for instance, if n were equal to three, so I've got three training samples, then my sequence of its might be equal to, you know, one, three, two. So I do three rounds. I hit each sample once in some random order. Then I'm going to reshuffle them again. Now I might get 3 1 I'm sorry 213. So that's my second epic or round across all of my samples.

Then I reshuffle again. Now I maybe I get 3 2 1. That's my next uh epic. And so what I'm doing is I'm making sure I'm hitting every sample exactly the same number of times, but I'm doing I'm I'm shuffling the order every round. So this is one common mode that people work in. Um, this is what I see a lot in practice when it comes to theory and proving these things converge. Um, and that you're actually going to find the minimizers of your loss.

It's much easier to work with a purely stochastic version. And so be how did I refer this? Yeah, just choose it T uniformly at random. And so for instance, when n is equal to three, my sequence of its might look like 3 1 2 2 2 1 2 3 etc. And so here because I'm every round is independent or the choice of sample that I use at each round is independent of all the other rounds. Theoretically it's a lot easier to analyze but in practice people maybe use it a little bit less often because it's possible that we use some training samples many more times than other training samples. um whereas the random perturbations or random permutations um give us um assurances that we will always see this each sample the same number of times.

Okay. So there's some additional notes in the lecture notes that are posted online include so online we've got um guidelines on towo and some theory about proving that these things actually converge. There's also information on the loss function geometry and the singular value decomposition that ties a lot of things together. And then in addition um mini batch uh optimization this is used quite a bit in training neural networks.

So with stochastic gradient descent, we're only looking at one sample at a time. With mini batch, you might say, "Oh, I want to look at 10 samples at a time." And so I kind of lay that out explicitly in the notes. Please do take a look at that because on Thursday, we are going to hit the ground running with back propagation for neural networks, which uses stochastic gradient descent. So make sure this is solid and I will see you all on Thursday.