Riemannian stochastic optimization methods avoid strict saddle points
Authors: Ya-Ping Hsieh
Mohammad Reza Karimi Jaghargh
Andreas Krause
Panayotis Mertikopoulos
Venue: NeurIPS 2023 poster (2023)
Keywords: Riemannian optimization
saddle points
stochastic approximation
TL;DR: Riemannian stochastic optimization methods avoid strict saddle points

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 end state of a stochastic Riemannian algorithm can only be a local minimizer.

Riemannian stochastic optimization methods avoid strict saddle points
Ya-Ping Hsieh,
Mohammad Reza Karimi, Andreas Krause
ETH Zürich mkarimi]@inf ethz. ch, krauseaßethz.co
sepping.hsihl.
Panayotis Mertikopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG 38000 France
banayotis.merrtioooullcooo
Abstract
Many modern machine learning applications - from online principal component analysis to covariance matrix identification and dictionary learning can be formu- lated minimization problems Riemannian manifolds, typically solved with a Riemannian stochastic gradient method (or some variant thereof). However, many cases of interest, the resulting minimization problem is geodesically convex, so the convergence of the chosen solver to a desirable solution i.e., a local minimizer is by means guaranteed. In this paper, study precisely this question, that is, whether stochastic Riemannian optimization algorithms are guaranteed avoid saddle points with probability 1. For generality, we study a family of retraction-basee methods which, in addition to having a potentially much relative 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 as- sumptions 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.
lower per-iteration
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, training algorithm can attain satisfactory performance by simply evading saddle points of the model's loss surface.
This observation has sparked 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:
Q When does given scheme, like stochastic gradient descent, avoid saddle points? Q2: Can we augment a given scheme so that it efficiently escapes saddle points?
Of the above questions, Q) focuses 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, 37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

leading to fairly complete understanding of how and when Euclidean (stochastic) algorithm escapes saddle points, cf. [6, 28, 29, 41, 42, 46, 47, 53, 54] 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 QI and Q2 manifold setting - itself due to a wide range of breakthrough applications to machine learning and data science, from natural language processing, and signal processing dictionary learning and robotics [48, 52, 64, 65J. 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 Qı concern deterministic methods [28, 41, 42, 53] 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 Qi for a broad class of Riemannian stochastic optimization methods including Riemannian stochastic gradient descent, its retraction-basee and/or optimistic variants, etc. Concretely, we focus throughout on a flexible template of Riemannian Robbins-Monro (RRM) schemes [34, 59] 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 submanifold thereof) is zero.
This statement provides firm grounds for accepting the output of a stochastic Riemannian optimization method valid, it shows that saddle points are avoided with probability 1. 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 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 flat, Euclidean setting. The connecting tissue of our analysis with these works is the notion of an asymptotic pseudotrajectory (APT), which allows to couple the long-run behavior of discrete-time RRM methods to that of associated Riemannian gradient flow. [This discrete-to-continne
comparison is crucial for our analysis in order to apply center stable manifold techniques [63] 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 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 brief overview of some basic definitions from Riemmanian geometry and optimiza- tion. 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 comprehensive introduction to the topic.
Le & be a d-dimensional, geodesically complete Riemannian manifold. Throughout the sequel, the tangent space to M at a point x E M will be denoted by M,M, and we will write (t) E Tyy M for the velocity vector to smooth curve y: I - M at time e R. We will also write (x--)x for the metric at x E M. || II for the associated norm, and dist(-.-) for the induced distance function on M, the latter being defined via the minimization of the length functional Lly] [l (yy dt.
We recall here that strict saddle manifold a set critical points each of which at least one negative Hessian eigenvalue. Such manifolds include ridge hypersurfaces and other connected sets of non non-isslated saddle points that are common in the loss landscapes of high dith-ndmminnal machine learning models, so this result has significant cutting power in this regard.

---

Given a point x M and a tangent vector 2 T.M, the (necessarily unique) geodesic emanating from x along will be denoted by Yz, and we define the exponential map at as expx(2) = Yz Y=(1) for all T.M (recall here that M is assumed complete, so this map is well-defined for all x E M and all z M.M). Whenever well-defined, the inverse of expy will be written as log,: M - MrM,, with the understanding that the domain of logx is actually the largest neighborhood of x E M on which the restriction of exp, is a (global) diffcomorphism: by definition, we have log, (exp, (2) = for for which the relevant quantities tangent vector 2 ε M, we will write x (z) for the vector obtained by parallel transporting z along any minimizing geodesic connecting x and x'.
for all well-defined. Finally, given pair of points x, x ε M and
In this general context, we will be interested in solving the Riemannian optimization problem
minimizexe.M
(Opt)
for some smooth objective function f: M R. We will also respectively write
v(x) = fx)
and H(x) == Hess (f (x))
(1)
for the negative (Riemannian) gradient and the (Riemannian) Hessian of f at Finally, in terms of solutions of (Opt), we will focus on the avoidance strict saddle points of f, i.e., points e MM for which
( = and A (H())) <0
(2)
where Amin denotes the minimum eigenvalue of the tensor in question. We will also say that smooth compact component (in the sense of manifolds) of critical points of f is a strict saddle manifold if such that all negative eigenvalues of H & E S, are bounded from
there exist constants c₂ above by -c- < O, and any positive eigenvalues (if they exist) are bounded from below by C, > O.
To differentiate the above from the Euclidean setting, when M is real space equipped with the Euclidean metric, we will instead write V f and 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 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 template. The Riemannian Robbins-Monro (RRM) frame- work 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 = expx, (y))
(RRM)
where
1. X, e MM denotes the state of the algorithm at each iteration = 1,
2.
0n E M is surrogate for the (negative) gradient u u(X,) of f at X,, (defined in detail below).
3. Yn is the method's 's step-size (discussed in detail in Section 4).
In the above, the defining element of (RRM) is the sequence of "surrogate gradients" i,, n = 1,2,.... .... so this will be our first object of interest. Formally, letting F, denote the history of X, up to stage n (inclusive), we will write
8, = v(Xn) + U, + bn
where we have defined
Un = En E [r]
and
bn bn 1F. - (X,),
as the random error and the offset of 0, relative to o(X,) respectively. It will also be convenient to introduce the total error Wn = i, - o(X,)) = Un + bn, which captures both random and systematic fluctuations in en and which measures the total deviation of é, from u v(X,).
3

---

