Accelerated First-order Methods for Geodesically Convex Optimization on Riemannian Manifolds
In this paper, we propose an accelerated first-order method for geodesically convex optimization, which is the generalization of the standard Nesterov's accelerated method from Euclidean space to nonlinear Riemannian space. We first derive two equations and obtain two nonlinear operators for geodesically convex optimization instead of the linear extrapolation step in Euclidean space. In particular, we analyze the global convergence properties of our accelerated method for geodesically strongly-convex problems, which show that our method improves the convergence rate from
Moreover, our method also improves the global convergence rate on geodesically general convex problems from O(1/k) to O(1/k 2 ). Finally, we give a specific iterative scheme for matrix Karcher mean problems, and validate our theoretical results with experiments.
Summary of the Paper
====================
The paper considers a geodesic generalization of Nesterov's accelerated gradient descent (AGD) algorithm for Riemannian spaces. Two versions are presented: geodesic convex case and geodesic strongly convex smooth case. The proposed algorithms are instantiated for Karcher mean problems, and are shown to outperform two previous algorithms (RGD, RSGD), which address the same setting, with randomized data. 
Evaluation
==========
From theoretical point of view, finding a proper generalization for the momentum term (so as to be able to implement AGD) which maintains the same convergence rate for any Riemannian space is novel and very interesting. From practical point of view, it is not altogether clear when the overall running time reduces. Indeed, although this algorithm requires significantly smaller number of iterations, implementing the momentum term can be very costly (as opposed to Euclidean spaces). That said, the wide range of settings to which this algorithm potentially applies makes it appealing as a general mechanism, and may encourage further development in this direction. The paper is well-written and relatively easy-to-follow.

General Comments
================
- The differential geometrical notions and and other definitions used intensively throughout this paper may not be familiar for the typical NIPS reader. I would suggest making the definition section more tight and clean. In particular, the following are not seemed to be defined in the text: star-concave, star-convex, grad f(x), intrinsic inner-product, diameter of X, conic geometric optimization, retractions.
- Equations 4 and 5 are given without any intuition as how should one derive them. They seem to be placed somewhat out of the blue, and I feel like the nice figure provided by the authors, which could potentially explain them, is not addressed appropriately in the text.

Minor Comments
==============
L52 - redundant 'The'
L52+L101 - There is a great line of work which tries to give a more satisfying interpretation for AGD. Stating that the proximal interpretation as the main interpretation seems to me somewhat misleading.
L59 - Can you elaborate more on the computational complexity required for implementing the exponent function and the nonlinear momentum operator S. 
L70 - why linearization of gradient-like updates are contributions by themselves.
L72 - classes?
L90 + L93 - The sentence 'we denote' is not clear.
L113 - the sentence 'In addition, different..' is a bit unclear..
L126 - besides the constraint on alpha, what other considerations are needed to be taken in order to set its value optimally?
L139 + L144 - Exp seems to be written in the wrong font.
L151 - The wording used in Lemma 3 is a bit unclear.
L155 - in Thm 1, consider restating the value of beta.
L165 - How does the upper bound depend on D? Also, here again, how is alpha should be set?
L177 - maybe geometrically -> geodesically?
L180 - In section 5, not sure I understand how the definition of S is instantiated for this case.
L181 - 'For the accelerated scheme in (4)' do you mean algorithm 1?
L183 - Y_k or y_k?
L193 - 'with the geometry' is not clear.
L201 - Redundant 'The'. Also, (2) should be (3)?
L219 - Can you explain more rigorously (or provide relevant pointers) why RGD is a good proxy for all the algorithm stated above?
Page 8 - Consider providing the actual time as well, as this benchmark does not take into account the per-iteration cost.
L225 - Why is C defined explicitly?