Archive for reversibility
mostly MC’ruary [14 Feb 2025]
Posted in Books, Statistics, University life with tags diffusions, exact sampling, irreducibility, Issy-les-Moulineaux, MCMC, Mostly MC, Mostly MCMC seminar, Ocean, Paris, PariSanté campus, PDMP, Porte de Versailles, reversibility, seminar on February 12, 2025 by xi'an
thou shalt not slice thine spaghetti
Posted in Statistics with tags geodesics, manifold, pasta machine, reversibility, Riemann manifold, Riemannian measure, seminar, shrinkage, slice sampler, spaghetti, University of Warwick on May 1, 2024 by xi'an
This 2023 work on Slice sampler on manifolds, as presented in the algorithms seminar in Warwick during a recent visit of by Mareike Hasenpflug, consists in designing and validating slice samplers for distributions on manifolds. It is mildly connected to some current work on MCMC algorithms on manifolds through coupling techniques by [my friends & coauthors] Elena Bortolado, Pierre Jacob, and Robin Ryder (who escape temporarily the manifold at each step). As in Neal (2003), uniform draws from the (super)level sets are replaced there with one-step Markov moves within the level set, that is, slice sampler moves. The slice sampler actually generalises Neal’s (2003) stepping-out and shrinkage steps rather closely. Based on the standard notion of the Riemannian measure induced by the very structure of the manifold, the model therein assumes that the simulation target is available as a closed-form if unormalised density p(x) against that measure, meaning that problems where the distribution is a push-forward one induced by a mapping onto the manifold are not necessary manageable. The slide sampler is decomposed into choosing (1-dimensional) geodesics defined by the manifold (and generalising great circles), uniformly, and then sampling by this one-dimensional slice sampling over the geodesic, under the level set constraint. Meaning that those geodesics must be manageable enough. (Note that the concept of stepping-out does not mean that the chain ever escapes from the manifold.) Demonstrating the validity and reversibility proves a challenging task.
exact yet private MCMC
Posted in Statistics with tags Arrowleaf Cellars, differential privacy, ergodicity, ICML 2023, Lake Okanagan, MCMC, Metropolis-Hastings algorithm, Okanagan vineyards, Poisson subsampling, reversibility, spectral gap, stationarity on August 9, 2023 by xi'an
“at each iteration, DP-fast MH first samples a minibatch size and checks if it uses a minibatch of data or full-batch data. Then it checks whether to require additional Gaussian noise. If so, it will instantiate the Gaussian mechanism which adds Gaussian noise to the energy difference function. Finally, it chooses accept or reject θ′ based on the noisy acceptance probability.”
Private, Fast, and Accurate Metropolis-Hastings for Large-Scale Bayesian Inference is an(other) ICML²³ paper, written by Wanrong Zhang and Ruqi Zhang. Who are running MCMC under DP constraints. For one thing, they compute the MH acceptance probability with a minibatch, which is Poisson sampled (in order to guarantee privacy). It appears as a highly calibrated algorithm (see, e.g., Algorithm 1). Under the assumption (1) that the difference between individual log densities for two values of the parameter is upper bounded (in the data), differential privacy is established as failing to detect for certain a datapoint from the MCMC output. Interestingly, the usual randomisation leading to pricacy is operated on the energy level, rather than on observations or summary statistics, although this may prove superfluous when there is enough randomness provided by the MH step itself: “inherent privacy guarantees in the MH algorithm”
“when either the privacy hyperparameter ϵ or δ becomes small, the convergence rate becomes small, characterizing how much the privacy constraint slows down the convergence speed of the Markov chain”
The major results of the paper are privacy guarantees (at each iteration) and preservation of the proper target distribution, in contrast with earlier versions. In particular, adding the Gaussian noise to the energy does not impact reversibility. (Even though I am not 100% sure I buy the entire argument about reversibility (in Appendix C) as it sounds too easy!) The authors even achieve a bound on the relative spectral gaps.
non-reversibility in discrete spaces
Posted in Books, Statistics, University life with tags birth-and-death process, coordinate sampler, JASA, jump process, Markov chain, non-reversible diffusion, PDMP, Peskun ordering, reversibility, Zig-Zag on January 3, 2020 by xi'an
Following a recent JASA paper by Giacomo Zanella (which I have not yet read but is discussed on this blog), Sam Power and Jacob Goldman have recently arXived a paper on Accelerated sampling on discrete spaces with non-reversible Markov processes, where they use continuous-time, non-reversible algorithms à la PDMP, even though differential equations do not exist on discrete spaces. More specifically, they devise discrete versions of the coordinate sampler and of the Zig-Zag sampler, using Markov jump processes instead of differential equations, with detailed balance on the jump rate rather than the Markov kernel. A use of jump processes originating at least from Peskun (1973) and connected with MCMC algorithms in Matthew Stephens‘ 1999 PhD thesis. A neat thing about discrete settings is that the jump process can be implemented with no discretisation! However, as we noticed when working on birth-and-death processes with Olivier Cappé and Tobias Rydèn, there is a potential for disastrous implementation if an infinite sequence of instantaneous moves (out of zero probability states) is proposed.
The authors make the further assumption(s) that the discrete space is endowed with a graphical structure with a group G acting upon this graph, with an involution keeping the target (or a completion of the original target) invariant. In this framework, reversibility amounts to repeatedly using (group) generators þ with a low order (as in Bayesian variable selection, binary spin systems, where þ.þ=id, and other permutation problems), since they bring the chain back to its starting point. Their first sampler is called a Tabu sampler for avoiding such behaviour, forcing the next step to use other generators þ in the generator set Þ thanks to a binary auxiliary variable that partitions Þ into forward vs backward moves. For high order generators, the discrete coordinate and Zig-Zag samplers are instead repeatedly using the same generator (although it is unclear to me why this is beneficial, given that neither graph nor generator is not necessarily linked with the target). With the coordinate sampler being again much cheaper since it only looks at one direction in the generator group.
The paper contains a range of comparisons with (only) Zanella’s sampler, some presenting heavy gains in terms of ESS. Including one on hundreds of sensors in a football stadium. As I am not particularly familiar with these examples, except for the Bayesian variable selection one, I found it rather hard to determine whether or not the compared samplers were indeed exploring the entirety of the (highly complex and highly dimensional) target. The collection of examples is however quite rich and support the use of such non-reversible schemes. It may also be that the discrete nature of the target could facilitate the theoretical study of their convergence properties.
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.]
