# Proof: Condition for a function being strongly convex

Let $$\lambda \in \mathbb{R}_{> 0}$$. A function $$f : \mathbb{R}^d \to \mathbb{R}$$ is $$\lambda$$-strongly convex, if for all $$\alpha \in (0, 1)$$ and all $$u, v \in \mathbb{R}^d$$ $$f(\alpha u + (1 - \alpha) v) \leq \alpha f(u) + (1 - \alpha) f(v) - \frac{\lambda}{2} \alpha (1 - \alpha) \lVert u - v\rVert^2$$ holds. In this blog post (ii -> iv) I found a condition for $$f$$ being $$\lambda$$-strongly convex:

If $$g(x) = f(x) - \frac{\lambda}{2} \lVert x \rVert^2$$ is convex, then $$f$$ is $$\lambda$$-strongly convex.

The author claims that this condition follows directly from definition of $$g$$ and convexity, however I'm having problems of proofing it for myself. This is basically how far I got:

\begin{align*} &\alpha f(u) + (1 - \alpha) f(v) - \frac{\lambda}{2} \alpha (1 - \alpha) \lVert{u - v}\rVert^2 \\ &= \alpha f(u) + (1 - \alpha) f(v) - \frac{\lambda}{2} \alpha (1 - \alpha) \left({\lVert{u}\rVert^2 + \lVert{v}\rVert^2 - 2\langle u, v\rangle}\right) \\ &\geq \alpha f(u) + (1 - \alpha) f(v) - \frac{\lambda}{2} \alpha (1 - \alpha) \left({\lVert{u}\rVert^2 + \lVert{v}\rVert^2}\right) \\ &= \alpha f(u) + (1 - \alpha) f(v) - \frac{\lambda}{2} \alpha (1 - \alpha) \lVert{u}\rVert^2 - \frac{\lambda}{2} \alpha (1 - \alpha) \lVert{v}\rVert^2 \\ &> \alpha f(u) + (1 - \alpha) f(v) - \frac{\lambda}{2} \alpha \lVert{u}\rVert^2 - \frac{\lambda}{2} (1 - \alpha) \lVert{v}\rVert^2 \\ &= \alpha \left({ f(u) - \frac{\lambda}{2} \lVert{u}\rVert^2 }\right) + (1 - \alpha) \left({ f(v) - \frac{\lambda}{2} \lVert{v}\rVert^2 }\right) \\ &= \alpha g(u) + (1 - \alpha) g(v) \\ &\geq g(\alpha u + (1 - \alpha) v) \\ &= f(\alpha u + (1 - \alpha) v) - \frac{\lambda}{2} \lVert{\alpha u + (1 - \alpha) v}\rVert^2 \\ &= ? \\ &= f(\alpha u + (1 - \alpha) v)\end{align*}

What am I missing?

• You're giving up too much in your inequalities. For insight, consider that without any loss of generality you may take $d=1,$ $u=0,$ and $v=1.$ See what happens in that case. – whuber Jun 7 at 14:23

Thanks to @whuber I noticed that especially the $$-2 \langle u, v \rangle$$-term is to valueable to discard. I restarted the calculation from the other side and was able to show the required bound by using $$\leq$$ exactly one time (applying the premise).
In case anybody else is interested in a sketch of the solution: Start by showing \begin{align*} &f(\alpha u + (1 - \alpha) v) \\ &= f(\alpha u + (1 - \alpha) v) - \frac{\lambda}{2} \lVert{\alpha u + (1 - \alpha) v}\rVert^2 + \frac{\lambda}{2} \lVert{\alpha u + (1 - \alpha) v}\rVert^2 \\ &= \dots \\ &\leq \alpha f(u) + (1 - \alpha) f(v) - \frac{\lambda}{2} \alpha \lVert{u}\rVert^2 - \frac{\lambda}{2} (1 - \alpha) \lVert{v}\rVert^2 + \frac{\lambda}{2} \lVert{\alpha u + (1 - \alpha) v}\rVert^2, \end{align*} and then conclude using only basic linear algebra that $$- \frac{\lambda}{2} \alpha \lVert{u}\rVert^2 - \frac{\lambda}{2} (1 - \alpha) \lVert{v}\rVert^2 + \frac{\lambda}{2} \lVert{\alpha u + (1 - \alpha) v}\rVert^2 = -\frac{\lambda}{2} \alpha (1 - \alpha) \lVert{u - v}\rVert^2.$$