Generalization properties of multiple passes stochastic gradient method
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Villa, Silvia
The stochastic gradient method has become an algorithm of choice in machine learning, because of its simplicity and small computational cost, especially when dealing with big data sets. Despite its widespread use, the generalization properties of the variants of stochastic gradient method used in practice are relatively little understood. Most previous works consider generalization properties of SGM with only one pass over the data, while in practice multiple passes are usually considered. The effect of multiple passes has been studied extensively for the optimization of an empirical objective, but the role for generalization is less clear. In this talk, we start filling this gap studying the generalization properties of multiple passes stochastic gradient method for least square regression in an abstract non parametric setting. We show that, if all other parameters are fixed a priori, the number of passes over the data indeed acts as a regularization parameter. The obtained bounds are sharp and matches those obtained with other regularized techniques such as ridge regression.
 So thank you for the introduction and the invitation. So we have learned during this workshop that large scale learning, to deal with large scale learning problems, statistical aspects and optimization aspects has to be treated jointly. One example of this is the stochastic gradient method that today is an algorithm of choice for these kind of problems. So our work started from the observation that there are several results studying generalization properties of one pass stochastic gradient descent, but in practice very often other heuristics are used such as multiple passes over the data and usually combined with early stopping. So what I'm going to present today are some theoretical results about these kind of heuristics and in particular the generalization properties of such kind of variants of SGD. I will call it randomly stochastic gradient method, stochastic gradient descent, so SGM, SGD. So I start from the problem setting. We consider linear regression in an abstract Hilbert space with the square loss. So the choice of the square loss is critical in our analysis, all that I'm going to say heavily depends on this choice. So probably I will forget to say this again during the talk, but so square loss plays a crucial role. So the objective in learning or in stochastic optimization is to minimize a functional E which can be written as an expectation. So in this case again the expectation of a square loss which depends in our setting linearly from W. And the problem here is the fact that the measure rho in general is unknown, but we only have some, we can only access to a finite number of points that are called examples. And so I have access only to these points that are independent and identical. So a randomly sampled from rho. So this setting naturally includes the linear regression with Gaussian noise in RD. So if I fix H to be RD, I can generate data for instance by randomly sample points Xi in RD and then by measuring some linear measurements corrupted by Gaussian noise, delta I. But also this framework includes for instance functional regression if my input points belong to an infinite dimensional space. For instance our curves or functions. Also this is a, let's say is an equivalent way to write the learning problem in reproducing kernel in birth spaces. So if you consider learning in an RKHS, then what you want to do is to minimize this again this risk where this time the function W that I want to find, so the element in HK is a function now depends non-linearly from the input variable. But as I think most of you know, if W is a function in the reproducing kernel in birth space generated by a kernel K, then we have the reproducing property therefore W evaluated at the point can be written as a scalar product between two elements in our birth space H. So Xi here is like X. Exactly, so Xi are the inputs that you will see in a moment why I don't call it X. And so the Xi can be seen as the input space R is the output space. And W is a function mapping the input into the output space. So what I can do is to consider a function that identifies the input point Xi with the kernel evaluated at this point Xi and send Y, leave Y unchanged. And then if I consider these change of variables inside these integral function, what I can write is that I use first the kernel trick. So W of Xi is the scalar product between W and K Xi and then I use the change of variable and then back to the model I'm presented at the beginning. So in this setting a classical approach is Ticonovergolarization. So what I want to do in the rest of my talk is to start from some very classical and basic results about Ticonovergolarization for learning problems. And then I will state some assumption and then state the main results and then I will compare them with the one that we get in for stochastic gradient descent. So what is the Ticonov estimator, the regularized empirical risk estimator? It is a point in my space age that can be built in this way. So I first replace the risk which is unknown by its empirical version and then I add to this risk a regularization function R that in this talk will be the square of the norm. Then what I do is that I minimize this regularized empirical risk and I build this estimator W hat which depends from a parameter which is the regularization parameter that balances the weight of the regularizer against the data fitting term. So the properties of this estimator has been studied a lot but mainly from a statistical point of view. So now I want to present to you some statistics, statistical properties of this estimator. In order to do that I need to introduce some assumptions. And so the first one is a fairly standard assumption basically requires that my measure rho is as a bounded support. So all my point axis, the norm of my point axis is bounded almost surely and the same holds for the output y. So the second one is this, okay, this assumption can be relaxed for what I'm going to say but I will consider this simpler setting. Another assumption that I do in this talk is the fact that the risk has a minimizer. And therefore, since it has at least a minimizer, the set of minimizers is non-empty and I can consider the minimal norm solution. This is a less standard assumption. It's a particular case in learning that is referred, I will call the attainable case. So where you have exactly one target parameter to estimate. So under these assumptions you can already prove some consistency results of the T-conve estimator but more assumptions are needed if we want to have more precise bounds, so known asymptotic bounds for the error. So the existence here is just because you're perhaps infinite, infinite dimension. If you're infinite dimension, if you're bounded in this case you will have always a solution. In infinite dimension or in finite dimensional, so yes, bounded sets are compact, therefore you have a convex continuous operator, the risk in this case it is, and therefore you have a minimizer. Because will you use the infinite dimensions anywhere else in the talk in the future? Can we always take each type you say about something that we're at a fine dimension and double use? Yes, you can. Yes, yes. Okay. As a convex, so you know something like the infinite dimension but you see that the number of W stars is very large. Yeah, it can be, yes. So large at infinite, that is finite, right? It is finite but you don't have maybe an estimation for instance. No, sorry, my comment was your dog. Sorry, my comment was if you don't assume that W is in the set, it's like having W star being very large in the finite dimensional set. Okay, you assume that W star is finite and the norm is reasonable. Okay. So some of the results, so I'm presenting the results in these settings, some of the results that I will present all even without these assumptions but in this talk I will assume that these all. So mainly because I want to introduce this source condition that is the technical condition that allows to get these error bounds. So first I define T which is the second moment operator. So it's an operator linear from H to H and this well defined bounded C thanks to the boundedness assumption that I just assume. Okay. What is this source condition? So it can be read as a regularity assumption of the solution I am assuming to exist and more precisely it asks that the solution, the minimal norm solution belongs to the range not only to the range of T but to the range of T at a certain power. Okay. So I will use this strange indexing just for easy to make easier the comparison with the existing result because this is the usual scaling that is used in the available papers. Okay. What does it mean? So with the picture we have the space H if R is equal to one-half I'm not asking anything since T to the zero is the identity therefore I'm just asking existence of the minimizer. If R is bigger than one-half then these spaces that are vector spaces subspaces of H are nested and as R increases my condition is stronger. Okay. So as R increases I'm requiring more regularity to my solution. Why do I call it regularity? Here is another interpretation. So the operator T is a compact operator from H to H, self-adjoint therefore I can diagonalize it and build a sequence of eigenvectors and eigenvalues. Okay. So my point W dagger belongs to H. This is a basis of H and so this quantity is finite. So this is equivalent to existence of W dagger. What does the source condition mean? It asks that since W dagger is in the run of T then H I can invert this operator and I can write H this way. Therefore H belongs to H to the capital H and here what I can do I can compute this quantity using these basis of H and I get this condition. So I get that since H is as a finite norm this sum here is finite. What does it mean? So remember that these eigenvalues are going to zero. We have a compact operator. So this inequality here asks that these coefficients, these Fourier coefficients go to zero sufficiently fast. Okay. So faster than usual. So this is the usual and this is the stronger assumption. Okay. Okay. So with this condition, so boundedness plus source condition, we can prove the following error bounds on the T-conoff regularized estimator. So the key point here is the choice of the regularization parameter. As you see I can prove that I have some bounds if I choose the regularization parameter as dependent on n in this way. So in a way that depends on this source condition. What I get here is that if r is smaller than 3 alps then I have this rate that increases as r increases but then at a certain point this rate doesn't increase anymore and it stops and is minus 1 alph. So if r is bigger than 3 alps, even if I'm requiring a stronger regularity on my solution, I will not be able to approximate it in a faster way. Okay. So just the idea of the proof is a bias variance tradeoff. So what I do here is I introduce an auxiliary point W lambda which is the minimizer of the risk through risk plus regularization. So I will not have access to this point but I don't need to compute it. I just use it as a reference point and then I can decompose the difference of the norm between my estimator and my true parameter W dagger as the sum of, I can bound this norm with the sum of these two terms. And as you can see here we have a term that depends on the sample and the term that depends only on the choice of lambda. So on the regularization properties of my approach. So balancing the two terms gives this, the behavior of this term is determined by the choice of the, by the source condition. We will have the result. So these results, the results that I showed are minimax. In this sense, so in the sense that if you fix a class of probability measures, and in this case the class of probability measures that I fix are the ones that satisfy the assumptions I just introduced, then okay I will have a different solution for each, in general a different solution for each probability measure. And I can, if I fix an algorithm I can compute the distance between the, the distance between my algorithm and my estimator and my true parameter. Then I can do a worst case analysis in the sense that I put in front of it a maximum. Therefore I take the problem on which my algorithm behaves worst. And then among all these, all the algorithms that I have at my disposal I take the best one. So I take, take the algorithm which has the best worst behavior. Okay, and as you can see here, I don't know if you remember the, the exponent in the bounds for the T-con of regularization. You get the, the exponent to this n is the same. Therefore the, yes. Oh, sorry, sir. Is there a reason why you're choosing to do this in that Hilbert norm rather than the two norm? Okay, yes. So the reason is the following. The results that I'm going to, that we obtained for multiple passes SGD are optimal minimax in the H norm, but are not, we still, let's say be optimistic, still don't have optimal results for the error. That's why I'm going to present these results. But basically you can do the same replacing the, the norm with the error and the R minus one-half with two R. Okay. And you get the same. Okay. So the, what happens, what I told for R bigger than three-halves is the fact that you do not, even if you're asking more to your solution, you don't see this, this regularity and this is called as saturation. So T-con of regularization as a saturation effect. And the problem in practice is the fact that you do not know R. So you do not know how to choose the regularization parameter. And so usually you need some adaptive results. And in this case, since you are dealing with the H norm, we will, you can use for instance, Lebsky, also known as balancing principle that allows to recover these optimal rates. Okay. So if you, finally, if you assume some further assumptions on your operator T, so that more precisely the eigenvalues decay with a certain rate, then you can improve, improve the rates. So that are called capacity dependent rates. So that depends on these decay of the eigenvalues and are more precise, more, let's say, tailored to the properties of your operator T. So in the, in the talk, I will consider the capacity independent setting. Okay. But there is a but. So all the analysis that I show to you does not take into account the optimization error. So there is a, okay. So what, what can we do? So someone did it already. So there is a, in the paper by Butuebosque, we can, what they suggest is the fact that if we are in the large scale scenario, computing these estimator W at lambda can be costly. And so this estimator is the solution of a minimization problem and does not come automatically out of your computer, but you will need to approximate it, to compute it. And so what makes more sense in this scenario, since this will be a bottleneck, is to analyze the behavior of a, let's say, an approximation of the true minimizer. Okay. So I will denote it with the lambda and T, meaning that T is the, so that this W hat lambda T is the outcome of the teeth iteration of an iterative procedure applied to the regularized empirical risk. So to the classical variance variance decomposition, we add another term, which is an optimization term. So the first, the first obvious comment, let's say comment or consideration that one can do looking at this decomposition is that when we use an optimization procedure in order to optimize the regularized empirical risk, it makes no sense to go beyond the statistical accuracy, since it will be not, so it will be lost, let's say the additional effort will be lost. Okay. So what can you, so okay, so on one hand, this decomposition, so parallel to this observation, let's say in the last year, in the last years, there have been a very active research on optimization methods to solve problems that have exactly this form, so that can be interpreted as, let's say, regularized empirical risk functions, so that have the structure of, have some structure and maybe are strong, possibly are strongly convex or not, and especially in the large scale scenario. So there have been a, there has been a huge amount of work on methods that scale to these dimensions, so our first order, and in a sense are not blind with respect to the structure of the function we optimize, so taking into account that we are minimizing a sum, so I'm thinking to both first order method, but splitting, stochastic, incremental, aggregated, okay, so all these class of methods. So what we can do once that we have the convergence properties, so the complexity bounce on these optimization methods, we can think to balance these two terms and to obtain some new trade-off that include also the number of steps that are needed in order to approximate my, okay, my true parameter. What we can also do, and it's what I will do now, is to instead take another direction and to abandon this, the composition, trying to, to have one that does not split, let's say the statistical part from the optimization one. Okay, so stochastic gradient method is maybe the algorithm that does this job. So the idea is that we forget the empirical risk and we try directly to minimize our true risk, so the expected error. In this case, and with what, with a stochastic gradient descent method, since we do not have access to the true gradient, since our measure is unknown. So one possibility is to use this simple version where each step is determined by, so each stochastic approximation of the gradient is given by a single sample point. And so the, in this setting, there is no explicit regularization, we do not have explicitly lambda appearing. And we have also several theoretical results. So under various assumptions that establish some convergence results of this iteration, towards the minimizer or the minimum of the true risk. But what's the point here, so what the point I want to make is the fact that in practice, very often multiple passes over the data are done. So I'm of course considering a situation in which I know how many data I have, so it's not a truly online situation because I know the horizon, I know how many data I will see, and in which I have the possibility to see, to visit them more than once. But this is done in practice, and so the, our idea was to try to explain from a theoretical point of view why these work. Okay, so I rewrite, we focused on the simplest version of multiple passes stochastic gradient, which is a C-click version. So I rewrite the iteration in order to make some points. So the, as you can see here, so the, okay, if you look at multiple passes stochastic gradient, this can be immediately interpreted as a minimization procedure for the empirical risk. So this is well known. If we visit each point infinite times, we will converge to the minimum of the empirical risk. But then the other observation that can be made is the fact that each step is a gradient, so it's a stochastic gradient step, as before. And why I use this strange decomposition, so with an inner loop and an outer one, because I wanted to keep this number t, to put in, in evidence this number t, which is the number of passes over the data, and that are usually called, that is usually called epoch. Okay. So the main question here that I try to answer is how many passes should we do? Should we, how many times should we see our, visit our data in order to minimize the true risk? So what's the, what's the point? So as I told you, there is, there is a, let's say the convergence of the iteration towards the minima, to the minimum of the empirical risk is well established. So starting from Berzec, but also before Gaiwuronski, Poliak, so there are many, so let's say it's classical. But what we would like is to prove this kind of result. So what's the point? And the idea is to exploit stability properties of our stochastic gradient and early stopping. How? So we first introduce an auxiliary iteration, which is the gradient descent applied to the true risk, Wt. As you can see here, this step, I fix the step size, which is gamma over n. Gamma is a constant, n is the number of points. And I write the gradient descent in this strange way in order to make the comparison easier with the incremental method. So Wt, if you want, Wt plus 1 will be the results of t plus 1, let's say n, t plus 1 iterations of the gradient descent on the true risk. So what happens? We know that this, it's a gradient descent applied to the risk. This iteration will converge to the minimizer of the risk. Okay? On the other hand, what I have is that I have the, my say multiple passes, stochastic gradient, applied to the empirical risk. And I will prove that for a certain time, these two iterations are close to each other. But then after a while, this iteration deviates from my goal and goes towards the minimizer of the empirical risk. So the job here is to detect, let's say, this zone where the approximation of my true objective holds. Okay? So I'm a bit confused here because if you're using fixed step size and you're not averaging, then you're not converging. So okay, that's, yes, it's true. So here I cheated a little bit. The step size, no, that's, so here, this one is converging. Do you agree? No. So this is a true gradient applied to a complex functional. So I fixed step size. But you're, you're, you're, and it's fixed. Oh, there was no x i. Okay, okay. Yes. Okay. Oh, sorry. Okay. Instead, this one, so this, on this one, I, so it's not very true, let's say. It's true in, sorry, in function values, for sure. But here we do not assume strong convexity. So that's the, a subtle point, but it's not, I think, important or essential for, for the presentation. Okay. So before giving the theoretical results, let's see what happens in practice. So what we did here is a very simple simulation. We generated some, so it's a linear regression problem. We generated some random points uniformly in RD and some noisy measurements, y i. And then we divided these points into a training and a test set. And we applied these incremental stochastic gradient. So what happens is that if you look at the training error, so more or less is decreasing, right? We know that since it's an incremental, it will not be a descent method, but this, this converts towards the, the MIMO. While if you monitor the test set, what happens is that, which should be a good approximation of our true error, expected error. What happens is that after some iterations, these curves starts to, to go up, to, to go up again. And therefore we start in, let's say an overfitting region, right? And we should better early stop our iterations here instead of going until the end. How many points here? So yes, I don't know. I will, I tried to, so it's an old figure. I think that here should be, I think it's around like 30, 50, less than 100. So and this is the number of iterations. So should be, I think, could be, I think that there is the right answer is 30 points and this is the true number of iterations. So here is really the first epoch. So the first epoch is very effective here and then it starts decreasing a little slower. And I guess, do you know what, like function or like what R is for this particular simulation? Sorry? What function or what R? So it's a linear function, linear regression. And I don't know what is D. So it was really just a, a plot to, to show the behavior. But it's a linear function in, in some Rd. So XI are in Rd and YI are in R. Okay. So here there is an example. There should be another point of view, another perspective on a similar example, not the same. So here we have, these I know better because it's more recent. So here is, we try to approximate is again a linear regression problem, but it's a function that can be written as a linear combination of trigonometric functions. So here we have 40 trigonometric functions. And if I'm not wrong, I don't know exactly point 30, 40. Okay. So this is the result. What happens after the first epoch of incremental gradient? And that's what happened after the 10th. And that's what happens after the 100th epoch. So that's, that's the idea. The idea is to stop the iteration in the middle in order to achieve, let's say, a, a reasonable approximate, so a regularized approximation of our points. Okay. So result. If we assume, so only boundedness and existence of a solution without assuming any source condition, what we can prove is the following. So fix the step size. As you can see here, the step size depends on our boundedness constant, our constant, unknown in general. And so what happens is that we can prove that this estimator is universally consistent. So converts almost surely to the true one. If we assume two things. First, the number of epochs goes to infinity as the number of points grow. And second, it goes to infinity not too fast. So this can be interpreted. So yes, you have the comments. So the comments that we can make on this statement are three. So this step size is fixed. Okay. It's a constant. But I recall you that is divided by n in the implementation. And so the, the, what, what this says is that on one hand, early stopping is needed to achieve consistency. And this can be interpreted as an early stopping rule since we, the number of epochs should not go to infinity too fast. But on the other hand, the number, so we, we need multiple passes. So what these results says that with our analysis, with this choice of step size, you need multiple passes. Okay. There are single first, single first, I know that's exactly the same part. Okay. I, I, just wait. I need it. Yeah. Yeah. I need it. Yes. So this is needed with this choice of step size. Okay. So, yes, just comment, brief comment on this. What we, so what we proved is that if you do, if you take a very small step size, so gamma over n and you do multiple passes where multiple passes is of the order of this quantity here, then you have consistency. And the other hand, what you can prove is that if we do one pass stochastic gradient method and you choose a larger step size and you choose just one epoch, then you will achieve the same result. Okay. So here again is the same imprecision that I mentioned before. So I'm stating this for the iterates. So for the, for the W's, this is not known, I think. So, but, so the, the idea is this one. If you care about the error, the comparisons is this one. So why multiple passes make sense? Why should I do smaller step size and visiting the data more than once instead of doing only one pass with a longer step size? So I, I try, I hope I will convince you that this makes sense in the following slides. So that's where the source condition comes into play. So if we want finite sample bounds, we need to assume a source condition. And in this case, we can still prove high probability. Let's say we can prove high probability, convergence with high probability with these rate here, exponent here. If the number of passes over the data depends on our, is proportional, let's say to, not proportional, but depends on the regularity of our, of the source solution. So what does some comments again, what does it tell us the fact that first the rates are minimax again, so are optimal, the same that I showed at the beginning for T-conoff method. Good news, there is no saturation with this method. So are, even if R goes to infinity, so as R goes to infinity, this rate is improving. So it's increasing until square root of n. And the, yeah, probably. And the stopping rule, so what happens is that this, the only thing that I have to tune, let's say to, I have to, I need to be adaptive is the stopping rule. For the number of passes over the data. So also here, as in the T-conoff case, I can use, I can get adaptive results by using, for instance, again, a balancing principle. Okay, so now I'd like to do a second round of comparison with stochastic, one pass stochastic gradient. So in order to compare with the existing results that let's say are in the same setting as ours, so in an infinite dimensional setting taking into account the source condition, I add this, let's say, a regular, additional regularization term in order to compare with all of them. Okay, so the theory, as I said at the beginning about stochastic gradient as a long history, so convergence in finite dimensional case for strongly convex function is classical and goes back to Robin's and Monroe and there have been many other developments later. Instead in an infinite dimensional case and specifically in a reproducing kernel-liber space with the square loss, I would say that the analysis starts from this paper by Smale and Yao in 2006. So there are three papers on which I think it's useful to compare with which is useful to compare our results and this paper by Iminging and Pontil, this by Thares and Yao and this by Francis and Imeric de Lever. So okay, first, I say first things that are less relevant, not less relevant but less relevant for what I'm going to say later. So first, this is the only paper which is able to obtain capacity-dependent bounds, so the same that holds for T-con of regularization, so that is able to take into account the effective dimension of the problem, so to interpolate between the finite and infinite dimensional case. The other two cases instead are in the capacity, are capacity-independent rates as ours and as you can see there is a difference, we have some methods which have saturation, for instance this one or this one and this one by Iminging and Pontil that does not saturate. And there are different results in expectation and with high probability, the only one with high probability is this one as ours and usually the analysis to obtain high probability bounds is more involved. So now I want to say that the only comment that I think is really relevant here, so as you can see here, also in this case it's true by the way, in order, so they are okay and all these papers obtain optimal rates, minimax rates, so they are indistinguishable from a statistical point of view, all the methods that I presented. So the point here is that in order to achieve these rates, both in all these papers, the step size depends on the source condition, on the parameter R in the source condition. Here we have only gamma, also here and we have both gamma and lambda. So the new picture is the following. So we now, I think... Is also the case in the third paper, the one from... Yes, also here the gamma depends on the source condition. Okay, so here we have the new picture, let's say, we can... Basically we have two regimes in which we can achieve minimax rates. One is the one which you take a small step size, universal, so not dependent on the source condition and the number of passes on the data that depends on your source condition. The other one is where... The case where you do one pass with a bigger step size and you do only one pass, possibly with averaging. So I think that... So in both cases, what I want to say is that model selection is needed. And in order to achieve minimax rates, here you have to select the right step size and here you have to select the right number of passes over the data. So from this point of view, what I'm claiming is that our method comes as a natural approach, in the sense that what you can do, for instance, is to have your training error and keep a test and just monitoring online the behavior of the test error and simply stop when over-fitting happens. So that's... I think it's the... The main difference is who plays the role of the regularization parameter. Here is the step size, here is the number of passes. And what I'm saying, and I repeat, is that being adaptive on the number of passes over the data is natural and can be done. Yeah. I mean, is it sort of too far, I like to say, that all that really matters is the sum of the step size being kind of the same whatever approach you use, because I guess the sum of the step size... Yeah, the step size, yes. So here, all the analysis that I have in mind with the constant step size, let's say constant divided by n, but yes, for instance, for the approximation error, so that is the optimization error here, what really matters is the sum of the step size and the same, I believe, so it's certainly the same for the sample error. So if you use different step sizes, one of the sum kind of stays the same, you'll get up to... So the point is that from our analysis, you can derive some convergence for this case, so for t star equal one, so if you take into account the gamma, and if you take gamma depending on the source condition, so you can. But the point is that we do not get optimal rates, and we do not... Yes, we do not get optimal rates, and the step size that are derived from our analysis are too small. So an open problem, a future, let's say, direction of research would be to understand what is the analysis, if there is an analysis that allows to interpolate between the long step size one pass towards the short step size multiple passes. Yeah, because here to main back to the triangle of computation statistics and something else, so here the multiple passes, if you actually count the gradient cost as expensive, it's much more expensive. Yeah, it's true, it depends what you have to do here in order to select the right step size. So probably you will have to do multiple passes, maybe on less data, just to adjust the step size. I don't know, two, yeah? So why not doing like a constant step size, I'm sure you can derive similar results with gamatik, with gamma, and with the early stopping, which should be much earlier. So gamma constant. Yeah. So in our case, at the moment, we are not able to do it. Yeah, it would be great. It's always convergent, so if you do a single pass with a fixed gamma, always convergent, it will be very slow. With multiple passes, you must... You reduce the variance, maybe. Yeah, no, I don't know. Only because you know the type of law. I don't know. You need smaller step sizes. Constant is too big. Yeah, because as you can see, if you look at the, let's say, sample error, so the stability, it increases with gamma. Therefore, I don't know. No, but I think you need like... The sample error needs like a smaller step size, so you can only get smaller and do multiple passes. Yeah. We cannot be bigger. We need to lessen the single pass. Exactly. It's gonna be... Yeah. Yes, what... Yes, it's exactly like this. So we can prove that... So from our analysis, you can derive that you have convergence for t star and equal one, and your gamma should be a gamma of n increasing. Okay? I don't know if this answers the question. Okay, so just one last comparison. There is also gradient descent. So we know that gradient descent on the empirical risk with early stopping works. And what I can say is that... So from the computational point of view, and both from the computational and the statistical point of view, there is apparently no difference between multiple passes stochastic gradient and gradient, the full gradient. So one point to... This is one point to be understood. And I have to say that is one point to be understood also in the optimization scenario. I mean, same coefficient, no, no, but gradient descent is being more garagian, so... I know. No, so you can prove that the stopping time is the same. So if you, let's say, do the mapping, so one epoch equal to one pass is exactly the same. Same stopping time, same step size. You can use a constant step size of the batch measure. You can use a constant step size, I think, for batch mode problems. Yeah, but it should be smaller. I think that the Lipschitz constant of the empirical differences, you have the one over an appearing... If I'm not mistaken, what you're missing is the capacity dependence. Yes, for sure. These one, we are not... At the moment, we don't have them. It's insensible if you combine what you did, but M-ray glue to combine and to get that to... So on this, what... So, as I was saying, this is an open problem also in optimization. It's not clear what is the advantage of an incremental gradient method applied to a sum of parabolas instead of a gradient method. But what is known is that... So empirical observed, at least, and some, let's say, almost theoretically justified, is that at least when you are far from the minimizer, at the beginning of the iteration, one pass of incremental is more or less equivalent to one full gradient pass until you do not enter in this confusion region where you're close to the minimizer, but the minimizers of your summands are away, so push you away from the true one. So this would be, again, could be one reason why, empirically, the incremental gradient has a better performance than the full one. Okay, so just maybe some idea of the proof. So just to see a trade-off, a new trade-off. So we... I recall you that I consider... I'm comparing my iteration with the one, the true gradient one. And so the variance variance trade-off this time is obtained by bounding this quantity here with the difference between our, let's say, in multiple passes, stochastic gradient iteration with the gradient on the true risk. So this quantity here, now, the bias is exactly the optimization error, right? Because I am applying the gradient method to minimize a function. Therefore, this is exactly the optimization error. And here, instead, I have the sampling that comes into play. And so as I showed you before with the picture, the idea will be to prove that this quantity is increasing with t, decreasing with n. And but, yes, and this quantity, instead, of course, is decreasing with t. Therefore, the idea of the proof is to balance these two terms. Okay, so I prepared just a few slides to give an idea of the proof. As I said at the beginning, so I don't forget, all... As you can see also already from here, the square loss plays a very crucial role because otherwise I do not have this expression of the iterates. So the idea is that I can write the iterate at the end of one epoch as a perturbed gradient descent iteration. So it's almost a gradient descent with step size gamma, but we have here a perturbation term. And so the idea will be to, yes, to compare this with the analog in the continuous setting. So here I have this operator, it's just this one, covariance operator, second moment. And okay, this one is an element in H. And then here you have these two quantities that are quite complex, as you can see. So that's the point. And the same you can do for the iteration on the expected risk. And you get more or less a very similar expression here, very similar A and B. And so what you do basically is to write the difference between these two iterates by a sum of an operator which has norm less than one, and so you forget it. And then you have this sum here where you have always, let's say, an empirical mean and its expectation. So you compare the empirical mean with the expectation. And so basically you can apply a concentration inequality to this. The only problem is for these two complex terms here, because they are not some of independent variables, but they are still some of martingales. And therefore the pinealists concentration inequality still apply. And then you get a bound of this form, increasing in T, decreasing in N, as I was saying, with high probability. Instead the, okay, the approximation error is standard, is well known, and you can prove that the rate depends on the source condition and on the sum of step size that are constant. And so the final result is obtained by balancing simply these two terms, and you obtain the expression that I showed. Okay, so the contributions, I think that we, so we add some results that are the first results explaining, trying to explain the generalization properties of some used heuristics for stochastic gradient, and more specifically multiple passes and early stopping. And so some future work I already mentioned, therefore some of these mentioned already Francis. So I think that's, that's all. Thank you. Okay, this is the paper. Maybe. So further questions and comments for Silvia, and see more can start if you want. So there was no notion of randomization within a pattern. Okay, so these, so we started from the cyclic one, thinking it was the easiest, probably, I don't know if from the, from the, for the analysis it is the easiest one, but in any case, so I think that already Lorenzo Rosasco with Junong Lin, tried to generalize these results both to a non-square loss and to other sampling techniques. So in particular the stochastic one. So you visit the time, your points multiple times, but you, you randomly select one. What is still missing, which would be very interesting, I think is the random reshuffling, let's say. Because, because here is, you're saying that my data came from some distribution ID. Then I have whatever order and I'm just running it through it, and you're saying everything is, is fine. Yeah, it works. It works. I mean, you're also in the deterministic cases like this, right, in optimization. But here it's all asymptotic, I guess. No, the key is that you can do that like full-radiant or the equity risk up to a point where you start with that error, and this is a T star or N. I'm just trying to reconcile this kind of result. With the earlier results we talked about during this workshop where having random permutation versus random sampling versus. The random, I think, yeah, the random sampling comes from the fact that you have random, so your points are ID, and that's it. So that's like your random permutation. I think so. And then after, after this you can, let's say, this is just an optimization procedure to minimize the, it's not true, but to minimize the empirical risk. And you can either access to your point, to visit your points randomly, you can visit your points cyclically, you can choose to visit your points by randomly reshuffling them after each epoch. So from the optimization point of view, this last policy seems to be the best one empirically. There are some results, very recent results, to show that it works also in theory, but I'm, so I don't know exactly the constants. So what is known that, at least up to my knowledge, is that the increments in the deterministic setting, so the incremental choice of the points behaves usually worse than the stochastic sampling. But for instance, in the strongly convex case they are the same. Then there is a recent paper by Guru Bhoot, Zubalaban, Parrillo and Osdaglar. Yeah, but there the constant is awful. Yeah, yeah, the constant, yes. It's a matter of the constants. Yeah, but still it's linear. So it's from, let's say, we don't see this effect here. I don't think, so what could happen, but I don't think so, I don't think so, that you, if you're optimizing, so if your optimization procedure is better, faster, probably you can stop earlier, but would expect this more from an accelerated method than from the random. Yeah, sorry. Another question for Sylvia? Yep. Could you show question people, that's good. Could you show your convergence rate again? Again, yeah. So the best R is the infinity. Yeah, yeah, but you cannot choose it, so it comes with your problem, right? So it's a datum of your problem. So what's the typical value of R? I don't know. If the data is IPE, the traditional framework, we have the convergence rate is square root n, but in your case, your best convergence rate is square root n. Yeah, be careful, because here we are looking at convergence of the iterates and not of the error. So the square root of n that you're talking about is on the error. Okay. So in this case, on the error, it would be 2R divided by 2R plus 1, so it should be better than 1alpha, I hope. You should compare 1alpha with this. So when R goes to infinity, this goes to 1 over n. Okay. Other questions? I have a question related to basically, yeah, you talked about regularization, and now like this approach is not using regularization at all. So basically, or maybe not, maybe not. So I basically have two questions, so if I know the value of R, which one is going to be faster to use early stopping, I mean, or to, I guess, it's only one path. If you know R, I would suggest to use one path, because it's one path. But the point is that usually you don't know it, and yes, the regularization comes from the early stopping, if you want. It's the idea that is well known in the inverse problems literature, where you, in a sense, exploit some self-regularizing effect of iterative procedure. So you can interpret them as regularization procedures, and therefore the early stopping of iteration allows you to get a form of implicit regularization. I understand that, could you add some, I mean, the fact of adding some regularization would make your problem more strongly condensed. Yeah. So it would help you to make progress at the beginning, and then is there a way to add regularization basically, you want to get an easy, then you want to do anything, but I guess. No, I think it works, so you can add it, you can apply it, you just add. Also, I think this analysis in the sense, but probably can be refined. What I fear is that the lambda will depend on R, again. So you will have something like this, where you're, so that you should then cross-validate also on this parameter. So you use a fixed lambda, but maybe you can change that. So if you use a fixed lambda, I don't know if you go to the, if you are able to approximate the true solution, I don't think so. I'm not sure. No, I meant that you could allow lambda to change with t, and not only with n. Ah, yes, yes, this is, oh, so, sorry, yes, of course. I compared my results with, let's say, the results in the online setting where the horizon is known, because this makes more sense in the sense that we know the horizon, so it would be, but of course, so here, so all these quantities here are constant with respect to t, but in the true online scenario, you will have something that varies with t more or less in the same way. So will be, so will not be constant. Yes, you could do it, but I guess that will depend again on r, also in this case. Last question, and when you don't know r, what kind of modellistic procedure would you recommend? Cross-validation, maybe, because the stopping, so also for the... Guarantees on... Yes, yes, yes, you have guarantees. You can achieve the same rates with cross-validation. So for this, so for the iterates, you need a balancing principle, but since the stopping time is the same, both for the risk and the iterates, you can play a little bit with this and use cross-validation. So let's thank Cilia again.
 So thank you for the introduction and the invitation.  So we have learned during this workshop that large scale learning, to deal with large scale  learning problems, statistical aspects and optimization aspects has to be treated jointly.  One example of this is the stochastic gradient method that today is an algorithm of choice  for these kind of problems.  So our work started from the observation that there are several results studying generalization  properties of one pass stochastic gradient descent, but in practice very often other  heuristics are used such as multiple passes over the data and usually combined with early  stopping.  So what I'm going to present today are some theoretical results about these kind of heuristics  and in particular the generalization properties of such kind of variants of SGD.  I will call it randomly stochastic gradient method, stochastic gradient descent, so SGM,  SGD.  So I start from the problem setting.  We consider linear regression in an abstract Hilbert space with the square loss.  So the choice of the square loss is critical in our analysis, all that I'm going to say  heavily depends on this choice.  So probably I will forget to say this again during the talk, but so square loss plays a  crucial role.  So the objective in learning or in stochastic optimization is to minimize a functional E  which can be written as an expectation.  So in this case again the expectation of a square loss which depends in our setting linearly  from W.  And the problem here is the fact that the measure rho in general is unknown, but we  only have some, we can only access to a finite number of points that are called examples.  And so I have access only to these points that are independent and identical.  So a randomly sampled from rho.  So this setting naturally includes the linear regression with Gaussian noise in RD.  So if I fix H to be RD, I can generate data for instance by randomly sample points Xi  in RD and then by measuring some linear measurements corrupted by Gaussian noise, delta I.  But also this framework includes for instance functional regression if my input points belong  to an infinite dimensional space.  For instance our curves or functions.  Also this is a, let's say is an equivalent way to write the learning problem in reproducing  kernel in birth spaces.  So if you consider learning in an RKHS, then what you want to do is to minimize this again  this risk where this time the function W that I want to find, so the element in HK is a  function now depends non-linearly from the input variable.  But as I think most of you know, if W is a function in the reproducing kernel in birth  space generated by a kernel K, then we have the reproducing property therefore W evaluated  at the point can be written as a scalar product between two elements in our birth space H.  So Xi here is like X.  Exactly, so Xi are the inputs that you will see in a moment why I don't call it X.  And so the Xi can be seen as the input space R is the output space.  And W is a function mapping the input into the output space.  So what I can do is to consider a function that identifies the input point Xi with the  kernel evaluated at this point Xi and send Y, leave Y unchanged.  And then if I consider these change of variables inside these integral function, what I can  write is that I use first the kernel trick.  So W of Xi is the scalar product between W and K Xi and then I use the change of variable  and then back to the model I'm presented at the beginning.  So in this setting a classical approach is Ticonovergolarization.  So what I want to do in the rest of my talk is to start from some very classical and basic  results about Ticonovergolarization for learning problems.  And then I will state some assumption and then state the main results and then I will  compare them with the one that we get in for stochastic gradient descent.  So what is the Ticonov estimator, the regularized empirical risk estimator?  It is a point in my space age that can be built in this way.  So I first replace the risk which is unknown by its empirical version and then I add to  this risk a regularization function R that in this talk will be the square of the norm.  Then what I do is that I minimize this regularized empirical risk and I build this estimator  W hat which depends from a parameter which is the regularization parameter that balances  the weight of the regularizer against the data fitting term.  So the properties of this estimator has been studied a lot but mainly from a statistical  point of view.  So now I want to present to you some statistics, statistical properties of this estimator.  In order to do that I need to introduce some assumptions.  And so the first one is a fairly standard assumption basically requires that my measure  rho is as a bounded support.  So all my point axis, the norm of my point axis is bounded almost surely and the same  holds for the output y.  So the second one is this, okay, this assumption can be relaxed for what I'm going to say but  I will consider this simpler setting.  Another assumption that I do in this talk is the fact that the risk has a minimizer.  And therefore, since it has at least a minimizer, the set of minimizers is non-empty and I can  consider the minimal norm solution.  This is a less standard assumption.  It's a particular case in learning that is referred, I will call the attainable case.  So where you have exactly one target parameter to estimate.  So under these assumptions you can already prove some consistency results of the T-conve  estimator but more assumptions are needed if we want to have more precise bounds, so  known asymptotic bounds for the error.  So the existence here is just because you're perhaps infinite, infinite dimension.  If you're infinite dimension, if you're bounded in this case you will have always a solution.  In infinite dimension or in finite dimensional, so yes, bounded sets are compact, therefore  you have a convex continuous operator, the risk in this case it is, and therefore you  have a minimizer.  Because will you use the infinite dimensions anywhere else in the talk in the future?  Can we always take each type you say about something that we're at a fine dimension and  double use?  Yes, you can.  Yes, yes.  Okay.  As a convex, so you know something like the infinite dimension but you see that the number  of W stars is very large.  Yeah, it can be, yes.  So large at infinite, that is finite, right?  It is finite but you don't have maybe an estimation for instance.  No, sorry, my comment was your dog.  Sorry, my comment was if you don't assume that W is in the set, it's like having W star  being very large in the finite dimensional set.  Okay, you assume that W star is finite and the norm is reasonable.  Okay.  So some of the results, so I'm presenting the results in these settings, some of the  results that I will present all even without these assumptions but in this talk I will  assume that these all.  So mainly because I want to introduce this source condition that is the technical condition  that allows to get these error bounds.  So first I define T which is the second moment operator.  So it's an operator linear from H to H and this well defined bounded C thanks to the  boundedness assumption that I just assume.  Okay.  What is this source condition?  So it can be read as a regularity assumption of the solution I am assuming to exist and  more precisely it asks that the solution, the minimal norm solution belongs to the range  not only to the range of T but to the range of T at a certain power.  Okay.  So I will use this strange indexing just for easy to make easier the comparison with the  existing result because this is the usual scaling that is used in the available papers.  Okay.  What does it mean?  So with the picture we have the space H if R is equal to one-half I'm not asking anything  since T to the zero is the identity therefore I'm just asking existence of the minimizer.  If R is bigger than one-half then these spaces that are vector spaces subspaces of H are  nested and as R increases my condition is stronger.  Okay.  So as R increases I'm requiring more regularity to my solution.  Why do I call it regularity?  Here is another interpretation.  So the operator T is a compact operator from H to H, self-adjoint therefore I can diagonalize  it and build a sequence of eigenvectors and eigenvalues.  Okay.  So my point W dagger belongs to H. This is a basis of H and so this quantity is finite.  So this is equivalent to existence of W dagger.  What does the source condition mean?  It asks that since W dagger is in the run of T then H I can invert this operator and  I can write H this way.  Therefore H belongs to H to the capital H and here what I can do I can compute this  quantity using these basis of H and I get this condition.  So I get that since H is as a finite norm this sum here is finite.  What does it mean?  So remember that these eigenvalues are going to zero.  We have a compact operator.  So this inequality here asks that these coefficients, these Fourier coefficients go to zero sufficiently  fast.  Okay.  So faster than usual.  So this is the usual and this is the stronger assumption.  Okay.  Okay.  So with this condition, so boundedness plus source condition, we can prove the following  error bounds on the T-conoff regularized estimator.  So the key point here is the choice of the regularization parameter.  As you see I can prove that I have some bounds if I choose the regularization parameter as  dependent on n in this way.  So in a way that depends on this source condition.  What I get here is that if r is smaller than 3 alps then I have this rate that increases  as r increases but then at a certain point this rate doesn't increase anymore and it  stops and is minus 1 alph.  So if r is bigger than 3 alps, even if I'm requiring a stronger regularity on my solution,  I will not be able to approximate it in a faster way.  Okay.  So just the idea of the proof is a bias variance tradeoff.  So what I do here is I introduce an auxiliary point W lambda which is the minimizer of the  risk through risk plus regularization.  So I will not have access to this point but I don't need to compute it.  I just use it as a reference point and then I can decompose the difference of the norm  between my estimator and my true parameter W dagger as the sum of, I can bound this norm  with the sum of these two terms.  And as you can see here we have a term that depends on the sample and the term that depends  only on the choice of lambda.  So on the regularization properties of my approach.  So balancing the two terms gives this, the behavior of this term is determined by the  choice of the, by the source condition.  We will have the result.  So these results, the results that I showed are minimax.  In this sense, so in the sense that if you fix a class of probability measures, and in  this case the class of probability measures that I fix are the ones that satisfy the assumptions  I just introduced, then okay I will have a different solution for each, in general a  different solution for each probability measure.  And I can, if I fix an algorithm I can compute the distance between the, the distance between  my algorithm and my estimator and my true parameter.  Then I can do a worst case analysis in the sense that I put in front of it a maximum.  Therefore I take the problem on which my algorithm behaves worst.  And then among all these, all the algorithms that I have at my disposal I take the best  one.  So I take, take the algorithm which has the best worst behavior.  Okay, and as you can see here, I don't know if you remember the, the exponent in the bounds  for the T-con of regularization.  You get the, the exponent to this n is the same.  Therefore the, yes.  Oh, sorry, sir.  Is there a reason why you're choosing to do this in that Hilbert norm rather than the  two norm?  Okay, yes.  So the reason is the following.  The results that I'm going to, that we obtained for multiple passes SGD are optimal minimax  in the H norm, but are not, we still, let's say be optimistic, still don't have optimal  results for the error.  That's why I'm going to present these results.  But basically you can do the same replacing the, the norm with the error and the R minus  one-half with two R. Okay.  And you get the same.  Okay.  So the, what happens, what I told for R bigger than three-halves is the fact that you do  not, even if you're asking more to your solution, you don't see this, this regularity and this  is called as saturation.  So T-con of regularization as a saturation effect.  And the problem in practice is the fact that you do not know R. So you do not know how  to choose the regularization parameter.  And so usually you need some adaptive results.  And in this case, since you are dealing with the H norm, we will, you can use for instance,  Lebsky, also known as balancing principle that allows to recover these optimal rates.  Okay.  So if you, finally, if you assume some further assumptions on your operator T, so that more  precisely the eigenvalues decay with a certain rate, then you can improve, improve the rates.  So that are called capacity dependent rates.  So that depends on these decay of the eigenvalues and are more precise, more, let's say, tailored  to the properties of your operator T. So in the, in the talk, I will consider the capacity  independent setting.  Okay.  But there is a but.  So all the analysis that I show to you does not take into account the optimization error.  So there is a, okay.  So what, what can we do?  So someone did it already.  So there is a, in the paper by Butuebosque, we can, what they suggest is the fact that  if we are in the large scale scenario, computing these estimator W at lambda can be costly.  And so this estimator is the solution of a minimization problem and does not come automatically  out of your computer, but you will need to approximate it, to compute it.  And so what makes more sense in this scenario, since this will be a bottleneck, is to analyze  the behavior of a, let's say, an approximation of the true minimizer.  Okay.  So I will denote it with the lambda and T, meaning that T is the, so that this W hat  lambda T is the outcome of the teeth iteration of an iterative procedure applied to the regularized  empirical risk.  So to the classical variance variance decomposition, we add another term, which is an optimization  term.  So the first, the first obvious comment, let's say comment or consideration that one can  do looking at this decomposition is that when we use an optimization procedure in order  to optimize the regularized empirical risk, it makes no sense to go beyond the statistical  accuracy, since it will be not, so it will be lost, let's say the additional effort will  be lost.  Okay.  So what can you, so okay, so on one hand, this decomposition, so parallel to this observation,  let's say in the last year, in the last years, there have been a very active research on optimization  methods to solve problems that have exactly this form, so that can be interpreted as,  let's say, regularized empirical risk functions, so that have the structure of, have some structure  and maybe are strong, possibly are strongly convex or not, and especially in the large  scale scenario.  So there have been a, there has been a huge amount of work on methods that scale to these  dimensions, so our first order, and in a sense are not blind with respect to the structure  of the function we optimize, so taking into account that we are minimizing a sum, so I'm  thinking to both first order method, but splitting, stochastic, incremental, aggregated, okay,  so all these class of methods.  So what we can do once that we have the convergence properties, so the complexity bounce on these  optimization methods, we can think to balance these two terms and to obtain some new trade-off  that include also the number of steps that are needed in order to approximate my, okay,  my true parameter.  What we can also do, and it's what I will do now, is to instead take another direction  and to abandon this, the composition, trying to, to have one that does not split, let's  say the statistical part from the optimization one.  Okay, so stochastic gradient method is maybe the algorithm that does this job.  So the idea is that we forget the empirical risk and we try directly to minimize our true  risk, so the expected error.  In this case, and with what, with a stochastic gradient descent method, since we do not have  access to the true gradient, since our measure is unknown.  So one possibility is to use this simple version where each step is determined by, so each  stochastic approximation of the gradient is given by a single sample point.  And so the, in this setting, there is no explicit regularization, we do not have explicitly  lambda appearing.  And we have also several theoretical results.  So under various assumptions that establish some convergence results of this iteration,  towards the minimizer or the minimum of the true risk.  But what's the point here, so what the point I want to make is the fact that in practice,  very often multiple passes over the data are done.  So I'm of course considering a situation in which I know how many data I have, so it's  not a truly online situation because I know the horizon, I know how many data I will see,  and in which I have the possibility to see, to visit them more than once.  But this is done in practice, and so the, our idea was to try to explain from a theoretical  point of view why these work.  Okay, so I rewrite, we focused on the simplest version of multiple passes stochastic gradient,  which is a C-click version.  So I rewrite the iteration in order to make some points.  So the, as you can see here, so the, okay, if you look at multiple passes stochastic  gradient, this can be immediately interpreted as a minimization procedure for the empirical  risk.  So this is well known.  If we visit each point infinite times, we will converge to the minimum of the empirical  risk.  But then the other observation that can be made is the fact that each step is a gradient,  so it's a stochastic gradient step, as before.  And why I use this strange decomposition, so with an inner loop and an outer one, because  I wanted to keep this number t, to put in, in evidence this number t, which is the number  of passes over the data, and that are usually called, that is usually called epoch.  Okay.  So the main question here that I try to answer is how many passes should we do?  Should we, how many times should we see our, visit our data in order to minimize the true  risk?  So what's the, what's the point?  So as I told you, there is, there is a, let's say the convergence of the iteration towards  the minima, to the minimum of the empirical risk is well established.  So starting from Berzec, but also before Gaiwuronski, Poliak, so there are many, so let's say it's  classical.  But what we would like is to prove this kind of result.  So what's the point?  And the idea is to exploit stability properties of our stochastic gradient and early stopping.  How?  So we first introduce an auxiliary iteration, which is the gradient descent applied to the  true risk, Wt.  As you can see here, this step, I fix the step size, which is gamma over n.  Gamma is a constant, n is the number of points.  And I write the gradient descent in this strange way in order to make the comparison  easier with the incremental method.  So Wt, if you want, Wt plus 1 will be the results of t plus 1, let's say n, t plus 1  iterations of the gradient descent on the true risk.  So what happens?  We know that this, it's a gradient descent applied to the risk.  This iteration will converge to the minimizer of the risk.  Okay?  On the other hand, what I have is that I have the, my say multiple passes, stochastic gradient,  applied to the empirical risk.  And I will prove that for a certain time, these two iterations are close to each other.  But then after a while, this iteration deviates from my goal and goes towards the minimizer  of the empirical risk.  So the job here is to detect, let's say, this zone where the approximation of my true objective  holds.  Okay?  So I'm a bit confused here because if you're using fixed step size and you're not averaging,  then you're not converging.  So okay, that's, yes, it's true.  So here I cheated a little bit.  The step size, no, that's, so here, this one is converging.  Do you agree?  No.  So this is a true gradient applied to a complex functional.  So I fixed step size.  But you're, you're, you're, and it's fixed.  Oh, there was no x i.  Okay, okay.  Yes.  Okay.  Oh, sorry.  Okay.  Instead, this one, so this, on this one, I, so it's not very true, let's say.  It's true in, sorry, in function values, for sure.  But here we do not assume strong convexity.  So that's the, a subtle point, but it's not, I think, important or essential for, for the  presentation.  Okay.  So before giving the theoretical results, let's see what happens in practice.  So what we did here is a very simple simulation.  We generated some, so it's a linear regression problem.  We generated some random points uniformly in RD and some noisy measurements, y i.  And then we divided these points into a training and a test set.  And we applied these incremental stochastic gradient.  So what happens is that if you look at the training error, so more or less is decreasing,  right?  We know that since it's an incremental, it will not be a descent method, but this, this  converts towards the, the MIMO.  While if you monitor the test set, what happens is that, which should be a good approximation  of our true error, expected error.  What happens is that after some iterations, these curves starts to, to go up, to, to go  up again.  And therefore we start in, let's say an overfitting region, right?  And we should better early stop our iterations here instead of going until the end.  How many points here?  So yes, I don't know.  I will, I tried to, so it's an old figure.  I think that here should be, I think it's around like 30, 50, less than 100.  So and this is the number of iterations.  So should be, I think, could be, I think that there is the right answer is 30 points and  this is the true number of iterations.  So here is really the first epoch.  So the first epoch is very effective here and then it starts decreasing a little slower.  And I guess, do you know what, like function or like what R is for this particular simulation?  Sorry?  What function or what R?  So it's a linear function, linear regression.  And I don't know what is D. So it was really just a, a plot to, to show the behavior.  But it's a linear function in, in some Rd.  So XI are in Rd and YI are in R. Okay.  So here there is an example.  There should be another point of view, another perspective on a similar example, not the  same.  So here we have, these I know better because it's more recent.  So here is, we try to approximate is again a linear regression problem, but it's a function  that can be written as a linear combination of trigonometric functions.  So here we have 40 trigonometric functions.  And if I'm not wrong, I don't know exactly point 30, 40.  Okay.  So this is the result.  What happens after the first epoch of incremental gradient?  And that's what happened after the 10th.  And that's what happens after the 100th epoch.  So that's, that's the idea.  The idea is to stop the iteration in the middle in order to achieve, let's say, a, a reasonable  approximate, so a regularized approximation of our points.  Okay.  So result.  If we assume, so only boundedness and existence of a solution without assuming any source condition,  what we can prove is the following.  So fix the step size.  As you can see here, the step size depends on our boundedness constant, our constant,  unknown in general.  And so what happens is that we can prove that this estimator is universally consistent.  So converts almost surely to the true one.  If we assume two things.  First, the number of epochs goes to infinity as the number of points grow.  And second, it goes to infinity not too fast.  So this can be interpreted.  So yes, you have the comments.  So the comments that we can make on this statement are three.  So this step size is fixed.  Okay.  It's a constant.  But I recall you that is divided by n in the implementation.  And so the, the, what, what this says is that on one hand, early stopping is needed to achieve  consistency.  And this can be interpreted as an early stopping rule since we, the number of epochs should  not go to infinity too fast.  But on the other hand, the number, so we, we need multiple passes.  So what these results says that with our analysis, with this choice of step size, you need multiple  passes.  Okay.  There are single first, single first, I know that's exactly the same part.  Okay.  I, I, just wait.  I need it.  Yeah.  Yeah.  I need it.  Yes.  So this is needed with this choice of step size.  Okay.  So, yes, just comment, brief comment on this.  What we, so what we proved is that if you do, if you take a very small step size, so gamma  over n and you do multiple passes where multiple passes is of the order of this quantity here,  then you have consistency.  And the other hand, what you can prove is that if we do one pass stochastic gradient method  and you choose a larger step size and you choose just one epoch, then you will achieve  the same result.  Okay.  So here again is the same imprecision that I mentioned before.  So I'm stating this for the iterates.  So for the, for the W's, this is not known, I think.  So, but, so the, the idea is this one.  If you care about the error, the comparisons is this one.  So why multiple passes make sense?  Why should I do smaller step size and visiting the data more than once instead of doing only  one pass with a longer step size?  So I, I try, I hope I will convince you that this makes sense in the following slides.  So that's where the source condition comes into play.  So if we want finite sample bounds, we need to assume a source condition.  And in this case, we can still prove high probability.  Let's say we can prove high probability, convergence with high probability with these rate here,  exponent here.  If the number of passes over the data depends on our, is proportional, let's say to, not  proportional, but depends on the regularity of our, of the source solution.  So what does some comments again, what does it tell us the fact that first the rates are  minimax again, so are optimal, the same that I showed at the beginning for T-conoff method.  Good news, there is no saturation with this method.  So are, even if R goes to infinity, so as R goes to infinity, this rate is improving.  So it's increasing until square root of n.  And the, yeah, probably.  And the stopping rule, so what happens is that this, the only thing that I have to tune,  let's say to, I have to, I need to be adaptive is the stopping rule.  For the number of passes over the data.  So also here, as in the T-conoff case, I can use, I can get adaptive results by using,  for instance, again, a balancing principle.  Okay, so now I'd like to do a second round of comparison with stochastic, one pass stochastic  gradient.  So in order to compare with the existing results that let's say are in the same setting  as ours, so in an infinite dimensional setting taking into account the source condition, I  add this, let's say, a regular, additional regularization term in order to compare with  all of them.  Okay, so the theory, as I said at the beginning about stochastic gradient as a long history,  so convergence in finite dimensional case for strongly convex function is classical  and goes back to Robin's and Monroe and there have been many other developments later.  Instead in an infinite dimensional case and specifically in a reproducing kernel-liber  space with the square loss, I would say that the analysis starts from this paper by Smale  and Yao in 2006.  So there are three papers on which I think it's useful to compare with which is useful  to compare our results and this paper by Iminging and Pontil, this by Thares and Yao and this  by Francis and Imeric de Lever.  So okay, first, I say first things that are less relevant, not less relevant but less  relevant for what I'm going to say later.  So first, this is the only paper which is able to obtain capacity-dependent bounds,  so the same that holds for T-con of regularization, so that is able to take into account the  effective dimension of the problem, so to interpolate between the finite and infinite  dimensional case.  The other two cases instead are in the capacity, are capacity-independent rates as ours and  as you can see there is a difference, we have some methods which have saturation, for instance  this one or this one and this one by Iminging and Pontil that does not saturate.  And there are different results in expectation and with high probability, the only one with  high probability is this one as ours and usually the analysis to obtain high probability  bounds is more involved.  So now I want to say that the only comment that I think is really relevant here, so as  you can see here, also in this case it's true by the way, in order, so they are okay and  all these papers obtain optimal rates, minimax rates, so they are indistinguishable from  a statistical point of view, all the methods that I presented.  So the point here is that in order to achieve these rates, both in all these papers, the  step size depends on the source condition, on the parameter R in the source condition.  Here we have only gamma, also here and we have both gamma and lambda.  So the new picture is the following.  So we now, I think...  Is also the case in the third paper, the one from...  Yes, also here the gamma depends on the source condition.  Okay, so here we have the new picture, let's say, we can...  Basically we have two regimes in which we can achieve minimax rates.  One is the one which you take a small step size, universal, so not dependent on the source  condition and the number of passes on the data that depends on your source condition.  The other one is where...  The case where you do one pass with a bigger step size and you do only one pass, possibly  with averaging.  So I think that...  So in both cases, what I want to say is that model selection is needed.  And in order to achieve minimax rates, here you have to select the right step size and  here you have to select the right number of passes over the data.  So from this point of view, what I'm claiming is that our method comes as a natural approach,  in the sense that what you can do, for instance, is to have your training error and keep a  test and just monitoring online the behavior of the test error and simply stop when over-fitting  happens.  So that's...  I think it's the...  The main difference is who plays the role of the regularization parameter.  Here is the step size, here is the number of passes.  And what I'm saying, and I repeat, is that being adaptive on the number of passes over  the data is natural and can be done.  Yeah.  I mean, is it sort of too far, I like to say, that all that really matters is the sum of  the step size being kind of the same whatever approach you use, because I guess the sum  of the step size...  Yeah, the step size, yes.  So here, all the analysis that I have in mind with the constant step size, let's say constant  divided by n, but yes, for instance, for the approximation error, so that is the optimization  error here, what really matters is the sum of the step size and the same, I believe,  so it's certainly the same for the sample error.  So if you use different step sizes, one of the sum kind of stays the same, you'll get  up to...  So the point is that from our analysis, you can derive some convergence for this case,  so for t star equal one, so if you take into account the gamma, and if you take gamma depending  on the source condition, so you can.  But the point is that we do not get optimal rates, and we do not...  Yes, we do not get optimal rates, and the step size that are derived from our analysis  are too small.  So an open problem, a future, let's say, direction of research would be to understand what is  the analysis, if there is an analysis that allows to interpolate between the long step  size one pass towards the short step size multiple passes.  Yeah, because here to main back to the triangle of computation statistics and something else,  so here the multiple passes, if you actually count the gradient cost as expensive, it's  much more expensive.  Yeah, it's true, it depends what you have to do here in order to select the right step  size.  So probably you will have to do multiple passes, maybe on less data, just to adjust the step  size.  I don't know, two, yeah?  So why not doing like a constant step size, I'm sure you can derive similar results with  gamatik, with gamma, and with the early stopping, which should be much earlier.  So gamma constant.  Yeah.  So in our case, at the moment, we are not able to do it.  Yeah, it would be great.  It's always convergent, so if you do a single pass with a fixed gamma, always convergent,  it will be very slow.  With multiple passes, you must...  You reduce the variance, maybe.  Yeah, no, I don't know.  Only because you know the type of law.  I don't know.  You need smaller step sizes.  Constant is too big.  Yeah, because as you can see, if you look at the, let's say, sample error, so the stability,  it increases with gamma.  Therefore, I don't know.  No, but I think you need like...  The sample error needs like a smaller step size, so you can only get smaller and do multiple  passes.  Yeah.  We cannot be bigger.  We need to lessen the single pass.  Exactly.  It's gonna be...  Yeah.  Yes, what...  Yes, it's exactly like this.  So we can prove that...  So from our analysis, you can derive that you have convergence for t star and equal one,  and your gamma should be a gamma of n increasing.  Okay?  I don't know if this answers the question.  Okay, so just one last comparison.  There is also gradient descent.  So we know that gradient descent on the empirical risk with early stopping works.  And what I can say is that...  So from the computational point of view, and both from the computational and the statistical  point of view, there is apparently no difference between multiple passes stochastic gradient  and gradient, the full gradient.  So one point to...  This is one point to be understood.  And I have to say that is one point to be understood also in the optimization scenario.  I mean, same coefficient, no, no, but gradient descent is being more garagian, so...  I know.  No, so you can prove that the stopping time is the same.  So if you, let's say, do the mapping, so one epoch equal to one pass is exactly the same.  Same stopping time, same step size.  You can use a constant step size of the batch measure.  You can use a constant step size, I think, for batch mode problems.  Yeah, but it should be smaller.  I think that the Lipschitz constant of the empirical differences, you have the one over  an appearing...  If I'm not mistaken, what you're missing is the capacity dependence.  Yes, for sure.  These one, we are not...  At the moment, we don't have them.  It's insensible if you combine what you did, but M-ray glue to combine and to get  that to...  So on this, what...  So, as I was saying, this is an open problem also in optimization.  It's not clear what is the advantage of an incremental gradient method applied to a sum  of parabolas instead of a gradient method.  But what is known is that...  So empirical observed, at least, and some, let's say, almost theoretically justified,  is that at least when you are far from the minimizer, at the beginning of the iteration,  one pass of incremental is more or less equivalent to one full gradient pass until you do not  enter in this confusion region where you're close to the minimizer, but the minimizers  of your summands are away, so push you away from the true one.  So this would be, again, could be one reason why, empirically, the incremental gradient  has a better performance than the full one.  Okay, so just maybe some idea of the proof.  So just to see a trade-off, a new trade-off.  So we...  I recall you that I consider...  I'm comparing my iteration with the one, the true gradient one.  And so the variance variance trade-off this time is obtained by bounding this quantity  here with the difference between our, let's say, in multiple passes, stochastic gradient  iteration with the gradient on the true risk.  So this quantity here, now, the bias is exactly the optimization error, right?  Because I am applying the gradient method to minimize a function.  Therefore, this is exactly the optimization error.  And here, instead, I have the sampling that comes into play.  And so as I showed you before with the picture, the idea will be to prove that this quantity  is increasing with t, decreasing with n.  And but, yes, and this quantity, instead, of course, is decreasing with t.  Therefore, the idea of the proof is to balance these two terms.  Okay, so I prepared just a few slides to give an idea of the proof.  As I said at the beginning, so I don't forget, all...  As you can see also already from here, the square loss plays a very crucial role because  otherwise I do not have this expression of the iterates.  So the idea is that I can write the iterate at the end of one epoch as a perturbed gradient  descent iteration.  So it's almost a gradient descent with step size gamma, but we have here a perturbation  term.  And so the idea will be to, yes, to compare this with the analog in the continuous setting.  So here I have this operator, it's just this one, covariance operator, second moment.  And okay, this one is an element in H. And then here you have these two quantities that  are quite complex, as you can see.  So that's the point.  And the same you can do for the iteration on the expected risk.  And you get more or less a very similar expression here, very similar A and B.  And so what you do basically is to write the difference between these two iterates by a  sum of an operator which has norm less than one, and so you forget it.  And then you have this sum here where you have always, let's say, an empirical mean  and its expectation.  So you compare the empirical mean with the expectation.  And so basically you can apply a concentration inequality to this.  The only problem is for these two complex terms here, because they are not some of independent  variables, but they are still some of martingales.  And therefore the pinealists concentration inequality still apply.  And then you get a bound of this form, increasing in T, decreasing in N, as I was saying, with  high probability.  Instead the, okay, the approximation error is standard, is well known, and you can prove  that the rate depends on the source condition and on the sum of step size that are constant.  And so the final result is obtained by balancing simply these two terms, and you obtain the  expression that I showed.  Okay, so the contributions, I think that we, so we add some results that are the first  results explaining, trying to explain the generalization properties of some used heuristics  for stochastic gradient, and more specifically multiple passes and early stopping.  And so some future work I already mentioned, therefore some of these mentioned already  Francis.  So I think that's, that's all.  Thank you.  Okay, this is the paper.  Maybe.  So further questions and comments for Silvia, and see more can start if you want.  So there was no notion of randomization within a pattern.  Okay, so these, so we started from the cyclic one, thinking it was the easiest, probably,  I don't know if from the, from the, for the analysis it is the easiest one, but in any  case, so I think that already Lorenzo Rosasco with Junong Lin, tried to generalize these  results both to a non-square loss and to other sampling techniques.  So in particular the stochastic one.  So you visit the time, your points multiple times, but you, you randomly select one.  What is still missing, which would be very interesting, I think is the random reshuffling,  let's say.  Because, because here is, you're saying that my data came from some distribution ID.  Then I have whatever order and I'm just running it through it, and you're saying everything  is, is fine.  Yeah, it works.  It works.  I mean, you're also in the deterministic cases like this, right, in optimization.  But here it's all asymptotic, I guess.  No, the key is that you can do that like full-radiant or the equity risk up to a point where you  start with that error, and this is a T star or N.  I'm just trying to reconcile this kind of result.  With the earlier results we talked about during this workshop where having random permutation  versus random sampling versus.  The random, I think, yeah, the random sampling comes from the fact that you have random,  so your points are ID, and that's it.  So that's like your random permutation.  I think so.  And then after, after this you can, let's say, this is just an optimization procedure  to minimize the, it's not true, but to minimize the empirical risk.  And you can either access to your point, to visit your points randomly, you can visit  your points cyclically, you can choose to visit your points by randomly reshuffling them  after each epoch.  So from the optimization point of view, this last policy seems to be the best one empirically.  There are some results, very recent results, to show that it works also in theory, but  I'm, so I don't know exactly the constants.  So what is known that, at least up to my knowledge, is that the increments in the deterministic  setting, so the incremental choice of the points behaves usually worse than the stochastic  sampling.  But for instance, in the strongly convex case they are the same.  Then there is a recent paper by Guru Bhoot, Zubalaban, Parrillo and Osdaglar.  Yeah, but there the constant is awful.  Yeah, yeah, the constant, yes.  It's a matter of the constants.  Yeah, but still it's linear.  So it's from, let's say, we don't see this effect here.  I don't think, so what could happen, but I don't think so, I don't think so, that you,  if you're optimizing, so if your optimization procedure is better, faster, probably you  can stop earlier, but would expect this more from an accelerated method than from the random.  Yeah, sorry.  Another question for Sylvia?  Yep.  Could you show question people, that's good.  Could you show your convergence rate again?  Again, yeah.  So the best R is the infinity.  Yeah, yeah, but you cannot choose it, so it comes with your problem, right?  So it's a datum of your problem.  So what's the typical value of R?  I don't know.  If the data is IPE, the traditional framework, we have the convergence rate is square root  n, but in your case, your best convergence rate is square root n.  Yeah, be careful, because here we are looking at convergence of the iterates and not of  the error.  So the square root of n that you're talking about is on the error.  Okay.  So in this case, on the error, it would be 2R divided by 2R plus 1, so it should be better  than 1alpha, I hope.  You should compare 1alpha with this.  So when R goes to infinity, this goes to 1 over n.  Okay.  Other questions?  I have a question related to basically, yeah, you talked about regularization, and now like  this approach is not using regularization at all.  So basically, or maybe not, maybe not.  So I basically have two questions, so if I know the value of R, which one is going to  be faster to use early stopping, I mean, or to, I guess, it's only one path.  If you know R, I would suggest to use one path, because it's one path.  But the point is that usually you don't know it, and yes, the regularization comes from  the early stopping, if you want.  It's the idea that is well known in the inverse problems literature, where you, in a sense,  exploit some self-regularizing effect of iterative procedure.  So you can interpret them as regularization procedures, and therefore the early stopping  of iteration allows you to get a form of implicit regularization.  I understand that, could you add some, I mean, the fact of adding some regularization would  make your problem more strongly condensed.  Yeah.  So it would help you to make progress at the beginning, and then is there a way to add  regularization basically, you want to get an easy, then you want to do anything, but I guess.  No, I think it works, so you can add it, you can apply it, you just add.  Also, I think this analysis in the sense, but probably can be refined.  What I fear is that the lambda will depend on R, again.  So you will have something like this, where you're, so that you should then cross-validate  also on this parameter.  So you use a fixed lambda, but maybe you can change that.  So if you use a fixed lambda, I don't know if you go to the, if you are able to approximate  the true solution, I don't think so.  I'm not sure.  No, I meant that you could allow lambda to change with t, and not only with n.  Ah, yes, yes, this is, oh, so, sorry, yes, of course.  I compared my results with, let's say, the results in the online setting where the horizon is known,  because this makes more sense in the sense that we know the horizon, so it would be,  but of course, so here, so all these quantities here are constant with respect to t,  but in the true online scenario, you will have something that varies with t more or less in the same way.  So will be, so will not be constant.  Yes, you could do it, but I guess that will depend again on r, also in this case.  Last question, and when you don't know r, what kind of modellistic procedure would you recommend?  Cross-validation, maybe, because the stopping, so also for the...  Guarantees on...  Yes, yes, yes, you have guarantees.  You can achieve the same rates with cross-validation.  So for this, so for the iterates, you need a balancing principle,  but since the stopping time is the same, both for the risk and the iterates,  you can play a little bit with this and use cross-validation.  So let's thank Cilia again.
Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__0_2531.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__2532_8771.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__8772_12395.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__12396_15419.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__15420_15527.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__15528_20987.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__20988_21047.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__21048_21119.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__21120_21371.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__21372_22163.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__22164_23975.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__23976_24659.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__24660_26711.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__26712_26807.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__26808_27107.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__27108_31151.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__31152_34103.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__34104_35195.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__35196_40139.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__40140_40499.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__40500_40595.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__40596_40715.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__40716_41531.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__41532_43991.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__43992_46919.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__46920_49187.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__49188_51059.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__51060_51359.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__51360_53111.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__53112_53327.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__53328_53783.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__53784_58655.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__58656_62027.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__62028_63347.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__63348_67619.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__67620_71459.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__71460_75167.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__75168_76031.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__76032_76199.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__76200_76295.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__76296_81179.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__81180_84635.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__84636_88163.png Silvia_Villa_-_Generalization_properties_of_multiple_passes_stochastic_gradient_method__1080p_25fps__88164_89124.png