Riemannian stochastic optimization methods avoid strict saddle points

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. EDIT: I've read the rebuttal, and am happy to keep my score where it was.

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. Due 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 The 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. The 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. Sec 2: consider a more informative title Optimization-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: * Lipschitz gradient * Avoidance defined in terms of strict saddle points * Geodesically complete manifold * Maybe consider adding \paragraph called "Key Assumptions"? Paper 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: * 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 The 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.

Questions

Certain points that describe what is new could be given in more detail: * Line 336: why does this work's probabilistic analysis diverge significantly? Step 2: would it be fair to say this part of the proof is effectively via a reduction to the Euclidean case? 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. 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. 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"? Typos: * 48: "scopein" -> typo * Line 626: wrong \eqref, this should instead refer to (13), not to (12) * 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)

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Yes, this is a theory paper and the technical assumptions are clearly stated throughout

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.

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. 2. This paper analyzed a number of different stochastic algorithms (algorithms 1-5) and shows that they all can escape saddle points. 3. The proof outline is nice. It provides readers a new proof technique that can deal with Riemanian optimization.

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. 2. 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).

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.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

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. In 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.

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. - Quality: The quality of the paper is commendable. The paper is well-written, and the results are convincing. - 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. - 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. - It would be better if there are numerical experiments to validate the findings.

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? - 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? Ref: [1] J LI et.al., Stochastic Zeroth-order Riemannian Derivative Estimation and Optimization [2] X Wang et.al., Online Optimization over Riemannian Manifolds

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors have outlined the limitations of their work.

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.

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. ## Questions 1. 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? 1. 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? 1. 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)? 1. Does (RGF) always stay within the manifold? If so, why? If not, doesn’t the ‘grad’ become not defined outside the manifold? ## Comments 1. 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. 1. 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. 1. Line 102: the “S” is not defined - I suppose you mean a stable manifold?

Questions

See above

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Yes

Official Comment by Authors

Thank you for the in-depth review and encouraging comments.