\section{Introduction}\label{sec:Intro}

The stochastic approximation (SA) algorithm, originally introduced in
\cite{Robbins-Monro51}, is a widely used method for finding a zero of
a function ${\bf f} : {\mathbb R}^d \rightarrow {\mathbb R}^d$, when only noisy measurements of ${\bf f}$
are available.
Since its introduction, it has been a workhorse of probability theory
and has found many applications.
An early survey can be found in \cite{Lai03}, and a more recent
survey can be found in \cite{Fran-Gram22}.
Here is a quick description of the algorithm.
Suppose ${\bf f} : {\mathbb R}^d \rightarrow {\mathbb R}^d$, and it is desired
to find a solution ${\boldsymbol \theta}^*$ to the equation ${\bf f}({\boldsymbol \theta}) = {\bf 0}$,
when one can access only noisy measurements of ${\bf f}(\cdot)$.
In broad terms, the algorithm proceeds as follows:
One begins with an initial guess ${\boldsymbol \theta}_0$.
In the original version of SA proposed in \cite{Robbins-Monro51},
at time $t+1 \geq 1$, one has access to a noisy measurement
\begin{equation}\label{eq:11a}
{\bf y}_{t+1} = {\bf f}({\boldsymbol \theta}_t) + {\boldsymbol \xi}_{t+1} ,
\end{equation}
where ${\boldsymbol \theta}_t$ is the current guess and ${\boldsymbol \xi}_{t+1}$ is the measurement error.
Then the guess ${\boldsymbol \theta}_t$ is updated according to
\begin{equation}\label{eq:11}
{\boldsymbol \theta}_{t+1} = {\boldsymbol \theta}_t + \alpha_t {\bf y}_{t+1} ,
\end{equation}
where $\{ \alpha_t \}_{t \geq 1}$ is a predetermined sequence of step sizes.
It is desired to study the limit behavior of the sequence $\{ {\boldsymbol \theta}_t \}$.
Of particular interest is the situation where
${\boldsymbol \theta}^*$ is the only solution to the equation $f({\boldsymbol \theta}) = {\bf 0}$.
We would like to find suitable conditions to ensure that the iterates
$\{ {\boldsymbol \theta}_t \}$ converge almost surely to ${\boldsymbol \theta}^*$.

In the original paper \cite{Robbins-Monro51}, 
the step sizes $\alpha_t$ are positive, and satisfy the conditions below,
generally referred to as the Robbins-Monro or RM conditions.
The two conditions are often shown together, but we display them separately
for reasons that will become clear later.
\begin{equation}\label{eq:12a}
\sum_{t=1}^\infty \alpha_t^2 < \infty .
\end{equation}
\begin{equation}\label{eq:12b}
\sum_{t=1}^\infty \alpha_t = \infty ,
\end{equation}
In addition, various assumptions are imposed on the function ${\bf f}(\cdot)$,
which have been relaxed by successive researchers.
Until 2000, the available results had the following general format:
\textit{If} the sequence of iterates $\{ {\boldsymbol \theta}_t \}$ is bounded almost surely,
\textit{then} ${\boldsymbol \theta}_t \rightarrow {\boldsymbol \theta}^*$ almost surely, provided some other conditions
are satisfied.
Some authors refer to the almost-sure boundedness of the
iterates $\{ {\boldsymbol \theta}_t \}$ as ``stability,'' and ${\boldsymbol \theta}_t \rightarrow {\boldsymbol \theta}^*$ almost surely
as ``convergence.''
Thus the typical result stated that stability plus other conditions imply
convergence.

A major breakthrough was achieved in \cite{Borkar-Meyn00}, in which the
stability of the iterations is a conclusion and not a hypothesis.
Thus, under suitable conditions on the function ${\bf f}$, both stability and
convergence follow.
In \cite{Borkar-Meyn00}, the authors follow the well-established ODE
method, whereby the sample paths of the recursion \eqref{eq:11}
are related to the (deterministic) solution trajectories of the
ODE $\dot{{\boldsymbol \theta}} = {\bf f}({\boldsymbol \theta})$.
This method was introduced in \cite{Der-Fradkov74,Ljung77b,Kushner-Clark78}.
A very readable summary of this method is found in \cite{Mete-Priou84}.
The present paper has the same objective, namely to make the stability
of the iterations a conclusion and not a hypothesis.

It is ironic that, as far back as 1965, there is a paper \cite{Gladyshev65}
that established both stability and convergence of the SA algorithm.
This paper uses martingale methods, but is restricted to a special 
class of functions ${\bf f}$.
On the other side, the proof is very short and elegant.
Thus the present author was motivated by a desire to extend the
martingale methods of \cite{Gladyshev65}
to the same class of functions ${\bf f}$ as are covered by the ODE method
in \cite{Borkar-Meyn00}, or perhaps more general.
Towards this end, we state and prove two very general ``framework'' results,
using martingale methods, for the almost sure boundedness and convergence
of a scalar-valued stochastic process, respectively.
These two framework results are abstract versions of the approach
proposed in \cite{Gladyshev65}, and were discovered independently 
of \cite{Robb-Sieg71}, which contains much of the framework.
Interestingly, the authors of \cite{Robb-Sieg71} were apparently unaware
of \cite{Gladyshev65} at the time of writing their paper.
In order to apply these framework results to the case where ${\boldsymbol \theta}^*$ is a 
globally exponentially stable equilibrium of the ODE $\dot{{\boldsymbol \theta}} = {\bf f}({\boldsymbol \theta})$,
we state and prove a new converse theorem on the existence of a
Lyapunov function that has a globally bounded Hessian matrix.
The converse theorem proved here builds on an earlier theorem in
\cite{Corless-Glielmo98}, which uses a significantly different
Lyapunov function compared to its predecessors.
This result is new and is possibly of independent interest within the
stability theory community.
By combining the framework with the new converse theorem,
we get a result along the following lines:
Suppose ${\boldsymbol \theta}^*$ is a
globally exponentially stable equilibrium of the ODE $\dot{{\boldsymbol \theta}} = {\bf f}({\boldsymbol \theta})$,
and ${\bf f}$ satisfies a few other technical conditions.
Then the sequence of iterates $\{ {\boldsymbol \theta}_t \}$ is bounded almost surely
whenever \eqref{eq:12a} holds;
if \eqref{eq:12b} also holds, then ${\boldsymbol \theta}_t \rightarrow {\boldsymbol \theta}^*$ almost surely.
If one were to compare our result to that in \cite{Borkar-Meyn00}, the
requirements on ${\bf f}$ are fewer, and the proof is more direct;
see Theorem \ref{thm:21} below.
Moreover, there is a nice ``division of labor'': Equation \eqref{eq:12a}
guarantees stability of the iterations, and \eqref{eq:12b} guarantees
convergence.
This division of labor is found in \cite{Gladyshev65}, but is not
found in too many other places.

Shortly after the publication of \cite{Robbins-Monro51}, a different
stochastic approximation algorithm was introdeced in \cite{Kief-Wolf-AOMS52}
and analyzed further in \cite{Blum54}.
Suppose $J : {\mathbb R}^d \rightarrow {\mathbb R}$ is in ${\cal C}^1$, and the objective is to find a
stationary point of $J$, that is, a solution of $\nabla J({\boldsymbol \theta}) = {\bf 0}$.
If one has access to possibly noisy measurements of $\nabla J(\cdot)$, then
this is the same as the problem studied in \cite{Robbins-Monro51}.
However, in \cite{Kief-Wolf-AOMS52}, the gradient is approximated using
first-order differences.
Here is the problem formulation.
Let $[d]$ denote $\{ 1 , \cdots , d \}$, and let ${\bf e}_i \in {\mathbb R}^d$ denote the
$i$-th elementary unit vector.
Let $\{ c_t \}$ denote a sequence of ``increments,'' and let ${\boldsymbol \theta}_t$
denote the current guess to the solution of $\nabla J({\boldsymbol \theta}) = {\bf 0}$.
Now define ${\bf y}_{t+1}$ by
\begin{equation}\label{eq:13}
y_{t+1,i} = \frac{ [J ( {\boldsymbol \theta}_t - c_t {\bf e}_i ) + \xi^-_{t+1,i} ]
- [J ( {\boldsymbol \theta}_t + c_t {\bf e}_i ) + \xi^+_{t+1,i} ] }{2 c_t} .
\end{equation}
Thus one systematically perturbs the $i$-th component of the current
guess ${\boldsymbol \theta}_t$ in both the positive and the negative direction by
the increment $c_t$ (which is the same for all coordinates $i$).
and measures the value of $J$ at these $2d$ perturbed vectors.
This process is repeated for each of the $d$ coordinates.
Here, $\xi^-_{t+1,i}$ and $\xi^+_{t+1,i}$ denote respectively the measurement 
errors when the $i$-th coordinate is perturbed in the negative
and positive directions respectively.
With this definition of the measurement vector ${\bf y}_{t+1}$,
${\boldsymbol \theta}_t$ is updated to ${\boldsymbol \theta}_{t+1}$ in accordance with \eqref{eq:11},
where $\{ \alpha_t \}$ is a predetermined sequence of step sizes as before.
This approach is suggested in \cite{Kief-Wolf-AOMS52} for the scalar
case $(d=1)$, and for the multivariable case in \cite{Blum54}, with
slight changes.\footnote{In \cite{Blum54}, instead of $2d$ measurements,
only $d+1$ measurements are used.}
Note that, even noise-free measurements, ${\bf y}_{t+1}$ would only equal
$-\nabla J({\boldsymbol \theta}_t) + \mathbf{o}(c_t)$.
Thus there are \textbf{two} sources of error in \eqref{eq:13}, namely
the use of first-order differences to approximate the gradient,
and the presence of measurement noise vectors.
If one were to rewrite \eqref{eq:13} as
\begin{displaymath}
y_{t+1,i} = \frac{ J ( {\boldsymbol \theta}_t - c_t {\bf e}_i ) 
- J ( {\boldsymbol \theta}_t + c_t {\bf e}_i ) } {2 c_t} 
+ \frac{ \xi^-_{t+1,i} - \xi^+_{t+1,i}  } {2 c_t} ,
\end{displaymath}
then as $c_t \rightarrow 0$, the first term approaches $- [ \nabla J({\boldsymbol \theta}_t) ]_i$,
but the variance of the second term approaches infinity if, as is common,
the measurement errors remain away from zero.

