aiqbench analysis
This research provides a rigorous geometric analysis of nonconvex matrix factorization using Riemannian quotient geometry, demonstrating that the search space naturally partitions into regions where gradient descent converges reliably without getting trapped in poor local minima. By establishing geodesic convexity near target parameters and bounding the convexity radius in Bures-Wasserstein space, the study offers a theoretical foundation for why vanilla optimization methods often succeed on fixed-rank problems despite their nonconvex formulation.
Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective
arXiv:2209.15130v3 Announce Type: replace-cross Abstract: We study a general matrix optimization problem with a fixed-rank positive semidefinite (PSD) constraint. We perform the Burer-Monteiro factorization and consider a particular Riemannian quotient geometry in a search space that has a total space equipped with the Euclidean metric. When the original objective f satisfies standard restricted strong convexity and smoothness properties, we characterize the global landscape of the factorized objective under the Riemannian quotient geometry. We show the entire search space can be divided into three regions: (R1) the region near the target parameter of interest, where the factorized objective is geodesically strongly convex and smooth; (R2) the region containing neighborhoods of all strict saddle points; (R3) the remaining regions, where the factorized objective has a large gradient. To our best knowledge, this is the first global landscape analysis of the Burer-Monteiro factorized objective under the Riemannian quotient geometry. Our results provide a fully geometric explanation for the superior performance of vanilla gradient descent under the Burer-Monteiro factorization. When f satisfies a weaker restricted strict convexity property, we show there exists a neighborhood near local minimizers such that the factorized objective is geodesically convex. To prove our results, we provide a comprehensive landscape analysis of a matrix factorization problem with a least squares objective, which serves as a critical bridge. Our conclusions are also based on a result of independent interest stating that the geodesic ball centered at Y with a radius 1/3 of the least singular value of Y is a geodesically convex set under the Riemannian quotient geometry, which as a corollary, also implies a quantitative bound of the convexity radius in the Bures-Wasserstein space. The convexity radius obtained is sharp up to constants.
Abstract:We study a general matrix optimization problem with a fixed-rank positive semidefinite (PSD) constraint. We perform the Burer-Monteiro factorization and consider a particular Riemannian quotient geometry in a search space that has a total space equipped with the Euclidean metric. When the original objective f satisfies standard restricted strong convexity and smoothness properties, we characterize the global landscape of the factorized objective under the Riemannian quotient geometry. We show the entire search space can be divided into three regions: (R1) the region near the target parameter of interest, where the factorized objective is geodesically strongly convex and smooth; (R2) the region containing neighborhoods of all strict saddle points; (R3) the remaining regions, where the factorized objective has a large gradient. To our best knowledge, this is the first global landscape analysis of the Burer-Monteiro factorized objective under the Riemannian quotient geometry. Our results provide a fully geometric explanation for the superior performance of vanilla gradient descent under the Burer-Monteiro factorization. When f satisfies a weaker restricted strict convexity property, we show there exists a neighborhood near local minimizers such that the factorized objective is geodesically convex. To prove our results, we provide a comprehensive landscape analysis of a matrix factorization problem with a least squares objective, which serves as a critical bridge. Our conclusions are also based on a result of independent interest stating that the geodesic ball centered at Y with a radius 1/3 of the least singular value of Y is a geodesically convex set under the Riemannian quotient geometry, which as a corollary, also implies a quantitative bound of the convexity radius in the Bures-Wasserstein space. The convexity radius obtained is sharp up to constants.
Accepted to Mathematical Programming, Series A. The abstract is shortened to meet the arXiv submission requirement
Optimization and Control (math.OC); Information Theory (cs.IT); Machine Learning (cs.LG); Signal Processing (eess.SP); Numerical Analysis (math.NA)
arXiv:2209.15130 [math.OC]
(or arXiv:2209.15130v3 [math.OC] for this version)
https://doi.org/10.1007/s10107-026-02400-x DOI(s) linking to related resources
Full text under the publisher's open licence · 324 words
Related coverage
Nonsmooth Optimization via Orthogonalized Momentum
arXiv · Sep 16, 2026
Near-Optimal Nonconvex Matrix Completion
arXiv · Sep 16, 2026
Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting
arXiv · Aug 20, 2026
Convergence of Practical Muon with Finite Newton-Schulz Iterations and Nesterov Momentum
arXiv · Oct 1, 2026