Riemannian gradient methods for stochastic composition problems

In the paper, we study a class of novel stochastic composition optimization problems over Riemannian manifold, which have been raised by multiple emerging machine learning applications such as distributionally robust learning in Riemannian manifold setting. To solve these composition problems, we propose an effective Riemannian compositional gradient (RCG) algorithm, which has a sample complexity of O(ϵ^-4) for finding an ϵ-stationary point. To further reduce sample complexity, we propose an accelerated momentum-based Riemannian compositional gradient (M-RCG) algorithm. Moreover, we prove that the M-RCG obtains a lower sample complexity of Õ(ϵ^-3) without large batches, which achieves the best known sample complexity for its Euclidean counterparts. Extensive numerical experiments on training deep neural networks (DNNs) over Stiefel manifold and learning principal component analysis (PCA) over Grassmann manifold demonstrate effectiveness of our proposed algorithms. To the best of our knowledge, this is the first study of the composition optimization problems over Riemannian manifold.