Constrained Langevin Algorithms with L-mixing External Random Variables
Authors: Yuping Zheng
Andrew Lamperski
Venue: NeurIPS 2022 Accept (2022)
Keywords: Langevin algorithms
L-mixing processes
Gradient descent methods
Non-convex optimization
Non-asymptotic analysis
Markov Chain Monte Carlo sampling

Abstract: Langevin algorithms are gradient descent methods augmented with additive noise, and are widely used in Markov Chain Monte Carlo (MCMC) sampling, optimization, and machine learning. In recent years, the non-asymptotic analysis of Langevin algorithms for non-convex learning has been extensively explored. For constrained problems with non-convex losses over a compact convex domain with IID data variables, the projected Langevin algorithm achieves a deviation of $O(T^{-1/4} (\log T)^{1/2})$ from its target distribution \cite{lamperski2021projected} in $1$-Wasserstein distance. In this paper, we obtain a deviation of $O(T^{-1/2} \log T)$ in $1$-Wasserstein distance for non-convex losses with $L$-mixing data variables and polyhedral constraints (which are not necessarily bounded). This improves on the previous bound for constrained problems and matches the best-known bound for unconstrained problems.


Constrained Langevin Algorithms with L-mixing External Random Variables
Yuping Zheng
Department of Electrical and Computer Engineering University of Minnesota, Twin Cities Minneapolis, MN 55455 2hen0348@umn edu
Andrew Lamperski
Department of Electrical and Computer Engineering University of Minnesota, Twin Cities Minncapolis, MN 55455 alampers@umn. edu
Abstract
Langevin algorithms are gradient descent methods augmented with additive noise, and are widely used in Markov Chain Monte Carlo (MCMC) sampling, opti- mization, and machine learning. In recent years, the non-asymptotic analysis of Langevin algorithms for non-convex learning has been extensively explored. For constrained problems with non-convex losses over a compact convex domain with IID data variables, the projected Langevin algorithm achieves deviation of O(T-1/4(log 1/2) from its target distribution [27] in I-Wasserstein distance. In this paper, we obtain a deviation of O(T log T') in 1- L-Wasserstein distance for non-convex losses with L-mixing data variables and polyhedral constraints (which are not necessarily bounded). This improves on the previous bound for constrained problems and matches the best-known bound for unconstrained problems.
Introduction
Langevin algorithms can be viewed as the simulation of Langevin dynamics from statistical physics [14]. They have been widely studied for Markov Chain Monte Carlo (MCMC) sampling [37], non-convex optimization [5, 23] and machine learning [43]. In the statistical community, Langevin methods are used to resolve the difficulty of exact sampling from high dimensional distribution. For non-convex optimization, the additive noise assists the algorithms escape from local minima and saddles. Since many modern technical challenges can be cast as sampling and optimization problems, Langevin algorithms are potential choice for the areas of adaptive control, deep neural networks, reinforcement learning, time series analysis, image processing and so on [4, 10, 29].
Related Work. In recent years, the non-asymptotic analysis of Langevin algorithms has been extensively studied. The discussion below reviews theoretical studies of Langevin algorithms for MCMC sampling, optimization, and learning.
The non-asymptotic analysis of Langevin algorithms for approximate sampling (Langevin Monte Carlo, LMC) began with [16, 17], with more recent relevant work given in [3, 4, 10, 13, 19, 22, 28, 30, 32-34, 42, 46). Most works on LMC consider log-concave target distributions, though there exists some work relaxing log-concavity [10, 13, 33. 34, 42] and smoothness of the target distribution [13, 28, 34]. Most LMC work focuses on the unconstrained case.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Constrained problems are less studied, but variety of works have begun to address constraints in recent years. The work [8. 9] analyzes the case of log-concave distributions with samples constrained to convex, compact set. Other methods derived from optimization have been introduced to handle constraints, such as mirror descent [1. 25, 26, 45] and proximal methods [7].
Pioneering work on non-asymptotic analysis of Langevin algorithms for unconstrained non-convex optimization with IID external data variables was given in [35], which was motivated by machine learning applications [43]. Since then, numerous improvements and variations on unconstrained Langevin algorithms for non-convex optimization have been reported [10-12, 21, 44].
The work [41] examines the Unadjusted Langevin Algorithms without convexity assumption of the objective function and achieves a convergence guarantee in Kullback-Leible (KL) divergence assuming that the target distribution satisfies a log-Soboley inequlity. However, KI. divergence is infinite with the deterministic initialization. To mitigate this pitfall, our work measures the convergence bound in 1- W-Wasserstein distance, which allows the initial condition to be deterministic.
The first analysis of Langevin algorithms for non-convex optimization with IID external variables constrained to compact convex sets is given in [27], and builds upon [8, 9]. However, the convergence rate derived in [27] is rather slow since it uses loose result on Skorokhod problems in [40]. Recent work of [39] obtains e-suboptimalitty guarantees in Õ However, some extra work would be required to give a direct comparison with the current work, as the results in [39] depend additionally on the spectral gap, which is not computed here.
Most convergence analyses for constrained non-convex optimization require no constraints or bounded constraint sets and IID external random variables or no external variables. In practice, the boundedness of constraint sets and the dependence of external variables do not always hold. The work [10] gives non-asymptotic bounds with L-mixing external variables and non-convex losses, which achieves tight performance guarantees in the unconstrained case. contrast, our work gets tight convergence bound (up to logarithmic factors) with L-mixing data streams and applies to arbitrary polyhedral constraints, which may be unbounded.
Contributions. This paper focuses on the non-asymptotic analysis of constrained I Langevin algo- rithms for non-convex problem with L-mixing external random variables and polyhedral constraints. We show the algorithm can achieve deviation of O(T log 7') from its target distribution in 1- Wasserstein distance in the polyhedral constraint and with dependent variables. The result from [10] on unconstrained Langevin algorithms with L-mixing external random variables gives deviation of O/T-1/2 T) 1/2), and so we see that our results match, up to factor of (log 1)2/2 For constrained problems, our general polyhedral assumption is not directly comparable to related work of [27], which examines compact convex constraints, and [39], which examines bounded non-convex constraints. In the cases where the domains and random variable assumptions match (i.e. bounded polyhedra with IID external random variables or no external random variables), our paper gives the tightest bounds. In particular, this improves on the bound from [27], which gives a deviation of O(T-1/A(log (log T)//2) with respect to Wasserstein distance.
A key enabling result in this paper is a new quantitative bound on the deviation between Skorokhod problem solutions over polyhedra, which gives a more explicit variation of an earlier non-constructive result from [18]. Additionally, we derive a relatively simple approach to averaging out the effect of L-mixing random variables on algorithms.
2 Problem Setup
2.1 Notation and terminology
R denotes the set of real numbers while N denotes the set of non-negative integers. The Euclidean norm over R is denoted by I|-
Random variables will be denoted bold. If x is random variable, then [[[] denotes its expected value and C(x) denotes its law. IID stands for independent, identically distributed. The indicator function is denoted by If P and Q are two probability measures over RR, then the 1-Wasserstein distance between them with respect to the Fuclidean norm is denoted by W1(P (P.

---

The 1- L-Wasserstein distance is defined as:
(i(P,Q)= inf TEE(P.Q) JACX J.cu ||x ylldT
where C is the couplings between and Q.
Let K. be convex set. (In this paper, we will assume that IC is polyhedral with in its interior.) The boundary of K. is denoted by aK. The normal cone of K. at a point is denoted by Nx( The convex projection onto K. is denoted by πl.-
Let Z denote the domain of the external random variables Zi.
F and are o-algebras, let F FVV denote the o-algebra generated by the union of F and G.
2.2 Constrained Langevin algorithm
For integers k let We ~ (0, I) be IID Gaussian random variables and let zą be an L-mixing process whose properties will be described later. Assume that z, is independent of w for all i, e N.
Assume that the initial value of X independent of z, and w, Then the constrained Langevin algorithm has the form:
2n 3
Xk+1
11
Xx= - VV- 2k) +
We
with & an integer. Here 77 > 0 is the step size parameter and 3 0 is the inverse temperature parameter. In the learning context, f(x, z) is the objective function where x are the parameters aim to learn and z a training data point.
2.3 L-mixing processes
In this paper, we assume that is sequence of external data variables. The class of L-mixing processes was introduced in [24] for applications in system identification and time-series analysis, and gives a means to quantitatively measure how the dependencies between the z₁ decay over time. Formally, I--mixigg requires two components: M-boundedness,, which specifies global bound on the moments and 2) measure of the decay of influence over time.
discrete-time stochastic processes Z& is M-bounded if for all
Mm (2) = sup //m || < xc.
(2)
k20
Let F& be an increasing family of o-aalebras such that 2μ is F3 measuraale and F be a decreasing family of o-algebras such that Fx and Fit are independent for all A: 2 0. Then, the process 2₃ is L-mixing with respect to ((Fx), (F+)) if is M-bounded and
V (z)
Σ 7=0 0
Um (T, 2) < 0
(3a)
with
Vm (T, 2). = =sup 1// 2/
Z Ft ["]
(3b)
22r
For concrete example, consider the order-1 autoregressive model:
Z aZk + Ex+1
where a is constant with loo] < and for all &o E Z. Ex IID standard Gaussian random variables and E Z, where Z = IR in this case. It can be observed from (4) that
2
a Ex-
(5)
1=0
Then, we specify Fú = :E k) and Ft = ofE, : k), can be verified that 2 satisfies (2) and (3) and so is an L-mixing process.
3

---

2.4 Assumptions
We assume that 2x, is E-Lipschitz in both and 2. In particular, this implies that
[[V,f(z1 - [x2(22222) 2)] I <1 - 12l and VV, 21) - Vf(x, 22) S 2 - 22ll-
We assume that 2, is stationary I--mixng process, and let f(x) [I 2:)] denote the function which averages (a, 2e) with respect to 2;-
Further, we assume that f(z) is μ-strongly convex outside ball of radius R 0, i.. (œ1
T22 (Vf(m)) V (2x2) ||= _2|| for all 31, 22 IC such that || x22 || 2 R.
We assume that the initial second moment is bounded above as [|[[ [o]]] S < co.
Throughout the paper, K. will denote polyhedral subset of R with in its interior.
Main results
3.1 Convergence of the law of the iterates
For f defined above, the associated Gibbs measure is defined by:
(af(A) = SAnx e dz Skc dx
(6)
The main result of this paper is stated next:
Theorem 1. Assume that S min { 462 J. K. is a polyhedron with O in its interior, E K, and There are constants CI, C2 and such that the following bound holds for all
< 2
integers 2
Wi (C(x)),, RTff) S (cr + c2v5)e nak + (cs + cav nlog(n
In particular, if =
TogT 2nT T 4 and 2 220 then
(i(L(x)), 61 + coys+ + cav5 (2a)1/2
T T-1/2 log
Furthermore, the constants, C12 C22 Ca2 and c₁ are O(n) with respect to the dimension of xg, and O (2) with respect to the inverse temperature, B. And for all 0,
18
The constants depend on the dimension of X5, the noise parameter, 8, the Lipschitz constant, f, the strong convexity constant μ4, the variance bound of the initial states, 5, and some geometric properties of the polyhedron, K.
The constants shown in Theorem are described explicitly in Appendix
3.2 Auxiliary processes for convergence analysis
Similar to the previous analyses of Langevin methods, e.g. [9, 10, 27, 35], the proof of Theorem
uses collection of auxiliary processes fitting between the algorithms iterates from (1) and stationary distribution given by (6).
The algorithm and variation in which the 2, variables are averaged out are respectively given by:
2n
x41 = 11k
x
V/ zr) +
wi
(7a)
B
XM1 = 11.
MM
n
f(
M +
'21 We
(7b)
3
Here X represents the Algorithm, while x represents a corresponding Mean process.

---

We embed the mean process in continuous time by setting x = [tjo where [t] indicates floor
M
function. The Gaussian noise We can be realized as We Wk+1 We where W; is Brownian motion.
Let denote Continuous timen approximation of x defined by the following reflected stochastic differential equation (RSDE):
2n dw, du dxf = V + V
(8)
Here So v dd (s) is bounded variation reflection process that ensures that x K. for all 2 0. as long x E K. In particular, the measure μ² is such that 4 ((0, t)) is finite, μe supported on {s|x; E ÖCJ. and v. E Nx(xx;) where [xxxx) is the normal cone K at æ. Lemma 10 in Appendix A shows that the reflection process is uniquely defined and x is the unique solution the Skorokhod problem for the process defined by:
2n W: 1VB
I vol(x
y =x +
(9)
See Appendix for more details on the Skorokhod problem.
For compact notation, we denote the Skorokhod solution for a given trajectory, y. by S(y). So. the fact that xC is the solution to the Skorokhod problem for y will be denoted succinctly by x =
S)
The basic idea behind the proof is to utilize the triangle inequality:
Wi (L(((x)) TR5) S (((((()), + (I((()))
(10)
and then bound each of the terms separately.
The second term is bounded by the following lemma:
Lemma 2. Assume that Xy E K. and B [1 s There are positive constants a, c1 and 02 such that for all 2 0
W1(C(xf), m S (e1 + c2v5)e eaat
This result is based on an extension of the contraction results from Corollary of [20] for SDEs to the case of the reflected SDEs. Appendix D steps through the methodology from [20] in order to derive a, Cj and 02 for our particular problem.
Most of the novel work in the paper focuses on deriving the following bound on W1 (1(C(x), ((x)))
Lemma 3. Assume that x² =x K. B||| < s, and 17 min { 87 }. Then there are positive constants C3 and c4 such that for all integers 2 0:
(L(((x)) ((x))) S (cs + cIV) log(n-)))
((((()))L(xx))
Proof of Theorem Plugging the results of Lemmas and into the triangle inequality bound from (10) proves the first result of the theorem. Specifically, let 17
log 20T
then
log
2aT
(((C(x)) < (cr + C2V5))-1/2 (cs + +av)))
log(
2αT
log T
C3 + cavs 7 T 1/2 log T.
S (cI + 1/2 log T
(2a)
This gives the specific bound in the theorem. The last inequality utilizes the fact that log T > 1 for all 7' 2 4 and
log T < T when T' > 2a
laT
Furthermore, we examine the bounds of the constants C₁, C2. Ca. C4 and a in Appendix H, where the dependencies of the convergence guarantee on state dimension n and the inverse temperature parameter, /3 can be observed directly.
The rest of the paper focuses on proving Lemma 3.

---

3.3 Proof overview for Lemma 3
This subsection describes the main ideas the proof of Lemma 3. The results highlighted here, and proved in the appendix, cover the main novel aspects of the current work. The first novelty, captured Lemmas 4 and is new way to bound stochastic gradient Langevin schemes with L-mixing data from Langevin method with the data variables averaged out. The key idea is method for examining a collection of partially averaged processes. The second novelty is tight quantitative bound on the deviation of discretized Langevin algorithms from their continuous tottimuuuu--meeeeeee counterparts when constrained to a polyhedron. This result is based on a new quantitative bound on Skorokhod solutions over polyhedra.
First we derive time rene-dependemt bounds (i.e. bounds that depend on k) for Wi [(x()) This is achieved by introducing collection of intermediate processes and bounding their differences. Time-uniform bounds are then achieved by exploiting contractivity properties of x
To bound Wi (I(C(x)), ()xE)), we first use the triangle inequality:
WI(C(x)) ((xE)) & (C((())), ((x+)) +
(11)
We bound W1 (I(((x)), (xxx)) )) via a collection of auxiliary processes in which the effect of z₁ is partially averaged out. We bound Wi (C(xx)) ((x{)) via specialized discrete-time approximation of x
Now we construct the collection of partially averaged processes. Recall that É 2 is stationary T--mixing process with respect to the o-algebras F& and F For lt < O, we set Fx = (0, 2), i.e. the trivial o-algebra. Let G. be the filtration generated by the Brownian motion, Wi-
Recall that for N. we set Wi
Wk+1
Wi. Define the following discrete-time processes:
2m B
x
M,s 1441
IIx
X
M,s
B
fx fx
M.s (2)) V 9k] +
W
(12a)
2m Wk
X
B38
Il
B,s X
(x Mis (z F 9 + NE
(12b)
Assume that all initial conditions are equal. In other words, x xM X M, s 2 O. The iterations from (12a) define a family of algorithms in which the data variables are partially averaged, while X
x B,s for all
B.s from (12b) corresponds to an auxiliary process that fits between x and
M.
MM*+1 (Here "A" stands for algorithm, "M" stands for mean, and "B" stands for between.)
x
x and for s > k, we have that x M,s XM So. in order to bound W1(C (xx )), it suffices to bound Wi(C(x M.s), L(xx and Wi (C(xxx B.s), which are proved in Appendix E.
Note for
0, we have that x
[(x, () for all 0. These bounds are achieved in the following lemmas,
Lemma 4, For all s 2 0 and all 2 O, the following bound holds:
Wi (C(x L(x s EElxx
-x xx111 2002 (s.
Lemma 5. For all 2 0 and all l 2 0, the following bound holds
wi (C(x (.) C(x Mattt)
B
B.*
X3
M.
III
S
26 z)nV -1)
Now we define the discretized approximation of xf For any initial x E K. we define the following iteration the integers:
1-1 1
2n
x (xP tyc y IT
x +
Vf(x
)ss +
Wk
Recall that the process y is defined by (9).

---

Provided that x = x we have that x" S(y") = S(D where D is the discretization operator that sets D(x), = [[] for any continuous-time trajectory I₁. Recall that S is the Skorokhod solution operator.
The approximation, xD utilized in [9, 27] to bound discretization error.. The next lemmas show (({{))
how to bound Wi (x(((xx) ), [(x )) and W1 (C ((x{)) )) respectively. In particular, Lemma 6 is analogous Propositions 2.4 and 3.6 of [9] and Lemma 9 of [27]. These earlier works end up with bounds of (112/4/1/2 + log k). It is shown in [27] that such bounds can be translated into time- uniform bounds of the form (() The bound from Lemma 6 is of the form O1p) v1i log K), time uime-unform bound of the form O1)) (2).
and we will see in the next subsection that this leads Lemma 6, Assume that K. is a polyhedron with O in its interior. Assume that x = xB E K. and that [[]] [I] I There are constants, Cb, CG and ey such that for all integers k 2 0, the following
bound holds:
W1 (C(xE),
S [IX xPi1 & (cs + covS) nvk + oT V log(4k)
Lemma 7. Assume that IC is polyhedron with O in its interior. Assume that x =xp = x E K. and that B[[[x] SS s. Then for all integers 0, the following bound holds
W1 (E(x [(xP)) = EE [ xxII < ((0s + coVs) + o7 er (og(k)))))))
(enek - 1).
We highlight that Lemma 6 utilizes the rather tight bounds solutions Skorokhod problems over a polyhedral domain shown in Theorem 9. The derivation such tight bounds is one of the novelties of our work. More details will be discussed in Section 4 and Appendix A.
With all of the auxiliary processes defined and their differences, we have the following lemma, which gives time-dependent bound on Wi (2(x)) ((x{));
Lemma 8. Assume that K. is a polyhedron with in its interior. Assume that x5 = x E K. and that B||x Ill S S. There are constants, Co. 07 and cs. such that for all k 2 the following bound holds:
(I(C(x).. S ((cs Covo)) oT / logg())))))) en
Proof of Lemma 8
Recalling that x M.O xx and x M,++1 = xx M and using the triangle inequality
gives;
Wi ([(()),
Wx(C(x My"), L(x ),+t))
+ Wi (C(x ((x ((x
sm0
Lemmas 4 &
Σ
2012(s, 2) ke
200 (2)
(13)
Here 2/2 z) and 2 are the terms that bound the decay of probabilistic dependence between the Zy variables, as defined in (3).
Similarly, we bound
Wi (C( ((xx))
(L(x ) ((xP)) + WCx ((x
Lermans & (css + c Co + 07 logg(4k) 4k)
enck
(14)
Plugging the bounds from (13) and (14) into (11) proves the lemma, with cs = C5 + (z).
The proof of Lemma 3 is completed by showing how the time-dependent bound from Lemma 8 can be turned into a bound that independent of k. The technique used for this step based on ideas from [10], and is shown in Appendix G.
7

---

4 Quantitative bounds on Skorokhod solutions over polyhedra
In this section, we present result that enables our new bound between the continuous-time process x and the discretized process x when constrained to the set IC defined by:
K. = {z|a; x S by for i = m........
(15)
where a, unit vectors.
As discussed in Section 3.3, the bound in Lemma 6 improves upon the corresponding results in earlier works [9, 27J. The improvement arises from the use of Theorem 9 below, which utilizes the explicit polyhedral structure of to achieve a tighter bound than could be obtained for general convex constraint sets. It variation proof in [18] con-constructivv, and so there is no way to calculate the constants, whereas the proof in Appendix A is fully constructive and the constants can be computed explicitly.
earlier result from [18]. The main distinction is that the
Theorem 9. There constants Cg and E (0, 1/2] such that if x S(y) and x' S(y') are Skorokhod solutions on the polyhedral set K. defined by (15), then for all 2 0, the following bound holds:
sup | x',1 S (cg + 1) sup l1ys v.ll. 0S55t
05ast
Here
-6 ( rank(A)/2
and = [a] am] whose rows are the a. vectors.
5 Limitations
Our current work is restricted to polyhedral sets. In particular, Theorem requires the polyhedral assumption, and it is unclear Skorokhod problems satisfy similar bounds on any more general classes of constraint sets. As result, it is unclear if our main results projected Langevin algorithms can be extended beyond polyhedra. We also only considered constant step sizes, but in many cases decreasing adaptive step sizes are used in practice. Finally, the dependence of the external data variables is limited to the class of L-mixing processes, which does not include all the real-world dependent data streams. Furthermore, it can be difficult to check that data stream is L-mixing without requiring strong assumptions or knowledge about how it is generated.
Conclusions and future work
In this paper, we derived non-asymptotic bounds in I-Wasserstein distance for a constrained Langevin algorithm applied to non-convex functions with dependent data streams satisfying L-mixing as- sumptions. Our convergence bounds match the best known bounds of the unconstrained case up to logarithmic factors, and improve on all existing bounds from the constrained case. The tighter bounds are enabled by constructive and explicit bound on Skorokhod solutions, which builds upon an earlier constrsttuctive bound from [18]. The analysis of L-mixing variables followed by comparatively simple averaging method. Future work will examine extensions beyond polyhedral domains, higher-order Langevin algorithms, alternative approaches to handling constraints, such as mirror descent, and more sophisticated step size rules. More specifically, future work will examine whether the projection step, and thus Skorkhod problems, can be circumvented by utilizing different algorithms, such as those based on proximal LMC [7]. Additionally, applications to real-world problems such as time-series analysis and adaptive control will be studied.
Acknowledgments
This work was supported in part by NSF CMMI-2122856. The authors thank the reviewers for helpful suggestions for improving the paper.
8

---

References
[1] Kwangjun Ahn and Sinho Chewi. Efficient constrained sampling via the mirror mairov-langevin algorithm. arXiv preprint arXiv:2010.16212, 2020.
[2] SV Anulova and B Sh Liptser. Diffusional approximation for processes with the normal reflection. Theory of Probability & Its Applications, 55(3):411-425 1991.
[3] Krishna Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil Salim, and Shunshi Zhang. Towards a theory of non-log-concave sampling: first-order stationarity guarantees for langevin monte carlo. In Conference Learning Theory, pages 2896-2922 PMLR, 2022.
[4] Mathias Barkhagen, Ngoc Huy Chau, Eric Moulines, Miklós Rásonyi, Sotirios Sabanis, Ying Zhang, et al. On stochastic gradient langevin dynamics with dependent data streams in the logconcave case. Bernoulli, 27(1):1-33, 2021.
[5] Vivek S Borkar and Sanjoy K Mitter. A strong approximation theorem for stochastic recursive algorithms. Journal of optimization theory and applications, 100(3):499-513, 1999.
[6] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[7] Nicolas Brosse, Alain Durmus, Érie Moulines, and Marcelo Pereyra. Sampling from log- concave distribution with compact support with proximal Langevin Monte Carlo. arXiv preprint arXiv:1705.08964 2017.
[8] Sebastien Bubeck, Ronen Eldan, and Joseph Lehec. Finite-time analysis of projected langevin monte carlo. Advances in Neural Information Processing Systems, 18:1244-1255 2015.
[9] Sébastien Bubeck, Ronen Eldan, and Joseph Lehec. Sampling from log-concave distribution with projected langevin monte carlo. Discrete & Computational Geometry, 59(4):757-783, 2018.
[10] Ngoc Huy Chau, Éric Moulines. Miklos Rásonyi, Sotirios Sabanis, and Ying Zhang, On stochastic gradient langevin dynamics with dependent data streams: the fully non-convex case. arXiv preprint arXiv: /905. 13142, 2019.
[11] Xi Chen, Simon S Du, and Xin Tong. On stationary-point hitting time and ergodicity of stochastic gradient langevin dynamics. Journal of Machine Learning Research, 21(68):1-41, 2020.
[12] Xiang Cheng, Niladri S Chatterji, Yasin Abbasi-Yadkori, Peter L. Bartlett, and Michael I Jordan. Sharp convergence rates for langevin dynamics in the nonconvex setting. arXiv preprint arXiv:1805.016448 2018.
[13] Sinho Chewi, Murat A Erdogdu, Mufan Bill Li, Ruoqi Shen, and Matthew Zhang, Analysis of langevin monte carlo from poincar' e to log-sobolev. arXiv preprint arXiv:2 12662, 2021.
[14] William Coffey and Yu Kalmykov. The Langevin equation: with applications to stochastic problems in physics, chemistry and electrical engineering, volume 27. World Scientific, 2012.
[15] Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley Sons, 2012.
[16] Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and log- concave densities. Journal of the Royal Statistical Society: Series (Statistical Methodology), 79(3):651-678 2017.
[17] Arnak S Dalalyan and Alexandre B Tsybakov. Sparse regression learning by aggregation and langevin monte-carlo. Journal of Computer and System Sciences, 78(5): 2012.
[18] Paul Dupuis and Hitoshi Ishii. On iynsinitzccomiinuityy of the solution mapping to the skorokhod problem, with applications. Stochastics: An International Journal of Probubility and Stochastic Processes, 35(1):31-62 1991.

---

[19] Alain Durmus, Eric Moulines, et al. Nonasymptotic convergence analysis for the unadjusted langevin algorithm. The Annals of Applied Probability, 27()):151-1587, 2017.
[20] Andreas Eberle. Reflection couplings and contraction rates for diffusions. Probability theory and related fiels, 166(3-4):851-888) --66, 2016.
[21] Murat A Erdogdu, Lester Mackey, and Ohad Shamir. Global non-convex optimization with discretized diffusions. In Advances in Neural Information Processing Systems, pages 9671-9680, 2018.
[22] Murat A Erdogdu, Rasa Hosseinzadeh, and Shunshi Zhang. Convergence of langevin monte carlo in chi-squared and rényi divergence. In International Conference on Artificial Intelligence and Statistics, pages 8151-8175. PMLR, 2022.
[23] Saul B Gelfand and Sanjoy K Mitter. Recursive stochastic algorithms for global optimization in r'd. SIAM Journal Control and Optimization, (01)),99-1118, 1991.
[24] László Gerenesér. On a class of mixing processes. Stochastics: An International Journal of Probability and Stochastic Processes, 2663):665-11, 1989.
[25] Ya-Ping Hsieh, Ali Kavis, Paul Rolland, and Volkan Cevher. Mirrored langevin dynamics. Advances in Neural Information Processing Systems, 31:2878-2887, 2018.
[26] Walid Krichene and Peter L Bartlett, Acceleration and averaging in stochastic mirror descent dynamics, arXiv preprint FrXiv:17770062111 2017.
[27] Andrew Lamperski. Projected stochastic gradient langevin algorithms for constrained sampling and non-convex learning. In Conference on Learning Theory, pages 2891-2937, PMLR, 2021.
[28] Joseph Lehec. The langevin monte carlo algorithm in the non-smooth log-concave case. arXiv preprint arXiv:2101. 2021.
[29] Tyler Lekang and Andrew Lamperski. Wasserstein contraction bounds closed convex domains with applications to stochastic adaptive control. In JEEE Conference on Decision and Control (CDC), 2021. Accepted, available at https://arra wwweev..rg//bbbbee arggabs//100/g// 12198.
[30] Ruilin Li, Hongyuan Zha, and Molei Tao. Sqrt (d) dimension dependence of langevin monte carlo. arXiv preprint
2021.
[31] Torgny Lindvall and LCG Rogers. Coupling of multidimensional diffusions by reflection. The Annals of Probability, pages 860-872, 1986.
[32] Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I Jordan. Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 116(42): 20881-20885, 2019.
[33] Mateusz B Majka, Aleksandar Mijatović, and Lukasz Szpruch. asm-tsymptotic bounds for sampling algorithms without log-concavity. arXiv preprint arXiv: 105, 2018.
[34] Dao Nguyen, Xin Dang, and Yixin Chen. Unadjusted langevin algorithm for non-convex weakly smooth potentials. arXiv preprint arXiv:2101.06369 2021.
[35] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamies: a nonasymptotic analysis. arXiv preprint 17020170,,,3849, 2017.
[36] Srinivasa Ramanujan. The lost notebook and other unpublished papers. Bull. Am. Math. Soc, 19:558-560, 1988.
[37] Gareth O Roberts, Richard L Tweedie, et al. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, 2(4):341-36) 1996.
[38] Ralph Tyrell Rockafellar. Convex Analysis, volume 36. Princeton University Press, 2015.
[39] Kanji Sato, Akiko Takeda, Reiichiro Kawai, and Taiji Suzuki. Convergence ervor analysis of reflected gradient langevin dynamics for globally optimizing non-convex constrained problems. arXiv preprint arXiv: 2022.
10

---

[40] Hiroshi Tanaka. Stochastic differential equations with reflecting boundary condition in convex regions. Hiroshima Mathematical Journal, 91):163-177 1979.
[41] Santosh S Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. arXiv preprint arXiv:1903.08350 2019.
[42] Xiao Wang. Qi Lei, and Ioannis Panageas. Fast convergence of langevin dynamics manifold: Geodesics meet log-sobolev. Advances in Neural Information Processing Systems, 33, 2020.
[43] Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-11), pages
68 1-188 2011.
[44] Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of langevin dynamics based algorithms for nonconvex optimization. Advances in Neural Information Processing Systems, pages 31 1126-3137, 2018.
[45] Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, and Marcelo Pereyra. Wasserstein control of mirror langevin monte carlo. arXiv preprint arXiv:2002.04363. 2020.
[46] Difan Zou, Pan Xu, and Quanquan Gu. Faster convergence of stochastic gradient langevin dynamics for non-log-concave sampling. In Uncertainty in Artificial Intelligence, pages 1152- 1 1162. PMLR, 2021.


Reviews:
[{"review_id": "z_B--AlSmpx", "reviewer": "Reviewer_RTV8", "summary": "This paper gives W_1 convergence guarantees for the constrained Langevin algorithm with stochastic gradients over a polyhedral constraint set. The assumption on the target function is that it is Lipschitz everywhere and strongly convex outside of a ball; moreover, the stochastic gradients are not i.i.d., but rather are obtained from an L-mixing process (which quantifies the amount of dependence in the noise). Similar problems have been studied before on more general constraint sets, but in the case of a polyhedral constraint set this paper obtains the sharpest bound thus far. The main challenge in this work is the mathematical difficulty associated with studying SDEs reflected at the boundary.", "questions": "None.", "limitations": "In the paper, quantitative dependence on problem parameters such as the dimension is not made explicit until the appendix. This is an issue because several parameters are quite large, e.g., there is an exponential dependence on the radius R of the ball without strong convexity, and an exponential dependence on the rank of the matrix specifying the polytope constraints. For the former, this is a standard feature of works which make the “strongly convex outside ball” assumption, but nevertheless such exponential dependence should be discussed clearly in the main text (especially since the abstract claims to handle non-convex functions, but realistically these bounds are quite poor for very non-convex functions). In particular, the contraction factor a is one of the most important parameters and an explicit bound on a should appear in the main text.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper makes a good contribution to a challenging problem. Technically, the analysis is quite similar to that of the prior work [24], which dampens the novelty. However, I believe that this is outweighed by the virtue of analyzing the projected Langevin algorithm, for which quite little is known. I also found the writing to be clear.\n\nAnother notable weakness is the lack of theoretical comparisons with other approaches, such as proximal LMC [5]. I understand that the settings considered in prior works may differ from the one considered here, but nevertheless it would be helpful to include a discussion on whether techniques in those other works can be expected to apply to this setting, especially since the other approaches avoid the technicalities involved in the Skorokhod problem.\n\nSpecific Comments:\n- Line 107, typo in the Lipschitz gradient assumption\n- Line 691 in supplement, typo: or -> of", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RV0n2SvFb4n", "reviewer": "Reviewer_6kMS", "summary": "This paper studies the problem of non-asymptotic convergence guarantees in 1-Wasserstein distance for projected Langevin Monte Carlo with (unbounded) polyhedral constraints, non-convex losses and L-mixing data. The convergence rate $O(T^{-1/2}\\log T)$, is faster than the previous works on constrained Langevin algorithms in the literature. ", "questions": "(1) On page 2 and page 3, I suggest the author(s) to define 1-Wasserstein distance and the polyhedral just in case some of the less theoretical readers are not familiar with these concepts.\n\n(2)  The authors should discuss or make some comments about the assumption in Section 2.4. You assumed that $\\bar{f}(x)$ is $\\mu$-strongly convex outside a ball of radius $R>0$. This can be confusing to some readers who are not familiar with such assumptions because on the surface it gives the readers the impression that you are assuming almost strong-convexity whereas in the abstract you are claiming that you are doing non-convex learning. Please provide some references and comments on whether this is a common assumption, and whether it is equivalent for example to dissipativity condition in the literature.\n\n(3) You mentioned that most of the novel work in the paper focuses on deriving Lemma 3 and you provided Section 3.3 for a proof overview for Lemma 3. But I think what would really be nice is to provide some high-level general discussions in plain English either before Section 3.3. or at the beginning of Section 3.3 about the novelty of your techniques to obtain Lemma 3 as well as the high-level descriptions of the steps needed to achieve Lemma 3.\n\n(4) Journal names etc. should be capitalized in the reference. For example, the journal name in [4] should be capitalized. Also in [6] and [9], langevin should be Langevin.", "limitations": "Indeed, the author(s) included a section near the end of the paper discussing the limitations of their work. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a solid theoretical paper and the analysis seems rigorous. This paper obtains the problem of non-asymptotic convergence guarantees in 1-Wasserstein distance for projected Langevin Monte Carlo with (unbounded) polyhedral constraints, non-convex losses and L-mixing data, with the convergence rate $O(T^{-1/2}\\log T)$ that is faster than the previous works on constrained Langevin algorithms in the literature. My understanding is that the paper has made the following contributions (1) the convergence rate is faster than the previous works for constrained Langevin algorithms (2) the continuous-time convergence rate in 1-Wasserstein distance extends some existing literature to allow reflected boundary (3) novel discretization error bound where the constraint can be unbounded. \n\nThere are several weaknesses of the paper that makes me question the technical novelty and the significance of the contributions of the paper.\n\n(1) Even though the results are new, similar analysis for non-convex learning for projected Langevin algorithms has already been appeared in [24] for example. The author(s) should do a better job at explaining what are the technical novelties and innovations that allow them to improve the convergence rate and allow the result to work on unbounded constraint set.\n\n(2) In the model, there is a scaling parameter $\\beta$, that is known as the inverse temperature. When you are doing sampling, you can simply let $\\beta=1$. But when you need to use Langevin algorithms to solve a non-convex optimization problem, you need to have large $\\beta$ in order for the Gibbs distribution to concentrate around the global minimizer of the target; see e.g. [30]. The authors at least should comment on the order of dependence of the constants on $\\beta$ and whether it is possible to allow $\\beta$ to be large to be used for non-convex optimization. Moreover, Theorem 1 is a result that can be used for sampling for non-log-concave target distribution, but can you use the ideas from [30] to obtain results for empirical risk minimization/population risk minimization? It is not clear to me because your result is in 1-Wasserstein and the constraint set is unbounded. In some sense, it is not clear to me your 1-Wasserstein result can lead to any non-convex optimization guarantees on an unbounded domain.\n\n(3)  In Lemma 7, Lemma 8, the error bound has the term $e^{\\eta\\ell k}$, where $\\ell$ is the parameter of the $\\ell$-smoothness of the target, $\\eta$ is the stepsize and $k$ is the number of iterates. The authors should comment on how tight/good these bounds are. I am a bit worried that these are too loose. For example, to make Langevin algorithm work, you need the continuous time dynamics to be close to the invariant distribution, also known as the Gibbs distribution, which requires $\\eta k$ to be large. But if $\\eta k$ is large, then the error bounds in Lemma 7 and Lemma 8 are exponentially bound. The discretization error bound in [30] does not have exponential dependence on $\\eta k$ and it would certainly be great if the author(s) can improve upon this.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LWRuIv1_Zaa", "reviewer": "Reviewer_xdj5", "summary": "Authors study the problem of constrained sampling guarantees for the projected Langevin algorithm in a non-asymptotic sense in Wasserstein 1 metric.", "questions": "Q1: What is the dimension dependence of this convergence guarantee?\n\nQ2: What is the motivation for sampling from the Gibbs potential \\bar{f}? Is this related to a Bayesian posterior sampling problem or any practical sampling problem? Is it only for obtaining non-convex optimization guarantees?\n\nQ3: What is the benefit of using Eberle's result instead of a functional inequality based approach such as LSI + Holley-Stroock as in Vempala&Wibisono if the dimension dependence is already exponential?", "limitations": "See the section \"Strengths and Weakness\".", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths:\n+The paper is well written and the proofs look correct as far as I can tell.\n+ Improves the previously known rates under milder conditions.\n\n- Weakness:\n+ Major concern 1: Lack of motivation in the solved problem.\n+ Major concern 2: it is not clear how the dimension and other problem parameters interact with the convergence rate. Since the authors are relying on Eberle's reflection coupling, the dimension dependency will be exponential, e.g. exp{LR^2}.\n+ Insufficient recent sampling literature review: Unconstrained sampling with Langevin algorithm is a well studied problem, especially under quadratic growth conditions that the current paper is making. Authors cite a few papers from 2017 referring to them as recent, yet there has been a lot of progress since then. \n\n- Minor concerns:\nI listed a few typos that I noticed below.\n+ l20 Deep Neural networks\n+ l107 missing \\nabla \n+l133 the interpolation process is not properly defined, so is the Brownian motion (and its filtration).\n+l85 before ever mentioning about f, we are introduced its gradient. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3fVWpGPMLPY", "reviewer": "Reviewer_JNhe", "summary": "The paper aims at deriving new bounds for langevin algorithms in some specific cases, showing that the bound of convergence it attains is better than previously obtained in the literature.\nIt focuses on obtaining new 1-Wasserstein distance for non-convex losses with L-mixing data variables and polyhedral constraints, showing that the rate of convergence is faster.", "questions": "My main question to the authors is can you find a practical case where the bound they obtain begins to be optimal, especially with respect to the rest of the literature ? Which would validate and motivate to my mind the impressive theoretical work you show.", "limitations": "The limitations are we’ll described by the authors  and are mainly the specificity of the results.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is technically well  written and presents a novel bound for Langevin algorithms. The math is advanced and the proof technically difficult. \nFurthermore, the paper is well organized and the derivation is clear.\nI checked some of the proofs which were very involved and the resulting paper is impressive theoretically.\n\nThe main weaknesses of the paper are to my mind thelimitation to the specific case with L-mixing data variables and polyhedral constraints, which is  Unfortunately not supported by a practical example to show the relevance of the approach proposed by the authors. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept