# Continuized Nesterov Momentum Achieves the $O(\varepsilon^{-7/4})$ Complexity without Additional Mechanisms

Julien Hermant, Jean-François Aujol, Charles Dossal, Lorick Huang, Aude Rondepierre

► To cite this version:

Julien Hermant, Jean-François Aujol, Charles Dossal, Lorick Huang, Aude Rondepierre. Continuized Nesterov Momentum Achieves the $O(\varepsilon^{-7/4})$ Complexity without Additional Mechanisms. 2026. hal-05503080

HAL Id: hal-05503080

https://hal.science/hal-05503080v1

Preprint submitted on 10 Feb 2026

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Continuized Nesterov Momentum Achieves the $O(\varepsilon^{-7/4})$ Complexity without Additional Mechanisms

Julien Hermant*†

Jean-François Aujol†

Charles Dossal‡

Lorick Huang‡

Aude Rondepierre‡

## Abstract

For first-order optimization of non-convex functions with Lipschitz continuous gradient and Hessian, the best known complexity for reaching an $\varepsilon$-approximation of a stationary point is $O(\varepsilon^{-7/4})$. Existing algorithms achieving this bound are based on momentum, but are always complemented with safeguard mechanisms, such as restarts or negative-curvature exploitation steps. Whether such mechanisms are fundamentally necessary has remained an open question. Leveraging the continuized method, we show that a Nesterov momentum algorithm with stochastic parameters alone achieves the same complexity in expectation. This result holds up to a multiplicative stochastic factor with unit expectation and a restriction to a subset of the realizations, both of which are independent of the objective function. We empirically verify that these constitute mild limitations.

## 1 Introduction

Many real-world problems can be formulated as the minimization of a function $f: \mathbb{R}^d \to \mathbb{R}$, that is, as $\min_{x \in \mathbb{R}^d} f(x)$. Yet, without structural assumptions—such as convexity of $f$—computing a global minimizer is generally intractable [20, Section 2.2]. In this work, assuming $f$ is lower bounded and differentiable, our goal is thus to find a stationary point of $f$, i.e. approximate $x^* \in \mathbb{R}^d$ such that

$$\nabla f(x^*) = 0.$$

The rising computational cost and expanding data scales in modern applications—ranging from machine learning to signal processing—have made first-order optimization algorithms widely used. These algorithms rely on gradient information to compute their iterates; gradient descent being a classic example. Among existing acceleration techniques designed to improve their convergence speed [35, 39], one of the most influential is momentum, whose idea dates back to the seminal work of [55].

**Nesterov momentum** The Nesterov momentum (NM) algorithm [49], sometimes called Nesterov accelerated gradient, is known to achieve optimal convergence bounds among first-order algorithms in various settings in convex optimization [48, 51], see Appendix A.1 for a more detailed discussion. One way to write Nesterov momentum is the following

$$ \begin{cases} y_n = x_n + \alpha_n(x_n - x_{n-1}), & \leftarrow \textit{momentum step} \\ x_{n+1} = y_n - s\nabla f(y_n). & \leftarrow \textit{gradient step} \end{cases} \qquad (\text{NM}) $$

The momentum step can be viewed as a memory term, which disappears in the case of gradient descent ($\alpha_n = 0$ in (NM)). Because a wide range of applications are formulated as a non-convex optimization problem [29, 13, 21, 10, 24, 23, 41], an important question is whether the benefits of momentum extend beyond convex optimization. Empirically, it is often observed that the use of momentum improves the speed of convergence for non-convex minimization tasks such as neural

<footnote>*corresponding author: julien.hermant@math.u-bordeaux.fr</footnote>

<footnote>†Univ. Bordeaux, Bordeaux INP, CNRS, IMB, UMR 5251, F-33400 Talence, France</footnote>

<footnote>‡IMT, Univ. Toulouse, INSA Toulouse, Toulouse, France</footnote>
network optimization [61, 30]. Theoretically, acceleration has been shown in some mild non-convex settings where finding a global minimizer remains tractable, see e.g. [34, 32, 28]. In this work, we only adopt smoothness assumptions, which fall outside regimes where guarantees of global minimization can be obtained.

**Lipschitz Gradient** When the objective $f$ has a Lipschitz continuous gradient, finding a $\varepsilon$-stationary point, i.e. $x \in \mathbb{R}^d$ such that $\|\nabla f(x)\| \le \varepsilon$, can be achieved by gradient descent in at most $O(\varepsilon^{-2})$ gradient evaluations [51, (1.2.22)]. This bound is worst-case optimal among first-order algorithms [16]. The momentum mechanism thus does not provably accelerate gradient descent, achieving a similar rate [25]. This impossibility result suggests that the class of functions with merely Lipschitz-continuous gradients does not provide an adequate framework for understanding the acceleration mechanisms observed in practice. This motivates the study of higher-order smoothness assumptions.

**Lipschitz Hessian** Assuming in addition that the Hessian is Lipschitz continuous, the aforementioned bound can be improved to $O(\varepsilon^{-7/4})$ [14, 37, 42]. This class of functions therefore admits accelerated rates, while still encompassing important non-convex problems, such as matrix factorization [36]. All existing first-order algorithms achieving this complexity rely on (NM) as their core update. However, these methods also need to perform a security check at each iteration. If it fails, an alternative mechanism is triggered. At a conceptual level, these procedures can be summarized as follows:

<caption>**Algorithm 1:** Structure of existing algorithms achieving the $O(\varepsilon^{-7/4})$ complexity</caption>

1. **if** Security check succeed **then**
2. **if** Run update rule (NM)
3. **else**
4. **Trigger alternative mechanism**

In [14, 37], the security check monitors the level of non-convexity between consecutive iterates; when it exceeds a threshold, a negative-curvature exploitation step is triggered as an alternative mechanism. [42] employs a security check based on the length of the trajectory residual; if it becomes too large, a restart mechanism is activated. Detailed algorithmic descriptions and further discussion are provided in Appendix A.3. This raises the following critical question:

**Is (NM) itself fundamentally unable to achieve the $O(\varepsilon^{-7/4})$ complexity?**

In a recent result, [53] shows that the time needed for the solution of the Heavy Ball ordinary differential equation (ODE) to find a $\varepsilon$-stationary solution is at most $O(\varepsilon^{-7/4})$. Importantly, the Heavy Ball ODE can be viewed as a continuous-time analogue of momentum algorithms [59, 58]. This raises the question of whether this result can be transferred to the discrete setting. To our knowledge, no such discrete counterpart currently exists.

**Contribution** To bridge the gap between the continuous result of [53] and the discrete setting, we study the *continuized version* of Nesterov momentum [22]. Its analysis involves a process that mixes continuous momentum and gradient steps at random times, leading to an alternative formulation of (NM):

$$ 
\left\{ 
\begin{aligned}
\tilde{y}_k &= \tilde{x}_k + \alpha_k(\tilde{z}_k - \tilde{x}_k), \\
\tilde{x}_{k+1} &= \tilde{y}_k - \gamma \nabla f(\tilde{y}_k), \\
\tilde{z}_{k+1} &= \tilde{z}_k + \beta_k(\tilde{y}_k - \tilde{z}_k) - \gamma' \nabla f(\tilde{y}_k),
\end{aligned}
\right. 
\quad (1) $$

where the sequences $(\alpha_k)_{k \ge 0}$ and $(\beta_k)_{k \ge 0}$ are stochastic. Noting $(\Omega, \mathcal{F}, \mathbb{P})$ the underlying probability space, our main result is the following (see Theorem 4.2 for the formal version).

**Theorem 1.1 (Informal version).** Let $A_n \subset \Omega$ a subset of the realizations and a random variable $\chi_n > 0$ verifying $\mathbb{E}[\chi_n] = 1$, for some $n \in \mathbb{N}^*$. For $f$ with Lipschitz gradient and Hessian, after $n$ iterations, (1) properly parameterized outputs a point $\tilde{x}$ verifying

$$ \mathbb{E}[1_{A_n} \|\nabla f(\tilde{x})\| \chi_n] = O(n^{-4/7}). $$

It further implies $\mathbb{E}[1_{A_n} \|\nabla f(\tilde{x})\| \chi_n] \le \varepsilon$ in at most $O(\varepsilon^{-7/4})$ gradient evaluations. Importantly, the set $A_n$ and the random variable $\chi_n$ are independent of the function $f$ to minimize, which enables us to empirically verify that for any choice of function:
1. $\mathbb{P}(A_n)$ is close to one.

2. $\chi_n$ is close to one.

## 1.1 Related works

**First order acceleration under Lipschitz gradient and Hessian** The $O(\varepsilon^{-7/4})$ complexity with a first-order algorithm was first achieved by [14]. The proposed nested-loop algorithm combines Nesterov momentum (NM) with negative-curvature exploitation and the minimization of a regularized surrogate function. This approach is subsequently simplified in [37], where the algorithm reduces to (NM) combined with negative-curvature steps. Replacing the negative curvature exploitation with a restart mechanism, [42] also achieves the $O(\varepsilon^{-7/4})$ bound, additionally improving by a logarithmic factor. This restart-based line of work has since been extended to a parameter-free algorithm [43], a forward-backward version [57] and a universal algorithm under Hölder continuous Hessian [44]. The existing lower bound on the number of gradient evaluations needed to find a $\varepsilon$-stationary point in this setting is $O(\varepsilon^{-12/7})$ [17], which does not match the best known upper bound $O(\varepsilon^{-7/4})$. Closing this gap remains an open problem.

**Second-order stationary points** In contrast to our setting, several works have focused on second-order stationary points, which under suitable assumptions correspond to local minimizers, see a formal definition in Appendix A.2. With probability $1 - \delta$, such a point is found in at most $O(\varepsilon^{-7/4} \log(\frac{d}{\delta\varepsilon}))$ gradient and Hessian-vector product evaluations [1, 15], or with gradient evaluation only [37, 42]. Nevertheless, we note that (i) first-order procedures exist that transform algorithms for finding first-order stationary points into ones that find second-order stationary points [63, 3] and (ii) under random initialization, gradient-based methods typically converge almost surely to local minimizers —see [40] for gradient descent, [60] for the heavy ball algorithm.

**Continuized Nesterov** The continuized Nesterov equations are introduced in [22], motivated by the study of asynchronous algorithms. They show that the continuized Nesterov algorithm recovers, in expectation, the existing rate of the classic Nesterov Momentum for (strongly)-convex functions, further generalized to (strongly)-quasar convex functions [62, 31]. This method has known some extensions in the specific field of decentralized asynchronous algorithms [47, 46], but remains largely unexplored in optimization.

# 2 Background

In this work, we denote by $\mathcal{E}(1)$ the exponential distribution with parameter 1, $\Gamma(k, 1)$ the Gamma distribution with shape parameter $k$ and rate 1 and $\mathcal{P}(\lambda)$ the Poisson distribution with parameter $\lambda$. For $\phi: \mathbb{R} \to \mathbb{R}$, $t \in \mathbb{R}$, we note $\phi(t^-) := \lim_{s \to t^-} \phi(s)$ the left-limit. $\| \cdot \|$ denotes the Euclidean norm for vectors and $\| \cdot \|_2$ denotes the spectral norm for matrices.

We consider the two following assumptions.

**Assumption 2.1.** $f$ is such that $\forall x, y \in \mathbb{R}^d$, $\|\nabla f(x) - \nabla f(y)\| \le L \|x - y\|$.

**Assumption 2.2.** $f$ is such that $\forall x, y \in \mathbb{R}^d$, $\|\nabla^2 f(x) - \nabla^2 f(y)\|_2 \le L_2 \|x - y\|$.

For functions satisfying Assumption 2.1 and/or Assumption 2.2, a critical point could be a non-global minimizer, a saddle point, or a maximizer. As mentioned in Section 1, Assumption 2.1 alone is sufficient to find a $\varepsilon$-stationary point with first-order methods [51, 25], but the complexity of gradient descent cannot be improved [16]. Considering Assumptions 2.1-2.2 together allows for such improvement. In existing analysis [37, 42], Assumption 2.2 enables working with local quadratic approximations, on which momentum is known to be effective [54]. Our analysis does not rely on such approximations.

## 2.1 Continuized Nesterov Algorithm

In this section, we describe the process studied in this work, and the resulting algorithm. An intuitive way to present the process is as follows: consider a sequence of random times $\{T_k\}_{k \in \mathbb{N}}$ such that $T_0 = 0$ and $T_{k+1} - T_k \stackrel{\text{i.i.d}}{\sim} \mathcal{E}(1)$ for $k \in \mathbb{N}$. For some constant parameters $\eta, \eta', \gamma, \gamma'$,
we define a continuous-time process $(x_t, z_t)_{t \in \mathbb{R}_+}$ on each interval $(T_k, T_{k+1})$ as the solution of the following equation

$$ \begin{cases} dx_t = \eta(z_t - x_t)dt, \\ dz_t = \eta'(x_t - z_t)dt. \end{cases} $$

At $t = T_k$, the process jumps by performing gradient steps,

$$ x_{T_k} = x_{T_k^{-}} - \gamma \nabla f(x_{T_k^{-}}), \quad z_{T_k} = z_{T_k^{-}} - \gamma' \nabla f(z_{T_k^{-}}). $$

This defines the *continuized Nesterov equation*. It can be written in a more compact form as the following stochastic differential equation

$$ \begin{cases} dx_t = \eta(z_t - x_t)dt - \gamma \nabla f(x_{t-})dN_t, \\ dz_t = \eta'(x_t - z_t)dt - \gamma' \nabla f(x_{t-})dN_t, \end{cases} \quad (CNE) $$

where $dN_t = \sum_{k \ge 0} \delta_{T_k}(dt)$ is a Poisson point measure with intensity $dt$. It mixes the continuous component, the $dt$ factor, with the gradient component that acts at discrete random times, the $dN_t$ factor. A remarkable property of (CNE) is that, upon defining the sequences $\tilde{y}_k := x_{T_{k+1}^{-}}$, $\tilde{x}_k := x_{T_k}$ and $\tilde{z}_k := z_{T_k}$, $k \in \mathbb{N}$, they satisfy a recursive relation that takes the form of a Nesterov momentum algorithm, with stochastic parameters depending on the random times $\{T_k\}_{k \in \mathbb{N}}$.

**Proposition 2.3** ([31], Proposition 5). Let $(x_t, z_t)_{t \in \mathbb{R}_+}$ follow (CNE) with $\eta + \eta' > 0$ and with underlying jumping times $\{T_k\}_{k \in \mathbb{N}}$. Define $\tilde{y}_k := x_{T_{k+1}^{-}}$, $\tilde{x}_{k+1} := x_{T_{k+1}}$ and $\tilde{z}_{k+1} := z_{T_{k+1}}$ as evaluations of this process. Then, $(\tilde{y}_k, \tilde{x}_k, \tilde{z}_k)$ writes as the following continuized Nesterov algorithm (CNA)

$$ \left\{ \begin{aligned} \tilde{y}_k &= \frac{\eta}{\eta+\eta'} \left(1 - e^{-(\eta+\eta')(T_{k+1}-T_k)}\right) (\tilde{z}_k - \tilde{x}_k) + \tilde{x}_k \\ \tilde{x}_{k+1} &= \tilde{y}_k - \gamma \nabla f(\tilde{y}_k) \\ \tilde{z}_{k+1} &= \tilde{z}_k + \eta' \frac{(1-e^{-(\eta+\eta')(T_{k+1}-T_k)})}{\eta'+\eta e^{-(\eta+\eta')(T_{k+1}-T_k)}} (\tilde{y}_k - \tilde{z}_k) - \gamma' \nabla f(\tilde{y}_k) \end{aligned} \right. \quad (CNA) $$

In words, (CNA) is an exact evaluation of a realization of (CNE). Intuitively, exact access to the continuous process (CNE) is possible because gradient information is only queried at discrete times. Because the random times $\{T_k\}_{k \in \mathbb{N}}$ can be readily simulated, (CNA) is implementable. This direct correspondence between (CNA) and (CNE) is powerful: it enables convergence guarantees for a discrete algorithm to be derived via continuous-time analysis. This comes at the cost that even with deterministic gradients, the resulting algorithm is inherently stochastic, thus leading to non-deterministic convergence guarantees.

**On the formulation of the algorithm** (CNA) is a three-point formulation of Nesterov's algorithm, contrasting with the two-point formulation of (NM). These two formulations are related, see [33, Appendix B.2]

# 3 Convergence Result without Lipschitz Hessian Assumption

We derive a convergence result under Assumption 2.1 only, illustrating the near-automatic transfer from continuous to discrete time. This intermediate result serves as a key building block for proving our main theorem in the Lipschitz Hessian setting (Theorem 4.2).

**Lemma 3.1.** If $(x_t, z_t)$ is solution of (CNE) under Assumption 2.1 with $\gamma \le \frac{1}{L}$, $\gamma' = \gamma + \sqrt{\frac{\gamma}{2}}$, $\eta = \gamma' - \gamma$ and $\eta' \ge -\eta$, we have

