Archive for spectral gap

Information Geometry, Privacy and Monte Carlo workshop, ISM, 6-7 July 2026

Posted in Mountains, pictures, Statistics, Travel, University life with tags , , , , , , , , , , , , , , , , , , , , , , , , , , , , , on July 8, 2026 by xi'an

Although some of the participants of the workshop left for ICML²⁶ or the 4th Bayesian Nonparametrics networking workshop, both taking place in Seoul this week, the following days of the workshop were as intense and captivating as the first two, with a return to MCMC “basics” but also more geometrical and maethematical aspects.

To wit, Radu Craiu talked on MCMC for DAG processes with revisiting the landmark paper of Geyer & Møller (1994) on replacing discrete time MCMC with a birth & death process and cutting on complexity by restricted set imposing some edges, set from a redetermined run. Galin Jones presented some (novel) Lower bounds on the rate of convergence for accept-reject-based Markov chains in Wasserstein and total variation distances, showing the massive dependence of the convergence rates on the scaling factors of the proposal, especially in relation with the data size n when considering posterior targets. James Flegal discussed Simultaneous confidence bands for (MC)MC simulations that aimed at returning a confidence band on marginal density estimates; it reminded me of our 2005 simultaneous coverage paper with Wilfrid Kendall and Jean-Michel Marin and got me wondering why not going full Bayes by adopting a GP prior modelling.

Michiko Okudo spoke about Applications of information geometry to Bayesian prediction and estimation in curved exponential families, returning to point estimation with a mention of Marchand & Strawderman (2025)! Marta Catalano presented results on Distances on random measures for Bayesian nonparametrics, involving random measures like Dirichlet processes, that was connected with Hugo Lavenant’s talk at ISBA, but more focussed on the mathematical aspects albeit algorithmic aspects were mentioned. With highly intuitive arguments (making the accronym WoW for Wasserstein on Wasserstein quite appropriate!).

Takemasa Miyoshi made a presentation of the Osaka Expo 2025 Weather [prediction] on Fugaku: Synergizing Big Data Assimilation and AIRIKEN, with impressive predictive abilities achieved using RIKEN super-computer (but no technical details). Björn Sprung exposed how they obtained Dimension-independent MCMC [convergence speed] on the sphere, using retroprojections of random walks outside the sphere (as in Frederica’s talk yesterday), which comes as a surprise given the deterioration of random walk performances with increasing dimensions.

Geoffrey Wolfer’s Characterization of Exponential Families of Lumpable Stochastic Matrices was a very mathematical talk set firmly in the Japanese probability school, going too fast with too many new definitions for my abilities (and attention span) but setting the scene for exponential families on stochastic matrices and being one of the rate cases I eve rsaw lumpability à la Kemeny & Snell (1983) mentionned! Daniel Paulin followed with Stochastic gradient Langevin dynamics: convergence and bias, via an UBU algorithm using splitting integrators that sound very much like the leapfrog for an HMC with unscented Langevin steps where the gradient is replaced with an unbiased estimator (connecting to the poster of Jack Jewson on Sunday, when he mentioned the opposition between pseudo-marginal MCMC, requiring an unbiased estimator of the target, and schemes using the log-target, for which unbiased estimators of the log can be used). Shahab Asoodeh concluded Monday with Recent Advances in Metropolis-Hastings Algorithms, actually developing multi-marginal coupling with freely coupling chains.

On the final morning, Weiming Feng showed results about a Faster mixing of the Jerrum-Sinclair chain, reminding me of the 1989 paper, with a Metropolis algorithm on graphs allowing for specific mixing time results with spectral gap and log-Sobolev inequalities (and a Poincáre typo!). Michael Choi produced convergence properties by Optimising two-block averaging kernels to speed up Markov chains, with a (rather formal) Gibbs sampler on orbits (in a finite state space) again connecting to Jerrum.

Yuga Iguchi discussed Diffusion models for high-dimensional clustered data: Intrinsic-dimension adaptivity via Bayesian classification, producing a rigorous characterisation of the phase transition property of their diffusion denoising probabilistic model when the target is a mixture with separation constraints on the components, phase transition meaning that eventually concentrating on a single cluster as the forward diffusion moves toward pure noise. (Although being fully awake, having mostly recovered from the longest jetlag period ever, I had trouble understanding the process per se.) Edric Tam discussed Fundamental Limits to Neural Monte Carlo by returning to standard variance reduction techniques like stratifying and antithetic-ying (!) and applying normalising flows on them. Victor Elvira concluded the meeting by Rethinking self-normalized importance sampling, with a fun interlude of Eric Veach’s Oscars joke, but I unfortunately had to miss the end to gather my bags and leave for the Alps! But Victor should be in Paris in the Fall and hopfefully giving a talk at mostly Monte Carlo!

This workshop was most efficiently supported by the Institute of Statistical Mathematics and its staff, including over the weekend days! On a personal foodie note, the coffee breaks featured the same unbelievable matcha cakes (“Chez Kobe”) as at ISBA²⁶, we enjoyed a terrific full tofu dinner at Umenohana Tachikawa shop and there were plenty French (or pseudo-French) bakeries in Tachekima, enough to find rye (raimugi) bread for breakfast!

