mlsanityData to 7 Oct 2026

The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing

arXiv 2302.01186 ↗First posted 2 Feb 2023cs.LG eess.SP math.OCcited by 32

Not on the map. Why?

Abstract (arXiv)

We propose textsfScaledGD(λ), a preconditioned gradient descent method to tackle the low-rank matrix sensing problem when the true rank is unknown, and when the matrix is possibly ill-conditioned. Using overparametrized factor representations, textsfScaledGD(λ) starts from a small random initialization, and proceeds by gradient descent with a specific form of damped preconditioning to combat bad curvatures induced by overparameterization and ill-conditioning. At the expense of light computational overhead incurred by preconditioners, textsfScaledGD(λ) is remarkably robust to ill-conditioning compared to vanilla gradient descent (textsfGD) even with overprameterization. Specifically, we show that, under the Gaussian design, textsfScaledGD(λ) converges to the true low-rank matrix at a constant linear rate after a small number of iterations that scales only logarithmically with respect to the condition number and the problem dimension. This significantly improves over the convergence rate of vanilla textsfGD which suffers from a polynomial dependency on the condition number. Our work provides evidence on the power of preconditioning in accelerating the convergence without hurting generalization in overparameterized learning.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). Builds on 32 of its 62 references that are in the map. First posted on arXiv 2 Feb 2023.

Builds on

32 of 62 references.

References · 32

  1. 2017Implicit Regularization in Matrix Factorizationcited by 318
  2. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  3. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  4. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
  5. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  6. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 87
  7. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  8. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  9. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
  10. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  11. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  12. 2015A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurementscited by 34
20 more
  1. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  2. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  3. 2020When Does Preconditioning Help or Hurt Generalization?cited by 30
  4. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  5. 2020Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Numbercited by 27
  6. 2018Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimationcited by 25
  7. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
  8. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  9. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  10. 2018Subgradient Descent Learns Orthogonal Dictionariescited by 17
  11. 2018Nonconvex Matrix Factorization from Rank-One Measurementscited by 13
  12. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  13. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  14. 2022Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descentcited by 11
  15. 2018Efficient Dictionary Learning with Gradient Descentcited by 10
  16. 2022Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initializationcited by 9
  17. 2019Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficientlycited by 6
  18. 2021Deep Networks Provably Classify Data on Curvescited by 6
  19. 2019A Nonconvex Approach for Exact and Efficient Multichannel Sparse Blind Deconvolutioncited by 5
  20. 2022Rank-1 Matrix Completion with Gradient Descent and Small Random Initializationcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 8; 2024: 9; 2025: 8; 2026: 7.

32 papers.

Sort:

  1. 2026Preconditioning Benefits of Spectral Orthogonalization in Muoncited by 28
  2. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  3. 2024On the Crucial Role of Initialization for Matrix Factorizationcited by 15
  4. 2023Canonical Factors for Hybrid Neural Fieldscited by 8
  5. 2024Guaranteed Nonconvex Factorization Approach for Tensor Train Recoverycited by 8
  6. 2025AltLoRA: Towards Better Gradient Approximation in Low-Rank Adaptation with Alternating Projectionscited by 8
  7. 2023Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCAcited by 7
  8. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
  9. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  10. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  11. 2024Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recoverycited by 4
  12. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
20 more
  1. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  2. 2024Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networkscited by 3
  3. 2025On the Benefits of Weight Normalization for Overparameterized Matrix Sensingcited by 3
  4. 2023Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?cited by 2
  5. 2023Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbationscited by 2
  6. 2024Improving Implicit Regularization of SGD with Preconditioning for Least Square Problemscited by 2
  7. 2024Robust Low-rank Tensor Train Recoverycited by 2
  8. 2024BLAST: Block-Level Adaptive Structured Matrices for Efficient Deep Neural Network Inferencecited by 2
  9. 2026Low-Rank Adaptation Redux for Large Modelscited by 2
  10. 2025Faster Than SVD, Smarter Than SGD: The OPLoRA Alternating Updatecited by 1
  11. 2025Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Trainingcited by 1
  12. 2023Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensingcited by 0
  13. 2025k-SVD with Gradient Descentcited by 0
  14. 2025RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guaranteescited by 0
  15. 2025Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappingscited by 0
  16. 2026Beyond SGD, Without SVD: Proximal Subspace Iteration LoRA with Diagonal Fractional K-FACcited by 0
  17. 2026Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Ratecited by 0
  18. 2026Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexitycited by 0
  19. 2026Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamicscited by 0
  20. 2026Reassessing Muon for Matrix Factorizationcited by 0