Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper claims to provide a first order gradient algorithm that achieves (global) equivalent rates of convergence than in Euclidean space on two particular models of geometry (though important) the hypersphere and the hyperbolic space.
The strategy proposed here consists in using the geodesic maps in order to write the minimization problem on the Euclidean space with a controlled distortion, which makes possible the use of a relaxed version of convexity inequalities. In the new coordinate system, the minimised function is not convex but not far from it, in a way the authors are able to control quantitatively.

My opinion on the technical content of the paper is hindered by the difficulty of reading this paper. See the remarks for improving its readability below. The overall result seems a bit weak for all this work (40 pages long paper in total incl. supplementary material.) and the calculations do not seem particularly enlightening. 

I would suggest an important rewriting of the paper; Ideally, the main ideas of the paper should be illustrated in the fist technical part section in a simple and enlightening example. Also, putting forward a skeleton of proof of the main result of the paper with more details on the objects would be very helpful for the reader.

Other comments on the readability:

In the contribution section, the third point on reductions is not clear at all. I suggest a rewriting of the sentence that makes it more understandable. 

The method uses geodesic maps and in particular  …maps geodesics from the constant curvature space to geodesics in the  Euclidean space… This condition is very stringent. For instance, there is a theorem by Kobayashi which quantifies that affine maps (a condition which implies geodesic maps) are often isometries.
I would suggest the authors spend more time on the definition of a geodesic map and provide a discussion. In particular, they could  write the explicit definition of such maps in the two cases of interest: the (hyper)sphere and the hyperbolic space instead of pointing to the so-called classical geodesic maps. 

The beginning of section 2 is difficult to read. The strategy is explained in wordy manner: example:
…. Our approach is to obtain a lower bound that is looser by a constant depending on R, and that is linear over B. In this way the aggregation becomes easier. … Helping the reader with equations or more precise definitions would be helpful.

Section 2.1 is hard to follow, example:
… after applying some desirable modifications, like regularization with a 1-strongly convex function 
ψ and removing the unknown x ̃∗ by taking a minimum over X . Note (4) comes from averaging (3) ∗ 
for y ̃ = x ̃ . …

The contributions to reductions techniques in Section 3 is only accessible to the expert reader and the main text is only statement of the results. The authors could make their point more explicit here.


review_title: Difficult paper to read for AGD on simple geometric models.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper considered the problem of minimizing (strongly and non-strongly) geodesically convex functions on hyperbolic and spherical manifolds, manifolds of constant curvature 1 and -1, respectively, and proposed accelerated algorithms for such problems. In particular, the author(s) showed the proposed algorithms enjoy global accelerated rates that match their Euclidean counterparts. A key to the main result is Lemma 2.2 which asserts a certain quasar convexity-type condition of the pull-back of the objective function to some Euclidean domain through a geodesic map. Based on this lemma, the main result follows from combining techniques for developing accelerated algorithms in Euclidean space, such as the approximate duality gap technique and a certain discretization scheme for continuous dynamics. Some reduction results, which obtain accelerated algorithms for the strongly convex case from the non-strongly convex case, and vice versa, are also presented.

I believe that the technique is new, to the best of my knowledge. And I think that obtaining accelerated algorithms for manifold optimization problems is definitely an important topic. Therefore, the results should be interesting to a broad audience of the conference and deserve some merits. However, I have some doubts about the paper.

1. The presentation of the proofs in the supplementary material is unsatisfactory. There are so many arguments like "trivial/easy to see/prove", "follows straightforwardly/trivially", etc. It makes the proofs very difficult to follow.

2. In Lemma 2.2, it's a bit surprising to me that the constants gamma_p and gamma_n depends only on the radius R of the geodesic ball but not the function F (which implicitly contains K due to the rescaling) nor the point x. Perhaps some intuition of why this is the case and some interpretation of these two constants would be good. It is important as the gamma constants are involved in the complexity in Theorem 2.4 (and hence in Theorem 2.5). 

3. The setting of manifolds of constant curvature seems to be quite restrictive. And, as pointed out in the paper, it seems difficult that the technique could be extended to other manifolds.

4. The practicality of the main algorithm (Algorithm 1) seems to be very limited. I understand that this paper focuses more on theoretical side. I am not hoping for practical use either. However, it would be good to demonstrate that performance/behaviour of the proposed algorithm does corroborate with the theories, at least in some toy examples such as optimization problems on the Poincare disk.

Other comments:
1. On page 3, the \tilde{v} (vector of the same norm) is not well-defined. If \tilde{v} satisfies the definition, then it can be checked that 2 \tilde{v} also satisfies the definition.

2. On page 3, it is mentioned that R\ge d(x_0, x^*) implies x^* \in \Exp_{x_0} (\bar{B}(0,R)). I believe such implication requires geodesic completeness of the manifold.

3. On page 3, in the notation section, the constant K appeared without definition.

4. The notions of curvature of manifolds and angles between points on manifolds are used without definition. It would be good to present the definition somewhere in the paper or the supplementary material.

5. A recent paper "An accelerated first-order method for non-convex optimization on manifolds" by Criscitiello and Boumal, which studied accelerated algorithms for non-g-convex optimization on a more general class of manifolds, is missing from the comparison.

6. Sometimes the tangent space T_x M is mistakenly written as T_x. For example, on page 4 and also in the supplementary material.

7. In Lemma 2.3, it is a bit strange that the smoothness property of the pull-back function would require the assumption of the existence of a stationary point. Could you please provide some explanation?
review_title: Review of Paper699

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a global accelerated method on Riemannian manifolds with the same rates as accelerated methods in the Euclidean space up to log factors. Reductions have also been studied on Riemannian manifolds.