$$ \mathbb{E} \left[ \int_{0}^{t} (\eta + \eta') \|x_s - z_s\|^2 + \frac{\gamma}{4} \|\nabla f(x_s)\|^2 ds \right] \le \mathbb{E} [f(x_0) - f^*]. \quad (2) $$
From Lemma 3.1, it follows that $\mathbb{E}[\min_{s \in [0, t]} \|\nabla f(x_s)\|^2] = \mathcal{O}(1/t)$. Its proof relies on stochastic continuous Lyapunov analysis, see Appendix E. A similar result is obtained under Assumption 2.1 for a continuous system in [46, Proposition 6], but with a different dynamic from (CNE), specifically adapted to asynchronous algorithms. Because $\tilde{x}_k$ in (CNA) is exactly $x_t$ in (CNE) evaluated at the time $T_k$, one can transfer the convergence result of Lemma 3.1 to the discrete case without any new discrete Lyapunov analysis.

**Proposition 3.2.** Assume $T_1, \dots, T_k$ are random variables such that $T_{i+1} - T_i$ are i.i.d of law $\mathcal{E}(1)$, with convention $T_0 = 0$. Under Assumption 2.1, iterations of (CNA) with $\gamma \le \frac{1}{L}$, $\gamma' = \gamma + \sqrt{\frac{\gamma}{2}}$, $\eta = \sqrt{\frac{\gamma}{2}}$ and $\eta' > -\eta$ verify

$$ \mathbb{E} \left[ \min_{0 \le i \le k-1} \| \nabla f(\tilde{y}_i) \|^2 \right] \le \frac{4}{\gamma} \frac{(f(x_0) - f^*)}{k}. \quad (3) $$

*Sketch of Proof.* From the proof of Lemma 3.1, it follows that for a martingale $U_t$ verifying $\mathbb{E}[U_t] = 0$, we have for $t \in \mathbb{R}_+$

$$ \int_0^t \frac{\gamma}{4} \| \nabla f(x_{s-}) \|^2 dN_s \le f(x_0) - f^* + U_t. $$

Evaluating this equation at $t = T_k$ and ensuring $\mathbb{E}[U_{T_k}] = 0$, we obtain

$$ \mathbb{E} \left[ \sum_{i=1}^{k} \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] \stackrel{(i)}{=} \mathbb{E} \left[ \int_0^{T_k} \frac{\gamma}{4} \left\| \nabla f(x_{s-}) \right\|^2 dN_s \right] \le f(x_0) - f^*, $$

where (i) is by definition of Poisson integrals. It remains to use Proposition 2.3 and the elementary fact that $\sum_{i=1}^k a_i \ge k \min_{1 \le i \le k} a_i$ for any set of real numbers $\{a_i\}_{i=1}^k$. $\square$

Technical details are deferred to Appendix E. Proposition 3.2 implies that we find, in expectation, a $\varepsilon$-stationary point in at most $\mathcal{O}(\varepsilon^{-2})$ gradient evaluations. This is a new result for the continuous algorithm (CNA), which shows it recovers the known bound of the classical Nesterov momentum algorithms in this setting, see [25].

# 4 Main Result under Lipschitz Hessian Assumption

Authors of [53] show that under Assumptions 2.1 and 2.2, if $(x_t)_{t \ge 0}$ satisfies the Heavy Ball equation (HB)

$$ \ddot{x}_t + \alpha \dot{x}_t + \nabla f(x_t) = 0, \quad (\text{HB}) $$

with $\alpha = \mathcal{O}(T^{-1/7})$, then defining for $t \ge 0$ the following average

$$ \bar{x}_t = \int_0^t w_t(s) x_s ds \quad (4) $$

with $w_t(s) := \frac{\alpha e^{\alpha s}}{e^{\alpha t} - 1}$, one has

$$ \min_{0 \le t \le T} \| \nabla f(\bar{x}_t) \| = \mathcal{O}(T^{-4/7}). \quad (5) $$

Fixing $\varepsilon > 0$, (5) implies that we find a point $\hat{x}$ such that $\|\nabla f(\hat{x})\| \le \varepsilon$ in at most $\mathcal{O}(\varepsilon^{-7/4})$ running time. This can be seen as a continuous version of the $\mathcal{O}(\varepsilon^{-7/4})$ bound on the number of iterations of a given algorithm. In the next section, we draw inspiration from their analysis to derive a result in the discrete setting using the continuous method.

## 4.1 Convergence Result

We first introduce the following definition, used to state our main convergence result.
**Definition 4.1.** For some $n \in \mathbb{N}^*$ and $C, \alpha > 0$, we note

$$ \mathcal{A}_n := \{ \forall i \in \{1, \dots, n\}, H_0^i \le C \mathbb{E}[H_0^i], H_1^i \le C \mathbb{E}[H_1^i], H_2^i \le C \alpha^{-1} \mathbb{E}[H_2^i] \}, $$

where for $\{T_k\}_{k \in \{1, \dots, n\}}$ such that $T_{i+1} - T_i \stackrel{i.i.d}{\sim} \mathcal{E}(1)$, we define

$$ H_0^i := \sum_{j=1}^{i} (T_i - T_j) e^{-\alpha(T_i - T_j)}, \quad H_1^i := \sum_{j=1}^{i} e^{-\alpha(T_i - T_j)}, \quad H_2^i := \sum_{j=1}^{i} (i-j) e^{-\alpha(T_i - T_j)}. $$

Definition 4.1 introduces the set of realizations on which our convergence result holds. Before commenting on it, we state our main result.

**Theorem 4.2.** For $\{T_k\}_{k \in \mathbb{N}}$ such that $T_0 = 0$, $T_{k+1} - T_k \stackrel{i.i.d}{\sim} \mathcal{E}(1)$, denote $dN_t = \sum_{k \ge 1} \delta_{T_k}(dt)$. Under Assumptions 2.1-2.2, iterations of (CNA) with $\gamma \le \frac{1}{L}$, $\gamma' = \gamma + \sqrt{\frac{\gamma}{2}}$, $\eta = \sqrt{\frac{\gamma}{2}}$ and $\eta' = n^{-1/7} - \sqrt{\frac{\gamma}{2}}$ with $n \ge 8$ ensure

$$ \mathbb{E} \left[ \mathbb{1}_{\mathcal{A}_n} \min_{k \in \{1, \dots, n\}} \| \nabla f(\bar{x}_k) \| \frac{\Delta_n}{\mathbb{E}[\Delta_n]} \right] = \mathcal{O}(n^{-4/7}), \quad (6) $$

where for $\alpha = n^{-1/7}$, we note $\Delta_n = \int_0^{T_n} \left( \int_0^t \alpha e^{\alpha(s-t)} dN_s \right)^2 dN_t$, $\bar{x}_k = \sum_{i=1}^k \lambda_{i,k} \tilde{y}_i$ with $\lambda_{i,k} = \frac{e^{\alpha T_i}}{\sum_{j=1}^k e^{\alpha T_j}}$, and $\mathcal{A}_n$ is defined in Definition 4.1.

See (17) for an explicit formulation of (6). For some precision $\varepsilon > 0$, it implies that we get a point $\tilde{x}$ such that $\mathbb{E}[\mathbb{1}_{\mathcal{A}_n} \|\nabla f(\tilde{x})\|_{\mathbb{E}[\Delta_n]}] \le \varepsilon$ in at most $\mathcal{O}(\varepsilon^{-7/4})$ gradient evaluations. We recall that (CNA) only depends on gradient steps and momentum, and does not involve negative curvature exploitation, restart mechanism, or other supplementary mechanisms.

**Limitations of Theorem 4.2** The presence of the factors $\mathbb{1}_{\mathcal{A}_n}$ and $\Delta_n/\mathbb{E}[\Delta_n]$ in Theorem 4.2 are clear limitations of our result. In particular, providing an explicit lower bound on the measure of $\mathcal{A}_n$ that does not depend on $n$ appears challenging. Importantly, for $j \in \{0, 1, 2\}$ and $i \in \{1, \dots, n\}$, the random variable $H_j^i$ does not depend on $f$, but only depends on the sequence $\{T_k\}_{k \in \{1, \dots, i\}}$. Since for $k_1 \ge k_0$ we have $T_{k_1} - T_{k_0} \sim \Gamma(k_1 - k_0, 1)$, understanding the set $\mathcal{A}_n$ reduces to analyzing specific properties of Gamma distributions. Owing to this independence from $f$, numerical simulations provide strong evidence that, for any choice of functions, the probability of $\mathcal{A}_n$ remains close to 1, with a choice of constant $C$ independent of the number of iterations $n$, see Figure 1(a)-(c) for the choice $C = 5$. Additional histograms illustrating the empirical distributions of these quantities for different values of $n$ are provided in Appendix B.1. Similarly, the ratio $\Delta_n/\mathbb{E}[\Delta_n]$ does not depend on the function and is observed to be close to 1, see Figure 1(d). These empirical findings suggest that these limitations may be removable, which we leave as an interesting direction for future work.

**Comparison with existing results** The geometrical constants appearing in the bound of Theorem 4.2 differ from those in existing works. Under Assumption 2.1 and 2.2, taking into account logarithmic factors, the best complexity is $\mathcal{O}(\Delta_f L^{1/2} L_2^{1/4} \varepsilon^{-7/4})$ [42]. From (17), noting $\Delta_f := f(x_0) - f^*$ our bound implies a decrease of order $(\sqrt{L\Delta_f} + (L_2/L_1)\Delta_f)n^{-7/4}$. As a consequence, in expectation and up to the limitation discussed above, an $\varepsilon$-stationary point is reached in at most $\mathcal{O}(\max\{L^{7/8}\Delta_f^{7/8} + (L_2/L)^{7/4}\Delta_f^{7/4}\}\varepsilon^{-7/4})$ iterations. If $L_2/L \ll 1$, this simplifies to $\mathcal{O}(L^{7/8}\Delta_f^{7/8}\varepsilon^{-7/4})$. Compared with [42], if $L \ge 1$ our dependence on $\Delta_f$ is slightly better, but our dependence on $L$ is worse. When the term $(L_2/L)^{7/4}\Delta_f^{7/4}$ is not negligible, the comparison is less clear-cut. Finally, while the analysis of [53] requires knowledge of the terminal time $T$ to tune parameters in the continuous setting, our result uses the final iteration $n$ to tune $\eta'$ in Theorem 4.2. This dependence might be removed by using an iteration-dependent schedule $\eta'_k = k^{-1/7} - \sqrt{\gamma/2}$, at the cost of significant additional technical complexity. In a similar way, most existing methods for finding a $\varepsilon$-stationary point involve $\varepsilon$-depending parameters [14, 37, 42], with the notable exception of the parameter-free restart method of [43].
<figure><img src="image_2.png" /><figcaption>Figure 1: For 100 realizations of sequences {$T_k$}$_{k \in \{1,...,10000\}}$, (a) shows the evolution of the max over all the realizations of $H_0^i - 5\mathbb{E}[H_0^i]$, similarly in (b) and (c), for $H_1^i - 5\mathbb{E}[H_1^i]$ and $H_2^i - 5\mathbb{E}[H_2^i]$, see Definition 4.1. All the realizations belong to $\mathcal{A}_n$, and it is even more pronounced as $n$ is larger. For 100 realizations of sequences {$T_k$}$_{k \in \{1,...,1000\}}$, (d) shows the evolution of $\Delta_n/\mathbb{E}[\Delta_n]$, see its definition in Theorem 4.2. The min, max, and mean are taken at each iteration among all the realizations. Observe that the ratio concentrates around 1.</figcaption></figure>

## 5 Outline of the proof of Theorem 4.2

This section provides a proof outline of Theorem 4.2, with most technical details deferred to the appendix. We recall that $(x_t, z_t)_{t \in \mathbb{R}_+}$ are defined as follows

$$ \begin{cases} dx_t = \eta(z_t - x_t)dt - \gamma \nabla f(x_{t-})dN_t, \\ dz_t = \eta'(x_t - z_t)dt - \gamma' \nabla f(x_{t-})dN_t, \end{cases} \quad (CNE) $$

with $dN_t = \sum_{k \ge 1} \delta_{T_k}(dt)$ for {$T_k$}$_{k \in \mathbb{N}}$ a sequence of random variable satisfying $T_{k+1} - T_k \stackrel{i.i.d}{\sim} \mathcal{E}(1)$, with convention $T_0 = 0$. Throughout the proof, we note $\alpha := \eta + \eta'$ and use the shorthand notation $\int_0^t := \int_{[0,t]}$ to save space. Inspired from the averaging (4) of [53], we consider a Poisson-average trajectory of $x_t$

$$ \bar{x}_t := \int_0^t w_t(s)x_s - dN_s, \quad (7) $$

where we set $w_t(s) = \frac{\alpha e^{\alpha s}}{\int_0^t \alpha e^{\alpha s'} dN(s')}$. To readers unfamiliar with Poisson processes, we emphasize that Poisson integrals are stochastic sums, namely

$$ \int_0^t w_t(s) x_s - dN_s = \sum_{i=1}^{N_t} w_t(T_i^-) x_{T_i^-}, $$

where $N_t = \sum_{k \ge 1} 1_{T_k \le t} \sim \mathcal{P}(t)$. In particular, at $t = T_n$, by definition $N_{T_n} = n$ and the number of terms in the sum is fixed, becoming $\sum_{i=1}^n w_t(T_i^-) x_{T_i^-}$. To ensure $\int_0^t w_t(s) dN_s = 1$, we assume $N_t \ge 1$ (otherwise the integral is zero). This is not a restriction, because $N_t < 1$ would imply no jumps occurred, i.e. the underlying algorithm has not started yet.

Ultimately, our goal is to obtain control of the norm of the gradient of the average (7), namely of $\|\nabla f(\bar{x}_t)\|$. The Lipschitz Hessian property (Assumption 2.2) allows us to control the distance of $\nabla f(\bar{x}_t)$ to a quantity of interest: the average of the gradient.
**Lemma 5.1.** Let $(x_t, z_t)_{t \in \mathbb{R}_+}$ be solution of (CNE). Under Assumption 2.2, we have

$$ \left\| \int_0^t w_t(s) \nabla f(x_{s-}) dN_s - \nabla f(\bar{x}_t) \right\| \le L_2 \int_0^t \eta \|z_s - x_s\|^2 \left( \int_s^t \int_0^s w_t(\sigma) w_t(\tau) (\tau - \sigma) dN_\sigma dN_\tau \right) ds \quad (8) $$

$$ + L_2 \int_0^t \gamma^2 \|\nabla f(x_{s-})\|^2 \left( \int_s^t \int_0^s w_t(\sigma) w_t(\tau) (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau \right) dN_s. \quad (9) $$

Lemma 5.1 is a continuized-adapted version of Lemma 1 in [53], the difference in our analysis mainly coming from the Poisson process and the fact that (CNE) is a two-trajectory system, in contrast with the Heavy Ball equation (HB), see the proof in Appendix C.1. The quantities $\|z_s - x_s\|^2$ and $\|\nabla f(x_{s-})\|^2$ appearing in (8) and (9) are interesting. Indeed, as showed in Section 3, the Lipschitz gradient property (Assumption 2.1) allows us to have controls such as (2), namely

$$ \mathbb{E} \left[ \int_0^t (\eta + \eta') \|x_s - z_s\|^2 + \frac{\gamma}{4} \|\nabla f(x_s)\|^2 ds \right] \le \mathbb{E} [f(x_0) - f^*]. \quad (10) $$

In contrast, we do not have direct control of $\int_0^t w_t(s) \nabla f(x_{s-}) dN_s$. However, because of the choice of averaging $w_s(\cdot)$ and the definition of (CNE), a stochastic integration by parts formula reduces it to a more tractable quantity.

**Lemma 5.2.** If $(x_t, z_t)_{t \in \mathbb{R}_+}$ is solution of (CNE), for $t > 0$ we have

$$ \int_0^t w_t(s) \nabla f(x_{s-}) dN_s = - \frac{w_t(t)(z_t - x_t)}{\gamma' - \gamma}. \quad (11) $$

See the proof in Appendix C.2. An integration by parts argument is also used in [53, Equation 18], for the Heavy Ball ODE (HB). In our case, the stochastic nature of the process requires some care when using such arguments.

Combining Lemmas 5.1 and 5.2 and using a triangular inequality yields the following upper bound

$$ \|\nabla f(\bar{x}_t)\| \le \frac{w_t(t) \|z_t - x_t\|}{\gamma' - \gamma} + L_2 \int_0^t \eta \|z_s - x_s\|^2 \left( \int_s^t \int_0^s w_t(\sigma) w_t(\tau) (\tau - \sigma) dN_\sigma dN_\tau \right) ds + L_2 \int_0^t \gamma^2 \|\nabla f(x_{s-})\|^2 \left( \int_s^t \int_0^s w_t(\sigma) w_t(\tau) (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau \right) dN_s. $$

This bound is nonetheless not sufficient to use our controls of Section 3. So, we integrate between $t = 0$ and $t = T_n$ the above inequality, after multiplication of each side by a proper quantity.

**Lemma 5.3.** Noting $\Lambda_t := (\int_0^t \alpha e^{\alpha(s-t)} dN_s)^2$, for $(x_t, z_t)_{t \in \mathbb{R}_+}$ solution of (CNE) under Assumption 2.2, we have

$$ \int_0^{T_n} \Lambda_t \|\nabla f(\bar{x}_t)\| dN_t \le \frac{1}{\gamma' - \gamma} \int_0^{T_n} \Lambda_t w_t(t) \|z_t - x_t\| dN_t \\ + \alpha^2 \eta^2 L_2 \int_0^{T_n} \|z_s - x_s\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau - \sigma) dN_\sigma dN_\tau dN_t \right) ds \quad (12) \\ + \alpha^2 \gamma^2 L_2 \int_0^{T_n} \|\nabla f(x_{s-})\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau dN_t \right) dN_s. $$

See the proof in Appendix C.3. A satisfying control of the first term of the right-hand side of (12) will follow from the Cauchy-Schwartz inequality and from a similar control as (10) evaluated
at $t = T_n$. The two other terms are particularly challenging. When using the classic deterministic (HB) equation, the analogue of the triple integrals inside the parentheses can be directly computed [53]. In our case, if the expectation of these triple integrals can be computed, the expectation of the full expression cannot be separated. To control these two terms, we restrict ourselves to a subset of the realizations.

**Lemma 5.4.** For some $C > 0$, let $\mathcal{A}_n$ as in Definition 4.1. Then

1. Noting $A_k := \int_{[T_k, T_n]} \int_{[T_k, t]} \int_{[0, T_k]} e^{\alpha(T_k-t)} e^{\alpha(\tau-t)} e^{\alpha(\sigma-T_k)} (\tau - \sigma) dN_\sigma dN_\tau dN_t$, we have

$$ 
\begin{aligned}
& \mathbb{E} \left[ 1_{\mathcal{A}_n} \int_0^{T_n} \eta^2 \|z_s - x_s\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau - \sigma) dN_\sigma dN_\tau dN_t \right) ds \right] \\
& \le C \max_{k \in \{1, \dots, n\}} \mathbb{E}[A_k] \mathbb{E} \left[ \int_0^{T_n} \eta^2 \|z_s - x_s\|^2 ds \right]
\end{aligned}
\quad (13) $$

2. Noting $B_k := \int_{T_k}^{T_n} \int_{T_k}^{t} \int_{0}^{T_k} e^{\alpha(\tau-t)} e^{\alpha(T_k-t)} e^{\alpha(\sigma-T_k)} (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau dN_t$, we have

$$ 
\begin{aligned}
& \mathbb{E} \left[ 1_{\mathcal{A}_n} \int_0^{T_n} \gamma^2 \|\nabla f(x_{s-})\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau dN_t \right) dN_s \right] \\
& \le C \alpha^{-1} \max_{k \in \{1, \dots, n\}} \mathbb{E}[B_k] \mathbb{E} \left[ \int_0^{T_n} \gamma^2 \|\nabla f(x_{s-})\|^2 dN_s \right]
\end{aligned}
\quad (14) $$

Intuitively, the crux of the proof of Lemma 5.4 is to isolate simple conditions, formalized with the definition of $\mathcal{A}_n$, that allow us to separate the expectation of the triple integrals from the expectation of the trajectory-dependent quantities, see Appendix C.4.

Combining Lemma 5.3 with Lemma 5.4, in which we bound $\max_{k \in \{1, \dots, n\}} \mathbb{E}[A_k]$ and $\max_{k \in \{1, \dots, n\}} \mathbb{E}[B_k]$, and using Lyapunov controls, we obtain our final lemma, whose proof is stated in Appendix C.5.

**Lemma 5.5.** Under Assumptions 2.1 and 2.2, let $(x_t, z_t)_{t \in \mathbb{R}_+}$ be solution of (CNE) with $\gamma \le \frac{1}{L}$, $\gamma' = \gamma + \sqrt{\frac{\gamma}{2}}$, $\eta = \sqrt{\frac{\gamma}{2}}$ and $\eta' \ge -\eta$. Then, we have

$$ 
\begin{aligned}
& \mathbb{E} \left[ 1_{\mathcal{A}_n} \int_0^{T_n} \left( \int_0^t \alpha e^{\alpha(s-t)} dN_s \right)^2 \|\nabla f(\bar{x}_t)\| dN_t \right] \\
& \le \sqrt{\alpha n} \sqrt{\frac{C_\alpha}{\gamma}} \sqrt{f(x_0) - f^*} \\
& \quad + \frac{CL_2\gamma}{\alpha^3} D_\alpha(f(x_0) - f^*),
\end{aligned}
\quad (15) $$

with $\mathcal{A}_n$ as in Definition 4.1, $C_\alpha := 6(1 + \frac{3}{2}\alpha)(1 + 2\alpha)$ and $D_\alpha := \frac{1}{2}(1 + 2\alpha)^4(1 + 8(1 + 2\alpha))$.

Using Lemma 5.5, we now conclude the proof. We have

$$ 
\begin{aligned}
& \mathbb{E} \left[ 1_{\mathcal{A}_n} \min_{t \in \{T_1, \dots, T_n\}} \|\nabla f(\bar{x}_t)\| \int_0^{T_n} \left( \int_0^t \alpha e^{\alpha(s-t)} dN_s \right)^2 dN_t \right] \\
& \le \mathbb{E} \left[ 1_{\mathcal{A}_n} \int_0^{T_n} \left( \int_0^t \alpha e^{\alpha(s-t)} dN_s \right)^2 \|\nabla f(\bar{x}_t)\| dN_t \right] \\
& \stackrel{(15)}{\le} \sqrt{\alpha n} \sqrt{\frac{C_\alpha}{\gamma}} \sqrt{f(x_0) - f^*} + \frac{CL_2\gamma}{\alpha^3} D_\alpha(f(x_0) - f^*) \\
& = \sqrt{\frac{6(1 + \frac{3}{2})}{\gamma}} n^{\frac{3}{2}} \sqrt{f(x_0) - f^*} + \frac{25}{2} \cdot 3^4 CL_2\gamma n^{\frac{3}{2}} (f(x_0) - f^*).
\end{aligned}
\quad (16) $$

The last equality in (16) is obtained by fixing $\alpha = n^{-1/7}$, which implies $\eta' = n^{-1/7} + \sqrt{\gamma/2}$ as $\alpha = \eta + \eta'$. It follows that $\alpha \le 1$, which in turn implies

$$ C_\alpha = 18 \left(1 + \frac{3}{2}\alpha\right) (1 + 2\alpha) \le 6 \left(1 + \frac{3}{2}\right), \quad D_\alpha = \frac{1}{2}(1 + 2\alpha)^4 (1 + 8(1 + 2\alpha)) \le \frac{25}{2} \cdot 3^4. $$
Dividing each side of (16) by $\mathbb{E}[\Delta_n]$, using Lemma D.5-(ii), and still using the notation $\alpha = n^{-1/7}$, we deduce for $n \ge 8$

$$ 
\begin{aligned}
& \mathbb{E} \left[ \mathbb{1}_{A_n} \min_{t \in \{T_1, \dots, T_n\}} \| \nabla f(\bar{x}_t) \| \frac{\Delta_n}{\mathbb{E}[\Delta_n]} \right] \\
& \le n^{-\frac{4}{7}} \frac{3 \sqrt{\frac{2(1+\frac{3}{2})}{\gamma}} \sqrt{f(x_0) - f^*} + \frac{25}{2} \cdot 3^4 CL_2 \gamma (f(x_0) - f^*)}{\frac{(2+\alpha)(1+2\alpha)}{2} + \frac{(1+2\alpha)(1+\frac{3}{2}\alpha)}{2} (1 - (1+2\alpha)^{-n}) n^{-\frac{6}{7}} - 2(1+\alpha)(1+2\alpha)(1 - (1+\alpha)^{-n}) n^{-\frac{6}{7}}} \\
& \le n^{-\frac{4}{7}} \left( 6 \sqrt{\frac{2(1+\frac{3}{2})}{\gamma}} \sqrt{f(x_0) - f^*} + \frac{25}{2} \cdot 3^4 CL_2 \gamma (f(x_0) - f^*) \right) \\
& = \mathcal{O}(n^{-4/7}).
\end{aligned}
\tag{17} $$

The assumption $n \ge 8$ allows to have the precise control (i) of the denominator, see Appendix C.6. It finally remains to show that the point $\arg\min_{t=\{T_1, \dots, T_n\}} \|\nabla f(\bar{x}_t)\|$ can be outputted by our algorithm. We have

$$ \bar{x}_k := \bar{x}_{T_k} = \int_{[0, T_k]} w_{T_k}(s) x_{s-dN}s = \sum_{i=1}^{k} w_{T_k}(T_i) x_{T_i^{-}} = \sum_{i=1}^{k} w_{T_k}(T_i) \tilde{y}_i, $$

using $x_{T_i^{-}} = \tilde{y}_i$ by Proposition 2.3. Also, recall that $w_t(s) = \frac{e^{\alpha s}}{\int_0^t e^{\alpha s} dN_s}$, such that we fix

$$ \lambda_{i,k} := w_{T_k}(T_i) = \frac{e^{\alpha T_i}}{\sum_{j=1}^{k} e^{T_j}}. $$

So, the convergence results holds for the computable point $\tilde{x}$ defined as follows

$$ \tilde{x} := \arg\min_{k=\{1, \dots, n\}} \|\nabla f(\bar{x}_k)\|, \text{ where } \bar{x}_k = \sum_{i=1}^{k} \lambda_{i,k} \tilde{y}_i, $$

## Acknowledgment

This work was supported by PEPR PDE-AI.

## References

[1] Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In *Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing*, page 1195–1199, 2017.

[2] Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. *Journal of Machine Learning Research*, 18(221):1–51, 2018.

[3] Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. *Advances in Neural Information Processing Systems*, 31, 2018.

[4] Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. In *8th Innovations in Theoretical Computer Science Conference (ITCS 2017)*, volume 67, pages 3:1–3:22, 2017.

[5] Hedy Attouch and Alexandre Cabot. Convergence rates of inertial forward-backward algorithms. *SIAM Journal on Optimization*, 28(1):849–874, 2018.

[6] Jean-François Aujol, Charles Dossal, and Aude Rondepierre. Optimal convergence rates for Nesterov acceleration. *SIAM Journal on Optimization*, 29(4):3131–3153, 2019.
[7] Jean-François Aujol, Charles Dossal, and Aude Rondepierre. Convergence rates of the Heavy-Ball method under the łojasiewicz property. *Mathematical Programming*, 198(1):195–254, 2023.

[8] Afonso S Bandeira, Nicolas Boumal, and Vladislav Voroninski. On the low-rank approach for semidefinite programs arising in synchronization and community detection. In *Conference on learning theory*, pages 361–382. PMLR, 2016.

[9] Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. *SIAM journal on imaging sciences*, 2(1):183–202, 2009.

[10] Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery. *Advances in Neural Information Processing Systems*, 29, 2016.

[11] Nicolas Boumal, Vlad Voroninski, and Afonso Bandeira. The non-convex burer-monteiro approach works on smooth semidefinite programs. *Advances in Neural Information Processing Systems*, 29, 2016.

[12] Sébastien Bubeck, Yin Tat Lee, and Mohit Singh. A geometric alternative to nesterov's accelerated gradient descent. *arXiv preprint arXiv:1506.08187*, 2015.

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

[14] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. "convex until proven guilty": Dimension-free acceleration of gradient descent on non-convex functions. In *International conference on machine learning*, pages 654–663. PMLR, 2017.

[15] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. *SIAM Journal on Optimization*, 28(2):1751–1772, 2018.

[16] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. *Mathematical Programming*, 184(1-2):71–120, 2020.

[17] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. *Mathematical Programming*, 185(1):315–355, 2021.

[18] Antonin Chambolle and Charles H Dossal. On the convergence of the iterates of "fista". *Journal of Optimization Theory and Applications*, 166(3):25, 2015.

[19] Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In *Artificial intelligence and statistics*, pages 192–204. PMLR, 2015.

[20] Marina Danilova, Pavel Dvurechensky, Alexander Gasnikov, Eduard Gorbunov, Sergey Guminov, Dmitry Kamzolov, and Innokentiy Shibaev. Recent theoretical advances in non-convex optimization. In *High-Dimensional Optimization and Probability: With a View Towards Data Science*, pages 79–163. Springer, 2022.

[21] Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. *Advances in neural information processing systems*, 27, 2014.

[22] Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Hadrien Hendrikx, Pierre Gaillard, Laurent Massoulié, and Adrien Taylor. Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms. *Advances in Neural Information Processing Systems*, 34:28054–28066, 2021.

[23] Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In *International conference on machine learning*, pages 1233–1242. PMLR, 2017.
[24] Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. *Advances in neural information processing systems*, 29, 2016.

[25] Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. *Mathematical Programming*, 156(1):59–99, 2016.

[26] Baptiste Goujaud, Adrien Taylor, and Aymeric Dieuleveut. Optimal first-order methods for convex functions with a quadratic upper bound. *arXiv preprint arXiv:2205.15033*, 2022.

[27] Baptiste Goujaud, Adrien Taylor, and Aymeric Dieuleveut. Provable non-accelerations of the heavy-ball method. *arXiv preprint arXiv:2307.11291*, 2023.

[28] Kanan Gupta, Jonathan W Siegel, and Stephan Wojtowytsch. Nesterov acceleration despite very noisy gradients. In *The Thirty-eighth Annual Conference on Neural Information Processing Systems*, 2024.

[29] Moritz Hardt. Understanding alternating minimization for matrix completion. In *2014 IEEE 55th Annual Symposium on Foundations of Computer Science*, pages 651–660. IEEE, 2014.

[30] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pages 770–778, 2016.

[31] Julien Hermant, Jean-François Aujol, Charles Dossal, Lorick Huang, and Aude Rondepierre. Continuized nesterov acceleration for non-convex optimization. *arXiv preprint arXiv:2512.16533*, 2025.

[32] Julien Hermant, Jean-François Aujol, Charles Dossal, and Aude Rondepierre. Study of the behaviour of nesterov accelerated gradient in a non convex setting: the strongly quasar convex case. *arXiv preprint arXiv:2405.19809*, 2024.

[33] Julien Hermant, Marien Renaud, Jean-François Aujol, Charles Dossal, and Aude Rondepierre. Gradient correlation is a key ingredient to accelerate sgd with momentum. In *The Thirteenth International Conference on Learning Representations*, 2025.

[34] Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In *Conference on learning theory*, pages 1894–1938. PMLR, 2020.

[35] Geoffrey Hinton. Neural networks for machine learning. Coursera Lecture 6e, 2012. Available at https://www.coursera.org/learn/neural-networks.

[36] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In *International conference on machine learning*, pages 1724–1732. PMLR, 2017.

[37] Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In *Conference On Learning Theory*, pages 1042–1085. PMLR, 2018.

[38] Kenji Kawaguchi. Deep learning without poor local minima. *Advances in neural information processing systems*, 29, 2016.

[39] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In *International Conference on Learning Representations*, 2015.

[40] Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In *Conference on learning theory*, pages 1246–1257. PMLR, 2016.

[41] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. *Advances in neural information processing systems*, 31, 2018.
[42] Huan Li and Zhouchen Lin. Restarted nonconvex accelerated gradient descent: No more polylogarithmic factor in the o(ε⁻⁷/⁴) complexity. *Journal of Machine Learning Research*, 24(157):1–37, 2023.

[43] Naoki Marumo and Akiko Takeda. Parameter-free accelerated gradient descent for nonconvex minimization. *SIAM J. Optim.*, 34:2093–2120, 2022.

[44] Naoki Marumo and Akiko Takeda. Universal heavy-ball method for nonconvex optimization under hölder continuous hessians. *Mathematical Programming*, 212(1):147–175, 2025.

[45] Song Mei, Theodor Misiakiewicz, Andrea Montanari, and Roberto Imbuzeiro Oliveira. Solving sdps for synchronization and maxcut problems via the grothendieck inequality. In *Conference on learning theory*, pages 1476–1515. PMLR, 2017.

[46] Adel Nabli, Eugene Belilovsky, and Edouard Oyallon. A²CiD²: Accelerating Asynchronous Communication in Decentralized Deep Learning. *Advances in Neural Information Processing Systems*, 36:47451–47474, 2023.

[47] Adel Nabli and Edouard Oyallon. Dadao: Decoupled accelerated decentralized asynchronous optimization. In *International Conference on Machine Learning*, pages 25604–25626. PMLR, 2023.

[48] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. *Wiley-Interscience*, 1983.

[49] Yurii Nesterov. A method for solving the convex programming problem with convergence rate o(1/k²). In *Dokl akad nauk Sssr*, volume 269, page 543, 1983.

[50] Yurii Nesterov. Introductory lectures on convex optimization. applied optimization, 2004.

[51] Yurii Nesterov. *Lectures on convex optimization*, volume 137. Springer, 2018.

[52] Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. *Mathematical programming*, 108(1):177–205, 2006.

[53] Kaito Okamura, Naoki Marumo, and Akiko Takeda. Heavy-ball differential equation achieves $O(\epsilon^{-7/4})$ convergence for nonconvex functions. *arXiv preprint arXiv:2406.06100*, 2024.

[54] Michael O’Neill and Stephen J Wright. Behavior of accelerated gradient methods near critical points of nonconvex functions. *Mathematical Programming*, 176(1):403–427, 2019.

[55] Boris Polyak. Some methods of speeding up the convergence of iteration methods. *USSR Computational Mathematics and Mathematical Physics*, 4(5):1–17, 1964.

[56] Philip E Protter. Stochastic differential equations. In *Stochastic integration and differential equations*, pages 249–361. Springer, 2012.

[57] Marien Renaud, Julien Hermant, Deliang Wei, and Yu Sun. Provably accelerated imaging with restarted inertia and score-based image priors. *arXiv preprint arXiv:2510.07470*, 2025.

[58] Jonathan W Siegel. Accelerated first-order methods: Differential equations and lyapunov functions. *arXiv preprint arXiv:1903.05671*, 2019.

[59] Weijie Su, Stephen Boyd, and Emmanuel J. Candès. A differential equation for modeling nesterov’s accelerated gradient method: theory and insights. *Journal of Machine Learning Research*, 17(153):1–43, 2016.

[60] Tao Sun, Dongsheng Li, Zhe Quan, Hao Jiang, Shengguo Li, and Yong Dou. Heavy-ball algorithms always escape saddle points. *arXiv preprint arXiv:1907.09697*, 2019.

[61] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In *International Conference on Machine Learning*, pages 1139–1147, 2013.
[62] Jun-Kun Wang and Andre Wibisono. Continuized acceleration for quasar convex functions in non-convex optimization, 2023.

[63] Yi Xu, Rong Jin, and Tianbao Yang. First-order stochastic algorithms for escaping from saddle points in almost linear time. *Advances in neural information processing systems*, 31, 2018.

# A Complementary details to Section 1

## A.1 Accelerated gradient algorithms under convexity

A seminal work [55] shows that the heavy ball momentum algorithm

$$x_{n+1} = x_n + \alpha(x_n - x_{n-1}) - \beta \nabla f(x_n)$$

can significantly improve over the convergence speed of gradient descent when minimizing strongly convex quadratic functions. [49, 50] further shows (NM) ensures an acceleration result for L-smooth (strongly)-convex functions. As mentioned in Section 1, the corresponding bounds are optimal among all first-order algorithms [48, 51]. There exists a rich literature building upon these contributions. Far from being exhaustive, it includes new interpretations of the algorithms [12, 59, 4], extensions to the non-smooth case e.g. via composite proximal optimization [9, 18, 5], extensions to the stochastic gradient case [25, 2, 33], and acceleration results under relaxed geometrical assumptions [34, 7, 6]. To add some nuance, it is worth noting that even in the convex setting, inertial methods do not necessarily ensure accelerated convergence [26, 27].

## A.2 Second-order stationary points

We provide a rigorous statement of the notion of second-order ε-stationary point, mentioned in our introductory section. We then briefly comment on it.

**Definition A.1** (Second-order ε-stationary point, [52]). For a L₂-Lipschitz Hessian function f, x is a ε-second-order stationary point if

$$\|\nabla f(x)\| \le \varepsilon, \quad \lambda_{\min}(\nabla^2 f(x)) \ge -\sqrt{\varepsilon L_2}.$$

A second-order ε-stationary point approximates a second-order stationary point, namely a point x* such that

$$\|\nabla f(x^*)\| = 0, \quad \lambda_{\min}(\nabla^2 f(x^*)) \ge 0.$$

In particular, such points are ensured to avoid *strict saddle-points*, that is, stationary points such that $\lambda_{\min}(\nabla^2 f(x^*)) < 0$. The 1d function $x \mapsto x^3$ is a simple example of a function that has a second-order stationary point (in $x = 0$) that is not a local minimizer, thus called *non-strict saddle-points*. Hopefully, several works indicate that many applications are prevented from such pathological stationary points [19, 38, 8, 45, 11, 10, 24, 23].

## A.3 Detailed formulations of existing security check and alternative mechanisms

For completeness, we give detailed versions of existing algorithms that achieve the complexity $O(e^{-7/4})$. Algorithm 2 is a detailed version of an algorithm that performs a negative curvature step [37]. Algorithm 3 is a detailed version of an algorithm that uses a restart mechanism [42]. We make a few remarks:

* We chose to state Algorithm 2 as the version from [37] rather than the earlier one from [14], because of the significant length and trickiness of the latter.

* In its original statement, Algorithm 2 also involves a "stochastic perturbation step", used to find a ε-second-order stationary point (Definition A.1). Because we do not study this concept, we avoided this step in our presentation.
<caption>**Algorithm 2:** Negative curvature exploitation and Nesterov momentum - Detailed version [37]</caption>

Input: $x_0, \eta, \theta, \gamma, s, r, \mathcal{T}$
1 $v_0 \leftarrow 0$
2 for $t = 0, 1, \dots$ do
3 &nbsp;&nbsp;&nbsp;&nbsp;$y_t \leftarrow x_t + (1 - \theta)v_t$;
4 &nbsp;&nbsp;&nbsp;&nbsp;$x_{t+1} \leftarrow y_t - \eta \nabla f(y_t)$;
5 &nbsp;&nbsp;&nbsp;&nbsp;$v_{t+1} \leftarrow x_{t+1} - x_t$;
6 &nbsp;&nbsp;&nbsp;&nbsp;if $f(x_t) \le f(y_t) + \langle \nabla f(y_t), x_t - y_t \rangle - \frac{\gamma}{2} \|x_t - y_t\|^2$ then
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(x_{t+1}, v_{t+1}) \leftarrow \text{Negative-Curvature-Exploitation}(x_t, v_t, s)$
8 Negative-Curvature-Exploitation($x_t, v_t, s$)
9 &nbsp;&nbsp;&nbsp;&nbsp;if $\|v_t\| \ge s$ then
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x_{t+1} \leftarrow x_t$
11 &nbsp;&nbsp;&nbsp;&nbsp;else
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\delta = s \cdot v_t / \|v_t\|$;
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x_{t+1} \leftarrow \underset{x \in \{x_t + \delta, x_t - \delta\}}{\operatorname{argmin}} f(x)$
14 &nbsp;&nbsp;&nbsp;&nbsp;return $(x_{t+1}, 0)$;

* In the convergence result associated with Algorithm 3 [42, Theorem 1], the restart threshold is set to $B = \sqrt{\epsilon/L_2}$, where $\epsilon$ denotes the target accuracy and $L_2$ is the Lipschitz constant of the Hessian. As noted by the authors, this value of $B$ can be very small in practice, causing the algorithm to restart at nearly every iteration. In such cases, the method effectively reduces to standard gradient descent, which eliminates the practical benefit of momentum. This behavior is confirmed by numerical experiments, showing little to no empirical acceleration due to the near absence of momentum steps.

To address this issue, the authors propose an alternative restart scheme [42, Algorithm 2], in which restarts are allowed to occur less frequently. While keeping $B = \sqrt{\epsilon/L_2}$, the user is permitted to initialize a larger value $B_0$, potentially satisfying $B_0 \gg B$. The restart condition is then replaced by

$$k \sum_{t=0}^{k-1} \|x^{t+1} - x^t\|^2 > \max\{B^2, B_0^2\},$$

and $B_0$ is gradually decreased until $B_0 \le B$, at which point the algorithm reduces to Algorithm 3. It is shown [42, Theorem 2] that this modification introduces an additional $O(L^{1/2}\epsilon^{-1/4}L_2^{1/4}\log(L_2B_0/\epsilon))$ term in the gradient complexity, which does not significantly degrade the overall rate. This modification shows great empirical behaviour, enabling acceleration over gradient descent. However, this alternative scheme requires additional function evaluations, leading to a total complexity of $O(\epsilon^{-3/2})$ function queries.

# B Numerical Experiments

In this section, we provide some numerical experiments.

## B.1 Law visualization

Our main theoretical result (Theorem 4.2) relies on the behaviour of the following random variables

$$H_0^i := \sum_{j=1}^{i} (T_i - T_j) e^{-\alpha(T_i - T_j)}, \quad H_1^i := \sum_{j=1}^{i} e^{-\alpha(T_i - T_j)}, \quad H_2^i := \sum_{j=1}^{i} (i - j) e^{-\alpha(T_i - T_j)},$$

where we recall $T_i - T_j \sim \Gamma(i - j, 1)$. In Figure 1, we empirically verify that, for a realization of $\{T_k\}_{k \in \mathbb{N}}$, these random variables are smaller than five times their expectations (with a factor
<caption>**Algorithm 3:** Restarted Nesterov Momentum - Detailed version [42]</caption>

Input: $x^{-1} = x^{0} = x_{\text{int}}, B > 0, K, \eta, \theta$.
1 &nbsp;&nbsp;&nbsp;&nbsp; $k \leftarrow 0$
2 &nbsp;&nbsp;&nbsp;&nbsp; **while** $k < K$ **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $y^k \leftarrow x^k + (1 - \theta)(x^k - x^{k-1})$
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x^{k+1} \leftarrow y^k - \eta \nabla f(y^k)$
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $k \leftarrow k + 1$
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $k \sum_{t=0}^{k-1} \|x^{t+1} - x^t\|^2 > B^2$ **then**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x^{-1} \leftarrow x^k$,
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x^{0} \leftarrow x^k$,
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $k \leftarrow 0$
10 &nbsp;&nbsp;&nbsp;&nbsp; $K_0 \leftarrow \arg \min_{[K/2] \le k \le K-1} \|x^{k+1} - x^k\|$

$\alpha$ for $H_2^i$) for all $i \in \{1, \dots, n\}$. We also emphasized that these quantities are difficult to study theoretically. To give more insights about their behaviour, we plot in Figure 2 histograms of their centered law. We fix $n = 100$, and plot the histogram distribution of $10^4$ realizations for $i = 2$, $i = 10$ and $i = 100$. We observe that the shape of the laws significantly changes with $i$ varying, and in most cases seems not to be symmetric.

## B.2 Matrix Factorization

We consider the following symmetric low-rank matrix factorization problem

$$ \min_{U \in \mathbb{R}^{d \times r}} f(U) := \|UU^T - M^*\|_F^2, \qquad (18) $$

where $M^*$ is a $d \times d$ matrix with rank $r < d$, and $\|\cdot\|_F$ denotes the Froebenius norm. This is a non-convex problem, with Lipschitz gradient and Hessian on a bounded domains, as stated in the following result.

**Lemma B.1.** [[36], Lemma 6] Let $\Gamma \ge \sigma_{\max}$, where $\sigma_{\max}$ is the largest singular value of $M^*$. Then, on $\{U \in \mathbb{R}^{d \times r} : \|U\|_F^2 < \Gamma\}$, we have that the function $f: U \mapsto \|UU^T - M^*\|_F^2$ is $8\Gamma$-smooth and with $12\Gamma^{1/2}$-Lipschitz Hessian.

We will run both gradient descent and (CNA) to solve problem (18).

**Experiment setting.** We chose $d = 200, r = 50$. We set $M^*$ to have symmetrical standard Gaussian entries on the $(i, j)$ coordinates such that $i, j \le 50$, other entries are zero. We initialize $U$ with each entry following a centered Gaussian law with variance 1. For (CNA), we chose the parameter as suggested by Theorem 4.2, such that we only have to tune $\gamma$. For both algorithms, we set $\gamma$ according to Lemma B.1, namely $\gamma = 8\sigma_{\max}$. Because of the stochastic nature of (CNA), we run the algorithm 10 times and average the function values iteration-wise. The results are displayed in Figure 3. We observe the faster decrease of the function values when using (CNA).

## C Proof of the Lemmas stated in Section 5

We prove formally all the Lemmas used in Section 5 to prove Theorem 4.2.
<figure><img src="image_3.png" /><figcaption>Figure 2: Histogram distribution of the centered laws of $H_j^i$ for $j = 0, 1, 2$ and $i = 2, 10, 100$, see Definition 4.1. The underlying $n$ is 100.</figcaption></figure>

## C.1 Proof of Lemma 5.1

The proof follows similar steps as for Lemma 1 in [53]. We show the following inequalities

$$ \left\| \int_{0}^{t} w_{t}(s) \nabla f(x_{s^{-}}) dN_{s} - \nabla f(\bar{x}_{t}) \right\| \le \frac{L_{2}}{2} \int_{0}^{t} w_{t}(s) \|x_{s^{-}} - \bar{x}_{t}\|^{2} dN_{s} \quad (19) $$

$$ = \frac{L_2}{2} \iint_{0 \le \sigma \le \tau \le t} w_t(\sigma) w_t(\tau) \|x_{\tau^{-}} - x_{\sigma^{-}}\|^2 dN_\sigma dN_\tau \quad (20) $$

$$ \le L_2 \int_0^t \eta^2 \|z_s - x_s\|^2 \left( \int_s^t \int_0^s w_t(\sigma) w_t(\tau) (\tau - \sigma) dN_\sigma dN_\tau \right) ds \\ + L_2 \int_0^t \gamma^2 \|\nabla f(x_{s^{-}})\|^2 \left( \int_s^t \int_0^s w_t(\sigma) w_t(\tau) (N_{\tau^{-}} - N_{\sigma^{-}}) dN_\sigma dN_\tau \right) dN_s. \quad (21) $$

**Inequality (19).** Using Taylor expansion of the gradient, we have
<figure><img src="image_4.png" /><figcaption>Figure 3: Decrease of log f values along the iterations of gradient descent and (CNA), with f defined by the matrix factorization problem (18). Because (CNA) is a stochastic algorithm, we averaged for 10 runs the functions values iteration-wise. We observe a faster decrease in favor of (CNA).</figcaption></figure>

$$
\begin{align*}
& \nabla f(x_{s-}) - \nabla f(\bar{x}_t) \\
&= \int_0^1 \nabla^2 f((1-\sigma)\bar{x}_t + \sigma x_{s-})(x_{s-} - \bar{x}_t) d\sigma \\
&= \nabla^2 f(\bar{x}_t)(x_{s-} - \bar{x}_t) + \int_0^1 (\nabla^2 f((1-\sigma)\bar{x}_t + \sigma x_{s-}) - \nabla^2 f(\bar{x}_t))(x_{s-} - \bar{x}_t) d\sigma.
\end{align*}
$$

Multiply both sides by $w_t(s)$ and integrate with respect to $dN(\cdot)$ on $s \in [0, t]$

$$
\begin{align}
& \int_0^t w_t(s)(\nabla f(x_{s-}) - \nabla f(\bar{x}_t))dN_s \nonumber \\
&= \int_0^t w_t(s)\nabla^2 f(\bar{x}_t)(x_{s-} - \bar{x}_t)dN_s \tag{22} \\
& \quad + \int_0^t w_t(s)\int_0^1 (\nabla^2 f((1-\sigma)\bar{x}_t + \sigma x_{s-}) - \nabla^2 f(\bar{x}_t))(x_{s-} - \bar{x}_t)d\sigma dN_s. \nonumber
\end{align}
$$

Because $\int_0^t w_t(s) dN_s = 1$, we have

$$
\int_0^t w_t(s)(\nabla f(x_{s-}) - \nabla f(\bar{x}_t))dN_s = \int_0^t w_t(s)\nabla f(x_{s-})dN_s - \nabla f(\bar{x}_t),
$$

and because $\bar{x}_t = \int_0^t w_t(s) x_{s-} dN_s$, we get

$$
\int_0^t w_t(s) \nabla^2 f(\bar{x}_t) (x_{s-} - \bar{x}_t) dN_s = 0.
$$

Also,

$$
\begin{align*}
& \left\| \int_0^t w_t(s) \int_0^1 (\nabla^2 f((1-\sigma)\bar{x}_t + \sigma x_{s-}) - \nabla^2 f(\bar{x}_t))(x_{s-} - \bar{x}_t) d\sigma dN_s \right\| \\
& \le \int_0^t w_t(s) \int_0^1 \left\| \nabla^2 f((1-\sigma)\bar{x}_t + \sigma x_{s-}) - \nabla^2 f(\bar{x}_t) \right\|_2 \|x_{s-} - \bar{x}_t\| d\sigma dN_s \\
& \le \int_0^t w_t(s) \int_0^1 \sigma L_2 \|x_{s-} - \bar{x}_t\|^2 d\sigma dN_s \quad (\text{Assumption 2.2}) \\
& = \frac{L_2}{2} \int_0^t w_t(s) \|x_{s-} - \bar{x}_t\|^2 dN_s.
\end{align*}
$$
Finally, taking the norm, (22) becomes

$$ \left\| \int_{0}^{t} w_{t}(s) \nabla f(x_{s-}) dN_{s} - \nabla f(\bar{x}_{t}) \right\| \leq \frac{L_{2}}{2} \int_{0}^{t} w_{t}(s) \|x_{s-} - \bar{x}_{t}\|^{2} dN_{s}. $$

**Equality (20).** We have

$$ \begin{aligned} \left\| \int_{0}^{t} w_{t}(\sigma) x_{\sigma^{-}} dN_{\sigma} \right\|^{2} &= \left\langle \int_{0}^{t} w_{t}(\sigma) x_{\sigma^{-}} dN_{\sigma}, \int_{0}^{t} w_{t}(\tau) x_{\tau^{-}} dN_{\tau} \right\rangle \\ &= \iint_{[0,t]^{2}} w_{t}(\sigma) w_{t}(\tau) \langle x_{\sigma^{-}}, x_{\tau^{-}} \rangle dN_{\sigma} dN_{\tau}. \end{aligned} \quad (23) $$

Also

$$ \begin{aligned} & \iint_{0 \le \sigma \le \tau \le t} w_t(\sigma) w_t(\tau) \|x_{\tau^{-}} - x_{\sigma^{-}}\|^2 dN_\sigma dN_\tau \\ &= \frac{1}{2} \iint_{[0,t]^2} w_t(\sigma) w_t(\tau) \|x_{\tau^{-}} - x_{\sigma^{-}}\|^2 dN_\sigma dN_\tau \\ &= \int_0^t w_t(\sigma) \|x_{\sigma^{-}}\|^2 dN_\sigma - \iint_{[0,t]^2} w_t(\sigma) w_t(\tau) \langle x_{\sigma^{-}}, x_{\tau^{-}} \rangle dN_\sigma dN_\tau \end{aligned} $$

where the last equality is obtained by developing the squared norm, and because

$$ \iint_{[0,t]^2} w_t(\sigma) w_t(\tau) \|x_{\tau^{-}}\|^2 dN_\sigma dN_\tau = \int_0^t w_t(\tau) \|x_{\tau^{-}}\|^2 dN_\tau \int_0^t w_t(\sigma) dN_\sigma = \int_0^t w_t(\tau) \|x_{\tau^{-}}\|^2 dN_\tau. $$

Then,

$$ \begin{aligned} & \int_0^t w_t(\sigma) \|x_{\sigma^{-}}\|^2 dN_\sigma - \iint_{[0,t]^2} w_t(\sigma) w_t(\tau) \langle x_{\sigma^{-}}, x_{\tau^{-}} \rangle dN_\sigma dN_\tau \\ &= \int_0^t w_t(\sigma) \|x_{\sigma^{-}}\|^2 dN_\sigma - \left\| \int_0^t w_t(\sigma) x_{\sigma^{-}} dN_\sigma \right\|^2, \quad \text{using (23)} \\ &= \int_0^t w_t(\sigma) \|x_{\sigma^{-}}\|^2 dN_\sigma - \|\bar{x}_t\|^2 \\ &= \int_0^t w_t(\sigma) \|x_{\sigma^{-}}\|^2 dN_\sigma - 2 \|\bar{x}_t\|^2 + \|\bar{x}_t\|^2 \\ &= \int_0^t w_t(\sigma) \|x_{\sigma^{-}}\|^2 dN_\sigma - 2 \left\langle \int_0^t w_t(\sigma) x_{\sigma^{-}} dN_\sigma, \underbrace{\int_0^t w_t(\sigma) x_{\sigma^{-}} dN_\sigma}_{=\bar{x}_t} \right\rangle \\ & \quad + \|\bar{x}_t\|^2 \underbrace{\int_0^t w_t(\sigma) dN_\sigma}_{=1} \\ &= \int_0^t w_t(\sigma) \|x_{\sigma^{-}}\|^2 dN_\sigma - 2 \int_0^t w_t(\sigma) \langle x_{\sigma^{-}}, \bar{x}_t \rangle dN_\sigma + \int_0^t w_t(\sigma) \|\bar{x}_t\|^2 dN_\sigma \\ &= \int_0^t w_t(\sigma) \|x_{\sigma^{-}} - \bar{x}_t\|^2 dN_\sigma. \end{aligned} $$

**Inequality (21).** By definition of $(x_t)_{t \ge 0}$, we have

$$ x_t = x_{\sigma^{-}} + \int_{\sigma}^{t} \eta(z_s - x_s) ds - \int_{[\sigma, t]} \gamma \nabla f(x_{s^{-}}) dN_s $$
Taking the left-limit at $t$, it becomes

$$x_{t-} = x_{\sigma-} + \int_{\sigma}^{t} \eta(z_s - x_s)ds - \int_{[\sigma,t)} \gamma \nabla f(x_{s-})dN_s$$

For $0 \le \sigma \le \tau \le t$, using $\|a-b\|^2 \le 2\|a\|^2 + 2\|b\|^2$ for $a, b \in \mathbb{R}^d$ and Cauchy-Schwarz inequality, we have

$$ \begin{aligned} \|x_{\tau-} - x_{\sigma-}\|^2 &= \left\| \int_{\sigma}^{\tau} \eta(z_s - x_s)ds - \int_{[\sigma,\tau)} \gamma \nabla f(x_{s-})dN_s \right\|^2 \\ &\le 2 \left\| \int_{\sigma}^{\tau} \eta(z_s - x_s)ds \right\|^2 + 2 \left\| \int_{[\sigma,\tau)} \gamma \nabla f(x_{s-})dN_s \right\|^2 \\ &\le 2 \left( \int_{\sigma}^{\tau} \|\eta(z_s - x_s)\| ds \right)^2 + 2 \left( \int_{[\sigma,\tau)} \|\gamma \nabla f(x_{s-})\| dN_s \right)^2 \\ &\le 2 \left( \int_{\sigma}^{\tau} \|\eta(z_s - x_s)\|^2 ds \right) \left( \int_{\sigma}^{\tau} ds \right) + \left( \int_{[\sigma,\tau)} dN_s \right) \left( \int_{[\sigma,\tau)} \|\gamma \nabla f(x_{s-})\|^2 dN_s \right) \\ &\le 2(\tau - \sigma) \left( \int_{\sigma}^{\tau} \eta^2 \|(z_s - x_s)\|^2 ds \right) + 2(N_{\tau-} - N_{\sigma-}) \int_{\sigma}^{\tau} \gamma^2 \|\nabla f(x_{s-})\|^2 dN_s. \end{aligned} \quad (24) $$

In the last inequality, we used $\int_{[\sigma,\tau]} \|\gamma \nabla f(x_{s-})\|^2 dN_s \le \int_{[\sigma,\tau]} \|\gamma \nabla f(x_{s-})\|^2 dN_s$, recalling our notation $\int_{\sigma}^{\tau} dN_s = \int_{[\sigma,\tau]}$. Then, we have

$$ \begin{aligned} & \iint_{0 \le \sigma \le \tau \le t} w_t(\sigma)w_t(\tau) \|x_{\tau-} - x_{\sigma-}\|^2 dN_\sigma dN_\tau \\ & \le \iint_{0 \le \sigma \le \tau \le t} w_t(\sigma)w_t(\tau)2(\tau - \sigma) \left( \int_{\sigma}^{\tau} \eta^2 \|z_s - x_s\|^2 ds \right) dN_\sigma dN_\tau \\ & + \iint_{0 \le \sigma \le \tau \le t} w_t(\sigma)w_t(\tau)2(N_{\tau-} - N_{\sigma-}) \left( \int_{\sigma}^{\tau} \gamma^2 \|\nabla f(x_{s-})\|^2 dN_s \right) dN_\sigma dN_\tau \\ & = \iint_{0 \le \sigma \le s \le \tau \le t} w_t(\sigma)w_t(\tau)2(\tau - \sigma)\eta^2 \|z_s - x_s\|^2 ds dN_\sigma dN_\tau \\ & + \iint_{0 \le \sigma \le s \le \tau \le t} w_t(\sigma)w_t(\tau)2(N_{\tau-} - N_{\sigma-})\gamma^2 \|\nabla f(x_{s-})\|^2 dN_s dN_\sigma dN_\tau \\ & = 2 \int_{0}^{t} \eta^2 \|z_s - x_s\|^2 \left( \int_{s}^{t} \int_{0}^{s} w_t(\sigma)w_t(\tau)(\tau - \sigma) dN_\sigma dN_\tau \right) ds \\ & + 2 \int_{0}^{t} \gamma^2 \|\nabla f(x_{s-})\|^2 \left( \int_{s}^{t} \int_{0}^{s} w_t(\sigma)w_t(\tau)(N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau \right) dN_s. \end{aligned} $$

## C.2 Proof of Lemma 5.2

We set $\tilde{w}(s) = \alpha e^{\alpha s}$, such that $s \mapsto \tilde{w}(s)$ is differentiable, satisfying

$$ \frac{d\tilde{w}(s)}{ds} = \alpha \tilde{w}(s). $$

Summing the two lines of (CNE) and using $\eta + \eta' = \alpha$, we get

$$ dx_s - dz_s = \alpha(z_s - x_s)ds - (\gamma - \gamma')\nabla f(x_{s-})dN_s. \quad (25) $$

We multiply each side of (25) by $\tilde{w}(s)$ and use $d\tilde{w}(s) = \alpha\tilde{w}(s)ds$ to get

$$ \begin{aligned} \tilde{w}(s)(dx_s - dz_s) &= \tilde{\alpha}w(s)(z_s - x_s)ds - \tilde{w}(s)(\gamma - \gamma')\nabla f(x_{s-})dN_s \\ &= (z_s - x_s)d\tilde{w}(s) - \tilde{w}(s)(\gamma - \gamma')\nabla f(x_{s-})dN_s. \end{aligned} $$
By rearranging, we obtain

$$ \tilde{w}(s)(dx_s - dz_s) + (x_s - z_s)d\tilde{w}(s) = -\tilde{w}(s)(\gamma - \gamma')\nabla f(x_{s-})dN_s. \quad (26) $$

We write (26) in an integral form, such that

$$ \int_{0}^{t} \tilde{w}(s)(dx_s - dz_s) + \int_{0}^{t} (x_s - z_s)d\tilde{w}(s) = -(\gamma - \gamma') \int_{0}^{t} \tilde{w}(s)\nabla f(x_{s-})dN_s \quad (27) $$

We use the following integration by part formula for stochastic integrals, see a precise statement in [56, p.83].

**Corollary C.1 ([56]).** Let X, Y be semimartingales with at least one of X or Y continuous. Then

$$ X_t Y_t = X_0 Y_0 + \int_0^t X_{s-} dY_s + \int_0^t Y_{s-} dX_s. $$

We apply Corollary C.1 to $X_t = x_t - z_t$ and $Y_t = \tilde{w}(t)$, such that $X_0Y_0 = 0$, and so

$$ \int_{0}^{t} \tilde{w}(s)(dx_s - dz_s) + \int_{0}^{t} (x_s - z_s)d\tilde{w}(s) = \tilde{w}(t)(x_t - z_t). \quad (28) $$

We combine (27) with (28), and multiply both sides by $(\int_0^t \alpha e^{\alpha s} dN_s)^{-1}$ to conclude. Note that we can use Corollary C.1 as $t \mapsto \tilde{w}(t)$ is deterministic and continuous, and $x_t - z_t$ is a semimartingale as a difference of semimartingales. To see that $(x_t)_{t \ge 0}$ is a semi martingale, remark that it writes

$$ \begin{aligned} x_t &= x_0 + \eta \int_0^t (z_s - x_s)ds - \gamma \int_0^t \nabla f(x_{s-})dN_s \\ &= x_0 + \underbrace{\int_0^t (\eta(z_s - x_s) - \gamma \nabla f(x_s))ds}_{\text{adapted + continuous + bounded variation}} - \gamma \underbrace{\int_0^t \nabla f(x_{s-})(dN_s - ds)}_{\text{martingale}} \end{aligned} $$

which is a semimartingale by definition. The same argument holds for $(z_t)_{t \ge 0}$.

### C.3 Proof of Lemma 5.3

From Lemma 5.1, we have

$$ \begin{aligned} \|\nabla f(\bar{x}_t)\| &\le \left\| \int_0^t w_t(s) \nabla f(x_{s-}) dN_s \right\| \\ &\quad + L_2 \int_0^t \eta^2 \|z_s - x_s\|^2 \left( \int_s^t \int_0^s w_t(\sigma) w_t(\tau) (\tau - \sigma) dN_\sigma dN_\tau \right) ds \\ &\quad + L_2 \int_0^t \gamma^2 \|\nabla f(x_{s-})\|^2 \left( \int_s^t \int_0^s w_t(\sigma) w_t(\tau) (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau \right) dN_s \\ &= \left\| \frac{w_t(t)(z_t - x_t)}{\gamma' - \gamma} \right\| + L_2 \int_0^t \eta^2 \|z_s - x_s\|^2 \left( \int_s^t \int_0^s w_t(\sigma) w_t(\tau) (\tau - \sigma) dN_\sigma dN_\tau \right) ds \\ &\quad + L_2 \int_0^t \gamma^2 \|\nabla f(x_{s-})\|^2 \left( \int_s^t \int_0^s w_t(\sigma) w_t(\tau) (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau \right) dN_s, \end{aligned} $$
where the equality is because of Lemma 5.2. Multiplying both sides by $\Lambda_t := (\int_0^t \alpha e^{\alpha(s-t)} dN_s)^2$ and integrating on $[0, T_n]$ with respect to $dN_t$, we get

$$
\begin{align*}
\int_0^{T_n} \Lambda_t \|\nabla f(\bar{x}_t)\| dN_t &\le \int_0^{T_n} \Lambda_t \left\| \frac{w_t(t)(z_t - x_t)}{\gamma' - \gamma} \right\| dN_t \\
&\quad + L_2 \int_0^{T_n} \Lambda_t \int_0^t \eta^2 \|z_s - x_s\|^2 \left( \int_s^t \int_0^s w_t(\sigma)w_t(\tau)(\tau - \sigma) dN_\sigma dN_\tau \right) ds dN_t \\
&\quad + L_2 \int_0^{T_n} \Lambda_t \int_0^t \gamma^2 \|\nabla f(x_{s-})\|^2 \left( \int_s^t \int_0^s w_t(\sigma)w_t(\tau)(N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau \right) dN_s dN_t \\
&\stackrel{(i)}{=} \int_0^{T_n} \Lambda_t \left\| \frac{w_t(t)(z_t - x_t)}{\gamma' - \gamma} \right\| dN_t \\
&\quad + \alpha^2 L_2 \int_0^{T_n} \int_0^t \eta^2 \|z_s - x_s\|^2 \left( \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau - \sigma) dN_\sigma dN_\tau \right) ds dN_t \\
&\quad + \alpha^2 L_2 \int_0^{T_n} \int_0^t \gamma^2 \|\nabla f(x_{s-})\|^2 \left( \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau \right) dN_s dN_t \\
&\stackrel{(ii)}{=} \int_0^{T_n} \Lambda_t \left\| \frac{w_t(t)(z_t - x_t)}{\gamma' - \gamma} \right\| dN_t \\
&\quad + \alpha^2 L_2 \int_0^{T_n} \eta^2 \|z_s - x_s\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau - \sigma) dN_\sigma dN_\tau dN_t \right) ds \\
&\quad + \alpha^2 L_2 \int_0^{T_n} \gamma^2 \|\nabla f(x_{s-})\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau dN_t \right) dN_s.
\end{align*}
$$

Equality (i) holds as $\Lambda_t = (\int_0^t \alpha e^{\alpha(s-t)} dN_s)^2 = (\int_0^t \alpha e^{\alpha s} dN_s)^2 e^{-2\alpha t}$, such that

$$
\Lambda_t w_t(\sigma) w_t(\tau) = \left( \int_0^t \alpha e^{\alpha s} dN_s \right)^2 e^{-2\alpha t} \frac{\alpha e^{\alpha \sigma}}{\int_0^t \alpha e^{\alpha s} dN_s} \frac{\alpha e^{\alpha \tau}}{\int_0^t \alpha e^{\alpha s} dN_s} = \alpha^2 e^{-2\alpha t} e^{\alpha \sigma} e^{\alpha \tau}.
$$

Equality (ii) holds by Tonelli, enabling to swap the integration order of s and t.

C.4 Proof of Lemma 5.4

We prove each statement separately.

**Equation (13)** We have

$$
\begin{align*}
& \int_0^{T_n} \eta^2 \|z_s - x_s\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau - \sigma) dN_\sigma dN_\tau dN_t \right) ds \\
&= \sum_{i=0}^{n-1} \int_{(T_i, T_{i+1})} \eta^2 \|z_s - x_s\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau - \sigma) dN_\sigma dN_\tau dN_t \right) ds,
\end{align*}
$$
where we used that integration with respect to $ds$ on a singleton is zero. Noting $U_i := \int_{(T_i, T_{i+1})} \eta^2 \|z_s - x_s\|^2 ds$, we have

$$
\begin{align*}
& \sum_{i=0}^{n-1} \int_{(T_i, T_{i+1})} \eta^2 \|z_s - x_s\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau-\sigma) dN_\sigma dN_\tau dN_t \right) ds \\
& \stackrel{(i)}{=} \sum_{i=0}^{n-1} \left( \int_{(T_i, T_{i+1})} \eta^2 \|z_s - x_s\|^2 ds \right) \left( \int_{T_{i+1}}^{T_n} \int_{T_{i+1}}^t \int_0^{T_i} e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau-\sigma) dN_\sigma dN_\tau dN_t \right) \\
& \stackrel{(ii)}{=} \sum_{i=1}^{n-1} \left( \int_{(T_i, T_{i+1})} \eta^2 \|z_s - x_s\|^2 ds \right) \left( \int_{T_{i+1}}^{T_n} \int_{T_{i+1}}^t \int_0^{T_i} e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau-\sigma) dN_\sigma dN_\tau dN_t \right) \\
& = \sum_{i=1}^{n-1} U_i \left( \int_{T_{i+1}}^{T_n} \int_{T_{i+1}}^t \int_0^{T_i} e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau-\sigma) dN_\sigma dN_\tau dN_t \right) \\
& = \sum_{i=1}^{n-1} \left( \int_{T_{i+1}}^{T_n} \int_{T_{i+1}}^t \int_0^{T_i} e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau-\sigma) U_i dN_\sigma dN_\tau dN_t \right), \tag{29}
\end{align*}
$$

where (i) uses the fact that $\int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau-\sigma) dN_\sigma dN_\tau dN_t$ is constant for $s \in (T_i, T_{i+1})$, as no new jump occurs on this interval. (ii) uses that $\int_0^{T_0} \cdot dN_t = \int_0^0 \cdot dN_t = 0$, as almost surely no jumps occur at $t=0$. Because we integrate over $[0, T_n]$ with Poisson integrals, we can write (29) as a sum

$$
(29) = \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \sum_{j=1}^{i} e^{\alpha(T_k-T_l)} e^{\alpha(T_j-T_l)} (T_k-T_j) U_i. \quad (30)
$$

We restrict ourselves to $\mathcal{A}_n$, and take expectation on (30)

$$
\begin{align*}
\mathbb{E}[1_{\mathcal{A}_n} \cdot (30)] &= \mathbb{E} \left[ 1_{\mathcal{A}_n} \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \sum_{j=1}^{i} e^{\alpha(T_k-T_l)} e^{\alpha(T_j-T_l)} (T_k-T_j) U_i \right] \\
&= \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ 1_{\mathcal{A}_n} e^{\alpha(T_k-T_l)} e^{\alpha(T_{i+1}-T_l)} \sum_{j=1}^{i} e^{\alpha(T_j-T_{i+1})} (T_k-T_j) U_i \right] \\
&\le \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ 1_{\mathcal{A}_n} e^{\alpha(T_k-T_l)} e^{\alpha(T_{i+1}-T_l)} \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} (T_k-T_j) U_i \right] \\
&= \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ 1_{\mathcal{A}_n} e^{\alpha(T_k-T_l)} e^{\alpha(T_{i+1}-T_l)} U_i \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} (T_k-T_{i+1}) \right] \\
&\quad + \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ 1_{\mathcal{A}_n} e^{\alpha(T_k-T_l)} e^{\alpha(T_{i+1}-T_l)} U_i \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} (T_{i+1}-T_j) \right].
\end{align*}
$$
(i) uses that $\sum_{j=1}^{i} a_j \le \sum_{j=1}^{i+1} a_j$, as long as $a_j \ge 0$ for any $j \in \{1, \dots, i+1\}$. Now, we use the fact that we are on the set $\mathcal{A}_n$, such that

