Continuously Tempered PDMP samplers
Authors: Matthew Sutton
Robert Salomone
Augustin Chevallier
Paul Fearnhead
Venue: NeurIPS 2022 Accept (2022)
Keywords: PDMP
Zig-Zag
tempering
MCMC
Monte Carlo
Markov Chain
Probabilistic Inference

Abstract: New sampling algorithms based on simulating continuous-time stochastic processes called piece-wise deterministic Markov processes (PDMPs) have shown considerable promise. However, these methods can struggle to sample from multi-modal or heavy-tailed distributions. We show how tempering ideas can improve the mixing of PDMPs in such cases. We introduce an extended distribution defined over the state of the posterior distribution and an inverse temperature, which interpolates between a tractable distribution when the inverse temperature is 0 and the posterior when the inverse temperature is 1. The marginal distribution of the inverse temperature is a mixture of a continuous distribution on $[0,1)$ and a point mass at 1: which means that we obtain samples when the inverse temperature is 1, and these are draws from the posterior, but sampling algorithms will also explore distributions at lower temperatures which will improve mixing. We show how PDMPs, and particularly the Zig-Zag sampler, can be implemented to sample from such an extended distribution. The resulting algorithm is easy to implement and we show empirically that it can outperform existing PDMP-based samplers on challenging multimodal posteriors.