The convergence analysis in \cite{Blum54} is rather convoluted.
In contrast, in the present paper, we use the martingale ``framework''
results to analyze the approach in \eqref{eq:13}.
It is shown that if the function $J$ is ${\cal C}^2$, has a unique
global minimum which can be taken as ${\boldsymbol \theta}^* = {\bf 0}$, and is ``unimodular''
in the sense that $\IP{{\boldsymbol \theta}}{\nabla J({\boldsymbol \theta})} \geq h \nmeusq{{\boldsymbol \theta}}$
for all ${\boldsymbol \theta}$ and some positive constant $h$, then the two conditions
\begin{equation}\label{eq:14}
\sum_{t=0}^\infty \left( \frac{\alpha_t}{c_t} \right)^2 < \infty ,
\sum_{t=0}^\infty \alpha_t c_t < \infty
\end{equation}
are sufficient to imply the almost sure boundedness of the iterates.
If $J(\cdot)$ satisfies a few additional assumptions (stated in
Theorem \ref{thm:22} below), and if in addition to \eqref{eq:14},
we have that
\begin{displaymath}
\sum_{t=0}^\infty \alpha_t = \infty ,
\end{displaymath}
(which is the same as \eqref{eq:12b}), then ${\boldsymbol \theta} \rightarrow {\bf 0}$ almost surely
as $t \rightarrow \infty$.
Note that in \cite{Blum54}, the author adds the condition that $c_t \rightarrow 0$
as $t \rightarrow \infty$.
However, \eqref{eq:12b} and the second equation in \eqref{eq:14}
together imply that $c_t \rightarrow 0$.
Hence this condition is extraneous.
Therefore, just as \eqref{eq:12a} and \eqref{eq:12b} are together
referred to as the Robbins-Monro conditions, it would be appropriate to
refer to \eqref{eq:14} and \eqref{eq:12b} as the Blum conditions.
To shed some light on the Blum conditions, suppose that $\alpha_t = (t+1)^{-p}$
and $c_t = (t+1)^{-r}$.
Then the Blum conditions are equivalent to $p+r < 1$ and $p-r > 1/2$.

\section{Main Results}\label{sec:Main}

To assist the reader in following the paper, we straightaway state the
main results on Stochastic Approximation (SA), as well as the
converse Lyapunov theorem that facilitates the proof.
To stremline the presentations, we state the various assumptions for ready
reference.
For concepts from nonlinear stability theory, the reader is referred to
\cite{MV-93,Khalil02}.

\subsection{Results on Stochastic Approximation}\label{ssec:21}

We begin with standard stochastic approximation as in \eqref{eq:11a},
and state the assumptions on the function ${\bf f} : {\mathbb R}^d \rightarrow {\mathbb R}^d$.
\begin{enumerate}
\item[(F1)] The equation ${\bf f}({\boldsymbol \theta}) = {\bf 0}$ has a unique solution ${\boldsymbol \theta}^*$.
\item[(F2)] The function ${\bf f}$ is twice continuously differentiable, and
is globally Lipschitz-continuous with
constant $L$.
Thus
\begin{equation}\label{eq:21}
\nmeu{{\bf f}({\boldsymbol \theta}) - {\bf f}({\boldsymbol \phi})} \leq L \nmeu{{\boldsymbol \theta} - {\boldsymbol \phi}} ,
\; \forall {\boldsymbol \theta} , {\boldsymbol \phi} \in {\mathbb R}^d .
\end{equation}
Note that, as a consequence of this assumption, for each ${\boldsymbol \theta} \in {\mathbb R}^d$
there is a unique function $\mathbf{s}(\cdot,{\boldsymbol \theta})$ that satisfies the ODE
\begin{equation}\label{eq:22}
\dx{\mathbf{s}(t,{\boldsymbol \theta})}{t} = {\bf f}(\mathbf{s}(t,{\boldsymbol \theta})) , \mathbf{s}(0,{\boldsymbol \theta}) = {\boldsymbol \theta} .
\end{equation}
\item[(F3)] The equilibrium ${\boldsymbol \theta}^*$ of the ODE $\dot{{\boldsymbol \theta}} = {\bf f}({\boldsymbol \theta})$ is
globally exponentially stable.
Thus there exist constants $\mu \geq 1, \gamma > 0$ such that
\begin{equation}\label{eq:23}
\nmeu{\mathbf{s}(t,{\boldsymbol \theta}) - {\boldsymbol \theta}^*} \leq \mu \nmeu{{\boldsymbol \theta} - {\boldsymbol \theta}^*} \exp(-\gamma t),
\; \forall t \geq 0 , \; \forall {\boldsymbol \theta} \in {\mathbb R}^d .
\end{equation}
\item[(F4)] There is a finite constant $K$ such that
\begin{equation}\label{eq:24}
\nmS{\nabla^2 f_i({\boldsymbol \theta})} \cdot \nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*} \leq K ,
\; \forall i \in [d] , \; \forall {\boldsymbol \theta} \in {\mathbb R}^d ,
\end{equation}
where $[d]$ denotes the set $\{ 1 , \ldots , d \}$, and
$\nmS{\cdot}$ denotes the spectral norm of a matrix, i.e., its
largest singular value.
A consequence of \eqref{eq:24} is that
\begin{equation}\label{eq:25}
\left| \tpx{ f_i({\boldsymbol \theta})} { \theta_j } {\theta_k} \right |
\cdot \nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*} \leq K ,
\; \forall i, j, k \in [d] , \; \forall {\boldsymbol \theta} \in {\mathbb R}^d .
\end{equation}
\end{enumerate}

Next we come to the noise sequence $\{ {\boldsymbol \xi}_t \}$ in \eqref{eq:11a}.
For a stochastic process $\{ {\bf x}_t \}$, we use the notation ${\bf x}_\tau^t$
to denote the tuple ${\bf x}_\tau , \cdots , {\bf x}_t$, when $t \geq \tau$.
Suppose the iterative sequence $\{ {\boldsymbol \theta}_t \}$ is defined by the stochastic
approximation algorithm \eqref{eq:11}.
For $t \geq 1$, let ${\cal F}_t$ denote the $\sigma$-algebra generated by the tuples
${\boldsymbol \theta}_0^t,{\boldsymbol \xi}_1^t$ (note that there is no ${\boldsymbol \xi}_0$).
Then it is assumed that $\{ {\boldsymbol \xi}_t \}$ satisfies the following:
\begin{enumerate}
\item[(N1)] The conditional expectation
\begin{equation}\label{eq:26}
E( {\boldsymbol \xi}_{t+1} | {\cal F}_t ) = 0, \mbox{ a.s.}
\end{equation}
This states that the process $\{ {\boldsymbol \xi}_t \}$ is a martingale difference sequence
with respect to the filtration ${\cal F}_t$; 
it also guarantees that the measurement ${\bf y}_{t+1}$ of ${\bf f}({\boldsymbol \theta}_t)$ is unbiased.
\item[(N2)] There exists a constant $d \geq 0$ such that
\begin{equation}\label{eq:27}
E( \nmeusq{{\boldsymbol \xi}_{t+1}} | {\cal F}_t ) \leq d(1 + \nmeusq{{\boldsymbol \theta}_t - {\boldsymbol \theta}^*})
\mbox{ a.s.}, \; \forall t \geq 0 .
\end{equation}
\end{enumerate}

With these assumptions specified, we can now state the main result on
the stability and convergence of the stochastic approximation algorithm
\eqref{eq:11}.

\begin{theorem}\label{thm:21}
Suppose Assumptions (F1)--(F4) and (N1)--(N2) hold.
Under these hypotheses,
\begin{enumerate}
\item If the step size sequence $\{ \alpha_t \}$ satisfies \eqref{eq:12a}, then
the stochastic process $\{ {\boldsymbol \theta}_t \}$ is bounded almost surely.
\item If the step size sequence $\{ \alpha_t \}$ satisfies \eqref{eq:12b}
in addition to \eqref{eq:12a}, then
the stochastic process $\{ {\boldsymbol \theta}_t \}$ converges almost surely to ${\boldsymbol \theta}^*$
as $t \rightarrow \infty$.
\end{enumerate}
\end{theorem}

