mlsanityData to 14 Oct 2026

Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Points

arXiv 2302.07828 ↗First posted 15 Feb 2023math.OC cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

This paper studies the role of over-parametrization in solving non-convex optimization problems. The focus is on the important class of low-rank matrix sensing, where we propose an infinite hierarchy of non-convex problems via the lifting technique and the Burer-Monteiro factorization. This contrasts with the existing over-parametrization technique where the search rank is limited by the dimension of the matrix and it does not allow a rich over-parametrization of an arbitrary degree. We show that although the spurious solutions of the problem remain stationary points through the hierarchy, they will be transformed into strict saddle points (under some technical conditions) and can be escaped via local search methods. This is the first result in the literature showing that over-parametrization creates a negative curvature for escaping spurious solutions. We also derive a bound on how much over-parametrization is requited to enable the elimination of spurious solutions.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 23 of its 45 references that are in the map. First posted on arXiv 15 Feb 2023.

Builds on

23 of 45 references.

References · 23

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2020Scaling Laws for Neural Language Modelscited by 6,586
  3. 2022Training Compute-Optimal Large Language Modelscited by 3,019
  4. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  5. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  6. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 413
  7. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  8. 2019Two models of double descent for weak featurescited by 195
  9. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  10. 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 142
  11. 2022A Solvable Model of Neural Scaling Lawscited by 116
  12. 2016Nonconvex phase synchronizationcited by 30
11 more
  1. 2019Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recoverycited by 27
  2. 2022The effect of smooth parametrizations on nonconvex optimization landscapescited by 21
  3. 2019The Kikuchi Hierarchy and Tensor PCAcited by 15
  4. 2018Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysiscited by 13
  5. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  6. 2021General Low-rank Matrix Optimization: Geometric Analysis and Sharper Boundscited by 12
  7. 2022Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Ratecited by 8
  8. 2021Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurementscited by 7
  9. 2017Conic Relaxations for Power System State Estimation with Line Measurementscited by 5
  10. 2022Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensingcited by 5
  11. 2018An equivalence between critical points for rank constraints versus low-rank factorizationscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 1; 2025: 0; 2026: 3.

5 papers.

  1. 2026Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Liftingcited by 3
  2. 2026Low-Rank Adaptation Redux for Large Modelscited by 3
  3. 2023Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensingcited by 1
  4. 2024Absence of spurious solutions far from ground truth: A low-rank analysis with high-order lossescited by 1
  5. 2026Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamicscited by 0