Gradient descent for wide two-layer neural networks
CC Attribution - NonCommercial - NoDerivatives 2.0 Generic:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Bach, Francis
Neural networks trained to minimize the logistic (a.k.a. cross-entropy) loss with gradient-based methods are observed to perform well in many supervised classification tasks. Towards understanding this phenomenon, we analyze the training and generalization behavior of infinitely wide two-layer neural networks with homogeneous activations. We show that the limits of the gradient flow on exponentially tailed losses can be fully characterized as a max-margin classifier in a certain non-Hilbertian space of functions.
 Thank you. And I would like to first thank the organizers for the event, very nice and sunny, and for inviting me. So today we need to speak about a lot of benchmarking, as you will see. And this is joint work with Enig Shiza. And when I say joint, this is more like me running after Enig. And so the topic of today is to look at gradient descent for, so, wide two-layer neural networks. So here I drew a very wide network. Okay, so we have the input, it will be X in RD. Okay, here we have M hidden neurons and a single output, which I recall Y. And so I'm going to restrict myself to a particular activation function. And I'm going to consider predation functions of the form f of X is one of M sum of I equals M from one to M of AI, Bi transpose X plus. So I'm considering the so-called relu activation function. So plus is just a positive part, the max of the argument and zero. So why is it interesting? So this is really a small proxy for deep learning. Okay, so it's a huge simplification, a single hidden layer. Okay, it's not really deep. No convolution, no pulling, no weird things. So good old, like fully connected neural network. And I'm going to focus a lot on this activation function. So why is it hard for us? Okay, so this is, the function is linear in A. So this would be the easy part, but it is non-linear in B. And this will create problems for optimization. And the other hard part will be that those are wide networks. So M, the number of hidden neurons will tend to infinity. Okay, so this is open code, the other parameterized regime. So here we're not trying to compare the number of observations or the number of parameters. We take M to infinity. And as we see, a big caveat in our analysis is the lack of quantitative analysis. So M is very big, and I will not tell you how big it needs to be. All right, so this is the setup. So why are we considering this? We're going to leverage two properties. One is what I call separability. So essentially your prediction function, F, is a sum of terms, okay, and the parameters for each of the terms are unique to those terms. It's a separable parameterization. And often I will use the notation F is 1 over M sum from i equals 1 to M of some phi of wi. Okay, just to highlight the fact that the sum of functions, okay, and so here, F is a function. So phi of wi is a function. So for example, so here, this corresponds to phi of wi at x is a of bx plus. Okay, so wi is the two-pole AB. And it's just to highlight that, okay, we have a separable function. Okay, and for the first part of the talk, I'm going to focus mostly on that setup. Okay, so just using separability. And if you look carefully, this works well for the one hidden layer. But if I add more layers, this will not be true anymore. Okay, the sharing of parameters, it's not true that beyond a single hidden layer, you're going to have some separability. So from the start, all the things I'm going to say cannot apply directly to more than one hidden layer. This is the first big assumption. And the second would be, so 2 homogeneity. Homogeneity. So what I mean by that is phi of lambda w is lambda square phi of w. Okay, so this is true for the ROLU. And this is why we consider the ROLU in this work. It's because the ROLU is homogeneous in A, homogeneous in B. And if you take the pair AB, it's two homogenous. Okay, so this is why we consider the ROLU. Before I move on, if you want to interact with me, please do so. Okay, you can get back at me. You have 35 minutes to do so. Okay. All right, so this is a setup. So we're going to consider a classical learning setup where we have some data. So it's xi, yi, nothing particular from i equals 1 to n and coming from qx, y. Okay, we have a loss. So this is not really particular. So you have a loss, L of y, f of x. And here we're going to assume the loss is convex with respect to the second variable. Okay, so it's convex with respect to the second one. And this can be logistic, this can be square loss. And I consider this as being a weak assumption even in the deepest of the deepest networks. They use what they call the cross-entropy loss, which happens to be convex. Okay, so I'm going to assume convexity in f. And I'm going to minimize the risk. Okay, so it will be the risk of f, the function f, will be an expectation of the loss, y, f of x. Okay, so here, depending on the setup, this will be the expectation with respect to the empirical distribution. And the average of the data, xi, yi, from i equals 1 to n, n, or this can be the expected loss. Okay, at the end, this is simply the risk. So it's convex in f because I assume L is convex. Okay, so this is a very, very standard setup. All right, so now I'm going to look at some properties. And I think the key here is that one big message of the talk, and this is true for several other talks, is that we cannot simply... So here, I've not talked about estimation algorithms. I just have some model, okay, I have a model which is at the top. I have some criteria which is there. And typically, it's enough, okay. Statisticians will tell you how to analyze this. And optimizers will tell you how to optimize it. Okay, so here, the key message that you cannot do this separately, very similarly to HGD. Okay, here you have to analyze some algorithm which is key to the analysis. And this will be, as the title says, gradient descent. Okay, so I'm going to study gradient descent techniques when I want to minimize the risk. And I have the parameters of F which are of that form. Okay, so in F, it's convex, but in W, it's not convex. Okay, why? Because Phi is not a linear function. All right, so this is a standard setup. Okay, so I'm going to do two things. Okay, so two parts from my talk. One is global convergence. The other is the idea that although we are non-convex, okay, in W, then if you let M go to infinity, and of course, there will be a lot of technical assumptions, we need to sweep under the carpet, okay. Then you do get some global convergence. This will be the first part of the talk. And then second, I will talk about what people call the implicit bias. The idea being that since I'm going to optimize with M big infinite, my space of function is huge. So typically, in particular when I minimize the un-picker risk, I have lots of minimizers. And among those minimizers, my algorithm will select one. And I want to study the one which is selected. Okay, and I will show like three different implicit biases, okay, and three different behaviors. And if you are nice, I will show you videos at the end. And so this is joint work with Lenaik and myself from 2018. And this is a mixture of something from this year and something with Edward Royalon, CBO, from last year. Okay, so if you want to know more, the papers are online. All right, so let's look first at the first element. And now I can use a reason why I give a talk on the blackboard is to play with the boards, okay. All right, so global convergence now. Okay, so the idea is to minimize, we're going to consider g of w. So it's a big w. So you have M weight vectors wm. Okay, if you go by the top board, okay, those are my weights. And this is simply the risk of 1 over M sum from i equals m of w. All right, so this is what I want to minimize. And the main gist of having M go to infinity is to write this as you're going to replace this empirical average by the integral of our measure, okay, and then you're going to optimize over measures. The weight is being done. And that you write it as you consider f of mu with the risk of the integral of phi of w d mu of w. And we're going to assume that mu here is a probability measure. Okay, so this is the way we're going to formalize it. So we have some probability measure. And if you take mu being the sum of the racks, you have that f of mu is g of w. Okay, so this is the main two we're going to consider. And these two are not ours, okay? So there's a long list of people looking at this. And I think this starts back with, I think, Baron, which you're Baron. Baron 83. So there is Andrew Baron in 83. There is Benjo, Le Roux, et al. 2005. And I've worked on it quite a bit while two years ago. Okay, so this is a very classical idea. And why is it so nice is that I've made my problem convex. Why? Because as a function of mu, so the space of probability measure is a convex set, okay? This is a linear function in mu. R is convex, so I have a convex problem. Okay, so this is, I've made my problem convex, but the downside is the fact that another space of probability measures on Rd is infinite dimensional, and it's going to be hard to optimize. Okay, so because it's convex, so what I tried first and failed miserably is to use convex techniques. Okay, so there's not too many talks about Frank Wolf, because it's not about one talk by Frank Wolf by Yifan. Then I have a big convex set, which is a convex set of many things, so I can optimize using Frank Wolf. And in Frank Wolf, you build your estimator incrementally, okay, as a weighted sum of elements, and every time you have to add a new element, okay? It's often called a Frank Wolf step. The problem, okay, the good thing is that if you can do the Frank Wolf step, you get a nice convergence rate as 1 over k when k is the number of iterations. But the downside is that to select a new neuron, you have to solve some problem called the Frank Wolf step, and this problem happens to be NP-hard. Okay, so you're replacing this hard problem, okay, which is not convex. You try to replace it by a convex problem, but every iteration requires to solve NP-hard problem, so it's not really useful, and if you want to know more about all the missed trials, there is like a few pages on that in this paper. And second, it's not that people are doing practice. It's tracked, but if you whiten the data. It is tracked, but if you whiten the data, what do you mean? There's a paper by Mark. No, yeah, I read the paper, and... We just got caught up. I read the paper, and tracked, but I think there's some powers involved. No, I think it's a mental issue. Okay, but... I had this from my reading of the paper in the airware. It doesn't mean like... It was not solving, but it's not the topic of today. The NP-hard problem is computing a brain, so... As an NPI, you want to do the Frank Wolf step. You have a gradient, you want to find a neuron which maximizes the problem with a gradient. It's linear classification, which is NPR. So if you assume some reduced... Anyway, it's not the topic of the talk, but... And... Yeah, so anyway, it's not people doing practice. In practice, people do just gradient descent. Okay, on this, okay, so this is gradient descent on the weights AB. So it's backprop, and we're going to study this. All right, so let's study backprop. So we're going to not use gradient descent. We're going to make our life simpler by using the gradient flow. What is the gradient flow? So if you do gradient descent, so... If you do hiking, so this is lumini, this is a canok, okay? So if you do gradient step, you do some things like that. So this is gradient descent. And gradient flow is like the limit with infinitely small step size, so it's more something like this. And this corresponds to the ODE, W dot, is minus M gradient of G of W. So the M is to make things easy when I'm going to take the limit when M goes to infinity. So this is what I'm going to minimize. So here, clearly, we go away from what people are doing practice, but it's the only thing we can do at the moment. And now I can hand wave my way through justifying why it's not too bad. So first, as I've mentioned, this is when your step size gets small, you get close to the gradient flow. And this is true both for the deterministic gradient and also for stochastic gradient. Okay, if you do HDD with a single pass, so you can see that the approximation of the gradient flow. So we need to study this one. Okay, so now the goal is to show global convergence of the gradient flow. What I mean by that is, I have option F, D final measures, and the goal is if I load the gradient flow on that function and M is big enough, I want to get to the minimizer of F. Okay, so this is what we are going to show. We're going to need two assumptions. So I don't want to talk about the technical ones, but the ones which are important. So the first one is, so two, homogeneity. Okay, so this is not necessary, but sufficient. And you can think of removing these constraints, and you get to, you can optimize anything. Okay, so this is unlikely to be true. And you're going to be going to need as well. So random initialization. Okay, so here I'm going to require that I sample all directions. I have put positive mass on all directions. Yep. I just, how do you define phi of W? Phi of W, this is W. So this is at the top. Okay, this is for neural networks, it's a function, and W is AB. And so we need to assume that you cover all the sphere of directions. Okay, so the problem is too homogeneous. So what you care about is directions. You need to sample weights. Uniform is simpler, it's simple, but you need positive mass everywhere. So one simple way is that W gargantuan, okay, that would be easy. And this corresponds to what people do in practice. Okay, they take A and B gargantuan, okay. So we're going to assume this, and then what we have, we have a theorem, and I put quotes because I'm missing a lot of the technical assumptions. Okay, then what we have is that when M goes to infinity, okay, so the trajectory, so the flow, goes to what is called a Vassarstein gradient flow. Okay, so the first part of the statement, so I will not define what the Vassarstein gradient flow is, it's just to highlight the fact that when you get M go to infinity, this does correspond to something which is well defined mathematically, and which you can analyze. Okay, so this is really just to make sure that what you cover is a PDE, and if you want to know more, you can look at the paper, or we can talk after the break. So this first thing, it does have a meaning, it has T, and if it has a limit, mu infinity, then mu infinity is an armin of F. Okay, so this is just a statement which I more or less expressed that as we get more and more particles, we often call the W's particles, you end up converging to the correct measure, so in a weak sense, okay, it has to be a weak sense because we have a bunch of Dirac's, and we may get to a density at the end. And so this has like a lot of limitations, so let me write them down immediately. So first, some other papers that do similar things, so there is Nintendo and Suzuki, who are already showing the first aspect, and there is a Me and Montanari, Monta, you know Montanari, okay, who are doing also similar things, okay, so it's a bit different, but so Nintendo, they prove, they prove convergence to a vassal gradient flow, and Me and Montanari, they prove convergence if you add some noise, okay, so it's a bit different, but it's interesting. Yeah? The two homogenities for phi or for G? For phi, so phi. For the four phi. For phi, yeah. So here, so if you take my setup over there, the loss is any convex loss, it is just for phi. So this applies to, but there are other situations, so this applies to spike decommolution, this applies to matrices, so this is like more general than neural networks. So there are big caveats, that this is this, if it has a limit, okay, so we've tried for several months to show that, to give summation conditions for the gradient flow to have a limit, and in the Euclidean case, this is known to be possible with like the Euclidean conditions, but for Wasserstein, we are not able to do it, so we simply assume that it does have a limit, okay, this is the first issue, and second issue is that this is very qualitative statement. It's just when m goes to infinity, and when t goes to infinity, okay, I will not tell you how big m needs to be, so how many neurons do I need, I don't know, and how big, and how fast am I converging, I don't know either, okay, so as you will see, this talk is full of open problems, and this is one of them, okay. So any questions on that part? Yep. Very good question, okay, and so this, so here, this is a conduct function, so with respect to mu, in a sense, in the classical sense, there are no local minima, but in the Wasserstein sense, there are local minima, there are stationary points, okay, and this is well known, if you take mu being a set of direct measures, if you optimize the neural network, it gets stuck, okay, so it is known that there are local minima, okay, and there are recent formal pros by O.H. Shemmier and colleagues, so there are local minima, and what makes it work is a similar argument and the paramethod for eigenvectors, so this includes the paramethod, not obvious, but this includes the paramethod, and so you get, so the idea that, so the proof, so I'm not going to do the proof, it's going to take me like the full day, is the fact that what we show is that if you convert to a stationary point, since we assume M is infinity and we have a density when we start, because we have this random initialization, then you can show that you cannot convert to a non-local, you still have mass everywhere that will forbid you to escape stationary points, like for the paramethod, if you look at a random sample, okay, it's always converging, okay, if you're really unlucky, you initialize away, like orthogonal to the leading eigenvector, and it's a similar thing, at every step, there is mass everywhere, so you cannot get stuck, so it's very informal, but it's quite happening. Is it something like negative curvature or? I don't know what negative curvature is, so it may. No, no, no, I know it's really, it's really the fact that, okay, in a sense, so I'm going to use the argument of Yann Leucan, okay, so if you add more and more neurons, okay, you can find a new passage, okay, to avoid like the local minima. Also, you're not going to show us a baby. Why a baby? That's the Yann Leucan argument. Oh, no, no baby, okay. I have videos, but no babies. Why is it, no, okay, so let me now move on to the second part, which is implicit bias, okay, because what this is saying, this is saying that, okay, so if you're overparameterized, now you can start to optimize, okay, now you can think of, okay, where does it converge to? Okay, I say to a minimizer of my, of my, of f of mu, f of mu is my risk, and if I have my unparameter risk, okay, I have eight data points, infinitely many parameters. Now, a lot of minimizers, okay, so where am I converging to? And this is the goal of the last, how much time do I have left? 20 minutes? What? 10 minutes. 10 minutes, okay, so I'll, a bit more, no, no, I said at 15. So I have 20 minutes. Why do you ask? Yeah, yeah, I don't know, I like to be polite, but, yes, okay, so here, we're going to follow, so we've tried with the square loss, a lot, also, so this is like three years with an A, it's three years of enjoyment, and sometimes pain of not trying to find good results, and we spent a lot of time trying to do this for square loss, okay, for the square loss, and you could imagine the gradient is linear function, it could be easier, and we couldn't do it, and then we saw the talk of, so very nice work by Sudri, Guna Sekar, and Srebro from 2018, and probably other authors, but I forgot, and what they do is very, very nice, they consider, so the so-called interpolation regime, where you can fit the data perfectly, but in the classification setup, okay, and they consider minimizing, okay, for linear function, this could be, okay, logistic regression, okay, so this is logistic regression, and if you do it with separable data, okay, so this is like your data like that in the plane, and then it's well known that if you're separable, this minimum is not attained, okay, why, because if you take any directions like that, okay, and you set the node of W to infinity, then this will, all the losses will convert to zero, okay, so at the end, the minimum is not attained, okay, so if you load, you got the descent, it will diverge, okay, so this is well known, but what they showed is that it does diverge in a good direction, okay, so you consider W bar being W over W2, okay, so you see the direction, okay, and what they showed is that it converges to the max margin, max margin classifier, okay, so for those who studied research like before in 2005, and I think it's maybe only like Alex and me, oh, okay, okay, good, is, so you take, if you minimize W2, such that YI, this is bigger than one, okay, so you try to find, there are many planes, okay, which are separable data, okay, but among those, you want to find the one for which, okay, this is a plot from the 2000, okay, you want to maximize this distance, okay, and this is called the margin, the inverse margin, okay, and you maximize this, so you're going to select not this one because it's going to be like, that direction would be, would be too close, those two points would be too close, but one which is like maximizing the margin, and this was like really what NIPPS was about like 20 years ago, okay, and so what they showed is that, okay, so when you diverge, you're going to have a good direction, okay, so what is nice is because it does relate some gradient descent towards an explicit minimum norm solution, okay, so often people say, when I do gradient descent, it's like implicitly doing like minimum regularization, it's always like hand waving, and this is formal, okay, so you see there's a proof for that statement, if I launch gradient descent or gradient flow, on that problem, it will diverge, but the direction will converge to this one, okay, all right, so now let's try to apply this to our setup, okay, so now we're going to consider, let me erase this, I'm going to consider, oops, sorry, that's okay, it's not the first time I say that word, so, and not the last time I ever know, okay, so again to consider, so minimizing, so R of F, okay, would be 1 over N sum from J equals 1 to N of log of 1 exponential minus YJ F of XJ, okay, and for which F, of course, for F I erase the important aspect, for F, for F of X being, study a collection, okay, sum over I of A i B i transpose X plus, okay, so now this is the goal, the goal for now is to look at the effect of doing gradient descent on the empirical logistic risk, okay, and with a space of function which is my now two-layer neural networks, okay, so, and now we're going to have similar things in here that it will diverge, but the F, the function will converge to something special, okay, and now the goal is to understand the various regimes, so it will be three regimes, okay, I will probably only have time to talk about two, okay, so let's take, so the first regime will be the kernel regime and the, we call variation norm regime, and this will depend on what I optimize over, okay, so in the kernel regime, I will only optimize with respect to A, okay, so why is it so nice to have only A, because first I've removed the difficulty of B, okay, so it's not going to be with respect to B, so I just assume B is fixed, so I sample B randomly from the sphere as garter, and optimize over A, so this is convex, okay, so first good news, second good news, so now when M is fixed, when M is fixed, this is just a linear function, so I can apply the result of the Chicago researchers saying that I'm going to converge to the F which has that form with the minimum A to norm for A, okay, and now I'm back to also familiar land from the year 2007, this is so-called random features, okay, so this is the so-called random features, why, because I'm sampling the BI uniformly, okay, and here I assume they are fixed, okay, they don't move anymore, they are sampled randomly, and then I do minimum A to norm optimization on A, so it's like I'm penalizing by the A to norm, and if you know your class from Jean-Philippe and Julia Méral, then you know that, then you can represent your F as a weighted sub of kernel functions, and the kernel function will be here, k of xs prime, one over M, so the dot product for the features, so here in this setup, my features are all the BI transpose x plus, okay, I have M of them, so I take the dot product, BI transpose x plus BI transpose x prime plus, all right, and what kernel features are saying, and this is word by Raimian Rect 2007 and Rad-Fornil in 95, they say this converges when M goes to infinity to the expectation of a B of B transpose x plus and B transpose x prime plus, okay, so this is standard like a kernel method from the 2007, all right, and so what is he saying is that if you're only optima about the last layer, you're doing a kernel method, okay, so this is but a good part, so many good parts, let's not forget the good parts, so the good part is that you can quantify how big M needs to be, okay, you can quantify the rate at which this will converge to the good direction, so we think it's more quantitative, the bad part is that the features are fixed, okay, this is not what people are doing in practice, in particular when M goes to infinity, this space of functions is a space of very smooth functions, okay, so I will show examples in the video, in particular if you have a single neuron, a single neuron does not belong to that space, okay, so essentially it's not adapted to a finite number of neurons, okay, so this is the first aspect is that, the first aspect is that kernel regime, you can apply the other regime if you're only optima about the last layer, any questions on this one? Yeah, yeah. How is it related to the theorem you've shown? So here, the relation of the first one? Yeah, so this result is it related to the theorem? No, okay, so the theorem that I'm saying is that, say that if you do, no, it's almost unrelated, because you can apply it, but it's a hammer to squash a fly. So the consequence of the theorem? It's almost a consequence in the sense that, so you apply that result, so you're going to convert it to minimum, and to some solutions for the AIs, okay, and we know that when M is big, doing many AIs like that, we convert the kernel solution, it's not like a formal, it's like a, but more or less totally the consequence of it. All right, so now let's do the, let's do optima thing about the two. This is the core novelty of the work. And then I show the video. All right, show the video. All right, so let's start with a very erratic argument, okay? So if you take ai bi transpose x plus, okay, so you can write this as, you can put the norm of bi outside of the plus by originating, so this is ai bi1 times bi over its norm, transpose x plus, okay, you agree with this? All right, and now if you optima the AI bi, so if you flow the recipe that AGD tends to do the minimum L2 norm solution, you get the L2 norm solution of the L2 norm of the AI bi's, okay? And the L2 norm of the AI bi's, this is ai squared plus bi bi squared, okay? You agree with this? Ai is a number, okay? And this is bigger than ai bi2 squared. No, there's no square. Times two, okay? So in a very erratic way, okay, if you do AGD on the two, you're going to minimize the L2 norm of AI bi, which if you're willing to follow me, you're going to minimize the sum of those, okay? So the L1 norm of those weights, okay? No, because, okay, so the squared L2 norm, if this, okay, and essentially this is bigger than this, you agree with this? Oh, yeah, yeah, yeah, yeah, yeah, sorry. I was like one step ahead, okay? So at the end, if you penalize the sum of the squared L2 norm of the AI bi's, which is suggested by the result by Sudri Gounesset-Karats-Rebro, then it's in a highly-waiving way equivalent to minimizing the sum of those and you get an L1 norm, okay? So it's essentially what we prove. So let me set the theorem. So this is with Venaik in 2020. So let me make it... So what we show is that F converges to... Okay, so we flagged before. So when the number of neurons go to infinity, then I'm going to converge to a gradon flow. And the gradon flow, if it converges to somewhere, it will converge to some solution, which will be the minimum. So L1 norm solution. And this is defined as the int of the integral. So it's going to be... I want to be just formal for once. Like that. So let me write it and then... Okay, so here this sigma is a uniform measure on the sphere. Okay, do you consider writing functions, okay, which are a combination of like those like Rolux functions, plus some weights, A, and you take a measure on those weights. Okay, so it's a special function. And you're going to penalize the output weights, A, by the L1 norm, which is a... Okay, so this is a formal... The formal results and this way cover things that we had, that I had done like three years ago. And this is called a violation norm, okay, and there's very nice paper by... I forgot the name. Corkova and Sanginetti, okay. And so what is nice is that because you have this L1 norm, you have this adaptivity effect that we often see with L1 norm, you can have Dirac's, those are allowed. So the first good thing, you can show that this is like... This can scale well to high dimensions. So as soon as you have some linear structure for your problem, this is going to find it because of the L1 norm. And finally, what is interesting here is that this is a context problem still. Okay, so it's a context problem for which we don't know any like classical algorithms to solve it, but if you use the Kennedy's set on particles, this is working. Okay. And so for the expert in the room, if you look carefully, this is giving you the end of the double descent curve. Okay, so you can meditate this and you can talk at the break. And now I want to show you the rules. All right, so this is like a problem today. So this is essentially this problem, a function which is like that when n equals 5. Okay, so I generate data from that function. Okay, and the goal is to recover the AI in the eyes because I'm homogeneous. I'm going to put AI inside. Okay, and the goal is to learn the five directions, which are the generating neurons. And I'm going to look when M is pretty large. I'm going to sample many neurons. Okay, so what we showed is an egg that when M is infinite, then you should converge to the global optimum and you see what it does for 100 neurons. It does something nice. Up. As you can see, the dynamics is a bit weird. Okay, it does oscillate in many ways and put it again. Okay. All right. So here, what is open for this is we only qualitative. Okay, when M is big, it's fine. But when we take M being five, it does not work. It gets stuck. Okay, you launch with five neurons. You know you can converge to the global optimum, but you never reach it. But as soon as you take M being like 10 or 20, it does work. Okay, and we don't know why. So first open problem. What? If you start really, really close to the true value. Sure, but that's... No, no, just... Of course, if you start at the optimum, it's greater than this end, you converge to the optimum. No, no, so it's... And then, down here. Sorry. Up, and then, so now I'm going to show like the final plot, where here this is strange, the output layer. On the right, the two layers. Okay, so you have plus on the left, plus and minus everywhere. And what I showed you that on the left, this was like L2 norm tab regularization. So it does converge to some kernel method. So it should be like some smooth function. Whereas on the right, it should converge to some L1 norm solution, where because of L1 norm, you're going to set only a small number of neurons, so it should be spiky. Okay, so let's look at... Okay. Ah, c'est joli, indeed. And, yeah, so first, Clarice, not me, we made those nice videos, it's Lenarik. So here you see on the right, the convergence, it's plotting as a classification of regions. So this is very, this is based on the 12 or 13 neurons. Okay, so it's very, very like this was Lenarik. Whereas for the kernel method, you get like a very smooth function. Okay, so just to highlight, to highlight the thing, and we'll put it again. Okay, and... Okay, so I'm almost done. So I've mentioned like several open problems. So the most important one, we have tried, we have tried, and any help is welcome, is to make this quantitative. Okay, so we can do it for the kernel methods. So this is like work from five years ago. But as soon as you go, something like that, you can see that it does behave quite well. You don't need to start with infinitely many neurons, so we don't know how to do it. Okay, we try to simplify the problem a lot, and it's still like not done yet, going convolutional. We don't know how to do. So we want to go beyond, and finally, we'll have to go deep. Okay, trying to go beyond one in a layer, but at the moment it's very hard. Thank you for your attention.
 Thank you.  And I would like to first thank the organizers for the event, very nice and sunny, and for  inviting me. So today we need to speak about a lot of benchmarking, as you will see.  And this is joint work with Enig Shiza. And when I say joint, this is more like me running after Enig.  And so the topic of today is to look at gradient descent for, so, wide two-layer neural networks.  So here I drew a very wide network. Okay, so we have the input, it will be X in RD.  Okay, here we have M hidden neurons and a single output, which I recall Y.  And so I'm going to restrict myself to a particular activation function.  And I'm going to consider predation functions of the form f of X is one of M sum of I equals M  from one to M of AI, Bi transpose X plus. So I'm considering the so-called relu activation function.  So plus is just a positive part, the max of the argument and zero.  So why is it interesting? So this is really a small proxy for deep learning.  Okay, so it's a huge simplification, a single hidden layer.  Okay, it's not really deep. No convolution, no pulling, no weird things.  So good old, like fully connected neural network. And I'm going to focus a lot on this activation function.  So why is it hard for us? Okay, so this is, the function is linear in A.  So this would be the easy part, but it is non-linear in B. And this will create problems for optimization.  And the other hard part will be that those are wide networks.  So M, the number of hidden neurons will tend to infinity.  Okay, so this is open code, the other parameterized regime.  So here we're not trying to compare the number of observations or the number of parameters.  We take M to infinity. And as we see, a big caveat in our analysis is the lack of quantitative analysis.  So M is very big, and I will not tell you how big it needs to be.  All right, so this is the setup. So why are we considering this?  We're going to leverage two properties. One is what I call separability.  So essentially your prediction function, F, is a sum of terms, okay,  and the parameters for each of the terms are unique to those terms.  It's a separable parameterization. And often I will use the notation F is 1 over M sum from i equals 1 to M of some phi of wi.  Okay, just to highlight the fact that the sum of functions, okay, and so here, F is a function.  So phi of wi is a function. So for example, so here, this corresponds to phi of wi at x is a of bx plus.  Okay, so wi is the two-pole AB. And it's just to highlight that, okay, we have a separable function.  Okay, and for the first part of the talk, I'm going to focus mostly on that setup.  Okay, so just using separability. And if you look carefully, this works well for the one hidden layer.  But if I add more layers, this will not be true anymore. Okay, the sharing of parameters, it's not true that beyond a single hidden layer,  you're going to have some separability. So from the start, all the things I'm going to say cannot apply directly to more than one hidden layer.  This is the first big assumption. And the second would be, so 2 homogeneity.  Homogeneity. So what I mean by that is phi of lambda w is lambda square phi of w.  Okay, so this is true for the ROLU. And this is why we consider the ROLU in this work. It's because the ROLU is homogeneous in A,  homogeneous in B. And if you take the pair AB, it's two homogenous. Okay, so this is why we consider the ROLU.  Before I move on, if you want to interact with me, please do so. Okay, you can get back at me. You have 35 minutes to do so.  Okay. All right, so this is a setup. So we're going to consider a classical learning setup where we have some data.  So it's xi, yi, nothing particular from i equals 1 to n and coming from qx, y.  Okay, we have a loss. So this is not really particular. So you have a loss, L of y, f of x.  And here we're going to assume the loss is convex with respect to the second variable.  Okay, so it's convex with respect to the second one. And this can be logistic, this can be square loss.  And I consider this as being a weak assumption even in the deepest of the deepest networks.  They use what they call the cross-entropy loss, which happens to be convex.  Okay, so I'm going to assume convexity in f. And I'm going to minimize the risk.  Okay, so it will be the risk of f, the function f, will be an expectation of the loss, y, f of x.  Okay, so here, depending on the setup, this will be the expectation with respect to the empirical distribution.  And the average of the data, xi, yi, from i equals 1 to n, n, or this can be the expected loss.  Okay, at the end, this is simply the risk. So it's convex in f because I assume L is convex.  Okay, so this is a very, very standard setup.  All right, so now I'm going to look at some properties. And I think the key here is that one big message of the talk,  and this is true for several other talks, is that we cannot simply...  So here, I've not talked about estimation algorithms. I just have some model, okay, I have a model which is at the top.  I have some criteria which is there. And typically, it's enough, okay.  Statisticians will tell you how to analyze this. And optimizers will tell you how to optimize it.  Okay, so here, the key message that you cannot do this separately, very similarly to HGD.  Okay, here you have to analyze some algorithm which is key to the analysis.  And this will be, as the title says, gradient descent.  Okay, so I'm going to study gradient descent techniques when I want to minimize the risk.  And I have the parameters of F which are of that form.  Okay, so in F, it's convex, but in W, it's not convex.  Okay, why? Because Phi is not a linear function.  All right, so this is a standard setup.  Okay, so I'm going to do two things. Okay, so two parts from my talk.  One is global convergence.  The other is the idea that although we are non-convex, okay, in W,  then if you let M go to infinity, and of course, there will be a lot of technical assumptions,  we need to sweep under the carpet, okay.  Then you do get some global convergence. This will be the first part of the talk.  And then second, I will talk about what people call the implicit bias.  The idea being that since I'm going to optimize with M big infinite,  my space of function is huge. So typically, in particular when I minimize the un-picker risk,  I have lots of minimizers. And among those minimizers, my algorithm will select one.  And I want to study the one which is selected.  Okay, and I will show like three different implicit biases, okay,  and three different behaviors. And if you are nice, I will show you videos at the end.  And so this is joint work with Lenaik and myself from 2018.  And this is a mixture of something from this year and something with Edward Royalon, CBO, from last year.  Okay, so if you want to know more, the papers are online.  All right, so let's look first at the first element. And now I can use a reason why I give a talk  on the blackboard is to play with the boards, okay.  All right, so global convergence now.  Okay, so the idea is to minimize, we're going to consider g of w.  So it's a big w. So you have M weight vectors wm.  Okay, if you go by the top board, okay, those are my weights.  And this is simply the risk of 1 over M sum from i equals m of w.  All right, so this is what I want to minimize.  And the main gist of having M go to infinity is to write this as you're going to replace this empirical average  by the integral of our measure, okay, and then you're going to optimize over measures.  The weight is being done. And that you write it as you consider f of mu  with the risk of the integral of phi of w d mu of w.  And we're going to assume that mu here is a probability measure.  Okay, so this is the way we're going to formalize it.  So we have some probability measure.  And if you take mu being the sum of the racks,  you have that f of mu is g of w.  Okay, so this is the main two we're going to consider.  And these two are not ours, okay?  So there's a long list of people looking at this.  And I think this starts back with, I think, Baron, which you're Baron.  Baron 83.  So there is Andrew Baron in 83.  There is Benjo, Le Roux, et al. 2005.  And I've worked on it quite a bit while two years ago.  Okay, so this is a very classical idea.  And why is it so nice is that I've made my problem convex.  Why? Because as a function of mu,  so the space of probability measure is a convex set, okay?  This is a linear function in mu.  R is convex, so I have a convex problem.  Okay, so this is, I've made my problem convex,  but the downside is the fact that another space of probability measures on Rd  is infinite dimensional, and it's going to be hard to optimize.  Okay, so because it's convex, so what I tried first and failed miserably  is to use convex techniques.  Okay, so there's not too many talks about Frank Wolf,  because it's not about one talk by Frank Wolf by Yifan.  Then I have a big convex set, which is a convex set of many things,  so I can optimize using Frank Wolf.  And in Frank Wolf, you build your estimator incrementally,  okay, as a weighted sum of elements,  and every time you have to add a new element, okay?  It's often called a Frank Wolf step.  The problem, okay, the good thing is that if you can do the Frank Wolf step,  you get a nice convergence rate as 1 over k when k is the number of iterations.  But the downside is that to select a new neuron, you have to solve some problem  called the Frank Wolf step, and this problem happens to be NP-hard.  Okay, so you're replacing this hard problem, okay, which is not convex.  You try to replace it by a convex problem,  but every iteration requires to solve NP-hard problem,  so it's not really useful,  and if you want to know more about all the missed trials,  there is like a few pages on that in this paper.  And second, it's not that people are doing practice.  It's tracked, but if you whiten the data.  It is tracked, but if you whiten the data, what do you mean?  There's a paper by Mark.  No, yeah, I read the paper, and...  We just got caught up.  I read the paper, and tracked, but I think there's some powers involved.  No, I think it's a mental issue.  Okay, but...  I had this from my reading of the paper in the airware.  It doesn't mean like...  It was not solving, but it's not the topic of today.  The NP-hard problem is computing a brain, so...  As an NPI, you want to do the Frank Wolf step.  You have a gradient, you want to find a neuron which maximizes the problem with a gradient.  It's linear classification, which is NPR.  So if you assume some reduced...  Anyway, it's not the topic of the talk, but...  And...  Yeah, so anyway, it's not people doing practice.  In practice, people do just gradient descent.  Okay, on this, okay, so this is gradient descent on the weights AB.  So it's backprop, and we're going to study this.  All right, so let's study backprop.  So we're going to not use gradient descent.  We're going to make our life simpler by using the gradient flow.  What is the gradient flow?  So if you do gradient descent, so...  If you do hiking, so this is lumini, this is a canok, okay?  So if you do gradient step, you do some things like that.  So this is gradient descent.  And gradient flow is like the limit with infinitely small step size,  so it's more something like this.  And this corresponds to the ODE, W dot, is minus M gradient of G of W.  So the M is to make things easy when I'm going to take the limit when M goes to infinity.  So this is what I'm going to minimize.  So here, clearly, we go away from what people are doing practice,  but it's the only thing we can do at the moment.  And now I can hand wave my way through justifying why it's not too bad.  So first, as I've mentioned, this is when your step size gets small,  you get close to the gradient flow.  And this is true both for the deterministic gradient and also for stochastic gradient.  Okay, if you do HDD with a single pass,  so you can see that the approximation of the gradient flow.  So we need to study this one.  Okay, so now the goal is to show global convergence of the gradient flow.  What I mean by that is, I have option F, D final measures,  and the goal is if I load the gradient flow on that function and M is big enough,  I want to get to the minimizer of F.  Okay, so this is what we are going to show.  We're going to need two assumptions.  So I don't want to talk about the technical ones,  but the ones which are important.  So the first one is, so two, homogeneity.  Okay, so this is not necessary, but sufficient.  And you can think of removing these constraints,  and you get to, you can optimize anything.  Okay, so this is unlikely to be true.  And you're going to be going to need as well.  So random initialization.  Okay, so here I'm going to require that I sample all directions.  I have put positive mass on all directions.  Yep.  I just, how do you define phi of W?  Phi of W, this is W.  So this is at the top.  Okay, this is for neural networks, it's a function,  and W is AB.  And so we need to assume that you cover all the sphere of directions.  Okay, so the problem is too homogeneous.  So what you care about is directions.  You need to sample weights.  Uniform is simpler, it's simple,  but you need positive mass everywhere.  So one simple way is that W gargantuan, okay, that would be easy.  And this corresponds to what people do in practice.  Okay, they take A and B gargantuan, okay.  So we're going to assume this, and then what we have,  we have a theorem, and I put quotes because I'm missing a lot  of the technical assumptions.  Okay, then what we have is that when M goes to infinity,  okay, so the trajectory, so the flow,  goes to what is called a Vassarstein gradient flow.  Okay, so the first part of the statement,  so I will not define what the Vassarstein gradient flow is,  it's just to highlight the fact that when you get M  go to infinity, this does correspond to something  which is well defined mathematically,  and which you can analyze.  Okay, so this is really just to make sure that what you  cover is a PDE, and if you want to know more,  you can look at the paper, or we can talk after the break.  So this first thing, it does have a meaning,  it has T, and if it has a limit, mu infinity,  then mu infinity is an armin of F.  Okay, so this is just a statement which I more or less  expressed that as we get more and more particles,  we often call the W's particles,  you end up converging to the correct measure,  so in a weak sense, okay, it has to be a weak sense  because we have a bunch of Dirac's,  and we may get to a density at the end.  And so this has like a lot of limitations,  so let me write them down immediately.  So first, some other papers that do similar things,  so there is Nintendo and Suzuki,  who are already showing the first aspect,  and there is a Me and Montanari,  Monta, you know Montanari, okay,  who are doing also similar things,  okay, so it's a bit different,  but so Nintendo, they prove, they prove  convergence to a vassal gradient flow,  and Me and Montanari, they prove convergence  if you add some noise, okay,  so it's a bit different, but it's interesting.  Yeah?  The two homogenities for phi or for G?  For phi, so phi.  For the four phi.  For phi, yeah.  So here, so if you take my setup over there,  the loss is any convex loss, it is just for phi.  So this applies to, but there are other situations,  so this applies to spike decommolution,  this applies to matrices,  so this is like more general than neural networks.  So there are big caveats,  that this is this, if it has a limit, okay,  so we've tried for several months to show that,  to give summation conditions for the gradient flow  to have a limit, and in the Euclidean case,  this is known to be possible with like  the Euclidean conditions,  but for Wasserstein, we are not able to do it,  so we simply assume that it does have a limit, okay,  this is the first issue,  and second issue is that this is very qualitative statement.  It's just when m goes to infinity,  and when t goes to infinity, okay,  I will not tell you how big m needs to be,  so how many neurons do I need, I don't know,  and how big, and how fast am I converging,  I don't know either, okay,  so as you will see, this talk is full of open problems,  and this is one of them, okay.  So any questions on that part?  Yep.  Very good question, okay,  and so this, so here, this is a conduct function,  so with respect to mu, in a sense,  in the classical sense, there are no local minima,  but in the Wasserstein sense, there are local minima,  there are stationary points, okay,  and this is well known, if you take mu being a set of direct measures,  if you optimize the neural network, it gets stuck, okay,  so it is known that there are local minima, okay,  and there are recent formal pros by O.H. Shemmier and colleagues,  so there are local minima,  and what makes it work is a similar argument  and the paramethod for eigenvectors,  so this includes the paramethod, not obvious,  but this includes the paramethod, and so you get,  so the idea that, so the proof, so I'm not going to do the proof,  it's going to take me like the full day,  is the fact that what we show is that if you convert to a stationary point,  since we assume M is infinity and we have a density when we start,  because we have this random initialization,  then you can show that you cannot convert to a non-local,  you still have mass everywhere that will forbid you  to escape stationary points, like for the paramethod,  if you look at a random sample, okay, it's always converging,  okay, if you're really unlucky, you initialize away,  like orthogonal to the leading eigenvector,  and it's a similar thing, at every step,  there is mass everywhere, so you cannot get stuck,  so it's very informal, but it's quite happening.  Is it something like negative curvature or?  I don't know what negative curvature is, so it may.  No, no, no, I know it's really, it's really the fact that,  okay, in a sense, so I'm going to use the argument of Yann Leucan,  okay, so if you add more and more neurons, okay,  you can find a new passage, okay, to avoid like the local minima.  Also, you're not going to show us a baby.  Why a baby?  That's the Yann Leucan argument.  Oh, no, no baby, okay.  I have videos, but no babies.  Why is it, no, okay, so let me now move on to the second part,  which is implicit bias, okay, because what this is saying,  this is saying that, okay, so if you're overparameterized,  now you can start to optimize, okay, now you can think of,  okay, where does it converge to?  Okay, I say to a minimizer of my, of my, of f of mu,  f of mu is my risk, and if I have my unparameter risk,  okay, I have eight data points, infinitely many parameters.  Now, a lot of minimizers, okay, so where am I converging to?  And this is the goal of the last, how much time do I have left?  20 minutes?  What?  10 minutes.  10 minutes, okay, so I'll, a bit more, no, no, I said at 15.  So I have 20 minutes.  Why do you ask?  Yeah, yeah, I don't know, I like to be polite, but,  yes, okay, so here, we're going to follow,  so we've tried with the square loss, a lot, also,  so this is like three years with an A,  it's three years of enjoyment,  and sometimes pain of not trying to find good results,  and we spent a lot of time trying to do this for square loss,  okay, for the square loss,  and you could imagine the gradient is linear function,  it could be easier, and we couldn't do it,  and then we saw the talk of, so very nice work by Sudri,  Guna Sekar, and Srebro from 2018,  and probably other authors, but I forgot,  and what they do is very, very nice,  they consider, so the so-called interpolation regime,  where you can fit the data perfectly,  but in the classification setup, okay,  and they consider minimizing, okay,  for linear function, this could be, okay,  logistic regression, okay,  so this is logistic regression,  and if you do it with separable data, okay,  so this is like your data like that in the plane,  and then it's well known that if you're separable,  this minimum is not attained, okay,  why, because if you take any directions like that, okay,  and you set the node of W to infinity,  then this will, all the losses will convert to zero, okay,  so at the end, the minimum is not attained, okay,  so if you load, you got the descent, it will diverge,  okay, so this is well known, but what they showed  is that it does diverge in a good direction, okay,  so you consider W bar being W over W2, okay,  so you see the direction, okay,  and what they showed is that it converges  to the max margin, max margin classifier, okay,  so for those who studied research like before in 2005,  and I think it's maybe only like Alex and me,  oh, okay, okay, good, is, so you take,  if you minimize W2, such that YI, this is bigger than one,  okay, so you try to find, there are many planes, okay,  which are separable data, okay,  but among those, you want to find the one for which,  okay, this is a plot from the 2000, okay,  you want to maximize this distance, okay,  and this is called the margin, the inverse margin, okay,  and you maximize this, so you're going to select not this one  because it's going to be like, that direction would be,  would be too close, those two points would be too close,  but one which is like maximizing the margin,  and this was like really what NIPPS was about like 20 years ago,  okay, and so what they showed is that, okay,  so when you diverge, you're going to have a good direction,  okay, so what is nice is because it does relate  some gradient descent towards an explicit minimum norm solution,  okay, so often people say, when I do gradient descent,  it's like implicitly doing like minimum  regularization, it's always like hand waving,  and this is formal, okay, so you see there's a proof  for that statement, if I launch gradient descent  or gradient flow, on that problem, it will diverge,  but the direction will converge to this one, okay,  all right, so now let's try to apply this to our setup,  okay, so now we're going to consider,  let me erase this, I'm going to consider,  oops, sorry, that's okay, it's not the first time  I say that word, so, and not the last time I ever know,  okay, so again to consider, so minimizing,  so R of F, okay, would be 1 over N sum from J  equals 1 to N of log of 1 exponential minus YJ  F of XJ, okay, and for which F, of course,  for F I erase the important aspect,  for F, for F of X being,  study a collection, okay, sum over I of A i B i  transpose X plus, okay, so now this is the goal,  the goal for now is to look at the effect of doing  gradient descent on the empirical logistic risk,  okay, and with a space of function which is  my now two-layer neural networks, okay,  so, and now we're going to have similar things  in here that it will diverge, but the F,  the function will converge to something special,  okay, and now the goal is to understand the various  regimes, so it will be three regimes, okay,  I will probably only have time to talk about two, okay,  so let's take, so the first regime will be the kernel regime  and the, we call variation norm regime,  and this will depend on what I optimize over, okay,  so in the kernel regime, I will only optimize  with respect to A, okay, so why is it so nice to have  only A, because first I've removed the difficulty of B,  okay, so it's not going to be with respect to B,  so I just assume B is fixed, so I sample B  randomly from the sphere as garter,  and optimize over A, so this is convex, okay,  so first good news, second good news,  so now when M is fixed, when M is fixed,  this is just a linear function, so I can apply the result  of the Chicago researchers saying that I'm going to converge  to the F which has that form with the minimum A to norm  for A, okay, and now I'm back to also familiar land  from the year 2007, this is so-called random features,  okay, so this is the so-called random features,  why, because I'm sampling the BI uniformly, okay,  and here I assume they are fixed, okay,  they don't move anymore, they are sampled randomly,  and then I do minimum A to norm optimization on A,  so it's like I'm penalizing by the A to norm,  and if you know your class from Jean-Philippe and Julia Méral,  then you know that, then you can represent your F  as a weighted sub of kernel functions,  and the kernel function will be here,  k of xs prime, one over M, so the dot product  for the features, so here in this setup,  my features are all the BI transpose x plus,  okay, I have M of them, so I take the dot product,  BI transpose x plus BI transpose x prime plus,  all right, and what kernel features are saying,  and this is word by Raimian Rect 2007  and Rad-Fornil in 95, they say this converges  when M goes to infinity to the expectation  of a B of B transpose x plus and B transpose x prime plus,  okay, so this is standard like a kernel method  from the 2007, all right,  and so what is he saying is that if you're only  optima about the last layer, you're doing a kernel method,  okay, so this is but a good part, so many good parts,  let's not forget the good parts,  so the good part is that you can quantify  how big M needs to be, okay,  you can quantify the rate at which this will converge  to the good direction, so we think it's more quantitative,  the bad part is that the features are fixed, okay,  this is not what people are doing in practice,  in particular when M goes to infinity,  this space of functions is a space of very smooth functions,  okay, so I will show examples in the video,  in particular if you have a single neuron,  a single neuron does not belong to that space, okay,  so essentially it's not adapted to a finite number of neurons,  okay, so this is the first aspect is that,  the first aspect is that kernel regime,  you can apply the other regime if you're only optima about  the last layer, any questions on this one?  Yeah, yeah.  How is it related to the theorem you've shown?  So here, the relation of the first one?  Yeah, so this result is it related to the theorem?  No, okay, so the theorem that I'm saying is that,  say that if you do, no, it's almost unrelated,  because you can apply it,  but it's a hammer to squash a fly.  So the consequence of the theorem?  It's almost a consequence in the sense that,  so you apply that result,  so you're going to convert it to minimum,  and to some solutions for the AIs, okay,  and we know that when M is big,  doing many AIs like that,  we convert the kernel solution,  it's not like a formal, it's like a,  but more or less totally the consequence of it.  All right, so now let's do the,  let's do optima thing about the two.  This is the core novelty of the work.  And then I show the video.  All right, show the video.  All right, so let's start with a very erratic argument, okay?  So if you take ai bi transpose x plus, okay,  so you can write this as,  you can put the norm of bi outside of the plus by originating,  so this is ai bi1 times bi over its norm,  transpose x plus, okay, you agree with this?  All right, and now if you optima the AI bi,  so if you flow the recipe that AGD tends to do  the minimum L2 norm solution,  you get the L2 norm solution of the L2 norm of the AI bi's, okay?  And the L2 norm of the AI bi's,  this is ai squared plus bi bi squared, okay?  You agree with this?  Ai is a number, okay?  And this is bigger than ai bi2 squared.  No, there's no square.  Times two, okay?  So in a very erratic way, okay,  if you do AGD on the two,  you're going to minimize the L2 norm of AI bi,  which if you're willing to follow me,  you're going to minimize the sum of those, okay?  So the L1 norm of those weights, okay?  No, because, okay, so the squared L2 norm,  if this, okay, and essentially this is bigger than this,  you agree with this?  Oh, yeah, yeah, yeah, yeah, yeah, sorry.  I was like one step ahead, okay?  So at the end, if you penalize the sum of the squared L2 norm  of the AI bi's, which is suggested by the result  by Sudri Gounesset-Karats-Rebro,  then it's in a highly-waiving way  equivalent to minimizing the sum of those  and you get an L1 norm, okay?  So it's essentially what we prove.  So let me set the theorem.  So this is with Venaik in 2020.  So let me make it...  So what we show is that F converges to...  Okay, so we flagged before.  So when the number of neurons go to infinity,  then I'm going to converge to a gradon flow.  And the gradon flow, if it converges to somewhere,  it will converge to some solution,  which will be the minimum.  So L1 norm solution.  And this is defined as the int of the integral.  So it's going to be...  I want to be just formal for once.  Like that.  So let me write it and then...  Okay, so here this sigma is a uniform measure on the sphere.  Okay, do you consider writing functions, okay,  which are a combination of like those like Rolux functions,  plus some weights, A, and you take a measure on those weights.  Okay, so it's a special function.  And you're going to penalize the output weights, A,  by the L1 norm, which is a...  Okay, so this is a formal...  The formal results and this way cover things that we had,  that I had done like three years ago.  And this is called a violation norm, okay,  and there's very nice paper by...  I forgot the name.  Corkova and Sanginetti, okay.  And so what is nice is that because you have this L1 norm,  you have this adaptivity effect that we often see with L1 norm,  you can have Dirac's, those are allowed.  So the first good thing,  you can show that this is like...  This can scale well to high dimensions.  So as soon as you have some linear structure for your problem,  this is going to find it because of the L1 norm.  And finally, what is interesting here is that this is a context problem still.  Okay, so it's a context problem for which we don't know  any like classical algorithms to solve it,  but if you use the Kennedy's set on particles, this is working.  Okay.  And so for the expert in the room,  if you look carefully, this is giving you the end of the double descent curve.  Okay, so you can meditate this and you can talk at the break.  And now I want to show you the rules.  All right, so this is like a problem today.  So this is essentially this problem,  a function which is like that when n equals 5.  Okay, so I generate data from that function.  Okay, and the goal is to recover the AI in the eyes  because I'm homogeneous.  I'm going to put AI inside.  Okay, and the goal is to learn the five directions,  which are the generating neurons.  And I'm going to look when M is pretty large.  I'm going to sample many neurons.  Okay, so what we showed is an egg that when M is infinite,  then you should converge to the global optimum  and you see what it does for 100 neurons.  It does something nice.  Up.  As you can see, the dynamics is a bit weird.  Okay, it does oscillate in many ways and put it again.  Okay.  All right.  So here, what is open for this is we only qualitative.  Okay, when M is big, it's fine.  But when we take M being five, it does not work.  It gets stuck.  Okay, you launch with five neurons.  You know you can converge to the global optimum,  but you never reach it.  But as soon as you take M being like 10 or 20, it does work.  Okay, and we don't know why.  So first open problem.  What?  If you start really, really close to the true value.  Sure, but that's...  No, no, just...  Of course, if you start at the optimum,  it's greater than this end, you converge to the optimum.  No, no, so it's...  And then, down here.  Sorry.  Up, and then, so now I'm going to show like the final plot,  where here this is strange, the output layer.  On the right, the two layers.  Okay, so you have plus on the left,  plus and minus everywhere.  And what I showed you that on the left,  this was like L2 norm tab regularization.  So it does converge to some kernel method.  So it should be like some smooth function.  Whereas on the right, it should converge to some L1 norm solution,  where because of L1 norm,  you're going to set only a small number of neurons,  so it should be spiky.  Okay, so let's look at...  Okay.  Ah, c'est joli, indeed.  And, yeah, so first, Clarice, not me,  we made those nice videos, it's Lenarik.  So here you see on the right, the convergence,  it's plotting as a classification of regions.  So this is very, this is based on the 12 or 13 neurons.  Okay, so it's very, very like this was Lenarik.  Whereas for the kernel method,  you get like a very smooth function.  Okay, so just to highlight, to highlight the thing,  and we'll put it again.  Okay, and...  Okay, so I'm almost done.  So I've mentioned like several open problems.  So the most important one,  we have tried, we have tried,  and any help is welcome, is to make this quantitative.  Okay, so we can do it for the kernel methods.  So this is like work from five years ago.  But as soon as you go, something like that,  you can see that it does behave quite well.  You don't need to start with infinitely many neurons,  so we don't know how to do it.  Okay, we try to simplify the problem a lot,  and it's still like not done yet, going convolutional.  We don't know how to do.  So we want to go beyond,  and finally, we'll have to go deep.  Okay, trying to go beyond one in a layer,  but at the moment it's very hard.  Thank you for your attention.