The closest available results to Theorem \ref{thm:21} in the current
literature are from \cite{Borkar-Meyn00}.
In that paper, it is also assumed that there is a unique solution ${\boldsymbol \theta}^*$
to the equation ${\bf f}({\boldsymbol \theta}) = {\bf 0}$.
In addition, it is assumed that the functions
\begin{displaymath}
{\bf f}_r({\boldsymbol \theta}) : {\boldsymbol \theta} \mapsto \frac{{\bf f}(r {\boldsymbol \theta})}{r} 
\end{displaymath}
converge uniformly over compact sets to a limit function ${\bf f}_\infty$
as $r \rightarrow \infty$,
and that ${\bf 0}$ is a globally exponentially stable equilibrium of the
ODE $\dot{{\boldsymbol \theta}} = {\bf f}_\infty({\boldsymbol \theta})$.\footnote{Actually, in 
\cite{Borkar-Meyn00}, it is assumed only that ${\bf 0}$ is globally
asymptotically stable.
However, due to the scale-invariance of the function ${\bf f}_\infty$,
this implies that actually ${\bf 0}$ is globally exponentially stable.
Moreover, even if the original equilibrium ${\boldsymbol \theta}^* \neq {\bf 0}$, the equilibrium
of the scale-free limit function ${\bf f}_\infty$ can only be ${\bf 0}$.}
There is no requirement of the limit function ${\bf f}_\infty$ here.
Instead we have Assumption (F4), which
requires that the spectral norm of the Hessian matrix of each component
$f_i({\boldsymbol \theta})$ decays at least as fast as $1/\nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*}$.
Obviously, if ${\bf f}({\boldsymbol \theta}) = A {\boldsymbol \theta}$ for some matrix $A$, then this assumption
holds trivially.
Moreover, if ${\bf f} \in {\cal C}^2$, then the Hessian matrix $\nabla^2 f_i({\boldsymbol \theta})$
is bounded over every compact set.
Thus Assumption (F4) is about the behavior of the Hessian $\nabla^2 f_i({\boldsymbol \theta})$
when $\nmeu{{\boldsymbol \theta}}$ is large.
Note that the same can be said about Assumption (F2) as well.
Because ${\bf f}$ is continuously differentiable, it is Lipschitz-continuous
over every compact set; therefore the essence of (F2) is about the
behaviour of the Jacobian matrix $\nabla {\bf f}({\boldsymbol \theta})$ when $\nmeu{{\boldsymbol \theta}}$
is large.
Note that
\begin{displaymath}
\nabla^2 {\bf f}_r({\boldsymbol \theta}) = r \nabla^2 {\bf f}({\boldsymbol \theta}) .
\end{displaymath}
Hence, if the function ${\bf f}_\infty$ exists \textit{and has a globally
bounded Hessian}, then this is essentially the same as (F4).
Thus, with this additional assumption, the present theorem 
includes the result of \cite{Borkar-Meyn00}
as a special case.\footnote{The author is grateful to Prof.\ Sean Meyn
for this observation.}

Now we study the stochastic approximation algorithm when ${\bf y}_{t+1}$
in \eqref{eq:11} is defined as in \eqref{eq:13}.

The objective function $J(\cdot)$ 
is assumed to satisfy the following conditions:
\begin{enumerate}
\item[(J1)] $J(\cdot)$ is in ${\cal C}^2$, and has a unique global minimizer
${\boldsymbol \theta}^*$, which can be taken as ${\bf 0}$ by translating coordinates.
\item[(J2)] There is a constant $h > 0$ such that
\begin{equation}\label{eq:81}
\IP{{\boldsymbol \theta}}{\nabla J({\boldsymbol \theta})} \geq h \nmeusq{{\boldsymbol \theta}} , \; \forall {\boldsymbol \theta} \in {\mathbb R}^d .
\end{equation}
\item[(J3)] $J(\cdot)$ is Lipschitz continuous at ${\bf 0}$ with constant $L$.
Hence
\begin{equation}\label{eq:82}
\nmeu{ \nabla J({\boldsymbol \theta})} \leq L \nmeu{{\boldsymbol \theta}} , \; \forall {\boldsymbol \theta} \in {\mathbb R}^d .
\end{equation}
\item[(J4)] The Hessian $\nabla^2 J(\cdot)$ is globally bounded.
Thus there exists a finite constant $M'$ such that
\begin{equation}\label{eq:83}
\nmS{\nabla^2 J({\boldsymbol \theta})} \leq \frac{M'}{2} , \; \forall {\boldsymbol \theta} \in {\mathbb R}^d ,
\end{equation}
where $\nmS{\cdot}$ denotes the spectral norm of a matrix, that is,
the largest singular value.
\end{enumerate}

Next we state the assumptions on the noise sequences $\{ {\boldsymbol \xi}^-_t \}$,
$\{ {\boldsymbol \xi}^+_t \}$, which is analogs of assumptions (N1) and (N2).
Let ${\cal F}_t$ denote the $\sigma$-algebra generated by ${\boldsymbol \theta}_0^t$,
${\boldsymbol \xi}^{+,t}_{+,1}$ and ${\boldsymbol \xi}^{-,t}_{-,1}$.
Then
\begin{enumerate}
\item[(N3)] We have that
\begin{equation}\label{eq:84}
E ( \xi^+_{t+1,i} | {\cal F}_t ) = 0 , E ( \xi^-_{t+1,i} | {\cal F}_t ) = 0 ,
\mbox{ a.s.}, \; \forall i \in [d], \; \forall t \geq 0 .
\end{equation}
\item[(N4)] Suppose that ${\boldsymbol \xi}^+_t$ and ${\boldsymbol \xi}^-_t$ are independent for
each $t$, and define ${\boldsymbol \xi}_t =  {\boldsymbol \xi}^+_t + {\boldsymbol \xi}^-_t$.
There there is a finite constant $d$ such that
\begin{equation}\label{eq:85}
E( \nmeusq{{\boldsymbol \xi}_{t+1}} | {\cal F}_t ) \leq d(1 + \nmeusq{{\boldsymbol \theta}_t}) , \; \forall t .
\end{equation}
\end{enumerate}

\begin{theorem}\label{thm:22}
Suppose $J: {\mathbb R}^d \rightarrow {\mathbb R}$ satisfies assumptions (J1) through (J4),
and that $\{ {\boldsymbol \theta}_t \}$ is defined by \eqref{eq:11}
where $y_{t+1}$ is defined by \eqref{eq:13}, where the noise sequences
satisfy assumptions (N3) and (N4).
Under these conditions:
\begin{enumerate}
\item If the sequences $\{ \alpha_t \} , \{ c_t \}$ together satisfy
\eqref{eq:14}, then $\{ {\boldsymbol \theta}_t \}$ is bounded almost surely.
\item If, in addition, $\{ \alpha_t \}$ satisfies \eqref{eq:12b}, then
${\boldsymbol \theta}_t \rightarrow {\bf 0}$ almost surely as $t \rightarrow \infty$.
\end{enumerate}
\end{theorem}


\subsection{A New Converse Lyapunov Theorem}\label{ssec:22}

The proof of Theorem \ref{thm:21}
is based on the following converse Lyapunov theorem,
which is new and possibly of independent interest.

\begin{theorem}\label{thm:23}
Suppose Assumptions (F1)--(F4) hold.
Under these hypotheses, there exists a ${\cal C}^2$ function $V : {\mathbb R}^d \rightarrow {\mathbb R}_+$
such that $V$ and its ``derivative'' $\dot{V} : {\mathbb R}^d \rightarrow {\mathbb R}$ defined by
\begin{equation}\label{eq:28}
\dot{V}({\boldsymbol \theta}) = \IP {\nabla V({\boldsymbol \theta})}{ {\bf f}({\boldsymbol \theta}) }
\end{equation}
together satisfy the following conditions:
There exist positive constants $a, b, c$ and a finite constant
$M$ such that
\begin{equation}\label{eq:29}
c_1 \nmeusq{{\boldsymbol \theta}-{\boldsymbol \theta}^*} \leq V({\boldsymbol \theta}) \leq c_2 \nmeusq{{\boldsymbol \theta}-{\boldsymbol \theta}^*} ,
\dot{V}({\boldsymbol \theta}) \leq -c_3 \nmeusq{{\boldsymbol \theta} - {\boldsymbol \theta}^*} , \; \forall {\boldsymbol \theta} \in {\mathbb R}^d .
\end{equation}
\begin{equation}\label{eq:210}
\nmS{\nabla^2 V({\boldsymbol \theta})} \leq 2M , \; \forall {\boldsymbol \theta} \in {\mathbb R}^d .
\end{equation}
\end{theorem}

The existence of a Lyapunov function $V$ that satisfies \eqref{eq:29}
is quite standard.
Indeed, the usual choice is
\begin{equation}\label{eq:211}
V({\boldsymbol \theta}) := \int_0^\infty \nmeusq{\mathbf{s}(t,{\boldsymbol \theta})} dt .
\end{equation}
However, for this choice of $V$,
no conclusions can be drawn about the behavior of the gradient
$\nabla V$ nor the Hessian $\nabla^2 V$.
In \cite{Corless-Glielmo98}, the authors introduce a completely different
Lyapunov function of the form
\begin{equation}\label{eq:212}
V({\boldsymbol \theta}) := \int_0^T e^{\kappa \tau} \nmeusq{\mathbf{s}(\tau,{\boldsymbol \theta} - {\boldsymbol \theta}^*} \; d \tau ,
\end{equation}
where $0 < \kappa < \gamma$ is arbitrary, and $T$ is any \textit{finite}
number such that
\begin{displaymath}
\frac{\ln \mu}{\gamma - \kappa} \leq T < \infty ,
\end{displaymath}
where $\mu, \gamma$ are defined in \eqref{eq:23}.
For this choice of Lyapunov function, it is shown in \cite{Corless-Glielmo98}
that there exists a finite constant $L'$ such that
\begin{equation}\label{eq:213}
\nmeu{\nabla V({\boldsymbol \theta})} \leq L' \nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*} .
\end{equation}
Therefore, the Lyapunov function $V$ of \eqref{eq:211} ``looks quadratic,''
while the Lyapunov function $V$ of \eqref{eq:212} and its gradient
both ``look quadratic.''
Now Theorem \ref{thm:23}
extends the theory further by showing that, if (F4) holds,
then the Lyapunov function $V$, gradient $\nabla V$, and Hessian
$\nabla^2 V$, all ``look quadratic.''
As we shall see, (F4) is the key assumption that allows us to extend the
converse Lyapunov theory of \cite{Corless-Glielmo98}.
In turn this leads to a simple proof of Theorem \ref{thm:21}.

\section{Proof of Theorem \ref{thm:23}}\label{sec:3}

\begin{proof}
Following in \cite{Corless-Glielmo98}, define the Lyapunov function candidate
$V$ as in \eqref{eq:212}.
Then, as shown in \cite{Corless-Glielmo98}, $V$ satisfies \eqref{eq:29}
and \eqref{eq:213}.
The latter is not of any concern to us.
So we focus on proving \eqref{eq:210}.

Note that the solution function $\mathbf{s}(\cdot,{\boldsymbol \theta})$ satisfies
\begin{equation}\label{eq:31}
\mathbf{s}(t,{\boldsymbol \theta}) = {\boldsymbol \theta} + \int_0^t {\bf f}(\mathbf{s}(\tau,{\boldsymbol \theta})) \; d\tau .
\end{equation}
Therefore
\begin{equation}\label{eq:31a}
\nabla_{{\boldsymbol \theta}} \mathbf{s}(t,{\boldsymbol \theta}) = I + \int_0^\tau \nabla_{{\boldsymbol \theta}} {\bf f}(\mathbf{s}(\tau,{\boldsymbol \theta})) \; d\tau .
\end{equation}
Next, the chain rule gives
\begin{displaymath}
\nabla_{{\boldsymbol \theta}} {\bf f}(\mathbf{s}(\tau,{\boldsymbol \theta})) = \left. \nabla_{{\boldsymbol \phi}} {\bf f}({\boldsymbol \phi})
\right|_{{\boldsymbol \phi} = \mathbf{s}(\tau,{\boldsymbol \theta}) } \nabla_{{\boldsymbol \theta}} \mathbf{s}(\tau,{\boldsymbol \theta}) .
\end{displaymath}
Now the global Lipschitz continuity of ${\bf f}$ implies that
\begin{displaymath}
\nmS{ \nabla_{{\boldsymbol \phi}} {\bf f}(\mathbf{s}(\tau,{\boldsymbol \phi})) } \leq L , \; \forall {\boldsymbol \phi} , \; \forall \tau .
\end{displaymath}
Therefore \eqref{eq:31a} leads to (after dropping the subscript ${\boldsymbol \theta}$)
\begin{displaymath}
\nmS{ \nabla \mathbf{s}(t,{\boldsymbol \theta}) } \leq 1 + \int_0^t L \nmS{\nabla \mathbf{s}(\tau,{\boldsymbol \theta})}
\; d\tau .
\end{displaymath}
Now Gronwall's inequality leads to the bound
\begin{equation}\label{eq:31b}
\nmS{ \nabla \mathbf{s}(t,{\boldsymbol \theta}) } \leq \exp(Lt) , \; \forall t , \; \forall {\boldsymbol \theta} .
\end{equation}

Next we proceed to find a bound on the second partial derivatives.
It follows from \eqref{eq:31} that
\begin{displaymath}
\px{s_i(t,{\boldsymbol \theta})}{\theta_j} = \delta_{ij} + \int_0^t \px{f_i(\mathbf{s}(\tau,{\boldsymbol \theta}))}{\theta_j}
\; d\tau ,
\end{displaymath}
where $\delta_{ij}$ is the Kronecker delta.
Next,
\begin{equation}\label{eq:32}
\tpx{s_i(t,{\boldsymbol \theta})}{\theta_j}{\theta_k} = 
\int_0^t \tpx{f_i(\mathbf{s}(\tau,{\boldsymbol \theta}))}{\theta_j}{\theta_k} \; d\tau .
\end{equation}
We will use \eqref{eq:32} later.
Next, expand $V({\boldsymbol \theta})$ as
\begin{displaymath}
V({\boldsymbol \theta}) = \int_0^T e^{2 \kappa \tau} \sum_{i=1}^d [ s_i(\tau,{\boldsymbol \theta}) - \theta_i^* ]^2 
\; d\tau .
\end{displaymath}
Thus
\begin{displaymath}
\px{V({\boldsymbol \theta})}{\theta_j} = \int_0^T 2 e^{2 \kappa \tau} \sum_{i=1}^d 
[ s_i(\tau,{\boldsymbol \theta}) - \theta_i^* ] \px{s_i(\tau,{\boldsymbol \theta})}{\theta_j} \; d\tau ,
\end{displaymath}
\begin{eqnarray*}
\tpx{V({\boldsymbol \theta})}{\theta_j}{\theta_k} & = & \int_0^T 2 e^{2 \kappa \tau} \sum_{i=1}^d
\px{s_i(\tau,{\boldsymbol \theta})}{\theta_k} \px{s_i(\tau,{\boldsymbol \theta})}{\theta_j} \; d\tau \\
& + & \int_0^T 2 e^{2 \kappa \tau} \sum_{i=1}^d
[ s_i(\tau,{\boldsymbol \theta}) - \theta_i^* ] \tpx{s_i(\tau,{\boldsymbol \theta})}{\theta_j}{\theta_k} \; d\tau \\
& = & I_1 + I_2 ,
\end{eqnarray*}
where
\begin{equation}\label{eq:32a}
I_1 = \int_0^T 2 e^{2 \kappa \tau} \sum_{i=1}^d
\px{s_i(\tau,{\boldsymbol \theta})}{\theta_k} \px{s_i(\tau,{\boldsymbol \theta})}{\theta_j} \; d\tau ,
\end{equation}
\begin{equation}\label{eq:32b}
I_2 = \int_0^T 2 e^{2 \kappa \tau} \sum_{i=1}^d
[ s_i(\tau,{\boldsymbol \theta}) - \theta_i^* ] \tpx{s_i(\tau,{\boldsymbol \theta})}{\theta_j}{\theta_k} \; d\tau .
\end{equation}
We will prove the boundedness of each integral separately.
Note that, as a consequence of \eqref{eq:31b}, we have
\begin{displaymath}
\left| \px{s_i(\tau,{\boldsymbol \theta})}{\theta_k} \right| ,
\left| \px{s_i(\tau,{\boldsymbol \theta})}{\theta_j} \right| \leq \nmS{\nabla \mathbf{s}(\tau,{\boldsymbol \theta}) }
\leq \exp{L\tau} , \; \forall \tau , i, j, k .
\end{displaymath}
So the first integral is bounded by
\begin{displaymath}
|I_1| \leq \int_0^T 2d e^{2 \kappa \tau} e^{2L\tau} \; d\tau =: C_1 
< \infty 
\end{displaymath}
for some constant $C_1$, whose precise value need not concern us.
So we concentrate on showing that, under Assumption (F4), $I_2$ is also
bounded globally.

Towards this end, we begin by observing that
\begin{displaymath}
\nmeu{\mathbf{s}(t,{\boldsymbol \theta})} \geq e^{-Lt} \nmeu{{\boldsymbol \theta} - {\boldsymbol \theta}^*} , \; \forall t \geq 0 .
\end{displaymath}
The proof is elementary and is omitted.
In particular
\begin{equation}\label{eq:33}
\nmeu{\mathbf{s}(t,{\boldsymbol \theta})} \geq e^{-LT} \nmeu{{\boldsymbol \theta} - {\boldsymbol \theta}^*} , \; \forall t \in [0,T] .
\end{equation}
Now we estimate the entity $\partial^2 f_i(\mathbf{s}(\tau,{\boldsymbol \theta}))/
\partial \theta_j \partial \theta_k$ in \eqref{eq:32}.
Note that
\begin{displaymath}
\px{f_i}{\theta_j} ( \mathbf{s}(\tau,{\boldsymbol \theta})) = \sum_{l=1}^d
\left. \px{f_i({\boldsymbol \phi})}{\phi_l} \right|_{{\boldsymbol \phi} = \mathbf{s}(\tau,{\boldsymbol \theta})} 
\px{s_l(\tau,{\boldsymbol \theta})}{\theta_j} ,
\end{displaymath}
\begin{eqnarray}
\tpx{f_i(\mathbf{s}(\tau,{\boldsymbol \theta}))}{\theta_j}{\theta_k} & = & \sum_{l=1}^d
\left. \px{f_i({\boldsymbol \phi})}{\phi_l} \right|_{{\boldsymbol \phi} = \mathbf{s}(\tau,{\boldsymbol \theta})}
\tpx{s_l(\tau,{\boldsymbol \theta})}{\theta_j}{\theta_k} \nonumber \\
& + & \sum_{l=1}^d \px{}{\theta_k} \left[ 
\left. \px{f_i({\boldsymbol \phi})}{\phi_l} \right|_{{\boldsymbol \phi} = \mathbf{s}(\tau,{\boldsymbol \theta})} \right]
\px{s_l(\tau,{\boldsymbol \theta})}{\theta_j} . \label{eq:34}
\end{eqnarray}
The second term can be expanded as
\begin{displaymath}
\sum_{l=1}^d \left[ \sum_{r=1}^d
\left. \tpx{f_i({\boldsymbol \phi})}{\phi_l}{\phi_r} \right|_{{\boldsymbol \phi} = \mathbf{s}(\tau,{\boldsymbol \theta})}
\px{s_r(\tau,{\boldsymbol \theta})}{\theta_k} \right] \px{s_l(\tau,{\boldsymbol \theta})}{\theta_j}
\end{displaymath}
Now Assumption (F4) and the bound \eqref{eq:33} together imply that
\begin{displaymath}
\left| \left. \tpx{f_i({\boldsymbol \phi})}{\phi_l}{\phi_r} \right|_{{\boldsymbol \phi} = \mathbf{s}(\tau,{\boldsymbol \theta})}
\right| \leq \nmS{\nabla^2 f_i(\mathbf{s}(\tau,{\boldsymbol \theta}))} \leq
\frac{K}{\nmeu{\mathbf{s}(\tau,{\boldsymbol \theta}) - {\boldsymbol \theta}^*} }
\leq \frac{K e^{LT} }{\nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*} } , \; \forall \tau \in [0,T] .
\end{displaymath}
Also, as shown in \eqref{eq:31b},
\begin{displaymath}
\left| \px{s_r(\tau,{\boldsymbol \theta})}{\theta_k} \right| ,
\left| \px{s_l(\tau,{\boldsymbol \theta})}{\theta_j} \right| \leq \nmS{\nabla \mathbf{s}(\tau,{\boldsymbol \theta})}
\leq e^{L\tau} \leq e^{LT} , \; \forall \tau \in [0,T].
\end{displaymath}
Next, the global Lipschitz continuity of ${\bf f}$ implies that
\begin{displaymath}
\left| \px{f_i({\boldsymbol \phi})}{\phi_l} \right| \leq L .
\end{displaymath}
Substituting all of these bounds into \eqref{eq:32} gives
\begin{eqnarray}
\left| \tpx{s_i(t,{\boldsymbol \theta})}{\theta_j}{\theta_l} \right|
& \leq & \int_0^t L \sum_{l=1}^d \left| \tpx{s_l(\tau,{\boldsymbol \theta})}{\theta_j}{\theta_k} \right|
\; d\tau 
+ \int_0^t \sum_{l=1}^d \sum_{r=1}^d \frac{K e^{LT} e^{L\tau} e^{L\tau} }
{\nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*} } \; dt \nonumber \\
& \leq & C_2 + 
\int_0^t L \sum_{l=1}^d \left| \tpx{s_l(\tau,{\boldsymbol \theta})}{\theta_j}{\theta_k} \right|
\; d\tau , \label{eq:35}
\end{eqnarray}
where
\begin{displaymath}
C_2 = \frac{d^2 TK e^{3LT}}{\nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*} } 
\end{displaymath}
is inversely proportional to $\nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*}$.
Now define
\begin{displaymath}
h_{jk}(t,{\boldsymbol \theta}) := \sum_{i=1}^d \left| \tpx{s_i(t,{\boldsymbol \theta})}{\theta_j}{\theta_k} \right| .
\end{displaymath}
Note that the right side of \eqref{eq:35} does not depend on $i$.
Therefore \eqref{eq:35} implies that
\begin{eqnarray*}
h_{jk}(t,{\boldsymbol \theta}) & \leq & \sum_{i=1}^d \left[ C_2 + \int_0^t L \left|
\sum_{l=1}^d \tpx{s_i(\tau,{\boldsymbol \theta})}{\theta_j}{\theta_k} \right| \right] \\
& \leq & C_2 d + \int_0^t Ld h_{jk}(\tau,{\boldsymbol \theta}) \; d\tau .
\end{eqnarray*}
So by Gronwall's inequality
\begin{displaymath}
h_{jk}(t,{\boldsymbol \theta}) \leq C_2 d e^{LdT} , \; \forall t \in [0,T] .
\end{displaymath}
Since $h_{jk}$ is a sum, each individual component must also be smaller than
$h_{jk}$ in magnitude.
Thus
\begin{displaymath}
\left| \tpx{s_i(t,{\boldsymbol \theta})}{\theta_j}{\theta_l} \right| \leq C_2 d e^{LdT} 
\leq \frac{C_3}{ \nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*} }
\end{displaymath}
for a suitable constant $C_3$.
Therefore we have established that the Hessian of each $s_i$ decays
as ${\boldsymbol \theta}$ gets farther away from ${\boldsymbol \theta}^*$.
Now we return to $I_2$ as defined in \eqref{eq:32b}, and observe that,
as a consequence of Assumption (F3) of global exponential stability, we have
\begin{displaymath}
| s_i(t,{\boldsymbol \theta}) - \theta_i^* | \leq \nmeu{\mathbf{s}(t,{\boldsymbol \theta}) - {\boldsymbol \theta}^*}
\leq \mu \nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*} , \; \forall t \geq 0 .
\end{displaymath}
Now in the definition of $I_2$, we get the bound
\begin{displaymath}
| s_i(t,{\boldsymbol \theta}) - \theta_i^* | \cdot 
\left| \tpx{s_i(\tau,{\boldsymbol \theta})}{\theta_j}{\theta_k} \right| 
\leq \mu \nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*} \cdot \frac{C_3}{ \nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*} }
= \mu C_3 .
\end{displaymath}
Since the integrand in \eqref{eq:32b} is bounded and $T$ is finite, it
follows that $I_2$ is also bounded.
This finally leads to the desired conclusion that $\nmS{ \nabla^2 V}$
is globally bounded.
\end{proof}

Note that in the above proof, the finiteness of the constant $T$ is crucial.
Therefore the traditional infinite integral type of Lyapunov function
defined in \eqref{eq:211} is not amenable to such analysis.

\section{A Framework for Martingale Methods}\label{sec:3a}

In this section, we present two technical lemmas which capture the
essence of the proof technique in \cite{Gladyshev65}.
These lemmas are used in the proofs of Theorems \ref{thm:21} 
and \ref{thm:22}.
Though the present author discovered these two lemmas independently,
it appears that Lemma \ref{lemma:41} is to be found in \cite{Robb-Sieg71}.
In turn those authors were apparently unaware that their proof technique
resembled that in \cite{Gladyshev65}.
The reference \cite{Robb-Sieg71} is difficult to locate,
but the relevant result, analogous
to the present Lemma \ref{lemma:41}, is
restated as \cite[Lemma 4.1]{Fran-Gram22}.\footnote{The author thanks
Prof.\ Boris Polyak for the reference \cite{Fran-Gram22}, and
Prof.\ Barbara Franci for supplying a copy of \cite{Robb-Sieg71}.}

\begin{lemma}\label{lemma:41}
Suppose $(\Omega,\Sigma,P)$ is a probability space, $\{ {\cal F}_t \}$ is a
filtration,
and $\{ X_t \}$ is a nonnegative-valued stochastic process that is
adapted to $\{ {\cal F}_t \}$.\footnote{This means that $\{ {\cal F}_t \}$ is an increasing
sequence of $\sigma$-algebras, and that $X_t$ is measurable with respect
to ${\cal F}_t$, denoted by $X_t \in {\cal M}({\cal F}_t)$.}
Suppose $\{ w_t \}$ is a summable sequence of positive numbers, and that
\begin{equation}\label{eq:71}
E(X_{t+1} | {\cal F}_t) \leq (1 + w_t ) X_t + w_t \mbox{ a.s.} , \; \forall t \geq 0 .
\end{equation}
Then
\begin{enumerate}
\item $\{ X_t \}$ is bounded almost surely, and
\item There is a random variable $\zeta$ such that $X_t \rightarrow \zeta$
almost surely as $t \rightarrow \infty$.
\end{enumerate}
\end{lemma}

\textbf{Remark:} Note that in \cite{Robb-Sieg71}, the assumption
\eqref{eq:71} is replaced by
\begin{displaymath}
E(X_{t+1} | {\cal F}_t) \leq (1 + w_t ) X_t + \epsilon_t \mbox{ a.s.} , \; \forall t \geq 0 ,
\end{displaymath}
where $\{ w_t \}, \{ \epsilon_t \}$ are both summable sequences of positive
numbers.
This alternate formulation does not offer any advantage because
one can replace both $w_t$ and $\epsilon_t$ by $\max \{ w_t , \epsilon_t \}$,
and \eqref{eq:71} holds.
More generally, the sequences $\{ w_t \}, \{ \epsilon_t \}$ are allowed to be
stochastic processes, in which case the conclusions hold on the subset
of $\Omega$ over which both sequences are summable.
We do not require this more general situation here.

