Archive for convergence
on the edge and online!
Posted in Books, Statistics, Travel, University life with tags advanced Monte Carlo methods, antithetic sampling, convergence, efficient importance sampling, MCMC, Monte Carlo Statistical Methods, open access, pseudo-random generators, simulation, Statistical Science, Università Ca' Foscari Venezia, Venice on March 11, 2024 by xi'an
snowballs in summer
Posted in Books, Statistics with tags arXiv, convergence, MCMC, nested sampling, posterior sampling, simulation, snow on September 13, 2023 by xi'an
A new arXival on nested sampling, Snowballing Nested Sampling by Johannes Buchner, just appeared. The idea behind this short note is to increase the number of “live” points at each iteration. (How?! Depending on how the different additions are dependent, the effective sample size will vary.) This exacerbates the tendency of the algorithm to concentrate on high density regions.
“Loosely speaking, each dead point from a run with K is split into two dead points from a run with K′ live points. The noise in the nested sampling estimate due to more dead points is also reduced, because the variance is inversely proportional to K.”
The following line is most puzzling (K being the number of live points and M the number of MCMC steps to simulate from the restricted prior):
“Based on this [argument], K → ∞ with fixed M achieves the properties of M → ∞ with fixed K.”
which connects with the ambiguity of running the MCMC move at each nested iteration a certain number M of steps, even though I always thought a single step was theoretically enough. In practice, this single step may further take forever if no trick is available for simulating from the constrained prior. And when K increases, so does the correlation unless iid sampling can be implemented, which does not sound realistic.
online approximate Bayesian learning
Posted in Statistics with tags AMIS, approximate MCMC, Bayesian learning, consistency, convergence, ibis, sequential Monte Carlo, state space model on September 25, 2020 by xi'anMy friends and coauthors Matthieu Gerber and Randal Douc have just arXived a massive paper on online approximate Bayesian learning, namely the handling of the posterior distribution on the parameters of a state-space model, which remains a challenge to this day… Starting from the iterated batch importance sampling (IBIS) algorithm of Nicolas (Chopin, 2002) which he introduced in his PhD thesis. The online (“by online we mean that the memory and computational requirement to process each observation is finite and bounded uniformly in t”) method they construct is guaranteed for the approximate posterior to converge to the (pseudo-)true value of the parameter as the sample size grows to infinity, where the sequence of approximations is a Cesaro mixture of initial approximations with Gaussian or t priors, AMIS like. (I am somewhat uncertain about the notion of a sequence of priors used in this setup. Another funny feature is the necessity to consider a fat tail t prior from time to time in this sequence!) The sequence is in turn approximated by a particle filter. The computational cost of this IBIS is roughly in O(NT), depending on the regeneration rate.
ABC with Gibbs steps
Posted in Statistics with tags ABC, ABC-Gibbs, Approximate Bayesian computation, Bayesian inference, bois de Boulogne, compatible conditional distributions, contraction, convergence, ergodicity, France, Gibbs sampler, hierarchical Bayesian modelling, incompatible conditionals, La Défense, Paris, stationarity, tolerance, Université Paris Dauphine on June 3, 2019 by xi'an
With Grégoire Clarté, Robin Ryder and Julien Stoehr, all from Paris-Dauphine, we have just arXived a paper on the specifics of ABC-Gibbs, which is a version of ABC where the generic ABC accept-reject step is replaced by a sequence of n conditional ABC accept-reject steps, each aiming at an ABC version of a conditional distribution extracted from the joint and intractable target. Hence an ABC version of the standard Gibbs sampler. What makes it so special is that each conditional can (and should) be conditioning on a different statistic in order to decrease the dimension of this statistic, ideally down to the dimension of the corresponding component of the parameter. This successfully bypasses the curse of dimensionality but immediately meets with two difficulties. The first one is that the resulting sequence of conditionals is not coherent, since it is not a Gibbs sampler on the ABC target. The conditionals are thus incompatible and therefore convergence of the associated Markov chain becomes an issue. We produce sufficient conditions for the Gibbs sampler to converge to a stationary distribution using incompatible conditionals. The second problem is then that, provided it exists, the limiting and also intractable distribution does not enjoy a Bayesian interpretation, hence may fail to be justified from an inferential viewpoint. We however succeed in producing a version of ABC-Gibbs in a hierarchical model where the limiting distribution can be explicited and even better can be weighted towards recovering the original target. (At least with limiting zero tolerance.)
efficient adaptive importance sampling
Posted in Books, Statistics with tags AMIS, convergence, generalised moments, importance sampling, Kullback-Leibler divergence, martingales, oracle inequalities, population Monte Carlo on June 22, 2018 by xi'anBernard Delyon and François Portier just recently arXived a paper on population or evolutionary importance sampling, pointed out to me by Víctor Elvira. Changing the proposal or importance sampler at each iteration. And averaging the estimates across iterations, but also mentioning AMIS. While drawing a distinction that I do not understand, since the simulation cost remains the same, while improving the variance of the resulting estimator. (But the paper points out later that their martingale technique of proof does not apply in this AMIS case.) Some interesting features of the paper are that
- convergence occurs when the total number of simulations grows to infinity, which is the most reasonable scale for assessing the worth of the method;
- some optimality in the oracle sense is established for the method;
- an improvement is found by eliminating outliers and favouring update rate over simulation rate (at a constant cost). Unsurprisingly, the optimal weight of the t-th estimator is given by its inverse variance (with eqn (13) missing an inversion step). Although it relies on the normalised versions of the target and proposal densities, since it assumes the expectation of the ratio is equal to one.
When updating the proposal or importance distribution, the authors consider a parametric family with the update in the parameter being driven by moment or generalised moment matching, or Kullback reduction as in our population Monte Carlo paper. The interesting technical aspects of the paper include the use of martingale and empirical risk arguments. All in all, quite a pleasant surprise to see some follow-up to our work on that topic, more than 10 years later.
