My friends Filipo Ascolani, Gareth Roberts, and Giacomo Zanella recently arXived a paper on the scalability (in the dimension) of Gibbs and Metropolis-within-Gibbs sampling schemes. Which is celebrating a sort of return of the Gibbs sampler as a dimension resistant device (when compared with other solutions), witness the following extract:
“….we provide bounds on the approximate conductance of a generic coordinate-wise scheme in terms of the corresponding quantity for the Gibbs sampler. Working with the approximate version of the conductance is crucial for our purposes and subsequent applications. The general theory naturally applies to Metropolis-within-Gibbs schemes, such as those targeting conditionally log-concave distributions. In the second part, we analyze performances of coordinate-wise samplers for relevant statistical applications, combining the bounds discussed above with specific model properties, statistical asymptotics and some novel auxiliary results on approximate conductances and perturbation of Markov operators. Much emphasis is placed on coordinate-wise schemes for generic two-levels hierarchical models with non-conjugate likelihood for which we are able to prove dimension-free behaviour of total variation mixing times, under warm and feasible starts.” F. Ascolani, G.O. Roberts, and G. Zanella
Here, M -warm starts meaning a starting measure bounded by the target, i.e., not too far in the tails, while conductance Φ is a measure related with the probability that the Markov chain exits an arbitrary set A in one step, given that it starts from the target π restricted to A. The paper quantifies the loss of efficiency incurred by substituting an exact Gibbs update with a π¹-invariant one, e.g. M-within-G, that is
following from
In the (rather unrealistic) case of an independent Metropolis-within-Gibbs proposal enjoying an upper bound M on the Radon-Nykodym derivative between target and kernel, the conductance of Metropolis-within-Gibbs is at least one M-th of the conductance of Gibbs, ie a constant slowdown relative to exact Gibbs if the dimensionality is fixed but arbitrary.
The paper further studies a hierarchical Bayes model when the number J of groups goes to infinity and only top (of the hierarchy) parameter is of interest. In that setting, only two requirements need be satisfied for the Metropolis-within-Gibbs kernel P to mix fast: namely that the Gibbs kernel G mixes fast and that the conditional conductance of P around true ψ is good enough. A further point of relevance is the demonstrated O(J) computational cost, ie the Metropolis-within-Gibbs algorithm with kernel P produces a sample with ϵ-accuracy in TV distance with O(J) cost when initialized from a warm start, a better magnitude than alternatives like the Metropolis-Adjusted Langevin (MALA) and the Hamiltonian Monte Carlo (HMC) algorithms. When checking for connections with other papers, I came across the nearly completed book by Sinho Chewi on long-concave sampling, which seems to be exploring similar ground.
