2

Given $f$ is strongly convex with convexity parameter $\sigma$ and $\displaystyle x_0=\arg\min_{x}f(x)$, how do we arrive at the following inequality: $$f(x)\ge f(x_0)+\frac{\sigma}{2}\|x-x_0\|^2$$ Note that $f$ is not assumed to be differentiable.

I tried to prove by contradiction as follows: \begin{align} f(\theta x+(1-\theta)x_0)&\le\theta f(x)+(1-\theta)f(x_0)-\frac{\sigma}{2}\theta(1-\theta)\|x-x_0\|^2\\ &=f(x_0)+\theta\left(f(x)-f(x_0)-\frac{\sigma}{2}\|x-x_0\|^2\right)+\frac{\sigma}{2}\theta^2\|x-x_0\|^2\\ &\qquad\vdots\\ &<f(x_0) \end{align} but I am unable to get the last inequality above.

Sapphire
  • 661

1 Answers1

4

You're almost there. First, if $\sigma=0$ the claimed inequality $$ f(x)\ge f(x_0)+\frac\sigma2|| x-x_0||^2 $$ is obviously true. So assume $\sigma>0$. Suppose that the claimed inequality does not hold for all $x$. Then there exists $x_1$ such that the quantity $$ \delta:=f(x_1)-f(x_0)-\frac\sigma2||x_1-x_0||^2 $$ is strictly negative. Note that $x_1\ne x_0$ (why?). Following your line of reasoning, we have for every $\theta\in(0,1)$: $$ \begin{align} f(x_0)\le f(\theta x_1+(1-\theta)x_0)&\le\theta f(x_1)+(1-\theta)f(x_0)-\frac{\sigma}{2}\theta(1-\theta)\|x_1-x_0\|^2\\ &=f(x_0)+\theta\left(f(x_1)-f(x_0)-\frac{\sigma}{2}\|x_1-x_0\|^2\right)+\frac{\sigma}{2}\theta^2\|x_1-x_0\|^2\\ &=f(x_0)+\delta\theta+\frac\sigma2\theta^2||x_1-x_0||^2 \end{align} $$ Rearrange and conclude that for every $\theta\in(0,1)$,

$$-\delta \le\frac\sigma2\theta\,||x_1-x_0||^2\ .\tag{*} $$ The LHS of (*) is strictly positive. Now your job is to find a small enough $\theta$ for which (*) cannot be true.

grand_chat
  • 38,951