A Riemannian AdaGrad-Norm Method

We propose a manifold AdaGrad-Norm method ($\text{textsc}MAdaGrad$), which extends the norm version of AdaGrad (AdaGrad-Norm) to Riemannian optimization. In contrast to line-search schemes, which may require several exponential map computations per iteration, $\text{textsc}MAdaGrad$ requires only one. Assuming the objective function $f$ has Lipschitz continuous Riemannian gradient, we show that the method requires at most $\mathcal{O}({\epsilon }^{-2})$ iterations to compute a point $x$ such that $\mathrm{\parallel }\mathrm{grad}f(x)\mathrm{\parallel }\le \epsilon$. Under the additional assumptions that $f$ is geodesically convex and the manifold has sectional curvature bounded from below, we show that the method takes at most $\mathcal{O}({\epsilon }^{-1})$ to find $x$ such that $f(x)-f_{low}\le \epsilon$, where $f_{low}$ is the optimal value. Moreover, if $f$ satisfies the Polyak–Łojasiewicz condition globally on the manifold, we establish a complexity bound of $\mathcal{O}(\log ({\epsilon }^{-1}))$, provided that the norm of the initial Riemannian gradient is sufficiently large. For the manifold of symmetric positive definite matrices, we construct a family of nonconvex functions satisfying the PL condition. Numerical experiments illustrate the remarkable performance of $\text{textsc}MAdaGrad$ in comparison with Riemannian Steepest Descent equipped with Armijo line-search.