# A new use of the Kurdyka-Łojasiewicz property to study asymptotic behaviours
of some stochastic optimization algorithms in a non-convex differentiable
framework

Jean-Baptiste Fest∗
∗Formerly CVN, CentraleSupélec, Inria, Université Paris-Saclay, France
E-mail<EMAIL_ADDRESS>
###### Abstract

The asymptotic analysis of a generic stochastic optimization algorithm mainly
relies on the establishment of a specific descent condition. While the
convexity assumption allows for technical shortcuts and generally leads to
strict convergence, dealing with the non-convex framework, on the contrary,
requires the use of specific results as those relying on the Kurdyka-
Łojasiewicz (KL) theory. While such tools have become popular in the field of
deterministic optimisation, they are much less widespread in the stochastic
context and, in this case, the few works making use of them are essentially
based on trajectory-by-trajectory approaches. In this paper, we propose a new
methodology, also based on KL theory, for deeper asymptotic investigations on
a stochastic scheme verifying a descent condition. The specificity of our work
is here to be of macroscopic nature insofar as our strategy of proof is more
in-expectation-based and therefore seems more natural typically with respect
to the noise properties, of conditional order, encountered in the stochastic
literature nowadays.

Keywords. Stochastic processes, Non-convexity, Kurdyka-Łojasiewicz properties,
Stochastic Gradient Descent.

##  1 Introduction

