Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
We study optimization of finite sums of geodesically smooth functions on Riemannian manifolds. Although variance reduction techniques for optimizing finite-sums have witnessed tremendous attention in the recent years, existing work is limited to vector space problems. We introduce Riemannian SVRG (RSVRG), a new variance reduced Riemannian optimization method. We analyze RSVRG for both geodesically convex and nonconvex (smooth) functions. Our analysis reveals that RSVRG inherits advantages of the usual SVRG method, but with factors depending on curvature of the manifold that influence its convergence. To our knowledge, RSVRG is the first provably fast stochastic Riemannian method. Moreover, our paper presents the first non-asymptotic complexity analysis (novel even for the batch setting) for nonconvex Riemannian optimization. Our results have several implications; for instance, they offer a Riemannian perspective on variance reduced PCA, which promises a short, transparent convergence analysis.
This paper develops RSVRG, a variance-reduced stochastic gradient method for minimizing finite sums of functions on Riemannian manifolds. The paper establishes that the approach can converge linearly, even for geodesically nonconvex functions, and that the complexity of the method depends on the geometry of the manifold. The convergence results are nonasymptotic, and the complexity results use the IFO paradigm. The paper provides experiments for two applications. One application is PCA and the other is computing the Riemannian centroid of symmetric positive definite matrices. Through these experiments, the paper illustrates the benefit of variance reduction.
This paper addresses a topic that was proposed as future work in [32], and by design, much of its contents are adaptations of results found in [14] and [21]. Thus, the analysis is incremental. Nonetheless, the paper contributes a manifoldized algorithm and bridges a gap between convex optimization and Riemannian optimization. Furthermore, the paper provides a useful lemma to analyze Riemannian methods, which can have a lasting impact.  My main concern with this paper is its presentation. The paper is elusive on details, which undermines its technical quality, omits an important reference, and suffers from language issues. In Theorem 4, the constants mu1 and nu1 should be defined (are they the same as the constants in [21]?). For the PCA application, the matrix Z should be related to the problem (are the vectors z the columns of Z as in [25]?). For both applications, it should be mentioned how the accuracy is measured (accuracy is the ordinate of most of the plots). For the centroid application, the parameters N and Q should be defined (is N=n?). The paper should expound on the exponential and parallel transport mappings (the most important parts of RSVRG) for each of the applications: granted, for the PCA application, the paper cites an entire textbook for the mappings, but a citation like this is more pleasant with page numbers (I could not find the relevant results). The reference for the IFO framework should be included; the reference is "A Lower Bound for the Optimization of Finite Sums" by Alekh Agarwal and Léon Bottou. Finally, the paper would benefit from a good proof read. Here are some of the language issues:  Line 48: "developing fast stochastic for it". Maybe this should read "developing fast stochastic methods for it". Line 56-57: "we generalize convergence analysis". This should read "we generalize the convergence analysis"; there are many missing "the's" in the paper. Line 59: "method this is provably". Perhaps "this" should be replaced by "that", or the sentence should be reworded. Line 130: "takes and i". Not "and" but "an". Line 155: "an fi minimize all". Not "minimize" but "minimizes". Theorem 2: The first sentence is incomplete. Maybe "If" should be replaced by "Suppose" (as in the restatement of the theorem in the supplementary material).  Here are some other issues: In the experiments for PCA, the methodology for estimating the number of accuracy-doubling epochs should be described. This number becomes less for RSVRG than for VR-PCA as the eigengap decreases, and it should be mentioned whether the number of IFO calls follows this tendency for a given accuracy (the comparison is provided only for a single, relatively large delta). It should be explained why the IFO complexity provides a fair comparison (RSVRG requires evaluating not only gradients, but also exponential and parallel transport mappings - are the extra computations worth it?).  More issues:  Equation 8: The index i on each z is missing.  Line 435 (in the supplementary material): "Corollary ??".