mlsanityData to 7 Oct 2026

Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees

arXiv 1509.03025 ↗First posted 10 Sep 2015math.ST cs.LG stat.MLcited by 68

Not on the map. Why?

Abstract (arXiv)

Optimization problems with rank constraints arise in many applications, including matrix regression, structured PCA, matrix completion and matrix decomposition problems. An attractive heuristic for solving such problems is to factorize the low-rank matrix, and to run projected gradient descent on the nonconvex factorized optimization problem. The goal of this problem is to provide a general theoretical framework for understanding when such methods work well, and to characterize the nature of the resulting fixed point. We provide a simple set of conditions under which projected gradient descent, when given a suitable initialization, converges geometrically to a statistically useful solution. Our results are applicable even when the initial solution is outside any region of local convexity, and even when the problem is globally concave. Working in a non-asymptotic framework, we show that our conditions are satisfied for a wide range of concrete models, including matrix regression, structured PCA, matrix completion with real and quantized observations, matrix decomposition, and graph clustering problems. Simulation results show excellent agreement with the theoretical predictions.

Key facts. Cited by 68 papers in the map (data through 7 Oct 2026). First posted on arXiv 10 Sep 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 14; 2023: 12; 2024: 12; 2025: 11; 2026: 2.

68 papers.

Sort:

By area:

  1. 2024GaLore: Memory-Efficient LLM Training by Gradient Low-Rank Projectioncited by 447
  2. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 48
  3. 2024Fira: Can We Achieve Full-rank Training of LLMs Under Low-rank Constraint?cited by 39
  4. 2023PDPP: Projected Diffusion for Procedure Planning in Instructional Videoscited by 36
  5. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  6. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  7. 2021Mind Mappings: Enabling Efficient Algorithm-Accelerator Mapping Space Searchcited by 24
  8. 2022Convergence of gradient descent for deep neural networkscited by 24
  9. 2021Inference for Heteroskedastic PCA with Missing Datacited by 21
  10. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  11. 2024VeLoRA: Memory Efficient Training using Rank-1 Sub-Token Projectionscited by 18
  12. 2021Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorizationcited by 15
38 more
  1. 2021Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approachcited by 14
  2. 2024Propulsion: Steering LLM with Tiny Fine-Tuningcited by 14
  3. 2023Subspace based Federated Unlearningcited by 13
  4. 2022Federated Learning and Meta Learning: Approaches, Applications, and Directionscited by 12
  5. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  6. 2021Implicit Regularization in Matrix Sensing via Mirror Descentcited by 11
  7. 2024Gradient Weight-normalized Low-rank Projection for Efficient LLM Trainingcited by 11
  8. 2021Multi-source Learning via Completion of Block-wise Overlapping Noisy Matricescited by 10
  9. 2024Parameter-Efficient Fine-Tuning of Large Language Models using Semantic Knowledge Tuningcited by 10
  10. 2023Approximate message passing from random initialization with applications to mathbbZ2 synchronizationcited by 9
  11. 2022A Validation Approach to Over-parameterized Matrix and Image Recoverycited by 8
  12. 2024COAP: Memory-Efficient Training with Correlation-Aware Gradient Projectioncited by 8
  13. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
  14. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  15. 2022Towards a Theoretical Foundation of Policy Optimization for Learning Control Policiescited by 6
  16. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  17. 2024Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completioncited by 6
  18. 2021Fast quantum state reconstruction via accelerated non-convex programmingcited by 5
  19. 2022Model-free Neural Lyapunov Control for Safe Robot Navigationcited by 5
  20. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  21. 2025Riemannian Optimization on Relaxed Indicator Matrix Manifoldcited by 5
  22. 2022Robust Matrix Completion with Heavy-tailed Noisecited by 4
  23. 2022Rank-1 Matrix Completion with Gradient Descent and Small Random Initializationcited by 4
  24. 2023Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regressioncited by 4
  25. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  26. 2021Riemannian Perspective on Matrix Factorizationcited by 3
  27. 2021Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descentcited by 3
  28. 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 3
  29. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 3
  30. 2023Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regretcited by 3
  31. 2023Gradient-Based Spectral Embeddings of Random Dot Product Graphscited by 3
  32. 2025One Rank at a Time: Cascading Error Dynamics in Sequential Learningcited by 3
  33. 2021Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensingcited by 2
  34. 2021On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squarescited by 2
  35. 2022Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problemscited by 2
  36. 2026Low-Rank Adaptation Redux for Large Modelscited by 2
  37. 2021Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recoverycited by 1
  38. 2022An Exponentially Increasing Step-size for Parameter Estimation in Statistical Modelscited by 1

50 most cited of 68 All 68 (JSON)