Source-linked AI summary
Adaptive parallel tempering algorithm
Blazej Miasojedow, Eric Moulines, Matti Vihola
TL;DR
Multimodal targets can defeat conventional random-walk sampling, and tuning temperatures and local proposals is consequential for mixing. This paper adapts both during parallel tempering and proves convergence results. The temperature adaptation converges to a unique point under mild target conditions, while the authors caution that a shared temperature progression can impair mixing at some levels.
Problem
For multimodal targets, random-walk methods can get stuck in one mode, while choosing a temperature schedule is generally nontrivial.
Source: §1 · pp. 1–2Method
The algorithm continuously adapts the temperature schedule to optimize adjacent-chain swap acceptance and adapts random-walk proposal parameters.
Source: §1 · p. 2, §2.1 · p. 4, §2.2 · p. 5Results
Temperature adaptation converges to a unique point under mild, natural target conditions, and parallel tempering is geometrically ergodic under (A1).
Source: §1 · p. 2, §3.2 · p. 8Takeaways & Limitations
The authors recommend setting projection constraint limits as large as numerical accuracy permits.
Source: §2.4 · p. 6A shared temperature progression can leave some levels with low asymptotic swap acceptance, inducing poor mixing.
Source: §2.4 · p. 7
Abstract
from arXiv · showhide
Parallel tempering is a generic Markov chain Monte Carlo sampling method which allows good mixing with multimodal target distributions, where conventional Metropolis-Hastings algorithms often fail. The mixing properties of the sampler depend strongly on the choice of tuning parameters, such as the temperature schedule and the proposal distribution used for local exploration. We propose an adaptive algorithm which tunes both the temperature schedule and the parameters of the random-walk Metropolis kernel automatically. We prove the convergence of the adaptation and a strong law of large numbers for the algorithm. We illustrate the performance of our method with examples. Our empirical findings indicate that the algorithm can cope well with different kind of scenarios without prior tuning.
1. Introduction
Multimodal targets can trap random-walk methods in one mode, while parallel tempering introduces auxiliary tempered distributions to improve mixing. The paper proposes continuously adapting the temperature schedule alongside local random-walk proposals, and establishes convergence of the temperature adaptation.
1. Introduction
- For multimodal targets, random-walk methods can remain trapped in one mode, causing false convergence and severely erroneous results.Parallel tempering uses auxiliary distributions proportional to π^β to improve mixing within modes.Source: §1 · p. 1
- The temperature schedule is generally nontrivial to choose; geometric progression and swap acceptance rates inform existing guidance.Prior work links mean swap acceptance to temperature selection, with further analysis in and.Source: §1 · p. 2
- The proposed method continuously adapts temperatures to optimize mean acceptance of swaps between adjacent chains, with convergence to a unique point under mild, natural target conditions.The scheme is similar to Atchadé, Roberts and Rosenthal, but adapts continuously during simulation.Source: §1 · p. 2
- Local exploration uses random-walk Metropolis proposals whose scale and shape can be adapted with existing techniques.Examples include covariance estimation with adaptive scaling toward a target acceptance rate, or robust shape estimation.Source: §1 · p. 2
2. Algorithm
The algorithm runs parallel-tempering chains on a product space, alternating swaps and random-walk updates. It adapts adjacent-temperature swap acceptance and local proposal parameters, with alternate proposal adaptations and implementation choices described.
2.1. Parallel tempering algorithm.
- Each iteration alternates a swap move with separate random-walk Metropolis updates for the chains, whose Gaussian increment covariances parameterize the proposals.The chains target tempered distributions at inverse temperatures ordered from 1 down to a positive value.Source: §2.1 · pp. 2–3
2.2. Adaptive parallel tempering algorithm.
- Temperature adaptation uses stochastic approximation to target mean acceptance α* for swaps between every pair of adjacent-temperature chains.The inverse temperatures are updated during the run; proposal covariance and scaling are also adapted, with scaling targeting a specified stationary acceptance rate.Source: §2.2 · pp. 4–5
2.3. Alternate random-walk adaptation.
- Alternate random-walk adaptations include a common covariance with separate temperature-level scaling, and RAM, which adjusts covariance to attain a given acceptance rate.RAM aims to estimate a local target shape that may allow better local exploration than a global covariance shape.Source: §2.3 · p. 6
2.4. Implementation details.
- Implementation uses α*=0.234 and projection constraints to stabilize adaptation for theoretical analysis; the authors recommend setting limits as large as numerical accuracy permits.A shared temperature progression may be more stable with many levels, but can yield low swap acceptance at some levels and poor mixing.Source: §2.4 · pp. 6–7
- The method can also use non-Gaussian proposals, including multivariate Student proposals, and can extend to block-wise or Metropolis-within-Gibbs settings.In hierarchical models, the latter structure can allow computational savings; the exposition presents the algorithm in R^d.Source: §2.4 · p. 7
3. Theoretical results
The theoretical results establish ergodicity and strong-law behavior for parallel tempering under stated regularity and step-size conditions. They also show that temperature adaptation converges to a unique setting targeting the specified mean swap acceptance rate.
3.1. Formal definitions and assumptions.
- Assumption (A1) requires a sufficiently regular target distribution whose tails decay faster than exponentially.The paper notes that this condition ensures integrability of the tempered densities for exponents β>0 of interest.Source: §3.1 · p. 8
3.2. Geometric ergodicity and continuity of parallel tempering kernels.
- Under (A1), parallel tempering is geometrically ergodic; under mild conditions its kernel is also φ-irreducible, strongly aperiodic, and V-uniformly ergodic.The drift function V is a sum of appropriately chosen negative powers of the target density.Source: §3.2 · p. 8
- Under (A1), measurable functions with the stated Vαβ0 bound have a unique-up-to-constant solution to the Poisson equation.The result also gives a bound on the growth of that solution.Source: §3.2 · p. 9
- The parallel-tempering kernel is locally Lipschitz continuous in its covariance and inverse-temperature parameters over the stated parameter sets.Theorem 3 gives this bound under (A1), with β and β′ in Kβ0,η.Source: §3.2 · p. 9
3.3. Strong law of large numbers.
- For functions satisfying the stated Vαβ0 bound, the algorithm obeys a strong law; for coolest-chain functions, the limit condition is automatic and πβn(f)=π(f).The strong law for the coolest chain does not require inverse-temperature convergence.Source: §3.3 · pp. 9–10, §3.4 · p. 10
3.4. Convergence of temperature adaptation.
- For finite-Lebesgue-measure support, sufficiently many temperature levels may leave no finite stable solution; higher levels then correspond to the uniform distribution on the support.The paper states that this can occur for L≥L0, with inverse temperatures equal to zero at levels ℓ≥L0+1.Source: §3.4 · p. 10
- Under (A1)–(A3) and the theorem’s additional conditions, inverse-temperature adaptation converges almost surely to a unique stable setting with adjacent swap acceptance targeting α*.The stable setting solves the system of equations defining the adaptation’s mean field.Source: §3.4 · pp. 10–11
4. Experiments
Experiments evaluate adaptive parallel tempering on Gaussian mixtures and a spatial imaging posterior, with favorable reported results across these settings. The mixture results vary with temperature count and covariance structure, while the spatial estimate required no prior tuning.
4.1. Mixture of Gaussians.
- Across 100 runs, estimates had smaller deviation than unadapted parallel tempering but larger deviation than samplers with equi-energy moves.The comparison reports means and standard deviations for estimates of means and squared coordinates.Source: §4.1 · p. 11, Table 1 · p. 12
- For the test of [7], Table 3 case (A), the five-temperature-level run used 5,000 iterations and 2,500 burn-in, while the three-level run used 8,333 iterations and 4,167 burn-in.Source: Table 1 · p. 12, Table 2 · p. 13
- With three temperature levels, accuracy increased over the five-level run and came close to results for samplers with equi-energy moves at comparable computational cost.The three-level run used 8,333 iterations to match computational cost.Source: §4.1 · pp. 12–13, Table 2 · p. 13
- In the harder mixture with σ2 = 0.001 and d = 8, Cov(g) seemed to improve on Cov, while RAM gave the most accurate results.The authors suggest RAM's performance may reflect the example's shared component covariance.Source: §4.1 · p. 13, Table 3 · p. 13
4.2. Spatial imaging.
- The spatial imaging run produced a posterior estimate similar to earlier reports, without prior tuning.Figure 3 places the original image beside the estimate from 100 replications.Source: §4.2 · p. 14
5. Proofs
The proofs establish ergodicity and a strong law under stated regularity and adaptation conditions, and show that the temperature schedule has a unique solution with convergent adaptation. They also develop continuity and monotonicity results used in these arguments.
5.1. Proof of Theorem 1.
- Explicit drift and minorisation controls yield V-uniform ergodicity for the parallel-tempering kernel under (A1).The argument controls individual random-walk Metropolis kernels and uses permutation invariance of the swap kernel to obtain the drift inequality.Source: §5.1 · pp. 15–17
5.2. Proof of Theorem 3.
- Bounds on random-walk and swap-kernel perturbations establish local Lipschitz continuity of the parallel-tempering kernels in covariance and temperature parameters.The propositions provide bounds for parameter pairs in specified covariance and temperature sets.Source: §5.2 · pp. 19, 21, 22
5.3. Proof of Theorem 5.
- The strong-law proof uses a finite initial Vβ0 moment and summable adaptation rates to establish the required moment bounds and conclude the theorem.The conditions include (A1), sup_n γn,2 ≤ 1, and a nonnegative sequence b_n with Σ_n≥1 b_n(γn,1 + γn,2 + γn,3) < ∞.Source: §5.3 · pp. 22, 25, 26
5.4. Proof of Proposition 7.
- Under the stated density conditions, the mean-field function is differentiable and monotonic in one argument on (0, v), supporting the proof of root existence and uniqueness.The proof introduces this property as its key lemma for establishing existence and uniqueness of the mean-field root.Source: §5.4 · p. 26
- Proposition 7’s equations have a unique solution, established recursively using strict monotonicity and endpoint limits.The proof first establishes the unique solution for the first coordinate, then proceeds by induction for subsequent coordinates.Source: §5.4 · pp. 27–28
5.5. Proof of Theorem 10.
- Theorem 10’s temperature-adaptation convergence is proved recursively for each coordinate using stochastic approximation.The proof uses local Lyapunov functions and a Poisson decomposition into martingale differences and a remainder; its stated assumptions include (A1)–(A3) and EVβ0(X0) < ∞.Source: §5.5 · pp. 28–30