vskip=0pt

# Riemannian stochastic optimization methods
avoid strict saddle points

Ya-Ping Hsieh∗ ∗ ETH Zürich<EMAIL_ADDRESS>,  Mohammad Reza
Karimi∗<EMAIL_ADDRESS>,
Andreas Krause∗<EMAIL_ADDRESS>and  Panayotis Mertikopoulos♯ ♯ Univ. Grenoble
Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.
<EMAIL_ADDRESS>
###### Abstract.

Many modern machine learning applications – from online principal component
analysis to covariance matrix identification and dictionary learning – can be
formulated as minimization problems on Riemannian manifolds, typically solved
with a Riemannian stochastic gradient method (or some variant thereof).
However, in many cases of interest, the resulting minimization problem is
_not_ geodesically convex, so the convergence of the chosen solver to a
desirable solution - i.e., a local minimizer - is by no means guaranteed. In
this paper, we study precisely this question, that is, whether stochastic
Riemannian optimization algorithms are guaranteed to avoid saddle points with
probability $1$. For generality, we study a family of retraction-based methods
which, in addition to having a potentially much lower per-iteration cost
relative to Riemannian gradient descent, include other widely used algorithms,
such as natural policy gradient methods and mirror descent in ordinary convex
spaces. In this general setting, we show that, under mild assumptions for the
ambient manifold and the oracle providing gradient information, the policies
under study avoid strict saddle points / submanifolds with probability $1$,
from any initial condition. This result provides an important sanity check for
the use of gradient methods on manifolds as it shows that, almost always, the
limit state of a stochastic Riemannian algorithm can only be a local
minimizer.

###### Key words and phrases:

Optimization on manifolds; stochastic approximation; saddle-point avoidance;
Riemannian Robbins-Monro algorithms.

###### 2020 Mathematics Subject Classification:

Primary 62L20, 37N40; secondary 90C15, 90C48.

##  1\. Introduction

Modern machine learning systems have achieved remarkable success in the
efficient optimization of highly non-convex functions using straightforward
_Euclidean_ techniques like stochastic gradient descent. A widely accepted
hypothesis to explain this phenomenon is that, when the learning system under
study – e.g., a neural network – is sufficiently expressive, local minimizers
are essentially as good as global ones [21, 35]; by this token, a training
algorithm can attain satisfactory performance by simply evading _saddle
points_ of the model’s loss surface.

This observation has sparked a far-reaching research thread examining the
behavior of various algorithms around saddle points in non-convex functions.
Informally, these studies aim to tackle two fundamental questions:

  1. (Q1)

When does a given scheme, like stochastic gradient descent, avoid saddle
points?

  2. (Q2)

Can we _augment_ a given scheme so that it efficiently escapes saddle points?

Of the above questions, (Q1) focuses on _explaining_ the empirical success of
commonly used schemes, while the resolution of (Q2) usually revolves around
proposing new schemes with desirable escape guarantees. These complementary
perspectives have been extensively studied over the past decade, leading to a
fairly complete understanding of how and when a Euclidean (stochastic)
algorithm escapes saddle points, cf. [54, 41, 42, 53, 28, 46, 29, 6, 47] and
references therein.

In parallel to the above, the recent surge of interest in Riemannian
optimization has prompted a closer examination of _Riemannian_ methods,
thereby motivating an extension of (Q1) and (Q2) to a manifold setting –
itself due to a wide range of breakthrough applications to machine learning
and data science, from natural language processing, and signal processing to
dictionary learning and robotics [52, 48, 64, 65]. As a result, there is an
increasing demand for a comprehensive exploration of various spaces, such as
the $d$-dimensional torus, Grassmannian or Stiefel manifolds, hyperbolic
spaces, and many others.

Unfortunately, in a proper Riemannian setting, only (Q2) has received
sufficient scrutiny thus far. Recent works by Criscitiello & Boumal [22] and
Sun et al. [66] have shown that standard Riemannian deterministic algorithms
can be augmented via the injection of an infinitesimal amount of noise
(proportional to the method’s desired accuracy), to achieve comparable escape
guarantees in terms of oracle complexity as the corresponding Euclidean
methods [30]. To the best of our knowledge, all existing results for (Q1)
concern _deterministic_ methods [41, 42, 53, 28] which are significantly
limited in scope in large-scale machine learning applications because of their
prohibitively high per-iteration cost.

#### Our results and techniques.

In view of the above, our paper aims to provide a general answer to (Q1) for a
broad class of Riemannian stochastic optimization methods – including
Riemannian stochastic gradient descent, its retraction-based and/or optimistic
variants, etc. Concretely, we focus throughout on a flexible template of
Riemannian Robbins–Monro (RRM) schemes [59, 34] which, in addition to the
specific algorithms of interest mentioned above, also includes a range of
Euclidean methods that can be analyzed efficiently from a Riemannian
viewpoint.

Informally, our main result may be stated as follows:

> Under any stochastic Riemannian Robbins–Monro method, the probability of
> converging to a strict saddle point (or a submanifold thereof) is zero.

This statement provides firm grounds for accepting the output of a stochastic
Riemannian optimization method as valid, as it shows that saddle points are
avoided with probability $1$.111We recall here that a strict saddle manifold
is a set of critical points each of which has at least one negative Hessian
eigenvalue. Such manifolds include ridge hypersurfaces and other connected
sets of non-isolated saddle points that are common in the loss landscapes of
high-dimensional machine learning models, so this result has significant
cutting power in this regard. In the context of stochastic methods, our result
builds on a series of foundational results by Pemantle [54] and Brandière &
Duflo [20] who focused on _hyperbolic traps_ (isolated saddle points with
invertible Hessian). These results were subsequently extended by Benaïm &
Hirsch [12] to a more general class of unstable _sets_ , but this analysis
remained grounded in a flat, Euclidean setting. The connecting tissue of our
analysis with these works is the notion of an asymptotic pseudotrajectory
(APT), which allows us to couple the long-run behavior of discrete-time
Riemannian Robbins–Monro (RRM) methods to that of an associated Riemannian
gradient flow. [This discrete-to-continuous comparison is crucial for our
analysis in order to apply center stable manifold techniques [63] to the RRM
framework.] However, this comes at a significant cost, as establishing the APT
property in a Riemannian setting is quite challenging. To achieve this, we
employ a set of techniques recently developed by [33] which allow us to make
this comparison precise and establish the desired avoidance result.

##  2\. Background on Riemannian Manifolds

We begin with a brief overview of some basic definitions from Riemmanian
geometry and optimization, solely intended to set notation and terminology;
our presentation roughly follows the masterful account of Lee [43, 44], to
which we refer the reader for a comprehensive introduction to the topic.

Le $\mathcal{M}$ be a $d$-dimensional, geodesically complete Riemannian
manifold. Throughout the sequel, the tangent space to $\mathcal{M}$ at a point
$x\in\mathcal{M}$ will be denoted by $\mathcal{T}_{x}\mathcal{M}$, and we will
write $\dot{\gamma}(t)\in\mathcal{T}_{\gamma(t)}\mathcal{M}$ for the velocity
vector to a smooth curve $\gamma\colon\mathbb{R}\to\mathcal{M}$ at time
$t\in\mathbb{R}$. We will also write $\langle\cdot,\cdot\rangle_{x}$ for the
metric at $x\in\mathcal{M}$, $\lVert\cdot\rVert_{x}$ for the associated norm,
and $\operatorname{dist}(\cdot,\cdot)$ for the induced distance function on
$\mathcal{M}$, the latter being defined via the minimization of the length
functional
$\mathcal{L}[\gamma]=\int\lVert\dot{\gamma}(t)\rVert_{\gamma(t)}\>dt$.

