https:/.../2019-05-13_opv1_caramanis_5.7_mirror_descent3.mp4

♪ (Music) ♪

Welcome back. This is our third lecture
in the series, talking about

mirror descent.

And um, we're going to get down to
the main definition of how it is that

we change the proximal term
in uh, from the subgradient method.

So again, recall that the subgradient
method tells me that xt plus one is

equal to xt minus eta gt, where gt is
an element of the subdifferential

of f at xt.

Again, I've said this in each
of these lectures, but I'm leaving

out the dependence on the
on the,

one the - set constraint,

but with the set constraint,
this would take the form

of an additional projection.

So xt plus one is equal to the projection
onto x, the projection here means

the Euclidean projection, of xt minus
eta gt.

But because it doesn't change very
much, for now,

I've just been sparing myself the
extra writing,

but we should really have this in mind.

And, uh, we've seen repeatedly, this
has been the theme of the first two

lectures on mirror descent, that
xt plus one is also

equivalently, just the argmin
of eta, gt, transpose x, plus,

this is the linear - you can think of this
as the linear approximation

to the function, plus something that
keeps us from going too far, and this

is typically the Euclidean norm, or
specifically, when we use the

Euclidean norm, we get exactly the
subgradient method.

Set constraint here, this is an
argmin over all x, but if I have a

set constraint, it just becomes -
the only thing that changes is

this is an argmin over x in my
set constraint.

So again, not much has changed.

So, we're going to change this.

And by changing it, we get
mirror descent, and we'll see

exactly when we can do this to
our advantage.

In order to do this, and to
explain what will replace it,

we need to define this concept
of Bregman divergence.

For a convex function phi,

I can define its Bregman
divergence as follows.

So the divergence with respect
to phi, between two points x and y,

is defined as phi of x minus
phi of y, minus the gradient of phi

of y transpose times x minus y.

So what does this mean?

It actually has a very simple
interpretation.

And let me group these terms
as follows.

Let me group the second and third
term, and then I'll have to distribute

that minus sign, in order to make
this plus.

So now, a simple picture tells
us exactly what this is.

If phi is a convex function, and
I've got my point y, and I've

got my point x, then what is
the first term?

The first term is just phi of
x, it's sitting up there.

What's the second term?

We can interpret the second
term as the linear approximation

to phi at y,

evaluated at the point x.

So this is the second term.

This is phi of y plus the gradient
of phi of y transpose x minus y.

And therefore, the Bregman
divergence is exactly this term.

Making things a little messy
here, so let's see.

One more try.

This is exactly the Bregman
divergence.

The more curvature something has,
the more Bregman divergence it has.

Let's do a very simple calculation.

In the simple case where phi of x

is just equal to one half times
the Euclidean distance.

So let's see what the Bregman
divergence is in this case.

Well, plugging in the definition,
I see that the Bregman divergence

between x and y is equal to
phi of x,

that's one half Euclidean norm
squared, of x,

Minus phi of y, that's one half
Euclidean norm squared of

y, Plus, gradient of phi of y.

Well, what's the gradient
of one half times the Euclidean norm?

It's just y itself.

Y transpose.

Times x minus y, and grouping
all these terms,

rewriting, I get one half, factor
that out, Euclidean norm of x

squared, plus...

minus twice y transpose x.

Then I've got minus y squared,

plus twice y squared.

That simplifies to just plus,
and you can see that this is

exactly the quadratic.

This is equal to one half x minus
y squared.

So, if we take phi to be the function
that's one half Euclidean norm squared,

then the Bregman divergence is

just going to be the difference in
Euclidean - it's the Euclidean norm of

the difference.

So we get something familiar.

But, we're going to see several examples
um, where we're going to take phi

to be something different and therefore we
get a very different Bregman divergence.

Okay, and we're going to use this directly
in our definition of mirror descent.

Mirror descent now becomes xt plus one,
is going to be equal to the argmin,

possibly in our set constraint,
eta gt transpose x,

plus, previously we had

one half times the Euclidean norm,
but now we have one half times the

Bregman divergence between x and xt.

So, if phi is equal to just one half
Euclidean norm squared, then

we recover our usual subgradient
method.

But, if we have something else,

if phi of x is equal to say,

one half times x transpose, times
a different matrix, times x,

where q is not equal to the identity,
then, we get a different algorithm.

And, this was exactly the idea that
started us off in mirror descent.

So this was the idea that we had
in lecture one on mirror descent.

So see the first lecture in the mirror
descent series.

But we're going to choose phi
to be even different than these.

So we'll see that we can take phi
to be quite different, and we would

therefore really change the
geometry of the space.

So, this is our first look
at mirror descent,

we're going to be trying to understand
its properties through examples,

