Łojasiewicz inequality

Short description: Inequality from distance to a zero of a real analytic function

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 ƒ : U → R be a real analytic function on an open set U in Rⁿ, 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

$\mathrm{dist}(x,Z{)}^{\alpha }\le C|f(x)|.$

Here, $\alpha$ can be small.

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

$|f(x)-f(p){|}^{\theta }\le c|\mathrm{\nabla }f(x)|.$

Polyak inequality

A special case of the Łojasiewicz inequality, due to Boris Polyak (ru) (see condition C in ), is commonly used to prove linear convergence of gradient descent algorithms. This section is based on (Karimi Nutini) and (Liu Zhu).

Definitions

$f$ is a function of type ${\mathbb{ℝ}}^d\to \mathbb{ℝ}$, and has a continuous derivative $\mathrm{\nabla }f$.

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

$\mu ,L>0$ are constants.

$\mathrm{\nabla }f$ is $L$-Lipschitz continuous iff

$$\Vert \mathrm{\nabla }f(x)-\mathrm{\nabla }f(y)\Vert \le L\Vert x-y\Vert ,\mathrm{\forall }x,y$$

$f$ is $\mu$-strongly convex iff$$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)+\frac{\mu }{2}\Vert y-x{\Vert }^2\mathrm{\forall }x,y$$

$f$ is $\mu$-PL (where "PL" means "Polyak-Łojasiewicz") iff$$\frac{1}{2}\Vert \mathrm{\nabla }f(x){\Vert }^2\ge \mu (f(x)-f(x^{*})),\mathrm{\forall }x$$

Basic properties

Theorem — 1. If $f$ is $\mu$-PL, then it is invex.

2. If $\mathrm{\nabla }f$ is L-Lipschitz continuous, then $$f(y)\le f(x)+⟨\mathrm{\nabla }f(x),y-x⟩+\frac{L}{2}\Vert y-x{\Vert }^2$$

3. If $f$ is $\mu$-strongly convex then it is $\mu$-PL.

4. If $g$ is $\mu$-strongly convex, and $A$ is linear, then $f:=g\circ A$ is $(\mu {\sigma }^2)$-PL, where $\sigma$ is the smallest nonzero singular value of $A$.

5. (quadratic growth) If $f$ is $\mu$ -PL, $x$ is a point, and $x^{*}$ is the point on the optimum set that is closest to $x$ in L2-norm, then $$f(x)\ge f\left(x^{*}\right)+\frac{\mu }{2}{\Vert x-x^{*}\Vert }_2^2$$

Proof

Proof

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

2. Set $g(t)=f(x+t(y-x))$ for $t\in [0,1]$ and use the $L$ -Lipschitz continuity to show that $f(y)-f(x)=g(1)-g(0)={\int }_0^1{g}^{\prime }(t)=⟨{\int }_0^1\mathrm{\nabla }f(x+t(y-x))dt,y-x⟩\le ⟨\mathrm{\nabla }f(x),y-x⟩+\frac{L}{2}\Vert y-x{\Vert }^2$.

3. By definition, $f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)+\frac{\mu }{2}\Vert y-x{\Vert }^2$. Now, minimize the left side, we have $$f(x^{*})\ge f(x)+\mathrm{\nabla }f(x{)}^T(x^{*}-x)+\frac{\mu }{2}\Vert x^{*}-x{\Vert }^2$$ then minimize the right side, we have$$f(x)+\mathrm{\nabla }f(x{)}^T(x^{*}-x)+\frac{\mu }{2}\Vert x^{*}-x{\Vert }^2\ge f(x)-\frac{1}{2\mu }\Vert \mathrm{\nabla }f(x){\Vert }^2$$ Combining the two, we have the $\mu$-PL inequality.

$$f\left(x_k\right)-f\left(x^{*}\right)\le {(1-\mu /L)}^k(f\left(x_0\right)-f\left(x^{*}\right))$$

4. $$g(Ay)\ge g(Ax)+⟨\mathrm{\nabla }g(Ax),Ay-Ax⟩+\frac{\mu }{2}\Vert Ay-Ax{\Vert }^2$$

Now, since $\mathrm{\nabla }f(x)=A^T\mathrm{\nabla }g(Ax)$, we have $$f(y)\ge f(x)+⟨\mathrm{\nabla }f(x),y-x⟩+\frac{\mu }{2}\Vert A(y-x){\Vert }^2$$

Set $y$ to be the projection of $x$ to the optimum subspace, then we have $\Vert A(y-x)\Vert \ge \sigma \Vert y-x\Vert$. Thus, we have $$f(y)-f(x)\ge ⟨\mathrm{\nabla }f(x),y-x⟩+\frac{\mu {\sigma }^2}{2}\Vert y-x{\Vert }^2$$ Vary the $y$ on the right side to minimize the right side, we have the desired result.

5. Let $g(x):=\sqrt{f(x)-f^{*}}$. For any $x\in ̸X^{*}$, we have $$\mathrm{\nabla }g(x)=\frac{\mathrm{\nabla }f(x)}{2\sqrt{f(x)-f^{*}}}$$ so by $\mu$ -PL,
$$\Vert \mathrm{\nabla }g(x){\Vert }^2\ge \mu /2$$

In particular, we see that $\mathrm{\nabla }g$ is a vector field on ${\mathbb{ℝ}}^d\setminus X^{*}$ with size at least $\sqrt{\mu /2}$. Define a gradient flow along $\mathrm{\nabla }g$ with constant unit velocity, starting at $x(0)=x$: $$x(0)=x,\dot{x}(t)=\frac{\mathrm{\nabla }g}{\Vert \mathrm{\nabla }g\Vert }$$

Because $g$ is bounded below by $0$, and $\Vert \mathrm{\nabla }g\Vert \ge \sqrt{\mu /2}$, the gradient flow terminates on the zero set $X^{*}$ at a finite time $$T\le g(x)/\sqrt{\mu /2}$$ The path length is $T$, since the velocity is constantly 1.

Since $x(T)$ is on the zero set, and $x^{*}$ is the point closest to $x$, we have $$\Vert x^{*}-x\Vert \le T\le g(x)/\sqrt{\mu /2}$$ which is the desired result.

Gradient descent

Theorem (linear convergence of gradient descent) — If $f$ is $\mu$-PL and $\mathrm{\nabla }f$ is $L$-Lipschitz, then gradient descent with constant step size $\eta$$$x_{k+1}=x_k-\eta \mathrm{\nabla }f(x_k)$$converges linearly as$$f\left(x_k\right)-f\left(x^{*}\right)\le {(1-2\mu \eta (1-L\eta /2))}^k(f\left(x_0\right)-f\left(x^{*}\right)),\eta \in (0,2/L)$$

The convergence is the fastest when $\eta =1/L$, at which point$$f\left(x_k\right)-f\left(x^{*}\right)\le {(1-\mu /L)}^k(f\left(x_0\right)-f\left(x^{*}\right))$$

Proof

Proof

Since $\mathrm{\nabla }f$ is $L$ -Lipschitz, we have the parabolic upper bound $$f(x_{k+1})\le f(x_k)+⟨\mathrm{\nabla }f(x_k),x_{k+1}-x_k⟩+\frac{L}{2}\Vert x_{k+1}-x_k{\Vert }^2$$

Plugging in the gradient descent step, $$\begin{array}{rl}f(x_{k+1})-f(x_k)& \le ⟨\mathrm{\nabla }f(x_k),-\eta \mathrm{\nabla }f(x_k)⟩+\frac{L}{2}\Vert -\eta \mathrm{\nabla }f(x_k){\Vert }^2\\ & =(L{\eta }^2/2-\eta )\Vert \mathrm{\nabla }f(x_k){\Vert }^2\\ & \le 2\mu (L{\eta }^2/2-\eta )(f(x_k)-f(x^{*}))\end{array}$$

Thus, $$f\left(x_k\right)-f\left(x^{*}\right)\le {(1-2\mu \eta (1-L\eta /2))}^k(f\left(x_0\right)-f\left(x^{*}\right))$$

Corollary — 1. $x_k$ converges to the optimum set $X^{*}$ at a rate of $(1-\mu \eta (2-L\eta ))$.

2. If $f$ is $\mu$ -PL, not constant, and $\mathrm{\nabla }f$ is $L$ -Lipschitz, then $L\ge \mu$.

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

$$f\left(x_k\right)-f\left(x^{*}\right)\le {(1-\mu /L)}^k(f\left(x_0\right)-f\left(x^{*}\right))$$

Coordinate descent

The coordinate descent algorithm first samples a random coordinate $i_k$ uniformly, then perform gradient descent by $$x_{k+1}=x_k-\eta {\partial }_{i_k}f(x_k)e_{i_k}$$

Theorem — Assume that $f$ is $\mu$ -PL, and that $\mathrm{\nabla }f$ is $L$ -Lipschitz at each coordinate, meaning that $$|{\partial }_{i}f(x+t{e}_i)-{\partial }_{i}f(x)|\le L|t|$$Then, $\mathbb{𝔼}[f(x_k)-f(x^{*})]$ converges linearly for all $\eta \in (0,2/L)$ by $$\mathbb{𝔼}[f(x_k)-f(x^{*})]\le {(1-\frac{\mu \eta (2-L\eta )}{d})}^k(f(x_0)-f(x^{*}))$$

Proof

Proof

By the same argument, $$f(x_{k+1})\le f(x_k)+(L{\eta }^2/2-\eta )({\partial }_{i_k}f(x_k){)}^2$$

Take expectation with respect to $i_k$, we have $$\mathbb{𝔼}[f(x_{k+1})]\le f(x_k)+\frac{L{\eta }^2/2-\eta }{d}\Vert \mathrm{\nabla }f(x_k){\Vert }^2$$

Plug in the $\mu$ -PL inequality, we have $$\mathbb{𝔼}[f(x_k)-f(x^{*})]\le (1-\frac{\mu \eta (2-L\eta )}{d})(f(x_k)-f(x^{*}))$$Iterating the process, we have the desired result.

Stochastic gradient descent

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

The gradient update step is $$x_{k+1}=x_k-{\eta }_k\mathrm{\nabla }{f}_{i_k}(x_k)$$ where ${\eta }_k>0$ are a sequence of learning rates (the learning rate schedule).

Theorem — If each $\mathrm{\nabla }{f}_i$ is $L$ -Lipschitz, $f$ is $\mu$ -PL, and $f$ has global minimum $f^{*}$, then $$\mathbb{𝔼}[f\left(x_{k+1}\right)-f^{*}]\le (1-2{\eta }_k\mu )[f\left(x_k\right)-f^{*}]+\frac{L{\eta }_k^2}{2}{\mathbb{𝔼}}_i[\Vert \mathrm{\nabla }{f}_i(x_k){\Vert }^2]$$We can also write it using the variance of gradient L2 norm: $$\mathbb{𝔼}[f\left(x_{k+1}\right)-f^{*}]\le (1-\mu (2{\eta }_k-L{\eta }_k^2))[f\left(x_k\right)-f^{*}]+\frac{L{\eta }_k^2}{2}{\mathbb{𝔼}}_i[\Vert \mathrm{\nabla }{f}_i(x_k)-\mathrm{\nabla }f(x_k){\Vert }^2]$$

Proof

Proof

Because all $\mathrm{\nabla }{f}_i$ are $L$ -Lipschitz, so is $\mathrm{\nabla }f$. We thus have $$f(x_{k+1})\le f(x_k)-{\eta }_k⟨\mathrm{\nabla }f(x_k),\mathrm{\nabla }{f}_{i_k}(x_k)⟩+\frac{L{\eta }_k^2}{2}\Vert \mathrm{\nabla }{f}_{i_k}(x_k){\Vert }^2$$

Now, take the expectation over $i_k$, and use the fact that $f$ is $\mu$ -PL. This gives the first equation.

The second equation is shown similarly by noting that $${\mathbb{𝔼}}_i[\Vert \mathrm{\nabla }{f}_i(x_k){\Vert }^2]={\mathbb{𝔼}}_i[\Vert \mathrm{\nabla }{f}_i(x_k)-\mathrm{\nabla }f(x_k){\Vert }^2]+\Vert \mathrm{\nabla }f(x_k){\Vert }^2$$

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 $C>0$ such that during the SG process, we have$${\mathbb{𝔼}}_i[\Vert \mathrm{\nabla }{f}_i(x_k){\Vert }^2]\le C$$ for all $k=0,1,\dots$, then$$\mathbb{𝔼}[f\left(x_{k+1}\right)-f^{*}]\le (1-2{\eta }_k\mu )[f\left(x_k\right)-f^{*}]+\frac{LC{\eta }_k^2}{2}$$Similarly, if $$\mathrm{\forall }k,{\mathbb{𝔼}}_i[\Vert \mathrm{\nabla }{f}_i(x_k)-\mathrm{\nabla }f(x_k){\Vert }^2]\le C$$ then$$\mathbb{𝔼}[f\left(x_{k+1}\right)-f^{*}]\le (1-\mu (2{\eta }_k-L{\eta }_k^2))[f\left(x_k\right)-f^{*}]+\frac{LC{\eta }_k^2}{2}$$

Learning rate schedules

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

For decreasing learning rate schedule with ${\eta }_k=O(1/k)$, we have $\mathbb{𝔼}[f\left(x_k\right)-f^{*}]=O(1/k)$.

References

• Bierstone, Edward; Milman, Pierre D. (1988), "Semianalytic and subanalytic sets", Publications Mathématiques de l'IHÉS 67 (67): 5–42, doi:10.1007/BF02699126, ISSN 1618-1913, http://www.numdam.org/item?id=PMIHES_1988__67__5_0 
• Ji, Shanyu; Kollár, János; Shiffman, Bernard (1992), "A global Łojasiewicz inequality for algebraic varieties", Transactions of the American Mathematical Society 329 (2): 813–818, doi:10.2307/2153965, ISSN 0002-9947, http://www.ams.org/journals/tran/1992-329-02/S0002-9947-1992-1046016-6/ 
• Karimi, Hamed; Nutini, Julie; Schmidt, Mark (2016). "Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak–Łojasiewicz Condition". arXiv:1608.04636 [cs.LG].
• Liu, Chaoyue; Zhu, Libin; Belkin, Mikhail (2022-07-01). "Loss landscapes and optimization in over-parameterized non-linear systems and neural networks". Applied and Computational Harmonic Analysis. Special Issue on Harmonic Analysis and Machine Learning 59: 85–116. doi:10.1016/j.acha.2021.12.009. ISSN 1063-5203. https://www.sciencedirect.com/science/article/abs/pii/S106352032100110X. 

External links

• Hazewinkel, Michiel, ed. (2001), "Lojasiewicz inequality", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Main_Page