Convergence Rates of Factorized Gradient Descent for Overparameterized Asymmetric Matrix Sensing with Balancing Regularization

Abstract

We study factorized gradient descent (FGD) for overparameterized asymmetric matrix sensing with the balancing regularizer $\frac{1}{8}\Vert L^{\top }L-R^{\top }R{\Vert }_F^2$. An exact indefinite lifting of the population objective decomposes the dynamics of FGD into positive, negative, and null spectral subspaces. The first two components have linear restoring terms, whereas the null component contracts only quadratically. For independent isotropic sub-Gaussian sensing matrices and independent centered sub-Gaussian noise with scale proxy $\sigma$, we prove the local bound \[ \|L_tR_t^\top-X^\star\|_2 \lesssim\max\left\{\frac{1}{ηt+1/σ_r}, κσ\sqrt{\frac{d_1+d_2}{n}}\right\}, \] under a sufficiently small initialization error, the number of linear measurements $n\gtrsim {\kappa }^2(d_1+d_2)\max \{k^2,{\sigma }^2/{\sigma }_r^2\}$, and step size $\eta \lesssim {\sigma }_1^{-1}$. Here ${\sigma }_1$ and ${\sigma }_r$ are the largest and smallest nonzero singular values of the target $X^{\star }\in {\mathbb{R}}^{d_1\times d_2}$ respectively, and $\kappa ={\sigma }_1/{\sigma }_r$. Furthermore, a population trajectory was constructed to have tight product error $\Theta (1/t)$. These results provide a local rate characterization for ordinary gradient descent for overparameterized asymmetric matrix sensing with balancing regularizer.