Two points are worth noting here: First, in is nor adapted to Fr, so Un is random relative to Fn; on the other hand. b Fr measuuaab,,,, it deterministic relative Fn. This brings us to the second important point regarding e given the systematic offset term b, in E2. the latter should not be seen as the output of gradient oracle for of (x,)). In partieular, bn intended 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 via stochastic first-order oracle (SFO) returning noisy gradients of f at the evaluation point. Formally, following Nesterov [50], an SFO is a black-box mechanism which, when queried at E M, returns a (negative) stochastic gradient of the form
v(x; 0) u(x) err(x;;
(SFO)
where the seed A E O is random variable taking values in some complete probability space O and err(x;; 0) is an umbrella error term capturing all sources of uncertainty the model.
The archetypal example of an SFO occurs when f is itself a stochastic expectation of the form f(x) [xF 8)] for some random function F: M tion framework. In this case, V is typically given by V(x; 0) = -grad_ x F(x; 0), so, under standard assumptions for exchanging differentiation and expectation, we have E1: 0)] v(x). Extrapolat- ing from this basic framework, our only assumption for the moment will be that Exerr(x; 0)] 0; for detailed discussion of the required assumptions for (SFO), see Section 4.
R the so-called stochastic optimiza-
In practice. (SFO) will be queried repeatedly at a sequence of states Xn. = 1, with a different random seed On drawn i.i.d. from O. In this manner, obtain the following specific algorithms as special cases of (RRM):
Algorithm (Riemannian stochastic gradient descent). Following Bonnabel [17], the Riemannian stochastic gradient descent (RSGD) algorithm queries (SFO) at X,, and proceeds as
X = expx, (yn V(X;; 0,))
(RSGD)
As such, (RSGD) can be seen as an RRM scheme with D, = v(X,; or, equivalently, Un err( (er(Xx;e)p) 0n) and b, O.
A key factor limiting the applicability of (RSGD) is that the exponential map expx, (-) could be prohibitively expensive to compute in practice, even for relatively low-dimensional manifolds. On that account, a popular alternative to (RSGD) is to employ retraction map [2. 19]. that is, smooth mapping R: TM- M that agrees with the exponential map up to first order, namely
d
R₂ (0) x
and
Rx(22) = for all (x. z) E T.M.
(Rtr)
di dr
With this machinery in hand, we obtain the following retraction-based variant of (RSGD):
Algorithm (Retraction-basee stochastic gradient descent). By replacing the exponential map in (RSGD) with a retraction, we obtain the retraction-based stochastic gradient descent scheme
X Rx (( 0.)).
(Rt--SGD
This algorithm does not seem immediately related to the RRM template and, indeed, the whole point of introducing 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, (Rt-SGD) can still be expressed as a special case of (RRM) in a fairly straightforward fashion.
To do so, define the
gradient mapping
En = logx, (Rx, (yn (X,, 0w)))
(5)
Yn
with the proviso that the Riemannian logarithm (5) is well-defined (we discuss the conditions under which this holds later in the paper). Under this definition, (Rtr-SGD) can be recast as special case
of (RRM) by running the latter with the surrogate gradient sequence ûn of Eq. (5). To streamline our presentation, we defer the discussion about the inherent error W,, 6 v v(X,) to Appendix A.

---

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 (Stochastic mirror descent). Let be an open convex subset of RM and let h: .M - R be -mmsoooth, strongly convex Legendre function on M,, that is, ||Vh(x)]I - co whenever x - (d( [cf. 60, Chap. 26]. Then, the stochastic mirror descent (SMD) algorithm unfolds as
Xn+1 Px, (yn ((nxiix),))
(SMD)
where V(X,: (n)) is the output of SFO query for fXx,) Xn, and P: P:MMRR RM - M is the so-called prox-mapping associated to h 17-9, 31], viz.
px(g) arg max ma (Vh(x) y.x') - h(x') for all x M.YER*
(6)
where (..)) stands for the ordinary Euclidean inner product in RM,
Now, even though the notation in (SMD) reminiscent of (Rtr-SG), the definition (6) of P does not bear any resemblance to geodesic exponential retraction and, indeed, its origins are starkly different. However, as we show below, P can indeed be seen as a retraction relative to a specific Riemannian structure M, the Hessian Riemannian (HR) metric associated to h [3, 16, 24, 45].
To make this precise, the first step is to note that the basic recursive structure x² Px (v) of (SMD) can be rewritten as
(7) where 1t (y) = max - -x(x)) denotes the convex conjugate of h, and we have used Danskin's theorem [62] to write arg max max.s.M (y.x) h(x)) Vh* Then, if we endow M with the Hessian Riemannian metric g(x) = v>)(x, the Riemannian gradient of f relative to becomes (x) = [V² more generally, given a cotangent (dual) vector y to M at x, the corresponding tangent (primal) vector will be g(x) [v>h(x)] ( "y. In view of this, by inverting the relation 2 = g(x)=1y y. the abstract mirror descent recursion (7) can be rewritten as
x+ =x VH'(((s)V))) + y)
x² (z) (g(x)))
Now, to proceed, consider the curve
y(t) (1z) Ps (1g(x)) A (Vh(x) + +g(())), so, by definition, y(0) x In addition, by direct diffcrentiation, we readily obtain
(9)
y(0) = (V
(10)
where we used the standard identity v2 (Vh(x)) = [v= [9, 61]. This shows that the map
(z) Pa (g(x)z) is, in fact, a retraction, so (SMD) is special case of (Rtr-GGD and hence, of the general stochastic approximation template (RRM).
Remark. Even though elements of the above ideas are implicit in previous works on mirror descent and Hessian Riemannian metrics [3. 16. 58, 68]. to the best of our knowledge, this the first time that (SMD) is formalized as a retraction- based (Hessian) Riemannian scheme.
Algorithm 4 (Riemannian optimistic gradient). 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
x = X,, + yn 1 0n-1)
(OG)
X,+1 = X,, + yn VX,
where, usual, V is SFO for the (negative) gradient ff of f. This idea can then be directly transported to a manifold setting [33], leading to the Riemannian optimistic gradient method
x; expx, (y,, ((
(ROG)
Xn+1 expx, (T (xx;-x, VX 0n))).
Importantly, the recursion (ROG) may be seen as a special case of (RRM) by setting in = (1/yn) -x;-xx, VXxt 0,)) or, equivalently U, = Tx;-xx (err( x;: 0,)) and bn = -x;-x, (o(Xt)) v (.)) We defer the details of this calculation to the Appendix A.
5

---

Algorithm 5 (Natural gradient descent). Our last example concerns the influential natural gradient descent (NGD) method of Amari [4], stochastic optimization scheme for Euclidean spaces, but adapted to the local geometry defined by strictly convex function h. Specifically, NGD queries an SFO and proceeds as
Xnt1 = Xn (gradf()) err( (er(Xx;;0)) 0,))
(NGD)
where gx) = [V2h()]] denotes the Riemannian gradient of f relative to Hessian Riemannian metric g(x) (x) RM It is well known that (NGD) can be seen as retraction- based Riemannian scheme [17], and may thus be integrated directly within the framework (RRM); we defer the details Appendix A. Importantly, (NGD) also includes the celebrated natural policy gradient [32] which plays an important role in reinforcement learning.
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, begin by discussing the technical assumptions that 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 (i) the regularity of f: (ū) the method's step-size sequence yná (ii)) the statistics of the surrogate gradients in entering (RRM); and (iv) the ambient manifold M. Specifically, will require the following:
Assumption 1 (Regularity of f). The function f is C² and v = g is (geodesically) L-Lipschitz, i.e. for all x, E M, we have
||T (xxx)) u(x') [lo(x) Fx (xxx (o(x))lxx s I. dist(xxxx').
(11)
Assumption 2 (Step-size schedule). The step-size sequence yn of (RRM) satisfies
n Yn and Σm
00 1/mm oo for all A (0, 1).
(12)
Assumption (Surrogate gradients). The offset and random error components of 0, satisfy
||alll,, S Cyn-
||U,l,x So,
El[(Un. 11) 5
(13)
for suitable constants C, 0 and for all 2 Tx, ||z|x, I (in the above, all conditions to be interpreted the almost sure sense and [r]+ = max (0, 2} denotes the positive part of r).
Assumption (Injectivity radius). The injectivity radius of M is bounded from below by e > O.
Before proceeding, we discuss the implications and range of validity of each of the above assumptions. Since Assumption is standard, focus the remaining three below:
On Assumption 2. The step-size conditions typically encountered in the analysis of Rob- www.ummmb------ot-suumm---e--eee
MonsMMoro schemes is the 1,2 - 1 Σn y < co, cf. [10, 13, 14, 17, 39, 59] and references therein. This puts hard threshold on the range of allowed step-size schedules at Q ((11n1/2)) any step-size that decays at least as slow as 1/2 cannot be used under the L L' assumption. By contrast, the step-size condition (12) is considerably more lax and can tolerate near-constant step-sizes of the form 7n 1/(log n)) I+& for some & > 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 guaranteed in general without vanishing step-size, cf. [10, 18, 40] and references therein.]
condition En Yn co,

---

On Assumption 3. Three remarks are in order for the noise and offset requirements (13). First, we should note that the condition b, Oy))) is, a priori, implicit, because it depends on the statistics of the feedback sequence in and these may be difficult to estimate in general. However, in most practical applications, this quantity is under the explicis control of the optimizer: partieular, 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 satisfied in many practical cases of interest. For example, when the problem's is objective function admits a finite-sum decomposition of the form f(x) Σ fx) for an ensemble of empirical instances fi, i = I.....N .V (the standard framework for applications to data science and machine learning), Un is typically generated by sampling minibatch of f. which in turn results in an error term of the form U, q (2)) where g(x) .M- - T&M is bounded on all compact subsets of M. Therefore, ||U,,|,, S (X,))xl < a for some constant o for any convergent algorithm (Xn)n-
2 Ç is also standard in the avoid- ance literature [10, 54]. and is substantially weaker than the isotropic condition, which, roughly speaking, requires the noise to have the same L magnitude along all directions in space [26, 30, 54]. Instead, (13) only posits that the noise U, has non-zero component along each direction, and imposes no other restrictions on the statistical profile of the noise.
Finally, the "uniform excitability" condition E[[(Un. 2)x, I+
On Assumption 4. For our last assumption, recall first that the injectivity radius of M at a point x E M is the largest radius for which exp, is a diffeomorphism onto its image; the injectivity radius of 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 Martan-Hadaman 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 Xn, n = 1,2...., be the sequence of states generated by (RRM), and let S be a strict saddle manifold of f. Then, under Assumptions 1-4, we have
P( Xn) - 0 as n n -o)= =0
(14)
where dS X,) infxes x dist(x. X,) denotes the (Riemannian) distance of Xn, from 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 [10. 12], 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 R" 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 saddle point; other than that, the magnitude of the noise must be proportional to the solver's '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 (RSGD) 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 simultaneously complements the stochastic analysis of [10, 12] to Riemannian problems, and the Riemannian analysis of [22, 66) to 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 hege-level description of our proof strategy and then encode the main arguments in a series of steps right after.
7

---

For the purposes of illustration, suppose that M is subset of R".. Then, given a tangent vector z TxM, we define the geodesic offset (see Fig. 1) from x along 2 as
A(x; 2) = exp, -x--
(15)
i.c., as the difference between the geodesic emanating from x along z and its first-order approximation relative to x in the ambient space R" (with all differences expressed in the ordinary vector space structure of ) The offset A(x; 2) is readily checked to be second-order in Z so, while the curve x+ rz does not in general induce retraction on the target manifold M (in particular, the point x + i2 may not even belong to M). the converse true: the map expx(z) is always a retraction on the ambient, Euclidean space RT In this way, the basic iteration (RRM) can be expressed as
Xn+1 expx, (yn0n) Xn Yn + Pn)
(16)
leading to the fundamental question below:
What is the maximum offset en == A(X;; 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 6, under (RRM) under 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 strict saddle point of f. By the stable manifold theorem [63], the set of all initializations such that the Riemannian gradient flow
*(1) -rad (x(())
(RGF)
converges to f is of measure O. Then, assuming for the moment that the geodesic offset error 6n, A(X;; 7,) 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 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 Tn
-- k= Ys and the associated geodesic interpolation (()) of X, as
X() = expx, (11 - (,)) for all r E [Tn, Tm+1), n 2
(GI)
so, by construction, (a) X(TT,) X,, for all n; and (b) each segment of X(t) is a geodesic. Then, letting d: R, x M + M denote the flow of (RGF) - i.c. (x) is simply the position at time h 2 0 of the solution orbit of (RGF) that starts at x M we will say that X(1) is an APT of (RGF) if, for all T > O, we have
lim, suPoshst dist( X(1 + h). D (x())) =0.
(APT)
This requirement is non-trivial, and our first technical result is to guarantee precisely this: Theorem Suppose that Assumptions 2-4 hold. Then, with probability 1, the geodesic interpolation X()) of the sequence of iterates X,, 1.2. .... generated by (RRM) is an APT of (RGF).
A version of Theorem 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 yu (square summability) but, on the other hand, it only posits that the noise increments Un are bounded in 1.2 (as opposed to 1 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 From Riemannian to Euelidean schemes (and back). Albeit crucial, the APT property is decidedly not enough to guarantee avoidance: after all, the constant orbit X(r) 2 for all / 2 0 is trivially an APT of (RGF) but, of course, does not avoid To proceed, we will need to exploit the precise update structure of (RRM) in conjunction with the stable manifold theorem applied to (RGF).
8

---

In the Euclidean case, this is achieved by means of an intricate Lyapunov function argument, originally due to [11]. Our second step is devise a new geometric argument reduce the analysis from an arbitrary intrinsic manifold to an isometrically embedded submanifold of IR" This step is carried out by a combination of the celebrated Nash embedding theorem and a (smooth) Tietze extension argument to rewrite (RRM)
"corrected" Jobbins-Monny scheme on R" that actually evolves on 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 Fu- clidean reframing of (RRM) introduces an intrinsic offset enror E, = A( x 8n which is difficult to analyze in detail (the offset incurred by a retraction on M is of sim- ilar order, the apponentil--eeracciinn distinction is not important at this stage). Our crucial observation here is that, under our blanket assumptions, en is small relative to Yn and, in particular, en O(y)). Thanks to this bound, able leverage series of stochastic bounds originally developed by Pemantle [54] - to show that the probability that these terms will have an adverse effect exiting the center manifold of f is zero (this is also where Assumption 3 comes in). We formalize this in Appendix B; Theorem then follows by putting everything together.
x+
A(r;)) xxx ex)x(2)
TxM
M
Figure 1: The geodesic offise ((x; 2).
Remark. A concept similar to our geodesic offset A(x; has been explored in the reverse direction by the very recent works [15, 23] whose goal was to study of avoidance of Euclidean subgradient methods 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 [15, 23] to handle general RRM schemes, such as retraction-bart 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 I would require mapping the requirements of Assumption the primitives of (SFO). A convenient way achieve this by means of the proposition below:
Proposition 1. Suppose that Algorithms 1-5 are run with gradient oracle Vxx; 0) = v(x) + (xrr(x; 0)
such that
||err(x; 0)lxx S (x)) and [[((er((x;0),)))x14] for all z T.M, || = 1, and for suitable functions o M - RR with o bounded on bounded subsets of M and {x)) 0. Then, under Assumplions 2 and 4, the conclusion of Theorem I holds, that is, Algorithms 1-5 avoid strict saddle manifolds of
(xx)
(17)
The proof of Proposition is deferred to Appendix B; only note here that its proof mainly hinges on verifying the bias requirement ||b, (y))) of (13) by means of ) the boundedness of the error function o (x) on bounded subsets of M; and (ii) controlling the maximal deviation between retraction and the exponential map for input vectors bounded by c.
5 Numerical Illustrations
In this section, we aim to demonstrate the practical applicability of the thcoretical framework proposed in our paper by providing numerical illustrations. To do so, we utilize 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., (RSGD) 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

