Nonlinear MCMC for Bayesian Machine Learning
Authors: James Vuckovic
Venue: NeurIPS 2022 Accept (2022)
Keywords: bayesian machine learning
markov chain monte carlo

Abstract: We explore the application of a nonlinear MCMC technique first introduced in [1] to problems in Bayesian machine learning. We provide a convergence guarantee in total variation that uses novel results for long-time convergence and large-particle (``propagation of chaos'') convergence. We apply this nonlinear MCMC technique to sampling problems including a Bayesian neural network on CIFAR10.

Nonlinear MCMC for Bayesian Machine Learning
James Vuckovic
sames@@amesvuucooviii
Abstract
We explore the application of a nonlinear MCMC technique first introduced in [1] problems in Bayesian machine learning. We provide convergence guarantee total variation that uses novel results for long-time convergence and large-particle ("propagation of chaos") convergence. We apply this nonlinear MCMC technique to sampling problems including Bayesian neural network on CIFAR10.
Introduction
Characterizing uncertainty fundamental problem in machine learning. It often desirable for machine learning model to provide a prediction and a measure of how "certain" the model is about that prediction. Having access robust measure of uncertainty becomes particularly important in real-world, high risk scenarios such as self-driving cars [2-4], medical diagnosis [5, 6]. and classifying harmful text [7].
However, despite the need for uncertainty in machine learning predictions, it is well known that traditional MI. training, i.e. based optimizing objective function, frequently does not provide robust uncertainty measures [8], yielding overconfident predictions for popular neural networks such ResNets [9]. An appealing alternative the traditional optimization paradigm for ML is the Bayesian probabilistic framework, due to its relatively simple formulation and extensive theoretical grounding: for example [10].
From the probabilistic perspective of machine learning [10]. one combines a prior P(0) over the parameter space 0 E @ and a likelihood of the data given model parameters P(D(0) using Bayes' rule to obtain a posterior over the parameters P() x P(()). The "traditional" approach in ma- chine learning is to optimize the posterior (or the likelihood) to obtain 6 arg max P(0 DD) and gen- erate predictions via P x, D) = P(y|æ, 8*). However, we adopt the Bayesian approach, the poste- rior characterizes the uncertainty about the parameters of the model (i.e. epistemic uncertainty). which can propagate to uncertainty about prediction by integration: P(y|æ, D) = Plylæ, #) P(0) DD. This paper studies the problem of how to approximate this integration with samples from PO)D))
1.1 Contributions
Our main contribution the novel analysis of modification of the general nonlinear Markov Chain Monte Carlo (MCMC) sampling method from [1] to obtain quantitative convergence guarantees in both the number of iterations and the number of samples.
We apply the general results from above to determine the convergence of two specific nonlinear MCMC samplers.
experiments, we compare these nonlinear MCMC samplers to their linear counterparts, and find that nonlinear MCMC provides additional flexibility in designing sampling algo- rithms with as good, or better, performance as the linear variety.
In Appendix C.2.4, we provide an experiment that demonstrates this effect.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.2 Background
Bayesian ML & MCMC. In Bayesian machine learning, the "computationally difficult" step is integration since the integral f P(ylæ, P) D) is not analytically solvable except for rare cases. In practice, one typically uses Monte Carlo approximation such
i P(ulx,0)P(000
E P(yl,,0', where O sid P(ODD)
where the expected error in this approximation is well known to converge to zero like D(1/VN by the Central Limit Theorem (CLT). There are various approaches sampling from P(O D), but Markov chain Monte Carlo (MCMC) is perhaps the most widely used. The basic idea of MCMC use Markov transition kernel T with stationary measure P)) to simulate a Markov chain 0 Bn+1 ~ (0 )) that converges rapidly to P() In this case, we can estimate
N
N
/ P(ulz, P) =
1
Σ
P
Plylz, 0 R
N
1=1
where Thxm is some large number of simulation steps and {0r ) n=o are independent Markov chains governed by T.
The basic problem is then to design an efficient transition kernel T. There is a vast body of literature studying various choices of Ti some well known choices are the Metropolis-Hasting algorithm [11, 12]. the Gibbs sampler [13], the Langevin algorithm [14-17], detropolis-Adjuste Langevin [18, 19), and Hamiltonian Monte Carlo [20-24].
However, there are various challenges in Bayesian ML that make applying these samplers difficult in practice. One challenge is that the posterior P() can be highly multimodal [25, 26], which makes it difficult to ensure that the Markov chain O,, explores all modes of the target distribution. One can combat this issue by employing auxiliary samplers that explore more "tractable" variation of P(O[D) [27, 28). Other methods that empirically improve posterior sampling quality include tempering [29-32], RMSProp-styLe preconditioning [33], or adaptive MCMC algorithms [34, 35] such as the popular No U-Turn Sampler [36].
Nonlinear MCMC. Another class of powerful MCMC algorithms, which is less-studied in the context of Bayesian ML, arises from allowing the transition kernel T to depend on the distribution of the Markov chain as in 0x+1 TDistribution(e.) (6,, +). This approach gives rise to so-called nonlinear MCMC since (0,) is no longer true Markov chain. Nonlinear Markov theory is a rich area of research [37-42] and has strong connections to nonlinear filtering problems [43, 44], sequential
Monte Carlo [45, 46], and nonlinear Feynman-Ka models [47]. One can replace Distribution((.).
which is often intractable. with an empirical estimate Distribution(9.) s 2/4 Σ Σi= 8ø: to obtain interacting particle MCMC (iMCMC, or iPMCMC) methods; see for example [48, 49, 1,, 50, 51].
Our view is that nonlinear MCMC offers some appealing features that traditional linear MCMC lacks. One such feature the ability to leverage global information about the state space θ contained in improve exploration, central issue in Bayesian MI. Another feature is the
Distribution (f'.) increased flexibility of nonlinear MCMC algorithms, which can be leveraged to correct biases that are introduced by other design decisions in MCMC for Bayesian ML such as tempering. These features will be explored empirically in Section 4.
However, the theoretical analysis of nonlinear Markov MCMC presents an added difficulty in that the particles (Ø...... 0N } of an interacting particle system are now statistically dependent. This means that. in addition to studying the long-time behaviour which is classical in MCMC [52, 53], one must study the aargepaaticlle behaviour separately to obtain Monte Carlo estimates since the CLT does not apply. One such large- particle behaviour is the propagation of chaos [41], which is the tendency for groups of interacting particles to become independent as the number of particles, N, increases; see [41]. We will need both of these elements long-time time convergence and propagation of chaos to properly characterize the convergence of nonlinear MCMC.
Other Sampling Methods. Finally, let us mention that MCMC is certainly not the only way to obtain Monte Carlo sample estimates in Bayesian MI: some popular examples include MC dropout [8]. black-box variational inference [54], and normalizing flows [55,

---

1.3
Common Notation
Let P(RR) be the set of probability measures on the measurable space (R" ((R)) For p e P(R4) and (RR))) = ( Ra R I bounded), we will denote p(f) == fdu. If K: Rd (RR) + [0, 1] is Markov kernel then we will denote K Kf(x)
f(v) dy) and uK(dy) == u(dx) K (Ir dy). Finally, for == fy (vt....,,'' R2, we will denote the empirical measure of 7 as (T) = + Eim by E P(R4).
2 Nonlinear MCMC
In this section, outline the family of MCMC algorithms that will be studied in rest of the work. We will use general notation for simplicity but this difference is merely cosmetic; the "target distribution" in this section corresponds directly to P(O)D) from the previous section.
2.1 Nonlinear Jump Interaction Markov Kernels
To specify a MCMC algorithm, we must specify the Markov transition kernel. The family of nonlinear Markov kernels that will be studying was introduced in [1] and is mixture of linear kernel, denoted K, and a nonlinear jump-interaction kernel indexed by probability measure 77, denoted Jn- to obtain
(x, dy) == -1-2) (1 dy) + EJ,, (x,dy) dy)
(1)
where e|0, 1[ is the mixture hyperparameter. The Markov kernel K, will be the main object of interest throughout this paper. We will give specific examples of J, in Section 2.2, which were also introduced in [1]. Despite building the constructions of [1], this work proceeds in some different substantially directions; see Appendix A.1 for more details.
Mean Field System. Now show how the kernel K, be used to construct Markov chain. Following [1], we use an auxiliary Markov chain {Y,} with transition kernel Q on the same state space as K, (i.e. Rd) to obtain the nonlinear Markov chain {(Y,, ) defined by
Yat1 Q(Yn,
Mh+1 Distributtonn(A4a))
Yo njo, Xo 1A
Xa41 ~ Knnia (X.,,
where yo: ?u P(RR) are the initial distributions and ~ denotes "sample from". One should interpret this as a sequence of steps where first we sample the auxiliary state Y,+1 from Q, then we obtain the distribution of Yn+1 denoted 7,+1, and use this distribution to index the primary kernel K 7=+: and obtain a sample X,+1- We sample X,+1 with probability (1 1-- E) from the linear kernel K, and with probability it will "jump" according Jn..1 (Xn, )). Because the Markov dynamics depend on Distribution Y.). we call this a "mean field system".
Interacting Particle System. One issue with the mean field system (2) is the fact that computing Distribution(Y,. ) is generally impossible except in special cases. Hence, to get a viable simulation algorithm, must upproximate Distribution (Y,). and we do this by replacing Distribution(Y.) with its empirical measure estimated from set of N particles Y,, {Y,) ...... Y,N } as follows:
Y ~ Q(Y: 12
N = m(nntt)
Yi
rid
~
X
sid
po. i == 1,..., N.
(3)
X Kg (X
2.2 Application to MCMC
Now we detail how to apply Ky, and the Markov chains (2) and (3) MCMC. In particular, we must understand how to choose Q, K, Jn such that K,, will be invariant w.r.t. a target distribution æ.
i.e. K K(x, is probability measure Ve E R8 and K K(,, A) is measurable A.A B(R)
3

---

As is usually the case in probabilistic inference problems, we will assumee that the target distribution is known only up to a normalizing constant and that has a density, also denoted æ. We also make the simplifying assumption that Q has an invariant measure 1)* (also with density denoted n1") i.e. q = = This is not burdensome; in practice we can, and will, obtain Q from a linear MCMC algorithm for some choice of ry" In fact, being able to choose 1f' is powerful design parameter of our methods as we will see in Section 4. We will also assume that the linear kernel K is -iinvariant, i.c. rk =
To see how we can ensure that π is ii,-inraiann,, consider the fact that we will design Q s.t. aa := Distribution(Y,) converges to 77". This means we will eventually be sampling from the kernel , and we already have π-- --invariance of K. Therefore, if we arrange for Jn- to be r-invariant, π will be invariant for K₁' since
T (1 E) + J. (1 (1-68 E) EXT
Intuitively, if the auxiliary chain converges to a steady state and the jumps in that steady state preserve (and K preserves T), then so will K,,, Now the remaining task is to design nonlinear interaction kernels Jn that will yield good performance; we detail two choices below.
Boltzmann-Gibbs Interaction. The first choice of Jn we will investigate, from [1], relies on the Boltzmann- Gibbs transformation [47], which we now explain. Let G : R -j00, oo be a potential function; then the Boltzmann Gibbss (BG) transformation is a nonlinear mapping Ve P(RR) + P(RR) defined by
Va())(dx) = G(z) su(dz) or equivalently p²G)
/ f(=))c(W(d))= := 5(x) G( ((G) u(dz)
for any f E (R(RR) and whenever (()) j O. This transformation has many interesting properties and been extensively studied in [47] and related works.
To use the BG transformation in MCMC, we will assume that the densities x and 1y* are positive" and make the choice that G(x) will be the function
(T))
G(z) = (1)
(4)
With this choice, we get an interaction kernel J (,, (d)) We can easily see that TTx))
17 (G)) - f dn
G(z)
dm and (dz)) 17" (G)
(dx)
(x) nj (dz) x(dz),
Le. G is the multiplicative "change of measure" from 17" to æ. Hence the first nonlinear Markoy kernel we will investigate is
BG (I, dy) = (1 <x, dy) + + From the remarks above, is clear that is K.,- -invariat..
(5)
Accept-Reject Interaction. The second choice of jump interaction we will study, also introduced in [1], is type of accept-reject interaction related to the Metropolis- Netropolis-Hastings algorithm. For the same choice of potential function G in (4), we can define the acceptance ratio
G(y) A G(x)
x (x) and the quantity A,(x) := a(x, ()(,))))()))
a(x, v) = 1
1y" (1)
for 7/ E P(Rd). Hence we can define the accept-reject interaction kernel as* R dy) a(x, v)n(dy)) + (1- (,,
We can interpret this jump interaction as: starting in state x, we jump to a new state distributed according to 7/dyy) with probability a<x, y) (i.e. accept the proposed jump) and remain the in current state with probability - A²(x) (i.e. reject the proposed jump). This a form of "adaptive Metropolis-Hastiee
in which the proposal distribution evolves over time the distribution of the auxiliary Markov chain. Hence we obtain the accept-reject nonlinear jump interaction kernel
7 KAAR| (I,, dy) == (1 - e)K (a, dy) + =fa(a, y)r(dy) + (1 - 6, (dy)).
(6)
We note that æ is also J A invariant; see Proposition in Appendix G for simple calculation.
this can be relaxed to क & l and μ & π Given f E B).)). we can also write this f(x) f(f()) [=))a(( y))(d))) f(x)