$$ 
\begin{aligned}
\mathbb{E}[1_{\mathcal{A}_n} \cdot (30)] & \le \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ 1_{\mathcal{A}_n} e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} (T_k - T_{i+1}) U_i C \mathbb{E} \left[ \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} \right] \right] \\
& \quad + \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ 1_{\mathcal{A}_n} e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} U_i C \mathbb{E} \left[ \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} (T_{i+1}-T_j) \right] \right] \\
& \stackrel{(i)}{\le} C \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} (T_k - T_{i+1}) U_i \right] \mathbb{E} \left[ \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} \right] \\
& \quad + C \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} U_i \right] \mathbb{E} \left[ \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} (T_{i+1}-T_j) \right],
\end{aligned} 
\quad (31) $$

where (i) is obtained by rearranging, and using $1_{\mathcal{A}_n} \le 1$. $U_i$ depends on $\{T_k\}_{k \in \{1, \dots, i\}}$, as it depends on $x_s$ and $z_s$ for $s \in (T_i, T_{i+1})$, which depend on $\{T_k\}_{k \in \{1, \dots, i\}}$. Also, $U_i$ depends on the length of the interval $(T_i, T_{i+1})$, such that $U_i$ also depends on $T_{i+1}$. So, we have that $U_i$ only depends on $\{T_k\}_{k \in \{1, \dots, i+1\}}$. Because the increments of $\{T_k\}_{k \in \mathbb{N}}$ are independent, because $k, l \ge i+1$, we have $T_{i+1} - T_l \perp U_i$ and $T_k - T_l \perp U_i$. So, (31) becomes

