Weak Poincaré inequalities for Markov chains: Theory and applications

We investigate the application of weak Poincaré inequalities (WPI) to Markov chains to study their rates of convergence and to derive complexity bounds. At a theoretical level we investigate the necessity of the existence of WPIs to ensure L2-convergence, in particular by establishing equivalence with the resolvent uniform positivity-improving (RUPI) condition and providing a counterexample. From a more practical perspective, we extend the celebrated Cheeger’s inequalities to the subgeometric setting, and further apply these techniques to study random-walk Metropolis algorithms for heavy-tailed target distributions and to obtain lower bounds on pseudo-marginal algorithms.