Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization

Abstract

In this paper, we provide some analysis on the asymptotic escape of strict saddles in manifold optimization using the projected gradient descent (PGD) algorithm. One of our main contributions is that we extend the current analysis to include non-isolated and possibly continuous saddle sets with complicated geometry. We prove that the PGD is able to escape strict critical submanifolds under certain conditions on the geometry and the distribution of the saddle point sets. We also show that the PGD may fail to escape strict saddles under weaker assumptions even if the saddle point set has zero measure and there is a uniform escape direction. We provide a counterexample to illustrate this important point. We apply this saddle analysis to the phase retrieval problem on the low-rank matrix manifold, prove that there are only a finite number of saddles, and they are strict saddles with high probability. We also show the potential application of our analysis for a broader range of manifold optimization problems.

References in corpus (14)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Compressed Modes for Variational Problems in Mathematics and Physics
• Classifying and measuring the geometry of the quantum ground state manifold
• Gradient Descent Converges to Minimizers
• Low-rank tensor completion: a Riemannian manifold preconditioning approach
• First-order Methods Almost Always Avoid Saddle Points
• Why Use Sobolev Metrics on the Space of Curves
• Efficiently escaping saddle points on manifolds
• Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis
• Escaping from saddle points on Riemannian manifolds
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• Optimization on flag manifolds

Cited by in corpus (2)

• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• Asymptotic Escape of Spurious Critical Points on the Low-rank Matrix Manifold