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.
翻译:我们用固定的正正半断面度( PSD) 限制来研究总体矩阵优化问题。 我们使用布勒- 蒙泰罗( Burer- Monteiro) 参数化, 并考虑在拥有全空间的Euclidean 度量的搜索空间中进行特定的 Riemannian 位数数几何。 当原始目标达到标准限制强的精度和平滑性时, 我们根据Riemannian 商数的几何度来描述因素化目标的全球景观。 我们显示整个搜索空间可以分为三个区域:( R1) 接近目标参数参数参数化的区域, 其参数化目标性能是地平面和光滑;( R2) 包含所有严格马鞍点的周边区域;( R3) 剩余区域, 其参数化目标性能具有很大的梯度值。 这是在Riemannian 位数数测算下第一次全球地形分析。 我们的精确度值值性直径直径直径直系直径值, 其直径直径直径直径直径直径直方值显示我们平方点的地平方值分析结果。