Inexact trust-region algorithms on Riemannian manifolds
We consider an inexact variant of the popular Riemannian trust-region algorithm for structured big-data minimization problems. The proposed algorithm approximates the gradient and the Hessian in addition to the solution of a trust-region sub-problem. Addressing large-scale finite-sum problems, we specifically propose sub-sampled algorithms with a fixed bound on sub-sampled Hessian and gradient sizes, where the gradient and Hessian are computed by a random sampling technique. Numerical evaluations demonstrate that the proposed algorithms outperform state-of-the-art Riemannian deterministic and stochastic gradient algorithms across different applications.
This paper proposed the inexact TR optimization algorithm on manifold, in which the analysis largely follows from the euclidean case [27,28]. They also considered the subsampling variant of their method for finite-sum problems and the empirical performance on PCA and matrix completion problems.   1. It seems to me the convergence analysis follows exactly from the works [27,28] except for some different notation. At least this paper doesn't show what is the technical challenge for the Riemannian case.   2. For the experiments, both MC and PCA problems can be solved efficiently by Euclidean method like GD/SGD. What are the advantages of using Riemannian optimization method?   3. In appendix, line 410, C should not depend on \delta_g or \delta_H otherwise it will depend on \eps_g and \eps_H.  Overall, it is a good paper with very interesting results. The presentation can be further improved.  First, show some real motivation for doing inexact RTR method. Right now the intro is a little bit general and vague.  Second, show the technical challenges/difficulties of obtaining the iteration complexity results and the analysis should be elaborated a little bit. Third, show some background/examples on how to compute the gradient and Hessian on manifold, i.e. how you can do it efficiently in practice for certain problems.