# Acceleration for Polyak-Łojasiewicz Functions with a Gradient Aiming Condition

Julien Hermant

► To cite this version:

Julien Hermant. Acceleration for Polyak-Łojasiewicz Functions with a Gradient Aiming Condition.
2026. hal-05503989

HAL Id: hal-05503989

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

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
# Acceleration for Polyak-Łojasiewicz Functions with a Gradient Aiming Condition

Julien Hermant<fnref n="1" />

## Abstract

It is known that when minimizing smooth Polyak-Łojasiewicz (PL) functions, momentum algorithms cannot significantly improve the convergence bound of gradient descent, contrasting with the acceleration phenomenon occurring in the strongly convex case. To bridge this gap, the literature has proposed strongly quasar-convex functions as an intermediate non-convex class, for which accelerated bounds have been suggested to persist. We show that this is not true in general: the additional structure of strong quasar-convexity does not suffice to guaranty better worst-case bounds for momentum compared to gradient descent. As an alternative, we study PL functions under an aiming condition that measures how well the descent direction points toward a minimizer. This perspective clarifies the geometric ingredient enabling provable acceleration by momentum when minimizing PL functions.

## 1. Introduction

Momentum (Polyak, 1964; Nesterov, 1983) is an important mechanism of modern machine learning optimizers, as it substantially improves the optimization of large-scale models in practice (Sutskever et al., 2013; He et al., 2016). Although the theoretical benefit of incorporating momentum in vanilla gradient descent is well established in the convex and strongly convex setting (Nemirovskij & Yudin, 1983; Nesterov, 2018), non-convexity is, however, an inherent property of many problems (Dauphin et al., 2014; Ge et al., 2016; 2017; Bhojanapalli et al., 2016; Li et al., 2018). Importantly, for some non-convex settings it is not possible to demonstrate acceleration using momentum (Carmon et al., 2020; Yue et al., 2023). Focusing on neural networks, some works establish acceleration properties (Wang et al., 2021; Liu et al., 2022b;c; Liao & Kyrillidis, 2024), but rely on

very important over-parameterization.

Another line of work lies in considering classes of non-convex functions that relax strong convexity. In particular, the class of Polyak-Łojasiewicz (PL) functions (Polyak, 1963; Lojasiewicz, 1963) has emerged as an important framework and has stimulated extensive interest (Karimi et al., 2016; Fazel et al., 2018; Oymak & Soltanolkotabi, 2019; Altschuler et al., 2021; Mérigot et al., 2021; Wang et al., 2022; Apidopoulos et al., 2022; 2025; Gess & Kassing, 2023). A continuously differentiable function $f: \mathbb{R}^d \to \mathbb{R}$ belongs to this class if there exists $\mu > 0$ such that the following inequality holds for all $x \in \mathbb{R}^d$

$$ \|\nabla f(x)\|^2 \geq 2\mu \left( f(x) - \min_{u \in \mathbb{R}^d} f(u) \right). $$

Among the remarkable properties of PL functions, we note that (i) it is a necessary and sufficient condition to achieve linear convergence using gradient descent (Abbaszadehpeivasti et al., 2023), and (ii) it can effectively model over-parameterized neural networks (Liu et al., 2022a; Barboni et al., 2022; Chen et al., 2023; Xu et al., 2025). Yet, PL functions are such that gradient descent's convergence bound cannot be significantly improved using momentum (Yue et al., 2023). This seems to contradict the often empirically observed benefit of momentum, and thus motivates the search for more structured relaxations of strong convexity. An intermediate non-convex class that is expected to capture acceleration by momentum is strong quasar-convexity (Hinder et al., 2020), sometimes referred to as weak-quasi-strong convexity (Necoara et al., 2019; Bu & Mesbahi, 2020). A continuously differentiable function $f: \mathbb{R}^d \to \mathbb{R}$ belongs to this class if there exists a minimizer $x^* \in \mathbb{R}^d$ and parameters $(\tau, \mu) \in (0, 1] \times \mathbb{R}_+^*$ such that for all $x \in \mathbb{R}^d$

$$ \min_{u \in \mathbb{R}^d} f(u) \geq f(x) + \frac{1}{\tau} \langle \nabla f(x), x^* - x \rangle + \frac{\mu}{2} \|x - x^*\|^2. $$

There has been growing interest in strongly quasar-convex functions in recent years (Gower et al., 2021; Wang & Wibisono, 2023; Alimisis, 2024; Alimisis & Vandereycken, 2024; Pun & Shames, 2024; Hermant et al., 2025; Chen et al., 2025; Lara & Vega, 2025; de Brito et al., 2025; Farzin et al., 2025). In the L-smooth setting, minimizing these functions using momentum is often referred to as accelerated

<footnote n="1">¹Univ. Bordeaux, Bordeaux INP, CNRS, IMB, UMR 5251, F-33400 Talence, France. Correspondence to: Julien Hermant <julien.hermant@math.u-bordeaux.fr>.</footnote>
optimization (Hinder et al., 2020; Fu et al., 2023; Hermant et al., 2024), suggesting better convergence bounds than gradient descent. This expectation partly stems from the fact that its complexity bounds take a form similar to those obtained in the smooth, strongly convex case. In this work, we show that this intuition is misleading.

## 1.1. Contributions

Our work addresses what additional structure beyond the PL condition is required to obtain improved theoretical convergence bounds over gradient descent when using momentum. We summarize our contributions as follows:

(1.) We show in Section 3 that, in contrast with existing interpretations, minimizing strongly quasar-convex functions with momentum does not necessarily yield better theoretical convergence bounds than gradient descent. This is because, in some cases, the PL condition admits tighter bounds that cannot be improved by momentum.

(2.) We propose in Section 4 a different viewpoint by studying the convergence of PL functions under an additional aiming condition

$$ \langle \nabla f(x), x - x^* \rangle \geq a \|\nabla f(x)\| \|x - x^*\|, \quad (1) $$

for $1 \geq a > 0$, which quantifies how well the descent direction aims toward a minimizer $x^*$. Using a stochastic parameterization of Nesterov momentum’s algorithm, we show that we obtain accelerated bounds when this alignment constant $a$ is sufficiently large (Section 4.2).

(3.) We relax the aiming condition by requiring it to hold only on average along the optimization trajectory, recovering similar convergence rates (Section 5). It shows that acceleration can be achieved as long as (1) holds over a sufficiently large fraction of the optimization path, better reflecting the behavior of practical optimization algorithms.

(4.) We exhibit a two-dimensional PL function with a unique minimizer that fails to satisfy (1). When minimizing this function, we empirically observe that the momentum mechanism initially drives the iterates away from the minimizer, causing gradient descent to outperform momentum methods during the early stages of optimization.

## 1.2. Related Works on Aiming Conditions

Studying SGD, (Liu et al., 2023; Gupta & Wojtowytsch, 2025; Alimisis et al., 2025) use conditions close to quasar-convexity they name aiming condition. While they consider the interpretation of pointing toward a minimizer, this condition actually carries more structure. Studying gradient descent, (Guille-Escuret et al., 2024; Singh et al., 2025) consider (1) from distinct perspectives: the first studies it empirically along the optimization path, the second uses it to prove a stability result, in the idea of better understanding the Edge of Stability phenomenon (Cohen et al., 2021).

(Hermant et al., 2024) establishes that a PL function with a unique minimizer is also strongly quasar-convex for some parameters, as long as (1) is verified, but the derived parameters are such that momentum does not yield accelerated bounds, see Appendix A.2.

# 2. Background

In this work, $f: \mathbb{R}^d \to \mathbb{R}$ is continuously differentiable. We note $f^* := \min_{x \in \mathbb{R}^d} f(x)$, $x^* \in \arg \min_{x \in \mathbb{R}^d} f(x)$. $k \in \mathbb{N}$ denotes a discrete index and $t \in \mathbb{R}_+$ a continuous one. $\mathcal{E}(1)$ denotes the exponential law of parameter 1.

## 2.1. Algorithms and Equations

We introduce the algorithms and dynamical systems that we study throughout this work.

**Gradient Descent and Gradient Flow** Among the most classical first-order algorithms is gradient descent (GD)

$$ \tilde{x}_{k+1} = \tilde{x}_k - \gamma \nabla f(\tilde{x}_k). \quad (\text{GD}) $$

It is the building block of many important algorithms used in modern applications (Hinton, 2012; Ghadimi & Lan, 2013; Kingma & Ba, 2015; Romano et al., 2017), and is still an important object of study (Malitsky & Mishchenko, 2020; Cohen et al., 2021). Writing gradient descent as $\frac{x_{k+1} - x_k}{\gamma} = -\nabla f(x_k)$, setting the Ansatz $\tilde{x}_k \approx x_{k\gamma}$ for some smooth curve $(x_t)_{t \ge 0}$, we consider the ODE limit of (GF) as the stepsize $\gamma$ vanishes to zero, named gradient flow (GF)

$$ \dot{x}_t = -\nabla f(x_t). \quad (\text{GF}) $$

With words, (GF) is a continuous version of (GD). This dynamical system viewpoint is longstanding for gaining insights into the corresponding algorithms (Ambrosio et al., 2005; Benaïm, 2006).

**Nesterov's Momentum: Ode and Algorithm** If (GD) benefits from a rather simple formulation, there are many situations where modifications of this algorithm accelerate its convergence speed. Among these mechanisms, an important one is momentum. The first momentum algorithm was Polyak's Heavy Ball (Polyak, 1964), which writes

$$ \tilde{x}_{k+1} = \tilde{x}_k + \underbrace{\alpha(\tilde{x}_k - \tilde{x}_{k-1})}_{\text{momentum}} - \underbrace{\eta \nabla f(\tilde{x}_k)}_{\text{gradient step}}. \quad (\text{HB}) $$

In this work, we focus on the Nesterov momentum (NM) version (Nesterov, 2018).

$$ \left\{ \begin{array}{l} \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{array} \right. \quad (\text{NM}) $$
Although its formulation is slightly more involved than Polyak's Heavy Ball, the latter exhibits worse convergence guarantees in some settings (Ghadimi et al., 2015; Goujaud et al., 2025). As for gradient descent, taking the limit of (NM) as stepsize $\gamma$ vanishes yields a limit Nesterov momentum ODE (NMO), (Kim & Yang, 2023, Appendix A.1)

$$ \left\{ \begin{aligned} \dot{x}_t &= \eta_t (z_t - x_t) - \gamma \nabla f(x_t), \\ \dot{z}_t &= \eta'_t (x_t - z_t) - \gamma' \nabla f(x_t). \end{aligned} \right. \quad \text{(NMO)} $$

Since the strong connection between these ODEs and the corresponding algorithm has been established (Su et al., 2016), their study has gained a rising interest both in the convex (Siegel, 2019; Shi et al., 2021; Attouch et al., 2022; Aujol et al., 2023; Li et al., 2024; Guo et al., 2024) and non-convex case (Okamura et al., 2024; Hermant et al., 2024; Gupta & Wojtowytsch, 2025; Renaud et al., 2025).

**Continuized Parameterization** We use a specific parameterization of (NM) with stochastic parameters that arises from the *continuized* method (Even et al., 2021). Precisely, for some $\eta, \eta' \in \mathbb{R}$ such that $\eta + \eta' > 0$, and some $\{T_k\}_{k \in \mathbb{N}}$ such that $T_{k+1} - T_k \stackrel{i.i.d}{\sim} \mathcal{E}(1)$, we fix in (NM):

$$ \alpha_k = \frac{\eta}{\eta + \eta'} \left(1 - e^{-(\eta+\eta')(T_{k+1}-T_k)}\right), \\ \beta_k = \eta' \frac{\left(1 - e^{-(\eta+\eta')(T_{k+1}-T_k)}\right)}{\eta' + \eta e^{-(\eta+\eta')(T_{k+1}-T_k)}}. $$

With this parameterization, the algorithm is inherently stochastic, yielding convergence guarantees holding with high probability. This viewpoint can be particularly well suited to non-convex optimization, where deterministic parameterization may lead to weaker results (Wang & Wibisono, 2023; Hermant et al., 2025). Its analysis involves a Poisson-driven SDE; see the latter reference for a methodological introduction to this continuized viewpoint.

## 2.2. Classical setting for acceleration

We first introduce a geometrical setting in which momentum-based acceleration is long established.

**Definition 2.1.** For $L > 0$, we call $LS^L$ the set of $L$-smooth functions, namely $f$ such that $\forall x, y \in \mathbb{R}^d$, $f(x) - f(y) - \langle \nabla f(y), x - y \rangle \le \frac{L}{2} \|x - y\|^2$.

**Definition 2.2.** For $\mu > 0$, we call $SC^\mu$ the set of $\mu$-strongly convex functions, namely $f$ such that $\forall x, y \in \mathbb{R}^d$, $f(x) + \langle \nabla f(x), y - x \rangle + \frac{\mu}{2} \|x - y\|^2 \le f(y)$.

Intuitively, $L$-smoothness and $\mu$-strong convexity provide global upper and lower bounds on the curvature of $f$. For a $C^2$ function, $f \in SC^\mu \cap LS^L$ implies that any eigenvalue $\lambda(x)$ of $\nabla^2 f(x)$ is such that $\mu \le \lambda(x) \le L$, for any $x \in \mathbb{R}^d$. The ratio $L/\mu \ge 1$ is called *condition number*, and characterizes how ill-conditioned the minimization problem

is—a higher condition number typically reflecting a more difficult problem. $SC^\mu \cap LS^L$ is a favorable setting for minimization: there exists a unique critical point $x^*$, satisfying $f(x^*) = f^*$, and linear convergence of function values is ensured by first order methods, namely

$$ \log(f(x_t) - f^*) \le -\Lambda t + \log(K(x_0)), $$

with $\Lambda > 0$ being the **convergence rate**, $K(x_0) > 0$ depends on the initialization. Linear convergence also holds in the discrete case, i.e., replacing $(x_t)_{t \ge 0}$ by $\{\tilde{x}_k\}_{k \ge 0}$ and $t$ by $k$. In this work, we specifically focus on the convergence rate value $\Lambda$. In the $SC^\mu \cap LS^L$ regime, the improvement of (NM) over (GD) is well established (Nesterov, 2004), see the convergence rates in Table 1. Precisely, as typically $L/\mu \gg 1$, improving from $\mu/L$ to $\sqrt{\mu/L}$ yields a substantial gain, often called *acceleration*. However, many problems of interest do not fall within $SC^\mu \cap LS^L$. This motivates to identify more general settings where momentum-based acceleration remains possible.

## 2.3. Relaxed setting

A first relaxation of $SC^\mu$ and $LS^L$ consists in lower and upper global quadratic bounds of the function.

**Definition 2.3.** For $\mu_0, L_0 > 0$, we call: $QG^\mu_0$ the set of functions $f$ that verify $f(x) - f^* \ge \frac{\mu_0}{2} \|x - x^*\|^2$, $QG^L_0$ the set of functions $f$ that verify $f(x) - f^* \le \frac{L_0}{2} \|x - x^*\|^2$.

$QG^\mu_0 \cap QG^L_0$ includes functions with pathological behavior, e.g. having an infinite amount of critical points in any vicinity of $x^*$ (Hermant et al., 2024, Proposition 9). This may discard the possibility of targeting a global minimizer $f^*$. A key relaxation of strong convexity that does not preclude this objective is the class of Polyak-Łojasiewicz (PL) functions (Polyak, 1963; Łojasiewicz, 1963).

**Definition 2.4.** For $\mu > 0$, we call $PL^\mu$ the set of functions $f$ that satisfies $\forall x \in \mathbb{R}^d$, $\|\nabla f(x)\|^2 \ge 2\mu(f(x) - f^*)$.

It immediately follows that for $f \in PL^\mu$, any critical point is a global minimizer of $f$. From an optimization perspective, two key results hold for the class $PL^\mu \cap LS^L$: (i) gradient descent achieves a linear convergence rate (Polyak, 1963), and (ii) this rate is optimal among first-order algorithms (Yue et al., 2023). As a consequence, (NM) cannot yield any significant theoretical improvement over this class, see Table 1. This motivates studying more structured non-convex relaxations of $SC^\mu \cap LS^L$. The class of strongly quasar-convex functions (SQC) is expected to fulfill the demand.

**Definition 2.5.** For $(\tau, \mu) \in (0, 1] \times \mathbb{R}_+$, we call $SQC_\tau^\mu$ the set of functions $f$ that verify $\forall x \in \mathbb{R}^d$, $f^* \ge f(x) + \frac{1}{\tau} \langle \nabla f(x), x^* - x \rangle + \frac{\mu}{2} \|x - x^*\|^2$.

$SQC_\tau^\mu$ is a relaxation of $SC^\mu$, while being more structured than $PL^\mu$ (Hermant et al., 2024). One possible application of
<table><caption>Table 1. Comparison of convergence rates up to a numerical constant, for (GF), (NMO), (GD) and (NM) properly parameterized, for functions belonging to $SC^{\mu}$, $SQC_{\tau}^{\mu}$ and $PL^{\mu}$, intersected with $LS^{L}$ for algorithms. Most can be found in the literature, see Appendix A.1.</caption><thead><tr><th>Equation/Algorithm</th><th>GF</th><th>NMO</th><th>GD</th><th>NM</th></tr></thead><tbody><tr><td>Function class</td><td></td><td></td><td></td><td></td></tr><tr><td>μ-strongly convex (SC<sup>μ</sup>)</td><td>μ</td><td>√μ</td><td>μ/L</td><td>√μ/L</td></tr><tr><td>(τ, μ)-strongly quasar-convex (SQC<sub>τ</sub><sup>μ</sup>)</td><td>τμ</td><td>τ√μ</td><td>τμ/L</td><td>τ√μ/L</td></tr><tr><td>μ-Polyak-Łojasiewicz (PL<sup>μ</sup>)</td><td>μ</td><td>(-)</td><td>μ/L</td><td>μ/L</td></tr></tbody></table>

these functions is the training of generalized linear models (Wang & Wibisono, 2023, Section 3). Functions in $SQC_{\tau}^{\mu}$ keep the property of $SC^{\mu}$ to having a unique minimizer, but can exhibit strong oscillations, see Figure 4. Unlike PL functions, this class admits distinct convergence rates for (GD) and (NM), resembling the strongly convex case up to a factor $\tau$, see Table 1. This apparent similarity should be treated with care, as it partly results from a notational convention that reuses the parameter $\mu$ for both the classes $SC^{\mu}$ and $SQC_{\tau}^{\mu}$, as discussed in Section 3.1.

**Relation between classes** The following inclusions hold (Karimi et al., 2016)

$$SC^{\mu} \subset SQC_{1}^{\mu} \subset PL^{\mu} \subset QG_{-}^{\mu}, \quad LS^{L} \subset QG_{+}^{L}.$$

As observed by (Guille-Escuret et al., 2021), the constants inherited from these inclusions may be severely suboptimal. In particular, it is possible to have $f \in LS^{L} \cap QG_{+}^{L_0}$ with $L_0 \ll L$, and similarly $f \in PL^{\mu} \cap QG_{-}^{\mu_0}$ with $\mu_0 \gg \mu$, see Figure 5 in the appendix. Consequently, reusing the same notation for constants across different function classes may lead to misleading comparisons of convergence rates.

### 3. Acceleration under Strong Quasar-Convexity: Hidden Pitfalls

Using momentum to optimize functions in $SQC_{\tau}^{\mu} \cap LS^{L}$ is often described as accelerated optimization (Hinder et al., 2020; Fu et al., 2023). This interpretation is motivated by an analogy with the complexity bounds obtained for functions in $SC^{\mu} \cap LS^{L}$, see Table 1. Precisely, following this line of reasoning, one might expect that for a function belonging to $SQC_{\tau}^{\mu} \cap LS^{L}$, the complexity bound of (NM) improves upon that of (GD). This does not hold in general.

**Weaker Assumption, Sharper Rate** To compare the convergence rates of (GD) and (NM) when minimizing functions in $SQC_{\tau}^{\mu} \cap LS^{L}$, it is natural to rely on the rates established in the literature for this class, namely $\tau\mu/L$ for (GD) and $\tau\sqrt{\mu/L}$ for (NM), see Table 1. However, any function belonging to $SQC_{\tau}^{\mu} \cap LS^{L}$ also belongs to $PL^{\mu'} \cap LS^{L}$, for some parameter $\mu'$. As a result, one may alternatively consider the convergence rate $\mu'/L$ of gradient descent derived for functions in $PL^{\mu'} \cap LS^{L}$. Strikingly, in some cases, this latter rate can be sharper than those given for the class

