Hurray, our signed mixture simulation paper has been accepted by Statistics & Computing! If Og’s readers remember my earlier post about this problem, things get surprisingly more complicated when the mixture weights can take negative values. For instance, the naïve solution consisting in first simulating from the associated mixture of positive weight components and then using an accept-reject step may prove highly inefficient since the overall probability of acceptance can get arbitrarily close to zero. Substituting to this naïve version, we construct an alternative accept-reject scheme based on pairing positive and negative components as efficiently as possible, partitioning the real line, and finding tighter upper and lower bounds on positive and negative components, respectively, towards yielding a higher acceptance rate on average. In retrospect, the problem was beyond the reach of the undergraduate students we supervised (pre-COVID) on a research internship!
Archive for acceptance probability
positive response to negative mixtures
Posted in pictures, Running with tags academic publisher, accept-reject algorithm, acceptance, acceptance probability, article, COVID-19, inverse cdf, master project, PSL Research University, publication, signed mixture, simulation, Statistics and Computing, Université Paris Dauphine, ziggurat algorithm on December 17, 2024 by xi'anmaximal 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.
informed proposals for local MCMC in discrete spaces
Posted in Books, Kids, Statistics, University life with tags acceptance probability, Barker's algorithm, discrete distribution, informed proposals, JASA, local MCMC, Markov kernel, Peskun ordering, Rao-Blackwellisation, stationarity, vanilla Rao-Blackwellisation on April 17, 2020 by xi'an
Last year Giacomo Zanella published a paper entitled informed proposals for local MCMC in discrete spaces in JASA. Which I had missed somehow and only discovered through another paper, and which we recently discussed at Paris-Dauphine with graduate students, marooned by COVID-19 . Probability targets in discrete spaces are intrinsically hard[er] to simulate in my opinion if only because there is no natural distance, hence no natural neighbourhood. A random walk proposal like the reference kernel in the paper is not directly calibrated. Without demarginalisation there is neither a clear version of calculus for implementing MALA or HMC. What indeed is HMC on a discrete space? If this requires “embedding the binary space in a continuous space”, it does not sound very enticing if the construct is context dependent.
“This would allow for more moves to be accepted and longer moves to be performed, thus improving the algorithm’s efficiency.”
A interesting aspect of the paper is that for near atomic transition kernels K, informally for small σ’s, the proposal switch to Q finds target x normalising constant as new stationary and close to the actual target. Which incidentally reminded me of our vanilla Rao-Blackwellisation with Randal Douc. This however begets the worry that it may prove unwieldy in continuous cases, as except for Gaussian kernels, the proposal switch to Q may prove intractable and requires further MCMC steps, in a form of infinite regress. Plus a musing that, were the original kernel K to be replaced with the new Q, another informed proposal transform could be applied to Q. Further infinite regress…
“[The optimality of the Metropolis-Hastings choice of acceptance probability] does not translate to the context of balancing functions.”
The paper indeed exhibits a setting that is rehabilitating Barker’ (1965) version of the acceptance probability, but I never was very much convinced there was a significant difference in using one or the other. During our virtual (?) discussion, we also wondered at the adaptive abilities of the approach, e.g., selecting among a finite family of g’s (according to which criterion) or parameterising g towards an optimal choice of its parameter. And at the capacity for Rao-Blackwellisation since the proposal have to consider the entire set of neighbours prior to moving to a likely one.
high dimension Metropolis-Hastings algorithms
Posted in Books, Kids, Mountains, pictures, R, Statistics with tags acceptance probability, curse of dimensionality, high dimensions, MCMC, Metropolis-Hastings algorithm, Monte Carlo Statistical Methods, unmlaut on January 26, 2016 by xi'an
When discussing high dimension models with Ingmar Schüster Schuster [blame my fascination for accented characters!] the other day, we came across the following paradox with Metropolis-Hastings algorithms. If attempting to simulate from a multivariate standard normal distribution in a large dimension, when starting from the mode of the target, i.e., its mean γ, leaving the mode γis extremely unlikely, given the huge drop between the value of the density at the mode γ and at likely realisations (corresponding to the blue sequence). Even when relying on the very scale that makes the proposal identical to the target! Resorting to a tiny scale like Σ/p manages to escape the unhealthy neighbourhood of the highly unlikely mode (as shown with the brown sequence).
Here is the corresponding R code:
[sourcecode language=”r” gutter=”false”]
p=100
T=1e3
mh=mu #mode as starting value
vale=rep(0,T)
for (t in 1:T){
prop=mvrnorm(1,mh,sigma/p)
if (log(runif(1))<logdmvnorm(prop,mu,sigma)-
logdmvnorm(mh,mu,sigma)) mh=prop
vale[t]=logdmvnorm(mh,mu,sigma)}
[/sourcecode]
a programming bug with weird consequences
Posted in Kids, pictures, R, Statistics, University life with tags acceptance probability, convergence assessment, heavy-tail distribution, independent Metropolis-Hastings algorithm, Metropolis-Hastings algorithm, normal distribution, Student's t distribution on November 25, 2015 by xi'anOne student of mine coded by mistake an independent Metropolis-Hastings algorithm with too small a variance in the proposal when compared with the target variance. Here is the R code of this implementation:
[sourcecode language=”r” gutter=”false”]
#target is N(0,1)
#proposal is N(0,.01)
T=1e5
prop=x=rnorm(T,sd=.01)
ratop=dnorm(prop,log=TRUE)-dnorm(prop,sd=.01,log=TRUE)
ratav=ratop[1]
logu=ratop-log(runif(T))
for (t in 2:T){
if (logu[t]>ratav){
x[t]=prop[t];ratav=ratop[t]}else{x[t]=x[t-1]}
}
[/sourcecode]
It produces outputs of the following shape
which is quite amazing because of the small variance. The reason for the lengthy freezes of the chain is the occurrence with positive probability of realisations from the proposal with very small proposal density values, as they induce very small Metropolis-Hastings acceptance probabilities and are almost “impossible” to leave. This is due to the lack of control of the target, which is flat over the domain of the proposal for all practical purposes. Obviously, in such a setting, the outcome is unrelated with the N(0,1) target!
It is also unrelated with the normal proposal in that switching to a t distribution with 3 degrees of freedom produces a similar outcome:
It is only when using a Cauchy proposal that the pattern vanishes:
