try to remember okay so this is where we
were we were talking about group
sparsity where you want to look for
solutions where certain predefined sets
of variables are turned on and off as a
group and the ways that we enforce that
is by by means of these group regular
izes so you break the unknown vector
into sub vectors corresponding to the
group's and then you take take the norm
separately for each sub vector and then
just add them up okay and this seems to
be fairly effective way of inducing
group regularity now if I just squared
this and sum them up then it would just
be the two norm of the whole vector
squared okay which is something
completely different so it's important
that we're only taking we're taking a
true norm here not a square norm that's
very important okay all right and there
are weighted versions as I talked about
and I showed you these pictures earlier
on okay different kinds of mix norms and
then the choice where you take the
Infinity norm here okay so different
scenarios first of the ones I've been
talking about up to now which is where
the groups don't overlap that's kind of
the easy case then there are cases where
the groups are structured according to
some sort of tree structure that comes
up alone and wavelet type applications
and the third one is where you've got
structured according to groups in a
graph okay so non-overlapping groups
where the different the partitioning of
the elements of X into group really is a
partition where there's no overlap
between them there's no intersection and
they then the union has just thought set
of all the indices and then you get
these kinds of norms that I talked about
okay tree structure groups this is where
the groups are designed so that there is
overlap between the groups but if there
is any overlap one is inside the other
one okay and so you can form kind of a
hierarchical structure of the group so
for example you could start out with
these three groups and then it could be
another group which is inside the blue
group and then it could be another group
that includes these two groups okay and
so you can actually make up
a tree based on the different sort of
groups so you start out with these first
three groups here on the bottom and then
the blue group is a super group of the
first one and the purple group is
includes the bottom two and then there
could be a group that includes all all
of those injuries okay so the rule for
here is if you decide not to use a group
that means all its descendants are also
not included as well so if I decide to
set this group to zero it means that all
the elements in the green group are also
0 okay and if I turn this group off the
purple group it means that these two
groups also do not appear in the
solution so there is a kind of a
structure in the solution okay Laura it
looks like here I want to say a little
bit about matrix inference problems so
these are analogous to finding the space
vector the most the vector with fewest
non zeros that satisfies a system of
equations okay that's mostly what we
talked about in the first session but
there's an analogous problem when you're
dealing with matrices in the case where
X is a matrix and M by n matrix you
could be making linear observations of
the elements of X okay so you could be
observing a specific element of X or you
could be observing a linear combination
of the elements of X and so be now
contains the observations that you make
about X and operator B contains the
description of how the observations are
collected okay so instead of looking for
the sparse matrix X that satisfies these
observations you might be interested in
finding the lowest rank X ok that
satisfies these observations and under
certain conditions on the observation
operator here you can show that the
lowest rank if you're looking for a low
rank X this process solving this problem
will actually find it now the rank
operator is very much like the
cardinality operator is a close analogy
there ok and the rank operator the rank
of X is just defined as a number of
nonzero singular values
okay just like this operators defined as
a number of nonzero elements of X so
there's a close analogy between this and
this however this is just as hard a
problem as that one just like this in
general is an np-hard problem so is this
an np-hard problem minimizing the rank
subject to there should be a constraint
here should be that this is less than or
equal to some threshold okay and so this
is also a hard problem so we want to
look for a more tractable version of
this problem okay and it turns out that
the more tractable version has given us
by the new clean on that I defined
earlier today so the nuclear norm of a
vector of a matrix X is just the sum of
the singular values and there was some
work on this by been wrecked and Candice
and others around 2010 that showed if
you replace the rank by the new clean
Orme then given that certain conditions
were true on the operator be that that
solving the new clean on problem
actually gave you the same solution of
solving the rank problem okay and just
recalling what the definition of the new
clean or it's the sum of the singular
values of x another way you can define
that as the trace of the square root of
x transpose x I like this definition
better okay it's kind of more it's
easier to say some of the singular
values all right you can come up with
different variants of that so this is
like the one norm of the matrix in some
sense you know the singular values you
can come you're going to replace that
with a sort of a Q norm these are called
schatten norms so that's where you just
take each singular value and raise it to
the power Q and add them up and then
take the q throught okay there are other
norms if you take Q equals to you get
the Frobenius norm and that's also very
important norm that's just the it turns
out you can define that as being the sum
of the squares of all the elements of X
and they take the square root of that
and then as the spectral norm the
spectral norm is just the maximum
singular
so there are particular cases of the
shattered norm and the nuclear norm is
just the case where q equals one of
course ok so if using the new clean or
MERS the regularizer rather than the
rank you can write down the ticket of
formulation which is the sum of the data
fitting term with some multiple of the
nuclear norm this looks a lot like what
we had when in the case of the ex being
a vector ok where we had the one norm
here and the sump and the square least
squares operator there ok when you've
got a well we're assuming these operated
these observations are linear and that
means that each observation in the in
the operator beta is given it you can
define it in terms of a matrix B I ok
and so you can think of the eighth
observation as being the inner product
of a matrix B I with a matrix X and the
inner product of two matrices the
conventional definition of that is just
the trace of B transpose X you also get
it by just taking the products of the
corresponding elements of the two
matrices and then just adding them all
up it's like an inner product ok and in
the particular case of matrix completion
that's the case where each matrix has it
has 11 and as everywhere else 0 so
matrix completion is the case where I'm
observing a single element of X ok each
observation is the observation of a
single element of X so that's a
particular case where bi almost all the
entries in bir 0 except for one of them
which is a one so why does the nuclear
norm favor low rank solutions well
remember we had this soft thresholding
operator when we were dealing with the
one norm and a zero norm I reduced it
down to a single variable and showed you
what happened when you took the
minimizer of Y minus x squared plus the
one or more lambda times the one norm of
Y or of X and we were able to write down
explicitly what that was
well it turns out in this case if you do
the same thing here if you look at the
solution of this problem where this is
the new clean or operator then it turns
out that if you know what the SVD of Y
is if you know that it's you x sigma x v
transpose just reminding what this the
singular value decomposition it's a
product of three matrices where this one
is this one is an orthogonal matrix
let's see which is the bigger number
here well okay these are both matrices
with orthonormal columns u and v are
both matrices where the columns are
orthonormal vectors okay they're all
orthogonal to each other okay and Sigma
in the middle is the diagonal matrix of
singular values all right so the
solution of this problem where you're
trying to find the matrix X that's
closest infra be Gnaeus norm to why but
also satisfies this additional objective
I'm sorry this here should be an X not a
gamma okay that should be an ax in there
okay the solution to that problem you
can write it down and closed form and
actually this here should be a gamma I
think this should be a gamma okay so I
think you need to switch we need to
switch these two was that I'm thinking
this should be a gamma and that should
be an X here okay because it turns out
you can write down the closed form
solution of this problem x is the
clothes solution of this minimization
over X it's just the matrix you get by
taking the same orthogonal vectors U and
V but you replace the vacuole replace
the matrix in the middle by the soft
thresholded version of the matrix okay
so you take each of these singular
values and you do that soft thresholding
operator that you did with the l1 norm
but you apply it individually to each of
these singular values okay so what that
means is that if the singular value is
bigger than tell you subtract our from
it okay so its bigger than tell you
replace it by itself minus
well if it's less than tower you just
replace it by 0 okay so the takeaway
here is that and this is basically what
you do in the one norm case so this is
more evidence that the nuclear norm
applied to matrices acts a lot like the
one norm applied to vectors ok of Y so Y
is the matrix that were given and X is
going to be the version of way after
we've done this regularization on it ok
so at our equal to 0 X would just be
equal to Y we're done but we want to we
want to come up sort of with a lower
rank version of why that's the purpose
of this so this is giving us a lower
rank version the reason that it's lower
rank is that when you do the soft
thresholding operator some of these
singular values get set to zero ok the
ones that a lesson tower gets set to
zero so the bigger that you make tower
in general the lower the rank is going
to be because more and more of the
singular values will be set to zero and
ultimately wen Tao gets bigger than the
biggest singular value then the solution
will just be zero ok solution will be x
equals zero I'm sorry about that typo
that should be an X and that should be
lambda ok so ok here's another
interesting inference problem that you
can do with matrices that's quite a
popular one so suppose we are given n
samples of a Gaussian random variable
and they're all drawn from the same
random distribution the same normal
distribution with a given mean mu and a
covariance see covariance matrix e ok so
we're given these n samples so we can
form a sample covariance from this using
as usual expression then what we'd like
to estimate is the inverse of inverse
covariance now why do we want to know
the inverse covariance influence
governance gives interesting information
about the components of the random
variable so in this random variable Y if
you've got to come
opponents that are conditionally
independent that is why I and YJ are
conditionally independent given that we
know all the other components of the
vector okay that will be revealed by the
fact that the IJ component of the
inverse covariance will be 0 okay so
it's an interesting problem to figure
out what this what this inverse
covariance matrix is given nothing more
than a bunch of observations of the
random vector okay so we're assuming
here we don't know what C is we're
trying to figure out the inverse of see
just by making up making a bunch of in
of observations of why okay so you can
write down a log likelihood function for
this and it looks like this the unknown
here is P which is the inverse
covariance that we're trying to recover
s here is the sample covariance matrix
this is the log of the determinant of P
this is the trace of SP and then there's
a constant time now it turns out that if
you just ignore this term here and take
the derivative of this with respect to P
you just get that p is equal to s
inverse okay which sort of makes sense
all right just to first the best guess
you could probably make of the universe
covariance is just to take the inverse
of the sample covariance okay the
derivative of this with respect to P is
just s the derivative of this with
respect to P is P inverse so when you
set that to zero you just get P inverse
equals s okay your p equals s anyways
however unless we're very lucky that's
going to give us a dense matrix it's not
going to reveal these conditional
independence a--'s that we're looking
for so we like to impose some structure
on P so that it will show up you know of
the elements of P which are the witch of
the small elements of PR noise and which
ones really should be 0 if we took an
infinite number of observations so how
do you do that well you take this
objective and you add on a
regularization term which we've been
doing all day today okay so what's the
appropriate regularization term in this
case it's just what you get by just some
all the absolute values of the elements
of P and taking the one norm okay so
just take the absolute values of all the
elements of P and just sum them up so
I've got this operator vector P which
just transformed the matrix P into a
vector and then I just take the one norm
of that ok so that's my regular ases I
of P so I add that onto the objective
and so what's going to be the effect of
this it's going to find a matrix P
that's close to being the inverse of the
sample covariance but also it's going to
try to make it sparse okay and the
bigger that I make tell the more sparse
it will make it so this is an
interesting a thing to do in fact that's
all I'm going to say about this for the
moment but this this formulation is
often used to recover inverse
covariances it's very useful when you're
observing random matrices that have a
graph structure for the dependence
between the so when you're observing
random vectors where there's a graph
structure for the dependence between the
components of the vector the nonzero
elements of P will tell you where the
hikes are in the graph ok so it's used a
lot when you're trying to analyze social
networks and things like that all right
here's another thing that I hopefully
will be able to say more about in the
later in this hour and that's atomic
norm regularization this came up in our
work from about 2010 involving been
wrecked and Venkaiah Chandrasekaran and
public Perillo I think and and one other
Alan we'll see I guess from MIT so this
one goes to the heart of what we're
doing in all of these cases and all of
these kind of sparse recovery things
basically what's going on is that we've
got an unknown X and we have prior
knowledge but the unknown X is a
positive conic combination of a of a
number of atoms okay so X lives in this
ambient space and most of what we talked
about today X has been a vector in RN
okay where it's been a matrix in our n
by n however the exit we're really
looking for belongs that really belongs
to a much smaller space
and in the case that we talked about
earlier it belongs to a space of sparse
factors say with the most que non zeros
or it might belong to a space of low
rank matrices and so in general you can
formulate the exit we're looking for has
a combination of a small number of atoms
so in the case of compressed sensing
each of these AIS might just be a unit
vector in RN it might be a vector with
just zeros everywhere except a one in
one location okay or in the case of
matrices each AI could be a matrix of
rank one okay so that the X that we're
trying to recover is a combination of a
small number of of elements or atoms in
this in this ambient space okay so
that's in general what we're trying to
do so you can define a gauge on the
space to be let's see you can define it
to be okay yeah you can define it to be
the infimum over T of a positive T such
an X is below okay so this this a by the
way is a set of atoms it's the set of
its the atomic set that spans the
ambient space kind of the building
blocks for the space so in the case of
RN the atoms could just be each of the
unit vector Z the atomic set would
contain n elements in the case of
matrices the set of atoms is actually
infinite because there are infinitely
many Rank 1 matrices of size M by n okay
and the exit you're looking for could be
a combination of any number of them so
the the set a could have infinite
cardinality okay but we can define a
norm of a given X bite by taking the
minimum teas such an x belongs to t
times the convex hull of a pay being the
set of atoms all right so I'm going to
assume that a is centrally symmetric
about the origin so in fact if I'm
dealing with our n he atom the atomic
set should be all the unit atoms and
their negatives okay because I like for
convenience i like to keep all the
coefficients I like to think of all
these coefficients C I as being non
okay so we can define a norm like this
and therefore we can then define the
atomic norm we can show that that's
equivalent to the infimum of the
representation of x in terms of the
atoms okay so I look for the you know
there are typically infinitely many ways
that I can represent X has a linear
combination of atoms from the atomic set
but if I find the one for which the sum
of the coefficients is minimized that's
actually equivalent to the norm ok so
this atomic norm gives us a very natural
regularizer it's very natural users as a
regularization function in those
contexts that I talked about earlier
okay so here's an example in
two-dimensional space the atoms would
would just simply be the two unit
vectors and their negatives and if I've
got a vector say minus one fifth and one
then the minimal representation of this
or one of the mineral minimal
representations is one fifth times this
vector plus one times this factor and
that gives me a norm of 60 to 50 k which
happens to correspond to the one norm
okay and so there are others you can you
can show that most of the interesting
cases that we've talked about today can
be posed in this form you can for things
like rank new clean or minimization and
l1 and so on you can write down atomic
sets and you can express the l1 norm or
the new clean or in terms of an atomic
norm defined in terms of that
appropriate atomic set okay and I've got
some examples there okay so that we can
then write all of the problems that
we've been talking about earlier we can
write down the regular eyes problem in
terms of the atomic norm and we can
solve that guy so we already have shown
today that by considering special cases
of these atomic norms we can come up
with various formulations and different
there are different alternatives in the
formulation we're going to talk a little
bit more about solving those special
cases but it's sort of interesting to
think about can you design algorithms
that were
in general with the atomic norm
formulation regardless of what context
there's norm is cropping up in and it so
happens that the Frank wolf approach is
very well suited to this general
formulation also known as conditional
gradient and if i get time I'll say a
little bit more about that later on it
turns out to be a very good a framework
for dealing with general atomic norm
situations and I have a paper with a
couple of co-authors where we sort of
write down what the Frank wolf method is
it's a very general very elementary
method and show that you can adapt it to
many many special cases of the atomic
norm form ok ok so the summary of the
first part of this talk were that we've
shown that many problems in inference
and learning and signal image processing
can be written as optimization problems
that regular eise's that induce some
sort of sparsity play an important role
in recovering solutions that are
interesting there are different ways to
induce sparsity different ways of
imposing its parts of the ticket of way
the eve arnold way and Maura's offers
the other one I think it's possible to
go from vectors two matrices and atomic
norms provide kind of a unified
framework ok well the rest of it's just
references so ok so let me switch to the
second deck if I can figure out how to
close this one down is going to be
exciting there we go
no G handle like an expert okay I'm not
a matter i'm not a Windows user so I'm
surprised I was that went so smoothly ok
so now I'm going to talk about first
autumn methods and this over that's
quite a bit with what proceeds talked
about so but you know you might enjoy
seeing my take which is a little bit
different and it also does it doesn't
completely overlap there was some
aspects that are not quite the same
alright so but fortunately some of the
notation is the same I think he was
using mu for the strong convexity
parameter so we're doing the same thing
here so at least that much is the same
all right so I'm going to talk mostly
about first order methods here and
accelerated first order methods and so
on ok but unlike France I'm going to
assume up front that I'm dealing with a
smooth function f so that this
derivative here really is a derivative
it really does exist and it's got a
unique value ok so we're going to assume
that the eigen that the eigenvalues of
the hessian of f are bounded below by mu
and above by l ok now if we're dealing
with convex f this lower bound is zero
at worst mu is 0 and but in the case
where mu is positive then we've got a
strongly convex situation and that we
know that the function f has at least
some sort of positive curvature and as
Francie's pointed out you can say more
about algorithms where the muirs
positive you can prove faster
convergence rates as we'll see in a
moment you can also talk about the
conditioning the conditioning is the
ratio of the two extreme eigenvalues and
the closer they are together The Closer
that Kappa becomes 2 1 and the easy the
problem becomes to solve so if Ellen
Muir very similar capper is not much
bigger than one and it turns out that
first order methods are very effective
they converge very rapidly ok as we'll
see all right so often we'll talk again
Francie's great minds think alike he
also spent a bit of time talking about
convex quadratics because a lot of what
you learn about first order methods you
can observe just by looking at the
quadratic case so a lot of
I'd say we'll focus on that all right so
what's the setup here we're talking
about iterative methods and in the
classic sort of greedy iterative method
like like steepest descent for example
the neck you generate the next hitter at
XK plus 1 that's your next guess at the
solution it's some function of X K okay
typically it uses XK and some
information about the gradient of F at X
K there are other methods which I'll
talk about when you use information not
just from xk but also from the previous
error at XK minus 1 and surprisingly you
can get significant advantages by
looking at the last two edits there also
might be methods where you look at the
entire history of the edits all the way
back to the initial literate x0 but it
turns out you don't get too much more
benefit from that you get most bang for
the buck just looking at the last two
okay for reasons that I'll talk about a
little bit later all right so I'm going
to assume that we can always evaluate
the function and its gradient at any
point now in the case of learning which
is mostly what Francie's talked about
you typically can't do this okay because
the F consists of a sum over all the
observations you've made of some loss
function and to evaluate F and great if
you have to look at every term in that
sum which is impossible to do in a
practical time so that's why he moved on
so quickly to talk about stochastic
gradient however in compressed sensing
and other image processing applications
it does make sense to evaluate these
there are reasonable algorithms where
you can get these in a reasonable amount
of time and see these these methods are
not completely irrelevant to the image
processing signal processing and so on
okay now even though i'm talking about
smooth problems here the source of
algorithms i'm talking about do
generalize to more general situations so
by making in some case pretty pretty
minor tweaks to these methods you can
get you can extend them to non smooth
functions
you can extend them to the case that
Francie's was talking about stochastic
gradient methods where you can't
evaluate f they serve as the motivation
for those methods as you saw this
morning you can again this is to cass
degrading where you can only get an
estimate of the gradient in the case
where you've got constraints where
you're trying to restrict X to a certain
set then these methods are still kind of
relevant they can be specialized to that
case and they can also be specialized to
the case that we were talking about in
the first session where you've got not
just F but a regular eyes version of F
ok so these algorithms can be adapted to
those kinds of scenarios ok so here's
the classic steepest descent approach
also known as a gradient descent and
this is truly descent ok so descent is
often a misused word in this context
because some of these algorithms
actually don't always go downhill but
this one does provided you're careful
about how you choose the Alpha the step
length the idea is you just had in the
negative gradient direction and that's
intuitive in the sense that if you think
of the contours is giving you the great
you know if you actually draw a picture
of what the graph looks like and you put
a ball at the current point XK it's
actually going to roll in this direction
if you release it from a resting
position it's actually going to roll in
this direction ok so it seems to be a
natural direction to go in ok so the
trick is how do you choose how do you
choose an appropriate value of alpha K
well traditionally in optimization for
years in years before optimizers
collided with people at do signal
processing and compressed sensing and
learning we sort of assumed that you
could always evaluate F ok and it wasn't
too expensive so our approach was that
we chose some initial value of alpha
let's call it alpha bar and we tested to
see when we plugged in alpha k equals
alpha bar we tested to see if this gave
us a decrease in F and if it didn't then
we just tried one half alpha instead ok
and if that didn't work reach right
one-quarter alpha and so on so he just
kept backtracking eventually you're
guaranteed that if you're not already
out of minimizer where the gradient is 0
then this is guaranteed eventually to
give you a point with a smaller
function value and you can prove that
using an argument based on Taylor series
ok Taylor series is kind of the
foundational Taylor's theorem I'm sorry
Taylor's theorem is kind of a
foundational theorem of smooth nonlinear
optimization okay and it will show you
that for a small enough alpha this will
always give you a decrease all right so
that's one approach and I guarantee that
in your lifetime you're probably going
to write a code that does this you know
dozens of times because it's so easy to
do this you just have a little loop
which tries this and then tests effin
and stops when you get one that works
okay so this is okay provided it's not
too expensive to evaluate F another
approach is that you don't try this you
just try to make some prior value of
alpha K based on what you know about F
and suppose you know the bounds on the
eigenvalues of the hessian of f you know
what Ellen muir then you can come up
with a version of alpha that's
guaranteed to work okay and I'll show
you what that is on the next slide or
you can maybe gain some experience and
this is in practice what a lot of people
do in learning they get a very good feel
for the sorts of data sets are working
with and the sorts of functions that
they working with they get to to learn
themselves what an appropriate value of
alpha is so they can make some kind of a
smart choice of alpha okay and this is
very obviously very user dependent very
applications dependent all right okay
but I'm mostly going to talk about I'm
mostly going to talk about number three
here number two by the way is kind of a
smarter way of doing backtracking you
can actually make educated choices of
alpha K by doing sort of an
interpolation along the line defined by
alpha okay so you can sort of fit
quadratics to the values of Alfea you've
tried so far or I think it's time for a
break let's take our two-minute break
okay
so okay so here's this is the case when
we're trying to find an alpha that you
know what conditions do we require an
alpha to make sure that we can prove
that the method actually converges to a
minimizer so when you're looking for an
alpha that's more or less you know doing
a good job of reducing the function you
typically want two conditions to be
satisfied first of all you want to make
sure that function decreases but it has
to decrease more than just by an
infinitesimal amount you actually wanted
to decrease by some multiple of alpha K
times the norm of the gradient squared
so this is a slightly stronger condition
than just requiring that in UF piece
less than the old F and there are
examples that show that if you don't
require this you can get stuck at a
point that's not optimal okay so that's
the first condition and the second one
says that the grading at the new point
transpose a great into the current point
should be bigger than or equal to this
now what this means if you're actually
finding the the alpha that exactly
minimizes F along the search direction
this will actually be zero okay this
directional derivative will actually be
0 so this is a relaxation of the
directional derivative so these are
called the wolf conditions and these are
kind of conditions that allow you to
prove that this thing will converge to a
solution and what you can do if you've
got if you're able to evaluate F without
much trouble he can just do a
one-dimensional line search for alpha K
and you can prove that it's you know
within a fairly small number of
iterations if you're reasonably clever
you can find an alpha K that satisfies
both of these conditions okay
backtracking that also works I won't
talk too much about that but here's what
i mostly want to talk about because this
is kind of in line with what Francis was
discussing this morning so you can
actually do a Taylor series expansion of
F yeah you can do it you can use
Taylor's theorem which basically gives
you a way to approximate f of X in terms
of the function value at a nearby point
and its derivatives okay so if I play if
I apply Taylor's theorem
to using xk as the anchor point and
trying to estimate f of xk f of xk plus
1 i get this expression that f of xk
plus 1 is less than or equal to this so
if i can choose the alpha k to make this
thing here positive and in fact to make
it as big as possible then i can
guarantee that i get a certain amount of
decrease in f over this step and this is
a nice quadratic function okay and so
it's possible to choose alpha to
maximize this guy and it turns out that
the maximizing choice is 1 over L okay
so if you said alpha to be 1 over L this
thing turns into one over 2l and you're
guaranteed to get this much decrease
okay so using this we can actually show
that the whole thing is going to
converge to a minimum in other words a
minimum is a point where the gradient is
0 but you can actually say more than
that you can show that it converges at a
certain rate okay which is nice so
you're guaranteed not only to get
convergence but to get some handle and
how fast it's converge so let me show
you I've got two or three slides that
summarize an argument I think I saw it
first in nest droves book in 2004 which
which Francie's also referred to so
let's work through that argument so if I
just rearrange this formula i get the
gradient on the left hand side and the
difference of the two latest function
values on the right hand side ok now
just some both sides from from 0 up to n
where n is some hitter it okay some
random literate so you get telescoping
of this some of your cancellation of
successive terms and on the right hand
side you're left with two old times if
the initial F of x0 minus F of xn plus 1
and here you get the sum of the squares
of the gradients now if you know right
away this gives convergence because if
you know a priori that the function is
bounded below which you often do know
right in cases that we're dealing with
we know that the function is always
non-negative for example so if you know
that you know that the right hand side
is bounded and that immediately means
that the gradients of F with respect to
X K are going to 0 so right away this
guarantees convergence okay
okay what else can you say against of
proceeds had very similar arguments to
this by applying Taylor's theorem in a
slightly different way you can find that
the distance if you've got a unique
solution that the distance between XK
plus 1 in that unique solution is given
by the distance between XK in that
solution squared minus this amount so
again okay we can use G this is very
similar as the argument on front thesis
slide we can see first of all that
you're always getting closer to the
solution with every step because this
just this is just 1 over 2l so the
distance is always shrinking to the
solution set that's good news ok now i'm
going to introduce a delta k as being
the non optimality measure in the
function f so this distance between F of
XK and it's optimal value so you can buy
convexity you know that you know that
this is less than or equal to that
Francie's drew a picture that
illustrated way that was true earlier on
that's less than equal of that this is
the set kosher Schwarz inequality
because the size of an inner product is
bounded by the product of the two norms
of the two vectors in the inner product
and then that's bounded by that because
I've just replaced xk x x0 and because
we're always getting closer to the
solution i can bound this by this ok so
using that let's see what's my reasoning
here I'm able to say that yeah I'm able
to go back to this page and subtract f
of X star from both sides ok so if i
subtract f of x star from both sides
this becomes delta k plus 1 and this
becomes delta k all right so i get dacic
that expression there and now how do i
get from here to here i guess i used
this guy ok so i used i use this guy to
bound this i found a lower bound on the
gradient of f of xk I said that's
greater than or equal to Delta K divided
by X 0 minus X K squared so that's how i
got from there today so now I've got a
recurrence relation on the dell
two on dealt on the sequence Delta K and
I'm getting that the delta k is always
getting smaller and it's getting smaller
by a certain amount now this allows me
to get a rate ok this is telling me not
only that Delta K is going to 0 but by a
certain trick just an algebraic trick I
can show that it's going to 0 at a rate
of 1 over K so here's the trick you take
the reciprocal of both sides you take
this expression and take 1 over both
sides and then do a bit of bounding and
mess around a little bit and what you
end up being able to show is that 1 over
delta k plus 1 is greater than or equal
to k plus 1 over a constant and then if
you flip them back again that means that
Delta K is less than or equal to
constant over k plus 1 so this is pretty
cool ok you've been able to show that
for a function where the the eigenvalues
of the hessian are bounded above that
steepest descent with this very naive
choice of step length actually converges
at a rate the function values converge
to the optimum at a rate at 1 over K all
right not only they converge but they
converge at least that rate so that's a
pretty nice observation now I want to
point out that this is even though this
is a nice observation it's still really
slow ok 1 over K is a really slow rate
so in other words if you want 10 times
the amount of accuracy you have to do 10
times as many iterations ok that's
pretty slow all right but still it's
something now in the case of strong
convection you can say much more about
the convergence rate using the same
sorts of naivety in the step length all
right so let's go back to the definition
of strong convexity and let's look at
what happens when I take the
approximation to F of Z based on on
what's happening at F at X K so I can
get this down for F of Z a lower bound
on F of Z ok so this analysis is
different from the 1i just presented
it's even simpler and it ends up giving
me a stronger rate ok now this is the
key expression I've taken an arbitrary
point Z and i found a lower bound on f
of z now i minimize both sides ok i can
minimize the two
independently and that greater than or
equal to will still be true so I'm going
to choose a Z that minimizes that side
and that Z is obviously going to be the
optimum X star ok and I'm going to
choose Z that minimizes that side and
that's something different from X star
ok but when I plug that Z and I get this
on the right hand side so I'm able to
show that this is a lower bound on f of
X star so I can get a lower bound an f
of X star in terms of the function and
the gradient had xk all right that's
pretty neat and now by manipulating that
I'm just taking this over the right-hand
side over the left hand side taking out
over the right hand side and so on I
find that the gradient of F of XK is
bounded below by 2 times mu so I'm
dealing here with the strongly convex
case where mu is positive so this
gradient squared is mounted by 2 times
mu times the non optimality measure in
the function ok so I've already derived
from the previous slides I'll use this a
lot in the last few slides that F of XK
plus 1 is bounded below by FX is bounded
above by F of XK minus this so what am I
going to do with this i'm going to
subtract f of x star from both sides of
this ok lo and behold and then i'm going
to replace this by this bound ok so
subtracting f of x star from both sides
and using this bound this is what i end
up with that the non optimality at the
new iterate xk plus 1 is this factor
times the non optimality at the previous
iterate so we're able to show that you
actually get a decrease in the in the
non optimality measure by a constant
factor that's strictly less than 1 at
every iteration ok so that's what's
called a linear or geometric rate of
convergence and that's an that's
typically much stronger than that one of
a que rate that I had on the previous
slide ok so if you want if you've got a
thing like this and you want you want to
find out how many iterations do you need
to get a solution that's 10 times more
accurate when you've got an algorithm
that converges like 1 over K you need 10
times as many iterations in
this case what do you need you need to
choose the number of extra iterations
that will make 1 minus mu over L to the
K be less than or equal to 1 over 10
maybe I've got that on the next slide
hold on yeah I probably do that
calculation later but let's do it
because it's easy okay the chalk all
right so I need to get a 10 times more
accurate rate I need this to be less
than or equal to 1 over 10 okay so this
is how many extra iterations I need k
iterations so how can I figure out what
K is where I can take the log of both
sides times K needs to be less than or
equal to minus log 10 ok now I can use I
can use the fact that blog of 1 minus mu
over L is approximately equal to minus
mu over L okay I won't get too fancy
with her it's an upper bound or low
about but it's approximately that okay
and so this expression becomes
approximately equivalent to k x minus mu
over l needs to be less than or equal to
minus log 10 okay and this tells you
that ke needs to be greater than or
equal to L over mu times locked n all
right so the number of extra interests
you need to get ten times more accurate
solution basically is related to the
condition number the ratio of lmm you so
if you've got a well-conditioned problem
where LM you are not very different you
can very quickly get more accurate
solutions okay you don't really need to
do much extra work you have much more
accurate solutions okay but obviously as
mu goes to 0 this number gets very big
and it degrades to that one over K type
result that we talked about earlier okay
but the thing that I want you to take
away from this is if you've got a
reasonable lower bound on the smallest
eigen value of the Hessian in general
you can get a geometrical or linear
convergence rate
now sometimes in the literature
particularly in the machine learning
literature people call this an
exponential convergence rate I prefer
not to use that term because it makes it
sound like it's really really fast and
this is kind of pretty fast but not you
know if in the case where you've got an
ill-conditioned problem it's not very
fast you know if this is 0 point nine
nine nine it's still kind of slowish
okay but but you know it's better than a
sub linear rate which is what 1 over K
is okay there's an important point to
make here and that the linear
convergence analysis that I showed you
on the last couple of slides it
basically used to balance you go back to
what I did here and use these two bounds
and generally they look like this is an
upper bound on the norm of the gradient
of F at X K and there's a lot of and
there's a upper bound on F of XK plus 1
and we go on those two together to get a
linear rate so it turns out that for you
don't necessarily need strong convexity
to get these kinds of bounds so it's
been observed recently that in cases
where you don't have a unique solution
but the function f increases
quadratically as you move away from the
solution set but that's enough to get
these bounds and therefore that's enough
to get a linear rate and this is
actually useful when you've got an
entire manifold linear subspace of
solutions which you often do okay so it
you often see in machine learning and
statistics you often see problems where
we've got the objective function is a
function of a times X where a is the
matrix with more columns and then rose
okay so if your objective and F itself
is a strongly convex function okay so
because this is a composition of a
strongly convex function and a fine
function it's still convex but it's no
longer strongly convex if you take the
Hessian of this function it's kind of
it's going to have a transpose times the
Hessian of F times let's say a transpose
times
half impressionable times they so it's
going to be generically ranked efficient
is never going to be strongly convex
okay however if F is strongly convex is
an entire manifold of solutions and it's
the set of points where ax achieve some
constant value okay and we'll still
satisfy even though it fails to satisfy
strong convexity is still satisfies
conditions like that because it
satisfies a quadratic growth condition
and so you can get linear convergence it
for problems like that as well so
generalized linear models that crop up a
lot and statistics often have this form
and so you can't get linear convergence
rates for them just like you get for
strongly convex functions also it's been
observed recently that the second one is
a special case of what's called a kadoka
lovis image property that's a property
that that has this forum where you can
show that the gradient well the growth
of f as you move away from the optimal
set it grows at least as fast as some
power of the gradient okay what that's
telling you is that the gradient is
telling you something about how
suboptimal you are okay you don't get a
situation when you're a long way from
optimality but the gradient is still
small so that's kind of intuitively
important because it means that a first
order method which is basically making
all this decisions based on the size of
the gradient isn't going to be fooled
you know if the gradient is telling you
something about how far you are from
being optimal first order method is
having a chance of working that's
basically what this condition holds it
but it's a weakened condition and strong
convexity and then this is the one I
just talked about here where F has the
form of a linear a composition of an a
phone operator and a strongly convex
operator okay they're fairly recent
observations at these things things nice
things happen in these more general
cases okay so you might ask the question
that you know I've done all this
analysis for a naive choice of alpha K
can I do better if I choose alpha K
exactly that is every time I do a search
I picked the alpha K that actually
minimizes F along the search direction
well we can do an analysis for just the
case where f is quadratic that shows
that no we can't necessarily do better
by doing the exact line search and I've
done the analysis here I don't think I
want to go through it in too much detail
you can show though that that each step
length you choose will be in the range
of the extreme eigenvalues be somewhere
between the inverses of the two extreme
eigenvalues and if you use that
minimizing alpha k you can actually get
an exact expression for how much the
function decreases at each step it will
decrease at a linear rate you ensure
that you get a linear improvement but
it's not much better than what you get
by just taking the standard 1 over L
step okay so in the case where we took
the naive step what we got was 1-1 /
kappa by taking the exact step we get 1
minus 2 / kappa squared which is factor
of 4 better basically okay but factor of
4 better but it's not radically better
okay so we don't get a massive quantum
improvement by doing an exact line
search in general so it's sort of a
negative result ok so the Sloan linear
rate when you're talking about applying
a gradient descent to ill-conditioned
functions the slow linear rate is kind
of typical it's not pessimistic you
really do see slow convergence at that
rate it's not just a bad up about so
this is the classic picture of what you
get when you've got a ill-conditioned
function in two dimensions bill
conditioning is implied by these
elongated sort of opera elongated
ellipses being the contours when you
start from a point here you tend to
zigzag back and forth across the valley
only making slow progress towards the
solution okay so there's this idea that
i mentioned at the start where and it's
not a totally intuitive idea of using
momentum and the first maybe the first
method in this class is called a heavy
ball and the idea here is that each step
is not simply a step in the negative
gradient direction but you also keep
going in the door
section of the step that you just took
at the previous iteration ok so the step
from XK to XK plus 1 is a composite of a
negative gradient step and a
continuation of the previous step all
right so we can analyze this and this
analysis goes back to a 1985 book by
polly ack we can come up with an
analysis of this by and by looking at
what happens over two consecutive steps
so I i can define this vector WK to be
the error vector taking it to successive
iterates and i can look at what happens
when k goes to k plus 1 and what we can
show is that this is the change you know
to first order this is what happens to
WK it gets multiplied by this factor by
this matrix bit of beta okay so you can
see that the second component of WK plus
1 is just going to be xk minus x star
and that's the same as the first
component of WK so that's why I've got
identity 0 here and you can show by
doing a sort of a Taylor series
expansion on the gradient that XK plus 1
minus 3x k plus 1 minus X star is
approximately minus alpha times the
optimal Hessian times XK plus x xk minus
x star so how do i get this term i get
this time by adding by subtracting from
here grad f of x star now gratifies x
star is 0 right so I'm free to subtract
it from here now grad F of XK minus grad
f of X star is approximately and keep
losing the chalk sorry here it is ok so
I grade F of XK minus grad f of X star
is approximately passion of f of X star
transpose XK money what times xk minus x
star so that's how i get that term
here okay and then that you can figure
out where that comes from so very simple
idea heavy ball because it's like a
heavy ball it tends to keep rolling in
the same direction but we tweaked it a
little bit in the direction of the
latest the latest gradient so okay the
trick is how do you choose these
parameters alpha and beta what's the
optimal way you can choose them to get
good overall convergence okay so suppose
that we do an eigenvalue decomposition
of the optimal fashion fashion of F at X
star so right the eigenvalues of this
like in this form then we can do an
eigenvalue decomposition of the matrix B
and we can figure out how can we choose
alpha and beta to minimize the maximum
eigen value of B okay that will give me
sort of the maximum contraction here
assuming I get close enough that I can
ignore this lower auditor so that's the
game to pick alpha and beta to minimize
the maximum eigen value of B it turns
out this is the optimal choice it's
defined in terms of the extreme egg
invaluable Hessian L is the maximum
eigen value kappa is l over mu where mu
is the snail stokenmait so making these
choices we actually get a faster
convergence rate let me tell you what
these choices are if Capra if the
problem is ill conditioned capper is
large so beta will be close to 1 and
alpha will be closer to 1 over L or four
over L ok so for ill-conditioned
problems beta we tend to mostly keep
rolling in the same direction but we put
a little tweak in the direction of the
latest gradient so we get a better rate
okay instead of one minus one over kappa
which is what we get for steepest
descent we get 1 minus 2 over square
root of kappa ok and that's
significantly better so if I'm looking
at how much how many interests do I need
to improve the error by a factor of
epsilon in the case of steepest descent
I need some I need something I need a
number of it it's proportional to kappa
x log epsilon ok that's what i got in
that analysis over there ok but if i'm
doing heavy ball i only need
of capital log epsilon so if you're
dealing with an say a fairly
ill-conditioned problem where capra is a
thousand in in 30 times fewer steps so
getting a faster linear rate is really
helping out here so momentum really
helps okay but you might say well heavy
ball this is a kind of an old
traditional clunky method you know
surely this is an idea that's come and
gone well in fact this idea of using the
previous step has actually ubiquitous
it's been around in various guises for a
long time konjuh gradient is probably
the workhorse algorithm in scientific
computing in the case where f is a
quadratic function this is absolutely
ubiquitous in scientific computing and
it's basically a heavy ball type method
it's sort of an adaptive heavy ball
method we are adaptively choosing the
Alpha and the beta at every step so if
you look at the basic step in a
classical conjure gradient method it
looks like this it takes a step in the
direction PK but how is PK to find PK is
a combination of the latest negative
gradient and the previous search
direction okay so it's exactly a kind of
a momentum heavy ball method with an
adaptive choice of parameters that's all
it is and in non-linear kanji ogrady
there are various schemes for choosing
the gamma k and various convergence
results at approvable for that so kanji
gradients really a variant on the same
idea and you can prove the same sorts of
asymptotic convergence rates pecans
Ukrainian the analysis for conjugate is
very rich theory for conjugal crania
particularly for the quadratic case
there's a whole chapter in our book
about that now this is something that
France he started to talk about in his
life last slide and I hope he continues
to talk about in his next lecture this
idea of accelerated first order methods
and it traces probably to nesterov in in
1983 and it really can be viewed as a
variant of the same idea okay of the
same idea is using the previous step
sort of continuing partly in the
direction of the previous step and
partly in the direction of the latest
gradient information the difference
between this
and heavy ball or conjugate gradient
because it sort of teasers apart the two
the two steps it doesn't combine that
the previous step and the latest
gradient into a single step it takes a
step in the direction of the gradient
and then takes a step in the direction
of the previous step okay so you can see
that's what you can see what's happening
here it all looks very complicated
because there's kind of an adaptive
choice of the parameters but this is
where it starts out taking just a
classical negative gradient step that's
how it gets from YK to XK plus 1 and
then it modifies XK plus 1 by taking a
step in the direction you know that the
previous xk came from so it keeps moving
in the difference of the difference in
the last two x case so it's kind of
teased apart the two components of the
step and it's used it adaptive choice in
prov parameter beta k in doing so okay
so really it's using the same idea of
momentum as we as we've seen in these
other methods now Francie says that he
has there are many variants of this
accelerated first order method okay this
is the basic one jutsu nesterov many
others have been proposed since then
including many by an asteroid himself
and the theme is that you still get
these 1 over square root of Kappa kinds
of convergence rates you get the same
kinds of acceleration that you see for
heavy ball and these other methods the
bonus with with nesterov method is that
even when you're not dealing with a
strongly convex function you get an
improvement in the sub linear rate as
well remember for the sublinear for the
case of not strongly convex we got a 1
over K ray well here we get a 1 over K
squared rate for this accelerated method
so we get an improvement even in the
case where we don't have her strong
convexity okay so pretty nice pretty
nice results now this this method or
variant on this method came up in a case
of compressed sensing in the form of
this very popular Fister method judah
back into bool and it's a method of the
same kind of it's a sort of nestor of
acceleration method
you can see it looks very much the same
here there's the same sort of step in
the direction of the negative gradient
there's some messing around with a
choice of parameters and then there's a
step in the direction of the previous
iteration okay and they get the same
sorts of convergence rates they also
have schemes for the dealing with the
case where you don't r priori have an
upper bound in the eigenvalues there are
the ways and all these methods of
adaptively estimating an appropriate
choice of hell okay by monitoring the
convergence rate and continuing to
increase L until you seem to have it
right so the analysis in back into built
the thing about all these analyses is
that they're sort of non-intuitive they
write out these very complicated
expressions and then spot that if you
make various choices of parameters you
get nice cancellations happening back
into built do it pretty neatly in two or
three pages and none of the steps are
complicated but none of them you know
then one they don't naturally lead one
into another in other words it's quite
technical and I think that from season
as collaborators recently you've figured
out how to compress it down into
something that's somewhat intuitive and
also straightforward which is I think a
big contribution so this is all very
important these the workhorse algorithms
in in machine learning and compressed
sensing tend to use these concepts of
acceleration okay I'll say a little bit
about this crazy approach due to crazy
colleague of ours John Ball wine and his
postdoc back in the 1980s called Basel
oh boy now this is not a descent method
okay so that's why I call it a non
monotone gradient method it's turned out
to be useful in some situations and it's
very non-intuitive okay it makes choices
of the step length which sometimes lead
to very large increases in the function
value okay and I can draw a picture even
of what's going on this is what you get
with classical short step steepest
ascent in Basel a born you tend to get
steps like this you start here and you
zoom off to a point somewhere up here
where the function value is much higher
okay now why might that be interesting
well the reason it might be interesting
is it could be that the gradient of
point up here will lead you back to a
point where over a space of two
iterations you make significant progress
towards a solution so if you look what's
happening over a span of every second
iteration you actually are making pretty
good progress more than your what you're
making here so that's the magic of these
methods that if you view them kind of
more widely oh they make good progress
and in fact they've got analysis it
backs that up so how do they work well
just very briefly because they don't
have a lot of time to spend on this they
sort of mimic and Newton's method in
some sense okay so how does Newton's
method work when you're minimizing F
since I won't get to talk about it well
I think frosties will talk a little bit
more about it Newton's method for
minimizing F has it just takes the steps
like this it takes xk minus the hashing
of F at X K inverse times the gradient
of F of XK all right that's a classical
Newton's method has big advantages that
it converges quadratically it's big very
rapidly in other words it's big
disadvantage is that you need to be able
to work with a hash or estimates of the
Hessian and in many cases that's hard
okay so what did i do in Basel a boy
well they make the observation that you
may not know the Hessian but what you do
know is that if you look at the
difference between two successive
gradients if you use Taylor's theorem
that's approximately equal to the
Hessian times the difference between the
last two successive X Factor's okay so
Taylor's theorem says the difference of
the gradients is approximately the
Hessian times the difference of the
access so quasi-newton methods which
unfortunately I'm not going to talk much
about but there are another very
important class of methods they use this
they use exactly this expression to
build up information about the Hessian
by looking at the difference of success
of gradients so quasi-newton methods
keep track of the difference of each
successive pair of gradients and they
they know that that's giving them
information about the action of the
Hessian in a particular one dimensional
space so we're looking at what happens
over
sequence of iterations you gradually
build up knowledge of the Hessian so
Bosley boy and methods do the same thing
except that they make a lower very one
parameter approximation to the Hessian
they pretend that you can parameterize
this Hessian by 1 over alpha times an
identity okay so they find the Alpha
that gives you the best one parameter
approximation to this Hessian and they
do that by by taking this by taking the
difference of a gradients take the
difference of the exes and solving this
least squares problem to find the Alpha
which which minimizes the discrepancy
between the two sides of the expression
I showed you earlier okay and because
this is such a simple one parameter
problem you can solve it explicitly and
you can figure out and that that's the
step length they use so listen this
mimic this mimics Newton's method will
replace the Hessian inverse with alpha K
that's it okay alpha K times the
identity so it's a minute it's mimics
Newton's method way you replace the
Hessian by this very elementary one
parameter approximation okay and they've
got an analysis of this there are many
variants of this i won't i won't going
to they've got an analysis I've got a
short paper in 1988 a brilliant
non-conventional analysis that kind of
shows that unless you're very unlucky
over a sequence of iterations you're
going to get significant improvements in
the function value I encourage you to
read this paper it's very ingenious
boleyn is also an expert in special
functions and it sort of uses special
function type analysis which as far as I
know hasn't been used before a sense in
analyzing optimization methods but he's
a very original guy all right when you
want to extend I promised you at the
start when you're dealing with first
order methods most of them you can
extend to more general situations such
as where you've got constraints so the
Nash drop method you can extend it to
the case where you want to minimize F
over some constraints that Omega by just
changing one part of the method one line
in the method and that is instead of
defining instead of defining xscape
us 12 b YK minus 1 over L times the
gradient you solve this little quadratic
sub-problem where you minimize this over
way belonging to Omega so that's the
only change you need to make to turn an
algorithm for minimizing earth into an
algorithm for minimizing f subject of X
belonging to Omega okay do you want to
finish soon yeah sure two minutes is
that ok ok got it all right I thought
ahead to top of the year anyway that's
fine sorry about that ok you can you can
generalize it for regular eyes adopt
amuse a shin where we add on we add on
this taken off type regularization term
again you can just change the update
step to bring in that second term
explicitly I'll say more about that in
the last in the last session I think
I'll yeah I think I can stop here and
then i'll stop here and then i'll
continue in the last session ok