Archive for coupling
Pierre Jacob awarded an ERC-Consolidator grant [congrats!]
Posted in pictures, Statistics, University life with tags Council of the European Union, coupling, ERC, ERC Consolidator Grant, ESSEC, EU, European Research Council, European Union, Markov chain Monte Carlo, MCMC, Pierre Jacob, scalable MCMC on December 6, 2024 by xi'an
d≥3 strikes again
Posted in Statistics, University life with tags Boltzmann-Grad limit, Brownian motion, CLT, coupling, Markov process, null recurrence, seminar, Stein effect, transience, University of Bristol, Wiener process on April 23, 2024 by xi'an
Yesterday, Bálint Tóth (University of Bristol and Alfréd Rényi Institute of Mathematics) came to Paris Dauphine for a seminar on the Botlzmann-Grad limit and the existence of a central (double) limit theory. Which was somewhat related with the above video of an earlier seminar, albeit without the first part on the historical roots of the problem. This was a brilliant talk as quite accessible to the entirety of the lab, while providing detailed entries on the mechanism leading to the CLT, in particular the substitution of the physical process by a Markovian(ised) process that stayed closed enough to the original for long enough, a sort of (anti-)coupling idea I had never met before. The other (personally) striking feature of the seminar was the occurrence of the boundary d=3 on the dimension of the process, The same boundary as in the Stein phenomenon (and the difference from recurrent to transient in random walks). But I could not see a clear connection with the present challenge.
coupling, donkeys, coins & fish meet in Paris
Posted in Statistics with tags #LedByDonkeys, Arianna Rosenbluth, Arthur Dempster, Bernoulli-Laplace diffusion, Charlie Geyer, coupling, coupling inequality, Dempster-Shafer theory, Gérard Letac, Gibbs sampler, Markov chains, MCMC convergence, number of iterations, optimal coupling, Paris, perfect sampling, random walk, rate of convergence, Séminaire Parisien de Statistique, seminar, slide, STAN, Valencia conferences on March 22, 2021 by xi'an
MCMC for conditional Bernoullis
Posted in Books, Statistics, University life with tags Bernoulli distribution, Constrained Monte Carlo, coupling, coupling from the past, quicksort, simulation on February 22, 2021 by xi'an
Jeremy Heng, Pierre Jacob [currently in Paris!] and Nianqiao Ju are in a recent arXival considering the simulation of a conditional Bernoulli, namely generating a vector of N Bernoullis with different probabilities under the constraint that their sum is fixed as I. Rather than going for a perfect simulator, with cost O(NI), they opt for the simplest of MCMC samplers, where a 0 and a 1 entries are exchanged at random. In connection with a recent spate of MCMC works using coupling, they establish convergence in O(N log N) steps, even when the probabilities are arbitrarily close to zero and one. Including the case when they are Uniformly generated. From a mundane perspective, I wonder at the appeal of using the probabilities to select the exchange pair. I realise sorting the probabilities is already of order O(N log N) avoiding selecting highly probable 1’s and highly probable 0’s should speed up converge, unless the gain is negligible. And to link MCMC and exact simulation in this setting, what would the cost of perfect sampling by sampling from the past be? Presumably much higher since there is little chance a total ordering can be found on the starting states.
maximal couplings of the Metropolis-Hastings algorithm
Posted in Statistics, University life with tags accept-reject algorithm, acceptance probability, Barker's algorithm, coupling, Crete, Leonid Vaseršteĭn, maximal coupling, Metropolis-Hastings algorithm, Metropolis-Hastings algorithms, Wasserstein distance on November 17, 2020 by xi'an
As a sequel to their JRSS B paper, John O’Leary, Guanyang Wang, and [my friend, co-author and former student!] Pierre E. Jacob have recently posted a follow-up paper on maximal coupling for Metropolis-Hastings algorithms, where maximal is to be understood in terms of the largest possible probability for the coupled chains to be equal, according to the bound set by the coupling inequality. It made me realise that there is a heap of very recent works in this area.
A question that came up when reading the paper with our PhD students is whether or not the coupled chains stay identical after meeting once. When facing two different targets this seems inevitable and indeed Lemma 2 seems to show that no. A strong lemma that does not [need to] state what happens outside the diagonal Δ.
One of the essential tricks is to optimise several kinds of maximal coupling, incl. one for the Bernoullesque choice of moving, as given on p.3.
Algorithm 1 came as a novelty to me as it first seemed (to me!) the two chains may never meet, but this was before I read the small prints of the transition (proposal) kernel being maximally coupled with itself. While Algorithm 2 may be the earliest example of Metropolis-Hastings coupling I have seen, namely in 1999 in Crete, in connection with a talk by Laird Breyer and Gareth Roberts at a workshop of our ESSS network. As explained by the authors, this solution is not always a maximal coupling for the reason that
min(q¹.q²) min(α¹,α²) ≤ min(q¹α¹,q²α²)
(with q for the transition kernel and α for the acceptance probability). Lemma 1 is interesting in that it describes the probability to un-meet (!) as the surface between one of the move densities and the minimum of the two.
The first solution is to couple by plain Accept-Reject with the first chain being the proposed value and if rejected [i.e. not in C] to generate from the remainder or residual of the second target, in a form of completion of acceptance-rejection (accept when above rather than below, i.e. in A or A’). This can be shown to be a maximal coupling. Another coupling using reflection residuals works better but requires some spherical structure in the kernel. A further coupling on the acceptance of the Metropolis-Hastings move seems to bring an extra degree of improvement.
In the introduction, the alternatives about the acceptance probability α(·,·), e.g. Metropolis-Hastings versus Barker, are mentioned but would it make a difference to the preferred maximal coupling when using one or the other?
A further comment is that, in larger dimensions, I mean larger than one!, a Gibbsic form of coupling could be considered. In which case it would certainly decrease the coupling probability but may still speed up the overall convergence by coupling more often. See “maximality is sometimes less important than other properties of a coupling, such as the contraction behavior when a meeting does not occur.” (p.8)
As a final pun, I noted that Vaserstein is not a typo, as Leonid Vaseršteĭn is a Russian-American mathematician, currently at Penn State.