Given a point $x\in\mathcal{M}$ and a tangent vector
$z\in\mathcal{T}_{x}\mathcal{M}$, the (necessarily unique) geodesic emanating
from $x$ along $z$ will be denoted by $\gamma_{z}$, and we define the
exponential map at $x$ as $\exp_{x}(z)=\gamma_{z}(1)$ for all
$z\in\mathcal{T}_{x}\mathcal{M}$ (recall here that $\mathcal{M}$ is assumed
complete, so this map is well-defined for all $x\in\mathcal{M}$ and all
$z\in\mathcal{T}_{x}\mathcal{M}$). Whenever well-defined, the inverse of
$\exp_{x}$ will be written as
$\log_{x}\colon\mathcal{M}\to\mathcal{T}_{x}\mathcal{M}$, with the
understanding that the domain of $\log_{x}$ is actually the largest
neighborhood of $x\in\mathcal{M}$ on which the restriction of $\exp_{x}$ is a
(global) diffeomorphism; by definition, we have $\log_{x}(\exp_{x}(z))=z$ for
all $z$ for which the relevant quantities are well-defined. Finally, given a
pair of points $x,x^{\prime}\in\mathcal{M}$ and a tangent vector
$z\in\mathcal{T}_{x}\mathcal{M}$, we will write $\Gamma_{#1\to#2}(z)$ for the
vector obtained by parallel transporting $z$ along any minimizing geodesic
connecting $x$ and $x^{\prime}$.

In this general context, we will be interested in solving the Riemannian
optimization problem

$\mathrm{minimize}_{x\in\mathcal{M}}f(x)$ (Opt)

for some smooth _objective function_ $f\colon\mathcal{M}\to\mathbb{R}$. We
will also respectively write

$v(x)\coloneqq-\mathrm{grad}f(x)\qquad\text{and}\qquad
H(x)\coloneqq\operatorname{Hess}(f(x))$ (1)

for the _negative(Riemannian) gradient_ and the _( Riemannian) Hessian_ of $f$
at $x$. Finally, in terms of solutions of (Opt), we will focus on the
avoidance of _strict saddle points_ of $f$, i.e., points
$\hat{x}\in\mathcal{M}$ for which

$v(\hat{x})=0\quad\text{and}\quad\lambda_{\min}(H(\hat{x}))<0$ (2)

where $\lambda_{\min}$ denotes the minimum eigenvalue of the tensor in
question. We will also say that a smooth compact component (in the sense of
manifolds) of critical points of $f$ is a _strict saddle manifold_ if there
exist constants $c_{\pm}>0$ such that all negative eigenvalues of
$H(\hat{x})$, $\hat{x}\in\mathcal{S}$, are bounded from above by $-c_{-}<0$,
and any positive eigenvalues (if they exist) are bounded from below by
$c_{+}>0$.

To differentiate the above from the Euclidean setting, when $\mathcal{M}$ is a
real space equipped with the Euclidean metric, we will instead write $\nabla
f$ and $\nabla^{2}f$ for the (ordinary) gradient and Hessian matrix of $f$. In
this case, as is customary, we will not distinguish between primal and dual
vectors.

##  3\. Core algorithmic framework

For generality, our avoidance analysis will be carried out in an abstract
stochastic approximation framework which includes several popular Riemannian
optimization algorithms – from ordinary Riemannian (stochastic) gradient
descent, to its retraction-based variants, optimistic methods, etc. For
concreteness, we start with the general template below, and we present a
(nonexhaustive!) series of representative examples right after.

###  3.1. The Riemannian Robbins–Monro template

The Riemannian Robbins–Monro (RRM) framework that we will consider for solving
(Opt) is an iterative family of methods which directly extends the seminal
stochastic approximation scheme of Robbins & Monro [59] to a manifold setting
by replacing vector addition with the Riemannian exponential. Roughly
following [33], we will focus on the abstract update rule

$X_{n+1}=\exp_{#1}(\gamma_{n}\hat{v}_{n})$ (RRM)

where

  1. (1)

$X_{n}\in\mathcal{M}$ denotes the state of the algorithm at each iteration
$n=1,2,\dotsc$

  2. (2)

$\hat{v}_{n}\in\mathcal{T}_{X_{n}}\mathcal{M}$ is a surrogate for the
(negative) gradient $v(X_{n})$ of $f$ at $X_{n}$ (defined in detail below).

  3. (3)

$\gamma_{n}>0$ is the method’s step-size (discussed in detail in Section 4).

In the above, the defining element of (RRM) is the sequence of “surrogate
gradients” $\hat{v}_{n}$, $n=1,2,\dotsc$, so this will be our first object of
interest. Formally, letting $\mathcal{F}_{n}$ denote the history of $X_{n}$ up
to stage $n$ (inclusive), we will write

$\hat{v}_{n}\coloneqq v(X_{n})+U_{n}+b_{n}$ (3)

where we have defined

$U_{n}\coloneqq\hat{v}_{n}-\operatorname{\mathbb{E}}[\hat{v}_{n}\nonscript\,|\nonscript\,\mathopen{}\mathcal{F}_{n}]\qquad\text{and}\qquad
b_{n}\coloneqq\operatorname{\mathbb{E}}[\hat{v}_{n}\nonscript\,|\nonscript\,\mathopen{}\mathcal{F}_{n}]-v(X_{n}),\qquad$
(4)

as the _random error_ and the _offset_ of $\hat{v}_{n}$ relative to $v(X_{n})$
respectively. It will also be convenient to introduce the _total error_
$W_{n}=\hat{v}_{n}-v(X_{n})=U_{n}+b_{n}$, which captures both random and
systematic fluctuations in $\hat{v}_{n}$, and which measures the total
deviation of $\hat{v}_{n}$ from $v(X_{n})$.

Two points are worth noting here: First, $\hat{v}_{n}$ is _not_ adapted to
$\mathcal{F}_{n}$, so $U_{n}$ is random relative to $\mathcal{F}_{n}$; on the
other hand, $b_{n}$ is $\mathcal{F}_{n}$-measurable, so it is deterministic
relative to $\mathcal{F}_{n}$. This brings us to the second important point
regarding $\hat{v}_{n}$: given the systematic offset term $b_{n}$ in
$\hat{v}_{n}$, the latter should _not be seen_ as the output of a gradient
oracle for $v(X_{n})$. In particular, $b_{n}$ is intended to capture possible
corrective terms, deviations from the exponential mapping, different
algorithmic update structures (such as optimism), etc. We make this
distinction precise below.

###  3.2. Specific algorithms and examples

In the series of examples that follow, we will assume that the optimizer can
access $f$ via a stochastic first-order oracle (SFO) returning noisy gradients
of $f$ at the evaluation point. Formally, following Nesterov [50], an
stochastic first-order oracle (SFO) is a black-box mechanism which, when
queried at $x\in\mathcal{M}$, returns a (negative) stochastic gradient of the
form

$V(x;\theta)=v(x)+\operatorname{err}(x;\theta)$ (SFO)

where the _seed_ $\theta\in\Theta$ is a random variable taking values in some
complete probability space $\Theta$, and $\operatorname{err}(x;\theta)$ is an
umbrella error term capturing all sources of uncertainty in the model.

The archetypal example of an SFO occurs when $f$ is itself a stochastic
expectation of the form $f(x)=\operatorname{\mathbb{E}}[F(x;\theta)]$ for some
random function $F\colon\mathcal{M}\times\Theta\to\mathbb{R}$ – the so-called
_stochastic optimization_ framework. In this case, $V$ is typically given by
$V(x;\theta)=-\mathrm{grad}_{x}F(x;\theta)$, so, under standard assumptions
for exchanging differentiation and expectation, we have
$\operatorname{\mathbb{E}}[V(x;\theta)]=v(x)$. Extrapolating from this basic
framework, our only assumption for the moment will be that
$\operatorname{\mathbb{E}}[\operatorname{err}(x;\theta)]=0$; for a detailed
discussion of the required assumptions for (SFO), see Section 4.

In practice, (SFO) will be queried repeatedly at a sequence of states $X_{n}$,
$n=1,2,\dotsc$, with a different random seed $\theta_{n}$ drawn i.i.d. from
$\Theta$. In this manner, we obtain the following specific algorithms as
special cases of (RRM):

######  Algorithm 1 (RSGD).

Following Bonnabel [17], the Riemannian stochastic gradient descent (RSGD)
algorithm queries (SFO) at $X_{n}$ and proceeds as

$X_{n+1}=\exp_{X_{n}}\left(\gamma_{n}V(X_{n};\theta_{n})\right).$ (RSGD)

As such, ( ‣ 1) can be seen as an RRM scheme with
$\hat{v}_{n}=V(X_{n};\theta_{n})$ or, equivalently,
$U_{n}=\operatorname{err}(X_{n};\theta_{n})$ and $b_{n}=0$. $\lozenge$

A key factor limiting the applicability of ( ‣ 1) is that the exponential map
$\exp_{#1}(\cdot)$ could be prohibitively expensive to compute in practice,
even for relatively low-dimensional manifolds. On that account, a popular
alternative to ( ‣ 1) is to employ a _retraction map_ [2, 19], that is, a
smooth mapping
$\operatorname{\mathcal{R}}\colon\mathcal{T}\mathcal{M}\to\mathcal{M}$ that
agrees with the exponential map up to first order, namely

$\operatorname{\mathcal{R}}_{#1}(0)=x\qquad\text{and}\qquad\left.\frac{d}{dt}\right|_{t=0}\operatorname{\mathcal{R}}_{#1}(tz)=z\quad\text{for
all $(x,z)\in\mathcal{T}\mathcal{M}$}.$ (Rtr)

With this machinery in hand, we obtain the following retraction-based variant
of ( ‣ 1):

######  Algorithm 2 (ReSGD).

By replacing the exponential map in ( ‣ 1) with a retraction, we obtain the
retraction-based stochastic gradient descent scheme

$X_{n+1}=\operatorname{\mathcal{R}}_{#1}(\gamma_{n}V(X_{n};\theta_{n})).$
(Rtr-SGD)

This algorithm does not seem immediately related to the RRM template – and,
indeed, the whole point of introducing a retraction was to get rid of the
exponential map in (RRM). The expressive power of (RRM) can be seen in the
fact that, despite this apparent disconnect, ( ‣ 2) can still be expressed as
a special case of (RRM) in a fairly straightforward fashion.

To do so, define the “forward-backward” gradient mapping

$\hat{v}_{n}\coloneqq\frac{1}{\gamma_{n}}\log_{#1}(\operatorname{\mathcal{R}}_{#1}(\gamma_{n}V(X_{n};\theta_{n})))$
(5)

with the proviso that the Riemannian logarithm in (5) is well-defined (we
discuss the conditions under which this holds later in the paper). Under this
definition, ( ‣ 2) can be recast as a special case of (RRM) by running the
latter with the surrogate gradient sequence $\hat{v}_{n}$ of Eq. 5. To
streamline our presentation, we defer the discussion about the inherent error
$W_{n}=\hat{v}_{n}-v(X_{n})$ to Appendix A. $\lozenge$

As we mentioned before, retraction-based algorithms typically exhibit
significantly lower per-iteration complexity compared to geodesic methods,
resulting in their remarkable success in practical machine learning
applications [2, 19]. In addition, as we show below, the use of a retraction
mapping allows us to provide a unified perspective for several classical
algorithms which, at first sight, might seem completely unrelated. An
important example is provided by the (stochastic) mirror descent (MD) family
of algorithms [49]:

######  Algorithm 3 (SMD).

Let $\mathcal{M}$ be an open convex subset of $\mathbb{R}^{M}$ and let
$h\colon\mathcal{M}\to\mathbb{R}$ be a $C^{2}$-smooth, strongly convex
_Legendre function_ on $\mathcal{M}$, that is, $\lVert\nabla
h(x)\rVert\to\infty$ whenever $x\to\operatorname{bd}(\mathcal{M})$ [cf. 60,
Chap. 26]. Then, the stochastic mirror descent (SMD) algorithm unfolds as

$X_{n+1}=\mathcal{P}_{#1}(\gamma_{n}V(X_{n};\theta_{n}))$ (SMD)

where $V(X_{n};\theta_{n})$ is the output of an SFO query for $\nabla
f(X_{n})$ at $X_{n}$, and
$\mathcal{P}\colon\mathcal{M}\times\mathbb{R}^{M}\to\mathcal{M}$ is the so-
called _prox-mapping_ associated to $h$ [9, 31, 8, 7], viz.

$\mathcal{P}_{#1}(y)=\operatorname*{arg\,max}\nolimits_{x^{\prime}\in\mathcal{M}}\\{\langle\nabla
h(x)+y,x^{\prime}\rangle-h(x^{\prime})\\}\qquad\text{for all
$x\in\mathcal{M}$, $y\in\mathbb{R}^{M}$}.$ (6)

where $\langle\cdot,\cdot\rangle$ stands for the ordinary Euclidean inner
product in $\mathbb{R}^{M}$.

Now, even though the notation in ( ‣ 3) is reminiscent of ( ‣ 2), the
definition (6) of $\mathcal{P}$ does not bear any resemblance to a geodesic
exponential or a retraction – and, indeed, its origins are starkly different.
However, as we show below, $\mathcal{P}$ can indeed be seen as a retraction
relative to a specific Riemannian structure on $\mathcal{M}$, the Hessian
Riemannian (HR) metric associated to $h$ [24, 3, 45, 16].

To make this precise, the first step is to note that the basic recursive
structure $x^{+}=\mathcal{P}_{#1}(y)$ of ( ‣ 3) can be rewritten as

$x^{+}=\mathcal{P}_{#1}(y)=\nabla h^{\ast}(\nabla h(x)+y)$ (7)

where $h^{\ast}(y)=\max_{x\in\mathcal{M}}\\{\langle y,x\rangle-h(x)\\}$
denotes the convex conjugate of $h$, and we have used Danskin’s theorem [62]
to write $\operatorname*{arg\,max}_{x\in\mathcal{M}}\\{\langle
y,x\rangle-h(x)\\}=\nabla h^{\ast}(y)$. Then, if we endow $\mathcal{M}$ with
the Hessian Riemannian metric $g(x)=\nabla^{2}h(x)$, the Riemannian gradient
of $f$ relative to $g$ becomes $\mathrm{grad}f(x)=[\nabla^{2}h(x)]^{-1}\nabla
f(x)$; more generally, given a cotangent (dual) vector $y$ to $\mathcal{M}$ at
$x$, the corresponding tangent (primal) vector will be
$z=g(x)^{-1}y=[\nabla^{2}h(x)]^{-1}y$. In view of this, by inverting the
relation $z=g(x)^{-1}y$, the abstract mirror descent recursion (7) can be
rewritten as

$x^{+}=\operatorname{\mathcal{R}}_{#1}(z)\coloneqq\mathcal{P}_{#1}(g(x)z).$
(8)

Now, to proceed, consider the curve

$\gamma(t)=\operatorname{\mathcal{R}}_{#1}(tz)=\mathcal{P}_{#1}(tg(x)z)=\nabla
h^{\ast}(\nabla h(x)+tg(x)z),$ (9)

so, by definition, $\gamma(0)=x$. In addition, by a direct differentiation, we
readily obtain

$\dot{\gamma}(0)=\nabla^{2}h^{\ast}(\nabla h(x))g(x)z=z$ (10)

where we used the standard identity $\nabla^{2}h^{\ast}(\nabla
h(x))=[\nabla^{2}h(x)]^{-1}$ [9, 61]. This shows that the map
$\operatorname{\mathcal{R}}_{#1}(z)=\mathcal{P}_{#1}(g(x)z)$ is, in fact, a
_retraction_ , so ( ‣ 3) is a special case of ( ‣ 2) – and hence, of the
general stochastic approximation template (RRM). $\lozenge$

######  Remark.

Even though elements of the above ideas are implicit in previous works on
mirror descent and Hessian Riemannian metrics [3, 58, 16, 5, 68], to the best
of our knowledge, this is the first time that ( ‣ 3) is formalized as a
retraction-based (Hessian) Riemannian scheme. $\lozenge$

######  Algorithm 4 (ROG).

Moving forward, an important algorithm for solving online optimization
problems and games is the so-called optimistic gradient method – originally
pioneered by Popov [56] and subsequently popularized by Rakhlin & Sridharan
[57]. In the Euclidean case, this method introduces an interim, “optimistic”
correction to gradient dynamics and updates as

$\displaystyle X_{n}^{+}$
$\displaystyle=X_{n}+\gamma_{n}V(X_{n-1}^{+};\theta_{n-1})$ (OG)
$\displaystyle X_{n+1}$
$\displaystyle=X_{n}+\gamma_{n}V(X_{n}^{+};\theta_{n})$

where, as usual, $V$ is an SFO for the (negative) gradient $\nabla f$ of $f$.
This idea can then be directly transported to a manifold setting [33], leading
to the Riemannian optimistic gradient method

$\displaystyle X_{n}^{+}$
$\displaystyle=\exp_{#1}(\gamma_{n}V(X_{n-1}^{+};{\theta_{n-1}})),$ (ROG)
$\displaystyle X_{n+1}$
$\displaystyle=\exp_{#1}(\Gamma_{#1\to#2}(\gamma_{n}V(X_{n}^{+};\theta_{n}))).$

Importantly, the recursion (ROG) may be seen as a special case of (RRM) by
setting
$\hat{v}_{n}=(1/\gamma_{n})\cdot\Gamma_{#1\to#2}(\gamma_{n}V(X_{n}^{+};\theta_{n}))$
or, equivalently
$U_{n}=\Gamma_{#1\to#2}(\operatorname{err}(X_{n}^{+};\theta_{n}))$ and
$b_{n}=\Gamma_{#1\to#2}(v(X_{n}^{+}))-v(X_{n})$. We defer the calculation
details to Appendix A. $\lozenge$

######  Algorithm 5 (NGD).

Our last example concerns the influential natural gradient descent (NGD)
method of Amari [4], a stochastic optimization scheme for Euclidean spaces,
but adapted to the local geometry defined by a strictly convex function $h$.
Specifically, natural gradient descent (NGD) queries an SFO and proceeds as

$X_{n+1}=X_{n}-\gamma_{n}(\mathrm{grad}f(X_{n})+\operatorname{err}(X_{n};\theta_{n}))$
(NGD)

where $\mathrm{grad}f(x)\coloneqq[\nabla^{2}h(x)]^{-1}\nabla f(x)$ denotes the
Riemannian gradient of $f$ relative to Hessian Riemannian metric $g(x)=\nabla
h^{2}(x)$ on $\mathbb{R}^{M}$. It is well known that (NGD) can be seen as a
retraction-based Riemannian scheme [17], and may thus be integrated directly
within the framework of (RRM); we defer the details to Appendix A.
Importantly, (NGD) also includes the celebrated natural policy gradient [32]
which plays an important role in reinforcement learning. $\lozenge$

The above examples have been chosen to illustrate a range of different update
mechanisms that can be integrated within the general algorithmic template
provided by (RRM). Of course, it is not possible to be exhaustive but, for
illustration purposes, we provide some more examples in Appendix A.

##  4\. Analysis and results

We are now in a position to state and discuss our main result concerning the
avoidance of saddle points under (RRM). For concreteness, we begin by
discussing the technical assumptions that we will need in Section 4.1;
subsequently, we proceed with the formal statement of our result and some
direct applications thereof in Section 4.2.

###  4.1. Technical assumptions

Our technical assumptions concern the four main ingredients of (RRM), namely
(it n) the regularity of $f$;  (it n) the method’s step-size sequence
$\gamma_{n}$;  (it n) the statistics of the surrogate gradients $\hat{v}_{n}$
entering (RRM); and  (it n) the ambient manifold $\mathcal{M}$.  Specifically,
we will require the following:

######  Assumption 1 (Regularity of $f$).

The function $f$ is $C^{2}$ and $v=-\mathrm{grad}f$ is (geodesically) _$L$
-Lipschitz_, i.e., for all $x,x^{\prime}\in\mathcal{M}$, we have

$\lVert\Gamma_{#1\to#2}(v(x))-v(x^{\prime})\rVert_{x^{\prime}}=\lVert
v(x)-\Gamma_{#1\to#2}(v(x^{\prime}))\rVert_{x}\leq
L\operatorname{dist}(x,x^{\prime}).$ (11)

######  Assumption 2 (Step-size schedule).

The step-size sequence $\gamma_{n}$ of (RRM) satisfies

$\sum\nolimits_{n=1}^{\infty}\gamma_{n}=\infty\quad\text{and}\quad\sum\nolimits_{n=1}^{\infty}\lambda^{1/\gamma_{n}}<\infty\quad\text{for
all $\lambda\in(0,1)$}.$ (12)

######  Assumption 3 (Surrogate gradients).

The offset and random error components of $\hat{v}_{n}$ satisfy

$\lVert b_{n}\rVert_{\scriptscriptstyle X_{n}}\leq C\gamma_{n},\qquad\lVert
U_{n}\rVert_{\scriptscriptstyle
X_{n}}\leq\sigma,\qquad\operatorname{\mathbb{E}}[[\langle
U_{n},z\rangle_{\scriptscriptstyle
X_{n}}]_{+}\nonscript\,|\nonscript\,\mathopen{}\mathcal{F}_{n}]\geq\zeta$ (13)

for suitable constants $C,\sigma,\zeta>0$ and for all
$z\in\mathcal{T}_{X_{n}}\mathcal{M}$, $\lVert z\rVert_{X_{n}}=1$ (in the
above, all conditions are to be interpreted in the almost sure sense and
$[t]_{+}=\max\\{0,z\\}$ denotes the positive part of $t$).

######  Assumption 4 (Injectivity radius).

The injectivity radius of $\mathcal{M}$ is bounded from below by $\varrho>0$.

Before proceeding, we discuss the implications and range of validity of each
of the above assumptions. Since Assumption 1 is standard, we focus on the
remaining three below:

#### On Assumption 2.

The step-size conditions typically encountered in the analysis of
Robbins–Monro schemes is the $L^{2}-L^{1}$ (“ _square-summabe-but-not-
summable_ ”) condition $\sum_{n}\gamma_{n}=\infty$,
$\sum_{n}\gamma_{n}^{2}<\infty$, cf. [59, 39, 13, 10, 14, 17] and references
therein. This puts a hard threshold on the range of allowed step-size
schedules at $\Omega(1/n^{1/2})$: any step-size that decays at least as slow
as $1/n^{1/2}$ cannot be used under the $L^{2}-L^{1}$ assumption. By contrast,
the step-size condition (12) is considerably more lax and can tolerate near-
constant step-sizes of the form $\gamma_{n}\propto 1/(\log n)^{1+\varepsilon}$
for some $\varepsilon>0$. This is enough to cover all dereasing step-size
policies used in practice. [We also recall here that, in stochastic non-convex
settings, trajectory convergence cannot be guaranteed in general without a
vanishing step-size, cf. [40, 10, 18] and references therein.]

#### On Assumption 3.

Three remarks are in order for the noise and offset requirements (13). First,
we should note that the condition
$b_{n}=\operatorname{\mathcal{O}}(\gamma_{n})$ is, a priori, _implicit_ ,
because it depends on the statistics of the feedback sequence $\hat{v}_{n}$,
and these may be difficult to estimate in general. However, in most practical
applications, this quantity is under the _explicit_ control of the optimizer:
in particular, as we show later in this section, this requirement is satisfied
by all the specific algorithms of Section 3.2.

Likewise, the bounded noise requirement is satisfied in many practical cases
of interest. For example, when the problem’s objective function admits a
finite-sum decomposition of the form $f(x)=\sum_{i=1}^{N}f_{i}(x)$ for an
ensemble of empirical instances $f_{i}$, $i=1,\dotsc,N$ (the standard
framework for applications to data science and machine learning), $U_{n}$ is
typically generated by sampling a minibatch of $f$, which in turn results in
an error term of the form $U_{n}=q(X_{n})$ where
$q(x):\mathcal{M}\to\mathcal{T}_{x}\mathcal{M}$ is bounded on all compact
subsets of $\mathcal{M}$. Therefore, $\lVert U_{n}\rVert_{\scriptscriptstyle
X_{n}}\leq\lVert q(X_{n})\rVert_{\scriptscriptstyle X_{n}}<\sigma$ for some
constant $\sigma$ for any convergent algorithm $\\{X_{n}\\}_{n}$.

Finally, the “uniform excitability” condition
$\operatorname{\mathbb{E}}[[\langle U_{n},z\rangle_{\scriptscriptstyle
X_{n}}]_{+}\nonscript\,|\nonscript\,\mathopen{}\mathcal{F}_{n}]\geq\zeta$ is
also standard in the avoidance literature [54, 10], and it is substantially
weaker than the _isotropic_ condition, which, roughly speaking, requires the
noise to have the same $L^{2}$ magnitude along all directions in space [54,
26, 30]. Instead, (13) only posits that the noise $U_{n}$ has a _non-zero_
component along each direction, and imposes no other restrictions on the
statistical profile of the noise.

#### On Assumption 4.

For our last assumption, recall first that the injectivity radius of
$\mathcal{M}$ at a point $x\in\mathcal{M}$ is the largest radius for which
$\exp_{x}$ is a diffeomorphism onto its image; the injectivity radius of
$\mathcal{M}$ is then taken to be the infimum over all such radii [43]. In
this regard, Assumption 4 simply serves to ensure that the exponential map is
invertible at consecutive iterates of (RRM) so no local topological
complications can arise. This assumption is automatically satisfied in closed
manifolds (independent of curvature), as well as in non-positively curved
manifolds – such as Cartan-Hadamard spaces and the like [43, 44]. This
assumption (and its variants) is also standard in the literature, cf. [17, 34,
66] and references therein.

###  4.2. Avoidance of saddle points

We are now in a position to state our main avoidance result:

######  Theorem 1.

Let $X_{n}$, $n=1,2,\dotsc$, be the sequence of states generated by (RRM), and
let $\mathcal{S}$ be a strict saddle manifold of $f$. Then, under Assumptions
1, 2, 3 and 4, we have

$\operatorname{\mathbb{P}}(\text{$\operatorname{dist}(\mathcal{S},X_{n})\to 0$
as $n\to\infty$})=0$ (14)

where
$\operatorname{dist}(\mathcal{S},X_{n})=\inf_{x\in\mathcal{S}}\operatorname{dist}(x,X_{n})$
denotes the (Riemannian) distance of $X_{n}$ from $\mathcal{S}$.

Before discussing the proof of Theorem 1, it is worthwhile to compare our work
with its closest antecedents. First, in regard to the general avoidance theory
in Euclidean spaces [12, 10], the statement is similar in scope (avoidance of
unstable manifolds with probability $1$), but the techniques and challenges
involved are very different. The reason for this is simple: the additive,
vector space structure of $\mathbb{R}^{m}$ is ingrained at every step of the
way in the Euclidean analysis of [10], and adapting the various constructions
to a manifold setting can be a complicated affair. For an illustration of the
technical difficulties involved, see the recent stochastic approximation
analysis of [33].

By contrast, the recent results of [22, 66] paint a complementary picture:
they concern Riemannian problems but, at their core, they are deterministic
results. More precisely, the noise in [22, 66] is actually _injected_ in an
otherwise deterministic gradient scheme to facilitate the escape from flat
regions in the vicinity of a saddle point; other than that, the magnitude of
the noise must be proportional to the solver’s desired accuracy, and hence is
typically extremely small. As a result, the analysis of [22, 66] cannot be
extended to bona fide stochastic schemes – like ( ‣ 1) – which also explains
why these results involve a constant step-size (as opposed to a decreasing
step-size schedule, which is required to guarantee trajectory convergence in
settings with persistent noise). In this regard, Theorem 1 simultaneously
complements the stochastic analysis of [10, 12] to Riemannian problems, and
the Riemannian analysis of [22, 66] to a stochastic setting.

#### Proof outline.

To facilitate the reading of our proof, we provide below a detailed outline of
the main steps and techniques involved therein, deferring the full proof to
Appendix B. We begin with a high-level description of our proof strategy and
then encode the main arguments in a series of steps right after.

For the purposes of illustration, suppose that $\mathcal{M}$ is a subset of
$\mathbb{R}^{m}$. Then, given a tangent vector
$z\in\mathcal{T}_{x}\mathcal{M}$, we define the _geodesic offset_ (see Fig. 1)
from $x$ along $z$ as

$\Delta(x;z)=\exp_{#1}(z)-x-z$ (15)

i.e., as the difference between the geodesic emanating from $x$ along $z$ and
its first-order approximation relative to $x$ in the ambient space
$\mathbb{R}^{m}$ (with all differences expressed in the ordinary vector space
structure of $\mathbb{R}^{m}$). The offset $\Delta(x;z)$ is readily checked to
be second-order in $z$ so, while the curve $x+tz$ does not in general induce a
retraction on the target manifold $\mathcal{M}$ (in particular, the point
$x+tz$ may not even _belong_ to $\mathcal{M}$), the converse _is_ true: the
map $\exp_{#1}(z)$ is always a retraction on the ambient, Euclidean space
$\mathbb{R}^{m}$. In this way, the basic iteration (RRM) can be expressed as

$X_{n+1}=\exp_{#1}(\gamma_{n}\hat{v}_{n})=X_{n}+\gamma_{n}\hat{v}_{n}+\Delta(X_{n};\gamma_{n}\hat{v}_{n})$
(16)

leading to the fundamental question below:

> What is the maximum offset
> $\epsilon_{n}\coloneqq\Delta(X_{n};\gamma_{n}\hat{v}_{n})$ that can be
> tolerated by a Euclidean stochastic approximation algorithm to avoid saddle
> points?

A key technical step in our work is to develop the means to control the offset
term $\epsilon_{n}$ under (RRM) under a sufficiently broad class of
assumptions that includes Algorithms 1–5. Crucially, this step is made
possible thanks to the very recent – and technical – stochastic approximation
work of [33]. To help the reader navigate our proof strategy, we outline the
main steps below, focusing for simplicity on the case of a single saddle
point.

#### Step 1: From discrete to continuous time (and back).

Let $\hat{x}$ be a strict saddle point of $f$. By the stable manifold theorem
[63], the set of all initializations such that the Riemannian gradient flow

$\dot{x}(t)=-\mathrm{grad}f(x(t))$ (RGF)

converges to $\hat{x}$ is of measure 0. Then, assuming for the moment that the
geodesic offset error $\epsilon_{n}=\Delta(X_{n};\gamma_{n}\hat{v}_{n})$ in
(16) is sufficiently small, the iterates of (RRM) can be seen as a noisy,
approximate Euler discretization of (RGF); as such, it is reasonable to expect
that the induced trajectories of (RRM) will never converge to $\hat{x}$.

To make this intuition precise, our first step will be to show that the
iterates of (RRM) comprise an asymptotic pseudotrajectory of (RGF) in the
sense of Benaïm [10], i.e., they asymptotically track the orbits of (RGF) with
arbitrary precision over windows of arbitrary length. To formalize this,
define the “effective time” variable
$\tau_{n}=\sum\nolimits_{k=1}^{n-1}\gamma_{k}$ and the associated _geodesic
interpolation_ $X(t)$ of $X_{n}$ as

$X(t)=\exp_{#1}\left((t-\tau_{n})\hat{v}_{n}\right)\quad\text{for all
$t\in[\tau_{n},\tau_{n+1})$, $n\geq 1$}$ (GI)

so, by construction,  (itn) $X(\tau_{n})=X_{n}$for all $n$; and  (itn) each
segment of $X(t)$ is a geodesic.  Then, letting
$\Phi\colon\mathbb{R}_{+}\times\mathcal{M}\to\mathcal{M}$ denote the _flow_ of
(RGF) – i.e., $\Phi_{h}(x)$ is simply the position at time $h\geq 0$ of the
solution orbit of (RGF) that starts at $x\in\mathcal{M}$ – we will say that
$X(t)$ is an APT of (RGF) if, for all $T>0$, we have

$\textstyle\lim_{t\to\infty}\sup_{0\leq h\leq
T}\operatorname{dist}(X(t+h),\Phi_{h}(X(t)))=0.$ (APT)

This requirement is non-trivial, and our first technical result is to
guarantee precisely this:

######  Theorem 2.

Suppose that Assumptions 2–4 hold. Then, with probability $1$, the geodesic
interpolation $X(t)$ of the sequence of iterates $X_{n}$, $n=1,2,\dotsc$,
generated by (RRM) is an APT of (RGF).

A version of Theorem 2 was very recently derived by [33] under a different set
of assumptions: On the one hand, [33] imposes a much more restrictive step-
size schedule for $\gamma_{n}$ (square summability) but, on the other hand, it
only posits that the noise increments $U_{n}$ are bounded in $L^{2}$ (as
opposed to $L^{\infty}$ in our case). Our proof relies on the same
construction of the Picard iteration map as [33], but otherwise diverges
significantly in the probabilistic analysis required to establish (APT).

#### Step 2: From Riemannian to Euclidean schemes (and back).

Albeit crucial, the APT property is decidedly not enough to guarantee
avoidance: after all, the constant orbit $X(t)=\hat{x}$ for all $t\geq 0$ is
trivially an APT of (RGF) but, of course, it does not avoid $\hat{x}$. To
proceed, we will need to exploit the precise update structure of (RRM) in
conjunction with the stable manifold theorem applied to (RGF).

In the Euclidean case, this is achieved by means of an intricate Lyapunov
function argument, originally due to [11]. Our second step is to devise a new
geometric argument to reduce the analysis from an arbitrary _intrinsic_
manifold to an isometrically embedded submanifold of $\mathbb{R}^{m}$. This
step is carried out by a combination of the celebrated Nash embedding theorem
and a (smooth) Tietze extension argument to rewrite (RRM) as a “corrected”
Robbins–Monro scheme on $\mathbb{R}^{m}$ that actually evolves on
$\mathcal{M}$. This construction also requires a “perturbation analysis” to
ensure that certain subtle topological issues do not arise when we invoke the
stable manifold theorem; we present the details in Appendix B.

#### Step 3: Controlling the geodesic offset.

As we briefly described in the beginning of the proof overview, this Euclidean
reframing of (RRM) introduces an intrinsic offset error
$\epsilon_{n}=\Delta(X_{n};\gamma_{n}\hat{v}_{n})$, which is difficult to
analyze in detail (the offset incurred by a retraction on $\mathcal{M}$ is of
similar order, so the exponential-retraction distinction is not important at
this stage). Our crucial observation here is that, under our blanket
assumptions, $\epsilon_{n}$ is small relative to $\gamma_{n}$ and, in
particular, $\epsilon_{n}=\operatorname{\mathcal{O}}(\gamma_{n}^{2})$. Thanks
to this bound, we are able to leverage a series of stochastic bounds –
originally developed by Pemantle [54] – to show that the probability that
these terms will have an adverse effect on exiting the center manifold of
$\hat{x}$ is zero (this is also where Assumption 3 comes in). We formalize
this in Appendix B; Theorem 1 then follows by putting everything together.

$\Delta(x;z)$
---
$x$
---
$x+z$
---
$z$
---
$x^{+}=\exp_{x}(z)$
---
$\hat{x}$
---
$\mathcal{M}$
---
$\mathcal{T}_{x}\mathcal{M}$
---
Figure 1. The geodesic offset $\Delta(x;z)$.

######  Remark.

A concept similar to our geodesic offset $\Delta(x;z)$ has been explored in
the _reverse direction_ by the very recent works [23, 15] whose goal was to
study of avoidance of _Euclidean_ subgradient methods as an inexact Riemannian
gradient scheme. They further show that this inexact Riemannian gradient
descent can avoid saddle points if uniform noise is injected. While their core
idea bears some similarity to ours, it remains unclear how to apply the
analysis in [23, 15] to handle general RRM schemes, such as retraction-based
and natural policy gradient methods.

###  4.3. Applications

As an illustration of the generality of Theorem 1, we now instantiate it to
the range of specific algorithms discussed in Section 3.2. Since all these
algorithms are run with gradient input generated by (SFO), applying Theorem 1
would require mapping the requirements of Assumption 3 to the primitives of
(SFO). A convenient way to achieve this is by means of the proposition below:

######  Proposition 1.

Suppose that Algorithms 1–5 are run with a gradient oracle
$V(x;\theta)=v(x)+\operatorname{err}(x;\theta)$ such that

$\lVert\operatorname{err}(x;\theta)\rVert_{x}\leq\sigma(x)\quad\text{and}\quad\operatorname{\mathbb{E}}[[\langle\operatorname{err}(x;\theta),z\rangle_{x}]_{+}]\geq\zeta(x)$
(17)

for all $z\in\mathcal{T}_{x}\mathcal{M}$, $\lVert z\rVert_{x}=1$, and for
suitable functions $\zeta,\sigma\colon\mathcal{M}\to\mathbb{R}_{+}$ with
$\sigma$ bounded on bounded subsets of $\mathcal{M}$ and $\inf_{x}\zeta(x)>0$.
Then, under Assumptions 2 and 4, the conclusion of Theorem 1 holds, that is,
Algorithms 1–5 avoid strict saddle manifolds of $f$.

The proof of Proposition 1 is deferred to Appendix B; we only note here that
its proof mainly hinges on verifying the bias requirement $\lVert
b_{n}\rVert_{X_{n}}=\operatorname{\mathcal{O}}(\gamma_{n})$ of (13) by means
of  (it n) the boundedness of the error function $\sigma(x)$ on bounded
subsets of $\mathcal{M}$; and  (it n) controlling the maximal deviation
between a retraction and the exponential map for input vectors bounded by
$\varrho$.

##  5\. Numerical Illustrations

(a) Riemannian stochastic gradient descent

(b) Riemannian stochastic extra-gradient

Figure 2. Avoidance of saddle points by stochastic RRM schemes on the torus.

In this section, we aim to demonstrate the practical applicability of the
theoretical framework proposed in our paper by providing numerical
illustrations. To do so, we utilize a 2-dimensional torus as the optimization
landscape, where the complexity and multi-modal nature of the objective
function can be easily visualized in Fig. 2.

Our objective function features three saddle points (in black) and one global
minimizer (in red). We subject two RRM schemes, i.e., ( ‣ 1) and (RSEG), to
initialization in proximity to these saddle points. This strategic choice
rigorously tests their ability to navigate and converge to the global optimum.
In line with our theoretical predictions, both RRM methods avoid the saddle
points and eventually reach the desirable global minimum. This empirical
confirmation reinforces the central message of our paper: stochastic
Riemannian schemes only converge to local minimizers.

##  6\. Conclusions and future work

In this paper, we addressed the question of when Riemannian stochastic
algorithms can effectively evade saddle points, focusing on the broad category
of Riemannian Robbins–Monro schemes. We introduced a novel framework for
analyzing the avoidance of Riemannian saddle points within the RRM framework,
which encompasses many commonly used Riemannian stochastic algorithms,
including retraction-based algorithms. Our framework builds upon the notion of
strict saddle points and provides a set of easily verifiable conditions that
guarantee the avoidance of such traps.

Our work paves the way for several promising research directions in learning
with Riemannian methods. One intriguing avenue for exploration is the
investigation of whether Riemannian _zeroth-order_ methods, such as the
Riemannian extension of the work by Kiefer & Wolfowitz [36], can effectively
evade strict saddle points. We believe that combining the insights from the
asymptotic pseudotrajectory theory with Euclidean analysis can shed light on
this question and provide valuable insights into the behavior of these methods
in the Riemannian setting.

Furthermore, an interesting direction for future research is the extension of
the avoidance of _unstable limit cycles_ in Euclidean min-max optimization, as
studied by Hsieh et al. [29], to the realm of Riemannian games. Investigating
the avoidance of unstable limit cycles in this context has the potential to
uncover novel phenomena specific to the manifold settings, leading to a deeper
understanding on the intricate dynamics and strategies involved in Riemannian
games.

## Acknowledgments

This work has been partially supported by the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation program grant
agreement No 815943, the French National Research Agency (ANR) in the
framework of the “Investissements d’avenir” program (ANR-15-IDEX-02), the
LabEx PERSYVAL (ANR-11-LABX-0025-01), and MIAI@Grenoble Alpes
(ANR-19-P3IA-0003), and project MIS 5154714 of the National Recovery and
Resilience Plan Greece 2.0 funded by the European Union under the
NextGenerationEU Program. PM is also with the Archimedes Research Unit, Athena
RC, Department of Mathematics, National & Kapodistrian University of Athens.
YPH acknowledges funding through an ETH Foundations of Data Science (ETH-FDS)
postdoctoral fellowship.

##  Appendix A Further examples of RRM schemes

In this section, we provide two additional algorithmic examples supplementing
the range of Algorithms 1–5 to illustrate the applicability of our RRM
template.

######  Algorithm 6 (RPPM).

The (deterministic) Riemannian proximal point method (RPPM) [25] is an
implicit (“backward”) update rule of the form

$\log_{X_{n+1}}(X_{n})=-\gamma_{n}v(X_{n+1}).$ (RPPM)

The RRM representation of (RPPM) is then obtained by taking
$b_{n}=\Gamma_{#1\to#2}(v(X_{n+1}))-v(X_{n})$ and $U_{n}=0$ in the
decomposition (4) of the error term $W_{n}$ of (RRM). If, in additional, the
true gradient $v(X_{n+1})$ is replaced by an oracle $V(X_{n+1};\theta_{n+1})$,
then (RPPM) becomes the stochastic version of Riemannian proximal point method
(RPPM) by setting

$b_{n}=\operatorname{\mathbb{E}}[\Gamma_{#1\to#2}(V(X_{n+1};\theta_{n+1}))-v(X_{n})\nonscript\,|\nonscript\,\mathopen{}\mathcal{F}_{n}]$

and

$U_{n}=\Gamma_{#1\to#2}(V(X_{n+1};\theta_{n+1}))-v(X_{n})-b_{n}.$

For a detailed discussion, see [25] and references therein. $\lozenge$

######  Algorithm 7 (RSEG).

Inspired by the original work of Korpelevich [38], the Riemannian stochastic
extra-gradient (RSEG) method [67, 51] proceeds as

$\displaystyle X_{n}^{+}$
$\displaystyle=\exp_{#1}(\gamma_{n}V(X_{n};\theta_{n})),$ (RSEG)
$\displaystyle X_{n+1}$
$\displaystyle=\exp_{#1}(\Gamma_{#1\to#2}(\gamma_{n}V(X_{n}^{+};\theta_{n}^{+})))$

where $\theta_{n}$ and $\theta_{n}^{+}$ are independent seeds for (SFO). Thus,
to cast (RSEG) in the RRM framework, it suffices to take
$U_{n}=\Gamma_{#1\to#2}(\operatorname{err}(X_{n}^{+};\theta_{n}^{+}))$ and
$b_{n}=\Gamma_{#1\to#2}(v(X_{n}^{+}))-v(X_{n})$. $\lozenge$

Under the assumptions in Proposition 1, one can show that Algorithms 6–7 also
avoid strict saddle points of $f$; we provide the relevant details in Section
B.3.

##  Appendix B Missing proofs from Section 4

###  B.1. Proof of Theorem 2

We begin by proving Theorem 2, which will play a crucial role in our proof of
Theorem 1. For the reader’s convenience, we restate the result below:

See 2

###### Proof.

To begin, let $\\{e_{i}(n)\\}_{i=1}^{d}$ be an arbitrary sequence of
orthonormal bases for $\mathcal{T}_{X_{n}}\mathcal{M}$, and let
$U_{n}^{\shortparallel}$ be the (Euclidean) noise vector composed of
components of the noise $U_{n}$ in the basis $\\{e_{i}(n)\\}_{i=1\dotsc d}$,
viz.

$U_{i,n}^{\shortparallel}\coloneqq\langle U_{n},e_{i}(n)\rangle_{X_{n}}.$
(B.1)

It is then easy to see that
$\operatorname{\mathbb{E}}[U_{n}^{\shortparallel}|\mathcal{F}_{n}]=0$, and,
moreover

$\left\lVert U_{n}^{\shortparallel}\right\rVert=\lVert
U_{n}\rVert_{X_{n}}\leq\sigma$ (B.2)

by Assumption 3. Then, following Benaïm [10], consider the “continuous-to-
discrete” counter

$M(t)=\sup\\{n\geq 1:t\geq\tau_{n}\\}$ (B.3)

which measures the number of iterations required for the effective time
$\tau_{n}=\sum_{k=1}^{n-1}\gamma_{k}$ to reach a given timestamp $t\geq 0$. We
further denote the piecewise-constant interpolation of the noise sequence as

$\bar{U}^{\shortparallel}(t)=U_{n}^{\shortparallel}\quad\text{for all
$t\in[\tau_{n},\tau_{n+1})$, $n\geq 1$}$ (B.4)

and we let

$\Delta(t;T)\coloneqq\sup_{0\leq h\leq
T}\left\lVert\int_{t}^{t+h}\bar{U}^{\shortparallel}(s)\>ds\right\rVert.$ (B.5)

Moving forward, since $X_{n}\to\mathcal{S}$ by assumption, we will also have

$\sup\nolimits_{n}\operatorname{dist}(X_{n},x)\eqqcolon R<\infty\quad\text{for
all $x\in\mathcal{S}$}$ (B.6)

for some (possibly random) $R\geq 0$. Moreover, since $f$ is assumed to be
$C^{2}$, (B.6) implies that

$\sup\nolimits_{n}\lVert v(X_{n})\rVert_{\scriptscriptstyle X_{n}}\eqqcolon
G<\infty$ (B.7)

for some (possibly random) non-negative constant $G\geq 0$. Moreover, since
the manifold $\mathcal{M}$ is assumed to be smooth, the sectional curvatures
at each $X_{n}$, $n=1,2,\dotsc$, must be likewise bounded by some constant
$K_{\max}$. Then, by the analysis of [34, Eq. 53], there exists a constant
$C\equiv C_{L,G,K_{\max},R}$ depending only on $L,G,K_{\max}$ and $R$ such
that

$\sup_{0\leq h\leq T}\operatorname{dist}(X(t+h),\Phi_{h}(X(t)))\leq
C_{L,G,K_{\max},R}\cdot\left[\sup_{n\geq M(t)}\left(\lVert
b_{n}\rVert_{\scriptscriptstyle
X_{n}}+\gamma_{n}\right)+\Delta(t-1;T+1)\right]$ (B.8)

By Assumption 3, we have $\lVert b_{n}\rVert_{\scriptscriptstyle
X_{n}}=\operatorname{\mathcal{O}}(\gamma_{n})$. Since $\gamma_{n}\to 0$, it
suffices to show that $\Delta(t;T)\to 0$ with probability $1$ under
Assumptions 2 and 3. This is equivalent to showing that, for any
$\varepsilon>0$, we have

$\lim_{t\to\infty}\Delta(t;T)\leq\varepsilon\quad\text{with probability 1}.$
(B.9)

To this end, let $n=M(t)$ and recall that, by (B.2), we have

$\operatorname{\mathbb{E}}\left[\exp\left(\langle
w,\bar{U}^{\shortparallel}_{n}\rangle\right)\nonscript\,\middle|\nonscript\,\mathopen{}\mathcal{F}_{n}\right]\leq\exp\left(\frac{\sigma^{2}}{2}\lVert
w\rVert^{2}\right)$ (B.10)

for all $w\in\mathbb{R}^{d}$ where $d$ is the dimension of $\mathcal{M}$.
Therefore, for each $w\in\mathbb{R}^{d}$, the sequence $Y_{n}(w)$ defined by

$Y_{n}(w)\coloneqq\exp\left(\sum_{k=1}^{n}\langle
w,\gamma_{k}\bar{U}^{\shortparallel}_{k}\rangle-\frac{\sigma^{2}\lVert
w\rVert^{2}}{2}\sum_{k=1}^{n}\gamma_{k}^{2}\right)$ (B.11)

is a supermartingale. Since $Y_{n}$ is a supermartingale, we have

$\displaystyle\operatorname{\mathbb{P}}\left(\sup_{n<k\leq
M(\tau_{n}+T)}\sum_{i=n}^{k-1}\langle
w,\gamma_{i}\bar{U}^{\shortparallel}_{i}\rangle\geq\delta\right)$
$\displaystyle\qquad\leq\operatorname{\mathbb{P}}\left(\sup_{n<k\leq
M(\tau_{n}+T)}Y_{k}(w)\geq Y_{n}(w)\exp\left(\delta-\frac{\sigma^{2}\lVert
w\rVert^{2}}{2}\sum_{i=n}^{M(\tau_{n}+T)-1}\gamma_{i}^{2}\right)\right)$
$\displaystyle\qquad\leq\exp\left(\frac{\sigma^{2}\lVert
w\rVert^{2}}{2}\sum_{i=n}^{M(\tau_{n}+T)-1}\gamma_{i}^{2}-\delta\right)$
(B.12)

for any $\delta>0$. Now, let $e_{i}$ be the $i$-th basis vector of
$\mathbb{R}^{d}$. Then, by (B.12), we have

$\displaystyle\operatorname{\mathbb{P}}\left(\sup_{n<k\leq
M(\tau_{n}+T)}\sum_{i=n}^{k-1}\langle\pm
de_{i},\gamma_{k}\bar{U}^{\shortparallel}_{k}\rangle\geq\varepsilon\right)$
$\displaystyle=\operatorname{\mathbb{P}}\left(\sup_{n<k\leq
M(\tau_{n}+T)}\sum_{i=n}^{k-1}\langle\pm\varepsilon^{-1}\delta
de_{i},\gamma_{k}\bar{U}^{\shortparallel}_{k}\rangle\geq\delta\right)$
$\displaystyle\leq\exp\left(\frac{\sigma^{2}\delta^{2}d^{2}}{2\varepsilon^{2}}\sum_{i=n}^{M(\tau_{n}+T)-1}\gamma_{i}^{2}-\delta\right).$
(B.13)

Optimizing (B.13) over $\delta$, we get

$\displaystyle\operatorname{\mathbb{P}}\left(\sup_{n<k\leq
M(\tau_{n}+T)}\sum_{i=n}^{k-1}\langle\pm
de_{i},\gamma_{k}\bar{U}^{\shortparallel}_{k}\rangle\geq\varepsilon\right)$
$\displaystyle\leq\exp\left(-\frac{\varepsilon^{2}}{2\sigma^{2}d^{2}\sum_{i=n}^{M(\tau_{n}+T)-1}\gamma_{i}^{2}}\right).$
(B.14)

Since $\gamma_{n}\to 0$, with loss of generality we may assume that
$\gamma_{n}\leq 1$, and hence

$\displaystyle\operatorname{\mathbb{P}}\left(\sup_{n<k\leq
M(\tau_{n}+T)}\sum_{i=n}^{k-1}\langle\pm
de_{i},\gamma_{k}\bar{U}^{\shortparallel}_{k}\rangle\geq\varepsilon\right)$
$\displaystyle\leq\exp\left(-\frac{\varepsilon^{2}}{2\sigma^{2}d^{2}\sum_{i=n}^{M(\tau_{n}+T)-1}\gamma_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{\varepsilon^{2}}{2\sigma^{2}d^{2}\int_{t}^{t+T}\bar{\gamma}(t)}\right)$
(B.15)

where, analogously to (B.4), we have defined the piece-wise constant
interpolated step-size sequence

$\bar{\gamma}(t)=\gamma_{n}\quad\text{for all $t\in[\tau_{n},\tau_{n+1})$,
$n\geq 1$.}$ (B.16)

Since

$\displaystyle\left\lVert\sum_{i=n}^{k-1}\gamma_{i}\bar{U}^{\shortparallel}_{i}\right\rVert\geq\varepsilon\quad\Rightarrow\quad\exists\,i\text{
such that }\sum_{i=n}^{k-1}\langle\pm
de_{i},\gamma_{i}\bar{U}^{\shortparallel}_{i}\rangle\geq\varepsilon,$ (B.17)

by the union bound, we have

$\displaystyle\operatorname{\mathbb{P}}\left(\Delta(t,T)\geq\varepsilon\right)\leq
2d\cdot\exp\left(-\frac{\varepsilon^{2}}{2\sigma^{2}d^{2}\int_{t}^{t+T}\bar{\gamma}(t)}\right)\leq
2d\cdot\exp\left(-\frac{\varepsilon^{2}}{2\sigma^{2}d^{2}T\bar{\gamma}(s)}\right)$
(B.18)

for some $t\leq s\leq t+T$. Therefore, by setting
$\lambda\coloneqq\exp\left(-\frac{\varepsilon^{2}}{2\sigma^{2}d^{2}T}\right)<1$,
we have

$\sum_{k}\operatorname{\mathbb{P}}\left(\Delta(kT,T)\geq\varepsilon\right)\leq
2d\sum_{k}\lambda^{1/\gamma_{k}}<\infty$ (B.19)

by Assumption 2. The Borel-Cantelli Lemma then implies that the following
event happens almost surely:

$\lim_{k\to\infty}\Delta(kT;T)\leq\varepsilon.$ (B.20)

The proof is finished by noting that, for $kT\leq t<(k+1)T$,

$\Delta(t;T)\leq 2\Delta(kT;T)+\Delta(kT+T;T)$ (B.21)

by triangle inequality. ∎

###  B.2. Proof of Theorem 1

We are now in a position to present our proof of Theorem 1, which we restate
below for convenience:

See 1

###### Proof.

Assume that $X_{n}\to\mathcal{S}$. We will show that this event has zero
probability in a series of steps which we outline below.

#### Step 1: Isometrically embedded Robbins–Monro iterates.

Since $\mathcal{M}$ is assumed to be smooth, the second Nash embedding theorem
[37] implies there exists a smooth and _isometric_ embedding
$\iota:\mathcal{M}\to\mathbb{R}^{M}$ such that, for all $x\in\mathcal{M}$ and
all $z,w\in\mathcal{T}_{x}\mathcal{M}$, we have

$\langle
z,w\rangle_{x}=\langle\operatorname{D}\iota_{x}(z),\operatorname{D}\iota_{x}(w)\rangle.$
(B.22)

Since $\iota$ is an embedding, it is surjective. Since it is isometric, it
preserves distance and hence must be one-to-one. Therefore, $\iota$ is an
diffeomorphism since it is also smooth. We can therefore define the
_pushforward_ of the vector field $v$ on $\mathcal{M}$ to a vector field on
the image $\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle
E}}\subset\mathbb{R}^{M}$ in the usual way as

$v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{0}(x^{\scriptscriptstyle{\scriptscriptstyle
E}})\coloneqq\operatorname{D}\iota_{x}v(x)\qquad\text{for all
$x^{\scriptscriptstyle{\scriptscriptstyle E}}=\iota(x)\in\mathbb{R}^{M}$}.$
(B.23)

We also set $\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle
E}}\coloneqq\iota(\mathcal{S})$.

By the Tietze extension theorem and the smooth manifold extension lemma [44],
$v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{0}(x^{\scriptscriptstyle{\scriptscriptstyle E}})$ can be extended to a
Lipschitz continuous vector field on all of $\mathbb{R}^{M}$, which we still
denote by $v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{0}(x^{\scriptscriptstyle{\scriptscriptstyle E}})$. To avoid trivialities,
we will also need to ensure that $v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{0}(x^{\scriptscriptstyle{\scriptscriptstyle E}})$ is not $0$ in a
neighborhood of $\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$: If
this is the case, then we set our target field
$v^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle E}})\coloneqq
v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{0}(x^{\scriptscriptstyle{\scriptscriptstyle E}})$; otherwise, let
$\mathbf{1}$ denote the vector of 1’s in all coordinates, and define a new
vector field $v^{\scriptscriptstyle{\scriptscriptstyle E}}$ on
$\mathbb{R}^{M}$ as

$v^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle E}})\coloneqq
v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{0}(x^{\scriptscriptstyle{\scriptscriptstyle
E}})+\operatorname{dist}^{\scriptscriptstyle
E}(x^{\scriptscriptstyle{\scriptscriptstyle
E}},\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle
E}})^{2}\cdot\mathbf{1}$ (B.24)

where $\operatorname{dist}^{\scriptscriptstyle
E}(x^{\scriptscriptstyle{\scriptscriptstyle
E}},\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle
E}})\coloneqq\inf_{y^{\scriptscriptstyle
E}\in\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}}\lVert
x^{\scriptscriptstyle{\scriptscriptstyle E}}-y^{\scriptscriptstyle E}\rVert$.
Obviously, this new vector field agrees with
$v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{0}(x^{\scriptscriptstyle{\scriptscriptstyle E}})$ on
$\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle E}}$ and therefore is
still the pushforward of $v$ under $\iota$. Moreover, it is not uniformly 0 in
a neighborhood of $\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$.
[It is worth noting that the so-defined vector field
$v^{\scriptscriptstyle{\scriptscriptstyle E}}$ is in general _not_ the
(Euclidean) gradient of any function, a fact which presents significant
difficulty to our analysis.]

#### Step 2: $\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$ is an
unstable invariant set.

Our next goal is to show that there exists an _unstable neighborhood_
$\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle E}}$ around
$\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$ in the following
sense: First, for each $\hat{x}\in\mathcal{S}$, consider its image
$\hat{x}^{\scriptscriptstyle{\scriptscriptstyle
E}}=\iota(\hat{x})\in\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$.
Since $v^{\scriptscriptstyle{\scriptscriptstyle E}}$ agrees with the
pushforward of $v\equiv\mathrm{grad}f$ under $\iota$, and since $\iota$ is an
isometry, we have the following relation for all tangent vector
$z\in\mathcal{T}_{\hat{x}}\mathcal{M}$:

$\langle\operatorname{D}v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{\scriptscriptstyle x^{\scriptscriptstyle{\scriptscriptstyle
E}}}\operatorname{D}\iota_{\hat{x}}(z),\operatorname{D}\iota_{\hat{x}}(z)\rangle=\langle\operatorname{Hess}f(\hat{x})z,z\rangle_{\hat{x}}.$
(B.25)

Since $\hat{x}$ is a strict saddle point, (B.25) implies that
$\lambda_{\min}\left(\operatorname{D}v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{\hat{x}^{\scriptscriptstyle{\scriptscriptstyle E}}}\right)<-c_{-}<0$ for
all $\hat{x}^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$. By an
established series of arguments [12, 10, 46], using the stable manifold
theorem for a strict saddle [63] and the transversality of the strict saddle
manifold [1], there exists a $(M-m)$-dimensional embedded submanifold
$\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$ in $\mathbb{R}^{M}$
that contains $\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$. [Here,
$1\leq m\leq M$, and $M-m$ represents the dimension of the _unstable manifold_
of $v^{\scriptscriptstyle{\scriptscriptstyle E}}$.] Moreover, writing
$\Phi^{\scriptscriptstyle{\scriptscriptstyle E}}$ for the flow generated by
$v^{\scriptscriptstyle{\scriptscriptstyle E}}$, it follows that
$\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$ is locally invariant
under $\Phi^{\scriptscriptstyle{\scriptscriptstyle E}}$. Hence, there exists a
neighborhood $\mathcal{N}^{\scriptscriptstyle E}$ of
$\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$ in $\mathbb{R}^{M}$
and a positive time $t_{0}$ such that for all $\lvert t\rvert\leq t_{0}$, the
following inclusion holds:

$\Phi^{\scriptscriptstyle{\scriptscriptstyle
E}}_{t}(\mathcal{N}^{\scriptscriptstyle
E}\cap\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle
E}})\subset\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}.$ (B.26)

To proceed, note that $\mathbb{R}^{M}$ can be decomposed further as the direct
sum of the tangent space to
$\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$ at
$x^{\scriptscriptstyle{\scriptscriptstyle E}}$, denoted by
$\mathcal{T}_{x^{\scriptscriptstyle{\scriptscriptstyle
E}}}\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$, and an additional
complementary subspace denoted by
$\mathcal{E}^{u}_{{x^{\scriptscriptstyle{\scriptscriptstyle E}}}}$:

$\mathbb{R}^{M}=\mathcal{T}_{x^{\scriptscriptstyle{\scriptscriptstyle
E}}}\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle
E}}\oplus\mathcal{E}^{u}_{{x^{\scriptscriptstyle{\scriptscriptstyle E}}}}.$
(B.27)

The mapping $x^{\scriptscriptstyle{\scriptscriptstyle
E}}\to\mathcal{E}^{u}_{{x^{\scriptscriptstyle{\scriptscriptstyle E}}}}$ is
continuous, where $x^{\scriptscriptstyle{\scriptscriptstyle E}}$ varies over
$\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$ and
$\mathcal{E}^{u}_{{x^{\scriptscriptstyle{\scriptscriptstyle E}}}}$ belongs to
the Grassmanian manifold $G({m},M)$. It is important to note that
_$\mathcal{E}^{u}_{{x^{\scriptscriptstyle{\scriptscriptstyle E}}}}$ contains
at least one direction in $\mathcal{T}_{\scriptscriptstyle
x^{\scriptscriptstyle{\scriptscriptstyle
E}}}\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle E}}$_ due to (B.25).
Then, for all $t\in\mathbb{R}$ and
$x\in\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$, the Jacobian of
$\Phi^{\scriptscriptstyle{\scriptscriptstyle E}}_{t}$ evaluated at
$x^{\scriptscriptstyle{\scriptscriptstyle E}}$ maps
$\mathcal{E}^{u}_{{x^{\scriptscriptstyle{\scriptscriptstyle E}}}}$ to
$\mathcal{E}^{u}_{{\Phi^{\scriptscriptstyle{\scriptscriptstyle
E}}_{t}(x^{\scriptscriptstyle{\scriptscriptstyle E}})}}$, i.e.,

$\operatorname{D}\Phi^{\scriptscriptstyle{\scriptscriptstyle
E}}_{t}(x^{\scriptscriptstyle{\scriptscriptstyle
E}})\mathcal{E}^{u}_{{x^{\scriptscriptstyle{\scriptscriptstyle
E}}}}=\mathcal{E}^{u}_{{\Phi^{\scriptscriptstyle{\scriptscriptstyle
E}}_{t}(x^{\scriptscriptstyle{\scriptscriptstyle E}})}}.$ (B.28)

Finally, and most importantly, we have the following characterization that
formalizes the idea that _all directions in the unstable manifold should
diverge under $\Phi^{\scriptscriptstyle{\scriptscriptstyle E}}_{t}$_: There
exist positive constants $c$ and $C$ such that for all
$x^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$,
$w^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{E}^{u}_{{x^{\scriptscriptstyle{\scriptscriptstyle E}}}}$, and
$t\geq 0$, the following inequality holds:

$\lVert\operatorname{D}\Phi^{\scriptscriptstyle{\scriptscriptstyle
E}}_{t}(x^{\scriptscriptstyle{\scriptscriptstyle
E}})w^{\scriptscriptstyle{\scriptscriptstyle E}}\rVert\geq Ce^{ct}\lVert
w^{\scriptscriptstyle{\scriptscriptstyle E}}\rVert.$ (B.29)

The above verifies all the conditions for a _unstable invariant set_ for
$\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$ in the sense of
Benaïm [10]. A deep result by Benaïm & Hirsch [11] then asserts the existence
of a _local Lyapunov function_ near a neighborhood of
$\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$, whose construction
we outline below.

#### Step 3: Local Lyapunov function
$\eta^{\scriptscriptstyle{\scriptscriptstyle E}}$.

For a right-differentiable function
$\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}\colon\mathbb{R}^{M}\to\mathbb{R}$ we define its right derivative
$\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle E}}$ applied to a
vector $h^{\scriptscriptstyle{\scriptscriptstyle E}}\in\mathbb{R}^{M}$ by

$\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}({x^{\scriptscriptstyle{\scriptscriptstyle
E}}})h^{\scriptscriptstyle{\scriptscriptstyle E}}=\lim_{t\to
0^{+}}\frac{\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle
E}}+th^{\scriptscriptstyle{\scriptscriptstyle
E}})-\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle E}})}{t}.$ (B.30)

