Mirror Langevin Monte Carlo: the Case Under Isoperimetry
Authors: Qijia Jiang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Langevin Dynamics
Mirror Descent
Discretization of SDE

Abstract: Motivated by the connection between sampling and optimization, we study a mirror descent analogue of Langevin dynamics and analyze three different discretization schemes, giving nonasymptotic convergence rate under functional inequalities such as Log-Sobolev in the corresponding metric. Compared to the Euclidean setting, the result reveals intricate relationship between the underlying geometry and the target distribution and suggests that care might need to be taken in order for the discretized algorithm to achieve vanishing bias with diminishing stepsize for sampling from potentials under weaker smoothness/convexity regularity conditions. 

Mirror Langevin Monte Carlo: the Case Under Isoperimetry
Qijia Jiang"
UT Austin
gjiangBaustin utexas.
Abstract
Motivated by the connection between sampling and optimization, we study mirror descent analogue of Langevin dynamics and analyze three different discretization schemes, giving nonasymptotic convergence rate under functional inequalities such as Log-Sobolev the corresponding metric. Compared the Euclidean setting, the result reveals intricate relationship between the underlying geometry and the target distribution and suggests that care might need to be taken in order for the discretized algorithm to achieve vanishing bias with diminishing stepsize for sampling from potentials under weaker smoothness/convexity regularity conditions.
Introduction
It has been widely recognized that optimization and sampling deeply connected. One hand, optimization can be viewed as performing sampling in the limit, and on the other, since the influential work of Miaaann-Knneeeeer-OOOOO deterministic optimization (gradient flow) in the space of probability measures. This profoundly shapes the way view and understand traditional MCMC sampling algorithms, deviating from the Markov semigroup path. While huge amount of progress has been made on the optimization front in the past few decades, its sampling counterpart, finding far-reat far-reaching applications in Bayesian statistical inference and inverse problems, hasn't t been fully explored to leverage the advancements offered by the optimization toolbox. In this paper, we draw inspiration from mirror descent [17] and ask the question if there's an analog of that can adapt to geometries beyond the Fuclidean case for Langevin diffusion, under isoperimetric inequalities such as Log-Sobolev for the target distribution. rather than Looong-Log-oo -onnCCcc,,,ty, where recall the celebrated result of Bakry and Émery ( prescribes that the latter implies the former.
122 Langevin dynamics takes the interpretation as performing
1.1 Mirror Flow and Mirror Descent
In optimization, the extension to arbitrary geometry through the choice of mirror map ó can often give better smoothness/strong convexity parameter dependence, or even handle cases where grong--onvvxityy and Lipschitz gradient of do not hold in the Euclidean geometry. The continuous limit of mirror descent can be written as
dY, dt, X, vo"
which is equivalent dYt/dt- d(Vo(x.))/dt V20(X,) -V((x, therefore the mirror flow can be recast in the primal variable as dX,, = (V -VV (fx akin to natural gradient flow, which preconditions the update adapt local geometry. Equation ① makes it clear that the mirror descent update
VΦ" (Vó(zz) h Vf(x)))))))))))))))))))))))))))) = arg min (z, vf(xx)) + hirl (z)
"Wor done while at Stanford University.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

is nothing more than the forward-discretize gradient descent in the dual y-space through mirror mapping. Here (z ((x) - V (z =xx) 2 is the Bregman divergence
and d the Fenchel conjugate of Φ. We assume that the mirror map Φ: Rd - R of Legendre
type Type and strictly convex throughout. Common choices include ((x) = | 18/2, /2, which reduces to
classical gradient descent as 21+11 = It h V ((xx), and Φ(x)
- 2; my lzg( which gives multiplicative weight update. In the special case when Φ = f' one readily recovers Newton's 's method.
1.2 Mirror Langevin Dynamics and Mirror Langevin Monte Carlo
For sampling, we consider the Mirror Langevin stochastic differential equation (SDE) where for Y = Vx((;), and target distribution π = =
dy; VV('V"
for We the standard Brownian motion in R.. If Φ is semre-times-diffeeeeee difee-differemtiabll, it is equivalent to
dX,- (-IVo [Tr (V*
Vf(xi)) dt (2[V% -'dW,
(3)
and the corresponding Fuler Fuler-Maruyama (EM) discretized version (in dual y-space) becomes
Fk+1 VΦ" (Vo(Ix) h (Fxx)) + 2h [20(+=]] Zk+1
(4)
for hx41 the stepsize and 1k+1 E Rd an independent standard Gaussian random vector, where we (xx)) No particular warm start is assumed for initialization. is worth noting that while the continuous dynamics in the primal X X-space involves the 3rd-order derivative tensor, the implementation of 4 only requires access gradient oracle for f. For ((x) | one recovers the classical (overdamped) Langevin dynamics, whose Fuler-Maruyama discretization
used V V
(Pp"(() (Yi)
is ULA: F4+11 = Ig hx+1 fx(x + 22h 2k++1- In the case when there no closed- form expression, the inversion VØ" can be solved numerically (and therefore approximately) using (z) = arg max, (2 x <(x), which is a convex optimization problem. A derivation for the cquivalence between
2 and along with the fact that 3 has π = e f as the stationary distribution
given in Appendix
evident (and reminiscent of the classical Langevin algorithm) that the discretized algorithm will converge to biased limit Th under mild regularity conditions. A Hetropolis-Hasting step can be applied on top to correct for the bias but we focus on the unadjusted case in this paper. The main question we aim address in this paper is what is the non-asymptotic rate of convergence for 22) using different discretization schemes, under functional inequalities such as Bog-Sobolev Inequality (LSI), which encompasses broader classes of distributions compared to the more restrictive and well-studied Loang---og-Concvviii (SLC) setting. particular, is known that LSII is preserved under bounded perturbation [C and Lipschitz mapping, which capture cases when f is far from convex, c.g., multi-modal such as Gaussian mixtures.
2 Related Work
Various discretizations of underdamped, overdamped Langevin dynamics in the Euclidean setting under LSI 144 23 [5] and SLC 88. [
19 [6] are the main focus of a series of developments, for which non-asymptotic error bounds are established for several metries including KL, Wasserstein and TV distance. Convergence of discretized algorithm under LSI, in general, introduces considerably more challenges, as commonly used synchronous/reflection coupling techniques do not apply.
For Langevin dynamics working under non-Eucle -on-Euciddean geometry, an earlier proposal was made in [ where algorithm was designed converge to ( being essentially change of measure from the classical Langevin dynamics. Crucially, their dynamics is different in that the diffusion term isn't scaled the one consider to take into account the Riemannian metric structure induced by d. The study of dynamics (2) was initiated in [24] under a relaxed-SLC assumption, where the authors show convergence of
Wasserstein ball with non-vanishing bias. [ studied under a similar relaxed-SLC assumption, but with a different discretization scheme as opposed to 4p.
so that V is invertible and V = (VØ)-1 -1 is single- valued mapping that makes sense for i

---

where the bias decreases to zero with diminishing stepsize. Closer to our work is [6], in which the authors investigated convergence of the continuous process 2 under functional inequalities resembling the ones we consider and focused on S. leaving the analysis of discretized algorithm for future work. In this case one does not need to resort to smoothness assumption etc. for deriving contraction/handling bias issues - it is only when studying stable discretization schemes that they become necessary (and slows down convergence from exponential to polynomial).
Recent work of 13 leverages the mean-square framework, which heavily exploits the contraction property of the dynamics, to show that under modified self cofforonceeeece property, algorithm @ in fact converges without asymptotic bias. This particular property is something we do not have here, therefore it's 's likely new ideas are needed if one were improve the analysis of 4 in this setting,
3 Notation and Assumptions
Notation We use V v(x) = = [0,(2)
E R to denote the divergence operator for a vector
8e;
field Fd Rd, and for matrix- function G : Fd - Rddd we let V G(xx e R" with the i-th element as ΣS aG(z)s, (x))) Moreover, let induced by positive definite G is defined as ||=118 = GT. Wasserstein-p distance is defined as Wplp, =) inf inpa"=/ B[[[2: x'' [P for p 2 1. From Monge-Kantorvich s duality (i #t) sup S1 Ep [p E, [f] and monotonicity property (p, л) I W2 x). bound on Wasserstein-2 metric captures many functions of potential interest. We define the pushforward measure p = Vo#P as p(B) = p V5 11 (B)) for every borel set B.
We denote the Laplacian operator as A where Aø(x) = d'G,((w) V (V G(x)) Eis dr,di E R. The norm
Oay
We state the assumptions that we will make below, some of which we will relax later. Assumption Sellf-Concordance) There exists constant Ç 2 such that the conjugate mirror map o² satisfies that Vy, u, 8,
( e] S 2 (u (u (
Moreover, this property is preserved under Fenchel conjugation (with the same parameter), affine transformation and summation (18).
Many natural barrier and entropy functions (e.g.. log-barrier) satisfy such self-concordance property.
This also guarantees solution of the continuous dynamics 2 cf. Appendix A of P41 One can show
that this invire-ntt condition implies a form of Hessian stability as M V ((x) z V²r(=') I M MV2o(r) for some M 2 1 (cf. Lemma 4) entailing that the underlying geometry isn't rapidly changing. This form of self-concordance also appears in interior point method in optimization and previous work on Mirror Langevin [1] and suggests that locally the function behaves like a quadratic.
Assumption 2 (B-MirrorLoog-Sohee Log-Sobolev.. The target distribution ा satisfies Mirror LSI with constant w. a given mirror map Φ i.e., for every locally lipschitz,uunction g, it holds that x satisfies
3 / [[
2
do 2 / g(x)) log g(x)) 2 d' -
( g(=))dd) log (fota)dds
(5)
taking g(x) = /dp(x)/dT(() one gets that for all p.
Hz(p) == / p(x) log
p(x) (xx)
dr S 1
p(x) 12
p(x)
V
log
dr =: J2(P)
(6)
2,3
(xx) [[))))))
23
This is the gradient-domination condition for KL-divergence in the Wasserstein metric, where the (weighted) Fisher information on the RHS is the squared norm of the gradient for KL divergence.
LSI is an isoperimetric inequality that implies concentration for the distribution (subgaussian tails on Lipschitz functions) and plays important role in many results in probability theory. A discussion of its implication in our context is further expanded in Section I. We note that both [ and [2] require relative p-strong convexity of ʃ w.r.t d, which means V PVL 0. Therefore this assumption based on LSI allows us to move away from convex potentials.
The following two recover the familiar smoothness and Lipschitz condition when d(z) ||x11//2.
3

---

Assumption 3 (L-Relative Lipschitz). For all x, it holds that f: R + IR is differentiable with
[V S L.
(7)
Assumption (?-Relative Smooth). For all x, E dom()).
-
S (VV1((())
(8)
One could show that 8 is slightly stronger than assuming v4f(y) (V for f(y)
f(Vo" (y)) that f(y) smooth, ie.. fly = c- (cf. Lemma 7. When d(x) = 2
condition ( reduces to f V((=')l(AAT) S y 5--1 2''l AT for which the dual norm on the two sides makes sense as a generalization, whereas one could check that the relative smoothness as defined in [24] 1 do not admit such natural interpretation. We will comment more on this assumption in later sections on discretization. Condition
also common previous works [ Assumption 5 (a-Strongly Convex), The mirror map is three-times differentiable, and let Amin (V*) 0.
All best known results under LSI [1. 2 in the Euclidean setting assume third order smoothness on (i.e., Lipschitz Hessian) and Lipschitz gradient (i.e., - 3 v² 3 T. T.. sometimes with an additional disspativity assumption 11). whereas we only require a weak notion of smoothness on o V The study of discretized sampling algorithms for non-smooth and non-convex potentials, to the best of our knowledge, is road less traversed.
4 Convergence Analysis
4.1 Continuous Time Process: Mirror LSI
One can get using LSI (and LSI alone) the exponential convergence in KI. divergence for the continuous time process, which is manifestation of convergence under Polyak-E.ojasiewicz (PL.) inequality from optimization. In optimization, steepest descent gradient flow curve E I is defined as
min (Vf(y)) 5e) + 1 2 1
Wr
which implies 1 = - ((x") and (f()) //dt = - V (v: II= from which m-gradient dominance condition on (weaker than strong convexity)
1 [f(>{)
f(vi) min f(v) S m
gives exponential convergence for the objective function f d(f(vi) miny, f(v))/dt s -m([(v]) - miny (y)). In sampling within the space of probability measures, the objective function(al) is replaced by Hn (pt), and the seminal work of [22 (see also later treatments by [2] 22 show that the density Pt E P(RR)) followed by the (overdamped) Langevin dynamics satisfies
1 +
pe: = arg min be langeni Ps
Eenpi [Vw, WWW vx (x(=))
(lle
where Vw; H (p:)
V
(xr) is the Wasserstein-2 gradient of KL divergence at Pt- aH, (H,
Opc
Therefore
dH+ Exxppt
(Hi(
= Expe || (1 (1+ log
(i T(x) )
V
(x)
dt
Op:.
The RHS becomes the negative of the Fisher information (p) therefore LSI O reduces to gradient dominance condition for KL divergence (in this case with 226 I for classical Langevin dynamics), from which one can derive exponential convergence rate to the target distribution as carried out in the optimization land sans bias. This casts Langevin diffusion as precisely gradient flow w.r.t KI. divergence in Wasserstein metric in the space of probability measures, from which LSI (weaker than SLC) suffices for convergence. We show in the lemma below that there an extension this result for Mirror-LSI that gives exponential convergence for the continuous process
where for the second step we used (H²(
+ log( Pt
Op

---

Proposition 1 (Convergence under Mirror-LSI), Along the dynamics of we have that H (p:) e-2st H (Po) under Assumption
which describes the density followed by and the integration by parts formula (V)(z), = =- f((x)V u(x)dr
Proof. Using the PDE
d
H1 (pt) = / dp:
Pt dx +
π dpt dx dl
log
di
dl
/ V
Pr. IV2 [5
V log Pt
log
Pr dx di
d
/ pide
n
- P:
V log Pt 1
[V20]-1 dx +0
S 2/- Hp()))
where we used Mirror LSI in the last step. This implies from Grönwall's inequality that H (p:) e e-28tH, H (Po).
U
For π that satisfies Mirror LSI with constant 3, thanks to the strong convexity of V > al, also satisfies Talagrand's 's inequality 21 with parameter B a, which means the Wasserstein-2 distance is upper bounded by KL divergence ad (2, )²² <. H (p) for any p. Such transportation-cost inequality has the interpretation of quadratic growth in the iterate space. Therefore Mirror LSI has the additional nice property of allowing divergence) to iterate space (that involves optimal coupling between iterates x ~ p. x ~ TT.
translate guarantee in the objective value (i.e., KL
Stability One can show that Mirror-LSI, similar to its Euclidean counterpart, is stable under bounded perturbation. Therefore if the potential function f of interest not exactly relative-smooth w.r. "nice" mirror map, it suffices for it be close to one, in the sense made precise in Appendix This is not something one can hope for with strong-con crong-convexity assumption, where perturbation from convex function usually breaks the assumption. This could be especially useful when the potential takes a composite form of f + g. where one part is smooth and the other part isn't. It is also known that operations such convolution with Gaussian (or other density that satisfy LSI) preserves LSI as well [4) which offers the option of smoothing to perform approximate sampling from a nicer proxy potential f. All these reasons make target measure satisfying Mirror-LSI appealing to study compared to the previous works 24 studying mirror Langevin for 4 -
4.2 EM-Discretized Process: Interpolation with Weighted Dynamics
For analyzing the EM discretization, we build upon the idea initiated 23 and view the discretized mirror Langevin Monte Carlo 4 as following weighted Langevin dynamics. It is clear that yk+1 = (T((+++) is the value at time = -h++1 of the stochastic process
Y Yo VS(V (Yo)) + 2 (Yo) (V))2=((Vo)))
starting from Yo yk. written in differential equation form,
dY, V (f)V)"(Y))d + (Y))
Through the mapping X, V (Yi), one study the corresponding dynamics in X-space, which evolves following a weighted I Langevin dynamics with shifted drift ja as shown in Lemma (that is responsible for convergence biased limit x² * m), i.e.,
dX. = ( G(X.) G(X)) + Ptdt+ + 22G(,)Jaw.
(10)
Lemma (Shifted Drift and Covariance). For the dynamics written in and
10 following have
G(X,) = VV
f = //164///F666044444444444777776A0 V (
5

---

Having established this, combination of Mirror LSI and careful bounding of the discretization error using colforanneee and smoothness properties can be brought together derive the per- per-iteration progress. Deatiled proofs for this section can be found in Appendix C
Proposition 2 (Progress in One Step of EM Discretization). In one iteration of Algorithm 4 with Fk ~ Po, Fk+1 ~ Ph, under Assumption
7 define D = max.,, [VVe(u) Veb(v)l2. we have for stepsize h S min(1/2 1/1662 D/ oo /ad M/63),
(Ph) S E 2 (Po) + 24M2 0 ?dh + 16M d'
where we denote M = exp(2(D//v) and n/. (1 exp(ppppp11 - (11 -[ + 2vhhd)) exp(-1/16("h) 2 We use the convention M- = when 0 and D 00.
Picking appropriate stepsize gives the following result - ppr-aps surprisingly, this particular analysis suggests that the simplest EM discretization exhibits irreducible bias, and similar observation was also made in (24] where the authors showed convergence to a Wasserstein ball with explicit radius, even for diminishing stepsize.
Theorem 1 (Convergence Guarantee for EM). Under Assumption 5 picking stepsize h S min(1/226 1/16(2d, Val, /Aod, M/63, 633 63/44MM=-21)) after k 2 ((Mar2d
iter- ations of Algorithm 4 we have for I4k ~ Pb: that H (pk) S 8 + Rg, where the nonvanishing bias In the above, D = m VV((u) Vé(v)lle and M- = exp(2(D//Vo Va).
Rg O(M² ( dl /3).
Proof. lterating the inequality in Proposition 2 for k iterations,
38 hk Hx + 24hh
16
(px) Se -
1- e 28.
1 e 281
2
15M2<2dPh
30 hk H (po) +
S e
B
8
where we used 1 - > 30/4 4 for a E 1/4] Now using Lemma for initialization, picking the
assumed stepsize, after k 2 ((M/Bh) 2 -(M*>2dd/33) iterations, we have H (px)
< 8 + Ra-
As long as V is not constant (therefore Ç ( 0, recall M 2 1), R2 := 15M <3 dl mhe
+ 0 as
h - 0 and the asymptotic bias Rg scale as (MM2 /B) since T/ + 1 as h O.
Remark. This convergence rate for KI. divergence is stronger than 24 with their guarantee in Wasserstein distance. Additionally, by Pinsker's inequality, TV distance upper bounded by KL divergence therefore one could also get analogous guarantee in that metric. Variations on the argument will likely generalize to other metrics such as x² and Rényi divergence, with other appropriate (mirror-version of) functional inequalities such Poincaré 16 20
In the case when d(x)= = |/ Theorem I ggiees no asymptotic bias, as we have M = 1 and <= O. Moreover, the assumption in this case says f is smooth in ll A although not necessarily convex, and our algorithm gives an update of the form #g+1 = 2% hx+1 (A V +
/2h ( A) 2k+1. which coincides with the classical Langevin performed on the function g( = f(A- for x = A- A-1 One could check that is smooth -7 I N V2g = ? / and satisfies the classical LSI, which means that f is globally nice w.r.t a fixed geometry, after a change of basis. If applying the Euclidean result of 200 on g()), Theorem I recover the same ((d88) complexity, which is the best-known rate without third-order smoothness assumption on f.
A closer look at the theorem points out that M plays a prominent role in the rate, where M is effectively the Hessian stability parameter (cf. Lemma 4. However, this dependence on M necessarily means that Φ needs to be smooth on its domain (and MM will be roughly the condition number of の). Although this extends beyond the Euclidean case when é needs to be constant hence allowing for clowly-changing geometry. it is still far from satisfying. An important motivation for relaxing smoothness assumption is in constrained sampling (e.g., uniform sampling from convex body), where one typically would pick 6 to be self-concordant barrier function that blows up on the boundary as proxy for the nonsmooth constraint for approximate sampling. Such functions do not have a bounded M. This, in additional to the non-vanishing bias, all suggest that EM discretization, natural as it may seem, although could improve particular parameter dependence compared to the Euclidean counterpart (as illustrated above), might not fully benefit from the use of a mirror map.

---

4.3 Alternative Forward Discretization Scheme
In practical upplications, it often the case that the cost of evaluating V is considerably cheaper than the cost of computing ff, which could involve a finite sum over large number of data points. Taking hints from this observation, in [. slightly modified mirror Langevin algorithm was considered where at iteration k; with step size 1)
Tk-1/2 = arg min 7/ ( To Do(u, = (V - f)()))
(11)
solve dy: 22 -dW, for yo Vo((Ix1122)
(12)
Th+1 VΦ" (v,)
(13)
The oracle complexity (i.e., number of queries for f.f the above algorithm is the same as the one in 4 but aiming at higher accuracy implementation for the diffusion part involving ø. The inner step can be implemented approximately using e.g., Buler-Maruyama. Integrating both sides of
is not hard to see that y/++1 Ve((<++1) is the value at time i 1 of the continuous process
Y, = Yo fXx) + v2
V (Y.) (Y)))11/d/V
(14)
given No = (V) = Fgk from the previous iteration. Written in differential form,
dy, = - VVVo + /2[V2 (Y))
(15)
Compared p the difference is in the second term where traded Yn for Y,, therefore this formu- lation amounts to discretizing the objective but not the geometry and will turn out to be crucial for re- moving the asymptotic bias. This is also in line with the observation from optimization ( from which the authors argue that di = -- V (xxx), (vx))=VVV f E1) gives a more "faithful" discretization compared to
i - V (=()) - f zj). Indeed for the process
[ one gets in the X X-space another weighted
I Langevin dynamics (T) with G 2 xxx))] and fa ( - - V (xx))). the discretization error of the gradient the local @ metric.
It turns out that this algorithm based on splitting the deterministic and stochastic part of the SDE works with a weaker notion of smoothness assumption as well. In particular, this definition of relative smoothness only involves the local metric V at single point, whereas the previous Assumption 4 requires Lipschitz gradient across different metrics V which might be unavoidable if one is discretizing the geometry as well.
Assumption (Weaker --Relative Smooth). For all x, x' E dom((). it holds that
[)) V [(<=)))( S [|V Vo(x') V
When d(x) = || Assumption reduces to [ - V (
$7.11x - a'IlATA:
and when o f always have y 1 (not the case for Assumption 4. We have the following result for the forward-discretized Mirror Langevin algorithm. Proofs for this section can be found in Appendix [
Proposition 3 (Convergence Guarantee for Forward Discretization). For the Algoritium in 1 under Assumption 5 let M exp(2CD/ v/a) and D max,,, [[Vo(u) <o(v))l
picking stepsize h S min(1/2{L, 1/1662 2d D/ Val, D2 /ad,, 1/63, 83 88/188 after Z d( 52) iterations, we have (pk)) S 5.
While it is reassuring that the algorithm has vanishing bias with diminishing stepsize for any self-concordant mirror map & (at a higher cost of computation for each step), we still see the appearance of M in the rate, which as we discussed earlier, substantially limit the use case for handling weakly smooth potentials
motivation for the introduction of a mirror map. To give a concrete example. for logistic regression, one might be interested in sampling from a posterior (0) x x(0) exp ex y:0 2; log(1 + exp(@ 2,))]. where x(0) could be a constrained prior such as uniform on foo ball [-1, 1]d. In such setting, one natural choice is to pick a mirror map which is self-concordant barrier for the constraint set to enforce the constraint on the drawn samples, e.g., (0)) = Σ, log((1 -,) ++++ + (1 + +0,) -1) with dom(() = (-1,1)d One could check that with the potential of interest as f(0) = E: -y.0" T x; + log(1 + exp(( r.)), it does not have a bounded M.
7

---

4.4 Alternative Backward Discretization Scheme
Backward discretization known be more stable compared to forward discretization in optimization and it is also known to give the best rate under LSI for Langevin diffusion in the Euclidean setting with weaker assumptions [26], albeit at a higher cost of solving a proximal step zk+1 = I'k // = arg min,, J (xx + (2n)
rxal2 compared to 2k+1 xx: v/V ( at each step.
It is relatively straightforward to see that a backward discretization for the dynamics using the same philosophy as Section 4.3 can be implemented with step size as (assuming nf + Φ is convex guaranteed 7 small enough)
solve dy: 2 (v:)) -dW, for yo- Vo(a)))
(16)
Tk+1 = arg min (1) + (bv) - yn + n/ [[((()) + Vo(()+1) -n =0
(17)
and yk++1 Vo((k+1) is the value at time 1 v of the continuous process
Y = Yo VV (Y)) v / V (Y.))
(18)
given 23 = (X) from the previous iteration. Here step T6 can again be solved iteratively using is another convex optimization for which we can implement approximately.
Euler-Maruyama and
We include the argument of this scheme in Appendix E from which we see that one gets a better rate compared to the previous crrward-discretiin bias. The crucial step, which was also used in the work of [23 is to relate the process (18) to an SDE for which the f and G only involve samples at XX, and no other time points (e.g.. Xo). contrary to what happens for EM and forward discretization. This allows us to get a tighter control on the relevant quantities for bounding the discretization error and hence better final rate (ef. Lemma 9 The difficulty for the other two schemes lies in the fact that due to the stochastic Brownian motion term, we were to bound the discretization error between two time points X, and X,, one would need a more global stability control (hence dependence on M) to account for the small probability that they are far apart (therefore local stability implied by self-concordance doesn't help). Our analysis for the algorithm works with the smoothness assumption stated below.
method (12 1/2) vs. 1)6-11) while maintaining no
Assumption 7 (Weaker y Reelative Smooth). For all x, x' E dom((), it holds that
max {
llop, [V' - -V
S K| 2'1l-
Examples abound for such assumption. We give example here where f is not smooth, yet satisfy this relative smoothness condition above. For f(x = x log(z)) (z) which does not have Lipschitz gradient, picking the strongly convex d(x) x logg(())))) (1 x)) log(1 - x) where dom( [0. 1). it's easy to see f"/ = x - / + - -) satisfy both requirements.
Below give the result for our algorithm. As alluded to earlier, this new proposal removes the M dependence altogether. It is somewhat expected that relative-smoothness type assumption would show up in the result, the lack of which necessarily implies that the potential f is "misaligned" w.r. the underlying changing geometry, for which sampling is unequivocally expected to be hard. But what's isss surprising is that this is in fact all that's 's required from 6 for our method, and ø in itself doesn't 't have to be smooth or self-concrodant in this case.
Proposition 4 (Convergence Guarantee for Backward Discretization). For the Algorithm 16-- under Assumption 2 3
$ 7 and stepsize h O(min (7,, 1 /// /53/ 122
+ o a -K(])
after ls 2 2
K2
18 1/2 33/2) iterations, we have Hz(pw) S 6.
Let us mention in passing some possible extensions to the framework presented above. In the case when we are dealing with potential with finite sum structure, i.e., f(x) = Σ, fz)), as is often the case in machine learning problems, one could execute instead of (17 the update
Tk+1 arg min 17 Σ fe(e) d(v) Vn
(19)
iEB
8

---

where B is random batch of data points. Such algorithm effectively assumes that we have stochastic (and therefore) noisy access to V f. where V f(x)= (z(x) + S for Ç an independent random noise vector with E[{] and Bilil I d Basic considerations suggest that this stochastic variant of the algorithm will converge to noise ball with radius that scales with the variance of the noise o, but nevertheless more efficient from a computational perspective.
5 Numerical Experiments
In this section, we test out the induced bias and the benefit of using mirror maps in two experiments.
For the first experiment, we take the similar setup as in 6. where we pick & ʃ (i.e. Newton) and consider uniform sampling from a 2D box [-0.01, 0.01] x [-1,1]. Four methods are compared. For Newton Langevin, we aim to target TT. X as the barrier. We test out the 3 different discretization schemes with / = 10 so that T3 = и. Stepsize is chosen to be h = 10 5 Projected Langevin is taken to be another option for dealing with constraints, which targets the uniform distribution π directly and simply performs ULA followed by projection onto the domain. The plot below shows the samples after 500 iterations, where Vo" and the proximal operator solved with 50 steps of gradient descent steps. Diffusion term é is solved with 10 inner steps of EM. From the samples, EM seems to give qualitatively different result, suggesting the possible existence of bias.
taking (0z) = log - log.))000001000
Discretize objective and geometry (EM)
Discretize objective not geometry (forward)
0.0
0.0
02-
02-
0.2
0.2
-0.01
-0.005
0.008
001
-
-0.005
0.001
0.11
Discretize objective not geometry (backward)
Projected Langevin
0.8
0.8
0.6
-0.2
-0.4
-0.4
-0.6
-0.0
0.01
-0.035
0.036
0.01
0.01
0..00
0.005
Figure 1: Uniform sampling from ill-conditioned box 0.011, 0.01] x [-1,
The second experiment concerns ill-conditioned Gaussian potential (no bias in this case), for which we compare the speed of convergence for Mirror-I Langevi (with EM discretization) vs. ULA. We 50, computing the
take Ø f (z 11) T - (x 22/2, and repeat the process 200 times with error in empirical mean [| - wll2 and covariance -|ا Σ||>/|Σ| F and plot them across iterations below. Stepsize h is picked to be 10-5 3 in both cases and initialization as ( I).
6 Discussion
Our result characterizes the interplay between and f for different discretization schemes, which can used to guide particular choice of mirror map given the sampling problem newly proposed algorithm and the analysis of several previously proposed schemes in the setting of
on hand. Our

---

Mean Iterations
Covariance Iterations
0.9
5.5
0.7
4.3
0.6
Figure 2: Newton Langevin vs. ULA for Gaussian (2i diag( ,.,,,,,,,,.. [1, ,
1D.
sampling from nonsmooth and nonconvex potentials highlight several interesting distinctions that do not find parallel in the traditional Euclidean setup.
In optimization, one typically requires quite strong assumption for global stable convergence of Newton's 's method (for which ø f). Are various tricks such Trust-Region, Cubic-Regee Regulaaizd Newton justified here as well for either speeding up sampling or correcting for bias? As future steps, it is an unfulfilled dream of ours to formalize and confirm lower bound. It is conceivable that the extra bias term is unavoidable and captures the price we have to pay for discretizing 6 while asking for weaker smoothness. It's also interesting to ask whether higher-order discretizers such as KungeeKuuttr would yield better rate. In a different vein, one could explore the possibility of higher-order dynamics (à la underdampled Langevin) for which more sophisticated integrator [T9 16 could potentially be leveraged. Conventional wisdom suggests that the introduction of auxiliary variable that handles the non-smoothness of Brownian motion often lead design of better discrete sampling algorithms. On the probability theory front, it remains an intriguing open question give complete characterization for the Mirror-LSI condition.
Acknowledgments and Disclosure of Funding
We are grateful for the constructive comments and feedback from the anonymous reviewers. This work was partially supported under NSF-2032014.
References
[1] Kwangjun Ahn and Sinho Chewi. Efficient constrained sampling via the mirror- langevn algorithm, 2020.
[2] L. Ambrosio. N. Gigli, and G. Savare. Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics. ETH Zürich. Birkhäuser Basel, 2005.
[3] Dominique Bakry and Michel Emery. Diffusions hypercontractives. Séminaire de probabilités de Strasbourg, 19:177-206, 1985.
[4] Djalil Chafai. Entropies, convexity, and functional inequalities, on ø-entropies and disobolev inequalities. Journal of Mathematics of Kyoto University J MATH KYOTO UNIV, 44, 01 2004.
[5] Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, and Michael I. Jordan. Underdamped langevin meme: A non-asymptotic analysis. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 300-323. PMLR, 06-09 Jul 2018.
[6] Sinho Chewi, Thibaut Gouic, Chen Lu, Tyler Maunu, Philippe Rigollet, and Austin Stromme. Exponential ergodicity of larror-langevin diffusions. In H. Larochelle, M. Ranzato, R. Had- sell, Balcan, and Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 19573-19585. Curran Associates, Inc., 2020.
10

---

[7] Arnak S. Dalalyan and Avetik G. Karagulyan. User-friendly guarantees for the langevin monte carlo with inaccurate gradient, 2018.
[8] Alain Durmus and Eric Moulines. High-dimensional Bayesian inference via the unadjusted Langevin algorithm. Bernoulli, 25(4A):2854 2882, 2019.
[9] Suriya Gunasekar, Blake Woodworth, and Nathan Srebro. Mirrorless mirror descent: natural derivation of mirror descent. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2005-2313. PMLR, 13-15 Apr 2021.
[10] R. Holley and D. Stroock. Logarithmic sobolev inequalities and stochastic ising models. Journal of Statistical Physics, 46:1 119-119944499 1987.
[11] Ya-Ping Hsich, Ali Kavis, Paul Rolland, and Volkan Cevher. Mirrored langevin dynamics, In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[12] Richard Jordan, David Kinderlehrer, and Felix Otto. The variational formulation of the fokker- planck equation. SIAM Journal on Mathematical Analysis, 29(1):1-17, 1998.
[13] Ruilin Li, Molei Tao, Santosh S. Vempala, and Andre Wibisono. The mirror langevin algorithm converges with vanishing bias, 2021.
[14] Yi-An Ma, Niladri S. Chatterji, Xiang Cheng, Nicolas Flammarion, Peter L. Bartlett, and Michael I. Jordan. Is there an analog of Nesterov acceleration for gradient-based MCMC? Bernoulli, 27(3): 1942 1992, 2021.
[15] Wenlong Mou, Nicolas Flammarion, Martin Wainwright, and Peter L. Bartlett. Improved bounds for discretization of langevin diffusions: Near-optimal rates without convexity, 2019.
[16] Wenlong Mou, Yi-An Ma, Martin J. Wainwright, Peter L. Bartlett, and Michael I. Jordan. High-order langevin diffusion yields an accelerated meme algorithm. Journal of Machine Learning Research, (2(42):1441 2021.
[17] A.S. Nemirovsky and D.B. Yudin. Problem complexity and method efficiency in optimization: Wiley, new york, 1983. Mathematics and Computers in Simulation, 26(1):75, 1984.
[18] Yurii Nesterov and Arkadii Nemirovskii. Interior-Poti Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, 1994.
[19] Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log-concave sampling. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[20] Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buu E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
[21] C. Villani. Optimal Transport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2016.
[22] Andre Wibisono. Sampling as optimization in the space of measures: The langevin dynamics as composite optimization problem. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31 Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 2093-3027. PMLR, 06-09 Jul 2018.
[23] Andre Wibisono. Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry. arXiv e-prints, page ArXiv:1911 (Tt.:1991.0144660 1.01469, November 2019.
[24] Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal M. Fadili, and Marcelo Pereyra. Wasserstein Control of Mirror Langevin Monte Carlo. In Proceedings of Machine Learning Research, Conference Learning Theory (COLT), volume 125, pages 1 - 28, Graz, Austria, July 2020.
11


Reviews:
[{"review_id": "lWZVdxMc7pS", "reviewer": "Reviewer_MHDF", "summary": "In this work the authors study the convergence of mirror descent langevin dynamics -- Langevin dynamics which have been transformed appropriately to satisfy certain constraints or evolve according to a specific non-euclidean geometry.   The dynamics can be characterised in various forms, including as a riemannian manifold overdamped langevin process with a specific choice of metric tensor -- but also as an SDE in the dual (unconstrained space) which is projected onto the original state space.\n\nThe paper considers the convergence to equilibrium of the mirror descent Langevin dynamics -- both for the original continuous time process, but also for various discretisations of the scheme.  This is done under the assumption of a Logarithmic Sobolev Inequality, thus generalising common convergence analysis which typically require strong-log-concavity assumptions.\n\nIt is demonstrated that the choice of discretisation plays a key role in achieving consistency under vanishing step-size for constraints which involve non-smooth contributions (e.g. constraint to lie within a box, etc), ultimately presenting a backward discretisation scheme which is far more stable to sudden changes in the geometry underlying the constraint.\n\nThese results are illustrated through a straightforward numerical example.\n\n\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found the paper generally well written, to the best of my ability in understanding the details.  The general arguments are familiar from other works, but this pulls them together to provide analysis for an important problem.  Based on this I believe the work demonstrates significance, particularly in identifying the role of the smoothness of the geometric induced by the constraint.  \n\nThe main issue I find with this work is the lack of convincing numerical examples to demonstrate this -- the single presented example is important as a toy illustrative example, but is trivial in many senses.  Perhaps one could find an opportunity to demonstrate more complex forms of constraints, e.g. e.g. constraints to simplex and another geometric constraints.  What about employing this methodology simply for accelerating unconstrained sampling using Newton-type updates based on the hessian of the objective?   These could've been addressed as  examples.\n\nMinor comments:\n\nl14: shapes\n\nl20: isoperimetric\n\nl26: continuous\n\nl35: legendre has an accent\n\nl53:'It is evident (and reminiscent of the classical Langevin algorithm) that the discretized algorithm will converge to a biased limit' --> there are many well-known examples where the EM discretisation of a Langevin SDE will not even have a long-time limit.  So without further assumptions, it's an open question whether a limit even exists, biased or not.\n\nl99: is the Hessian stability condition correct -- what are $x$ and $x'$ here?\n\nl105: What is $|| \\cdot ||_{[\\nabla^2 \\phi(x)]^{-1}}$ ?  Has this been defined?\n\nI also highlight some important works which don't appear to have been cited/considered in this work\n\nWang, Xiao, Qi Lei, and Ioannis Panageas. \"Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev.\" arXiv preprint arXiv:2010.05263 (2020) which really follows the approach of Vempala & Wibiscono 2019, \n\nLamperski, Andrew. \"Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning.\" arXiv preprint arXiv:2012.12137 (2020).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations have been adequately addressed -- societal impacts have not been mentioned, though I certainly cannot envisage any.", "review_text": "", "extra_scores": {"ethical_concerns": "no concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "c5b2emx0YMl", "reviewer": "Reviewer_dzsF", "summary": "This paper studies discretized mirror Langevin diffusions under the assumption of mirror-log Sobolev inequalities as well as relative smoothness assumptions. In particular, they show that a new backward method obtains perhaps the best dependence in terms of finite sample guarantees in this setting. On the other hand, Euler-Maruyama discretization has an irreducible bias and a different forward discretization has an exponential dependence on the diameter of the mirror set.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Upsides:\n\n+ This paper gives new upper bounds for discrete mirror Langevin dynamics.\n+ The upper bounds on these three different discretizations of mirror Langevin dynamics allow one to compare them theoretically.\n+ The work proposes a new backward discretization that has the best guarantees.  \n+ This work tackles the analysis of an important generalization of Langevin dynamics, that may hold the key to more efficient sampling algorithms.\n+ The paper is generally well written and highlights the differences in the upper bounds obtained.\n+ The assumption of weaker relative smoothness is interesting.\n\nDownsides: \n\n- The methodology and assumptions have mostly been used before, with the exception of the weaker relative smoothness and the new discretization.\n- Proposition 1 appears to be a restatement of in Chewi et al. 2020. Theorem 1. (since Poincare is weaker than log Sobolev *edit due to typo)\n - Experiments do not enlighten differences between the forward discretization of Ahn and Chewi versus the new backward discretization. For example, the difference in dependence on $M$ for the forward versus backward schemes is in terms of upper bounds rather than lower bounds, and it would be nice to see experiments that illustrate this difference. Also, it is unclear how different (12) versus (16) is in terms of hardness to solve. (*edit: this should be (11) versus (17), as the authors point out)\n- It is unclear how tight the analysis in Theorem 1 and Proposition 3 are. In particular, does Theorem 1 necessarily imply that the bias is non-vanishing? Are the bounds in Proposition 3 in some sense tight?\n- The performance of EM in Figure 1 is strange in light of Figure 3 in Chewi et al. 2020. What is the difference in implementation here?\n- The comment at the bottom of page 8 is not clear. Why is mini batching equivalent to adding Gaussian noise?\n\n(edit fixed a few typos)\n\n---\n\nAfter considering the authors' response and discussion with the other reviewers, I am raising my score to 6 and recommending acceptance based on the theoretical merit of the paper, although I do not give a higher score due to the weaker practical details.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not explicitly discussed. In particular, the analysis done is all in terms of upper bounds, which may not be optimal. Furthermore, the performance of the forward and backward schemes are not thoroughly explored in practice, and in particular, the differences in solving (12) versus (16).", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "6fXXvHkW9p0", "reviewer": "Reviewer_82Yq", "summary": "The paper under review mainly studies different discretization schemes for mirror Langevin dynamics. The main assumption is the non-asymptotic convergence/long time convergence behavior to the target invariant measure. The main feature of this type Langevin dynamic is that they have non-gradient drift and variable diffusion matrix. The author try to covey the importance of the underlying geometry which is introduced by the variable diffusion matrix. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positive.\n\n1. The logic of the paper is easy to follow, and the several discretization schemes are presented with complete derivation. \n\n2. The idea of introducing new  discretization schemes seems to be valid for more general variable diffusion Langevin dynamics. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Negative.\n\n1. The Mirror Langevin dynamics presented in this paper is a special case of a series paper for general Langevin dynamics.  e.g. [Q. Feng and W. Li] Hypoelliptic entropy dissipation for stochastic differential equations. The dynamics (3) is simply by choosing $a(X_t)=[\\nabla^2\\phi(X_t)]^{-1}$ and $\\gamma=0$ for the dynamics (1) in  [Q. Feng and W. Li].  The Fokker-Planck equation is also derived there together with the entropy decay result Proposition 1. (Note here the LSI is assumed to be true in the current paper, thus the decay of KL seems to follow naturally.)\n\n2. The assumption of the current paper claims to be weaker comparing to the existing ones [23]. The reviewer is quite curious about the verification of Assumption 2. In the aforementioned paper [Q. Feng and W. Li], the existence of the LSI for a general variable diffusion Langevin dynamic follows from the Ricci curvature lower bound. Can the author verify that Assumption 2 is indeed true for certain classes of the mirror map $\\phi$. It would very interesting to see such examples where global in time and space LSI is established for non-convex f. \n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "5sIj7-MxDPQ", "reviewer": "Reviewer_T7ux", "summary": "This paper gives a discretization analysis of the mirror-Langevin Monte Carlo algorithm, which is the analogue of mirror descent for MCMC. The prior works studying discretization of mirror-Langevin are as follows:\n\n[1] Zhang et al., who studied the Euler-Maruyama discretization. They used stochastic calculus coupling techniques in the vein of works by e.g. Dalalyan.\n\n[2] Ahn and Chewi, who introduced and studied an alternate discretization which simulates the diffusion step more faithfully. Their analysis uses Wasserstein calculus in the vein of Durmus, Majewski, and Miasojedow.\n\nA key difference between these two works is that the result of [1] has a non-vanishing bias (even with vanishing step size), whereas the discretization of [2] does not.\n\nThis paper studies both the Euler-Maruyama and Ahn-Chewi discretizations, and introduces a third one which combines the Ahn-Chewi discretization with a proximal step to obtain better guarantees. The results obtained have non-vanishing bias for the Euler-Maruyama discretization, and vanishing bias for the latter two discretizations, which is in line with previous work. The techniques are inspired by the discretization analyses of Wibisono, who is inspired by the interpretation of sampling as composite optimization in Wasserstein space. Moreover, this paper emphasizes the use of a mirror-log-Sobolev inequality as the condition ensuring rates of convergence, which allows for treating examples of non-convex potentials (which are not handled by the prior two works).\n\nThe main contributions can be summarized thus: (1) by obtaining a similar dichotomy between the bias of Euler-Maruyama vs. Ahn-Chewi, it sheds further light on the effect of discretization of the diffusion in the presence of non-isotropic diffusions; (2) it shows how to adapt a third type of discretization analysis to the mirror-Langevin setting; (3) it introduces a proximal mirror-Langevin algorithm which had previously not been considered and gives guarantees.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Evaluation: This paper is a good contribution to the sampling literature in light of the main contributions listed above. Since it is more challenging to handle the non-isotropic diffusion than the study of vanilla Langevin, understanding discretization analysis for mirror-Langevin is an important problem.\n\nMy main concern with this work is that it is not straightforward to find examples in which the mirror log-Sobolev inequality holds (besides when the mirror map is quadratic, in which case it reduces to the usual log-Sobolev inequality). For example, the usual log-Sobolev inequality is implied by strong convexity, and besides there are many identified situations where it holds (e.g. convolution of a measure with bounded support with a Gaussian). On the other hand, relative strong convexity w.r.t. a mirror map is not enough to imply a mirror LSI; for instance, as discussed in the paper of Chewi et al. on mirror-Langevin, when the mirror map equals the potential then relative strong convexity trivially holds, but a mirror LSI does not hold without further assumption on the potential/mirror map (see the reference to Bobkov-Ledoux therein). It is important therefore to find further examples in which the mirror LSI holds to assess whether this is indeed a useful assumption.\n\nSpecific Comments:\n- On pg. 3, after Assumption 2, it is claimed that the assumption of a mirror LSI is “strictly weaker” than that of relative strong convexity, but this is false as discussed above. Rather, it would be better to include somewhere in the paper a more thorough comparison of the two sets of assumptions.\n- Last display equation on pg. 4 should have \\nabla_x rather than \\nabla x.\n- On pg. 6, it is claimed that “the simplest EM discretization exhibit [sic] an irreducible bias”. It is not clear what exactly is meant by this statement: after all, Thm. 1 (as well as the prior work by Zhang et al.) merely provide upper bounds on the bias, and it is not yet proven if the EM discretization indeed exhibits bias or not.\n- On the subject of the bias of EM discretization: the O(d^2) bias is quite large. For comparison purposes, what is the size of the relative entropy at initialization under the same assumptions, for a sensible choice of initialization (e.g. Gaussian with appropriate variance)? Is it clear that this bias term O(d^2) actually constitutes an improvement over the initialization? If not, then the EM result seems almost vacuous to me.\n- Lemma 6 in the appendix is surely wrong; the relative entropy of ρ_0 w.r.t. to π is only finite if ρ_0 is absolutely continuous w.r.t. π, and this cannot hold if ρ_0 is taken to be a Dirac mass. It means that Thm. 1 which initializes (4) at a Dirac mass is incorrect as stated (or at least the proof has to be modified to show that the relative entropy becomes finite after finitely many iterations).\n- Throughout the paper there are a number of minor grammatical errors, and the paper would benefit from an extra round of proofreading.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies discretization schemes for the mirror-descent version of Langevin dynamics, under a mirror log-Sobolev inequality (LSI). We thank the authors for a lively discussion. We have decided to recommend acceptance, because the theoretical contribution is of interest to the community. That being said, we still had concerns about 1) knowing when mirror LSI is likely to hold, and 2) the thinness of the experimental section. We thus encourage the authors to update the paper before the final version, so as to include:
* a paragraph on when mirror LSI holds, or might hold, following the discussion that was held during the reviewing process.
* More quantitative experiments that illustrate the theoretical results on the various discretization schemes. Please also make the figure labels more readable.
Decision: Accept (Poster)