Characterizing limits and opportunities in speeding up Markov chain mixing - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Stochastic Processes and their Applications Année : 2021

Characterizing limits and opportunities in speeding up Markov chain mixing

Résumé

Lifted Markov chains are Markov chains on graphs with added local "memory" and can be used to mix towards a target distribution faster than their memoryless counterparts. Upper and lower bounds on the achievable performance have been provided under specific assumptions. In this paper, we analyze which assumptions and constraints are relevant for mixing, and how changing these assumptions affects those bounds. Explicitly, we find that requesting mixing on either the original or the full lifted graph, and allowing for reducible lifted chains or not, have no essential influence on mixing time bounds. On the other hand, allowing for suitable initialization of the lifted dynamics and/or imposing invariance of the target distribution for any initialization do significantly affect the convergence performance. The achievable convergence speed for a lifted chain goes from diameter-time to no acceleration over a standard Markov chain, with conductance bounds limiting the effectiveness of the intermediate cases. In addition, we show that the relevance of imposing ergodic flows depends on the other criteria. The presented analysis allows us to clarify in which scenarios designing lifted dynamics can lead to better mixing, and provide a flexible framework to compare lifted walks with other acceleration methods.

Dates et versions

hal-03097637 , version 1 (05-01-2021)

Identifiants

Citer

Simon Apers, Francesco Ticozzi, Alain Sarlette. Characterizing limits and opportunities in speeding up Markov chain mixing. Stochastic Processes and their Applications, 2021, 136, pp.Pages 145-191. ⟨10.1016/j.spa.2021.03.006⟩. ⟨hal-03097637⟩
27 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More