Lemma: Given $f(x)$ convex and $L$-smooth then $$f(y)-f(x)\leq \nabla f(y)^T(y-x) - \frac{1}{2L}||\nabla f(y) - \nabla f(x)||_2^2.$$
In order to prove this lemma the following are used:
- Because of the convexity of $f$ we have $$f(z)\geq f(y) + \nabla f(y)^T(z-y) \iff \\ f(y)-f(z) \leq \nabla f(y)^T(y-z) \tag{1}$$
- Because $f$ is $L$ smooth we have: $$f(z)\leq f(x)+\nabla f(x)^T (z-x) + \frac{L}{2}||z-x||_2^2 \iff \\ f(z)-f(x) \leq \nabla f(x)^T (z-x) + \frac{L}{2}||z-x||_2^2\tag{2}$$ Using $(1)$ and $(2)$ we have: $$f(y)-f(x)=f(y)-f(z)+f(z)+f(x)\leq \\\nabla f(y)^T (y-z) + \nabla f(x)^T (z-x) + \frac{L}{2}||z-x||_2^2 \tag{3}.$$ The minimum of he right side of inequality is $z=x-\frac{1}{L}(\nabla f(x) - \nabla f(y)).$ Substituting $z$ in the previous inequality we have: $$f(y)-f(x)\leq \nabla f(y)^T(y-x) -\frac{1}{2L}||\nabla f(x) - \nabla f(y)||\tag{4}.$$
I am trying to conclude with a similar lemma but with $f$ is concave. I started with the same rationale but with: $$f(z)\leq f(y) + \nabla f(y)^T(z-y) \iff \\ f(y)-f(z) \geq \nabla f(y)^T(z-y) \iff \\ f(z)-f(y) \geq \nabla f(y)^T(y-z) \tag{5}$$ instead of $(1)$ as $f$ is concave now. Starting with the same rationale and combining $(2)$ and $(5)$, $$f(y)-f(x)=f(y)-f(z)+f(z)+f(x)=\dots$$ does not help. Is it possible to prove the lemma with $f$ concave? How should we proceed?
Thanks.