4 ms·

Anyone who does Monte Carlo simulations would at least be interested in the notion of Quasi Monte Carlo, in which points are sampled "more evenly than random."

Anyone who does Monte Carlo simulations would at least be interested in the notion of Quasi Monte Carlo, in which points are sampled "more evenly than random." As noted in OP, this can lead to O(1/n) convergence of averages to underlying target values, rather than the expected O(1/sqrt(n)) convergence ("n" is the number of probes of the underlying system). This is shown, strikingly, in Fig. 2 of the OP. There is a conference, tutorial papers etc. E.g.: http://mcqmc2018.inria.fr http://mcqmc2018.inria.fr

mlthoughts2018 8y ago
I work professionally in large-scale mcmc projects and don’t find quasi mc to be much more than a curiosity in my work, because integration (as opposed to drawing a rich set of posterior samples) is virtually never the goal. To do anything of use, you have to draw samples and then simulate complex outcomes, very few of which reduce to simple averages over the drawn samples or functions of the drawn samples. And since you need to draw samples, you might as well use those samples for any parts that do happen to require integration, rather than a quasi mc calculation, except in extremely toy-problem situations where the convergence rate matters disproportionately for that smallset of outcomes. I agree that for cases when you just want to evaluate an integral it could be useful. I have never encountered a use case when anyone just wanted to calculate an integral, as opposed to also generating posterior uncertainty metrics, posterior test statistics for posterior predictive checking, posterior diagnostics like ordinal statistics among the posterior samples. I’m sure outside of stats, there must be use cases. Just adding a counterpoint to the idea that quasi mc should always be interesting to practitioners. For a lot of people who work in mcmc methods, quasi mc is just not interesting and generally speaking could never be.
- mturmon 8y ago
  I agree with all of this. QMC is more relevant to Monte Carlo, but MCMC is its own thing as far as I know. There is some work on combining the two, but it doesn’t seem mature. If you don’t mind: what’s the general application domain for your MCMC‘s? For me, it’s inference of (usually) spatial fields for various science data sets, like Earth or solar imagery or atmospheric composition.
  - mlthoughts2018 8y ago
    For me it’s posterior sampling to generate meaningful uncertainty metrics in very large scale causal inference for understanding location-based behavioral data, sometimes for ads, sometimes for other modeling problems like image quality, app engagement, etc.
extremelearning 8y ago
Absolutely! This is actually the original reason I began exploration into quasirandom numbers. I wanted to see if I could replace some of the stochastic process in current machine learning architectures with quasirandom processes. In principle, the curse of dimensionality kicks in after a dozen or so dimensions, as convergence is O( log(N)^D / N). But in practice I have found that in a surprising number of applications and circumstances, quasirandom sequences can have offer a substantial improvement even when the number of dimensions are in the hundreds or even thousands. (Some authors have suggested this works because the solution space is of low dimensions but embedded in a much higher dimensional space...) However, to get the full benefit I needed to find a low discrepancy quasirandom sequence that did not suffer the many of the parameter degeneracy problems that many of the conventional ones exhibit for very large D. For me, the new R-sequence nicely solves this parameter selection problem by not having any parameters to optimize!
- jacobolus 8y ago
  Can you explain how you figured out that these were the right generalization of the golden ratio? Were you doing a literature search? Just experimenting? BTW, in the past couple months I have directed several people who were interested in spiral phyllotaxis and the like at your page. I think your sequences could make for some interesting art projects. Personally I plan to try them out for dithering, picking well-spaced colors for diagrams, picking points in a region when trying to optimize a map projection, etc.
  - extremelearning 8y ago
    Thanks for the kind words and promotion! ;) These findings were a combination of a lot of literature searching, perseverance, decades of mathematical intuition and computer modelling of various hypotheses. I had a problem to solve so I was determined to find a solution. And then combine this with my obsession with simplicity, it meant I didn’t just want to tweak a million parameters to get a result.
cosmic_ape 8y ago
Just to make sure, the uniform grid on n points will also lead to O(1/n) convergence, right? I get that the uniform grid is not an open sequence, just want to understand which kind of convergence do you have in mind. For which class of functions?
- extremelearning 8y ago
  For a known fixed value of n, you can get amazing convergence rates. For example, the basic midpoint rule gives O(1/n^2) and Simpson's rule gives O(1/n^4). Despite this, there are two major use cases for quasirandom sequences: The first is when n is not known upfront and so you can't create a lattice; and the second is in higher dimensions. The reason for this latter situation is because the number of points required to make a lattice in D dimensions scales exponentially in D, whereas the convergence rates for random or quasirandom sampling are (amazingly!) independent on the dimension. I think that you would really like Owen's paper on this topic. It is very comprehensive and yet extremely readable [1] 1[ ]http://statweb.stanford.edu/~owen/mc/Ch-quadrature.pdf http://statweb.stanford.edu/~owen/mc/Ch-quadrature.pdf
  - cosmic_ape 8y ago
    I certainly agree re:high dimensions. This is because to integrate, you don't need to approximate the function everywhere.
  - _0ffh 8y ago
    Yes, with a fixed n you can essentially do what some fields call DOE [1]. If your sampling process is open-ended things are different. [1] https://en.wikipedia.org/wiki/Design_of_experiments https://en.wikipedia.org/wiki/Design_of_experiments

