Worst-case complexity for the minimization of strict saddle functions

Many problems in data science can be expressed as the minimization of a strict-saddle function. Strict saddle functions are in general nonconvex, but have the property that the Hessian has a negative eigenvalue at every saddle point. Using this information on the landscape, we design an efficient and specific algorithms for the minimisation of strict saddle functions. We derive guarantees on the number of iterations that have to be performed in the worst-case before an approximate minimizer of the function is reached.  We show how our algorithm improves on the classical complexity results of nonconvex optimization. This is joint work with Clément Royer.