# A stochastic use of the Kurdyka-Lojasiewicz property: Investigation of optimization algorithms behaviours in a non-convex differentiable framework

Jean-Baptiste Fest, Audrey Repetti, Emilie Chouzenoux

► To cite this version:

Jean-Baptiste Fest, Audrey Repetti, Emilie Chouzenoux. A stochastic use of the Kurdyka-Lojasiewicz property: Investigation of optimization algorithms behaviours in a non-convex differentiable framework. Foundations of Data Science, In press. hal-04874316v2

HAL Id: hal-04874316

https://inria.hal.science/hal-04874316v2

Submitted on 3 Aug 2025

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 Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

# A STOCHASTIC USE OF THE KURDYKA-ŁOJASIEWICZ PROPERTY: INVESTIGATION OF OPTIMIZATION ALGORITHMS BEHAVIOURS IN A NON-CONVEX DIFFERENTIABLE FRAMEWORK

JEAN-BAPTISTE FEST*1 AUDREY REPETTI*2 AND EMILIE CHOUZENOUX*3

¹CMAP, Ecole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France

²Maxwell Institute for Mathematical Sciences and School of Mathematical and Computer Sciences Heriot-Watt University, Edinburgh, UK

²CVN, CentraleSupélec, Inria, Université Paris-Saclay, Gif-sur-Yvette, France

(Communicated by Handling Editor)

**ABSTRACT.** Asymptotic analysis of generic stochastic algorithms often relies on descent conditions. In a convex setting, some technical shortcuts can be considered to establish asymptotic convergence guarantees of the associated scheme. However, in a non-convex setting, obtaining similar guarantees is usually more complicated, and relies on the use of the Kurdyka-Łojasiewicz (KŁ) property. While this tool has become popular in the field of deterministic optimization, it is much less widespread in the stochastic context and the few works making use of it are essentially based on trajectory-by-trajectory approaches. In this paper, we propose a new framework for using the KŁ property in a non-convex stochastic setting based on conditioning theory. We show that this framework allows for deeper asymptotic investigations on stochastic schemes verifying some generic descent conditions. We further show that our methodology can be used to prove convergence of generic stochastic gradient descent (SGD) schemes, and unifies conditions investigated in multiple articles of the literature.

1. **Introduction.** The objective of this work is to approximate a solution of an un-constrained optimization problem of the form of

$$ \underset{w \in \mathbb{R}^N}{\text{minimize}} \quad F(w), \qquad (1) $$

where $F: \mathbb{R}^N \to \mathbb{R}$ is a continuously differentiable function. Specifically, we will investigate the behaviour of a process $(w_k)_{k \in \mathbb{N}}$ defined on a probabilistic space $(\Omega, \mathcal{F}, \mathbb{P})$ and belonging to the finite dimensional space $\mathbb{R}^N$, that will aim to asymptotically approximate such a solution [34, 54]. Celebrated examples are often based on stochastic gradient descent (SGD) algorithms.

When (1) is solved using a deterministic scheme, a set of recent proofs of convergence results rely on the Kurdyka-Łojasiewicz (KŁ) property, that has the advantage of promoting interesting asymptotic behaviors when $F$ is non-necessarily convex.

<footnote n="2020">2020 Mathematics Subject Classification. Primary: 65K05, 90C26, 90C15; Secondary: 90C53.</footnote>

<footnote>Key words and phrases. Stochastic processes, non-convex optimization, Kurdyka-Łojasiewicz property, stochastic gradient descent.</footnote>

<footnote>The work of J.-B.F. and E.C. was partly supported by the ERC Starting Grant MAJORIS ERC-2019-STG-850925. The work of A.R. was partly supported by the EPSRC grant EP/X028860, the Royal Society of Edinburgh, and a grant from the Simons Foundation in the context of an Isaac Newton Programme.</footnote>

<footnote>*Corresponding author: Jean-Baptiste Fest.</footnote>
In this context, KŁ has been used to prove convergence of proximal point algorithms [4, 3], of simple splitting algorithms such as the forward-backward algorithm and its variants [3, 29, 12, 35, 24, 53, 16, 17], as well as other algorithms based on the majorization-minimization principle [30, 25, 21]. A natural question is to investigate the transfer of such proof techniques from the deterministic setting, to the stochastic setting, for asymptotic analysis including a.s. convergence of stochastic processes. Such an extension is quite challenging, mainly due to the dynamics of the functions involved in KŁ conditions, that cannot be controlled in a stochastic environment.

In this work we will develop a new framework, based on KŁ theory [44, 13], to derive almost sure (a.s.) convergence guarantees of the stochastic process $(w_k)_{k \in \mathbb{N}}$, for the resolution of (1) when $F$ is not convex.

Stochastic approximation theory. Following stochastic approximation theory introduced in [54, 55] and similarly to the stabilisation theory for dynamic systems [59], the asymptotic behaviour of $(w_k)_{k \in \mathbb{N}}$ to approximate the minimum of $F$ can be investigated by introducing an auxiliary function $V: \mathcal{H} \to \mathbb{R}$ acting as a Lyapunov function, with $\mathcal{H}$ being a finite-dimensional Euclidean space. To this aim, we introduce an auxiliary augmented process $(x_k)_{k \in \mathbb{N}}$ defined on $(\Omega, \mathcal{F}, \mathbb{P})$ that will be used to study the behaviour of $V$, including process $(w_k)_{k \in \mathbb{N}}$ and any underlying parameters of the associated recursive scheme (e.g., step-sizes). In particular, similarly to [61], in this work we will focus on functions $V$ such that $(V(x_k))_{k \in \mathbb{N}}$ follows a supermartingale behavior. Such an approach is instrumental to avoid the strong assumption that process $(F(w_k))_{k \in \mathbb{N}}$ verifies a supermartingale condition. In fact, stochastic approximation theory results highlight that $(F(w_k))_{k \in \mathbb{N}}$ usually only verifies almost-supermartingale condition [55]. In many cases, however, it is fairly easy to construct $V$ that holds supermartingale condition and enabling to study the asymptotic behaviour of $(F(w_k))_{k \in \mathbb{N}}$ [55].

In this work, we assume that such a Lyapunov function $V$ exists, and we aim to design a framework, with mild assumptions, that allows obtaining stronger asymptotic convergence results on $(w_k)_{k \in \mathbb{N}}$, including its almost-sure convergence to a solution to problem (1). Such a result is challenging to establish in a non-convex stochastic context, and has mainly been studied so far for particular cases. For instance, [47] proved this result when the set of accumulation points of $(w_k)_{k \in \mathbb{N}}$ is included in a subset that is only made up of isolated points. Without this strong assumption, the most common approach to handle non-convex problems consists in adopting the ODE method [5]. This method uses the fact that the asymptotic behaviour of most stochastic schemes is very similar to the one of some differential equations. Nevertheless the noise conditions considered in these works may be difficult to verify in practice, hence restricting their practical use. Instead, in this work we aim to introduce a framework that allows the use of the KŁ property to investigate almost-sure convergence of $(w_k)_{k \in \mathbb{N}}$ under mild assumptions that are generally assumed to be true in modern stochastic optimization (i.e., supermartingale like properties).

However, as explained earlier, although KŁ conditions have been widely used to investigate convergence of deterministic schemes in a non-convex context, their use in a stochastic framework is not straightforward. In the next paragraphs we better explain the Łojasiewicz and KŁ properties, and give an overview of their use in the stochastic literature.
Non-convex optimization and Łojasiewicz theory. Łojasiewicz condition [48] was
originally introduced to study the behaviour of trajectories of some bounded gradi-
ent flow in a continuous setting, for the class of analytical functions, under the form
of a local curvature relation. The works of Łojasiewicz have then been transferred
later to the discrete deterministic framework. In particular, it is shown in [1] that
the Łojasiewicz condition can be used to establish the convergence of a determinis-
tic iterative approximation scheme starting from a descent condition.

The Łojasiewicz condition being originally designed to study gradient flow trajec-
tories, it naturally shares strong connections with the ODE method. Indeed, com-
bining this fact to works such as [5, 23], Benaim provided in [6] strong conver-
gence guarantees of the SGD algorithm when applied to real analytic non-convex
cost functions, without further assumption on the set of accumulating points of
$(w_k)_{k \in \mathbb{N}}$. Almost at the same time, Tadić published similar results in [58], proving
convergence of SGD iterations under the Łojasiewicz condition for real analytic non-
convex cost functions, using a trajectory-based proof. Although the works of Benaim
and Tadić [5, 6, 58] based on Łojasiewicz condition made a breakthrough to inves-
tigating asymptotic behaviour of stochastic processes within a non-convex context,
the “trajectory-by-trajectory approach” of their analysis restricts their framework
to noise conditions that may be difficult to satisfy in practice. In the recent work
[32], the noise conditions have been relaxed thanks to the use of a combination of
conditioning theory with the use of Łojasiewicz condition in a non-convex setting.
Non-convex optimization and KŁ theory. Kurdyka proposed a generalization of the
Łojasiewicz condition in [44] that holds for differentiable functions definable an
o-minimal structure. Similarly to the Łojasiewicz condition, the use of KŁ condi-
tion for discrete deterministic approximations is fairly recent, and its popularity is
mainly due to the pioneering works [14, 4, 12]. Nevertheless, the use of KŁ prop-
erty in the stochastic framework remains rare and seems to be limited to a few
articles. In [36], the authors used the KŁ condition to show $L^1$ and $L^2$ conver-
gence of some stochastic schemes. Further, [33] proposed a new version of the KŁ
condition, in expectation, to study the a.s. convergence of their specific stochas-
tic proximal-gradient algorithm leveraging a mini-batch structure, in a non-convex
non-differentiable setting. In [50] the authors considered a similar algorithm with
more general noise conditions, but with a more restrictive KŁ formulation and us-
ing a “trajectory-by-trajectory” approach. Finally, the authors of [46] mention that a
stochastic formulation of the KŁ inequality would enable to study the accumulation
points of their process, without however providing any theoretical results.

Hence, to our knowledge, no asymptotic analysis including a.s. convergence of
generic stochastic processes has been developed yet.

Contributions. In this paper, we develop a framework to study the a.s. convergence of a generic stochastic process $(w_k)_{k \in \mathbb{N}}$ to a critical point of a differentiable non-convex function $F$, under the KŁ condition. Starting from an augmented process $(V(x_k))_{k \in \mathbb{N}}$ following a supermartingale behaviour, we make use of the KŁ condition (instead of typical convexity assumption) to obtain strong asymptotic results. Unlike the ODE method or the “trajectory-by-trajectory” approach, our strategy is reminiscent of the deterministic proof methodology typically developed in [12], that we adapt to a stochastic framework based on conditioning theory. We further show that our conditions enable the convergence of a wide class of state-of-the-art SGD algorithms [7, 9, 10, 19, 26, 38, 39, 41, 56, 60], summarized in Table 1.
Article outline. The rest of the paper is organized as follows. Section 2 presents the basic assumptions and foundational results needed throughout the article. Section 3 can be considered as the cornerstone of our theoretical analysis. In this section, we introduce a framework to enable the use of the KŁ property (for non-convex functions) in a stochastic setting. We then leverage this framework in Section 4, to present our main asymptotical result, consisting in a summability condition involving a generic (differentiable, non-convex) Lyapunov function V. In Sections 5 and 6 we apply these results to deduce convergence guarantees of the SGD scheme, under generic assumptions. Finally, we give our conclusion in Section 7 and discuss the possible extension of the current work to the non-differentiable case.

Notation. ($\mathcal{H}$, $\langle \cdot | \cdot \rangle_{\mathcal{H}}$) correspond to the (finite-dimensional) Euclidean space under study. $\| \cdot \|_{\mathcal{H}}$ denotes the canonical norm associated with $\mathcal{H}$. For any subset $E \subset \mathcal{H}$, the distance function to this set is denoted by $\text{dist}_{\mathcal{H}}(\cdot, E) = \inf_{x \in \mathcal{H}} \| \cdot - x \|_{\mathcal{H}}$. Bold letters as $x$ are used for deterministic vectors, while straight bold letters as $\mathbf{x}$ are used for stochastic vectors. Similarly, $x$ is used for denoting a deterministic scalar variable, while straight $\mathbf{x}$ denotes a stochastic scalar variable. For a given function $F: \mathcal{H} \to \mathbb{R}$, the variable $F(\mathbf{x})$ denotes the stochastic value of function $F$ evaluated at the stochastic variable $\mathbf{x}$. For a given $E \subset \mathcal{H}$ we denote $|E|$ the cardinal of $E$, and $F(E) := \{F(\mathbf{x}) \mid \mathbf{x} \in \mathcal{H}\}$ is the image under $F$ of $E$. Considering $U$ an open-set of $\mathcal{H}$, if $F$ is differentiable at $\mathbf{x} \in U$, $\nabla F(\mathbf{x})$ denotes the gradient of $F$ at $\mathbf{x}$. If $F$ is differentiable over $\mathcal{H}$, $\text{zer } \nabla F$ corresponds to the set of zeros of $\nabla F$, i.e., the set of critical/stationary points of $F$.

Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space. We say that a condition holds *almost surely* (a.s.) if it holds on a probability-one event of $\mathcal{F}$. We denote by $\mathbb{E}[\cdot]$ the expectation operator, and $\mathbb{E}[\cdot|\mathcal{G}]$ the conditional expectation operator with respect to a generic sub sigma-algebra $\mathcal{G} \subset \mathcal{F}$. Finally, a process $(\mathbf{u}_k)_{k \in \mathbb{N}}$ defined on $(\Omega, \mathcal{F}, \mathbb{P})$ whose values belong to a Banach space $(B, \|\cdot\|_{\mathcal{B}})$ is said to be integrable (resp square-integrable) if $\mathbb{E}[\|\mathbf{u}_k\|_{\mathcal{B}}] < +\infty$ (resp. $\mathbb{E}[\|\mathbf{u}_k\|_{\mathcal{B}}^2] < +\infty$), for any $k \in \mathbb{N}$.

**2. General assumptions and preliminary results.** Let $(\mathbf{x}_k)_{k \in \mathbb{N}}$ be a process belonging to $(\Omega, \mathcal{F}, \mathbb{P})$, and $\chi_\infty$ be its set of accumulation (or cluster) points<fnref n="1" />. We introduce the assumptions and the framework under which we will study the behaviour of $(\mathbf{x}_k)_{k \in \mathbb{N}}$, focusing on a type-Lyapunov function $V: \mathcal{H} \to \mathbb{R}$.

