1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – whuber Jun 7 at 14:23
1
$\begingroup$

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. $$

| cite | improve this answer | |
$\endgroup$

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.