Local-Global MCMC kernels: the best of both worlds
Authors: Sergey Samsonov
Evgeny Lagutin
Marylou Gabrié
Alain Durmus
Alexey Naumov
Eric Moulines
Venue: NeurIPS 2022 Accept (2022)
Keywords: MCMC
Markov chains
adaptive MCMC

Abstract: Recent works leveraging learning to enhance sampling have shown promising results, in particular by designing effective non-local moves and global proposals. However, learning accuracy is inevitably limited in regions where little data is available such as in the tails of distributions as well as in high-dimensional problems. In the present paper we study an Explore-Exploit Markov chain Monte Carlo strategy ($\operatorname{Ex^2MCMC}$) that combines local and global samplers showing that it enjoys the advantages of both approaches. We prove $V$-uniform geometric ergodicity of $\operatorname{Ex^2MCMC}$ without requiring a uniform adaptation of the global sampler to the target distribution. We also compute explicit bounds on the mixing rate of the Explore-Exploit strategy under realistic conditions. Moreover, we propose an adaptive version of the strategy ($\operatorname{FlEx^2MCMC}$) where a normalizing flow is trained while sampling to serve as a proposal for global moves. We illustrate the efficiency of $\operatorname{Ex^2MCMC}$ and its adaptive version on classical sampling benchmarks as well as in sampling high-dimensional distributions defined by Generative Adversarial Networks seen as Energy Based Models.