The theoretical analysis of a discrete process
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ with values in a (finite-dimensional)
Euclidean space ${\mathcal{E}}$ and generated from a stochastic approximation
scheme is based on the establishment of a specific condition involving a
function of interest $V:{\mathcal{E}}\to{\mathbb{R}}$, the structure of which
depends both on the parameters and on the problem initially studied. By
analogy with the stabilisation theory for dynamic systems [42], $V$ behaves in
the same way as a Lyapunov function in that the latter is constructed to be
lower-bounded and to ensure, in a certain mathematical sense, the decay and
then the convergence of $\left(V({\mathbf{x}}_{k})\right)_{k\in{\mathbb{N}}}$.
As such, the existence of such a function is fundamental insofar as it enables
us to judge the relevance of the initial scheme by ensuring a certain
robustness. More precisely, we are here interested in functions $V$ we suppose
to be ”decreasing” in the sense that they satisfy a supermartingale behaviour
[44] (for a certain filtration living in a given probability space).
In an optimization context over another Euclidean space ${\mathcal{W}}$, given
a cost function $F:{\mathcal{W}}\to{\mathbb{R}}$, for which we aim to
investigate on the convergence of an attached minimization process
$({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$, space ${\mathcal{E}}$,
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ and $V$ cannot be taken so as
${\mathcal{W}}$, $({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ and $F$ respectively
except in simple cases. This actually assumes that the process
$(F({\mathbf{w}}_{k}))_{k\in{\mathbb{N}}}$ verifies itself a supermartingale
condition which reveals to be quite strong. More generally, the original
theory of stochastic approximation [37] actually highlighted the fact
$(F({\mathbf{w}}_{k}))_{k\in{\mathbb{N}}}$ prone to ”only” verify what it is
called an almost-supermartingale condition [38]. In many cases, however, it is
fairly easy to construct ${\mathcal{E}}$,
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ and $V$ with structures that make them
fairly easy to link with those of ${\mathcal{W}}$,
$({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ and $F$. Typically, if we come back to
the previous example, the convergence properties of an almost-supermartingale
are based on the rewriting of its associated conditional inequality as a
martingale relation relative to certain Lyapunov-type process [38] depending,
at a current iteration $k\in{\mathbb{N}}$, both on ${\mathbf{w}}_{k}$ and
additional algorithms parameters (e.g. the stepsize value, the moments of the
noise under consideration…). beyond this example, the use of Lyapunov-type
processes to conclude on the convergence of discrete schemes has spanned over
the last decades and was notably been formalised for the first time in [36].

#### General approach to deal with non-convexity

Although the construction of a Lyapunov-type process that shall remain easy to
connect to the original problem is essential, our work focuses more on the
step upstream where this time we fix ${\mathcal{E}}$, a function
$V:{\mathcal{E}}\to{\mathbb{R}}$ and an attached process
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ for which
$\left(V({\mathbf{x}}_{k})\right)_{k\in{\mathbb{N}}}$ turns out to be a
supermartingale. More specifically, what we want to do here is to propose
additional assumptions, as mild as possible but relevant enough, to obtain
finer asymptotic behaviours for $({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ and so
new information on the original problem (typically relative to the almost-sure
convergence of $({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ in an optimization
setting). In particular, we are endeavouring to remain within a non-convex
study framework.
In such a context, obtaining almost-sure convergence results for
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ that are not just direct consequences
of the attached descent condition (i.e. the supermartingale inequality) turns
out to be a major challenge insofar as it requires further researches on
$\chi^{\infty}$, the set of accumulation points of
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ whose structure is difficult to
unravel. Apart from the special case where $\chi^{\infty}$ is included in a
subset that is only made up of isolated points [30], there are no easy
technical shortcuts that can be used to conclude on a potential almost-sure
convergence behavior. As such, without any strong assumption on
$\chi^{\infty}$, the most common approach to deal with non-convexity relies on
the ODE method [3] given the following starting point; most of the stochastic
schemes encountered (e.g. the original one of [37]) has an asymptotic
behaviour that can be likened to that of a particular differential equation.

#### Łojasiewicz theory

Either in stochastic or deterministic settings and similarly with Lyapunov
method, the theoretical tools used to obtain additional asymptotic information
on discrete approximation schemes mainly derived from the continuous domain.
In our setting, those dealing with non-convexity, as generically as possible
(typically outside the quasi-convex framework), were initially developped to
provide some answers to the subanalytic geometry problem which consists in
obtaining convergence guarantees for trajectories of a given bounded gradient
flow. Historically, [31] was the first paper to provide a sufficient condition
of convergence, for the class of analytical functions, under the form of a
local curvature relation, the Łojasiewicz (L) inequality, named after its
author. Its transposition to the discrete deterministic framework was carried
by works such as [1] which remains the first contribution to really highlight
the interest of such an inequality to establish the strict convergence of an
iterative approximation scheme starting from a descent condition. Regarding
the stochastic context, as (L)-inequality was originally designed to solve a
problem focused of the gradient flow trajectories, it naturally shares a
strong connection with the ODE method. From this observation, making the link
with its anterior work [3] and those of [16], [4] was typically able to
provide strong convergence guarantees for non-convex SGD applied to real
analytic cost functions and without considering that all stationary points are
isolated (which allowed technical shortcuts in the vein of [30]). Nevertheless
and although its approach remains less popular, [41] was actually the first
work to invoke (L)-inequality to obtain strict convergence results for the
latter scheme in a similar context.

#### Paper’s location in the literature

Following the analogy with the physical world, the ODE strategy of proofs [3,
4] as well as those of [41] can be considered of microscopic nature insofar as
they propose an analysis following a trajectory-by-trajectory approach.
Because we directly place ourselves in a supermartingale context, our work
aims to provide an alternative approach, more of macroscopic order or ”in
mean” insofar as we here strive to deploy techniques directly taken from the
field of conditioning. In contrast to the ODE approach, the combination of
conditioning theory with the use of (L)-inequality to deal with the non-convex
setting is still relatively marginal and, to our knowledge, has only been
studied [21].
Nevertheless, we are here straying somewhat from Łojasiewicz’s original
framework in that the Lyapunov-type functions that we manipulate are assumed
to follow the more general Kurdyka Łojasiewicz (KL)-property proposed by K.
Kurdyka in the line of the work of his peer, which holds for differentiable
functions definable an o-minimal structure [28]. As for inequality-(L), the
interest of (KL)- property for discrete deterministic approximation remains a
recent development whose emergence is mainly due to the pioneering work [8, 2,
9]. Its use in the stochastic framework is even rarer and seems to be limited
to two articles initially dedicated to the construction of new proximal
methods. On the one hand, by taking account of the mini-batch structure of
their approximation and then by adapting the deterministic line of proof of
[9], [22] proposed a new version of the (KL)-property, in expectation, to
prove the strict convergence of their algorithm. On the other hand, [33] used
a slightly stronger formulation and proceeded this time to a trajectory-by-
trajectory approach to reach similar conclusions.

#### Organization

In the light of this discussion, our approach can be formulated a little more
precisely. Starting from a process
$\left(V({\mathbf{x}}_{k})\right)_{k\in{\mathbb{N}}}$ (typically of Lyapunov-
type) following a supermartingale behaviour, we make use of the (KL)-property,
instead of a convexity assumption, to obtain more precise asymptotic results,
i.e. which are not direct consequences of the associated
descent/supermartingale inequality. Unlike the ODE approach, our strategy is
based more on the methodology of proof typically developed in [9] we seek to
adapt to a stochastic framework based on assumptions of conditional nature.
Finally, using less restrictive and more easily interpretable assumptions,
this work can be seen as an extension and so an improvement of the one we
carried out in [18].
The rest of the paper is thus organized as follows. Section 2 presents the
very fundamental toolbox we need to carry out our investigations. Section 3
can be considered as the cornerstone of our theoretical analysis to the extent
we deploy the differentiable version of (KL)-property to combine the latter
with our stochastic setting. This allows us to deduce, in Section 4, our main
result which consists in a summability condition between the supermatingale
descent condition and the gradient sequence attached to
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$. The main purpose of section 5 is to
assess the relevance of this result in order to deduce new behaviours on
strict convergence for stochastic algorithms. More precisely, we here place
ourselves in the relatively well-known context for which
$\left(V({\mathbf{x}}_{k})\right)_{k\in{\mathbb{N}}}$ is related to a generic
stochastic gradient descent (SGD) scheme of the type of [25]. Section 6
develops a number of avenues of exploration that we believe could be pursued
from this work and especially regarding a non-smooth context.

#### General notations

$({\mathcal{E}},\left\langle\cdot|\cdot\right\rangle_{{\mathcal{E}}})$
correspond to the (finite-dimensional) Euclidean space under study.
$\|\cdot\|_{{\mathcal{E}}}$ denotes the canonical norm associated with
${\mathcal{E}}$. For any subset $E\subset{\mathcal{E}}$, the distance function
to this set is denoted by
$\operatorname{dist}_{{\mathcal{E}}}(\cdot,E)=\inf_{{\mathb{x}}\in{\mathcal{E}}}\|\cdot-{\mathb{x}}\|_{{\mathcal{E}}}$.
Bold letters as ${\mathcal{E}}$ 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 ${\mathrm{x}}$ denotes a stochastic scalar variable. Upper-case
letters are used for functions. For a given function
$f:{\mathcal{E}}\longrightarrow{\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{E}}$,
$f(E):=\\{f({\mathb{x}})~{}|~{}{\mathb{x}}\in{\mathcal{E}}\\}$ is the image
under $f$ of $E$. Considering $U$ an open-set of ${\mathcal{E}}$, if $f$ is
differentiable at ${\mathb{x}}\in U$, $\nabla f({\mathcal{E}})$ denotes the
gradient of $f$ at ${\mathb{x}}$. If $f$ is differentiable over
${\mathcal{E}}$, $\operatorname{zer}\nabla f$ corresponds to the set of zeros
of $\nabla f$, i.e., the set of critical/stationary points of $f$.
In regards to a probability space $\left(\Omega,\mathcal{F},P\right)$, we
remind 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 regarding a generic sub sigma-algebra
${\mathcal{G}}\subset{\mathcal{F}}$. Finally, for a process
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ defined on
$(\Omega,{\mathcal{F}},{\mathbb{P}})$, we introduce $\chi^{\infty}$, the set
of accumulation (or cluster) points of sequence
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ (it is here important to note that
$\chi^{\infty}$ is a random variable from $\Omega$ to $2^{{\mathcal{E}}}$, the
set of subsets of ${\mathcal{E}}$).

##  2 Initial investigations

We here introduce our preliminary framework around
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$, the process under study all along
this paper. The goal of the first subsection is to present a relatively
generic assumption, notably of a topological nature, concerning
$\chi^{\infty}$, the set of accumulation points of
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$. We then derive two useful results
grouped under two separate lemmas and the subject of our second subsection.

###  2.1 Main assumption

The following assumption will guide us throughout the remainder of this work.

###### Assumption 2.1

On some probability space $\left(\Omega,{\mathcal{F}},{\mathbb{P}}\right)$ and
for some $V:{\mathcal{E}}\longrightarrow{\mathbb{R}}$, a coercive and
continuous function:

  1. (i)

There exists a subset $\Gamma\subset{\mathcal{E}}$ such that
$|V(\Gamma)|<+\infty$ and $\chi^{\infty}\bigcap\Gamma\neq\emptyset$ almost-
surely.

  2. (ii)

Sequence $(V({\mathbf{x}}_{k})_{k\in{\mathbb{N}}})$ converges almost-surely to
a random variable ${\mathrm{V}}^{\infty}$. In addition,
${\mathrm{V}}^{\infty}$ is finite almost-surely.

With the exception of continuity and coercivity, Assumption 2.1 does not
impose any more conditions on the curvature of function $V$. Moreover,
although the combination of these two conditions provides the existence of a
minimizer for $V$ [5], we will not really make use of such a property for the
main part of our theoretical reasoning. In our context, Assumptions 2.1
finally provides more information on the behaviour verified by
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ and is thus closer to the general
field of stochastic approximation [23]. Of course, the two postulates (i) and
(ii) tend to work in symbiosis in an optimization setting, typically when
$\left(V({\mathbf{x}}_{k})\right)_{k\in{\mathbb{N}}}$ is proving to be an
almost-supermartingale [38] and so also a supermartingale (what it is supposed
to be in the next sections).
As such, while statement (ii) can usually be deduced from an approximation
scheme verifying a descent condition, (i) may appear as more original. The
need for such an assumption actually stems entirely from the stochastic
framework used here, and more specifically from the fact that $\chi^{\infty}$
is a random variable. Here, we actually need all (or at least a ”vast
majority” because almost-surely) of the trajectories
$\chi^{\infty}(\omega)~{}(\omega\in\Omega)$ to share a common characteristic,
namely they intersect the set $\Gamma$ whose image by $V$ is finite. As
mentioned in the introduction, in what follows we want to favour a macroscopic
approach for our proof, rather than one trajectory-by-trajectory based. To
such an extent, the fact that we possess $\Gamma$, as a kind of linking set
between the accumulation points of every trajectory, will enable us to
construct uniformization properties that will allow us to make free of the
$\omega$-variable dependency. It is also important to notice that obtaining a
set $\Gamma$ intersecting $\chi^{\infty}$ almost-surely is relatively natural
for a wide class of problems. As the example 2.2 below highlights, in the case
of stochastic gradient algorithms, there is generally a very close relation
between $\chi^{\infty}$ and the stationary points of the cost function which
offers a serious avenue for the choice of an interesting $\Gamma$ set.

###### Example 2.2

Let us consider $({\mathcal{W}},\left\langle\cdot|\cdot\right\rangle)$ a
finite-dimensional Euclidean space and $F:{\mathcal{W}}\to{\mathbb{R}}$, a
coercive and Lipschitz continuous gradient function we want to minimize. For
the majority of Stochastic Gradient Descent (SGD) schemes encountered and
regarding the noise assumptions they usually consider [25, 11], their
associated descent condition tends to promotes, almost-surely, both the
convergence of $\left(F({\mathbf{w}}_{k})\right)_{k\in{\mathbb{N}}}$ to a
finite limit as well as $\liminf_{k\to+\infty}\|\nabla
F({\mathbf{w}}_{k})\|=0$. We then proceed with the following classic reasoning
which holds almost-surely; the first point combined with the coercivity
directly conducts to the boundedness of
$({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ and so the fact that
$\Upsilon^{\infty}$, the set of $({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$
cluster points is non-empty, then, using this time also the second point and
$\nabla F$ continuity, this finally gives
$\Upsilon^{\infty}\cap\operatorname{zer}\nabla F\neq\emptyset$.
Moreover, in certain cases as such in [39],
$\left(F({\mathbf{w}}_{k})\right)_{k\in{\mathbb{N}}}$ can even be chosen as
the Lyapunov-type process to study with $\Gamma=\operatorname{zer}\nabla F$
and Assumption 2.1 is verified under $|F(\operatorname{zer}\nabla F)|<+\infty$
meaning that $F$ has no stationary point ”at infinity” and finally appears as
a reasonable sufficient condition. In particular, this allows
$\operatorname{zer}\nabla F$ to contain points which are not necessarily
isolated.

###  2.2 Preliminary results

The next two results will guide us throughout the rest of our analysis. The
first one, of analytical nature, provides more indications on the structure of
subset $\Gamma$ verifying Assumption (ii) while its counterpart gives some
properties relative to process $({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$,
frequently encountered but that will be essential later on.

###### Proposition 2.3

Let $f:{\mathcal{E}}\to{\mathbb{R}}$ be a continuous coercive function and $C$
a non-empty subset of ${\mathcal{E}}$ for which $|f(C)|<+\infty$. Then, the
closure of $C$, $\overline{C}$, can be written under a finite union of non-
empty compact sets on which $f$ is constant on each.

Proof. Let us start by proving that $C$ is bounded. If not there exists
$({\mathb{v}}_{k})_{k\in{\mathbb{N}}}$, a sequence of vectors of $C$, for
which
$\|{\mathb{v}}_{k}\|_{{\mathcal{E}}}\underset{k\to+\infty}{\longrightarrow}+\infty$
and coercivity of $f$ basically conducts to
$f({\mathb{v}}_{k})\underset{k\to+\infty}{\longrightarrow}+\infty$ which
contradict the finiteness of $f(C)$.

For better clarity, let us denote $I=|f(C)|$ and
$f(C)=\left\\{f_{1},...,f_{I}\right\\}~{}(f_{1}\neq f_{2}...\neq f_{I})$. From
boundedness of $C$, it follows that $\overline{C}$ is also bounded. Moreover,
since $f(C)$ is finite and $f$ continuous, we also have
$f\left(\overline{C}\right)=f(C)$ and so $\overline{C}\subset
f^{-1}\left(\left\\{f_{1},...,f_{I}\right\\}\right)=\bigcup_{i=1}^{I}f^{-1}\left(\\{f_{i}\\}\right).$

We are thus allowed to write
$\overline{C}=\bigcup_{i=1}^{I}C_{i}\quad\text{where for all
}i\in\\{1,...,I\\}\quad C_{i}=f^{-1}\left(\\{f_{i}\\}\right)\cap\overline{C}.$

Let us now fix $i\in\\{1,...,I\\}$. $\overline{C}$. On first hand,
$f^{-1}\left(\\{f_{i}\\}\right)$ and $\overline{C}$ being closed (the second
one is due to $f$ continuity), their finite intersection $C_{i}$ is also
closed. On the other hand, the boundedness of $\overline{C}$ ensures those of
$C_{i}$. The finite dimension of ${\mathcal{E}}$ giving the compactness of
$C_{i}$. Moreover, due to $f(\overline{C})=\\{f_{1},...,f_{I}\\}$, there
exists ${\mathb{v}}\in\overline{C}$ such that $f({\mathb{v}})=f_{i}$, i.e.
${\mathb{v}}\in f^{-1}\left(\\{f_{i}\\}\right)$ and so $C_{i}$ is non empty.
Finally inclusion $C_{i}\subset f^{-1}\left(\\{f_{i}\\}\right)$ ensures that
$f$ is constant on $C_{i}$ with $f(C_{i})=f_{i}$.

Our next proposition provides some technical results of topological nature.
This gives standard information on the behaviour of $\chi^{\infty}$, the set
of cluster points of $({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ and on
${\mathrm{V}}^{\infty}$, the limit of
$(V({\mathbf{x}}_{k}))_{k\in{\mathbb{N}}}$. The proof we introduce below takes
up the classic arguments, most often encountered in the deterministic setting
as in [2, 9], but which are generalized here, without any great difficulty, to
the stochastic framework.

###### Proposition 2.4

Under Assumption 2.1, we almost-surely have

  1. (i)

$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ bounded,

  2. (ii)

$\chi^{\infty}$ non empty and compact,

  3. (iii)

${\mathrm{V}}^{\infty}\in V(\Gamma)$,

  4. (iv)

$\left(\operatorname{dist}_{{\mathcal{E}}}({\mathbf{x}}_{k},\chi^{\infty})\right)_{k\in{\mathbb{N}}}$
converges to $0$.

Proof. According to Assumption 2.1, there exists a set $\Lambda\subset\Omega$
of probability one such that any $\omega\in\Lambda$ satisfies:

$\displaystyle\lim\limits_{k\rightarrow+\infty}V({\mathbf{x}}_{k}(\omega))<+\infty,$
(2.1a) $\displaystyle\chi^{\infty}(\omega)\bigcap\Gamma\neq\emptyset.$ (2.1b)

Then for all $\omega\in\Omega$;

Similarly with Example 2.2, the boundedness of
$\left({\mathbf{x}}_{k}(\omega)\right)_{k\in{\mathbb{N}}}$ is a direct
consequence of (2.1a) associated with $f$ coercivity. It follows that
statement (i) holds. Since $({\mathbf{x}}_{k}(\omega))_{k\in{\mathbb{N}}}$ is
bounded, in finite dimension, the set of cluster points
$\chi^{\infty}(\omega)$ is non empty, bounded and closed in ${\mathcal{E}}$,
hence compact. Statement (ii) is thus verified.

Let us now prove (iii). Assumption 2.1 (ii) ensures the existence of
${\mathb{x}}_{\infty}\in\Gamma$ and a subsequence
$\left({\mathbf{x}}_{\psi(k)}(\omega)\right)_{k\in{\mathbb{N}}}$ converging to
${\mathb{x}}_{\infty}$. From (2.1a), we have
$V\left({\mathbf{x}}_{\psi(k)}(\omega)\right)\underset{k\to+\infty}{\longrightarrow}{\mathrm{V}}^{\infty}(\omega)$.
Moreover, continuity of $V$ leads to
$V\left({\mathbf{x}}_{\psi(k)}(\omega)\right)\underset{k\to+\infty}{\longrightarrow}V({\mathbf{x}}_{\infty})$.
We thus deduces that
${\mathrm{V}}^{\infty}(\omega)=V({\mathbf{x}}_{\infty})\in V(\Gamma)$.

We now show that statement (iv) holds by contradiction. If not, there exist
$\varepsilon>0$ and a subsequence
$({\mathbf{x}}_{\psi_{1}(k)}(\omega))_{k\in{\mathbb{N}}}$ such that

$(\forall
k\in{\mathbb{N}})\quad\operatorname{dist}_{{\mathcal{E}}}\left({\mathbf{x}}_{\psi_{1}(k)}(\omega),\chi^{\infty}(\omega)\right)>\epsilon.$
(2.2)

Boundedness of $({\mathbf{x}}_{k}(\omega))_{k\in{\mathbb{N}}}$ ensuring those
of $({\mathbf{x}}_{\psi_{1}(k)}(\omega))_{k\in{\mathbb{N}}}$ , the set of
cluster points of $({\mathbf{x}}_{\psi_{1}(k)}(\omega))_{k\in{\mathbb{N}}}$ is
non-empty and basically included in $\chi^{\infty}(\omega)$. Thus, there
exists another subsequence
$({\mathbf{x}}_{(\psi_{1}\circ\psi_{2})(k)}(\omega))_{k\in{\mathbb{N}}}$ and
${\mathb{x}}^{\prime}_{\infty}\in\chi^{\infty}(\omega)$ such that
$\left\|{\mathbf{x}}_{(\psi_{1}\circ\psi_{2})(k)}(\omega)-{\mathb{x}}^{\prime}_{\infty}\right\|_{{\mathcal{E}}}\underset{k\to+\infty}{\longrightarrow}0$.
Hence,
$\operatorname{dist}_{{\mathcal{E}}}\left({\mathbf{x}}_{(\psi_{1}\circ\psi_{2})(k)}(\omega),\chi^{\infty}(\omega)\right)\underset{k\to+\infty}{\longrightarrow}0$,
which contradicts (2.2) and thus concludes the proof.

Among the four previous statements of Proposition 2.4, it is especially (iii)
and (iv) that will be directly useful in what follows. As we will see in our
next section, they will allow us to use the $\Gamma$ set as a technical
cornerstone in the connection between (KL)-property and our stochastic
framework.

##  3 New results derived from Kurdyka-Łojasiewicz (KL) property

This third section can be considered as the central point of all the
theoretical analysis we are conducting in this paper. Here we propose a new
use of the (KL)-property to promote intermediate results that, regarding our
discussion in introduction, can be described as macroscopic in that they
bypass the $\omega$-dependence. This will allow us to propose new results of
asymptotic nature obtained through a strategy of proof that typically differs
from the ODE approach [3], i.e. the best known today. The theory developed
here was initially instigated in [18] and the associated proofs have been
remodelled or at least reformulated with additional details for better
understanding.

###  3.1 The set of concave desingularization functions

This preparatory subsection introduce a specific class of functions which will
be useful to us before introducing the most fundamental concept of this part,
namely the (KL)-property.

For every $\zeta\in(0,+\infty]$, we denote by $\Phi_{\zeta}$ the set of
concave functions $\varphi\colon[0,\zeta)\mapsto\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^{\prime}(s)>0$. In the literature, an
element of $\Phi_{\zeta}$ for a certain $\zeta>0$ is also found under the name
of concave desingularization function [8].

The link between $\Phi_{\zeta}$ (for $\zeta>0$) 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.1

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

Proof. Let $\varphi\in\Phi_{\zeta}$. Since $\varphi^{\prime}$ 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)\leqslant
s\varphi^{\prime}(0)$. Passing to the limit thus gives
$l_{1}\leqslant\zeta\varphi^{\prime}(0)$ and then $l_{1}<+\infty$.

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

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

$(\forall s\geqslant
0)\quad\widetilde{\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}$ (3.1)

$\widetilde{\varphi}$ belongs to $\Phi_{+\infty}$ and is bounded (see figure 1
for a graphical representation).

Figure 1: An graphical representation of the proof of Proposition 3.1.
$\tilde{\varphi}$ (the green curve) is the $C^{1}$ bounded extension of
$\varphi$(the green curve following construction (3.1). We can also notice
that $\tilde{\varphi}$ admits $l_{1}+\zeta l_{2}$ as limits to $+\infty$.

###  3.2 Limitation of the usual (KL) framework

Although the non-smooth version of (KL)-property developped by [7, 2] is now
widely used extensively, particularly in the study of proximal-type algorithms
[9, 19, 22, 33], we here propose to work with its differentiable version in
order to remain closer with the framework we propose in our application
Section 5. However, as we will highlight in section 6, the technical
modifications to achieve similar results in a non-smooth framework are mainly
structural and do not distort the proof strategy developed here. We thus work
with the following definition:

###### Definition 3.2

_[KL Property]_ A differentiable function $f:{\mathcal{E}}\to{\mathbb{R}}$
satisfies the _Kurdyka-Lojasiewicz (KL)-property_ at
$\widetilde{{\mathb{x}}}\in{\mathcal{E}}$, if there exist a neighbourhood $V$
of $\widetilde{{\mathb{x}}}$, $\zeta>0$ and $\varphi\in\Phi_{\zeta}$ such that

$\|\nabla
f({\mathb{x}})\|_{{\mathcal{E}}}~{}\varphi^{\prime}(f({\mathb{x}})-f(\widetilde{{\mathb{x}}}))\geqslant
1,$

for every ${\mathb{x}}\in V$ satisfying
$0<f({\mathb{x}})-f(\widetilde{{\mathb{x}}})<\zeta$.

More specifically, $f$ is said to satisfy the (KL)-property over
$E\subset{\mathcal{E}}$ if the latter is verified at every point of $E$.

As it stands, Definition 3.2 of the (KL)-property remains of local nature;
$\zeta$ and $\varphi$ strictly depend on the point we are located. As a
consequence, this naturally tend to favour a trajectory-by-trajectory approach
to the problem, dealing in a stochastic context, typically in the manner of
[33]. Insofar as we aim to adopt a macroscopic approach instead, the
(KL)-property as such is of little use. To carry out our reasoning, we would
then need to manipulate an inequality similar to that of Definition 3.2 but
under a more global form. Actually, the main reason which has motivated us to
conduct this work relies in a key result bringing some responses to the latter
issue, namely the uniformized (KL)-property of [9]:

###### Theorem 3.3

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

$\|\nabla
f({\mathb{x}})\|_{{\mathcal{E}}}~{}\varphi^{\prime}(f({\mathb{x}})-f(\overline{{\mathb{x}}}))\geqslant
1,$

for all $\overline{{\mathb{x}}}\in C$ and ${\mathb{x}}\in{\mathcal{E}}$
verifying $\operatorname{dist}_{{\mathcal{E}}}({\mathb{x}},C)<\varepsilon$ and
$0<f({\mathb{x}})-f(\overline{{\mathb{x}}})<\zeta$.

Theorem 3.3 is therefore a particularly interesting tool because it attenuates
the excessively local character of the initial (KL)-property. This time, the
dependence of $(\zeta,\varphi)$ is not relative to a singleton, but relaxed on
an infinitely larger set $C$, subject to compactness and with a constant image
by the function under study. Even better, the $\epsilon$ variable, unlike the
notion of neighbourhood which is much vaguer when we reason locally, gives an
explicit quantification of the global behaviour of the newly obtained
property. In addition to its appearance article [9], let us also mentioned
that Theorem 3.3 has been used next in various works as those of [20, 14] in
the deterministic setting.

Set $C$ relative to Theorem 3.3 and $\Gamma$ from Assumption 2.1 have in
common that they are partially characterized by their image by the respective
function to which they are associated. Because of this proximity, it seems
desirable to apply Theorem 3.3 to the function $V$, assuming that the latter
verifies the (KL)-property (at least on $\Gamma$). However, Theorem 3.3 turns
out to be a little too restrictive here in that it requires for $\Gamma$ not
only to have a finite image by $F$ but even for the latter to be reduced to a
singleton which remains a limitation for our initial approach. $\Gamma$
serving as a link between all trajectories
$\chi^{\infty}(\omega)~{}~{}(\omega\in\Omega)$, this actually supposes that
the image sets $V(\chi^{\infty}(\omega))$ are themselves all reduced to a
common singleton (i.e. independant from $\omega$-variable). Such a scenario is
all the more difficult to envisage as we are working here in a non-convex
context. As it stands, the uniformized (KL)-property can be applied to
$\chi^{\infty}(\omega)$, but if so parameters $\zeta,\epsilon$ as well as the
desingularizing function $\varphi$ become dependant on $\omega$ which, in this
case, suggests using once again a trajectory-by-trajectory reasoning method.
In other words, for our macroscopic approach to work, it becomes necessary to
build a new version of Theorem 3.3 taking account of two requirements; the
image of $C$ by the function under study shall not be constant anymore and
despite the stochasticity $\zeta,\epsilon,\varphi$ shall remain deterministic.
In particular, the question of getting around the $\omega$-dependence of these
three parameters has already been considered in [22]. More specifically, their
authors proposed a version in expectation of Theorem 3.3 taking a
desingularization function $\varphi$ directly derived from the assumed mini-
batch structure of their noise. In our case, the construction of a new version
of the uniformized (KL)-property that meets our two requirements is carried
out in two stages, which are the topic of our next two subsections.

###  3.3 Extension of the uniformized KL property

This third subsection corresponds to the first stage of extension of Theorem
3.3. We here seek to relax the initial constraint on $C$ having only a single
point as its image by the function under study. For this stage, we remain in a
deterministic framework. More precisely, the result we present was introduced
for the first time in our previous article [18] and can be seen as a
generalized version of the uniformized (KL)-property where this time $C$ can
be taken as a finite union of compact sets where the function under study is
only constant on each. This result in a new theorem which can be seen roughly
as a combination of the uniform (KL)-property and [7, Corollary 11] but
regarding a more generic set $C$.

###### Theorem 3.4

_[Extended uniformized (KL)-property]_ Let $C=\bigcup_{i=1}^{I}C_{i}$ be a
union of $I\in{\mathbb{N}}_{*}$ non-empty compact subsets $(C_{i})_{1\leqslant
i\leqslant I}$ of ${\mathcal{E}}$, and
$f\colon{\mathcal{E}}\rightarrow{\mathbb{R}}$ be a differentiable function
satisfying the KL property on $C$. We also suppose that $f$ is constant on
every $C_{i}~{}(1\leqslant i\leqslant I)$, with $\left\\{f_{i}\right\\}$ as
associated image by $f$. Then, there exist
$(\varepsilon,\zeta)\in(0,+\infty)^{2}$ and $\varphi\in\Phi_{\zeta}$ such that

$\|\nabla
f({\mathb{x}})\|_{{\mathcal{E}}}~{}\varphi^{\prime}(f({\mathb{x}})-f_{i})\geqslant
1$

for all $i\in\\{1,\ldots,I\\}$ and ${\mathb{x}}\in{\mathcal{E}}$ verifying
$\operatorname{dist}_{{\mathcal{E}}}({\mathb{x}},C)<\varepsilon$ and
$0<f({\mathb{x}})-f_{i}<\zeta$.

Proof. Without loss of generality (grouping together $C_{i},C_{j}~{}~{}i\neq
j$ if $f_{i}=f_{j}$) we can assume $f_{1}\neq\cdots\neq f_{I}$.

We first apply the uniform KL property to $C_{1},\ldots,C_{I}$. For every
$i\in\\{1,\ldots,I\\}$, there exist
$(\varepsilon_{i},\zeta_{i})\in(0,+\infty)^{2}$ and
$\varphi_{i}\in\Phi_{\zeta_{i}}$ such that every ${\mathb{x}}\in{\mathcal{E}}$
verifying
$\operatorname{dist}_{{\mathcal{E}}}({\mathb{x}},C_{i})<\varepsilon_{i}$ and
$0<f({\mathb{x}})-f_{i}<\zeta_{i}$ also satisfies

$\|\nabla
f({\mathb{x}})\|_{{\mathcal{E}}}~{}\varphi_{i}^{\prime}(f({\mathb{x}})-f_{i})\geqslant
1.$ (3.2)

Let us consider $\widetilde{\zeta}=\eta\min\limits_{j\neq i}|f_{i}-f_{j}|$
with $\eta\in]0,1/2[$. From $f_{1}\neq\cdots\neq f_{I}$, minoration
$\widetilde{\zeta}>0$ basically holds. In addition, from $f$ continuity and
for every $i\in\\{1,\ldots,I\\}$, there exists an attached
$\widetilde{\varepsilon}_{i}\in]0,\varepsilon_{i}[$ so that every
${\mathb{x}}$ verifying
$\operatorname{dist}_{{\mathcal{E}}}({\mathb{x}},C_{i})<\widetilde{\varepsilon}_{i}$
also satisfies

$|f({\mathb{x}})-f_{i}|<\widetilde{\zeta}.$ (3.3)

Let $\delta\in]0,1[$ and $\varepsilon=\delta\min\limits_{1\leqslant i\leqslant
I}\widetilde{\varepsilon}_{i}$ in a way to have

$\left\\{{\mathb{v}}\in{\mathcal{E}}\,\mid\,\operatorname{dist}_{{\mathcal{E}}}({\mathb{v}},C)<\varepsilon\right\\}\subset\bigcup_{i=1}^{I}\left\\{{\mathb{v}}\in{\mathcal{E}}\,\mid\,\operatorname{dist}_{{\mathcal{E}}}({\mathb{v}},C_{i})<\widetilde{\varepsilon}_{i}\right\\}.$
(3.4)

The rest of the proof consist in showing that the property of the theorem
holds for $\varepsilon$ as defined above,
$\zeta=\min(\zeta_{1},\ldots\zeta_{I},\widetilde{\zeta})$ and
$\varphi=\sum_{i=1}^{I}\varphi_{i}\in\Phi_{\zeta}$.

To do so, let ${\mathb{x}}\in{\mathcal{E}}$ and $i\in\\{1,\ldots,I\\}$ be such
that $\operatorname{dist}_{{\mathcal{E}}}({\mathb{x}},C)<\varepsilon$ and
$0<f({\mathb{x}})-f_{i}<\zeta$.

For every $j\in\\{1,\ldots,I\\}\setminus\\{i\\}$, since
$\zeta\leqslant\widetilde{\zeta}$, using the definition of
$\widetilde{\zeta}$, we have
$0<|f({\mathb{x}})-f_{i}|\leqslant\eta|f_{i}-f_{j}|$. With $v\in]0,1/2[$, we
thus deduce that

$\displaystyle|f({\mathb{x}})-f_{j}|$
$\displaystyle=|(f({\mathb{x}})-f_{i})+(f_{i}-f_{j})|$
$\displaystyle\geqslant\left|~{}|f_{i}-f_{j}|-|f({\mathb{x}})-f_{i}|~{}\right|$
$\displaystyle=|f_{i}-f_{j}|-|f({\mathb{x}})-f_{i}|$
$\displaystyle\geqslant(1-\eta)|f_{i}-f_{j}|$
$\displaystyle>\eta|f_{i}-f_{j}|$ $\displaystyle\geqslant\widetilde{\zeta}.$
(3.5)

The continuity property of $f$ (3.3) being contradicted otherwise, relation
(3.3) implies that
$\operatorname{dist}_{{\mathcal{E}}}({\mathb{x}},C_{j})\geqslant\widetilde{\varepsilon_{j}}$.
So, as $\operatorname{dist}_{{\mathcal{E}}}({\mathb{x}},C)<\varepsilon$ and
given inclusion (3.4), ${\mathb{x}}$ finally belongs to

$\displaystyle\bigcup_{j=1}^{I}\left\\{{\mathb{v}}\in{\mathcal{E}}\,\mid\,\operatorname{dist}_{{\mathcal{E}}}({\mathb{v}},C_{j})<\widetilde{\varepsilon}_{j}\right\\}\setminus\left(\bigcup_{j\neq
i}\left\\{{\mathb{v}}\in{\mathcal{E}}\,\mid\,\operatorname{dist}_{{\mathcal{E}}}({\mathb{v}},C_{j})<\widetilde{\varepsilon}_{j}\right\\}\right)$
$\displaystyle=\left\\{{\mathb{v}}\in{\mathcal{E}}\,\mid\,\operatorname{dist}_{{\mathcal{E}}}({\mathb{v}},C_{i})<\widetilde{\varepsilon}_{i}\right\\}.$
(3.6)

Keeping in mind that $\varepsilon_{i}>\widetilde{\varepsilon}_{i}$ and
$\operatorname{dist}_{{\mathcal{E}}}({\mathb{x}},C_{i})<\varepsilon_{i}$
holds. At last, since $\zeta\leqslant\zeta_{i}$, we also have
$0<f({\mathb{x}})-f_{i}<\zeta_{i}$ and the uniformized (KL)-property at
$C_{i}$ conducts to

$\displaystyle\|\nabla
f({\mathb{x}})\|_{{\mathcal{E}}}~{}\varphi^{\prime}(f({\mathb{x}})-f_{i})$
$\displaystyle=\|\nabla
f({\mathb{x}})\|_{{\mathcal{E}}}\sum_{j=1}^{I}\varphi_{j}^{\prime}(f({\mathb{x}})-f_{i})$
$\displaystyle\geqslant\|\nabla
f({\mathb{x}})\|_{{\mathcal{E}}}~{}\varphi_{i}^{\prime}(f({\mathb{x}})-f_{i})\geqslant
1,$ (3.7)

where the first inequality basically comes from positivity of
$\varphi_{1}^{\prime},...,\varphi_{I}^{\prime}$. This completes the proof.

This extended version of the uniformized (KL)-property is particularly
interesting in our context because it bridges the gap with our $\Gamma$ set.
Since $|V(\Gamma)|<+\infty$, Proposition 2.3 in fact guarantees for the latter
that its closure $\overline{\Gamma}$ can be written under the form required to
apply Theorem 3.4. This new theorem is therefore a step forward in our
approach but is still not enough to deal with our stochastic setting. The main
limitation relying on the fact that the distance of
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ to $\overline{\Gamma}$ does not
necessarily converge to zero almost-surely. Proposition 2.4(iv) ensures that
this is the case but only with $\chi^{\infty}$ which is $\omega$-dependant.
However, because of the assumed link between $\Gamma$ and $\chi^{\infty}$,
such an avenue of work is invaluable for what follows.

###  3.4 An alternative KL property to deal with stochastic setting

This subsection is dedicated to the introduction our final derived result from
the (KL)-property we will use to conduct the rest of our analysis. Given what
we established, this result will be more precisely derived from Theorem 3.4.
Here we return to our initial stochastic framework and, as we pointed out in
subsection 3.2, we seek to construct a property of macroscopic nature by
masking the $\omega$-dependence of the (KL)-parameters involved. In our last
discussion in subsection 3.3, we have already given some hints about the set
$C$ to consider. More precisely, we first need to take an intermediate set
which has to be large enough to take into account the information carried by
accumulation points of all trajectories, ensuring $\omega$-independence at the
time. Second, such a set also has to share the same topological structure as
$\Gamma$ in order to be able to apply Proposition 2.3. By following such a
strategy, we are able to obtain the following result.

###### Proposition 3.5

Assume that Assumption 2.1 holds and that the attached function $V$ is
differentiable and verifies the (KL)- property (over ${\mathcal{E}}$). Then,
there exist a bounded function $\varphi\in\Phi_{+\infty}$ and a discrete
random variable ${\mathrm{K}}$ such that, almost-surely over the set
$\Pi_{V}:=\liminf\limits_{k\to+\infty}\left\\{V({\mathbf{x}}_{k})>{\mathrm{V}}^{\infty}\right\\}$,
${\mathrm{K}}$ is finite and for every $k>{\mathrm{K}}$

$\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}~{}\varphi^{\prime}(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})\geqslant
1.$

Proof. Let us introduce event

$\Theta:=\Big{\\{}V({\mathbf{x}}_{k})\underset{k\to+\infty}{\to}{\mathrm{V}}^{\infty}\Big{\\}}\bigcap\Big{\\{}{\mathrm{V}}^{\infty}\in
V(\Gamma)\Big{\\}}\bigcap\Big{\\{}\operatorname{dist}_{{\mathcal{E}}}({\mathbf{x}}_{k},\chi^{\infty})\underset{k\to+\infty}{\to}0\Big{\\}},$
(3.8)

as well as the (deterministic) subset of ${\mathcal{E}}$

$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\mathcal{C}}:=\bigcup_{\omega\in\Theta\cap\Pi_{V}}\chi^{\infty}(\omega).$
(3.9)

In particular, its image by $V$ verifies

$\displaystyle
V({\mathcal{C}})=V\left(\bigcup_{\omega\in\Theta\cap\Pi_{V}}\chi^{\infty}(\omega)\right)=\bigcup_{\omega\in\Theta\cap\Pi_{V}}V\left(\chi^{\infty}(\omega)\right)$
$\displaystyle=\bigcup_{\omega\in\Theta\cap\Pi_{V}}\left\\{{\mathrm{V}}^{\infty}(\omega)\right\\}$
$\displaystyle\subset\bigcup_{\omega\in\Theta\cap\Pi_{V}}V(\Gamma)=V(\Gamma).$
(3.10)

Since $|V(\Gamma)|<+\infty$, it follows that $|V({\mathcal{C}})|<+\infty$ and
Proposition 2.3 then ensures that its closure $\overline{{\mathcal{C}}}$ can
be written a finite union of non-empty compacts on which $V$ is constant on.
Since $V$ satisfies the (KL)-property, we can apply Theorem 3.4 considering
$f=V$ and $C=\overline{{\mathcal{C}}}$. As a consequence and denoting
$I=|V({\mathcal{C}})|$ and
$V({\mathcal{C}})=\\{V_{1},...,V_{I}\\}~{}(V_{1}\neq V_{2}...\neq V_{I})$
there exist $\varepsilon_{\mathcal{C}}>0$, $\zeta_{\mathcal{C}}>0$ and
$\varphi_{\mathcal{C}}\in\Phi_{\zeta_{\mathcal{C}}}$, such that, for every
${\mathb{x}}\in{\mathcal{E}}$ and $i\in I$ satisfying
$\operatorname{dist}_{{\mathcal{E}}}({\mathb{x}},\overline{{\mathcal{C}}})<\varepsilon_{{\mathcal{C}}}$
and $0<V({\mathb{x}})-V_{i}<\zeta_{\mathcal{C}}$,

$\|\nabla
V({\mathb{x}})\|_{{\mathcal{E}}}~{}\varphi_{\mathcal{C}}^{\prime}(V({\mathb{x}})-V_{i})\geqslant
1.$ (3.11)

According to Proposition 3.1, $\varphi_{\mathcal{C}}$ has a bounded extension
$\widetilde{\varphi}_{\mathcal{C}}$ belonging to $\Phi_{+\infty}$. Then,
$\widetilde{\varphi}_{\mathcal{C}}$ also satisfies, for any
${\mathb{x}}\in{\mathcal{E}}$ and $i\in I$ such that
$\operatorname{dist}_{{\mathcal{E}}}({\mathb{x}},\overline{{\mathcal{C}}})<\varepsilon_{\mathcal{C}}$
and $0<V({\mathb{x}})-V_{i}<\zeta_{\mathcal{C}}$,

$\|\nabla
V({\mathb{x}})\|_{{\mathcal{E}}}~{}\widetilde{\varphi}_{\mathcal{C}}^{\prime}(V({\mathb{x}})-V_{i})\geqslant
1.$ (3.12)

Considering this, we now define the positive discrete random variable

${\mathrm{K}}=\min\left\\{l>0\,\mid\,(\forall p\geqslant
l)\;\operatorname{dist}_{{\mathcal{E}}}({\mathbf{x}}_{p},\overline{{\mathcal{C}}})\leqslant\varepsilon_{\mathcal{C}}\text{
and
}0<V({\mathbf{x}}_{p})-{\mathrm{V}}^{\infty}<\zeta_{\mathcal{C}}\right\\}.$
(3.13)

According to Assumption 2.1 (i) and proposition 2.4 (iv), the latter is finite
over $\Theta\cap\Pi_{V}$. In addition, for every $\omega\in\Theta\cap\Pi_{V}$,
since ${\mathrm{V}}^{\infty}(\omega)\in
V({\mathcal{C}})=\\{V_{1},...,V_{I}\\}$, there exists a unique $i_{\omega}\in
I$ such that ${\mathrm{V}}_{\infty}(\omega)=V_{i_{\omega}}$. As a consequence,
(3.12) finally leads to

$(\forall\omega\in\Theta\cap\Pi_{V})\quad(\forall
k>{\mathrm{K}}(w))\quad\|\nabla
V({\mathb{x}}(\omega))\|_{{\mathcal{E}}}~{}\widetilde{\varphi}_{\mathcal{C}}^{\prime}\left(V({\mathbf{x}}_{k}(\omega))-{\mathrm{V}}^{\infty}(\omega)\right)\geqslant
1.$ (3.14)

Assumption 2.1, and Proposition 2.4 guaranteeing that
${\mathbb{P}}(\Theta)=1$, this leads to
${\mathbb{P}}(\Theta\cap\Pi_{V})=P(\Pi_{V})$ and so concludes the proof.

In a nutshell, the previous proof simply consists in applying Theorem 3.4 to
${\mathcal{C}}$ as defined in (3.9) which here plays the role of the
”intermediary” set fulfilling the two conditions mentioned previously. The
latter set being deterministic, so its attached (KL)-parameters are and thus
the $\omega$-dependence is alleviate which will make much easier the reasoning
we present in the next subsection.

##  4 Asymptotic analysis

This section is devoted to the implementation of our macroscopic theoretical
approach, for which we use the main result of our last section, namely the
Proposition 3.5 combined with a probabilistic reasoning of conditional/in
expectation order. However, we place ourselves in a slightly less generic
setting than those induced by Assumption 2.1 insofar as we adopt, as announced
in the introduction, a context of supermartingale convergence. This is
described in more details through a new assumption we introduce below.

###### Assumption 4.1

Process $(V({\mathbf{x}}_{k}))_{k\in{\mathbb{N}}}$ is a
${\mathcal{F}}_{k}$-supermartingale on some probability space
$\left(\Omega,{\mathcal{F}},{\mathbb{P}}\right)$, for some filtration
$({\mathcal{F}}_{k})_{k\in{\mathbb{N}}}$ and a certain coercive continuous
function $V:{\mathcal{E}}\longrightarrow{\mathbb{R}}$.

We introduce, in a first subsection, a technical result playing the role of a
structural basement for our main asymptotical convergence theorem, presented
in a second phase.

###  4.1 A useful technical lemma

The main result of this subsection is the following.

###### Lemma 4.2

Under Assumption 4.1,

  1. (i)

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

  2. (ii)

Moreover, if for all $k\in{\mathbb{N}}$, one of the two situations occurs
almost-surely
$V({\mathbf{x}}_{k})\geqslant{\mathbb{E}}[{\mathrm{V}}^{\infty}|{\mathcal{F}}_{k}]>{\mathrm{V}}^{\infty}$
or
$V({\mathbf{x}}_{k})>{\mathbb{E}}[{\mathrm{V}}^{\infty}|{\mathcal{F}}_{k}]\geqslant{\mathrm{V}}^{\infty}$,
then for any function $\varphi\in\Phi_{+\infty}$

$\displaystyle
E[{\mathrm{X}}_{\varphi}]\leqslant{\mathbb{E}}[\varphi(V({\mathbf{x}}_{0})-{\mathrm{V}}^{\infty})],$
(4.1)
$\displaystyle\text{where}\quad{\mathrm{X}}_{\varphi}:=\sum_{k=0}^{+\infty}\varphi^{\prime}\left(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty}\right)\left(V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]\right).$
(4.2)

Proof. Since $V$ is lower-bounded as a coercive and continuous function, (i)
holds as a direct consequence of the Doob’s convergence theorem [44].

To prove (ii), let us start by fixing $k\in{\mathbb{N}}$. Given the assumption
$V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty}$ is positive while
${\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}])-{\mathrm{V}}^{\infty}$
and
$V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}])$
are non-negative and thus, the three quantities
$\varphi(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty}),~{}\varphi({\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}])-{\mathrm{V}}^{\infty})$
and $\varphi^{\prime}(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})$ are
correctly defined. The concavity of $\varphi$ then leads to:

$\displaystyle\varphi(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})-\varphi({\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}])-{\mathrm{V}}^{\infty})$
$\displaystyle\geqslant\varphi^{\prime}(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})\left(V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]\right)~{}~{}\text{a.s.}.$
(4.3)

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

