Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points
Not on the map. Why?
Abstract (arXiv)
Motivated by the emerging role of interpolating machines in signal processing and machine learning, this work considers the computational aspects of over-parametrized matrix factorization. In this context, the optimization landscape may contain spurious stationary points (SSPs), which are proved to be full-rank matrices. The presence of these SSPs means that it is impossible to hope for any global guarantees in over-parametrized matrix factorization. For example, when initialized at an SSP, the gradient flow will be trapped there forever. Nevertheless, despite these SSPs, we establish in this work that the gradient flow of the corresponding merit function converges to a global minimizer, provided that its initialization is rank-deficient and sufficiently close to the feasible set of the optimization problem. We numerically observe that a heuristic discretization of the proposed gradient flow, inspired by primal-dual algorithms, is successful when initialized randomly. Our result is in sharp contrast with the local refinement methods which require an initialization close to the optimal set of the optimization problem. More specifically, we successfully avoid the traps set by the SSPs because the gradient flow remains rank-deficient at all times, and not because there are no SSPs nearby. The latter is the case for the local refinement methods. Moreover, the widely-used restricted isometry property plays no role in our main result.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 22 of its 52 references that are in the map. First posted on arXiv 25 Dec 2021.
Builds on
22 of 52 references.
References · 22
- 2016Understanding deep learning requires rethinking generalizationcited by 1,674
- 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
- 2018On Lazy Training in Differentiable Programmingcited by 675
- 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
- 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
- 2017Implicit Regularization in Matrix Factorizationcited by 322
- 2017How to Escape Saddle Points Efficientlycited by 285
- 2018To understand deep learning we need to understand kernel learningcited by 187
- 2018A Convergence Analysis of Gradient Descent for Deep Linear Neural Networkscited by 184
- 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
- 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 160
- 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
10 more
- 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
- 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
- 2016The non-convex Burer-Monteiro approach works on smooth semidefinite programscited by 46
- 2016Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regionscited by 34
- 2019An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraintscited by 29
- 2015Global Optimality in Tensor Factorization, Deep Learning, and Beyondcited by 22
- 2018Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programscited by 19
- 2020Training Linear Neural Networks: Non-Local Convergence and Complexity Resultscited by 19
- 2018Parallelizable Algorithms for Optimization Problems with Orthogonality Constraintscited by 16
- 2020Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entriescited by 10
Built on by
Citing papers per year: 2025: 1.
1 paper.