If $\eta^{\scriptscriptstyle{\scriptscriptstyle E}}$ is differentiable, then
(B.30) is simply
$\langle\operatorname{\nabla}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle
E}}),h^{\scriptscriptstyle{\scriptscriptstyle E}}\rangle$. In view of all
this, Benaïm [10] provides the following crucial result:

######  Proposition B.1 (Benaïm, 1999, Prop. 9.5).

There exists a compact neighborhood
$\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})$ of
$\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$, positive numbers
$l,\beta>0$, and a map $\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}\colon\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})\to\mathbb{R}^{+}$
such that $\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle E}})=0$ if and only if
$x^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$, and the
following holds:

  1. n(it n)

$\eta^{\scriptscriptstyle{\scriptscriptstyle E}}$ is $C^{2}$ on $\
\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle
E}})\setminus\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$.

  2. n(it n)

For all $x^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle
E}})\cap\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$,
$\eta^{\scriptscriptstyle{\scriptscriptstyle E}}$ admits a right derivative
$\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle
E}})\colon\mathbb{R}^{M}\to\mathbb{R}^{M}$ which is Lipschitz, convex and
positively homogeneous.

  3. n(it n)

There exists $k>0$ and a neighborhood
$\mathcal{W}^{\scriptscriptstyle{\scriptscriptstyle E}}\subset\mathbb{R}^{M}$
of $0$ such that for all $x^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})$ and
$z^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{W}^{\scriptscriptstyle{\scriptscriptstyle E}}$,