---

(a) Riemannian stochastic gradient descent
(b) Riemannian stochastic extra- gradient
Figure 2: Stochastic RRM schemes on the torus.
eventually reach the desirable global minimum. This empirical confirmation reinforces the central message of our paper: stochastic Riemannian schemes only converge to local minimizers.
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-Mon 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-basee algorithms. Our framework builds upon the notion of strict saddle points and provides 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 Fuclidean min-max optimization, studied by Hsieh al. [29], to the realm of Rie- mannian games. Investigating the avoidance of unstable limit cycles in this context has the potential uncover novel phenomena specific the manifold settings, leading deeper understanding on the intricate dynamics and strategies involved in Riemannian games.
Acknowledgments and Disclosure of Funding
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, by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program, and by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project the LabEx PERSYVAL ---A----LAB----AA 1--LABX-002--01, and PM is also with the Archimedes Research Unit Athena RC University of Athens. YPH acknowledges funding through an ETH Foundations of Data Science (ETH-FDS) postdoctoral fellowship.
(IRR-33-PEIA-0003) the "Investissements
d'avenir" program 1--R--5-IDEX-AA
MIAI@ Grenoble Alpes 1ANR-19-P31A
10

---

References
[1] Abraham, R. and Marsden, J. E. Foundations of mechanics. Number 364. American Mathematical Soc., 2008.
[2] Absil, P.A.. Mahony, R., and Sepulchre, R. Optimization Algorithms on Mutrix Manifolds. Princeton University Press, 2008.
[3] Alvarez, F., Bolte, J., and Brahic, O. Hessian Riemannian gradient flows in convex programming. SIAM Journal on Control and Optimization, 43(2)4477-501, 2004.
[4] Amari, S.-I Natural gradient works efficiently in learning. Neural computation, (0(2):251-266 1998.
[5] Antonakopoulos, K., Belmega, F. V., and Mertikopoulos, P. Online and stochastic optimization heyond Lipschitz continuity: A Riemannian approach. In ICLR '20: Proceedings of the 2020 International Conference on Learning Representations, 2020.
[6] 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.
[7] Azizian, W., lutzeler, F., Malick, J., and Mertikopoulos, P. On the rate of convergence of Bregman proximal methods in constrained variational inequalities. http://arxiv wrgg 2221 2w1...2210000 08803,, 2022.
[8] 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-344 -38, May 2017.
[9] Beck, A. and Teboulle, M. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 3163):167-775, 2003.
[10] Benaïm, M. Dynamics of stochastic approximation algorithms. Azéma, J., Émery, M., Ledoux, M., and Yor, M. (eds.). Séminaire de Probabilité' XXXIII, volume 1709 of Lecture Notes in Mathematics, pp. 1-68. Springer Berlin Heidelberg, 1999.
[11] Benaim, M. and Hirsch, M. W. Dynamics of Morse-Smale um processes. Ergodic Theory and Dynamical Systems, 1005-10005 December 1995.
[12] Benaim, M. and Hirsch, W. Asymptotic pseudotrajectories and chain recurrent flows, with applications. Journal of Dynamics and Disferential Equations, 8 8(1):141-17, 1996.
[13] Benveniste, A., Métivier, M., and Priouret, P. Adaptive Algoritims and Stochastic Approximations. Springer, 1990.
[14] Bertsekas, D. P. and Tsitsiklis, J. N. Gradient convergence in gradient methods with errors. SIAM Journal on Optimization, 10(3):627-622, 2000.
[15] Bianchi, P., Hachem, W., and Schechtman, S. Stochastic subgradient descent escapes active strict saddles on weakly convex functions. arXiv preprint 10XXiv2208.02000 2021.
[16] 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.
[17] Bonnahel, S. Stochastic gradient descent on Riemannian manifolds. IEEF Trans. Autom. Control, 58()):
2217-2229, September 2013.
[18] Borkar, V. S. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press and Hindustan Book Agency, 2008
[19] Boumal, N. An introduction optimization on smooth manifolds. book/, 2022.
net/
[20] Brandière, O. and Duflo, M. Les algorithmes stochastiques contournent-ils les pièges ? Annales de I'Instita Henri Poincaré, Probabilités et Statistiques, 32(3):395-422 427, 1996.
[21] Choromanska, A., Henaff, M., Mathicu, 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.
[22] Criscitiello. C. and Boumal, N. Efficiently escaping saddle points on manifolds. Advances in Neural Information Processing Systems, 32, 2019.
[23] Davis, D., Drusvyatskiy, D., and Jiang, L. Subgradient methods near active manifolds: saddle point avoidance, local convergence, and asymptotic normality. arXiv preprint arXiv:2108.1 1832, 2021.
[24] Duistermaat, J. J. On Hessian Riemannian structures. Asian Journal of Mathematics, 5:79-91, 2001.
[25] Ferreira, O. and Oliveira, Proximal point algorithm on Riemannnian manifolds. Optimization, 51(2): 257-270, 2002.
[26] 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.
[27] Hirsch, M. W. Differential Topology. Springer-Verlag, Berlin, 1976.
11

---

[28] 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.
[29] Hsieh, Y.-P., Mertikopoulos, P., and Cevher, V. The limits min max optimization algorithms: Conver- gence to spurious non-critical sets, International Conference on Machine Learnnng pp. 4337-4348. PMI.R, 2021.
[30] Jin, C., Ge. R., Netrapalli, P., Kakade, S. M., and Jordan, M. I. How to escape saddle points efficiently. In International conference machine learning, pp. 1724-1732. PMLR, 2017.
[31] Juditsky, A., Nemirovski, A. S., and Tauvel. C. Solving variational inequalities with stochastic mirror-pret prox
algorithm. Stochastic Systems, 1(1):17-58, 2011.
[32] Kakade, S. M. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
[33] Karimi, M. R., Hsieh, Y.PP., Mertikopoulos, P., and Krause, A. The dynamics of Riemannian Robbins-
Monro algorithms. In COLT '22: Proceedings of the 35th Annual Conference on Learning Theory, 2022.
[34] Karimi, M. R., Hsieh, Y.PP., Mertikopoulos, P., and Krause, A. The dynamics of Riemannian Robbins- Monro algorithms. In COLT 2022-35th Annual Conference on Learning Theory. pp- 1-31, 2022.
[35] Kawaguchi, K. Deep learning without poor local minima. In NIPS '16: Proceedings of the 30th International Conference on Neural Information Processing Systems, 2016.
[36] Kiefer. and Wolfowitz, J. Stochastic estimation the maximum of regression function. The Annals of Mathematical Statistics, 23(3):462-466 1952.
[37] Kobayashi, S. and Nomizu, K. Foundations of Differential Geometry. Wiley Classics Library. Wiley, 2 edition, 1996.
[38] Korpelevich, G. M. The extragradient method for finding saddle points and other problems. Ekonom. i Mat. Metody, 12:747-756, 1976.
[39] Kushner, H. J. Clark, D. S. Stochastic Approximation Methods for Constrained and Unconstrained Systems. Springer, 1978.
[40] Kushner, H. J. and Yin, G. G. Stochastic approximation algorithms and applications. Springer-Verlae New York, NY, 1997.
[41] Lee, D.,, Simchowitz, M., Jordan, I., and Recht, B. Gradient descent only converges to minimizers. In 29th Annual Conference on Learning Theory, pp. 1246-1257, 2016.
[42] 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 progranming, 176:311-3311 2019.
[43] Lee. J. M. Riemannian Manifolds: an Introduction to Curvature. Number 176 in Graduate Texts in Mathematics. Springer, 1997.
[44] Lee, M. Introduction to Smooth Manifolds. Number 218 in Graduate Texts in Mathematics. Springer- Verlag, New York, NY, 2003.
[45] Mertikopoulos. P. and Sandholm, W. H. Riemannian game dynamics. Journal of Economic Theory, 177:
315-364. September 2018
[46] Mertikopoulos, Hallak, N., Kavis, A., and Cevher, V. On the almost sure convergence stochastic gra- dient descent in non-convex problems. In NeurlPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[47] Mertikopoulos, P.. Hsieh, Y.PP., and Cevher, V. A unified stochastic approximation framework for learning in games. Mathematical Progranming, forthcoming, 2023.
[48] Meyer, G., Bonnabel, S., and Sepulchre, R. Linear regression under fixed-rank constraints: a riemannian approach. 28th International Conference on Machine Learning, 2011.
[49] Nemirovski, A. S. and Yudin, D. B. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, NY, 1983.
[50] Nesterov, Y. Introductory Lectures on Convex Optimization: A Basic Course. Number 87 in Applied Optimization. Kluwer Academic Publishers, 2004.
[51] Neto, J. C., Santos, P., and Soares, P. An extragradient method for equilibrium problems on Hadamard manifolds. Optimization Letters, 10(6): 1377-136, 2016.
[52] Oja, E. Principal components. minor components, and linear neural networks. Neural networks, 5(6): 927-935, 1992.
[53] 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.
[54] Pemantle, R. Nonconvergence to unstable points in urn models and stochastic aproximations. Annals of Probability, 18(2):698-712, April 1990.
[55] Pemantle, R. fertex-reinforedd random walk. Probability Theory and Related Fields, 92:117-136, 1992.
12

