  Adaptive regularization with cubics (ARC) is an algorithm for unconstrained,
non-convex optimization. Akin to the popular trust-region method, its
iterations can be thought of as approximate, safe-guarded Newton steps. For
cost functions with Lipschitz continuous Hessian, ARC has optimal iteration
complexity, in the sense that it produces an iterate with gradient smaller than
$\varepsilon$ in $O(1/\varepsilon^{1.5})$ iterations. For the same price, it
can also guarantee a Hessian with smallest eigenvalue larger than
$-\varepsilon^{1/2}$. In this paper, we study a generalization of ARC to
optimization on Riemannian manifolds. In particular, we generalize the
iteration complexity results to this richer framework. Our central contribution
lies in the identification of appropriate manifold-specific assumptions that
allow us to secure these complexity guarantees both when using the exponential
map and when using a general retraction. A substantial part of the paper is
devoted to studying these assumptions---relevant beyond ARC---and providing
user-friendly sufficient conditions for them. Numerical experiments are
encouraging.