Local-Global MCMC kernels: the best of both worlds
Sergey Samsonov
Evgeny Lagutin'
Marylou Gabrie²
Alain Durmus
Alexey Naumov' Eric Moulines
HSE University Ecolee Polytechnique ENSS Paris-Saclay
{svsamsonov, elagutin, anaumov) Chsee
peric..ouuinees mnoulines, m alain daw.indduuuuuees--eee pattemusdesssparii---eee saclay .rr
edu
Abstract
Recent works leveraging learning enhance sampling have shown promising results, in particular by designing effective non-local moves and global propos- als. However, learning accuracy is inevitably limited in regions where little data is available such as in the tails of distributions as well as in high-dimensional problems. In the present paper we study an Explore-Exploi Markov chain Monte Carlo strategy (Ex²MCMC) that combines local and global samplers showing that enjoys the advantages of both approaches. We prove V-uniform geometric ergodicity of Ex² MCMC without requiring a uniform adaptation of the global sampler to the target distribution. We also compute explicit bounds on the mixing strategy under realistic conditions. Moreover, we also
rate of the Explore-Exple analyze an adaptive version of the strategy (FIEX* where normalizing flow is trained while sampling to serve a proposal for global moves. We illustrate the efficiency of E and its adaptive version on classical sampling bench- marks as well in sampling high-dimensional distributions defined by Generative Adversarial Networks seen as Energy Based Models.
Introduction
We consider the setting where a target distribution æ on a measurable space (X, X²) is known up to normalizing constant and one tries to estimate the expectations of some function f X + I with respect to π. Examples include the extraction of Bayesian statisties from posterior distributions derived from observations as well as the computation of observables of a physical system & E X under the Boltzmann distribution with non-normalized density (2) = (U) for the energy function U the inverse temperature 3.
common strategy to tackle this estimation to resort to Markov chain Monte Carlo algorithms (MCMCs). The MCMC approach aims simulate realization of time-homogeneone Markov chain (Yn, n E N), such that the distribution of the n-th iterate Y, with n - oo is arbitrarily close ग, regardless of the initial distribution of Yo. In particular, the Satropolii-Hastting kernel (MH) is the cornerstone of MCMC simulations, with number of successful variants following the process of proposal step followed by an accept/reject step (see e.g. 62 In large dimensions, proposal distributions are typically chosen to generate local moves that depend on the last state of the chain in order to guarantee an admissible acceptance rate. However, local samplers suffer from long mixing times as exploration is inherently slow, and mode switching, when there is more than one, can be extremely infrequent.
On the other hand, independent proposals are able to generate more global updates, but they are difficult design. Developments in deep generative modelling, in particular versatile autoregressive and normalising flows 39
20 55), spurred efforts to use learned probabilistic models to improve
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the exploration ability of MCMC kernels. Among rapidly growing body of work, references include [3 While these works show that global moves in number of practical problems can be successfully informed by machine learning models, it remains the case that the acceptance rate of independent proposals decreases dramatically with dimensions - except in the unrealistic case that they perfectly reproduce the target. This is well-known problem in the MCMC literature [12 71 D. and it was recently noted that deep learning-basee suggestions are no exception in works focusing on physical systems [19 46].
36
2
5
25
In this paper we focus on the benefits of combining local and global samplers. Intuitively, local steps interleaved between global updates from an independent proposal (leared or not) increase accuracy by allowing accurate sampling tails that are not usually well handled by the independent proposal. Also, mixing time is usually improved by the local-global combination, which prevents long chains of consecutive rejections. Here we focus on a global kernel of type sterative-smpllnng importance resampling (i-STR) 7 4
[ This kernel uses multiple proposals in each iteration to take full advantage of modern parallel computing architectures. For local samplers, we consider common techniques such as Metropolis Adjusted Langevin (MALA) and Hamiltonian Monte Carlo (HMC). We call this combination strategy Hxplorre-xploii MCMC (Ex" MCMC) in the following.
Contributions
The main contributions of the paper are as follows:
We provide theoretical bounds the accuracy and convergence speed of MCMC strategies. In particular, we prove V-uniform geometric convergence of EX'MCMC under assumptions much milder than those required prove uniform geometric ergodicity of the global sampler i-STR alone.
We provide convergence guarantees for an adaptive version of the strategy, called TIEx2MCMM which involves learning an efficient proposal while sampling, as in adaptive MCMC.
We perform a numerical evaluation of Exx MCMC and PIEX2MCMC for various sampling prob- lems, including sampling GANs energy-based models. The results clearly show the advantages of the combined approaches compared to purely local or purely global MCMC methods.
Denote N = N N {0}. For a measurable function f X + R. we define |fl supzex [f()] and Tff) == fx (dx). For a function V X + (1) we introduce the V-norm of two probability measures & and g on (X, X", IlE -''llv== sup sv(x) (E(f) - (f)) If 1, ||- lli equal to the total variation distance (denoted || ||T)).
Notations
2 Explore-Exploit Samplers
Suppose we are given a target distribution π on measurable space (X, X)) that is known only up to a normalizing constant. We will often assume that X = Rd or a subset thereof. Two related problems are sampling from и and estimating integrals of function f X + R w.r.t. t, i.e., π xf)). Among the many methods devoted to solving these problems, there is popular family of techniques based on Importance Sampling (IS) and relying on independent proposals, see e.g. M 74. We first give a brief overview of IS, to describe the global sampler i-SIR. We recall ergodicity results for the latter before investigating the Explore-Exphe
sampling strategy which couples the global sampler with a
local kernel. Then we present the main theoretical result of the paper on the ergodicity of the coupled strategy.
2.1 From Importance Sampling to i-SIR
The primary purpose of IS to approximate integrals of the form xf)). Its main instrument is a (known) proposal distribution, which we denote by X(dx). To describe the algorithm, we assume that (dzz) = ((xx))))))(())))) In this formula, w(xx is the importance weight function assumed to be known and positive, i.e., w(xx) > 0 for all æ X. and X(w) is the normalizing constant of the distribution x. Typically X(w) is unknown. If we assume that æ and À have positive densities w.r.t. common dominant measure, denoted also by π and À respectively, then the self-normalized importance sampling (SNIS, see 61) estimator of (Tf) is given by
TN(S) CENWWN/(X
1.4. ~ X, and w/y = w(x) En= wX²) are the self-normalized importance weights. Note that computing w'y does not require the knowledge of X(w). The main problem in the practical applications of IS the choice of the proposal distribution X. The representation T (dr)- w(x))(dx))/)) implies that the support of À covers the support of m. At the same
where 1
2

---

Algorithm 1: Single stage of i-SIR algorithm with independent proposals
Procedure i-STR (Ve, A):
Input :Previous state V&: proposal distribution A; Output:New state Yk+1: pool of proposals X X2:N
2
Set x = YE. draw x ~ >; for E [N] do
compute the normalized weights w1,++1 w 1/ Ee w(X
Draw the proposal index 1++1 (aa(ss1-1.........
Set V -X/111
time, too large variance of is obviously detrimental the quality of ( This suggests adaptive im- portance sampling techniques (discussed in [T))). which involve learning the proposal X to improve the quality of I We return to this idea in section
IS -based techniques can also be used to draw an (approximate) sample from æ. For instance, Sampling Importance Resampling (SIR, (68) follows the steps:
1. Draw X1:N lid. X;
2. Compute the self-normalized importance weights w = w(x)) EE w(X), NJ,
3. Select M samples I1:M from the set X choosing X with probability w/y with replacement.
The drawback of the procedure is that it is only asymptotically valid with N - 0o. Alternatively, SIR can be repeated to define Markov Chain as in iterated SIR (i-SIR), proposed in (7 and also studied in 4 43 42 [5. At each iteration of i-SIR described Algorithm a candidate pool X is sampled from the proposal and the next state Yk+1 is choosen among the candidates and the previous state X = Y according the importance weights. i-SIR shares similarities with the Multiple-try Metropolis (MTM) algorithm 44 but is computationally simpler and exhibits more favorable mixing properties; see Appendix
A.1 The Markov chain (Yk, e N} generated by i-STR
has the following Markov kernel
(2(2, A f (dzx)))
N
w(x') j=1 w(x)
N
IA(x*) ) II A(dx)). J=2
Interpreting i-SIR systematic-scan two-stage Gibbs sampler (see Appendix A.2 for more details), follows easily that the Markov kernel Px is reversible w.r.t. the target म, Harris recurrent and ergodic (see Theorem 5. Provided also that |w/xc < co, it was shown in [5] that the Markov kernel P is uniformly geometrically ergodic. Namely, for any initial distribution & on (X, X) and & N,
N 1
| F||TV NNy with eN 2L N 2. L= /w]s>/A(w)) and KN
CN-
We provide simple direct proof of Q in Appendix
Yet, note that the bound 2 relies
significantly on the restrictive condition that weights are uniformly bounded [w)x < cc. Moreover, even when this condition is satisfied, the rate KN can be close to when the dimension is large We illustrate this phenomenon on a Gaussian target in Appendix [..2 Figure with an experiment that also contrasts the degradation as dimension grows of the purely global sampler with the robustness of the local-ge local-global kernels analyzed in the next section.
2.2 Coupling with local kernels: MCMC
After each i-STR step. we apply a local MCMC kernel R (rejuvenation kernel), with an invariant distribution We call this startegy Fx² because it combines steps of exploration by i-SIR and steps of exploitation by the local MCMC moves. The resulting algorithm, formulated in Algorithm 2 defines Markov chain {Y, j N} with Markov kernel (N Px)(( f N (z, dl R(y.))
We now present the main theoretical result of this paper on the properties of MCM. Under rather weak conditions, provided that R is geometrically regular (see [2]] Chapter 14]), it is possible
Indeed, consider simple scenario (σ) I p(x,) and A(x) = IT g(xx) for some densities p(-) and g(-) on I.. Then is easy that L (sup,ER p())/ grows exponentially with d.

---

Algorithm 2: Single stage of MCCM algorithm with independent proposals
Procedure Ex² (Yx, R):
Input :Previous state Yk: proposal distribution A; rejuvenation kernel R;
Output:New sample Yi+1: pool of proposals A++1 X;
Zk+1 .x2.1 i-SIR(Y;,
Draw Yx+1* ~ R(Z++1,-).
to establish that EC²MCMC remains V V-uniformly geometrically ergodic even if the weight function w(x) is unbounded.
Definition 1 (V Geometric Ergodicity). A Markov kernel Q with invariant probability measure is V V-geometrically ergodic if there exist constants E 1) and M < co such that, for all x E X and E N. (1, 1--m <llv S M (V()) + =VV))p²
In particular, --gemmetric ergodicity ensures that the distribution of the k-th iterate of Markov chain converges geometrically fast to the invariant probability in V-norm, for all starting points x E X. Here the dependence on the initial state appears on the right-hand side only in V(x). Denote by Varx[w] = [w(z) A(w) {w))>X(da {x((z) the variance of the importance weight functions under the proposal distribution and consider the following assumptions:
AL. (i) R has π. its unique invariant distribution; (ii) There exists function V: X + [1, oc), such that for all r 2 TR > 1 there exist AR. E [0, 1). bR.- < oc, such that RV (z)x) S AR. V V(x) + bR Iv,,
where V, {x: V(x) rr)
A2. (i) For all 2 Woor == sup.ev, (w)))/(()) < oc and (ii) Varx[w]/( < co.
A (ii) states that R satisfies Foster-Lyapunov drift condition for V. This condition is fulfilled by most classical MCMC kernels- - like detropolis-Adjuster Langevin (MALA) algorithm or Hamil- tonian Monte Carlo (HMC), typieally under tail conditions for the target distribution; see 163 22). and [2] Chapter 2] with the references therein. (i) states that the (normalized) importance weights w(()//(w)) are upper bounded on level sets of V This is a mild condition: if X Rdd and V is norm-like, then the level sets V, are compact and w(-) is bounded on V, soon positive and continuous. (ii) states that the variance of the importance weights is bounded; note that this variance is also equal to the x² -ddittance between the proposal and the target distributions which plays a key role in the non- -sympptpiooicc analysis of the performance of IS methods [1 70
and À are
Theorem 2. Assume A and Then, for all X and ls E N.
(I, F| l|v S OKN (=)) + (=))]Kk
(3)
where the constant OK KKy E [0. are given in the proof. In addition, OKN = .K.. + O(N-1)
and RK_ RKN + O(N-1) with explicit expressions provided in (3)
The proof of Theorem 2 is provided in Appendix B.2, We stress that in many situations, the mixing rate RKy of the Mx2MCMC Markov Kernel KN significantly better than the corresponding mixing rate of the local kernel R. provided N is large enough. This is due to the fact that assumptions A and
A do not require to identify the small sets of the rejuvenation kernel R (see 21 Definition 9.3.5)). At the same time, the quantitative bounds on the mixing rates relies on the constants appearing in the small set condition, see 21 Theorem 19.4.1]. Focusing on MALA (see, e.g. (66) as the rejuvenation kernel R we detail bounds in Appendix C and prove in Theorem 20 that the ratio of mixing times of KN is typically very favorable compared to MALA provided that N is large enough.
3 Adaptive version: MCMC
The performance of proposal- based samplers depends on the distribution of importance weights which is related to the similarity of the proposal and target distributions Therefore, yet another strategy to improve sampling performance is to select the proposal distribution À from a family of parameterized distributions } and fit the parameter 0 E θ = RR to the target x, for example, by
minimizing a Kullback-Leinn divergence (KL) 57
50 or matching moments (59 In adaptive
more specifically, it depends on the the quantities appearing in A2 namely, the maximum of the importance weight on a level set of the drift function for the local kernel R and the variance of the importance weights under the proposal

---

64 MCMCs, parameter adaptation is performed along the MCMC run 6 2 propose an adaptive version of Ex MCMC, which we call FIEx MCMC.
In this section we
Normalizing flow proposal. A flexible way to parameterize proposal distributions is to combine tractable distribution op with invertible parameterized transformation. Let 7 X - X be Cº diffcomorphism. We denote by T the push-forward of yp under T', that is, the distribution of X T()) with Z ip. Assuming that yp has a p.d.f. (also denoted y)) the corresponding push-forward density (w..t. the Lebesgue measure) is given by (x) (T (v)) Jr (y), where Jy denotes the Jacobian determinant of T. The parameterized family of diffeomorphisms {To) defines a family of distributions {>T, Jeee. denoted for simplicity as fee. This construction is called normalizing flow (NF) and great deal of work has been devoted to ways of parameterizing
invertible flows T3 with neural networks; see [40 555 for reviews.
Simultaneous learning and sampling, As with adaptive MCMC methods, the parameters of NF proposal are learned for the global proposal during sampling, see also [25]. We work with M copies of the Markov chains {(Yx [[. X [D) indexed by j E {1...., MM. At each step & E N", each copy is sampled as in ExMMCMC using the NF proposal, inde- pendently from the other copies, but conditionally to the the current value of the parameters 0k-1. We then adapt the parameters by taking steps of gradient descent on a convex com- bination of the forward KL, (L(T]|AA) (L())llT)= (2) log(r(=)/>oo())dd
fI(x (o)(=()\\)((z))d and the backward KL I p(2) log we o To(z)dz. Let {*k, E N) be sequence of nonnegative stepsizes and {az, k E N] be nondecreasing sequence in [0, 1] with 0 = som Oik- The update rule is Og 0k- + TMM-- (Ox- X [5]. (2)
where H(0, I.:,, x1:N 22N) Ook H (0,. + (1 - -ax) 2:N) with
H (',,.21:N) -Ex N
wo(x²)
Vo log da (x(),
uo(x) = (x))/>/(x))
(4)
we (x+)
(0,
Veloog o To(2 + Volog (z²))
(5)
N
Note that we use a Raa- nro-Blackwellized estimator of the gradient of the forward KL where we fully recycle all the N candidates sampled at each iteration of i-SIR. The quality of this estimator is expected to improve along the iterations & of the algorithm as the variance of importance weights decreases the proposal improves. Note also that using only gradients from the backward KL (5) is prone to mode-collapse (57 (54 50 (25], hence the need for also using gradients from the forward KL (0,00..::) ..::N), which requires the simultaneous sampling from æ. See also Appendix R.5 for further discussions. The MCMC algorithm is summarized in Algorithm
Since the parameters of the Markov kernel 0μ are updated using samples X from the chain, ((r,, X...XI-- ) JLEN is no longer Markovian. This type of problems has been considered in 48 1 30 and to prove convergence of the strategy we need to strengthen assumptions compared to the previous section.
A3. There exists function W X R. such that p(W2) = ( (z))p(()) co, and constant L < oo such that, for all 0, 0 e and & E X. | log o To(:) - Vo log R (2)) v
L| - -0' and [[V log JT, (z) Ve log JTg. (2)Il L - O'))W(2).
A4. (i) For all d 2 dR. Woo,d supage supreva (>)(()))))) < co.
< and (ii) supace Var
Bis is continuity condition on the NF forward density w.r.t. its parameters 0. the Markov kernel KN.0 a = PN,eR satisfies a drift and minorization condition uniform in 6.
A immliees that
Theorem 3 (simplified). Assume A and that Σn I xc, -x 2h < and lim Cg = a... Then, w.p. 1, the sequence {0x, k E N} converges to the set (0- E 0 0. VKL(T]])o) + a (KLL) [[]).
Theorem 3 proves the convergence of the learning of parameters 0 to stationary point of the loss. The proof is postponed to Appendix D Note that once the proposal learning has converged, FIE boils back to MCMC with fixed learned proposal. Our experiments show that adaptivity can significantly speed up mixing for i-STR, especially for distributions with complex geometries and that the addition of a rejuvenation kernel further improves samples quality.
5

---

Algorithm 3: Single stage of MCMC. Steps of MCMC use the NF proposal with parameters bx. Step 4 updates the parameters using the gradient estimate obtained from all the chains.
Input :weights 0s, batch (x(1 : M] Output: new weights 0k+1, batch Yz- [1: M]
for j E [AM] do
L
Y++1 = Ex (Yn, To, #4 R)
3 Draw Z[1 .M] ~ q.
Update 02 = 0k-1 + M 1 اッ= 1(00-1,, X N
M
[J. 22
4 Related Work
The possibility to parametrize very flexible probabilistic models with neural networks thanks to deep learning has rekindled interest in adapting MCMC kernels; see e.g. 72
B While significant performance gain were found in problems of moderate dimensions, these learning-base -based methods were found to suffer from increasing dimensions as fitting models accurately becomes more difficult [9]46]. 46 Similarly MCEX, few work proposed adaptive algorithms that alternates between global and local MCMC moves to ensure ergodicity without requiring a perfect learning 59 focused on multimodal distributions and analysed of the proposal 5 2 More precisely,
36
2
3
mode jumping algorithm using proposals parametrized as mixture of simple distributions. While [25], closer to this work, introduced a combination of a local and global sampler leveraging normalizing flows with a more classical choice for the global sampler: independent Metropolis- -astiig (IMH) instead of i-SIR. The present work builds on these previous propositions of combinations of local and global sampler by clarifying the reasons of their effectiveness through entirely novel detailed mathematical and empirical analyses. We chose to focus on i-SIR. with an adaptive proposal as the global sampler since (i) the learning component allows to tackle high sigh-dimensional targets, (ii) theoretical guarantees can be obtained for i-STR whereas IMH is more difficult to analyze, (iii) IMH and i-SIR (as a multiple-try try MCMC) are expected to have similar performances for comparable computational budget [1]] but IMH is sequential where i-SIR can be parallelized by increasing the number N of proposals per iteration.
Another line of work exploits both normalizing flows and common local MCMC kernels for sampling [57] 36 77.. yet following the different paradigm of using the flow as a reparametrization map, a method sometimes referred to as neural transport: the flow T is trained to transport a simple distribution & near т, which is equivalent to bringing T T-1## (the pushforward of the original target distribution π by the inverse flow T- close to yp If yo is simple enough to be efficiently sampled by local samplers, the hope is that local samplers can also obtain high- nigh-quality samples of T # samples which can be transported back through T to obtain samples of æ. This method attempts to reparametrize the space to disentangle problematic geometries for local kernels. Yet, it is unclear what will happen in the tails of the distribution for which the flow is likely poorly learned. Furthermore, in order to derive an ergodicity theory for these transported samplers, [57) necessitated substantial constraints on maps (see section 2.2.2.).
5
Numerical experiments
We provide the code to reproduce the experiments below at https://github httpgiitib..cmm///ssssssoooooooo ex2mmmmc_ [ew new
5.1
Synthetic examples
Multimodal distributions. Let us start with toy example highlighting differences between purely global i-SIR, purely local MALA and MCM combining both. We consider sampling from mixture of equally weighted Gaussians in dimension d 2. In Figure Lal we compare single chains produced by each algorithms. The global proposal is wide Gaussian, with pools of N = 3 candidate. The MALA stepsize chosen to reach target acceptance rate of ~ 0.67. This simple experiment illustrates the drawbacks of both approaches: i-SIR samples reach all the modes of the target, but the chains often get stuck for several steps hindering variability. MALA allows for better local exploration of each particular mode, yet it fails to cover all the target support. Meanwhile, MCMC retains the benefits of both methods, combining the i-STR- based global exploration with MALA-based local exploration.

---

MALA samples
i-SIR samples
EX²MCMC samples
MALA tehovd
(b)
3.0
(a)
(c)
Figure 1: (a) Single chain mixing visualization. Blue color levels represent the target 2d density, Random chain initialization is noted in black, 100 steps are plotted per sampler: the size of each red dot corresponds to the number of consecutive steps the walkers remains at given location. Note that the variance of the global proposal (dotted countour lines) should be relatively large to cover well all the modes. (b c) Inhomogeneous 2d Gaussian mixture. Quantitative analysis during burn-in of parallel chains (b, M 500 chains KDE) and for after burn-in for single chains statistics (c, MM- = 100 average).
In larger dimensions, an adaptive proposal is necessary. In Appendix we show that PIEx2MCMC can mix between modes of a 50d Gaussian mixture, provided that the rough lo- cation of all the modes is known and used to initialize walkers. We also stress the robustness of the on-the-fly -ly training exploiting rumning MCMC chains evaluate the forward KL term of the loss.
E.5
To illustrate further the performance of the combined kernel, we keep the 2d target mixture model yet assigning the uneven weights (2/3, /6, 1 /66 to the 3 modes. We start M chains drawing from the initial distribution ę ~ NO, Ta) and use the same nyper-parameete we provide simple illustration to the statement 2 and Theorem 2 namely we compare the target density to the instantancous distributions for each sampler propagating & during burn-in steps. As MALA does not mix easily between modes, the different statistical weights of the different modes can hardly be rendered in few iterations and KL and TV distances stalls after few iterations. i-SIR can visit the different modes, yet it does not necessarily move at each step which slows down its covering of the modes full support, which again shows in the speed of decrease of the TV and KL. Overcoming both of these shortcomings, Ex? MCMC instantaneous density comes much closer to the target. Finally, Figure I evaluates the same metrics yet for the density estimate obtained with single chain samples after burn-in. Results demonstrate once again the superiority of Ex MCMC. Further details on these experiments can be found Appendix E.3
as above. In Figure Tb
Distributions with complex geometry. Next, we turn to highly anisotropic distributions in high dimensions. Following [52] and [32] we consider the finnel and the banana-shape distributions.
We remind densities in Appendix E.6 along with providing experiments details. For d E [10; 200],
i-SIR, MALA, MCMM MCMC, adaptive i-SIR. (using the same proposal as MCMX but without interleaved local steps) and the versatile sampler NUTS (35 as a baseline. Here the parameter adaptation for MCEX performed in a pre-run and parameters are frozen before sampling. For the adaptive samplers, a simple RealNVP-basee normalizing flow 20 is used such that total running times, including training, are comparable with NUTS. For MCM and i-SIR the global proposal is a wide Gaussian with a pool of N = 2000 candidates drawn at each iteration. For MALA we tune the step size in order to keep acceptance rate approximately at 0.5. We report the average sliced TV distance and ESS in Figure (see Appendix E. for metrics definition). In most cases, FlEx² MCMC is the most reliable algorithm. The only exception is at very high dimension for the banana where NUTS performs the best: in this case, tuning the flow to learn tails -igh-dimnnsion faithfully was costly such that we proceeded to an early stopping to maintain comparability with the baseline. Remarkably, FIEx2MCMM compensates significantly for the imperfect flow training, improving over adaptive-i-SIR, but NUTS eventually performs better. Conversely, for the funnel, most of the improvement comes from well-trained proposal flow, leading to similar behaviors of adaptive i-STR and FCFX2MCMC, while both algorithms clearly outperforms NUTS in terms of metrics.
7

---

True
True
PMNN MALL depn
ESC
-2.
2-
20
122
100
(b) Banana-shape distribution
(a) d 100, 2000 samples projection
Thue samples
The samples NUTS samples
FEXNCCNC
6.3
632
31
07
100
dimenoze
(d) Neal's funnel
(c) d 100, 1000 samples projection
Figure 2: Anisotropic Funnel and Banana-shape distributions - (a) and (b) visualize samples projected onto the first 2 coordinates of tested algorithms (blue) versus true samples obtained by reparametriza- tion (orange). (c) and (d) compare Sliced Total Variation and Effective Sample Size as function of dimension. i-SIR is removed from (b) as corresponding metrics for d > 20 are significantly worse.
5.2 Sampling from GANs as Energy-based models (EBMs)
Generative adversarial networks (GANs (27] are a class of generative models defined by a pair of a generator network G' and discriminator network D. The generator G takes latent variable from prior density Po (=), = E Rd, and generates an observation G(z) E IRD in the observation space. The discriminator takes a sample in the observation space and aims discriminate between true examples and false examples produced by the generator. Recently, it has been advocated to consider GANs as Energy-Based Models (EBMs) 77 17. Following [7 we consider the EBM model induced by the GAN in latent space. Recall that EBM is defined by Boltzmann distribution p(=) e e-E(s) 7,, E R& where E(z) is the energy function and ZZ is the normalizing constant. Note that Wasserstein GANs also allow for an energy-based interpretation (see [77,, although the interpretation of the discriminator in this case is different. The energy function is given by
E2s(2)= log Po (z) logit (D(G(=)))
(= log (o)) D(G(=)), 2 Rd (6)
for the vanilla Sensen-Shannon and Wasserstein GANs, respectively. Here (ygit(y), y E (0.1) is the inverse of the sigmoid function and (= = Lo)
MNIST results. We consider simple -hannnn GAN model trained on the MNIST dataset with latent space dimension d = 2. We compare samples obtained by i-SIR, MALA, and MCMC from the energy- based model associated with E2s(2), see C We use wide normal distribution as the global proposal for i-SIR and Ex² MCMC, and pools of candidates at each iteration N = 10. The step-size of MALA is tuned to keep acceptance rate 0.5. We visualize chains of 100 steps in the latent space obtained with each method in Figure 3 Note that the poor agreement between the proposal and the landscape makes it difficult for i-SIR accept from the proposal and for MALA to explore many modes of the latent distribution, as shown in Figure 3 Mx2MCMC combines effectively global and local moves, encouraging better diversity associated with a better mixing time. The images corresponding to the sampled latent space locations are displayed in Figure 4 and reflect the diversity issue of MALA and i-SIR. Further details and experiments are provided in Appendix
E.7. including similar results for WGAN-GP [1 and the associated EBM Ew (z).
Cifar-10 results.
We consider two popular architectures trained on Cifar- 10, DC-GAN [60| and SN-GAN 40 In both cases the dimension of the latent space equals
128. Together with the
non-trivial geometry of the corresponding energy landscapes, the large dimension makes sampling with NUTS unfeasible in terms of computational time. We perform sampling from mentioned GANs as energy-based models using i-STR, MALA, Ex²MCMC, and FIEx"MCMC, In i-SIR
and MCM we use the prior p0(2) as global proposal with pool of 10 candidates. For FIEx² MCMC we perform training and sampling simultaneously. Implementation details are
8

---

2
-2
Figure 3: MNIST energy landscape and single chain latent samples visualizations.
/
9
4
8
8
9
9
9
9
4
A
I
1
7
6
0
II
0
9
9
0
(a) i-SIR samples
(b) MALA samples
(c) Ex samples
Figure MNIST samples visualization. - -Single chains run, sequential steps.
provided in Appendix E.7.2 To evaluate sampling quality, we report the values of the energy function E(z), averaged over 500 independent runs of each sampler. We also visualize the inception score (IS) dynamics calculated over 10000 independent trajectories. We present the results Figure 5 together with the images produced by each sampler. Note that MCM and FCEX²MCMC reach low level of energies faster than other methods, and reach high IS samples in a limited number of iterations. Visualizations indicate that MALA is unlikely escape the mode of the distribution p(=) it started from, while i-SIR and MCMC/F/EE MCMC better explores the target support. However, global move appear become more rare after some number iterations for which then exploit a particular mode with MALA steps. We here hit the following limitation: i-SIR remains at relatively high-energies, failing to explore well modes basins but still accepting global moves, while MCMM//EXXMMMMMM explores well modes basins but eventually remains trapped. We predict that improving further the quality of the FIEX²MCMC proposal by scaling the normalizing flow architecture would allow for more global moves.See Appendix E.7.2 E.7.. for additional experiments (including ones with SN-GAN), FID dynamics, and visualizations.
MCMC/FIII*
6 Conclusions and further research directions
Extectic MALK
VALA
2.5
L5 TEVMONG
Flcc/NCCC
110
202
400
603
1000
(c) Ex MCMC samples
(a) Energy decay for 100
(b) IS dynamics, 1000 iterations
iterations
(d) MALA samples
(e) i-SI samples
Figure 5: Cifar- 10 energy and sampling results with DC-GAN architecture. Along the horizonthal lines we visualize each 10th sample from a single trajectory.

---

The present paper examines the benefits of combining local and global samplers. From theoretical point of view, we show that global samplers are more robust when coupled with local samplers. Namely, V-geometric ergodicity is obtained for the Ex²MCMC kernel under minimal assumptions. Meanwhile, the global samplers drives exploration when properly adjusted. Therefore, we also describe the adaptive version parametrized by a normalizing flow. We also check for the learning convergence along the adaptive MCMC run. Finally, series of numerical experiments confirms the superiority of the strategy, including the high-dimensional examples. While the startegy was described and analyzed for the i-SIR. global kernel, we note that it would be possible extend the theory other independent global samplers. We expect that the benefit of the combination would remain. Further studies of FIEx²MCMC, in particular the derivation of its mixing rate, is an interesting direction for future work.
of the strategy involving the learning of global proposal
Acknowledgement
The article was partly prepared within the framework of the HSE University Basic Research Program. This work was partly supported by SCAI from HilParis. A.D. and E.M. acknowledges support from the Lagrange Mathematics and Computing Research Center.
M.G. acknowledges funding
10

---

References
[1] S. Agapiou, O. Papaspiliopoulos, D. Sanz-Alonso, and A. M. Stuart. Importance sampling: Intrinsic dimension and computational cost. Statistical Science, 3203):00--33, 2017.
[2] M. Albergo, G. Kanwar, and P. Shanahan. Flow-based generative models for Markov chain Monte Carlo in lattice field theory. Physical Review D, 100(3):034515, 2019.
[3] C. Andrieu. On random-and systematic-sean samplers. Biometrika, 103(3):719-726, 2016.
2016.
[4] C. Andrieu, A. Doucet, and R. Holenstein. Particle Markov chain Monte Carlo methods. Journal of the Royal Statistical Society: Series B, 72(3):269-34) 2010.
[5] C. Andrieu, A. Lee, M. Vihola, et al. Uniform ergodicity of the iterated conditional SMC and geometric ergodicity of particle Gibbs samplers. Bernoulli, 24(2)842-877, 2018.
[6] C. Andrieu and É. Moulines. On the ergodicity properties of some adaptive meme algorithms. The Annals of Applied Probability, 16(3):1462-1500 2006.
[7] C. Andrieu, É. Moulines, and P. Priouret. Stability of stochastic approximation under verifiable conditions. SIAM Journal on control and optimization, 44(1):283-312, 2005.
[8] C. Andrieu, B. Tadić, and M. Vihola. On the stability of some controlled markov chains and its applications to stochastic approximation with markovian dynamic. The Annals of Applied Probability, 25(1):1-44 2015.
[9] C. Andrieu and J. Thoms. tutorial on adaptive MCMC. Statistics and computing, 18(4):343- 373, 2008.
[10] C. Andrieu and M. Vihola. Markovian stochastic approximation with expanding projections. Bernoulli, 20(2):545-55) 588,, 2014.
[11] M. Bédard, R. Douc, and E. Moulines. Scaling analysis of multiple-try MCMC methods. Stochastic Processes and their Applications, (22(3):758-788 2012.
[12] T. Bengtsson, P. J. Bickel, and B. Li. Curse-of-dimensionalle revisited: Collapse of the particle filter very large scale systems. arXiv: Statistics Theory, pages 316-334, 2008.
[13] A. Benveniste, M. Métivier, and Priouret. Adaptive algorithms and stochastic approximations, volume 22 of Applications of Mathematics (New York). Springer-Verlage Berlin, 1990. Translated from the French by Stephen S. Wilson.
[14] N. Bonneel, M. Van De Panne, S. Paris, and W. Heidrich. Displacement interpolation using lagrangian mass transport. In Proceedings of the 2011 SIGGRAPH Asia Conference, pages 1-12, 2011.
[15] V. S. Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48. Springer, 2009.
[16] M. Bugallo, V. Elvira, L. Martino, Luengo, Miguez, and P. M. Djuric. Adaptive importance sampling: The past, the present, and the future. IEEE Signal Processing Magazine, 34(4):60-79, 2017.
[17] Che, R. Zhang, Sohl-Dickstein, H. Larochelle, L. Paull, Y. Cao, and Y. Bengio. Your GAN is Secretly an Energy-based Model and You Should Use Discriminator Driven Latent Sampling. In H. Larochelle, M. Ranzato, Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 12275-1222 Curran Associates, Inc., 2020.
[18] M.-F. Chen and F-Y Wang. Estimation of spectral gap for elliptic operators. Trans. Amer. Math. Soc.,
1997.
[19] L. Del Debbio, J. Marsh Rossney, and M. Wilson. Efficient modeling of trivializing maps for lattice @4 theory using normalizing flows: first look scalability. Physical Review D, 104(9), 2021.

---

[20] L. Dinh, J. Sick-Dickstein, and S. Bengio. Density estimation using real NVP. In 5th Interna- tional Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017. Conference Track Proceedings, 2017.
[21] R. Douc, E. Moulines, P. Priouret, and P. Soulier. Markov chains. Springer Series in Operations Research and Financial Engineering. Springer, Cham, 2018.
[22] A. Durmus and E. Moulines. On the geometric convergence for MALA under verifiable conditions. 2022.
[23] A. Eberle. Reflection couplings and contraction rates for diffusions. Probab. Theory Related Fields, pages 1-36, 2015.
[24] D. L. Ermak. computer simulation of charged particles in solution. i. technique and equilib- rium properties. The Journal of Chemical Physics, 62(10):4189-411 1975.
[25] M. Gabrié, G. M. Rotskoff, and E. Vanden- -ijnden. Adaptive Monte Carlo augmented with normalizing flows. Proceedings of the National Academy of Sciences, 119(10), mar 2022.
[26] M. Girolami and B. Calderhead. Riemann manifold langevin and hamiltonian monte carlo methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73(2):123 214, 2011.
[27] I. J. Goodfellow, J. Pbudee-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2, NIPS' 14, page 2672-2680, Cambridge, MA, USA, 2014, MIT Press.
[28) U. Grenander. Tutorial in pattern theory. Division of Applied Mathematics, Brown University, Providence, 1983.
[29] U. Grenander and M. I. Miller. Representations of knowledge in complex systems. J. Roy. Statist. Soc. Ser. B, 56(4))5499666 -005,,9,,,....... 1994. With discussion and a reply by the authors.
[30] M. G. Gu and H. Kong. A stochastic approximation algorithm with markov chain monte-carlo method for incomplete data estimation problems. Proceedings of the National Academy of Sciences, 95(13):7270-722
1998.
[31] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville. Improved train- ing of wasserstein gans. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[32] H. Haario, F. Saksman, and Tamminen. Adaptive proposal distribution for random walk metropolis algorithm. Computational Statistics, 14(3):375-395, 1999.
[33] D. C. Hackett, C.-C. Hsieh, M. S. Albergo, D. Boyda, J.-W. Chen, K.-F Chen, K. Cranmer, G. Kanwar, and P. E. Shanahan. Flow-based sampling for multimodal distributions in lattice field theory. arXiv preprint, 2107.00734, 2021.
[34] M. Heusel, H. Ramsauer, Unterthiner, Nessler, and S. Hochreiter. Gans trained by a two time-scale update rule converge to local nash equilibrium. In I. Guyon, U. V. Luxburg, Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[35] M. D. Hoffman, A. Gelman, et al. The no- no-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo. J. Mach. Learn. Res., 15(1):1933-122 2014.
[36] M. D. Hoffman, P. Sountsov, J. V. Dillon, I. Langmore, D. Tran, and S. Vasudevan. NeuTra- lizing Bad Geometry in Hamiltonian Monte Carlo Using Neural Transport. In /st Symposium on Advances in Approximate Bayesian Inference, 2018 1-5, 2019.
12

---

[37] C.-W. Huang, D. Krueger, A. Lacoste, and A. Courville. Neural autoregressive flows. In Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 2078-2087, PMLR, 10-15 Jul 2018.
[38] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR 2015, 2013.
[39] D. P. Kingma, T. Salimans, R. Jozefowicz, X. Chen, I. Sutskever, and M. Welling, Improving variational inference with inverse autoregressive flow, 2016.
[40] Kobyzev, S. Prince, and M. Brubaker. Normalizing flows: An introduction and review of current methods. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
[41] H. J. Kushner and G. G. Yin. Stochastic approximation and recursive algorithms and appli- cations, volume 35 of Applications of Mathematics (New York). Springer- Verlag, New York, second edition, 2003. Stochastic Modelling and Applied Probability.
[42] A. Lee. On auxiliary variables and many-core architectures in computational statisties. PhD thesis, University of Oxford, 2011.
[43] A. Lee, C. Yau. M. B. Giles, A. Doucet, and C. C. Holmes. On the utility of graphics cards to perform massively parallel simulation of advanced Monte Carlo methods. Journal of computational and graphical statistics. 19(4):769-78)) 2010.
[44] S. Liu, F. Liang, and W. H. Wong. The multiple-try method and local optimization in Metropolis sampling. Journal of the American Statistical Association, 95(449):121- 134, 2000.
[45] J. S. Liu, W. H. Wong, and A. Kong. Covariance structure of the gibbs sampler with applications to the comparisons of estimators and augmentation schemes. Biometrika, 81(1):27-40, 1994.
[46] A. H. Mahmoud, M. Masters, S. J. Lee, and M. A. Lill. Accurate Sampling of Macromolecular Conformations Using Adaptive Deep Learning and Coarse-Grained' Representation. Journal of Chemical Information and Modeling, 6207))1602-1617, apr 2022.
[47] J. Mattingly, A. Stuart, and D. Higham. Ergodicity for (SDEs) and approximations: locally lipschitz vector fields and degenerate noise. Stochastic Processes and their Applications, 101(2):185 - 232, 2002.
[48] M. Métivier and P. Priouret. Théorèmes de convergence presque sure pour une classe d' d'algorithmes stochastiques à pas décroissant. Probability Theory and related fields, 74(3):403- 428, 1987.
[49] T. Miyato, Kataoka, M. Koyama, and Y. Yoshida. Spectral normalization for generative adversarial networks. arXiv:1802 180.005972. 2018.
[50] C. A. Naesseth, F. Lindsten, and D. Blei. Markovian score climbing: Variational inference with (plll))). Advances in Neural Information Processing Systems, DD2C-DecemMMCMCC, 2020.
[51] R. M. Neal. Bayesian learning via stochastic dynamics. In Advances in Neural Information Processing Systems 5, INIPS Conference], pages 475-482, San Francisco, CA, USA, 1993.
Morgan Kaufmann Publishers Inc.
[52] R. M. Neal. Slice sampling. The Annals of Statistics, 31(3):705 - 767, 2003.
[53] K. A. Nicoli, S. Nakajima, N. Strodthoff, W. Samek, K. R. Müller, and P. Kessel. Asymptotically unbiased estimation of physical observables with neural samplers. Physical Review E, 101(2), 2020.
[54] Noé. Olsson, J. Köhler, and H. Wu. Boltzmann generators: Sampling equilibrium states of many-body systems with deep learning. Science, 365(6457), 2019.
[55] G. Papamakarios, E. Nalisnick, D. J. Rezende, S. Mohamed, and B. Lakshminarayanan. Nor- malizing flows for probabilistic modeling and inference. Journal of Machine Learning Research, 22(57): 2021.
13

---

[56] G. Parisi. Correlation functions and computer simulations. Nuclear Physics B, 180:378-384,
1981.
[57] M. D. Parno and Y. M. Marzouk. Transport map accelerated markov chain monte carlo. SIAM-ASA Journal on Uncertainty Quantification, 6(2):645-687) 2018.
[58] D. Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electromic Journal of Probability, 20(none): 32, 2015.
[59] E. Pompe, C. Holmes, and K. Latuszyúski. A framework for adaptive meme targeting multi- modal distributions. Annals of Statistics, 48(5):2930-2955) 2020.
[60] A. Radford, L. Metz, and Chintala. Unsupervised representation learning with deep convolu- tional generative adversarial networks. arXiv:1511.06444 2016.
[61] C. Robert and G. Casella, Monte Carlo statistical methods. Springer Science & Business Media, 2013.
[62] C. Robert. The Metropolis-Hasting Algorithm, pages 1-15. John Wiley & Sons, Ltd, 2015.
[63] G. O. Roberts and J. S. Rosenthal. General state space markov chains and meme algorithms. Probability surveys, 1:20-71, 2004.
[64] G. O. Roberts and J. S. Rosenthal. Examples of adaptive meme. Journal of computational and graphical statistics, 18(2)339-3367, 2009.
[65] G. O. Roberts and R. L. Tweedie. Exponential convergence of Langevin distributions and their discrete approximations. Bermoulli, 2(4):341-363, 1996.
[66] G. O. Roberts and R. L. Tweedie. Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms. Biometrika, 83(1):95-110, 03 1996.
[67] J. Rossky, Doll, and L.. Friedman. Brownian dynamics as smart Monte Carlo simulation. The Journal of Chemical Physics, 69(10)):628-46333 1978.
[68] D. Rubin. Comment: A noniterative Sampling/mpportacce Resampling alternative to the data augmentation algorithm for creating a few imputations when fractions of missing information are modest: The SIR algorithm. Journal of the American Statistical Association, 824398):542-543, 1987.
[69] Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, X. Chen, and X. Chen. Improved techniques for training gans. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[70] D. Sanz-Alonso. Importance sampling and necessary sample size: an information theory approach. SIAM/ASA Journal on Uncertainty Quantification, 6(2):867-879, 2018.
[71] C. Snyder, T. Bengtsson, P. Bickel, and Anderson. Obstacles high-dimensional particle filtering. Monthly Weather Review, 136(12):4629- - -6640, 2008
[72] J. Song, S. Zhao, and S. Ermon. A-NICE-MC: Adversarial training for MCMC. In Advances in Neural Information Processing Systems, pages 5140-5150, 2017.
[73] H. Tjelmeland. Using all Metropolis Hastiings proposals to estimate mean values. Technical report, 2004.
[74] S. T. Tokdar and R. E. Kass. Importance sampling: review. WIREs Computational Statistics, 2(1):54 60, 2010.
[75] R. Turner, J. Hung, E. Frank, Y. Saatchi, and J. Yosinski. Metropolis generative adversarial networks. In International Conference on Machine Learning, pages 6345-6353. PMLR, 2019.
14

