Łojasiewicz inequality explained

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

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

Polyak inequality

A special case of the Łojasiewicz inequality, due to, is commonly used to prove linear convergence of gradient descent algorithms. This section is based on and .

Definitions

$f$ is a function of type $\backslash R^d\; \backslash to\; \backslash R$, and has a continuous derivative

. is the subset of on which achieves its global minimum (if one exists). Throughout this section we assume such a global minimum value exists, unless otherwise stated. The optimization objective is to find some point in .

$\backslash mu,\; L\; >\; 0$ are constants.

$\backslash nabla\; f$ is

-Lipschitz continuous iff

$$\backslash |\backslash nabla\; f(x)\; -\; \backslash nabla\; f(y)\backslash |\; \backslash leq\; L\; \backslash |x\; -\; y\backslash |,\; \backslash quad\; \backslash forall\; x,\; y$$

$f$ is $\backslash mu$-strongly convex iff$$f(y)\backslash ge\; f(x)+\backslash nabla\; f(x)^T(y-x)+\backslash frac\backslash lVert\; y-x\; \backslash rVert^2\; \backslash quad\; \backslash forall\; x,\; y$$

$f$ is $\backslash mu$-PL (where "PL" means "Polyak-Łojasiewicz") iff$$\backslash frac\backslash |\backslash nabla\; f(x)\backslash |^2\; \backslash geq\; \backslash mu\backslash left(f(x)-f(x^*)\backslash right),\; \backslash quad\; \backslash forall\; x$$

Coordinate descent

The coordinate descent algorithm first samples a random coordinate $i\_k$ uniformly, then perform gradient descent by $$x\_\; =\; x\_k\; -\; \backslash eta\; \backslash partial\_\; f(x\_k)\; e\_$$

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 $\backslash nabla\; f\_i(x)$, where $f\_i$ are such that $$f(x)\; =\; \backslash mathbb\; E\_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\_\; =\; x\_k\; -\; \backslash eta\_k\; \backslash nabla\; f\_(x\_k)$$ where $\backslash 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$$\backslash mathbb\; E\_i[\backslash |\backslash nabla\; f\_i(x\_k)\backslash |^2]\; \backslash leq\; C$$ for all $k\; =\; 0,\; 1,\; \backslash dots$, then$$\backslash mathbb\backslash left[f\backslash left(x\_\{k+1\}\backslash right)-f^*\backslash right]\; \backslash leq\backslash left(1-2\; \backslash eta\_k\; \backslash mu\backslash right)\backslash left[f\backslash left(x\_k\backslash right)-f^*\backslash right]+\backslash frac$$Similarly, if $$\backslash forall\; k,\; \backslash quad\; \backslash mathbb\; E\_i[\backslash |\backslash nabla\; f\_i(x\_k)\; -\; \backslash nabla\; f(x\_k)\backslash |^2]\backslash leq\; C$$ then$$\backslash mathbb\backslash left[f\backslash left(x\_\{k+1\}\backslash right)-f^*\backslash right]\; \backslash leq\backslash left(1-\backslash mu\; (2\backslash eta\_k\; -\; L\backslash eta\_k^2)\backslash right)\backslash left[f\backslash left(x\_k\backslash right)-f^*\backslash right]+\backslash frac$$

Learning rate schedules

For constant learning rate schedule, with $\backslash eta\_k\; =\; \backslash eta\; =\; 1/L$, we have$$\backslash mathbb\backslash left[f\backslash left(x\_\{k+1\}\backslash right)-f^*\backslash right]\; \backslash leq\backslash left(1-\backslash mu/L\backslash right)\backslash left[f\backslash left(x\_k\backslash right)-f^*\backslash right]+\backslash frac$$By induction, we have $$\backslash mathbb\backslash left[f\backslash left(x\_\{k\}\backslash right)-f^*\backslash right]\; \backslash leq\backslash left(1-\backslash mu/L\backslash right)^k\; \backslash left[f\backslash left(x\_0\backslash right)-f^*\backslash right]+\backslash frac$$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 $\backslash eta\_k\; =\; O(1/k)$, we have

.

References

• • • 1608.04636 . cs.LG . Hamed . Karimi . Julie . Nutini . Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak–Łojasiewicz Condition . Mark . Schmidt . 2016.
• 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 . 10.1016/j.acha.2021.12.009 . 1063-5203. 2003.00307 .