so I've got a I'm going to skip a lot of
these slides in this second deck so I'm
just going to do the interesting parts
from remaining in this part and then
I'll switch to the third deck which is
about augmented lagrangian an 80mm to
class of methods that's been very
popular in signal processing
applications so I'll do about half of
that deck just with a kind of key ideas
okay alright so this is where we left
off we talked about a bunch of methods
for first order methods for minimizing a
smooth f and now i want to extend them
to the case where we're adding on a
regularizer here where this regularizer
is usually convex but not smooth and so
how do we extend these methods that we
figured out to deal with that so usually
what we do is basically take a
first-order step in F and then we
incorporate the regularization term
explicitly okay so you can think of this
is the basic step that from from xk the
current iterate you do something just
with F so this operator here is
something based on X K and grad F of XK
usually and maybe it also has some of
those acceleration techniques that we
talked about and then you plug it into
this formula and bring in this
regularizer which so far you've left out
this lambda should be equal to tau here
and what you get out of that is a new
editor at XK plus 1 i'm sorry this
should be a k plus 1 over here okay so
this is how you get with a regulars
formulation this is how you get from one
is it to the next so there's a whole
bunch of slides here where we talk about
the details of doing that about sub
gradients which I think you probably
know about from France theses talk
yesterday so I'm doing a lot of skipping
here a bit about prox regulator you know
we talked about some of this I'm sure
you're taking this all in okay so here
we are this is where I left off a moment
ago and this is the special case where
we're taking a steepest descent step and
so I've got this notation here prox and
let me explain what that means it just
basically means a solution of that sub
problem that I through
earlier ok so i define prox with respect
to some function h of some function y is
just the minimum of one half over x of
one half x minus y 2 norm squared plus h
of x ok so it basically accepts as its
argument some something Y which in our
case is a steepest descent step from the
current XK and then it brings in the H
explicitly ok so if H is not there if h
is the null function the minimizer this
is just x equals y so if there's no
regularizer we just get the steepest
descent step but if there is a
regularizer it solves this little
subproblem to get the to get the steve
is this internet all right so that's
what's going on here and usually this is
easy to solve in the case where H is a 1
norm for example this breaks down and
this decomposes into single components
of the vectors x and y and you just get
n scale of problems that you can just
solve in closed form using that soft
thresholding operation we talked about
earlier so usually solving the sub
problem for a lot of practical
regularization functions is very easy ok
so this is the basic extension of
steepest ascent to the case where we've
got a regularizer and you can change a
little bit you can make some various
enhancements you can bring in this
lambda to make it if Flame is equal to 1
it's the basic steepest descent step if
not it's some sort of relaxation where
you might overshoot or undershoot and
then you might make some errors here in
the calculations BK and AK so this is
kind of a generalized form of steepest
descent extended to their regular eyes
case and there's a paper of now 10 years
older to combat some while from Paris II
so I guess they are and it shows that if
you choose the alpha K the step length
parameter to be between 0 and 2 / l now
this is pretty much the range that we
can prove things
about for just the smooth case remember
the smooth case i took alpha to be 1
over l which is what right in the middle
of this range you don't actually need to
fix it at 1 overall just as long as it's
you know somewhere near that if you
choose the relaxation parameters to just
all be in this range what we usually do
is just choose them all to be one but
this kind of generalizes out a little
bit and if the error is some to less
than infinity that all of this is
guaranteed to converge so it converges
under pretty general conditions okay so
very often in many of the cases that we
have like we had in compressed sensing
that function f is actually a
least-squares type function so in the
first talk i gave this morning where I
dealt with the compressed sensing case
and proved exactness and all that this
is the kind of case we had for rash so
let's see what happens in that case
let's see how this algorithm specializes
for that case well this is the basic
step so this year should be an XK so
from xk we calculate V xk minus B so
that involves mostly a matrix
multiplication involving be we take that
vector and multiply with B transpose
okay then we do the subtraction and then
we do the prox operator so you are
usually the expensive part of this step
how the multiplication by be here matrix
vector multiplication with B and then we
do a matrix vector multiplication with B
transpose okay these other operations
are just relatively small order n order
M operations including the prox
operation let's order hand ok so the
thing about this is that in many
applications like in compressed sensing
applications it's possible to do these
multiplications relatively efficiently
ok so in compressed sensing we use the
notation a for this matrix this morning
one popular compressed sensing matrix is
as a row sub matrix of the FFT okay
that's a quite an effective sensing
matrix it tends to have those those nice
properties like rip type properties that
I talk
about this morning so if this is a sub
matrix of an FFT you know that you can
calculate the FFT and order n log n
complexity and then you just have to sub
sample down from that so basically the
cost of each step is order n log n
wavelet transformations are if B has
some sort of sub matrix of a wavelet
matrix again you can do that you know
more efficiently than just the
dimensions would suggest ok there are
efficient ways of operating with wavelet
type matrices and so for those kinds of
applications this is a very elementary
algorithm that you can apply quite
efficiently now for some in this case
you can prove some more refined things
about conversions which I'll mention and
if the regularizer in fact is a 1 norm
we can say even more about how the
convergence of this approach works ok so
this basic approach is known as IST
iterated shrinking and thrush holding
and the distinctive features of this
approach or that the alpha the step
alpha is the same kind of short step
that I talked about earlier it's like a
1 over L step where at least it's no
bigger than 2 / l where l is the maximum
eigen value of the Hessian the hash in
this case is just be transposed be ok
it's just a constant matrix and L would
be the maximum eigen value of that so
provided alpha is like that we can prove
that this whole approach I'm converges
now in the case that is this is the one
on the regularizer is the one norm we
can even say more about this approach we
can say that it identifies the correct
set of zeros in a finite number of
iterations ok so the after you've taken
finitely many steps the elements of X
that are 0 at the solution of the
problem actually are 0 at all of the
iterates past a certain stage and after
that the problem just collapses to
minimizing you know figuring out what
the true value of x is on the non zero
set ok so at least you get 20 is right
after a finite number of steps and after
that you just have to iterate some more
to get convergence on the non zero
so that's quite a strong result already
right there and in fact the convergence
behavior from then on it doesn't depend
on the conditioning of the Hessian it
just depends on the conditioning of the
reduced ashen that is the Hessian just
on the non-zeros so I only need to look
at the columns of B the correspond to
perversely I've called Z of uz here for
the set of oh god no I've messed up the
notation here this should be an this
should be the set of non zeros okay so
we only need to look at the Hessian
caught the reduced session corresponding
to the nonzero components of X and the
condition of that is going to tell us
how fast this method method converges in
the asymptotic stages after the zeros
have been identified okay alright so
that was for the basic steepest descent
algorithm extended to the regularized
case now you can also extend that Fister
approach that I talked about earlier
this is the accelerated nesterov type
approach in fact the fist of paper did
already include the extension to the
regular ace case so it's all the same as
basically very similar to nesterov
except in this first step here you are
applying the prox operator these other
steps are just the same and again you
need to restrict the alpha to be less
than 1 / hell in this case and you get
some benefit from that you get instead
of the one over K rate that is all you
can prove for the unexcelled added first
order method you can get a 1 over K
squared rate which is typical of
nesterov okay and this is kind of still
a pessimistic great and it only it's not
taking account of the fact that
eventually you find the right manifold
when you've got the right manifold
you're essentially doing with a strongly
convex problem and after that the
converges is linear so although this is
faster than what you get for the
classical weakly convex algorithm it
still doesn't really capture the true
behavior of the method which is
eventually that it becomes linear rather
than sublinear okay this one I think
I'll kind of skip
what okay okay I want to talk about this
possum method this is the one that we
worked on in 2008-2009 and basically
it's just the Iast method except that
we're more aggressive about choosing
step lengths because this idea of short
step lengths in practice is not very
fast and you can often be a little bit
more adventurous in fact what we did was
to use barzilai born type steps and I
pointed out earlier that this is a non
monotone method that sometimes takes
long steps that sometimes causes the
function to really blow up but in the
long run it's often better okay okay so
we we do actually safeguard the buzz
libor we sort of apply some restrictions
to it so that occasionally you know over
a span and say 10 iterations we at least
want to get a reduction are we at least
want to be better now than we were 10
iterations ago so occasionally will do
backtracking to force us to to in the
long run get better so we don't just go
all out Basel a ball and there's a
little bit of safeguarding going on but
essentially the ideas are from Basel a
ball one okay and for that case we can
prove convergence to two critical points
and we get significantly better a
practical performance often better than
than Fister even okay this will skip
over this was actually a first idea
maybe i'll mention it our first idea
when we looked at this problem which is
the one that shows up in compressed
sensing is to actually split the
variable X into positive and negative
part so we just express X as u minus V
where u and v are both positive and if
you do that splitting you can write the
1 norm of X just as the sum of the
elements of U and V man there are typos
all over the place here that should be a
V okay so this is this is just the sum
of the elements of you that's the sum of
the elements of V okay so that captures
the one norm and this of course is the
first time and so and so this is just
now a quadratic program with down
constraints and there are nice efficient
solvers available for that projected
gradient types always work on that
so that was our first approach until we
figured out that you really didn't need
to do the splitting you can just treat
it directly using this shrinking type
this prox operator okay but then we got
two papers out of it instead of one so
if she can't argue with that okay so
here are some colleague Dirk Lorenz
wrote this paper where he developed I
think a reasonable way of generating
test problems for these cases that have
something to do with compressed sensing
so you know they involve the sorts of
matrices that show up in and observation
matrices and he ran tests between a
bunch of different algorithms and I've
mentioned is tgps are sparser and Fister
I've actually covered a bunch of these
these are sort of alternative
acceleration this is a different kind of
acceleration due to Canada's and and
some of his collaborators this is
actually as an amended Lagrangian
approach which I'll talk about presently
and this was an earlier approach which I
won't mention but he sort of generated
results and they color-coded I'm not
sure as you can see the colors too well
but in this one sparser actually did
quite well that Nesta which is an
accelerated nesterov acceleration type
one sort of did quite similarly to
spacer on that example they did better
than Fister even though Fister has
acceleration but here's an example where
well here's another example is parted as
well okay I guess Mario picked the ones
where we do we do well here but here's
an example where sparsa really exhibits
that non monotonicity ok this was one
where all the solvers kind of struggle
the a here is coherent in other words it
doesn't satisfy that those rip
properties that the classical
compressive compressed sensing analysis
depends on and so when when their
property is not satisfied these solvers
can be very slow and they're all quite
slow here and you'll see that mr.
although you know at its best is not too
bad oh sorry this is sparta you really
see the ball the basel a boy
behavior where in between it spikes and
goes crazy these other methods are much
more kind of monitor monotonic and
Fister here does generally better than
the others okay yes yes you can always
evaluate functions in you can always
evaluate the function so you can always
tell when this is happening but you kind
of you ignore it for a while it's only
if it sort of consistently stays high
that you start backtracking to make sure
you get back to the baseline here
because in general if you don't allow it
to do this you get kind of a slower over
all right so even though this looks bad
it's kind of setting you up to make
better advances down the road so I think
here is T i'm not sure i think is t is
this one so i AST is really sparsely
with the less aggressive step length so
you can see that overall its behavior is
worse right so by bouncing around you do
do a little bit better not terribly
intuitive than anyway okay so this is
another trick that's very important in
these methods and that's the idea of
continuation so this regularization
parameter tau turns out to really affect
the performance so remember tower is the
coefficient that goes with the with the
x1 term okay so let's see so wen Tao is
small these things can be pretty slow
okay a lot slower towers bigger means
that really is penalizing the nonzero
X's more viciously and that tends to
drive a lot of the excess 20 more
quickly and those problems seem tend to
be easier to solve and so you can design
a very simple strategy where you know
you know the value of tau that you want
to apply but you start it with some
value that's much bigger than that and
you solve the problem for that big value
of tau you run these algorithms for a
while you stop when they find an
approximate solution for that value of
tau then you decreased our by a bit and
repeat the process starting from the
solution that you found here so sort of
an obvious idea continuation idea where
you gradually work from an easy problem
to the hard problem
and little baby steps okay sort of
starting from the warm starting each
time from the solution of the previous
step so the parameter here to chooses
how much you decreased our boy you can
be adaptive about that you can you know
start off decreasing how aggressively if
you find out you're taking too many
iterations to solve this problem he can
back off and decrease it kind of less
aggressively so you know there are
pretty pretty good ways of figuring out
how to do this and there's some analysis
of this in this paper by Zhao and Jang
they sort of show the overall complexity
of this approach okay so when you do
continuation with these methods you tend
to party I have to remember what this
thing is showing you tend to get sort of
more gentle increases so as we move out
along here towers getting smaller so the
ratio of the maximum value of tau to the
value that we actually try is getting
bigger okay and this is how the CPU time
goes up so this is if you don't use
continuation the CPU time increases
sharply as tower decreases but if you
use this continuation idea and sort of
gradually ramp up to the ramp down to
the value of tau that you're looking for
you get much gentler behavior okay so
all right D biasing I don't the advising
is kind of the obvious idea that when
you think you've identified the support
of X when you think you've figured out
which components of X want to be nonzero
you just toss out the zero components
and solve the reduced problem and drop
the l1 term okay so you just you just
use the regularizer to pick the support
and once you find the support you just
saw the least squares problem just over
the thing the support that you've
identified and we usually do that as a
kind of a post processing step in sparsa
because if you leave the regularizer in
there it tends to suppress the values of
x the real values of x it tends to push
them down a little bit so this is a bit
out Hawk you know there are other
regular eise's that statisticians our
interests
in that that that don't introduce this
bias into the solution the so-called
scared and mcp regular eise's where when
I keep losing the chalk yeah where you
know the l1 regularizer basically does
this okay penalize is like that but the
statisticians are interested in these
other regular izes where as you move
away from the origin it flattens out and
so when you're out in this region it
doesn't penalize you too much for being
non zero whereas here the penalty keeps
going up the further bigger you get and
they can show that regular roses like
this give unbiased solutions so you
wouldn't have to do these you wouldn't
have to do these post processing steps
but what's the disadvantage of this
what's the disadvantage of using this as
opposed to this any ideas yep it's not
convex yeah that's kind of the killer
about this so you have a non convex
problem to solve it's you know convict
algorithms like the ones we've talked
about still work pretty well on these
problems but you lose a lot of the
convergence guarantees okay because
you've got a non convex problem so I've
often had this discussion with
statisticians of why don't you why don't
you do it this way why don't you use L
once of a convex problem find the
support and then d bias as opposed to
just doing it one step like this and
their argument is that this is actually
better at finding the support if you do
this upfront and you are able to solve
it which is a big caveat that it
actually does a better job in finding
the right support then the old one does
okay and I have to trust them on that
right because they're the experts on
this kind of thing alright so this is
just to illustrate the effect of
devising here's a problem where we've
got N equals 4096 here's the true
solution notice all of the spikes have
norm of size 1 plus or minus 1 if you do
sparser on this and solve it you get a
solution that's obviously biased a lot
of the magnitudes of the spikes have
been
rest but then if you take the support
the non-zeros here and solve that d bias
problem throughout the l1 regularizer
you recover the you basically recover
most of the unit magnitudes okay the
reason they're not exactly the same is
that some of the the supports not
exactly right okay if the support was
exactly right I'm not sure if we have
noise in this problem yeah I think we do
have a little bit of noise the noise
would be another reason way why it
wouldn't be exact okay I think I'll skip
the rest of this yeah well skip the rest
of this deck so let me go under the
pigmented Lagrangian one okay which is
this one okay so this whole 80mm is
spawned a whole cottage industry in the
optimization community mostly because
it's turned out to be quite useful and a
lot of these image reconstruction signal
reconstruction applications so the
second half of this deck actually has a
lot of stuff about the work of Mario and
his collaborators on on those kinds of
applications and I probably won't get
that far so let's see I've got to finish
it 10 to six and if I go off to go over
time people will kill me because I'm
getting into dinner time and I've got to
remember to have a break right at
quarter past about 10 minutes okay all
right so i'll probably get through about
half of this deck maybe a little bit
more all right so i just want to give
you the basic idea of augmented
lagrangian and and its extension to a
dmm all right so i'll start by
considering this linearly constrained
problem where I've got a smooth function
f and a bunch of linear constraints so
first of all how do we recognize that an
x star is a solution of this problem
well we can write down these magical
things call karu kuhn tucker conditions
that guarantee that you or at least if X
star really is a solution these KKT
conditions have to hold in other words
they're necessary conditions
for a solution and they say the
following that if if there exists a
lambda star so that you can express the
gradient of F at X star as a linear
combination of the rows of a where the
coefficients of that combination of the
elements of lambda star and of course
you also need X star to be feasible it
has to satisfy the constraints so if
those conditions are true then that's
kind of an indication that you're you're
out of solution if F is convex these are
also sufficient conditions ok so if F is
convex this is what you're looking for
you're looking for an X star and a land
of style that satisfy these conditions
ok all right so a neat way to write
those conditions is to write down this
so-called Lagrangian function and it's a
way of combining the objective and the
constraints so you're right down f of X
and then you add on this term lambda
transpose the constraints hey X minus P
and ax minus P has to be 0 at the
solution of course ok and so those KKT
conditions you can write them down by
first of all taking the partial
derivative of this expression with
respect to X and then you just get grad
F plus a transpose lambda ok and that
has to be equal to 0 so that gives me
exactly what I had here all right so
that's the first KKT condition and the
second KKT condition is when I
differentiate with respect to lambda I
just get ax minus B equals 0 and that's
the second condition here ok so this is
a neat way of writing the KKT conditions
just that we're at a stationary point of
this function a stationary point is one
way the gradient is 0 ok so if F is
convex but non-smooth all of these ideas
are the same we can just replace the
gradient with a generalized with a sub
gradient and then grad F just becomes
sub gradient of F sub differential ok
and I skipped over all the stuff about
sub differentials but but it's a you
know it's a the obvious extension of the
derivative to the case where F
convex okay but I won't say too much
more about this all right so what is an
augmented lagrangian method so the idea
is you write down the Lagrangian
function and you add on this extra term
it's kind of a penalty tone for the
constraints and it's just some multiple
times the 2 norm of ax minus B squared
now obviously at the solution this is
going to be 0 so this is penalizing you
it's sort of forcing you to be feasible
ok so you define that function it's just
an extension of Lagrangian and then this
is the basic iteration truck-mounted
Lagrangian first of all you fix the
lambda at its value from the previous
hitter at lambda k minus 1 and you
minimize with respect to X ok so you
just get a sub problem if you look at it
look at what it's doing just with
respect to X it's the original f plus a
linear time in X is the lambdas fixed so
it's just going to be X transpose a
transpose lambda so it's a linear term
and then there's going to be a quadratic
term coming in here so you know it might
be a little bit harder it might be a lot
harder than the original problem
depending on how hard it is to solve to
minimize F could be easier could be the
same it's usually not easier but it
could be the same or a bit harder ok and
then and then you update lambda
according to this formula alright so
this seems a little bit magic but I'm
going to show you a simple derivation
that sort of makes this all make sense
ok so you change land or according to
this simple formula this is usually easy
to do and then you solve these
minimization so the idea is you're
replacing the solution of a constrained
problem with a solution of a sequence of
unconstrained problems alternating with
some updates which are usually cheap
okay all right all right so here's a
derivation it's kind of a favorite of
mine and it's kind of rigorous I think
you can you can show that all the steps
i'm going to describe here actually can
be rigorously justified in the case
where f
x okay so first of all I'm going to take
the original problem but I'm going to
write it in a really bizarre form i'm
going to say instead of minimizing f of
X subject to ax equals B I'm going to
say that I want to minimize this
function here this function that is
defined as being the maximum over lambda
of f of X plus lambda transpose ax minus
B now that's a really bizarre function
and kind of an ugly function but you can
see that if a X is not equal to be some
elements of this vector are going to be
non zero and then when I maximize
Overlander I'm going to be able to drive
this term to infinity okay if any of
these are either positive or negative I
can pick the corresponding and component
of lambda to go to infinity in one
direction or another and drive this
whole term and drive this whole term to
infinity okay and so you can see that
this function here it's going to be
infinite if I X is not equal to B if ax
is equal to B this whole function just
going to be equal to f of X so this is
totally equivalent to this original
problem okay but of course it's not
useful from an optimization viewpoint
because this function in here is a
horrible function it's discontinuous
sometimes it's finite sometimes it's
equal to F but then if you move off this
manifold that suddenly jumps to infinity
so it's not something we can apply any
kind of reasonable algorithm to but we
can sort of stabilize it okay so what we
can do is to add on or subtract a
quadratic term from this so here's the
original maximization but i'm just going
to subtract this quadratic term so i'm
going to pick some sort of anchor point
lambda bar and i'm going to penalize any
move away from lambda bar and I'll
parameterize it with some positive
quantity here okay so what's happened
now is that this function that I'm
maximizing land rover is now a concave
quadratic it's got this shape upside
down convex strictly concave quadratic
and so for any X feasible or infeasible
I can actually write down and close
form what the maximizing Lander of this
thing is okay in fact it's a very simple
quadratic because the Hessian is just
the identity or multiple of the identity
so i can write down a closed form
solution of this guy here it is here ok
it's just lambda bar plus rho times ax
minus B okay so actually calculating in
closed form what this whole maximization
thing is doing is now has now become
easy so now what I can do is to plug
this optimized lambda back into this
function and then I've evaluated the
thing in the curly brackets here okay
I've actually got a value of that and
this is what it is this is all it
becomes when I plug that in I just get
that okay and that's exactly the
augmented lagrangian function where the
anchor point is just the lambda from the
previous iteration okay so basically
what I've got is I go from the exact
formulation exact butt-ugly formulation
of the original problem I stabilize it
by introducing this proc stone
explicitly maximized and I get back
exactly the function that we minimize in
the augmented lagrangian step so now you
can see that you can view the whole
augmented lagrangian process as plugging
in lambda k minus 1 here minimizing this
guy to get the new X then shifting
lambda bar to be the updated point in
other words you do this maximization to
get your next iterate your next estimate
of lambda so your update land according
to that formula and that's exactly the
formula that I had here okay so I update
lambda I use that as the new anchor
point for the next iteration and then
just repeat the whole process okay so
you can think of a med and Lagrangian as
a stabilized version of a sort of dual
ascent a doula sent kind of approach
okay you can do other things you can
mess around with the lambda here with a
row which is a penalty time most of
mental Lagrangian methods have
heuristics for deciding when they need
to increase the row if the if
these constraints are not becoming
feasible fast enough they decide to sort
of increase the road to make the penalty
more acute and they might have a
different row for each each constraint
things like that the lots of heuristics
there but you don't particularly need to
do very much with the row another way to
motivate augmented lagrangian by the way
is as an extension of the old-fashioned
quadratic penalty function then this was
invented by Courant in the 1940s the
quadratic penalty function is just the
same as this way there's no lambda tone
we just take the original objective and
add on a quadratic penalty for the
constraints the problem with quadratic
penalty is that you have to make the row
go to infinity to get convergence to a
feasible point you have to drive that to
infinity the advantage of augmented
lagrangian is you don't have to do that
you can actually get convergence to the
exact solution even for finite values of
Rho which is a pretty big advantage ok
all right right I say so how do we
extend this this is a very special case
equality constraints ok we can extend it
to inequality constraints using exactly
the same rationale so i can write it
down as a min max function but when I'm
dealing with inequality constraints now
I have to maximize over lambda greater
than or equal to 0 ok because if I need
to only pay attention to the cases where
these constraints are violated that's
where the ax is less than B one of the
rows of a X is less than the
corresponding element of B and then I
can drive this function to infinity ok
if this constraint is not satisfied I
can drive this to infinity so again this
is not practical because it's equal to F
when this thing is um feasible that
infinity otherwise I can stabilize it in
the same way add on that prox term do an
explicit minimization with respect to
Phi now this is the explicit minimum i
can plug that back in and i get an
inequality constraint form of the
omentum
June and it all goes through the formula
by the way for inequality constraints
looks very very non-intuitive but that's
all it is it can be motivated in exactly
the same way here's another extension
sometimes you've got constraints that
are this cut this happens a lot actually
you've got some constraints that are
easy to deal with explicitly and others
that you need to kind of penalize in the
Lagrangian approach and so you can deal
with those just by putting these into
the augmented lagrangian and dealing
with these explicitly in the
minimization step so these might be for
example bound you might have excavated
or equal to 0 here well it might be
boxed constraints where X has to be in a
range between lower and upper bound and
sometimes it's easy to deal with them
here and everything else about this is
the same you just need to minimize over
the the constraints at Omega everything
else works and in fact you can use that
observation that you can deal with some
of the constraints explicitly by it'll
give you another way to deal with cases
where you've got inequalities because
you can just replace inequalities by
slacks okay when you've got a constraint
C of X greater than or equal to 0 where
C is some vector function you can
replace that with C of X equal to s then
s is greater than or equal to 0 so now
you've got an optimization problem
involving x and s I need to have a comma
s here because I'm minimizing over x and
s and you can deal with this exactly
using this methodology where I put this
constraint into the Lagrangian and I
deal with this one explicitly that gives
you an alternative way of applying
augmented lagrangian two functions with
inequality constraints the only thing
here is when you're solving the
sub-problem you have to remember that
you need to keep the s is greater than
equal to 0 so the codes that there is a
general code that came out over 20 years
ago now 25 years ago lancelot where they
essentially used this way of solving
general nonlinear programs with with
inequality constraints okay
alright so a bit of history of augmented
lagrangian it's at a very rocky history
I would say it was first invented
simultaneously and independently by
these two researchers in 1969's Tunisian
Powell Powell died recently we had a
meeting celebrate him last week in
Mexico actually but this is one of a
number of things that he was famous for
then these are very famous figures
Rockefeller and Boots akos worked on it
in the 1970s and more in the early 1980s
and extended it to non linear
constraints to inequalities and all this
kind of thing and developed generalized
to operators rather than a minute rather
than just optimization did a lot of work
on it and then it sort of fell out of
favor for quite a while maybe ten years
or so and then these guys con gold and
white started working in the late 80s
trying to started really trying to get
it to work then as a culmination of
about four or five years of work they
came up with his coat Lancelot that won
prizes and seemed to be quite
competitive and then something
revolutionary happened in the years you
know probably mid to late 90s
particularly in the late 90s in
nonlinear programming algorithms does
anyone know what that was so the new
technology came along they kind of blew
these out of the water to some extent
interior point methods yeah so interior
point methods were developed for linear
programming and computationally they
matured in the early 90s and then in the
late 90s they became one of the dominant
technologies in nonlinear programming as
well and it turned out that they beat
Lancelot and sqp sequential quadratic
programming on a lot of problems not
uniformly but but they seem too unkind
of the general test sets that nonlinear
programming people use interior points
started to dominate yeah
no they're actually easier to code in
many ways basic versions of them are
quite easy to code because the core
operations are just solving linear
systems you know that's pretty
straightforward even for linear program
either extraordinary because you can
write you know I've got a matlab code
that's a page and a half long that's
actually quite competitive and so for
linear programming as a general purpose
solver interior point solver whereas
simplex codes are incredibly
sophisticated simplex codes for linear
programming run to you know hundreds of
thousands of lines to get all the
factorizations efficient and everything
so interplan codes are remarkably easy
to code how these these are sqp codes
are demanding because you have to solve
a quadratic program at every iteration
and to do that properly as is hard and
Lancelot is pretty complicated because
you have to solve there's nonlinear
bound constraint problem and they do
that using a variety of quasi Newton
type methods so anyway this kind of fell
out of favor and the whole the whole
augmented lagrangian ideas sort of
dropped dropped out of favor until you
know until order of five to five or six
years ago okay yep yeah well right now
I've been asking that it's smooth and
you know convex if you want strong
convergence results but it actually does
work for non-smooth apps as well yeah if
you yeah then the theory probably gets a
bit more shaky but you can still try
there's no harm in trying yeah yeah but
I'm not going to say much about that
Oh break sorry yeah oh god I always go
over time okay so after the break I've
got about twenty twenty something
minutes left okay sorry about that about
20 minutes to finish up yeah ok so I
just wanted to make this comment that
the these methods they fell out of favor
for a long time but but now in the last
five to seven or so years they've been
revived in the context of sparse
optimization regularize type
optimization as well see ok in
conjunction with splitting so splitting
has turned out to be an important way of
making these work for those applications
so let me describe what this this whole
splitting idea is about and I'll define
it first in these very basic terms where
we just split the variables into two
blocks so let's suppose that I've got
that linearly constrained problem that I
talked about earlier but let's suppose
that I can break the variables into two
vectors X and Z and each of them has a
separate objective ok so this is a
slightly more specialized form than I
had originally ok so i can write down
the augmented lagrangian for this
problem in exactly the same way I've got
the objective here I've got lambda times
our constraint here I've got row over
two times the norm of the constraint
here ok so I could just apply augmented
lagrangian to this and a ground
Lagrangian would have two steps the
first step you fix lambda and minimize
jointly over X and Z ok and the second
step you update later that's all it is
so that's what you would do in standard
augmented lagrangian the separable ax t
is lost you can see when you jointly
minimize over X and Z in this to in
these terms the x and z are decoupled
you can solve them independently in this
time they decoupled again there's no
cross term involving both x and z but
here they're coupled
okay if you multiply out this term here
it's got a term and say it says X
transpose a transpose B times Z so the
coupling between the x's and disease so
when you minimize with respect to x and
z jointly you have to take care of that
coupling and so you don't get any
advantage of the fact that you know
they're almost separate here so in a DMM
or alternating Direction method of
multipliers what you do is just minimize
with respect to x and z separately so
instead of a joint minimization over x
and z first you fix z as well as lambda
okay and just minimize with respect to x
and then you do the opposite then you
leave the lambda fixed and you fix X at
its latest value that you just
calculated and then you minimize with
respect to Z okay so these two steps
replace the joint minimization and then
you update the lambda so you can see
this is kind of an approximate way of
doing the joint minimization okay it's
kind of an approximate way where you
just take a step in the X direction and
in the Z direction so you're alternating
between between X and Z stats
essentially so you're also updating the
lambda in between okay so you can think
of it and there's some controversy about
how you should think about what's going
on here one way to think about is this
is like coordinate descent block
coordinate descent coordinate descent is
a classic algorithm where you break the
components of X into blocks and and the
deej iteration you pick one block and
you just minimize over that block of
components leave all the others fixed so
you can think of this as one step of
coordinate descent over the for the
minimization over x and z jointly fixing
x the fixings e minimizing over x fixing
x minimizing over z you could keep
cycling around here you could keep the
lambda fixed at this value and you could
keep updating x and z but it turns out
not to be very very beneficial as a
paper by eckstein from a few years ago
maybe two or three years ago where he
shows
if you actually make a serious attempt
to minimize over X and Z jointly you
don't do much better than if you do this
approach of doing this very approximate
minimization that's one way to think
about it what about the cost of these
things well basically when you do these
these minimization steps when you
minimize over the X the Z is fixed and
so the HM is not going to come into it
okay that's just a constant as far as
this guy is concerned this is a constant
this is a constant so what you've got is
a minimization over F plus a linear term
plus a quadratic term in X and this
quadratic term is going to have a
hessian a transpose a okay now again
that might be same difficulty as the
original minimization over F or it might
be harder okay depends on the context
same thing here from the minimization
over Z then the X term is basically
constant because you're fixing it you
just got the original h plus a linear
term involving Z plus a quadratic term
with B transpose B in it okay so that's
the cost it's like a sequence of
minimization is over F&H with this
quadratic term added on you can also
deal with the case where you've got some
explicit separated constraint so if
you've got some additional constraints
on X and Z that are separated if you
want X to belong to some set Omega X and
0 going to some set Omega Z you can go
here and just apply those constraints
explicitly in these minimization 'he's
so that generalizes the class of
problems that you can deal with and as
we'll see because we have a little bit
of extra time there are many
applications of this to compressed
sensing image processing matrix
completion sparse pca and so on okay so
this idea of a dmm the way that it's
written here it's the right from what
many Lagrangian but its history actually
goes back further you can you can treat
it as an operator splitting type method
and the antecedents for that go back to
the 1950s and so there are papers and
the operator splitting literature going
way back that basically
the same sort of idea of breaking
operators into two pieces and there's
this recent paper by boyd he really
caught the wave here Boyden Eckstein and
two other people wrote this survey paper
in 2011 and I checked the citation count
on that last week it's already 2,800
citations so it turned out to be a great
idea to write a survey paper right when
they did okay now I'll give you some
applications of this idea just to show
how it is very useful in this the
splitting a dmm idea is very useful for
a lot of kind of interesting familiar
problems so suppose here you have a
problem well like again in machine
learning and many other applications
where the objective function is a but
it's a sum of a bunch of objective
functions but they all depend on the
same variable X ok now this does not
look like the sort of problem that I've
been writing down in the previous slides
it's an unconstrained problem so what's
how do I apply or medula grunge in or a
DMM to this well I can reformulate it
like this instead I can say let me let
me introduce a copy of this variable X
that's different for every objective
every objective in the sum so I'll bring
in a separate variable X I such that F Y
is just a function of X I and then I'll
have this constraint that all of the
excise have to be equal to X ok so you
can think of X as being kind of the
master variable and you want all of
these sort of copies to be equal to X
ultimately all right so it's obvious i'm
sure it's obvious to everyone that if I
that this formulation and this are going
to have basically the same problem they
can have the same answer ok but this
problem is in a form that i can apply a
dmm and what i'll do is apply a dmm
where where I had X in the ad mm
expression and the last few slides I'll
replace that with X and where I had Z in
the last few slides I'll replace that
with all the copies x1 through XM so
this is going to be the Z block ok so i
can write down what does the augmented
lagrangian look like well
just the original objective here it is
here plus lambda transpose the
constraints well now there's a whole
bunch of constraints so I've got a lamb
too high for each of these individual
constraints so that's the lambda
transpose constraint tone and then I've
got this penalty tone for each of these
constraints as well XA minus X 2 norm
squared okay so this is my augmented
lagrangian term to stochastic
optimization this is not okay it looks
similar because the objective is exactly
the form that stochastic optimization
uses but what I'm describing here is not
going to be a stochastic optimization
method okay then you have to do yeah
it's a different is a different
algorithm because it's actually treating
f it's dealing with the whole f at every
iteration whereas the casting
optimization doesn't do that let's take
us through optimization you typically
pick one of these f is and you do
something based on that I have a whole
other slide deck for that but since
Francis is going to talk more about that
tomorrow I'm going to leave it up to him
okay besides which are going to go 10
minutes so all right so that's a topic
for another day ok but certainly this is
the kind of thing that you also be
interested in using stochastic
optimization for ok so what are the
steps to implement a dmm on this what
are the two things you have to do well
the first thing is you have to minimize
this over X the master variable X that's
one step and if you look at this
function as a function of X it's
actually very simple function because
there's no X anywhere in here ok this
funk this function here only has the
copies it only has the Z in it in fact
all we've got going on in X is this
quadratic and we can explicitly minimize
this code with respect to X and here it
is here's the solution this is what i
get when i when i minimize the augmented
lagrangian with respect to X i can write
down explicitly what the answer is so
that part is really easy ok
now what's the other step in canadia mmm
it's minimizing with respect to Z to
minimize with respect to Z you I have to
minimize this over all of the x i's now
if you look at that it's got a special
property with respect to the excise can
can you tell me what it is well I've
written it down here given you the
answer it's separable okay I should use
the I should have used the striptease
thing where I obscure the last part of
its light anyway it's separable so
that's the big advantage here is that
when you minimize / z it decomposes into
em separate problems okay you can
minimize with respect to each of the
excise separately okay so you can just
pick out the X I turn from here pick out
the X item here pick out the X item here
and in parallel simultaneously whatever
I can solve this problem for each X I ok
so it gives me a very natural way to
paralyze an algorithm for this for
solving this problem so all in all a 80
mm for this problem I've got to step
here which is probably the expensive
part of it but one that I can decompose
and solve in parallel I've got this step
which I have to perform on some sort of
master processor I have to gather in the
results of all the minimization for the
excise and then sum them all up and do
something with the lambda i's and then I
have to update the lambdas and again I
can do that by in parallel this can be
done in parallel as well so the
advantage of using a dmm to solve this
problem is that most of the computation
can actually be parallelized okay other
words is not obvious just looking at
this how to paralyze it I guess it I
guess one obvious way to paralyze it is
you can just evaluate all the gradients
of this and and do those in parallel who
all the all the f is simultaneously so I
guess there is another way to do it okay
so here's another important way when
you're dealing with matrix optimization
problems sometimes in these problems
you've got a feasible set that's the
intersection of two sets questioning
yeah yes exactly yeah yeah if we go back
to this let's go back to the general
form if one of F H is a is an l1 for
example then the corresponding step you
just becomes a cell thresholding step so
if you think of this as being l1 then
you've just got when you do this
minimization here you've just got l1
plus a quadratic term involving Z and
that just that just becomes a sore
thresholding step so it becomes quite
simple to solve at least if if B is
their identity it becomes soft
thresholding it be as a general matrix
it becomes a quadratic plus in l1 and
again you can solve that using sparser
or some algorithm like that so again it
becomes relatively easy yeah
often yet often is competitive yeah
often it's it really depends a lot on
the context but it's um it's often
competitive with interior point or
better than interior point for sure yeah
again it's very context dependent and
it's very dependent on how easy these
subproblems are to solve entering point
can't really deal with non smoothness
here where as we've just mentioned that
if H is in l1 then you know this is good
you can still do this interior point
it's not so obvious how to deal with
that you'd have to reap Rama tries it to
make it smooth for instance so there are
factors like that that you have to take
into account yeah this one yep yeah if
these are l1 yeah so as some of these
are L 1 then this so some of these would
be thresholding type operations yeah
yeah
yeah if you're going to regularize least
squares problem then you can think of
that as being m equals 2 and f 1 would
be the least squares part and f2 would
be the regular eyes part okay and then
actually that's kind of what y'all is
that's one of the methods that I plotted
earlier it sort of does that it
basically does what he said so it's all
these it solves these subproblems where
it it updates the you know has the two
copies in it and one of the steps is
kind of a threshold eng step yeah the
advantage is actually not so clear
you'll sometimes competitive but it
really depends one of the subproblems
are still kind of hard to solve because
you still have a least squares in one of
these guys and so to solve that
subproblem you sort of have to invert
and a transpose a plus some multiple of
the identity and in your your one they
do that approximately they have an
approximate way of doing that and they
have to bring in heuristics to make it
competitive but
you could but then you'd have to settle
for an approximate solution because you
wouldn't be minimizing exactly over the
X I you know you'd have a narrative
method where you can be iterating
towards a solution and that actually
brings up a point the idea of inexact
implementations of a dmm there wasn't
much theory about those until recently
because obviously in practice you want
to be able to get away with in exact
solutions here and it's only been in the
last couple of years that people have
started coming up with convergent series
for in exact methods in fact I wasted a
chunk of my summer working on in exact
convergence theory only to find that
someone else had done it already so I've
got a real grudge against these methods
anyway okay all right I do want to say
something about this in the last five
minutes this is a very popular problem
where you've got to constraint sets that
individually are not very hard to deal
with but their intersection is difficult
to deal with so these constraints this
is a matrix optimization problem where
one constraint says I want the matrix to
be positive semi-definite that's what
that is saying X here is I'm taking to
be a square matrix okay the square
actually a square symmetric square
matrix okay and this constraint is
saying that I want all the elements of X
to be individually non-negative okay so
these are two different constraints and
it turns out you can project onto this
set by itself pretty efficiently by
taking a singular value decomposition or
an eigenvalue decomposition and just
throwing away the negative eigenvalues
is setting them to zero so it's easy to
project under this set and it's easy to
project under this set you just take the
negative elements of X and set them to
zero so they're easy to deal with but
dealing with your intersection is much
harder okay so how can you solve this
kind of problem using a dmm well here's
the general form let me write this down
in general form I just want X to belong
to a bunch of different constraints
Omega hi and I'm assuming that I can
project onto each Omega I efficiently
but dealing with the intersection is
hard
so I sort of come up with the same idea
as on the previous example I make copies
of X I make up one copy of X for each
constraint set let's call it X I and
then I add these constraints that say
that all of the excise have to equal x
and the limit okay for all for all I
going from 1 up to him so right the
problem like this and then I do a dmm
and I do it in the same way as I did on
the previous slide okay so i will almost
the same way but the difference is that
when i write down the augmented
lagrangian for this the first term has
an f of X in it it doesn't have any
terms involving the excise the excise
only come into the constraints okay but
it looks like I've skipped the details
here but now in this case that the part
that's easy is the minimization over the
excise because to minimize over the
excise I just have to minimize a
quadratic with actually with an identity
Hessian here but I have to project back
onto the set the constraint set for that
the ice constraint set okay so this
usually is easy depending on how
difficult it is to deal with this
constraint set okay and then to minimize
over the X which is the other step in a
dmm I no longer have any constraints all
the constraint sets are gone I just have
the original objective plus some
quadratic x okay so this is how we deal
with intersection of awkward constraints
and then you update the multipliers like
this so this turns out to be a pretty
good method for solving problems like
that okay so on one step of Manila
grungy and you're minimizing over these
two set separately and then you're kind
of doing this amalgamation where you
bring them together okay so this is
pretty much where I have to stop the
other half of this deck which I'll leave
for your viewing pleasure basically is
considering a slightly more general form
in fact a slightly more specialized form
of the form we've been discussing where
the B matrix is
the identity and it turns out that a lot
of applications in image processing look
like this they have this kind of a form
and so some of the papers that have been
written actually deal with a special
form I'll just point to this slide here
where the first kind of one of the
foundational papers of a dmm is this
paper that came out of Eckstein's thesis
he wrote the thesis in 89 the paper
appeared in 92 and if you look at the
citation record for this it's really
interesting because it was around for a
while you know people knew about this
paper for a long time it got you know a
steady number of few citations a year
and then suddenly in 2008 the citation
count started to blow up because people
started to find that this was incredibly
useful in a lot of these applications
coming from signal reconstruction image
reconstruction so it's starting to
plateau again now but it really went
crazy for all and as i mention this Boyd
paper is 2,800 citations so I'll let you
look at this Mario added a lot of slides
here with different kinds of image
processing problems showing how it meant
Lagrangian can be applied and how it's
more efficient than competing methods
then I have a slide at the end about
remember i mentioned that i think in the
first session this morning i mentioned
this problem of recovering the sparse
inverse covariance matrix and you can do
that also using a dmm and i've got a
couple of slides demonstrating how to do
that but i'll leave them for your
viewing enjoyment thank you very much I
made it
yep yep yep yeah let's see where was it
okay okay yep yeah well first of all
this is not my approach on this problem
but certainly there are other ways to
solve this problem and I don't really
know how they compare so certainly that
what you mentioned could be competitive
on some regime for sure yeah there are
other ways to deal with this in fact I
think when I saw that I did solve it as
an sdp I had a problem like this that
showed up in some context that right did
use an stp solver yeah so all of these
things are very context dependent that's
why you'll see comparisons on a set of
test problems between vastly different
approaches and sometimes one of them has
an advantage sometimes the other one
does so you know what we've got here is
a toolbox of a bunch of different kinds
of methods I've only mentioned a few
today and that's what modern
optimization is like in these
applications there's no one best method
that fits all instead you've got this
toolbox of different techniques and you
sort of have to dig in the toolbox and
combine different methods maybe take
elements of different methods and you
know join them together in weird ways
use some imaginative merging and use
some a lot of domain knowledge
knowledge is incredibly important making
these things work and eventually you get
some method that works well that's what
that's how things work these days yeah
often it's just some kind of i'm trying
to think because they don't know these
problems all that well often it's just
in the ennis thing so you're trying to
find the nearest matrix to it could be
just X minus y frobenius norm squared
for example so you're given a matrix why
they're just trying to find the matrix
close as to why that's doubly
non-negative you know that might be one
example that's probably the simplest
example I'm sure there are others that
I'm not thinking of right now not really
no I can't actually I've been asked this
question a lot but there's no recipe
book anymore really you just have to you
have to come to tutorials like this and
and you know the other talks included
and learn enough about the recipe so
that when you're presented with a
problem you kind of recognize some
distinctive features for which certain
approaches are kind of useful and then
try a bunch of things out so no there's
not a it'd be nice if I could draw it
draw a flowchart you know with a like
those all the design diagrams that leads
to have in the 60s where you ask these
questions you know is f non convex yes
no you're not go in these different
directions there's f quadratic yes know
if quadratic is at least squares yes no
but maybe you could do that to some
extent but I'm not sure how useful it
would be yeah so it's a hug that's a
hard question to ask
make any next information yeah but you
make it the wrong yeah produce efficient
perturbation of regulations in such a
way that the one consciously try to have
on average the right plane and speed up
anyway convergence yeah let's look at
this this is you know I didn't talk
about stochastic it over front seat he
should ask him that when he talks about
it more tomorrow or Thursday one way to
do that is that you should make a
conscious attempt to touch all of the if
you've got a finite sum you can make a
conscious attempt to touch all of the f
is right so the way the classic
stochastic gradient applied to this
problem as you pick one of the eyes at
random and on the next iteration you
pick another I at random independently
of the previous high so in general you
have to be lucky to see all of the eyes
using this a coupon collector argument I
don't know if you're familiar with that
but if you're picking a I at random each
time through from a collection of em
items with high probability you end up
picking all of the eyes after about M
log M iterations okay so but if you
systematically try to scroll through
these in some you know random order you
can get better behavior and there's that
people are sort of starting to
understand why that's true it's not so
obvious but part of it is what it has to
do with what you're saying and that when
you do a complete pass through this
you've actually got something closer to
the true gradient of the whole function
then if you just pick eyes at random
every time there are these algorithms
call sag and saga which people are
France this is probably an author on
those papers which are kind of
combinations of true steepest descent
with the entire function
and stochastic gradient this there's
sort of a hybrid of those two things and
for those algorithms they can get a more
stable convergence behavior than just
classic stochastic gradient but you
should ask her for a cease about that
when he talks tomorrow it's a very
interesting it's still a very current
area research yeah good question I don't
know you can imagine they can imagine
juggling the X and Z ok but as I said
here we go here we are here you can
imagine changing the order of the x and
z or picking them randomly or something
but as I said Eckstein claims that doing
it this way is in some sense the best
way computationally on the problems that
he tried he couldn't really improve on
this by doing you know wild variations
of this and I think he has some analysis
to support way that's true as a paper of
him and I think as a yang that appeared
maybe last year where this is explained
yeah I mean you should not be afraid to
do crazy things here that's that's
another motto is that a lot of
developments that have happened have
come from people just trying crazy
things and then later on trying to
understand why they work okay so you
should feel free to try things like that
on your problems and if they work that's
great and then we can try to figure out
why okay
thank you