---

Simulation. Let us note briefly that using both Ka and K,R in (3) produce interacting particle systems that can, and will, be simulated. The simulation is relatively straightforward, see Appendix for pseudocode implementing the nonlinear MCMC algorithms we have now constructed.
3 Convergence Analysis
We will now study whether the nonlinear MCMC algorithms based on K,, from Section 2- i.e., the interacting particle system (3) with the restrictions on K, Q, J, from Section 2.2 - will actually converge to the target distribution и. In other words, we would like to estimate || - 7| for some suitable notion of distance on P(RR). where fe := Distribution( (X,,) is the distribution a single particle (it doesn't I matter which particle the X; are exchangeable).
The nonlinear nature of K2 makes this analysis more difficult than of a linear MCMC method. We break the problem into two parts: one studying the convergence of the mean-field system (2) as the number steps n + xc, and one studying the convergence the interacting particle system (3) to the mean field system as the number of particles N - oc. This will allow us to apply the triangle inequality as follows:
<
Mm
large-particle convergence
long-time convergence
where Hn, := Distribution(X.) is the distribution of the mean-field system. Crucially, our analysis of the large-particle limit is uniform in the number of steps which will allow us to establish bounds above that hold as n + co. The actual result is contained in Theorem 1.
While our analysis does not rely on heavy mathematical machinery, to state the full set of conditions and results for long-time and large-particle convergence each of which is substantial result in its own right - would occupy too much space in the main text. Instead, we will state the main result in Theorem
which essentially corollary of the long-time and large-particle analyses Theorems 2 and 3 in Appendices E and FF respectively, and below we will sketch the general arguments used in those appendices. The proofs of the main results are in Appendix F.2. Note that our analysis, and the results we obtain, are novel and not found in [1]; see Appendix D for an elaboration.
The following result is stated in terms of the total variation metric, defined here for μ. E P(R") as || - ulle> sup S1 Iu(f)
v(f) where
lce is the sup-norm B, (R.)..
Theorem 1. [Convergence of Nonlinear MCMCJ Under suitable conditions on K₂, and Q, there exist fixed constants C1, C2, C3 > 0, function R [0, oo| [1, oof, and p > 0 s.t.
I Tlleo S C1 N
R(1/N) + C2p" + Canp".
Let us make couple of remarks:
This result shows that, to control the approximation error || - -lllee it does not necessarily suffice to run the MCMC algorithm for a large number of steps n, since - oc but N < oc then our bound on ||,," x|| A O. However, this approximation cannot lead to arbitrarily bad results: Theorem provides quantitative upper bound on how much the MCMC algorithm can be biased. This behaviour is supported empirically: in Figure 5 of Appendix C.1.4 1.4 we provide a clear illustration of how changing N significantly affects the bias of our nonlinear MCMC methods while having no effect on the bias of linear MCMC, as expected.
This result uses total variation, which is a strong metric that represents a worst-case over all bounded functions / (up to rescaling by ()]))))) It is entirely possible that, for many choices of practical f, the approximation will be better as we will see empirically.
The constant is, roughly speaking, the slower of the rate of convergence for Q and for K. Hence if K, Q are chosen to be efficient samplers with fast convergence, this will result in p < and hence y will also converge quickly.
5

---

In our specific samplers K and K KAR, we will see in Appendix G that R is a monotoni-
cally increasing function that is lower-bounded by 1. Hence, as N co, N R xv) 0 as expected.
corollary of Theorem I is that that we regain a Monte Carlo estimate for the interacting particle system. This result is essentially due to [41] Theorem 2.2.
Corollary 1. [Adapted from [41], Theorem 2.2/ Suppose that Theorem I applies to Ky. Let
Xn = { XN be the interacting particle system from (3). Then for every n E -N and E (R() we have
1 N N
-
lim N -00
This corollary directly relates to the application of Bayesian ML we are interested in, where we would have f(0) 2( 0).
3.1 Long-Time Bounds
There are two main ingredients in the general result on long-time convergence: ergodicity of K and Q, and Lipschitz, regularity of the interaction kernel + Jn. These, along with other technical conditions, produce an estimate of the form || - =|I C2p" + Cznp" where + is a weighted total variation norm. The full statement is in Theorem of Appendix E.
Ergodicity of K and Q. A fundamental requirement of our results is that the linear building blocks of K,, must converge to their respective stationary measures in an appropriate metric. This type of result is now standard in the Markov chain literature, and we use a result from [57] for K and result from [1] for Q. The former is actually able to ensure that K a contraction on P(Rd) w.r.t. a suitable weighted total variation; we use this feature repeatedly in our analysis.
Lipschitz Regularity of J,. We also need that 7) J, is Lipschitz-contimuuus w.r.t. weighted total variation norm on Markov kernels (the Lipschitz constant does not have to be < 1). This regularity used to translate the convergence of Th - -/ (as guaranteed by the ergodicity of Q) into convergence of Jn + Jnp with the Lipschitz estimate I| - Jn & I| 1/"Il. In Appendix G, we verify this analytically for JBG and J,AR, see Lemma 5 and [1] Proposition 5.3.
3.2 Large-Particle Bounds
To study the interacting particles [X,,,... X3} c {X,.... .x.....,. x =: X,, from (3) is to being i.i.d. according to the mean-fiell measure pa- This analysis was pioneered in [41] under the name "propagation of chaos" and formalizes the intuition that, as N + co, the influence of any individual particle + 0.
behaviour, we would like to measure how close subset of q E (1...., N}
To state this more precisely, first note that if we had random variables Z iid 17 E P(R") then the joint distribution of Z : -2²,.. ........ za would be s78, Hence, as N + 3o for the interacting particles X, time n, we expect the distribution of [X....., X9). denoted na.N, to the distribution of i.i.d. mean field particles from (2), denoted p,9 In other words, we expect [| - 1 Ilev
get closer
N + co. The full statement of this result is Theorem 3 of Appendix F.
The main condition in our propagation of chaos result another type of regularity for - J, which basically requires that, if one approximates distribution E P(Rd) by its empirical measure m(Y) where Y : (YI,.... Y and Y rid n, then JnxY) + J,, as N + oc. More precisely, there should be function R: : [0, oo| [1, oof, which is ideally nondecreasing, s.t.
E m(X) f f(a)) d2 R((22/N)) Vz e Rd and f (R with "oscillations" osc(f) s 1. N
The expectation taken over 17 and "oscillations" are defined precisely in Appendix D. This inequality is essentially total variation regularity since we can alternately write || Vllev sup(lu(f) - r(f)l f B,(R)), osc(f) < 1} [47].

---

3.3 Analysis of Specific Interaction Kernels
The main result Theorem is in terms of conditions on a general K, (i.e. general choices of K, Q, Jn). To apply this result to the samplers in Section 2, we must establish if these conditions hold for K BG and K KAR. Fortunately this can be done analytically: in Appendix G, we present conditions under which the Lipschitz regularity (see Lemma and [1] Proposition 5.3) and large-particle regularity (see Corollaries 3 and 5) hold. These results, particularly for KBG are interesting and rely on novel techniques for controlling the various guantities, sometimes improving over previous methods. Due to space constraints, the results for K and KAR are in Corollaries 2 and 4 from Appendix G.
4 Experiments
In this section, detail two experiments designed to explore how might apply the nonlinear MCMC methods developed in the previous sections to Bayesian machine lcarning." Let us state explicitly that our aim is not to achieve state-of-the-art with these experiments, nor do we claim that this method will necessarily lead to state-of-the-ar results on particular task. Rather, the aims of these experiments are: to demonstrate that nonlinear MCMC can be applied successfully to lcage-scale problems; to compare linear vs nonlinear methods to understand what benefits and drawbacks nonlinear MCMC offers compared linear MCMC in practice; and to develop some recipes for choosing the various hyperparameters and samplers that determine a nonlinear MCMC method.
4.1 Two-Dimeesional Toy Experiments
First, we use toy setting of two-dimensional distributions to compare the relative benefits of linear and nonlinear MCMC. A benefit of this simple setting is that the multimodal toy distributions can be exactly sampled. This gives us the opportunity to quantify the quality of our samples via an unbiased estimator of the Maximum Mean Discrepancy (MMD) metric on P ((R)) [58]. This approach stands in contrast to many previous works, which use simplistic distributions (e.g. Gaussians) with analytically tractable statistics measure quality. See Appendix C.1 for an overview of our methodology.
Setup. Our setup will compare the Metropolis Adjusted Langevin Algorithm (MALA) [18] (see Appendix for an overview of MALA) with the nonlinear BG and AR samplers using MALA for the kernels K, Q in our nonlinear setup from Section 2. This will allow us to examine the effects of the nonlinearity KAR and K, while controlling for the type of sampler used and its hyperparameters.
g
The main difference between the lincar and nonlinear algorithms, aside from the interaction itself, is the extra "design knob" to control in the form of the choice of the auxiliary density nn" Below, show how one can use 17" to incorporate additional insight to guide the sampling, such as regions of the state space explore. In our experiments, we choose 17 to be centered, 2-dimensional Gaussian with a large variance (E = 4/2 for the circular MoG and two-rings densities, and Σ = 20/2 for the grid MoG). This conveys "coarse-gre -arrined- information of roughly where the support of the target density is located - in this case, neighbourhood of (0, 0). See Table 2 in Appendix C. for a full account of our experimental settings.
Results. From Figure 1, we see that having a simple auxiliary density with good coverage of the support of the target distribution is quite helpful. In all three examples, one both of the nonlinear samplers outperformed the equivalent linear sampler in the empirical MMD metric. For the two most challenging densities, the "two rings" and "grid MoG" distributions, the improved exploration is particularly evident. We also include an analysis of the runtime of the algorithms in Appendix C.1.3.
Comparison With [1]. We also compared the performance of our methods with those of [1] in this two-dimensional toy setting. See Appendix 1.4 for an overview of the results; they support all of the theoretical considerations and design principles we have introduced in this paper.
Thee code used in our experiments can be found at https: thub. com/ amesvuc/ nonlinear mcme- paper. See also Appendix A for discussion of the implementation details.
7

---

Port Bull
1.6--
0200
Target Density
Ground Truth
Linear (MALA)
Nonlinear (AR)
Nonlinear (BG)
Figure 1: Visualizations of the 2d experiment. The top row shows the empirical MMD-squared plotted over number of sampled steps, where the shaded region independent runs. The bottom three rows show histograms for the N = 2000 samples of the Circular Mixture Gaussians (MoG) density [59], the Two Rings density [59], and the Grid Mixture of Gaussians density [60] respectively.
standard deviation with
4.2
CIFAR10
4.2.1
Setup
To examine the properties of the nonlinear sampler outside of a toy setting, we have also implemented
a Bayesian neural network on the CIFAR 10 dataset. We use a likelihood Plylæ, 0) parameterized by
ResNet- 18 convolutional neural network [61] and a Gaussian prior P(0) on the parameters of this neural network which are combined to form posterior P(0) (rain) x P(0) (I P(y (x,, f).
The goal is to sample 8² 1.....A N from this posterior. See Table Appendix C.2 for full account of the experimental settings.
To deal with the fact that this sampling problem is very high-dimensional (d ~ 11M) and |Driin is large (fD = 60, 000) we use a variety of techniques:
1. We sample minibatches D of size 256 to obtain the surrogate target density P() [17]. 2. We use an RMSProp-like "preconditioned" Langevin algorithm, called RMS-Langevin RMS-ULA, in [33] for the auxiliary sampler Q; see Appendix B for details on this sampler. As shown in [33], this sampler is biased.
3. We use tempering, wherein we aim to sample from π small number. This substantially improves mixing for hard-to-sample distributions such as P(t)Dmmin) at the cost of bias since we are no longer sampling from the true posterior [32].
P( 1/r where 7 is
Using our nonlinear algorithm presents novel opportunity to correct the bias introduced by tempering. For our experiments, we pick 1y* x P and π = chain Y, explores tempered version of the target, whereas the target chain X,, (in theory) explores the true target distribution. This is novel strategy that is made possible by being able to select n almost independently of the target We study the case when is tempered well.
This means that the auxiliary

---

For our experiments, we use the RMS- AMS-Langevin sampler as the baseline, and we also use it for the auxiliary sampler Q. For the target sampler, it not possible use the RMS-Langevin algorithm because the smoothed square-gradient estimate is incompatible with the discontinuities (i.e. jumps) introduced by the nonlinear interaction. Instead, for the linear sampler K we use the unadjusted Langevin algorithm, ULA, [16] (see Appendix B). We investigate both test accuracy and calibration error [9] to assess performance.
Table I: Results for CIFARIO experiments. + represents I standard deviation on 5 random seeds. The tempered results are using т = 10- See Appendix C.2 for an overview of expected calibration error. We also compute the maximum calibration error in Appendix C.2. All Expected Calibration Error numbers are multiplied by 102 in this table.
Test Accuracy (1)
Expected Calibration Error (4)
Algorithm
Non- Tempeeee
Tempered
Non- non-Tempered
Tempered
Linear
85.01
85.01+0.19
0.24 0.24
0.26
Nonlinear (BG)
84.28
84. 84.7440.08
0.14
0.16=0.03
Nonlinear (AR)
Diverged
84.67 +0.23
Diverged
0.15=0.05
3.8
3.52
0.78
3.7
0.0
362
025
028
Provo Thrach
Figure 2: Evaluation of test accuracy during sampling for CIFARIO. The shaded areas represent +1 standard deviation for 5 random seeds. For readability, we omit the AR interaction curve on the non-tempered result since it diverged and it distorts the scale of the plot. For completeness, all the curves for the non-tempered case are plotted in Appendix C.2.2, Figure 6.
4.2.2 Results
Linear vs Nonlinear. From Table 1, we see that the linear (RMS- sampler has slightly higher, but comparable test accuracy to the nonlinear samplers. This is likely because RMS-Langevin algorithm has better stability around the regions of high probability due to its adaptive stepsize scaling. However, from Figure 2, we see that for both the tempered and non-tempered cases, the nonlinear interaction appears to benefit during early exploration. This is expected and desired property of these nonlinear samplers, which incorporate global information about the sampler state (in this case, the relative potential G of each auxiliary chain's 's state) and are able to emphasize those states with higher probability. However, the linear method is able to eventually explore the relevant regions of the state space, and the difference disappears. See Appendix C.2.5 for comparison linear vs nonlinea performance scaled by the number of gradient evaluations.
Tempering Vs Non- -ompeenne The linear MCMC sampler is always tempered in experiments so there should not be any statistically significant difference in the linear case. For the nonlinear sampler, the tempered version has slightly higher accuracy; this trend is also observed in [32]. On the other hand, the calibration errors are the same for both tempered and non-tempered variants. This is somewhat surprising. given the aggressive tempering used, and one would expect that this reduces the variance of the posterior estimate." This observation can perhaps be explained by the fact that we are using N 10 samples which may not be enough to accurately change the tempered auxiliary distribution 17* into the non-tempered primary distribution π in the jump interaction.
As 0, this 0 ~ ((0 L/T converges to the maximum posteriori estimate with zero variance.

---

Calibration. Considering the expected calibration enror (ECE) [9], in Table I we see that the nonlinear method has statistically significantly lower ECE (p < 0.05) compared to the linear method. We hypothesize that this is due to tension between the RMS scaling of the gradient which improves the efficiency of each MCMC step but at the cost of bias, which may be measurable in the form of calibration error. The Langevin algorithm is also biased, but is generally known to have good convergence properties [16] and much less is known about the RMS- RMS-Langevin variant. By using our nonlinear setup, we are able to aggressively explore the auxiliary distribution without sacrificing calibration on the target distribution.
5 Conclusion
In this paper, we have studied the theoretical and empirical properties of nonlinear MCMC methods. We have obtained powerful theoretical results to characterize the convergence of our MCMC methods, and we have applied these methods to Bayesian neural networks. The results BNNs are comparable to, but not better than, the linear methods we studied. We hypothesize that this is because more investigation into choosing the best auxiliary density 1j" is required; our choice is simplistic and may not be optimal. This hypothesis is supported by our toy experiments, which show significant improvement when 17" is able to incorporate some additional insight into the problem. How to do this in high dimensions is an exciting direction for future research.
Broader Impact. There are benefits and drawbacks to the nonlinear MCMC methods we describe. The benefits are mainly that properly accounting for uncertainty in machine learning will lead to better real-world outcomes for high-value scenarios such as self-driving cars or medical imaging. The drawbacks are that MCMC methods require (NN) storage and computations relative to the O(1) for deterministic methods; in fact, our nonlinear method would require 2N resources compared with N for linear method (see also Appendices C.1.3 and C.2.5). If our algorithms were applied to large swath of ML "as is", this would mean a substantial increase in the energy consumption required for experimentation and deployment, worsening already substantial issue in the field.
References
[1] Christophe Andrieu, Ajay Jasra, Arnaud Doucet, and Pierre Del Moral. On nonlinear Markov chain Monte Carlo. Bernoulli, 17(3):987 1014, 2011. doi: 10.3150/10-BEJ307. URL
https://doi. org/10. 3150/10-
[2] Rhiannon Michelmore, Marta Kwiatkowska, and Yarin Gal. Evaluating uncertainty quantifica- tion in end-to-end autonomous driving control. arXiv preprint /0/1v/////.0088 2018.
[3] Sina Shafaei, Stefan Kugele, Mohd Hafeez Osman, and Alois Knoll. Uncertainty in machine learning: A safety perspective on autonomous driving. In International Conference Computer Safety, Reliability, and Security, pages 458-464. Springer, 2018
[4] Liuhui Ding, Dachuan Li, Bowen Liu, Wenxing Lan, Bing Bai, Qi Hao, Weipeng Cao, and Ke Pei. Capture uncertainties in deep neural networks for safe operation of autonomous driving vehicles. In 2021 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & wtwe://oosSScciaooo///o/a//aeeae
Networking
pages 826-835. IEEE, 2021.
[5] Benjamin Kompa, Jasper Snoek, and Andrew L Beam. Second opinion needed: communicating uncertainty in medical machine learning. NPJ Digital Medicine. 4(1):166, 2021.
[6] Roohallah Alizadehsani, Mohamad Roshanzamir, Sadiq Hussain, Abbas Khosravi, Afsanch Koohestani, Mohammad Hossein Zangooei, Moloud Abdar, Adham Beykikhoshk, Afshin Shoeibi. Assef Zare, et al. Handling of uncertainty in medical data using machine learning and probability theory techniques: A review of 30 years (1991-2020). Annals of Operations Research, pages 1-42, 2021.
[7] Jianfeng He, Xuchao Zhang, Shuo Lei, Zhiqian Chen, Fanglan Chen, Abdulaziz Alhamadani, Bei Xiao, and Chang Tien Lu. Towards more accurate uncertainty estimation in text classification. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 8362-8372, 2020.
[8] Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In International Conference on Machine Learning, pages
1050-1059. PMLR, 2016.
10

---

Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. International Conference on Machine Learning, pages 1321-1330. PMLR, 2017. [10] K.P. Murphy. Machine Learning: A Probabilistic Perspective. Adaptive Computation and Machine Learning series. MIT Press, 2012. ISBN 978026201800 URL https://books: google. ca//booksPid-222AAAAADA
[9]
[11] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21 (6): 1087=109, 1953.
[12] W Keith Hastings. Monte Carlo sampling methods using Markov chains and their applications.
1970.
[13] Stuart Geman and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, (6):
721-741, 1984.
[14] Donald L. Ermak. A computer simulation of charged particles in solution. i. technique and equilibrium properties. The Journal of Chemical Physics, (111)94489-449,, 1975. doi: 10.1063/1 430300. URI http:: //doi. org/ 10. 1063/1 00666/1.430335 430300..
[15] Gareth O Roberts and Richard L Tweedie. Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, pages 341 341-363, 1996.
[16] Alain Durmus and Eric Moulines. High-dimensional Bayesian inference via the unadjusted Langevin algorithm. Bernoulli, 25(4A):2854-288)) 2882, 2019.
[17] Max Welling and Yee W Teh. Bayesian learning via stochastic gradient Langevin dynamics. In Proceedings of the 28th International Conference on Machine Learning, pages 681-688. Citeseer, 2011.
[18] Gareth O Roberts and Jeffrey S Rosenthal. Optimal scaling of discrete approximations to Langevin diffusions. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 60(1):255-268, 1998.
[19] Gareth O. Roberts and Richard L. Tweedie. Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, 2(4):341 - -363, 1996. doi: bj/1 178291 1835. URL https://doi. org/.
[20] Simon Duane, Anthony Kennedy, Brian Pendleton, and Dunean Roweth. Hybrid Monte Carlo. Physics letters B, 195(2):216-25) 1987.
[21] Michael Betancourt. A conceptual introduction to Hamiltonian Monte Carlo. arXiv preprint
17X1v:1001.02434 2017.
[22] Radford M. Neal. An improved acceptance procedure for the hybrid Monte Carlo algorithm.
Journal of Computational Physics, 111:194-203, 1992.
[23] R.M. Neal. Bayesian Learning for Neural Networks. Lecture Notes in Statistics. Springer New York, 2012. ISBN 9781461207450. URL https://booke borooks..oogla LHHrBBAAQBAJ.
google. ee ca/books? id=
[24] Mark Girolami and Ben Calderhead. Riemann manifold Langevin and Hamiltonian Monte Carlo methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 73
(2):123-214, 2011.
[25] Peter Müller and David Rios Insua Issues in Bayesian analysis of neural network models. Neural Computation, 10(3):749-770, 1998.
[26] Arya A Pourzanjani, Richard M Jiang, and Linda R Petzold. Improving the identifiability of neural networks for Bayesian inference. In NIPS Workshop on Bayesian Deep Learning. volume 4, page 31, 2017.
[27] David M. Higdon. Auxiliary variable methods for Markov chain Monte Carlo with applications. Journal of the American Statistical Association, 93(442):585-595, 1998. ISSN 1459. URL
http:/ httt:://wat //www/ www.wwssoor..........oo..oom.... jsstor org/ stable/2670111
[28] Raza Habib and David Barber. Auxiliary variational MCMC. In International Conference on Learning Representations, 2018
[29] Malcolm Sambridge. A Parallel Tempering algorithm for probabilistic sampling and multimodal
optimization. Geophysical Journal International, 196(1):357-374 10 2013. ISSN 0956-540X. doi: /0.10923gji//gg3332.. URL https: http///ooiioo// org/10. 1093/ /t////gg/gga..../
[30] Robert Swendsen and Jian-Sheng Wang. Replica Monte Carlo simulation of spin-glasses. Physical review letters, 57:2607-2609, 12 1986. doi: 101100PPhysReeLeett5....60

---

[31]
Rohitash Chandra, Konark Jain, Ratneel V Deo, and Sally Cripps. Saangevin-gradeenr parallel tempering for Bayesian neural learning. Neurocomputing, 359:315-326, 2019.
[32]
Florian Wenzel, Kevin Roth, Bastiaan Veeling, Jakub Swiatkowski, Linh Tran, Stephan Mandt, Jasper Snoek, Tim Salimans, Rodoiphe Jenatton, and Sebastian Nowozin. How good is the Bayes posterior in deep neural networks really? In International Conference on Machine Learning, pages 10248-10259 PMLR, 2020.
[33] Chunyuan Li, Changyou Chen, David Carlson, and Lawrence Carin. Preconditioned stochastic gradient Langevin dynamics for deep neural networks. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
[34] Christophe Andrieu and Éric Moulines. On the ergodicity properties of some adaptive MCMC algorithms. The Annals of Applied Probability, 16(3):1462-1500 2006.
[35] Christophe Andrieu and Johannes Thoms. tutorial on adaptive MCMC. Statistics and
computing, 3834)33, 2008.
[36] Matthew D) Hoffman, Andrew Gelman, et al. The no-u-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo. J. Mach. Learn. Res., 15(1):1993-1623, 2014.
[37] Henry P McKean Jr. A class of Markov processes associated with nonlinear parabolic equations. Proceedings of the National Academy of Sciences of the United States of America, 56(6):1907, 1966.
[38] Sylvie Méléard. Asymptotic behaviour of some interacting particle systems; mckean-vlasov and boltzmann models. In Probabilistic models for nonlinear partial differential equations, pages 42-95. Springer, 1996.
[39] José A Carrillo, Robert J McCann, and Cédric Villani. Kinetic equilibration rates for granular media and related equations: entropy dissipation and mass transportation estimates. Revista Matematica Iberoamericana, 19(3);971-1018 2003.
[40] Arnaud Guillin and Pierre Monmarché. Uniform long-time and propagation of chaos estimates for mean field kinetic particles in non-convex landscapes. Journal of Statisticul Physics, 185(2):
1-20, 2021.
[41] Alain-Sol Sznitman. Topics in propagation of chaos. In Ecole d' é'été de probabilités de Saint-
Flour XIX-1989, pages 165-251. Springer, 1991.
[42] OA Butkovsky. On ergodic properties of nonlinear Markov chains and stochastic McKean-
Vlasov equations. Theory of Probability & Its Applications, 5864)6661 2014.
[43] Pierre Del Moral. Nonlinear filtering: Interacting particle resolution. Comptes Rendus de I' l'Académie des Sciences-Seriee I-Mathematics, 325(6)6653-658 1997.
[44] Pierre Del Moral and Laurent Miclo. Asymptotic results for genetic algorithms with applications to nonlinear estimation. In Theoretical aspects of evolutionary computing, pages 439-493. Springer, 2001.
[45] Arnaud Doucet, Nando De Freitas, and Neil Gordon. An introduction to sequential Monte Carlo methods. In Sequential Monte Carlo methods in practice, pages 3-14. Springer, 2001.
[46] Pierre Del Moral, Arnaud Doucet, and Ajay Jasra. Sequential Monte Carlo samplers. Journal of the Royal Statistical Society: Series B (Statistical Methodoloyy), 68(3):41 11346,, 2006.
[47] P.D. Moral. Feynman- Formulae: Genealogical and Interacting Particle Systems with Applications. Probability and Its Applications. Springer New York, 2004. ISBN 9780387202686. URL https: .oogle. ca/ sa/bbooksidd-Bee -iddddiydd-d.iL....
[48] Christophe Andrieu, Arnaud Doucet, and Roman Holenstein. Particle Markov chain Monte Carlo methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 72 (3):269-342, 2010.
[49] Tom Rainforth, Christian Naesseth, Fredrik Lindsten, Brooks Paige, Jan- Willem Vandemeent, Arnaud Doucet, and Frank Wood. Interacting particle Markov chain Monte Carlo. In Interna- tional Conference on Machine Learning, pages 2616-2625. PMLR, 2016.
[50] Grégoire Clarté, Antoine Diez, and Jean Feydy. Collective proposal distributions for nonlinear MCMC samplers: Mean-field theory and fast implementation. arXiv preprint arXiv: 199.0088888
2019.
[51] Michael Arbel, Anna Korba, Adil Salim, and Arthur Gretton. Maximum mean discrepancy gradient flow. Advances in Neural Information Processing Systems, 32, 2019.
[52] Gareth Roberts and Jeffrey S Rosenthal General state space Markov chains and MCMC algorithms. Probability surveys, 1:20-71, 2004.
12

---

[53] Sean P Meyn and Richard L Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
[54] Rajesh Ranganath, Sean Gerrish, and David Blei. Black box variational inference. In Artificial intelligence and statistics, pages 814-822. PMLR, 2014.
[55] Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. In International conference on machine learning. pages 1530-1538. PMLR, 2015.
[56] George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. Journal of Machine Learning Research, 22(57):1 2021.
[57] Martin Hairer and Jonathan C Mattingly. Yet another look at Harris' ergodic theorem for Markov chains. In Seminar on Stochastic Analysis, Random Fields and Applications VI, pages
109-117. Springer, 2011.
[58] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander
Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):223-773 2012.
[59] Vincent Stimper, Bernhard Schölkopf, and José Miguel Hernández-Lobato Resampling base distributions of normalizing flows. In International Conference on Artificial Intelligence and Statistics, pages 4915--936. PMLR, 2022.
[60] Ruqi Zhang, Chunyuan Li, Jianyi Zhang, Changyou Chen, and Andrew Gordon Wilson. Cyclical stochastic gradient MCMC for Bayesian deep learning. In International Conference on Learning Representations, 2019.
[61] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[62] Michael K Pitt and Neil Shephard. Filtering via simulation: Auxiliary particle filters. Journal of the American statistical association, 94(446):590-599 1999.
[63] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Landerman-Milng and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL com/ joogle/jax.
http://gite
[64] Grigorios A Pavliotis. Stochastic processes and applications: diffusion processes, the Fokker-
Planck and Langevin equations, volume 60. Springer, 2014.
[65] Denis Talay and Luciano Tubaro. Expansion of the global error for numerical schemes solving stochastic differential equations. Stochastic analysis and applications, 8(4):483 1008833559,-0 1990. [66] T. Tieleman and G. Hinton. Lecture 6.5 -0s--mmpPPppp Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
[67] Chii-Ruey Hwang. Shu-Yin Hwang-Mas and Shuenn-Jyi Sheu. Accelerating diffusions. The Annals of Applied Probability, 1433-144344,, 2005.
[68] Andrew B Duncan, Tony Lelievre, and Grigorios A Pavliotis. Variance reduction using nonre- versible I Langevin samplers. Journal of statistical physics, 163(3):457-491, 2016.
[69] Alessandro Barp, Lancelot Da Costa, Guilherme França, Karl Friston, Mark Girolami, Michael I Jordan, and Grigorios A Pavliotis. Geometric methods for sampling, optimisation, inference and adaptive agents. arXiv preprint arXiv:2203. 10592, 2022.
[70] Joris Bierkens, Paul Fearnhead, and Gareth Roberts. The zig-7ag process and super-efficient sampling for Bayesian analysis of big data. The Annals of Statistics, 47(3): (2(3):1288-1322 -320,, 2019.
[71] George Deligiannidis, Alexandre Bouchard-Côté, and Arnaud Doucet. Exponential ergodicity of the bouncy partiele sampler. The Annals of Statisties, 47(3): 1287, 2019.
[72] Augustin Chevallier, Sam Power, Andi Q Wang, and Paul Fearnhead. PDMP Monte Carlo methods for piecewise-smooth densities. arXiv preprint arXiv:21 2021.
[73] Alain Durmus, Arnaud Guillin, and Pierre Monmarché. Piecewise deterministic Markov processes and their invariant measures. In Annales de I' l'Institut Henri Poincaré, Probabilités et Statistiques, volume 57, pages 1442-1475. Institut Henri Poincaré, 2021.
[74] Pierre Monmarché. High-dimensional MCMC with a standard splitting scheme for the under- damped Langevin diffusion. Electronic Journal of Statistics, 15(2):41174416 2021.
[75] Dimitris Bertsimas and John Tsitsiklis. Simulated annealing. Statistical science, 8(1):10-15,
1993.
13

---

[76] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images.
2009.
[77] Tom Hennigan, Trevor Cai, Tamara Norman, and Igor Babuschkin. Haiku: Sonnet for JAX,
2020. URL http: thgbbtb...u. cww/deeppeeeeeeeeeee homp/eepmind////e/ dm- haiku.
[78] Yuval Netzer, Tao Wang. Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
14


Reviews:
[{"review_id": "haMQu7_mzTK", "reviewer": "Reviewer_3nmg", "summary": " This paper builds on the nonlinear MCMC methods proposed in [1], and provides convergence guarantees of these nonlinear sampling techniques in terms of the number of iterations and the number of samples required.\n- Using these general convergence guarantees, the paper shows that this holds for two specific algorithms: Boltzmann-Gibbs interaction, and Accept-Reject Interaction.\n- The paper also reports some positive and \"negative\" results on 2D toy tasks, and on CIFAR10. On 2D tasks, the paper shows that if the invariant density $\\eta^*$ can incorporate further details about the problem, then nonlinear methods work really well. However, on CIFAR10 they perform as well as linear methods, but not better. \n\n[1] Christophe Andrieu, Ajay Jasra, Arnaud Doucet, and Pierre Del Moral. On nonlinear Markov\nchain Monte Carlo. Bernoulli,  17(3):987 – 1014,  2011.   doi:  10.3150/10-BEJ307.   URL\nhttps://doi.org/10.3150/10-BEJ307", "questions": "1.I'm quite curious to understand and decouple the interactions between linear vs nonlinear MCMC methods, and the approximations and minibatching required to sample in a high-dimensional space such as CIFAR10. I think it might be important to decouple these interactions, to see if it really is the nature of the invariant density $\\eta$ that results in similar performance to a linear MCMC scheme, or if it is one of the approximations and assumptions made in 4.2.1. Maybe the authors could consider a smaller subset of CIFAR10, or MNIST and perform full batch sampling to see if there are significant changes.\n\nOtherwise, I am quite happy with the quality and contributions of the paper. However, as a layperson in the field of nonlinear sampling, I might have missed something important in the proofs and theorems, and would defer to the judgement of more knowledgeable reviewers before making a final judgement.", "limitations": "I believe the authors should refer to the additional computational requirements required by their method in terms of wall clock time as well, if possible. They might have this information in an appendix, or I might have missed it, in which case please point me to it. They have addressed social impacts.", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. Originality\n\nThe paper builds heavily on the initial mathematical machinery proposed in [1]. However, they derive novel convergence bounds for these nonlinear MCMC samplers in quite general settings. They also show that these bounds are satisfied for two common nonlinear samplers. The paper also uses really interesting results from the \"propagation of chaos\" to show that even though the central limit theorem breaks down in a nonlinear setting due to statistical dependences across particles, there are still arguments that can be made about the independence of these interactions as $N \\rightarrow \\infty$. I found the motivations and mathematical proofs quite novel.\n\n2. Quality\n\nFor someone who is a layperson to nonlinear MCMC methods, I found the paper had very high pedagogical quality, and I was able to understand to a large extent the breadth of the literature on this field. I found the mathematical proofs correct in my understanding, though I did not look closely at the proofs in the appendix. I followed through the intuition and justifications that lead to Theorem 1, and I think it is an elegant result, that gives us useful convergence bounds for nonlinear MCMC methods.\n\n3. Clarity\n\nI found the paper easy to follow in terms of its writing, if not always in the math. Some of this is due to a lack of expertise in nonlinear MCMC techniques, however I believe the authors did a good job providing background where necessary and shifted a large part of the verbose Mathematics to the appendices.\n\n4. Significance\n\nI believe this paper has quite a significant convergence bound for nonlinear MCMC. Also, I believe the empirical \"negative\" result on the CIFAR10 problem shows an important limitation of nonlinear MCMC methods currently. I think this result, showing that nonlinear methods perform as well as linear methods, but don't necessarily outperform them, is an important factor to consider before using these methods for large scale Bayesian machine learning.", "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": "_WDdnPUZEZ8", "reviewer": "Reviewer_RMta", "summary": "The work explores the existing technique of nonlinear MCMC, where the transition kernel draws information from across a collection of samples. It establishes some theoretical results, and proposes two such kernels (Boltzmann-Gibbs interaction and Accept-Reject interaction), with empirical demonstrations of both.", "questions": "* How are the x-axes on the MMD plot in Figure 1 scaled? Do they account for different number of kernel executions in each MCMC step for these methods (if I understand correctly), i.e. computational complexity?", "limitations": "No concerns.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work reflects substantial effort, but a good amount of the material reads as a review, and I'm unsure that the theoretical results really connect with the proposed kernels to make for a coherent contribution at this stage. This does look to be a useful line of inquiry and I do not wish to discourage the author(s), but the work as it stands does not yet seem ready for publication.\n\nIn a sense it seems like two works, the first establishing the theoretical results, the second proposing the new kernels within the nonlinear MCMC framework and showing they can work, although not that they can outperform. On the first I'm not well placed to determine whether the theoretical results alone stand as a sufficient contribution or display original insight (and if they do, they might be published in isolation). On the second I am not sure that there is sufficient novelty here: the kernels are not greatly different from existing work from what I can tell, and the empirical assessment of them is quite limited, showing that they work, but not that they outperform in predictive performance, say, or exhibit some other desirable quality such as accurate uncertainty quantification (as motivated in the introduction).\n\nOverall, I think that either the method and application would need to be developed further, or the work should focus on the theoretical results, but it is difficult to recommend in its current form.", "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": "9JXtKiX45J9", "reviewer": "Reviewer_A9qb", "summary": "This paper considers the application of the nonlinear Markov Chain Monte Carlo (MCMC) method to problems in Bayesian inference. The key idea of the method is, instead of using a single kernel, a mixture of two kernels, a linear and non-linear one are used. Two types of non-linear kernels are considered, the Boltzmann-Gibbs interaction and the Accept-Reject interaction. It is shown that the performance of the proposed methods is at least as good as when the non-linear kernel is not used in addition to the linear one.\n", "questions": "In line 145-146 you say \"jump to a new state distributed according to \\eta(dy)\". However, this sampler [Accept-Reject interaction] just samples from \\pi using the proposal \\eta^*. What is, and what is the role of \\eta here? \n\nAnother question about the accept-reject interaction is why do you call it \"adaptive Metropolis-Hastings\"? This term is usually used for MCMC samplers that progressively change the proposal as the chain is run, while preserving convergence properties. The Accept-Reject interaction as presented here is a standard independence (or independent) Metropolis-Hastings sampler with the proposal distribution \\eta^*.\n\nI am not sure that the non-reversibility of BG (as opposed to AR) matters so much in the neural networks experiment. Have you tried AR for completeness? Does it do the same? I would presume that using a tempered density as the proposal is the more important factor here?\n", "limitations": "Yes. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general, combining different MCMC methods to achieve better exploration of a target density is good practice, e.g., in the case of a multimodal density, one can combine local moves that explore within a mode with moves that explore between different modes. The rationale is that neither of these moves by themselves would provide good exploration of the target density: local moves will take a long time to travel between different modes, whereas global moves will typically have trouble exploring a mode locally. This paper aligns with the general idea of the benefit of combining together different MCMC kernels.\n\nThe general idea of the paper is sound. However, a drawback is that it is at times hard to understand what exactly is happening and to link various portions of the paper together. As far as was able to tell, the idea at the core of the paper is as described above, to combine MCMC moves with different average jump sizes and to show this leads to better exploration. For example, the description of an Interacting Particle System is hard to link to the concrete MCMC schemes (i.e., based on the Boltzmann-Gibbs and Accept-Reject interaction) proposed in this paper. \n", "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": "8GRrSrVNVc", "reviewer": "Reviewer_tYtV", "summary": "This work proposes a non linear MCMC method based on an interacting particle system. The article studies its long-time and large-particle non-asymptotic behaviour, ultimately showing the method consistency under standard hypotheses. The method is then illustrated on toy and real-world examples. While the paper is strongly related to [1], it the way the empirical non-linearity is formed (and subsequent analysis) differs from [1] in the following way: it is defined as a self-interacting process in [1], and as an interacting particle system in this work.", "questions": "1. The paper argues that MCMC consists in running independent chains and averaging the results out (line 43). However, this is typically argued against in the literature (see http://users.stat.umn.edu/~geyer/mcmc/one.html for a summary). This is also not the approach taken by [1] as the main related work. I believe why the paper considers this framework in particular probably requires some discussion. This seems a subtle yet key difference with [1], visibly coming from the IPS perspective in this work versus the self-interacting perspective of [1]. Perhaps a background section on [1] in the supplementary would help the reader pinpoint the exact difference with [1].\n\n2. A related question is concerned with the ergodicity of the system (3): can we hope for a LLN (similar to Theorem 6.1 in [1]) for a fixed number of particles $N$? \n\n3. Corollary 1 seems to be a corollary of Theorem 3, not Theorem 1. It would be good to refer to the proof Proposition 2.2 in [41] to help the reader. Furthermore, a square seems to be missing from the corollary as compared to the proof (although Cauchy-Schwarz gives you the result stated). If however, the desired result is indeed in terms of absolute error, why not directly use Theorem 3 with $q = N$ on the function $\\tilde{f}(x_1, \\ldots, x_N) := \\frac{1}{N osc(f)}\\sum_{k=1}^N f(x_k)$? I think this would be simpler to understand than the argument given.\n\n4. Theorem 3: I believe the hypothesis on $J$ should be for all probability measures $\\eta$. The proof is difficult to read, is it possible to make the absolute value bars larger to see where it is split? There is a typo in the proof second line of the equation block under line 888: the subcripts for the compensating terms are wrong. Furthermore, a lot of things are happening between step 3 and 4 of this block. Isn't there a term missing similar to what is obtained in Case 2? More details on the derivation would be appreciated. As minor details, there are some double closed (and unclosed) brackets and parentheses throughout the proof. E.g. line 896 and 897 (last equation of the block). There is a typo on the fact that K is a q-product on line 894. Also, the notation is not coherent in terms of applying a kernel to a function: sometimes it is K(f), sometimes Kf (and similarly for J(f) vs Jf). Can you make it fit with Section 1.3?\n\n5. This is minor, but in Assumptions D.2., isn't the condition that V needs to be finite at least somewhere missing?\n\n6. In the experiments section, why is the current work not compared with [1]? While I don't mind the method not necessarily reaching state of the art, I believe it is rather important to compare it to its closest relative. My guess is that this is due to a technical limitation related to using JAX. This is clearly an issue with [1] that it requires evergrowing memory (and it could be pointed in the paper) however, it would be great to compare the two methods on at least the toy examples.\n\n7. As mentioned in the CIFAR example, using an based sampler for Q results in a biased method of X, because G is now not perfectly related to Q. In this case, have the authors considered using an empirical version of G: $G_n$, where $\\eta^*$ is replaced by using the previous estimate $\\eta_n$, giving (in the Boltzmann case) $K_{\\eta, n} = (1-\\epsilon) K(x, dy) + \\epsilon \\Psi_{G_n}(\\eta)(dy)$ (this would be, I guess, a bit similar to [50])? \n\n8. The run time for the different experiments was not reported. In fact, I believe that Figure 2 should be reported in terms of iterations (as here) as well as with the x-axis being the run time.  ", "limitations": "Some limitations of the work are a bit too quickly brushed over, in particular, the fact that the LLN of this article is across the particles, and not on the trajectory of the Markov chains, is a bit too subtle (see questions).", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\nThis is clearly a strong methodological paper, with good theoretical backing for the consistency of the method. The method is creative and substantially different from previous works. The presentation is rather clear, but can be improved upon as hinted in the questions section.\n\n# Weaknesses\nThe differences with [1] are fairly subtle and may not be noticed at first read, in particular because no background on [1] is provided. \nThis paper is rather long for a conference format, and most of the story, and interesting proof points lie in the appendix.\nThe experiments lack a comparison with [1] which is the main related work, rather than MALA.\n\n\n# Minor comments and typos\n\n1. The references are not formatted properly (for instance lacking proper capitalisation of names \"hamiltonian monte carlo\", \"bayes\" etc), or sometimes not properly referenced (\"How good is the bayes posterior in deep neural networks really?\" is published at ICML, \"Uniform long-time [...]\" at Journal of Statistical Physics)\n2. intractible -> intractable\n3. has an added -> presents an additional\n4. Compatability -> Compatibility\n5. critera -> criteria\n6. “distribution flow” is not linked to equation (8)\n7. This is inequality -> This inequality (line 222)\n8. The weighted supremum norm term used in G2 is not defined explicitly in D.1.2\n9. of auxiliary density $\\eta^*$ is required -> the auxiliary\n10. dyanmics -> dynamics\n11. stepszie -> stepsize\n12. otherewise -> otherwise\n13. account of our experimental settings -> missing full stop.\n14. which is depends -> which depends\n15. Capitalisation of names in the references is sometimes off (langevin, gibbs, etc)\n16. I can see that some cited papers are given as arxiv references, but are actually published (at least [32], [40], [60]), please check.", "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