Almost sure convergence of stochastic Hamiltonian descent methods

## Abstract

Abstract. Gradient normalization and soft clipping are two popular techniques for tackling instability issues and improving convergence of stochastic gradient descent (SGD) with momentum.
In this article, we study these types of methods through the lens of dissipative Hamiltonian systems. Gradient normalization and certain types of soft clipping algorithms can be seen as (stochastic) implicit-explicit Euler discretizations of dissipative Hamiltonian systems, where the kinetic energy function determines the type of clipping that is applied.
We make use of dynamical systems theory to show in a unified way that all of these schemes converge to stationary points of the objective function, almost surely, in several different settings:
a) for L − limit-from 𝐿 L- italic_L - smooth objective functions,
when the variance of the stochastic gradients is possibly infinite
b) under the ( L 0 , L 1 ) − limit-from subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1})- ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) - smoothness assumption, for heavy-tailed noise with bounded variance and c) for ( L 0 , L 1 ) − limit-from subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1})- ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) - smooth functions in the empirical risk minimization setting, when the variance is possibly infinite but the expectation is finite.

## 1. Introduction

In this article we consider the optimization problem

$$ (1) $\displaystyle\min_{q\in\mathbb{R}^{d}}F(q),$ $$

where $F:\mathbb{R}^{d}\to\mathbb{R}$ is an objective function. A common case in mathematical statistics and machine learning is the empirical risk minimization setting, where $F$ is a weighted sum of loss functions:

$$ (2) $\displaystyle F(q)=\frac{1}{N}\sum_{i=1}^{N}f_{i}(q),$ $$

with $f_{i}(q)=\ell(h(x_{i},q),y_{i})$.
Here, $\{(x_{i},y_{i})\}_{i=1}^{N}$ is an underlying data set of feature-label pairs in the feature-label space $\mathcal{X}\times\mathcal{Y}$, $h(q,\cdot)$ is a model with model parameters $q$ such as a neural network or a regression function, and $\ell$ is a loss function.
A common approach within the machine learning community for solving problems of the type given by (1)
is to employ *stochastic gradient descent* (SGD) (Robbins & Monro, ). The solution to (1) is approximated iteratively with a stochastic approximation to the gradient of the function defined by (2):

$$ (3) $\displaystyle q_{k+1}=q_{k}-\alpha_{k}\nabla f(q_{k},\xi_{k}).$ $$

Here $\alpha_{k}$ is the learning rate and $\xi_{k}$ is a random variable that accounts for the stochasticity.
A common choice is to take a random subset $B_{\xi_{k}}\subset\{1,\dots,N\}$ of the indices of the objective function defined by (2) and choose

$$ (4) $\displaystyle\nabla f(q,\xi_{k})=\frac{1}{|B_{\xi_{k}}|}\sum_{i\in B_{\xi_{k}} }\nabla f_{i}(q),$ $$

where $|B_{\xi_{k}}|$ denotes the cardinality of $B_{\xi_{k}}$. This is attractive when $N$ is very large and $|B_{\xi}|\ll N$, as it is less computationally expensive than gradient descent. It also tends to escape local saddle points (Fang et al., ) - an appealing property as many machine learning problems are non-convex.
Among the variations of SGD is the popular *SGD with momentum*. Its deterministic counterpart was first introduced in the seminal work of Polyak (). A common form of this algorithm is expressed as an update in two stages

$$ (5) $\displaystyle\begin{split}p_{k+1}&=\beta_{k}p_{k}-\alpha_{k}\nabla f(q_{k},\xi _{k})\\ q_{k+1}&=q_{k}+\alpha_{k}p_{k+1}\end{split}$ $$

where $p_{0}=0$ and $\beta_{k}>0$ is a momentum parameter.
The usage of the momentum update makes the algorithm less sensitive to noise. Indeed, by an iterative argument, we obtain that
$p_{k+1}=-\sum_{i=0}^{k}\left(\prod_{j=i+1}^{k}\beta_{j}\right)\alpha_{i}\nabla
f
(q_{i},\xi_{k}).$
That is, $p_{k+1}$ is an average of the previous gradients where $\beta_{k}$ determines how much we value information from the preceding stages.

Notwithstanding the benefits of stochastic gradient algorithms, they frequently suffer from instability problems such as exploding gradients (Pascanu et al., ; Bengio et al., ) and sensitivity to the choice of learning rate (Owens & Filkin, ).
A way to mitigate these issues is to employ gradient clipping (Goodfellow et al., ; Pascanu et al., )
or gradient normalization.
Gradient normalization was introduced in Poljak () in the deterministic and a stochastic version appears already in Andradóttir (). A normalized version of the algorithm determined by (3) is given by

$$ $\displaystyle q_{k+1}=q_{k}-\alpha_{k}\frac{\nabla f(q_{k},\xi_{k})}{\lVert \nabla f(q_{k},\xi_{k})\rVert_{2}}.$ $$

In practice a small number $\epsilon>0$ is added in the denominator to ensure that the update does not become infinitely large.

Gradient clipping was first introduced in Mikolov (). In so-called *hard clipping*, the gradient is simply rescaled if it is larger than some predetermined threshold. *Soft clipping*, on the other hand, makes use of a differentiable function for rescaling the gradient (Zhang et al., ). It was recently shown that hard clipping algorithms suffer from an *unavoidable bias term*
(Koloskova et al., ); a term in the convergence bound that does not decrease as the number of iterations increases. This is one reason why soft clipping is preferable.

### 1.1. Gradient normalization, momentum and Hamiltonian systems

In this article, we study gradient normalization and soft clipping of stochastic momentum algorithms from the perspective of *Hamiltonian systems*. As a first step, we note that if we take $\beta_{k}=1-\gamma\alpha_{k}$ with $\gamma>0$, we can view the scheme given by (5) as an approximate implicit-explicit Euler discretization of the equation system

$$ (6) $\displaystyle\begin{split}\dot{p}&=-\nabla F(q)-\gamma p,\\ \dot{q}&=p.\end{split}$ $$

The system 6 is *nearly Hamiltonian* (Glendinning, ); taking

$$ (7) $\displaystyle H(p,q)=F(q)+\varphi(p),$ $$

with $\varphi(p)=\frac{1}{2}\lVert p\rVert_{2}^{2}$, we can write it on the form

$$ (8) $\displaystyle\begin{split}\dot{p}&=-\nabla_{q}H(p,q)-\nabla_{\dot{q}}\mathcal{ R}(\dot{q}),\\ \dot{q}&=\nabla_{p}H(p,q),\end{split}$ $$

where $\nabla_{p},\nabla_{q}$ denote the gradients with respect to $p$ and $q$ respectively and $\mathcal{R}(\dot{q})=\gamma\frac{\lVert\dot{q}\rVert_{2}^{2}}{2}$ is a *Rayleigh dissipation function* that accounts for energy dissipation (viscous friction) of the system. Note that this choice of $\mathcal{R}$ yields $\nabla_{\dot{q}}\mathcal{R}(\dot{q})=\gamma\nabla_{p}H(p,q)$, which will always be the case in this paper. Thus, for a Hamiltonian of the form 7, (8), reads

$$ $\displaystyle\begin{split}\dot{p}&=-\nabla F(q)-\gamma\nabla\varphi(p),\\ \dot{q}&=\nabla\varphi(p).\end{split}$ $$

We notice that any *fixed point* of this system is a stationary point of $F$, since $(\dot{q},\dot{p})=0$ implies that $\nabla F(q)=0$.
The dissipation term is often included as an extra term in the Euler-Lagrange equations

$$ $\displaystyle\nabla_{\dot{q}}L(q,\dot{q})-\frac{\mathrm{d}}{\mathrm{d}t}L(q, \dot{q})=\nabla_{\dot{q}}\mathcal{R}(\dot{q}),$ $$

where $L(q,\dot{q})=\varphi^{*}(\dot{q})-F(q)$ is the *Lagrangian*, and $\varphi^{*}$ is the convex conjugate of $\varphi$, compare Proposition 51.2 and Ex. 51.3 in Zeidler (). The physical interpretation is that
$q$ is the position of a particle in a potential field $F(q)$ with kinetic energy given by $\varphi^{*}(\dot{q})$ (in the case when $\varphi(p)=\frac{\lVert p\rVert_{2}^{2}}{2}$ we have $\varphi^{*}(\dot{q})=\frac{\lVert\dot{q}\rVert_{2}^{2}}{2}$).
In many scenarios, such as in this case, it happens that the friction tern is proportional to the velocity (Goldstein et al., ). A ball rolling on a rough incline (Wolf et al., ; Bideau et al., )) or on a tilted plane coated with a viscous fluid (Bico et al., ) could for instance be modelled in this fashion, giving weight to the analogy of the *heavy ball* (Polyak, ). See also Goodfellow et al. (), for a further discussion on this.

In this paper, we consider generalizations of the algorithm defined by (5) to equations of the type (8) where $F$ is an $L$-smooth, coercive function and $\varphi$ is a convex, coercive and $L$-smooth function. The scheme we consider is given by

$$ (9) $\displaystyle\begin{split}p_{k+1}&=p_{k}-\alpha_{k}\nabla f(q_{k},\xi_{k})- \alpha_{k}\gamma\nabla\varphi(p_{k}),\\ q_{k+1}&=q_{k}+\alpha_{k}\nabla\varphi(p_{k+1}),\end{split}$ $$

where $p_{0}=0$, $q_{0}$ is arbitrary, and $\{\xi_{k}\}_{k\geq 0}$ is a sequence of independent, identically distributed random variables. We show that this scheme converges almost surely to the set of stationary points of $F$.
If we take $\varphi(x)=\frac{\lVert x\rVert_{2}^{2}}{2}$ in (9), we get (5). Taking $\varphi(x)=\sqrt{\lVert x\rVert_{2}^{2}+\epsilon},\ \epsilon>0$, gives us a gradient normalization scheme, where both the gradient and the momentum variables are rescaled:

$$ (10) $\displaystyle\begin{split}p_{k+1}&=p_{k}-\alpha_{k}\nabla f(q_{k},\xi_{k})- \alpha_{k}\gamma\frac{p_{k}}{\sqrt{\lVert p_{k}\rVert_{2}^{2}+\epsilon}},\\ q_{k+1}&=q_{k}+\alpha_{k}\frac{p_{k+1}}{\sqrt{\lVert p_{k+1}\rVert_{2}^{2}+ \epsilon}}.\end{split}$ $$

Other conceivable choices are

- i)
*Relativistic kinetic energy:*
$\varphi(x)=c\sqrt{\lVert x\rVert_{2}^{2}+(mc)^{2}}$. (Franca et al., )
- ii)
*Non-relativistic kinetic energy:* $\varphi(x)=\frac{1}{2}\langle x,Ax\rangle+\langle b,x\rangle+c$, where $A$ is a positive definite, symmetric matrix, $b\in\mathbb{R}^{d}$ and $c\in\mathbb{R}$. (Goldstein et al., )
- iii)
*Gradient rescaling:*
$\varphi(x)=c\sqrt{\lVert x\rVert_{2}^{2}+\epsilon}$, for $c,\epsilon>0$.
- iv)
*Soft clipping:*
$\varphi(x)=\sqrt{1+\lVert x\rVert_{2}^{2}}$.
- v)
*The symmetric LogSumExp-function:*
$\varphi(x)=\ln\left(\sum_{i=1}^{d}e^{x_{i}}+e^{-x_{i}}\right)$, which can be seen as an approximation of the $\ell^{\infty}$-norm (Sherman, ).
- vi)
*Half-squared $\ell^{p}$-norm:* $\varphi(x)=\frac{1}{2}\lVert x\rVert_{p}^{2}$, for $p\in[2,\infty)$.

Examples i), iii) and iv) are analytically similar, but give rise to different behaviours in the algorithm given by (9).
We refer the reader to Beck (); Peressini et al. (), for verifying that the functions above satisfy the assumptions in Section 5.2.

## 2. Contributions

Making use of Hamiltonian dynamics, we consider a large class of stochastic optimization algorithms (9) for large-scale optimization problems, for which we perform a rigorous convergence analysis. Our assumptions on the dissipation term $\varphi$ are fairly permissive, and thus the class of algorithms covers both interesting cases like normalized SGD with momentum and various soft-clipping methods with momentum, as well as novel methods. Our analysis shows that the iterates generated by any method in this class are finite almost surely, and that they converge almost surely to the set of stationary points of the objective function $F$. This means that the methods “always” work in practice, in contrast to what can be guaranteed by analyses that show convergence in expectation. These results are valid in many applications, due to fairly weak assumptions on the optimization problem. The exact assumptions are listed in Section 5 but essentially consist of either

- •
$L$-smooth objective functions and stochastic gradients with possibly infinite variance, or
- •
$(L_{0},L_{1})$-smooth objective functions and heavy-tailed stochastic gradients with bounded variance, or
- •
$(L_{0},L_{1})$-smooth objective functions arising in the empirical risk minimization setting and stochastic gradients with possibly infinite variance but bounded expectation.

In particular, we do not assume convexity of the objective function $F$ in any of the cases.

## 3. Outline

In Section 4, we briefly discuss some results that are related to the analysis in this paper. The main results and analysis is presented in Section 5, with conclusions in Section 6. The details of the analysis can be found in Appendix A. This depends on some auxiliary results listed in Appendix B. Finally, Appendix C presents a few numerical experiments that illustrate the behaviour of the methods.

## 4. Related works

In the first subsection we consider other formulations of SGD with momentum and how the formulation in this
paper relates to them.
In the second subsection we summarize work in optimization and statistics which make use of Hamiltonian dynamics.
Next, we discuss the approach we use for showing almost sure convergence of the methods. Finally, we discuss the central $(L_{0},L_{1})-$smoothness condition on the objective function.

### 4.1. Momentum algorithms

The implementations of SGD with momentum in the libraries Tensorflow (Abadi et al., ) and Pytorch (Paszke et al., ) are equivalent to (5) after a transformation of the learning rate:

$$ $\displaystyle\begin{split}p_{k+1}&=\beta_{k}p_{k}-\alpha_{k}\nabla f(q_{k},\xi _{k})\\ q_{k+1}&=q_{k}+p_{k+1}.\end{split}$ $$

Typically the momentum parameter $\beta_{k}$ is a fixed number. The update
(5) resembles the (hard-clipped) scheme proposed in Mai & Johansson ():

$$ $\displaystyle\begin{split}p_{k+1}&=\text{clip}_{r}\left((1-\beta_{k})p_{k}- \beta_{k}\nabla f(q_{k},\xi_{k})\right),\\ q_{k+1}&=q_{k}+\alpha_{k}p_{k+1},\end{split}$ $$

where $\text{clip}_{r}$ is a projection operator that projects the argument onto a ball of radius $r$ at the origin.
The algorithm generated by
(5) is also reminiscent of
Stochastic Primal Averaging (SPA) (Defazio, ):

$$ $\displaystyle p_{k+1}$ $\displaystyle=p_{k}-\eta_{k}\nabla f(q_{k},\xi_{k}),$ $\displaystyle q_{k+1}$ $\displaystyle=(1-c_{k+1})q_{k}+c_{k+1}p_{k+1}.$ $$

In Theorem 1 in Defazio () it is shown that this is equivalent to SGD with momentum version

$$ $\displaystyle p_{k+1}$ $\displaystyle=\beta_{k}p_{k}+\nabla f(q_{k},\xi_{k}),$ $\displaystyle q_{k+1}$ $\displaystyle=q_{k}-\alpha_{k}p_{k+1},$ $$

if one takes $\eta_{k+1}=\frac{\eta_{k}-\alpha_{k}}{\beta_{k+1}}$
and $c_{k+1}=\frac{\alpha_{k}}{\eta_{k}}$.
The SPA algorithm can be seen as a randomized implicit-explicit Euler discretization of the equation system

$$ $\displaystyle\dot{p}$ $\displaystyle=-\nabla F(q),$ $\displaystyle\dot{q}$ $\displaystyle=p-q,$ $$

which after a change of variable is equivalent with (6) for $\gamma=1$.
Under the rather strong assumptions that the noise is almost surely bounded(^1^11This does for instance not hold for Gaussian noise.), so-called mixed-clipped SGD with momentum was studied in Zhang et al. ():

$$ $\displaystyle p_{k+1}$ $\displaystyle=\beta p_{k}-(1-\beta)\nabla f(q_{k},\xi_{k}),$ $\displaystyle q_{k+1}$ $\displaystyle=q_{k}-\biggl{[}\nu\min\Big{(}\eta,\frac{\gamma}{\lVert p_{k+1} \rVert_{2}}\Big{)}p_{k+1}$ $\displaystyle\qquad\qquad+(1-\nu)\min\Big{(}\eta,\frac{\gamma}{\lVert\nabla f( q_{k},\xi_{k})\rVert_{2}}\Big{)}\nabla f(q_{k},\xi_{k})\biggr{]},$ $$

Here, $0\leq\nu\leq 1$ is an interpolation parameter.

A drawback with the previously mentioned analyses is that the convergence results are obtained in expectation, which means that there is no guarantee that a single path will converge.

### 4.2. Hamiltonian dynamics

Hamiltonian dynamics, in its energy conserving form, has been well-explored in the Markov chain Monte Carlo field, compare Leimkuhler & Matthews (). In Livingstone et al. (), various kinetic energy functions $\varphi$ are considered for equation (8) without the dissipation term $\nabla_{\dot{q}}\mathcal{R}(\dot{q})$.

The algorithm (9) was studied in the context of stochastic differential equations and Langevin dynamics in
Stoltz & Trstanova (), where the noise is assumed to be Gaussian. In general, this is however a restrictive assumption in the stochastic optimization setting.

The specific update
(10) bears resemblance to deterministic time integration- and optimization schemes studied in Franca et al. (), that arise as discretizations of the system

$$ (11) $\displaystyle\begin{split}\dot{p}&=-\nabla_{q}H(p,q)-\gamma p,\\ \dot{q}&=\nabla_{p}H(p,q),\end{split}$ $$

where the dissipation term $\gamma p$ emanates from *Bateman’s Lagrangian* $L(q,\dot{q})=e^{\gamma t}(\varphi^{*}(\dot{q})-F(q))$, see Bateman (). A similar point of view is also taken in Franca et al. (), but where so-called Bregman dynamics is employed.
In the (deterministic) optimization setting this was studied in Maddison et al. (), where strictly convex kinetic energy functions $\varphi$ are considered.
A stochastic gradient version is analysed in Kapoor & Harshvardhan () for strongly convex objective functions $F$.

However, the stochastic optimization algorithm has not been studied for non-convex problems, and an analysis for merely convex (and not strictly convex) kinetic energy functions is lacking.

### 4.3. Almost sure convergence

The analysis in this paper is based on the *ODE method*, emanating from Ljung ().
The particular proof strategy is due to
Kushner & Clark (), and is based on linear interpolation of the sequence of iterates.
The technique was extended to piecewise constant interpolations in Kushner & Yin ().
The approach relies on the assumption that the iterates generated by the algorithm are finite almost surely; an assumption that has to be verified independently.

A similar analysis of the SGD with momentum was performed in Gadat et al. (). It was extended in Barakat et al. (), to a class of schemes that encompasses (5).
The analytical approach is slightly different and does not cover the normalization- and clipping algorithms that we analyze in this article.