$SQC_{\tau}^{\mu} \cap LS^{L}$. In Figure 1, we plot two examples of functions that belong to $SQC_{\tau}^{\mu} \cap LS^{L}$, and so also belong to $PL^{\mu'} \cap LS^{L}$, for some parameters. For a given pair of algorithm and function class, we numerically compute the associated parameters and convergence rate. For the first example, we find that the rate of (NM) characterized by $SQC_{\tau}^{\mu}$ is $\approx 10^2$ times larger than the one of (GD) characterized by $PL^{\mu'}$. However, for the second example, we find that the rate of (GD) characterized by $PL^{\mu'}$ is $\approx 10^2$ times better than the rate of (NM) characterized by $SQC_{\tau}^{\mu}$. Surprisingly, $SQC_{\tau}^{\mu} \cap LS^{L}$ does not necessarily ensure accelerated bounds when using momentum.

The previous discussion shows that $SQC_{\tau}^{\mu} \cap LS^{L}$ does not guarantee improved convergence rates in general. This naturally raises the question of when acceleration can actually be expected. An important obstacle is that the convergence rates for $PL^{\mu} \cap LS^{L}$ and $SQC_{\tau}^{\mu} \cap LS^{L}$ are not directly comparable. To address this issue, in Section 4 we use $PL^{\mu}$ as a common baseline to study each algorithm and dynamical systems. Before doing so, we first highlight several issues inherent to the definition of the class $SQC_{\tau}^{\mu}$.

#### 3.1. Specific Problems of Strong Quasar-Convexity

The intuition that a similar acceleration phenomenon occurs for $SQC_{\tau}^{\mu} \cap LS^{L}$ and $SC^{\mu} \cap LS^{L}$ can results from an appearing improvement from $\mu/L$ with (GD) to $\sqrt{\mu/L}$ with (NM) in both cases, and from carrying the interpretation of $L/\mu$ as a condition number. This is somewhat deceptive, as we detail below.

**Parameter Interpretation** The constant $\mu$ in $SC^{\mu}$ parametrizes a global lower bound on the curvature. Reusing the notation $\mu$ in a similar way in $SQC_{\tau}^{\mu}$ may therefore suggest a similar interpretation. In particular, for $f \in SQC_{\tau}^{\mu} \cap LS^{L}$, one may be tempted to view $L/\mu$ as a conditioning measurement, analogously to the setting $SC^{\mu} \cap LS^{L}$. Under this interpretation, one would expect $L/\mu \ge 1$, see Section 2.2. However, since $f \in SQC_{\tau}^{\mu} \Rightarrow f \in SQC_{\theta_{\tau}}^{\mu/\theta}$, for any $\theta \in (0, 1]$ (Hinder et al., 2020, Observation 5), it is possible to have $f \in SQC_{\tau}^{\mu} \cap LS^{L}$ for some parameters satisfying $\mu > L$. This observation challenges both the condition-number interpretation of $L/\mu$ and the common way to interpret the convergence rates in this setting.
<figure><img src="image_2.png" /><figcaption>**Figure 1.** Left: graph of $f(t) = 5(t + 0.19 \sin(5t))^2$, minimizer is 0. Right: graph of $f(x, y) = 0.5(0.5x^2 - y)^2 + 0.05x^2$, minimizer is (0, 0). Bottom: table giving for each function the numerical value of the theoretical convergence rate for (GD) or (NM), precising what class of function is used to characterize the bound (see Table 1), where $\Lambda$ is the convergence rates. See implementation details in Appendix B.1. It shows that depending on the functions, $PL^\mu$-based bound may be sharper than $SQC_\tau^\mu$-based bounds, and conversely.</figcaption></figure>

**The Optimal Choice of Parameters** For many function classes, there exists a natural notion of optimal parameters. For instance, if $f \in PL^\mu$ for a range of constants $\mu > 0$, the tighter class to describe $f$ is $PL^\mu$ with $\hat{\mu}$ the largest admissible value. Accordingly, the rates reported in Table 1 are maximized by choosing $\mu = \hat{\mu}$. In contrast, because of the double parameterization, there is no canonical way to choose among all admissible pairs $(\tau, \mu)$ an optimal one for a function in $SQC_\tau^\mu$. Choosing the largest admissible $\tau$ and then the largest admissible $\mu$ leads to a different parameter pair than optimizing in the reverse order, see Appendix A.3. Critically, the parameter pair that maximizes a given convergence rate depends on the algorithm or dynamic under consideration, as illustrated in Figure 2. As a consequence, statements of the form “the rates of (GF) and (NMO) scale as $\tau\mu$ and $\tau\sqrt{\mu}$” without clarifying how the parameters are chosen may result in misleading comparisons.

## 4. Acceleration for PL Functions with an Aiming Condition

$PL^\mu \cap LS^L$ is not sufficient to guarantee accelerated bounds with momentum. Rather than introducing a different intermediate function class such as $SQC_\tau^\mu$, we augment the $PL^\mu \cap LS^L$ framework with an additional geometric ingredient and study its effect on acceleration. We initially assume the existence of a unique minimizer $x^*$, which can be relaxed as discussed in Section 5.

<figure><img src="image_3.png" /><figcaption>**Figure 2.** For a range of parameters $\tau$, we compute the highest admissible $\mu$ ensuring $f \in SQC_\tau^\mu$, and plot the numerical values of the associated theoretical convergence rates for (GD) and (NM) under $SQC_\tau^\mu \cap LS^L$, namely $\tau\mu/L$ and $\tau\sqrt{\mu/L}$, with $f(t) = 5(t + 0.19 \sin(5t))^2$. See implementation details in Appendix B.1. Note that the pair $(\tau, \mu)$ that maximizes the convergence rate of (GD) differs from the pair that maximizes the one of (NM).</figcaption></figure>

**Definition 4.1.** For $a \in (0, 1]$, we call $AC^a$ the set of functions satisfying the aiming condition, i.e. $\forall x \in \mathbb{R}^d$, $\langle \nabla f(x), x - x^* \rangle \ge a \|\nabla f(x)\| \|x - x^*\|$.

The parameter $a$ measures the alignment between the descent direction $-\nabla f$ and the direction toward the minimizer. Values of $a$ close to 1 indicate a strong alignment. In one dimension, any function in $AC^a$ has perfect alignment, yielding $a = 1$. Such strong alignment is particularly favorable to momentum methods, as it ensures that the accumulated momentum reinforces progress toward $x^*$. In contrast, if $a$ is small, momentum may amplify steps taken in poorly aligned directions. For example, the rightmost function in Figure 1 exhibits a small aiming condition value, $a \approx 3 \cdot 10^{-4}$, which helps to explain why the convergence rate of (GD) is sharper than that of (NM) in this case. The connection between $AC^a$ and $SQC_\tau^\mu$ is discussed in Appendix G.

In Section 4.1, we observe the impact of the aiming condition when studying standard gradient methods (GF) and (GD). We consider in Section 4.2 the convergence of (NMO) and (NM), and the question of acceleration.

### 4.1. $AC^a$ Gives Weight to the Local Information at $x^*$

We first compare convergence bounds obtained for (GF), depending on $f$ belongs to $AC^a$ or not.

**Theorem 4.2.** Let $(x_t)_{t \ge 0} \sim (\text{GF})$.

(i) If $f \in PL^\mu$, then

$$f(x_t) - f^* \le (f(x_0) - f^*)e^{-2\mu t}.$$

(ii) If $f \in PL^\mu \cap AC^a \cap \mathcal{Q}G_+^{L_0}$, then

$$f(x_t) - f^* \le \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) (f(x_0) - f^*) e^{-a\sqrt{\mu\mu_0}t},$$

where $\mu_0 := \sup\{\mu' \ge \mu : f \in \mathcal{Q}G_-^{\mu'}\}$.
See the proof in Appendix D.1. For bound (ii), we also assume $f \in \text{QG}_{+}^{L_0}$ for technical reasons. When considering algorithms, we will assume $f \in \text{LS}^L$, such that they will naturally belong to $\text{QG}_{+}^{L_0}$. We note that under the aiming condition, there is a worse constant factor $1 + \sqrt{L_0/\mu_0}$, which mainly affects the bound for early iterations. In this work, we specifically focus on convergence rates.

**Comparison of Convergence Rates** In addition to the PL constant $\mu$, the convergence rates in (ii) depends on a quadratic lower bound parameter $\mu_0$ and the aiming condition parameter $a$. As a result, rate (ii) improves upon rate (i) whenever $a \ge 2\sqrt{\mu/\mu_0}$. So, for functions with bad alignment, characterizing the convergence rate solely through the PL condition may lead to sharper rates. It is interesting to observe that $\mu_0$ appears in (ii), but not in (i). In the presence of flat plateaus, we may have $\mu \ll \mu_0$. This is due to $\mu_0$ being less affected by global irregularities of the function landscape, as we discuss next.

**The Aiming Condition Exploits the Local Information at**
$x^*$ For functions in $\text{SC}^\mu \cap \text{LS}^L$, the slowest direction toward the minimizer is the one with the smallest curvature $\mu$, since it corresponds to the flattest direction (left plot of Figure 6 in the appendix). For functions in $\text{PL}^\mu \cap \text{LS}^L$, the situation is less clear: the trajectory may approach the minimizer either through low-curvature directions near $x^*$ or through plateau-like regions (right plot of Figure 6). Thus, it is ambiguous whether the relevant $\mu$ is determined by local curvature at $x^*$ or by the plateaus, as $\text{PL}^\mu$ handles both information. Bound (i) of Theorem 4.3 does not separate these effects, but bound (ii) does: it reveals a trade-off between global plateaus and local curvature $\mu_0$. If $\mu = \mu_0$, flatness near $x^*$ dominates and we recover the rate $O(e^{-\mu t})$. If $\mu < \mu_0$, the plateaus matter, yielding a rate $e^{-\sqrt{\mu\mu_0}}$, which shows that plateaus do not fully determine the convergence.

**Convergence of (GD)** Assuming the function belongs to $\text{LS}^L$, we deduce similar convergence rates for (GD), with the difference that the L-smoothness constant intervenes.

**Theorem 4.3.** Let $f \in \text{LS}^L$, $\{\tilde{x}_k\}_{k \in \mathbb{N}} \sim (\text{GD})$, $\gamma = \frac{1}{L}$.

(i) If we also have $f \in \text{PL}^\mu$, then

$$f(\tilde{x}_k) - f^* \le (1 - \frac{\mu}{L})^k (f(\tilde{x}_0) - f^*).$$

(ii) If we also have $f \in \text{PL}^\mu \cap \text{AC}^a$, then

$$f(\tilde{x}_k) - f^* \le K_0 \left(1 - a \frac{\sqrt{\mu\mu_0}}{L}\right)^k (f(x_0) - f^*).$$

with $K_0 := (1 + \sqrt{L_0/\mu_0})$, $\mu_0 := \sup\{\mu' \ge \mu : f \in \text{QG}_{-}^{\mu'}\}$ and $L_0 := \inf\{L' \le L : f \in \text{QG}_{+}^{L'}\}$.

Grossly, the convergence rates of Theorem 4.3 are the same

as those of Theorem 4.2, divided by $L$, such that we can draw similar insights, see the proof in Appendix D.2.

## 4.2. Acceleration using Momentum with Large Enough Aiming Condition Constant

We state the convergence rates of (NMO) and (NM), under the aiming condition.

**Theorem 4.4.** Let $f \in \text{PL}^\mu \cap \text{AC}^a \cap \text{LS}^L$, $L_0 := \inf\{L' \le L : f \in \text{QG}_{+}^{L'}\}$, $\mu_0 := \sup\{\mu' \ge \mu : f \in \text{QG}_{-}^{\mu'}\}$.

(i) Let $(x_t)_{t \ge 0} \sim (\text{NMO})$ and constant parameters $\gamma \ge 0$, $\gamma' = (\mu_0 L_0)^{-1/4}$, $\eta = (\mu_0 L_0)^{1/4}$, $\eta' = a (\mu_0 / L_0)^{1/4} \sqrt{\mu}$. Then,

$$f(x_t) - f^* \le K_0 e^{-a \left(\frac{\mu_0}{L_0}\right)^{\frac{1}{4}}} \sqrt{\mu t},$$

where $K_0 := \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) (f(x_0) - f^*)$

(ii) Let $\{\tilde{x}_k\}_{k \in \mathbb{N}}$ verify (NM) with the continuous parameterization, with $\eta = (\mu_0 L_0)^{1/4} / \sqrt{L}$, $\gamma = 1/L$, $\gamma' = ((\mu_0 L_0)^{1/4} / \sqrt{L})^{-1}$, and $\eta' = a (\mu_0 / L_0)^{1/4} / \sqrt{\mu / L}$. Then, with probability $1 - \frac{1}{c_0} - \exp(-(c_1 - 1 - \log(c_1))k)$, for some $c_0 > 1$ and $c_1 \in (0, 1)$ we have

$$f(\tilde{x}_k) - f^* \le K_1 e^{-a \left(\frac{\mu_0}{L_0}\right)^{1/4}} \sqrt{\frac{\mu}{L}(1-c_1)k},$$

where $K_1 := c_0 \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) (f(x_0) - f^*)$.

See the proof in Appendix D.3. The result of Theorem 4.4 (ii) holds under high probability, due to the use of the continuous version of Nesterov. In the following, we compare convergence rates despite this difference.

**Comparison of the Convergence Rates: Discrete Case**

The convergence rates in Theorem 4.3 and Theorem 4.4 (ii) are

$$\frac{\mu}{L}, \quad a \frac{\sqrt{\mu\mu_0}}{L}, \quad a \left(\frac{\mu_0}{L_0}\right)^{1/4} \sqrt{\frac{\mu}{L}}(1-c_1).$$

Ignoring the factor $(1 - c_1)$, the latter always dominates $a \frac{\sqrt{\mu\mu_0}}{L}$, such that we compare $\mu/L$ and $a(\mu_0/L_0)^{1/4} \sqrt{\mu/L}$. Thus, for functions in $\text{PL}^\mu \cap \text{AC}^a \cap \text{LS}^L$, the rate of (NM) is better than the rate of (GD) whenever

$$a \ge \left(\frac{L_0}{\mu_0}\right)^{1/4} \sqrt{\frac{\mu}{L}}.$$

This bound suggests that, in the presence of oscillations and flat plateaus, leading to $\mu/L \ll 1$, there is increased tolerance for poor alignment while still allowing acceleration. We test this bound numerically on the PL lower-bound function of (Yue et al., 2023), and find that the two quantities scale similarly, in a sense described in Appendix B.3, providing a heuristic support for the relevance of our bound.
**Acceleration for Dynamical Systems: Flatness Matters** Comparing the rates of Theorem 4.2 (i) and Theorem 4.4 (i) yields an improvement of momentum if $a \ge (L_0/\mu_0)^{1/4} \sqrt{\mu}$, namely a similar bound as a in the discrete case, up to the $\sqrt{L}^{-1}$ factor. Contrasting with the discrete case, the rate of Theorem 4.4 (i) does not necessarily improve upon Theorem 4.2 (ii). Improvement occurs whenever

$$ \mu_0 L_0 < 1. $$

Since $L_0 \ge \mu_0$, this implies that if $\mu_0 > 1$ (the function is sharp near the minimizer), then (GF) is preferable, whereas if $L_0 < 1$ (flatness near minimizer), then (NMO) performs better. In the intermediate regime $\mu_0 < 1 < L_0$, the outcome depends on the balance between the smallest and largest local curvatures: if $\mu_0$ is much smaller than 1 while $L_0$ is only moderately above 1, flatness dominates and (NMO) wins; conversely, in the opposite case. The advantage of (NMO) on flat landscapes is consistent with previous observations for the Heavy Ball dynamics when $f \in \text{PL}^\mu$ (Apidopoulos et al., 2022; Gess & Kassing, 2023), whose dynamics are close to (NMO).

## 5. Relaxed Setting: Aiming Condition on Average

There is a gap between the convergence observed in practice and the theoretical bounds established for globally defined classes such as PL functions. The reason is intuitive: if the global landscape of non-convex functions can be highly irregular, nevertheless, the optimization path may remain in a favorable region. Importantly, the performance of first-order algorithms such as (GD) and (NM) only depends on the geometry surrounding their optimization path.

**Naive Relaxation** A first direct idea to take this intuition into account is to consider an algorithm $\{\tilde{x}_k\}_{k \ge 0}$ and a minimizer $\hat{x}$ such that $\tilde{x}_k \to_{k \to +\infty} \hat{x}$, and assuming

$$ \forall k \in \mathbb{N}, \langle \nabla f(\tilde{x}_k), \tilde{x}_k - \hat{x} \rangle \ge a \|\nabla f(\tilde{x}_k)\| \|\tilde{x}_k - \hat{x}\|. \quad (2) $$

With words, $f$ is assumed to satisfy the $a$-aiming condition along the trajectory $\{\tilde{x}_k\}_{k \ge 0}$, with respect to its convergence point $\hat{x}$. For a function in $\text{PL}^\mu \cap \text{LS}^L$, if $\{\tilde{x}_k\}_{k \ge 0} \sim (\text{GD})$ or (NM) verify (2), we would deduce for this sequence the same result as for Section 4. The relaxation is twofold: (i) we get rid of the uniqueness minimizer assumption, and (ii) the convergence rate is not affected by potential pathological regions of $f$, as long as the sequence does not cross it. However, it suffices for (2) to not be verified for a single iteration to make this reasoning fail. We thus derive a relaxation that, in the case where pathological regions remain a negligible section of the optimization path, still allows to keep accelerated results.

**Averaging Relaxation** We relax the viewpoint (2). We ad-

dress the continuous case; the discrete case follows similarly, see Appendix E.

**Assumption 5.1.** For some minimizer $x^* \in \mathbb{R}^d$, $\theta > 0$, $a_{avg} > 0$, and $(x_t)_{t \ge 0}$, we have

$$ \int_0^t e^{\theta s} \Delta_s ds \ge 0, \\ \Delta_s := \langle \nabla f(x_s), x_s - x^* \rangle - a_{avg} \|\nabla f(x_s)\| \|x_s - x^*\|. $$

A function $f$ satisfies Assumption 5.1 as long as the aiming condition holds along a specific average of the trajectory. If $f \in \text{AC}^a$, Assumption 5.1 holds with $a_{avg} = a$ for any initialization. However, we could have $a \ll a_{avg}$, or having that the path crosses some regions where the aiming condition is not verified, while still having $a_{avg} > 0$.

**Theorem 5.2.** Let $f \in \text{PL}^\mu \cap \text{QG}_+^{L_0}$, $\mu_0 := \sup\{\mu' \ge \mu : f \in \text{QG}_{-}^{\mu'}\}$ and $a_{avg} > 0$. If:

(i) $(x_t)_{t \ge 0} \sim (\text{GF})$ for a given initialization $x_0 \in \mathbb{R}^d$ is such that Assumption 5.1 holds with $\theta = a_{avg} \sqrt{\mu\mu_0}$, then

$$ f(x_t) - f^* \le K_0 e^{-a_{avg} \sqrt{\mu\mu_0 t}} (f(x_0) - f^*). $$

(ii) $(x_t)_{t \ge 0} \sim (\text{NMO})$ for $\eta' = a_{avg} (\mu_0/L_0)^{1/4} \sqrt{\mu}$, $\gamma' = (\mu_0 L_0)^{-1/4}$, $\eta = (\mu_0 L_0)^{1/4}$, $\gamma \ge 0$ and such that Assumption 5.1 holds with $\theta = a_{avg} (\mu_0/L_0)^{1/4} \sqrt{\mu}$, then

$$ f(x_t) - f^* \le K_0 e^{-a_{avg} \left(\frac{\mu_0}{L_0}\right)^{\frac{1}{4}} \sqrt{\mu}} (f(x_0) - f^*). $$

In both statements, $K_0 := \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right)$.

The proof is in Appendix E.1. We obtain the same convergence rate as for Theorem 4.2 (ii) and Theorem 4.4 (i), replacing $a$ with $a_{avg}$. However, the rates of Theorem 5.2 could be either significantly sharper, or allow for obtaining such a rate while the algorithm crosses regions with negative aiming condition values. This reasoning can be extended to other geometrical conditions, such as $\text{PL}^\mu$. This perspective might explain why, in practice, grid-search selection of parameters often leads to relatively large constants, compared to what would be allowed by geometrical constants that parameterize globally the associated landscape.

## 6. Numerical Experiment