Quality: I think this paper has high quality in theory.

Clarity: I have no experience on Riemannian manifolds before. This paper reads difficult for me. I think this paper is too technical and some descriptions are not clear.

Originality: There are a number of works that study the problem of first-order acceleration on Riemannian manifolds. This paper studies the special case of constant sectional curvature, i.e., the hyperbolic and spherical spaces. I am not sure whether there are literatures studying the optimization algorithms (either accelerated or non-accelerated) on the constant sectional curvature before.

Significance: This paper gives the state-of-the-art rates in the special case of constant sectional curvature. I think it is significant.

I have some comments. I have no experience on the optimizaton on Riemannian manifolds before. My comments may be too strict for the analysis on Riemannian manifolds.

1. Previous literatures have studied the optimization on Riemannian manifolds of bounded sectional curvature, while this paper focuses on the special hyperbolic and spherical spaces, that have constant sectional curvature. Is there any literature focusing on the constant sectional curvature before? either accelerated or non-accelerated. What is the critical difference when transforming the analysis on the bounded sectional curvature to constant sectional curvature? Is it a straightforward extension, or very challenging?

2. I am not sure whether each step of the proposed method needs more computations than the standard accelerated gradient method. For example, function f is a composition of F and h^{-1}, can \nabla f(x) be efficiently computed? The BinaryLineSearch needs to compute \Gamma_i^{-1} and x_{i+1}^{\lambda}, do they need more computations? 

review_title: This paper obtains the state-of-the-art rates with solid theoretical guarantees on accelerated Riemannian optimization.

final_score: rating: 4: Ok but not good enough - rejection
review_content: Unfortunately, though I am familiar with the literature on accelerated gradient methods in Euclidean spaces, I am not familiar enough with Riemannian geometry to provide a confident review of this paper. That being said I can provide some feedback.

Overall, this paper is very dense with mathematics that will not be not particularly familiar to most machine learning people. Moreover the suggested applications to ML (a single line in the paper) is not particularly convincing without more discussion and context (e.g., a fully worked example). This is compounded by the fact that no experiments were presented. This paper would be greatly improved by an experiment that showed the improvement of this algorithm over vanilla gradient approaches on a Riemannian manifold, even if the experiment was totally synthetic. Even better would be to present a real machine learning application. With that in mind, I have a concern that ICLR is not the right venue for this paper. After all, ICLR is focussed on Learning Representations and though I tend to have a relaxed approach to this I think this paper might not be of general enough interest to the ICLR community (even though it may well be an excellent paper).

Some more minor comments:

This paper focuses on hyperbolic and spherical manifolds. How important are these spaces in practical problems? I wonder if the limited scope of the results covers the machine learning applications discussed in the introduction. This needs more discussion. If these spaces are presented primarily because the analysis is easier then this is another reason why ICLR might not be the right venue.

I am surprised that any of the parameters of the manifold do not appear in the bound. Is there some intuition why the bound relies only on the constants of the function f (\mu and L) and not on any property of M (eg, the main results section the results are in terms of L and mu and ignore only factors of log(L/mu))? It would be good to add a discussion of this, or be explicit with the dependency in the bounds if there is one.

Very minor comment: the word 'unfeasible' is unusual (though apparently it is a real world), infeasible is more common.
review_title: Acceleration in Hyperbolic and Spherical Spaces

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: This paper provides a generalization of AGD to constant sectional curvature spaces (or subsets of them), and proves the same global rates of convergence that hold in the Euclidean space. Additionally, they provide reductions for the bounded sectional curvature case. Their basic strategy involves the use of geodesic maps to accumulate local linear lower bounds, in a way that accounts for the geometric distortion incurred by the map.

Strengths: The paper is written well and organized in a reasonable fashion. They have a clear description of the general techniques applied in their work, and push overly technical arguments to the appendix. They provide global rates which also apply to g-convex functions (not just strongly convex). Where I have checked, their statements are mathematically sound.

Weaknesses: The domain of applicability for their main rates are restricted to the constant curvature spaces, and it could be argued that it is relatively narrow in scope. I am not sure of the convention in this community, but perhaps it would helpful also to have some experimental results and code to assist in reproduction and discussion of practical import and comparison.

Recommendation: I gave a score of 7, as it seems to provide technical progress over previous results and the authors are clear in describing their contributions. My score is relatively uncertain as I was not able to check many of the technical arguments and lemmas. UPDATE: I would reduce my score to a 6 based on the opinions of my fellow reviewers. It appears that the restricted scope and lack of experimental results is quite a problem within this community and venue.
review_title: Global rates on constant curvature model spaces via geodesic map analysis and approximate duality gap techniques

Meta-review: Reviewers generally appreciate the theoretical contribution of the paper, namely Accelerated Gradient Descent on the sphere and hyperbolic space with the same convergence rate as the Euclidean counterpart. However, there are several major concerns with the current work. From a theoretical standpoint, the geodesic map, which plays a crucial role in the algorithm and theoretical analysis, exists if and only if the manifold has constant sectional curvature (sphere and hyperbolic space). It is not at all clear how the current approach can be extended beyond this setting. 
From an algorithmic viewpoint, the stated algorithm has not been experimentally validated. It is suggested that at least some synthetic experiments, e.g. on the sphere or Poincare disk, be carried out. Finally, the current presentation is quite dense and should be considerably improved.
Decision: Reject