**2.1. Assumptions.** The following generic assumptions will guide us throughout the remainder of this work.

**Assumption 2.1.** $V$ is coercive and continuously differentiable.

**Assumption 2.2.** 1. The sequence $(V(\mathbf{x}_k))_{k \in \mathbb{N}}$ converges a.s. to a random variable $V_\infty$, such that $V_\infty < +\infty$ a.s.

2. There exists a deterministic non-empty subset $\Gamma$ of $\mathcal{H}$ such that $|V(\Gamma)| < +\infty$ a.s. and $\Gamma \cap \chi_\infty \neq \emptyset$.

A few remarks can be made on the generality of these assumptions:

**Remark 2.3.** 1. Assumption 2.1 ensures the existence of a minimizer for $V$ [8].

2. Assumption 2.2 gives information on the behaviour of $(\mathbf{x}_k)_{k \in \mathbb{N}}$, and is thus similar to the general field of stochastic approximation [34].

<footnote n="1">¹$\chi_\infty$ is a random set from $\Omega$ to $2^\mathcal{H}$, the set of subsets of $\mathcal{H}$.</footnote>
3. Assumption 2.21 can usually be deduced from an approximation scheme verifying a descent condition of the form of an almost-supermatingale inequality [55].

4. Assumption 2.22 will be necessary in the stochastic framework considered in this work, in particular due to the fact that $\chi_\infty$ is a random set. This assumption can be interpreted as the need for almost all trajectories $(\chi_\infty(\omega))_{\omega\in\Omega}$ to share a common asymptotic characteristic, represented by their common intersection with a finite set $\Gamma$. This set will be used as a substitute to the "trajectory-by-trajectory" approach adopted in works such as [5, 6, 58], in order to deduce more general convergence guarantees. Specifically, $\Gamma$ will be used to construct uniformization properties similar to the deterministic work [12], that will allow us to work independently from $\omega$-variable. It is worth noticing that Assumption 2.22 is not too constraining, and such a $\Gamma$ exists for a wide class of problems.

The practicality of these conditions will be studied in the context of the SGD scheme, in Sections 5 and 6.

**2.2. Preliminary results.** The next two results will guide us throughout the rest of our analysis. The first one, Proposition 2.4, will provide us with some indications on the structure of subset $\Gamma$ verifying Assumption 2.22 in a generic context. The second result, Proposition 2.5, gives some properties on process $(x_k)_{k\in\mathbb{N}}$.

**Proposition 2.4.** Let $f: \mathcal{H} \to \mathbb{R}$ be a continuous coercive function and $C$ be a non-empty subset of $\mathcal{H}$ such that $|f(C)| < +\infty$. The closure of $C$, denoted $\bar{C}$, can be written as a finite union of non-empty compact sets, such that $f$ is constant on each of them.

*Proof.* We first show that $C$ is bounded. If not, there would exist a sequence $(v_k)_{k\in\mathbb{N}}$ of vectors of $C$ such that $\|v_k\|_{\mathcal{H}} \xrightarrow{k\to+\infty} +\infty$, which, by coercivity, conducts to $f(v_k) \xrightarrow{k\to+\infty} +\infty$ and finally contradicts the finiteness of $f(C)$.

Since $|f(C)| < +\infty$, we can denote $I = |f(C)|$ and $f(C) = \{f_1, \dots, f_I\}$ ($f_1 \neq f_2 \dots \neq f_I$). As $C$ is bounded, it follows that $\bar{C}$ is also bounded. Moreover, since $f(C)$ is finite and $f$ continuous, we also have $f(\bar{C}) = f(C)$. So $\bar{C} \subset f^{-1}(f(C)) = \bigcup_{i=1}^I f^{-1}(\{f_i\})$, and we can write $\bar{C} = \bigcup_{i=1}^I C_i$ where, for all $i \in \{1, \dots, I\}$, $C_i = f^{-1}(\{f_i\}) \cap \bar{C}$.

Let us now fix $i \in \{1, \dots, I\}$. On the one hand, $C_i$ is closed has an intersection of two closed sets. On the other hand, since $\bar{C}$ is bounded, so is $C_i$. We can hence deduce that $C_i$ is compact (since $\mathcal{H}$ is of finite dimension). Moreover, due to $f(\bar{C}) = f(C)(= \{f_1, \dots, f_I\})$, there exists $v \in \bar{C}$ such that $f(v) = f_i$ and so $C_i$ is not empty. Finally, the fact that $C_i \subset f^{-1}(\{f_i\})$ ensures that $f$ is constant on $C_i$ (with $f(C_i) = f_i$). $\square$

The next proposition provides technical topological results on $\chi_\infty$, the set of cluster points of $(x_k)_{k\in\mathbb{N}}$, and on $V_\infty$, the limit of $(V(x_k))_{k\in\mathbb{N}}$. The proof of this result is reminiscent from classical arguments often encountered in the deterministic non-convex setting as in [4, 12], that we generalize here to a stochastic framework.

**Proposition 2.5.** Under Assumptions 2.1 and 2.2, we have

1. $(x_k)_{k\in\mathbb{N}}$ is a.s. bounded.

2. $\chi_\infty$ is a.s. non empty and compact.
3. $(\text{dist}(\mathbf{x}_k, \chi_\infty))_{k \in \mathbb{N}}$ converges a.s. to 0.

4. $V_\infty(\omega) \in V(\Gamma)$ a.s..

**Proof.** According to Assumption 2.2, there exists a set $\Lambda \subset \Omega$ of probability one where, for all $\omega \in \Lambda$,

$$ \lim_{k \to +\infty} V(\mathbf{x}_k(\omega)) = V_\infty(\omega) < +\infty, \quad (2a) $$

$$ \Gamma \cap \chi_\infty(\omega) \neq \emptyset. \quad (2b) $$

Inequality (2a) implies that $(V(\mathbf{x}_k(\omega)))_{k \in \mathbb{N}}$ is a bounded sequence. According to Assumption 2.1, $V$ being coercive, $(\mathbf{x}_k(\omega))_{k \in \mathbb{N}}$ is also bounded. It follows that the set of cluster points $\chi_\infty(\omega)$ is non empty, bounded and closed in $\mathcal{H}$, hence compact. This proves 1 and 2.

We now show that 3 holds. By contradiction, if 3 does not hold, then, for every $\omega \in \Lambda$, there exist $\varepsilon > 0$ and a subsequence $(\mathbf{x}_{\phi(k)}(\omega))_{k \in \mathbb{N}}$ such that

$$ (\forall k \in \mathbb{N}) \quad \text{dist}(\mathbf{x}_{\phi(k)}(\omega), \chi_{\infty}(\omega)) > \varepsilon. \quad (3) $$

Since $(\mathbf{x}_k(\omega))_{k \in \mathbb{N}}$ is bounded, $(\mathbf{x}_{\phi(k)}(\omega))_{k \in \mathbb{N}}$ is also bounded. So the set of cluster points of $(\mathbf{x}_{\phi(k)}(\omega))_{k \in \mathbb{N}}$ is non-empty and included in $\chi_\infty(\omega)$. Thus, there exists another subsequence $(\mathbf{x}_{(\phi \circ \tilde{\phi})(k)}(\omega))_{k \in \mathbb{N}}$ and a point $\mathbf{x}_\infty(\omega) \in \chi_\infty(\omega)$ such that
$$ \|\mathbf{x}_{(\phi \circ \tilde{\phi})(k)}(\omega) - \mathbf{x}_\infty(\omega)\| \xrightarrow{k \to +\infty} 0. \text{ Hence, } \text{dist} \left( \mathbf{x}_{(\phi \circ \tilde{\phi})(k)}(\omega), \chi_\infty(\omega) \right) \xrightarrow{k \to +\infty} 0, \text{ which contradicts (3) and thus makes 3 true.} $$

We finally prove 4. For every $\omega \in \Lambda$, there exist $\mathbf{x}_\infty(\omega) \in \Gamma$ and a subsequence $(\mathbf{x}_{\psi(k)}(\omega))_{k \in \mathbb{N}}$ such that $\mathbf{x}_{\psi(k)}(\omega) \xrightarrow{k \to +\infty} \mathbf{x}_\infty(\omega)$, and $V(\mathbf{x}_{\psi(k)}(\omega)) \xrightarrow{k \to +\infty} V_\infty(\omega)$. In addition, since $V$ is continuous, we deduce that $V(\mathbf{x}_{\psi(k)}(\omega)) \xrightarrow{k \to +\infty} V(\mathbf{x}_\infty(\omega))$. Hence $V_\infty(\omega) = V(\mathbf{x}_\infty(\omega)) \in V(\Gamma)$ which concludes the proof. $\square$

**3. KŁ theory as a baseline of improvement.** In this section we present cornerstone results that will be used in the remainder of the paper to conduct the theoretical analysis of stochastic schemes. Specifically, we propose a new use of the KŁ property that does not explicitly depend on $\omega$ variable. This will allow us to derive new asymptotic results leveraging mathematical tools different from the standard ODE method and “trajectory-by-trajectory” strategy used in [5, 32, 58].

To this aim, we first give some notation in Section 3.1 and recall the KŁ framework introduced in [12] in Section 3.2. We then provide an extended version of this framework in Section 3.3, and we finally introduce in Section 3.4 the stochastic framework that will enable us to us the KŁ property to study a.s. convergence of stochastic differentiable schemes under mild assumptions.

**3.1. A set of concave desingularization functions.** In this section we introduce a specific class of functions that will be necessary to reframe the KŁ property into a stochastic framework.

**Definition 3.1.** [14] Let $\zeta \in (0, +\infty]$. We denote $\Phi_\zeta$ the set of concave desingularization functions defined as the set of concave functions $\varphi: [0, \zeta) \to \mathbb{R}_+$ such that $\varphi(0) = 0$, $\varphi$ is continuous in $0$, $\varphi \in C^1((0, \zeta))$, and, for every $s \in (0, \zeta)$, $\varphi'(s) > 0$.
In Definition 3.1, we can have $\zeta = +\infty$. The link between $\Phi_\zeta$ for $\zeta \in [0, +\infty)$ and $\Phi_{+\infty}$ is described by the following proposition which we will use much later for essentially technical purposes in section 4. However, we have preferred to present the latter in this subsection for the sake of consistency.

**Proposition 3.2.** Let $\zeta \in (0, +\infty)$. Any function $\varphi$ of $\Phi_\zeta$ admits a bounded extension $\tilde{\varphi}$ belonging to $\Phi_{+\infty}$.

*Proof.* Let $\varphi \in \Phi_\zeta$. Since $\varphi'$ is positive, it follows that $\varphi$ is an increasing function. Then $l_1 = \lim_{s \to \zeta^{-}} \varphi(s)$ exists and lies in $[0, +\infty]$. Moreover the concavity and differentiability of $\varphi$ with $\varphi(0) = 0$ ensure that, for every $s \in (0, \zeta)$, $\varphi(s) \le s\varphi'(0)$. Passing to the limit thus gives $l_1 \le \zeta\varphi'(0)$ and then $l_1 < +\infty$.

Moreover, since $\varphi'$ is decreasing on $(0, \zeta)$ (due to the concavity of $\varphi$) and positive, we conclude that $l_2 = \lim_{s \to \zeta^{-}} \varphi'(s)$ exists and lies in $[0, +\infty)$.

Finally, it remains easy to verify that function $\tilde{\varphi}: [0, +\infty) \to \mathbb{R}_+$ defined as

$$ (\forall s \ge 0) \quad \tilde{\varphi}(s) = \begin{cases} \varphi(s) & \text{if } s \in [0, \zeta), \\ l_1 + l_2 \zeta \left(1 - \frac{\zeta}{s}\right) & \text{otherwise.} \end{cases} \quad (4) $$

$\tilde{\varphi}$ belongs to $\Phi_{+\infty}$ and is bounded (see figure 1 below for an illustrative example). □

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

<figure><img src="image_4.png" /><figcaption>FIGURE 1. Illustration of the proof of Proposition 4. $\tilde{\varphi}$ (green curve) is the $C^1$ bounded extension over $(0, +\infty)$ of $s \in [0, \zeta) \mapsto \varphi(s) = \sqrt{s}$ (blue curve), as defined in (4).</figcaption></figure>

In optimization, the most popular desingularization functions are those of the form of $\varphi: s \mapsto cs^{1-\theta}$ where $c > 0$ and $\theta \in (0, 1)$ is referred to as the Lojasiewicz exponent [11]. For such functions, the parameter $\theta$ provides a theoretical understanding of their analytical properties. Historically, desingularization functions have shown to be useful metrics for certifying geometric finiteness of flows derived from the gradient dynamic. More recently, such an interpretation got interest from the optimization community to study behaviour of algorithms in a non-convex context [2].
**3.2. Limitation of the usual KŁ framework.** The KŁ property has been developed for both differentiable [44] and non-differentiable [15, 4] functions, to be used to study gradient descent and proximal-based algorithms, respectively, in a deterministic context (see e.g., [12, 29]). In this section, we focus on the differentiable KŁ framework, generalized to be used for stochastic schemes. Note that this focus is made mainly for the sake of simplicity, but a similar study could be done for the non-smooth framework by replacing the gradient by the limiting subdifferential [4]. Section 5 will be dedicated to examples where the proposed theoretical differentiable framework can be used.

**Definition 3.3.** [KŁ Property] A differentiable function $f: \mathcal{H} \to \mathbb{R}$ satisfies the Kurdyka-Lojasiewicz (KŁ) property at $\tilde{x} \in \mathcal{H}$, if there exist a neighbourhood $\mathcal{V}$ of $\tilde{x}$, $\zeta > 0$ and $\varphi \in \Phi_\zeta$ such that

$$ \|\nabla f(x)\|_{\mathcal{H}} \varphi'(f(x) - f(\tilde{x})) \geq 1, $$

for every $x \in \mathcal{V}$ satisfying $0 < f(x) - f(\tilde{x}) < \zeta$. Furthermore, $f$ is said to satisfy the KŁ property over $E \subset \mathcal{H}$ if the latter is verified at every point of $E$.

The KŁ property given in Definition 3.3 is defined locally in the sense that parameter $\zeta$ and function $\varphi$ depend on the point we are located. As a consequence, this naturally tends to favour trajectory-by-trajectory strategies as investigated, e.g., in [50]. Instead, we aim to adopt a more global approach, as proposed in [12, Lemma 6], leading to the “uniformized KŁ property”.