We also note that one can employ an analysis similar to that in e.g. Bottou et al. (), along with martingale results like that in Robbins & Siegmund () to obtain almost sure convergence of a subsequence of the iterates. This is for instance the case in Sebbouh et al. () where almost sure convergence guarantees of the type $\min_{0\leq k\leq K}\lVert\nabla F(q_{k})\rVert_{2}\to 0$ almost surely for SGD and SGD with momentum are established. These types of results are weaker than those obtained in this paper, since they cannot guarantee that the whole sequence of iterates $\{q_{k}\}_{k\geq 0}$ converges to a stationary point.

### 4.4. ( L 0 , L 1 ) − limit-from subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1})- ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) - smoothness

The $(L_{0},L_{1})-$smoothness assumption was introduced in Zhang et al. () as a more appropriate measure of smoothness for certain machine learning problems. It is shown in Zhang et al. () that
the iteration complexity of clipped SGD is bounded, under the assumption that the stochastic gradients are bounded almost surely. The latter is a very restrictive assumption that is not fulfilled even by Gaussian noise. In Zhang et al. () a clipped algorithm with momentum is shown to converge in expectation to a stationary point under the same strong assumptions on the noise. Similar assumptions are also encountered in e.g. Crawshaw et al. (); Li et al. ().(^2^22Li et al. () also considers the slightly more general case of *sub-Gaussian* noise.)
Koloskova et al. () analyses clipped SGD under Assumption 4.ii), but do not obtain a convergence guarantee due to an *unavoidable bias* (Koloskova et al., ).
Recently are Wang et al. () and Faw et al. () obtained convergence guarantees for versions of AdaGrad Norm under the weaker affine variance-assumption. These results are however only with a certain probability, and there is always some set of positive measure on which the algorithm may not converge.

The convergence guarantees that we obtain in Theorem
5.5
under Assumption 4.i) and Assumption 3.ii) is stronger in the sense that it converges for every path.
We also stress the fact that Assumption 3.ii)
is relatively weak since it covers all heavy-tailed distributions with finite variance (Rolski et al., ). This includes for instance the large class of sub-Weibull distributions, which generalizes sub-Gaussian and sub-exponential distributions (Vladimirova et al., ).

## 5. Analysis

We first give a brief overview of the analysis in Section 5.1. In Section 5.2 we describe the setting and
in Section 5.3 we give a more detailed outline of the theorems and the proofs.
The full proofs of the results are given in Appendix A.

### 5.1. Brief overview

The analysis is split into two parts.

In the first, we show that the iterates of the scheme defined by (9) are finite almost surely, if the objective function $F$ and the convex kinetic energy function $\varphi$ are $L$-smooth and coercive, or if $F$ is $(L_{0},L_{1})-$smooth and the variance is finite. This is done by constructing a Lyapunov function with the help of the Hamiltonian $H$, and then appealing to the classical Robbins–Siegmund theorem (Robbins & Siegmund, ).

In the second, we show that given that
the iterates defined by (9) are bounded, they converge almost surely to a stationary point of $F$. We make use of a modification of the *ODE method*, compare Kushner & Yin (). Since the scheme is implicit-explicit, we cannot directly apply e.g. Theorem 2.1 in Kushner & Yin ().

Essentially, the idea is to

- i)
Introduce a pseudo time $t_{k}=\sum_{i=0}^{k-1}\alpha_{i}$ and construct piecewise constant interpolations $P_{0}(t)$ and $Q_{0}(t)$ of $\{p_{k}\}_{k\geq 0}$ and $\{q_{k}\}_{k\geq 0}$ from (9).
- ii)
Show that the time shifted processes $P_{k}(t)=P_{0}(t_{k}+t)$ and $Q_{k}(t)=Q_{0}(t_{k}+t)$ are *equicontinuous in the extended sense* (Kushner & Yin, ) and that $P_{k}(t)$ and $Q_{k}(t)$ asymptotically satisfies (8).
- iii)
At last, make use of the underlying dynamics of (8) to conclude that $\{q_{k}\}_{k\geq 0}$ converges almost surely to a stationary point of $F$.

### 5.2. Setting

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, and $\{\xi_{k}\}_{k\geq 0}$ be a sequence of independent, identically distributed random variables. We further let $\mathcal{F}_{k}$ denote the $\sigma-$algebra generated by $\xi_{0},\dots,\xi_{k-1}$.
By $\mathbb{E}_{\xi_{k}}\left[X\right]$ we denote the conditional expectation of a random variable $X$ with respect to $\mathcal{F}_{k}$.
For a set $A\subset\mathbb{R}^{d}$, we let
$N_{\delta}(A)=\{x:\inf_{a\in A}\|x-a\|<\delta\}$.

#### 5.2.1. Basic assumptions

We make the following basic assumptions on $f$, $F$ and $\varphi$:

###### Assumption 1 .

The objective function $F$ is differentiable and satisfies:

- i)
*(Coercivity)* $\lim_{\lVert x\rVert_{2}\to\infty}F(x)=\infty$.
- ii)
*(Proper)* There is a number $F_{*}>-\infty$ such that $F(x)\geq F_{*},\ \forall x\in\mathbb{R}^{d}$.
- iii)
*(Locally finite cardinality)* Let $\Lambda=\{q:\nabla F(q)=0\}$. For every compact set $K\subset\mathbb{R}$, the set $F(\Lambda)\cap K$ has finite cardinality.

Further, the stochastic gradient $\nabla f$ is an unbiased estimator of $\nabla F$, i.e.

- iv)
$\mathbb{E}\left[\nabla f(x,\xi)\right]=\nabla F(x)$.

###### Remark 5.1 .

Assumption 1.i) implies that the sublevel sets $\{x:F(x)\leq c\}$ are bounded, compare Proposition 11.12 in Bauschke & Combettes ().

###### Remark 5.2 .

Assumption 1.iii) is slightly more general than the assumption that $F(\Lambda)$ has finite cardinality, which one often sees; compare e.g. Benaïm (). We make use of it in Lemma 5.16, in order to show that the sublevel sets of the Hamiltonian are locally asymptotically stable.

###### Assumption 2 .

The kinetic energy function $\varphi$ is differentiable and satisfies:

- i)
*(Lipschitz continuous $\nabla\varphi$)* There is a constant $\lambda>0$ such that $\lVert\nabla\varphi(y)-\nabla\varphi(x)\rVert_{2}\leq\lambda\lVert x-y\rVert_{2}$, for all $x,y\in\mathbb{R}^{d}$.
- ii)
*(Convexity)* For all $x,y\in\mathbb{R}^{d}$, it holds that
$\varphi(y)-\varphi(x)\leq\langle\nabla\varphi(y),y-x\rangle$.
- iii)
*(Coercivity)* $\lim_{\lVert x\rVert_{2}\to\infty}\varphi(x)=\infty$.
- iv)
*(Proper)* For all $x\in\mathbb{R}^{d}$, it holds that $\varphi(x)\geq\varphi_{*}>-\infty$.

###### Remark 5.3 .

Asumption 1.i), 1.ii), 2.iii) and 2.iv) together implies that the Hamiltonian $H(p,q)=F(q)+\varphi(p)$ is coercive as a function of $q$ and $p$.

In addition to these basic assumptions, we consider three different settings.

###### Assumption 1 .

###### Remark 5.1 .

###### Remark 5.2 .

###### Assumption 2 .

###### Remark 5.3 .

#### 5.2.2. Setting 1

In the first setting, $\nabla F$ is Lipschitz continuous but the stochastic gradients can have large variance.

###### Assumption 3 .

The objective function $F$ and the stochastic gradient $\nabla f$ further satisfy:

- i)
*(Lipschitz-continuous $\nabla F$)* There is a constant $L>0$ such that $\lVert\nabla F(y)-\nabla F(x)\rVert_{2}\leq L\lVert x-y\rVert_{2}$, for all $x,y\in\mathbb{R}^{d}$.
- ii)
*(Locally bounded variance)*
$\mathbb{V}\left[\nabla f(x,\xi)\right]\leq\kappa\left(F(x)-F_{*}\right)+\tau
\lVert\nabla F(x)\rVert_{2}^{2}+\sigma^{2}$,

where $\kappa,\sigma,\tau\geq 0$.

Assumption 3.i) implies that the inequality $F(y)-F(x)\leq\langle\nabla F(x),y-x\rangle+\frac{L}{2}\lVert x-y\rVert_{2}^{2}$ holds
for all $x,y\in\mathbb{R}^{d}$, compare Lemma 1.2.3 in  Nesterov ().
Assumption 3.ii) was first introduced in Khaled & Richtárik () where it was called as "expected smoothness". It is weak in the sense that it allows for infinite variance in the case that either the gradient or the objective function becomes infinitely large.
The condition is similar to e.g. the "affine noise variance" in Wang et al. () and the "affine variance" in Faw et al. ().

###### Assumption 3 .

#### 5.2.3. Setting 2

Alternatively, we consider the following setting, where we require less regularity of $F$ but instead restrict the variance of the stochastic gradient.

###### Assumption 4 .

The objective function $F$ and the stochastic gradient $\nabla f$ further satisfy:

- i)
*($(L_{0},L_{1})-$smoothness)*
There exists $L_{0},L_{1}$ such that for all $x,y\in\mathbb{R}^{d}$, if $\lVert x-y\rVert_{2}\leq\frac{1}{L_{1}}$, then
$\lVert\nabla F(x)-\nabla F(y)\rVert\leq\left(L_{0}+L_{1}\lVert\nabla F(y)
\rVert_{2}\right)\lVert x-y\rVert_{2}.$
- ii)
*(Bounded variance)* $\mathbb{V}\left[\nabla f(x,\xi)\right]\leq\sigma^{2}$,
- iii)
*(Bounded $\nabla\varphi$)*
There exists $\Delta>0$ such that $\lVert\nabla\varphi(x)\rVert_{2}\leq\Delta$ for all $x\in\mathbb{R}$.

Here $\mathbb{V}\left[\nabla f(x,\xi)\right]=\mathbb{E}\left[\lVert\nabla f(x,\xi)
\rVert_{2}^{2}\right]-\lVert\nabla F(x)\rVert_{2}^{2}$.

###### Remark 5.4 .

By *Lyapunov’s inequality*, compare p. 230 in Shiryaev (), it follows from Assumption 4.ii) that
$\mathbb{E}\left[\lVert\nabla f(x,\xi)-\nabla F(x)\rVert_{2}\right]\leq\sigma.$

Assumption 4.ii) sometimes called *heavy-tailed noise* assumption in the literature (Gorbunov et al., ; Koloskova et al., ). It covers all zero-mean, heavy-tailed distributions with finite second moment, compare Rolski et al. (). In particular, it also includes the large class of *sub-Weibull distributions*
(Vladimirova et al., ), which generalizes random variables of sub-Gaussian and sub-Exponential distribution.

###### Assumption 4 .

###### Remark 5.4 .

#### 5.2.4. Setting 3

Assumption 4.ii) may be restrictive in some cases, compare (Gurbuzbalaban et al., ). Therefore we also consider the the empirical risk minimization setting when the objective function is on the form (2), $f(\cdot,\xi)$ is $(L_{0},L_{1})-$smooth and $\nabla f(\cdot,\xi)$ is given by (4). In this setting, we can
further lower the assumptions on the noise to merely finite expectation:

###### Assumption 5 .

The objective function satisfies 4.i) and $\nabla\varphi$ satisfies 4.iii).
The objective function $F$ and the stochastic gradient $\nabla f$ further satisfy:

- i)
*(Empirical risk minimization)* The objective function and the stochastic gradient is of the form (2) and (4),
where each for $i$, it holds that $\inf_{q\in\mathbb{R}^{d}}f_{i}(q)>-\infty$.
- ii)
*(Bounded expectation)* The stochastic gradients satisfy
$\mathbb{E}\left[\lVert\nabla f(x,\xi)-\nabla F(x)\rVert_{2}\right]\leq\sigma.$
- iii)
*($(L_{0},L_{1})-$smooth)*
The stochastic functions $f(\cdot,\xi)$ are $(L_{0},L_{1})-$smooth.

###### Assumption 5 .

#### 5.2.5. Book-keeping assumptions

The following assumption on the step sizes $\alpha_{k}$ is standard and originates from Robbins & Monro (). Informally, the step sizes must go to zero in order to counter the stochasticity, but do so slowly enough that we have time to reach a stationary point.

###### Assumption 6 (Step sizes) .

The step size sequence $\{\alpha_{k}\}_{k\geq 0}$ satisfies $\alpha_{0}=0$ and
$\{\alpha_{k}\}_{k\geq 0}\in\ell^{2}(\mathbb{R})\backslash\ell^{1}(\mathbb{R})$.

Our analysis shows convergence to the set of stationary points of $\nabla F$. Under the following additional assumption, we get convergence to a unique stationary point:

###### Assumption 7 .

The stationary points of $F$ are isolated.

###### Assumption 6 (Step sizes) .

###### Assumption 7 .

### 5.3. Outline of proof

The proofs of the results in this section can be found in Appendix A.
The main theorem is an extension of the approach in Kushner & Yin ():

###### Theorem 5.5 .

Let Assumptions 1, 2 and 6 be satisfied, as well as either Assumption 3, 4 or 5. Then $\{q_{k}\}_{k\geq 0}$ converges almost surely to the set of stationary points of the objective function $F$.
If we additionally assume that Assumption 7 holds, the convergence is to a unique stationary point.

The following result is a direct consequence of Theorem 5.5:

###### Corollary 5.6 (Convergence in expectation) .

Let Assumptions 1, 2, 6 and 7 be valid. Further, let the Hamiltonian be on the form (7) and let the sequences$\{p_{k}\}_{k\geq 0}$ and $\{q_{k}\}_{k\geq 0}$ be generated by  (9).
Then it holds under that

$$ $\displaystyle\lim_{k\to\infty}\mathbb{E}\left[\lVert\nabla F(q_{k})\rVert_{2}^ {\theta}\right]=0,$ $$

where $\theta=1$ under Assumption 3 and
$\theta=\frac{1}{2}$ under Assumption 4 or 5.

Our proof strategy consists of two parts. In the first part we show that the sequences $\{p_{k}\}_{k\geq 0}$ and $\{q_{k}\}_{k\geq 0}$ are finite almost surely:

###### Theorem 5.7 (Finiteness of $\{p_{k}\}_{k\geq 0}$ and $\{q_{k}\}_{k\geq 0}$ ) .

Let Assumptions 1, 2 and 6 be valid, as well as either Assumption 3, 4 or 5. Further, let the Hamiltonian be on the form (7) and let the sequences$\{p_{k}\}_{k\geq 0}$ and $\{q_{k}\}_{k\geq 0}$ be generated by  (9).
Then $\{p_{k}\}_{k\geq 0}$ and $\{q_{k}\}_{k\geq 0}$ are finite almost surely. Moreover, it holds that $\sup_{k\geq 0}\mathbb{E}\left[F(q_{k})\right]<\infty$.

In the second part of the analysis, we closely follow the ODE method approach as outlined in Kushner & Yin (): We start with introducing a pseudo time $t_{k}=\sum_{i=0}^{k-1}\alpha_{i}$, and define two piecewise constant, (stochastic) interpolation processes defined by

$$ (12) $\displaystyle\begin{split}P_{0}(t)&=p_{0}I_{(-\infty,t_{0}]}(t)+\sum_{k=0}^{ \infty}p_{k}I_{[t_{k},t_{k+1})}(t),\\ Q_{0}(t)&=q_{0}I_{(-\infty,t_{0}]}(t)+\sum_{k=0}^{\infty}p_{k}I_{[t_{k},t_{k+1 })}(t).\end{split}$ $$

We next consider the shifted sequence of processes
$\{P_{k}\}_{k\geq 0}$ and $\{Q_{k}\}_{k\geq 0}$, defined by

$$ (13) $\displaystyle\begin{split}P_{k}(t)&=P_{0}(t_{k}+t),\\ Q_{k}(t)&=Q_{0}(t_{k}+t).\end{split}$ $$

We note that $\{P_{k}\}_{k\geq 0}$ and $\{Q_{k}\}_{k\geq 0}$ are stochastic processes; they depend on $\omega\in\Omega$(^3^33Here $\omega$ is an *outcome* and $\Omega$ is the *sample space* of the underlying probability space $\left(\Omega,\mathcal{F},\mathbb{P}\right)$.)
through the stochasticity of the sequences $\{p_{k}\}_{k\geq 0}$ and $\{q_{k}\}_{k\geq 0}$.
For brevity we will refrain from writing out the dependence on $\omega$.

The next step is to introduce the concept of *extended equicontinuity* (Kushner & Yin, ; Freise, ):

###### Definition 5.8 (Extended equicontinuity) .

A sequence of $\mathbb{R}^{d}$-valued functions $\{f_{k}\}_{k\geq 0}$, defined on $(-\infty,\infty)$ , is said to be *equicontinuous in the extended sense* if $\{|f_{k}(0)|\}_{k\geq 0}$ is bounded and for every $T$ and $\epsilon>0$ there is $\delta>0$ such that

$$ (14) $\displaystyle\limsup_{k\to\infty}\sup_{0<|t-s|\leq\delta,\ t,s\in[0,T]}|f_{k}( t)-f_{k}(s)|\leq\epsilon.$ $$

Following Freise (), we show that the process $\{Z_{k}\}_{k\geq 0}=\{(P_{k},Q_{k})\}_{k\geq 0}$, where $\{P_{k}\}_{k\geq 0}$ and $\{Q_{k}\}_{k\geq 0}$ defined by (13), is equicontinuous in the extended sense:

###### Lemma 5.9 (Equicontinuous in the extended sense) .

Consider $\{Z_{k}\}_{k\geq 0}=\{(P_{k},Q_{k})\}_{k\geq 0}$ where the sequences $\{P_{k}\}_{k\geq 0}$ and $\{Q_{k}\}_{k\geq 0}$
are defined by (13) (equivalently, by (37)). Suppose that $\{p_{k}\}_{k\geq 0}$ and $\{q_{k}\}_{k\geq 0}$ are defined by (9), and that the Hamiltonian is on the form (7). Further, let Assumptions 1, 2 and 6 be valid, as well as either Assumption 3, 4 or 5.
Then $\{Z_{k}\}_{k\geq 0}$ is equicontinuous in the extended sense, almost surely.

We can then appeal to the *extended/discontinuous Arzelà–Ascoli theorem* (Kushner & Yin, ; Freise, ; Droniou & Eymard, ), to conclude that $\{Z_{k}\}_{k\geq 0}$ has a subsequence that converges to a continuous function $z$:

###### Theorem 5.10 (Discontinuous Arzelà–Ascoli theorem) .

Let $\{f_{k}\}_{k\geq 0}$ be a sequence of functions, defined on $\mathbb{R}^{d}$, that is equicontinuous in the extended sense. Then there is a subsequence $\{f_{n_{k}}\}_{n_{k}\geq 0}$ of $\{f_{k}\}_{k\geq 0}$, that converges uniformly on compact sets to a continuous function.

For a proof see, e.g. Theorem 6.2 in
Droniou & Eymard () or Theorem 12.3 in Billingsley ().

With this established, we proceed to show that $\{Z_{k}\}_{k\geq 0}$ is an *asymptotic solution*(^4^44By *Grönwall’s inequality* (compare e.g. Ethier & Kurtz ()) this is equivalent to (12) being an *asymptotic pseudotrajectory* (Benaïm, ) to (8).) to (8); i.e. asymptotically $\{P_{k}\}_{k\geq 0}$ and $\{Q_{k}\}_{k\geq 0}$ satisfy (8).
More precisely we show

###### Lemma 5.11 (Asymptotic solutions) .

With the same assumptions and notation as in Lemma 5.9,
we can write

$$ (15) $\displaystyle\begin{split}P_{k}(t)=P_{k}(0)&-\int_{0}^{t}\nabla F(Q_{k}(s)) \mathrm{d}s-\gamma\int_{0}^{t}\nabla\varphi(P_{k}(s))\mathrm{d}s+M_{k}(t)+\mu_ {k}(t),\\ Q_{k}(t)=Q_{k}(0)&+\int_{0}^{t}\nabla\varphi(P_{k}(s))\mathrm{d}s+\nu_{k}(t)+ \kappa_{k}(t),\end{split}$ $$

where the functions $\{M_{k}\}_{k\geq 0}$, $\{\mu_{k}\}_{k\geq 0}$, $\{\nu_{k}\}_{k\geq 0}$ and
$\{\kappa_{k}\}_{k\geq 0}$ converge to 0 0 uniformly on compact sets almost surely.

It follows that any limit point of $\{Z_{k}\}_{k\geq 0}$ satisfies

$$ (16) $\displaystyle\begin{split}P(t)&=P(0)-\int_{0}^{t}\nabla F(Q(s))\mathrm{d}s- \gamma\int_{0}^{t}\nabla\varphi(P(s))\mathrm{d}s\\ Q(t)&=Q(0)+\int_{0}^{t}\nabla\varphi(P(s))\mathrm{d}s.\end{split}$ $$

The limits we can extract by appealing to Theorem 5.10 are continuous. Thus it follows from (16) and the fundamental theorem of calculus that they are differentiable and satisfy (8).

###### Remark 5.12 .

The functions $\{\mu_{k}\}_{k\geq 0}$ and $\{\nu_{k}\}_{k\geq 0}$ are essentially what is left when we have rewritten the sums in (12) as integrals.
The functions $\{M_{k}\}_{k\geq 0}$ account for the difference between $\nabla F(q_{k})$ and $\nabla f(q_{k},\xi_{k})$ and $\kappa_{k}(t)$ for the implicit discretization in the second equation of (9).

###### Remark 5.13 .

The convergence “uniformly on compact sets almost surely” is to be understood as uniformly on compact sets in $t$ and almost surely in $\omega$.
For example, for the sequence $\{M_{k}\}_{k\geq 0}$ we have that for any compact set $K\subset\mathbb{R}$, $\lim_{k\to\infty}\sup_{t\in K}\lVert M_{k}(t)(\omega)\rVert_{2}=0$
for almost all $\omega\in\Omega$.

We recall the definition of a *locally asymptotically stable set* (Borkar, ; Kushner & Yin, ):

###### Definition 5.14 (Locally asymptotically stable set) .

A set $A$ is said to be *Lyapunov
stable* if for any $\epsilon>0$, there exists a $\delta>0$ such that every trajectory initiated
in the $N_{\delta}(A)$ remains in $N_{\epsilon}(A)$. It is *locally asymptotically stable* if every such path ultimately goes to $A$.

With this in mind, we show the following theorem, which is essentially an adaptation of Theorem 5.2.1 in Kushner & Yin ().

###### Theorem 5.15 .

Under the same assumptions and notation as in Theorem 5.5, let $A$ be a locally asymptotically stable set for (8). If there exists a compact set in the domain of attraction of $A$ that $\{z_{k}\}_{k\geq 0}$ visits infinitely often, then $z_{k}\to A$ almost surely:

$$ (17) $\displaystyle\lim_{k\to\infty}\inf_{a\in A}\lVert z_{k}-a\rVert_{\ell^{2}\left (\mathbb{R}^{2d}\right)}=0,\ \text{ a.s.}$ $$

The next step is to prove the following, which gives us specific locally asymptotically stable sets:

###### Lemma 5.16 .

Consider the same assumptions and notation as in Theorem 5.5.
For each $c$, if the set $\{z:H(z)\leq c\}$ is non-empty, it is a locally asymptotically stable set for the solutions to (8).

In particular, the set $A=\{z:H(z)\leq\liminf_{k}H(z_{k})\}$ is locally asymptotically stable. By the properties of $\liminf$, we can also find a compact set which $z_{k}$ enters infinitely often, and we can therefore apply Theorem 5.15 to conclude that $z_{k}\to A$. The final step is to show that this convergence in fact implies convergence to the set of stationary points of $H$, and therefore that $q_{k}$ converges to the set of stationary points of $F$. Under Assumption 7 we can additionally conclude that the convergence is to a unique equilibrium.

###### Theorem 5.5 .

###### Corollary 5.6 (Convergence in expectation) .

###### Theorem 5.7 (Finiteness of { p k } k ≥ 0 subscript subscript 𝑝 𝑘 𝑘 0 \{p_{k}\}_{k\geq 0} { italic_p start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k ≥ 0 end_POSTSUBSCRIPT and { q k } k ≥ 0 subscript subscript 𝑞 𝑘 𝑘 0 \{q_{k}\}_{k\geq 0} { italic_q start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k ≥ 0 end_POSTSUBSCRIPT ) .

###### Definition 5.8 (Extended equicontinuity) .

###### Lemma 5.9 (Equicontinuous in the extended sense) .

###### Theorem 5.10 (Discontinuous Arzelà–Ascoli theorem) .

###### Lemma 5.11 (Asymptotic solutions) .

###### Remark 5.12 .

###### Remark 5.13 .

###### Definition 5.14 (Locally asymptotically stable set) .

###### Theorem 5.15 .

###### Lemma 5.16 .

## 6. Conclusions

In this paper, we have shown that the stochastic Hamiltonian descent algorithm (9), arising as a stochastic explicit-implicit Euler discretization of (8), under weak assumptions converges almost surely to the set of stationary points of the objective function $F$.
In the terminology of Robbins & Monro (), this means that the estimator determined by $\{q_{k}\}$ is a strongly consistent estimator of a stationary point of $F$. (Here, the designated asymptoticity is with respect to the number of iterations instead of the sample size.) Similarly, the result in Corollary 5.6 is akin to $\{q_{k}\}_{k\geq 0}$ being an asymptotically unbiased estimator of a stationary point $q_{*}$.

## Appendix A Analysis

As explained in Section 5.3, the two main steps of the convergence analysis are to first prove that $p_{k}$ and $q_{k}$ are finite almost surely, and then to use this a priori result to show that they in fact converge.

### A.1. The sequences { p k } k ≥ 0 subscript subscript 𝑝 𝑘 𝑘 0 \{p_{k}\}_{k\geq 0} { italic_p start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k ≥ 0 end_POSTSUBSCRIPT and { q k } k ≥ 0 subscript subscript 𝑞 𝑘 𝑘 0 \{q_{k}\}_{k\geq 0} { italic_q start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k ≥ 0 end_POSTSUBSCRIPT are finite almost surely

We first prove Theorem 5.7:
See 5.7
The proof relies on the Robbins-Siegmund theorem:

###### Theorem A.1 ( (Robbins & Siegmund, 1971 ) ) .

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and
$\mathcal{F}_{1}\subset\mathcal{F}_{2}\subset\dots$ be a sequence of sub-$\sigma$-algebras of $\mathcal{F}$.
For each $k=1,2,\dots$ let $V_{k},\beta_{k},X_{k}$ and $Y_{k}$ be
non-negative $\mathcal{F}_{k}$-measurable random variables such that

$$ $\displaystyle\mathbb{E}\left[V_{k+1}|\mathcal{F}_{k}\right]\leq V_{k}(1+\beta_ {k})+X_{k}-Y_{k}.$ $$

Then $\lim_{k\to\infty}V_{k}$ exists and is finite and $\sum_{k}Y_{k}<\infty$ on the set

$$ $\displaystyle\left\{\omega:\sum_{k}\beta_{k}<\infty,\sum_{k}X_{k}<\infty\right\}.$ $$

We first consider Setting 1, i.e. with Assumption 3.
The strategy is to introduce $V_{k}=H(p_{k},q_{k})-F_{*}-\varphi_{*}=F(q_{k})-F_{*}+\varphi(p_{k})-\varphi_{*}$, then use $L$-smoothness of $F$ and the convexity of $\varphi$ to bound the difference $V_{k+1}-V_{k}$ by
$\alpha_{k}^{2}V_{k}$ plus higher-order terms of $\alpha_{k}$. Then we can appeal to Theorem A.1 to conclude that $\{p_{k}\}_{k\geq 1}$ and $\{q_{k}\}_{k\geq 1}$ are finite a.s.

###### Proof of Theorem 5.7 in Setting 1.

Let $V_{k}=H(p_{k},q_{k})-F_{*}-\varphi_{*}$.
Then we have that

$$ (18) $\displaystyle V_{k+1}-V_{k}=F(q_{k+1})-F(q_{k})+\varphi(p_{k+1})-\varphi(p_{k}).$ $$

By $L$-smoothness of $F$ and convexity of $\varphi$, this is less than or equal to

$$ $\displaystyle\langle\nabla F(q_{k}),q_{k+1}-q_{k}\rangle+\frac{L}{2}\lVert q_{ k+1}-q_{k}\rVert_{2}^{2}+\langle\nabla\varphi(p_{k+1}),p_{k+1}-p_{k}\rangle.$ $$

We insert (9) into the previous expression to obtain that it is equal to

$$ $\displaystyle I_{1}+I_{2}+I_{3}:$ $\displaystyle=\alpha_{k}\langle\nabla F(q_{k})-\nabla f(q_{k},\xi_{k}),\nabla \varphi(p_{k+1})\rangle$ $\displaystyle\quad+\frac{L\alpha_{k}^{2}}{2}\lVert\nabla\varphi(p_{k+1})\rVert _{2}^{2}-\alpha_{k}\gamma\langle\nabla\varphi(p_{k+1}),\nabla\varphi(p_{k})\rangle.$ $$

We add and subtract $\alpha_{k}\langle\nabla F(q_{k})-\nabla f(q_{k},\xi_{k}),\nabla\varphi(p_{k})\rangle$ to the first term:

$$ $\displaystyle I_{1}$ $\displaystyle=\alpha_{k}\langle\nabla F(q_{k})-\nabla f(q_{k},\xi_{k}),\nabla \varphi(p_{k})\rangle$ $\displaystyle\quad+\alpha_{k}\langle\nabla F(q_{k})-\nabla f(q_{k},\xi_{k}), \nabla\varphi(p_{k+1})-\nabla\varphi(p_{k})\rangle.$ $$

When we take the conditional expectation (w.r.t. the sigma algebra generated by $\xi_{1},\dots,\xi_{k-1}$) of $I_{1}$, the first term is 0 0 by the unbiasedness of the gradient and the independence of $\{\xi_{k}\}$:

$$ $\displaystyle\mathbb{E}_{\xi_{k}}\left[I_{1}\right]=\alpha_{k}\mathbb{E}_{\xi_ {k}}\left[\langle\nabla F(q_{k})-\nabla f(q_{k},\xi_{k}),\nabla\varphi(p_{k+1} )-\nabla\varphi(p_{k})\rangle\right].$ $$

Using Assumption 2.i), we can bound $I_{3}$ as

$$ $\displaystyle I_{3}$ $\displaystyle=-\alpha_{k}\gamma\langle\nabla\varphi(p_{k+1}),\nabla\varphi(p_{ k})\rangle$ $\displaystyle\leq\frac{\alpha_{k}\gamma}{2}\lVert\nabla\varphi(p_{k+1})-\nabla \varphi(p_{k})\rVert_{2}^{2}$ $\displaystyle\leq\frac{\alpha_{k}\gamma\lambda^{2}}{2}\lVert p_{k+1}-p_{k} \rVert_{2}^{2}.$ $$

After taking the expectation of (18), we thus get
the bound

$$ (19) $\displaystyle\begin{split}\mathbb{E}_{\xi_{k}}\left[V_{k+1}\right]-V_{k}&\leq \alpha_{k}\mathbb{E}_{\xi_{k}}\left[\langle\nabla F(q_{k})-\nabla f(q_{k},\xi_ {k}),\nabla\varphi(p_{k+1})-\nabla\varphi(p_{k})\rangle\right]\\ &\quad+\frac{L\alpha_{k}^{2}}{2}\mathbb{E}_{\xi_{k}}\left[\lVert\nabla\varphi( p_{k+1})\rVert_{2}^{2}\right]+\frac{\alpha_{k}\gamma\lambda^{2}}{2}\mathbb{E}_ {\xi_{k}}\left[\lVert p_{k+1}-p_{k}\rVert_{2}^{2}\right]\\ &=:I_{1}^{\prime}+I_{2}+I_{3}^{\prime}.\end{split}$ $$

We now make use of Cauchy–Schwarz inequality along with the Lipschitz continuity of $\nabla\varphi$ to bound $I_{1}^{\prime}$ as

$$ $\displaystyle I_{1}^{\prime}$ $\displaystyle\leq\alpha_{k}\lambda\mathbb{E}_{\xi_{k}}\left[\lVert\nabla F(q_{ k})-\nabla f(q_{k},\xi_{k})\rVert_{2}\lVert p_{k+1}-p_{k}\rVert_{2}\right].$ $$

We insert (9) into the previous expression, and make use of Young’s inequality for products, $ab\leq\frac{a^{2}}{2}+\frac{b^{2}}{2}$, to obtain that

$$ $\displaystyle I_{1}^{\prime}$ $\displaystyle\leq\alpha_{k}^{2}\lambda\mathbb{E}_{\xi_{k}}\left[\lVert\nabla F (q_{k})-\nabla f(q_{k},\xi_{k})\rVert_{2}\lVert\nabla f(q_{k},\xi_{k})+\gamma \nabla\varphi(p_{k})\rVert_{2}\right]$ $\displaystyle\leq\frac{\alpha_{k}^{2}}{2}\lambda\mathbb{E}_{\xi_{k}}\left[ \lVert\nabla F(q_{k})-\nabla f(q_{k},\xi_{k})\rVert_{2}^{2}\right]+\frac{ \alpha_{k}^{2}}{2}\lambda\mathbb{E}_{\xi_{k}}\left[\lVert\nabla f(q_{k},\xi_{k })+\gamma\nabla\varphi(p_{k})\rVert_{2}^{2}\right].$ $$

Making use of the inequality

$$ (20) $\displaystyle\lVert x-y\rVert_{2}^{2}\leq 2\lVert x\rVert_{2}^{2}+2\lVert y \rVert_{2}^{2},$ $$

we can further bound $I_{1}^{\prime}$ by

$$ $\displaystyle I_{1}^{\prime}$ $\displaystyle\leq\frac{\alpha_{k}^{2}}{2}\lambda\mathbb{E}_{\xi_{k}}\left[ \lVert\nabla F(q_{k})-\nabla f(q_{k},\xi_{k})\rVert_{2}^{2}\right]$ $\displaystyle\quad+\alpha_{k}^{2}\lambda\mathbb{E}_{\xi_{k}}\left[\lVert\nabla f (q_{k},\xi_{k})\rVert_{2}^{2}\right]+\alpha_{k}^{2}\lambda\gamma^{2}\mathbb{E} _{\xi_{k}}\left[\lVert\nabla\varphi(p_{k})\rVert_{2}^{2}\right].$ $$

At last we make use of Assumption 3.ii) to get that

$$ $\displaystyle I_{1}^{\prime}$ $\displaystyle\leq\frac{\alpha_{k}^{2}}{2}\lambda\left(\kappa(F(q_{k})-F_{*})+ \tau\lVert\nabla F(q_{k})\rVert_{2}^{2}+\sigma^{2}\right)$ $\displaystyle\quad+\alpha_{k}^{2}\lambda\left(\kappa(F(q_{k})-F_{*})+(1+\tau) \lVert\nabla F(q_{k})\rVert_{2}^{2}+\sigma^{2}\right)+\alpha_{k}^{2}\lambda \gamma^{2}\mathbb{E}_{\xi_{k}}\left[\lVert\nabla\varphi(p_{k})\rVert_{2}^{2} \right].$ $$

We now turn our attention to the term $I_{2}$ in (19). Adding and subtracting $\nabla\varphi(p_{k})$ and making use of Assumption 2.i) we get that

$$ $\displaystyle I_{2}$ $\displaystyle\leq\frac{L\alpha_{k}^{2}}{2}\mathbb{E}_{\xi_{k}}\left[\lVert \nabla\varphi(p_{k+1})-\nabla\varphi(p_{k})\rVert_{2}^{2}\right]+\frac{L\alpha _{k}^{2}}{2}\mathbb{E}_{\xi_{k}}\left[\lVert\nabla\varphi(p_{k})\rVert_{2}^{2}\right]$ $\displaystyle\leq\frac{L\lambda^{2}\alpha_{k}^{2}}{2}\mathbb{E}_{\xi_{k}}\left [\lVert p_{k+1}-p_{k}\rVert_{2}^{2}\right]+\frac{L\alpha_{k}^{2}}{2}\lVert \nabla\varphi(p_{k})\rVert_{2}^{2}$ $\displaystyle\leq L\alpha_{k}^{4}\lambda^{2}\mathbb{E}_{\xi_{k}}\left[\lVert \nabla f(q_{k},\xi_{k})\rVert_{2}^{2}\right]+\left(L\alpha_{k}^{4}\gamma^{2} \lambda^{2}+\frac{L\alpha_{k}^{2}}{2}\right)\lVert\nabla\varphi(p_{k})\rVert_{ 2}^{2},$ $$

where we have made use of (9) and (20) in the last step.
Making use of Assumption 2.i) again we obtain that

$$ $\displaystyle I_{2}$ $\displaystyle\leq L\alpha_{k}^{4}\lambda^{2}\left(\kappa(F(q_{k})-F_{*})+(1+ \tau)\lVert\nabla F(q_{k})\rVert_{2}^{2}+\sigma^{2}\right)$ $\displaystyle\quad+\left(L\alpha_{k}^{3}\gamma^{2}\lambda^{2}+\frac{L\alpha_{k }^{2}}{2}\right)\lVert\nabla\varphi(p_{k})\rVert_{2}^{2}.$ $$

In a similar way, we find that

$$ $\displaystyle I_{3}^{\prime}\leq\alpha_{k}^{3}\gamma\lambda^{2}\left(\kappa(F( q_{k})-F_{*})+(1+\tau)\lVert\nabla F(q_{k})\rVert_{2}^{2}+\sigma^{2}\right)+ \alpha_{k}^{3}\gamma^{3}\lambda^{2}\lVert\nabla\varphi(p_{k})\rVert_{2}^{2}.$ $$

Gathering up the terms, we get that

$$ $\displaystyle\begin{split}&\mathbb{E}_{\xi_{k}}\left[V_{k+1}\right]-V_{k}\\ &\quad\leq\left(\frac{\alpha_{k}^{2}\lambda}{2}+\alpha_{k}^{2}\lambda+L\alpha_ {k}^{4}\lambda^{2}+\alpha_{k}^{3}\gamma\lambda^{2}\right)\sigma^{2}\\ &\qquad+\alpha_{k}^{2}\kappa\lambda\left(\frac{3}{2}+L\alpha_{k}^{2}\lambda+ \alpha_{k}\gamma\lambda\right)(F(q_{k})-F_{*})\\ &\qquad+\left(\frac{\alpha_{k}^{2}\lambda\tau}{2}+\alpha_{k}^{2}\lambda(1+\tau )+L\alpha_{k}^{4}\lambda^{2}(1+\tau)+\alpha_{k}^{3}\gamma\lambda^{2}(1+\tau) \right)\lVert\nabla F(q_{k})\rVert_{2}^{2}\\ &\qquad+\left(\alpha_{k}^{2}\gamma^{2}\lambda+L\alpha_{k}^{4}\lambda^{2}\gamma ^{2}+\frac{L\alpha_{k}^{2}}{2}+\alpha_{k}^{3}\gamma^{3}\lambda^{2}\right) \lVert\nabla\varphi(p_{k})\rVert_{2}^{2}.\end{split}$ $$

Making use of Lemma 5.6, we see that

$$ (21) $\displaystyle\begin{split}&\mathbb{E}_{\xi_{k}}\left[V_{k+1}\right]-V_{k}\\ &\quad\leq\left(\frac{\alpha_{k}^{2}\lambda}{2}+\alpha_{k}^{2}\lambda+L\alpha_ {k}^{4}\lambda^{2}+\alpha_{k}^{3}\gamma\lambda^{2}\right)\sigma^{2}\\ &\qquad+(F(q_{k})-F_{*})\left[\alpha_{k}^{2}\kappa\lambda\left(\frac{3}{2}+L \alpha_{k}^{2}\lambda+\alpha_{k}\gamma\lambda\right)\right.\\ &\qquad\quad+\left.2L\left(\frac{\alpha_{k}^{2}\lambda\tau}{2}+\alpha_{k}^{2} \lambda(1+\tau)+L\alpha_{k}^{4}\lambda^{2}(1+\tau)+\alpha_{k}^{3}\gamma\lambda ^{2}(1+\tau)\right)\right]\\ &\qquad+\left(\alpha_{k}^{2}\gamma^{2}\lambda+L\alpha_{k}^{4}\lambda^{2}\gamma ^{2}+\frac{L\alpha_{k}^{2}}{2}+\alpha_{k}^{3}\gamma^{3}\lambda^{2}\right)( \varphi(p_{k})-\varphi_{*}).\end{split}$ $$

Now define

$$ $\displaystyle C_{1}(\alpha_{k})=\sigma^{2}\left(\frac{\alpha_{k}^{2}\lambda}{2 }+\alpha_{k}^{2}\lambda+L\alpha_{k}^{4}\lambda^{2}+\alpha_{k}^{3}\gamma\lambda ^{2}\right)$ $$

and let $C_{2}(\alpha_{k})$ be the maximum of the terms in front of $F(q_{k})-F_{*}$ and $\varphi(p_{k})-\varphi_{*}$.
It follows that

$$ (22) $\displaystyle\mathbb{E}_{\xi_{k}}\left[V_{k+1}\right]-V_{k}\leq C_{1}(\alpha_{ k})+C_{2}(\alpha_{k})V_{k}.$ $$

Since $C_{1}$ and $C_{2}$ only contain second-order terms of $\alpha_{k}$ (and by assumption $\sum_{k=1}^{\infty}\alpha_{k}^{2}<\infty$), we have that

$$ $\displaystyle\sum_{k=0}^{\infty}C_{1}(\alpha_{k})<\infty,\ \sum_{k=0}^{\infty} C_{2}(\alpha_{k})<\infty.$ $$

We can thus make use of the Robbins–Siegmund theorem with $\beta_{k}=C_{2}(\alpha_{k})$, $X_{k}=C_{1}(\alpha_{k})$ and $Y_{k}=0$ to conclude that $V_{k}$ tends to a non-negative, finite, random variable $V$ almost surely.
Since $F$ and $\varphi$ are assumed to be coercive, this implies that $\{p_{k}\}_{k\geq 1}$ and $\{q_{k}\}_{k\geq 1}$ are finite almost surely.
For the second claim of the proof, we define

$$ $\displaystyle S_{k}=\frac{V_{k}}{\prod_{j=0}^{k-1}(1+C_{2}(\alpha_{j}))}.$ $$

By (22), we have that

$$ $\displaystyle\mathbb{E}_{\xi_{k}}\left[S_{k+1}\right]\leq S_{k}+\frac{C_{1}( \alpha_{k})}{\prod_{j=0}^{k}(1+C_{2}(\alpha_{j}))}\leq S_{k}+C_{1}(\alpha_{k}).$ $$

Taking the expectation and, summing from 0 0 to $K-1$, we see that

$$ $\displaystyle\mathbb{E}\left[S_{K}\right]\leq S_{0}+\sum_{k=0}^{K-1}C_{1}( \alpha_{k}).$ $$

We multiply both sides of the previous inequality with $\prod_{k=0}^{K-1}(1+C_{2}(\alpha_{k}))$

$$ $\displaystyle\mathbb{E}\left[V_{K}\right]$ $\displaystyle\leq\prod_{k=0}^{K-1}(1+C_{2}(\alpha_{k}))\left(S_{0}+\sum_{k=0}^ {K-1}C_{1}(\alpha_{k})\right)$ $\displaystyle\leq e^{\sum_{j=0}^{K-1}C_{2}(\alpha_{k}))}\cdot\left(S_{0}+\sum_ {k=0}^{K-1}C_{1}(\alpha_{k})\right),$ $$

where we have used the fact that $1+x\leq e^{x}$ in the second step.
Letting $K$ tend to infinity on the left hand side and using the fact that $\sum_{k=0}^{\infty}C_{2}(\alpha_{k}))<\infty$ we see that the last claim of the theorem also holds:

$$ $\displaystyle\sup_{k}\mathbb{E}\left[V_{k}\right]<\infty.$ $$

∎

We now give a proof of Theorem 5.7 in Setting 2, i.e. with Assumption 4.

###### Proof of Theorem 5.7 in Setting 2.

By Assumption 4.i)
it holds for $\lVert x_{k}-x_{k+1}\rVert\leq\frac{1}{L_{1}}$ that

$$ (23) $\displaystyle F(x_{k+1})-F(x_{k})\leq\langle\nabla F(x_{k}),x_{k+1}-x_{k} \rangle+\frac{L_{0}+L_{1}\lVert\nabla F(x_{k})\rVert}{2}\lVert x_{k+1}-x_{k} \rVert^{2}.$ $$

Since

$$ (24) $\displaystyle q_{k+1}-q_{k}=\alpha_{k}\nabla\varphi(p_{k+1})$ $$

we get for large enough $k$ that

$$ (25) $\displaystyle\lVert q_{k+1}-q_{k}\rVert=\alpha_{k}\lVert\nabla\varphi(p_{k+1}) \rVert\leq\alpha_{k}\Delta\leq\frac{1}{L_{1}},$ $$

by Assumption 4.iii).
If we insert (24) into (23), we get

$$ (26) $\displaystyle F(q_{k+1})-F(q_{k})$ $\displaystyle\leq\langle\nabla F(q_{k}),q_{k+1}-q_{k}\rangle+\frac{L_{0}}{2} \lVert q_{k+1}-q_{k}\rVert^{2}$ (27) $\displaystyle\quad+\frac{L_{1}}{2}\lVert\nabla F(q_{k})\rVert\lVert q_{k+1}-q_ {k}\rVert^{2}.$ $$

By (25), we get that

$$ (28) $\displaystyle F(q_{k+1})-F(q_{k})\leq\alpha_{k}\langle\nabla F(q_{k}),\nabla \varphi(p_{k+1})\rangle+\frac{L_{0}}{2}\alpha_{k}^{2}\Delta^{2}+\frac{L_{1}}{2 }\lVert\nabla F(q_{k})\rVert\alpha_{k}^{2}\Delta^{2}.$ $$

By Assumption 2.ii) we have that

$$ $\displaystyle\varphi(p_{k+1})-\varphi(p_{k})$ $\displaystyle\leq\langle\nabla\varphi(p_{k+1}),p_{k+1}-p_{k}\rangle$ $\displaystyle=-\alpha_{k}\langle\nabla\varphi(p_{k+1}),\nabla f(q_{k},\xi_{k}) \rangle-\alpha_{k}\gamma\langle\nabla\varphi(p_{k+1}),\nabla\varphi(p_{k})\rangle$ $$

With $H(p,q)=F(q)+\varphi(p)$ and $V_{k}=H(p_{k},q_{k})-F_{*}-\varphi_{*}$
as in the previous proof we thus get that

$$ $\displaystyle V_{k+1}-V_{k}$ $\displaystyle\leq\alpha_{k}\langle\nabla F(q_{k}),\nabla\varphi(p_{k+1}) \rangle+\frac{L_{0}}{2}\alpha_{k}^{2}\Delta^{2}+\frac{\alpha_{k}^{2}L_{1}}{2} \lVert\nabla F(q_{k})\rVert\Delta^{2}$ $\displaystyle-\alpha_{k}\langle\nabla\varphi(p_{k+1}),\nabla f(q_{k},\xi_{k}) \rangle-\alpha_{k}\gamma\langle\nabla\varphi(p_{k+1}),\nabla\varphi(p_{k})\rangle,$ $$

which can be rewritten as

$$ $\displaystyle V_{k+1}-V_{k}$ $\displaystyle\leq\alpha_{k}\langle\nabla F(q_{k})-\nabla f(q_{k},\xi_{k}), \nabla\varphi(p_{k+1})\rangle+\frac{L_{0}}{2}\alpha_{k}^{2}\Delta^{2}$ $\displaystyle\quad+\frac{\alpha_{k}^{2}L_{1}}{2}\lVert\nabla F(q_{k})\rVert \Delta^{2}-\alpha_{k}\gamma\langle\nabla\varphi(p_{k+1}),\nabla\varphi(p_{k})\rangle.$ $$

We add and subtract $\nabla\varphi(p_{k})$ in the first scalar product:

$$ (29) $\displaystyle\begin{split}V_{k+1}-V_{k}&\leq\alpha_{k}\langle\nabla F(q_{k})- \nabla f(q_{k},\xi_{k}),\nabla\varphi(p_{k+1})-\nabla\varphi(p_{k})\rangle\\ &\quad+\alpha_{k}\langle\nabla F(q_{k})-\nabla f(q_{k},\xi_{k}),\nabla\varphi( p_{k})\rangle\\ &\quad+\frac{L_{0}}{2}\alpha_{k}^{2}\Delta^{2}+\frac{\alpha_{k}^{2}L_{1}}{2} \lVert\nabla F(q_{k})\rVert\Delta^{2}-\alpha_{k}\gamma\langle\nabla\varphi(p_{ k+1}),\nabla\varphi(p_{k})\rangle.\end{split}$ $$

The second scalar product disappears due to the unbiasedness of $\nabla f(q_{k},\xi_{k})$ and the fact that $\xi_{k}$ is independent of $q_{k}$ and $p_{k}$.
We now focus on the first scalar product in (29). Taking the conditional expectation and using Cauchy–Schwarz inequality, we see that

$$ $\displaystyle\alpha_{k}\mathbb{E}_{\xi_{k}}\left[\langle\nabla F(q_{k})-\nabla f (q_{k},\xi_{k}),\nabla\varphi(p_{k+1})-\nabla\varphi(p_{k})\rangle\right]$ $\displaystyle\qquad\leq\alpha_{k}\mathbb{E}_{\xi_{k}}\left[\lVert\nabla F(q_{k })-\nabla f(q_{k},\xi_{k})\rVert\lVert\nabla\varphi(p_{k+1})-\nabla\varphi(p_{ k})\rVert\right]$ $$

Using the Lipschitz continuity of $\nabla\varphi$, this can be further bounded as

$$ (30) $\displaystyle\begin{split}&\alpha_{k}^{2}\lambda\mathbb{E}_{\xi_{k}}\left[ \lVert\nabla F(q_{k})-\nabla f(q_{k},\xi_{k})\rVert\lVert\nabla f(q_{k},\xi_{k })-\gamma\nabla\varphi(p_{k})\rVert\right]\\ &\qquad\leq\alpha_{k}^{2}\lambda\mathbb{E}_{\xi_{k}}\left[\lVert\nabla F(q_{k} )-\nabla f(q_{k},\xi_{k})\rVert\left(\lVert\nabla f(q_{k},\xi_{k})\rVert+ \gamma\lVert\nabla\varphi(p_{k})\rVert\right)\right].\end{split}$ $$

We now add and subtract $\nabla F(q_{k})$ inside the $\lVert\nabla f(q_{k},\xi_{k})\rVert-$term and make use of the triangle inequality to bound the previous expression by

$$ $\displaystyle\alpha_{k}^{2}\lambda\mathbb{E}_{\xi_{k}}\left[\lVert\nabla F(q_{ k})-\nabla f(q_{k},\xi_{k})\rVert\left(\lVert\nabla F(q_{k})-\nabla f(q_{k}, \xi_{k})\rVert+\lVert\nabla F(q_{k})\rVert+\gamma\Delta\right)\right]$ $\displaystyle\quad=\alpha_{k}^{2}\lambda\mathbb{E}_{\xi_{k}}\left[\lVert\nabla F (q_{k})-\nabla f(q_{k},\xi_{k})\rVert^{2}+\lVert\nabla F(q_{k})-\nabla f(q_{k} ,\xi_{k})\rVert\lVert\nabla F(q_{k})\rVert\right.$ $\displaystyle\qquad+\left.\gamma\Delta\lVert\nabla F(q_{k})-\nabla f(q_{k},\xi _{k})\rVert\right]$ $$

where we also have used the assumption that $\lVert\nabla\varphi(p_{k})\rVert\leq\Delta$.
Now, the first term can by Assumption 4.ii) be bounded by

$$ $\displaystyle\mathbb{E}_{\xi_{k}}\left[\lVert\nabla F(q_{k})-\nabla f(q_{k}, \xi_{k})\rVert^{2}\right]\leq\sigma^{2}.$ $$

By Remark 5.4, we can bound the second term as follows

$$ $\displaystyle\mathbb{E}_{\xi_{k}}\left[\lVert\nabla F(q_{k})-\nabla f(q_{k}, \xi_{k})\rVert\lVert\nabla F(q_{k})\rVert\right]\leq\sigma\lVert\nabla F(q_{k} )\rVert,$ $$

since $\xi_{k}$ is independent of $\lVert\nabla F(q_{k})\rVert$. Likewise, we can bound the last expectation by $\sigma$. Thus, we arrive at the bound

$$ (31) $\displaystyle\begin{split}&\alpha_{k}\mathbb{E}_{\xi_{k}}\left[\langle\nabla F (q_{k})-\nabla f(q_{k},\xi_{k}),\nabla\varphi(p_{k+1})-\nabla\varphi(p_{k}) \rangle\right]\\ &\qquad\leq\alpha_{k}^{2}\lambda\left(\sigma^{2}+\sigma\lVert\nabla F(q_{k}) \rVert+\gamma\Delta\sigma\right).\end{split}$ $$

We can bound the last inner product of (29) using Lemma B.1 in Zhang et al. (), taking $\mu=0$:

$$ $\displaystyle-\alpha_{k}\gamma\langle\nabla\varphi(p_{k+1}),\nabla\varphi(p_{k })\rangle$ $\displaystyle\qquad\leq-\alpha_{k}\gamma\lVert\nabla\varphi(p_{k})\rVert^{2}+ \alpha_{k}\gamma\lVert\nabla\varphi(p_{k+1})-\nabla\varphi(p_{k})\rVert\lVert \nabla\varphi(p_{k})\rVert$ $\displaystyle\qquad\leq\alpha_{k}^{2}\gamma\lambda 2\lVert\nabla f(q_{k},\xi_{ k})-\gamma\nabla\varphi(p_{k})\rVert\Delta.$ $$

By Remark 5.4 we thus get

$$ (32) $\displaystyle\begin{split}&-\alpha_{k}\gamma\mathbb{E}_{\xi_{k}}\left[\langle \nabla\varphi(p_{k+1}),\nabla\varphi(p_{k})\rangle\right]\\ &\qquad\leq\alpha_{k}^{2}\gamma\lambda\Delta\left(\mathbb{E}_{\xi_{k}}\left[ \lVert\nabla f(q_{k},\xi_{k})\rVert\right]+\gamma\lVert\nabla\varphi(p_{k}) \rVert\right)\\ &\qquad\leq\alpha_{k}^{2}\gamma\lambda\Delta\big{(}\mathbb{E}_{\xi_{k}}\left[ \lVert\nabla f(q_{k},\xi_{k})-\nabla F(q_{k})\rVert\right]+\lVert\nabla F(q_{k })\rVert_{2}+\gamma\lVert\nabla\varphi(p_{k})\rVert\big{)}\\ &\qquad\leq\alpha_{k}^{2}\gamma\lambda\Delta\left(\sigma+\lVert\nabla F(q_{k}) \rVert_{2}+\gamma\Delta\right).\end{split}$ $$

Inserting (31) and (32)
into (29), we get that

$$ (33) $\displaystyle\begin{split}\mathbb{E}_{\xi_{k}}\left[V_{k+1}\right]-V_{k}&\leq \alpha_{k}^{2}\lambda\left(\sigma^{2}+\sigma\lVert\nabla F(q_{k})\rVert+\gamma \Delta\sigma\right)+\frac{L_{0}}{2}\alpha_{k}^{2}\Delta^{2}\\ &\quad+\frac{\alpha_{k}^{2}L_{1}}{2}\lVert\nabla F(q_{k})\rVert\Delta^{2}+ \alpha_{k}^{2}\gamma\lambda\Delta\left(\sigma+\lVert\nabla F(q_{k})\rVert_{2}+ \gamma\Delta\right)\end{split}$ $$

From Lemma 5.6, we can bound the $\lVert\nabla F(q_{k})\rVert-$terms, and obtain the bound

$$ (34) $\displaystyle\begin{split}\mathbb{E}_{\xi_{k}}\left[V_{k+1}\right]-V_{k}&\leq \alpha_{k}^{2}\lambda\left(\sigma^{2}+\sigma\left(2L_{1}(F(q)-F_{*})+\frac{L_{ 0}}{L_{1}}\right)+\gamma\Delta\sigma\right)+\frac{L_{0}}{2}\alpha_{k}^{2} \Delta^{2}\\ &\quad+\frac{\alpha_{k}^{2}L_{1}}{2}\left(2L_{1}(F(q)-F_{*})+\frac{L_{0}}{L_{1 }}\right)\Delta^{2}\\ &\quad+\alpha_{k}^{2}\gamma\lambda\Delta\left(\sigma+\left(2L_{1}(F(q)-F_{*})+ \frac{L_{0}}{L_{1}}\right)+\gamma\Delta\right).\end{split}$ $$

We now define

$$ $\displaystyle C_{1}(\alpha_{k})$ $\displaystyle=\alpha_{k}^{2}\lambda\sigma 2L_{1}+\alpha_{k}^{2}L_{1}^{2}\Delta ^{2}+\alpha_{k}^{2}\gamma\lambda\Delta 2L_{1},$ $\displaystyle C_{2}(\alpha_{k})$ $\displaystyle=\alpha_{k}^{2}\lambda\sigma^{2}+\alpha_{k}^{2}\lambda\sigma\frac {L_{0}}{L_{1}}+\alpha_{k}^{2}\lambda\gamma\Delta\sigma+\alpha_{k}^{2}L_{0} \Delta^{2}$ $\displaystyle\quad+\alpha_{k}^{2}\gamma\lambda\Delta\sigma+\alpha_{k}^{2} \gamma\lambda\Delta\frac{L_{0}}{L_{1}}+\alpha_{k}^{2}\gamma^{2}\lambda\Delta^{ 2}.$ $$

We see that

