arXiv:2509.26175v1 Announce Type: new
Abstract: The Metropolis-within-Gibbs (MwG) algorithm is a widely used Markov Chain Monte Carlo method for sampling from high-dimensional distributions when exact conditional sampling is intractable. We study MwG with Random Walk Metropolis (RWM) updates, using proposal variances tuned to match the target’s conditional variances. Assuming the target $pi$ is a $d$-dimensional log-concave distribution with condition number $kappa$, we establish a spectral gap lower bound of order $mathcal{O}(1/kappa d)$ for the random-scan version of MwG, improving on the previously available $mathcal{O}(1/kappa^2 d)$ bound. This is obtained by developing sharp estimates of the conductance of one-dimensional RWM kernels, which can be of independent interest. The result shows that MwG can mix substantially faster with variance-adaptive proposals and that its mixing performance is just a constant factor worse than that of the exact Gibbs sampler, thus providing theoretical support to previously observed empirical behavior.