mlthoughts2018 8y ago

I work professionally in large-scale mcmc projects and don’t find quasi mc to be much more than a curiosity in my work, because integration (as opposed to drawing a rich set of posterior samples) is virtually never the goal. To do anything of use, you have to draw samples and then simulate complex outcomes, very few of which reduce to simple averages over the drawn samples or functions of the drawn samples. And since you need to draw samples, you might as well use those samples for any parts that do happen to require integration, rather than a quasi mc calculation, except in extremely toy-problem situations where the convergence rate matters disproportionately for that smallset of outcomes. I agree that for cases when you just want to evaluate an integral it could be useful. I have never encountered a use case when anyone just wanted to calculate an integral, as opposed to also generating posterior uncertainty metrics, posterior test statistics for posterior predictive checking, posterior diagnostics like ordinal statistics among the posterior samples. I’m sure outside of stats, there must be use cases. Just adding a counterpoint to the idea that quasi mc should always be interesting to practitioners. For a lot of people who work in mcmc methods, quasi mc is just not interesting and generally speaking could never be.

mturmon 8y ago
I agree with all of this. QMC is more relevant to Monte Carlo, but MCMC is its own thing as far as I know. There is some work on combining the two, but it doesn’t seem mature. If you don’t mind: what’s the general application domain for your MCMC‘s? For me, it’s inference of (usually) spatial fields for various science data sets, like Earth or solar imagery or atmospheric composition.
- mlthoughts2018 8y ago
  For me it’s posterior sampling to generate meaningful uncertainty metrics in very large scale causal inference for understanding location-based behavioral data, sometimes for ads, sometimes for other modeling problems like image quality, app engagement, etc.

extremelearning 8y ago

Absolutely! This is actually the original reason I began exploration into quasirandom numbers. I wanted to see if I could replace some of the stochastic process in current machine learning architectures with quasirandom processes. In principle, the curse of dimensionality kicks in after a dozen or so dimensions, as convergence is O( log(N)^D / N). But in practice I have found that in a surprising number of applications and circumstances, quasirandom sequences can have offer a substantial improvement even when the number of dimensions are in the hundreds or even thousands. (Some authors have suggested this works because the solution space is of low dimensions but embedded in a much higher dimensional space...) However, to get the full benefit I needed to find a low discrepancy quasirandom sequence that did not suffer the many of the parameter degeneracy problems that many of the conventional ones exhibit for very large D. For me, the new R-sequence nicely solves this parameter selection problem by not having any parameters to optimize!

jacobolus 8y ago
Can you explain how you figured out that these were the right generalization of the golden ratio? Were you doing a literature search? Just experimenting? BTW, in the past couple months I have directed several people who were interested in spiral phyllotaxis and the like at your page. I think your sequences could make for some interesting art projects. Personally I plan to try them out for dithering, picking well-spaced colors for diagrams, picking points in a region when trying to optimize a map projection, etc.
- extremelearning 8y ago
  Thanks for the kind words and promotion! ;) These findings were a combination of a lot of literature searching, perseverance, decades of mathematical intuition and computer modelling of various hypotheses. I had a problem to solve so I was determined to find a solution. And then combine this with my obsession with simplicity, it meant I didn’t just want to tweak a million parameters to get a result.

cosmic_ape 8y ago

Just to make sure, the uniform grid on n points will also lead to O(1/n) convergence, right? I get that the uniform grid is not an open sequence, just want to understand which kind of convergence do you have in mind. For which class of functions?

extremelearning 8y ago
For a known fixed value of n, you can get amazing convergence rates. For example, the basic midpoint rule gives O(1/n^2) and Simpson's rule gives O(1/n^4). Despite this, there are two major use cases for quasirandom sequences: The first is when n is not known upfront and so you can't create a lattice; and the second is in higher dimensions. The reason for this latter situation is because the number of points required to make a lattice in D dimensions scales exponentially in D, whereas the convergence rates for random or quasirandom sampling are (amazingly!) independent on the dimension. I think that you would really like Owen's paper on this topic. It is very comprehensive and yet extremely readable [1] 1[ ]http://statweb.stanford.edu/~owen/mc/Ch-quadrature.pdf http://statweb.stanford.edu/~owen/mc/Ch-quadrature.pdf
- cosmic_ape 8y ago
  I certainly agree re:high dimensions. This is because to integrate, you don't need to approximate the function everywhere.
- _0ffh 8y ago
  Yes, with a fixed n you can essentially do what some fields call DOE [1]. If your sampling process is open-ended things are different. [1] https://en.wikipedia.org/wiki/Design_of_experiments https://en.wikipedia.org/wiki/Design_of_experiments