$\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle
E}}+z^{\scriptscriptstyle{\scriptscriptstyle
E}})\geq\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle
E}})+{\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle
E}})}{z^{\scriptscriptstyle{\scriptscriptstyle E}}}-k\lVert
z^{\scriptscriptstyle{\scriptscriptstyle E}}\rVert^{2}.$ (B.31)

  4. n(it n)

There exists $c_{1}>0$ such that for all
$x^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle
E}})\setminus\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$

$\left\lVert\Pi_{\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle
E}}}\left(\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle E}})\right)\right\rVert\geq
c_{1}$ (B.32)

where $\Pi_{\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle E}}}$ is the
projection on $\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle E}}$.222The
original statement in [10] is
$\left\lVert\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle E}})\right\rVert\geq c_{1}$. The
inequality in (B.32) is obtained via the same proof and noting that
$\mathcal{E}^{u}_{{x^{\scriptscriptstyle{\scriptscriptstyle E}}}}$ contains at
least one direction in $\mathcal{T}_{x^{\scriptscriptstyle{\scriptscriptstyle
E}}}\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle E}}$. In addition, for
all $x^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle
E}})\cap\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$ and
$z^{\scriptscriptstyle{\scriptscriptstyle E}}\in\mathbb{R}^{M}$

$\langle\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle
E}}),z^{\scriptscriptstyle{\scriptscriptstyle E}}\rangle\geq c_{1}\lVert
z^{\scriptscriptstyle{\scriptscriptstyle
E}}-\operatorname{D}\operatorname{\Pi}(x^{\scriptscriptstyle{\scriptscriptstyle
E}})z^{\scriptscriptstyle{\scriptscriptstyle E}}\rVert$ (B.33)

