We study the problem of non-convex optimization using Stochastic Gradient Langevin Dynamics (SGLD).
SGLD is a natural and popular variation of stochastic gradient descent where at each step, appropriately scaled Gaussian noise is added.
To our knowledge, the only strategy for showing global convergence of SGLD on the loss function is to show that SGLD can sample from a stationary distribution which assigns larger mass when the function is small (the Gibbs measure), and then to convert these guarantees to optimization results.

We employ a new strategy to analyze the convergence of SGLD to global minima, based on Lyapunov potentials and optimization. We convert the same mild conditions from previous works on SGLD into geometric properties based on Lyapunov potentials.
This adapts well to the case with a stochastic gradient oracle, which is natural for machine learning applications where one wants to minimize population loss but only has access to stochastic gradients via minibatch training samples.
Here we provide 1) improved rates in the setting of previous works studying SGLD for optimization, 2) the first finite gradient complexity guarantee for SGLD where the function is Lipschitz and the Gibbs measure defined by the function satisfies a Poincaré Inequality, and 3) prove if continuous-time Langevin Dynamics succeeds for optimization, then discrete-time SGLD succeeds under mild regularity assumptions.

§ INTRODUCTION

We consider the minimization problem

\[ \arg \min_{\vecW \in \mathbb{R}^d} F(\vecW).\]

More specifically we are interested in returning a vector $\vecW$ such that $F(\vecW)-\min_{\vecW}F(\vecW) \le \epsilon$ for some desired sub-optimality $\epsilon>0$. In Machine Learning (ML) settings, $F$ can be thought of as population loss and $\vecW$ as the parameters of a model we are using for the learning problem. Additionally, in ML one does not have direct access to $F$ but only via samples $\vecZ_1,\ldots,\vecZ_n$ drawn iid from some unknown but fixed distribution $D$ and we assume that $\mathbb{E}_{\vecZ\sim D}[f(\vecW;\vecZ)] =  F(\vecW)$. Here the $\vecZ_i$ can be thought of as input-output pairs and $f(\vecW;\vecZ)$ can be thought of as the loss of the model parametrized by weights $\vecW$ on instance $\vecZ$. When the objective function/loss function is differentiable (or sub-differentiable), then a common method of choice in practice is to use gradient descent (GD), stochastic gradient descent (SGD) and its variants to perform the optimization. To understand their properties theoretically, we aim to understand how many gradient computations are necessary to find an $\epsilon$-suboptimal $\vecW$, and for which functions $F$ this is possible. Under geometric conditions such as convexity, the properties of GD and SGD are well-understood. For convex functions, methods from acceleration to variance reduction have been developed to speed up runtime in a variety of settings. Matching lower and upper bounds exist for both exact and stochastic gradients for convex functions and smaller classes such as strongly convex functions [Bubeck et al., 2015].
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
In recent years, machine learning has seen an explosion of success employing non-convex models. However, despite intensive study, the empirical success of optimizing non-convex functions to global optima is not at all well-understood theoretically. Beyond convexity, GD/SGD converges to global minima under general conditions such as Polyak-Łojasiewicz (PŁ) [Polyak, 1963] [Lojasiewicz, 1963] and Kurdyka-Łojasiewicz (KŁ) [Kurdyka, 1998] functions. Much more general geometric properties where GD/SGD can converge to global minima were found in [De Sa et al., 2022], by considering what properties hold if and only if gradient flow succeeds. Additionally, researchers have proved GD/SGD with appropriate initialization can find global minima of particular non-convex problems such as matrix square root [Jain et al., 2017] [De Sa et al., 2022], matrix completion [Jin et al., 2016], phase retrieval [Candes et al., 2015] [Chen et al., 2019] [Tan and Vershynin, 2023] [De Sa et al., 2022], and dictionary learning [Arora et al., 2015].

While gradient descent/stochastic gradient descent has been shown to be successful in the aforementioned cases, there are well-known cases where GD/SGD does not work.
A natural variant of gradient descent that is used for optimization is perturbed gradient descent, where Gaussian noise is added to the iterates of stochastic gradient descent – known as Langevin Dynamics – is frequently analyzed. Formally, the iterates of Gradient Langevin Dynamics (GLD) are given as follows:

\[ \vecW_{t+1} \leftarrow \vecW_t - \eta \nabla F(\vecW_t)+\sqrt{2\eta\beta^{-1}}\vecEps_t\numberthis\label{eq:SGLDiterates}.\]

Here $\eta>0$ is the step size, $\vecEps_t \sim \mathcal{N}(0,\bbI_d)$ is a $d$-dimensional standard Gaussian, and $\beta>0$ is the inverse temperature parameter (when larger, noise is weighted less). When we use a stochastic gradient oracle $\nabla f(\vecW_t;\vecZ_t)$ in place of $\nabla F(\vecW_t)$, these iterates become those of Stochastic Gradient Langevin Dynamics (SGLD). Langevin Dynamics has been shown to work in several highly non-convex settings where even gradient descent fails [Raginsky et al., 2017].

The continuous time version of eq:SGLDiterates is the following Stochastic Differential Equation (SDE):

\[ \DERIV \vecW(t) = -\grad F(\vecW(t))\DERIV t+\sqrt{2\beta^{-1}}\DERIV \vecB(t)\numberthis\label{eq:LangevinSDE}.\]

Here $\vecB(t)$ denotes a standard Brownian motion in $\mathbb{R}^d$. This is known as the Langevin Diffusion. Broadly, all of these recursions are known as Langevin Dynamics. Note as $\beta\rightarrow\infty$, these iterates become exactly those of GD/SGD (for eq:SGLDiterates) or Gradient Flow (for eq:LangevinSDE).

The only strategy in literature we know for proving global optimization guarantees for GLD is by first showing sampling guarantees, and then connecting it back to optimization.
Consider the Gibbs measure $\mu_{\beta} = e^{-\beta F}/Z$, where $Z$ denotes the partition function.
It is well known that the continuous-time Langevin Diffusion with inverse temperature $\beta$ eq:LangevinSDE converges to $\mu_{\beta}$ [Chiang et al., 1987] (although this is in fact false in discrete time).
When $\beta$ is sufficiently large, one can use this convergence to  get optimization guarantees.
This was exactly the strategy of the works Raginsky et al., 2017, Xu et al., 2018, and Zou et al., 2021.
These works prove that under their conditions, this measure $\mu_{\beta}$ can be sampled from, and therefore non-convex optimization can succeed. Sampling from $\mu_{\beta}$ is generally known as Langevin Monte Carlo (LMC).

The most general condition under which LMC has been proven to be successful is when $\mu_{\beta}$ satisfies a Poincaré Inequality [Chewi et al., 2022].
A Poincaré Inequality is defined as follows:

A measure $\mu$ on $\mathbb{R}^d$ satisfies a Poincaré Inequality with Poincaré constant $\CPI(\mu)$ if for all infinitely differentiable functions $f:\mathbb{R}^d\rightarrow \mathbb{R}$, we have

\[ \int_{\mathbb{R}^d} f^2 \DERIV\mu - \prn*{\int_{\mathbb{R}^d} f \DERIV\mu}^2 \le \CPI(\mu) \int_{\mathbb{R}^d} \nrm*{\grad f}^2 \DERIV\mu.\]

If the above is not satisfied, following the convention, we set  $\CPI(\mu)=\infty$.

There is evidence that in several cases, LMC does not succeed efficiently under looser conditions on $\mu_{\beta}$ such as a weak Poincaré Inequality [Mousavi-Hosseini et al., 2023]. Ultimately, a Poincaré Inequality being satisfied by $\mu_{\beta}$ is a geometric condition on $F$.

A Poincaré Inequality is quite natural.
For instance, when $F$ is convex ($\mu_{\beta}$ is log-concave), $\mu_{\beta}$ satisfies a Poincaré Inequality. This is a famous result of Bobkov [Bobkov, 1999].
But a Poincaré Inequality is in fact much more general. It is stable under bounded perturbations, hence covering a wide range of cases that log-concave measures (when $F$ is convex) does not (see Proposition 4.2.7, Bakry et al., 2014). Thus starting with a convex $F_{\text{old}}$ and creating $F$ by arbitrarily perturbing $F_{\text{old}}$, perhaps creating exponentially many local minima or maxima, the resulting measure $\mu_{\beta}=e^{-\beta F(\vecW)}/Z$ still satisfies a Poincaré Inequality (at the expense of worsening the Poincaré constant). Poincaré Inequalities are also stable under convolutions and mixtures, in the sense that for distributions which all satisfy a Poincaré Inequality, their mixture or convolutions between any two of them will also satisfy a Poincaré Inequality (again, at the expense of worsening the Poincaré constant; see Propositions 2.3.7 and 2.3.8, Chewi, 2024). What a Poincaré Inequality fundamentally says is the existence of a spectral gap (in terms of variance) for the Langevin Diffusion eq:LangevinSDE, see Theorem 4.2.5, Bakry et al., 2014. It should be noted that the Poincaré constant $\CPI(\mu_{\beta})$ can behave in many ways, including as a constant. For example when $\mu_{\beta}$ is isotropic and $F$ is convex, the famous conjecture of Kannan, Lovász, and Simonovits claims that $\CPI(\mu_{\beta}) = O(1)$ [Kannan et al., 1995]. This has been resolved up to polylog by the series of works Lee and Vempala, 2024, Chen, 2021, Klartag and Lehec, 2022, Jambulapati et al., 2022, and Klartag, 2023, the best result known being $\CPI(\mu_{\beta}) = O(\sqrt{\log d})$ from Klartag, 2023.
For further details on Poincaré Inequalities, we refer the reader to the excellent survey Bonnefont, 2022.

However, the approach of studying optimization guarantees for GLD/SGLD via sampling is not necessarily optimal. It does not handle stochastic gradients well (the more relevant setting for optimization), only works well when $F$ is approximately smooth, and converting sampling results back to optimization guarantees often incurs extra runtime. Moreover, it is not clear whether sampling, i.e. proving mixing, is necessary to study optimization.

§.§ Our Contributions

In our work, we offer a different perspective: we aim to prove optimization results for GLD/SGLD through Lyapunov potentials that are implied by Poincaré Inequalities. To our knowledge, this is the first time such a proof has been used to analyze global convergence of GLD/SGLD. Techniques to analyze sampling of GLD/SGLD generally go through a Girsanov change of measure style argument [Raginsky et al., 2017, Balasubramanian et al., 2022, Chewi et al., 2022]. This is both fragile, and does not work as well for the more natural case of stochastic gradients (SGLD).
In contrast, our Lyapunov-potential based method is more direct, robust, and naturally handles stochastic gradients. Rather than in sampling or even expected suboptimality, our geometric properties allow us to study the hitting time of GLD/SGLD. This leads to better bounds for optimizing non-convex functions, both in general and especially via SGLD.

Below we summarize our main contributions. The full statements are given in subsec:results:

* thm:poincareoptlipschitz and thm:poincareoptlipschitzestimate: Consider the case where $F$ is $s$-Hölder continuous for some $0 \le s \le 1$, there exists $\gamma \ge 2s$ such that for some $m,b>0$ we have $\tri*{\vecW, \grad F(\vecW)} \ge m\nrm*{\vecW}^{\gamma}-b$, and $\mu_{\beta}$ satisfies a Poincaré Inequality with constant $\CPI(\mu_{\beta})$ for $\beta = \widetilde{\Omega}\prn*{\frac{d}{\epsilon}}$. This is the setting of Balasubramanian et al., 2022 and Chewi et al., 2022[Although these works do not make our assumption on the tail growth of $F$, this assumption is mild and natural for non-convex optimization problems motivated by machine learning.]. For both GLD and SGLD, with probability at least $1-\delta$ we will reach a $\vecW$ with $\epsilon$-suboptimality to the global minimum using at most

\[ \widetilde{O}\prn*{\max\crl*{d^3 \max(\CPI(\mu_{\beta}), 1)^3, \frac{d^{2+\frac{s}2} \max(\CPI(\mu_{\beta}), 1)^{2+\frac{s}2}}{\epsilon^{2+\frac{s}2}}} \log\prn*{\nicefrac{1}{\delta}}} \]

gradient/stochastic gradient evaluations. Here, the $\tilde{O}$ hides universal constants and polynomial $\log$ factors in $\beta, d, \epsilon$.

* thm:poincareoptlipschitz and thm:poincareoptlipschitzestimate, special case: Consider the case where $F$ is Lipschitz and $\mu_{\beta}$ satisfies a Poincaré Inequality with constant $\CPI(\mu_{\beta})$ for $\beta = \widetilde{\Omega}\prn*{\frac{d}{\epsilon}}$. Here, unlike the above, we do not need lower bounds on the tails of $F$. For both GLD and SGLD, with probability at least $1-\delta$ we will reach a $\vecW$ with $\epsilon$-suboptimality to the global minimum using at most

\[ \widetilde{O}\prn*{\max\crl*{d^3 \max(\CPI(\mu_{\beta}), 1)^3, \frac{d^2 \max(\CPI(\mu_{\beta}), 1)^2}{\epsilon^2}} \log\prn*{\nicefrac{1}{\delta}}} \]

gradient/stochastic gradient evaluations.

* thm:smoothdissipativesettingpoincareopt: Consider the case when $F$ is smooth ($\grad F$ is Lipschitz) and $(m,b)$-dissipative (that is, there exist $m, b > 0$ such that $\tri*{\vecW, \nabla F(\vecW)} \ge m\nrm*{\vecW}^2-b$; see Raginsky et al., 2017, Xu et al., 2018, Zou et al., 2021, and Mou et al., 2022 for more details on dissipativeness). By $F$ smooth and dissipative, one can show that $\mu_{\beta}$ satisfies a Poincaré Inequality for $\beta = \widetilde{\Omega}\prn*{\frac{d}{\epsilon}}$; see Proposition 9 of Raginsky et al., 2017. For both GLD and SGLD, with probability at least $1-\delta$ we will reach a $\vecW$ with $\epsilon$-suboptimality using

\[ \widetilde{O}\prn*{\max\crl*{d^3 \max(\CPI(\mu_{\beta}), 1)^3, \frac{d^2 \max(\CPI(\mu_{\beta}), 1)^2}{\epsilon^2}} \log\prn*{\nicefrac{1}{\delta}}} \]

gradient/stochastic gradient evaluations.

* thm:maingeometriccondition: We show a tight connection between $\mu_{\beta}$ satisfying a Poincaré Inequality and the hitting time of the Langevin Diffusion to the set of $\epsilon$-suboptimal global minima of $F$. This is a corollary of literature in probability theory and partial differential equations (PDEs) [Cattiaux et al., 2013, Cattiaux and Guillin, 2017]; we believe we are the first to connect these results to optimization.

* thm:gradexactFeps, <ref>, and <ref>: A stronger condition is when the Langevin Diffusion works for optimization in the expected sense: when $\mathbb{E}\brk*{F(\vecW(t))}- \min_{\vecW}F(\vecW)$ is upper bounded by a rate that depends on $t$ and initialization. This is a stronger assumption than a Poincaré Inequality, which is tied to the hitting time of the Langevin Diffusion. Under this condition, we prove an optimization rate on the average suboptimality of the iterates for GLD/SGLD of $O \prn*{\nicefrac1{\epsilon^2}}$, which is dimension independent. This shows that when the continuous-time Langevin Diffusion works for optimization, discrete-time GLD/SGLD works as well.

Note that there are several caveats for using sampling as a way to show global optimization results. As mentioned earlier, $\beta$ must be sufficiently large relative to the tolerance $\epsilon>0$ we want to optimize $F$ to: we need $\beta = \widetilde{\Omega}(\frac{d}{\epsilon})$.
Specifically, consider when $F(\vecW)=\nrm*{\vecW}^2$, thus $\mu_{\beta}$ is a Gaussian with covariance $\frac1{\beta}\bbI_d$. This is by no means an adversarial example: $F$ is strongly convex, smooth, and well-conditioned. By standard results on Gaussian concentration about mean [Vershynin, 2018], we see that we need $\beta = \widetilde{\Omega}(\frac{d}{\epsilon})$ in order for even exact oracle access to $\mu_{\beta}$ to succeed as an efficient optimization strategy. The expected number of queries is $\frac1{\mu_{\beta}\prn*{\{\vecW:F(\vecW)<\epsilon\}}}$ with exact oracle access; if $\epsilon = {o}(\frac{d}{\beta})$, then $\mu_{\beta}\prn*{\{\vecW:F(\vecW)<\epsilon\}}$ is exponentially small in $d$. Note this is reflected in our work, for instance due to the $\mu_{\beta}\prn*{\{\vecW:F(\vecW)<\epsilon\}}$ term in thm:maingeometriccondition (see lem:measureoflargeF). This is also reflected in Raginsky et al., 2017, Xu et al., 2018, and Zou et al., 2021, which use the sampling result to upper bound $\mathbb{E}_{\vecW \sim \mu_T}\brk*{F(\vecW)} - \mathbb{E}_{\vecW \sim \mu_{\beta}}\brk*{F(\vecW)}$, where $\mu_T$ denotes the distribution upon running /SGLD after $T$ iterations. The expected suboptimality of $F$ under $\mu_{\beta}$, $\mathbb{E}_{\vecW \sim \mu_{\beta}}\brk*{F(\vecW)}$, behaves like $\tilde{\Theta}\prn*{\frac{d}{\beta}}$, and hence $\beta = \Omega\prn*{\frac{d}{\epsilon}}$ is required for optimization. The upper bound here can be proven quite generally, and again consider the Gaussian example for the lower bound.

Additionally, sampling and optimization runtime guarantees are not the same. As mentioned above, as done in Raginsky et al., 2017, Xu et al., 2018, and Zou et al., 2021, one uses the sampling result to upper bound $\mathbb{E}_{\vecW \sim \mu_T}\brk*{F(\vecW)} - \mathbb{E}_{\vecW \sim \mu_{\beta}}\brk*{F(\vecW)}$. However, techniques to do this can and often do pick up extra dependence in $d$, $\epsilon$, and isoperimetric constants such as $\CPI(\mu_{\beta})$, depending on the information metric the sampling guarantee is for. Moreover, for papers such as Chewi et al., 2022 and Balasubramanian et al., 2022 which study sampling in the constant temperature regime, when converting their results to optimization, we must scale their smoothness parameter by $\beta$, which again changes the runtime. Therefore, the runtime for optimization for other papers may not reflect the runtime written in said paper for sampling, as we compute the rate implied by the literature for our task of optimization (which requires low temperature, that is, large $\beta = \Omega\prn*{\frac{d}{\epsilon}}$): refer to subsec:poincareoptcomparisontoliteratureproofs for full derivation of the rates of literature.

We summarize the comparison to literature in tab:resultscompare. Note in our comparisons, we assume other results in literature are done with an $O(1)$ warm-start, which is the most favorable for pre-existing literature (i.e. the least favorable comparisons for our results).[For simplicity, in our comparisons we assume $\CPI(\mu_{\beta}) = \tilde{\Omega}(1)$, which is generally the case (for example this is true if $\mu_{\beta}$ is isotropic and $F$ is convex, and perturbations to $F$ will increase $\CPI(\mu_{\beta})$). All explicit expressions for our rates and those of the literature are given, so one can still perform these comparisons when $\CPI(\mu_{\beta}) = o(1)$.]

We additionally note that unlike the strategy for converting sampling to optimization guarantees outlined in Raginsky et al., 2017 and followed in Xu et al., 2018 and Zou et al., 2021, which is to upper bound $\mathbb{E}_{\vecW \sim \mu_T}\brk*{F(\vecW)} - \mathbb{E}_{\vecW \sim \mu_{\beta}}\brk*{F(\vecW)}$ using sampling guarantees, there is a more elegant and faster approach. To our knowledge it has not been mentioned in literature. The approach is to simply sample until $TV\prn*{\mu_T, \mu_{\beta}} \le 0.1 = O(1)$. For any $\epsilon>0$, denote the set $\{\vecW:F(\vecW)\le\epsilon\}$ by $\cA_{\epsilon}$. For $\beta=\Omega\prn*{\frac{d}{\epsilon}}$, one can show (see lem:measureoflargeF) that $\mu_{\beta}\prn*{\cA_{\epsilon}} \ge 0.5$. Therefore $\mu_T\prn*{\cA_{\epsilon}} \ge 0.4$ by definition of TV distance – that is, the probability our iterate $\vecW_T \in \cA_{\epsilon}$ is at least 0.4. When $\beta=o\prn*{\frac{d}{\epsilon}}$, $\mu_{\beta}\prn*{\cA_{\epsilon}}$ can be exponentially small in $d$ as seen from the Gaussian example, so this strategy still requires large $\beta$. tab:resultscompare shows the results using the strategy from Raginsky et al., 2017 known in the literature, but below we discuss the comparisons using both methods. While the rates of literature do improve, our rates are still more favorable.

Here we expand on these comparisons:

* Consider the case where $F$ is $s$-Hölder continuous, there exists $\gamma \ge 2s$ such that $\tri*{\vecW, \grad F(\vecW)} \ge m\nrm*{\vecW}^{\gamma}-b$, and $\mu_{\beta}$ satisfies a Poincaré Inequality for $\beta = \widetilde{\Omega}\prn*{\frac{d}{\epsilon}}$. This case has been studied in Chewi et al., 2022 and Balasubramanian et al., 2022.

In the GLD case, using the strategy of Raginsky et al., 2017, Theorem 7 of Chewi et al., 2022 obtains a rate of $\tilde{O}\prn*{\frac{d^{2+\frac3{s}}\CPI(\mu_{\beta})^{1+\frac1{s}} }{\epsilon^{\frac{4}{s}}}}$. Following the method suggested by rem:cleversamplingtoopt, the rate becomes $\tilde{O}\prn*{\frac{d^{1+\frac2{s}}\CPI(\mu_{\beta})^{1+\frac1{s}} }{\epsilon^{\frac{2}{s}}}}$. When $s \le \frac12$, our result from thm:poincareoptlipschitz is always better or equal to both of these in all parameters. When $s \in (\frac12, 1]$, our result from thm:poincareoptlipschitz is superior to the rate obtained following the strategy of Raginsky et al., 2017 when $\epsilon < \frac{d^{\frac14(3-s)}}{\CPI(\mu_{\beta})^{\frac12(s-\frac12)}}$. thm:poincareoptlipschitz is superior to the rate obtained following rem:cleversamplingtoopt when $\epsilon < \frac{d^{1-s}}{\CPI(\mu_{\beta})^{s-\frac12}}$.

When $s \le \frac12$, Corollary 19 of Balasubramanian et al., 2022 improves on Chewi et al., 2022. Using the strategy of [Raginsky et al., 2017], the rate is $\tilde{O}\prn*{\frac{d^{\frac{6}{1+s}+8-3s} \CPI(\mu_{\beta})^3}{\epsilon^{\frac{16-2s}{1+s}}}}$, which is using $s \le \frac12$ at least $\tilde{O}\prn*{\frac{d^{10.5} \CPI(\mu_{\beta})^3}{\epsilon^{10}}}$. Following rem:cleversamplingtoopt, the rate becomes $\tilde{O}\prn*{\frac{d^{3+\frac{6}{1+s}-2s} \CPI(\mu_{\beta})^3 }{\epsilon^{\frac{6}{1+s}}}}$, which using $s \le \frac12$ is at least $\tilde{O}\prn*{\frac{d^{8} \CPI(\mu_{\beta})^3 }{\epsilon^{6}}}$. Our result from thm:poincareoptlipschitz is superior or equal to both of these in all parameters, oftentimes by a significant amount.

In the SGLD case, our rate from thm:poincareoptlipschitzestimate is the first finite gradient complexity guarantee.

* Consider the case when $F$ is Lipschitz and $\mu_{\beta}$ satisfies a Poincaré Inequality for $\beta = \widetilde{\Omega}\prn*{\frac{d}{\epsilon}}$. This has not been well-studied in the sampling or optimization literature, and the only work we know of with finite gradient complexity is Balasubramanian et al., 2022, namely $s=0$ in Corollary 19, in the GLD case. The rate here using the strategy of Raginsky et al., 2017 is $\widetilde{O}\prn*{\frac{d^{14} \CPI(\mu_{\beta})^3}{\epsilon^{16}}}$, or following rem:cleversamplingtoopt, is $\widetilde{O}\prn*{\frac{d^{9} \CPI(\mu_{\beta})^3}{\epsilon^{6}}}$. Our rate from thm:poincareoptlipschitz is superior or equal to both of these in every parameter, oftentimes by a significant amount. Again, thm:poincareoptlipschitzestimate is the first finite gradient complexity guarantee for the SGLD case.

* Consider the case for SGLD and when $F$ is smooth and dissipative, which has been well-studied in the works Raginsky et al., 2017, Xu et al., 2018, and Zou et al., 2021. Theorem 1 of Raginsky et al., 2017 requires gradient noise $\delta$ to be potentially exponentially small in $d$, which does not make sense (we only require gradient noise of constant order, which is more realistic).

