Descent lemma ($f(v)\le f(u)+⟨\nabla f(u),v-u⟩+\frac{L}{2}\Vert v-u{\Vert }^2$)

Suppose $f$ is a differentiable function on an open convex set $D\subseteq {\mathbb{R}}^n$ and has an $L$-Lipschitz gradient there, in the Euclidean norm. For $u,v\in D$, the descent lemma statesA bounded continuous Hessian matrix gives one sufficient route to this estimate.^[ref]

For a short proof, put $d=v-u$. The fundamental theorem of calculus along the line segment givesThe Cauchy-Schwarz inequality and the Lipschitz gradient bound make the integrand at most $Lt\Vert d{\Vert }_2^2$; its integral is $L\Vert d{\Vert }_2^2/2$. This proof needs no assumption that $f$ is a convex function.

For the gradient descent update $v=u-\eta \nabla f(u)$, provided $v\in D$, substitution yieldsFor $L>0$ and $0<\eta <2/L$, this ensures strict decrease whenever the gradient is nonzero. At $\eta =2/L$ it guarantees only nonincrease; the quadratic example has a nonshrinking alternating component at this endpoint. At $\eta =1/L$ the guaranteed decrease is $\Vert \nabla f(u){\Vert }_2^2/(2L)$. A bound valid only on $D$ cannot justify a step leaving $D$.

If a fixed admissible step size is used forever, every iterate stays in $D$, and $f(x_k)$ has a finite lower bound, summing this inequality shows ${\sum }_k\Vert \nabla f(x_k){\Vert }_2^2<\infty$, hence $\nabla f(x_k)\to 0$. That conclusion alone gives neither convergence of the iterates nor a global minimum. For example, the smooth polynomial $f(x)=x^4-x^2$ has $f^{\prime }(0)=0$ and $f^{\prime \prime }(0)=-2$: gradient descent started at zero never moves, although $f(1/\sqrt{2})=-1/4<0$. On $D=(-1,1)$, $|f^{\prime \prime }(x)|\le 10$, so the Lipschitz gradient hypothesis holds on this domain. Convex functions and strongly convex functions provide additional structure; the exact quadratic convergence result above uses a positive-definite matrix.