---

[56] Popov, L. D. A modification of the Arrow-Hurwicz method for search of saddle points. Mathematicul Notes the Academy of Sciences the USSR, 28(5):845-848, 1980.
[57] Rakhlin, A. and Sridharan, K. Online learning with predictable sequences. COLT '1: Proceedings of the 26th Annual Conference on Learning Theory, 2013.
[58] Raskutti, G. and Mukherjee, S. The information geometry of mirror descent. IEEE Trunsactions on Information Theory, 61(3):1451-1457, 2015.
[59] Robbins, H. and Monro, A stochastic approximation method. Annals of Mathematical Statistics, 22: 400-407, 1951.
[60] Rockafellar, R. T. Convex Analysis. Princeton University Press, Princeton, NJ, 1970.
[61] Rockafellar, R. T. and Wets, R. J. B. Variational Analysis, volume 317 of A Series of Comprehensive Studies in Mathemuticy. Springer- Opringer-Verlag- Berlin, 1998.
[62] Shapiro, A., Dentcheva, D., and Ruszczyński, A. Lectures Stockastic Programming. Society for Industrial and Applied Mathematics, Philadelphia. PA, 2009.
[63] Shub, M. Global Stability of Dynamical Systems. Springer-Vertee Verlag, Berlin, 1987.
[64] Sra, S. and Hosseini, R. Conic geometric optimization on the manifold of positive definite matrices. SIAM Journal on Optimization, 25(1):713-739 2015.
[65] Sun, J.. Qu, Q.. and Wright. J. Complete dictionary recovery the sphere ii: Recovery by riemannian trust-region method. IEEE Transactions Information Theory, 63(2):8559914 2016.
[66] Sun, Y., Flammarion, N., Fazel, M. Escaping from saddle points on riemannian manifolds. Advances in Neural Information Processing Systems, 32, 2019.
[67] Tang, G.-j. and Huang, N.-j. Korpelevich's s method for variational inequality problems on Hadamard manifolds. Journal of Global Optimization, 54(3)=993550, 2012.
[68] Zhou, Z., Mertikopoulos, P. Bambos, N., Boyd, S. and Glynn, On convergence of mirror descent beyond stochastic convex programming. SIAM Journal Optimization, 30(1):687-776, 2020.
13

---

