A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees

Abstract

We describe a line-search algorithm which achieves the best-known worst-case complexity results for problems with a certain "strict saddle" property that has been observed to hold in low-rank matrix optimization problems. Our algorithm is adaptive, in the sense that it makes use of backtracking line searches and does not require prior knowledge of the parameters that define the strict saddle property.

References in corpus (7)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Guaranteed Matrix Completion via Non-convex Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• When Are Nonconvex Problems Not Scary?
• The Global Optimization Geometry of Low-Rank Matrix Optimization

Cited by in corpus (1)

• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization