Stanford CS229M - Lecture 11: All-layer margin

Key Takeaways

so last time we talked about the generalization bonds and today we are going to talk about um uh some better generalization bonds for these Networks so recall that last time what we did was that we show something like the rather macro complexity is bounded by something like this times and polynomial of the norms of the the weights right so and we said that this comes from a kind of a worst case bond for ellipsislessness um of the of the model um foreign over the entire worst case over the entire input space and this is because when we do the covering number we have to use this Ellipsis decomposition this lipsticks composition level and and there you have to um use the um uh you have to use the lipstickness for the entire set so this is a little bit distracting in the in the in the life just because I'm sharing the screen using my laptop so that you can charge my iPad um okay so and we have discussed a few motivations for us to improve upon this uh theorems right so I guess we discussed four of them and one of them I guess I'll just briefly mention them in words one of them is that you know this bond is exponential um exponential in depth which is bad because typically you have a lot of players and another thing is that you know this is worst case lupusiousness and one another thing is that typically you want to have something like um SGD prefers um Ellipsis models that's good but this is Ellipsis models you know and where Ellipsis is on the empirical data because if you think about an algorithm and an algorithm can only do something on the empirical data right so you know so we'll show this more like later in the course but even if you think about it right so like on a high level right so the algorithm can only prefer something about empirical data but not about the entire space right and and and also we said that for tighter Bond we're going to have something of data dependent right something that depends on the lips on the empirical data so concretely I guess today we're going to do is that we are going to show something like this the generalization of parameter Theta is a function of lusciousness of f Theta on the empirical data X1 after X and and also the norm of theta and this function is a polynomial so that there is no any exponential dependency there's no Paradox of things so so that's the goal of this lecture and we're going to call it so and we we have to do like the we have to Define some kind of like I'll introduce some new Machinery to achieve this kind of things the reason is that this is a different type of phone than what we have done before because you can see that on the right hand side you have a function of the tuning data so typically on the right hand side right so the the so-called Club let's call it classical uniform convergence I guess you know what really uniform confidence really mean that's slightly kind of debatable because it depends on how you Scope it but at least what we have discussed in this lecture all the bonds are doing something like this right so the bounds before we all look like for every Earth in some hypothesis class f the the law the empirical loss is less than something like a complexity measure of um of of capital F over square rooted something like this right so or you know like maybe with high probability something like this and all alternatively we can also achieve this kind of things I think we in implicitly discuss this right so for every Earth L of f is less than a complexity measure of little f over square rooted so so here this is capital f so the first type is what we do exactly you know what we got exactly from random marker complexity because you just you know apply random marker complexity on it and and this is in some sense they write the marker complexity and the second type you can also get it by doing a little bit things from the first type so you can get the second type yeah by something like I guess this is a remark by considering F to be something like all the functions where the complexity of legal f is less than Capital C right think of the complexity as for example Norm of the weights when you first Define hypothesis class where the norm of the weight is less than Capital C and then you apply uh one on all on on capital f on this hypothesis class and then you do a unit Bond and then and then take a union bound on all C right so for every Capital C it defines a hypothesis class and you probably can write it as f 2 F Sub C right so and for this subject F Sub C you can do the standard random marker complexity and then you can say that I'm going to enumerate over all possible Capital C and then do another layer of Union Bond on top of it we didn't we never do this formula but this is just one parameter you can just discretize whatever you want so so in some sense this is how you get the type 1 type 2 bound but the thing is that either of this bound on the right hand side the bound depends on the data the empirical data it's always a property either of the model or of the function class so so the question is you know how do you if you want to get something like this right like our goal today you have to do something kind of like more um uh you have to include some new techniques right so our goal right so our goal is to get something like I think maybe let's call this I think we call this data dependent Bond generalization Bond this term might be a little bit kind of overused in certain cases you know but but what I mean here is that you want to have a bond that with higher probability for every f your population loss is less than some maybe complexity of F and the empirical date so the right hand side is also random variable that depends on the empirical data of course the you you're asking this for high probability right anyways right so you're asking that for all for with high probability over the choice of the empirical data this inequality is true and and this is useful in the sense that you know this is useful in a still kind of useful in a sense that you can regularize the right hand side you can you can add the rhs as a regularizer right so not only this is explanation in some sense but also it can be used actively as a regularizer because the right transfer is something you can optimize right so so this is kind of the goal that we are uh trying to achieve so um and in some sense I think you know I used to have a little argument about you know why this is actually the right thing to do it's kind of like cheeky because you know uh these days still there's no consensus on what exactly kind of generalization you are looking for you know I'm I believe that this is one thing that is good to have but you know uh but there could be other forms of like generalization blocks um in some sense you can argue that this is um the best you can achieve in the sense that you know you cannot you know have a stronger one on the right hand side because for example you cannot replace this empirical uh data by population description right if you replace that then you can just choose suppose you allow the complex measure to depend on the population distribution suppose you allow that I can have complexity of F and the population distribution T then why not just Define this to be LP of f like sorry why not to Define this to be the population risk what if you allow this why not just Define to be something like tax from p f x right so the population risk would be a good complex measure then it sometimes you lose the the the gist here in some sense it becomes too trivial and in some sense they suggests that you're cheating in some sense by allowing the complex measure to depend on P so in some sense the kind of the fundamental question we are facing about this we are facing about in the generalization bound is that you don't have access to the population distribution you want to have an empirical measure for your complexity so that you can use that for regularization by the way but you know it this argument is kind of like I know a debateful so so for now we just say that this is a one of the reasonable goals right so okay and and why doing this is challenging um uh I think the the first thing is that this is challenging because you cannot do the simple reduction as as we have done before so so the reduction from type the reduction between one two type one type two bonds uh doesn't work anymore foreign for example let's define capital F to be all the way to F such that the complexity um of f X suppose you say this is less than C um suppose you define this right this is your hypothesis class and let's say suppose our we attempt to use you know as an attempt is that you use f is rather marker complexity for capital f worst issue why we cannot do this the reason is that if your complex Network depends on the data then your random hypothesis class also depends on data before your complexion identity depend on data your hypothesis cost is just a fixed hypothesis class so so now it's a hypothesis cost that depends on data so f is also a random variable depending on data data in data means means empirical data right and then you can use the writer marker complexity like the theorem for random marker complexity but why the random Market complex debunks the the generalization over that theorem requires the capital F to be a fixed hypothesis class that is fixed before you draw the the random data so so that's the that's the challenge Okay so and how do we uh adjust this so in some sense the kind of like the the way to the high level way to to address it is to kind of like redefine uh you have to have a refund way to think about you know uh uniform convert so some refund refund uniform converges this is not going to be exactly what we do like eventually because you know you what we do eventually will be something very clean and and doesn't have any kind of like kind of like personality but but this is kind of the roughly thinking how do you think about it so um so maybe let's make a make assumption these are some suppose the complexity measure uh is uh separable in the sense that this complexity of f on the empirical example is of some form like G of f x i right it's really some function of F and x i and you take the sum of them so suppose in this special case then you can think of essentially what we're doing is that we are considering then we can consider a an augmented loss so you can define something like L tilde f is equals to something like LF times the indicator that is complexity is less than C so in some sense what you are doing here is that you are changing the the loss function in some way so that it's easier for you to use the existing bar so before for example let's say the kind of the mental picture I have in mind is something like you have um you have a loss function which is like something like this maybe let's say this is empirical loss and you have some region and this is the region where you have low complexity right so but this region is a random region because the low complexity the definition of low complexity depends on data so this is random so that's why you can use the uniform convergence only on this low complexity region right so you cannot say that I'm only going to apply my uniform convergence for this region even though that's your goal but you cannot apply the random micro complexity Theory so so the the kind of like the this kind of like organic laws what is fundamental is doing something like it changed the geometry outside the the low complex region so you for example you just Define a lot newer loss function to be zero here and then um I like a the same thing as it as it was you know in the low complex region so now we have a globally defined loss function and so basically the the region that you are taking Union Bond over right the the the the hypothesis class is still the same but you change the loss function so so if you do this then you can hope to so can hope to apply like existing tools on altitude of F and l2.5 is sometimes kind of like a filtering thing that filters the the uh um the low complexity but but you don't do it you know technically right technically you are just changing the loss function that's the only thing you do but the effect of it is the same as you change the hypothesis class so so I think this is the first thing like this is the first attempt that we have done in one of our paper when we try to address this and and and this is actually the fundamental um on idea in some sense so so you change your loss function so that you can deal with different type of quantities of different regions of the hypothesis and then later um so so this is one of the paper we had in I think 2019 and we got some results and the the if you exactly do this indicator thing where you change the loss like this you can already get something but the kind of the the results are messy so then we kind of like um in some sense I think even more broadly right so so in some sense all this is doing is change the loss function right so so so you are trying to have a surrogate loss and and surrogate loss we are not actually unfamiliar with it right we have used the surrogate loss in the margin case right it's just that surrogate loss there is kind of like this the simplest way the simplest is surrogates loss so so so basically what we are um what I'm going to talk about today you know in the main part is this so-called you know Euler margin which is a different way of it's kind of like a surrogate margin and once you have this kind of like a like fake margin this is a kind of in some sense to define a new loss function for you and once you have this new loss function you can do everything in a super clean way and then uh you can um um like you can apply the existing kind of tools in some sense okay so this is a kind of like a sketchy a vague kind of introduction I'm not sure whether any questions so far oh sorry this is um I yeah this is the name of the the thing we are going to introduce but we're gonna introduce a new margin which is we call it only rematch I probably should Define it formally so um okay so some so basically the main point I'm doing I'm saying here is that we have not defined a surrogate loss and and using this surrogate loss the the point of the target loss is to change the original Law so that you can focus on the important part of the space and this target loss will be basically kind of boring for for this kind of like a high complexity part right they are just they are not doing anything they are basically zeroing out like in some sense and so that's the general intuition okay so now let's see how do we do that exactly so so we're gonna start with a generalization of of margin so um so let f um so this is a classification model foreign and your margin is just F itself right so the the typical margin the classic the the standard margin is just defined a standard margin is just equals to Y times f x Y is between plus one minus one right that's what we used before and now I'm going to define a so-called generalized margin we say g f x y is a generalized margin if satisfies the following two properties so the first part of it is that g f x y is zero if you classify correctly it classified correctly so I think I have typo here let me think sorry I think if you cast very wrongly and this will be larger than zero if f x y is classified correctly so let me mark this important type of sorry okay so and you can see that you know this is trying to imitate the the standard margin right the first standard margin is bigger than zero if you classify correctly and otherwise you say you zero it out so that's a like external Market also this is only defined only defined for correct classification right so so in some sense you can extend to incorrect classification just by extending it to zero and so and we and we say that you know like uh and there's another small thing which is that we have to define the so-called you know infinite carbon number so um this is defined to be L Infinity Epsilon f is the this is a small technical extension of the L2 carbon number it's not that you know important in most of the cases it just makes the in some sense the in some cases it makes the definition cleaner um and in some cases it makes the proof a little bit easier so so our Infinity carbon number is the minimum cover size with respect to the Matrix row your row is defined to be this L Infinity Norm so basically you say that you look at the entire space of the input of F and you look at the difference between f x and F Prime X and and you take the soup so basically this is the F minus F Prime Infinity naught um so okay so given these two what we'll say is that um our Lemma will be that the with the you can have a analogous um Theory analogous to the modern Theory where you use this generalized margin and also the infinite cover number actually actually you can even do it without like a standard carbon number it's just easier to state with the infinite cover number and also maybe before doing that let me also have another remark which is that this infinite cover number is larger than the standard Auto covering this is just because the this is the more demanding notion because you are demanding that F and F Prime are closed at every possible input and before you are demanding that F and F Prime are closed on the empirical data right so this is because the metric that we used before was The Matrix that is smaller then the Matrix used in the infinite case Okay so so with this um small extension what we're going to do is that we're going to say actually we can have analogous modern Theory with the generous margin so the Lemma is that um so suppose GF is a generalized margin and let's capital G to be the family of GF where f is ranging over the capital n and suppose recall that this is kind of like what we are kind of like a this is in some sense just a slightly kind of like more complex version of your model hypothesis right like if you just use yfx then this will just be y times f x that's the hypothesis cause that's the class G and this is a little more General than that and suppose uh for some r a covering number the infinite covering number of G of G is less than R square over Epsilon Square for Epsilon and 0 for any Epsilon zero or I suppose you have this kind of like one over Epsilon Square decay in the low carbon number recall that this is one of the regime that we that is good right so this is the actually the the worst regime we can tolerate when we do the right Market complexity right so and suppose you have to understand with probability larger than one minus Delta the other is the failure probability which will be hidden in the in the logarithmic uh over the randomness training data for every F in capital f that correctly predicts all shiny example right so for margin we also we for and in the modern Theory we always consider functions that can correctly predict all the examples then you have the zero one error is less than of tilde of 1 over square root n times well over the minimum generalized margin plus altitude of one over square root so so to recall that basically before what we had was oh there's an R here sorry so before what we had was that here you have the standard margin standard margin the minimum margin over the entire data set and here R is the complexity of the model hypothesis class right and all the other things are mistake now the change is that now here you replace it by generalized margin and R becomes the hypothesis uh the complexity of the hypothesis class of this generalized margin GF right and the complexity is measured slightly differently we are using the the covering number but actually you can also use weather marker complexity here um it's the same I'm just stating it so that it's easier for for the Future Part um and this one is actually not very tight you can actually improve this Bond you know in some ways um but but that's but this is the simplest version and and the proof of this you know is basically it's just we just basically we use all what we have done with margin Theory it's just everything seems to just can transfer exactly so so just to replace in some sense the proof is just replace the f by G in the margin Theory I'll do this you know step by step um but but this is the short version so so so so technically what you do is let's still use the the Ram plus recall that the Run plus was the loss function that looks like this where this is a gamma red this part is gamma this part is one something like this and recall that before we after we have this run plus we Define this you know surrogate loss right so we Define a surrogate loss our height gamma data to be before we just apply it with the model but now we use the generator smart uh before here this was just F Theta but now it becomes like G of f Theta G sub F Theta and we can also Define the surrogate population loss which is just the expectation of the empirical loss okay so and before what we do it is that we use the radar marker complexity to control the differences of these two loss function wow we saw that you take L gamma Theta is minus L height gamma Theta is less than the import router marker complexity of f that's what we did before but now is to start before we did the Imperial number complexity of L gamma composed with f and now it's l gamma composed with g because the function class the function is different um plus o to the Power Square 10. sorry oh okay thank you so much yeah that's a so I would just switch to this I only have one charger but yeah uh no I think it's uh the problem is that when you use this I cannot charge uh right oh but I can wait it doesn't matter how yeah it's not the charger it's the the plug the the hole yeah okay so now it works okay good thanks uh okay cool so right so okay so so now we have to use the random mark on Flex day and then the radamr complexity is less than the copying number right so I guess maybe let's still do that let's do the cover number so cover number let's do some preparation so we assume the Infinity Property number but actually you know um it's um okay I guess let's say so the covering number the standard cover number composed with g the l2pn this is less than this Standard carbon number where you use the um by removing the the Algoma right so Alabama so l2pn because this is this step is using the Ellipsis deliciousness of agama so it's actually one over gamma Ellipsis right so this is using the ellipselessness of the carbon number and now next you say this is also bonded by the infinity version right and and then if the infinite version will have assumption the Assumption was that for every episode you this is less than R square over Epsilon Square gamma Square the last step is spell assumption okay so so you can see that actually you know even suppose you assume something about this then it's also fun if you receive something about um right so you don't have to you I literally use the infinite note um okay so and then because the this low carbon number is less than this and we have kind of like a this kind of like translation right so that if you translate low carbon number to random marker complexity you got are as our gamma composed with G is less than o tilde R over gamma squared overcome scorpion right this is by uh chaining a w theorem and and its consequences because we have discussed what kind of like cover numbers replies what kind of random marker complexity right so okay so and then [Music] the same thing I guess take gamma to be gamma mean which is the Min over I g i f say y i right so and then there this step is not form this some some there's some caveat here because gamma is a random variable you have to do Union Bond eventually but let me not get into it I guess we had this issue before as well um but it's only one number you can discretize and doing over gamma but suppose let's say we just take down what we Gamma mean and then foreign so then you got L 0 1 Theta then zero plus O2 off R over square root n times gamma mean plus some altitude of Y squared okay so this proof is not 100 formal just because the technical I'm not allowed to take gamma to be anything that depends on the data right so I have to really show it for every gamma um and that requires another inbound overcome foreign so maybe let's let's see what we have achieved with this level right what we achieve this this Lemma is that now if you define your basically you can fold everything you can try to fold everything in this generalized market right this challenge margin in some sense is a way to to twist your model output right so you can stretch the model output in for certain F and you can squeeze it for certain other app so in some sense this is what we actually will do right so we in some sense stretched the function for those places where we'll see you you see how we do it like you stretch the function according to where you are at and um so so basically everything is folded into this um thermos margin and the question is so the question now is that question so for what GF you can you can bounce the generalization error you can Bond the covering number of G right and also you want this GF to be something with meaning of also and so forth so and suppose you know if you just take GF to be the standard one yfx then the cover number of this GF will be the same as current number of F and it will be the then the rather Market complexity will be something like then a cover number depends on the product so so but but we are trying to do better than this okay so how do we do this so now we Define this so-called all layer margin this is a special instance of this GF this is a concrete definition of GF for which we can Bond the render marker or the cover number uh complexity so to Define this uh to Define this Euler margin this generalized margin right so we have to actually introduce some notations so we are considering some perturbed model so I guess okay I think maybe I think actually it's good useful to have some motivations before I defined I forgot to add this so uh in the our motivation is the following so if you think about the linear model and the the margin is defined to be the the margin the standard margin right so this like the you like the normalized margin to normalized margin is defined to be something like y times f x over the norm of maybe it says your model is double transpose X so your margin is defined to be y times the model output over the two Norm of w right so this is the normalized margin which is something that's kind of like governs uh the the generalization performance and the question is how do you normalize right so so like if you have deep model then you can try to normalize by something right so if you have a deep model you can so while attempt is that you can try to normalize by some quantity maybe this could be the product of the Ellipsis Network or maybe something else so that's the that's the natural attempt and in some sense all the previous work is in some sense doing this right you are normalizing the margin based on the worst case slips so and what we are doing is that we don't know we don't want to all normalize by only a constant that depends only on the function class so so we take a different approach what we do is we say we reinterpreted the standard margin by something else so so we have another interpretation so our interpretation is that you can view this as something like minimum Delta such that w plus Delta um trans sorry w times X Plus Delta y is less than zero so you're trying to find the minimum perturbation of your data point such that after perturbate you can cross the the boundary right so intuitively this is also kind of right because the margin is the distance to the boundary right so it's also the same thing as how much you can perturb it so that you can cross the boundary so so this is the kind of the perspective we take to generalize the margin for all for for deep models so if you take this you know there's some kind of like a small you know like if you do the all the exact math maybe something that match exactly but this is still kind of like the the the rough intuition about it and how do we do this exactly so um so for deep models we are still trying to take this perturbation based perspective but we have to perturb it turns out we have to predict all the all the layers not only the input so the the first attempt we tried is that you just perturb the input you try to see what is the smallest perturbation of the input so that you can change the decision of your of your model right but that just technically doesn't work it it doesn't seems to capture the fundamental complexity so we have to consider this um perturbed uh consider this percept model that perturbs all the layers so what we do is we have a perturbation Delta which is a cost sequence of perturbation Delta 1 up to Delta r and each Delta I is a vector and the way you perturb is the following you also have to work out the normalization in the right way um so your first perturb the first layer so the first layer used to be W1 transpose x w one times x you know deep net and you perturb that by adding the other one which is a vector times the norm of X the true Norm of x and then you perturb the second layer um so okay how do you predict the second layer you first apply W2 on the first layer on the perturbed version of the first layer and then you perturb it Furthermore with Delta two and how much you perturb those with what's the scaling in front of the other two there are two is a vector the scaling is the norm of the first layer so so how do the exactly Design This preservation is a little bit kind of like a tricky right so like we tried the virus versions in our research and it turns out this is actually make everything fade nicely so you can do this for multiple layers and then eventually you have this HR the OS layer perturbed uh layer is equals to you first apply the nonlinear The Matrix notification and nonlinearity on your previous preserved layer and then you perturb it by Vector Delta R scaled by the norm of the previous layer and after you define this perturbation you can ask you know what's the smallest preservation that changed my decision so you can and that's the definition of the lower layer margin which we call an F X Y this is the Euler margin is defined to be the minimum perturbation and how do you match the size of the pertivation you measure it by the sum of the two Norm of the perturbation of every layer and your Constitution is that after perturb I guess you call this FX Delta this is the perturbation of the whole model f x Delta after perturbation times y it becomes negative so incorrect prediction you can also do this for multi on labels but it's essentially the same so I'm doing binary labels okay so this is the definition of the all layer margin so you can you can see that the definition becomes much more complicated but then the proof of it will be easy and I guess you can also intuitively interpret this right so so M as X y so in some sense this is big if uh if it's hard to perturb right so if it's hard to preserve it's hard to change hard to change decisions of the network and how how could it be hard I think there are the two ways to make it hard to perturb right so one thing is that um the model f is ellipsis and this means that it's very Ellipsis so this means that you have to perturb a lot to to make a big difference of your a big change of your model output right so and another possibility is that your FX just is large in some sense your standard margin is large if a standard margin is large you have to change a lot right you also have to change a lot because before you're outputting something like positive where FX is very big and now you have to change it to another side of the boundary so then you have to perturb a lot right so or maybe I could I could say F like y f x y times f x is large so typical I also I always talk about about why is one so so positive means that you are very confident about your prediction and if you're very confident then it means you have to change perturb a lot so that you can change your um change your mind right so that the model can change it so much right so and here loves us you know technically this is lip system in the intermediate variables intermediate intermediate layers because you are measuring how robust it is to perturbation but the perturbation is done on the intermediate layers but Ellipsis needs in the intimidate layers it turns out that it's actually close to lapuousness with respect to parameters LL discuss that in a moment Okay so and and once you have all of this so then you have the following theorem so this is saying that with high probability um l01 f the zero one Arrow of f is less than o tilde of the following we have one over square root 10 first and then you have sum of this is the so-called one one Norm of w which I'm going to Define your moment and also minimum I am f x i why I plus o tilde of R over squared where is the sum of absolute values branches w I guess the in some sense you know we are in a method that anything polynomial in the norm doesn't really matter so doesn't matter that much so so so this is uh in some sense you just consider it as polynomial but of course you know you can also talk about you know whether this one to one comma one Norm is the right choice of the norm in some sense this is not the best Norm we can hope for so so there's still some have room for improvement here um but I guess you know suppose you ignore anything polynomial Norm so then what's important hitting here is the this all layer margin here so basically this is saying that if the Euler margin is always big then your generation is good if the other model is smaller then your generalization is bad and what's all your margin all the margin is about the perturbation your business to the intermediate layers so this is saying that if you're robust to perturbations robust to perturbations in intermediate layers and that implies that you have good generalization and you can also compare this with the bond that we've got before you can pretty much argue that this is strictly better than before um so so um so basically so compare because is this the right place for us to fix us I guess let me discuss this you know comparing with the pre-response later uh when I'm doing all the all kind of remarks about this theorem but but you can show that this is um better than the previous one mostly just because um this MF in some sense this mfxy it's kind of like roughly speaking you can think of it this as so like in the in the worst case I think this is smaller because maybe is smaller than well over effects something like this right so because this is ellipselessness and this is how much you have to change your output you have to change your output from FX to zero right so and and and this is our lipstickness so that's why you have to change you have to make a big movement to to change it to change FX from something like positive or negative to zero and and uh and and and and wait my bad I think I sorry I think I I'm doing the should be this um and um and so that's why this is kind of better than the previous Bond because the previous Bond didn't consider the different preciousness a different data point but here you are really talking about you know if your lips at the data point you have seen then you can uh generalize code well um but maybe let me discuss this more I think yeah let me have a more thyroid discussion about this like later I just don't want to I want to have a show a little bit of this just so that you don't feel like this is a huge response um but maybe bear with me and just assume this is useful and then we can discuss all the interpretations any questions so far oh well I'm doing fine okay okay so we have 30 minutes okay so let's just dive into the proof so um I guess the proof requires you know a few steps but um a few small steps so first of all it's it suffices to to bond foreign by of this by the way I think I have some sorry I think I have some typos here don't I think this should be this this should be this I'll double check it later because it's always a polynomial so I didn't really pay too much attention but I think this is a type of um so so so so I think you only have to show this okay um sorry I don't know I I don't know really what this I was gonna scrub no take out a clarification about this I think I don't know exactly where the square is applied inside or outside um but anyway you have to show some Bond like this right so let's assume this is the correct amount and then you basically have to show something like this um because if you have this then you can use dilemma before and then on the challenge margin you get this random marker this standardization ball all right so essentially we just have to bounce the cover number of t and it turns out that the carbon number of G you have uh this very nice decomposition name on so let's say let f i Define each layer the hypothesis cost for every layer right and we also constrained that wi one comma one Norm is less than beta I okay so then your your if is really f r composed with f r minus 1 up to F1 this is the notation we have used and recall that we had a kind of a decomposition limit before which was kind of complicated right so you have all of these dependencies and how the error propagates but now dilemma is pretty simple cool so so let's I'm composed with f denote its family of the earlier margin foreign [Music] the log of the infinity carbon number where the radius is just simply the sum the average in some sense a quadratic average of the radius on each layer and you care about the generalized margin this is less than the sum of the log if you know probably number of Epsilon I have to f i so so in some sense this is saying that you only have to deal with the cover number for every layer and then you got a cover number for the composed function class but you don't get the cover number for the compose function class exactly you get the cover number of the Euler margin of the composed function class so and here this early Infinity Epsilon if I is defined with respect to the input so there's the input domain to Define this common number right so the input domain X which is the the the one not the true Norm ball is less than what and so I guess the one of the important thing is that this is not uh this is an and right this is the Euler margin Okay so on the Corollary is that if each of the layer you can bounce the cover number by something like Ci Square over Epsilon y Square suppose you can bound this let's use letter C here so then take Epsilon to be Epsilon times c p i over sum of square roots C Square so I is equals this then we have log infinite Epsilon you have the carbon number of the compose model is less than sum of c i Square over Epsilon Square so which means that suppose you believe CI is a complex measure for each of the layer then you can get the complexity for the composed model the Euler margin of the compose model the complexity will be just the sum of CI score yeah I think I think I know I didn't have an error here I think this is indeed something like this yeah this was correct sorry Okay cool so and you see I will be something like see I will be something like the w i one comma one Norm and that's how you go through all these things right so so basically you know we will show we can show I think I will improve this but this is not this is all because this is for one layer right so we assume you can basically you know you can believe that you can basically invoke a theorem for linear model together so indeed it's true so for linear models um you get something like this and beta I was the bond on the so we call that beta I was the bound on the one comma one Norm of WI and this will this will imply the main theorem okay so I think I hope I convinced you that basically as long as you prove this decomposition level then you are done because you for the right hand side you invoke something about linear model and then you plug in Islam or you get the cover number bounds for the all layer margin and then you get the original zero using the the lemon I have shown before about the generalized margin Okay so any questions so far foreign [Music] for the concrete fi right which is the Z map to Sigma w i z you can also have you can State the landmark in a more general form and also you can prove it in a more general form but I'm only going to prove it for this particular family of F5 um and so the first step is that so so we'll show so the so the two steps step one uh we show that mfx is one ellipsis are in f and what one loop 16 f means is the following so for every Earth an F Prime MF X Y minus f f Prime x y it's less than in some sense the luciousness of every layer so you have all layers so this is some from one to R and you take the max of f i x minus f i Prime X to know X is so so here f is equals to f r composed with f r minus 1 up to F1 and F Prime is FR Prime composed with f r minus one F1 Prime so basically the largestness of this Euler margin is something that doesn't have actual scale in some sense because you are looking at the uh this this no no this power with no scale and also it only depends it's basically the sum of the ellipselessness or the sum of the um the differences between F5 and F5 Prime right so so there's no multiplier here right you are not multiplying on the the ellipselessness of f right so it's really literal stuff it's very clean um and let's prove this step one um uh your moment but suppose you have step one then you what you can get is that you can use step two you can use this step one just to get uh the theorem relatively easily what you do is you say now you construct a cover construct a cover and how do you do that you the cover is the construction is also kind of show you so what you do is you let U1 up to u r b Epsilon 1 up to Epsilon R cover of uh F1 up to fr respectively and recall that you know if you still remember what DVD last time the covering was very complicated right so you iteratively construct covers and make it you know very complicated but now we just individually construct covers for every fi and then and then we say UI such that UI is equals to this the infinite Norm carbon number and um and then so so this means that you know by definition right so we got that you know for every fi in capital f i there exists some function UI in capital UI such that f i minus UI is small right so and I guess we are using this metric this if Phenom metric f i x minus u i x to none is smaller than Epsilon this is window by definition and now we're going to turn this into a cover for the compose the family so and the cover is just a so we just take the U to be the family of just the composition of all of this the conversation of u r composed with U or minus 1 composed with U1 which is foreign and this is will be our cover and we'll show this is will be shown will be our cover for M composed with f and why that's the case this is because suppose we are given f is equals to FR compose up to F1 in capital f you you are up to you one be the nearest neighbor 's neighbor of f r up to F1 so then as you can see that using this ellipselessness this minus and as a u is equals to u r composed with 0 minus 1 up to U1 so look at this so suppose you do this this is less than using our step one sum of the difference between if I and UI the worst case difference between them over the normal one and because F and U are closed that's how we constructed the cover so we get square root sum of Epsilon I Square and from 1 to R okay so so basically you know once you have this such a nice ellipselessness so kind of lepslessness property then you can just cover everything individually and you don't have to think too much about conversation the conversations to you because it's deal with this it's dealt with but so so now and now why deluxiousness holds so let's prove step one so and so we only approved the upper bounds so we want to prove this by symmetry right because I find F Prime have the same row so you can only have to proof one side and you can flip them together other side and it sometimes the way to prove it is just really each of them is defined by some optimization program right and there are the solutions the optimal value of the optimization programs right basically you're trying to show the two optimization programs are doing similar stuff um and how do you do that hey people you construct optimal solution of one optimization program into a speedable solution to other optimization program that's how you relate to optimization programs so so let Delta one store up to Delta R star the the optimal choice of Delta uh in defining MF x y so and we want to turn so our goal is to turn this into Delta one height there's our gamma of feasible solution of MF Prime x y right so if you have a if it's a feasible solution you get NF Prime x y is less than sum of Delta I hat Square and then you can relate this to sum of Delta I using your Construction right so okay so that's the rough idea and how do we construct this the other one hand up to build the r height so so we wanted it to be feasible so that we can have this inner Corner this part is going to be the feasibility part so so basically the way we do it is that we want to construct so we want to make of Prime with the other one had up to Delta R hat doing the same thing as as and with the other one star up to Delta R star so basically on the perturbation on F Prime to do the same thing as perturbation the the perturbation of data I star on F so that then you know that this will be a feasible solution because what's the feasibility the feasibility is about whether you perturbed the prediction to to the other side right so if this this one can perturb the prediction to change the prediction to the other side then the other one also change the position because they are doing the same thing that that's the the the the the the the principle and how do you do that it's just pretty much just algebra right so F has parameter that's a parameter W1 after WR and F Prime has parameter W1 Prime up to w r Prime and let's consider the computation right so um I guess the the in the competition is this right so H1 is equals w1x plus Delta one star X S2 is equals to Sigma W 2 H1 plus Delta 2 Star H1 so and so forth HR is equal to Sigma w r h r minus 1 plus Delta R star h r minus one so this is the computation you did for this is the computation for for m f x y right so and I want to imitate this computation by perturbing F Prime in some way and how do we imitate that so the imitation is kind of trivial so imitate this so what you do is you say you take so for f Prime what happens H1 is equals to W1 Prime X plus something right plus and how do so and you suppose you predict the other one star X then it wouldn't help because this W1 Prime is different from W1 right so you have to predict something new addition to make this computation the same as before and how to do that is you perturb in addition W1 minus W1 Prime X and then these two are literally exactly the same so basically you declare this as my new preservation you declare this has to be now Delta one hat times x to know so so basically compensate the difference between W1 and W1 Prime by adding this additional perturbation so that means that Delta 1 Hat is equals to Delta 1 Star Plus W1 minus W1 Prime X over the two Norm of x and you do the same thing basically for every layer so now H2 you want H2 to be equal to the same H2 above but your first step is your only product being based on W1 Prime you are not pretending based on W2 so you are only practicing based on W2 Prime but not based on W2 so what you do is you first perturb the original one the one it gives us two star H1 and then you compensate the div by perturbing even more something like this and you declare this entire thing will be defined to be Delta 2 h one to naught and that means that the other two that you had that you had will be the other one two star Plus Something Like H one two Norm uh and the denominator will be Sigma W 2 H1 minus Sigma 2W 2 Prime H1 I guess you do the same thing for every layer and in general you just take Delta I hat to be Delta I Star Plus Sigma w i h i minus 1 minus Sigma wi Prime h i minus 1 over h i minus one and now we've got the same we got our goal so basically Delta one hat on F right on F Prime is the same doing the same thing as Delta 1 up to Delta r um I'm using this short answers too to save some time in writing so I'm saying that basically I'm saying you perturbed the Delta one has up to the r height from F Prime it's doing this exactly the same functionality the same prediction as the other one so that means that we this is a feasible solution this is a feasible solution for MF Prime so that's why MF Prime x y is less than the sum of Delta I had two Norm square square root and now this is uh this is equals to I guess I'm going to bound this by square root sum of the entire star to Norm square plus square root sum of the differences between them and this is using the so-called [Music] this is using the so-called mink misconf I guess I I always think of it as cautious words but I think there's a technical name which is called means minkowski inequality in the quality so what he's doing is that say stay in the following so if you look at square root of the sum of a i plus b i to Norm Square it says less than square root sum of a i Square and square root sum of bi to Norm squared so this is the mean meaning of inequality and actually you can prove this inequality by cosine squares by just X you take the square on both sides and cancel Bank of terms and it becomes