A Cubic Regularized Newton's Method over Riemannian Manifolds

Abstract

In this paper we present a cubic regularized Newton's method to minimize a smooth function over a Riemannian manifold. The proposed algorithm is shown to reach a second-order $\epsilon$-stationary point within $\mathcal{O}(1/{\epsilon }^{\frac{3}{2}})$ iterations, under the condition that the pullbacks are locally Lipschitz continuous, a condition that is shown to be satisfied if the manifold is compact. Furthermore, we present a local superlinear convergence result under some additional conditions.

References in corpus (8)

• Global rates of convergence for nonconvex optimization on manifolds
• First-order Methods Almost Always Avoid Saddle Points
• Gradient Descent Can Take Exponential Time to Escape Saddle Points
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
• Quadratic Optimization with Orthogonality Constraints: Explicit Lojasiewicz Exponent and Linear Convergence of Line-Search Methods
• Riemannian stochastic variance reduced gradient on Grassmann manifold
• A Grothendieck-type inequality for local maxima
• Block Coordinate Descent Only Converge to Minimizers

Cited by in corpus (9)

• Efficiently escaping saddle points on manifolds
• Escaping from saddle points on Riemannian manifolds
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• Simple algorithms for optimization on Riemannian manifolds with constraints
• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
• A Brief Introduction to Manifold Optimization
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem