D.8. **Extension: the mean occupation measures.** We now state and prove analogue of Theorems 1–4 for the mean occupation measure $\mu_n$.

For this we will need a strengthened version of Assumption 3*, viz.

**Assumption 3**\*\* (Variant of Assumption 3\*). The signal-to-noise ratio of G satisfies

$$ \frac{\|\nabla f(x)\|^2}{\sigma_{\infty}^2(f(x))} \to \infty \quad \text{as} \quad \|x\| \to \infty. \qquad (4^{**}) $$

In this section, we will posit that Assumption 3\*\* holds in addition to Assumptions 1\*, 2\* and 4. We then have the following series of results for the occupation measure $\mu_n$ of (SGD).

**Theorem 1\*** (Occupation variant of Theorem 1). Fix a tolerance level $\varepsilon > 0$, and let $\mathcal{U}_i \equiv \mathcal{U}_i(\delta)$, $i = 1, \dots, K$, be $\delta$-neighborhoods of the components of crit $f$. Then, for all sufficiently small $\delta, \eta > 0$ and large enough $n$, we have

$$ |\eta \log \mu_n(\mathcal{U}_i) + E_i - \min_j E_j| \le \varepsilon \qquad (D.8.1) $$

and

$$ |\eta \log \frac{\mu_n(\mathcal{U}_i)}{\mu_n(\mathcal{U}_j)} + E_i - E_j| \le \varepsilon. \qquad (D.8.2) $$

More compactly, with notation as above, we have:

$$ \mu_n(\mathcal{U}_i) \propto \exp\left(-\frac{E_i + \mathcal{O}(\varepsilon)}{\eta}\right). \qquad (D.8.3) $$

**Theorem 2\*** (Occupation variant of Theorem 2). Let $\mathcal{K}$ be a non-minimizing component of $f$. Then, with notation as in Theorem 1, there exists a minimizing component $\mathcal{K}'$ of $f$ and a positive constant $c \equiv c(\mathcal{K}, \mathcal{K}') > 0$ such that

$$ \frac{\mu_n(\mathcal{U})}{\mu_n(\mathcal{U}')} \le \exp\left(-\frac{c(\mathcal{K}, \mathcal{K}') + \varepsilon}{\eta}\right) \qquad (D.8.4) $$

for all all sufficiently small $\eta > 0$, $n$ large enough and all sufficiently small neighborhoods $\mathcal{U}$ and $\mathcal{U}'$ of $\mathcal{K}$ and $\mathcal{K}'$ respectively.

**Theorem 3\*** (Occupation variant of Theorem 3). Fix a tolerance level $\delta > 0$, and let $\mathcal{U} \equiv \mathcal{U}(\delta)$ be a $\delta$-neighborhood of crit $f$. Then there exists a constant $c \equiv c_{\delta} > 0$ such that, for all sufficiently small $\eta > 0$ and large enough $n$, we have:

$$ \mu_n(\mathcal{U}) \ge 1 - e^{-c/\eta}. \qquad (D.8.5) $$

**Theorem 4\*** (Occupation variant of Theorem 4). Fix a tolerance level $\delta > 0$, and let $\mathcal{U}_0 \equiv \mathcal{U}_0(\delta)$ be a $\delta$-neighborhood of the system's ground state $\mathcal{K}_0$. Then there exists a constant $c \equiv c_{\delta} > 0$ such that, for all sufficiently small $\eta > 0$ and large enough $n$, we have:

$$ \mu_n(\mathcal{U}_0) \ge 1 - e^{-c/\eta}. \qquad (D.8.6) $$

We begin with a preliminary lemma which shows that, under Assumption 3\*\*, the sequence of mean occupation measure $(\mu_n)_{n \ge 0}$ is tight (see e.g., Kallenberg [32, Chap. 23]).

**Lemma D.34.** The sequence of mean occupation measures $(\mu_n)_{n \ge 0}$ is tight.

The proof of this lemma first follows the proof of Lemma D.16 and then relies on the same reasoning as the proof of Douc et al. [14, Thm. 12.3.3].
Proof. By Lemma D.14, there exists $\mathcal{K} \subset \mathcal{X}$ compact, $\eta_0 > 0$, $c > 0$ such that, for any $\eta \le \eta_0$, $x_0 = x \notin \mathcal{K}$,

$$ U_{\infty}(x_1) - U_{\infty}(x) \le \eta \left( \frac{\|\mathbf{U}(x, \omega_0)\|^2}{\sigma_{\infty}^2(f(x))} - \frac{\|\nabla f(x)\|^2}{\sigma_{\infty}^2(f(x))} \right). \quad (D.8.7) $$

Passing to the expectation yields that, for any $x \notin \mathcal{K}$,

$$ \mathbb{E}_x[U_{\infty}(x_1)] - U_{\infty}(x) \le \eta \left( \frac{\mathbb{E}_x[\|\mathbf{U}(x, \omega_0)\|^2]}{\sigma_{\infty}^2(f(x))} - \frac{\|\nabla f(x)\|^2}{\sigma_{\infty}^2(f(x))} \right). \quad (D.8.8) $$

Applying Corollary D.2 with $X \leftarrow \frac{\mathbb{U}(x, \omega_0)}{\sqrt{\sigma_{\infty}^2(f(x))}}$ (the conditions of application are verified from Assumption 2*(c)) yields that

$$ \mathbb{E}_x[U_{\infty}(x_1)] - U_{\infty}(x) \le -\eta \frac{\|\nabla f(x)\|^2}{\sigma_{\infty}^2(f(x))} + \eta \times 16d \log 6. \quad (D.8.9) $$

Hence, for any $x \in \mathcal{X}$, we have