where $\operatorname{\Pi}$ is the projection of a neighborhood of
$\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}}$ onto
$\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$.

  5. n(it n)

For all $x^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle
E}})\cap\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$,
$w^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{T}_{x^{\scriptscriptstyle{\scriptscriptstyle
E}}}\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$ and
$z^{\scriptscriptstyle{\scriptscriptstyle E}}\in\mathbb{R}^{M}$,

${\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle
E}})}{(w^{\scriptscriptstyle{\scriptscriptstyle
E}}+z^{\scriptscriptstyle{\scriptscriptstyle
E}})}={\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle
E}})}{z^{\scriptscriptstyle{\scriptscriptstyle E}}}.$ (B.34)

  6. n(it n)

For all $x^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})$ we have

${\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x)}{v^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle
E}})}\geq\beta\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle E}}).$ (B.35)

The function $\eta^{\scriptscriptstyle{\scriptscriptstyle E}}$ will serve as a
local “energy function” that plays an instrumental role in our analysis; the
well-posedness of $\Pi$ is guaranteed by [27, Chap 4].

#### Step 4: Geodesic offset.

Consider the image of an RRM scheme $X_{n}^{\scriptscriptstyle
E}\coloneqq\iota(X_{n})$. If $X_{n}^{\scriptscriptstyle
E}\notin\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})$ for all $n$, then
there is nothing to prove. Otherwise, without loss of generality we may assume
that $X_{1}^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})$. Accordingly,
define the first exit time $T$ from
$\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})$ as

$T\coloneqq\inf\\{k\geq 1:X^{\scriptscriptstyle{\scriptscriptstyle
E}}_{n}\notin\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})\\}.$ (B.36)

Evidently, $T$ is a stopping time adaptive to $\mathcal{F}_{n}$, so it
suffices to show that333Theorem 1 follows from (B.37) because the event
$\\{\operatorname{dist}(X_{n},\mathcal{S})\to 0\\}$ is contained in
$\\{T=\infty\\}$.

$\operatorname{\mathbb{P}}(T=\infty)=0.$ (B.37)

To this end, a notion that plays a central role in our analysis is the
_geodesic offet_ , defined as follows. Define the pushforward of the
respective noise and bias vectors in the RRM scheme $X_{n}$ by

$\displaystyle U_{n}^{\scriptscriptstyle
E}\coloneqq\operatorname{D}\iota_{\scriptscriptstyle X_{n}}U_{n},\quad
b_{n}^{\scriptscriptstyle E}\coloneqq\operatorname{D}\iota_{\scriptscriptstyle
X_{n}}b_{n}.$ (B.38)

_It is important to remember that $U_{n}^{\scriptscriptstyle
E}\in\mathcal{T}_{X_{n}^{\scriptscriptstyle
E}}\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle E}}$_, a fact that we
will use freely in the sequel.

We now formally define the _geodesic offset_ $\Delta(x;z)\in\mathbb{R}^{M}$
as, for any $x\in\mathcal{M}$ and $z\in\mathcal{T}_{x}\mathcal{M}$,

$\displaystyle\Delta(x;z)\coloneqq\iota(\exp_{x}(z))-\iota(x)-\operatorname{D}\iota_{x}(z).$
(B.39)

By Assumption 4, there exists $\varrho>0$ such that, for all $\lVert
z\rVert_{\scriptscriptstyle x}<\varrho$, the exponential mapping is the unique
minimizing geodesic. Furthermore, for all such $z$’s, define the curve
$\gamma^{\scriptscriptstyle
E}(t)\coloneqq\iota(x)+t\operatorname{D}\iota_{x}(z)$, then

$\gamma^{\scriptscriptstyle
E}(0)=\iota(x),\quad\dot{\gamma}^{\scriptscriptstyle
E}(0)=\operatorname{D}\iota_{x}(z)$ (B.40)

so that $\gamma^{\scriptscriptstyle E}(t)$ agrees with the image of the
geodesics $\iota(\exp_{x}(tz))$. As a result, for any $\lVert
z\rVert_{\scriptscriptstyle x}<\varrho$, we have
$\Delta(x;z)=\operatorname{\mathcal{O}}(\lVert z\rVert_{x}^{2})$. Now, setting
$x\leftarrow X_{n}$ and $z\leftarrow\gamma_{n}(v(X_{n})+U_{n}+b_{n})$, we have

$\displaystyle X_{n+1}^{\scriptscriptstyle E}$
$\displaystyle=X_{n}^{\scriptscriptstyle
E}+\gamma_{n}\left(v^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})+U_{n}^{\scriptscriptstyle
E}+b_{n}^{\scriptscriptstyle E}\right)+\epsilon_{n}^{\scriptscriptstyle E}$
(B.41)

where $\epsilon_{n}^{\scriptscriptstyle
E}\coloneqq\Delta(X_{n};\gamma_{n}(v(X_{n})+U_{n}+b_{n}))$. By Assumption 3,
we know that $U_{n}^{\scriptscriptstyle E}+b_{n}^{\scriptscriptstyle
E}=\operatorname{\mathcal{O}}(1)$ almost surely. Moreover, since $v$ is
smooth, on the event $T=\infty$, $X_{n}^{\scriptscriptstyle
E}\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})$ for all $n$ and
therefore $\sup_{n\geq 1}\lVert v^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})\rVert<\infty$. Since $\gamma_{n}\to 0$, for
any $n$ large enough, we get

