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 Rn, 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 Boris Polyak, is commonly used to prove linear convergence of gradient descent algorithms. This section is based on and.

Definitions

f is a function of type \R^d \to \R, and has a continuous derivative \nabla f. X^* is the subset of \R^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. \nabla f is L-Lipschitz continuous iff f is \mu-strongly convex iff f is \mu-PL (where "PL" means "Polyak-Łojasiewicz") iff

Basic properties

Gradient descent

Coordinate descent

The coordinate descent algorithm first samples a random coordinate i_k uniformly, then perform gradient descent by

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, where f_i are such that 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 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 for all, thenSimilarly, if then

Learning rate schedules

For constant learning rate schedule, with, we haveBy induction, we have 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, we have.