22. Downhill to a Minimum
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...Gradient descent is the most common optimization algorithm in deep learning and machine learning. It only takes into account the first derivative when performing updates on parameters - the stepwise process that moves downhill to reach a local minimum. License: Creative Commons BY-NC-SA More information at https://ocw.mit.edu/termsMore courses at https://ocw.mit.edu
00:00
00:01
The following content is provided under a Creative
00:03
Commons license.
00:05
Your support will help MIT Open Courseware
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
00:16
MITopencourseware@ocw.MIT.edu.
00:18
00:24
GILBERT STRANG: So I'm going to talk about the gradient descent
00:29
today to get to that central algorithm
00:32
of neural net deep learning, machine learning,
00:38
and optimization in general.
00:40
So I'm trying to minimize a function.
00:43
And that's the way you do it if there are many, many variables,
00:50
too many to take second derivatives,
00:52
then we settle for first derivatives of the function.
00:56
So I introduced, and you've already
00:59
met the idea of gradient.
01:01
But let me just be sure to make some comments
01:04
about the gradient and the Hessian
01:07
and the role of convexity before we see the big crucial example.
01:15
So I've kind of prepared over here for this crucial example.
01:19
01:22
The function is a pure quadratic, two unknowns, x
01:26
and y, pure quadratic.
01:30
So every pure quadratic I can write in terms
01:34
of a symmetric matrix s.
01:37
And in this case, x1 squared was bx2 squared, the symmetric,
01:42
the matrix is just 2 by 2.
01:45
It's diagonal.
01:47
It's got eigenvalues 1 and b sitting on the diagonal.
01:52
I'm thinking of b as being the smaller one.
01:56
So the condition number, which we'll see,
02:00
is all important in the question of the speed of convergence
02:07
is the ratio of the largest to the smallest.
02:13
In this case, the largest is 1 the smallest is b.
02:17
So that's 1 over b.
02:19
And when 1 over b is a big number,
02:23
when b is a very small number, then that's
02:26
when we're in trouble.
02:27
02:31
When the matrix is symmetric, that condition number
02:34
is lambda max over lambda min.
02:37
If I had an unsymmetric matrix, I
02:40
would probably use sigma max over sigma min, of course.
02:44
But here, matrices are symmetric.
02:48
We're going to see something neat
02:52
is that we can actually take the steps of steepest descent,
02:58
write down what each step gives us,
03:01
and see how quickly they converge to the answer.
03:05
And what is the answer?
03:07
So I haven't put in any linear term here.
03:11
So I just have a bowl sitting on the origin.
03:14
So of course, the minimum point is x equal 0, y equals 0.
03:18
So the minimum point x star, is 0, 0, of course.
03:26
So the question will be how quickly do we get to that one.
03:29
And you will say pretty small example, not typical.
03:33
But the terrific thing is that we see
03:37
everything for this example.
03:38
We can see the actual steps of steepest descent.
03:43
We can see how quickly they converge
03:45
to the x star, the answer, the place
03:50
where this thing is a minimum.
03:52
And we can begin to think what to do if it's too slow.
04:01
So I'll come to that example after some general thoughts
04:06
about gradients, Hessians.
04:09
So what does the gradient tell us?
04:12
So let me just take an example of the gradient.
04:14
04:17
Let me take a linear function, f of xy equals say, 2x plus 5y.
04:23
04:26
I just think we ought to get totally familiar with these.
04:31
We're doing something.
04:33
We're jumping into an important topic.
04:38
When I ask you what's the gradient,
04:41
that's a freshman question.
04:43
But let's just be sure we know how to interpret the gradient,
04:48
how to compute it, what it means,
04:51
how to see it geometrically.
04:54
So what's the gradient of that function?
04:56
It's a function of two variables.
04:58
So the gradient is a vector with two components.
05:02
And they are?
05:02
05:07
The derivative of this factor x, which
05:09
is 2 and the derivative of this factor y, which is 5.
05:13
So in this case, the gradient is constant.
05:17
And the Hessian, which I often call H after Hessian,
05:22
or del squared F would tell us we're
05:25
taking the second derivatives, that
05:27
will be the second derivatives obviously 0 in this case.
05:33
So what shape is H here?
05:38
It's 2 by 2.
05:39
Everybody recognizes 2 by 2 is H would have the--
05:45
I'll take a second derivative of that--
05:49
sorry, the first derivative of that with respect to x,
05:52
obviously 0, the first derivative with respect
05:54
to y, the first derivative of that with respect to x y.
06:00
Anyway, Hessian 0 for sure.
06:04
So let me draw the surface.
06:08
So x, y, and the surface, if I graph F in this direction,
06:13
then obviously, I have a plane.
06:16
And I'm at a typical point on the plane let's say.
06:20
Yeah, yeah.
06:21
So I'm at a point x, y, I should say.
06:24
I'm at a point x, y.
06:25
And let me put the plane through it.
06:28
So how do I interpret the gradient
06:30
at that particular point x, y?
06:32
06:35
What does 2x plus 5y tell me?
06:38
Or rather what does grad F tell me about movement
06:46
from that point x, y?
06:50
Of course, the gradient is constant.
06:52
So it really didn't matter what point I'm moving from.
06:55
But taking a point here.
06:57
So what's the deal if I move?
07:00
What's the fastest way to go up the surface?
07:04
If I took the plane that went through that point x, y,
07:09
what's the fastest way to climb the plane?
07:11
What direction goes up fastest?
07:14
The gradient direction, right?
07:16
The gradient direction is the way up.
07:19
How am I going to put it in this picture?
07:22
I guess I'm thinking of this plane as--
07:26
so what plane?
07:27
You could well ask what plane have I drawn?
07:30
Suppose I've drawn the plane 2x plus 5y equals 0 even?
07:39
So I'll make it go through the arc.
07:41
And I've taken a typical point on that plane.
07:44
Now if I want to increase that function,
07:48
I go perpendicular to the plane.
07:52
If I want to stay level with the function,
07:54
if I wanted to stay at 0, I stay in the plane.
07:58
So there are two key directions.
08:00
Everybody knows this.
08:01
I'm just repeating.
08:03
This is the direction of the gradient of F out
08:08
of the plane, steepest upwards.
08:10
This is the downwards direction minus gradient
08:13
of F, perpendicular to the plane downwards.
08:16
And that line is in the plane.
08:21
That's part of the level set.
08:23
2x plus 5y equals 0 would be a level set.
08:28
That's my pretty amateur picture.
08:32
Just all I want to remember is these words level and steepest,
08:45
up or down.
08:49
Down with a minus sign that we see in steepest descent.
08:54
So where in steepest descent.
08:58
09:03
And what's the Hessian telling me about the surface
09:08
if I take the matrix of second derivatives?
09:12
So I have this surface.
09:14
So I have a surface F equal constant.
09:18
09:22
That's the sort of level surface.
09:25
So if I stay in that surface, the gradient of F is 0.
09:29
Gradient of F is 0 in--
09:33
09:36
on-- on is a better word--
09:39
on the surface.
09:39
09:43
The gradient of F points perpendicular.
09:46
But what about the Hessian, the second derivative?
09:58
What is that telling me about that surface
10:03
in particular when the Hessian is 0 or other surfaces?
10:07
What does the Hessian tell me about--
10:10
10:13
I'm thinking of the Hessian at a particular point.
10:16
So I'm getting 0 for the Hessian because the surface is flat.
10:25
If the surface was convex upwards from--
10:34
if it was a convex or a graph of F, the Hessian would be--
10:41
10:46
so I just want to make that connection now.
10:48
What's the connection between the Hessian and convexity
10:54
of the--
10:55
the Hessian of the function and convexity of the function?
11:00
So the point is that convexity--
11:06
the Hessian tells me whether or not the surface is convex.
11:10
And what is the test?
11:11
AUDIENCE: [INAUDIBLE].
11:12
GILBERT STRANG: Positive definite or semi definite.
11:16
I'm just looking for an excuse to write down
11:20
convexity and strong.
11:26
Do I say strict or strong convexity?
11:29
I've forgotten.
11:30
Strict, I think.
11:32
Strictly convex.
11:33
11:38
So convexity, the Hessian is positive semi-definite,
11:45
or which includes--
11:48
I better say that right here--
11:49
includes positive definite.
11:52
11:58
If I'm looking for a strict convexity,
12:00
then I must require positive definite.
12:03
H is positive definite.
12:05
12:09
Semi-definite won't do.
12:12
So semi-definite for convex.
12:15
So that in fact, the linear function
12:18
is convex, but not strictly convex.
12:22
Strictly means it really bends upwards.
12:25
The Hessian is positive definite.
12:26
The curvatures are positive.
12:31
So this would include linear functions,
12:34
and that would not include linear function.
12:37
They're not strictly convex.
12:40
Good, good, good.
12:42
Some examples-- OK, the number one example, of course,
12:46
is the one we're talking about over here.
12:49
So examples f of x equal 1/2 x transpose Sx.
12:59
13:03
And of course, I could have linear terms
13:05
minus a transpose x, a linear term.
13:10
And I could have a constant.
13:12
OK.
13:13
13:18
So this function is strictly convex
13:23
when S is positive definite, because H is now
13:28
S for that function, for that function
13:33
H. Usually H, the Hessian is varying from point to point.
13:39
The nice thing about a pure quadratic is its constant.
13:42
It's the same S at all points.
13:46
Let me just ask you--
13:49
so that's a convex function.
13:53
And what's its minimum?
13:56
What's the gradient, first of all?
13:57
What's the gradient of that?
13:59
14:03
I'm asking really for differentiating
14:09
thinking in vector, doing all n derivatives at once here.
14:14
I'm asking for the whole vector of first derivatives.
14:19
Because here I'm giving you the whole function
14:24
with x for vector x.
14:28
Of course, we could take n to be 1.
14:31
And then we would see that if n was 1,
14:33
this would just be Sx squared, half Sx squared.
14:39
And the derivative of a half Sx squared--
14:44
let me just put that over here so we're
14:46
sure to get it right-- half of Sx squared.
14:48
This is in the n equal 1 case.
14:51
And the derivative is obviously Sx.
14:53
And that's what it is here, Sx.
14:55
15:06
It's obviously simple, but if you
15:10
haven't thought about that line, it's
15:14
asking for all the first derivatives
15:18
of that quadratic function.
15:20
Oh!
15:21
It's not-- What do I have to include now here?
15:27
That's not right as it stands for the function that's
15:31
written above it.
15:32
What's the right gradient?
15:33
AUDIENCE: [INAUDIBLE].
15:34
GILBERT STRANG: Minus a, thanks.
15:38
Because the linear function, its partial derivatives
15:41
are obviously just the components of a.
15:45
And the Hessian H is S, derivatives of that guy.
15:56
OK.
15:56
Good.
15:57
Good, good, good.
15:59
And the minimum value-- we might as well-- oh yeah!
16:02
What's the right words for a minimum value?
16:07
No, I'm sorry.
16:09
The right word is minimum value like f min.
16:14
So I want to compute f min.
16:17
Well, first I have to figure out where is that minimum reached?
16:23
And what's the answer to that?
16:27
We're putting everything on the board for this simple case.
16:30
The minimum of f of f of f of x--
16:38
remember, it's x is-- we're in n dimensions--
16:42
is at x equal what?
16:49
Well, the minimum is where the gradient is 0.
16:52
16:55
So what's the minimizing x?
16:59
S inverse a, thanks.
17:01
17:08
Sorry.
17:09
That's not right.
17:12
It's here that I meant to write it.
17:14
17:17
Really, my whole point for this little moment
17:20
is to be sure that we keep straight what
17:23
I mean by the place where the minimum is reached
17:27
and the minimum value.
17:29
Those are two different things.
17:30
17:34
So the minimum is reached at S inverse
17:36
a, because that's obviously where the gradient is 0.
17:40
It's the solution to Sx equal a.
17:43
And what I was going to ask you is what's the right word--
17:48
well, sort of word, made up word-- for this point x star
17:56
where the minimum is reached?
17:58
So it's not the minimum value.
18:00
It's the point where it's reached.
18:01
And that's called-- the notation for that point is
18:06
AUDIENCE: Arg min.
18:06
GILBERT STRANG: Arg min, thanks.
18:10
Arg min of my function.
18:16
And that means the place--
18:18
the point where f equals f min.
18:24
18:28
I haven't said yet what the minimum value is.
18:30
This tells us the point.
18:31
And that's usually what we're interested in.
18:34
We're, to tell the truth, not that
18:36
interested in a typical example and what the minimum value
18:40
is as much as where is it?
18:43
Where do we reach that thing?
18:46
And of course, so this is x min.
18:50
This is then arg min of my function f.
19:00
That's the point.
19:00
And it happens to be in this case,
19:04
the minimum value is actually 0.
19:06
19:11
Because there's no linear term a transpose x.
19:15
19:20
Why am I talking about arg min when you've all seen it?
19:26
I guess I think that somebody could just
19:28
be reading this stuff, for example, learning
19:34
about neural net, and run into this expression arg min
19:40
and think what's that?
19:43
So it's maybe a right time to say what it is.
19:47
It's the point where the minimum is reached.
19:50
19:52
Why those words, by the way?
19:55
Well, arg isn't much of a word.
19:57
It sounds like you're getting strangled.
20:00
But it's sort of short.
20:03
I assume it's short.
20:05
Nobody ever told me this.
20:07
I assume it's short for argument.
20:10
The word argument is a kind of long word for the value of x.
20:15
If I have a function f of x, f, I
20:18
call it function and x is the argument of that function.
20:23
You might more often see the word variable.
20:27
But argument-- and I'm assuming that's what that refers to,
20:31
it's the argument that minimizes the function.
20:35
OK, good.
20:37
And here it is, S inverse a.
20:41
Now but just by the way, what is f min?
20:43
Do you know the minimum of a quadratic?
20:45
I mean, this is the fundamental minimization question,
20:49
to minimize a quadratic.
20:52
Electrical engineering, a quadratic regulator problem
20:56
is the simplest problem there.
20:58
There could be constraints.
20:59
And we'll see it with constraints included.
21:03
But right now, no constraints at all.
21:06
We're just looking at the function f of x.
21:08
21:11
Let me to remove the b, because that just
21:15
shifts the function by b.
21:18
If I erase that, just to say it didn't matter.
21:22
It's really that function.
21:25
So that function actually goes through 0.
21:28
As it is, when x is 0, we obviously get 0.
21:32
But it's still on its way down, so to speak.
21:35
It's on its way down to this point, S inverse a.
21:40
That's where it bottoms out.
21:42
And when it bottoms out, what do you get for f?
21:47
One thing I know, it's going to be negative
21:49
because it passed through 0, and it was on its way below 0.
21:53
So let's just figure out what that f min is.
21:57
So I have a half.
22:00
I'm just going to plug in S inverse a, the bottom point
22:05
into the function, and see where the surface bottoms out
22:11
and at what level it bottoms out.
22:15
So I have a half.
22:17
So that's S inverse a is a transpose S inverse.
22:23
S symmetric, so I'll just write this inverse transpose.
22:26
S, S inverse a from the quadratic term,
22:33
minus a transpose.
22:37
And x is S inverse a.
22:40
Have you done this calculation?
22:42
It just doesn't hurt to repeat it.
22:46
So I've plugged in S inverse a there, there, and there.
22:53
OK, what have I got?
22:55
Well, S inverse cancels S. So I have
22:58
a half of a transpose S inverse a minus 1
23:02
of a transpose inverse a.
23:04
So I get finally negative a half.
23:08
Half of it minus one of it of a transpose S inverse a.
23:15
Sorry, that's not brilliant use of the blackboard
23:19
to squeeze that in there.
23:21
But that's easily repeatable.
23:26
OK, good.
23:29
So that's what a quadratic bowl, a perfect quadratic problem
23:34
minimizes to that's its lowest level.
23:40
Ooh, I wanted to mention one other function,
23:45
because I'm going to speak mostly about quadratics,
23:48
but obviously, the whole point is
23:51
that it's the convexity that's really making things work.
23:56
So here, let me just put here, a remarkable convex function.
24:07
24:11
And the notes tell what's the gradient of this function.
24:20
They don't actually go as far as the Hessian.
24:24
Proving that this function I'm going to write down is convex,
24:32
it takes a little thinking.
24:34
But it's a fantastic function.
24:37
You would never sort of imagine it
24:41
if you didn't see it sometime.
24:44
So it's going to be a function of a matrix, a function of--
24:48
those are n squared variables, x, i, j.
24:58
So it's a function of many variables.
25:01
And here is this function.
25:03
It's you take the determinant of the matrix.
25:07
That's clearly a function of all the n squared variables.
25:11
Then you take the log of the determinant
25:15
and put in a minus sign because we want convex.
25:21
That turns out to be a convex function.
25:24
And even to just check that for 2 by 2 well, for 2 by 2
25:29
you have four variables, because it's a 2 by 2 matrix.
25:32
We could maybe check it for a symmetric matrix.
25:35
I move it down to three variables.
25:37
But I'd be glad anybody who's ambitious to see
25:45
why that log determinant is a remarkable function.
25:51
And let me see.
25:52
25:56
So the gradient of that thing is also amazing.
26:01
The gradient of that function--
26:06
I'm going to peek so I don't write the wrong fact here.
26:11
26:15
So the partial derivative of that function
26:19
are the entries of--
26:23
these are the entries of a, a inverse.
26:26
That's the-- of x inverse.
26:27
26:38
That's like, wow.
26:39
Where did that come from?
26:42
It might be minus the entries, of course.
26:45
Yeah, yeah, yeah.
26:46
So we've got n squared function--
26:53
what is a typical entry in x inverse?
26:56
What does a typical x inverse i, j?
27:02
Just to remember that bit of pretty
27:05
old fashioned linear algebra, the entry
27:09
is of the inverse matrix, I'm sure to divide by what?
27:14
The determinant, that's the one thing we know.
27:17
27:21
And that's the reason we take the log,
27:24
because when you take derivatives of a log,
27:27
that will put determinant of x in the denominator.
27:31
And then the numerator will be the derivatives
27:33
of the determinant of x.
27:36
Oh!
27:36
Can we get any idea what are the derivatives of the determinant?
27:41
Oh my god.
27:43
How did I never get into this?
27:46
So are you with me so far?
27:50
This is going to be derivatives of determinant,
27:54
the strength of all these variables divided
27:58
by the determinant, because that's what the log achieved.
28:02
So when I take the derivative of the log of something,
28:04
that chain rule says take the derivative of that something
28:12
divide by the function determinant of x.
28:15
So what's the derivative of the determinant of a matrix
28:20
with respect to its 1, 1 entry?
28:22
Yeah, sure.
28:23
This is crazy.
28:24
But it's crazy to be doing this.
28:26
But it's healthy.
28:28
OK.
28:28
28:31
So I have a matrix x, da, da, da, x, x, 1, 1, x, 1n,
28:38
et cetera, xn, 1, x, n, n.
28:43
OK.
28:45
And what am I looking for?
28:46
I'm looking for that for the derivatives of the--
28:52
do I want the derivatives of the determinant?
28:55
Yes.
28:57
So what's the derivative of x of the determinant with respect
29:05
to the first equals what?
29:10
29:13
How can I figure out?
29:15
So what's this asking me to do?
29:17
It's asking me to change x, 1, 1 by delta x and see what's
29:22
the change in the determinant.
29:25
That's what derivatives are.
29:28
Change x, 1, 1 a little bit.
29:31
How much did the determinant change?
29:32
29:36
What has the determinant of the whole matrix
29:39
got to do with x, 1, 1?
29:42
You remember that there is a formula for determinants.
29:47
So I need that fact.
29:49
The determinant of x is x, 1, 1 times something.
29:55
Is that something that I really want to know?
29:58
Plus x, 1, 2 times other something plus
30:01
say, along the first row times another something.
30:06
30:09
What are these factors that multiply
30:15
the x's to give the determinant?
30:19
What [INAUDIBLE] a linear combination
30:22
of the first row time certain factors gives the determinant?
30:27
And how do I know that there will be such factors,
30:30
because the fundamental property of the determinant
30:33
is that it's linear in row 1 if I don't mess with other rows.
30:39
It's a linear function of row 1.
30:43
So it has a form x, 1, 1 times something.
30:46
And what is something?
30:48
AUDIENCE: [INAUDIBLE].
30:49
GILBERT STRANG: The determinant of this.
30:52
So what does x, 1, 1 multiply when you compute determinants?
30:56
X, 1, 1 will not multiply any other guys in its row,
31:00
because you're never multiplying two
31:02
x's in the same row or the same column.
31:06
What x, 1, 1 is multiplying all these guys.
31:10
And in fact, it turns out to be is the determinant.
31:15
And what is this called?
31:17
That one smaller determinant that I get by throwing away
31:22
the first row and first column?
31:24
It's called a--
31:27
Minor is good.
31:28
Yes, minor is good.
31:30
I was saying there are two words that can be used,
31:33
minor and co-factor.
31:36
31:42
Yeah.
31:43
And what is it?
31:44
I mean, how do I compute it?
31:46
What is the number?
31:47
This is a number.
31:48
31:51
It's just a number.
31:52
31:56
Maybe I think of the minor as this determinant--
32:01
Ah!
32:01
Let me cancel that.
32:03
Maybe I think of the minor as this smaller
32:05
matrix, and the co-factor, which is
32:08
the determinant of the minor.
32:10
32:15
And there is a plus or minus.
32:16
Everything about determinants, there's
32:20
a there's a plus or minus choice to be made.
32:23
And we're not going to worry about that.
32:27
But so anyway, so it's the co-factor.
32:33
Let me call it C, 1, 1.
32:35
32:37
And so that's the formula for a determinant.
32:42
That's the co-factor expansion of a determinant.
32:46
32:54
OK.
32:56
And that will connect back to this amazing fact
32:59
that the gradient is the entries of x inverse,
33:02
because the inverse is the ratio of co-factor to determinant.
33:07
So x inverse 1, 1 is that co-factor over the determinant.
33:15
33:18
Yeah.
33:20
So that's where this all comes from.
33:22
Anyway, I'm just mentioning that as a very interesting example
33:32
of a convex function.
33:35
OK.
33:37
I'll leave that.
33:37
That's just for like, education.
33:41
OK.
33:43
Now I'm ready to go to work on gradient descent.
33:48
So actually, the rest of this class and Friday's class
33:52
about gradient descent are very fundamental parts of 18.065.
33:59
And that will be one of our examples.
34:01
And then the general case here.
34:06
So I'm using this.
34:11
It would be interesting to minimize that thing,
34:13
but we're not going there.
34:15
Let's hide it, so we don't see it again.
34:20
And I'll work with that example.
34:23
34:26
So here's gradient descent.
34:28
34:37
Is xk plus 1 is xk minus Sk the step size
34:45
times the gradient of f at xk.
34:47
34:52
So the only thing left that requires
34:56
us to input some decision making is a step size, the learning
35:01
rate.
35:03
We can take it as constant.
35:06
If we take too big a learning rate,
35:09
the thing will oscillate all over the place
35:12
and it's a disaster.
35:16
If we take too small a learning rate, too small steps,
35:19
what's the matter with that?
35:22
Takes too long.
35:24
Takes too long.
35:26
So the problem is to get it just right.
35:30
And one way that you could say get it right
35:32
would be to think of optimize.
35:37
Choose the optimal Sk.
35:38
Of course, that takes longer than just deciding an Sk
35:43
in advance, which is what people do.
35:46
So I'll tell you what people do is on really big problems is
35:51
take an Sk--
35:53
estimate a suitable Sk, and then go with it for a while.
35:57
And then look back to see if it was too big,
36:02
they'll see oscillations.
36:05
It'll be bouncing all over the place.
36:09
Or of course, an exact line search--
36:13
36:16
so you see that this expression often.
36:19
The exact line search choose Sk to make my function
36:30
f at xk plus 1 a minimum on the line, on the search line,
36:44
a minimum in the search direction.
36:48
36:54
The search direction is given by the gradient.
36:57
That's the direction we're moving.
36:59
This is the distance we're moving,
37:02
or measure of the distance we're moving.
37:05
And an exact search would be to go along there.
37:09
If I have a convex function, then as I move along this line,
37:14
as I increase Sk, I'll see the function start down,
37:19
because the gradient, negative gradient means down.
37:25
But at some point it'll turn up again.
37:28
And an exact line search would find that point and stop there.
37:33
37:36
That doesn't mean we would--
37:38
we will see in this example where
37:40
we will do exact line searches that for a small value of b,
37:46
it's extremely slow, that the condition number controls
37:51
the speed.
37:52
That's really what my message will
37:55
be just in these last minutes and next time
37:59
the sort of key lecture on gradient descent.
38:03
So an exact line search would be that.
38:06
So what a backtracking line search--
38:09
38:15
backtracking would be take a fixed S like one.
38:24
And then be prepared to come backwards.
38:32
Cut back by half.
38:34
See what you get at that point.
38:36
Cut back by half of that to a quarter of the original step.
38:40
See what that is.
38:41
38:44
So the full step might have taken you back
38:48
to the upward sweep.
38:52
Halfway forward it might still be on the upward sweep.
38:55
Might be too much, but so backtracking cuts the step size
39:00
in pieces and checks until it--
39:04
39:08
So S0, half of S0, quarter of S0,
39:13
or obviously, a different parameter, aS0, a squared S0,
39:18
and so on until you're satisfied with that step.
39:25
And there are of course, many, many refinements.
39:28
We're talking about the big algorithm
39:31
here that everybody has, depending on their function,
39:40
has different experiences with.
39:44
So here's my fundamental question.
39:46
39:50
Let's think of an exact line search.
39:53
How much does that reduce the function?
39:57
How much does that reduce the function?
40:00
So that's really what the bounds that I want are.
40:05
How much does that reduce the function?
40:08
And we'll see that the reduction involves the condition number,
40:24
m over M. So why don't I turn to the example first?
40:32
And then where we know exact answers.
40:37
That gives us a basis for comparison.
40:39
And then our math goal is prove--
40:46
get S dead bounds on the size of f
40:50
that match what we see exactly in that example
40:55
where we know everything.
40:58
We know the gradient.
41:01
We know the Hessian.
41:03
It's that matrix.
41:04
We know the condition number.
41:05
So what happens if I start at a point
41:08
x0 y0 that's on my surface?
41:15
41:19
Sorry.
41:20
What do I want to do here?
41:22
Yeah.
41:23
I take a point, x0 y0 and I iterate.
41:31
41:34
So the new xy k plus 1 is xyk minus the S,
41:54
which I can compute times the gradient of f.
41:56
So I'm going to put in gradient f.
41:58
What is the gradient here?
42:00
42:02
The derivative is we expect to x.
42:05
So I have a 2xk and 2by.
42:11
42:16
And this is the step size.
42:18
42:22
And for this small problem where we're
42:25
going to get such a revealing answer,
42:27
I'm going to choose exact line search.
42:29
I'm going to choose the best xk.
42:31
42:34
And what's the answer?
42:35
So I just want to tell you what the iterations are
42:39
for that particular function starting at x0 y0.
42:43
42:46
So let me put start x0 y0.
42:51
42:54
And I haven't done this calculation myself.
42:56
It's taken from the book by Steven Boyd and Vandenberghe
43:01
called Convex Optimization.
43:03
Of course, they weren't the first to do this either.
43:06
But I'm happy to mention that book Convex Optimization.
43:11
And Steven Boyd will be on campus this spring
43:14
actually, in April for three lectures.
43:18
This is April, maybe.
43:20
Yeah, OK.
43:21
So it's this month in two or three weeks.
43:24
And I'll tell you about that.
43:26
So here are the xk's and the yk's and the f and the function
43:34
values.
43:35
43:40
So where am I going to start?
43:41
43:44
Yeah.
43:45
So I'm starting from the point x0 y0 equal b1.
43:50
Turns out that will make our formulas very convenient,
43:54
x0 y0 equals b1.
43:57
Good.
43:58
So OK.
44:00
So xk is b times the key ratio b minus 1 over b plus 1
44:09
to the kth power.
44:11
And yk happens to be--
44:15
44:20
it has this same ratio.
44:24
And my function f has the same ratio too.
44:29
This is fk.
44:30
It has that same ratio 1 minus b over 1
44:34
plus b to the kth times f0.
44:39
That's the beautiful formula that we're
44:51
going to take as the best example possible.
44:54
Let's just see.
44:55
If k equals 0, I have xk equal b yk equal 1 b starting at b1.
45:04
And that tells me the rate of decrease of the function.
45:09
It's this same ratio.
45:11
So what am I learning from this example?
45:14
What's jumping out is that this ratio 1 minus b over 1 plus b
45:20
is crucial.
45:20
45:25
If b is near 1, that ratio is small.
45:29
If b is near 1, that's near 0 over 2.
45:32
And I converge quickly, no problem at all.
45:36
But if b is near 0, if my condition number is bad--
45:42
so the bad case, the hard case is small b.
45:51
45:55
Of course, when b is small, that ratio is very near 1.
46:01
It's below 1.
46:02
The ratio is below 1, so I'm getting convergence.
46:06
I do get convergence.
46:07
I do go downhill.
46:09
But what happens is I don't go downhill very far until I'm
46:13
headed back uphill again.
46:15
So the picture to draw for this--
46:20
let me change that picture to a picture in the xy
46:26
plane of the level sets.
46:29
So the picture really to see is in the xy plane.
46:33
The level sets f equal constant.
46:37
That's what a level set is.
46:38
It's a set of points, x and y where f has the same value.
46:43
And what do those look like?
46:46
Oh, let's see.
46:48
46:50
I think-- what do you think?
46:53
What do the level sets look like for this particular function?
46:59
If I look at the curve x squared plus b y squared equal
47:04
a constant, that's what the level set is.
47:07
This is x squared plus by squared equal a constant.
47:13
What kind of a curve is that?
47:16
AUDIENCE: [INAUDIBLE].
47:17
GILBERT STRANG: That's an ellipse.
47:19
And what's up with that ellipse?
47:21
What's the shape of it?
47:24
Because there is no xy term, that ellipse
47:27
is like, well lined up with the axes.
47:33
The major axes of the ellipse are in the x and y directions,
47:37
because there is no cross term here.
47:42
We could always have diagonalized our matrix
47:46
if it wasn't diagonal.
47:47
And that wouldn't have changed anything.
47:49
So it's just rotating this space.
47:52
And we've done that.
47:54
47:57
What do the levels set look like?
47:59
They're ellipses.
48:00
And suppose b is a small number, then what's with the ellipses?
48:06
If b is small, I have to go pretty--
48:10
I have to take a pretty large y to match a--
48:14
change an x.
48:15
I think maybe they're ellipses of that sort.
48:18
Are they?
48:18
48:24
They're lined up for the axes.
48:26
And I hope I'm drawing in the right direction.
48:30
They're long and thin.
48:33
Is that right?
48:34
Because I would have to take a pretty big y
48:36
to make up for a small b.
48:40
OK.
48:41
So what happens when I'm descending?
48:44
This is a narrow valley then.
48:45
Think of it as a valley which comes down steeply
48:52
in the y direction, but in the x direction
48:54
I'm crossing the valley slow--
48:57
Oh, is that right?
49:00
So what happens if I take a point there?
49:04
Oh yeah, I remember what to do.
49:06
So let's start at that point on that ellipse.
49:10
49:14
And those were the levels sets f equal constant.
49:17
So what's the first search direction?
49:20
What direction do I move from x0 y0?
49:23
49:28
Do I move along the ellipse?
49:31
Absolutely not, because along the ellipse f is constant.
49:35
The gradient direction is perpendicular to the ellipse.
49:39
So I move perpendicular to the ellipse.
49:42
And when do I stop?
49:43
49:47
Pretty soon, because very soon I'm going back up again.
49:50
50:02
I haven't practiced with this curve.
50:04
But I know-- and time is up, thank God.
50:08
So what do I know is going to happen?
50:10
And by Friday we'll make it happen?
50:13
So what do we see for the curve, the track of the--
50:22
it's say it?
50:24
AUDIENCE: Zigzag.
50:25
GILBERT STRANG: It's a zigzag, yeah.
50:28
We would like to get here, but we're not aimed here at all.
50:31
So we zig, zig, zig zag, and very slowly approach
50:36
that point.
50:36
50:39
And how slowly?
50:41
With that multiplier, 1 minus b over 1 plus b.
50:48
That's what I'm learning from this example,
50:51
that that's a key number.
50:53
And then you could ask, well, what about general examples?
50:56
This was one specially chose an example with exact solution.
51:01
Well, we'll see at the beginning of next time
51:04
that for a convex function this is typical.
51:08
This is 1 minus b is the critical quantity, or 1 over b,
51:14
or the how small is b compared to 1?
51:17
So that will be the critical quantity.
51:20
And we see it in this ratio 1 minus b over 1 plus b.
51:24
So if b is 100, this is 0.99 over 1.01.
51:30
It's virtually 1.
51:31
OK.
51:32
So next time is a sort of a key lecture
51:36
to see what I've just said, that this controls
51:43
the convergence of steepest descent,
51:46
and then to see an idea that speeds it up.
51:51
That idea is called momentum or heavy ball.
51:54
So the physical idea is if you had a heavy ball right there
52:02
and wanted to get it down the valley toward the bottom,
52:06
you wouldn't go perpendicular to the level sets.
52:10
Not at all.
52:11
You'd let the momentum of the ball take over
52:13
and let it roll down.
52:16
So the idea of momentum is to model the possibility
52:21
of letting that heavy ball roll instead of directing it
52:26
by the steepest descent at every point.
52:30
So there's an extra term in steepest descent, the momentum
52:34
term that accelerates.
52:36
OK.
52:36
So Friday is the day.
52:39
Good.
52:40
See you then.
52:42
English - CC (English)
###