$\epsilon_{n}^{\scriptscriptstyle
E}=\operatorname{\mathcal{O}}(\gamma_{n}^{2}).$ (B.42)

Now, define two sequences of random variables $\\{Y_{n}\\}_{n\geq 1}$ and
$\\{S_{n}\\}_{n\geq 1}$ as

$\displaystyle Y_{n+1}$
$\displaystyle=\left(\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X^{\scriptscriptstyle{\scriptscriptstyle
E}}_{n+1})-\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})\right)\operatorname{\mathds{1}}_{\\{n\leq
T\\}}+\gamma_{n}\operatorname{\mathds{1}}_{\\{n>T\\}},$ (B.43a) $\displaystyle
S_{0}$ $\displaystyle=\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X^{{\scriptscriptstyle E}}_{0}),\quad S_{n}=S_{0}+\sum_{k=1}^{n}Y_{k}.$
(B.43b)

The importance of these sequences is that the event $\\{T=\infty\\}$ is
contained in the event $\\{S_{n}\to 0\\}$. To see this, assume $T=\infty$.
Then we have $Y_{n+1}=\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n+1}^{\scriptscriptstyle
E})-\eta^{\scriptscriptstyle{\scriptscriptstyle E}}(X_{n}^{\scriptscriptstyle
E})$ and $S_{n}=\eta^{\scriptscriptstyle{\scriptscriptstyle E}}(X_{n})$ by
Eqs. B.43a and B.43b. In addition, since $\\{X_{n}^{\scriptscriptstyle E}\\}$
remains in $\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})$ by definition of
the stopping time $T$, Theorem 2 combined with [10, Theorem 5.7] asserts that
the limit set $L(\\{X_{n}^{\scriptscriptstyle E}\\})$ of
$\\{X_{n}^{\scriptscriptstyle E}\\}$ is a nonempty compact invariant subset of
$\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})$, so that for all
$y^{{\scriptscriptstyle E}}\in L(\\{X_{n}^{\scriptscriptstyle E}\\})$ and
$t\in\mathbb{R}$, $\Phi^{\scriptscriptstyle{\scriptscriptstyle
E}}_{t}(y^{{\scriptscriptstyle
E}})\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})$. But then
Proposition B.1Item 6 implies that
$\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(\Phi^{\scriptscriptstyle{\scriptscriptstyle E}}_{t}(y^{{\scriptscriptstyle
E}}))\geq e^{\beta t}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(y^{\scriptscriptstyle E})$ for all $t>0$, forcing
$\eta^{\scriptscriptstyle{\scriptscriptstyle E}}(y^{\scriptscriptstyle E})$ to
be zero. Since $\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle E}})=0$ if and only if
$x^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$, we have
$L(\\{X_{n}^{\scriptscriptstyle
E}\\})\subset\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$, which
implies $S_{n}=\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})\to 0$.

Therefore, the rest of the proof is devoted to showing that
$\operatorname{\mathbb{P}}\left(\lim_{n\to\infty}S_{n}=0\right)=0$.

#### Step 5: Probabilistic estimates.

To this end, we will need two technical lemmas, originally due to Pemantle
[55], and extended to their current form by Benaïm & Hirsch [12].

######  Lemma B.1.

Let $S_{n}$ be a nonnegative stochastic process,
$S_{n}=S_{0}+\sum\nolimits_{k=1}^{n}Y_{k}$ where $Y_{n}$ is
$\mathcal{F}_{n}$-measurable. Let
$\alpha_{n}\coloneqq\sum\nolimits_{k=n}^{\infty}\gamma_{k}^{2}$. Assume there
exist a sequence $0\leq\varepsilon_{n}=o(\sqrt{\alpha_{n}})$, constants
$a_{1},a_{2}>0$ and an integer $N_{0}$ such that for all $n\geq N_{0}$,

  1. n(it n)

$\lvert Y_{n}\rvert=o(\sqrt{\alpha_{n}})$.

  2. n(it n)

$\operatorname{\mathds{1}}_{\\{S_{n}>\varepsilon_{n}\\}}\operatorname{\mathbb{E}}[Y_{n+1}|\mathcal{F}_{n}]\geq
0$.

  3. n(it n)

$\operatorname{\mathbb{E}}[S^{2}_{n+1}-S^{2}_{n}|\mathcal{F}_{n}]\geq
a_{1}\gamma^{2}_{n}$.

  4. n(it n)

$\operatorname{\mathbb{E}}[Y^{2}_{n+1}|\mathcal{F}_{n}]\leq
a_{2}\gamma^{2}_{n}.$

Then $\operatorname{\mathbb{P}}(\lim_{n\to\infty}\nolimits S_{n}=0)=0.$

######  Lemma B.2.

Let $S_{n}$ be a nonnegative stochastic process,
$S_{n}=S_{0}+\sum\nolimits_{k=1}^{n}Y_{k}$ where $Y_{n}$ is
$\mathcal{F}_{n}$-measurable and $|Y_{n}|\leq C$ almost surely for some
constant $C$. Assume that $\sum_{n}\gamma_{n}^{2}=\infty$, and there exists
$c>0,N^{\prime}\in\mathbb{N}$ such that for all $n\geq N^{\prime}$,

$\operatorname{\mathbb{E}}[S_{n+1}^{2}-S_{n}^{2}\nonscript\,|\nonscript\,\mathopen{}\mathcal{F}_{n}]\geq
c\gamma_{n}^{2}.$ (B.44)

Then

$\operatorname{\mathbb{P}}\left(\lim_{n\to\infty}S_{n}=0\right)=0.$ (B.45)

Our proof will be concluded by verifying all the premises of Lemmas B.1–B.2.
To that end, note first that the sequence $S_{n}$ defined in (B.43b) is
nonnegative by construction. We will then separate the analysis into two
cases:

####  Case 1: Square-summable step-sizes ($\sum_{n}\gamma_{n}^{2}<\infty$).

In this case, we have

$\displaystyle\lim_{n\to\infty}\frac{\gamma_{n}}{\sqrt{\sum\nolimits_{k=n}^{\infty}\gamma_{k}^{2}}}=0$
(B.46)

so
$\gamma_{n}=o\left(\sqrt{\sum\nolimits_{k=n}^{\infty}\gamma_{k}^{2}}\right)$.
This fact will be used in the proof when we invoke Lemma B.1 below with
$\varepsilon_{n}=\operatorname{\mathcal{O}}(\gamma_{n})$ and
$\alpha_{n}=\sum\nolimits_{k=n}^{\infty}\gamma_{k}^{2}$ therein. The
verification process then proceeds as follows:

  * •

Verifying Lemma B.1Items 1 and 4: By the Lipschitz continuity of
$\eta^{\scriptscriptstyle{\scriptscriptstyle E}}$, we know that

$\displaystyle\lVert\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}X_{n}^{\scriptscriptstyle E}-\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}X_{n+1}^{\scriptscriptstyle E}\rVert$ $\displaystyle\leq L^{\prime}\lVert
X_{n}^{\scriptscriptstyle E}-X_{n+1}^{\scriptscriptstyle E}\rVert$
$\displaystyle=\gamma_{n}\lVert v^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})+U_{n}^{\scriptscriptstyle
E}+b_{n}^{\scriptscriptstyle E}\rVert$ (B.47)

where $L^{\prime}$ is the Lipschitz constant of
$\eta^{\scriptscriptstyle{\scriptscriptstyle E}}$. We have seen in the
analysis of (B.42) that $\lVert v^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})+U_{n}^{\scriptscriptstyle
E}+b_{n}^{\scriptscriptstyle E}\rVert=\operatorname{\mathcal{O}}(1)$ almost
surely by Assumption 3 on the event $T=\infty$. Therefore, $\lvert
Y_{n+1}\rvert=\operatorname{\mathcal{O}}({\gamma_{n}})=o(\sqrt{\alpha_{n}})$
which implies both Lemma B.1Items 1 and 4.

  * •

Verifying Lemma B.1Item 2: Let $k^{\prime}=k\lVert
v^{\scriptscriptstyle{\scriptscriptstyle E}}\rVert+\sigma$ where $k$ is given
by Proposition B.1Item 3 and $\lVert v^{\scriptscriptstyle{\scriptscriptstyle
E}}\rVert\coloneqq\sup\\{v^{\scriptscriptstyle{\scriptscriptstyle
E}}(x^{\scriptscriptstyle{\scriptscriptstyle
E}}):x^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})\\}$ and $\sigma$
is the uniform bound of $U_{n}$. If $n\leq T$, using Proposition B.1Items 2,
3, 5 and 6 we have

$\displaystyle\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n+1}^{\scriptscriptstyle
E})-\eta^{\scriptscriptstyle{\scriptscriptstyle E}}(X_{n}^{\scriptscriptstyle
E})$
$\displaystyle\geq\gamma_{n}\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle
E})\left(v^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})+U_{n}^{\scriptscriptstyle
E}+b_{n}^{\scriptscriptstyle E}\right)$
$\displaystyle\qquad+\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})\epsilon_{n}^{\scriptscriptstyle
E}-k\gamma_{n}^{2}\left(\lVert v^{\scriptscriptstyle{\scriptscriptstyle
E}}\rVert+\lVert U_{n}^{\scriptscriptstyle E}\rVert+\lVert
b_{n}^{\scriptscriptstyle E}\rVert\right)^{2}$
$\displaystyle\geq\gamma_{n}\beta\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle
E})+\gamma_{n}\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})U_{n}^{\scriptscriptstyle
E}+\gamma_{n}\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})b_{n}^{\scriptscriptstyle E}$
$\displaystyle\qquad+\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})\epsilon_{n}^{\scriptscriptstyle
E}-2k^{\prime}\gamma_{n}^{2}-2k\gamma_{n}^{2}\lVert b_{n}^{\scriptscriptstyle
E}\rVert^{2}.$ (B.48)

By Assumption 3, there exists a constant $c^{\prime}>0$ such that $-\lVert
b_{n}^{\scriptscriptstyle E}\rVert\geq-c^{\prime}\gamma_{n}$ (a.s.). Combining
this with the Lipschitz continuity of
$\eta^{\scriptscriptstyle{\scriptscriptstyle E}}$ and (B.42), we can merge the
last four terms in (• ‣ B.2) as

$\displaystyle\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n+1}^{\scriptscriptstyle
E})-\eta^{\scriptscriptstyle{\scriptscriptstyle E}}(X_{n}^{\scriptscriptstyle
E})$
$\displaystyle\geq\gamma_{n}\beta\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle
E})+\gamma_{n}\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})U_{n}^{\scriptscriptstyle
E}-2k^{\prime\prime}\gamma_{n}^{2}$ (B.49)

for some constant $k^{\prime\prime}>0$. We thus get

$\operatorname{\mathds{1}}_{\left\\{n\leq
T\right\\}}\operatorname{\mathbb{E}}[Y_{n+1}|\mathcal{F}_{n}]\geq\operatorname{\mathds{1}}_{\left\\{n\leq
T\right\\}}\left[\gamma_{n}\beta\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle
E})-2k^{\prime\prime}\gamma_{n}^{2}+\gamma_{n}\operatorname{\mathbb{E}}[\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})U_{n}^{\scriptscriptstyle
E}|\mathcal{F}_{n}]\right].$ (B.50)

By Proposition B.1Item 2 again, we have

$\displaystyle\operatorname{\mathbb{E}}[\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})U_{n}^{\scriptscriptstyle
E}|\mathcal{F}_{n}]$
$\displaystyle\geq\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle
E})\operatorname{\mathbb{E}}[U_{n}^{\scriptscriptstyle E}|\mathcal{F}_{n}]=0$
$\displaystyle=\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle
E})\operatorname{\mathbb{E}}[\operatorname{D}\iota_{\scriptscriptstyle
X_{n}}U_{n}|\mathcal{F}_{n}]=0$ (B.51)

since we have assumed the noise to be zero mean. Combining (B.50) and (B.51),
we then get

$\operatorname{\mathds{1}}_{\left\\{n\leq
T\right\\}}\operatorname{\mathbb{E}}[Y_{n+1}|\mathcal{F}_{n}]\geq\operatorname{\mathds{1}}_{\left\\{n\leq
T\right\\}}\left[\gamma_{n}\beta\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})-2k^{\prime\prime}\gamma_{n}^{2}\right].$
(B.52)

If $n>T$, $Y_{n+1}=\gamma_{n}$ so trivially

$\operatorname{\mathds{1}}_{\left\\{n\leq
T\right\\}}\operatorname{\mathbb{E}}[Y_{n+1}|\mathcal{F}_{n}]\geq 0.$ (B.53)

Combining (B.52) with (B.53), we see that Lemma B.1Item 2 is satisfied with
$\varepsilon_{n}=\frac{k^{\prime\prime}}{\beta}\gamma_{n}$.

  * •

Verifying Lemma B.1Item 3: We begin by observing that

$\operatorname{\mathbb{E}}[S_{n+1}^{2}-S_{n}^{2}|\mathcal{F}_{n}]=\operatorname{\mathbb{E}}[Y_{n+1}^{2}|\mathcal{F}_{n}]+2S_{n}\operatorname{\mathbb{E}}[Y_{n+1}|\mathcal{F}_{n}].$
(B.54)

If $S_{n}\geq\varepsilon_{n}$, then the last term on the right-hand side of
(B.54) is non-negative by Lemma B.1Item 2 that we just verified above. If
$S_{n}<\varepsilon_{n}$, (B.52) with (B.53) imply that
$S_{n}\operatorname{\mathbb{E}}[Y_{n+1}|\mathcal{F}_{n}]\geq-\varepsilon_{n}k^{\prime\prime}\gamma_{n}^{2}=-\operatorname{\mathcal{O}}(\gamma_{n}^{3})$.
In other words, (B.54) can be rewritten as

$\operatorname{\mathbb{E}}[S_{n+1}^{2}-S_{n}^{2}|\mathcal{F}_{n}]\geq\operatorname{\mathbb{E}}[Y_{n+1}^{2}|\mathcal{F}_{n}]-\operatorname{\mathcal{O}}(\gamma_{n}^{3}).$
(B.55)

Below, we shall prove that
$\operatorname{\mathbb{E}}[Y_{n+1}^{2}|\mathcal{F}_{n}]\geq
b_{1}\gamma_{n}^{2}$ for some $b_{1}>0$ and $n$ large enough. Combining this
with (B.55) proves Lemma B.1Item 3.

From (B.49), we deduce

$\operatorname{\mathds{1}}_{\left\\{n\leq
T\right\\}}\left[\operatorname{\mathbb{E}}[\left(Y_{n+1}\right)_{+}|\mathcal{F}_{n}]-\left(\gamma_{n}\operatorname{\mathbb{E}}[(\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})U_{n}^{\scriptscriptstyle
E})_{+}|\mathcal{F}_{n}]-k^{\prime\prime}\gamma_{n}^{2}\right)\right]\geq 0.$
(B.56)

We now claim that

$\operatorname{\mathds{1}}_{\\{n\leq T\\}\cap\\{X_{n}^{\scriptscriptstyle
E}\notin\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle
E}}\\}}\Big{(}\operatorname{\mathbb{E}}[(\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})U_{n}^{\scriptscriptstyle
E})_{+}|\mathcal{F}_{n}]\Big{)}\geq c_{1}\zeta.$ (B.57)

where $c_{1}$ is given by Proposition B.1Item 4 and $\zeta$ is defined in
Assumption 3. To see this, recall that $\lVert U_{n}\rVert_{\scriptscriptstyle
X_{n}}<\sigma$ by Assumption 3. Moreover, we have $X_{n}^{\scriptscriptstyle
E}\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle E}})$ on the event
$T=\infty$. Proposition B.1Item 1 then implies
$\eta^{\scriptscriptstyle{\scriptscriptstyle E}}$ is differentiable on
$\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle
E}})\setminus\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$, and
Proposition B.1Item 4 further shows that