In this section, we first design an example that shows how negative aiming condition values can hurt the convergence of momentum algorithms, and then discuss the aiming condition in neural networks. For our experiment, we consider an alternative formulation of (NM) that we call (NM').

$$ \begin{cases} \tilde{y}_k = \tilde{x}_k + \alpha(\tilde{x}_k - \tilde{x}_{k-1}) \\ \tilde{x}_{k+1} = \tilde{y}_k - \gamma \nabla f(\tilde{y}_k) \end{cases} \quad (\text{NM}') $$
<figure><img src="image_4.png" /><figcaption>Figure 3. Left: Heatmap of $F_{0.001}(x, y) = 0.5(y - \sin(x))^2 + 0.001 \cdot 0.5x^2$. Blue arrows indicate the descent direction $-\nabla F_{0.001}$. Center: First 1000 iterations of the trajectories of (GD) and (NM'), both starting from the initialization point (0, 3), for different values of momentum parameter $\alpha$. Top right: Corresponding decrease of $\log(f)$. Bottom right: Values of the aiming condition along the iterates, zoomed on the first 100 iterations. Early negative aiming condition values cause momentum to drive the trajectory away from the minimizer, leading (GD) to outperform momentum in early iterations, with increasing effect for larger $\alpha$.</figcaption></figure>

While (NM) with the continuized parameterization is convenient for theoretical analysis, (NM') is more amenable to practical implementation, as it involves only two easily tunable parameters with clear interpretations: the stepsize $s$ and the momentum parameter $\alpha$. See (Defazio, 2019) for a discussion on the different forms of Nesterov momentum.

## 6.1. An Example with Negative Aiming Condition

Consider the 2-dimensional function

$$F_{\varepsilon}(x, y) = 0.5(y - \sin(x))^2 + 0.5\varepsilon x^2.$$

The special case $\varepsilon = 0$ is introduced in (Apidopoulos et al., 2022). For $\varepsilon > 0$, $F_{\varepsilon}$ has (0, 0) as unique minimizer, and it belongs to $PL^{\mu}$ with $\mu \le \frac{2+\varepsilon-\sqrt{\varepsilon^2+4}}{2}$, see Lemma B.1. We display $F_{0.001}$ in Figure 3. We also provide a three-dimensional visualization in the appendix, see Figure 7. At certain points of the landscape, the descent direction is anti-correlated with the direction pointing toward the minimizer, thereby violating the aiming condition.

**Negative aiming condition shoots (NM') away** In Figure 3, we compare (GD) and (NM') for different values of momentum parameter $\alpha$, see details in Appendix B.2. Due to negative aiming condition values during the early phase of the optimization process, iterates of (NM') are initially driven away from the minimizer. Increasing the momentum parameter amplifies this effect, causing the trajectory to deviate even further. As a result, (GD) outperforms (NM') for up to 1000 iterations in terms of function value decrease. This example illustrates how negative aiming condition values can hinder momentum methods. More broadly, designing functions with unfavorable aiming behavior while retaining desirable optimization properties—such as satisfying the PL condition and having a unique minimizer—appears to be an

interesting direction for better understanding landscapes on which momentum is ineffective.

(NM') eventually catches up due to favorable averaged aiming condition Figure 3 shows that, although the aiming condition takes negative values at early iterations, it then stabilizes around a positive value close to one. As discussed in Section 5, this suggests that (NM') should eventually benefit from momentum for a large enough number of iterations. We confirm this behavior in Figure 8 in the appendix.

## 6.2. Aiming Condition and Neural Networks

Because of the curse of dimensionality and their high level of non-convexity, we could expect that large-scale models such as those involved in deep learning do not verify any aiming condition. This intuition is challenged by the fact that well-designed neural networks are known to have favorable optimization properties. It was observed in (Li et al., 2018) that around 90% of the variations of the path of SGD with large batch size lie in a dimension 2 space, despite the high dimensionality of the models. Of special interest to our work, (Guille-Escuret et al., 2024) performs an extensive empirical evaluation of the aiming condition, which they name the cosine similarity. They observe that for various tasks and architectures, $a$ remains between $10^{-1}$ and $10^{-3}$, despite the high dimensionality of the model. This observation was consistent across several stochastic first-order algorithms, including SGD with momentum. Although our theoretical results do not apply to general deep learning models, these experiments tend to highlight the crucial role of the aiming condition as a key ingredient in explaining the effectiveness of momentum.
Acknowledgements

This work was supported by PEPR PDE-AI. The author thanks Jean-François Aujol, Erell Gachon and Marien Reinaud for their feedback, which helped improve the presentation and clarity of this work.

Impact Statement

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

References

Abbaszadehpeivasti, H., de Klerk, E., and Zamani, M. Conditions for linear convergence of the gradient method for non-convex optimization. *Optimization Letters*, 17(5): 1105–1125, 2023.

Alimisis, F. Characterization of optimization problems that are solvable iteratively with linear convergence. *IFAC-PapersOnLine*, 58(17):280–285, 2024.

Alimisis, F. and Vandereycken, B. A geodesic convexity-like structure for the polar decomposition of a square matrix. *arXiv preprint arXiv:2412.13990*, 2024.

Alimisis, F., Islamov, R., and Lucchi, A. Why do we need warm-up? a theoretical perspective. *arXiv preprint arXiv:2510.03164*, 2025.

Altschuler, J., Chewi, S., Gerber, P. R., and Stromme, A. Averaging on the bures-wasserstein manifold: dimension-free convergence of gradient descent. *Advances in Neural Information Processing Systems*, 34:22132–22145, 2021.

Alvarez, F., Attouch, H., Bolte, J., and Redont, P. A second-order gradient-like dissipative dynamical system with hessian-driven damping.: Application to optimization and mechanics. *Journal de mathématiques pures et appliquées*, 81(8):747–779, 2002.

Ambrosio, L., Gigli, N., and Savaré, G. *Gradient flows: in metric spaces and in the space of probability measures*. Springer, 2005.

Apidopoulos, V., Ginatta, N., and Villa, S. Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under polyak–lojasiewicz condition. *Journal of Global Optimization*, 84(3):563–589, 2022.

Apidopoulos, V., Mavrogeorgou, V., and Tsironis, T. G. Heavy-ball dynamics with hessian-driven damping for non-convex optimization under the lojasiewicz condition. *arXiv preprint arXiv:2506.11705*, 2025.

Attouch, H., Chbani, Z., Fadili, J., and Riahi, H. First-order optimization algorithms via inertial systems with Hessian driven damping. *Mathematical Programming*, pp. 1–43, 2022.

Aujol, J.-F., Dossal, C., and Rondepierre, A. Convergence rates of the Heavy-Ball method under the lojasiewicz property. *Mathematical Programming*, 198(1):195–254, 2023.

Barboni, R., Peyré, G., and Vialard, F.-X. On global convergence of resnets: From finite to infinite width using linear parameterization. *Advances in Neural Information Processing Systems*, 35:16385–16397, 2022.

Benaïm, M. Dynamics of stochastic approximation algorithms. In *Seminaire de probabilites XXXIII*, pp. 1–68. Springer, 2006.

Bhojanapalli, S., Neyshabur, B., and Srebro, N. Global optimality of local search for low rank matrix recovery. *Advances in Neural Information Processing Systems*, 29, 2016.

Bolte, J., Nguyen, T. P., Peypouquet, J., and Suter, B. W. From error bounds to the complexity of first-order descent methods for convex functions. *Mathematical Programming*, 165(2):471–507, 2017.

Bu, J. and Mesbahi, M. A note on nesterov's accelerated method in nonconvex optimization: a weak estimate sequence approach. *arXiv preprint arXiv:2006.08548*, 2020.

Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. Lower bounds for finding stationary points of i. *Mathematical Programming*, 184(1-2):71–120, 2020.

Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. Lower bounds for finding stationary points ii: first-order methods. *Mathematical Programming*, 185(1):315–355, 2021.

Cevher, V. and Vu, B. C. On the linear convergence of the stochastic gradient method with constant step-size. *Optimization Letters*, 13(5):1177–1187, 2019.

Chen, L., Xiao, Q., Fukuda, E. H., Chen, X., Yuan, K., and Chen, T. Efficient first-order optimization on the pareto set for multi-objective learning under preference guidance. In *Forty-second International Conference on Machine Learning*, 2025.

Chen, Y., Shi, Y., Dong, M., Yang, X., Li, D., Wang, Y., Dick, R. P., Lv, Q., Zhao, Y., Yang, F., Gu, N., and Shang, L. Over-parameterized model optimization with polyak-lojasiewicz condition. In *The Eleventh International Conference on Learning Representations*, 2023. URL https://openreview.net/forum?id=aBIpZvMdS56.
Cohen, J., Kaur, S., Li, Y., Kolter, J. Z., and Talwalkar, A. Gradient descent on neural networks typically occurs at the edge of stability. In *International Conference on Learning Representations*, 2021.

Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Gangui, S., and Bengio, Y. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. *Advances in neural information processing systems*, 27, 2014.

de Brito, J., Lara, F., and Liu, D. Extending linear convergence of the proximal point algorithm: The quasar-convex case. *arXiv preprint arXiv:2509.04375*, 2025.

Defazio, A. On the curved geometry of accelerated optimization. *Advances in Neural Information Processing Systems*, 32, 2019.

Even, M., Berthier, R., Bach, F., Flammarion, N., Hendrikx, H., Gaillard, P., Massoulié, L., and Taylor, A. Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms. *Advances in Neural Information Processing Systems*, 34:28054–28066, 2021.

Farzin, A. A., Pun, Y.-M., and Shames, I. Minimisation of quasar-convex functions using random zeroth-order oracles. *arXiv preprint arXiv:2505.02281*, 2025.

Fazel, M., Ge, R., Kakade, S., and Mesbahi, M. Global convergence of policy gradient methods for the linear quadratic regulator. In *International conference on machine learning*, pp. 1467–1476. PMLR, 2018.

Fu, Q., Xu, D., and Wilson, A. C. Accelerated stochastic optimization methods under quasar-convexity. In *International Conference on Machine Learning*, pp. 10431–10460. PMLR, 2023.

Ge, R., Lee, J. D., and Ma, T. Matrix completion has no spurious local minimum. *Advances in neural information processing systems*, 29, 2016.

Ge, R., Jin, C., and Zheng, Y. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In *International conference on machine learning*, pp. 1233–1242. PMLR, 2017.

Gess, B. and Kassing, S. Exponential convergence rates for momentum stochastic gradient descent in the over-parametrized setting. *arXiv e-prints*, pp. arXiv:2302.2023.

Ghadimi, E., Feyzmahdavian, H. R., and Johansson, M. Global convergence of the heavy-ball method for convex optimization. In *2015 European control conference (ECC)*, pp. 310–315. IEEE, 2015.

Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. *SIAM journal on optimization*, 23(4):2341–2368, 2013.

Goujaud, B., Taylor, A., and Dieuleveut, A. Provable non-accelerations of the heavy-ball method: B. goujaud et al. *Mathematical Programming*, pp. 1–59, 2025.

Gower, R., Sebbouh, O., and Loizou, N. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. In *International Conference on Artificial Intelligence and Statistics*, pp. 1315–1323. PMLR, 2021.

Guille-Escuret, C., Girotti, M., Goujaud, B., and Mitliagkas, I. A study of condition numbers for first-order optimization. In *International Conference on Artificial Intelligence and Statistics*, pp. 1261–1269. PMLR, 2021.

Guille-Escuret, C., Naganuma, H., Fatras, K., and Mitliagkas, I. No wrong turns: The simple geometry of neural networks optimization paths. In *International Conference on Machine Learning*, pp. 16751–16772. PMLR, 2024.

Guo, H., Maulén, J. J., and Peypouquet, J. A speed restart scheme for a dynamical system with hessian-driven damping and three constant coefficients. *arXiv preprint arXiv:2412.06691*, 2024.

Gupta, K. and Wojtowytsch, S. Nesterov acceleration in benignly non-convex landscapes. In *The Thirteenth International Conference on Learning Representations*, 2025.

Gupta, K., Siegel, J. W., and Wojtowytsch, S. Nesterov acceleration despite very noisy gradients. In *The Thirty-eighth Annual Conference on Neural Information Processing Systems*, 2024.

He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pp. 770–778, 2016.

Hermant, J., Aujol, J.-F., Dossal, C., and Rondepierre, A. Study of the behaviour of nesterov accelerated gradient in a non convex setting: the strongly quasar convex case. *arXiv preprint arXiv:2405.19809*, 2024.

Hermant, J., Aujol, J.-F., Dossal, C., Huang, L., and Rondepierre, A. Continuized nesterov acceleration for non-convex optimization, 2025. URL https://arxiv.org/abs/2512.16533.

Hinder, O., Sidford, A., and Sohoni, N. Near-optimal methods for minimizing star-convex functions and beyond. In *Conference on learning theory*, pp. 1894–1938. PMLR, 2020.
Hinton, G. Neural networks for machine learning. Coursera Lecture 6e, 2012. Available at https://www.coursera.org/learn/neural-networks.

Karimi, H., Nutini, J., and Schmidt, M. Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiewicz condition. In *Joint European conference on machine learning and knowledge discovery in databases*, pp. 795–811. Springer, 2016.

Kassing, S. and Weissmann, S. Polyak's heavy ball method achieves accelerated local rate of convergence under polyak-lojasiewicz inequality. *arXiv preprint arXiv:2410.16849*, 2024.

Kim, J. and Yang, I. Unifying Nesterov's accelerated gradient methods for convex and strongly convex objective functions. In *Proceedings of the 40th International Conference on Machine Learning*, pp. 16897–16954. PMLR, 2023.

Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In Bengio, Y. and LeCun, Y. (eds.), *3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings*, 2015.

Lara, F. and Vega, C. Delayed feedback in online non-convex optimization: a non-stationary approach with applications. *Numerical Algorithms*, pp. 1–42, 2025.

Li, B., Shi, B., and Yuan, Y.-X. Linear convergence of forward-backward accelerated algorithms without knowledge of the modulus of strong convexity. *SIAM Journal on Optimization*, 34(2):2150–2168, 2024.

Li, H., Xu, Z., Taylor, G., Studer, C., and Goldstein, T. Visualizing the loss landscape of neural nets. *Advances in neural information processing systems*, 31, 2018.

Liao, F. and Kyrillidis, A. Provable accelerated convergence of nesterov's momentum for deep relu neural networks. In *International Conference on Algorithmic Learning Theory*, pp. 732–784. PMLR, 2024.

Liu, C., Zhu, L., and Belkin, M. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. *Applied and Computational Harmonic Analysis*, 59:85–116, 2022a.

Liu, C., Drusvyatskiy, D., Belkin, M., Davis, D., and Ma, Y. Aiming towards the minimizers: fast convergence of sgd for overparametrized problems. *Advances in neural information processing systems*, 36:60748–60767, 2023.

Liu, X., Pan, Z., and Tao, W. Provable convergence of nesterov's accelerated gradient method for over-parameterized neural networks. *Knowledge-Based Systems*, 251:109277, 2022b.

Liu, X., Tao, W., and Pan, Z. A convergence analysis of nesterov's accelerated gradient method in training deep linear neural networks. *Information Sciences*, 612:898–925, 2022c.

Lojasiewicz, S. A topological property of real analytic subsets. *Coll. du CNRS, Les équations aux dérivées partielles*, 117(87-89):2, 1963.

Malitsky, Y. and Mishchenko, K. Adaptive gradient descent without descent. In *International Conference on Machine Learning*, pp. 6702–6712. PMLR, 2020.

Mérigot, Q., Santambrogio, F., and Sarrazin, C. Non-asymptotic convergence bounds for wasserstein approximation using point clouds. *Advances in Neural Information Processing Systems*, 34:12810–12821, 2021.

Necoara, I., Nesterov, Y., and Glineur, F. Linear convergence of first order methods for non-strongly convex optimization. *Mathematical programming*, 175(1):69–107, 2019.

Nemirovskij, A. S. and Yudin, D. B. Problem complexity and method efficiency in optimization. *Wiley-Interscience*, 1983.

Nesterov, Y. A method for solving the convex programming problem with convergence rate o (1/k2). In *Dokl akad nauk Sssr*, volume 269, pp. 543, 1983.

Nesterov, Y. Introductory lectures on convex optimization. applied optimization, 2004.

Nesterov, Y. *Lectures on convex optimization*, volume 137. Springer, 2018.

Okamura, K., Marumo, N., and Takeda, A. Heavy-ball differential equation achieves $o(\epsilon^{-7/4})$ convergence for nonconvex functions. *arXiv preprint arXiv:2406.06100*, 2024.

Oymak, S. and Soltanolkotabi, M. Overparameterized non-linear learning: Gradient descent takes the shortest path? In *International Conference on Machine Learning*, pp. 4951–4960. PMLR, 2019.

Polyak, B. and Shcherbakov, P. Lyapunov functions: An optimization theory perspective. *IFAC-PapersOnLine*, 50 (1):7456–7461, 2017.

Polyak, B. T. Gradient methods for minimizing functionals. *USSR Computational Mathematics and Mathematical Physics*, 3(4):864–878, 1963. doi: 10.1016/0041-5553(63)90382-3.

Polyak, B. T. Some methods of speeding up the convergence of iteration methods. *Ussr computational mathematics and mathematical physics*, 4(5):1–17, 1964.
Polyak, B. T. Introduction to optimization. 1987.

Pun, Y.-M. and Shames, I. Online non-stationary stochastic quasar-convex optimization. *arXiv preprint arXiv:2407.03601*, 2024.

Renaud, M., Hermant, J., Wei, D., and Sun, Y. Provably accelerated imaging with restarted inertia and score-based image priors. *arXiv preprint arXiv:2510.07470*, 2025.

Romano, Y., Elad, M., and Milanfar, P. The little engine that could: Regularization by denoising (red). *SIAM journal on imaging sciences*, 10(4):1804–1844, 2017.

Shi, B., Du, S. S., Jordan, M. I., and Su, W. J. Understanding the acceleration phenomenon via high-resolution differential equations. *Mathematical Programming*, pp. 1–70, 2021.

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

Singh, S. P., He, B., Hofmann, T., and Schölkopf, B. The directionality of optimization trajectories in neural networks. In *The Thirteenth International Conference on Learning Representations*, 2025.

Solodov, M. V. Incremental gradient algorithms with step-sizes bounded away from zero. *Computational Optimization and Applications*, 11:23–35, 1998.

Su, W., Boyd, S., and Candès, E. J. A differential equation for modeling nesterov's accelerated gradient method: theory and insights. *Journal of Machine Learning Research*, 17(153):1–43, 2016. URL http://jmlr.org/papers/v17/15-084.html.

Sutskever, I., Martens, J., Dahl, G., and Hinton, G. On the importance of initialization and momentum in deep learning. In *International conference on machine learning*, pp. 1139–1147. pmlr, 2013.

Tseng, P. An incremental gradient (-projection) method with momentum term and adaptive stepsize rule. *SIAM Journal on Optimization*, 8(2):506–531, 1998.

Vaswani, S., Bach, F., and Schmidt, M. Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron. In *The 22nd international conference on artificial intelligence and statistics*, pp. 1195–1204. PMLR, 2019.

Wang, J.-K. and Wibisono, A. Continuized acceleration for quasar convex functions in non-convex optimization. In *The Eleventh International Conference on Learning Representations*, 2023. URL https://openreview.net/forum?id=yYbhKqdi7Hz.

Wang, J.-K., Lin, C.-H., and Abernethy, J. D. A modular analysis of provable acceleration via polyak's momentum: Training a wide relu network and a deep linear network. In *International Conference on Machine Learning*, pp. 10816–10827. PMLR, 2021.

Wang, J.-K., Lin, C.-H., Wibisono, A., and Hu, B. Provable acceleration of heavy ball beyond quadratics for a class of polyak-lojasiewicz functions when the non-convexity is averaged-out. In *International conference on machine learning*, pp. 22839–22864. PMLR, 2022.

Xu, Z., Min, H., Tarmoun, S., Mallada, E., and Vidal, R. A local polyak-lojasiewicz and descent lemma of gradient descent for overparametrized linear models. *Transactions on Machine Learning Research*, 2025.

Yue, P., Fang, C., and Lin, Z. On the lower bound of minimizing Polyak-Łojasiewicz functions. In *The Thirty Sixth Annual Conference on Learning Theory*, pp. 2948–2968. PMLR, 2023.

Zhang, H. and Yin, W. Gradient methods for convex minimization: better rates under weaker conditions. *arXiv preprint arXiv:1303.4645*, 2013.
# A. Related Works and Background Details

In this section, we first provide bibliographical details about Table 1 (Appendix A.1), then give more details about a specific related work in Appendix A.2.

## A.1. Details for Table 1

In this section, we detail Table 1, giving in particular references for the results. We note that some of the results do not exist in the literature. Before, we state the following result that we will use in this section.

**Proposition A.1.** Let $(x_t, z_t)_{t \ge 0}$ verify (NMO). Then, it verifies the Heavy Ball equation with Hessian damping

$$ \ddot{x}_t + \left( \eta_t - \frac{\dot{\eta}_t}{\eta_t} + \eta'_t \right) \dot{x}_t + \gamma \nabla^2 f(x_t) \dot{x}_t + \left( \eta'_t \gamma + \eta_t \gamma' - \frac{\dot{\eta}_t}{\eta_t} \gamma \right) \nabla f(x_t) = 0. \quad (3) $$

Proposition A.1 states that (NMO) can be written as the Heavy Ball equation with Hessian damping (Alvarez et al., 2002). We will use results established for this equation in the case of (NMO).

**About SC**$^{µ}$ The rate for (GF) can be deduced from the one in the PL$^{µ}$ case. The rate stated for (NMO) can be found in the case of heavy ball with Hessian damping in (Shi et al., 2021), from which we deduce the same rate for (NMO). The rates for (GD) and (NM) can be found in (Nesterov, 2018).

**About SQC**$^{µ}$ See Proposition A.2 for the rate of (GF). The rate of (GD) can be found in (Hermant et al., 2024, Proposition 3). The rate stated for (NMO) can be found in the case of heavy ball with Hessian damping in (Hermant et al., 2024, Theorem 5), from which we deduce the same rate for (NMO). The rate for (NM) requires some care. It can be found in (Hinder et al., 2020, Theorem 1), but involves a line-search procedure that requires computing evaluations of $f$ and $\nabla f$ at each iteration to compute one of the parameters. It can also be found in (Hermant et al., 2024, Theorem 2) up to a supplementary assumption of weak-convexity, namely $f + \rho/2 \|\cdot\|^2$ is convex for some $\rho \in \mathbb{R}$, with $\rho \le L$. Finally, it can be found in (Wang & Wibisono, 2023, Theorem 2) up to non-deterministic results, because of the use of the continuized parameterization.

**About PL**$^{µ}$ The rate $\mu$ for (GF) can be found in (Polyak & Shcherbakov, 2017, Theorem 3). The rate $\mu/L$ for (GD) has been known for a long time (Polyak, 1963; Bolte et al., 2017), see (Karimi et al., 2016, Theorem 1) for a direct proof. The rate for (NM) can be found in (Hermant et al., 2025, Proposition 7), but holds with high probability because of the use of the continuized framework. We note that using the Heavy Ball algorithm (HB), this rate can be improved to a rate close to $\sqrt{\mu/L}$ if assuming that $f$ is four times differentiable, and if the algorithm is initialized close enough to the minimizer (Kassing & Weissmann, 2024). The case of (NMO) is more complicated. For Polyak's momentum (Heavy Ball equation), a result exists assuming $f$ is also in $LS^L$, yielding a convergence rate $\approx \mu/\sqrt{L}$ (Apidopoulos et al., 2022). For the same equation, the rate $\sqrt{\mu}$ holds asymptotically, provided that $f$ is four times differentiable, providing strong local regularity around minimizers (Kassing & Weissmann, 2024). In the case of Heavy Ball with Hessian damping, a rate $\sqrt{\mu}$ is deduced (Apidopoulos et al., 2025), but the gradient term in the equation is rescaled by $O(1/\sqrt{\mu})$, which means we are minimizing a rescaled version of the function. In Proposition A.3, we actually show without assuming $f \in LS^L$ or smoother than $C^1$–and with a considerably simpler proof than the previously mentioned works–that (NMO) achieves a rate $\gamma\mu$, where $\gamma$ is a parameter of (NMO). It highlights that we can achieve whatever rate we want, as long as we take $\gamma$ big enough. However, in the discrete case, $\gamma$ corresponding intuitively to the stepsize, it appears clearly that the descent lemma induced by $f \in LS^L$ will impose a bound on $\gamma$, namely $\gamma \le 1/L$, yielding a rate $\mu/L$.

### A.1.1. PROOF OF NOT EXISTING RATES OF TABLE 1

**Proposition A.2.** Let $f \in SQC_{\tau}^{\mu}$, $(x_t)_{t \ge 0} \sim (\text{GF})$. Then,

$$ f(x_t) - f^* = O(e^{-\tau \mu t}). $$

*Proof.* Let

$$ E_t = f(x_t) - f^* + \frac{\mu}{2} \|x_t - x^*\|^2. $$
Then

$$
\begin{align*}
\dot{E}_t &= \langle \nabla f(x_t), \dot{x}_t \rangle + \mu \langle x_t - x^*, \dot{x}_t \rangle \\
&\stackrel{(i)}{=} - \|\nabla f(x_t)\|^2 - \mu \langle \nabla f(x_t), x_t - x^* \rangle \\
&\leq -\mu \langle \nabla f(x_t), x_t - x^* \rangle \\
&\stackrel{(ii)}{\leq} -\mu \tau \left( f(x_t) - f^* + \frac{\mu}{2} \|x_t - x^*\|^2 \right) = -\mu \tau E_t,
\end{align*}
$$

where (i) follows from (GF) and (ii) from $f \in \text{SQC}_\tau^\mu$. Integrating yields $E_t \le e^{-\mu\tau t} E_0$, hence $f(x_t) - f^* \le E_t = O(e^{-\mu\tau t})$. $\square$

**Proposition A.3.** Let $f \in \text{PL}^\mu$. Let $(x_t)_{t \ge 0} \sim (\text{NMO})$ with $\eta_t \equiv \eta$ and $\eta'_t \equiv \eta'$ constants and under the constraint $\gamma = (\eta + \eta')/\mu$. Then, we have

$$f(x_t) - f^* = \mathcal{O}(e^{-2\mu\gamma t}).$$

*Proof.* Let

$$E_t = f(x_t) - f^* + \frac{\delta}{2} \|x_t - z_t\|^2.$$

Then

$$
\begin{align*}
\dot{E}_t &= \langle \nabla f(x_t), \dot{x}_t \rangle + \delta \langle x_t - z_t, \dot{x}_t - \dot{z}_t \rangle \\
&\stackrel{(i)}{=} \langle \nabla f(x_t), \eta(z_t - x_t) - \gamma \nabla f(x_t) \rangle + \delta \langle x_t - z_t, (\eta + \eta')(z_t - x_t) + (\gamma' - \gamma) \nabla f(x_t) \rangle \\
&= (\eta + \delta(\gamma - \gamma')) \langle \nabla f(x_t), z_t - x_t \rangle - \gamma \|\nabla f(x_t)\|^2 - \delta(\eta + \eta') \|z_t - x_t\|^2,
\end{align*}
$$

where (i) follows from (NMO). Using $f \in \text{PL}^\mu$, we have $-\gamma \|\nabla f(x_t)\|^2 \le -2\mu\gamma(f(x_t) - f^*)$, hence

$$\dot{E}_t \le (\eta + \delta(\gamma - \gamma')) \langle \nabla f(x_t), z_t - x_t \rangle - 2\mu\gamma(f(x_t) - f^*) - \delta(\eta + \eta') \|z_t - x_t\|^2.$$

Impose $\eta + \delta(\gamma - \gamma') = 0$ (i.e. $\delta = \eta/(\gamma' - \gamma)$) and $\eta + \eta' = \mu\gamma$. Then $\dot{E}_t \le -2\mu\gamma E_t$, so $E_t \le e^{-2\mu\gamma t} E_0$. Since $f(x_t) - f^* \le E_t$, the claim follows. $\square$

### A.1.2. PROOF OF PROPOSITION A.1

The following proof is borrowed to (Hermant et al., 2025, Proposition 27). From the first line of (NMO), we have

$$z_t = x_t + \frac{1}{\eta_t} (\dot{x}_t + \gamma \nabla f(x_t)). \qquad (4)$$

Differentiating (4) yields

$$\dot{z}_t = \dot{x}_t - \frac{\dot{\eta}_t}{\eta_t^2} (\dot{x}_t + \gamma \nabla f(x_t)) + \frac{1}{\eta_t} (\ddot{x}_t + \gamma \nabla^2 f(x_t) \dot{x}_t). \qquad (5)$$

Using this expression and the second line of (NMO), we obtain

$$\dot{x}_t - \frac{\dot{\eta}_t}{\eta_t^2} (\dot{x}_t + \gamma \nabla f(x_t)) + \frac{1}{\eta_t} (\ddot{x}_t + \gamma \nabla^2 f(x_t) \dot{x}_t) = \eta'_t (x_t - z_t) - \gamma' \nabla f(x_t) \qquad (6)$$

$$= -\frac{\eta'_t}{\eta_t} \dot{x}_t - \frac{\eta'_t \gamma}{\eta_t} \nabla f(x_t) - \gamma' \nabla f(x_t), \qquad (7)$$

where we used $x_t - z_t = -\frac{1}{\eta_t} (\dot{x}_t + \gamma \nabla f(x_t))$. Multiplying by $\eta_t$ and rearranging, we get

$$\ddot{x}_t + \left( \eta_t - \frac{\dot{\eta}_t}{\eta_t} + \eta'_t \right) \dot{x}_t + \gamma \nabla^2 f(x_t) \dot{x}_t + \left( \eta'_t \gamma + \eta_t \gamma' - \frac{\dot{\eta}_t}{\eta_t} \gamma \right) \nabla f(x_t) = 0. \qquad (8)$$
## A.2. Comparison with Theorem 7 of (Hermant et al., 2024)

**Theorem A.4** (Hermant et al., 2024). Let $f \in PL^\mu$, with a unique minimizer $x^*$. Then, there exists $(\tau, \mu') \in (0, 1] \times \mathbb{R}_+^*$ such that $f \in SQC_\tau^{\mu'}$ if and only if

$$ \exists a > 0, \forall x \in \mathbb{R}^d, \quad 1 \ge \frac{\langle \nabla f(x), x - x^* \rangle}{\|\nabla f(x)\| \|x - x^*\|} \ge a > 0, \qquad (9) $$

In particular if (9) holds, then as long as $\tau < \frac{2\mu a}{L}$, F is $(\gamma, \frac{\mu a}{\tau} - \frac{L}{2})$-strongly quasar-convex.

The parameters derived in Theorem A.4 are significantly different compared to those we deduce from our analysis, see Appendix G. Theorem A.4 ensures that, at best, we can take $\tau = O(a^\mu)$, inducing $\mu' = O(L)$. We are in the setting where the condition number interpretation fails for strongly quasar-convex functions, see Section 3. Also, plugging these choices of parameters in Table 1 in the line of convergence rate for SQC$\tau^\mu$, if the convergence rates of (GF) and (GD) remain the same, namely $a\mu$ and $a\mu/L$ respectively, the convergence rates of (NMO) and (NM) however also reduce to $a\mu$ and $a\mu/L$ respectively, such that we do not obtain accelerated bound with Nesterov's momentum.

## A.3. Choice of Parameters for SQC$\tau^\mu$.

In Section 3, we discuss that $\sup_\tau \sup_\mu \{(\tau, \mu) \in (0, 1] \times \mathbb{R}_+ : f \in SQC_\tau^\mu\}$ and $\sup_\mu \sup_\tau \{(\tau, \mu) \in (0, 1] \times \mathbb{R}_+ : f \in SQC_\tau^\mu\}$ leads to different choices of parameters. To justify this statement, we assume there exists $\tau, \mu \in (0, 1] \times \mathbb{R}_+$ such that $f \in SQC_\tau^\mu$. We first recall $f \in SQC_\tau^\mu \Rightarrow f \in SQC_{\tau^\mu}^\theta$, for all $\theta \in (0, 1]$ (Hinder et al., 2020, Observation 5). Letting $\theta \to 0$, it follows that

$$ \arg\sup_{\tau} \arg\sup_{\mu} \{(\tau, \mu) \in (0, 1] \times \mathbb{R}_+ : f \in SQC_{\tau}^{\mu}\} = (0, +\infty). $$

On the other hand, it is clear that $\arg\sup_\mu \arg\sup_\tau \{(\tau, \mu) \in (0, 1] \times \mathbb{R}_+ : f \in SQC_\tau^\mu\} \ne (0, +\infty)$.

# B. More Details on Figures and Numerical Experiments

In this section, we provide details about our method to generate Figure 1, Figure 2 (Appendix B.1) and Figure 3 (Appendix B.2). We provide in Appendix B.3 a heuristic discussion of the bound over aiming condition to have acceleration derived in Section 4.2. We also provide in Appendix B.4 additional figures, useful for the main text but that could not be included because of space limitations. Our figures and experiments are reproducible; see the code in the supplement.

## B.1. Details about Figure 1 and Figure 2

In this section, we detail how we numerically compute the convergence rate of the functions displayed in Figure 1 and Figure 2. We split our presentation between the two underlying functions.

**One-dimensional example** The function displayed on the left in Figure 1 is

$$ f(t) = 5(t + 0.19 \sin(5t))^2, $$

defined on $[-2, 2]$. It has 0 as its unique critical point and minimizer, which satisfies $f(0) = 0$. We define a grid of $10^5$ points in $[-2, 2]$, equally spaced. This grid has been refined until the subsequent numerical values are not impacted by further refinement. For the i-th point $x_i$ in this grid, we compute the associated point-wise PL value

$$ \mu_i = \frac{f'(x_i)^2}{2f(x_i)}, $$

and point-wise L-smooth value

$$ L_i = |f''(x_i)|. $$

We define $\mu := \min_{1 \le i \le 10^5} \mu_i$ and $L := \max_{1 \le i \le 10^5} L_i$ the constant such that numerically, $f \in PL^\mu \cap LS^L$ on $[-2, 2]$. On this domain, we thus obtain a convergence rate $\mu/L$ for (GD).

Because of the double parameterization, the case of SQC$\tau^\mu$ is slightly more involved. We define a grid of 1000 potential $\tau$ parameters, equally spaced in $[10^{-5}, 0.1]$. Note that we take $10^{-5}$ as the lower bound for this interval instead of zero, to
avoid dividing by zero. For a given $\tau_j$ in the grid on $[10^{-5}, 0.1]$, and each $x_i$ belonging to the grid on $[-2, 2]$, we compute the point-wise strong quasar convexity constant $\mu'_{i,j}$

$$ \mu'_{i,j} = -2 \frac{(f(x_i) - f'(x_i)x_i)}{x_i^2} $$

For this $\tau_j$, we define $\mu'_j = \min_{1 \le i \le 10^5} \mu_{i,j}$ the constant such that numerically, $f \in \text{SQC}_{\tau_j}^{\mu_j}$. In the case where $\mu_j \le 0$, we consider $\tau_j$ is not admissible, which occurs for $\tau_j \ge 0.1$. The pairs $(\tau_j, \mu_j)_{1 \le j \le 1000}$ thus generate Figure 2, by plotting $(\tau_j \mu_j / L)_{1 \le j \le 1000}$ for (GD) and $(\tau_j \sqrt{\mu_j / L})_{1 \le j \le 1000}$ for (NM). As a supplement, we plot in Figure $(\tau_j \mu_j)_{1 \le j \le 1000}$ and $(\tau_j \sqrt{\mu_j})_{1 \le j \le 1000}$ which are the convergence rates of (GF) and (NMO). We observe a similar behavior compared with the discrete case. Finally, we obtain the convergence rate values of Figure 1 by considering $\max_{1 \le j \le 1000} \tau_j \mu_j / L$ for (GD), and $\max_{1 \le j \le 1000} \tau_j \sqrt{\mu_j / L}$ for (NM). As illustrated in Figure 2, the pair $(\tau_{j_0}, \mu_{j_0})$ that maximizes the rate of (GD) differs from the pair $(\tau_{j_1}, \mu_{j_1})$ that maximizes the rate of (NM).

**Two-dimensional example** The function displayed on the left in Figure 1 is

$$ f(x, y) = 0.5(0.5x^2 - y)^2 + 0.05x^2, $$

defined on the square $[-1.2638, 1.2638]^2$. It has a unique minimizer and critical point at $(0, 0)$. To compute the convergence rate for this function, we proceed similarly to the one-dimensional case. The only difference is that we define a two-dimensional grid on $[-1.2638, 1.2638]^2$ of $10^6$ points, equally spaced. The grid has been refined until the numerical values we compute are not impacted by further refinement.

## B.2. Details about Figure 3

In Figure 3, we optimize

$$ F_{\varepsilon}(x, y) = 0.5(y - \sin(x))^2 + 0.5\varepsilon x^2, $$

with $\varepsilon = 10^{-3}$. It is clear that $F_{\varepsilon}(0, 0) = 0$ is a global minimizer, and for all $(x, y) \ne (0, 0)$, $F_{\varepsilon}(x, y) > 0$. This function has no other critical point, which is induced by the fact that it is PL.

**Lemma B.1.** For $x, y \in \mathbb{R}$, $\varepsilon > 0$ the function $F_{\varepsilon}(x, y) = \frac{1}{2}(y - \sin x)^2 + \frac{1}{2}\varepsilon x^2$ belongs to $\text{PL}^{\mu}$ with

$$ \mu \le \frac{2 + \varepsilon - \sqrt{\varepsilon^2 + 4}}{2}. $$

*Proof.* Consider the function

$$ F_{\varepsilon}(x, y) = \frac{1}{2}(y - \sin x)^2 + \frac{1}{2}\varepsilon x^2, \quad x, y \in \mathbb{R}, \varepsilon > 0. $$

Let

$$ u(x, y) := y - \sin x. $$

Then

$$ F_{\varepsilon} = \frac{1}{2}(u^2 + \varepsilon x^2). $$

The gradient is

$$ \nabla F_{\varepsilon} = \begin{pmatrix} -u \cos x + \varepsilon x \\ u \end{pmatrix}, \quad \|\nabla F_{\varepsilon}\|^2 = u^2 + (-u \cos x + \varepsilon x)^2. $$

Writing both sides as quadratic forms in $z = (u(x, y), x)^{\top}$, we obtain

$$ 2F_{\varepsilon} = z^{\top} \begin{pmatrix} 1 & 0 \\ 0 & \varepsilon \end{pmatrix} z, \quad \|\nabla F_{\varepsilon}\|^2 = z^{\top} \begin{pmatrix} 1 + \cos^2 x & -\varepsilon \cos x \\ -\varepsilon \cos x & \varepsilon^2 \end{pmatrix} z. $$
Define

$$N = \begin{pmatrix} 1 & 0 \\ 0 & \epsilon \end{pmatrix}, \quad M(x) = \begin{pmatrix} 1 + \cos(x)^2 & -\epsilon \cos(x) \\ -\epsilon \cos(x) & \epsilon^2 \end{pmatrix}, \quad c := \cos x \in [-1, 1].$$

So, f belong to PL$^{\mu}$ with

$$\begin{align} \mu = \min_{\substack{z=(u(x,y),x) \neq 0, \\ (x,y) \in \mathbb{R}^2}} \frac{z^T M(x) z}{z^T N z} &\ge \min_{\substack{z=(z_1,z_2), \\ (z_1,z_2) \in \mathbb{R}^2 \setminus (0,0)}} \frac{z^T M(x) z}{z^T N z} \nonumber \\ &\stackrel{(i)}{=} \min_{\substack{z=(z_1,z_2), \\ (z_1,z_2) \in \mathbb{R}^2 \setminus (0,0)}} \frac{z^T N^{-1/2} M(x) N^{-1/2} z}{z^T z} \tag{10} \\ &\stackrel{(ii)}{=} \lambda_{\min}(N^{-1/2} M(x) N^{-1/2}), \nonumber \end{align}$$

where (i) holds with the reparameterization $z' = N^{-1/2}z$, and (ii) is a property of the Rayleigh coefficient. We consider the matrix

$$N^{-1/2} M(x) N^{-1/2} = \begin{pmatrix} 1 + \cos(x)^2 & -\sqrt{\epsilon} \cos(x) \\ -\sqrt{\epsilon} \cos(x) & \epsilon \end{pmatrix} := \begin{pmatrix} 1 + c^2 & -\sqrt{\epsilon} c \\ -\sqrt{\epsilon} c & \epsilon \end{pmatrix} := B(c), \quad c := \cos(x) \in [-1, 1].$$

So, we have

$$\lambda_{\min}(N^{-1/2} M(x) N^{-1/2}) \ge \inf_{c \in [-1,1]} \lambda_{\min}(B(c)).$$

The eigenvalues of $B(c)$ are

$$\lambda_{\pm}(c) = \frac{\operatorname{tr}(B(c)) \pm \sqrt{\operatorname{tr}(B(c))^2 - 4 \det(B(c))}}{2}.$$

We have

$$\det(B(c)) = \epsilon, \quad \operatorname{tr}(B(c)) = 1 + c^2 + \epsilon.$$

Such that we solve

$$\min_{c \in [-1,1]} \frac{1+c^2+\epsilon - \sqrt{(1+c^2+\epsilon)^2 - 4\epsilon}}{2} = \min_{t \in [0,1]} \frac{1+t+\epsilon - \sqrt{(1+t+\epsilon)^2 - 4\epsilon}}{2} := \phi(t).$$

We have for $t \in [0, 1]$,

$$2\phi'(t) = 1 - \frac{1 + t + \epsilon}{\sqrt{(1 + t + \epsilon)^2 - 4\epsilon}} \le 0,$$

such that $\phi$ is decreasing on $[0, 1]$. So, the minimum is reached for $t = 1 \Rightarrow c^2 = 1$, which leads to the eigenvalue

$$\inf_{c \in [-1,1]} \lambda_{\min}(B(c)) = \lambda_{\min}(B(1)) = \frac{2 + \epsilon - \sqrt{\epsilon^2 + 4}}{2} > 0.$$

Therefore, for all $(x, y) \in \mathbb{R}^2$,

$$\|\nabla F_{\epsilon}(x, y)\|^2 \ge 2\mu F_{\epsilon}(x, y),$$

with

$$\mu \le \frac{2 + \epsilon - \sqrt{\epsilon^2 + 4}}{2}.$$

The Hessian matrix of $F_{\epsilon}$ at $(x, y)$ is

$$\nabla^2 F_{\epsilon}(x, y) = \begin{pmatrix} \cos(x)^2 + \sin(x)(y - \sin(x) + \epsilon) & -\cos(x) \\ -\cos(x) & 1 \end{pmatrix}.$$
The function is not globally L-smooth, because of the y factor in $\nabla_{1,1}^2 F_{\varepsilon}(x, y)$. However, for a fixed y, the eigenvalues are bounded for any $x \in \mathbb{R}$.

**Implementation Details** We fix $\varepsilon = 10^{-3}$, and chose $(0, 3)$ as the initialization point. We compute the L-smooth value of $F_{0.001}$ on the domain $[-2\pi, 2\pi] \times [-3, 3]$, using a grid of $10^6$ equally spaced points. We then fix $\gamma = 1/L$ for both (GD) and (NM').

### B.3. Test of the acceleration bound of Section 4.2 on the hard PL$^{\mu}$ instance of (Yue et al., 2023)

In this section, we provide a heuristic validation of the bound on the aiming condition to provide acceleration, derived in Section 4.2. To do so, we consider the PL$^{\mu}$ function introduced in (Yue et al., 2023), which serves to obtain a lower bound on the number of gradient calls needed by first order algorithms–algorithms that make use of gradient information–to obtain a point $\hat{x} \in \mathbb{R}^d$ such that $f(\hat{x}) - \min f \le \varepsilon$. Precisely, it is shown that the number of needed gradient calls scales at best as $O(\frac{L}{\mu} \log(\frac{1}{\varepsilon}))$ for any first-order algorithms. This bound corresponds to a $\mu/L$ convergence rate, inducing that, up to constants, the convergence rate of (GD) is optimal, see Table 1. The definition of the hard instance is rather involved. The core object of its definition is the following function

$$g_{T,t}(x) = q_{T,t}(x) + \sum_{i=1}^{Tt} v_{y_i}(x_i),$$

where $x_i$ is the i-th coordinate of $x \in \mathbb{R}^{Tt} \to \mathbb{R}$, where $q_{T,t}(x)$ is defined as follows

$$q_{T,t}(x) = \frac{1}{2} \sum_{i=0}^{t-1} \left[ \left( \frac{7}{8} x_{iT} - x_{iT+1} \right)^2 + \sum_{j=1}^{T-1} (x_{iT+j+1} - x_{iT+j})^2 \right],$$

and for all $y \in \mathbb{R}$, $v_y(t)$ is the following one-dimensional function

$$v_y(t) = \begin{cases} \frac{1}{2}t, & t \le \frac{31}{32}y, \\ \frac{1}{2}t^2 - 16(t - \frac{31}{32})^2, & \frac{31}{32}y < t \le y, \\ \frac{1}{2}t^2 - \frac{y^2}{32} + 16(t - \frac{33}{32}y)^2, & y < t \le \frac{33}{32}y, \\ \frac{1}{2}t^2 - \frac{y}{32}, & t > \frac{33}{32}y. \end{cases}$$

The function $q_{T,t}$ belongs to the class of zero-chain functions (Nesterov, 2004; Carmon et al., 2020; 2021), which are hard to minimize with first-order algorithms. The key idea is that for these functions, if starting from 0, first-order algorithms will be able to explore only one new coordinate at each iteration for a number of iterations equal to the dimension of the problem. Here, the $v_y(\cdot)$ components introduce non-convexity. Up to a rescaling, the function $g_{T,t}$ belongs to PL$^{\mu} \cap LS^L$ for desired constants $\mu$ and $L$, see all details in (Yue et al., 2023).

Note that $q_{T,t}$ is a strongly convex quadratic function, such that it belongs to $SQC_{\tau}^{\mu}$ for some parameters. Also, for any $y \in \mathbb{R}$, one can check that the function $v_y(\cdot)$ has zero as its unique minimizer and belongs to PL$^{\mu} \cap LS^L$ for some parameter, which implies it belongs to $SQC_{\tau}^{\mu} \cap LS^L$ because the function is one-dimensional. It follows that the function $\sum_{i=1}^{Tt} v_{y_i}(x_i)$ also belongs to $SQC_{\tau}^{\mu} \cap LS^L$ for some parameters, with unique minimizer $0 \in \mathbb{R}^d$. Then, $g_{T,t}$ belongs to $SQC_{\tau}^{\mu} \cap LS^L$ as a sum of strongly quasar convex functions with the same minimizer $0 \in \mathbb{R}^d$ (Hinder et al., 2020, Section D.3). In particular, it implies that it belongs to $AC^a$ for some $a > 0$, see Appendix G. This provides an example of a function that belongs to PL$^{\mu} \cap AC^a \cap LS^L$ such that momentum does not provide acceleration.

**Non acceleration of momentum on the hard function** We observe empirically that, as expected, momentum does not allow improvement over gradient descent when minimizing the hard function of (Yue et al., 2023). We consider (GD) and (NM) with the continuous parameterization. We chose the parameter of the scaled function such that it belongs to PL$^{\mu} \cap LS^L$ with $\mu = 10^{-4}$, $L = 10^3$, and the dimension is 4550. For both (GD) and (NM), we tune the parameters such that the decrease at iteration 1000 is maximized. We plot the decrease of function values of the hard function in Figure 10. We observe that tuning of (NM) only permits to catch up with the decrease of (GD), but provides no acceleration.

### Heuristic test of the acceleration bound
In Section 4.2, we stated that for $f \in PL^\mu \cap AC^a \cap LS^L$, momentum provide acceleration as long as

$$a \geq \left(\frac{L_0}{\mu_0}\right)^{1/4} \sqrt{\frac{\mu}{L}}.$$

It is natural to test whether this bound is verified or not on the aforementioned hard function. Importantly, the following discussion should be regarded as a **heuristic**, rather than a rigorous derivation.

For our test, we do not consider the global parameters $\mu, a, L$ such that $f$ belongs to $PL^\mu \cap AC^a \cap LS^L$. This is because (i) we do not know the optimal parameters $a, \mu_0$ and $L_0$, and (ii) in the lower bound provided in (Yue et al., 2023), there is a hidden constant with values $\approx 10^6$, which is not negligible. Moreover, the decrease observed in Figure 10 is significantly faster than what is predicted by the theoretical bound derived under the global parameters, such that it actually poorly describes the algorithm's behavior. This motivates to use a perspective that has a similar spirit to the one described in Section 5, such that we will consider the values of PL and aiming condition taken along the optimization path. Along the iterates of $\{\tilde{x}_k\}_{k \ge 0}$ generated by (GD) or (NM), we compute the point-wise PL and aiming condition values, namely

$$\mu(\tilde{x}_i) := 2 \frac{\|\nabla f(\tilde{x}_i)\|^2}{f(\tilde{x}_i) - f^*}, \quad a(\tilde{x}_i) := \frac{\langle \nabla f(\tilde{x}_i), \tilde{x}_i - x^* \rangle}{\|\nabla f(\tilde{x}_i)\| \|\tilde{x}_i - x^*\|}.$$

Empirically, we observe that $\mu(\tilde{x}_i) \approx 1$ (see Figure 11), while the function is $PL^\mu$ with $\mu = 10^{-4}$. This suggests that the algorithm stays in favorable regions compared to those existing on the global landscape. As a result, in the case of (GD), compared to the rate $\mu/L$, we expect that its convergence rate is more accurately described by

$$\tilde{\mu}_{gd}/L,$$

with $\tilde{\mu}_{gd} = \frac{1}{N} \sum_{i=1}^N \mu(\tilde{x}_i)$ is the averaged point-wise PL values along the $N$ iterations of the algorithm. Moreover, because we observed that (GD) achieves a better decrease with stepsize $\gamma_{gd} \ge 1/L$, running the algorithm with this stepsize suggests that an even more accurate rate is

$$\tilde{\mu}_{gd}\gamma_{gd}. \qquad (11)$$

We plot the curve associated to this theoretical rate in Figure 10. We observe that, if not matching perfectly the decrease of (GD), it is significantly more accurate compared with the rate $\mu/L$. Following the same reasoning, we will model the rate for (NM) as (see Theorem 4.4 (ii))

$$\tilde{a}(\tilde{\mu}_0/\tilde{L}_0)^{1/4} \sqrt{\tilde{\mu}_{nm}\gamma_{nm}}, \qquad (12)$$

where $\tilde{a} = \frac{1}{N} \sum_{i=1}^N a(\tilde{x}_i)$ and $\tilde{\mu}_{nm} = \frac{1}{N} \sum_{i=1}^N \mu(\tilde{x}_i)$ are respectively the point-wise aiming condition value and point-wise PL values along the algorithm, and $\tilde{\mu}_0$ and $\tilde{L}_0$ are estimation of the optimal constant involved in $QG^0$ and $QG^L$, and $\gamma_{nm} \ge L$ is the used stepsize for (NM) that arises from the tuning of parameters. The parameters used in (NM) result from grid-search rather than the theoretical recommendation of Theorem 4.4, and we observe that (NM) has a slightly better decreasing rate compared to the bound (12). Up to associating the empirical decreasing rate of (GD) and (NM) with the bounds (11) and (12), we thus test the acceleration condition of Section 4.2 by comparing $\tilde{a}$ with

$$\frac{\tilde{\mu}_{gd}\gamma_{gd}}{\sqrt{\gamma_{nm}\tilde{\mu}_{nm}}} \left(\frac{\tilde{L}_0}{\tilde{\mu}_0}\right)^{\frac{1}{4}}.$$

We find numerically that $\tilde{a} \approx 0.16$, while $\frac{\tilde{\mu}_{gd}\gamma_{gd}}{\sqrt{\gamma_{nm}\tilde{\mu}_{nm}}} \left(\frac{\tilde{L}_0}{\tilde{\mu}_0}\right)^{\frac{1}{4}} \approx 0.19$ such that they are roughly the same. So, in this setting where (NM) does not accelerate over (GD), we observe that the acceleration condition of Section 4.2 is indeed not verified. This gives heuristic weights to the relevance of this bound. Finally, this suggests that the function that serves as lower bound for PL functions, which actually belongs to $PL^\mu \cap AC^a \cap LS^L$, is such that the aiming condition values do not scale properly with other geometrical constants to permit acceleration using momentum.

## B.4. Supplementary Figures

In this section, we provide some figures that are not in the main text, due to available space.
**About Figure 4** We display in Figure 4 two synthetic examples of functions belonging to SQC<sub>τ</sub><sup>μ</sup>, in dimension one and two.
The one-dimensional example is

$$f(t) = 0.5 \cdot (t + 0.15 \sin(5t))^2.$$

The two dimensional example is $h: \mathbb{R}^2 \to \mathbb{R}$, built as follows:

$$h(x) = f(\|x\|)g\left(\frac{x}{\|x\|}\right) \qquad (13)$$

where $f(t) = t^2$ and

$$g(x_1, x_2) = \frac{1}{4N} \sum_{i=1}^{N} (a_i \sin(b_i x_1)^2 + c_i \cos(d_i x_2)^2) + 1 \qquad (14)$$

with $N = 10$ and the ${a_i}_i$, ${c_i}_i$ are independently and uniformly distributed on $[0, 20]$, and the ${b_i}_i$, ${d_i}_i$ are independently and uniformly distributed on $[-25, 25]$. It is borrowed from (Hermant et al., 2024).

<figure><img src="image_5.png" /><figcaption>Figure 4. Visualization of functions belonging in SQC<sub>τ</sub><sup>μ</sup>, for some parameters. The figure is borrowed from (Hermant et al., 2025), see details in Appendix B.4.</figcaption></figure>

**About Figure 5** Figure 5 displays a simple one-dimensional example where $f \in LS^L \cap QG_+^{L_0}$ with $L$ significantly larger than $L_0$, and similarly for $f \in PL^\mu \cap QG_-^{\mu_0}$. Such differences are created by local variations outside of the vicinity of the minimizer. This is because the parameterizing $QG_+^{L_0}$ and $QG_-^{\mu_0}$ is mainly affected by the geometry in the vicinity of the minimizer, while $LS^L$ and $PL^\mu$ are strongly sensitive to variations at any points.

**About Figure 6** Figure 6 illustrates that, for a function belonging to $PL^\mu$, the optimal $\mu$ may depend on the local smaller curvature at a minimizer $x^*$, or by plateaus.

## C. Technical Lemmas

The following lemmas serve as technical tools for our convergence proofs.

**Lemma C.1.** Let $f \in PL^\mu \cap AC^a \cap QG_+^{L_0}$. Let $\mu_0 := \sup\{\mu' \ge \mu : f \in QG_-^{\mu'}\}$. Then, for all $x \in \mathbb{R}^d$,

$$\langle \nabla f(x), x^* - x \rangle \le -a \sqrt{\frac{\mu}{L_0}} (f(x) - f^*) - \frac{a}{2} \sqrt{\mu \mu_0} \|x - x^*\|^2.$$

*Proof.* If $x = x^*$, the inequality holds trivially. Assume $x \neq x^*$.

**Step 1 (AC + PL).** Since $f \in AC^a$, we have

$$\langle \nabla f(x), x - x^* \rangle \ge a \|\nabla f(x)\| \|x - x^*\|, \quad \text{hence} \quad \langle \nabla f(x), x^* - x \rangle \le -a \|\nabla f(x)\| \|x - x^*\|.$$
<figure><img src="image_6.png" /><figcaption>Figure 5. The grey curve is $f(t) = 0.5 \cdot 5(t + 0.07 \sin(13t))^2$. The blue (red) curve is a quadratic upper (lower) bound. We compute the largest $\mu$ and smallest $L$ such that $f \in \text{PL}^\mu \cap \text{LS}^L$ on the displayed domain, numerically evaluated at $\mu \approx 4 \cdot 10^{-2}$, $L \approx 6 \cdot 10^2$. Also, the parameters $L_0$ and $\mu_0$ that parameterize the quadratic bounds are $\mu_0 \approx 3$ and $L_0 \approx 18$. On this prototype 1-dimensional example, $\frac{\mu_0}{L_0} \approx 0.2$ while $\frac{\mu}{L} \approx 7 \cdot 10^{-5}$. This highlight the possibility of a significant gap between these two ratios.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 6. Left: Simple 1-dimensional functions in $\text{SC}^\mu$, so also in $\text{PL}^\mu$. The worst approaching direction toward the minimizer $t^*$ is the red zone, which determines the optimal $\mu$ constant. Right: Simple non-convex function that belongs to $\text{PL}^\mu$ for some $\mu > 0$. The $\mu$ constant could be determined either by the local flatness around the minimizer $t^*$ (red zone), or by the flatness of the plateau (blue zone).</figcaption></figure>

Since $f \in \text{PL}^\mu$, we also have $\|\nabla f(x)\| \ge \sqrt{2\mu}\sqrt{f(x) - f^*}$, so

$$ \langle \nabla f(x), x^* - x \rangle \le -a\sqrt{2\mu} \sqrt{f(x) - f^*} \|x - x^*\|. \quad (15) $$

**Step 2 (use $\text{QG}_+^{L_0}$).** Since $f \in \text{QG}_+^{L_0}$,

$$ f(x) - f^* \le \frac{L_0}{2} \|x - x^*\|^2 \quad \Rightarrow \quad \|x - x^*\| \ge \sqrt{\frac{2}{L_0}} \sqrt{f(x) - f^*}. $$

Plugging this into (15) yields

$$ \langle \nabla f(x), x^* - x \rangle \le -a\sqrt{2\mu} \sqrt{\frac{2}{L_0}} (f(x) - f^*) = -2a\sqrt{\frac{\mu}{L_0}} (f(x) - f^*). \quad (16) $$

**Step 3 (use $\text{QG}_-^{\mu_0}$).** By definition of $\mu_0$, we have

$$ f(x) - f^* \ge \frac{\mu_0}{2} \|x - x^*\|^2 \quad \Rightarrow \quad \sqrt{f(x) - f^*} \ge \sqrt{\frac{\mu_0}{2}} \|x - x^*\|. $$

Plugging this into (15) yields

$$ \langle \nabla f(x), x^* - x \rangle \le -a\sqrt{2\mu} \sqrt{\frac{\mu_0}{2}} \|x - x^*\|^2 = -a\sqrt{\mu\mu_0} \|x - x^*\|^2. \quad (17) $$

**Step 4 (combine the two bounds).** From (16) and (17), we have

$$ \langle \nabla f(x), x^* - x \rangle \le -\max\left\{2a\sqrt{\frac{\mu}{L_0}}(f(x) - f^*), a\sqrt{\mu\mu_0} \|x - x^*\|^2\right\}. $$
<figure><img src="image_8.png" /><figcaption>Figure 7. 3-dimensional visualization of $F_{0.001}(x, y) = 0.5(y - \sin(x))^2 + 0.001 \cdot 0.5x^2$, considered in Section 6</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 8. Plot of the 3000 first iterations of the trajectories of (GD) and (NM') on $f$, when minimizing $F_{0.001}(x, y) = 0.5(y - \sin(x))^2 + 0.001 \cdot 0.5x^2$. This is a version of Figure 3 with 3000 iterations instead of 1000. Observe that the decrease of the momentum method (NM') catches up with the one of (GD), which is coherent with the values of the aiming condition.</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 9. For a range of parameters $\tau$, we compute the highest admissible $\mu$ ensuring $f \in \text{SQC}_{\tau}^{\mu}$, and plot the associated theoretical convergence rates of (GF) and (NMO) under $\text{SQC}_{\tau}^{\mu}$, namely $\tau\mu$ and $\tau\sqrt{\mu}$, with $f(t) = 5(t + 0.19 \sin(5t))^2$. See details in Appendix B.1. This is the continuous counterpart of Figure 2. Similarly to the discrete setting, the pair $(\tau, \mu)$ that maximizes the convergence rate differ in both cases.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 10. Function values decrease when running (GD) and (NM) on the hard instance of (Yue et al., 2023). We also plot the log of the theoretical convergence upper bound $\log((1 - \mu\gamma)^k(f(x_0) - f^*))$ with $\mu$ the global PL constant, and the log of the theoretical convergence upper bound using parameter values across the path, see (11) and (12) in Appendix B.3. It can be observed that (GD) and (NM) decrease at same speed, and that the bounds proposed at (11) and (12) are significantly more accurate compared with the global worst case bound.</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>Figure 11. Left: Values of $\mu(\tilde{x}_i)$ along the iterates of (GD) and (NM). Values of $a(\tilde{x}_i)$ along the iterates of (NM). The underlying function is the hard instance of (Yue et al., 2023), see details in Appendix B.3.</figcaption></figure>

Since $\max\{u, v\} \ge \frac{u+v}{2}$ for $u, v \ge 0$, we obtain

$$ \langle \nabla f(x), x^* - x \rangle \le -\frac{1}{2} \left( 2a \sqrt{\frac{\mu}{L_0}} (f(x) - f^*) + a \sqrt{\mu\mu_0} \|x - x^*\|^2 \right), $$

which is the claim.

**Lemma C.2.** Let $f \in PL^\mu \cap QG_+^{L_0}$. Noting $\mu_0 := \sup\{\mu' \ge \mu : f \in QG_-^{\mu'}\}$, we have for all $x \in \mathbb{R}^d$,

$$ \|x - x^*\| \|\nabla f(x)\| \ge \sqrt{\frac{\mu}{L_0}} (f(x) - f^*) + \frac{\sqrt{\mu\mu_0}}{2} \|x - x^*\|^2. $$

*Proof.* If $x = x^*$, the statement is trivial. Assume $x \ne x^*$ and write

$$ \|x - x^*\| \|\nabla f(x)\| = \|x - x^*\| \sqrt{f(x) - f^*} \frac{\|\nabla f(x)\|}{\sqrt{f(x) - f^*}}. $$

(1) **Step 1 (PL$^\mu$ and QG$^{L_0}_+$).** Since $f \in PL^\mu$, $\|\nabla f(x)\| \ge \sqrt{2\mu} \sqrt{f(x) - f^*}$, and since $f \in QG_+^{L_0}$,

$$ f(x) - f^* \le \frac{L_0}{2} \|x - x^*\|^2 \quad \Rightarrow \quad \|x - x^*\| \ge \sqrt{\frac{2}{L_0}} \sqrt{f(x) - f^*}. $$

Therefore,

$$ \|x - x^*\| \|\nabla f(x)\| \ge \sqrt{\frac{2}{L_0}} (f(x) - f^*) \sqrt{2\mu} = 2\sqrt{\frac{\mu}{L_0}} (f(x) - f^*). \quad (18) $$

**Step 2 (PL$^\mu$ and QG$^{\mu_0}_-$).** By definition of $\mu_0$

$$ f(x) - f^* \ge \frac{\mu_0}{2} \|x - x^*\|^2 \quad \Rightarrow \quad \sqrt{f(x) - f^*} \ge \sqrt{\frac{\mu_0}{2}} \|x - x^*\|. $$

Combining with $\|\nabla f(x)\| \ge \sqrt{2\mu} \sqrt{f(x) - f^*}$ gives

$$ \|x - x^*\| \|\nabla f(x)\| \ge \sqrt{\mu\mu_0} \|x - x^*\|^2. \quad (19) $$

**Combine the bounds** From (18) and the previous bound,

$$ \|x - x^*\| \|\nabla f(x)\| \ge \max\left\{2\sqrt{\frac{\mu}{L_0}}(f(x) - f^*), \sqrt{\mu\mu_0} \|x - x^*\|^2\right\}. $$

Using $\max\{u, v\} \ge \frac{u+v}{2}$ for $u, v \ge 0$, we obtain

$$ \|x - x^*\| \|\nabla f(x)\| \ge \sqrt{\frac{\mu}{L_0}} (f(x) - f^*) + \frac{\sqrt{\mu\mu_0}}{2} \|x - x^*\|^2, $$

which concludes the proof.
**Lemma C.3.** Assume $x \neq x^*$ and $f(x) \neq f^*$. Define the point-wise quantities

$$ \mu(x) = \frac{1}{2} \frac{\|\nabla f(x)\|^2}{f(x) - f^*}, \quad a(x) = \frac{\langle \nabla f(x), x - x^* \rangle}{\|\nabla f(x)\| \|x - x^*\|}, \quad \mu_0(x) = 2 \frac{f(x) - f^*}{\|x - x^*\|^2}. $$

Then,

$$ \langle \nabla f(x), x^* - x \rangle = -a(x) \sqrt{\frac{\mu(x)}{\mu_0(x)}} (f(x) - f^*) - \frac{a(x)}{2} \sqrt{\mu(x)\mu_0(x)} \|x - x^*\|^2. $$

If $f \in PL^\mu$, it follows

$$ \langle \nabla f(x), x^* - x \rangle = -a(x) \sqrt{\frac{\mu}{\mu_0}} (f(x) - f^*) - \frac{a(x)}{2} \sqrt{\mu \mu_0} \|x - x^*\|^2, $$

with $\mu_0 := \sup\{\mu' \ge \mu : f \in QG^\mu\}$.

*Proof.* By definition of $a(x)$,

$$ \langle \nabla f(x), x^* - x \rangle = -a(x) \|\nabla f(x)\| \|x - x^*\|. $$

Moreover, by the definitions of $\mu(x)$ and $\mu_0(x)$,

$$ \|\nabla f(x)\| = \sqrt{2\mu(x)}\sqrt{f(x) - f^*}, \quad \|x - x^*\| = \sqrt{\frac{2}{\mu_0(x)}}\sqrt{f(x) - f^*}. $$

Hence

$$ \|\nabla f(x)\| \|x - x^*\| = 2\sqrt{\frac{\mu(x)}{\mu_0(x)}} (f(x) - f^*). $$

Also, using $\|\nabla f(x)\| = \sqrt{2\mu(x)}\sqrt{f(x) - f^*} = \sqrt{2\mu(x)}\sqrt{\frac{\mu_0(x)}{2}} \|x - x^*\|$,

$$ \|\nabla f(x)\| \|x - x^*\| = \sqrt{\mu(x)\mu_0(x)} \|x - x^*\|^2. $$

Combining the two equal expressions and using $\xi = \frac{1}{2}\xi + \frac{1}{2}\xi$ with $\xi = \|\nabla f(x)\| \|x - x^*\|$ gives

$$ \|\nabla f(x)\| \|x - x^*\| = \sqrt{\frac{\mu(x)}{\mu_0(x)}} (f(x) - f^*) + \sqrt{\mu(x)\mu_0(x)} \frac{1}{2} \|x - x^*\|^2, $$

and multiplying by $-a(x)$ yields the claim. $\square$

## D. Proofs of Section 4

This section is dedicated to proving the results of Section 4. In the discrete setting, we will actually prove a more general result, replacing the gradient with a stochastic estimator, under a strong growth condition, also sometimes named multiplicative noise assumption.

**Assumption D.1 (Strong growth condition).** We assume we have access to stochastic approximations $\nabla f(x, \xi)$ of the real gradient $\nabla f(x)$, where $\xi \sim 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$.

To our knowledge, this assumption was introduced in (Polyak, 1987), and further used by (Cevher & Vu, 2019) and (Vaswani et al., 2019) as a relaxation of the maximal strong growth condition (Tseng, 1998; Solodov, 1998). We avoid this more general setting in the main text, to discard adding a layer of complexity. The deterministic case is a special instance of Assumption D.1, corresponding to $\rho = 1$. For functions in $LS^L$ that verify Assumption D.1, we have a stochastic descent lemma, see (Gupta et al., 2024, Lemma 16).
**Lemma D.2.** If $f \in LS^L$ and Assumption D.1 holds, then we have

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

In the subsequent sections, for an algorithm $\{\tilde{x}_k\}_{k \ge 0}$ we denote $\mathbb{E}_k[\cdot] = \mathbb{E}[\cdot | \mathcal{F}_k]$. For a sequence $\{\xi_k\}_{k \in \mathbb{N}}$ of random variables, we note $\mathcal{F}_k = \sigma(\xi_0, \dots, \xi_k)$ the filtration generated by $\xi_0, \dots, \xi_k$.

### D.1. Proof of Theorem 4.2

(i) $f \in \text{PL}^{\mu}$ The following proof is classical (Polyak & Shcherbakov, 2017). We provide a proof the sake of completeness. Let

$$ E_t = f(x_t) - f^*. $$

By definition of (GF), we have

$$ \dot{E}_t = \langle \nabla f(x_t), \dot{x}_t \rangle = - \| \nabla f(x_t) \|^2 \le -2\mu (f(x_t) - f^*) = -2\mu E_t, $$

where we used $f \in \text{PL}^{\mu}$. By integration,

$$ f(x_t) - f^* \le e^{-2\mu t} (f(x_0) - f^*). $$

(ii) $f \in \text{PL}^{\mu} \cap \text{AC}^a \cap \text{QG}_+^{L_0}$ Let

$$ E_t = f(x_t) - f^* + \frac{\beta}{2} \|x_t - x^*\|^2. $$

Then

$$ \begin{aligned} \dot{E}_t &= \langle \nabla f(x_t), \dot{x}_t \rangle + \beta \langle x_t - x^*, \dot{x}_t \rangle \\ &= - \| \nabla f(x_t) \|^2 - \beta \langle \nabla f(x_t), x_t - x^* \rangle \\ &\le -\beta \langle \nabla f(x_t), x_t - x^* \rangle = \beta \langle \nabla f(x_t), x^* - x_t \rangle. \end{aligned} $$

By Lemma C.1, for all $t \ge 0$,

$$ \langle \nabla f(x_t), x^* - x_t \rangle \le -a \sqrt{\frac{\mu}{L_0}} (f(x_t) - f^*) - \frac{a}{2} \sqrt{\mu \mu_0} \|x_t - x^*\|^2, $$

hence

$$ \dot{E}_t \le -\beta a \sqrt{\frac{\mu}{L_0}} (f(x_t) - f^*) - \frac{\beta a}{2} \sqrt{\mu \mu_0} \|x_t - x^*\|^2. $$

Choose $\beta$ so that the two coefficients match:

$$ \beta a \sqrt{\frac{\mu}{L_0}} = a \sqrt{\mu \mu_0} \quad \Rightarrow \quad \beta = \sqrt{\mu_0 L_0}. $$

Then

$$ \dot{E}_t \le -a \sqrt{\mu \mu_0} (f(x_t) - f^* + \frac{\beta}{2} \|x_t - x^*\|^2) = -a \sqrt{\mu \mu_0} E_t, $$

and by integration,

$$ E_t \le e^{-a \sqrt{\mu \mu_0} t} E_0. $$

Since $f \in \text{QG}_-^{\mu_0}$, we have

$$ \frac{\beta}{2} \|x_0 - x^*\|^2 \le \beta \frac{1}{\mu_0} (f(x_0) - f^*) = \sqrt{\frac{L_0}{\mu_0}} (f(x_0) - f^*), $$

so $E_0 \le (1 + \sqrt{\frac{L_0}{\mu_0}}) (f(x_0) - f^*)$. Finally, since $f(x_t) - f^* \le E_t$, we deduce

$$ f(x_t) - f^* \le \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) e^{-a \sqrt{\mu \mu_0} t} (f(x_0) - f^*). $$
## D.2. Proof of Theorem 4.3

We prove the following more general result.

**Theorem D.3.** Let $f \in LS^L$. Let $\{\tilde{x}_k\}_{k \in \mathbb{N}} \sim (\text{GD})$ with $\nabla f(\tilde{x}_k)$ replaced by $\nabla f(\tilde{x}_k, \xi_k)$, where $\xi_k$ is independent of $\tilde{x}_k$, and assume Assumption D.1. Let $\gamma = \frac{1}{\rho L}$.

(i) If $f \in PL^\mu$, then

$$ \mathbb{E}[f(\tilde{x}_k) - f^*] \le \left(1 - \frac{\mu}{\rho L}\right)^k (f(\tilde{x}_0) - f^*). $$

(ii) If $f \in PL^\mu \cap AC^a \cap QG_+^{L_0}$, then

$$ \mathbb{E}[f(\tilde{x}_k) - f^*] \le \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) \left(1 - \frac{a\sqrt{\mu\mu_0}}{\rho L}\right)^k (f(\tilde{x}_0) - f^*), $$

with $\mu_0 := \sup\{\mu' \ge \mu : f \in QG_-^{\mu'}\}$ and $L_0 := \inf\{L' \le L : f \in QG_+^{L'}\}$.

The result for Theorem 4.3 is deduced in the case $\rho = 1$, which removes the expectations.

*Proof of Theorem D.3. (i) $f \in PL^\mu$* This result and proof is well known, see by instance (Karimi et al., 2016) in the deterministic setting, (Vaswani et al., 2019) for the stochastic case. We provide a proof for completeness. Define

$$ E_k = f(\tilde{x}_k) - f^*. $$

By Lemma D.2,

$$ \mathbb{E}_k [E_{k+1} - E_k] = \mathbb{E}_k [f(\tilde{x}_{k+1}) - f(\tilde{x}_k)] \le -\frac{1}{2\rho L} \|\nabla f(\tilde{x}_k)\|^2. $$

Since $f \in PL^\mu$, $\|\nabla f(\tilde{x}_k)\|^2 \ge 2\mu(f(\tilde{x}_k) - f^*) = 2\mu E_k$, hence

$$ \mathbb{E}_k [E_{k+1}] \le \left(1 - \frac{\mu}{\rho L}\right) E_k. $$

By induction and taking expectation,

$$ \mathbb{E}[E_k] \le \left(1 - \frac{\mu}{\rho L}\right)^k E_0, $$

which is the claim.

(ii) $f \in PL^\mu \cap AC^a \cap QG_+^{L_0}$ Set $\beta := \sqrt{\mu_0 L_0}$ and define

$$ E_k = f(\tilde{x}_k) - f^* + \frac{\beta}{2} \|\tilde{x}_k - x^*\|^2. $$

Using the update $\tilde{x}_{k+1} = \tilde{x}_k - \gamma \nabla f(\tilde{x}_k, \xi_k)$, we expand

$$ \|\tilde{x}_{k+1} - x^*\|^2 - \|\tilde{x}_k - x^*\|^2 = -2\gamma \langle \tilde{x}_k - x^*, \nabla f(\tilde{x}_k, \xi_k) \rangle + \gamma^2 \|\nabla f(\tilde{x}_k, \xi_k)\|^2. $$

Taking $\mathbb{E}_k[\cdot]$, using Assumption D.1 (unbiasedness + SGC) and Lemma D.2, we obtain

$$ \begin{aligned} \mathbb{E}_k [E_{k+1} - E_k] &\le -\frac{1}{2\rho L} \|\nabla f(\tilde{x}_k)\|^2 + \frac{\beta}{2} \left( -2\gamma \langle \tilde{x}_k - x^*, \nabla f(\tilde{x}_k) \rangle + \gamma^2 \rho \|\nabla f(\tilde{x}_k)\|^2 \right) \\ &= \left( -\frac{1}{2\rho L} + \frac{\beta}{2}\gamma^2 \rho \right) \|\nabla f(\tilde{x}_k)\|^2 - \beta\gamma \langle \tilde{x}_k - x^*, \nabla f(\tilde{x}_k) \rangle. \end{aligned} $$

With $\gamma = \frac{1}{\rho L}$, we have $\gamma^2 \rho = \frac{1}{\rho L^2}$, hence

$$ -\frac{1}{2\rho L} + \frac{\beta}{2}\gamma^2 \rho = -\frac{1}{2\rho L} + \frac{\beta}{2\rho L^2} = -\frac{1}{2\rho L} \left(1 - \frac{\beta}{L}\right) \le 0, $$
because $\beta = \sqrt{\mu_0 L_0} \le L_0 \le L$. Therefore,

$$ \mathbb{E}_k [E_{k+1} - E_k] \le -\frac{\beta}{\rho L} \langle \tilde{x}_k - x^*, \nabla f(\tilde{x}_k) \rangle = \frac{\beta}{\rho L} \langle \nabla f(\tilde{x}_k), x^* - \tilde{x}_k \rangle . $$

By Lemma C.1,

$$ \langle \nabla f(\tilde{x}_k), x^* - \tilde{x}_k \rangle \le -a \sqrt{\frac{\mu}{L_0}} (f(\tilde{x}_k) - f^*) - \frac{a}{2} \sqrt{\mu \mu_0} \|\tilde{x}_k - x^*\|^2 . $$

Multiplying by $\beta/(\rho L)$ and using $\beta\sqrt{\mu/L_0} = \sqrt{\mu\mu_0}$ (since $\beta = \sqrt{\mu_0 L_0}$), we get

$$ \mathbb{E}_k [E_{k+1} - E_k] \le -\frac{a\sqrt{\mu\mu_0}}{\rho L} (f(\tilde{x}_k) - f^*) - \frac{a\sqrt{\mu\mu_0}}{\rho L} \frac{\beta}{2} \|\tilde{x}_k - x^*\|^2 = -\frac{a\sqrt{\mu\mu_0}}{\rho L} E_k. $$

Hence

$$ \mathbb{E}_k [E_{k+1}] \le \left(1 - \frac{a\sqrt{\mu\mu_0}}{\rho L}\right) E_k, $$

taking the expectation and by induction,

$$ \mathbb{E}[E_k] \le \left(1 - \frac{a\sqrt{\mu\mu_0}}{\rho L}\right)^k E_0. $$

Finally, since $f(\tilde{x}_k) - f^* \le E_k$, and using $f \in \mathbb{Q}\mathbb{G}^{\mu_0}$,

$$ \frac{\beta}{2} \|\tilde{x}_0 - x^*\|^2 \le \beta \frac{1}{\mu_0} (f(\tilde{x}_0) - f^*) = \sqrt{\frac{L_0}{\mu_0}} (f(\tilde{x}_0) - f^*), $$

so $E_0 \le (1 + \sqrt{\frac{L_0}{\mu_0}}) (f(\tilde{x}_0) - f^*)$. This yields the claim. $\square$

### D.3. Proof of Theorem 4.4

(i) Assume that $\eta_t \equiv \eta$, $\eta'_t \equiv \eta'$ are constants. Let

$$ E_t = e^{\theta t} (f(x_t) - f^* + \beta \frac{1}{2} \|z_t - x^*\|^2). \qquad (21) $$

Then $E_t = E_0 + \int_0^t \dot{E}_s ds$, where

$$ \begin{aligned} \dot{E}_t &= \theta e^{\theta t} (f(x_t) - f^*) + \theta \beta \frac{e^{\theta t}}{2} \|z_t - x^*\|^2 + e^{\theta t} \langle \nabla f(x_t), \dot{x}_t \rangle + \beta e^{\theta t} \langle z_t - x^*, \dot{z}_t \rangle \\ &= \theta e^{\theta t} (f(x_t) - f^*) + \theta \beta \frac{e^{\theta t}}{2} \|z_t - x^*\|^2 + e^{\theta t} \langle \nabla f(x_t), \eta(z_t - x_t) - \gamma \nabla f(x_t) \rangle \\ &\quad + \beta e^{\theta t} \langle z_t - x^*, \eta'(x_t - z_t) - \gamma' \nabla f(x_t) \rangle \\ &= \theta e^{\theta t} (f(x_t) - f^*) + \theta \beta \frac{e^{\theta t}}{2} \|z_t - x^*\|^2 - \gamma e^{\theta t} \|\nabla f(x_t)\|^2 \\ &\quad + e^{\theta t} \eta \langle \nabla f(x_t), z_t - x_t \rangle + \beta \eta' e^{\theta t} \langle z_t - x^*, x_t - z_t \rangle - \beta \gamma' e^{\theta t} \langle \nabla f(x_t), z_t - x^* \rangle. \end{aligned} \qquad (22) $$

Using the decomposition

$$ \langle \nabla f(x_t), z_t - x_t \rangle = \langle \nabla f(x_t), x^* - x_t \rangle + \langle \nabla f(x_t), z_t - x^* \rangle, $$

and the identity

$$ \langle z_t - x^*, x_t - z_t \rangle = \frac{1}{2} \|x_t - x^*\|^2 - \frac{1}{2} \|z_t - x^*\|^2 - \frac{1}{2} \|x_t - z_t\|^2 \le \frac{1}{2} \|x_t - x^*\|^2 - \frac{1}{2} \|z_t - x^*\|^2, $$
we obtain from (22)

$$e^{-\theta t} \dot{E}_t \le \theta(f(x_t) - f^*) + \frac{\beta}{2} (\theta - \eta') \|z_t - x^*\|^2 + \frac{\beta \eta'}{2} \|x_t - x^*\|^2 \\ + \eta \langle \nabla f(x_t), x^* - x_t \rangle + (\eta - \beta \gamma') \langle \nabla f(x_t), z_t - x^* \rangle - \gamma \|\nabla f(x_t)\|^2. \quad (23)$$

We choose $\eta' = \theta$ to cancel the $\|z_t - x^*\|^2$ term, and we choose $\eta = \beta\gamma'$ to cancel the $\langle \nabla f(x_t), z_t - x^* \rangle$ term. Dropping the negative term $-\gamma \|\nabla f(x_t)\|^2$, we get

$$e^{-\theta t} \dot{E}_t \le \theta(f(x_t) - f^*) + \eta \langle \nabla f(x_t), x^* - x_t \rangle + \frac{\beta \theta}{2} \|x_t - x^*\|^2. \quad (24)$$

By Lemma C.1,

$$\langle \nabla f(x_t), x^* - x_t \rangle \le -a \sqrt{\frac{\mu}{L_0}} (f(x_t) - f^*) - \frac{a}{2} \sqrt{\mu \mu_0} \|x_t - x^*\|^2.$$

Plugging into (24) yields

$$e^{-\theta t} \dot{E}_t \le \left(\theta - \eta a \sqrt{\frac{\mu}{L_0}}\right) (f(x_t) - f^*) + \frac{1}{2} \left(\beta \theta - \eta a \sqrt{\mu \mu_0}\right) \|x_t - x^*\|^2. \quad (25)$$

We impose the cancellation of both coefficients in (25):

$$\theta = \eta a \sqrt{\frac{\mu}{L_0}} \quad \text{and} \quad \beta \theta = \eta a \sqrt{\mu \mu_0}.$$

These two equalities are equivalent to $\beta = \sqrt{\mu_0 L_0}$ and $\theta = \eta a \sqrt{\mu/L_0}$. With the additional choice $\eta = \beta\gamma'$, we may take

$$\beta = \sqrt{\mu_0 L_0}, \quad \gamma' = \beta^{-1/2} = (\mu_0 L_0)^{-1/4}, \quad \eta = \beta\gamma' = (\mu_0 L_0)^{1/4}, \quad \eta' = \theta = a \left(\frac{\mu_0}{L_0}\right)^{1/4} \sqrt{\mu}.$$

With these parameters, (25) gives $e^{-\theta t} \dot{E}_t \le 0$, hence $E_t \le E_0$. Therefore, using (21),

$$f(x_t) - f^* \le e^{-\theta t} E_t \le e^{-\theta t} E_0 = \exp\left(-a\left(\frac{\mu_0}{L_0}\right)^{1/4} \sqrt{\mu t}\right) E_0.$$

Finally, using $x_0 = z_0$ and $f \in \mathrm{QG}^{\mu_0}$,

$$\frac{\beta}{2} \|x_0 - x^*\|^2 \le \beta \frac{1}{\mu_0} (f(x_0) - f^*) = \sqrt{\frac{L_0}{\mu_0}} (f(x_0) - f^*),$$

so $E_0 \le \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) (f(x_0) - f^*)$, yields the claim.

(ii) The proof in the discrete case exploits the continuous framework. This implies that the following analysis differs from the previous ones. We refer to Appendix F to a brief introduction of the tools needed when carrying such analysis, or (Hermant et al., 2025) for a more detailed introduction. Also, we will prove the following more general result.

**Theorem D.4.** Let $f \in PL^\mu \cap AC^a \cap LS^L$. Denote $L_0 := \inf\{L' \le L : f \in \mathrm{QG}^{L'}\}$, $\mu_0 := \sup\{\mu' \ge \mu : f \in \mathrm{QG}^{\mu'}\}$. Let $\{\tilde{x}_k\}_{k \in \mathbb{N}}$ verify (NM) with the continuous parameterization and with $\nabla f(\tilde{x}_k)$ replaced by $\nabla f(\tilde{x}_k, \xi_k)$ for random variables $\xi_k$ independent of $\tilde{x}_k$ and under Assumption D.1. Let $\eta' = \frac{a}{\rho} \left(\frac{\mu_0}{L_0}\right)^{1/4} \sqrt{\frac{\mu}{L}}$, $\gamma = \frac{1}{\rho L}$, $\gamma' = \frac{1}{\rho} \frac{1}{(\mu_0 L_0)^{1/4} \sqrt{L}}$, and $\eta = \frac{1}{\rho} \frac{(\mu_0 L_0)^{1/4}}{\sqrt{L}}$. Then, with probability $1 - \frac{1}{c_0} - \exp(-(c_1 - 1 - \log(c_1))k)$, for some $c_0 > 1$ and $c_1 \in (0, 1)$ we have

$$f(\tilde{x}_k) - f^* \le K_1 e^{-\frac{a}{\rho} \left(\frac{\mu_0}{L_0}\right)^{1/4} \sqrt{\frac{\mu}{L}} (1-c_1)k},$$

where $K_1 := c_0 \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) (f(x_0) - f^*)$.
The proof of Theorem 4.4 (ii) is deduced in the case $\rho = 1$.

