Archive for adaptive Monte Carlo algorithm
Congrats, Dr. Andral!
Posted in Books, pictures, Statistics, University life with tags adaptive Monte Carlo algorithm, ENSAE, history of Monte Carlo, importance MCMC, importance sampling, jury, normalizing flow, Paris, PDMP, PhD thesis, PSL Research University, quasi-Monte Carlo methods, thesis defence, Université Paris Dauphine on November 27, 2024 by xi'an
sampling using adaptive regenerative processes [in print!]
Posted in pictures, Statistics, University life with tags #ERCSyG, academic journals, adaptive MCMC methods, adaptive Monte Carlo algorithm, Bernoulli, Bernoulli society, eadem mutata resurgo, ERC Synergy Grant, Markov process, Ocean, Project euclid, regeneration, University of Warwick on November 16, 2024 by xi'an
bandits for stratified Monte Carlo
Posted in Books, pictures, Statistics, University life with tags adaptive Monte Carlo algorithm, multi-armed bandits, stratified sampling on December 12, 2021 by xi'an
In our Monte Carlo reading group in Dauphine, we recently went through Carpentier, Munos and Antos’ Adaptive strategy for stratified Monte Carlo sampling, a 2015 JMLR paper. Which given K strata and corresponding weights on the different strata aims at producing an efficient estimate of the weighted mean. This problem can be re-expressed as a K armed bandit problem, where choosing an arm is driven by running the optimal number of simulation per arm (stratum). The ideal solution takes a number of simulations proportional to the weight x standard deviation of the associated stratum. The proposed algorithm estimates this quantity on the go by always pulling the arm (stratum) with the largest (over-)estimated value. The rather unusual perspective of the paper is to bring out precise, deterministic, and finite-sample bounds on the errors between the optimal allocations (to the arms) and their sequential approximations, the weighted MSE regrets, and the overall regret. Albeit crucially depending on the sub-Gaussianity rates c¹ and c² of the arm distributions for the construction of the shrinkage coefficient β… (Obviously, I am not deeply knowledgeable in bandits so may miss some of the more recent literature.) An extension of interest would be to estimate the weights as well, for instance when the masses of the strata are unknown. Or even deciding on the strata themselves. We also all wondered at a possible link with Wang-Landau, but the desiderata sounded divergent.
an independent sampler that maximizes the acceptance rate of the MH algorithm
Posted in Books, Kids, Statistics, University life with tags accept-reject algorithm, adaptive Monte Carlo algorithm, Addis Abeba, Bayesian GANs, Ethiopia, ICLR 2019, importance sampling, Kullback-Leibler divergence, Monte Carlo Statistical Methods, optimal acceptance rate, optimisation, reversibility, simulation, total variation on September 3, 2019 by xi'anAn ICLR 2019 paper by Neklyudov, Egorov and Vetrov on an optimal choice of the proposal in an independent Metropolis algorithm I discovered via an X validated question. Namely whether or not the expected Metropolis-Hastings acceptance ratio is always one (which it is not when the support of the proposal is restricted). The paper mentions the domination of the Accept-Reject algorithm by the associated independent Metropolis-Hastings algorithm, which has actually been stated in our Monte Carlo Statistical Methods (1999, Lemma 6.3.2) and may prove even older. The authors also note that the expected acceptance probability is equal to one minus the total variation distance between the joint defined as target x Metropolis-Hastings proposal distribution and its time-reversed version. Which seems to suffer from the same difficulty as the one mentioned in the X validated question. Namely that it only holds when the support of the Metropolis-Hastings proposal is at least the support of the target (or else when the support of the joint defined as target x Metropolis-Hastings proposal distribution is somewhat symmetric. Replacing total variation with Kullback-Leibler then leads to a manageable optimisation target if the proposal is a parameterised independent distribution. With a GAN version when the proposal is not explicitly available. I find it rather strange that one still seeks independent proposals for running Metropolis-Hastings algorithms as the result will depend on the family of proposals considered and as performances will deteriorate with dimension (the authors mention a 10% acceptance rate, which sounds quite low). [As an aside, ICLR 2020 will take part in Addis Abeba next April.]
probably ABC [and provably robust]
Posted in Books, pictures, Statistics, Travel with tags ABC, ABC-SMC, adaptive Monte Carlo algorithm, Bayesian asymptotics, CREST, Gaussian processes, likelihood-free methods, misspecified model, oracle inequalities on August 8, 2017 by xi'an
Two weeks ago, James Ridgway (formerly CREST) arXived a paper on misspecification and ABC, a topic on which David Frazier, Judith Rousseau and I have been working for a while now [and soon to be arXived as well]. Paper that I re-read on a flight to Amsterdam [hence the above picture], written as a continuation of our earlier paper with David, Gael, and Judith. One specificity of the paper is to use an exponential distribution on the distance between the observed and simulated sample within the ABC distribution. Which reminds me of the resolution by Bissiri, Holmes, and Walker (2016) of the intractability of the likelihood function. James’ paper contains oracle inequalities between the ABC approximation and the genuine distribution of the summary statistics, like a bound on the distance between the expectations of the summary statistics under both models. Which writes down as a sum of a model bias, of two divergences between empirical and theoretical averages, on smoothness penalties, and on a prior impact term. And a similar bound on the distance between the expected distance to the oracle estimator of θ under the ABC distribution [and a Lipschitz type assumption also found in our paper]. Which first sounded weird [to me] as I would have expected the true posterior, until it dawned on me that the ABC distribution is the one used for the estimation [a passing strike of over-Bayesianism!]. While the oracle bound could have been used directly to discuss the rate of convergence of the exponential rate λ to zero [with the sample size n], James goes into the interesting alternative direction of setting a prior on λ, an idea that dates back to Olivier Catoni and Peter Grünwald. Or rather a pseudo-posterior on λ, a common occurrence in the PAC-Bayesian literature. In one of his results, James obtains a dependence of λ on the dimension m of the summary [as well as the root dependence on the sample size n], which seems to contradict our earlier independence result, until one realises this scale parameter is associated with a distance variable, itself scaled in m.
The paper also contains a non-parametric part, where the parameter θ is the unknown distribution of the data and the summary the data itself. Which is quite surprising as I did not deem it possible to handle non-parametrics with ABC. Especially in a misspecified setting (although I have trouble perceiving what this really means).
“We can use most of the Monte Carlo toolbox available in this context.”
The theoretical parts are a bit heavy on notations and hard to read [as a vacation morning read at least!]. They are followed by a Monte Carlo implementation using SMC-ABC. And pseudo-marginals [at least formally as I do not see how the specific features of pseudo-marginals are more that an augmented representation here]. And adaptive multiple pseudo-samples that reminded me of the Biometrika paper of Anthony Lee and Krys Latuszynski (Warwick). Therefore using indeed most of the toolbox!
