Learning Rate Free Sampling in Constrained Domains
Authors: Louis Sharrock
Lester Mackey
Christopher Nemeth
Venue: NeurIPS 2023 poster (2023)
Keywords: Sampling
Particle Based Variational Inference
Bayesian Inference
Wasserstein Gradient Descent
Coin Betting
Constrained Domains
TL;DR: We introduce new algorithms for sampling in constrained domains which are learning rate free.

Abstract: We introduce a suite of new particle-based algorithms for sampling in constrained domains which are entirely learning rate free. Our approach leverages coin betting ideas from convex optimisation, and the viewpoint of constrained sampling as a mirrored optimisation problem on the space of probability measures. Based on this viewpoint, we also introduce a unifying framework for several existing constrained sampling algorithms, including mirrored Langevin dynamics and mirrored Stein variational gradient descent. We demonstrate the performance of our algorithms on a range of numerical examples, including sampling from targets on the simplex, sampling with fairness constraints, and constrained sampling problems in post-selection inference. Our results indicate that our algorithms achieve competitive performance with existing constrained sampling methods, without the need to tune any hyperparameters.

Learning Rate Free Sampling in Constrained Domains
Louis Sharrock
Lester Mackey
Department of Mathematics and Statistics Lancaster University, UK
Microsoft Research New England Cambridge, MA
1. sharrock@lancaster. au.uk
Imackey&microsoffe
Christopher Nemeth
Department of Mathematics and Statistics Lancaster University, UK
c. aanametth@lncasstee acc.aac.in ackuk
Abstract
We introduce suite of new particle-based algorithms for sampling in constrained domains which are entirely learning rate free. Our approach leverages coin betting ideas from convex optimisation, and the viewpoint of constrained sampling as a mirrored optimisation problem the space of probability measures. Based on this viewpoint, we also introduce a unifying framework for several existing constrained sampling algorithms, including mirrored Langevin dynamics and mirrored Stein variational gradient descent. We demonstrate the performance of our algorithms on range of numerical examples, including sampling from targets the simplex, sampling with fairness constraints, and constrained sampling problems in post- selection inference. Our results indicate that our algorithms achieve competitive performance with existing constrained sampling methods, without the need to tune any hyperparameters.
Introduction
The problem of sampling from unnormalised probability distributions of central importance to computational statistics and machine learning. Standard approaches this problem include Markov chain Monte Carlo (MCMC) [11, 76] and variational inference (VI) [41, 96]. More recently, there has been growing interest particle-based variational inference (ParVI) methods, which deterministically evolve a collection of particles towards the target distribution and combine favourable aspects of both MCMC and VI. Perhaps the most well-known of these methods is Stein variational gradient descent (SVGD) [63], which iteratively updates particles according to form of gradient descent on the Leibber (KL) divergence. This approach has since given rise to several extensions [16, 27, 97, 105] and found success in a wide range of applications [27, 66, 74].
While such methods have enjoyed great success in sampling from unconstrained distributions, they typically break down when applied to constrained targets [see, e.g., 60, 82). This is required for targets that are not integrable over the entire Euclidean space (e.g., the uniform distribution), when the target density is undefined outside a particular domain (c.g., the Dirichlet distribution), or when the target must satisfy certain additional constraints (c.g., fairness constraints Bayesian inference [65]). Notable examples include latent Dirichlet allocation [9], ordinal data models [45], regularised regression [15], survival analysis [49], and post-selection inference [54, 88]. recent years, there has been increased interest in this topic, with several new methodological and theoretical developments [1, 19, 43, 44, 60, 61, 82, 86, 103, 104].
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

