Efficient constrained sampling via the mirror-Langevin algorithm
Authors: Kwangjun Ahn
Sinho Chewi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Langevin MCMC
Sampling
Optimization
mirror-Langevin

Abstract: We propose a new discretization of the mirror-Langevin diffusion and give a crisp proof of its convergence. Our analysis uses relative convexity/smoothness and self-concordance, ideas which originated in convex optimization, together with a new result in optimal transport that generalizes the displacement convexity of the entropy. Unlike prior works, our result both (1) requires much weaker assumptions on the mirror map and the target distribution, and (2) has vanishing bias as the step size tends to zero. In particular, for the task of sampling from a log-concave distribution supported on a compact set, our theoretical results are significantly better than the existing guarantees.

Efficient constrained sampling via the mirror-Langevin algorithm
Kwangjun Ahn
Sinho Chewi
Department of EECS
Department of Mathematics Massachusetts Institute of Technology
Massachusetts Institute of Technology Cambridge, MA 02139 kjahn&mit.cc
Cambridge, MA 02139 schewi @mit edu
Abstract
We propose a new discretization of the mangev- diffusion and give a crisp proof of its convergence. Our analysis uses relative convexity/smoothnes. and self-concordance, ideas which originated in convex optimization, together with a new result in optimal transport that generalizes the displacement convexity of the entropy. Unlike prior works, our result both (1) requires much weaker assumptions the mirror map and the target distribution, and (2) has vanishing bias the step size tends to zero. In particular, for the task of sampling from log-concave distribution supported better than the existing guarantees.
compact set, our theoretical results are significantly
Introduction
We consider the following canonical sampling problem. Let V R² - [ooo be convex function and let æ be the density on R which is proportional to cxp(-V). The task is to output sample which is (approximately) distributed according to x, given query access the gradients of V.
The sampling problem has attracted considerable attention recently within the machine learning and statistics communities. This renewed interest in sampling is spurred,
hand, by wide breadth of applications ranging from Bayesian inference [RC04] 19] and its use in inverse problems [DS17]. to neural networks [GPAM*14 14 TR20). On the other hand, there is deep and fruitful connection between sampling and the field of optimization, introduced in the seminal work [JKO98], which has resulted in the rapid development of sampling algorithms inspired by opti- mization methods such as: proximal/splitting methods [Ber18] Wibl8 Wib19, 222, coordinate descent [DLLW21a DLLW2Ib mirror descent [HKRCI& CLGL 20 ZPFP20, Nesterov's accel- erated gradient descent [CCJJ88 MCC DRD20,, and Newton methods [MWBG12] SBCR16]
CLGL + 22 WL20].
To describe this connection, we recall the Langevin diffiusio,, which is the solution to the following stochastic differential equation (SDE):
dx, = VV) v2dB.
(LD)
Under standard assumptions on the potential V. the SDE is well-posed and converges distribution, as co, to its unique stationary distribution Thus, once suitably discretized, it yields popular algorithm for the sampling problem. The Langevin diffusion classically studied using techniques from Markov semigroup theory [see, e.g. [GL.14 Pav 14), but there is more insightful perspective
which views the diffusion (L) through the lens of optimization [KO98]. Specifically, if 14, denotes
the law of the process
(LD at time t, then the curve (Pc) is the gradient flow of the KL divergence
DRL(: (- || T) in the Wasserstein space of probability measures. This perspective has not only inspired
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Figure 1: Illustration of the mirror Langevin algorithm MLA). from Bub15 Figure 4.1].
This illustration is adapted
dom(
V
dom
X
-*V((X))
Vo(X&)
V
mirror descent
Wo
MLA:1
Wi
X Xx+1/2
mirror diffusion
MLA:2
W
V
X
new analyses of Langevin ICBI8 Wib18 DMM19 VW 19), but has also emboldened the possibility of bringing bear the extensive toolkit of optimization the problem of sampling; see the references listed above.
However, the vanilla Langevin diffusion notably fails when the support of the target distribution is not all R This task constrained sampling, named analogy to constrained optimization, arises in applications such latent Dirichlet allocation [BNI03] ordinal data models [TA66), survival time analysis [K066, regularized regression [CEAM* 12), and Bayesian matrix factorization [PBJ14] Despite such broad range of applications, the constrained sampling problem has proven to be challenging, In particular, most prior works have focused on domain-specific algorithms [GSL92
PP14 LS16), and the first general-purpon algorithms for this task recent [BDMP17 BEL18)
In this work, we tackle constrained sampling problem the mirror-Langevin algorithm (MLA).
MLAjis is discretization of the miiror-Langewe diffusion [HKRCI8] ZPFP20), which is the sampling analogue of mirror descent. Namely, Φ R2d + RR {oo) is mirror map, then the mirror-Langevin
diffusion is the solution to the SDE
X, (V²)()),
dY, VV dt + (V))(x))
(MLD)
Technical motivation. Recently, Zhang et al. [ZPFP20 analyze an Euler-Maruyama discretization of MLD] see (2.2) for details. The most curious aspect of their result is that their convergence guarantee has a bias term that does not vanish even when step size tends to zero and the number of
iterations tends infinity. Moreover, they conjecture that this bias term is unavoidable. This is in contrast to known results for standard Langevin, which raises the main question of this paper:
Can different discretizution of MLD lead to vanishing bias?
discretization of the mirror- mirror-Langevin Langevin diffusion, given in (MLA) and illustrated in Figure Our proposed discretization has the same cost as the standard Euler-Maruyama discretization of MLD in terms of the number of queries the gradient oracle for V. We remark that our scheme for the case & = ||- F/2 recovers the unadjusted Langevin algorithm. The most important aspect of our result is that the bias of our algorithm vanishes as the step size tends to zero unlike the result by Zhang et al. [ZPFP20].
Our contributions. We propose
By adapting the analysis of Durmus et al. DMM19) provide clean convergence analysis of our algorithm which theoretically validates our discretization scheme. Notably, our analysis only requires standard assumptionssddeiiitoon which are well-studied in optimization. In particular, establish stronger link between sampling and optimization without relying on technical assumptions of Zhang al. (2PFP20) (e.g. commutation conditions for Hessians; (A5) therein).
Moreover, our analysis combines ideas from optimization with the calculus of optimal transport. In particular, establish new generalization of a celebrated fact, namely that the entropy functional is

---