**Theorem 3.4.** [Uniformized KŁ property] Let $C$ be a compact subset of $\mathcal{H}$ and $f: \mathcal{H} \to \mathbb{R}$ be a differentiable function constant on $C$, satisfying the KŁ property over $C$. Then, there exist $(\varepsilon, \zeta) \in (0, +\infty)^2$ and $\varphi \in \Phi_\zeta$ such that

$$ \|\nabla f(x)\|_{\mathcal{H}} \varphi'(f(x) - f(\bar{x})) \geq 1, $$

for all $\bar{x} \in C$ and $x \in \mathcal{H}$ verifying $\mathrm{dist}_{\mathcal{H}}(x, C) < \varepsilon$ and $0 < f(x) - f(\bar{x}) < \zeta$.

We can notice that the sets $C$ in Theorem 3.4 and $\Gamma$ in Assumption 2.2 are both partially characterized by their image through $f$ and $V$, respectively. This similarity suggests that Theorem 3.4 can be applied to function $V$, assuming that it satisfies the KŁ property on $C = \Gamma$. However, Theorem 3.4 might be over restrictive as it would require that $V(\Gamma)$ is reduced to a singleton. Since $\Gamma$ links all trajectories $(\chi_\infty(\omega))_{\omega \in \Omega}$, the singleton assumption would require that the image sets $(V(\chi_\infty(\omega)))_{\omega \in \Omega}$ are themselves all reduced to a common singleton (i.e. independent from $\omega$-variable), that is not amenable to working in a non-convex context. Hence, the uniformized KŁ property given in Theorem 3.4 can be applied to each $\chi_\infty(\omega)$, for $\omega \in \Omega$, but then the associated parameters $\zeta$ and $\varepsilon$, as well as the desingularizing function $\varphi$ would all also depend on $\omega$. Such an approach would again require working using a trajectory-by-trajectory strategy.

As emphasized in the Introduction, in this work we aim to move away from such a strategy and develop a simplified framework to study a.s. convergence of stochastic processes. Specifically, in the remainder of this section, we build a new version of Theorem 3.4 such that (i) the image of $C$ by $f$ shall not be constant anymore, and (ii) $\zeta, \varepsilon, \varphi$ shall remain deterministic (i.e., independent from $\omega$). The $\omega$-dependency issue of these three last parameters has already been considered in [33]. In their work, the authors assume a mini-batch structure of the gradient-noise and give a version in expectation of Theorem 3.4. In contrast, we aim here to provide a version of Theorem 3.4 that is independent from the considered stochastic scheme.
More generally, both the KŁ and uniformized KŁ properties provide curvature control results, more or less local, given some metric induced by a desingularization function $\varphi$. Unfortunately, such a function $\varphi$ is usually unknown in practice, and the KŁ properties do not give construction rules for obtaining such a function. In fact, to the best of our knowledge, making $\varphi$ explicit is still a challenging problem which has mainly been studied for desingularization functions with Lojasiewicz exponent (see Section 3.1) [45, 63].

**3.3. Proposed extension of the uniformized KŁ theorem.** In this section, we will give our extended version of Theorem 3.4 to the case where the set $C$ can be taken as a finite union of compact sets on which $f$ is constant. This result can be seen as a combination of the uniform KŁ property and [15, Corollary 11], for a more generic set $C$. Such an extension will be necessary to provide a framework where the KŁ property can be used independently from the considered stochastic scheme.

**Theorem 3.5.** [Extended uniformized KŁ property] Let $C = \bigcup_{i=1}^I C_i$ be a union of $I \in \mathbb{N}^*$ non-empty disjoint and compact subsets $(C_i)_{1 \le i \le I}$ of $\mathcal{H}$, and $f: \mathcal{H} \to \mathbb{R}$ be a differentiable function satisfying the KŁ property on $C$. We also suppose that $f$ is constant on every $C_i$, for $i \in \{1, \dots, I\}$, with respective values $f_{C_1}, \dots, f_{C_I}$. Then, there exist $(\varepsilon, \zeta) \in (0, +\infty)^2$ and $\varphi \in \Phi_\zeta$ such that for every $i \in \{1, \dots, I\}$, and for every $x \in \mathcal{H}$ verifying $\text{dist}_{\mathcal{H}}(x, C) < \varepsilon$ and $0 < f(x) - f_{C_i} < \zeta$, we have

$$ \|\nabla f(x)\|_{\varphi'(f(x) - f_{C_i})} \ge 1. \qquad (5) $$

*Proof.* Without loss of generality we consider that $f_{C_1} \ne \dots \ne f_{C_I}$.

We start by applying the uniformized KŁ property 3.4 to $C_1, \dots, C_I$. For every $i \in \{1, \dots, I\}$, there exist $(\varepsilon_i, \zeta_i) \in (0, +\infty)^2$ and $\varphi_i \in \Phi_{\zeta_i}$ such that for every $x \in \mathcal{H}$ verifying $\text{dist}_{\mathcal{H}}(x, C_i) < \varepsilon_i$ and $0 < f(x) - f_{C_i} < \zeta_i$ we have

$$ \|\nabla f(x)\|_{\varphi'_i(f(x) - f_{C_i})} \ge 1. \qquad (6) $$

Let $\tilde{\zeta} = v \min_{j \ne i} |f_{C_i} - f_{C_j}|$ with $v \in (0, 1/2)$. We have $\tilde{\zeta} > 0$. In addition, using the continuity of $f$, for every $i \in \{1, \dots, I\}$, there exists $\tilde{\varepsilon}_i \in (0, \varepsilon_i)$ such that, for every $x$ satisfying $\text{dist}_{\mathcal{H}}(x, C_i) < \tilde{\varepsilon}_i$, we have

$$ |f(x) - f_{C_i}| < \tilde{\zeta}. \qquad (7) $$

Let $\delta \in (0, 1)$ and $\varepsilon = \delta \min_{1 \le i \le I} \tilde{\varepsilon}_i$. Then

$$ \{x \in \mathcal{H} \mid \text{dist}_{\mathcal{H}}(x, C) < \varepsilon\} \subset \bigcup_{i=1}^{I} \{x \in \mathcal{H} \mid \text{dist}_{\mathcal{H}}(x, C_i) < \tilde{\varepsilon}_i\}. \qquad (8) $$

We now show that (5) is satisfied for $\varepsilon$ as defined above, $\zeta = \min(\zeta_1, \dots, \zeta_I, \tilde{\zeta})$ and $\varphi = \sum_{i=1}^I \varphi_i \in \Phi_\zeta$. Let $x \in \mathcal{H}$ and $i \in \{1, \dots, I\}$ be such that $\text{dist}_{\mathcal{H}}(x, C) < \varepsilon$ and $0 < f(x) - f_{C_i} < \zeta$. For every $j \in \{1, \dots, I\} \setminus \{i\}$, since $\zeta \le \tilde{\zeta}$, using the definition of $\tilde{\zeta}$, we have $0 < |f(x) - f_{C_i}| \le v|f_{C_i} - f_{C_j}|$. Insofar $v \in (0, 1/2)$, we obtain

$$ \begin{aligned} |f(x) - f_{C_j}| &= |(f(x) - f_{C_i}) + (f_{C_i} - f_{C_j})| \\ &\ge |f_{C_i} - f_{C_j}| - |f(x) - f_{C_i}| \\ &= |f_{C_i} - f_{C_j}| - |f(x) - f_{C_i}| \\ &\ge (1 - v)|f_{C_i} - f_{C_j}| \end{aligned} $$
$$ 
\begin{aligned}
&> v|f_{C_i} - f_{C_j}| \\
&\geq \tilde{\zeta}. \qquad (9)
\end{aligned}
$$

Then $\mathrm{dist}_{\mathcal{H}}(x, C_j) \geq \tilde{\varepsilon}_j$, otherwise this contradicts the continuity property of $f$ in (7). So, as $\mathrm{dist}_{\mathcal{H}}(x, C) < \varepsilon$, and due to (8), this necessarily implies that $\mathrm{dist}_{\mathcal{H}}(x, C_i) < \tilde{\varepsilon}_i$ and thus $\mathrm{dist}_{\mathcal{H}}(x, C_i) < \varepsilon_i$ (since $\tilde{\varepsilon}_i \leq \varepsilon_i$). In addition, since $\zeta \leq \zeta_i$, we have $0 < f(x) - f_{C_i} < \zeta_i$, and we can apply once more the uniformized KŁ property at $C_i$ (i.e., (6) is verified). Finally the positivity of $\varphi'_1, \dots, \varphi'_I$ ensure the desired relation as follows

$$ 
\begin{aligned}
\|\nabla f(x)\|\varphi'(f(x) - f_{C_i}) &= \|\nabla f(x)\| \sum_{j=1}^{I} \varphi'_{j}(f(x) - f_{C_i}) \\
&\geq \|\nabla f(x)\|\varphi'_{i}(f(x) - f_{C_i}) \geq 1.
\end{aligned}
$$

This completes the proof.

□

**3.4. A KŁ framework for stochastic schemes.** The objective of this section is to introduce a new framework derived from our extended uniformized KŁ property (Theorem 3.5), that can be used in a stochastic setting, independently from the considered stochastic scheme (in particular removing the $\omega$-dependency that appears if using directly Theorem 3.4). To this aim we need to work under the following assumption.

**Assumption 3.6.**

1. The function $V$ defined in Assumption 2.1 satisfies the KŁ property (on $\mathcal{H}$).

2. There exists a positive integer $I < +\infty$ such that the set $\Gamma$ defined in Assumption 2.22 satisfies $\Gamma = \bigcup_{i=1}^{I} C_i$, where, for every $i \in \{1, \dots, I\}$, $C_i$ is a compact set on which $V$ is constant on.

Note that assuming that $V$ satisfies the KŁ property on $\mathcal{H}$ (i.e., Assumption 3.61) is common in non-convex optimization. As emphasized, e.g., in [13], the KŁ inequality is satisfied for a wide class of functions, and in particular by real analytic, semi-algebraic<fnref n="2" /> and log-exp functions.

**Proposition 3.7.** Assume that Assumptions 2.1, 2.2 and 3.6 hold and assume that the event

$$ \Pi_V := \liminf_{k \to +\infty} \{\omega \in \Omega \mid V(\mathbf{x}_k(\omega)) > V_\infty(\omega)\}. \qquad (10) $$

has probability one, i.e. $\mathbb{P}(\Pi_V) = 1$. Then there exist a bounded function $\varphi \in \Phi_{+\infty}$ and an a.s. finite positive discrete random variable K such that

$$ (\forall k > K) \quad \|\nabla V(\mathbf{x}_k)\|\varphi'(V(\mathbf{x}_k) - V_\infty) \geq 1 \text{ a.s..} \qquad (11) $$

**Proof.** The cornerstone of the proof relies in the application of Theorem 3.5 on set

$$ C := \bigcup_{\omega \in \Theta \cap \Pi_V} \chi_\infty(\omega), \qquad (12) $$

where

$$ \Theta = \{V(\mathbf{x}_k) \underset{k \to +\infty}{\to} V_\infty\} \cap \{V_\infty \in V(\Gamma)\} \cap \{\mathrm{dist}_{\mathcal{H}}(\mathbf{x}_k, \chi_\infty) \underset{k \to +\infty}{\to} 0\}. \qquad (13) $$

<footnote n="2">²A function is semi-algebraic if its graph is a finite union of sets defined by a finite number of polynomial inequalities.</footnote>
Here, the role of C is to bring together the accumulation points of all feasible trajectories of process $(x_k)_{k \in \mathbb{N}}$. This will allow us to build a desingularization function which is uniform in $\omega$-variable.

First, by definition of C (12) and continuity of V, we have

$$V(C) = V\left(\bigcup_{\omega \in \Theta \cap \Pi_V} \chi_{\infty}(\omega)\right) = \bigcup_{\omega \in \Theta \cap \Pi_V} V(\chi_{\infty}(\omega)).$$

Furthermore, since V is continuous, by definition of $V_{\infty}$ and $\chi_{\infty}$ we have $V(\chi_{\infty}(\omega)) = \{V_{\infty}(\omega)\}$, and hence

$$V(C) = \bigcup_{\omega \in \Theta \cap \Pi_V} \{V_{\infty}(\omega)\} \subset \bigcup_{\omega \in \Theta \cap \Pi_V} V(\Gamma) = V(\Gamma), \quad (14)$$

where the inclusion is obtained by (13) and the last equality is due to the fact that $V(\Gamma)$ is constant. Since $|V(\Gamma)| < +\infty$ (Assumption 2.21), it follows from (14) that $|V(C)| < +\infty$. Then Proposition 2.4 ensures that $\bar{C}$ can be written as a finite union of non-empty compacts on which V is constant on.

Since V satisfies the KŁ property, we can apply Theorem 3.5 considering $f = V$ and $C = \bar{C}$. Let $I = |V(\bar{C})|$ and $V(\bar{C}) = \{V_1, \dots, V_I\}$ with $V_1 \neq V_2 \cdots \neq V_I$. Then, there exist $\varepsilon_C > 0$, $\zeta_C > 0$ and $\varphi_C \in \Phi_{\zeta_C}$, such that, for every $x \in \mathcal{H}$ and $i \in I$ satisfying $\mathrm{dist}_{\mathcal{H}}(x, \bar{C}) < \varepsilon_C$ and $0 < V(x) - V_i < \zeta_C$,

$$\|\nabla V(x)\|_{\mathcal{H}} \varphi'_{C}(V(x) - V_i) \geq 1. \quad (15)$$

According to Proposition 3.2, $\varphi_C$ has a bounded extension $\tilde{\varphi}_C$ belonging to $\Phi_{+\infty}$. Then, $\tilde{\varphi}_C$ also satisfies, for any $x \in \mathcal{H}$ and $i \in I$ such that $\mathrm{dist}_{\mathcal{H}}(x, \bar{C}) < \varepsilon_C$ and $0 < V(x) - V_i < \zeta_C$,

$$\|\nabla V(x)\|_{\mathcal{H}} \tilde{\varphi}'_{C}(V(x) - V_i) \geq 1. \quad (16)$$

We now introduce the positive discrete random variable

$$K = \min \{l > 0 \mid (\forall p \geq l) \mathrm{dist}_{\mathcal{H}}(x_p, \bar{C}) \leq \varepsilon_C \text{ and } 0 < V(x_p) - V_{\infty} < \zeta_C \}. \quad (17)$$

According to Assumption 2.21 and Proposition 2.5, for every $\omega \in \Theta \cap \Pi_V$, $K(\omega) < +\infty$. In addition, for every $\omega \in \Theta \cap \Pi_V$, since $V_{\infty}(\omega) \in V(\bar{C}) = \{V_1, \dots, V_I\}$, there exists a unique $i_{\omega} \in I$ such that $V_{\infty}(\omega) = V_{i_{\omega}}$. As a consequence, (16) finally leads to

$$(\forall \omega \in \Theta \cap \Pi_V) \quad (\forall k > K(\omega)) \quad \|\nabla V(x(\omega))\|_{\mathcal{H}} \tilde{\varphi}'_{C}(V(x_k(\omega)) - V_{\infty}(\omega)) \geq 1. \quad (18)$$

Assumption 2.2 and Proposition 2.5 lead to $\mathbb{P}(\Theta) = 1$. Furthermore by assumption we have $\mathbb{P}(\Pi_V) = 1$. Combining the two leads to $\mathbb{P}(\Theta \cap \Pi_V) = 1$ and so concludes the proof. $\square$

**4. An almost sure convergence result based on KŁ theory.** This section is devoted to the implementation of our theoretical approach based on conditioning theory (similarly to [12] in the deterministic case), combined with Proposition 3.7 from the previous section.

In the following, we consider a slightly more restrictive assumption than Assumption 2.21, given below.

**Assumption 4.1.** Process $(V(x_k))_{k \in \mathbb{N}}$ is a $\mathcal{F}_k$-supermartingale on some probability space $(\Omega, \mathcal{F}, \mathbb{P})$, given a filtration $(\mathcal{F}_k)_{k \in \mathbb{N}}$.
Note that if Assumptions 2.1 and 4.1 are satisfied, then Assumption 2.21 holds.

In this section, we first give a technical result in Section 4.1, that will be used to apply the KŁ property in our main result given in Section 4.2.

**4.1. A useful technical lemma.** We introduce here a purely technical lemma which will be useful for establishing the central result of this section

**Lemma 4.2.** *Under Assumption 2.1 and 4.1,*

1. Process $(V(\mathbf{x}_k))_{k \in \mathbb{N}}$ converges almost-surely to an integrable random variable $V_\infty$.

2. Assume that, for all $k \in \mathbb{N}$, either

$$V(\mathbf{x}_k) \geq \mathbb{E}[V_\infty | \mathcal{F}_k] > V_\infty \quad \text{a.s.,} \qquad (19)$$

or

$$V(\mathbf{x}_k) > \mathbb{E}[V_\infty | \mathcal{F}_k] \geq V_\infty \quad \text{a.s.} \qquad (20)$$

Then for any bounded function $\varphi \in \Phi_{+\infty}$

$$\mathbb{E}[X_\varphi] \leq \mathbb{E}[\varphi(V(\mathbf{x}_0) - V_\infty)], \qquad (21)$$

$$\text{where} \quad X_\varphi := \sum_{k=0}^{+\infty} \varphi'(V(\mathbf{x}_k) - V_\infty) (V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1}) | \mathcal{F}_k]). \qquad (22)$$

*Proof.* 1. Since $V$ is lower-bounded as a coercive and continuous function (Assumption 2.1), 1 holds as a direct consequence of the Doob's convergence theorem [61].

2. Let $k \in \mathbb{N}$. By hypothesis, we have $V(\mathbf{x}_k) - V_\infty > 0$, $\mathbb{E}[V(\mathbf{x}_{k+1}) | \mathcal{F}_k] - V_\infty \geq 0$ and $V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1}) | \mathcal{F}_k] \geq 0$. Hence the three quantities $\varphi(V(\mathbf{x}_k) - V_\infty)$, $\varphi(\mathbb{E}[V(\mathbf{x}_{k+1}) | \mathcal{F}_k] - V_\infty)$ and $\varphi'(V(\mathbf{x}_k) - V_\infty)$ are well defined. Further, the concavity of $\varphi$ leads to:

