Level algorithm

[HaroldRKingsberg]

@mtran2011, just making a documented request for some explanation of the multi-level logic here.

If I remember your initial explanation, there's a deterministic solution for how many paths are required per level, and if the confidence level creation is roughly similar to the vanilla stuff, then really, what we need to know is how to figure out what the stdev is.

Of course, I could be completely wrong. Either way, please respond here with some explanation of the algorithm.

Thanks.

[mtran2011]

The paper An Introduction to Multilevel Monte Carlo for etc. by DJ Higham has on pg 8, equation 10, an exact formula for L, the highest level. Also, pg 9 has a formula for N(l), aka the num paths required for level l, but this formula is not exact, and instead a O(.) form, for which we do not know the constant. The problem then is as before, that b/c we don't know the constant for N(l), we fail to get the accuracy level inputted.

A harder algo is on pg 612, equation 12 of paper Multilevel Monte Carlo path simulation - Giles. This is more "official" because Giles is the author of MLMC. I uploaded a first stab at implementing this algo in Giles 2008 paper.

The Giles 2008 algo is more like what you did in vanilla. In this algo, the max L keeps += 1 until a criteria is met.

Both papers are in our docs folder. The 2015 paper by Giles Acta Numerica is very broad and doesn't have an algo for SDE Euler specifically I think.

[mtran2011]

I just uploaded a draft of Giles 2008 algo, it calculates the estimator (Y) and the variance of this estimator (var_Y). This is like tracker.mean and tracker.stdev. But I don't know how to make this conform to existing API. Also the code is a manual step by step thing with lots of repetitions, so will need your help on this. I'm going back to the paper and other things. Pls call me tonight if needed.

[HaroldRKingsberg]

As it turns out, Giles himself appears to have implemented the algorithm in Matlab:

https://people.maths.ox.ac.uk/gilesm/acta/

mlmc.m is the file you're looking for -- I've reimplemented most of it in option.py in the "layers" branch.

I have not tested this out because I did not finish the code, and more specifically, I couldn't figure out how to calculate alpha. @mtran2011, @petercwill -- could either of you please implement finding alpha sometime tomorrow? I'd do it, but I just don't have any gas left in the tank after the last three nights of this, and I really just want to go to bed.

[HaroldRKingsberg]

Figured out how to calculate alpha - ordinary least squares, where the independent variable is the level (not including the base level) and the dependent variable is the log_2 of the mean of the samples at that level. Can implement later, would appreciate it if someone else beat me to the punch.

[mtran2011]

Found this algo using alpha and beta in Giles 2015 paper, it seems to be different from the one he wrote himself for his 2008 paper and for the geometric brownian and heston model here: https://people.maths.ox.ac.uk/gilesm/mlmc/ https://people.maths.ox.ac.uk/gilesm/mlmc/matlab/opre/opre.m

But I think it also works. I'm looking at implementing _find_alpha(). Also, his code involves using a beta but I can't find the beta in option.py yet

[HaroldRKingsberg]

I didn't see where beta and gamma were actually used in the process that we actually needed, so I didn't implement.

On May 4, 2017 10:21 AM, "mtran2011" notifications@github.com wrote:

Found this algo using alpha and beta in Giles 2015 paper, it seems to be different from the one he wrote himself for his 2008 paper and for the geometric brownian and heston model here: https://people.maths.ox.ac.uk/gilesm/mlmc/ https://people.maths.ox.ac.uk/gilesm/mlmc/matlab/opre/opre.m

But I think it also works. I'm looking at implementing _find_alpha(). Also, his code involves using a beta but I can't find the beta in option.py yet

— You are receiving this because you were assigned. Reply to this email directly, view it on GitHub https://github.com/HaroldRKingsberg/MLMC/issues/9#issuecomment-299199600, or mute the thread https://github.com/notifications/unsubscribe-auth/AFAfVF4w3S8YsDWqXrkHri-SvnRaQuv6ks5r2d7igaJpZM4NO7vp .

[mtran2011]

I don't fully understand the 2015 paper and matlab code, but it seems beta is the decay rate of the variance V, and gamma is the growth rate of the computing cost. Near the end of the matlab code, he wrote Vl(L+1) = Vl(L) / 2^beta; so it seems as though in this algo we'd need beta to get the variance of the estimator. Gamma is used to determine the optimal numpaths Ns at next level Cl = 2.^(gamma(0:L)); Ns = ceil(2 sqrt(Vl./Cl) sum(sqrt(Vl.Cl)) / eps^2); dNl = max(0, Ns-Nl); The stopping criteria is while sum(dNl) > 0 It seems that beta and gamma would come into play somehow...what do you think?

[HaroldRKingsberg]

Yeah, I just assumed any new level would start with N0 to go with, which is why beta and gamma didn't come into play. It looks like calculating beta and gamma should be fairly easy to do. I'll do it when I get home tonight.

[mtran2011]

I went to the prof's office just now and he explained that both algos work; the one with alpha and beta requires that the user derives these convergence rates before on paper and then input into algo, or if not then they are estimated. This is on pg 6 of Giles 2015 theorem 1, and also pg 8 first paragraph. The prof wants us to use both algos and compare their results -- he said this is where modular codes come into play. The display of results is graphs on pg 31 of Giles 2015. There is no formula for gamma but he said this is all good stuff to try so that's all I can take away.

[HaroldRKingsberg]

Easy enough.

On May 4, 2017 5:08 PM, "mtran2011" notifications@github.com wrote:

I went to the prof's office just now and he explained that both algos work; the one with alpha and beta requires that the user derives these convergence rates before on paper and then input into algo, or if not then they are estimated. This is on pg 6 of Giles 2015 theorem 1, and also pg 8 first paragraph. The prof wants us to use both algos and compare their results -- he said this is where modular codes come into play. The display of results is graphs on pg 31 of Giles 2015. There is no formula for gamma but he said this is all good stuff to try so that's all I can take away.

— You are receiving this because you were assigned. Reply to this email directly, view it on GitHub https://github.com/HaroldRKingsberg/MLMC/issues/9#issuecomment-299309713, or mute the thread https://github.com/notifications/unsubscribe-auth/AFAfVGJDij1mfC1xrJl86eyl_xWsO8m-ks5r2j5UgaJpZM4NO7vp .