$$ (35) $\displaystyle\begin{split}\mathbb{E}_{\xi_{k}}\left[V_{k+1}\right]-V_{k}&\leq C _{1}(\alpha_{k})(F(q_{k})-F_{*})+C_{2}(\alpha_{k})\\ &\leq C_{1}(\alpha_{k})(H(p_{k},q_{k})-F_{*}-\varphi_{*})+C_{2}(\alpha_{k}), \end{split}$ $$

where we have used the fact that $\varphi(p_{k})-\varphi_{*}\geq 0$.
Since $\sum_{k\geq 0}C_{i}(\alpha_{k})<\infty$ for $i=1,2$, we can appeal to the Robbins–Siegmund theorem to conclude that $\lim_{k\to\infty}V_{k}$ exists and is finite almost surely. Since $F$ and $\varphi$ are coercive this implies that $\sup_{k}\lVert p_{k}\rVert<\infty$ and $\sup_{k}\lVert q_{k}\rVert<\infty$ almost surely.

∎

###### Proof of Theorem 5.7 in Setting 3.

Let $F_{*}$ be as in Lemma 5.6. By Lemma 5.6, we have that the right-hand side of (30) can be bounded by

$$ $\displaystyle\alpha_{k}^{2}\lambda\mathbb{E}_{\xi_{k}}\left[\lVert\nabla F(q_{ k})-\nabla f(q_{k},\xi_{k})\rVert\right]\left(2L_{1}N(F(q_{k})-F_{*})+\gamma \Delta\right).$ $$

By Assumption 5.ii) this can in its turn be bounded by

$$ $\displaystyle\alpha_{k}^{2}\lambda\sigma\left(2L_{1}N(F(q_{k})-F_{*})+\gamma \Delta\right).$ $$

The rest of the proof proceeds exactly like that of Setting 2 (with suitable modifications of the constants in the bound (35)).
∎

###### Theorem A.1 ( (Robbins & Siegmund, 1971 ) ) .

###### Proof of Theorem 5.7 in Setting 1.

###### Proof of Theorem 5.7 in Setting 2.

###### Proof of Theorem 5.7 in Setting 3.

### A.2. Almost sure convergence, notation

To prove convergence, we start with rewriting the processes (13) on a form that is more reminiscent of the integral equations (16).
As in Kushner & Yin (), we use the convention that

$$ $\displaystyle\begin{split}\sum_{i=n}^{k}a_{i}&=0,\ \text{ if }k=n-1\text{ (the empty sum)},\\ \sum_{i=n}^{k}a_{i}&=-\sum_{i=k+1}^{n-1}a_{i},\ \text{ if }k<n-1.\end{split}$ $$

By introducing the function

$$ (36) $\displaystyle m(t)=\begin{cases}j,\ t_{j}\leq t<t_{j+1},\\ 0,\ t\leq 0,\end{cases}$ $$

we can write (13) as

$$ (37) $\displaystyle\begin{split}P_{k}(t)&=p_{k}+\sum_{i=k}^{m(t_{k}+t)-1}(p_{i+1}-p_ {i}),\\ Q_{k}(t)&=q_{k}+\sum_{i=k}^{m(t_{k}+t)-1}(q_{i+1}-q_{i}).\end{split}$ $$

Using the fact that $p_{k}=P_{k}(0)$ and $q_{k}=Q_{k}(0)$, along with the update (9), we can rewrite (37) as

$$ (38) $\displaystyle\begin{split}P_{k}(t)&=P_{k}(0)-\sum_{i=k}^{m(t_{k}+t)-1}\alpha_{ i}\nabla F(q_{i})+M_{k}(t)-\gamma\sum_{i=k}^{m(t_{k}+t)-1}\alpha_{i}\nabla \varphi(p_{i}),\\ Q_{k}(t)&=Q_{k}(0)+\sum_{i=k}^{m(t_{k}+t)-1}\alpha_{i}\nabla\varphi(p_{i+1}), \end{split}$ $$

where

$$ $\displaystyle M_{k}(t)=\sum_{i=k}^{m(t_{k}+t)-1}\alpha_{i}\delta M_{i}$ $$

and $\delta M_{i}=\nabla f(q_{i},\xi_{i})-\nabla F(q_{i})$.

In the next section, we show that the process $\{M_{k}\}_{k\geq 0}$ converges uniformly on compact sets, almost surely, to 0 0.

### A.3. Convergence of the sequence { M k } subscript 𝑀 𝑘 \{M_{k}\} { italic_M start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT }

The following lemma is and adaptation of part 1 of the proof of Theorem 2.1 from Kushner & Yin ():

###### Lemma A.3 (Convergence of $\{M_{k}(t)\}_{k\geq 0}$ ) .

Suppose that Assumption 1, 2 and 6 holds, along with either Assumption 3, 4 or 5.
Then, the sequence $\{M_{k}(t)\}_{k\geq 0}$ converges uniformly on compact sets almost surely to 0 0.
More precisely, for any $T$ it holds that

$$ (39) $\displaystyle\lim_{k\to\infty}\sup_{t\in[0,T]}\lVert M_{k}(t)\rVert_{2}=0,$ $$

almost surely.

###### Proof of Lemma A.3 .

Closely following the proof of Theorem 2.1 in Kushner & Yin ():
We let $\mathcal{F}_{j}=\sigma(\xi_{1},\dots,\xi_{j})$.
By definition, we have that

$$ $\displaystyle M_{k}(t)=\sum_{i=k}^{m(t_{k}+t)-1}\alpha_{i}\delta M_{i},$ $$

where $\delta M_{i}=\nabla f(q_{i},\xi_{i})-\nabla F(q_{i})$.
Define

$$ $\displaystyle\tilde{M}_{j}=\sum_{i=k}^{j}\alpha_{i}\delta M_{i}.$ $$

We will show that $\tilde{M}_{j}$ is a martingale sequence. We first note that

$$ $\displaystyle\mathbb{E}\left[\tilde{M}_{j+1}|\mathcal{F}_{j}\right]=\tilde{M}_ {j},$ $$

by Assumption 1.iv) and the fact that the noise is independent. Next, we demonstrate that

$$ (40) $\displaystyle\mathbb{E}\left[\lVert\tilde{M}_{j+1}\rVert_{2}\right]<\infty,$ $$

Note that

$$ $\displaystyle\mathbb{E}\left[\lVert\tilde{M}_{l}\rVert_{2}^{2}\right]$ $\displaystyle=\mathbb{E}\left[\lVert\sum_{i=k}^{l}\alpha_{i}\delta M_{i}\rVert _{2}^{2}\right]$ $\displaystyle=\mathbb{E}\left[\sum_{i=k}^{l}\alpha_{i}^{2}\lVert\delta M_{i} \rVert_{2}^{2}+2\sum_{i=k}^{l}\sum_{j=k}^{i-1}\alpha_{i}\alpha_{j}\langle \delta M_{i},\delta M_{j}\rangle\right]$ $\displaystyle=\mathbb{E}\left[\sum_{i=k}^{l}\alpha_{i}^{2}\lVert\delta M_{i} \rVert_{2}^{2}\right],$ $$

where we have used the fact that for $j<i$

$$ $\displaystyle\mathbb{E}\left[\langle\delta M_{i},\delta M_{j}\rangle\right]= \mathbb{E}\left[\mathbb{E}\left[\langle\delta M_{i},\delta M_{j}\rangle| \mathcal{F}_{j}\right]\right]=\mathbb{E}\left[\langle\mathbb{E}\left[\delta M_ {i}|\mathcal{F}_{j}\right],\delta M_{j}\rangle\right]=0,$ $$

since $M_{j}$ is $\mathcal{F}_{j}$-measurable and $\mathbb{E}\left[\delta M_{i}|\mathcal{F}_{j}\right]=0$ (recall that $\xi_{i}$ is independent of $\mathcal{F}_{j}$).
In the case that Assumption 4.ii) holds we therefore have that

$$ (41) $\displaystyle\mathbb{E}\left[\lVert\delta M_{i}\rVert_{2}^{2}\right]<\infty.$ $$

If instead Assumption 3.ii) holds, we have that

$$ $\displaystyle\mathbb{E}\left[\lVert\delta M_{i+1}|\mathcal{F}_{i}\rVert_{2}^{2 }\right]\leq\kappa(F(q_{k})-F_{*})+(1+\tau)\lVert\nabla F(q_{k})\rVert_{2}^{2} +\sigma^{2}.$ $$

Under Assumption 3.i) or 4.i) we get from Theorem 5.7 that the expectation of the right-hand side is finite(^5^55Under assumption 3.i) we can use Lemma 5.6 to bound the gradient with $2L(F(q_{k})-F_{*})$ which is bounded in expectation by Theorem 5.7.), in which case (41) also holds. Hence $\tilde{M}_{j}$ satisfies (40) and it is thus a martingale.

We now show that (39) holds.
For any interval $[0,T]$, we have that

$$ $\displaystyle\sup_{t\in[0,T]}\lVert M_{k}(t)\rVert_{2}=\sup_{k\leq j\leq l} \lVert\tilde{M}_{j}\rVert_{2},$ $$

where $l=m(t_{k}+T)$. By *Doob’s submartingale inequality* (Kushner & Yin, ; Williams, ), we have for every $\mu>0$ that

$$ $\displaystyle\mathbb{P}\left(\sup_{k\leq j\leq l}\lVert\tilde{M}_{j}\rVert_{2} \geq\mu\right)\leq\frac{\mathbb{E}\left[\lVert\tilde{M}_{l}\rVert_{2}^{2} \right]}{\mu^{2}}.$ $$

which implies that

$$ $\displaystyle\mathbb{P}\left(\sup_{k\leq j}\lVert\tilde{M}_{j}\rVert_{2}\geq \mu\right)\leq C\sum_{i=k}^{\infty}\alpha_{i}^{2}$ $$

and hence

$$ $\displaystyle\lim_{k\to\infty}\mathbb{P}\left(\sup_{k\leq j}\lVert\tilde{M}_{j }\rVert_{2}\geq\mu\right)=0.$ $$

By Theorem 1 in Section 2.10.3 of Shiryaev (), the sequence $\tilde{M}_{j}$ converges almost surely to 0 0,
i.e. there is a set $U$ such that $\mathbb{P}(U)=0$ and for every $\omega\in U^{c}$
we have that (39) holds.
∎

###### Lemma A.3 (Convergence of { M k ⁢ ( t ) } k ≥ 0 subscript subscript 𝑀 𝑘 𝑡 𝑘 0 \{M_{k}(t)\}_{k\geq 0} { italic_M start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ( italic_t ) } start_POSTSUBSCRIPT italic_k ≥ 0 end_POSTSUBSCRIPT ) .

###### Proof of Lemma A.3 .

### A.4. Equicontinuity of the sequences { P k } k ≥ 0 subscript subscript 𝑃 𝑘 𝑘 0 \{P_{k}\}_{k\geq 0} { italic_P start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k ≥ 0 end_POSTSUBSCRIPT and { Q k } k ≥ 0 subscript subscript 𝑄 𝑘 𝑘 0 \{Q_{k}\}_{k\geq 0} { italic_Q start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k ≥ 0 end_POSTSUBSCRIPT

See 5.9
To show Lemma 5.9, we make use of an equivalent definition of extended equicontinuity:

###### Lemma A.4 (Equivalent definition of extended continuity) .

A sequence of functions $\{f_{k}\}_{k\geq 0}$, $f_{k}:\mathbb{R}\to\mathbb{R}^{d}$ is *equicontinuous in the extended sense*
if and only if $\{|f_{k}(0)|\}_{k\geq 0}$ is bounded and for every $T$ and $\epsilon>0$ there is a null sequence $\left(a_{k}\right)_{k\geq 0}$ (that is, $\lim_{k\to\infty}a_{k}=0$) such that

$$ (42) $\displaystyle\sup_{0<|t-s|\leq\delta,\ t,s\in[0,T]}|f_{k}(t)-f_{k}(s)|\leq \epsilon+a_{k}.$ $$

###### Proof of Lemma A.4 .

By definition (14) is equal to

$$ $\displaystyle\lim_{k\to\infty}b_{k}\leq\epsilon$ $$

with

$$ $\displaystyle b_{k}:=\sup_{j\geq k}\sup_{0<|t-s|\leq\delta,\ t,s\in[0,T]}|f_{j }(t)-f_{j}(s)|.$ $$

Define

$$ $\displaystyle a_{k}=\max\{0,b_{k}-\epsilon\}.$ $$

Then $\left(a_{k}\right)_{k\geq 0}$ satisfies all the requirements; $a_{k}$ is clearly positive and by continuity of the function $\max\{0,x\}$ it holds that

$$ $\displaystyle\lim_{k\to\infty}a_{k}=\max\{0,\lim_{k\to\infty}b_{k}-\epsilon\}=0,$ $$

as $\lim_{k\to\infty}b_{k}-\epsilon\leq 0$.
Furthermore, we have that

$$ $\displaystyle\sup_{0<|t-s|\leq\delta,\ t,s\in[0,T]}|f_{k}(t)-f_{k}(s)|\leq b_{ k}\leq\epsilon+a_{k},$ $$

for every $k$ and thus we have shown that (42) follows from (14).
We now show the converse.
Suppose that (42) holds. Taking the supremum of (42) we obtain

$$ $\displaystyle\sup_{j\geq k}\sup_{0<|t-s|\leq\delta,t,s\in[0,T]}|f_{j}(t)-f_{j} (s)|\leq\epsilon+\sup_{j\geq k}a_{j}.$ $$

We finally take the limit with respect to $k$

$$ $\displaystyle\lim_{k\to\infty}\sup_{j\geq k}\sup_{0<|t-s|\leq\delta,\ t,s\in[0 ,T]}|f_{j}(t)-f_{j}(s)|\leq\epsilon+\lim_{k\to\infty}\sup_{j\geq k}a_{j}=: \epsilon+\limsup_{k\to\infty}a_{k}.$ $$

But as $\lim_{k\to\infty}a_{k}$ exists by assumption and is equal to 0 0, it holds that $\limsup_{k\to\infty}a_{k}=\lim_{k\to\infty}a_{k}=0$. We thus conclude that (14) holds.
∎

We now turn to the proof of Lemma 5.9.

###### Proof of Lemma 5.9 .

Closely following Lemma 2 in Freise ():
We want to show that the sequence $\{Z_{k}\}_{k\geq 0}=\{(P_{k},Q_{k})\}_{k\geq 0}$, where $\{P_{k}\}_{k\geq 0}$ and $\{Q_{k}\}_{k\geq 0}$ are defined by (13), is equicontinuous in the extended sense.

First, we note that the sequences $\{P_{k}(0)\}$ and $\{Q_{k}(0)\}$ are finite except on a set of measure 0 0, since by Theorem 5.7 $\sup_{k}\lVert p_{k}\rVert_{2}<\infty$ and $\sup_{k}\lVert q_{k}\rVert_{2}<\infty$ almost surely.

By Lemma A.4 an equivalent charaterization of extended equicontinuity is that for every $\epsilon>0$, there is a sequence $\{a_{k}\}_{k\geq 0}$ such that $\lim_{k\to\infty}a_{k}=0$ and a $\delta>0$ such that

$$ (43) $\displaystyle\sup_{|t-s|<\delta,\ t,s\in[0,T]}\lVert Z_{k}(t)-Z_{k}(s)\rVert_{ \ell^{2}\left(\mathbb{R}^{2d}\right)}\leq\epsilon+a_{k},\ \text{a.s.}$ $$

By (38), we have that

$$ (44) $\displaystyle\lVert P_{k}(t)-P_{k}(s)\rVert_{2}\leq C(\omega)\sum_{i=m(t_{k}+s )}^{m(t_{k}+t)-1}\alpha_{i}+\lVert M_{k}(t)\rVert_{2}+\lVert M_{k}(s)\rVert_{2},$ $$

where $C(\omega)=\sup_{i}\lVert\nabla F(q_{i})-\gamma\nabla\varphi(p_{i})\rVert_{2}$.
By the boundedness of $p_{k}$ and $q_{k}$ along with the continuity of $\nabla F$ and $\nabla\varphi$, we have that $C(\omega)<\infty$, a.s.
The sum on the right-hand side of (44) can be rewritten as

$$ $\displaystyle\sum_{i=m(t_{k}+s)}^{m(t_{k}+t)-1}\alpha_{i}=t_{m(t_{k}+t)}-t_{m( t_{k}+s)}.$ $$

By definition of $m$, (36), we have that

$$ $\displaystyle t_{m(t_{k}+t)}\leq t_{k}+t.$ $$

Thus

$$ (45) $\displaystyle t_{m(t_{k}+t)}-t_{m(t_{k}+s)}\leq t_{k}+t-t_{m(t_{k}+s)}.$ $$

But we also have

$$ $\displaystyle t_{m(t_{k}+s)}\leq t_{k}+s<t_{m(t_{k}+s)+1},$ $$

and hence the right-hand side of (45) can be rewritten and
bounded as follows

$$ $\displaystyle t_{k}+t-(t_{k}+s)+(t_{k}+s)-t_{m(t_{k}+s)}\leq(t-s)+t_{m(t_{k}+s )+1}-t_{m(t_{k}+s)}.$ $$

Now, $t_{m(t_{k}+s)+1}-t_{m(t_{k}+s)}=\alpha_{m(t_{k}+s)+1}$ and hence we see that

$$ $\displaystyle\lVert P_{k}(t)-P_{k}(s)\rVert_{2}\leq C(\omega)\left(|t-s|+ \alpha_{m(t_{k}+s)+1}\right)+\lVert M_{k}(t)\rVert_{2}+\lVert M_{k}(s)\rVert_{ 2}.$ $$

Let $\epsilon$ be greater than 0 0. There are now two cases. If $C(\omega)=0$, (42) clearly holds for any $\delta>0$. If $C(\omega)\neq 0$, then take $\delta>0$ so small that $C(\omega)\delta<\epsilon$. We then have

$$ $\displaystyle\sup_{|t-s|<\delta,\ t,s\in[0,T]}\lVert P_{k}(t)-P_{k}(s)\rVert_{2}$ $\displaystyle\leq\sup_{|t-s|<\delta,t,s\in[0,T]}\Big{[}C(\omega)(|t-s|+\alpha_ {m(t_{k}+s)+1})$ $\displaystyle\hskip 80.00012pt+\lVert M_{k}(t)\rVert_{2}+\lVert M_{k}(s)\rVert _{2}\Big{]}$ $\displaystyle\quad<\epsilon+C(\omega)\alpha_{m(t_{k})+1}+2\lVert M_{k}(T) \rVert_{2}.$ $$

By Lemma A.3, $\lim_{k\to\infty}\lVert M_{k}(T)\rVert_{2}=0$ a.s. and
we see that (42) in Lemma A.4 holds almost surely.
A similar argument yields an analogous bound for $Q_{k}$, and by the equivalence of norms on $\mathbb{R}^{2d}$, we obtain (43).
∎

In the next section, we show that the processes $\{P_{k}\}_{k\geq 0}$ and $\{Q_{k}\}_{k\geq 0}$ can be written as solutions to the integral equations corresponding to (8), plus terms that converge uniformly on compact sets to 0 0 as $k$ tends to $\infty$.

###### Lemma A.4 (Equivalent definition of extended continuity) .

###### Proof of Lemma A.4 .

###### Proof of Lemma 5.9 .

### A.5. Asymptotic solution

See 5.11

###### Proof of Lemma 5.11 .

We start with showing that the sum

$$ $\displaystyle-\sum_{i=k}^{m(t_{k}+t)-1}\alpha_{i}\nabla F(q_{i})$ $$

in Equation (38)
can be rewritten as

$$ $\displaystyle-\int_{0}^{t}\nabla F(Q_{k}(s))\mathrm{d}s+\mu_{1,k}(t),$ $$

where $Q_{k}(t)$ is defined by (13) and $\{\mu_{1,k}\}_{k\geq 0}$ is a sequence of functions that tends to 0 uniformly on compact intervals.
Consider

$$ $\displaystyle I_{k}:=-\int_{0}^{t}\nabla F(Q_{k}(s))\mathrm{d}s.$ $$

Then, since $t_{k}+s$ belongs to a single interval $[t_{i},t_{i+1})$,

$$ $\displaystyle I_{k}$ $\displaystyle=-\int_{0}^{t}\left(\nabla F(q_{0})I_{(-\infty,t_{0})}(t_{k}+s)- \sum_{i=0}^{\infty}\nabla F(q_{i})I_{[t_{i},t_{i+1})}(t_{k}+s)\right)\mathrm{d}s$ $\displaystyle=-\int_{0}^{t}\left(\nabla F(q_{0})I_{(-\infty,t_{0}-t_{k})}(s)- \sum_{i=0}^{\infty}\nabla F(q_{i})I_{[t_{i}-t_{k},t_{i+1}-t_{k})}(s)\right) \mathrm{d}s.$ $$

The term $t_{0}-t_{k}$ is always less than or equal to 0 0. Hence the first term disappears as we are integrating from 0 0 to $t$.
For $i<k$, we have that $t_{i+1}-t_{k}\leq 0$. We can therefore start the sum at $i=k$, as earlier terms will not contribute to the integral.
Thus,

$$ $\displaystyle I_{k}=-\int_{0}^{t}\left(\sum_{i=k}^{\infty}\nabla F(q_{i})I_{[t _{i}-t_{k},t_{i+1}-t_{k})}(s)\right)\mathrm{d}s.$ $$

Now suppose $t_{j}-t_{k}\leq t<t_{j+1}-t_{k}$. We split up the previous integral as follows:

$$ $\displaystyle I_{k}$ $\displaystyle=-\int_{0}^{t_{j}-t_{k}}\left(\sum_{i=k}^{j-1}\nabla F(q_{i})I_{[ t_{i}-t_{k},t_{i+1}-t_{k})}(s)\right)\mathrm{d}s$ $\displaystyle\quad-\int_{t_{j}-t_{k}}^{t}\nabla F(q_{k})I_{[t_{j}-t_{k},t_{j+1 }-t_{k})}(s)\mathrm{d}s$ $\displaystyle=-\sum_{i=k}^{j-1}\nabla F(q_{i})\alpha_{i}-\nabla F(q_{j})\left( t-t_{j}+t_{k}\right),$ $$

where we have used that $\int_{0}^{t_{j}-t_{k}}I_{[t_{i}-t_{k},t_{i+1}-t_{k})}(s)ds=\alpha_{i}$.
Using the fact that $m(t+t_{k})=j$ (where $m(t)$ is defined by (36)), we can rewrite this further as

$$ $\displaystyle-\sum_{i=k}^{m(t_{k}+t)-1}\nabla F(q_{i})\alpha_{i}-\mu_{1,k}(t),$ $$

where $\mu_{1,k}(t)=\nabla F(q_{m(t_{k}+t)})\left(t-t_{m(t_{k}+t)}+t_{k}\right)$.
The function $\mu_{1,k}$ is piecewise linear and 0 0 at $t=t_{j}-t_{k}$.
The gradient $\nabla F$ is Lipschitz-continuous by assumption, and thus there is some positive random variable $C(\omega)$, finite almost everywhere, such that

$$ $\displaystyle\lVert\nabla F(q_{m(t_{k}+t)})\rVert_{2}\leq C(\omega)<\infty,$ $$

since by Theorem 5.7 $\sup_{k}\lVert q_{k}\rVert_{2}<\infty$.
Hence, it holds that

$$ $\displaystyle\lVert\mu_{1,k}(t)\rVert_{2}\leq C(\omega)|\alpha_{m(t_{k}+t)}|.$ $$

Now, we have that $\lim_{k\to\infty}\sup_{t\in[0,T]}\alpha_{m(t_{k}+t)}=0$ for any fixed $T$, since $\lim_{k\to\infty}\alpha_{k}=0$, and thus $\mu_{1,k}$ converges to 0 0 uniformly on compact intervals.
Hence, it holds that

$$ $\displaystyle-\int_{0}^{t}\nabla F(Q_{k}(s))ds=-\sum_{i=k}^{m(t_{k}+t)-1} \nabla F(q_{i})\alpha_{i}+\mu_{1,k}(t),$ $$

where

$$ $\displaystyle\mu_{1,k}(t)=\nabla F(q_{m(t_{k}+t)})(t_{m(t_{k}+t)}-t-t_{k}).$ $$

In a similar fashion we obtain that

$$ $\displaystyle-\sum_{i=k}^{m(t_{k}+t)-1}\alpha_{i}\nabla\varphi(p_{i})=-\int_{0 }^{t}\nabla\varphi(P_{k}(s))\mathrm{d}s+\mu_{2,k}(t),$ $$

where $\{\mu_{2,k}\}_{k\geq 0}$ converges uniformly on compact sets to 0 0.
Letting $\mu_{k}=\mu_{1,k}+\gamma\mu_{2,k}$, we obtain the expression in the first line of (15).

We now turn our attention to the second line of (15). By an argument analogous to the previous, we can write the second line of (38) as

$$ $\displaystyle Q_{k}(t)=Q_{k}(0)+\int_{0}^{t}\varphi(P_{k+1}(s))\mathrm{d}s+\nu _{k}(t),$ $$

where $\nu_{k}$ converges uniformly on compact sets to 0 0.
We can rewrite the integral on the right-hand side as

$$ $\displaystyle\int_{0}^{t}\nabla\varphi(P_{k+1}(s))\mathrm{d}s=\underset{:= \kappa_{k}(t)}{\underbrace{\int_{0}^{t}\nabla\varphi(P_{k+1}(s))-\nabla\varphi (P_{k}(s))\mathrm{d}s}}+\int_{0}^{t}\nabla\varphi(P_{k}(s))\mathrm{d}s.$ $$

The norm of $\kappa_{k}(t)$ can be bounded as follows:

$$ $\displaystyle\lVert\kappa_{k}(t)\rVert_{2}\leq\int_{0}^{t}\lambda\lVert P_{k+1 }(s))-P_{k}(s)\rVert_{2}\mathrm{d}s=\int_{0}^{t}\lambda\lVert P_{k}(\alpha_{k} +s)-P_{k}(s)\rVert_{2}\mathrm{d}s,$ $$

where we have used the Lipschitz continuity of $\nabla\varphi$ and the fact that $P_{k+1}(s)=P_{k}(\alpha_{k}+s)$. Since $\{P_{k}(t)\}_{k\geq 0}$ is equicontinuous in the extended sense by Lemma 5.9, there is for each $T$ and $\epsilon>0$ a $\delta>0$ such that

$$ (46) $\displaystyle\limsup_{k\to\infty}\sup_{|t-s|<\delta,\ t,s\in[0,T]}\lVert P_{k} (\alpha_{k}+s)-P_{k}(s)\rVert_{2}\leq\epsilon.$ $$

What remains is to show is that $\{\kappa_{k}\}_{k\geq 0}$ converges uniformly on compact sets to 0 0.
For any $T$, we have that

$$ $\displaystyle\lim_{k\to\infty}\sup_{t\in[0,T]}\lVert\kappa_{k}(t)\rVert_{2} \leq\lim_{k\to\infty}\int_{0}^{T}\lambda\lVert P_{k}(\alpha_{k+1}+s)-P_{k}(s) \rVert_{2}\mathrm{d}s$ $$

since the integrand is positive. By Theorem 5.7, we can bound $\lVert P_{k}(\alpha_{k+1}+s)-P_{k}(s)\rVert_{2}\leq 2\sup_{t\in\mathbb{R}}
\lVert P_{k}(t)\rVert_{2}<\infty$. Thus, we can use the Lebesgue dominated convergence theorem and take the limit inside the integral:

$$ $\displaystyle\lim_{k\to\infty}\sup_{t\in[0,T]}\lVert\kappa_{k}(t)\rVert_{2} \leq\int_{0}^{T}\lim_{k\to\infty}\lambda\lVert P_{k}(\alpha_{k+1}+s)-P_{k}(s) \rVert_{2}\mathrm{d}s$ $$

By (46), we can make the integrand arbirarily small by choosing $k$ so large that $\alpha_{k+1}\leq\delta$.
∎

###### Proof of Lemma 5.11 .

### A.6. Convergence to a locally asymptotically stable set

The goal of this section is to show
See 5.15

We start with showing the following help-lemma:

###### Lemma A.6 .

In the same context as Theorem 5.15, for each $\delta>0$ there is a subsequence $\{z_{n_{k}}\}_{k\geq 0}$ of $\{z_{k}\}_{k\geq 0}$ such that that $\{z_{n_{k}}\}_{k\geq 0}\subset N_{\delta}(A)$.

###### Proof of Lemma A.6 .

Since $\{z_{n_{k}}\}_{k\geq 0}\subset K$, and $K$ is compact, we can find a further subsequence
$\{z_{n_{k}^{\prime}}\}_{k\geq 0}$ that tends to $z_{0}\in K$. Let $\{Z_{n_{k}^{\prime}}\}_{k\geq 0}$ be the sequence of shifted interpolations associated with $\{z_{n_{k}^{\prime}}\}_{k\geq 0}$. This family is equicontinuous in the extended sense by Lemma 5.9, and thus it has a subsequence $\{Z_{n_{k}^{{}^{\prime\prime}}}\}_{k\geq 0}$ converging to a function $z(\cdot)$ which is a solution to (8) by Lemma 5.11, and satisfies $z(0)=z_{0}$. Since $z_{0}$ is in the domain of attraction of $A$, it holds that

$$ $\displaystyle\lim_{t\to\infty}\inf_{a\in A}\lVert z(t)-a\rVert_{\ell^{2}\left( \mathbb{R}^{2d}\right)}=0.$ $$

Choose $T_{\frac{\delta}{2}}$ so large that

$$ (47) $\displaystyle\inf_{a\in A}\lVert z(t)-a\rVert_{\ell^{2}\left(\mathbb{R}^{2d} \right)}<\frac{\delta}{2}$ $$

for all $t\geq T_{\frac{\delta}{2}}$.
Then, we have

$$ $\displaystyle\inf_{a\in A}\lVert Z_{n_{k}^{\prime\prime}}(t)-a\rVert_{\ell^{2} \left(\mathbb{R}^{2d}\right)}$ $\displaystyle\leq\lVert Z_{n_{k}^{\prime\prime}}(t)-z(t)\rVert_{\ell^{2}\left( \mathbb{R}^{2d}\right)}+\inf_{a\in A}\lVert z(t)-a\rVert_{\ell^{2}\left( \mathbb{R}^{2d}\right)}$ $\displaystyle<\lVert Z_{n_{k}^{\prime\prime}}(t)-z(t)\rVert_{\ell^{2}\left( \mathbb{R}^{2d}\right)}+\frac{\delta}{2}.$ $$

Since $\{Z_{n_{k}^{\prime\prime}}\}$ converges uniformly on compact sets to $z$, we can choose $N_{\frac{\delta}{2}}$ so large that
for any $n_{k}^{\prime}\geq N_{\frac{\delta}{2}}$ we have that $\sup_{s\in[0,t]}\lVert Z_{n_{k}^{\prime\prime}}(s)-z(s)\rVert_{\ell^{2}\left(
\mathbb{R}^{2d}\right)}<\frac{\delta}{2}$.
Hence, for $n_{k}^{\prime\prime}>N_{\frac{\delta}{2}}$ we have

$$ $\displaystyle\inf_{a\in A}\lVert Z_{n_{k}^{\prime\prime}}(t)-a\rVert_{\ell^{2} \left(\mathbb{R}^{2d}\right)}<\delta,$ $$

which yields the statement of the lemma.
∎

With the help of Lemma A.6, we now show Theorem 5.15. The proof is inspired by the proof strategy in Fort & Pagès ().

###### Proof of Theorem 5.15 .

Let $\epsilon>0$ and let $\delta>0$ be as in Definition 5.14.
According to Lemma A.6, there is a subsequence $\{z_{r_{k}}\}_{k\geq 0}$ of $\{z_{k}\}_{k\geq 0}$ such that
$\{z_{r_{k}}\}_{k\geq 0}\subset N_{\delta/2}(A)$.

We now show by contradiction that $\{z_{k}\}_{k\geq 0}$ cannot escape $N_{\epsilon}(A)$ infinitely often.
Suppose that there is a subsequence
$\{z_{s_{k}}\}_{k\geq 0}\subset N_{\epsilon}(A)^{c}$.

Define $\ell_{0}=\min\{j:z_{j}\in N_{\delta/2}(A)\}$ and recursively for $k=1,2,\ldots$,

$$ $\displaystyle n_{k}$ $\displaystyle=\min\{j:j\geq\ell_{k-1}\text{ and }z_{j}\in N_{\epsilon}(A)^{c}\},$ $\displaystyle m_{k}$ $\displaystyle=\max\{j:j\leq n_{k}\text{ and }z_{j}\in N_{\delta/2}(A)\},$ $\displaystyle\ell_{k}$ $\displaystyle=\min\{j:j\geq n_{k}\text{ and }z_{j}\in N_{\delta/2}(A)\}.$ $$

Then there is no index $j\in\{m_{k}+1,\dots,n_{k}\}$ such that
$z_{j}\in N_{\delta/2}(A)$; i.e. $m_{k}$ is the last index for which $z_{j}$ visits $N_{\delta/2}(A)$ before going to $N_{\epsilon}(A)^{c}$.

Consider the associated sequence of functions $\{Z_{m_{k}}\}_{k\geq 0}$. This satisfies

$$ $\displaystyle Z_{m_{k}}(t)$ $\displaystyle=z_{m_{k}}\in N_{\delta/2}(A),$ $\displaystyle 0$ $\displaystyle\leq t<\alpha_{m_{k}},$ $\displaystyle Z_{m_{k}}(t)$ $\displaystyle=z_{n_{k}}\in N_{\epsilon}(A)^{c},$ $\displaystyle t_{n_{k}}-t_{m_{k}}$ $\displaystyle\leq t<t_{n_{k}}-t_{m_{k}}+\alpha_{n_{k}}.$ $$

In between these two time intervals, $Z_{m_{k}}$ attains the values $z_{m_{k}+1}$, $z_{m_{k}+2}$, $\ldots$, $z_{n_{k}-1}$. We can therefore guarantee that

$$ (48) $\displaystyle Z_{m_{k}}(t)\in N_{\delta/2}(A)^{c}\text{ for }t\in[\alpha_{m_{k }},t_{n_{k}}-t_{m_{k}}].$ $$

Let $\{Z_{m_{k}^{\prime}}\}$ be a subsequence of $\{Z_{m_{k}}\}$ that converges uniformly on compact sets to a function $z$.

First, assume that $\limsup_{k\to\infty}t_{n_{k}^{\prime}}-t_{m_{k}^{\prime}}=\infty$. Then we can extract a subsequence (which we continue to denote $\{t_{n_{k}}\}$) for which $\lim_{k\to\infty}t_{n_{k}^{\prime}}-t_{m_{k}^{\prime}}=\infty$.
Under this assumption, it holds that

$$ $\displaystyle z(t)\in N_{\delta/2}(A)^{c}\text{ for }t>0.$ $$

If this was not the case there would be a $t^{\prime}>0$ such that $z(t^{\prime})\in N_{\delta/2}(A)$.
By the openness of $N_{\delta/2}(A)$ we can choose $\eta>0$ such that
$B(z(t^{\prime}),\eta)\subset N_{\delta/2}(A)$. There is a $K_{\eta}$ such that $k\geq K_{\eta}$ implies that

$$ $\displaystyle\lVert Z_{m_{k}^{\prime}}(t^{\prime})-z(t^{\prime})\rVert<\eta,$ $$

i.e. $Z_{m_{k}^{\prime}}(t^{\prime})\in B(z(t^{\prime}),\eta)\subset N_{\delta/2}(A)$.
However, since $t_{n_{k}^{\prime}}-t_{m_{k}^{\prime}}\to\infty$ and $\alpha_{m_{k}^{\prime}}\to 0$, it holds that $t^{\prime}\in[\alpha_{m_{k}^{\prime}},t_{n_{k}^{\prime}}-t_{m_{k}^{\prime}}]$ for large enough $k$. This contradicts (48), so that indeed $z(t)\in N_{\delta/2}(A)^{c}$ for $t>0$. By Theorem 5.10, $z$ is continuous and since $Z_{m_{k}}(0)\in N_{\delta/2}(A)$ we must thus have $z(0)\in\partial N_{\delta/2}(A)$.
However, the fact that $z(t)\in N_{\delta/2}(A)^{c}$ for $t\geq 0$ contradicts the asymptotic stability of $A$, since this path which starts in $\partial N_{\delta/2}(A)\subset N_{\delta}(A)$ does not approach $A$.
This is a contradiction towards our assumption that $t_{n_{k}^{\prime}}-t_{m_{k}^{\prime}}\to\infty$, and we can thus define $\tilde{T}=\sup_{k}t_{n_{k}^{\prime}}-t_{m_{k}^{\prime}}<\infty$.
Then $[0,\tilde{T}]$ is a compact interval such that $\{t_{n_{k}^{\prime}}-t_{m_{k}^{\prime}}\}_{k\geq 0}\subset[0,\tilde{T}]$. Hence there is a subsequence
$\{t_{n_{k}^{{}^{\prime\prime}}}-t_{m_{k}^{{}^{\prime\prime}}}\}_{k\geq 0}
\subset\{t_{n_{k}^{\prime}}-t_{m_{k}^{\prime}}\}_{k\geq 0}$ that converges to some $T\in[0,\widetilde{T}]$.

The corresponding sequence of functions $\{Z_{m_{k}^{{}^{\prime\prime}}}\}$ is a subsequence of $\{Z_{m_{k}^{\prime}}\}$ and thus it must also converge uniformly on compact sets to the same function $z$.
From the uniform convergence it also follows that

$$ $\displaystyle z_{n_{k}^{{}^{\prime\prime}}}=Z_{m_{k}^{{}^{\prime\prime}}}(t_{n _{k}^{{}^{\prime\prime}}}-t_{m_{k}^{{}^{\prime\prime}}})\to z(T).$ $$

Since each $z_{n_{k}^{{}^{\prime\prime}}}\in N_{\epsilon}(A)^{c}$ we must have $z(T)\in N_{\epsilon}(A)^{c}$.
However, this contradicts the Lyapunov stability of $A$ and therefore also our original assumption that there exists a subsequence $\{z_{s_{k}}\}_{k\geq 0}\subset N_{\epsilon}(A)^{c}$. This concludes the proof.
∎

###### Lemma A.6 .

###### Proof of Lemma A.6 .

###### Proof of Theorem 5.15 .

### A.7. Convergence to a stationary point

We will now apply Theorem 5.15 and show that $\{z_{k}\}_{k\geq 0}$ converges to the set $\{z:H(z)\leq\lim\inf_{k}H(z_{k})\}$. First, we need to show that it is locally asymptotically stable:
See 5.16

