  The difficulty of minimizing a nonconvex function is in part explained by the
presence of saddle points. This slows down optimization algorithms and impacts
worst-case complexity guarantees. However, many nonconvex problems of interest
possess a favorable structure for optimization, in the sense that saddle points
can be escaped efficiently by appropriate algorithms. This strict saddle
property has been extensively used in data science to derive good properties
for first-order algorithms, such as convergence to second-order critical
points. However, the analysis and the design of second-order algorithms in the
strict saddle setting have received significantly less attention. In this
paper, we consider second-order trust-region methods for a class of strict
saddle functions defined on Riemannian manifolds. These functions exhibit
(geodesic) strong convexity around minimizers and negative curvature at saddle
points. We show that the standard trust-region method with exact subproblem
minimization finds an approximate local minimizer in a number of iterations
that depends logarithmically on the accuracy parameter, which significantly
improves known results for general nonconvex optimization. We also propose an
inexact variant of the algorithm that explicitly leverages the strict saddle
property to compute the most appropriate step at every iteration. Our bounds
for the inexact variant also improve over the general nonconvex case, and
illustrate the benefit of using strict saddle properties within optimization
algorithms. Keywords: Riemannian optimization, strict saddle function,
second-order method, complexity guarantees.
