Global Convergence Analysis of Vanilla Gradient Descent for Asymmetric Matrix Completion
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908487782498304 |
|---|---|
| author | Zhang, Xu Chen, Shuo Li, Jinsheng Pang, Xiangying Gong, Maoguo |
| author_facet | Zhang, Xu Chen, Shuo Li, Jinsheng Pang, Xiangying Gong, Maoguo |
| contents | This paper investigates the asymmetric low-rank matrix completion problem, which can be formulated as an unconstrained non-convex optimization problem with a nonlinear least-squares objective function, and is solved via gradient descent methods. Previous gradient descent approaches typically incorporate regularization terms into the objective function to guarantee convergence. However, numerical experiments and theoretical analysis of the gradient flow both demonstrate that the elimination of regularization terms in gradient descent algorithms does not adversely affect convergence performance. By introducing the leave-one-out technique, we inductively prove that the vanilla gradient descent with spectral initialization achieves a linear convergence rate with high probability. Besides, we demonstrate that the balancing regularization term exhibits a small norm during iterations, which reveals the implicit regularization property of gradient descent. Empirical results show that our algorithm has a lower computational cost while maintaining comparable completion performance compared to other gradient descent algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09685 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Global Convergence Analysis of Vanilla Gradient Descent for Asymmetric Matrix Completion Zhang, Xu Chen, Shuo Li, Jinsheng Pang, Xiangying Gong, Maoguo Machine Learning Information Theory This paper investigates the asymmetric low-rank matrix completion problem, which can be formulated as an unconstrained non-convex optimization problem with a nonlinear least-squares objective function, and is solved via gradient descent methods. Previous gradient descent approaches typically incorporate regularization terms into the objective function to guarantee convergence. However, numerical experiments and theoretical analysis of the gradient flow both demonstrate that the elimination of regularization terms in gradient descent algorithms does not adversely affect convergence performance. By introducing the leave-one-out technique, we inductively prove that the vanilla gradient descent with spectral initialization achieves a linear convergence rate with high probability. Besides, we demonstrate that the balancing regularization term exhibits a small norm during iterations, which reveals the implicit regularization property of gradient descent. Empirical results show that our algorithm has a lower computational cost while maintaining comparable completion performance compared to other gradient descent algorithms. |
| title | Global Convergence Analysis of Vanilla Gradient Descent for Asymmetric Matrix Completion |
| topic | Machine Learning Information Theory |
| url | https://arxiv.org/abs/2508.09685 |