Continuously-Tempered PDMP samplers
Matthew Sutton
Robert Salomone
Centre for Data Science Queensland University of Technology matt. sutton@qut..uu...o edu.au
Centre for Data Science
Queensland University of Technology robert.sall www.smlelluuu....mmmmmmm edu.
Augustin Chevallier
Paul Fearnhead
Department of Mathematics and Statistics Lancaster University
Department of Mathematics and Statistics Lancaster University
a www.haalllerrrlnncstterrrrrrrrr uk
p p.fe ac.uk
Abstract
New sampling algorithms based on simulating continuous-time stochastic pro- cesses called piecewise deterministic Markov processes (PDMPs) have shown considerable promise. However, these methods can struggle sample from multi- modal or heavy-tailed distributions. We show how tempering ideas can improve the mixing of PDMPs in such cases. We introduce an extended distribution defined over the state of the posterior distribution and an inverse temperature, which in- terpolates between a tractable distribution when the inverse temperature is and the posterior when the inverse temperature is 1. The marginal distribution of the inverse temperature a mixture of continuous distribution on [0, 1) and point mass I: which means that we obtain samples when the inverse temperature is 1, and these are draws from the posterior, but sampling algorithms will also explore distributions at lower temperatures which will improve mixing. We show how PDMPs, and particularly the Zig-Zag sampler, can be implemented to sample from such extended distribution. The resulting algorithm is easy to implement and we show empirically that can outperform existing PDMP-based samplers on challenging multimodal posteriors.
1 Introduction
Recently there has been considerable interest in developing sampling algorithms based on simulating continuous time stochastic processes called piecewise deterministic processes (PDMPs) (DDMP))Davis/ [1993].
These sampling algorithms are qualitatively similar to Hamiltonian Monte Carlo algorithms Neal (2011). To simulate from some target distribution ग,, they work with an augmented state-space (ær, v). where the component can be viewed as position, and the component a velocity. The motivation æ by simulating continuous velocity
for this is that these processes will encourage exploration paths in between random event times at which the velocity changes. Examples of such sampling algorithms include the Bouncy Particle Sampler [Peters and de With 2012, Bouchard -otté et al.
2018), the Zig-Zas algorithm [Bierkens al. 2019], the Coordinate Sampler (w and Robert 2020 and the Boomerang Sampler [Bierkens al. 2020 See Fearnhead et al. [2018] for an overview of
these methods. Importantly, it is simple write down the event rate, and how the velocity should change at each event, to ensure these PDMPs have π as their invariant distribution. These samplers depend only through the gradient of log æ, and thus æ only needs to be known up constant of proportionality.
"The authors acknowledge funding through EPSRC grants EP/R018561/1 and EP/R034710/
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

PDMP samplers have number of advantages, including non-reversible dynamics (which are known to improve mixing relative reversible processes (Diaconis al. 2000 Bierkens] 2016)), and the ability to reduce [Bouchard-Cöre et al. 2018 Sutton and Fearnhead [02T] or using only sub-samples of the data to approximate the log- li lilkliikooood at each iteration (whilst still guaranteeing sampling from the target [Bierkens et al. 2019]. However, like other MCMC algorithms, particularly those that use gradient information, these PDMP samplers can struggle to mix for multi-modal target distributions, for heavy-tailed targets [Vasdekis and Roberts 2021].
computation--er-iiiee per-iteration by either leveraging sparsity structure in the model
One of the more successful techniques for enabling an MCMC algorithm to sample from challenging, e.g. multi-modal, target distributions to use tempering. There are various forms of tempering, but each is based on defining either a discrete set or continuum of distributions that interpolate between a distribution that is simple to sample from (viewed as at high temperature) and the target distribution (at low temperature). The idea is that allowing moving across this set will improve mixing, as moving between modes will be easier for the distributions higher temperatures. Examples of such algorithms include parallel tempering [Swendsen and Wang 1986), simulated tempering [Marinari and Parisi 1992]. and continuous tempering [Graham and Storkey 2017).
In this paper we show how continuous tempering ideas can be used with PDMP samplers. We have chosen continuous tempering, as opposed to the alternative tempering approaches, it is the method that can most naturally benefit from the continuous satruouuus--ueeeeee nature of PDMP dynamics. To the best of our knowledge, this is the first attempt at using tempering ideas to improve PDMP samplers. The general idea is to define joint distribution on the state of the PDMP, = (ar, v). and the inverse temperature, B. The target distribution of interest is the z--magginal of this joint distribution when B = 1. We define the joint distribution so that it has point mass at / = 1 - thus simulating from it will lead to a proportion of the resulting samples being from the target. We then use a PDMP sampler to simulate from this joint distribution. Constructing the appropriate dynamics of the PDMP sampler non-trivial this case as we have to deal with its behaviour as it transitions between the continuous distribution on 3 E [0, 1) and the point mass at B = 1. We use recent ideas for PDMP samplers with discontinuities [Chevallier et al. 2021 2020 to solve this challenge.
While we express ideas based on and similar to Graham and Storkey [017)] a key difference is the inclusion of a point-mass at 3 1, this means we can obtain samples from i rather than having to resort to importance sampling to correct samples drawn at different temperatures. It is easy to introduce a point mass into the dynamics of the PDMP sampler due to its continuous sample paths: we simulate paths for 3 E [0, 1) until the process hits 3 = 1 - we then simulate paths with 3 fixed to for an exponentially-distriuuu using point-mass within Hamiltonian Monte Carlo sampler is not possible as the discretised sample paths will not hit 3 = with probability 1. Yao et al. (2020) consider an indirect approach to sampling with a pass at 3 1 using continuous link function. Our approach is distinct and more direct, allowing one to exploit the unique advantages of PDMP samplers - such as the ability to perform subsampling without altering the ergodic distribution and application to sampling transdimensional distributions.
period of time before returning to 3 [0, 1). By comparison,
The benefits of introducing the point mass at , 1 are numerically investigated, and practical considerations related to choosing tuning parameters to encourage a desired proportion of time at the target distribution are presented (Section 3.4). We find that, analogously to standard methods in discrete-time, the tempered counterparts of PDMP samplers outperform vanilla PDMP on challenging sampling problems.
2 The Zig-Zag sampler
For the purposes of brevity and case of exposition, we focus specifically on continuous-tempee version of the Zig-Zag sampler. However, we stress that the underlying ideas can easily be applied to any PDMP sampler, for example, the Bouncy Particle Sampler [Bouchard-Cōré et al. 2018 or the
Boomerang Sampler [Bierkens et al., 2020 see the comments at the end of Section 3.2
Consider the problem of sampling from a target density defined for a E X == Rd by
1 x(x)
Z exp(-U(x))
2

---

where U : X' + R is differentiable function referred to as the potential and Z is the, potentially unknown, normalising constant density by q, so Tx)) g(z)/Z.
Jx exp(-U(x)) (x)), We will denote the un no-nomallieed target
The Zig-Zag process is a continuous-time PDMP, which can be defined so as to have л as its invariant distribution. The process is defined on extended state-space sate-space that can be viewed consisting of position x and a velocity component v. For the Zig-Zag process, the velocity is restricted to be #1 in each axis direction. Thus the extended space is E = R x 1) We write from here on. We use subscripts to denote time, and superscripts to denote components. So 2, will be the state at time while æt will be the ith component of the position at time I.
(z, e) for x E E
For an event at time we use the notation 2,_ for the state immediately before the event, and 2, the state immediately after it. The dynamics of the Zig- Zig-Zag process are deterministic between random event times, At each event time the direction of one component the velocity is switched. The deterministic dynamics are specified by a constant velocity model. So, if there are events between times and t + h, for h > 0, the change of state is given by 24+h = (Iz+h, v(+h) = (2t + hw,, vz).
The events occur with rate that depends on the curret state. For the Zig-Zag, process we have types of event, each of which results in the flipping of one of the d components of the velocity process. To ensure that we have и as the a--margial of the process's 's invariant distribution, these rates are defined to be, for ,,...,d. d. (z,,, v,) max(0, (x)),
with the transition at the corresponding event being that of ui_ and all other elements of the state are unchanged.
Pseudo-code for simulating the Zig-Zag process is given in Algorithm T When we simulate such process, the output of the algorithm is the set of event times, positions and velocities after the event times. This set is known the PDMP skeleton and with the deterministic dynamics of the process it defines the continuous time path of the process. We can use such a simulated path to give us draws from x (xx), by discarding some suitably chosen initial path time as burn-in, and then evaluating the æ component of the process at set of evenly spaced discrete time points (see e.g. Fearnhead et al. 2018 for alternative approaches that use the continuous- paths).
Algorithm Zig-Zag algorithm
1: Inputs: initial state (att, vto) and number of simulated events K
2: In <-
3: for kelk, K do
4: Simulate an event-time for each rate A (xc, v.)
5: i f argmin, { and b + tx-1 + Ti-
6: Ete + Lta + TG. vc-11
b Update position Update velocity
7:
vi
v. Vin-1
8: end for
9: Outputs: Zig-Zag skeleton (1e, Bies Dee
3 Continuous tempering with a point mass
3.1 Continuous tempering
Continuous tempering is an approach to improve mixing of MCMC and related sampling algorithms. It introduces second distribution To, called the base distribution, which is assumed to have density To()) = Z.
(n) The idea is that this density will be simple to simulate from. For any 3 E [o, 1] is now possible to define a distribution which interpolates between л and wa in that density 7 (<)) To (x)) Continuous tempering then defines joint distribution for 3 and æ. This
distribution has un-oormalised density q( 3), Hd x [0, 1]. defined to be
q(x, 3) = qo (x) 1-8 -x)))
In practice, tempering methods often introduce pseudo prior, p(3) on B E [0, 1). and sample from the distribution proportional to ((3)g(x, 9). The idea of introducing the prior is that it can be tuned
3

---

to give marginal distribution on 3 that has reasonable mass across all of the interval [0, 1]. Without a prior, the distribution q is likely put almost all mass on 3 close
1.
By construction, conditional on satisfying 3 = 1, samples drawn from g(ar, (3) are distributed according
However, if we continuous prior, samples will almost-surely not lie in that set, and we have to use importance sampling to correct for 3 * 1. This leads to weighted sample from т,, with the Monte Carlo accuracy of the resulting approach depending greatly on the variability of the weights introduced by importance sampling.
To overcome this issue, and an arbitrary (possibly non non-nonee (on--ommalsed probability density function & on the interval [0, 1), we define
p(3) that introduces a point mass at 3 1. Specifically, for R.
p(3) = (1 - (0) + (x=3))
With the above prior, we can define the augmented target
w wda, d8) (( B) (z)x(())add))) + g(z))ax((3dddd)_)
(1)
We can extend the Zig-Zag process to sample from such a distribution. The next subsection describes the extension. The usual advantages of subsampling and transdimensional sampling using PDMPs apply for the tempered extension.
3.2 Continuously-tempered Zig-Zag
Unlike most MCMC samplers, Zig-Zag is a continuous-time process. This makes it simpler to deal with the point-mass at 3 = 1, using ideas from Chevallier et al. [2020]: we simulate paths for E (0,1) 1) until hits the boundary 3 = 1; when this happens, we set the velocity component for 3, denoted as it to zero so that the Zig-Zag process explores the distribution w restricted to until the first event in new Poisson process, which point we set the velocity component for 3 to -1 to allow exploration of the distribution for E [0, 1). We define the rate of the events when leave relevant modifications of the standard Zig-Zag process for events concerning the inverse temperature variable 3.
1; the Zig-Zag process stays with 3
be 7). Algorithm 2 provides sketch of the
Algorithm 2 Tempered Zig Zag algorithm
1: Run Zig-Zag for Bg E 1) until first time t at which trajectory hits 3 =
2: vi+t1 +0
b Kill the velocity component for B
3: Simulate event-time with rate 7)
4: Run the Zig-Zag process with 3 = 1, for time
b Sample π b Reintroduce B
5: dd1 +- -1
Goto Step 1.
appropriate choice of rate to ensure that the resulting algorithm generates process with as its limiting distribution is given in the following result (the proof of is located in Section 1 of the supplement).
Theorem Assuming xs(3) continuous and the rate function Algorithm 2 chosen as
1-a
2a
Then, the resulting Zig-Zag process has w as stationary distribution.
The theorem statement above considers the case where is continuous but we note in the proof that more general choice is possible with slight adjustment the rate.
Importantly, the rate 7/(x)) is constant, and thus simulating the time at which we transition from 3 = to 3 < 1 is independent of the path of the process and simulating the event time is simple. While we have described the use continuous tempering as an extension the Zig-Zag process, the same construction readily extends to other PDMP samplers.

