mlsanityData to 14 Oct 2026

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

arXiv 1411.1134 ↗First posted 5 Nov 2014cs.LG math.OC stat.MLcited by 25

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 10; 2022: 3; 2023: 4; 2024: 2; 2025: 3; 2026: 3.

25 papers.

Sort:

By area:

  1. 2023QuIP: 2-Bit Quantization of Large Language Models With Guaranteescited by 414
  2. 2021A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groupscited by 187
  3. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 130
  4. 2022Preference Dynamics Under Personalized Recommendationscited by 25
  5. 2021Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updatescited by 21
  6. 2021On the Optimality of the Oja's Algorithm for Online PCAcited by 11
  7. 2021Bootstrapping the error of Oja's algorithmcited by 11
  8. 2023Global Optimality in Bivariate Gradient-based DAG Learningcited by 10
  9. 2024Implicit Regularization of Sharpness-Aware Minimization for Scale-Invariant Problemscited by 10
  10. 2022A Novel Stochastic Gradient Descent Algorithm for Learning Principal Subspacescited by 7
  11. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  12. 2021Rank-one matrix estimation: analytic time evolution of gradient descent dynamicscited by 5
13 more
  1. 2022From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descentcited by 5
  2. 2023Matrix Completion in Almost-Verification Timecited by 4
  3. 2021Riemannian Perspective on Matrix Factorizationcited by 3
  4. 2021Learning Stochastic Optimal Policies via Gradient Descentcited by 3
  5. 2025Low-Precision Streaming PCAcited by 3
  6. 2026Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Liftingcited by 3
  7. 2023Demystifying the Myths and Legends of Nonconvex Convergence of SGDcited by 2
  8. 2026Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacycited by 1
  9. 2021Non-Gradient Manifold Neural Networkcited by 0
  10. 2021AgFlow: Fast Model Selection of Penalized PCA via Implicit Regularization Effects of Gradient Flowcited by 0
  11. 2025k-SVD with Gradient Descentcited by 0
  12. 2025Global Convergence of Adaptive Sensing for Principal Eigenvector Estimationcited by 0
  13. 2026PEIRA: Learning Predictive Encoders through Inter-View Regressor Alignmentcited by 0