*Proof of Theorem D.4.* Let $\bar{x}_t = (t, x_t, z_t)$. 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} 1 \\ \eta(z_t - x_t) \\ \eta'(x_t - z_t) \end{pmatrix}, \quad G(\bar{x}_t, \xi) = \begin{pmatrix} 0 \\ -\gamma \nabla f(x_t, \xi) \\ -\gamma' \nabla f(x_t, \xi) \end{pmatrix}.$$

We apply Proposition F.1 to $\phi(t) = \varphi(\bar{x}_t)$, where

$$\varphi(t, x, z) = A_t(f(x) - f^*) + \frac{B_t}{2} \|z - x^*\|^2.$$

Hence

$$\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 (26)$$

where $M_t$ is a martingale.

We have

$$\frac{\partial \varphi}{\partial s}(\bar{x}_s) = \frac{dA_s}{ds}(f(x_s) - f^*) + \frac{1}{2} \frac{dB_s}{ds} \|z_s - x^*\|^2, \quad \frac{\partial \varphi}{\partial x}(\bar{x}_s) = A_s \nabla f(x_s), \quad \frac{\partial \varphi}{\partial z}(\bar{x}_s) = B_s(z_s - x^*).$$

So,

$$\langle \nabla \varphi(\bar{x}_s), b(\bar{x}_s) \rangle = \frac{dA_s}{ds}(f(x_s) - f^*) + \frac{1}{2} \frac{dB_s}{ds} \|z_s - x^*\|^2 \\ + A_s \eta \langle \nabla f(x_s), z_s - x_s \rangle + B_s \eta' \langle z_s - x^*, x_s - z_s \rangle. \quad (27)$$

