# lower bound of a special type of convex functions

Suppose $f$ is a convex, differentiable and $\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$. The minimum of $f$ is $0$. ($f$ may not be twice differentiable.)

How to show $f(x)\geq\frac{1}{2L}\|\nabla f(x)\|^2$, $\forall x$?

-

I'll assume $f$ is defined on all of $\mathbb{R}^n$. Let $f^* = \inf_{y \in \mathbb{R}^n} f(y)$. (You have told us that $f^* = 0$, but I prefer just to call it $f^*$.)

Because $\nabla f(x)$ is Lipschitz continuous with parameter $L$, we have the following quadratic upper bound on $f$:

$$f(y) \leq f(x) + \langle \nabla f(x),y - x \rangle + \frac{L}{2} \| y - x \|^2$$ for all $x,y \in \mathbb{R}^n$.

It follows that $$\inf_y \, f(y) \leq \inf_y \, f(x) + \langle \nabla f(x),y - x \rangle + \frac{L}{2} \| y - x \|^2$$ for all $x \in \mathbb{R}^n$.

The infimum on the left hand side is just $f^*$. The infimum on the right hand side is $f(x) -\frac{1}{2L} \| \nabla f(x) \|^2$. Thus we find that \begin{align*} & f^* \leq f(x) - \frac{1}{2L} \| \nabla f(x) \|^2 \\ \implies& f(x) - f^* \geq \frac{1}{2L} \| \nabla f(x) \|^2. \end{align*}

This result appears in chapter 1 ("Gradient method") of Vandenberghe's 236c lecture notes (see slide 1-14 entitled "Quadratic upper bound").

-
Thank you, littleO, especially for pointing out the reference. –  mining Nov 10 '12 at 19:32

I started this last night, but got stuck with the transition from the one dimensional example back to $f$. (A problem related to the Pinot Grigio technique I was using, I think.)

Let $\phi:\mathbb{R}\to [0,\infty)$ be convex, differentiable, $\phi'$ Lipschitz continuous with rank $L$. Then Taylor gives: $\phi(y) = \phi(x)+\phi'(x)(y-x) + \int_x^y (\phi'(t)-\phi'(x) )dt \leq \phi(x)+\phi'(x)(y-x) + L\int_x^y |t-x|dt$. Integrating gives the bound $\phi(y) \leq \phi(x)+\phi'(x)(y-x) + \frac{L}{2} (y-x)^2$. By assumption $\phi(t) \geq 0$, so we have $\phi(x)+\phi'(x)(y-x) + \frac{L}{2} (y-x)^2 \geq 0$ for all $x,y$. Minimizing over $y$ gives $\phi(x) \geq \frac{1}{2L} (\phi'(x))^2$, which is basically the desired result.

To connect with $f$ above, choose $x\neq y$, and let $\phi(t) = \frac{f(y+t(x-y))}{\|x-y\|^2}$, then $\phi'(t) = \frac{\partial f(y+t(x-y))}{\partial x}\frac{(x-y)}{\|x-y\|^2}$, and a quick computation shows $|\phi'(t)-\phi'(s)|\leq L|t-s|$. This gives $\phi(1) \geq \frac{1}{2L} (\phi'(1))^2$, or equivalently, $f(x) \geq \frac{1}{2L} |\frac{\partial f(x)}{\partial x}\frac{(x-y)}{\|x-y\|}|^2$ (for all $x\neq y$). Since $\|v\| = \max_{\|u\|=1} |v^T u|$, this gives the desired result $f(x) \geq \frac{1}{2L} \|\frac{\partial f(x)}{\partial x}\|^2$.

-
Thank you, copper.hat. –  mining Nov 10 '12 at 19:32
You are welcome, sorry I left you hanging last night. Late night brain fuzz... –  copper.hat Nov 10 '12 at 19:40

Let $f : {\bf R}^n \rightarrow {\bf R}$ be a function such that $f(0)=0$ and $f$ is a nonconstant nonnegative function.

$c(t) = tx$ with $|x|=1$

Then $h(t)=f(c(t))$ has $h''(t) = (\nabla f(tx)\cdot x)' = x^T$Hess$(f)(tx) x$

Note : $h(0) =0$

$| \nabla f (y) - \nabla f(tx) |(1/|y-tx|) \leq L$ implies $lim_{y\rightarrow tx}|Hess(f)(tx) (y-tx)|(1/|y-tx|) \leq L$ So $|Hess(f)| \leq nL$ where $|(a_{ij})|^2 = \sum_{i,j} a_{ij}^2$

Recall $\sum_{i,j} |a_{ij}| \leq C(n)L$ where $C(n)$ is a constant depending on $n$.

This implies $0\leq h''(t) \leq D(n)$ for all $t$ and for some constant $D$

Let $h''(t) = h''(0)+ \sum_{k=1} \frac{1}{k!} h^{(k+2)}(0)t^k$ be a Taylor series.

So $0\leq h''(0)+ \sum_{k=1} \frac{1}{k!} h^{(k+2)}(0)t^k \leq D(n)$

So $0\leq \frac{ h''(0)}{t} + \sum_{k=1} \frac{1}{k!} h^{(k+2)}(0)t^{k-1} \leq \frac{D(n)}{t}$ From $t \rightarrow \infty$ we have $h^{(k)}=0$ for all $k\geq 3$

This implies $h(t) = at^2+bt$ ($a \geq 0$). From $|\nabla f (tx) | \leq L |tx|$, $h'(t) \leq L|t||x|^2=L|t|$ So $b=0$

Note that $a(x)=\frac{1}{2} x^T$ Hess$(f)(0) x$ Accordingly $f(x) =\frac{1}{2} x^T Hess(f)(0) x$ and $\nabla f(x) =$Hess$(f)(0) x$

Let $\lambda_i (\lambda_i \leq \lambda_{i+1})$ be a nonnegative eigenvalues of Hess$(f)(0)$ Then $\lambda_n \leq L$ and $|Hess(f)(0) x|^2 \leq L |x^T Hess(f)(0) x|$ So we finish the proof.

-
$f$ is not necessarily twice differentiable... –  copper.hat Nov 10 '12 at 6:58
Yeah, that's the difficulty. –  mining Nov 10 '12 at 7:02
It's not insurmountable, you could note that this essentially a one dimensional problem, and the the derivative is AC, and use the integral form of the Taylor expansion. However, I think there is a more direct way, it's just not happening for me now! –  copper.hat Nov 10 '12 at 7:08
Can you explain a little bit more on how to use Taylor expansion? Thanks. –  mining Nov 10 '12 at 7:17
Sorry, I was 'thinking out loud'. I haven't worked out the details... –  copper.hat Nov 10 '12 at 7:20