Smooth globally PLI functions are nonlinear least-squares, and so are their gradient-dominated cousins

Abstract

Boumal, Criscitiello and Rebjock (BCR) proved that if $M$ is a contractible, connected and complete Riemannian manifold, then every smooth function $f\colon M\to R$ satisfying the global Polyak--\L{}ojasiewicz inequality (P\L{}I) is necessarily of the form $f = f^* + \|\phi\|^2$ with $\phi$ a submersion. Informally, minimizing such a function amounts to solving a nonlinear least-squares problem in new coordinates. The global P\L{}I hypothesis fails, however, in many problems of interest, among them continuous-time LQR policy optimization in optimal control and a standard formulation of logistic regression. A hierarchy of weakened P\L{} inequalities has been introduced in order to cover such problems, and more generally to study the effect of noise and adversarial perturbations on gradient flows. This note shows that, with minor modifications, the same reduction to a nonlinear least-squares problem holds under a substantially weaker hypothesis, ``semiglobal'' P\L{}I, which is satisfied in both of the examples just mentioned. That condition asks that $f$ satisfy an estimate $\|\nabla f(x)\| \ge \alpha\bigl(f(x)-f^*\bigr)$ for all $x$, with $\alpha$ merely positive definite and bounded below by a positive multiple of $\sqrt{s}$ for small $s>0$.