explicit convergence bounds for Metropolis

Posted in Books, Statistics, University life with tags , , , , , , , , on March 2, 2026 by xi'an

C\,L\, d\,\sigma^{2}\, e^{-2\, L\, d\,\sigma^{2}}\,\frac{m}{L}\,\frac{1}{d}\leqslant\gamma_{P}\leqslant\min\left\{ \frac{1}{2}\, L\,\sigma^{2},\left(1+m\,\sigma^{2}\right)^{-d/2}\right\}

Last week, our MCMC reading group in PariSanté started reading Explicit convergence bounds for Metropolis Markov chains by my friends Christophe Andrieu, Anthony Lee, Sam Power, and Andi Wang (University of Warwick), recently published in the Annals of Applied Probability. The paper is centred on the bound above. Which may sound cryptic but gives a non-asymptotic explicit bound on the spectral gap γ, when the potential of the target is L-smooth, m-strongly convex and twice continuously differentiable, in dimension d, with a proposal being the Gaussian random walk with scale σ.  With C = 1.972 10⁻⁴. if “possibly a few orders of magnitude larger”. This characterisation of the spectral gap leads to a sharper identification of d⁻¹ as the proper rate for σ². Other consequences are finding the order of the number of simulations to reach a χ² distance of ε,

e^{2\,\varsigma}\,\varsigma\,\kappa\, d\,\left\{ \log d+\log\kappa-\log\varepsilon\right\}

when κ is the condition number L/m and

\sigma^2=\varsigma\, L^{-1}\, d^{-1}

And a bound on the ergodic averages

{\rm var} (Pf )\leqslant10141\,\varsigma\,e^{2\,\varsigma}\,\kappa\, d\,\left\Vert f\right\Vert _{2}^{2}

The technicity of the proof is quite involved, with a special kind of coupling, to the point the authors provide a roadmap, as reproduced left.

Elo rating systems via Markov Chains

Posted in pictures, Running, Statistics, University life with tags , , , , , , , , , , , on December 18, 2025 by xi'an

In preparation for meeting with a national sport association towards a Bayesian approach to ranking (I can only confirm this not for volleyball!), I was searching for advanced studies of the Elo (not ELO!) rating system and came across this 2024 arXival by Sam Olesker-Taylor (U Warwick) and Luca Zanetti. Where they analyse the online behaviour of the player ratings and their convergence (in Wasserstein distance), with fairly intricate proofs.

“Elo is not a reversible Markov chain and, while it has a unique stationary distribution, assuming a minor and natural condition, it does not converge to it in total variation.”

The analysis is based on the Bradley–Terry–Luce model of the probability of player i winning a game against player j. Which amounts to a logit or sigmoïd transform of the difference between the players’ true ratings. The practical Elo updates amounts to one stochastic gradient step for the associated likelihood. The authors also propose a random allocation of players into pairs that achieves optimal convergence to the true rating, by maximising the spectral gap of the allocation matrix. Although I did not spot how to derive it in practice.

exact yet private MCMC

Posted in Statistics with tags , , , , , , , , , , , 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.

inefficiency of data augmentation for large samples

Posted in Books, pictures, Running, Statistics, Travel, University life with tags , , , , , , , , , , on May 31, 2016 by xi'an

On Monday, James Johndrow, Aaron Smith, Natesh Pillai, and David Dunson arXived a paper on the diminishing benefits of using data augmentation for large and highly imbalanced categorical data. They reconsider the data augmentation scheme of Tanner and Wong (1987), surprisingly not mentioned, used in the first occurrences of the Gibbs sampler like Albert and Chib’s (1993) or our mixture estimation paper with Jean Diebolt (1990). The central difficulty with data augmentation is that the distribution to be simulated operates on a space that is of order O(n), even when the original distribution covers a single parameter. As illustrated by the coalescent in population genetics (and the subsequent intrusion of the ABC methodology), there are well-known cases when the completion is near to impossible and clearly inefficient (as again illustrated by the failure of importance sampling strategies on the coalescent). The paper provides spectral gaps for the logistic and probit regression completions, which are of order a power of log(n) divided by √n, when all observations are equal to one. In a somewhat related paper with Jim Hobert and Vivek Roy, we studied the spectral gap for mixtures with a small number of observations: I wonder at the existence of a similar result in this setting, when all observations stem from one component of the mixture, when all observations are one. The result in this paper is theoretically appealing, the more because the posteriors associated with such models are highly regular and very close to Gaussian (and hence not that challenging as argued by Chopin and Ridgway). And because the data augmentation algorithm is uniformly ergodic in this setting (as we established with Jean Diebolt  and later explored with Richard Tweedie). As demonstrated in the  experiment produced in the paper, when comparing with HMC and Metropolis-Hastings (same computing times?), which produce much higher effective sample sizes.