---

[76] D. Wu, L. Wang, and P. Zhang. Solving Statistical Mechanics Using Variational Autoregressive Networks. Physical Review Letters, 122(8)11-11, 2019.
[77] L. Zhang, C. A. Naesseth, and D. M. Blei. Transport Score Climbing: Variational Inference Using Forward KL and Adaptive Neural Transport. arXiv preprint, 2202.01841, 2022.
15

---

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 descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] The paper suggests novel MCMC technique and is validated on artificial and standard datasets.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? (Yes] See Section and Section in the main text.
2
(b) Did you include complete proofs of all theoretical results? [Yes] Yes, the proofs of Section and Section $ are provided in Appendix B and Appendix D
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or URL)? [Yes]] Code to reproduce experiments is attached to the supplement. Due to size constraints, we are not available to present all the pre-trained GANs models for the section Section 5 but we intend to do so when possible.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The hyperparameters are provided in the supplement paper.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Partially yes, but not for all experiments.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We provide this information in the supplement paper.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We use only the common knowledge datasets.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(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 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]
16


Reviews:
[{"review_id": "zCW2xZgskya", "reviewer": "Reviewer_UfPV", "summary": "This work proposes a novel MCMC kernel which consists of a \"local\" move $\\mathsf{R}$ (e.g. a Metropolis-adjusted Langevin update) followed by a \"global\" i-SIR update. The latter is an MCMC kernel which proposes multiple particles from a distribution $\\lambda$ which does not depend on the current state of the Markov chain and then potentially accepts one of these as the new state. The authors prove that the algorithm is geometrically ergodic.\n\nThe authors also consider adapting the proposal distribution $\\lambda$ to the target distribution by specifying it through a normalising flow and taking gradient steps to minimise a suitable convex combination of forward and backward KL divergence at each iteration. Under additional assumptions, they show that the amount of adaptation converges to zero, i.e. adapting the proposal does not \"break\" the algorithm.", "questions": "I'm curious why this has been submitted here rather than to a computational statistics journal where the theoretical guarantees may find more appreciation (and where reviewers have more time to review these).\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Extensive theoretical guarantees including for the adaptive case (although I didn't not check the proofs in the appendix). To my knowledge, these are novel.\n\n2. The presentation is very clear.\n\n3. The proposed algorithm is demonstrated to be competitive in low to moderate dimensions.\n\nWeaknesses:\n\n1. The proposed algorithm itself is not the most original since it is simply a composition of two well-known MCMC kernels.\n\n2. I appreciate that the page limit is very tight but it would be useful to have more explanation of the constants that appear in Theorem 2 in the main manuscript. For instance, in Theorem 2, does the analysis demonstrate that the convergence rate is provably better for the proposed algorithm than for just the rejuvenation kernel alone?\n\n3. In the \"multimodal distributions\" example in Section 5.1, I think it needs to be stressed that the proposed method would likely not work well for larger dimensions $d$ (the example uses $d = 2$). The way the example is presented might give some non-experts the idea that the proposed algorithm can overcome the problem targetting a distribution with well-separated modes in higher dimensions which is not the case. Of course, in fairness, I don't know of any other method that would work in such a scenario.\n\n\nSome typos:\n\n- l.117: missing space after \"strategy\"\n- l.213: work -> works\n- l.213: alternates -> alternate\n- l.218: author -> authors\n- l.248: stalls -> stall\n- l.257: \"remind\"\n- l.257: define the \"$[x;y]$\" notation\n- l.272: outperforms -> outperform\n- Bibliography: there are missing details/inconsistent use of journal name abbreviations/missing capitalisation of proper nouns in a number of entries\n- Theorem 2: Equation 13 is referenced here but can only be found in the appendix", "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": "N1Z22pLHDmM", "reviewer": "Reviewer_9sXT", "summary": "The authors propose to combine a global MCMC kernel with a local MCMC kernel to achieve exploration and exploitation. Specifically, they use iterate sampling importance resampling proposed in [H. Tjelmeland, 2004] as the global kernel and MALA as the local kernel. To further improve the proposal distribution in the global kernel, the authors apply normalizing flow to learn a proposal that is close to the target distribution. The authors prove the V -uniform geometric ergodicity of the proposed method. Empirical results on synthetic distributions, and the latent space of Generative adversarial networks demonstrate the effectiveness. \n\n", "questions": "In Figure 1, how does local MCMC (which is MALA on this task) perform? On a standard Gaussian, I guess MALA should perform well. It might be more convincing to show a case, such as the multimodal distribution in Section 5.1, where Ex2MCMC is better than purely i-SIR and purely MALA. \n\nTheorem 2 provides the mixing rate of the proposed Ex2MCMC. Could the authors compare it with the mixing rate of i-SIR and MALA? Under which conditions, Ex2MCMC is faster? I do not find a discussion on it in the current form.\n\nIt might be clearer to summarize the adaptive Ex2MCMC in an algorithm box, then we can see what are the differences between Ex2MCMC and adaptive Ex2MCMC by comparing it with Algorithm 2.\n\nThe related work section is a bit vague. It is unclear to me how the proposed method differs from previous work and what are the pros and cons. For example, [1] also combines local and global MCMC kernels and the global kernel is also learned by a normalizing flow. Is the difference only in the global sampler where [1] uses independent MH and the proposed method uses i-SIR? In the second paragraph, the authors simply claimed, “another line of work exploits both normalizing flows and common local MCMC kernels for sampling, yet in a different way” without explaining in what different way. \n\nIn the experiments, I think it is necessary to include previous local-global methods, such as [1], as baselines. The empirical results look reasonable to me. It is expected that combining local and global moves improves the sampling results on multimodal distributions. \n\n", "limitations": "There is no related discussion on limitations in the paper.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The motivation is clear and the paper is easy to follow.\n\n- As far as I understand, the proposed method is technically sound.\n\n- The authors provide both theoretical and empirical analysis to the proposed method.\n\nWeaknesses\n\n- It is unclear whether the methodology significantly differs from previous local-global MCMC work. Thus, the originality is unclear.\n\n- The empirical results do not include previous local-global MCMC methods as baselines, so it is unclear whether the empirical improvement is significant. \n\nMy main concern is the originality and significance. To me, the proposed method is very similar to [1] and the authors did not compare it with [1] in the experiments. If the authors can show significant differences and improvements of the proposed method over the previous work in the rebuttal, I'm happy to increase the score.\n\n[1] Adaptive Monte Carlo augmented with normalizing flows", "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": "D5J6QTP2dt", "reviewer": "Reviewer_PqJ7", "summary": "This paper addresses MCMC sampling from unnormalized probability distributions. The main idea here is to combine sampling importance resampling using a global proposal with an interleaved local update -- a local MCMC transition kernel (such as MALA or HMC) with a metropolis correction. The authors argue that this simple approach effectively combines the best of both worlds -- faster mixing between modes (from the global proposal) and better local exploitation of modes (from the local kernel). The authors provide theory and empirical results which back up this claim. A key theoretical result is that the proposed method is geometrically ergodic even if the importance weights are unbounded (assuming properties of the local kernel which hold for most sensible choices). This is in contrast to i-SIR which requires bounded importance weights. Thus the approach retains the nice mixing properties of i-SIR while inheriting some convergences guarantees from the local methods. \n\nThe authors also propose an adaptive variant of the method where the global proposal is a normalizing flow which is tuned online using the outputs of the sampler. Modifying the proposal online can break ergodicity but the authors present sufficient conditions to guarantee it (basically just ensure that the flow converges).\n\nThe authors present some nice toy results to help visualize the performance of the approach compared to some obvious baselines (pure-global and pure-local MCMC). They then present results on some standard benchmark distributions of increasing dimension and show that their method outperforms most baselines except for NUTs (only outperformed in high dimensions). They then sample from high-dimensional EBM-GANs and show similar improvements. \n", "questions": "Most of my questions relate to the adaptive variant of the method. First, I am curious how important it is to train using the mixture of forward and reverse kl. Do we need both? I know you note (correctly) that reverse kl can suffer from mode-dropping, but it can also be made to work in many scenarios if done carefully. It would be great to have some sort of ablation on this? Maybe compare reverse only, forward only, and the mixture. I would not be surprised if the mixture performs better but it would be useful to back up the choice used here.\n\nNext, I am curious how important the initialization of the proposal distribution is to the performance of the method. In my experience, reverse kl can be made to work if the proposal is initialized properly. Does the mixture save us from that? It might also be nice to see how the approach performs when we use a good init (distribution with the right scale) to a bad init (distribution with scale too small or too large). It would also be nice to discuss a practical initialization procedure such as: start with a wide proposal, run K steps of HMC and take the mean/std of the resulting samples and use that to parameterize the initial proposal. It would be very cool to see if the method is relatively robust to these choices. ", "limitations": "I feel the limitations of the method are clear from reading the work. There is no specific limitations section (might be nice to add), but I do not think it is absolutely necessary. ", "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\nI enjoyed reading this work. This method is very simple (a good thing!) and once you hear it, it makes perfect sense. Its always great to see simple, intuitive ideas that appear to perform well. In my experience, it is methods like these that end up having the most impact (which is what we should all be trying to achieve). While the method is relatively simple, it is not obvious where and when it should outperform related methods. The theory shown here definitely makes that clear and does so in a way that is easily understandable and not over-cluttered with unnecessary math that would obfuscate the presentation of the method and the results. \n\nThe results are presented nicely. I like the progression from toy visualizations, to challenging standard benchmarks, to real-world deep learning models. I am convinced that the approach scales to high-dimensional problems and still performs well.\n\nWeaknesses: \n\nI do not have too many large critiques for the work but I do have a few questions (which will be expanded on in the next section). \n\nI do feel there is some related work that has not been addressed (not my work I swear!). There has been a fair bit of work in the EBM space using a mix of local MCMC and global proposals ([3] is a good starting point but this family of methods has been explored quite thoroughly). Most of this has been focused on improving MCMC used to train energy-based models. To my knowledge, these methods have not been given the same theoretical treatment presented here, so it might be nice to compare these methods to your work and discuss where your theory could (or could not) be applied.\n\nI feel the experimental results in the image generation section could be improved. I know it can be difficult to come up with quantitative measures of sampler performance for image data but some decent proxies do exist. I am not super-convinced by looking at energy values alone. Some measure which could compare likelihood and entropy would be nice. While not a perfect metric, FID could be used on the CIFAR experiments to give a solid proxy for this. Another idea would be to use a tractable model as a target. For example, you could train a normalizing flow on MNIST or CIFAR and sample from the flow, treating it as unnormalized. Then you could compare likelihood histograms between the MCMC samples and actual samples from the model. This has been done in other work dealing with unnormalized models [1, 2].\n\nLike I said, I enjoyed this work, but some further large-scale experiments like this would greatly improve its experimental section. \n\n[1] https://arxiv.org/pdf/1905.07088.pdf\n[2] https://arxiv.org/abs/2010.04230.pdf\n[3] http://www.stat.ucla.edu/~ywu/CoopNets/doc/CoopNets_AAAI.pdf", "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