Faster FirstOrder Methods for Stochastic NonConvex Optimization on Riemannian Manifolds SPIDER (Stochastic Path Integrated Differential EstimatoR) is an efficient gradient estimation technique developed for nonconvex stochastic optimization. Although having been shown to attain nearly optimal computational complexity bounds, the SPIDERtype methods are limited to linear metric spaces. In this paper, we introduce the Riemannian SPIDER (RSPIDER) method as a novel nonlinearmetric extension of SPIDER for efficient nonconvex optimization on Riemannian manifolds. We prove that for finitesum problems with n components, RSPIDER converges to an epsilonaccuracy stationary point within mathcalObig(minbig(nfracsqrtnepsilon2,frac1epsilon3big)big) stochastic gradient evaluations, which is sharper in magnitude than the prior Riemannian firstorder methods. For online optimization, RSPIDER is shown to converge with mathcalObig(frac1epsilon3big) complexity which is, to the best of our knowledge, the first nonasymptotic result for online Riemannian optimization. Especially, for gradient dominated functions, we further develop a variant of RSPIDER and prove its linear convergence rate. Numerical results demonstrate the computational efficiency of the proposed methods.

A Geometric Interpretation of Stochastic Gradient Descent Using Diffusion Metrics This paper is a step towards developing a geometric understanding of a popular algorithm for training deep neural networks named stochastic gradient descent (SGD). We built upon a recent result which observed that the noise in SGD while training typical networks is highly nonisotropic. That motivated a deterministic model in which the trajectories of our dynamical systems are described via geodesics of a family of metrics arising from a certain diffusion matrix; namely, the covariance of the stochastic gradients in SGD. Our model is analogous to models in general relativity: the role of the electromagnetic field in the latter is played by the gradient of the loss function of a deep network in the former.