[MUSIC]
But before we get to how to minimize residual sum of squares in particular,
let's talk about optimization in a more abstract sense.
In terms of just a generic function and thinking about how do we minimize it,
what are the properties of the minimum of a function and algorithms for
achieving that minimum?
One of the first important concepts that we can talk about is the notion of convex
and concave functions.
So here, I have a picture of a concave function over
just one variable, we'll call it w.
And this function here, this is g(w).
And this is a concave function, and the way I remember concave versus convex,
is concave it looks like you're in a cave, so it looks like the arch of a cave.
And convex is just the other one.
So, the way we can think about defining what a concave
function is, we can look at any two values of w.
Let's call it a and b.
And look at the value of the function at a and b.
So g(a) and g(b).
And let's draw a line between g(a) and g(b).
So that's this green line here.
And what we see is that this line
lies below g(w) everywhere.
And a concave function is function where for any value of a and any value
of b that you choose, when you go and draw this little line between the points of
the function, it's always gonna lie below the actual curve of the function itself.
A convex function,
on the other hand, let's just draw a little picture of a convex function.
It has exactly the same, but opposite, so not the same.
It has exactly the opposite property.
Where if you choose any a and any b, so
just to be clear this is w, this is g(w).
If I go and connect g(a) with
g(b), with just a line, and
this line is above g(w), everywhere.
Okay, so that's the very intuitive geometric definition of what a concave or
convex function is.
But then of course there are functions that are neither concave nor convex.
So, let me just draw two examples here.
Here's an example of a function that is not concave nor convex.
And how do we see that?
Well, let's look at a point a and
a point b, and draw a line between these points.
And we see that this line lies both below the curve here and above the curve here.
So it doesn't satisfy either the concave or convex criteria.
And likewise this function Has the same property, a and b.
Draw our little line, which okay I didn't draw that well at all.
Let me try and draw a straight line.
But I think you get the point, that neither of these functions are concave,
nor convex.
Okay, so that's the notion of defining what a concave or convex function is.
But we're looking at an optimization objective,
where either our goal is to find the minimum or maximum of a function.
So typically if we're looking at a concave function, our interest is
in finding the maximum, and for convex it's in finding the minimum.
So let's look at, what is the maximum of this concave function?
Well, that's just this point right here.
So that is the maximum.
And [COUGH] here, what I'm saying is
our goal is max over all w, g(w).
In terms of the notation that we introduced a little bit earlier.
And so what's the property of this concave function at this point?
Well what we know is that this is the point where the derivative is 0.
So there's no rate of change of this function at this point.
And what about a convex function?
If we're seeking to find min over all w g(w),
well the minimum is clearly this point right here.
And again, what's the property?
Same thing, derivative = 0.
And note that for the concave and convex functions,
there's only one place where the derivative = 0.
In contrast, when we look at the two examples for functions that were neither
concave nor convex that we showed on the previous slide.
What we see is in this case, for example,
they're multiple locations where you have the derivative equaling 0.
So, let's write that explicitly and
say that there are multiple
solutions to derivative = 0.
In contrast for this function there's actually no solution to derivative = 0.
The derivative is nowhere near 0.
The function continuously has a rate of change.
So, no solution
To derivative = 0.
Okay, so the key take home message here,
is the reason we're talking about concave and convex functions is the fact that when
we have an objective to find the minimum or the maximum.
Minimum of a convex, maximum of a concave.
The solution to that is gonna be unique, and we know that it's gonna exist.
[MUSIC]