$\displaystyle\operatorname{\mathds{1}}_{\\{n\leq
T\\}\cap\\{X_{n}^{\scriptscriptstyle
E}\notin\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle
E}}\\}}\Big{(}\operatorname{\mathbb{E}}[(\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})U_{n}^{\scriptscriptstyle
E})_{+}|\mathcal{F}_{n}]\Big{)}$
$\displaystyle\qquad=\operatorname{\mathds{1}}_{\\{n\leq
T\\}\cap\\{X_{n}^{\scriptscriptstyle
E}\notin\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle
E}}\\}}\Big{(}\operatorname{\mathbb{E}}[[\langle\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E}),U_{n}^{\scriptscriptstyle
E}\rangle]_{+}|\mathcal{F}_{n}]\Big{)}$
$\displaystyle\qquad=\operatorname{\mathds{1}}_{\\{n\leq
T\\}\cap\\{X_{n}^{\scriptscriptstyle
E}\notin\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle
E}}\\}}\Big{(}\operatorname{\mathbb{E}}\left[[\langle\Pi_{\mathcal{T}_{X_{n}^{\scriptscriptstyle
E}}\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle
E}}}\left(\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})\right),U_{n}^{\scriptscriptstyle
E}\rangle]_{+}|\mathcal{F}_{n}\right]\Big{)}$ $\displaystyle\qquad\geq
c_{1}\zeta$ (B.58)

where we have used the fact that $U_{n}^{\scriptscriptstyle
E}\in\mathcal{T}_{X_{n}}\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle
E}}$ and Assumption 3.

If $X_{n}^{\scriptscriptstyle
E}\in\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$, we can choose a
unit vector $v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{n}\in\ker(I-\operatorname{D}\operatorname{\Pi}(X_{n}^{\scriptscriptstyle
E}))^{\perp}\cap\mathcal{T}_{X_{n}^{\scriptscriptstyle
E}}\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle E}}$ where
$\operatorname{\Pi}$ denotes the projection operator onto
$\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}$; note that
$v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{n}\in\ker(I-\operatorname{D}\operatorname{\Pi}(X_{n}^{\scriptscriptstyle
E}))^{\perp}\cap\mathcal{T}_{X_{n}^{\scriptscriptstyle
E}}\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle E}}\neq\emptyset$ since
$\mathcal{E}^{u}_{{x^{\scriptscriptstyle{\scriptscriptstyle E}}}}$ contains at
least one direction in $\mathcal{T}_{x^{\scriptscriptstyle{\scriptscriptstyle
E}}}\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle E}}$ for all
$x^{\scriptscriptstyle{\scriptscriptstyle
E}}\in\mathcal{U}^{\scriptscriptstyle{\scriptscriptstyle
E}}(\mathcal{S}^{\scriptscriptstyle{\scriptscriptstyle
E}})\cap\mathcal{M}^{\scriptscriptstyle{\scriptscriptstyle E}}$. By the
definition of $v^{\scriptscriptstyle{\scriptscriptstyle E}}_{n}$, we have
$\langle U_{n}^{\scriptscriptstyle E},v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{n}\rangle=\langle U_{n}^{\scriptscriptstyle
E}-\operatorname{D}\operatorname{\Pi}(X_{n}^{\scriptscriptstyle
E})U_{n}^{\scriptscriptstyle E},v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{n}\rangle$. Let $\mathcal{H}=\\{n\leq
T\\}\cap\\{X_{n}^{\scriptscriptstyle
E}\in\mathcal{Q}^{\scriptscriptstyle{\scriptscriptstyle E}}\\}.$ By
Proposition B.1Item 4, Cauchy-Schwartz, and Assumption 3, we get

$\displaystyle\operatorname{\mathds{1}}_{\mathcal{H}}\operatorname{\mathbb{E}}\left[[\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})U_{n}^{\scriptscriptstyle
E}]_{+}|\mathcal{F}_{n}\right]$ $\displaystyle\geq
c_{1}\operatorname{\mathds{1}}_{\mathcal{H}}\operatorname{\mathbb{E}}\left[\lVert
U_{n}^{\scriptscriptstyle
E}-\operatorname{D}\operatorname{\Pi}(X_{n}^{\scriptscriptstyle
E})U_{n}^{\scriptscriptstyle E}\rVert|\mathcal{F}_{n}\right]$
$\displaystyle\geq
c_{1}\operatorname{\mathds{1}}_{\mathcal{H}}\operatorname{\mathbb{E}}\left[[\langle
U_{n}^{\scriptscriptstyle
E}-\operatorname{D}\operatorname{\Pi}(X_{n}^{\scriptscriptstyle
E})U_{n}^{\scriptscriptstyle E},v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{n}\rangle]_{+}|\mathcal{F}_{n}\right]$
$\displaystyle=c_{1}\operatorname{\mathds{1}}_{\mathcal{H}}\operatorname{\mathbb{E}}\left[[\langle
U_{n}^{\scriptscriptstyle E},v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{n}\rangle]_{+}|\mathcal{F}_{n}\right]$
$\displaystyle=c_{1}\operatorname{\mathds{1}}_{\mathcal{H}}\operatorname{\mathbb{E}}\left[[\langle
U_{n},v_{n}\rangle_{\scriptscriptstyle X_{n}}]_{+}|\mathcal{F}_{n}\right]$
(B.59)

where $v_{n}$ is the _pullback_ of $v^{\scriptscriptstyle{\scriptscriptstyle
E}}_{n}$ under $\iota$. Since $\iota$ is an isometry, the pullback preserves
the inner product, and therefore

$\displaystyle\operatorname{\mathds{1}}_{\mathcal{H}}\operatorname{\mathbb{E}}\left[[\operatorname{D}\eta^{\scriptscriptstyle{\scriptscriptstyle
E}}(X_{n}^{\scriptscriptstyle E})U_{n}^{\scriptscriptstyle
E}]_{+}|\mathcal{F}_{n}\right]\geq
c_{1}\zeta\operatorname{\mathds{1}}_{\mathcal{H}}$ (B.60)

by Assumption 3. Combining Eqs. B.53, B.56, B.57 and B.60 then gives

$\operatorname{\mathbb{E}}[[Y_{n+1}]_{+}|\mathcal{F}_{n}]\geq
c_{1}\zeta\gamma_{n}-k^{\prime\prime}\gamma_{n}^{2}.$ (B.61)

On the other hand, we always have
$\operatorname{\mathbb{E}}[Y^{2}_{n+1}|\mathcal{F}_{n}]\geq\operatorname{\mathbb{E}}[[Y_{n+1}]_{+}|\mathcal{F}_{n}]^{2}$
by Jensen. It then follows that
$\operatorname{\mathbb{E}}[Y^{2}_{n+1}|\mathcal{F}_{n}]\geq
b_{1}\gamma_{n}^{2}$ for some $b_{1}>0$ and large enough $n$ as desired.

We have now verified conditions Items 1–4 in Lemma B.1. Thus, Lemma B.1
concludes that

$\operatorname{\mathbb{P}}(\lim\nolimits_{n\to\infty}S_{n}=0)=0$ (B.62)

which finishes the proof for the case of $\sum_{n}\gamma_{n}^{2}<\infty$.

####  Case 2: Non-square-summable step-sizes
($\sum_{n}\gamma_{n}^{2}=\infty$).

When $\sum_{n}\gamma_{n}^{2}=\infty$, the same proof above shows that
$\operatorname{\mathbb{E}}[Y^{2}_{n+1}|\mathcal{F}_{n}]\geq
b_{1}\gamma_{n}^{2}$ for some $b_{1}>0$ and large enough $n$. Combining this
with (B.55) yields

$\operatorname{\mathbb{E}}[S_{n+1}^{2}-S_{n}^{2}|\mathcal{F}_{n}]\geq
c\gamma_{n}^{2}$ (B.63)

for some $c>0$. Lemma B.2 then implies that

$\operatorname{\mathbb{P}}(\lim\nolimits_{n\to\infty}S_{n}=0)=0$ (B.64)

and our claim follows. ∎

###  B.3. Proof of Proposition 1

We conclude this appendix with the application of Theorem 1 to Algorithms 1–5
under the explicit oracle assumptions of Proposition 1. For convenience, we
restate the relevant result below:

See 1

######  Remark.

In additional to the claimed Algorithms 1–5, we will further prove the same
conclusion for the two algorithms considered in Appendix A.

###### Proof.

By Theorem 1, it suffices to verify Assumption 3 under (17) and the event
$\operatorname{dist}(X_{n},\mathcal{S})\to 0$. We proceed method by method.

####  Algorithm 1.

Since $b_{n}=0$ in Algorithm 1, Assumption 3 holds trivially by (17).

####  Algorithms 2, 3 and 5.

By definition, ${\mathcal{R}}_{x}(z)$ is a smooth map and hence satisfies
$\lim_{z\to 0}{\mathcal{R}}_{x}(z)=x$. On the event
$\operatorname{dist}(X_{n},\mathcal{S})\to 0$, we have
$v(X_{n})+U_{n}+b_{n}=\operatorname{\mathcal{O}}(1)$, and therefore $X_{n+1}$
lies in the injectivity radius of $X_{n}$ with probability 1 for $n$ large
enough. As a result, the mapping $\log_{X_{n}}(X_{n+1})$ is well-define for
all $n$ large enough.

We first consider Algorithms 2 and 5 whose proofs are identical since they are
both are the form:

$\displaystyle X_{n+1}$
$\displaystyle={\mathcal{R}}_{X_{n}}(\gamma_{n}V(X_{n};\theta_{n})).$ (B.65)

Let $\tilde{v}_{n}\in\mathcal{T}_{X_{n}}\mathcal{M}$ be the vector such that
$\exp_{\scriptscriptstyle X_{n}}\left(\gamma_{n}\tilde{v}_{n}\right)=X_{n+1}$,
i.e.,

$\gamma_{n}\tilde{v}_{n}=\log_{\scriptscriptstyle
X_{n}}\Big{(}{\mathcal{R}}_{X_{n}}(\gamma_{n}V(X_{n};\theta_{n}))\Big{)}.$
(B.66)

Then (B.65) is an RRM scheme with $W_{n}=\tilde{v}_{n}-v(X_{n})$ where
$\tilde{v}_{n}$ is defined in (B.66).

Now, consider the curve
$c(t)\coloneqq{\mathcal{R}}_{X_{n}}(tV(X_{n};\theta_{n}))$. By (17), on the
event $\operatorname{dist}(X_{n},\mathcal{S})\to 0$, the curve $c(t)$ lies in
the injectivity radius of $X_{n}$ almost surely for all $t\in[0,\gamma_{n}]$
and all $n$ large enough. Let $\hat{c}(t)$ be the smooth curve of $c(t)$ in
the normal coordinate with base $X_{n}$ and an arbitrary orthonormal frame,
and let $\hat{X}_{n+1}$ be the normal coordinate of $X_{n+1}$. Also, let
$\tilde{v}_{n}^{\mathrm{N}}$ be the (Euclidean) vector of $\tilde{v}_{n}$
expanded in the chosen orthonormal basis, and define
$V^{\mathrm{N}}(X_{n};\theta_{n})$ and
$\operatorname{err}^{\mathrm{N}}(X_{n};\theta_{n})$ similarly. By definition,
$\hat{X}_{n+1}$ is nothing but $\gamma_{n}\tilde{v}_{n}^{\mathrm{N}}$. In
addition, by (17), we have

$\displaystyle\lVert\operatorname{err}^{\mathrm{N}}(X_{n};\theta_{n})\rVert=\lVert\operatorname{err}(X_{n};\theta_{n})\rVert_{\scriptscriptstyle
X_{n}}\leq\sigma$ (B.67)

for some $\sigma<\infty$.

Since $X_{n}=c(0)$ and $X_{n+1}=c(\gamma_{n})$, by properties of a retraction
map we must have

$\displaystyle\gamma_{n}\tilde{v}_{n}^{\mathrm{N}}$
$\displaystyle=\hat{c}(\gamma_{n})$
$\displaystyle=\hat{c}(0)+\gamma_{n}\dot{\hat{c}}(0)+\operatorname{\mathcal{O}}\left(\gamma_{n}^{2}\lVert\dot{\hat{c}}(0)\rVert_{2}^{2}\right)$
$\displaystyle=\gamma_{n}V^{\mathrm{N}}(X_{n};\theta_{n})+\operatorname{\mathcal{O}}\left(\gamma_{n}^{2}\lVert
V(X_{n};\theta_{n})\rVert_{\scriptscriptstyle X_{n}}^{2}\right)$
$\displaystyle\eqqcolon\gamma_{n}V^{\mathrm{N}}(X_{n};\theta_{n})+\gamma_{n}\tilde{b}_{n}$
(B.68)

where $\tilde{b}_{n}=\operatorname{\mathcal{O}}\left(\gamma_{n}\lVert
V(X_{n};\theta_{n})\rVert_{\scriptscriptstyle
X_{n}}^{2}\right)=\operatorname{\mathcal{O}}(\gamma_{n})$. Therefore,

$\left\lVert b_{n}\right\rVert_{\scriptscriptstyle
X_{n}}=\left\lVert\operatorname{\mathbb{E}}\left[W_{n}\nonscript\,\middle|\nonscript\,\mathopen{}\mathcal{F}_{n}\right]\right\rVert_{\scriptscriptstyle
X_{n}}=\left\lVert\operatorname{\mathbb{E}}\left[\tilde{b}_{n}\nonscript\,\middle|\nonscript\,\mathopen{}\mathcal{F}_{n}\right]\right\rVert=\operatorname{\mathcal{O}}\left(\gamma_{n}\right)$
(B.69)

which proves the condition for $b_{n}$ in Assumption 3. On the other hand,
(B.68) shows that

$\displaystyle\lVert U_{n}\rVert_{\scriptscriptstyle X_{n}}$
$\displaystyle\leq\lVert
V^{\mathrm{N}}(X_{n};\theta_{n})+\tilde{b}_{n}\rVert+\lVert\operatorname{\mathbb{E}}\left[V^{\mathrm{N}}(X_{n};\theta_{n})+\tilde{b}_{n}\right]\rVert$
$\displaystyle=\operatorname{\mathcal{O}}(1)$

since $\lVert
V^{\mathrm{N}}(X_{n};\theta_{n})\rVert=\operatorname{\mathcal{O}}(1)$ by (17)
and $\tilde{b}_{n}=\operatorname{\mathcal{O}}(\gamma_{n})$. Finally, for any
unit vector $z\in\mathcal{T}_{X_{n}}\mathcal{M}$, (B.68) implies

$\displaystyle\operatorname{\mathbb{E}}[[\langle
z,U_{n}\rangle_{\scriptscriptstyle X_{n}}]_{+}]$
$\displaystyle\geq\operatorname{\mathbb{E}}[[\langle
z,\operatorname{err}(X_{n};\theta_{n})\rangle_{\scriptscriptstyle
X_{n}}]_{+}]-\lVert\tilde{b}_{n}\rVert$
$\displaystyle=\operatorname{\mathbb{E}}[[\langle
z,\operatorname{err}(X_{n};\theta_{n})\rangle_{\scriptscriptstyle
X_{n}}]_{+}]-\operatorname{\mathcal{O}}(\gamma_{n}).$ (B.70)

Since $\gamma_{n}\to 0$, this finishes the proof of Algorithms 2 and 5. For
Algorithm 3, an Euclidean oracle of the form (17) translates to a Riemannian
oracle with
$\operatorname{err}^{\prime}(x;\theta)\coloneqq\nabla^{2}h(x)^{-1}\operatorname{err}(x;\theta)$.
It then suffices to note that, on the event
$\operatorname{dist}(X_{n},\mathcal{S})\to 0$, $\nabla^{2}h(X_{n})$ is both
upper and lower bounded.

####  Algorithms 4, 6 and 7.