$$\varphi(V(\mathbf{x}_k) - V_\infty) - \varphi(\mathbb{E}[V(\mathbf{x}_{k+1}) | \mathcal{F}_k]) - V_\infty \\ \geq \varphi'(V(\mathbf{x}_k) - V_\infty) (V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1}) | \mathcal{F}_k]) \quad \text{a.s.} \qquad (23)$$

Using the fact that $V_\infty \leq \mathbb{E}[V_\infty | \mathcal{F}_k]$ and $V_\infty \leq V(\mathbf{x}_{k+1})$ almost-surely, we can deduce that

$$\mathbb{E}[V(\mathbf{x}_{k+1}) | \mathcal{F}_k] - V_\infty \\ \geq \mathbb{E}[V(\mathbf{x}_{k+1}) | \mathcal{F}_k] - \mathbb{E}[V_\infty | \mathcal{F}_k] = \mathbb{E}[V(\mathbf{x}_{k+1}) - V_\infty | \mathcal{F}_k] \geq 0 \quad \text{a.s.} \qquad (24)$$

Then, we can apply $\varphi$ to (24) (as an increasing function), and we obtain

$$\varphi(\mathbb{E}[V(\mathbf{x}_{k+1}) | \mathcal{F}_k] - V_\infty) \geq \varphi(\mathbb{E}[V(\mathbf{x}_{k+1}) - V_\infty | \mathcal{F}_k]) \quad \text{a.s.} \qquad (25)$$

Moreover, due to Jensen's inequality:

$$\varphi(\mathbb{E}[V(\mathbf{x}_{k+1}) - V_\infty | \mathcal{F}_k]) \geq \varphi(\mathbb{E}[V(\mathbf{x}_{k+1}) - V_\infty] | \mathcal{F}_k) \quad \text{a.s.} \qquad (26)$$

Hence combining the last two inequalities we get

$$\varphi(\mathbb{E}[V(\mathbf{x}_{k+1}) | \mathcal{F}_k] - V_\infty) \geq \varphi(\mathbb{E}[V(\mathbf{x}_{k+1}) - V_\infty] | \mathcal{F}_k) \quad \text{a.s.} \qquad (25)$$

Injecting (25) in (23) gives:

$$\varphi(V(\mathbf{x}_k) - V_\infty) - \mathbb{E}[\varphi(V(\mathbf{x}_{k+1}) - V_\infty) | \mathcal{F}_k] \\ \geq \varphi'(V(\mathbf{x}_k) - V_\infty) (V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1}) | \mathcal{F}_k]) \quad \text{a.s.} \qquad (26)$$
The two terms involved in (26) being non-negative, we are allowed to pass to expectation operator. Then, by linearity of the expectation (as $\varphi$ is bounded), we obtain

$$ \mathbb{E}[\varphi(V(\mathbf{x}_k) - V_\infty)] - \mathbb{E}[\varphi(V(\mathbf{x}_{k+1}) - V_\infty)] \\ \geq \mathbb{E}[\varphi'(V(\mathbf{x}_k) - V_\infty)(V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k])] \quad \text{a.s..} \quad (27) $$

On the one hand, by summing (27) for $k \in \mathbb{N}$, we have

$$ \sum_{k=0}^{+\infty} (\mathbb{E}[\varphi(V(\mathbf{x}_k) - V_\infty)] - \mathbb{E}[\varphi(V(\mathbf{x}_{k+1}) - V_\infty)]) \\ \geq \sum_{k=0}^{+\infty} \mathbb{E}[\varphi'(V(\mathbf{x}_k) - V_\infty)(V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k])] \\ = \mathbb{E}\left[\sum_{k=0}^{+\infty} \varphi'(V(\mathbf{x}_k) - V_\infty)(V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k])\right], \quad (28) $$

where the last equality holds since $\varphi' \geq 0$.

On the other hand, since $V(\mathbf{x}_k) \xrightarrow{k \to +\infty} V_\infty$ a.s. we have

$$ \mathbb{E}[\varphi(V(\mathbf{x}_k) - V_\infty)] \xrightarrow{k \to +\infty} \mathbb{E}[\varphi(V_\infty - V_\infty)] = 0, $$

by virtue of the dominated convergence theorem (as $\varphi$ is bounded). Hence

$$ \sum_{k=0}^{+\infty} (\mathbb{E}[\varphi(V(\mathbf{x}_k) - V_\infty)] - \mathbb{E}[\varphi(V(\mathbf{x}_{k+1}) - V_\infty)]) = \mathbb{E}[\varphi(V(\mathbf{x}_0) - V_\infty)]. \quad (29) $$

As a consequence, combining (29) and (28) gives

$$ \mathbb{E}[\varphi(V(\mathbf{x}_0) - V_\infty)] \\ \geq \mathbb{E}\left[\sum_{k=0}^{+\infty} \varphi'(V(\mathbf{x}_k) - V_\infty)(V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k])\right] = \mathbb{E}[X_\varphi], \quad (30) $$

which concludes the proof.

□

Conditions (19) and (20) in Lemma 4.2 may look technical. On the one hand, the left hand-side inequalities (of the form $V(\mathbf{x}_k) \geq \mathbb{E}[V_\infty|\mathcal{F}_k]$) always hold in the context of supermartingales, as a direct consequence of Fatou's lemma. However, on the other hand, the right hand-side inequalities (of the form $\mathbb{E}[V_\infty|\mathcal{F}_k] \geq V_\infty$) are more technical, and indicates that the estimation of $V_\infty$ with respect to $\mathcal{F}_k$, i.e. $\mathbb{E}[V_\infty|\mathcal{F}_k]$, must remain greater than the true limit value $V_\infty$ (in other word, we must "approach" this limit "from above").

**4.2. Main result.** We are now ready for our main convergence theorem, that aims to provide a generic framework to show convergence of stochastic schemes in a differentiable non-convex context. To this aim, we need to combine Lemma 4.2 with Proposition 3.7.

**Theorem 4.3.** Assume that Assumptions 2.1, 2.22, 3.6 and 4.1 are verified for a probability space $(\Omega, \mathcal{F}, \mathbb{P})$ and a filtration $(\mathcal{F}_k)_{k \in \mathbb{N}}$. Assume that, for every $k \in \mathbb{N}$, $\|\nabla V(\mathbf{x}_k)\|_{\mathcal{H}} > 0$, and that either (19) or (20) holds, for $V_\infty$ the a.s. limit defined in Lemma 4.21. Then the following hold.
1. There exist $\varphi \in \Phi_{+\infty}$ and an almost-sure finite discrete positive random variable K such that the following inequality holds:

$$ \mathbb{E}[D] \le \mathbb{E}[\varphi(V(\mathbf{x}_0) - V_\infty)] \quad \text{where } D := \sum_{k=K+1}^{+\infty} \frac{V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]}{\|\nabla V(\mathbf{x}_k)\|_{\mathcal{H}}}. \quad (31) $$

2. We have

$$ \sum_{k=0}^{+\infty} \frac{V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]}{\|\nabla V(\mathbf{x}_k)\|_{\mathcal{H}}} < +\infty \text{ a.s..} \quad (32) $$

*Proof.* 1. Let $\Pi_V$ defined as in (10). By hypothesis ((19) or (20)), this is a probability-one set. Thus Proposition 3.7 ensures the existence of $\varphi \in \Phi_{+\infty}$ and an almost-sure finite random variable K such that

$$ (\forall k \ge K) \quad \|\nabla V(\mathbf{x}_k)\|_{\mathcal{H}} \varphi'(V(\mathbf{x}_k) - V_\infty) \ge 1 \text{ a.s..} \quad (33) $$

Let $X_\varphi$ be the variable defined in (22). Using (33), we have

$$ \begin{align*} X_\varphi &= \sum_{k=0}^{K} \varphi'(V(\mathbf{x}_k) - V_\infty) (V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]) \\ &\quad + \sum_{k=K+1}^{+\infty} \varphi'(V(\mathbf{x}_k) - V_\infty) (V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]) \\ &\ge \sum_{k=0}^{K} \varphi'(V(\mathbf{x}_k) - V_\infty) (V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]) \\ &\quad + \sum_{k=K+1}^{+\infty} \frac{V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]}{\|\nabla V(\mathbf{x}_k)\|_{\mathcal{H}}} \\ &\ge \sum_{k=K+1}^{+\infty} \frac{V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]}{\|\nabla V(\mathbf{x}_k)\|_{\mathcal{H}}} \quad \text{a.s.,} \end{align*} $$

where the last inequality is obtained using the fact that $\varphi'$ is positive and Assumption 4.1. Passing to the expectation (all quantities involved are positives almost-surely) and using Lemma 4.2 leads to

$$ \mathbb{E} \left[ \sum_{k=K+1}^{+\infty} \frac{V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]}{\|\nabla V(\mathbf{x}_k)\|_{\mathcal{H}}} \right] \le \mathbb{E}[X_\varphi] \le \mathbb{E}[\varphi(V(\mathbf{x}_0) - V_\infty)]. \quad (34) $$

2. Because $\mathbb{E}[X_\varphi]$ is finite (according to (34)) we have

$$ \sum_{k=K+1}^{+\infty} \frac{V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]}{\|\nabla V(\mathbf{x}_k)\|_{\mathcal{H}}} < +\infty \text{ a.s..} $$

On event $\{K < +\infty\}$, of probability one, we thus have

$$ \begin{align*} & \sum_{k=0}^{+\infty} \frac{V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]}{\|\nabla V(\mathbf{x}_k)\|_{\mathcal{H}}} \\ &= \sum_{k=0}^{K} \frac{V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]}{\|\nabla V(\mathbf{x}_k)\|_{\mathcal{H}}} \end{align*} $$
$$ + \sum_{k=K+1}^{+\infty} \frac{V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]}{\|\nabla V(\mathbf{x}_k)\|_{\mathcal{H}}} < +\infty \text{ a.s..} $$

This concludes the proof.

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

Theorem 4.3 ensures the existence of an upper-bound for the expectation of the variable D (see (31)) which can be interpreted as follows. The residual of the descent condition (i.e. $V(\mathbf{x}_k) - \mathbb{E}[V(\mathbf{x}_{k+1})|\mathcal{F}_k]$) is expected to be “very small” compared to $\|V(\mathbf{x}_k)\|_{\mathcal{H}}$ for $k > K$. When comparing with previous works in the deterministic setting [4, 29, 25], it is consistent to have an upper-bound depending on the desingularization function $\varphi$. In the stochastic case, variable K plays a role similar to a stopping time<fnref n="3" /> that appears to be consistent with [58, Theorem 2.2].

5. **Building $\mathcal{H}$ space and $V$ function for generic SGD.** In the remainder of this work, we will show how the results presented in the previous sections (in particular Theorem 4.3) can be used to establish convergence guarantees of stochastic approximation schemes for solving problem (1).

