Research map / Optimization / Implicit bias and generalization
Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
Tian Tong, Cong Ma, Yuejie Chi
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace vanilla GD with ScaledGD (right-preconditioning of the factor gradients) | factored low-rank matrix sensing, robust PCA, matrix completion · Table 1 theory, spectral initialization | iteration complexity: kappa log(1/epsilon) -> log(1/epsilon) | Improved |
| use ScaledGD instead of vanilla GD as condition number kappa grows (1,5,10,20) | matrix sensing, robust PCA, matrix completion, Hankel completion · noise-free synthetic | relative error vs iterations | Improved |
| add observation noise at SNR 40, 60, 80 dB with ScaledGD | ScaledGD · synthetic, kappa=10 | final statistical error and convergence speed | No clear effect |
| vary step size eta from 0.1 to 1.2 for ScaledGD versus vanilla GD (ablation) | matrix completion, n=1000, r=10, p=0.2 · synthetic | relative error after 80 iterations | Improved |
| use ScaledGD instead of alternating minimization | matrix sensing n=200 and matrix completion n=1000 · run time, kappa=1,5,20 | run time | Improved |
Closest papers by meaning
- The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing (ICML 2023 · similarity 0.92)
- Guaranteed Nonconvex Low-Rank Tensor Estimation via Scaled Gradient Descent (JMLR 2026 · similarity 0.91)
- A Unified Variance Reduction-Based Framework for Nonconvex Low-Rank Matrix Recovery (ICML 2017 · similarity 0.90)
- Preconditioning Matters: Fast Global Convergence of Non-convex Matrix Factorization via Scaled Gradient Descent (NeurIPS 2023 · similarity 0.90)
- How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization (ICLR 2024 · similarity 0.88)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
