Geometric Certificates for Deterministic Global Linear Convergence of Overparameterized Projected Gradient Descent

Abstract

We study projected gradient descent (ProjGD) for the rank-constrained problem $\min \{f(X):\mathrm{rank}(X)\le r\}$ when the unconstrained minimizer $X_{\ast }$ has rank $r_{\ast }\le r$. Our main contribution is a quantitative geometric certificate relating the normal component of $\nabla f(X)$ to the smallest nonzero singular value of $X$. Under a rank-$(r+r_{\ast })$ restricted curvature condition with constants $0<\mu <L$, every nonoptimal rank-$r$ stationary point satisfies $\Vert P_{T(X{)}^{\perp }}\nabla f(X)\Vert /{\sigma }_r(X)\ge [2L\mu /(L-\mu )]\sqrt{r/r_{\ast }}$, where $T(X)$ is the tangent space to the rank-$r$ manifold at $X$. This certificate implies that $X_{\ast }$ is the unique fixed point of ProjGD whenever the step size satisfies $\eta >\sqrt{r_{\ast }/r}(L-\mu )/(2L\mu )$. With an additional rank-$2r$ restricted smoothness assumption, we establish deterministic global linear convergence for $\sqrt{r_{\ast }/r}(L-\mu )/(2L\mu )<\eta <1/L$. The result accommodates arbitrary rank overparameterization $r\ge r_{\ast }$ and is independent of the singular-value condition number of $X_{\ast }$. As a consequence, we obtain an alternative proof of the sharp threshold $\delta <(1+\sqrt{r_{\ast }/r}{)}^{-1}$ for the absence of spurious local minima in the asymmetric setting, where $\delta =(L-\mu )/(L+\mu )$. This threshold and matching asymmetric examples were established in recent work.