A Further examples of RRM schemes
In this section, we provide two additional algorithmic examples supplementing the range of Algo- rithms 1-5 to illustrate the applicability of our RRM template.
Algorithm 6 (Riemannian proximal point methods). The (deterministic) Riemannian proximal point method (RPPM) [25] an implicit ("backward")) update rule of the form
logx,.. (X,) =Xnx(XX+1)-
(RPPM)
The RRM representation of (RPPM) is then obtained by taking bn = [ Xmx1-XX (0((n+1)) ((x)) and Un 0 in the decomposition (4) of the error Wn of (RRM). in additional, the true gradient o( v(Xn+1) is replaced by an oracle V(Xn+1; Out1), then (RPPM) becomes the stochastic version of RPPM by setting
bn =[[ Xmxxxxx- xx,
(Vw,VVVXX,,. (V(X=+1: 0+)))) - - v(X,) [FF
and
Un [ - (V(X++1: 0n+1)) v(X,) bn-
For detailed discussion, see [25] and references therein.
Algorithm 7 (Riemannian stochastic strragraddeett. Inspired by the original work Korpelevich [38], the Riemannian stochastic extra-gradee extra-gradient (RSEG) method [51, 67] proceeds
x expx, (yn, VY, (,),
(RSEG)
X expx, (T [xx;- -,, (X,V 0)))
where 6n and 8 are independent seeds for (SFO). Thus, to cast (RSEG) in the RRM framework, it suffices take Un -x (err(X;;; 6)) and b, -xx=-x (v(x;)) u(x,).
Under the assumptions in Proposition 1, one can show that Algorithms 6-7 also avoid strict saddle points f; we provide the relevant details Appendix B.3.
B Missing Proofs of Section
We begin by proving Theorem 2, which will play a crucial role in our proof of Theorem 1. For the reader's convenience, restate the result below:
B.1. Proof of Theorem 2.
Theorem 2. Suppose that Assumptions 2-4 hold. Then, with probability 1, the geodesic interpolation (() of the sequence of iterates X,, n 1, ..., generated by (RRM) is an APT of (RGF).
Proof. To begin, let (e;(1) be an arbitrary sequence of orthonormal bases for M, and let U"! be the (Euclidean) noise vector composed of components the noise Un the basis {e; (e:(n) hist...d viz.
UH = (Un, e, (n))xx.
(B.1)
is then easy see that E[U 0, and, moreover
| ||Un||x o
(B.2)
by Assumption 3. Then, following Benaïm [10], consider the "comtimaous-to-diicreee counter
((r) = sup(n n 2 1
(B.3)
which measures the number of iterations required for the effective time F Σn= y* to reach a given timestamp / 2 O. We further denote the piecewise-constant interpolation of the noise sequence as
("(1)= = U" for all / [TT, Tn+1), n 2
(B.4)
and we let
rth (*(ss as
(I; sup 0sh
(B.5)
Moving forward, since X, - by assumption, we will also have
sup, xi, R <
al
(B.6)
14

---

for some (possibly random) R 2 0. Moreover, since f is assumed to be C², (B.6) implies that
sup,lle(X,]IIx, = G 00
(B.7)
Moreover, since the manifold M is assumed to be smooth, the sectional curvatures at each X,. 11 = 1,2, .... must be likewise bounded by some constant Kmax- Then, by the analysis of [34, Eq. 53], there exists constant CL.GGKmm.d depending only on L, G, Kmax and R such that
for some (possibly random) non-negative constant G
sup dist( (1+ h), (x((())) & CL.GGKMa..R OshsT
sup (lballx,, + + + A(t 1:7'+1 n2M((1
(B.8)
By Assumption 3, have ||b,|xx, = =0(yn). Since yn suffices show that A(;;7) - with probability under Assumptions and 3. This is equivalent to showing that, for any > 0, we have
lim A(::)) with probability 1.
(B.9)
To this end, let n = M()) and recall that, by (B.2), we have
Efexp ((w, (.)) FM & exp o02 for all Rd where d is the dimension of M.. Therefore, for each Rd, the sequence (,)
(B.10)
defined by
@21l112
(w) == exp
Σ w. yu 02)
Σ yk
(B.11)
2
R=1
supermartingale. Since Y, is supermartingale, have
P
sup
(w. y;ū)) 2 6
M
1=n
(w) 2 (w) exp 5 1311111
((
P
sup
Σ
neksMiT.+t
(T++T)-
exp
(B.
2
for any 8' > 0. Now, let e; be the i-th basis vector of Rd. Then, by (B.12), have
k-1
P
sup (T.t)
(+ ynU
=
sup
Σ
(+E
ode yu U2U
nakks((T.
1=
2222 M( M(T
exp
Σ
- 0
(B.13)
26
Optimizing (B.13) over 5, we get
82
sup n<ksMi TT)
(dde 0 2 & S exp
(B.14)
20 > i=n
((
ten
Since Yn - O, with loss of generality we may assume that 7n 1, and hence
k-1 (tde,, vx0%)
P
sup
s exp
F=
2 M
((
Vi
S exp
(B.15)
22 51 7(1)
15

---

where, analogously to (B.4), we have defined the piece-wise constant interpolated step-size sequence for all E [Tn, Tn+1), 1.
7(r)
(B.16)
Since
k-1 3i such that (+de y;U!)) 8.
Σ Y:U
28
(B.17)
by the union bound, we have
8²
8²
P(A(t, 7) 2 8) s 2d exp
$ 2d exp
(B.18)
20d Ji 7(1)
20
for some / $s$1+1 Therefore, by setting d = expl
62
< 1, we have
20----
P(ACKT, 2 8) s 2d
Σ
a 11/2
< 0o
(B.19)
by Assumption 2. The Borel-Cantelli Lemma then implies that the following event happens almost surely:
lim A(KT:T) se. k-20
(B.20)
The proof is finished by noting that, for KT +k+ 1)T,
A(r:T) s 2A(KT; A(KT+
(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:
Theorem 1. Let Xn. 1.2...., be the sequence of states generated by (RRM), and let S be a strict saddle manifold of f. Then, under Assumptions I-4, we have
P(dist(S, Xn)) - 0 as o0) =0
(14)
where dSst(S, X,) infxes dist(x, Xn) denotes the (Riemannian) distance of Xn. from S.
Proof. Assume that x, S. We will show that this event has zero probability series of steps which we outline below.
Isometrically embedded Robbins-Monro iterates. Since M is assumed be smooth, the second Nash embedding theorem [37] implies there exists a smooth and isometric embedding 1 M RM such that, for all E M and all z, w MxM, we have
Step 1:
(z,w)x (D (D),(
(B.22)
Since is embedding, it is surjective. Since it is isometric, preserves distance and hence must be one-to-one. Therefore, is an diffeomorphism since it is also smooth. We can therefore define the pushforward of the vector field on M vector field on the image M R in the usual way as
off (x*)= = Dx.((x)
for all x (xx) E RM
(B.23)
We also set S = (S)..
By the Tietze extension theorem and the smooth manifold extension lemma [44], og (x=) can be extended to Lipschitz continuous vector field on all of RM which we still denote by of (x.). To avoid trivialities, we will also need to ensure that of (x*) is not neighborhood of St: If this the case, then set target field of (x*) := of (x*²;; otherwise, let denote the vector of I's in all coordinates, and define new vector field oF on RM
(x*) (x + dist
(B.24)
where dist" , S*) inf F ES ||x* Il Obviously, this vector field agrees with uf (x*) on ME and therefore is still the pushforward of under Moreover, it is not uniformly 0 in neighborhood of SE [It worth noting that the so-defined vector field of in general not the (Euclidean) gradient of any function, fact which presents significant difficulty our analysis.]
16

---

Step 2: S is an unstable invariant set. Our next goal is to show that there exists an instable neighborhood 4t around 8 in the following sense: First. for each & S, consider its image f = (f) E S Since of agrees with the pushforward of grad under and since is an isometry, we have the following relation for all tangent vector E TTM:
(D D (is(t).
(Hess f(8),, 2)
(B.25)
Since 2 is strict saddle point, (B.25) implies that Amin (D < <cc < O for all 8 E 8 By an
established series of arguments [10, 12, 46), using the stable manifold theorem for a striet saddle [63] and the transversality of the strict saddle manifold [1], there exists (M dimeeniiil embedded submanifold O in RM that contains S [Here, 1 1 m S M, and M -m represents the dimension of the unstable manifold of of.] Moreover, writing of for the flow generated by of, it follows that Q
is locally invariant under Φf. Hence, there exists a neighborhood A of S in RM and a positive time to such that for all |r| s fo. the following inclusion holds:
(NV n Q*) c Q
(B.26)
To proceed, note that RM can be decomposed further as the direct sum of the tangent space to Q" at x" denoted by Txx 2" and an additional complementary subspace denoted by 8
x
RM TxE Q. E...
(B.27)
The mapping x² - ee is continuous, where x varies over S and Eye belongs to the Grassmanian manifold (m,, M). It is important to note that EN contains at least one direction in T.r. T. due to (B.25). Then, for all E R and x E SE, the Jacobian of of evaluated at x maps Eyt to Eu 0f (x
i.e.
Eu (xF)
(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 Df: There exist positive constants c and C such that for all x S A E4 and 1 O, the following inequality holds:
||D (x (= 2 Ce"I[
[|
(B.29)
The above verifies all the conditions for a unstable invariant set for S 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 neighborhood of S", whose construction we outline below.
Local Lyapunov function nf.. For dight-lifferenttabbe function 17;: RM - R we define its right derivative D of applied to a vector h RM by
Step 3:
1f" 1hh) (x
Dn ()" =im r-0"
(B.30)
ry is differentiable, then (B.30) is simply (x"" 1F). ., In view of all this, Benaïm [10] provides the following crucial result:
Proposition B.1 (Benaïm, 1999, Prop. 9.5). There exists compact neighborhood of Sh positive numbers I.B > O, and a map TF UE (SE) - R* such that of (x5)) = 0 if and only if F QF, and the following holds:
(i) nf is C² on U (SF)
(i)) For all X E (SF) n oF admits a right derivative (xFF(x):: RM - RM which is Lipschitz convex and positively homogeneous.
(ii) There exists k > O and a neighhorhood W RM of such that for all x E (S*) and
z E WW
1x + 2 (x²) + Dnf (z * 11
(B.31)
(iv) There exists C₁ 0 such that for all x" E us* \ Q"
|M (Dn (xF)
(B.32)
17

---

where ME is the projection on M In addition, for all x E (S") n Q and z" E RM
2 - -DI(x>)=*
(B.33)
where II is the projection of a neighborhood of S onto Q
(v) For all x e (5") n O", w TT and zth E RM,
Dyf (rffx"") (wF ++²) Dff (x²)
(B.34)
(vi) For all x E EU (SF we have
(x) (x*) 2 Buf (x²).
(B.35)
The function of will serve as local "energy function" that plays an instrumental role in our analysis; the well-posedness of guaranteed by (27, Chap 4].
Step 4: Geodesic offset. Consider the image of an RRM scheme X == ((,)) If X & (SF) for all then there is nothing prove. Otherwise, without loss of generality we may assume that X e 4t (S"). Accordingly, define the first exit time 7 from (5") as
T in k 1: X $ (SF)).
(B.36)
Evidently, T' is a stopping time adaptive to Fu, so it suffices to show that?
P(7 0o) 0.
(B.37)
To this end, notion that plays central role in our analysis is the geodesic offet, defined follows. Define the pushforward of the respective noise and bias vectors in the RRM scheme X,, by
U = Dix, Un. b" == D Dix, bn-
(B.38)
It is important to remember that U Tx.M fact that we will use freely in the sequel.
We now formally define the geodesic offset A(x; z) RM as, for any x E M and E T,M, (xx; = ((exx,
(xx (zx(2).
(B.39)
By Assumption 4, there exists @ such that, for all |||||, < o. the exponential mapping is the unique minimizing geodesic. Furthermore, for all such z's, define the curve y*()) = ((x) + D 1x (z), then
(0)) = (x), (²)) = (z)
(B.40)
so that (1) agrees with the image of the geodesics ((exp, (tz)). As result, for any ||=l|, < we have A(x:)) = 011211)). Now, setting x < Xn and 2 - Yn(o (w)
)) + Un + bn), we have
X X 7a (xx) + U bn) +
(B.41)
where ex A(Xni (n (X,) UU + bn)). By Assumption surely. Moreover, since v is smooth, on the event = co, X E (S*) for all n and therefore supma1llo (X,5)l co. Since Yn for any large enough, we get
know that U5 + +b; 0(1) almost
c Oly.)
(B.42)
Now, define two sequences of random variables (Ynhna1 and (Sm)na1 Y = (x ( 17" (xx)) (nsT) +yn I (n>T),
(B.43a)
So = 1)=)(((()) Sn So + Σ Yk.
(B.43b)
k=1
The importance of these sequences is that the event (T co) is contained in the event (S,, - 0).
n1) To see this, assume T = co. Then we have Yn+1 = 1X - (X,) and Sn = n7"(X,, by Eqs. (B.43a) and (B.43b). In addition, since (Xx) remains in in(""((*) by definition of the stopping time T, Theorem 2 combined with [10, Theorem 5.7] asserts that the limit set L((X;) of (xx) is nonempty compact invariant subset of (EF))).
that for all yf (((XE)) and / E R,
of (1²) E (S*). But then Proposition (vi) implies that ((FFF) 2 of (y for all > 0, forcing (1)) to be zero. Since (x5)= ) 0 if and only if xf E Q² we have L((X)) Q which implies S, = 775(( (X,) - O.
Therefore, the rest of the proof is devoted to showing that P(lim Sn = 0) = 0.
2The original statement in [10] is If 2 c1. The inequality in (B.32) is obtained via the same proof and noting that Exp contains at least one direction in M... Theorem follows from (B.37) because the event (dist(Xn. S) 0} contained in (T = oo).
18

---

Step 5: Probabilistic estimates. To this end, we will need two technical lemmas, originally due to Pemantle [55], and extended their current form by Benaim & Hirsch [12].
Lemma B.1. Let Sn be a nonnegative stochastic process, S, = So + Σ Yx where Yn is Fu measurable. Let on == 2k=n yy. Assume there exist a sequence 0 En ol o()an). constants a1,02 > 0 and an integer No such that for all n 2 No.
(i) | (()a))
(i) (5,>>a)) 1 2 O.
(iii) ESS n+1 Fr a1y
(iv) E[ n+1 [r azy
Then P(lim,,-00 Sn = 0) =.
Lemma B.2. Let Sn be nonnegative stochastic process, Sn So Σi Yx where Yn is Fu
measurable and [Y,] C almost surely for some constant Assume that En Yn co, and there
exists c > Nº E IN such for all 2 N
E n+1 - 11 2 cy.
(B.44)
Then
P lim Sn 0 0.
(B.45)
Our proof will be concluded by verifying all the premises Lemmas B.1-B.2. To that end, note first that the sequence Sn defined in (B.43b) is nonnegative by construction. We will then separate the analysis into two cases:
Case 1. Square-summable step-sizes, i.e., En y In this case, we have
Yn
lim
=0
(B.46)
k== Yk
0
This fact will be used in the proof when we invoke Lemma B. below with 6, OOyn) and an Em-n ye therein. The verification process then proceeds as follows: Verifying Lemma B.1(i) and (iv): By the Lipschitz continuity of 17",, we know that || x 1 xi s L'IIX, x II -Y (x + U b,
000 so Yn V 2 Y
(B.47)
where L'' is the Lipschitz constant of rf. We have seen in the analysis of (B.42) that [X,)(Xx)) U + b1 = 0(1) almost surely by Assumption 3 on the event O(y,) = v()a,) which implies both Lemma Bi) and (iv).
co. Therefore, |Y*+1|
Verifying Lemma B.1(ii): Let k' = || + a where & is given by Proposition B.i and ||=||| sup(u"(x*)) : xx (F*)))) and o is the uniform bound of Un. If s T. using Proposition (ii), (iii), (v) and (vi) we have
7 (Xx,.) 17 (xx)) Z Yn Dn (x;) (x,)) + U, + b,:)
(D kyā + ||
[1b
2 YnBn" (X,) + D (X,""" + DT "T""(X())) (X,) +D (x, 22' 11,
(B.48)
By Assumption 3, there exists a constant c' such that -1 2 -c' yn (a.s.). Combining this with the Lipschitz continuity of 17 and (B.42), we can merge the last four terms in (B.48) as
17 " 17th (X 2 YnBn" (X,) + yn DIy DT 2k"
(B.49)
for some constant k" O. We thus get
1 (ms7) E[Y,.) [F)] 2 1 (ns7) (rnBn (x, 2k" y 2
EDA
(B.50)
19

---

By Proposition (ii again, we have
E[Dn (X, (1 2 Dn
B F =
=f (X,, E[D 5x, Un|
(B.51)
since we have assumed the noise to be zero mean. Combining (B.50) and (B.51), we then get
1 (nST) [[ 2 l1 (nS7) (nm -x y
(B.52)
If n > T, V+1 = so trivially
11 (1S7) H[ [Fn] 0.
(B.53)
Combining (B.52) with (B.53), we see that Lemma B.I satisfied with En B nn-
8"
Verifying Lemma B. Bii(i We begin by observing that
E a+1
= [Fnl] + 2S, E[
(B.54)
Sn, En. then the last term on the right-hand side of (B.54) is non-negative by Lemma B.i that we just verified above. If S, < En. (B.52) with (B.53) imply that S, E[ [Fn] 2 En kr.k",n O. In other words, (B.54) can be rewritten as
ElSa n+1 - 1F 2 E[Y F+ - O(y)).
(B.55)
Below, we shall prove that IF[r2 n+1 [F,x] 2 biy? for some b O and n large enough. Combin- ing this with (B.55) proves Lemma B. (iii). From (B.49), we deduce
1l (nst) E| ((().t))+ 1F5)) (X k" k"y²) 2 0.
(B.56)
We now claim that
(IST))(X(E00) (X5D) 2 ci5.
(B.57)
where ej is given by Proposition (iv and & is defined in Assumption 3. To see this, recall that Ilx by Assumption 3. Moreover, have X (S*) the event 7 co. Proposition (i) then implies of is differentiable on (EEE \ O and Proposition B.1 further shows that
(nST)n(XFe(=) (X)U))
[InSTIn(XEEOO)
E[I (X,) U
[ M (x)5))
2 215
(B.58)
where we have used the fact that U. E Tx,, M" and Assumption 3.
If X Q we can choose unit vector of e (er(I-DII(X5)) nT M where II denotes the projection operator onto Q"; note that op E (AN(IDDI(X (x) M 0 since She contains at least one direction in TM for all x E (S*) n... By the definition of of have (US, of) (U D II (I())) UX og)). Let H (n 7' n (X Q*). By
Proposition B. Biv),,, Cauchy-Schwarde and Assumption 3, we get
1x ( Cı 1x E[IIU - DDI(X [1
C1 1x [ DI(X u 1.1
= ci 1 E (U +
c1 h [U, 1+1F,
(B.59)
where is the pullback of of under Since is an isometry, the pullback preserves the inner product, and therefore
1
c 1x
(B.60)
20

---

by Assumption 3. Combining Eqs. (B.53), (B.56) and (B.60) and Item Case 1. then gives
E[[x,=1]+15 2 cı5Yn k"yn -
(B.61)
On the other hand, we always have E[ that n- bi for some by > 0 and large enough n as desired.
n+1 [F,,] 2 =[[V==1>+\PP] by Jensen. then follows
We have now verified conditions (i)-(iv Lemma B.1. Thus, Lemma B.1 concludes that
P(lim,-oo 100 Sn = 00 =0
(B.62)
which finishes the proof for the case of Σn yn < oo.
Case 2. When Σn yn co, the same proof above shows that E| 2 biyū for some bj > 0 and large enough n. Combining this with (B.55) yields
B[S л+1
1 2 cyπ
(B.63)
for some
0. Lemma B.2 then concludes:
P(lim Sn 0) =0
as claimed.
B.3. Proof of Proposition 1.
We conclude this appendix with the application of Theorem I to
Algorithms 1-5 under the explicit oracle assumptions Proposition For convenience, we restate the relevant result below:
Proposition 1. Suppose that Algorithms 1-5 are run with gradient oracle V(x; v(x) + (rr((x)) such that
||err(x; 0)1,x S (x) and (1) (x)
(17)
for all z M.M, ||l|l = 1, and for suitable functions (. -M- - R4 with or bounded on bounded
subsets of M and inf, 5(x) O. Then, under Assumptions 2 and 4, the conclusion of Theorem I holds, that is, Algorithms 1-5 avoid strict saddle manifolds of f.
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 suffices to verify Assumption 3 under (17) and the event dist( X,, - We proceed method by method.
Algorithm 1. Since bn 0 in Algorithm 1, Assumption holds trivially by (17).
Algorithms 2, 3 and 5. By definition, (z) is smooth map and hence satisfies lim--o Rz(z)) On the event dist(X,. S) - 0, we have o( (n) + Un + bn O(1). and therefore Xn+1 lies in the injectivity radius of X,, with probability 1 for n large enough. As result, the mapping logx, (Xn+1) 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:
Xn+1 Rx (yn ((x;; 8n)).
(B.64)
Let o, E Mx be the vector such that expx. (r,,0,) X i.e.,
En logx, Rxx (Yn ((X,i On)))
(B.65)
Then (B.64) is RRM scheme with W, i, ((x,) where i, is defined in (B.65). Consider the curve c(t) = Rxx (IV(X,;:,a)) By (17), on the event dist( S) - O, the curve c(t) lies in the injectivity radius of X,, almost surely for all [0, ynl and all large enough. Let é(1) be the smooth curve of c(r) in the normal coordinate with base X, and an arbitrary orthonormal frame, and let & be the normal coordinate of X,-1. Also, let ON be the (Euclidean) vector of é, expanded in the chosen orthonormal basis, and define VÑ (X,,;; 0,) and err (X,; 0,) similarly. By definition, 8 is nothing but o In addition, by (17), we have
|lerr\ 0,) = ||err( (x; 0,) $ o
(B.66)
21

---

for some o < co.
Since X, c(0) and Xn+1 = c(yn), by properties of retraction map must have
nn = 6(7n)
+,(0))y,(0)++))))0)))) (0)) = + y,, = =
= =y, 0n) (7)
= = (Xn: 0n) + ynbn
(B.67)
where b, OYxulIV(X,; (n) 1,,, (y))) Therefore,
||b,lxx = || 1 Fx1 llx. = ||E ( F ( which proves the condition for b, in Assumption On the other hand, (B.67) shows that
(B.68)
IUnllx. S |/ (Xn: 0,,) b, + ||E V (Xn; 0,) + bn
=0(1)
since (xx: 0(1) by (17) and b, = O(ya). Finally, for any unit vector E M, (B.67) implies
E[[(z, Un) 1.1 E[[ err( 0n)
||
[[] 0,,) ]+] Orr))
(B.69)
Since Yn - O, this finishes the proof Algorithms and For Algorithm 3, an Euclidean oracle of the form (17) translates to a Riemannian oracle with err' (x; 0) = h err(x; 0). It then suffices to note that, on the event dist( X,, S) - (²h(X,) is both upper and lower bounded.
Algorithms 4, 6 and? 7. For (RSEG), U, = I x -xn (err (X; 67))
||,, ||err(X; 0 S
(B.70)
by (17) and the fact that the parallel transport map is a linear isometry. For the bias term, the definition of (RSEG) yields
||b,1| -x, (o(X;)) llx,)llx, dist( X,) L,. 0n)lxx O(1) (B.71)
by the same argument as for Algorithms 2, and 5.
For (ROG), we have U, I xx (err(X, (x)) and b, [x (v(x;)) v v(X,), Assumption can be checked exactly as in the case of Algorithm 7 above. The analysis for Algorithm 6 is similar so we omit the details.
22


Reviews:
[{"review_id": "SvJeYsQsF4", "reviewer": "Reviewer_MfPv", "summary": "This paper studies the problem of when Riemannian first-order optimization algorithms evade strict saddles points. The proof leverages a connection to the Euclidean case, to the continuous-time Riemannian gradient flow, and shows that the deviation from them is bounded. Intuitions are given in the main paper to facilitate readership.", "questions": "See above", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper has done a great job in writing, connecting with existing literature, and giving intuitions on how the proof is done. I agree with the claimed contribution in Lines 42-48 and 276-292.", "weaknesses": "I don't see major problems. I do have a few questions and minor comments below.\n\n## Questions\n1. For the definition of a stable manifold: why do we need positive eigenvalues lower bounded by c+>0? What goes bad if the positive eigenvalues could get arbitrarily close to 0?\n1. Equation 6: Consider any update rule whose output is in the range of the exponential map. We can cast the update as (RRM), as is also done in (6). I understand that the gain is that we can then analyze just the exponential map such as the arguments around (15). However, the difficulty is then transferred to checking whether the logarithm of the update satisfies assumption 2, which is much more indirect than checking whether V satisfies assumption 2 as in Algorithm 1. Is this a problem? Could you comment more on this? \n1. Related to the above, for algorithm 3, why do I view it as a special case of algorithm 2 and hence of RRM, rather than saying oh, algorithm 3 is a special case of RRM, because one can just take logarithm and exponential map of (SMD)?\n1. Does (RGF) always stay within the manifold? If so, why? If not, doesn’t the ‘grad’ become not defined outside the manifold?\n\n## Comments\n1. Line 124-125: The definition looks recursive hence confusing: to understand vn_hat I need to understand Un, bn, both of which depend on vn_hat. \n1. Line 18: “end state of a stochastic Riemannian algorithm can only be a local minimizer.” Do you mean something like the limiting state? Even for convex problems in Euclidean space, gradient descent is only guaranteed to approach a solution - the more iterations, the closer. So, in general, the end state is something close to a local minimizer.\n1. Line 102: the “S” is not defined - I suppose you mean a stable manifold?\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you again for your input and remarks. We reply to your questions below, and we will revise our manuscript accordingly in the upcoming revision.\n\n>For the definition of a stable manifold: why do we need positive eigenvalues lower bounded by c+>0? What goes bad if the positive eigenvalues could get arbitrarily close to 0?\n\nWhat is really needed is to be able to invoke the stable manifold theorem. In this regard, the $c_{+}$ lower bound is simply a convenient way to ensure that the positive, zero and negative eigenspaces of the Hessian of $f$ do not change dimension across the saddle manifold, and they induce a well-defined separation of the tangent bundle to $S$ (as a sub-bundle of the tangent space of $M$). It would be possible to relax this condition with no impact on our results, but this is the most straightforward condition that we're aware of in the literature.\n\n\n>Equation 6: Consider any update rule whose output is in the range of the exponential map. We can cast the update as (RRM), as is also done in (6). I understand that the gain is that we can then analyze just the exponential map such as the arguments around (15). However, the difficulty is then transferred to checking whether the logarithm of the update satisfies assumption 2, which is much more indirect than checking whether V satisfies assumption 2 as in Algorithm 1. Is this a problem? Could you comment more on this?\n\nIndeed, if an algorithm has a \"look-ahead\" structure (potentially involving a parallel transport step, like RSEG or the optimistic version of RSGD), the verification of Assumption 2 might require some work, and it is not an immediate consequence of the oracle / stochastic gradient assumptions. So, yes, in theory, if one seeks to employ the RRM framework for a given algorithm, they would have to verify whether Assumption 2 is verified for said algorithm. In practice however, in all the examples that we tested from the literature (Algorithms 1-7, and several that we did not include to avoid overbloating the presentation), this verification is a relatively straightforward affair that did not present any major difficulties (conceptual or technical).\n\n\n>Related to the above, for algorithm 3, why do I view it as a special case of algorithm 2 and hence of RRM, rather than saying oh, algorithm 3 is a special case of RRM, because one can just take logarithm and exponential map of (SMD)?\n\nThis is indeed related to your previous point. In the case of Bregman-based methods, the main difficulty lies in the verification of **Assumption 2**, which explains our preference for viewing (SMD) as a special case of retraction-based methods, as opposed to a direct adoption of the logarithm map.\n\n\n>Does (RGF) always stay within the manifold? If so, why? If not, doesn’t the ‘grad’ become not defined outside the manifold?\n\nYes, $\\mathrm{grad} f$ is a section of the manifold's tangent bundle so, by completeness, RGF gives rise to a global flow on the manifold, and hence always remains there, cf. [36, Chaps. 9 and 10].\n\n\n>Line 124-125: The definition looks recursive hence confusing: to understand vn_hat I need to understand Un, bn, both of which depend on vn_hat.\n\nWhoops, yes, Line (125) was supposed to be a consequence of (124). We will fix this, apologies for any confusion.\n\n\n>Line 18: “end state of a stochastic Riemannian algorithm can only be a local minimizer.” Do you mean something like the limiting state? Even for convex problems in Euclidean space, gradient descent is only guaranteed to approach a solution - the more iterations, the closer. So, in general, the end state is something close to a local minimizer.\n\nYes, by \"end state\" we meant the \"limit state\", not that a minimizer can be reached in a finite number of steps (in general, this is not possible). Consider this fixed in our revision.\n\n---\n\nWe hope that the above addresses your questions - but please let us know if any of the above is not sufficiently clear.\n\nThank you again for your input and positive evaluation,\n\nThe authors"}, {"review_id": "5EP2MKJ3LB", "reviewer": "Reviewer_5i8d", "summary": "The paper presents a focused study on the avoidance of saddle points for stochastic Riemannian optimization algorithms. To tackle this issue, the authors introduce the Riemannian Robbins-Monro (RRM) schemes to the context of Riemannian manifolds, where includes fundamental Riemannian stochastic optimization methods as special cases, such as Riemannian stochastic Gradient Descent (GD), Riemannian proximal GD, and Riemannian optimistic GD.\n\nIn their analysis, the authors have modeled the RRM within the context of a Euclidean stochastic approximation framework by famous Nash embedding theorem, introducing an element of geodesic offset. The authors make the assumption that this offset is $\\mathcal O(\\gamma_n^2)$, a condition found to be met in the case of a bounded-variance stochastic gradient estimator as indicated in Proposition 1. Based on this assumption, they have been able to indicate that RRM schemes have the capacity to avoid saddle points with a probability of 1.\n", "questions": "- In the conclusion section of your paper, you mention 'zeroth-order optimization' as a potential avenue for future work. There have been several studies related to the zeroth-order (or so-called 'bandit') gradient descent method ([1,2]). I am interested to know whether such zeroth-order methods fit within your proposed Riemannian Robbins-Monro (RRM) scheme. If not, could you please clarify the primary gap or obstacle in incorporating these methods into the RRM framework?\n\n- A lot of work on Riemannian optimization tends to focus on complexity analysis in terms of iteration rounds, instead of asymptotic behavior. I was wondering if it would be possible to extend your proposed RRM framework to a non-asymptotic setting. In other words, can the avoidance probability be expressed in terms of the number of iteration rounds, like some approaches in Euclidean space? If this is not feasible, could you elaborate on the main hindrances or challenges in doing so?\n\nRef: [1] J LI et.al., Stochastic Zeroth-order Riemannian Derivative Estimation and Optimization  \n[2] X Wang et.al., Online Optimization over Riemannian Manifolds", "limitations": "The authors have outlined the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Originality: The analysis presented in Theorem 1 and Theorem 2 is highly innovative. In the analysis, the author apply the Nash embedding theorem to isometrically embed the Riemannian manifold into a Euclidean space. This approach allows them to approximate the intrinsic geometry of the manifold using its extrinsic (now Euclidean) geometry, an approach that seems highly original and may potentially shed light on further development in Riemannian optimization methods.\n\n- Quality: The quality of the paper is commendable. The paper is well-written, and the results are convincing.\n\n- Clarity: The paper is well-structured. The assumptions made are either standard in the field of Euclidean optimization or are accompanied by discussions regarding their implications,  making the paper easy to follow for readers.   \n\n- Significance: The paper is the first to generalize saddle point avoidance for stochastic optimization methods on Riemannian manifolds. Additionally, the proposed Riemannian Robbins-Monro (RRM) schemes encompass numerous state-of-the-art Riemannian stochastic optimization algorithms, illustrating potential applications in tackling Riemannian machine learning problems.", "weaknesses": "- Possible typo: l52 shcemes -> schemes.\n\n- It would be better if there are numerical experiments to validate the findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your input and remarks. We reply to your questions below, and we will revise our manuscript accordingly in the next revision opportunity.\n\n\n> It would be better if there are numerical experiments to validate the findings.\n\nDone - please see the \"global rebuttal\" where we included a series of plots on the torus to illustrate how RSGD and RSEG avoid saddle points, despite being initialized closed to spurious saddle points. [The plots are all in the the one-page pdf that we were allowed to upload as part of our rebuttal.]\n\n\n>In the conclusion section of your paper, you mention 'zeroth-order optimization' as a potential avenue for future work. There have been several studies related to the zeroth-order (or so-called 'bandit') gradient descent method ([1,2]). I am interested to know whether such zeroth-order methods fit within your proposed Riemannian Robbins-Monro (RRM) scheme. If not, could you please clarify the primary gap or obstacle in incorporating these methods into the RRM framework?\n\nThis question is fairly intricate:\n\n1. It is not hard to show that the methods in the provided references, as well as a number of other zeroth-order Riemannian methods, indeed fall under the RRM template with certain explicit expressions on the noise and bias/offset terms ($U_n$ and $b_n$ respectively).\n\n2. However, a simple calculation reveals that \n$$\n\\|U_n\\| = O(\\mu_n^{-2}), \\quad  ||b_n || = O(\\mu_n).\n$$\nwhere, in line with the notation in reference [1] that you provided, $\\mu_n$ is the *sampling radius* of the zeroth-order scheme under scrutiny (also known as smoothing parameter, exploration parameter, etc.). In zeroth-order methods, this parameter typically goes to $0$ as $n\\to\\infty$ to enable convergence so, even though the bias/offset assumption in (12) is not violated, the noise bound becomes time-varying, and our results do not immediately apply in this context.\n\nAddressing these challenges, potentially through a careful balance between the step-sizes $\\gamma_n$ and $\\mu_n$ (plus a suitable extension of the probabilistic estimates of Lemma B.1), is an intriguing research question - but, at the same time, it would require orthogonal work to the current paper, so we left it as a direction for future research.\n\n\n>A lot of work on Riemannian optimization tends to focus on complexity analysis in terms of iteration rounds, instead of asymptotic behavior. I was wondering if it would be possible to extend your proposed RRM framework to a non-asymptotic setting. In other words, can the avoidance probability be expressed in terms of the number of iteration rounds, like some approaches in Euclidean space? If this is not feasible, could you elaborate on the main hindrances or challenges in doing so?\n\nIt is certainly possible to enhance our analysis further through the imposition of more stringent conditions, such as the capability to intentionally introduce artificial noise, as discussed in references like [20,63], or additional structure on the function being optimized - e.g., like the \"$(\\alpha,\\beta,\\gamma,\\delta)$-strict-saddle\" property of Ge et al. [22] and Jin et al. [25]. In this more restrictive context, we believe it should be possible to obtain a result along the lines that you suggest - i.e., providing an upper bound on the number of iterations required to produce \"an\" iterate which is sufficiently far from a saddle point. However, this would not imply avoidance, but a \"best iterate with high probability\" guarantee - i.e., in principle, the sequence of iterates could still converge to a strict saddle, even if, with high probability, it has produced an iterate which is close to a local minimum. [We should perhaps also emphasize at this point that this phenomenon is not exclusive to the manifold context, as similar scenarios are encountered in Euclidean optimization problems.]\n\n---\n\nWe hope and trust that these points address your questions - but please let us know if any of the above is not sufficiently clear.\n\nThank you again for your input and positive evaluation,\n\nThe authors"}, {"review_id": "GfJ95GqX1x", "reviewer": "Reviewer_SLQm", "summary": "This paper proves that under a rather general RRM scheme (akin to vanilla GD in euclidean space), strict saddles can be avoided when stochastic approaches are used.", "questions": "I want to know how important the noise perturbation is to this analysis. For the RRM, if no random error is observed, will the theorems still work? Also I want to know whether random perturbations is more important for saddle-escaping or the stochastic oracles are more important.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Proves that Riemannian Optimization, much like its euclidean counterpart, can have its strict saddles easily avoided by using a simple update rule (RRM in this case) coupled with perturbations.\n\n2. This paper analyzed a number of different stochastic algorithms (algorithms 1-5) and shows that they all can escape saddle points.\n\n3. The proof outline is nice. It provides readers a new proof technique that can deal with Riemanian optimization.\n\n", "weaknesses": "1. For unfamiliar readers, it is hard to gauge how limiting the \"our assumptions 1-3\" are, and I would like to see the authors provide a bit more analysis on the limitations of these assumptions.\n\n2. Maybe it's better to include the convergence analysis of the RRM update rule to let users understand better the limitations of this result (it doesn't need to be self-derived, it's perfectly fine to quote well-known results).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your input, insightful questions, and positive evaluation. We address each of your questions in a point-by-point thread below, and we will revise our manuscript accordingly in the next revision opportunity.\n\n>For unfamiliar readers, it is hard to gauge how limiting the \"our assumptions 1-3\" are, and I would like to see the authors provide a bit more analysis on the limitations of these assumptions.\n\nWe understand your concern. It is for this reason that we had included a specific paragraph for discussing each assumption in detail but, at the same time, we were constrained by the 9-page limit and could not include a more extensive positioning for unfamiliar readers. We will be happy to take advantage of the extra page afforded in the upcoming revision to expand on our discussion and provide more details for readers less familiar with the relevant literature.\n\n\n>Maybe it's better to include the convergence analysis of the RRM update rule to let users understand better the limitations of this result (it doesn't need to be self-derived, it's perfectly fine to quote well-known results).\n\nPoint well-taken. Again, due to space limitations, we had to make some tough choices in terms of what to present and what to leave out, but we will be happy to take advantage of the extra page provided in the revision stage to include the basic steps of the convergence analysis for RRM.\n\n\n>I want to know how important the noise perturbation is to this analysis. For the RRM, if no random error is observed, will the theorems still work? \n\nWe did not address the noiseless scenario because, to a certain extent, it had already been examined in various prior studies for RGD [34,35]. The high-level conclusion is that, depending on the initialization, Riemannian first-order methods may or may not evade saddle points; however, the set of initial conditions that result in convergence to saddle points occupies a Lebesgue measure of 0, aligning conceptually with our result that $\\mathbb{P}(X_n \\rightarrow \\mathcal{S}) = 0$ for stochastic methods.\n\nIt is noteworthy to mention that the analysis of the noiseless scenario follows a straightforward trajectory: it emerges as a direct outcome of linearization near saddle points and the implicit function theorem. However, this approach is not sufficient in the presence of noise, leading to a substantially more intricate proof.\n\n\n>Also I want to know whether random perturbations is more important for saddle-escaping or the stochastic oracles are more important.\n\nThe direction the Reviewer is seeking to emphasize would determine the context: Our paper asserts that, in the presence of stochastic oracle feedback, *no random perturbations* are needed to avoid saddle points. Previous research indicates that if the primary objective is to elude saddle points *efficiently*, then random perturbations can be employed to accelerate the process of escape - but, otherwise, in this \"efficient escape\" literature, the optimizer is assumed to have full access to the function's gradients.\n\n---\n\nWe hope and trust that these points address your questions - but please let us know if any of the above is not sufficiently clear.\n\nThank you again for your input and positive evaluation,\n\nThe authors"}, {"review_id": "hkfHsTHPXT", "reviewer": "Reviewer_K9Za", "summary": "The authors study saddle point avoidance of stochastic gradient algorithms formulated on Riemannian manifolds. They prove a number of results on saddle avoidance for which the Euclidean analogs, possibly under slightly different technical assumptions, are known. These results show that stochastic gradient descent algorithms also avoid strict saddle points even if working in a geometric setting. This is a purely theoretical paper and does not include any experiments or empirical examples.\n\nEDIT: I've read the rebuttal, and am happy to keep my score where it was.", "questions": "Certain points that describe what is new could be given in more detail:\n* Line 336: why does this work's probabilistic analysis diverge significantly?\n\nStep 2: would it be fair to say this part of the proof is effectively via a reduction to the Euclidean case?\n\nGeneral question: why is the defined \"(strict) saddle manifold\" actually a manifold? If the saddle points are mere points, and not ridges, this'll (trivially) be a zero-dimensional manifold, as it is a finite or countable point set, but what if there are ridges? Does something assumption here that I've missed prevent singularities from appearing? May help to include some intuition here.\n\nAm I right to think of the RRM scheme as traveling some distance in a tangent space, then mapping back onto the manifold? Thought in this way, it starts to feel a bit like mirror descent, which also projects back onto the space.\n\nAm I right to think about the retraction version as \"viewing the difference between the retraction and exponential map as noise, which we then simply merge with the gradient noise\"?\n\nTypos:\n* 48: \"scopein\" -> typo\n* Line 626: wrong \\eqref, this should instead refer to (13), not to (12)\n* Appendix B: title in the PDF table of contents is \"Proof of thm:repeller\", use \\texorpdfstring to fix this (you can look up what it does)", "limitations": "Yes, this is a theory paper and the technical assumptions are clearly stated throughout", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper addresses an important topic and is very-well-written, particularly its main text. It is very readable to those with theoretical training, but not necessarily experts in optimization - a common pitfall among works written at a similar technical level.\n\nDue to field's historical emphasis on convex optimization at the expense of non-convex optimization, theory on saddle point avoidance is only beginning to become available. At the same time, Riemannian optimization is a rapidly growing area, and has the potential to help bring improved understanding to optimization at a time when doing so is increasingly important due to the rise of deep learning. Therefore, the contribution is timely and valuable\n\nThe technical appendix reads as if it was written carefully. I spotted no hints of sloppiness that would call the results into question, but at the same time this work is heavy enough that typos - including potentially in references the work relies on - are a concern. I did not do a full check, since my primary work is in a different (albeit related) area, and this paper is technical enough that it needs an expert familiar other saddle-avoidance papers for the verification to be trustworthy. I encourage the authors to do a careful read-over after not thinking about this paper for at least a month, so as to go over the logic and spot typos. With this caveat stated, the paper clearly meets the NeurIPS bar from a technical viewpoint.\n\nThe introduction is particularly well put together, makes clear what is already done, what the authors are adding, and what the key takeaways are. I would use this paper as an example to students for how to write a good introduction.", "weaknesses": "No experiments. This paper would have been made significantly stronger with even a minimal empirical study to illustrate how a few examples of RSGD behave on common manifolds. It would have been particularly interesting to see a case or two where RSGD does not get stuck, confirming the theory, and one which violates the theory's assumptions where it does get stuck, illustrating the limitations.\n\nSec 2: consider a more informative title\n\nOptimization-theoretic assumptions involving the setting should be stated more clearly clearly all in one location, so that optimization theory people can easily see how strong the obtained results are:\n* Lipschitz gradient\n* Avoidance defined in terms of strict saddle points\n* Geodesically complete manifold\n* Maybe consider adding \\paragraph called \"Key Assumptions\"?\n\nPaper takes a bit too long to get to the point, page 5 is still describing the setting. Even though the description is good, consider simplifying by having less examples:\n* Consider splitting the examples into one or two key examples, then have the results more in the middle of the paper, then having a final section which describes additional examples\n\nThe paper talks way too many times about how intricate the analysis is. My experience is that most publishable forms of analysis are either intricate or they are obvious, so stating this just makes it feel like the authors want to make themselves look fancy and important to the readers. This is distracting and takes away from the paper's actual content. Rather than saying it's intricate, maybe instead say what specific elements of the analysis make it so.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are sincerely grateful for your encouraging remarks and thoughtful suggestions. We reply to your questions below, and we will revise our paper accordingly in the next revision opportunity.\n\n\n> This paper would have been made significantly stronger with even a minimal empirical study to illustrate how a few examples of RSGD behave on common manifolds. It would ha been particularly interesting to see a case or two where RSGD does not get stuck, confirming the theory, and one which violates the theory's assumptions where it does get stuck, illustrating the limitations.\n\nWe took your point to heart and we generated a series of plots to illustrate how RSGD avoids saddle points on the torus (everything is included in the one-page pdf that we were allowed to upload). Regarding your second point, the stochasticity involved makes it quite difficult to construct an example where RSGD does indeed get stuck with positive probability but, on the flip side, we performed a series of experiments with the extra-gradient method RSEG to illustrate that our avoidance results are not limited to RSGD.\n\n\n> Sec 2: consider a more informative title.\n\nWill do - we will highlight that it is intended to fix some basic definitions of Riemannian geometry and optimization.\n\n\n> Optimization-theoretic assumptions involving the setting should be stated more clearly all in one location, so that optimization theory people can easily see how strong the obtained result\n\nWill do - we will modify the beginning of Section 4 accordingly, along the lines you recommended.\n\n\n> Consider splitting the examples into one or two key examples, then have the results more in the middle of the paper, then having a final section which describes additional examples.\n\nPoint taken. We did want to emphasize the flexibility afforded by the RRM template, but we also understand the benefit of getting to the point faster. We will restructure accordingly (sending some examples to the appendix if needed).\n\n\n> The paper talks way too many times about how intricate the analysis is.\n\nApologies, we did not mean to make the exposition sound bloated or over-inflated. We will remove all such instances that we spot, and we will do a full editorial pass to remove any adverbs and/or adjectives that are subjective.\n\n\n> Line 336: why does this work's probabilistic analysis diverge significantly?\n\nThis is due to the disparities in the step-size and noise assumptions: To provide a simplified overview, an essential step in the analysis is to control the fluctuation of cumulative noise $\\sum_{n\\geq m} \\gamma_nU_n$, where $\\gamma_n$ is the step-size and $U_n$ is the noise. In [31] (cf. numbering as in the full paper, including the appendix), because the step-size schedule exhibits a significantly faster decrease rate $\\Omega(1/\\sqrt{n})$, the Burkholder-Davis-Gundy inequality serves as the appropriate tool for that scenario. However, this analysis is inadequate when dealing with gradually decreasing step-sizes of the form $\\mathcal{O}(1/(\\log n)^{1+\\epsilon})$ in our particular context.\n\n\n>Step 2: would it be fair to say this part of the proof is effectively via a reduction to the Euclidean case?\n\nYes, this is the driving idea.\n\n\n>General question: why is the defined \"(strict) saddle manifold\" actually a manifold? If the saddle points are mere points, and not ridges, this'll (trivially) be a zero-dimensional manifold, as it is a finite or countable point set, but what if there are ridges? Does something assumption here that I've missed prevent singularities from appearing? May help to include some intuition here.\n\nApologies for any confusion. When we wrote \"smooth compact component\" in the definition of a strict saddle manifold, the \"smooth\" was meant in the manifold sense. As you recommended above, we will bring this definition in Section 4 to collect all relevant information in a single place and ensure there is no ambiguity or confusion.\n\n\n>Am I right to think of the RRM scheme as traveling some distance in a tangent space, then mapping back onto the manifold? Thought in this way, it starts to feel a bit like mirror descent, which also projects back onto the space.\n\nThis is not our intuition. For us, RRM is traveling on the manifold directly, along a search direction defined by an \"approximate\" / \"surrogate\" gradient, including noise and/or a (possibly non-random) bias/offset. This bias/offset term is crucial for our purposes as it allows us to capture several different algorithms, possibly with a forward-backward-forward structure (like ROG and RSEG). However, the RRM iterates per se never leave the underlying manifold.\n\nWhen embedded in real space, the part $X_n + \\gamma_n \\hat V_n$ of (16) which represents the RRM update minus the geodesic offset does exhibit the behavior that you describe. If this is what you are referring to, then we agree with your intuition - with the \"geodesic offset\" essentially standing in for the projection mechanism.\n\n\n>Am I right to think about the retraction version as \"viewing the difference between the retraction and exponential map as noise, which we then simply merge with the gradient noise\"?\n\nYour intuition is accurate, with a minor caveat. The gradient \"noise\" is conventionally assumed to have zero mean, while the difference between the retraction and exponential map does not possess this property. To circumvent any potential confusion, we opt for the term \"error\" instead of \"noise\" when discussing the differences between random and systematic errors.\n\n> {Typos}\n\nWill fix, thanks for spotting them and bringing them to our attention!\n\n---\n\nWe hope that these points address your questions - please let us know if any of the above is not sufficiently clear.\n\nThank you again for your input and positive evaluation,\n\nThe authors"}]

Author rebuttal:
Dear AC, dear reviewers,

We are sincerely grateful for your time, input and positive evaluation.

To streamline our rebuttal, we reply to each reviewer's questions in a separate point-by-point thread below. We only include in this global rebuttal a pdf with two figures showing the avoidance of saddle points under the RSGD and RSEG methods (Riemannian stochastic gradient and extra-gradient respectively). For illustration purposes, we used a $2$-dimensional torus and an objective function with three saddle points and one minimizer, depicted as black and red respectively. Despite being initialized close to the spurious saddle points, both methods avoid them and ultimately converge to a (global) minimum, as suggested by the theory of the paper.

We defer all other points to the reviewer-specific threads below and we are looking forward to the discussion phase if any further questions remain.

With our kindest regards,

The author team of Paper 6491

Meta-review: This paper answers an important question: when can Riemannian stochastic algorithms avoid saddle point? This question has been addressed in the Euclidean space and for the Riemannian deterministic algorithm. Therefore, the results provide important complement to the literature. The results of this paper are timely and valuable since both Riemannian optimization and stochastic algorithms are becoming more and more important and find many important applications. The paper is well-written and organized.
Decision: Accept (poster)