For the sake of simplicity, we will focus on the asymptotic convergence of a generic stochastic gradient descent (SGD) scheme, with preconditioning. Specifically, we define

$$ (\forall k \in \mathbb{N}) \quad \mathbf{w}_{k+1} = \mathbf{w}_k - \alpha_k \mathbf{U}_k \mathbf{f}_k \qquad (35) $$

where $(\alpha_k)_{k \in \mathbb{N}}$ is a sequence of positive step-sizes, $(\mathbf{f}_k)_{k \in \mathbb{N}}$ is a process of directions belonging to $\mathbb{R}^N$ aiming at approximating the gradients $(\nabla F(\mathbf{w}_k))_{k \in \mathbb{N}}$, and $(\mathbf{U}_k)_{k \in \mathbb{N}}$ is a process of preconditioning matrices in $\mathbb{R}^{N \times N}$. Scheme (35) encompasses the most usual second order methods of SGD [19] and notably, for the non-convex setting, some Newton/Quasi-Newton versions as those of [51, 60]. Then, our analysis will rely on the finding of a finite-dimensional Euclidean space $\mathcal{H}$, a process $(\mathbf{x}_k)_{k \in \mathbb{N}}$ and a Lyapunov-type function $V: \mathcal{H} \to \mathbb{R}$ associated with the problem of interest (1), that will enable stronger convergence guarantees on $(\mathbf{w}_k)_{k \in \mathbb{N}}$ than classical non-convex studies.

5.1. **Assumptions.** We consider a probabilistic space $(\Omega, \mathcal{F}, \mathbb{P})$ with the canonical filtration $\mathcal{F}_0 = \{\emptyset, \Omega\}$ and for all $k \ge 1$ $\mathcal{F}_k = \sigma(\mathbf{f}_0, \mathbf{w}_1, \dots, \mathbf{f}_{k-1}, \mathbf{w}_k)$ the smallest $\sigma$-algebra gathering all the past information from zero to the current state $k$. We consider the following assumptions:

**Assumption 5.1.**

1. $F$ is coercive and $\beta$-Lipschitz differentiable i.e. for every $(\mathbf{w}, \mathbf{w}') \in \mathbb{R}^N \times \mathbb{R}^N$, $\|\nabla F(\mathbf{w}) - \nabla F(\mathbf{w}')\| \le \beta \|\mathbf{w} - \mathbf{w}'\|$.

2. The image of zero $\nabla F$ by $F$ satisfies $|F(\text{zero } \nabla F)| < +\infty$.

3. $(\mathbf{U}_k)_{k \in \mathbb{N}}$ is $\mathcal{F}_k$-measurable, made of symmetric matrices and there exist $\underline{\nu}, \bar{\nu} > 0$ such that:

$$ (\forall k \in \mathbb{N}) \quad \underline{\nu} \|\mathbf{f}_k\|^2 \le \langle \mathbf{f}_k, \mathbf{U}_k \mathbf{f}_k \rangle \le \bar{\nu} \|\mathbf{f}_k\|^2 \text{ a.s..} $$

4. There exist $\mu, B > 0$ and $A, C \ge 0$ such that almost-surely and for all $k \in \mathbb{N}$

$$ \begin{cases} \langle \nabla F(\mathbf{w}_k), \mathbf{U}_k \mathbb{E}[\mathbf{f}_k | \mathcal{F}_k] \rangle \ge \mu \langle \nabla F(\mathbf{w}_k), \mathbf{U}_k \nabla F(\mathbf{w}_k) \rangle \\ \mathbb{E}[\|\mathbf{f}_k\|^2 | \mathcal{F}_k] \le A(F(\mathbf{w}_k) - F^*) + B \|\nabla F(\mathbf{w}_k)\|^2 + C, \end{cases} $$

<footnote n="3">³Note that K is not a stopping time in the purely mathematical sense since, as seen in the proof of Proposition 3.7, it involves the variable $V_\infty$ which is not $\mathcal{F}_k$-measurable.</footnote>
where $F^*$ denotes the minimal value of $F$.

5. The sequence $(\alpha_k)_{k \in \mathbb{N}}$ is positive and verifies the two Robbins-Monro conditions [54] $\sum_{k=0}^{+\infty} \alpha_k = +\infty$ and $\sum_{k=0}^{+\infty} \alpha_k^2 < +\infty$.

<table><caption>TABLE 1. Examples of preconditioned SGD schemes from the literature (introduced by chronological order) satisfying Assumption 5.14-5 and dealing with non-convex problems.</caption><thead><tr><th>Reference</th><th>μ</th><th>A</th><th>B</th><th>C</th><th>U<sub>k</sub></th><th>ν</th><th>ν̄</th></tr></thead><tbody><tr><td>Bertsekas and Tsitsiklis (2000) [9]</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>Schmidt and Leroux (2013) [56]</td><td>✗</td><td>✗</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>Berahas et al (2016) [7]</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Bollapragada et al (2016) [10]</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Wang et al (2017) [60]</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Ghadimi and Lan (2018) [38]</td><td>✗</td><td>✗</td><td>✗</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>Bottou et al (2018) [19]</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>Gower et al (2019) [39]</td><td>✗</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>Jahani et al (2021) [41]</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Chouzenoux and Fest (2022) [26]</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr></tbody></table>

Symbols in each box should be interpreted as follows;

✓: $A, C \neq 0, \mu, B, \nu, \bar{\nu} \neq 1, U_k \neq I_N$.

✗: $A, C = 0, \mu, B, \nu, \bar{\nu} = 1, U_k = I_N$ (i.e. the counterpart conditions of ✓).

Table 1 gives examples of SGD schemes from the literature of the form of (35) satisfying Assumption 5.1. In addition, a few comments can be made on these assumptions, given in the following remark.

**Remark 5.2.**

1. Assumption 5.11 and 2 are directly related to the curvature of $F$, i.e. the function to minimize in (1). The first one is common and tends to promote the existence of a descent condition for any gradient-type schemes (both in deterministic and stochastic) via the usual descent lemma [8]. The second one is necessary to easily verify Assumption 2.2.

2. Assumption 5.13 ensures that $(U_k)_{k \in \mathbb{N}}$ is well-conditioned enough and is not over restrictive. First, since, for every $k \in \mathbb{N}$, $U_k$ is generally constructed using the past information, $F_k$-measurability condition is not too constraining. Second, the uniformly bounded spectrum condition of sequence $(f_k)_{k \in \mathbb{N}}$, which is essential to ensure the existence of a decreasing Lyapunov function associated with the problem, is directly satisfied in the convex case when $(U_k)_{k \in \mathbb{N}}$ approximates the second order information of $F$ (if twice-differentiable) and includes regularity terms in its structure [20, 62]. In the non-convex case, it generally requires specific update rules [60, 22]. Such rules have been investigated extensively also in the deterministic case, in particular within majorization-minimization theory [37, 28].

3. The first condition in Assumption 5.14 classically stipulates that, with respect to the past events, the preconditioned approximate gradient and the true one are oriented in relatively closed directions. This is typically verified in the
situation where process $(f_k)_{k \in \mathbb{N}}$ is unbiased regarding filtration $(\mathcal{F}_k)_{k \in \mathbb{N}}$ i.e. $\mathbb{E}[f_k | \mathcal{F}_k] = \nabla F(w_k)$ a.s. for all $k \in \mathbb{N}$.

The second condition, often called the *ABC Condition* in the literature [43], is linked to the conditional variance and indicates that it can be controlled by three constants: A controlling the distance between the evaluation of $F$ and $F^*$, B controlling the multiplicative tolerable error with respect to the true gradient, and C controlling some additive error. This condition has been first introduced in [9] to investigate SGD convergence in the non-convex setting, with $A = 0$. It has then been used in [38] with $A = 0$ and $B = 1$, and in [56] with $A = C = 0$. The latter case is often called *Strong Growth Condition*. Although this simple case allows to study SGD taking a permissive stepsize (typically a constant one), this situation is only encountered in practice when $F$ (written in the form of an empirical risk) has all its stationary points following an interpolation condition [56]. Examples of these $A, B, C$ variables encountered in the literature are summarized in Table 1.

4. Finally, Assumption 5.15 is the standard Robbins-Monro condition [54] used to control the relative fluctuations of the variance terms, in particular generated by the additive term $C$.

**5.2. Quasi super-martingale condition.** Similarly to the historical approach of [55], the first step to show the convergence of $(w_k)_{k \in \mathbb{N}}$ as defined in (35) is to establish a quasi-supermartingale descent inequality as follows.

**Lemma 5.3.** Under Assumption 5.1 1,3-5, processes $(w_k)_{k \in \mathbb{N}}$ updated given (35) as well as $(\nabla F(w_k))_{k \in \mathbb{N}}$, $(f_k)_{k \in \mathbb{N}}$ are square integrable. Their associated random expectation are thus correctly defined and for all $k \in \mathbb{N}$:

$$ \mathbb{E}[F(\mathbf{w}_{k+1}) - F^* | \mathcal{F}_k] \le (1 + A\lambda\alpha_k^2) (F(\mathbf{w}_k) - F^*) - \alpha_k (\mu\underline{\nu} - B\lambda\alpha_k) \|\nabla F(\mathbf{w}_k)\|^2 + C\lambda\alpha_k^2 \text{ a.s.,} \quad (36) $$

where $\lambda = (\beta\bar{\nu}^2)/2$.

*Proof.* Proving that $(w_k)_{k \in \mathbb{N}}$, $(\nabla F(w_k))_{k \in \mathbb{N}}$, $(f_k)_{k \in \mathbb{N}}$ are square-integrable can be made by induction (see e.g. [26, Lemma 2]). Inequality as those of (36) is very common in the filed of stochastic optimization. In our case, this can be seen as an easy generalization of the proof of [38] or [18], that can typically be found in [60]. □

A common approach to deduce asymptotic convergence results of SGD (in a non-convex setting) using (36) then consists in using the Robbins-Siegmund lemma [55]. In a nutshell, this lemma almost surely ensures that $(F(w_k))_{k \in \mathbb{N}}$ converges to a finite limit, and that $\sum_{k=0}^{+\infty} \alpha_k \|\nabla F(w_k)\|^2 < +\infty$ (assuming that $(\alpha_k)_{k \in \mathbb{N}}$ is small enough). In this article, the framework we have developed aims to drop the square for the summability, i.e. we aim to obtain $\sum_{k=0}^{+\infty} \alpha_k \|\nabla F(w_k)\| < +\infty$. For this we need to build a suitable Lyapunov function $V$ to rely on Theorem 31. Before this, we need to reformulate the algorithm's descent condition (36), obtained in Lemma 5.3.

**Corollary 5.4.** Under Assumption 5.1 1,3-5, the process $(w_k)_{k \in \mathbb{N}}$ defined in (35) satisfies
$$ (\forall k \in \mathbb{N}) \quad \begin{aligned} & \mathbb{E}[p_{k+1}^{-1}(F(\mathbf{w}_{k+1}) - F^*) + C\lambda r_{k+1} | \mathcal{F}_k] \\ & \le p_k^{-1}(F(\mathbf{w}_k) - F^*) + C\lambda r_k - p_{k+1}^{-1}\alpha_k (\mu\underline{\nu} - \lambda B\alpha_k) \|\nabla F(\mathbf{w}_k)\|^2 \quad \text{a.s.,} \quad (37) \end{aligned} $$

where

$$ (\forall k \in \mathbb{N}) \quad p_k := \prod_{i=0}^{k} (1 + A\lambda\alpha_i^2) \quad \text{and} \quad r_k := \sum_{i=k}^{+\infty} p_i^{-1}\alpha_i^2. \quad (38) $$

*Proof.* We only need to show that (36) implies (37).

Since $\sum_{k=0}^{+\infty} \alpha_k^2 < +\infty$ and that, for every $k \in \mathbb{N}$, $p_k \ge 1$, thus we have $\sum_{k=0}^{+\infty} p_k^{-1}\alpha_k^2 < +\infty$. This allows us to write a “difference trick” on $(p_k^{-1}\alpha_k^2)_{k \in \mathbb{N}}$ of the form of:

$$ (\forall k \in \mathbb{N}) \quad p_k^{-1}\alpha_k^2 = \sum_{i=k}^{+\infty} p_i^{-1}\alpha_i^2 - \sum_{i=k+1}^{+\infty} p_i^{-1}\alpha_i^2 = r_k - r_{k+1}. \quad (39) $$

Multiplying, for every $k \in \mathbb{N}$, (36) by $p_{k+1}^{-1}$, and using the fact that the associated sequence $(p_k^{-1})_{k \in \mathbb{N}}$ is non-increasing, we obtain

$$ \begin{aligned} & \mathbb{E}[p_{k+1}^{-1} (F(\mathbf{w}_{k+1}) - F^*) | \mathcal{F}_k] \\ & \le p_{k+1}^{-1} (1 + A\lambda\alpha_k^2) (F(\mathbf{w}_k) - F^*) - p_{k+1}^{-1}\alpha_k (\mu\underline{\nu} - B\lambda\alpha_k) \|\nabla F(\mathbf{w}_k)\|^2 + C\lambda p_{k+1}^{-1}\alpha_k^2 \\ & \le p_{k+1}^{-1} (1 + A\lambda\alpha_k^2) (F(\mathbf{w}_k) - F^*) - p_{k+1}^{-1}\alpha_k (\mu\underline{\nu} - B\lambda\alpha_k) \|\nabla F(\mathbf{w}_k)\|^2 + C\lambda p_k^{-1}\alpha_k^2. \end{aligned} $$

Combining this inequality with (39) leads to the conclusion

$$ \begin{aligned} & \mathbb{E}[p_{k+1}^{-1} (F(\mathbf{w}_{k+1}) - F^*) | \mathcal{F}_k] \\ & \le p_k^{-1} (F(\mathbf{w}_k) - F^*) - p_{k+1}^{-1}\alpha_k (\mu\underline{\nu} - B\lambda\alpha_k) \|\nabla F(\mathbf{w}_k)\|^2 + C\lambda(r_k - r_{k+1}) \quad \text{a.s.,} \end{aligned} $$

hence the result.

□

**5.3. Choice of the Lyapunov function.** As highlighted in the previous subsection, we now aim to build a suitable Lyapunov function $V$ to apply Theorem 31. Considering the Euclidean space product $\mathcal{H} = \mathbb{R}^N \times \mathbb{R} \times \mathbb{R}$ (of finite dimension), we deduce a family of processes able to verify Assumptions 2.2 and 4.1.

