Archive for computing time
algorithmic complexity
Posted in Books, Kids, Statistics, University life with tags algorithms, computational complexity, computing time, webcomic, xkcd on July 31, 2024 by xi'an
repelling-attracting Hamiltonian Monte Carlo
Posted in Books, pictures, Statistics, University life with tags computing time, friction, Hamiltonian Monte Carlo, HMC, multimodality, repelling-attracting, Stanford University on June 25, 2024 by xi'an
Lasrt week, Siddharth Vishwanath and Hyungsuk Tak—whom I first met at an MCQMC session about multimodal sampling at MCqMC 2016 in Stanford, same year as my San Fran’ half-marathon race, most memorable of all my races!)—proposed a Repelling-Attracting Hamiltonian Monte Carlo (raHMC) algorithm, towards sampling from multimodal distributions.
“The success of raHMC for sampling from multimodal distributions crucially hinges on the choice of the [three] tuning parameter[s]”
The concept behind raHMC is to endow an HMC algorithm with an added friction term that slows down moves, except it can get turned into an acceleration effect when the friction coefficient γ becomes negative. In a proposal remindful of leapfrog half-time moves, raHMC proceeds by switching the sign of this coefficient γ half-way of an artificial time parameter T that is representing the inter-simulation time between two successive states of the Markov chain. By this aggregation of opposite forces, the resulting algorithm satisfies the detailed-balance condition, hence is reversible and preserves symplectic structure and volume. If not energy.
“…a direct application of the repelling-attracting mechanism to NUTS may not be straightforward. Lastly, we have not been able to guarantee that raHMC conserves energy”
Given the dependence on the tuning parameters, I fear implementing the algorithm may prove delicate in more complex settings, e.g. when the number of modes is unknown, as the acceleration component is rather blind to the actual target. In addition, the leapfrog integrator may prove quite slow in low density regions, which are visited about half the time.
“This, however, comes at the price of a higher computational cost, as the auto-tuning procedure for raHMC tends to favor longer trajectories, and therefore requires more gradient evaluations per step”
Numerical experiments show, indeed, that the algorithm is much slower than others, as this occurence of a 8.5s execution time for HMC vs a corresponding 1094s for raHM…
population quasi-Monte Carlo
Posted in Books, Statistics with tags Bernhard Flury, computing time, mixture of distributions, Monte Carlo Statistical Methods, PMC, population Monte Carlo, principal points, quasi-Monte Carlo methods, residual resampling, SMC, Sobol sequences, support points, systematic resampling on January 28, 2021 by xi'an
“Population Monte Carlo (PMC) is an important class of Monte Carlo methods, which utilizes a population of proposals to generate weighted samples that approximate the target distribution”
A return of the prodigal son!, with this arXival by Huang, Joseph, and Mak, of a paper on population Monte Carlo using quasi-random sequences. The construct is based on an earlier notion of Joseph and Mak, support points, which are defined wrt a given target distribution F as minimising the variability of a sample from F away from these points. (I would have used instead my late friend Bernhard Flury’s principal points!) The proposal uses Owen-style scrambled Sobol points, followed by a deterministic mixture weighting à la PMC, followed by importance support resampling to find the next location parameters of the proposal mixture (which is why I included an unrelated mixture surface as my post picture!). This importance support resampling is obviously less variable than the more traditional ways of resampling but the cost moves from O(M) to O(M²).
“The main computational complexity of the algorithm is O(M²) from computing the pairwise distance of the M weighted samples”
The covariance parameters are updated as in our 2008 paper. This new proposal is interesting and reasonable, with apparent significant gains, albeit I would have liked to see a clearer discussion of the actual computing costs of PQMC.
likelihood free nested sampling
Posted in Books, Statistics with tags auxiliary particle filter, Bayesian inference, bioRxiv, computing time, Dirichlet process Gaussian mixture, intractable likelihood, MCMC, Monte Carlo Statistical Methods, nested sampling, pseudo-marginal MCMC, state space model, statistical evidence on April 26, 2019 by xi'an
A recent paper by Mikelson and Khammash found on bioRxiv considers the (paradoxical?) mixture of nested sampling and intractable likelihood. They however cover only the case when a particle filter or another unbiased estimator of the likelihood function can be found. Unless I am missing something in the paper, this seems a very costly and convoluted approach when pseudo-marginal MCMC is available. Or the rather substantial literature on computational approaches to state-space models. Furthermore simulating under the lower likelihood constraint gets even more intricate than for standard nested sampling as the parameter space is augmented with the likelihood estimator as an extra variable. And this makes a constrained simulation the harder, to the point that the paper need resort to a Dirichlet process Gaussian mixture approximation of the constrained density. It thus sounds quite an intricate approach to the problem. (For one of the realistic examples, the authors mention a 12 hour computation on a 48 core cluster. Producing an approximation of the evidence that is not unarguably stabilised, contrary to the above.) Once again, not being completely up-to-date in sequential Monte Carlo, I may miss a difficulty in analysing such models with other methods, but the proposal seems to be highly demanding with respect to the target.
Monte Carlo calculations of the radial distribution functions for a proton-electron plasma
Posted in Books, pictures, Statistics, University life with tags Australian Journal of Physics, Barker's algorithm, computing time, Metropolis-within-Gibbs algorithm, nuclear weapons, rand, random walk, temperature, University of Adelaide on October 11, 2017 by xi'an“In conclusion, the Monte Carlo method of calculating radial distribution functions in a plasma is a feasible approach if significant computing time is available (…) The results indicate that at least 10000 iterations must be completed before the system can be considered near to its equilibrium state, and for a badly chosen starting configuration, the run would need to be considerably longer (…) for more conclusive results a longer run is needed so that the energy of the system can settle into an equilibrium pattern and steady-state radial distribution functions can be obtained.” A.A. Barker
Looking for the history behind Barker’s formula the other day made me look for the original 1965 paper. Which got published in the Australian Journal of Physics at the beginning of Barker’s PhD at the University of Adelaide.
As shown in the above screenshot, the basis of Barker’s algorithm is indeed Barker’s acceptance probability, albeit written in a somewhat confusing way since the current value of the chain is kept if a Uniform variate is smaller than what is actually the rejection probability. No mistake there! And more interestingly, Barker refers to Wood and Parker (1957) for the “complete and rigorous theory” behind the method. (Both Wood and Parker being affiliated with Los Alamos Scientific Laboratory, while Barker acknowledges support from both the Australian Institute of Nuclear Science and Engineering and the Weapons Research Establishment, Salisbury… This were times when nuclear weapon research was driving MCMC. Hopefully we will not come back to such times. Or, on the pessimistic side, we will not have time to come back to such times!)
As in Metropolis et al. (1953), the analysis is made on a discretised (finite) space, building the Markov transition matrix, stating the detailed balance equation (called microscopic reversibility). Interestingly, while Barker acknowledges that there are other ways of assigning the transition probability, his is the “most rapid” in terms of mixing. And equally interestingly, he discusses the scale of the random walk in the [not-yet-called] Metropolis-within-Gibbs move as major, targetting 0.5 as the right acceptance rate, and suggesting to adapt this scale on the go. There is also a side issue that is apparently not processed with all due rigour, namely the fact that the particles in the system cannot get arbitrarily close from one another. It is unclear how a proposal falling below this distance is processed by Barker’s algorithm. When implemented on 32 particles, this algorithm took five hours to execute 6100 iterations. With a plot of the target energy function that does not shout convergence, far from it! As acknowledged by Barker himself (p.131).
The above quote is from the conclusion and its acceptance of the need for increased computing times comes as a sharp contrast with this week when one of our papers was rejected based on this very feature..!