displacement convex along Wasserstein geodesics, to the setting of Bregman divergences (Theorem 4 This inequality has interesting consequences in own right: as we discuss in Corollary already implies the transport inequality of Cordero-Erausquue
our result
CE177.
We provide convergence guarantees for the following classes of potentials: (1) convex and relatively smooth (Theorem I]: (2) strongly relatively convex and relatively smooth (Theorem ) and (3) convex and Lipschitz (Theorem 3 Our results largely match state-of-the-art results for the discretization of the Langevin algorithm for unconstrained sampling. Our work paves the way for the practical deployment of gairor-Langevee methods for sampling applications, paralleling the successes of mirror descent in optimization [NY83] [N Bub13].
In Section 5 we demonstrate the strength of our convergence guarantees compared with the previous works [BDMP17 BEL18 in an application to Bayesian logistic regression; further applications are theoretical findings with numerical experiments.
given in Appendix H We also corroborate
Other related works. Recently, a few works have proposed modifications of the Langevin algorithm for the task of constrained sampling. Bubeck et al. [BELI8] studied the projected Langevin algorithm (PLA), which simply projects each step of the Langevin algorithm onto dVm(V). A different approach was taken in Brosse et al. 1] which applies the Langevin algorithm to smooth approximation of V given by the Moreau- Yosida envelope. The latter approach was later interpreted and further analyzed by Salim and Richtarik (SR20) using the primal-dual optimality framework from convex optimization.
A different line of work, more closely related to ours, uses a mirror map to change the geometry of the sampling problem [HKRCI&] CLGLL,+0) [ZPF220 In particular, the mirror- Langevin diffu- sion (MLD) was first introduced in an earlier draft of [HKRCI8), as well as in [ZPFP20) The diffu- sion was further studied in [CLGL 20), which provided a simple convergence analysis continuous time using the sampling analog of Polyak-Lojasiewice inequalities [KNS16). We also remark that the idea of changing the geometry via a mirror map also played an crucial role for the problem of sampling
from the uniform distribution over polytope [KN12 LV17 CDWY18 LV18 GN20 LLV20].
Lastly, our work follows the trend of applying ideas from optimization to the task of sampling. Specifically, our analysis adopts the framework of relative convexity and smoothness, which was advocated more flexible framework for optimization [BTT17 LFN18
2 The mirror-Langevin algorithm
2.1 Background
In this section, we list basic definitions and assumptions that we employ in this work.
Convex functions of Legendre type. Throughout, we assume familiarity with the basic notions of convex analysis [see e.g. Roc70 [BL06].
Definition (Convex functions of Legendre type [Roc70] $26]). A proper convex lower semicontin- uous function d : d + R U {oo} is of Legendre type if
(i) (do (b)) + 0.
(ii) @ is strictly convex and differentiable on Q, and (ii) lime ((V((a)) = x whenever {sa)ee is sequence in Q converging to OQ.
The key properties of convex functions of Legendre type are listed below:
The subdifferential öø is single-valued and hence dØ = (vØ) Roc70 Theorem 26. 1].
& is convex function of Legendre type if and only if its Fenchel conjugate di is a convex function of Legendre type [Roc70] Theorem 26.5].
The gradient V forms a bijection between int (d) and int(dom( (d)m with V (V))=
Roc70 Theorem 26.5).
We refer readers to 7o (26) for more details. We henceforth assume that our mirror map á is
convex function of Legendre type.
3

---

The natural notion of "distance" associated with the mirror map ø is given by the Bregman diver- gence [see, e.g. gg.BBb15] $4]:
Definition 2 (Bregman divergence [Bre67]) For convex function & of Legendre type, the Bregman
divergence (s(:s)) associated to & defined as
D2(2, y) = ((x) <(v) ( v).
Vx, E 2 == int(dom(o))
The Bregman divergence behaves like squared distance; indeed, as + Taylor expansion shows that Do (z. y) ~ (a y, V (z)((( y)). We refer [Bub15] $4] for other basic properties the Bregman divergence, Hereinafter, when we use Bregman divergence, we implicitly assume that its associated function Φ is mirror map.
An important case to keep in mind the mirror map Φ = 11-11" where ||-|| denotes the Euclidean 2
norm, in which case the Bregman divergence simply becomes (z y) = 1 yl1
Self-concordance. We recall the definition of self-concordance, which has been extensively used in applications such interior-poine methods [NN94]. Given a C2 strietly convex function d the local norm at z E int (dom(() with respect to & is defined as
/v/c)<())) (V²)(r)u, u)
for u E ER.
The dual local norm at æ E int(dom(6)) with respect to is
| = / <<)))) u, u)
for all u E Rd
Definition 3 (Self-concordant function 8e $5.1.3.. We say that C convex function Φ is self-concordant with constant Ma 2 if for any æ E int(dom(o))
V (o) [u, ull < 2M |
for all u E Rd
Relative convexity/smoothness. We recall the following definitions:
Definition 4 (Relative convexity [BBT17 LFN18)) V is a-convex relative to o if Vyy) (zz) (VV(z), x) + aDD(y, Vx, Q
Definition (Relative smoothness BBT17 LFNI8). V is B-smooth relative to @ if Vvy) S + ( x) + 3D, Vx,y Q
We give some basic facts about these definitions Appendix B
In the rest of this work, assume that V C22(2') where X' int int(dom that X C Q, and X' in Q + W. Also, we assume that exp( - V) integrable so that я is well-defined; this holds if and only if (xx) 2 a ||=||| - for some a, [BVVV14 Lemma 2.2.1].
Optimal transport. Given a lower semicontinuous cost function e Rd x Rd + [0, oc]. we can define the optimal transport cost between two probability measures μ and v on Rdd to be
(E
X p4, Y ~~v) v).
(2.1)
Here, the infimum is taken over pairs random variables (X, Y) defined on the same probability space, with marginal laws f and // respectively. It is known that the infimum in ( is always attained; we refer to the standard introductory texts [Vil03 Vil09 San for this and other basic facts in optimal transport.
In this work, we are most concerned with the case when the cost function es the Bregman divergence associated with a mirror map:
Definition (Bregman transport cost). The Bregman transport cost defined as
(1, == inf (&,
n, Y~u Nn..
The Bregman transport cost was also studied in CE17
In particular, when 1:1 2
obtain important special case:

---

Definition 7 2-Wasserstein distance). The 2- W-sssersteinn distance 22 is defined as W v) == inf [E|IX YI
Y Y~ ~w).
The W2 optimal transport cost indeed defines a metric over the space of probability measures on I with finite second moment [Vi103] Theorem 7.3]; we refer to this metric space the Wasserstein space. The 22 metric particularly important because it arises from a formal Riemannian structure on the Wasserstein space. This perspective was introduced in [[нбî] and applied to the Langevin diffusion in JK098 OV00); in particular, these latter two works justify the perspective of the Langevin diffusion gradient flow of the Kullback-Leibles divergence in Wasserstein space. A rigorous exposition to Wasserstein calculus can be found in [GSO8 Vi109].
Here, we give brief and informal introduction to the calculation rules of optimal transport. For any regular curve of measures (pe) there is a corresponding family of tangent vectors (vr) [see AGSO8
Theorem 1] here, 12 Rd + Rd is vector field on R4. Also, if F is any well- behaved functional defined over Wasserstein space, then at each regular measure μr one can define the Wasserstein gradient of JJ at μ., which we denote (w.J(():: it is also mapping 12d + Rd Then, we have the calculation rule
0,5(m) = ((V)x,,((x)))))) (x()))
for any regular curve of measures (14)220 with corresponding tangent vectors (U:) where X2 ~ Pt- We will use this calculation rule in Appendix
2.2 Diseretization of the mirror-Langevin diffusion
In order turn a continuous-time diffusion such (MLD) into implementable algorithm, it necessary to first discretize the stochastic process. The discretization considered the prior works [ZPFP20 CLGL++00 is simple Euler-Maruyama discretization: fixing 7 > 0, we define sequence of iterates (Xx) via
vo(X++1) = Vo(X;) 7XV) + 2 ( (Xx))
1/2
EK.
(2.2)
where (Ex)REN is a sequence of i.i.d. standard Gaussians in IRd..
However, many other discretizations are possible. Indeed, in many machine learning applications, the most costly step is the evaluation of VV. which may require a sum over large training set, whereas the mirror map á may be chosen to have a simple form. For the purpose of obtaining more efficient sampling algorithm, it may therefore be favorable trade-off to use high-precision implementation of the diffusion step at the cost additional computation time (which nonetheless does not require additional query access to the gradients of V). Motivated by these considerations, propose new discretization (see Figure [ for an illustration):
The mirror-Langen algorithm (MLA):
X == arg min (Xx)) + Ds(x,Xx)] =EQ
(MLA:1)
JaW, v2 1/2 aB.,
X = VW)(W,,
where
(MLA:2)
Wo Vo((x++1/2)
In MLA:2 the stochastie processes (Wi) are assumed be driven by independent Brownian motions at each iteration. When 6 = 11-11/2 MLA recovers the unadjusted Langevin algorithm.
Practicality, Although MLA:2 is defined using the exact solution of an SDE (and we analyze the exact step MLA:2 for simplicity). it should be understood as capturing the idea of discretizing the diffusion step more finely (e.g., through multiple inner iterations of an Euler-Maruyana discretization) than the gradient step. This indeed amenable to practical implementation since, as previously discussed, the gradient step is typically much more costly than the diffusion step. Moreover, this is justified by our theoretical results in the next section, which together with the conjecture of [ZPFP20) suggest that fine discretization of MLA:2 is potentially crucial for attaining vanishing bias. Nevertheless, it is indeed the case that single iteration of MLA is more costly than single step of the Manyamaa discretization of MLD and this represents a limitation of our work.
5

---

Remark 1. Our proposed discretization can be understood as more faithful discretization of the mirror-Langevin diffusion (MLD). la [GWS2T] It can also be understood as the forward-flow discretization of MLD in the interpretation of [Wib18].
Remark 2. order for [MLA:2 to be well-defined, we require assumptions on & such that the diffusion (We) is non-explosive, i.e., it does not exit (nl(()(()))) in finite time. This holds under very mild assumptions on d; see [GK96]. For situations of interest, the assumptions of [GK96 can be checked directly.
3 Convergence rates of mirror-Langevin algorithm
First, we state the main assumptions which are used for our main results.
Assumption (Self-concordance of Φ). We assume that & is Mo-self-concorrdmm (Definition 3
Assumption 2 (Relative Lipschitzness), We assume that V is L-relatively Lipschitz with respect to 6, in the sense that [[ (x) ([)))==" S for all a E X (see Section 2.1 for the definition of the local norm used here).
Assumption 3 (Relative convexity and smoothness). We assume that V is a-convex relative to & and 3-smooth relative to 6, where a S 3 S x (Definitions F 5
Our analysis works under weaker assumptions than those of [ZPFP20] In particular, analysis does not assume the moment condition on the Hessian ((A2) therein) and the bound on the commutator between V2 and V ((A5) therein). Moreover, analysis uses weaker (and more standard) definitions of cefeccnncod..cee
Remark 3.
Throughout this section, we assume the conditions listed above, and we present convergence results for MLA under various sets assumptions. Our first two results pertain to the smooth case, i.e. 00. Define the parameter
B := B
One might wonder how large 3' is for typical applications. First, we only need & to be self-concordant, not a self-concordant burrier. Hence the appearance of M& is typically not problematic; for instance, a log barrier with m constraints is ((1--self-concordaan. The smoothness parameter could be large and cemeension-depndenn in general. However, such situations are actually where approach could be potentially advantageous. In Appendix E.2 we demonstrate an example where the smoothness parameter becomes much smaller by choosing & carefully.
Theorem (Weakly convex case). Suppose that Assumptions
hold with a = and 3' > 0. For larget accuracy let Xx μu denote the iterates of MLA with step size 1j = min ( 2 }
Then, the following convergence rate holds for the mixture distribution PN = N Σ Mk:
4.3 @ po) max 1, 2d
c
DKL(FN (] sc provided that N 2
(3.1)
2
Proof. See Appendix
Theorem (Strongly relatively convex case). Suppose that Assumptions hold with a,
1. (Convergence in Bregman transport cost) For a target accuracy e 0, let X ~ Hy denote the iterates of MLA with step size 1) min{ 29/d 37 Then,
Dolm, UN) se, provided that N
23'dd are
In
2D 2DD(TT
max (1, QE 2d
2. (Convergence KL divergence) For a targel accuracy e >> O, suppose that Xo oi satisfies (T(T, (o) & e/a. Let Xx ~ Ps denote the iterates of MLA with step size }. Then, the following convergence rate holds for the mixture distribution
" = min( 2
as
n = N Ek=ika
43'd max (1, E
DeL (p || ④) See, c, provided that N 2
ae
2d

---

Proof. See Appendix C33
Note that the initialization assumption (T. no) <e/a in the second assertion of Theorem can be
Chaining together the two parts of the theorem, we therefore obtain the following guarantee: suppose that we initialize MLA a distribution No- Then, with step size min 23'd I. we obtain
obtained from the first guarantee of Theorem 2
ae I
No+ N1
No
2 In 2a (0DD)T)H))) max fax(1, 2d
DKL
TT Se,
provided that
or 43'd
N1 No+1
Ni
max 30
Observe also that for the case 1111. Theorems and recover the corresponding convergence
guarantees for the unadjusted Langevin algorithm [Corollary 7, and Corollaries 10 and 11 respectively in DMM19
Next, we present our guarantee for the non-smooth case oo. For this result, we assume that strongly convex w.r.t a norm ||-I| on Rd. and that V L--ippshitz in this norm. Since the norm of the gradient should be measured in the dual norm ||-II this means precisely that VV I L, for all X
(3.2)
We also note that the next result does not require self-concordance of Φ. Theorem (Non-smooth case). Assume is 1-strongly convex L-Lipschitz in this norm (in the sense of (322), and that a (i.e., is convex). For a target accuracye >> O, let Xx ps denote the iterates of [MLA with step size = e/i.2. Then, the following convergence rate holds for the mixture distribution Ty == 1/ +E uei
norm |-1| Rdd, that V is
2L2 2T
DKL ( [1 sc, provided that N
Proof. See Appendix C.4
The assumption 3 is stronger than relative Lipschitzness: if satisfies 3.2 and is I-strongly convex w.r.t. ||- then is T.-relatively Lipschitz with respect to & with S T.. When ||:]| the
Euclidean norm and / 2, then recover special case of [DMM19 Corollary 14).
11-12
We now make a number of remarks about our result.
Remark 4 (Implementing P.). One can output a sample from Ta by simply outputting one of the iterates [Xx k= chosen uniformly at random.
Remark (Convergence other metrics). Using standard inequalities, our results for convergence in KI. divergence imply convergence in number of other information divergences such as the total variation distance, see Tsy099 $2.4).
When V is a-strongly convex (w.rt. 2-) then the T3 transportation-cos inequality [V1009 Theorem 22. 14] a x) S 'DLL (n4 [[ implies convergence in the W2 distance as well. In general, we do have convergence in Wz, but we can always obtain convergence with respect to a different optimal transport cost, namely, the Bregman transport cost Dy associated with V. This is a consequence of Corollary aalso see CE17 Proposition 1], which asserts that Dy(u, π) DKL (n m))
11:12,
Remark 6 (Dimension dependence). Ignoring for now the dependence on 3 (which may also have a dimension dependence depending on the application), the Bregman divergence Da Mo) term is typically of size ((d) (see Section 5 for particular instance of this). Thus, our overall dimension dependence is (dd)) for the weakly convex case and Odd) for the strongly convex case. Overall, this is a significantly better dependence on the dimension as compared to the previous works BDMP17 BELI8; we perform detailed comparison in Section 5 a specific setting.
We also remark that mirror descent has classically been used for dimension reduction by changing the geometry of the algorithm from &g to f1. We investigate the possibility of doing the same for sampling in Appendix E.2
In this case, Ms = 0, so the Lipschitz constant L does not enter the final result. In particular, it is not contradictory assume strong convexity (a 0).
7

---

Remark 7 (Comparison with (HKRCI8). [HKRCI8] show that for strictly cogccoecave targets, there exists good mirror map for which the pushforward of the target distribution via V enjoys the same guarantees as ordinary Langevin. However, this result is only existential and gives no guidance on how to construct the mirror map. contrast, our theorems hold for any choice of mirror map which satisfies our assumptions, and provide guidance on how to choose the mirror map. Also, our relative smoothness condition allows for potentials which blow up at the boundary of their domain (i.e. the target distribution vanishes near the boundary of its support), whereas this is forbidden by the assumptions of [HKRCTS] Lastly, our algorithm does not require computing the third derivative of the mirror map, whereas this is required for [HKRC18].
Remark (Comparison with (ZPFP20). ZPFP20 performs an analysis of the Euler-Maruyama discretization of MLD which we temporarily refer to as MLA'. Our result guarantees that for any desired accuracy c, it possible to choose the step size sufficiently small so that MLA]achieve the target accuracy; in contrast, the result of [ZPFP20) only guarantees that MLA' contracts to within ball around и of radius O(vd) (measured w.r.t. a modified Wasserstein distance) conjecture that their bias term is unavoidable.
2 Moreover, (PFP22)
In light of our result, we believe that it is an interesting open question to resolve their conjecture. Their conjecture, if true, suggests that replacing MLA:2 in our algorithm by single step of the Euler- Maruyama discretization has disastrous effects on the convergence of the algorithm, and therefore provides further support for considering MLA instead of MLA'.
Recently, after the first draft of our paper was published online, Li et al. LTVW21] gave an analysis of MLA' under subset of the assumptions of [ZPFP20] which indeed exhibits vanishing bias, provided that the relative strong convexity parameter of the potential is sufficiently large compared to the modified self-concordance parameter of the mirror map. It remains an open question remove this latter restriction from their work, and moreover to obtain similar results under the more usual definitions of relative convexity/mootthnes and self-concordance that we adopt this work.
In order to generalize the discretization analysis from the vanilla Langevin algorithm to the mirror- Langevin algorithm. in the next section we prove a new displacement convexity result for the entropy with respect to the Bregman transport cost which may be of independent interest.
4 Convexity of the entropy with respect to the Bregman divergence
is well-known that the entropy funetional H is displacement convex along W2 geodesics AGSO8 Theorem 1.4. In fact, this displacement convexity is crucial in showing that DxL || T) displacement convex (when π is log-concave), which in turn is used to analyze the convergence of LD to the target measure. Therefore, in order to understand the convergence of MLD it is crucial to see if such result is true when W2 is replaced by Dz. We prove that indeed the displacement linvexity-like property holds for HC under Do-optimal couplings.
E + H
Theorem 4 ("Convexity" of the entropy with respect to the Bregman divergence). Let p. v be probability measures on Rd and let X ~ μ.. Y ~ be coupled according to the Bregman transport cost D s V). Then, holds that
H(v) 2 H(() + (IVV w. HX))(X))
As a corollary, we can use the calculus of optimal transport in order to recover the transportation-cost inequality of (EI77. In the following, we do not carry out the approximation arguments necessary to make the proof fully correct because rigorous proof of the statement is already given in [CE17] Rather, our main purpose in giving this argument is simply to point out the convexity principle which underlies the transport incquality.
Corollary (CB17 Proposition I)). For any probability measure a on Rd,,
'DkL T) 2 (y, m).
Proof Sketch. Let (X,Y) be optimally coupled according to the Bregman transport cost (...) between μ and We decompose DKL (u || m) = EV()) H(H)). On one hand, the first term is E (X)) = E (YY + E(VV(Y), - Y) + (X,,
Notably, the radius this ball comparable to the distance at initialization. In fact, the proof of [CE17] does not even require convexity of V.
8

---

On the other hand, the convexity result (Theorem 4 shows that
H(n)) 2 {()=) + B (V)) X--), Y).
Putting these together, we obtain
DKL (H ))
2 EV(Y) + (
X-) YY =x 11 [[ (()) = (D
since VV + H(T). the W2 gradient of DKL (- || (T) π,, is zero This proves the result.
5 Application to Bayesian logistic regression
In this section, we apply our main result to Bayesian logistic regression. For more applications of our result, such the possibility of dimension reduction and sampling from non-smooth distributions, we refer the readers to Appendix D
We recall the setting of Bayesian logistic regression: we observe pairs (X,, Y.), i 1, I,.... where X; E Rd and Y; E 13. The data are assumed to follow the model
exp (a) 1 + exp (0, X.)
Y; Bernoulli
independently for i 1,..., n.
(5.1)
Here, the parameter ! itself is assumed be a random variable taking values in Rd If we assume that 0 has a prior density X with respect to Lebesgue measure, then the posterior distribution is
r(0) x A(0) exp
(Yr (0. In(1 + exp (0, (0.x
Since may be computationally infeasible to explicitly compute the normalizing constant for the posterior distribution, we turn towards sampling algorithms.
When we take a prior À which has full support Rd, e.g. Gaussian prior, then we may apply off-the-shelf methods such as the Langevin diffusion (LD). However, if we choose a prior which has compact support, then the unadjusted Langevin algorithm is no longer an acceptable option because it outputs samples outside the support of the posterior. In this case, we must turn to other methods, such as the projected Langevin algorithm [BELI8]. Here, we explore the use of the mangev-nangevvn algorithm (MLA) for constrained sampling.
For the rest of this section, will focus on a particular problem for concreteness and interpretabilliy: we consider the uniform prior À the foe ball [-1, By duality, this an attractive model when the data (X.) have small L -norm, i.e., are approximately sparse. A natural choice of mirror map for this problem is the logarithmic barrier
1
((0)=
Σ In
In
8
A[2]
where use f[+] to denote the coordinates of Rd Then, ó is 1-self-concordam ([Nes18) $5.1.3)). We remark that the separability of the mirror map in this example implies that the diffusion step MLA:2 can be simulated in ((d) steps, rather than (dP)).
For this setting, we compare the guarantees of MLA with the Projected Langevin Algorithm unadjusted Langevin algorithm (MYULA) [DMP17]:
(PLA) [BELI8] and the Moreau-Yosse see Table D The details of the comparison are given in Appendix E.T
We also perform numerical experiment to compare the practical performance of MLA with PLA. We take 8- (0.9..... 0.9) E R000 as the ground truth, and we generate 1000 i.i.d. pairs (X,, Y)) where X; is sampled uniformly from the & ball and Y; is generated from X; according to [5.] with 0+ We generate 30 samples using both MLA and PLA (both with step size y = 0.005). At each iteration, we average the samples to obtain an estimate 0₂ for the posterior mean, and we plot the MaaimneentMMM/.. MLA:2 by performing 10 inner
error |00 02 in Figure 2 averaged over 10 trials. We implement iterations of an Euler-Maruyane discretization.

---

Algorithm
Guarantee
MLA
O(dje) Oidbbe
2.75
PLA
PLA
2.50
MYULA
Old
225
Table 1: Comparison of [ML with other constrained sampling algo- rithms for the number of iterations required output sample whose squared total variation distance to ı at most For simplicity, we focus on the dependence with re- spect to dimension and the accuracy and we defer details of the com- parison to Appendix
2.00
1.75
1.50
125
200
100 600
800
1000
Figure 2: We plot the error for estimators of the posterior mean computed using both MLA and PLA, each taken with step size = 0.005.
Acknowledgments. Kwangjun Ahn was supported by graduate assistantship from the NSF Grant (CAREER: 1846088) and by Kwanjeong Educational Foundation. Sinho Chewi was supported by the Department of Defense (DoD) through the National Defense Science & Engincering Graduate Fellowship (NDSEG) Program. We thank Philippe Rigollet for helpful suggestions which greatly improved the presentation of this paper.
References
[AGS08] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2008.
[BBT17] Heinz H. Bauschke, Jérôme Bolte, and Marc Teboulle. descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Math. Oper. Res., (2(2):330-333) 348, 2017.
[BDMP17] Nicolas Brosse, Alain Durmus, Eric Moulines, and Marcelo Pereyra. Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo. In Satyen Kale and Ohad Shamir, editors, Conference on Learning Theory, COLT 2017, volume 65, pages 319-342 Amsterdam, Netherlands, 07-10 Jul 2017. PMLR.
[BEL18] Sébastien Bubeck, Ronen Eldan, and Joseph Lehec. Sampling from a log-concave dis- tribution with projected Langevin Monte Carlo. Discrete & Computational Geometry, 59(4):757-76) 783, 2018.
[Ber18] Espen Bernton. Langevin Monte Carlo and JKO splitting. 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 1777-1798 PMLR, 2018.
[BGL14] Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion operators, volume 348 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer, Cham, 2014.
[BGVV14] Silouanos Brazitikos, Apostolos Giannopoulos, Petros Valettas, and Beatrice-Hells Vritsion. Geometry of isotropic convex bodies, volume 196 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2014.
[BL06] Jonathan M. Borwein and Adrian S. Lewis. Convex analysis and nonlinear optimization, volume 3 of CMS Books in MathematicsOOvvuue de Mathématiques de la SMC. Springer, New York, second edition, 2006. Theory and examples.
10

---

[BNJ03] David M. Blei, Andrew Y. Ng, and Michael I. Jordan. Latent Dirichlet allocation. Journal of Machine Learning Research, 3(Jan):933-1022 2003.
[Bre67] Lev M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3):200-22) 217, 1967.
[Bub15] Sébastien Bubeck. Convex optimization: algorithms and complexity. Foundations and Trends@: Machine Learning, 8(3-4):231-355 2015.
[CB18] Xiang Cheng and Peter Bartlett. Convergence of Langevin MCMC in KL-divergence. In Algorithmic Learning Theory 2018, volume 83 of Proc. Mach. Learn. Res. (PMLR), page 26. Proceedings of Machine Learning Research PMLR, 2018
[CCBJ18] Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, and Michael I. Jordan. Under- damped Langevin MCMC: a non-asymptotic analysis. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learn- ing Theory, volume 75 of Proceedings of Machine Learning Research, pages 300-323. PMLR, 06-09 09 Jul 2018.
[CDWY18] Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, and Bin Yu. Fast MCMC sampling algorithms on polytopes. The Journal of Machine Learning Research, 19(1):1146-2331 2018.
[CE17] Dario Cordero caaddro-Erauquin. Transport inequalities for lonccve measures, quantitative forms, and applications. Canad. J. Math., 69(3):481 -,,,,,155,,111111
[CEAM* 12] Gilles Celeux, Mohammed El Anbari, Michel Marin, Christian P. Robert, al. Regularization in regression: comparing Bayesian and frequentist methods in a poorly informative situation. Bayesian Analysis, 7(2):777-502, 2012.
[CLGL* +20] Sinho Chewi, Thibaut Le Gouic, Chen Lu, Tyler Maunu, Philippe Rigollet, and Austin J. Stromme. Exponential ergodicity of Miiror-Langeve diffusions. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 19573-19585. Curran Associates, Inc., 2020.
+2G
[DLLW21a] Zhiyan Ding, Qin Li, Jianfeng Lu, and Stephen J. Wright. Random coordinate Langevin Monte Carlo. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learn- ing Research, pages 1683-1710. PMLR, 15-19 19 Aug 2021.
[DLLW21b] Zhiyan Ding, Qin Li, Jianfeng Lu, and Stephen Wright. Random coordinate under- damped Langevin Monte Carlo. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statis- tics, volume 130 of Proceedings of Machine Learning Research, pages 2701-2709. PMLR, 13-15 Apr 2021.
[DM+19] 19] Alain Durmus, Éric Moulines, et al. High-dimensional Bayesian inference via the unadjusted Langevin algorithm. Bernoulli, 25(4A):2854-255) 2882, 2019.
[DMM19] Alain Durmus, Szymon Majewski, and Blazej Miasojedow. Analysis of Langevin Monte Carlo via convex optimization. Mach. Learn. Res., 20:73-1, 2019.
[DRD20] Arnak S. Dalalyan and Lionel Riou-Durand, On sampling from a log-concave density using kinetic Langevin diffusions. Bernoulli, 26(3):1956-1988, 2020.
[DS17] Masoumeh Dashti and Andrew M. Stuart. The Bayesian approach inverse problems. In Handbook of uncertainty quantification. Vol. 1, 2, 3, pages 31 311-428, Springer, Cham, 2017.
[GK96] István Gyöngy and Nicolai Krylov, Existence of strong solutions for Itô's stochastic equations via approximations, Probab. Theory Related Fields, (05(2):143-155 1996.
11

---

[GN20] Adam Gustafson and Hariharan Narayanan. John's 's walk, 2020.
[GPAM+1]] 14] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 2672-2680. 2014.
[GSL92] Alan E Gelfand, Adrian FM Smith, and Tai-Ming Lec. Bayesian analysis of constrained parameter and truncated data problems using Gibbs sampling. Journal of the American Statistical Association, 87(418):523 532, 1992.
[GWS21] Suriya Gunasekar, Blake Woodworth, and Nathan Srebro. Mirrorless mirror descent: a 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 2305-2313. PMLR, 13-15 Apr 2021.
[HKRC18] Ya-Ping Hsieh, Ali Kavis, Paul Rolland, and Volkan Cevher. Mirrored Langevin dynamies. In Advances in Neural Information Processing Systems, pages 2878-2887 2018.
[JA06] Valen E Johnson and James H Albert. Ordinal data modeling. Springer Science & Business Media, 2006.
[JKO98] 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.
[JNI]] Anatoli Juditsky and Arkadi Nemirovski. First order methods for nonsmooth convex large-scale optimization, I: general purpose methods. Optimization for Machine Learning, pages 121-148, 2011.
[KM06] John P Klein and Melvin L. Moeschberger. Survival analysis: techniques for censored and truncated data. Springer Science & Business Media, 2006.
[KN12] Ravindran Kannan and Hariharan Narayanan. Random walks on polytopes and an affine interior point method for linear programming. Mathematics of Operations Research, 37(1):1-20 2012.
[KNS16] H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal- gradient methods under the Polyak-Lojasiewice condition. In Joint European Confer- ence on Machine Learning and Knowledge Discovery in Databases, pages 795-811. Springer, 2016.
[LFN18] Haihao Lu, Robert M. Freund, and Yurii Nesterov. Relatively smooth convex opti- mization by first-order methods, and applications. SIAM Optim., 28 (8(1):333-355 354,, 2018.
[LLV20] Aditi Laddha, Yin Tat Lee, and Santosh S. Vempala. Strong self-concordance and sampling. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1212-1222, 2020.
[LS16] Shiwei Lan and Babak Shahbaba. Sampling constrained probability distributions using spherical augmentation. In Algorithmic Advances in Riemannian Geometry and Applications, pages 25-71. Springer, 2016.
[LTVW21] Ruilin Li, Molei Tao, Santosh S. Vempala, and Andre Wibisono. The mirror Langevin algorithm converges with vanishing bias. arXiv e-prints, 2021.
[LV17] Yin Tat Lee and Santosh S. Vempala. Geodesic walks in polytopes. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 927-940, 2017.
[LV18] 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 SIGACT Symposium Theory of Computing, pages 1115-1121, 2018.
12

---

[MCC*21] 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-base MCMC? Bernoulli, 27(3):1942 1992, 2021.
[MWBG12] 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 J. Sci. Comput., 346)):1440-A1443 2012.
[Nes18] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[NN94] Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming. SIAM, 1994.
[NY83] Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[Otб0]] Felix Otto. The geometry of dissipative evolution equations: the porous medium equation. Comm. Partial Differential Equations, 26 2611-2):1111774 2001.
[OV00] Otto and C. Villani. Generalization of an inequality by Talagrand and links with logarithmic Sobolev inequality. J. Funct. Anal., 173(2):361-40) 2000.
[Pav14] 14] Grigorios A Pavliotis. Stochastic processes and applications: diffusion processes, the Fokker-Planck and Langevin equations, volume 60. Springer, 2014.
[PBJ14] John W. Paisley, David M. Blei, and Michael I. Jordan. Bayesian nonnegative matrix factorization with stochastic variational inference, 2014.
[PP14] Ari Pakman and Liam Paninski. Exact Hamiltonian Moute Carlo for truncated multi- variate Gaussians, Journal of Computational and Graphical Statistics, 23(2)5118-542, 2014.
[RC04] C.P. Robert and G. Casella. Monte Carlo statistical methods. Springer Verlag, 2004.
[Roc70] R Tyrrell Rockafellar. Convex analysis. Number 28. Princeton University Press, 1970.
[San15] Filippo Santambrogio. Optimal transport for applied mathematicians, vol- ume 87 of Progress in Nonlinear Differential Equations and their Applications. Birkhäuser/Springer, Cham, 2015. Calculus of variations, PDEs, and modeling.
[SBCR16] 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 International Conference on Machine Learning Volume 48, ICML'16, 16, page 642 651. JMLR.org, 2016.
[SKL20] Adil Salim, Anna Korba, and Giulia Luise. The Wasserstein proximal gradient algo- rithm. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 12356-12366. Curran Associates, Inc., 2020.
[SR20] Adil Salim and Peter Richtarik. Primal dual interpretation of the proximal stochastic gradient Langevin algorithm. Advances in Neural Information Processing Systems, 33, 2020.
[TR20] Belinda Tzen and Maxim Raginsky, A mean-field theory of lazy training in two-layer neural nets: entropic regularization and controlled McKean- KeKean-Vlasoov dynamics, arXiv preprint arXiv:2002.01987. 2020.
[Tsy09] Alexandre Tsybakov. Introduction to nonparametric estimation. Springer Series in Statistics. Springer, New York, 2009. Revised and extended from the 2004 French original, Translated by Vladimir Zaiats.
[Vi103] Cédrie Villani. Topics in optimal transportation, volume 58 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2003.
13