**Proposition 5.5.** Assume that Assumptions 5.11-5 hold, and assume that $\sup_{k \in \mathbb{N}} \alpha_k < \mu\underline{\nu}(\lambda B)^{-1}$ (with $\lambda$ given in Lemma 5.3). Let $m \in \mathbb{N}^*$ and define the process $(\mathbf{x}_{m,k})_{k \in \mathbb{N}}$ such that for every $k \in \mathbb{N}$, $\mathbf{x}_{m,k} = (\mathbf{w}_k, p_k^{-1/(2m)}, r_k^{1/(2m)}) \in \mathcal{H}$, where $p_k$ and $r_k$ are defined in Corollary 5.4. Let

$$ V_m: \begin{array}{rcl} \mathcal{H} & \to & \mathbb{R} \\ (\mathbf{w}, t, r) & \mapsto & t^{2m} (F(\mathbf{w}) - F^*) + C\lambda r^{2m} \end{array} \quad (40) $$

and $\Gamma_m := \text{zer } \nabla F \times \{p_{\infty}^{-1/(2m)}\} \times \{0\}$ where $p_{\infty} := \prod_{i=0}^{+\infty} (1 + A\lambda\alpha_i^2) \in (0, +\infty)$. Then the following holds:

1. The limit of $(F(\mathbf{w}_k))_{k \in \mathbb{N}}$, denoted by $F_\infty$ exists and is integrable.

2. $(\mathbf{x}_{m,k})_{k \in \mathbb{N}}$ satisfies Assumption 2.2 and Assumption 4.1 for $V = V_m$ and $\Gamma = \Gamma_m$ defined above.

3. $(V_m(\mathbf{x}_{m,k}))_{k \in \mathbb{N}}$ almost-surely converges to an integrable limit given by

$$ V_{m,\infty} = p_{\infty}^{-1/(2m)} (F_{\infty} - F^*). \quad (41) $$
4. If $F_\infty$ satisfies, for every $k \in \mathbb{N}$, $\mathbb{E}[F_\infty|\mathcal{F}_k] > F_\infty$ a.s., then Lemma 4.22 is satisfied.

*Proof.* Let $m \in \mathbb{N}^*$.

1. Since Lemma 5.3 holds with $\sum_{k=0}^{+\infty} \alpha_k^2 < +\infty$, Robbins-Siegmund lemma can be used [55]. As such and almost-surely, $F_\infty$ is well-defined and integrable.

2. In addition to the previous fact, we also have $\liminf_{k \to +\infty} \|\nabla F(\mathbf{w}_k)\| = 0$ due to $\sum_{k=0}^{+\infty} \alpha_k = +\infty$ and $\sup_{k \in \mathbb{N}} \alpha_k < \mu\underline{\nu}(B\lambda)^{-1}$. We deduce that $\Upsilon_\infty$, the set of accumulation points of $(\mathbf{w}_k)_{k \in \mathbb{N}}$ almost-surely contains a point of zer $\nabla F$. Furthermore, since $r_k^{1/(2m)} \xrightarrow{k \to +\infty} 0$ and $p_k^{-1/(2m)} \xrightarrow{k \to +\infty} p_\infty^{-1/(2m)}$, then the set of accumulation points of $(\mathbf{x}_{m,k})_{k \in \mathbb{N}}$ is equal to $\chi_{m,\infty} = \Upsilon_\infty \times \{p_\infty^{-1/(2m)}\} \times \{0\}$ and contains a point of zer $\nabla F \{p_\infty^{-1/(2m)}\} \times \{0\}$. According to Assumption 5.11, $V_m$ is continuous and coercive. Hence, using Assumption 5.12, we have $|V_m(\text{zer } \nabla F \times \{0\} \times \{p_\infty^{-1}\})| = |F(\text{zer } \nabla F)| < +\infty$, and it follows that Assumption 2.21 is satisfied.

Process $(V_m(\mathbf{x}_{m,k}))_{k \in \mathbb{N}}$ is integrable and, for all $k \in \mathbb{N}$, (37) can be also rewritten as

$$ \mathbb{E}[V_m(\mathbf{x}_{m,k+1}) | \mathcal{F}_k] \leq V_m(\mathbf{x}_{m,k}) - p_{k+1}^{-1} \alpha_k (\mu\underline{\nu} - B\lambda\alpha_k) \|\nabla F(\mathbf{w}_k)\|^2 \quad \text{a.s.} \quad (42) $$

Finally, $\sup_{k \in \mathbb{N}} \alpha_k < \mu\underline{\nu}(\lambda B)^{-1}$ ensures for $(V_m(\mathbf{x}_{m,k}))_{k \in \mathbb{N}}$ to be a supermartingale and so to verify Assumption 4.1.

3. Following from (ii), $(V_m(\mathbf{x}_{m,k}))_{k \in \mathbb{N}}$ almost-surely converges to an integrable limit $V_{m,\infty}$ and regarding (i) and (37), the latter can be expressed as in (41).

4. Then, $F_\infty$ is integrable and, almost-surely for all $k \in \mathbb{N}$, due to $\mathbb{E}[F_\infty|\mathcal{F}_k] > F_\infty$ we have $\mathbb{E}[V_{m,\infty}|\mathcal{F}_k] > V_{m,\infty}$ and Lemma 4.22 holds.

□

The previous proof relies on the convergence $(p_k)_{k \in \mathbb{N}}^{-1/(2m)}(r_k)_{k \in \mathbb{N}}$ to a finite limit, and more specifically on the fact that their set of accumulation points is reduced to a singleton. This allows us to make easy links between process $(F(\mathbf{w}_k))_{k \in \mathbb{N}}$, directly associated with the initial scheme, and process $(V_m(\mathbf{x}_{m,k}))_{k \in \mathbb{N}}$ verifying the supermartingale condition. Asymptotically, the link between $F_\infty$ and $V_{m,\infty}$ is made throughout relation (41) whose remains moderate in term of complexity.

In the case when the constant $A$ appearing in Assumption 5.14 is equal to zero, the choice of the Lyapunov-type space and function can be simplified. Following the same technique of proof as for Proposition 5.5 and using the fact that $p_k := 1$ in such a case, the following result is obtained.

**Proposition 5.6.** Assume that Assumption 5.1 holds with $A = 0$, and assume that $\sup_{k \in \mathbb{N}} \alpha_k < \mu\underline{\nu}(\lambda B)^{-1}$ (with $\lambda$ given in Lemma 5.3). Let $\tilde{\mathcal{H}} = \mathbb{R}^N \times \mathbb{R}$ and $m \in \mathbb{N}^*$. Define the process $(\tilde{\mathbf{x}}_{m,k})_{k \in \mathbb{N}}$ such that for every $k \in \mathbb{N}$, $\tilde{\mathbf{x}}_{m,k} = (\mathbf{w}_k, r_k^{1/(2m)}) \in \tilde{\mathcal{H}}$, where $r_k$ is defined in Corollary 5.4. Let

$$ \begin{aligned} \tilde{V}_m: \quad & \tilde{\mathcal{H}} \to \mathbb{R} \\ (\mathbf{w}, r) \mapsto & \quad F(\mathbf{w}) - F^* + C\lambda r^{2m} \end{aligned} \quad (43) $$

and $\tilde{\Gamma} := \text{zer } \nabla F \times \{0\}$. Then the following holds:
1. The limit of $(F(\mathbf{w}_k))_{k \in \mathbb{N}}$, denoted by $F_\infty$ exists and is integrable.

2. $(\tilde{\mathbf{x}}_{m,k})_{k \in \mathbb{N}}$ satisfies Assumption 2.2 and Assumption 4.1 for $\tilde{V}_m$ and $\tilde{\Gamma}$ defined above.

3. $(\tilde{V}_m(\mathbf{x}_{m,k}))_{k \in \mathbb{N}}$ almost-surely converges to an integrable limit given by

$$ \tilde{V}_{m,\infty} = F_{\infty} - F^{*}. \qquad (44) $$

4. If $F_\infty$ satisfies, for every $k \in \mathbb{N}$, $\mathbb{E}[F_\infty|\mathcal{F}_k] > F_\infty$ a.s., then Lemma 4.22 is satisfied.

**6. Application to generic SGD scheme.** In this section, we introduce our main asymptotical results related to scheme (35), ensuring the convergence in expectation for a sum close to $\sum_{k=0}^{+\infty} \alpha_k \|\nabla F(\mathbf{x}_k)\|$ in a way to estimate the mean length of $(\mathbf{w}_k)_{k \in \mathbb{N}}$. To our knowledge, this result is novel, and although applied here to scheme (35), it could be mimicked to study the asymptotic behaviour of other stochastic processes. A simplified version of these results has been introduced by the authors in [27].

**6.1. Asymptotic behavior of generic SGD scheme in a non-convex setting.** We first aim to study the asymptotic behavior of the SGD scheme given in (35). Similarly to results given in subsection 5.3, we distinguish the cases the constant $A$ of Assumption 4 is zero or not.

**Proposition 6.1.** (Upper-bound in expectation for non-convex SGD) Assume that Assumption 5.1 holds with $\sup_{k \in \mathbb{N}} \alpha_k < \mu\nu(\lambda B)^{-1}$ ($\lambda$ given in Lemma 5.3) and that $F$ verifies the KL property on $\mathbb{R}^N$, given in Definition 3.3. Then, according to Proposition 5.5, process $(F(\mathbf{w}_k))_{k \in \mathbb{N}}$ almost-surely converges to an integrable limit $F_\infty$. Moreover, if the latter almost-surely verifies

$$ (\forall k \in \mathbb{N}) \quad \mathbb{E}[F_\infty|\mathcal{F}_k] > F_\infty \text{ and } \|\nabla F(\mathbf{w}_k)\| > 0, \qquad (45) $$

then, for every $m \in \mathbb{N}^*$, there exists a desingularization function $\varphi_m \in \Phi_{+\infty}$ and an almost-sure finite random variable $K_m > 0$ such that

$$ \mathbb{E} \left[ \sum_{k=K_m}^{+\infty} \frac{\alpha_k \|\nabla F(\mathbf{w}_k)\|}{\sqrt{1 + 4m^2 Y_{m,k}}} \right] \le \left( \frac{1 + A \lambda \bar{\alpha}}{\underline{\nu} - B \lambda \bar{\alpha}} \right) \mathbb{E} \left[ \varphi_m (V_m(\mathbf{x}_{m,0}) - V_{m,\infty}) \right], \quad (46) $$

where $V_m$ (resp $V_{m,\infty}$) is the Lyapunov function (resp its limit) defined in (40) (resp in (41)), and

$$ (\forall k \in \mathbb{N}) \quad Y_{m,k} = \frac{p_k^{1/m} (F(\mathbf{w}_k) - F^*)^2 + (C\lambda)^2 p_k^2 r_k^{2-1/m}}{\|\nabla F(\mathbf{w}_k)\|^2}. \qquad (47) $$

**Proof.** Let $m \in \mathbb{N}^*$. The Lyapunov function $V_m$ defined in (40) is differentiable (Assumption 5.11), and

$$ (\forall (\mathbf{w}, t, r) \in \mathcal{H}) \quad \nabla V_m(\mathbf{w}, t, r) = \left( \frac{t^{2m} \nabla F(\mathbf{w})}{2mt^{2m-1}(F(\mathbf{w}) - F^*)} \right) . \qquad (48) $$

Moreover, since $F$ and $u \in \mathbb{R} \mapsto u^{2m}$ verify the KL property, so it is for $V_m$. Then, according to Proposition 5.5, all the conditions for applying Theorem 4.3 are met.
Hence there exists $\varphi_m \in \Phi_{+\infty}$ as well as an almost-sure finite random variable $K_m > 0$ such that

$$ \mathbb{E} \left[ \sum_{k=K_m}^{+\infty} \frac{V_m(\mathbf{x}_{m,k}) - \mathbb{E}[V_m(\mathbf{x}_{m,k+1})|\mathcal{F}_k]}{\|\nabla V_m(\mathbf{x}_{m,k})\|_{\mathcal{H}}} \right] \le \mathbb{E}[\varphi_m(V_m(\mathbf{x}_{m,0}) - V_{m,\infty})], $$

where $(\mathbf{x}_{m,k})_{k \in \mathbb{N}}$ is defined in Proposition 5.5. Combining this inequality with (42) and (48) with $(\mathbf{w}, t, r) = (\mathbf{w}_k, p_k^{-1/(2m)}, r_k^{1/(2m)})$, we obtain

$$ \mathbb{E} \left[ \sum_{k=K_m}^{+\infty} \frac{p_{k+1}^{-1} \alpha_k (\underline{\nu} - B\lambda\alpha_k) \|\nabla F(\mathbf{w}_k)\|^2}{\sqrt{p_k^{-2} \|\nabla F(\mathbf{w}_k)\|^2 + 4m^2 \left(p_k^{1/m-2}(F(\mathbf{w}_k) - F^*)^2 + (C\lambda)^2 r_k^{2-1/m}\right)}} \right] \le \mathbb{E}[\varphi_m(V_m(\mathbf{x}_{m,0}) - V_{m,\infty})]. $$

Factorizing by $\|\nabla F(\mathbf{w}_k)\|^2$ into the square root of the denominator and using the fact that, for every $k \in \mathbb{N}$, $p_{k+1}/p_k = (1 + A\lambda\alpha_k)$, we obtain

$$ \mathbb{E} \left[ \sum_{k=K_m}^{+\infty} \frac{\alpha_k (\underline{\nu} - B\lambda\alpha_k) (1 + A\lambda\alpha_k)^{-1} \|\nabla F(\mathbf{w}_k)\|}{\sqrt{1 + 4m^2 \left( p_k^{1/m} (F(\mathbf{w}_k) - F^*)^2 + (C\lambda)^2 r_k^{2-1/m} \right) / \|\nabla F(\mathbf{w}_k)\|^2}} \right] \le \mathbb{E}[\varphi_m(V_m(\mathbf{x}_{m,0}) - V_{m,\infty})]. $$

Consequently (46) follows by using $\sup_{k \in \mathbb{N}} \alpha_k < \underline{\nu}(\lambda B)^{-1}$. $\square$

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

Following the same line of proof, starting from Proposition 5.6, we obtain a more specific upper-bound when $A = 0$ in Assumption 5.14.