Also,

$$\mathbb{E}_{\xi}[\varphi(\bar{x}_s + G(\bar{x}_s, \xi)) - \varphi(\bar{x}_s)] = \mathbb{E}_{\xi}[A_s(f(x_s - \gamma \nabla f(x_s, \xi)) - f(x_s))] \\ + \frac{B_s}{2} \mathbb{E}_{\xi}[\|z_s - \gamma' \nabla f(x_s, \xi) - x^*\|^2 - \|z_s - x^*\|^2] \\ = A_s \mathbb{E}_{\xi}[f(x_s - \gamma \nabla f(x_s, \xi)) - f(x_s)] + \frac{B_s \gamma'^2}{2} \mathbb{E}_{\xi}[\|\nabla f(x_s, \xi)\|^2] \quad (28)$$

$$+ B_s \gamma' \langle \nabla f(x_s), x^* - z_s \rangle, \quad (29)$$

where we used $\mathbb{E}_{\xi}[\nabla f(x_s, \xi)] = \nabla f(x_s)$.

As $f \in \text{LS}^L$ and Assumption D.1 holds, by Lemma D.2 (with $\gamma = \frac{1}{\rho L}$),

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

Moreover, by the strong growth condition, $\mathbb{E}_{\xi}[\|\nabla f(x_s, \xi)\|^2] \leq \rho \|\nabla f(x_s)\|^2$. Hence

