View source for Łojasiewicz inequality

In [[real algebraic geometry]], the ''' Łojasiewicz inequality''', named after [[Stanisław Łojasiewicz]], gives an upper bound for the distance of a point to the nearest zero of a given [[real analytic function]].  Specifically, let ƒ&nbsp;:&nbsp;''U''&nbsp;→&nbsp;'''R''' be a real analytic function on an [[open set]] ''U'' in '''R'''<sup>''n''</sup>, and let ''Z'' be the [[zero locus]] of ƒ. Assume that ''Z'' is not empty.  Then for any [[compact set]] ''K'' in ''U'', there exist positive constants α and ''C'' such that, for all  ''x'' in ''K'' 

:<math>\operatorname{dist}(x,Z)^\alpha \le C|f(x)|. </math>

Here α can be large.

The following form of this inequality is often seen in more analytic contexts:  with the same assumptions on ''f'', for every ''p''&nbsp;∈&nbsp;''U'' there is a possibly smaller open neighborhood ''W'' of ''p'' and constants θ&nbsp;∈&nbsp;(0,1) and ''c''&nbsp;>&nbsp;0 such that

:<math>|f(x)-f(p)|^\theta\le c|\nabla f(x)|. </math>

== Polyak inequality ==
A special case of the Łojasiewicz inequality, due to {{ill|Boris Polyak|ru|Поляк, Борис Теодорович|lt=Polyak}}, is commonly used to prove linear [[Convergent series|convergence]] of [[gradient descent]] algorithms. This section is based on {{Harvtxt|Karimi|Nutini|Schmidt|2016}} and {{Harvtxt|Liu|Zhu|Belkin|2022}}.

=== Definitions ===
<math display="inline">f</math> is a function of type <math display="inline">\R^d \to \R</math>, and has a continuous derivative <math>\nabla f</math>.

<math>X^*</math> is the subset of <math>\R^d</math> on which <math>f</math> achieves its global minimum (if one exists). Throughout this section we assume such a global minimum value <math>f^*</math> exists, unless otherwise stated. The optimization objective is to find some point <math>x</math> in <math>X^*</math>.

<math display="inline">\mu, L > 0</math> are constants. 

<math display="inline">\nabla f</math> is <math>L</math>-[[Lipschitz continuity|Lipschitz continuous]] iff 

<math display="block">\|\nabla f(x) - \nabla f(y)\| \leq L \|x - y\|, \quad \forall x, y</math>

<math display="inline">f</math> is <math display="inline">\mu</math>-[[Strong convexity|strongly convex]] iff<math display="block">f(y)\ge f(x)+\nabla f(x)^T(y-x)+\frac{\mu}{2}\lVert y-x \rVert^2  \quad \forall x, y</math>

<math display="inline">f</math> is <math display="inline">\mu</math>-PL (where "PL" means "Polyak-Łojasiewicz") iff<math display="block">
          \frac{1}{2}\|\nabla f(x)\|^2 \geq \mu\left(f(x)-f(x^*)\right), \quad \forall x
          </math>

=== Basic properties ===

{{Math theorem|math_statement= 

1. If <math display="inline">f</math> is <math display="inline">\mu</math>-PL, then it is [[Invex function|invex]].

2. If <math display="inline">\nabla f</math> is L-Lipschitz continuous, then <math display="block">
          f(y) \leq f(x)+\langle\nabla f(x), y-x\rangle+\frac{L}{2}\|y-x\|^2
          </math>

3. If <math display="inline">f</math> is <math display="inline">\mu</math>-strongly convex then it is <math display="inline">\mu</math>-PL.

4. If <math display="inline">g</math> is <math display="inline">\mu</math>-strongly convex, and <math display="inline">A</math> is linear, then <math display="inline">f := g \circ A</math> is <math display="inline">(\mu \sigma^2)</math>-PL, where <math display="inline">\sigma</math> is the smallest nonzero [[singular value]] of <math display="inline">A</math>.

5. (quadratic growth) If <math display="inline">f</math> is <math display="inline">\mu</math> -PL, <math display="inline">x</math> is a point, and <math display="inline">x^*</math> is the point on the optimum set that is closest to <math display="inline">x</math> in L2-norm, then <math display="block">
          f(x) \geq f\left(x^*\right) + \frac{\mu}{2}\left\|x-x^*\right\|_2^2 
          </math>
}}