###### Proof.

We need to show that for all $\epsilon>0$ we can choose $\delta>0$ so that if $z_{0}\in N_{\delta}(A)$, $z(t)$ stays in $N_{\epsilon}(A)$ and that $\lim_{t\to\infty}z(t)\in A$.

By Lemma 5.6, there exists a $\eta>0$ such that
$\{z:H(z)\leq c+\eta\}\subset N_{\epsilon}(A)$.
Now $z(t)$ will stay in $\{z:H(z)\leq c+\eta\}$ since $z(t)$ decreases along the paths of $H$.
However, it might not converge to $A$ since there may exists stationary points $z_{*}$ such that

$$ $\displaystyle c<H(z_{*})\leq c+\eta,$ $$

and if we reach one of these we will get stuck there instead of reaching $A$. Define

$$ $\displaystyle c_{*}=\inf\{H(z_{*}):c<H(z_{*})\leq c+\eta,\nabla H(z_{*})=0\}.$ $$

It holds that $c_{*}>c$, i.e. we cannot find stationary points for which $H(z_{*})$ is arbitrarily close to $c_{*}$. We can see this by letting $\Lambda=\{x:\nabla H(x)=0\}$ and $K=[c,c+\eta]$. Then by Assumption 1.iii), there exist numbers $\{y_{i}\}_{i=1}^{n}$ , such that $y_{1}<\dots<y_{n}$ and

$$ $\displaystyle\{H(z):c\leq H(z)\leq c+\eta:z\in\Lambda\}=H(\Lambda)\cap K=\{y_{ 1},\dots,y_{n}\}.$ $$

If $y_{1}=c$, we have that

$$ $\displaystyle y_{2}=\min H(\Lambda)\cap K=\min\{H(z):c<H(z)\leq c+\eta,\ z\in \Lambda\}=c_{*}$ $$

and thus $c_{*}>c$. Similarly, if $y_{1}>c$, we also get that $c_{*}=y_{1}>c$. Thus indeed it always holds that $c_{*}>c$, and we can take $\mu>0$ so small that $c_{*}-\mu>c$.
By Lemma 5.6 there exists some $\delta>0$ such that

$$ $\displaystyle N_{\delta}(A)\subset\{H(z)<c_{*}-\mu\}$ $$

Since $H$ is decreasing along the paths of $z(t)$, any solution starting in $N_{\delta}(A)$ will stay inside $\{z:H(z)\leq c_{*}-\mu\}$ (and thus $N_{\epsilon}(A)$).
By La Salle’s invariance principle, any path starting in the compact set $\mathcal{M}=\{z:H(z)\leq c_{*}-\mu\}$ tends to $\{z\in\mathcal{M}:\nabla H(z)=0\}$.
All points $z_{*}\in\{z\in\mathcal{M}:\nabla F(z)=0\}$ satisfy $H(z_{*})\leq c$, by the choice of $c_{*}$ and $\mu>0$.
Thus, $z(t)\to\{z:H(z)\leq c\}$ whenever $z(0)\in N_{\delta}(A)$.

We have for the given $\epsilon>0$ found a $\delta>0$ such that any path in $N_{\delta}(A)$ never leaves $N_{\epsilon}(A)$ and tends to $A$ as $t\to\infty$.
∎

We are now ready to prove our main result, Theorem 5.5:

See 5.5

###### Proof.

Let $c=\lim\inf_{k}H(z_{k})$.
We start with showing that $\lim_{k\to\infty}H(z_{k})=c$.
By Lemma 5.16, the set $A=\{z:H(z)\leq c\}$ is a locally asymptotically stable set, and by Lemma 5.6, we can find a compact set $K$ in the domain of attraction of $A$ that $\{z_{k}\}_{k\geq 0}$ enters infinitely often:
In particular, we can take $K=\mathcal{M}$, where $\mathcal{M}$ is as in the proof of Lemma 5.16; $\mathcal{M}$ is in the domain of attraction of $A$, and by Lemma 5.6, $\{z_{k}\}_{k\geq 0}$ visits $\mathcal{M}$ infinitely often.
Theorem 5.15 then implies that
$z_{k}\to\{z:H(z)\leq c\}$.
Suppose that $\lim_{k}H(z_{k})\neq c$.
The negation of the statement is

$$ $\displaystyle\exists\epsilon>0:\forall n\exists n_{k}\geq n,H(z_{n_{k}})\leq c -\epsilon\lor H(z_{n_{k}})\geq c+\epsilon.$ $$

In the case that there exists a subsequence $\{z_{n_{k}}\}$ such that $H(z_{n_{k}})\geq c+\epsilon$, since then $\{z_{k}\}$ would not converge to $\{z:H(z)\leq c\}$.
If there exists a subsequence that satisfies $H(z_{n_{k}})\leq c-\epsilon$ we would have
$\lim\inf_{k}H(z_{k})\leq c-\epsilon<c$ which is also a contradiction by the choice of $c$.

We now know that $\lim_{k\to\infty}H(z_{k})=c$, but we have yet to verify that $\{z_{k}\}_{k\geq 0}$ converges to the set of stationary points.
Suppose that this is not the case. For brevity let $\Lambda=\{z:\nabla H(x)=0\}$. Then there exists an $\epsilon_{0}>0$ and subsequence $\{z_{n_{k}}\}_{k\geq 0}$
such that

$$ (49) $\displaystyle\inf_{x\in\Lambda}\lVert z_{n_{k}}-x\rVert\geq\epsilon_{0}.$ $$

From the previous paragraph, it holds that

$$ $\displaystyle\lim_{n_{k}\to\infty}H(z_{n_{k}})=c.$ $$

By Theorem 5.7, the sequence $\{z_{n_{k}}\}_{k\geq 0}$ is bounded. By Lemma 5.6 we can thus find a further subsequence (still denoted by $\{z_{n_{k}}\}_{k\geq 0}$) and a point
$\tilde{z}_{0}$ such that $\lim_{n_{k}\to\infty}z_{n_{k}}=\tilde{z}_{0}$ and $H(\tilde{z}_{0})=c$.
The sequence of interpolations $\{Z_{n_{k}}(\cdot)\}$
associated with $\{z_{n_{k}}\}$, has a subsequence $\{Z_{n_{k}^{\prime}}(\cdot)\}$ that converges to a solution $\tilde{z}(\cdot)$, such that $\tilde{z}(0)=\tilde{z}_{0}$.
By (49) it holds that $\tilde{z}_{0}\not\in\{z:\nabla H(z)=0\}$.
As $H$ is decreasing along the paths of $\tilde{z}(\cdot)$, we have for $t^{\prime}>0$ that $c=H(\tilde{z}_{0})=H(\tilde{z}(0))>H(\tilde{z}(t^{\prime}))$.
However, $\tilde{z}(\cdot)$ is taking values in $L\left(\{z_{k}\}\right)$, the set of limit points of $\{z_{k}\}$, compare Proposition 1.b) in Fort & Pagès (). Thus, there is some subsequence $\{z_{m_{k}}\}$ that converges to
$H(\tilde{z}(t^{\prime}))$.
But since $c=H(\tilde{z}_{0})>H(\tilde{z}(t^{\prime}))$ and $\{z_{m_{k}}\}$ converges to
$H(\tilde{z}(t^{\prime}))$ which is a contradiction, by the choice of $c$.
It follows that the set of limit points $L\left(\{z_{k}\}_{k\geq 0}\right)$ of $\{z_{k}\}_{k\geq 0}$ is contained in $\{z:\nabla H(z)=0\}$.
Since $z_{k+1}-z_{k}\to 0$, the limit set $L\left(\{z_{k}\}_{k\geq 0}\right)$ is connected (Asic & Adamovic, ). By Assumption 7, this implies that $\{z_{k}\}_{k\geq 0}$ converges to a single stationary point.
∎

At last, we prove Corollary 5.6:
See 5.6

###### Proof.

By Theorem 5.5 $\{q_{k}\}_{k\geq 0}$ converges almost surely to a stationary point $q_{*}$. Hence,

$$ $\displaystyle\lim_{k\to\infty}\lVert\nabla F(q_{k})\rVert_{2}=0,\text{a.s.},$ $$

compare Lemma 2.3 in van der Vaart ().
From Lemma 5.6 we have that

$$ $\displaystyle\lVert\nabla F(q_{k})\rVert_{2}^{2}\leq 2L\left(F(q_{k})-F_{*} \right).$ $$

By Theorem 5.7, we obtain that

$$ $\displaystyle\sup_{k}\mathbb{E}\left[\lVert\nabla F(q_{k})\rVert_{2}^{2}\right ]<\infty.$ $$

By Lemma 3 in Chapter 2.6 of Shiryaev () we obtain (taking $G(t)=t^{2}$) that the sequence $\{\|\nabla F(q_{k})\|\}_{k\geq 0}$ is uniformly integrable. It follows from Theorem 5 in Chapter 2.6 of Shiryaev () that

$$ $\displaystyle\lim_{k\to\infty}\mathbb{E}\left[\lVert\nabla F(q_{k})\rVert_{2} \right]=0.$ $$

Under Assumption 4 or 5, we instead get from Lemma 5.6 and Theorem 5.7 that

$$ $\displaystyle\sup_{k}\mathbb{E}\left[\lVert\nabla F(q_{k})\rVert_{2}\right]<\infty.$ $$

It follows that

$$ $\displaystyle\lim_{k\to\infty}\mathbb{E}\left[\lVert\nabla F(q_{k})\rVert_{2}^ {\frac{1}{2}}\right]=0.$ $$

∎

###### Proof.

###### Proof.

###### Proof.

## Appendix B Auxiliary results

Several of the results in this section are relatively standard, but we keep them here for the sake of reference.

###### Lemma 5.6 .

Let $\{x_{k}\}_{k\geq 0}$ be a sequence in $\mathbb{R}^{d}$.
Suppose that $\sup_{k}\lVert x_{k}\rVert<\infty$ and that $f(x_{k})\to y$, where $f:\mathbb{R}^{d}\to\mathbb{R}$ is continuous. Then there is a subsequence $\{x_{n_{k}}\}_{k\geq 0}\subset\{x_{k}\}_{k\geq 0}$ that converges to some number $x$ such that
$f(x)=y$

###### Proof.

Since $\sup_{k}\lVert x_{k}\rVert<\infty$ there is some compact set $K$ such that $\{x_{k}\}\subset K$. By compactness, there is some subsequence $\{x_{n_{k}}\}$, that converges to some element $x$. The sequence $\{f(x_{n_{k}})\}$ is a subsequence of $\{f(x_{k})\}$, and must converge to the same limit $y$. However, by continuity of $f$, we have that $\lim_{k\to\infty}f(x_{n_{k}})=f(\lim_{k\to\infty}x_{n_{k}})=f(x)$. Thus, $f(x)=y$.
∎

The next two Lemmas, Lemma 5.6 and 5.6, are helpful in showing that the sublevel sets the Hamiltonian are locally asymptotically stable:

###### Lemma 5.6 .

Suppose that $f:\mathbb{R}^{d}\to\mathbb{R}$ is continuous and coercive. Let $A=\{x:f(x)\leq c\}$, where $c$ is such that $A\neq\emptyset$. Then, for every $\eta>0$ there is $\delta>0$ such that $N_{\delta}(A)\subset\{x:f<c+\eta\}$.

###### Proof.

We first note that since $f$ is coercive, $A$ is compact. Let $\eta>0$ be given. By continuity of $f$, there is $\delta>0$ such that

$$ $\displaystyle|x-y|<\delta\ \implies|f(x)-f(y)|<\eta.$ $$

For such $\delta$, we consider

$$ $\displaystyle N_{\delta}(A)=\{x:\inf_{a\in A}\lVert x-a\rVert<\delta\}.$ $$

Take $x_{0}\in N_{\delta}(A)$. Then $\inf_{a\in A}\lVert x_{0}-a\rVert<\delta$ and by the definition of the infimum, there exists for each $n$ and element $a_{n}\in A$ such that

$$ $\displaystyle\lVert x_{0}-a_{n}\rVert<\inf_{a\in A}\lVert x_{0}-a\rVert+\frac{ 1}{n}.$ $$

Then $\{a_{n}\}\subset A$ and by compactness there is a subsequence $\{a_{n_{k}}\}$ that converges to an element $a_{*}\in A$. Since

$$ $\displaystyle\lVert x_{0}-a_{n_{k}}\rVert<\inf_{a\in A}\lVert x_{0}-a\rVert+ \frac{1}{n_{k}},$ $$

it holds that

$$ $\displaystyle\lVert x_{0}-a_{*}\rVert\leq\inf_{a\in A}\lVert x_{0}-a\rVert<\delta.$ $$

Since $f$ is continuous, we have that

$$ $\displaystyle f(x_{0})<f(a_{*})+\eta\leq c+\eta$ $$

i.e. $x_{0}\in\{x:f(x)\leq c+\eta\}$. Thus $N_{\delta}(A)\subset\{x:f(x)\leq c+\eta\}$.
∎

###### Lemma 5.6 .

Let $A=\{x:f(x)\leq c\}$ (where $c$ is such that $A\neq\emptyset$). Then for every $\epsilon>0$ there is $\eta>0$ such that $\{x:f(x)\leq c+\eta\}\subset N_{\epsilon}(A)$.

###### Proof.

If this was not the case, then there exists some $\epsilon>0$ and for every $n$ we can find $x_{n}$ that satisfies

$$ $\displaystyle x_{n}\in\{x:f(x)\leq c+\frac{1}{n}\}\cap N_{\epsilon}(A)^{c} \subset\{x:f(x)\leq c+1\}\cap N_{\epsilon}(A)^{c}.$ $$

The latter is compact since $N_{\epsilon}(A)^{c}$ is closed and $\{x:f(x)\leq c+1\}$ is compact.
Thus, $\{x_{n}\}$ has a subsequence $\{x_{n_{k}}\}$ that converges to $x_{*}\in\{x:f(x)\leq c+1\}\cap N_{\epsilon}(A)^{c}\subset N_{\epsilon}(A)^{c}
\subset A^{c}$.
However, each $x_{n_{k}}\in\{x:f(x)\leq c+\frac{1}{n_{k}}\}$ and thus by continuity it holds that
$f(x_{*})\leq c$ which is a contradiction.
∎

We will use the next Lemma to show that under the given assumptions, the sublevel set $\{z:H(z)\leq\liminf_{k\to\infty}H(z_{k})\}$ is non-empty:

###### Lemma 5.6 .

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be a continuous function that is bounded below by $f_{*}=\inf_{x\in\mathbb{R}^{d}}f(x)$.
Let $\{x_{k}\}_{k\geq 0}$ be a sequence in $\mathbb{R}^{d}$ such that $\sup_{k}\lVert x_{k}\rVert<\infty$. Put $c=\lim\inf_{k}f(x_{k})$. Then $\{x:f(x)\leq c\}\neq\emptyset$.

###### Proof.

By assumption $\{x_{k}\}_{k\geq 0}$ is contained in some compact set $K$. By continuity, it holds that $C=\sup_{k}f(x_{k})<\infty$ and
hence the sequence $\{f(x_{k})\}_{k\geq 0}$ is contained the compact set $[f_{*},C]$.
It follows that $c\in[f_{*},C]$. By a standard result in real analysis, we can (since $\{f(x_{k})\}_{k\geq 0}$ is bounded) find a subsequence $\{f(x_{n_{k}})\}$ that converges to $c$. By Lemma 5.6, there exists a further subsequence $\{x_{n_{k}^{\prime}}\}$ that converges to some element $x$ such that $f(x)=c$.
Hence $x\in\{x:f(x)\leq c\}$ and $\{x:f(x)\leq c\}\neq\emptyset$.
∎

###### Lemma 5.6 .

Let $f$ be a function which is bounded below. and let $c=\lim\inf_{k}f(x_{k})$. Then for every $\delta>0$, the sequence $\{x_{k}\}$ is in the set $A_{\delta}=\{x:f(x)\leq c+\delta\}$ infinitely often.

###### Proof.

The negation of statement is

$$ $\displaystyle\lnot\left(\forall\delta>0,\forall n,\exists n_{k},n_{k}\geq n \land z_{n_{k}}\in A_{\delta}\right)$ $$

which can be rewritten as

$$ $\displaystyle\exists\delta_{0}>0,\exists k_{0},\forall k\geq k_{0},\ x_{k}\not \in A_{\delta}.$ $$

This means that for all $k\geq k_{0}$,

$$ (50) $\displaystyle f(x_{k})>c+\delta_{0}.$ $$

Taking the infimum, we see that

$$ (51) $\displaystyle\inf_{k\geq k_{0}}f(x_{k})\geq c+\delta_{0}.$ $$

Since $\inf_{k\geq k_{0}}f(x_{k})$ is increasing, we have for $k\geq k_{0}$ that

$$ $\displaystyle\inf_{m\geq k}f(x_{m})\geq\inf_{m\geq k_{0}}f(x_{m})\geq c+\delta _{0}$ $$

Taking the supremum over $k$, we see that we must have

$$ $\displaystyle\liminf_{k}f(x_{k})=\sup_{k\geq 0}\inf_{m\geq k}f(x_{m})\geq c+ \delta_{0},$ $$

i.e. $\liminf_{k\to\infty}f(x_{k})\geq c+\delta_{0}$, which is a contradiction.
∎

###### Lemma 5.6 .

Let $F$ be bounded from below by $F_{*}$. If $F$ is $(L_{0},L_{1})-$smooth, it holds that

$$ $\displaystyle\lVert\nabla F(q)\rVert\leq 2L_{1}(F(q)-F_{*})+\frac{L_{0}}{L_{1}}.$ $$

If $F$ is instead $L$-smooth with Lipschitz constant $L$, it holds that

$$ $\displaystyle\lVert\nabla F(q)\rVert_{2}^{2}\leq 2L(F(q)-F_{*}).$ $$

###### Proof.

Consider first the $(L_{0},L_{1})-$smooth case.
Put

$$ (52) $\displaystyle q_{+}=q-\frac{1}{L_{1}\lVert\nabla F(q)\rVert}\nabla F(q),$ $$

Then

$$ $\displaystyle\lVert q_{+}-q\rVert=\frac{1}{L_{1}}$ $$

Thus, the conditions for (21) in Zhang et al. () are satisfied, and it holds that

$$ $\displaystyle F(q_{+})-F(q)\leq\langle\nabla F(q),q_{+}-q\rangle+\frac{L_{0}+L _{1}\lVert\nabla F(q)\rVert}{2}\lVert q_{+}-q\rVert^{2}.$ $$

Inserting (52) into the previous expression we see that

$$ $\displaystyle F(q_{+})-F(q)\leq-\frac{1}{L_{1}}\lVert\nabla F(q)\rVert+\frac{L _{0}+L_{1}\lVert\nabla F(q)\rVert}{2}\frac{1}{L_{1}^{2}},$ $$

Rearranging the terms, we find that

$$ $\displaystyle F(q_{+})-F(q)\leq-\frac{1}{2L_{1}}\lVert\nabla F(q)\rVert+\frac{ L_{0}}{2}\frac{1}{L_{1}^{2}}$ $$

One more rearrangement yields

$$ $\displaystyle\lVert\nabla F(q)\rVert\leq 2L_{1}(F(q)-F(q_{+}))+\frac{L_{0}}{L_ {1}}.$ $$

Since $F(q_{+})\geq F_{*}$ we obtain the statement of the first part of the Lemma. The proof of the second part is very similar but simpler, and therefore omitted.
∎

###### Lemma 5.6 .

Let $F$ satisfy Assumption 5.i) and $f(\cdot,\xi)$ satisfy Assumption 5.iii). Then

$$ (53) $\displaystyle\lVert\nabla f(x,\xi)\rVert_{2}\leq 2NL_{1}\left(F(q)-F_{*}\right )+\frac{L_{0}}{L_{1}},$ $$

almost surely,
where $F_{*}=\frac{1}{N}\sum_{i=1}^{N}\inf_{q\in\mathbb{R}^{d}}f_{i}(x)$.

###### Proof.

We start with showing that there exists a constant $C$ such that

$$ (54) $\displaystyle f(x,\xi)-\inf_{x\in\mathbb{R}^{d}}f(x,\xi)\leq C(F(x)-F_{*}),$ $$

almost surely.
First we note that by the properties of $\inf$ it holds that

$$ $\displaystyle\inf_{x\in\mathbb{R}^{d}}f(x,\xi)$ $\displaystyle=\inf_{x\in\mathbb{R}^{d}}\bigg{(}\frac{1}{|B_{\xi}|}\sum_{i\in B _{\xi}}f_{i}(x)\bigg{)}$ $\displaystyle=\frac{1}{|B_{\xi}|}\cdot\inf_{x\in\mathbb{R}^{d}}\bigg{(}\sum_{i \in B_{\xi}}f_{i}(x)\bigg{)}\geq\frac{1}{|B_{\xi}|}\cdot\sum_{i\in B_{\xi}} \inf_{x\in\mathbb{R}^{d}}f_{i}(x).$ $$

Hence

$$ $\displaystyle\begin{split}f(x,\xi)-\inf_{x\in\mathbb{R}^{d}}f(x,\xi)&=\frac{1} {|B_{\xi}|}\cdot\sum_{i\in B_{\xi}}f_{i}(x)-\inf_{x\in\mathbb{R}^{d}}f(x,\xi) \\ &\leq\frac{1}{|B_{\xi}|}\cdot\sum_{i\in B_{\xi}}f_{i}(x)-\frac{1}{|B_{\xi}|} \cdot\sum_{i\in B_{\xi}}\inf_{x\in\mathbb{R}^{d}}f_{i}(x)\end{split}$ $$

Since $f_{i}(x)-\inf_{x\in\mathbb{R}^{d}}f_{i}(x))\geq 0$, the previous expression can be bounded by

$$ $\displaystyle\frac{1}{|B_{\xi}|}\cdot\sum_{i=1}^{N}f_{i}(x)-\inf_{x\in\mathbb{ R}^{d}}f_{i}(x)=\frac{N}{|B_{\xi}|}\left(F(x)-F_{*}\right).$ $$

As the batch size $|B_{\xi}|$ is non-decreasing, (54) holds.
Since $f(\cdot,\xi)$ is $(L_{0},L_{1})$-smooth,
it holds that

$$ $\displaystyle\lVert\nabla f(x,\xi)\rVert_{2}\leq 2L_{1}\left(f(x,\xi)-\inf_{x \in\mathbb{R}^{d}}f(x,\xi)\right)+\frac{L_{0}}{L_{1}}.$ $$

Combining the previous expression with (54), we obtain (53).
∎

###### Remark 5.6 .

Note that for fixed, *deterministic* $x$, (53) implies that the norm $\lVert\nabla f(x,\xi)-\nabla F(x)\rVert_{2}$ is bounded almost surely. This means that around a stationary point $q_{*}$ or for the initial iterate $q_{0}$ (which in this paper is assumed to be deterministic), the norm of the noise is not heavy-tailed. When $x=q_{k}$ is a random variable this is no longer the case. This is in line with e.g (Gurbuzbalaban et al., ), in which it is reported that the noise is not heavy-tailed initially.

###### Lemma 5.6 .

###### Proof.

###### Lemma 5.6 .

###### Proof.

###### Lemma 5.6 .

###### Proof.

###### Lemma 5.6 .

###### Proof.

###### Lemma 5.6 .

###### Proof.

###### Lemma 5.6 .

###### Proof.

###### Lemma 5.6 .

###### Proof.

###### Remark 5.6 .

## Appendix C Numerical experiments

In order to illustrate the behavior of the algorithms, we set up three numerical experiments.
The experiments are implemented in Tensorflow 2.12 (Abadi et al., ).
We consider the following kinetic energy functions

- •
$\varphi(x)=x$. (Abbreviated as SHD.)
- •
$\varphi(x)=\sqrt{\epsilon+\lVert x\rVert_{2}^{2}}$. (Normalized).
- •
$\varphi(x)=\sqrt{1+\lVert x\rVert_{2}^{2}}$. (SoftClipped.)

In the plots we also see the results of Adam (Kingma & Ba, ), SGD with momentum (abbreviated as SGDmom), Clipped SGD with momentum (ClippedSGDmom) and Clipped SGD (ClippedSGD). All of these algorithms are as implemented in Abadi et al. ().
Each of the experiments were run for $4$ random seeds ranging from
$3000$ to $3003$, that all yielded similar results. In the plots we see the results for the random seed
$3000$. For every experiment we consider a grid of initial step sizes $\beta$ with values

$$ $\displaystyle\left(10^{-4},5\cdot 10^{-4},10^{-3},5\cdot 10^{-3},10^{-2},5 \cdot 10^{-2},0.1,0.5,1\right).$ $$

To find the optimal initial value of $\beta$ among these, we use the Keras implementation of the Hyperband algorithm (Li et al., ); a hyper parameter optimization algorithm that makes use of a combination of random search and successive halving
(Jamieson & Talwalkar, ). In all the experiments, we use a step size scheme defined by $\frac{\beta}{\lfloor k/10\rfloor+1}$, where $\beta$ is the initial step size and $k$ is the epoch.

### C.1. Classification of the MNIST dataset

The first experiment is a simple convolutional neural network used to classify the MNIST dataset (Lecun et al., ). We split the data in the standard way, but use both the training and validation sets for training. The training- and test accuracy after 20 epochs is displayed in Figure 1. All of the algorithms work well for the given problem.
Around the 10th epoch several of the methods see an improvement in training accuracy due to the step size decrease. All the methods converge relatively fast on both training and test data and display performance on par to the state of the art algorithms implemented in Tensorflow.
We also remark that Normalized and SoftClipped perform at their best with a higher step size, like the clipped SGD-methods. The methods all exhibit a smooth behavior on the training data, while the oscillations are slightly higher on the test data.

Figure: Figure 1. Accuracy of the different methods when used for training a simple convolutional neural network to classify the MNIST dataset. Each method displays the result when the optimal initial step size $\beta$ is used.
Refer to caption: x1.png

#### C.1.1. Details on the network architecture

The model consists of one convolutional layer with 32 filters, a kernel size of 3 and a stride of 1. Padding is chosen such that the input has the same shape as the output.
Upon this, a dense layer of 128 neurons is stacked before the output layer with a softmax function. The activation function used in the hidden layers is the *exponential linear unit* (Clevert et al., ).
In both the convolutional- and the dense layers we use a weight decay of $5\cdot 10^{-3}$.

### C.2. Classification of the CIFAR10 dataset

The second experiment is a VGG-network (Simonyan & Zisserman, ) used to classify the CIFAR10 dataset (Krizhevsky, ).
We split the data in the standard way, but use both the training and validation sets for training.
In Figure 2, we see the train- and test accuracy for the methods. We see that all the kinetic energy functions display performance on par with state of the art algorithms.
On the training data, the majority of the methods converge to a stationary point for which the models has an accuracy of about $70$ percent. After the first step size decrease, the algorithms find a new stationary point towards which they converge.
The training curves are smooth, while again the oscillations are slightly higher on the test data during the first $15$ epochs. Adam, Normalized and SoftClipped exhibits a smoother behavior on the test data than the other algorithms.

Figure: Figure 2. Accuracy of the different methods when used for training a VGG-network to classify the CIFAR10 dataset. The two plots in the top shows the first 12 epochs and the two plots in the bottom, all the 50 epochs. Each method displays the result when the optimal initial step size $\beta$ is used.
Refer to caption: x2.png

#### C.2.1. Details on the network architecture

The model consists of three blocks of convolutional layers. The first block consists of two convolutional layers with $32$ filters with kernel size of $3$, each followed by a batch normalization layer (Ioffe & Szegedy, ). This is then passed through a max-pooling layer with a kernel size of $2\times 2$ and a stride of $2$.
In the convolutional layers a weight decay of $5\cdot 10^{-3}$ is used.
The next two blocks have similar structure but with filter sizes of $64$ and $128$ respectively.
In between each layer a drop out of $20\%$ is used. As in the first example we use a dense hidden layer with $128$ neurons before the output layer. In all layers, the exponential linear unit was used as activation function.

### C.3. Text prediction on the Pennsylvania treebank corpus

The last experiment is a long-short-term memory-type model, that we use for text prediction on the Pennsylvania Treebank portion of the Wall Street Journal corpus (Marcus et al., ). The design of the experiment is inspired by similar ones in e.g. Graves (); Mikolov et al. (); Pascanu et al. (); Zhang et al. (). For the experiment, we use the same training and validation split of the dataset as in Merity et al. ().(^6^66We call the validation set ’Test’ in Figure 3 so that it agrees with the terminology in the previous experiments.)

In Figure 3 we see the exponentiated average regret, or *perplexity*

$$ $\displaystyle\exp\left(\frac{1}{K}\sum_{k=1}^{K}f(q_{k},\xi_{k})\right),$ $$

where K is the number of batches in an epoch. For a model that chooses each of the words in the vocabulary with uniform probability we expect this to be close to the size of the vocabulary (in this case $10000$). We expect a well performing model to have a perplexity close to $1$.
In Figure 3, we see the training- and test perplexity for the various methods. The SHD-method achieves a slightly higher perplexity on the training data then the other methods. (Although this behavior is not as pronounced on the test data). In general, methods that make use of some sort of normalization or clipping appears to be working best for this task; the best method is the SoftClipped, which quickly reaches the lowest perplexity on the test data set.

Figure: Figure 3. Perplexity of the different methods when used for text prediction on the Penn. Treebank dataset. Each method displays the result when the optimal initial step size $\beta$ is used.
Refer to caption: x4.png

#### C.3.1. Details on the network architecture

The network consists of an embedding layer of size $400$ upon which three bidirectional LSTM-layers are stacked, each with $1150$ RNN-units. A dropout of $50\%$ is used in the LSTM-layers, as well as weight decay of $1.2\cdot 10^{-6}$. In the output layer, a dense layer with $10000$ neurons is used. The batch size is $64$ and we use a sequence length of $10$ words.

### C.4. Conclusions

The experiments in the previous section verify the theoretical results in the paper and we see that most of the algorithms also exhibit performance on par with state of the art algorithms.
We remark that in all the examples, we used very generic networks for the sake of finding problems on which we could easily compare the behavior of the models. Better performance could be achieved in all cases if the networks and optimizers would have been tuned more carefully to the classification problems, but the intention here is to illustrate the behavior of the algorithms rather than achieving state of the art results.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 6
presentation: 4
questions: 1. (Clarification for Assumption 4 iii) This assumption is not satisfied when $\varphi(x)=||x||^2/2$. For the family of algorithms under study defined by equation 9 to include SGD with momentum we need $\varphi(x)= ||x||^2/2$. So, the analysis does not hold true for SGD with momentum. Is this correct?
2. (Suggestion about numerical experiments in Appendix C) The main claim of the paper that the family of algorithms converges to a stationary point of the objective function can be better demonstrated if there are graphs showing the evolution of $||\nabla F||_2$ with the number of epochs.
soundness: 4
strengths: The paper is written in an easy to understand way and the ideas flow smoothly between sections. On the technical side it has the following strengths:
1. Previous work has given guarantees that hold either in expectation or with high probability. These do not guarantee the convergence of every trajectory. However, the results presented in this paper can guarantee the convergence of almost all the trajectories i.e. there exists a set of initial points of measure zero whose trajectories are not guaranteed to converge.
2. The analysis done in previous work holds true only under strong assumption that the stochastic gradients are bounded. Whereas the current work’s analysis holds under much more general assumption of bounded variance.
summary: The paper studies a family of stochastic gradient methods given by equation 9 and for this family almost sure convergence to stationary points is proved under the following settings:
1. Smooth objective functions with stochastic gradients having locally bounded variance,
2. $(L_0,L_1)$-smooth objective functions with stochastic gradients having finite second moments,
3. $(L_0,L_1)$-smooth objective functions occurring in the empirical risk minimization problem with stochastic gradients having bounded expectation.

Two interesting algorithms that are part of this family are SGD with soft clipped momentum and SGD with normalized momentum.
weaknesses: The paper focuses primarily on proving almost sure convergence and does not provide any claims about convergence rate. The paper could benefit from showing convergence rate of the family of methods given by equation 9 under one of the settings.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 4
questions: - How do you check in pratice Assumption 1-iii). Give a clear and easy to check criterion (based a.g. on Sard's theorem)
- How do you check the conditions of Theorem 5.15
soundness: 3
strengths: - The paper is very well-written, and the authors rigorously verify the standard assumptions of the ODE approach, even if this means including assumptions that may seem idealized.
summary: The paper investigates the almost sure convergence of stochastic Hamiltonian descent methods in optimization, especially in the context of machine learning and statistical estimation. Key methods discussed include gradient normalization and soft clipping, which are used to stabilize stochastic gradient descent (SGD) with momentum, commonly applied in non-convex optimization settings. The authors analyze the convergence properties of these modified SGD algorithms, especially when applied to objective functions with heavy-tailed noise and potentially infinite gradient variance, by classifying these techniques into dissipative Hamiltonian systems.

 One of the main contributions of the paper is to show that gradient normalization and soft clipping can be viewed as stochastic implicit-explicit Euler discretizations of dissipative Hamiltonian systems. By utilizing Hamiltonian dynamics and dynamical systems theory, the authors provide a unified convergence framework for these methods in different objective function settings, including \(L\)-smooth and \((L_0, L_1)\)-smooth functions.

The paper introduces assumptions for the objective function and the stochastic gradient, such as coercivity and locally bounded variance, which ensure that the optimization problem satisfies the necessary conditions for convergence. Moreover, the convergence guarantee is extended to settings with heavy-tailed noise, which is common in real data. In particular, the analysis shows that the iterative updates of these modified SGD algorithms converge almost surely to the set of stationary points of the objective function under these assumptions.

The proof strategy involves the use of a Lyapunov function based on the Hamiltonian of the system to demonstrate the finiteness and boundedness of the iterative sequences. The analysis then uses an ODE (Ordinary Differential Equation) approach to show that these sequences converge almost surely to stationary points of the objective function, and not just in expectation. This result is important because it ensures convergence along each individual optimization path and not just on average, which is crucial for the robustness of optimization algorithms.
weaknesses: The paper doesn’t bring substantial new insights to the field; it essentially revisits classical methods, line by line, and demonstrates the applicability of standard ODE-based techniques. While it is certainly rigorous and methodical, the paper ultimately falls short of deepening our understanding of the algorithms themselves or providing fresh perspectives on their behavior. This makes it a rather conventional contribution, adhering closely to established approaches without pushing beyond them in terms of theoretical or practical insight.

The authors rely on the Kushner and Yin approach, which, although mathematically elegant, has a significant drawback: it depends on assumptions that are notably difficult to verify. For example, Theorem 5.15 includes the assumption that “there exists a compact set in the domain of attraction of \( A \) that \( \{z_k\}_{k \geq 0} \) visits infinitely often.” However, the practicality of checking this condition is questionable. For dissipative systems with Lyapunov functions, more robust and accessible conditions are typically available. For instance, Benaïm’s 2006 work on the dynamics of stochastic approximation provides an alternative perspective with less restrictive assumptions, and the work by Andrieu, Moulines, and Priouret (2005) presents stability criteria that are generally easier to validate. Both of these references suggest that a more flexible framework is possible and may have been preferable in analyzing the convergence behavior.



See Benaïm, M. (2006). Dynamics of stochastic approximation algorithms. In Seminaire de probabilites XXXIII (pp. 1-68). Berlin, Heidelberg: Springer Berlin Heidelberg.
- Andrieu, C., Moulines, É., & Priouret, P. (2005). Stability of stochastic approximation under verifiable conditions. SIAM Journal on control and optimization, 44(1), 283-312. "

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: * Could the authors more clearly explain how their approach seems to extend Kushner and Yin (2003)? This would allow the reader to better evaluate the novel elements needed in the proof almost sure convergence. 
* This next question is not related to the perceived weakness of the paper but more for a deeper understanding of the results. Because the kinetic energy function is assumed to be differentiable, almost sure convergence cannot be concluded for clipping as studied by Zhang et. al. (2020) in expectation. Could the authors explain the need of the differentiability assumption, and why working with the sub-gradients of $\varphi$ is not possible?
soundness: 3
strengths: The paper is well written, structured, and thus easy to follow. It contributes to the theoretical understanding of SGD with momentum under gradient normalization and soft clipping. 

Although I didn't read every proof in extreme detail, I believe the formal arguments and results are correct. 

Minor detail: Since the authors initially present the formulation of the nearly Hamiltonian system in continuous time (see eq. (8)), perhaps the choice of the Lyapunov function in the proof of Theorem 5.7 could be motivated in that context, showing that: $\dot V = -\gamma\||\nabla\varphi\||^2 \leq 0.$
summary: This paper shows the almost sure convergence of a class of stochastic Hamiltonian descent methods, including gradient normalization and soft clipping algorithms, under three different set of assumptions which provide validity of the conclusions to a wide range of settings. The proof relies on the typical argument followed in dynamic systems and control theory, which is to: (1) find a suitable Lyapunov function (in this case the Hamiltonian of the system); and (2) invoke LaSalle's Invariance theorem to establish the convergence to a (isolated) stationary point the (non-convex) objective function.

Typo: Line 112 should read "term" instead of "tern"
weaknesses: The main issue I have with the paper is that, because the proof strategy closely follows the approach developed by Kushner and Yin (2003) (cf. Section 5 and Theorem 5.2.1), it is not immediately clear why their proof cannot be directly invoked after showing that the sequence of iterates is finite almost surely. For example, Lemma A.3 can in fact be found in the first part of Theorem 5.2.1 but this is not explicitly mentioned by the authors. Could the authors explicitly discuss how their proof extends or differs from Kushner and Yin (2003), for example by including a paragraph comparing their approach to Kushner and Yin's and highlighting any novel elements or modifications needed for the Hamiltonian specific setting.

Meta-review: This paper considers gradient normalization and soft clipping methods in the context of Hamiltonian systems. Authors view these as a kind of Euler discretization of dissipative systems and use dynamical systems approach and show convergence to stationary points of the objective function, under several interesting regimes.


This paper was reviewed by three expert reviewers and received the following Scores/Confidence: 6/2, 6/4, 3/5. I think paper is studying an interesting topic but authors are not able to convince the reviewers sufficiently well about the novelty of their work. The following concerns were brought up by the reviewers:

- The main concern about this paper was its novelty in terms of insights it brings to the field. 
- Authors rely on classical techniques in this area, which in turn depend on conditions that are difficult to verify or too opaque in practice.


Although two reviewers were positive, no reviewers championed the paper and they are not particularly excited about the paper. As such, based on the reviewers' suggestion, as well as my own assessment of the paper, I recommend not including this paper to the ICLR 2025 program.

Decision: Reject