One limitation shared by all of these methods is that their performance depends, often significantly. on a suitable choice of learning rate. In principle, convergence rates for existing constrained sampling schemes (e.g., [1, Theorem 1] or [86, Corollary IJ) allow one to compute the optimal learning rate for a given problem. In practice, however, this optimal learning rate is function of the unknown target and thus cannot be computed. Motivated by this problem, in this paper we introduce suite of new sampling algorithms for constrained domains which are entirely learning rate free.
Our contributions We first propose unifying perspective of several existing constrained sampling algorithms, based on the viewpoint of sampling in constrained domains as a 'mirrored' optimisation problem on the space of probability measures. Based on this perspective, we derive a general class of solutions to the constrained sampling problem via the mirrored Wasserstein gradient flow (MWGF). The MWGF includes, as special cases, several existing constrained sampling methods, e.g., mirrored Langevin dynamics [43] and mirrored SVGI (MSVGD) [82]. Using this formulation, we also introduce mirrored versions of several other particle-bass sampling algorithms which are suitable for sampling in constrained domains, and study their convergence properties in continuous time.
By leveraging this perspective, and extending the coin sampling methodology recently introduced in [81], we then obtain suite of learning rate free algorithms suitable for constrained domains. In particular, we introduce mirrored coin sampling, which includes as a special case Coin MSVGD, as well as several other tuning-free -free constrained sampling algorithms. We also outline an alternative approach which does not rely on a mirror mapping, namely, coin mollified interaction energy descent (Coin MIED). This algorithm can be viewed as the natural coin sampling analogue of the method recently introduced in [60]. Finally, we demonstrate the performance of our methods on a wide range of examples, including sampling on the simplex, sampling with fairness constraints, and constrained sampling problems in post-selection inference. Our empirical results indicate that our methods achieve competitive performance with the optimal performance of existing approaches, with no need to tune a learning rate.
2 Preliminaries
The Wasserstein Space. We will make use of the following notation. For any X' C Rd. we write (x)))) for the set of probability measures on X' with finite 2nd moment: Jx [|=]] < co, where ||-|| denotes the Euclidean norm. For j E P2(x)) we write (²( for the set of measur- able f : X + X with finite || = Sxx [I (u(x). For f.g E (²),), we also define (J: LP(W)) = fx f(x) (()))((z)) Given μ E (2) and T E LP(,), we write Typ for the pushforward of μ under T, that is, the distribution of T(X) when X μ..
P2( the Wasserstein 2-distance between i and v is defined according to v) inf, (Er(,)))))) fxxx || ydr, dy), where v(H,v) denotes the set of couplings between μ and v. The Wasserstein distance W₂ is indeed a distance over P2 [2. Chapter 7.11, with the metric space (P2(X). W2) known as the Wasserstein space. Given a functional
Given p,
F: FP(()) - (-20, oo). we will write F(u) for the Wasserstein gradient of F at μs, which
exists under appropriate regularity conditions [2, Lemma 10.4.1]. We refer to App. A for further details on calculus in the Wasserstein space.
Wasserstein Gradient Flows. Suppose that ग E P2(X') and that π admits a density x x e e with respect to Lebesgue measure," where V X' - R is a smooth potential function. The problem of sampling from π can be recast as an optimisation problem over P2(X') [c.g., 99]. In particular, one can view the target as the solution of
π arg min F(u) (X)
(I)
where F: P(X)) - (-oc, oo] is functional uniquely minimised at w. In the unconstrained case, X' = RRd, now rather classical method for solving this problem is to identify a continuous process which pushes samples from an initial distribution μi to the target π. This corresponds to finding a
-
family of vector fields (v:)c20. with U2 E L (ux), which transports μe to π via the continuity equation
Opc + V (vepte 0.
Øt
'In slight abuse of notation, throughout this paper we will use the same letter to refer to a distribution and its density with respect to Lebsegue measure.
2

---

A standard choice is 0z = -V -V.,F((u)). in which case the solution (Pt) of (2) is referred to as the Wasserstein gradient flow (WGF) of F. fact, for different choices of (v) (2))20- one can obtain the continuous-tin Unfortunately, it not straightforward to extend these approaches to the case which X C Rd is a constrained domain. For example, the vector fields 1, may push the random variable Iy outside of its support X, thus rendering all future updates undefined.
limit of several popular sampling algorithms [3. 20, 40, 46, 51, 63, 99].
3 Mirrored Wasserstein Gradient Flows
We now outline one way to extend the WGF approach to the constrained case, based on the use of a mirror map. We will first require some basic definitions from convex optimisation [e.g., 77J. Let X' be closed, convex domain in R Let Φ X R J {oo} be proper, lower semicontinuous, strongly convex function of Legendre type [77]. This implies, in particular, that Vo((X) R and VØ X + Rd is bijective [77, Theorem 26.5]. Moreover, its inverse (VØ)-1 : Rd + X satisfies (VØ)
Vø", where o* Rd + R denotes the Fenchel conjugate of Φ, defined as o (v)) = supzex (ar, v) - (x)). We will refer to V X + Rd as the mirror map and V*(()) Rd
as the dual space.
3.1 Constrained Sampling as Optimisation
Using the mirror map VΦ: X ER we can now reformulate the constrained sampling problem as the solution of a 'mirrored' version of the optimisation problem in (1). Let us define (VØ) # with ग (Vo") We can then view the target π as the solution of
(Vo")
V == arg min F(n), vEP2(Bd)
(3)
where now F P2( ( (-00, oa] is functional uniquely minimised by == (Vo) The motivation for this formulation is clear. Rather than directly solving a constrained optimisation problem for the target æ E (2) as in (1), we could instead solve unconstrained optimisation problem for the mirrored target E (2))))) and then recover the target via æ = (VØ*) This is a rather natural extension of the formulation of sampling as optimisation the constrained setting.
3.2 Mirrored Wasserstein Gradient Flows
One way to solve the mirrored optimisation problem in (3) is to find a continuous process which transports samples from 7/- == (Vo) # M4 E (R2))) to the mirrored target v. According to the mirror map, this process will implicitly also push samples from po to the target æ. More preciscly, we would like to find (wy)220. where W Rd 12d, which evolves To Hd and thus μr on X, through
On
+ (we)) = 14 =
Öt
where (wy)22 should ensure convergence of y/ to v. the case that wi = - we will refer to (4) as the mirrored Wasserstein gradient flow (MWGF) of F. The idea of (4) is to simulate the WGF in the (unconstrained) dual space and then map back to the primal (constrained) space using a carefully chosen mirror map. This approach bypasses the inherent difficulties associated with simulating a gradient flow on the constrained space itself.
While a similar approach has previously been used to derive certain mirrored sampling schemes [43, 82, 86], these works focus on specific choices of F and (wx)22o. while we consider the general case. Our general perspective provides a unifying framework for these approaches, whilst also allowing us to obtain new constrained sampling algorithms and to study their convergence properties (see App. B). We now consider one such approach in detail.
3.2.1 Mirrored Stein Variational Gradient Descent
MSVGD [82] a mirrored version the popular SVGD algorithm. In [82], MSVGD is derived using a mirrored Stein operator in a manner analogous to the original SVGD derivation [63]. Here, we take an alternative perspective, which originates in the MWGF. This formulation is more closely aligned with other more recent papers analysing the non-asympiotic convergence of SVGD [51, 78, 85, 86).
3

---

Algorithm 1 MSVGD
input:
target density n, kernel kt mirror function o, particles (x))) 14o, step size 7-
initialise: v6 VØ((t) for i E [N]
for t = ==0,... ....... T 1 do
For i E [i], = vi - 117-7p P ko V log ) (vi), where it. = ΣE= 22
For i E [N], (N (vt(v)+1)
return (x7))
We will require the following additional notation. Let k X' X' R denote a positive semi-definite kernel and Hy the corresponding reproducing kernel Hilbert space (RKHS) of real-valued functions X + R. with inner product (--) and norm || 1124.. Let H. := Hg denote the Cartesian product RKHS, consisting of elements f (J1...., fa) for fa E Ha. We write Sp. 1.2 + H for the operator Su = k(x, (()((. We assume I k(z z)du(a) < Do for μa E P2 in which case H C (p) for all μ E (2( [52, Sec. 3.1]. We also define the identity embedding i: H (m) with adjoint i = Sp,-- Finally, we define Pus: (²(x)) + (2( Py. is p.
We are now ready to introduce our perspective on MSVGD. We begin by introducing the continuous- time MSVGD dynamics, which are defined by the continuity equation
Om
V
(Pos. V log
mh = 0, 14 (V +7t:
Öt
where (v)y, 3/) = k (V) (y). V (y')) for some base kernel k X x X + R. Clearly, this is a special case of the MWGF in (4), in which (wy)e20 are defined according to W. = -P... V F(n)). with F(m) = (L(mllv> In particular, Wi can be interpreted as the negative Wasserstein gradient of KL (m)) the KL divergence of the n, with respect to v, under the inner product of Hi.
The key point here is that, given samples from 17, estimating Pnc.kg V Vlog(") (t) is straightforward. In particular, if liml ki -)u(s)) O, then, integrating by parts,
P Re V Log( ne (v) - f [koly/ V of log v(y'
ko y)l (v').
(6)
To obtain implementable algorithm, we must discretise in time. By applying an explicit Euler discretisation to (5), we arrive at
id - ko V log ())
+
# nt. Mc+1 = (V ) #++1
where 7 >> is step size or learning rate, and id is the identity map. This is the population limit of the MSVGD algorithm in [82]. Now, suppose No E P2( admits a density with respect to the Lebesgue measure. In addition, suppose To Mo and yo Vo(zu). Then, for t E Ny. if we define
M-+1 = ye - y kg V log
7/
(vr),
F++1 = (1(+1),
(8)
then (MN), and (Me)tEN in (7) are precisely the densities of (We)en,, and (xx (EN)) in (8). In prac- tice, these densities are unknown and must be estimated using samples. In particular, to approximate i.i.d.
(8), we initialise a collection of particles zi ng for E [N]. set y6 = Vo(zz)) and then update
Vi+1 = vi - PrPni V log
(1)),
2 = (v(41)
N where it = N. プタ
8 6zg This is precisely the MSVGD algorithm introduced in [82] and since also
studied in [86].
3.2.2 Other Algorithms
In App. B. we outline several algorithms which arise as special cases of the MWGF. These include existing algorithms, such as the mirrored Langevin dynamics (MLD) [43] and MSVGD [82], and two new algorithms, which correspond to mirrored versions of Laplacian adjusted Wasserstein gradient descent (LAWGD) [20] and kernel Stein discrepancy descent (KSDD) [51]. We also study the convergence properties of these algorithms in continuous time.

---

4 Mirrored Coin Sampling
By construction, any algorithm derived as discretisation of the MWGF, including MSVGD, will depend on an appropriate choice of learning rate 7, In this section, we consider an alternative approach, leading to new algorithms which are entirely learning rate free. Our approach can be viewed as an extension of the coin sampling framework introduced in [81] to the constrained setting, based on the reformulation of the constrained sampling problem mirrored optimisation problem.
4.1 Coin Sampling
We begin by reviewing the general coin betting framework [22, 71, 72]. Consider gambler with initial wealth we = 1 who makes bets on a series of adversarial coin flips e2 E {-1,1} 1,, where +1 denotes heads and - denotes tails. We encode the gambler's bet by I2 R. In particular, sign(x;) E } denotes whether the bet is on heads or tails, and |atel E IR denotes the size of the bet. Thus, in the tth round, the gambler wins [ if sign(c;) = sign(24) and loses |2t,c| otherwise. Finally, we write W/ for the wealth of the gambler at the end of the HTh round. The gambler's 's wealth
thus accumulates as wi = -1+ + CgUgg We assume that the gambler's bets satisfy xt = Brw,-1, for a betting fraction Be E [-1, I]. which means the gambler does not borrow any money.
In [71], the authors show how this approach can be used to solve convex optimisation problems on R", that is, problems of the form x= arg minzerd f(x)), for convex f Rdd -> R.. In particular, [71] con- sider a betting game with 'outcomes' Q = - (xx,, replacing scalar multiplications C.T. by scalar products (ca, .z). In this case, under certain assumptions, they show that f(y Σl= 324 - f(=") a rate determined by the betting strategy. There are many suitable choices for the betting strategy. Perhaps the simplest of these is 3r strategy (53, 71]. which yields the sequence of bets dt = -, = 1-1 > Other choices, however, are also possible [22, 70, 72].
Σ C.. known as the Krichevsky-Trofimng
(KT) betting
f-1 1==1 c, + > s=1 (Ca, tx,).
In [81], this approach was extended to solve optimisation problems on the space of probability measures. In this case, several further modifications are necessary. First, in each round, one now bets 24- - Fo rather than Tt, where Zg ~ (4n is distributed according to some μl0 E (RR))). In this case, viewing Fe : Rd -> Rd as function that maps To + Iz (2o), one can define a sequence of distributions ((4))n as the push-forwards of μo under the functions (xx) In particular, this means that, if xg Ho. then 2t,- Pr-
By using these modifications in the original coin betting framework, and choosing (Co)EeN == (cp, (EE)))EN appropriately, [81] show that it is now possible to solve problems of the form =²= = arg min F(u). This approach is referred to as coin sampling. For example, by consid- ering betting game with c
F(r)) [81] obtain 'coin Wasserstein gradient descent' algorithm, which can be viewed as a learning-rate free analogue of Wasserstein gradient descent. Alternatively, setting C =-Pp.. fr, V (zz)), one can obtain a learning-rate free analogue of the population limit of SVGD, in which the updates are given by
21 Z0
=== P & & Vw, Vw, (2.))
(1-
(1-
t-1 Vw,
zo)
(10)
where, as described above, 14, (xx) Ho. In practice, the densities (Ut)LEN, and thus the outcomes (C.)eN are almost always intractable, and will be approximated using a set of interacting particles.
4.2 Mirrored Coin Sampling
By leveraging the formulation of constrained sampling as a 'mirrored' optimisation problem over the space of probability measures, we can extend the coin sampling approach to constrained domains. In particular, as an alternative to discretising the MWGF to solve this optimisation problem (Sec. 3.2), we propose instead to use a mirrored version of coin sampling (Sec. 4.1.. The idea is use coin sampling to solve the optimisation problem in the dual space, and then map back to the primal space using the mirror map. In particular, this suggests the following scheme. Let an ~ po E P2(X)) and Yo Vo(zo) E Rd.. Then, for t N, update
V/ = yo + L=ml Cy. (U=))
--11
1+ Σ (Cn (v.). yo yod = -Z)(22),
(11)
5

---

Algorithm 2 Coin MSVGD
input: target density n, kernel kt mirror function o, particles (x 14o- intialise: vó= = Vo((t)) for i E [M]
for 1,..., do
For [N] vi = yo
Σ.n Pa V Vlog(
( di (oh)
(1- E-=E (Prinko log (og(()))))))))))) =6))
For E [M] 2t = (v)(
return iiT)
A.V.
where 7/c = (Ve) ) #o and μr (Vé") # and where Cr, (v.) = F (v+), some variant thereof. We will refer to this approach as mirrored coin sampling, or mirrored coin Wasserstein gradient descent. In order to obtain an implementable algorithm, we proceed as follows. First, decide on suitable functional and a suitable (Ct)LEN := (c,, (y, ).EN. For example, F(n) = KL v), and (Ce)<EN (-Pr, Ak F(n:) updates using a set of interacting particles, as in existing ParVIs algorithms.
Then, substitute these into (11), and approximate the
Following these steps, we obtain a learning rate free analogue of MSVGD [82]. which we will refer as Coin MSVGD, This is summarised in Alg. 2. For different choices of (c,, JtE in (11), we also obtain learning rate free analogues of two other mirrored VI algorithms introduced in App. B, namely mirrored LAWGD (App. B.3), and mirrored KSDD (App. B.4). These algorithms, which we term Coin MLAWGD and Coin MKSDD, are given in Alg. 6 and Alg. 7 in App. D.
Even in the unconstrained setting, establishing the convergence of coin sampling remains an open problem. In [81]. the authors provide a technical sufficient condition under which it is possible to establish convergence to the target measure in the population limit; however, it difficult to verify this condition in general. In the interest of completeness, in App. C, we provide an analogous convergence result for mirrored coin sampling, adapted appropriately the constrained setting.
4.3 Alternative Approaches
In this section, we outline an alternative approach, based on a 'coinification' of the mollified interaction energy descent (MIED) method recently introduced in [60]. MIED is based minimising a function known as the mollified interaction energy (MIE) & P(R") + [0, xo]. The idea is that minimising this function balances two forces: a repulsive force which ensures the measure is well spread, and an attractive force which ensures the measure is concentrated around regions of high density. In order to obtain practical sampling algorithm. [60] propose to minimise a discrete version of the logarithmic MIE, using, c.g., Adagrad [31] or Adam [48]. That is, minimising the function
a
n
log (."w)) == log
(12)
N2
where wn = {x ".."....,""". r²), and where (Øe)eso is a family of mollifiers [60. Definition 3.1]. This approach can be adapted to handle the constrained case, as outlined in [60]. In particular, if there exists differentiable f Rd - X' such that X' \ f(R4) has Lebesgue measure zero, then one can reduce the constrained problem to an unconstrained one by minimising log (f(f(w")) where If f(w*) = (x)),.... ... [x")). Meanwhile, if X = {x E Id g(x) < 0} for some differentiable g: g + R, then one can use variant of the dynamic barrier method introduced [37].
Here, as an alternative to the optimisation methods considered in [60], we instead propose to use a learning-rate free algorithm to minimise (12), based on the coin betting framework described in 4.1. We term the resulting method, summarised in Alg. 3, Coin MIED. In comparison to our mirrored coin sampling algorithm, this approach has the advantage that it only requires differentiable (not necessarily bijective) map.
5 Related Work
Sampling as Optimisation. The connection between sampling and optimisation has a long history, dating back to [46], which established that the evolution of the law of the Langevin diffusion

---

Algorithm 3 Coin MIED
Input: target density n, mollifier de. particles wß (zt))==1 (1 (1- (V
for 1 = 1....,, .....,Too Tdo do
For E [4 2² 2 V o log Ec(w")
log Ee (u()), mb)))
return (27))
corresponds to the WGF of the KL divergence. In recent years, there has been renewed interest in this perspective [99]. In particular, the viewpoint of existing algorithms such as LMC. [23, 24, 33, 34] and SVGD [32, 63] as discretisations of WGFs has proved fruitful in deriving sharp convergence rates |6. 34, 52, 78, 83, 85]. has also resulted in the rapid development of new sampling algorithms, inspired by ideas from the optimisation literature such as proximal methods [100], coordinate descent [29, 30J, Nesterov acceleration [18, 25, 67J. Newton methods [68, 84, 98], and coin betting [80, 81].
Sampling in Constrained Domains. Recent interest in constrained sampling has resulted in a range of general-purpose algorithms for this task [e.g., 43, 60, 82, 103, 104]. In cases where it is possible to explicitly parameterise the target domain in lower dimensional space, one can use variants of classical methods, including LMC [98], rejection sampling [28]. Hamiltonian Monte Carlo (HMC) [13]. and Riemannian manifold HMC [55, 73]. Several other approaches are based on the use of mirror map. In particular, [43] proposed mirrored Langevin dynamics and its first-order discretisation. [103], and an earlier draft of [43]. introduced the closely related mirror Langevin diffusion and the mirror Langevin algorithm, which has since also been studied [1, 19, 44, 61J. Along the same lines, [82] introduced two variants of SVGD suitable for constrained domains based on the use of mirror map, and established convergence of these schemes to the target distribution; see also [86]. In certain cases [e.g.. 56, 58] one cannot explicitly parameterise the manifold of interest. In this setting, different approaches are required. [12] introduced a constrained version of HMC for this case. Meanwhile, [102] proposed a constrained Hasttng algorithm with reverse projection check to ensure reversibility: this approach has since been extended in [57, 59]. Other, more recent approaches suitable for this setting include MIED [60] (see Sec. 4.3), and O-SVGD [104].
Numerical Results
In this section, we perform an empirical evaluation of Coin MSVGD (Sec. 6.2) and Coin MIED (Sec. 6.3). We consider several simulated and real data experiments, including sampling from targets defined on the simplex (Sec. 6. confidence interval construction for post-selection inference (Sec. 6.2), and inference in a fairness Bayesian neural network (Sec. 6.3). We compare our methods to their learning-rate- dete-dependnnt analogues, namely, MSVGD [82] and MIED [60]. We also include a comparison with Stein Variational Mirror Descent (SVMD) [82], and projected versions of Coin SVGD [81] and SVGD [63], which include Euclidean projection step to ensure the iterates remain in the domain. We provide additional experimental details in App. F and additional numerical results in App. G. Code reproduce all of the numerical results can be found at https:// gi thub. com/louis swwarssck/ www.ccoonnnnndnncocccco sat--sammlnnn...
6.1 Simplex Targets
Following [82], we first test the performance of our algorithms on 20-dimensional targets defined
on the simplex: the sparse Dirichlet posterior of [73] and the quadratic simplex target of [1]. We employ the IMQ kernel and the entropic mirror map [7]; and use N 50 particles, T = 500 iterations. In Fig. I and Fig. 6- (App. F.1), we plot the energy distance [87] to a set of surrogate ground truth samples, either obtained i.i.d. (sparse Dirichlet target) or using the No-U-Turn Sampler (NUTS) [42] (quadratic target). After T = 500 iterations, Coin MSVGD has comparable performance to MSVGD and SVMD with optimal learning rates but significantly outperforms both algorithms for sub-optimal learning rates (Fig. 1). In both cases, the projected methods fail to converge. For the sparse Dirichlet posterior, Coin MSVGD converges more rapidly than MSVGD and SVMD, even for well-chosen values of the learning rate (Fig. 6a in App. F. Meanwhile, for the quadratic target, Coin MSVGD generally converges more rapidly than MSVGD but not as fast as SVMD [82], which takes advantage of the log-concavity of the target in the primal space (Fig. 6a in App. F.1).
7

---

10a
10
Energy Distance
Energy Distance
10-1
10
Coin MSVGD
Coin MSVGD
10-2
Proj. Coin SVGD
Proj. Coin SVGD
MSVGD
MSVGD
SVMD
SVMD
10
Proj. SVGD
SVGD
10-3
10
10-4
10
10-4
10-4
10
10
10
10
10-4
10-4
10
Learning Rate
Learinng Rate
(a) Sparse Dirichlet Posterior.
(b) Quadratic Target.
Figure 1: Results for the simplex targets in [73] and [1]. Posterior approximation quality for Coin
MSVGD, MSVGD, projected Coin SVGD, projected SVGD, and SVMD.
6.2 Confidence Intervals for Post Selection Inference
We next consider a constrained sampling problem arising in post-selection inference [54, 88]. Suppose are given data (X, y) IR" "x x IR". We interested in obtaining valid confidence intervals (CIs) for regression coefficients obtained via the randomised Lasso [89], defined as the solution of
8 arg min BERP
2 - x Al1 - ww" w =1111111
(13)
where X, R2 are penalty parameters and Rp is an auxiliary random vector. Let 88 R2 rep- resent the non-zero coefficients of 3 and 2g sign(3p for their signs. If the support E were known priori, could determine CIs for Bg using the asymptotic normality of Ôg (X x - However, when E is based on data, these "classical' CIs will no longer be valid. In this case, one approach is condition on the result the initial model selection, i.e., knowledge of and zz In practice, this means sampling from the so-called selective distribution, which has support [(3r, å_ F. sign(3r: fn || Ello S 1}. and density proportional to [e.g.. 90, Sec. 4.2]
g(3r, 2 F) x (=(3g.0) x XBBE) (
(14)
Synthetic Example. We first consider the model setup described in [79, Sec. 5.3]; see App. F22 for full details. In Fig. 2, we plot the energy distance between samples obtained using Coin MSVGD and projected Coin SVGD, and set of 1000 samples obtained using NUTS [42], for two-dimensional selective distribution. Similar to previous examples, the performance of MSVGD is very sensitive to the choice learning rate. the learning rate too small, the partiele converge rather slowly; on the other hand, if the learning rate is too big, the particles may not Coin MSVGD converges rapidly to the true target, with no need to tune a learning rate. Similar to the examples considered in Sec. 6.1, the projected methods once again fail to converge the target, highlighting the need for the mirrored approach.
converge. Mcanwhile,
0.8
0.8
Coin MSVGD
Proj. Coin SVGD
0.7
0.7
MSVGD (LR=0.1)
Proj. SVGD (LR=0.1)
Energy Distance
0.6
MSVGD (LR=0.05)
Energy bistac
0.6
Proj. SVGD (LR=0.05)
0.5
MSVGD (LR=0.01)
0.5
Proj. SVGD (LR-0.01)
0.4
MSVGD (LR=0.005)
0.4
Proj. SVGD (LR=0.005)
0.3
0.2
0.2
0.1
0.0
0.0
200
400
600
800
1000
200
400
600
800
1000
Iterations
Iterations
(a) Coin MSVGD.
(b) Projected Coin SVGD.
Figure 2: Results for a two-dimensional post-selection inference target. Energy distance versus iterations for (a) Coin MSVGD and MSVGD and (b) projected Coin SVGD and projected SVGD, for a selective distribution the randomised Lasso in which two features are selected.

---

1.00
1.00
0.95
Actual Coverage
Actual coverage
0.90
0.85
Coin MSVGD
Coin MSVGD
MSVGD
MSVGD
0.80
SVMD
Standard
Standard
0.75
0.75
0.85
0.95
1000
1500
2000
2500
3000
Nominal coverage
Number of Samples
(a) Actual vs Nominal Coverage
(b) Coverage vs Number Samples
Figure 3: Coverage results for post-selection inference. Coverage of the post-selection confidence intervals obtained by Coin MSVGD, MSVGD, and SVMD, for 100 repeats of the simulation in [79, Sec. 5.3].
In Fig. 3, we plot the coverage of the CIs obtained using Coin MSVGD, MSVGD, SVMD, and the [91]. as vary the nominal coverage
norejection MCMC algorithm in selectiveInferent or the total number samples. For MSVGD and SVMD, we use RMSProp [92] to adapt the learning rate, with initial learning rate of 0.1, following [82]. As the nominal coverage varies, Coin MSVGD achieves similar coverage to MSVGD and SVMD; and significantly higher actual coverage than norejection (Fig. 3a). Meanwhile, as the number of samples varies, Coin MSVGD, MSVGD, and SVMD consistently all obtain higher coverage than the fixed nominal coverage of 90% (Fig. 3b). This is important for small sample sizes, where the standard approach undercovers. The performance of MSVGD and SVMD is, of course, highly dependent on an appropriate choice of learning rate. In Fig. 11 (App. G.3), provide additional plots illustrating how the coverage of the CIs obtained using MSVGD and SVMD can deteriorate when the learning-rate is chosen sub-optimally.
Real Data Example. We next consider post-sclection inference problem involving the HIV-1 drug resistance dataset studied in [8, 75]; see App. F.2 for full details. The goal is to identify statistically significant mutations associated with the response the drug Lamivudine (3TC). The randomised Lasso selects a subset mutations, for which we compute 90% CIs using 5000 samples and five methods: 'unadjusted' (the unadjusted Cls), 'standard' (the method in selecti weeenffeeee enennce)ce)) MSVGD, SVMD, and Coin MSVGD. Our results (Fig. 4) indicate that the CIs obtained by Coin MSVGD are similar those obtained via the standard approach, which view benchmark, as well as by MSVGD and SVMD (with a well chosen learning rate). Importantly, they differ from the CIs obtained using the unadjusted approach (see, e.g., mutation P65R or P184V in Fig. 4). Meanwhile, for sub-optimal choices of the learning rate (Fig. 4b and Fig. 4c, Fig. 12 in App. G.3), the CIs obtained using MSVGD and SVMD differ substantially from those obtained using the baseline 'standard' approach and by Coin MSVGD, once more highlighting the sensitivity of these methods the choice of an appropriate learning rate.
Coin MSVGD
2.4
MSVGD
DARU
2.2
SVMD
Unadjusted
2.0
Standard
ARL
(b) 7 0.001.
0.4
0.2
P1LL
P62V
PeSR
P67N
p69t
P7OR
p03k
PISIM
PISIC
P184V
P210W
P215Y
7
0.07.
(c) 7
1.0.
Figure 4: Real data results for past-selection inference. Confidence intervals for the mutations selected by the randomised Lasso as candidates for HIV-1 drug resistance. We report (a) all mutations when MSVGD and SVMD use a well chosen learning rate (y = 0.01) and (b) (c) subset of mutations when MSVGD and SVMD use smaller (? 0.001) or larger (? 1.0) learning rate.

---

Lingen
1.2e-03
4000
Can H&B pole-1
can Mad mnde
mad (mcea))
1.0e:03
HID
Constraint
Rlesz Energy
0.10
Coin KIEO
2000
0.08
6.0 6.0e-04
0.06-
4.0p-04
1000
0.04
2.0e-04
0.0e+00 00
0.645 0.840 0.835 0.830 0.825
500
1500
1000
1500
2000
Accuracy
Iterations
Iterations
(a) Trade off curves.
(b) Constraint vs. Iterations.
(c) Riesz Energy vs. Iterations.
Figure 5: Results for the fairness Bayesian neural network. (a) Trade-off curves showing dis-
parate impact versus test accuracy for MIED, Coin MIED, and the methods [65]. (b) - (c)
Co [2;; 0)] and MIE versus the number of iterations, for different values of for MIED and Coin MIED.
6.3 Fairness Bayesian Neural Network
Finally, following [60, 64, 65, 69], train fairness Bayesian neural network to predict whether an individual's 's income greater than $50,000, with gender as a protected characteristic. We use the Adult Income dataset [50]. The dataset is of the form D { Vi, 24 } where x; denote the feature vectors, Y/ denote the labels (i.e., whether the income is greater than $50,000), and 2 denote the protected attribute (i.e., the gender). We train two-layer Bayesian neural network y) w) with weights w and place a standard Gaussian prior on each weight independently. The fairness constraint given by g(0) Cov (r.,,)))) |2, [z;; 0))² t S for some user-specified >> In testing, we evaluate each method using a Calder-Verwer (CV) score [14]. a standard measure of disparate impact. We run each method for T 2000 iterations and use N 50 particles.
In Fig. 5a, we plot the trade-off curve between test accuracy and CV score, for t E (10-6,10 10-55 10-4..1.. 10 2 10 10-3,5 10 2). We compare the results for Coin MIED, MIED, and the methods in [65], using the default implementations. In this experiment, Coin MIED is clearly preferable to the other methods, achieving much larger Pareto front. In Fig. 5b and Fig. 5c, we plot the constraint and the MIE versus training iterations for both coin MIED and MIED. Once again, coin MIED tends outperform MIED, achieving both lower values of the constraint and lower values of the energy.
Discussion
Summary. In this paper, we introduced several new particle-based algorithms for constrained sampling which are entirely learning rate free. Our first approach was based the coin sampling framework introduced in [81], and a perspective of constrained sampling as a mirrored optimisation problem on the space of probability measures. Based this perspective, we also unified several existing constrained sampling algorithms, and studied their theoretical properties in continuous time. Our second approach can be viewed the coin sampling analogue of the recently proposed MIED algorithm [60]. Empirically, our algorithms achieved comparable or superior performance to other particle-based constrained sampling algorithms, with no need tune learning rate.
Limitations. We highlight three limitations. First, like any mirrored sampling algorithm, mirrored coin sampling (e.g., Coin MSVGD), necessarily depends the availability of mirror map that can appropriately capture the constraints of the problem at hand. Second, Coin MSVGD has a cost of O(N*) per update. Finally, even in the population limit, establishing the convergence of mirrored coin sampling under standard conditions (e.g., strong log-concavity or a mirrored log- tog-Sobolev inequality) remains an open problem. We leave this interesting direction for future work.
Acknowledgements
LS and CN were supported by the UK Research and Innovation (UKRI) Engineering and Physical Sciences Research Council (EPSRC), grant number EP/V022636/1. CN acknowledges further support from the EPSRC, grant number EP/RO1 860X/1.
10

---

References
[1] Kwangjun Ahn and Sinho Chewi. Efficient constrained sampling via the mirror-Langews algorithm. In Proceedings of the 35th International Conference Neural Information Processing Systems (NeurIPS 2021), ,, Online, 2021. 1,2, 7, 8, 18, 31, 33
[2] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Birkhäuser, Basel, 2008. 2, 17, 23, 28
[3] Michael Arbel, Anna Korba, Adil Salim, and Arthur Gretton, Maximum Mean Discrepancy Gradient Flow. In Proceedings of the 33rd International Conference Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada, 2019.
[4] D Bakry and M Emery. Diffusions hypercontractives. In Jacques Azéma and Marc Yor, editors, Séminaire de Probabilités XIX 1983/84, pages 177-206, Berlin, Heidelberg, 1985. Springer Berlin Heidelberg. 20, 23
[5] Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and Geometry of Markov Diffusion Operators. Springer Cham, 2014. 25
[6] Krishnakumar Balasubramanian, Sinho Chewi, Murat A. Erdogdu, Adil Salim, and Matthew Zhang. Towards a Theory Non-Log-Coneen Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo. In Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022), London, UK, 2022. 7
[7] Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letfers, 3163):167-175, 2003. 7
[8] Nan Bi, Jelena Markovic, Lucy Xia, and Jonathan Taylor. Inferactive data analysis. Scandina- vian Journal of Statistics, 47(1):212-249, 2020.
[9] David M. Blei, Andrew Y. Ng. and Michael Jordan. Latent Dirichlet Allocation. Journal of
Machine Learning Research, 10992,102,,, 2003. 1,
[10] Sergey G Bobkov. Isoperimetric and Analytic Inequalities for Log-Concave Probability Measures. The Annals of Probability, 27(4):1903-192) 1999. 20
[11] Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbook of Markov Chain
Monte Carlo. Chapman and Hal//CRC, 1st edition, 2011. 1
[12] Mareus Brubaker, Mathieu Salzmann, and Raquel Urtasun. A Family of MCMC Methods on Implicitly Defined Manifolds. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS), La Palma, Canary Islands, 2012. 7
[13] Simon Byme and Mark Girolami. Geodesic Monte Carlo on Embedded Manifolds. Scandina- vian Journal of Statistics, 40(4):825-84) 825, 2013. 7
[14] Toon Calders and Sicco Verwer. Three Naive Bayes Approaches for Discrimination-Free Classification. Data Mining and Knowledge Discovery. 21(2))277-292 2010. 10
[15] Gilles Celeux, Mohammed El Anbari, Jean-Michel Marin, and Christian P Robert, Regular- ization in Regression: Comparing Bayesian and Frequentist Methods in Poorly Informative Situation. Bayesian Analysis, 7(2):477-500 2012.
[16] Peng Chen and Omar Ghattas. Projected Stein Variational Gradient Descent. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada, 2020.
[17] Yuansi Chen. An Almost Constant Lower Bound of the Isoperimetric Coefficient in the KLS Conjecture. Geometric and Functional Analysis, 31(1):34-61, 2021. 20
[18] Xiang Cheng, Niladri S. Chatterji, Peter L.. Bartlett, and Michael I. Jordan. Underdamped Langevin MCMC: non-asymptotic analysis. In Proceedings of the 3 Annual Conference Learning Theory (COLT volume 75, pages 1-24, Stockholm, Sweden, 2018.

---

[19] Sinho Chewi, Thibaut Le Gouic, Chen Lu, Tyler Maunu, Philippe Rigollet, and Austin Stromme. Exponential ergodicity of mirror-Lagevin diffusions. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurIPS 2020), Online, 2020. 1, 18, 20
[20] Sinho Chewi, Thibaut Le Gouic, Chen Lu, Tyler Maunu, and Philippe Rigollet. SVGD as kernelized Wasserstein gradient flow of the chi-squared divergence. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurIPS 2020), pages 2020. 3, 4, 23, 24, 25
[21] Kacper Chwialkowski, Heiko Strathmann, and Arthur Gretton. A Kernel Test of Goodness of Fit. In Proceedings of the 33rd International Conference on Machine Learning (ICML 2016),
New York, NY, 2016. 26
[22] Ashok Cutkosky and Francesco Orabona. Black-Box Reductions for Parameter-free Online Learning in Banach Spaces. In Proceedings of the 31st Annual Conference on Learning Theory (COLT 2018), Stockholm, Sweden, 2018.
[23] Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and log- concave densities. Journal of the Royal Statistical Society. Series B (Statistical Methodology). 79(3):651-61) 2017.7 7
[24] Arnak S Dalalyan and Avetik Karagulyan. User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient. Stochastic Processes and their Applications, 129(12):527-- 5311, 2019. 7
[25] Armak S Dalalyan and Lionel Riou-Durand. On sampling from a log-concave density using kinetic Langevin diffusions. Bernoulli, 26(3):1956-1988, 2020. 7
[26] Nabarun Deb, Boung-Heon, Kim, Soumik Pal, and Geoffrey Schiebinger. Wasserstein Mirror Gradient Flow as the Limit of the Sinkhorn Algorithm. arXiv preprini (tti:2307.11422)
2023. 18
[27] Gianluca Detommaso, Tiangang Cui, Alessio Spantini, Youssef Marzouk, and Robert Scheichl. A Stein variational Newton method. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NIPS 2018), Montreal, Canada, 2018.
[28) Persi Diaconis, Susan Holmes, and Mehrdad Shahshahani. Sampling from manifold. Ad- vances in modern statistical theory and applications: a Festschrifi in honor of Morris I. Eaton, 10: 10:102-122 125, 2013. 7
[29] Zhiyan Ding, Qin Li, Jianfeng Lu, and Stephen J. Wright. Random Coordinate Langevin Monte Carlo. In Proceedings of the 34th Annual Conference on Learning Theory (COLT 2021), volume 134, pages 1-28, Boulder, CO, 2021. 7
[30] Zhiyan Ding, Qin Li, Jianfeng Lu, and Stephen J. Wright. Random Coordinate Underdamped Langevin Monte Carlo. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021), San Diego, CA, 2021. 7
[31] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(11)212,, 2011.
6, 30
[32] Andrew Duncan, Nikolas Nüsken, and Lukasz Szpruch. On the geometry of Stein variational gradient descent. Journal of Machine Learning Research. 24:1-40, 2023. 7, 22
[33] Alain Durmus, Szymon Majewski, and Blazej Miasojedow. Analysis of Langevin Monte Carlo via Convex Optimization. Journal of Machine Learning Research, 20(1):2666-277 27111, 2019.
[34] Alain Durmus and Éric Moulines. High-dimensional Bayesian inference via the unadjusted Langevin algorithm. Bernoulli, 25(4A):2854 288-228542888,, 2019. 7
[35] Murat A. Erdogdu and Rasa Hosseinzadeh. On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness. In Proceedings of the 34th Annual Conference on Learning Theory (COLT 2021), Boulder, CO, 2021. 21
12

---

[36] Damien Garreau, Wittawat Jitkrittum, and Motonobu Kanagawa. Large sample analysis of the median heuristic. arXiv preprint arXiv:1707.0726% 2017. 30
[37] Chengyue Gong, Xingchao Liu, and Qiang Liu. Bi-objective trade-off with dynamic barrier gradient descent. In Proceedings of the 35th International Conference on Neural Information Processing Systems (NeurIPS 2021), Online, 2021.
[38] Jackson Gorham and Lester Mackey, Measuring Sample Quality with Kernels. In Proceedings of the 34th International Conference on Machine Learning (ICML 2017), Sydney, Australia, 2017. 26,3 30
[39] T H Gronwall. Note on the Derivatives with Respect Parameter of the Solutions of System of Differential Equations. Annals of Mathematics, 20(4))292-296, 1919. 20
[40] Richard Grumitt, Biwei Dai, and Uros Seljak. Deterministic Langevin Monte Carlo with Nor- malizing Flows for Bayesian Inference. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NeurIPS 2022), New Orleans, LA, 2022. 3, 21
[41] Matthew D. Hoffman, David M. Blei, Chong Wang. and John Paisley, Stochastic variational inference. Journal of Machine Learning Research, 14(1):1303 -3477337,,77 2013. 1
[42] Matthew D Hoffman and Andrew Gelman. The No-U-Turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo. Journal of Machine Learning Research, 15(1):1593-1633 2014. 3,
[43] Ya-Ping Hsieh, Ali Kavis, Paul Rolland, and Volkan Cevher. Mirrored Langevin Dynamics. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NIPS 2018), Montreal, Canada, 2018. 1, 2, 3, 4. 7, 17, 18, 20, 21, 23, 25, 28
[44] Qijia Jiang. Mirror Langevin Monte Carlo: the Case Under Isoperimetry. In Proceedings of the 35th International Conference on Neural Information Processing Systems (NeurIPS 2021), Online, 2021. 1, 7, 18, 20
[45] Valen E. Johnson and James H. Albert. Ordinal Data Modeling. Springer, New York, NY, 1999. 1
[46] Richard Jordan, David Kinderlchrer. and Felix Otto. The Variational Formulation of the Fokker-Planck Equation. SIAM Journal on Mathematical Analysis, 29(1):1-17, 1998. 3, 6
[47] Ravi Kannan, László Lovász, and Miklós Simonovits. Isoperimetric problems for convex bodies and localization lemma. Discrete & Computational Geometry, 13(3):541-55, 1995. 20
[48] Diederik P. Kingma and Jimmy Ba. Adam: a method for stochastic optimisation. In Proceed- ings of the 3rd International Conference on Learning Representations (ICLR '15), pages 1-13, San Diego, CA, 2015. 6, 30
[49] John P. Klein and Melvin L. Moeschberger. Survival Analysis: Techniques for Censored and Truncated Data. Springer, New York, NY, 2003.
[50] Ron Kohavi. Scaling up the Accuracy of Naive-Bayes Classifiers: A Decision- Tree Hybrid. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, KDD'9e 96, pages 202-207. AAAI Press, 1996. 10
[51] Anna Korba, Pierre-Cynn Cyril, Fabin-Frankowski.. Szymon Majewski, and Pierre Ablin. Kernel Stein Discrepancy Descent. In Proceedings of the 38th International Conference on Machine Learning (ICML 2021), Online, 2021. 3, 4, 26, 27
[52] Anna Korba, Adil Salim, Michael Arbel, Giulia Luise, and Arthur Gretton. A AsymAsipiii Analysis for Stein Variational Gradient Descent. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada, 2020, 4, 2,22
[53] Raphail E Krichevsky and Victor Trofimov. The performance of universal encoding. IEEE Transactions on Information Theory, 27(2): 1981. 5
13

---

[54] Jason D Lee, Dennis L Sun, Yuekai Sun, and Jonathan E Taylor. Exact post-selection inference, with application to the lasso. The Annals of Statistics, 44(3):907-927, 2016. 1, 8
[55] Yin Tat Lee and Santosh S Vempala. Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation. In Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC 2018), pages 1 1115-1121, Los Angeles,CA, 2018. 7
[56] Tony Lelièvre, Mathias Rousset, and Gabriel Stoltz. Free Energy Computations. Imperial College Press, 2010. 7
[57] Tony Lelièvre, Mathias Rousset, and Gabriel Stoltz. Hybrid Monte Carlo methods for sampling probability measures on submanifolds. Numerische Mathematik, 143(2):379 4211, 2019.
[58] Tony Lelièvre and Gabriel Stoltz. Partial differential equations and stochastic methods in molecular dynamics. Acta Numerica, 25:681-880, 2016. 7
[59] Tony Lelièvre, Gabriel Stoltz, and Wei Zhang. Multiple projection Markov chain Monte Carlo algorithms on submanifolds. IMA Journal of Numerical Analysis, 43(2):737-788, 2023. 7
[60] Lingxiao Li, Qiang Liu, Anna Korba, Mikhail Yurochkin, and Justin Solomon. Sampling with Mollified Interaction Energy Descent, In Proceedings of the 1 11th International Conference on Learning Representations, Kigali, Rwanda, 2023. 1, 2, 6, 7, 10, 30, 32, 34
[61] Ruilin Li, Molei Tao, Santosh S. Vempala, and Andre Wibisono. The Mirror Langevin Algorithm Converges with Vanishing Bias. In Proceedings the the 33rd International Conference Algorithmic Learning Theory (ALT 2022), Paris, France, 2022. 1,1.8
[62] Qiang Liu, Jason D. Lee, and Michael Jordan. A Kernelized Stein Discrepancy for Goodness- of-fit Tests. In Proceedings of the 33rd International Conference on Machine Learning (ICML. 20/6), New York, NY, 2016. 26, 27
[63] Qiang Liu and Dilin Wang. Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm. In Proceedings of the 30th Conference on Neural Information Processings Systems (NIPS 2016), Barcelona, Spain, 2016. 1, 7,30
[64] Suyun Liu and Luis Nunes Vicente. Accuracy and fairness trade-offs in machine learning: stochastic multi objeitobee approach. Computational Management Science, 19(3)511-5377 2022. 10, 32
[65] Xingchao Liu, Xin T. Tong, and Qiang Liu. Sampling with Trustworthy Constraints: A Variational Gradient Framework. In Proceedings of the 35th International Conference on Neural Information Processing Systems (NeurIPS 2021), Online, 2021. 1, 10, 32
[66] Yang Liu, Prajit Ramachandran, Qiang Liu, and Jian Peng. Stein Variational Policy Gradient. In Proceedings of the Conference Uncertainty In Artificial Intelligence (UAI 2017), Sydney, Australia, 2017.
[67] Yi-An Ma, Niladri S Chatterji, Xiang Cheng, Nicolas Flammarion, Peter L. Bartlett, and Michael Jordan. Is there an analog of Nesterov acceleration for gradient- MCMC? Bernoulli, 1723):19221199, 2021.
[68] James Martin, Lucas C Wilcox, Carsten Burstedde, and Omar Ghattas. A Stochastic Newton MCMC Method for Large-Scale Statistical Inverse Problems with Application to Seismic Inversion. SIAM Journal on Scientific Computing, 3403):460-1147, 2012.
[69] Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax Pareto Fairness: A Multi Objective Perspective. In Proceedings of the 37th International Conference on Machine Learning (ICMI. 2020), Online, 2020. 10
[70] Francesco Orabona and Ashok Cutkosky. Tutorial on Parameter-Free Online Learning. In Proceedings of the 37th International Conference on Machine Learning (ICMI. 2020), Online, 2020. 5
14

---

[71] Francesco Orabona and David Pal. Coin Betting and Parameter-Free Online Learning. In Proceedings of the 30th Conference on Neural Information Processings Systems (NIPS 2016), Barcelona, Spain, 2016. 5
[72] Francesco Orabona and Tatiana Tommasi. Training Deep Networks without Learning Rates Through Coin Betting. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, 2017. 5, 29
[73] Sam Patterson and Yee Whye Teh. Stochastic gradient Riemannian Langevin dynamics on the probability simplex. In Proceedings of the 27th International Conference Neural Information Processing Systems (NIPS 2013), Lake Tahoe, NV, 2013. 7, 8, 31, 32, 33
[74] Yunchen Pu, Zhe Gan, Ricardo Henao, Chunyuan Li, Shaobo Han, and Lawrence Carin. VAE Learning via Stein Variational Gradient Descent. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, 2017. I
[75] Soo- Yon Rhee, Jonathan Taylor, Gauhar Wadhera, Asa Hen, Douglas L Brutlag, and Robert W Shafer. Genotypic predictors of human immunodeficiency virus type drug resistance. Proceedings of the National Academy of Sciences,
2006.
[76] Christian P Robert and George Casella, Monte Carlo Statistical Methods. Springer-Verlag. New York, 2 edition, 2004. 1
[77] Ralph Tyrrell Rockafellar. Convex Analysis. Princeton University Press, Princeton, NJ, 1970.
3
[78] Adil Salim, Lukang Sun, and Peter Richtárik. A Convergence Theory for SVGD in the Population Limit under Talagrand's Inequality T1. In Proceedings the 39th International Conference on Machine Learning (ICML 2022), Online, 2022. 3,7
the
[79] Amir Sepehri and Jelena Markovic. Non-reversible, tuning- and rejection-free Markov chain Monte Carlo via iterated random functions. arXiv preprint arXiv: 171000177, 2017. 8, 91
[80] Louis Sharrock, Daniel Dodd, and Christopher Nemeth. CoinEM: Tuning- Free Barticle-Based Variational Inference for Latent Variable Models. arXiv preprint arXiv:2305. 14916, 2023. 7
[81] Louis Sharrock and Christopher Nemeth. Coin Sampling: Gradient- Bayesian Inference without Learning Rates. In Proceedings of the 40th International Conference on Machine Learning (ICML 2023), Honolulu, HI, 2023. 2, 5, 6, 7, 10, 28, 29
[82] Jiaxin Shi, Chang Liu, and Lester Mackey, Sampling with Mirrored Stein Operators. In Proceedings of the 10th International Conference on Learning Representations (ICLR 2022). Online, 2022. 1, 2, 3, 4, 6, 7, 9, 21, 22, 24, 30, 31,32
[83] Jiaxin Shi and Lester Mackey. Firite-Particle Convergence Rate for Stein Variational Gradient Descent. In Proceedings of the 37th International Conference Neural Information Processing Systems (NeurIPS 2023), New Orleans, LA, 2023.
[84] Umut Simsekli, Roland Badeau, A. Taylan Cemgil, and Gaël Richard. Stochastic Quasi- Newton Langevin Monte Carlo. In Proceedings of the 33rd International Conference on Machine Learning (ICML 2016), New York, NY, 2016. 7
[85] Lukang Sun, Avetik Karagulyan, and Peter Richtarik. Convergence of Stein Variational Gradi- ent Descent under a Weaker Smoothness Condition. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023), Valencia, Spain, 2023.
7, 23
[86] Lukang Sun and Peter Richtárik. A Note on the Convergence of Mirrored Stein Variational Gradient Descent under (LOO..))-Smoothness Condition. arXiv preprint arXiv:2206.09709
2022. 1, 2, 3, 4, 7, 22, 23
[87] Gábor Székely and Maria L.. Rizzo. Energy statistics: A class of statistics based on distances.
Journal of Statistical Planning and Inference, 1239)):12991177 2013. 3.7 7
15

---

[88] Jonathan Taylor and Robert Tibshirani. Statistical learning and selective inference. Proceed- ings of the National Academy of Sciences, 1 112225):7629-7634 2015. 1,
[89] Xiaoying Tian, Nan Bi, and Jonathan Taylor. MAGIC: a general, powerful and tractable method for selective inference. arXiv preprint arXiv: 2016. 8, 31
[90] Xiaoying Tian, Snigdha Panigrahi, Jelena Markovic, Nan Bi, and Jonathan Taylor. Selective sampling after solving a convex problem. arXiv preprint 160.055699 2016. 8, 3,31
[91] Ryan Tibshirani, Rob Tibshirani, Jonatha Taylor, Joshua Loftus, Stephen Reid, and Jelena Markovic. selectiveInference: Tools for Post-Sclection Inference, 2019. 9, 34
[92] Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning. 4(2):26-31, 2012. 9, 30, 31
[93] Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer, New York, NY, 2009. 20, 24
[94] Santosh S. Vempala and Andre Wibisono. Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices. In Proceedings of the 33rd International Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada, 2019, 21
[95] Cédric Villani. Optimal Transport: Old and New. Springer- Verlag, Berlin, 2008. 23
[96] Martin Wainwright and Michael Jordan. Graphical Models, Exponential Families, and Variational Inference. Foundations and Trends in Machine Learning, 1(1 (1-2):1-305, 2008.
[97] Dilin Wang. Zhe Zeng, and Qiang Liu. Stein Variational Message Passing for Continuous Graphical Models. In Proceedings of the 35th International Conference on Machine Learning (ICML 2018), Stockholm, Sweden, 2018. 1
[98] Xiao Wang, Qi Lei, and Ioannis Panageas. Fast Convergence of Langevin Dynamics Manifold: Geodesics meet Log-Sobolev. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada, 2020.
[99] Andre Wibisono. Sampling as optimization in the space of measures: The Langevin dynamics as composite optimization problem. In Proceedings of the 31st Annual Conference on Learning Theory (COLT 2018), Stockholm, Sweden, 2018 2, 7,
[100] Andre Wibisono. Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry. arXiv preprint arXiv:1911.01469) 2019.
[101] Edwin B Wilson. Probable Inference, the Law of Succession, and Statistical Inference. Journal of the American Statistical Association, 22(155))209-212, 1927. 31
[102] Emilio Zappa, Miranda Holmes-Cerfon and Jonathan Goodman. Monte Carlo on Mani- folds: Sampling Densities and Integrating Functions. Communications on Pure and Applied Mathematics, 71 (12):2609-2677, 2018.
[103] Kelvin Shuangjian Zhang, Gabriel Peyré. Jalal Fadili, and Marcelo Pereyra. Wasserstein Control of Mirror Langevin Monte Carlo. In Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020), Graz, Austria, 2020. 1, 7, 18
[104] Ruqi Zhang, Qiang Liu, and Xin T. Tong. Sampling in Constrained Domains with Orthogonal- Space Variational Gradient Descent. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NeurIPS 2022), New Orleans, LA, 2022. 1,7
[105] Jingwei Zhuo Chang Liu, Jiaxin Shi, Jun Zhu, Ning Chen, and Bo Zhang. Message Passing Stein Variational Gradient Descent. In Proceedings of the 35th International Conference on Machine Learning (ICML 2018), Stockholm, Sweden, 2018.
16

---

A Calculus in the Wasserstein Space
We recall the following from [2, Chapter 10]. Suppose μ (2(R) and & L²()). Let F be proper and lower semi-continuous functional on P2 We say that & E (²( belongs to the Fréchet subdifferential of F at and write & E (F(()) if, for any v E P2((R),
- (g=(5(x), (x) 2)u(dr) W)(
lim inf 1-
(15)
where ti, :Rd Rd denotes the optimal transport map from l to [2, Chapter 7.1). Under mild conditions [2. Lemma 10.4.1], the subdifferential 0F is single-valued, (FF()) {Vw, and
VW,F(n) E (m) is given by
Vw, V
(F((m) (s) for jra.e x E RR
(16)
where 0F(m), Rd + R denotes the first variation of F at ja, that is, the unique function such that 8p
1 -((())))-(()))
{ OF(u)) (z){(dx).
lim +It g
JRd 0p
(17)
where Ç= 1/-144 μr and v E (2()). We will refer to F(, as the Wasserstein gradient of F at jr.
B Examples of Mirrored Wasserstein Gradient Flows
In this section, we outline several algorithms which arise as special cases of the MWGF introduced in See 3.2, namely
One Ot
+ (wen) =0 0 Pe = (V6")
(18)
where (w))20 are vector fields chosen to ensure the convergence of (n:)c2 to = (
We will assume, throughout this section, that π e and that v (VØ) म & e- The Monge-Ampert equation determines the relationship between W and V. In particular, we have [e.g.. 43]
ev = e-==e-Woeere det
e -oVe VoVe det d
(19)
Thus, the potential W(y) of the mirrored target evaluated at y = Vœ(z) can be expressed in terms of the potential (zx) of the original target evaluated at æ, as
W = V V(x + log det (xx)
(20)
B.1 Mirrored Langevin Dynamics
Suppose that F(n) (T(n)le), where, as elsewhere, v = (V # is the dual target. In addition, let ut V Vw, -Vn,F(n) In this case, it is straightforward show that [e.g. 2, Chapter 10] Vw,)()) v log (1). Thus, for this choice of (w:)roo the MWGF in (18) reads
dm
(v log
11t
O, Pe (V Th-
(21)
Substituting V Vlog
VW, and using the fact that n). V log(n)) nt this also be written as On V VW + Vm)= 0, 1t (V 4h
(22)
Øt
This PDE nothing more than the Bokkeer-Planck equation describing the evolution of the law the overdamped Langevin SDE with respect to the mirrored target x e-w To ~ Moi Ho = Vo((r)) ~ T/o and that (2r) and (yt)e2 are the solutions of
W In particular, suppose that
dy: = VW dy + 2dbb 24 = (z))
(23)
where b = ) a standard Brownian motion. Then, if we let (H4)220 and (7:)) denote the laws of (arz J220 and (ya).o, it follows that (W:)2g and (n))20 satisfy (22). This is precisely the mirrored Langevin dynamics (MLD) introduced in [43]. We remark that, using (20), the MLD in (23) can also be written as
dy: - ---(oo (VV + V log det V (zz V2db, It (v). (24)
17

---

Remark 1. It is worth distinguishing between the mirrored Langevin dynamics in (23) and the so-called mirror Langevin diffusion [e.g.. 44, Equation 2]. which refers to the solution of
dyt = -V + v2 V (xz)) dbi, 2t Vo" (yt)
(25)
These dynamics, and the corresponding Langevin algorithm or mirror Langevin Monte Carlo, were first studied in [103], and have since also been analysed in [1, 44, 61), An alternative time discretisation has also been studied in [19].
Maruyama discretisation, known as the mirror
In this case, one can show that the law (ju)e20 of the solution of the mirror Langevin diffusion in (25) satisfies the Bikker-Planckk equation [e.g., 44, App. A.2]
8p + (Jeeet) =0,
1/ [22)) - log Nr π
(26)
Ot
Recalling that V Vw,KL (LellT = V log Ue, one can view (26) special case of the so-called Wasserstein mirror flow (WMF), defined according to [e.g. 1, App. CI
x
0pe dL
+ V (wesse) = 0, U2 =
(27)
The WMF is rather different from the MWGF in (18). In particular, the WMF in (27) describes the evolution of br according to the Wasserstein tangent vector
F F(pe). where F functional minimised n, while the MWGF in (18) describes the evolution of the mirrored T == (V)) #b4r according to the tangent vector -V w.,, F(Te). where F is now a functional minimised at v = (V () # n.. We refer to for a detailed discussion of the mirror Langevin diffusion from this perspective; and [26] for more general formulation of the WMF
B.1.1 Continuous Time Results
We now study the properties of the dynamics in (23) in continuous time, starting with the dissipation of (L(H)(T) (r) and (p(l)T [T) along the MLD. These results are a natural extension of existing results in the unconstrained case to our setting.
Proposition 1. The dissipation of (-I(+))) along the MWGF in (21) is given by
d
|
log
(28)
dt
LP(P)))
Proof. Using differential calculus in the Wasserstein space and the chain rule, have that
(KTl()lle) = We: V log dt
1/t (P)))) = - v log
1/
(29)
(m)))
By [43, Theorem 2], we have that (L]l||>) = [ul[FT. To deal with the term on the RHS, first note that, using the formula for the change of variable in probability density, we have that
7イy) = s(V (w)))det "(V (w))1=
v(y) = x (Vob"
((V
(30)
Thus, in particular, if y Vo(z), then we have that
log (y) = log (Vo'(v) (v)) = log (H) (I).
(31)
Using this, and the fact that 17 (V)) we can now compute
77 V log
V v log
7
(3)
dn((y)
(32)
((x))
/ V v log
ne (x)
dd((v))HH))))
(33)
/ V v log
( (Vo(=))) dur(#)
(34)
/ V y log
(())( "dp.(x))
(35)
/ | xxxx) -vvx log [ (v) dup(v))
(36)
| - V log /4
(v) 2
(37)
[P(()))
18

---

The conclusion now follows.
Proposition 2. The dissipation of x² (-1(T) along the MWGF in (21) is given by
dx² (Je (T) -2 I
- Mr 2 LP(x)
(38)
dt
Proof. The proof is rather similar to the previous one. In this case, using the fact that Vw, Vw,x?(nllp)) = 2V 2 we have
dx (mell)))) = (-V log (w) 2V 1/1 LP(m)) = - T 2 V L2(2)
dt
We next observe, using now the fact that
[10 (xx) which follows from (30), that
x (mell)) = (et (v) -1) du(u) = / (tt (v) - (w)--) 1) (((()()))) (()V))+T)())
(39)
= / (Vo(o) 1) 2 dπ(x)) = / (#) dx(x) = (MellT).
(40)
In addition, based on a very similar argument, we have that
v 7h 2 1izeo 12(0)
/ V ( (w) du(u) /11 ( (v) (((v))+=)(()
(
(41)
/ v, (Vo(z)) 2
| dd(xx) / V A (x) dm(z))
(42)
/ ا(m) ,, U1 (w) dπ()) = |
Mc
(v)
(m)
(43)
This completes the proof.
Since the RHS of both (28) and (38) are con-iositeve, these results show that (L()) and x (pell) decrease along the MLD. As an immediate corollary, we have the following continuous time conver-
gence rate for the time-average of [[["%) Vogo (t) )1 and 1|[ ( A4 )
Proposition 3. For any 2 0, it holds that
V log ( 2
S 1/'
| log ( -
2
(L(HOll
ds <
(pe)
(P))))
(44)
Proposition 4. For any 2 0, it holds that
min
|
H4
(3( E
1
1
||
| ds <
(
(
(45)
t
Proof. These results follow straightforwardly from integration of (28) or (38) and the non-negativity of the KL or x² divergence.
To obtain stronger convergence results, we will require additional assumptions on the target measure. In the first case, we assume that the target satisfies what we will refer to mirrored logarithmic Sobolev inequality (LSI).
Proposition 5. Assume that satisfies mirrored LSI with constant X > O. In particular, for all E P2(X)), there exists X > 0 such that
V2 - log (
(T(u||=> S
(46)
2X
(2(())
Then the KL divergence converges exponentially along the MWGF in (21):
KL(pel(T) S 22x (M(LL(H
(47)
19

---

Proof. Substituting the mirrored LSI (46) into (28), we have that
dKT.(jullT) - | V log
14
S (-2AKI(()11m))
(48)
dt
12(M)
The conclusion now follows straightforwardly from Grönwall's inequality [39].
Alternatively, under the assumption that the target satisfies mirrored Poincaré inequality (PI), can obtain exponential convergence in a number of metrics.
Proposition 6. Assume that a satisfies a mirrored PI with constant K. >> 0. In particular, for all locally Lipschitz 9 E (m), there exists & >> 0 such that
1 1 LL(m)
Var, [g]
(49)
Then the total variation distance, Hellinger distance, KL divergence, and the x² divergence all converge exponentially along the MWGF in (21):
max Ilb,, Hu,,, W2 m), KT(pelT)) ( Se- =20t (wollTT) (50)
Proof. The proof proceeds similarly to above. In particular, this time substituting the mirrored PI (49) with g 1 into (38), we have
dx (x 2 -2
S --2n 2nxx 1 (xrl) L2(x)
2
dt
The result for the x2 divergence follows via an application of Grönwall's inequality, The remaining bounds follow from standard comparison inequalities [e.g.. 93, Sec. 2.4].
The assumption that satisfies the mirrored LSI in (46) or the mirrored PI in (49) is precisely equivalent to the assumption that the mirrored target v = (V)) H satisfies the classical LSI or the classical PI, respectively. The LSI holds, for example, for all strongly log-concave distributions, with constant equal to the reciprocal of the strong convexity constant of the potential [4]. The class of measures sattisfying the PI is even larger, including all strongly log-concave measures and, more generally, all log- oog-concaee measures [10, 17, 47].
Remark 2.
Remark 3. The mirrored LSI (46) and the mirrored PI in (49) are distinct from the so-called mirror LSI [44, Assumption 2] and mirror PI [19, Definition 1]. These assumptions are used in [44, Proposition 1] and [19, Theorem 1]. respectively, establish exponential convergence of the mirror Langevin diffusion [e.g., 44, Equation 2], which we recall is distinct from the mirrored Langevin diffusion in (23); see Remark 1.
Remark 4. In Propositions 5 6 above, and also in Proposition 7 below, our assumptions the target π are, in some sense, better viewed as assumptions on the mirrored target v = (Vő) # π. Indeed, by construction, the imposed assumptions
equivalent to the assumptions that the mirrored target v satisfies a LSI (Proposition 5, 7), or that the mirrored target v satisfies a PI (Proposition 6).
In some sense, it would be preferable to establish such results under more direct assumptions on the target x itself. One possibility is assume that the target strongly log-concave. this case, [43, Proof of Theorem 3] guarantees the existence of mirror map such that the mirrored target (Vo) n is also strongly log-concave. Thus, in particular, the mirrored target sutisfies a LSI and PI or, equivalently, the turget satisfies mirrored LSI and a mirrored PI, Thus, Propositions 5 - all still hold.
B.1.2 Discrete Time Results
In practice, of course, it is necessary to discretise the dynamics in (23) in time. Applying a standard Fuler- Maruyaaa discretisation to (23), or equivalently a forward-flow discretisation (21) [e.g.. 99], one arrives the mirrored Langevin algorithm (MLA) from [43], viz
Vt+1
yt AvW + V2hE,
F++1 V ()(+1)
(51)
where 0 is the step size or learning rate and where (Gr)ee are sequence of i.i.d. standard normal random variables.
20

---

Proposition 7. Suppose that satisfies the mirrored LSI with constant X >> 0. In addition, suppose that n is suirror--smmone Then, if < 7 $ .े., the iterates (z+)120 (51) satisfy
SydL2
KT( Se (ToollT) +
(52)
A
Proof. By [43, Theorem 21. and (32) (37) in the proof of Proposition 1, if πt satisfies mirrored LSI with constant À > O, then = (Vo) # a satisfies a LSI with the same constant X. In addition, by definition, if π is mirror-L-smone then is L-smooth. Thus, it follows from [94, Theorem 1] that
8ydT.²
(L(aalp) S e A (Looll)) +
(53)
Finally, using the invariance of the KL divergence under the mirror map Ve [43, Theorem 2], the result follows.
Remark 5. Using a similar approach, one can also obtain bounds on x² (pellx) under a mirrored
LSI [35, Theorem 4], and for the Renyi divergence (Pelle)) under mirrored LSI [94, Theorem 2] or a mirrored PI [94, Theorem 3).
Remark 6. One could also consider a forward Fuler discretisation of the dynamics in (21), which leads mirrored version of the so-called deterministic I Langevin Monte Carlo algorithm [40].
B.2 Mirrored Stein Variational Gradient Descent
We now turn our attention to the MSVGD dynamics given in Sec. 3.2.1, which we recall are defined by the continuity equation
On V
71 m:) 0, de === "V= (Vo") Th,
Ko ko V
log
(54)
OL
where, as previously, Ks is the kernel defined according to ka k(Vp Vo some base kernel ls X X R.
given
B.2.1 Continuous Time Results
We now study the convergence properties of the continuous-tim time MSVGD dynamics. We note that a similar set of results can also found in [82, App. H]. We provide them here to highlight the analogues with the convergence results obtained for the MLD in Sec. B.1. Proposition 8. The dissipation of the KL along the mirrored SVGD gradient flow is given by (Kee( di
-|ss [
14
log
(55)
Proof. The proof is similar to the proof of Proposition 1. In particular, using differential calculus on the Wasserstein space and the chain rule, we have
dKL(nnla dt
[v)
(wr. we. V log
- Sm. v log
2
(56)
(²(m)
H
By Theorem 2 in [43], we have that KL(n]lv) = (L(u][=). In addition, using (31), we can compute
? 2
Snakk Ao V log
(57)
= =/ ((V)"()) (/)( (V, log
(1t (7) (V), V. log (3) (0/) (n((e)d
(58)
= -/ / K(, V log
144 πT
(I)), Vy log (#) (a')) dus (z)d)))))
(59)
/ K(2, 2/ (()((())- log
( (V log
14 (a') dpe(z)dd((z))
π
Sm 0) 1 v log
M4
(60)
We say that ग -V is mirror L-soooh if y x e W is L-smooth. This holds, in particular, if W -V V log det 200 has Hessian bounded by L.
21

---

Remark 7. The quantity on the RHS of (55) is referred to in [86] as the mirrored Stein Fisher information of ls with respect to n, with mirror map Vo. This quantity represents the Stein Fisher information [32] between (Vo) # a and (Vo) # n, given the kernel kig(t-) k(V@" ()), Vo
Similar to before, straightforward consequence of this result is a continuous time convergence rate for the average of the mirrored stein discrepancy along the continuous-time MSVGD dynamics. Proposition 9. For all 2 0. it holds that
min 0se5t
S [
VVllo log
Me
1
log
U4
ds S
KL(uolIT)
t
(61)
Proof. We integrate (55), and use the non-negativity of the KL divergence.
To obtain stronger convergence guarantees, we must once again assume some additional properties on the target. Here, a natural choice is the mirrored Stein LSI, the analogue of the Stein LSI introduced in [32] in the mirrored setting; see also [82, Definition 2].
Proposition 10. Assume that satisfies the mirrored Stein LSI with constant À > 0. In particular, for all μ E P2(X), there exists X 0 such that
1 2A
(T.(4llm) S Spp
log
(62)
Then the KL divergence converges exponentially along the continuous-time MSVGD dynamics:
(L(pl|==) <e (
(63)
Proof. The result is straightforward consequence of (55) and (62). In particular, substituting (62) into (55), we have
dKT(uelTT) = =-|[spm. (
log
(4t
S (AKL(
(64)
dt
We conclude by applying Grönwall's inequality.
Remark 8. The assumption that и satisfies the mirrored Stein LSI is equivalent to the assumption that
(VØ) # π satisfies the classical Stein LSI with kernel kg. The Stein LSI is rather less well known than the classical LSI, and holds for much smaller class of targets. In particular, this condition fails hold the kernel k is regular with respect the target n, e.g., a has exponential tails and the derivatives of the kernel and the potential V grow at most polynomially [32, 52]. It remains an open problem to establish conditions for which this conditions holds.
B.2.2 Discrete Time Results
In discrete time, [86] recently established descent lemma and complexity bound for MSVGD in the population limit. For completeness, we recall one of these results here.
Theorem (Corollary 1 in [86]). Suppose that the following assumptions hold:
(1) The mirror function & X (-x, +00) is strongly K-convex.
(2) There exist B1, B3 > 0 such that for all X, k(x,x') S Bi and On, Oz, k(a, x xx- S
Bh for all [d]. [d].
(3) There exist Lu, L such that [| S La + /
(4) There exists p 2 1, Yo E IRd, and s > such that f exp [s|ly - voll2] du(y) oc.
(5) There exists p > 1. Cp > 0 such that [VW(())] < C₁ (llv) 12 1) for any y Rd
22

---

Then, provided satisfies [86, Equation 21J, then
Σ
T-1
log
1
2KL(Ho]|T)
(65)
Ty
1=
Remark 9. The results in [86] obtained by extending the proofs used to establish convergence of SVGD in [85] to the mirrored setting. In this case, essentially all of the same arguments can be applied (in the dual space), provided suitable assumptions (V6) n. The disadvantage of this approach is that the required assumptions are specified in terms of the mirrored target u, rather than the target n.
imposed the mirrored target
Following a similar approach to [43, Theorem 31, let us show how to recover this result under standard assumption
itself. Suppose replace [86, Assumption 4] by the assumption that is strongly log- oo-conaave. Under this assumption, [43, Proof of Theorem 3] guarantees the existence of mirror map such that is also strongly log-concave. By the Bakry-Emer criterion [4], it follows that the T2 inequality is satisfied by the dual target v, and thus so too is the Tj inequality. Finally, the Ti inequality is necessary and sufficient for [86, Assumption 4] by [95, Theorem 22. 22.10.. Thus, [86, Corollary I] holds whenever the target π is strongly log-concave.
B.3 Mirrored Laplacian Adjusted Wasserstein Gradient Descent
We now consider the MWGF of the chi-squared divergence; see also [20, Sec. 3] or [2, Theorem 11.2.1] the unconstrained case. Following similar steps to [20], we will then obtained mirrored version of the Laplacian Adjusted Wasserstein Gradient Descent (LAWGD) algorithm.
B.3.1 MWGF of the Chi-Squared Divergence
Suppose that F(n) (mll) with Vw, 2V interested in the following MWGF
11 Setting wt
V W; F(T)) (4), we are
dm 2V
(V
M1
m)
-0, 0, Pt (Vo) #h--
(66)
01
Similar to before, we will begin by studying the convergence properties of this MWGF in continuous time. Proposition 11. The dissipation of (L-I-T along the MWGF in (66) is given by
(KL(wellT) = 2 V dt
- Ut
'7
(67)
π LP())
Proof. The proof is essentially identical to the proof of Proposition 2, although the roles of the Lyapunov functional and the Wasserstein gradient are now reversed. In particular, we now have
dKT(mell) dt
(2V - log (")
(P()))
LP())
By Theorem 2 in [43] and (41) (43) in the proof of Proposition 2, we have that KL(n||p) =
(L(H=||z) and V (*) (B [|[ ( (B) from which the conclusion follows. O
Proposition 12. The dissipation of x2 (-1(TT along the MWGF in (66) is given by
dx² dx2lIT -4 1
Me
(68)
di
(2()))))
Proof. Similar to the last result, the proof follows very closely the proof of Proposition On this occasion, we have
dx dx²(m= (2)
(wr, 2V
(²())) = v
11
2
(69)
(z()))
Arguing in (39) (40) and (41) (43) in the proof of Proposition 2, we have that (2(ll))
(((([TT) and | [ > 2 (#) || ( from which the conclusion follows. O
23

---

Similar to before, we can also obtain exponential convergence to the target under mirrored functional inequality.
Proposition 13. Assume that satisfies mirrored PI with constant 0. In particular, for all locally Lipschitz g E (T), there exists K. >> 0 such that
1 ||
Var, [g]
(70)
I.((m)
Then the KL divergence converges exponentially along the MWGF in (66);
(L(pel(=) S KL(Holll T)e 2M
(71)
Furthermore, for 2 J. the following convergence rate holds: 2X
KI(H]]TT) - (KI(pol|T)) A 2) e -M
(72)
Proof. The proof follows closely the proof of [20, Theorem IJ. In particular, substituting the mirrored PI (70) with 1 into (67), we have that
dKL(uelIT) dt
V
22x2(mel11 - (2AKL(
(73)
(P))))
where in the final inequality have used the fact that KL(-II=) (-1(x) (e.g.. 193, Sec. 2.4]). The first bound now follows straightforwardly from Grönwall's inequality.
For the second bound, we will instead use the inequality (L((IIT)) s log (1 + x+((())))) (e.g.. 193, Sec. 2.4]), which implies that KL(-II+) - x2 Using this in (73), follows that
dt (1 (1-e (-KL((ell+)) = 22 (1 -
-KL(ull)))) (1-e-kl(uall)))
(74)
Applying Grönwall's lemma, we then have that
- (---KL(uullee) S =2-e (1 e
S ee- -2r
(75)
where in the final line we have used the elementary inequality ((x) = 1- < 1, for x 2 0.
Finally, observe that if 2 2X then (1 -e-- -KL( m)) S e-2 Se- Combining this with the fact that < 2z(x) whenever g(x) I e__,, we have that
(L(Hel(T) s 1-- 22 (1-e-Ku(ull)))) < 2e -2x
(76)
for tortz 2 Alongside the bound in (71), this completes the proof of (72).
B.3.2 Kernelised MWGF of the Chi-Squared Divergence
In [20], the authors provide an interpretation of SVGD as a kernelised WGF of the x² divergence. Similarly, interpret MSVGD as kernelised MWGF of the x² divergence; see also [82, App. H]. In particular, observe that [20, Sec. 2.3]
/ (xx,) log (a:) dz)
P ks
V log
(77)
/ k(x,
Mi r dv(x) = Pu.k. V 71
(78)
It follows that the continuous-time MSVGD dynamics in (5) (54) can equivalently be written
One
(Pr.ke (Pu.k.
1it
= 0, P = (V #
(79)
0t
Comparing (79) and (66), it is clear that, up to a factor of two, MSVGD can be interpreted as the MWGF obtained by replacing the gradient of chi-squared divergence, V 1 ). by Pu,k, V ( In
[82, App. H], the authors obtain continuous-time convergence results for this scheme, under mirrored Stein PI. Here, we proceed differently,, based the approach in [20].
24

---

B.3.3 Mirrored Laplacian Adjusted Wasserstein Gradient Descent (MLAWGD)
Following [20], suppose now that we replace Pe,k, V (?) by the vector field V Perk, (.) The new dynamics, which we refer to as the mirrored Laplacian adjusted Wasserstein gradient flow (MLAWGF), are then given by
dn - (VPu.A Th nt - 01
(VP.RR
Pr - (V6")
(80)
The dynamics in (80) can essentially be viewed as change of measure of the standard LAWGD dynamics in [20, Sec. 4], designed to converge to the dual target // (V6) #T.
Suppose, in addition, that the kernel K were chosen such that Pu.A, = - where Lu. denotes the infinitesimal generator the Langevin SDE with stationary distribution v. Thus, particular,
(xfoly) - (VW()) ff((v)) (v)
(81)
where fe Rd -> IR denotes the function fa(-) ((V given some base function f : - IR. Letting y (z)x). using (20), and then the chain rule, we can rewrite this as
(x) - [[)) [VV
Vlogdet [V* V((+)) (00
(82)
(83)
We will denote this kernel kcc, In practice, computing kzc requires computing the spectral decom- position of the operator Ly, which is challenging even the moderate dimensions. Nonetheless, following [20, Theorem 4]. for this choice of kernel can show that the MLAWGF converges exponentially fast to the target distribution, at a rate independent of the Poincaré constant.
Proposition 14. Assume that π satisfies mirrored PI with some constant > 0. In addition, suppose that E, has a discrete spectrum. Then the KL divergence converges exponentially along the MLAWGF, with rate independent of
KL(pull=)) < (KT(Hol|=) A 2)
(84)
Proof. Using standard rules for calculus on the Wasserstein space, and the integration by parts formula E, f. Vg) = Eflff Lugl [e.g., 5]. we have
dKL(Telk) dt
()) )
The 1
The dv(()) (((a)==ii - The Lew CopPue v
(m)m)
By [43, Theorem 2] and (41) (43) in the proof of Proposition 2, we have that KL (1]) = KI
and | (*) (1) 112A(0) [ o) (#) [*)) which implies that
(KT.(eellT) dt
Mt 2
= =-
--1((=-1) (2))) = -- -x2 (MellT)) S -KI(H
(85)
(x))
π
where in the final line we have once again used the fact that KL(-IIT) S (-11TT). The conclusion now follows via Grönwall's 's inequality.
To obtain an implementable algorithm, observe that the vector field in the continuity equation can be rewritten as [20]
V. (.) - Vike, (.v) /
(u)dr(v) = v Vzke,
(86)
Next, using a forward Euler discretisation in time, we arrive at
M+1 = (id- - VV--VPP..ke v
T] =
)) Tt PL+1 = (V0)
(87)
Finally, approximate the expectations in (87) with samples. In particular, after initialising Ltd. collection of particles si ~ pi for i E [N], we set v/ = Vo(ag) for i E [N), and then update
1 NONNN
14 = vi
Σ
yycke, v/). 2f41 V (v(1))
(88)
This algorithm, which we refer to as the mirrored LAWGD (MLAWGD) algorithm, is summarised in Alg. 4.
25

---

Algorithm 4 Mirrored LAWGD
input: target density n, kernel ke.,; mirror function o, particles (zr) 14, step size 7. initialise: for E [N]. V0 = ()())) for =0,.....
1 do
For E [N] f = yi - - Ey V kc v/).
For i E [ = VØ" Vo"(yi+1)
return (27))=1-
B.4 Mirrored Kernel Stein Discrepancy Descent
Finally, we consider the MWGF of the kernel Stein discrepancy (KSD) [21, 38, 62]. In so doing, we
will obtain a mirrored version of the kernel Stein diserepancy descent (KSDD) algorithm in [51].
B.4.1
MWGF of the Kernel Stein Diserepancy
We begin by defining F(n) 1.KSD3 where KSD{(1lv) is the mirrored KSD, which define as
KSD - / kussl
(89)
where lin., is the mirrored Stein kernel, defined in terms of the score 8, = V log of the mirrored target (V and the positive semi-definite kernel hgs as
kv v') = V. log ((y) Rusl, V'V log u(y') V log VV Vorki( + v V
(V ), (g v'))
(90)
and where, as before, Ko is the kernel defined according to (v. = A A(V (w). VΦ (y')). for some base kernel &o X' x X' + R. The MKSD is nothing more than the KSD between rj = (Vo) and p = TT, with respect to the kernel kg-
In this case, define the MKSD gradient flow according to
V show that Fw,) E Vzku, )) [51, Proposition 2). We thus
On. Øt
(Eyyon, 22hi (y, )mk)) 1r = (V)*)
(1))
Similar to the previous sections, we would like to study the properties of this scheme in continuous time.
Proposition 15, The dissipation of (KSD2nn (ndlv) along the MWGF in (91) is given by
d KSKDD di (n.l)) -Eg>n [|yy- Wyrki (v, x')l"
(92)
Proof. The result follows straightffrwarddy using the chain rule. particular, have
d KSD' 0
(nd (ndlv) (we, Vws 1 "MsDDSseellll (2()))
(93)
dl
--Ey'm [|Eynn (Vyrhin, (v, w')l?
(94)
Proposition 8, and Propositions 12) this dissipation result is given in terms of the mirrored densities (ni)io and the mirrored target = (Vo) nT, rather than densities (Pt)22 and the target n. The crucial difference here is that the objective functional KKDD (melv) is not equal to (pel) whereas previously it was true
Remark 10. Unlike elsewhere (i.e., Propositions
that, e.g., KL(T)P (v) = (T (x) or (nelll) ( Nonetheless, is possible to give dissipation result in terms of the target
26

---

Algorithm 5 Mirrored KSDD
input: target density n, kernel k mirror function o, particles (xr))= 14, step size 7.
initialise: for E [N]. V0 = Vo(z))) for t =0,.... T 1 do
For E [N] 3 = yi - 7 1/ No Ejz V (v..vo
For i E [ = Vo"(vi+))
return (27))
We begin by rewriting the LHS of (92). Recall that the squared KSD between and v is identical to the Stein Fisher information between P and at le.g. 62, Theorem 3.6]. This also holds for 1j = (V # 1s and v= = (V)) # in the mirrored space, and thus we have
(SD = Sukko V log ())
S log
(95)
where in the second equality we have used the result obtained in (57) (60); see the proof of Proposition 8. Thus, in particular, F(n) is equal to the mirrored Stein Fisher information, up to factor half.
We now turn our attention the RHS of (92). We would like simplify V vi o (y, v') as defined in (90). Let = V and y = Vo(x'). Using the definition of kig we have kis (V, y') = k(2,2').
Using also the chain rule, we have
Voholy. y/) = xx)) "(=)) Similarly, holds that
(96)
(Vykoly, )), Vyrko(-) 11 pu. = = ([V
- ( v2.k(, (97)
),,
Finally, due (20), we have V logv(y) Putting everything together, we thus have that
V log (()) Tg
V log det det
kv v/) (IV2 log x(x) V log det V2 x(x)]) k(I,,')
((V''(x)] log x(x) V, log det V2 ox))))
+ ([V* log T (z) V, log vo()))
(IV2 / k(z,
log V log det 22 (xx))
( (x)) VV _k( ), ( (()))))) == = (=, (V
(98)
Using (95) and (98) we thus have the following dissipation result for the mirrored Stein Fisher information in terms of the target æ.
dt 1 2 Vlog (4g)
BEaape [in, [
2E mp
(99)
B.4.2 Mirrored Kernel Stein Discrepancy Descent (MKSDD)
To obtain an implementable MKSDD algorithm, it is, of course, necessary to discretise in time and in space. In this case, following [5I], we will first discretise in space, replacing the measure r by a discrete approximation i) N
Σj=1 oy.. This yields, writing " {y y²}.
F (w = F(i)) 2N
Σ , 1
y (w = F(i)
V ( vy²).
N2
(100)
The mirrored KSDD algorithm thus takes the following form. Initialise collection of particles btd. Ltd. z ~ Ao for i [N], and set v0 = vo(zz) for i E [N]. Then, update
1
v = Vt
V V2ku.o (WL vi)
at4 Vo (oo()()))
(101)
N2
27

---

C Convergence of Mirrored Coin Wasserstein Gradient Descent
Proposition 16. Suppose that is strongly log-concave and that W1, Fun)) & L for all t e (T) In addition, suppose that (Ne), and satisfy [8I, Assumption B.1]. Then there exists mirror map & such that
T
KL
1
Σ 1=1
π
+
/ [VV((2)1 / T'n (1 96K273 | (dæ) x
T
T
+
|Vo(2)]| 'Tln (1 (1+ || (o(dd))
(102)
where K >> 0 is the constant defined in 181, Assumption B.
Proof. First note, using Jensen's inequality, and [43, Theorem 2], that
T
T
KL
T
$
T
KL ( pell
(103)
T
[K(m))p) - KI(UIKM
(104)
T
T Σ
F -(F))
(105)
where in the final line we have defined F(n) KL(n]TT) Now, under the assumption that is strongly log-concave, [43, Proof of Theorem 3] guarantees the existence of mirror map Φ X' U [oo} such that the mirrored target v = (V also strongly log-concave. follows, in particular, that F(n) == KL(nI(T) is geodesically convex [e.g.. 2, Chapter 9]. Thus, arguing as in the proof of [81, Proposition 3.3], with wo 1, follows that
T -
L +
/ Rd
- F(v)
1+
Tin 1 96A |llll v(dy) |ull
T
|llll
Tin (1
967 ||
70 (dx)
(106)
Finally, once more using the definition of the mirror map and in particular the fact that v = (VØ) T and 1/o = (V 7o. we can rewrite the RHS in (106) as the RHS in (102). This completes the proof.
D Other Mirrored Coin Sampling Algorithms
In this section, we provide some other mirrored coin sampling algorithms besides Coin MSVGD. Recall, from Sec. 4.2, the general form of the mirrored coin sampling algorithm. Let H4o (2)) and yo = Vo(zo)= E Rd. Then, for & E N, update
1= Cy. (U=)
t-1
= +
|+
Σ
(cn, (v.), Yo yo)
= Vo)(2))
(107)
where Cn, (v)) choices of F and (EN,), one obtains learning-rate free analogues of different mirrored ParVI algorithms.
-V F(n) some variant thereof. As noted in Sec. 4.2, for different
In Sec. 4.2, we provided the Coin MSVGD algorithm (Alg. 2), which corresponds to (L.-Iv) and (cn, JEN, = (-P n..kk
k. V log( 2 ))ENoo This can be viewed as the coin sampling analogue of MSVGD (Sec. 3.2. and App. B.2). We now provide two more mirrored coin sampling algorithms, which correspond to the coin sampling analogues of MLAWGD (App. B.3) and MKSDD (App. B.4).
28

---

D.1 Coin MLAWGD
Algorithm 6 Coin MLAWGD
target density x, kernel kc; mirror map @, initial particles (rr)) Po. initialise: for E [N], vo Vo(1)) for t 1,..., ,, do
input:
For [N].
E
E V yyckc, (32.1%)
1
1-1
v = v6
1-
V y kc. (Va, (u.. vo)
N
of VO" (vi).
where kc, is the mirrored LAWGD kernel defined in (81). return (11))
D.2 Coin MKSDD
Algorithm 7 Coin MKSDD
input:
target density kernel k mirror map ø, initial particles (xb) ~
initialise: for i E [N], vb Vo(z().
for / 1,...,7 T do For [N]
E
1ILLA NO E Ne (V2.0))
1-1
1/2 yo
y (Vb. v60
N2
2 Vo" (v1).
where kv. is the mirrored Stein kernel defined in (90).
return (17)
E Adaptive Coin MSVGD
In Sec. 4.1 4.2, we described a betting strategy which is valid under the assumption that the sequence of outcomes (ce (CE)EEN == (C,, (yt))eeN are bounded by one, in the sense that ||c,, (y/)l S for all t e [T] and for all E [N] [see also 81, Sec. 3.4]. In practice, this may not be the case. If, instead, ||e,, (yi)) < for some constant L, then one can simply replace c,, (yr) by its normalised version, namely 6n (Vx) = cn (v+)/L. in Alg. 2.
If, on the other hand, the constant I. is unknown in advance, then empirical estimate Li,, which is adaptively updated as the algorithm runs, following [72] and later [81, App. DJ.² We provide full details of this version of Coin MSVGD Alg. 8. One can also obtain an analogous version of Coin MIED; we omit the full details here in the interest of brevity.
coordinate-wise
Finally, when use coin sampling algorithm to perform inference for (fairness) Bayesian neural network (see Sec. 6.3), we alter the denominator the betting fraction in Alg. such that it is at least 100L;,;- Thus, the update equation in Alg. 8 (or, analogously, the update equation in the adaptive version of Coin MIED) now reads as
R
vi. vo.j + max + Ligg 100L (1
(108)
D
This modification, recommended in [72, Sec. 6), has the effect of restricting the value of the particles in the first few iterations. We should emphasise that these adaptive algorithms, which in practice we use in all experiments, are still free of any hyperparameters which need be tuned by hand.
Here, E [LV indexes the particle, and j [d] indexes the dimension (see Alg. 8).
29

---

Algorithm 8 Adaptive Coin MSVGD
input: target density n, kernel k mirror map ø, initial particles (at) 140. initialise: for E [N], vô Vo(x)); for E [N] and j E [d], Lo.j = 0. Go.j = 0, Rb. 0. for 1 to T do For [.]]
N
f6-1 (Vi-1), Mp-1
1
d-1 -P V Vlog
(compute SVGD gradient)
N
i E [[] [d].
[ = max( [i 11 (c--1)))
(update max. observed scale)
G = Gi-1ş + 1c
(update sum of abs. value of gradients) (update total reward)
R -max(R;
(c) 1.5- Vi- vo.5).0)
- Ca. (1+ Ridy.
vis = yo.s +
(update the particles)
Gi,1 + Lin
Li
For E [N]. 2f Vo)(
output: (x/)
Computational Cost. is worth noting that, in terms of computational and memory cost, the adaptive Coin MSVGD algorithm is no worse than MSVGD when the latter is paired, is common, with method such as Adagrad [31], RMSProp [92]. or Adam [48]. The computational cost per iteration is O(N2), due to the kernelised gradient. Meanwhile, in terms of memory requirements, is necessary to keep track of the maximum observed absolute value the gradients (component-wise) the sum of (eapoonettwisee)) and the total reward (component-wise This
the absolute value of the gradients similar to, e.g., Adam, which keeps track of exponential moving averages of the gradient and the (component-wise) squared gradient [48].
Additional Experimental Details
In this section, we provide additional details relevant to the experiments carried out in Sec. 6. We im- plement all methods using Python 3, PyTorch, and TensorFlow. We use the existing implementations of MSVGD and SVMD [82] and MIED [60] to run these methods. We perform all experiments using a MacBook Pro 16" (2021) laptop with Apple M1 Pro chip and 16GB RAM.
For the experiments in Sec. 6,1 and 6.2, we use the inverse multiquadric (IMQ) kernel k(r,,')== (1 [||= x' =1112//12)- due its favourable convergence control properties (e.g.. [38]).
Unless otherwise stated, the bandwidth is determined using the median heuristic [36, 63). For the experiment Sec. 6.3. following [60], we use the s-Riesz family of mollififiers {d?} with
= + 10 and = 80
F.1 Simplex Targets
For both experiments in Sec. 6.1, we initialise all methods with i.i.d samples from Dirichlet distribution and use the entropic mirror map
d
d
d
((x)
log I + (1 26 log(1 (1-
Σ I4).
(109)
Km
We run all methods for T 500 iterations using N 50 particles. In the interest of a fair comparison, we run all of the learning-rate dependent methods (MSVGD, SVMD, projected SVGD) using RMSProp [92], extension of the Adagrad algorithm [31], adapt the learning rates.
30

---

Sparse Dirichlet Posterior. We first consider the sparse Dirichlet posterior in [73], which is given by
d+1
π (x)
ta I E Entt(A),
(110)
> 0 and observations w1...., Bdd+ where is the number of observa- tions of category k. We consider the sparse regime, in which most of the ny are zero and the remaining ny are large, c.g., of order (d). In particular,
for parameters ....... Otd+1
in [82], set ag 0.1 for k E {1...., 20) and use count data nı = 90, n2 = 723 5, and n. = for j > 3. This target is used to replicate the multimodal sparse conditionals that arise in Latent Dirichlet Allocation (LDA) [9]. While this distribution is not log-concave, the dual-target strictly log-concave under the entropic mirror map.
Quadratic Target. We next consider the quadratic simplex target introduced in [1]. In this case, the target takes the form
(2)) exp
Ar
(111)
20
where E Raxd is a symmetric positive semidefinite matrix with all entries bounded in magnitude by 1. Following [82], we = 0.01 and generate A by normalising products of random matrices with i. elements drawn from Unif[-1] 1,
F.2 Confidence Intervals for Post Selection Inference
Given data (X,y)= E R2xp x R", the randomised Lasso is defined as the solution of [89, Sec. 3.1]
B arg min BERP
E 111111 ly x + (|18|II ~ B +
(112)
where X is the & penalty parameter, E R is ridge term, and E R is an auxiliary random vector drawn from some distribution G with density g. We choose G to be zero-mean independent Gaussian distribution. The scale of this distribution, and the parameter e, are both determined automatically by the randomizedLasso function in the selective weeetiieInneeeenc package. The distribution of interest has density proportional (e.g., [90, Sec. 4.2))
0( E) x o (c(3E,0) T)T xT -x + (Ég,é_E)T)
(113)
with support D ((88, sign(Bg) âg || < 1}. In all experiments, following [89], we integrate out é_ E analytically and reparameterise 3E as â C [8E]. This yields a log-concave density for [3rz], with domain given by the non-negative orthant in RJ, We then use the mirror map d
((x)
(I log Tx - xR))
(114)
1cm
Synthetic Example. We consider the simulation [79, Sec. 5.3], with n = 100 and y = 40. The design matrix X is generated from equi-correlated model. In particular, for 1, n, the rows 24
Ltd. ~ (O, )), where Σg = 8,,, + p(1 - 6t,)). with p = 0.3. We also normalise the columns y ~ (N, Ln), independent of v where denotes the empirical standard deviation of the response. We set À using the default value returned by theoretice package, multiplied by a factor of 0.7n. This adjustment reduces the L regularisation, ensuring that a reasonable subset of the p 40 features are selected.
of X to have norm 1. Mcanwhile, the response is distributed X. That is the true parameter 3 = 0. We set ε = a"
lmbdaa in
the
We run each algorithm for T = 1000 iterations. For Coin MSVGD, MSVGD, and SVMD, we use N = 50 particles, and generate Nental samples by aggregating the particles from Ntotal/ /N independent runs. For the norejection method, we generate Niotal samples by running the algorithm for Ntotal iterations after burn-in. Finally, following [82], in Fig. 3 the error bars for the actual coverage levels correspond to 95% Wilson intervals [101].
HIV-1 Drug Resistance. We use the vitro measurement of log-fold change under 3TC as the response and include mutations that appear more than 10 times in the dataset as predictors. The resulting dataset consists of n 633 cases and p = 91 predictors. In the selection stage, we apply the ran- domised Lasso, setting the regularisation parameter to the theoretical value in multiplied by a factor of n. We implement SVMD and MSVGD using RMSProp [92], with an initial learning rate of 7 = 0.01 following [82]. We implement each method for T 2000 iterations, using N 50 particles.
31

---

F.3 Fairness Bayesian Neural Network
We use train-test split of 80% / 20%, as in [60, 65]. We implement the methods in [60, 65] using their source code, using the default hyperparameters. We run all algorithms for T = 2000 iterations, and using N 50 particles. Similar to [60], we found that one of the algorithms (Control + SVGD) in [64] got stuck after initialisation, with accuracy close to 0.75 and did not improve during training. We thus omit the results for this method in Fig. 5.
G Additional Numerical Results
G.1 Simplex Targets
In Fig. 6 and Fig. 7, we provide additional results for the sparse Dirichlet posterior [73] and the quadratic simplex target [1] considered in Sec. 6.1. In particular, in Fig. 6a and Fig. 7a, we plot the energy distance to of ground truth samples either obtained i..d. (sparse Dirichlet target) or using NUTS [42] (quadratic target) versus the number of íterations for Coin MSVGD, MSVGD, SVMD, and projected versions of Coin SVGD and SVGD). Meanwhile, in Fig. 6b and Fig. 7b, compare the performance of Coin MSVGD with the performance of MSVGD, for multiple choices of the learning rate.
1.2
1.75
Coin MSVGD
(LR=1e
MSVGD (LR=5n-01)
MSVGD (LR-1e:3))
Energy Distance
1.0
1.50
MSVGD (LR=1e
MSVGD (LR= 04)
1.25
1.00
0.6
Coin MSVGD
Projected Coin SVGD
0.75
0.4
MSVGD
SVMD
0.2
Projected SVGD
0.25
0.0
0.00
100
200
300
400
500
100
200
300
400
500
Iterations
lterations
(a) All methods.
(b) Coin MSVGD MSVGD.
Figure 6: Additional results for the sparse dirichlet posterior in [73]. (a) Energy distance vs. iterations for Coin MSVGD, MSVGD, SVMD, projected Coin SVGD, and projected SVGD; and (b) energy distance vs iterations for Coin MSVGD and MSVGD, using five different learning rates.
0.6
0.35
Coin
Coin MSVGD
MSVGD (LR-1e-02)
0.30
Projected Coin SVGD
0.5
MSVGD (LR-5e-01)
MSVGD (LR-1e-03)
Energy Distance
MSVGD (LR=1e-01)
(LR=1e-04)
0.25
SVMD
0.4
0.20
Projected SVGD
0.3
0.15
0.2
0.10
0.1
0.00
0.0
100
200
300
400
500
100
200
300
400
500
Iterations
Iterations
(a) All methods.
(b) Coin MSVGD MSVGD.
Figure 7: Additional results for the quadratic simplex target in [1]. (a) Energy distance vs. iterations for Coin MSVGD, MSVGD, SVMD, projected Coin SVGD, and projected SVGD; and (b) energy distance vs iterations for Coin MSVGD and MSVGD, using five different learning rates.
As observed in Sec. 6.1, for the sparse Dirichlet posterior, Coin MSVGD converges more rapidly than MSVGD and SVMD, even for well-chosen values of the learning rate (Fig. 6). Meanwhile, for quadratic target, Coin MSVGD generally converges more rapidly than MSVGD but not as fast as SVMD [82], which leverages the log-concavity of the target in the primal space (Fig. 7). In both cases, for poorly chosen values of the learning rate, MSVGD (e.g., 7 = 5 x 10-1 in Fig. 6b and
y x 1 7 1 10 7
5x 10 in Fig. 7b) entirely fails converge to the true target.
32

---

Results for Different Numbers of Particles. In Fig. 8 and Fig. 9, we provide additional results for the two simplex targets, now varying the number of particles N. The results are similar those reported in Sec. 6.1. In particular, Coin MSVGD has comparable performance to MSVGD and SVMD with optimal learning rates, but significantly outperforms both algorithms for sub-optimal learning rates. In addition, as expected, the posterior approximation quality of Coin MSVGD, as measured by the energy distance, improves as a function of the number of particles N (Fig. 8d and Fig. 9d).
10p
12F
Energy Detrance
Coi MSVCa)
Energy Distunce 30
Coin MEVGD Pro. Coir SYGD
Cain MSVID
10"1
Pojj. Cain SVGD
20-1
10
Pojj, Goin SVGD
NSVCE
MSVGD
Enargy
HOVED
Proj. SVED
Proj.
Proj.
10"4
(a) N = 10.
(b) N 20.
(c) N = 100.
Energy Distance
Cain MSVGD
10-2
MSVGD (1R=1e001)
MSVGDO (LR=1e-02]
50
100
150
200
250
N
(d) N (10,..., 2503.
Figure 8: Additional results for the sparse Dirichlet posterior in [73]. (a) - (c) Energy distance vs learning rate, for several values of N, for Coin MSVGD, MSVGD, SVMD, projected Coin SVGD, and projected SVGD. (d) Energy distance vs N. for several different values of the learning rate, for Coin MSVGD and MSVGD. We run each algorithm for T 250 iterations.
10a
10
Energy Dedtine
Energy Distance
Listance
10-2
10
Proj, Coin SVGD
MSVCD
Prol Coir SYGO
MEVGD
10--
Coin MSVID
Proj. Cain SVGD
MSVCD
30-2
---
MSVGD
MSVED
30-4
SUND
SYND
SVMD
SV50
Proj. SWGD
10
10
10
10
10'
10
10
10
10
10
10
10
10
10
30
10
10
Learnig
Learning Rata
Leaming
(a) N 10.
(b) N 20.
(c) N 100.
Enerryy Distance
10-1
Coin MSVGD
MSVGD (LA- Se-02)
MSVGD (LR=5e-01)
MSVED (e-22e-02)
MSVGD (1R=1e01)
MSVGO (LR=1e
10:3
100
200
(d) N (10. 2503.
Figure 9: Additional results for the quadratic target in [1]. (a) - (c) Energy distance vs learning rate, for several values of N, for Coin MSVGD, MSVGD, SVMD, projected Coin SVGD, and projected SVGD. (d) Energy distance vs N, for several different values of the learning rate, for Coin MSVGD and MSVGD. We run each algorithm for T 500 iterations.
33

---

G.2
Sampling from a Uniform Distribution
In this section, we consider the task of sampling from the uniform distribution on the unit square, namely Unif[-1, 1, For MSVGD and Coin MSVGD, we once again use the entropic mirror map. We also now use the RBF kerne,, with fixed bandwidth of h 0.01. 4 For MIED and Coin MIED, following [60], we reparameterise the particles using tanh to eliminate the constraint. We show results for several choices of mollifiers, in each casing choosing the smallest which guarantees the optimisation remains stable. We initialise all methods with particles drawn i.i.d. from [ [ 0.5)². For both methods, in the interest of a fair comparison, we adapt the learning rates using RMSProp [92]. We use N 100 particles and run each experiment for T 250 iterations. We then assess the quality of the posterior approximations by computing the energy distance to a set 1000 samples drawn i.i.d. from the true target distribution.
The results for this experiment are shown in Fig. 10. Similar to our previous synthetic examples. Coin MSVGD is competitive with the optimal performance of MSVGD. Meanwhile, for sub-optimal choices of the learning rate, the coin sampling algorithm is clearly preferable. The same is also true for Coin MIED which, depending on the choice of mollifier, obtains comparable or superior performance to MIED with the optimal choice of learning rate.
10a
109
Cain MSVGD MSVGD
MIED 18 Coin MIE (8.22)
NIED (Gaussian) Con VIED (Saussian)
HED (Laplace) Coin MED (Laplace)
Energy Disrance
Erergy Distance
Energy Distancce
Energy Disrance
20-1
10-1
20-
20-1
10-1
10-2
10-
10-2
10-3
10-3
10-1
20-1
20-3 Learning Rate
Learning Rate
Learning
Learning
(a) MSVGD
(b) MIED (Riesz)
(c) MIED (Gaussian)
(d) MIED (Laplace)
10
Coin MSVGD
MSVGD
Coin MIED (Riesz)
MIED (Riesz)
Coin MIED (Laplace)
MIED (Laplace)
Energy Distance
Coin MIED (Gaussian)
MIED (Gaussian)
10-2
50
100
150
200
250
Iterations
Comparison of Methods.
Figure 10: Results for the uniform target: Unil[ |-1, 1]2. Energy distance vs learning rate after 250 iterations for (a) Coin MSVGD and MSVGD; and (b) (d) Coin MIED and MIED, for three different choices of mollifier.
G.3 Post-Selection Inference
In this section, we provide additional results for the post-selection inference examples considered again plot the coverage of the Cls obtained using Coin MSVGD, in Sec. 6.2. In Fig. 11, poreject:on eeetttiionn io algorithm in
MSVGD, SVMD, and the norej the nominal coverage the total number of samples. Now, however, we consider choices of the learning rate for MSVGD and SVMD. In particular, we now use an initial learning rate of 7 0.001 (Fig. lla- 11b) or 7 0.1 (Fig. 11c- 1ld) for RMSProp [92], rather than 7 0.01 as in Fig. 3 (see Sec. 6.2).
[91], as we vary either
sub-optimal
'In this example, the use of an adaptive kernel (e.g.. with the bandwidth chosen according to the median rule), cause the samples from MSVGD to collapse [60].
34

---

In this case, we see that the performance of both MSVGD and SVMD deteriorates. In particular, they both now obtain significantly lower coverage than Coin MSVGD. As noted in the main text, this increased coverage is of particular importance for smaller sample sizes (see Fig. 11b and Fig. 11c), and for greater nominal coverage levels (see Fig. 1la and 11c), where the standard CIs generally undercover.
1.00
1.00
0.95
Actual coverage
Actual Coverage
0.90
0.85
Coin MSVGD
Coin MSVGD
MSVGD
0.80
SVMD
0.80
SVMD
Standard
Standard
0.75
0.75
0.80
0.85
0.90
0.95
1.00
1000
1500
2000
2500
3000
Nominal coverage
Number of Samples
(a) Actual vs Nominal Coverage (? = 0.001).
(b) Coverage vs No. of Samples (7 = 0.001).
1.00
1.00
0.95
0.95
Actual coverage
Actual Coverage
0.90
0.85
Coin MSVGD
Coin MSVGD
MSVGD
MSVGD
0.80
SVMD
0.80
SVMD
Standard
Standard
0.75
0.75
0.80
0.85
0.90
0.95
1.00
1000
1500
2000
2500
3000
Nominal coverage
Number of Samples
(c) Actual vs Nominal Coverage (r = 0.1).
(d) Coverage vs No. of Samples (y = 0.1).
Figure 11: Additional coverage results for the post-selection inference. Coverage of pest-selection confidence intervals for Coin MSVGD, MSVGD, and SVMD, using sub-optimal learning rates.
Finally, in Fig. 12, perform similar experiment for the real-data example involving the HIV-1 drug resistance dataset. In particular, we compute 90% CIs for the subset of mutations selected by the randomised Lasso, using 5000 samples and the same five methods as before: 'unadjusted' (the unadjusted Cls), 'standard" (the method in selective erence), MSVGD, SVMD, and Coin MSVGD. Now, however, we use sub-optimal choices of the initial learning rate RMSProp. namely, 0.001 (Fig. 12a) and = 1.0 (Fig. 12b), compared to 0.01 in the main paper.
Similar to the synthetic example, the impact of using a sub-optimal choice of learning rate is clear. In particular, Cls obtained using MSVGD and SVMD now differ substantially from those obtained by Coin MSVGD and the standard approach. This means, in particular, that several mutations now incorrectly flagged as significant by MSVGD and SVMD (e.g., mutation P41L, P62V, P70R, or P215Y in Fig. 12b). when in reality there insufficient evidence after conditioning on the selection event.
35

---

1
Coin MSVGD
2.4
MSVGD
SVMD
2.2
Unadjusted
2.0
Standard
0.0
-0.2
P41L
P62V
P65R
P67N
P69i
P70R
P83K
P151M
P181C
P184V
P210W
P215Y
(a) y 0.001.
Coin MSVGD
MSVGD
SVMD
2.2
Unadjusted
2.0
Standard
0.4
0.2
0.0
-0.
P41L
P62V
P65R
P67N
P69i
P70R
P83K
P151M
P18IC
P184V
P210W
P215Y
(b)
1.0.
Figure 12: Additional real data results for post-selection inference. Unadjusted and post-selection confidence intervals for the mutations selected by the randomised Lasso candidates for HIV-1 drug resistance, for two sub-optimal choices of the learning rate 7.
36


Reviews:
[{"review_id": "DBi8teYAxJ", "reviewer": "Reviewer_fTFt", "summary": "The authors derive a general class of solutions to the constrained sampling problem via MWGF, which incorporates various existing constrained sampling techniques. They do this by viewing sampling in constrained domains as a mirrored optimization problem on the space of probability measures.\nThe paper presents a set of new particle-based sampling algorithms for constrained domains that are entirely learning rate free, building on the recently introduced coin sampling methodology. The efficacy of these algorithms is demonstrated on various numerical examples.", "questions": "1) Line 74: Is the assumption of \"uniquely minimized\" generally valid?\n\n2) Line 197: typo, \"using\" instead of \"sing\"\n\n3) Line 256: Why did you chose the IMQ kernel in this case?\n\n4) Figure 4: Are the legends in (b) and (c) accurate? Shouldn't the time increase?", "limitations": "The authors adequately addressed the limitations of their approach in a dedicated paragraph (see Section 7).", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Despite the availability of various efficient methods for sampling from unconstrained distributions, which have demonstrated success across numerous applications, the effectiveness of analogous techniques for constrained targets largely relies on selecting an appropriate learning rate. The findings presented in this paper demonstrate that the suggested learning-rate free algorithms achieve comparable performance to finely tuned constrained sampling methods, eliminating the need for hyperparameter tuning. Moreover, the paper thoroughly considers related research and emphasizes the originality and advantages of the proposed approach.", "weaknesses": "The authors do not address the computational complexity of their methods, which would be beneficial for comparing them with other approaches. Additionally, it is somewhat cumbersome to switch back and forth between the main body and the appendix to comprehend the results in Section 6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their positive comments and constructive feedback. We provide a point by point response to their comments below.\n\n---\n\n**Weaknesses**\n\n**The authors do not address the computational complexity...**\nThanks for this comment. We do, in fact, provide a discussion of the computational complexity of our algorithm in App. E (lines 941 - 948). To summarise, the time complexity of both Coin MSVGD and Coin MIED is $O(N^2)$ per iteration, which is identical to MSVGD and MIED. In experiments, we also found that our algorithms took essentially the same time as MSVGD and MIED. However, we acknowledge that this discussion wasn't signposted in the main body of the paper, so it was easy to miss. We will update this in the camera-ready version.\n\n**It is somewhat cumbersome to switch back and forth...** \nThanks for highlighting this. Using the additional page allowed in the camera ready version, we plan to move several Figs from the appendices to the main body of the paper, which should help to include readability. Using this additional page, we will also add additional detail wherever we have referred to results given in the appendices, ensuring as far as possible to make the description of any results in the appendices self contained.\n\n---\n**Questions** \n\n**1. Line 74: Is the assumption of \"uniquely minimized\" generally valid?**\nThis assumption is indeed valid for the dissimilarity functionals considered in this paper, as well as those considered more widely in the literature. In particular, this is true for $\\mathcal{F}(\\mu) = \\mathrm{KL}(\\mu|\\pi)$, as well as for other $f$-divergences such as the $\\chi^2$-divergence. Under mild assumptions (e.g., use of a characteristic kernel), this is also the case for other dissimilarity functionals whose Wasserstein gradient flows have been studied in the literature, including the MMD [1] and the KSD [2]. We refer to, e.g., Theorem 5 in [3] for (mild) assumptions under which the MMD uniquely vanishes at the $\\mu=\\pi$.\n\n**2. Line 197: typo, \"using\" instead of \"sing\".**\nThanks for spotting this typo, it has now been corrected.\n\n**3. Line 256: Why did you chose the IMQ kernel in this case?**\nWe use the IMQ kernel here due to its convergence control properties. In particular, the IMQ kernel is known to metrize weak convergence [4, Theorem 8]. While this was previously mentioned in the appendix on 'Additional Numerical Details' (App. F), we will make sure to also mention this in the main text.\n\n**4. Fig. 4: Are the legends in (b) and (c) accurate? Shouldn't the time increase?**\nThe legends in Fig. 4(b) and 4(c) are, indeed, accurate. It is worth noting that $t$ denotes the value of the fairness constraint here, rather than the time. We follow the standard notation here, see, e.g., [5], although we acknowledge that this notation may be slightly confusing. We have now added an additional remark in the caption to clarify the meaning of $t$.\n\n---\n\n**References**\n\n[1] Michael Arbel et al. Maximum Mean Discrepancy Gradient Flow. NeurIPS 2019. \n \n[2] Anna Korba et al. Kernel Stein Discrepancy Descent. ICML 2021.\n\n[3] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Scholkopf, Alexander Smola. A Kernel Two-Sample Test. JMLR, 13, 2012.\n\n[4] Jackson Gorham and Lester Mackey. Measuring sample quality with kernels. ICML 2017.\n    \n[5] Lingxiao Li, Qiang Liu, Anna Korba, Mikhail Yurochkin, and Justin Solomon. Sampling with Mollified Interaction Energy Descent. ICLR 2023."}, {"review_id": "o9nGZ2HnOA", "reviewer": "Reviewer_Uc6g", "summary": "The problem of sampling from unnormalised probability distributions is of central importance to computational statistics and machine learning. The well-known SVGD method appears to break down when applied to constrained targets. Other recent methods share the same limitation, namely, significantly depend on a suitable choice of learning rate.\n\nHence, this paper mainly focus on constrained sampling algorithms. The authors propose a suite of particle-based algorithms (coin MSVGD, coin MIED), which are entirely learning rate free. \n\nDetailed theoretical description and justification are provided in the paper. Several numerical experiments (simplex targets, post selection inference, and fairness bayesian neural network) are also conducted to evaluate the performance of proposed methods, superior or competitive results are obtained when compared to other methods.\n", "questions": "I have the some minor questions/comments for the authors:\n\n1. In the result of Section 6.1 (Figure 1), although MSVGD and SVMD are sensitive to learning rate, SVMD seems to converge at lower energy distance when using a proper learning rate (eg. 1e-1). I wonder the reason of this phenomenon, and is there any solutions to achieve similar performance for Coin MSVGD?\n\n2. Also in Figure 1, when learning rate is higher than 1e-3, Projected SVGD is also learning rate free, so does Coin MSVGD has any other advantage over it?\n\n3. The presentation of Figure 3 is not clear and straight enough to compare the result difference of the four methods. \n\n4. Move some method background and detailed algorithm description to Appendix and add more result analysis in the main paper.\n\n5. The proposed method is based on [76] and [56], it would be better to describe the connection and difference more clearly in the paper.\n\n6. First sentence of second paragraph in Introduction: 'While such methods have enjoyed great success in sampling from unconstrained distributions, they typically break down when applied to constrained targets', may needs a reference.", "limitations": "The authors have highlighted two limitations of their work, and the limitations are still open problems in the research domain.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea of viewing constrained sampling as a mirrored optimisation problem is interesting.\n2. A suite of learning rate free methods is provided, which will facilite researchers from different disciplines that related to sampling from unnormalised probability distributions.\n3. The paper is well written and easy to read. ", "weaknesses": "1. Analysis of the results is not enough.\n2. On the second numerical experiment, advantage of this method is marginal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their constructive feedback. We provide a detailed point by point response to their comments below. \n\n---\n**Weaknesses**\n\n**Analysis of the results is not enough.**\nThanks for this feedback. As noted in Sec 4.2 and discussed in [1], establishing the theoretical properties of coin sampling methods under standard conditions is very challenging, and remains unresolved even in the unconstrained case. This being said, we do actually discuss how to obtain a convergence rate for mirrored coin sampling in App. C, based on an extension of [1]. We also provide a detailed analysis of the convergence properties of MWGFs in continuous-time in App. B. \n\n**On the second numerical experiment...**\nWe agree that the advantage of our method in this experiment may seem marginal. We would, however, note the following. First, the optimal learning rate for, e.g., MSVGD, is not known a priori, and must therefore be tuned by hand. This comes at the cost of an additional computational expense. Second, if the learning rate for MSVGD is poorly tuned, Coin MSVGD does lead to a clear advantage (Fig. 9 in App. G.3). Third, empirically, Coin MSVGD seems to converge much faster than MSVGD (Fig. 8 in App G.3), even when using a well tuned learning rate. Although one can obtain comparable results by using a larger learning rate for MSVGD, this can lead to non-convergence (Fig. 8 in App. G.3). These points could be emphasised more clearly in the main text, which we have now addressed.\n\n---\n**Questions**\n\n**1. In the result of Sec 6.1...**\nThanks for this question. There is, indeed, a good reason why SVMD compares favourably to (Coin) MSVGD in this example, which we explain below. Before we do so, we should note that Fig. 1a and 1b were labelled in reverse in the original submission (this has now been corrected). With this said, let us consider the results for the quadratic target (Fig. 1a). In this case, the target is log-concave, while the dual target is not. In such cases, SVMD is expected to outperform (Coin) MSVGD, as it can exploit log-concavity in the primal space. This is further discussed in App. G.1. \n\nCurrently, it is unclear whether it is possible to obtain a coin sampling algorithm that can obtain comparable results in this case. While, in principle, one can write down a coin sampling analogue of SVMD, it is not evident that this is a principled approach. \n\nGenerally, coin sampling analogues of ParVI algorithms perform well when the coin sampling updates are used in place of a time-discretisation of a standard WGF. In such cases, when using a single particle, existing algorithms reduce to gradient descent w.r.t. the negative log-density of the target, and coin sampling reduces to coin betting [2]. This is essentially the framework for MSVGD and Coin MSVGD, even though the updates are taking place in the dual space. In particular, with a single particle, MSVGD and Coin MSVGD reduce to gradient descent or coin betting w.r.t. the negative log-density of the dual target.\n\nOn the other hand, it is not clear coin sampling can be used when existing algorithms correspond to a `non-standard' WGF, e.g., the Wasserstein mirror flow [3], which yields the mirror Langevin diffusion [3] and SVMD [4]. In these cases, if one uses a single particle (SVMD), or removes the noise (mirror Langevin diffusion), these algorithms reduce to a mirror flow (i.e., Riemannian gradient flow) w.r.t. the negative log-density of the (primal) target.\n\nWhile beyond the scope of this paper, we believe further study of this topic would be a very interesting avenue for future work. \n\n**2. Also in Fig. 1, when learning rate is...**\nAs noted in Sec. 6, projected SVGD is just SVGD with a Euclidean projection onto $\\mathcal{X}$ after each update. As such, projected SVGD does always depends on a learning rate, even though in this example the results for projected SVGD with LRs greater than $1\\times 10^{-3}$ may appear to be identical. In terms of other advantages of Coin MSVGD over projected SVGD in this example, we would highlight that Coin MSVGD converges to the target distribution, while projected SVGD fails to converge for any value of the learning rate.\n\n**3. The presentation of Fig. 3 is not clear...** \nThanks for raising this concern. We have now added additional remarks describing this figure in more detail, which should help to aid comparison between the various methods.\n\n**4. Move some method background...** \nThanks for this feedback. Given that coin sampling is a rather new approach, we feel it is important to include a detailed description of our methodology and algorithms in the main paper. This being said, we agree that some readers may appreciate seeing some more results on MWGFs in the main text. As such, we have now included in Sec 3.2 a much more detailed description of the convergence results in App. B. If space allows, we will also include a basic dissipation result for the MWGF (4).\n\n**5. The proposed method is based on [76] and [56]...**\nWe also agree that a more explicit delineation between our approaches and [56, 76] would be appreciated. We have therefore added additional remarks in Sections 4.2 and 4.3, clarifying the relationships between Coin MSVGD and Coin SVGD, and between Coin MIED and MIED, respectively. We have also added an additional appendix providing a more detailed overview of MIED and its relationship to other ParVI methods. \n\n**6. First sentence of second paragraph in Introduction...**\nWe have added references to [4, 5] after this sentence.\n\n---\n**References**\n\n[1] L. Sharrock et al. Coin Sampling: Gradient-Based Bayesian Inference without Learning Rates. ICML 2023.\n\n[2] F. Orabona et al. Coin Betting and Parameter-Free Online Learning. NeurIPS 2016.\n\n[3] K. Ahn et al. Efficient constrained sampling via the mirror-Langevin algorithm. NeurIPS 2021.\n\n[4] J. Shi et al. Sampling with Mirrored Stein Operators. ICLR 2022.\n\n[5] Y.P. Hsieh et al. Mirrored Langevin Dynamics. NeurIPS 2018."}, {"review_id": "HBmzICYNAF", "reviewer": "Reviewer_aGzU", "summary": "This paper studies constrained sampling with algorithms such as Langevin dynamics or stein-variation gradient. They provide a continuous based framework which can be specialised to various other algorithms as well. The proposed modification of the classical algorithms does not require a well-specified learning rate; instead by utilising a betting scheme the algorithm adjusts its learning rate to maintain a good convergence. A versatile set of numerical examples is provided to support the claim that the iterative methods above converge faster and hence are closer to true distribution than the same instances of the algorithm with badly chosen learning rates. ", "questions": "- Can you give an example for operator P from 132? \n- Are there other betting strategies which are worth mentioning? \n- Does SVMD fall into your framework too? Afaik SVMD is not only-dual algorithm like your proposed Alg. 1? If not why?\n", "limitations": "Tthe authors adequately addressed the limitations and, if applicable, potential negative societal impact of their work", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The authors focus on a problem which is often omitted in the development of approximate inference algorithms, namely the choice of learning rate. They focus on constrained settings where they work with continuous versions of mirrored langevin dynamics and stein-variational gradient. The proposed discretized variants of the algorithms. I find these problems of very big practical relevance having encountered these problems myself. \n\nAuthors provide a very compelling experimental section where they show the benefit of their betting scheme in improving the convergence rate and/or converged solution. The benchmark problems are very versatile and compare with the right baselines. \n", "weaknesses": "I am not familiar with related work, but it seems a lot of the results are standard from sampling literature with the only novelty being the coin betting which itself is inspired by convex optimization literature works. \n\nThere is no theoretical analysis and there is no conjecture even if this works or what are the conditions that this might work, but well this might be a really difficult problem. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their positive remarks, as well as their insightful feedback. We provide a detailed point by point response to their comments below. \n\n---\n**Weaknesses**\n\n**I am not familiar with related work, but it seems...**\nThanks for this remark. Although some of the results in App. B do exist in the sampling literature, we would respectfully disagree that the only novelty in this paper is the introduction of learning-rate free algorithms based on coin betting. In particular, we also introduce a general formulation of constrained sampling as a mirrored optimisation problem, and the notion of a MWGF. This provides a unifying framework for existing approaches, and allows us to obtain new constrained sampling algorithms (e.g., MKSDD, MLAWGD) and analyse their convergence. This framework also provides a principled basis from which we derive mirrored coin sampling. In any case, we would argue that introducing several new learning-rate free constrained sampling algorithms is, in itself, a significant and novel contribution, particularly given their impressive numerical performance compared to existing methods.\n\n**There is no theoretical analysis...**\nThe reviewer is correct that a theoretical analysis of coin sampling (under standard conditions) is a very difficult question, even in the unconstrained case. We include several remarks on this in Sec 4.2. It is worth emphasising that we do, in fact, provide a discussion of how to obtain a convergence rate for mirrored coin sampling, under an appropriate extension of the conditions in [1], in App. C.\n\n---\n**Questions**\n\n**1. Can you give an example for operator P...**\n We could not locate a reference to $P$ in 132. If the question refers to $P_{\\mu,k}$ in 133, then this is simply the integral operator $P_{\\mu,k}f = \\int k(x,\\cdot) f(x)\\mathrm{d}\\mu(x)$. This only differs from $S_{\\mu,k}$ in its range.\n\n\n**2. Are there other betting strategies...**\nThanks for raising this point. While, in this paper, we consider only the KT betting strategy, there are other strategies (e.g., [2]). We now include a remark pointing to this and other relevant references, leaving a more detailed investigation to future work.\n\n**3. Does SVMD fall into your framework too?...**\nThanks for raising this question. It is currently not clear that SVMD naturally fits into our framework. \n\nAs outlined in the paper, MSVGD can naturally be viewed as a kernelised version of the WGF of the KL w.r.t. the dual target in the dual space. When only a single particle is used, MSVGD reduces to gradient descent w.r.t. the negative log-density of the dual target [3]. In this sense, MSVGD can be viewed as the SVGD-analogue of the mirrored Langevin dynamics in [4]. In particular, [4] proposes running the unadjusted Langevin algorithm w.r.t. the dual target. Thus, if one removes the noise, the scheme in [4] also reduces to gradient descent w.r.t. the negative log-density of the dual target. On the other hand, we would argue that SVMD is best viewed as a kernelised approximation to the Wasserstein mirror flow w.r.t. the (primal) target [5, App. C]. In particular, with a single particle, SVMD reduces to mirror descent w.r.t. the negative log-density of the (primal) target [3, Sec 4.3]. In this sense, SVMD can be viewed as the SVGD-analogue of the mirror Langevin diffusion in [5]. Indeed, when the noise is removed in [5], this scheme also reduces to mirror descent w.r.t. the negative log-density of the (primal) target.\n\nGiven this interpretation, a natural question is then whether one can obtain a coin-sampling analogue of SVMD. In principle, one can certainly write down and implement \"Coin SVMD\". However, given that SVMD does not naturally fit into the MWGF framework, as outlined above, it is unclear that this is a particularly well-justified approach. Generally speaking, coin sampling analogues of ParVI algorithms perform well when coin sampling is used in place of a time-discretisation of a standard WGF. In such cases, when using a single particle, existing ParVI algorithms reduce to gradient descent, and coin sampling reduces to the coin betting algorithm [6], in either case w.r.t the negative log-density of the target. As outlined above, this is essentially the framework for MSVGD and Coin MSVGD, although now the updates take place in the dual space w.r.t. the dual target. In particular, if one uses a single particle, MSVGD and Coin MSVGD reduce to gradient descent or coin betting w.r.t. the negative log-density of the dual target. On the other hand, it is not clear that coin sampling can be used in cases where existing algorithms correspond to time-discretisations of `non-standard' WGFs, e.g., the Wasserstein mirror flow [5, App. C]. As noted above, in these cases, when one uses a single particle (SVMD), or removes the noise term (mirror Langevin diffusion), these algorithms reduce to mirror descent w.r.t. the negative log-density of the (primal) target. \n\nThis hypothesis is partially based on some preliminary numerical experiments. Indeed, after implementing \"Coin SVMD\", we observed numerical instabilities across various experiments. This is in contrast to Coin MSVGD, which performed consistently across experiments, and was derived in a principled way based on the MWGF framework. While beyond the scope of this work, we feel that a detailed investigation of these issues would be an interesting avenue for future work. \n\n---\n**References**\n\n[1] L. Sharrock et al. Coin Sampling: Gradient-Based Bayesian Inference without Learning Rates. ICML 2023.\n\n[2] A. Cutkosky et al. Black-Box Reductions for Parameter-free Online Learning in Banach Spaces. COLT 2018.\n\n[3] J. Shi et al. Sampling with Mirrored Stein Operators. ICLR 2022.\n\n[4] Y-P Hsieh et al. Mirrored Langevin Dynamics. NeurIPS 2018.\n\n[5] K. Ahn et al. Efficient constrained sampling via the mirror-Langevin algorithm. NeurIPS 2021.\n\n[6] F. Orabona et al. Coin Betting and Parameter-Free Online Learning. NeurIPS 2016.\n"}, {"review_id": "6Izs2wu2u8", "reviewer": "Reviewer_6R7u", "summary": "In this paper the authors first introduce a unified view of some existing sampling algorithms for constrained spaces by exploiting the notion of \"mirrored optimisation\" from standard convex optimisation in the setting of optimisation on probability spaces.  \n\nThe problem of sampling is first converted into an optimisation problem through standard arguments of Wasserstein Gradient Flows (WGF) on $\\mathbb{R}^d$: 1) consider a minimisation problem $\\pi = \\mathrm{argmin}_{\\mu} \\mathcal{F}(\\mu)$ for some functional $\\mathcal{F}$ and target probability measure $\\pi$, 2) find a continuous process which transports from some initial $\\eta_0$ to the target $\\pi$ via the continuity equation, and c) discretise the initial distribution $\\mu_0$ into some $N$ particles. which, when transported along the trajectory $\\mu_t$, produces, under suitable assumptions, samples from the target $\\pi$, as desired.  \n\nTo generalise this to possibly constrained spaces $\\mathcal{X} \\subset \\mathbb{R}^d$, the authors then introduce the *Mirrored* Wasserstein Gradient Flows (MWGF) by using the idea of a \"mirror map\" from convex optimisation. In particular, they use the mirror map to define a bijective transformation from the space of probability measures on the constrained space $\\mathcal{P}_2(\\mathcal{X})$ to probability measures on unconstrained space $\\mathcal{P}_2(\\mathbb{R}^d)$.  \n\nTo make the above construction practically useful, one needs to also discretise the resulting trajectories wrt. time, which then require a choice of stepsize. But equipped with the above view, the authors make use of previous work on \"coin sampling\", an idea which is based on \"coin optimisation\" from the convex optimisation literature, to make an explicit choice of stepsize no longer necessary, resulting in a family of particle-based learning rate free sampling methods for constrained domains.  \n", "questions": "-   As far as I can tell, every experiment is performed using a fixed number of particles ($N = 50$ for some, and $N = 100$ for others). Is this a particular choice, and if so, are there reasons for it, other than computational concerns? Though I would suspect the results to generalise, it would be comforting to see results for a few different choices of $N$.\n-   From what I can tell, previous usages of mirror maps in sampling are generally motivated by improving convergence wrt. certain sampler parameters, e.g. stepsize. Do the two algorithms which correspond to mirrored versions of Laplacian adjusted Wasserstein gradient descent and kernel Stein discrepancy descend also posses similar properties? Or is this not something that has been explored yet? (From a quick glance at the appendix, it seem the results are mainly related to continuous-time convergence.)", "limitations": "There are two main limitations with the method in its current form: a) since much of the work is based on coin sampling for unconstrained domains, this work suffers from the same ailments, i.e. theoretical results establishing convergence without somewhat strict and non-standard assumptions (which cannot be easily checked in practice) are not yet addressed, and b) any mirrored sampling algorithm requires the availability of a mirror map, and hence so does this work. These limitations are explicitly mentioned by the authors, which is appreciated.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "There are two main points of the paper that are novel:  \n\n1.  The framework of \"Mirrored Wasserstein Gradient Flows\", though not a huge step from the unconstrained \"Wasserstein Gradient Flows\", generalises a few previously seen mirrored sampling methods and allows the authors to introduce new mirrored versions of other existing methods for unconstrained spaces.\n2.  The combination of \"Mirrored Wasserstein Gradient Flows\" and \"coin sampling\", allowing the authors to obtain learning free rate particle-based sampling methods.\n\n(1) is, as far as I can tell, of greatest novelty. Even though instances of this family have previously been seen in the literature, as pointed out by the authors, putting these methods into a more general framework can lead to both improved theoretical understanding of the algorithms and new practically useful methods, the later which the authors nicely demonstrates by the generalisation of existing unconstrained methods to constrained spaces.\n\nThe authors nicely demonstrates through empirical results that the introduced methods have empirical advantages over existing methods; in particular, the learning rate free constrained methods perform similarly to their counterparts with finely tuned stepsizes. Given how sensitive some of these algorithms can be to the stepsize, this seems like a useful improvement for practical applications of these methods.\n\nThe paper is also very nice to read and not too difficult to follow. The authors also seem to have done a good job mentioning existing works.  ", "weaknesses": "One aspect that might be worth a little bit of questioning is the novelty of the work. As mentioned, the novelty comes from 1) the introduction of a framework capturing several existing mirrored sampling approaches, and 2) the application of coin sampling to the resulting framework. Having seen previous works on mirrored particle-based sampling methods in addition the work on coin sampling, neither of these might seem all too surprising.  \n\nWith that being said, the authors themselves demonstrate the utility of this formulation by the introduction of two new mirrored sampling methods, and the practical utility of (2) is clearly demonstrated in the empirical section; in total, I think this makes this work more than sufficiently novel.  \n\nAnother aspect is some lack of clarity regarding the utility of the mirror map in the introduction MWGF in Section 3. Going from the constrained WGF to the unconstrained MWGF is really only using the bijectivity property of the mirror-map $\\nabla \\phi$; that is, we could easily \"generalise\" this framework further by just replacing $\\nabla \\phi$ with *any* bijective map $\\psi: \\mathcal{X} \\to \\mathbb{R}^n$, which is commonly what is done under naive application of more classical sampling methods such as HMC to constrained problems (with the additional constraint of differentiability so the push-forward is computable).  \n\nI therefore find it somewhat non-obvious as to why the \"mirroring\" approach is preferable to what I describe above. It seems to me that previous works on mirrored sampling are generally motivated by improved convergence rates in the constrained setting as in Hsieh (2018) and Zhang (2020), which is not going to be the case for any bijective transformation. But in this work there is no mentioning of improved convergence rates of the mirrored versions introduced. I can see why the mirroring is important for the coin sampling, as the proof in Appendix C makes use of fact that the push-forward of strongly log-concave $\\pi$ under the mirror map $\\nabla \\phi$ is also strongly log-concave, but it's so clear why this is imposed already in the MWGF construction. I therefore suspect the authors has taken this less general presentation for the sake of readability, which is completely sensible, but then I'd personally appreciate a minor remark in the main text explaining this and mentioning somewhat clearly why the \"restriction\" to mirror maps is necessary for the coin sampling.  \n\nFor the empirical results, one minor weakness is that, as far as I can tell, only a single number of particles is used in each experiment, making one wonder if there is a reason for that choice, or if indeed the observed results generalise nicely for different choices of number of particles. Even though I'd expect the results to generalise, it would be nice to see a few different values for the number of parameters for each experiment rather than one.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thorough engagement with our work and their constructive feedback. We provide a detailed point by point response to their comments below.\n\n---\n**Weaknesses**\n\n**One aspect that might be worth a little bit of questioning is the novelty of the work...** \nMany thanks for these considered and thoughtful remarks. We would broadly agree that, given a close familiarity with the constrained sampling literature, as well as the recent work in [1], some of the results in this paper may not be entirely surprising. Nonetheless, as acknowledged by the reviewer, we would highlight several novel contributions.\n\nWe introduce the MWGF framework, which elegantly captures many existing constrained sampling approaches, providing a unifying framework for their analysis, as well as allowing us to derive new sampling schemes and analyse their properties. This framework also provides the basis for a principled extension of coin sampling ideas to the constrained setting, resulting in mirrored coin sampling. The result is a highly practical and easy-to-implement algorithm, which consistently obtains state-of-the-art performance. Although not based on the MWGF framework, we also introduce another learning-rate free algorithm, Coin MIED, extending ideas in [2]. Once again, this algorithm achieves excellent performance in empirical testing. \n\n**Another aspect is some lack of clarity regarding the utility of the mirror map...**\nThanks for raising this point. The reviewer is correct that, for many of the results in App. B, it would be possible to replace the mirror map by a more general bijective map, up to some minor modifications. As the reviewer suggests, our choice is largely one made out of convenience, as well as to aid comparison with existing results. In particular, adopting this formulation makes it easier to contextualise the results in App. B. For example, some of the results we obtain for mirrored LAWGD hold under identical assumptions to those previously used to analyse MSVGD [4].\n\nThis aside, we should note that the use of a mirror map does allow us to strengthen several of the results in App. B. In particular, by combining the arguments in [3, App. C], and the results in App. B, we can obtain existential results on the existence of \"good mirror maps\" which guarantee the convergence of, e.g., MSVGD or MLAWGD to the target at a particular rate, in the spirit of the result for the mirrored Langevin algorithm in [3, Theorem 3], and our own result for mirrored coin sampling [Proposition 16, App. C].\n\nAs an example, let us show how to extend [5, Theorem 1] (Theorem 1 in App. B.1) in this way. Suppose we replace [5, Assumption 4] by the assumption that $\\pi$ is strongly log-concave. Under this assumption, [3, App. C] guarantees the existence of a mirror map such that the dual target is also strongly log-concave. By the Bakry-Emery criterion, it follows that the $T_p$ inequality is satisfied by the dual target with $p=2$. Thus, [5, Assumption 4] is satisfied and so [5, Theorem 1] holds. In other words, assuming $\\pi$ is strongly log-concave, there exists a mirror map such that MSVGD converges to the target at the rate in [5, Theorem 1]. While the assumption that $\\pi$ is strongly log-concave is strictly stronger than the original assumption [5, Assumption 4], it is much more tangible, as it relates to the target $\\pi$, rather than the dual target $\\nu$.\n\nUsing similar arguments, we can also extend the other results given in App. B (e.g., Prop. 5 - 7 in App. B.1, Prop. 10 in App. B.2, Prop. 13 - 14 in App. B.3). Given this, we have now added several additional remarks in App. B, summarising how our results can be extended when restricting to a mirror map. As suggested by the reviewer, we have also added an additional remark in Sec 3.2, clarifying our use of a mirror map.\n\n**For the empirical results, one minor weakness is that...only a single number of particles...**\nThanks for this feedback. The results do generalise across different numbers of particles, but we agree it would be useful to include a comparison in the paper. We have now added an appendix comparing results for different values of $N$, across several experiments.\n\nWe include some illustrative results in the attached PDF. In Figs 1(a)-(d), 2(a)-(d), 3(a)-(d), we plot the energy distance as a function of the LR using several different numbers of particles, for the sparse Dirichlet posterior in [6] (Sec 6.1), the quadratic target in [7] (Sec 6.1), and the two-dimensional post-selection inference target [8] (Sec 6.2). In addition, in Figs 1(e), 2(e), 3(e), we plot the energy distance as a function of the number of particles, and for each of the three experiments above.  \n\n---\n**Questions**\n\n**1. As far as I can tell, every experiment is performed...**\nPlease refer to our previous response and the attached PDF.\n\n**2. From what I can tell, previous usages of mirror maps in sampling...**\nThanks for this question. Other than as outlined in our earlier response, we have not yet explored this issue as it relates to mirrored LAWGD and mirrored KSDD. As the reviewer notes, the theoretical results provided in App. B are generally restricted to the continuous time case. However, it would certainly be interesting to the discrete-time properties of these methods further. Given the considerable length of this paper, this is something we feel is best left to future work. Nonetheless, we will add a remark in Sec. 3.2 on this point.\n\n---\n**References**\n\n[1] L. Sharrock et al. Coin Sampling: Gradient-Based Bayesian Inference without Learning Rates. ICML 2023.\n\n[2] L. Li, et al. Sampling with Mollified Interaction Energy Descent. ICLR 2023.\n\n[3] Y-P Hsieh et al. Mirrored Langevin Dynamics. NeurIPS 2018.\n\n[4] J. Shi et al. Sampling with Mirrored Stein Operators. ICLR 2022.\n\n[5] L. Sun et al. A Note on the Convergence of Mirrored Stein Variational Gradient Descent under (L0,L1) Smoothness Condition. arXiv, 2022."}]

Author rebuttal:
Many thanks to all of the reviewers for their thorough engagement with our work, and for the many constructive comments. We have made several revisions to our original submission in response to the reviewers' feedback, which we feel have further improved our paper. Full details are provided in our individual responses to each of the reviewers below.

At the request of reviewer 6R7u, we have also performed some additional numerical experiments, verifying that our results generalise for different numbers of particles. We report the results of these experiments in an additional appendix in the latest revision of our paper. We also provide a sample of these results in the attached PDF.

Meta-review: This paper considers the problem of sampling in constrained spaces. Many widely-studied algorithms like Langevin dynamics require learning rates (unlike in unconstrained spaces). This paper proposes a set of particle-based methods that rely on coin betting rather than learning rates. Reviewers agreed this was an important problem and useful solution.
Decision: Accept (poster)