${\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]-{\mathrm{V}}^{\infty}\geqslant{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]-{\mathbb{E}}[{\mathrm{V}}^{\infty}|{\mathcal{F}}_{k}]={\mathbb{E}}[V({\mathbf{x}}_{k+1})-{\mathrm{V}}^{\infty}|{\mathcal{F}}_{k}]\geqslant
0~{}~{}\text{a.s.}.$ (4.4)

Then, we can compose by $\varphi$ in (4.4) and since the latter is increasing:

$\varphi\left({\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]-{\mathrm{V}}^{\infty}\right)\geqslant\varphi\left({\mathbb{E}}[V({\mathbf{x}}_{k+1})-{\mathrm{V}}^{\infty}|{\mathcal{F}}_{k}]\right)~{}~{}\text{a.s.}.$
(4.5)

Moreover, due to Jensen’s inequality:

$\varphi\left({\mathbb{E}}[V({\mathbf{x}}_{k+1})-{\mathrm{V}}^{\infty}|{\mathcal{F}}_{k}]\right)\geqslant{\mathbb{E}}\left[\varphi\left(V({\mathbf{x}}_{k+1})-{\mathrm{V}}^{\infty}\right)|{\mathcal{F}}_{k}\right]~{}~{}\text{a.s.}.$
(4.6)