For (RSEG),
$U_{n}=\Gamma_{#1\to#2}(\operatorname{err}(X_{n}^{+};\theta_{n}^{+}))$ so

$\left\lVert U_{n}\right\rVert_{\scriptscriptstyle
X_{n}}=\left\lVert\operatorname{err}(X_{n}^{+};\theta_{n}^{+})\right\rVert_{\scriptscriptstyle
X_{n}^{+}}\leq\sigma$ (B.71)

by (17) and the fact that the parallel transport map is a linear isometry. For
the bias term, the definition of (RSEG) yields

$\lVert
b_{n}\rVert=\lVert\Gamma_{#1\to#2}(v(X_{n}^{+}))-v(X_{n})\rVert_{\scriptscriptstyle
X_{n}}\leq L\operatorname{dist}\left(X_{n}^{+},X_{n}\right)=\gamma_{n}L\lVert
V(X_{n};\theta_{n})\rVert_{\scriptscriptstyle
X_{n}}=\operatorname{\mathcal{O}}(1)$ (B.72)

by the same argument as for Algorithms 2, 3 and 5.

For (ROG), we have
$U_{n}=\Gamma_{#1\to#2}(\operatorname{err}(X_{n};\theta_{n}^{+}))$ and
$b_{n}=\Gamma_{#1\to#2}(v(X_{n}^{+}))-v(X_{n})$, so Assumption 3 can be
checked exactly as in the case of Algorithm 7 above. The analysis for
Algorithm 6 is similar so we omit the details. ∎

## References

  * Abraham & Marsden [2008] Abraham, R. and Marsden, J. E.  _Foundations of mechanics_.  Number 364. American Mathematical Soc., 2008.
  * Absil et al. [2008] Absil, P.-A., Mahony, R., and Sepulchre, R.  _Optimization Algorithms on Matrix Manifolds_.  Princeton University Press, 2008.
  * Alvarez et al. [2004] Alvarez, F., Bolte, J., and Brahic, O.  Hessian Riemannian gradient flows in convex programming.  _SIAM Journal on Control and Optimization_ , 43(2):477–501, 2004.
  * Amari [1998] Amari, S.-I.  Natural gradient works efficiently in learning.  _Neural computation_ , 10(2):251–276, 1998.
  * Antonakopoulos et al. [2020] Antonakopoulos, K., Belmega, E. V., and Mertikopoulos, P.  Online and stochastic optimization beyond Lipschitz continuity: A Riemannian approach.  In _ICLR ’20: Proceedings of the 2020 International Conference on Learning Representations_ , 2020.
  * Antonakopoulos et al. [2022] Antonakopoulos, K., Mertikopoulos, P., Piliouras, G., and Wang, X.  AdaGrad avoids saddle points.  In _ICML ’22: Proceedings of the 39th International Conference on Machine Learning_ , 2022.
  * Azizian et al. [2022] Azizian, W., Iutzeler, F., Malick, J., and Mertikopoulos, P.  On the rate of convergence of Bregman proximal methods in constrained variational inequalities.  http://arxiv.org/abs/2211.08043, 2022.
  * Bauschke et al. [2017] Bauschke, H. H., Bolte, J., and Teboulle, M.  A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications.  _Mathematics of Operations Research_ , 42(2):330–348, May 2017.
  * Beck & Teboulle [2003] Beck, A. and Teboulle, M.  Mirror descent and nonlinear projected subgradient methods for convex optimization.  _Operations Research Letters_ , 31(3):167–175, 2003.
  * Benaïm [1999] Benaïm, M.  Dynamics of stochastic approximation algorithms.  In Azéma, J., Émery, M., Ledoux, M., and Yor, M. (eds.), _Séminaire de Probabilités XXXIII_ , volume 1709 of _Lecture Notes in Mathematics_ , pp. 1–68. Springer Berlin Heidelberg, 1999.
  * Benaïm & Hirsch [1995] Benaïm, M. and Hirsch, M. W.  Dynamics of Morse-Smale urn processes.  _Ergodic Theory and Dynamical Systems_ , 15(6):1005–1030, December 1995.
  * Benaïm & Hirsch [1996] Benaïm, M. and Hirsch, M. W.  Asymptotic pseudotrajectories and chain recurrent flows, with applications.  _Journal of Dynamics and Differential Equations_ , 8(1):141–176, 1996.
  * Benveniste et al. [1990] Benveniste, A., Métivier, M., and Priouret, P.  _Adaptive Algorithms and Stochastic Approximations_.  Springer, 1990.
  * Bertsekas & Tsitsiklis [2000] Bertsekas, D. P. and Tsitsiklis, J. N.  Gradient convergence in gradient methods with errors.  _SIAM Journal on Optimization_ , 10(3):627–642, 2000.
  * Bianchi et al. [2021] Bianchi, P., Hachem, W., and Schechtman, S.  Stochastic subgradient descent escapes active strict saddles on weakly convex functions.  _arXiv preprint arXiv:2108.02072_ , 2021.
  * Bomze et al. [2019] Bomze, I. M., Mertikopoulos, P., Schachinger, W., and Staudigl, M.  Hessian barrier algorithms for linearly constrained optimization problems.  _SIAM Journal on Optimization_ , 29(3):2100–2127, 2019.
  * Bonnabel [2013] Bonnabel, S.  Stochastic gradient descent on Riemannian manifolds.  _IEEE Trans. Autom. Control_ , 58(9):2217–2229, September 2013.
  * Borkar [2008] Borkar, V. S.  _Stochastic Approximation: A Dynamical Systems Viewpoint_.  Cambridge University Press and Hindustan Book Agency, 2008.
  * Boumal [2022] Boumal, N.  _An introduction to optimization on smooth manifolds_.  https://www.nicolasboumal.net/book/, 2022.
  * Brandière & Duflo [1996] Brandière, O. and Duflo, M.  Les algorithmes stochastiques contournent-ils les pièges ?  _Annales de l’Institut Henri Poincaré, Probabilités et Statistiques_ , 32(3):395–427, 1996.
  * Choromanska et al. [2015] Choromanska, A., Henaff, M., Mathieu, M., Ben Arous, G., and LeCun, Y.  The loss surfaces of multilayer networks.  In _AISTATS ’15: Proceedings of the 18th International Conference on Artificial Intelligence and Statistics_ , 2015.
  * Criscitiello & Boumal [2019] Criscitiello, C. and Boumal, N.  Efficiently escaping saddle points on manifolds.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Davis et al. [2021] Davis, D., Drusvyatskiy, D., and Jiang, L.  Subgradient methods near active manifolds: saddle point avoidance, local convergence, and asymptotic normality.  _arXiv preprint arXiv:2108.11832_ , 2021.
  * Duistermaat [2001] Duistermaat, J. J.  On Hessian Riemannian structures.  _Asian Journal of Mathematics_ , 5:79–91, 2001.
  * Ferreira & Oliveira [2002] Ferreira, O. and Oliveira, P.  Proximal point algorithm on Riemannnian manifolds.  _Optimization_ , 51(2):257–270, 2002.
  * Ge et al. [2015] Ge, R., Huang, F., Jin, C., and Yuan, Y.  Escaping from saddle points – Online stochastic gradient for tensor decomposition.  In _COLT ’15: Proceedings of the 28th Annual Conference on Learning Theory_ , 2015.
  * Hirsch [1976] Hirsch, M. W.  _Differential Topology_.  Springer-Verlag, Berlin, 1976.
  * Hou et al. [2020] Hou, T. Y., Li, Z., and Zhang, Z.  Analysis of asymptotic escape of strict saddle sets in manifold optimization.  _SIAM Journal on Mathematics of Data Science_ , 2(3):840–871, 2020.
  * Hsieh et al. [2021] Hsieh, Y.-P., Mertikopoulos, P., and Cevher, V.  The limits of min-max optimization algorithms: Convergence to spurious non-critical sets.  In _International Conference on Machine Learning_ , pp. 4337–4348. PMLR, 2021.
  * Jin et al. [2017] Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., and Jordan, M. I.  How to escape saddle points efficiently.  In _International conference on machine learning_ , pp. 1724–1732. PMLR, 2017.
  * Juditsky et al. [2011] Juditsky, A., Nemirovski, A. S., and Tauvel, C.  Solving variational inequalities with stochastic mirror-prox algorithm.  _Stochastic Systems_ , 1(1):17–58, 2011.
  * Kakade [2001] Kakade, S. M.  A natural policy gradient.  _Advances in neural information processing systems_ , 14, 2001.
  * Karimi et al. [2022a] Karimi, M. R., Hsieh, Y.-P., Mertikopoulos, P., and Krause, A.  The dynamics of Riemannian Robbins-Monro algorithms.  In _COLT ’22: Proceedings of the 35th Annual Conference on Learning Theory_ , 2022a.
  * Karimi et al. [2022b] Karimi, M. R., Hsieh, Y.-P., Mertikopoulos, P., and Krause, A.  The dynamics of Riemannian Robbins-Monro algorithms.  In _COLT 2022-35th Annual Conference on Learning Theory_ , pp. 1–31, 2022b.
  * Kawaguchi [2016] Kawaguchi, K.  Deep learning without poor local minima.  In _NIPS ’16: Proceedings of the 30th International Conference on Neural Information Processing Systems_ , 2016.
  * Kiefer & Wolfowitz [1952] Kiefer, J. and Wolfowitz, J.  Stochastic estimation of the maximum of a regression function.  _The Annals of Mathematical Statistics_ , 23(3):462–466, 1952.
  * Kobayashi & Nomizu [1996] Kobayashi, S. and Nomizu, K.  _Foundations of Differential Geometry_.  Wiley Classics Library. Wiley, 2 edition, 1996.
  * Korpelevich [1976] Korpelevich, G. M.  The extragradient method for finding saddle points and other problems.  _Èkonom. i Mat. Metody_ , 12:747–756, 1976.
  * Kushner & Clark [1978] Kushner, H. J. and Clark, D. S.  _Stochastic Approximation Methods for Constrained and Unconstrained Systems_.  Springer, 1978.
  * Kushner & Yin [1997] Kushner, H. J. and Yin, G. G.  _Stochastic approximation algorithms and applications_.  Springer-Verlag, New York, NY, 1997.
  * Lee et al. [2016] Lee, J. D., Simchowitz, M., Jordan, M. I., and Recht, B.  Gradient descent only converges to minimizers.  In _29th Annual Conference on Learning Theory_ , pp. 1246–1257, 2016.
  * Lee et al. [2019] Lee, J. D., Panageas, I., Piliouras, G., Simchowitz, M., Jordan, M. I., and Recht, B.  First-order methods almost always avoid strict saddle points.  _Mathematical programming_ , 176:311–337, 2019.
  * Lee [1997] Lee, J. M.  _Riemannian Manifolds: an Introduction to Curvature_.  Number 176 in Graduate Texts in Mathematics. Springer, 1997.
  * Lee [2003] Lee, J. M.  _Introduction to Smooth Manifolds_.  Number 218 in Graduate Texts in Mathematics. Springer-Verlag, New York, NY, 2003.
  * Mertikopoulos & Sandholm [2018] Mertikopoulos, P. and Sandholm, W. H.  Riemannian game dynamics.  _Journal of Economic Theory_ , 177:315–364, September 2018\.
  * Mertikopoulos et al. [2020] Mertikopoulos, P., Hallak, N., Kavis, A., and Cevher, V.  On the almost sure convergence of stochastic gradient descent in non-convex problems.  In _NeurIPS ’20: Proceedings of the 34th International Conference on Neural Information Processing Systems_ , 2020.
  * Mertikopoulos et al. [2023] Mertikopoulos, P., Hsieh, Y.-P., and Cevher, V.  A unified stochastic approximation framework for learning in games.  _Mathematical Programming_ , forthcoming, 2023.
  * Meyer et al. [2011] Meyer, G., Bonnabel, S., and Sepulchre, R.  Linear regression under fixed-rank constraints: a riemannian approach.  In _28th International Conference on Machine Learning_ , 2011.
  * Nemirovski & Yudin [1983] Nemirovski, A. S. and Yudin, D. B.  _Problem Complexity and Method Efficiency in Optimization_.  Wiley, New York, NY, 1983.
  * Nesterov [2004] Nesterov, Y.  _Introductory Lectures on Convex Optimization: A Basic Course_.  Number 87 in Applied Optimization. Kluwer Academic Publishers, 2004.
  * Neto et al. [2016] Neto, J. C., Santos, P., and Soares, P.  An extragradient method for equilibrium problems on Hadamard manifolds.  _Optimization Letters_ , 10(6):1327–1336, 2016\.
  * Oja [1992] Oja, E.  Principal components, minor components, and linear neural networks.  _Neural networks_ , 5(6):927–935, 1992.
  * Panageas et al. [2019] Panageas, I., Piliouras, G., and Wang, X.  First-order methods almost always avoid saddle points: The case of vanishing step-sizes.  In _Advances in Neural Information Processing Systems_ , pp. 6471–6480, 2019.
  * Pemantle [1990] Pemantle, R.  Nonconvergence to unstable points in urn models and stochastic aproximations.  _Annals of Probability_ , 18(2):698–712, April 1990.
  * Pemantle [1992] Pemantle, R.  Vertex-reinforced random walk.  _Probability Theory and Related Fields_ , 92:117–136, 1992\.
  * Popov [1980] Popov, L. D.  A modification of the Arrow–Hurwicz method for search of saddle points.  _Mathematical Notes of the Academy of Sciences of the USSR_ , 28(5):845–848, 1980.
  * Rakhlin & Sridharan [2013] Rakhlin, A. and Sridharan, K.  Online learning with predictable sequences.  In _COLT ’13: Proceedings of the 26th Annual Conference on Learning Theory_ , 2013.
  * Raskutti & Mukherjee [2015] Raskutti, G. and Mukherjee, S.  The information geometry of mirror descent.  _IEEE Transactions on Information Theory_ , 61(3):1451–1457, 2015.
  * Robbins & Monro [1951] Robbins, H. and Monro, S.  A stochastic approximation method.  _Annals of Mathematical Statistics_ , 22:400–407, 1951\.
  * Rockafellar [1970] Rockafellar, R. T.  _Convex Analysis_.  Princeton University Press, Princeton, NJ, 1970.
  * Rockafellar & Wets [1998] Rockafellar, R. T. and Wets, R. J. B.  _Variational Analysis_ , volume 317 of _A Series of Comprehensive Studies in Mathematics_.  Springer-Verlag, Berlin, 1998.
  * Shapiro et al. [2009] Shapiro, A., Dentcheva, D., and Ruszczyński, A.  _Lectures on Stochastic Programming_.  Society for Industrial and Applied Mathematics, Philadelphia, PA, 2009\.
  * Shub [1987] Shub, M.  _Global Stability of Dynamical Systems_.  Springer-Verlag, Berlin, 1987.
  * Sra & Hosseini [2015] Sra, S. and Hosseini, R.  Conic geometric optimization on the manifold of positive definite matrices.  _SIAM Journal on Optimization_ , 25(1):713–739, 2015.
  * Sun et al. [2016] Sun, J., Qu, Q., and Wright, J.  Complete dictionary recovery over the sphere ii: Recovery by riemannian trust-region method.  _IEEE Transactions on Information Theory_ , 63(2):885–914, 2016.
  * Sun et al. [2019] Sun, Y., Flammarion, N., and Fazel, M.  Escaping from saddle points on riemannian manifolds.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Tang & Huang [2012] Tang, G.-j. and Huang, N.-j.  Korpelevich’s method for variational inequality problems on Hadamard manifolds.  _Journal of Global Optimization_ , 54(3):493–509, 2012.
  * Zhou et al. [2020] Zhou, Z., Mertikopoulos, P., Bambos, N., Boyd, S. P., and Glynn, P. W.  On the convergence of mirror descent beyond stochastic convex programming.  _SIAM Journal on Optimization_ , 30(1):687–716, 2020.

  *[RRM]: Riemannian Robbins–Monro
  *[APT]: asymptotic pseudotrajectory
  *[SFO]: stochastic first-order oracle
  *[i.i.d.]: independent and identically distributed
  *[RSGD]: Riemannian stochastic gradient descent
  *[]:
  *[Rtr-SGD]: retraction-based stochastic gradient descent
  *[MD]: mirror descent
  *[SMD]: stochastic mirror descent
  *[HR]: Hessian Riemannian
  *[OG]: optimistic gradient
  *[NGD]: natural gradient descent
  *[RPPM]: Riemannian proximal point method
  *[RSEG]: Riemannian stochastic extra-gradient