Analysis of asymptotic escape of strict saddle sets in manifold optimization

DOI10.1137/19M129437XzbMATH Open1486.90155arXiv1911.12518OpenAlexW3088502654MaRDI QIDQ5037575FDOQ5037575

Authors: Zhenzhen Li, Thomas Y. Hou, Zi-Yun Zhang 

Publication date: 1 March 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1911.12518

Recommendations

• Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
• On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
• Behavior of accelerated gradient methods near critical points of nonconvex functions
• Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
• A Newton-based method for nonconvex optimization with fast evasion of saddle points

zbMATH Keywords

phase retrievalstable manifold theoremmanifold optimizationprojected gradient descentstrict saddles

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Iterative numerical methods for linear systems (65F10) Invariant manifold theory for dynamical systems (37D10)

Cites Work

• The Geometry of Algorithms with Orthogonality Constraints
• Title not available (Why is that?)
• Optimization Techniques on Riemannian Manifolds
• Efficient rank reduction of correlation matrices
• Compressed modes for variational problems in mathematics and physics
• Title not available (Why is that?)
• Low-rank tensor completion by Riemannian optimization
• Title not available (Why is that?)
• Online learning in the embedded manifold of low-rank matrices
• Critical points of matrix least squares distance functions
• Diffuse Interface Models on Graphs for Classification of High Dimensional Data
• Low-rank matrix completion by Riemannian optimization
• On the Number of Solutions to Polynomial Systems of Equations
• Data-driven tight frame construction and image denoising
• Information-theoretic differential geometry of quantum phase transitions
• An Extrinsic Look at the Riemannian Hessian
• Riemannian structure on manifolds of quantum states
• Morse-Bott homology
• On manifolds of tensors of fixed TT-rank
• Dynamical Low‐Rank Approximation
• Feature selection and multi-kernel learning for sparse representation on a manifold
• Empirical Arithmetic Averaging Over the Compact Stiefel Manifold
• Optimization on the hierarchical Tucker manifold - applications to tensor completion
• Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality
• Time integration of tensor trains
• Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
• Natural gradient via optimal transport
• A fast hierarchically preconditioned eigensolver based on multiresolution matrix decomposition
• Sobolev gradient flow for the Gross-Pitaevskii eigenvalue problem: global convergence and computational efficiency
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guarantees of Riemannian optimization for low rank matrix recovery
• Solving polynomial systems
• A geometric analysis of phase retrieval
• Low dimensional manifold model for image processing
• Bose-Einstein condensation and superfluidity
• Welcome to Riemannian computing in computer vision
• Gradient descent only converges to minimizers: non-isolated critical points and invariant regions
• Toward the Optimal Construction of a Loss Function Without Spurious Local Minima for Solving Quadratic Equations
• Blind deconvolution by a steepest descent algorithm on a quotient manifold
• Exact guarantees on the absence of spurious local minima for non-negative rank-1 robust principal component analysis
• 3D Point Cloud Denoising Using Graph Laplacian Regularization of a Low Dimensional Manifold Model

Cited In (1)

• Escaping strict saddle points of the Moreau envelope in nonsmooth optimization

This page was built for publication: Analysis of asymptotic escape of strict saddle sets in manifold optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5037575)