A differentiable function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ is said to have Lipschitz continuous gradient with modulus $L>0$ if
$$
||\nabla f(\mathbf{x}) – \nabla f(\mathbf{y})\|\leq L\|\mathbf{x}-\mathbf{y}\|,\, \forall \mathbf{x},\mathbf{y} \in \mathbb{R}^n \tag{1}
$$
The above is the sufficient condition to get the following:
$$
f(\mathbf{y}) \leq f(\mathbf{x}) + \langle \nabla f(\mathbf{x}) , \mathbf{y}-\mathbf{x} \rangle + \frac{L}{2}\|\mathbf{y}-\mathbf{x}\|^2 \quad \forall \mathbf{x},\mathbf{y} \in \mathbb{R}^n \tag{2}
$$
Under what condition (2) implies (1)?
Note: for $f(x)=\frac{1}{2}||Ax-b||^2$ we can make it work. I am looking for another cases.
Best Answer
If $f$ is convex, then (2) implies (1). Take $x\ne y$ and $d\ne0$. Set ${\bf y}:=y+d$, ${\bf x}:=x$ in (2), ${\bf y}:=x-d$, ${\bf x}:=y$ in (2) and add the resulting inequalities: $$ f(y+d) + f(x-d) \le f(x) + \nabla f(x)(y+d-x) + \frac L2 \|y+d-x\|^2\\ + f(y)+ \nabla f(y)(x-d-y) + \frac L2 \|x-d-y\|^2 $$ which is equivalent to $$ f(y+d)-f(y) + f(x-d) - f(x) \le (\nabla f(x) - \nabla f(y))(y-x+d) + L \|x-y-d\|^2. \tag{3} $$ Since $f$ is assumed to be convex, the left-hand side is larger than $(\nabla f(y)-\nabla f(x))d$, which results in the inequality $$ (\nabla f(x) - \nabla f(y))(x-y-2d) \le L \|x-y-d\|^2. $$ Set $e:=\frac1L(\nabla f(x) - \nabla f(y))$ and $d:=\frac12(x-y-e)$. Using the definition of $d$ implies $$ (\nabla f(x) - \nabla f(y))e \le \frac L4 \|x-y+e\|^2 \le \frac L2 \|x-y\|^2 + \frac L2 \|e\|^2, $$ while the definition of $e$ implies $$ \frac1L \|\nabla f(x) - \nabla f(y)\|^2 \le \frac L2 \|x-y\|^2 + \frac1{2L} \|\nabla f(x) - \nabla f(y)\|^2,$$ which implies $$ \frac1{2L} \|\nabla f(x) - \nabla f(y)\|^2 \le \frac L2 \|x-y\|^2, $$ and the claim is proven.
If $f$ is concave, then (2) holds automatically for all $L\ge 0$. So any concave function whose gradient is not Lipschitz is a counterexample to the claim (2) $\Rightarrow$ (1).
If in addition to (2) the lower bound $$ f(y) \ge f(x) + \nabla f(x)(y-x) - \frac L2 \|x-y\|^2\quad \forall x,y\in \mathbb R^n $$ is satisfied then one can proceed in (3) using this lower bound (instead of convexity). The resulting inequality is then (if I'm not mistaken) $$ (\nabla f(x) - \nabla f(y))(x-y-2d) \le L \|x-y-d\|^2 + L\|d\|^2. $$ With the same choice of $d$ and $e:=\frac1{2L}(\nabla f(x) - \nabla f(y))$ one gets (1).