And so

$\varphi\left({\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]-{\mathrm{V}}^{\infty}\right)\geqslant{\mathbb{E}}\left[\varphi\left(V({\mathbf{x}}_{k+1})-{\mathrm{V}}^{\infty}\right)|{\mathcal{F}}_{k}\right]~{}~{}\text{a.s.}.$
(4.7)

Injecting (4.7) in (4.1) gives:

$\displaystyle\varphi(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})-{\mathbb{E}}\left[\varphi\left(V({\mathbf{x}}_{k+1})-{\mathrm{V}}^{\infty}\right)|{\mathcal{F}}_{k}\right]$
$\displaystyle\geqslant\varphi^{\prime}(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})\left(V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]\right)~{}~{}\text{a.s.}.$
(4.8)

The two terms involved in (4.1) being non-negative, we are allowed to pass to
expectation operator. Moreover, the fact that $\varphi$ is bounded ensures we
can use its linearity on the right term:

$\displaystyle{\mathbb{E}}\left[\varphi(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})\right]-{\mathbb{E}}\left[\varphi(V({\mathbf{x}}_{k+1})-{\mathrm{V}}^{\infty})\right]$
$\displaystyle\geqslant{\mathbb{E}}\left[\varphi^{\prime}(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})\left(V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]\right)\right]~{}~{}\text{a.s.}.$
(4.9)