**Proposition 6.2.** (Upper-bound in expectation for non-convex SGD, $A = 0$) Assume that Assumption 5.1 holds with $A = 0$ and $\sup_{k \in \mathbb{N}} \alpha_k < \mu\underline{\nu}(\lambda B)^{-1}$ ($\lambda$ given in Lemma 5.3) and that $F$ verifies the KŁ property on $\mathbb{R}^N$, given in Definition 3.3. Then, according to Proposition 5.6, process $(F(\mathbf{w}_k))_{k \in \mathbb{N}}$ almost-surely converges to an integrable limit $F_\infty$. Moreover, if (45) holds, then, for every $m \in \mathbb{N}^*$, there exists a desingularization function $\tilde{\varphi}_m \in \Phi_{+\infty}$ and an almost-sure finite random variable $\tilde{K}_m$ such that

$$ \mathbb{E} \left[ \sum_{k=K_m}^{+\infty} \frac{\alpha_k \|\nabla F(\mathbf{w}_k)\|}{\sqrt{1 + 4m^2 \tilde{Y}_{m,k}}} \right] \le (\underline{\nu} - B\lambda\bar{\alpha})^{-1} \mathbb{E}[\tilde{\varphi}_m(\tilde{V}_m(\mathbf{x}_{m,0}) - \tilde{V}_{m,\infty})], \quad (49) $$

where $\tilde{V}_m$ is the Lyapunov function defined in (43), $\tilde{V}_{m,\infty}$ the limit given in (44), and

$$ (\forall k \in \mathbb{N}) \quad \tilde{Y}_{m,k} = \frac{(C\lambda)^2 r_k^{2-1/m}}{\|\nabla F(\mathbf{w}_k)\|^2}. $$

A direct consequence of Propositions 6.1 and 6.2 is that the lengths $\sum_{k=0}^{+\infty} \frac{\alpha_k \|\nabla F(\mathbf{w}_k)\|}{\sqrt{1+4m^2 \tilde{Y}_{m,k}}}$ and $\sum_{k=0}^{+\infty} \frac{\alpha_k \|\nabla F(\mathbf{w}_k)\|}{\sqrt{1+4m^2 \tilde{Y}_{m,k}}}$ are finite almost-surely, hence providing some asymptotical guarantees on the algorithm of interest. Although more explicit forms of $\tilde{K}_m$ and $K_m$ are not needed in practice to implement the algorithm, making them more explicit would provide some additional understanding of the behaviour of the iterates.
Unfortunately, such a problem appears to be particularly challenging as it would require accessing explicitly to functions $\varphi_m$ and $\tilde{V}_m$, that are very difficult to know in practice (see also discussion at the end of Section 3.2). In particular, it is interesting to note that, even in a deterministic setting, the research of convergence rate for non-convex gradient descent-type algorithms under KL property remains particularly challenging as it is strongly correlated to explicitly knowing the $\varphi$ function. More specifically, most of the existing papers tend to work with functions admitting a Lojasiewicz exponent (see Section 3.2) which provides convergence rates directly correlated with such a parameter [2, 25, 29].

**6.2. Particular cases for stronger convergence results.** The results in Propositions 6.1 and 6.2 give upper-bounds on the expectation of the summation of a power of the norm of the gradient of $F$. In this section we will investigate particular cases allowing to deduce stronger convergence guarantees. In particular we first focus on the Strong Growth Condition, and then explore another type of assumption.

**6.2.1. Almost-sure convergence of SDG under Strong Growth Condition.** We consider the process generated in (35), and focus on the case when $A = C = 0$ in Assumption 5.14, i.e., the usual Strong Growth Condition [56]. In this case, it can be noticed that, for every $m \in \mathbb{N}^*$, $\tilde{Y}_{m,k} = 0$, hence the following result is a direct application of Proposition 6.2.

**Proposition 6.3. (Almost sure convergence of SGD under Strong Growth Condition)** Let $(w_k)_{k \in \mathbb{N}}$ be the process generated by (35). Under the same assumptions as in Proposition 6.2, and assuming further that $C = 0$ in Assumption 5.14, the process $(w_k)_{k \in \mathbb{N}}$ almost surely converges to a stationary point of $F$. Moreover, there exists $\varphi \in \Phi_{+\infty}$ and an almost-surely finite random variable $K > 0$ such that

$$ \mathbb{E} \left[ \sum_{k=K}^{+\infty} \alpha_k \| \nabla F(w_k) \| \mid \mathcal{F}_k \right] \le \frac{1}{\bar{\nu}\sqrt{B}} (\underline{\nu} - \bar{\alpha}B\lambda)^{-1} \mathbb{E} \left[ \varphi(F(w_0) - F_\infty) \right], \quad (50) $$

where $F_\infty$ is the integrable limit of $(F(w_k))_{k \in \mathbb{N}}$.

*Proof.* Since $C = 0$, we have, for every $k \in \mathbb{N}$ and $m \in \mathbb{N}^*$, $\tilde{Y}_{m,k} = 0$ in Proposition 6.2, and by definition $\tilde{V}_m(\mathbf{x}_{m,k}) = F(\mathbf{w}_k) - F^*$ and $\tilde{V}_{m,\infty} = F_\infty - F^*$ (see (43) and (44), respectively). It follows that (49) can be simplified as:

$$ \mathbb{E} \left[ \sum_{k=K_m}^{+\infty} \alpha_k \| \nabla F(\mathbf{w}_k) \| \right] \le (\underline{\nu} - \bar{\alpha}B\lambda)^{-1} \mathbb{E} \left[ \varphi_m (F(\mathbf{w}_0) - F_\infty) \right]. \quad (51) $$

Let $k \in \mathbb{N}$. According to (35), and using Assumption 5.14, we have

$$ \mathbb{E} [\|\mathbf{w}_{k+1} - \mathbf{w}_k\| | \mathcal{F}_k] = \alpha_k [\|\mathbf{B}_k \mathbf{f}_k\| | \mathcal{F}_k] \le \alpha_k \bar{\nu} \mathbb{E} [\|\mathbf{f}_k\| | \mathcal{F}_k]. $$

Then, applying Jensen's inequality to the last inequality, combined with Assumption 5.15, yield

$$ \mathbb{E} [\|\mathbf{w}_{k+1} - \mathbf{w}_k\| | \mathcal{F}_k] \le \alpha_k \bar{\nu} \|\mathbb{E}[\mathbf{f}_k | \mathcal{F}_k]\| \le \alpha_k \bar{\nu} \sqrt{B} \|\nabla F(\mathbf{w}_k)\|. $$

Combining the last result with (51), and taking $\varphi = \tilde{\varphi}_m$ and $K = \tilde{K}_m$, we obtain (50).
Since $K > 0$ is finite almost-surely and that all terms in (50) are positive, we can deduce that

$$ \sum_{k=0}^{+\infty} \mathbb{E}[\|\mathbf{w}_{k+1} - \mathbf{w}_k\| | \mathcal{F}_k] < +\infty \text{ a.s..} $$

Since, for every $k \in \mathbb{N}$, $\|\mathbf{w}_{k+1} - \mathbf{w}_k\| \ge 0$, we can use Levy's sharpening of Borel-Cantelli Lemma [49, Ch.1, Th.21] leading to

$$ \sum_{k=0}^{+\infty} \|\mathbf{w}_{k+1} - \mathbf{w}_k\| < +\infty \text{ a.s..} $$

Almost-surely $(\mathbf{w}_k)_{k \in \mathbb{N}}$ is then of finite length (i.e. Cauchy) and so it converges. Finally, similarly to the proof of Proposition 5.5, $(\mathbf{w}_k)_{k \in \mathbb{N}}$ also possesses (almost-surely) an accumulation point contained in $\text{zer } \nabla F$, hence the conclusion. $\square$

### 6.2.2. Convergence guarantees under particular convergence rate conditions.
In Proposition 6.3 we shown that, under the assumption that $A = C = 0$, the process $(\mathbf{w}_k)_{k \in \mathbb{N}}$ is of finite length almost surely. In this section we aim to extend this result for a class of events even when $A$ and $C$ are non-zero. Hence we introduce the two following events:

$$ \Xi_1 := \bigcup_{m \in \mathbb{N}^*} \left\{ \limsup_{k \to +\infty} \left[ \frac{\left( \sum_{i=k}^{+\infty} \alpha_i^2 \right)^{2-\frac{1}{m}}}{\|\nabla F(\mathbf{w}_k)\|^2} \right] < +\infty \right\}, \quad (52) $$

$$ \Xi_2 := \left\{ \limsup_{k \to +\infty} \frac{(F(\mathbf{w}_k) - F^*)}{\|\nabla F(\mathbf{w}_k)\|} < +\infty \right\}, \quad (53) $$

that will act as control bounds on the behaviour of the gradient and the step-size of SGD. Before giving further intuition on these bounds, we give the following convergence guarantees on these events.

**Corollary 6.4.** We consider the same assumptions as in Proposition 6.1. Then

$$ \sum_{k=0}^{+\infty} \alpha_k \|\nabla F(\mathbf{w}_k)\| < +\infty $$

almost-surely on the event

$$ \Xi := \begin{cases} \Xi_1 & \text{if } A = 0, \\ \Xi_2 & \text{if } C = 0, \\ \Xi_1 \cap \Xi_2 & \text{otherwise.} \end{cases} \quad (54) $$

*Proof.* We first look at the case $\Xi = \Xi_1 \cap \Xi_2$. We introduce

$$ A := \bigcap_{m \in \mathbb{N}^*} \left\{ \sum_{k=0}^{+\infty} \frac{\alpha_k \|\nabla F(\mathbf{w}_k)\|}{\sqrt{1 + Y_{m,k}}} < +\infty \right\}. $$

Let $\omega \in \Xi \cap A$. By definition of $\Xi$ and $\Xi_1$ more specifically, there exists $m_\omega > 0$ s.t.

$$ \frac{\left( \sum_{i=k}^{+\infty} \alpha_i^2 \right)^{2-\frac{1}{m_\omega}}}{\|\nabla F(\mathbf{w}_k(\omega))\|^2} < +\infty. \quad (55) $$
Then, reformulating (47) we have

$$Y_{m_{\omega}, k}(\omega) = p_k^{1/m_{\omega}} \frac{(F(\mathbf{w}_k(\omega)) - F^*)}{\|\nabla F(\mathbf{w}_k(\omega))\|} + (C\lambda)^2 p_k^2 \frac{r_k^{2-1/m_{\omega}}}{\|\nabla F(\mathbf{w}_k(\omega))\|^2}.$$

On the one hand, since $(p_k)_{k \in \mathbb{N}}$ is bounded (as it converges to $p_\infty$) On the other hand, since, by definition of $(r_k)_{k \in \mathbb{N}}$ (see (38)), we have $r_k < \sum_{i=k}^{+\infty} \alpha_i^2$ then the second term in the above equation is also finite. It follows that $(Y_{m_{\omega}, k}(\omega))_{k \in \mathbb{N}}$ is bounded and so

$$\frac{1}{\sqrt{1 + Y_{m_{\omega}, k}(\omega)}} = \mathcal{O}(1). \qquad (56)$$

As $\omega \in \mathcal{A}$

$$\sum_{k=0}^{+\infty} \frac{\alpha_k \|\nabla F(\mathbf{w}_k(\omega))\|}{\sqrt{1 + Y_{m_{\omega}, k}(\omega)}} < +\infty, \qquad (57)$$

and, from positivity $(Y_{m_{\omega}, k}(\omega))_{k \in \mathbb{N}}$ and (56), this leads to

$$\sum_{k=0}^{+\infty} \alpha_k \|\nabla F(\mathbf{w}_k(\omega))\| < +\infty. \qquad (58)$$

Since Proposition 6.1 ensures that $\mathbb{P}(\mathcal{A}) = 1$, (58) thus occurs for almost every $\omega$ of $\Xi$, hence the conclusion.

Cases $\Xi = \Xi_1$ and $\Xi = \Xi_2$ can be treated in a similar way (consider $(\tilde{Y}_{m,k})_{k \in \mathbb{N}}$ instead of $(Y_{m,k})_{k \in \mathbb{N}}$ for the case $A = 0$). $\square$

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

The practical use of Corollary 6.4 depends on the probabilities $\mathbb{P}(\Xi_1)$, $\mathbb{P}(\Xi_2)$, that should be close to 1 to be of interest. We discuss below a few examples where this happens to be the case $(\Xi_2$ first, $\Xi_1$ then).

**Example 6.5.** If $F$ is assumed to be $\rho$-strongly convex ($\rho > 0$), then the following particular version of Łojasiewicz inequality (see e.g. [42]) holds

$$\forall w \in \mathbb{R}^N \quad \|\nabla F(w)\|^2 \geq 2\rho(F(w) - F^*) \qquad (59)$$

which ensures that

$$\forall k \in \mathbb{N} \quad \frac{F(\mathbf{w}_k) - F^*}{\|\nabla F(\mathbf{w}_k)\|} = \frac{\sqrt{F(\mathbf{w}_k) - F^*}}{\|\nabla F(\mathbf{w}_k)\|} \sqrt{F(\mathbf{w}_k) - F^*} \leq \frac{1}{\sqrt{2\rho}} \sqrt{F(\mathbf{w}_k) - F^*}. \qquad (60)$$

Since $(F(\mathbf{w}_k) - F^*)_{k \in \mathbb{N}}$ almost-surely converges to the almost-sure finite limit $F_\infty - F^* \geq 0$, (60) conducts to $\mathbb{P}(\Xi_2) = 1$ with

$$\limsup_{k \to +\infty} \frac{F(\mathbf{w}_k) - F^*}{\|\nabla F(\mathbf{w}_k)\|} \leq \frac{1}{\sqrt{2\rho}} \sqrt{F_\infty - F^*} \quad \text{a.s.}.. \qquad (61)$$

To investigate more general cases than the convex settings described in Example 6.5, we need to take a closer look at the convergence rates of the SGD scheme. Intuitively, as discussed in [57], the gradient $(\|\nabla F(\mathbf{w}_k)\|)_{k \in \mathbb{N}}$ should not converge too fast to 0 to enable the event $\Xi$ to not be too small, as shown in the following example.
**Example 6.6.** Let, for every $k \in \mathbb{N}$, $\alpha_k = \frac{a}{k^{\frac{1}{2}+\epsilon}}$ with $a > 0$ small enough and $\epsilon \in (0, \frac{1}{2})$. Then, according to [57, Corollary 18], we have

$$ \min_{1 \le i \le k} \|\nabla F(\mathbf{w}_i)\|^2 = o\left(\frac{1}{k^{\frac{1}{2}-\epsilon}}\right) \text{ a.s..} $$

