Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors present "an accelerated first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions over a compact and geodesically convex set in Hadamard manifolds, that we access to via a metric-projection oracle". For this oracle, they use "projected Riemannian gradient descent to implement an inexact proximal point operator". 
The analysis aims to establish 'an accelerated rate' up to multiplicative factors induced by the manifold's sectional curvature (Line 166, Fact 1.3, Lines 149-155), as well as some log factors (Remark A.5, Line 838, Remark 2.3). An extensive list of recent work on Riemannian optimization has been provided. 

strengths_and_weaknesses: The writing and the flow are excellent but only provide a very high level idea of the work and contributions of the current paper. A considerable part of the paper, up until the middle of page 7, out of 9 pages, focuses on review of background material, review of previous works, and "insights", and the technical statements and proofs have been presented in the appendices. I would also leave a proper assessment of the claims to reviewers with close familiarity to those recent works cited upon which the paper claims advantages. As an example a lot of the background reviewed on Lines 85-152 remains unused within the main paper. 

questions: It would be helpful to provide a remark, specifically gathering all of the "universal constants" and "logarithmic factors" (e.g., Remark A.5, Line 838, Remark 2.3, etc); and/or the source of their introduction into the analysis. 

Footnote 0: some of the links seem to be broken; for example, for \kappa_\min. 

There is an impossibility argument on Lines 246-250 that I did not follow. Could you please elaborate?

A short discussion on the gains from the 'approximate' computation (Remark 2.3), in some of the Riemannian optimization instances, could be helpful.

Some examples/references for the note on Lines 365-367 could be useful. ("We note that any other algorithm with linear convergence rates for constrained strongly g-convex, smooth problems that works with a metric-projection oracle can be used as a subroutine to obtain an accelerated Riemannian algorithm.")

Could the authors elaborate on 
- "due to fundamental properties of their methods" on Line 63; 
- "which is not amenable to optimization" on Line 73-74;

In relation to "The Riemannian proximal point subroutine we design is of independent interest", on Lines 79-80 (and in the abstract), it might be beneficial to present this subroutine in an algorithmic form instead of plain text. 


Are there any limitations of the presented algorithm or analysis that the authors feel could inform a better comparison with the existing literature as well as future work? Including possibilities of alternatives in certain aspects. Other examples: any further details regarding the multiplicative factors (Line 382), or any indication or difficulty in extending to other manifolds (Lines 383-384)?

limitations: Please see previous comments on the discussion of technical contributions as well as on logarithmic factors.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes accelerated first-order methods for optimizing smooth and geodesically convex functions on Hadamard manifolds. 
strengths_and_weaknesses: Acceleration on Riemannian manifolds is an important and timely topic that has recently received a lot of interest in the optimization community. The literature review is comprehensive and the background section is well-written. The theoretical results are well-motivated and presented.

My main concern is the metric projection oracle and the resulting comparison results with existing methods. If I understand correctly, the complexity results are given with respect to the number of queries to the metric projection oracle. However, the cost of one such query is not clear to me from the text (also not from Rmk. 2.3). If you factor in this cost, does the method still compare favorably to prior methods? Please clarify, if I am misunderstanding. 

How practical is the proposed method? Can Alg. 1 (including the subproblems) be implemented efficiently for at least some classical problems, e.g., some of the examples listed in the first paragraph of the introduction?
questions: see above
limitations: see above
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposed an accelerated first-order optimization algorithm for smooth and
(strongly) geodesically-convex functions over a compact and geodesically-convex set
on Hadamard manifolds. It is proven in this paper that this Riemannian algorithm
enjoys the same convergence rate as the Euclidean AGD algorithm without convex constraints. 
Though there exist some relavent works, none of them fully generalize the Euclidean AGD 
convergence results to the Riemannian setting.
strengths_and_weaknesses: The contribution of this paper is on the theoretical aspect. It is interesting in the sense 
that it firstly gives an algorithm that fully extends the Euclidean AGD to the Riemannian setting
with constraints. However, numerically, this algorithm is hard to use. It involves quite a 
few unknown operators and parameters, and expensive operators.
questions: The requirements of a geodesically convex function over a geodesically-convex set on Hadamard manifolds
are quite strong and already limit the usage for many important applications. The author gives two manifolds in
the paper, one is a hyperbolic manifold and the other one is the manifold of SPD manifold. Giving a few applications
would be helpful.

The metric projection oracle seems not easily available. Giving a few examples and potentials in applications
would be useful.

The algorithm needs the value of \zeta_{2D}. How do users get this value?
limitations: I think the authors need to comment on the implementation and numerical performance of this proposed algorithm.
review_title: null

Meta-review: metareview: The paper deals with accelerated methods on Riemannian manifolds. A particular challenge that the paper tries to address, which the AC believes is important, is related to the bounding of the iterates. The paper starts with an explicit bounding constraint on the manifold (and relaxes to the ball constraint for certain manifolds) and shows that the proposed algorithm can respect that while achieving acceleration. The reviewers including this AC see the merits of the paper. However, the paper in its current form is far from complete. A particular concern is on the empirical performance of the algorithm, resolving which should strengthen the paper. I would encourage the authors to build on the discussions and polish the paper accordingly.

Even though the paper has positive scores, the paper in its current form is a borderline paper with significant scope for improvement. To this end, the AC cannot accept the paper.
confidence: Certain
Decision: Reject