To the extent that (4.1) for a generic $k\in{\mathbb{N}}$, we can some the
latter inequality on ${\mathbb{N}}$:

$\displaystyle\sum_{k=0}^{+\infty}\left({\mathbb{E}}\left[\varphi(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})\right]-{\mathbb{E}}\left[\varphi(V({\mathbf{x}}_{k+1})-{\mathrm{V}}^{\infty})\right]\right)$
$\displaystyle\geqslant\sum_{k=0}^{+\infty}{\mathbb{E}}\left[\varphi^{\prime}(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})\left(V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]\right)\right]$
$\displaystyle={\mathbb{E}}\left[\sum_{k=0}^{+\infty}\varphi^{\prime}(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})\left(V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]\right)\right],$
(4.10)

the positivity of all the terms in the middle sum ($\varphi^{\prime}\geqslant
0$) making legal the last equality . Finally, as usual telescopic sum with
$V({\mathbf{x}}_{k})\underset{k\to+\infty}{\longrightarrow}{{\mathrm{V}}^{\infty}}$
almost-surely, we obtain:

$\displaystyle\sum_{k=0}^{+\infty}\left({\mathbb{E}}\left[\varphi(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})\right]-{\mathbb{E}}\left[\varphi(V({\mathbf{x}}_{k+1})-{\mathrm{V}}^{\infty})\right]\right)$
$\displaystyle={\mathbb{E}}\left[\varphi(V({\mathbf{x}}_{0})-{\mathrm{V}}^{\infty})\right]-{\mathbb{E}}\left[\varphi({\mathrm{V}}^{\infty}-{\mathrm{V}}^{\infty})\right]$
$\displaystyle={\mathbb{E}}\left[\varphi(V({\mathbf{x}}_{0})-{\mathrm{V}}^{\infty})\right].$
(4.11)

As a consequence, the replacement of (4.1) in (4.1) gives the conclusion i.e.

${\mathbb{E}}\left[\varphi(V({\mathbf{x}}_{0})-{\mathrm{V}}^{\infty})\right]\geqslant{\mathbb{E}}\left[\sum_{k=0}^{+\infty}\varphi^{\prime}(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty})\left(V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]\right)\right]={\mathbb{E}}[{\mathrm{X}}_{\varphi}].$
(4.12)

Although the condition to verify (4.1)+(4.2) may appear as quite technical, it
remains favourable in a supermartingale context. As an easy consequence of
Fatou’s lemma, we always have almost-surely and for any $k\in{\mathbb{N}}\quad
V({\mathbf{x}}_{k})\geqslant{\mathbb{E}}[{\mathrm{V}}^{\infty}|{\mathcal{F}}_{k}]$.
An additional relation of the type
${\mathbb{E}}[{\mathrm{V}}^{\infty}|{\mathcal{F}}_{k}]\geqslant{\mathrm{V}}^{\infty}$
almost-surely for all $k\in{\mathbb{N}}$ indicates that the estimation of
${\mathrm{V}}^{\infty}$ regarding the past events between states $0$ and $k$
remains ”optimistic”.

###  4.2 Main result

Combining Lemma 4.2 with Proposition (3.5), we can now exhibit our main
convergence theorem which is stated as follows.

###### Theorem 4.3

Assume that Assumptions 2.1(i), 4.1 are verified for a same probability space
$(\Omega,{\mathcal{F}},{\mathbb{P}})$, a same filtration
$({\mathcal{F}}_{k})_{k\in{\mathbb{N}}}$ and a same coercive and
differentiable function $V:{\mathcal{E}}\mapsto{\mathbb{R}}$.

  1. (i)

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

  2. (ii)

Moreover, suppose that $V$ satisfies the (KL)-property (over ${\mathcal{E}})$
and that, for all $k\in{\mathbb{N}}$, one of the two situations occurs almost-
surely
$\left(V({\mathbf{x}}_{k})\geqslant{\mathbb{E}}[{\mathrm{V}}^{\infty}|{\mathcal{F}}_{k}]>{\mathrm{V}}^{\infty},~{}\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}>0\right)$ or
$\left(V({\mathbf{x}}_{k})>{\mathbb{E}}[{\mathrm{V}}^{\infty}|{\mathcal{F}}_{k}]\geqslant{\mathrm{V}}^{\infty},\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}>0\right)$.
Then, there exists $\varphi\in\Phi_{+\infty}$ and an almost-sure finite random
variable ${\mathrm{K}}$ so that the following inequality holds:

${\mathbb{E}}\left[{\mathrm{D}}\right]\leqslant{\mathbb{E}}\left[\varphi(V({\mathbf{x}}_{0})-{\mathrm{V}}^{\infty})\right]\text{
where
}{\mathrm{D}}:=\sum_{k={\mathrm{K}}+1}^{+\infty}\frac{V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]}{\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}}.$ (4.13)

Proof. Fact (i) has already been proven (see Lemma 4.2).

Let us now show (ii). In such a case, $\Pi_{V}$ (as defined in Proposition
3.5) is a probability-one set and thus Proposition 3.5 ensures the existence
of $\varphi\in\Phi_{+\infty}$ and an almost-sure finite random variable
${\mathrm{K}}$ so that:

$(\forall k\geqslant{\mathrm{K}})\quad\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}~{}\varphi^{\prime}\left(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty}\right)\geqslant
1~{}~{}\text{a.s.}.$ (4.14)

Then variable ${\mathrm{X}}_{\varphi}$ so as defined in Lemma 4.2 can be
lower-bounded as:

$\displaystyle{\mathrm{X}}_{\varphi}$
$\displaystyle=\sum_{k=0}^{{\mathrm{K}}}\varphi^{\prime}\left(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty}\right)\left(V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]\right)$
$\displaystyle~{}~{}~{}+\sum_{k={\mathrm{K}}+1}^{+\infty}\varphi^{\prime}\left(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty}\right)\left(V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]\right)$
$\displaystyle\geqslant\sum_{k=0}^{K}\varphi^{\prime}\left(V({\mathbf{x}}_{k})-{\mathrm{V}}^{\infty}\right)\left(V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]\right)$
$\displaystyle~{}~{}~{}+\sum_{k={\mathrm{K}}+1}^{+\infty}\frac{V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]}{\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}}$
$\displaystyle\geqslant\sum_{k={\mathrm{K}}+1}^{+\infty}\frac{V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]}{\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}}~{}~{}\text{a.s.}.$ (4.15)

Passing to the expectation (all quantities involved are positives almost-
surely) and the use of Lemma 4.2 finally gives:

${\mathbb{E}}\left[\sum_{k={\mathrm{K}}+1}^{+\infty}\frac{V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]}{\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}}\right]\leqslant{\mathbb{E}}[{\mathrm{X}}_{\varphi}]\leqslant{\mathbb{E}}\left[\varphi(V({\mathbf{x}}_{0})-{\mathrm{V}}^{\infty})\right],$
(4.16)

which ends the proof.

Theorem 4.3 thus provides the existence of an upper-bound for the expectation
of specific variable ${\mathrm{D}}$ which can interpreted as follow; in mean,
it is expected for
$V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]$
i.e. the residual of the descent condition to be ”very small” compare with
those of $\|V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}$ from a certain rank. In
regards, with all the previous works in the deterministic setting [2, 19, 17],
it is finally not surprising that the upper-bound obtained directly depends on
the desingularization function $\varphi$. In the stochastic case, the
additional intervention of a variable ${\mathrm{K}}$ playing a role similar to
a stopping time 111However, ${\mathrm{K}}$ it is not a stopping time in the
purely mathematical sense insofar as, as seen in the proof of Proposition 3.5,
it involves the variable ${\mathrm{V}}^{\infty}$ which is not
${\mathcal{F}}_{k}$-measurable does not appear to be inconsistent either in
the image of [41, Theorem 2.2].

We finally end this section by a useful corollary which generally possesses an
easier interpretation of Theorem 4.3 in practise.

###### Corollary 4.4

Under Assumptions of Theorem 4.3 (ii), 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{E}}}}<+\infty~{}~{}\mathrm{a.s.}.$ (4.17)

Proof. According to Theorem 4.3, there exists an almost sure finite random
variable ${\mathrm{K}}$ such that

${\mathbb{E}}\left[\sum\limits_{k={\mathrm{K}}+1}^{+\infty}\frac{V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]}{\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}}\right]<+\infty\text{ and thus
}\sum\limits_{k={\mathrm{K}}+1}^{+\infty}\frac{V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]}{\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}}<+\infty~{}~{}\mathrm{a.s.}.$

Then, on event $\\{{\mathrm{K}}<+\infty\\}$, of probability one, we have

$\displaystyle\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{E}}}}$
$\displaystyle=\sum_{k=0}^{{\mathrm{K}}}\frac{V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]}{\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}}+\sum_{k={\mathrm{K}}+1}^{+\infty}\frac{V({\mathbf{x}}_{k})-{\mathbb{E}}[V({\mathbf{x}}_{k+1})|{\mathcal{F}}_{k}]}{\|\nabla
V({\mathbf{x}}_{k})\|_{{\mathcal{E}}}}<+\infty~{}~{}\mathrm{a.s.}.$ (4.18)

This concludes the proof.

##  5 New results on the asymptotical behaviour of SGD

The goal of this section is to provide an example for which Theorem 4.3, or
even its direct Corollary 4.4, are able to provide new asymptotical guarantees
for a given stochastic approximation scheme. We here place in a differentiable
optimization context where the scheme under study corresponds to a
preconditioned version of the stochastic gradient descent of [25] and thus is
a litle bit more general. The key point of our analysis is to find a finite-
dimensional Euclidean space ${\mathcal{E}}$, a process
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ and a Lyapunov-type function
$L:{\mathcal{E}}\to{\mathbb{R}}$ attached to the problem that are sufficiently
relevant to be able to carry out convergence analyses that are more advanced
than in the classic non-convex framework.

###  5.1 Setting and assumptions

The problem under consideration in this section consists of finding a solution
to

$\underset{{\mathbf{w}}\in{\mathcal{W}}}{\text{minimize}}\quad
F({\mathbf{w}}),$ (5.1)

where $F:{\mathcal{W}}\rightarrow{\mathbb{R}}$ is a continuously
differentiable function defined on
$\left({\mathcal{W}},\left\langle\cdot|\cdot\right\rangle\right)$, a finite-
dimensional Euclidean space. In a way to solve (5.1) we consider a generic
stochastic gradient descent scheme (SGD) of the form of

$(\forall
k\in{\mathbb{N}})\quad{\mathbf{w}}_{k+1}={\mathbf{w}}_{k}-\alpha_{k}{\mathbf{B}}_{k}{\mathbf{g}}_{k}$
(5.2)

where $(\alpha_{k})_{k\in{\mathbb{N}}}\in(0,+\infty)^{{\mathbb{N}}}$
classically corresponds to a stepsize while
$({\mathbf{g}}_{k})_{k\in{\mathbb{N}}}$ is a process of directions lying in
${\mathcal{W}}$ supposed to ”approximate” the ”true” gradient $\left(\nabla
F({\mathbf{w}}_{k})\right)_{k\in{\mathbb{N}}}$ in some mathematical sense. We
also incorporate $({\mathbf{B}}_{k})_{k\in{\mathbb{N}}}$, a process of linear
operators defined on ${\mathcal{W}}$ in a way to work in a litle bit more
general context. As such and without any other assumption, scheme (5.2)
encompasses the most usual second order methods of SGD [11] and notably, for
the non-convex setting, some Newton/Quasi-Newton versions as those of [34,
43].

