Inequality of convex function with Lipschitz continuous gradient

Question

I am interested in proving the following inequality for a convex function $g$ with $L$-Lipschitz continuous gradient:

For $\alpha \in [0,1]$, $$g(\alpha x + (1- \alpha)y) \leq \alpha g(x) + (1-\alpha)g(y) – \frac{\alpha (1-\alpha)}{2 L} \left\| \nabla g(x) – \nabla g(y) \right\|^2 $$

I have tried to apply the definitions of convexity but have not been able to prove this.

Answer 1

Hint: your claim will follow from the following lower bound:

Lemma: if $g$ is convex and $L$-smooth, then for any $x, y$ we have $$ g(y) \geq g(x) + \langle \nabla g(x), y - x \rangle + \frac{1}{2L} \lVert \nabla g(x) - \nabla g(y) \rVert^2. $$

Proof sketch: note that since $g$ is $L$-smooth, it satisfies

$$ g(y) \leq g(x) + \langle \nabla g(x), y - x \rangle + \frac{L}{2} \lVert y -x \rVert^2 $$

Let $h(y) := g(y) - \langle \nabla g(x), y \rangle$, which is also convex and $L$-smooth (why?) and minimized at $x$. Then:

$$ h(x) \leq \min_{z} h(z) \overset{(\text{smoothness})}{\leq} \min_{z} \left\{ h(y) + \langle \nabla h(y), z - y \rangle + \frac{L}{2} \lVert y - z \rVert^2 \right\} $$

Try finding the minimizer in the expression on the RHS above and rearranging, and you obtain the lemma.