# Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview

arXiv: https://arxiv.org/abs/1809.09573 · HTML: https://mlsanity.com/paper/1809.09573/

## Key facts

- Cited by 160 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2018.

## Built on by (most cited first, 30 of 160)

- [Exploiting Shared Representations for Personalized Federated Learning](https://mlsanity.com/paper/2102.07078/) (2021)
- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications](https://mlsanity.com/paper/2111.12444/) (2021)
- [On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Features](https://mlsanity.com/paper/2203.01238/) (2022)
- [Robust Training under Label Noise by Over-parameterization](https://mlsanity.com/paper/2202.14026/) (2022)
- [Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction](https://mlsanity.com/paper/2206.07085/) (2022)
- [Are All Losses Created Equal: A Neural Collapse Perspective](https://mlsanity.com/paper/2210.02192/) (2022)
- [Initialization and Regularization of Factorized Neural Layers](https://mlsanity.com/paper/2105.01029/) (2021)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [The SSL Interplay: Augmentations, Inductive Bias, and Generalization](https://mlsanity.com/paper/2302.02774/) (2023)
- [On the Stepwise Nature of Self-Supervised Learning](https://mlsanity.com/paper/2303.15438/) (2023)
- [Perturbation Analysis of Neural Collapse](https://mlsanity.com/paper/2210.16658/) (2022)
- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [Hessian Eigenspectra of More Realistic Nonlinear Models](https://mlsanity.com/paper/2103.01519/) (2021)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Preconditioning Benefits of Spectral Orthogonalization in Muon](https://mlsanity.com/paper/2601.13474/) (2026)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Geometry of Linear Convolutional Networks](https://mlsanity.com/paper/2108.01538/) (2021)
- [Subquadratic Overparameterization for Shallow Neural Networks](https://mlsanity.com/paper/2111.01875/) (2021)
- [Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptation](https://mlsanity.com/paper/2406.04112/) (2024)
- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [The Law of Parsimony in Gradient Descent for Learning Deep Linear Networks](https://mlsanity.com/paper/2306.01154/) (2023)
- [Convergence of Random Reshuffling Under The Kurdyka-Lojasiewicz Inequality](https://mlsanity.com/paper/2110.04926/) (2021)
- [Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization](https://mlsanity.com/paper/2102.12430/) (2021)
- [On Speeding Up Language Model Evaluation](https://mlsanity.com/paper/2407.06172/) (2024)

## Abstract (arXiv)

Substantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. While conventional wisdom often takes a dim view of nonconvex optimization algorithms due to their susceptibility to spurious local minima, simple iterative methods such as gradient descent have been remarkably successful in practice. The theoretical footings, however, had been largely lacking until recently. In this tutorial-style overview, we highlight the important role of statistical models in enabling efficient nonconvex optimization with performance guarantees. We review two contrasting approaches: (1) two-stage algorithms, which consist of a tailored initialization step followed by successive refinement; and (2) global landscape analysis and initialization-free algorithms. Several canonical matrix factorization problems are discussed, including but not limited to matrix sensing, phase retrieval, matrix completion, blind deconvolution, robust principal component analysis, phase synchronization, and joint alignment. Special care is taken to illustrate the key technical insights underlying their analyses. This article serves as a testament that the integrated consideration of optimization and statistics leads to fruitful research findings.