If a function $f$ satisfies the Polyak-Lojasiewicz (PL) condition, that is,
$$\Vert \nabla f \Vert^2 \ge 2\mu(f(x)-f^*),$$
is the function strongly convex in a certain neighborhood of the optimal solution $x^*$? Or equivalently, for a stationary point of $f$ (PL condition implies that all stationary points are global optimum), is there a neighborhood such that the function is strongly convex?
Optimization – Can Polyak-Lojasiewicz (PL) Condition Imply Local Strong Convexity?
convex optimizationconvex-analysisoptimization
Related Solutions
This is true. Notice that taking the dual reverses inequalities: $f\ge g$ implies $f^*\le g^*$.
Fix $x_0$ and let $y_0=\nabla f(x_0)$. Define $$g(x) = f(x_0) + y_0^T (x-x_0) + \frac{1}{2}\|x-x_0\|^2 \tag{1}$$ This is a convex quadratic function of $x$. Its dual is $$ g^*(y) = g(y_0)+x_0^T(y-y_0)+ \frac{1}{2}\|y-y_0\|^2 \tag{2} $$ (The derivation of $(2)$ is standard; included below for completeness.)
So, strong convexity of $f$ at $x_0$, expressed as $f\ge g$, implies $f^*\le g^*$, which is the strong smoothness of $f^*$ at $y_0$. Similarly the other way around.
Proof of $(2)$
Since $\nabla g(x) = x-x_0+y_0$, it follows that $\max_x (y^T x - g(x))$ is attained when $x-x_0+y_0=y$, which implies $$\begin{split} g^*(y) &= y^T(y-y_0+x_0) - \left(f(x_0) + y_0^T (y-y_0) + \frac{1}{2}\|y-y_0\|^2 \right) \\ &= (y-y_0)^T(y-y_0) +y^Tx_0 - f(x_0) - \frac{1}{2}\|y-y_0\|^2 \\ &= -f(x_0) + y^Tx_0 + \frac{1}{2}\|y-y_0\|^2 \end{split}$$ Since $g^*(y_0)=-f(x_0)+y_0^Tx_0$, the latter formula can be rewritten as $(2)$.
I was thinking this has a chance in $\mathbb R$ but once you step in $\mathbb R^2$ there should be counterexamples. Let us have a look at the polynomial function: $f\colon (x,y)\in \mathbb R^2 \longmapsto x^4 + 12 x^2 y^2 + y^4 + (x+2y)^2$. You can factor it as $f(x,y) = (x^2+y^2)^2 + 10x^2y^2 + (x+2y)^2$, this establishes that $f(0,0) = 0$ is the unique minimum.
We should note that $f$ is not locally convex around $(0,0)$. For example you can check that, \begin{equation} \begin{bmatrix} 2 \\ -1 \end{bmatrix}^\top \nabla^2 f(t,t) \begin{bmatrix} 2 \\ -1 \end{bmatrix} = -12t^2 < 0, \end{equation} for all $t \neq 0$, no matter how small.
It seemed that there existed a unique minimum for a small enough linear perturbation, however upon closer inspection the gradient map is not injective. I have plotted (rotated and resized) $\nabla f(r\cos \theta, r\sin\theta)$ with $r$ fixed smaller and smaller, and with $\theta$ varying from $0$ to $2 \pi$. It seems to describe a deformed circle around $(0,0)$ (it actually becomes close to a segment) but those circles actually overlap (see the attached plot). In any case the equation is, \begin{equation} \begin{bmatrix} 4 x^3 + 24 x y^2 + 2 (x + 2 y) \\ 24 x^2 y + 4 y^3 + 4 (x + 2 y) \end{bmatrix} = \begin{bmatrix} -u \\ -v \end{bmatrix}. \end{equation}
Arcs of the gradient are drawn, $\nabla f(r \cos t, r \sin t)$, for $r=10^{-7}(1+n/4)$ with $n=1,\dots,10$ and $t = 0 \dots 2\pi$. The picture has been rotated and stretched to show clearly the overlap.
Best Answer
Every constant function satisfies (PL).