$$ 
\begin{aligned}
\mathbb{E}[1_{\mathcal{A}_n} \cdot (30)] & \le C \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} (T_k - T_{i+1}) \right] \mathbb{E}[U_i] \mathbb{E} \left[ \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} \right] \\
& \quad + C \sum_{i=1}^{n-1} \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} \right] \mathbb{E}[U_i] \mathbb{E} \left[ \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} (T_{i+1}-T_j) \right] \\
& = C \sum_{i=1}^{n-1} \mathbb{E}[U_i] \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} (T_k - T_{i+1}) \right] \mathbb{E} \left[ \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} \right] \\
& \quad + C \sum_{i=1}^{n-1} \mathbb{E}[U_i] \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} \right] \mathbb{E} \left[ \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} (T_{i+1}-T_j) \right] \\
& \stackrel{(i)}{=} C \sum_{i=1}^{n-1} \mathbb{E}[U_i] \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} (T_k - T_{i+1}) \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} \right] \\
& \quad + C \sum_{i=1}^{n-1} \mathbb{E}[U_i] \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} \mathbb{E} \left[ e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} (T_{i+1}-T_j) \right] \\
& = C \sum_{i=1}^{n-1} \mathbb{E}[U_i] \mathbb{E} \left[ \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} (T_k - T_j) \right],
\end{aligned} 
\quad (32) $$