$$ \mathbb{E}_x[U_{\infty}(x_1)] - U_{\infty}(x) \le 1\{x \in \mathcal{K}\} \left( \sup_{x' \in \mathcal{K}} \mathbb{E}_{x'}[U_{\infty}(x')] - \inf_{\mathcal{X}} U_{\infty} \right) \\ - 1\{x \notin \mathcal{K}\} \left( \eta \frac{\|\nabla f(x)\|^2}{\sigma_{\infty}^2(f(x))} - \eta \times 16d \log 6 \right), \quad (D.8.10) $$

or, after rearranging,

$$ \mathbb{E}_x[U_{\infty}(x_1)] - 1\{x \in \mathcal{K}\} \left( \sup_{x' \in \mathcal{K}} \mathbb{E}_{x'}[U_{\infty}(x')] - \inf_{\mathcal{X}} U_{\infty} \right) \\ + 1\{x \notin \mathcal{K}\} \left( \eta \frac{\|\nabla f(x)\|^2}{\sigma_{\infty}^2(f(x))} - \eta \times 16d \log 6 \right) \le U_{\infty}(x). \quad (D.8.11) $$

Since the function

$$ x \mapsto -1\{x \in \mathcal{K}\} \left( \sup_{x' \in \mathcal{K}} \mathbb{E}_{x'}[U_{\infty}(x')] - \inf_{\mathcal{X}} U_{\infty} \right) \\ + 1\{x \notin \mathcal{K}\} \left( \eta \frac{\|\nabla f(x)\|^2}{\sigma_{\infty}^2(f(x))} - \eta \times 16d \log 6 \right) \quad (D.8.12) $$

is measurable, lower-bounded and goes to infinity as $\|x\| \to \infty$ by Assumption 3**, one can then apply the same computations as in the proof of Douc et al. [14, Thm. 12.3.3] to obtain that the sequence of occupation measures $(\mu_n)_{n \ge 0}$ is tight. ■

We now prove Theorem 1* by adapting the proof of Theorem 1. Since the process is exactly the same for Theorems 2*-4*, we omit their proofs.

*Proof of Theorem 1*\*. We show that, for sufficiently small $\delta, \eta > 0$, for any $i \in I$, we have that

$$ \exp\left(-\frac{E_i - \min_j E_j + \varepsilon}{\eta}\right) \le \liminf_{n \to \infty} \mu_n(\mathcal{U}_i) \\ \le \limsup_{n \to \infty} \mu_n(\mathcal{U}_i) \\ \le \exp\left(-\frac{E_i - \min_j E_j - \varepsilon}{\eta}\right) \quad (D.8.13) $$

and the results in the statement will follow with $2\varepsilon$ in place of $\varepsilon$.

We apply Proposition D.4 (Appendix D.5): take $\delta$ small enough so Proposition D.4 can be applied with both the neighborhoods $\mathcal{U}_1, \dots, \mathcal{U}_K$ and $\mathrm{cl}\,\mathcal{U}_1, \dots, \mathrm{cl}\,\mathcal{U}_K$. One then obtain
$\eta_0 > 0$ such that, for all $0 < \eta < \eta_0$ and any $\mu_\infty$ invariant probability measure for $(x_n^\eta)_n$, for any $i \in I$,

$$ \mu_\infty(\mathcal{U}_i) \ge \exp\left(-\frac{E(\mathcal{K}_i) - \min_{j \in I} E(\mathcal{K}_j)}{\eta} - \frac{\varepsilon}{\eta}\right) \qquad (D.8.14) \\ \mu_\infty(\mathrm{cl}\,\mathcal{U}_i) \le \exp\left(-\frac{E(\mathcal{K}_i) - \min_{j \in I} E(\mathcal{K}_j)}{\eta} + \frac{\varepsilon}{\eta}\right). $$

We now prove that Eq. (D.8.13) holds. Fix $i \in I$. By Lemma D.34, the sequence of mean occupation measures $(\mu_n)_{n \ge 0}$ is tight, so that, by Prohorov theorem [32, Thm. 23.2], it is sequentially compact for the weak topology, or, in other terms, for the convergence in distribution. Therefore, $(\mu_n)_{n \ge 0}$ admits a weak accumulation point which is a probability distribution and that we denote by $\nu$. Applying Portmanteau theorem [32, Thm. 5.25] to the open set $\mathcal{U}_i$ and the closed set $\mathrm{cl}\,\mathcal{U}_i$ yields that

$$ \nu(\mathcal{U}_i) \le \liminf_{n \to \infty} \mu_n(\mathcal{U}_i) \le \limsup_{n \to \infty} \mu_n(\mathrm{cl}\,\mathcal{U}_i) \le \nu(\mathrm{cl}\,\mathcal{U}_i). \qquad (D.8.15) $$

Since $(x_n)_{n \ge 0}$, the sequence of iterates of SGD, is (weak) Feller by Lemma D.15, $\nu$ is actually invariant for $(x_n)_{n \ge 0}$, by, e.g., Douc et al. [14, Prop. 12.3.1], and a fortiori invariant for the accelerated process $(x_n^\eta)_{n \ge 0}$. Combining Eq. (D.8.14) with Eq. (D.8.15) gives the result Eq. (D.8.13). ■

## APPENDIX E. POTENTIAL FOR THE INVARIANT MEASURE

### E.1. Gaussian noise.
Though it does not formally fit into our setting, let us first begin with the case where the noise is Gaussian. Since it is unbounded, our assumptions are not satisfied and our theorems describing the invariant measure do not apply. However, all the objects we consider are still well-defined, and, in that case, it is possible to compute the $E_i$ explicitly. Moreover, this section serves as a blueprint for the truncated Gaussian case of the next section.

Assume that, for every $x \in \mathcal{X}$, $U(x, \omega)$ follows a centered Gaussian distribution with covariance $\sigma^2(f(x))I$ for some continuous function $\sigma^2: \mathbb{R} \to (0, +\infty)$.

Akin to $U_\infty$ in Appendix D, a key role is played by the function $U: \mathcal{X} \to \mathbb{R}$ defined by

$$ U(x) := 2\alpha(f(x)) \quad \text{with} \quad \alpha: \mathbb{R} \to \mathbb{R} \quad \text{a primitive of} \quad 1/\sigma^2. \qquad (\text{E.1.1}) $$

Since the noise is Gaussian, the Lagrangian and Hamiltonian have explicit expressions: for every $x, p, v \in \mathcal{X}$,

$$ \mathcal{H}(x, p) = -\langle \nabla f(x), p \rangle + \frac{1}{2} \sigma^2(f(x)) \|p\|^2 \qquad (\text{E.1.2a}) $$

$$ \mathcal{L}(x, v) = \frac{\|v + \nabla f(x)\|}{2\sigma^2(f(x))}. \qquad (\text{E.1.2b}) $$

This expression of $\mathcal{L}$ make it clear that the action function penalizes the deviation of a path from the flow: for a path $\gamma \in \mathcal{C}([0, T])$ for some $T > 0$,

$$ S_T(\gamma) = \int_0^T \frac{\|\dot{\gamma}_t + \nabla f(\gamma_t)\|^2}{2\sigma^2(f(\gamma_t))} dt. \qquad (\text{E.1.3}) $$

The computation of the $E_i$ relies on the following observation. Take a path $\gamma \in \mathcal{C}([0, T])$ for some $T > 0$ and consider $\varphi$ defined by $\varphi_t = \gamma_{T-t}$ for $t \in [0, T]$. Then, the action cost of $\varphi$ is given by,

$$ S_T(\varphi) = \int_0^T \frac{\| -\dot{\gamma}_t + \nabla f(\gamma_t) \|^2}{2\sigma^2(f(\gamma_t))} dt $$
$$ 
\begin{aligned}
&= \int_0^T \frac{\|\dot{\gamma}_t + \nabla f(\gamma_t)\|^2}{2\sigma^2(f(\gamma_t))} dt - \int_0^T \frac{2\langle \dot{\gamma}_t, \nabla f(\gamma_t) \rangle}{\sigma^2(f(\gamma_t))} dt \\
&= S_T(\gamma) - \int_0^T \langle \dot{\gamma}_t, \nabla U(\gamma_t) \rangle dt,
\end{aligned} 
\quad (E.1.4) $$

since $\nabla U(x) = 2\nabla\alpha(f(x))\nabla f(x)$. Therefore, we get that

$$ S_T(\varphi) = S_T(\gamma) - (U(\gamma_T) - U(\gamma_0)). \quad (E.1.5) $$

Take $i, j \in I$. This equality then translates to a relation between $B_{i,j}$ and $B_{j,i}$: considering $\gamma \in C([0, T])$ such that $\gamma_0 \in K_i$, $\gamma_T \in K_j$ and taking the infimum over all such paths, we get that

$$ B_{j,i} \le B_{i,j} + (U_j - U_i). \quad (E.1.6) $$

where, since $f$ is constant on $K_i$ and $K_j$, we denote by $U_i$ and $U_j$ the values of $U$ on $K_i$ and $K_j$ respectively.

Reversing the roles of $i$ and $j$ and applying the same argument shows that this inequality is an equality:

$$ B_{j,i} + U_j = B_{i,j} + U_i. \quad (E.1.7) $$

Denote by $C_{i,j}$ this common value. Crucially, $C_{i,j}$ is symmetric in $i$ and $j$.

Consider now $T^*$ a minimum weight spanning tree on the complete but now undirected graph on $I$ with weights $(C_{i,j})_{i,j}$. We show that the minima in the $E_i$ are attained $T^*$, or more precisely, a directed version of it.

Fix $i$ and consider $T \in \mathcal{T}_i$ a spanning tree rooted at $i$. We have that, since any node $j$ is the origin of exactly one edge in $T$,

$$ 
\begin{aligned}
\sum_{(j \to l) \in T} B_{j,l} + \sum_{j \in I} U_j &= \sum_{(j \to l) \in T} (B_{j,l} + U_j) + U_i \\
&= \sum_{(j \to l) \in T} C_{j,l} + U_i.
\end{aligned} 
\quad (E.1.8) $$

But by definition of $T^*$, this sum is at least greater than $\sum_{(j \leftrightarrow l) \in T^*} C_{j,l}$ so that we have

$$ \sum_{(j \to l) \in T} B_{j,l} + \sum_{j \in I} U_j \ge \sum_{(j \leftrightarrow l) \in T^*} C_{j,l} + U_i, \quad (E.1.9) $$

and taking $T_i$ an oriented version of $T^*$ rooted at $i$, the equality is attained. Therefore, we have that

$$ E_i = \sum_{(j \to l) \in T_i} B_{j,l} - \sum_{j \in I} U_j + U_i, \quad (E.1.10) $$

or, in short, $E_i = U_i + c$ where $c > 0$ is independent of $i$.

Therefore, the mass distribution over critical points is governed by a Gibbs measure with potential $U$.

Let us now mention two particular cases.

* If $\sigma^2$ is constant, then $U = \frac{2f}{\sigma^2}$.

* It $\sigma^2$ is linear, i.e., of the form $\sigma^2(f(x)) = \sigma_1^2(f(x) + \sigma_0^2)$, then $U = \frac{2}{\sigma_1^2} \log(f + \sigma_0^2)$.

E.2. **Truncated Gaussian noise.** To fit into our theoretical framework, we consider truncated Gaussian noise instead. The general outline of the proof but with added steps to handle the error due to the truncation. In particular, one must show that, without loss of generality, we can only consider paths whose derivative has the same norm as the gradient of $f$. This is done with Freidlin & Wentzell [20, Chap. 4, Lem. 3.1] that we adapt to our setting.
Assume that $U(x, \omega)$ follows a centered Gaussian distribution with covariance $\sigma^2(f(x))I$ conditioned on being in $\mathbb{B}(0, R(x))$ for some $R(x) > 0$.

As in Definition 4, we define $U(x) = 2\alpha(f(x))$ with $\alpha' = \frac{1}{\sigma^2}$ and denote by $U_i$ the value taken by $U$ on $K_i$.

Consider some $0 < \delta \le \frac{1}{2}$ and assume that

$$ \sup_{x \in \mathcal{X}} 2^{d+4}(d+1)e^{-\frac{R^2}{16\sigma^2}} \le \delta, \qquad (\text{E.2.1}) $$

so that the error term $2E(\sigma^2(f(x)), R(x))$ in Lemma F.2 is bounded by $\delta$.

Moreover, assume that, for any $x \in \mathcal{X}$

$$ \|\nabla f(x)\| \le \frac{R(x)}{8} \qquad (\text{E.2.2}) $$

**Lemma E.1.** Consider $\gamma \in \mathcal{C}([0, T])$. Then, there exists $\tilde{\gamma} \in \mathcal{C}([0, S])$ a reparametrization of $\gamma$ such that, for any $t \in [0, S]$,

$$ \|\dot{\tilde{\gamma}}_s\| = \|\nabla f(\tilde{\gamma}_s)\|. \qquad (\text{E.2.3}) $$

and

$$ S_T(\gamma) \ge \int_0^S \frac{\|\dot{\tilde{\gamma}}_s + \nabla f(\tilde{\gamma}_s)\|^2}{2(1+\delta)\sigma^2(f(\tilde{\gamma}_s))} ds. \qquad (\text{E.2.4}) $$

*Proof.* By the proof Freidlin & Wentzell [20, Chap. 4, Lem. 3.1], there exists $t(s)$ change of time such that, with $\tilde{\gamma}_s = \gamma_{t(s)}$, $\|\dot{\tilde{\gamma}}_s\| = \|\nabla f(\tilde{\gamma}_s)\|$.

We have that

$$ S_T(\gamma) = \int_0^{t^{-1}(T)} \dot{t}(s) \mathcal{L}(\tilde{\gamma}_s, (\dot{t}(s))^{-1} \dot{\tilde{\gamma}}_s) ds, \qquad (\text{E.2.5}) $$

so it suffices to bound $\mathcal{L}(\tilde{\gamma}_s, \dot{\tilde{\gamma}}_s)$ from below: by definition, we have

$$ \begin{aligned} \mathcal{L}(\tilde{\gamma}_s, (\dot{t}(s))^{-1}\dot{\tilde{\gamma}}_s) &\ge \sup \left\{ \langle p, (\dot{t}(s))^{-1}\dot{\tilde{\gamma}}_t + \nabla f(\tilde{\gamma}_s) \rangle - \bar{\mathcal{H}}(\tilde{\gamma}_s, p) : \|p\| \le \frac{R(\tilde{\gamma}_s)}{2\sigma^2(f(\tilde{\gamma}_s))} \right\} \\ &\ge \sup \left\{ \langle p, (\dot{t}(s))^{-1}\dot{\tilde{\gamma}}_t + \nabla f(\tilde{\gamma}_s) \rangle - (1+\delta)\frac{\sigma^2(f(\tilde{\gamma}_s))}{2} \|p\|^2 : \|p\| \le \frac{R(\tilde{\gamma}_s)}{2\sigma^2(f(\tilde{\gamma}_s))} \right\}, \end{aligned} \qquad (\text{E.2.6}) $$

by Lemma F.2. Applying Lemma F.3 with $\lambda \leftarrow \dot{t}(s)$, now exactly yields, for almost all $s$,

$$ \begin{aligned} \mathcal{L}(\tilde{\gamma}_s, (\dot{t}(s))^{-1}\dot{\tilde{\gamma}}_s) &\ge \dot{t}(s) \sup \left\{ \langle p, \dot{\tilde{\gamma}}_t + \nabla f(\tilde{\gamma}_s) \rangle - (1+\delta) \frac{\sigma^2(f(\tilde{\gamma}_s))}{2} \|p\|^2 : \|p\| \le \frac{R(\tilde{\gamma}_s)}{2\sigma^2(f(\tilde{\gamma}_s))} \right\} \\ &= \dot{t}(s) \frac{\|\dot{\tilde{\gamma}}_s + \nabla f(\tilde{\gamma}_s)\|^2}{2(1+\delta)\sigma^2(f(\tilde{\gamma}_s))}, \end{aligned} \qquad (\text{E.2.7}) $$

$$ \text{since } \|\dot{\tilde{\gamma}}_s + \nabla f(\tilde{\gamma}_s)\| \le \frac{R(\tilde{\gamma}_s)}{2}. \qquad \blacksquare $$

**Lemma E.2.** With this setting, for any $i \in I$

$$ E_i = U_i + \sum_{(j \to l) \in T_i} B_{j,l} - \sum_{j \in I} U_j + \mathcal{O}(\delta) \qquad (\text{E.2.8}) $$

*Proof.* Consider $\gamma \in \mathcal{C}([0, T])$ such that $\gamma_0 \in K_i$, $\gamma_T \in K_j$ and $S_T(\gamma) < +\infty$. Then, by the previous lemma Lemma E.1, there exists $\tilde{\gamma} \in \mathcal{C}([0, S])$ a reparametrization of $\gamma$ such that, for any $t \in [0, S]$,

$$ S_T(\gamma) \ge \int_0^S \frac{\|\dot{\tilde{\gamma}}_s + \nabla f(\tilde{\gamma}_s)\|^2}{2(1+\delta)\sigma^2(f(\tilde{\gamma}_s))} ds $$
$$ = \int_{0}^{S} \frac{\| -\dot{\tilde{\gamma}}_{s} + \nabla f(\tilde{\gamma}_{s}) \|^2}{2(1 + \delta)\sigma^2(f(\tilde{\gamma}_{s}))} ds + \frac{U(\gamma_{T}) - U(\gamma_{0})}{1 + \delta}, \qquad (E.2.9) $$

where we performed the same computations as above in Appendix E.1. Considering the path $(\tilde{\gamma}_{S-s})_{s \in [0, S]}$ and invoking the upper-bound on the Lagrangian from Lemma F.2 with $-\dot{\tilde{\gamma}}_s + \nabla f(\tilde{\gamma}_s)$ which still has norm less than $R(\tilde{\gamma}_s)/4$, we get that

$$ S_T(\gamma) \geq \frac{1 - \delta}{1 + \delta} B_{j,i} + \frac{U(\gamma_T) - U(\gamma_0)}{1 + \delta}. \qquad (E.2.10) $$

The result now follows from the same computations as in Appendix E.1. ■

**E.3. Local dependencies.** Under local assumptions similar to Mori et al. [56], we demonstrate how the modelling of the noise influences the invariant measure.

**Lemma E.3.** Consider $K_i$ minimizing, $\sigma^2: \mathbb{R} \to (0, +\infty)$ continuous, and take $\alpha: \mathbb{R} \to \mathbb{R}$ such that $\alpha' = \frac{1}{\sigma^2}$. Assume that $H^*$ is a positive definite matrix such that, locally near $K_i$, it holds that:

$$ \alpha(f(x)) = \sum_{\lambda \in \text{eig } H^*} g^{\lambda}(x_{\lambda}), \qquad (E.3.1) $$

where $x_\lambda$ denotes the orthogonal projection of $x$ on the eigenspace of the eigenvalue $\lambda$ and where $g^\lambda: \mathcal{X} \to \mathbb{R}$ is continuously differentiable. Define the potential $U: \mathcal{X} \to \mathbb{R}$ by

$$ U(x) = \sum_{\lambda \in \text{eig } H^*} \frac{2g^{\lambda}(x_{\lambda})}{\lambda}. \qquad (E.3.2) $$

If we have the anistropic subGaussian bound: for $x$ in a neighborhood of $K_i$, $p \in \bar{\mathbb{B}}(0, \|U(x)\|)$,

$$ \bar{H}(x, p) \leq \frac{\sigma^2(f(x))}{2} \langle p, H^*p \rangle, \qquad (E.3.3) $$

then there is $\delta > 0$ such that, for all $j \neq i$, any $0 < \delta' \leq \delta$,

$$ E_j \geq \min\{U(x) - U_i : x, d(x, K_i) = \delta'\} > 0, \qquad (E.3.4) $$

where $U_i$ is the value of $U$ on $K_i$.

Moreover, there exists $R > \delta$ such that, if there exists $c > 0$, $s^2 > 0$, such that, for all $x \in \bar{\mathbb{B}}(0, R) \setminus U_\delta(K_i)$, $v \in \bar{\mathbb{B}}(\nabla f(x), c)$,

$$ \bar{\mathcal{L}}(x, v) \leq \frac{\|v\|}{2s^2}, \qquad (E.3.5) $$

then there exists $C > 0$ that depends only on $r, R, c$, $f$ restricted to $\mathcal{X} \setminus U_r(K_i)$ such that

$$ E_i \leq \frac{C}{s^2}. \qquad (E.3.6) $$

The assumptions on the Hamiltonian and the Lagrangian roughly say that the noise share some similarities with Gaussian distributions with the prescribed variances. In particular, they are satisfied in the (truncated) Gaussian case, as shown in Lemma F.2.

Moreover, a takeaway of this lemma is that, if $\sigma^2$ or the eigenvalues of $H^*$ are small enough, then $K_i$ must be the ground state even if it may not be the global minimum of $U$. This lemma is general enough to handle non-constant variance: a notable example is when $\sigma^2(f(x))$ is linear in $f(x)$ and where the resulting potential $U$ then depends logarithmically on the value $f$.
Proof. Denote $P_{\lambda} \in \mathbb{R}^{d \times d}$ the orthogonal projection on the eigenspace of $H^*$ associated with the eigenvalue $\lambda$. U can thus be rewritten as

$$U(x) = \sum_{\lambda \in \text{eig } H^*} \frac{2g^{\lambda}(P_{\lambda}x)}{\lambda}, \qquad (\text{E.3.7})$$

so that its gradient is given by

$$\nabla U(x) = \sum_{\lambda \in \text{eig } H^*} \frac{2P_{\lambda}\nabla g^{\lambda}(P_{\lambda}x)}{\lambda}. \qquad (\text{E.3.8})$$

In particular, we obtain that for $x$ close enough to $K_i$, using the orthogonality of the projections,

$$\begin{aligned}
\bar{H}(x, \nabla U(x)) &\le \frac{\sigma^2(f(x))}{2} \langle \nabla U(x), H^* \nabla U(x) \rangle \\
&= \frac{\sigma^2(f(x))}{2} \sum_{\lambda \in \text{eig } H^*} \frac{4 \| P_{\lambda} \nabla g^{\lambda}(P_{\lambda}x) \|^2}{\lambda} \\
&= \frac{\sigma^2(f(x))}{2} \langle \nabla U(x), 2 \nabla(\alpha \circ f)(x) \rangle \\
&= \langle \nabla U(x), \nabla f(x) \rangle.
\end{aligned} \qquad (\text{E.3.9})$$

Therefore, for $x$ close enough to $K_i$, we have that

$$\mathcal{H}(x, \nabla U(x)) = -\langle \nabla U(x), \nabla f(x) \rangle + \bar{H}(x, \nabla U(x)) \le 0. \qquad (\text{E.3.10})$$

For $x$ close to $K_i$, let us compute $\langle \nabla U(x), \nabla f(x) \rangle$:

$$\begin{aligned}
\langle \nabla U(x), \nabla f(x) \rangle &= \sigma^2(f(x)) \langle \nabla U(x), \nabla(\alpha \circ f)(x) \rangle \\
&= \sigma^2(f(x)) \sum_{\lambda \in \text{eig } H^*} \frac{2 \| P_{\lambda} \nabla g^{\lambda}(P_{\lambda}x) \|}{\lambda},
\end{aligned} \qquad (\text{E.3.11})$$

which is (stricly) positive in a small neighborhood of $K_i$ (excluding $K_i$ itself). Therefore, $U$ is decreasing on trajectories of the flow in this neighborhood. With the same proof as in Lemma D.29, we deduce that there exists $\delta > 0$ such that $\arg\min_{x \in U_{\delta}(K_i)} U(x) = K_i$. Moreover, take $\delta > 0$ small enough such that Eq. (E.3.10) holds on $U_{\delta}(K_i)$, $U_{\delta}(K_i) \cap \text{crit } f = K_i$ and the trajectories of the flow started in $U_{\delta}(K_i)$ stay converge to $K_i$. We now proceed as in the proof of Lemma D.33. Take $\delta' \le \delta/2$, $\mathcal{U} := U'_{\delta}(K_i)$ and $\Delta := \min\{U(x) - U_i : x \in \mathcal{X}, d(x, K_i) = \delta'\}$, which is positive by definition. Fix $j \ne i$: we show that $B_{i,j} \ge \Delta$. Consider some $T > 0$ and $\gamma \in \mathcal{C}([0, T], \mathcal{X})$ such that $\gamma_0 \in K_i$ and $\gamma_T \in K_j$. By definition of $\delta$ and by continuity of $\gamma$ and $d(\cdot, K_i)$, there exists $t \in [0, T]$ such that $d(\gamma_t, K_i) = \delta'$. Therefore, we have that

$$S_{0,T}(\gamma) \ge S_{0,t}(\gamma) = \int_{0}^{t} \mathcal{L}(\gamma_s, \dot{\gamma}_s) ds, \qquad (\text{E.3.12})$$

and therefore, by definition of $\mathcal{L}$ as the conjugate of $\mathcal{H}$, we obtain that

$$S_{0,T}(\gamma) \ge \int_{0}^{t} \langle \dot{\gamma}_s, \nabla U(\gamma_s) \rangle - \bar{H}(\gamma_s, \nabla U(\gamma_s)) ds \ge \int_{0}^{t} \langle \dot{\gamma}_s, \nabla U(\gamma_s) \rangle, \qquad (\text{E.3.13})$$

where we used Eq. (E.3.10) in the last inequality. Thus, we get

$$S_{0,T}(\gamma) \ge U(\gamma_t) - U(\gamma_0) \ge \Delta, \qquad (\text{E.3.14})$$

with any $\delta' \le \delta/2$ (and therefore $\delta$ in the statement corresponds to $\delta/2$ here).
Finally, it remains to show that, any $l \neq i$, $E_l \geq \Delta$. Consider any tree rooted at $l$: it must have an edge of the form $i \to j$ for some $j \in I$ and therefore the sum of its weights will be at least $B_{i,j} \geq \Delta$. Hence, since it holds for any such tree, we have that $E_l \geq \Delta$.

We now prove the second part of the lemma. $\delta$ was chosen small enough so that it is possible to find $R > \delta$ such that $\mathbb{B}(0, R) \setminus \mathcal{U}_{\delta}(\mathcal{K}_i)$ contains all the $\mathcal{K}_j$ for $j \neq i$ and not $\mathcal{K}_i$. The assumption on the Lagrangian implies that, for any $x \in \mathbb{B}(0, R) \setminus \mathcal{U}_{\delta}(\mathcal{K}_i)$, $v \in \mathbb{B}(0, c)$,

$$ \mathcal{L}(x, v) \leq \frac{\|v + \nabla f(x)\|^2}{2s^2}. \qquad (\text{E.3.15}) $$

Fix $j \neq i$ and take $\gamma \in C^1([0, T], \mathcal{X})$ such that $\gamma_0 \in \mathcal{K}_j$, $x := \gamma_T \in \mathcal{U}_{\delta}(\mathcal{K}_i)$ and $\gamma$ remains in $\mathbb{B}(0, R) \setminus \mathcal{U}_{\delta}(\mathcal{K}_i)$. Without loss of generality, at the expense of replacing $\gamma$ by a reparametrization, we can assume that $\dot{\gamma}_t$ in $\mathbb{B}(0, c)$ for all $t \in [0, T]$. Then, we have that

$$ S_{0,T}(\gamma) \leq \int_{0}^{T} \mathcal{L}(\gamma_s, \dot{\gamma}_s) \, ds \leq \int_{0}^{T} \frac{\|\dot{\gamma}_s + \nabla f(\gamma_s)\|^2}{2s^2} \, ds, \qquad (\text{E.3.16}) $$

which depends only on the value of $\nabla f$ outside of $\mathcal{U}_{\delta/2}(\mathcal{K}_i)$. But, by the same reasoning as in Lemma D.31, since the flow started at $x$ converges to $\mathcal{K}_i$, we have that $B(\{x\}, \mathcal{K}_i) = 0$. Therefore, we have that,

$$ B_{j,i} \leq \int_{0}^{T} \frac{\|\dot{\gamma}_s + \nabla f(\gamma_s)\|^2}{2s^2} ds, \qquad (\text{E.3.17}) $$

and, taking the maximum of such quantities over all $j \neq i$, we obtain $C > 0$ such, for any $j \neq i$,

$$ B_{j,i} \leq \frac{C}{s^2}. \qquad (\text{E.3.18}) $$

To conclude on the value of $E_i$, we consider the tree rooted at $i$ made of all the edges $(j, i)$ for $j \neq i$. It has weight at most $(K-1)C/s^2$ and therefore, we have that $E_i \leq (K-1)C/s^2$. ■

# APPENDIX F. AUXILIARY RESULTS

## F.1. Truncated Gaussian distribution.

**Lemma F.1.** Consider $X \sim N(0, \Sigma)$ a multivariate Gaussian distribution $\Sigma \in \mathbb{R}^{d \times d}$ positive definite. For $R > 0$, define the truncated Gaussian random variable (r.v.) $X_R$ by conditioning $X$ to the ball $\mathbb{B}(0, R)$. Define

$$ \tilde{\mathcal{H}}(p) := \log \mathbb{E} \left[ e^{\langle p, X_R \rangle} \right] \qquad (\text{F.1.1}) $$

and

$$ \tilde{E}(\Sigma, \tilde{R}) := e^{-\frac{\tilde{R}^2}{4\|\Sigma\|^2}} (\text{tr} \Sigma + \|\Sigma\|) 2^{d+3} \qquad (\text{F.1.2}) $$

Then, for $\tilde{R} > 0$ such that

$$ \tilde{R} \geq \sqrt{\|\Sigma\|(2d+4)\log 2}, \qquad (\text{F.1.3}) $$

it holds that, for any $p \in \mathcal{X}$ such that $\|\Sigma p\| \leq R - \tilde{R}$,

$$ |\tilde{\mathcal{H}}(p) - \frac{1}{2}\langle p, \Sigma p \rangle| \leq \frac{1}{2}\tilde{E}(\Sigma, \tilde{R})\|p\|^2 \qquad (\text{F.1.4a}) $$

$$ \|\nabla \tilde{\mathcal{H}}(p) - \Sigma p\| \leq \tilde{E}(\Sigma, \tilde{R})\|p\| \qquad (\text{F.1.4b}) $$

$$ \|\text{Hess } \tilde{\mathcal{H}}(p) - \Sigma\| \leq \tilde{E}(\Sigma, \tilde{R}). \qquad (\text{F.1.4c}) $$

*Proof.* Define, for $S$ a measurable set,

$$ Z(S) = \int_S e^{-\frac{1}{2}x \cdot \Sigma^{-1}x} dx, \qquad (\text{F.1.5}) $$
and, for convenience, $\mathcal{K} := \bar{\mathbb{B}}(0, R)$. For notational convenience, in this proof, we will denote the inner product between two vectors $x$ and $p$ with a simple dot $x \cdot p$. We have that

$$ 
\begin{aligned}
\mathbb{E}[e^{X_R \cdot p}] &= \frac{e^{\frac{1}{2} p \cdot \Sigma p}}{Z(\mathcal{K})} \int_{\mathcal{K}} e^{-\frac{1}{2} (x - \Sigma p) \cdot \Sigma^{-1} (x - \Sigma p)} dx \\
&= \frac{e^{\frac{1}{2} p \cdot \Sigma p}}{Z(\mathcal{K})} \int_{\mathcal{K} - \Sigma p} e^{-\frac{1}{2} x' \cdot \Sigma^{-1} x'} dx' \\
&= e^{\frac{1}{2} p \cdot \Sigma p} \frac{Z(\mathcal{K} - \Sigma p)}{Z(\mathcal{K})},
\end{aligned} 
\quad (F.1.6) 
$$

where we performed the change of variable $x' \leftarrow x - \Sigma p$.

Define

$$ f(p) := Z(\mathcal{K} - \Sigma p) = \int_{\mathcal{K}} e^{-\frac{1}{2}(x - \Sigma p) \cdot \Sigma^{-1}(x - \Sigma p)} dx. \quad (F.1.7) $$

so that

$$ \bar{\mathcal{H}}(p) = \log \mathbb{E}[e^{X_R \cdot p}] = \frac{1}{2} p \cdot \Sigma p + \log \frac{f(p)}{f(0)}. \quad (F.1.8) $$

Therefore it suffices to bound $\log \frac{f(p)}{f(0)}$ and its derivatives.

Differentiating yields

$$ \nabla f(p) = \int_{\mathcal{K}} (x - \Sigma p) e^{-\frac{1}{2}(x - \Sigma p) \cdot \Sigma^{-1}(x - \Sigma p)} dx \quad (F.1.9a) $$

$$ \text{Hess } f(p) = \int_{\mathcal{K}} (x - \Sigma p)(x - \Sigma p)^{\top} e^{-\frac{1}{2}(x - \Sigma p) \cdot \Sigma^{-1}(x - \Sigma p)} dx - \Sigma f(p). \quad (F.1.9b) $$

Note that, by symmetry of $\bar{\mathbb{B}}(0, R)$, $\nabla f(0) = 0$.

We first bound $\text{Hess } f(p)$. Performing the change of variable $x' \leftarrow x - \Sigma p$ again gives us

$$ 
\begin{aligned}
\text{Hess } f(p) &= \int_{\mathcal{K} - \Sigma p} x' x'^{\top} e^{-\frac{1}{2} x' \cdot \Sigma^{-1} x'} dx' - \Sigma f(p) \\
&= \int_{\mathcal{K} - \Sigma p} (x' x'^{\top} - \Sigma) e^{-\frac{1}{2} x' \cdot \Sigma^{-1} x'} dx' \\
&= - \int_{\mathcal{X} \setminus (\mathcal{K} - \Sigma p)} (x' x'^{\top} - \Sigma) e^{-\frac{1}{2} x' \cdot \Sigma^{-1} x'} dx',
\end{aligned} 
\quad (F.1.10) 
$$

$$ \text{where we used that } \int_{\mathcal{X}} (x' x'^{\top} - \Sigma) e^{-\frac{1}{2} x' \cdot \Sigma^{-1} x'} dx' = 0. $$

By definition of $\bar{R}$, $\mathcal{K} - \Sigma p$ contains $\bar{\mathbb{B}}(0, \bar{R})$. We now bound the operator norm of $\text{Hess } f(p)$:

$$ 
\begin{aligned}
\|\text{Hess } f(p)\| &\le \int_{\mathcal{X} \setminus (\mathcal{K} - \Sigma p)} (\|x'\|^2 + \|\Sigma\|) e^{-\frac{1}{2} x' \cdot \Sigma^{-1} x'} dx' \\
&\le \int_{\mathcal{X} \setminus \bar{\mathbb{B}}(0, \bar{R})} (\|x'\|^2 + \|\Sigma\|) e^{-\frac{1}{2} x' \cdot \Sigma^{-1} x'} dx' \\
&\le e^{-\frac{\bar{R}^2}{4\|\Sigma\|}} \int_{\mathcal{X}} (\|x'\|^2 + \|\Sigma\|) e^{-\frac{1}{4} x' \cdot \Sigma^{-1} x'} dx' \\
&= e^{-\frac{\bar{R}^2}{4\|\Sigma\|}} (\text{tr} \Sigma + \|\Sigma\|) (4\pi)^{d/2} \det(\Sigma)^{1/2},
\end{aligned} 
\quad (F.1.11) 
$$
We now bound $\nabla f(p)$. The change of variable $x' \leftarrow x - \Sigma p$ yields

$$ \nabla f(p) = \int_{\mathcal{K}-\Sigma p} x' e^{-\frac{1}{2}x' \cdot \Sigma^{-1} x'} dx' = \int_{\mathcal{X} \setminus (\mathcal{K}-\Sigma p)} x' e^{-\frac{1}{2}x' \cdot \Sigma^{-1} x'} dx', \quad (F.1.12) $$

where we used that $\int_{\mathcal{X}} x' e^{-\frac{1}{2}x' \cdot \Sigma^{-1} x'} dx' = 0$.

Therefore, similar computations as above yield that

$$ \begin{aligned} \|\nabla f(p)\| & \le \int_{\mathcal{X} \setminus (\mathcal{K}-\Sigma p)} \|x'\| e^{-\frac{1}{2}x' \cdot \Sigma^{-1} x'} dx' \\ & \le \int_{\mathcal{X} \setminus \bar{\mathcal{B}}(0, \tilde{R})} \|x'\| e^{-\frac{1}{2}x' \cdot \Sigma^{-1} x'} dx' \\ & \le e^{-\frac{\tilde{R}^2}{4\|\Sigma\|}} \int_{\mathcal{X}} \|x'\| e^{-\frac{1}{4}x' \cdot \Sigma^{-1} x'} dx' \\ & \le e^{-\frac{\tilde{R}^2}{4\|\Sigma\|}} \sqrt{\operatorname{tr} \Sigma} (4\pi)^{d/2} \det(\Sigma)^{1/2}. \end{aligned} \quad (F.1.13) $$

Let us now lower-bound $f(p)$. In the same fashion as above, we have that

$$ \begin{aligned} f(p) &= \int_{\mathcal{K}-\Sigma p} e^{-\frac{1}{2}x' \cdot \Sigma^{-1} x'} dx' \\ &\ge \int_{\bar{\mathcal{B}}(0, \tilde{R})} e^{-\frac{1}{2}x' \cdot \Sigma^{-1} x'} dx' \\ &\ge (2\pi)^{d/2} \det(\Sigma)^{1/2} \left(1 - 2^{d/2} e^{-\frac{\tilde{R}^2}{4\|\Sigma\|}}\right), \end{aligned} \quad (F.1.14) $$

so that, if $\tilde{R} \ge \sqrt{\|\Sigma\|(2d+4)\log 2}$, it holds that

$$ f(p) \ge \frac{1}{2}(2\pi)^{d/2} \det(\Sigma)^{1/2} \quad (F.1.15) $$

The Hessian of $\log f/f(0)$ is then given by

$$ \text{Hess} \log \frac{f(p)}{f(0)} = \frac{\text{Hess } f(p)}{f(p)} - \frac{\nabla f(p) \nabla f(p)^{\top}}{f(p)^2}. \quad (F.1.16) $$

Eqs. (F.1.11), (F.1.13) and (F.1.15) combined yield that

$$ \begin{aligned} \left\| \text{Hess} \log \frac{f(p)}{f(0)} \right\| & \le e^{-\frac{\tilde{R}^2}{4\|\Sigma\|}} (\operatorname{tr} \Sigma + \|\Sigma\|)^{2d/2+1} + \left( e^{-\frac{\tilde{R}^2}{4\|\Sigma\|}} \sqrt{\operatorname{tr} \Sigma} 2^{d/2+1} \right)^2 \\ & \le e^{-\frac{\tilde{R}^2}{4\|\Sigma\|}} (\operatorname{tr} \Sigma + \|\Sigma\|)^{2d+3} = \tilde{E}(\Sigma, \tilde{R}). \end{aligned} \quad (F.1.17) $$

Taylor-Lagrange inequality now yields the full result since $\log f(0)/f(0) = 0$ and $\nabla \log f(0) = 0$. ■

**Lemma F.2.** Consider $X \sim \mathcal{N}(0, \sigma^2 I)$ a multivariate Gaussian distribution with $\sigma^2 > 0$. For $R > 0$, define the truncated Gaussian r.v. $X_R$ by conditioning $X$ to the ball $\bar{\mathcal{B}}(0, R)$. Define

$$ \mathcal{H}(p) := \log \mathbb{E} \left[ e^{\langle p, X_R \rangle} \right] \quad (F.1.18a) $$

$$ \mathcal{L}(p) := \mathcal{H}^*(p), \quad (F.1.18b) $$

and

$$ E(\sigma^2, R) := e^{-\frac{R^2}{16\sigma^2}} 2^{d+3}(d+1) \quad (F.1.19) $$
and assume that $R > 0$ satisfies

$$R \geq 4\sigma\sqrt{(d+3)\log 2 + \log(d+1)}. \qquad (\text{F.1.20})$$

Then, for any $p \in \mathcal{X}$ such that $\|p\| \le \frac{R}{2\sigma^2}$, $v \in \mathcal{X}$ such that $\|v\| \le \frac{R}{4}$, it holds that

$$(1 - E(\sigma^2, R)) \frac{\sigma^2 \|p\|^2}{2} \le \bar{\mathcal{H}}(p) \le (1 + E(\sigma^2, R)) \frac{\sigma^2 \|p\|^2}{2} \qquad (\text{F.1.21a})$$

$$(1 - 2E(\sigma^2, R)) \frac{\|v\|^2}{2\sigma^2} \le \bar{\mathcal{L}}(v) \le (1 + 2E(\sigma^2, R)) \frac{\|v\|^2}{2\sigma^2}. \qquad (\text{F.1.21b})$$

*Proof.* First, let us show that, for any $r > 0$, $\nabla\mathcal{H}(\bar{\mathbb{B}}(0,r))$ is an open ball centered at 0. Since the distribution of $X_R$ is invariant by rotation, this set can be rewritten as

$$\nabla\mathcal{H}(\bar{\mathbb{B}}(0,r)) = \{v \in \mathcal{X} : \|v\| \in \{\|\nabla\mathcal{H}(p)\| : p \in \bar{\mathbb{B}}(0,r)\}\}. \qquad (\text{F.1.22})$$

But, by connectedness of $\bar{\mathbb{B}}(0, r)$ and continuity of $\nabla\mathcal{H}$, $\{\|\nabla\mathcal{H}(p)\| : p \in \bar{\mathbb{B}}(0, r)\}$ is an interval. Since $\nabla\mathcal{H}(0) = 0$, it is either $[0, \|\nabla\mathcal{H}(r)\|]$ or $[0, \|\nabla\mathcal{H}(-r)\|)$. $\nabla\mathcal{H}(\bar{\mathbb{B}}(0, r))$ being compact and therefore closed, it must be the latter. Hence, we have shown that

$$\nabla\mathcal{H}(\bar{\mathbb{B}}(0,r)) = \bar{\mathbb{B}}\left(0, \sup_{\bar{\mathbb{B}}(0,r)} \|\nabla\mathcal{H}\|\right). \qquad (\text{F.1.23})$$

We apply Lemma F.1 with $\tilde{R} \leftarrow \frac{R}{2}$. Note that our choice of $R$ implies that $\tilde{R}$ satisfies the condition of Lemma F.1 and, moreover, that $E(\sigma^2, R) \le \frac{1}{2}$. Lemma F.1 directly implies the bound on $\tilde{\mathcal{H}}$.

Consider $p \in \mathcal{X}$ such that $\|p\| \le \frac{R}{2\sigma^2}$. Then, by Lemma F.1, we have that

$$\begin{aligned} \|\nabla \bar{\mathcal{H}}(p)\| &\ge \sigma^2 \|p\| - e^{-\frac{R^2}{16\sigma^2}} 2^{d+3} (\text{tr}(\sigma^2 I) + \|\sigma^2 I\|) \|p\| \\ &= \sigma^2 \|p\| (1 - E(\sigma^2, R)) \\ &\ge \frac{\sigma^2 \|p\|}{2}, \end{aligned} \qquad (\text{F.1.24})$$

where we used that $E(\sigma^2, R) \le \frac{1}{2}$. Therefore, we obtain that $\sup\{\|\nabla\bar{\mathcal{H}}(p)\| : p \in \bar{\mathbb{B}}(0, \frac{R}{2\sigma^2})\} \ge \frac{R}{4}$ so that $\nabla\mathcal{H}(\bar{\mathbb{B}}(0, \frac{R}{2\sigma^2}))$ contains $\bar{\mathbb{B}}(0, \frac{R}{4})$.

Take $p \in \bar{\mathbb{B}}(0, \frac{R}{4})$ which therefore belongs to $\nabla\mathcal{H}(\bar{\mathbb{B}}(0, \frac{R}{2\sigma^2}))$. Therefore, $\bar{\mathcal{L}}(v)$ can be rewritten as

$$\bar{\mathcal{L}}(v) = \sup_{p \in \bar{\mathbb{B}}(0, \frac{R}{2\sigma^2})} \langle v, p \rangle - \bar{\mathcal{H}}(p). \qquad (\text{F.1.25})$$

Using Lemma F.1 again, we obtain that

$$\sup_{p \in \bar{\mathbb{B}}(0, \frac{R}{2\sigma^2})} \langle v, p \rangle - \frac{\sigma^2}{2}(1 + E(\sigma^2, R))\|v\|^2 \le \bar{\mathcal{L}}(v) \le \sup_{p \in \bar{\mathbb{B}}(0, \frac{R}{2\sigma^2})} \langle v, p \rangle - \frac{\sigma^2}{2}(1 - E(\sigma^2, R))\|v\|^2, \qquad (\text{F.1.26})$$

so that, since $E(\sigma^2, R) \le \frac{1}{2}$, we obtain that

$$\frac{\|v\|^2}{2\sigma^2(1 + E(\sigma^2, R))} \le \bar{\mathcal{L}}(v) \le \frac{\|v\|^2}{2\sigma^2(1 - E(\sigma^2, R))}. \qquad (\text{F.1.27})$$

Since, for $x \in [0, 1/2]$, both $\frac{1}{1+x} \ge 1 - 2x$ and $\frac{1}{1-x} \le 1 + 2x$ hold, we get

$$\frac{\|v\|^2}{2\sigma^2} (1 - 2E(\sigma^2, R)) \le \bar{\mathcal{L}}(v) \le \frac{\|v\|^2}{2\sigma^2} (1 + 2E(\sigma^2, R)) \qquad (\text{F.1.28})$$

which concludes the proof. ■
We will require the following technical lemma.

**Lemma F.3.** Consider $v, w \in \mathcal{X}$ such that $0 < \|w\| \le \frac{\mu R}{2}$ for some $R, \mu > 0$. Define,

$$f(u) = \sup_{p \in \mathcal{X}: \|p\| \le R} \langle p, u \rangle - \frac{\mu}{2} \|p\|^2, \qquad (F.1.29)$$

then, with $\lambda = \frac{\|v\|}{\|w\|}$,

$$\lambda f\left(\frac{v}{\lambda} + w\right) \le f(v + w). \qquad (F.1.30)$$

*Proof.* Define $p := \frac{1}{\mu}(\frac{v}{\lambda} + w)$ which has norm at most $R$ since $\|w\| \le \frac{R}{2\mu}$. Then, we have that

$$\begin{align*}
\lambda f\left(\frac{v}{\lambda} + w\right) - f(v + w) &\le \lambda\left(\left\langle p, \frac{v}{\lambda} + w \right\rangle - \frac{\mu}{2}\|p\|^2\right) - \left\langle p, v + w \right\rangle - \frac{\mu}{2}\|p\|^2 \\
&= (\lambda - 1)\left(\left\langle p, w \right\rangle - \frac{\mu}{2}\|p\|^2\right) \\
&= (\lambda - 1) \times \frac{1}{\mu}\left(\frac{\langle v, w \rangle}{\lambda} + \|w\|^2 - \frac{1}{2}\left(2\|w\|^2 + 2\frac{\langle v, w \rangle}{\lambda}\right)\right) \\
&= 0, \tag{F.1.31}
\end{align*}$$

and our proof is complete.

## REFERENCES

[1] Alongi, J. M. and Nelson, G. S. *Recurrence and Topology*, volume 85 of *Graduate Studies in Mathematics*. American Mathematical Society, 2007.

[2] Antonakopoulos, K., Mertikopoulos, P., Piliouras, G., and Wang, X. AdaGrad avoids saddle points. In *ICML '22: Proceedings of the 39th International Conference on Machine Learning*, 2022.

[3] Benaïm, M. Dynamics of stochastic approximation algorithms. In *Azéma, J., Émery, M., Ledoux, M.*, and Yor, M. (eds.), *Séminaire de Probabilités XXXIII*, volume 1709 of *Lecture Notes in Mathematics*, pp. 1–68. Springer Berlin Heidelberg, 1999.

[4] Benaïm, M. and Hirsch, M. W. Dynamics of Morse-Smale urn processes. *Ergodic Theory and Dynamical Systems*, 15(6):1005–1030, December 1995.

[5] Bertsekas, D. P. and Tsitsiklis, J. N. Gradient convergence in gradient methods with errors. *SIAM Journal on Optimization*, 10(3):627–642, 2000.

[6] Blanc, G., Gupta, N., Valiant, G., and Valiant, P. Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process. In *COLT '20: Proceedings of the 33rd Annual Conference on Learning Theory*, 2020.

[7] Brown, L. D. *Fundamentals of Statistical Exponential Families with Applications in Statistical Decision Theory*, volume 9 of *Lecture Notes-Monograph Series*. Institute of Mathematical Statistics, 1986.

[8] Choromanska, A., Henaff, M., Mathieu, M., Ben Arous, G., and LeCun, Y. The loss surfaces of multilayer networks. In *AISTATS '15: Proceedings of the 18th International Conference on Artificial Intelligence and Statistics*, 2015.

[9] Coste, M. An introduction to *o*-minimal geometry, 1999.

[10] Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., and Bengio, Y. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In *NIPS '14: Proceedings of the 27th International Conference on Neural Information Processing Systems*, 2014.

[11] de Acosta, A. D. *Large Deviations for Markov Chains*. Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, UK, 2022.

[12] Dembo, A. and Zeitouni, O. *Large Deviations Techniques and Applications*. Springer-Verlag, Berlin, 1998.

[13] Dieuleveut, A., Durmus, A., and Bach, F. Bridging the gap between constant step size stochastic gradient descent and Markov chains. *The Annals of Statistics*, 48(3):1348–1382, June 2020.

[14] Douc, R., Moulines, E., Priouret, P., and Soulier, P. *Markov Chains*. Springer Series in Operations Research and Financial Engineering. Springer, 2018.
[15] Dupuis, P. Large deviations analysis of some recursive algorithms with state dependent noise. *The Annals of Probability*, 16(4):1509–1536, October 1988.

[16] Dupuis, P. and Kushner, H. J. Stochastic approximations via large deviations: Asymptotic properties. *SIAM Journal on Control and Optimization*, 23(5):675–696, September 1985.

[17] Eberle, A. Reflection couplings and contraction rates for diffusions. *Probability Theory and Related Fields*, 166(3-4):851–886, December 2016.

[18] Erdogdu, M. A., Mackey, L. W., and Shamir, O. Global non-convex optimization with discretized diffusions. In *NeurIPS '18: Proceedings of the 32nd International Conference of Neural Information Processing Systems*, 2018.

[19] Feng, Y., Gao, T., Li, L., Liu, J.-G., and Lu, Y. Uniform-in-time weak error analysis for stochastic gradient descent algorithms via diffusion approximation. *Communications in Mathematical Sciences*, 18 (1):163–188, 2020.

[20] Freidlin, M. I. and Wentzell, A. D. *Random Perturbations of Dynamical Systems*. Springer, 1 edition, 1998.

[21] Ge, R., Huang, F., Jin, C., and Yuan, Y. Escaping from saddle points – Online stochastic gradient for tensor decomposition. In *COLT '15: Proceedings of the 28th Annual Conference on Learning Theory*, 2015.

[22] Gulinsky, O. V. and Veretennikov, A. Y. *Large Deviations for Discrete-Time Processes with Averaging*. De Gruyter, 1993.

[23] Gürbüzbalaban, M., Şimşekli, U., and Zhu, L. The heavy-tail phenomenon in SGD. In *ICML '21: Proceedings of the 38th International Conference on Machine Learning*, 2021.

[24] Hernández-Lerma, O. and Lasserre, J.-B. *Markov Chains and Invariant Probabilities*. Birkhäuser, Basel, 2003.

[25] Hodgkinson, L. and Mahoney, M. Multiplicative noise and heavy tails in stochastic optimization. In *ICML '21: Proceedings of the 38th International Conference on Machine Learning*, 2021.

[26] Hsieh, Y.-P., Mertikopoulos, P., and Cevher, V. The limits of min-max optimization algorithms: Convergence to spurious non-critical sets. In *ICML '21: Proceedings of the 38th International Conference on Machine Learning*, 2021.

[27] Hsieh, Y.-P., Karimi, M. R., Krause, A., and Mertikopoulos, P. Riemannian stochastic optimization methods avoid strict saddle points. In *NeurIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems*, 2023.

[28] Hu, W., Li, C. J., Li, L., and Liu, J.-G. On the diffusion approximation of nonconvex stochastic gradient descent. *Annals of Mathematical Sciences and Applications*, 4(1):3–32, 2019.

[29] Ioffe, A. D., Tikhomirov, V. M., and Makowski, K. *Theory of Extremal Problems*. North Holland, Amsterdam, NL, 1979.

[30] Jastrzębski, S., Kenton, Z., Arpit, D., Ballas, N., Fischer, A., Bengio, Y., and Storkey, A. Three factors influencing minima in SGD. https://arxiv.org/abs/1711.04623, 2017.

[31] Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., and Jordan, M. I. How to escape saddle points efficiently. In *ICML '17: Proceedings of the 34th International Conference on Machine Learning*, 2017.

[32] Kallenberg, O. *Foundations of Modern Probability*, volume 99 of *Probability Theory and Stochastic Modelling*. Springer, 2021.

[33] Kawaguchi, K. Deep learning without poor local minima. In *NIPS '16: Proceedings of the 30th International Conference on Neural Information Processing Systems*, 2016.

[34] Kiefer, J. and Wolfowitz, J. Stochastic estimation of the maximum of a regression function. *The Annals of Mathematical Statistics*, 23(3):462–466, 1952.

[35] Kifer, Y. *Random Perturbations of Dynamical Systems*. Birkhäuser, Boston, MA, 1988.

[36] Kifer, Y. A discrete-time version of the Wentzell-Freidlin theory. *Annals of Probability*, 18(4):1676–1692, October 1990.

[37] Lan, G. *First-order and Stochastic Optimization Methods for Machine Learning*. Springer, 2020.

[38] Landau, L. D. and Lifshitz, E. M. Statistical physics. In *Course of Theoretical Physics*, volume 5. Pergamon Press, Oxford, 1976.

[39] Lee, J. D., Panageas, I., Piliouras, G., Simchowitz, M., Jordan, M. I., and Recht, B. First-order methods almost always avoid strict saddle points. *Mathematical Programming*, 176(1):311–337, February 2019.

[40] Li, L. and Wang, Y. A sharp uniform-in-time error estimate for stochastic gradient Langevin dynamics. https://arxiv.org/abs/2207.09304, 2022.
[41] Li, L. and Wang, Y. On uniform-in-time diffusion approximation for stochastic gradient descent. https://arxiv.org/abs/2207.04922, 2022.

[42] Li, Q., Tai, C., and E. W. Stochastic modified equations and adaptive stochastic gradient algorithms. In *ICML '17: Proceedings of the 34th International Conference on Machine Learning*, 2017.

[43] Li, Q., Tai, C., and E. W. Stochastic modified equations and dynamics of stochastic gradient algorithms I: Mathematical foundations. *Journal of Machine Learning Research*, 20(40):1–47, 2019.

[44] Li, Z., Lyu, K., and Arora, S. Reconciling modern deep learning with traditional optimization analyses: The intrinsic learning rate. In *NeurIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems*, 2020.

[45] Li, Z., Wang, T., and Arora, S. What happens after SGD reaches zero loss? –A mathematical framework. In *ICLR '21: Proceedings of the 2021 International Conference on Learning Representations*, 2021.

[46] Li, Z., Wang, T., and Yu, D. Fast mixing of stochastic gradient descent with normalization and weight decay. In *NeurIPS '22: Proceedings of the 36th International Conference on Neural Information Processing Systems*, 2022.

[47] Liu, S., Papailiopoulos, D., and Achlioptas, D. Bad global minima exist and SGD can reach them. In *NeurIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems*, 2020.

[48] Ljung, L. Analysis of recursive stochastic algorithms. *IEEE Trans. Autom. Control*, 22(4):551–575, August 1977.

[49] Lu, Y., Balasubramanian, K., Volgushev, S., and Erdogdu, M. A. An analysis of constant step size SGD in the non-convex regime: Asymptotic normality and bias. In *NeurIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems*, 2021.

[50] Lytras, I. and Mertikopoulos, P. Tamed Langevin sampling under weaker conditions. https://arxiv.org/abs/2405.17693, 2024.

[51] Majka, M. B., Mijatović, A., and Szpruch, Ł. Nonasymptotic bounds for sampling algorithms without log-concavity. *The Annals of Applied Probability*, 30(4):1534–1581, 2020.

[52] Mertikopoulos, P., Hallak, N., Kavis, A., and Cevher, V. On the almost sure convergence of stochastic gradient descent in non-convex problems. In *NeurIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems*, 2020.

[53] Mertikopoulos, P., Hsieh, Y.-P., and Cevher, V. A unified stochastic approximation framework for learning in games. *Mathematical Programming*, 203:559–609, January 2024.

[54] Mignacco, F. and Urbani, P. The effective noise of stochastic gradient descent. *Journal of Statistical Mechanics: Theory and Experiment*, 2022(8):083405, 2022.

[55] Mignacco, F., Krzakala, F., Urbani, P., and Zdeborová, L. Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification. In *NeurIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems*, 2020.

[56] Mori, T., Ziyin, L., Liu, K., and Ueda, M. Power-law escape rate of SGD. In *ICML '22: Proceedings of the 39th International Conference on Machine Learning*, 2022.

[57] Pavasovic, K. L., Durmus, A., and Şimşekli, U. Approximate heavy tails in offline (multi-pass) stochastic gradient descent. In *NeurIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems*, 2023.

[58] Pemantle, R. Nonconvergence to unstable points in urn models and stochastic approximations. *Annals of Probability*, 18(2):698–712, April 1990.

[59] Raginsky, M., Rakhlin, A., and Telgarsky, M. Non-convex learning via stochastic gradient Langevin dynamics: A nonasymptotic analysis. In *COLT '17: Proceedings of the 30th Annual Conference on Learning Theory*, 2017.

[60] Rigollet, P. and Hütter, J.-C. High-dimensional statistics. https://arxiv.org/abs/2310.19244, 2023.

[61] Robbins, H. and Monro, S. A stochastic approximation method. *Annals of Mathematical Statistics*, 22: 400–407, 1951.

[62] Tutte, W. T. *Graph theory*. Cambridge University Press, 2001.

[63] van den Dries, L. and Miller, C. Geometric categories and $o$-minimal structures. *Duke Mathematical Journal*, 84(2), August 1996.

[64] Veiga, R., Remizova, A., and Macris, N. Stochastic gradient flow dynamics of test risk and its exact solution for weak features. https://arxiv.org/abs/2402.07626, 2024.
[65] Wainwright, M. J. *High-dimensional statistics: A non-asymptotic viewpoint*, volume 48. Cambridge University Press, 2019.

[66] Wang, Y. and Wang, Z. Three-stage evolution and fast equilibrium for SGD with non-degenerate critical points. In *ICML '22: Proceedings of the 39th International Conference on Machine Learning*, 2022.

[67] Wojtowytsch, S. Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis. *Journal of Nonlinear Science*, 33(3):45, 2023.

[68] Xie, Z., Sato, I., and Sugiyama, M. A diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima. In *ICLR '21: Proceedings of the 2021 International Conference on Learning Representations*, 2021.

[69] Yang, J., Hu, W., and Li, C. J. On the fast convergence of random perturbations of the gradient flow. *Asymptotic Analysis*, 122(3-4):371-393, 2021.

[70] Zhou, Z., Mertikopoulos, P., Bambos, N., Boyd, S. P., and Glynn, P. W. On the convergence of mirror descent beyond stochastic convex programming. *SIAM Journal on Optimization*, 30(1):687-716, 2020.

[71] Ziyin, L., Li, H., and Ueda, M. Law of balance and stationary distribution of stochastic gradient descent. https://arxiv.org/abs/2308.06671, 2023.