Hi.
In this lecture, I'm going to talk about stochastic gradient
descent.
So recall gradient descent, which was the optimization
algorithm that we decided on for optimizing all our training
losses for classification and regression.
So recall that the training loss is
an average over all the examples in the training set of the per
example losses.
So gradient descent works as follows.
We're going to initialize the weight vector to 0,
and then we're going to repeat T times
and do the following update.
We're going to take the old weight vector
and subtract out the step size times the gradient
over the training loss.
And now this looks very simple.
But if you unpack what this gradient is,
it's actually the average over the gradients
of the per example losses.
So now imagine you have a data set with a million examples.
Computing the single gradient is going
to involve looping over all the million examples just
to get a single update, and then you take a step
and then you have to do it all over again.
So this is why gradient descent is slow,
because it requires going through all the training
examples just to make one update.
So what can we do about this?
So the answer is stochastic gradient descent.
So here is the same training loss function,
and stochastic descent is going to work as follows.
So we initialize the weight vectors to 0,
and then we iterate T times.
And now on each epoch, we're going
to loop over the training examples
and then perform an update on the individual losses.
OK, so here instead of going through the training set
and performing one update, we're going
to go through the training set.
And after each example, we're going to perform an update.
And this is going to be a lot faster in terms of having
the number of updates be large.
Of course, there is a trade-off because each
update itself is not going to be as high quality because it only
consists of one example as opposed to all the examples.
And that's it for stochastic gradient descent.
I want to talk about one small note, which is the step size.
So recall that update includes a step size which
determines how far in the direction of the gradient
or away from the gradient do you want to move.
OK, so what should eta be?
And in general, there's not really a one satisfying answer
to this.
And it's usually a hyperparameter
that has to be tuned via trial and error.
But here are some general guidance here.
So the step size has to be greater or equal to 0.
And if it is small, that means you're
taking little, little steps.
But that means your algorithm is going
to be more stable and less likely to bounce around.
And as you increase eta larger and larger,
then you're taking more aggressive steps
so you can move faster but perhaps at the risk of being
a bit more unstable.
So two typical strategies for setting a step size.
One is using just a constant step size.
We've used, so far, eta equals 0.1--
kind of an arbitrary number--
or you can do a decreasing step size
rate, where eta is 1 over the number of updates
that you've made.
And the intuition here is that, in the beginning,
you're far away from the optimum,
so you're going to move quickly.
You want to move quickly.
But as soon as you start getting close to the optimum,
you want to slow down.
So now let us explore stochastic gradient descent in Python.
I'm going to code it up and see what happens, OK?
So remember last time, we did gradient descent.
So I'm going to copy this code over.
DescentHinge-- sorry, stochasticGradientDescent.
And what we're going to do is modify this code
to make it do stochastic gradient descent.
OK, so just recall, last time, we
set up some training examples.
We defined the loss function, and then we
had this generic optimization algorithm.
So now to really tell the difference
between gradient descent and stochastic gradient descent,
I'm going to make a larger data set.
And I'm going to do it in a way so that it's large
but it's structured so we know what the right answer is.
Because, otherwise, how can we verify it did the right thing?
To do this-- this is kind of just a general trick--
is that you kind of generate synthetic data from kind
of a ground truth, and then you try
to recover that ground truth.
So suppose we had some true weight vector.
This is our secret code, which is unknown to the learning
algorithm, but we hope that learning algorithm will recover
this, and then we're going to define a function called
generate which uses this trueW to generate an example.
So here I'm going to generate x, and I'm going to just sample
randomly a five-dimensional weight vector--
oh, sorry, an input point, and then I'm going to set y to be
trueW.dot(x).
So the examples I'm going to generate
are generated from the true weight vector,
and then I'm just going to add some noise.
Do randn, OK?
And then I'm going to set the training examples to be just
generate for, let's say, one--
let's do 1 million examples.
That's a lot of examples.
All right, so let's see what this data looks like.
So I'm going to print out x and y
and just to see what is coming out--
oops, I had a typo here.
OK, so here is the data set that we are going to train on.
So, example, x is a five-dimensional vector,
and the output is a scalar.
A lot of examples here.
All right, so I need to update the feature vector to be just
x, the identity, and here I'm going to-- the initial weight
vector has to match the dimensionality
of the true weight vector, and then everything
else, the training loss and gradient,
I'm going to leave alone, OK?
So now let's uncomment this line and let's run gradient descent.
Let's see what happens here.
OK, so it's going to generate the data.
And now to compute a single gradient,
it has to enumerate over one million examples.
So this is going to be quite slow.
I'll finish the first epoch, and it has some values.
And then the second epoch, and it seems
like it's making some progress.
Remember, we want to see if this can hit 1, 2, 3, 4, 5.
The loss is going down, which is good,
and it seems like it's moving in the right direction.
But it's pretty slow, and I'm here
so I'm just going to stop it there because I
don't want to wait forever.
OK, so now let's do stochastic gradient descent.
So first, I need to change the interface because gradient
descent only had access to F and the gradient of F.
And now stochastic gradient descent
needs to assess individual losses.
So what I'm going to do is I'm going to define a stochastic--
or actually I just call this the loss of w.
I'm going to use i here to denote an index into one
of these terms and the sum.
So what the loss is going to be is
it's just going to be one of these terms.
And the term I'm going to select out
is just the ith data point, OK?
And similarly, the gradient of the loss
is going to be just the gradient but for the ith data point.
And this also takes in the index i.
So now if I feed in i for various values,
I can access the loss and the gradient of that loss
function for any given point vector.
All right, so now let's go over to the optimization algorithm
and let me do stochastic gradient descent.
OK, so I'm going to call this stochasticGradientDescent,
and I'm going to call this--
just to distinguish things, I'm going
to use lowercase f for individual components
of an objective function.
OK, so I'm going to initialize the weight vector.
I'm going to use a different step size here, just for fun.
I'm going to initialize with 1.0--
actually, let me do this instead.
I'm going to set the step size to be
1 over the square root of number of updates.
And each time I do an update, I'm
going to increase the number of updates.
So, actually, let me do it in this order.
OK, so the number of updates starts at 0.
And then remember in stochastic gradient descent,
I'm going to loop over the number of components
of the objective function.
So 1-- 0 to n minus 1.
So another thing I'm going to have
to pass in is the number of components
that I'm going to use to index into F.
And so now this is f of w, 1, gradient f of w, i,
and then I'm going to move everything inward.
OK, so now to call this function,
I'm going to run stochastic gradient descent.
And with just the loss and the gradient of the loss,
I'm going to pass in n, which is a number of training examples
and initial weight vector, OK?
So let's just review what's going on here.
So stochastic gradient descent takes a function
which can access individual components of the objective,
initialize the weights, and then iterate some number of times.
And in each epoch, it's going to loop over all the examples,
compute the value, compute the gradient,
and then it's going to do a gradient update.
And here I'm using a step size, which
is 1 over the number of updates that I've made so far.
OK, so let's see stochastic gradient descent in action now.
I have two returns here, so there's a syntax error.
Let me fix that.
So now it's going through 1 million examples-- oh, I
need to import math as well.
So it's going to loop over 1 million examples,
but each example it's going to perform an update.
And so when it prints out, it's going
to have already taken 1 million steps of stochastic gradient
descent.
And look at what happened here.
So after the first step, it's already
quite close to 1, 2, 3, 4, 5.
And objective in the--
I guess the function of value doesn't really
mean as much because it's only of an individual point.
But you can see that the weight vector
is converging quite nicely.
And this shows that stochastic gradient descent, just even
sometimes with one pass of a training data,
can get much closer to the optimum
than if you were to do many, many rounds
of gradient descent.
OK, so that was stochastic gradient descent in Python.
So let's summarize here.
So we want to optimize this training loss, which
is an average over the per example losses,
and we looked at gradient descent,
which takes a step on the gradient of the training loss.
And we also looked at stochastic gradient descent,
which picked up individual examples and updated
on computing-- after computing the gradient
of individual examples.
And now on this example, we've shown that stochastic gradient
descents wins.
And the key idea behind stochastic updates
is that it's not about quality.
It's about quantity.
So maybe not a general life lesson,
but it seems like, in this case, it is more wise to keep in mind
what you're trying to do, which is optimize this objective,
rather than compute the gradient, which
is only a means to an end.
OK, so that concludes the module on stochastic gradient descent.
Thanks for listening.