Reproduce “Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent” on OpenResearch

About this paper

Tian Tong, Cong Ma, Yuejie Chi

Researchers from Carnegie Mellon University and UC Berkeley introduce Scaled Gradient Descent (ScaledGD), an optimization algorithm for low-rank matrix estimation. ScaledGD achieves linear convergence independent of the underlying matrix's condition number, matching the iteration efficiency of Alternating Minimization while significantly reducing the per-iteration computational cost, leading to faster wall-clock times for various ill-conditioned problems.

Key insights

• A new distance metric is introduced that inherently accounts for preconditioning and the non-unique factorization of low-rank matrices, enabling rigorous analysis of convergence.
• ScaledGD implicitly maintains desirable properties of low-rank factors, such as incoherence and balancedness, without requiring explicit regularization terms or projection steps.
• The analytical framework for ScaledGD is generalizable to various low-rank matrix estimation problems and other loss functions satisfying restricted strong convexity and smoothness.

Summary by alphaXiv.