Hence, intuitively, we can postulate that $\|\nabla F(\mathbf{w}_i)\|^2$ does not decrease faster than $\frac{1}{k^{1/2}}$. As such, assuming that $\|\nabla F(\mathbf{w}_k)\|^2 \sim \frac{1}{k^{1/2}}$ almost surely, then for all $m \in \mathbb{N}^*$, we deduce that

$$ \frac{\left(\sum_{i=k}^{+\infty} \alpha_i^2\right)^{2-\frac{1}{m}}}{\|\nabla F(\mathbf{w}_k)\|^2} \underset{k \to +\infty}{\sim} \left(\frac{a^2}{k^{2\epsilon}}\right)^{2-\frac{1}{m}} k^{\frac{1}{2}} = \mathcal{O}\left(k^{\left(\frac{1}{2}-2\epsilon\left(2-\frac{1}{m}\right)\right)}\right) \text{ a.s..} $$

Since $\frac{1}{2}-2\epsilon(2-\frac{1}{m}) \underset{m \to +\infty}{\to} \frac{1}{2}-4\epsilon$, we deduce that, if $\epsilon \in [\frac{1}{8}, \frac{1}{2})$, there exists $m_0 \in \mathbb{N}^*$ for which $\frac{1}{2}-2\epsilon(2-\frac{1}{m_0}) \le 0$ and

$$ \frac{\left(\sum_{i=k}^{+\infty} \alpha_i^2\right)^{2-\frac{1}{m_0}}}{\|\nabla F(\mathbf{w}_k)\|^2} = \mathcal{O}(1) \text{ a.s.} $$

Hence we have $\mathbb{P}(\Xi_1) = 1$.

## 7. Discussion and conclusion.
In this work, we presented a new framework to investigate convergence properties of stochastic schemes in a non-convex context.

In Sections 3-4, we introduced a framework to apply the KL property in a stochastic setting. In this context the notion of “decay”, that is usually key to study convergence on deterministic schemes in a non-convex setting, is associated with that of supermartingale. It then appears to be more difficult to satisfy in the stochastic than in the deterministic case. To circumvent this difficulty, we made the choice to add mild conditions as those described in Theorem 4.3. This allowed us to derive new asymptotic results leveraging mathematical tools different from the standard ODE method and “trajectory-by-trajectory” strategy used in [5, 32, 58]. In Sections 5-6, we studied the case of the SGD scheme to show that our assumptions are reasonable in practice. In particular, they do not require specific curvature properties for the functions on interest.

Finally, we focused on the particular case of smooth functions. However, as highlighted in [14, 12], we are naturally led to consider a non-smooth extension of our framework. Using non-smooth version of the KL property, Sections 3-4 could be straightforwardly extended to non-smooth coercive and continuous Lyapunov functions $V$. The difference would only be of structural order, by replacing the gradient norm by the distance of the limiting subdifferential [52] to zero. Note that the stochastic non-smooth case has been investigated for particular schemes (see e.g., [31] or [40]).

## References.

[1] Pierre-Antoine Absil, Robert Mahony, and Benjamin Andrews. “Convergence of the iterates of descent methods for analytic cost functions”. In: *SIAM Journal on Optimization* 16.2 (2005), pp. 531–547.

[2] Hedy Attouch and Jérôme Bolte. “On the convergence of the proximal algorithm for nonsmooth functions involving analytic features”. In: *Mathematical Programming* 116 (2009), pp. 5–16.
[3] Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter. "Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods". In: *Mathematical Programming* 137.1 (2013), pp. 91–129.

[4] Hédy Attouch et al. "Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality". In: *Mathematics of Operations Research* 35.2 (2010), pp. 438–457.

[5] Michel Benaim. "A dynamical system approach to stochastic approximations". In: *SIAM Journal on Control and Optimization* 34.2 (1996), pp. 437–472.

[6] Michel Benaim. "On strict convergence of stochastic gradients". In: *arXiv preprint arXiv:1610.03278* (2016).

[7] Albert S Berahas, Jorge Nocedal, and Martin Takác. "A multi-batch L-BFGS method for machine learning". In: *Advances in Neural Information Processing Systems* 29 (2016).

[8] Dimitri P Bertsekas. *Nonlinear Programming*. 2nd. Athena Scientific, 1999.

[9] Dimitri P Bertsekas and John N Tsitsiklis. "Gradient convergence in gradient methods with errors". In: *SIAM Journal on Optimization* 10.3 (2000), pp. 627–642.

[10] Raghu Bollapragada, Richard H Byrd, and Jorge Nocedal. "Exact and inexact subsampled Newton methods for optimization". In: *IMA Journal of Numerical Analysis* 39.2 (2019), pp. 545–578.

[11] Jérôme Bolte, Aris Daniilidis, and Adrian Lewis. "The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems". In: *SIAM Journal on Optimization* 17.4 (2007), pp. 1205–1223.

[12] Jérôme Bolte, Shoham Sabach, and Marc Teboulle. "Proximal alternating linearized minimization for nonconvex and nonsmooth problems". In: *Mathematical Programming* 146.1 (Aug. 2014), pp. 459–494.

[13] Jérôme Bolte et al. "Characterizations of Lojasiewicz inequalities and applications". In: *arXiv preprint arXiv:0802.0826* (2008).

[14] Jérôme Bolte et al. "Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity". In: *Transactions of the American Mathematical Society* 362.6 (2010), pp. 3319–3363.

[15] Jérôme Bolte et al. "Clarke subgradients of stratifiable functions". In: *SIAM Journal on Optimization* 18.2 (2007), pp. 556–572.

[16] Silvia Bonettini, Marco Prato, and Simone Rebegoldi. "Convergence of Inexact Forward-Backward Algorithms Using the Forward-Backward Envelope". In: *SIAM Journal on Optimization* 30.4 (2020), pp. 3069–3097.

[17] Silvia Bonettini, Marco Prato, and Simone Rebegoldi. "New convergence results for the inexact variable metric forward-backward method". In: *Applied Mathematics and Computation* 392 (2021), p. 125719.

[18] Léon Bottou. "Large-scale machine learning with stochastic gradient descent". In: *Proceedings of COMPSTAT'2010*. Springer, 2010, pp. 177–186.

[19] Léon Bottou, Frank E Curtis, and Jorge Nocedal. "Optimization methods for large-scale machine learning". In: *Siam Review* 60.2 (2018), pp. 223–311.

[20] Richard H Byrd et al. "A stochastic quasi-Newton method for large-scale optimization". In: *SIAM Journal on Optimization* 26.2 (2016), pp. 1008–1031.
[21] Mathieu Chalvidal et al. "Block delayed Majorize-Minimize subspace algorithm for large scale image restoration". In: *Inverse Problems* 39.4 (2023), p. 044002.

[22] Huiming Chen et al. "A stochastic quasi-Newton method for large-scale non-convex optimization with applications". In: *IEEE transactions on neural networks and learning systems* 31.11 (2019), pp. 4776-4790.

[23] Ralph Chill, Alain Haraux, and Mohamed Ali Jendoubi. "Applications of the Lojasiewicz-Simon gradient inequality to gradient-like evolution equations". In: *Anal. Appl. (Singap.)* 7.4 (2009), pp. 351-372.

[24] E. Chouzenoux, J.-C. Pesquet, and A. Repetti. "A Block Coordinate Variable Metric Forward-Backward Algorithm". In: *Journal of Global Optimization* 66.3 (Nov. 2016), pp. 457-485.

[25] Emilie Chouzenoux and Jean-Baptiste Fest. "Convergence analysis of block majorize-minimize subspace approach". In: *Optimization Letters* (2023), pp. 1-20.

[26] Emilie Chouzenoux and Jean-Baptiste Fest. "SABRINA: A stochastic subspace majorization-minimization algorithm". In: *Journal of Optimization Theory and Applications* 195 (2022), pp. 919-952.

[27] Emilie Chouzenoux, Jean-Baptiste Fest, and Audrey Repetti. "A Kurdyka-Lojasiewicz property for stochastic optimization algorithms in a non-convex setting". In: (2023). https://inria.hal.science/hal-03992655v1.

[28] Emilie Chouzenoux, Jérôme Idier, and Said Moussaoui. "A majorize-minimize strategy for subspace optimization applied to image restoration". In: *IEEE Transactions on Image Processing* 20.6 (2010), pp. 1517-1528.

[29] Emilie Chouzenoux, Jean-Christophe Pesquet, and Audrey Repetti. "Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function". In: *Journal of Optimization Theory and Applications* 162.1 (2014), pp. 107-132.

[30] Emilie Chouzenoux et al. "A majorize-minimize subspace approach for $ℓ_2 - ℓ_0$ image regularization". In: *SIAM Journal on Imaging Sciences* 6.1 (2013), pp. 563-591.

[31] Damek Davis. *The asynchronous PALM algorithm for nonsmooth nonconvex problems*. Tech. rep. arXiv:1604.00526. 2016.

[32] Steffen Dereich and Sebastian Kassing. "Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes". In: *arXiv:2102.09385* (2021).

[33] Derek Driggs et al. "SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization". In: *arXiv:2002.12266* (2020).

[34] Marie Duflo. *Random Iterative Models*. Berlin Heidelberg: Springer-Verlag, 2013.

[35] P. Frankel, G. Garrigos, and J. Peypouquet. "Splitting methods with variable-metric for Kurdyka-Łojasiewicz functions and general convergence rates". In: *Journal of Optimization Theory and Applications* 165.3 (2015), pp. 874-900.

[36] Sébastien Gadat and Fabien Panloup. *Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity*. Tech. rep. arXiv preprint arXiv:1709.03342. 2017.

[37] Donald Geman and Chengda Yang. "Nonlinear image recovery with half-quadratic regularization". In: *IEEE transactions on Image Processing* 4.7 (1995), pp. 932-946.
[38] Saeed Ghadimi and Guanghui Lan. “Stochastic first-and zeroth-order methods for nonconvex stochastic programming”. In: *SIAM Journal on Optimization* 23.4 (2013), pp. 2341–2368.

[39] Robert Mansel Gower et al. “SGD: General analysis and improved rates”. In: *International conference on machine learning*. PMLR. 2019, pp. 5200–5209.

[40] Johannes Hertrich and Gabriele Steidl. “Inertial stochastic PALM and applications in machine learning”. In: *Sampling Theory, Signal Processing, and Data Analysis* 20.1 (2022), p. 4.

[41] Majid Jahani et al. “Doubly adaptive scaled algorithm for machine learning using second-order information”. In: *arXiv preprint arXiv:2109.05198* (2021).

[42] Hamed Karimi, Julie Nutini, and Mark Schmidt. “Linear convergence of gradient and proximal-gradient methods under the polyak-Łojasiewicz condition”. In: *Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16*. Springer. 2016, pp. 795–811.

[43] Ahmed Khaled and Peter Richtárik. *Better theory for SGD in the nonconvex world*. Tech. rep. arXiv:2002.03329. 2020.

[44] Krzysztof Kurdyka. “On gradients of functions definable in o-minimal structures”. In: *Annales de l'institut Fourier*. Vol. 48. 3. 1998, pp. 769–783.

[45] Guoyin Li and Ting Kei Pong. “Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods”. In: *Foundations of computational mathematics* 18.5 (2018), pp. 1199–1232.

[46] Xiao Li, Andre Milzarek, and Junwen Qiu. “Convergence of random reshuffling under the kurdyka-Łojasiewicz inequality”. In: *SIAM Journal on Optimization* 33.2 (2023), pp. 1092–1120.

[47] Lennart Ljung. “Strong convergence of a stochastic approximation algorithm”. In: *The Annals of Statistics* 6.3 (1978), pp. 680–696.

[48] Stanislas Łojasiewicz. “Sur la géométrie semi-et sous-analytique”. In: *Annales de l'institut Fourier*. Vol. 43. 5. 1993, pp. 1575–1595.

[49] Paul-André Meyer. *Martingales and Stochastic Integrals I*. Vol. 284. Springer, 2006.

[50] Andre Milzarek and Junwen Qiu. “Convergence of a Normal Map-based ProxSGD Method under the KL Inequality”. In: *arXiv preprint arXiv:2305.05828* (2023).

[51] Aryan Mokhtari and Alejandro Ribeiro. “RES: Regularized stochastic BFGS algorithm”. In: *IEEE Transactions on Signal Processing* 62.23 (2014), pp. 6089–6104.

[52] Boris S Mordukhovich. *VARIATIONAL ANALYSIS AND GENERALIZED DIFFERENTIATION Vol. I: Basic Theory, Vol. II: Applications*. 2006.

[53] A. Repetti and Y. Wiaux. “Variable Metric Forward-Backward Algorithm for Composite Minimization Problems”. In: *SIAM Journal on Optimization* 31.2 (May 2021), pp. 1215–1241.

[54] Herbert Robbins and Sutton Monro. “A stochastic approximation method”. In: *The Annals of Mathematical Statistics* (1951), pp. 400–407.

[55] Herbert Robbins and David Siegmund. “A convergence theorem for non negative almost supermartingales and some applications”. In: *Optimizing Methods in Statistics* (1971), pp. 233–257.
[56] Mark Schmidt and Nicolas Le Roux. *Fast convergence of stochastic gradient descent under a strong growth condition*. Tech. rep. arXiv:1308.6370. 2013.

[57] Othmane Sebbouh, Robert M Gower, and Aaron Defazio. "Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball". In: *Proceedings of the Conference on Learning Theory (COLT 2021)*. 2021, pp. 3935–3971.

[58] Vladislav B Tadić. "Convergence and convergence rate of stochastic gradient search in the case of multiple and non-isolated extrema". In: *Stochastic Processes and their Applications* 125.5 (2015), pp. 1715–1755.

[59] William J Terrell. *Stability and stabilization: an introduction*. Princeton University Press, 2009.

[60] Xiao Wang et al. "Stochastic quasi-Newton methods for nonconvex stochastic optimization". In: *SIAM Journal on Optimization* 27.2 (2017), pp. 927–956.

[61] David Williams. *Probability with martingales*. Cambridge university press, 1991.

[62] Farzad Yousefian, Angelia Nedić, and Uday V Shanbhag. "Stochastic quasi-Newton methods for non-strongly convex problems: convergence and rate analysis". In: *2016 IEEE 55th Conference on Decision and Control (CDC)*. IEEE. 2016, pp. 4496–4503.

[63] Peiran Yu, Guoyin Li, and Ting Kei Pong. "Kurdyka-Łojasiewicz exponent via inf-projection". In: *Foundations of Computational Mathematics* 22.4 (2022), pp. 1171–1217.