\begin{proof}
The idea is taken from \cite{Gladyshev65}.
We define a new stochastic process $\{ Z_t \}$ which is an
affine transformation of $\{ X_t \}$ such that $\{ Z_t \}$ is a
nonnegative supermartingale.
Accordingly, define
\begin{equation}\label{eq:72}
Z_t = a_t X_t + b_t ,
\end{equation}
where $\{ a_t \} , \{ b_t \}$ are constants to be chosen appropriately.
Then it follows from \eqref{eq:71} that
\begin{eqnarray}
E(Z_{t+1} | {\cal F}_t ) & = & a_{t+1} E(X_{t+1} | {\cal F}_t ) + b_t \nonumber \\
& \leq & a_{t+1} (1+w_t) X_t + a_{t+1} w_t + b_{t+1} \nonumber \\
& = & a_{t+1} (1+w_t) \left[ \frac{Z_t - b_t}{a_t} \right]
+ a_{t+1} w_t + b_{t+1} \nonumber \\
& = & \frac{a_{t+1} (1+w_t)}{a_t} Z_t - \frac{a_{t+1} (1+w_t)}{a_t} b_t
+ a_{t+1} w_t + b_{t+1} . \label{eq:73}
\end{eqnarray}
So we get the supermartingale property
\begin{displaymath}
E(Z_{t+1} | {\cal F}_t ) \leq Z_t
\end{displaymath}
provided we define $a_{t+1}$ and $b_{t+1}$ in such a way that
\begin{displaymath}
\frac{a_{t+1} (1 + w_t  )}{a_t} = 1 , \mbox{ or }
a_{t+1} = \frac{a_t}{1 + w_t } ,
\end{displaymath}
\begin{displaymath}
- b_t + a_{t+1} w_t  + b_{t+1} = 0 , \mbox{ or }
b_{t+1} = b_t - w_t  a_{t+1} .
\end{displaymath}
The above recursive relationships define $a_t$ and $b_t$ completely once
we specify $a_0$ and $b_0$.
To ensure that $Z_t \geq 0$ for all $t$, we choose
\begin{displaymath}
a_0 = \prod_{t=0}^\infty (1 +  w_t) ,
b_t
= \sum_{t=0}^\infty  w_t a_{t+1} .
\end{displaymath}
The summability of the sequence $\{ w_t \}$ ensures
that both $a_0$ and $b_0$ are well-defined.
This gives the closed-form expressions
\begin{displaymath}
a_t = \prod_{k=t}^\infty (1 +  w_k) ,
b_t
= \sum_{k=t}^\infty w_k a_{k+1}
= \sum_{k=t}^\infty w_k \prod_{m=k+1}^\infty (1 +  w_m) .
\end{displaymath}
Moreover, we have
\begin{displaymath}
1 < a_{t+1} < a_t < a_0 , 0 < b_{t+1} < b_t < b_0 , \; \forall t .
\end{displaymath}
Therefore $a_t \downarrow a_\infty \geq 1$ and $b_t \downarrow b_\infty \geq 0$.
With the above choices for $a_t, b_t$,
$\{ Z_t \}$ is a nonnegative supermartingale.
By \cite[Theorem 4.2.12]{Durrett19}, $\{ Z_t \}$ is bounded almost surely,
and converges almost surely to some random variable $\zeta'$.
Because $a_t \rightarrow a_\infty \geq 1$ and $b_t \rightarrow b_\infty$,
it follows from \eqref{eq:72} that $\{ X_t \}$ is bounded almost surely,
and converges almost surely $\zeta := (\zeta' - b_\infty)/a_\infty$.
\end{proof}

\begin{lemma}\label{lemma:42}
Let $(\Omega,\Sigma,p)$ and $\{ {\cal F}_t \}$ be as in  Lemma \ref{lemma:41}.
Suppose $\{ w_t \},\{ u_t \}$ are sequences of positive numbers such that
\begin{equation}\label{eq:74}
\sum_{t=0}^\infty w_t < \infty, \sum_{t=0}^\infty u_t = \infty .
\end{equation}
Suppose $\{ X_t \}$ is a nonnegative stochastic process that is
adapted to $\{ {\cal F}_t \}$, and that satisfies
\begin{equation}\label{eq:75}
E(X_{t+1} | {\cal F}_t ) \leq (1+w_t-u_t) X_t + w_t, \mbox{ a.s.}, \; \forall t \geq 0.
\end{equation}
Then $\{ X_t \}$ is bounded almost surely, and converges almost surely
to $0$ as $t \rightarrow \infty$.
\end{lemma}

\textbf{Remark:} Some version of this lemma is available in
\cite{Robb-Sieg71}, and as \cite[Lemma 4.2]{Fran-Gram22}.
However, the statement in the latter is for sequences and not
stochastic processes.
The present lemma gives a slight improvement.

\begin{proof}
Since $u_t > 0$ for all $t$, \eqref{eq:75} implies \eqref{eq:71}.
Hence Lemma \ref{lemma:41} applies, and it follows that $\{ X_t \}$
is bounded almost surely and that ${\cal X}_t \rightarrow \zeta$ almost surely
for some random variable $\zeta$.
Moreover, since $\{ Z_t \}$ defined in \eqref{eq:72} is a nonnegative
supermartingale, it follows that
\begin{displaymath}
E[Z_t,P] \leq E[Z_0,P] , \; \forall t \geq 0 .
\end{displaymath}
Since $Z_t = a_t X_t + b_t$ and $a_t \geq a_\infty \geq 1$ for all $t$,
and $b_t \geq 0$ for all $t$, we conclude that
\begin{equation}\label{eq:76}
E[X_t,P] = \frac{1}{a_t} E[Z_t,P] - \frac{b_t}{a_t} 
\leq \frac{1}{a_\infty} E[Z_0,P] =: H, \mbox{ say} .
\end{equation}
For convenience, define
\begin{displaymath}
W := \sum_{t=0}^\infty w_t .
\end{displaymath}

Next, observe that, for any random variable $Y$, we have that
\begin{displaymath}
E[E(Y|{\cal F}_t),P] = E[Y,P] .
\end{displaymath}
Therefore it follows from \eqref{eq:76} 
\begin{displaymath}
E[X_{t+1},P] \leq (1+w_t-u_t) E[X_t,P] + w_t , \; \forall t \geq 0 ,
\end{displaymath}
which can be rewritten as
\begin{displaymath}
E[X_{t+1},P] - E[X_t,P] \leq w_t (1+E[X_t,P]) - u_t E[X_t,P] , \; \forall t \geq 0 .
\end{displaymath}
Now sum over $\tau$ ranging from $0$ to $t$.
This gives
\begin{displaymath}
\sum_{\tau=0}^t \left\{ E[X_{\tau+1},P] - E[X_\tau,P] \right\}
\leq \sum_{\tau=0}^t w_\tau (1+E[X_\tau,P]) - \sum_{\tau=0}^t u_\tau E[X_\tau,P] .
\end{displaymath}
However, the sum on the left side is a telescoping sum.
Therefore the above can be rewritten as
\begin{displaymath}
E[X_{t+1},P] - E[X_0,P] \leq \sum_{\tau=0}^t w_\tau (1+E[X_\tau,P]) -
\sum_{\tau=0}^t u_\tau E[X_\tau,P] .
\end{displaymath}
This can in turn be rearranged as
\begin{eqnarray*}
\sum_{\tau=0}^t u_\tau E[X_\tau,P] & \leq & \{ E[X_0,P] - E[X_{t+1},P] \} +
\sum_{\tau=0}^t w_\tau (1+E[X_\tau,P]) \\
& \leq & E[X_0,P] + \sum_{\tau=0}^t w_\tau (1+E[X_\tau,P]) \\
& \leq & H + W(1+H) .
\end{eqnarray*}
Since the right side does not depend on $t$, we can conclude that
\begin{equation}\label{eq:77}
\sum_{t=0}^\infty u_t E[X_t,P] \leq H + W(1+H) < \infty .
\end{equation}
Since the sum $\sum_t u_t$ diverges, it follows that
\begin{equation}\label{eq:77a}
\liminf_{t \rightarrow \infty} E[X_t,P] = 0 .
\end{equation}
Otherwise, there would exist a time $T$ and an $\epsilon > 0$ such that
\begin{displaymath}
E[X_t,P] \geq \epsilon , \; \forall t \geq T ,
\end{displaymath}
which contradicts \eqref{eq:77} because $\sum_{t=T}^\infty u_t = \infty$.
(Dropping finitely many terms does not affect the limit.)
Now \eqref{eq:77a} implies that there is a subsequence $\{ t_k \}$
such that $X_{t_k} \rightarrow 0$ in probability as $k \rightarrow \infty$.
In turn this implies the existence of yet another subsequence of $\{ t_k \}$,
which is again denoted by $\{ t_k \}$, such that $X_{t_k} \rightarrow 0$ 
almost surely as $k \rightarrow \infty$.
Snce we already know that $X_t \rightarrow \zeta$ almost surely as $t \rightarrow \infty$,
this implies that $\zeta = 0$ almost surely, and that $X_t \rightarrow 0$
almost surely as $t \rightarrow \infty$.
\end{proof}

\section{Proofs of Theorems \ref{thm:21} and \ref{thm:22}}\label{sec:4}

\subsection{Proof of Theorem \ref{thm:21}}\label{ssec:41}

In this section we prove Theorem \ref{thm:21}.
A little historical perspective is given first.
Shortly after the introduction of the SA algorithm in \cite{Robbins-Monro51},
The paper \cite{Gladyshev65} gave a simple proof of both the stability and
the convergence of the SA algorithm whenever the
function ${\bf f}$ satisfies the condition
\begin{equation}\label{eq:40a}
\inf_{\epsilon < \nmeu{{\boldsymbol \theta}-{\boldsymbol \theta}^*} < 1/\epsilon} \IP{{\boldsymbol \theta}-{\boldsymbol \theta}^*}{{\bf f}({\boldsymbol \theta}} < 0 ,
0 < \epsilon < 1 .
\end{equation}
If ${\bf f}(\cdot)$ is continuous, the above is equivalent to
\begin{equation}\label{eq:40b}
\IP{{\boldsymbol \theta}-{\boldsymbol \theta}^*}{{\bf f}({\boldsymbol \theta}} < 0 , \; \forall {\boldsymbol \theta} \neq {\boldsymbol \theta}^* .
\end{equation}
In \cite[Section 5.3.2]{BMP92}, the condition above on ${\bf f}$ is replaced
by the assumption that there exists a ${\cal C}^2$ Lyapunov function $V$
that satisfies \eqref{eq:29} and \eqref{eq:210}.
The point to note is that this assumption \textit{does not readily get
translated} into a set of conditions on ${\bf f}$.
Thus, except for the rather trivial case where ${\bf f}$ is linear,
there was no way to use this approach.
Our main contribution is to build on the Lyapunov function proposed in
\cite{Corless-Glielmo98}, and convert the above assumption on $V$
into readily verifiable assumptions on ${\bf f}$.
The proof of Theorem \ref{thm:21} is based on the
martingale methods framework of Section \ref{sec:3a}.

Now the proof begins.
For notational simplicity, suppose ${\boldsymbol \theta}$ is changed to ${\boldsymbol \theta}-{\boldsymbol \theta}^*$,
and ${\bf f}({\boldsymbol \theta})$ is changed to ${\bf f}({\boldsymbol \theta}-{\boldsymbol \theta}^*)$, so that the unique solution
to ${\bf f}({\boldsymbol \theta}) = {\bf 0}$ is ${\boldsymbol \theta} = {\bf 0}$.
Then \eqref{eq:27} continues to hold with possibly a different (but
still finite) constant, which we continue to denote by $d$.
Thus Assumption (N2) now becomes
\begin{equation}\label{eq:41}
E( \nmeusq{{\boldsymbol \xi}_{t+1} } | {\cal F}_t ) \leq d ( 1 + \nmeusq{{\boldsymbol \theta}_t} ) \mbox{ a.s.}, \; \forall t.
\end{equation}
Now choose a Lyapunov function $V$ that satisfies all the properties in
\eqref{eq:29} and \eqref{eq:210}.
Such a $V$ exists, as per Theorem \ref{thm:23}.
Note that
\begin{displaymath}
V({\boldsymbol \theta}_{t+1}) = V({\boldsymbol \theta}_t + \alpha_t ( {\bf f}({\boldsymbol \theta}_t) + {\boldsymbol \xi}_{t+1}) ) .
\end{displaymath}
Now by Taylor's expansion around ${\boldsymbol \theta}_t$, we get
\begin{eqnarray*}
V({\boldsymbol \theta}_{t+1}) & = & V({\boldsymbol \theta}_t) + \alpha_t \IP {\nabla V({\boldsymbol \theta}_t) }
{{\bf f}({\boldsymbol \theta}_t) + {\boldsymbol \xi}_{t+1} } + r_{t+1} \\
& = & V({\boldsymbol \theta}_t) + \alpha_t \dot{V}({\boldsymbol \theta}_t) + \alpha_t \IP{\nabla V({\boldsymbol \theta}_t)}
{{\boldsymbol \xi}_{t+1}} + r_{t+1} ,
\end{eqnarray*}
where the remainder term $r_{t+1}$ satisfies
\begin{displaymath}
r_{t+1} = \frac{1}{2} \alpha_t^2 [ {\bf f}({\boldsymbol \theta}_t) + {\boldsymbol \xi}_{t+1} ]^\top \nabla^2 V({\bf z}_t)
[ {\bf f}({\boldsymbol \theta}_t) + {\boldsymbol \xi}_{t+1} ]
\end{displaymath}
for some ${\bf z}_t$ belonging to the line segment from ${\boldsymbol \theta}_t$ to ${\boldsymbol \theta}_{t+1}$.
Therefore, by applying \eqref{eq:210}, we get
\begin{eqnarray*}
| r_{t+1} | & \leq & \alpha_t^2 M \nmeusq{ {\bf f}({\boldsymbol \theta}_t) + {\boldsymbol \xi}_{t+1} } \\
& = & \alpha_t^2 M [ \nmeusq{{\bf f}({\boldsymbol \theta}_t)} + \nmeusq{{\boldsymbol \xi}_{t+1}^2}
+ 2 {\bf f}({\boldsymbol \theta}_t)^\top {\boldsymbol \xi}_{t+1} ] .
\end{eqnarray*}
Now we observe that $\nmeu{{\bf f}({\boldsymbol \theta}_t)} \leq L \nmeu{{\boldsymbol \theta}_t}$ due to the
Lipschitz continuity of ${\bf f}$.
If we couple this with (N1), (N2), and the first bound in \eqref{eq:29}.
we get
\begin{eqnarray*}
E( r_{t+1} | {\cal F}_t ) 
& \leq & \alpha_t^2 M [ L^2 \nmeusq{{\boldsymbol \theta}_t} + d (1 + \nmeusq{{\boldsymbol \theta}_t} ) ] \\
& \leq & \alpha_t^2 \left[ \frac{M(L^2+d)}{c_1} V({\boldsymbol \theta}_t) + Md \right] \\
& \leq & \alpha_t^2 \bar{d} (1+ V({\boldsymbol \theta}_t)) ,
\end{eqnarray*}
where
\begin{displaymath}
\bar{d} := \max \left\{ \frac{M(L^2+d)}{c_1} , Md \right\} .
\end{displaymath}
Also, note that the last bound in \eqref{eq:29} can be rewritten as
\begin{displaymath}
\dot{V}({\boldsymbol \theta}) \leq - c_3 \nmeusq{{\boldsymbol \theta}} \leq - c_4 V({\boldsymbol \theta}) ,
\end{displaymath}
where $c_4 = c_3/c_2$.
Combining all of these upper bounds results in
\begin{eqnarray}
E( V({\boldsymbol \theta}_{t+1}) | {\cal F}_t ) & = &
V({\boldsymbol \theta}_t) + \alpha_t \IP{\nabla V({\boldsymbol \theta}_t)}
{{\bf f}({\boldsymbol \theta}_t)} + E( r_{t+1} | {\cal F}_t ) \nonumber \\
& = & V({\boldsymbol \theta}_t) + \alpha_t \dot{V}({\boldsymbol \theta}_t) + E( r_{t+1} | {\cal F}_t ) \nonumber \\
& \leq & V({\boldsymbol \theta}_t) - \alpha_t c_4 V({\boldsymbol \theta}_t) + \alpha_t^2 \bar{d} (1+ V({\boldsymbol \theta}_t))
\label{eq:42}
\end{eqnarray}
Now apply Lemma \ref{lemma:42} with $w_t = \alpha_t^2 \bar{d}$ and $u_t = \alpha_t c_4$.
This shows that $V({\boldsymbol \theta}_t) \rightarrow 0$ almost surely as $t \rightarrow \infty$.
Now the leftmost inequality in \eqref{eq:29} implies that ${\boldsymbol \theta}_t \rightarrow {\bf 0}$
almost surely as $t \rightarrow \infty$.

\subsection{Proof of Theorem \ref{thm:22}}\label{ssec:42}

Using Taylor's theorem, one can conclude that
\begin{displaymath}
\frac{ J ( {\boldsymbol \theta}_t - c_t {\bf e}_i ) - J ( {\boldsymbol \theta}_t + c_t {\bf e}_i ) }{2 c_t} 
= - [\nabla J({\boldsymbol \theta})]_i + 2 [ \nabla^2 J({\boldsymbol \theta} + \lambda {\bf e}_i)]_{ii} c_t ,
\end{displaymath}
for some $\lambda \in [-1,1]$.
Hence we can write $y_{t+1,i}$ of \eqref{eq:13} as
\begin{displaymath}
y_{t+1,i} = - [\nabla J({\boldsymbol \theta}_t)]_i + c_t r_{t,i} + \frac{1}{c_t} \xi_{t+1,i} ,
\end{displaymath}
\begin{equation}\label{eq:91}
{\bf y}_{t+1} = - \nabla J({\boldsymbol \theta}_t) + c_t {\bf r}_t + \frac{1}{c_t} {\boldsymbol \xi}_{t+1,i} ,
\end{equation}
where ${\boldsymbol \xi}_{t+1} = 2( {\boldsymbol \xi}^-_{t+1} - {\boldsymbol \xi}^+_{t+1})$, and
\begin{displaymath}
r_{t,i} = 2 [ \nabla^2 J({\boldsymbol \theta} + \lambda {\bf e}_i)]_{ii} .
\end{displaymath}
Though ${\bf r}_t$ is random (because ${\boldsymbol \theta}_t$ is random),
\eqref{eq:83} guarantees that
\begin{displaymath}
| r_{t,i} | \leq M' , \; \forall t .
\end{displaymath}
(Here we use the fact that for any matrix $A$, we have that
$A_{ii} \leq \nmS{A}$ for all $i \in [d]$.)
Consequently $\nmeu{{\bf r}_t} \leq \sqrt{d} M' =: M_0$, for all $t$.

Now let analyze the recursion \eqref{eq:11},
using the hypotheses, in particular \eqref{eq:84} and \eqref{eq:85}.
This gives
\begin{eqnarray*}
\nmeusq{{\boldsymbol \theta}_{t+1}} & = & \nmeusq{{\boldsymbol \theta}_t + \alpha_t {\bf y}_{t+1}} \\
& = & \nmeusq{ {\boldsymbol \theta}_t - \alpha_t \nabla J({\boldsymbol \theta}_t) + \alpha_t c_t {\bf r}_t
+ (\alpha_t/c_t) {\boldsymbol \xi}_{t+1} } .
\end{eqnarray*}
If we expand the Euclidean norm squared on the right side, we get
four square terms and six cross product terms.
The conditional expectation of these terms can be bounded using
the following facts, all of which hold almost surely and for all $t$:
\begin{displaymath}
E( \nmeusq{{\boldsymbol \xi}_{t+1}^2} | {\cal F}_t ) \leq d( 1+ \nmeusq{{\boldsymbol \theta}_t}) ,
\end{displaymath}
\begin{displaymath}
E( {\boldsymbol \xi}_{t+1} | {\cal F}_t ) = {\bf 0} ,
\end{displaymath}
\begin{displaymath}
\nmeu{{\bf r}_t} \leq M_0 ,
\end{displaymath}
\begin{displaymath}
\nmeu{\nabla J({\boldsymbol \theta}_t)} \leq L \nmeu{{\boldsymbol \theta}_t} ,
\end{displaymath}
\begin{displaymath}
\IP{{\boldsymbol \theta}_t}{\nabla J({\boldsymbol \theta}_t)} \geq h \nmeusq{{\boldsymbol \theta}_t} .
\end{displaymath}
These substitutions lead to the following complicated expression which
we will simplify in stages.
\begin{eqnarray}
E( \nmeusq{{\boldsymbol \theta}_{t+1}} | {\cal F}_t ) & \leq & 
\nmeusq{{\boldsymbol \theta}_t} [ 1 + \alpha_t^2 L^2 + (\alpha_t/c_t)^2 d ]
+ \alpha_t^2 c_t^2 M_0^2 + (\alpha_t/c_t)^2 d \nonumber \\
& + & 2 \nmeu{{\boldsymbol \theta}_t} ( \alpha_t c_t M_0 + \alpha_t^2 c_t L M_0 )
- 2 \alpha_t \IP{{\boldsymbol \theta}_t}{\nabla J({\boldsymbol \theta}_t)} . \label{eq:92}
\end{eqnarray}
On the right side,
there are constant terms, linear terms, and quadratic terms in $\nmeu{{\boldsymbol \theta}_t}$.
To make things uniform,
we replace $\nmeu{{\boldsymbol \theta}_t}$ by its upper bound\footnote{Actually
$\nmeu{{\boldsymbol \theta}_t} \leq (1+\nmeusq{{\boldsymbol \theta}_t})/2$.
However, we drop the factor $2$ to keep the formulas less cluttered.}
$1 + \nmeusq{{\boldsymbol \theta}_t}$,
and $\alpha_t \IP{{\boldsymbol \theta}_t}{\nabla J({\boldsymbol \theta}_t)} $ by its lower bound
$\alpha_t h \nmeusq{{\boldsymbol \theta}_t}$.
This gives
\begin{equation}\label{eq:92a}
E( \nmeusq{{\boldsymbol \theta}_{t+1}} | {\cal F}_t ) \leq \nmeusq{{\boldsymbol \theta}_t} ( 1 + p_{t,1}) + p_{t,2}
- 2 \alpha_t h \nmeusq{{\boldsymbol \theta}_t} ,
\end{equation}
where
\begin{displaymath}
p_{t,1} = \alpha_t^2 L^2
+ 2 ( \alpha_t c_t M_0 + \alpha_t^2 c_t L M_0 ) + (\alpha_t/c_t)^2 d ,
\end{displaymath}
\begin{displaymath}
p_{t,2} = 2 ( \alpha_t c_t M_0 + \alpha_t^2 c_t L M_0 ) + \alpha_t^2 c_t^2 M_0^2 .
\end{displaymath}
Define $p_t = \max \{ p_{t,1},p_{t,2} \}$.
Then we can replace \eqref{eq:92a} by
\begin{equation}\label{eq:93}
E( \nmeusq{{\boldsymbol \theta}_{t+1}} | {\cal F}_t ) \leq \nmeusq{{\boldsymbol \theta}_t} ( 1 + p_t) + p_t
- 2 \alpha_t h \nmeusq{{\boldsymbol \theta}_t} .
\end{equation}
By hypothesis, the sum $\sum_{t=0}^\infty h \alpha_t$ diverges.
So if we can establish that $\{ p_t \}$ is summable, then it would follow
from Lemma \ref{lemma:42} that $\nmeusq{{\boldsymbol \theta}_t} \rightarrow 0$ almost surely as
$t \rightarrow \infty$, which in turn implies that ${\boldsymbol \theta}_t \rightarrow {\bf 0}$ almost surely as $t \rightarrow \infty$.
This is established next.
Recall the two hypotheses that
\begin{displaymath}
\sum_{t=0}^\infty \alpha_t c_t < \infty ,
\sum_{t=0}^\infty (\alpha_t/c_t)^2 < \infty .
\end{displaymath}
So, if $\{ \alpha_t c_t \}$ is summable, then it is also square-summable.
Moreover, since $\alpha_t$ is bounded, the sequence $\{ \alpha_t^2 c_t \}$
is also summable.
Finally, $\{ \alpha_t \}$ itself is square-summable because $c_t \rightarrow 0$,
so that for $t$ sufficiently large, we have that $\alpha_t /c_t \geq \alpha_t$,
and $\{ \alpha_t /c_t \}$ is square-summable.
These observations show that each of the terms that make up $p_t$,
namely (excluding constants) $\alpha_t^2 , \alpha_t^2 c_t^2, \alpha_t c_t,
\alpha_t^2 c_t, (\alpha_t/c_t)^2$, are all summable.
The desired conclusion now follows from Lemma \ref{lemma:42}.

\section{Conclusions and Future Work}\label{sec:Conc}

In this paper, we have presented a simple proof for the convergence of
the stochastic approximation (SA) algorithm, based on martingale methods and
a new converse theorem for Lyapunov stability.
The latter result is new and may be of independent interest.
The fact that the proof is based on Lyapunov theory, and not the
more complicated ODE
method discussed in \cite{Der-Fradkov74,Ljung77b,Kushner-Clark78},
opens the possibility that the same approach can be used to prove
the convergence of the SA algorithm in more general settings, such as
two-time scale SA \cite{CL-SB-Auto17} or projected gradient SA
\cite{Tsi-Van-TAC97}.
These lines of research are currently under investigation.

In \cite{Ljung78}, a different class of stochastic algorithms is studied.
Specifically, the basic recursion is
\begin{equation}\label{eq:51}
{\boldsymbol \theta}_{t+1} = {\boldsymbol \theta}_t + \alpha_t ( {\bf f}({\boldsymbol \theta}_t) + {\boldsymbol \xi}_{t+1} + {\boldsymbol \eta}_{t+1} ) ,
\end{equation}
where the function ${\bf f}(\cdot)$ is a \textit{gradient vector field}, that is,
\begin{displaymath}
{\bf f}({\boldsymbol \theta}) = - \nabla J({\boldsymbol \theta})
\end{displaymath}
for some function $J : {\mathbb R}^d \rightarrow {\mathbb R}$ with compact level sets.
This means  that, for every constant $c \in {\mathbb R}$, the set
\begin{displaymath}
{\cal S}(c) := \{ {\boldsymbol \theta} \in {\mathbb R}^d : J({\boldsymbol \theta}) \leq c \}
\end{displaymath}
is compact.
In addition, there are now \textit{two} measurement noise sequences
$\{ {\boldsymbol \xi}_t \}$ and $\{ {\boldsymbol \eta}_t \}$.
The sequence $\{ {\boldsymbol \eta}_t \}$ converges to zero almost surely as $t \rightarrow \infty$,
while the sequence $\{ {\boldsymbol \xi}_t \}$ \textit{is not required to satisfy} the
conditional zero mean assumption \eqref{eq:26}.
There are other minor differences, but these are the main differences
between the set-up studied here and that studied in \cite{Ljung78}.
The convergence of the algorithm is established using what might be termed
as ``direct''  methods.
The two problem set-ups are not directly comparable.
In \cite{Ljung78}, the function ${\bf f}(\cdot)$ is restricted to be a gradient
vector field, whereas there is no such restriction here.
On the other hand, the conditional zero-mean assumption \eqref{eq:26}
is replaced by a more relaxed assumption.
It would be highly desirable to explore whether the results of
\cite{Ljung78} (or some broadly similar results) can be obtained via
martingale methods.

Finally, it might mentioned that the present work still does not
completely recover the results of \cite{Gladyshev65}, which applies to
any function ${\bf f}(\cdot)$ that satisfies \eqref{eq:40a} or \eqref{eq:40b}
as appropriate.
Consider for example a function $f: {\mathbb R} \rightarrow {\mathbb R}$ defined by
\begin{displaymath}
f(\theta) = \left\{ \begin{array}{ll} -\theta, & -1 \leq \theta \leq 0 , \\
-1, & \theta \leq -1 , \end{array} \right. 
\end{displaymath}
with $f(\theta) = -f(\theta)$ when $\theta \geq 0$.
Then $f(\cdot)$ satisfies \eqref{eq:40b}.
However, the equilibrium $\theta = 0$ is only globally \textit{asymptotically}
stable but not globally \textit{exponentially} stable.
Work is under way to extend the Lyapunov approach to cover this situation.

\section*{Acknowledgements}

The author thanks Prof.\ Rajeeva Karandikar for assistance in understanding
the contents of \cite{Gladyshev65}, Prof.\ Sean Meyn for the comment
following Theorem \ref{thm:21}, Prof.\ Boris Polyak for drawing his
attention to the reference \cite{Fran-Gram22}, and to  Prof.\ Barbara
Franci for providing a copy of the difficult to locate paper
\cite{Robb-Sieg71}.