where in (i) we used the independence of the increments of the $\{T_k\}_{k \in \mathbb{N}}$. Finally, writing the sums as Poisson integrals, noting $A_{i+1} := \sum_{l=i+1}^{n} \sum_{k=i+1}^{l} e^{\alpha(T_{i+1}-T_l)} e^{\alpha(T_k-T_l)} \sum_{j=1}^{i+1} e^{\alpha(T_j-T_{i+1})} (T_k - T_j) = \int_{[T_{i+1}, T_n]} \int_{[T_{i+1}, t]} e^{\alpha(T_{i+1}-t)} e^{\alpha(\tau-t)} \int_{[0, T_{i+1}]} e^{\alpha(\sigma-T_{i+1})} (\tau - \sigma) dN_{\sigma} dN_{\tau} dN_t$, and recalling $U_i := \int_{(T_i, T_{i+1})} \eta^2 \|z_s - x_s\|^2 ds$, (32) becomes
$$
\begin{align*}
\mathbb{E}[\mathbb{1}_{\mathcal{A}_n} \cdot (30)] &= C \sum_{i=1}^{n-1} \mathbb{E} \left[ \int_{(T_i, T_{i+1})} \eta^2 \|z_s - x_s\|^2 ds \right] \mathbb{E}[A_{i+1}] \\
&\le C \max_{i \in \{1, \dots, n-1\}} \mathbb{E}[A_{i+1}] \sum_{i=1}^{n-1} \mathbb{E} \left[ \int_{(T_i, T_{i+1})} \eta^2 \|z_s - x_s\|^2 ds \right] \\
&\le C \max_{i \in \{1, \dots, n\}} \mathbb{E}[A_i] \mathbb{E} \left[ \int_0^{T_n} \eta^2 \|z_s - x_s\|^2 ds \right].
\end{align*}
$$

Equation (14)

