Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization
Authors: Yuri Kinoshita
Taiji Suzuki
Venue: NeurIPS 2022 Accept (2022)
Keywords: stochastic gradient Langevin dynamics
variance reduction
log-Sobolev
SGLD
SVRG-LD
SARAH

Abstract: The stochastic gradient Langevin Dynamics is one of the most fundamental algorithms to solve sampling problems and non-convex optimization appearing in several machine learning applications. Especially, its variance reduced versions have nowadays gained particular attention. In this paper, we study two variants of this kind, namely, the Stochastic Variance Reduced Gradient Langevin Dynamics and the Stochastic Recursive Gradient Langevin Dynamics. We prove their convergence to the objective distribution in terms of KL-divergence under the sole assumptions of smoothness and Log-Sobolev inequality which are weaker conditions than those used in prior works for these algorithms. With the batch size and the inner loop length set to $\sqrt{n}$, the gradient complexity to achieve an $\epsilon$-precision is $\tilde{O}((n+dn^{1/2}\epsilon^{-1})\gamma^2 L^2\alpha^{-2})$, which is an improvement from any previous analyses. We also show some essential applications of our result to non-convex optimization.

Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization
Yuri Kinoshita
Department of Mathematical Informaties, Graduate School of Information Science and Technology,
The University of Tokyo, Tokyo, Japan yuri- yuri-Kinoshitall100 ecc. u-tokyo. ac.jp
Taiji Suzuki
Department of Mathematical Informatics,
Graduate School of Information Science and Technology,
The University of Tokyo, Tokyo, Japan Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan taijimmist. i. u-tokyo..aa ac.
Abstract
The stochastic gradient Langevin Dynamics one of the most fundamental gorithms to solve sampling problems and non-convex optimization appearing in several machine learning applications. Especially, its variance reduced versions have nowadays gained particular attention. In this paper, we study two variants this kind, namely, the Stochastic Variance Reduced Gradient Langevin Dynam- ics and the Stochastic Recursive Gradient Langevin Dynamics. We prove their convergence to the objective distribution in terms of KL-divergence under the sole assumptions of smoothness and Log-Sobolev inequality which weaker conditions than those used prior works for these algorithms. With the batch size and the inner loop length set /n, the gradient complexity achieve e-precision Ö((n previous analyses. We also show some essential applications of our result to non-convex optimization.
which an improvement from any
1 Introduction
Background and Organization
Over the past decade, the gradient Langevin Dynamics (GLD) has gained particular attention for providing an effective tool for sampling from Gibbs distribution, a fundamental task omnipresent in the field of machine learning and statistics, and for non-convex optimization, which is nowadays witnessing an unignorable empirical success. Notably, GLD a stochastic differential equation (SDE) (KL) divergence towards the
that be viewed the steepest descent flow of the Kullback-Leibe stationary Gibbs distribution in the space of measures endowed with the 2- 2-Wasserstein metric (Jordan al., 1998). As consequence of the unique properties of GLD, its implementable discrete schemes and their ability to suitably track it have been the subject large number of studies.
The Buler-Maruyann scheme of GLD gives rise to an algorithm known as the Langevin Monte Carlo method (LMC). This algorithm biased (Wibisono, 2018): that is, the distribution of the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

discrete scheme does not converge to the same as GLD. Nonetheless, it has been shown that this bias could be made arbitrarily small under certain assumptions by taking a sufficiently small step size (Dalalyan, 2017b; Vempala and Wibisono, 2019). Dalalyan (201 7a.b) provided one of the first non-asymptotic rates of convergence of LMC for smooth log-concave distributions. Assumptions to obtain a non-asymptotic analysis and this controllable bias have been relaxed by further research to dissipativity and smoothness (Raginsky et al., 2017; Xu et al., 2018), and recently to Log-Sobolev inequality (LSI) and smoothness (Vempala and Wibisono, 2019). This relaxation of conditions is especially meaningful as the objective distribution nowadays tends to become more and more complicated beyond the classical assumption of log-concavity.
However, in the field of machine learning, the main function can often be formulated as the average of the loss function of an enormous number of training data points (Welling and Tch, 2011), which subsequently makes it difficult to calculate its full gradient. As a result, research on stochastic algorithms has been also conducted to avoid this computational burden (Chen et al., 2021; Dubey et al., 2016; Raginsky et al., 2017; Welling and Teh, 2011; Xu al., 2018; Zou et al., 2018, 2019a,b, 2021). Welling and Teh (2011) 1) introduced the concept of Stochastic Gradient Langevin Dynamics (SGLD) which combines the Stochastic Gradient Descent with LMC. This has been the subject of successful studies (Raginsky et al., 2017; Welling and Teh, 2011 I; Xu et al., 2018). Nevertheless, the variance of its stochastic gradient is too large, which leads to a slow convergence compared to LMC. Therefore, stochastic gradient Langevin Dynamics algorithms with variance reduction, such as the Stochastic Variance Reduced Gradient Langevin Dynamics (SVRG-LD), have been considered and their convergence has been thoroughly analyzed for both sampling (Dubey et al., 2016; Zou et al., 2018, 2019a, 2021) and optimization (Huang and Becker, 2021; Xu et al., 2018).
Dubey et al. (2016) first united SGLD with variance reduction techniques and proposed two new algorithms, namely, SVRG-LD and SAGA-LD. Chatterji et al. (2018) and Zou et al. (2018) proved the convergence rate of SVRG-LD to the target distribution in 2-Wasserstein distance for smooth log-concave distributions. Xu et al. (2018) showed the weak convergence of SVRG-LD under the smoothness and dissipativity conditions. They expanded the non-asymptotic analysis of Raginsky et al. (2017) to LMC and SVRG-LD, and improved the result for SGLD. Few years ago, Zou et al. (2019a) provided the gradient complexity of SVRG-LD to converge to the stationary distribution in 2- Wasserstein distance under the smoothness and dissipativity assumptions. This convergence can be even improved if make warm-start (Zou et al., 2021). While these works investigated algorithms with fixed hyperparameters, Huang and Becker (2021) additionally assumed a strict saddle and some other minor conditions study SVRG-LD with a decreasing step size and improved its convergence in high probability to the second order stationary point. Zou et al. (2019b) also applied variance reduction techniques to the Hamiltonian Langevin Dynamies, or underdamped Langevin Dynamics in opposition to GLD also known as overdamped Langevin Dynamics. As we can observe, the current convergence analyses of the stochastic schemes with variance reduction are mostly restricted to log-concavity and dissipativity, and do not enjoy the same broad convergence guarantee with a concrete gradient complexity as LMC does under LSI and smoothness in terms of KL-divergence.
Therefore, in order to bridge this theoretical gap between LMC and stochastic gradient Langevin Dynamies with variance reduction, relaxed assumptions of smoothness and LSI. In Section 3, we study the convergence to the Gibbs distribution of SVRG-LD and the Stochastic Recursive Gradient Langevin Dynamics (SARAH-LD), another variant of stochastic gradient Langevin Dynamics with variance reduction inspired by the Stochastic Recursive Gradient algorithm (SARAH) of Nguyen et al. (2017a,b). On the other hand, optimization and sampling are only two sides of the same coin for GLD. That is why, in Section 4, we also investigate implications of Section 3 for non-convex optimization. We prove the convergence of SVRG-LD and SARAH-LD to the global minimum of dissipative functions and we provide their aon-asympooiic rate of convergence. We also consider the additional Morse assumption and study its effect. Finally, we illustrate our main result with simple experiment.
study in this paper the convergence of the latter under the
1.2 Contributions
The major contributions of this paper can be summarized as follows. We provide a non-asymptotic analysis of the convergence of SVRG-LD and SARAH-LD to the Gibbs distribution in terms of Ki-ddieeeeecce under smoothness and LSI which are weaker conditions than those used in prior works for these algorithms. KL-divergence is generally stronger convergence criterion than both total
2

---

Table 1: Comparison of our main result with prior works (sampling). The first three works are about LMC. Compared to Vempala et al. (2019), with the same assumptions and criterion, the order of gradient complexity is improved from n to vn. The others are about SVRG-LD except the last one which is about the Stochastic Gradient Hamiltonian Monte Carlo Methods with Recursive Variance Reduction. c is the accuracy required on the criterion, d is the dimension of the input of the main function, n is the number of data points, and L is the smoothness constant, 2-Wass. stands for "2-Wasserstein", and conv. stands for "convergence". poly(M, L) stands for polynomial of M and
Method
Major Assumptions
Criterion"
Gradient Complexity"
Dalalyan (2017a)
Smooth, Log-coneave (M)
2- Wass.
6 2 poly(M.L))
Xu et al. (2018)
Smooth, Dissipative
Weak conv.
Ö( (4) (iii)
Vempala et al. (2019)
Smooth, Log-Sobolev (a)
KI.
o 1.2 -)
Zou et al. (2018)
Smooth, Log-concave (M)
2- Wasss,
0 (I+ 1//2,,12,1/21
1r3/2,
Zou et al. (2019a)
Smooth, Dissipative
2- Wass.
o(+ 22- =14²) ocT+)))
Zou et al. (2021)
Smooth, Dissipative, Warm-start
TV
0(22) oli))
Zou et al. (2019h)
Smooth, Dissipative
2-Wass.
ò (1+ 233733 )n 1:
11/2
This paper
Smooth, Log-Soboles (a)
KL
ō 6((+ 72² 32=
variation (TV) and 2- Wasserstein distance as they can be controlled by KL-divergence under the LSI condition. Notably, we prove that, with the batch size and inner loop length set to vn. the gradient complexity to achieve an e-precision in terms of KI-divergence is Ö((n + 32,, which is better than any previous analyses. See Table for a comparison with previous research in terms of assumptions, criterion and gradient complexity. We also prove the convergence of SVRG- LD and SARAH-LD to the global minimum under an additional assumption of dissipativity with a gradient complexity of Ö((n + n 1/2 dLa -1 2)>2L'a which is better than previous work since has almost all the time a dependence
n of O(vr) and does not require the batch size and the inner loop length to depend on the accuracy e. On the other hand, we import the idea of Li and Erdogdu (2020) from product manifolds of spheres to the Fuclidean space in order show that under the additional assumption of Morse, the convergence in the Euclidean space can be accelerated by eliminating the exponential dependence on 1/c.
1.3 Other Related Works
The theoretical study of GLD goes back to Chiang et al. (1987) who showed that global convergence could be achieved with a proper annealing schedule. This work did not specify how to implement this SDE, but Gelfand and Mitter (1991) filled this gap. Later, Borkar and Mitter (1999) proved an asymptotic convergence in terms of relative entropy for the discrete scheme of gradient Langevin Dynamics when the inverse temperature and the step size are kept constant.
The variance reduction technique, introduced to Langevin Dynamics by Dubey al. (2016), was orig- inally presented by Johnson and Zhang (2013) as Stochastic Variance Reduced Gradient (SVRG) to improve the convergence speed of Stochastic Gradient Descent. Other variance reduction techniques were also considered such as the Stochastic Recursive Gradient Langevin Dynamics (SARAH) from Nguyen et al. (2017a,b) which outperforms SVRG in non-convex optimization (Pham et al., 2020) and is used in many algorithms such as SSRGD (Li, 2019) and SpiderBoost (Wang et al., 2019).
Li and Erdogdu (2020) extended Vempala and Wibisono's result to Riemannian manifolds. One of the highlights of their work is that they showed the Log- Log-Sobolev constant of the Gibbs distribution for a product manifold of spheres only depends some particular conditions including Morse. We will adapt this result to our situation.
polynomial of the inverse temperature under
In the concurrent work of Balasubramanian et al. (2022) (especially Section 6), they also studied the convergence of stochastic schemes of GLDD with more relaxed conditions than prior analyses. However, our contributions not overshadowed by theirs, and we clarify the reasons. In Subsection
3

---

6.1 of their paper, Balasubramanian et al. (2022) focused on stochastic discrete schemes with finite variance and bias (which is not the case for SVRG-LD) and provided a first-order convergence guarantee in the space of measures equipped with the 2- 2-Wasserstein distance. Subsection 6.2 proved a global convergence under some other conditions but most of these two analyses did not consider in particular the usual case in machine learning when F is the average of some other functions, which leads to a generally worse gradient complexity than ours. Concerning this finite sum setting, Balasubramanian et al. (2022) investigated the Variance Reduced LMC algorithm (slightly different from SVRG-LD in this paper) in Subsection 6.3 and gave a first-order convergence under the sole assumption of smoothness. When restrained in our problem setting, the gradient complexity of SVRG-LD and SARAH-LD we provide is still considerably better (see Section 3 for more details).
1.4 Notation
We denote deterministic vectors by lower case symbol (e.g.. x)) and random variables by an upper case symbol (e.g., X). The Euclidean norm is denoted by || - for vectors and the inner product by (.-)) For matrices, || is the norm induced by the Euclidean norm for vectors. We only treat distributions absolutely continuous with respect to the Lebesgue measure in Rd for simplicity. Especially, throughout the paper, v refers to the probability measure with the density function dv x o->Pdr, where F is function introduced below. V ò is equivalent max bj and A b to min(a,br We also use the shorthand Ô hide logarithmic polynomials.
Preliminaries
In this section, we briefly explain the problem setting, necessary mathematical background and assumptions used in this paper.
2.1 Problem Setting and GLD
In Section 3, we consider sampling from a distribution written in the form du xx e- dx where y is positive constant (which corresponds to the inverse temperature) and F R2 R is formulated as F(x) == 1 Ei= fi()),, the average of the loss function of n training data points (-:(1) Here, [((x) [(, (0) can be regarded the loss of data (0()) For instance, I can be the average of the negative log likelihood of n training data points. In Section 4, we consider the non-convex optimization (minimization) of the same F as above.
Fi=1-
GLD can be described as the following stochastic diffcrential equation (SDE):
dx.CDD VF ddt + B()
(1)
where 7 >> 0 is called the inverse temperature parameter and (B(t))22 is the standard Brownian motion in Rd. It can be used for sampling since under some reasonable assumptions of F, the distribution GGLD of XCLD governed by SDE (1) converges to the invariant stationary distribution dv & e x dr. also known the Gibbs distribution (Chiang et al., 1987). Moreover, previously mentioned, this convergence efficient in the sense that SDE (1) corresponds to the steepest descent flow of the Kullback-Leibler (KL) divergence towards the stationary distribution in the space of measures endowed with the 2- 2-Wasserstein metric (Jordan et al., 1998). Alternatively, GLD can be interpreted as the composite optimization problem of negative entropy and expected function value as follows (Wibisono, 2018):
min gidensity
E,[7F] + E. [log 4].
The gradient flow is the well-known Fokker-Planne Planck equation associated to SDE (1):
OLDLD
V Ap (GGDDVF) 1 A
-v. GLD = 7 (DGLLD
GLD
V log
0t
This will be useful in our analysis. In addition to its potential for sampling, GLD can also be employed for non-convex optimization as the Gibbs distribution concentrates on the global minimum of F for sufficiently large values of y (Hwang, 1980).

---

Algorithm 1: SVRG-LDD SARAH-LD
input: step size 1) > 0, batch size B, epoch length m, inverse temperature 7
2 initialization: X, = 0, x Xy
foreach = 0, 1, ..., (K/m) do
Usm VF(((s))
randomly draw Esm ~ N NN,, Ldxd)
X.m+1= = Xam sm + v /2///n/nnn 7eam
foreach 1 ,
do
k +
randomly pick a subset 1 from {I,..., nn of size 14l = B randomly draw E N (0, Laxa)
10
11
SVRG-LD then
Uk = =# Eine (Vii, (Xx. - V.s + Usm
12
13
else if SARAH-LD then
14
UK- B Einen (V (X&) (X uk-1
15
end
16
X = Xx nu + 2
17
end
((++1) = X ((+1))
18
19
end
2.2 Algorithms of GLD
Applying the Euler-Maruyama scheme (I), we obtain the Langevin Monte Carlo (LMC)
X8+1 Xx - 7)VP((x)) 2nn
where n) called the step size. This is similar to the gradient descent except the additional Gaussian noise / /2n/7eg, where ex ~ (O, laxa) and laxa is the x d unit matrix. the case ni is huge and the computation of V is too difficult, we are incited to use stochastic gradient methods in analogy to stochastic gradient optimization. This gives
X X (X((x)) + 22n//
where v(Xg) is the stochastic gradient. When ((xx) is defined Eiter f4x where B is called the batch size and I is random subset uniformly chosen from (1, (1....,7)) n) such that | = B, we obtain the Stochastic Gradient Langevin Dynamics (SGLD). As this method exhibits a slow convergence, has been popular use variance reduction methods such as the Stochastic Variance Reduced Gradient Langevin Dynamics (SVRG-LD) where v(Xa) B Eiien, (V (V,,,(X.) - Vi, (x(+))) + VF((())). Details of this algorithm stated in Algo- 1
rithm I. (*) is reference point updated every m steps that X (*), As can observe in Lemma A.4, around the optimal point, the variance of the stochastic gradient is indeed decreased as (*) and X2 are both close to each other. We can also casily extend some successful stochastic gradient algorithms Langevin Dynamics. Hence, sive Gradient Algorithm (SARAH) to Langevin Dynamics since we can expect that some bottlenecks of the analysis of SVRG-LD can be removed in that of SARAH-LD subtracting the previous stochastic gradient enables stabler performance than SVRG-LD. This algorithm can be described as Algorithm with v(Xx) Y/2 Σi,er, (V (Xx) (xx,(x)))) + v(Xx-1).
motivated extend the Stochastic Recur-
We define Pk the distribution of X generated the kth step of SVRG-LD, and similarly Φx for SARAH-LD.
Definition 1.
2.3 Assumptions
The assumptions used throughout this paper can be summarized as follows. Assumption 1. For all = 1...., n, S twice differentiable, and Va. y E Rd. [V*](>)]] s I. In other words. fo (i 1, 1,...,n) n) and F are L-smooth.

---

Assumption 2. Distribution v satisfies the Log- Log-Sobolev inequality (LSI) with a constant a. That is, for all probability density functions p absolutely continuous with respect to v, the following holds:
1 Jo(p), 20x
Ho(p) S
where (p) =
Ex llg Ll is the KL-divergence of with respect to v, and Ju(p) ==
Ep | log =1(]] is the relative Fisher information of p with respect
The recent work of Vempala and Wibisono (2019) motivates us to use the combination of smoothness and LSI for the analysis of SVRG-LD and SARAH-LD, Indeed, they showed that these conditions were enough to assure for the Fuler-Maruyama scheme an exponentially fast convergence and a bias controllable by the step size. Under smoothness, LSII is not only the necessary condition of log- concavity and dissipativity, but is also robust to bounded perturbation and Lipschitz mapping, contrary to log-concavity (Vempala and Wibisono, 2019). For example, for any distribution dy that satisfies LSI and bounded function : R + IR, dū xx e satisfies LSI as well (Holley and Stroock, 1986). Moreover, while KL-divergence is not in general convex with regard to the Wasserstein geodesic, thanks to LSI, the realize exponential convergence for the of continuous time Langevin Dynamics (Vempala and Wibisono, 2019). That is why, it is actually both useful and natural to suppose LSI in this context. Note that under T-smoothness of F and LSI with constant a for de x e da, it holds that a S y (Vempala and Wibisono, 2019).
condition is satisfied. It is well- that LSI suffices to
As for optimization, we additionally use the following conditions. Assumption
(M, -iiisiipateeve That is, there exist constants M and b > such that for all Rdd the following holds: (Vx)) 2 M M|==2|2 b.
Assumption (Li and Erdogdu (2020), Assumption 3.3 adapted). F satisfies the Morse condition. That is, for all eigenvalues of the Hessian of stationary points, there exists constant At E (0, such that
VF = 0, i d.....dJ. Furthermore, for the S of stationary points that are a global minimum, supzes Amin (V²P(x)) -
At S inf { (|, (V²F(x))
Assumption 5. f ft is L'piihhciizz and without loss of generality, we let mingere F(x)= = 0.
Assumption 6. F has a unique global minimum.
Smoothness and dissipativity setting (Raginsky et al., 2017; Xu et al., 2018; Zou et al., 2019a). We assume dissipativity instead of LSI for non-convex optimization in order to obtain explicit value of the Log-Sobolev constant of du x e dx in function of the inverse temperature parameter " (see Property C.3), making a non-asymptotic analysis possible. Furthermore, Assumptions 4 to 6 can ameliorate the exponential dependence of the inverse of the Log-Sobolev constant on the inverse temperature parameter to polynomial one (see Property C.4).
classical combination of assumptions for this kind of problem
3 Main Results
In this section, we state our main results which prove that SVRG-LD and SARAH-LD (Algorithm 1) achieve exponentially fast convergence to the Gibbs distribution and controllable bias in terms of KL-divergence under the sole assumptions of LSI and smoothness. We provide their gradient complexity as well. The proofs can be found in Appendix A and B respectively.
3.1 Improved Convergence of SVRG-LD
Our analysis shows that the convergence of SVRG-LD the stationary distribution du e- dr can be formulated as the theorem below.
Theorem 1. Under Assumptions 1 and 2, 0 < 16/6L/my 2 1 and B 2 m, for all
.. the following holds in the update of SVRG-LD where E = Bin-1)
[n B)
(px) se- 3c- + 22AmydL2
(2 + 33 + 2m
3a

---

We observe that the bias term of the upper bound, which is the second term linearly dependent on can be easily controlled while the first term exponentially converges to with + cc. This is more precisely formulated in the following corollary.
Corollary 1.1. Under the same assumptions Theorem for all 2 0, if we choose step size
Sae ti such that rj S 448,d12, then a precision (pk) S e reached after k Z 2 log 2Hv(po) steps.
Especially, if we take B m /n and the largest permissible step size 1j 16V6122/07 118dLA7'
3
then the gradient complexity becomes
((1x dn
2²1²2 a²
This gradient complexity is an improvement compared with prior works for three reasons. First of all, we provide non-asymptotic analysis of the convergence of SVRG-LD under smoothness and Log- Sobolev inequality which are conditions weaker than those (e.g.. log- concavittv or dissipativity) used in prior works for these algorithms. Morcover, a stronger convergence criterion than both total variation (TV) and 2- 2-Wasserstein distance as they can both be controlled by KL-divergence under the LSI condition. For instance, TV was used by Zou et al. (2021) and 2- Wasserstein distance by Dalalyan (201 and Zou et al. (2019a). KL--divergence makes it possible to unify these two different criteria. Finally, while prior research generally used Girsanov's theorem which generates a bias term that accumulates through the iteration (see for example Raginsky al. (2017) and Xu et al. (2018)), we solve this issue by taking benefit of the exponential convergence of GLD to the Gibbs distribution under LSI and smoothness that enables us to forget about past bias. That way, with the batch size and inner loop set to vni, the gradient complexity to achieve an e-precision in terms of KL-divergence becomes Ö((n + dn E/ " })2 than previous analyses. For example, Vempala and Wibisono (2019) provided a gradient complexity 2) for LMC under Assumptions 1 and 2, and Zou et al. (2019a) a gradient
prove it in terms of KL-divergence which is generally
L ?). which is better
of Ô complexity of Ö(n + 2 that the dependence on the dimension d is not improved since -1 may exponentially depend on d. Recently, Zou et al. (2019b) proposed the Stochastic Gradient Hamiltonian Monte Carlo Methods with Recursive Variance Reduction with gradient complexity of Ö((n + n2 "u, 3/2) A p. 2 in terms of 2-Wasserstein distance. Even though their algorithm is based on the underdamped Langevin Dynamics whose discrete schemes use to perform better than those of the overdamped Langevin Dynamics such as SVRG-LD, our gradient complexity, which applies to a broader family of distributions, is almost the same except for small interval of e, but we do not require the batch size B and the inner loop length m to depend on while Zou et al. (2019b) do, i.e., B S B m = (Bo/ B). where Bg = (E "x_² A n). This strengthens the importance of our result since it shows that adapting this analysis to other stochastic schemes of GLD is promising and could lead to tighter bounds and relaxation of conditions. See Table for a summary. Concerning the concurrent work of Balasubramanian et al. (2022), under the sole assumption of smoothness, they provided a gradient complexity of O 2n//2 2 for the Variance Reduced LMC algorithm that updates the stochastic gradient differently and in some extent, our work can be interpreted as an acceleration of their result with a slightly stronger additional condition than Poincaré inequality.
e0(r+d) for SVRG-LD under Assumptions and 3. Note
SVRG-LD and SARAH-LD. This is almost the square of our result,
Proof Sketch Proceeding in a similar way as Vempala and Wibisono (2019), we evaluate how (p*)) decreases at each step shown in Theorem A. of Appendix A. This is realized by comparing the evolution of the continuous-time GL.D for time and one step of SVRG-LD. Since we use a stochastic gradient, we need the same time evaluate the variance of the stochastic gradient. Theorem can be obtained by recursively solving the inequality derived in Theorem A.1.
3.2 Convergence Analysis of SARAH-LD
As for SARAH-LD, its convergence to the stationary distribution du x c-1F can be formulated as the theorem below. Interestingly, we obtain the same result as SVRG-LD (Theorem 1) but we do not require B 2 m anymore.
7

---

Theorem 2. Under Assumptions and 2. 0 < <
and 2 for all k = 1,2,... the
16v2L'mm
following holds in the update of SARAH-LD where B(n-1)
(n-B)
32ny'L2 (2+E+ 2
Ho(dr) S Ho(0o) +
3a
This is the first convergence guarantee of SARAH-LD in this problem setting so far, and it leads to the following gradient complexity.
Corollary 2.1. Under the same assumptions as Theorem 2, for all e 2 0. if we choose step 3ax
size d7 such that S 64ydT + - then a precision Hy(őı) S reached after
k 2 log (0)( steps. Especially, if we take B = m = vn and the largest permissible step size
7 26 VAN 320d1 then the gradient complexity becomes
δ 0(11 dn
3 L2
a²
The reason why obtain the same gradient complexity for both SARAH-LD and SVRG-LD (except better coefficients for SARAH-LD) is that in our analysis, the Brownian noise added at each step of the Langevin Dynamies plays the role of fundamental bottleneck that even SARAH-LD could not eliminate, and we still need to set = m = vn. We can hypothesize that this order of gradient complexity might be tight for variance-reduced stochastic gradient Langevin Dynamics algorithms.
4 Some Applications to Non-Convex Optimization
Here, we apply our main results to non-convex optimization. Thanks to analysis applicable to broader family of probability distributions satisfying ISII, the additional conditions we pose this section are mainly reflected in the concrete formulation of the Log-Sobolev constant, which keeps our study simple and clear. The proofs can be found Appendix C. Since SVRG-LD and SARAH-LD exhibited almost the same performance in sampling. we can simultancously analyse them. We first prove the convergence to the global minimum SVRG-LD and SARAH-LD without clarifying the explicit formulation of the Log-Sobolev constant in function y.
Theorem 3. Using SVRG-LD or SARAH-LD, under Assumptions 1 to 3, 0 <
16.61.
7 Ad log (eL (M
8db 2
V VIV
vnn and the largest permissible the gradiens complexity to reach a precision of 1792 L=
and B if we take B
step size 1) 18V
o²e
[x[F((X)] F(X*) Se
nł dL. δ 0(m
222 a²
where a is a function of and X* is the global minimum of F.
Remark 1. Under Assumptions and 3, Assumption is negligible as shown Property C.2.
Under Assumptions to 3 only, this leads to a gradient complexity which exponentially depends on the inverse of the precision level as shown the next corollary since the inverse of the Log-Soboler constant exponentially depends on 7,
Corollary 3.1. Under the same assumptions Theorem 3, taking 7 i(c) 1 M. we obtain gradient complexity of
4d log (ol) V 8db
2
(((
n n dL
Cailee 130203ic))
Cii(e)
since = =Cie--01 (Property C.3).

---

The second term with n!/2 is almost all the time dominant since it has a factor that exponentially depends on 1/c and the first term not. This dependence on n of O(2 is the best so far for these algorithms. Moreover, comparing with the gradient complexity Ô (n 1211/2-=-6/33 Cll), also of order n2 provided by Xu et al. (2018) who used SVRG-L. and the same assumptions, our gradient complexity is an improvement since their analysis required a batch size B and an inner loop length m that strongly depend on c (i.e., B Vne 3/2 m /nz and ours does not. Note that the dependence of the gradient complexity of Xu et al. (2018) on 1/ce is not necessarily better than ours as X is actually the spectral gap of the discrete- time Markov chain generated by (I) and its inverse exponentially depends on 1/c as well. Although Xu et al. (2018) did not investigate the explicit nature of X, this is supported by Raginsky et al. (2017) who proved this exponential dependence for the spectral gap of the continuous time SDE and by Mattingly et al. (2002) who showed the spectral gap of continuous-time SDE and that of discrete-time version are almost the same in this context.
Analysis under the Morse condition Now, under the additional Assumptions 4 to 6, it is interesting to note that polynomial dependence on 1/e is achieved as the following corollary shows.
Corollary 3.2. Under the same assumptions as Theorem and Assumptions 4 to 6, taking Y = j(e) := 4d log (MT)
e V1V M V Crp where Cit a constant independent of e defined in Property C.4, we obtain a gradient complexity of
(el) V 8dh
((m
no dl (5(ee )3)(E)))) e :
n
since a CCs/ (Property C.4).
The crux of this corollary is Property C.4. To prove this, we show like Li and Erdogdu (2020) that satisfies the Poincaré inequality with constant independent of y. Since it is not hard to show this around the global minimum, we can step by step extend the set where this inequality holds by a Lyapunov argument (Theorems D.1 and D.2). The essential difference between this analysis and that of Li and Erdogdu (2020) is that we do not work on compact manifolds anymore. Some rather minor difficulties emerge as we cannot employ the compactness but they can be addressed by supposing dissipativity which assures a quadratic growth for large x.
Remark 2. These results do not definitively assert that SARAH-LD and SVRG-LD show the exact same performance in terms of optimization. Indeed, suppose we are close enough to the global optimum. Then, a big noise is not necessary anymore since it is more important to stably converge to the global minimum. Here, we should be able significantly decrease the noise ek, and the bottleneck from the noise should disappear. In this case, SARAH-LD LDD would perform better than SVRG-LD as we approach the original non-convex optimization setting where SARAH outperforms SVRG.
Remark 3. ameliorate the gradient complexity. The detailed analysis can be found in Appendix E.
We also investigated an annealed version of SVRG-LD and SARAH-LD but could not
5 Experiment
In this section, we illustrate our main result with simple experiment.' 1 We follow the same problem
setting as that of Welling and Teh (2011) 1) Section 5.1. That is, we aim to sample from a non-log-
concave posterior distribution p(f]zz) X |( - p(r,10) where {xx] ) is sampled from p(x](),
distribution parameterized by 0 = (0), 02). The prior p(0) and the distribution of x parametrized by
1/2N (022(0,, 2) + 1/2N (0) + 0z, 2). Here, we set n = 10000, 0, = 0 and 02 = 1. Using the obtained 10000 samples, we simulated 1000 points of SVRG-LD with the inner loop length m n/B B and different batch sizes B, namely, 100, 1000 and 10000 so that B= 2 m as required in Theorem 1. Evolution of KL-divergence between the true posterior, estimated by the Metropolls-adjjstte SVRG-LD is plotted in Figure 1. KL-divergence was approximated following Pérez- Cruz (2008).
respectively defined as 0₁
(0, 10). O2 N(0, 1) and
Langevin algorithm, and that simulated by
As we can observe, Figure correctly reproduces the theoretical bound of Theorem 1, with an exponential convergence the beginning and persistent bias due to the use of discrete scheme and mini-batches. The fastest convergence in terms of gradient complexity under the condition B 2 m
Source code can be found in https: //ggt//ggttt.ttt//ee http://ttu.cc///o/ee// wtt.ii-kii/eeerrP222222

---

107
SVRG-LD. B-100
SVRG-LD, B-1000
SURG-LD B-10050
S474H LD. E-200
10-1
15
4.0
Gradient
1a5
Figure 1: KL-divergence between the true and the simulated posterior. 1000 points were simulated for each algorithm with step size 17 = 0.00001. The inner loop length m for SVRG-LD was defined n B, and initial points were randomly drawn from the standard normal distribution. 1 gradient computation refers to one computation V.
is achieved by SVRG-LD with B vn, which confirms main theorem. Furthermore, with this best batch size, we also simulated 1000 points of SGLD and SARAH-LD as shown in Figure I as well. While SGLD and SVRG-LD have similar convergence speed the beginning, the latter eventually achieves a higher precision thanks to the variance reduction method adopted this scheme. SARAH-LD exhibits similar performance as SVRG-LD, which agrees with Theorem 2.
Discussion and Conclusion
The main limitations of our work reside in the gap between practice and theory. Indeed, while paper supposes assumptions quite standard in the literature of GLD, it cannot explain the whole empirical success that machine learning currently experiencing. Some choices of parameters may also seem different than the practical use. However, compared to previous work, we succeeded in proving convergence of GLD with the popular stochastic gradient with relaxed conditions, and deleting the dependence of batch size and inner loop length on epsilon, which are all more realistic situations than prior work. The theoretical study machine learning and deep learning precisely plays the role of filling as much as possible this large gap, and our work could be regarded as further step forward to achieve this goal. Furthermore, this paper, we focused on the pure sampling and optimization performance of the algorithms. and some of the drawbacks are simply due to this fact. For example, another limitation is that we did not investigate the generalization error Section but this was only outside the scope of this work.
In conclusion, we analysed the convergence rate of stochastic gradient Langevin Dynamies with variance reduction under smoothness and LSI and its application to optimization. In Section 3, we proved the convergence of SVRG-LD in terms of KL-divergence with more relaxed conditions (LSI and smoothness) and with a better gradient complexity than previous works. We also expanded SARAH SARAH-LD and showed that this algorithm enjoyed the same advantages as SVRG-LD with only improvement in the coefficients of the gradient complexity. These results led us to apply SVRG-LD and SARAH-LD to non-convex optimization Section 4. We provided the global convergence and non-asymptotic analysis of SVRG-LD and SARAH-LD. We obtained better conditions than prior works. Furthermore, we showed that under the additional assumption including Morse and Hessian Lipschitzness, the gradient complexity could be ameliorated, eliminating the exponential dependence on the inverse of the required error.
Acknowledgments and Disclosure of Funding
This study was partially supported by Japan Digital Design and JST CREST. We would like to thank Mufan Li and Murat A. Erdogdu for their valuable comments to fix some issues in the proof in Appendix D and their suggestion to improve We also thank anonymous reviewers for their feedback.
10

---

References
D. Bakry, Barthe, Cattiaux, and A. Guillin. A simple proof of the Poincaré incquality for large class of probability measures. Electronic Communications in Probability, 13:60-66, 2008.
K. Balasubramanian, S. Chewi, M. A. Erdogdu, A. Salim, and M. Zhang. Towards theory of non-log-concave sampling: first-order stationarity guarantees for langevin monte carlo. arXiv preprint arXiv:2202.0522 22..22222... 2022.
V. S. Borkar and S. K. Mitter. A strong approximation theorem for stochastic recursive algorithms. Journal of Optimization Theory and Applications, 100(3))499-513, 1999.
A. Bovier and F. Den Hollander. Metastability: Potential-Theorrli Approach, volume 351. Springer, 2016.
Cattiaux, A. Guillin, and L.-M. Wu. A note on Talagrand's transportation inequality and logarithmic Sobolev inequality. Probability Theory and Related Fields, 148(1):285-4)) -0485 2010.
N. Chatterji, N. Flammarion, Y. Ma, P. Bartlett, and M. Jordan. On the theory of variance reduction for stochastic gradient Monte Carlo. In International Conference on Machine Learning, pages 764-773. PMLR, 2018.
Chen, Lu, and L. Xu. Approximation stochastic variance reduced gradient Langevin dynamies by stochastic delay differential equations. arXiv preprint arXiv:2106.04333 2021.
T.-S. Chiang, C.-R. Hwang, and S. Sheu. Diffusion for global optimization in R". SIAM Journal on Control and Optimization, 25(3)7337-75, 1987.
A. Dalalyan. Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent. In Conference Learning Theory, pages 678 689. PMLR, 2017a.
A. S. Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79(3): 651-676, 2017b.
K. A. Dubey, S. Reddi, S. Williamson. Poczos, A. J. Smola, and P. Xing. Variance reduction in stochastic gradient Langevin dynamics. Advances in Neural Information Processing Systems, 29:1154-1162. 2016.
B. Gelfand and S. K. Mitter. Recursive stochastic algorithms for global optimization in Rdd SIAM Journal on Control and Optimization, 29(5)999- 1991.
R. Holley and D. W. Stroock. Logarithmic Sobolev inequalities and stochastic Ising models. 1986.
Z. Huang and S. Becker. Stochastic gradient Langevin dynamics with variance reduction. In 2021 International Joint Conference on Neural Networks, pages 1-8. IEEE, 2021.
C.R. Hwang. Laplace's 's method revisited: weak convergence of probability measures. The Annals of Probability, 8(6): 8(6): 177-118,7 1980.
R. Johnson and Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26:315-325 2013.
R. Jordan, D. Kinderlehrer, and F. Otto. The variational formulation of the Bakker-Plande equation. SIAM Journal on Mathematical Analysis, 29(1):1-17, 1998.
M. B. Li and M. A. Erdogdu. Riemannian langevin algorithm for solving semidefinite programs. arXiv preprint arXiv:2010.1117000 2020.
Z. Li. SSRGD: Simple stochastic recursive gradient descent for escaping saddle points. Advances in Neural Information Processing Systems, 32, 2019.
J. C. Mattingly, A. M. Stuart, and D. J. Higham. Ergodicity for SDEs and approximations: locally Lipschitz vector fields and degenerate noise. Stochastic Processes and their Applications, 101(2): 185-232. 2002.
11

---

G. Menz and A. Schlichting. Poincaré and logarithmic Sobolev inequalities by decomposition of the energy landscape. The Annals of Probability, 42(5):1809- 1884, 2014.
L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning. pages 2613-262) PMLR, 2017a.
L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. Stochastic recursive gradient algorithm for nonconvex optimization. arXiv preprint arXiv:1705.07220 2017b.
F. Otto and C. Villani. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev incquality. Journal of Functional Analysis, 173(2):361-400, 2000.
Pérez-Cruz. Estimation of information theoretic measures for continuous random variables. Advances in neural information processing systems, 21, 2008
N. H. Pham, L. M. Nguyen, D. T. Phan, and Q. Tran-Dinh. ProXSARAH: An efficient algorithmic framework for stochastic composite nonconvex optimization. Journal of Machine Learning Research, 21(110):1-48, 2020.
M. Raginsky, A. Rakhlin, and M. Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pages 1674-1703. PMLR, 2017.
S. Vempala and A. Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. Advances Neural Information Processing Systems, 118094-8106, 2019.
M. Wainwright. High- Dimensionnn Statistics: A Non-Asymptotic Viewpoint, volume 48. Cambridge University Press, 2019.
Z. Wang, K. Ji, Y. Zhou, Liang, and V. Tarokh. SpiderBoost and momentum: Faster variance reduction algorithms, Advances in Neural Information Processing Systems, 32, 2019.
M. Welling and Y. Teh. Bayesian learning via stochastic gradient Langevin dynamics. In International Conference Machine Learning, pages 681 1-1-688. Citeseer, 2011.
A. Wibisono. Sampling as optimization in the space of measures: The Langevin dynamics as composite optimization problem. In Conference Learning Theory, pages 2093-3027. PMLR, 2018.
Xu, J. Chen, D. Zou, and Q. Gu. Global convergence of Langevin dynamics based algorithms for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.
D. Zou, P. Xu, and Q. Gu. Subsampled stochastic variance-reduced gradient Langevin dynamics. In International Conference Uncertainty in Artificial Intelligence, 2018.
D. Zou, P. Xu, and Q. Gu. Sampling from pon-log-concave distributions via variance-reduced gradient Langevin dynamics. In International Conference on Artificial Intelligence and Statistics, pages 2936-2945. PMLR, 2019a.
D. Zou, P. Xu, and Q. Gu. Stochastic gradient Hamiltonian Monte Carlo methods with recursive variance reduction. Advances in Neural Information Processing Systems, 32:3835-3846 2019b.
D. Zou, P. Xu, and Q Gu. Faster convergence of stochastic gradient Langevin Dynamics for non-log-concan sampling. In Uncertainty in Artificial Intelligence, pages 1152-1162. PMLR, 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All the assumptions are summarized in Subsection 2.3 and refered when used.
(b) Did you include complete proofs of all theoretical results? [Yes] See the appendices.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as a URL)? [Yes] See the footnote.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "yTJ0gpD46Hd", "reviewer": "Reviewer_rRnx", "summary": "The connection between Langevin sampling and optimization has been extensively studied. A line of research in literature tries to adapt the known optimization techniques to get new sampling algorithms. This paper follows the same direction. The authors studies two algorithms SVRG-LD and SARAH-LD which are respectively based on the variance-reduced stochastic optimization algorithms SVRG and SARAH. Under the smoothness and LSI conditions the convergence of both algorithms is established in the KL divergence through a descent-like inequality. Under additional conditions, they apply these algorithms for the problem of non-convex optimization.", "questions": "* How does your work compare to the above mentioned paper?\n* In the statement of the theorems 1 and 2, the introduction of the constant $\\Lambda$  seems to be redundant as $\\Lambda = 1 + 2\\Xi$.\n\n", "limitations": "* The assumption 6 is restrictive as one might have multiple global minima.\n* The discussion on the limitations of the work seem to be absent in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* The paper is very well written. It explains the problem and the setting very clearly. One of the best written papers I have reviewed this year.\n* The proposed methods work in the relaxed LSI regime instead of strong convexity. \n\n\nWeaknesses\n* In the literature review the paper _\"On the Theory of Variance Reduction for SG-MC \" _ by Chetterji et al. is missing. This paper studies a similar problem. In particular, they propose an adaptation of the SAGA algorithm to the LMC problem. After a brief overview of the results, I saw that the their iteration complexity of Chatterji et al. is smaller than the one proposed in this paper. A discussion on this paper is required. \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": "y1-Ykus1v2s", "reviewer": "Reviewer_UBuG", "summary": "This paper presents improved convergence rates of SGLD with variance reduction. Also, it presents an application to non-convex optimization -- namely an upper bound on the gradient complexity necessary to reach a certain complexity, in SVRG-LD and SARAH-LD methods. The results are novel -- they take the same assumptions of Vempala et al. (2019), who also used the KL divergence as a criterion, but derive a better gradient complexity. Other works have used other assumptions or criteria. Crucially, however, this paper assumes that the batch size and inner loop length is set to \\sqrt{n}.  ", "questions": "1. I didn't understand what the \"inner loop length\" is. This concept needs some clarification in my opinion. \n2. Doesn't one have to assume, in Assumption 2, that \\rho is asymptotically continuous wrt. \\nu.\n3. The paragraph on top of page 9, before \"Analysis under the weak Morse condition\", is very confusing. Why is the second term with n^{1/2} almost all the time dominant? Why does the analysis of Mattingly et al. (2002) support this? Why use \"likely\" if the work of Raginsky et al. (2017) implies it? (Not a big deal, but maybe this paragraph can be improved.)", "limitations": "No limitations and no negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is theoretically a very strong paper. The main weakness is that its implications are a bit restrictive, as SVRG-LD and SARAH-LD aren't used so much in practice, as far as I know. (In fact, variance reduction is not used much in practice; instead, it has been shown recently that the stochasticity in SGD is vital for generalization and escaping minima/saddle-points.)\n\nStrengths:\nThe analysis is very detailed and technically involved. I did not read the Appendix, but could follow the exposition in the main paper. The literature review is very good and contains most relevant prior work. Table 1 is very helpful to the reader. (A few more words about the comparison with Vempala et al. (2019) could be added to the caption though.) The texts are clear and easy to read, and the authors are transparent about their assumptions. \n\nWeaknesses: \n1. The discussion of variance reduction methods is lacking in nuance: Lately it has been demonstrated the _stochasticity_, i.e. the variance, actually makes SGD so good by improving generalization. See e.g. https://arxiv.org/abs/2006.15081?context=stat or https://arxiv.org/pdf/2202.02831.pdf . Also, the variance is useful to escape saddle points and local minima: https://opt-ml.org/papers/2021/paper24.pdf and https://arxiv.org/abs/1902.04811. As far as I know, people don't really use variance reduction in practice, for precisely this reason. This is not a fundamental criticism of the paper: It is still important to study variance reduction, but there should be a discussion of the role of stochasticity and the usefulness of the studied methods in the Introduction. Also, the restriction of the results to variance-reduced method of course reduces the significance of the result.\n2. There should be a better discussion of the assumption that \"the batch size and the inner loop length are set to \\sqrt{n}\". While the other assumptions are fairly standard, this assumption is highly unusual. Also, it doesn't appear in Table 1 (why?). There should be a better discussion of this assumption, if this appears in other papers, too, and why it is necessary. \n3. Some plots or experiments demonstrating these experiments would be nice. (The proofs are very complicated and it would make the results more plausible if there were a few experiments, demonstrating them.)\n\nBottom line: If the authors provide a few experiments, I am fine with accepting this paper.\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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "HG90utBhjnt", "reviewer": "Reviewer_4MBs", "summary": "In this paper, the authors proved the convergence rate of the Stochastic Variance Reduced Gradient Langevin Dynamics and the Stochastic Recursive Gradient Langevin Dynamics. The proof is based on Log-Sobolev inequality and a relaxed assumption of smoothness and the result shows an improvement from the previous analysis.\n", "questions": "1. Wondering if the authors could comment on the scale of the learning rate. I feel in order to have Theorem 1 and Corollary 1.1. to hold, the required learning rate could be quite small.\n\n2. While setting the batch size to be $\\sqrt(n)$ leads to an improved gradient complexity, such batch size is very large and rarely used in practice. What would the gradient complexity look like if using a much smaller batch size?\n", "limitations": "In order to have the theorems hold, the choice of a few hyper-parameters, such as learning rate and batch size seem, seem to be far away from what has been used in practice.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper provides a non-asymptotic analysis of the convergence of SVRG-LD and SARAH-LD to the Gibbs distribution in terms of KL-divergence. The analysis is based on the relaxed assumptions of smoothness and LSI which are weaker conditions than those used in prior works for these algorithms. Overall, the proven convergence rate of SVRG is better than in previous work. \n\n\nHowever, I feel the result seems to be an incremental improvement of the work by Li and Erdogdu (2020) and Vempala and Wibisono (2019).\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": {}}]

Author rebuttal:

Decision: Accept