Global rates of convergence for nonconvex optimization on manifolds

Journal article

We consider the minimization of a cost function $f$ on a manifold $M$ using Riemannian gradient descent and Riemannian trust regions (RTR). We focus on satisfying necessary optimality conditions within a tolerance $\varepsilon$. Specifically, we show that, under Lipschitz-type assumptions on the pullbacks of $f$ to the tangent spaces of $M$, both of these algorithms produce points with Riemannian gradient smaller than $\varepsilon$ in $O(1/\varepsilon^2)$ iterations. Furthermore, RTR returns a point where also the Riemannian Hessian's least eigenvalue is larger than -$\varepsilon$ in $O(1/\varepsilon^3)$ iterations. There are no assumptions on initialization. The rates match their (sharp) unconstrained counterparts as a function of the accuracy $\varepsilon$ (up to constants) and hence are sharp in that sense. These are the first general results for global rates of convergence to approximate first- and second-order KKT points on manifolds. They apply in particular for optimization constrained to compact submanifolds of $\mathbb{R}^n$, under simpler assumptions.

Authors: Boumal, N; Absil, P; Cartis, C

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Oxford University Press
• Journal: IMA Journal of Numerical Analysis
• Volume: 39
• Issue: 1
• Pages: 1–33
• Publication date: 2018-02-07
• Acceptance date: 2017-11-26
• DOI: 10.1093/imanum/drx080
• EISSN: 1464-3642
• ISSN: 0272-4979