Lipschitz gradient ($\Vert \nabla f(x)-\nabla f(y){\Vert }_2\le \beta \Vert x-y{\Vert }_2$)

A differentiable function has a $\beta$-Lipschitz gradient on a set $D$ if its gradient satisfies Lipschitz continuity there:All norms here are the Euclidean norm. The constant limits how fast the gradient changes; it is not a bound on the magnitude of the gradient. For $f(x)=(x_1^2+9x_2^2)/2$, the gradient is the linear map $x\mapsto \mathrm{diag}(1,9)x$. Its operator norm is $9$, so $\beta =9$ works globally and is sharp by taking $x-y=(0,1{)}^T$. The gradient itself is unbounded on the whole Euclidean space.

If $f$ has a continuous Hessian matrix on an open convex set $D$ and $\Vert {\nabla }^{2}f(z){\Vert }_2\le \beta$ throughout $D$, integrate that linear map along the line segment from $x$ to $y$:The operator norm bound proves the displayed Lipschitz continuity. Convexity of the domain keeps the entire line segment inside it. Bounding the Hessian matrix only at the endpoints is insufficient.

For a continuously differentiable convex function on ${\mathbb{R}}^n$ with coordinate Lipschitz continuity constants $L_i$, its block coordinate gradient is Lipschitz continuous along each corresponding coordinate subspace, with constant at most $S_{\mathcal{B}}={\sum }_{i\in \mathcal{B}}{L}_i$.

To prove this without assuming a Hessian matrix, put ${\delta }_{\mathcal{B}}={\nabla }_{\mathcal{B}}f(x)-{\nabla }_{\mathcal{B}}f(y)$. Sum the coordinate derivative bound by Bregman divergence over the block, then repeat with $x,y$ interchanged and average:If $x-y$ is supported in the block, the dot product uses only ${\delta }_{\mathcal{B}}$. The Cauchy-Schwarz inequality and cancellation of its Euclidean norm give the result, including the zero case separately. Taking the full block supplies a global Lipschitz gradient constant ${\sum }_i{L}_i$.

Target: convex-optimization.bigb, under Coordinate descent.

Suppose $f$ is a differentiable convex function with coordinate Lipschitz continuity constant $L_i>0$. Put $\varphi (u)=D_f(u,y)=f(u)-f(y)-\nabla f(y{)}^T(u-y)$, the Bregman divergence from the supporting affine function at $y$. The subgradient inequality gives $\varphi \ge 0$, and its coordinate Lipschitz constant is still $L_i$. The coordinate descent lemma with step size $1/L_i$ yieldsSince ${\partial }_i\varphi (x)={\partial }_{i}f(x)-{\partial }_{i}f(y)$, rearrangement proves the bound. Continuous differentiability suffices; a Hessian matrix is unnecessary.

Target: gradient-descent.bigb, under Lipschitz gradient.

The displayed estimate, for all $x$ and real $t$, defines a coordinate Lipschitz constant $L_i$ for the partial derivative in coordinate $i$. It implies the coordinate descent lemmaby the fundamental theorem of calculus and integration of the Lipschitz continuity estimate. Subtracting an affine function leaves these constants unchanged.

The apparently weaker estimate along the singleton negative gradient direction is equivalent when every real step size is allowed: if the initial partial derivative is nonzero, any displacement can be written $-\alpha {\partial }_{i}f(x)e_i$; if it is zero but the final partial derivative is nonzero, reverse the endpoints; if both vanish the estimate is trivial.

Target: gradient-descent.bigb, under Lipschitz gradient.

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.