{{hidden begin|style=width:100%|ta1=center|border=1px #aaa solid|title=Proof}}

{{Math proof|title=Proof|proof= 

1. By definition, every stationary point is a global minimum. 

2. Integrate <math display="inline">f(x + t(y-x))</math> for <math display="inline">t \in [0, 1]</math> and use the <math display="inline">L</math> -Lipschitz continuity.

3. By definition, <math display="inline">f(y)\ge f(x)+\nabla f(x)^T(y-x)+\frac{\mu}{2}\lVert y-x \rVert^2</math>. Now, minimize the left side, we have <math display="block">
                  f(x^*)\ge f(x)+\nabla f(x)^T(x^*-x)+\frac{\mu}{2}\lVert x^*-x \rVert^2
                  </math> then minimize the right side, we have<math display="block">
                  f(x)+\nabla f(x)^T(x^*-x)+\frac{\mu}{2}\lVert x^*-x \rVert^2 \geq f(x) - \frac{1}{2\mu} \|\nabla f(x)\|^2
                  </math> Combining the two, we have the <math display="inline">\mu</math>-PL inequality.

<math display="block">
          f\left(x_k\right)-f\left(x^*\right) \leq\left(1- \mu/ L \right)^k\left(f\left(x_0\right)-f\left(x^*\right)\right)
          </math>

4. 
<math display="block">
              g(Ay) \geq g(Ax) + \langle \nabla g(Ax) , Ay - Ax\rangle + \frac \mu 2 \|Ay - Ax\|^2
              </math>

Now, since <math display="inline">\nabla f(x) = A^T \nabla g (Ax)</math>, we have <math display="block">
              f(y) \geq f(x) + \langle \nabla f (x), y-x\rangle + \frac \mu 2 \|A(y - x)\|^2
              </math>

Set <math display="inline">y</math> to be the projection of <math display="inline">x</math> to the optimum subspace, then we have <math display="inline">\|A(y - x)\| \geq \sigma \|y - x\|</math>. Thus, we have <math display="block">
              f(y) - f(x) \geq \langle \nabla f (x), y-x\rangle + \frac{\mu \sigma^2}{2} \|y - x\|^2
              </math> Vary the <math display="inline">y</math> on the right side to minimize the right side, we have the desired result.

5. Let <math display="inline">g(x) := \sqrt{f(x) - f^*}</math>. For any <math display="inline">x \not\in X^*</math>, we have <math display="block">
              \nabla g(x) = \frac{\nabla f(x)}{2\sqrt{f(x) - f^*}}
              </math> so by <math display="inline">\mu</math> -PL,<br />
<math display="block">
              \|\nabla g(x)\|^2 \geq \mu/2
              </math>

In particular, we see that <math display="inline">\nabla g</math> is a vector field on <math display="inline">\R^d \setminus X^*</math> with size at least <math display="inline">\sqrt{\mu / 2}</math>. Define a gradient flow along <math display="inline">\nabla g</math> with constant unit velocity, starting at <math display="inline">x(0) = x</math>: <math display="block">
              x(0) = x, \quad \dot x(t) = \frac{\nabla g}{\|\nabla g\|}
              </math>

Because <math display="inline">g</math> is bounded below by <math display="inline">0</math>, and <math display="inline">\|\nabla g\| \geq \sqrt{\mu/ 2}</math>, the gradient flow terminates on the zero set <math display="inline">X^*</math> at a finite time <math display="block">T \leq g(x) / \sqrt{\mu / 2}</math> The path length is <math display="inline">T</math>, since the velocity is constantly 1.

Since <math display="inline">x(T)</math> is on the zero set, and <math display="inline">x^*</math> is the point closest to <math display="inline">x</math>, we have <math display="block">
              \|x^* - x\| \leq T \leq  g(x) / \sqrt{\mu / 2}
              </math> which is the desired result.

}}{{hidden end}}

=== Gradient descent ===

{{Math theorem|note=linear convergence of gradient descent
|math_statement= 

If <math display="inline">f</math> is <math display="inline">\mu</math>-PL and <math display="inline">\nabla f</math> is <math display="inline">L</math>-Lipschitz, then gradient descent with constant step size <math display="inline">\eta</math><math display="block">
          x_{k+1} = x_k - \eta \nabla f(x_k)
          </math>converges linearly as<math display="block">
          f\left(x_k\right)-f\left(x^*\right) \leq \left(1- 2\mu \eta (1 - L\eta/2)\right)^k\left(f\left(x_0\right)-f\left(x^*\right)\right),
\quad \eta \in (0, 2/L)
          </math>

The convergence is the fastest when <math display="inline">\eta = 1/L</math>, at which point<math display="block">
          f\left(x_k\right)-f\left(x^*\right) \leq\left(1- \mu/ L \right)^k\left(f\left(x_0\right)-f\left(x^*\right)\right)
          </math>
}}

{{hidden begin|style=width:100%|ta1=center|border=1px #aaa solid|title=Proof}}

{{Math proof|title=Proof|proof=

Since <math display="inline">\nabla f</math> is <math display="inline">L</math> -Lipschitz, we have the parabolic upper bound <math display="block">
                  f(x_{k+1}) \leq f(x_k) + \langle \nabla f(x_k) , x_{k+1} - x_k\rangle + \frac{L}{2}\|x_{k+1} - x_k\|^2
                  </math>

Plugging in the gradient descent step, <math display="block">
                  \begin{aligned}
                  f(x_{k+1}) - f(x_k) &\leq \langle \nabla f(x_k) , -\eta \nabla f(x_k)\rangle + \frac{L}{2}\|- \eta \nabla f(x_k)\|^2 \\
                  &= (L\eta^2/2-\eta) \|\nabla f(x_k)\|^2\\
                  &\leq 2\mu (L\eta^2/2-\eta)\left(f(x_k)-f(x^*)\right)
                  \end{aligned}
                  </math>

Thus, <math display="block">
                  f\left(x_k\right)-f\left(x^*\right) \leq\left(1- 2\mu \eta (1 - L\eta/2)\right)^k\left(f\left(x_0\right)-f\left(x^*\right)\right)
                  </math>
}}{{hidden end}}

{{Math theorem
| name = Corollary
| note = 
| math_statement = 1. <math display="inline">x_k</math> converges to the optimum set <math display="inline">X^*</math> at a rate of <math display="inline">\left(1- \mu \eta (2 - L\eta)\right)</math>.

2. If <math display="inline">f</math> is <math display="inline">\mu</math> -PL, not constant, and <math display="inline">\nabla f</math> is <math display="inline">L</math> -Lipschitz, then <math display="inline">L \geq \mu</math>.

3. Under the same conditions, gradient descent with optimal step size (which might be found by [[line search|line-searching]]) satisfies

<math display="block">f\left(x_k\right)-f\left(x^*\right) \leq\left(1- \mu/ L \right)^k\left(f\left(x_0\right)-f\left(x^*\right)\right)</math>
}}

=== Coordinate descent ===
The [[Coordinate descent|coordinate descent algorithm]] first samples a random coordinate <math display="inline">i_k</math> uniformly, then perform gradient descent by <math display="block">
      x_{k+1} = x_k - \eta \partial_{i_k} f(x_k) e_{i_k}
      </math>

{{Math theorem|name=Theorem|note=|math_statement= 

Assume that <math display="inline">f</math> is <math display="inline">\mu</math> -PL, and that <math display="inline">\nabla f</math> is <math display="inline">L</math> -Lipschitz at each coordinate, meaning that <math display="block">|\partial_{i}f(x + te_i) - \partial_i f(x)| \leq L|t|</math>Then, <math display="inline">\mathbb E[f(x_k) - f(x^*)]</math> converges linearly for all <math display="inline">\eta \in (0, 2/L)</math> by <math display="block">
          \mathbb E[f(x_k) - f(x^*)] \leq \left(1 - \frac{\mu\eta(2 - L\eta)}{d}\right)^k (f(x_0) - f(x^*))
          </math>
}}

{{hidden begin|style=width:100%|ta1=center|border=1px #aaa solid|title=Proof}}
{{Math proof|title=Proof|proof= 

By the same argument, <math display="block">
              f(x_{k+1}) \leq f(x_k) + (L\eta^2/2 - \eta) (\partial_{i_k}f(x_k))^2
              </math>

Take expectation with respect to <math display="inline">i_k</math>, we have <math display="block">
              \mathbb E[f(x_{k+1})] \leq f(x_k) + \frac{L\eta^2/2 - \eta}{d} \|\nabla f(x_k)\|^2
              </math>

Plug in the <math display="inline">\mu</math> -PL inequality, we have <math display="block">
              \mathbb E[f(x_k) - f(x^*)] \leq \left(1 - \frac{\mu\eta(2 - L\eta)}{d}\right) (f(x_k) - f(x^*))
              </math>Iterating the process, we have the desired result.
}}{{hidden end}}

=== Stochastic gradient descent ===

In [[stochastic gradient descent]], we have a function to minimize <math display="inline">f(x)</math>, but we cannot sample its gradient directly. Instead, we sample a random gradient <math display="inline">\nabla f_i(x)</math>, where <math display="inline">f_i</math> are such that <math display="block">
          f(x) = \mathbb E_i[f_i(x)]
          </math> For example, in typical machine learning, <math display="inline">x</math> are the parameters of the neural network, and <math display="inline">f_i(x)</math> is the loss incurred on the <math display="inline">i</math> -th training data point, while <math display="inline">f(x)</math> is the average loss over all training data points.

The gradient update step is <math display="block">
          x_{k+1} = x_k - \eta_k \nabla f_{i_k}(x_k)
          </math> where <math display="inline">\eta_k > 0</math> are a sequence of learning rates (the learning rate schedule).

{{Math theorem|math_statement= 

If each <math display="inline">\nabla f_i</math> is <math display="inline">L</math> -Lipschitz, <math display="inline">f</math> is <math display="inline">\mu</math> -PL, and <math display="inline">f</math> has global mimimum <math display="inline">f^*</math>, then <math display="block">
              \mathbb{E}\left[f\left(x_{k+1}\right)-f^*\right] \leq\left(1-2 \eta_k \mu\right)\left[f\left(x_k\right)-f^*\right]+\frac{L \eta_k^2}{2} \mathbb E_i[\|\nabla f_i(x_k) \|^2]
              </math>We can also write it using the variance of gradient L2 norm: <math display="block">
              \mathbb{E}\left[f\left(x_{k+1}\right)-f^*\right] \leq\left(1-\mu (2\eta_k - L\eta_k^2 )\right)\left[f\left(x_k\right)-f^*\right]+\frac{L \eta_k^2}{2} \mathbb E_i[\|\nabla f_i(x_k) - \nabla f(x_k)\|^2]
              </math>
}}

{{hidden begin|style=width:100%|ta1=center|border=1px #aaa solid|title=Proof}}

{{Math proof|title=Proof|proof= 

Because all <math display="inline">\nabla f_i</math> are <math display="inline">L</math> -Lipschitz, so is <math display="inline">\nabla f</math>. We thus have <math display="block">
              f(x_{k+1}) \leq f(x_k) - \eta_k \langle \nabla f(x_k) , \nabla f_{i_k}(x_k)\rangle + \frac{L\eta_k^2}{2} \| \nabla f_{i_k}(x_k)\|^2
              </math>

Now, take the expectation over <math display="inline">i_k</math>, and use the fact that <math display="inline">f</math> is <math display="inline">\mu</math> -PL. This gives the first equation.

The second equation is shown similarly by noting that <math display="block">
              \mathbb E_i[\|\nabla f_i(x_k) \|^2] = \mathbb E_i[\|\nabla f_i(x_k) - \nabla f(x_k) \|^2] + \|\nabla f(x_k) \|^2
              </math>

}}{{hidden end}}

As it is, the proposition is difficult to use. We can make it easier to use by some further assumptions.

The second-moment on the right can be removed by assuming a uniform upper bound. That is, if there exists some <math display="inline">C> 0</math> such that during the SG process, we have<math display="block">\mathbb E_i[\|\nabla f_i(x_k)\|^2] \leq C</math> for all <math display="inline">k = 0, 1, \dots</math>, then<math display="block">
              \mathbb{E}\left[f\left(x_{k+1}\right)-f^*\right] \leq\left(1-2 \eta_k \mu\right)\left[f\left(x_k\right)-f^*\right]+\frac{LC \eta_k^2}{2}
              </math>Similarly, if <math display="block">\forall k, \quad \mathbb E_i[\|\nabla f_i(x_k) - \nabla f(x_k)\|^2]\leq C</math> then<math display="block">
              \mathbb{E}\left[f\left(x_{k+1}\right)-f^*\right] \leq\left(1-\mu (2\eta_k - L\eta_k^2 )\right)\left[f\left(x_k\right)-f^*\right]+\frac{L C\eta_k^2}{2}
              </math>

==== Learning rate schedules ====
For '''constant learning rate schedule''', with <math display="inline">\eta_k = \eta = 1/L</math>, we have<math display="block">
                  \mathbb{E}\left[f\left(x_{k+1}\right)-f^*\right] \leq\left(1-\mu/L\right)\left[f\left(x_k\right)-f^*\right]+\frac{C}{2L}
                  </math>By induction, we have <math display="block">\mathbb{E}\left[f\left(x_{k}\right)-f^*\right] \leq\left(1-\mu/L\right)^k \left[f\left(x_0\right)-f^*\right]+\frac{C}{2\mu}
                  </math>We see that the loss decreases in expectation first exponentially, but then stops decreasing, which is caused by the <math display="inline">C/(2L)</math> term. In short, because the gradient descent steps are too large, the variance in the stochastic gradient starts to dominate, and <math display="inline">x_k</math> starts doing a random walk in the vicinity of <math display="inline">X^*</math>.

For '''decreasing learning rate schedule''' with <math display="inline">\eta_k = O(1/k)</math>, we have <math>\mathbb{E}\left[f\left(x_{k}\right)-f^*\right] = O(1/k)</math>.

==References==
{{Reflist}}
*{{Citation | last1=Bierstone | first1=Edward | last2=Milman | first2=Pierre D. | title=Semianalytic and subanalytic sets |mr=972342 | year=1988 | journal=[[Publications Mathématiques de l'IHÉS]] | volume=67 | issn=1618-1913 | issue=67 | pages=5–42| doi=10.1007/BF02699126 | s2cid=56006439 |url=http://www.numdam.org/item?id=PMIHES_1988__67__5_0}}
*{{Citation | doi=10.2307/2153965 | last1=Ji | first1=Shanyu | last2=Kollár | first2=János | last3=Shiffman | first3=Bernard | title=A global Łojasiewicz inequality for algebraic varieties |mr=1046016 | url=http://www.ams.org/journals/tran/1992-329-02/S0002-9947-1992-1046016-6/ | year=1992 | journal=[[Transactions of the American Mathematical Society]] | issn=0002-9947 | volume=329 | issue=2 | pages=813–818 | jstor=2153965}}
*{{cite arXiv |eprint=1608.04636 |class=cs.LG |first1=Hamed |last1=Karimi |first2=Julie |last2=Nutini |title=Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak–Łojasiewicz Condition |first3=Mark |last3=Schmidt |year=2016}}
*{{Cite journal |last=Liu |first=Chaoyue |last2=Zhu |first2=Libin |last3=Belkin |first3=Mikhail |date=2022-07-01 |title=Loss landscapes and optimization in over-parameterized non-linear systems and neural networks |url=https://www.sciencedirect.com/science/article/abs/pii/S106352032100110X |journal=Applied and Computational Harmonic Analysis |series=Special Issue on Harmonic Analysis and Machine Learning |volume=59 |pages=85–116 |doi=10.1016/j.acha.2021.12.009 |issn=1063-5203|arxiv=2003.00307 }}

== External links ==

* {{SpringerEOM|title=Lojasiewicz inequality|oldid=Lojasiewicz_inequality}}
{{DEFAULTSORT:Lojasiewicz inequality}}
[[Category:Inequalities]]
[[Category:Mathematical analysis]]
[[Category:Real algebraic geometry]]