---

Remark A tempered version of any PDMP-based sampler can be constructed more generally by adding a tempering variable with associated velocity =1 and Zig-Zag rate function (irrespective of the base PDMP). When B3 hits 1, the process reduces to the PDMP sampler a and is reintroduced with rate given by that of Theorem I. See Remark I in the supplement for additional details.
3.3 Importance sampling estimator
By construction, continoosll--emmpere Zig-Zag will spend substantial amount of time in states importance
with 3 = 1, and thus the states those times give draws from x (x)). We sampling ideas from Graham and Storkey [2017] to re-weight samples when 0 S 8 < to give
weighted samples from T()); but this only applies if x(3) El- for some constant Ç.
The idea of this approach is that, for /3 E [0, 1), we can marginalise out / from w, and the marginal distribution for æ is
(x) = [// x(3)g(z)
(0(2))
1-8
d3 = g(x)) L.'
(Ego(z) q(x))
1-8
d3.
((x)
Defining A(x)) = log (2:) log log g(x),, the above is equal to
((x) / (1
exp(A(x)) -
= (()) (xpp--(p(A(a))))))
A(x)
Thus, if we have this as our proposal distribution, then the corresponding importance sampling weights will be w(x) (xx) (()][((((((()) 1]. However, this will involve additional post-sampling computation of the importance weights at the samples taken from the Zig-Zag trajectory.
3.4 Calibration of k(B)
The efficiency of continuous tempering depends on an appropriate choice of and a. The choice of x also arises in path sampling Gelman and Meng [1998] and in simulated tempering Marinari and Parisi 1992]. A common approach from this literature is to choose so the resulting marginal for is uniform. This choice is made to balance
non-negligible amount of time at while simultancously allowing occasional excursions to lower inverse temperatures to help mix, e.g. between modes. We consider how this choice for x may be adapted our work considering the point mass at and additional parameter
For B [0, 1] define, Z(3) Sga (xx, B)dx. The induced 3-marginal of for Bo [0, 1) is
(1 - ())(()))(()))))))
w(B)) a1 So <² (B)) + ax(1)
The above suggests that appropriate choice is k(3) x Z(B)-1, as this would both induce B to be marginally uniform under w for 3 E [0, 1), and cause the parameter a directly represent the probability that B = under w.
In our work, we choose x(() x -(5)-1, where 2( = exp {EXT ag for some coefficients
1m-1 1 The restriction to polynoiial terms allows for simple implementation of thinning bounds TR=0 following Sutton and Fearnhead (2021). Since Z(3) is unknown practice, common approach is to replace it with an approximation. Following ideas from the path sampling literature [Gelman) and Meng 1998 Yao et al.) 2020), we can make of numerical integration to form an estimate of log ((3) using pilot run of the sampler. The terms {ax 1m-1 may be estimated based on this
{az
approximation (see Section 6.3 the supplement for details).
4
Numerical experiments
4.1 Mixture of Gaussians
In our first example, the target corresponds to mixture of Gaussian distributions with equal weights and variances so our target has unnormalised density
m.) (xc m.))
q(>)
exp
20
(x
i=1
5

---

where K 55, o² = 0.2 and {Ki....,, μs} were generated uniformly on the region [0, 10] x [0, 10] and are given in Table the supplement. Figure[[plots the PDMP trajectories for the tempered and untempered Zig-Zag sampler, in addition to the trajectories for inverse temperature fixed at / = 1. For this example we choose go go(x)) (a) be a Gaussian Nu, Σ) centred at v (5, 5) with covariance matrix Σ 2.
125
10.0
7.-
5.0
0.50
1.00
0
12
12
Figure 1: Trajectories of the Zig-ZZ Zag process simulated for 30,000 events for a multi-modal Gaussian mixture model, Zig-Zag (left) and continuously-temperr Zig-Zag (right) with = 0.7.
We define the work normalised efficiency as the square root of the total number of gradient (or target) evaluations multiplied by the Mean Square Error (MSE). This quantity includes the additional target evaluations required for the importance weights in Zig-7ag (IS). We consider the MSE for the first and second marginal moments of the Gaussian mixture model. Relative work normalised efficiency is then the ratio of this metric relative to competitor. Table the relative work normalised efficiency for the methods comparative to the standard (untempered) Zig-Zag sampler. relative efficiency of 2 indicates the proposed method is twice efficient as the standard Zig-Zag. All methods were simulated for 50,000 event-times, with the first 40% used as burnin in the standard Zig-Zag and used for both burn-in and estimating the polynomial x(3) in the tempered samplers.
Table 1:
Work normalised efficiency for the first two moments of a Gaussian mixture relative to the standard Zig-Zag sampler (averaged over 20 replications).
Relative work normalised efficiency
Thinning efficiency
Method
a
w(3 = 1)
E[X]]
E[X₂]
[[
E E[X,]
Zig-Zag
1
1
1
0.057
7ig-Zag CT
0.800
0.789
4.641
4.366
4.568
5.216
0.080
0.700
0.703
8.079
5.024
8.447
6.202
0.090
0.500
0.499
10.963
7.134
10.265
9.047
0.114
0.300
0.302
13.145
9.388
14.838
11.885
0.139
0.200
0.197
14.153
9.479
13.235
11.225
0.153
0.100
0.097
12.550
12.057
13.145
12.958
0.167
Zig-Zag (IS)
0
0
10.640
11.689
11.038
12.713
0.301
The standard Zig-Zag is not able to explore the multiple modes, yielding poor estimates of the first and second moments see section 6.2 of the supplement for RMSE performance. We also compare to direct Zig-Zag analogue of the 2017] where no mass is given to 3 1 and x x33) 1, the estimator is based on importance sampling as defined in Section 3.3 We find that the tuning procedure yielded precise control over the time spent 8 = and that for between 0. and 0.3 the results are similar. Tempering with point mass was found to give more efficient estimates of the first and second moments. This may be because the importance sampling estimate spends more time at O. addition to exhibiting better statistical performance, the tempered versions of the Zig-Zag sampler have better computational properties. The thinning efficiency, measured as the proportion of proposals that result in an event-time simulation .06 at 3 1, but improves significantly when the sampler can transition to lower temperatures.
pentiniouusl-tempprre
HMC algorithm [Graham and Storkey

---

While the importance sampling estimator for 3 = 0 has the best thinning efficiency, we note that it requires additional post processing evaluate the importance sampling weights.
Table 2 provides further simulations to compare our tempering approach with both reversible Woodard et al., 2009] and non-reversible [Syed al. 2022 parallel tempering (denoted R-PT and NR-PT respectively). A Zig-Zag kernel is used at each temperature level and run for S E {0.1, 1, 2} units of stochastic time. We use geometric temperature sequence [1, a a² recommended in the literature [Tawn et al. 2020 and consider results for a E {0.1, 0.3, 0.5, 0.7), with n E {3, 5, 7). Results are again relative to standard (untempered) Zig-Zap normalised efficiency. We present the best performing parallel tempering result for each choice of a. The full set of results provided in Section of the supplement. Our methods show similar performance to well-tuned NR-PT PT and outperform R-PT.
a as commonly
terms of work
Table Work normalised efficiency for the first two moments a Gaussian mixture for parallel tempering relative to the standard 7ig-Zag (averaged over 20 replications), Results are only shown for the best performing choice of S and n for each choice of a E {0.1, 0.3, 0.5, Extended results may be found in the supplement.
Relative work normalised efficiency [[X]]
Method
S
[[X]]
[[X²]
[[X]]
NR-PT
0.1
7
9.160
11.029
9.441
12.883
NR-PT
0.3
5
11.626
14.757
11.679
15.972
NR-PT
0.5
5
2
11.072
12.320
11.352
13.951
NR-PT
0.7
7
12.185
8.942
12.956
10.512
R-PT
0.1
5
7.142
6.750
7.382
7.448
R-PT
0.3
5
9.549
7.645
9.912
8.949
R-PT
0.5
3
10.136
7.672
10.830
8.842
R-PT
0.7
7
12.275
11.273
12.591
12.648
4.2
Transdimensional example
We apply the tempered Zig-Zag to the challenge of sampling a transdimensional distribution. Such target distributions arise naturally in variable selection problems. The resulting target (posterior) distribution is a discrete mixture of 2 models, where is the number of variables in the dataset.
Such setting produces challenge, typical samplers such HMC do not extend naturally to such spaces. On the other hand, PDMPs have recently been extended to sample transdimensional distributions [Chevallirr et al. 2020 202 Bierkens et al. 2021]. This extension employs within- model gradient information to efficintlly explore the space and jumps between models when a parameter hits zero. The approach is beneficial
informative likelihood function's gradient will direct less informative variables towards zero and more informative ones away from zero, aiding exploration of the sampler.
This example explores how tempering a target with a point mass can improve performance over standard transdimensional Zig-Zag process. Specifically, we define family of example problems of increasing difficulty in the sense that for higher values of an underlying parameter m, separation between the mode of the slab component and the spike at zero is increased. Allow
2
(xx) = II (wolzz m, 0²) + +1 (1- wx)o(z))).
(2)
1=1
where o0,;;,,, o²) is the normal density and w 0.5 is the probability of a variable being included. We fix o² 0.5 and increase from m m 4. To enable tempering, define
m.
2
(00, 9) II
+ w))0(x:)).
==1
where at 9 = the spike and slab centred zero, encouraging variables to enter and exit the model. While this is somewhat artificial example, it is important to note that it encompasses precisely the
7

---

situations which transdimensional PDMPs will find challenging, and allows us to explore robustness for increasing levels of pathology the purest setting possible.
Figure 2 (rightmost panel) displays the dynamics of the tempered Zig-Zag for this problem for the choice of m 4. Note that the standard transdimensional Zig-Zag process (bottom left) becomes stuck in a single model whilst its tempered counterpart is able to transition easily between models and thus visit the required areas for which each coordinate equal zero.
III
0.5
0.50
Figure 2: Sampling from with m = 4. I. Exact samples from the spike-slab distribution. II. Standard Zig-Zag for 10 wemnt-imme. III. Tempered Zig-Zag trajectories with 0.5 for 10* event-times.
Table 3: Absolute error of marginal mean and probability of inclusion for X (averaged over 10 simulations for increasing m (
Mean Absolute Error
0
m
m
m
171
E[X
Zig-Zag
0.005
0.018
0.633
1.498
1.998
Zig-Zag CT
0.007
0.025
0.022
0.047
0.214
F([X1 0)
Zig- Zag
0.009
0.012
0.322
0,500
0.500
Zig-Zag CT
0.010
0.023
0.008
0.018
0.055
Table 3 gives the absolute enror for the Monte Carlo estimates of the marginal inclusion probabilities and marginal means. For lower m, the standard and tempered Zig-Zag perform similarly as the mode of the slab close enough to ensure regular crossing of the zero-axis for the PDMP trajectories. However, as m increases, the marginal probabilities of inclusion tend to and the standard Zig-Zag process becomes stuck in single model.
4.3 Boltzmann machine relaxation
Following Nemeth et al. 2019 and Graham and Storkey (017), the final example considers sampling continuous relaxation of Boltzmann machine distribution. Full details surrounding the derivation of the distribution can be found [Nemeth et al.) 2019 Supplementary Material, Section D], though for the considered example the target density d is of the form
q(x) d2m) exp( Tr(D))
24
1 exp (-
II cosh(g x + bb),
where q) denotes the k-th row of Q, which is d, x d, matrix such that QQ W D. and D is arbitrary diagonal matrix that ensures W + D is positive semi-definite. The above is continuous relaxation the Boltzmann Machine distribution on (-1,1]% with probability mass function
((s) 2,, exp
W + +
8

---

The moments up to second order of the relaxation and the original (discrete) Boltzmann Machine
distribution are related via E X Q E and E[XX Q E|SS We employ similar experimental setup as in Nemeth et al. 2019), namely 28 28-dimensional example which allows for exact computation via enumeration of the moments of S, and hence in turn of X (the latter being useful for evaluating sampler performance). Again, we use work normalised efficiency taken relative to the standard (untempered) Zig-Zag as described in Section 4.1. The average mean square error for the first and second marginal moments over the 28 dimensions is used to evaluate the work normalised efficiency.
Table 4 displays the results. We find that the best performance is given by the Zig-Zag sampler with 0.2 which outperforms the standard Zig-Zag (a 1) and the seadiioousl--temperee importance sampling approach (a = 0). For these experiments, the tuning of k is notably sub-optima as the proportion of time spent at zero not fully controlled by a. Despite this, the samplers still offered substantial improvements over the importance sampling approach and the standard Zig-Zag. Further details on the experiment and specification of may be found in Section 6.3 of the supplement. Additional tables recording the root mean square error of the methods may be found in Section 6.2 of the supplement.
Table 4: Average relative work normalised mean square error of the first and second marginal moments of the Boltzmann machine relaxation averaged over 20 simulations reported to decimal places.
Average relative work normalised efficiency
Thinning efficiency
Method
Q
(3
1)
B[X+]
Zig-Zag
1
1
0.146
Zig-Zag CT
0.700
0.632
2.025
1.065
0.187
0.500
0.417
1.835
1.016
0.219
0.300
0.231
2.021
0.795
0.251
0.200
0.145
2.511
1.033
0.267
0.100
0.076
1.332
0.549
0.284
Zig-Zag CT (IS)
0
0
1.253
0.390
0.505
We further compared our methods with reversible and non-reversible parallel tempering for wide variety of tuning choices, and these results may be found in Section 7 of the supplement. We found that our methods appear be less sensitive to tuning. However, for this example parallel tempering was able to achieve better performance than our continuously-tempers of a, S and n. Parallel tempering achieved optimal average work normalised relative efficiency of 6.1 on the first marginal moment (NR-PT with a = 0.5, S = 2, n = 7) and 1 1.98 for the second marginal moment (R-PT with 0.7, S
methods for certain choices
7).
Discussion
We present a general strategy to improve the performance of PDMP samplers challenging targets. The approach uses an extended distribution that uses an inverse temperature which interpolates between a challenging distribution of interest and a tractable base distribution. At lower values of 3 the mixing will improve and we allow a point-mast at B = 1 to attain exact samples from the distribution. As proof of concept, numerical study of these ideas surrounding the Zig-Zag sampler was employed. This revealed that there are considerable benefits to the proposed extensions, as well as to introducing the point mass at 1. We compared our tempering with a point-mass extension of the Zig-Zag to version based on setiinouuslytemmperre estimates that are given using importance sampling ideas from Graham and Storkey [2017]. The importance sampling approach requires restrictive choice of к and gave inferior performance. Our approach may be readily applied to other PDMP samplers and can incorporate assets of sampling with PDMP such as sampling transdimensional spaces and using subsampling methods. Another avenue of research in incorporating direct simulation from yo when the sampler hits 3 = 0 such moves would be particularly useful when yo is tractable multimodal distribution. Another avenue for research would be consider parallel versions of the continuous tempered PDMP. Additional moves could be made to swap temperatures between different parallel PDMPs analogous to parallel tempering.

---

Broader impact
Effective sampling methods are instrumental in many probabilistic modelling approaches that account for uncertainty quantification (c.g., Bayesian Machine Learning approaches). Thus, it is important to employ reliable methods obtaining such estimates, especially they are used for downstream tasks and decisions. The methodological innovations discussed herein aim to produce more reliable results the context of PDMP samplers, which are growing area of research. The proposed approaches are more suited to sampling challenging multi-modal distributions with PDMP-based samplers. As the methods are presented as proof of concept, and not feature as an implemented component within any deployed artificial intelligence system, there are no immediate broader consequences related to their potential failures.
References
J. Bierkens. Non-reversible Metropolis-Hasting Statistics and Computing, (21(6)))113-2228, 2016.
Bierkens, P. Fearnhead, and G. Roberts. The zig-zag process and super-efficient sampling for Bayesian analysis of big data. The Annals of Statistics,
2019.
J. Bierkens, S. Grazzi, K. Kamatani, and G. Roberts. The boomerang sampler. In International Conference on Machine Learning, pages 908-918. PMLR, 2020.
J. Bierkens, S. Grazzi, F. van der Meulen, and M. Schauer. Sticky PDMP samplers for sparse and local inference problems. arXiv.2103.08478 2021.
A. Bouchard-Côté, S. J. Vollmer, and A. Doucet. The bouncy particle sampler: A nonreversible rejection- free Markov chain Monte Carlo method. Journal of the American Statistical Association, 113(522):855 867,,8677777 2018.
A. Chevallier, P. Fearnhead, and M. Sutton. Reversible jump PDMP samplers for variable selection. arXiv:2010.11771, 2020.
A. Chevallier S. Power, Wang, and P. Fearheedd. PDMP Monte Carlo methods for piecewise- smooth densities. 0.::21111.08555 2021.
M. H. A. Davis. Markov Models and Optimization. Monographs on Statistics and Applied Probability, Springer Science and Business Media, 1993.
Diaconis, S. Holmes, and R. M. Neal. Analysis of nonreversible Markov chain sampler. Annals of Applied Probability, pages 226-752, 2000.
P. Fearnhead, J. Bierkens, M. Pollock, and G. O. Roberts. Piecewise deterministic Markov processes for continuous-time Monte Carlo. Statistical Science, 33(3):386-411 2018.
A. Gelman and X.-L. Meng. Simulating normalizing constants: From importance sampling to bridge sampling to path sampling. Statistical science: review journal of the Institute of Mathematical Statistics, (3(2): 163-185, 1998.
M. M. Graham and A. Storkey. Continuously tempered Hamiltonian Monte Carlo. Proceedings of the Third Conference Uncertainty in Artificial Intelligence (UAT), 2017.
E. Marinari and G. Parisi. Simulated tempering: new Monte Carlo scheme. EPL (Europhysics Letters), 1966)451, 1992.
R. M. Neal. MCMC using Hamiltonian dynamics. Handbook of Markov chain Monte Carlo, 2(11):2, 2011.
C. Nemeth, F. Lindsten, M. Filippone, and J. Hensman. Pseudo-extended Markov chain Monte Carlo. Advances in Neural Information Processing Systems, 32, 2019.
E. A. J. F. Peters and G. de With. Rejection-free Monte Carlo sampling for general potentials. Physical Review E, 85(2):026703, 2012.
M. Sutton and P. Fearnhead. Concave-Coovex PDMP-based sampling. arXiv:2112.12897, 2021.
10

---

R. H. Swendsen and J.-S. Wang. Replica Monte Carlo simulation of upin-glassen Physical review letters, 57(21):2607, 1986.
S. Syed, A. Bouchard-Côté, G. Deligiannidis, and A. Doucet. Non-reversible parallel tempering: A scalable highly parallel meme scheme. Journal of the Royal Statistical Sociery: Series
(Statistrical Methodology), 84(2):21 2022. doi: https://doi..or//OO... 1/rssb. 12464. URL
httpp::/rss http://sw...nnleeebbbrrrr......r wiw.......ll.......... wwt.://cccooo//////////o http://aww..aaaaloooooo/o//a////
12464
N. G. Tawn, G. O. Roberts, and J. S. Rosenthal. Weight-preserving simulated tempering. Stativtics and Computing, 30(1):27-41, Feb 2020. ISSN 1573-1375. doi: 10. 12.0007//11222-19-9999
URL http::///aa...o./000000001111122
G. Vasdekis and G. O. Roberts. Speed up zig-zag. arXiv:2103./6620, 2021.
D. Woodard, Schmidler, and M. Huber. Sufficient conditions for torpid mixing of parallel and simulated tempering. Electron. J. Probab., 14:780-808 804. 2009. ISSN 1083-6489. doi: 10.1214/EJBw11--638 bttp://://ejp..iii ejpecp. htgg/ariiceevviee
C. Wu and C. P. Robert. Coordinate sampler: non-reversible Gibbs-like MCMC sampler. Statistics and Computing, 30(3):221-73, 2020.
Y. Yao, C. Cademartori, A. Vehtari, and A. Gelman. Adaptive path sampling in metastable posterior distributions. TrXiv:2009.0047/ 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Broader Impact statement.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Theorem
(b) Did you include complete proofs of all theoretical results? [Yes] See Supplementary Material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main exper- imental results (either in the supplemental material or as a URLY? [Yes] See Supple- mentary Material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Numerical Experiments section.
(c) Did you report error bars (c.g., with respect the random seed after running ex- periments multiple times)? [Yes] See plots included in Supplementary Material for visualization of variability for multiple runs.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Supplementary Material.
4. If you using existing assets (e.g., code, data, models) curating/releusing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 4.3.
(b) Did you mention the license of the assets? [Yes] See Supplementary Material.
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
Yes, Supplementary Material.

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [Yes] See Supplementary Material.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "tzuLrmDQzRk", "reviewer": "Reviewer_rki5", "summary": "The manuscript proposes to use a modification of the ZigZag sampler (or any almost any other PDMP sampler) to sample from complex (eg. multimodal) target distributions. The approach proceeds by introducing a \"temperature\" parameter $\\beta \\in [0,1]$ and an extended distribution with a Dirac mass at $\\beta=1$ (corresponding to the target distribution of interest) and run a slightly-modified ZigZag sampler on the extended target. Samples obtained at temperatures $\\beta < 1$ can still be used by using an importance sampling scheme, if necessary.", "questions": "1. Choosing the distribution $p(\\beta)$ is indeed crucial in not-entirely-trivial situations. I think that this section should be expanding greatly. Choosing $\\kappa(\\beta) \\propto 1/Z(\\beta)$ is indeed a good strategy, I think, but quite hard to implement in practice in difficult situations. How do the authors think this should be done in practice? There are about 3 lines describing this and one would expect a much more thorough discussion since it is likely to have a very important impact on the method.\n\n2. Implementing the Zig-Zag, and many other PDMP sampler, is not trivial (eg. simulating the event time, etc..) A metric of the type (accuracy)/(compute time) should be reported. For example, (accuracy) / (number of target or gradient-of-target evaluations) seems like an appropriate metric.\n\n3. It is very standard and straightforward to use SMC methods, or parallel-tempering schemes, to tackle multi-modal situations. Furthermore, it is not that difficult to (almost) automatically tune these methods. I think that it is crucial to compare the proposed method to these standard alternatives (and report ESS or MSE per compute time!). Since the method is relatively simple (which is good), it seems natural to expect very thorough numerical experiments.\n\n**minor remarks:**\n1. Are we assuming $\\kappa(\\beta)=1$ so that $\\int_{[0,1]} p(\\beta) d\\beta=1$? \n", "limitations": "NaN", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength:**\n\nThe text is well-written and very easy to follow. Furthermore, the approach is quite natural and, to the best of my knowledge, novel. \n\n**Weaknesses:** \nThe method is simple to implement (which is an advantage) and its working principles are intuitive. Unfortunately, I have not found the numerical experiments extremely convincing. As a matter of fact, after reading the paper, I am not concince that I would like to give the method a try (even if it is simple to implement). See next section for more detailed remarks. As of now, I am leaning towards a \"weak reject\" since I am finding the empirical evaluation section to not be up to the standard of NeuRIPS.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "U-QAgUMpRRm", "reviewer": "Reviewer_77P1", "summary": "The authors show how to use (continuous) simulated tempering in conjunction with a PDMP sampler (in particular, the zig-zag sampler) to sample from multi-modal distributions. In the process that they propose, once the process hits $\\beta=1$, it spends an amount of time there that is an exponential rv; this ensures that the marginal distribution of the inverse temperature is a mixture of a continuous distribution on [0,1) and a point mass at 1, which allows obtaining samples directly rather than from importance/rejection sampling. Experiments show significantly improved performance compared with the non-tempered algorithm, as well as how the root-mean-square error and thinning efficiency depends on the value chosen for alpha (parameter controlling how much time the process spends at $\\beta=1$).", "questions": "* Line 61-62: \"this means we can obtain samples from $\\pi(x)$ rather than having to resort to importance sampling to correct samples drawn at different temperatures\" - in what sense is the proposed approach better than using correction using importance sampling?\n* Line 66-67: Can you explain or give a reference for the issue with the HMC sampler?\n* Line 156-157: Can't you use importance sampling no matter what \\beta is, by using the ratio of the unnormalized distribution at the temperature of the sample and at temperature 1?\n\nMinor notes:\n\n* line 171: \"important\" sampling -> \"importance\"\n", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors propose a simple, easy-to-use extension of PDMP (specifically the zig-zag sampler) that significantly improves its performance on multi-modal objectives in simulations. The simulations show how the parameters can be tuned to minimize the error. The paper is generally clear.\n\nHowever, only the zig-zag sampler was considered in this work. Furthermore, one limitation of the simulated tempering-based approach is the necessity of estimating the normalizing constant (discussed in section 3.4). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DKW4jqZG_cT", "reviewer": "Reviewer_Lpcb", "summary": "This article presents a principled way to do continuous tempering in PDMP samplers, with positive probability of sampling from the actual target distribution. It discusses its ergodicity, implementation and optimisation with respect to the tempering distribution. The method is illustrated on a series of challenging examples.", "questions": "1. I am rather uncertain how Section 3.4 on the calibration of $\\kappa$ differs from Section 2.1. of Yao et al. [2020]. It seems to me that Section 3.4 is a direct special case of the latter. Can you explain how your method is different from this? Note that I understand this is not the main contribution of the article, but believe this kinship between the two methods should be highlighted in case I am not mistaken.\n\n2. The use of $t$ and $s$ in Section 3 of the supplementary material is somewhat fuzzy: $t$ sometimes is a free parameter (or the current time), and sometimes denote the next exent. Clarifying the notation (for instance by calling the event time $\\tau$ as per the main text) would be useful. Referring to the supplementary material at the time of introducing the Zig-zag sampler would be useful too.\n\n3. I believe that the proof that $\\omega$ is an invariant distribution for the given rate (Theorem 1) is correct. However, I believe this to follow more from Proposition 7 of [6] than directly from Theorem 2 and 3; a comment on the other PDMP sampler would also be useful. Moreover, for completeness, it may be useful in the supplementary material to insist that $\\omega$ is the **unique** stationary distribution of the chain.\n\n", "limitations": "One of the main limitations of PDMP is the need to sample from a non-homogeneous Poisson process. This is however thoroughly discussed in the supplementary material. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n--------------\n1. This article is well written, and beside its contributions, offers a good overview of the zig-zag sampler. \n2. The heuristics of the method are clear, and its symbiosis with PDMP samplers made clear.\n3. The method is theoretically grounded, and the article clearly describes the sampling mechanism (thinning) for each example.\n4. The applicability of tempering for transdimensional sampling is particularly convincing.\n\n\nWeaknesses:\n------------------\n1. Because the paper insists that the method applies to any PDMP sampler, a quick review of PDMP samplers in general (as in, a short summary of, e.g., Fernhead et al. [2018]), allowing the reader to confirm that it indeed generalises, would have been welcome in the supplementary material.\n\n2. While the experimental validation is thorough, the reported metrics hardly allow to understand which sampler is best due to the fact we are lacking information on the run time of each method. This is probably the main issue with the article. Given that the RMSE of the MCMC estimates is roughly speaking $O(\\frac{1}{\\sqrt{ESS}})$, and that $ESS$ should increase in average linearly with the run time of the experiment (supposing that the average time to simulate an event is constant), I believe a better metric to report would be $\\frac{RMSE}{\\sqrt{T}}$, where $T$ is the time (e.g., in seconds) to get 50,000 samples from the chains, similarly, the absolute error should then be divided by the time taken (please adapt the $\\sqrt{T}$ terms the way you deem best to match the super efficiency of PDMPs). Would this be feasible? Alternatively (and perhaps better), instead of giving yourself a number of iterations in the chain, you could give yourself a time budget for each chain (for example the average time taken by your experiments) and report the error achieved in this amount of time. I tend to believe this could marginally change the conclusions as it would take into account the thinning efficiency directly into the result.\n\n3. The estimator of Section 3.3 --- which I believe is essentially a Rao-Blackwellisation of the proposed method for a specific choice of tempering prior --- does not seem to be empirically evaluated at all. Instead, a less performing version is used which almost surely does not sample from the target. It would have been interesting to also check if the \"sacrifice\" of using a poorly adapted tempering prior was compensated by being able to use the intermediate samples in the case when there is a point mass at $\\beta = 1$. However, this point is less important than the point 2 above.\n\nSome minor comments and typos:\n---------------------------------------------\n1. The reference style changes between the main paper and the supplementary, making it hard to jump from one to the other. \n2. The citations in the main paper are breaking the text, and it seems like the authors perhaps used \"\\citet{}\" from natbib everywhere. This probably should be corrected for readability. For example \"piecewise deterministic processes (PDMPs) Davis [1993]\" should probably read \"piecewise deterministic processes (PDMPs) [Davis, 1993]\" or similar depending on the chosen style.\n3. The text alternates between of \"piece-wise\" and \"piecewise\"\n4. \"called a piecewise deterministic processes\" -> \"called piecewise deterministic processes\"\n5. \"The idea is that allowing mixing across this set will improve mixing\" -> probably meant \"moving across this set\"\n6. \"transitions from the continuous\" -> \"transitions between ...\"\n7. \"for an exponential period of time\": this sounds like it stays there for a long time, where as you approximately meant \"exponentially distributed\"\n8. \"This will involve additional post-sampling computation of the importance weights at the samples taken from the Zig-Zag trajectory.\" I believe this cost will probably be negligible compared to the cost of simulating from the Poisson process, so this sentence feels overly pessimistic to me.\n9. In the supplementary, the box plots are not linked to the text.\n10. \"Zig-Zag $\\alpha = 1$ and importance\" -> \"Zig-Zag ($\\alpha = 1$) and importance\"\n11. \"and we allow a pointmass at  $\\beta = 1$\" -> \"and we allow a pointmass at $\\beta = 1$\"?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept