Smooth, globally Polyak-Łojasiewicz functions are nonlinear least-squares

Abstract

The Polyak-Łojasiewicz (PŁ) condition is often invoked in nonconvex optimization because it allows fast convergence of algorithms beyond strong convexity. A function $f:\mathcal{M}\to \mathbb{R}$ on a Riemannian manifold $\mathcal{M}$ is globally PŁ if $\Vert \nabla f(x){\Vert }^2\ge 2\hat{I}¼(f(x)-f^{\ast })$ for all $x$, where $f^{\ast }=\inf f$ and $\hat{I}¼>0$. How much does this pointwise, first-order inequality constrain $f$ and its set of minimizers $S$? We show that if $f$ is also smooth ($C^{\infty }$) and $\mathcal{M}$ is contractible (e.g., if $\mathcal{M}={\mathbb{R}}^n$), then the PŁ condition imposes a firm global structure: such a function is necessarily of the form $f(x)=f^{\ast }+\Vert \ddot{I}†(x){\Vert }^2$ (a nonlinear sum of squares) where $\ddot{I}†:\mathcal{M}\to {\mathbb{R}}^k$ is a submersion, and $k$ is the codimension of $S$ in $\mathcal{M}$. The proof hinges on showing that the end-point map of negative gradient flow on $f$ is a trivial smooth fiber bundle over $S$. This rigidity leads to a striking dichotomy. Either $S$ is diffeomorphic to a Euclidean space, in which case $f$ can be transformed into a convex quadratic by a smooth change of coordinates. Or $S$ must display genuinely exotic geometry; for example, it can be diffeomorphic to the Whitehead manifold. As a further consequence, we show that there exists a complete Riemannian metric on $\mathcal{M}$ under which $f$ remains PŁ and becomes geodesically convex.

34 pages + 12 pages of appendices and references