Absence of spurious solutions far from ground truth: A low-rank analysis with high-order losses
Not on the map. Why?
Abstract (arXiv)
Matrix sensing problems exhibit pervasive non-convexity, plaguing optimization with a proliferation of suboptimal spurious solutions. Avoiding convergence to these critical points poses a major challenge. This work provides new theoretical insights that help demystify the intricacies of the non-convex landscape. In this work, we prove that under certain conditions, critical points sufficiently distant from the ground truth matrix exhibit favorable geometry by being strict saddle points rather than troublesome local minima. Moreover, we introduce the notion of higher-order losses for the matrix sensing problem and show that the incorporation of such losses into the objective function amplifies the negative curvature around those distant critical points. This implies that increasing the complexity of the objective function via high-order losses accelerates the escape from such critical points and acts as a desirable alternative to increasing the complexity of the optimization problem via over-parametrization. By elucidating key characteristics of the non-convex optimization landscape, this work makes progress towards a comprehensive framework for tackling broader machine learning objectives plagued by non-convexity.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 19 of its 47 references that are in the map. First posted on arXiv 10 Mar 2024.
Builds on
19 of 47 references.
References · 19
- 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
- 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
- 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
- 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 40
- 2017Global Optimality in Low-rank Matrix Optimizationcited by 35
- 2016Nonconvex phase synchronizationcited by 30
- 2019Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recoverycited by 26
- 2016A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimationcited by 21
- 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
- 2018Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysiscited by 13
- 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
- 2021General Low-rank Matrix Optimization: Geometric Analysis and Sharper Boundscited by 12
7 more
- 2020How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?cited by 10
- 2021Local and Global Linear Convergence of General Low-rank Matrix Recovery Problemscited by 8
- 2021Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurementscited by 7
- 2022Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Ratecited by 7
- 2017Conic Relaxations for Power System State Estimation with Line Measurementscited by 5
- 2022Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensingcited by 5
- 2023Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Pointscited by 5
Built on by
Citing papers per year: 2026: 1.
1 paper.