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
dist ( x , Z ) α ≤ C | f ( x ) | . {\displaystyle \operatorname {dist} (x,Z)^{\alpha }\leq C|f(x)|.}
Here, α {\displaystyle \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 ) | θ ≤ c | ∇ f ( x ) | . {\displaystyle |f(x)-f(p)|^{\theta }\leq c|\nabla f(x)|.}
The proof for the one-dimensional case uses the order of vanishing: if f(x) − f(p) = (x − p)k · g(x) with g(p) ≠ 0, then θ = (k − 1)/k works for k ≥ 2, and θ = 1/2 works for k = 1.
Polyak inequality A special case of the Łojasiewicz inequality, due to Polyak (see condition C in ), is commonly used to prove linear convergence of gradient descent algorithms. This section is based on Karimi, Nutini & Schmidt (2016) and Liu, Zhu & Belkin (2022).
Definitions
f {\textstyle f} is a function of type R d → R {\textstyle \mathbb {R} ^{d}\to \mathbb {R} } , and has a continuous derivative ∇ f {\displaystyle \nabla f} .
X ∗ {\displaystyle X^{*}} is the subset of R d {\displaystyle \mathbb {R} ^{d}} on which f {\displaystyle f} achieves its global minimum (if one exists). Throughout this section we assume such a global minimum value f ∗ {\displaystyle f^{*}} exists, unless otherwise stated. The optimization objective is to find some point x {\displaystyle x} in X ∗ {\displaystyle X^{*}} .
μ , L > 0 {\textstyle \mu ,L>0} are constants.
∇ f {\textstyle \nabla f} is L {\displaystyle L} -Lipschitz continuous if
‖ ∇ f ( x ) − ∇ f ( y ) ‖ ≤ L ‖ x − y ‖ , ∀ x , y {\displaystyle \|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|,\quad \forall x,y}
f {\textstyle f} is μ {\textstyle \mu } -strongly convex iff f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) + μ 2 ‖ y − x ‖ 2 ∀ x , y {\displaystyle f(y)\geq f(x)+\nabla f(x)^{T}(y-x)+{\frac {\mu }{2}}\lVert y-x\rVert ^{2}\quad \forall x,y}
f {\textstyle f} is μ {\textstyle \mu } -PL (where "PL" means "Polyak-Łojasiewicz") iff 1 2 ‖ ∇ f ( x ) ‖ 2 ≥ μ ( f ( x ) − f ( x ∗ ) ) , ∀ x {\displaystyle {\frac {1}{2}}\|\nabla f(x)\|^{2}\geq \mu \left(f(x)-f(x^{*})\right),\quad \forall x}
Basic properties
Gradient descent
Coordinate descent The coordinate descent algorithm first samples a random coordinate i k {\textstyle i_{k}} uniformly, then perform gradient descent by x k + 1 = x k − η ∂ i k f ( x k ) e i k {\displaystyle 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 ) {\textstyle f(x)} , but we cannot sample its gradient directly. Instead, we sample a random gradient ∇ f i ( x ) {\textstyle \nabla f_{i}(x)} , where f i {\textstyle f_{i}} are such that f ( x ) = E i [ f i ( x ) ] {\displaystyle f(x)=\mathbb {E} _{i}[f_{i}(x)]} For example, in typical machine learning, x {\textstyle x} are the parameters of the neural network, and f i ( x ) {\textstyle f_{i}(x)} is the loss incurred on the i {\textstyle i} -th training data point, while f ( x ) {\textstyle f(x)} is the average loss over all training data points. The gradient update step is x k + 1 = x k − η k ∇ f i k ( x k ) {\displaystyle x_{k+1}=x_{k}-\eta _{k}\nabla f_{i_{k}}(x_{k})} where η k > 0 {\textstyle \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 {\textstyle C>0} such that during the SG process, we have E i [ ‖ ∇ f i ( x k ) ‖ 2 ] ≤ C {\displaystyle \mathbb {E} _{i}[\|\nabla f_{i}(x_{k})\|^{2}]\leq C} for all k = 0 , 1 , … {\textstyle k=0,1,\dots } , then E [ f ( x k + 1 ) − f ∗ ] ≤ ( 1 − 2 η k μ ) [ f ( x k ) − f ∗ ] + L C η k 2 2 {\displaystyle \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}}} Similarly, if ∀ k , E i [ ‖ ∇ f i ( x k ) − ∇ f ( x k ) ‖ 2 ] ≤ C {\displaystyle \forall k,\quad \mathbb {E} _{i}[\|\nabla f_{i}(x_{k})-\nabla f(x_{k})\|^{2}]\leq C} then E [ f ( x k + 1 ) − f ∗ ] ≤ ( 1 − μ ( 2 η k − L η k 2 ) ) [ f ( x k ) − f ∗ ] + L C η k 2 2 {\displaystyle \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 {LC\eta _{k}^{2}}{2}}}
Learning rate schedules For constant learning rate schedule, with η k = η = 1 / L {\textstyle \eta _{k}=\eta =1/L} , we have E [ f ( x k + 1 ) − f ∗ ] ≤ ( 1 − μ / L ) [ f ( x k ) − f ∗ ] + C 2 L {\displaystyle \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}}} By induction, we have E [ f ( x k ) − f ∗ ] ≤ ( 1 − μ / L ) k [ f ( x 0 ) − f ∗ ] + C 2 μ {\displaystyle \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 }}} We see that the loss decreases in expectation first exponentially, but then stops decreasing, which is caused by the C / ( 2 L ) {\textstyle 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 {\textstyle x_{k}} starts doing a random walk in the vicinity of X ∗ {\textstyle X^{*}} . For decreasing learning rate schedule with η k = O ( 1 / k ) {\textstyle \eta _{k}=O(1/k)} , we have E [ f ( x k ) − f ∗ ] = O ( 1 / k ) {\displaystyle \mathbb {E} \left[f\left(x_{k}\right)-f^{*}\right]=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, MR 0972342, S2CID 56006439 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, JSTOR 2153965, MR 1046016 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. arXiv:2003.00307. doi:10.1016/j.acha.2021.12.009. ISSN 1063-5203.
External links "Lojasiewicz inequality", Encyclopedia of Mathematics, EMS Press, 2001 [1994]