mlsanityData to 14 Oct 2026

Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting

arXiv 2602.05887 ↗First posted 5 Feb 2026cs.LG math.OCcited by 3

Not on the map. Why?

Abstract (arXiv)

Low-rank matrix sensing is a fundamental yet challenging nonconvex problem whose optimization landscape typically contains numerous spurious local minima, making it difficult for gradient-based optimizers to converge to the global optimum. Recent work has shown that over-parameterization via tensor lifting can convert such local minima into strict saddle points, an insight that also partially explains why massive scaling can improve generalization and performance in modern machine learning. Motivated by this observation, we propose a Simulated Oracle Direction (SOD) escape mechanism that simulates the landscape and escape direction of the over-parametrized space, without resorting to actually lifting the problem, since that would be computationally intractable. In essence, we designed a mathematical framework to project over-parametrized escape directions onto the original parameter space to guarantee a strict decrease of objective value from existing local minima. To the best of our knowledge, this represents the first deterministic framework that could escape spurious local minima with guarantee, especially without using random perturbations or heuristic estimates. Numerical experiments demonstrate that our framework reliably escapes local minima and facilitates convergence to global optima, while incurring minimal computational cost when compared to explicit tensor over-parameterization. We believe this framework has non-trivial implications for nonconvex optimization beyond matrix sensing, by showcasing how simulated over-parameterization can be leveraged to tame challenging optimization landscapes.

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

Builds on

44 of 91 references.

References · 44

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2020Scaling Laws for Neural Language Modelscited by 6,586
  3. 2021Convex optimizationcited by 2,515
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  6. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  7. 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 289
  8. 2017How to Escape Saddle Points Efficientlycited by 285
  9. 2017The Marginal Value of Adaptive Gradient Methods in Machine Learningcited by 250
  10. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 160
  11. 2017Non-convex Optimization for Machine Learningcited by 133
  12. 2021Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Trainingcited by 110
32 more
  1. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  2. 2025Fantastic Pretraining Optimizers and Where to Find Themcited by 100
  3. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 78
  4. 2017The loss surface of deep and wide neural networkscited by 74
  5. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  6. 2020Recent Theoretical Advances in Non-Convex Optimizationcited by 30
  7. 2019Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recoverycited by 27
  8. 2014Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problemscited by 25
  9. 2016Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regressioncited by 23
  10. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  11. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  12. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  13. 2018Benefits of over-parameterization with EMcited by 10
  14. 2015Strong SOCP Relaxations for the Optimal Power Flow Problemcited by 9
  15. 2018How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?cited by 8
  16. 2022Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Ratecited by 8
  17. 2021Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methodscited by 6
  18. 2022Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensingcited by 5
  19. 2023Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Pointscited by 5
  20. 2025SecureReviewer: Enhancing Large Language Models for Secure Code Review through Secure-aware Fine-tuningcited by 5
  21. 2023Data-driven Piecewise Affine Decision Rules for Stochastic Programming with Covariate Informationcited by 4
  22. 2025Sensor network localization has a benign landscape after low-dimensional relaxationcited by 3
  23. 2025On the Benefits of Weight Normalization for Overparameterized Matrix Sensingcited by 3
  24. 2025Exploring Landscapes for Better Minima along Valleyscited by 3
  25. 2023Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?cited by 2
  26. 2024The Implicit Bias of Heterogeneity towards Invariance: A Study of Multi-Environment Matrix Sensingcited by 2
  27. 2025Understanding Overparametrization in Survival Models through Interpolationcited by 2
  28. 2015Interpolating Convex and Non-Convex Tensor Decompositions via the Subspace Normcited by 1
  29. 2022Deep Learning Generalization, Extrapolation, and Over-parameterizationcited by 1
  30. 2023Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensingcited by 1
  31. 2024Absence of spurious solutions far from ground truth: A low-rank analysis with high-order lossescited by 1
  32. 2025Phase retrieval and matrix sensing via benign and overparametrized nonconvex optimizationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamicscited by 0
  2. 2026VepAgent: Bridging Causal-Transition via Tool-Augmented Reinforcement Learning for Video Event Predictioncited by 0
  3. 2026X-Ragent: Tool-Augmented Reinforcement Learning for Evidence-Grounded Chest X-Ray Reasoningcited by 0