Ł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 ƒ : 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 α 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 ∈ 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 Template:Ill, is commonly used to prove linear convergence of gradient descent algorithms. This section is based on Template:Harvtxt and Template:Harvtxt.

Definitions

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

$X^{*}$ is the subset of ${ℝ}^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$$

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}$$

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)={𝔼}_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).

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$${𝔼}_i[\Vert \mathrm{\nabla }{f}_i(x_k){\Vert }^2]\le C$$ for all $k=0,1,\dots$, then$$𝔼[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,{𝔼}_i[\Vert \mathrm{\nabla }{f}_i(x_k)-\mathrm{\nabla }f(x_k){\Vert }^2]\le C$$ then$$𝔼[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$$𝔼[f\left(x_{k+1}\right)-f^{*}]\le (1-\mu /L)[f\left(x_k\right)-f^{*}]+\frac{C}{2L}$$By induction, we have $$𝔼[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 $𝔼[f\left(x_k\right)-f^{*}]=O(1/k)$.

References

• Template:Citation
• Template:Citation
• Template:Cite arXiv
• Template:Cite journal

External links

• Template:SpringerEOM