$$(28) \leq \frac{1}{2} \left( \rho B_s \gamma'^2 - \frac{A_s}{\rho L} \right) \|\nabla f(x_s)\|^2. \quad (30)$$

We use the identity

$$\langle z_s - x^*, x_s - z_s \rangle = \frac{1}{2} \|x_s - x^*\|^2 - \frac{1}{2} \|z_s - x^*\|^2 - \frac{1}{2} \|x_s - z_s\|^2 \leq \frac{1}{2} \|x_s - x^*\|^2 - \frac{1}{2} \|z_s - x^*\|^2. \quad (31)$$

Also,

$$A_s \eta \langle \nabla f(x_s), z_s - x_s \rangle + B_s \gamma' \langle \nabla f(x_s), x^* - z_s \rangle = A_s \eta \langle \nabla f(x_s), x^* - x_s \rangle + (A_s \eta - B_s \gamma') \langle \nabla f(x_s), z_s - x^* \rangle. \quad (32)$$
By Lemma C.1,

$$ \langle \nabla f(x_s), x^* - x_s \rangle \leq -a \sqrt{\frac{\mu}{L_0}} (f(x_s) - f^*) - \frac{a}{2} \sqrt{\mu\mu_0} \|x_s - x^*\|^2. $$

Gathering (27), (29), (30), (31), and (32), we obtain

