Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective

Technical Summary: Nonconvex Matrix Factorization is Geodesically Convex

Problem Formulation
This paper investigates the optimization landscape of a general fixed-rank positive semidefinite (PSD) matrix optimization problem:
$$\min_{0 \preceq X \in \mathbb{S}^p, \text{rank}(X)=r} f(X)$$
where $0 < r \leq p$. To handle the rank constraint, the authors employ the Burer-Monteiro factorization, rewriting the problem in terms of a rectangular matrix $Y \in \mathbb{R}^{p \times r}$ with full column rank, such that $X = YY^\top$. The resulting nonconvex objective is $\bar{h}(Y) = f(YY^\top)$.

The authors address three specific limitations in existing literature regarding the global landscape analysis of this factorization:

1. Geometric Interpretation: Previous Euclidean-based analyses often rely on non-intuitive regularity conditions or restricted directions. The authors seek a more straightforward explanation using classical geometric notions like convexity.
2. Noise Handling: Most existing global landscape results assume a noiseless setting where $\nabla f(X^*) = 0$ at the true parameter $X^*$. The paper aims to analyze the landscape in general noisy settings where this gradient may be non-zero.
3. Assumption Strength: Prior work often requires $f$ to satisfy restricted strong convexity and smoothness (RSC/RSM) globally or near stationary points. The authors aim to relax these assumptions to restricted strict convexity for local results.

Methodology: Riemannian Quotient Geometry
The core methodological innovation is the application of Riemannian optimization on a quotient manifold. The authors recognize that the factorization $X = YY^\top$ introduces an invariance under orthogonal transformations ($Y \to YO$ for any $O \in \mathcal{O}_r$).

• Search Space: They define the search space as the quotient manifold $\mathcal{M}^q_{r+} := \widetilde{\mathcal{M}}^q_{r+} / \mathcal{O}_r$, where $\widetilde{\mathcal{M}}^q_{r+}$ is the set of full-rank $p \times r$ matrices.
• Metric: The total space is equipped with the Euclidean metric $\bar{g}_Y(\eta_Y, \theta_Y) = \text{tr}(\eta_Y^\top \theta_Y)$. This induces a Riemannian metric on the quotient manifold.
• Key Insight: While the Euclidean objective $\bar{h}(Y)$ is inherently nonconvex due to the rotational symmetry (making it impossible to be convex in any neighborhood of a stationary point), the induced objective $h([Y])$ on the quotient manifold can exhibit geodesic convexity.
• Equivalence: Crucially, the Riemannian gradient and Hessian of $h([Y])$ on the quotient manifold correspond exactly to the Euclidean gradient and Hessian of $\bar{h}(Y)$ when restricted to the horizontal space. This implies that standard gradient descent algorithms (which operate on the Euclidean space) are computationally identical to Riemannian gradient descent on this quotient manifold, allowing the authors to transfer geometric guarantees to standard algorithms.

Key Contributions and Results

1. Geometric Properties of the Manifold
The authors establish a fundamental geometric property of the quotient manifold $\mathcal{M}^q_{r+}$:

• Geodesic Convexity Radius: They prove that a geodesic ball centered at $[Y]$ with radius $x \leq \sigma_r(Y)/3$ is geodesically convex. This radius is sharp up to a constant factor.
• Significance: This result provides the first explicit geodesic convexity radius for the Bures-Wasserstein space (the case where $r=p$) under the Bures-Wasserstein geometry.

2. Global Landscape Analysis (Under RSC and RSM)
When $f$ satisfies $(2r, 4r)$-restricted strong convexity and smoothness properties, the authors characterize the global landscape of the factorized objective into three distinct regions (Theorem 1, Corollary 1):

• Region R1 (Near the Target): In a neighborhood of the true parameter $X^*$, the objective $h([Y])$ is geodesically strongly convex and smooth. This region is defined by the distance to the true solution being small relative to the condition number and the smallest singular value.
• Region R2 (Strict Saddles): In neighborhoods of strict saddle points, the Riemannian Hessian possesses at least one negative eigenvalue, and an explicit escaping direction is provided.
• Region R3 (Far from Target): In the remaining regions, the magnitude of the Riemannian gradient is large.

This "benign landscape" structure (strong convexity near the solution, negative curvature at saddles, large gradients elsewhere) guarantees that algorithms satisfying the robust strict saddle property (e.g., perturbed Riemannian gradient descent) will converge globally to the global minimizer.

3. Local Landscape Analysis (Under Restricted Strict Convexity)
Under a weaker assumption where $f$ only satisfies $(r, 2r)$-restricted strict convexity, the authors show that there exists a neighborhood around any local minimizer where the objective is geodesically convex. This extends the applicability of the geometric analysis beyond the strong convexity regime.

4. Noisy Setting Analysis
Unlike previous works that assume $\nabla f(X^*) = 0$, this analysis explicitly handles the noisy case where $\nabla f(X^*) \neq 0$. The bounds on the landscape properties (such as the radius of strong convexity and the magnitude of gradients) depend on the norm of the gradient at the true parameter, $\|\nabla f(X^*)\|$. The results show that as long as the noise level is controlled, the benign landscape structure is preserved.

5. Iteration Complexity
Applying these landscape results to the matrix approximation problem (a specific instance of the general setting), the authors derive iteration complexity bounds for a perturbed Riemannian gradient descent algorithm with local improvement. They show that with random initialization, the algorithm achieves $\epsilon$-accuracy in $O(\log(1/\epsilon) + \log^4(p))$ iterations, provided the initialization satisfies certain spectral conditions (which are shown to hold with high probability).

Significance and Claims
The paper claims to provide the first global landscape analysis of the Burer-Monteiro factorized objective under the Riemannian quotient geometry. Its primary significance lies in:

• Geometric Explanation: It offers a fully geometric explanation for the success of vanilla gradient descent in Burer-Monteiro factorization, attributing it to the geodesic strong convexity of the objective on the quotient manifold, rather than just local regularity conditions.
• Generality: The results cover both noisy and noiseless settings and apply to general objectives satisfying RSC/RSM, not just least squares.
• Sharpness: The derived convexity radius ($\sigma_r(Y)/3$) is shown to be sharp up to constants.
• Algorithmic Implications: The analysis provides a theoretical foundation for the fast global convergence of gradient-based methods, explaining why they avoid spurious local minima and saddle points in practice.

The authors note that while the conditions on the restricted strong convexity parameter $\delta$ may not be as sharp as recent local analyses, the geometric nature of their results (providing convexity rather than just regularity) offers a more intuitive and robust explanation for the algorithm's performance. They also identify future directions, such as exploring the landscape in over-parameterized settings and identifying metrics that maximize the geodesic convexity radius.