2020-03-12_Bach_II_0_155.png 2020-03-12_Bach_II_156_215.png 2020-03-12_Bach_II_216_467.png 2020-03-12_Bach_II_468_2915.png 2020-03-12_Bach_II_2916_3851.png 2020-03-12_Bach_II_3852_4619.png 2020-03-12_Bach_II_4620_7331.png 2020-03-12_Bach_II_7332_7427.png 2020-03-12_Bach_II_7428_7559.png 2020-03-12_Bach_II_7560_8759.png 2020-03-12_Bach_II_8760_9323.png 2020-03-12_Bach_II_9324_10343.png 2020-03-12_Bach_II_10344_10811.png 2020-03-12_Bach_II_10812_15047.png 2020-03-12_Bach_II_15048_16067.png 2020-03-12_Bach_II_16068_16415.png 2020-03-12_Bach_II_16416_17159.png 2020-03-12_Bach_II_17160_17603.png 2020-03-12_Bach_II_17604_18959.png 2020-03-12_Bach_II_18960_20003.png 2020-03-12_Bach_II_20004_23279.png 2020-03-12_Bach_II_23280_24275.png 2020-03-12_Bach_II_24276_26099.png 2020-03-12_Bach_II_26100_32783.png 2020-03-12_Bach_II_32784_33371.png 2020-03-12_Bach_II_33372_36071.png 2020-03-12_Bach_II_36072_40019.png 2020-03-12_Bach_II_40020_40775.png 2020-03-12_Bach_II_40776_41351.png 2020-03-12_Bach_II_41352_42503.png 2020-03-12_Bach_II_42504_43115.png 2020-03-12_Bach_II_43116_44591.png 2020-03-12_Bach_II_44592_47039.png 2020-03-12_Bach_II_47040_48251.png 2020-03-12_Bach_II_48252_49019.png 2020-03-12_Bach_II_49020_49547.png 2020-03-12_Bach_II_49548_49919.png 2020-03-12_Bach_II_49920_50459.png 2020-03-12_Bach_II_50460_50663.png 2020-03-12_Bach_II_50664_50843.png 2020-03-12_Bach_II_50844_52247.png 2020-03-12_Bach_II_52248_53111.png 2020-03-12_Bach_II_53112_57131.png 2020-03-12_Bach_II_57132_59051.png 2020-03-12_Bach_II_59052_59519.png 2020-03-12_Bach_II_59520_60263.png 2020-03-12_Bach_II_60264_60383.png 2020-03-12_Bach_II_60384_60467.png 2020-03-12_Bach_II_60468_60683.png 2020-03-12_Bach_II_60684_60983.png 2020-03-12_Bach_II_60984_61511.png 2020-03-12_Bach_II_61512_61571.png 2020-03-12_Bach_II_61572_63779.png 2020-03-12_Bach_II_63780_64355.png 2020-03-12_Bach_II_64356_68507.png 2020-03-12_Bach_II_68508_71039.png 2020-03-12_Bach_II_71040_71171.png 2020-03-12_Bach_II_71172_71284.png