---

[Vi109] Cédric Villani. Optimal transport, volume 338 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer- Verlag, Berlin, 2009. Old and new.
[VW19] Santosh S. Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algorithm: isoperimetry suffices. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8094-8106. Curran Associates, Inc., 2019.
[Wib18] Andre Wibisono. Sampling as optimization in the space of measures: the Langevin dynamies composite optimization problem. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Conference on Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 2093-3027, PMLR, 2018.
[Wib19] Andre Wibisono. Proximal Langevin algorithm: rapid convergence under isoperimetry. arXiv e-prints, November 2019.
[WL20] Yifei Wang and Wuchen Li. Information Newton's flow: second-order optimization method in probability space. arXiv e-prints, January 2020.
[ZPFP20] Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, and Marcelo Pereyra. Wasserstein control of mirror Langevin Monte Carlo. In Jacob Abernethy and Shivani Agarwal, editors, Conference Learning Theory (COLT), 2020, volume 125, pages 3814-388 4841. PMLR, 09-12 Jul 2020.
14


Reviews:
[{"review_id": "nFzhYEvaXT6", "reviewer": "Reviewer_UqoF", "summary": "The paper under review is considering a new discretization for the MLD. The motivation comes from solving constrained optimization problem. Under proper assumption, the authors present convergence analysis for the algorithm in terms of the KL and Bregman divergence.  In order to derive the convergence analysis, the author derive displacement convexity property and treat/verify several technical conditions following previous works in the literature.", "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": "Positive.\n\n1. The paper is well written. The preparation of the materials, the main proof outlines, and the organization of the paper are in good manner.\n\n2. The Proof seems to be easy to follow; I did not check all the computations and the all the coefficients in the proof process. The logic and the basic stream seems to be correct. The authors show some subtle points and technique conditions that were used in the proof. \n\n3. The analysis of the discretization algorithms seem to work for more general Langevin diffusions, e.g. variable diffusion Langevin dynamics. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Questions and comments.\n\n1.  The condition $N>\\frac{2\\mathcal D(\\pi||d\\mu_0)}{\\eta\\varepsilon}$ in Theorem 1 seems to be big. Is there any guideline how does this help in practice. \n\n2. MLA 1 and MLA 2 seems to be quite general. Can this be adapted to reversible/nonreversible variable diffusion Langevin diffusion? Can you deal with the non-convex $V$ case? For example, the mirror Langevin is one special case of the gradient drift variable Langevin diffusion considered in [Q. Feng and W. Li: Hypoelliptic entropy dissipation for stochastic differential equations ].  The entropy decay and LSI are derived for general Langevin diffusions. ( here diffusion matrix $a(X_t)= \\nabla^2\\phi(X_t)$ ) Do you think that this may help to derive the convergence analysis for more general potential fiction $V$?\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "n1POnmFj8Iw", "reviewer": "Reviewer_AWLg", "summary": "The paper proposes a new mirror descent like Langevin algorithm to sample from exp(-V), where V is relatively smooth/convex.\nThe algorithm is designed as a Forward Flow algorithm.\nThe convergence guarantees are similar to those of the vanilla Langevin algorithm (ULA), but using some newly defined Bergman divergence instead of the Wasserstein 2 distance. ", "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": "Originality: \n\nThe paper extends the approach of [DMM19] to handle a mirror descent like Langevin algorithm. To this end, the authors define a Bregman optimal transport cost that will induce the natural geometry of the algorithm. Basically, the convergence rate are provided in terms of the Bregman cost if V is relatively strongly convex and in terms of KL else.  \n\n\n\nThe algorithm is designed as a \"Forward Flow\" algorithm [Wib18], so that the convergence proof of [DMM19] can be extended to mirror descent. The algorithm has two steps. The first step is like a mirror descent descent and the second one introduce randomness following a mirror flow  (instead of a Gaussian noise in ULA). \n\nOn the practical side, unlike ULA, this mirror flow step cannot be implemented in closed form. The implementation of MLD2 should be discussed further. Can we implement it in closed form for some \\phi (other than the square norm)?\n\nOn the theoretical side, this paper is quite rich mathematically with several interesting ideas that extend those of DMM19 and can be used beyond the scope of this paper. Indeed, although there is a direct parallel between the proof of [DMM19] and this paper, the adaptation of [DMM19] is highly non trivial. Basically, every steps is more complex, in more details:\n\n-the step that looks like a gradient descent proof in DMM19 here looks like a mirror descent proof\n-the dissipation of the entropy along the mirror flow relies on the **provable** (Theorem 4) convexity of the entropy along geodesics induced by the Bregman optimal transport cost. Inspecting the proof, it is a consequence of the geodesic convexity of the entropy along generalized geodesics. \n-the dissipation of energy along the mirror flow relies in DMM19 on a simple smoothness argument and here relies on Ito calculus.\n\n\nQuality: \n\nThe paper is well written. Even the appendix is of high quality. The convergence rates are natural extensions of those of ULA, I just have some concern about the warm start assumption in Th 2 (convergence in KL divergence). Moreover, in the proof of Corollary 1, it is used that the entropy is (sub)differentiable at \\pi, and this requires implicitly the density of \\pi to be an element of S_{loc}^{1,1}(R^d) (see [AGS08, Th 10.4.13]).\n\nAdditionally, I would be happy to see the Forward flow interpretation of the algorithm in the main paper, as well as the Wasserstein mirror flow interpretation of MLD2. In particular, how do you find the formula of the velocity field?\n\nThe simulations are a bit lightweight. I understand the this work is theoretical. In Figure 2, why not plotting the ergodic means of the \\theta_k along the algorithm? (they are supposed to converge a.s. to the mean a posteriori thanks to the ergodic theorem).\n\nFinally, some cleaning is needed in the references. \n\nClarity: \n\nThe assumptions should be recall in the statement of each theorem. In particular, do the authors assume simultaneously Ass. 2 and Ass. 3 with \\alpha > 0 in Theorem 2? It seems that these assumptions are mainly incompatible (think about a Lipschitz strongly convex function for the case where \\phi is the square norm)\n\nSignificance: \n\nOverall, the paper is a smart extension of DMM19 and, even if one could argue that the practical implementation should be discussed further, the paper brings new ideas on how to use optimization techniques in sampling and that should be relevant to the community.\n\nMINOR:\n\nl.134: FYI, this is an equivalence, see [A, Lemma 2.2.1]\nl. 231: \"V is relatively convex\"\nl. 242: \"O(d) for the weakly convex case with a warm start\" Why? I don't understand.\nl. 664: \"known\" <-- \"new\"\nl. 685: conclusion of the proof is missing. One can conclude using Lemma 4 in [SKL20]\nl. 305: Better to write \"it output samples outside...\"\nl. 108: Capital letter missing\nl. 314: MLA2\nl. 615: superdifferentiability argument: Why is the entropy (sub)differentiable at \\nu_t ?\n\n\n[A]: S. Brazitikos, A. Giannopoulos, P. Valettas, and B.-H. Vritsiou. Geometry of isotropic convex bodies\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: the authors could discuss more the implementation of MLD2 and acknowledge clearly that the complexity of one iteration of the proposed algorithm **is** higher than one iteration of ULA of [ZPFP20].", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "el-rX1JN3Hm", "reviewer": "Reviewer_FccJ", "summary": "This work proposes an analysis of the symmetric Mirror Langevin diffusion, in the case where the diffusion step in the mirror space is computed exactly. Under milder assumptions than existing work [ZPFP20], the authors prove convergence of the error in KL divergence to 0 as opposed to previous work showing convergence to a Wasserstein ball with non-zero radius, hence showing the benefit of better approximating the diffusion step than simply doing an Euler-Maruyama step.", "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": "Pros:\n- Interesting theoretical result, showing that the convergence issue in [ZPFP20] can be solved by a better approximation of the diffusion step.\n- Relaxes the assumptions made in [ZPFP20], in particular the commutation conditions for Hessians.\n\nCons:\n- The paper would greatly improve by analyzing the impact of approximate, which would provide a more correct description of the practical convergence rate. In particular, the claim in the abstract that “Unlike prior work, our result has vanishing bias as the step size goes to zero” is not fair, since including a discretization of the diffusion will most probably involve a similar bias.\n- The practical usefulness of the algorithm seems limited. Based on Figure 4, it is not clear whether a better diffusion discretization truly yields a better solution. Moreover, the algorithm is only compared to PLA, which has the worst convergence rate, and is known to perform rather badly in practice. It may be interesting to compare against MYULA [BDMP17], MLD (asymmetric discretization [HKRC18], or  [REKV20] (the latter also being worth mentioning in Table 1).\n\n[ZPFP20] Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, and Marcelo Pereyra. Wasserstein control of mirror Langevin Monte Carlo\n\n[HKRC18] Ya-Ping Hsieh, Ali Kavis, Paul Rolland, and Volkan Cevher. Mirrored Langevin dynamics.\n\n[BDMP17] Nicolas Brosse, Alain Durmus, Eric Moulines, and Marcelo Pereyra. Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo.\n\n[REKV20] Paul Rolland, Armin Eftekhari, Ali Kavis, and Volkan Cevher. Double-loop unadjusted Langevin algorithm.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2h"}, "extra_text": {}}, {"review_id": "OShD6pB2bHT", "reviewer": "Reviewer_d6un", "summary": "This paper proposes and studies a new discretization scheme of the mirror-Langevin diffusion proposed in Zhang et al. (2020). The results build on the assumption of self-concordance of the mirror function and has vanishing bias as the step size tends to zero.", "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": "Strengths:\n* The motivation is strong --- correcting bias in the Euler-Maruyama discretization of Zhang et al.\n* The proof looks correct to me. It is also easy to follow and the results are neat.\n\nWeaknesses:\n* The biggest concern for me is that the proposed algorithm is not really a discretization since the diffusion step is still in continuous time and the proof relies on Ito's formula. This obviously makes a big difference and it is unclear what a proper discretization of it is. I noticed that this has been the concern for reviewers of COLT. However, I don't think it is now addressed up to satisfactory.\n* I wonder how the proposed algorithm compare to running LD in the mirrored space, which was shown in Ya-Ping Hsieh et al. (2018) to have O(d/eps^2) convergence. For optimization this would not be a concern since the optimum need not match under transformation of the mirror map, but since now we are dealing with sampling, there is no obvious reason that one should prefer MLA over LD in the mirrored space.\n* The empirical result (Figure 2), if the authors decide to include any, does not provide strong evidence supporting the theoretical argument. PLA seems to converge much faster, although MLA lead to better results but there is still a large gap from the target distribution.\n* How strong is the self-concordance assumption on mirror maps? Does it apply to choices other than barriers?", "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": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors have identified an assumption that extends the work of [Zhang, Peyre, Fadili, Pereyra] to have guarantees for the mirrored Langevin algorithm -- not to be confused from the mirrored Langevin dynamics of [Hsieh et al].

However. the assumption cannot be implemented in practice since the authors cannot do the perfect discretization in the flow step. The standard Euler discretization normally results in the Cox-Ingersoll-Ross (CIR) process, which has a notoriously slow convergence rate. While the authors use a different discretization process, it cannot be implemented. The additional assumptions of the relative smoothness + strong convexity seems restrictive.

Even in the case of the simplex constraints, the authors use the log-barrier and not the usual entropy, which is the staple of mirror descent methods. Moreover, there is no comparison with [Hsieh et al] for the same example. Note that those authors use the entropic mirror map.

There are weaknesses as there is no analysis on the proposed discretization and the ensuing bias introduced while the paper is beautifully written with solid mathematical content. In particular, as one of the reviewers point out, this is not a real discrete time paper nor a continuous time paper - but it is somewhere in between. A revised paper with some analysis on the discretization would make it super compelling. 
Decision: Accept (Poster)