This content will become publicly available on July 22, 2027

Title: Nonconvex matrix factorization is geodesically convex: global landscape analysis for fixed-rank matrix optimization from a Riemannian perspective
Abstract In this paper we study the landscape of a general matrix optimization problem with a fixed-rank positive semidefinite (PSD) constraint. We perform the Burer-Monteiro factorization, i.e., factorize a PSD matrix$${\textbf{X}}$$ X as$${\textbf{Y}}{\textbf{Y}}^\top $$ YY⊤ , and consider a particular Riemannian quotient geometry in a search space that has a total space equipped with the Euclidean metric. When the original objectivefsatisfies standard restricted strong convexity and smoothness properties, we characterize the global landscape of the factorized objective under the Riemannian quotient geometry. In particular, we show that the entire search space can be divided into three regions: ($$\mathcal{R}_1$$ R1 ) the region near the target parameter of interest, where the factorized objective is geodesically strongly convex and smooth; ($$\mathcal{R}_2$$ R2 ) the region containing neighborhoods of all strict saddle points; ($$\mathcal{R}_3$$ R3 ) the remaining regions, where the factorized objective has a large gradient. Our results cover both noisy and noiseless settings in applications of interest. To the best of our 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. Whenfsatisfies 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 main results we provide a comprehensive landscape analysis of a matrix factorization problem with a least squares objective, which serves as a critical bridge in establishing the results in the general setting. Our conclusions are also based on a result of independent interest stating that the geodesic ball centered at$${\textbf{Y}}$$ Y with a radius one-third of the least singular value of$${\textbf{Y}}$$ Y is a geodesically convex set under the Riemannian quotient geometry, a result that, as a corollary, also implies a quantitative bound of the convexity radius in the Bures-Wasserstein space. The convexity radius obtained in this paper is sharp up to constants.  more » « less
Award ID(s):
2236447 2005797
PAR ID:
10702208
Author(s) / Creator(s):
;
Publisher / Repository:
Springer
Date Published:
Journal Name:
Mathematical Programming
ISSN:
0025-5610
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract LetMbe an open (complete and non-compact) manifold with$$\textrm{Ric}\ge 0$$ Ric≥0 and escape rate not 1/2. It is known that under these conditions, the fundamental group$$\pi _1(M)$$ π1(M) has a finitely generated torsion-free nilpotent subgroup$$\mathcal {N}$$ N of finite index, as long as$$\pi _1(M)$$ π1(M) is an infinite group. We show that the nilpotency step of$$\mathcal {N}$$ N must be reflected in the asymptotic geometry of the universal cover$$\widetilde{M}$$ M~ , in terms of the Hausdorff dimension of an isometric$$\mathbb {R}$$ R -orbit: there exist an asymptotic cone (Y, y) of$$\widetilde{M}$$ M~ and a closed$$\mathbb {R}$$ R -subgroupLof the isometry group ofYsuch that its orbitLyhas Hausdorff dimension at least the nilpotency step of$$\mathcal {N}$$ N . This resolves a question raised by Wei and the author (see Pan and Wei in Geom Funct Anal 32:676–685, 2022, Remark 1.7 and Pan in Geom Topol 28:1409–1436, 2024, Conjecture 0.2). 
    more » « less
  2. Abstract Let$$\mathbb {F}_q^d$$ Fqd be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ E⊆Fqd and a fixed nonzero$$t\in \mathbb {F}_q$$ t∈Fq , let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ Ht(E)= {hy:y∈E} , where$$h_y:E\rightarrow \{0,1\}$$ hy:E→{0,1} is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ {x∈E:x·y=t} . Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ d=3 that if$$|E|\ge Cq^{\frac{11}{4}}$$ |E|≥Cq114 andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ Ht(E) is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ Ht(E) isdwhenever$$E\subseteq \mathbb {F}_q^d$$ E⊆Fqd with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ |E|≥Cdq d- 1d-1 . 
    more » « less
  3. Abstract A family ofrdistinct sets$$\{A_1,\ldots , A_r\}$$ {A1,…,Ar} is anr-sunflower if for all$$1 \leqslant i < j\leqslant r$$ 1⩽i<j⩽r and$$1 \leqslant i' < j'\leqslant r$$ 1⩽i′<j′⩽r , we have$$A_i\cap A_j = A_{i'}\cap A_{j'}$$ Ai∩Aj=Ai′∩Aj′ . Erdős and Rado conjectured in 1960 that every family$$\mathcal {H}$$ H of$$\ell $$ ℓ -element sets of size at least$$K(r)^\ell $$ K(r)ℓ contains anr-sunflower, whereK(r) is some function that depends only onr. We prove that if$$\mathcal {H}$$ H is a family of$$\ell $$ ℓ -element sets of VC-dimension at mostdand$$|\mathcal H| > (C r(\log d+\log ^*\ell ))^\ell $$ |H|> (Cr(logd+log∗ℓ)) ℓ for some absolute constant$$C > 0$$ C>0 , then$$\mathcal {H}$$ H contains anr-sunflower. This improves a recent result of Fox, Pach, and Suk. When$$d=1$$ d=1 , we obtain a sharp bound, namely that$$|\mathcal H| > (r-1)^\ell $$ |H|>(r-1) ℓ is sufficient. Along the way, we establish a strengthening of the Kahn–Kalai conjecture for set families of bounded VC-dimension, which is of independent interest. 
    more » « less
  4. Abstract We study the cohomology of a general stable sheaf on an abelian surface. We say that a moduli space satisfies weak Brill–Noether if the general sheaf has at most one non-zero cohomology group. Let (X, H) be a polarized abelian surface and let$${\textbf{v}}=(r, \xi , a)$$ v=(r,ξ,a) be a Mukai vector onXwith$${\textbf{v}}^2 \geqslant 0$$ v2⩾0 ,$$r>0$$ r>0 and$$\xi \cdot H>0$$ ξ·H>0 . We show that if$$\rho (X)=1$$ ρ(X)=1 or$$\rho (X)=2$$ ρ(X)=2 andXcontains an elliptic curve, then all the moduli spaces$$M_{X,H}({\textbf{v}})$$ MX,H (v) satisfy weak Brill–Noether. Conversely, if$$\rho (X)>2$$ ρ(X)>2 or$$\rho (X)=2$$ ρ(X)=2 andXdoes not contain an elliptic curve, we show that there are infinitely many moduli spaces$$M_{X,H}({\textbf{v}})$$ MX,H (v) that fail weak Brill–Noether. As a consequence, we classify Chern classes of Ulrich bundles on abelian surfaces. 
    more » « less
  5. Abstract A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$ (a1,a2,…,an) whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$ b1≤b2≤⋯≤bn satisfies$$b_i \le i$$ bi≤i . The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$ Rn , which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$ x -parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$ x=(a,b,⋯,b) , which we refer to as$${\textbf{x}}$$ x -parking function polytopes. We explore connections between these$${\textbf{x}}$$ x -parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$ x -parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary. 
    more » « less