$$ \begin{aligned} & \langle \nabla \varphi(\bar{x}_s), b(\bar{x}_s) \rangle + \mathbb{E}_{\xi} [\varphi(\bar{x}_s + G(\bar{x}_s, \xi)) - \varphi(\bar{x}_s)] \\ & \leq \frac{1}{2} \left( \frac{dB_s}{ds} - B_s \eta' \right) \|z_s - x^*\|^2 + \frac{1}{2} (B_s \eta' - A_s \eta a \sqrt{\mu\mu_0}) \|x_s - x^*\|^2 + \left( \frac{dA_s}{ds} - A_s \eta a \sqrt{\frac{\mu}{L_0}} \right) (f(x_s) - f^*) \\ & \quad + (A_s \eta - B_s \gamma') \langle \nabla f(x_s), z_s - x^* \rangle + \frac{1}{2} \left( \rho B_s \gamma'^2 - \frac{A_s}{\rho L} \right) \|\nabla f(x_s)\|^2. \end{aligned} $$

**Parameter tuning** Set $A_s = e^{\theta s}$ and $B_s = \sqrt{\mu_0 L_0} e^{\theta s}$, with

$$ \theta = \eta' = \frac{a}{\rho} \left( \frac{\mu_0}{L_0} \right)^{1/4} \sqrt{\frac{\mu}{L}}, \quad \gamma = \frac{1}{\rho L}, \quad \gamma' = \frac{1}{\rho} \frac{1}{(\mu_0 L_0)^{1/4} \sqrt{L}}, \quad \eta = \frac{1}{\rho} \frac{(\mu_0 L_0)^{1/4}}{\sqrt{L}}. $$

These parameters imply the cancellations

$$ A_s \eta - B_s \gamma' = 0, \quad (33) $$

$$ \rho B_s \gamma'^2 - \frac{A_s}{\rho L} = 0, \quad (34) $$

$$ \frac{dB_s}{ds} - B_s \eta' = 0, \quad (35) $$

$$ \frac{dA_s}{ds} - A_s \eta a \sqrt{\frac{\mu}{L_0}} = 0, \quad (36) $$

$$ B_s \eta' - A_s \eta a \sqrt{\mu\mu_0} = 0. \quad (37) $$

Therefore,

$$ \langle \nabla \varphi(\bar{x}_s), b(\bar{x}_s) \rangle + \mathbb{E}_{\xi} [\varphi(\bar{x}_s + G(\bar{x}_s, \xi)) - \varphi(\bar{x}_s)] \leq 0, $$

so from (26),

$$ \varphi(\bar{x}_t) \leq \varphi(\bar{x}_0) + M_t. $$

We evaluate at $t = T_k$, take expectation, and use Theorem F.3 and Proposition F.2 to get

$$ \mathbb{E} [e^{\theta T_k} (f(\tilde{x}_k) - f^*)] \leq \varphi(\bar{x}_0). $$

Finally, as $x_0 = z_0$ and $f \in \mathrm{QG}^{\mu_0}$, we have

$$ \varphi(\bar{x}_0) = f(\tilde{x}_0) - f^* + \frac{\sqrt{\mu_0 L_0}}{2} \|\tilde{x}_0 - x^*\|^2 \leq \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) (f(\tilde{x}_0) - f^*), $$

where we used $\tilde{x}_0 = \tilde{z}_0$, and we obtain (57), namely

$$ \mathbb{E} [e^{\beta T_k} (f(\tilde{x}_k) - f^*)] \leq K_0, $$

with $\beta = \theta$ and $K_0 = \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) (f(\tilde{x}_0) - f^*)$. By Lemma F.4, with probability $1 - \frac{1}{c_0} - \exp(-(c_1 - 1 - \log c_1)k)$,

$$ f(\tilde{x}_k) - f^* \leq c_0 \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) (f(\tilde{x}_0) - f^*) \exp(-\theta(1 - c_1)k), $$

which is the claim.

□
E. Trajectory-adapted convergence

In this section, we address a setting in which we assume the aiming condition is verified on average along the trajectory (Assumption 5.1). We start by proving Theorem 5.2, that addresses the dynamical system case. Then, we will state and prove similar results in the discrete case.

E.1. Proof of Theorem 5.2

Proof with Gradient Flow (GF) Let

$$
E_t = e^{a_{avg} \sqrt{\mu \mu_0} t} \left[ f(x_t) - f^* + \frac{\beta}{2} \|x_t - x^*\|^2 \right].
$$

Then

$$
\begin{align*}
\dot{E}_t &= a_{avg}\sqrt{\mu\mu_0} e^{a_{avg}\sqrt{\mu\mu_0}t} \left[ f(x_t) - f^* + \frac{\beta}{2} \|x_t - x^*\|^2 \right] \\
&\quad + e^{a_{avg}\sqrt{\mu\mu_0}t} \left[ \langle \nabla f(x_t), \dot{x}_t \rangle + \beta \langle x_t - x^*, \dot{x}_t \rangle \right] \\
&\stackrel{(i)}{=} a_{avg}\sqrt{\mu\mu_0} e^{a_{avg}\sqrt{\mu\mu_0}t} \left[ f(x_t) - f^* + \frac{\beta}{2} \|x_t - x^*\|^2 \right] \\
&\quad + e^{a_{avg}\sqrt{\mu\mu_0}t} \left[ -\|\nabla f(x_t)\|^2 - \beta \langle x_t - x^*, \nabla f(x_t) \rangle \right] \\
&\le a_{avg}\sqrt{\mu\mu_0} e^{a_{avg}\sqrt{\mu\mu_0}t} \left[ f(x_t) - f^* + \frac{\beta}{2} \|x_t - x^*\|^2 \right] - \beta e^{a_{avg}\sqrt{\mu\mu_0}t} \langle x_t - x^*, \nabla f(x_t) \rangle,
\end{align*}
$$

where (i) follows from $\dot{x}_t = -\nabla f(x_t)$.

Integrating from 0 to t yields

$$
E_t \le E_0 + \int_0^t a_{avg} \sqrt{\mu\mu_0} e^{a_{avg}\sqrt{\mu\mu_0}s} \left[ f(x_s) - f^* + \frac{\beta}{2} \|x_s - x^*\|^2 \right] ds - \int_0^t \beta e^{a_{avg}\sqrt{\mu\mu_0}s} \langle x_s - x^*, \nabla f(x_s) \rangle ds. \quad (38)
$$

By Assumption 5.1 (with $\theta = a_{avg}\sqrt{\mu\mu_0}$), we have

$$
\int_0^t e^{\theta s} \langle \nabla f(x_s), x_s - x^* \rangle \, ds \geq a_{\text{avg}} \int_0^t e^{\theta s} \| \nabla f(x_s) \| \| x_s - x^* \| \, ds,
$$

hence

$$
\int_0^t \beta e^{\theta s} \langle x_s - x^*, \nabla f(x_s) \rangle \, ds \geq \int_0^t \beta a_{\text{avg}} e^{\theta s} \|x_s - x^*\| \|\nabla f(x_s)\| \, ds.
$$

Plugging into (38) gives

$$
E_t \le E_0 + \int_0^t a_{avg} \sqrt{\mu\mu_0} e^{\theta s} \left[ f(x_s) - f^* + \frac{\beta}{2} \|x_s - x^*\|^2 \right] ds - \int_0^t \beta a_{avg} e^{\theta s} \|x_s - x^*\| \|\nabla f(x_s)\| ds. \quad (39)
$$

Using Lemma C.2, for all $s \ge 0$,

$$
- \|x_s - x^*\| \|\nabla f(x_s)\| \le - \sqrt{\frac{\mu}{L_0}} (f(x_s) - f^*) - \frac{\sqrt{\mu\mu_0}}{2} \|x_s - x^*\|^2.
$$

Multiplying by $\beta a_{avg} e^{\theta s}$ and inserting into (39), we obtain

$$
\begin{align*}
E_t \le E_0 &+ \int_0^t e^{\theta s} \Biggl[ a_{avg} \sqrt{\mu\mu_0} (f(x_s) - f^*) - \beta a_{avg} \sqrt{\frac{\mu}{L_0}} (f(x_s) - f^*) \\
&\phantom{+ \beta a_{avg} \sqrt{\mu\mu_0} (f(x_s) - f^*)} + \frac{\beta}{2} a_{avg} \sqrt{\mu\mu_0} \|x_s - x^*\|^2 - \frac{\beta}{2} a_{avg} \sqrt{\mu\mu_0} \|x_s - x^*\|^2 \Biggr] ds \\
&= E_0 + a_{avg} \int_0^t e^{\theta s} \left( \sqrt{\mu\mu_0} - \beta \sqrt{\frac{\mu}{L_0}} \right) (f(x_s) - f^*) ds.
\end{align*}
$$
Choose $\beta = \sqrt{\mu_0 L_0}$, so that $\sqrt{\mu\mu_0} - \beta\sqrt{\mu/L_0} = 0$. Then $E_t \le E_0$ for all $t \ge 0$. Since $f(x_t) - f^* \le e^{-\theta t} E_t$, we get

$$f(x_t) - f^* \le e^{-\theta t} E_0 = e^{-a_{avg}\sqrt{\mu\mu_0 t}} (f(x_0) - f^* + \frac{\beta}{2} \|x_0 - x^*\|^2).$$

Finally, using $f(x_0) - f^* \ge \frac{\mu_0}{2} \|x_0 - x^*\|^2$ and $\beta = \sqrt{\mu_0 L_0}$,

$$\frac{\beta}{2} \|x_0 - x^*\|^2 \le \sqrt{\frac{L_0}{\mu_0}} (f(x_0) - f^*),$$

hence

$$f(x_t) - f^* \le \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) e^{-a_{avg}\sqrt{\mu\mu_0 t}} (f(x_0) - f^*).$$

**Proof with Nesterov ODE momentum (NMO) Let**

$$E_t = e^{\theta t} (f(x_t) - f^*) + \frac{\beta}{2} e^{\theta t} \|z_t - x^*\|^2.$$

As in the proof of Theorem 4.4 (i), choose $\eta' = \theta$ and $\eta = \beta\gamma'$. Then we get (see (24))

$$\dot{E}_t \le e^{\theta t} (\theta(f(x_t) - f^*) + \eta \langle \nabla f(x_t), x^* - x_t \rangle + \frac{\beta\theta}{2} \|x_t - x^*\|^2). \quad (40)$$

Integrating,

$$\begin{aligned} E_t &\le E_0 + \int_0^t e^{\theta s} (\theta(f(x_s) - f^*) + \frac{\beta\theta}{2} \|x_s - x^*\|^2) ds + \eta \int_0^t e^{\theta s} \langle \nabla f(x_s), x^* - x_s \rangle ds \\ &= E_0 + \int_0^t e^{\theta s} (\theta(f(x_s) - f^*) + \frac{\beta\theta}{2} \|x_s - x^*\|^2) ds - \eta \int_0^t e^{\theta s} \langle \nabla f(x_s), x_s - x^* \rangle ds. \end{aligned} \quad (41)$$

By Assumption 5.1,

$$\int_0^t e^{\theta s} \langle \nabla f(x_s), x_s - x^* \rangle ds \ge a_{avg} \int_0^t e^{\theta s} \| \nabla f(x_s) \| \| x_s - x^* \| ds,$$

hence

$$E_t \le E_0 + \int_0^t e^{\theta s} \left( \theta(f(x_s) - f^*) + \frac{\beta\theta}{2} \|x_s - x^*\|^2 \right) ds - \eta a_{avg} \int_0^t e^{\theta s} \|\nabla f(x_s)\| \|x_s - x^*\| ds. \quad (42)$$

Using Lemma C.2,

$$- \|x_s - x^*\| \|\nabla f(x_s)\| \le - \sqrt{\frac{\mu}{L_0}} (f(x_s) - f^*) - \frac{\sqrt{\mu\mu_0}}{2} \|x_s - x^*\|^2,$$

and inserting into (42), we obtain

$$E_t \le E_0 + \int_0^t e^{\theta s} \left[ \left( \theta - \eta a_{avg} \sqrt{\frac{\mu}{L_0}} \right) (f(x_s) - f^*) + \frac{1}{2} \left( \beta\theta - \eta a_{avg} \sqrt{\mu\mu_0} \right) \|x_s - x^*\|^2 \right] ds. \quad (43)$$

Choose $\beta = \sqrt{\mu_0 L_0}$ and impose the cancellations

$$\theta = \eta a_{avg} \sqrt{\frac{\mu}{L_0}} \quad \text{and} \quad \beta\theta = \eta a_{avg} \sqrt{\mu\mu_0}.$$

These two equalities are equivalent to $\beta = \sqrt{\mu_0 L_0}$ and

$$\theta = a_{avg} \left( \frac{\mu_0}{L_0} \right)^{1/4} \sqrt{\mu}, \quad \eta = (\mu_0 L_0)^{1/4}.$$
With $\eta' = \theta$ and $\eta = \beta\gamma'$, we can take

$$ \gamma' = \frac{\eta}{\beta} = (\mu_0 L_0)^{-1/4}, \quad \eta' = \theta = a_{\text{avg}} \left(\frac{\mu_0}{L_0}\right)^{1/4} \sqrt{\mu}, \quad \gamma \ge 0. $$

Then the integrand in (43) is identically zero and we get $E_t \le E_0$. Since $f(x_t) - f^* \le e^{-\theta t} E_t$, we deduce

$$ f(x_t) - f^* \le e^{-\theta t} E_0 = e^{-\theta t} \left( f(x_0) - f^* + \frac{\beta}{2} \|z_0 - x^*\|^2 \right). $$

As $z_0 = x_0$, then

$$ f(x_t) - f^* \le e^{-\theta t} \left( f(x_0) - f^* + \frac{\sqrt{\mu_0 L_0}}{2} \|x_0 - x^*\|^2 \right). $$

Using $f(x_0) - f^* \ge \frac{\mu_0}{2} \|x_0 - x^*\|^2$, we obtain

$$ f(x_t) - f^* \le \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) e^{-\theta t} (f(x_0) - f^*), \quad \theta = a_{\text{avg}} \left(\frac{\mu_0}{L_0}\right)^{1/4} \sqrt{\mu}. $$

## E.2. Discrete case

We address the discrete case. As in Appendix D, we consider stochastic gradients under Assumption D.1.

**Assumption E.1.** For some $\{A_i\}_{i=1,...,k}$ and $a_{\text{avg}} > 0$, $\{\tilde{y}_k\}_{k \ge 0}$ is such that

$$ \sum_{i=1}^{k} A_i \left[ \langle \nabla f(\tilde{y}_i, \xi_i), \tilde{y}_i - x^* \rangle - a_{\text{avg}} \| \nabla f(\tilde{y}_i, \xi_i) \| \| x^* - \tilde{y}_i \| \right] \ge 0. $$

We consider (NM), a similar and simpler analysis can be carried for (GD).

