# Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2014.

## Built on by (most cited first, 25 of 25)

- [QuIP: 2-Bit Quantization of Large Language Models With Guarantees](https://mlsanity.com/paper/2307.13304/) (2023)
- [A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups](https://mlsanity.com/paper/2104.09459/) (2021)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Preference Dynamics Under Personalized Recommendations](https://mlsanity.com/paper/2205.13026/) (2022)
- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [On the Optimality of the Oja's Algorithm for Online PCA](https://mlsanity.com/paper/2104.00512/) (2021)
- [Bootstrapping the error of Oja's algorithm](https://mlsanity.com/paper/2106.14857/) (2021)
- [Global Optimality in Bivariate Gradient-based DAG Learning](https://mlsanity.com/paper/2306.17378/) (2023)
- [Implicit Regularization of Sharpness-Aware Minimization for Scale-Invariant Problems](https://mlsanity.com/paper/2410.14802/) (2024)
- [A Novel Stochastic Gradient Descent Algorithm for Learning Principal Subspaces](https://mlsanity.com/paper/2212.04025/) (2022)
- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [Rank-one matrix estimation: analytic time evolution of gradient descent dynamics](https://mlsanity.com/paper/2105.12257/) (2021)
- [From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent](https://mlsanity.com/paper/2210.06705/) (2022)
- [Matrix Completion in Almost-Verification Time](https://mlsanity.com/paper/2308.03661/) (2023)
- [Riemannian Perspective on Matrix Factorization](https://mlsanity.com/paper/2102.00937/) (2021)
- [Learning Stochastic Optimal Policies via Gradient Descent](https://mlsanity.com/paper/2106.03780/) (2021)
- [Low-Precision Streaming PCA](https://mlsanity.com/paper/2510.22440/) (2025)
- [Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting](https://mlsanity.com/paper/2602.05887/) (2026)
- [Demystifying the Myths and Legends of Nonconvex Convergence of SGD](https://mlsanity.com/paper/2310.12969/) (2023)
- [Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy](https://mlsanity.com/paper/2609.26508/) (2026)
- [Non-Gradient Manifold Neural Network](https://mlsanity.com/paper/2106.07905/) (2021)
- [AgFlow: Fast Model Selection of Penalized PCA via Implicit Regularization Effects of Gradient Flow](https://mlsanity.com/paper/2110.03273/) (2021)
- [k-SVD with Gradient Descent](https://mlsanity.com/paper/2502.00320/) (2025)
- [Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation](https://mlsanity.com/paper/2505.10882/) (2025)
- [PEIRA: Learning Predictive Encoders through Inter-View Regressor Alignment](https://mlsanity.com/paper/2605.17671/) (2026)

## Abstract (arXiv)

Stochastic gradient descent (SGD) on a low-rank factorization is commonly employed to speed up matrix problems including matrix completion, subspace tracking, and SDP relaxation. In this paper, we exhibit a step size scheme for SGD on a low-rank least-squares problem, and we prove that, under broad sampling conditions, our method converges globally from a random starting point within O(ε-1 n log n) steps with constant probability for constant-rank problems. Our modification of SGD relates it to stochastic power iteration. We also show experiments to illustrate the runtime and convergence of the algorithm.