and then also, in the following
lecture, actually deriving

rate of convergence and proof
for rate of convergence.

But in the meantime, let's go
back to Bregman divergence, and get

used to it a little bit, and see what
some of its properties are.

So, in part, I'm going to derive this
because we'll need it.

In part, just to get us used to thinking
about Bregman divergence.

It is a little bit familiar, because
it seems like -

because we saw that if we choose
phi to be half the Euclidean norm

squared, we get back something
very familiar, but if we plug in

other things, it will be a little bit
different.

So, just want to get used to
manipulating it, and seeing that

it's really not that difficult.

Um, okay, so let's, in part for exercise,
again, in part because we'll need it,

let's show that um, for any convex
function phi, we have this property

that the gradient of phi, evaluated
at x, minus the gradient of phi,

evaluated at y, transpose, times x minus
z, is in fact equal to the Bregman

divergence between x and y,
plus the Bregman divergence between

z and x, minus the Bregman
divergence between z and y.

And this is just a matter of
plugging in these definitions and

evaluating, so let's just do exactly
that.

So from the definition, the
right hand side is equal to the first

term, is equal to phi of x,
minus phi of y,

plus gradient phi of y,

times x minus y. The second term
is equal to phi of z, minus phi

of x, plus the gradient of phi
of x, times z minus x.

And then the third term, which
we subtract, is equal to phi of z,

plus, I'm distributing the
minus sign here,

So it's plus phi of y, plus the
gradient of phi of y, times

z minus y.

Okay, so what do we see?

Well, first of all, there's -

I see a positive phi of x
here, and a negative phi of x,

I see a positive phi of z
and a negative phi of z.

I see a negative phi of y
and another positive phi of y,

so all of these cancel,
and now I - oops.

And now I just have to collect
all of these terms here.

And this is just a matter of
a little bit of accounting.

So this is equal to

the gradient of phi of x
times x minus z

minus the gradient of phi of y
times x minus y

plus the gradient of phi of y
times z minus y,

and this is equal to the gradient
of phi of x times x minus z

minus the gradient of phi of y
times x minus z.

Now I can group these together
and I get exactly what I wanted.

This is the gradient of phi of x
minus the gradient of phi of y

times x minus z.

We're going to use this property,
but again, the point is for us

not to worry about just
plugging in the definitions.

These are relatively simple things.

We're going to need something else
in our development of mirror descent

and when we analyze it.

And this is the concept of a dual norm.

So where have we been
using dual norms

without even really knowing it?

We've been using dual norms because
everything we've done so far

with the exception of a few things
like prox, we used L1 norm, and so on,

we've been using the Euclidean norm.

So let's - let me give the definition
here of a dual norm.

So now I'm going to use this
double bar just as a generic norm.

So don't look at it and think
it's the two norm.

This is just some norm.

So for this indicating any norm,

its dual

is defined as follows.

I'm going to use this lower star notation.

So lower star is very frequently
used to denote the dual.

But in some other contexts
it has a specific definition.

So for example with matrices,
sometimes it denotes the trace norm

or the nuclear norm.

But in this case I'll try to be crystal
clear if we do need to talk about

another norm that's
often denoted like this.

For us, this star is always going to mean
the dual norm unless I specify otherwise.

So this is defined as the
maximum of u transpose v

subject to v less than one
where this is the original norm,

whatever that might have been.

Okay, so this is just the definition.

So let's do some examples.

So let's take - let's take this

equal to the Euclidean norm.

Might as well warm up with
something familiar.

So what is the dual
of the Euclidean norm,

u - I'll put a star, I'll write it
this way so we remember.

This is defined as the
max of u transpose v

subject to the Euclidean
norm of v is less than one.

We can just solve this geometrically.

It's saying your constrained
set is just a sphere.

So it's saying find the
point on the sphere

that has the largest inner product
with a particular vector.

What is that going to be?

Well, it's - you can see
from this picture.

You're not going to pick something
that is perpendicular, certainly.

If you picked something perpendicular,
you'd get zero in the max.

You're not going to pick something
in the opposite direction,

you'd get negative.

No, you're going to align exactly
with it and go out unit norm.

So in other words,
the optimal solution here

is the maximizer,

is just equal to u divided by its norm,

and the max value

is therefore going to be
u transpose times this v

times v star.

This is equal to just u transpose u
divided by the norm of u,

which is the norm of u.

In other words,
the two norm is self dual.

So the Euclidean norm - what we just
showed is is that the Euclidean norm

is its own dual.

It's called self dual.

So this is the way that we've been
actually using the dual norm

without even really knowing it,

because we've just been
working in the two norm.

So let's take another example.

So now let's take - that's example one.

Let's take norm equal to the one norm.

Okay, and let's see what its dual is.

So we've got, what is the dual norm
of u in the one norm?

This is again, just copying the definition,
the max of u transpose v...

u transpose v,

subject to v in the one norm
being less than one.

So let's think about what
this is going to give us.

So what does v - what does
this one norm tell us?

So this constraint is telling us that

we have to be inside this diamond,

or algebraically it's telling us that the
absolute values have to sum to one.

You can think about this as
a resource allocation problem.

You have to allocate your resources,
but you only have 100%

and you have to allocate the pieces
so that they add up to one.

Where are you going to put them?

You're going to put them
wherever the values are the biggest.

The slight difference to this
is that you can take values

that are positive and negative,
but then so can v.

So what you're going to do is
you're going to find the biggest

in absolute value element of u,

whether it's positive or negative,

and you're going to keep all of v,
all of your energy,

you're going to put onto that coordinate.

If the biggest element of u is negative,
you're also going to make v negative.

If the biggest element of u is positive,
you're also going to make v positive.

So in other words, v star in this case,
our optimizing v,

is going to be

is going to look like

the vector that's all zero except
with a single one.

And it's going to have a single one
in the ith position,

and its sign is going to be
the sign of ui.

And which i is it going to be?

It's going to be the i where the value
of the absolute value of ui is biggest.

So i is the argmax of the
absolute value of ui.

So in other words, what do we get?

The dual norm is the infinity norm.

So the dual norm of u is just
equal to the infinity norm.

And you can also see
that the infinity norm,

its dual is going to be
the one norm.

So there are many examples
like this that we can work out.

Let's do one more example.

So, so far

we've seen that the dual
of the Euclidean norm

is again the Euclidean norm.

The dual of the one norm
is the infinity norm.

I mentioned that the dual of
the infinity norm is the one norm.

So let's try that.

So the infinity norm,
let's look at the dual of that.

By definition this is
the max of u transpose v

subject to v in the infinity norm
being less than one.

So the infinity norm being less than one
means that every element of v

can be between minus one and one.

And there's no penalty.

In other words, if v1 is very big,
it doesn't mean that v2 has to be small.

So what would you do?

Again you can see this is quite simple.

You would look at ui and say ui,
is that positive or negative?

I'm going to let vi be the same
sign and be as big as I'm allowed,

which is in this case one.

So the optimizing v is just
going to be the sign of u,

element-wise.

In other words,

the ith element of v star is just
going to be the sign of ui.

And so then what is the sum of -

so u transpose v is equal
to the sum of ui vi.

And plugging in this v, this is
the same as the sum of ui

times the sign of ui,

which is exactly equal to the sum
of the absolute value of ui,

which is in fact the L1 norm.

So now we've seen
all three of these examples.

And we're going to use a very
important property of dual norms,

which I'm going to write down now,

and we're going to see it again
in the next lecture.

So an important inequality

says the following.

Remember that we've needed to bound,
several times, the dot product

between two vectors u and v.

And we've done this in several ways.

So we can bound this
in terms of the two norm.

So this is upper bounded by the two
norm of u times the two norm of v.

In fact we know that these are equal
only when u and v are parallel

and pointing in the same direction.

So this is the Cauchy-Schwarz -
famous Cauchy-Schwarz inequality.

In fact, it's also true that u transpose v

is less than or equal to u times v star,

where u and v are any norm and its dual.

And this is sometimes called
Hölder's inequality.

And so far we've used - if you go
back to the proofs of gradient descent,

subgradient descent, and so on,
you'll see this kind of inequality,

the first one, in many places.

So one of the properties that we've
used, another way to bound uv

is as follows.

Also, u transpose v
is less than or equal to

One half times u squared - this is
the Euclidean norm squared -

plus one half v squared.

This just comes from
completing the square.

Again, we've used this
over and over again.

But using the dual norm,

we can refine this in a particular way.

So we will use the following upper bound:

u transpose v is less than or equal to
one over two alpha

times the norm of u squared -

note there's no two subscript,
this is not the Euclidean norm -

plus alpha over two,
times the dual norm of v, squared.

And this is very similar.

If we take alpha equals to one,

we recover what we get
from completing the square.

The reason that this
is so important for us

is that these dot products
are foundational for us.

This is the definition of convexity.

We use these to make our
linear approximations.

This is how we define convex functions,

this is how we define
our linear approximations,

and this is how we define
all our algorithms.

So we're going to see next time
how we use this inequality,

how we use Bregman divergence,

and how we use the definition of
the Bregman divergence

as a proximal term

in order to show better
convergence rates for mirror prox

in certain settings where -
I'm sorry, for mirror descent

in certain settings where we don't
want to use Euclidean geometry.

We'll pick this up next time.