Let $$f(x) := \|x\|_2 + \lambda \|x-y\|_2^2$$ where $\lambda > 0$, and $x, y \in \Bbb R^n$. How to prove that function $f$ is strongly convex?

I tried to prove this using the definition of a strongly convex function:

If $f$ is twice differentiable then it is strongly convex with parameter $m$ if and only if $\nabla^2 f \geq m I$ for any $x$ in the domain

I computed

$$\nabla f = \frac{x}{\|x\|_2} + (x-a), \qquad\qquad \nabla^2f = \frac{I}{\|x\|_2} - \frac{1}{\|x\|_2^2} + I$$

but then I don't know how to proceed to show that $\nabla^2 f \geq mcI$. Moreover, I should prove this for all $x$ in the domain, but this expression is not defined for $x=0$.

  • $\begingroup$ can you include your attempt? $\endgroup$ Apr 23 at 15:27
  • $\begingroup$ @SiongThyeGoh I included my attempt in the original question. $\endgroup$ Apr 23 at 17:42
  • $\begingroup$ Where does $a$ come from? $\endgroup$ Apr 24 at 11:32

Your $f$ is the sum of $\| x \|_2$, which is convex, and a strongly convex function $\lambda \| x - y \|_2^2$. Then you can use this fact:

Fact: If $f_1, f_2$ are convex and $f_2$ is strongly convex with modulus $\mu > 0$, then $f_1 + f_2$ is strongly convex with modulus $\mu$ as well.

You can try to prove this fact just by combining the (sub)gradient inequalities for the two functions.

  • $\begingroup$ Thank you! Can you please tell me the reference of the fact? Is it in a textbook? $\endgroup$ Apr 23 at 18:21
  • $\begingroup$ You can probably find it in standard textbooks in convex analysis, but the proof is really simple: write down the subgradient inequality for $f_1$ and $f_2$, and add them up together. $\endgroup$
    – VHarisop
    Apr 23 at 18:29

We are not supposed to use the definition that you stated as the function is not differentiable.

We can use this definition:

$$\forall t \in [0,1], f(tx_1+(1-t)x_2) \le tf(x_1) + (1-t)f(x_2) - \frac12 mt(1-t)\|x_1-x_2\|_2^2$$

for non-differentiable function.

Let $f_1(x)=\|x\|_2$ and $f_2(x)=\lambda \|x-y\|^2$.

Since $\nabla^2 f_2 = 2\lambda I$, $f_2$ is strongly convex with parameter $2\lambda$.

That is

$$\forall t \in [0,1], f_2(tx_1+(1-t)x_2) \le tf_2(x_1) + (1-t)f_2(x_2) - \lambda t(1-t)\|x_1-x_2\|_2^2$$

$f_1$ being the norm is convex, hence

$$\forall t \in [0,1], f_1(tx_1+(1-t)x_2) \le tf_1(x_1) + (1-t)f_1(x_2) $$

Summing the two inequalities prove that $f$ is strongly convex.


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.