So hello, everyone, so welcome to the first Yasumoto seminar.
So this week, the speaker is to talk to So Radice, assistant professor at the University of Toronto,
the Departments of Computer Science and Statistical Sciences.
He's a faculty member of the Machine Learning Group and the Bacteria Institute, and Seifi chair in Artificial Intelligence before joining Toronto.
He was also at the Microsoft Research New England, where I did his Ph.D.
They teach statistics at Stanford University, a device by Mosin Bayati and Andrea Montana.
So today Mirada will be talking about some new results of our exciting result about convergence
of online stochastic reading designed under infinite noise virus and non-combustible.
Thank you, Jim, for that very kind introduction and thank you all for coming to the talk show today.
I'll talk about convergence of online stochastic gradient descent under some modern set
ups where you may have infinite noise variance or a non complexity in the problem.
So, as you mentioned, I did my Ph.D. in statistics department and back then pretty much every talk started with the following line.
And I'll stick to the tradition and also do the same.
So we considered for this slide the following linear model where why is the response to the is the covariates data?
Zero is the true parameter that we are after. And Epsilon, here is the noise.
So the noise is assumed to have conditional meaning.
And when you're trying to find beta zero, what you do is you write down the population problem and and write this as a minimisation problem.
So minimum of this population risk is a population problem because it's under
expectation of response and the covariance is going to give you the true beta not.
And since this is a minimisation problem, you can write down the stochastic gradient descent updates given as this here Gamma T is your step system.
So it turns out stochastic gradient descent with a proper step size choice will give you the two parameter B to zero.
So of course I did not.
So I left a couple of blank space here.
The reason for that is what happens if you assumed the noise variance is infinity, right?
So the noise may have maybe tails. It's coming from the model and the second moment of the noise is infinity.
Then this objective function is not defined. So this becomes infinity.
But nothing is stop being a practitioner to run SGD in this scenario again, it turns out SAGD still finds the true parameter.
Not so. Some of you may see what's going on here and some of you may be surprised, just like I was.
And I will tell you why this is happening in after I give you some convergence results on SGV.
OK, so throughout this talk, I am interested in the following unconstrained optimisation problem where we are trying to minimise the function F of X,
and its argument is in this dimension and we would like to use stochastic gradient
descent algorithm given as the following recursion and here GMAT is denoting the step.
This is gradient of the function you're trying to minimise and this is state dependent.
So noisy, state dependent, then it is an important component of this algorithm.
So two things that I would like to study in this talk is that in modern settings,
just as I describe in the infinite variations in underlying complexity, how does this algorithm converge and how does the averaging behave?
So I'm not specifying where they converge or how they converge or the type of convergence.
And I'm just saying these are the two things that I would like to study and we will see different notions of convergence and very soon.
OK, and I'll talk more about polygrapher average, why it is interesting.
So this study looks a bit different than the study that we run and run into in machine learning algorithms, but it is actually the same thing.
So consider the stochastic optimisation problem where you have a function f AWEX that can be written as the population risk,
but the population risk and machine learning is the expected loss over a random variable Z.
This is typically your data points YMC together and this expectation is in all the data points so you don't have access to it.
So you resort to a stochastic optimisation algorithm like stochastic gradient descent, the speed that we run in general.
It takes a bunch of data and many batched say it with a bad side.
B is the estimates the gradient of this function F or using the M.H. So B samples,
you just estimate the gradient of F of X, which is a population quantity.
You estimate it using this over this batch of data points.
And what you can do here is to convert this back to our formulation.
You can simply say that the noise is given by the difference between this gradient estimated with the true gradient itself.
So this is the noisy gradient, in other words. And the difference between this noisy gradient with the true gradient is the noise in my studio.
Good.
I would like to emphasise that this is online SAGD, meaning that this is a stream of data coming in and each batch is independent from each other.
So this is not like you have a batch of data points and you subsample a B data points from that.
That's not what we are doing. There is a stream of data coming in and and that's why the title is on minus.
So I am interested in the settings where the noise has infinite variance, noise is heavy tailed.
So the first item is motivated by recent observations.
That study can exhibit heavy tails and in many modern machine learning models.
And the second thing I'm interested in is the objective function is not.
This is also motivated by the fact that many of the objective functions in machine learning is non-com.
And lastly, a practitioner can never take infinite iterations of SAGD.
So in some scenarios,
I would like to characterise these conversions behaviour within an asymptotic analysis so I can quantify how much iterations I need.
Exactly. So these are the three items that I am interested in.
So remember when I said I'm interested in the interest, I'm also interested in the public reppert averaging.
So what is all crap, the averaging? It's a very simple adjustment to the output.
So you run a CD for titrations and you average them out.
That is called Polyakov Upward Averaging. And Polier Interrupted introduced this and different papers around the same time.
It turns out this algorithm has. Good generalisation properties observed numerically, also, you can under classical set ups,
you can prove that this is optimal, achieves Kramer all over, bound under a finite Nigeriens, et cetera.
So it's it's it's it enjoys some nice properties.
And one thing that I am interested in is that it admits a central limit theorem in the classical
setting where the noise variance is finite and and the function you're minimising is strongly complex.
And this is the basis for many inference methods under your algorithm and pretty
much all the inference methods that rely that take the algorithmic part of the.
That take into consideration the algorithmic part of the methodology relies on the CFT,
but what happens to this Keltie if the noise variance is infinity or F is non-com X, and what is the rate of these this CRT?
These are the two things I would like to answer.
OK, so there are many papers on stochastic gradient descent because the method of choice these days to train a model for that reason,
but many of them actually can be considered as kind of follow up to these classical results by in the sky and cross the line, etc.
And I will only compare this talk to the classical results. And I also consider this.
These are the most important papers that kind of led the field.
So the first result is by now where the first paper to consider infinite variance and infinite variance in study.
So what this paper did was in one dimension, the function is assumed to be strongly complex.
So it looks like this and the noise variance has a sorry.
The noise variance is fairly, but the noise has the of moment finite and alpha is less than two and the step
size is T to the minus row decaying step size where row is set to be one.
Now the convergence in LP, the Convergence Rate of Speed LP is given by this expression.
And it turns out that with this rate you cannot show that the public average the convergence of the polio Grubert average.
So the reason for this I'll get to it is that the Stepaside decay is too fast.
Growing equals one.
Is it too fast to that decay to that will not give you at least as far as the proof is concerned, polio be convergence of the polio for the average.
So the the seminal work by Paul Kanjorski was considering the strongly complex set up, and they assume that the noise variance is finite,
Alpha is, too, and they considered a range of steps, such as the case where it is ranging from one 1/2 to one notice.
That equals one is not included here. The reason for that is Roy equals one is too fast and anything below is fine.
And the rate that they consider, I mean, this they relied on previous results to is this much.
And the most important part is that they showed us some tricks, which led to many interesting results.
They show that it's achieved a lower bound to show that.
So they showed, I think, the first asymptotically for the polygrapher.
Babaji and many other papers actually use this idea to construct inference methods based on the fact that they proved.
And in this talk, I will first consider a class of functions that are strongly complex,
but it is a stronger assumption than strong convexity, so strongly convex functions have hachim that live inside of the core.
So let's say this is the speaker. I will consider a set of Q positive, definite matrices.
That is a subset of the sequence. So this is the orange region that you're seeing and I'll explain what this red region is.
Later, I will assume that the noise variances infinity.
So we are in the setting and the step size it satisfies the exponent of the step size is in this range.
So notice that when Alpha is two, you have flying experience and this reduces to the same interval that polio can you diski consider this is
the rate that I obtain and we show that the public averaging actually does not admit a Gaussian Keltie.
It admits the alpha stable limit and it is heavy tail.
It doesn't have a finite variance.
So many of the inference methods that you relied on that you constructed, relying on this asymptotically will not hold in the air.
And in this case. And I will.
As a follow up to this, I'll talk about how we can actually make these asymptotically results not asymptotic,
and prove that this Keltie can be achieved with a raid of this square over tea,
but under the assumption that the third movement of the noise is finite.
So this is a finite this is a nine asymptotically and based on a science method.
And this is the rate is the square oberti.
So this is going to tell us that in practise, these KLZ, especially in high dimension, require too much work.
And I will relax the strong convexity assumptions, which is in the first four items,
I will assume that the strong convexity is contained only in details of the function,
as in the last figure here,
where around the origin you can't you are allowed to have any behaviour and with an assumption that the fourth moment of the noise is finite.
I will show that the asymptotically the Gaussian Keltie still holds.
So these are the three results that I would like to talk to talk about.
And before I give you the results, I'll try to give you some intuition.
And intuition is quite simple and it'll lead to the assumptions that we have.
So assume that you're going to run on this CD and at iteration you are here.
This is the point. You are and an extra is where you want to get at.
So once you have strong complexity, you run gradient descent, you will converge to this point.
It's small enough, so let's consider the one step of the full gradient descent.
This is the full gradient descent. So it takes you from your text and makes it closer texta.
Right. So the distance from X to X killed it, which is the output of gradient descent, non stochastic gradient descent.
Is going to be decreased following this rule.
Right, so there is a constant ah, which is less than one,
so it will multiply the distance from 60 to start and make it distance from X to the T plus one to Exter.
So this is the gradient descent algorithm. And.
In the stochastic gradient descent, you have a noise.
So what it means is that you have the gradient descent plus step size times, some noise.
So this is the stochastic city part and this is where your study is getting you right.
And the. And it turns out that this distance is going to be controlled by the Stepaside because this noise has is multiplied by the steps,
the smaller the step sizes, this noise will be smaller and smaller.
OK. Now I can construct this triangle and right down this triangle, inequality,
basically the distance from the next iteration of SAGD to the optimum is the summit.
It's smaller than the sum of these two edges. And this is the basically triangle inequality.
And what this is telling me is that so this is getting and obtaining this from
the contraction I'm obtaining this due to noise is multiplied by the step size.
OK, so it's a very simple argument, and this leads to the assumption that we we have and it's going to be hopefully intuitive.
So the gradient descent contraction is, as I said, is given by this relationship, this inequality in the case where you have finite noise variance.
The standard analysis continues with setting this distance from 60 to Exter as the expected value.
I mean, this L2 to distance basically the expected value of the squared or so.
And it turns out that the gradient descent iteration satisfies this inequality following the standard analysis.
So all I need to show is that I need to show this guy, which is the R here is less than one.
So remember, I'm going to let the step size go to zero because I need to decrease the step size in this part of the talk.
So this means that for a four, Gama'a, that is small enough, this quantity has to be smaller than one.
In other words, I'm just going to say that for small enough gammer, there is a L such that this inequality is satisfied.
Now, this is exactly equivalent to saying that F is strongly comeback's or Heshan of F is uniformly positive, definite.
These two statements are equivalent. OK, so this was the standard speed analysis and it turns out strong convexity is giving us nice results.
But in the infinite noise variance setting, you see, I cannot use the second moment here.
So what I need to use is the moment where P is smaller than to.
And for that reason, I'm going to choose my distance and this is not a metric, but so this distance as the expected value of the.
Peace, power of the peace, no, of this distance, if this is my new distance metric,
then the recursion I wrote for the second in the in the finite notes variance case, I can write it equivalently as this and.
With the same strategy, I need to make this first term here, which is going to be giving me to dictate smaller than one so that I have a contraction.
OK, and. The equivalent, the expression is this, So I need to have this power of the peace no less than or equal to one minus Gamma.
And it turns out, just as this was equivalent to the uniform positive definiteness, this will also imply some sort of positive definiteness.
But it's going to be stronger than the standard notion of positive definiteness that we all are familiar with.
So this is the idea. I need a contraction in some distance.
Second, so if the distance is the Euclidean distance squared, that gives me strong complexity,
if it is the norm, it will give me it will require something stronger.
That is the idea, so let's recap some of the results where we have in the standard.
Standard classical set up so. As I mentioned, this inequality, basically this matrix, having this operator, Naum Square,
being less than equal to one minus gamma four for all small gamma is equivalent to F being strong economics,
which is saying that the Heshan is lower bonded.
Right, and so this means that this implies that the set of mattresses, the federal mattresses that are over this set,
basically the question of the function you're trying to minimise is a subset of the equation which is represented as this coin and figure on the left.
So it's symmetric Matrix two is positive, definite if the normal V is one, we have this inequality,
which is a strict inequality is this quadratic form is greater than zero all the time for all V on this unit,
Saffir and two is positive, semi definite if this inequality is not strict.
Right, and instead of the mattresses defines a count. So this is that cone.
Now let's go to the pinata. So this was to Norm here, right?
Let's go to the Pinault and see what happens to get the contraction in the arm.
I need this inequality for Gammer in this range.
Now, before showing you the equivalence, I need a definition.
I need sign power or a vector.
So given a vector like this and some positive or Q greater than equal to zero, the same power of a vector is defined by this quantity.
So I have the sign of each entry and taking the absolute value and raising to the public.
So you can say, OK, let's let me give you the definition and then I'll show you the figure and how they look like.
So a symmetric matrix cue is positive, definite, if for all we on the units to fear but fear and Piñera satisfy this strict inequality.
And it is positive, semi definite, if this strict inequality becomes non strict and said of all the mattresses are also defined.
And here is how the picture looked like when P is equal to this definition here.
Exactly. Reduces to the cone.
So vampyres equal to two.
You have the cone that is the blue region here, and this definition reduces the standard definition and then P is equal to one.
Then this definition reduces to the set of all diagonal dominant matrices that have positive entries.
And that is also a cone. That is this red region here.
And any party that is in between one half, you still get a cone, but that is in between these two these two cases, then equal to one and two.
So there is this inclusion relationship between these cones and.
And it is important that this war and peace and peace in between one and two discon lives in these two two columns
of background dominant in East Coast and the cone of diagonally dominant mattresses is the most extreme case.
So if you make this assumption, then any of our assumptions are already satisfied.
I'll get I'll talk about this a bit further. Let me give you the two assumptions that I need for the convergence of SAGD and the heavy tailed Riggi.
So I will assume that the set of matrices, basically these Heshan matrices, are bounded and uniformly positive, definite.
So when you see in this region, so when you see a few positive definiteness assumption, so is referring to this.
Uniformly on the set of all sessions and here equal to Q so this is my first
assumption on the function and I will assume that the noise admits the following,
the composition. So noise itself is state dependent and there is a state dependent component and a state independent component,
by state I mean the 60 and the state independent components are eyed with expectation
zero and has the finite of US moment for some of our less than or equal to two.
Two is also fine. And this state dependent component is a martingale different sequence.
And this martingale different sequence satisfies this inequality.
So this means that the the variance of the state dependent component can be large.
But for a fixed X or for a given X T, it is always finite, whereas the heavy tail part comes from the side component.
So this is the noise assumption that I make in the heavy tails, heavy tail case,
so we have this very recent result saying that if you have a step size satisfying
this decaying like this to my nostril and this row is in between zero and one,
the air of the city in Kunar to normal to the power kyuzo here,
to the subscripts to that's why we limited to naum to the power you is given by this expression and that is its decay rate.
So this is the convergence rate that we achieve in the case of heavy tailed mouse.
For the less illiterate of GD to minimise their unique minimisation of the problem.
OK, so what is this rate about? Remember, we have a stat size decaying with teeth minus Joe.
And we have a noise that has finite of us moment for hopefully some of that is smaller than two and we have a HESHBON that is too positive,
definite, and this is a stronger assumption that than a plain positive definiteness, which is equivalent to strong convexity.
Right. So this rate. Is basically giving me when Q is going to Alpha,
so you see the assumption on the function and the assumption on the noise are connected to has to be always less than Alpha.
But being curious, going to Alpha in this regime, you achieved this great.
OK, and when role is going to one which is the fastest dictate that you can have on the step size, that gets you to the fastest convergence rate.
This is the rate of Gasolina. Sixty nine.
But this is too fast for the convergence of polygraphers average.
So this will not this case will not work if our objective is to show the convergence of politics upward averaging.
So when offer is going to two, meaning that your noise is now having finite variance.
Then the rate that you achieve is this much, and in this case now you can actually move to the all the way to the two.
So you have the strongly complex functions. And in this case, you recover the normal rate T to the minus trover to for finite variance.
But this is the finite variance regime and this is the infinite variance regime.
And this rate is not good for us because I want to show the convergence of the political upward averaging.
That's too fast for that. So remember, the gradient noise was given by this edness, this decomposition.
So what I will additionally issue to the previous case is that I'll assume that this average of the IED component admits that of a stable,
symmetric of a stable limit.
And so standard generalised Keltie results actually has certain conditions to be satisfied in one result is due to climate in a Danco.
And if the random variables with power to tails symmetric random variables with power little tails, then you have the following satisfied.
So a stable distribution, this alpha stable limit assumption allows me to characterise the limiting behaviour of the Polya corrupted averaging.
So I'll talk about alpha stable limits in the next slide.
But the result is as follows. If the Roka and Alpha satisfied satisfy this inequality and this additional smoothness assumption.
So you can think of this assumption as the Heshan smoothness. Then,
for a Stepaside sequence satisfying the standard indicate the normalised average
pull Robert averaging Convergys weekly to an alpha stable distribution.
So here, the first observation is that the staff size the index of the staff size the role.
It has to be in this regime and in politics and you just keep this within this regime, when Alpha goes to two,
when you have finite experience these to match, but when Alpha is smaller than two, we have a smaller interval here to work with.
So offer stable distributions. So here is a figure that I took from Wikipedia and I forgot to acknowledge in the slide.
And so this is the PDF of our first table distribution and this is the parameter alpha.
So the variance of this limit is infinity. So there is no variance when Alpha is smaller than two.
So you won't have a Gaussian Keltie when Alpha is smaller than two.
And when Alpha is to this recovers the standard asymptotically results of and she did Saeki is because of a stable one of equals two is Gaussian.
And. Real, as with pretty much all results on Polier Crawford,
averaging this proof of this theorem relies on the construction first made by Pollack and you to see the seminal work.
And it's just that we we analyse this algorithm in the heavy tail setting.
That is the novelty. So at one point that I would like to make is that when Alpha is less than two, there is no Girl Cincotti.
So the inference methods that are constructed for the uncertainty.
Quantifying the uncertainty of SGV, for example,
is not going to be valid because they are all based on this Gaussian Keltie assumption of the polio Chrebet averaging.
So a lot of those methods has to be rethought in the in the case where you have heavy tail noise in the studio gaud.
So, one, before I moved to Non-Com Back City and the final result,
understand convexity is a result that you obtain twenty nineteen as a product of the science method workshop in San Jose.
So here we actually characterised how fast you're converging to Gaussian in the case where you have a finite variance.
Actually, we assume that this third movement of the noise exists. Then you can characterise how fast you're converging to Gaussian with this theorem.
So what this theorem is saying is for any test function that is three times differentiable, you can show that this expectation,
the difference between the test function value to the polygraph or the averaging and Gaussian is upper bounded by this quantity.
So the proof relies on and not asymptotic martingale Keltie using Stine's method.
But one thing that I would like to emphasise is that this rate here is not a good rate.
It is because these squared divided by squared of the number of iterations and this is the dimension that you have in the high dimensions.
To make this no small, you need to take way too many iterations.
It's not a good rate, but it is still consistent with the experiments. A lot of these methodology like inference methodology that rely on this,
Keltie actually realised, requires a small dimension, plus a lot of iterations of the.
And so this is consistent with what we observed in practise, it's also as a side note,
burning helps a lot in these kind of stuff, but I don't have any theoretical quantification of that.
So back to the least squares example that I started to talk with, so we considered this linear model, right?
And Epsilon, the epsilon, the noise had infinite variance.
Now, without defining the objective function, you can directly define the gradient of it.
So what does this mean? This is a bit cheating, but I can actually choose a function of X,
and instead of writing this as a minimisation problem, I can write this as a finding the zero of a function.
Right. And if I define this, the zero of the function is going to be below zero.
Right. And that's basically where the minimum will be 18.
So George has a question in the right result was the absolute value inside the expectation.
Site. Hmm.
Good point, that is inside the expectation. I just verified it.
By looking at the paper, so it should be inside the expectation, but I can I can double check.
OK, so. And the least squares set up the beat of zero is the unique minimum of this multi dimensional function,
and Exter is going to be the start that the zero of this function is going to be to be to not be quite straightforward to see this.
So the study updates, you can write it as a stochastic approximation algorithm and is given by this quantity.
So the noise part is going to be just as we did for the in the second slider.
So the noise I can write it as it has.
It admits that the composition where the IED component is given by this quantity and the state dependent component is given by this quantity.
So here the state is X, right? You see the IED component does not have the state in it.
So one can verify if you assume that the first moment of the noise is finite,
then the first moment of the IED component is finite and the state dependent
component trivially satisfies this upper bound if we assume the covariates are nice.
Right. So this basically is telling us that the assumption to the noise assumption will be easily satisfied.
And for the function, the direction of the function, we have this expected value of the transfer,
covariance of the covariance, covariance of the features.
So you can assume this matrix is diagonally dominant and all the assumptions are satisfied.
Like the Stupples, the definiteness is satisfied, but the cumulative definiteness is a milder assumption than diagonal.
So you can actually assume this from the covariance matrix.
Then you actually have the convergence results can be invoked for this case.
OK, so now I will talk about non convexity and and what happens in this case and in the case of non convexity and non smoothness,
basically assuming that your objective function is non convex and lossiemouth at the same time.
The problem is a bit harder to handle.
So we will consider in this case and EGD with a constant step size so that we can actually rely on the convergence Markov chain convergence results.
And this methodology is actually the constant analysis of constant stepaside size is first derived by these people in 2019,
delivered in 2019, and but the analysis was under strong complexity.
And so it turns out that these are not needed assumptions and you can relax those pronouncements and come complex objectives.
But the key point here is that I have a Gama'a that is websites that is constant.
So this has to be Gammer. It's a typo. So the assumption, the first assumption, instead of the smoothness assumption.
I make is that the gradient of F the objective function is growing at most linearly.
So this is the first assumption.
The second assumption I make is that the instead of strong complexity, the function satisfies a discipline assumption.
So this opportunity is given by this inequality and this is satisfied for all X.
So what does this assumption tell me and how does it reflect strong convexity is here.
It basically says the strong convexity is a global curvature assumption, whereas this opportunity is restricting the strong convexity to the tails.
So anything above you have the quadratic growth of F and around the origin you can have none complexity.
So that is that assumption and it's quite common in not convex optimisation analysis.
So in this case, the noise sequence is assumed to have finite fourth moment and additionally,
I assume that its density has full support so so that I have a nice Markov chain defined by the L word.
And the key point is that noise is still state dependent,
so I can write the standard email SCD in this form, but it has a finite variance given X, given the state.
OK, so now I used Oxford comma in the title so you can tell me if I use it correctly or not,
but yeah, so in this case, the noise is state dependent and that's fine at variance, but not.
So given these standard Markov chain results can tell us the area of the city of SAGD,
so for a small enough staff size the DEA to admit a unique stationary distribution and this distribution,
although we cannot characterise it, we can show its existence and uniqueness.
And it depends on the step size. And also for a test function, it satisfies this convergence to the stationary distribution,
not to any of the minima, it's just to the stationary distribution.
The convergence is geometric, but it's not directly comparable to the previous convergence results that we talked about.
And so what happens to the public or averaging non-com excuse now heavy tailed kids?
It doesn't satisfy Ghastliness TLT, but it turns out that in the non-com excuse.
There is a Gulf society, so now I will define the average of the city's interests are evaluated at a test function by and I
will define the average display and the expectation under the invariant measure is defined this way.
So this means that the Poljac report averaging where they evaluated a test function,
is going to admit a central limit theorem given by the expression here.
So this is cool. The Keltie is still valid under non complexity.
And but we we have to talk about the bias of this algorithm in order to in order to come up with something useful.
So what do I mean by bias? How does this compare to any of the critical points or the global M.O., the minima of this non complex function?
So if without making any local regularity, so we if you don't assume anything further than just discipline,
every assumption, this is not possible and all we can hope for is that the SGD algorithm will satisfy this inequality.
And this is a constant that is an old one. So by letting step size small, you're not getting any improvement here.
So SAGD converges to a ball that contains all the critical points in this convergence is exponentially fast,
but bias is not controllable with the step size. Bias to the extreme.
OK, so for that reason, I need to enforce a local regularity on top of the the growth assumption that was anticipated.
So this is the previous disciplinary,
I assume this outside of a board and now I assume inside of a bowl there is a local regularity defined by this convex function.
That is incredible. And zero zero zero.
Right. So this is the additional local irregularity and then under this additional localised, this Aparecida assumption,
I can show that the was admitted a stationary distribution and the bias of this distribution,
stationary distribution of the study is now controllable by the step website.
So if I let Gamma to zero, the right hand side here also converges to zero.
And for a test function that is Lipshitz, you can just take this and then show that the expectation under the invariant measure,
minus the test function evaluated at the minimum, is going to be upper bound by this quantity, which goes to zero when Gamma goes to zero.
And so here is a non Carmex function that is called Blake's Esterman Emily, that I found in, I think, visual reconstruction book.
So this assumption, these this function actually turns out satisfies the assumptions of these theorems.
And you can actually verify that it has a cult.
And also this is by experiments is also correct.
So our results also match with the numerical studies and in the numerical studies we use this test function, which is the absolute value.
And in the paper, we also verified it rigorously that these assumptions of our theorems are satisfied.
So. I'm out of time, so I'll conclude and with the summary of what I told you today.
So basically this is the convergence analysis of attitude and the politics upward averaging.
Right. So that's what we talked about, the infinite noise variance case.
We showed the LP Convergence of SAGD and we identified a regime that size decay.
So I that the polio growth rate averaging admits an awful stable limit and negotiate non Gaussian limit and understand complexity.
We talked about it on asymptotically rate due to Y signs LAMBA and under non complexity.
We show that Polier support averaging admits the CLT and its bias can be characterised if we have additional low cost structure.
So that's it from me today. And if you have questions I would be happy to answer.
OK, so thank you very much for very nice talk. So is there any question from the audience you can just amuse yourself and ask?
Yeah, I've got a question. Well, I really enjoyed your talk, and you probably guess what my question is, is about.
So you say you cannot ever run at the stuff that the gradient descent infinitely long.
Mm hmm. So do you have these results with Andrius for the Central Limit Theorem?
But can you use results also for a stable distribution using Stintz method in order to get an exclusive count?
Yes. So that's a great question. And I think you had a recent paper on our first table limits and sties method.
So it's definitely doable. It's just that it's a matter of doing it.
So, yes, that's a good point. OK, good, Senator. Yes, a very interesting direction.
Like basically, how does this discredited basket of trade change when you don't have a girlfriend sensibility, but you have all of those people?
So that's a very interesting direction to explore. OK, yeah.
Can I ask a question? Actually, it's sort of a double question, so, um, what's the motivation behind the Policy Act, Rupert averaging?
Yeah. Another great question.
So the poll Rupert averaging is so in the classical setting, it achieved the Krimmer all over Bonte, whereas the Lessiter iDesk does not.
So now to the and other interesting research directions.
How to what is that like the bond on lower bond on the variance.
What does that translate to in the end, the heavy tail setting when there is no beating us?
So what kind of optimality can one prove for political operative, right?
OK, so is there does anyone ever consider, like, different types of averaging?
Yes, I think that is also common.
And I don't think the analysis is very hard given like a specific weighting between the iterates, but we haven't done that in any of our results.
OK, OK, great, thanks. And to go back to my previous question about the absolute value.
And so the reason I'm asking is because if you put the absolute value inside the expectation,
then it sort of requires that you build some kind of coupling between the limiting Gaussian and your process.
So it usually requires heavier machinery and potentially the red can be worse.
So if you take the absolute value outside of the expectation, maybe the rate can improve.
Hmm, that's interesting point. So. And usually the absolute value is outside, I think I think you're you're right,
I think the absolute value should be outside because I'm checking the martingale Keltie that we proved in the paper.
And it appears that it's outside of the expectation. OK, OK.
Because otherwise you need to do like some kind of, like, strong central element, you know.
You're right. Yeah. Yeah. No, this is relying on like basically.
Like similar construction by rainout, drilling. So it should be outside, I guess.
Yeah, yeah, yeah. We always have the outside. Yeah. I had a quick question.
Yeah, go ahead.
So the assumption on the experiences of the Cotard's, so you said that in the case of P equals one, it's aligned to the diagonal dominant.
So is there like an intuition on what kind of how that changes the covariance structure in the case of linear regression?
So is going to be more aligned to that identity as the candidates have to be more independent or something like this.
So you have the covariates, expected value of.
These transports, right? So these are your covariates and this is a kind of a signal and that is like if this sigma satisfies.
Diagonal dominance, then this assumption is satisfied because then you are in this red regime, and that is going to satisfy any people.
The assumption. So this only means that like this covariance, I mean, for example, if you have white covariance, then this is identity, right?
So it's going to be satisfied, for example. Does that answer your question or did I miss it part of your question?
So in some sense,
is it saying is the assumption saying that the court does have to be more independent as P increases are equal to it will always be satisfied.
But then I think as it moved towards Dinotopia and just say that the variance has to be closer to an identity in some sense.
Yeah, so I think so. This is what I want.
Right. So Viji G is not a.
So I think that can be interpreted this way.
I just wondered whether that sort of in between in the case of people wanting to so, so close to little.
Certainly like this is a weaker assumption than the diagonal dominance, and this is also just to clarify, this is not really diagonal dominance.
This is diagonal dominance with non-negative diagonal entries.
And in this case, so this is the assumption that you have and I think you can interpret this as like the
correlation between the features are weaker compared to the compared to the strong,
stronger case. Another question from the audience.
Yeah, I see the question, I guess for the latter part of the talk, the constant subsides down capacity.
So if it's a mini batch instead of last year, can we still prove could with some stronger assumption to prove the central premise here?
You can't prove you can't use minibike SCD. But, um, so let me go back to this slide.
So this is still valid. Like you can have gamma T plus one equals gamma constant step size, but you can have many batched.
But this is stream of data, so it's not like you have a batch of data that you resample.
And so you should be doing these mini batches should be coming in as like new data points.
That's what I meant. So if that is the case, you can do it. But everything here in this talk is on line.
OK. For the for the U.S., there is a stationary distribution for them, but do you have any type of convergence results?
Sort of. You mentioned it. So convergence to the invariant measure.
Yeah. So convergence to so the standard are good to see the type of stuff is like easy to prove using Markov chain machinery like this one.
Right. So this is the convergence that I briefly talked about.
So this is quite standard. But the important point is like this.
This is easy. But what is hard is this guy like how do you actually characterise anything about this invariant measure is the biggest challenge.
That's not. Yeah, I see what you mean. So but I guess my question is so in practise, when you run algorithms like this, do you ever have convergence?
You mean variance distribution or do people just run it for much shorter time scale so that
you may only ever see you're still close to initialisation or the part of the environment,
as you explore, is heavily influenced by your initialisation? Mm hmm.
Mm hmm. So that's a good point.
And so what you're saying is, OK, this is not what this is not answering your question,
because this is true for any initialisation you're getting the same result.
So what you're saying is if the stationary distribution depends on the or like.
Yeah, it could depend on the initialisation as well. Well, that's not quite what I'm saying is.
So obviously this are there the rate is sort of I'm not sure if you've quantified it.
You could you can you can verify this are.
I mean, I think we stop that saying our is less than one and greater than zero, but this is kind of like I think you can you can compute it, but.
Yeah, but what I'm saying. OK, so let me rephrase.
So I'm not sure how you proving this, but if you're doing it using Dreft and, you know, functions and things like that,
it's very likely that this hour will be very, very bad in terms of the dimensioned dependence.
Yes. So if you do that in practise, if you plug that in and you say, OK, so I've run my algorithm for,
let's say capital case, that's how close our mind to the environment distribution.
What I'm saying is so obviously this gives you a mixing time.
So does the mixing time compared to practical runtime.
Some of these algorithms will raise it at a different and a completely different time scale so that you'll never, ever see the environ distribution.
So that's a good point. So this proposition is used in this theorem, which is asymptotic.
So we actually never required are to be something nice as long as it's less than one.
We were good.
So we didn't explore anything that like what happens in the finite sample regime because our objective was this Keltie and which is asymptotic.
But that's a that's an interesting thing to think about, actually.
In your experience, what do you think? So I can show you I mean, I knew I wasn't going to have time, so that's why I.
covid. Yeah, OK, so I actually had experiments that I took it out of the talk, but so.
It's. So what people observe is like when is larger than 20, you have to run for a very long time to see any of these results, actually.
This asymptotic ski resort that is in line with this not asymptotic version of the CFT.
So it's like if the raid is discovered, I'm scared of the squirrel, we're scared of tea, then you expect to run forever.
It is like large, right? So and what we observed is similar.
The experiments you can verify staff and these like 20 fifty.
But anything beyond that is hard. Right.
OK, thanks. OK, I guess we have a run run out of time, so let's add some in there for today.
So thank you, everyone, for coming in. Let's listen to the speaker again.
Have a nice weekend. Thank you for spending.