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

2020/06/14 by Michael O’Neill, Stephen J. Wright, O'Neill, Michael +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2006.07925

openalex publication_date 2020/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Citations

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified\n Geometric Analysis
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Cited by

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

Related

• Convergence and Cycling in Walker-type Saddle Search Algorithms
• Complexity analysis of second-order line-search algorithms for smooth\n nonconvex optimization
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Adaptive Backtracking Line Search
• Finding the saddlepoint faster than sorting