Abstract
Prior work has shown that low-rank matrix factorization has infinitely many critical points, each of which is either a global minimum or a (strict) saddle point. We revisit this problem and provide a rigorous geometric analysis of the matrix factorization (MF) optimization landscape. By focusing on a specific "balanced" manifold that gradient flow naturally follows, we demonstrate that saddle points have a guaranteed, non-vanishing downward curvature, ensuring that gradient-based methods can reliably escape them.
Introduction
Matrix Factorization (MF)—the decomposition of a target matrix $X$ into factors $W$ and $S$ such that $X \approx WS$—is a fundamental operation in machine learning, underpinning techniques from Principal Component Analysis (PCA) to recommendation systems. Despite its non-convex nature, MF is often solved efficiently using gradient-based methods. While it is well-established that the MF objective contains no "bad" local minima, the behavior of optimization near saddle points remains a critical area of study. Specifically, if saddle points are "flat" (possessing near-zero curvature), gradient descent may stall. This work quantifies the curvature at these points, proving that they are "strict" saddles with a clear path for escape.
Geometric Framework: Orbits and Invariance
The core of the analysis lies in the geometric structure of the factorization space. Because $WS = (WA)(A^{-1}S)$ for any invertible matrix $A$, the objective function is invariant under certain transformations. This leads to the concept of orbits: sets of equivalent factorizations that represent the same product matrix.
To simplify the analysis, the authors identify "canonical points" on these orbits. Theorem 3.2 establishes that every critical point with positive rank lies on the orbit of a specific, mathematically tractable canonical point. By analyzing these representatives, the complex global landscape is reduced to a set of manageable cases.
The Balanced Manifold
A key insight is the role of the balanced manifold $\mathcal{M}_0$, defined by the condition $W^T W = SS^T$. This manifold is not merely a theoretical construct; it is an invariant of the gradient flow. If an optimization process is initialized near the origin (a common practice), the trajectory is mathematically confined to $\mathcal{M}_0$. This "balance" ensures that the factors $W$ and $S$ evolve at comparable scales, which is crucial for stable and efficient convergence.
Main Results: Quantifying the Escape Route
The paper's primary contribution is a uniform bound on the "steepness" of saddle points. By performing a detailed Hessian eigenvalue analysis, the authors prove:
- Uniform Negative Curvature: On the balanced manifold, every strict saddle point has a minimum Hessian eigenvalue ($\lambda_{min}$) that is bounded away from zero. Specifically, there exists a constant $\gamma > 0$ such that $\lambda_{min}(\nabla^2 J) \le -\gamma$.
- Dependence on Singular Values: The magnitude of this downward curvature is directly related to the singular values of the target matrix $X$. For a saddle point that is not maximal at index $p$, the curvature is bounded by $-\sigma_p$, where $\sigma_p$ is the $p$-th singular value of $X$.
These results provide a geometric guarantee that gradient-based methods will not linger indefinitely at saddle points, as there is always a "minimum amount of steepness" helping the optimizer escape toward a global minimum.
Conclusion
This research provides a unified framework for understanding the optimization landscape of matrix factorization in both low-rank and over-parameterized regimes. By leveraging the geometric properties of orbits and the balanced manifold, the authors offer a rigorous explanation for the empirical success of gradient descent in MF. Future work may extend these orbit-based proofs to deeper linear networks and explore the impact of alternative loss functions beyond the squared Frobenius norm.
Summary updated