Skip to main content
Loading Explore guides…
Data dump tutorial · Acedra
Home
Explore
Computer Science
Data dump tutorial
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
231 segments
Copy
Hide video
0:00
[SEAN MEYN] Yeah. Oh, Yeah, Yeah, It's raise time. Okay. So Yeah, I know it's a big data dump for all of you.
0:11
Let me just close this down.
0:14
So it's a totally different sort of flavor in a way. Um, so it's really strange, you know, I guess this always happens, you know, so because I was thinking about this for a long time starting in January I've been sort of trying to think about how to present all this stuff to real newcomers, you know, so no, so no mark off stuff, keep things simple, sine waves instead of noise. And instead of trying to prepare this, I had a really cool discovery in the last six weeks.
0:45
So this wasn't supposed to be research seminar. This is supposed to be a tutorial.
0:51
So that's why you'll see an emergency exit sign. If-- if I'm going too far, I'll just flip slides, skip some slides, and I won't give the details. But there's something in here I'm super excited about and then I'm gonna give more applications. So the first hour is gonna be sort of some general theory with applications at all, and the second one will be more applications and history-oriented, and a full history of actor-critics since 1968. Okay so first of all, you know, I--
1:25
I've been talking about stochastic approximation. I want to define it. I'll do that in one slide. I want to explain to you what I mean by quasi-stochastic approximation. I've already said it, I'm replacing noise by-- by quasi-random numbers like sine waves. Um, and I've learned over the last four months that the area of quasi-Monte Carlo is so damned hard. It is so deep and so difficult, I'm not gonna touch that theory. I'll talk about sine waves, just to make it easy.
1:53
And I'm gonna explain how you apply this to grading for your optimization, and just, so I'll be getting closer to actor-critic methods, all right? And I'll show some examples. And then this is the thing I'm really excited about, but I think it may be too much. So Aditya says, "Sean, it's too much." We'll see, okay?
2:12
I'll give you the result. I might not give you the proof.
2:16
All right, so a lot of-- I mean, so the paper I mentioned with Prashant on LP methods for Q-learning
2:27
that goes back, you know, quite a ways. When I was at N-- uh, NREL two years ago I got a big-- I had just some fantastic interaction with people there, you know, including Andrei, who you'll-- You'll hear from at the end of today, Marcello, who's gone back to ETH, who's at ETH, and Emiliano, who's at Boulder, Colorado. And sorry for the crappy photograph. Uh, that's Yueqin during his graduation several years ago. He's at NREL now. And that's Yuang Chen, who is in the math department here.
2:59
He'll be graduating, by the way. This guy is awesome. He'll be graduating next year. So, keep your eyes open.
3:09
So stochastic approximation, my caricature is this, you know, throw in a bunch of noise. In stochastic, in Q-- in reinforcement learning, it's often excitation or exploration and you get some estimates of some parameter theta n, which determines your Q function, your policy or something like that. And this is going back to Eric's comment that asymptotic statistics are useful. Um, you know, basically, Aditya's thesis, a lot of it was about using a central limit theorem which
3:44
is an asymptotic concept, a stochastic approximation for algorithm design, and it was very successful for the algorithms he was looking at. It's not--doesn't always work, but it did in his case. All right, so the goal is that every single problem we've talked about is a root finding problem, you know? We wanna find a solution f bar of theta star equals zero, where the f bar is a function of a parameter theta and something random that comes from nature or on exploration signals or whatever.
4:22
So that's what stochastic approximation is, and-- and just like Eric, I have a million different symbols for the same thing. I've, Theta, I've got a little squiggly theta, I've got a big theta, I've got so many thetas it's insane It's just, there aren't enough symbols in the world. Um, but so this is what I mean, Csaba, about it being backwards. Why did Robinson and Rowe present an algorithm, and then, I don't know, not make it clear that the entire algorithm was this?
4:59
The whole algorithm was, we would like an ODE to solve this root finding problem, right? Maybe we've designed the root finding problem so this ODE is stable, and then let's use an Euler scheme to approximate that. I-- I'm s-- more talking about pedagogy. I don't know why it's always flipped around, that we present an algorithm And then we analyze it. So often the ODE comes first.
5:27
But it's not just pedagogy, you'll see. Um, so again, you would do an Euler approximation if you could, right?
5:37
It involves an expectation that's too complex, and so what you do is you replace the f bar, which is too complex to compute, with the observations, all right?
5:52
That's the-- that's the definition of stochastic approximation, and-- and basically the idea is you can write this down as exactly this but with noise,
6:08
and so all of the convergence there of stochastic approximation is to say that, um-- Oh, I should have waited, that Euler approximations are robust.
6:20
That's convergence theory of stochastic approximation, and it is robust and it takes a bit of muscle to prove that robustness, but that's it. That's what stochastic approximation is. So I don't know why it's made out to be so mysterious. It's really funny, and I think that it's a disservice because it's a very beautiful and powerful technique, and it's a shame that it intimidates people so much. But that's it. You have an ODE you'd like to approximate, you can't do Euler,
6:50
so you basically would do noisy Euler approximation
6:55
and the thing is that Euler approximations are robust, and the mathematical tool you should use to prove that are the same you use to prove that this is convergent. The theory is identical.
7:17
Identical. You know-- Well, --I know that, I know there's a bit of Martingale stuff in there, but those, that's just properties of the disturbance.
7:27
You know? You know, there's Bellman-Gronwall. There's how much noise is there and Bellman-Gronwall done. Here, the noise is because you're discretizing an ODE.
7:40
[CSABA SZEPESVARI] Is it a more precise way of saying that these are identical or the theory for this? [SEAN MEYN] Oh, the theory's Bellman-Gronwall is the key [CSABA SZEPESVARI] Step. Okay.
7:53
[SEAN MEYN] Yeah. Tell him. So basically to prove existence to the ODE,
8:00
Bellman-Gronwall, you know? To prove that this thing approximates this thing Bellman-Gronwall. And here dealing with the noise, you get an error term Bellman-Gronwall. So, you know, and so that's why if you look at Vivek Kar's book, he knocks off convergence just in a, you know, very quickly in a paragraph, you know, one subsection and then moves on. So the convergence theory is not deep. It just took a lot of brilliant people to come up with the right way of setting up the problem for analysis.
8:30
And now that it's so well done, it's really easy to understand convergence theory. Now, grades of convergence theory is still deep and difficult. Um, and when, when this function is nasty, if it's not Lipschitz or something, then that, that's when you get use literature like work of Ben Ami and stuff. You can see references in the, at the end. Okay? Now that's convergence theory. Um
8:57
so again, see Vivek's monograph. Now oh yeah I didn't-- I thought I had a slide, but again, rates of convergence, variance, all that stuff, that's when the statistics really comes in and then things really get harder.
9:12
Now let me work towards it closer to convince you that this is how the ODE method should be defined, is that first you design the dynamics so that theta T converges to the desired theta star. You have to decide what your theta star should be, your metric should be. And so therefore this convergence holds as well. So this is a control problem, right?
9:52
We're trying to make theta T, the state variable, converge to a desired equilibrium, theta star. It's a control problem, but there's no physics. We are unbound by nature or any kind of laws. We can do whatever we want. So for example, here's something crazy.
10:11
Let's forget about thinking of theta T as a variable.
10:16
You know, why not think of F bar Theta T as a variable?
10:20
You know? This would say that F bar of Theta T is this equal to F bar of Theta 0 times E to the minus T. Happy face, right?
10:35
Yeah, we can do whatever we want. Now this is going to end up being complex because when you do the chain rule, you'll get a matrix gain algorithm. But that's one way now we know how you derive Zapier learning. And it's called the Newton-Raphson flow now. That's-- that's what, I mean, Smale, this is from Sma-- Uh, Smale back in the '70s.
10:55
Well, I-- I'm just trying to get at, we have so much freedom in designing the ODE, and then we have to talk to a numerical analyst perhaps to find out the most efficient way to approximate it.
11:06
And they might re-- w-- they might suggest some Runge-Kutta method instead of a Lagrange, all right?
11:13
All right.
11:15
So this is one example where the ODE design, you'd never find this in the discrete world. You'd only find it by thinking of ODEs.
11:30
Okay. So I'm pulling you a little to my side. Now of course, I'm not saying it's the only way to do things, but I-- I'm saying that, that this is an example where the ODE gives you great insight in how to design an algorithm, you know, the translations-- I think there are, [CSABA SZEPESVARI] Yeah. So in this problem definition what is hidden is that very often, you have constraints on what you're observing, so it's true that you want to control theta in some way,
11:56
and then there are some constraints on what you are observing, and then you have to cook with that. Yes. And some such things such that you get on one hand stability, and on the other hand, you're only working with things that you can observe. So the way you're writing, these two things match up, but if I'm thinking about just TD learning or, or something like that, there are a million ways of constructing these things And you know, you can change various things. Uh-- [SEAN MEYN] Yeah, yeah.
12:28
That's right. Well, if your objective-- If you've identified an objective, which is F bar theta star equals zero, right?
12:37
You know, if that's your goal, right? Then you have a control problem. And you-- And to solve that control problem, you know, you wanna design a stable ODE, you know. As I said, that's a control problem.
12:52
That's what I mean. So if you, if you've been given a goal written as an expectation, you know, then you wanna think really hard about ODE design.
13:03
[CSABA SZEPESVARI] Yeah. I totally agree. I'm just making a note that there is some observer Yeah. --process also going on here. [SEAN MEYN] Observer, but that's what I-- That's why I highlighted this. I mean, right there. [CSABA SZEPESVARI] Yeah. [SEAN MEYN] You know? [CSABA SZEPESVARI] Right. [SEAN MEYN] We're assuming that-- We are assuming we have-- [CSABA SZEPESVARI] Sometimes it's not so simple that you observe. --something that observes that. Yeah. But sometimes that's not so simple.
13:23
[SEAN MEYN] Yeah. Okay. [CSABA SZEPESVARI] Anyways. [SEAN MEYN] Yeah. Oh no. I'm not, I'm not saying this is the only way to think about things. Please please please. I-- You know, I'm k-- I'm kind of object-- I just think that Leonard Young made a big mistake way back when. I think it would be much prettier teaching this to spend a lot more time on ODEs, understand the stability properties and then say, "Hey, there's numerical methods to approximate," and, "Hey, there's even numerical
13:48
methods when you don't observe the functions." It's just peda-- I'm thinking more pedagogy than anything. [CSABA SZEPESVARI] Yeah.
13:55
Putting up a theorist hat the natural question to ask is whether if you're thinking in terms of designs that can come out from this, is this going to be limited in some way? Are we ruling out any discrete time algorithms right? Yeah, [SEAN MEYN] Absolutely. We're Absolutely. All the batch algorithms I talked about in lecture two, you know, no way, you know.
14:24
Then you have to go backwards, you know. You design the linear program, and then you can prove convergence through an ODE. That's a case where Leonard Young is absolutely right, you know. But then-- I have to start with that algorithm. [CSABA SZEPESVARI] Yeah. But the real question is whether we're losing anything in terms of. Yeah.
14:40
[SEAN MEYN] Well, there's example where we are. Right. Yeah. Yeah. The other yeah, yes, for examples where we are, where you, where this is not, is too restrictive. Absolutely. [CSABA SZEPESVARI] Okay. [SEAN MEYN] Okay, so-- Uh, it would be good to, to see some-- And that's okay. That's okay. It's not the only [CSABA SZEPESVARI] Way. Yeah. Okay. [SEAN MEYN] Yeah. But again, but let me just say it again to everybody, you would never get my previous talk from ODE methods.
15:02
You really need to think discrete and then use the ODE method as it's usually defined for stability.
15:12
Okay. Now, the next thing is you can start looking at gain selection, and there's some really pretty theory there. So if you take a gain which is-- uh, a step size which is some constant times N plus one, then you can get this optimal one over N convergence rate for the mean square error, but only if this matrix is Hurwitz where A star is a linearization, assuming it's, it's smooth at the equilibrium which is a sad fact. That's a sad face.
15:51
So you need g big enough.
15:59
Yeah. Just [CSABA SZEPESVARI] For clarification, Hurwitz means the eigenvalues lie-- Oh yeah. --in the left open plane. [SEAN MEYN] Yeah, thank you. [CSABA SZEPESVARI] Some people sometimes flip these things but-- [SEAN MEYN] I know, sorry. Yeah. So Yeah, So I mean, Yeah, it means all the eigenvalues are over here in the left half [CSABA SZEPESVARI] Plane.
16:21
[SEAN MEYN] Yeah. Yeah, thank you, thank you, thank you. I forgot to mention that. So the yeah. Yeah, so they basically, the linearization is asymptotically stable at the-- And so that's a sad fact, you know?
16:39
And the, those ZAP things I mentioned was a way to deal with them and to get optimal convergence rate, I mean, to optimize the constant, okay?
16:49
And when that happens, you actually have a formula, and again, I don't-- I don't wanna keep on hearkening back to to Eric, but I just think it's nice to get somebody else to say it, asymptotic statistics can be valuable. Um, and I'm not gonna, I don't have time to show you plots, but the CLT is sometimes very, very rapid to converge, and so you can get really good insight on rates of convergence in the asymptotic statistics. And isn't it amazing that only linearizations are
17:17
enough to tell you about the optimal rate of convergence? You don't need to know the covariance of the noise to know if the rate of convergence is optimal, you know? It's all about sort of, you know, very, very, you know, really simple concepts. So it's, I love this stuff. But I can give you examples, not today, but where it does fail, where the CLT is worthless. I can give examples, numerical examples.
17:49
All right, so there it is. You know everything about stochastic approximation. I mean, I just wanted to explain what it is and there's a nice theory. Now I wanna do the whole thing over again with sine waves instead of noise, all right? And you see I've got these pretty sine waves, you know, and now I've got my estimates going along in this beautiful smooth way. Well, I-- I claim this is reality in all the examples I've looked at. It's so pretty how using the smooth exploration
18:21
how cool it looks. But I haven't looked at high-dimensional problems yet, so, all right, so all right, you ready for your crash course? Questions?
18:33
All right.
18:35
So in a lot of applications, we create the noise. Now, I know that's not universal, not finance.
18:45
But you know, in many applications, the volatility is not the biggest issue. There's randomness and uncertainty and there's randomness, but it's complexity and uncertainty about the model, things like that, that drive everything. And we definitely create the-- Well, I think most of you would agree, in the numerical work you've done, the, us creating the noise is the biggest source of noise. When Google spent 47 days training their computer to play chess, they inserted the noise.
19:17
The chess wasn't being noisy okay? So if we're inserting the noise, then we might as well make it tame. We might as well make it nice. Okay? And why settle for this crappy rate of convergence?
19:34
We're getting this lousy rate of convergence because we're introducing this blah noise. Let's stop. Ha.
19:42
It's a terrible rate of convergence. So what we want is to get that rate of convergence. Instead of one over N, we want one over N squared, and maybe we want to optimize the constant as well and do it purely deterministically. So there's an expectation there, which I'll explain, there's still expectations and then go through this three-step design process. So basically, I wanna design an ODE based on my goal, as I said before that I'm going to, you know, come up with something
20:17
based on exploration
20:20
And then I'm gonna use something like Oiler or some other better approximation to go from the ODE to this. Trying to pres-- so I'm gonna get really tight, beautiful results on the rate of convergence of this result. So that's brand new. That's a month old.
20:38
And then I need a numerical analyst to tell me how to, the best way to preserve that rate. Rather than reproduce the theory here, I think I can just be very clever in my numerical approximation and how to sample this to get, to preserve my rate of convergence. All right? That's a conjecture, you know. So I'll, I'll write that down. That's a conjecture.
21:02
The conjecture is, can I preserve rates?
21:19
I mean, my conjecture is that we can preserve the rates. That's an open question. All right. Ready?
21:27
Okay. So
21:31
all right, everybody drink your cappuccino, your espresso.
21:35
You know I've gotta-- I've gotta do some technicalities, put in some technicalities. So an example of this quasi noise is just sinusoids, but it's much easier to work with complex exponentials, okay? So I've got a bunch of vector of complex exponentials of-- of different frequencies, okay? And that's just an example of where I get this crucial property that I need for rates of convergence,
22:01
that if I take this noise and I do look at partial integrals, they're bounded because they're also just sine waves, okay?
22:10
Now, we're gonna see that that's a very general property for dynamical systems as I'll explain.
22:17
So what I'm gonna do is to generalize these these complex exponentials, I'm gonna assume my noise comes out of a dynamical system like this 'cause th-- this includes all sorts of other things like sawtooth functions and stuff like that um, which I can make into a continuous domain. So I've got a domain that the probing-- call it a probing signal, lives on which is compact,
22:45
and I've got this vector field H which defines the Z. But if you like, just ignore that and just say I'm-- I'm looking at sine waves, you know?
22:54
All right. So if you like the whole lecture, I'm just talking about mixed use of sine waves and cosine waves 'cause that's all I'm doing is encoding cosines and
23:04
[CSABA SZEPESVARI] Sine waves. So wait, so is HN operator here? Oh, no, no-- It's a [SEAN MEYN] Function. [CSABA SZEPESVARI] It's just a function. Yeah. Yeah, because you take the derivate of. Okay sure. [SEAN MEYN] Yeah. [CSABA SZEPESVARI] Okay. All right. Thank you. But the point [SEAN MEYN] Is this is a-- This is a Mar-- this is a Markov process. I know-- I know it's not what you'd normally call a Markov process
23:21
but it's really important to keep in mind that it is Markov because Poisson's equation plays a major role, which is a k-- um, which is something that has followed me around my whole life, and it comes up in actor-critic methods. It comes up everywhere. I'll explain what I mean by that in a moment. Um but the mindset of saying, "Hey, that's a Markov process," is really valuable in thinking about how to analyze these algorithms, okay?
23:52
Okay, so there's a notion of ergodicity. We're gonna assume it is a unique and invariant measure. I apologize again denoting pi.
24:03
I'm sorry I'm torturing you, but pi for me is an invariant measure, and I'm gonna assume that the sample path averages converge to a-- an ergodic average for every say, bounded continuous function and-- and every initial condition. Okay? So this is obviously true for this, right, where the limiting measure would be product form. It'd be a, you know, independent marginals uniform on the unit circle in the complex plane. All right.
24:32
So that's my key assumption, and again, just assume that if you want.
24:41
Um, oh, yeah, Poisson's equation. So this is the definition of Poisson's equation.
24:49
You'd have a conditional expectation if this was a stochastic setting, but because deterministic, there's no conditional expectation. So this is the definition of Poisson's equation.
25:01
Where G is called the forcing function.
25:11
And again, thi-- I spent half of my life being chased around by Poisson's equation. It's like a terminal disease. I caught it in 1990, and I will die with it. It just chases me everywhere I go. Who would think Poisson's equation would come up in getting convergence rates for deterministic algorithms? Well, it does. So this is crucial, and you can see, the reason it's crucial is that very often this has a very nicely behaved solution, and you can see if it does
25:42
have a solution, I have an ergodic theorem and a rate of convergence in ergodic theorem, 'cause I can divide both sides by T1 minus T0.
25:53
Do I have it here? Yeah. I'm just saying here that I can divide both sides by T. You know, one over T integral zero to T of G of Ct dt is just equal to, you know, G bar,
26:12
and I'm taking T naught equals zero and T1 equals T, and then something divided by T.
26:25
Right. I'm not gonna put this in. I might make a mistake
26:29
So But yeah, you can see it. And basically, you know, taking two values and taking the difference. So I have this optimal rate of convergence right away, right? So it turns out in order to be able to present these results, I have to say, I assume a solution to Poisson's equation exists. Again, it's trivial for exponentials. The conditions are just nothing, you know, and I won't get into that, but yeah. You can find conditions in the lecture notes, and then nothing.
27:01
So what I'm gonna do is I'm, I know I might not have time to say anything about theory, so instead, I'm just gonna go and present some applications, and if there's time, say a few words about the theory, okay?
27:14
But this is my standing assumption, that my probing noise is a solution to a
27:23
system like this or just complex exponentials, and I'm gonna need these solutions to Poisson's equation for analysis. I don't need to compute anything, but to get ready to convergence I'll need, need these guys.
27:39
Okay, so this is gonna be fun. So yeah, this is really cool. This is amazing actually. So by the way, this blue thing is gonna be s-- uh, Richard Sutton's mountain car. We'll get back to that next lecture.
27:55
So suppose our objective is to minimize some loss function L of theta, okay? And, but we don't have access to gradients. So there's the Kiefer Wolfowitz procedure, which is well known in RL circles, which is where you take finite differences, you know. Um, so, so W here is some-- Uh, typically, it's assumed to be IID, as it was in, in the Kiefer and Wolfowitz paper.
28:25
And you might stick a gain in here. G is a matrix called a gain. Um, and and then, and I'm not following my rule. I'm not giving you an ODE and then approximating it. Here's an example where you really can't you know what I mean? At least it wouldn't be-- Well, you could, but it wouldn't be-- It would be very contrived. So this is an example where you start discrete, analysis continuous makes perfect sense.
28:53
Okay And so to justify this, it's just Taylor series expansion right? I mean, for those of you who haven't seen it, you've got a difference of two functions here, and I've just abstracted it a little bit. And you do a Taylor series expansion of both terms, you know, assuming epsilon is small, and all the even terms in the Taylor series expansion cancel out, right? Um, so you get
29:18
you get the first-order term, which is the gradient, and you'd get this awful tensor-looking thing involving the the third derivative and something little o of, of epsilon cubed, assuming you have a, a, a Lipschitz third derivative. I mean, you know, if you have less smoothness, you'll get a less tight approximation. But right there, you can see what's happening is the gradient pops out. And what you'd like to do then is get rid of the W, and you do that through multiplication by W,
29:50
all right? 'cause you get a W times a W, and then you take you know, and then everything, nice things happen as we'll see.
29:59
So now I will write down an ODE.
30:02
If I take the expectation of both sides, you know, we all, you all know f-bar means expectation.
30:15
Um, so then-- so using the standard notion of ODE method, I have a discrete time algorithm And I look at the mean dynamics, that's the standard way people use the term ODE method, and you find that this function F-bar is truly the gradient
30:34
But, you know, with a-- The matrix G that we introduced and the covariance of the noise W, and again that's because I have a W times a W, so I end up with a covariance of the noise. Or if it does have zero mean, it's just the autocorrelation. And then this, all this other stuff just becomes some big O epsilon squared term or better. Okay? All right. So that's it. Now there's something a lot of you don't know about and that's this beautiful theory of extremum seeking control.
31:14
I don't think-- I'm not doing it today, am I? No. So I'm gonna give you a full history of this in the next lecture comparing this and actor-critic methods.
31:23
But it's completely wild. So this started they claim in 1922. I'll, I'll explain that later. But what you do is you, again, you try to get an approximate gradient and here's the procedure which I will not justify. It's too hard right now. But you have a physical system and what you do is you take your current parameter estimate, here is theta, okay? And you add on a probing signal, all right, like these mixed two sine waves.
31:59
So nothing's complex here. Mixed two sine waves is fine and you give it a name then you put that in your physical system and out comes the loss evaluated at that. So this mapping pass filter, like differentiation is an example, and you put your probing thing, signal through the same high pass filter and you multiply them together, and that gives you this approximate gradient. You know? And then you multiply that by G and you pass it to this machine and you get this ODE. So this is, this has been
32:41
studied for 100 years. I mean, it only became seriously studied of course in the last 50 years, but it's really old and I don't know why it's not even well known in the controls community. You know, it's a niche sub area of the controls community. But they improve with a low pass filter which is like Rupert Polyak averaging. So they, they, they sort of have their own Rupert Polyak theory in parallel with the stochastic world. It's quite remarkable. Okay?
33:12
So that's something, there's references in the lecture notes. Okay? All right. And then there's this quasi Kiefer Wolterowitz
33:22
or quasi stochastic gradient descent where you just copy and paste, right? I've, I've done nothing here. You know, all I've done is I've taken the W you see there and I've replaced it by a sine wave or some mixture of sine waves. That's all I've done.
33:41
So let's try it out, okay?
33:46
And see what happens. All right. So it turns out that, so nothing how, you know, proposing this algorithm is nothing But it turns out you can get really crisp rates of convergence. And, and Tsabo I mean really understand exactly when the-- I mean, I mean you'll see. You'll be surprised. Really incredibly tight results on the rate of convergence.
34:16
And those are, that hasn't been published yet. So it's summarized in the book chapter.
34:22
All right.
34:25
Okay. All right. So, so next lecture I'm gonna give e-- examples in detail, applications through reinforcement learning. Here, I'm really just gonna polish up, you know, present a, a, a hint at theory and go to questions. All right?
34:45
Okay. And so in terms of rates, you know, there's a hint.
34:52
So there's a gain. Oh yeah, I mean there's a gain there, you know. And the only, the assumption I'm going to be making to get convergence rates, I'm gonna assume that AT goes to zero.
35:06
That's really about it for my step size. So I don't have these complicated-- I don't have the set of rules you see in stochastic approximation.
35:17
All right.
35:20
So what do I do everybody?
35:22
Um, I don't-- I'm not thrilled with this, this choice of step size because I'm still forced to look at this y-- I plus G A star being Hurwitz to get the optimal rate. Um, so, And to see that you only have to look at the non-quasi stochastic approximation algorithm. Just look at the thing without noise. Suppose you could actually run that ODE. You can't because you don't know F bar, you don't have access to it. Um, even, even without noise if you want a G over 1 plus G
36:06
rate of convergence, you need this matrix to be Hurwitz. So maybe we shouldn't use that game, that step size rule. You know, it's just it's too ugly. And do you see the emergency exit button?
36:21
So who wants me to talk about the theory? Uh y-- I guess I'll do it until somebody screams. Okay. I can't hit this I realize 'cause it's on the GoodNotes So I can't even use this.
36:32
Okay. So here's a fun thing. So step one in analysis is to look at this guy here. What I'm doing is I'm, I'm taking my I'm taking my algorithm here, my quasi-stochastic approximation algorithm and then compare it to the guy, the mean field guy, but with, both of them have a step size.
36:58
That's what's different than traditional stochastic approximation analysis. I use the same step size for each. I look at the difference between the two and I divide by the step size.
37:09
So A of T is going to zero, so if this is bounded I'll get a rate of A of AT.
37:29
That's the hope. If Z is bounded, I get my rate of convergence and I get the constants because the rate of convergence, you know, theta of T is equal to theta of RT plus ZTAT, you know, and that's going to zero. And if I, so if I know a bound on ZT, then I have a really good thing here. And bounds on the rate of convergence here is, is much easier--
38:00
As I'll explain. Well, maybe I won't. I w-- uh, why this is easy to explain would take another lecture because I'd have to give a lecture on, on on Lyapunov theory for nonlinear systems and I don't have time for that.
38:17
But this, you can all guess right? This is much easier to understand than this thing here. All right. It satisfies the differential equation. So the derivative of Z to respect the time looks just like what we started with except linearized
38:36
and plus some crazy noise over here. So what this crazy noise is, is a difference between the vector field defining the quasi-Stieltjes approximation algorithm and the vector field here for the deterministic algorithm.
38:56
Yeah.
39:05
All right, so that's noise.
39:11
And this is pretty, isn't it? So I get this additional term here
39:17
which is the derivative of the log of the gain. And this is just a chain rule. It's trivial, but it's so damn tight under very mild conditions you get this result that this RT here is this plus this. And it's not just a little RT. You can get a very crisp bound on that error term, right? So that's step two.
39:43
All right, y'all awake? And then in particular, let's just stick to these special cases, you know. The standard thing you'd look at in stochastic approximation is like a constant over one plus T to the rho. Then RT turns out to be rho over one plus T, yeah.
40:05
I mean, yeah. Rho of one plus T, plus this little of AT. And here's where you see the big discrepancies.
40:13
If rho is less than one--
40:24
Then well, I should do, do it here. If rho is less than one, then one over one plus T is going to be zero super fast, compared to the other term. So it's negligible in terms of, at least in first or ideas of rates. But if rho equals one, then RT and AT are the same magnitude, and that's the reason you get this bigger matrix in the case of using rho equals one. Okay? So it really he-- really helps to explain things. All right? And then, All right. You still awake? What time is it? Then
41:08
you make a change of variables. I'll, I'll explain what this crazy thing is in a moment.
41:14
It's basically this noise.
41:18
It's the integral of a noise. I'll, I'll define it actually, but let's forget it for now. Um, basically, what I'm gonna do is I, I wanna-- My goal is to take this and bring it to the other side, and doing that, I get some approximations but they're not too bad. And so with this change of variables, YT also satisfies an ODE, and this now is zero-mean.
41:50
All right. And then this is just an additive term. Big deal.
41:56
So I don't need to emphasize that. Okay? All right. So this is just from here to here is again a bit of algebra. Once I've defined this, you know, which I don't have definition. But the big thing is that we can get a rate of convergence on this really easily with a rate
42:17
that YT is basically a constant, and therefore we've identified ZT. So ZT is just equal to the thing I haven't defined plus a constant.
42:33
Okay.
42:35
And we can sharpen this a lot, you know, we won't have time today but we can discuss it later. Okay.
42:43
Yeah, so the amazing conclusion is, is that we have this result
42:50
that the parameter estimate Theta T is Theta star
42:56
you know, plus this step size 0 times this.
43:00
And here I can finally give you the definitions.
43:08
So this weird thing here, it's an integral of this zero-mean process,
43:16
all right? Because we know this is bounded.
43:25
And it's-- we're assuming, this is an assumption that this Poisson's equation solution exists. But in the-- you'll see in the lecture notes, it's valid at very minor, minor conditions. So this is just a sinusoidal signal basic-- I mean, a periodic signal or almost periodic signal And then there's a constant. So we get this really thin, and again, we'll discuss it later, you can sharpen this quite a bit. Um, and so there's bias because we're doing
43:58
quasi-st-- uh, we're doing, you know Kiefer Wolfowitz stuff, but it's of the order epsilon squared or something. And to your point, Shaba, about do we want to compute things exactly? We don't, you know. So I wouldn't mind a constant step size. So I'm looking at managing step size to get some really tight understanding. In practice, I might use a very small constant step size, maybe not. You know, we'll discuss that as well.
44:25
So the bias I don't think is a big issue. Um, now here's a fun fact, anybody out there, like Eric, you must be out there, I don't know, Eric Maline many people out there are saying, "Yeah, just do group root Polyak averaging." So basically, you take the output of the algorithm with rho less than one, say rho equals a half, and then you just average it. That's the definition of Polyak group root averaging.
44:54
Well, guess what? It fails.
44:57
It fails because of this damn thing here. It works if and only if the strange y per thing is zero, and I don't know what the hell this thing is.
45:10
I can give you cases where it's zero, but in general it's not. It's a very non-local thing.
45:21
Yeah.
45:23
So sorry you can't use your pu-- um, I don't think it's gonna work for a quasi-gradient descent in gel.
45:31
So it's that hat there that makes it non-local--
45:41
You know, the f-hat means it depends on the behavior of the system far from the equilibrium. So that, that's what happens. So that's fun. This is a few weeks old in a way and-- or a month old. I'm really excited about it. Um, so again, um-- Yeah, I've got a minute. So some refinements and warnings. Now global-- one-- I haven't given you conditions for convergence for any of this theory to work. Again, you can find it in the book chapter. Lipschitz continuity of f is really critical in
46:10
the analysis and all. And for example, if you look at this algorithm, which I used to love, it has almost the same fr as the other algorithm I presented, if xi has zero mean.
46:32
You're like a mixture of, of science-- Sorry.
46:39
You know, zero temporal mean. But, L is gonna typically be strongly convex. So what, in that case, L is not gonna be globally Lipschitz continuous. And so the theory falls apart. None of what I said is true. You might be able to get some local theory, but I can't-- you know, I, I'm not gonna try. Now, at first, I didn't realize that, and I did experiments. This is mountain car, by the way. I'll, I'll explain it next lecture.
47:08
I compared this algorithm with, you know, with the sort of Kiefer-Wolferwitz equivalent where you put an IID noise with the same variance in quotes. And with the stochastic algorithm, so I did a thousand independent trials.
47:24
You got this incredibly just noise. Every run looked different. Um, while with the quasi algorithm, it was consistently converging close to the minimum after only 5,000 samples 'cause I was doing Euler scheme sampling every second.
47:42
And there's a lack of, It doesn't always converge to the same thing, but it converges to the valley. The objective function is flat. This light blue thing is the objective function. And so after 5,000 samples, it's dead on, giving you something right in that tiny region where it's almost optimal. So it's just, I'm very excited about how well this performs in some experiments I've done.
48:12
Okay, so conclusions. Don't introduce volatility if you don't have to.
48:19
What's the best way to do translation? As I asked in the beginning of the lecture, I think people in quasi-Monte Carlo would love to help, so why not let 'em? Also, people in numerical analysis looking at differential equations, we should bring 'em in, you know? More the merrier.
48:37
Applications to constrained optimizations is something we're working on with friends at NRL in particular.
48:44
And in particular what I just talked about in the last lecture, you know, we have a constrained optimization problem there. And applications to RL is the next thing. Now what's really funny is that an interest in Kiefer-Wolferwitz
48:59
was reborn two years ago at the, at the 2018 program
49:07
when Panagiotis with Greek last name, and Shaba, don't ask me to pronounce your last name either grabbed Adith and I, and we set to work trying to get a better understanding of rate of convergence to Kiefer-Wolferwitz. So it was really cool. I mean, that program was just life-changing, right? Thank you, Simons. That was just one thing. It was, it was awesome talking to Panagiotis. But I give up. I mean, the quasi theory is so damn simple. I wanna dive into that
49:38
And I'm gonna let somebody else extend the theory for stochastic algorithms. Um, that's what I'm saying here. Some of the ideas that I laid out to you, I bet could help to improve the rate theory for stochastic algorithms. But again, I'm gonna leave that to somebody else.
49:55
Yeah, that's it.
50:02
Questions?
50:04
[CSABA SZEPESVARI] Cool. Uh, Thank you. Uh, so Sharon was asking--
50:11
Yeah yeah. [SEAN MEYN] Yeah.
50:13
[CSABA SZEPESVARI] What's that? About-- Yeah. Sharon
50:17
What's funny was asking about this averaging, exactly this slide. [SEAN MEYN] Yeah. [CSABA SZEPESVARI] But this is something like tail averaging that you're talking about here? [SEAN MEYN] Well, no. Well, oh yeah, this is Polyak-Rubin Polyak averaging. So Rubik Polyak averaging the way it's defined is you-- you take a very high gain algorithm, you know, so they had more restrictive consumptions on row is one example. So the high gain, So again, the row is right there,
50:47
means that this is, so if row is small, means high gain.
50:56
[CSABA SZEPESVARI] You're pushing up 80. Yeah. Step size is big. [SEAN MEYN] Yeah.
51:02
Yeah, taking something small, raising it to the row power and
51:09
make it bigger. One over. Yeah. Yeah. And so that means high volatility.
51:18
Okay. And so Rupert Poljak proved that if you-- for stochastic algorithms, that if you just do that, say, "Okay, I'll have high volatility but I'll average at the end," you get the optimal, not-- you get the optimal rate of convergence and the optimal constants in the rate. It's absolutely mind-boggling. In practice, it doesn't work very well often because the rate of convergence is CLT is sometimes very slow. I think there are ways to fix that. So, But in practice, it hasn't been very
51:46
popular because of that. But for the deterministic case, it actually fails because of this residual constant.
51:55
It's because-- Mm-hmm. Our objective is stronger. They're trying to get the CLT in the usual sense. I'm trying to get a one over T convergence rate. And so that's the reason it fails.
52:06
[CSABA SZEPESVARI] Yeah. Um, yeah, I guess Sharan's point was actually the maybe there's something called tail averaging where you put higher weight on, uh-- Mm-hmm. --iterative, the more recent,
52:18
[SEAN MEYN] -- That, that's, that's, that's what I was gonna say. In fact, if you look at my lecture notes, that's all I say. I-- Oh, I see. The only reason I presented this was so it'd be easy to write it down. So theoretically this has the same variance as tail averaging, but in practice, no way. Tail averaging kicks ass you know? It's, it's just, it's amazing how much better it is. And the experiments I've done, it's all tail averaging. So I take the last 20%, say or something.
52:49
[CSABA SZEPESVARI] Yeah. Uh-huh. So Roshan had a question on Discord that I were trying to convey. I think it was-- it mostly relates to the previous lecture.
53:03
So the question was whether the ODE approach to stochastic approximation can also recover the ideas from online learning and online optimization like neural descent, regularizers whatnot. [SEAN MEYN] Oh. [CSABA SZEPESVARI] It's a bit open-ended. I guess the elaboration is whether these ideas are able to, the continuous time method is able to recover the performance guarantees that usually you get for the online, from the online learning literature. [SEAN MEYN] I don't know. Um--
53:42
[CSABA SZEPESVARI] I think that was what I was also poking at previously. [SEAN MEYN] Yeah, I don't know. Um, the thing is that here, you know, a lot of what I'm doing here is showing that the stochastic algorithm and the deterministic algorithm couple so fast that it's not even random. And,
54:05
um-- Sure. Yeah. And, but only because I designed the deterministic algorithm carefully. You know, like I mentioned, if I use the wrong gain, it's not true. So if I design my non-quasi pure mean derivative thing properly, I automatically get incredibly fast rate of convergence. And I wish I had time-- Well, maybe I-- I mean, you've got your theta star, right?
54:35
And then I, I'm gonna draw an epsilon ball around that.
54:39
Some-- Or delta, whatever. And I have an initial condition here, theta zero, right? And I've got my deterministic guy, my, my theta dot equals f bar of theta, and I put bars on that just to-- What do I need my gain?
55:04
Now, there's two properties. There's one-- how long to reach the ball?
55:22
What's cool is that this is just a time change of the original ODE.
55:35
So, Lyapunov theory gives you-- gives you answers.
55:42
So we can get bounds on the time to reach this ball using Lyapunov theory.
55:46
And then within the bowl--
55:53
We have pristine rate results of rate down--
56:03
I'm just excited, everyone. I'm not bragging because it's so, You know how it is, when something's very new, you smile a lot. So I'm not-- This is not arrogance, it's happiness.
56:14
So the word pristine sounds totally arrogant and pretentious. But I-- I-- But it's true that you'll see, we-- The-- The results I've given to you, I haven't given you the details, you get really, really nice results in-- in this region of attraction for the deterministic eye, not for the stochastic eye, you know? So Lyapunov theory tells you this is invariant,
56:35
for this invariant-- This-- this ball.
56:43
This is an invariant set. So for the theta bar set you can never leave it. And the fact that you can never leave it is how you get such tight bounds.
56:58
So to answer your question, I think that you can get a lot of success by first looking at the idealization ODE, and then once you understand it well enough, go to the stochastic or whatever, you know, the, the noisy version.
57:21
Yeah. So there's no way to prove it's absorbing for the original thing, it's for this deterministic R.
57:28
That's sort of an answer.
57:34
[CSABA SZEPESVARI] I was also wondering about whether there is any connection to, I remember that there was a time in the '90s where we-- people were trying to work on conditions for stochastic approximation that were based on deterministic analysis. Like, I think Dayan or Benayum or--
57:52
[SEAN MEYN] Oh, sure. Oh, but that's the thing. But they-- but they were-- I mean, Benayum, How do you pronounce his name? Be-- Benayum? Benayum? Benayum. Anyway Yeah. He was mainly extending the theory, this beautiful ways of conceptualizing really difficult problems. You know, where f is not, not Lipschitz, not smooth, not anything. Um-- That is-- And some really nice dynamical systems theory to-- He has great lecture notes on that. Um, and Dayan du-- I don't know.
58:26
The Dayan reference, I know Dayan, but I don't know what you're referring to. Um--
58:31
[CSABA SZEPESVARI] It's been a while. I looked at his literature, so off the top of my head, but I see that there is something called deterministic analysis of stochastic approximation algorithms. I can dig up the reference later. Yeah. I remember that they were talking about sufficient conditions for the noise sequence to hold, which is not noise anymore, but this deterministic perturbation. Oh, [SEAN MEYN] Yeah, Yeah yeah. Oh, I see. And-- That's, and that-- that's a-- Yeah yeah Yeah.
58:59
So, oh, that's right. Absolutely. So Yeah. But I-- Yeah, that's right. Which is really a good way to go is, is instead of assuming it's IID or mar-- or Martingale-- Yeah. --put conditions on the noise. Um, but all, all the theory I'm aware of is geared towards making sure it's acceptable when you go to a IID setting or whatever. Mm-hmm. And I'm going the other route. I, I don't want it to be acceptable because I'm trying to get this 1 over T rate of convergence. [CSABA SZEPESVARI] Yeah, yeah.
59:30
I see that My, my [SEAN MEYN] Goals are different. That's all.
59:33
[CSABA SZEPESVARI] Yeah. [SEAN MEYN] I should have said that-- Okay. --the p-- The, the prior work I'm aware of is in finance. I forgot to mention that. Not on rates of convergence, but on using like sine waves.
59:46
Again, you can find it in the references and
59:50
[CSABA SZEPESVARI] Yeah. Is there-- So, you also mentioned this. So this is Kiefer-Wolferit.
1:00:01
It's like the two-point approximation of the gradient-- Oh yeah. --of PSA And then you were talking about the one-point approximation. Yeah. And if you do the two-point approximation, you can do the Taylor expansion to a higher degree. And I think that maybe one crucial fact here is that you have the same noise plugged into two places-- [SEAN MEYN] Yeah. --that [CSABA SZEPESVARI] Are to cancel each other. [SEAN MEYN] Yeah.
1:00:28
[CSABA SZEPESVARI] Or same perturbation in this case
1:00:32
which is going to be challenging reinforcement learning, right? [SEAN MEYN] Uh-huh. Yeah yeah. Good point. So that's why-- Oh my. [CSABA SZEPESVARI] I mean if you have a simulator sure. Like, it's like a common random number generator I think. [SEAN MEYN] Yeah, yeah. That's a good point. Yeah I'll, I'll, I'll give an example next hour where it's not a big deal. You know. But you're right. In general, it would be a big deal. Um, and-- And, and, and is it-- So what did--
1:00:59
[CSABA SZEPESVARI] This is one of the big reasons you can get the faster rate because you can reuse the same perturbation twice and make two measurements at least?
1:01:10
[SEAN MEYN] Oh, no. [CSABA SZEPESVARI] No? You don't think so? The theory is [SEAN MEYN] Totally general. Oh, no, it's the Lipschitz continuity because my the-- the theorem I gave is nothing to do with anything. It's totally general. It doesn't require Kiefer-Wolferits or anything. This is for any rate. Oh okay. [CSABA SZEPESVARI] Okay. I kind of thought-- Oh yes. Okay. Oh, [SEAN MEYN] Yeah. Sorry if I didn't make that clear. Oh no. So this was just an example.
1:01:32
But my-- Oh. But this-- But-- Oh, I'm sorry. I should have made that clearer. I didn't realize that. Now, this entire theory part was for anything.
1:01:43
This theorem here-- Okay. This theorem here is for anything. Okay. Okay. Yeah. I mean, the assumptions are really mild. Um-- [CSABA SZEPESVARI] Okay. Cool. [SEAN MEYN] Yeah. I need a Lyapunov function or something to make sure I get in a region of attraction and I need a linearization. That's really crucial, you know.
1:02:04
I need smoothness at theta star.
1:02:07
[CSABA SZEPESVARI] Mm-hmm. Mm-hmm. [SEAN MEYN] Okay. Everyone left? Oh no no. All right, good.
1:02:13
So the next lecture will be lighter, I think. It'll be a lot of history, but it'll be fun history and some examples on how to apply these ideas to the mountain car. You know, it's a fun last lecture.
1:02:29
[CSABA SZEPESVARI] All right. So let's take a quick break and we come back in 20 minutes then. Cool.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat