4
$\begingroup$

I'm have been looking for a while now for a proof to "Polyak-Lojasiewicz (PL) inequality", which states that:

if: $\forall x\in Dom(f):mI\succcurlyeq\nabla^{2}f(x)$ then:

$f(x)-f(x^{*})\geq\frac{1}{2m}\left|\left|\nabla f(x)\right|\right|_{2}^{2}$

where $ \succcurlyeq\ $is the positive semi-definite notation.

this is the only article that I have encountered who uses this inequality: http://liberzon.csl.illinois.edu/teaching/Polyak-Lojasiewicz.pdf

I have tried to prove it for my own in the following link, but lately I found a mistake and therefore I'm trying to prove it in other way:

proving:$f(x)-f(x^{*})\geq\frac{1}{2m}\left|\left|\nabla f(x)\right|\right|_{2}^{2}$

$\endgroup$
1
  • 3
    $\begingroup$ The inequality you mention is not the PL inequality. It's the reverse direction. $\endgroup$
    – xel
    Commented Aug 5, 2020 at 15:07

1 Answer 1

5
$\begingroup$

Proving your Polyak-Lojasiewicz (PL) inequality is not an easy task, one of the easiest ways comes from assuming that the function is a Morse-Bott function of order 2, a proof can be found in this beautiful article. Proving the converse, i.e., every function that satisfies your Polyak-Lojasiewicz (PL) inequality is in fact a Morse-Bott function of order 2 it's even harder. It requires Resolution of singularities, a powerful tool in Algebraic Geometry.

The Polyak-Lojasiewicz (PL) inequality is not wrong, since it is assumed as a hypothesis. On the other hand, in general, the inequality is not true. For example, the functions $f(x)=x^{k}$ for $k$ even is convex, and it only satisfies $$\dfrac{1}{k}|f'(x)|\geq |f(x)|^{\dfrac{k-1}{k}}.$$ Observe that the exponents can be taken arbitrarily close to $1$, which means that the result starts getting worse and worse as it happens.

Generally, only the Lojasiewicz gradient inequality holds around a point, which is a weaker result, but yet strong. And proving it requires Algebraic Geometry as well. Again, the ideas of the proof can be found here.

I will prove Polyak-Lojasiewicz (PL) inequality for strongly convex functions $f:\mathbb{R}^{n} \rightarrow \mathbb{R}$ for completeness and my own future reference. Looking to the equivalent definitions of strongly convex functions, they say that a function is strongly convex whenever $$ \begin{align} \left( \nabla f(\boldsymbol x) - \nabla f(\boldsymbol y) \right)^{T}(\boldsymbol x - \boldsymbol y ) \geq & m \|\boldsymbol x- \boldsymbol y\|^{2},\\ \end{align} $$ for all $\boldsymbol x, \boldsymbol y \in \mathbb{R}^n.$ From what follows we need to assume the Lipschitz continuity of the gradient, this means that there exist an $L>0$ such that $$ f(\boldsymbol x)\leq f(\boldsymbol y) + \nabla f (\boldsymbol y)^{T} (\boldsymbol x - \boldsymbol y)+ \dfrac{L}{2} \|\boldsymbol x - \boldsymbol y\|^2,$$ for all $\boldsymbol x, \boldsymbol y \in \mathbb{R}^n.$

Finally, for the only minimizer $\boldsymbol y \in \mathbb{R}^{n}$, we have that $\nabla f (\boldsymbol y) =\boldsymbol 0$ and for all $\boldsymbol x \in \mathbb{R}^n$ $$ \begin{align} \left\| \nabla f(\boldsymbol x) \right\| = & \left\| \nabla f(\boldsymbol x) - \nabla f(\boldsymbol y) \right\|\\ \geq & m \|\boldsymbol x- \boldsymbol y\| \\ = & \dfrac{\sqrt{2} m}{\sqrt{L}} \sqrt{ \dfrac{L}{2} \|\boldsymbol x- \boldsymbol y\|^{2}} \\ = & \dfrac{\sqrt{2} m}{\sqrt{L}} \sqrt{ \dfrac{L}{2} \|\boldsymbol x- \boldsymbol y\|^{2} + \nabla f (\boldsymbol y)^{T} (\boldsymbol x- \boldsymbol y) + f(\boldsymbol y) - f(\boldsymbol y) } \\ \geq & \dfrac{\sqrt{2} m}{\sqrt{L}} \sqrt{ f(\boldsymbol x) - f(\boldsymbol y)}, \\ \end{align} $$ which is your desired result for the article.

As can be noticed, the Polyak-Lojasiewicz (PL) inequality is weaker than asking strong convexity of the function, and, by the Corollary 2, is equivalent to asking for the function being a Morse-Bott of order 2. That's why your article directly ask it instead of asking the strong convexity of the function.

In general, observe that all the arguments here could be seamlessly generalized considering that we are working functions that are locally strongly convex, which gives the intuition why asking for the inequality for convex functions it not much.

$\endgroup$
5
  • $\begingroup$ I am a bit lost. Is this PL inequality a theorem or an hypothesis? Under what conditions should be true? What is provable using algebraic geometry and what is not? What shows the article you link? $\endgroup$
    – Thomas
    Commented Nov 19, 2021 at 23:37
  • $\begingroup$ Would it be possible to clarify better the logics? $\endgroup$
    – Thomas
    Commented Nov 19, 2021 at 23:38
  • $\begingroup$ There are theorems of the form "If the PL inequality holds for a particular function f, then ..." In that sense, it's a hypothesis. @R. W. Prado has shown that if $f$ is strongly convex, the PL inequality holds.. $\endgroup$ Commented Nov 20, 2021 at 0:18
  • $\begingroup$ An edit was made to clarify the differences between Lojasiewicz gradient inequality and Polyak-Lojasiewicz (PL) inequality. It was not clear in the first time I answered. $\endgroup$ Commented Nov 22, 2021 at 11:00
  • $\begingroup$ The link math.stackexchange.com/questions/3804327/… shows that it's not needed to assume the Lipschitz continuity of the gradient to the result to hold. $\endgroup$ Commented Nov 23, 2021 at 18:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .