23. Accelerating Gradient Descent (Use Momentum)
2.71M subscribers
SUBSCRIBED
MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning, Spring 2018 Instructor: Gilbert Strang View the complete course: https://ocw.mit.edu/18-065S18YouTube Playlist: https://www.youtube.com/playlist?list...In this lecture, Professor Strang explains both momentum-based gradient descent and Nesterov's accelerated gradient descent. License: Creative Commons BY-NC-SA More information at https://ocw.mit.edu/termsMore courses at https://ocw.mit.edu
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:23
GILBERT STRANG: OK.
00:23
So what I promised, and now I'm going to do it,
00:27
to talk about gradient descent and its descendants.
00:34
So from the basic gradient descent formula,
00:37
which we all know--
00:38
let me just write that down--
00:40
the new point is the old point.
00:47
We're going downwards, so with a minus
00:49
sign that's the step size.
00:52
And we compute the gradient at XK.
00:57
So we're descending in the direction
01:00
of the negative gradient.
01:02
And that's the basic formula, and is in every book studied.
01:09
So my main reference for some of these lectures
01:18
is the book by Stephen Boyd and Lieven Vandenberghe.
01:24
And I mention again, Professor Boyd is talking, in this room,
01:30
next week Wednesday, Thursday and he's speaking
01:35
somewhere on Friday at 4:30--
01:38
and of course, about optimization.
01:41
And he's a good lecturer, yeah, very good.
01:43
OK.
01:45
So there's steepest descent, and I've redrawn my picture
01:49
from last time.
01:50
Now I'll go over there and look at that picture.
01:53
But let me say what's coming.
01:56
So that's pretty standard--
01:59
very standard, you could say.
02:02
Then this is the improvement that is widely used.
02:09
Adding in something called momentum
02:11
to avoid the zigzag that we're going to see over there.
02:15
And there's another way to do it.
02:17
There's a Russian guy named Nesterov.
02:20
His papers are not easy to read, but they've
02:22
got serious content.
02:25
And one thing he did was find an alternative
02:29
to momentum that also accelerated the descent.
02:37
So this produces-- these both produce faster descent
02:42
than the ordinary one.
02:45
OK.
02:46
And then you know, looking ahead,
02:48
that for problems of machine learning,
02:52
they're so large that the gradient--
02:56
we have so many variables--
02:58
all those weights are variables.
03:01
And that could-- hundreds of thousands is not uncommon.
03:07
So then the gradient becomes a pretty big calculation,
03:12
and we just don't have to do it all at once.
03:15
We don't have to change--
03:16
so XK is a vector of all the weights, or-- and using--
03:22
and our equations are matching the training data.
03:29
So we don't have to use all the training data at once,
03:33
and we don't.
03:34
We take a batch of training data, like one.
03:38
But that's sort of inefficient in the opposite direction,
03:42
to do them one at a time.
03:43
So we don't know want to do them one at a time,
03:46
but we don't want to do all million at a time.
03:49
So the compromise is a mini batch.
03:53
So stochastic gradient descent does a mini batch at a time--
03:59
a mini batch of training, of samples
04:04
training data each step.
04:08
04:12
And it can choose them stochastically--
04:15
meaning randomly, or more systematically--
04:19
but we do a batch at a time.
04:23
And that will come after the--
04:26
it'll come next week after a marathon, of course, on Monday.
04:32
OK.
04:33
So let me just go back to that picture for a moment,
04:36
but then the real content of today
04:39
is this one with momentum added.
04:43
OK.
04:44
I just-- I probably haven't got the picture perfect yet.
04:48
I'm just not an artist, but I think I'm closer.
04:56
So this is-- those are the level sets.
05:01
Those are the sets f of x equal constant.
05:06
And in our model problem, f of x is x1 squared--
05:11
or let's say x squared plus b-y squared equal constant with
05:16
small b--
05:18
b below 1 and maybe far below 1.
05:22
So those are ellipses.
05:23
05:26
Those are the equations of an ellipse,
05:27
and that's what I tried to draw.
05:30
And if b is small, then the ellipses
05:32
are long and thin like that.
05:35
And now, what's the picture?
05:38
You start with a point x nought, and you descend
05:42
in the steepest direction.
05:44
So the steepest direction is perpendicular to the level set,
05:47
right?
05:48
Perpendicular to the ellipse.
05:49
So you're down, down, down.
05:51
You're passing through more ellipses,
05:53
more ellipses, more ellipses.
05:55
Eventually, your tangent to a--
05:58
it seems to me it has to be tangent.
06:00
I didn't read this, but looks reasonable to me that
06:05
the farthest in level set-- farthest in ellipse--
06:11
you're tangent to, and then you start going up again.
06:15
So that's the optimal point to stop to end that step.
06:19
And then where does the next step go?
06:21
Well, you're here.
06:23
You're on an ellipse.
06:25
That's a level set.
06:26
You want to move in the gradient direction.
06:28
That's perpendicular to the level set.
06:31
So you're going down somewhere here,
06:33
and you're passing again through more and more ellipses,
06:37
until you're tangent to a smaller ellipse here.
06:44
And you see the zigzag pattern.
06:48
And that zigzag pattern is what we
06:50
see, by formula, in Boyd's book, and many other places, too.
07:00
The formula has those powers of the magic number.
07:06
So we start at the--
07:08
start at the point b1, and follow this path.
07:21
Then the X's are the same b times this quantity
07:27
to the kth power.
07:29
And here is that quantity, b minus 1 over b plus 1.
07:34
So you see, for a small b, that's a negative number.
07:38
So it's flipping sine in the X's, as we saw in the picture.
07:42
At least that part of the picture is correct.
07:45
The y's don't flip sine.
07:48
So this was XK, and when k is 0, we got b.
07:55
YK is, I think, is not flipping sine.
08:03
So that looks good.
08:05
And then FK-- the value of f--
08:09
also was the same quantity.
08:12
FK is that same quantity to the kth times f0.
08:20
So that quantity's all important.
08:24
And so the purpose of today's lecture,
08:27
is to tell you what the momentum term--
08:33
what improvement-- what change that
08:35
brings in the basic steepest descent formula.
08:39
I'm going to add on another term, which
08:41
is going to have some--
08:43
give us some memory of the previous step.
08:48
And so when I do that, I want to track that kind of descent
08:58
for the new--
09:00
for the accelerated descent, and track it and see
09:06
what improvement the momentum term brings.
09:11
And so the final result will be to tell you
09:14
the improvement in the--
09:15
produced by the momentum term.
09:18
Maybe while I have your attention,
09:21
I'll tell you what it is now.
09:24
And then will come the details, the algebra.
09:29
And to me-- so this is as my own thought--
09:33
09:36
it's a miracle that the algebra, which
09:38
is straightforward-- you really see the value of eigenvectors.
09:43
We explained eigenvectors in class, but here you see why--
09:49
how to use them.
09:51
That is really a good exercise.
09:54
But to me it's a miracle that the expression with momentum
10:03
is very much like that expression, but different,
10:07
of course.
10:08
The decay-- the term that tells you how fast the decay is--
10:18
is smaller.
10:19
So you're taking kth power.
10:21
So let me-- I'll write that down, if that's all right.
10:25
I didn't plan to do--
10:26
to reveal the final result at the beginning of the lecture.
10:34
But I think you want to see where we're going.
10:37
So with momentum-- and we have to see what that means--
10:48
this term of 1 minus b over 1 plus b becomes--
10:56
changes to-- 1 minus square root of b over 1
11:06
plus square root of b.
11:08
So I mentioned that before, but I don't think
11:12
I wrote it down as clearly.
11:16
So the miracle to me is to get such a nice expression
11:20
for the--
11:22
because you'll see the algebra is-- it works, but it involves
11:31
more terms because of momentum, involves
11:34
doing a minimization of eigenvalues,
11:37
and yet it comes out nicely.
11:39
And then you have to see the importance of that.
11:42
So let me-- I will just take the same example
11:45
that I mentioned before.
11:47
If b is 1 over 100, then this is 0.99 over 1.01.
11:55
I think that these--
11:58
there's a square here, 2k.
12:05
So if we're-- so I'll just keep the square there,
12:10
no big change, but I'm looking at-- now here-- at the square.
12:14
12:17
Maybe squares are everywhere.
12:21
OK.
12:22
So that's close to 1.
12:26
And now let's compare that with what we have.
12:29
So if b is 1 over 100--
12:32
so I'm taking b to be 1 over 100--
12:35
and square root of b is 1 over 10.
12:37
So this is 0.9 over 1.1 squared.
12:45
And there's a tremendous-- that's
12:46
a lot smaller than that is.
12:49
Right.
12:51
9/10-- 9 over 11, compared to 99 over 101.
12:57
This one is definitely-- oh, sorry.
13:03
Yeah, this reduction factor is well below that one.
13:10
So it's a good thing.
13:11
It's worth doing.
13:14
And now what does it involve?
13:17
So I'll write down the expression for the stochastic--
13:25
here we go.
13:26
OK.
13:27
So here's one way to see it.
13:29
The new X is the old X minus the gradient.
13:36
13:40
And now comes an extra term, which gives us a little memory.
13:47
Well, sorry.
13:50
The algebra is slightly nicer if I write it a little bit
13:54
differently.
13:56
I'll create a new quantity, ZK, with a step size.
14:06
OK.
14:06
14:15
So if I took ZK to be just the gradient,
14:19
that would be steepest descent.
14:20
Nothing has changed.
14:22
But instead, I'm going to take ZK--
14:26
well, it's leading term will be the gradient.
14:28
14:31
But here comes the momentum term.
14:34
I add on a multiple beta.
14:36
One way to do it is of the previous Z.
14:40
So the Z is the search direction.
14:42
Z is the gradient you're traveling.
14:44
It is the direction you're moving.
14:47
So it's different from that direction there.
14:51
That direction was the gradient.
14:56
This direction is the gradient corrected by a memory
15:02
term, a momentum term.
15:05
And one way to interpret that is to say that that ball--
15:09
is to think of a heavy ball, instead of just a point.
15:14
I think of a heavy ball.
15:17
It, instead of bouncing back and forth as uselessly as this one,
15:27
it tends to--
15:28
it still bounces, of course, on the sides of the level set--
15:32
but it comes down the valley faster.
15:35
And that's the effect of this.
15:37
So you could play with different adjustment
15:43
terms, different corrections.
15:45
So I'll follow through this one.
15:48
Nesterov had another way to make a change in the formula,
15:53
and there are certainly others beyond that.
15:57
OK, so how do we analyze that one?
16:01
Well, the real point is, we've sort of, by taking--
16:07
by involving the previous step, we now
16:11
have a three level method instead of a two level method,
16:16
you could say.
16:18
This involves only level K plus 1
16:21
and level K. The formulas now involve K plus 1K,
16:28
and K minus 1.
16:30
It's just like going from a first order differential
16:35
equation to a second order differential equation.
16:38
16:42
I'm not really thinking that K is a time variable.
16:46
But in the analogy, K could be a time variable.
16:50
So that here we had a first order equation.
16:54
If I wanted to model that, it's sort
16:57
of a DXDT coming in there, equal gradient.
17:01
And these models are highly useful
17:04
and developed for sort of a continuous model
17:09
of steepest descent--
17:12
a continuous motion instead of the discrete motion.
17:19
OK.
17:20
So that would-- that continuous model for that guy
17:25
would be a first order in time.
17:27
For this one, it'll be second order in time.
17:30
And second order equations, of course,
17:33
and there'd be constant coefficients
17:35
in our model problem.
17:37
And the thing about a second order equation that we all know
17:41
is, there is a momentum term--
17:45
a damping term, you could say--
17:49
in multiplying the first derivative.
17:53
So that's what a second order equation offers--
17:59
is the inclusion of a damping term
18:02
which isn't present in the original first order.
18:07
OK.
18:09
So how do we analyze this?
18:11
18:13
I have to-- so how do you analyze second order
18:17
differential equations?
18:19
You write them as a system of two first order equations.
18:22
So that's exactly what we're going to do here,
18:25
in the discrete case.
18:27
We're going to see--
18:29
because we have two equations.
18:31
And they're first order, and we can--
18:34
let me play with them for a moment to make them good.
18:38
OK.
18:39
So I'm going to have--
18:40
so this will go to two first order equations,
18:46
in which the first one--
18:48
I'm just going to copy, XK plus 1
18:51
is XK minus that step size ZK.
18:56
19:00
Yeah.
19:00
OK.
19:02
Yeah.
19:03
OK.
19:03
Time the previous times step here--
19:07
the next time step on the left.
19:09
OK.
19:09
So I just copied that.
19:11
Now this one I'm going to increase K by 1.
19:17
So in order to have that looking to match this,
19:21
I'll write that as ZK plus 1, and I'll bring the K, saying,
19:27
grad FK plus 1 equal beta ZK.
19:35
That work with you?
19:37
I just, in this thing, instead of looking at it at K,
19:42
I went to K plus 1.
19:47
And I put the K plus 1 terms on one side.
19:50
OK.
19:50
So now I have a--
19:52
19:56
let's see.
19:57
Let's remember, we're doing--
19:58
the model we're doing is F equal a half X transpose SX.
20:04
So the gradient of F is SX.
20:09
So what I've written there, for gradient, is really--
20:13
I know what that gradient is.
20:15
So that's really SX K plus 1.
20:20
20:23
OK.
20:23
20:27
How to analyze that.
20:30
What happens as K travels forward 1, 2, 3, 4, 5?
20:36
We have a constant coefficient problem at every step.
20:40
The XZ variable is getting multiplied by a matrix.
20:46
So here's XZ at K plus 1.
20:52
And over here will be XZ at step K.
20:58
And I just have to figure out what matrix
21:02
is multiplying here and here.
21:05
OK.
21:07
And I guess here I see it.
21:09
For the first equation has a 1 and a minus S,
21:12
looks like, in the first row.
21:14
And it has a beta in the second row.
21:17
And here the first equation has a 1, 0 in that row.
21:24
And then a minus S. So I'll put in
21:27
minus S, multiplying XK plus 1, and then
21:31
the 1 that multiplies ZK plus 1.
21:34
Is that all right?
21:35
21:39
Sorry.
21:39
I've got two S's, and I didn't draw that one--
21:42
didn't write that one in large enough,
21:43
and I'd planned to erase it anyway.
21:47
This is the step sizes.
21:49
This is the matrix.
21:51
But it's not quite fitting its place.
21:57
This is the point where I'm going to use eigenvalues.
22:01
I'm going to follow each eigenvalue.
22:05
That's the whole point.
22:06
When I follow each eigenvalue-- each eigenvector,
22:10
I should say--
22:11
I'll follow each eigenvector of S. So let's do that.
22:17
So eigenvectors of S-- what are we going to call those?
22:23
Lambda, probably.
22:26
So SX equal lambda X. I think that's what's coming.
22:30
22:34
Or Q. To do things right, I want to remember
22:41
that S is a positive, definite symmetric matrix.
22:45
That's why I call it S, instead of A.
22:47
So I really should call the eigen--
22:49
it doesn't matter, but to be on the ball,
22:54
let me call the eigenvector Q, and the eigenvalue lambda.
22:58
23:02
OK.
23:02
23:06
So now I want to follow this eigenvector.
23:10
So I'm supposing that XK is sum CK times Q.
23:17
I'm assuming that X is in the--
23:21
tracking this eigenvector.
23:23
And I'm going to assume that ZK is some other constant times Q.
23:30
Everybody, do you see?
23:31
That's a vector and that's a vector.
23:33
And I want scalars.
23:35
I want to attract just scalar CK and DK.
23:40
So that's really what I have here.
23:43
This was a little tricky, because X here is a vector,
23:47
and two components are N components.
23:50
I didn't want that.
23:51
I really wanted just to track an eigenvector.
23:56
Once I've settled on the direction Q,
23:59
everything is-- all vectors are in the direction of Q.
24:02
So we just have numbers C and D to track.
24:06
OK.
24:07
So I'm going to rewrite this correctly, as, yeah.
24:15
Well, let me keep going with this little formula.
24:19
Then what will--
24:20
I needed an SX.
24:22
What will SXK be?
24:26
If XK is in the direction of the eigenvector Q, and it's CK--
24:33
what happens when I multiply by S?
24:34
24:37
Q was an eigenvector.
24:39
So the multiplying by S gives me a--
24:42
AUDIENCE: Eigenvalue.
24:42
GILBERT STRANG: Eigenvalue, right?
24:44
So it's CK lambda Q. Everything is a multiple of Q.
24:50
And it's only those multiples I'm looking
24:53
for, the C's and the D's.
24:56
And then the lambda comes into the S term.
24:59
Yeah.
24:59
I think that's probably all I need to do this.
25:05
And then the gradient-- yeah.
25:07
So that's the gradient, of course.
25:09
This is the gradient of F at K--
25:15
is that one.
25:15
OK.
25:16
So instead of this, let me just write
25:19
what's happening if I'm tracking the coefficients CK plus 1
25:26
and DK plus 1.
25:29
Then what I really meant to have there is 1, 0.
25:34
And minus S is a minus lambda.
25:39
25:43
Is that right?
25:44
Yeah.
25:45
When I multiply the eigenvector by S, I'm just getting--
25:50
oh, it's a lambda times a CK.
25:54
Yeah.
25:54
Lambda times the CK-- that's good.
25:57
I think that that's the left hand side of my equation.
26:02
And on the right hand side, I have here.
26:10
That's 1.
26:11
And this was the scalar, the step size.
26:14
And this was the other coefficient.
26:16
It's the beta.
26:17
So I want to choose--
26:18
what's my purpose now?
26:22
That gives me the--
26:26
what happens at every step to the C and D.
26:30
So I want to choose the two things that I have--
26:34
I'm free to choose are S and beta.
26:36
So that's my big job--
26:39
choose S and beta.
26:41
26:44
OK.
26:45
Now I-- to make--
26:46
oh, let me just shape this by multiplying the inverse
26:52
of that, and get it over here.
26:54
So that will really--
26:55
you'll see everything.
26:57
So CK plus 1, DK plus 1.
27:02
What's the inverse of 1, 0?
27:05
Oh, I don't think I want to-- that
27:07
would have a tough time finding an inverse.
27:12
It was a 1, wasn't it?
27:13
27:19
Yeah.
27:20
OK.
27:20
So I'm going to multiply by the inverse of that matrix
27:23
to get it over here.
27:26
And what's the inverse of 1, 1 minus lambda?
27:29
It's 1, 1 plus lambda.
27:32
So that the inverse brought it over here,
27:34
times this matrix, 1, 0 beta, and minus the step size.
27:41
That's what multiply CK DK.
27:42
27:45
So we have these simple, beautiful steps
27:49
which come from tracking one eigenvector--
27:53
makes the whole problem scalar.
27:55
So I multiply those two matrices and I finally
27:58
get the matrix that I really have to think about.
28:01
1, 0 times that'll be 1 minus S. Lambda 1 times that'll
28:06
be a lambda there.
28:08
And minus lambda S plus beta.
28:11
Beta minus lambda S. That's the matrix
28:15
that we see at every step.
28:18
Let me call that matrix R.
28:27
So I've done some algebra-- more than I would always do
28:32
in a lecture--
28:33
but it's really my--
28:35
I wouldn't do it if it wasn't nice algebra.
28:37
What's the conclusion?
28:39
That conclusion is that with the momentum term--
28:44
with this number beta available to choose, as well as S,
28:49
the step--
28:51
the coefficient of the eigenvector
28:57
is multiplied at every step by that matrix R.
29:00
R is that matrix.
29:04
And of course, that matrix involves the eigenvalue.
29:06
29:10
So we have to think about--
29:14
what do we want to do now?
29:17
We want to choose beta and S to make
29:23
R as small as possible, right?
29:26
We want to make R as small as possible.
29:29
And we are free to choose beta and S, but R depends on lambda.
29:34
29:36
So I'm going to make it as small as possible
29:39
over the whole range of possible lambdas.
29:42
So let me-- so now here we really go.
29:45
29:49
So we have lambda between sum.
29:55
These are the eigenvalue of S. And what we know--
30:04
what's reasonable to know-- is a lower bound.
30:09
It's a positive.
30:10
This is a symmetric positive definite matrix.
30:13
A lower bound and an upper bound, for example, m was B,
30:20
and M was 1, in that 2 by 2 problem.
30:25
And this is what we know, that the eigenvalues
30:28
are between m and M. And the ratio of m to M--
30:38
well, if I write--
30:42
30:45
this is the key quantity.
30:50
And what's it called?
30:53
Lambda max divided by lambda min is the--
30:55
AUDIENCE: Condition number.
30:56
GILBERT STRANG: Condition number.
30:57
Right.
30:58
This is all sometimes written kappa--
31:00
Greek letter kappa-- the condition number of S.
31:10
And when that's big, then the problem is going to be harder.
31:14
When that's 1, then my matrix is just a multiple
31:19
of the identity matrix.
31:21
And the problem is trivial.
31:22
When capital M and small m are the same,
31:27
then that's saying that the largest and smallest
31:31
eigenvalues are identical, that the matrix is
31:34
a multiple of the identity.
31:36
That's the condition number one.
31:39
But the bad one is when it's 1 over b, in our example,
31:47
and that could be very large.
31:51
OK.
31:52
That's where we have our problem.
31:56
Let me just insert about the ordinary gradient descent.
32:05
Of course, the textbooks find a estimate for how fast that is.
32:11
And of course, it depends on that number.
32:15
Yeah.
32:16
So it depends on that number, and you exactly
32:19
saw how it depended on that number.
32:23
Right.
32:25
But now we have a different problem.
32:27
And we're going to finish it.
32:29
OK.
32:30
So what's my job?
32:31
I'm going to choose S and beta to keep the eigenvalues of R.
32:38
So let's give the eigenvalues of R a name.
32:42
So R-- let's say R has eigenvalues e1, that
32:50
depends on the lambda and the S and the beta and e2.
32:56
33:00
So those are the eigenvalues of R--
33:03
just giving a letter to them.
33:07
So what's our job?
33:09
We want to choose S and beta to make those eigenvalues as
33:14
small as possible.
33:16
Right?
33:17
Small eigenvalues-- if R has small eigenvalues, its powers--
33:24
every step multiplies by R. So the convergence rate
33:29
with momentum is--
33:32
depends on the powers of R getting small fast.
33:36
It depends on the eigenvalues being small.
33:39
We want to minimize the largest eigenvalue.
33:48
So I'll say the maximum of e1 and e2--
33:56
that's our job.
33:57
Minimize-- we want to choose S and beta to minimize
34:01
the largest eigenvalue.
34:03
Because if there's one small eigenvalue,
34:05
but the other is big, then the other one is going to kill us.
34:08
So we have to get both eigenvalues down.
34:12
And of course, those depend on lambda.
34:16
E1 depends on lambda.
34:18
So we have a little algebra problem.
34:20
And this is what I described as a miracle--
34:23
the fact that this little algebra problem--
34:26
the eigenvalues of that matrix, e1 and e2, which
34:30
depend on lambda in some way.
34:35
And we want to make both e1 and e2 small--
34:39
the maximum of those-- of them.
34:42
And we have to do it for all the eigenvalues lambda,
34:47
because we have to--
34:48
we're now thinking-- we've been tracking each eigenvector.
34:54
So that gave us 1--
34:56
so this is for all possible lambda.
34:59
So we have to decide, what do I mean by all possible lambda?
35:03
And I mean all lambda that are between some m and M.
35:12
There is a beautiful problem.
35:17
You have a 2 by 2 matrix.
35:18
You can find its eigenvalues.
35:22
They depend on lambda.
35:24
And what we-- all we know about lambda is it's between m
35:27
and cap M. And also, they also depend on S and beta--
35:32
the two parameters we can choose.
35:35
And we want to choose those parameters,
35:37
so that for all the possible eigenvalues,
35:43
the larger of the two eigenvalues
35:45
will be as small as possible.
35:47
That's-- it's a little bit of algebra,
35:51
but do you see that that's the tricky--
35:54
that-- I shouldn't say tricky, because it comes out--
35:59
this is the one that is a miracle in the simplicity
36:03
of the solution.
36:05
OK.
36:05
And I'm going to--
36:07
in fact, maybe I'll move over here to write the answer.
36:10
36:13
OK.
36:16
And I just want to say that miracles
36:19
don't happen so often in math.
36:22
There is-- all of mathematics-- the whole point of math
36:26
is to explain miracles.
36:28
So there is something to explain here,
36:33
and I don't have my finger on it yet.
36:37
Because-- anyway, it happens.
36:41
So let me tell you what the right S, and the right beta,
36:45
and the resulting minimum eigenvalue are.
36:53
So again, they depend on little m and big M.
37:00
That's a very nice feature, which we expect.
37:05
And they depend on the ratio.
37:07
OK.
37:08
So that ratio-- all right.
37:09
Let's see it.
37:11
OK.
37:12
So the best S--
37:13
37:18
the S optimal has the formula 2 over square root of lambda max.
37:29
That's the square root of M and the squared of m squared.
37:37
Amazing OK.
37:38
And beta optimal turns out to be the square root of M
37:49
minus the square of little m, over the square root of M
37:53
plus the square root of little m, all squared.
37:57
And of course, we know what these numbers are--
37:59
1 and beta, in our model problem.
38:02
That's where I'm going to get this square root of--
38:06
this is 1 minus the square root-- oh sorry, b.
38:09
This is 1 minus the square root of b.
38:13
In fact, for our example--
38:17
well, let me just write what they would be.
38:19
2 over 1 plus square root of b squared,
38:25
and 1 minus square root of b over 1 plus square--
38:29
you see where this is--
38:33
1 minus square root of b is beginning to appear in that.
38:36
It appears in this solution to this problem.
38:38
And then I have to tell you what the--
38:41
38:45
how small do these optimal choices
38:49
make the eigenvalues of R, right?
38:52
This is what we're really paying attention to, because
38:57
if the eigenvalues--
38:59
that matrix tells us what happens at every step.
39:02
And its eigenvalues have to be small to get fast convergence.
39:06
So how small are they?
39:08
Well they involve this--
39:09
39:13
yeah.
39:13
So it's the number that I've seen.
39:17
So in this case, the e's--
39:21
the eigenvalues of R--
39:29
that's the iterating matrix--
39:32
are below-- now you're going to see the 1 minus square root
39:36
of b over 1 plus square root of b--
39:41
I think, maybe, squared.
39:43
Let me just see.
39:44
Yeah.
39:45
It happens to come out that number again.
39:50
So that's the conclusion.
39:53
That with the right choice of S and beta,
39:57
by adding this look back term-- look back one step--
40:03
you get this improvement.
40:05
And it happens, and you see it in practice, of course.
40:13
You'll see it exactly.
40:15
And so you do the job to use momentum.
40:26
Now I'm going to mention what the Nesterov--
40:30
Nesterov had a slightly different way to do it,
40:33
and I'll tell you what that is.
40:37
But it's the same idea-- get a second thing.
40:40
So let's see if I can find that.
40:42
Yeah, Nesterov.
40:44
OK.
40:44
40:51
Here we go.
40:53
So let me bring Nesterov's name down.
40:55
41:01
So that's basically what I wanted to say about number 1.
41:07
And when you see Nesterov, you'll
41:09
see that it's a similar idea of involving the previous time
41:14
value.
41:16
OK.
41:17
There are very popular methods in use now
41:24
for machine learning that involve--
41:28
by a simple formula--
41:29
all the previous values, by sort of a--
41:34
just by an addition of a bunch of terms.
41:36
So it's really-- so it goes under the names
41:44
adagrad, or others.
41:50
Those of you who already know about machine learning
41:54
will know what I'm speaking about.
41:55
And I'll say more about those.
41:58
Yeah.
41:59
But it doesn't involve a separate coefficient
42:02
for each previous value, or that would
42:05
be a momentous amount of work.
42:08
So now I just want to tell you what Nesterov is, and then
42:12
we're good.
42:13
OK.
42:13
Nesterov's idea.
42:14
42:18
Let me bring that down.
42:20
Shoot this up.
42:22
Bring down Nesterov.
42:23
42:31
Because he had an idea that you might not have thought of.
42:35
Somehow the momentum idea was pretty natural--
42:38
to use that previous value.
42:41
And actually, I would like to know
42:43
what happens if you use two previous values, or three
42:46
previous values.
42:47
Can you then get improvements on this convergence rate
42:57
by going back two steps or three steps?
43:00
If I'd use the analogy with ordinary differential
43:05
equations, maybe you know.
43:07
So there are backward difference formulas.
43:12
Do you know about those for--
43:14
those would be in MATLAB software,
43:18
and all other software.
43:20
Backward differences-- so maybe you
43:22
go back two steps or four steps.
43:27
If you're doing planetary calculations,
43:29
if you're an astronomer, you go back maybe seven or eight steps
43:33
to get super high accuracy.
43:35
So that doesn't seem to have happened yet,
43:40
but it's should happen here--
43:42
to go back more.
43:43
But Nesterov has this different way to go back.
43:48
So his formula is XK plus 1-- the new X--
43:52
is YK-- so he's introducing something a little different--
43:58
minus S gradient f at YK.
44:03
44:09
I'm a little surprised about that YK,
44:10
but this is the point, here--
44:13
that the gradient is being evaluated
44:15
at some different point.
44:18
And then he has to give a formula for that to track those
44:22
Y's.
44:23
So the Y's are like the X's, but they
44:27
are shifted a little bit by some term-- and beta would be fine.
44:33
Oh no.
44:35
Yeah-- beta-- have we got Nesterov here?
44:39
Yes.
44:40
Nesterov has a factor gamma in.
44:45
Yeah.
44:45
So all right.
44:47
Let me try to get this right.
44:50
OK.
44:52
All right.
44:53
On a previous line, I've written the whole Nesterov thing.
44:56
Here, let's see a Nesterov completely.
44:59
And then it'll break--
45:00
then this is the step that breaks it into two first order.
45:04
But you'll see the main formula here.
45:06
XK plus 1 is XK.
45:08
45:10
And then a beta times XK minus XK minus 1.
45:19
So that's a momentum term.
45:22
And then a typical gradient.
45:26
But now here is Nesterov speaking up.
45:29
Nesterov evaluates the gradient not at XK, not at XK minus 1.
45:35
But it his own, Nesterov point.
45:38
So this is Nesterov's favorite point.
45:41
Gamma XK minus XK minus 1.
45:46
Some point, part way along that step.
45:54
So this point-- because gamma is going to be some non-integer--
46:01
this evaluation point for the gradient of f
46:04
is a little unexpected and weird,
46:07
because it's not a mesh point.
46:09
It's somewhere between.
46:13
OK.
46:15
Yeah.
46:17
And then that-- so that involves XK plus 1, XK, and XK minus 1.
46:29
So it's a second order--
46:33
there's a second order method here.
46:35
We're going to-- to analyze it, we're going to go through this
46:39
same process of writing it as two first order steps--
46:45
two first-- two single step--
46:48
two one step from K to K plus 1 coupled with one step thing.
46:58
Follow that same thing through, and then the result
47:03
is, the same factor appears for him.
47:08
The same factor-- this is also--
47:11
so the point is, this is for momentum and Nesterov,
47:24
with some constant-- different by some constant.
47:33
But the key quantity is that one and that appears in both.
47:41
So I don't propose, of course, to repeat these steps
47:49
for Nesterov.
47:50
But you see what you could do.
47:54
You see that it involves K minus 1, KNK plus 1.
47:59
You write it as--
48:01
you follow an eigenvector.
48:03
You write it as a coupled system of-- that's a one step.
48:08
That has a matrix.
48:10
You find the matrix.
48:12
You find the eigenvalues of the matrix.
48:14
You make those eigenvalues as small as possible.
48:17
And you have optimized the coefficients in Nesterov.
48:22
OK.
48:22
That's sort of a lot of algebra that's
48:27
at the heart of accelerated gradient descent.
48:32
And of course, it's worth doing because it's
48:37
a tremendous saving in the convergence rate.
48:42
OK.
48:44
Anybody running in the marathon or just watching?
48:49
It's possible to run, you know.
48:53
Anyway, I'll see you after the marathon, next Wednesday.
48:57
And Professor Boyd will also see you.
English - CC (English)
###