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 1/8|L⊤ L−R⊤ R|F2. 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 σ, we prove the local bound |LtRt⊤−X⋆|2 ≲max{1/(ηt+1/σr), κσ√((d1+d2)/n)}, under a sufficiently small initialization error, the number of linear measurements n≳κ2(d1+d2)max{k2,σ2/σr2}, and step size η≲σ1−1. Here σ1 and σr are the largest and smallest nonzero singular values of the target X⋆∈ ℝd1× d2 respectively, and κ=σ1/σr. Furthermore, a population trajectory was constructed to have tight product error Θ(1/t). These results provide a local rate characterization for ordinary gradient descent for overparameterized asymmetric matrix sensing with balancing regularizer.
Related
- Convergence Analysis of Newton's Method for Neural Networks in the Overparameterized Limit
- Strong convergence of a slowly damped primal-dual dynamical system with general time-scaling, Tikhonov regularization and implicit Hessian damping
- Convergence rates of mixed primal-dual dynamical systems with implicit Hessian damping and Tikhonov regularization
- Finite-Data Error Bounds for Approximating the Koopman Operator: Sampling Measures, Super-Polynomial Convergence and Regularization
- Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter
BibTeX
@misc{chen2026convergence,
title = {{Convergence Rates of Factorized Gradient Descent for Overparameterized Asymmetric Matrix Sensing with Balancing Regularization}},
author = {Yongjun Chen and Jiaming Zhang and Liping Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19477},
eprint = {2610.19477},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19477},
}
RIS
TY - UNPB
TI - Convergence Rates of Factorized Gradient Descent for Overparameterized Asymmetric Matrix Sensing with Balancing Regularization
AU - Yongjun Chen
AU - Jiaming Zhang
AU - Liping Zhang
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19477
UR - https://arxiv.org/abs/2610.19477
AB - We study factorized gradient descent (FGD) for overparameterized asymmetric matrix sensing with the balancing regularizer 1/8|L^⊤ L−R^⊤ R|_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 σ, we prove the local bound |L_tR_t^⊤−X^⋆|_2 ≲max{1/(ηt+1/σ_r), κσ√((d_1+d_2)/n)}, under a sufficiently small initialization error, the number of linear measurements n≳κ^2(d_1+d_2)max{k^2,σ^2/σ_r^2}, and step size η≲σ_1^−1. Here σ_1 and σ_r are the largest and smallest nonzero singular values of the target X^⋆∈ ℝ^d_1× d_2 respectively, and κ=σ_1/σ_r. Furthermore, a population trajectory was constructed to have tight product error Θ(1/t). These results provide a local rate characterization for ordinary gradient descent for overparameterized asymmetric matrix sensing with balancing regularizer.
ER -