25. Stochastic Gradient Descent
2.71M subscribers
SUBSCRIBED
MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning, Spring 2018 Instructor: Suvrit Sra View the complete course: https://ocw.mit.edu/18-065S18YouTube Playlist: https://www.youtube.com/playlist?list...Professor Suvrit Sra gives this guest lecture on stochastic gradient descent (SGD), which randomly selects a minibatch of data at each step. The SGD is still the primary method for training large-scale machine learning systems. License: Creative Commons BY-NC-SA More information at https://ocw.mit.edu/termsMore courses at https://ocw.mit.edu
SHOW LESS
00:00
00:01
The following content is provided under a Creative
00:03
Commons license.
00:05
Your support will help MIT OpenCourseWare
00:07
continue to offer high quality educational resources for free.
00:11
To make a donation or to view additional materials
00:14
from hundreds of MIT courses, visit MIT OpenCourseWare
00:18
at ocw.mit.edu.
00:19
00:22
PROFESSOR STRANG: [INAUDIBLE] Professor Suvrit
00:24
Sra from EECS who taught 6.036 and the graduate version.
00:31
And maybe some of you had him in one or other of those classes.
00:37
So he graciously agreed to come today
00:41
and to talk about Stochastic Gradient Descent, SGD.
00:45
00:48
And it's terrific.
00:51
Yeah, yeah.
00:52
So we're not quite at 1:05, but close.
00:56
01:00
If everything is ready, then we're off.
01:03
OK.
01:04
Good.
01:06
PROFESSOR SRA: And your cutoff is like 1:55?
01:09
PROFESSOR STRANG: Yeah.
01:10
PROFESSOR SRA: OK.
01:11
PROFESSOR STRANG: But this is not a sharp cutoff.
01:15
PROFESSOR SRA: Why is there [INAUDIBLE] fluctuation?
01:18
PROFESSOR STRANG: There you go.
01:21
PROFESSOR SRA: Somebody changed their resolution it seems,
01:24
but that's fine.
01:27
It doesn't bother us.
01:29
So I'm going to tell you about, let's say, one of the most
01:34
ancient optimization methods, much
01:36
simpler than, in fact, the more advanced methods
01:40
you have already seen in class.
01:43
And interestingly, this more ancient method
01:47
remains "the" method for training large scale machine
01:51
learning systems.
01:55
So there's a little bit of history around that.
01:57
I'm not going to go too much into the history.
02:00
But the bottom line, which probably Gil
02:04
has also mentioned to you in class,
02:08
that at least four large data science problems, in the end,
02:13
stuff reduces to solving an optimization problem.
02:17
And in current times these optimization problems
02:19
are pretty large.
02:21
So people actually started liking stuff
02:25
like gradient descent, which was invented by Cauchy back
02:29
in the day.
02:30
And this is how I'm writing the abstract problem.
02:35
And what I want to see is--
02:37
OK, is it fitting on the page?
02:38
This is my implementation in MATLAB of gradient descent,
02:42
just to set the stage that this stuff really looks simple.
02:46
You've already seen gradient descent.
02:48
And today, essentially, in a nutshell,
02:53
what really changes in this implementation
02:56
of gradient descent is this part.
02:59
That's it.
03:02
So you've seen gradient descent.
03:04
I'm only going to change this one line.
03:06
And the change of that one line, surprisingly,
03:10
is driving all the deep learning tool boxes
03:13
and all of large scale machine learning, et cetera.
03:16
This is an oversimplification, but morally, that's it.
03:20
So let's look at what's happening.
03:23
So I will become very concrete pretty soon.
03:28
But abstractly, what I want you to look at
03:32
is the kinds of optimization problems
03:35
we are solving in machine learning.
03:38
And I'll give you very concrete examples of these optimization
03:42
problems so that you can relate to them better.
03:46
But I'm just writing this as the key topic,
03:49
that all the optimization problems
03:52
that I'm going to talk about today, they look like that.
03:55
You're trying to find an x over a cost
03:59
function, where the cost function can
04:01
be written as a sum.
04:04
In modern day machine learning parlance
04:06
these are also called finite sum problems,
04:08
in case you run into that term.
04:11
And they just call it finite because n is finite here.
04:15
In pure optimization theory parlance,
04:18
n can actually go to infinity.
04:20
And then they're called stochastic optimization
04:22
problems--
04:23
just for terminology, if while searching the internet
04:27
you run into some such terminology
04:29
so you kind of know what it means.
04:32
So here is our setup in machine learning.
04:37
We have a bunch of training data.
04:39
04:42
On this slide, I'm calling x1 through xn.
04:47
These are the training data, the raw features.
04:50
Later, actually, I'll stop writing x for them
04:52
and write them with the letter a.
04:54
But hopefully, that's OK.
04:57
So x1 through xn, these could be just raw images, for instance,
05:02
in ImageNet or some other image data set.
05:05
They could be text documents.
05:06
They could be anything.
05:08
y1 through yn, in classical machine learning,
05:11
think of them as plus minus 1 labels--
05:14
cat, not cat-- or in a regression
05:17
setup as some real number.
05:20
So that's our training data.
05:21
We have d dimensional raw vectors, n of those.
05:26
And we have corresponding labels which
05:28
can be either plus or minus 1 in a classification setting
05:32
or a real number in a regression setting.
05:34
It's kind of immaterial for my lecture right now.
05:37
So that's the input.
05:39
And whenever anybody says large scale machine learning,
05:44
what do we really mean?
05:47
What we mean is that both n and d can be large.
05:52
So what does that mean in words?
05:54
That n is the number of training data points.
05:58
So n could be, these days, what?
06:00
A million, 10 million, 100 million,
06:02
depends on how big computers and data sets you've got.
06:04
So n can be huge.
06:06
d, the dimensionality, the vectors
06:09
that we are working with--
06:10
the raw vectors-- that can also be pretty large.
06:13
Think of x is an image.
06:16
If it's a megapixel image, wow, d's like a million already.
06:21
If you are somebody like Criteo or Facebook or Google,
06:25
and your serving web advertisements, d--
06:29
these are the features--
06:31
could be like in several hundred million, even
06:34
a billion, where they encode all sorts of nasty stuff
06:38
and information they collect about you as users.
06:41
So many nasty things they can collect, right?
06:44
So d and n are huge.
06:46
And it's because both d and n are huge,
06:49
we are interested in thinking of optimization
06:52
methods for large scale machine learning that can
06:55
handle such big d and n.
06:59
And this is driving a lot of research
07:00
on some theoretical computer science, including
07:02
the search for sublinear time algorithms
07:05
and all sorts of data structures and hashing tricks just
07:08
to deal with these two quantities.
07:12
So here is an example--
07:13
super toy example.
07:16
And I hope really that I can squeeze
07:18
in a little bit of proof later on towards the end.
07:22
I'll take a vote here in class to see if you are interested.
07:24
Let's look at the most classic question,
07:27
least squares regression.
07:30
A is a matrix of observations-- or sorry, measurements. b
07:34
are the observations.
07:36
You're trying to solve Ax minus b whole square.
07:38
Of course, a linear system of equations,
07:41
the most classical problem in linear algebra,
07:42
can also be written like that, let's say.
07:47
This can be expanded.
07:49
Hopefully, you are comfortable with this norm.
07:55
So x2 squared, this is just defined
07:58
as that's the definition of that notation.
08:02
But I'll just write it only once now.
08:06
I hope you are fully familiar with that.
08:09
So by expanding that, I managed to write least squares problem
08:13
in terms of what I call the finite sum right.
08:18
So it's just going over all the roles in a.
08:20
The end roles, let's say.
08:22
So that's the classical least squares problem.
08:25
It assumes this finite sum form that we care about.
08:31
Another random example is something called Lasso.
08:34
Maybe if anybody of you has played with machine learning
08:37
or statistics toolkits, you may have
08:39
seen something called Lasso.
08:40
Lasso is essentially least squares,
08:42
but there's another simple term at the end.
08:47
That again, looks like f of i.
08:50
Support vector machines, once a workhorse of--
08:55
there's still a workhorse horse of people
08:57
who work with small to medium sized data.
09:01
Deep learning stuff requires huge amount of data.
09:04
If you have small to medium amount of data,
09:06
logistic regression support, vector machines, trees, et
09:08
cetera, this will be your first go to methods.
09:10
They are still very widely used.
09:13
These problems are, again, written in terms
09:15
of a loss over training data.
09:19
So this again, has this awesome format, which
09:22
I'll just now record here.
09:25
I may not even need to repeat it.
09:26
Sometimes I write it with a normalization--
09:30
you may wonder at some point, why--
09:33
as that finite sum problem.
09:36
And maybe the example that you wanted to see
09:40
is something like that.
09:45
So deep neural networks that are very popular these days,
09:49
they are just yet another example
09:51
of this finite sum problem.
09:53
How are they an example of that?
09:56
So you have n training data points,
09:59
there's a neural network loss, like cross entropy,
10:02
or what have you, squared loss, cross-- any kind of loss.
10:06
yi's are the labels--
10:08
cat not cat, or maybe a multiclass.
10:12
And then you have a transfer function
10:15
called a deep neural network which takes raw images as input
10:19
and generates a prediction whether this is a dog or not.
10:23
That whole thing I'm just calling DNN.
10:26
So it's a function of ai's which are the training data.
10:29
X are the [INAUDIBLE] matrices of the neural network,
10:32
so I've just compressed the whole neural network
10:34
into this notation.
10:35
Once again, it's nothing but an instance of that finite sum.
10:41
So that fi in there captures the entire neural network
10:45
architecture.
10:48
But mathematically, it's still just one particular instance
10:51
of this finite sum problem.
10:55
And then people who do a lot of statistics, maximum likelihood
10:58
estimation.
11:01
This is log likelihood over n observations.
11:05
You want to maximize log likelihood.
11:08
Once again, just a finite sum.
11:10
So pretty much most of the problems
11:13
that we're interested in machine learning and statistics,
11:17
when I write them down as an optimization problem,
11:20
they look like these finite sum problems.
11:23
And that's the reason to develop specialized optimization
11:28
procedures to solve such finite some problems.
11:32
And that's where SGD comes in.
11:35
OK.
11:36
So that's kind of just the backdrop.
11:37
Let's look at now how to go about solving these problems.
11:41
11:45
So hopefully this iteration is familiar to you--
11:51
gradient descent, right?
11:53
OK.
11:54
So just for notation, f of x refers
12:02
to that entire summation.
12:04
F sub i of x refers to a single component.
12:08
So if you were to try to solve--
12:10
that is, to minimize this cost function, neural network, SVM,
12:14
what have you using gradient descent,
12:18
that's what one iteration would look like.
12:22
Because it's a finite sum, gradients are linear operators.
12:26
Gradient of the sum is the sum of the gradient--
12:29
that's gradient descent for you.
12:30
12:34
And now, I'll just ask a rhetoric question
12:36
that, if you put yourself in the shoes of you're
12:38
[INAUDIBLE] algorithm designers, some things that you
12:42
may want to think about-- what may you
12:44
not like about this iteration, given that big n, big d story
12:48
that I told you?
12:50
So anybody have any reservations or about
12:53
drawbacks of this iteration?
12:55
Any comments?
12:57
AUDIENCE: It's a pretty big sum.
13:00
PROFESSOR SRA: It's a pretty big sum.
13:02
Especially if n is say, a billion
13:04
on some bigger, [INAUDIBLE] number.
13:07
That is definitely a big drawback.
13:09
13:12
Because that is the prime drawback for large scale,
13:15
that n be huge.
13:16
There can be variety of other drawbacks.
13:19
Some of those you may have seen previously
13:21
when people compare whether to the gradient or to do Newton,
13:24
et.
13:24
Cetera but for the purpose of today, for finite sums,
13:29
the big drawback is computing gradient at a single point--
13:34
there's a subscript xk missing there--
13:37
involves computing the gradient of that entire sum.
13:40
That sum is some is huge.
13:42
So getting a single gradient to do
13:45
a single step of gradient descent for a large data set
13:49
could take you hours or days.
13:51
13:54
So that's a major drawback.
13:56
But then if you identify that drawback,
13:58
anybody have any ideas how to counter
14:03
that drawback, at least, say, purely from an engineering
14:06
perspective?
14:07
14:10
I heard something.
14:10
Can you speak up?
14:13
AUDIENCE: [INAUDIBLE]
14:15
PROFESSOR SRA: Using some kind of badge?
14:17
AUDIENCE: Yeah.
14:18
PROFESSOR SRA: You are well ahead of my slides.
14:21
We are coming to that.
14:23
And maybe somebody else has, essentially, the same idea.
14:26
Anybody want to suggest how to circumvent that big n
14:30
stuff in there?
14:32
Anything-- suppose you are implementing this.
14:34
What would you do?
14:35
14:38
AUDIENCE: One example at a time.
14:40
PROFESSOR SRA: One example at a time.
14:43
AUDIENCE: [INAUDIBLE] a random sample full set of n.
14:47
PROFESSOR SRA: Random sample of the full n.
14:49
So these are all excellent ideas.
14:51
And hence, you folks in the class
14:55
have discovered the most important method
14:57
for optimizing machine learning problems,
14:59
sitting here in a few moments.
15:01
Isn't that great?
15:03
So the part that is missing is of course to make sense of,
15:06
does this idea work?
15:07
Why does it work?
15:09
So this idea is really at the heart of stochastic gradient
15:14
descent.
15:16
So let's see.
15:19
Maybe I can show you an example, actually, that I--
15:22
15:25
I'll show you a simulation I found on somebody's nice web
15:29
page about that.
15:33
So exactly your idea, just put in slight mathematical
15:37
notation, that what if at each iteration,
15:41
we randomly pick some integer, i k out of the n training data
15:46
points, and we instead just perform this update.
15:51
15:56
So instead of using the full gradient,
16:02
you just compute the gradient of a single randomly chosen data
16:05
point.
16:07
So what have you done with that?
16:09
One iteration is now n times faster.
16:11
If n were a million or a billion wow, that's super fast.
16:17
But why should this work right?
16:18
16:21
I could have done many other things.
16:23
I could have not done any update and just output the 0 vector.
16:28
That would take even less time.
16:30
That's also an idea.
16:31
It's a bad idea, but it's an idea in a similar league.
16:34
I could have done a variety of other things.
16:36
Why would you think that just replacing that sum with just
16:40
one random example may work?
16:41
16:44
Let's see a little bit more about that.
16:48
So of course, it's n times faster,
16:53
and the key question for us here, right now--
16:55
the scientific question-- is does this make sense?
17:00
It makes great engineering sense.
17:02
Does it make algorithmic or mathematical sense?
17:04
17:07
So this idea of doing stuff in the stochastic manner
17:11
was actually originally proposed by Robbins and Monro,
17:14
somewhere, I think, around 1951.
17:16
And that's the most advanced method
17:18
that we are essentially using currently.
17:22
So I'll show you that this idea makes sense.
17:25
But maybe let's first just look at a comparison of SGD
17:30
with gradient descent in this guy's simulation.
17:34
17:37
So this is that MATLAB code of gradient descent,
17:42
and this is just a simulation of gradient descent.
17:47
As you pick a different step size, that gamma in there,
17:51
you move towards the optimum.
17:53
If the step size is small, you make many small steps,
17:58
and you keep making slow progress, and you reach there.
18:02
That's for a well-conditioned problem
18:04
and an ill-conditioned problem.
18:06
It takes you even larger.
18:08
In a neural network type problem which is nonconvex,
18:11
you have to typically work with smaller step sizes.
18:14
And if you take bigger ones, you can get crazy oscillations.
18:16
But that's gradient descent.
18:19
In comparison, let's hope that this loads correctly.
18:26
Well, there's even a picture of Robbins,
18:28
who was a co-discoverer of the stochastic gradient method.
18:31
There's a nice simulation, that instead
18:34
of making that kind of deterministic descent--
18:38
after all, gradient descent is called "gradient descent."
18:43
At every step it descends-- it decreases the cost function.
18:48
Stochastic gradient descent is actually a misnomer.
18:52
At every step it doesn't do any descent.
18:54
It does not decrease the cost function.
18:56
So you see, at every step, those are the contours of the cost
18:59
function.
19:00
Sometimes it goes up, sometimes it goes down.
19:02
It fluctuates around, but it kind of stochastically still
19:06
seems to be making progress towards the optimum.
19:10
And stochastic gradient descent, because it's not
19:14
using exact gradients, just working
19:16
with these random examples, it actually
19:20
is much more sensitive to step sizes.
19:24
And you can see, as I increase the step size, its behavior.
19:29
This is actually full simulation for [INAUDIBLE] problem.
19:32
So initially, what I want you to notice is--
19:36
let me go through this a few times--
19:40
keep looking at what patterns you may notice in how
19:44
that line is fluctuating.
19:47
Hopefully this is big enough for everybody to see.
19:50
So this slider that I'm shifting is just the step size.
19:55
So let me just remind you, in case you forgot, the iteration.
19:58
We are running x k plus 1 is x k minus some eta k--
20:04
It's called alpha there--
20:06
times some randomly chosen data point.
20:11
You compute its gradient.
20:13
This is SGD.
20:14
That's what we are running.
20:18
And we threw away tons of information.
20:21
We didn't use the full gradient.
20:22
We're just using this crude gradient.
20:27
So this process is very sensitive
20:28
to the other parameter in the system, which is the step size.
20:32
Much more sensitive than gradient descent, in fact.
20:34
And let's see.
20:35
As I vary the step size, see if you
20:38
can notice some patterns on how it
20:42
tries to go towards an optimum.
20:44
20:59
There's a zoomed in version, also, of this later, here.
21:02
21:05
I'll come to that shortly.
21:08
I'll repeat again, and then I'll ask you for your observations--
21:11
if you notice some patterns.
21:12
21:15
I don't know if they're necessarily apparent.
21:16
That's the thing with patterns.
21:18
Because I know the answer, so I see the pattern.
21:20
If you don't know the answer, you may or may not
21:22
see the pattern.
21:22
But I want to see if you actually see the pattern as I
21:26
change the step size.
21:28
So maybe that was enough simulation.
21:31
Anybody have any comments on what kind of pattern
21:33
you may have observed?
21:34
Yep.
21:35
AUDIENCE: It seems like the clustering in the middle
21:37
is getting larger and more widespread.
21:39
PROFESSOR SRA: Yeah, definitely.
21:40
That's a great observation.
21:43
Any other comments?
21:43
21:49
There's one more interesting thing happening here,
21:52
which is a very, very typical thing for SGD,
21:56
and one of the reasons why people love SGD.
21:59
Let me do that once again briefly.
22:03
OK, this is tiny step size--
22:05
almost zero.
22:07
Close to zero-- it's not exactly zero.
22:10
So you see what happens for a very tiny step size?
22:14
It doesn't look that stochastic, right?
22:16
But that's kind of obvious from there if eta k is very tiny,
22:21
you'll hardly make any move.
22:24
So things will look very stable.
22:28
And in fact, the speed at which stochastic gradient converges,
22:31
that's extremely sensitive to how you pick the step size.
22:34
It's still an open research problem
22:35
to come up with the best way to pick step sizes.
22:37
So it's even that simple, it doesn't mean it's trivial.
22:41
And as I vary the step size, it make some progress,
22:47
and it goes towards the solution.
22:49
Are you now beginning to see that it
22:51
seems to be making a more stable progress in the beginning?
22:55
And when it comes close to the solution,
22:58
it's fluctuating more.
23:01
And the bigger the step size, the amount
23:05
of fluctuation near the solution is wilder
23:08
as he noticed back there.
23:12
But one very interesting thing is more or less constant.
23:17
There is more fluctuation also on the outside,
23:19
but you see that the initial part still
23:21
seems to be making pretty good progress.
23:24
And as you come close to the solution, it fluctuates more.
23:27
And that is a very principally typical behavior
23:30
of stochastic gradient descent, that in the beginning,
23:35
it makes rapid strides.
23:37
So you may see your training loss
23:39
decrease super fast and then kind of peter out.
23:46
And it's this particular behavior
23:48
which guard people super excited,
23:49
that, hey, in machine learning, we are working
23:52
with all sorts of big data.
23:54
I just want a quick and dirty progress on my training.
23:59
I don't care about getting to the best optimum.
24:02
Because in machine learning, you don't just
24:04
care about solving the optimization problem,
24:07
you actually care about finding solutions
24:10
that work well on unseen data.
24:12
So that means you don't want to over fit and solve
24:15
the optimization problem supremely well.
24:17
So it's great to make rapid initial progress.
24:20
And if after that progress peters out, it's OK.
24:24
This intuitionistic statement that I'm making,
24:28
in some nice cases like convex optimization problems,
24:31
one can mathematically fully quantify these.
24:34
One can prove theorems to quantify each thing
24:37
that I said in terms of how close, how fast, and so on.
24:40
We'll see a little bit of that.
24:43
And this is what really happens to SGD.
24:46
It makes great initial progress, and regardless
24:50
of how you use step sizes, close to the optimum
24:54
it can either get stuck, or enter
24:56
some kind of chaos dynamics, or just behave like crazy.
25:00
So that's typical of SGD.
25:03
And let's look at now slight mathematical insight
25:07
into roughly why this behavior may happen.
25:13
This is a trivial, one-dimensional optimization
25:17
problem, but it conveys the crux of why
25:20
this behavior is displayed by stochastic gradient methods.
25:23
That it works really well in the beginning,
25:26
and then, God knows what happens when
25:28
it comes close to the optimum, anything can happen.
25:31
So let's look at that.
25:32
25:38
OK.
25:39
So let's look at a simple, one-dimensional optimization
25:43
problem.
25:44
I'll kind of draw it out maybe on the other side
25:48
so that people on this side are not disadvantaged.
25:52
So I'll just draw out at least squares problem--
25:57
x is one dimensional.
25:59
Previously, I had ai transpose x Now, ai is also a scalar.
26:03
So it's just 1D stuff--
26:06
everything is 1D
26:08
So this is our setup.
26:13
Think of ai into x minus b i.
26:18
These are quadratic functions, so they look like this.
26:25
Corresponding to different eyes, there's
26:26
like some different functions sitting and so on.
26:31
26:34
So these are my n different loss functions,
26:43
and I want to minimize those.
26:47
26:52
We know-- we can actually explicitly compute
26:55
the solution of that problem.
26:58
So you set the derivative of f of x to 0 so.
27:03
You set the gradient of f of x to 0.
27:05
Hopefully, that's easy for you to do.
27:09
So if you do that differentiation,
27:11
will get gradient of f of x will just given by.
27:16
Well, you can do that in your head,
27:18
I'll just write it out explicitly. aix
27:21
minus bi times ai Is equal to zero, and you solve that for x.
27:30
You get x star, the optimum of this least squares problem.
27:35
So we actually know how to solve it pretty easily.
27:37
27:43
That's a really cool example actually.
27:45
I got that from textbook by Professor Dimitry [INAUDIBLE]..
27:50
Now, a very interesting thing.
27:53
We are not going to use the full gradient,
27:55
we are only going to use the gradients
27:57
of individual components.
28:00
So what does the minimum of an individual component look like?
28:05
Well, the minimum of an individual component
28:07
is attained when we can set this thing to 0.
28:11
And that thing becomes 0 if we just pick x equal to bi
28:15
divided by ai, right?
28:18
So a single component can be minimized by that choice.
28:21
28:24
So you can do a little bit of arithmetic
28:27
mean, geometric mean type inequalities
28:30
to draw this picture.
28:31
28:37
So over all i from 1 through n, this
28:40
is the minimum value of this ratio, ai by bi.
28:46
And let's say this is the max value of ai by bi.
28:55
And we know that closed form solution, that
28:58
is the true solution.
29:01
So you can verify with some algebra
29:03
that that solution will lie in this interval.
29:09
So you may want to--
29:13
this is a tiny exercise for you.
29:17
Hopefully some of you love inequalities like me.
29:19
So this is hopefully not such a bad exercise.
29:22
But you can verify that within this range
29:26
of the individual mins and max is where
29:28
the combined solution lies.
29:29
So of course, intuitively, with a physics styles thinking,
29:32
you would have guessed that right away.
29:33
29:37
That means when you're outside where
29:39
the individual solutions, let's call this the far out zone.
29:43
29:46
And also, this side is the far out zone.
29:49
And this region, within which the true minimum can lie,
29:53
you can say, OK, that's the region of confusion.
29:55
29:58
Why I'm calling it the region of confusion?
30:01
Because there, by minimizing an individual fi,
30:05
you're not going to be able to tell
30:07
what is the combined x star.
30:09
That's all.
30:12
And a very interesting thing happens now, just
30:14
to gain some mathematical insight into that simulation
30:17
that I showed you, that if you have a scalar x that
30:23
is outside this region of confusion, which states
30:28
that if you're far from the region
30:32
within which an optimum can lie.
30:34
So you're far away.
30:35
So you've just started out your progress,
30:36
you made a random initialization, most likely
30:39
far away from where the solution is.
30:41
So suppose that's where you are.
30:43
What happens when you're in that far out region?
30:46
So if you're in the far out region,
30:48
you use a stochastic gradient of some i-th component.
30:55
So the full gradient will look like that.
30:58
A stochastic gradient looks like just one component.
31:03
And when you're far out, outside that min and max regime,
31:08
then you can check by just looking at it,
31:16
that a stochastic gradient, in the far away regime,
31:21
has exactly the same sign as the full gradient.
31:25
What does gradient descent do?
31:27
It says, well, walk in the direction
31:28
of the negative gradient.
31:31
And far away from the optimum, outside the region
31:35
of confusion, you're stochastic gradient has the same sign
31:39
as the true gradient.
31:41
Maybe in more linear algebra terms,
31:44
it makes an acute angle with your gradient.
31:48
So that means if even though a stochastic gradient is not
31:52
exactly the full gradient, it has
31:55
some component in the direction of the true gradient.
31:58
This is one 1D.
31:58
Here it is, exactly the same sign.
32:01
In multiple dimensions, this is the idea
32:04
that it'll have some component in the direction
32:06
of true gradient when you're far away.
32:08
32:10
Which means, if you then use that direction to make
32:15
an update in that style, you will end up
32:18
making solid progress.
32:21
And the beauty is, in the time it
32:25
would have taken you to do one single iteration of batch
32:29
gradient descent, far away you can do millions
32:32
stochastic steps, and, each step will make some progress.
32:35
And that's where we see this dramatic, initial--
32:39
again, in the 1D case this is explicit mathematically.
32:43
In the high-D case, this is more intuitive.
32:46
Without further assumptions about angles, et,
32:48
we can't make such a broad claim.
32:51
But intuitively, this is what's happening,
32:53
and why you see this awesome initial speed.
32:56
32:59
And once you're inside the region of confusion,
33:04
then this behavior breaks down.
33:07
Some stochastic gradient may have
33:08
the same sign as the full gradient, some may not.
33:11
And that's why you can get crazy fluctuations.
33:15
So this simple 1D example kind of exactly
33:18
shows you what we saw in that picture.
33:21
33:24
And people really love this initial progress.
33:26
Because, often we also do early stopping.
33:28
You train for some time, and then you say, OK, I'm done.
33:31
33:34
So importantly, if you are purely an optimization person,
33:40
not thinking so much in terms of machine learning,
33:44
then please keep in mind that stochastic gradient descent
33:47
or stochastic gradient method is not such a great optimization
33:51
method.
33:52
Because once in the region of confusion,
33:54
it can just fluctuate all over forever.
33:57
And in machine learning, you say, oh, the region
33:59
of confusion, that's fine.
34:01
It'll make my method robust.
34:02
It'll make my neural network training more robust.
34:05
It's generalize better, et cetera,
34:06
er cetera-- we like that.
34:08
So it depends on which frame of mind you're in.
34:13
So that's the awesome thing about the stochastic gradient
34:16
method.
34:19
So I'll give you now key mathematical ideas
34:26
behind the success of SGD.
34:27
This was like little illustration.
34:30
Very abstractly, this is an idea that [INAUDIBLE]
34:35
throughout machine learning and throughout theoretical computer
34:38
science and statistics, anytime you're faced with the need
34:43
to compute an expensive quantity,
34:47
resort to randomization to speed up the computation.
34:51
SGD is one example.
34:54
The true gradient was expensive to compute,
34:57
so we create a randomized estimate of the true gradient.
35:03
And the randomized estimate is much faster to compute.
35:08
And mathematically, what will start happening is,
35:12
depending on how good your randomized estimate is,
35:15
your method may or may not convert to the right answer.
35:21
So of course, one has to be careful about what
35:23
particular randomized estimate one makes.
35:28
But really abstractly, even if I hadn't
35:30
shown you, the main idea, this idea
35:32
you can apply in many other settings.
35:35
If you have a difficult quantity,
35:36
come up with a randomized estimate
35:39
and save on computation.
35:41
This is a very important theme throughout machine learning
35:44
and data science.
35:48
And this is the key property.
35:50
So stochastic gradient descent, it uses stochastic gradients.
35:56
Stochastic is, here, used very loosely.
35:58
And it just means that some randomization.
36:01
That's all it means.
36:03
And the property-- the key property that we have
36:06
is in expectation.
36:10
The expectation is over whatever randomness you used.
36:15
So if you picked some random training data point out
36:19
of the million, then the expectation
36:22
is over the probability distribution
36:24
over what kind of randomness you used.
36:27
If you picked uniformly at random from a million points,
36:31
then this expectation is over that uniform probability.
36:34
But the key property for SGD, or at least the version
36:39
of SGD I'm talking about, is that that over that randomness.
36:44
The thing that you're pretending to use,
36:46
instead of the true gradient n expectation actually
36:49
it is the true gradient.
36:52
So in statistics language, this is
36:54
called the stochastic gradient that we
36:57
use is an unbiased estimate of the true gradient.
37:03
And this is a very important property
37:05
in the mathematical analysis of stochastic gradient descent,
37:08
that it is an unbiased estimate, And
37:12
Intuitively speaking anytime you did any proof
37:16
in class, or in the book, or lecture, or to wherever,
37:19
where you were using true gradients,
37:23
more or less, you can do those same proofs--
37:25
more or less, not always.
37:27
Using stochastic gradients by encapsulating everything
37:33
within expectations over the randomness.
37:36
I'll show you an example of what I mean by that.
37:38
I'm just trying to simplify that for you.
37:42
And
37:42
In particular, the unbiasedness is great.
37:48
So it means I can kind of plug-in
37:51
these stochastic gradients in place of the true gradient,
37:55
and I'm still doing something meaningful.
37:57
So this is answering that earlier question,
38:00
why this random stuff?
38:03
Why should we think it may work?
38:05
But there's another very important aspect
38:07
to why it works, beyond this unbiasedness,
38:12
that the amount of noise, or the amount of stochasticity
38:19
is controlled.
38:20
So just because it is an unbiased estimate,
38:24
doesn't mean that it's going to work that well.
38:28
Why?
38:28
Because it could still fluctuate hugely, right?
38:32
Essentially, plus infinity here, minus infinity here.
38:34
You take an average, you get 0.
38:36
So that is essentially unbiased, but the fluctuation
38:40
is gigantic.
38:41
So whenever talking about estimates,
38:44
what's the other key quantity we need to care about
38:47
beyond expectation?
38:48
AUDIENCE: Variance.
38:49
AUDIENCE: Variance.
38:50
PROFESSOR SRA: Variance.
38:51
And really, the key thing that governs
38:55
the speed at which stochastic gradient descent does
38:59
the job that we want it to do is, how much variance do
39:02
the stochastic gradients have?
39:06
Just this simple statistical point, in fact,
39:09
is at the heart of a sequence of research progress
39:13
in the past five years in the field of stochastic gradient,
39:17
where people have worked really hard to come up
39:20
with newer and newer, fancier and fancier
39:22
versions of stochastic gradient which
39:26
have the unbiasedness property, but have
39:28
smaller and smaller variance.
39:30
And the smaller the variance you have,
39:33
the better your stochastic gradient
39:36
is as a replacement of the true gradient.
39:41
And of course, the better [INAUDIBLE]
39:42
of the true gradient, then you truly get that n times up.
39:47
39:51
So the speed of convergence depends
39:53
on how noisy the stochastic gradients are.
39:55
It seems like I'm going too slow.
39:57
I won't be able to do a proof, which sucks.
40:00
But let me actually tell you then about, rather than
40:05
the proof, I think I'll share the proof with Gil.
40:09
Because the proof that I wanted to actually show you,
40:14
gives a proof of stochastic gradient
40:17
is well-behaved on both convex and nonconvex problems.
40:21
And the proof I wanted to show was
40:22
for the nonconvex case, because it applies to neural networks.
40:25
So you may be curious about that proof.
40:27
And remarkably, that proof is much simpler
40:29
than the case of convex problems.
40:32
So let me just mention some very important points
40:35
about stochastic gradient.
40:36
So even though this method has been around since 1951,
40:39
every deep learning tool kit has it,
40:41
and we are studying it in class, there are still
40:45
gaps between what we can say theoretically
40:47
and what happens in practice.
40:50
And I'll show you those gaps already,
40:52
and encourage you to think about those if you wish.
40:55
So let's look back at our problem
40:56
and deliver two variants.
40:58
So here are the two variants.
41:00
I'm going to ask if any of you is
41:02
familiar with these variants in some way or the other.
41:05
So I just call it feasible.
41:08
Here, there are no constraints.
41:10
So start with any random vector of your choice.
41:15
In deep network training you have to work harder.
41:17
And then, this is the iteration you run--
41:20
option 1 and option 2.
41:22
So option 1 says, that was the idea we had in class,
41:26
randomly pick some training data point,
41:28
use its stochastic gradient.
41:29
41:33
What do we mean by randomly pick?
41:36
The moment you use the word random,
41:38
you have to define what's the randomness.
41:43
So one randomness is uniform probability
41:45
over n training data points.
41:47
That is one randomness.
41:49
The other version is you pick a training data point
41:54
without replacement.
41:56
So with replacement means uniformly at random.
42:00
Each time you draw a number from 1 through n,
42:02
use their stochastic gradient, move on.
42:05
Which means the same point can easily be picked twice, also.
42:09
And without replacement means, if you've picked a point number
42:12
three, you're not going to pick it again
42:15
until you've gone through the entire training data set.
42:19
Those are two types of randomness.
42:23
Which version would you use?
42:24
42:27
There is no right or wrong answer to this.
42:29
I'm just taking a poll.
42:30
What would you use?
42:33
Think that you're writing a program for this,
42:37
and maybe think really pragmatically, practically.
42:41
So that's enough of a hint.
42:43
Which one would you use--
42:44
I'm just curious.
42:44
42:47
Who would use 1?
42:48
Please, raise hands.
42:50
OK.
42:51
And the exclusion-- the compliment thereof.
42:55
I don't know.
42:55
Maybe some people are undecided.
42:57
Who would use 2?
42:59
Very few people.
43:00
Ooh, OK.
43:01
43:04
How many of you use neural network training
43:06
toolkits like TensorFlow, PyTorch, whatnot?
43:10
Which version are they using?
43:12
43:16
Actually, every person in the real world is using version 2.
43:21
Are you really going to randomly go through your RAM
43:24
each time to pick random points?
43:27
That'll kill your GPU performance like anything.
43:31
What people do is take a data set,
43:34
use a pre-shuffle operation, and then just stream
43:37
through the data.
43:38
What does streaming through the data mean?
43:41
Without replacement.
43:42
So all the toolkits actually are using the
43:44
without replacement version, even though, intuitively,
43:49
uniform random feels much nicer.
43:51
And that feeling is not ill-founded,
43:53
because that's the only version we know
43:55
how to analyze mathematically.
43:57
So even for this method, everybody studies it.
44:00
There are a million papers on it.
44:02
The version that is used in practice
44:04
is not the version we know how to analyze.
44:07
It's a major open problem in the field of stochastic gradient
44:11
to actually analyze the version that we use in practice.
44:14
It's kind of embarrassing, but without replacement means
44:19
non-IAD probability theory, and non-IAD probability theory
44:23
is not so easy.
44:24
That's the answer.
44:27
OK.
44:27
So the other version is this mini-batch idea--
44:29
which you mentioned really early on--
44:33
is that rather than pick one random point,
44:39
I'll pick a mini batch.
44:42
So I had a million points--
44:43
each time, instead of picking one, maybe I'll pick 10, or.
44:46
100, or 1,000, or what have you.
44:48
So this averages things.
44:51
Averaging things reduces the variance.
44:54
So this is actually a good thing,
44:57
because the more quantities you average,
44:58
the less noise you have.
45:00
That's kind of what happened in probability.
45:04
So we pick a mini-batch, and the stochastic estimate now
45:11
is this not just a single gradient,
45:13
but averaged over a mini-batch.
45:17
So a mini-batch of size 1 is the pure vanilla SGD.
45:21
Mini-batch of size n is nothing other than pure gradient
45:23
descent.
45:24
Something in between is what people actually use.
45:28
And again, the theoretical analysis
45:30
only exists if the mini-batch is picked with replacement
45:33
not without replacement.
45:36
So one of the reasons actually-- a very important thing--
45:40
in theory, you don't gain too much in terms
45:43
of computational gains on convergent speed
45:46
by using mini-batches.
45:48
But mini-batches are really crucial, especially
45:50
in the deep learning, GPU-style training,
45:54
because they allow you to do things in parallel.
45:58
Each thread or each core or subcore or small chip
46:02
or what have, you depending on your hardware,
46:04
can be working with one stochastic gradient.
46:07
So mini-batches, the larger the mini batch the more things
46:10
you can do in parallel.
46:11
46:13
So mini-batches are greatly exploited by people
46:16
to give you a cheap version of parallelism.
46:22
And where does the parallelism happen?
46:23
You can think that each core computes a stochastic gradient.
46:28
So the hard part is not adding these things up
46:31
and making the update to x, the hard part is computing
46:35
a stochastic gradient.
46:38
So if you can compute 10,000 of those in parallel
46:40
because you have 10,000 cores, great for you.
46:44
And that's the reason people love using mini-batches.
46:47
But a nice side remark here, this also
46:51
brings us closer to the research edge of things again.
46:54
That, well, you'd love to use very large mini-batches
46:58
so that you can fully max out on the parallelism
47:01
available to you.
47:02
Maybe you have a multi-GPU system,
47:04
if you're friends with nVidia or Google.
47:07
I only have two GPUs.
47:09
But it depends on how many GPU shows you have.
47:11
You'd like to really max out on parallelism
47:14
so that you can really crunch through big data sets
47:17
as fast as possible.
47:19
But you know what happens with very large mini-batches?
47:21
47:24
So if you have very large mini-batches,
47:28
stochastic gradient starts looking more like?
47:30
47:33
Full gradient descent, which is also
47:35
called batch gradient descent.
47:38
That's not a bad thing.
47:39
That's awesome for optimization.
47:41
But it is a weird conundrum that happens in training
47:44
deep neural networks.
47:46
This type of problem we wouldn't have for convex optimization.
47:49
But in deep neural networks, this
47:50
is really disturbing thing happens,
47:52
that if you use this very large mini-batches,
47:56
your method starts resembling gradient descent.
47:59
That means it decreases noise so much so
48:02
that this region of confusion shrinks so much--
48:07
which all sounds good, but it ends up
48:09
being really bad for machine learning.
48:11
That's what I said, that in machine learning
48:13
you want some region of uncertainty.
48:15
And what it means actually is, a lot of people
48:19
have been working on this, including at big companies,
48:23
that if you reduce that region of uncertainty too much,
48:27
you end up over-fitting your neural network.
48:31
And then it starts sucking in its test data, unseen data
48:36
performance.
48:38
So even though for parallelism, programming, optimization
48:42
theory, big mini-batch is awesome,
48:45
unfortunately there's price to be paid, that it hurts
48:51
your test error performance.
48:53
And there are all sorts of methods
48:55
people are trying to cook up, including shrinking data
49:00
accordingly, or chaining neural network architecture,
49:03
and all sorts of ideas.
49:04
You can cook up your ideas for your favorite architecture,
49:07
how to make a large mini-batch without hurting
49:09
the final performance.
49:11
But it's still somewhat of an open question
49:14
on how to optimally select how large your mini-batch should
49:19
be.
49:20
So even though these ideas are simple,
49:23
you see that every simple idea leads
49:25
to an entire sub area of SGD.
49:30
So here are practical challenges.
49:33
People have various heuristics for solving these challenges.
49:37
You can cook up your own, but it's not
49:39
that one idea always works.
49:42
So if you look at SGD, what are the moving parts?
49:48
The moving parts in SGD--
49:50
the gradients, stochastic gradient, the step size,
49:53
the mini batch.
49:54
So how should I pick step sizes--
49:57
very non-trivial problem.
49:59
Different deep learning toolkits may
50:01
have different ways of automating that tuning,
50:04
but it's one of the painful things.
50:07
Which mini batch to use?
50:08
With replacement, without replacement
50:10
I already showed you.
50:12
But which mini batch should I use, how large that should be?
50:15
Again, not an easy question to answer.
50:18
How to compute stochastic gradients.
50:20
Does anybody know how stochastic gradients are computed
50:22
for deep network training?
50:25
Anybody know?
50:26
50:30
There is a very famous algorithm called back propagation.
50:34
That back propagation algorithm is
50:36
used to compute a single stochastic gradient.
50:39
Some people use the word back prop to mean SGD.
50:43
But what back prop really means is some kind of algorithm
50:47
which computes for you a single stochastic gradient.
50:51
And hence this TensorFlow, et cetera-- these
50:54
toolkits-- they come up with all sorts of ways
50:56
to automate the computation of a gradient.
50:59
Because, really, that's the main thing.
51:01
And then other ideas like gradient clipping,
51:03
and momentum, et cetera.
51:04
There's a bunch of other ideas.
51:06
And the theoretical challenges, I mentioned to you already--
51:09
proving that it works, that it actually
51:11
solves what it set out to do.
51:13
Unfortunately, I was too slow.
51:15
I couldn't show you the awesome five-line proof
51:19
that I have that SGD works for neural networks.
51:23
And theoretical analysis, as I said, it's really laggy.
51:28
My proof also uses the with replacement.
51:32
And the without replacement version,
51:34
which is the one that is actually implemented,
51:38
there's very little progress on that.
51:40
There is some progress.
51:41
There's a bunch of papers, including
51:43
from our colleagues at MIT, but it's quite unsolved.
51:47
And the biggest question, which most
51:49
of the people in machine learning
51:51
are currently excited about these days is stuff like,
51:56
why does SGD work so well for neural networks?
52:00
We use this crappy optimization method,
52:02
it very rapidly does some fitting--
52:05
the data is large, neural network is large,
52:07
and then this neural network ends up
52:10
having great classification performance.
52:12
Why is that happening?
52:14
It's called trying to explain--
52:16
build a theory of generalization.
52:17
Why does an SGD-trained neural network
52:21
work better than neural networks train with more
52:23
fancy optimization methods?
52:25
It's a mystery, and most of the people
52:27
who take interest in theoretical machine
52:29
learning and statistics, that is one of the mysteries they're
52:32
trying to understand.
52:33
So I think that's my story of SGD.
52:37
And this is the part we skipped, but it's OK.
52:41
The intuition behind SGD is much more important in this.
52:46
So I think we can close.
52:48
PROFESSOR STRANG: Thank you.
52:49
[APPLAUSE]
52:55
And maybe I can learn the proof for Monday's lecture.
52:58
PROFESSOR SRA: Exactly.
52:59
Yeah, I think so.
53:00
That'll be great.
English - CC (English)
###