We place ourselves in a probabilistic space
$(\Omega,{\mathcal{F}},{\mathbb{P}})$ that we provide with the canonical
filtration ${\mathcal{F}}_{0}=\\{\emptyset,\Omega\\}$ and for all $k\geqslant
1~{}{\mathcal{F}}_{k}=\sigma({\mathbf{g}}_{0},{\mathbf{w}}_{1},...,{\mathbf{g}}_{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. (i)

$F$ is coercive, differentiable and $\beta$-Lipschitz gradient i.e.

$(\forall{\mathb{w}},{\mathb{w}}^{\prime}\in{\mathcal{W}})\quad\|\nabla
F({\mathb{w}})-\nabla
F({\mathb{w}}^{\prime})\|\leqslant\beta\|{\mathb{w}}-{\mathb{w}}^{\prime}\|.$

  2. (ii)

The image of $\operatorname{zer}\nabla F$ by $F$ satisfies
$|F(\operatorname{zer}\nabla F)|<+\infty$.

  3. (iii)

Process $({\mathbf{B}}_{k})_{k\in{\mathbb{N}}}$ is
${\mathcal{F}}_{k}$-measurable and there exists
$\underline{\nu},\overline{\nu}>0$ such that:

$(\forall
k\in{\mathbb{N}})~{}(\forall{\mathb{w}}\in{\mathcal{W}})\quad\underline{\nu}\|{\mathb{w}}\|^{2}\leqslant\langle{\mathb{w}},{\mathbf{B}}_{k}{\mathb{w}}\rangle\leqslant\overline{\nu}\|{\mathb{w}}\|^{2}.$

  4. (iv)

There exists $B\geqslant 1$ and $C\geqslant 0$ such that almost-surely:

$(\forall
k\in{\mathbb{N}})\quad{\mathbb{E}}[{\mathbf{g}}_{k}|{\mathcal{F}}_{k}]=\nabla
F({\mathbf{x}}_{k}),\quad{\mathbb{E}}[\|{\mathbf{g}}_{k}\|^{2}|{\mathcal{F}}_{k}]\leqslant
B\|\nabla F({\mathbf{w}}_{k})\|^{2}+C.$

  5. (v)

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

Assumption 5.1(i) and (ii) are directly related to the curvature of $F$ the
function to minimize. While the first one is really 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 [5], the
second one is necessary to easily verify Assumption 2.1 once ${\mathcal{E}}$
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ and $L$ function have been identified.
However, Assumption 5.1(ii) do not appear to be so restrictive in practise
and, as seen in Example 2.2, seems not be satisfied only by coercive function
$F$ for which stationary point stretch out to infinity.

Assumption 5.1(iii) imposes for $({\mathbf{B}}_{k})_{k\in{\mathbb{N}}}$ to be
well-conditioned enough. Due to the fact that that
${\mathbf{B}}_{k}~{}(k\in{\mathbb{N}})$ is generally constructed using the
past information and those of ${\mathbf{w}}_{k}$, the current iterate,
${\mathcal{F}}_{k}$-measurability condition cannot be considered as too
constraining. The uniformly bounded spectrum condition is generally essential
so as not to counterbalance too negatively the effects of the descent
condition. By contrast with the convex case, where such a condition turns out
to be satisfied as soon as $({\mathbf{B}}_{k})_{k\in{\mathbb{N}}}$
approximates the second order information of $F$ (if twice-differentiable) and
includes regularity terms in its structure [12, 45], it generally requires to
deal with specific update rules [43, 15] considering a non-convex framework.

The first criterion of Assumption 5.1(iv) classically stipulates that,
regarding all the past events, the true gradient matches, in means with its
estimation. The second one is a criterion related to the conditional variance
and indicated that the latter can be controlled by two constants; $B$ relative
to the multiplicative tolerable error with respect to the true gradient and
$C$, relative to the additive error permitted. In the literature, this
criterion can now be found under the name of Weak (or Relaxed) Strong Growth
Condition [13, 27] but has been popularized few years before through [11].
Historically, [6] was the first one to invoke such a condition to investigate
on SGD convergence in the non-convex setting. However, its most widespread
form corresponds to the one where $B=1$ and therefore where only an additive
order error is assumed [25]. By contrast, the situation where $C=0$ refers to
what was originally called Strong Growth Condition. Although it allows to
study SGD taking a permissive stepsize (typically a constant one), this
situation is, in practice, only encountered when $F$, written in the form of
an empirical risk, has all its stationary points following an interpolation
condition [39].

Finally, Assumption 5.1(v) is the historical one made in [37] in a way to have
a preliminary control on the fluctuations relative the variance terms and more
specifically generated by the additive term $C$.

###  5.2 About the objectives

In the light of the approach historical initiated in [38], the universal first
step to investigate on the asymptotic behaviour of SGD consists in
establishing an almost-supermartingale descent inequality. In our situation,
this can be expressed under the following form

###### Lemma 5.2

Under Assumption 5.1 (i),(iii)-(v), $({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$
satisfies almost-surely

$(\forall
k\in{\mathbb{N}})\quad{\mathbb{E}}[F({\mathbf{w}}_{k+1})|{\mathcal{F}}_{k}]\leqslant
F({\mathbf{w}}_{k})-\alpha_{k}\left(\underline{\nu}-\frac{\alpha_{k}\beta
B\overline{\nu}^{2}}{2}\right)\|\nabla F({\mathbf{w}}_{k})\|^{2}+\frac{\beta
C\overline{\nu}^{2}}{2}\alpha_{k}^{2}$ (5.3)

Proof. The strategy of proof is very common and used extensively as first
approach to theoretically study stochastic optimization schemes in a
differentiable setting. In our case, this can be seen as an easy
generalization of the proof of [25] or [10] that typically can be found in
[43].

In a very classic way, once the descent inequality has been established, and
without any convexity assumption, asymptotic results for SGD starting from
(5.3) are directly obtained using the famous Robbins-Siegmund lemma [38].
Similarly with Example 2.2, $F$ being lower-bounded as a coercive function and
assuming that $(\alpha_{k})_{k\in{\mathbb{N}}}$ is small enough, such a result
can be invoked and gives, almost-surely, the convergence of
$(F({\mathbf{w}}_{k}))_{k\in{\mathbb{N}}}$ to a finite limit but above all
$\sum_{k=0}^{+\infty}\alpha_{k}\|\nabla F({\mathbf{w}}_{k})\|^{2}<+\infty$.
The latter property is an interesting starting point for our investigation to
the extent losing a order of magnitude in gradient, i.e. having almost-surely
$\sum_{k=0}^{+\infty}\alpha_{k}\|\nabla F({\mathbf{w}}_{k})\|<+\infty$
instead, is a sufficient condition of finite length for
$({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$.

###### Proposition 5.3

Let $A$ be an event of $\Omega$ and assume that $(\alpha_{k}\|\nabla
F({\mathbf{w}}_{k})\|)_{k\in{\mathbb{N}}}$ is summable almost-surely over $A$,
i.e.

$\sum_{k=0}^{+\infty}\alpha_{k}\|\nabla
F({\mathbf{w}}_{k})\|1_{A}<+\infty~{}~{}\mathrm{a.s.}.$ (5.4)

Then, under Assumption (iv), sequence $({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$
converges almost-surely over $A$.

Proof. Let us introduce filtration
$\left({\mathcal{F}}_{k}^{A}\right)_{k\in{\mathbb{N}}}$ such that for all
$k\in{\mathbb{N}}$
${\mathcal{F}}_{k}^{A}:=\sigma\left({\mathcal{F}}_{k}\cup\\{\\{A\\}\\}\right)$
(i.e. ${\mathcal{F}}_{k}^{A}$ is the smallest sigma-algebra containing both
${\mathcal{F}}_{k}$ and $\\{A\\}$). Following Definition (5.2) and the fact
that $({\mathbf{g}}_{k})_{k\in{\mathbb{N}}}$ is unbiased (Proposition (iv)),
we deduce that
${\mathbb{E}}[\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\||{\mathcal{F}}_{k}]=\alpha_{k}\|\nabla
F({\mathbf{x}}_{k})\|$ and so
${\mathbb{E}}[\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\||{\mathcal{F}}_{k}^{A}]=\alpha_{k}\|\nabla
F({\mathbf{x}}_{k})\|$ holds almost-surely for every $k\in{\mathbb{N}}$. As a
result, (5.3) can be rewritten as

$\sum_{k=0}^{+\infty}{\mathbb{E}}[\|{\mathbf{w}}_{k+1}-{\mathbf{w}}_{k}\|1_{A}|{\mathcal{F}}_{k}^{A}]<+\infty~{}~{}\mathrm{a.s.}.$
(5.5)

The terms inside the conditional expectation operator being positive, we are
allowed to invoke Levy’s sharpening of Borel-Cantelli Lemma [32, Ch.1, Th.21]
which finally gives

$\sum_{k=0}^{+\infty}\|{\mathbf{w}}_{k+1}-{\mathbf{w}}_{k}\|1_{A}<+\infty~{}~{}\mathrm{a.s.}.$
(5.6)

The latter relation indicates that, almost-surely over $A$, process
$({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ is of finite length (i.e. Cauchy) and
so converges.

Our strategy for establishing an almost-sure convergence result for the
iterates $({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ is therefore based on an
application of Proposition 5.3 considering an event $A$ as large as possible
and even ideally of probability one. To do so, the interest of using the
results of Section 4 is primarily of a structural nature; relations (4.17) of
Corollary 4.4 and (5.4) both correspond to summability conditions whose terms
inside the sums can be interpreted as ratios between the residues of a descent
condition and the gradient norm of the iterates. From this observation and
starting from the descent condition of the algorithm, the main challenge of
this section is none other to bridge the gap between (4.17) and (5.4) by
finding an Euclidean space of interest ${\mathcal{E}}$, a process
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ as well as a Lyapunov function $V$
(defined on ${\mathcal{E}}$) subject to the Assumptions 2.1, 4.1 and whose
structure is flexible enough to be related to those of $F$ in the simplest
possible way.

###  5.3 Attached Lyapunov function

In the light of what we studied before, the first step of our analysis
consists in identifying an Euclidean space ${\mathcal{E}}$, a process
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ and an associated function
$V:{\mathcal{E}}\to{\mathbb{R}}$, linked in some way to process
$({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ at stake and verifying a
supermartingale condition. To achieve this, we rely on the algorithm’s descent
condition, remind here below, we will write under a slightly less conventional
form.
The middle term from the right member of inequality (5.3) being negative as
soon as $(\alpha_{k})_{k\in{\mathbb{N}}}$ is small enough, it does not detract
from the martingale-like character we are trying to obtain here. The
positivity of term $\beta
C\overline{\nu}^{2}\alpha_{k}^{2}/2~{}(k\in{\mathbb{N}})$, on the contrary,
requires, for the latter, to be written under a different form.
To do so, we will invoke the ”difference trick” on
$\left(\alpha_{k}^{2}\right)_{k\in{\mathbb{N}}}$ under a more original way
using the fact that $\sum_{k=0}^{+\infty}\alpha_{k}^{2}<+\infty$. As such and
for any $k\in{\mathbb{N}}$ we are allow to write
$\alpha_{k}^{2}=\sum_{i=k}^{+\infty}\alpha_{i}^{2}-\sum_{i=k+1}^{+\infty}\alpha_{i}^{2}$
and finally, $\left(\alpha_{k}^{2}\right)_{k\in{\mathbb{N}}}$ being
deterministic descent inequality (5.3) almost-surely can be expressed as:

${\mathbb{E}}\left[F({\mathbf{w}}_{k+1})+\frac{\beta
C\overline{\nu}^{2}}{2}r_{k+1}|{\mathcal{F}}_{k}\right]\leqslant\left(F({\mathbf{w}}_{k})+\frac{\beta
C\overline{\nu}^{2}}{2}r_{k}\right)-\alpha_{k}\left(\underline{\nu}-\frac{\alpha_{k}\beta
B\overline{\nu}^{2}}{2}\right)\|\nabla F({\mathbf{w}}_{k})\|^{2}.$ (5.7)

where $r_{k}:=\sum_{i=k}^{+\infty}\alpha_{i}^{2}$ denotes the $k$-th rest of
the sum generated by $\left(\alpha_{k}^{2}\right)_{k\in{\mathbb{N}}}$.
Considering the Euclidean space product ${\mathcal{W}}\times{\mathbb{R}}$ (of
finite dimension), we then deduce a family of processes able to verify
Assumptions 2.1 and 4.1.

###### Proposition 5.4

Assume Assumption 5.1 holds with
$\sup_{k\in{\mathbb{N}}}\alpha_{k}<2\underline{\nu}/(\beta
B\overline{\nu}^{2})$, then for any $p\in{\mathbb{N}}^{*}$, process
$({\mathbf{x}}_{p,k})_{k\in{\mathbb{N}}}:=\left(\left({\mathbf{w}}_{k},r_{k}^{1/(2p)}\right)\right)_{k\in{\mathbb{N}}}$
, with values in ${\mathcal{E}}={\mathcal{W}}\times{\mathbb{R}}$, verifies
Assumption 2.1 as well as Assumption 4.1 considering
$V_{p}:{\mathcal{E}}\to{\mathbb{R}}$ defined as

$V_{p}:({\mathb{w}},r)\in{\mathcal{E}}\mapsto
V_{p}({\mathb{w}},r):=F({\mathb{w}})+\frac{\beta
C\overline{\nu}^{2}}{2}r^{2p}$ (5.8)

and $\Gamma:=\operatorname{zer}\nabla F\times\\{0\\}$. Moreover,
${\mathrm{F}}^{\infty}$, the integrable limit of
$\left(F({\mathbf{w}}_{k})\right)_{k\in{\mathbb{N}}}$ exists and if it
verifies
${\mathbb{E}}[{\mathrm{F}}^{\infty}|{\mathcal{F}}_{k}]>{\mathrm{F}}^{\infty}$
almost-surely at any iteration $k\in{\mathbb{N}}$, condition (ii) of Lemma 4.2
is satisfied.

Proof. Let us fix $p\in{\mathbb{N}}^{*}$.

First of all, regarding Assumption 5.1(i), $V_{p}$ is clearly a continuous and
coercive function.

Similarly with Example 2.2, $F$ being lower-bounded as a coercive function,
Lemma 5.2 with $\sum_{k=0}^{+\infty}\alpha_{k}^{2}<+\infty$ makes legal the
use of Robbins-Siegmund lemma [38]. As such and almost-surely,
${\mathrm{F}}^{\infty}$ is well-defined and finite while
$\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}<2\underline{\nu}/(\beta
B\overline{\nu}^{2})$. We deduce that $\Upsilon^{\infty}$, the set of
accumulation points of $({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ almost-surely
contains a point of $\operatorname{zer}\nabla F$. Then, with
$r_{k}^{1/(2p)}\underset{k\to+\infty}{\longrightarrow}0$, $\chi_{p}^{\infty}$
the set of accumulation points of $({\mathbf{x}}_{k,p})_{k\in{\mathbb{N}}}$,
is equal to $\chi_{p}^{\infty}=\Upsilon^{\infty}\times\\{0\\}$ and contains a
point of $\operatorname{zer}\nabla F\times\\{0\\}$. Finally with
$|V_{p}(\operatorname{zer}\nabla F\times\\{0\\}))|=|F(\operatorname{zer}\nabla
F)|<+\infty$ (Assumption 5.1(ii)), it follows that Assumption 2.1(i) is
satisfied taking $\Gamma=\operatorname{zer}\nabla F\times\\{0\\}$. Moreover
for all $k\in{\mathbb{N}}$ a simple calculus allows to, almost-surely, rewrite
$\eqref{rewrite_sto_grad}$ as

${\mathbb{E}}\left[V_{p}\left({\mathbf{x}}_{p,k+1}\right)|{\mathcal{F}}_{k}\right]\leqslant
V_{p}\left({\mathbf{x}}_{p,k}\right)-\alpha_{k}\left(\underline{\nu}-\frac{\alpha_{k}\beta
B\overline{\nu}^{2}}{2}\right)\|\nabla F({\mathbf{w}}_{k})\|^{2}.$ (5.9)

Thanks again to
$\sup\limits_{k\in{\mathbb{N}}}\alpha_{k}<2\underline{\nu}/(\beta
B\overline{\nu}^{2})$, process
$\left(V_{p}\left({\mathbf{x}}_{k,p}\right)\right)_{k\in{\mathbb{N}}}$ is a
supermartingale and Assumption 4.1 is verified.
$\left(V_{p}\left({\mathbf{x}}_{k,p}\right)\right)_{k\in{\mathbb{N}}}$ thus
almost-surely converges to an integrable limit ${\mathrm{V}}_{p}^{\infty}$ and
it is easy to show that, almost-surely,
${\mathrm{V}}_{p}^{\infty}={\mathrm{F}}^{\infty}$. Then,
${\mathrm{F}}^{\infty}$ is integrable and, almost-surely for all
$k\in{\mathbb{N}}$, due to
${\mathbb{E}}[{\mathrm{F}}^{\infty}|{\mathcal{F}}_{k}]>{\mathrm{F}}^{\infty}$
we finally have
${\mathbb{E}}[{\mathrm{V}}_{p}^{\infty}|{\mathcal{F}}_{k}]>{\mathrm{V}}_{p}^{\infty}$
and condition (ii) of Lemma 4.2 holds.

One of the key point of the previous proof relies on the convergence of
$(r_{k})_{k\in{\mathbb{N}}}$, the sequence of rests, to zero which allows us
to make easy links between process $(F({\mathbf{w}}_{k}))_{k\in{\mathbb{N}}}$,
directly associated to the initial scheme, and
$\left(V_{p}({\mathbf{x}}_{p,k})\right)_{k\in{\mathbb{N}}}$ of Lyapunov type
verifying the supermartingale condition. More specifically, they have the
advantage of sharing ${\mathrm{F}}^{\infty}$ as a common limit, independant
from $p$ parameter. From an asymptotic point of view, the further apart $F$
and $V_{p}$ are, the less realistic Assumption 4.1 (which relates directly to
$V_{p}$, the object that is technically the most difficult to assemble)
appears to be.

###  5.4 One sufficient condition for almost-sure convergence of SGD in a non-
convex framework

We introduce in this subsection our main new asymptotical results related to
scheme (5.2). To do so and to highlight the relevance of the study conducted
in the previous sections, we first exhibit a new lemma which actually
corresponds to the application of Corollary 4.4.

###### Lemma 5.5

Assume that Assumption 5.1 holds and also that $F$ verifies the KL property.
If conditions $\sup_{k\in{\mathbb{N}}}\alpha_{k}<2\underline{\nu}/(\beta
B\overline{\nu}^{2})$, and
${\mathbb{E}}[{\mathrm{F}}^{\infty}|{\mathcal{F}}_{k}]>{\mathrm{F}}^{\infty},\|\nabla
F({\mathbf{w}}_{k})\|>0$ at any iteration $k\in{\mathbb{N}}$ are satisfied,
then, for all $p\in{\mathbb{N}}^{*}$:

$\sum_{k=0}^{+\infty}\frac{\alpha_{k}\|\nabla
F({\mathbf{w}}_{k})\|}{\sqrt{1+{\mathbf{Y}}_{k}^{p}}}<+\infty~{}~{}\mathrm{a.s.},~{}~{}\text{where
}~{}~{}(\forall k\in{\mathbb{N}})~{}~{}{\mathbf{Y}}_{k}^{p}:=\frac{(p\beta
C)^{2}\overline{\nu}^{4}r_{k}^{2-1/p}}{\|\nabla F({\mathbf{w}}_{k})\|^{2}}.$
(5.10)

Proof. Once again, let us start by fixing $p>0$. According to Assumption
5.1(i), $V_{p}$ (defined in (5.8)) is basically differentiable whose
associated gradient simply corresponds to:

$\nabla V_{p}:({\mathb{w}},r)\in{\mathcal{E}}\mapsto\nabla
V_{p}({\mathb{w}},r)=\begin{pmatrix}\nabla F({\mathb{w}})\\\ p\beta
C\overline{\nu}^{2}r^{2p-1}\end{pmatrix}.$ (5.11)

Moreover, since $F$ and $r\in{\mathbb{R}}\mapsto r^{2p}$ verify the KL
property, so it is for $V_{p}$. Then, according to Proposition 5.4, all the
conditions for applying the Theorem 4.3 and Corollary 4.4 are met. We thus
deduce that

$\sum_{k=0}^{+\infty}\frac{V_{p}({\mathbf{x}}_{p,k})-{\mathbb{E}}[V_{p}({\mathbf{x}}_{p,k+1})|{\mathcal{F}}_{k}]}{\|\nabla
V_{p}({\mathbf{x}}_{p,k})\|_{{\mathcal{E}}}}<+\infty~{}~{}\text{a.s.},$ (5.12)

which, in regards of (5.9) and (5.11), can be rewritten as

$\sum_{k=0}^{+\infty}\alpha_{k}\left(\underline{\nu}-\frac{\alpha_{k}\beta
B\overline{\nu}^{2}}{2}\right)\frac{\|\nabla
F({\mathbf{w}}_{k})\|^{2}}{\sqrt{\|\nabla F({\mathbf{w}}_{k})\|^{2}+(p\beta
C)^{2}\overline{\nu}^{4}r_{k}^{2-1/p}}}<+\infty~{}~{}\text{a.s.}.$ (5.13)

Relation (5.10) simply follows by positive comparison with
$\sup_{k\in{\mathbb{N}}}\alpha_{k}<2\underline{\nu}/(\beta
B\overline{\nu}^{2})$ and by removing term $\|\nabla
F({\mathbf{w}}_{k})\|^{2}$ from the root.

Lemma 5.5 is all the more interesting because it highlights the crucial role
of process
$({\mathbf{Y}}_{k})^{p}_{k\in{\mathbb{N}}}~{}~{}(p\in{\mathbb{N}}^{*})$ in the
establishment of new convergence properties for
$({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$.
$({\mathbf{Y}}_{k})^{p}_{k\in{\mathbb{N}}}$ can be interpreted as a kind of
control ratio between $(r_{k})_{k\in{\mathbb{N}}}$ directly associated to the
stepsize and $\left(\|\nabla F({\mathbf{w}}_{k})\|\right)_{k\in{\mathbb{N}}}$
the norm of the true gradient. In the case where $C=0$, i.e. under the Strong
growth Condition [39], ${\mathbf{Y}}_{k}^{p}=0$ for all $k\in{\mathbb{N}}$ and
Proposition 5.3 especially directly leads to the almost-sure convergence of
$({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$.

However, the greatest strength of the lemma 5.5, more generally, lies in the
fact that it states that preserving a gradient norm that is not too small
compare with the stepsize is a favourable situation in a way to obtain new
convergence results. Typically, regarding (5.10), in the ideal scenario where,
for a given $p\in{\mathbb{N}}^{*}$ and almost-surely, ratio
$({\mathbf{Y}}_{k})^{p}_{k\in{\mathbb{N}}}$ turns out to be bounded
$\sum_{k=0}^{+\infty}\alpha_{k}\|\nabla F({\mathbf{w}}_{k})\|<+\infty$
directly follows. To such an extent, our convergence theorem gives the almost-
sure convergence of process $({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ to a
stationary point of $F$ in the situation where the decay of the gradient
remains ”moderate” regarding those of the stepsize.

###### Theorem 5.6

Assume that Assumption 5.1 holds and also that $F$ verifies the KL property.
If conditions $\sup_{k\in{\mathbb{N}}}\alpha_{k}<2\underline{\nu}/(\beta
B\overline{\nu}^{2})$, and
${\mathbb{E}}[{\mathrm{F}}^{\infty}|{\mathcal{F}}_{k}]>{\mathrm{F}}^{\infty},~{}\|\nabla
F({\mathbf{w}}_{k})\|>0$ at any iteration $k\in{\mathbb{N}}$ are satisfied,
process $({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ almost-surely converges to a
stationary point of $F$ under the event

$\Xi:=\bigcup\limits_{p\in{\mathbb{N}}^{*}}\left\\{\limsup\limits_{k\to+\infty}\left[\left(\sum_{i=k}^{+\infty}\alpha_{i}^{2}\right)^{2-1/p}\|\nabla
F({\mathbf{w}}_{k})\|^{-2}\right]<+\infty\right\\}.$ (5.14)

Proof. Let us first denote

${\mathcal{A}}:=\bigcap_{p\in{\mathbb{N}}^{*}}\left\\{\sum_{k=0}^{+\infty}\frac{\alpha_{k}\|\nabla
F({\mathbf{w}}_{k})\|}{\sqrt{1+{\mathbf{Y}}_{k}^{p}}}<+\infty\right\\}.$
(5.15)

For all $\omega\in\Xi\cap{\mathcal{A}}$, there exists
$p_{\omega}\in{\mathbb{N}}^{*}$ for which trajectory
$\left({\mathbf{Y}}^{p_{\omega}}(\omega)\right)_{k\in{\mathbb{N}}}$ is bounded
with

$\sum_{k=0}^{+\infty}\frac{\alpha_{k}\|\nabla
F({\mathbf{w}}_{k}(\omega))\|}{\sqrt{1+{\mathbf{Y}}^{p_{\omega}}(\omega)}}<+\infty,$
(5.16)

and then by positive comparison and boundedness of
$\left({\mathbf{Y}}^{p_{\omega}}(\omega)\right)_{k\in{\mathbb{N}}}$, it
directly follows that

$\sum_{k=0}^{+\infty}\alpha_{k}\|\nabla
F({\mathbf{w}}_{k}(\omega))\|<+\infty.$ (5.17)

Since Lemma 5.5 ensures that ${\mathbb{P}}({\mathcal{A}})=1$, relation (5.17)
can be expressed as

$\sum_{k=0}^{+\infty}\alpha_{k}\|\nabla
F({\mathbf{w}}_{k})\|1_{\Xi}<+\infty~{}~{}~{}\mathrm{a.s.}.$ (5.18)

As such, Proposition 5.3 directly ensures that process
$({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ almost-surely converges over $\Xi$.
The conclusion simply comes from the fact that $\Upsilon^{\infty}$ the set of
accumulation points of $({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ almost-surely
contains a stationary point of $F$.

###  5.5 Discussion

The relevance of Theorem 5.6 directly depends on the size (in the sense of
${\mathbb{P}}$) of the set $\Xi$ that it involves. Because ${\mathbb{P}}(\Xi)$
shall remains close to one in practise for our result to be of any real
interest, this suggests to investigate on the existing almost-sure convergence
rates related to the gradient norm of SGD schemes.

The main results, supporting the fact that the convergence of the real
gradient to zero does not appear to be fast and therefore $\Xi$ does not
appear to be too small, are those introduced in [40]. In a pessimistic way, it
has only been proven, for a stepsize $(\alpha_{k})_{k\in{\mathbb{N}}}$ of
generic structure, that, almost-surely, quantity $\min_{1\leqslant i\leqslant
k}\|\nabla F({\mathbf{w}}_{i})\|^{2}$ remains asymptotically small in front of
$1/\sum_{i=0}^{k}\alpha_{i}^{2}$ ([40, Theorem 16]). More precise convergence
rates can be obtained but require to take specific stepsizes. However, as
shown in Example 5.7 below, the resulting improvement are generally not strong
enough to compromise the usefulness of Theorem 5.6.

###### Example 5.7

According to [40, Corollary 18] if we take $\alpha_{k}=a/k^{1/2+\epsilon}$ for
all $k>0$ ($a>0$ small enough and $\epsilon\in(0,1/2)$), the convergence rate
of $\min_{1\leqslant i\leqslant k}\|\nabla F({\mathbf{w}}_{i})\|^{2}$ can be
refined as

$\min_{1\leqslant i\leqslant k}\|\nabla
F({\mathbf{w}}_{i})\|^{2}\underset{k\to+\infty}{=}\left(\frac{1}{k^{1/2-\epsilon}}\right)~{}~{}\mathrm{a.s.}.$

Considering this, it does not appear inconsistent to consider that the
gradient norm does not decrease faster than ${\mathcal{O}}(1/k^{1/4})$. As
such, if we then place ourselves in the ”optimistic” situation where $\|\nabla
f({\mathbf{w}}_{k})\|^{2}\underset{k\to+\infty}{\sim}1/k^{1/4}$ almost surely,
then for all $p\in{\mathbb{N}}^{*}$, we deduce that

$\displaystyle\left(\sum_{i=k}^{+\infty}\alpha_{i}^{2}\right)^{2-1/p}\|\nabla
F({\mathbf{w}}_{k})\|^{-2}$
$\displaystyle=\left(\sum_{i=k}^{+\infty}\frac{a^{2}}{k^{1+2\epsilon}}\right)^{2-1/p}\|\nabla
F({\mathbf{w}}_{k})\|^{-2},$
$\displaystyle\underset{k\to+\infty}{\sim}\frac{a^{2}}{k^{2\epsilon(2-1/p)}}k^{1/2},$
$\displaystyle\underset{k\to+\infty}{=}{\mathcal{O}}\left(k^{(1/2-2\epsilon(2-1/p))}\right)~{}~{}\mathrm{a.s.}.$

Since
$1/2-2\epsilon(2-1/p)\underset{p\to+\infty}{\longrightarrow}1/2-4\epsilon$, we
thus deduce that, if $\epsilon\geqslant 1/8$, there basically exists
$p_{0}\in{\mathbb{N}}^{*}$ for which $1/2-2\epsilon(2-1/p)\leqslant 0$, then

$\left(\sum_{i=k}^{+\infty}\alpha_{i}^{2}\right)^{2-1/p_{0}}\|\nabla
F({\mathbf{w}}_{k})\|^{-2}\underset{k\to+\infty}{=}{\mathcal{O}}(1)~{}~{}\mathrm{a.s.}$

and finally ${\mathbb{P}}(\Xi)=1$.

In the previous example and in a way to prove as best as best possible the
validity of our theorem, we have considered a situation where the convergence
of the gradient to zero turns out to be quite ”fast” compared with the
theoretical convergence rate estimation of [40]. In the (very) particular
situation where the gradient converges to zero even more quickly to the point
that the use of Theorem 5.6 cannot provide interesting results (typically
because $\Xi$ becomes too small), it would be possible, to a certain extent,
to obtain the almost-sure convergence of
$({\mathbf{w}}_{k})_{k\in{\mathbb{N}}}$ by making use of the fact that the
decay of $(\nabla F({\mathbf{w}}_{k}))_{k\in{\mathbb{N}}}$ may be large enough
to directly ensure $\sum_{k=0}^{+\infty}\alpha_{k}\|\nabla
F({\mathbf{w}}_{k})\|<+\infty$ almost-surely. Nevertheless, such a situation,
up to our knowledge, seems to be rarely encountered in practise.

##  6 Scope for improvements

###  6.1 Around our assumptions in general

The various assumptions made throughout this work seem reasonable insofar as
they do not require curvature properties that are too specific for the
functions studied, and in particular we have endeavoured to retain a non-
convex framework. Moreover, the supermartingale behaviour assumed in the main
part of our analysis is one of the founding points of the theory of stochastic
approximation [23]. As we typically tried to highlight in section 5, most of
the descent conditions verified by an approximation scheme in an optimisation
context can be interpreted as supermartingale inequality of a certain
Lyapunov-type function.

The (KL)-property as a way of circumventing the non-convexity of our framework
is verified by a large class of functions and in particular those that turn
out to be semi-algebraic [28]. However, in contrast to its historical
counterpart, namely the (L)-inequality [31], (KL)-property is somewhat
inflexible in that it imposes a demanding condition of the form
$0<V({\mathb{x}})-V(\tilde{{\mathb{x}}})<\zeta$ in the neighborhood of
$\tilde{{\mathb{x}}}\in{\mathcal{E}}$, the ”target” point. Since the decay of
a Lyapunov-type process is generally strict in deterministic, the latter
condition does not constitute an obstacle as such in this kind of context.
However, in the case of stochasticity, where the notion of ”decay” is
associated with that of supermartingale, this condition is more difficult to
meet. In our case, we made the choice to admit additional conditions as those
of Theorem 4.3(ii) for counterbalancing purposes. Let us mention that [24] has
started some numerical experiments on small academical examples to see how
mild this kind of conditions is in practise. On a more theoretical aspect,
[29, 33] bypassed such a difficulty by assuming a version of (KL)-property
involving absolute values for the term $V({\mathb{x}})-V(\tilde{{\mathb{x}}})$
and which would not be too restrictive according to the authors.

###  6.2 The non-smooth case

In the light of the works of [8, 9], we are naturally led to consider a non-
smooth extension of our framework. If we stay in the situation where the $V$
function remains coercive and continuous, it is not difficult to adapt our
previous reasoning starting from the non-smooth version of the (KL)-property.
The difference being only of structural order and simply consists in replacing
the gradient norm by the distance of the limiting subdifferential [35] to
zero. Such an approach seems to be all the more interesting as it could refine
the asymptotical results of some recent schemes as the existing versions of
stochastic PALM [22, 26] or even the asynchronous previous version of [20].
For this specific class of algorithms, if we consider that the origin of
stochasticity also comes from the indices selection, the structure of the
Lyapunov process is expected to be more complex that the one we use in Section
5. The reader may typically refer to the proof of [20, Theorem 4.1] or [26,
Theorem 5.4] to have an idea of ${\mathcal{E}}$,
$({\mathbf{x}}_{k})_{k\in{\mathbb{N}}}$ and function $V$ to consider. As such,
the conditions to apply Theorem 4.3 appear to be valid but the resulting
summability relation seem not to give easy interpretable asymptotic results
given that, the relation between the descent condition and the distance of the
limiting subdifferential to zero is generally quite complex.

## References

  * [1] P.-A. Absil, R. Mahony, and B. Andrews.  Convergence of the iterates of descent methods for analytic cost functions.  SIAM Journal on Optimization, 16(2):531–547, 2005.
  * [2] H. Attouch, J. Bolte, P. Redont, and A. Soubeyran.  Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality.  Mathematics of Operations Research, 35(2):438–457, 2010.
  * [3] M. Benaim.  A dynamical system approach to stochastic approximations.  SIAM Journal on Control and Optimization, 34(2):437–472, 1996.
  * [4] M. Benaim.  On strict convergence of stochastic gradients.  arXiv preprint arXiv:1610.03278, 2016.
  * [5] D. P. Bertsekas.  Nonlinear Programming.  Athena Scientific, 2nd edition, 1999.
  * [6] D. P. Bertsekas and J. N. Tsitsiklis.  Gradient convergence in gradient methods with errors.  SIAM Journal on Optimization, 10(3):627–642, 2000.
  * [7] J. Bolte, A. Daniilidis, A. Lewis, and M. Shiota.  Clarke subgradients of stratifiable functions.  SIAM Journal on Optimization, 18(2):556–572, 2007.
  * [8] J. Bolte, A. Daniilidis, O. Ley, and L. Mazet.  Characterizations of łojasiewicz inequalities: subgradient flows, talweg, convexity.  Transactions of the American Mathematical Society, 362(6):3319–3363, 2010.
  * [9] J. Bolte, S. Sabach, and M. Teboulle.  Proximal alternating linearized minimization for nonconvex and nonsmooth problems.  Mathematical Programming, 146(1):459–494, Aug 2014.
  * [10] L. Bottou.  Large-scale machine learning with stochastic gradient descent.  In Proceedings of COMPSTAT’2010, pages 177–186. Springer, 2010.
  * [11] L. Bottou, F. E. Curtis, and J. Nocedal.  Optimization methods for large-scale machine learning.  Siam Review, 60(2):223–311, 2018.
  * [12] R. H. Byrd, S. L. Hansen, J. Nocedal, and Y. Singer.  A stochastic quasi-newton method for large-scale optimization.  SIAM Journal on Optimization, 26(2):1008–1031, 2016.
  * [13] V. Cevher and B. C. Vũ.  On the linear convergence of the stochastic gradient method with constant step-size.  Optimization Letters, 13(5):1177–1187, 2019.
  * [14] M. Chalvidal, E. Chouzenoux, J.-B. Fest, and C. Lefort.  Block delayed majorize-minimize subspace algorithm for large scale image restoration.  Technical report, 2022.  https://hal.science/hal-03814231.
  * [15] H. Chen, H.-C. Wu, S.-C. Chan, and W.-H. Lam.  A stochastic quasi-newton method for large-scale nonconvex optimization with applications.  IEEE transactions on neural networks and learning systems, 31(11):4776–4790, 2019.
  * [16] R. Chill, A. Haraux, and M. A. Jendoubi.  Applications of the lojasiewicz-simon gradient inequality to gradient-like evolution equations.  Anal. Appl.(Singap.), 7(4):351–372, 2009.
  * [17] E. Chouzenoux and J.-B. Fest.  Convergence analysis of block majorize-minimize subspace approach.  Optimization Letters, pages 1–20, 2023.
  * [18] E. Chouzenoux, J.-B. Fest, and A. Repetti.  A kurdyka-lojasiewicz property for stochastic optimization algorithms in a non-convex setting.  2023\.
  * [19] E. Chouzenoux, J.-C. Pesquet, and A. Repetti.  Variable metric forward–backward algorithm for minimizing the sum of a differentiable function and a convex function.  Journal of Optimization Theory and Applications, 162(1):107–132, 2014.
  * [20] D. Davis.  The asynchronous PALM algorithm for nonsmooth nonconvex problems.  Technical report, 2016.  https://arxiv.org/abs/1604.00526.
  * [21] S. Dereich and S. Kassing.  Convergence of stochastic gradient descent schemes for lojasiewicz-landscapes.  arXiv preprint arXiv:2102.09385, 2021.
  * [22] D. Driggs, J. Tang, J. Liang, M. Davies, and C.-B. Schönlieb.  Spring: A fast stochastic proximal alternating method for non-smooth non-convex optimization.  arXiv preprint arXiv:2002.12266, 2020.
  * [23] M. Duflo.  Random Iterative Models.  Springer-Verlag, Berlin Heidelberg, 2013.
  * [24] J.-B. Fest, A. Repetti, and E. Chouzenoux.  A new non-convex framework to improve asymptotical knowledge on generic stochastic gradient descent.  In 2023 IEEE 33rd International Workshop on Machine Learning for Signal Processing (MLSP), pages 1–6. IEEE, 2023.
  * [25] S. Ghadimi and G. Lan.  Stochastic first-and zeroth-order methods for nonconvex stochastic programming.  SIAM Journal on Optimization, 23(4):2341–2368, 2013.
  * [26] J. Hertrich and G. Steidl.  Inertial stochastic palm and applications in machine learning.  Sampling Theory, Signal Processing, and Data Analysis, 20(1):4, 2022.
  * [27] A. Khaled and P. Richtárik.  Better theory for SGD in the nonconvex world.  Technical report, 2020.  https://arxiv.org/abs/2002.03329.
  * [28] K. Kurdyka.  On gradients of functions definable in o-minimal structures.  In Annales de l’institut Fourier, volume 48, pages 769–783, 1998.
  * [29] X. Li, A. Milzarek, and J. Qiu.  Convergence of random reshuffling under the kurdyka–łojasiewicz inequality.  SIAM Journal on Optimization, 33(2):1092–1120, 2023.
  * [30] L. Ljung.  Strong convergence of a stochastic approximation algorithm.  The Annals of Statistics, 6(3):680–696, 1978.
  * [31] S. Łojasiewicz.  Sur la géométrie semi-et sous-analytique.  In Annales de l’institut Fourier, volume 43, pages 1575–1595, 1993.
  * [32] P.-A. Meyer.  Martingales and Stochastic Integrals I, volume 284.  Springer, 2006.
  * [33] A. Milzarek and J. Qiu.  Convergence of a normal map-based prox-sgd method under the kl inequality.  arXiv preprint arXiv:2305.05828, 2023.
  * [34] A. Mokhtari and A. Ribeiro.  Res: Regularized stochastic bfgs algorithm.  IEEE Transactions on Signal Processing, 62(23):6089–6104, 2014.
  * [35] B. S. Mordukhovich.  Variational analysis and generalized differentiation vol. i: Basic theory, vol. ii: Applications, 2006.
  * [36] B. T. Polyak.  Some methods of speeding up the convergence of iteration methods.  Ussr computational mathematics and mathematical physics, 4(5):1–17, 1964.
  * [37] H. Robbins and S. Monro.  A stochastic approximation method.  The Annals of Mathematical Statistics, pages 400–407, 1951.
  * [38] H. Robbins and D. Siegmund.  A convergence theorem for non negative almost supermartingales and some applications.  Optimizing Methods in Statistics, pages 233–257, 1971.
  * [39] M. Schmidt and N. L. Roux.  Fast convergence of stochastic gradient descent under a strong growth condition.  Technical report, 2013.  https://arxiv.org/abs/1308.6370.
  * [40] O. Sebbouh, R. M. Gower, and A. Defazio.  Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball.  In Proceedings of the Conference on Learning Theory (COLT 2021), pages 3935–3971, 2021.
  * [41] V. B. Tadić.  Convergence and convergence rate of stochastic gradient search in the case of multiple and non-isolated extrema.  Stochastic Processes and their Applications, 125(5):1715–1755, 2015.
  * [42] W. J. Terrell.  Stability and stabilization: an introduction.  Princeton University Press, 2009.
  * [43] X. Wang, S. Ma, D. Goldfarb, and W. Liu.  Stochastic quasi-Newton methods for nonconvex stochastic optimization.  SIAM Journal on Optimization, 27(2):927–956, 2017.
  * [44] D. Williams.  Probability with martingales.  Cambridge university press, 1991.
  * [45] F. Yousefian, A. Nedić, and U. 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), pages 4496–4503. IEEE, 2016.