CaltechAUTHORS
  A Caltech Library Service

Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization

Hou, Thomas Y. and Li, Zhenzhen and Zhang, Ziyun (2019) Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20200122-133158689

[img] PDF - Submitted Version
See Usage Policy.

1MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200122-133158689

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1911.12518arXivDiscussion Paper
Additional Information:The research was in part supported by NSF Grants DMS-1613861, DMS-1907977 and DMS-1912654.
Funders:
Funding AgencyGrant Number
NSFDMS-1613861
NSFDMS-1907977
NSFDMS-1912654
Subject Keywords:Manifold optimization, projected gradient descent, strict saddles, stable manifold theorem, phase retrieval
Classification Code:AMS subject classifications: 58D17, 37D10, 65F10, 90C26
DOI:10.48550/arXiv.1911.12518
Record Number:CaltechAUTHORS:20200122-133158689
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200122-133158689
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100844
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:22 Jan 2020 22:02
Last Modified:02 Jun 2023 01:02

Repository Staff Only: item control page