Riemannian trust-region methods for strict saddle functions with complexity guarantees

Understand

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.