I came into a practice problem on Lipschitz continuous gradient.

Given convex and twice continuously differentiable $f$, prove the following statements are equivalent.

  1. $\nabla f$ is Lipschitz continuous with constant $L$.

  2. $(\nabla f(x) − \nabla f(y))^T (x − y) \leq L \| x − y \|_2^2$ for all $x$, $y$.

$1\to2$ it can be tackled by the Cauchy-Schwartz inequality. However, I can not figure $2\to1$ out.

  • $\begingroup$ Are you sure that the LHS of the second inequality is not $(\triangledown f(x) − \triangledown f(y))^T (\triangledown f(x) −\triangledown f(y))$? $\endgroup$ – user88923 May 8 '19 at 5:32
  • $\begingroup$ Hi, I checked the original statement. The statement indeed is as correct here. $\endgroup$ – JC Wang May 8 '19 at 18:41

It easy to check that 2. is equivalent to the monotonicity of the gradient of the function $g:x\mapsto \frac L2 \|x\|_2^2-f(x)$, which is equivalent to the convexity of $g$.
The Hessian of $g$ at $x$ is $H(g)(x)=LI-H(f)(x)$ where $I$ denotes the identity matrix. Let $\operatorname{spec}(A)$ denote the eigenvalues of any matrix $A$. Note that $\operatorname{spec}(LI-H(f)(x)) = L-\operatorname{spec}(H(f)(x))$, and since $g$ is convex, $\operatorname{spec}(LI-H(f)(x)) \subset [0,\infty)$, hence $\operatorname{spec}(H(f)(x))\subset (-\infty,L]$. Convexity of $f$ implies the refinement $\operatorname{spec}(H(f)(x))\subset [0,L]$.

Let $h:[0,1]\to \mathbb R^n, t\mapsto \nabla(f)(x+t(y-x))$. $h$ is differentiable and $$\begin{aligned}\|h'(t)\|_2=\|H(f)(x+t(y-x))(y-x)\|_2 &\leq \max \left[\operatorname{spec}(H(f)(x+t(y-x)))\right] \|y-x\|_2\\ &\leq L \|y-x\|_2 \end{aligned} $$
The mean value inequality for vector-valued functions yields $\|h(1)-h(0)\|\leq L \|y-x\|_2$, hence the claim.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.