Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
By Tian Ye, Simon Shaolei Du. 2021
60 citations recorded by the source corpus.
We study the asymmetric low-rank factorization problem: \[\min_{\mathbf{U} \in \mathbb{R}^{m \times d}, \mathbf{V} \in \mathbb{R}^{n \times d}} \frac{1}{2}\|\mathbf{U}\mathbf{V}^\top -\mathbf{\Sigma}\|_F^2\] where $\mathbf{\Sigma}$ is a given matrix of size $m \times n$ and rank $d$. This is a canonical problem that admits two difficulties in optimization: 1) non-convexity and 2) non-smoothness (due to unbalancedness of $\mathbf{U}$ and $\mathbf{V}$). This is also a prototype for more complex problems such as asymmetric matrix sensing and matrix completion. Despite being non-convex and non-smooth, it has been observed empirically that the randomly initialized gradient descent algorithm can solve this problem in polynomial time. Existing theories to explain this phenomenon all require artificial modifications of the algorithm, such as adding noise in each iteration and adding a balancing regularizer to balance the $\mathbf{U}$ and $\mathbf{V}$. This paper presents the first proof that shows randomly initialized gradient descent converges to a global minimum of the asymmetric low-rank factorization problem with a polynomial rate. For the proof, we develop 1) a new symmetrization technique to capture the magnitudes of the symmetry and asymmetry, and 2) a quantitative perturbation analysis to approximate matrix derivatives. We believe both are useful for other related non-convex problems.
Subfields: Aerospace Engineering, Computational Mechanics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Aerospace Engineering
In Computational Mechanics
- René Vidal
- Binghui Peng
- Andrej Risteski
- Paris V. Giampouras
- Liangzu Peng
- Ehsan Elhamifar
- Zhouchen Lin
- Paolo Favaro
Citations in the corpus
- The Ideal Continual Learner: An Agent That Never Forgets (2023, background): “Peng & Risteski (2022) performed one such analysis, based on prior works on orthogonal gradient descent (Farajtabar et al., 2020; Chaudhry et al., 2020) and matrix factorization (Ye & Du, 2021).”
- Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions (2022, methodology): “Our analysis draws inspiration from the recent work of [38], and divides the optimization process into two stages.”