Global rates of convergence for nonconvex optimization on manifolds

By Nicolas Boumal, Pierre-Antoine Absil, Coralia Cartis. 2016

359 citations recorded by the source corpus.

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 deterministic results for global rates of convergence to approximate first- and second-order Karush-Kuhn-Tucker points on manifolds. They apply in particular for optimization constrained to compact submanifolds of $\mathbb{R}^n$, under simpler assumptions.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/c26cc911ec12923af30ad485b4c93691a534960d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Bispectrum Inversion with Application to Multireference Alignment (2017, background): “RTR enjoys global convergence to second-order critical points [64] and a quadratic local convergence rate.”
SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group (2016, methodology): “Consequently, we propose to employ the truncated-Newton Riemannian Trust-Region (RTR) method [1, 9] to efficiently compute high-precision estimates of second-order critical points of Problem 4 in practice.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “Additionally, we note that it is possible to adapt many of the above mentioned saddle-point escaping algorithms onto manifolds; we refer the readers to [168, 187, 200].”
Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group (2019, background): “A study of the convergence properties of first and second-order optimization algorithms when using retractions can be found in (Boumal et al., 2016).”