**Theorem E.2.** Let $f \in PL^\mu \cap LS^L$. Denote $L_0 := \inf\{L' \le L : f \in QG_+^{L'}\}$, $\mu_0 := \sup\{\mu' \ge \mu : f \in QG_-^{\mu'}\}$. Let $\{\tilde{x}_k\}_{k \in \mathbb{N}}$ verify (NM) with the continuized parameterization and with $\nabla f(\tilde{x}_k)$ replaced by $\nabla f(\tilde{x}_k, \xi_k)$ for random variables $\xi_k$ independent of $\tilde{x}_k$, under Assumption D.1, and assume that Assumption E.1 holds with $A_i = e^{\theta T_i}$, where

$$ \theta = \eta' = \frac{a_{\text{avg}}}{\rho} \left(\frac{\mu_0}{L_0}\right)^{1/4} \sqrt{\frac{\mu}{L}}. $$

Let

$$ \gamma = \frac{1}{\rho L}, \quad \gamma' = \frac{1}{\rho(\mu_0 L_0)^{1/4} \sqrt{L}}, \quad \eta = \frac{1}{\rho} \frac{(\mu_0 L_0)^{1/4}}{\sqrt{L}}. $$

Then, with probability $1 - \frac{1}{c_0} - e^{-(c_1-1-\log(c_1))k}$ (for some $c_0 > 1$, $c_1 \in (0,1)$),

$$ f(\tilde{x}_k) - f^* \le c_0 \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) (f(\tilde{x}_0) - f^*) \exp(-\theta(1 - c_1)k). $$

**Proof.** We use the same notations as in the proof of Theorem D.4. Let $\bar{x}_t = (t, x_t, z_t)$ and define

$$ \varphi(t, x, z) = A_t(f(x) - f^*) + \frac{B_t}{2} \|z - x^*\|^2, \quad A_t = e^{\theta t}, \quad B_t = \sqrt{\mu_0 L_0} e^{\theta t}. $$

Applying Proposition F.1, we have

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

where $M_t$ is a martingale with $\mathbb{E}[M_t] = 0$.
From the same algebraic computations as in Theorem 4.4 (ii), we obtain

$$ 
\begin{aligned}
& \langle \nabla \varphi(\bar{x}_s), b(\bar{x}_s) \rangle + \mathbb{E}_{\xi}(\varphi(\bar{x}_s + G(\bar{x}_s, \xi)) - \varphi(\bar{x}_s)) \\
& \leq \frac{1}{2} \left( \frac{dB_s}{ds} - B_s \eta' \right) \|z_s - x^*\|^2 + \frac{B_s \eta'}{2} \|x_s - x^*\|^2 + \frac{dA_s}{ds} (f(x_s) - f^*) \\
& \quad + A_s \eta \langle \nabla f(x_s), x^* - x_s \rangle + (A_s \eta - B_s \gamma') \langle \nabla f(x_s), z_s - x^* \rangle \\
& \quad + \frac{1}{2} \left( \rho B_s \gamma'^2 - \frac{A_s}{\rho L} \right) \|\nabla f(x_s)\|^2.
\end{aligned} 
\quad (45) $$

With the parameter choices of the theorem and $B_s = \sqrt{\mu_0 L_0} A_s$, we have

$$ A_s \eta - B_s \gamma' = 0, \quad \rho B_s \gamma'^2 - \frac{A_s}{\rho L} = 0, \quad \frac{dB_s}{ds} - B_s \eta' = 0. $$

Thus (45) reduces to

$$ \langle \nabla \varphi(\bar{x}_s), b(\bar{x}_s) \rangle + \mathbb{E}_{\xi}(\varphi(\bar{x}_s + G(\bar{x}_s, \xi)) - \varphi(\bar{x}_s)) \leq \frac{dA_s}{ds} (f(x_s) - f^*) + \frac{B_s \eta'}{2} \|x_s - x^*\|^2 + A_s \eta \langle \nabla f(x_s), x^* - x_s \rangle. \quad (46) $$

We now control the last term using the jump structure. For any predictable process $h_s$,

$$ \int_0^t h_s dN_s = \int_0^t h_s ds + \int_0^t h_s (dN_s - ds), $$

where $\int_0^t h_s(dN_s - ds)$ is a martingale.

Applying this identity with

$$ h_s = A_s \eta \left[ \langle \nabla f(x_s, \xi_s), x_s - x^* \rangle - a_{avg} \| \nabla f(x_s, \xi_s) \| \| x_s - x^* \| \right], $$

and using Assumption E.1 with $A_i = e^{\theta T_i}$, we obtain for $t = T_k$

$$ \int_0^{T_k} A_s \eta \langle \nabla f(x_s), x^* - x_s \rangle dN_s \leq -\eta a_{avg} \int_0^{T_k} A_s \| \nabla f(x_s) \| \| x_s - x^* \| dN_s. \quad (47) $$

This holds because by definition of the Poisson integrals, we have

$$ \int_0^{T_k} A_s \eta \langle \nabla f(x_s), x^* - x_s \rangle dN_s = \sum_{i=1}^k A_k \eta \langle \nabla f(x_{T_k^{-}}), x^* - x_{T_k^{-}} \rangle = \sum_{i=1}^k A_k \eta \langle \nabla f(\tilde{y}_k), x^* - \tilde{y}_k \rangle, $$

where the last inequality follows from Proposition F.2.

Using Lemma C.2,

$$ - \| \nabla f(x_s) \| \| x_s - x^* \| \leq - \sqrt{\frac{\mu}{L_0}} (f(x_s) - f^*) - \frac{\sqrt{\mu \mu_0}}{2} \| x_s - x^* \|^2, $$

and inserting this inequality into (47), then back into (46), we obtain

$$ \langle \nabla \varphi(\bar{x}_s), b(\bar{x}_s) \rangle + \mathbb{E}_{\xi}(\varphi(\bar{x}_s + G(\bar{x}_s, \xi)) - \varphi(\bar{x}_s)) \leq 0. $$

Plugging this bound into (44) yields

$$ \varphi(\bar{x}_t) \leq \varphi(\bar{x}_0) + M_t, $$

where $M_t$ is a martingale. Evaluating at $t = T_k$, taking expectations, and using Theorem F.3, we get

$$ \mathbb{E} [e^{\theta T_k} (f(\tilde{x}_k) - f^*)] \leq \varphi(\bar{x}_0). $$

Finally,

$$ \varphi(\bar{x}_0) = f(\tilde{x}_0) - f^* + \frac{\sqrt{\mu_0 L_0}}{2} \|\tilde{z}_0 - x^*\|^2 \leq \left(1 + \sqrt{\frac{L_0}{\mu_0}}\right) (f(\tilde{x}_0) - f^*), $$

and Lemma F.4 concludes the proof. □
### E.3. Possible Extensions: Adapt to other Conditions and Exact Rates

We could consider other extensions of the proposed viewpoint. First, we could consider other averaged condition, such as an averaged PL condition:

$$ \int_{0}^{t} e^{\theta t} \|\nabla f(x_s)\|^2 ds \geq 2\mu_{\text{avg}} \int_{0}^{t} (f(x_s) - f^*)ds, $$

for some $\mu_{\text{avg}} > 0$. This inequality is automatically verified if $f \in \text{PL}^{\mu}$, with $\mu_{\text{avg}} \geq \mu$. Interestingly, $(x_t)_{t \geq 0}$ could cross a saddle point $\hat{x}$, such that $f \notin \text{PL}^{\mu}$, while having that this inequality is verified. In particular, (NMO) could cross and escape such saddle point, and then converging to a global minima. This saddle point could be "averaged out".

Alternatively, we also could consider point-wise parameter, as illustrated next.

**Proposition E.3.** Define the point-wise Polyak-Lojasiewicz constant $\mu(x) := 2 \frac{\|\nabla f(x)\|^2}{f(x)-f^*}$. If $(x_t)_{t \geq 0} \sim (\text{GF})$, we have

$$ f(x_t) - f^* = e^{-2 \int_0^t \mu(x_s) ds} (f(x_0) - f^*). $$

We obtain an exact rate for the decrease of $f(x_t) - f^*$. If $f \in \text{PL}^{\mu}$, we have in particular $2 \int_0^t \mu(x_s) ds \geq 2\mu t$. We can carry similar analysis with (NMO), under a point-wise aiming condition.

**Proposition E.4.** Define the point-wise: Polyak-Lojasiewicz constant $\mu(x) := 2 \frac{\|\nabla f(x)\|^2}{f(x)-f^*}$, aiming condition constant $a(x) := \frac{\langle \nabla f(x), x-x^* \rangle}{\|\nabla f(x)\|\|x-x^*\|}$ and quadratic growth constant $\mu_0(x) = 0.5 \cdot \frac{f(x)-f^*}{\|x-x^*\|^2}$. If $(x_t)_{t \geq 0} \sim (\text{NMO})$ with $\eta'_t = a(x_t)\sqrt{\mu(x_t)}$, $\eta_t = \frac{L_0}{\sqrt{\mu_0(x_t)}}$, $\gamma'_t = \frac{1}{\sqrt{\mu_0(x_t)}}$, $\gamma_t \geq 0$, we have

$$ f(x_t) - f^* \leq e^{-\int_0^t a(x_s) \sqrt{\mu(x_s)} ds} L_0 \|x_0 - x^*\|^2, $$

with $L_0 = \sup_{x \in \mathbb{R}^d} \mu_0(x)$.

This rate is however purely conceptual, as it involves exact values of parameters we cannot compute. The averaged conditions such as Assumption 5.1 are more practical, as it is sufficient to use a small enough value of $a_{\text{avg}}$, and not an exact one.

#### E.3.1. PROOF OF PROPOSITION E.3

##### (i) Case of gradient flow (GF). Set

$$ E_t := e^2 \int_0^t \mu(x_s) ds (f(x_t) - f^*). $$

We have

$$ \begin{aligned} \dot{E}_t &= 2\mu(x_t)e^2 \int_0^t \mu(x_s)ds (f(x_t) - f^*) + e^2 \int_0^t \mu(x_s)ds \langle \nabla f(x_t), \dot{x}_t \rangle \\ &\stackrel{\text{(GF)}}{=} 2\mu(x_t)e^2 \int_0^t \mu(x_s)ds (f(x_t) - f^*) - e^2 \int_0^t \mu(x_s)ds \|\nabla f(x_t)\|^2 \end{aligned} \quad (48) $$

Recall $\mu(x) := 2 \frac{\|\nabla f(x)\|^2}{f(x)-f^*}$. Plugging it in (48), we deduce

$$ \dot{E}_t = 2\mu(x_t)e^2 \int_0^t \mu(x_s)ds (f(x_t) - f^*) - 2\mu(x_t)e^2 \int_0^t \mu(x_s)ds (f(x_t) - f^*) = 0. \quad (49) $$

By integrating we deduce

$$ f(x_t) - f^* = e^{-2 \int_0^t \mu(x_s) ds} (f(x_0) - f^*). \quad (50) $$

#### E.3.2. PROOF OF PROPOSITION E.4

Let

$$ E_t = e^{\int_0^t a(x_s) \sqrt{\mu(x_s)} ds} \left( f(x_t) - f^* + \frac{\beta}{2} \|z_t - x^*\|^2 \right). \quad (51) $$

Denote

$$ \Delta_t := e^{\int_0^t a(x_s) \sqrt{\mu(x_s)} ds}, \quad u_t := a(x_t) \sqrt{\mu(x_t)}. $$
We have

$$
\begin{align}
\Delta_t^{-1} \dot{E}_t &= u_t(f(x_t) - f^*) + \frac{u_t \beta}{2} \|z_t - x^*\|^2 + \langle \nabla f(x_t), \dot{x}_t \rangle + \beta \langle z_t - x^*, \dot{z}_t \rangle \nonumber \\
&= u_t(f(x_t) - f^*) + \frac{u_t \beta}{2} \|z_t - x^*\|^2 \nonumber \\
&\quad + \langle \nabla f(x_t), \eta_t(z_t - x_t) - \gamma_t \nabla f(x_t) \rangle \nonumber \\
&\quad + \beta \langle z_t - x^*, \eta'_t(x_t - z_t) - \gamma'_t \nabla f(x_t) \rangle \nonumber \\
&= u_t(f(x_t) - f^*) + \frac{u_t \beta}{2} \|z_t - x^*\|^2 \nonumber \\
&\quad + \eta_t \langle \nabla f(x_t), x^* - x_t \rangle + (\eta_t - \beta \gamma'_t) \langle \nabla f(x_t), z_t - x^* \rangle \nonumber \\
&\quad + \beta \eta'_t \langle z_t - x^*, x_t - z_t \rangle - \gamma_t \|\nabla f(x_t)\|^2. \tag{52}
\end{align}
$$

We choose $\eta'_t = u_t$ to cancel the $\|z_t - x^*\|^2$ term, and $\eta_t = \beta\gamma'_t$ to cancel the mixed scalar product. Then

$$
\Delta_t^{-1} \dot{E}_t = u_t(f(x_t) - f^*) + \beta \gamma'_t \langle \nabla f(x_t), x^* - x_t \rangle + \frac{\beta u_t}{2} \|x_t - x^*\|^2 - \gamma_t \|\nabla f(x_t)\|^2. \quad (53)
$$

By Lemma C.3,

$$
\langle \nabla f(x_t), x^* - x_t \rangle = -a(x_t) \sqrt{\frac{\mu(x_t)}{\mu_0(x_t)}} (f(x_t) - f^*) - a(x_t) \sqrt{\mu(x_t)\mu_0(x_t)} \frac{1}{2} \|x_t - x^*\|^2.
$$

Fixing $\gamma'_t = \frac{1}{\sqrt{\mu_0(x_t)}}$ and ignoring the nonpositive term $-\gamma_t \|\nabla f(x_t)\|^2$, we obtain

$$
\Delta_t^{-1} \dot{E}_t = u_t \left(1 - \frac{\beta}{\mu_0(x_t)}\right) (f(x_t) - f^*). \quad (54)
$$

Choosing $\beta = L_0 = \sup_{x \in \mathbb{R}^d} \mu_0(x)$ ensures $\dot{E}_t \le 0$ for all $t \ge 0$. Therefore $E_t \le E_0$, and

$$
f(x_t) - f^* \le e^{-\int_0^t a(x_s) \sqrt{\mu(x_s)} ds} E_0.
$$

Finally, since $\mu_0(x_0) \le L_0$, we have

$$
f(x_0) - f^* = 2\mu_0(x_0) \|x_0 - x^*\|^2 \le 2L_0 \|x_0 - x^*\|^2,
$$

which yields

$$
f(x_t) - f^* \le e^{-\int_0^t a(x_s) \sqrt{\mu(x_s)} ds} L_0 \|x_0 - x^*\|^2.
$$

F. Continuized Toolbox

The continuized framework (Even et al., 2021) offers an alternative momentum method compared to the more classic ones.
In practice, it results in a stochastic parameterization of (NM). It can lead to interesting results in some non-convex setting,
see (Wang & Wibisono, 2023; Hermant et al., 2025). We refer to (Hermant et al., 2025, Section 3) for an methodological
introduction of this concept, on the class of function PL<sup>μ</sup> ∩ LS<sup>L</sup>. In this section, we will simply state the fundamental
objects and tools. The fundamental object are the continuized Nesterov equations:

$$
\left\{
\begin{array}{l}
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{array}
\right.
\qquad (\text{CNE})
$$

where $dN(t) = \sum_{k \ge 0} \delta_{T_k}(dt)$ is a Poisson point measure with intensity $dt$, with $T_1, T_2, \dots$ random times such that for all $i$, $T_{i+1} - T_i \stackrel{\text{i.i.d}}{\sim} \mathcal{E}(1)$. It mixes a continuous component, the $dt$ factor, with a discrete component that acts at random times, the $dN_t$ factor. $(x_t, z_t)_{t \ge 0}$ cannot be differentiated, but we can still use Lyapunov-approaches through Itô calculus.
**Proposition F.1** (Even et al., 2021), Proposition 2). Let $x_t \in \mathbb{R}^d$ be a solution of

$$dx_t = b(x_t)dt + \int_{\Xi} G(x_t, \xi)dN(t, \xi)$$

and $\varphi: \mathbb{R}^d \to \mathbb{R}$ be a smooth function. Then,

$$\varphi(x_t) = \varphi(x_0) + \int_0^t \langle \nabla \varphi(x_s), b(x_s) \rangle ds + \int_{[0,t]} \mathbb{E}_{\xi} \varphi(x_s + G(x_s, \xi)) - \varphi(x_s) ds + M_t, \quad (55)$$

where $M_t$ is a martingale such that $\mathbb{E}[M_t] = 0, \forall t \ge 0$.

Importantly, the following evaluations $\tilde{y}_k := x_{T_{k+1}^-}$, $\tilde{x}_k := x_{T_k}$ and $\tilde{z}_k := z_{T_k}$ of (CNE) can be written as an algorithmic form.

**Proposition F.2** (Hermant et al., 2025), Proposition 5). Let $(x_t, z_t)_{t \ge 0}$ follow (CNE). Define $\tilde{y}_k := x_{T_{k+1}^-}$, $\tilde{x}_k := x_{T_k}$ and $\tilde{z}_k := z_{T_k}$ as evaluations of this process. Then, $(\tilde{y}_k, \tilde{x}_k, \tilde{z}_k)$ writes as a Nesterov algorithm in the form of (NM) with stochastic parameters

$$\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) \\
\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 (56)$$

In order to transfer a result involving $(x_t, z_t)_{t \ge 0}$ to $(\tilde{x}_k, \tilde{z}_k)_{k \in \mathbb{N}}$, we use need a stopping theorem, such as the following.

**Theorem F.3** (Stopping theorem, (Hermant et al., 2025), Theorem 6). Let $(\varphi_t)_{t \in \mathbb{R}_+}$ be a nonnegative process with cadlag trajectories, such that it verifies

$$\varphi_t \le K_0 + M_t,$$

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

$$\mathbb{E}[\varphi_{\tau}] \le \mathbb{E}[K_0].$$

Finally, because the continuized analysis leads to result in expectation, in the case where we obtain linear convergence rates, concentration inequalities such as Chernov inequality allows to deduce a result on the trajectory, with high probability.

**Lemma F.4** (Hermant et al., 2025), Proposition 14). 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$. If the iterations of (56) verify

$$\mathbb{E}[e^{\beta T_k} (f(\tilde{x}_k) - f^*)] \le K_0, \quad (57)$$

then, with probability $1 - \frac{1}{c_0} - e^{-(c_1-1-\log(c_1))^k}$, for some $c_0 > 1$ and $c_1 \in (0, 1)$ we have

$$f(\tilde{x}_k) - f^* \le c_0 K_0 e^{-\beta(1-c_1)^k}.$$

## G. Link between aiming condition and other conditions

In this section, we investigate the link between $AC^a$ and relaxations of strong convexity. In Lemma C.1, we already proved that for $f \in \text{PL}^\mu \cap \text{AC}^a \cap \text{QG}_+^{L_0}$, and noting $\mu_0 := \sup\{\mu' \ge \mu : f \in \text{QG}_-^\mu\}$, we have

$$f^* \ge f(x) + \frac{1}{a} \sqrt{\frac{L_0}{\mu}} \langle \nabla f(x), x^* - x \rangle + \frac{\sqrt{L_0 \mu_0}}{2} \|x - x^*\|^2.$$

This indicates that the set $\text{PL}^\mu \cap \text{AC}^a \cap \text{QG}_+^{L_0}$ defines a specific parameterization of $\text{SQC}_\tau^\mu$. As mentioned in Section 1.2, (Hermant et al., 2024, Theorem 7) derives a different parameterization. The parameters they obtain are such that the bounds of (NMO) and (NM) reduce to those of (GF) and (GD), see Appendix A.2.

For the converse relation, we define a weaker relaxation of strong convexity than $\text{SQC}_\tau^\mu$, defined by the Restricted Secant Inequality (RSI) (Zhang & Yin, 2013).
**Definition G.1.** For $\nu > 0$, we call RSI$^{\nu}$ the set of functions $f$ that satisfies the Restricted Secant Inequality, namely $\forall x \in \mathbb{R}^d$, $\langle \nabla f(x), x - x^* \rangle \geq \nu \|x - x^*\|^2$.

A function in $SQC_{\tau}^{\mu}$ is also in RSI$_{\tau}^{\frac{2\mu}{2-\gamma}}$, such that the RSI condition is weaker (Hermant et al., 2024).

**Proposition G.2.** Let $f \in RSI^{\nu}$. If $f$ also satisfies

$$ \forall x \in \mathbb{R}^d, \quad \|\nabla f(x)\| \leq L \|x - x^*\|, \qquad (58) $$

then $f \in AC_{\mathcal{L}}^{\nu}$.

*Proof.* We have

$$ \langle \nabla f(x), x - x^* \rangle \geq \nu \|x - x^*\|^2 \geq \frac{\nu}{L} \|x - x^*\| \|\nabla f(x)\|. $$

□

The condition (58) is sometimes named EB$^{+}$, as the upper version of the Error-Bound condition (Guille-Escuret et al., 2021). It can also be interpreted as being Lipschitz with respect to the minimizers. The previous result implies in particular that $SQC_{\tau}^{\mu} \cap LS^{L} \subset AC^{a}$, for some parameters.