$$
\begin{align}
& \int_0^{T_n} \gamma^2 \|\nabla f(x_{s-})\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau dN_t \right) dN_s \tag{33} \\
&= \int_0^{T_n} \left( \int_s^{T_n} \int_s^t e^{\alpha(\tau-t)} e^{\alpha(s-t)} \gamma^2 \|\nabla f(x_{s-})\|^2 \int_0^s e^{\alpha(\sigma-s)} (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau dN_t \right) dN_s \nonumber
\end{align}
$$

Because we integrate over $[0, T_n]$, (33) can be written as a sum

$$
(33) = \sum_{i=1}^{n} \sum_{l=i}^{n} \sum_{k=i}^{l} e^{\alpha(T_k - T_l)} e^{\alpha(T_i - T_l)} \gamma^2 \left\| \nabla f(x_{T_i^-}) \right\|^2 \sum_{j=1}^{i} e^{\alpha(T_j - T_i)} (k-j). \quad (34)
$$

We used that $N_{T_k^-} - N_{T_j^-} = (k-1) - (j-1)$. Taking expectation and by multiplication by $\mathbb{1}_{\mathcal{A}_n}$, we have

$$
\begin{align*}
\mathbb{E}[\mathbb{1}_{\mathcal{A}_n} \cdot (33)] &= \mathbb{E} \left[ \mathbb{1}_{\mathcal{A}_n} \sum_{i=1}^{n} \sum_{l=i}^{n} \sum_{k=i}^{l} e^{\alpha(T_k - T_l)} e^{\alpha(T_i - T_l)} \gamma^2 \left\| \nabla f(x_{T_i^-}) \right\|^2 \sum_{j=1}^{i} e^{\alpha(T_j - T_i)} (k-j) \right] \\
&= \sum_{i=1}^{n} \sum_{l=i}^{n} \sum_{k=i}^{l} \mathbb{E} \left[ \mathbb{1}_{\mathcal{A}_n} e^{\alpha(T_k - T_l)} e^{\alpha(T_i - T_l)} \gamma^2 \left\| \nabla f(x_{T_i^-}) \right\|^2 \sum_{j=1}^{i} e^{\alpha(T_j - T_i)} (k-j) \right] \\
&= \sum_{i=1}^{n} \sum_{l=i}^{n} \sum_{k=i}^{l} \mathbb{E} \left[ \mathbb{1}_{\mathcal{A}_n} e^{\alpha(T_k - T_l)} e^{\alpha(T_i - T_l)} \gamma^2 \left\| \nabla f(x_{T_i^-}) \right\|^2 (k-i) \sum_{j=1}^{i} e^{\alpha(T_j - T_i)} \right] \\
&\quad + \sum_{i=1}^{n} \sum_{l=i}^{n} \sum_{k=i}^{l} \mathbb{E} \left[ \mathbb{1}_{\mathcal{A}_n} e^{\alpha(T_k - T_l)} e^{\alpha(T_i - T_l)} \gamma^2 \left\| \nabla f(x_{T_i^-}) \right\|^2 \sum_{j=1}^{i} e^{\alpha(T_j - T_i)} (i-j) \right]
\end{align*}
$$

Now, since we are on the set $\mathcal{A}_n$, we have

$$
\begin{align}
\mathbb{E}[\mathbb{1}_{\mathcal{A}_n} \cdot (33)] &\le \sum_{i=1}^{n} \sum_{l=i}^{n} \sum_{k=i}^{l} \mathbb{E} \left[ \mathbb{1}_{\mathcal{A}_n} e^{\alpha(T_k - T_l)} e^{\alpha(T_i - T_l)} \gamma^2 \left\| \nabla f(x_{T_i^-}) \right\|^2 C(k-i) \mathbb{E} \left[ \sum_{j=1}^{i} e^{\alpha(T_j - T_i)} \right] \right] \nonumber \\
&\quad + \sum_{i=1}^{n} \sum_{l=i}^{n} \sum_{k=i}^{l} \mathbb{E} \left[ \mathbb{1}_{\mathcal{A}_n} e^{\alpha(T_k - T_l)} e^{\alpha(T_i - T_l)} \gamma^2 \left\| \nabla f(x_{T_i^-}) \right\|^2 C \alpha^{-1} \mathbb{E} \left[ \sum_{j=1}^{i} e^{\alpha(T_j - T_i)} (i-j) \right] \right] \nonumber \\
&\le C \sum_{i=1}^{n} \sum_{l=i}^{n} \sum_{k=i}^{l} \mathbb{E} \left[ e^{\alpha(T_k - T_l)} e^{\alpha(T_i - T_l)} \gamma^2 \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] (k-i) \mathbb{E} \left[ \sum_{j=1}^{i} e^{\alpha(T_j - T_i)} \right] \nonumber \\
&\quad + C \alpha^{-1} \sum_{i=1}^{n} \sum_{l=i}^{n} \sum_{k=i}^{l} \mathbb{E} \left[ e^{\alpha(T_k - T_l)} e^{\alpha(T_i - T_l)} \gamma^2 \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] \mathbb{E} \left[ \sum_{j=1}^{i} e^{\alpha(T_j - T_i)} (i-j) \right]. \tag{35}
\end{align}
$$
Now, because the increments of {$T_k$}$_{k \in \mathbb{N}}$ are independent, as $l, k \ge i$, we have $T_k - T_l \perp \|\nabla f(x_{T_i^-})\|$ and $T_i - T_l \perp \|\nabla f(x_{T_i^-})\|$. So, (35) becomes

$$
\begin{align}
\mathbb{E}[1_{\mathcal{A}_n} \cdot (33)] &\le C \sum_{i=1}^n \sum_{l=i}^n \sum_{k=i}^l \mathbb{E} \left[ e^{\alpha(T_k-T_l)} e^{\alpha(T_i-T_l)} \right] \gamma^2 \mathbb{E} \left[ \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] (k-i) \mathbb{E} \left[ \sum_{j=1}^i e^{\alpha(T_j-T_i)} \right] \nonumber \\
&\quad + C \alpha^{-1} \sum_{i=1}^n \sum_{l=i}^n \sum_{k=i}^l \mathbb{E} \left[ e^{\alpha(T_k-T_l)} e^{\alpha(T_i-T_l)} \gamma^2 \right] \mathbb{E} \left[ \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] \mathbb{E} \left[ \sum_{j=1}^i e^{\alpha(T_j-T_i)} (i-j) \right] \nonumber \\
&= C \sum_{i=1}^n \gamma^2 \mathbb{E} \left[ \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] \sum_{l=i}^n \sum_{k=i}^l \mathbb{E} \left[ e^{\alpha(T_k-T_l)} e^{\alpha(T_i-T_l)} \right] (k-i) \mathbb{E} \left[ \sum_{j=1}^i e^{\alpha(T_j-T_i)} \right] \nonumber \\
&\quad + C \alpha^{-1} \sum_{i=1}^n \gamma^2 \mathbb{E} \left[ \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] \sum_{l=i}^n \sum_{k=i}^l \mathbb{E} \left[ e^{\alpha(T_k-T_l)} e^{\alpha(T_i-T_l)} \right] \mathbb{E} \left[ \sum_{j=1}^i e^{\alpha(T_j-T_i)} (i-j) \right] \nonumber \\
&\stackrel{(i)}{\le} C \alpha^{-1} \sum_{i=1}^n \gamma^2 \mathbb{E} \left[ \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] \sum_{l=i}^n \sum_{k=i}^l \mathbb{E} \left[ e^{\alpha(T_k-T_l)} e^{\alpha(T_i-T_l)} (k-i) \right] \mathbb{E} \left[ \sum_{j=1}^i e^{\alpha(T_j-T_i)} \right] \nonumber \\
&\quad + C \alpha^{-1} \sum_{i=1}^n \gamma^2 \mathbb{E} \left[ \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] \sum_{l=i}^n \sum_{k=i}^l \mathbb{E} \left[ e^{\alpha(T_k-T_l)} e^{\alpha(T_i-T_l)} \right] \mathbb{E} \left[ \sum_{j=1}^i e^{\alpha(T_j-T_i)} (i-j) \right] \nonumber \\
&\stackrel{(ii)}{=} C \alpha^{-1} \sum_{i=1}^n \gamma^2 \mathbb{E} \left[ \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] \mathbb{E} \left[ \sum_{l=i}^n \sum_{k=i}^l e^{\alpha(T_k-T_l)} e^{\alpha(T_i-T_l)} \sum_{j=1}^i e^{\alpha(T_j-T_i)} (k-j) \right], \tag{36}
\end{align}
$$

where (i) used $\alpha^{-1} \ge 1$, and (ii) the independence property of the increments of {$T_k$}$_{k \in \mathbb{N}}$. Rewriting (36) as Poisson integrals, we note $B_i := \sum_{l=i}^n \sum_{k=i}^l e^{\alpha(T_k-T_l)} e^{\alpha(T_i-T_l)} \sum_{j=1}^i e^{\alpha(T_j-T_i)} (k-j) = \int_{T_i}^{T_n} \int_{T_i}^t e^{\alpha(\tau-t)} e^{\alpha(T_i-t)} \int_0^{T_i} (N_{\tau-} - N_{\sigma-}) e^{\alpha(\sigma-T_i)} dN_\sigma dN_\tau dN_t$, such that

$$
\begin{align*}
\mathbb{E}[1_{\mathcal{A}_n} \cdot (33)] &\le C \alpha^{-1} \sum_{i=1}^{n} \gamma^2 \mathbb{E} \left[ \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] \mathbb{E}[B_i] \\
&\le C \alpha^{-1} \max_{i \in \{1, \dots, n\}} \mathbb{E}[B_i] \sum_{i=1}^{n} \gamma^2 \mathbb{E} \left[ \left\| \nabla f(x_{T_i^-}) \right\|^2 \right] \\
&= C \alpha^{-1} \max_{i \in \{1, \dots, n\}} \mathbb{E}[B_i] \mathbb{E} \left[ \int_{0}^{T_n} \gamma^2 \left\| \nabla f(x_{s-}) \right\|^2 dN_s \right]
\end{align*}
$$

C.5 Proof of Lemma 5.5

Under Assumption 2.1, we prove in Lemma 3.1 inequality (70), namely

$$
\int_0^t (\eta + \eta') \|x_s - z_s\|^2 + \frac{\gamma}{4} \|\nabla f(x_s)\|^2 ds \leq f(x_0) - f^* + M_t,
$$

with $M_t$ a martingale such that $\mathbb{E}[M_t] = 0$. From this, we deduce

$$
\begin{align}
\int_0^t (\eta + \eta') \|x_s - z_s\|^2 ds &\le f(x_0) - f^* + M_t, \nonumber \\
\int_0^t \frac{\gamma}{4} \|\nabla f(x_{s-})\|^2 dN_s &\le f(x_0) - f^* + U_t, \tag{37}
\end{align}
$$

$$
\int_0^t (\eta + \eta') \|x_{s-} - z_{s-}\|^2 dN_s \le f(x_0) - f^* + V_t, \quad (38)
$$
where for some martingales $U_t, V_t$ with mean zero, (37) and (38) hold because $\int_0^t (\eta+\eta') \|x_s-z_s\|^2 ds = \int_0^t (\eta+\eta') \|x_{s-}-z_{s-}\|^2 dN_s$ and $\int_0^t \frac{\gamma}{4} \|\nabla f(x_s)\|^2 ds = \int_0^t \frac{\gamma}{4} \|\nabla f(x_{s-})\|^2 dN_s$, up to martingales whose expectations are zero. Now, using Theorem E.6, evaluating these bounds at $t = T_n$, they become

$$ \mathbb{E} \left[ \int_{0}^{T_n} (\eta + \eta') \|x_s - z_s\|^2 ds \right] \leq \mathbb{E} [f(x_0) - f^*], \quad (39) $$

$$ \mathbb{E} \left[ \int_{0}^{T_n} \frac{\gamma}{4} \| \nabla f(x_{s-}) \|^2 dN_s \right] \leq \mathbb{E} [f(x_0) - f^*], \quad (40) $$

$$ \mathbb{E} \left[ \int_{0}^{T_n} (\eta + \eta') \|x_{s-} - z_{s-}\|^2 dN_s \right] \leq \mathbb{E} [f(x_0) - f^*]. \quad (41) $$

We also need the following intermediate result, that allows to control the quantities related to $A_k$ and $B_k$ in Lemma 5.4, see its proof in Appendix D.1.

**Lemma C.2.** Consider $A_k$ and $B_k$ as defined in Lemma 5.4. Then

$$ 1. \max_{k \in \{2, \dots, n\}} \mathbb{E}[A_k] \leq \frac{(1+2\alpha)^4}{\alpha^4}. $$

$$ 2. \max_{k \in \{1, \dots, n\}} \mathbb{E}[B_k] \leq \frac{(1+2\alpha)^5}{\alpha^4}. $$

Noting $\Lambda_t := (\int_0^t \alpha e^{\alpha(s-t)} dN_s)^2$, multiplying each side of (12) in Lemma 5.3 by $\mathbb{1}_{A_n}$ and taking expectation, we have

$$ \mathbb{E} \left[ \mathbb{1}_{A_n} \int_0^{T_n} \Lambda_t \| \nabla f(\bar{x}_t) \| dN_t \right] \leq \mathbb{E} \left[ \mathbb{1}_{A_n} \int_0^{T_n} \Lambda_t \left\| \frac{w_t(t)(z_t - x_t)}{\gamma' - \gamma} \right\| dN_t \right] \quad (42) $$

$$ + \mathbb{E} \left[ \mathbb{1}_{A_n} \alpha^2 L_2 \int_0^{T_n} \eta^2 \|z_s - x_s\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau - \sigma) dN_\sigma dN_\tau dN_t \right) ds \right] \quad (43) $$

$$ + \mathbb{E} \left[ \mathbb{1}_{A_n} \alpha^2 L_2 \int_0^{T_n} \gamma^2 \| \nabla f(x_{s-}) \|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau dN_t \right) dN_s \right]. \quad (44) $$

We bound each term of the above equation.

1. Bounding the right hand side of (42). Recalling $w_t(t) = \frac{\alpha e^{\alpha t}}{\int_0^t \alpha e^{\alpha s} dN_s}$, one has

$$ \begin{aligned} \left\| \frac{w_t(t)(z_t - x_t)}{\gamma' - \gamma} \right\| &= \frac{\alpha e^{\alpha t}}{(\gamma' - \gamma)} \frac{1}{\int_0^t \alpha e^{\alpha s} dN_s} \|z_t - x_t\| \\ &= \frac{\alpha}{(\gamma' - \gamma)} \frac{1}{\int_0^t \alpha e^{\alpha(s-t)} dN_s} \|z_t - x_t\| \end{aligned} $$

So

$$ \begin{aligned} \mathbb{E} \left[ \int_{0}^{T_n} \Lambda_t \left\| \frac{w_t(t)(z_t - x_t)}{\gamma' - \gamma} \right\| dN_t \right] &= \mathbb{E} \left[ \int_{0}^{T_n} \frac{\alpha}{\gamma' - \gamma} \left( \int_{0}^{t} \alpha e^{\alpha(s-t)} dN_s \right) \|z_t - x_t\| dN_t \right] \\ &\leq \frac{\alpha}{\gamma' - \gamma} \sqrt{\mathbb{E} \left[ \int_{0}^{T_n} \Lambda_t dN_t \right]} \sqrt{\mathbb{E} \left[ \int_{0}^{T_n} \|z_t - x_t\|^2 dN_t \right]}, \end{aligned} \quad (45) $$

where we used the Cauchy-Schwarz inequality. We have

$$ \begin{aligned} \int_{0}^{T_n} \|z_t - x_t\|^2 dN_t &= \int_{0}^{T_n} \|z_{t-} - x_{t-} - (\gamma' - \gamma) \nabla f(x_{t-})\|^2 dN_t \\ &\leq 2 \int_{0}^{T_n} \|z_{t-} - x_{t-}\|^2 dN_t + 2(\gamma' - \gamma)^2 \int_{0}^{T_n} \|\nabla f(x_{t-})\|^2 dN_t \end{aligned} $$
From (40), we have

$$ \int_{0}^{T_n} \|\nabla f(x_{t-})\|^2 dN_t \le \frac{4}{\gamma}(f(x_0) - f^*), \quad (46) $$

and from (41), we have

$$ \mathbb{E} \left[ \int_{0}^{T_n} \|z_{t-} - x_{t-}\|^2 dN_t \right] \le \frac{1}{\eta + \eta'} (f(x_0) - f^*) = \frac{1}{\alpha} (f(x_0) - f^*). \quad (47) $$

Combining (46) and (47), we obtain

$$ \begin{aligned} \sqrt{\mathbb{E}\left[\int_{0}^{T_n} \|z_t - x_t\|^2 dN_t\right]} &\le \sqrt{2(f(x_0) - f^*)} \sqrt{\frac{1}{\alpha} + \frac{4(\gamma' - \gamma)^2}{\gamma}} \\ &\le \sqrt{2\alpha^{-1}(f(x_0) - f^*)} \sqrt{1 + \frac{4(\gamma' - \gamma)^2}{\gamma}}, \end{aligned} \quad (48) $$

the last inequality using $\alpha^{-1} \ge 1$. Note that we assume $\gamma' = \gamma + \sqrt{\gamma/2}$, such that $\frac{\gamma'-\gamma}{\gamma} = \frac{1}{2}$, such that $\sqrt{1 + \frac{4(\gamma'-\gamma)^2}{\gamma}} = \sqrt{1+2} = \sqrt{3}$. Combining this with (45), Lemma D.5-(i) and (48), we deduce

$$ \begin{aligned} \mathbb{E} \left[ \int_{0}^{T_n} \Lambda_t \left\| \frac{w_t(t)(z_{t-} - x_{t-})}{\gamma' - \gamma} \right\| dN_t \right] &\le \frac{\alpha}{\gamma' - \gamma} \sqrt{3 \left(1 + \frac{3}{2}\alpha\right) (1 + 2\alpha)n} \sqrt{2 \frac{f(x_0) - f^*}{\alpha}} \\ &= \sqrt{\alpha n} \sqrt{\frac{6 \left(1 + \frac{3}{2}\alpha\right) (1 + 2\alpha)}{\gamma}} \sqrt{f(x_0) - f^*} \\ &= \sqrt{\alpha n} \sqrt{\frac{C_\alpha}{\gamma}} \sqrt{f(x_0) - f^*}, \end{aligned} \quad (49) $$

where we used $\gamma' = \gamma + \sqrt{\gamma/2}$ and defined $C_\alpha = 6(1 + \frac{3}{2}\alpha)(1 + 2\alpha)$.

2. Bounding (43). Using Lemma 5.4 and Lemma C.2, we have

$$ \begin{aligned} & \mathbb{E} \left[ \mathbb{1}_{A_n} \alpha^2 L_2 \int_0^{T_n} \eta^2 \|z_s - x_s\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau - \sigma) dN_\sigma dN_\tau dN_t \right) ds \right] \\ &\le C L_2 \frac{(1+2\alpha)^4}{\alpha^2} \mathbb{E} \left[ \int_0^{T_n} \eta^2 \|z_s - x_s\|^2 ds \right]. \end{aligned} \quad (50) $$

From (39), we have

$$ \mathbb{E} \left[ \int_{0}^{T_n} \|z_s - x_s\|^2 ds \right] \le \frac{1}{\eta + \eta'} (f(x_0) - f^*) = \frac{1}{\alpha} (f(x_0) - f^*). \quad (51) $$

So, combining (50) and (51), we deduce

$$ \begin{aligned} & \mathbb{E} \left[ \mathbb{1}_{A_n} \alpha^2 L_2 \int_0^{T_n} \eta^2 \|z_s - x_s\|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau - \sigma) dN_\sigma dN_\tau dN_t \right) ds \right] \\ &\le C L_2 \eta^2 \frac{(1+2\alpha)^4}{\alpha^3} (f(x_0) - f^*) \\ &= C L_2 \gamma \frac{(1+2\alpha)^4}{2\alpha^3} (f(x_0) - f^*), \end{aligned} \quad (52) $$

where the last equality uses $\eta = \sqrt{\frac{\gamma}{2}}$.
**3. Bounding (44).** Using Lemma 5.4 and Lemma C.2, we have

$$
\begin{align}
& \mathbb{E} \left[ \mathbb{1}_{A_n} \alpha^2 L_2 \int_0^{T_n} \gamma^2 \| \nabla f(x_{s-}) \|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau dN_t \right) dN_s \right] \nonumber \\
& \le C \alpha^{-1} L_2 \frac{(1+2\alpha)^5}{\alpha^4} \mathbb{E} \left[ \int_0^{T_n} \gamma^2 \| \nabla f(x_{s-}) \|^2 dN_s \right] \tag{53}
\end{align}
$$

From (40), we have

$$
\mathbb{E} \left[ \int_{0}^{T_n} \| \nabla f(x_{s-}) \|^2 dN_s \right] \leq \frac{4}{\gamma} (f(x_0) - f^*). \quad (54)
$$

So, combining (53) and (54), we deduce

$$
\begin{align}
& \mathbb{E} \left[ \mathbb{1}_{A_n} \alpha^2 L_2 \int_0^{T_n} \gamma^2 \| \nabla f(x_{s-}) \|^2 \left( \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_\sigma dN_\tau dN_t \right) dN_s \right] \nonumber \\
& \le 4CL_2 \gamma \frac{(1+2\alpha)^5}{\alpha^3} (f(x_0) - f^*). \tag{55}
\end{align}
$$

Combining (49), (52) and (55), we obtain the desired result.

C.6 Control of the Denominator in (17)

In (17), we use the following control.

**Lemma C.3.** Let $\alpha = n^{-1/7}$, for $n \in \mathbb{N}$ such that $n \ge 8$. Then, we have

$$
\frac{(2+\alpha)(1+2\alpha)}{2} + \frac{(1+2\alpha)(1+\frac{3}{2}\alpha)}{2} \left(1-(1+2\alpha)^{-n}\right)n^{-\frac{6}{7}} - 2(1+\alpha)(1+2\alpha)(1-(1+\alpha)^{-n})n^{-\frac{6}{7}} \ge \frac{1}{2}.
$$

Proof. We first note that

$$
\begin{align*}
& \frac{(2+\alpha)(1+2\alpha)}{2} + \frac{(1+2\alpha)(1+\frac{3}{2}\alpha)}{2} \left(1-(1+2\alpha)^{-n}\right)n^{-\frac{6}{7}} - 2(1+\alpha)(1+2\alpha)(1-(1+\alpha)^{-n})n^{-\frac{6}{7}} \\
&= \frac{(1+2\alpha)}{2} \left(2+\alpha+(1+\frac{3}{2}\alpha)(1-(1+2\alpha)^{-n})n^{-\frac{6}{7}} - 4(1+\alpha)(1-(1+\alpha)^{-n})n^{-\frac{6}{7}}\right).
\end{align*}
$$

Then, because

$$
(1 - (1 + 2\alpha)^{-n}) \geq (1 - (1 + \alpha)^{-n}),
$$

we have

$$
\begin{align*}
& (1 + \frac{3}{2}\alpha)(1 - (1 + 2\alpha)^{-n})n^{-\frac{6}{7}} - 4(1 + \alpha)(1 - (1 + \alpha)^{-n})n^{-\frac{6}{7}} \\
&= (1 - (1 + \alpha)^{-n})n^{-\frac{6}{7}} \left( (1 + \frac{3}{2}\alpha) - 4(1 + \alpha) \right) \\
&= -(1 - (1 + \alpha)^{-n})n^{-\frac{6}{7}} \left( 3 + \frac{5}{2}\alpha \right) \\
&\geq -\frac{11}{2}n^{\frac{6}{7}}.
\end{align*}
$$

In the last inequality, we use that as $0 \le \alpha \le 1$, we have $-(1-(1+\alpha)^{-n}) \ge -1$ and $-(3+\frac{5}{2}\alpha) \ge -\frac{11}{2}$. We verify that $-\frac{11}{2}n^{\frac{6}{7}} \ge -1$, as long as $n \ge (\frac{11}{2})^{\frac{7}{6}} \approx 7.3$. So, assuming $n \ge 8$, we deduce that

$$
2 + \alpha + \left(1 + \frac{3}{2}\alpha\right)(1 - (1 + 2\alpha)^{-n})n^{-\frac{6}{7}} - 4\left(1 + \alpha\right)(1 - (1 + \alpha)^{-n})n^{-\frac{6}{7}} \geq 2 + \alpha - 1 \geq 1,
$$

and as $(1+2\alpha) \ge 1$, we conclude

$$
\frac{(1+2\alpha)}{2} \left( 2 + \alpha + \left(1 + \frac{3}{2}\alpha\right)(1 - (1+2\alpha)^{-n})n^{-\frac{6}{7}} - 4\left(1+\alpha\right)(1 - (1+\alpha)^{-n})n^{-\frac{6}{7}} \right) \ge \frac{1}{2}.
$$

□
## D Other Lemmas used to prove Theorem 4.2

In this section, we state and prove lemmas used to prove Theorem 4.2, but not explicitly stated in Section 5. We start with some elementary results.

**Lemma D.1.** Let $\alpha > 0, i \ge 1$. We have for $c > 0$

$$ \sum_{j=1}^{i} (1 + c\alpha)^{-(i-j)} = \frac{1 + c\alpha - (1 + c\alpha)^{-i+1}}{c\alpha}, $$

*Proof.*

$$ \begin{aligned} \sum_{j=1}^{i} (1 + c\alpha)^{-(i-j)} &= \sum_{k=0}^{i-1} (1 + c\alpha)^{-k} \\ &= \frac{1 - (1 + c\alpha)^{-i}}{1 - (1 + c\alpha)^{-1}} \\ &= \frac{1 + c\alpha - (1 + c\alpha)^{-i+1}}{c\alpha} \end{aligned} $$

□

**Lemma D.2.** Let $\gamma \ne 1, n \in \mathbb{N}^*$. We have

$$ \sum_{k=1}^{n} k\gamma^k = \gamma \frac{1 - (n+1)\gamma^n + n\gamma^{n+1}}{(1-\gamma)^2}. \qquad (56) $$

*Proof.* Define $\varphi(\gamma) := \sum_{k=1}^n \gamma^k = \frac{\gamma - \gamma^{n+1}}{1-\gamma}$. We have

$$ \varphi'(y) = \sum_{k=1}^{n} k\gamma^{k-1} = \frac{(1 - (n+1)\gamma^n)(1-\gamma) + \gamma - \gamma^{n+1}}{(1-\gamma)^2} = \frac{1 - (n+1)\gamma^n + n\gamma^{n+1}}{(1-\gamma)^2}. $$

Multiply by $\gamma$ allows to get (56).

□

**Lemma D.3.** Let $\gamma \ne 1, n \in \mathbb{N}^*$. We have

$$ \sum_{k=l_0}^{n} k\gamma^k = \frac{\gamma^{l_0}}{(1-\gamma)^2} (l_0 - (n+1)\gamma^{n-l_0+1})(1-\gamma) + \gamma - \gamma^{n-l_0+2} $$

*Proof.* Define $\varphi(\gamma) := \sum_{k=l_0}^n \gamma^k = \frac{\gamma^{l_0} - \gamma^{n+1}}{1-\gamma}$. We have

$$ \begin{aligned} \varphi'(\gamma) &= \sum_{k=l_0}^{n} k\gamma^{k-1} = \frac{(l_0\gamma^{l_0-1} - (n+1)\gamma^n)(1-\gamma) + \gamma^{l_0} - \gamma^{n+1}}{(1-\gamma)^2} \\ &= \frac{\gamma^{l_0-1}}{(1-\gamma)^2} (l_0 - (n+1)\gamma^{n-l_0+1})(1-\gamma) + \gamma - \gamma^{n-l_0+2}. \end{aligned} $$

Multiplying both sides by $\gamma$ gives the result.

□

**Lemma D.4.** If $i \le j$, we have

$$ \mathbb{E}[e^{-\alpha(T_j - T_i)}] = (1 + \alpha)^{-j+i}. $$
*Proof.* It is trivially true if $i = j$. If $i < j$, we have

$$e^{-\alpha(T_j - T_i)} = \prod_{k=0}^{j-i-1} e^{-\alpha(T_{k+i+1} - T_{k+i})}$$

By independence of the $T_{k+1} - T_k$ for all $k$, we have

$$\mathbb{E} \left[ \prod_{k=0}^{j-i-1} e^{-\alpha(T_{k+i+1} - T_{k+i})} \right] = \prod_{k=0}^{j-i-1} \mathbb{E} \left[ e^{-\alpha(T_{i+j+1} - T_{i+j})} \right].$$

Recall $T_{k+1} - T_k$ for all $k$ follows an exponential law with parameter 1, such that we have $\mathbb{E}[e^{-\alpha(T_{i+j+1} - T_{i+j})}] = (1 + \alpha)^{-1}$. So,

$$\prod_{k=0}^{j-i-1} \mathbb{E} \left[ e^{-\alpha(T_{i+j+1} - T_{i+j})} \right] = \prod_{k=0}^{j-i-1} (1 + \alpha)^{-1} \\ = (1 + \alpha)^{-j+i}.$$

□

**Lemma D.5.** For $n \ge 1$, $\alpha > 0$, we have:

(i) The following upper bound

$$\mathbb{E} \left[ \int_{0}^{T_n} \left( \int_{0}^{t} \alpha e^{\alpha(s-t)} dN_s \right)^2 dN_t \right] \le \left(1 + \frac{3}{2}\alpha\right) (1 + 2\alpha)n.$$

(ii) The following equality

$$\mathbb{E} \left[ \int_{0}^{T_n} \left( \int_{0}^{t} \alpha e^{\alpha(s-t)} dN_s \right)^2 dN_t \right] \\ = \frac{(2+\alpha)(1+2\alpha)}{2} n + \frac{(1+2\alpha)(1+\frac{3}{2}\alpha)}{2\alpha} (1 - (1+2\alpha)^{-n}) \\ - \frac{2(1+\alpha)(1+2\alpha)}{\alpha} (1 - (1+\alpha)^{-n})$$

*Proof. Point (i)* We have

$$\int_{0}^{T_n} \left( \int_{0}^{t} \alpha e^{\alpha(s-t)} dN_s \right)^2 dN_t = \sum_{i=1}^{n} \left( \sum_{j=1}^{i} \alpha e^{\alpha(T_j - T_i)} \right)^2 \\ = \alpha^2 \sum_{i=1}^{n} \sum_{j=1}^{i} e^{-2\alpha(T_i - T_j)} + 2\alpha^2 \sum_{i=1}^{n} \sum_{1 \le j < l \le i} e^{-\alpha(T_i - T_j)} e^{-\alpha(T_l - T_i)}. \qquad (57)$$

We focus on the first term in (57). We have by using Lemma D.4 and Lemma D.1 ($c = 2$)

$$\mathbb{E} \left[ \alpha^2 \sum_{i=1}^{n} \sum_{j=1}^{i} e^{-2\alpha(T_i - T_j)} \right] = \alpha^2 \sum_{i=1}^{n} \sum_{j=1}^{i} \mathbb{E} \left[ e^{-2\alpha(T_i - T_j)} \right] \\ = \alpha^2 \sum_{i=1}^{n} \sum_{j=1}^{i} (1 + 2\alpha)^{-(i-j)} \\ = \alpha^2 \sum_{i=1}^{n} \frac{1 + 2\alpha - (1 + 2\alpha)^{-i+1}}{2\alpha}$$
Omitting the non positive term, we have

$$ \mathbb{E} \left[ \alpha^2 \sum_{i=1}^{n} \sum_{j=1}^{i} e^{-2\alpha(T_i - T_j)} \right] \leq \alpha n \frac{1 + 2\alpha}{2}. $$

We focus on the second term of (57). We have

$$ 2\alpha^2 \sum_{i=1}^{n} \sum_{1 \le j < l \le i} e^{-\alpha(T_i - T_j)} e^{-\alpha(T_i - T_l)} = 2\alpha^2 \sum_{i=1}^{n} \sum_{1 \le j < l \le i} e^{-2\alpha(T_i - T_l)} e^{-\alpha(T_l - T_j)} $$

We take expectation and we use Lemma D.4

$$ \begin{aligned} 2\alpha^2 \mathbb{E} \left[ \sum_{i}^{n} \sum_{1 \le j < l \le i} e^{-\alpha(T_i - T_j)} e^{-\alpha(T_i - T_l)} \right] &= 2\alpha^2 \sum_{i=1}^{n} \sum_{1 \le j < l \le i} \mathbb{E} \left[ e^{-2\alpha(T_i - T_l)} e^{-\alpha(T_l - T_j)} \right] \\ &= 2\alpha^2 \sum_{i=1}^{n} \sum_{1 \le j < l \le i} \mathbb{E} \left[ e^{-2\alpha(T_i - T_l)} \right] \mathbb{E} \left[ e^{-\alpha(T_l - T_j)} \right] \\ &= 2\alpha^2 \sum_{i=1}^{n} \sum_{1 \le j < l \le i} (1 + 2\alpha)^{-(i-l)} (1 + \alpha)^{-(l-j)} \\ &= 2\alpha^2 \sum_{i=1}^{n} \sum_{l=1}^{i} \sum_{j=1}^{l-1} (1 + 2\alpha)^{-(l-j)} (1 + \alpha)^{-(i-j)}. \end{aligned} $$

Now, using twice Lemma D.1 with $c=1$ and $c=2$, and omitting non negative terms

$$ \begin{aligned} 2\alpha^2 \sum_{i=1}^{n} \sum_{l=1}^{i} \sum_{j=1}^{l-1} (1 + 2\alpha)^{-(i-l)} (1 + \alpha)^{-(i-j)} &= 2\alpha^2 \sum_{i=1}^{n} \sum_{l=1}^{i} (1 + 2\alpha)^{-(i-l)} \sum_{j=1}^{l-1} (1 + \alpha)^{-(l-j)} \\ &= 2\alpha^2 \sum_{i=1}^{n} \sum_{l=1}^{i} (1 + 2\alpha)^{-(i-l)} \left( \frac{1 + \alpha - (1 + \alpha)^{-i+1}}{\alpha} \right) \\ &\le 2\alpha(1 + \alpha) \sum_{i=1}^{n} \sum_{l=1}^{i} (1 + 2\alpha)^{-(i-l)} \\ &= 2\alpha(1 + \alpha) \sum_{i=1}^{n} \left( \frac{1 + 2\alpha - (1 + 2\alpha)^{-i+1}}{2\alpha} \right) \\ &\le (1 + \alpha)(1 + 2\alpha)n \end{aligned} $$

We then deduce that

$$ 2\alpha^2 \mathbb{E} \left[ \sum_{i}^{n} \sum_{1 \le j < l \le i} e^{-\alpha(T_i - T_j)} e^{-\alpha(T_i - T_l)} \right] \le (1 + \alpha)(1 + 2\alpha)n. $$

Finally, we have the bound

$$ \begin{aligned} \mathbb{E} \left[ \int_{0}^{T_n} \left( \int_{0}^{t} \alpha e^{\alpha(s-t)} dN_s \right)^2 dN_t \right] &\le \alpha \frac{1+2\alpha}{2} n + (1+\alpha)(1+2\alpha)n \\ &= \left(1+\frac{3}{2}\alpha\right) (1+2\alpha)n. \end{aligned} $$
**Point (ii)** Let $Y_k = (\int_{[0,T_k]} \alpha e^{\alpha(s-T_k)} dNs)^2$. We have

$$ 
\begin{aligned}
Y_{k+1} &= \left( \int_{[0,T_{k+1}]} \alpha e^{\alpha(s-T_{k+1})} dNs \right)^2 \\
&= \left( e^{\alpha(T_k-T_{k+1})} \int_{[0,T_k]} \alpha e^{\alpha(s-T_k)} dNs + \int_{[T_k,T_{k+1}]} \alpha e^{\alpha(s-T_{k+1})} dNs \right)^2.
\end{aligned}
$$

We have $\int_{[T_k,T_{k+1}]} \alpha e^{\alpha(s-T_{k+1})} dNs = \alpha$. So

$$ Y_{k+1} = e^{2\alpha(T_k - T_{k+1})} Y_k + 2\alpha e^{\alpha(T_k - T_{k+1})} \int_{[0,T_k]} \alpha e^{\alpha(s-T_k)} dNs + \alpha^2. $$

We take the expectation

$$ 
\begin{aligned}
\mathbb{E}[Y_{k+1}] &= \mathbb{E} \left[ e^{2\alpha(T_k - T_{k+1})} Y_k + 2\alpha e^{\alpha(T_k - T_{k+1})} \int_{[0,T_k]} \alpha e^{\alpha(s-T_k)} dNs + \alpha^2 \right] \\
&= \mathbb{E} \left[ e^{2\alpha(T_k - T_{k+1})} Y_k \right] + 2\alpha \mathbb{E} \left[ e^{\alpha(T_k - T_{k+1})} \int_{[0,T_k]} \alpha e^{\alpha(s-T_k)} dNs \right] + \alpha^2 \\
&= \mathbb{E} \left[ e^{2\alpha(T_k - T_{k+1})} \right] \mathbb{E}[Y_k] + 2\alpha \mathbb{E} \left[ e^{\alpha(T_k - T_{k+1})} \right] \mathbb{E} \left[ \int_{[0,T_k]} \alpha e^{\alpha(s-T_k)} dNs \right] + \alpha^2 \\
&= (1 + 2\alpha)^{-1} \mathbb{E}[Y_k] + 2\alpha(1 + \alpha)^{-1}(1 + \alpha - (1 + \alpha)^{-k+1}) + \alpha^2 \\
&= (1 + 2\alpha)^{-1} \mathbb{E}[Y_k] + 2\alpha(1 - (1 + \alpha)^{-k}) + \alpha^2 \\
&= (1 + 2\alpha)^{-1} \mathbb{E}[Y_k] - 2\alpha(1 + \alpha)^{-k} + \alpha(2 + \alpha).
\end{aligned}
$$

Noting $u_k := \mathbb{E}[Y_k]$, we get a recursive formula of the form

$$ u_{k+1} = au_k + b_k + c, $$

whose solution is given by

$$ u_k = a^k \sum_{i=0}^{k-1} \frac{b_i + c}{a^{i+1}} = \sum_{i=0}^{k-1} (b_i + c) a^{k-i-1}. \quad (58) $$

We compute (58) in two steps. We start with

$$ 
\begin{aligned}
\sum_{i=0}^{k-1} ca^{k-i-1} &= c \sum_{j=0}^{k-1} a^j \\
&= c \frac{1-a^k}{1-a} \qquad (59) \\
&= \alpha(2+\alpha) \frac{1-(1+2\alpha)^{-k}}{1-(1+2\alpha)^{-1}} \\
&= \frac{(2+\alpha)(1+2\alpha)}{2} - \frac{2+\alpha}{2} (1+2\alpha)^{-k+1}.
\end{aligned}
$$

Then, we have

$$ 
\begin{aligned}
a^{k-1} \sum_{i=0}^{k-1} \frac{b_i}{a^i} &= -2\alpha a^{k-1} \sum_{i=0}^{k-1} \left( \frac{1+2\alpha}{1+\alpha} \right)^i \\
&= -2\alpha a^{k-1} \left( 1 - \left( \frac{1+2\alpha}{1+\alpha} \right)^k \right) \left( 1 - \left( \frac{1+2\alpha}{1+\alpha} \right)^{-1} \right)^{-1} \qquad (60) \\
&= 2(1+\alpha) (a^{k-1} - a^{-1}(1+\alpha)^{-k}) \\
&= 2(1+\alpha)(1+2\alpha)((1+2\alpha)^{-k} - (1+\alpha)^{-k}) \\
&= 2(1+\alpha)(1+2\alpha)(1+2\alpha)^{-k} - 2(1+\alpha)(1+2\alpha)(1+\alpha)^{-k}.
\end{aligned}
$$
Injecting (59) and (60) into (58), we get the following expression for $u_k$

$$
\begin{align*}
u_k &= \frac{(2+\alpha)(1+2\alpha)}{2} - \frac{2+\alpha}{2}(1+2\alpha)^{-k+1} + 2(1+\alpha)(1+2\alpha)(1+2\alpha)^{-k} \\
&\quad - 2(1+\alpha)(1+2\alpha)(1+\alpha)^{-k} \\
&= \frac{(2+\alpha)(1+2\alpha)}{2} + \left(-\frac{(2+\alpha)(1+2\alpha)}{2} + 2(1+\alpha)(1+2\alpha)\right)(1+2\alpha)^{-k} \\
&\quad - 2(1+\alpha)(1+2\alpha)(1+\alpha)^{-k} \\
&= \frac{(2+\alpha)(1+2\alpha)}{2} + (1+2\alpha)(1+\frac{3}{2}\alpha)(1+2\alpha)^{-k} - 2(1+\alpha)(1+2\alpha)(1+\alpha)^{-k}.
\end{align*}
$$

It remains to sum over $k = 0, \dots, n$, to get

$$
\sum_{k=1}^{n} u_k = \frac{(2+\alpha)(1+2\alpha)}{2} n + \frac{(1+2\alpha)(1+\frac{3}{2}\alpha)}{2\alpha} (1-(1+2\alpha)^{-n}) \\ - \frac{2(1+\alpha)(1+2\alpha)}{\alpha} (1-(1+\alpha)^{-n}).
$$

To conclude, remark that

$$
\mathbb{E} \left[ \int_0^{T_n} \left( \int_0^t \alpha e^{\alpha(s-t)} dN_s \right)^2 dN_t \right] = \sum_{k=1}^n \mathbb{E} \left[ \left( \int_{[0,T_k]} \alpha e^{\alpha(s-T_k)} dN_s \right)^2 \right] = \sum_{k=1}^n \mathbb{E} [Y_k] = \sum_{k=1}^n u_k.
$$

□

D.1 Proof of Lemma C.2

We recall

$$
A_k := \int_{[T_k, T_n]} \int_{[T_k, t]} \int_{[0, T_k]} e^{\alpha(T_k-t)} e^{\alpha(\tau-t)} e^{\alpha(\sigma-T_k)} (\tau - \sigma) dN_{\sigma} dN_{\tau} dN_t,
$$

$$
B_k := \int_{T_k}^{T_n} \int_{T_k}^{t} \int_{0}^{T_k} e^{\alpha(\tau-t)} e^{\alpha(T_k-t)} e^{\alpha(\sigma-T_k)} (N_{\tau-} - N_{\sigma-}) dN_{\sigma} dN_{\tau} dN_t.
$$

We will split the proof in several sub lemmas. We first bound $\max_{k \in \{1, \dots, n\}} \mathbb{E}[B_k]$.

**Lemma D.6.** We have

$$
\begin{align*}
\max_{s \in \{T_1, \dots, T_n\}} \mathbb{E} \left[ \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_{\sigma} dN_{\tau} dN_t \right] \\
&\le \max \left\{ \frac{(1+2\alpha)(1+\alpha)^4}{2\alpha^4}, \frac{(1+2\alpha)(1+\alpha)^3}{\alpha^4} \right\} \\
&\le \frac{(1+2\alpha)^5}{\alpha^4}
\end{align*}
$$

Proof. Let $s = T_k$, $k \le n$.

$$
\begin{align*}
& \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_{\sigma} dN_{\tau} dN_t \\
&= \int_{T_k}^{T_n} \int_{T_k}^t \int_0^t T_k e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_{\sigma} dN_{\tau} dN_t \\
&= \sum_{i=k}^n \sum_{j=1}^k \sum_{l=k}^i e^{\alpha(T_l-T_i)} e^{\alpha(T_j-T_i)} (l-j) \\
&= \sum_{i=k}^n \sum_{j=1}^k \sum_{l=k}^i e^{2\alpha(T_l-T_i)} e^{\alpha(T_j-T_l)} (l-j).
\end{align*}
$$
We take expectation, use $T_l - T_i \perp T_j - T_l$ and Lemma D.4

$$
\begin{align}
\mathbb{E} \left[ \sum_{i=k}^{n} \sum_{j=1}^{k} \sum_{l=k}^{i} e^{2\alpha(T_l - T_i)} e^{\alpha(T_j - T_l)} (l-j) \right] &= \sum_{i=k}^{n} \sum_{j=1}^{k} \sum_{l=k}^{i} \mathbb{E} [e^{2\alpha(T_l - T_i)}] \mathbb{E} [e^{\alpha(T_j - T_l)}] (l-j) \tag{61} \\
&= \sum_{i=k}^{n} \sum_{j=1}^{k} \sum_{l=k}^{i} (1+2\alpha)^{(k-i)} (1+\alpha)^{(j-l)} (l-j) \nonumber \\
&= \sum_{i=k}^{n} \sum_{l=k}^{i} (1+2\alpha)^{(k-i)} \sum_{j=1}^{k} (1+\alpha)^{-(l-j)} (l-j). \nonumber
\end{align}
$$

Noting $(1+\alpha)^{-1} = \gamma$ we have

$$
\sum_{j=1}^{k} (1+\alpha)^{-(l-j)} (l-j) = \sum_{j'=l-k}^{l-1} \gamma^{j'} j' = \frac{\gamma^{l-k-1}}{(1-\gamma)^2} (l-k-l\gamma^k)(1-\gamma) + \gamma - \gamma^{k+1}).
$$

So

$$
\begin{align}
& \mathbb{E} \left[ \sum_{i=k}^{n} \sum_{j=1}^{k} \sum_{l=k}^{i} e^{2\alpha(T_l - T_i)} e^{\alpha(T_j - T_l)} (l-j) \right] \nonumber \\
&= \sum_{i=k}^{n} \sum_{l=k}^{i} (1+2\alpha)^{(k-i)} \frac{\gamma^{l-k-1}}{(1-\gamma)^2} (l-k-l\gamma^k)(1-\gamma) + \gamma - \gamma^{k+1} \nonumber \\
&= \frac{1}{(1-\gamma)^2} \sum_{i=k}^{n} (1+2\alpha)^{k-i} \sum_{l'=0}^{i-k} (1+2\alpha)^{l'} \gamma^{l'-1} (l' - (l'+k)\gamma^k)(1-\gamma) + \gamma - \gamma^{k+1} \nonumber \\
&\le \frac{1}{(1-\gamma)^2} \sum_{i=k}^{n} (1+2\alpha)^{k-i} \sum_{l'=0}^{i-k} (1+2\alpha)^{l'} \gamma^{l'-1} (l'(1-\gamma) + \gamma - \gamma^{k+1}) \nonumber \\
&\le \frac{1}{(1-\gamma)^2} \sum_{i=k}^{n} (1+2\alpha)^{k-i} \sum_{l'=0}^{i-k} (1+2\alpha)^{l'} \gamma^{l'-1} (l'(1-\gamma) + \gamma) \tag{62}
\end{align}
$$

We split the right hand side of (62).

$$
\begin{align*}
& \frac{1}{(1-\gamma)^2} \sum_{i=k}^{n} (1+2\alpha)^{k-i} \sum_{l'=0}^{i-k} (1+2\alpha)^{l'} \gamma^{l'} \\
&= \frac{(1+\alpha)^2}{\alpha^2} \sum_{i=k}^{n} (1+2\alpha)^{k-i} \sum_{l'=0}^{i-k} \left(\frac{1+2\alpha}{1+\alpha}\right)^{l'} \\
&\le \frac{(1+\alpha)^2}{\alpha^2} \sum_{i=k}^{n} (1+2\alpha)^{k-i} \left(\frac{1+2\alpha}{1+\alpha}\right)^{i-k+1} \left(\frac{1+2\alpha}{1+\alpha}-1\right)^{-1} \\
&= \frac{(1+2\alpha)(1+\alpha)^2}{\alpha^3} \sum_{i=k}^{n} (1+\alpha)^{-(i-k)} \\
&\le \frac{(1+2\alpha)(1+\alpha)^3}{\alpha^4}
\end{align*}
$$
Consider

$$
\begin{align*}
& \frac{1}{(1-\gamma)^2} \sum_{i=k}^{n} (1+2\alpha)^{k-i} \sum_{l'=0}^{i-k} (1+2\alpha)^{l'} \gamma^{l'-1} l' (1-\gamma) \\
&= \frac{\gamma^{-1}}{1-\gamma} \sum_{i=k}^{n} (1+2\alpha)^{k-i} \sum_{l'=0}^{i-k} \left(\frac{1+2\alpha}{1+\alpha}\right)^{l'} l' \\
&= \frac{(1+\alpha)^2}{\alpha} \sum_{i=k}^{n} (1+2\alpha)^{k-i} \sum_{l'=0}^{i-k} \left(\frac{1+2\alpha}{1+\alpha}\right)^{l'} l',
\end{align*}
$$

using $\gamma^{-1} = (1+\alpha)$. Now apply Lemma D.2 with $\gamma = \frac{1+2\alpha}{1+\alpha}$

$$
\sum_{l'=0}^{i-k} \left( \frac{1+2\alpha}{1+\alpha} \right)^{l'} l' = \frac{1-\gamma^{i-k} + (i-k)\gamma^{-(i-k)}(\gamma-1)}{(1-\gamma)^2}.
$$

We split it into two terms:

$$
\begin{align*}
& \frac{(1+\alpha)^2}{\alpha} \sum_{i=k}^{n} (1+2\alpha)^{k-i} (i-k) \left(\frac{1+2\alpha}{1+\alpha}\right)^{-(i-k)} \frac{1}{1-\frac{1+2\alpha}{1+\alpha}} \\
&= \frac{(1+\alpha)^3}{\alpha^2} \sum_{i=k}^{n} (i-k)(1+\alpha)^{-(i-k)} \\
&= \frac{(1+\alpha)^3}{\alpha^2} \sum_{i'=1}^{n-k} i' (1+\alpha)^{-i'} \\
&\le \frac{(1+\alpha)^3}{\alpha^2} \frac{(1+\alpha)^{-1}}{(1-(1+\alpha)^{-1})^2} \\
&= \frac{(1+\alpha)^4}{\alpha^4}.
\end{align*}
$$

and,

$$
\begin{align*}
\frac{(1+\alpha)^2}{\alpha} \sum_{i=k}^{n} (1+2\alpha)^{k-i} \frac{1}{\left(1-\frac{1+2\alpha}{1+\alpha}\right)^2} &\le \frac{(1+\alpha)^4}{\alpha^3} \sum_{i=k}^{n} (1+2\alpha)^{k-i} \\
&= \frac{(1+\alpha)^3}{\alpha^2} \frac{1-(1+2\alpha)^{-(n-i)}}{1-(1+2\alpha)^{-1}} \\
&\le \frac{(1+2\alpha)(1+\alpha)^4}{2\alpha^4}.
\end{align*}
$$

So, we have that

$$
\max_{s \in \{0, T_1, \dots, T_n\}} \mathbb{E} \left[ \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (N_{\tau-} - N_{\sigma-}) dN_{\sigma} dN_{\tau} dN_t \right] \\
\le \max \left\{ \frac{(1+2\alpha)(1+\alpha)^4}{2\alpha^4}, \frac{(1+2\alpha)(1+\alpha)^3}{\alpha^4} \right\}
$$

□

We now turn to $\max_{k \in \{0, \dots, n\}} \mathbb{E}[A_k]$. The computations are similar, thanks to the following elementary result.

**Lemma D.7.** If $T_n \sim \Gamma(n, 1)$, then

$$
\mathbb{E}[T_n e^{-\alpha T_n}] = \frac{n}{(1+\alpha)^{n+1}}
$$
Proof. Let $\varphi(\alpha) = \mathbb{E}[e^{-\alpha T_n}]$ the moment-generating function of $T_n$. As $T_n \sim \Gamma(n, 1)$, we have
$\phi(\alpha) = (1+\alpha)^{-n} \Rightarrow \phi'(\alpha) = -(1+\alpha)^{-n-1}$. So

$$
\phi(\alpha) = -\mathbb{E}[T_n e^{-\alpha T_n}] \Rightarrow \mathbb{E}[T_n e^{-\alpha T_n}] = \frac{n}{(1+\alpha)^{n+1}}.
$$

□

**Lemma D.8.** *We have*

$$
\begin{align*}
\max_{s \in \{0, T_1, \dots, T_n\}} \mathbb{E} \left[ \int_s^{T_n} \int_s^t \int_0^s e^{\alpha(\tau-t)} e^{\alpha(\sigma-t)} (\tau - \sigma) dN_\sigma dN_\tau dN_t \right] \\
&\le \max \left\{ \frac{(1+2\alpha)(1+\alpha)^3}{2\alpha^4}, \frac{(1+2\alpha)(1+\alpha)^2}{\alpha^4} \right\} \\
&\le \frac{(1+2\alpha)^4}{\alpha^4}
\end{align*}
$$

Proof. The proof is almost identical to the one of Lemma D.6. The only difference lies in (61), where $l-j$ is replaced by $T_l - T_j$. Then, a direct application of Lemma D.7 gives $\mathbb{E}[T_n e^{-\alpha T_n}] = (1+\alpha)^{-1} \mathbb{E}[ne^{-\alpha T_n}]$ for some $T_n \sim \Gamma(n, 1)$. $\square$

E Proof of Lemma 3.1 and Proposition 3.2

We prove a more general result than Lemma 3.1 and Proposition 3.2, by considering a version of
(CNE) with stochastic estimates of the gradient, namely

$$
\left\{
\begin{aligned}
dx_t &= \eta(z_t - x_t)dt - \gamma \int_{\Xi} \nabla f(x_t, \xi) dN(t, \xi) \\
dz_t &= \eta'(x_t - z_t)dt - \gamma' \int_{\Xi} \nabla f(x_t, \xi) dN(t, \xi)
\end{aligned}
\right.
\qquad (63)
$$

with the Poisson point measure $dN_t = \sum_{k>0} \delta_{T_k, \xi_k}(dt, d\xi)$ on $\mathbb{R}_+ \times \Xi$, which has intensity $dt \otimes \mathcal{P}$, for some law $\mathcal{P}$ over a space $\Xi$. These equations are associated with a similar formulation of (CNA), with a stochastic estimate of the gradient

$$
\left\{
\begin{aligned}
\tilde{y}_k &= (\tilde{z}_k - \tilde{x}_k) \frac{\eta}{\eta+\eta'} (1 - e^{-(\eta+\eta')(T_{k+1}-T_k)}) + \tilde{x}_k \\
\tilde{x}_{k+1} &= \tilde{y}_k - \gamma \nabla f(\tilde{y}_k, \xi_{k+1}) \\
\tilde{z}_{k+1} &= \tilde{z}_k + \eta' \frac{(1-e^{-(\eta+\eta')(T_{k+1}-T_k)})}{\eta'+\eta e^{-(\eta+\eta')(T_{k+1}-T_k)}} (\tilde{y}_k - \tilde{z}_k) - \gamma' \nabla f(\tilde{y}_k, \xi_{k+1})
\end{aligned}
\right.
\qquad (64)
$$

See a proof in [31]. We use the following assumption on our estimates of the gradient.

**Assumption E.1 (Strong growth condition).** We assume we have access to stochastic approxi-
mations $\nabla f(x, \xi)$ of the real gradient $\nabla f(x)$, where $\xi \sim \mathcal{P}(\Xi)$, such that

(i) (Unbiased estimator) $\forall x \in \mathbb{R}^d$, $\mathbb{E}[\nabla f(x, \xi)] = \nabla f(x)$.

(ii) (Strong Growth Condition) $\exists \rho \ge 1, \forall x \in \mathbb{R}^d$, $\mathbb{E}_\xi [\|\nabla f(x, \xi)\|^2] \le \rho \|\nabla f(x)\|^2$.

Observe that our statement for Lemma 3.1 and Proposition 3.2 will follow by taking $\rho = 1$ in Assumption E.1, thus reducing to the deterministic gradient case. Under Assumption 2.1 and E.1, we have a stochastic descent lemma, see [28, Lemma 16].

**Lemma E.2.** Under Assumption 2.1 and E.1, if $\gamma \le \frac{1}{L\rho}$, we have

$$
\mathbb{E}_{\xi} [f(x - \gamma \nabla f(x, \xi)) - f(x)] \leq \gamma \left( \frac{L\rho}{2} - 1 \right) \|\nabla f(x)\|^2.
$$

To perform Lyapunov analysis, our tool is the following Itô formula.
**Proposition E.3** ([22], Proposition 2). Let $\varphi: \mathbb{R}^d \times \Xi \to \mathbb{R}$ be a smooth function.
Then we have

$$ \int_{[0,t]\times\Xi} \varphi(x_{s^{-}}, \xi) dN(s, \xi) = \int_{[0,t]\times\Xi} \varphi(x_s, \xi) ds d\mathcal{P}(\xi) + M_t $$

where $M_t = \int_{[0,t]\times\Xi} \varphi(x_{s^{-}}, \xi)(dN(s, \xi) - dtd\mathcal{P}(\xi))$ is a martingale.

**Lemma E.4.** If $(x_t, z_t)$ solutions of (63) with $\gamma \le \frac{1}{\rho L}$, $\gamma' = \gamma_+\sqrt{\frac{\gamma}{2\rho}}$, $\eta = \gamma' - \gamma$ and $\eta' \ge -\eta$, under Assumptions 2.1-E.1, we have

$$ \mathbb{E} \left[ \min_{s \in [0,t]} \| \nabla f(x_{s^{-}}) \|^2 \right] \le \frac{4(f(x_0) - f^*)}{\gamma t}. $$

*Proof.* Let $\bar{x}_t = (x_t, z_t)$ where $(x_t, z_t)_{t \in \mathbb{R}_+}$ satisfy (63). It satisfies $d\bar{x}_t = b(\bar{x}_t)dt + G(\bar{x}_t, \xi)dN(t, \xi)$, where

$$ b(\bar{x}_t) = \begin{pmatrix} \eta(z_t - x_t) \\ \eta'(x_t - z_t) \end{pmatrix}, \quad G(\bar{x}_t, \xi) = \begin{pmatrix} -\gamma_t \nabla f(x_t, \xi) \\ -\gamma'_t \nabla f(x_t, \xi) \end{pmatrix} $$

We apply Proposition E.3 to $\varphi(\bar{x}_t)$, where

$$ \varphi(x, z) = f(x) + \frac{1}{2} \|x - z\|^2, $$

inducing

$$ \varphi(\bar{x}_t) = \varphi(\bar{x}_0) + \int_0^t \langle \nabla \varphi(\bar{x}_s), b(\bar{x}_s) \rangle ds + \int_0^t \mathbb{E}_\xi (\varphi(\bar{x}_s + G(\bar{x}_s, \xi)) - \varphi(\bar{x}_s)) ds + M_t, \quad (65) $$

where $M_t$ is a martingale.

**Computations** We compute $\langle \nabla \varphi(\bar{x}_s), b(\bar{x}_s) \rangle$ and $\mathbb{E}_\xi \varphi(\bar{x}_s + G(\bar{x}_s)) - \varphi(\bar{x}_s)$. We have

$$ \frac{\partial \varphi}{\partial x} = \nabla f(x) + x - z, \quad \frac{\partial \varphi}{\partial z} = z - x. $$

So,

$$ \begin{aligned} \langle \nabla \varphi(\bar{x}_s), b(\bar{x}_s) \rangle &= \langle \nabla f(x_s) + x_s - z_s, \eta(z_s - x_s) \rangle + \langle z_s - x_s, \eta'(x_s - z_s) \rangle \\ &= \eta \langle \nabla f(x_s), z_s - x_s \rangle - (\eta + \eta') \|x_s - z_s\|^2. \end{aligned} \quad (66) $$

Also,

$$ \begin{aligned} \mathbb{E}_{\xi}\varphi(\bar{x}_s + G(\bar{x}_s)) - \varphi(\bar{x}_s) &= \mathbb{E}_{\xi}[f(x_s - \gamma\nabla f(x_s, \xi)) - f(x_s)] \\ &\quad + \frac{1}{2}\mathbb{E}_{\xi}\left[\|x_s - \gamma\nabla f(x_s, \xi) - (z_s - \gamma'\nabla f(x_s, \xi))\|^2 - \|x_s - z_s\|^2\right] \\ &= \mathbb{E}_{\xi}[f(x_s - \gamma\nabla f(x_s, \xi)) - f(x_s)] + \frac{(\gamma' - \gamma)^2}{2}\mathbb{E}_{\xi}[\|\nabla f(x_s, \xi)\|^2] \\ &\quad + (\gamma' - \gamma)\langle\mathbb{E}_{\xi}[\nabla f(x_s, \xi)], x_s - z_s\rangle \\ &\le (\rho(\gamma' - \gamma)^2 - \gamma(2 - L\gamma\rho))\frac{1}{2}\|\nabla f(x_s)\|^2 \\ &\quad + (\gamma' - \gamma)\langle\nabla f(x_s), x_s - z_s\rangle. \end{aligned} \quad (67) $$

The last inequality uses Assumption E.1 and Lemma E.2, assuming $\gamma \le \frac{1}{\rho L}$. We combine (66) and (67)

$$ \begin{aligned} & \langle \nabla \varphi(\bar{x}_s), b(\bar{x}_s) \rangle + \mathbb{E}_{\xi} \varphi(\bar{x}_s + G(\bar{x}_s)) - \varphi(\bar{x}_s) \\ & \le (\eta - (\gamma' - \gamma)) \langle \nabla f(x_{s^{-}}), z_s - x_s \rangle - (\eta + \eta') \|x_s - z_s\|^2 \\ & \quad + (\rho(\gamma' - \gamma)^2 - \gamma(2 - L\gamma\rho)) \frac{1}{2} \|\nabla f(x_s)\|^2 \end{aligned} \quad (68) $$
**Parameter tuning** As it is standard in convergence proof, we now choose the parameters driving (63) such that we obtain the desired result. We set $\eta = \gamma' - \gamma$ to cancel scalar product. Then fixing $\gamma' = \gamma + \sqrt{\frac{\gamma}{2\rho}}$ ensures

$$ \rho(\gamma' - \gamma)^2 - \gamma(2 - L\gamma\rho) \leq \frac{\gamma}{2} - \gamma = -\frac{\gamma}{2}. $$

The latter holds because $\gamma \leq \frac{1}{\rho L} \Rightarrow -\gamma(2 - L\rho\gamma) \leq -\gamma$. We thus have

$$ \langle \nabla \varphi(\bar{x}_s), b(\bar{x}_s) \rangle + \mathbb{E}_{\xi} [\varphi(\bar{x}_s + G(\bar{x}_s)) - \varphi(\bar{x}_s)] \leq -(\eta + \eta') \|x_s - z_s\|^2 - \frac{\gamma}{4} \|\nabla f(x_s)\|^2. \quad (69) $$

**Conclusion** Combining (69), (68) and (65), we get

$$ \begin{aligned} \varphi(\bar{x}_t) &\leq \varphi(\bar{x}_0) + \int_0^t -(\eta + \eta') \|x_s - z_s\|^2 - \frac{\gamma}{4} \|\nabla f(x_s)\|^2 ds + M_t \\ &\Rightarrow \int_0^t (\eta + \eta') \|x_s - z_s\|^2 + \frac{\gamma}{4} \|\nabla f(x_s)\|^2 ds \leq f(x_0) - f^* + M_t, \end{aligned} \quad (70) $$

using $\varphi(\bar{x}_0) - \varphi(\bar{x}_t) \leq f(x_0) - \min_x f(x)$ and that $x_0 = z_0$. It remains to take expectation on (70)

$$ \mathbb{E} \left[ \int_0^t (\eta + \eta') \|x_s - z_s\|^2 + \frac{\gamma}{4} \|\nabla f(x_s)\|^2 ds \right] \leq \mathbb{E} [f(x_0) - f^*], $$

where we used $\mathbb{E}[M_t] = \mathbb{E}[M_0] = 0$. $\square$

**Proposition E.5.** Assume $T_1, \dots, T_k$ are random variables such that $T_{i+1} - T_i$ are i.i.d of law $\mathcal{E}(1)$, with convention $T_0 = 0$. Under Assumptions 2.1 and E.1, iterations of (64) with $\gamma \leq \frac{1}{\rho L}$, $\gamma' = \gamma + \sqrt{\frac{\gamma}{2\rho}}$, $\eta = \sqrt{\frac{\gamma}{2\rho}}$ and $\eta' > -\eta$ verify

$$ \mathbb{E} \left[ \min_{0 \leq i \leq k-1} \|\nabla f(\tilde{y}_i)\|^2 \right] \leq \frac{4}{\gamma} \frac{(f(x_0) - f^*)}{k}. $$

*Proof.* From (70), we have

$$ \int_0^t \frac{\gamma}{4} \|\nabla f(x_s)\|^2 ds \leq f(x_0) - f^* + M_t. $$

Also, we have

$$ \int_0^t \frac{\gamma}{4} \|\nabla f(x_s)\|^2 ds = \int_0^t \frac{\gamma}{4} \|\nabla f(x_{s-})\|^2 dN_s + \int_0^t \frac{\gamma}{4} \|\nabla f(x_{s-})\|^2 (ds - dN_s), \quad (71) $$

where $\int_0^t \frac{\gamma}{4} \|\nabla f(x_{s-})\|^2 (ds - dN_s)$ is a centered martingale. Then, there exists a centered martingale $U_t$ such that

$$ \int_0^t \frac{\gamma}{4} \|\nabla f(x_{s-})\|^2 dN_s \leq f(x_0) - f^* + U_t. $$

We use the following stopping theorem.

**Theorem E.6 ([31], Theorem 6).** Let $(\varphi_t)_{t \in \mathbb{R}_+}$ be a nonnegative process with cadlag trajectories, such that it verifies

$$ \varphi_t \leq K_0 + M_t, $$

for some positive random variable $K_0$, some martingale $(M_t)_{t \geq 0}$ with $M_0 = 0$. Then, for an almost surely finite stopping time $\tau$, one has

$$ \mathbb{E}[\varphi_{\tau}] \leq \mathbb{E}[K_0]. $$
Applying Theorem E.6 with $\tau = T_k$, $\varphi_t = \int_0^t \frac{\gamma}{4} \|\nabla f(x_{s-})\|^2 dN_s$, $K_0 = f(x_0) - f^*$ and $M_t = U_t$, we obtain

$$ \mathbb{E} \left[ \int_0^{T_k} \|\nabla f(x_{s-})\|^2 dN_s \right] \leq \frac{4}{\gamma} (f(x_0) - f^*). $$

Finally, we have

$$ \int_0^{T_k} \|\nabla f(x_{s-})\|^2 dN_s = \sum_{i=1}^k \left\| \nabla f(x_{T_i^-}) \right\|^2 = \sum_{i=1}^k \|\nabla f(\tilde{y}_{i-1})\|^2 \geq k \min_{0 \leq i \leq k-1} \|\nabla f(\tilde{y}_i)\|^2, $$

thus the result. $\square$

<figure><img src="image_5.png" /></figure>