On Shorter Tempering Paths in Non-Reversible Parallel tempering

Abstract

Parallel tempering (PT) is a classical Markov chain Monte Carlo algorithm for sampling from challenging distributions. It employs a sequence of distributions interpolating between a simple reference distribution and a complex target distribution to aid sampling at the target. Non-reversible parallel tempering (NRPT) is a variant of PT that has been shown to outperform standard, reversible variants of PT in past work. In NRPT, the performance of the algorithm increases with the number of parallel chains but eventually saturates at a level determined by the global communication barrier, a PT-specific divergence between the tempering endpoints that is inherent to the standard, linear tempering path.

In this thesis we consider two approaches for decreasing the global communication barrier and improving the performance of NRPT. In the first approach, we study Bayesian problems and check whether the intermediate distributions, the tempered posteriors, retain statistical properties of the target posterior distribution. We show via two counterexamples that replacing the posterior with the tempered posterior is not justified in general, and conclude that the use of tempered posteriors for inference requires additional restrictions on the Bayesian model.

In the second approach, we develop new methods for optimizing tempering paths.
Previous work on path optimization in NRPT used a path variant that can produce improper intermediate distributions. We construct two families of proper paths and analyze them numerically. Our results show that path optimization can be a viable approach to reduce the global communication barrier, as both path families outperform the linear NRPT algorithm on some models. For one path family, however, the numerical experiments show that path optimization can worsen violations of the model conditions needed to establish the communication barrier. We therefore conclude that not only properness, but also the interaction with the model conditions should be considered when constructing tempering paths.

Popular Abstract (Swedish)

Då komplexa data analyseras statistiskt uppstår i regel svåra beräkningsproblem. De löses ofta med metoder som kan liknas vid en vandrare som slumpmässigt utforskar ett landskap, men för vissa problem räcker dessa metoder inte till. En lösning är att låta vandrare på ett svårt och ett enkelt problem kommunicera och hjälpa varandra -- i detta arbete undersöks hur denna kommunikation kan göras mer effektiv.

En klassisk metod för att lösa statistiska beräkningsproblem är med hjälp av slumpvandrare. Problemen kan liknas vid att utforska ett dimmigt bergsmassiv, och slumpvandraren går runt i detta landskap för att förstå hur massivet ser ut. Denna metod är både enkel och fungerar ofta tillräckligt bra. För vissa typer av svåra problem, som kan liknas vid ett bergsmassiv där topparna är separerade av djupa dalar, fungerar metoden sämre eftersom slumpvandraren har svårt att upptäcka alla toppar och därför misslyckas med att förstå hela problemet.

Irreversibel parallell temperering är en metod för att förbättra utforskningen av sådana svåra problem. För att göra detta tar metoden hjälp av ett enklare problem som är lättare att utforska. De två problemen kopplas samman med en så kallad tempereringsstig, längs med vilken slumpvandrarna kan kommunicera. Genom denna kommunikation underlättar slumpvandraren på det enklare problemet utforskningen av det svåra. Graden av kommunikation avgör därför hur effektiv metoden är. Den begränsas av stigens längd som beskriver den teoretiskt maximala kommunikationen som stigen tillåter − en kortare stig tillåter potentiellt mer kommunikation.

I detta arbete utforskas hur stigen påverkar kommunikationen i irreversibel parallell temperering från två synvinklar. Först studeras huruvida man kan förkorta stigen genom att inte gå hela vägen fram till målet. Det förutsätter att tidigare problem längs med stigen är tillräckliga för att förstå slutproblemet. Två motexempel visar här att man inte kan stanna för tidigt för alla val av problem, och att detta därför inte ger ett automatiskt sätt att förbättra kommunikationen.

Därefter utforskas hur valet av stig påverkar kommunikationen. Två olika familjer av stigar utvärderas, vilket visar att kortare stigar kan hittas, åtminstone för vissa problemtyper. Resultaten visar emellertid att en kortare stig inte nödvändigtvis kan omsättas till bättre kommunikation i praktiken, utan att kommunikationen rentav kan försämras på en kortare stig. Arbetets resultat bidrar på så sätt till förståelsen av både möjligheterna och begränsningarna hos denna metod för att lösa statistiska beräkningsproblem.

• author: Danielsson, Erik
• supervisor: Filip Tronarp
• organization: Mathematical Statistics
• course: FMSM01 20261
• year: 2026
• type: H2 - Master's Degree (Two Years)
• subject: Mathematics and Statistics
• keywords: Markov chain Monte Carlo, Parallel tempering, Bayesian inference, Tempered posterior, Stochastic optimization
• publication/series: Master's Theses in Mathematical Sciences
• report number: LUTFMS-3566-2026
• ISSN: 1404-6342
• other publication id: 2026:E87
• language: English
• id: 9244818
• date added to LUP: 2026-06-29 11:40:14
• date last changed: 2026-06-29 11:40:14