For using the results from Xu et al., 2018 and Zou et al., 2021, we must account for total gradient complexity for a stochastic gradient oracle with $O(1)$ noise. After doing so we obtain $\widetilde{O}\prn*{\frac{d^7}{\epsilon^5 \lambda_{*}^5}}$ for Xu et al., 2018 and a rate of $\widetilde{O}\prn*{\frac{d^5}{\lambda_{*}^4 \epsilon^4}}$ for variance-reduced SGLD from Xu et al., 2018. Here, $\lambda_{*}$ is a quantity similar to $\frac1{\CPI(\mu_{\beta})}$ (but not directly comparable)[It is the spectral gap of discrete-time SGLD.]. Our rate from thm:smoothdissipativesettingpoincareopt thus is generally superior to both of these in every parameter. (The results of Xu et al., 2018, being phrased directly in optimization, can't be directly improved using rem:cleversamplingtoopt.) The rate from Zou et al., 2021 is, using Cheeger's Inequality, at least $\widetilde{O}\prn*{\frac{d^8 \CPI(\mu_{\beta})^2}{\epsilon^4}}$ using the strategy of Raginsky et al., 2017. Thus our rate is superior when $\epsilon < \frac{d^{1.25}}{\CPI(\mu_{\beta})^{0.25}}$. Following rem:cleversamplingtoopt, Zou et al., 2021 yields a rate of $\widetilde{O}\prn*{\frac{d^{6} \CPI(\mu_{\beta})^2 }{\epsilon^2}}$; our rate is superior when $\epsilon < \frac{d^{1.5}}{\CPI(\mu_{\beta})^{0.5}}$.

* We additionally touch on other discretizations of the Langevin Diffusion. To our knowledge, the only other discretization of eq:LangevinSDE successful beyond log-concavity is the Proximal Sampler first introduced in Lee et al., 2021.  With exact gradients, Altschuler and Chewi, 2023 showed it succeeds under a Poincaré Inequality when $F$ is smooth; the Proximal Sampler can only be implementable with smoothness for non-convex $F$. In the stochastic gradient setting, the only work we are aware of showing its success is Theorems 4.1 and 4.2 of Huang et al., 2024, showing the Proximal Sampler succeeds under smoothness and a Log-Sobolev Inequality (which is satisfied in the smooth and dissipative setting as shown in Proposition 9 of Raginsky et al., 2017). The rate from there is, using the strategy of Raginsky et al., 2017, $\tilde{O}\prn*{\frac{d^{5.5} \CPI(\mu_{\beta})^3}{\epsilon^5}}$. Or following rem:cleversamplingtoopt, the rate is $\tilde{O}\prn*{\frac{d^{3.5} \CPI(\mu_{\beta})^3}{\epsilon^3}}$. Our rate from thm:smoothdissipativesettingpoincareopt is superior or equal in every parameter, often by a significant amount.

Problem Setting     Our Result     Best in Literature

GLD Poincaré & Lipschitz     $\widetilde{O}\prn*{\max\crl*{d^3 \CPI(\mu_{\beta})^3, \frac{d^2 \CPI(\mu_{\beta})^2}{\epsilon^2}}}$     1in

$\widetilde{O}\prn*{\frac{d^{14} \CPI(\mu_{\beta})^3}{\epsilon^{16}}}$

[Balasubramanian et al., 2022]

SGLD Poincaré & Lipschitz    $\widetilde{O}\prn*{\max\crl*{d^3 \CPI(\mu_{\beta})^3, \frac{d^2 \CPI(\mu_{\beta})^2}{\epsilon^2}}}$     1.5in

No finite guarantee

SGLD smooth & dissipative     $\widetilde{O}\prn*{\max\crl*{d^3 \CPI(\mu_{\beta})^3, \frac{d^2 \CPI(\mu_{\beta})^2}{\epsilon^2}}}$

$\widetilde{O}\prn*{\min\crl*{\frac{ d^{8}\CPI(\mu_{\beta})^2}{\epsilon^4},\frac{d^7}{\epsilon^5 \lambda_{*}^5}}}$

[Xu et al., 2018, Zou et al., 2021]

Gradient complexity comparisons. In the table, $d$ refers to dimension and $\epsilon$ refers to tolerance. $\beta = \widetilde{\Theta}\prn*{\frac{d}{\epsilon}}$, and $\CPI(\mu_{\beta})$ denotes the Poincaré constant of $\mu_{\beta}$. $\lambda_{*}$ is a spectral gap comparable to $\CPI(\mu_{\beta})$.

Notation. Unless otherwise specified the domain is $\mathbb{R}^d$, with origin $\vecOrigin$. We denote the Laplacian (sum of second derivatives) of a twice-differentiable function $f$ by $\Delta f$. Here $\ball(p,R)$ denotes the Euclidean $l_2$ ball centered at $p\in\mathbb{R}^d$ with radius $R \ge 0$. $\mathcal{S}^{d-1}$ denotes the surface of the $d$-dimensional unit sphere. $\widetilde{\Omega}$, $\widetilde{\Theta}$, $\widetilde{O}$ hide universal constants, $\log$ factors in $\beta, d, \epsilon$, as well as $\vecW_0$-dependence. Sometimes we will write exponentials as $\text{exp}$ for readability. When we write vectors $\vecW_t$ this denotes time $t$ in discrete time, and when we write $\vecW(t)$ this denotes time $t$ in continuous time.

Unless indicated otherwise, $\mathbb{E}$ refers to expectation over the Brownian motion/random variables $\vecEps_t$ (as well as the data samples $\vecZ_t$ in the SGLD case), and $\mathbb{E}_{\vecW}$ denotes the same expectation when the stochastic processes is initialized at $\vecW$. For any set $\cU \subset\mathbb{R}^d$, let the hitting time of the Langevin Diffusion eq:LangevinSDE initialized at $\vecW$ to $\cU$ be $\tau_{\cU}(\vecW)$.
We assume that first order tensors, i.e. vectors, are equipped with $l_2$ Euclidean norm and that all second order tensors (i.e. matrices) and above are equipped with operator norm. When we write $\nrm*{\cdot}$ without specifying the norm, we implicitly mean the $l_2$ Euclidean norm of a vector. For some $f$ differentiable to $k$ orders, we will let $\nabla^{k} f$ denote the tensor of all the $k$-th order derivatives of $f$, and $\nrm*{\cdot}_{\OPNORM}$ denotes the corresponding tensor's operator norm.

§ LYAPUNOV POTENTIALS AND OPTIMIZATION

In the rest of this paper, suppose $F$ has a global minimum $\vecW^{\star}$, which need not be unique (thus $\vecW^{\star}$ can refer to any of these). Furthermore, without loss of generality, assume that $F(\vecW^{\star})=0$.

§.§ Our Strategy

Optimization under Langevin Dynamics can ultimately be posed as a question of hitting time: how long does it take to reach a point $\vecW$ such that  $F(\vecW)\le \epsilon$? In the probability theory and stochastic partial differential equations (PDEs) literature, an extensive program has been devoted to studying the connection between isoperimetric inequalities such as a Poincaré Inequality, hitting times of the Langevin Diffusion to sets $A \subset \mathbb{R}^d$, and Lyapunov potentials.
A subset of this literature includes Carmona and Klein, 1983, Meyn and Tweedie, 1993, Down et al., 1995, Bakry et al., 2008, Cattiaux et al., 2009, Cattiaux et al., 2010, Meyn and Tweedie, 2012, Cattiaux et al., 2013, Cattiaux and Guillin, 2017.
As mentioned in sec:introduction, Poincaré Inequalities are the loosest conditions under which sampling and in turn global optimization guarantees for Langevin Dynamics have been well-studied. This literature connects these inequalities to the geometry of $F$.

Say a non-negative function $\Phi:\mathbb{R}^d\rightarrow\mathbb{R}$ is a Lyapunov potential (for Langevin Dynamics at inverse temperature $\beta$ given in eq:LangevinSDE) if $\Phi \ge 1$ and on the set $\{\vecW:F(\vecW) > \epsilon\}$ we have

\[ \tri*{\grad \Phi(\vecW), \grad F(\vecW)} \ge \lambda \Phi(\vecW)+\frac1{\beta}\Delta\Phi(\vecW),  \numberthis\label{eq:lyapunovbaby}\]

where  $\beta$ refers to the inverse temperature of eq:LangevinSDE.

Our main method to study optimization is to track the progress of GLD/SGLD using the Lyapunov potential $\Phi(\vecW)$. Suppose such a Lyapunov potential existed: from here, we can study the hitting time of GLD/SGLD to the set $\cA_{\epsilon}=\{\vecW: F(\vecW)\le\epsilon\}$.

The fundamental idea is as follows. Consider $\tau_{\cA_{\epsilon}}(\vecW_0)$, the hitting time of GLD/SGLD initialized at $\vecW_0$ to $\cA_{\epsilon}$. Denote this by $\tau$ for short in the following. Consider the random variable $X :=\frac1{\tau} \sum_{t=0}^{\tau-1} \lambda\Phi(\vecW_t)$.
Suppose that $\Phi$ is $L$-smooth and $L$-Hessian Lipschitz. The idea is that, by the following, we can make $X$ relatively small if $\tau$ is relatively large, by Taylor expanding $\Phi$ to third order and using eq:poincaregeomcondition (it turns out to be possible to control the higher order discretization terms).

However, by definition none of $\vecW_0, \ldots, \vecW_{\tau-1}$ lie in $\cA_{\epsilon}$. Clearly $X$ is lower-bounded by $\lambda$, since $\Phi \ge 1$. But we just showed $X$ is small if $\tau$ is relatively large. This gives contradiction! Hence, we can upper bound $\tau$. This idea, while currently informal, can be made rigorous (using discrete-time Dynkin's formula, Theorem 11.3.1, page 277 of Meyn and Tweedie, 2012). See  sec:PIoptproofs for details.

To show how $X$ can be made small, using definition eq:SGLDiterates, we Taylor expand $\Phi$ to third order (using that it is $L$-smooth and $L$-Hessian Lipschitz) to obtain

\begin{align*}
\Phi(\vecW_{t+1}) &= \Phi\prn*{\vecW_t - \eta \grad F(\vecW_t) + \sqrt{2\eta\beta^{-1}} \vecEps_t} \\
&\le \Phi(\vecW_t) + \tri*{-\eta \grad F(\vecW_t), \grad \Phi(\vecW_t)} + \tri*{\sqrt{2\eta\beta^{-1}} \vecEps_t, \grad \Phi(\vecW_t)}\\
&\hspace{1in}+ \frac12 \tri*{\grad^2 \Phi(\vecW_t)\prn*{- \eta \grad F(\vecW_t) + \sqrt{2\eta\beta^{-1}} \vecEps_t}, - \eta \grad F(\vecW_t) + \sqrt{2\eta\beta^{-1}} \vecEps_t} \\
&\hspace{1in}+ \frac{L}6 \nrm*{- \eta \grad F(\vecW_t) + \sqrt{2\eta\beta^{-1}} \vecEps_t}^3.
\end{align*}

We first use eq:lyapunovbaby, which gives

\[ \tri*{-\eta \grad F(\vecW_t), \grad \Phi(\vecW_t)} \le -\eta \lambda \Phi(\vecW_t) -\frac{\eta}{\beta}\Delta\Phi(\vecW_t). \]

Now, take expectations with respect to $\vecEps_t$. The term $\tri*{\sqrt{2\eta\beta^{-1}} \vecEps_t, \grad \Phi(\vecW_t)}$ disappears, in addition to the cross term $-2\eta \sqrt{2\eta\beta^{-1}} \tri*{\grad^2 \Phi(\vecW_t) \vecEps_t, \grad F(\vecW_t)}$ from the second-order term. Note now that

\[ \mathbb{E}\brk*{\frac12\tri*{\grad^2 \Phi(\vecW_t) \cdot \sqrt{2\eta\beta^{-1}} \vecEps_t,\sqrt{2\eta\beta^{-1}} \vecEps_t}} = \frac{\eta}{\beta}\Delta\Phi(\vecW_t).\]

Therefore, the Laplacian terms $\frac{\eta}{\beta}\Delta\Phi(\vecW_t)$ cancel in the above after taking expectations, and what we obtain is (upon dividing by $\eta$)

\[ \lambda\mathbb{E}\brk*{\Phi(\vecW_t)} \le \mathbb{E}\brk*{\Phi(\vecW_t)}-\mathbb{E}\brk*{\Phi(\vecW_{t+1})} + \crl{\text{higher order discretization error terms}}.\]

Summing and telescoping this relation, and using that $\Phi$ is non-negative, we obtain

\[ \mathbb{E}\brk*{X} = \frac1{\tau} \sum_{t=0}^{\tau-1} \lambda\mathbb{E}\brk*{\Phi(\vecW_t)} \le \frac{\Phi(\vecW_0)}{\tau} + \frac1{\tau} \cdot \crl{\text{higher order discretization error terms}}.\]

If we can control higher order discretization error terms, which it turns out we can do as discussed in sec:PIoptproofs, then if $\tau$ is large then $\mathbb{E}\brk*{X}$ will be small. But as discussed earlier $X \ge \lambda$ pointwise, hence $\mathbb{E}\brk*{X} \ge \lambda$. This lets us control $\tau$, the hitting time of GLD/SGLD to the set $\cA_{\epsilon}$.

One might note this idea of considering the hitting time of SGLD to $\cA_{\epsilon}$ bears resemblance to the style of proof from Zhang et al., 2017. However, Zhang et al., 2017 considered the hitting time to second-order stationary points, and so our results (in addition to the techniques) are fairly different.

To fully generalize this, using lem:thirdordersmoothfromregularity, this idea can be extended to cover essentially all Lyapunov functions of interest (far beyond when $\Phi$ is smooth and Hessian Lipschitz). Due to the stochasticity already present in GLD, our analysis for GLD vs SGLD is extremely similar.

The geometric condition eq:lyapunovbaby turns out to be closely linked to a Poincaré Inequality: as a corollary of Cattiaux and Guillin, 2017 we obtain the following:

Assume that $\mu_{\beta}$ satisfies a Poincaré inequality with constant $\CPI(\mu_{\beta})$ and has finite second second moment for some $\beta = \widetilde{\Omega}\prn*{\frac{d}{\epsilon}}$. Then on $\cA_{\epsilon}^c=\{\vecW:F(\vecW) > \epsilon\}$,

\[ \tri*{\grad F(\vecW), \grad \Phi(\vecW)} \ge\lambda\Phi(\vecW) + \frac1{\beta} \Delta\Phi(\vecW)  \quad \text{ for } \quad \lambda \in \brk*{\frac1{8\beta} \min\prn*{\frac1{{\CPI}(\mu_{\beta})}, \frac12}, \frac1{4\beta} \min\prn*{\frac1{{\CPI}(\mu_{\beta})}, \frac12}},\numberthis\label{eq:poincaregeomconditioninformal}\]

for some non-negative $\Phi$ that is differentiable to all orders such that on $\cA_{\epsilon}^c$, $\Phi$ takes the explicit form

\[ \Phi(\vecW') = \mathbb{E}_{\vecW'}\brk*{\exp\prn*{\lambda \tau_{\cA_{\epsilon}}}}.\]

Note that on $\cA_{\epsilon}^c$, $\Phi \ge 1$. Also note $\Phi$ generally behaves in a `dimension free' manner, depending on how $\tau_{\cA_{\epsilon}}(\vecW')$ behaves, as $\lambda \le \frac1{4\beta} \min\prn*{\frac1{{\CPI}(\mu_{\beta})}, \frac12}$ is very small.

We note that in Bakry et al., 2008 and Cattiaux et al., 2013, the condition eq:poincaregeomconditioninformal is shown to imply that $\mu_{\beta}$ satisfies a Poincaré Inequality if $\cA_{\epsilon}$ is connected. The proof of this direction requires connectedness. However, note eq:poincaregeomconditioninformal implies the moment generating function $\mathbb{E}_{\vecW'}\brk*{\exp\prn*{\lambda \tau_{\cA_{\epsilon}}}} < \infty$. Make the very mild assumption that $\cA_{\epsilon}$ lies in $\ball(\vecOrigin, R)$ for $R<\infty$ large enough. Since pointwise $\tau_{\cA_{\epsilon}} \ge \tau_{\ball(\vecOrigin, R)}$, this implies $\mathbb{E}_{\vecW'}\brk*{\exp\prn*{\lambda \tau_{\ball(\vecOrigin, R)}}} < \infty$. From here, Cattiaux et al., 2013 shows a geometric property analogous to eq:poincaregeomconditioninformal holds where the Lyapunov function is now $\mathbb{E}_{\vecW'}\brk*{\exp\prn*{\lambda \tau_{\ball(\vecOrigin, R)}}}$, and in turn that $\mu_{\beta}$ satisfies a Poincaré Inequality. The moment generating function satisfying eq:lyapunovbaby (that is, the moment generating function being a valid Lyapunov potential in the sense here) and isoperimetric inequalities are thus linked very tightly, as equivalent for the Langevin diffusion.

§.§ Results

Now, we state our results in full detail. Complete statements and proofs, including all explicit dependencies, are in sec:PIoptproofs. For all of our results, recall from subsec:ourcontributions that the desired tolerance $\epsilon= \widetilde{\Omega}\prn*{\frac{d}{\beta}}$; no results so far in literature yield meaningful optimization guarantees for smaller tolerance levels.

Before we state our results more explicitly, we state our assumptions, which are in fact necessary. Our first assumption, generalized to higher order derivatives from De Sa et al., 2022, is that the Lyapunov potential $\Phi$ satisfies `self-bounding regularity' in the following sense:

A $k$ times differentiable function $f:\mathbb{R}^d\rightarrow\mathbb{R}$ satisfies $k$-th order self-bounding regularity if

\[ \nrm*{\nabla^{k} f(\vecW)}_{\OPNORM}\le \rho_{f,k}(\abs{f(\vecW)})\]

for some increasing function $\rho_{f,k}:\mathbb{R}\rightarrow\mathbb{R}_{\ge 0}$.

We say $f$ satisfies polynomial-like self-bounding regularity at order $k$ if we can express $\rho_{f,k}(z)=\sum_{j=0}^{n} c_j z^{d_j}$ where all $d_j \ge 0$. Note without loss of generality we can assume all $c_j, d_j \ge 0$ and $\rho_{f,k}(z)=A(z+1)^p$ or $\rho_{f,k}(z)=A+Az^p$ by the AM-GM Inequality.

Such an assumption is necessary for discrete-time optimization to succeed: Theorem 3 from De Sa et al., 2022 shows even for Gradient Flow/Gradient Descent, there are examples where discrete-time optimization fails when continuous-time optimization succeeds. This is exactly what allow for control of higher order discretization terms arising in discrete-time optimization. As such we will assume the following:

Suppose $\Phi$ satisfies first, second, and third order polynomial-like self-bounding regularity where the monomials in the self-bounding regularity functions have degree at most 1.

Note ass:selfboundingPhipoly is satisfied by many Lyapunov functions, e.g. when the Lyapunov function $\Phi$ has tail growth polynomial in $\nrm*{\vecW}$ or of the form $e^{r\nrm*{\vecW}^s}$ for $s\le 1$, going well beyond smoothness. Since we have explicit knowledge of $\Phi$ via thm:maingeometriccondition, this is just saying the MGF of $\tau_{\{\vecW:F(\vecW) < \epsilon\}}$ is reasonably well-behaved as a function of the initialization $\vecW$ of the continuous-time Langevin Diffusion.

Now we state our assumptions on $F$. We consider the most general setting of previous works [Chewi et al., 2022, Balasubramanian et al., 2022] for analyzing LMC where we assume $F$ is Hölder continuous with parameter $0 \le s \le 1$:
[Hölder continuity]
Suppose $\nabla F$ satisfies $L$-Hölder continuity for some $0 \le s \le 1$:

\[ \nrm*{\nabla F(\mathbf{u})-\nabla F(\mathbf{v})} \le L\nrm*{\mathbf{u}-\mathbf{v}}^s.\]

When $s>0$, that is $F$ is not Lipschitz, we also require an assumption on the growth of $F$. This significantly generalizes the dissipation assumption (when $s=1$ and $\gamma=2$) made in several previous works studying non-convex optimization [Raginsky et al., 2017, Xu et al., 2018, Zou et al., 2021, Mou et al., 2022].

There exists $\gamma \ge 2s$ such that for some $m,b>0$ and all $\vecW\in\mathbb{R}^d$,

\[ \tri*{\vecW, \grad F(\vecW)} \ge m\nrm*{\vecW}^{\gamma}-b.\]

Analyzing growth rates, we can see $\gamma \le s+1$, which leads to no issues for $0 \le s \le 1$. Note this assumption is quite reasonable: in some sense it states that the gradient will push us towards the origin when we are sufficiently far away. Moreover, all critical points of $F$ are in $\ball(\vecOrigin,(b/m)^{1/\gamma})$. However, we allow for arbitrary non-convexity inside this ball. In fact, by adding a suitable regularizer penalizing solutions lying outside $\ball(\vecOrigin,(b/m)^{1/\gamma})$, we can ensure $F$ satisfies the above, which is discussed on page 15 of Raginsky et al., 2017.

Suppose that $F$ satisfies ass:holderF and ass:weakdissipation, $\mu_{\beta}$ satisfies a Poincaré Inequality with constant $\CPI(\mu_{\beta})$ for $\beta = \widetilde{\Omega}\prn*{\frac{d}{\epsilon}}$, and $\mu_{\beta}$ has finite second moment $S<\infty$. (In our results dependence on $S$ will be logarithmic.) Suppose $\Phi$ (from thm:maingeometriccondition) satisfies ass:selfboundingPhipoly with $p\le 1$. Then running , with probability at least $1-\delta$, across all the runs we will reach a $\vecW$ with $F(\vecW)\le\epsilon$ in at most

\[ \widetilde{O}\prn*{\max\crl*{d^3 \max(\CPI(\mu_{\beta}), 1)^3, \frac{d^{2+\frac{s}2} \max(\CPI(\mu_{\beta}), 1)^{2+\frac{s}2}}{\epsilon^{2+\frac{s}2}}} \log\prn*{\frac1{\delta}}}\numberthis\label{eq:runtimeguaranteelipschitz}\]

gradient evaluations.

We note considering ass:holderF for any $s \ge 0$ and a Poincaré Inequality is quite natural. In terms of growth of $F$, a Poincaré Inequality implies at least linear tail growth of $F$ but nothing further, as discussed on page 7 of [Chewi et al., 2022]. Thus, ass:holderF for any $s \ge 0$ and a Poincaré Inequality are not only compatible but natural to study in tandem.

We now move on to the stochastic gradient oracle case. Some control over the stochastic gradient estimates is necessary: if they are very inaccurate, following them will be meaningless.
[Bound of variance of gradient estimates]
The unbiased gradient estimate $\nabla f(\vecW;\vecZ)$ of $\nabla F(\vecW)$ satisfies the sub-Gaussian property that for all $\vecW\in\mathbb{R}^d$ and $t\ge 0$,

\[ \mathbb{P}_{\vecZ}\prn*{\nrm*{\nabla f(\vecW;\vecZ)-\nabla F(\vecW)}_2 \ge t} \le e^{-t^2/\sigma_F^2}. \numberthis\label{eq:gradnoisestandard}\]

This covers the classic setting of stochastic optimization where $\nabla f(\vecW;\vecZ) = \nabla F(\vecW)+\vecEps_t$ where $\vecEps_t$ is sub-Gaussian with mean 0 and variance $\sigma_F^2$ [Nemirovski et al., 2009]. We expect our techniques to hold when gradient noise scales in function value, a more general setting discussed in De Sa et al., 2022, but for simplicity we work with ass:gradnoiseassumption.

We also need the following assumption made in Raginsky et al., 2017 studying stochastic optimization in this setting. This is quite reasonable: it essentially says the stochastic gradients contain reasonable signal and also will push us towards the origin when sufficiently far away.

For every $\vecZ$, $\grad f(\vecW;\vecZ)$ satisfy ass:holderF and ass:weakdissipation. (Note they may be satisfied with larger $L$ and $b$ and smaller $m$.)

Then, we have the following:

Suppose $\mu_{\beta}$, $F$, $\Phi$ satisfy the same assumptions as in thm:poincareoptlipschitz. Then running with a stochastic gradient oracle satisfying ass:gradnoiseassumption and ass:stochasticgradcontrol, we obtain the same guarantee eq:runtimeguaranteelipschitz of the query complexity of our stochastic gradient oracle as in thm:poincareoptlipschitz.

To our knowledge, our result thm:poincareoptlipschitzestimate is the first finite iteration guarantee for the setting of $F$ Hölder-continuous and $\mu_{\beta}$ satisfying a Poincaré Inequality with a stochastic gradient oracle. The stronger assumption of smoothness is not satisfied by many canonical non-convex optimization problems [De Sa et al., 2022], so analyzing optimization with a stochastic gradient oracle in this more general setting is highly relevant to study.

Recall from our conditions ass:holderF and ass:weakdissipation that by analyzing the implied growth rates of $F$, we have $2s \le \gamma \le s+1$. Thus when $s=1$, $\gamma=1$ is forced, so this recovers as a special case of our assumption the smooth and dissipative setting from Raginsky et al., 2017, Xu et al., 2018, and Zou et al., 2021. In turn, $s=1$, $\gamma=1$ actually implies $\mu_{\beta}$ satisfies a Poincaré Inequality for all $\beta \ge \frac2m$ [Raginsky et al., 2017]. In this setting we have the following result which is stronger than directly applying thm:poincareoptlipschitz:

Suppose $F$ is $L$-smooth and $(m,b)$-dissipative (that is, there exist $m, b > 0$ such that $\tri*{\vecW, \nabla F(\vecW)} \ge m\nrm*{\vecW}^2-b$). Running either or with a stochastic gradient oracle satisfying ass:gradnoiseassumption and ass:stochasticgradcontrol, with probability at least $1-\delta$, across all the runs we will reach a $\vecW$ with $F(\vecW)\le\epsilon$ in at most

\[ \widetilde{O}\prn*{\max\crl*{d^3 \max(\CPI(\mu_{\beta}), 1)^3, \frac{d^{2} \max(\CPI(\mu_{\beta}), 1)^{2}}{\epsilon^{2}}} \log\prn*{\frac1{\delta}}} \]

gradient/stochastic gradient evaluations.

§ DIMENSION FREE RATES FOR SGLD UNDER STRONGER CONDITIONS

Our results in the above upper bound the hitting-time of GLD/SGLD to $\{\vecW:F(\vecW)<\epsilon\}$. As discussed in subsec:strategy, there is a close connection between a Poincaré Inequality, geometric properties, and hitting times of the Langevin Diffusion, so those results make intuitive sense. However, hitting times are a weaker guarantee than average suboptimality which is commonly studied in optimization. It is thus natural to ask if there are stronger conditions where we have guarantees not about not the hitting time but the average suboptimality $\frac1T \sum_{t=1}^T F(\vecW_t)$? This is indeed the case as we now discuss.

This idea is similar to that of De Sa et al., 2022. In De Sa et al., 2022, an analogous setup was considered where continuous-time gradient flow led to geometric properties and in discrete-time, the average suboptimality of gradient descent/stochastic gradient descent was studied under these geometric properties. This is the Itô calculus analogy of the work in De Sa et al., 2022.

Define a rate function for average suboptimality as follows: fix a desired tolerance $\epsilon=\widetilde{\Omega}\prn*{\frac{d}{\beta}}$. Define

\[ F_{\epsilon}(\vecW)=F(\vecW) \mathbf{1}_{\{\vecW:F(\vecW) \ge \epsilon\}}.\numberthis\label{eq:Fepsdef}\]

Here $\mathbf{1}_{\cA}$ denotes the indicator function of $\cA \subset\mathbb{R}^d$. Suppose we had some non-negative rate function $R(\vecW,t)$ upper bounding the suboptimality of $F$, namely such that $R(\vecW, t) \ge \mathbb{E}\brk*{F_{\epsilon}(\vecW(t))}$ for all $t \ge 0$. By rate function, we mean that the following conditions, natural for optimization, hold: $\lim_{t\rightarrow\infty}R(\vecW(0),t)=0$ for all $\vecW(0)$, and:

\[ \mathbb{E}\brk*{R(\vecW(s),t)} \le R(\vecW(0),s+t) \FORALLTEXT s, t \ge 0, \vecW(0)\in\mathbb{R}^d. \numberthis\label{eq:ldrateineq}\]

That is, in expectation more information about the Langevin Dynamics path improves the rate. Note from any rate function $R(\vecW,t)$, there is an equivalent rate function satisfying eq:ldrateineq; see De Sa et al., 2022 for more discussion.

It is important to note the following: we cannot have $R(\vecW,t) \ge \mathbb{E}\brk*{F(\vecW(t))}$: say after reaching $\epsilon$-suboptimality, gradients are very small and Langevin dynamics approximates a random walk. Then for all $t$ large enough, $\mathbb{E}\brk*{F(\vecW(t))} \approx c_0\epsilon$ for some $c_0=\Theta\prn*{1}$. We thus have for all $t$ large enough,

\[ R(\vecW, t)\ge \mathbb{E}\brk*{R(\vecW(t), 0)}\ge \mathbb{E}\brk*{F(\vecW(t))} \approx c_0\epsilon,\]

contradicting that $\lim_{t\rightarrow\infty}R(\vecW,t)=0$. However, our definition eq:Fepsdef resolves this problem: now for large enough $t$, $\mathbb{E}\brk*{F_{\epsilon}\prn*{\vecW(t)}}=0$, so eq:ldrateineq now holds.
Moreover, such a rate function clearly implies Langevin Dynamics works as an optimization strategy. In fact, such a rate function implies similar geometric properties to eq:lyapunovbaby from thm:maingeometriccondition:

A non-negative function $\Phi(\vecW)$ is an admissible potential with respect to the cost function $F_{\epsilon}(\vecW)$ if

\[ \tri*{ \nabla\Phi(\vecW),\nabla F(\vecW)} \ge F_{\epsilon}(\vecW)+\frac1{\beta} \Delta \Phi(\vecW).\numberthis\label{eq:admissablepotentialF}\]

Under mild assumptions on $F$ and $R$, suppose $R(\vecW,t)$ satisfies the relationship eq:ldrateineq and $\int_0^\infty R(\vecW,t) \DERIV t<\infty$ always holds true. Then $\Phi(\vecW)=\int_0^\infty R(\vecW,t) \DERIV t$ is an admissable potential.

Note the Langevin Diffusion with $\beta=\infty$ becomes gradient flow (). In De Sa et al., 2022, the success of an analogous rate function for GF implied
the very similar condition

\[ \tri*{\nabla F(\vecW), \nabla \Phi(\vecW)} \ge F(\vecW).\numberthis\label{eq:oldconditiongf}\]

Note eq:oldconditiongf implies eq:admissablepotentialF with $\beta=\infty$. The confirms the intuition that Langevin Dynamics optimizes a larger class of functions than can.

It turns out in the idealized continuous-time setting, eq:admissablepotentialF is enough to show that $F$ can be optimized: see subsec:optrategeometryformal and  thm:conditionimpliesrateproofformal.
But as Theorem 3 from De Sa et al., 2022 showed, to go to discrete time, we need assumptions on $\Phi$ such as self-bounding regularity assumptions.

$\Phi$ satisfies polynomial self-bounding regularity (def:selfboundingregularity) for degrees one through three.

Moreover, our potential function needs to capture reasonable information (e.g. it cannot remains small while the iterates $\vecW_t$ escapes to infinity).
We make this precise as follows.

Suppose we initialize $\vecW_0$ in $\ball(\vecOrigin, R_1')$ for some $R_1'>0$. Letting $\sup_{\vecW\in \ball(\vecOrigin, R_1')} \Phi(\vecW) = B'$, suppose that there is some $\kappa'>1$ and $R_1 > 0$ such that $\{\vecW:\Phi(\vecW)<\kappa' B'\} \subset \ball(\vecOrigin, R_1)$.

For $F$, we slightly loosen the assumptions compared to sec:contributions, and just assume ass:holderF holds for any $s \ge 0$.

From here, we have the following results for GLD and SGLD:

Suppose eq:admissablepotentialF holds for some $\beta=\tilde{\Omega}\prn*{\frac{d}{\epsilon}}$, where the Lyapunov function $\Phi \ge 0$ and where $F_{\epsilon}$ is defined from eq:Fepsdef. Suppose $F$ satisfies ass:holderF, and $\Phi$ satisfies ass:polyselfbounding and ass:iteratesinballassumption. Then running discrete-time with constant step size $\eta$ will, with probability at least $1-\delta$, yield a sequence of iterates $\vecW_t$ with $\frac1T \sum_{t=1}^T F(\vecW_t) = \widetilde{O}\prn*{\epsilon}$ in at most $T=O\prn*{\frac{1}{\epsilon^2}\log\prn*{\nicefrac1{\delta}}}$ iterations.

Suppose $F$, $\Phi$ satisfy the same assumptions as in thm:gradexactFeps. Then running with a stochastic gradient oracle satisfying ass:gradnoiseassumption, we obtain the same guarantees as thm:gradexactFeps.

We defer the proofs to sec:corediscreteproofs. The idea is similar to the sketch from subsec:strategy; we again use self-bounding regularity to control the higher order discretization terms. Note this implies the following result: using GLD/SGLD, we can not only optimize (via GLD) but also learn (via SGLD) any function for which Langevin Dynamics can optimize with a rate function well-behaved for optimization (one that is admissible).

However, we would like to loosen our condition eq:admissablepotentialF for it to hold for function classes of interest in optimization. By modifying our proofs, we can show success if we have the looser condition

\[ \tri*{ \nabla \Phi(\vecW), \nabla F(\vecW)} \ge F_{\epsilon}(\vecW) +\min\prn*{0, \frac1{\beta} \Delta\Phi(\vecW)}\numberthis\label{eq:loosenedcondition}.\]

whenever we can query $\tri*{ \nabla \Phi(\vecW), \nabla F(\vecW)} - F_{\epsilon}(\vecW)$. Note this is realistic, for example, if $\Phi = F$. This difference represents local gradient domination; if non-negative, gradient descent locally succeeds and we should not add noise. Otherwise, we add noise, and eq:loosenedcondition guarantees the noise will cancel the Laplacian (as in subsec:strategy). This algorithm is described formally as alg:sgldmodlaplacian in subsec:loosenconditionproofs. Note eq:loosenedcondition subsumes the condition eq:oldconditiongf implied by the success of gradient flow: in particular it contains Pfunctions and Kfunctions (see subsec:loosenconditiondiscussion).

Suppose that we have eq:loosenedcondition for some $\beta =\tilde{\Omega}\prn*{\frac{d}{\epsilon}}$, and $F$, $\Phi$ satisfy the same assumptions as thm:gradexactFeps.
Moreover suppose we have query access to $\tri*{ \nabla \Phi(\vecW), \nabla F(\vecW)} - F_{\epsilon}(\vecW)$. Now run modified Langevin Dynamics as described above with constant step size $\eta$. This will, with probability at least $1-\delta$, yield a sequence of iterates $\vecW_t$ with $\frac1T \sum_{t=1}^T F(\vecW_t) = \widetilde{O}\prn*{\epsilon}$ in at most $O\prn*{\frac{1}{\epsilon^2}\log\prn*{\nicefrac1{\delta}}}$ iterations.

We defer the proof to subsec:loosenconditionproofs, since it heavily relies on the analysis done in sec:corediscreteproofs. Again, note in all these results thm:gradexactFeps, <ref>, and <ref> that $\beta = \widetilde{\Omega}\prn*{\frac{d}{\epsilon}}$.

§.§.§ Acknowledgements

AS thanks Adam Block and Sasha Rakhlin for useful discussions and acknowledges support from the Simons Foundation and
NSF through award DMS-2031883, as well as from DOE through the award DE-SC0022199.

[Agarwal et al., 2021]
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.
On the theory of policy gradient methods: Optimality, approximation, and distribution shift.
Journal of Machine Learning Research, 220 (98):0 1–76, 2021.

[Allen-Zhu et al., 2019]
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.
A convergence theory for deep learning via over-parameterization.
In International Conference on Machine Learning, pages 242–252. PMLR, 2019.

[Altschuler and Chewi, 2023]
Jason M Altschuler and Sinho Chewi.
Faster high-accuracy log-concave sampling via algorithmic warm starts.
In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2169–2176. IEEE, 2023.

[Arora et al., 2015]
Sanjeev Arora, Rong Ge, Tengyu Ma, and Ankur Moitra.
Simple, efficient, and neural algorithms for sparse coding.
In Conference on Learning Theory, pages 113–149. PMLR, 2015.

[Bakry et al., 2008]
Dominique Bakry, Franck Barthe, Patrick Cattiaux, and Arnaud Guillin.
A simple proof of the poincaré inequality for a large class of probability measures.
Electronic Communications in Probability [electronic only], 13:0 60–66, 2008.

[Bakry et al., 2014]
Dominique Bakry, Ivan Gentil, Michel Ledoux, et al.
Analysis and geometry of Markov diffusion operators, volume 103.
Springer, 2014.

[Balasubramanian et al., 2022]
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 on Learning Theory, pages 2896–2923. PMLR, 2022.

[Bi et al., 2022]
Yingjie Bi, Haixiang Zhang, and Javad Lavaei.
Local and global linear convergence of general low-rank matrix recovery problems.
Proceedings of the AAAI Conference on Artificial Intelligence, 360 (9):0 10129–10137, 2022.

[Bobkov, 1999]
Sergey G Bobkov.
Isoperimetric and analytic inequalities for log-concave probability measures.
The Annals of Probability, 270 (4):0 1903–1921, 1999.

[Bonnefont, 2022]
Michel Bonnefont.
Poincaré inequality with explicit constant in dimension $d\ge1$.
https://www.math.u-bordeaux.fr/ mibonnef/Poincare__Toulouse.pdf, 2022.

[Bu et al., 2019]
Jingjing Bu, Afshin Mesbahi, Maryam Fazel, and Mehran Mesbahi.
Lqr through the lens of first order methods: Discrete-time case.
arXiv preprint arXiv:1907.08921, 2019.

[Bubeck et al., 2015]
Sébastien Bubeck et al.
Convex optimization: Algorithms and complexity.
Foundations and Trends in Machine Learning, 80 (3-4):0 231–357, 2015.

[Candes et al., 2015]
Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi.
Phase retrieval via wirtinger flow: Theory and algorithms.
IEEE Transactions on Information Theory, 610 (4):0 1985–2007, 2015.

[Carmona and Klein, 1983]
René Carmona and Abel Klein.
Exponential moments for hitting times of uniformly ergodic markov processes.
The Annals of Probability, 110 (3):0 648–655, 1983.

[Cattiaux and Guillin, 2017]
Patrick Cattiaux and Arnaud Guillin.
Hitting times, functional inequalities, lyapunov conditions and uniform ergodicity.
Journal of Functional Analysis, 2720 (6):0 2361–2391, 2017.

[Cattiaux et al., 2009]
Patrick Cattiaux, Arnaud Guillin, Feng-Yu Wang, and Liming Wu.
Lyapunov conditions for super poincaré inequalities.
Journal of Functional Analysis, 2560 (6):0 1821–1841, 2009.

[Cattiaux et al., 2010]
Patrick Cattiaux, Nathael Gozlan, Arnaud Guillin, and Cyril Roberto.
Functional inequalities for heavy tailed distributions and application to isoperimetry.
Electronic Journal of Probability, 15, 2010.

[Cattiaux et al., 2013]
Patrick Cattiaux, Arnaud Guillin, and Pierre André Zitt.
Poincaré inequalities and hitting times.
Annales de l'IHP Probabilités et Statistiques, 490 (1):0 95–118, 2013.

[Chen, 2021]
Yuansi Chen.
An almost constant lower bound of the isoperimetric coefficient in the kls conjecture.
Geometric and Functional Analysis, 31:0 34–61, 2021.

[Chen et al., 2019]
Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma.
Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval.
Mathematical Programming, 176:0 5–37, 2019.

[Chewi, 2024]
Sinho Chewi.
Log-concave sampling.
Book draft available at https://chewisinho. github.io, 2024.

[Chewi et al., 2022]
Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, and Shunshi Zhang.
Analysis of langevin monte carlo from poincare to log-sobolev.
In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1–2. PMLR, 02–05 Jul 2022.
URL <https://proceedings.mlr.press/v178/chewi22a.html>.

[Chiang et al., 1987]
Tzuu-Shuh Chiang, Chii-Ruey Hwang, and Shuenn Jyi Sheu.
Diffusion for global optimization in rn.
SIAM Journal on Control and Optimization, 250 (3):0 737–753, 1987.

[De Sa et al., 2022]
Christopher M De Sa, Satyen Kale, Jason D Lee, Ayush Sekhari, and Karthik Sridharan.
From gradient flow on population loss to learning with stochastic gradient descent.
Advances in Neural Information Processing Systems, 35:0 30963–30976, 2022.

[Down et al., 1995]
Douglas Down, Sean P Meyn, and Richard L Tweedie.
Exponential and uniform ergodicity of markov processes.
The Annals of Probability, 230 (4):0 1671–1691, 1995.

[Fatkhullin and Polyak, 2021]
Ilyas Fatkhullin and Boris Polyak.
Optimizing static linear feedback: Gradient method.
SIAM Journal on Control and Optimization, 590 (5):0 3887–3911, 2021.

[Huang et al., 2024]
Xunpeng Huang, Difan Zou, Yi-An Ma, Hanze Dong, and Tong Zhang.
Faster sampling via stochastic gradient proximal sampler.
arXiv preprint arXiv:2405.16734, 2024.

[Jain et al., 2017]
Prateek Jain, Chi Jin, Sham Kakade, and Praneeth Netrapalli.
Global convergence of non-convex gradient descent for computing matrix squareroot.
In Artificial Intelligence and Statistics, pages 479–488. PMLR, 2017.

[Jambulapati et al., 2022]
Arun Jambulapati, Yin Tat Lee, and Santosh S Vempala.
A slightly improved bound for the kls constant.
arXiv preprint arXiv:2208.11644, 2022.

[Jin et al., 2016]
Chi Jin, Sham M Kakade, and Praneeth Netrapalli.
Provable efficient online matrix completion via non-convex stochastic gradient descent.
Advances in Neural Information Processing Systems, 29, 2016.

[Kannan et al., 1995]
Ravi Kannan, László Lovász, and Miklós Simonovits.
Isoperimetric problems for convex bodies and a localization lemma.
Discrete & Computational Geometry, 13:0 541–559, 1995.

[Klartag, 2023]
Bo'az Klartag.
Logarithmic bounds for isoperimetry and slices of convex sets.
arXiv preprint arXiv:2303.14938, 2023.

[Klartag and Lehec, 2022]
Bo’az Klartag and Joseph Lehec.
Bourgain’s slicing problem and kls isoperimetry up to polylog.
Geometric and Functional Analysis, 320 (5):0 1134–1159, 2022.

[Kurdyka, 1998]
Krzysztof Kurdyka.
On gradients of functions definable in o-minimal structures.
Annales de l'institut Fourier, 480 (3):0 769–783, 1998.

[Lee and Vempala, 2024]
Yin Tat Lee and Santosh S Vempala.
Eldan’s stochastic localization and the kls conjecture: Isoperimetry, concentration and mixing.
Annals of Mathematics, 1990 (3), 2024.

[Lee et al., 2021]
Yin Tat Lee, Ruoqi Shen, and Kevin Tian.
Structured logconcave sampling with a restricted gaussian oracle.
In Conference on Learning Theory, pages 2993–3050. PMLR, 2021.

[Lojasiewicz, 1963]
Stanislaw Lojasiewicz.
A topological property of real analytic subsets.
Coll. du CNRS, Les équations aux dérivées partielles, 1170 (87-89):0 2, 1963.

[Mei et al., 2020]
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans.
On the global convergence rates of softmax policy gradient methods.
In International Conference on Machine Learning, pages 6820–6829. PMLR, 2020.

[Mei et al., 2021]
Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans.
Leveraging non-uniformity in first-order non-convex optimization.
In International Conference on Machine Learning, pages 7555–7564. PMLR, 2021.

[Meyn and Tweedie, 1993]
Sean P Meyn and Richard L Tweedie.
Stability of markovian processes iii: Foster–lyapunov criteria for continuous-time processes.
Advances in Applied Probability, 250 (3):0 518–548, 1993.

[Meyn and Tweedie, 2012]
Sean P Meyn and Richard L Tweedie.
Markov chains and stochastic stability.
Springer Science & Business Media, 2012.

[Mou et al., 2022]
Wenlong Mou, Nicolas Flammarion, Martin J Wainwright, and Peter L Bartlett.
Improved bounds for discretization of langevin diffusions: Near-optimal rates without convexity.
Bernoulli, 280 (3):0 1577–1601, 2022.

[Mousavi-Hosseini et al., 2023]
Alireza Mousavi-Hosseini, Tyler K Farghly, Ye He, Krishna Balasubramanian, and Murat A Erdogdu.
Towards a complete analysis of langevin monte carlo: Beyond poincaré inequality.
In The Thirty Sixth Annual Conference on Learning Theory, pages 1–35. PMLR, 2023.

[Nemirovski et al., 2009]
A Nemirovski, A Juditsky, G Lan, and A Shapiro.
Stochastic approximation approach to stochastic programming.
SIAM Journal on Optimization, 190 (4):0 1574–1609, 2009.

[Øksendal, 2003]
Bernt Øksendal.
Stochastic differential equations.
Springer, 2003.

[Peskir and Shiryaev, 2006]
Goran Peskir and Albert Shiryaev.
Optimal stopping and free-boundary problems.
Springer, 2006.

[Polyak, 1963]
Boris T Polyak.
Gradient methods for the minimisation of functionals.
USSR Computational Mathematics and Mathematical Physics, 30 (4):0 864–878, 1963.

[Raginsky et al., 2017]
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky.
Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis.
In Conference on Learning Theory, pages 1674–1703. PMLR, 2017.

[Street, 2018]
Brian Street.
What else about… hypoellipticity?
Notices of the AMS, 650 (4), 2018.

[Tan and Vershynin, 2023]
Yan Shuo Tan and Roman Vershynin.
Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval.
Journal of Machine Learning Research, 240 (58):0 1–47, 2023.

[Vempala and Wibisono, 2019]
Santosh Vempala and Andre Wibisono.
Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices.
Advances in Neural Information Processing Systems, 32, 2019.

[Vershynin, 2018]
Roman Vershynin.
High-dimensional probability: An introduction with applications in data science, volume 47.
Cambridge university press, 2018.

[Xu et al., 2018]
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, 31, 2018.

[Yang, 2020]
Zhipeng Yang.
What is hypoellipticity?
https://www.yzpmath.com/post/2020-2/2020-2.pdf, 2020.

[Yuan et al., 2022]
Rui Yuan, Robert M Gower, and Alessandro Lazaric.
A general sample complexity analysis of vanilla policy gradient.
In International Conference on Artificial Intelligence and Statistics, pages 3332–3380. PMLR, 2022.

[Zeng et al., 2018]
Jinshan Zeng, Shikang Ouyang, Tim Tsz-Kit Lau, Shaobo Lin, and Yuan Yao.
Global convergence in deep learning with variable splitting via the kurdyka-łojasiewicz property.
arXiv preprint arXiv:1803.00225, 9, 2018.

[Zhang et al., 2024]
Ruiqi Zhang, Spencer Frei, and Peter L Bartlett.
Trained transformers learn linear models in-context.
Journal of Machine Learning Research, 250 (49):0 1–55, 2024.

[Zhang et al., 2017]
Yuchen Zhang, Percy Liang, and Moses Charikar.
A hitting time analysis of stochastic gradient langevin dynamics.
In Conference on Learning Theory, pages 1980–2022. PMLR, 2017.

[Zou et al., 2021]
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–1162. PMLR, 2021.

§ SETUP FOR REST OF PAPER

The appendix is organized as follows. We derive our `continuous time' results (thm:maingeometriccondition and thm:constructadmissablepotential) in sec:continuoustimeproofs.
We present our proofs for sec:beyondpoincare first in sec:corediscreteproofs, proving thm:gradexactFeps, <ref>, and <ref>; later our proofs of thm:poincareoptlipschitz, <ref>, and <ref> rely on some of this work. Finally, in sec:PIoptproofs we prove thm:poincareoptlipschitz, <ref>, and <ref>.

§.§ Additional Notation

In the following, $\log$ always denotes natural logarithm. The notation $U\prn*{[a,b]}$ refers to the uniform distribution on $[a,b]$. The notation $\delta_{\cA}$ denotes the Dirac Delta on some event $\cA$. The notation $\Gamma$ refers to the Gamma function.

The notation $d(p, \cA)$ refers to the minimum distance from a point $p \in \mathbb{R}^d$ to a set $\cA \subset \mathbb{R}^d$. For a set $\cU \subset \mathbb{R}^d$, $\partial \cU$ denotes its boundary. For a vector $\vecW\in\mathbb{R}^d$, $\vecW_i$ refers to its $i$-th coordinate. For a $k$-th order tensor operator $T$ and $\vecV_1, \ldots, \vecV_k\in\mathbb{R}^d$, $T\brk*{\vecV_1,\ldots,\vecV_k}$ refers to applying $T$ to the $k$-th order tensor $\vecV_1 \otimes \dots \otimes \vecV_k$, that is, $\tri*{T, \vecV_1 \otimes \dots \otimes \vecV_k}$.

Again, we will refer to the measure on $\mathbb{R}^d$ proportional to $e^{-\beta F(\vecW)}$ by $\mu_{\beta}$ (the subscript shows the dependence on the temperature, which is crucial for optimization). When we write $Z$, it refers to the normalizing constant $\int_{\mathbb{R}^d} e^{-\beta F(\vecW)} \DERIV\vecW$ of the measure, unless specified otherwise (so it may change line-to-line if we refer to different measures). For any set $\cU \subset\mathbb{R}^d$, let the hitting time of the SDE eq:langevindiffusioncorrect initialized at $\vecW$ to $\cU$ be $\tau'_{\cU}(\vecW)$.

Before we apply results from probability regarding the continuous-time Langevin Diffusion, consider the SDE

\[ \DERIV \vecW(t) = -\beta\grad  F(\vecW(t)) \DERIV t + \sqrt{2} \DERIV \vecB(t). \numberthis\label{eq:langevindiffusioncorrect}\]

We refer to this SDE when we directly use results from Cattiaux et al., 2013 and Cattiaux and Guillin, 2017, so that our convention for Poincaré and Log-Sobolev constants will match theirs. Note eq:langevindiffusioncorrect is equivalent to eq:LangevinSDE. For a given realization of a Brownian motion driving both SDEs, both SDEs will trace out the same path. However in eq:langevindiffusioncorrect time passes `$\beta$ times faster' than in eq:LangevinSDE. Hence for any set $\cU \subset\mathbb{R}^d$, the hitting time of the SDE eq:langevindiffusioncorrect to $\cU$ is $\frac1{\beta}$ (i.e. faster if $\beta \ge 1$) than that of the hitting time of eq:LangevinSDE to $\cU$, if both SDEs are driven by the same Brownian motion. That is, using our notation, we have $\tau'_{\cU} = \frac1{\beta} \tau_{\cU}$ for all $\cU \subset \mathbb{R}^d$.

§ PROOFS FOR CONTINUOUS TIME

§.§ Proof of thm:maingeometriccondition and Related Results

Now we restate thm:maingeometriccondition formally here. Note thm:maingeometricconditionformal requires us to control $\mu\prn*{\cA_{\epsilon}}$ in the $\lambda$ from thm:maingeometriccondition, for which we need lem:measureoflargeF. lem:measureoflargeF is precisely where we need $\epsilon = \widetilde{\Omega}\prn*{\frac{d}{\beta}}$. This leads to consistency between our results and our discussion from subsec:ourcontributions. We defer lem:measureoflargeF to later in this section and note thm:maingeometriccondition follows immediately from combining thm:maingeometricconditionformal and lem:measureoflargeF.

Assume that $\mu_{\beta}$ satisfies a Poincaré inequality with constant $\CPI(\mu_{\beta})$. Then there exists a non-negative Lyapunov function $\Phi$ differentiable to all others such that on $\cA_{\epsilon}^c$, we have $\Phi \ge 1$ and

\[ -\tri*{\grad F(\vecW), \grad \Phi(\vecW)} + \frac1{\beta} \Delta\Phi(\vecW) \le-\lambda\Phi(\vecW),\numberthis\label{eq:poincaregeomcondition}\]

\[ \lambda = \frac1{\beta}\mu_{\beta}\prn*{\cA_{\epsilon}} \min\prn*{\frac1{4\CPI(\mu_{\beta})}, \frac18}.\]

In fact, on $\cA_{\epsilon}^c$, $\Phi$ has the explicit form

\[ \Phi(\vecW') = \mathbb{E}_{\vecW'}\brk*{\exp\prn*{\lambda \tau_{\cA_{\epsilon}}}}.\]

We first need to introduce some concepts from Markov processes and Partial Differential Equations (PDEs). First, we introduce the concept of the (infinitesimal) generator of a Markov process, which will make this exposition much more natural. We give only what is needed for our proof and refer the reader to Chewi, 2024 for more details.

The (infinitesimal) generator of a Markov process $\vecW(t)$ is the operator $\mathcal{L}$ defined on all (sufficiently differentiable) functions $f$ by

\[ \mathcal{L}f(\vecW) = \lim_{t\rightarrow0}\frac{\mathbb{E}\brk*{f(\vecW(t))}-f(\vecW)}{t}.\]

It is well-known and can be easily checked that for the Langevin Diffusion given in the form eq:langevindiffusioncorrect, the generator

\[ \mathcal{L}f(\vecW) = -\tri*{\beta \grad F(\vecW), \grad f(\vecW)} + \Delta f(\vecW).\numberthis\label{eq:generatorlangevin}\]

For example, this calculation can be found in Example 1.2.4 of Chewi et al., 2022.

Note the similarity of the above to eq:lyapunovbaby. This is no coincidence; our discrete-time proofs, specifically lem:onesteprecursion and lem:onesteprecursionstochastic, are essentially re-deriving the generator of the Langevin diffusion. In lem:onesteprecursion and lem:onesteprecursionstochastic we Taylor expand to third order (so we have the full second order quadratic form); intuitively that is all that is needed by Itô's Lemma.

We also need to introduce the idea of symmetry of the measure $\mu_{\beta}$ with respect to the stochastic process. In particular, we say $\mu_{\beta}$ is symmetric (with respect to the Langevin Diffusion eq:langevindiffusioncorrect) if for all infinitely differentiable $f, g$,

\[ \int f \cL g \DERIV\mu_{\beta} = \int \cL f g \DERIV\mu_{\beta}.\]

Here $\cL$ refers to the generator eq:generatorlangevin for the Langevin Diffusion eq:langevindiffusioncorrect. It is well-known and can be easily checked again that $\mu_{\beta}$ is symmetric, see Example 1.2.18 of Chewi et al., 2022 or the discussion on page 3 of Cattiaux and Guillin, 2017.

Finally, we need to introduce some ideas from PDE theory. Consider a second-order differential operator

\[ \mathcal{P} = \frac12\sum_{1 \le i < j \le d} a_{ij}\frac{\partial^2}{\partial \vecW_i \partial \vecW_j} + \sum_{1 \le i \le d} b_i \frac{\partial}{\partial \vecW_i} + c.\]

The following definitions generalize far beyond second-order differential operators, but this is all we need for our work. We say that $\mathcal{P}$ is elliptic if, for every $\vecW \neq 0 \in \mathbb{R}^d$,

\[ \sum_{1 \le i, j \le d} a_{ij} \vecW_i \vecW_j \neq 0.\]

We say $\mathcal{P}$ is uniformly elliptic if we can write

\[\mathcal{P} = \frac12\sum_{1 \le i < j \le d} \prn*{\mathbf{\sigma} \mathbf{\sigma}^T}_{ij} \frac{\partial^2}{\partial \vecW_i \partial \vecW_j} + \sum_{1 \le i \le d} b_i \frac{\partial}{\partial \vecW_i} +c,\]

for some $\mathbf{\sigma} \in \mathbb{R}^d$ where uniformly on $\mathbb{R}^d$ we have

\[ \mathbf{\sigma} \mathbf{\sigma}^T\succcurlyeq a > 0\]

in the PSD order [Street, 2018, Cattiaux and Guillin, 2017].

A canonical example of $\mathcal{P}$ that is uniformly elliptic is the Laplacian, where $a_{ij} = 2\delta_{i=j}$ [Yang, 2020]. Beyond this, note for the Langevin Diffusion eq:langevindiffusioncorrect, we have $a_{ij}=2\delta_{i=j}$ as well, from eq:generatorlangevin. Thus, it is clear that $\cL$ for the Langevin Diffusion eq:langevindiffusioncorrect is uniformly elliptic.

Ellipticity is well-known to imply that solutions $u$ to the Dirichlet problem $\mathcal{P} u = f$ in some open domain $\Omega \subset \mathbb{R}^d$ are smooth, which is all we need here [Yang, 2020].[For this, ellipticity is sufficient but not necessary. The loosest such condition for this is hypoellipticity [Street, 2018, Yang, 2020], which is not relevant for this work.] Ellipticity implies maximal hypoellipticity, which in turn implies strong hypoellipticity/Hormander's condition from Cattiaux et al., 2013, as discussed in Yang, 2020. Thus uniform ellipticity implies strong uniform hypoellipticity as defined in Cattiaux et al., 2013. Using the results of Cattiaux et al., 2013 requires strong uniform hypoellipticity and symmetry with respect to the stochastic process, and Cattiaux and Guillin, 2017 requires uniform ellipticity and symmetry. We have uniform ellipticity and symmetry, and so can use all those results.

Now we move to the main proof. Our main tool is Theorem 2.1 of Cattiaux and Guillin, 2017, which connects Poincaré Inequalities to more explicit geometric conditions that we can use in an `optimization-styled' proof analysis later.[We presume here $F$ is sufficiently differentiable to use the results of Cattiaux et al., 2013 and Cattiaux and Guillin, 2017, for example this holds if $F$ is infinitely differentiable. The careful reader will notice that $F$ can be approximated by an infinitely differentiable function to arbitrary precision. We also assume the boundary $\partial \cA_{\epsilon} = \{\vecW:F(\vecW)=\epsilon\}$ is differentiable to all orders, non-characteristic for eq:langevindiffusioncorrect in the sense described in Cattiaux et al., 2013 and Cattiaux and Guillin, 2017, and has Lebesgue measure 0. In the $F$ Lipschitz case we assume this set is bounded and hence compact; boundedness and hence compactness follows from ass:weakdissipation in all other cases. Since we can approximate $F$ by an infinitely differentiable function to arbitrary precision, this boundary in turn will be infinitely differentiable.] Specialized to the Langevin Diffusion eq:langevindiffusioncorrect on the domain $\cD=\mathbb{R}^d$, it states the following:

Suppose that $\mu_{\beta}$ satisfies a Poincaré Inequality with constant $\CPI(\mu_{\beta})$. Then for all open subsets $\cU$ of $\mathbb{R}^d$, there exists a function $\Phi$ differentiable to all orders such that on $\cU^c$ we have $\Phi \ge \delta' > 0$ for some $\delta'$, as well as

\begin{align*} \mathcal{L}\Phi(\vecW)=-\tri*{\beta \grad F(\vecW), \grad \Phi(\vecW)} + \Delta\Phi(\vecW) \le -\lambda'\Phi(\vecW),\numberthis\label{eq:originalphiineq}\end{align*}

where $\lambda'=\mu_{\beta}\prn*{\mathcal{U}} \min\prn*{\frac1{4\CPI(\mu_{\beta})}, \frac18}$.

Note to prove this result in $\cD=\mathbb{R}^d$ all that is needed is ellipticity, which is clearly satisfied here in the case of the Langevin diffusion (following the discussion on page 9 of Cattiaux and Guillin, 2017). Hence, applying thm:cattiauxopenresult with $\cU=\{\vecW:F(\vecW)<\epsilon\}$ which is clearly open, this gives the existence of such a $\Phi$.

Suppose $\{\vecW:\Phi(\vecW) \le \frac{\delta'}2\} \neq \emptyset$. In this case, consider $\{\vecW:\Phi(\vecW) \le \frac{\delta'}2\} \subset \{\vecW:\Phi(\vecW) < \frac{3\delta'}4\} \subset \{\vecW:F(\vecW)<\epsilon\}$. Apply the standard construction of bump functions to the compact set $\{\vecW:\Phi(\vecW) \le \frac{\delta'}2\}$ contained in the open set $\{\vecW:\Phi(\vecW) < \frac{3\delta'}4\}$ to obtain a function $\chi$ differentiable to all orders supported on $\{\vecW:\Phi(\vecW) < \frac{3\delta'}4\}$ and identically 1 on $\{\vecW:\Phi(\vecW) \le \frac{\delta'}2\}$. Let $B = \inf \Phi \le \frac{\delta'}2$. It is easy to check that $\Phi + \prn*{\frac{\delta'}2 + \max\prn*{0, -B}}\chi \ge \frac{\delta'}2$, and differentiable to all orders as $\Phi$ and $\chi$ are, and is identical to $\Phi$ on $\{\vecW:F(\vecW)\ge\epsilon\}$. Taking $\Phi \leftarrow \Phi + \prn*{\frac{\delta'}2 + \max\prn*{0, -B}}\chi \ge \frac{\delta'}2$, this gives us the existence of $\Phi \ge \frac{\delta'}2$ differentiable to all orders where we know on $\{\vecW:F(\vecW)\ge\epsilon\}$, it satisfies eq:originalphiineq.

Notice $\mu_{\beta}\prn*{\{\vecW:F(\vecW)<\epsilon\}} = \mu_{\beta}\prn*{\cA_{\epsilon}}$, since $\mu_{\beta}\prn*{\partial \cA_{\epsilon}}=\mu_{\beta}\prn*{\{\vecW:F(\vecW)=\epsilon\}}$ is simply a positive constant times the Lebesgue measure of $\partial \cA_{\epsilon}$, and hence is 0. Therefore we know for this $\Phi$,

\[\mathcal{L}\Phi(\vecW)=-\tri*{\beta \grad F(\vecW), \grad \Phi(\vecW)} + \Delta\Phi(\vecW) \le-\lambda'\Phi(\vecW)=-\beta \lambda \Phi(\vecW).\numberthis\label{eq:geomconditionproof}\]

We claim with such a $\Phi$, the moment generating function $\mathbb{E}_{\vecW'}\brk*{\exp\prn*{\beta\lambda \tau'_{\cA_{\epsilon}}}}$ exists (i.e. is finite). The argument is done explicitly on page 8 of Cattiaux et al., 2013 (connectivity of $\cA$ is not necessary, as one will see below). We write it here explicitly here for the reader. Clearly this MGF is finite for $\vecW' \in \cA_{\epsilon}$, so consider any $\vecW' \in \cA_{\epsilon}^c$. Consider any $t<\infty$, any $R < \infty$ and consider the hitting time $\tau'_{\cA_{\epsilon} \cup \ball\prn*{\vecOrigin, R}^c}$. Denote $\tau'_{t,\epsilon,R} := t \land \tau'_{\cA_{\epsilon} \cup \ball\prn*{\vecOrigin, R}^c}$ for short, which is clearly a stopping time. Apply Dynkin's Formula to the map $(s,\vecW) \rightarrow e^{\beta \lambda s} \Phi(\vecW)$ with the stopping time $\tau'_{t,\epsilon,R}$; thus for all $s<\tau'_{t,\epsilon,R}$, we know $\Phi\prn*{\vecW(s)}$ satisfies eq:geomconditionproof. We obtain:

\begin{align*}
\frac{\delta'}2 \mathbb{E}_{\vecW'}\brk*{\text{exp}\prn*{\beta \lambda \tau'_{t,\epsilon,R}}} &\le \mathbb{E}_{\vecW'}\brk*{\text{exp}\prn*{\beta \lambda\tau'_{t,\epsilon,R}} \Phi\prn*{\vecW(\tau'_{t,\epsilon,R})}} \\
&= \Phi(\vecW') + \mathbb{E}_{\vecW'}\brk*{ \int_0^{\tau'_{t,\epsilon,R}} \text{exp}\prn*{\beta \lambda s}\prn*{\beta \lambda\Phi\prn*{\vecW(s)} + \mathcal{L}\Phi\prn*{\vecW(s)}} \DERIV s} \\
&\le \Phi(\vecW') + \mathbb{E}_{\vecW'}\brk*{ \int_0^{\tau'_{t,\epsilon,R}} \text{exp}\prn*{\beta \lambda s}\prn*{\beta \lambda\Phi\prn*{\vecW(s)} - \beta \lambda \Phi\prn*{\vecW(s)}} \DERIV s} \\
&= \Phi(\vecW').
\end{align*}

For justification, the first line above follows as $\Phi(\vecW) \ge \frac{\delta'}2$. Dynkin's Formula and then Chain Rule and Itô's Lemma are used in the second line (an analogous calculation is done formally on page 121, Peskir and Shiryaev, 2006). The third line uses the geometric condition eq:geomconditionproof that we know $\Phi\prn*{\vecW(s)}$ satisfies for $s<\tau'_{t,\epsilon,R}$.

Thus, we have for all $t<\infty$, $R<\infty$ that

\[ \mathbb{E}_{\vecW'}\brk*{\text{exp}\prn*{\beta \lambda\tau'_{t,\epsilon,R}}} \le \frac{2\Phi(\vecW')}{\delta'}<\infty.\]

Recalling $\delta'>0$ is independent of $R,t$, letting first $R \rightarrow \infty$ and then $t \rightarrow \infty$, Dominated Convergence Theorem gives the result $\mathbb{E}_{\vecW'}\brk*{\exp\prn*{\beta\lambda \tau'_{\cA_{\epsilon}}}} \le \frac{2\Phi(\vecW')}{\delta'} < \infty$ (since the right hand side above is a finite upper bound independent of $R,t$).

We now claim the moment generating function $\mathbb{E}_{\vecW'}\brk*{\exp\prn*{\beta\lambda \tau'_{\cA_{\epsilon}}}}$, which we now know exists, satisfies eq:poincaregeomcondition. In fact this holds as an equality on $\cA_{\epsilon}^c$ (although we don't need this). This is shown on page 8 of Cattiaux et al., 2013 and discussed on page 12 of Cattiaux and Guillin, 2017. Thus, here we just give a sketch; it follows by literature on PDEs, specifically Dirichlet problems. The result used to prove this is result 1 of Section 7.2 of Peskir and Shiryaev, 2006:

Let $\cU$ be a bounded, open subset of $\mathbb{R}^d$. Given a continuous function $L:\cU \rightarrow\mathbb{R}$ define

\[ F(\vecW) = \mathbb{E}_{\vecW}\brk*{\int_0^{\tau'_{\cU^c}} L\prn*{\vecW(t)}\DERIV t},\]

where $\vecW(t)$ here denotes the iterates of any diffusion process and $\tau'_{\cU^c}$ denotes the hitting time of $\vecW(t)$ to $\cU^c$. Then $F$ solves the Dirichlet problem

\[ \mathcal{L} F = -L \text{ in }\cU, F|_{\partial \cU}=0.\]

Here, $\mathcal{L}$ is the generator of this diffusion.

Consider any $R<\infty$. Consider $\cU_{\epsilon,R} := \cA_{\epsilon}^c \cap \{\vecW:\nrm*{\vecW}<R\}$, which is clearly open. Now, we apply the same reasoning as Result 4 of Section 7.2 of Peskir and Shiryaev, 2006 (the killed version of the Dirichlet problem), except now we want to study the created version of the Dirichlet problem[See Section 5.4, [Peskir and Shiryaev, 2006].]. There is not much difference, thus we just give a sketch and refer the reader to Result 4 of Section 7.2 of Peskir and Shiryaev, 2006 and again page 8 of Cattiaux et al., 2013. Let $L \equiv \beta \lambda$ be a constant function and now let $\vecW(t)$ denotes the iterates of the Langevin diffusion eq:langevindiffusioncorrect. Consider

\[ F(\vecW) = \mathbb{E}_{\vecW}\brk*{\int_0^{\tau'_{\cU_{\epsilon,R}^c}} e^{\beta \lambda t} \beta \lambda \DERIV t} = \mathbb{E}_{\vecW}\brk*{\int_0^{\tau'_{\cU_{\epsilon,R}^c}} e^{\beta \lambda t} L\prn*{\vecW(t)}\DERIV t}. \]

where $\tau'_{\cU^c}$ now is consistent with our definition from sec:setup, being for the Langevin Diffusion eq:langevindiffusioncorrect. Observe that

\[ F(\vecW)+1=\mathbb{E}_{\vecW}\brk*{1+\int_0^{\tau'_{\cU_{\epsilon,R}^c}} e^{\beta \lambda t} \beta \lambda \DERIV t} = \mathbb{E}_{\vecW}\brk*{e^{\beta \lambda \tau'_{\cU_{\epsilon,R}^c}}} \le \mathbb{E}_{\vecW}\brk*{e^{\beta \lambda \tau'_{\cA_{\epsilon}}}} < \infty,\]

since $\frac{\partial}{\partial t} e^{\beta \lambda t} = \beta \lambda e^{\beta \lambda t}$, $\tau'_{\cU_{\epsilon,R}^c} \le \tau'_{\cA_{\epsilon}}$. Hence, $F(\vecW)<\infty$ and so we may continue to analyze it.

Now consider $\tilde{\vecW}(t) := e^{\beta \lambda t}\vecW(t)$ (the created process). By the same reasoning as in Result 4 of Section 7.2 of Peskir and Shiryaev, 2006 but for the created rather than killed process, we have $F(\vecW) = \mathbb{E}_{\vecW}\brk*{\int_0^{\tilde{\tau'}_{\cU_{\epsilon,R}^c}} L\prn*{\vecW(t)}\DERIV t}$ where $\tilde{\tau'}_{\cU_{\epsilon,R}^c}$ denotes the hitting time of $\tilde{\vecW}(t)$ to $\cU_{\epsilon,R}^c$. Let the generator of $\tilde{\vecW}(t)$ be $\tilde{\cL}$. Now, thm:fundamentaldirichletproblem implies that $F(\vecW)$ solves the Dirichlet problem

\[ \tilde{\cL}F = -L = -\beta \lambda \text{ in }\cU_{\epsilon,R}, F|_{\partial \cU_{\epsilon,R}} = 0.\]

It can be readily seen that by Chain Rule that $\tilde{\cL} = \cL + \beta\lambda$; this calculation is done formally on page 121, Peskir and Shiryaev, 2006. Therefore, we have

\[ -\beta \lambda = \tilde{\cL}F = \cL F + \beta \lambda F\text{ in } \cU_{\epsilon,R}, F|_{\partial \cU_{\epsilon,R}} = 0.\]

Therefore, $\Phi_R = F+1$ satisfies (note $\cL \Phi_R = \cL F$)

\[ \cL \Phi_R = \cL F = -\beta \lambda (F+1) = -\beta \lambda \Phi_R\text{ in } \cU_{\epsilon,R}, \Phi_R|_{\partial \cU_{\epsilon,R}}=1.\]

Note we showed earlier

\[ \Phi_R(\vecW)=F(\vecW)+1=\mathbb{E}_{\vecW}\brk*{1+\int_0^{\tau'_{\cU_{\epsilon,R}^c}} e^{\beta \lambda t} \beta \lambda \DERIV t} = \mathbb{E}_{\vecW}\brk*{e^{\beta \lambda \tau'_{\cU_{\epsilon,R}^c}}}.\]

Finally, since we've already shown $\mathbb{E}_{\vecW}\brk*{e^{\beta \lambda \tau'_{\cA_{\epsilon}}}}<\infty$, the same argument of page 8 of Cattiaux et al., 2013 shows that the pointwise limit

\[ \Phi(\vecW) := \mathbb{E}_{\vecW}\brk*{e^{\beta \lambda \tau'_{\cA_{\epsilon}}}} = \lim_{R\rightarrow\infty} \mathbb{E}_{\vecW}\brk*{e^{\beta \lambda \tau'_{\cU_{\epsilon,R}^c}}} \]

exists and solves the Dirichlet Problem

\[ \cL \Phi = -\beta \lambda \Phi \text{ in }\lim_{R\rightarrow\infty}\cU_{\epsilon,R} \cap \{\vecW:\nrm*{\vecW}<R\} =\cA_{\epsilon}^c.\]

Thus, it satisfies eq:poincaregeomcondition. Moreover, since $\cL$ is elliptic (and therefore hypoelliptic), the resulting solution

\[ \Phi(\vecW) = \mathbb{E}_{\vecW}\brk*{e^{\beta \lambda \tau'_{\cA_{\epsilon}}}}\]

is differentiable to all orders in $\lim_{R\rightarrow\infty}\cA_{\epsilon}^c \cap \{\vecW:\nrm*{\vecW}<R\} = \cA_{\epsilon}^c$. Note since the quantity in the exponential is always non-negative pointwise, $\Phi(\vecW) \ge 1$ on $\cA_{\epsilon}^c$.

Since the boundary $\partial \cA_{\epsilon}=\{\vecW:F(\vecW)=\epsilon\}$ is compact and differentiable to all orders, through a standard compactness and $\delta-\epsilon$ argument we can show by defining

\[ \Phi(\vecW) = \lim_{\vecW' \rightarrow \vecW, \vecW' \in \cA_{\epsilon}^c} \Phi(\vecW') \FORALLTEXT \vecW \in \partial \cA_{\epsilon},\]

the resulting $\Phi$ is differentiable to all orders on $\cA_{\epsilon}^c \cup \partial \cA_{\epsilon}$ (when we define derivatives as the limits coming from outside $\cA_{\epsilon}^c$). (Compactness here is important.) As $\cA_{\epsilon}^c \cup \partial \cA_{\epsilon}$ is closed, applying Whitney's Extension Theorem as mentioned in [Cattiaux et al., 2013], $\Phi$ above can be extended to a function differentiable to all orders on all of $\mathbb{R}^d$ so that eq:poincaregeomcondition holds on $\{\vecW:F(\vecW) \ge \epsilon\}$. Note $\Phi \ge 1$ on $\{\vecW:F(\vecW) \ge \epsilon\}$.

Suppose the resulting $\Phi$ from the extension was not non-negative. Let $B:=\inf \Phi <0$. Observe $\{\vecW:\Phi(\vecW) \le 0\} \subset \{\vecW:\Phi(\vecW) < \frac12\} \subset \cA_{\epsilon}$. Apply the standard construction of bump functions to the compact set $\{\vecW:\Phi(\vecW) \le 0\}$ contained in the open set $\{\vecW:\Phi(\vecW) < \frac12\}$ to obtain a function $\chi$ differentiable to all orders supported on $\{\vecW:\Phi(\vecW) < \frac12\}$ and identically 1 on $\{\vecW:\Phi(\vecW) \le 0\}$. Then $\Phi-B\chi$ is non-negative (recall $B<0$) and differentiable to all orders, and is identical to $\Phi$ on $\cA^c_{\epsilon}$. Taking $\Phi \leftarrow \Phi-B\chi$, this gives us the existence of $\Phi \ge 0$ differentiable to all orders where we have its explicit form and know it satisfies eq:geomconditionproof and therefore eq:poincaregeomcondition (upon dividing both sides by $\beta>0$) on $\cA^c_{\epsilon}$.

To conclude, note from our remarks from sec:setup that

\[ \tau'_{\cA_{\epsilon}}(\vecW') = \frac1{\beta} \tau_{\cA_{\epsilon}}(\vecW').\]

Therefore on $\cA_{\epsilon}^c$ we can also write

\[ \Phi(\vecW') = \mathbb{E}_{\vecW'}\brk*{\exp\prn*{\lambda \tau_{\cA_{\epsilon}}}} \ge 1.\]

This completes the proof.

Now we prove lem:measureoflargeF.

Suppose $F$ satisfies ass:holderF and $\mu_{\beta}$ has finite second moment $S<\infty$. Then for $\epsilon \ge \frac{2d}{\beta} \log(4\pi e \beta L d S)$, we have $\mu_{\beta}\prn*{\cA_{\epsilon}} \ge \frac12$.

As $F(\vecW)$ is non-negative, by Markov's Inequality, we have

\[ \mu_{\beta}\prn*{\cA_{\epsilon}^c}=\mu_{\beta}\prn*{\{\vecW:F(\vecW) > \epsilon\}} \le \frac{\mathbb{E}_{\vecW\sim\mu_{\beta}}\brk*{F(\vecW)}}{\epsilon}.\]

Now we compute $\mathbb{E}_{\vecW\sim\mu_{\beta}}\brk*{F(\vecW)}$ with the same strategy as in the proof of Proposition 11 of Raginsky et al., 2017. Write

\[ \mathbb{E}_{\vecW\sim\mu_{\beta}}\brk*{F(\vecW)} = \int_{\mathbb{R}^d} F(\vecW) \mu_{\beta}(\vecW)\DERIV \vecW = \frac1{\beta}\prn*{h(\mu_{\beta}) - \log Z}.\]

Here $Z$ is the partition function of $\mu_{\beta}$ and

\[ h(\mu_{\beta}) = -\int_{\mathbb{R}^d}\mu_{\beta}(\vecW)\log\mu_{\beta}(\vecW) \DERIV \vecW\]

is the differential entropy of $\mu_{\beta}$.

To upper bound the differential entropy of $\mu_{\beta}$, we use the same derivation as the proof of Proposition 11 of Raginsky et al., 2017. The assumption that $\int_{\mathbb{R}^d}\nrm*{\vecW}^2 \DERIV \mu_{\beta}(\vecW) \le S$, as well as the fact that the differential entropy of a measure with finite second moment is upper bounded by the differential entropy of a Gaussian with the same second moment, yields

\[ h(\mu_{\beta}) \le \frac{d}2 \log\prn*{\frac{2\pi e S}{d}}.\]

Now we aim to lower bound the partition function $Z$. Using lem:upperboundFholder and lem:extensionofgaussianintegral, we obtain

\begin{align*}
\log Z &= \log \int_{\mathbb{R}^d} e^{-\beta F(\vecW)} \DERIV \vecW \\
&\ge \log \int_{\mathbb{R}^d} e^{-\beta L \nrm*{\vecW-\vecW^{\star}}^{s+1}} \DERIV \vecW\\
&= \log \int_{\mathbb{R}^d} e^{-\beta L \nrm*{\vecW}^{s+1}} \DERIV \vecW \\
&= \log \prn*{\frac{2\pi^{d/2}}{\Gamma(d/2)} \cdot \frac1{s+1} \cdot \prn*{\beta L}^{-\frac{d}{s+1}}\cdot \Gamma\prn*{\frac{d}{s+1}}}.
\end{align*}

It is well known that on $\mathbb{R}_{>0}$, $\Gamma(\cdot)$ attains a constant lower bound of at least $\frac12$ (the real value is around 0.8856, but this is all we need for our purposes). Moreover, by well-known properties of $\Gamma(\cdot)$, we have $\Gamma(d/2) = \frac{d}{2} \cdot \frac{d-2}{2}\cdot \cdots\cdot \frac{d-2\lfloor d/2 \rfloor+r'+2}{2}\cdot \Gamma\prn*{\frac{d-2\lfloor d/2 \rfloor+r'}{2}}$, where $r' = 2\prn*{1-d\pmod{2}}$. Since $\frac{d-2\lfloor d/2 \rfloor+r'}{2}\in\{1/2,1\}$ and $\Gamma(1/2)=\sqrt{\pi}$, $\Gamma(1)\le 1$, this gives $\Gamma\prn*{\frac{d-2\lfloor d/2 \rfloor}{2}} \le d^{d/2} \sqrt{\pi}$. This implies (since $\beta L \ge 1$) the following very loose bound:

\begin{align*}
\log Z &\ge \log \prn*{\frac{2\pi^{d/2}}{\Gamma(d/2)} \cdot \frac1{s+1} \cdot \prn*{\beta L}^{-\frac{d}{s+1}}\cdot \Gamma\prn*{\frac{d}{s+1}}} \\
&\ge \log \prn*{\frac{\pi^{d/2}}{2\sqrt{\pi}\prn*{\beta L}^{d} d^{d/2}}} \\
&\ge -d\log\prn*{2\beta L d}.
\end{align*}

Hence, we see

\[ \mathbb{E}_{\vecW\sim\mu_{\beta}}\brk*{F(\vecW)} = \frac1{\beta}\prn*{h(\mu_{\beta}) - \log Z} \le \frac{d}{\beta}\prn*{\frac12\log\prn*{\frac{2\pi e S}{d}} + \log\prn*{2\beta L d}} \le \frac{d}{\beta} \log(4\pi e \beta L d S).\]

The conclusion follows from our condition on $\beta$ and the original application of Markov's Inequality.

Note it suffices to just take $\epsilon \ge 2\mathbb{E}_{\vecW\sim\mu_{\beta}}\brk*{F(\vecW)}$ to make this proof work; most of our work was to find a suitable upper bound for $\mathbb{E}_{\vecW\sim\mu_{\beta}}\brk*{F(\vecW)}$. Also, $\epsilon =\Omega\prn*{\mathbb{E}_{\vecW\sim\mu_{\beta}}\brk*{F(\vecW)}}$ is necessary, as demonstrated by the Gaussian example in subsec:ourcontributions.

§.§ Proof of thm:constructadmissablepotential

We derive the implication of a rate function $R(\vecW,t)$ satisfying the condition eq:ldrateineq to a geometric condition, which we described in sec:beyondpoincare. First we convert eq:ldrateineq into a more tractable condition about the rate function:

Assume $R$ has continuous second partials and that

\[ \mathbb{E}\brk*{\abs*{\tri*{R(\vecW,t), \nabla F(\vecW)}}}, \mathbb{E}\brk*{\abs*{\Delta R(\vecW(s),t)}} < \infty, \mathbb{P}\prn*{\int_0^{\infty} \nrm*{R(\vecW(\tau),t)}_2^2 \DERIV\tau<\infty}=1. \]

Then, we have that $R$ satisfying eq:ldrateineq implies the condition:

\[ \frac{\partial}{\partial t}R(\vecW,t) \ge -\langle \nabla R(\vecW,t), \nabla F(\vecW)\rangle+\frac1{\beta}\Delta R(\vecW,t) \FORALLTEXT \vecW\in\mathbb{R}^d, t \ge 0.\numberthis\label{eq:derivconditionadmissibile}\]

Note from $\mathbb{E}\brk*{R(\vecW(s),t)} \le R(\vecW,s+t) \FORALLTEXT s, t, \vecW = \vecW(0)$ we have

\[ \lim_{s\rightarrow 0} \frac{\mathbb{E}\brk*{R(\vecW(s),t)}-\mathbb{E}\brk*{R(\vecW(0),t)}}{s}\le \lim_{s\rightarrow 0}\frac{R(\vecW,s+t)-R(\vecW,t)}{s}= \frac{\partial}{\partial t}R(\vecW,t).\]

In the following we consider $t$ as a fixed constant. Note $\mathbb{E}\brk*{R(\vecW(\cdot),t)}$ is a deterministic function of the argument and so by definition of partial derivative

\[ \lim_{s\rightarrow 0} \frac{\mathbb{E}\brk*{R(\vecW(s),t)}-\mathbb{E}\brk*{R(\vecW(0),t)}}{s} = \frac{\partial}{\partial s} \mathbb{E}\brk*{R(\vecW(s),t)}\Big|_{s=0}.\]

Thus the above becomes

\[ \frac{\partial}{\partial s} \mathbb{E}\brk*{R(\vecW(s),t)}\Big|_{s=0} \le \frac{\partial}{\partial t}R(\vecW,t).\]

Now, recall Langevin Dynamics eq:LangevinSDE is given by the SDE

\[ \DERIV\vecW(s) = -\nabla F(\vecW(s)) \mathrm{d}s + \sqrt{2/\beta} \mathrm{d}\vecB(s),\]

where $\vecB(s)$ is the standard Brownian motion in $\mathbb{R}^d$ and $\beta$ is the inverse temperature parameter. This SDE is a compact way of writing

\[ \vecW(s) = \vecW(0)-\int_0^s \nabla F(\vecW(\tau)) \mathrm{d}\tau + \int_0^s \sqrt{2/\beta} \mathrm{d}\vecB(\tau).\]

The next step is to find the corresponding Itô process that describes $R(\vecW(s), t)$. By Itô's Lemma,

\[ \mathrm{d}R(\vecW(s), t) =\sum_{i=1}^d \prn*{\frac{\partial R}{\partial \vecW_i}(\vecW(s),t)} \mathrm{d}\vecW(s)_i + \frac12 \sum_{1 \le i,j\le d} \prn*{\frac{\partial^2 R}{\partial \vecW_i\partial \vecW_j}(\vecW(s),t)} \mathrm{d}\vecW(s)_i \mathrm{d}\vecW(s)_j.\]

Straightforward calculation and the fact that $(\DERIV \vecB(s))_i (\DERIV \vecB(s))_j = \delta_{i=j} \DERIV s$ gives

\begin{align*}
\DERIV \vecW(s)_i \DERIV \vecW(s)_j &= \prn*{-\nabla F(\vecW(s))_i \DERIV s + \sqrt{2/\beta} (\DERIV \vecB(s))_i}\prn*{-\nabla F(\vecW(s))_j \DERIV s + \sqrt{2/\beta} (\DERIV \vecB(s))_j}\\
&=\begin{cases} 0 &\IF i \neq j \\ \frac2{\beta} \DERIV s &\OTHERWISEIF i = j.\end{cases}
\end{align*}

Substituting this into the above we get

\begin{align*}
\DERIV R(\vecW(s),t) &= \tri*{\nabla R(\vecW(s),t), \DERIV \vecW(s)} + \frac12 \sum_{i=1}^d \prn*{\frac{\partial^2 R}{\partial \vecW_i^2}(\vecW(s),t)} \frac2{\beta} \DERIV s \\
&= \tri*{\nabla R(\vecW(s),t), \prn*{-\nabla F(\vecW(s)) \DERIV s+\sqrt{2/\beta} \DERIV \vecB(s)}} + \frac1{\beta} \Delta R(\vecW(s),t) \DERIV s \\
&= -\tri*{\nabla R(\vecW(s),t), \nabla F(\vecW(s))} + \frac1{\beta}\Delta R(\vecW(s),t) \DERIV s \\
&\hspace{1in}+ \sqrt{2/\beta} \tri*{\nabla R(\vecW(s),t), \DERIV \vecB(s)}.
\end{align*}

We can rewrite this as

\begin{align*}
R(\vecW(s),t) &= R(\vecW(0),t) + \int_0^s \prn*{-\tri*{\nabla R(\vecW(\tau),t), \nabla F(\vecW(\tau))} + \frac1{\beta}\Delta R(\vecW(\tau),t)} \DERIV \tau \\
&\hspace{1in}+ \int_0^s \sqrt{2/\beta} \tri*{\nabla R(\vecW(\tau),t), \DERIV \vecB(\tau)}.
\end{align*}

We aim to find an expression for $\mathbb{E}\brk*{R(\vecW(s)),t}$. Note by our conditions, considering Definition 3.1.4, Theorem 3.2.1 and Definition 3.3.2 together in Øksendal, 2003, we see that in fact we have

\[ \mathbb{E}\brk*{\int_0^s \sqrt{2/\beta} \tri*{\nabla R(\vecW(\tau),t), \DERIV\vecB(\tau)}} = 0 \FORALLTEXT s \ge 0.\]

Thus taking expectations gives

\[ \mathbb{E}\brk*{R(\vecW(s),t)} = R(\vecW(0),t)+\mathbb{E}\brk*{\int_0^s \prn*{-\tri*{\nabla R(\vecW(\tau),t), \nabla F(\vecW(\tau))} + \frac1{\beta}\Delta R(\vecW(\tau),t)} \DERIV\tau}. \]

Now we want to deal with this expectation. By Dominated Convergence, thanks to our assumptions, we can swap the order of expectation and integration. So we obtain

\[ \mathbb{E}\brk*{R(\vecW(s),t)} = R(\vecW(0),t)+\int_0^s\mathbb{E} \brk*{-\tri*{\nabla R(\vecW(\tau),t),\nabla F(\vecW(\tau))} + \frac1{\beta}\Delta R(\vecW(\tau),t)} \DERIV\tau. \]

Now applying Leibniz Rule gives

\[ \frac{\partial}{\partial s} \mathbb{E}\brk*{R(\vecW(s),t)} = \frac{\partial}{\partial s}(s) \cdot \mathbb{E}\brk*{-\tri*{\nabla R(\vecW(s),t),\nabla F(\vecW(s))} + \frac1{\beta}\Delta R(\vecW(s),t)}.\]

And thus our condition becomes

\begin{align*}
\frac{\partial}{\partial t}R(\vecW,t) &\ge \frac{\partial}{\partial s} \mathbb{E}\brk*{R(\vecW(s),t)} \Big|_{s=0}\\
&= \lim_{s\rightarrow 0}\mathbb{E}\brk*{-\tri*{\nabla R(\vecW(s),t),\nabla F(\vecW(s))} + \frac1{\beta}\Delta R(\vecW(s),t)} \\
&= -\langle \nabla R(\vecW,t), \nabla F(\vecW)\rangle+\frac1{\beta}\Delta R(\vecW,t).
\end{align*}

This last step is justified as follows. Our formula for $\frac{\partial}{\partial s} \mathbb{E}\brk*{R(\vecW(s),t)}$ holds for all $s > 0$, and our expression for $\mathbb{E}\brk*{R(\vecW(s),t)}$ is continuous in $s$. Recall our assumptions that $R$ has continuous second partials and

\[ \mathbb{E}\brk*{\abs*{\tri*{\nabla R(\vecW,t), \nabla F(\vecW)}}}, \mathbb{E}\brk*{\abs*{\Delta R(\vecW(s),t)}}< \infty.\]

Thus, Dominated Convergence Theorem may be used to swap the order of limit and expectation, so we may take the limit of both sides as $s \rightarrow 0^{+}$, yielding

\begin{align*}
\frac{\partial}{\partial t}R(\vecW,t) &\ge -\mathbb{E}[\tri*{\nabla R(\vecW,t), \nabla F(\vecW)}] + \frac1{\beta}\Delta R(\vecW,t)\\
&= -\langle \nabla R(\vecW,t), \nabla F(\vecW)\rangle+ \frac1{\beta}\Delta R(\vecW,t),
\end{align*}

where the expectation clearly drops since we took the limit.

To justify the application of Dominated Convergence in more detail, note $\vecW = \vecW(0)$ and $t$ here are both fixed and so for $s > 0$ small enough, we have

\[ \abs*{\tri*{\nabla R(\vecW(s),t),\nabla F(\vecW(s)}} \le \abs*{\tri*{\nabla R(\vecW,t), \nabla F(\vecW)}}+1,\]

by continuity of the gradients of $R(\vecW, t)$ and $F$. Now under the expectation with respect to the probability measure given by the Brownian motion up to time $s$ we get

\[ \mathbb{E}\brk*{\abs*{\tri*{\nabla R(\vecW(s),t), \nabla F(\vecW(s)}}}\le \mathbb{E}\brk*{\abs*{\tri*{\nabla R(\vecW,t), \nabla F(\vecW)}}}+1.\]

The same argument, since we have the appropriate conditions, can be used for $\Delta R$.

Recall that we claimed in sec:beyondpoincare that a rate function $R(\vecW, t)$ satisfying eq:ldrateineq implied $\Phi(\vecW)=\int_0^\infty R(\vecW,t) \DERIV t$ satisfies the definition of admissible potential eq:admissablepotentialF. Using lem:deriveadmissibleformal, we show this now.

Assuming the conditions

\[\mathbb{E}\brk*{\abs*{\tri*{\nabla R(\vecW,t), \nabla F(\vecW)}}} < \infty, \nrm*{\int_0^\infty \nabla R(\vecW,t) \DERIV t} < \infty,\int_0^\infty R(\vecW,t) \DERIV t < \infty \]

for all $\vecW$, and the assumption that $R(\vecW, t)$ and $F$ have continuous gradients. Then we know that

\[ \Phi(\vecW)=\int_0^\infty R(\vecW,t) \DERIV t\]

is an admissable potential if $R(\vecW,t)$ satisfies the relationship eq:derivconditionadmissibile given in lem:deriveadmissibleformal.

Rearrange the condition from lem:deriveadmissibleformal to read

\[ -\frac{\partial}{\partial t}R(\vecW,t) + \frac1{\beta}\Delta R(\vecW,t)\le \tri*{ \nabla R(\vecW,t), \nabla F(\vecW)}.\]

Next integrate both sides from $0 \le t < \infty$, yielding

\begin{align*}
\int_0^\infty \prn*{-\frac{\partial}{\partial t}R(\vecW,t) + \frac1{\beta}\Delta R(\vecW,t))} \DERIV t &\le \int_0^\infty \tri*{ \nabla R(\vecW,t), \nabla F(\vecW)} \DERIV t \\
&= \tri*{\int_0^\infty \nabla R(\vecW,t) \DERIV t, \nabla F(\vecW)} \\
&= \tri*{ \nabla \prn*{\int_0^\infty R(\vecW,t) \DERIV t}, \nabla F(\vecW)}.
\end{align*}

The last step follows as for all $1 \le i \le d$ we have again by Dominated Convergence Theorem that

\[ \frac{\partial}{\partial \vecW_i} \int_0^\infty R(\vecW,t) \DERIV t = \int_0^\infty \frac{\partial}{\partial \vecW_i} R(\vecW,t) \DERIV t,\]

by assumption that $\int_0^\infty R(\vecW,t) \DERIV t < \infty \FORALLTEXT \vecW$ (as $R$ is non-negative).

Next, observe that

\begin{align*}
\int_0^\infty \prn*{-\frac{\partial}{\partial t}R(\vecW,t) + \frac1{\beta}\Delta R(\vecW,t))} \DERIV t &= \int_0^\infty -\frac{\partial}{\partial t}R(\vecW,t)
\DERIV t + \frac{1}{\beta} \int_0^\infty \Delta R(\vecW,t) \DERIV t \\
&= R(\vecW,0) + \frac1{\beta}\int_0^\infty \Delta R(\vecW,t) \DERIV t \\
&\ge F_{\epsilon}(\vecW)+ \frac1{\beta}\int_0^\infty \Delta R(\vecW,t) \DERIV t,
\end{align*}

since $\lim_{t\rightarrow \infty} R(\vecW,t)=0$ and as $R(\vecW,0)\ge F_{\epsilon}(\vecW)$. To complete the proof, note by two applications of Dominated Convergence Theorem that

\[ \int_0^\infty \frac{\partial^2}{\partial \vecW_i^2} R(\vecW,t) \DERIV t = \frac{\partial}{\partial \vecW_i} \int_0^\infty \frac{\partial}{\partial \vecW_i} R(\vecW,t) \DERIV t
= \frac{\partial^2}{\partial \vecW_i^2} \int_0^\infty R(\vecW,t) \DERIV t,\]

by assumption that $\nrm{\int_0^\infty \nabla R(\vecW,t) \DERIV t} < \infty$ and $\int_0^\infty R(\vecW,t) \DERIV t < \infty \FORALLTEXT \vecW$ (as $R$ is non-negative). Therefore we have

\[\int_0^\infty \Delta R(\vecW,t) \DERIV t = \Delta \int_0^\infty R(\vecW,t)\DERIV t \]

and so by definition of the potential $\Phi$ we have

\[ \tri*{ \nabla \Phi(\vecW), \nabla F(\vecW)} \ge F_{\epsilon}(\vecW)+\frac1{\beta} \Delta \Phi(\vecW),\]

as wanted.

Recall in sec:beyondpoincare we stated eq:admissablepotentialF implies that the Langevin Diffusion succeeds as an optimization strategy for rate in expectation. Here we show this.

Suppose that we have

\[\mathbb{E}\brk*{\abs*{\tri*{\nabla \Phi(\vecW,t),\nabla F(\vecW)}}}, \mathbb{E}\brk*{\abs*{\Delta \Phi(\vecW,t)}} < \infty\]

for all $\vecW\in\mathbb{R}^d$, for an admissable potential $\Phi$ with respect to $F$. Then running Langevin Dynamics at temperature $\beta$ starting from $\vecW(0)$, we have that

\[ \frac1t \int_0^t \mathbb{E}\brk*{F_{\epsilon}(\vecW(s))} \DERIV s \le \frac{\Phi(\vecW(0))}{t}.\]

That is, if we uniformly choose a stopping time in $[0,t]$ we obtain a $O(t^{-1})$ rate.

Considering an arbitrary path of and then taking expectation with respect to the Brownian motion, the admissability condition eq:admissablepotentialF rearranges to

\[ \mathbb{E}\brk*{F_{\epsilon}(\vecW(s))} \le \mathbb{E}\brk*{\tri*{ \nabla\Phi(\vecW(s)), \nabla F(\vecW(s))} - \frac1{\beta}\Delta \Phi(\vecW(s))} \FORALLTEXT s \ge 0,\]

because we have such an inequality pointwise by definition of admissability.

By an analogous application of Itô's formula as the above in the proof of lem:deriveadmissibleformal, since our conditions allow us to apply Dominated Convergence Theorem, we can compute

\[ \frac{\DERIV}{\DERIV s} \mathbb{E}\brk*{\Phi(\vecW(s))}= \mathbb{E}\brk*{-\tri*{\nabla \Phi(\vecW(s)),\nabla F(\vecW(s))} +\frac{1}{\beta} \Delta \Phi(\vecW(s))},\]

and so the condition actually becomes

\[\mathbb{E}\brk*{F_{\epsilon}(\vecW(s))} \le -\frac{\DERIV}{\DERIV s}\mathbb{E}\brk*{\Phi(\vecW(s))}. \]

Integrating this from all $0 \le s \le t$ gives

\[ \int_0^t \mathbb{E}\brk*{F_{\epsilon}(\vecW(s))} \DERIV s \le -\int_0^t \frac{\DERIV }{\DERIV s} \mathbb{E}\brk*{\Phi(\vecW(s))} \DERIV s \le \mathbb{E}\brk*{\Phi(\vecW(0))} = \Phi(\vecW(0)).\]

Dividing by $t$ yields the result.

§ PROOFS FOR SEC:BEYONDPOINCARE

In this section we prove our results with constant probability guarantees; we can recover our results from sec:beyondpoincare easily via the standard log-boosting trick. Moreover, in this section, $\rho_{\Phi}(z)$ is defined in terms of $\rho_{\Phi,1}(z), \rho_{\Phi,2}(z), \rho_{\Phi,3}(z)$ as i lem:thirdordersmoothfromregularity (to be stated later in this section) for the general $p$ case.

§.§ Proof of thm:gradexactFeps

In the exact gradient oracle setting, we have the following result for optimization in discrete time. This is a formal statement of thm:gradexactFeps.

Consider $F$ and suppose $F$ is differentiable. Suppose that we have eq:admissablepotentialF:

\[ \tri*{ \nabla \Phi(\vecW), \nabla F(\vecW)} \ge F_{\epsilon}(\vecW)+\frac1{\beta} \Delta \Phi(\vecW),\]

for some $\beta>0$. Suppose ass:holderF, <ref>, and <ref> hold. Moreover suppose $\beta \ge d\sqrt{\frac{\log10}{C(\vecW_0)}}$ where $C(\cdot)$ is defined below.

Define the following quantities:

\[ A_0(\vecW_0) = \theta\prn*{\rho_{\Phi}^{-1}\prn*{\kappa' \rho_{\Phi}\prn*{\Phi(\vecW_0)}}}-\theta\prn*{\Phi(\vecW_0)} >0, A_1(\vecW_0) = 12\sqrt{2} CB_{\textsc{grad}}^3.\]

Here $C$ comes from lem:onesteprecursion and $B_{\textsc{grad}}:=L\prn*{R_1+\nrm*{\vecW^{\star}}}^s$, $L$ comes from ass:holderF and $R_1$ comes from ass:iteratesinballassumption. (If necessary take $C\leftarrow\max(C,1)$, and $B_{\textsc{grad}}\leftarrow\max(B_{\textsc{grad}},1)$.) Now define

\[ r(\vecW_0) = \min\prn*{1, \frac3{4C}, \frac1{B_{\textsc{grad}}}}, C(\vecW_0) = \min\prn*{1,\frac{A_0(\vecW_0)^2 r(\vecW_0)}{128A_1(\vecW_0)^2}}.\]

In terms of these define (where $\theta$ comes from lem:thirdordersmoothfromregularity),

\[M(\vecW_0) = \frac{10\max\prn*{\theta\prn*{\Phi(\vecW_0)}, 6C B_{\textsc{grad}}^3}}{\theta'\prn*{\rho_{\Phi}^{-1}\prn*{\kappa' \rho_{\Phi}\prn*{\Phi(\vecW_0)}}}} \in (0,\infty).\]

Discrete Time Gradient Langevin Dynamics with slight modifications

[1]
$\epsilon \le \min\prn*{1/e, C', \sqrt{\frac{C(\vecW_0)}{\log 10}}}$, where $C'$ is an absolute, dimension and temperature free constant given in lem:actuallypotentialsimplesetting:
Consider some constant choice of $\eta$, $T$ given in lem:actuallypotentialsimplesetting and run the following process with $\eta$ for $T$ steps:

\[ \vecW_{t+1} \leftarrow \vecW_t - \eta \nabla F(\vecW_t) + \sqrt{2\eta/\beta} \vecEps_t.\]

Here we sample $\vecEps_t \sim \sqrt{d}\cS^{d-1}$ uniformly (in spirit a Gaussian).
$\epsilon > \min\prn*{1/e, C', \sqrt{\frac{C(\vecW_0)}{\log 10}}}$:
Run this process with $\epsilon\leftarrow\min\prn*{1/e, C', \sqrt{\frac{C(\vecW_0)}{\log 10}}}$.

Now consider running alg:langevingradoracle. We claim it has the following guarantees. First, its runtime $T$ is as follows:

* If $\epsilon \le \min\prn*{1/e, C', \sqrt{\frac{C(\vecW_0)}{\log 10}}}$: then

\[ T \le \begin{cases} \frac{\beta^2}{d^2}&\IF \beta \le \frac{d}{\epsilon/\prn*{\log 1/\epsilon}^2} \\
\frac{1}{\epsilon^2}\prn*{\log 1/\epsilon}^2&\IF \beta \ge \frac{d}{\epsilon/\prn*{\log 1/\epsilon}^2}. \end{cases} \]

* If $\epsilon > \min\prn*{1/e, C', \sqrt{\frac{C(\vecW_0)}{\log 10}}}$: then we have the same runtime guarantee as implied by above with $\min\prn*{1/e, C', \sqrt{\frac{C(\vecW_0)}{\log 10}}}$ in place of $\epsilon$.

In terms of error, we have with probability at least 0.75 (taken over the $\{\epsilon_t\}_{0 \le t \le T-1}$) that

\begin{align*}
\frac1T \sum_{t=0}^{T-1}F_{\epsilon}(\vecW_t)\le \begin{cases} 6M(\vecW_0) \prn*{\frac{\log(20)+2\log(\beta/d)}{r(\vecW_0)C(\vecW_0)} + 1} \frac{d}{\beta} &\IF \beta \le \frac{d}{\epsilon/(\log 1/\epsilon)^2} \\
6M(\vecW_0) \prn*{\frac1{r(\vecW_0) C(\vecW_0)}+1}\epsilon &\IF \beta \ge \frac{d}{\epsilon/(\log 1/\epsilon)^2}. \end{cases}
\end{align*}

Here $C'$ is an absolute, dimension and temperature free constant given in lem:actuallypotentialsimplesetting.

Note now that logarithmic boosting tricks proves that a given one of these guarantees can occur with probability at least $1-\delta$ using at most $T \log(1/\delta)$ steps.

In our proofs of thm:gradexactFeps, <ref>, and <ref>, our results hold under the more general condition

\[ \tri*{\grad F(\vecW), \grad\Phi(\vecW)} -\frac1{\beta}\Delta F(\vecW) \ge A(\vecW),\]

for a general non-negative cost function $A(\vecW)$. Note $A(\vecW)$ need not be continuous (for example, $F_{\epsilon}(\vecW)$ is not continuous).

This lets us use the Lemmas we develop here, in the proofs of thm:poincareoptlipschitz, <ref>, and <ref>.

The proofs of this result is `optimization style'. We break it into parts. First we perform a one-step discretization bound in expectation by applying lem:thirdordersmoothfromregularity, which gives lem:onesteprecursion. Then we analyze a stochastic process naturally arising from this setup to show that $\Phi$ indeed is a potential function for the discrete-time algorithm, for appropriate choice of $\eta$ and $T$, which is detailed in lem:actuallypotentialsimplesetting. After this, we can conclude upon using the resulting bound and telescoping.

First, we need to show that with self-bounding regularity, by composing with the appropriate function, we can obtain some analogue of third-order smoothness in order to perform optimization-style discretization. We detail this as follows via the following Lemmas, which are also used later to prove thm:poincareoptformal.

Let $\Phi$ be any non-negative function that satisfies polynomial self-bounding regularity to first, second, and third orders[This implicitly assumes $\Phi$ is differentiable through third order.], that is we have $\nrm*{\nabla^i \Phi(\vecW)}_{\OPNORM} \le \rho_{\Phi,i}\prn*{\Phi(\vecW)}$ for $1 \le i \le 3$, where $\rho_{\Phi,i}(z)= \sum_{j=1}^{n_i} c_{i,j} z^{d_{i,j}}$ for all $z \ge 0$ (where all the $d_{i,j} \ge 0$). Then there exists some $\theta:\mathbb{R}_{\ge 0} \rightarrow\mathbb{R}_{\ge 0}$ such that $\theta'(z) > 0$, $\theta''(z)< 0$, $\theta'''(z) \ge 0$ for all $z \ge 0$, and

\[ \theta\prn*{\Phi(\vecW+\vecU)} \le \theta\prn*{\Phi(\vecW)}+\theta'\prn*{\Phi(\vecW)} \tri*{\nabla \Phi(\vecW), \vecU}+\frac12\theta'\prn*{\Phi(\vecW)}\tri*{ \nabla^2 \Phi(\vecW) \vecU, \vecU} + \frac{C}6 \nrm*{\vecU}^3,\]

for some constant $C$ that depends only on the form of the functions $\rho_1, \rho_2$, and $\rho_3$.

Moreover, we also have

\[ \theta\prn*{\Phi(\vecW+\vecU)} \le \theta\prn*{\Phi(\vecW)}+\theta'\prn*{\Phi(\vecW)} \tri*{ \nabla \Phi(\vecW), \vecU}+\frac12 \nrm*{\vecU}^2,\]

\[\nrm*{\nabla \Phi(\vecW)} \le \rho_{\Phi}\prn*{\Phi(\vecW)}\sqrt{2\theta\prn*{\Phi(\vecW)}}.\]

Note we can assume without loss of generality that all the $c_{i,j} \ge 0$, and thus again we can assume without loss of generality that for all $z \ge 0$ we have

\[ \max\prn*{\rho_{\Phi,1}(z), \rho_{\Phi,1}(z)^3,\rho_{\Phi,2}(z),\rho_{\Phi,3}(z), \rho_{\Phi,1}(z)\rho_{\Phi,2}(z)} \le A+Az^p \le 2A(z+1)^p\]

for some $A \ge 0, p \ge 0$. The last step follows from lem:upperboundpower.

Next, define $\rho_{\Phi}(z) := 2A(z+1)^p$, which is clearly non-negative and increasing. Thus for all $z \ge 0$ we have

\[ \rho_{\Phi}(z) \ge \max\prn*{\rho_{\Phi,1}(z), \rho_{\Phi,1}(z)^3,\rho_{\Phi,2}(z),\rho_{\Phi,3}(z), \rho_{\Phi,1}(z)\rho_{\Phi,2}(z)}.\]

Now let $\theta(z)$ be defined by $\theta'(z)=\frac1{\rho_{\Phi}(z)}$ and $\theta(0)=0$. The potential $\Phi$ we consider is non-negative and so we only consider $z \ge 0$; thus, $\theta$ is differentiable to all orders. Clearly $\theta'(z) > 0$. We can also check that $\theta''(z)=-\frac{p}{2A} (z+1)^{-p-1} < 0$, thus

\[ \abs*{\theta''(z)}\rho_{\Phi}(z) = \frac{p}{2A}(z+1)^{-p-1} \cdot
2A(z+1)^p \le p(z+1)^{-1} \le p.\]

for all $z \ge 0$. Finally, we can compute $\theta'''(z) = \frac{p(p+1)}{2A} (z+1)^{-p-2}$, thus

\[ \abs*{\theta'''(z)} \rho_{\Phi}(z) = \theta'''(z)\rho_{\Phi}(z) = \frac{p(p+1)}{2A}(z+1)^{-p-2} \cdot 2A(z+1)^p=\frac{p(p+1)}{(z+1)^2} \le p(p+1)\]

for all $z \ge 0$.

Now define for all $0 \le \alpha \le 1$,

\[l(\alpha) := \theta\prn*{\Phi(\vecW+\alpha \vecU)}.\]

Recall $\Phi$ is non-negative, so all the inputs here to $\theta$ are non-negative. $l(\alpha)$ is differentiable to third order, since $\Phi$ is and $\theta$ is for non-negative inputs.

By standard calculation using the Chain Rule (this is also done in the proof of Lemma 11 of [De Sa et al., 2022]),

\begin{align*}l'(\alpha) = \theta'\prn*{\Phi(\vecW + \alpha \vecU)} \tri*{ \nabla \Phi(\vecW + \alpha \vecU), \vecU}.\end{align*}

We also have, from similar calculation (also done in the proof of Lemma 11 of [De Sa et al., 2022]) and using that $\theta''(z) \le 0$ for all $z \ge 0$ which was established earlier,

\begin{align*}l''(\alpha) &= \theta''\prn*{\Phi(\vecW + \alpha \vecU)} \tri*{\grad \Phi(\vecW + \alpha \vecU), \vecU}^2+\theta'\prn*{\Phi(\vecW + \alpha \vecU)} \tri*{ \grad^2 \Phi(\vecW + \alpha \vecU) \vecU, \vecU} \\
&\le \theta'\prn*{\Phi(\vecW + \alpha \vecU)}\tri*{ \nabla^2 \Phi(\vecW + \alpha \vecU) \vecU, \vecU}.\end{align*}

Similar calculation, noting $\theta'(z) \ge 0$ and the bounds we established earlier on $\abs*{\theta''(z)}\rho_{\Phi}(z)$ and $\abs*{\theta'''(z)}\rho_{\Phi}(z)$, gives

\begin{align*}l'''(\alpha) &= \theta'''\prn*{\Phi(\vecW + \alpha \vecU)} \tri*{ \grad \Phi(\vecW + \alpha \vecU), \vecU}\cdot \tri*{ \grad \Phi(\vecW + \alpha \vecU), \vecU}^2 \\
&\hspace{1in}+ \theta''\prn*{\Phi(\vecW + \alpha \vecU)} \cdot 2\tri*{ \nabla \Phi(\vecW + \alpha \vecU), \vecU}\tri*{ \nabla^2 \Phi(\vecW + \alpha \vecU) \vecU, \vecU} \\
&\hspace{1in} + \theta''\prn*{\Phi(\vecW + \alpha \vecU)}\tri*{ \nabla \Phi(\vecW + \alpha \vecU), \vecU} \cdot \tri*{ \nabla^2 \Phi(\vecW + \alpha \vecU) \vecU, \vecU} \\
&\hspace{1in} + \theta'\prn*{\Phi(\vecW + \alpha \vecU)}\nabla^3 \Phi(\vecW + \alpha \vecU) [\vecU,\vecU,\vecU]\\
&=\theta'''\prn*{\Phi(\vecW + \alpha \vecU)} \tri*{ \grad \Phi(\vecW + \alpha \vecU), \vecU}^3\\
&\hspace{1in}+3\theta''\prn*{\Phi(\vecW + \alpha \vecU)}\tri*{ \nabla^2 \Phi(\vecW + \alpha \vecU) \vecU, \vecU} \tri*{ \nabla \Phi(\vecW + \alpha \vecU), \vecU}\\
& \hspace{1in} + \theta'\prn*{\Phi(\vecW + \alpha \vecU)}\nabla^3 \Phi(\vecW + \alpha \vecU) [\vecU,\vecU,\vecU] \\
&\le \abs*{\theta'''(\Phi(\vecW + \alpha \vecU))} \rho_{\Phi,1}(\Phi(\vecW + \alpha \vecU))^3 \nrm*{\vecU}^3 \\
&\hspace{1in}+ 3\abs*{\theta''(\Phi(\vecW + \alpha \vecU))} \rho_{\Phi,1}\prn*{\Phi(\vecW + \alpha \vecU)} \rho_{\Phi,2}\prn*{\Phi(\vecW + \alpha \vecU)} \nrm*{\vecU}^3\\
&\hspace{1in}+\theta'(\Phi(\vecW + \alpha \vecU)) \rho_{\Phi,3}(\Phi(\vecW + \alpha \vecU)) \nrm*{\vecU}^3 \\
&\le \rho_{\Phi}\prn*{\Phi(\vecW + \alpha \vecU)}\prn*{\abs*{\theta'''(\Phi(\vecW + \alpha \vecU))}+3\abs*{\theta''\prn*{\Phi(\vecW + \alpha \vecU)}}+\theta'\prn*{\Phi(\vecW + \alpha \vecU)}}\nrm*{\vecU}^3\\
&\le (p^2+p+3p+1) \nrm*{\vecU}^3.\end{align*}

From here, we consider Taylor expansion of $l(1)$ around $0$. By Taylor's formula for the remainder, we know for some $\alpha \in [0,1]$ that

\begin{align*}
l(1) &=l(0)+l'(0)+\frac12 l''(0)+\frac16 l'''(\alpha).
\end{align*}

Plugging in the above inequalities, we get

\[ \theta\prn*{\Phi(\vecW+\vecU)} \le \theta\prn*{\Phi(\vecW)}+\theta'\prn*{\Phi(\vecW)} \tri*{ \nabla \Phi(\vecW), \vecU}+\frac12\theta'\prn*{\Phi(\vecW)}\tri*{ \nabla^2 \Phi(\vecW) \vecU, \vecU} + \frac{p^2+4p+1}6 \nrm*{\vecU}^3.\]

The result follows since $C=p^2+4p+1$ only depends on the form of the functions $\rho_{\Phi,1}, \rho_{\Phi,2}$, and $\rho_{\Phi,3}$.

The second part follows from noticing that $\rho_{\Phi}$ as defined here is an upper bound on $\rho_{\Phi,1}$ and $\rho_{\Phi,2}$, so the same derivation as in the proof of Lemma 11 of De Sa et al., 2022 suffices.

Finally, if $\max_j \prn*{d_{i,j}} \le 1$ for all $1 \le i \le 3$ (i.e. the max degree of the self-bounding regularity functions is at most 1), we can be a bit tighter in how we define $\theta$. Instead we can just say

\[ \max\prn*{\rho_{\Phi,1}(z), \rho_{\Phi,1}(z),\rho_{\Phi,1}(z)} \le A+Az^p \le 2A(z+1)^p\]

where $0\le p\le 1$, and we define $\rho_{\Phi}(z)=A(z+1)^p$. Defining $\theta$ by $\theta'(z)=\frac1{\rho_{\Phi}(z)}$, $\theta(0)=0$ analogously as before, note we have for any $z \ge 0$ that

\[ \theta'(z) > 0, \theta''(z) < 0, \theta'''(z)>0,\]

\[ \abs*{\theta'''(z)}\rho_{\Phi,1}(z)^3 = \frac{p(p+1)}{A} (z+1)^{-p-2} \cdot 8A^3 (z+1)^{3p} =8A^2 p(p+1) (z+1)^{2p-2} \le 8A^2 p(p+1),\]

\[ \abs*{\theta''(z)} \rho_{\Phi,1}(z) \rho_{\Phi,2}(z) = \frac{p}{A} (z+1)^{-p-1} \cdot 4A^2 (z+1)^{2p}= 4Ap (z+1)^{p-1} \le 4Ap,\]

\[ \abs*{\theta'(z)} \rho_{\Phi,3}(z) = \frac{1}{A(z+1)^p} \cdot 2A(z+1)^p = 2.\]

The above three lines all use $p \le 1$ in the last inequality of those lines. Therefore, an analogous derivation as above gives

\begin{align*}
\theta\prn*{\Phi(\vecW+\vecU)} &\le \theta\prn*{\Phi(\vecW)}+\theta'\prn*{\Phi(\vecW)} \tri*{ \nabla \Phi(\vecW), \vecU}+\frac12\theta'\prn*{\Phi(\vecW)}\tri*{ \nabla^2 \Phi(\vecW) \vecU, \vecU} \\
&\hspace{1in}+ \frac{4A^2 p(p+1)+2Ap+1}3 \nrm*{\vecU}^3.
\end{align*}

For one iteration of starting at arbitrary $\vecW_t$,

\begin{align*}
\mathbb{E}_{\vecEps_t} \brk*{\theta\prn*{\Phi(\vecW_{t+1})}} &\le \theta\prn*{\Phi(\vecW_t)} - \eta  \theta'\prn*{\Phi(\vecW_t)} F_{\epsilon}(\vecW_t)\\
&\hspace{1in}+ \frac12 \eta^2 \nrm*{\nabla F(\vecW_t)}^2+\frac{2C}3 \eta^3\nrm*{\nabla F(\vecW_t)}^3 + 2C(\eta d/\beta)^{3/2},
\end{align*}

where $p$ and $C$ are defined from lem:thirdordersmoothfromregularity.

First, apply lem:thirdordersmoothfromregularity with $\vecW=\vecW_t$ and $\vecU = -\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t$ to obtain

\begin{align*}
\theta\prn*{\Phi(\vecW_{t+1})}
&= \theta\prn*{\Phi(\vecW_t-\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t)} \\
&\le\theta\prn*{\Phi(\vecW_t)}+ \theta'\prn*{\Phi(\vecW_t)}\tri*{ \nabla \Phi(\vecW_t),-\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t} \\
&+\frac12 \theta'\prn*{\Phi(\vecW_t)} \tri*{ \nabla^2 \Phi(\vecW_t) \prn*{-\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t}, -\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t } \\
&\hspace{1in}+\frac{C}6 \nrm*{-\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t}^3
\end{align*}

where $C$ is defined in the proof of lem:thirdordersmoothfromregularity.

We take expectations of this inequality with respect to $\vecEps_t$. Let's consider what each term of the upper bound becomes when we take expectations.

* First order term: Since $\vecEps_t$ has mean as the 0 vector,

\[ \mathbb{E}_{\vecEps_t}\brk*{\theta'\prn*{\Phi(\vecW_t)}\tri*{ \nabla \Phi(\vecW_t),-\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t}} =  -\eta \theta'\prn*{\Phi(\vecW_t)}\tri*{\grad \Phi(\vecW_t), \grad F(\vecW_t)}.\]

* Second order term: Note

\begin{align*}
&\mathbb{E}_{\vecEps_t} \brk*{\theta'\prn*{\Phi(\vecW_t)} \tri*{ \nabla^2 \Phi(\vecW_t) (-\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t), -\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t }}\\
&= \eta^2\theta'\prn*{\Phi(\vecW_t)} \tri*{\nabla^2 \Phi(\vecW_t) \nabla F(\vecW_t), \nabla F(\vecW_t)} \\
&\hspace{1in}- 2\eta \prn*{2\eta/\beta}^{1/2} \theta'\prn*{\Phi(\vecW_t)} \tri*{ \nabla^2 \Phi(\vecW_t) \nabla F(\vecW_t),\mathbb{E}_{\vecEps_t}\brk*{\vecEps_t}} \\
&\hspace{1in} + \prn*{2\eta/\beta} \theta'\prn*{\Phi(w_t)} \mathbb{E}_{\vecEps_t}\brk*{\tri*{\nabla^2\Phi(\vecW_t)\vecEps_t,\vecEps_t}}.
\end{align*}

In the above, the cross terms cancel because $\vecEps_t$ has mean of the 0 vector.

Now, consider $\mathbb{E}_{\vecEps_t}\brk*{\tri*{\nabla^2\Phi(\vecW_t)\vecEps_t,\vecEps_t}}$. We perform similar analysis as in the derivation and application of Ito's Lemma. This is where we see how the Laplacian term here actually helps. To make the parallels and motivation to Stochastic Calculus clear, here $\eta$ corresponds to $\DERIV t$, and $\sqrt{\eta} (\vecEps_t)_i$ corresponds to $(\DERIV \vecB_t)_i$. Note

\begin{align*}
\mathbb{E}_{\vecEps_t}\brk*{\tri*{\nabla^2\Phi(\vecW_t)\vecEps_t,\vecEps_t}} &= \sum_{1 \le i, j \le d} \mathbb{E}_{\vecEps_t}\brk*{(\vecEps_t)_i (\vecEps_t)_j \prn*{\nabla^2 \Phi(\vecW_t)}_{ij}} \\
&= \sum_{1 \le i, j \le d} \nabla^2 \Phi(\vecW_t)_{ij}\mathbb{E}_{\vecEps_t}\brk*{(\vecEps_t)_i (\vecEps_t)_j}.
\end{align*}

We break into cases:

* When $i \neq j$: Note by symmetry of the unit sphere that

\[ \mathbb{E}_{\vecEps_t}\brk*{(\vecEps_t)_i (\vecEps_t)_j}= 0.\]

In particular this follows because for any $\mathbf{x}\in\cS^{d-1}$, $(\vecEps_t)_j$ has equal probability of being $\mathbf{x}$ or $-\mathbf{x}$.

* When $i=j$: This is where we pick up the Laplacian. Note by symmetry,

\[\mathbb{E}_{\vecEps_t}\brk*{(\vecEps_t)^2_i}=\mathbb{E}_{\vecEps_t}\brk*{(\vecEps_t)^2_j} \FORALLTEXT i, j, \text{ and }d = \mathbb{E}_{\vecEps_t}[\sum_{i=1}^d (\vecEps_t)^2_i] =\sum_{i=1}^d \mathbb{E}_{\vecEps_t}\brk*{(\vecEps_t)^2_i}.\]

\[ \mathbb{E}_{\vecEps_t}\brk*{(\vecEps_t)^2_i}=1\FORALLTEXT 1 \le i \le d.\]

Hence, we obtain the Laplacian $\Delta \Phi(\vecW_t)$: we have plugging this into the above that

\[ \mathbb{E}_{\vecEps_t}\brk*{\tri*{\nabla^2\Phi(\vecW_t)\vecEps_t,\vecEps_t}} = \sum_{i=1}^d (\nabla^2 \Phi(\vecW_t))_{ii} = \Delta \Phi(\vecW_t).\]

\begin{align*}
&\mathbb{E}_{\vecEps_t} \brk*{\theta'\prn*{\Phi(\vecW_t)} \tri*{ \nabla^2 \Phi(\vecW_t) (-\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t), -\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t }}\\
&=\eta^2\theta'\prn*{\Phi(\vecW_t)} \tri*{\nabla^2 \Phi(\vecW_t) \nabla F(\vecW_t), \nabla F(\vecW_t)} + (2\eta/\beta) \theta'\prn*{\Phi(\vecW_t)} \Delta\Phi(\vecW_t).
\end{align*}

* Third order term: By AM-GM, we can prove for all $\mathbf{a},\mathbf{b}\in\mathbb{R}^d$,

\[ \nrm*{\mathbf{a}+\mathbf{b}}^3 \le \prn*{\nrm*{\mathbf{a}}+\nrm{\mathbf{b}}}^3 \le 4\nrm*{\mathbf{a}}^3+4\nrm{\mathbf{b}}^3.\]

Thus using this inequality pointwise we obtain

\begin{align*}
\mathbb{E}_{\vecEps_t}\brk*{\nrm*{-\eta \nabla F(\vecW_t)+\sqrt{2\eta/\beta} \vecEps_t}^3} &\le 4\eta^3 \nrm*{\nabla F(\vecW_t)}^3+4(2\eta/\beta)^{3/2} d^{3/2}.
\end{align*}

The last step is because deterministically $\nrm*{\vecEps_t}\le\sqrt{d}$ always.

Using the geometric property eq:admissablepotentialF and $\theta'\prn*{\Phi(\vecW_t)} \ge 0$ from lem:thirdordersmoothfromregularity,

\[ -\eta \theta'\prn*{\Phi(\vecW_t)}\tri*{\grad \Phi(\vecW_t), \grad F(\vecW_t)} \le -\eta \theta'\prn*{\Phi(\vecW_t)}\prn*{F_{\epsilon}(\vecW_t) + \frac1{\beta} \Delta \Phi(\vecW_t)}. \]

Putting these together, this gives

\begin{align*}
&\mathbb{E}_{\vecEps_t} \brk*{\theta\prn*{\Phi(\vecW_{t+1})}} \\
&\le \theta\prn*{\Phi(\vecW_t)} -\eta \theta'\prn*{\Phi(\vecW_t)}\tri*{ \nabla \Phi(\vecW_t),\nabla F(\vecW_t)}\\
&\hspace{1in}+\frac12\prn*{\eta^2\theta'\prn*{\Phi(\vecW_t)} \tri*{\nabla^2 \Phi(\vecW_t) \nabla F(\vecW_t), \nabla F(\vecW_t)} + (2\eta/\beta) \theta'\prn*{\Phi(\vecW_t)} \Delta\Phi(\vecW_t)} \\
&\hspace{1in}+\frac{C}6 (4\eta^3 \nrm*{\nabla F(\vecW_t)}^3+4(2\eta/\beta)^{3/2} d^{3/2})  \\
&\le \theta\prn*{\Phi(\vecW_t)} -\eta \theta'\prn*{\Phi(\vecW_t)}\prn*{F_{\epsilon}(\vecW_t) + \frac1{\beta} \Delta \Phi(\vecW_t)}\\
&\hspace{1in}+\frac12\prn*{\eta^2\theta'\prn*{\Phi(\vecW_t)} \tri*{\nabla^2 \Phi(\vecW_t) \nabla F(\vecW_t), \nabla F(\vecW_t)} + (2\eta/\beta) \theta'\prn*{\Phi(\vecW_t)} \Delta\Phi(\vecW_t)} \\
&\hspace{1in}+\frac{C}6 \prn*{4\eta^3 \nrm*{\nabla F(\vecW_t)}^3+4(2\eta/\beta)^{3/2} d^{3/2}}.
\end{align*}

Note the terms $\eta \theta'\prn*{\Phi(\vecW_t)} \cdot \frac1{\beta} \Delta \Phi(\vecW_t)$ and $\frac12 (2\eta/\beta) \theta'\prn*{\Phi(\vecW_t)}\Delta \Phi(\vecW_t)$ cancel out. Moreover, note by definition of operator norm and since we set $\theta'(z) = \frac1{\rho_{\Phi}(z)} \le \frac1{\rho_{\Phi,2}(z)}$, we obtain

\begin{align*}
\frac12 \eta^2\theta'\prn*{\Phi(\vecW_t)} \tri*{\nabla^2 \Phi(\vecW_t)\nabla F(\vecW_t), \nabla F(\vecW_t)} &\le \frac12 \eta^2\theta'\prn*{\Phi(\vecW_t)} \nrm*{\nabla F(\vecW_t)}^2 \rho_2\prn*{\Phi(\vecW_t)}\\
&\le \frac12 \eta^2\nrm*{\nabla F(\vecW_t)}^2.
\end{align*}

Thus our above bound becomes

\begin{align*}
\mathbb{E}_{\vecEps_t} \brk*{\theta\prn*{\Phi(\vecW_{t+1})}} &\le \theta\prn*{\Phi(\vecW_t)} - \eta  \theta'\prn*{\Phi(\vecW_t)} F_{\epsilon}(\vecW_t)\\
&\hspace{1in}+ \frac12 \eta^2 \nrm*{\nabla F(\vecW_t)}^2+\frac{2C}3 \eta^3\nrm*{\nabla F(\vecW_t)}^3 + 2C(\eta d/\beta)^{3/2}.
\end{align*}

This is the desired result.

The above result gives us a way to upper bound $\theta\prn*{\Phi(\vecW_t)}$. To control this we will need to control the $\Phi(\vecW_t)$ which we do as follows.

Suppose $\beta \ge d$ and $\epsilon \le 1/e$. Additionally suppose $\epsilon < C'$ where $z=\frac1{C'}$ is the largest solution to $\frac{\log(\sqrt{10}z(\log z))}{\log^2(z)}=1/2$ (the existence of finitely many such $C'>0$ is obvious).

With probability at least $0.9$, we have that

\[ \rho_{\Phi}\prn*{\Phi(\vecW_t)} \le \kappa' \rho_{\Phi}\prn*{\Phi(\vecW_0)}\]

for all $0 \le t \le T-1$ if $T, \eta$ are chosen as follows, where $\kappa'$ comes from ass:iteratesinballassumption. First define

\[ A_0(\vecW_0) = \theta\prn*{\rho_{\Phi}^{-1}\prn*{\kappa' \rho_{\Phi}\prn*{\Phi(\vecW_0)}}}-\theta\prn*{\Phi(\vecW_0)} >0, A_1(\vecW_0) = 12\sqrt{2} CB_{\textsc{grad}}^3.\]

Here $C$ comes from lem:onesteprecursion and $B_{\textsc{grad}}:=L\prn*{R_1+\nrm*{\vecW^{\star}}}^s$, $L$ comes from ass:holderF and $R_1$ comes from ass:iteratesinballassumption. (Again if necessary take $C\leftarrow\max(C,1)$ and $B_{\textsc{grad}}\leftarrow\max(B_{\textsc{grad}},1)$.)

Also define

\[ r(\vecW_0) = \min\prn*{1, \frac3{4C}, \frac1{B_{\textsc{grad}}}}, C(\vecW_0) = \min\prn*{1,\frac{A_0(\vecW_0)^2 r(\vecW_0)}{128A_1(\vecW_0)^2}}.\]

Now we choose $T, \eta$ based on cases:

* If $\beta \le \frac{d}{\epsilon/\prn*{\log 1/\epsilon}^2}$: Take $T, \eta$ such that

\[ \eta = r(\vecW_0) \frac{d}{\beta}\]

and where $T$ is the floor of the unique solution to the equation

\[ z \log (10z) = C(\vecW_0) \frac{\beta^2}{d^2}.\]

Existence and uniqueness to this equation is clear since $z \log(10z)$ is surjective on $\mathbb{R}_{\ge 0}$ and for every positive real $t$, exactly one positive real $z$ is such that $z \log (10z)=t$. Now note if $C(\vecW_0) \cdot \frac{\beta^2}{d^2} \ge 1$ then this means $T \le C(\vecW_0)\frac{\beta^2}{d^2} \le \frac{\beta^2}{d^2}$, and otherwise we have $T < 1 \implies T=0$. However, recall $\beta \ge d$ so in all cases we have $T \le \frac{\beta^2}{d^2}$.

Also note this means

\[ \eta \le \min\prn*{1, \frac3{4C}, \frac1{B_{\textsc{grad}}},  \frac{d}{\beta}}.\]

* If $\beta \ge \frac{d}{\epsilon/\prn*{\log 1/\epsilon}^2}$: Take $T, \eta$ such that

\[ \eta = r(\vecW_0)\frac{\epsilon}{\prn*{\log 1/\epsilon}^2}, T = \floor{ \frac{C(\vecW_0)}{\epsilon^2}\prn*{\log 1/\epsilon}^2 }.\]

Note this implies $T \le C(\vecW_0) \cdot \frac{1}{\epsilon^2}\prn*{\log 1/\epsilon}^2 \le \frac{1}{\epsilon^2}\prn*{\log 1/\epsilon}^2$.

Note as $\epsilon \le 1/e$, if $\beta \ge d\sqrt{\log (10)/C(\vecW_0)}$ and $\epsilon \le \sqrt{C(\vecW_0)}$, then $T \ge 1$.

Also note in all cases that $\eta \le \min(1, r(\vecW_0))$, since $\epsilon \le 1$, $\beta \ge d$.

Define $\mathfrak{F}_t$ by the natural filtration with respect to $\vecW_j, \vecEps_j$ for all $j \le t$. Let

\[ \tau := \min\{T, \inf\{t:\rho_{\Phi}\prn*{\Phi(\vecW_t)} > \kappa' \rho_{\Phi}\prn*{\Phi(\vecW_0)}\}\]

where $\kappa'$ comes from ass:iteratesinballassumption.

Define a stochastic process $Y_t$ by

\[ Y_t := \begin{cases}\theta\prn*{\Phi(\vecW_t)}+\sum_{j=0}^{t-1} \prn*{\eta F_{\epsilon}(\vecW_j) - R(\vecW_j, \Phi, \eta, \beta, d)}&\IF t \le \tau \\ Y_{\tau}&\OTHERWISEIF t > \tau \end{cases}\]

\[ R(\vecW_j, \Phi, \eta, \beta, d) := \frac12 \eta^2 \nrm*{\nabla F(\vecW_t)}^2+\frac{2C}3 \eta^3\nrm*{\nabla F(\vecW_t)}^3 + 2C(\eta d/\beta)^{3/2}.\]

We show properties of $Y_t$ in lem:Ytsupermartingalesimplesetting and lem:azumahoeffding for the sake of presentation. Together, these prove that with probability at $1-\delta$, we have